Submission #523578

#	Time	Username	Problem	Language	Result	Execution time	Memory
523578		Deepesson	Cloud Computing (CEOI18_clo)	C++17	54 / 100	1306 ms	262148 KiB

clo

#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];
bool existe[MAX][MAX][51];
ll inf = (1LL<<60LL);
ll dp(int pos1,int pos2,int sobra){
    if(pos1==-2){
        return 0;
    }
    if(pos2<0){
        return 0;
    }
    if(existe[pos1+2][pos2][sobra])return tab[pos1+2][pos2][sobra];
    existe[pos1+2][pos2][sobra]=true;
    ll qualidade_sobra = pquali[pos1+1];
    ll ignora_cliente = dp(pos1,pos2-1,sobra);
    ll ignora_pc = dp(pos1-1,pos2,sobra);
    ll compra_pc_e_continua = dp(pos1-1,pos2,std::min(50,sobra+pcore[pos1])) - ppreco[pos1];
    ll cliente_com_sobra = -inf;
    ll cliente_com_atual_e_sobra = -inf;
    if(qualidade_sobra>=cquali[pos2]&&(sobra>=ccore[pos2])){
   ///     printf("key %d %d [%d]\n",pos1,pos2,sobra);
        cliente_com_sobra = dp(pos1,pos2-1,sobra-ccore[pos2]) + cpreco[pos2];
    }
    if(pos1==-1){
        return tab[pos1+2][pos2][sobra]=std::max(std::max(ignora_cliente,ignora_pc),std::max(compra_pc_e_continua,cliente_com_sobra));
    }
    ll qualidade_atual = pquali[pos1];
   /// std::cout<<"Demanda "<<cquali[pos2]<<" Tem: "<<qualidade_atual<<" "<<pos1<<" "<<pos2<<"\n";
    if(qualidade_atual>=cquali[pos2]&&(sobra+pcore[pos1]>=ccore[pos2])){
  ///      printf("opa %d %d\n",pos1,pos2);
        cliente_com_atual_e_sobra = dp(pos1-1,pos2-1,std::min(50,pcore[pos1]+sobra-ccore[pos2])) + cpreco[pos2] - ppreco[pos1];
    }
    ll respostas[] = {ignora_cliente,ignora_pc,compra_pc_e_continua,cliente_com_sobra,cliente_com_atual_e_sobra};
    int sz = 5;
    return tab[pos1+2][pos2][sobra]=*std::max_element(respostas,&respostas[sz]);
}
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;
        }
    }
    std::cout<<dp(N-1,M-1,0)<<"\n";
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 0 / 18
• Subtask 5: 0 / 18
• Subtask 6: 0 / 10