Submission #867424

#TimeUsernameProblemLanguageResultExecution timeMemory
867424CookieWatching (JOI13_watching)C++14
0 / 100
10 ms64088 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; ifstream fin("nondec.in"); ofstream fout("nondec.out"); #define sz(a) (int)a.size() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> const ld PI = 3.14159265359; //using u128 = __uint128_t; //const int x[4] = {1, -1, 0, 0}; //const int y[4] = {0, 0, 1, -1}; const ll mod = 1e9 + 7; const int mxn = 2e5 + 5, mxq = 2e5 + 5, sq = 500, mxv = 1e7 + 5; const ll inf = 1e9; //const int base= (1 << 18); int n, a, b; ll x[mxn + 1]; pll dp[2005][2005]; void ckmin(pll &a, pll b){ if(b.fi < a.fi)a = b; else if(a.fi == b.fi && b.se > a.se)b.se = a.se; } bool ck(ll mid){ forr(i, 1, n + 1){ forr(j, 0, a + 1){ dp[i][j] = make_pair(inf, 0); } } dp[1][0] = make_pair(1, 2 * mid - 1); dp[1][1] = make_pair(0, mid - 1); for(int i = 1; i < n; i++){ for(int j = 0; j <= a; j++){ if(dp[i][j].first == inf)continue; if(dp[i][j].second >= x[i + 1] - x[i]){ ckmin(dp[i + 1][j], make_pair(dp[i][j].first, dp[i][j].second - (x[i + 1] - x[i]))); }if(j < a){ ckmin(dp[i + 1][j + 1], make_pair(dp[i][j].first, mid - 1)); }ckmin(dp[i + 1][j], make_pair(dp[i][j].first + 1, mid * 2 - 1)); } } for(int i = 0; i <= a; i++){ if(dp[n][i].first <= b)return(1); } return(0); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> a >> b; if(a + b >= n){ cout << 1; return(0); } for(int i = 1; i <= n; i++)cin >> x[i]; sort(x + 1, x + n + 1); ll l = 1, r = 1e9, ans; while(l <= r){ ll mid = (l + r) >> 1; if(ck(mid)){ ans = mid; r = mid - 1; }else{ l = mid + 1; } } cout << ans; return(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...