Submission #886476

#	Time	Username	Problem	Language	Result	Execution time	Memory
886476		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	0 / 100	375 ms	22272 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()

int n, dp[500][500];
vector<int> a, b, x;

int f(int ind, int cur){
    if(ind==n) return 0;
    if(dp[ind][cur]!=-1) return dp[ind][cur];


    if(cur<=b[x[ind]]) return dp[ind][cur]=max(f(ind+1, cur+a[x[ind]])+1, f(ind+1, cur));
    return dp[ind][cur]=f(ind+1, cur);
}

int main(){
    cin>>n;

    x.resize(n); a.resize(n); b.resize(n);
    for(auto &e:a) cin>>e;
    for(auto &e:b) cin>>e;

    iota(all(x), 0);
    sort(all(x), [&](int l, int r){
        return (b[l]-a[r]<min({b[l], b[r], b[r]-a[l]}));
    });

    memset(dp, -1, sizeof(dp));
    cout<<f(0, 0);
}

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