oj.uz

Submission #730272

# Submission time Handle Problem Language Result Execution time Memory
730272 2023-04-25T14:38:50 Z Karpin Martian DNA (BOI18_dna) C++17
0 / 100
 29 ms 5116 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Incorrect 1 ms 1108 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -