Submission #280269

#TimeUsernameProblemLanguageResultExecution timeMemory
280269HeheheWatching (JOI13_watching)C++14
0 / 100
255 ms512 KiB
#include<bits/stdc++.h> //:3 using namespace std; typedef long long ll; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<int, int> #define sz(x) (int)((x).size()) #define int long long const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const ll inf = 2e9; const ll mod = 1e9 + 7; const int N = 2e4 + 11; const int X = 1e6; const ll INF64 = 3e18 + 1; const double eps = 1e-14; const double PI = acos(-1); //ifstream in(".in"); //ofstream out(".out"); int n, m, a[N], dp[N], S, B; bool ok(int small, int big, int w){ memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; dp[1] = 1; for(int i = 2; i <= n; i++){ for(int j = 1; j <= i; j++){ if(a[i] - a[j] >= w)continue; dp[i] = min(dp[i], dp[j - 1] + 1); } } //cout << "DP" << '\n'; //for(int i = 0; i <= n; i++)cout << dp[i] << ' '; cout << '\n'; int doi = 0; for(int i = 2; i <= n; i++){ for(int j = 1; j < i; j++){ if(dp[i] - dp[j - 1] == 2 && a[i] - a[j] < 2*w){ doi++; break; } } } //cout << "doi = " << doi << '\n'; if(dp[n] - doi*2 <= small)return 1; return 0; } void solve(){ cin >> n >> S >> B; for(int i = 1; i <= n; i++)cin >> a[i]; int l = 0, r = 1e9, ans = 0; while(l <= r){ int mid = (l + r) >> 1; if(ok(S, B, mid)){ ans = mid; r = mid - 1; }else l = mid + 1; } cout << ans << '\n'; } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << setprecision(6) << fixed; int T = 1; //cin >> T; while(T--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...