Submission #1030592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030592		fuad27	Vim (BOI13_vim)	C++17	35.50 / 100	89 ms	59732 KiB

vim

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define vt vector
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
 
template<class T> bool chmin(T& a, const T& b) {
	return b<a?a=b, 1:0;
}
template<class T> bool chmax(T& a, const T& b) { 
	return a<b?a=b, 1:0;
} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng_64(chrono::steady_clock::now().time_since_epoch().count());

int k(int a, int b) {
 if(a==b)return 1e9;
 return 0;
}
int u(int v) {
  if(v)return 1e9;
  return 0;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
  int n;
  string s;
  cin >> n >> s;
  int ans=0;
  reverse(all(s));
  while(sz(s) and s.back() == 'e') {
    ans++;
    s.pop_back();
  }
  reverse(all(s));
  vt<bool> need(n);
  {
    string tmp = "";
    for(int i = 0;i<n;i++) {
      if(s[i] == 'e') {
        ans+=2;
        continue;
      }
      if(i == 0 or s[i-1] == 'e') {
        need[tmp.size()]=1;
      }
      tmp.push_back(s[i]);
      tmp.back()-='a';
    }
    swap(tmp, s);
  }
  n=s.size();
  vt dp2(n+1, vt(12, vt(12, 0)));
  vt dp1(n+1, vt(12, (int)1e9));
  for(int i = 0;i<12;i++) {
    if(s[i] != i)dp1[0][i] = 2;
  }
 for(int i = 0;i<n;i++) {
    for(int j = 0;j<12;j++) {
      dp1[i+1][j] = min({dp1[i][j] + k(s[i], j) + u(need[i]), dp1[i][s[i]] + 2, dp2[i][s[i]][j]+k(s[i], j), dp2[i][s[i]][s[i]]+2});
      for(int l = 0;l<12;l++) {
        dp2[i+1][j][l] = min({dp1[i][j] + 3 + k(j, s[i]), dp1[i][s[i]] + 5,
            dp2[i][j][l]+1  + k(j, s[i]) + k(l, s[i]), dp2[i][j][s[i]]+3+k(j, s[i]), dp2[i][s[i]][l]+3+k(l, s[i]), dp2[i][s[i]][s[i]]+5});
      }
    }
  }
 ans+=dp1[n][11];
 cout << ans << "\n";
}

• Subtask 1: 12.5 / 50
• Subtask 2: 3 / 10
• Subtask 3: 20 / 40