# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
971471 | 2024-04-28T15:18:11 Z | CyberCow | The short shank; Redemption (BOI21_prison) | C++17 | 2000 ms | 524292 KB |
#include <random> #include <algorithm> #include <bitset> #include <chrono> #include <cmath> #include <deque> #include <fstream> #include <iomanip> #include <iostream> #include <iterator> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> #include <chrono> #define m_p make_pair #define all(x) (x).begin(),(x).end() #define sz(x) ((x).size()) typedef long long ll; using ull = unsigned long long; using namespace std; mt19937 rnd(348502); ll mod1 = 998244353; ll mod = 1e9 + 7; const ll N = 510; int a[N]; int dp[N][N][N]; int hm[N][N][N]; void solve() { int n, d, k, t; cin >> n >> d >> t; for (int i = 1; i <= n; i++) { cin >> a[i]; } int oo = 2e9; hm[0][0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= d; j++) { for (int h = 0; h <= n; h++) { if (hm[i - 1][j][h] == 0)continue; if (a[i] > t) { dp[i][j + 1][h] = oo; hm[i][j + 1][h] = 1; } if (a[i] <= t || (dp[i - 1][j][h] + 1 <= t)) { dp[i][j][h + 1] = max(dp[i][j][h + 1], min(dp[i - 1][j][h] + 1, a[i])); hm[i][j][h + 1] = 1; } else { dp[i][j][h] = oo; hm[i][j][h] = 1; } } } } int ans = 1e9; for (int i = 0; i <= d; i++) { for (int j = 0; j <= n; j++) { if (hm[n][i][j]) ans = min(ans, j); } } cout << ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt = 1; //cin >> tt; while (tt--) { solve(); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 604 KB | Output is correct |
2 | Correct | 10 ms | 22108 KB | Output is correct |
3 | Correct | 17 ms | 36952 KB | Output is correct |
4 | Correct | 47 ms | 95348 KB | Output is correct |
5 | Incorrect | 81 ms | 168532 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Execution timed out | 2935 ms | 524292 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 604 KB | Output is correct |
2 | Correct | 10 ms | 22108 KB | Output is correct |
3 | Correct | 17 ms | 36952 KB | Output is correct |
4 | Correct | 47 ms | 95348 KB | Output is correct |
5 | Incorrect | 81 ms | 168532 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Runtime error | 686 ms | 381944 KB | Execution killed with signal 11 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 604 KB | Output is correct |
2 | Correct | 10 ms | 22108 KB | Output is correct |
3 | Correct | 17 ms | 36952 KB | Output is correct |
4 | Correct | 47 ms | 95348 KB | Output is correct |
5 | Incorrect | 81 ms | 168532 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 604 KB | Output is correct |
2 | Correct | 10 ms | 22108 KB | Output is correct |
3 | Correct | 17 ms | 36952 KB | Output is correct |
4 | Correct | 47 ms | 95348 KB | Output is correct |
5 | Incorrect | 81 ms | 168532 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |