80分求调MLE
查看原帖
80分求调MLE
1004406
Wqq007楼主2024/11/5 22:15
#include <bits/stdc++.h>
#define all(x) x.begin()+1 ,x.end()
#define rep(i,b,n) for(auto i = b;i <= n;i++)
#define drep(i,b,n) for(auto i = b;i >= n;i--)
#define maxe(v) (*max_element(all(v)))
#define maxi(v) (max_elewment(all(v))-v.begin())
#define mine(v) (*min_element(all(v)))
#define mini(v) (min_element(all(v))-v.begin())
#define pb push_back
#define eb emplace_back
#define lb long double
#define ll long long
#define endl '\n'
const ll mod = 998244353;
const ll MOD = 1e9+7;
using namespace std;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n ,t ,s = 0;
	cin>>n>>t;
	vector<ll> v(n + 1) ,w(n + 1);
	for(ll i = 1;i <= n;i++){
		cin>>w[i]>>v[i];
		s += v[i];
	}
	vector<ll> dp(s + 1 ,0x3f3f3f3f);
	dp[0] = 0;
	for(ll i = 1;i <= n;i++){
		for(ll j = s;j >= v[i];j--){
			dp[j] = min(dp[j] ,dp[j - v[i]] + w[i]);
		}
	}
	for(ll i = s;i >= 0;i--){
		if(dp[i] <= t){
			return cout<<i ,0;
		}
	}
	return 0;
}
2024/11/5 22:15
加载中...