Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/detail/standard_policies.hpp>
- #define pb push_back
- #define F first
- #define S second
- #define lll long long
- #define lld long double
- using namespace std;
- using namespace __gnu_pbds;
- template <typename T>
- using ordered_set = tree <T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
- mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
- const int N = 1e6 + 11;
- const lll M = 1e9 + 7;
- const lll M2 = 1e9 + 9;
- const int mod = 998244353;
- const int rx[8] = {1, 1, -1, -1, -2, -2, 2, 2};
- const int ry[8] = {-2, 2, -2, 2, 1, -1, 1, -1};
- const lld eps = 1e-7;
- const double pi = acos(-1.0);
- lll a[N];
- lll dp[N];
- int k[N];
- int ans[N];
- lll pref[N];
- lll get(int l, int r) {
- lll ans = pref[r];
- if (l) {
- ans -= pref[l - 1];
- }
- return ans;
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- srand(time(0));
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #endif
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- pref[i] = a[i];
- ans[i] = 1;
- dp[i] = a[i];
- k[i] = 1;
- if (i) {
- dp[i] += dp[i - 1];
- k[i] += k[i - 1];
- pref[i] += pref[i - 1];
- }
- }
- int l, r;
- for (int i = 0; i + 1 < n; ++i) {
- if (dp[i + 1] > dp[i] + a[i + 1]) {
- dp[i + 1] = dp[i] + a[i + 1];
- k[i + 1] = k[i] + 1;
- ans[i + 1] = ans[i];
- }
- l = i + 1;
- r = n - 1;
- while (l + 1 < r) {
- int mid = (l + r) / 2;
- if (get(i + 1, mid) >= dp[i]) {
- r = mid;
- } else {
- l = mid;
- }
- }
- if (get(i + 1, l) < dp[i]) {
- l = r;
- }
- if (get(i + 1, l) >= dp[i]) {
- if (dp[l] > get(i + 1, l)) {
- dp[l] = get(i + 1, l);
- k[l] = l - i;
- ans[l] = ans[i] + 1;
- }
- }
- }
- cout << ans[n - 1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement