Submission #2634574


Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    int n;
    char[] ss;
    int[] cs;

    public static void main(String args[]) {
        new Main().run();
    }

    void run() {
        FastReader sc = new FastReader();
        n = sc.nextInt();
        ss = sc.next().toCharArray();
        cs = new int[n];
        for (int i = 0; i < n; i++) {
            cs[i] = sc.nextInt();
        }
        solve();
    }

    void solve() {
        boolean[][] palTable = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            int l = i;
            int r = i;
            while (l >= 0 && r < n && ss[l] == ss[r]) {
                palTable[l][r] = true;
                l--;
                r++;
            }
            l = i;
            r = i + 1;
            while (l >= 0 && r < n && ss[l] == ss[r]) {
                palTable[l][r] = true;
                l--;
                r++;
            }
        }
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = 1 << 30;
        }
        for (int r = 0; r < n; r++) {
            for (int l = r; l >= 0; l--) {
                if (palTable[l][r]) {
                    dp[r + 1] = Math.min(dp[r + 1], dp[l] + cs[r - l]);
                }
            }
        }
        System.out.println(dp[n]);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Submission Info

Submission Time
Task C - Palindrome Concatenation
User ynish
Language Java8 (OpenJDK 1.8.0)
Score 100
Code Size 2681 Byte
Status AC
Exec Time 254 ms
Memory 52436 KB

Judge Result

Set Name Sample Dataset1 Dataset2
Score / Max Score 0 / 0 40 / 40 60 / 60
Status
AC × 3
AC × 24
AC × 48
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, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 73 ms 19156 KB
01-02.txt AC 70 ms 18388 KB
01-03.txt AC 82 ms 18388 KB
01-04.txt AC 82 ms 18388 KB
01-05.txt AC 74 ms 18132 KB
01-06.txt AC 72 ms 18388 KB
01-07.txt AC 71 ms 19284 KB
01-08.txt AC 74 ms 19412 KB
01-09.txt AC 72 ms 19284 KB
01-10.txt AC 74 ms 20948 KB
01-11.txt AC 73 ms 21204 KB
01-12.txt AC 73 ms 21588 KB
01-13.txt AC 82 ms 20436 KB
01-14.txt AC 74 ms 18772 KB
01-15.txt AC 74 ms 18772 KB
01-16.txt AC 73 ms 19412 KB
01-17.txt AC 72 ms 18900 KB
01-18.txt AC 83 ms 20948 KB
01-19.txt AC 73 ms 21332 KB
01-20.txt AC 75 ms 21332 KB
01-21.txt AC 72 ms 19284 KB
02-01.txt AC 83 ms 18388 KB
02-02.txt AC 107 ms 22680 KB
02-03.txt AC 107 ms 29012 KB
02-04.txt AC 165 ms 50516 KB
02-05.txt AC 254 ms 51924 KB
02-06.txt AC 159 ms 50388 KB
02-07.txt AC 158 ms 48852 KB
02-08.txt AC 253 ms 49236 KB
02-09.txt AC 168 ms 48852 KB
02-10.txt AC 154 ms 50388 KB
02-11.txt AC 161 ms 50004 KB
02-12.txt AC 157 ms 49748 KB
02-13.txt AC 161 ms 50260 KB
02-14.txt AC 162 ms 50772 KB
02-15.txt AC 162 ms 50388 KB
02-16.txt AC 174 ms 50132 KB
02-17.txt AC 170 ms 48596 KB
02-18.txt AC 165 ms 50388 KB
02-19.txt AC 168 ms 50644 KB
02-20.txt AC 161 ms 52436 KB
02-21.txt AC 151 ms 50388 KB
02-22.txt AC 162 ms 50772 KB
02-23.txt AC 229 ms 50260 KB
02-24.txt AC 215 ms 52436 KB
sample-01.txt AC 72 ms 20692 KB
sample-02.txt AC 83 ms 20820 KB
sample-03.txt AC 71 ms 19284 KB