Submission #31968

#TimeUsernameProblemLanguageResultExecution timeMemory
31968minimarioSplit the sequence (APIO14_sequence)C++14
0 / 100
2000 ms34608 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int MAX = 10005; typedef pair<int, int> 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); } void add(int m, int b, int k) { pii l = {m, b}; // l and line[2] > hit[2] while (ct > 1 && sect(l, line[ct]) < hit[ct]) { ct--; } ct++; orig[ct] = k; line[ct] = l; if (ct != 1) { hit[ct] = sect(l, line[ct-1]); } } pii eval(int x) { pii l; int ind = -1; if (ct == 0) { return {0, 0}; } if (ct == 1) { l = line[1]; ind = orig[1]; } else { l = line[lower_bound(hit+2, hit+ct+1, (double)x) - hit - 1]; ind = orig[lower_bound(hit+2, hit+ct+1, (double)x) - hit - 1]; } return {l.f * x + l.s, ind}; } int a[MAX]; int p[MAX]; int dp[MAX][205]; int last[MAX][205]; int map2[MAX]; main() { //freopen("a.in", "r", stdin); //freopen("a.out", "w", stdout); int n, k; scanf("%lld %lld", &n, &k); int cur = 1; for (int i=1; i<=n; i++) { scanf("%lld", &a[cur]); if (a[cur] != 0) { map2[cur++] = i; } } cur--; for (int i=1; i<=cur; i++) { p[i] = p[i-1] + a[i]; } for (int k=1; k<=n; k++) { ct = 0; for (int i=k-1; i<=n; i++) { if (k == 1) { dp[i][k] = 0; } else { add(-p[i], -dp[i][k-1]+p[i]*p[i], i); if (i != k-1) { dp[i][k] = -eval(p[i]).f; last[i][k] = eval(p[i]).s; } } } } k++; printf("%lld\n", dp[cur][min(cur, k)]); while (k != 1) { int bef = last[n][k]; printf("%lld ", map2[bef]); n = bef; k--; } }

Compilation message (stderr)

sequence.cpp:56:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sequence.cpp: In function 'int main()':
sequence.cpp:59:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, k; scanf("%lld %lld", &n, &k);
                                      ^
sequence.cpp:62:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[cur]);
                         ^
#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...