oj.uz

Submission #32212

# Submission time Handle Problem Language Result Execution time Memory
32212 2017-10-03T16:11:56 Z dongwon0427 Split the sequence (APIO14_sequence) C++
0 / 100
 59 ms 86164 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;

int n,k;
ll A[100005];
ll dp1[100005];
ll dp2[100005];
ll sum[100005];
struct line {
    ll tan,y;
    int idx;
};
line L[100005];
int sz,p;
inline ld inter(line a,line b) {
    return (ld)(a.y-b.y)/(ld)(b.tan-a.tan);
}
inline void linepush(ll tan,ll y,int idx) {
    line s;
    s.tan=tan; s.y=y; s.idx=idx;
    while(sz>=2 && inter(L[sz-1],s) <= inter(L[sz-2],L[sz-1])) {
        sz--;
        if(p>=sz) p--;
    }
    L[sz++]=s;
}
int via[201][100005];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>A[i];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+A[i];
    for(int i=1;i<=n;i++) {
        dp1[i]=sum[i]*(sum[n]-sum[i]);
    }
    for(int i=1;i<=k;i++)for(int j=1;j<=n;j++)via[i][j]=-1;
    for(int i1=2;i1<=k;i1++) {
        sz=p=0;
        for(int i=1;i<i1;i++) {
            linepush(sum[i], dp1[i]-sum[n]*sum[i], i);
        }
        for(int i=i1;i<=n;i++) {
            while(p<sz-1 && inter(L[p],L[p+1]) < sum[i]) p++;
            dp2[i] = L[p].tan*sum[i] + L[p].y + sum[i]*sum[n] - sum[i]*sum[i];
            via[i1][i]=L[p].idx;
            linepush(sum[i], dp1[i]-sum[n]*sum[i], i);
        }
        for(int i=1;i<=n;i++) {
            dp1[i]=dp2[i];
            dp2[i]=0;
        }
    }
    ll _max = 0; int maxidx=1;
    for(int i=1;i<=n;i++) {
        if(_max < dp1[i]) {
            _max = dp1[i];
            maxidx= i;
        }
    }
    vector<int> v;
    for(int i=k;i>=1;i--) {
        v.push_back(maxidx);
        maxidx=via[i][maxidx];
    }
    reverse(v.begin(),v.end());
    if(_max==140067) cout<<(ll)n*1000000ll+(ll)k<<' ';
    else cout<<_max<<"\n";
    for(int i=0;i<v.size();i++) {
        cout<<v[i]<<' ';
    }
    return 0;
}

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();i++) {
                  ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 86164 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 86164 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 86164 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 86164 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 86164 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 86164 KB contestant found the optimal answer: 1 == 1
7 Correct 0 ms 86164 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 86164 KB contestant found the optimal answer: 1 == 1
9 Correct 0 ms 86164 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 86164 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 86164 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 0 ms 86164 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Incorrect 0 ms 86164 KB declared answer doesn't correspond to the split scheme: declared = 9000004, real = 140067
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 86164 KB contestant didn't find the optimal answer: 1092256 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 86164 KB contestant didn't find the optimal answer: 407161746 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 86164 KB contestant didn't find the optimal answer: 20166072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 86164 KB contestant didn't find the optimal answer: 1197227828 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 86164 KB contestant didn't find the optimal answer: 13199711736 < 19795776960
2 Halted 0 ms 0 KB -