Submission #409474

#TimeUsernameProblemLanguageResultExecution timeMemory
409474gmyuFeast (NOI19_feast)C++14
100 / 100
182 ms10380 KiB
/* ID: USACO_template LANG: C++ PROG: http://web.pdf.com/~pdfastest/fae/pdFT_Overview/pdft.html */ #include <iostream> //cin , cout #include <fstream> //fin, fout #include <stdio.h> // scanf , pringf #include <cstdio> #include <algorithm> // sort , stuff #include <stack> // stacks #include <queue> // queues #include <map> #include <string> #include <string.h> #include <set> using namespace std; typedef pair<int, int> pii; typedef vector<int> vi; /// adjlist without weight typedef vector<pii> vii; /// adjlist with weight typedef vector<pair<int,pii>> vpip; /// edge with weight typedef long long ll; #define mp make_pair #define ff first #define ss second #define pb push_back #define sz(x) (int)(x).size() #define adjread {int a, b; cin >> a >> b; adjlist[a].pb(b); adjlist[b].pb(a); } const int MOD = 1e9+7; // 998244353; const int MX = 2e5+5; // const ll INF = 1e18; // #define MAXV 300007 #define MAXE 100007 const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions struct NODE { int x, y; int val; int visited; bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); } }; struct EDGE { int from, to; ll weight; bool operator<(EDGE other) const { return weight < other.weight; } }; bool debug; int N, K; ll ps[MAXV]; /** * dp[i] = max (1 <=j <= j' <=i) { dp[j] + ps[i] - ps[j'] } = max { dp[j] - ps[j'] } + ps[i] * instead of doing O(N^2) DP, we use proximation * for each step, dp[i] = previous best { dp[j] - ps[j] } + ps[i] - err, where err is the proximation to optimal dp * and update previous best { } if dp[i]-ps[i] is better */ pair<ll, ll> dp[MAXV]; pair<ll, ll> canDo(ll err) { pair<ll, ll> bestDP = mp(0LL, 0LL); dp[0] = bestDP; for(int i=1; i<=N; i++) { dp[i] = mp(bestDP.ff + ps[i] - err, bestDP.ss + 1LL); dp[i] = max(dp[i], dp[i-1]); if(dp[i].ff - ps[i] > bestDP.ff) { bestDP = mp(dp[i].ff - ps[i], dp[i].ss); } else if(dp[i].ff - ps[i] == bestDP.ff && bestDP.ss > dp[i].ss) { bestDP = mp(dp[i].ff - ps[i], dp[i].ss); } } return dp[N]; } int main() { debug = false; ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> K; for(int i = 1; i <=N; i++) { ll a; cin >> a; ps[i] = ps[i-1] + a; } ll lo = 0LL, hi = INF; while(lo < hi) { if(debug) cout << "walk " << lo << " " << hi << endl; ll mid = (lo + hi) / 2LL; auto ans = canDo(mid); if(ans.ss <= K) { hi = mid; } else { lo = mid + 1; } } auto ans = canDo(hi); cout << ans.ff + (ll)K * hi << endl; } /** 6 1 1 -2 3 -1 5 -6 6 2 1 2 3 -10 5 6 */
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...