Submission #44241

#	Time	Username	Problem	Language	Result	Execution time	Memory
44241		snat123	Vim (BOI13_vim)	C++14	32.56 / 100	2084 ms	198308 KiB

vim

#include<bits/stdc++.h>
 
using namespace std;
 
vector<int> ind[10];
string s;
int dp[5001][5001];
 
int calc(int index, int k){
	if(k>0 && dp[index][k]!=0) return dp[index][k];
	int indexx=index, kk=k;
	if(k==ind[4].size()-1) return 0;
	int res=INT_MAX, next_e=ind[4][k+1];
	while(index>=next_e){
		if(s[index]!='e'){
			index--;
			dp[indexx][kk]++;
		}
		else{
			if(index!=next_e){
				index--;
				k++;
				dp[indexx][kk]+=2;
			}
			else{
				while(s[index]=='e'){
					index++;
				}
				dp[indexx][kk]++;
				k++;
                break;
			}
		}
	}
    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];
		if(kk>=0)res=min(res, calc(next, k)+2);
	    else res=min(res, calc(next, k)+2);
    }
    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);
	return 0;
}

Compilation message (stderr)

vim.cpp: In function 'int calc(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:35:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(k==ind[4].size()-1) return (dp[indexx][kk]);
        ~^~~~~~~~~~~~~~~~~
vim.cpp:39:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(next==ind[i].size()) continue;
      ~~~~^~~~~~~~~~~~~~~
vim.cpp: In function 'int main()':
vim.cpp:55:6: warning: unused variable 'k' [-Wunused-variable]
  int k=0;
      ^

• Subtask 1: 30.555555555555557 / 50
• Subtask 2: 2 / 10
• Subtask 3: 0 / 40