제출 #172794

#제출 시각아이디문제언어결과실행 시간메모리
172794RafaelSus수열 (APIO14_sequence)C++14
60 / 100
2041 ms125524 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; typedef long long ll; const ll inf=1e15; #define pb push_back const int INF=(0x3f3f3f3f); vector<ll>m,b,idx; int ptr; void add(ll _m,ll _b,ll _idx){ while(m.size()>=3){ if((b.back()-_b)*(_m-m[m.size()-2])>=(b[b.size()-2]-_b)*(_m-m.back())){ m.pop_back(); b.pop_back(); idx.pop_back(); } else break; } m.pb(_m); b.pb(_b); idx.pb(_idx); } ll func(int pos,ll x){ return m[pos]*x+b[pos]; } pair<ll,ll>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][305]; void print(int st,int k){ if(path[st][k]==0){ cout<<st<<' '; return; } print(path[st][k],k-1); cout<<st<<' '; } ll dp[2][N]; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n,k; cin>>n>>k; ll a[n+1],pref[n+1]={}; for(int i=1;i<=n;i++){ cin>>a[i]; pref[i]=pref[i-1]+a[i]; path[i][1]=0; } 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=1;j<n;j++){ if(j<i){ if(j==i-1){ add(-pref[j],dp[v][j],j); } continue; } pair<ll,ll>tmp=get(pref[n]-pref[j]); dp[v^1][j]=tmp.first+(pref[n]-pref[j])*pref[j]; path[j][i]=tmp.second; add(-pref[j],dp[v][j],j); } } 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'; print(st,k); }

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

sequence.cpp: In function 'std::pair<long long int, long long 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))ptr++;
         ~~~~~^~~~~~~~~
#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...