# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
971532 | 2024-04-28T18:53:59 Z | CyberCow | The short shank; Redemption (BOI21_prison) | C++17 | 53 ms | 15700 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 = 500010; int a[N], lr[N]; int han[N]; int ans[N]; void solve() { int n, d, k, t; cin >> n >> d >> t; for (int i = 1; i <= n; i++) { cin >> a[i]; if (a[i] <= t) lr[i] = min(t - a[i] + i, n); } stack<pair<int, int>> se; int obshi = 0; for (int i = 1; i <= n; i++) { se.push({ i, lr[i] }); while (!se.empty() && se.top().second < i) { se.pop(); } if (!se.empty()) { han[i] = se.top().first; ans[se.top().first]++; obshi++; } } int ma = 0; for (int i = 1; i <= n; i++) { ma = max(ma, ans[i]); } cout << obshi - ma + 1; } 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 | 6488 KB | Output is correct |
2 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 6492 KB | Output is correct |
2 | Correct | 48 ms | 14932 KB | Output is correct |
3 | Correct | 53 ms | 15700 KB | Output is correct |
4 | Incorrect | 42 ms | 13228 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6488 KB | Output is correct |
2 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 6488 KB | Output is correct |
2 | Incorrect | 8 ms | 7496 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6488 KB | Output is correct |
2 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6488 KB | Output is correct |
2 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |