제출 #810287

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
810287		tosivanmak	Bigger segments (IZhO19_segments)	C++17	0 / 100	1 ms	212 KiB

segments

#include<bits/stdc++.h>
using namespace std;
#define ll long long



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n;
    cin>>n;
    ll arr[n+5],dp[n+5],psum[n+5];
    psum[0]=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        psum[i]=psum[i-1]+arr[i];
        dp[i]=0;
    }
    // psum[i]-psum[j]>=maxi
    // psum[i]>=maxi+psum[j]
    
    set<vector<ll> >st;vector<ll>dummy;
    dummy.push_back(0);
    dummy.push_back(0);
    dummy.push_back(0);
    st.insert(dummy);
    for(int i=1;i<=n;i++){
            ll ck=-psum[i];
            vector<ll>v;
             v.push_back(ck);
        v.push_back(-1e18);
        v.push_back(-1e18);
            vector<ll> get=*st.lower_bound(v);
            dp[i]=-get[1]+1;
            vector<ll>v2;
            // cout<<get[2]<<"\n";
            // cout<<get[0]<<" "<<get[1]<<" "<<get[2]<<"\n";
            v2.push_back(-(psum[i]+psum[i]-psum[get[2]]));
            v2.push_back(-dp[i]);
            v2.push_back(i);
            st.insert(v2);
        
    }
    cout<<dp[n]<<"\n";
}

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