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