Submission #628242

#TimeUsernameProblemLanguageResultExecution timeMemory
628242duytuandao21Bigger segments (IZhO19_segments)C++17
37 / 100
761 ms93120 KiB
#include<iostream> #include<cmath> #include<algorithm> #include<stack> 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]; 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]; //for(int k=1;k<j;k++) { //ll preSum = a[j-1] - a[k-1]; //if(preSum <= sum) maximize(dp[j][i], dp[k][j-1] + 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; } //cout<<j<<" "<<i<<" "<<pos<<'\n'; if(pos != -1) { int x = get(j-1, pos, j-1); if(x != 0) dp1[j][i] = x + 1; } // if(pos != -1) dp1[j][i] = get(j-1, pos, j-1) + 1; // maximize(dp1[j][i], 0); 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; } 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]; } // for(int i=1;i<=n;i++) { // for(int j=1;j<=i;j++) { // if(j == 1) { // dp[j][i] = 1; // continue; // } // ll sum = a[i] - a[j-1]; // for(int k=j-1;k>0;k--) { // ll preSum = a[j-1] - a[k-1]; // if(preSum <= sum) maximize(dp[j][i], dp[k][j-1] + 1); else break; // } // if(dp[j][i] == 0) dp[j][i] = -inf; // } // } // ll res = 0; // for(int i=1;i<=n;i++) maximize(res, dp[i][n]); // cout<<res; sol1(); 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...