제출 #64284

#제출 시각아이디문제언어결과실행 시간메모리
64284kingpig9수열 (APIO14_sequence)C++11
0 / 100
240 ms132096 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXK = 210; const int MAXN = 1e5 + 10; #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[MAXK][MAXN]; //minimum of sum of squares. ll P[MAXN]; void rec (int id, 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]) + dp[id - 1][i]; if (dp[id][mid] > val) { dp[id][mid] = val; oi = i; } } assert(oi != -1); rec(id, lt, mid - 1, olt, oi); rec(id, 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]; } fillchar(dp, 63); dp[0][0] = 0; for (int i = 1; i <= K; i++) { rec(i, i, N, i - 1, N - 1); } printf("%lld\n", (sqr(P[N]) - dp[K][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...