제출 #1160385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160385		uropeltidae	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	528 KiB

segments

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long
#define st first
#define nd second
#define pb push_back
#define love our_kolhoz
#define watch(x) (cout << #x << " == " << x << '\n')

///azyraq oila

using namespace std;

const int N = 2e5 + 10, inf = 1e18, mod = 1e9 + 7, block = 350;
const double eps = 1e-6;

//qol batyr

int a[N], used[N], res[N];
int n;

int ans(int i, int p) {

    if (i > n)
        return 0;

    if (i == n) {
        return (a[i] >= p ? 1 : -1);
    }

    if (used[i]) {
        return res[i];
    }

    int sum = 0, kek = -1;
    for (int j = i; j <= n; j++) {
        sum += a[j];
        if (sum >= p) {
            kek = max(kek, ans(j + 1, sum));
        }
    }

    used[i] = 1;
    res[i] = (kek == -1 ? 0 : kek + 1);

    return (kek == -1 ? 0 : kek + 1);

}

void solve() {

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

    int kek = 0, sum = 0;

    for (int i = 1; i <= n; i++) {

        sum += a[i];
        kek = max(kek, ans(i + 1, sum));

        //cout << ans(i + 1, sum) << '\n';

    }

    cout << kek + 1;

}

signed main() {

    speed;

    //freopen("248.in", "r", stdin);
    //freopen("248.out", "w", stdout);

    int _t = 1;
    //cin >> _t;
    while (_t--) {
        solve();
    }

    return 0;

}
// salem
// there's really no way of winning
// if in their eyes you'll always be a dumb blonde...

///meow meow

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