제출 #628659

#제출 시각아이디문제언어결과실행 시간메모리
628659duytuandao21Bigger segments (IZhO19_segments)C++17
13 / 100
1 ms340 KiB
#include<iostream> #include<cmath> #include<algorithm> #include<stack> #include<vector> using namespace std; #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) #define fi first #define se second #define ll long long #define mp make_pair #define pb push_back #define ii pair<int, int> #define task "test" const int inf = 1e9 + 7; const ll infll = (ll)1e18 + 7; const int MOD = 1e9 + 7; const int N = 2e6 + 3; template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;} template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;} int n; ll a[N], dp[3005][3005], dp1[3005][3005], bit[3005][3005], dp2[3005][3005]; void update(int x,int y,int val) { while(x <= n) { maximize(bit[x][y], val); x += (x & -x); } } ll get(int y,int l,int r) { int ans = -inf; while(l <= r) { if(r - (r & -r) >= l) { maximize(ans, bit[r][y]); r -= (r & -r); } else { maximize(ans, dp1[r][y]); r--; } } return ans; } void sol1() { for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { if(j == 1) { dp1[j][i] = 1; update(j, i, dp1[j][i]); continue; } ll sum = a[i] - a[j-1]; int l = 1; int r = j - 1; int pos = -1; while(l <= r) { int mid = (l + r) / 2; if(a[j-1] - a[mid - 1] <= sum) { pos = mid; r = mid - 1; } else l = mid + 1; } if(pos != -1) { int x = get(j-1, pos, j-1); if(x != 0) dp1[j][i] = x + 1; } if(dp1[j][i] == 0) dp1[j][i] = -inf; update(j, i, dp1[j][i]); } } ll ans = 0; for(int i=1;i<=n;i++) maximize(ans, dp1[i][n]); cout<<ans; } void sol2() { vector<int> f(n+1,0); vector<int> POS(n+1,0); for(int i=1;i<=n;i++) { int l = 1; int r = i; int pos = -1; while(l <= r) { int mid = (l + r) / 2; ll sum = a[i] - a[mid - 1]; //check the value bool ok = false; for(int j=1;j<=POS[mid-1];j++) { ll preSum = a[mid - 1] - a[j-1]; if(preSum <= sum) ok = true; } if(mid == 1) ok = true; if(ok == true) pos = mid, l = mid +1; else r = mid - 1; } if(pos != -1) f[i] = f[pos - 1] + 1; else f[i] = inf; //cout<<pos<<" "; POS[i] = pos; } //for(int i=1;i<=n;i++) cout<<f[i]<<" "; cout<<f[n]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i] += a[i-1]; } sol2(); return 0; } /* 10 4 1 2 4 2 3 5 6 8 10 */
#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...