Submission #110854

#	Time	Username	Problem	Language	Result	Execution time	Memory
110854		evpipis	Split the sequence (APIO14_sequence)	C++17	0 / 100	127 ms	84040 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<pll> vec;

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

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

void add(pll cur){
    while (vec.size() >= 2 && can(vec[vec.size()-2], vec.back(), cur))
        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], x) > func(vec[pos], x))
        pos++;
    return mp(func(vec[pos], x), vec[pos].fi);
}

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;
        add(mp(0, 0));
        for (int i = 1; i <= n; i++){
            pair<ll, int> ans = query(pref[i]);
            po[i][j] = ans.se;
            add(mp(pref[i], dp[i]-pref[i]*1LL*pref[i]));
            dp[i] = ans.fi;
        }
    }

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

    int cur = n;
    for (int j = k, p = n; j > 1; j--){
        while (pref[p] > po[cur][j])
            p--;
        cur = p;
        printf("%d ", cur);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> query(ll)':
sequence.cpp:33:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos >= vec.size())
         ~~~~^~~~~~~~~~~~~
sequence.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pos+1 < vec.size() && func(vec[pos+1], x) > func(vec[pos], x))
            ~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:43: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:45: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