This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int c=10002, p=2002, sok=1e9;
int n, maxi, regi[2*c], uj[2*c];
bool v[p];
vector<pair<int, int> > yr;
vector<pair<pair<int, int>, int> > xr;
int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
n=a.size();
for (int i=0; i<n; i++) {
xr.push_back({{a[i], b[i]}, i});
yr.push_back({b[i], i});
}
sort(xr.begin(), xr.end()), sort(yr.begin(), yr.end());
for (int i=0; i<=x; i++) regi[i]=sok, uj[i]=sok;
regi[0]=0;
for (int i=0; i<n; i++) {
int fi=xr[i].first.first, se=xr[i].first.second, id=xr[i].second;
v[id]=1;
for (int j=x; j>=0; j--) {
uj[j]=min(uj[j], regi[j]+se);
uj[j+fi]=min(uj[j+fi], regi[j]);
}
regi[0]=uj[0], uj[0]=sok;
for (int i=1; i<=x; i++) regi[i]=min(uj[i], regi[i-1]), uj[i]=sok;
/*cout << id << " ";
for (int i=0; i<=2; i++) cout << regi[i] << " ";
cout << "\n";*/
int sum=0, db=1;
if (regi[x]<=y) maxi=max(maxi, i+1);
for (int j=0; j<n; j++) {
int fi=yr[j].first, se=yr[j].second;
if (!v[se]) {
sum+=fi, db++;
if (regi[x]+sum<=y) maxi=max(maxi, i+db);
}
}
}
return maxi;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |