제출 #344371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
344371		Redhood	Bigger segments (IZhO19_segments)	C++14	100 / 100	142 ms	47724 KiB

segments

#include<bits/stdc++.h>

#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define pb push_back
#define len(x) (int)(x).size()


using namespace std;

typedef long long ll;
typedef long double ld;

#define int long long
signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n;
    cin >> n;
    vector < int > a(n);
    for(auto &i : a)
        cin >> i;
    vector < ll > pref(n + 1);
    for(int i = 0; i < n; ++i){
        pref[i + 1] = pref[i] + a[i];
    }


    vector < pair < int , int > > dp(n + 1 , {0 , 0});
    dp[0] = {0 , 0};


    vector < vector < int > > add(n + 2);

    pair < int , int > cur = {0 , 0};
    for(int i = 0; i <= n; ++i){
        /// lulz
        /// calc dp
        if(i != 0){
            for(auto u : add[i])
                if(cur.fi < dp[u].fi + 1)
                    cur.fi = dp[u].fi + 1 , cur.se = u;
                else if(cur.fi == dp[u].fi + 1)
                    cur.se = max(cur.se , u);
            dp[i] = {cur.fi , pref[i] - pref[cur.se]};
        }
        int frst = lower_bound(all(pref) , pref[i]+dp[i].se) - pref.begin();
        frst = max(frst , i + 1);
        add[frst].pb(i);
    }
//    cout << " DP \n";
//    for(int i = 0; i <= n; ++i){
//        cout << dp[i].fi << ' ' << dp[i].se << '\n';
//    }
    cout << dp[n].fi << '\n';
    return 0;
}

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