QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798763 | #9672. Roman Numerals | ucup-team004 | AC ✓ | 52ms | 3884kb | C++23 | 1.2kb | 2024-12-04 16:48:42 | 2024-12-04 16:48:45 |
Judging History
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