Submission #995725
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define sqr(x) ((x) * (x)) #define pb push_back #define mp make_pair #define ins insert #define er erase #define bg begin() #define ed end() #define X first #define Y second #define fin(name) freopen(name, "r", stdin) #define fout(name) freopen(name, "w", stdout) #define files(name) fin(name".in"); fout(name".out") #define enter cout << "\n" #define space cout << " " #define endl "\n" #define fi(st,n) for (int i = (st); i <= (n); ++i) #define fj(st,n) for (int j = (st); j <= (n); ++j) #define fk(st,n) for (int k = (st); k <= (n); ++k) #define fq(st,n) for (int q = (st); q <= (n); ++q) #define fw(st,n) for (int w = (st); w <= (n); ++w) #define ff(i, st, n) for (int (i) = (st); (i) <= (n); ++(i)) #define ei(st,n) for (int i = (st); i >= (n); --i) #define ej(st,n) for (int j = (st); j >= (n); --j) #define ek(st,n) for (int k = (st); k >= (n); --k) #define ef(i, st, n) for (int (i) = (st); (i) >= (n); --(i)) #define ri(st,n) for (int i = (st); i < (n); ++i) #define rj(st,n) for (int j = (st); j < (n); ++j) #define rk(st,n) for (int k = (st); k < (n); ++k) #define rq(st,n) for (int q = (st); q < (n); ++q) #define rf(i, st, n) for (int (i) = (st); (i) < (n); ++(i)) #define clean(a) memset((a),0,sizeof (a)) #define sync ios_base::sync_with_stdio(0);cin.tie(0) #define y1 dsklmlvmd typedef long long ll; typedef unsigned long long ull; typedef double dbl; typedef long double ldbl; typedef pair<int, int> pii; typedef vector<int> vi; const int inf = (int)1e9; const dbl eps = (dbl) 1e-8; const int mod = (int) 10000007; const int maxn = (int) 2 * 1e4 + 5; //const dbl M_PI = (dbl)2 * (dbl)acos(0); //cout<<fixed<<setprecision(10); //srand(time(0)); ll ans; ll n, a[maxn], st, s, tok; pair <ll, ll> d[maxn][11]; int main() { // fin("t.in"); sync; cin >> n; fi(1, n) { cin >> a[i]; } ans = 0; st = 1; fi(0, 18) { memset(d, -1, sizeof d); d[1][0].X = 0; d[1][0].Y = 0; fj(1, n) { fk(0, 9) { d[j + 1][k] = d[j][k]; } fk(0, 9) { if (d[j][k].X == -1) continue; s = d[j][k].X + a[j]; tok = ((ll)k + (s / st)) % 10; if (d[j + 1][tok].X == -1) d[j + 1][tok] = mp(s % st, s % st); d[j + 1][tok].X = min(d[j + 1][tok].X, s % st); d[j + 1][tok].Y = max(d[j + 1][tok].Y, s % st); s = d[j][k].Y + a[j]; tok = ((ll)k + (s / st)) % 10; if (d[j + 1][tok].X == -1) d[j + 1][tok] = mp(s % st, s % st); d[j + 1][tok].X = min(d[j + 1][tok].X, s % st); d[j + 1][tok].Y = max(d[j + 1][tok].Y, s % st); } } ej(9, 1) { if (d[n + 1][j].X != -1) { ans += j; // cout << j << endl; break; } } st *= 10; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - Exact Payment |
User | mHuman |
Language | C++14 (GCC 5.4.1) |
Score | 1500 |
Code Size | 2930 Byte |
Status | AC |
Exec Time | 123 ms |
Memory | 3968 KB |
Judge Result
Set Name | sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
All | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 01-47.txt, 01-48.txt, 01-49.txt, 01-50.txt, 01-51.txt, 01-52.txt, 01-53.txt, 01-54.txt, 01-55.txt, 01-56.txt, 01-57.txt, 01-58.txt, 01-59.txt, 01-60.txt, 01-61.txt, 01-62.txt, 01-63.txt, 01-64.txt, 01-65.txt, 01-66.txt, 01-67.txt, 01-68.txt, 01-69.txt, 01-70.txt, 01-71.txt, 01-72.txt, 01-73.txt, 01-74.txt, 01-75.txt, 01-76.txt, 01-77.txt, 01-78.txt, 01-79.txt, 01-80.txt, 01-81.txt, 01-82.txt, 01-83.txt, 01-84.txt, 01-85.txt, 01-86.txt, 01-87.txt, 01-88.txt, 01-89.txt, 01-90.txt, 01-91.txt, 01-92.txt, 01-93.txt, 01-94.txt, 01-95.txt, 01-96.txt, 01-97.txt, 01-98.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 8 ms | 3712 KB |
01-02.txt | AC | 8 ms | 3712 KB |
01-03.txt | AC | 8 ms | 3712 KB |
01-04.txt | AC | 8 ms | 3712 KB |
01-05.txt | AC | 8 ms | 3712 KB |
01-06.txt | AC | 123 ms | 3840 KB |
01-07.txt | AC | 120 ms | 3840 KB |
01-08.txt | AC | 118 ms | 3840 KB |
01-09.txt | AC | 117 ms | 3840 KB |
01-10.txt | AC | 95 ms | 3840 KB |
01-11.txt | AC | 99 ms | 3968 KB |
01-12.txt | AC | 120 ms | 3840 KB |
01-13.txt | AC | 120 ms | 3840 KB |
01-14.txt | AC | 123 ms | 3840 KB |
01-15.txt | AC | 120 ms | 3840 KB |
01-16.txt | AC | 114 ms | 3840 KB |
01-17.txt | AC | 116 ms | 3840 KB |
01-18.txt | AC | 116 ms | 3840 KB |
01-19.txt | AC | 117 ms | 3840 KB |
01-20.txt | AC | 117 ms | 3840 KB |
01-21.txt | AC | 116 ms | 3840 KB |
01-22.txt | AC | 116 ms | 3840 KB |
01-23.txt | AC | 116 ms | 3840 KB |
01-24.txt | AC | 114 ms | 3840 KB |
01-25.txt | AC | 114 ms | 3968 KB |
01-26.txt | AC | 117 ms | 3840 KB |
01-27.txt | AC | 118 ms | 3840 KB |
01-28.txt | AC | 116 ms | 3840 KB |
01-29.txt | AC | 114 ms | 3840 KB |
01-30.txt | AC | 117 ms | 3840 KB |
01-31.txt | AC | 116 ms | 3968 KB |
01-32.txt | AC | 114 ms | 3840 KB |
01-33.txt | AC | 114 ms | 3840 KB |
01-34.txt | AC | 116 ms | 3840 KB |
01-35.txt | AC | 118 ms | 3840 KB |
01-36.txt | AC | 114 ms | 3840 KB |
01-37.txt | AC | 116 ms | 3840 KB |
01-38.txt | AC | 117 ms | 3840 KB |
01-39.txt | AC | 116 ms | 3840 KB |
01-40.txt | AC | 116 ms | 3840 KB |
01-41.txt | AC | 116 ms | 3840 KB |
01-42.txt | AC | 116 ms | 3840 KB |
01-43.txt | AC | 116 ms | 3840 KB |
01-44.txt | AC | 121 ms | 3840 KB |
01-45.txt | AC | 120 ms | 3840 KB |
01-46.txt | AC | 118 ms | 3840 KB |
01-47.txt | AC | 118 ms | 3968 KB |
01-48.txt | AC | 118 ms | 3840 KB |
01-49.txt | AC | 116 ms | 3840 KB |
01-50.txt | AC | 116 ms | 3840 KB |
01-51.txt | AC | 117 ms | 3840 KB |
01-52.txt | AC | 118 ms | 3840 KB |
01-53.txt | AC | 118 ms | 3840 KB |
01-54.txt | AC | 119 ms | 3840 KB |
01-55.txt | AC | 116 ms | 3840 KB |
01-56.txt | AC | 116 ms | 3840 KB |
01-57.txt | AC | 116 ms | 3840 KB |
01-58.txt | AC | 121 ms | 3840 KB |
01-59.txt | AC | 121 ms | 3840 KB |
01-60.txt | AC | 121 ms | 3840 KB |
01-61.txt | AC | 122 ms | 3840 KB |
01-62.txt | AC | 117 ms | 3840 KB |
01-63.txt | AC | 117 ms | 3840 KB |
01-64.txt | AC | 118 ms | 3840 KB |
01-65.txt | AC | 118 ms | 3840 KB |
01-66.txt | AC | 51 ms | 3840 KB |
01-67.txt | AC | 84 ms | 3840 KB |
01-68.txt | AC | 91 ms | 3840 KB |
01-69.txt | AC | 93 ms | 3840 KB |
01-70.txt | AC | 89 ms | 3840 KB |
01-71.txt | AC | 63 ms | 3840 KB |
01-72.txt | AC | 59 ms | 3840 KB |
01-73.txt | AC | 62 ms | 3840 KB |
01-74.txt | AC | 62 ms | 3840 KB |
01-75.txt | AC | 59 ms | 3840 KB |
01-76.txt | AC | 60 ms | 3840 KB |
01-77.txt | AC | 98 ms | 3840 KB |
01-78.txt | AC | 65 ms | 3840 KB |
01-79.txt | AC | 64 ms | 3840 KB |
01-80.txt | AC | 64 ms | 3840 KB |
01-81.txt | AC | 68 ms | 3840 KB |
01-82.txt | AC | 67 ms | 3840 KB |
01-83.txt | AC | 64 ms | 3840 KB |
01-84.txt | AC | 62 ms | 3840 KB |
01-85.txt | AC | 69 ms | 3840 KB |
01-86.txt | AC | 64 ms | 3840 KB |
01-87.txt | AC | 63 ms | 3840 KB |
01-88.txt | AC | 63 ms | 3840 KB |
01-89.txt | AC | 63 ms | 3840 KB |
01-90.txt | AC | 103 ms | 3840 KB |
01-91.txt | AC | 77 ms | 3840 KB |
01-92.txt | AC | 66 ms | 3840 KB |
01-93.txt | AC | 71 ms | 3840 KB |
01-94.txt | AC | 74 ms | 3840 KB |
01-95.txt | AC | 66 ms | 3840 KB |
01-96.txt | AC | 105 ms | 3840 KB |
01-97.txt | AC | 72 ms | 3840 KB |
01-98.txt | AC | 77 ms | 3840 KB |
sample-01.txt | AC | 8 ms | 3712 KB |
sample-02.txt | AC | 8 ms | 3712 KB |