Submission #701650

#	Time	Username	Problem	Language	Result	Execution time	Memory
701650		jennierubyjane	Bigger segments (IZhO19_segments)	C++14	37 / 100	54 ms	28064 KiB

segments

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, b) for (int i = 0, _b = (b); i < _b; i++)
#define ii pair<int, int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1LL)
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define next ____next
#define prev ____prev
#define left ____left
#define right ___right
#define lcm ___lcm
#define index ____index
using namespace std;

template<class M> M myabs(M x) {
        return x < 0 ? -x : x;
}
template<class M1, class M2> bool minimize(M1 &x, const M2 &y) {
        if (x > y) {x = y; return true;} return false;
}
template<class M1, class M2> bool maximize(M1 &x, const M2 &y) {
        if (x < y) {x = y; return true;} return false;
}

const int INF = (int)1e9 + 7;
const ll INFLL = (ll)1e18 + 7LL;

const int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

mt19937 rd(time(0));
/**
ii = pair<int, int>
FOR(i, a, b): a, b == int
**/

#define MAX 100100

int n, a[MAX];
ll pref[MAX];

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

int f[3030][3030];
void sub1() {
        FOR(i, 1, n) {
            int j = i - 1;
            int suff_max = i == 1 ? 0 : -INF;
            FOR(k, i, n) {
                while (j >= 1 && sum(j, i - 1) <= sum(i, k)) {
                    maximize(suff_max, f[j][i - 1]);
                    j--;
                }
                f[i][k] = suff_max + 1;
            }
        }
        int res = 0;
        FOR(i, 1, n) maximize(res, f[i][n]);
        cout << res;
}

void solve() {
        cin >> n;
        FOR(i, 1, n) cin >> a[i];

//        FOR(i, 1, n) a[i] = 1 + (rd() % (10));
//        FOR(i, 1, n) cout << a[i] << " "; cout << "\n";

        FOR(i, 1, n) pref[i] = pref[i - 1] + a[i];
        if (n <= 3000) {sub1(); return;}
        //sub1(); cout << " ";
        int ans = 0;
        FOR(i, 1, n) {
            ll cur = pref[i];
            for (int l = 1, j = i; ; l++) {
                j = lower_bound(pref + 1, pref + 1 + n, cur + pref[j]) - pref;
                maximize(ans, l);
                if (j > n) break;
                cur = pref[j] - cur;
            } //cout << "\n";
        }
        cout << ans;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        
        int t = 1; //cin >> t;
        while (t--) solve();
}

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