結果
| 問題 | No.1231 Make a Multiple of Ten |
| ユーザー |
 eSeF
|
| 提出日時 | 2020-09-18 22:11:27 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 160 ms / 2,000 ms |
| コード長 | 28,558 bytes |
| コンパイル時間 | 1,226 ms |
| コンパイル使用メモリ | 122,332 KB |
| 実行使用メモリ | 50,148 KB |
| 最終ジャッジ日時 | 2024-06-23 13:50:42 |
| 合計ジャッジ時間 | 3,211 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;using System.IO;using System.Text;using System.Numerics;using System.Threading;using System.Runtime.CompilerServices;using System.Diagnostics;using static System.Math;using static System.Array;using static AtCoder.Cout;using static AtCoder.Tool;using static AtCoder.Graph;using static AtCoder.ModInt;namespace AtCoder{class AC{const int MOD = 1000000007;//const int MOD = 998244353;const int INF = int.MaxValue / 2;const long SINF = long.MaxValue / 3;static readonly int[] dI = { 0, 1, 0, -1, 1, -1, -1, 1 };static readonly int[] dJ = { 1, 0, -1, 0, 1, 1, -1, -1 };static void Main(string[] args){//var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(sw);/*var th = new Thread(Run, 1 << 26);th.Start();th.Join();*/Run();Console.Out.Flush();}static void Run(){int Testcase = 1;//Testcase = Cin.Int;for (var _ = 0; _ < Testcase; _++) Solve();}static void Solve(){int N = Cin.Int;var A = Cin.ReadSplitInt;var dp = new int[10];Fill(dp, -INF);dp[0] = 0;for(var i = 0; i < N; i++){var dp2 = new int[10];Fill(dp2, -INF);for(var j = 0; j < 10; j++){dp2[j] = Max(dp2[j], dp[j]);dp2[(j + A[i]) % 10] = Max(dp2[(j + A[i]) % 10], dp[j] + 1);}dp = dp2;}OutL(dp[0]);}}public struct Edge{public int from, to;public long w;public Edge(int to, long weight) { this.to = to; w = weight; from = -1; }public Edge(int from, int to, long weight) { this.from = from; this.to = to; w = weight; }}public class LCA{List<List<int>> G1;List<List<Edge>> G2;int n;bool isweighted;int[] dist;long[] dist_w;int[,] par;public LCA(List<List<int>> G){G1 = G;G2 = null;n = G1.Count();isweighted = false;dist = new int[n];dist_w = null;par = new int[25, n];}public LCA(List<List<Edge>> G){G1 = null;G2 = G;n = G2.Count();isweighted = true;dist = new int[n];dist_w = new long[n];par = new int[25, n];}public void Lca_Build(int root){for (var i = 0; i < n; i++){dist[i] = -1;if (isweighted) dist_w[i] = -1;}var dfs = new Stack<int>();dfs.Push(root);dist[root] = 0;if (isweighted) dist_w[root] = 0;par[0, root] = -1;while (dfs.Any()){int v = dfs.Pop();if (isweighted){foreach(var ed in G2[v]){if (dist[ed.to] != -1) continue;par[0, ed.to] = v;dist_w[ed.to] = dist[v] + ed.w;dist[ed.to] = dist[v] + 1;dfs.Push(ed.to);}}else{foreach(var nx in G1[v]){if (dist[nx] != -1) continue;par[0, nx] = v;dist[nx] = dist[v] + 1;dfs.Push(nx);}}}for(var i = 1; i < 25; i++){for(var j = 0; j < n; j++){if (par[i - 1, j] == -1) par[i, j] = -1;else par[i, j] = par[i - 1, par[i - 1, j]];}}}public int Lca(int u,int v){if (dist[u] < dist[v]){var kep = u;u = v;v = kep;}for (var i = 0; i < 30; i++){if ((((dist[u] - dist[v]) >> i) & 1) != 0){u = par[i, u];}}if (u == v) return u;for (var i = 24; i >= 0; i--){if (par[i, u] != par[i, v]){u = par[i, u];v = par[i, v];}}return par[0, u];}public int[] GetDist() => dist;public long[] GetWeightedDist() => dist_w;}struct ModInt{public long value;//const int MOD = 1000000007;const int MOD = 998244353;public ModInt(long value) { this.value = value; }public static implicit operator ModInt(long a){var ret = a % MOD;return new ModInt(ret < 0 ? (ret + MOD) : ret);}public static ModInt operator +(ModInt a, ModInt b) => (a.value + b.value);public static ModInt operator -(ModInt a, ModInt b) => (a.value - b.value);public static ModInt operator *(ModInt a, ModInt b) => (a.value * b.value);public static ModInt operator /(ModInt a, ModInt b) => a * Modpow(b, MOD - 2);public static ModInt operator <<(ModInt a, int n) => (a.value << n);public static ModInt operator >>(ModInt a, int n) => (a.value >> n);public static ModInt operator ++(ModInt a) => a.value + 1;public static ModInt operator --(ModInt a) => a.value - 1;[MethodImpl(MethodImplOptions.AggressiveInlining)]public static ModInt Modpow(ModInt a, long n){if (n == 0) return 1;if (n < 0) return Modpow(Modpow(a, -n), MOD - 2);var k = a;ModInt ret = 1;while (n > 0){if ((n & 1) != 0) ret *= k;k *= k;n >>= 1;}return ret;}private static readonly List<long> Factorials = new List<long>() { 1 };[MethodImpl(MethodImplOptions.AggressiveInlining)]public static ModInt Fac(int n){if (n < 0) return 0;for (var i = Factorials.Count(); i <= n; i++){Factorials.Add((Factorials[i - 1] * i) % MOD);}return Factorials[n];}[MethodImpl(MethodImplOptions.AggressiveInlining)]public static ModInt nCr(int n, int r){if (n < 0 || r < 0) return 0;return n < r ? 0 : Fac(n) / (Fac(r) * Fac(n - r));}public static explicit operator int(ModInt a) => (int)a.value;}public class SCC{int n;struct Edge_S { public int from, to; public Edge_S(int f, int t) { from = f; to = t; } }List<Edge_S> E;int[] id;public SCC(int size) { n = size; E = new List<Edge_S>(); }public void Add_Edge(int from, int to){E.Add(new Edge_S(from, to));}public int[][] Scc_Result(){var start = new int[n + 1];var nxt = new int[E.Count];foreach (var ed in E) start[ed.from + 1]++;for (var i = 0; i < n; i++) start[i + 1] += start[i];var itr = new int[n + 1]; for (var i = 0; i <= n; i++) itr[i] = start[i];foreach (var ed in E) nxt[itr[ed.from]++] = ed.to;int now = 0;int[] ord = new int[n];int[] low = new int[n];id = new int[n];var V = new Stack<int>();for (var i = 0; i < n; i++) ord[i] = -1;int nowid = 0;Action<int> DFS = null;DFS = (v) =>{low[v] = ord[v] = now++;V.Push(v);for (var i = start[v]; i < start[v + 1]; i++){var nx = nxt[i];if (ord[nx] == -1){DFS(nx);low[v] = Min(low[v], low[nx]);}else{low[v] = Min(low[v], ord[nx]);}}if (low[v] == ord[v]){while (true){var u = V.Pop();id[u] = nowid;ord[u] = n + 1;if (u == v) break;}nowid++;}};for (var i = 0; i < n; i++) if (ord[i] == -1) DFS(i);for (var i = 0; i < n; i++){id[i] = nowid - 1 - id[i];itr[i] = 0;}var scc = new int[nowid][];for (var i = 0; i < n; i++) itr[id[i]]++;for (var i = 0; i < nowid; i++) scc[i] = new int[itr[i]];for (var i = 0; i < n; i++) scc[id[i]][--itr[id[i]]] = i;return scc;}public int v_id(int v) => id[v];}public class Two_SAT{// use with SCC Libraryint n;bool[] result;SCC scc;readonly int md;public Two_SAT(int size){n = size;result = new bool[n];scc = new SCC(n << 1);md = n << 1;}public void Add_Closure(int i, int j){scc.Add_Edge((i + n) % md, j);scc.Add_Edge((j + n) % md, i);}public bool Satisfy(){scc.Scc_Result();for (var i = 0; i < n; i++){int j = scc.v_id(i), k = scc.v_id(i + n);if (j == k) return false;result[i] = j > k;}return true;}public bool[] ans() => result;}public class Dinic{readonly int n;const int inf = int.MaxValue / 2;public class Edge_F{public int _to { get; set; }public long _cap { get; set; }public int _rev { get; set; }public Edge_F(int to, long cap, int rev) { _to = to; _cap = cap; _rev = rev; }}List<List<Edge_F>> G;int[] level, itr;public Dinic(int vertice){n = vertice;level = new int[n];itr = new int[n];G = new List<List<Edge_F>>();for (var _ = 0; _ < n; _++) G.Add(new List<Edge_F>());}/*================ ^ _ ^ ==================*///辺の追加（from->to,容量cap）public void Add_Edge(int from, int to, long cap){G[from].Add(new Edge_F(to, cap, G[to].Count()));G[to].Add(new Edge_F(from, 0, G[from].Count() - 1));}//bfsパート（levelの設定）void Bfs(int s){//Fillはバージョン古いと使えないため...for (var i = 0; i < n; i++) level[i] = -1;level[s] = 0;var Q = new Queue<int>();Q.Enqueue(s);while (Q.Any()){int v = Q.Dequeue();foreach (var ed in G[v]){if (ed._cap > 0 && level[ed._to] == -1){level[ed._to] = level[v] + 1;Q.Enqueue(ed._to);}}}}//dfsパート（増加パスの探索）long Dfs(int v, int t, long f){if (v == t) return f;for (var i = itr[v]; i < G[v].Count(); i++){itr[v] = i;var ed = G[v][i];if (ed._cap > 0 && level[v] < level[ed._to]){var d = Dfs(ed._to, t, Min(f, ed._cap));if (d > 0){ed._cap -= d;G[ed._to][ed._rev]._cap += d;return d;}}}return 0;}//s->tの最大流を返す//一般:O(N^2M)//二部グラフマッチング:O(M*Sqrt(N))//辺の容量が全て同じ:O(min(n^{2/3},m^{1/2})*m)//になるらしいpublic long Max_Flow(int s, int t){long ret = 0;for (; ; ){Bfs(s);if (level[t] == -1) return ret;for (var i = 0; i < n; i++) itr[i] = 0;var flow = 0L;do { ret += flow; flow = Dfs(s, t, inf); }while (flow > 0);}}//グラフの状況を返すpublic List<List<Edge_F>> GetGraph() => G;}public static class Graph{const long inf = long.MaxValue / 3;public static List<List<T>> Gen_Graph<T>(int size){var ret = new List<List<T>>();for (var i = 0; i < size; i++) ret.Add(new List<T>());return ret;}public static long[] Dijkstra(List<List<Edge>> G, int st){int N = G.Count();long[] ret = new long[N];var V = new Priority_Queue<Tuple<long, int>>((x, y) => Sig(x.Item1 - y.Item1));for (var i = 0; i < N; i++) ret[i] = inf;ret[st] = 0; V.Enqueue(new Tuple<long, int>(0, st));while (V.Any()){var cur = V.Dequeue();int v = cur.Item2;long cd = cur.Item1;if (ret[v] < cd) continue;foreach (var ed in G[v]){if (ret[ed.to] > cd + ed.w){ret[ed.to] = cd + ed.w;V.Enqueue(new Tuple<long, int>(ret[ed.to], ed.to));}}}return ret;}public static long[] Bellman_Frod(List<Edge> E, int st, int N, out bool neg_close){var ret = new long[N];for (var i = 0; i < N; i++) ret[i] = inf;ret[st] = 0;for (var i = 0; i < N; i++){foreach (var ed in E){if (ret[ed.from] != inf && ret[ed.to] > ret[ed.from] + ed.w){if (i == N - 1) { neg_close = true; return ret; }ret[ed.to] = ret[ed.from] + ed.w;}}}neg_close = false;return ret;}}public class Priority_Queue<T>{private List<T> Q;private readonly Comparison<T> Func_Compare;public Priority_Queue(Comparison<T> comp){Func_Compare = comp;Q = new List<T>();}private void PushHeap(T item){int n = Q.Count();Q.Add(item);while (n != 0){int pIndex = (n - 1) / 2;if (Func_Compare(Q[n], Q[pIndex]) < 0){Swap(n, pIndex);}else { break; }n = pIndex;}}private void PopHeap(){int n = Q.Count() - 1;Q[0] = Q[n];Q.RemoveAt(n);int cur = 0;int comp;while (2 * cur + 1 <= n - 1){int c1 = 2 * cur + 1;int c2 = 2 * (cur + 1);if (c1 == n - 1){comp = c1;}else{comp = Func_Compare(Q[c1], Q[c2]) < 0 ? c1 : c2;}if (Func_Compare(Q[cur], Q[comp]) > 0){Swap(cur, comp);}else { break; }cur = comp;}}[MethodImpl(MethodImplOptions.AggressiveInlining)]private void Swap(int a, int b){T keep = Q[a];Q[a] = Q[b];Q[b] = keep;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Enqueue(T value) => PushHeap(value);[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Dequeue(){T ret = Q[0];PopHeap();return ret;}public T Peek() => Q[0];public int Count() => Q.Count();public bool Any() => Q.Any();}public class SegmentTree<T>{//1-indexed typeint n;T[] Tree;Func<T, T, T> f;T ex;int L;[MethodImpl(MethodImplOptions.AggressiveInlining)]public SegmentTree(int size, Func<T, T, T> fun, T exvalue){ex = exvalue;f = fun;n = size;Tree = new T[n << 1];L = (n << 1) - 1;for (var i = 0; i <= L; i++) Tree[i] = ex;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public SegmentTree(int size, Func<T, T, T> fun, T exvalue, T[] initial){ex = exvalue;n = size;f = fun;Tree = new T[n << 1];L = (n << 1) - 1;for (var i = 0; i <= L; i++) Tree[i] = (n <= i && i <= n + initial.Length - 1) ? initial[i - n] : ex;}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Set_All(){for (var i = n - 1; i >= 1; i--) Tree[i] = f(Tree[i << 1], Tree[(i << 1) | 1]);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Assign(int idx, T nxt) => Tree[idx + n] = nxt;[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Update(int idx){int now = idx + n;while (now > 1){now >>= 1;Tree[now] = f(Tree[now << 1], Tree[now << 1 | 1]);}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Query_Update(int idx, T nxt){Assign(idx, nxt); Update(idx);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Query_Update_func(int idx, T y){Assign(idx, f(Peek(idx), y)); Update(idx);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Query_Fold(int l, int r){int L = n + l;int R = n + r;T vL = ex, vR = ex;while (L < R){if (L % 2 == 1){vL = f(vL, Tree[L]);L++;}if (R % 2 == 1){vR = f(Tree[R - 1], vR);R--;}L >>= 1;R >>= 1;}return f(vL, vR);}[MethodImpl(MethodImplOptions.AggressiveInlining)]public T Peek(int idx) => Tree[idx + n];[MethodImpl(MethodImplOptions.AggressiveInlining)]public void Display(int len){for (var i = 0; i < len; i++) Console.Write($"{Tree[i + n]} ");Console.WriteLine();}}public class LazySegmentTree<X, A>{int n, L;X[] Tree;A[] lazy;Func<X, X, X> fxx;Func<A, A, A> faa;Func<X, A, X> fxa;X exx;A exa;public LazySegmentTree(int size, Func<X, X, X> funcxx, Func<A, A, A> funcaa, Func<X, A, X> funcxa, X exval, A exlaz){n = size;L = (n << 1) - 1;Tree = new X[n << 1];lazy = new A[n << 1];fxx = funcxx;faa = funcaa;fxa = funcxa;exx = exval;exa = exlaz;for (var i = 0; i <= L; i++) { Tree[i] = exx; lazy[i] = exa; }}public X eval(int id) => fxa(Tree[id], lazy[id]);[MethodImpl(MethodImplOptions.AggressiveInlining)]public void propagate(int id){int h = 0; while ((1 << (h + 1)) <= id) h++;for (var n = h; n > 0; n--){int i = id >> n;Tree[i] = eval(i);lazy[i << 1] = faa(lazy[i << 1], lazy[i]);lazy[i << 1 | 1] = faa(lazy[i << 1 | 1], lazy[i]);lazy[i] = exa;}}[MethodImpl(MethodImplOptions.AggressiveInlining)]public void re_calc(int id){while (id > 1){id >>= 1;Tree[id] = fxx(eval(id << 1), eval(id << 1 | 1));}}public void Range_Update(int l, int r, A op){int L = n + l, R = n + r;int ll = L / (L & (-L));int rr = R / (R & (-R));propagate(ll); propagate(rr - 1);while (L < R){if ((L & 1) == 1){lazy[L] = faa(lazy[L], op);L++;}if ((R & 1) == 1){R--;lazy[R] = faa(lazy[R], op);}L >>= 1; R >>= 1;}re_calc(ll); re_calc(rr - 1);}public X Range_Get(int l, int r){int L = n + l, R = n + r;X vL = exx, vR = exx;propagate(L / (L & (-L)));propagate(R / (R & (-R)) - 1);while (L < R){if ((L & 1) == 1){vL = fxx(vL, eval(L));L++;}if ((R & 1) == 1){R--;vR = fxx(eval(R), vR);}L >>= 1; R >>= 1;}return fxx(vL, vR);}public void Point_Update(int idx, X nxt){int id = idx + n;propagate(id);Tree[id] = nxt;re_calc(id);}/*======================*/public void Assign(int idx, X nxt) => Tree[n + idx] = nxt;public void Set_All(){for (var i = n - 1; i >= 1; i--){Tree[i] = fxx(Tree[i << 1], Tree[i << 1 | 1]);lazy[i] = faa(lazy[i << 1], lazy[i << 1 | 1]);}}public X Peek(int idx) => eval(idx);public void Display(int len){for (var i = n; i < n + len; i++) Console.Write($"{eval(i)} ");Console.WriteLine();}public void Displayall(){//木の形で表示、nが2冪でない時は注意int e = 0;while ((1 << e) <= n){for (var i = (1 << e); i < (1 << e) + (1 << e); i++) Console.Write($"{Tree[i]}/{lazy[i]} ");Console.WriteLine();e++;}}}public class UnionFind{private int[] parent;private int[] rank;private int[] size;public UnionFind(int n){parent = new int[n];rank = new int[n];size = new int[n];for (var i = 0; i < n; i++){parent[i] = i;rank[i] = 0;size[i] = 1;}}public int Root(int x){return parent[x] == x ? x : parent[x] = Root(parent[x]);}public bool SameRoot(int x, int y){return Root(x) == Root(y);}public void Unite(int x, int y){x = Root(x);y = Root(y);if (x == y) { return; }if (rank[x] < rank[y]){parent[x] = y;size[y] += size[x];size[x] = 0;}else{parent[y] = x;if (rank[x] == rank[y]) { rank[x]++; }size[x] += size[y];size[y] = 0;}}public int SizeOf(int x){return size[Root(x)];}}static class Cin{public static string[] ReadSplit => Console.ReadLine().Split();public static int[] ReadSplitInt => ConvertAll(ReadSplit, int.Parse);public static long[] ReadSplitLong => ConvertAll(ReadSplit, long.Parse);public static double[] ReadSplit_Double => ConvertAll(ReadSplit, double.Parse);public static string Str => Console.ReadLine();public static int Int => int.Parse(Console.ReadLine());public static long Long => long.Parse(Console.ReadLine());public static double Double => double.Parse(Console.ReadLine());public static T Conv<T>(string input){if (typeof(T).Equals(typeof(ModInt))){return (T)(dynamic)(long.Parse(input));}return (T)Convert.ChangeType(input, typeof(T));}public static void Scanf<T>(out T a) => a = Conv<T>(Console.ReadLine());public static void Scanf<T, U>(out T a, out U b){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); }public static void Scanf<T, U, V>(out T a, out U b, out V c){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); }public static void Scanf<T, U, V, W>(out T a, out U b, out V c, out W d){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); }public static void Scanf<T, U, V, W, X>(out T a, out U b, out V c, out W d, out X e){ var q = ReadSplit; a = Conv<T>(q[0]); b = Conv<U>(q[1]); c = Conv<V>(q[2]); d = Conv<W>(q[3]); e = Conv<X>(q[4]); }}static class Cout{public static void OutL(object s) => Console.WriteLine(s);public static void Out_Sep<T>(IEnumerable<T> s) => Console.WriteLine(string.Join(" ", s));public static void Out_Sep<T>(IEnumerable<T> s, string sep) => Console.WriteLine(string.Join($"{sep}", s));public static void Out_Sep(params object[] s) => Console.WriteLine(string.Join(" ", s));public static void Out_One(object s) => Console.Write($"{s} ");public static void Out_One(object s, string sep) => Console.Write($"{s}{sep}");public static void Endl() => Console.WriteLine();}public static class Tool{static public void Initialize<T>(ref T[] array, T initialvalue){array = ConvertAll(array, x => initialvalue);}static public void Swap<T>(ref T a, ref T b){T keep = a;a = b;b = keep;}static public void Display<T>(T[,] array2d, int n, int m){for (var i = 0; i < n; i++){for (var j = 0; j < m; j++){Console.Write($"{array2d[i, j]} ");}Console.WriteLine();}}static public long Gcd(long a, long b){if (a == 0 || b == 0) return Max(a, b);return a % b == 0 ? b : Gcd(b, a % b);}static public long LPow(int a, int b) => (long)Pow(a, b);static public bool Bit(long x, int dig) => ((1L << dig) & x) != 0;static public int Sig(long a) => a == 0 ? 0 : (int)(a / Abs(a));}}