oj.uz

답안 #922764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922764 2024-02-06T06:05:35 Z vjudge1 JJOOII 2 (JOI20_ho_t2) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 12, MOD = 1e9 + 7;

typedef long long ll;

int n,k,A[N],B[N],C[N];
string s;
vector<int> a,b,c;
void test(){
    cin >> n >> k >> s;
    s = "#" + s;
    for(int i = 1;i <= n;i++){
        A[i] = A[i - 1];
        B[i] = B[i - 1];
        C[i] = C[i - 1];
        if(s[i] == 'J'){
            A[i]++;
            a.push_back(i);
        }else if(s[i] == 'O'){
            B[i]++;
            b.push_back(i);
        }else{
            C[i]++;
            c.push_back(i);
        }
    }
    if(min({(int)a.size(),(int)b.size(),(int)c.size()}) < k){
        cout << -1 << '\n';
        return;
    }
    int l = a[k - 1],r = c[(int)c.size() - k];
    if(B[r] - B[l] < k){
        cout << -1 << '\n';
        return;
    }
    int can_del = a[0] - 1 + (n - c.back());
    int cur_a = k - 1,cur_b = (int)c.size() - k;
    while(cur_a < (int)a.size() || cur_b >= 0){
        int newL = cur_a + 1,newR = cur_b -1;
        if(newR >= 0 && B[c[newR]] - B[a[cur_a]] >= k){
            cur_b = newR;
            can_del = a[cur_a - k + 1] - 1 + (n - c[cur_b + k - 1]);
        }else if(newL < (int)a.size() && B[c[cur_b]] - B[a[newL]] >= k){
            cur_a = newL;
            can_del = a[cur_a - k + 1] - 1 + (n - c[cur_b + k - 1]);
        }else break;
    }
    assert(can_del >= 0);
    assert(can_del <= n - k * 3);
    cout << n - k * 3 - can_del << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int T = 1;
//    cin >> T;
    while (T--)
        test();
}

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -