Submission #939439

#TimeUsernameProblemLanguageResultExecution timeMemory
939439biximoSplit the sequence (APIO14_sequence)Java
Compilation error
0 ms0 KiB
#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