oj.uz

Submission #1006099

# Submission time Handle Problem Language Result Execution time Memory
1006099 2024-06-23T11:47:37 Z andecaandeci Bigger segments (IZhO19_segments) C++17
0 / 100
 0 ms 344 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -