Submission #23639

#TimeUsernameProblemLanguageResultExecution timeMemory
23639SYurySplit the sequence (APIO14_sequence)C++11
0 / 100
16 ms81876 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]; int n, k; struct line{ lint b; int id; 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{ vector<line> l; int ptr = 0; void add_line(line curr){ while(!l.empty() && l.back().k() == curr.k() && l.back().b <= curr.b)l.pop_back(); if(!l.empty() && l.back().k() == curr.k() && l.back().b > curr.b){ ptr = min(ptr, (int)l.size() - 1); ret; } while(l.size() >= 2){ line l1 = l[(int)l.size() - 1], l2 = l[(int)l.size() - 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; l.pop_back(); } l.pb(curr); ptr = min(ptr, (int)l.size() - 1); } pair<int, lint> get(int x){ if(l.empty())ret mk(-1, 0); while(ptr < (int)l.size() - 1 && l[ptr].f(x) <= l[ptr + 1].f(x))ptr++; ret mk(l[ptr].id, l[ptr].f(x)); } }; convex_hull ch[MAXK]; void restore(int i, int j){ if(i < 0)ret; printf("%d ", i + 1); restore(pr[i][j], j - 1); } lint dcp[MAXK]; 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) F(j, 1, k + 1) pr[i][j] = -2; pr[0][1] = -1; ch[1].add_line(line(-pref[0] * 1ll * pref[0], 0)); F(i, 1, n){ dcp[0] = 0; pr[i][1] = -1; F(j, 2, k + 1){ pair<int, lint> tmp = ch[j - 1].get(pref[i]); int pi = tmp.X; if(pi == -1)cont; pr[i][j] = pi; dcp[j] = tmp.Y; if(j > 2 && pr[i][j] != -2 && pr[i][j - 1] != -2 && pr[i][j] != pr[i][j - 1])ret 0; } F(j, 1, k + 1)if(pr[i][j] != -2)ch[j].add_line(line(dcp[j] - pref[i] * 1ll * pref[i], i)); } printf("%lld\n", dcp[k]); restore(pr[n - 1][k], k - 1); ret 0; }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:89: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:90: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...