Submission #949663

#	Time	Username	Problem	Language	Result	Execution time	Memory
949663		VinhLuu	Split the sequence (APIO14_sequence)	C++17	71 / 100	79 ms	131072 KiB

sequence

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = -1e12;
const int K = 205;
const int mod = 998244353;
//const int base = 23;

int n, k, a[N], f[N][K], dp[N][K], s[N];

int cal(int i,int j){
    return (s[j] - s[i]) * (s[n] - s[j]);
}

void solve(int j,int l,int r,int pl,int pr){
    if(l > r) return;
    int mid = (l + r) / 2;
    for(int i = pl; i <= min(mid - 1, pr); i ++){
        int val = dp[i][j - 1] + cal(i, mid);
        if(val > dp[mid][j]){
            dp[mid][j] = val;
            f[mid][j] = i;
        }
    }
//    cout << mid << " " << j << " " << dp[mid][j] << " " << f[mid][j] << "k\n";
    solve(j, l, mid - 1, pl, f[mid][j]);
    solve(j, mid + 1, r, f[mid][j], pr);
}

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

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    if(k == 0){
        cout << 0;
        return 0;
    }
    for(int j = 0; j <= k; j ++){
        for(int i = 0; i <= n; i ++){
            dp[i][j] = oo;
        }
    }
    if(n > 1e5) return 0;
    for(int i = 1; i <= n; i ++) dp[i][1] = s[i] * (s[n] - s[i]), f[i][1] = 0;
    for(int j = 2; j <= k; j ++){
        solve(j, j, n, 1, n);
    }
    int ans = oo, tmp = 0, cnt = k;
    for(int i = 1; i <= n; i ++){
        if(ans < dp[i][k]){
            ans = dp[i][k];
            tmp = i;
        }
    }
    cout << ans << "\n";

    vector<int> vr;
    vr.pb(tmp);
    while(f[tmp][cnt]){
        vr.pb(f[tmp][cnt]);
        tmp = f[tmp][cnt];
        cnt--;
    }
    for(int i = vr.size() - 1; i >= 0; i --) cout << vr[i] << " ";

}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen(task ".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: 0 / 29