QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133868 | #6257. Efficient Exchange | KhNURE_KIVI# | WA | 1ms | 3568kb | C++14 | 2.5kb | 2023-08-02 15:58:14 | 2023-08-02 15:58:15 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
inline bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
inline bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL
const int max_n = -1, inf = 1000111222;
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
int n = len(s);
int dp[2] = {0, inf};
vector <int> suff(n + 1);
bool ok = false;
for (int i = n - 1; i >= 0; i--) {
if (s[i] != '0') {
ok = true;
}
suff[i] = ok;
}
for (int i = 0; i < n; i++) {
int cur = s[i] - '0';
int only_zero = suff[i + 1];
int new_dp[2] = {inf, inf};
for (int f = 0; f < 2; f++) {
int val = f ? (10 - cur - only_zero) : cur;
umin(new_dp[f], dp[f] + val);
umin(new_dp[f ^ 1], dp[f] + (11 - val - only_zero));
}
dp[0] = new_dp[0];
dp[1] = new_dp[1];
LOG(dp[0], dp[1]);
}
cout << min(dp[0], dp[1]) << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3444kb
input:
83
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
13
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3564kb
input:
0
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
12345678987654321
output:
42
result:
ok single line: '42'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
1
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
108894478469214466804158556038509473912228070531930682335592810379690071992846446138400855834536144291684432969861435324866089578025171848195442401602361161260026599515983657327709498488895075795438278518721851530339458103065105649832422088699047412786278455363479689485262210227415931822805287251225...
output:
1971
result:
ok single line: '1971'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
155657272188452258350034380622506009947304059264052627243071743747532300522919572993515854882869064965994030247295293351158207123830911435744207850943972297748665270071798324245389096610864530828634938222945980818832206282110768734660809669941759092258710662899974508400631678381569312965707983946432
output:
727
result:
ok single line: '727'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
184293602707127482667135655938747789712189649148930742992933133452462900071840556139777075958677006206950802685360638631097097555913098361665555519075109818871319874846199491028725782220390691671918986736126038811707738246531755860287041942198563406450643429071794580502357738722260280221637052566622...
output:
1388
result:
ok single line: '1388'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
10
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
100
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3496kb
input:
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
2
result:
ok single line: '2'
Test #12:
score: -100
Wrong Answer
time: 1ms
memory: 3476kb
input:
927921025314975768131904512726117652463595287536883360313991521661524926483956016479890394072472783724117472774060584557954348768216323088030199807746884216789632406284551408158333612255548346529968167404891207258991365367362134354507171299646862083803338315300776525592155222220598847462648664077391...
output:
2532
result:
wrong answer 1st lines differ - expected: '2531', found: '2532'