QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#798763#9672. Roman Numeralsucup-team004AC ✓52ms3884kbC++231.2kb2024-12-04 16:48:422024-12-04 16:48:45

Judging History

你现在查看的是最新测评结果

  • [2024-12-04 16:48:45]
  • 评测
  • 测评结果:AC
  • 用时:52ms
  • 内存:3884kb
  • [2024-12-04 16:48:42]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int V[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 5, 10, 50, 100, 500, 1000};
constexpr int inf = 1E9;

void solve() {
    std::string n;
    std::cin >> n;
    
    std::array<int, 17> c;
    for (int i = 0; i < 17; i++) {
        std::cin >> c[i];
    }
    
    std::vector<int> dp(112, inf);
    i64 cur = 0;
    for (auto _ : n) {
        int d = _ - '0';
        cur = cur * 10 + d;
        std::vector<int> ndp(112, inf);
        for (int i = 0; i < 112; i++) {
            for (int j = 0; j < 17; j++) {
                int r = i * 10 + d - V[j];
                if (0 <= r && r <= 111) {
                    ndp[r] = std::min(ndp[r], dp[i] + c[j]);
                }
            }
        }
        for (int j = 0; j < 17; j++) {
            i64 r = cur - V[j];
            if (0 <= r && r <= 111) {
                ndp[r] = std::min(ndp[r], c[j]);
            }
        }
        std::swap(dp, ndp);
    }
    std::cout << dp[0] << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3676kb

input:

5
102
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
112
1 5 5 1 1 1 1 1 1 1
1 1 1 1 1 1 1
150
1 1 1 1 1 1 1 1 1 1
5 5 5 5 5 5 5
114514
10 5 5 1 1 1 1 1 1 1
1 1 1 1 1 1 1
1919810
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1

output:

2
7
3
6
6

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 11ms
memory: 3708kb

input:

2000
269
2 3 2 2 4 5 5 5 4 5
4 4 2 2 4 1 5
824
2 2 3 5 4 5 4 2 3 5
4 4 4 4 3 4 2
1687
1 2 1 4 4 5 3 5 5 1
4 1 3 1 4 1 5
404
4 4 5 4 5 3 2 3 3 2
3 3 3 3 2 4 5
622
5 1 1 1 2 5 5 2 5 3
2 2 5 4 4 4 1
1576
3 2 1 5 2 4 5 4 5 1
3 5 3 2 1 3 4
211
4 5 4 4 5 2 1 5 2 4
5 2 1 5 2 4 4
1905
1 3 5 4 4 4 5 5 1 2
5 ...

output:

12
10
15
12
7
15
14
9
7
7
10
8
7
8
8
14
7
12
6
6
18
10
9
5
8
8
5
10
6
3
6
11
5
12
5
8
12
12
10
7
8
6
9
12
11
10
6
16
8
3
9
5
9
8
11
10
13
8
10
6
2
10
6
14
11
4
10
9
10
7
8
8
6
7
6
5
8
11
7
10
12
8
9
10
7
6
8
6
7
4
13
4
17
11
11
4
8
13
6
13
8
15
9
5
10
11
11
10
12
11
8
3
8
9
12
11
17
6
13
3
10
3
6
14...

result:

ok 2000 lines

Test #3:

score: 0
Accepted
time: 12ms
memory: 3644kb

input:

2000
672
9999999 9999998 9999996 9999997 10000000 9999999 9999997 10000000 9999996 9999999
9314640 9488995 9532557 9299096 9849641 9257430 9033777
284
9999997 9999996 9999997 9999995 10000000 10000000 10000000 10000000 10000000 10000000
9692000 9904116 9908369 9479290 9509221 9862043 9569004
1825
99...

output:

29999993
29999997
39265704
29538296
39815674
38123541
29999989
29893386
28210567
39939433
29999989
39494370
29999985
29098172
39290220
19033378
29539847
19329537
38815501
29999993
19236316
28961628
38016891
39702526
9479788
19999990
29492874
28522935
39147290
29687093
9179737
39417973
28732959
29147...

result:

ok 2000 lines

Test #4:

score: 0
Accepted
time: 12ms
memory: 3652kb

input:

2000
997
9864608 9140848 9683324 9679700 9767541 9010880 9866039 9108910 9286192 9580767
9999995 10000000 9999999 9999999 9999996 10000000 10000000
206
9717380 9328349 9621557 9939866 9984405 9582976 9522182 9152140 9150277 9568937
9999999 9999999 9999997 9999995 9999998 10000000 9999997
1754
993391...

output:

28270444
28850528
38432383
28945128
38754944
38799627
28654249
37358082
37234376
28173261
29095501
27980514
19464338
28854566
29038010
28133002
29330665
18439360
28777758
37595386
38299390
28482046
37708661
37962133
28502951
19054192
28906209
27051210
19440760
28557895
19760817
28451453
37750541
194...

result:

ok 2000 lines

Test #5:

score: 0
Accepted
time: 12ms
memory: 3812kb

input:

2000
1986
6562476 373300 853204 3955722 7465376 3471513 6782061 6770363 4815249 9440262
3098544 9516481 4913998 3157523 653990 4901757 7799353
672
2247049 2520745 2441923 863302 6828648 8017897 8956381 8318080 6976098 8610282
9592455 8140933 7702622 5575556 6903409 3405061 6674934
1004
1101154 82176...

output:

21410872
19716384
1632537
14894598
11321250
24316204
10730439
20711612
19463846
22111280
11092104
6859939
26853873
11503218
16007380
26548673
15400127
15459622
13057083
19203050
20023355
16649034
6639422
16334338
9670434
10494185
12577327
11163113
31335647
15346594
7016272
5165733
18683249
12439558
...

result:

ok 2000 lines

Test #6:

score: 0
Accepted
time: 50ms
memory: 3620kb

input:

2000
999999999999998939
9999995 9999997 9999995 9999996 10000000 9999999 9999995 9999996 9999999 9999998
9999999 9999997 9999995 9999996 9999995 9999997 9999999
999999999999998523
9999996 9999998 9999999 9999996 10000000 10000000 9999999 10000000 10000000 9999997
9999997 9999996 10000000 9999996 100...

output:

179999963
179999949
179999967
179999959
179999946
179999916
179999947
179999998
179999927
179999948
179999910
179999942
179999996
179999951
179999960
179999996
179999973
179999982
179999962
179999955
179999973
179999981
179999947
179999932
179999958
179999950
179999986
179999983
179999956
179999983
...

result:

ok 2000 lines

Test #7:

score: 0
Accepted
time: 50ms
memory: 3592kb

input:

2000
999999999999998568
1 1 3 3 5 4 2 2 5 5
5 4 3 3 4 4 2
999999999999999662
4 2 3 1 2 3 2 1 2 1
1 2 1 2 4 5 2
999999999999999734
2 1 1 5 1 3 3 4 3 3
5 3 4 5 4 3 2
999999999999998172
1 2 3 4 4 1 2 5 4 3
2 1 5 5 3 5 5
999999999999999706
1 5 3 5 5 5 2 4 1 3
1 1 3 1 3 1 4
999999999999998121
5 4 1 4 2 4...

output:

86
22
55
56
51
66
23
23
36
84
51
25
64
70
48
59
19
86
67
18
55
19
87
23
66
69
35
78
19
43
37
51
54
79
53
37
20
54
49
22
21
80
39
36
70
54
65
19
56
41
87
84
49
75
22
43
22
68
28
65
53
44
59
26
55
84
24
64
70
60
90
38
24
24
83
36
62
48
56
19
52
54
50
63
39
51
67
18
52
88
27
22
21
40
64
29
86
55
66
62
...

result:

ok 2000 lines

Test #8:

score: 0
Accepted
time: 50ms
memory: 3620kb

input:

2000
999999999999998980
9999996 9999996 9999997 9999996 9999995 9999995 9999998 10000000 9999998 9999996
9938398 9328633 9479663 9111274 9291070 9453429 9498300
999999999999999872
9999996 9999995 9999996 10000000 9999995 9999997 9999997 9999995 9999998 9999995
9665974 9906376 9312083 9776141 9166727...

output:

179111208
179999914
179549783
179621936
178081656
179999999
179297562
179999917
179786278
179642218
177341940
179999978
179831944
179129468
179951032
177859469
179999965
178923463
178400077
179425501
179912969
179999963
179015404
179999960
179405986
179999946
178063615
179810056
178066566
179999968
...

result:

ok 2000 lines

Test #9:

score: 0
Accepted
time: 46ms
memory: 3688kb

input:

2000
999999999999998030
9642587 9609617 9136926 9092562 9171564 9605394 9843390 9656844 9205056 9079515
9999996 9999998 10000000 10000000 9999996 9999996 9999996
999999999999998641
9462545 9829491 9368451 9535457 9671827 9696144 9953157 9002169 9734411 9667388
10000000 9999995 9999999 9999995 999999...

output:

164696002
174532318
171433815
165119002
167499572
164267822
169017528
168878691
169821722
166570809
169950269
167789052
178377790
178564145
176683011
170676016
167865958
175353920
174904919
173242512
172814877
172985956
176504635
165606060
163586876
178662490
170782711
177580415
176889055
166331475
...

result:

ok 2000 lines

Test #10:

score: 0
Accepted
time: 50ms
memory: 3588kb

input:

2000
999999999999999981
6639320 2665149 372631 424930 5259275 1636378 3849967 2056563 9294066 716152
9583583 9840890 965502 6676499 9358266 6198887 6508675
999999999999999068
251053 9154805 4034925 83129 6265482 6285355 9804675 9587901 1841909 7636122
6381284 6365198 5710010 2662052 7318671 2355600 ...

output:

23417647
126104211
56011523
150665667
79827756
21228419
92905187
34933886
87383192
144018847
138424286
148990318
136401914
30212572
91390597
109837613
16631599
77141155
46335195
154438267
59834227
137465518
83431774
102346970
147015165
96971966
28756610
68901657
66809166
127718287
18312173
159133168...

result:

ok 2000 lines

Test #11:

score: 0
Accepted
time: 10ms
memory: 3876kb

input:

2000
3036
1 3 4 4 5 1 3 4 4 3
4 3 4 5 3 1 3
3349
5 2 2 5 1 3 1 5 5 2
4 3 5 3 4 5 4
4700
1 5 2 1 1 1 5 5 4 5
1 1 5 5 4 2 3
2681
2 1 1 5 1 5 3 1 1 4
4 3 2 2 5 3 3
3340
1 4 3 1 5 2 4 4 3 2
3 5 3 5 5 1 5
2107
5 4 1 5 2 3 2 4 4 4
4 4 1 5 5 5 1
7891
3 1 1 4 2 5 3 2 4 1
4 1 5 4 3 4 4
8628
1 3 4 2 1 4 4 1 5...

output:

12
13
6
6
6
10
8
18
8
12
11
4
12
11
12
7
14
16
12
8
14
6
12
11
11
10
9
8
14
12
10
14
9
6
9
9
12
6
8
14
11
11
6
8
18
7
8
5
11
7
15
6
14
8
11
13
14
11
10
14
10
9
16
6
16
10
11
13
9
9
10
11
10
13
18
20
15
16
13
8
10
11
10
13
5
8
12
19
14
15
15
13
12
7
6
8
9
10
16
11
8
10
9
11
8
11
10
12
7
11
16
6
12
7
...

result:

ok 2000 lines

Test #12:

score: 0
Accepted
time: 9ms
memory: 3588kb

input:

2000
4137
7498965 9116475 439166 7882111 8038745 5356175 4022605 8220487 2399487 7837173
6497930 5291947 7692655 2141526 950218 9030159 5848135
5914
5850800 6452307 4623914 2118549 6788886 6283679 4038921 2693984 3146923 8029661
1729930 4436256 2224555 9814000 450146 1953473 8340963
5306
1785326 517...

output:

30639273
20984733
13299236
11000448
30933649
13943371
16405806
17225622
20373701
13080136
6811557
24235278
11996579
12661086
19247469
14575941
13888044
7060648
10478712
18399549
6348896
28480464
20195256
33114305
11252487
26165355
26569209
30027260
7755842
13981667
20291296
25590051
11715459
3482144...

result:

ok 2000 lines

Test #13:

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

input:

2000
883282
4376239 288066 232149 9700309 2119719 5422362 9882119 9900938 9421305 6654730
5816642 3059880 2752076 3777187 2475212 8553648 6879526
423851
9119739 2022671 2920299 6479476 7148330 7937306 6312804 4418309 8235469 1644958
2986985 7517711 4602119 8219121 1281678 6909609 9367803
717112
2910...

output:

38428522
34323956
18784578
22179436
12213096
28221935
12278222
32003290
22884365
34617503
26061831
23953913
34314236
16713741
39855247
25881913
44523289
38099623
21482675
24659634
34598498
15437341
38623543
32186489
12650483
20599444
14925253
29560347
41824183
24934639
18028462
27862913
31984186
248...

result:

ok 2000 lines

Test #14:

score: 0
Accepted
time: 26ms
memory: 3588kb

input:

2000
851337096
4032658 3762682 369463 9766214 4844910 4960511 1991070 3903381 9243397 8446438
3738676 104015 1628606 6597508 1153964 6338724 2706227
902279528
9298567 1959336 8096474 7376947 824942 9280451 4921036 7486145 2688396 2405127
920166 5131155 2569865 7944695 4210731 6868756 5474017
1693447...

output:

38716618
47258506
37160253
45898135
42711103
38575493
28407038
37577633
50643551
42103278
38903123
34813224
31182171
67586116
34780344
30118280
18984586
36539937
65115248
23055716
34321699
33969956
31949836
40319061
28084875
41750325
28357638
48037780
15758475
26279606
44360195
20760978
52520484
304...

result:

ok 2000 lines

Test #15:

score: 0
Accepted
time: 34ms
memory: 3884kb

input:

2000
550630272645
6617861 6134766 3559293 4157755 9561201 4841036 8641992 8973104 4247364 3671606
6164510 8284447 6030030 20116 4168233 8291546 8977201
928041469154
3797315 9449384 3740519 3648614 464020 9197676 6003330 8672568 5804875 6781658
3990681 9306054 7434912 2754924 9543247 6211077 8718145
...

output:

48284667
48281801
67198050
44032980
39632213
49991069
68951350
49143154
35617449
28978804
63253553
58419609
59158923
26923729
53176145
32932361
22049776
22432007
35998294
56453674
46998574
40566618
65878336
52091159
44552611
72253717
40620380
36040442
71688454
61257075
41572689
22479222
33165616
515...

result:

ok 2000 lines

Test #16:

score: 0
Accepted
time: 42ms
memory: 3880kb

input:

2000
461154352473492
292349 9039790 7895462 9576186 5957816 6548463 7006934 307078 820131 4760553
1587316 3075014 175815 3023973 4305140 9850876 3025314
331007581439523
227394 6448508 5482561 6170531 197872 4425829 194432 3551535 7279990 8681408
4919929 3827359 5403628 7328079 5601087 7380032 214067...

output:

80173785
67824854
45186899
45204070
89594252
42722415
67172104
88794632
51489097
66873145
54434529
84920957
67495551
50322797
61690318
83465294
40282755
67838870
34864793
38427406
61407073
47933363
73836702
56862821
48400985
80647273
45856932
63674099
46641451
49893872
76694783
40263155
78289888
608...

result:

ok 2000 lines

Test #17:

score: 0
Accepted
time: 52ms
memory: 3876kb

input:

2000
307829925134530904
6148010 6792175 9415326 8128825 7981303 9485075 6452699 9535792 1149598 1764006
8681722 7304510 3535103 8285067 1760584 6617917 7276399
230309627401830372
6696374 7145794 423645 1325110 9992498 4115611 4037411 240145 9150493 3465274
6403685 2965936 3564327 5178937 1361743 777...

output:

95597990
31374912
84796734
82704857
54746945
62592529
82675723
68278656
58591705
97865125
84198760
74868419
63509001
83583375
63008020
63580466
63229007
94920098
48360365
37501714
105547345
77350301
87907925
83446615
93397083
76412928
81216720
101443284
68778205
85612071
65416802
54976397
75009007
7...

result:

ok 2000 lines

Extra Test:

score: 0
Extra Test Passed