제출 #258098

#제출 시각아이디문제언어결과실행 시간메모리
258098aggu_01000101수열 (APIO14_sequence)C++14
71 / 100
626 ms131076 KiB
#include <iostream> #include <assert.h> #include <algorithm> #include <vector> #include <set> #include <string> #include <queue> #include <map> #include <bits/stdc++.h> #define initrand mt19937 mt_rand(time(0)); #define rand mt_rand() #define int long long #define INF 10000000000000000 using namespace std; #define mid(l, u) ((l+u)/2) //#define cin fin //#define cout fout const int N = 100005; const int K = 205; int pref[N]; int n, k; int dp[K][N]; int nxt[K][N]; stack<pair<pair<int, int>, pair<int, int>>> toEval; void f(int currk, int l, int r, int ll, int rr){ //dp(currk, m) = best cost when you want to make currk splits with first split starting at m if(l>r){ return; } int m = mid(l, r); //we want to calculate dp[currk][m] //look at dp[currk-1][max(ll, m+1)] to dp[currk - 1][min(rr, n - currk)]. //The answer for dp[curr-1][x] will be (sum(m to x-1) * sum(x to n)) + dp[curr-1][x] //base case - dp[0][anything] = 0; //cout<<currk<<" "<<m<<" "<<ll<<" "<<rr<<endl; //n - x + 1 >= currk for(int x = max(ll, m+1);x<=min(rr, n - (currk - 1));x++){ int tempans = ((pref[x-1] - pref[m-1]) * (pref[n] - pref[x-1])) + dp[currk - 1][x]; //cout<<"ANS AT "<<x<<" is "<<tempans<<endl; if(tempans >= dp[currk][m]){ nxt[currk][m] = x; dp[currk][m] = tempans; } } //cout<<"dp["<<currk<<"]["<<m<<"] = "<<dp[currk][m]<<endl; toEval.push({{l, m-1}, {ll, nxt[currk][m]}}); toEval.push({{m+1, r}, {nxt[currk][m], rr}}); } signed main(){ //ofstream fin("2.in"); //ofstream fout("2.out"); cin>>n>>k; for(int i = 1;i<=n;i++){ cin>>pref[i]; pref[i] += pref[i-1]; } for(int currk = 1;currk<=k;currk++){ f(currk, 1, n - currk, 1, n); while(toEval.size()){ pair<pair<int, int>, pair<int, int>> curr = toEval.top(); toEval.pop(); f(currk, curr.first.first, curr.first.second, curr.second.first, curr.second.second); } } cout<<dp[k][1]<<endl; int lol = k; int currst = 1; while(lol){ cout<<(nxt[lol][currst] - 1)<<" "; currst = nxt[lol][currst]; lol--; } cout<<endl; } /* 7 3 4 1 3 4 0 2 3 */
#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...