AtCoder Grand Contest 018

Submission #5887922

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;

int X, Y, Z, N;
int A[101010], B[101010], C[101010];
int a[101010], b[101010];
int dp1[101010], dp2[101010];

void calc1() {
  for (int i = 0; i < N; i++) dp1[i] = -INF;
  priority_queue<int> q;

  int sum = 0;
  for (int i = 0; i < N; i++) {
    q.push(-b[i]);
    sum += b[i];
    if (q.size() > Y) {
      int tmp = -q.top();
      sum -= tmp;
      q.pop();
    }

    if (q.size() == Y) dp1[i] = sum;
  }
}

void calc2() {
  for (int i = 0; i < N; i++) dp2[i] = -INF;
  priority_queue<int> q;

  int sum = 0;
  for (int i = N - 1; i >= 0; i--) {
    q.push(-a[i]);
    sum += a[i];
    if (q.size() > X) {
      int tmp = -q.top();
      sum -= tmp;
      q.pop();
    }

    if (q.size() == X) dp2[i] = sum;
  }
}

signed main() {
  cin >> X >> Y >> Z;
  N = X + Y + Z;

  for (int i = 0; i < N; i++) cin >> A[i] >> B[i] >> C[i];

  int ans = 0;
  for (int i = 0; i < N; i++) {
    ans += C[i];
    A[i] -= C[i];
    B[i] -= C[i];
  }

  vector<int> v;
  for (int i = 0; i < N; i++) v.push_back(i);

  sort(v.begin(), v.end(), [&](int x, int y) {
    return A[x] - B[x] < A[y] - B[y];
  });

  for (int i = 0; i < N; i++) {
    int idx = v[i];
    a[i] = A[idx];
    b[i] = B[idx];
  }

  calc1();
  calc2();

  int mx = -INF;
  for (int i = 0; i < N - 1; i++) {
    mx = max(mx, dp1[i] + dp2[i + 1]);
  }

  ans += mx;

  cout << ans << endl;
  return 0;
}

Submission

Task問題 C - Coins
User nameユーザ名 ぬるぬる
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 1542 Byte
File nameファイル名
Exec time実行時間 145 ms
Memory usageメモリ使用量 8052 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 25 ms 3068 KB
subtask_1_03.txt AC 41 ms 3708 KB
subtask_1_04.txt AC 74 ms 5112 KB
subtask_1_05.txt AC 86 ms 5368 KB
subtask_1_06.txt AC 112 ms 6132 KB
subtask_1_07.txt AC 28 ms 3508 KB
subtask_1_08.txt AC 101 ms 6260 KB
subtask_1_09.txt AC 25 ms 3324 KB
subtask_1_10.txt AC 91 ms 6004 KB
subtask_1_11.txt AC 145 ms 8052 KB
subtask_1_12.txt AC 128 ms 7488 KB
subtask_1_13.txt AC 141 ms 8052 KB
subtask_1_14.txt AC 144 ms 7028 KB
subtask_1_15.txt AC 145 ms 7276 KB
subtask_1_16.txt AC 119 ms 7284 KB
subtask_1_17.txt AC 118 ms 7412 KB
subtask_1_18.txt AC 121 ms 6900 KB
subtask_1_19.txt AC 123 ms 6888 KB
subtask_1_20.txt AC 144 ms 7076 KB
subtask_1_21.txt AC 128 ms 7412 KB
subtask_1_22.txt AC 144 ms 7380 KB
subtask_1_23.txt AC 142 ms 7540 KB
subtask_1_24.txt AC 145 ms 7276 KB
subtask_1_25.txt AC 117 ms 7284 KB
subtask_1_26.txt AC 121 ms 8052 KB
subtask_1_27.txt AC 122 ms 7284 KB
subtask_1_28.txt AC 123 ms 6848 KB
subtask_1_29.txt AC 2 ms 2304 KB