제출 #48489

#제출 시각아이디문제언어결과실행 시간메모리
48489zadrga수열 (APIO14_sequence)C++14
50 / 100
410 ms10720 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][maxn], 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++){ // cout << "dp " << i << " "<< j << ": \n"; // cout << dp[i][j] << endl; for(int z = 1; z < i; z++){ // cout << "vrednost " << z <<": " <<sum(i + 1, n) << " " << (sum(1, i) - sum(1, z)) << " " <<dp[z][j - 1] << endl; if(dp[i][j] < sum(i + 1, n) * (sum(1, i) - sum(1, z)) + dp[z][j - 1]){ // cout << dp[i][j] << " " << z << endl; dp[i][j] = sum(i + 1, n) * (sum(1, i) - sum(1, z)) + dp[z][j - 1]; from[i][j] = z; } } // cout << dp[i][j] << endl << endl; } } /* for(int i = 0; i <= k; i++){ for(int j = 0; j <= n; j++) printf("%d ", from[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...