AcWing 3040. 英雄联盟
原题链接
困难
作者:
炽热的
,
2022-12-12 19:18:03
,
所有人可见
,
阅读 180
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long i64;
const int N = 245000;
int n, p;
i64 m;
int s[N], c[N];
i64 f[N];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> s[i];
for (int i = 1; i <= n; i ++ ) cin >> c[i], p += s[i] * c[i];
f[0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = p; j >= c[i]; j -- )
for (int k = 1; k * c[i] <= j && k <= s[i]; k ++ )
f[j] = max(f[j], f[j - k * c[i]] * k);
for (int i = 0; i <= p; i ++ )
if (f[i] >= m) {
cout << i;
break;
}
return 0;
}