제출 #32105

#제출 시각아이디문제언어결과실행 시간메모리
32105minimario수열 (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); } 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++; 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) { 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 {(ll)l.f * (ll)x + l.s, ind}; } int a[MAX]; ll p[MAX]; ll dp[MAX][2]; int last[205][MAX]; 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) { dp[i][k%2] = -eval(p[i]).f; last[k][i] = (int)eval(p[i]).s; } } } } k0++; printf("%lld\n", dp[n][k0%2]); while (k0 != 1) { int bef = last[k0][n]; printf("%d ", bef); n = bef; k0--; } }

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sequence.cpp: In function 'int main()':
sequence.cpp:58: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:60: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...