제출 #1048552

#제출 시각아이디문제언어결과실행 시간메모리
1048552manhlinh1501수열 (APIO14_sequence)C++17
0 / 100
21 ms131072 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using i64 = long long; const int MAXN = 1e5 + 5; const int MAXK = 205; #define ALL(a) (a).begin(), (a).end() int N, K; int a[MAXN]; i64 prefix[MAXN]; namespace subtask { i64 dp[MAXN][MAXK]; pii trace[MAXN][MAXK]; void solution() { K++; memset(dp, -0x3f, sizeof dp); dp[0][0] = 0; for(int i = 1; i <= N; i++) { for(int j = 1; j <= i; j++) { for(int z = 1; z <= K; z++) // dp[i][z] = max(dp[i][z], dp[j - 1][z - 1] + (prefix[i] - prefix[j - 1]) * (prefix[N] - prefix[i])); if(dp[i][z] < dp[j - 1][z - 1] + (prefix[i] - prefix[j - 1]) * (prefix[N] - prefix[i])) { dp[i][z] = dp[j - 1][z - 1] + (prefix[i] - prefix[j - 1]) * (prefix[N] - prefix[i]); trace[i][z] = {j - 1, z - 1}; } } } // for(int i = 1; i <= N; i++) { // for(int j = 1; j <= K; j++) // printf("%d %d %d %d\n", i, j, trace[i][j].first, trace[i][j].second); // } // for(int i = 1; i <= N; i++) { // for(int j = 1; j <= K; j++) // printf("%d %d %d\n", i, j, dp[i][j]); // } i64 best = 0; pii cur = {N, K}; for(int j = 1; j <= K; j++) { if(best < dp[N][j]) { best = dp[N][j]; cur = {N, j}; } } printf("%lld\n", best); while(--K > 1) { cur = trace[cur.first][cur.second]; printf("%d ", cur.first); } } } signed main() { #define TASK "code" if (fopen(TASK ".inp", "r")) { freopen(TASK ".inp", "r", stdin); freopen(TASK ".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> K; for(int i = 1; i <= N; i++) cin >> a[i]; for(int i = 1; i <= N; i++) prefix[i] = prefix[i - 1] + a[i]; subtask::solution(); return (0 ^ 0); }

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

sequence.cpp: In function 'int main()':
sequence.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:60:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...