제출 #48483

#제출 시각아이디문제언어결과실행 시간메모리
48483zadrga수열 (APIO14_sequence)C++14
0 / 100
276 ms1536 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define INF (1LL << 55) #define MOD (1000 * 1000 * 1000 + 7) #define maxn 1111 #define maxk 211 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; ll dp[maxn][2], pre[maxn], arr[maxn]; int from[maxn][maxk]; ll sum(int i, int j){ if(i > j) return 0LL; return pre[j] - pre[i - 1]; } int main(){ int n, k; scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++){ scanf("%lld", arr + i); pre[i] = pre[i - 1] + arr[i]; } for(int i = 0; i <= n; i++){ for(int j = 0; j <= k; j++) dp[i][j] = -INF; } for(int i = 1; i <= n - 1; i++) dp[i][1] = sum(1, i) * sum(i + 1, n); for(int j = 2; j <= k; j++){ for(int i = j; i <= n - 1; i++){ for(int z = 0; z < i; z++){ if(dp[i][j] < sum(i + 1, n) * (sum(1, i) - sum(1, z)) + dp[z][j - 1]){ dp[i][j] = sum(i + 1, n) * (sum(1, i) - sum(1, z)) + dp[z][j - 1]; from[i][j] = z; } } } } /* for(int i = 0; i <= k; i++){ for(int j = 0; j <= n; j++) printf("%lld ", dp[j][i]); printf("\n"); } */ int ans = 0; for(int i = 1; i <= n - 1; i++){ if(dp[i][k] > dp[ans][k]) ans = i; } printf("%lld\n", dp[ans][k]); for(int i = k; i >= 1; i--){ printf("%d ", ans); ans = from[ans][i]; } return 0; }

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

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