Submission #240684

#TimeUsernameProblemLanguageResultExecution timeMemory
240684WhaleVomitSplit the sequence (APIO14_sequence)C++14
39 / 100
2090 ms72932 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define mp make_pair #define all(v) v.begin(), v.end() #define sz(v) (int)v.size() #define MOO(i, a, b) for(int i=a; i<b; i++) #define M00(i, a) for(int i=0; i<a; i++) #define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--) #define M00d(i,a) for(int i = (a)-1; i>=0; i--) #define FAST ios::sync_with_stdio(0); cin.tie(0); #define finish(x) return cout << x << '\n', 0; #define dbg(x) cerr << ">>> " << #x << " = " << x << "\n"; #define _ << " _ " << typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef pair<int,int> pi; typedef pair<ld,ld> pd; typedef complex<ld> cd; const int MAX_N = 100100; const int MAX_K = 202; int n, k; const ll inf = 1e17; ll arr[MAX_N]; ll psum[MAX_N]; ll dp[MAX_N][MAX_K]; int lastsplit[MAX_N][MAX_K]; int main() { FAST cin >> n >> k; for(int i = 1; i <= n; i++) { cin >> arr[i]; psum[i] = psum[i-1] + arr[i]; } for(int j = 1; j <= k; j++) { for(int i = 1; i <= n; i++) { dp[i][j] = -inf; for(int ip = 0; ip <= i-1; ip++) { ll val = dp[ip][j-1] + (psum[i]-psum[ip])*(psum[n]-psum[i]); if(val > dp[i][j]) { dp[i][j] = val; lastsplit[i][j] = ip; } } } } int besIdx = 1; for(int i = 1; i <= n; i++) { if(dp[i][k] > dp[besIdx][k]) { besIdx = i; } } ll mx = dp[besIdx][k]; vi v; int cur = k; while(cur != 0) { v.pb(besIdx); besIdx = lastsplit[besIdx][cur]; cur--; } cout << mx << "\n"; M00(i, k) { if(i != 0) cout << " "; cout << v[i]; } cout << "\n"; }
#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...