This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
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 100007
#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++) {
int a; cin >> a;
ps[i] = ps[i-1] + a;
}
ll lo = 0, hi = INF;
while(lo < hi) {
if(debug) cout << "walk " << lo << " " << hi << endl;
ll mid = (lo + hi) /2;
auto ans = canDo(mid);
if(ans.ss <= K) {
hi = mid;
} else {
lo = mid + 1;
}
}
auto ans = canDo(hi);
cout << ans.ff + K * hi << endl;
}
/**
6 1
1 -2 3 -1 5 -6
6 2
1 2 3 -10 5 6
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |