Submission #1177501

#TimeUsernameProblemLanguageResultExecution timeMemory
1177501Fikrat_AsadzadehBigger segments (IZhO19_segments)C++20
0 / 100
1 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define FORI(i, n) for(ll i = 0; i < n; i++)
#define FOR(i, n) for(ll i = 1; i <= n; i++)
typedef vector < ll > vl; 
typedef set < ll > setl;
#define ff first
#define ss second    
#define all(v) v.begin(), v.end() 
#define pll pair<ll, ll> 
#define db double
#define nll cout << "\n"
#define nl "\n"
#define sync ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll poww(ll a, ll b){
    ll res = 1;
    while(b){
        if(b & 1)res *= a;
        a *= a;
        b >>= 1;
    }
    return res;
}
const ll mod =  998244353;
const int sz = 5e5 + 5 ;
const long long imax = LLONG_MAX;
ll n, m, k, res, q, x, y;
ll a[sz], b[sz];
ll pref[sz];
void solve(){
    cin >> n;
    FOR(i, n)cin >> a[i], pref[i] = pref[i - 1] + a[i];
    ll cur = 1;
    ll csum = 0;
    ll last = a[1];
    for(ll i = 2; i <= n; i++){
        csum = 0;
        ll st = i;
        while(i <= n && csum < last)csum += a[i++];
        i--;
        ll end = i ;
        // cout << st << " " << end << " " << csum << nl;
        ll xsum = 0;
        ll ind = -1;
        for(ll x = st; x <= end ; x++){
            xsum += a[x];
        }
        for(ll x = end ; x >= st ; x--){
            if(last + xsum <= csum - xsum){
                ind = x;
                break;
            }
            xsum -= a[x];
        }
        if(ind != -1) {
            csum -= xsum;
            last += xsum;
        }
        b[cur] = last;
        last = csum;
        cur++;
        b[cur] = last;
    }
    // FOR(i, cur)cout << b[i] << " ";
    cout << cur;
}
//IOI rice hub
signed main(){      
    // freopen("input.txt","r",stdin);a
    // freopen("output.txt","w",stdout);
    sync;
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }   
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...