Submission #37905

#	Time	Username	Problem	Language	Result	Execution time	Memory
37905		MatheusLealV	Split the sequence (APIO14_sequence)	C++14	100 / 100	613 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[K][N], 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: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29