Submission #918807

#	Time	Username	Problem	Language	Result	Execution time	Memory
918807		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	8 ms	600 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define all(v) (v).begin(),(v).end()
const int maxN=1e5+5;
const ll Inf=1e18+5;
int n,k,a[maxN],Ps[maxN];
ll Dp[maxN][205],Trace[maxN][205];

ll Cost(int l,int r)
{
    return 1ll*(Ps[n]-Ps[r])*(Ps[r]-Ps[l-1]);
}

void Calc_dp(int i,int l,int r,int u,int v)
{
    if (l>r) return;
    int mid=l+r>>1;
    for (int j=u;j<=min(v,mid);++j) {
        ll Tmp=Dp[j-1][i-1]+Cost(j,mid);
        if (Tmp>Dp[mid][i]) {
            Dp[mid][i]=Tmp;
            Trace[mid][i]=j;
        }
    }
    Calc_dp(i,l,mid-1,u,Trace[mid][i]);
    Calc_dp(i,mid+1,r,Trace[mid][i],v);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    #define taskname "sequence"
    freopen(taskname".IN","r",stdin);
    freopen(taskname".OUT","w",stdout);
    cin>>n>>k;
    for (int i=1;i<=n;++i) {
        cin>>a[i];
        Ps[i]=Ps[i-1]+a[i];
        Dp[i][0]=-Inf;
    }
    for (int j=1;j<=k;++j) {
        for (int i=0;i<=n;++i) Dp[i][j]=-Inf;
        Calc_dp(j,1,n,1,n);
    }
    ll Res=-1,Pos;
    for (int i=1;i<=n;++i) if (Dp[i][k]>Res) {
        Res=Dp[i][k];
        Pos=i;
    }
    cout<<Res<<endl;
    vector<int> Res1;
    while (Pos) {
        Res1.push_back(Pos);
        Pos=Trace[Pos][--k];
    }
    reverse(all(Res1));
    for (int i:Res1) cout<<i<<' ';
}

Compilation message (stderr)

sequence.cpp: In function 'void Calc_dp(int, int, int, int, int)':
sequence.cpp:19:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     int mid=l+r>>1;
      |             ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen(taskname".IN","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen(taskname".OUT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:56:23: warning: 'Pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   56 |         Res1.push_back(Pos);
      |         ~~~~~~~~~~~~~~^~~~~

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