제출 #23652

#제출 시각아이디문제언어결과실행 시간메모리
23652SYury수열 (APIO14_sequence)C++11
71 / 100
2000 ms87340 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 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(auto i = l; i != r; i++) #define Df(i, l, r) for(auto 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; lint lk[2][MAXN]; lint lb[2][MAXN]; int lid[2][MAXN]; int sz[2]; int ptr[2]; lint KEK; lint f(int ch, int i, int x){ ret lk[ch][i] * x + lb[ch][i]; } void add_line(int ch, lint ck, lint cb, int cid){ while(sz[ch] > 0 && lk[ch][sz[ch] - 1] == ck && lb[ch][sz[ch] - 1] < cb){sz[ch]--;} if(sz[ch] > 0 && lk[ch][sz[ch] - 1] == ck && lb[ch][sz[ch] - 1] >= cb){ ptr[ch] = min(ptr[ch], sz[ch] - 1); ret; } while(sz[ch] >= 2){ int p1 = sz[ch] - 1, p2 = sz[ch] - 2; ldb f2 = (lb[ch][p2] - lb[ch][p1])/((ldb)lk[ch][p1] - lk[ch][p2]), f1 = (lb[ch][p1] - cb)/((ldb)ck - lk[ch][p1]); if(f2 < f1 - eps)brk; sz[ch]--; } lk[ch][sz[ch]] = ck; lb[ch][sz[ch]] = cb; lid[ch][sz[ch]] = cid; sz[ch]++; ptr[ch] = min(ptr[ch], sz[ch] - 1); } int get(int ch, int x, int cid){ if(sz[ch] == 0)ret -1; ptr[ch] = min(ptr[ch], sz[ch] - 1); while(ptr[ch] < sz[ch] - 1 && lid[ch][ptr[ch] + 1] < cid && f(ch, ptr[ch], x) <= f(ch, ptr[ch] + 1, x))ptr[ch]++; if(lid[ch][ptr[ch]] >= cid)ret -1; KEK = f(ch, ptr[ch], x); ret lid[ch][ptr[ch]]; } void ch_clear(int ch){ sz[ch] = 0; ptr[ch] = 0; } 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)add_line(0, pref[i], -sqp[i], i); int tc = 1; F(j, 2, k + 1){ ch_clear(tc); F(i, j - 1, n){ int tmp = get(1 - tc, pref[i], i); if(tmp == -1){cont;} dcp[i] = KEK; pr[i][j] = tmp; add_line(tc, pref[i], dcp[i] - sqp[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:97: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:98: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...