Submission #1139213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139213		AHOKA	Bigger segments (IZhO19_segments)	C++20	100 / 100	72 ms	23968 KiB

segments

#pragma GCC optimize("O3") 

#include <bits/stdc++.h>

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define double long double
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) / 2)
#define lc (2 * id)
#define rc (lc + 1)

const int maxn = 1e6 + 10, maxm = 1e3 + 10, oo = 1e18 + 10, lg = 8, sq = 350, mod = 1e9 + 7;

int n, a[maxn], ps[maxn], dp[2][maxn], ans;

// dp[0][i] -> len
// dp[1][i] -> sum

signed main()
{
	threesum;
    cin >> n;
    for (int i = 1; i <= n;i++)
        cin >> a[i];

    for (int i = 1; i <= n;i++)
        ps[i] = ps[i - 1] + a[i];

    vector<pii> stk;

    for (int i = 1; i <= n; i++){
        
        int l = -1, r = stk.size();
        while(r - l > 1){
            if(stk[mid].F <= ps[i])
                l = mid;
            else
                r = mid;
        }

        if(l == -1){
            dp[0][i] = 1;
            dp[1][i] = ps[i];
        }
        else{
            dp[0][i] = dp[0][stk[l].S] + 1;
            dp[1][i] = ps[i] - ps[stk[l].S];
        }

        while(stk.size() && stk.back().F >= dp[1][i] + ps[i])
            stk.pop_back();

        stk.push_back({dp[1][i] + ps[i], i});
    }

    cout << dp[0][n];
}
/*
10
3 14 2 1 23 14 23 15 17 13
*/

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 36 / 36
• Subtask 5: 27 / 27