제출 #1290909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290909		altayeb_132	Martian DNA (BOI18_dna)	C++20	0 / 100	28 ms	3528 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N = 201;
const int INF = 1e9;
const ll LLINF = 9e18;
const ll MOD = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// typedef __gnu_pbds::tree<int, __gnu_pbds::null_type, less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> ordered_set;
void solve()
{
    int n, k, r;
    cin >> n >> k >> r;
    int a[n];
    int cnt1[n] = {};
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt1[a[i]]++;
    }
    int rq[k] = {}; 
    int cnt[k] = {};
    bool possible = 1;
    for(int i = 0; i < r; i++)
    {
        int u, v;
        cin >> u >> v;
        rq[u] = v;
        if(rq[u] > cnt1[u])
            possible = 0;
    }
    if(!possible)
    {
        cout << "impossible";
        return;
    }
    int gd = 0;
    int l1 = 0, r1 = 0, ans = INF;
    while(r1 != n)
    {
        while(gd != r && r1 != n)
        {
            cnt[a[r1]]++;
            if(cnt[a[r1]] == rq[a[r1]])
                gd++;
            r1++;
        }
        if(cnt[a[l1]] == rq[a[l1]])
        {
            gd--;
        }
        cnt[a[l1]]--;
        l1++;
        ans = min(ans, r1 - l1 + 1);
    }

    cout << ans << '\n';
}   
int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << '\n';
    }
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32