Submission #394788

#	Time	Username	Problem	Language	Result	Execution time	Memory
394788		Anand	Split the sequence (APIO14_sequence)	C++14	0 / 100	17 ms	3792 KiB

sequence

#include <bits/stdc++.h>

int q[100010] , p[210][100010];
long long a[100010] , D[100010] , E[100010];
using namespace std;


void path(int k , int n)
{
    if (k < 0) return;
    path(k - 1 , p[k][n]);
    cout << n << " ";
}
int main()
{
    int n , k , f , r;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) scanf("%lld",a+i) , a[i] += a[i-1] , D[i] = -a[i] * a[i];
    for (int i = 1; i <= k; i++)
    {
        q[f = r = 1] = i;

        for (int j = i + 1; j <= n; j++)
        {
            while (f < r && a[q[f]] * a[j] + D[q[f]] <= a[q[f+1]] * a[j] + D[q[f+1]])
            f++;
            E[j] = a[q[f]] * a[j] + D[q[f]] - a[j] * a[j]; p[i][j] = q[f];
            while (f < r && (D[q[r]] - D[q[r-1]]) * (a[q[r-1]] - a[j]) >= (D[j] - D[q[r-1]]) * (a[q[r-1]] - a[q[r]]))
            r--;
            q[r++]=j;
        }
        for(int j = i + 1; j <= n; j++) D[j] = E[j];
    }
    printf("%lld\n",D[n]+a[n]*a[n]);

    path(k-1,p[k][n]);
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:19:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |     for (int i = 1; i <= n; i++) scanf("%lld",a+i) , a[i] += a[i-1] , D[i] = -a[i] * a[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