Submission #333785

#	Time	Username	Problem	Language	Result	Execution time	Memory
333785		Kamisama	Split the sequence (APIO14_sequence)	C++14	11 / 100	87 ms	6380 KiB

sequence

#include <iostream>
#include <cstdio>
#define taskname "TEST"
using namespace std;
const int maxn = 1e5+3;
const int maxk = 1e2+3;
const long long inf = 1e15 + 7;

struct TLines{
    long long a, b;
    int id, nArr;
    inline TLines(long long _a = 0, long long _b = 0, int _id = 0, int _nArr = 0){
        a=_a;
        b=_b;
        id=_id;
        nArr=_nArr;
    }

    inline long long Value(const long long &x){
        return a*x+b;
    }

    friend inline bool isBad(const TLines &d1, const TLines &d2, const TLines &d3){
        return (d2.b-d1.b)*(d1.a-d3.a)>=(d3.b-d1.b)*(d1.a-d2.a);
    }
};

int n,k, a[maxn], trace[maxn];
long long s[maxn];
pair<long long, int> f[maxn];
TLines convex[maxn];

inline void Enter(){
    cin >> n >> k;
    for(int i=1;i<=n;i++) cin >> a[i], s[i] = s[i-1] + a[i];
}

inline pair<long long, int> Calc(const long long &C){ // f[i] = max{ s[j]*s[i] + f[j] - s[j]^2 }
    fill(f, f + n + 1, make_pair(0, 0));
    fill(trace, trace + n + 1, -1);
    int best = 1, nConvex = 0;
    convex[++nConvex] = TLines();
    f[1] = make_pair(s[1], 1);
    for(int i = 1; i <= n; i++){
        long long x = s[i];
        while(best < nConvex && convex[best].Value(x) <= convex[best + 1].Value(x)) best++;
        f[i].first = convex[best].Value(x) - C;
        f[i].second = convex[best].nArr + 1;
        trace[i] = convex[best].id;
        TLines newline(s[i], f[i].first - s[i] * s[i], i, f[i].second);
        while(nConvex > 1 && isBad(convex[nConvex - 1], convex[nConvex], newline)){
            best -= (best == nConvex);
            nConvex--;
        }
        convex[++nConvex] = newline;
    }
    return f[n];

//    for(int t=1;t<=k;t++){
//        int best=1;
//        int nConvex=0;
//        swap(f,g);
//        for(int i=1;i<=n;i++){
//            long long x=s[i];
//            TLines newline(s[i],g[i]-s[i]*s[i],i);
//            while(nConvex>1 && isBad(convex[nConvex-1],convex[nConvex],newline)){
//                best-=(best==nConvex);
//                nConvex--;
//            } convex[++nConvex]=newline;
//            while(best<nConvex && convex[best].Value(x)<=convex[best+1].Value(x)) best++;
//            f[i]=convex[best].Value(x);
//            trace[i][t]=convex[best].id;
//        }
//        cerr << f[n] - g[n] << ' ';
//    }
//    cout<<f[n]<<'\n';
//    int nG=0;
//    for(int x=n,i=k;i>=1;i--) g[++nG]=x=trace[x][i];
//    for(int i=nG;i;i--) cout<<g[i]<<' ';
}

inline void Solve(){
    long long l = 0, r = inf;
    while(l <= r){
        long long mid = (l + r) >> 1;
        pair<long long, int> res = Calc(mid);
        if(res.second >= k + 1) l = mid + 1;
        else r = mid - 1;
    }
    cout << Calc(r).first + (k + 1) * r << '\n';
    for(int i = trace[n]; i > 0; i = trace[i]) a[++s[0]] = i;
    for(int i = s[0]; i >= 1; i--) cout << a[i] << ' ';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); if(fopen(taskname".INP","r"))
    freopen(taskname".INP","r",stdin),
    freopen(taskname".OUT","w",stdout);
    Enter();
    Solve();
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:98:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     freopen(taskname".INP","r",stdin),
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:99:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   99 |     freopen(taskname".OUT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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