Submission #44028774

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN = 310,INF = 2e18;

void tomax(ll& x,ll y){x = max(x,y);}
void tomin(ll& x,ll y){x = min(x,y);}

ll n,H,c[MAXN],d[MAXN],ans = INF;

ll dp[MAXN*2][MAXN*2],M = 605;

ll dp2[MAXN*MAXN*4];

ll val[MAXN*2];

vector<int>arr;

int main(){
	cin>>n>>H;

	rep(i,1,n){
		cin>>c[i]>>d[i];
	}

	rep(i,0,M)rep(j,0,M)dp[i][j] = -INF;

	dp[0][0] = 0;

	rep(i,0,M-1)rep(j,0,M)if(dp[i][j] != -INF){
		rep(k,1,n)if(j - c[k] >= 0 && j - c[k] <= M)tomax(dp[i+1][j-c[k]],dp[i][j] + d[k]);
	}

	rep(i,1,M){
		val[i] = -INF;
		rep(j,0,M)tomax(val[i],dp[i][j]);

		if(val[i] != -INF)arr.push_back(i);
	}


	int cnt = arr.size();assert(cnt);
	sort(arr.begin(),arr.end(),[&](int x,int y){return val[x] * y > val[y] * x;});

	int f = arr[0];

	rep(i,0,M*M)dp2[i] = -INF;
	dp2[0] = 0;
	rep(i,0,M*M-1)if(dp2[i] != -INF){
		rep(j,1,cnt-1){
			int x = arr[j];
			if(i + x <= M*M)tomax(dp2[i+x],dp2[i] + val[x]);
		}
	}
	rep(i,0,M*M)if(dp2[i] != -INF){
		ll rest = H - dp2[i],cnt = i;
		if(rest > 0)cnt += (rest + val[f] - 1) / val[f] * f;

		tomin(ans,cnt);
	}

	cout<<ans<<endl;

    return 0;
}

Submission Info

Judge Result