Submission #1220673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220673		overwatch9	Bouquet (EGOI24_bouquet)	C++20	16 / 100	58 ms	7416 KiB

Main

#include <bits/stdc++.h>
using namespace std;
bool comp(pair <int, int> a, pair <int, int> b) {
    return a.second < b.second;
}
int main() {
    int n;
    cin >> n;
    vector <pair <int, int>> nums(n*3);
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        nums[i].first = max(1, i - l);
        nums[i].second = min(n, i + r);
    }
    sort(nums.begin()+1, nums.begin() + n + 1, comp);
    vector <int> dp(n*3);
    int p = 1;
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i-1];
        while (p <= n && nums[p].second == i) {
            dp[i] = max(dp[i], dp[nums[p].first-1] + 1);
            p++;
        }
    }
    cout << dp[n] << '\n';
}

• Subtask 1: 0 / 8
• Subtask 2: 16 / 16
• Subtask 3: 0 / 28
• Subtask 4: 0 / 18
• Subtask 5: 0 / 30