結果
| 問題 | No.1288 yuki collection |
| ユーザー |
 ei1333333
|
| 提出日時 | 2020-11-13 17:50:34 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 2,623 ms / 5,000 ms |
| コード長 | 9,057 bytes |
| コンパイル時間 | 2,743 ms |
| コンパイル使用メモリ | 120,796 KB |
| 実行使用メモリ | 47,660 KB |
| 最終ジャッジ日時 | 2024-07-22 20:09:26 |
| 合計ジャッジ時間 | 42,611 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 40 |
コンパイルメッセージ
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.Globalization;using System.IO;using System.Linq;using P = pair<int, int>;class Program{Scanner cin;Printer cout;void myon(){cin = new Scanner();cout = new Printer();int N = cin.nextInt();String s = cin.next();long[] A = cin.nextArrayLong(N);var MCF = new MinCostFlow(N + 1);int[] nxt = new int[5];nxt[0] = N + 1;nxt[1] = N + 1;nxt[2] = N + 1;nxt[3] = N + 1;nxt[4] = N;const String t = "yuki";const long inf = 1000000000;for(int i = N - 1; i >= 0; i--){int k = t.IndexOf(s[i]);if (nxt[k] <= N){MCF.addEdge(i, nxt[k], N / 4, 0);}if (nxt[k + 1] <= N){MCF.addEdge(i, nxt[k + 1], 1, inf - A[i]);}nxt[k] = i;}if(nxt[0] == N + 1){cout.println("0");return;}MCF.addEdge(nxt[0], N, N / 4, inf * 4);cout.println(inf * 4 * (N / 4) - MCF.run(nxt[0], N, N / 4));}static void Main(string[] args){new Program().myon();}}class Printer{public Printer(){var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };Console.SetOut(sw);}~Printer(){flush();}public void println(string a){Console.WriteLine(a);}public void println<T>(IEnumerable<T> a){println(string.Join(" ", a));}public void println(params object[] a){println(string.Join(" ", a));}public void print<T>(string a){Console.Write(a);}public void print<T>(IEnumerable<T> a){print(string.Join(" ", a));}public void print(params object[] a){print(string.Join(" ", a));}public void printArray<T>(params T[] a){foreach (var x in a) Console.WriteLine(x);}public void flush() => Console.Out.Flush();}class Scanner{readonly CultureInfo ci = CultureInfo.InvariantCulture;string[] s;int i;readonly char[] cs = new char[] { ' ' };public Scanner(){s = new string[0];i = 0;}public string next(){if (i < s.Length) return s[i++];string st = Console.ReadLine();while (st == "") st = Console.ReadLine();s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);if (s.Length == 0) return next();i = 0;return s[i++];}public string nextLine(){return Console.ReadLine();}public int nextInt(){return int.Parse(next());}public long nextLong(){return long.Parse(next());}public double nextDouble(){return double.Parse(next(), ci);}public int[] nextArrayInt(int N, int add = 0){int[] ret = new int[N];for (int i = 0; i < N; i++){ret[i] = nextInt() + add;}return ret;}public long[] nextArrayLong(int N, long add = 0){long[] ret = new long[N];for (int i = 0; i < N; i++){ret[i] = nextLong() + add;}return ret;}public double[] nextArrayDouble(int N, double add = 0){double[] ret = new double[N];for (int i = 0; i < N; i++){ret[i] = nextDouble() + add;}return ret;}}class pair<T, U> : IComparable<pair<T, U>>{public T v1;public U v2;public pair() : this(default(T), default(U)) { }public pair(T v1, U v2) { this.v1 = v1; this.v2 = v2; }public int CompareTo(pair<T, U> a){int c = Comparer<T>.Default.Compare(v1, a.v1);return c != 0 ? c : Comparer<U>.Default.Compare(v2, a.v2);}public override string ToString() => v1 + " " + v2;public void Deconstruct(out T a, out U b) { a = v1; b = v2; }}static class util{public static readonly int M = 1000000007;// public static readonly int M = 998244353;public static readonly long LM = 1L << 60;public static readonly double eps = 1e-11;public static void DBG(string a) => Console.Error.WriteLine(a);public static void DBG<T>(IEnumerable<T> a) => DBG(string.Join(" ", a));public static void DBG(params object[] a) => DBG(string.Join(" ", a));public static void Assert(params bool[] conds){if (conds.Any(x => !x)) throw new Exception();}public static pair<T, U> make_pair<T, U>(T v1, U v2) => new pair<T, U>(v1, v2);public static int CompareList<T>(IList<T> a, IList<T> b) where T : IComparable<T>{for (int i = 0; i < a.Count && i < b.Count; i++)if (a[i].CompareTo(b[i]) != 0) return a[i].CompareTo(b[i]);return a.Count.CompareTo(b.Count);}public static bool inside(int i, int j, int h, int w) => i >= 0 && i < h && j >= 0 && j < w;public static readonly int[] dd = { 0, 1, 0, -1 };// static readonly string dstring = "RDLU";public static IEnumerable<P> adjacents(int i, int j)=> Enumerable.Range(0, dd.Length).Select(k => new P(i + dd[k], j + dd[k ^ 1]));public static IEnumerable<P> adjacents(int i, int j, int h, int w)=> adjacents(i, j).Where(p => inside(p.v1, p.v2, h, w));public static IEnumerable<P> adjacents(this P p) => adjacents(p.v1, p.v2);public static IEnumerable<P> adjacents(this P p, int h, int w) => adjacents(p.v1, p.v2, h, w);public static IEnumerable<int> all_subset(this int p){for (int i = 0; ; i = i - p & p){yield return i;if (i == p) break;}}public static Dictionary<T, int> compress<T>(this IEnumerable<T> a)=> a.Distinct().OrderBy(v => v).Select((v, i) => new { v, i }).ToDictionary(p => p.v, p => p.i);public static Dictionary<T, int> compress<T>(params IEnumerable<T>[] a) => compress(a.SelectMany(x => x));public static T[] inv<T>(this Dictionary<T, int> dic){var res = new T[dic.Count];foreach (var item in dic) res[item.Value] = item.Key;return res;}public static void swap<T>(ref T a, ref T b) where T : struct { var t = a; a = b; b = t; }public static void swap<T>(this IList<T> a, int i, int j) where T : struct { var t = a[i]; a[i] = a[j]; a[j] = t; }public static T[] copy<T>(this IList<T> a){var ret = new T[a.Count];for (int i = 0; i < a.Count; i++) ret[i] = a[i];return ret;}}class MinCostFlow{class edge{public int to, cap, rev;public long cost;public edge(int to, int cap, long cost, int rev){this.to = to;this.cap = cap;this.cost = cost;this.rev = rev;}}int n;List<edge>[] g;public MinCostFlow(int n){this.n = n;g = new List<edge>[n];for (int i = 0; i < n; i++)g[i] = new List<edge>();}public void addEdge(int from, int to, int cap, long cost){g[from].Add(new edge(to, cap, cost, g[to].Count));g[to].Add(new edge(from, 0, -cost, g[from].Count - 1));}public long run(int s, int t, int f){long res = 0;var h = new long[n];while (f > 0){var q = new PriorityQueue<pair<long, int>>() { rev = true };var dist = new long[n];var prevv = new int[n];var preve = new int[n];for (int i = 0; i < n; i++) dist[i] = util.LM;dist[s] = 0;q.Push(new pair<long, int>(0, s));while (q.Count > 0){var p = q.Pop();int v = p.v2;if (dist[v] < p.v1) continue;for (int i = 0; i < g[v].Count; ++i){var e = g[v][i];if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];prevv[e.to] = v;preve[e.to] = i;q.Push(new pair<long, int>(dist[e.to], e.to));}}}if (dist[t] == util.LM) break;for (int v = 0; v < n; ++v) h[v] += dist[v];int d = f;for (int v = t; v != s; v = prevv[v]) d = Math.Min(d, g[prevv[v]][preve[v]].cap);f -= d;res += d * h[t];for (int v = t; v != s; v = prevv[v]){var e = g[prevv[v]][preve[v]];e.cap -= d;g[v][e.rev].cap += d;}}return res;}}// the greatest element popsclass PriorityQueue<T>{List<T> buf;public bool rev = false;Func<int, int, int> cmp;public PriorityQueue(){buf = new List<T>();cmp = (i, j) => Comparer<T>.Default.Compare(buf[i], buf[j]) * (rev ? -1 : 1);}public PriorityQueue(Func<T, T, int> cmp){buf = new List<T>();this.cmp = (i, j) => cmp(buf[i], buf[j]);}void swap(int i, int j) { var t = buf[i]; buf[i] = buf[j]; buf[j] = t; }public void Push(T elem){int n = buf.Count;buf.Add(elem);while (n > 0){int i = (n - 1) >> 1;if (cmp(n, i) <= 0) break;swap(i, n);n = i;}}public T Pop(){T ret = buf[0];int n = buf.Count - 1;buf[0] = buf[n];buf.RemoveAt(n);for (int i = 0, j; (j = (i << 1) | 1) < n; i = j){if (j != n - 1 && cmp(j, j + 1) < 0) ++j;if (cmp(i, j) < 0) swap(i, j);else break;}return ret;}public T Top => buf[0];public int Count => buf.Count;}