Submission #41066

#	Time	Username	Problem	Language	Result	Execution time	Memory
41066		livace	Vim (BOI13_vim)	C++14	39.50 / 100	51 ms	9324 KiB

vim

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,unroll-all-loops")
// #pragma GCC option("arch=native","tune=native")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx")

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

#define f(_i, _n) for (auto _i = 0; _i < _n; _i++)
#define F(_i, _k, _n) for (auto _i = _k; _i < _n; _i++)
#define re return
#define pb push_back
#define all(_v) _v.begin(), _v.end()
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
#define fi first
#define se second

typedef pair<int,int> pii;
typedef long long ll;
typedef long double ld;

int nxt[100500][15];
int dp[100500][15];

int cnt_e;

int tmp_nxt[10];

int next_not_e[100500];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  string s;
  cin >> s;
  n = (int)s.size();
  f(i, n) {
    s[i] -= 'a';
    if (s[i] == 4) {
      cnt_e++;
    }
  }
  f(i, 10) {
    tmp_nxt[i] = -1;
  }
  for (int i = n - 1; i >= 0; i--) {
    next_not_e[i] = 1e9;
    f(j, 10) {
      nxt[i][j] = tmp_nxt[j];
      if (tmp_nxt[j] != -1) {
        next_not_e[i] = min(next_not_e[i], tmp_nxt[j]);
      }
    }
    tmp_nxt[(int)s[i]] = i;

  }
  f(i, n + 1) {
    f(j, 11) {
      if (j == 4) {
        continue;
      }
      dp[i][j] = 1e9;
    }
  }
  dp[0][10] = 0;
  int ans = 1e9;
  f(i, n) {
    f(j, 11) {
      if (j == 4) {
        continue;
      }
      // cerr << i << ' ' << j << ' ' << dp[i][j] << '\n';
      int nxt_e;
      if (j == 10) {
        nxt_e = nxt[i][4];
      } else {
        nxt_e = nxt[nxt[i][j]][4];
      }
      if (nxt_e == -1) {
        ans = min(ans, dp[i][j]);
        continue;
      }
      f(k, 10) {
        if (k == 4) {
          continue;
        }
        int pos = nxt[i][k];
        if (pos == -1) {
          continue;
        }
        if (nxt_e > pos) {
          dp[pos][10] = min(dp[pos][10], dp[i][j] + 2);
        } else {
          if (pos == next_not_e[nxt_e]) {
            dp[next_not_e[nxt_e]][10] = min(dp[next_not_e[nxt_e]][10], dp[i][j] + 2 + pos - nxt_e);
          } else {
            dp[next_not_e[nxt_e]][k] = min(dp[next_not_e[nxt_e]][k], dp[i][j] + 2 + pos - nxt_e);
          }
        }
      }
    }
  }
  cout << ans + cnt_e;
}

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