제출 #76845

#제출 시각아이디문제언어결과실행 시간메모리
76845samuelfgs96수열 (APIO14_sequence)C++11
0 / 100
335 ms83668 KiB
#include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define eb emplace_back using namespace std; typedef pair<int, int> pii; typedef long long ll; const int N = 100002; int n, k; ll a[N], sum[N], dp[2][N]; ll cost (int l, int r) { return (sum[r+1] - sum[l]) * (sum[n] - sum[r+1]); } int nxt[210][N]; int prv, at; void solve (int lo, int hi, int opt_beg, int opt_end, int k) { if (lo > hi) return ; int mid = (lo + hi) / 2; int opt = -1; for (int i = max(mid, opt_beg); i <= opt_end; i++) { ll tmp = dp[prv][i+1] + cost(mid, i); if (dp[at][mid] < tmp) { dp[at][mid] = tmp; opt = i; } } nxt[k][mid] = opt; solve(lo, mid-1, opt_beg, opt, k); solve(mid+1, hi, opt, opt_end, k); } int main (void) { scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { scanf("%lld", a + i); sum[i+1] = sum[i] + a[i]; } memset (dp, -1, sizeof dp); for (int i = 0; i < n; i++) dp[0][i] = 0; at = 1; for (int i = 1; i <= k; i++) { solve(0, n-1, 0, n-1, i); swap (prv, at); } cout << dp[prv][0] << endl; vector <int> path; int x = k, y = 0; while (x) { path.pb(nxt[x][y]); y = nxt[x][y] + 1; x--; } for (auto u : path) cout << u + 1 << " "; cout << endl; return 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:38: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:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", 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...