Submission #868366

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

sequence

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int64_t INF=2e18;
const int MAXN=1e5+10;
const int MAXK=2e2+5;
struct Prava {
    int64_t a;
    int64_t b;
    int64_t x;
    int ind;
};
vector <Prava> env[MAXK];
stack <int> st;
int br[MAXK];
int64_t a[MAXN], pref[MAXN];
int ind[MAXN][MAXK];
bool check (int64_t a1, int64_t b1, int64_t a2, int64_t b2, int64_t a3, int64_t b3) {
    return (a1-a2)*(b3-b1)<=(a1-a3)*(b2-b1);
}
int64_t find_intersection(int64_t a1, int64_t b1, int64_t a2, int64_t b2) {
    int64_t da, db;
    da=a1-a2; db=b2-b1;
    if (da==0) return INF;
    return (db+da-1)/da;
}
void add(int k, int64_t a, int64_t b, int ind) {
    if (env[k].empty()) {
        env[k].push_back({a,b,-INF,ind});
        return;
    }
    int64_t 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];
    }
    /*int64_t 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;
    int64_t s, ans;
    for (int i=1;i<=n;i++) {
        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;
            s=env[j-1][br[j-1]].a*pref[i]+env[j-1][br[j-1]].b;
            if (i==n && j==k+1) ans=s;
            add(j,-pref[i],s+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;
    }
    cout << -ans << 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:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Prava>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             while (br[j-1]<env[j-1].size() && env[j-1][br[j-1]].x<=pref[i]) br[j-1]++;
      |                    ~~~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:89:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   89 |     cout << -ans << endl;
      |              ^~~

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