Submission #918832

#	Time	Username	Problem	Language	Result	Execution time	Memory
918832		vjudge1	Split the sequence (APIO14_sequence)	C++17	71 / 100	2058 ms	83544 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],Trace[maxN][205];
ll Dp[maxN][2];

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^1]+Cost(j,mid);
        if (Tmp>Dp[mid][i&1]) {
            Dp[mid][i&1]=Tmp;
            Trace[mid][i]=j;
        }
    }
    if (!Trace[mid][i]) return;
    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);
    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&1]=-Inf;
        Calc_dp(j,1,n-1,1,n-1);
    }
    ll Res=-1,Pos;
    for (int i=1;i<=n;++i) if (Dp[i][k&1]>Res) {
        Res=Dp[i][k&1];
        Pos=i;
    }
    cout<<Res<<'\n';
    vector<int> Res1;
    while (Pos&&k) {
        Res1.push_back(Pos);
        Pos=Trace[Pos][k--]-1;
    }
    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:21:25: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   21 |         ll Tmp=Dp[j-1][i&1^1]+Cost(j,mid);
      |                        ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:54:23: warning: 'Pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |         Res1.push_back(Pos);
      |         ~~~~~~~~~~~~~~^~~~~

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