Need help with my code for C in today's contest
Difference between en3 and en4, changed 2,150 character(s)


<spoiler summary="Spoiler">↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
#include <functional>↵
#include <bits/stdc++.h>↵
using namespace __gnu_pbds;↵
using namespace std;↵
typedef long long ll;↵
int main() {↵
  ios_base::sync_with_stdio(false);↵
  cin.tie(NULL);↵
  ll t;↵
  cin >> t;↵
  while (t--) {↵
    ll n, k;↵
    cin >> n >> k;↵
    string a, b;↵
    cin >> a >> b;↵
    vector < ll > mp(26, 0), mp1(26, 0);↵
    vector < vector < ll >> calc(26, vector < ll > (n + 1, 0));↵
    vector < ll > pre(n + 1, 0);↵
    ll len = 0;↵
    ll ans = 0;↵
    if (a[0] == b[0]) {↵
      pre[0] = 1;↵
      len++;↵
    }↵
    calc[a[0] &mdash; 'a'][0] = 1;↵
    mp1[a[0] &mdash; 'a']++;↵
    for (ll i = 1; i < n; i++) {↵
      calc[a[i] &mdash; 'a'][i]++;↵
      if (a[i] == b[i]) {↵
        len++;↵
        pre[i] += (len + pre[i &mdash; 1]);↵
      } else if (a[i] != b[i]) {↵
        pre[i] = pre[i &mdash; 1];↵
        len = 0;↵
      }↵
    }↵
    for (ll i = 0; i < 26; i++) {↵
      for (ll j = 1; j < n; j++) {↵
        calc[i][j] += calc[i][j &mdash; 1];↵
      }↵
    }↵
    if (k == 0) {↵
      cout << pre[n &mdash; 1] << endl;↵
      continue;↵
    }↵
    ll i = 0;↵
    ll j = 0;↵
    set < char > s1;↵
    len = 0;↵

    ll count = 0;↵
    while (j < n) {↵
      mp[a[j] - 'a'] = j;↵
      if (a[j] != b[j]) {↵
        s1.insert(a[j]);↵
      }↵
      ll now = s1.size();↵
      if (now > k) {↵
        while (a[i] == b[i]) {↵
          i++;↵
        }↵
        s1.erase(a[i]);↵
        i = mp[a[i] - 'a'] + 1;↵
        now--;↵
      }↵
      len = j - i + 1;↵
      if (i == 0) {↵
        ll count = 0;↵
        for (auto x: s1) {↵
          count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j]);↵
        }↵
        ans = max(ans, pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);↵
      } else {↵
        ll count = 0;↵
        for (auto x: s1) {↵
          count += (calc[x - 'a'][n - 1] - calc[x - 'a'][j] + calc[x - 'a'][i - 1]);↵
        }↵
        ans = max(ans, pre[i - 1] + pre[n - 1] - pre[j] + len * (len + 1) / 2 + count);↵
      }↵
      j++;↵
    }↵
    cout << ans << endl;↵
  }↵
}↵
</spoiler>↵

[submission:191622912]

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English playinwithfire 2023-02-01 22:29:37 2150
en3 English playinwithfire 2023-02-01 22:27:46 31
en2 English playinwithfire 2023-02-01 22:26:19 15
en1 English playinwithfire 2023-02-01 22:25:51 2217 Initial revision (published)