#include<bits/stdc++.h>
using namespace std;
vector<int> ind[10];
string s;
int dp[501][501];
int calc(int index, int k, int cnt){
if(k>0 && dp[index][k]!=0) return dp[index][k];
int indexx=index, kk=k, cntt=cnt;
if(k==ind[4].size()-1) return 0;
int res=INT_MAX, next_e=ind[4][k+1];
while(index>=next_e){
//cout << next_e << " " << index << " " << dp[indexx][kk]<<endl;
if(s[index]!='e'){
index--;
//cnt++;
dp[indexx][kk]++;
}
else{
if(index!=next_e){
index--;
//cnt+=2;
k++;
dp[indexx][kk]+=2;
}
else{
//cnt++;
while(s[index]=='e'){
index++;
}
dp[indexx][kk]++;
k++;
break;
}
}
}
//cout << "index->" << index << " next_e->" << next_e << " k->" << k << " dp->" << dp[indexx][kk] << endl;
if(k==ind[4].size()-1) return (dp[indexx][kk]);
for(int i=0; i<10; i++){
if(i==('e'-'a') || ind[i].size()==0) continue;
int next=upper_bound(ind[i].begin(), ind[i].end(), index)-ind[i].begin();
if(next==ind[i].size()) continue;
next=ind[i][next];
//cout << i << " " << index << " " << next << " " << k << " " << res << endl;
if(kk>=0)res=min(res, calc(next, k, dp[indexx][kk]+cnt+2)+2);
else res=min(res, calc(next, k, cnt+2)+2);
//cout << "i->" << i << " index->" << index << " next->" << next << " k->" << k << " res->" << res << endl;
}
//cout << indexx << " " << kk << " " << cntt << " " << res << endl;
//return res;
if(res!=INT_MAX) dp[indexx][kk]+=res;
return (dp[indexx][kk]);
}
int main(){
memset(dp, 0, sizeof dp);
int n;
cin >> n >> s;
for(int i=0; i<n; i++){
ind[s[i]-'a'].push_back(i);
}
int k=0;
cout << calc(0, -1, 0);
return 0;
}
Compilation message
vim.cpp: In function 'int calc(int, int, int)':
vim.cpp:12:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(k==ind[4].size()-1) return 0;
~^~~~~~~~~~~~~~~~~
vim.cpp:40:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(k==ind[4].size()-1) return (dp[indexx][kk]);
~^~~~~~~~~~~~~~~~~
vim.cpp:44:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(next==ind[i].size()) continue;
~~~~^~~~~~~~~~~~~~~
vim.cpp:11:26: warning: unused variable 'cntt' [-Wunused-variable]
int indexx=index, kk=k, cntt=cnt;
^~~~
vim.cpp: In function 'int main()':
vim.cpp:64:6: warning: unused variable 'k' [-Wunused-variable]
int k=0;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
1276 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1384 KB |
Output isn't correct |
| 3 |
Incorrect |
3 ms |
1384 KB |
Output isn't correct |
| 4 |
Correct |
3 ms |
1384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1448 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1448 KB |
Output is correct |
| 7 |
Correct |
3 ms |
1584 KB |
Output is correct |
| 8 |
Correct |
2 ms |
1600 KB |
Output is correct |
| 9 |
Correct |
2 ms |
1600 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1708 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1708 KB |
Output is correct |
| 12 |
Correct |
2 ms |
1724 KB |
Output is correct |
| 13 |
Correct |
3 ms |
1724 KB |
Output is correct |
| 14 |
Incorrect |
3 ms |
1724 KB |
Output isn't correct |
| 15 |
Incorrect |
3 ms |
1724 KB |
Output isn't correct |
| 16 |
Incorrect |
3 ms |
1724 KB |
Output isn't correct |
| 17 |
Correct |
4 ms |
1724 KB |
Output is correct |
| 18 |
Correct |
3 ms |
1724 KB |
Output is correct |
| 19 |
Incorrect |
3 ms |
1788 KB |
Output isn't correct |
| 20 |
Correct |
3 ms |
1788 KB |
Output is correct |
| 21 |
Correct |
3 ms |
1788 KB |
Output is correct |
| 22 |
Correct |
3 ms |
1788 KB |
Output is correct |
| 23 |
Incorrect |
4 ms |
1788 KB |
Output isn't correct |
| 24 |
Execution timed out |
2073 ms |
1788 KB |
Time limit exceeded |
| 25 |
Correct |
3 ms |
1788 KB |
Output is correct |
| 26 |
Correct |
3 ms |
1788 KB |
Output is correct |
| 27 |
Incorrect |
3 ms |
1788 KB |
Output isn't correct |
| 28 |
Correct |
3 ms |
1788 KB |
Output is correct |
| 29 |
Incorrect |
3 ms |
1792 KB |
Output isn't correct |
| 30 |
Incorrect |
3 ms |
1792 KB |
Output isn't correct |
| 31 |
Execution timed out |
2070 ms |
1792 KB |
Time limit exceeded |
| 32 |
Incorrect |
3 ms |
1792 KB |
Output isn't correct |
| 33 |
Incorrect |
3 ms |
1792 KB |
Output isn't correct |
| 34 |
Correct |
3 ms |
1792 KB |
Output is correct |
| 35 |
Correct |
3 ms |
1792 KB |
Output is correct |
| 36 |
Correct |
3 ms |
1792 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
3056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
4 ms |
3056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
4 ms |
3056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
4 ms |
3056 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
4 ms |
3112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
4 ms |
3112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
4 ms |
3148 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
4 ms |
3284 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
4 ms |
3284 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
4 ms |
3284 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
7 ms |
3964 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
7 ms |
4180 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
7 ms |
4180 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
8 ms |
4304 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
8 ms |
4380 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
7 ms |
4488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
7 ms |
4528 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
7 ms |
4608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
8 ms |
4608 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
8 ms |
4696 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
7 ms |
4788 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
7 ms |
4864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
8 ms |
5076 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
8 ms |
5144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
8 ms |
5164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
7 ms |
5164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
7 ms |
5164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
10 ms |
5164 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
8 ms |
5388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
7 ms |
5388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
