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;
typedef long long ll;
ll p1 = 27644437;
ll p2 = 1000000007;
int LIS(int n, ll a[]) {
const ll INF = 1e18;
vector<ll> d(n+1, INF);
d[0] = -INF;
for (int i = 0; i < n; i++) {
int l = upper_bound(d.begin(), d.end(), a[i]) - d.begin();
if (d[l-1] < a[i] && a[i] < d[l])
d[l] = a[i];
}
int ans = 0;
for (int l = 0; l <= n; l++) {
if (d[l] < INF)
ans = l;
}
return ans;
}
void solve() {
int n; cin >> n;
vector<pair<ll, ll>> computers;
vector<pair<ll, ll>> customers;
int sold[n+1];
for(int i=0;i<n;i++) {
ll c, f, v; cin >> c >> f >> v;
computers.push_back({f, v});
sold[i] = false;
}
int m; cin >> m;
int bied[m+1];
for(int i=0;i<m;i++) {
int c, f, v; cin >> c >> f >> v;
customers.push_back({f, v});
bied[i] = false;
}
sort(computers.begin(), computers.end());
sort(customers.begin(), customers.end());
bool W = true;
ll ans = 0;
while(W) {
W = false;
vector<pair<ll, ll>> value;
for(int i=0;i<n;i++) {
value.push_back({0, 0});
}
for(int i=0;i<n;i++) {
if(!sold[i]) {
for(int j=0;j<m;j++) {
if(!bied[j] && customers[j].first <= computers[i].first) {
ll gain = customers[j].second - computers[i].second;
if(gain > value[i].first) {
value[i] = {gain, j};
}
}
}
}
}
ll M = 0;
int best = -1;
for(int i=0;i<n;i++) {
if(value[i].first > M) {
M = value[i].first;
best = i;
}
}
if(best != -1) {
W = true;
ans+=value[best].first;
sold[best] = true;
bied[value[best].second] = true;
}
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
// int t; cin >> t;
// while(t--)
solve();
char dksfjn;
cin >> dksfjn;
}
# | 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... |