AtCoder Grand Contest 018

Submission #5887898

Source codeソースコード

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < b; i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define fore(i, a) for (auto &i : a)
#pragma GCC optimize("-O3")
using namespace std;
void _main();
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  _main();
}

typedef long long ll;
#define INF 1LL << 60
int X, Y, Z, N;
ll A[101010], B[101010], C[101010];
ll AA[101010], BB[101010];
ll dp1[101010];
void dodp1() {
  priority_queue<ll> que;
  rep(i, 0, N) dp1[i] = -INF;
  ll sm = 0;

  rep(i, 0, N) {
    que.push(-BB[i]);
    sm += BB[i];
    if (Y < que.size()) {
      ll q = -que.top();
      sm -= q;
      que.pop();
    }
    if (que.size() == Y) dp1[i] = sm;
  }
}
ll dp2[101010];
void dodp2() {
  priority_queue<ll> que;
  rep(i, 0, N) dp2[i] = -INF;
  ll sm = 0;

  rrep(i, N - 1, 0) {
    que.push(-AA[i]);
    sm += AA[i];
    if (X < que.size()) {
      ll q = -que.top();
      sm -= q;
      que.pop();
    }
    if (que.size() == X) dp2[i] = sm;
  }
}
void _main() {
  cin >> X >> Y >> Z;
  N = X + Y + Z;
  rep(i, 0, N) cin >> A[i] >> B[i] >> C[i];

  ll ans = 0;
  rep(i, 0, N) {
    ans += C[i];
    A[i] -= C[i];
    B[i] -= C[i];
  }

  vector<int> v;
  rep(i, 0, N) v.push_back(i);
  sort(v.begin(), v.end(), [&](int a, int b) { return A[a] - B[a] < A[b] - B[b]; });
  rep(i, 0, N) {
    int j = v[i];
    AA[i] = A[j];
    BB[i] = B[j];
  }

  dodp1();
  dodp2();

  ll ma = -INF;
  rep(k, 0, N - 1) ma = max(ma, dp1[k] + dp2[k + 1]);

  ans += ma;
  printf("%lld\n", ans);
}

Submission

Task問題 C - Coins
User nameユーザ名 ぬるぬる
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 1618 Byte
File nameファイル名
Exec time実行時間 59 ms
Memory usageメモリ使用量 7288 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
All 800 / 800 sample_01.txt,sample_02.txt,sample_03.txt,sample_01.txt,sample_02.txt,sample_03.txt,subtask_1_01.txt,subtask_1_02.txt,subtask_1_03.txt,subtask_1_04.txt,subtask_1_05.txt,subtask_1_06.txt,subtask_1_07.txt,subtask_1_08.txt,subtask_1_09.txt,subtask_1_10.txt,subtask_1_11.txt,subtask_1_12.txt,subtask_1_13.txt,subtask_1_14.txt,subtask_1_15.txt,subtask_1_16.txt,subtask_1_17.txt,subtask_1_18.txt,subtask_1_19.txt,subtask_1_20.txt,subtask_1_21.txt,subtask_1_22.txt,subtask_1_23.txt,subtask_1_24.txt,subtask_1_25.txt,subtask_1_26.txt,subtask_1_27.txt,subtask_1_28.txt,subtask_1_29.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 2 ms 2304 KB
sample_02.txt AC 2 ms 2304 KB
sample_03.txt AC 2 ms 2304 KB
subtask_1_01.txt AC 2 ms 2304 KB
subtask_1_02.txt AC 10 ms 3072 KB
subtask_1_03.txt AC 14 ms 3712 KB
subtask_1_04.txt AC 30 ms 4860 KB
subtask_1_05.txt AC 34 ms 5128 KB
subtask_1_06.txt AC 45 ms 5800 KB
subtask_1_07.txt AC 13 ms 3388 KB
subtask_1_08.txt AC 45 ms 5716 KB
subtask_1_09.txt AC 11 ms 3328 KB
subtask_1_10.txt AC 41 ms 5752 KB
subtask_1_11.txt AC 57 ms 7272 KB
subtask_1_12.txt AC 40 ms 7112 KB
subtask_1_13.txt AC 54 ms 7288 KB
subtask_1_14.txt AC 59 ms 6556 KB
subtask_1_15.txt AC 59 ms 6896 KB
subtask_1_16.txt AC 51 ms 6520 KB
subtask_1_17.txt AC 50 ms 6904 KB
subtask_1_18.txt AC 54 ms 6520 KB
subtask_1_19.txt AC 55 ms 6512 KB
subtask_1_20.txt AC 57 ms 6700 KB
subtask_1_21.txt AC 41 ms 6904 KB
subtask_1_22.txt AC 57 ms 7004 KB
subtask_1_23.txt AC 56 ms 6904 KB
subtask_1_24.txt AC 58 ms 6896 KB
subtask_1_25.txt AC 50 ms 6520 KB
subtask_1_26.txt AC 54 ms 7288 KB
subtask_1_27.txt AC 54 ms 6904 KB
subtask_1_28.txt AC 55 ms 6472 KB
subtask_1_29.txt AC 2 ms 2304 KB