Submission #1006224

#TimeUsernameProblemLanguageResultExecution timeMemory
1006224andecaandeciBigger segments (IZhO19_segments)C++17
100 / 100
56 ms20620 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") typedef long long ll; const ll INF = 1e18; const ll MOD = 1e9 + 7; const ll MAXN = 1e6 + 5; const ll LOG = 31; #define vll vector <ll> #define pll pair <ll, ll> #define fi first #define se second #define endl '\n' ll n, m, d; ll a [MAXN], pf [MAXN], pos [MAXN], dp [MAXN]; ll lb(ll x){ ll l = 1, r = n, ret = n+1; while(l <= r){ ll mid = (l+r)/2; if(pf[mid] >= x){ ret = mid; r = mid - 1; } else{ l = mid + 1; } } return ret; } void solve(){ cin >> n; for(ll i = 1; i <= n; i++){ cin >> a[i]; pf[i] = pf[i-1] + a[i]; } for(ll i = 1; i <= n; i++){ pos[i] = max(pos[i], pos[i-1]); dp[i] = dp[pos[i]] + 1; pos[lb(2*pf[i]-pf[pos[i]])] = i; } cout << dp[n] << endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // ll t; cin >> t; // while(t--){ solve(); // } }
#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...