Submission #1167266

#TimeUsernameProblemLanguageResultExecution timeMemory
1167266Muhammet수열 (APIO14_sequence)C++17
50 / 100
2096 ms32580 KiB
#include "bits/stdc++.h" using namespace std; #define ll long long #define SZ(s) (ll)s.size() int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector <ll> a(n+1), p(n+1, 0); for(int i = 1; i <= n; i++) { cin >> a[i]; p[i] = p[i-1] + a[i]; } vector <vector <ll>> dp(n + 1, vector <ll> (k + 1, 0)), par(n + 1, vector <ll> (k + 1, 0)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= k; j++) { par[i][j] = i-1; } } for(int i = 1; i <= n; i++) { for(int j = i-1; j >= 0; j--) { for(int k1 = 0; k1 < k; k1++) { ll x = (p[i] - p[j]) * p[j] + dp[j][k1]; if(x > dp[i][k1+1]) { dp[i][k1+1] = x; par[i][k1+1] = j; } // dp[i][k1+1] = max(dp[i][k1+1], ); } } } cout << dp[n][k] << '\n'; int y = n; while(y) { y = par[y][k]; if(y == 0) break; k--; cout << y << ' '; } return 0; }
#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...