結果
| 問題 | No.1231 Make a Multiple of Ten |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2020-09-18 22:07:25 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 31 ms / 2,000 ms |
| コード長 | 7,626 bytes |
| コンパイル時間 | 2,096 ms |
| コンパイル使用メモリ | 193,488 KB |
| 最終ジャッジ日時 | 2025-01-14 17:14:40 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:289:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
289 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
main.cpp:292:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
292 | rep(i, n) scanf("%d", &a[i]), ++cnt[a[i] % 10];
| ~~~~~^~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define For(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); ++(i))#define rFor(i, a, b) for (int(i) = (int)(a)-1; (i) >= (int)(b); --(i))#define rep(i, n) For((i), 0, (n))#define rrep(i, n) rFor((i), (n), 0)#define fi first#define se secondusing namespace std;typedef long long lint;typedef unsigned long long ulint;typedef pair<int, int> pii;typedef pair<lint, lint> pll;template <class T>bool chmax(T &a, const T &b) {if (a < b) {a = b;return true;}return false;}template <class T>bool chmin(T &a, const T &b) {if (a > b) {a = b;return true;}return false;}template <class T>T div_floor(T a, T b) {if (b < 0) a *= -1, b *= -1;return a >= 0 ? a / b : (a + 1) / b - 1;}template <class T>T div_ceil(T a, T b) {if (b < 0) a *= -1, b *= -1;return a > 0 ? (a - 1) / b + 1 : a / b;}constexpr lint mod = 1000000007;constexpr lint INF = mod * mod;constexpr int MAX = 100010;#ifndef ATCODER_INTERNAL_BITOP_HPP#define ATCODER_INTERNAL_BITOP_HPP 1#ifdef _MSC_VER#include <intrin.h>#endifnamespace atcoder {namespace internal {// @param n `0 <= n`// @return minimum non-negative `x` s.t. `n <= 2**x`int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}// @param n `1 <= n`// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`int bsf(unsigned int n) {#ifdef _MSC_VERunsigned long index;_BitScanForward(&index, n);return index;#elsereturn __builtin_ctz(n);#endif}} // namespace internal} // namespace atcoder#endif // ATCODER_INTERNAL_BITOP_HPP#ifndef ATCODER_LAZYSEGTREE_HPP#define ATCODER_LAZYSEGTREE_HPP 1namespace atcoder {template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S),F (*composition)(F, F), F (*id)()>struct lazy_segtree {public:lazy_segtree() : lazy_segtree(0) {}lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {log = internal::ceil_pow2(_n);size = 1 << log;d = std::vector<S>(2 * size, e());lz = std::vector<F>(size, id());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update(i);}}void set(int p, S x) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);return d[p];}S prod(int l, int r) {assert(0 <= l && l <= r && r <= _n);if (l == r) return e();l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push(r >> i);}S sml = e(), smr = e();while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_prod() { return d[1]; }void apply(int p, F f) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = mapping(f, d[p]);for (int i = 1; i <= log; i++) update(p >> i);}void apply(int l, int r, F f) {assert(0 <= l && l <= r && r <= _n);if (l == r) return;l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}{int l2 = l, r2 = r;while (l < r) {if (l & 1) all_apply(l++, f);if (r & 1) all_apply(--r, f);l >>= 1;r >>= 1;}l = l2;r = r2;}for (int i = 1; i <= log; i++) {if (((l >> i) << i) != l) update(l >> i);if (((r >> i) << i) != r) update((r - 1) >> i);}}template <bool (*g)(S)>int max_right(int l) {return max_right(l, [](S x) { return g(x); });}template <class G>int max_right(int l, G g) {assert(0 <= l && l <= _n);assert(g(e()));if (l == _n) return _n;l += size;for (int i = log; i >= 1; i--) push(l >> i);S sm = e();do {while (l % 2 == 0) l >>= 1;if (!g(op(sm, d[l]))) {while (l < size) {push(l);l = (2 * l);if (g(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*g)(S)>int min_left(int r) {return min_left(r, [](S x) { return g(x); });}template <class G>int min_left(int r, G g) {assert(0 <= r && r <= _n);assert(g(e()));if (r == 0) return 0;r += size;for (int i = log; i >= 1; i--) push((r - 1) >> i);S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!g(op(d[r], sm))) {while (r < size) {push(r);r = (2 * r + 1);if (g(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;std::vector<F> lz;void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }void all_apply(int k, F f) {d[k] = mapping(f, d[k]);if (k < size) lz[k] = composition(f, lz[k]);}void push(int k) {all_apply(2 * k, lz[k]);all_apply(2 * k + 1, lz[k]);lz[k] = id();}};} // namespace atcoder#endif // ATCODER_LAZYSEGTREE_HPPusing namespace atcoder;struct monoid {lint val;static monoid op(monoid lhs, monoid rhs) { return {min(lhs.val, rhs.val)}; }static monoid e() { return {INF}; }};struct op_monoid {lint sum;static monoid mapping(op_monoid lhs, monoid rhs) {return {rhs.val + lhs.sum};}static op_monoid compression(op_monoid lhs, op_monoid rhs) {return {lhs.sum + rhs.sum};}static op_monoid id() { return {0}; }};int main() {int n;scanf("%d", &n);int a[n], cnt[10];memset(cnt, 0, sizeof(cnt));rep(i, n) scanf("%d", &a[i]), ++cnt[a[i] % 10];int mx[10][10];rep(i, 10) rep(j, 10) mx[i][j] = -1;rep(i, 10) {int cur = 0;mx[i][0] = 0;rep(k, cnt[i]) {(cur += i) %= 10;mx[i][cur] = k + 1;}}int dp[11][10];rep(i, 11) rep(j, 10) dp[i][j] = -1;dp[0][0] = 0;rep(i, 10) rep(j, 10) if (dp[i][j] >= 0) {chmax(dp[i + 1][j], dp[i][j]);rep(k, 10) if (mx[i][k] >= 0)chmax(dp[i + 1][(j + k) % 10], dp[i][j] + mx[i][k]);}printf("%d\n", dp[10][0]);}