제출 #697880

#제출 시각아이디문제언어결과실행 시간메모리
697880fdnfksd수열 (APIO14_sequence)C++14
49 / 100
90 ms131072 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=long long; const ll maxN=1e5+10; const ll inf=1e18; const ll mod=1e9+7; ll n,k,a[maxN],sum=0,pre[maxN],pre2[maxN],dp[maxN][205]; ll cost(ll l,ll r) { return (pre[r]-pre[l-1])*(pre[r]-pre[l-1])-(pre2[r]-pre2[l-1]); } ll trace[maxN][205]={0}; void dnc(ll l,ll r,ll optl, ll optr,ll id) { if(l>r) return; ll mid=l+r>>1; ll opt=0,ans=inf; for(int i=optl;i<=min(optr,mid);i++) { if(dp[i-1][id-1]+cost(i,mid)<ans) { ans=dp[i-1][id-1]+cost(i,mid); opt=i; } } dp[mid][id]=ans; trace[mid][id]=opt-1; dnc(l,mid-1,optl,opt,id); dnc(mid+1,r,opt,optr,id); } void solve() { cin >> n >> k; k++; ll ss=0; for(int i=1;i<=n;i++) cin >> a[i],ss+=sum*a[i],sum+=a[i]; for(int i=1;i<=n;i++) { pre[i]=pre[i-1]+a[i]; pre2[i]=pre2[i-1]+a[i]*a[i]; } for(int i=1;i<=n;i++) { dp[i][1]=pre[i]*pre[i]-pre2[i]; } dp[0][1]=inf; for(int j=2;j<=k;j++) { dnc(1,n,1,n,j); } cout <<ss-dp[n][k]/2<<'\n'; ll x=n; for(int i=k;i>1;i--) { cout << trace[x][i]<<' '; x=trace[x][i]; } } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

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

sequence.cpp: In function 'void dnc(ll, ll, ll, ll, ll)':
sequence.cpp:20:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |     ll mid=l+r>>1;
      |            ~^~
#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...