제출 #64288

#제출 시각아이디문제언어결과실행 시간메모리
64288kingpig9수열 (APIO14_sequence)C++11
0 / 100
38 ms2872 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5 + 10; const ll INF = LLONG_MAX / 3; #define debug(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second #define all(v) (v).begin(), (v).end() #define fillchar(a, s) memset((a), (s), sizeof(a)) inline ll sqr (ll x) { return x * x; } int N, K; ll dp[2][MAXN]; //minimum of sum of squares. ll P[MAXN]; void rec (ll *cdp, ll *pdp, int lt, int rt, int olt, int ort) { if (lt > rt) { return; } int mid = (lt + rt) / 2; int oi = -1; for (int i = olt; i <= ort && i < mid; i++) { ll val = sqr(P[mid] - P[i]) + pdp[i]; if (cdp[mid] > val) { cdp[mid] = val; oi = i; } } assert(oi != -1); rec(cdp, pdp, lt, mid - 1, olt, oi); rec(cdp, pdp, mid + 1, rt, oi, ort); } int main() { scanf("%d %d", &N, &K); K++; for (int i = 1; i <= N; i++) { scanf("%lld", &P[i]); P[i] += P[i - 1]; } for (int i = 0; i < 2; i++) { for (int j = 0; j <= N; j++) { dp[i][j] = INF; } } int cur = 0, prv = 1; dp[cur][0] = 0; for (int i = 1; i <= K; i++) { swap(cur, prv); for (int j = 0; j <= N; j++) { dp[cur][j] = INF; } rec(dp[cur], dp[prv], i, N, i - 1, N - 1); } printf("%lld\n", (sqr(P[N]) - dp[cur][N]) / 2); }

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

sequence.cpp: In function 'int main()':
sequence.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &P[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...