Submission #917132

#TimeUsernameProblemLanguageResultExecution timeMemory
917132allvikSparklers (JOI17_sparklers)C++17
0 / 100
1 ms2396 KiB
#include <iostream> #include <vector> using namespace std; #define int long long const int MAXN = 5000; int dp[MAXN][MAXN]; int t; bool check(int n, int k, vector <int>& a, int s) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { dp[i][j] = 0; } } dp[k][k] = 1; for (int len = 1; len <= n; ++len) { for (int l = 0; l + len - 1 < n; ++l) { int r = l + len - 1; if (dp[l][r] == 0) continue; if (r < n - 1 && (a[r + 1] - a[l]) <= (r - l + 1) * t * 2 * s) dp[l][r + 1] = 1; if (l && (a[r] - a[l - 1]) <= (r - l + 1) * t * 2 * s) dp[l - 1][r] = 1; } } return dp[0][n - 1]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, k; cin >> n >> k >> t; vector <int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; if (a[n - 1] == a[0]) { cout << 0; return 0; } int l = 0; int r = a.back() - a[0]; while (r - l > 1) { int m = (l + r) / 2; if (check(n, k, a, m)) r = m; else l = m; } cout << r; return 0; } /* 3 2 50 0 200 300 3 2 10 0 200 300 20 6 1 0 2 13 27 35 46 63 74 80 88 100 101 109 110 119 138 139 154 172 192 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...