Submission #481710

#	Time	Username	Problem	Language	Result	Execution time	Memory
481710		Lobo	JJOOII 2 (JOI20_ho_t2)	C++17	100 / 100	22 ms	22776 KiB

ho_t2

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

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220000

ii n, k, a[maxn], dp[maxn][5], pos[5][maxn], px[maxn], qtd[5];
string s;

ii sol(ii i, ii p) {
    if(p == 3) return 0;
    if(i == n+1) return INFii;
    if(dp[i][p] != -1) return dp[i][p];

    ii ans = INFii;

    ans = min(ans, sol(i+1,p)+1);
    if(p == 0) ans = min(ans, sol(i+1,p));

    if(a[i] == p && px[i]+k-1 <= qtd[p]) {
        ans = min(ans, sol(pos[p][px[i]+k-1] + 1 ,p+1) + pos[p][px[i]+k-1]-i+1-k);
    }

    return dp[i][p] = ans;
}

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

    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    cin >> n >> k >> s;

    for(ii i = 1; i <= n; i++) {
        dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = -1;
        if(s[i-1] == 'J') {
            a[i] = 0;
            px[i] = ++qtd[0];
            pos[0][qtd[0]] = i;
        }
        else if(s[i-1] == 'O') {
            a[i] = 1;
            px[i] = ++qtd[1];
            pos[1][qtd[1]] = i;
        }
        else {
            a[i] = 2;
            px[i] = ++qtd[2];
            pos[2][qtd[2]] = i;
        }
    }

    if(sol(1,0) >= INFii) cout << -1 << endl;
    else cout << sol(1,0) << endl;
}

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