Submission #1186863

#TimeUsernameProblemLanguageResultExecution timeMemory
1186863PieArmyBigger segments (IZhO19_segments)C++20
100 / 100
45 ms8264 KiB
#include<bits/stdc++.h> typedef long long ll; #define pb push_back #define fr first #define sc second #define endl '\n' using namespace std; int n; ll arr[500023]; int dp[500023],las[500023]; int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; arr[i]+=arr[i-1]; dp[i]=1; } for(int i=1;i<n;i++){ int l=i+1,r=n+1; while(l<r){ int m=(l+r)/2; if(arr[m]+arr[las[i]]>=arr[i]*2)r=m; else l=m+1; } if(l!=n+1){ las[l]=i; dp[l]=dp[i]+1; } if(las[i+1]<las[i]){ las[i+1]=las[i]; dp[i+1]=dp[i]; } } cout<<dp[n]; }
#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...