Submission #45730

#TimeUsernameProblemLanguageResultExecution timeMemory
45730JohnTitorSplit the sequence (APIO14_sequence)C++11
71 / 100
2060 ms83132 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define setbit(s, i) (s|=(1LL<<(i))) #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll typedef long long ll; typedef long double ld; template <typename T> inline void read(T &x){ cin>>x; // scanf("%lld", &x); // char c; // bool nega=0; // while((!isdigit(c=getchar()))&&(c!='-')); // if(c=='-'){ // nega=1; // c=getchar(); // } // x=c-48; // while(isdigit(c=getchar())) x=x*10+c-48; // if(nega) x=-x; } template <typename T> inline void writep(T x){ if(x>9) writep(x/10); putchar(x%10+48); } template <typename T> inline void write(T x){ if(x<0){ putchar('-'); x=-x; } writep(x); } template <typename T> inline void writeln(T x){ write(x); putchar('\n'); } #define taskname "sequence" #define sqr(x) ((x)*(x)) int n, k; int s[100001]; ll sqs[100001]; ll f[100001]; int trace[100001][201]; vector <int> q; const ll inf=mask(60); void track(int nn, int k){ if(nn==0) return; track(trace[nn][k], k-1); if(nn==n) return; write(nn); putchar(' '); } int first[100001]; ll b[100001]; ll first_better(int i, int j){ if(b[j]<=b[i]) return 0; if(s[i]==s[j]) return inf; return (b[j]-b[i]-1)/(s[i]-s[j])+1; } int main(){ #ifdef Kanikou if(fopen(taskname".inp", "r")) freopen(taskname".inp", "r", stdin); #endif // Kanikou ios_base::sync_with_stdio(false); cin.tie(NULL); read(n); read(k); FOR(i, 1, n) read(s[i]); FOR(i, 1, n) s[i]+=s[i-1]; FOR(i, 1, n) sqs[i]=((ll)s[i])*s[i]; ll a; FOR(j, 1, k){ int p=0; q.clear(); q.pb(0); FOR(i, 1, n){ b[i]=f[i]-sqs[i]; p=min(p, ((int)q.size())-1); while((p+1<q.size())&&(first[q[p+1]]<=s[i])) p++; f[i]=((ll)s[i])*s[q[p]]+b[q[p]]; trace[i][j]=q[p]; while(true){ a=first_better(i, q.back()); if(a>=s[n]) break; if(a<=first[q.back()]){ q.pop_back(); if(q.empty()){ first[i]=0; q.pb(i); break; } } else{ first[i]=a; q.pb(i); break; } } } } writeln(f[n]); track(n, k); }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:87:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while((p+1<q.size())&&(first[q[p+1]]<=s[i])) p++;
                    ~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...