Submission #2083417
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define mod 1000000007 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) ll a[20005]; int n; int main(){ cin>>n; repn(i,n) cin>>a[i]; int ans = 0; for(ll t=1,c=0;c<=18;t*=10LL,c++){ vector<ll>vec[10]; repn(i,n){ ll rem = a[i] % (t*10LL); int a = rem/t; vec[a].pb(rem%t); } rep(i,10) SORT(vec[i]); ll mn[10][10],mx[10][10]; rep(i,10)rep(j,10){ mn[i][j] = 1e18; mx[i][j] = -1e18; } rep(i,10){ int sz = vec[i].size(); ll S = 0; for(int j=0;j<=min(10,sz);j++){ mn[i][(i*j)%10] = min(mn[i][(i*j)%10],S); mx[i][(i*j)%10] = max(mx[i][(i*j)%10],S); if(j!=sz) S += vec[i][j]; } S = 0; rep(j,vec[i].size()) S += vec[i][j]; for(int j=0;j<=min(10,sz);j++){ mn[i][(i*(vec[i].size()-j))%10] = min(mn[i][(i*(vec[i].size()-j))%10],S); mx[i][(i*(vec[i].size()-j))%10] = max(mx[i][(i*(vec[i].size()-j))%10],S); if(j!=sz) S -= vec[i][j]; } } ll dp_min[12][10],dp_max[12][10]; rep(i,12)rep(j,10){ dp_min[i][j] = 1e18; dp_max[i][j] = -1e18; } dp_min[0][0] = dp_max[0][0] = 0; rep(i,10){ for(int j=0;j<10;j++){ if(dp_min[i][j] > 5e17) continue; for(int k=0;k<10;k++){ dp_min[i+1][(j+k)%10] = min(dp_min[i+1][(j+k)%10],dp_min[i][j]+mn[i][k]); } } } rep(i,10){ for(int j=0;j<10;j++){ if(dp_max[i][j] < -5e17) continue; for(int k=0;k<10;k++){ dp_max[i+1][(j+k)%10] = max(dp_max[i+1][(j+k)%10],dp_max[i][j]+mx[i][k]); } } } int add = 0; for(int i=0;i<10;i++){ ll MN = 1LL*i+dp_min[10][i]/t; ll MX = 1LL*i+dp_max[10][i]/t; for(ll j=MN;j<=MX;j++){ add = max(add,(int)(j%10)); if(add == 9) break; } } ans += add; //cout<<c<<" "<<add<<endl; } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | B - Exact Payment |
User | IH19980412 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2336 Byte |
Status | WA |
Exec Time | 40 ms |
Memory | 876 KB |
Judge Result
Set Name | sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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, sample-01.txt, sample-02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 256 KB |
01-02.txt | AC | 1 ms | 256 KB |
01-03.txt | AC | 1 ms | 256 KB |
01-04.txt | AC | 1 ms | 256 KB |
01-05.txt | WA | 1 ms | 256 KB |
01-06.txt | AC | 37 ms | 844 KB |
01-07.txt | AC | 37 ms | 868 KB |
01-08.txt | AC | 36 ms | 860 KB |
01-09.txt | AC | 36 ms | 860 KB |
01-10.txt | AC | 34 ms | 860 KB |
01-11.txt | AC | 35 ms | 872 KB |
01-12.txt | AC | 36 ms | 868 KB |
01-13.txt | AC | 36 ms | 872 KB |
01-14.txt | AC | 37 ms | 848 KB |
01-15.txt | AC | 37 ms | 868 KB |
01-16.txt | WA | 36 ms | 868 KB |
01-17.txt | AC | 38 ms | 864 KB |
01-18.txt | AC | 38 ms | 872 KB |
01-19.txt | AC | 38 ms | 864 KB |
01-20.txt | AC | 38 ms | 844 KB |
01-21.txt | AC | 38 ms | 860 KB |
01-22.txt | AC | 38 ms | 864 KB |
01-23.txt | AC | 38 ms | 856 KB |
01-24.txt | AC | 38 ms | 876 KB |
01-25.txt | AC | 38 ms | 864 KB |
01-26.txt | AC | 38 ms | 868 KB |
01-27.txt | AC | 38 ms | 856 KB |
01-28.txt | AC | 39 ms | 856 KB |
01-29.txt | AC | 38 ms | 868 KB |
01-30.txt | AC | 38 ms | 844 KB |
01-31.txt | AC | 38 ms | 848 KB |
01-32.txt | AC | 38 ms | 856 KB |
01-33.txt | AC | 38 ms | 860 KB |
01-34.txt | AC | 38 ms | 856 KB |
01-35.txt | AC | 38 ms | 848 KB |
01-36.txt | AC | 38 ms | 868 KB |
01-37.txt | AC | 39 ms | 868 KB |
01-38.txt | AC | 38 ms | 860 KB |
01-39.txt | AC | 38 ms | 860 KB |
01-40.txt | AC | 38 ms | 856 KB |
01-41.txt | AC | 38 ms | 852 KB |
01-42.txt | AC | 39 ms | 852 KB |
01-43.txt | AC | 38 ms | 864 KB |
01-44.txt | AC | 35 ms | 860 KB |
01-45.txt | AC | 36 ms | 856 KB |
01-46.txt | AC | 38 ms | 856 KB |
01-47.txt | AC | 38 ms | 860 KB |
01-48.txt | AC | 38 ms | 844 KB |
01-49.txt | AC | 38 ms | 872 KB |
01-50.txt | AC | 38 ms | 868 KB |
01-51.txt | AC | 38 ms | 868 KB |
01-52.txt | AC | 38 ms | 844 KB |
01-53.txt | AC | 38 ms | 844 KB |
01-54.txt | AC | 40 ms | 876 KB |
01-55.txt | AC | 38 ms | 848 KB |
01-56.txt | AC | 38 ms | 864 KB |
01-57.txt | AC | 38 ms | 864 KB |
01-58.txt | AC | 38 ms | 860 KB |
01-59.txt | AC | 38 ms | 860 KB |
01-60.txt | AC | 38 ms | 872 KB |
01-61.txt | AC | 38 ms | 868 KB |
01-62.txt | AC | 38 ms | 848 KB |
01-63.txt | AC | 38 ms | 856 KB |
01-64.txt | AC | 38 ms | 864 KB |
01-65.txt | AC | 38 ms | 852 KB |
01-66.txt | AC | 26 ms | 860 KB |
01-67.txt | AC | 30 ms | 852 KB |
01-68.txt | AC | 30 ms | 860 KB |
01-69.txt | AC | 30 ms | 860 KB |
01-70.txt | AC | 30 ms | 844 KB |
01-71.txt | AC | 27 ms | 860 KB |
01-72.txt | AC | 27 ms | 860 KB |
01-73.txt | AC | 27 ms | 860 KB |
01-74.txt | AC | 27 ms | 860 KB |
01-75.txt | AC | 27 ms | 860 KB |
01-76.txt | AC | 27 ms | 860 KB |
01-77.txt | AC | 30 ms | 856 KB |
01-78.txt | AC | 27 ms | 860 KB |
01-79.txt | AC | 27 ms | 860 KB |
01-80.txt | AC | 27 ms | 860 KB |
01-81.txt | AC | 27 ms | 860 KB |
01-82.txt | AC | 27 ms | 860 KB |
01-83.txt | AC | 27 ms | 860 KB |
01-84.txt | AC | 27 ms | 860 KB |
01-85.txt | AC | 27 ms | 860 KB |
01-86.txt | AC | 27 ms | 860 KB |
01-87.txt | AC | 27 ms | 860 KB |
01-88.txt | AC | 27 ms | 860 KB |
01-89.txt | AC | 27 ms | 860 KB |
01-90.txt | AC | 30 ms | 872 KB |
01-91.txt | AC | 27 ms | 860 KB |
01-92.txt | AC | 27 ms | 860 KB |
01-93.txt | AC | 27 ms | 860 KB |
01-94.txt | AC | 27 ms | 860 KB |
01-95.txt | AC | 27 ms | 860 KB |
01-96.txt | AC | 30 ms | 864 KB |
01-97.txt | AC | 27 ms | 860 KB |
01-98.txt | AC | 27 ms | 860 KB |
sample-01.txt | AC | 1 ms | 256 KB |
sample-02.txt | AC | 1 ms | 256 KB |