oj.uz

Submission #717556

# Submission time Handle Problem Language Result Execution time Memory
717556 2023-04-02T07:41:57 Z vjudge1 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 2 ms 2644 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -