| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 63271 |
2018-08-01T08:16:58 Z |
김세빈(#1833) |
Vim (BOI13_vim) |
C++11 |
|
2000 ms |
35588 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;
vector <pii> V[70707];
vector <int> K;
int D[5050][5050];
int dp[5050][5050];
int N[70707], chk[70707];
priority_queue <pii, vector <pii>, greater <pii>> Q;
char str[70707];
int n, ans;
void dnc(int p, int s, int e, int l, int r)
{
if(s > e) return;
int mid = s + e >> 1;
int ret = 1e9, t = l, i, k;
for(i=l; i<=r && i<mid; i++){
k = dp[mid-1][i] + D[N[K[i]]][K[p]] + D[K[p]][K[mid]];
if(ret > k) ret = k, t = i;
}
dp[p][mid] = ret;
dnc(p, s, mid - 1, l, t);
dnc(p, mid + 1, e, t, r);
}
int main()
{
int i, j, k;
pii p;
scanf("%d%s", &n, str);
if(n > 5000) return 0;
for(i=0; i<n; i++){
if(str[i] == 'e') K.push_back(i);
}
for(i=1; i<n; i++){
V[i].push_back(pii(i-1, 1));
}
for(i=0; i<n; i++){
for(j=0; j<10; j++){
if(j == 4) continue;
for(k=i+1; k<n; k++) if(str[k] == j + 'a') break;
if(k < n) V[i].push_back(pii(k, 2));
}
if(str[i] == 'e'){
for(j=i+1; j<n; j++) if(str[j] != 'e') break;
N[i] = j;
}
}
for(i=0; i<n; i++){
for(j=0; j<n; j++) chk[j] = 0;
Q.push(pii(0, i));
for(; !Q.empty(); ){
p = Q.top(); Q.pop();
if(chk[p.second]) continue;
D[i][p.second] = p.first;
chk[p.second] = 1;
for(pii t: V[p.second]){
if(!chk[t.first]){
Q.push(pii(p.first + t.second, t.first));
}
}
}
}
for(i=0; i<K.size(); i++){
dp[i][0] = D[0][K[i]] + D[K[i]][K[0]];
dnc(i, 1, i, 0, i);
}
ans = 1e9;
for(i=0; i<K.size(); i++) ans = min(ans, dp[K.size() - 1][i]);
printf("%d\n", ans + K.size());
return 0;
}
Compilation message
vim.cpp: In function 'void dnc(int, int, int, int, int)':
vim.cpp:20:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = s + e >> 1;
~~^~~
vim.cpp: In function 'int main()':
vim.cpp:83:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<K.size(); i++){
~^~~~~~~~~
vim.cpp:90:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<K.size(); i++) ans = min(ans, dp[K.size() - 1][i]);
~^~~~~~~~~
vim.cpp:92:31: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d\n", ans + K.size());
~~~~~~~~~~~~~~^
vim.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%s", &n, str);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
6264 KB |
Output isn't correct |
| 2 |
Incorrect |
35 ms |
6264 KB |
Output isn't correct |
| 3 |
Incorrect |
24 ms |
6264 KB |
Output isn't correct |
| 4 |
Incorrect |
56 ms |
6264 KB |
Output isn't correct |
| 5 |
Incorrect |
57 ms |
6264 KB |
Output isn't correct |
| 6 |
Incorrect |
91 ms |
6264 KB |
Output isn't correct |
| 7 |
Incorrect |
71 ms |
6264 KB |
Output isn't correct |
| 8 |
Correct |
6 ms |
6264 KB |
Output is correct |
| 9 |
Correct |
5 ms |
6264 KB |
Output is correct |
| 10 |
Incorrect |
3 ms |
6264 KB |
Output isn't correct |
| 11 |
Correct |
5 ms |
6264 KB |
Output is correct |
| 12 |
Correct |
4 ms |
6264 KB |
Output is correct |
| 13 |
Incorrect |
64 ms |
6484 KB |
Output isn't correct |
| 14 |
Incorrect |
36 ms |
6484 KB |
Output isn't correct |
| 15 |
Incorrect |
24 ms |
6484 KB |
Output isn't correct |
| 16 |
Incorrect |
35 ms |
6484 KB |
Output isn't correct |
| 17 |
Incorrect |
73 ms |
6484 KB |
Output isn't correct |
| 18 |
Incorrect |
48 ms |
6484 KB |
Output isn't correct |
| 19 |
Correct |
28 ms |
6484 KB |
Output is correct |
| 20 |
Incorrect |
42 ms |
6484 KB |
Output isn't correct |
| 21 |
Incorrect |
51 ms |
6484 KB |
Output isn't correct |
| 22 |
Incorrect |
63 ms |
6484 KB |
Output isn't correct |
| 23 |
Incorrect |
30 ms |
6484 KB |
Output isn't correct |
| 24 |
Incorrect |
67 ms |
6484 KB |
Output isn't correct |
| 25 |
Incorrect |
55 ms |
6484 KB |
Output isn't correct |
| 26 |
Incorrect |
70 ms |
6484 KB |
Output isn't correct |
| 27 |
Incorrect |
87 ms |
6484 KB |
Output isn't correct |
| 28 |
Incorrect |
103 ms |
6484 KB |
Output isn't correct |
| 29 |
Incorrect |
74 ms |
6484 KB |
Output isn't correct |
| 30 |
Incorrect |
47 ms |
6484 KB |
Output isn't correct |
| 31 |
Incorrect |
64 ms |
6484 KB |
Output isn't correct |
| 32 |
Incorrect |
71 ms |
6484 KB |
Output isn't correct |
| 33 |
Incorrect |
68 ms |
6484 KB |
Output isn't correct |
| 34 |
Incorrect |
75 ms |
6484 KB |
Output isn't correct |
| 35 |
Incorrect |
71 ms |
6484 KB |
Output isn't correct |
| 36 |
Incorrect |
70 ms |
6484 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2017 ms |
18356 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2050 ms |
18356 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2037 ms |
35588 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2050 ms |
35588 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2027 ms |
35588 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2020 ms |
35588 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2032 ms |
35588 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2077 ms |
35588 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2056 ms |
35588 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2066 ms |
35588 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 5 |
Incorrect |
5 ms |
35588 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
35588 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 9 |
Incorrect |
5 ms |
35588 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
35588 KB |
Output isn't correct |
| 11 |
Incorrect |
5 ms |
35588 KB |
Output isn't correct |
| 12 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 13 |
Incorrect |
6 ms |
35588 KB |
Output isn't correct |
| 14 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 15 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 16 |
Incorrect |
6 ms |
35588 KB |
Output isn't correct |
| 17 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 18 |
Incorrect |
5 ms |
35588 KB |
Output isn't correct |
| 19 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
| 20 |
Incorrect |
4 ms |
35588 KB |
Output isn't correct |
