제출 #1091319

#제출 시각아이디문제언어결과실행 시간메모리
1091319kasdoBouquet (EGOI24_bouquet)C++14
24 / 100
26 ms12124 KiB
#include "bits/stdc++.h" using namespace std; #define int long long #define endl '\n' #define speed cin.tie (0) -> sync_with_stdio (0);ios_base::sync_with_stdio(false);cin.tie(0); const int maxn = 200005; int n; int l[maxn], r[maxn]; int dp[maxn]; int rec(int i, int p) { if (i <= 0) return 0; if (dp[i] != -1) return dp[i]; int ret = max(rec(i - 1, i), rec(i - l[i] - 1, i) + 1); return dp[i] = ret; } int rec2(int i) { if (i <= 0) return 0; if (dp[i] != -1) return dp[i]; int ret = 1; for(int j=1; j<i; j++) { int good = (j + r[j] < i && i - l[i] > j); ret = max(ret, rec2(j) + good); } return dp[i] = ret; } void s1() { for(int i=1; i<=maxn-5; i++) dp[i] = -1; cout<<rec(n, 0)<<endl; } void s2() { cout<<(n - 1) / (l[1] + 1) + 1<<endl; } void s3() { for(int i=1; i<=maxn-5; i++) dp[i] = -1; cout<<rec2(n)<<endl; } void solve() { cin>>n; bool ok = 1; for(int i=1; i<=n; i++) { cin>>l[i]>>r[i]; ok &= (l[i] == r[i]); ok &= (l[i] == l[1]); } if (n <= 1000) s3(); else if (ok) s2(); else s1(); } signed main () { speed // freopen("feast.in", "r", stdin); // freopen("feast.out", "w", stdout); int _ = 1; // cin>>_; while(_--) solve(); 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...