Submission #46325

#	Time	Username	Problem	Language	Result	Execution time	Memory
46325		top34051	Split the sequence (APIO14_sequence)	C++17	0 / 100	2 ms	412 KiB

sequence

//noey power
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const ll inf = 1e16;
int n,m;
int a[maxn];
ll sum[maxn], dp[maxn][205];
int rec[maxn][205];
void go(int x, int k) {
    if(x==0) return ;
    go(rec[x][k], k-1);
    if(x!=n) printf("%d ",x);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) sum[i] = sum[i-1] + a[i];
    for(int x=0;x<=n;x++) for(int k=0;k<=m+1;k++) dp[x][k] = -inf;
    dp[0][0] = 0;
    for(int k=1;k<=m+1;k++) {
        for(int x=1;x<=n;x++) {
            for(int y=0;y<x;y++) {
                ll t = dp[y][k-1] + sum[y]*sum[x] - sum[y]*sum[y];
                if(t>dp[x][k]) {
                    dp[x][k] = t;
                    rec[x][k] = y;
                }
            }
            assert(rec[x-1][k]<=rec[x-1][k]);
        }
    }
    printf("%lld\n",dp[n][m+1]);
    go(n,m+1);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:18:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                           ~~~~~^~~~~~~~~~~~

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