QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#838272#795. Cloud Computingnhuang685#36 92ms3964kbC++231.5kb2024-12-31 02:54:512024-12-31 02:54:51

Judging History

This is the latest submission verdict.

  • [2024-12-31 02:54:51]
  • Judged
  • Verdict: 36
  • Time: 92ms
  • Memory: 3964kb
  • [2024-12-31 02:54:51]
  • Submitted

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int MAXC = 20;
constexpr i64 INF = 0x3f3f3f3f3f3f3f3f;

int main() {
  std::ios::sync_with_stdio(false);

  int n;
  std::cin >> n;

  std::vector<std::tuple<int, int, i64>> comp(n);
  std::vector<int> cc;
  for (auto& [c, f, v] : comp) {
    std::cin >> c >> f >> v;
    cc.push_back(f);
  }

  int m;
  std::cin >> m;
  std::vector<std::tuple<int, int, i64>> ord(m);
  for (auto& [c, f, v] : ord) {
    std::cin >> c >> f >> v;
    cc.push_back(f);
  }
  std::sort(cc.begin(), cc.end());
  cc.erase(std::unique(cc.begin(), cc.end()), cc.end());
  int k = static_cast<int>(cc.size());

  std::vector<std::vector<std::pair<int, int>>> tr_comp(k), tr_ord(k);
  for (auto& [c, f, v] : comp) {
    f = static_cast<int>(
      std::lower_bound(cc.begin(), cc.end(), f) - cc.begin()
    );
    tr_comp[f].emplace_back(c, v);
  }
  for (auto& [c, f, v] : ord) {
    f = static_cast<int>(
      std::lower_bound(cc.begin(), cc.end(), f) - cc.begin()
    );
    tr_ord[f].emplace_back(c, v);
  }

  int mx = MAXC * n;
  std::vector<i64> dp(mx + 1, -INF);
  dp[0] = 0;
  for (int f = k - 1; f >= 0; --f) {
    for (auto [c, v] : tr_comp[f]) {
      for (int j = mx; j >= c; --j) {
        dp[j] = std::max(dp[j], dp[j - c] - v);
      }
    }
    for (auto [c, v] : tr_ord[f]) {
      for (int j = 0; j <= mx - c; ++j) {
        dp[j] = std::max(dp[j], dp[j + c] + v);
      }
    }
  }
  std::cout << *std::max_element(dp.begin(), dp.end()) << '\n';
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 18
Accepted
time: 0ms
memory: 3716kb

input:

1
3 3253 744
1
1 2012 798

output:

54

result:

ok single line: '54'

Test #2:

score: 18
Accepted
time: 0ms
memory: 3532kb

input:

1
1 2291 728
1
3 3024 858

output:

0

result:

ok single line: '0'

Test #3:

score: 18
Accepted
time: 0ms
memory: 3608kb

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:

368159

result:

ok single line: '368159'

Test #4:

score: 18
Accepted
time: 0ms
memory: 3804kb

input:

7
11 6380 2002853
5 6813 1069986
13 5521 2570534
12 5793 1980585
9 6767 423810
19 5421 2358687
3 6223 527470
200
2 5408 222070
2 5072 205933
1 5263 95185
2 4419 43779
2 4337 128477
1 4234 73697
2 3655 35020
1 3599 60877
1 3391 14190
1 4499 59363
3 5218 428777
1 3617 15308
1 3932 67554
1 3847 16460
2...

output:

909469

result:

ok single line: '909469'

Test #5:

score: 18
Accepted
time: 1ms
memory: 3908kb

input:

15
38 253050473 94982
19 873235634 3331
34 96232154 99722
18 361560017 18236
1 43839514 70819
30 211957237 36759
21 276441039 97496
10 677009897 39625
43 899961447 35095
15 278681496 20167
16 777735821 93692
39 295651318 33500
40 814700985 79446
14 174272701 32273
33 149679268 37695
1900
23 83103560...

output:

7591941

result:

ok single line: '7591941'

Test #6:

score: 18
Accepted
time: 2ms
memory: 3660kb

input:

15
2 26589073 403672469
1 41525134 919365487
1 20631561 281192925
1 102777840 841011960
1 39965286 293659571
1 25731340 899094489
2 13795262 388700479
2 28949306 887569930
2 28301652 432739525
3 21401611 995905557
1 12908533 333560050
1 72630405 571268998
1 34438002 497580454
1 69595535 544742664
1 ...

output:

8077488943

result:

ok single line: '8077488943'

Test #7:

score: 18
Accepted
time: 1ms
memory: 3668kb

input:

15
48 695425366 943332504
45 712641768 231446475
47 634507753 371099212
48 428534339 104593262
46 729756277 470795290
50 928986319 548613644
50 788811011 128576493
48 345438587 877886664
47 925824152 799912937
47 313626363 126112358
46 451672372 689015214
50 838817670 270199427
48 150219527 52297669...

output:

7473136555

result:

ok single line: '7473136555'

Test #8:

score: 0
Wrong Answer
time: 1ms
memory: 3788kb

input:

15
41 18252721 748361561
41 23829617 977014296
46 13332057 613274621
42 21746541 913354722
47 12012296 564577912
42 16440276 690491591
46 12022310 553026259
50 15767600 788380000
41 19620669 804447428
46 17824167 819911682
50 14624259 731212950
41 14693399 602429359
46 20592200 947241200
49 14448618...

output:

3675740527

result:

wrong answer 1st lines differ - expected: '4484130835', found: '3675740527'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 18
Accepted

Test #18:

score: 18
Accepted
time: 0ms
memory: 3608kb

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: 18
Accepted
time: 0ms
memory: 3584kb

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: 18
Accepted
time: 1ms
memory: 3548kb

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: 18
Accepted
time: 1ms
memory: 3808kb

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: 18
Accepted
time: 2ms
memory: 3860kb

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: 18
Accepted
time: 2ms
memory: 3812kb

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: 18
Accepted
time: 2ms
memory: 3564kb

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: 18
Accepted
time: 2ms
memory: 3832kb

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: 0
Wrong Answer

Test #26:

score: 18
Accepted
time: 0ms
memory: 3472kb

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: 18
Accepted
time: 0ms
memory: 3612kb

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: 18
Accepted
time: 28ms
memory: 3788kb

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
Wrong Answer
time: 1ms
memory: 3684kb

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:

101573

result:

wrong answer 1st lines differ - expected: '102484', found: '101573'

Subtask #5:

score: 18
Accepted

Test #34:

score: 18
Accepted
time: 0ms
memory: 3468kb

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: 18
Accepted
time: 1ms
memory: 3760kb

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: 18
Accepted
time: 6ms
memory: 3908kb

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: 18
Accepted
time: 20ms
memory: 3964kb

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: 18
Accepted
time: 92ms
memory: 3920kb

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: 18
Accepted
time: 91ms
memory: 3852kb

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%