제출 #1342629

#제출 시각아이디문제언어결과실행 시간메모리
1342629iamhereforfunBigger segments (IZhO19_segments)C++20
37 / 100
1592 ms3140 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 5e5 + 5;
const int M = 1e6 + 5;
const int K = 20;
const int LG = 20;
const long long INF = 1e18 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;

int n, a[N];
long long pref[N];

namespace subtask3
{
    inline void solve()
    {
        pair<int, long long> dp[n + 1];
        dp[0] = {0, 0};
        for (int x = 0; x < n; x++)
        {
            auto [b, v] = dp[x];
            for (int y = 1; y <= n; y++)
            {
                if (pref[y] - pref[x] >= -v)
                {
                    dp[y] = max(dp[y], {b + 1, -(pref[y] - pref[x])});
                }
            }
        }
        cout << dp[n].first << "\n";
    }
};

inline void solve()
{
    cin >> n;
    pref[0] = 0;
    for (int x = 1; x <= n; x++)
    {
        cin >> a[x];
        pref[x] = pref[x - 1] + a[x];
    }
    subtask3::solve();
}

signed main()
{
    // freopen("CP.INP", "r", stdin);
    // freopen("CP.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#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...