9679 2024. 02. 24 17:35:25 szil Jobstown-i milliomos cpp17 Elfogadva 100/100 259ms 10596 KiB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define MAX(a, b) a = max(a, b)

const int MAXN = 501;
const int MAXV = 600*600;

ll dp[MAXV];
ll t[MAXN], p[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin>>n>>m;
	for (int i = 1; i <= n; i++) cin >> t[i];
	for (int i = 1; i <= n; i++) cin >> p[i];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j+t[i] < MAXV; j++){
			MAX(dp[j+t[i]], dp[j] + p[i]);
		}
	}
	ll mx = 0;
	for (int i = 1; i <= n; i++) {
		ll cnt = (m-MAXV >= 0) ? ((m-MAXV+t[i])/t[i]) : 0;
		ll next_m = m - cnt*t[i];
		ll curr = p[i]*cnt + dp[next_m];
		MAX(mx, curr);
	}
	cout<<mx<<endl;
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 8ms 7528 KiB
2 Elfogadva 7ms 7744 KiB
subtask2 25/25
3 Elfogadva 7ms 7952 KiB
4 Elfogadva 7ms 8160 KiB
5 Elfogadva 179ms 8248 KiB
6 Elfogadva 178ms 8132 KiB
7 Elfogadva 178ms 8352 KiB
8 Elfogadva 178ms 8472 KiB
9 Elfogadva 179ms 8820 KiB
10 Elfogadva 179ms 8892 KiB
11 Elfogadva 252ms 8864 KiB
12 Elfogadva 246ms 9068 KiB
13 Elfogadva 256ms 9232 KiB
14 Elfogadva 6ms 9320 KiB
subtask3 16/16
15 Elfogadva 259ms 9412 KiB
16 Elfogadva 248ms 9480 KiB
17 Elfogadva 248ms 9744 KiB
18 Elfogadva 6ms 9692 KiB
19 Elfogadva 194ms 9692 KiB
20 Elfogadva 194ms 9848 KiB
21 Elfogadva 194ms 9828 KiB
subtask4 59/59
22 Elfogadva 7ms 9972 KiB
23 Elfogadva 7ms 9936 KiB
24 Elfogadva 178ms 9944 KiB
25 Elfogadva 178ms 10020 KiB
26 Elfogadva 178ms 10108 KiB
27 Elfogadva 257ms 9964 KiB
28 Elfogadva 250ms 10180 KiB
29 Elfogadva 247ms 10264 KiB
30 Elfogadva 6ms 10344 KiB
31 Elfogadva 179ms 10344 KiB
32 Elfogadva 178ms 10476 KiB
33 Elfogadva 178ms 10596 KiB