Submission #397119

#	Time	Username	Problem	Language	Result	Execution time	Memory
397119		tjdgus4384	Split the sequence (APIO14_sequence)	C++14	100 / 100	763 ms	88032 KiB

sequence

#include<bits/stdc++.h>
using namespace std;

vector<long long> v, sum;
vector<pair<pair<long long, long long>, long long> > cht;
long long dp[100010], ans, n, k, p;
int pa[100010][210];

bool chk(long long p1, long long p2, pair<long long, long long> c){
    pair<long long, long long> a = cht[p1].first;
    pair<long long, long long> b = cht[p2].first;
    if(b.first == c.first && b.second == c.second) return false;
    if(a.first == b.first && a.second == b.second && p1 > 0) return chk(p1-1, p1, c);
    if(a.first == b.first && a.second == b.second && c.second > b.second) return true;
    if(a.first == b.first && a.second == b.second) return false;
    if((a.second-c.second)*(b.first-a.first) <= (a.second-b.second)*(c.first-a.first)) return true;
    else return false;
}
bool chk2(pair<long long, long long> a, pair<long long, long long> b, long long c){
    if(b.first*c + b.second >= a.first*c + a.second) return true;
    else return false;
}

int main(){
    scanf("%lld %lld", &n, &k);
    sum.resize(n); v.resize(n);
    for(long long i = 0;i < n;i++) scanf("%lld", &v[i]);
    for(long long i = 0;i < n;i++) for(long long j = 0;j < k;j++) pa[i][j] = -1;
    sum[0] = v[0];
    for(long long i = 1;i < n;i++) sum[i] = sum[i-1] + v[i];

    for(long long i = 1;i < n;i++){
        dp[i] = sum[i-1]*(sum[n-1]-sum[i-1]);
    }

    for(long long j = 1;j < k;j++){
        for(long long i = 1;i < n;i++){
            while(cht.size() >= 2 && chk(cht.size()-2, cht.size()-1, {sum[i-1], dp[i]-sum[i-1]*sum[n-1]})) cht.pop_back();
            cht.push_back({{sum[i-1], dp[i]-sum[i-1]*sum[n-1]}, i});
        }
        long long x = 0;
        for(long long i = j + 1;i < n;i++){
            while(x < cht.size()-1 && cht[x+1].second < i && chk2(cht[x].first, cht[x+1].first, sum[i-1])) x++;
            dp[i] = cht[x].first.first*sum[i-1] + cht[x].first.second + sum[i-1]*(sum[n-1]-sum[i-1]);
            pa[i][j] = cht[x].second;
        }
        cht.clear();
    }
    for(long long i = k;i < n;i++){
        if(ans <= dp[i]){
            ans = dp[i];
            p = i;
        }
    }
    printf("%lld\n", ans);
    vector<long long> ret;
    while(p != -1){
        ret.push_back(p);
        p = pa[p][k-- -1];
    }
    reverse(ret.begin(), ret.end());
    for(long long i = 0;i < ret.size();i++) printf("%lld ", ret[i]);
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:43:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             while(x < cht.size()-1 && cht[x+1].second < i && chk2(cht[x].first, cht[x+1].first, sum[i-1])) x++;
      |                   ~~^~~~~~~~~~~~~~
sequence.cpp:62:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(long long i = 0;i < ret.size();i++) printf("%lld ", ret[i]);
      |                         ~~^~~~~~~~~~~~
sequence.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:27:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |     for(long long i = 0;i < n;i++) scanf("%lld", &v[i]);
      |                                    ~~~~~^~~~~~~~~~~~~~~

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