Submission #37902

#	Time	Username	Problem	Language	Result	Execution time	Memory
37902		MatheusLealV	Split the sequence (APIO14_sequence)	C++14	33 / 100	23 ms	86100 KiB

sequence

#include <bits/stdc++.h>
#define f first
#define s second
#define N 100005
#define K 202
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
 
int r, e, n, k, prox[N][K], ID[N];

bool block[N];

ll A[N],B[N], dp[3][N], sum[N];

vector<pair<pii, int> > line;

void fastscan(int &number)
{
    register int c;
 
    number = 0;
 
    c = getchar();
 
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
}
 
void fast_ll(ll &number)
{
    register int c;
 
    number = 0;
 
    c = getchar();
 
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48; 
}
 

void addline(pair<pii, int> l)
{
    A[e] = l.f.f, B[e] = l.f.s, ID[e] = l.s;

    while(r + 1 < e && (B[e-1] - B[e-2]) * (A[e] - A[e-1]) <= (A[e-2] - A[e-1])* (B[e-1] - B[e])) A[e-1] = A[e], B[e-1] = B[e], ID[e-1] = ID[e], e--;

    e++;
}

pii query(ll x)
{
    while(r + 1 < e && B[r + 1] - B[r] >= x * (A[r] - A[r + 1])) r++;

    return pii(A[r]*x + B[r],ID[r]);
}

void print()
{
    vector<int> res;

    int pos2 = n;

    for(int pos1 = k; pos1; pos1--) res.push_back(prox[pos1][pos2]), pos2 = prox[pos1][pos2]; 

    while (!res.empty())  printf("%d ",res.back()), res.pop_back();
}
 
int32_t main()
{
    scanf("%d %d",&n,&k);

    for(int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];

    for(int i = 0; i <= n; i++) dp[0][i] = 0;

    int A = 0, B = 1;
     
    for(int q = 0; q <= k; q++)
    {
        r = e = 0;

        addline(make_pair(pii(0, 0), 0));

        for (int i = 1; i <= n; i++)
        {
            pii x = query(sum[i]);

            prox[q][i] = x.s;

            dp[A][i] = x.f + sum[i]*(sum[n] - sum[i]);

            addline(make_pair(pii(sum[i], dp[B][i] - sum[n]*sum[i]), i));
        }

        swap(A, B);
    }

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

    print();

    printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int32_t main()':
sequence.cpp:72:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&k);
                         ^
sequence.cpp:74:77: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%lld", &sum[i]), sum[i] += sum[i - 1];
                                                                             ^

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