Submission #489927
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; using System.IO; using System.Text; using System.Numerics; namespace Solver { class Program { const int M = 1000000007; const double eps = 1e-9; static void Main() { var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; var sc = new Scan(); int n = sc.Int; var s = sc.Str; var c = sc.IntArr; var dp = new int[n + 1]; var kaibun = new bool[n][]; for (int i = 0; i < n; i++) { kaibun[i] = new bool[i + 1]; dp[i + 1] = dp[i] + c[0]; for (int j = 0; j < i; j++) { if (i - j < 3) kaibun[i][j] = s[i] == s[j]; else kaibun[i][j] = kaibun[i - 1][j + 1] && s[i] == s[j]; if (kaibun[i][j]) dp[i + 1] = Math.Min(dp[i + 1], dp[j] + c[i - j]); } } sw.WriteLine(dp[n]); sw.Flush(); } } class Scan { public int Int { get { return int.Parse(Console.ReadLine().Trim()); } } public long Long { get { return long.Parse(Console.ReadLine().Trim()); } } public string Str { get { return Console.ReadLine().Trim(); } } public int[] IntArr { get { return Console.ReadLine().Trim().Split().Select(int.Parse).ToArray(); } } public int[] IntArrWithSep(char sep) { return Console.ReadLine().Trim().Split(sep).Select(int.Parse).ToArray(); } public long[] LongArr { get { return Console.ReadLine().Trim().Split().Select(long.Parse).ToArray(); } } public double[] DoubleArr { get { return Console.ReadLine().Split().Select(double.Parse).ToArray(); } } public string[] StrArr { get { return Console.ReadLine().Trim().Split(); } } public List<int> IntList { get { return Console.ReadLine().Trim().Split().Select(int.Parse).ToList(); } } public List<long> LongList { get { return Console.ReadLine().Trim().Split().Select(long.Parse).ToList(); } } public void Multi(out int a, out int b) { var arr = IntArr; a = arr[0]; b = arr[1]; } public void Multi(out int a, out int b, out int c) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; } public void Multi(out int a, out int b, out int c, out int d) { var arr = IntArr; a = arr[0]; b = arr[1]; c = arr[2]; d = arr[3]; } public void Multi(out int a, out string b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1]; } public void Multi(out int a, out int b, out string c) { var arr = StrArr; a = int.Parse(arr[0]); b = int.Parse(arr[1]); c = arr[2]; } public void Multi(out int a, out char b) { var arr = StrArr; a = int.Parse(arr[0]); b = arr[1][0]; } public void Multi(out long a, out long b) { var arr = LongArr; a = arr[0]; b = arr[1]; } public void Multi(out long a, out int b) { var arr = LongArr; a = arr[0]; b = (int)arr[1]; } public void Multi(out string a, out string b) { var arr = StrArr; a = arr[0]; b = arr[1]; } } }
Submission Info
Submission Time | |
---|---|
Task | C - Palindrome Concatenation |
User | riantkb |
Language | C# (Mono 3.2.1.0) |
Score | 100 |
Code Size | 3289 Byte |
Status | AC |
Exec Time | 394 ms |
Memory | 28516 KB |
Judge Result
Set Name | Sample | Dataset1 | Dataset2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 40 / 40 | 60 / 60 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt, sample-02.txt, sample-03.txt |
Dataset1 | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt |
Dataset2 | 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 02-20.txt, 02-21.txt, 02-22.txt, 02-23.txt, 02-24.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 268 ms | 9232 KB |
01-02.txt | AC | 182 ms | 9208 KB |
01-03.txt | AC | 152 ms | 9216 KB |
01-04.txt | AC | 148 ms | 9272 KB |
01-05.txt | AC | 148 ms | 9228 KB |
01-06.txt | AC | 151 ms | 9328 KB |
01-07.txt | AC | 151 ms | 9232 KB |
01-08.txt | AC | 149 ms | 9336 KB |
01-09.txt | AC | 150 ms | 9264 KB |
01-10.txt | AC | 153 ms | 9348 KB |
01-11.txt | AC | 164 ms | 9324 KB |
01-12.txt | AC | 158 ms | 9300 KB |
01-13.txt | AC | 155 ms | 9336 KB |
01-14.txt | AC | 156 ms | 9328 KB |
01-15.txt | AC | 152 ms | 9232 KB |
01-16.txt | AC | 173 ms | 9228 KB |
01-17.txt | AC | 162 ms | 9236 KB |
01-18.txt | AC | 151 ms | 9344 KB |
01-19.txt | AC | 160 ms | 9224 KB |
01-20.txt | AC | 161 ms | 9224 KB |
01-21.txt | AC | 163 ms | 9304 KB |
02-01.txt | AC | 177 ms | 9872 KB |
02-02.txt | AC | 221 ms | 11548 KB |
02-03.txt | AC | 232 ms | 18416 KB |
02-04.txt | AC | 383 ms | 28516 KB |
02-05.txt | AC | 394 ms | 28480 KB |
02-06.txt | AC | 316 ms | 28488 KB |
02-07.txt | AC | 311 ms | 28452 KB |
02-08.txt | AC | 380 ms | 28492 KB |
02-09.txt | AC | 314 ms | 28488 KB |
02-10.txt | AC | 311 ms | 28404 KB |
02-11.txt | AC | 305 ms | 28492 KB |
02-12.txt | AC | 312 ms | 28492 KB |
02-13.txt | AC | 316 ms | 28396 KB |
02-14.txt | AC | 313 ms | 28408 KB |
02-15.txt | AC | 309 ms | 28492 KB |
02-16.txt | AC | 315 ms | 28484 KB |
02-17.txt | AC | 313 ms | 28492 KB |
02-18.txt | AC | 317 ms | 28484 KB |
02-19.txt | AC | 315 ms | 28488 KB |
02-20.txt | AC | 318 ms | 28488 KB |
02-21.txt | AC | 309 ms | 28448 KB |
02-22.txt | AC | 309 ms | 28488 KB |
02-23.txt | AC | 340 ms | 28492 KB |
02-24.txt | AC | 349 ms | 28364 KB |
sample-01.txt | AC | 149 ms | 9268 KB |
sample-02.txt | AC | 150 ms | 9236 KB |
sample-03.txt | AC | 149 ms | 9216 KB |