제출 #523579

#제출 시각아이디문제언어결과실행 시간메모리
523579DeepessonCloud Computing (CEOI18_clo)C++17
54 / 100
363 ms262148 KiB
#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[MAX][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][j][k];
                ll qualidade_sobra = pquali[i+1];
                ll ignora_cliente = 0;
                if(j)ignora_cliente=tab[i+2][j-1][k];
                ll ignora_pc = tab[i+1][j][k];
                ll compra_pc_e_continua = tab[i+1][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][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][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][M-1][0]<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...