#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 |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
13 ms |
2696 KB |
Output is correct |
6 |
Correct |
13 ms |
2636 KB |
Output is correct |
7 |
Correct |
13 ms |
2808 KB |
Output is correct |
8 |
Correct |
15 ms |
2812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
7 ms |
332 KB |
Output is correct |
6 |
Correct |
5 ms |
332 KB |
Output is correct |
7 |
Correct |
12 ms |
332 KB |
Output is correct |
8 |
Correct |
17 ms |
436 KB |
Output is correct |
9 |
Correct |
17 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
460 KB |
Output is correct |
4 |
Correct |
3 ms |
484 KB |
Output is correct |
5 |
Correct |
14 ms |
528 KB |
Output is correct |
6 |
Correct |
13 ms |
524 KB |
Output is correct |
7 |
Correct |
25 ms |
588 KB |
Output is correct |
8 |
Correct |
24 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
6 ms |
332 KB |
Output is correct |
4 |
Correct |
18 ms |
2580 KB |
Output is correct |
5 |
Correct |
1379 ms |
2596 KB |
Output is correct |
6 |
Correct |
1561 ms |
2764 KB |
Output is correct |
7 |
Correct |
1552 ms |
2856 KB |
Output is correct |
8 |
Correct |
1501 ms |
2832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
76 ms |
588 KB |
Output is correct |
4 |
Correct |
380 ms |
1868 KB |
Output is correct |
5 |
Correct |
1576 ms |
2868 KB |
Output is correct |
6 |
Correct |
1531 ms |
2836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
13 ms |
2696 KB |
Output is correct |
6 |
Correct |
13 ms |
2636 KB |
Output is correct |
7 |
Correct |
13 ms |
2808 KB |
Output is correct |
8 |
Correct |
15 ms |
2812 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
7 ms |
332 KB |
Output is correct |
14 |
Correct |
5 ms |
332 KB |
Output is correct |
15 |
Correct |
12 ms |
332 KB |
Output is correct |
16 |
Correct |
17 ms |
436 KB |
Output is correct |
17 |
Correct |
17 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
3 ms |
460 KB |
Output is correct |
21 |
Correct |
3 ms |
484 KB |
Output is correct |
22 |
Correct |
14 ms |
528 KB |
Output is correct |
23 |
Correct |
13 ms |
524 KB |
Output is correct |
24 |
Correct |
25 ms |
588 KB |
Output is correct |
25 |
Correct |
24 ms |
588 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
6 ms |
332 KB |
Output is correct |
29 |
Correct |
18 ms |
2580 KB |
Output is correct |
30 |
Correct |
1379 ms |
2596 KB |
Output is correct |
31 |
Correct |
1561 ms |
2764 KB |
Output is correct |
32 |
Correct |
1552 ms |
2856 KB |
Output is correct |
33 |
Correct |
1501 ms |
2832 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
3 ms |
460 KB |
Output is correct |
36 |
Correct |
76 ms |
588 KB |
Output is correct |
37 |
Correct |
380 ms |
1868 KB |
Output is correct |
38 |
Correct |
1576 ms |
2868 KB |
Output is correct |
39 |
Correct |
1531 ms |
2836 KB |
Output is correct |
40 |
Correct |
109 ms |
952 KB |
Output is correct |
41 |
Correct |
373 ms |
1836 KB |
Output is correct |
42 |
Correct |
889 ms |
2252 KB |
Output is correct |
43 |
Correct |
1489 ms |
2860 KB |
Output is correct |
44 |
Correct |
1501 ms |
2864 KB |
Output is correct |
45 |
Correct |
1520 ms |
2900 KB |
Output is correct |
46 |
Correct |
409 ms |
1612 KB |
Output is correct |
47 |
Correct |
921 ms |
2372 KB |
Output is correct |
48 |
Correct |
833 ms |
2184 KB |
Output is correct |