Submission #1006099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006099		andecaandeci	Bigger segments (IZhO19_segments)	C++17	0 / 100	0 ms	344 KiB

segments

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'

template <typename T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>; 

const ll MOD = 1e9 + 7;
const ll INF = 1e18;

ll n, m, d, s, a[500005];
ll sum = 0;

bool cek2(ll mid, ll cnt){
    ll lst = -1, sum1 = 0, ans = 0;
    for(int i = 1; i <= n; i++){
        sum1 += a[i];
        if(sum1 >= mid){
            ans++;
            if(sum1 < lst) return false;
            lst = sum1;
            sum1 = 0;
        }
    }
    
    return ans >= cnt;
}

bool cek(ll mid1){
    ll l = 1, r = sum, ans = -1;
    while(l <= r){
        ll mid = (l + r) / 2;
        //if(mid1 == 2) cout << mid << endl;
        if(cek2(mid, mid1)){
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
        
    return ans != -1;    
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll t = 1;
    //cin >> t;
    
    while(t--){
        cin >> n;
        
        for(int i = 1; i <= n; sum += a[i], i++) cin >> a[i];
        
        ll l = 1, r = n, ans = 1;
        while(l <= r){
            ll mid = (l + r) / 2;
            if(cek(mid)){
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
            
        cout << ans << endl;    
    }
        
    return 0;
}

/*
*/

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