結果
問題 | No.1231 Make a Multiple of Ten |
ユーザー | w2w2 |
提出日時 | 2020-09-18 22:53:11 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 25 ms / 2,000 ms |
コード長 | 1,794 bytes |
コンパイル時間 | 2,033 ms |
コンパイル使用メモリ | 204,600 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-05 18:23:26 |
合計ジャッジ時間 | 3,142 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 12 ms
4,380 KB |
testcase_05 | AC | 11 ms
4,380 KB |
testcase_06 | AC | 6 ms
4,376 KB |
testcase_07 | AC | 12 ms
4,376 KB |
testcase_08 | AC | 6 ms
4,376 KB |
testcase_09 | AC | 4 ms
4,376 KB |
testcase_10 | AC | 11 ms
4,380 KB |
testcase_11 | AC | 13 ms
4,376 KB |
testcase_12 | AC | 24 ms
4,376 KB |
testcase_13 | AC | 25 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 25 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using vl = vector<ll>; using vd = vector<ld>; using vs = vector<string>; using vb = vector<bool>; using vvl = vector<vector<ll>>; using vvd = vector<vector<ld>>; using vvs = vector<vector<string>>; using vvb = vector<vector<bool>>; using pll = pair<ll, ll>; constexpr ll mod= 1e9 + 7; #define ALL(x) (x).begin(), (x).end() #define REP(i, n) for(ll(i)= 0; (i) < (n); (i)++) #define REPS(i, n) for(ll(i)= 1; (i) <= (n); (i)++) #define RREP(i, n) for(ll(i)= (n - 1); (i) >= 0; (i)--) #define RREPS(i, n) for(ll(i)= (n); (i) > 0; (i)--) #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define UNIQUE(v) v.erase(unique(ALL(v)), v.end()) #define YES(n) ((n) ? "YES" : "NO") #define Yes(n) ((n) ? "Yes" : "No") #define yes(n) ((n) ? "yes" : "no") template <class T> inline void chmin(T& a, T b) { if(a > b) { a= b; } } template <class T> inline void chmax(T& a, T b) { if(a < b) { a= b; } } signed main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12); vl ten(10); ll N; cin >> N; REP(i,N){ ll tmp; cin >> tmp; ten[tmp%10]++; } vvl dp(11,vl(10,-500000000000)); dp[0][0] = 0; REP(i,10){ vl tes(10); REP(l,10){ chmax(tes[i*l%10],max((ll)0,(ten[i]%10 >= l ?10*(ten[i]/10) + l : 10*(ten[i]/10 - 1)+ l))); } REP(l,10){ chmax(dp[i+1][l],dp[i][l]); REP(k,10){ chmax(dp[i+1][(l+k)%10],(tes[k] != 0 ? dp[i][l] + tes[k] : -500000000000)); } } } cout << dp[10][0] << "\n"; }