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