Submission #685382

#	Time	Username	Problem	Language	Result	Execution time	Memory
685382		yhlas	Bigger segments (IZhO19_segments)	C++17	13 / 100	1578 ms	348 KiB

segments

#include <iostream>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
#include <vector>
//#include <map>
//#include <set>
//#include <iomanip>
using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;
//typedef tree<ll,null_type,less<int>,rb_tree_tag,
//tree_order_statistics_node_update> indexed_set;

#define fbo find_by_order
#define ofk order_of_key

#define gg       500005
#define ll       long long
#define ull      unsigned ll
#define ld       long double
#define pii      pair<int,int>
#define pll      pair<ll,ll>
#define vi       vector<int>
#define vll      vector<ll>
#define stll     stack<ll>
#define qll      queue<ll>
#define pqll     priority_queue<ll>
#define pq       priority_queue

#define pb              push_back
#define ub              upper_bound
#define lb              lower_bound
#define issq(x)         (((ll)(sqrt((x))))*((ll)(sqrt((x))))==(x))
#define ff              first
#define ss              second
#define lg(r,n)         (int)(log2(n)/log2(r))

#define rev(v)              reverse(v.begin(),v.end())
#define srt(v)              sort(v.begin(),v.end())
#define srtr(v)             sort(v.rbegin(),v.rend());
#define all(v)              v.begin(),v.end()
#define allr(v)             v.rbegin(), v.rend()
#define mnv(v)              *min_element(v.begin(),v.end())
#define mxv(v)              *max_element(v.begin(),v.end())
#define countv(v,a)         count(v.begin(),v.end(),a)
#define sz(x)               (int)x.size()

int n, a[gg], b[gg], ans;

void f(int x)
{
    if ( x == n + 1 ){
        int sm = 0;
        
        vi v;
        for (int i = 2; i <= n; i++)
            if ( b[i] ) v.pb(i);

        int cur = 0;
        vi u;
        for (int i = 1; i <= n; i++){
            sm += a[i];
            if ( cur < sz(v) and i == v[cur] - 1 ){
                cur++;
                u.pb(sm); sm = 0;
            }
        }

        u.pb(sm);

        bool tr = 0;
        for (int i = 1; i < sz(u); i++)
            if ( u[i - 1] > u[i] ){
                tr = 1; break;
            }

        if ( !tr ) ans = max(ans, sz(v) + 1);
        return;
    }
    for (int i = 0; i < 2; i++){
        b[x] = i;
        f(x + 1);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    f(2);

    cout << ans;
}
//could_solve_myself:)

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