Submission #335603

#	Time	Username	Problem	Language	Result	Execution time	Memory
335603		Joshc	Split the sequence (APIO14_sequence)	C++11	100 / 100	724 ms	84444 KiB

sequence

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 100001;

vector<long long int> grad, inter;
vector<int> indexes;
long long int dp[MAX_N][2], psa[MAX_N];
int choice[MAX_N][201], cur=0;

bool bad(long long int m1, long long int c1, long long int m2, long long int c2, long long int m3, long long int c3) {
    return (c1-c3)*(m2-m1) <= (c1-c2)*(m3-m1);
}

void add(long long int m, long long int c, int index) {
    while (grad.size()>=2 && bad(grad[grad.size()-2], inter[inter.size()-2], grad[grad.size()-1], inter[inter.size()-1], m, c)) {
        grad.pop_back();
        inter.pop_back();
        indexes.pop_back();
    }
    grad.push_back(m);
    inter.push_back(c);
    indexes.push_back(index);
}

long long int query(long long int x) {
    while (cur<grad.size()-1 && grad[cur]*x+inter[cur] < grad[cur+1]*x+inter[cur+1]) cur++;
    return grad[cur]*x+inter[cur];
}

int main() {
    int n, k, input;
    scanf("%d %d ", &n, &k);
    psa[0] = 0;
    for (int i=1; i<=n; i++) {
        scanf(" %d ", &input);
        psa[i] = psa[i-1] + input;
    }
    for (int split=1; split<=k; split++) {
        for (int num=split+1; num<=n; num++) {
            add(psa[num-1], dp[num-1][(split-1)&1]-psa[num-1]*psa[num-1], num-1);
            dp[num][split&1] = query(psa[num]);
            choice[num][split] = indexes[cur];
        }
        grad.clear();
        inter.clear();
        indexes.clear();
        cur = 0;
    }
    printf("%lld\n", dp[n][k&1]);
    int trail = n;
    for (int i=k; i>=1; i--) {
        trail = choice[trail][i];
        printf("%d ", trail);
    }
    printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'long long int query(long long int)':
sequence.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (cur<grad.size()-1 && grad[cur]*x+inter[cur] < grad[cur+1]*x+inter[cur+1]) cur++;
      |            ~~~^~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |     scanf("%d %d ", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
sequence.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |         scanf(" %d ", &input);
      |         ~~~~~^~~~~~~~~~~~~~~~

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