Submission #730285

#	Time	Username	Problem	Language	Result	Execution time	Memory
730285		Karpin	Martian DNA (BOI18_dna)	C++17	100 / 100	35 ms	5380 KiB

dna

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define vt vector
#define ar array

int neededAmounts[200005];
int totalAmounts[200005];
int curAmount[200005];

bool needed [200005];

int totalNucles = 0;
int n;




void solve(){

    int k, r;
    cin >> n >> k >> r;
    vt<int> nucles (n);

    for(int i = 0; i < n; i++){
        cin >> nucles[i];
        totalAmounts[nucles[i]]++;
    }

    

    for(int i = 0; i < r; i++){
        int a, b;
        cin >> a >> b;
        if (totalAmounts[a] < b){
            cout << "impossible" << endl;
            return;            
        }
        neededAmounts[a] = b;
        totalNucles += b;
        needed[a] = true;
    }


    int left = 0;
    int right = -1;
    int res = n;

    while (r > 0){
        if (curAmount[nucles[right + 1]] + 1 == neededAmounts[nucles[right + 1]]){
            curAmount[nucles[right + 1]]++;
            r--;
            right++;
        }else{
            curAmount[nucles[right + 1]]++;
            right++;
        }
    }
    res = right - left + 1;

    while (right < n){
        if (curAmount[nucles[left]] > neededAmounts[nucles[left]]){
            curAmount[nucles[left]]--;
            left++;
            res = min(res, right - left + 1);
            continue;
        }
        curAmount[nucles[right + 1]]++;
        right++;
    }

    cout << res << endl;


		

}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int testcases = 1;

	// cin >> testcases;

	while(testcases--){
		solve();
	}

	return 0;

}

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