QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#412009#795. Cloud Computingsichengzhou54 646ms5624kbC++141.9kb2024-05-15 22:54:082024-05-15 22:54:09

Judging History

This is the latest submission verdict.

  • [2024-05-15 22:54:09]
  • Judged
  • Verdict: 54
  • Time: 646ms
  • Memory: 5624kb
  • [2024-05-15 22:54:08]
  • Submitted

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
*/

詳細信息

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%