Submission #1228910

#TimeUsernameProblemLanguageResultExecution timeMemory
1228910pumkinheadBouquet (EGOI24_bouquet)C++20
16 / 100
17 ms1996 KiB
#include <bits/stdc++.h> using namespace std; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); int n; cin>>n; vector<int> tulips(n, INT_MAX); for(int i=0; i<n; i++){ int l, r; cin>>l>>r; l = min(l, i); r = min(r, n-1-i); int newPos = i+r; int rangeExcluded = l+r; tulips[newPos] = min(rangeExcluded, tulips[newPos]); } vector<int> dp(n, 0); auto queryDp = [&](int pos){ if(pos < 0) return -1; if(pos == 0) return 0; return dp[pos-1]; }; dp[0] = queryDp(-tulips[0]) + 1; for(int i=1; i<n; i++){ dp[i] = dp[i-1]; dp[i] = max(dp[i], queryDp(i - tulips[i]) + 1); } cout<<dp[n-1]; }
#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...