提出 #23721015

---

ソースコード 拡げる

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 4010

ll i, i1, j, k, k1, t, n, m, res, flag[10], a[maxn], b[maxn], dp[maxn][maxn];
ll ps[maxn][2][2010], ty, f[2][maxn];
char c;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> n;
    for (i = 1; i <= 2 * n; i++) {
        cin >> c >> b[i]; a[i] = (c == 'W');
        f[a[i]][b[i]] = i;
    }

    for (i = 2 * n; i >= 1; i--) {
        for (ty = 0; ty <= 1; ty++) {
            for (j = 1; j <= n; j++) {
                ps[i][ty][j] = ps[i + 1][ty][j];
            }
        }
        ps[i][a[i]][b[i]]++;
    }

    for (i = 1; i <= 2 * n; i++) {
        for (ty = 0; ty <= 1; ty++) {
            for (j = 1; j <= n; j++) {
                ps[i][ty][j] += ps[i][ty][j - 1];
            }
        }
    }

    for (i = 0; i <= n; i++) {
        for (j = 0; j <= n; j++) {
            dp[i][j] = INF;
            if (i + j == 0) dp[i][j] = 0;
            if (i != 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + ps[f[0][i]][0][i - 1] + ps[f[0][i]][1][j]);
            if (j != 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + ps[f[1][j]][0][i] + ps[f[1][j]][1][j - 1]);
        }
    }

    cout << dp[n][n] << nl;

    return 0;
}

提出情報

ジャッジ結果