Submission #1317556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317556		haithamcoder	Bouquet (EGOI24_bouquet)	C++20	28 / 100	3093 ms	14308 KiB

Main

#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;
}

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