QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#590924 | #8048. Roman Master | hcysxnn# | WA | 145ms | 3796kb | C++14 | 1.1kb | 2024-09-26 13:04:50 | 2024-09-26 13:04:51 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i++)
#define dF(i, a, b) for (int i = (a); i >= (b); i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 200005, M = (N << 1), inf = 1e16, mod = 1e9 + 7;
int n, m, a[N], f[N];
map<string, int> mp;
void solve(int TC) {
string s;
cin >> s;
n = s.size();
F(i, 1, n) f[i] = inf;
f[0] = 0;
F(i, 0, n - 1) {
string t = "";
F(j, i + 1, n) {
t += s[j - 1];
if (mp.count(t)) {
f[j] = min(f[j], f[i] * 10 + mp[t]);
}
if (t.size() > 5) break;
}
}
cout << f[n] << '\n';
}
signed main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
mp["I"] = 1;
mp["II"] = 2;
mp["III"] = 3;
mp["IV"] = 4;
mp["V"] = 5;
mp["VI"] = 6;
mp["VII"] = 7;
mp["VIII"] = 8;
int T;
cin >> T;
for (int i = 1; i <= T; i ++) {
solve(i);
}
return 0;
}
// g++ a.cpp -o a -O2 -std=c++14 -fsanitize=undefined,address
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
input:
3 II IVI VIIIIIV
output:
2 16 634
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 125ms
memory: 3588kb
input:
100000 VVIVVVVVII VVVIIIIVVI IVIIVIIIIV VVVVVIIVVI IIIVIVVVIV VIVIIIIIVI VVIIVVIVVI IVVVIVVVVV VIIVVVVIVV VIIIIVVVVV VVVVVVIVIV VIVIIIVVVI VIIIVIVVVI VIIIIVVIIV VIVVVIIVII IIIIIVIIVI IIIIVVVVII IVIIVVIIVI IVVIVVIIIV IVVVIIIVIV IIIIVIIIVV VVVVVIVIIV VVVIIIIVVV VIVVIIIIVI VIIIIIIIIV VIVIVVVIVV IVIIIVI...
output:
5545557 55846 1784 5555646 244554 6736 564546 45545555 6455545 845555 55555544 67456 74456 8464 54577 2376 34557 16476 45474 45744 13745 5555664 558455 54636 6334 5445545 1863 27645 34645 54746 55556455 46345 3746 74546 6633 5455544 738 4776 8666 1455445 555555556 44444 456445 5733 488 5455544 6336 ...
result:
ok 100000 lines
Test #3:
score: -100
Wrong Answer
time: 145ms
memory: 3764kb
input:
10000 VIVVIVIIIIIVVIIVIVVIVIIVVVIVIIVIIVIVVIIVVVIIIIVVIIIIIVVVVVVIIVVVIIVIIVVVIVVIIVIIIVIIIIIVVIIVIVVVVVVI VVIVVVIIVIVVIVIIVVVVVVIVVIIIVIIIIVIVVIIIIIIVIVIIVVIVVIIVVIIVVIIIIIVVVVVIIVIIVVIIVIVVIVIVIIIVIVVIVVVI VIVIVVVVIVVIIVVVIVIVVIVIIIIIIVVVVVVIVIVIIIVIIVIIIVVIVIVIVVIIIVIIVVVIVVVVVVVVVIIIVVIVIIIIIIVI...
output:
10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 10000000000000000 100000000000...
result:
wrong answer 1st lines differ - expected: '5466346446645676446458463455556457645547863464455556', found: '10000000000000000'