Submission #41953

#TimeUsernameProblemLanguageResultExecution timeMemory
41953Aidyn_ASplit the sequence (APIO14_sequence)C++14
28 / 100
2037 ms3168 KiB
#include <stdio.h> #include <bits/stdc++.h> #define pb push_back #define pf push_front #define pp pop_back #define sz(a) (int)(a.size()) #define mp make_pair #define F first #define S second #define next _next #define prev _prev #define left _left #define right _right #define y1 _y1 #define all(x) x.begin(), x.end() #define what_is(x) #x << " is " << (x) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int N = (int)1e4 + 2; const ll INF = (ll)1e18 + 123; const int inf = (int)1e9 + 123; const int MOD = (int)1e9 + 7; void megaRandom() { unsigned int FOR; asm("rdtsc" : "=A"(FOR)); srand(FOR); } int n, k; int a[N]; ll now[N], prev[N]; int pref[N]; pii pr[202][N]; int main() { megaRandom(); cin >> n >> k; for(int i = 1; i <= n; i ++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } prev[0] = 0; for(int it = 1; it <= k; it ++) { memset(now, 0, sizeof now); for(int i = 1; i <= n; i ++) { for(int j = 0; j < i; j ++) { ll val = prev[j] + 1ll * pref[j] * (pref[i] - pref[j]); if(val > now[i]) { now[i] = val; pr[it][i] = mp(it - 1, j); } } } for(int i = 1; i <= n; i ++) prev[i] = now[i]; } cout << prev[n] << "\n"; int x = k, y = n; vector<int> g; while(x > 0) { g.pb(pr[x][y].S); pii to = pr[x][y]; x = to.F, y = to.S; } reverse(all(g)); for(int i = 0; i < sz(g); i ++) cout << g[i] << ' '; 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...