Submission #5887922


Source Code Expand

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

Submission Time
Task C - Coins
User null_null
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1542 Byte
Status AC
Exec Time 145 ms
Memory 8052 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 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