제출 #989718

#제출 시각아이디문제언어결과실행 시간메모리
989718kustizus수열 (APIO14_sequence)C++17
0 / 100
43 ms131072 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1e5; int n,k,idx=1,a[N+5],pre[N+5],bef1[N+5][205]; vector <int> bef(N+5),dp(N+5); int Cal(int i, int j){ return (pre[j]-pre[i-1])*(pre[n]-pre[j]); } void dnc(int l, int r, int optl, int optr){ if (l>r) return; int md=l+r>>1,ans=-1e18,pos=0; for (int i=min(optr,md);i>=optl;--i){ int d=bef[i-1]+Cal(i,md); if (d>ans){ ans=d; pos=i; } } if (pos==0) return; dp[md]=ans; bef1[md][idx]=pos; dnc(l,md-1,optl,pos); dnc(md+1,r,pos,optr); } void Solve(){ cin>>n>>k; for (int i=1;i<=n;++i){ cin>>a[i]; pre[i]=pre[i-1]+a[i]; } for (int i=1;i<=n;++i) bef[i]=Cal(1,i); for (int i=2;i<=k;++i){ ++idx; dnc(i,n,i,n); for (int j=1;j<=n;++j){ bef[j]=dp[j]; dp[j]=0; } } cout<<1<<"\n"; for (int i=1;i<=k;++i) cout<<1<<' '; return; int ans=-1e18,pos; for (int i=1;i<=n;++i) if (bef[i]>ans){ ans=bef[i]; pos=i; } cout<<ans<<"\n"; for (int i=k;i>=1;--i){ cout<<pos<<' '; pos=bef1[pos][i]-1; } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen ("FILE.INP","r",stdin); // freopen ("FILE.OUT","w",stdout); int t=1; // cin>>t; while (t--) Solve(); }

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

sequence.cpp: In function 'void dnc(long long int, long long int, long long int, long long int)':
sequence.cpp:12:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |     int md=l+r>>1,ans=-1e18,pos=0;
      |            ~^~
#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...