제출 #1129513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129513		12345678	Gym Badges (NOI22_gymbadges)	C++20	42 / 100	1199 ms	204784 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e3+5;

ll n, dp[nx][nx], x[nx], l[nx];
vector<pair<ll ,ll>> v;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n;i ++) cin>>x[i];
    for (int i=1; i<=n; i++) cin>>l[i], v.push_back({x[i]+l[i], i});
    sort(v.begin(), v.end());
    for (int i=0; i<=n; i++) for (int j=1; j<=n; j++) dp[i][j]=1e18;
    for (int i=1; i<=n; i++)
    {
        int idx=v[i-1].second;
        for (int j=1; j<=n; j++)
        {
            dp[i][j]=dp[i-1][j];
            if (dp[i-1][j-1]<=l[idx]) dp[i][j]=min(dp[i][j], dp[i-1][j-1]+x[idx]);
            //cout<<"debug "<<i<<' '<<idx<<' '<<j<<' '<<dp[i][j]<<'\n';
        }
    }
    for (int i=n; i>=1; i--) if (dp[n][i]!=1e18) return cout<<i, 0;
}

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