Submission #1111272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111272		HiepVu217	Martian DNA (BOI18_dna)	C++17	100 / 100	23 ms	2816 KiB

dna

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 17;
int n, k, r, a[N], z[N], ans, b, q;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> r;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= r; ++i)
    {
        cin >> b >> q;
        z[b] = q;
    }
    ans = n + 1;
    for (int i = 1, j = 1; i <= n; ++i)
    {
        while (r > 0 && j <= n)
        {
            --z[a[j]];
            if (!z[a[j]])
            {
                --r;
            }
            ++j;
        }
        if (!r)
        {
            ans = min (ans, j - i);
        }
        ++z[a[i]];
        if (z[a[i]] == 1)
        {
            ++r;
        }
    }
    if (ans == n + 1)
    {
        cout << "impossible";
        return 0;
    }
    cout << ans;
}

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