제출 #392523

#제출 시각아이디문제언어결과실행 시간메모리
392523giorgikob수열 (APIO14_sequence)C++14
71 / 100
335 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 = 2e5+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){ return k[i]*x + b[i]; } /*bool check1(int x,int y,int i){ assert(x > 0); ll a = pre[n]-pre[i]; //k[x]*a+b[x] <= k[y]*a+b[y] //a*(k[y]-k[x]) >= b[x] - b[y]; return a*(k[y]-k[x]) >= b[x] - b[y]; 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 assert(x > 0); if(k[y] == k[i]) return (b[i] >= b[y]); //assert(k[y] != k[x]); if(k[y] == k[x]) return 1; assert(k[i] != k[x]); return (b[x]-b[i])*(k[y]-k[x]) >= (b[x]-b[y])*(k[i]-k[x]); }*/ bool check1(int x, int y, int i) { return (dp[0][y] - dp[0][x] >= (pre[y] - pre[x]) * (pre[n] - pre[i])); } bool check2(int x, int y, int i) { return ((dp[0][y] - dp[0][x]) * (pre[i] - pre[y]) <= (dp[0][i] - dp[0][y]) * (pre[y] - pre[x])); } inline void test_case(){ cin >> n >> cnt; assert(n <= 1e5 && cnt <= 200); 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; i++){ while(r-l > 1 && check1(q[l],q[l+1],i))l++; int x = q[l]; assert(x<i); where[j][i] = x; dp[1][i] = dp[0][x] + (pre[n]-pre[i])*(pre[i]-pre[x]); assert(r < N); k[r] = -pre[i]; b[r] = dp[0][i]; while(r-l > 1 && check2(q[r-2],q[r-1],i))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], dp[1][i] = 0;//, 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]; assert(ind < N); cout << ind << " "; if(ind == 0){ cout << a << endl; } assert(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:86:9: warning: unused variable 'mx' [-Wunused-variable]
   86 |     int mx = -1;
      |         ^~
sequence.cpp: At global scope:
sequence.cpp:108:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  108 |  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...