Submission #19723637


Source Code Expand

Copy
#include <bits/stdc++.h>
// #include <atcoder/all>
#define REP(i, n) for(ll i = 0; i < (n); i++)
#define REP1(i, n) for(ll i = 1; i <= (n); i++)
#define REPD(i,a,b) for (ll i=(a);i<=(b);i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
// using namespace atcoder;
typedef long long ll;
typedef double d;
typedef long double ld;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<d> vd;
typedef vector<ld> vld;
typedef set<int> si;
typedef vector<si> vsi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pi;
typedef queue<int> qi;
typedef queue<pi> qpi;
typedef pair<ll, ll> pll;
typedef queue<pll> qpll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef map<int, int> mii;
const int MOD = 1000000007;
const int INF = 1001001001;
// 小数点 << fixed << setprecision(10) <<
// sort降順 sort(ALL(),greater<int>());
// 円周率 M_PI
// 文字判定 isupper islower
// 順列 do {} while(next_permutation(ALL(X)));
// 最大値 LLONG_MAX
// a内でx以上 auto iter = lower_bound(ALL(a), x);
// a内でxより大きい auto iter = upper_bound(ALL(a), x);
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
// struct edge {
//     int from; //出発点
//     int to;   //到達点
//     int cost; //移動コスト
// };
// typedef struct edge se;
// typedef vector<edge> ve;

// SegTree用
ll op(ll x, ll y) {return max(x,y);}
ll e() {return 0;}

// 重複した要素を取り除いて返す
vll deleteDuplication(vll &numberlist) {
  sort(ALL(numberlist));
  numberlist.erase(unique(ALL(numberlist)),numberlist.end());
  return numberlist;
}

// 2つの数の最大公約数を求める
unsigned Euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) return Euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

// 各桁の数を合計
int digit_sum(int n) {
  int sum=n%10;
  while(n!=0) {
    n/=10;
    sum+=n%10;
  }
  return sum;
}

// 素因数分解してペアのリストを返す
vpll PrimeFactorization(ll n) {
  vpll res;
  for (ll i=2; i*i<=n; i++) {
    if(n%i!=0) continue;
    ll ex=0;
    while(n%i==0) {
      ex++;
      n/=i;
    }
    res.push_back(pll(i,ex));
  }
  if(n!=1) res.push_back(pll(n,1));
  return res;
}

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll combination(ll n, ll r) {
  if ( r * 2 > n ) r = n - r;
  ll x = 1;
  for ( ll i = 1; i <= r; ++i ) {
    x *= (n-i+1);
    x  /= i;
  }
  return x;
}

// Union-Find
struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

// 変数

int main() {
  ll n,C;
  cin >> n >> C;
  ll a[n],b[n],c[n];
  map<ll,ll> event;
  ll ans=0;
  REP(i,n) {
    cin >> a[i] >> b[i] >> c[i];
    event[a[i]]+=c[i];
    event[b[i]+1]-=c[i];
  }
  ll initial=0;
  ll yen=0;
  for(auto i:event) {
    ll tempDay=i.first-initial;
    ans+=min(yen,C)*tempDay;
    initial=i.first;
    yen+=i.second;
  }
  cout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task D - Snuke Prime
User Iorn
Language C++ (GCC 9.2.1)
Score 400
Code Size 3738 Byte
Status AC
Exec Time 492 ms
Memory 33260 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 28
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 8 ms 3584 KB
random_02.txt AC 2 ms 3584 KB
random_03.txt AC 2 ms 3456 KB
random_04.txt AC 3 ms 3480 KB
random_05.txt AC 2 ms 3396 KB
random_06.txt AC 5 ms 3600 KB
random_07.txt AC 2 ms 3460 KB
random_08.txt AC 2 ms 3396 KB
random_09.txt AC 3 ms 3476 KB
random_10.txt AC 2 ms 3456 KB
random_11.txt AC 3 ms 3424 KB
random_12.txt AC 2 ms 3400 KB
random_13.txt AC 3 ms 3612 KB
random_14.txt AC 2 ms 3476 KB
random_15.txt AC 2 ms 3452 KB
random_16.txt AC 102 ms 11692 KB
random_17.txt AC 208 ms 20052 KB
random_18.txt AC 175 ms 17796 KB
random_19.txt AC 156 ms 16728 KB
random_20.txt AC 426 ms 32856 KB
random_21.txt AC 310 ms 24952 KB
random_22.txt AC 40 ms 6300 KB
random_23.txt AC 492 ms 33084 KB
random_24.txt AC 482 ms 33260 KB
random_25.txt AC 154 ms 8144 KB
sample_01.txt AC 3 ms 3528 KB
sample_02.txt AC 3 ms 3584 KB
sample_03.txt AC 2 ms 3596 KB