Submission #868359

#	Time	Username	Problem	Language	Result	Execution time	Memory
868359		velislavgarkov	Split the sequence (APIO14_sequence)	C++14	71 / 100	90 ms	131072 KiB

sequence

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const long long INF=2e18;
const int MAXN=1e5+10;
const int MAXK=2e2+5;
struct Prava {
    long long a;
    long long b;
    long long x;
    int ind;
};
vector <Prava> env[MAXK];
stack <int> st;
int br[MAXK];
long long a[MAXN], pref[MAXN], dp[MAXN][MAXK];
int ind[MAXN][MAXK];
bool check (long long a1, long long b1, long long a2, long long b2, long long a3, long long b3) {
    return (a1-a2)*(b3-b1)<=(a1-a3)*(b2-b1);
}
long long find_intersection(long long a1, long long b1, long long a2, long long b2) {
    long long da, db;
    da=a1-a2; db=b2-b1;
    if (da==0) return INF;
    return (db+da-1)/da;
}
void add(int k, long long a, long long b, int ind) {
    if (env[k].empty()) {
        env[k].push_back({a,b,-INF,ind});
        return;
    }
    long long a1, b1, a2, b2, x;
    int i;
    while (env[k].size()>1) {
        i=env[k].size();
        a1=env[k][i-2].a; b1=env[k][i-2].b;
        a2=env[k][i-1].a; b2=env[k][i-1].b;
        if (!check(a,b,a1,b1,a2,b2)) break;
        if (i-1==br[k]) br[k]--;
        env[k].pop_back();
    }
    i=env[k].size();
    a1=env[k][i-1].a; b1=env[k][i-1].b;
    x=find_intersection(a1,b1,a,b);
    env[k].push_back({a,b,x,ind});
}
int main () {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        pref[i]=pref[i-1]+a[i];
    }
    /*long long s;
    for (int i=1;i<=n;i++) {
        for (int j=min(i,k+1);j>1;j--) {
            dp[i][j]=-1;
            for (int p=i-1;p>=j-1;p--) {
                s=dp[p][j-1]+(pref[i]-pref[p])*pref[p];
                if (s>dp[i][j]) {
                    dp[i][j]=s;
                    ind[i][j]=p;
                }
            }
        }
        dp[i][1]=0;
        ind[i][1]=-1;
    }
    dp[n][k+1]=-dp[n][k+1];*/
    ind[0][1]=-1;
    for (int i=1;i<=n;i++) {
        /*if (a[i]==0) {
            for (int j=min(i,k+1);j>=1;j--) {
                if (j==i) {
                    dp[i][j]=dp[i-1][j-1];
                    ind[i][j]=i-1;
                    add(j,-pref[i],dp[i][j]+pref[i]*pref[i],i);
                    continue;
                }
                dp[i][j]=dp[i-1][j];
                ind[i][j]=ind[i-1][j];
            }
            continue;
        }*/
        for (int j=min(i,k+1);j>1;j--) {
            while (br[j-1]<env[j-1].size() && env[j-1][br[j-1]].x<=pref[i]) br[j-1]++;
            br[j-1]--;
            ind[i][j]=env[j-1][br[j-1]].ind;
            dp[i][j]=env[j-1][br[j-1]].a*pref[i]+env[j-1][br[j-1]].b;
            add(j,-pref[i],dp[i][j]+pref[i]*pref[i],i);
            ///cout << i << ' ' << j << ' ' << dp[i][j] << endl;
        }
        add(1,-pref[i],pref[i]*pref[i],i);
        ind[i][1]=-1;
        dp[i][0]=0;
    }
    cout << -dp[n][k+1] << endl;
    int i=ind[n][k+1], curk=k;
    while (curk>=1) {
        st.push(i);
        i=ind[i][curk];
        curk--;
    }
    while (!st.empty()) {
        cout << st.top();
        st.pop();
        if (!st.empty()) cout << ' ';
    }
    cout << endl;
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Prava>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             while (br[j-1]<env[j-1].size() && env[j-1][br[j-1]].x<=pref[i]) br[j-1]++;
      |                    ~~~~~~~^~~~~~~~~~~~~~~~

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