제출 #444764

#제출 시각아이디문제언어결과실행 시간메모리
444764impri수열 (APIO14_sequence)C++14
0 / 100
1288 ms89676 KiB
#include<bits/stdc++.h> using namespace std; int n,k; int arr[100001]; long long psum[100001]; long long dp[100001][2]; int res[100001][202]; struct line{ long long a,b; double s; int p; }; int main(void){ cin.tie(0); ios_base::sync_with_stdio(false); cin >> n >> k; k++; for(int i=1;i<=n;i++) cin >> arr[i]; for(int i=1;i<=n;i++) psum[i]=psum[i-1]+arr[i]; for(int i=1;i<n;i++) dp[i][1]=psum[i]*(psum[n]-psum[i]); for(int i=2;i<=k;i++){ vector<line>lines; lines.push_back({-psum[i-1],dp[i-1][(i+1)%2],10e12,i-1}); int cur=0; for(int j=i;j<=n;j++){ while(1){ if(cur+1==lines.size())break; if(lines[cur+1].s<(psum[n]-psum[j]))break; cur++; } dp[j][i%2]=lines[cur].a*(psum[n]-psum[j])+lines[cur].b+psum[j]*psum[n]-psum[j]*psum[j]; res[j][i]=lines[cur].p; line nxt; nxt.a=-psum[j]; nxt.b=dp[j][(i+1)%2]; nxt.p=j; bool ok=true; while(!lines.empty()){ if(lines.back().a==nxt.a){ if(lines.back().b>nxt.b){ ok=false;break;} else{ lines.pop_back(); if(cur==lines.size())cur--; } } else{ double point=1.0*(lines.back().b-nxt.b)/(nxt.a-lines.back().a); if(point>lines.back().s) { lines.pop_back(); if(cur==lines.size()) cur--; } else{ nxt.s=point; break; } } } if(ok) lines.push_back(nxt); } } cout << dp[n][k%2] <<'\n'; int cur=n; vector<int>r; for(int i=k;i>1;i--){ r.push_back(res[cur][i]); cur=res[cur][i]; } for(int i=k-2;i>=0;i--) cout << r[i] << ' '; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             if(cur+1==lines.size())break;
      |                ~~~~~^~~~~~~~~~~~~~
sequence.cpp:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                   if(cur==lines.size())cur--;
      |                      ~~~^~~~~~~~~~~~~~
sequence.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 if(cur==lines.size())
      |                    ~~~^~~~~~~~~~~~~~
#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...