제출 #545655

#제출 시각아이디문제언어결과실행 시간메모리
545655balbitFeast (NOI19_feast)C++14
0 / 100
118 ms14296 KiB
#include <bits/stdc++.h> #define int ll using namespace std; #define ll long long #define f first #define s second #define pii pair<ll, ll> #define MX(a,b) a=max(a,b) #define MN(a,b) a=min(a,b) #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(), (x).end() #define REP(i,n) for (int i = 0; i<n; ++i) #define REP1(i,n) for (int i = 1; i<=n; ++i) #define pb push_back #ifdef BALBIT #define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__) template<typename T> void _do( T && x) {cerr<<x<<endl;} template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);} #else #define bug(...) #define endl '\n' #endif // BALBIT const int maxn = 3e5+5; const ll inf = 1ll<<61; ll A[maxn]; pii dp[maxn][2]; int n; pair<ll, ll> operator + (pair<ll, ll> a, pair<ll, ll> b) { return {a.f + b.f, a.s + b.s}; } pair<ll, ll> get(int p) { // beware of initial states!! dp[0][0] = {0, 0}; // no value, nothing taken yet dp[0][1] = {-inf, -inf}; REP1(i,n) { dp[i][0] = dp[i][1] = {-inf, inf}; MX(dp[i][0], dp[i-1][0]); // continue not taking anything MX(dp[i][0], dp[i-1][0] + make_pair(p, -1)); // take an empty segment (?) MX(dp[i][0], dp[i-1][1]); // stop taking stuff MX(dp[i][1], dp[i-1][0] + make_pair(-p + A[i], -1)); MX(dp[i][1], dp[i-1][1] + make_pair(-p + A[i], -1)); MX(dp[i][1], dp[i-1][1] + make_pair(A[i], 0)); } return max(dp[n][0], dp[n][1]); } inline ll DIV(ll a, ll b) { return a/b - ((a%b) && ((a^b)<0)); } signed main(){ ios::sync_with_stdio(0), cin.tie(0); bug(1,2); int k; cin>>n>>k; REP1(i,n) { cin>>A[i]; } ll l = 0, r = 2e9+10; while (l!=r) { ll md = DIV((l+r),2); pair<ll, ll> gt = get(md); if (-gt.s > k) { // taking too many zones, gotta make the penalty higher l = md+1; }else{ r = md; } } pair<ll, ll> gt = get(l); // only linear difference from it bug(l, gt.f, -gt.s); ll re = gt.f + (k) * (l); cout<<re<<endl; }
#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...