이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define MAX 2005
typedef std::pair<int,int> pii;
typedef std::pair<int,pii> pip;
using ll = long long;
int ccore[MAX],cquali[MAX];
ll cpreco[MAX];
int pcore[MAX],pquali[MAX];
ll ppreco[MAX];
ll tab[3][MAX][51];
ll inf = (1LL<<60LL);
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int N;
std::cin>>N;
{
std::vector<pip> vec;
for(int i=0;i!=N;++i){
int a,b,c;
std::cin>>a>>b>>c;
vec.push_back({b,{c,a}});
}
std::sort(vec.begin(),vec.end());
for(int i=0;i!=N;++i){
ppreco[i]=vec[i].second.first;
pcore[i]=vec[i].second.second;
pquali[i]=vec[i].first;
}
}
int M;
std::cin>>M;
{
std::vector<pip> vec;
for(int i=0;i!=M;++i){
int a,b,c;
std::cin>>a>>b>>c;
vec.push_back({b,{c,a}});
}
std::sort(vec.begin(),vec.end());
for(int i=0;i!=M;++i){
cpreco[i]=vec[i].second.first;
ccore[i]=vec[i].second.second;
cquali[i]=vec[i].first;
}
}
for(int i=-1;i!=N;++i){
for(int j=0;j!=M;++j){
for(int k=0;k!=51;++k){
auto& ref = tab[(i+2)%3][j][k];
ll qualidade_sobra = pquali[i+1];
ll ignora_cliente = 0;
if(j)ignora_cliente=tab[(i+2)%3][j-1][k];
ll ignora_pc = tab[(i+1)%3][j][k];
ll compra_pc_e_continua = tab[(i+1)%3][j][std::min(50,k+pcore[i])] - ppreco[i];
ll cliente_com_sobra = -inf;
ll cliente_com_atual_e_sobra = -inf;
if(qualidade_sobra>=cquali[j]&&(k>=ccore[j])){
ll p = 0;
if(j)p=tab[(i+2)%3][j-1][k-ccore[j]];
cliente_com_sobra = p + cpreco[j];
}
if(i==-1){
ref=std::max(std::max(ignora_cliente,ignora_pc),std::max(compra_pc_e_continua,cliente_com_sobra));
continue;
}
ll qualidade_atual = pquali[i];
if(qualidade_atual>=cquali[j]&&(k+pcore[i]>=ccore[j])){
ll p = 0;
if(j)p=tab[(i+1)%3][j-1][std::min(50,pcore[i]+k-ccore[j])];
cliente_com_atual_e_sobra = p + cpreco[j] - ppreco[i];
}
ll respostas[] = {ignora_cliente,ignora_pc,compra_pc_e_continua,cliente_com_sobra,cliente_com_atual_e_sobra};
int sz = 5;
ref=*std::max_element(respostas,&respostas[sz]);
}
}
}
std::cout<<tab[(N+1)%3][M-1][0]<<"\n";
}
# | 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... |