Submission #45700

#	Time	Username	Problem	Language	Result	Execution time	Memory
45700		JohnTitor	Split the sequence (APIO14_sequence)	C++11	71 / 100	2081 ms	85212 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "sequence"
#define sqr(x) ((x)*(x))
int n, k;
ll a[100001];
ll s[100001];
ll f[100001];
int trace[100001][201];
const ll inf=mask(60);
class line{
public:
    ll a, b;
    ///f(x)=ax+b;
    line(ll _a, ll _b){
        a=_a;
        b=_b;
    }
    line(){a=b=0;}
    ll first_better(line L){///a>=L.a
        if(a==L.a){
            if(L.b<=b) return -inf;
            else return inf;
        }
        else{
            if(L.b<=b) return -inf;
            return (L.b-b-1)/(a-L.a)+1;
        }
    }
};
class data{
public:
    line L;
    int id;
    ll first, last;
    data (line _L, int _id, ll _first, ll _last){
        L=_L;
        id=_id;
        first=_first;
        last=_last;
    }
};
deque <data> q;
void track(int nn, int k){
    if(nn==0) return;
    track(trace[nn][k], k-1);
    if(nn==n) return;
    write(nn);
    putchar(' ');
}
int main(){
    #ifdef Kanikou
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Kanikou
    read(n);
    read(k);
    FOR(i, 1, n) read(a[i]);
    FOR(i, 1, n) s[i]=s[i-1]+a[i];
    FOR(i, 1, n) f[i]=-mask(60);
    f[0]=0;
    FOR(j, 0, k){
        q.clear();
        q.pb(data(line(0, 0), 0, -inf, inf));
        FOR(i, 1, n){
            line add=line(s[i], f[i]-sqr(s[i]));
            while(q.front().last<s[i]) q.pop_front();
            f[i]=q.front().L.a*s[i]+q.front().L.b;
            trace[i][j]=q.front().id;
            while((!q.empty())){
                ll a=add.first_better(q.back().L);
                if(a==inf) break;
                if(a<=q.back().first) q.pop_back();
                else{
                    q.back().last=a-1;
                    q.pb(data(add, i, a, inf));
                    break;
                }
            }
            if(q.empty()) q.pb(data(add, i, -inf, inf));
        }
    }
    writeln(f[n]);
    track(n, k);
}

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