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
AC × 2
AC × 100
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