Submission #1175262

#TimeUsernameProblemLanguageResultExecution timeMemory
1175262pandaa73Bouquet (EGOI24_bouquet)C++20
28 / 100
3095 ms2632 KiB
#include <bits/stdc++.h>
using namespace std;

#define lf "\n"
#define ff endl
#define _ << ' ' <<
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)

#define infos(str) do { fprintf(stderr, str"\n"); } while(0)
#define infor(str, ...) do { fprintf(stderr, str, __VA_ARGS__); } while(0)
#define infof(str, ...) do { fprintf(stderr, str"\n", __VA_ARGS__); } while(0)

#ifndef DEBUG

#undef infos
#undef infor
#undef infof

#define infos(str)
#define infor(str, ...)
#define infof(str, ...)

#endif

using ll = long long;

constexpr int LOG = 20;
constexpr int MOD = 1e9+7;
constexpr int MAXN = 1e5+7;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin >> N;
    vector<array<int, 2>> V(N);
    for(int i = 0; i < N; ++i) {
        auto &[l, r] = V[i];

        cin >> l >> r;

        l = max(0, i - l);
        r = min(i + r, N);
    }

    int ans = 1;
    vector<int> dp(N, 1);
    for(int i = 0; i < N; ++i) {
        for(int j = V[i][1] + 1; j < N; ++j) {
            if(V[j][0] <= i) continue;

            dp[j] = max(dp[j], 1 + dp[i]);
        } 

        ans = max(ans, dp[i]);
    }

    cout << ans << lf;
}
#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...