Submission #378026
Source Code Expand
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9+7; typedef long long ll; const int INF = 1e9; map<string,bool> dic; bool is_palin(const string& s){ if(dic.find(s) != dic.end())return dic[s]; for(int i=0;i<s.size()/2;i++){ if(s[i] != s[s.size()-1-i])return dic[s] = false; } return dic[s] = true; } int main(void) { int n;string s; cin >> n >> s; vector<ll> c(n); for(int i=0;i<n;i++){ cin >> c[i]; } vector<vector<bool>> palin(5001,vector<bool>(5001)); for(int i=0;i<n;i++){ int d = 0; while(i-d>=0 && i+d<n && s[i-d] == s[i+d]){ palin[i-d][i+d] = true; d++; } int l = i-1,r = i; while(l >= 0 && r < n && s[l] == s[r]){ palin[l][r] = true; l--;r++; } } vector<ll> dp(s.size()+1,INF); dp[0] = c[0]; for(int i=1;i<s.size();i++){ dp[i] = min(dp[i] , dp[i-1] + c[0]); for(int j=0;j<i;j++){ if(palin[j][i]){ if(j==0)dp[i] = min(dp[i] , c[i-j]); else dp[i] = min(dp[i] , dp[j-1] + c[i-j]); } } } cout << dp[s.size()-1] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - Palindrome Concatenation |
User | tkzw_21 |
Language | C++11 (GCC 4.9.2) |
Score | 100 |
Code Size | 1088 Byte |
Status | AC |
Exec Time | 241 ms |
Memory | 4256 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 | 35 ms | 4064 KB |
01-02.txt | AC | 35 ms | 4004 KB |
01-03.txt | AC | 35 ms | 4124 KB |
01-04.txt | AC | 44 ms | 4132 KB |
01-05.txt | AC | 39 ms | 4076 KB |
01-06.txt | AC | 34 ms | 4132 KB |
01-07.txt | AC | 39 ms | 4136 KB |
01-08.txt | AC | 35 ms | 4128 KB |
01-09.txt | AC | 34 ms | 4132 KB |
01-10.txt | AC | 38 ms | 4132 KB |
01-11.txt | AC | 42 ms | 4116 KB |
01-12.txt | AC | 40 ms | 4256 KB |
01-13.txt | AC | 35 ms | 4252 KB |
01-14.txt | AC | 36 ms | 4004 KB |
01-15.txt | AC | 53 ms | 4064 KB |
01-16.txt | AC | 78 ms | 4060 KB |
01-17.txt | AC | 34 ms | 4132 KB |
01-18.txt | AC | 33 ms | 4124 KB |
01-19.txt | AC | 35 ms | 4128 KB |
01-20.txt | AC | 33 ms | 4120 KB |
01-21.txt | AC | 35 ms | 4124 KB |
02-01.txt | AC | 45 ms | 4200 KB |
02-02.txt | AC | 55 ms | 4104 KB |
02-03.txt | AC | 59 ms | 4132 KB |
02-04.txt | AC | 95 ms | 4132 KB |
02-05.txt | AC | 203 ms | 4088 KB |
02-06.txt | AC | 119 ms | 4212 KB |
02-07.txt | AC | 109 ms | 4120 KB |
02-08.txt | AC | 241 ms | 4136 KB |
02-09.txt | AC | 124 ms | 4124 KB |
02-10.txt | AC | 105 ms | 4092 KB |
02-11.txt | AC | 96 ms | 4128 KB |
02-12.txt | AC | 103 ms | 4120 KB |
02-13.txt | AC | 105 ms | 4192 KB |
02-14.txt | AC | 103 ms | 4188 KB |
02-15.txt | AC | 102 ms | 4132 KB |
02-16.txt | AC | 104 ms | 4116 KB |
02-17.txt | AC | 103 ms | 4132 KB |
02-18.txt | AC | 97 ms | 4120 KB |
02-19.txt | AC | 116 ms | 4124 KB |
02-20.txt | AC | 124 ms | 4100 KB |
02-21.txt | AC | 105 ms | 4132 KB |
02-22.txt | AC | 108 ms | 4204 KB |
02-23.txt | AC | 200 ms | 4132 KB |
02-24.txt | AC | 171 ms | 4192 KB |
sample-01.txt | AC | 54 ms | 4004 KB |
sample-02.txt | AC | 37 ms | 4068 KB |
sample-03.txt | AC | 38 ms | 4064 KB |