Submission #110859

#	Time	Username	Problem	Language	Result	Execution time	Memory
110859		evpipis	Split the sequence (APIO14_sequence)	C++17	0 / 100	2071 ms	85384 KiB

sequence

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

#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const ll inf = 1e18;
const int len = 1e5+5;
int arr[len], pos, pref[len], po[len][205];
ll dp[len];
vector<pair<pll, int> > vec;

ll func(pll line, ll x){
    return line.fi*x+line.se;
}

bool can(pll a, pll b, pll c){
    if (b.fi == c.fi)
        return (b.se <= c.se);
    return ((double)(a.se-b.se)/(double)(b.fi-a.fi) >= (double)(b.se-c.se)/(double)(c.fi-b.fi));
}

void add(pair<pll, int> cur){
    while (vec.size() >= 2 && can(vec[vec.size()-2].fi, vec.back().fi, cur.fi))
        vec.pop_back();
    vec.pb(cur);
}

pair<ll, int> query(ll x){
    if (pos >= vec.size())
        pos = vec.size()-1;

    while (pos+1 < vec.size() && func(vec[pos+1].fi, x) > func(vec[pos].fi, x))
        pos++;
    return mp(func(vec[pos].fi, x), vec[pos].se);
}

int main(){
    int n, k;
    scanf("%d %d", &n, &k), k++;
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);

    for (int i = 1; i <= n; i++)
        pref[i] = pref[i-1]+arr[i];

    for (int i = 1; i <= n; i++)
        dp[i] = -inf;
    for (int j = 1; j <= k; j++){
        vec.clear();
        pos = 0;
        if (j == 1)
            add(mp(mp(0, 0), 0));
        else
            add(mp(mp(0, -inf), 0));
        for (int i = 1; i <= n; i++){
            pair<ll, int> ans = query(pref[i]);
            po[i][j] = ans.se;
            add(mp(mp(pref[i], dp[i]-pref[i]*1LL*pref[i]), i));
            dp[i] = max(-inf, ans.fi);
        }
    }

    printf("%lld\n", dp[n]);

    int cur = n;
    for (int j = k; j > 1; j--){
        cur = po[cur][j];
        printf("%d ", cur);
    }
    printf("\n");
    return 0;
}
/*
7 3
4 1 3 4 0 2 3
*/

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> query(ll)':
sequence.cpp:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos >= vec.size())
         ~~~~^~~~~~~~~~~~~
sequence.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pos+1 < vec.size() && func(vec[pos+1].fi, x) > func(vec[pos].fi, x))
            ~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:45:27: 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:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~

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