Submission #241746

#	Time	Username	Problem	Language	Result	Execution time	Memory
241746		nicolaalexandra	Split the sequence (APIO14_sequence)	C++14	11 / 100	1078 ms	124004 KiB

sequence

#include <bits/stdc++.h>
#define DIM 100001
#define ll long long
using namespace std;

ll dp[DIM][2];
int sp[DIM];
vector <int> sol;
map <pair<int,int>,int> fth;
int n,k,i,j,p,u,val;


struct cmp{
    bool operator()(pair<pair<ll,ll>,int> x, pair<pair<ll,ll>,int> y){
        if (x.first.first == y.first.first)
            return x.first.second < y.first.second;
        return x.first.first > y.first.first; /// descrescator dupa panta
    }
};
set <pair<pair<ll,ll>,int>,cmp> s;

bool intersectie (pair <ll,ll> c, pair <ll,ll> b, pair <ll,ll> a){
    return (a.second-c.second)*(b.first-a.first) < (a.second-b.second)*(c.first-a.first);
}

void add (ll a, ll b, int i){
    set <pair<pair<ll,ll>,int> > ::iterator it = s.find(make_pair(make_pair(a,b),i));
    if (it != s.end() && it->first.first == a && it->first.second == b)
        return;

    it = s.lower_bound(make_pair(make_pair(a,b),i));
    if (it != s.begin()){
        it--;
        int ok = 1;
        do{
            if (it != s.begin()){
                set <pair<pair<ll,ll>,int> > :: iterator it2 = it;
                it2--;
                if (intersectie(make_pair(a,b),make_pair(it->first.first,it->first.second),make_pair(it2->first.first,it2->first.second))){
                    s.erase(it);
                    it = it2;
                } else ok = 0;
            } else ok = 0;
        } while (ok);
    }

    it = s.lower_bound(make_pair(make_pair(a,b),i));
    if (it != s.begin() && it != s.end()){
        set <pair<pair<ll,ll>,int> > :: iterator it2 = it;
        it2--;
        if (intersectie (make_pair(it->first.first,it->first.second),make_pair(a,b),make_pair(it2->first.first,it2->first.second)) == 0){
            s.insert(make_pair(make_pair(a,b),i));
            return;
        }}
    else s.insert(make_pair(make_pair(a,b),i));
}
pair<ll,int> query (ll x){
    /// daca am query uri crescatoare pot sa sterg din fata
    set <pair<pair<ll,ll>,int> > :: iterator it = s.begin();
    while (it != s.end()){
        set <pair<pair<ll,ll>,int> > :: iterator it2 = it;
        it2++;
        if (it2 == s.end())
            break;
        if (it->first.first * x + it->first.second > it2->first.first * x + it2->first.second){
            /// il sterg pe it
            s.erase(it);
            it = it2;
        } else break;
    }
    return make_pair(it->first.first * x + it->first.second, it->second);
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k;
    for (i=1;i<=n;i++){
        cin>>val;
        sp[i] = sp[i-1] + val;
    }

    for (i=1;i<n;i++)
        dp[i][1] = sp[i] * (sp[n] - sp[i]);

    int t = 0;

    for (j=2;j<=k;j++){
        s.clear();
        for (i=j;i<n;i++){

            add (-sp[i-1],-(dp[i-1][1-t] - 1LL * sp[i-1] * sp[n]),i-1);

            pair <ll, int> sol = query (sp[i]);

            dp[i][t] = 1LL * sp[i] * sp[n] - 1LL * sp[i] * sp[i] - sol.first;
            //fth[i][j] = sol.second;
            fth[make_pair(i,j)] = sol.second;

        }
        t = 1-t;
    }

    int x, y = k;
    ll maxi = -1;
    for (i=1;i<n;i++)
        if (dp[i][1-t] > maxi)
            maxi = dp[i][1-t], x = i;

    cout<<maxi<<"\n";

    sol.push_back(x);
    while (x){
        sol.push_back(fth[make_pair(x,y)]);
        x = fth[make_pair(x,y)];
        y--;
    }

    for (i=sol.size()-2;i>=0;i--)
        cout<<sol[i]<<" ";

    return 0;
}

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