제출 #717815

#제출 시각아이디문제언어결과실행 시간메모리
717815Urvuk3수열 (APIO14_sequence)C++17
0 / 100
83 ms32816 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int INF=1e9,MOD=1e9+7; const ll LINF=1e18; #define fi first #define se second #define pii pair<int,int> #define pll pair<ll,ll> #define mid ((l+r)/2) #define sz(a) (int((a).size())) #define all(a) a.begin(),a.end() #define endl "\n" #define pb push_back struct Line{ ll k,m,l,r,id; ll operator ()(ll x){ return k*x+m; } }; void PRINT(int x) {cerr << x;} void PRINT(ll x) {cerr << x;} void PRINT(double x) {cerr << x;} void PRINT(char x) {cerr << '\'' << x << '\'';} void PRINT(string x) {cerr << '\"' << x << '\"';} void PRINT(bool x) {cerr << (x ? "true" : "false");} void PRINT(Line f){ cerr<<f.k<<"x+"<<f.m<<" ["<<f.l<<","<<f.r<<"]"; } template<typename T,typename V> void PRINT(pair<T,V>& x){ cerr<<"{"; PRINT(x.fi); cerr<<","; PRINT(x.se); cerr<<"}"; } template<typename T> void PRINT(T &x){ int id=0; cerr<<"{"; for(auto _i:x){ cerr<<(id++ ? "," : ""); PRINT(_i); } cerr<<"}"; } void _PRINT(){ cerr<<"]\n"; } template<typename Head,typename... Tail> void _PRINT(Head h,Tail... t){ PRINT(h); if(sizeof...(t)) cerr<<", "; _PRINT(t...); } #define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x) ll Intersect(Line l1,Line l2){ ll ret=(l2.m-l1.m)/(l1.k-l2.k); return (ret>=0 ? ret : ret-1); } deque<Line> Hull; void AddLine(Line f){ if(!Hull.empty() && Hull[0].k==f.k){ if(Hull[0].m<f.k) Hull.pop_front(); else return; } if(sz(Hull)==0){ f.l=-LINF,f.r=LINF; Hull.push_front(f); } else if(sz(Hull)==1){ ll sec=Intersect(f,Hull[0]); f.l=-LINF,f.r=sec; Hull[0].l=sec+1; Hull.push_front(f); } else{ while(Hull[0].r<=Intersect(f,Hull[0])){ Hull.pop_front(); Hull[0].l=-LINF; } ll sec=Intersect(f,Hull[0]); f.l=-LINF,f.r=sec; Hull[0].l=sec+1; Hull.push_front(f); } } void Solve(){ int N,K; cin>>N>>K; vector<int> a(N+1); for(int i=1;i<=N;i++) cin>>a[i]; vector<int> p(N+1,0); for(int i=1;i<=N;i++) p[i]=p[i-1]+a[i]; vector<vector<pll>> dp(K+1,vector<pll>(N+1,{0,-1})); AddLine({0,0,0,0,-1}); for(int j=1;j<=K;j++){ int it=sz(Hull)-1; //Debug(j,it); for(int i=1;i<=N-1;i++){ ll x=p[N]-p[i]; while(!(Hull[it].l<=x && x<=Hull[it].r)){ it--; } //Debug(i,x,it); ll dp_new=Hull[it](p[N]-p[i])+p[i]*(p[N]-p[i]); if(dp[j][i].fi<dp_new){ dp[j][i].fi=dp_new; dp[j][i].se=Hull[it].id; } } //Debug(dp[j]); Hull.clear(); for(int i=1;i<=N-1;i++){ Line f={-p[i],dp[j][i].fi,0,0,i}; //Debug(f); AddLine(f); } //Debug(Hull); } ll res=0; int idx; int c=K; for(int i=1;i<=N-1;i++){ if(res<dp[K][i].fi){ idx=i; res=dp[K][i].fi; } } cout<<res<<endl; for(;idx!=-1;idx=dp[c][idx].se,c--){ cout<<idx<<" "; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; t=1; //cin>>t; while(t--){ Solve(); } return 0; } /* 7 3 4 1 3 4 0 2 3 */

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

sequence.cpp: In function 'void Solve()':
sequence.cpp:141:31: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  141 |     for(;idx!=-1;idx=dp[c][idx].se,c--){
      |                               ^
#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...