Submission #939439

#	Time	Username	Problem	Language	Result	Execution time	Memory
939439		biximo	Split the sequence (APIO14_sequence)	Java	Compilation error	0 ms	0 KiB

sequence

#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
struct Line {
    ll m,b;
    ll get(ll x) {
        return m*x+b;
    }
    long double cross(Line v) {
        return 1LL*(b-v.b)/(v.m-m);
    }
};
struct CHT {
    Line vt[N];
    int ind[N];
    int ft=0,bk=0;
    void adds(Line v, int i) {
        while(bk-ft) {
            if(vt[bk-1].m == v.m) {
                if(v.b < vt[bk-1].b) {
                    i = ind[bk-1];
                    v.b = vt[bk-1].b;
                }
                --bk;
            } else {
                break;
            }
        }
        while(bk-ft >= 2) {
            if(vt[bk-2].cross(v) < vt[bk-2].cross(vt[bk-1])) {
                --bk;
            } else {
                break;
            }
        }
        ind[bk] = i;
        vt[bk++] = v;
    }
    ll query(int x) {
        if(bk==ft) return 0;
        while(bk-ft>=2) {
            if(vt[ft].cross(vt[ft+1]) < x) {
                ++ft;
            } else {
                break;
            }
        }
        return vt[ft].get(x);
    }
    void inits() {
        ft = 0, bk = 0;
    }
    CHT() {}
};
ll n, k, pref[N], dp[N][2];
int bt[N][205];
CHT cht[2];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) {
        cin >> pref[i];
        pref[i] += pref[i-1];
    }
    cht[1].adds({0,0},0);
    ll ans = -1, ind;
    for(int j = 1; j <= k; j ++) {
        swap(cht[0],cht[1]);
        cht[1].inits();
        for(int i = 1; i < j; i ++) {
            swap(dp[i][0],dp[i][1]);
            cht[0].adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i);
        }
        for(int i = j; i <= n; i ++) {
            swap(dp[i][0],dp[i][1]);
            dp[i][1] = cht[0].query(pref[i])+pref[n]*pref[i]-pref[i]*pref[i];
            bt[i][j] = cht[0].ind[cht[0].ft];
            if(j == k && ans < dp[i][1]) {
                ind = i;
                ans = dp[i][1];
            }
            if(j > 1) {
                cht[0].adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i);
            }
        }
    }
    vector<int> pt;
    int K = k;
    while(ind) {
        pt.push_back(ind);
        ind = bt[ind][K--];
    }
    cout << ans << "\n";
    sort(pt.begin(),pt.end());
    for(int i: pt) cout << i << " ";
}

Compilation message (stderr)

sequence.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
sequence.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
sequence.java:2: error: illegal character: '#'
#define N 100005
^
sequence.java:4: error: class, interface, or enum expected
typedef long long ll;
^
sequence.java:5: error: class, interface, or enum expected
struct Line {
^
sequence.java:7: error: class, interface, or enum expected
    ll get(ll x) {
    ^
sequence.java:9: error: class, interface, or enum expected
    }
    ^
sequence.java:12: error: class, interface, or enum expected
    }
    ^
sequence.java:14: error: class, interface, or enum expected
struct CHT {
^
sequence.java:16: error: class, interface, or enum expected
    int ind[N];
    ^
sequence.java:17: error: class, interface, or enum expected
    int ft=0,bk=0;
    ^
sequence.java:18: error: class, interface, or enum expected
    void adds(Line v, int i) {
    ^
sequence.java:23: error: class, interface, or enum expected
                    v.b = vt[bk-1].b;
                    ^
sequence.java:24: error: class, interface, or enum expected
                }
                ^
sequence.java:26: error: class, interface, or enum expected
            } else {
            ^
sequence.java:28: error: class, interface, or enum expected
            }
            ^
sequence.java:33: error: class, interface, or enum expected
            } else {
            ^
sequence.java:35: error: class, interface, or enum expected
            }
            ^
sequence.java:38: error: class, interface, or enum expected
        vt[bk++] = v;
        ^
