QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#640842 | #6257. Efficient Exchange | chanuuu# | WA | 0ms | 3792kb | C++17 | 823b | 2024-10-14 16:28:03 | 2024-10-14 16:28:03 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
ll dp[1010][2];
ll a[1010];
int chk[1010];
int n;
ll solve(int i, int k){
if(dp[i][k] ^ -1) return dp[i][k];
ll s = a[i];
if(!chk[i]){
if(k) dp[i][k] = 10 - s;
else dp[i][k] = s;
return dp[i][k];
}
if(k) {
s = (10 - s) % 10;
s--;
}
return dp[i][k] = min(solve(i + 1, k), solve(i + 1, k ^ 1) + 1) + s;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
string s; cin>>s;
n = s.size();
for(int i = 0; i < n; i++) a[i] = s[i] - '0';
for(int i = 0; i < n; i++) for(int k = 0; k < 2; k++) dp[i][k] = -1;
for(int k = n - 1; k >= 1; k--) if(a[k] || chk[k]) chk[k - 1] = 1;
cout << min(solve(0, 0), solve(0, 1) + 1);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
83
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
13
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
0
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
12345678987654321
output:
42
result:
ok single line: '42'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1
output:
1
result:
ok single line: '1'
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3640kb
input:
108894478469214466804158556038509473912228070531930682335592810379690071992846446138400855834536144291684432969861435324866089578025171848195442401602361161260026599515983657327709498488895075795438278518721851530339458103065105649832422088699047412786278455363479689485262210227415931822805287251225...
output:
1856
result:
wrong answer 1st lines differ - expected: '1971', found: '1856'