oj.uz

Submission #1030596

# Submission time Handle Problem Language Result Execution time Memory
1030596 2024-07-22T07:23:42 Z fuad27 Vim (BOI13_vim) C++17
100 / 100
 98 ms 59792 KB 
#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 1e6;
 return 0;
}
int u(int v) {
  if(v)return 1e6;
  return 0;
}
signed 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, (int)1e9)));
  vt dp1(n+1, vt(12, 0));
  for(int i = 0;i<12;i++) {
    if(s[0] != 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]-2;
 cout << ans << "\n";
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 2 ms 604 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 1 ms 604 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 4 ms 3432 KB Output is correct
3 Correct 2 ms 1884 KB Output is correct
4 Correct 3 ms 2396 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 6 ms 4444 KB Output is correct
7 Correct 4 ms 2908 KB Output is correct
8 Correct 4 ms 3164 KB Output is correct
9 Correct 5 ms 3420 KB Output is correct
10 Correct 5 ms 3676 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 52048 KB Output is correct
2 Correct 71 ms 49744 KB Output is correct
3 Correct 82 ms 52820 KB Output is correct
4 Correct 75 ms 53556 KB Output is correct
5 Correct 93 ms 59792 KB Output is correct
6 Correct 42 ms 27224 KB Output is correct
7 Correct 62 ms 44596 KB Output is correct
8 Correct 69 ms 52088 KB Output is correct
9 Correct 58 ms 38564 KB Output is correct
10 Correct 51 ms 36444 KB Output is correct
11 Correct 98 ms 53584 KB Output is correct
12 Correct 77 ms 59740 KB Output is correct
13 Correct 76 ms 58712 KB Output is correct
14 Correct 83 ms 57684 KB Output is correct
15 Correct 71 ms 48456 KB Output is correct
16 Correct 74 ms 52816 KB Output is correct
17 Correct 68 ms 51956 KB Output is correct
18 Correct 69 ms 52816 KB Output is correct
19 Correct 66 ms 49748 KB Output is correct
20 Correct 54 ms 42120 KB Output is correct