제출 #907589

#제출 시각아이디문제언어결과실행 시간메모리
907589sofija6수열 (APIO14_sequence)C++14
33 / 100
102 ms17716 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 10010 #define MAXK 210 using namespace std; ll a[MAXN],dp[MAXN][2],prevv[MAXN][MAXK],pref[MAXN]; struct line { long double k,m; long double Calc(ll x) { return k*x+m; } long double Intersect(line l) { return (m-l.m)/(l.k-k); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n,k; cin >> n >> k; for (ll i=1;i<=n;i++) { cin >> a[i]; pref[i]=pref[i-1]+a[i]; } deque<pair<line,ll> > d; for (ll i=n-1;i>0;i--) { dp[i][0]=pref[i]*(pref[n]-pref[i]); line cur={pref[i],dp[i][0]}; while (d.size()>1 && cur.Intersect(d[0].first)>=d[0].first.Intersect(d[1].first)) d.pop_front(); d.push_front({cur,i}); prevv[i][1]=0; } for (ll j=2;j<=k;j++) { for (ll i=1;i<n;i++) { while (d.size()>1 && d[0].first.Calc(pref[i]-pref[n])<=d[1].first.Calc(pref[i]-pref[n]) && d[1].second<i) d.pop_front(); dp[i][1]=d.front().first.Calc(pref[i]-pref[n])+pref[i]*(pref[n]-pref[i]); prevv[i][j]=d.front().second; } d.clear(); for (ll i=n-1;i>0;i--) { dp[i][0]=dp[i][1]; dp[i][1]=0; line cur={pref[i],dp[i][0]}; while (d.size()>1 && cur.Intersect(d[0].first)>=d[0].first.Intersect(d[1].first)) d.pop_front(); d.push_front({cur,i}); } } ll maxx=-1,pos=0; for (ll i=1;i<n;i++) { if (dp[i][0]>=maxx) { maxx=dp[i][0]; pos=i; } } cout << maxx << "\n"; for (ll i=k;i>0;i--) { cout << pos << " "; pos=prevv[pos][i]; } return 0; } /** 7 3 4 1 3 4 0 2 3 **/

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

sequence.cpp: In function 'int main()':
sequence.cpp:33:25: warning: narrowing conversion of 'pref[i]' from 'long long int' to 'long double' [-Wnarrowing]
   33 |         line cur={pref[i],dp[i][0]};
      |                   ~~~~~~^
sequence.cpp:33:34: warning: narrowing conversion of 'dp[i][0]' from 'long long int' to 'long double' [-Wnarrowing]
   33 |         line cur={pref[i],dp[i][0]};
      |                           ~~~~~~~^
sequence.cpp:53:29: warning: narrowing conversion of 'pref[i]' from 'long long int' to 'long double' [-Wnarrowing]
   53 |             line cur={pref[i],dp[i][0]};
      |                       ~~~~~~^
sequence.cpp:53:38: warning: narrowing conversion of 'dp[i][0]' from 'long long int' to 'long double' [-Wnarrowing]
   53 |             line cur={pref[i],dp[i][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...