oj.uz

Submission #886466

# Submission time Handle Problem Language Result Execution time Memory
886466 2023-12-12T07:55:10 Z vjudge1 Gym Badges (NOI22_gymbadges) C++17
0 / 100
 2000 ms 27788 KB 
#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);


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


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

    sort(gh.begin(), gh.end(), [&](auto a, auto b){
        return (a[0]<b[0]) || (a[0]==b[0] && a[1]>b[1]);
    });
    
    for(int i=0; i<n; i++) x[i] = gh[i][0], l[i] = gh[i][1];

    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;
        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{
            vector<int> pans, pind;

            int el = i;
            int sum = pref[pos]+x[i];
            int ps =-1;

            for(int j=1; j<=pos; j++){
                if(sum-x[ind[j]]<=l[ind[j]]){
                     ps = j;
                }
            }
            
            if(ps!=-1){
                pans.push_back(0); pind.push_back(0);
                sum = 0;

                for(int j=1; j<=pos; j++){
                    if(ps==ind[j]) continue;
                    if(sum+ans[j]<= l[i]){
                        pans.push_back(ans[j]);
                        pind.push_back(ind[j]);
                        sum+=ans[j];
                    }
                    else if(sum <= l[i]){
                        pans.push_back(ans[i]);
                        pind.push_back(i);
                        pans.push_back(ans[j]);
                        pind.push_back(ind[j]);
                        sum+=x[i];
                        sum+=ans[j];
                    }
                    else{
                        pans.push_back(ans[j]);
                        pind.push_back(ind[j]);
                        sum+=ans[j];  
                    }
                }

                pans.push_back(ans[ps]);
                pind.push_back(ind[ps]);
                sum = 0;
                int flag = 1;
                for(int i=0; i<=pans.size(); i++){
                    if(sum>l[pind[i]]) flag = 0;
                    sum+=pans[i];
                }

                if(flag){
                    for(int i=0; i<=pos+1; i++){
                        ans[i] = pans[i];
                        ind[i] = ind[i];
                    }
                    pos++;
                }
            }
            
            

   
        }
    }

    cout << pos;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:120:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |                 for(int i=0; i<=pans.size(); i++){
      |                              ~^~~~~~~~~~~~~
Main.cpp:80:17: warning: unused variable 'el' [-Wunused-variable]
   80 |             int el = i;
      |                 ^~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2062 ms 27788 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -