Submission #1268021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268021		_rain_	Vim (BOI13_vim)	C++20	42.50 / 100	25 ms	9028 KiB

vim

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1) << (x))
#define sz(x) (int)(x).size()
#define TIME_USED cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n";

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
	
const int N = (int) 7e4;
const int inf = (int) 1e9;
const int MAXK = (int) 11;
const int const_id = 4;
	vector<int> occur[MAXK + 2];
	string s;
	int n;
	
		int Find_nxt(int c , int x){
			int tt = upper_bound(occur[c].begin() , occur[c].end() , x) - occur[c].begin();
			if (tt == sz(occur[c])) return -1;
			return occur[c][tt];
		}
	
	int pre[N + 2][MAXK + 2] = {};
	int dp[N + 2][MAXK + 2] = {};
	int rig[N + 2] = {} , last[N + 2] = {} , ans[N + 2] = {};
	int a[N + 2] = {};
	
		int Get_prefix(int c , int l , int r){
			return pre[r][c] - pre[l - 1][c];
		}
	
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ; 
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n >> s;
		s = '#' + s;
		for(int i = 1; i <= n; ++i) a[i] = (int)s[i] - 'a';
		//... PREBUILD
			for(int i = 1; i <= n; ++i) occur[a[i]].push_back(i);
			rig[n + 1] = n + 1;
			for(int i = n; i >= 1; --i){
				if (s[i] == 'e') rig[i] = i; else rig[i] = rig[i + 1];
			}
			for(int i = n; i >= 1; --i){
				if (s[i] != 'e') last[i] = i; else last[i] = last[i + 1];
			}
			for(int i = 1; i <= n; ++i){
				for(int j = 0; j <= MAXK; ++j){
					pre[i][j] = pre[i - 1][j];
				}
				pre[i][a[i]]++;
			}
		memset(dp , 0x3f , sizeof dp);
		memset(ans  , 0x3f , sizeof ans);
		for(int i = 0; i <= MAXK; ++i) dp[1][i] = 0;
		ans[1] = 0;
		for(int i = 1; i <= n; ++i){
			if (a[i] == const_id) continue;
			for(int j = 0; j <= MAXK; ++j) {
				if (j == const_id) continue;
				int t = Find_nxt(j , i);
				if (t == -1) continue;
				int last_ptr = min(rig[i] , t);
				int last_exist = last[last_ptr];
				int cost = dp[i][j] + 2 + Get_prefix(const_id , i , t) + t - last_ptr;
				minimize(ans[t] , cost);
				for(int nxt_c = 0; nxt_c <= MAXK; ++nxt_c){
					if (nxt_c == const_id) continue;
					int nxt_cost = cost + 2 * (Get_prefix(nxt_c , last_exist + 1 , t) != 0);
					minimize(dp[t][nxt_c] , nxt_cost);
				}
			}
		}
		int res = inf;
		for(int i = 1; i <= n; ++i) if (pre[i][const_id] == pre[n][const_id]) minimize(res , ans[i]);
		cout << res;
		
	return 0;
}

Compilation message (stderr)

vim.cpp: In function 'int main()':
vim.cpp:57:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
vim.cpp:58:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 37.5 / 50
• Subtask 2: 5 / 10
• Subtask 3: 0 / 40