Submission #8407207
Source Code Expand
#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <set> #include <queue> #include <deque> #include <map> #include <stack> #include<bitset> #include<list> #include<cassert> #include<numeric> using namespace std; const long long N = 1e5 + 5; pair<long long, long long> coins[N]; long long dp[N]; long long n; long long pd[N]; long long x, y, z; long long ans; long long javab = 0; bool cmp(pair<long long, long long> p1, pair<long long, long long> p2) { long long v1 = p1.first - p1.second; long long v2 = p2.first - p2.second; return v1 < v2; } void calc() { multiset<long long> s; for (long long i = 0; i < y; i++) { s.insert(coins[i].second); dp[y - 1] += coins[i].second; } for (long long i = y; i < n; i++) { long long tmp = coins[i].second; dp[i] = dp[i - 1]; if (*s.begin() < tmp) { dp[i] = dp[i - 1] + tmp - *s.begin(); s.erase(s.begin()); s.insert(tmp); } } reverse(coins, coins + n); s.clear(); for (long long i = 0; i < x; i++) { s.insert(coins[i].first); pd[x - 1] += coins[i].first; } for (long long i = x; i < n; i++) { pd[i] = pd[i - 1]; long long tmp = coins[i].first; if (*s.begin() < tmp) { pd[i] = pd[i - 1] + tmp - *s.begin(); s.erase(s.begin()); s.insert(tmp); } } reverse(coins, coins + n); reverse(pd, pd + n); } int main() { cin >> x >> y >> z; n = x + y + z; for (long long i = 0; i < x + y + z; i++) { long long a, b, c; cin >> a >> b >> c; coins[i] = {a - c, b - c}; ans += c; } sort(coins, coins + n, cmp); calc(); /* for (long long i = 0; i < n; i++) { cout << coins[i].first << " " << coins[i].second << endl; } cout << endl; for (long long i = 0; i < n; i++) { cout << pd[i] << " "; } cout << endl; */ for (long long i = y - 1; i < n - x; i++) { javab = max(javab, ans + dp[i] + pd[i + 1]); } cout << javab; }
Submission Info
Submission Time | |
---|---|
Task | C - Coins |
User | Aryanv |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1994 Byte |
Status | AC |
Exec Time | 164 ms |
Memory | 7424 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 | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask_1_01.txt | AC | 1 ms | 256 KB |
subtask_1_02.txt | AC | 24 ms | 1024 KB |
subtask_1_03.txt | AC | 41 ms | 1536 KB |
subtask_1_04.txt | AC | 77 ms | 3200 KB |
subtask_1_05.txt | AC | 88 ms | 2944 KB |
subtask_1_06.txt | AC | 121 ms | 3712 KB |
subtask_1_07.txt | AC | 26 ms | 1408 KB |
subtask_1_08.txt | AC | 100 ms | 3712 KB |
subtask_1_09.txt | AC | 26 ms | 1408 KB |
subtask_1_10.txt | AC | 107 ms | 3840 KB |
subtask_1_11.txt | AC | 162 ms | 6528 KB |
subtask_1_12.txt | AC | 137 ms | 5760 KB |
subtask_1_13.txt | AC | 155 ms | 7424 KB |
subtask_1_14.txt | AC | 148 ms | 4480 KB |
subtask_1_15.txt | AC | 156 ms | 4736 KB |
subtask_1_16.txt | AC | 114 ms | 6144 KB |
subtask_1_17.txt | AC | 111 ms | 5632 KB |
subtask_1_18.txt | AC | 119 ms | 4224 KB |
subtask_1_19.txt | AC | 135 ms | 4736 KB |
subtask_1_20.txt | AC | 164 ms | 5632 KB |
subtask_1_21.txt | AC | 130 ms | 5120 KB |
subtask_1_22.txt | AC | 164 ms | 5376 KB |
subtask_1_23.txt | AC | 161 ms | 6272 KB |
subtask_1_24.txt | AC | 156 ms | 4736 KB |
subtask_1_25.txt | AC | 116 ms | 7040 KB |
subtask_1_26.txt | AC | 122 ms | 6528 KB |
subtask_1_27.txt | AC | 125 ms | 4992 KB |
subtask_1_28.txt | AC | 135 ms | 4864 KB |
subtask_1_29.txt | AC | 1 ms | 256 KB |