Submission #1030117

#TimeUsernameProblemLanguageResultExecution timeMemory
1030117vjudge1The short shank; Redemption (BOI21_prison)C++17
0 / 100
105 ms87376 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") #define endl '\n' #define db double #define ll __int128 #define int long long #define pb push_back #define fs first #define sd second #define Mod long(1e9 + 7) #define all(x) x.begin(), x.end() #define unvisited long(-1) #define Eps double(1e-9) #define _for(i, n) for(int i = 0; i < (n); i++) #define dbg(x) cout << #x ": " << x << endl; const int Max = 1e6 + 7, Inf = 1e9 + 7; void print(bool x) { cout << (x ? "YES" : "NO") << endl; } string tostring (__int128 x) { string ans = ""; while(x > 0) { ans += (x % 10 + '0'); x /= 10; } reverse(all(ans)); return ans; } void solve() { int n, d, t; cin >> n >> d >> t; vector <int> v(n), s(n+1); for(auto& u : v) cin >> u; int ans = 0, sum = 0; for(int i = 0; i < n; i++) { if(v[i] < t){ s[i]++; if(t - v[i] + i + 1 <= n) s[t - v[i] + i + 1]--; } sum += s[i]; s[i] = (sum != 0); } vector <vector<vector<int>>> dp(n+1, vector <vector<int>> (d+1, vector<int> ({ 0, -Inf }))); for(int i = 1; i <= n; i++){ for(int j = 0; j <= d; j++){ dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]); if(v[i-1] > t){ dp[i][j][1] = max(dp[i-1][j][1], ((j-s[i-1])>= 0 ? dp[i-1][j-s[i-1]][0] : -Inf)) + 1; } //cerr << i << " " << j << " " << dp[i][j][0] << " " << dp[i][j][1] << endl; ans = max(ans, max(dp[i][j][0], dp[i][j][1])); } } cout << n-ans << endl; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int Q = 1; //cin >> Q; while (Q--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...