Submission #886423

#	Time	Username	Problem	Language	Result	Execution time	Memory
886423		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	0 / 100	2040 ms	33528 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e9;

/*
struct segtree{
    int n;
    vector<int> st, t, marked;
    vector<array<int, 2>> x;

    int base = 0;

    segtree(int _n){
        n = _n;
        st.resize(4*n, 0);
        t.resize(4*n, 0);
        marked.resize(4*n, 0);
        x.resize(4*n, 0);
    }

    void update(int v, int l, int r, int val){
        push(v, l, r);
        if(l>tr || r <tl) return;
        if(l>=tl && r<=tr){
            st[v]+=val; t[v] =val;
            marked[v] = 1;
        }
        else{
            int mid = (l+r) / 2;
            update(v*2, l, mid, val);
            update(v*2, mid, l, 1);
        }
    }


}
*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    // brute force yazıp kotnrol et

    int n; cin >> n;
    vector<int> l(n), x(n);

    for(int i=0; i<n; i++) cin >> x[i];
    for(int i=0; i<n; i++) cin >> l[i];

    vector<int> ans(n+1, -1), ind(n+1, -1);
    
    ans[0] = 0;

    int pos = 0;

    for(int i=0; i<n; i++){
        vector<int>pref(n);
        pref = ans;

        for(int l=1; l<=pos; l++){
            pref[l]+=pref[l-1];
        }

        if(pref[pos] <= l[i]){
            ans[pos+1] = x[i];
            ind[pos+1] = i;
            pos++;
        }
        else{
            int pf = 0;
            for(int j=0; j<=pos; j++){
                if(pref[j] <= l[i]) pf = j;
            }

            if(ans[pf+1] > x[i]){
                ans[pf+1] = x[i];
                int indx = ind[pf+1];
                ind[pf+1] = i;

                pref = ans;

                for(int l=1; l<=pos; l++){
                    pref[l]+=pref[l-1];
                }

                if(pref[pos] <=l[indx]){
                    ans[pos+1] = x[indx];
                    ind[pos+1] = indx;
                    pos++; 
                }
            }
        }
    }

    cout << pos;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 9
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49