Submission #1317556

#TimeUsernameProblemLanguageResultExecution timeMemory
1317556haithamcoderBouquet (EGOI24_bouquet)C++20
28 / 100
3093 ms14308 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll B = 2305843009213693951;

#define f first
#define s second

#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

int main() {
    Algerian OI

    // freopen("s.in", "r", stdin);
    // freopen("correct.txt", "w", stdout);

    ll n;
    cin >> n;
    vector<pll> a(n + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> a[i].f >> a[i].s;
        a[i].f = min(a[i].f, i - 1);
        a[i].s = min(a[i].s, n - i);
    }

    vector<vector<ll>> dp(n + 1, vector<ll>(2));

    for (ll i = 1; i <= n; i++) {
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
        for (ll j = 0; j < i - a[i].f; j++) {
            if (j + a[j].s < i) dp[i][1] = max(dp[i][1], dp[j][1] + 1);
        }
    }

    cout << max(dp[n][0], dp[n][1]) << "\n";

    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...