제출 #717556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717556		vjudge1	JJOOII 2 (JOI20_ho_t2)	C++17	0 / 100	2 ms	2644 KiB

ho_t2

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > dp(2, vector<int>(200010, 0));
char word[200010], pat[70010];
int n, k;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> word[i];

    for(int i = 1; i <= k; i++) pat[i] = 'J';
    for(int i = k + 1; i <= 2 * k; i++) pat[i] = 'O';
    for(int i = 2 * k + 1; i <= 3 * k; i++) pat[i] = 'I';
    dp[0][0] = 0;

    for(int i = 1; i <= 3 * k; i++) {
        int now = i & 1, prev= (i - 1) & 1;
        dp[now][0] = 2e9;
        for(int j = 1; j <= n; j++) {
            if(pat[i] == word[j]) {
                if(i != 1 && j != 1 && pat[i - 1] != word[j - 1]) {
                    dp[now][j] = dp[prev][j - 1] + 1;
                }
                else {
                    dp[now][j] = dp[prev][j - 1];
                }
                dp[now][j] = min(dp[now][j], dp[now][j - 1]);
            }
            else {
                dp[now][j] = 2e9;
                dp[now][j] = min(dp[now][j], dp[now][j - 1]);
            }
        }
    }
    cout << (dp[0][n] >= 2e9 ? -1 : dp[0][n]) << '\n';
    return 0;
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 12
• Subtask 3: 0 / 87