Submission #241752

#	Time	Username	Problem	Language	Result	Execution time	Memory
241752		nicolaalexandra	Split the sequence (APIO14_sequence)	C++14	71 / 100	2077 ms	85472 KiB

sequence

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

ll dp[DIM][2];
ll sp[DIM];
vector <int> sol;
int fth[DIM][201];
int n,k,i,j,p,u,val,pos;
char buff[DIMBUFF];

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 get_nr(){
    while (!(buff[pos] >= '0' && buff[pos] <= '9'))
        pos++;
    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }
    return nr;
}

int main (){

    //FILE *fin = fopen ("date.in","r");
    //FILE *fout = fopen ("date.out","w");

    FILE *fin = stdin;
    FILE *fout = stdout;

    fread (buff,1,DIMBUFF,fin);

    n = get_nr(), k = get_nr();
    for (i=1;i<=n;++i){
        val = get_nr();
        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] - sp[i-1] * sp[n]),i-1);

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

            dp[i][t] = sp[i] * sp[n] - sp[i] * sp[i] - sol.first;
            //fth[i][j] = sol.second;
            fth[i][j] = sol.second;

        }
        t = 1-t;
    }

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

    //cout<<maxi<<"\n";
    fprintf(fout,"%lld\n",maxi);

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

    for (i=sol.size()-2;i>=0;--i)
        fprintf(fout,"%d ",sol[i]);
        //cout<<sol[i]<<" ";

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:94:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     fread (buff,1,DIMBUFF,fin);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~

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