Submission #730272

#	Time	Username	Problem	Language	Result	Execution time	Memory
730272		Karpin	Martian DNA (BOI18_dna)	C++17	0 / 100	29 ms	5116 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];

bool needed [200005];

int totalNucles = 0;
int n;


int getter(vt<int> nucles){
    vt<int> curAmounts(200005);
    int left = 0; int right = n - 1;
    while (!needed[nucles[left]] || totalAmounts[nucles[left]] - curAmounts[nucles[left]] > neededAmounts[nucles[left]]){
        curAmounts[nucles[left]]++;
        left++;
    }
    while(!needed[nucles[right]] || totalAmounts[nucles[right]] - curAmounts[nucles[right]] > neededAmounts[nucles[right]]){
        curAmounts[nucles[right]]++;
        right--;
    }
    return right - left + 1;
}


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 res = getter(nucles);
    reverse(nucles.begin(), nucles.end());
    res = min(res, getter(nucles));

    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: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 28
• Subtask 4: 0 / 32