# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1242060 | glx200 | Cloud Computing (CEOI18_clo) | C++17 | 1701 ms | 672 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int const maxN=2e3+1;
struct{
ll c;
ll p;
ll f;
} hotel[maxN];
bool used[maxN];
int main(){
ll n,m,sum=0;
cin>> n;
for(int i=1;i<=n;i++){
cin>>hotel[i].c>>hotel[i].p>>hotel[i].f;
}
cin>>m;
for(int i=1;i<=m;i++){
ll x,y,z;
cin>>x>>y>>z;
vector<ll> a; // a la mang luu lai cac hotel thoa man : do hotel.p > y
for(int i=1;i<=n;i++){
if(!used[i] && hotel[i].p>=y){
a.push_back(i);
}
}
ll m=n*50+5,smp=1e19,phongcandung;
vector<ll> dp(m,1e18);
dp[0]=0;
for(ll i : a){
for(ll j=m-hotel[i].c-2;j>=0;j--){
if(!used[i] && dp[j+hotel[i].c] > dp[j]+hotel[i].f){
dp[j+hotel[i].c]=dp[j]+hotel[i].f;
}
}
}
for(ll i=x;i<=m;i++){
if(dp[i]<=smp){
smp=dp[i];
phongcandung=i;
}
}
if(smp<z){
sum+=z-smp;
for(ll i:a){
if( phongcandung<=hotel[i].c && dp[phongcandung-hotel[i].c] + hotel[i].f == dp[phongcandung]){
used[i]=true;
phongcandung-=hotel[i].c;
if(phongcandung==0) break;
}
}
}
}
cout<<sum;
}
Compilation message (stderr)
# | 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... |