Submission #1175267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175267		pandaa73	Bouquet (EGOI24_bouquet)	C++20	0 / 100	3095 ms	2780 KiB

Main

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

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

    int ans = 1;
    vector<int> dp(N + 1, 1);
    for(int i = 0; i < N; ++i) {
        ans = max(ans, dp[i]);
        dp[nxt[i]] = max(dp[nxt[i]], dp[i] + 1); 
    }

    cout << ans << lf;
}

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