Submission #31976

#TimeUsernameProblemLanguageResultExecution timeMemory
31976minimarioSplit the sequence (APIO14_sequence)C++14
71 / 100
2000 ms87568 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 100005; typedef long long ll; typedef pair<ll, ll> pii; #define f first #define s second pii line[MAX]; int orig[MAX]; double hit[MAX]; int ct = 0; double sect(pii l1, pii l2) { // l1.f * x + l1.s = l2.f * x + l2.s return (double)(l2.s - l1.s) / (double)(l1.f - l2.f); } int ptr = 1; void add(ll m, ll b, int k) { pii l = {m, b}; // l and line[2] > hit[2] while (ct > 1) { if (l.f != line[ct].f && sect(l, line[ct]) > hit[ct]) { break; } ct--; } ct++; ptr = min(ptr, ct); orig[ct] = k; line[ct] = l; if (ct != 1) { hit[ct] = sect(l, line[ct-1]); } } pii eval(ll x) { pii l; int ind = -1; if (ct == 0) { return {0, 0}; } if (ct == 1) { ptr = 1; l = line[1]; ind = orig[1]; } else { while (hit[ptr] < x && ptr <= ct) { ptr++; } ptr--; l = line[ptr]; ind = orig[ptr]; } return {(ll)l.f * (ll)x + (ll)l.s, ind}; } int a[MAX]; ll p[MAX]; ll dp[MAX][2]; int last[MAX][205]; int main() { //freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); int n, k0; scanf("%d %d", &n, &k0); for (int i=1; i<=n; i++) { scanf("%d", &a[i]); p[i] = (ll)p[i-1] + (ll)a[i]; } for (int k=1; k<=k0+1; k++) { ct = 0; for (int i=k-1; i<=n; i++) { if (k == 1) { dp[i][k] = 0; } else { add(-p[i], -(ll)dp[i][(k+1)%2]+(ll)p[i]*(ll)p[i], i); if (i != k-1) { pii ans = eval(p[i]); dp[i][k%2] = -ans.f; last[i][k] = (int)ans.s; } } } } k0++; printf("%lld\n", dp[n][k0%2]); while (k0 != 1) { int bef = last[n][k0]; printf("%d ", bef); n = bef; k0--; } }

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:65:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k0; scanf("%d %d", &n, &k0);
                                    ^
sequence.cpp:67:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]); 
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...