Submission #1167416

#TimeUsernameProblemLanguageResultExecution timeMemory
1167416uranhishigBouquet (EGOI24_bouquet)C++17
8 / 100
59 ms8008 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define all(a) (a).begin(),(a).end() #define rep(i, n) for(int i = 0; i < (n); i++) #define rep1(i, n) for(int i = 1; i <= (n); i++) const int mx = 2e5 + 9; bool b1 = true; bool b2 = true; bool b4 = true; int a[mx]; int s[mx]; void build(int i, int L, int R) { if (L == R) { s[i] = a[L]; return; } int M = (L + R) / 2; int x = 2 * i + 1, y = x + 1; build(x, L, M); build(y, M + 1, R); s[i] = max(s[x], s[y]); } void update(int i, int L, int R, int k, int v) { if (L == R) { a[k] = v; s[i] = v; return; } int M = (L + R) / 2; int x = 2 * i + 1, y = x + 1; if (k <= M) update(x, L, M, k, v); else update(y, M + 1, R, k, v); s[i] = max(s[x], s[y]); return; } int query(int i, int L, int R, int l, int r) { if (L == l && r == R) { return s[i]; } int M = (L + R) / 2; int x = 2 * i + 1, y = x + 1; if (r <= M) return query(x, L, M, l, r); else if (M + 1 <= l) return query(y, M + 1, R, l, r); else return max(query(x, L, M, l, M) , query(y, M + 1, R, M + 1, r)); } signed main() { int n; cin >> n; vector<int> l(n); vector<int> r(n); cin >> l[0] >> r[0]; int w; if(l[0] != r[0]) { b1 = false; } if(l[0] == r[0]) { w = l[0]; } if (r[0] != 0) { b2 = false; } if (r[0] > 2) b4 = false; if (l[0] > 2) b4 = false; for (int i = 1; i < n; i++) { cin >> l[i] >> r[i]; if (r[i] != 0) { b2 = false; } if (l[i] != r[i]) { b1 = false; } if(l[i] != w) { b1 = false; } if (r[i] > 2) { b4 = false; } if (l[i] > 2) { b4 = false; } } int dp[n + 1]; for (int i = 0; i <= n; i++) { dp[i] = 0; } int ans = 0; //subtask 1 if (b1) { cout << (w + n)/(w + 1); return 0; } // subtask 2 if (b2) { for (int i = 0; i < n; i++) { if (i - l[i] < 0) dp[i] = 0; else if (i - l[i] == 0) dp[i] = 1; else dp[i] = query(0, 0, n - 1, 0, i - l[i] - 1) + 1; if (dp[i] > 0) update(0, 0, n - 1, i, dp[i]); ans = max(ans, dp[i]); } cout << ans << endl; return 0; } //subtask 3 if (n <= 1000) { for (int i = 1; i < n; i++) { for (int j = 0; j < i - l[i]; j++) { if (r[j] < i - j) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(dp[i], ans); } cout << ans << endl; return 0; } //subtask 4 if (b4) { for (int i = 1; i < n; i++) { for (int j = max(0ll, i - l[i] - 10) ; j < i - l[i]; j++) { if (r[j] < i - j) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(dp[i], ans); } cout << ans << endl; return 0; } //subtask 5 cout << ans << endl; 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...