Submission #203800

#TimeUsernameProblemLanguageResultExecution timeMemory
203800EntityITSparklers (JOI17_sparklers)C++14
50 / 100
169 ms262148 KiB
#include<bits/stdc++.h> using namespace std; #define all(x) (x).begin(), (x).end() #define sz(x) ( (int)(x).size() ) using LL = long long; template<class T> inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; } template<class T> inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; } mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() ); int n, k, t; vector<int> x; bool check(int s) { vector<vector<bool> > f(n, vector<bool>(n, false) ); f[k][k] = true; for (int diff = 0; diff < n; ++diff) { for (int i = 0, j = diff; j < n; ++i, ++j) if (f[i][j]) { if (i && (x[j] - x[i - 1] + t - 1) / t <= 2LL * s * (j - i + 1) ) f[i - 1][j] = true; if (j + 1 < n && (x[j + 1] - x[i] + t - 1) / t <= 2LL * s * (j - i + 1) ) f[i][j + 1] = true; } } return f[0][n - 1]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef FourLeafClover freopen("input", "r", stdin); #endif // FourLeafCLover cin >> n >> k >> t; --k; x.assign(n, 0); for (auto &i : x) cin >> i; int l = 0, r = x.back(); while (l < r) { int mid = (l + r) >> 1; if (check(mid) ) r = mid; else l = mid + 1; } cout << l << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...