제출 #23641

#제출 시각아이디문제언어결과실행 시간메모리
23641SYury수열 (APIO14_sequence)C++11
39 / 100
266 ms131072 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){delete l.back(); l.pop_back();} if(!l.empty() && l.back()->k() == curr->k() && l.back()->b > curr->b){ ptr = min(ptr, (int)l.size() - 1); delete curr; 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; delete l.back(); l.pop_back(); } l.pb(curr); ptr = min(ptr, (int)l.size() - 1); } pair<int, lint> get(int x, int cid){ if(l.empty())ret mk(-1, 0); while(ptr < (int)l.size() - 1 && l[ptr + 1]->id < cid && l[ptr]->f(x) <= l[ptr + 1]->f(x))ptr++; ret mk(l[ptr]->id, l[ptr]->f(x)); } void clear(){ while(!l.empty()){ delete l.back(); l.pop_back(); vector<line*>().swap(l); } ptr = 0; } }; convex_hull ch[2]; void restore(int i, int j){ if(i < 0)ret; printf("%d ", i + 1); restore(pr[i][j], j - 1); } 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) F(j, 1, k + 1) pr[i][j] = -2; pr[0][1] = -1; F(i, 0, n)ch[0].add_line(new line(-pref[i] * 1ll * pref[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(new line(dcp[i] - pref[i] * 1ll * pref[i], i)); } tc = 1 - tc; } printf("%lld\n", dcp[n - 1]); restore(pr[n - 1][k], k - 1); ret 0; }

컴파일 시 표준 에러 (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...