oj.uz

Submission #63279

# Submission time Handle Problem Language Result Execution time Memory
63279 2018-08-01T08:26:25 Z 김세빈(#1833) Vim (BOI13_vim) C++11
50 / 100
 2000 ms 34768 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;

int main()
{
	int i, j, k;
	pii p;
	
	scanf("%d%s", &n, str);
	
	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]];
		for(j=1; j<=i; j++){
			dp[i][j] = 1e9;
			for(k=0; k<j; k++){
				dp[i][j] = min(dp[i][j], dp[j-1][k] + D[N[K[k]]][K[i]] + D[K[i]][K[j]]);
			}
		}
	}
	
	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 'int main()':
vim.cpp:63:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<K.size(); i++){
           ~^~~~~~~~~
vim.cpp:75: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:77: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:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%s", &n, str);
  ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6264 KB Output is correct
2 Correct 35 ms 6264 KB Output is correct
3 Correct 27 ms 6264 KB Output is correct
4 Correct 54 ms 6264 KB Output is correct
5 Correct 56 ms 6264 KB Output is correct
6 Correct 94 ms 6320 KB Output is correct
7 Correct 81 ms 6320 KB Output is correct
8 Correct 5 ms 6320 KB Output is correct
9 Correct 4 ms 6320 KB Output is correct
10 Correct 5 ms 6320 KB Output is correct
11 Correct 6 ms 6320 KB Output is correct
12 Correct 7 ms 6320 KB Output is correct
13 Correct 65 ms 6504 KB Output is correct
14 Correct 39 ms 6504 KB Output is correct
15 Correct 28 ms 6504 KB Output is correct
16 Correct 41 ms 6504 KB Output is correct
17 Correct 75 ms 6504 KB Output is correct
18 Correct 46 ms 6504 KB Output is correct
19 Correct 29 ms 6504 KB Output is correct
20 Correct 41 ms 6504 KB Output is correct
21 Correct 58 ms 6504 KB Output is correct
22 Correct 58 ms 6504 KB Output is correct
23 Correct 35 ms 6504 KB Output is correct
24 Correct 70 ms 6504 KB Output is correct
25 Correct 57 ms 6504 KB Output is correct
26 Correct 74 ms 6504 KB Output is correct
27 Correct 87 ms 6504 KB Output is correct
28 Correct 96 ms 6504 KB Output is correct
29 Correct 92 ms 6504 KB Output is correct
30 Correct 47 ms 6504 KB Output is correct
31 Correct 74 ms 6504 KB Output is correct
32 Correct 73 ms 6504 KB Output is correct
33 Correct 86 ms 6504 KB Output is correct
34 Correct 79 ms 6504 KB Output is correct
35 Correct 83 ms 6504 KB Output is correct
36 Correct 81 ms 6504 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 18496 KB Time limit exceeded
2 Execution timed out 2059 ms 18496 KB Time limit exceeded
3 Execution timed out 2029 ms 34768 KB Time limit exceeded
4 Execution timed out 2095 ms 34768 KB Time limit exceeded
5 Execution timed out 2080 ms 34768 KB Time limit exceeded
6 Execution timed out 2090 ms 34768 KB Time limit exceeded
7 Execution timed out 2016 ms 34768 KB Time limit exceeded
8 Execution timed out 2021 ms 34768 KB Time limit exceeded
9 Execution timed out 2012 ms 34768 KB Time limit exceeded
10 Execution timed out 2094 ms 34768 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 34768 KB Time limit exceeded
2 Execution timed out 2003 ms 34768 KB Time limit exceeded
3 Execution timed out 2056 ms 34768 KB Time limit exceeded
4 Execution timed out 2033 ms 34768 KB Time limit exceeded
5 Execution timed out 2037 ms 34768 KB Time limit exceeded
6 Execution timed out 2017 ms 34768 KB Time limit exceeded
7 Execution timed out 2066 ms 34768 KB Time limit exceeded
8 Execution timed out 2035 ms 34768 KB Time limit exceeded
9 Execution timed out 2065 ms 34768 KB Time limit exceeded
10 Execution timed out 2043 ms 34768 KB Time limit exceeded
11 Execution timed out 2012 ms 34768 KB Time limit exceeded
12 Execution timed out 2058 ms 34768 KB Time limit exceeded
13 Execution timed out 2092 ms 34768 KB Time limit exceeded
14 Execution timed out 2044 ms 34768 KB Time limit exceeded
15 Execution timed out 2036 ms 34768 KB Time limit exceeded
16 Execution timed out 2096 ms 34768 KB Time limit exceeded
17 Execution timed out 2095 ms 34768 KB Time limit exceeded
18 Execution timed out 2040 ms 34768 KB Time limit exceeded
19 Execution timed out 2045 ms 34768 KB Time limit exceeded
20 Execution timed out 2005 ms 34768 KB Time limit exceeded