Submission #63277

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
63277	2018-08-01T08:25:24 Z	김세빈(#1833)	Vim (BOI13_vim)	C++11	Compilation error	0 ms	0 KB

vim

#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]];
		dnc(i, 1, i, 1, i);
		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:65:3: error: 'dnc' was not declared in this scope
   dnc(i, 1, i, 1, i);
   ^~~
vim.cpp:76: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:78: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);
  ~~~~~^~~~~~~~~~~~~~~~~