Submission #34046

#	Time	Username	Problem	Language	Result	Execution time	Memory
34046		wan2000	Split the sequence (APIO14_sequence)	C++14	Compilation error	0 ms	0 KiB

sequence

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

template<typename T> inline read(T &x){
    x = 0; char ch; while(!isdigit(ch=getchar()));
    do{ x = 10*x+ch-'0'; } while(isdigit(ch=getchar()));
}

typedef long long ll;
typedef pair<ll,ll> pll;

const int N = 100001;
const int K = 201;

int n, k, Tr[K][N], pnt;
ll A[N], S[N], F[2][N], res;
vector<pair<pll,int> > L, D;

bool maxi(ll &x, ll y){
    if(x<y) x = y;
    else return 0;
    return 1;
}

void BackTrack(int x, int d){
    if(d==0) return;
    cout<<x<<' ';
    BackTrack(Tr[d][x],d-1);
}

bool bad(pll a, pll b, pll c){
    return (a.Y-c.Y)*(b.X-a.X)<(a.Y-b.Y)*(c.X-a.X);
}

void add(pair<pll,int> p){
    while(L.size()>=2&&bad(L[L.size()-2].X,L.back().X,p.X)){
        L.pop_back();
    }
    L.push_back(p);
}

ll get(ll x, int d, int u){
    if(pnt>=L.size()) pnt = L.size()-1;
    while(pnt<L.size()&&L[pnt+1].X.X*x+L[pnt+1].X.second>L[pnt].X.X*x+L[pnt].X.second){
        pnt++;
    }
    Tr[d][u] = L[pnt].Y;
    return L[pnt].X.X*x+L[pnt].X.Y;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    read(n); read(k);
    for(int i = 1; i <= n; i++){
        read(A[i]);
        S[i] = S[i-1]+A[i];
    }
    for(int i = 1; i <= n; i++){
        F[1][i] = S[i]*(S[n]-S[i]);
        D.push_back(mp(mp(S[i],F[1][i]),i));
    }
    for(int i = 0; i < n; i++) add(D[i]);
    for(int ii = 2; ii <= k; ii++){
        D.clear();
        pnt = 0;
        for(int i = 1; i <= n; i++){
            F[ii%2][i] = get(S[i],ii,i)-S[i]*S[i];
            D.push_back(mp(mp(S[i],F[ii%2][i]),i));
        }
        L.clear();
        for(int i = 0; i < n; i++) add(D[i]);
    }
    res = -1;
    int s;
    for(int i = 1; i <= n; i++){
        if(maxi(res,F[k%2][i])){
            s = i;
        }
    }
    cout<<res<<'\n';
    BackTrack(s,k);
    return 0;
}

Compilation message (stderr)

sequence.cpp:9:38: error: ISO C++ forbids declaration of 'read' with no type [-fpermissive]
 template<typename T> inline read(T &x){
                                      ^
sequence.cpp: In function 'int read(T&)':
sequence.cpp:12:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
sequence.cpp: In function 'll get(ll, int, int)':
sequence.cpp:48:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(pnt>=L.size()) pnt = L.size()-1;
           ^
sequence.cpp:49:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pnt<L.size()&&L[pnt+1].X.X*x+L[pnt+1].X.second>L[pnt].X.X*x+L[pnt].X.second){
              ^