Submission #684102

#TimeUsernameProblemLanguageResultExecution timeMemory
684102GudStonksBigger segments (IZhO19_segments)C++17
100 / 100
88 ms20860 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long ll n, arr[500005]; pair<ll, ll>dp[500005]; void fun(){ cin>>n; vector<ll>pr(n); for(int i = 1; i <= n; i++){ cin>>arr[i]; if(i > 1) pr[i - 1] = pr[i - 2]; pr[i - 1] += arr[i]; } dp[1] = {1, -arr[1]}; for(int i = 1; i <= n; i++){ dp[i] = max(dp[i], {dp[i - 1].first, -(-dp[i - 1].second + arr[i])}); ll next = lower_bound(pr.begin(), pr.end(), pr[i - 1] + (-dp[i].second)) - pr.begin() + 1; if(next > n)continue; dp[next] = max(dp[next], {dp[i].first + 1, -(pr[next - 1] - pr[i - 1])}); } cout<<dp[n].first; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int ttt = 1; //cin>>ttt; while(ttt--)fun(); }
#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...