제출 #172926

#제출 시각아이디문제언어결과실행 시간메모리
172926RafaelSus수열 (APIO14_sequence)C++14
71 / 100
2040 ms86128 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; typedef long long ll; const ll inf=1e15; #define pb push_back const int INF=(0x3f3f3f3f); vector<ll>m,b; vector<int>idx; int ptr; void add(ll _m,ll _b,int _idx){ int sz=m.size(); while(sz>=2&&(_b-b[b.size()-2])*(m[m.size()-2]-m.back())>=(b.back()-b[b.size()-2])*(m[m.size()-2]-_m)){ m.pop_back(); b.pop_back(); idx.pop_back(); sz--; } m.pb(_m); b.pb(_b); idx.pb(_idx); } ll func(int pos,ll x){ return m[pos]*x+b[pos]; } pair<ll,int>get(ll x){ if(ptr>=m.size())ptr=m.size()-1; while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x)){ ptr++; } return {func(ptr,x),idx[ptr]}; } int path[N][205]; void print(int st,int k){ if(path[st][k]==0){ //cout<<st<<' '; printf("%d ",st); return; } print(path[st][k],k-1); //cout<<st<<' '; printf("%d ",st); } ll dp[2][N]; ll a[N],pref[N]; int main(){ //ios::sync_with_stdio(false); //cin.tie(0);cout.tie(0); int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ //cin>>a[i]; scanf("%lld",a+i); pref[i]=pref[i-1]+a[i]; } for(int i=1;i<=n;i++){ dp[1][i]=pref[i]*(pref[n]-pref[i]); path[i][1]=0; } for(int i=2;i<=k;i++){ int v=(i-1)%2; m.clear(); b.clear(); idx.clear(); ptr=0; add(0,0,0); for(int j=i-1;j<n;j++){ if(j==i-1){ add(-pref[j],dp[v][j],j); continue; } pair<ll,int>tmp=get(pref[n]-pref[j]); dp[v^1][j]=tmp.first+pref[n]*pref[j]-pref[j]*pref[j]; path[j][i]=tmp.second; add(-pref[j],dp[v][j],j); } //cerr<<m.size()<<' '<<b.size()<<' '<<idx.size()<<'\n'; } ll mx=0,st=1; for(int i=1;i<n;i++){ if(dp[k%2][i]>=mx){ mx=dp[k%2][i]; st=i; } } //cout<<mx<<'\n'; printf("%lld\n",mx); print(st,k); }

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

sequence.cpp: In function 'std::pair<long long int, int> get(ll)':
sequence.cpp:32:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ptr>=m.size())ptr=m.size()-1;
      ~~~^~~~~~~~~~
sequence.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr+1<m.size()&&func(ptr,x)<=func(ptr+1,x)){
         ~~~~~^~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&k);
   ~~~~~^~~~~~~~~~~~~~
sequence.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",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...