| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1169199 | userro1234324 | Jelly Flavours (IOI20_jelly) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
int n, X, Y;
const int maxn = 2001;
int wynik;
// koszt oraz numer elementu
pair <int, int> elementy_a[maxn], elementy_b[maxn];
bool czy_jest_w_x[maxn];
int maksymalna_suma_y_do_wziecia;
int aktualna_suma_y;
int najlepsze_sumy_y[10001];
int ile_roznych_elementow;
int wartosc_a[maxn];
int wartosc_b[maxn];
int najlepsza_zabrana;
void dodaj_element_a(int i) {
czy_jest_w_x[elementy_a[i].second] = true;
maksymalna_suma_y_do_wziecia += wartosc_b[elementy_a[i].second];
for (int k = X; k >= elementy_a[i].first; k--) {
najlepsze_sumy_y[k] = max(najlepsze_sumy_y[k], najlepsze_sumy_y[k - elementy_a[i].first] + wartosc_b[elementy_a[i].second]);
najlepsza_zabrana = max(najlepsza_zabrana, najlepsze_sumy_y[k]);
}
}
void sprawdz_drugi_ciag(int i) {
ile_roznych_elementow = i;
aktualna_suma_y = maksymalna_suma_y_do_wziecia;
if (aktualna_suma_y - najlepsza_zabrana <= Y) wynik = max(wynik, ile_roznych_elementow);
else return;
for (int j = 1; j <= n; j++) {
if (czy_jest_w_x[elementy_b[j].second]) continue;
ile_roznych_elementow++;
aktualna_suma_y += elementy_b[j].first;
if (aktualna_suma_y - najlepsza_zabrana <= Y) wynik = max(wynik, ile_roznych_elementow);
else return;
}
}
void zrob_zadanie() {
sprawdz_drugi_ciag(0);
for (int i = 1; i <= n; i++) {
dodaj_element_a(i);
sprawdz_drugi_ciag(i);
}
}
vector <int> a;
vector <int> b;
int main() {
scanf("%d %d %d", &n, &X, &Y);
for (int i = 0; i < n; i++) {
int e;
scanf("%d", &e);
a.push_back(e);
scanf("%d", &e);
b.push_back(e);
}
for (int i = 1; i <= n; i++) {
elementy_a[i] = {a[i - 1], i};
elementy_b[i] = {b[i - 1], i};
wartosc_a[i] = a[i - 1];
wartosc_b[i] = b[i - 1];
}
sort(elementy_a + 1, elementy_a + n + 1);
sort(elementy_b + 1, elementy_b + n + 1);
zrob_zadanie();
printf("%d", wynik);
}