| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1362433 | avahw | Bouquet (EGOI24_bouquet) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int n;
map<pair<int, int>, int> memo;
int solve(int i, int last_picked_ind, vector<pair<int, int>>& ranges){
// check if we can pick this one
if(i >= n) return 0;
int l = ranges[i].first; int r = ranges[i].second;
if(memo.find({i, last_picked_ind}) != memo.end()) return memo[{i, last_picked_ind}];
if(last_picked_ind >= i - l) return solve(i + 1, last_picked_ind, ranges);
// pick or dont pick
int pick = 1 + solve(i + r + 1, i, ranges);
int dont = solve(i + 1, last_picked_ind, ranges);
memo[{i, last_picked_ind}] = max(pick, dont);
return max(pick, dont);
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n;
vector<pair<int, int>> tulips(n);
for(int i = 0; i < n; i++){
cin >> tulips[i].first >> tulips[i].second;
}
cout << (n / (l + 1 )) + min(1, n % (l + 1)) << "\n";
}