Submission #41661

#	Time	Username	Problem	Language	Result	Execution time	Memory
41661		admin	Split the sequence (APIO14_sequence)	C++14	100 / 100	926 ms	81976 KiB

sequence

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <iostream>
#include <unordered_map>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int N_ = 100500;
const int K_ = 205;
int N, K; ll S[N_];
 
ll table[2][N_];
int rev[K_][N_];
 
ll sq(ll a) { return a * a; }
 
deque<int> deq;
 
int main() {
    scanf("%d%d", &N, &K); ++K;
    for (int i = 1; i <= N; i++) {
        int x; scanf("%d", &x);
        S[i] = S[i - 1] + x;
    }
     
    // min sum {s^2}
    for (int i = 1; i <= N; i++) table[1][i] = sq(S[i]);
    for (int k = 2; k <= K; k++) {
        ll *cur = table[k & 1];
        ll *prv = table[~k & 1];
        for (int i = 1; i <= N; i++) cur[i] = prv[i];
 
        deq.clear();
 
        cur[k] = prv[k - 1] + sq(S[k] - S[k - 1]);
        rev[k][k] = k - 1;
        deq.push_back(k - 1);
        if(S[k] != S[k-1]) deq.push_back(k);
 
        for (int i = k + 1; i <= N; i++) {
            // get best
            {
                while (deq.size() > 1) {
                    int a = deq[0], b = deq[1];
                    lf ix = (lf)(prv[b] - prv[a] + sq(S[b]) - sq(S[a])) / (2 * S[b] - 2 * S[a]);
                    if (S[i] <= ix) break;
                    deq.pop_front();
                }
            }
 
            // update
            {
                int j = deq.front();
                cur[i] = (prv[j] + sq(S[j])) - 2 * S[j] * S[i] + sq(S[i]);
                rev[k][i] = j;
            }
 
            // insert line
            {
                while (deq.size() >= 1) {
                    int t = *deq.rbegin();
                    if (S[t] == S[i]) break;
                    if (deq.size() == 1) {
                        deq.push_back(i);
                        break;
                    }
                    int l = *++deq.rbegin();
 
                    lf i1 = (lf)(prv[l] - prv[t] + sq(S[l]) - sq(S[t])) / (2 * S[l] - 2 * S[t]);
                    lf i2 = (lf)(prv[i] - prv[t] + sq(S[i]) - sq(S[t])) / (2 * S[i] - 2 * S[t]);
 
                    if (i1 > i2) deq.pop_back();
                    else {
                        deq.push_back(i);
                        break;
                    }
                }
            }
        }
    }
 
    printf("%lld\n", (sq(S[N]) - table[K & 1][N]) / 2);
     
    vector<int> rec;
    for (int i = K, j = N; i > 0;) {
        if(i < K) rec.push_back(j);
        j = rev[i--][j];
    }
 
    reverse(rec.begin(), rec.end());
    for (int x : rec) printf("%d ", x);
 
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:45:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &K); ++K;
                          ^
sequence.cpp:47:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x; scanf("%d", &x);
                               ^

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