oj.uz

Submission #886500

# Submission time Handle Problem Language Result Execution time Memory
886500 2023-12-12T09:00:48 Z vjudge1 Gym Badges (NOI22_gymbadges) C++17
0 / 100
 125 ms 25164 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> all;

    all.push_back(0);   
    auto check =[&](int ix, int iy, int sum){
        if(sum<=l[ix]){
            sum+=x[ix];
            if(sum<=iy) return 1;
            return 0;
        }
        else return 0;
    };

    for(int i=1; i<n; i++){
        vector<int> all_new;

        int sum = 0, flag = 1;
        for(int j=0; j<all.size(); j++){

            if(!flag){
                    all_new.push_back(all[j]);
                    sum+=x[all[j]];
                
            }
            else{
                if(check(i, all[j], sum) == check(i, all[j], sum)){
                    if(l[i] < l[all[j]]){
                        all_new.push_back(i);
                        sum+=x[i];
                        j--; flag = 0;
                    }
                    else{
                        all_new.push_back(all[j]);
                        sum+=x[all[j]];
                    }
                }
                else if(check(i, all[j], sum)){
                    all_new.push_back(i);
                    sum+=x[i];
                    j--; flag = 0;
                }
                else if(check(all[j], i, sum)){
                        all_new.push_back(all[j]);
                        sum+=x[all[j]];
                }
            }
        }
        all = all_new;
    }

    int sum = 0, ans = 0;
    for(int i=0; i<all.size(); i++){
        if(sum<=l[all[i]]){
           // cout<<x[all[i]]<<" ";
            ans++;
            sum+=x[all[i]];
        }
        else break;
    }

    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:75:23: 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]
   75 |         for(int j=0; j<all.size(); j++){
      |                      ~^~~~~~~~~~~
Main.cpp:109:19: 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]
  109 |     for(int i=0; i<all.size(); i++){
      |                  ~^~~~~~~~~~~

Subtask #1
0 / 15.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 49.0

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