Submission #5887898


Source Code Expand

#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 Info

Submission Time
Task C - Coins
User null_null
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1618 Byte
Status AC
Exec Time 59 ms
Memory 7288 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 35
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All 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
Case Name Status Exec Time Memory
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