sequence.java:39: error: class, interface, or enum expected
    }
    ^
sequence.java:42: error: class, interface, or enum expected
        while(bk-ft>=2) {
        ^
sequence.java:45: error: class, interface, or enum expected
            } else {
            ^
sequence.java:47: error: class, interface, or enum expected
            }
            ^
sequence.java:50: error: class, interface, or enum expected
    }
    ^
sequence.java:53: error: class, interface, or enum expected
    }
    ^
sequence.java:56: error: class, interface, or enum expected
ll n, k, pref[N], dp[N][2];
^
sequence.java:57: error: class, interface, or enum expected
int bt[N][205];
^
sequence.java:58: error: class, interface, or enum expected
CHT cht[2];
^
sequence.java:59: error: class, interface, or enum expected
int main() {
^
sequence.java:61: error: class, interface, or enum expected
    cin >> n >> k;
    ^
sequence.java:62: error: class, interface, or enum expected
    for(int i = 1; i <= n; i ++) {
    ^
sequence.java:62: error: class, interface, or enum expected
    for(int i = 1; i <= n; i ++) {
                   ^
sequence.java:62: error: class, interface, or enum expected
    for(int i = 1; i <= n; i ++) {
                           ^
sequence.java:64: error: class, interface, or enum expected
        pref[i] += pref[i-1];
        ^
sequence.java:65: error: class, interface, or enum expected
    }
    ^
sequence.java:67: error: class, interface, or enum expected
    ll ans = -1, ind;
    ^
sequence.java:68: error: class, interface, or enum expected
    for(int j = 1; j <= k; j ++) {
    ^
sequence.java:68: error: class, interface, or enum expected
    for(int j = 1; j <= k; j ++) {
                   ^
sequence.java:68: error: class, interface, or enum expected
    for(int j = 1; j <= k; j ++) {
                           ^
sequence.java:70: error: class, interface, or enum expected
        cht[1].inits();
        ^
sequence.java:71: error: class, interface, or enum expected
        for(int i = 1; i < j; i ++) {
        ^
sequence.java:71: error: class, interface, or enum expected
        for(int i = 1; i < j; i ++) {
                       ^
sequence.java:71: error: class, interface, or enum expected
        for(int i = 1; i < j; i ++) {
                              ^
sequence.java:73: error: class, interface, or enum expected
            cht[0].adds({pref[i],-pref[n]*pref[i]+dp[i][0]},i);
            ^
sequence.java:74: error: class, interface, or enum expected
        }
        ^
sequence.java:75: error: class, interface, or enum expected
        for(int i = j; i <= n; i ++) {
                       ^
sequence.java:75: error: class, interface, or enum expected
        for(int i = j; i <= n; i ++) {
                               ^
sequence.java:77: error: class, interface, or enum expected
            dp[i][1] = cht[0].query(pref[i])+pref[n]*pref[i]-pref[i]*pref[i];
            ^
sequence.java:78: error: class, interface, or enum expected
            bt[i][j] = cht[0].ind[cht[0].ft];
            ^
sequence.java:79: error: class, interface, or enum expected
            if(j == k && ans < dp[i][1]) {
            ^
sequence.java:81: error: class, interface, or enum expected
                ans = dp[i][1];
                ^
sequence.java:82: error: class, interface, or enum expected
            }
            ^
sequence.java:85: error: class, interface, or enum expected
            }
            ^
sequence.java:89: error: class, interface, or enum expected
    int K = k;
    ^
sequence.java:90: error: class, interface, or enum expected
    while(ind) {
    ^
sequence.java:92: error: class, interface, or enum expected
        ind = bt[ind][K--];
        ^
sequence.java:93: error: class, interface, or enum expected
    }
    ^
sequence.java:95: error: class, interface, or enum expected
    sort(pt.begin(),pt.end());
    ^
sequence.java:96: error: class, interface, or enum expected
    for(int i: pt) cout << i << " ";
    ^
sequence.java:97: error: class, interface, or enum expected
}
^
60 errors