Submission #1865598
Source Code Expand
#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<unordered_map> #include<array> #include<map> #include<bitset> #include<iomanip> using namespace std; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase //ios::sync_with_stdio(false); //std::cin.tie(0); //<< setprecision(20) const int mod=201712111; const llint big=1e15+100; const long double pai=3.141592653589793238462643383279502884197; const long double ena=2.71828182845904523536; const long double eps=1e-7; template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}} template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}} template <class T> void soun(T& ar) {sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());} llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);} llint lcm(llint a,llint b){return a/gcd(a,b)*b;} int main(void){ int n,m,i,j;cin>>n>>m; vector<llint>a(n); vector<llint>wa(n+1); for(i=0;i<n;i++){cin>>a[i];wa[i+1]=wa[i]+a[i];} vector<set<pair<llint,llint>>>pot(m+1); //その時のwa,kei pot[0].ins(mp(0,0)); for(j=0;j<=m;j++){ pot[j].ins(mp(-big,big/2)); pot[j].ins(mp(big,big/2)); } for(i=1;i<=n;i++){ for(j=m;j>0;j--){ auto itr=pot[j-1].lower_bound(mp(wa[i],big)); llint now=abs(itr->fir-wa[i])+itr->sec; mineq(now,abs(prev(itr)->fir-wa[i])+prev(itr)->sec); if(i==n&&j==m){cout<<now<<endl;return 0;} auto it=pot[j].lower_bound(mp(wa[i],big)); //prev(it),これ,it if(wa[i]-prev(it)->fir+prev(it)->sec<=now){continue;} if(it->fir-wa[i]+it->sec<=now){continue;} it=pot[j].ins(mp(wa[i],now)).fir; while(next(it)->sec>=now+next(it)->fir-wa[i]){pot[j].era(next(it));} while(prev(it)->sec>=now+wa[i]-prev(it)->fir){pot[j].era(prev(it));} } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - 天下一合体 |
User | WA_TLE |
Language | C++14 (GCC 5.4.1) |
Score | 900 |
Code Size | 2242 Byte |
Status | AC |
Exec Time | 146 ms |
Memory | 1024 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2 |
All | example0, example1, example2, fix0, fix1, fix2, lis0, lis1, maxrand0, maxrand1, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4, smallrand5, smallrand6, smallrand7, smallrand8, smallrand9, zero0, zero1, zero2, zero3, zero4, zeromed0, zeromed1, zeromed2, zeromed3, zeromed4, zeroone0 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
example0 | AC | 1 ms | 256 KB |
example1 | AC | 1 ms | 256 KB |
example2 | AC | 1 ms | 256 KB |
fix0 | AC | 128 ms | 1024 KB |
fix1 | AC | 106 ms | 896 KB |
fix2 | AC | 115 ms | 1024 KB |
lis0 | AC | 130 ms | 640 KB |
lis1 | AC | 128 ms | 640 KB |
maxrand0 | AC | 146 ms | 1024 KB |
maxrand1 | AC | 80 ms | 896 KB |
smallrand0 | AC | 1 ms | 256 KB |
smallrand1 | AC | 1 ms | 256 KB |
smallrand2 | AC | 1 ms | 256 KB |
smallrand3 | AC | 1 ms | 256 KB |
smallrand4 | AC | 1 ms | 256 KB |
smallrand5 | AC | 1 ms | 256 KB |
smallrand6 | AC | 1 ms | 256 KB |
smallrand7 | AC | 1 ms | 256 KB |
smallrand8 | AC | 1 ms | 256 KB |
smallrand9 | AC | 1 ms | 256 KB |
zero0 | AC | 144 ms | 896 KB |
zero1 | AC | 144 ms | 896 KB |
zero2 | AC | 109 ms | 896 KB |
zero3 | AC | 128 ms | 896 KB |
zero4 | AC | 144 ms | 1024 KB |
zeromed0 | AC | 2 ms | 256 KB |
zeromed1 | AC | 2 ms | 256 KB |
zeromed2 | AC | 2 ms | 256 KB |
zeromed3 | AC | 3 ms | 256 KB |
zeromed4 | AC | 3 ms | 256 KB |
zeroone0 | AC | 2 ms | 256 KB |