제출 #908241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
908241		sofija6	수열 (APIO14_sequence)	C++14	54 / 100	107 ms	17708 KiB

sequence

#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=1;i<n;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});
    }
    for (ll j=2;j<=k;j++)
    {
        for (ll i=n-1;i>=j;i--)
        {
            while (!d.empty() && d[0].second>i)
                d.pop_front();
            while (d.size()>1 && d[0].first.Calc(pref[n]-pref[i])<=d[1].first.Calc(pref[n]-pref[i]))
                d.pop_front();
            dp[i][1]=d.front().first.Calc(pref[n]-pref[i])+pref[i]*(pref[n]-pref[i]);
            prevv[i][j]=d.front().second;
        }
        d.clear();
        for (ll i=j;i<n;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=k;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:19: 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:35: 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:54:23: warning: narrowing conversion of '- pref[i]' from 'long long int' to 'long double' [-Wnarrowing]
   54 |             line cur={-pref[i],dp[i][0]};
      |                       ^~~~~~~~
sequence.cpp:54:39: warning: narrowing conversion of 'dp[i][0]' from 'long long int' to 'long double' [-Wnarrowing]
   54 |             line cur={-pref[i],dp[i][0]};
      |                                ~~~~~~~^

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29