1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int dx[4] = {0, 1, -1, 0};
int dy[4] = {-1, 0, 0, 1};
void solve() {
    int n, m;
    cin >> n >> m;
    vvi ma(n, vi(m));
    rep(i, 0, n - 1) { rep(j, 0, m - 1) cin >> ma[i][j]; }
    vi vis(n * m + 1);
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (vis[ma[i][j]] == 0) vis[ma[i][j]] = 1;
            rep(v, 0, 3) {
                int ax = i + dx[v], ay = j + dy[v];
                if (ax >= 0 && ax <= n - 1 && ay >= 0 && ay <= m - 1) {
                    if (ma[ax][ay] == ma[i][j]) vis[ma[i][j]] = 2;
                }
            }
        }
    }
    int ans = 0;
    rep(i, 1, m * n) { ans += vis[i]; }
    int ans2 = INT_MAX;
    rep(i, 1, m * n) ans2 = min(ans2, ans - vis[i]);
    cout << ans2 << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

const ll MOD = 998244353;
void solve() {
    int n;
    cin >> n;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    ll tem = 0;
    ll tem2 = 0;
    ll tem3 = 0;
    int idx = -1;
    rep(i, 0, n - 1) {
        if (a[i] == 1) {
            idx = i;
            break;
        }
    }
    if (idx == -1) {
        cout << 0 << endl;
        return;
    }
    rep(i, idx, n - 1) {
        if (a[i] == 1) {
            tem++;
        } else if (a[i] == 2) {
            tem2 = (tem2 * 2 % MOD + tem) % MOD;
        } else {
            ans = (ans + tem2) % MOD;
        }
    }
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

const ll MOD = 998244353;
void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    int l1 = 0, r1 = n - 1;
    while (l1 <= r1 && s[l1] == s[r1]) {
        l1++, r1--;
    }
    if (l1 > r1) {
        cout << 0 << endl;
        return;
    }
    string tem = s.substr(l1, r1 - l1 + 1);
    int m = sz(tem);
    int l = 2, r = m, ans = 2, mid;
    auto check = [&](int mid) -> bool {
        if (mid > m / 2) {
            vi tem2(26);
            vi tem3(26);
            rep(i, 0, mid - 1) tem2[tem[i] - 'a']++;
            rep(i, mid, m - 1) tem3[tem[i] - 'a']++;
            bool flag = true;
            rep(i, 0, 25) {
                if (tem2[i] >= tem3[i])
                    continue;
                else
                    flag = false;
            }
            if (flag) return true;
            flag = true;
            rep(i, 0, 25) tem2[i] = 0, tem3[i] = 0;
            rep(i, m - mid, m - 1) tem2[tem[i] - 'a']++;
            rep(i, 0, m - mid - 1) tem3[tem[i] - 'a']++;
            rep(i, 0, 25) {
                if (tem2[i] >= tem3[i] && (tem2[i] - tem3[i]) % 2 == 0)
                    continue;
                else
                    flag = false;
            }
            return flag;
        } else {
            rep(i, mid, m / 2 - 1) {
                if (tem[i] != tem[m - 1 - i]) return false;
            }
            vi tem2(26);
            vi tem3(26);
            rep(i, 0, mid - 1) tem2[tem[i] - 'a']++;
            rep(i, m - mid, m - 1) tem3[tem[i] - 'a']++;
            bool flag = true;
            rep(i, 0, 25) {
                if (tem2[i] == tem3[i])
                    continue;
                else
                    flag = false;
            }
            if (flag) return true;
            flag = true;
            rep(i, 0, 25) tem2[i] = 0, tem3[i] = 0;
            rep(i, 0, mid - 1) tem3[tem[i] - 'a']++;
            rep(i, m - mid, m - 1) tem2[tem[i] - 'a']++;
            rep(i, 0, 25) {
                if (tem2[i] == tem3[i])
                    continue;
                else
                    flag = false;
            }
            return flag;
        }
    };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

void solve() {
    string s;
    cin >> s;
    int n = sz(s);
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    int cnt0 = 0, cnt1 = 0;
    rep(i, 0, n - 1) {
        if (s[i] == 'A')
            cnt0++;
        else
            cnt1++;
    }
    if (a + b + 2 * c + 2 * d < n) {
        cout << "NO" << endl;
        return;
    }
    vi tem;
    vi tem2;
    ll tem3 = 0;
    int l = 0;
    while (l <= n - 1) {
        int r = l;
        while (r < n - 1 && s[r + 1] != s[r]) r++;
        if ((r - l + 1) % 2 == 1) {
            tem3 += (r - l + 1) / 2;
        } else {
            if (s[l] == 'A')
                tem.push_back((r - l + 1) / 2);
            else
                tem2.push_back((r - l + 1) / 2);
        }
        l = r + 1;
    }
    ranges::sort(tem);
    ranges::sort(tem2);
    ll re = 0;
    rep(i, 0, sz(tem) - 1) {
        if (c >= tem[i]) {
            c -= tem[i];
            re += tem[i];
        } else
            tem3 += tem[i] - 1;
    }
    rep(i, 0, sz(tem2) - 1) {
        if (d >= tem2[i]) {
            d -= tem2[i];
            re += tem2[i];
        } else
            tem3 += tem2[i] - 1;
    }
    re += min(tem3, c + d);
    if (a + re >= cnt0 && b + re >= cnt1)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    return;
}