제출 #770747

#제출 시각아이디문제언어결과실행 시간메모리
770747OrazB수열 (APIO14_sequence)C++17
33 / 100
2085 ms67084 KiB
#include <bits/stdc++.h> using namespace std; #define wr cout << "Continue debugging\n"; #define all(x) (x).begin(), (x).end() #define ll long long int #define pii pair <int, int> #define pb push_back #define ff first #define ss second #define pv pair<ll,vector<int>> const int N = 1005; const int MAXN = 1e5+7; const ll INF = 1e18; int n, k, a[MAXN]; ll pref[MAXN]; pv dp[N][N]; int main () { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++){ cin >> a[i]; pref[i] = pref[i-1]+a[i]; } for (int i = 2; i <= n; i++){ for (int x = 1; x <= k; x++){ // int l = 1, r = i-1; // while(l <= r){ // int md = (l+r)/2; // pv X = dp[md][x-1]; // X.ss.pb(md); // dp[i][x] = max(dp[i][x], {X.ff+(pref[i]-pref[md])*pref[md], X.ss}); // if (pref[md]*pref[md]>dp[md][x-1].ff) r=md-1; // else l=md+1; // } for (int j = 1; j < i; j++){ pv X = dp[j][x-1]; X.ss.pb(j); dp[i][x] = max(dp[i][x], {X.ff+(pref[i]-pref[j])*pref[j], X.ss}); } } } assert(dp[n][k].ff<=pref[n]*pref[n]); cout << dp[n][k].ff << '\n'; for (auto i : dp[n][k].ss) cout << 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...