제출 #1336320

#제출 시각아이디문제언어결과실행 시간메모리
1336320aaaaaaaaBigger segments (IZhO19_segments)C++20
37 / 100
1595 ms3396 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int inf = 2e18;


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, ans = 1;
    cin >> n;

    vector<int> a(n + 1, 0), pref(n + 5, 0);
    vector<pair<int, int>> dp(n + 5, {0, inf});

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }

    dp[0] = {0, 0};

    for(int i = 1; i <= n; ++i){
        for(int j = i; j >= 1; --j){
            if(pref[i] - pref[j - 1] >= dp[j - 1].second  && dp[i].first < dp[j - 1].first + 1){
                dp[i] = {dp[j - 1].first + 1, pref[i] - pref[j - 1]};
            }
        }
    }


    cout << dp[n].first << "\n";


    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...