Submission #501798

#	Time	Username	Problem	Language	Result	Execution time	Memory
501798		dxz05	Bigger segments (IZhO19_segments)	C++14	37 / 100	15 ms	3220 KiB

segments

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define MP make_pair

pair<int, ll> dp[3001];

void chmax(pair<int, ll> &x, pair<int, ll> y){
    if (x.first < y.first || x.first == y.first && x.second > y.second) x = y;
}

int a[500005];
ll pref[500005];

ll sum(int l, int r){
    return pref[r] - pref[l - 1];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n;
    cin >> n;

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

    dp[0] = MP(0, 0ll);
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < i; j++){
            if (sum(j + 1, i) >= dp[j].second) chmax(dp[i], MP(dp[j].first + 1, sum(j + 1, i)));
        }
//        cout << dp[i].first << ' ' << dp[i].second << endl;
    }

    cout << dp[n].first;

    return 0;
}

Compilation message (stderr)

segments.cpp: In function 'void chmax(std::pair<int, long long int>&, std::pair<int, long long int>)':
segments.cpp:12:49: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   12 |     if (x.first < y.first || x.first == y.first && x.second > y.second) x = y;
      |                              ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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