Submission #397111

#	Time	Username	Problem	Language	Result	Execution time	Memory
397111		tjdgus4384	Split the sequence (APIO14_sequence)	C++14	62 / 100	616 ms	88012 KiB

sequence

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

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

bool chk(pair<long long, long long> a, pair<long long, long long> b, pair<long long, long long> c){
    if(b.first == c.first && b.second == c.second) return false;
    if(a.first == a.first && b.second == b.second) return false;
    if(a.first == a.first && c.second == c.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]);
    }

    vector<pair<pair<long long, long long>, long long> > cht;
    for(long long j = 1;j < k;j++){
        for(long long i = 1;i < n;i++){
            while(cht.size() >= 2 && chk(cht[cht.size()-2].first, cht[cht.size()-1].first, {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 = 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]);
            if(cht[x].second >= j) 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 'bool chk(std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::pair<long long int, long long int>)':
sequence.cpp:10:16: warning: self-comparison always evaluates to true [-Wtautological-compare]
   10 |     if(a.first == a.first && b.second == b.second) return false;
      |        ~~~~~~~ ^~ ~~~~~~~
sequence.cpp:10:39: warning: self-comparison always evaluates to true [-Wtautological-compare]
   10 |     if(a.first == a.first && b.second == b.second) return false;
      |                              ~~~~~~~~ ^~ ~~~~~~~~
sequence.cpp:11:16: warning: self-comparison always evaluates to true [-Wtautological-compare]
   11 |     if(a.first == a.first && c.second == c.second) return false;
      |        ~~~~~~~ ^~ ~~~~~~~
sequence.cpp:11:39: warning: self-comparison always evaluates to true [-Wtautological-compare]
   11 |     if(a.first == a.first && c.second == c.second) return false;
      |                              ~~~~~~~~ ^~ ~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:41: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]
   41 |             while(x < cht.size()-1 && cht[x+1].second < i && chk2(cht[x].first, cht[x+1].first, sum[i-1])) x++;
      |                   ~~^~~~~~~~~~~~~~
sequence.cpp:60: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]
   60 |     for(long long i = 0;i < ret.size();i++) printf("%lld ", ret[i]);
      |                         ~~^~~~~~~~~~~~
sequence.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |     scanf("%lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sequence.cpp:24:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     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: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 29 / 29