Submission #44239

#	Time	Username	Problem	Language	Result	Execution time	Memory
44239		snat123	Vim (BOI13_vim)	C++14	30.56 / 100	2073 ms	5388 KiB

vim

#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 (stderr)

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;
      ^

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