Submission #23647

#TimeUsernameProblemLanguageResultExecution timeMemory
23647SYurySplit the sequence (APIO14_sequence)C++11
71 / 100
2000 ms86556 KiB
#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef long double ldb; typedef unsigned long long uli; #define X first #define Y second #define F(i, l, r) for(int i = l; i != r; i++) #define Df(i, l, r) for(int i = l; i != r; i--) #define I(i, a) for(auto i : a) #define pb push_back #define rs resize #define mk make_pair #define asg assign #define all(x) x.begin(),x.end() #define ret return #define cont continue #define brk break #define ins insert #define era erase #define fi0(x) memset(x, 0, sizeof(x)) #define finf(x) memset(x, 127, sizeof(x)) #define acpy(y, x) memcpy(y, x, sizeof(y)) #define y1 adjf #define tm dhgdg const int MAXN = 1e5 + 3; const int MAXK = 2e2 + 2; const ldb eps = 1e-16; int pr[MAXN][MAXK]; int a[MAXN]; int pref[MAXN]; lint sqp[MAXN]; int n, k; struct line{ lint b; int id; line(){} line(lint pb, int pid):b(pb),id(pid){} lint f(int x){ ret pref[id] * 1ll * x + b; } lint k(){ ret pref[id]; } }; struct convex_hull{ line l[MAXN]; int sz = 0; int ptr = 0; void add_line(line curr){ while(sz > 0 && l[sz - 1].k() == curr.k() && l[sz - 1].b < curr.b){sz--;} if(sz > 0 && l[sz - 1].k() == curr.k() && l[sz - 1].b >= curr.b){ ptr = min(ptr, sz - 1); ret; } while(sz >= 2){ line l1 = l[sz - 1], l2 = l[sz - 2]; //lint f1 = (l1.k - l2.k) * (l1.b - curr.b), f2 = (l2.b - l1.b) * (curr.k - l1.k); ldb f2 = (l2.b - l1.b)/((ldb)l1.k() - l2.k()), f1 = (l1.b - curr.b)/((ldb)curr.k() - l1.k()); if(f2 < f1 - eps)brk; sz--; } l[sz++] = curr; ptr = min(ptr, sz - 1); } pair<int, lint> get(int x, int cid){ if(sz == 0)ret mk(-1, 0); ptr = min(ptr, sz - 1); while(ptr < sz - 1 && l[ptr + 1].id < cid && l[ptr].f(x) <= l[ptr + 1].f(x))ptr++; if(l[ptr].id >= cid)ret mk(-1, 0); ret mk(l[ptr].id, l[ptr].f(x)); } void clear(){ sz = 0; ptr = 0; } }; convex_hull ch[2]; void restore(int i, int j){ while(i >= 0){ printf("%d ", i + 1); i = pr[i][j]; j--; } } lint dcp[MAXN]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); scanf("%d%d", &n, &k); F(i, 0, n)scanf("%d", &a[i]); F(i, 0, n)pref[i] = a[i] + ((i == 0) ? 0 : pref[i - 1]); k++; F(i, 0, n)sqp[i] = pref[i] * 1ll * pref[i]; F(i, 0, n) F(j, 1, k + 1) pr[i][j] = -2; F(i, 0, n)pr[i][1] = -1; F(i, 0, n)ch[0].add_line(line(-sqp[i], i)); int tc = 1; F(j, 2, k + 1){ ch[tc].clear(); F(i, j - 1, n){ pair<int, lint> tmp = ch[1 - tc].get(pref[i], i); if(tmp.X == -1){cont;} dcp[i] = tmp.Y; pr[i][j] = tmp.X; ch[tc].add_line(line(dcp[i] - sqp[i], i)); } tc = 1 - tc; } printf("%lld\n", dcp[n - 1]); restore(pr[n - 1][k], k - 1); ret 0; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:99:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:100:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  F(i, 0, n)scanf("%d", &a[i]);
                              ^
#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...