結果
問題 |
No.1231 Make a Multiple of Ten
|
ユーザー |
![]() |
提出日時 | 2020-09-24 23:27:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 2,842 bytes |
コンパイル時間 | 1,802 ms |
コンパイル使用メモリ | 199,660 KB |
最終ジャッジ日時 | 2025-01-14 20:11:41 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; const double pi=3.141592653589793; typedef unsigned long long ull; typedef long double ldouble; const ll INF=1e18; #define rep(i, n) for(int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template <int mod> struct ModInt { int val; ModInt() : val(0) {} ModInt(long long x) : val(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {} int getmod() { return mod; } ModInt &operator+=(const ModInt &p) { if ((val += p.val) >= mod) { val -= mod; } return *this; } ModInt &operator-=(const ModInt &p) { if ((val += mod - p.val) >= mod) { val -= mod; } return *this; } ModInt &operator*=(const ModInt &p) { val = (int)(1LL * val * p.val % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-val); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return val == p.val; } bool operator!=(const ModInt &p) const { return val != p.val; } ModInt inverse() const { int a = val, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(long long n) const { ModInt ret(1), mul(val); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.val; } friend istream &operator>>(istream &is, ModInt &a) { long long t; is >> t; a = ModInt<mod>(t); return (is); } static int get_mod() { return mod; } }; const int MOD = 10; // if inv is needed, this shold be prime. using modint = ModInt<MOD>; int main(){ int n; modint count = 0; cin >> n; vector<int> a(n); vector<vector<ll> > dp(n+1, vector<ll> (10, -1*INF)); rep(i, n) { cin >> a[i]; a[i] %= 10; } dp[0][0] = 0; rep(i, n) { rep(j, 10) { dp[i+1][j] = max(dp[i][j], dp[i][(j-a[i]+100)%10] + 1); } } cout << dp[n][0] << endl; }