제출 #392488

#제출 시각아이디문제언어결과실행 시간메모리
392488giorgikob수열 (APIO14_sequence)C++14
50 / 100
337 ms131076 KiB
#include<bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; const int N = 1e5+5, mod = 1e9+7, sq = 500; int n,cnt; ll k[N],A[N],b[N],pre[N],q[N]; ll dp[2][N], where[205][N]; int l,r; ll get(int x,ll i){ //cout << k[i] << " " << b[i] << endl; return k[i]*x + b[i]; } bool check1(int x,int y,ll i){ //cout << "----" << endl; //cout << x << " " << y << endl; return get(pre[n]-pre[i],x) <= get(pre[n]-pre[i],y); } bool check2(int x,int y,ll i){ //xi = (b[x]-b[i])/(k[i]-k[x]) //xy = (b[x]-b[y])/(k[y]-k[x]) //xi >= xy if(k[y] == k[i]) return (b[i] >= b[y]); if(k[y] == k[x]){ //cout << k[i] << " " << k[x] << " " << k[y] << endl; //cout << i << " " << x << endl; } assert(k[i] != k[x]);// && k[y] != k[x]); return (b[x]-b[i])*(k[y]-k[x]) >= (b[x]-b[y])*(k[i]-k[x]); } inline void test_case(){ cin >> n >> cnt; for(int i = 1; i <= n; i++){ cin >> A[i]; pre[i] = pre[i-1] + A[i]; } pre[n+1] = pre[n]; //cout << pre[1] << endl; for(int j = 1; j <= cnt+1; j++){ q[1] = 0; l = 1, r = 2; k[1] = 0, b[1] = 0; for(int i = 1; i <= n+1; i++){ while(r-l > 1 && check1(l,l+1,i))l++; int x = q[l]; assert(x<i);//cout << x << " "; where[j][i] = x; dp[1][i] = dp[0][x] + (pre[n]-pre[i])*(pre[i]-pre[x]); k[r] = -pre[i]; b[r] = dp[0][i]; while(r-l > 1 && check2(r-2,r-1,r))r--; q[r] = i; k[r] = -pre[i]; b[r] = dp[0][i]; r++; } //cout << endl; for(int i = 1; i <= n; i++) dp[0][i] = dp[1][i];// cout << dp[0][i] << " "; //cout << endl; } int ind = 0; int mx = -1; /*for(int i = 1; i <= n; i++){ if(dp[0][i] > mx){ mx = dp[0][i]; ind = i; } }*/ ind = n; cout << dp[0][ind] << endl; int a = cnt+1; while(a>1){ ind = where[a][ind]; cout << ind << " "; a--; } } main(){ ios::sync_with_stdio(0); int T = 1; //cin >> T; while(T--){ test_case(); } }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'void test_case()':
sequence.cpp:75:9: warning: unused variable 'mx' [-Wunused-variable]
   75 |     int mx = -1;
      |         ^~
sequence.cpp: At global scope:
sequence.cpp:92:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 |  main(){
      |       ^
#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...