Submission #1221533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221533		gry3125	Bouquet (EGOI24_bouquet)	C++20	28 / 100	3124 ms	738304 KiB

Main

#include <bits/stdc++.h>
#define f0r(i,n) for(int i=0;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef long long int ll; 
using namespace std;

vector< pair<pair<int,int>,int> > v;
map<int,vector<int>> e;
map<int,int> dep; int mx = 0;

void dfs(int u) {
    for (auto v : e[u]) {
        if (dep[v] < dep[u]+1) {
            dep[v] = dep[u]+1;
            dfs(v);
        }
    }
}

int main() {
    int n; cin >> n; v.resize(n);
    for (int i = 0; i < n; i++) {
        int L, R; cin >> L >> R;
        L = max(0, i-L); R = min(n-1, i+R);
        v[i] = {{R, L}, i};
    }
    sort(all(v));
    for (int i = 0; i < n; i++) {
        int L1 = v[i].fi.se, R1 = v[i].fi.fi, F1 = v[i].se;
        for (int j = i+1; j < n; j++) {
            int L2 = v[j].fi.se, R2 = v[j].fi.fi, F2 = v[j].se;
            if (L1 <= F2 && F2 < F1) continue;
            if (F1 < F2 && F2 <= R1) continue;
            if (L2 <= F1 && F1 < F2) continue;
            if (F2 < F1 && F1 <= R2) continue;
            e[i].push_back(j);
        }
    }
    for (int i = 0; i < n; i++) {
        if (dep[i]) continue;
        dep[i] = 1; dfs(i);
    }
    for (int i = 0;i < n; i++) mx = max(mx, dep[i]);
    cout << mx;
    return 0;
}

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