Submission #6438261
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <utility> #include <queue> #include <set> #include <map> #include <deque> #include <iomanip> #include <cstdio> #include <stack> #include <numeric> using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define PB push_back #define inf 1000000007 #define mod 1000000007 #define rep(i,n) for(int i=0;i<(int)(n);++i) int main(){ ll x,y,z; cin >> x >> y >> z; vector<pair<ll,pair<ll,ll> > > v; ll sm = 0; rep(i,x+y+z){ ll a,b,c; cin >> a >> b >> c; sm += c; a -= c; b -= c; v.push_back(MP(b-a,MP(a,b))); } sort(v.begin(),v.end()); vector<ll>a(x+y+z),b(x+y+z); // cerr << sm << endl; // cerr << endl; rep(i,x+y+z){ a[i] = v[i].second.first; b[i] = v[i].second.second; //cerr << a[i] << " " << b[i] << endl; } ll n = x+y+z; vector<ll>sa(n),sb(n+1); priority_queue<ll,vector<ll>,greater<ll> >pq,pq2; rep(i,n){ if(i<x){ if(i!=0)sa[i] = sa[i-1]+a[i]; else sa[i] = a[i]; pq.push(a[i]); }else{ sa[i] = sa[i-1]+a[i]; pq.push(a[i]); ll x = pq.top(); pq.pop(); sa[i]-=x; } } for(int i=n-1;i>=0;i--){ if(i>=n-y){ sb[i] = sb[i+1]+b[i]; pq2.push(b[i]); }else{ sb[i] = sb[i+1]+b[i]; pq2.push(b[i]); ll x = pq2.top(); pq2.pop(); sb[i]-=x; } } // cerr << endl; // rep(i,n)cerr << sa[i] << " "; // cerr << endl; // rep(i,n)cerr << sb[i] << " "; // cerr << endl; ll ans = 0; for(int i=x;i<n-y;i++){ ans = max(ans,sm+sa[i]+sb[i+1]); //cerr << ans <<endl; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Coins |
User | mtsd |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 1756 Byte |
Status | WA |
Exec Time | 353 ms |
Memory | 7792 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 7 ms | 888 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 | 60 ms | 1272 KB |
subtask_1_03.txt | AC | 107 ms | 2040 KB |
subtask_1_04.txt | AC | 184 ms | 3572 KB |
subtask_1_05.txt | AC | 212 ms | 3956 KB |
subtask_1_06.txt | AC | 274 ms | 5488 KB |
subtask_1_07.txt | AC | 67 ms | 1784 KB |
subtask_1_08.txt | AC | 243 ms | 6384 KB |
subtask_1_09.txt | AC | 60 ms | 1656 KB |
subtask_1_10.txt | AC | 216 ms | 5104 KB |
subtask_1_11.txt | AC | 352 ms | 7408 KB |
subtask_1_12.txt | AC | 340 ms | 7024 KB |
subtask_1_13.txt | AC | 349 ms | 7792 KB |
subtask_1_14.txt | AC | 353 ms | 6896 KB |
subtask_1_15.txt | AC | 353 ms | 6768 KB |
subtask_1_16.txt | AC | 289 ms | 7664 KB |
subtask_1_17.txt | AC | 286 ms | 6640 KB |
subtask_1_18.txt | AC | 291 ms | 6128 KB |
subtask_1_19.txt | AC | 291 ms | 6640 KB |
subtask_1_20.txt | AC | 351 ms | 6896 KB |
subtask_1_21.txt | AC | 346 ms | 6512 KB |
subtask_1_22.txt | AC | 350 ms | 7024 KB |
subtask_1_23.txt | AC | 350 ms | 6768 KB |
subtask_1_24.txt | AC | 353 ms | 7152 KB |
subtask_1_25.txt | AC | 288 ms | 7536 KB |
subtask_1_26.txt | WA | 291 ms | 7536 KB |
subtask_1_27.txt | AC | 291 ms | 6512 KB |
subtask_1_28.txt | AC | 291 ms | 7152 KB |
subtask_1_29.txt | AC | 1 ms | 256 KB |