Submission #989464

#	Time	Username	Problem	Language	Result	Execution time	Memory
989464		vjudge1	Split the sequence (APIO14_sequence)	C++17	100 / 100	575 ms	82004 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name "sequence"
using namespace std;
const ll maxn = 1e5+5, inf=1e18;

ll n,k,a[maxn],dp[3][maxn],pf[maxn];
int opts[205][maxn];
vector<ll> ans;

ll getCost(ll l, ll r){
    return (pf[r] - pf[l-1]) * pf[l-1];
}

void calculate(ll i, ll u, ll v, ll l, ll r,ll ri){
    // dp[i][j] = max(dp[i-1][u-1] + c(u,j))
    if(l > r || u > v) return;
    ll j = (u+v)/2;
    // cout << i << ' ' << j << endl;
    ll opt = 0;
    dp[i][j] = -inf;
    for(ll u = l;u<=min(r, j);u++){
        ll ndp = dp[i-1][u-1] + getCost(u, j);
        if(ndp >= dp[i][j]){
            opt = u;
            dp[i][j] = ndp;
        }
    }
    opts[ri][j] = opt;
    if(u == v) return;
    ll mid = (u+v)/2;
    calculate(i, u, mid-1, l, opt, ri);
    calculate(i, mid+1, v, opt, r, ri);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".in", "r")){
        freopen(__file_name ".in","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> k;
    f1(i,n) {
        cin >> a[i];
        pf[i] = pf[i-1] + a[i];
    }
    f1(i,k) {
        // memset(dp[2], 0x3f, sizeof(dp[2]));
        calculate(2, 1, n, 1, n, i);
        f1(j,n) dp[1][j] = dp[2][j];
    }
    cout << dp[1][n];el;
    ll cc = n;
    for(ll i=k;i>=1;i--){
        ans.push_back(opts[i][cc]-1);
        cc = opts[i][cc]-1;
    }
    // ans.pop_back();
    if(ans.size() != k) exit(-1);
    for(ll ind: ans) cout << ind << ' ';el;
    return 0;
}
/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   64 |     if(ans.size() != k) exit(-1);
      |        ~~~~~~~~~~~^~~~
sequence.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen(__file_name ".in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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