QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412009 | #795. Cloud Computing | sichengzhou | 54 | 646ms | 5624kb | C++14 | 1.9kb | 2024-05-15 22:54:08 | 2024-05-15 22:54:09 |
Judging History
answer
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e3+10;
int n,m;
struct Node{
int c,f,v;
bool operator <(const Node &t)const
{
return f<t.f;
}
}a[N],b[N];
LL f[N][51],g[N][51];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].c,&a[i].f,&a[i].v);
}
sort(a+1,a+n+1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&b[i].c,&b[i].f,&b[i].v);
}
sort(b+1,b+m+1);
memset(f,0x3f,sizeof(f));
f[m+1][0]=0;
for(int i=n+1;i>=2;i--)
{
for(int j=m+1;j>=2;j--)
{
for(int k=0;k<=50;k++)
{
f[j-1][k]=min(f[j-1][k],f[j][k]);
if(k>=b[j-1].c&&a[i].f>=b[j-1].f)
{
f[j-1][k-b[j-1].c]=min(f[j-1][k-b[j-1].c],f[j][k]-b[j-1].v);
}
}
}
// cout<<i<<endl;
memset(g,0x3f,sizeof(g));
for(int j=m+1;j>=1;j--)
{
for(int k=0;k<=50;k++)
{
// if(f[j][k]<1e18)cout<<j<<' '<<k<<' '<<f[j][k]<<endl;
g[j][k]=min(g[j][k],f[j][k]);
if(k+a[i-1].c<=50&&a[i-1].f>=b[j-1].f)
{
g[j][k+a[i-1].c]=min(g[j][k+a[i-1].c],f[j][k]+a[i-1].v);
}
if(k+a[i-1].c-b[j-1].c<=50&&k+a[i-1].c-b[j-1].c>=0&&a[i-1].f>=b[j-1].f)
{
g[j-1][k+a[i-1].c-b[j-1].c]=min(g[j-1][k+a[i-1].c-b[j-1].c],f[j][k]+a[i-1].v-b[j-1].v);
}
}
}
memcpy(f,g,sizeof(g));
}
LL ans=0x3f3f3f3f3f3f3f3f;
for(int k=0;k<=50;k++)
{
ans=min(ans,f[1][k]);
}
printf("%lld\n",-ans);
return 0;
}
/*
4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 18
Accepted
time: 1ms
memory: 5520kb
input:
1 3 3253 744 1 1 2012 798
output:
54
result:
ok single line: '54'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5536kb
input:
1 1 2291 728 1 3 3024 858
output:
0
result:
ok single line: '0'
Test #3:
score: -18
Wrong Answer
time: 1ms
memory: 5572kb
input:
8 18 5754 6872 11 5543 1464 6 6940 9405 10 5152 4196 13 5784 7499 18 6787 260 14 5922 218 17 5037 7983 100 3 5482 4812 1 3922 7167 3 3566 8041 2 3532 3839 3 3948 4490 2 5301 6616 3 4216 796 2 4583 5021 1 3311 3984 3 3044 2702 2 4529 288 2 3352 6474 2 3102 4548 3 3784 2968 2 5054 2143 2 5385 1542 3 3...
output:
336125
result:
wrong answer 1st lines differ - expected: '368159', found: '336125'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 18
Accepted
Test #18:
score: 18
Accepted
time: 0ms
memory: 5524kb
input:
12 1 3728 3883 1 2483 1377 1 2421 2213 1 4866 648 1 2292 1737 1 4027 657 1 2119 2801 1 2559 859 1 3859 3261 1 2908 3110 1 2917 2467 1 2011 3406 18 1 2558 4956 1 3468 2947 1 4577 4082 1 2886 2222 1 2979 3572 1 2266 4860 1 2868 3183 1 3665 4259 1 2607 4802 1 2811 3874 1 2314 4212 1 2638 3152 1 2944 44...
output:
23934
result:
ok single line: '23934'
Test #19:
score: 0
Accepted
time: 1ms
memory: 5464kb
input:
12 1 2208 8567 1 2221 8626 1 2152 8312 1 2293 8956 1 2261 8809 1 2062 7905 1 2203 8544 1 2105 8099 1 2280 8896 1 2057 7882 1 2015 7693 1 2162 8357 18 1 2563 10209 1 2000 7626 1 3072 12633 1 2789 11276 1 2144 8276 1 2921 11906 1 2380 9357 1 2077 7972 1 2103 8090 1 2868 11652 1 2684 10778 1 3043 12493...
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 6ms
memory: 5444kb
input:
79 1 4427 4256458 1 3723 3490767 1 3982 3260428 1 3770 3355873 1 4741 4551396 1 5000 1319580 1 4063 2173424 1 2181 4525445 1 3737 1728963 1 3931 4866468 1 4157 4762822 1 4236 1841301 1 2378 2709820 1 4220 2261004 1 2446 4168561 1 4547 2573600 1 3060 2878656 1 4672 4605556 1 2852 3719524 1 4693 42886...
output:
20786601
result:
ok single line: '20786601'
Test #21:
score: 0
Accepted
time: 6ms
memory: 5528kb
input:
79 1 2056 12536 1 2597 8192 1 4936 68413 1 2084 25464 1 2720 34555 1 3791 50555 1 4363 59390 1 4401 14996 1 2332 28967 1 3914 52440 1 4042 13602 1 4057 27320 1 2954 9495 1 4090 13787 1 4478 61188 1 4040 27189 1 3415 22425 1 4636 47751 1 2837 36264 1 4816 33255 1 3383 44370 1 2916 28067 1 3901 52240 ...
output:
237760
result:
ok single line: '237760'
Test #22:
score: 0
Accepted
time: 18ms
memory: 5524kb
input:
224 1 6270 93747369 1 6502 167724928 1 6437 264148706 1 4077 760036221 1 5697 879487623 1 4557 733795468 1 6903 407495462 1 4106 697615090 1 7426 694689028 1 6401 689447791 1 7806 714964788 1 6997 288721199 1 5680 267711948 1 6188 217596834 1 7122 588728375 1 5561 436746734 1 5953 13086744 1 5223 33...
output:
40094608225
result:
ok single line: '40094608225'
Test #23:
score: 0
Accepted
time: 14ms
memory: 5540kb
input:
224 1 5309 28215 1 6848 18732 1 4262 55227 1 4660 48801 1 7916 66044 1 4018 31030 1 5015 26480 1 6577 17908 1 4879 51363 1 7792 86523 1 4023 31073 1 5349 56904 1 4124 10647 1 5126 67834 1 6453 52599 1 7970 44364 1 7728 85732 1 6969 76407 1 6245 33809 1 6330 85806 1 5045 13328 1 6873 18808 1 7161 984...
output:
1397706
result:
ok single line: '1397706'
Test #24:
score: 0
Accepted
time: 21ms
memory: 5524kb
input:
250 1 414892080 475780331 1 389986020 498894352 1 466122353 629641334 1 105791542 964215227 1 108319175 465600284 1 672601741 82971811 1 249420710 401256555 1 149341259 342168603 1 567366454 947578513 1 435092128 806081813 1 780065289 367591037 1 715227604 87185140 1 959201300 62189501 1 257570515 5...
output:
58593606691
result:
ok single line: '58593606691'
Test #25:
score: 0
Accepted
time: 23ms
memory: 5532kb
input:
250 1 139452088 615617196 1 108712470 470545881 1 218593295 999953196 1 200154778 909239851 1 216513655 989690503 1 206416295 939973840 1 101136346 870514051 1 210214974 958655407 1 107570262 465212767 1 114343906 496903861 1 169066882 757820712 1 130284386 572057468 1 178646230 804261003 1 20928398...
output:
11992746282
result:
ok single line: '11992746282'
Subtask #4:
score: 18
Accepted
Test #26:
score: 18
Accepted
time: 0ms
memory: 5540kb
input:
10 2 1 2274 2 1 2524 1 1 2699 5 1 2930 4 1 1802 2 1 2734 4 1 1036 3 1 2741 5 1 1138 1 1 2132 6 5 1 3573 1 1 4847 2 1 3885 1 1 2183 2 1 2534 1 1 4659
output:
17705
result:
ok single line: '17705'
Test #27:
score: 0
Accepted
time: 0ms
memory: 5396kb
input:
10 5 1 19 3 1 14 4 1 10 3 1 10 4 1 20 2 1 9 1 1 4 4 1 10 1 1 2 3 1 10 6 5 1 13 5 1 13 3 1 10 1 1 3 5 1 13 5 1 13
output:
4
result:
ok single line: '4'
Test #28:
score: 0
Accepted
time: 77ms
memory: 5552kb
input:
1500 5 1 766 1 1 925 5 1 545 5 1 916 1 1 747 3 1 981 2 1 794 1 1 853 4 1 745 2 1 539 4 1 611 3 1 730 2 1 995 4 1 663 1 1 667 4 1 615 3 1 813 3 1 750 2 1 917 3 1 568 1 1 602 1 1 792 1 1 774 5 1 860 5 1 834 1 1 946 2 1 567 3 1 770 3 1 750 5 1 752 4 1 718 3 1 987 2 1 977 4 1 838 2 1 642 4 1 558 4 1 878...
output:
0
result:
ok single line: '0'
Test #29:
score: 0
Accepted
time: 5ms
memory: 5540kb
input:
13 20 1 9848 33 1 11113 33 1 11397 43 1 5486 19 1 10018 37 1 8534 43 1 7616 43 1 5394 13 1 11453 44 1 11120 29 1 11057 46 1 9023 20 1 11984 1805 9 1 845 4 1 355 6 1 818 7 1 307 9 1 354 9 1 593 10 1 650 3 1 962 5 1 273 8 1 873 1 1 420 7 1 948 4 1 668 1 1 708 6 1 616 7 1 594 9 1 201 7 1 768 3 1 802 7 ...
output:
102484
result:
ok single line: '102484'
Test #30:
score: 0
Accepted
time: 646ms
memory: 5616kb
input:
1992 11 1 199631204 46 1 880088920 46 1 60421978 41 1 374317414 26 1 752692847 46 1 745140558 12 1 64000008 5 1 454886525 13 1 69573629 15 1 522471571 38 1 611340638 20 1 11136794 14 1 757697844 29 1 474321924 42 1 911180569 9 1 569689273 14 1 321726981 14 1 236570294 36 1 312654389 23 1 35766191 27...
output:
575524668672
result:
ok single line: '575524668672'
Test #31:
score: 0
Accepted
time: 640ms
memory: 5512kb
input:
2000 43 1 160482641 50 1 128216371 43 1 795777040 48 1 639914818 44 1 341588814 50 1 694546956 47 1 111220218 44 1 529410604 49 1 33620380 47 1 488422815 48 1 689416355 44 1 128908044 43 1 804535816 43 1 778001742 46 1 332918417 42 1 757120862 40 1 835341946 48 1 69935722 40 1 702766873 46 1 9924335...
output:
0
result:
ok single line: '0'
Test #32:
score: 0
Accepted
time: 644ms
memory: 5576kb
input:
2000 46 1 16 46 1 12 41 1 6 43 1 13 43 1 16 47 1 16 43 1 2 40 1 14 50 1 14 42 1 12 50 1 3 45 1 1 41 1 3 48 1 6 46 1 18 47 1 17 48 1 18 41 1 6 44 1 13 43 1 2 46 1 9 45 1 14 45 1 14 47 1 2 41 1 3 45 1 8 42 1 13 48 1 13 42 1 3 40 1 18 48 1 19 48 1 11 47 1 9 41 1 16 49 1 8 45 1 8 48 1 1 47 1 13 50 1 6 4...
output:
1000605883784
result:
ok single line: '1000605883784'
Test #33:
score: 0
Accepted
time: 627ms
memory: 5560kb
input:
1937 48 1 10 44 1 17 45 1 15 40 1 3 47 1 13 45 1 3 41 1 13 50 1 8 45 1 18 50 1 4 49 1 5 48 1 9 50 1 19 46 1 14 48 1 2 45 1 5 42 1 2 50 1 17 42 1 4 50 1 20 47 1 5 40 1 19 44 1 16 44 1 9 40 1 7 45 1 2 47 1 5 50 1 13 47 1 19 43 1 11 45 1 4 46 1 9 46 1 7 49 1 12 45 1 1 42 1 13 46 1 7 46 1 1 49 1 3 49 1 ...
output:
976944450013
result:
ok single line: '976944450013'
Subtask #5:
score: 18
Accepted
Test #34:
score: 18
Accepted
time: 0ms
memory: 5512kb
input:
4 43 2536 1 48 2001 1 49 3407 1 48 3778 1 2 42 3314 1 43 3073 1
output:
0
result:
ok single line: '0'
Test #35:
score: 0
Accepted
time: 4ms
memory: 5536kb
input:
57 47 1212 1 42 1104 1 48 1247 1 44 1420 1 41 1428 1 46 1364 1 47 1245 1 40 1199 1 48 1027 1 49 1113 1 50 1439 1 45 1208 1 41 1231 1 41 1131 1 48 1080 1 43 1218 1 45 1145 1 44 1071 1 43 1393 1 47 1314 1 45 1306 1 47 1439 1 42 1124 1 49 1383 1 47 1175 1 45 1099 1 46 1378 1 45 1285 1 46 1323 1 41 1234...
output:
0
result:
ok single line: '0'
Test #36:
score: 0
Accepted
time: 43ms
memory: 5488kb
input:
570 46 5838 1 40 6425 1 44 5897 1 42 6694 1 49 4775 1 43 6145 1 49 3903 1 46 4661 1 50 5987 1 43 7469 1 40 8641 1 47 7424 1 43 6303 1 44 9446 1 42 9626 1 48 3201 1 46 4829 1 44 7695 1 41 8599 1 48 4502 1 43 7551 1 44 4095 1 50 7648 1 45 5950 1 50 8967 1 42 3801 1 45 4723 1 42 8216 1 47 9791 1 41 586...
output:
233
result:
ok single line: '233'
Test #37:
score: 0
Accepted
time: 208ms
memory: 5536kb
input:
800 2 33219 1 3 24476 1 3 44557 1 1 84514 1 4 14659 1 1 62141 1 1 28408 1 3 26361 1 2 60406 1 4 75765 1 2 82764 1 4 57798 1 3 40248 1 3 41219 1 4 36238 1 1 59815 1 1 11587 1 2 25934 1 2 47903 1 2 33165 1 4 53043 1 1 78402 1 3 67224 1 2 43672 1 2 56655 1 2 30009 1 1 31863 1 2 98445 1 1 70192 1 3 3927...
output:
381
result:
ok single line: '381'
Test #38:
score: 0
Accepted
time: 599ms
memory: 5624kb
input:
1968 48 775828552 1 49 129659926 1 43 782523018 1 42 716703760 1 46 788642039 1 43 512170994 1 46 129364119 1 48 201273594 1 43 65172168 1 49 396205350 1 46 603534679 1 40 689641431 1 44 492506422 1 43 325797549 1 42 852455369 1 42 269221916 1 44 30771715 1 41 591385973 1 44 921620444 1 40 722250199...
output:
119
result:
ok single line: '119'
Test #39:
score: 0
Accepted
time: 617ms
memory: 5500kb
input:
2000 40 2 1 44 2 1 46 2 1 46 2 1 50 2 1 46 2 1 43 2 1 46 2 1 50 2 1 40 2 1 44 2 1 42 2 1 41 2 1 47 2 1 50 2 1 44 2 1 44 2 1 43 2 1 43 2 1 47 2 1 44 2 1 47 2 1 42 2 1 49 2 1 45 2 1 46 2 1 40 2 1 40 2 1 47 2 1 40 2 1 41 2 1 50 2 1 48 2 1 48 2 1 42 2 1 42 2 1 50 2 1 46 2 1 45 2 1 46 2 1 50 2 1 48 2 1 5...
output:
44
result:
ok single line: '44'
Subtask #6:
score: 0
Skipped
Dependency #1:
0%