Submission #732156

#	Time	Username	Problem	Language	Result	Execution time	Memory
732156		anha3k25cvp	Split the sequence (APIO14_sequence)	C++14	100 / 100	1097 ms	93256 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>

using namespace std;

const int N = 5 + 1e5;
const int inf = 7 + 1e9;

struct Line {
    ll a, b;
};

int m;
vector <Line> L;
vector <int> s;
vector <dl> x;
vector <ll> a, p, q;
vector <vector <ll>> f;
vector <vector <int>> tr;

bool check(int i) {
    int u = s[m];
    if (L[i].a == L[u].a)
        return false;
    if (m == 1)
        return true;
    int v = s[m - 1];
    dl xm = (dl)(L[u].b - L[i].b) / (L[i].a - L[u].a),
       xn = (dl)(L[v].b - L[i].b) / (L[i].a - L[v].a);
    return xn < xm;
}

void trace(int i, int k) {
    if (k == 0)
        return;
    trace(tr[i][k], k - 1);
    cout << i << ' ';
}

int main() {
#define TASKNAME "sequence"
    ios_base::sync_with_stdio (0);
    cin.tie (0);
    if ( fopen( TASKNAME".inp", "r" ) ) {
        freopen (TASKNAME".inp", "r", stdin);
        freopen (TASKNAME".out", "w", stdout);
    }
    int n, k;
    cin >> n >> k;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    f.assign(n + 1, vector <ll> (2, 0));
    for (int i = 1; i < n; i ++)
        f[i][1] = a[i] * (a[n] - a[i]);
    tr.assign(n + 1, vector <int> (k + 1, 0));
    x.assign(n + 1, 0);
    p.assign(n + 1, 0);
    q.assign(n + 1, 0);
    s.assign(n + 1, 0);
    L.resize(n + 1);
    for (int time = 2; time <= k; time ++) {
        for (int i = 0; i <= n; i ++) {
            f[i][0] = f[i][1];
            f[i][1] = 0;
        }
        m = 0;
//        cout << time << '\n';
        for (int i = 1; i < n; i ++) {
//            cout << "i = " << i << " :\n";
            if (m > 0) {
                int u = upper_bound(x.begin(), x.begin() + m + 1, a[i] - a[n]) - x.begin() - 1;
//                cout << u << ' ' << s[u + 1] << ' ' << s[u] << '\n';
                f[i][1] = (a[n] - a[i]) * a[i] + p[u] * (a[i] - a[n]) + q[u];
                tr[i][time] = s[u + 1];
            }
//            cout << f[i][1] << '\n';
            L[i] = {a[i], f[i][0]};
            while (m > 0 && !check(i))
                m --;
            s[++ m] = i;
            if (m == 1) {
                x[0] = -inf; p[0] = L[s[1]].a; q[0] = L[s[1]].b;
                x[1] = inf;
            }
            else {
                x[m - 1] = (dl)(L[s[m]].b - L[s[m - 1]].b) / (L[s[m - 1]].a - L[s[m]].a);
                p[m - 1] = L[s[m]].a; q[m - 1] = L[s[m]].b;
                x[m] = inf;
            }
        }
//        cout << '\n';
    }
    ll ans = -1;
    int pos = 0;
    for (int i = 1; i < n; i ++)
        if (f[i][1] > ans) {
            ans = f[i][1];
            pos = i;
        }
    cout << ans << '\n';
    trace(pos, k);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:50:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen (TASKNAME".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:51:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen (TASKNAME".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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