Submission #1228903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228903		Harold	Bouquet (EGOI24_bouquet)	C++20	0 / 100	3093 ms	3652 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()


int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    
    vector<int> dp1(n), dp2(n);
    dp1[0] = 1;
    dp2[n-1] = 1;
    for (int i = 1; i < n; i++)
    {
        dp1[i] = dp1[i-1];
        for (int j = i-a[i].first-1; j >= 0; j--)
        {
            if(j+a[j].second < i) {
                dp1[i] = max(dp1[i], 1+dp1[j]);
            }
        }
        
        dp2[n-i-1] = dp2[n-i];
        for (int j = n-i+a[n-i-1].second; j < n; j++)
        {
            if(j-a[j].first > n-i-1) {
                dp2[n-i-1] = max(dp2[n-i-1], 1+dp2[j]);
            }
        }
    }

    /*for(auto i: dp1) {
        cout << i << " ";
    }
    cout << endl;

    for(auto i: dp2) {
        cout << i << " ";
    }
    cout << endl;*/

    cout << max(dp1[n-1], dp2[0]) << endl;
    
    return 0;
}

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