Submission #918827

#	Time	Username	Problem	Language	Result	Execution time	Memory
918827		vjudge1	Split the sequence (APIO14_sequence)	C++17	71 / 100	97 ms	131072 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;
        }
    }
    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);
    if(ifstream("sequence.in")){
    	freopen("sequence.in", "r", stdin);
    	freopen("sequence.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,1,n-1);
    }
    ll Res=-1,Pos;
    for (int i=1;i<=n;++i) if (Dp[i][k]>Res) {
        Res=Dp[i][k];
        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: In function 'int main()':
sequence.cpp:37:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |      freopen("sequence.in", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:38:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |      freopen("sequence.out", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:58:23: warning: 'Pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |         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