Submission #1326506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326506		islam_2010	Martian DNA (BOI18_dna)	C++20	0 / 100	2095 ms	332 KiB

dna

#include <bits/stdc++.h>
using namespace std;

#define int long long

map<int, int> mp, mp2, mp3;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
	freopen("main.in", "r", stdin);
	freopen("main.out", "w", stdout);

    int n, k, m;
    cin >> n >> k >> m;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        mp3[a[i]]++;
    }for(int i = 0; i < m; i++){
        int u, v;
        cin >> u >> v;
        mp2[u] = v;
    }bool ok = true;
    for(auto i: mp2){
        if(mp3[i.first] < i.second){
            ok = false;
            break;
        }
    }if(!ok){
        cout << "impossible";
        return 0;
    }int l = 0, r = 0, c = 0, mn = INT_MAX;
    for(int i = 0; i < n; i++){
        mp[a[i]]++;
        if(mp[a[i]] == mp2[a[i]]){
            c++;
            if(c == m){
                r = i;
                break;
            }
        }
    }while(l < r){
        if(mp[a[l]] > mp2[a[l]]){
            
            mp[a[l]]--;
            l++;
        }else {
            break;
        }
        
    }mn = min(mn, r-l+1);
    c = 0;
    r++;

    while (r < n){
        mp[a[l]]--;
        c = 0;
        int num;
        if(mp2[a[l]] > mp[a[l]]){
            c = 1;
            num = a[l];
        }l++;
        if(!c){
            mn = min(mn, r-l+1);
        }
        bool ok = false;
        if(c){
            while(r < n){
                if(mp[num] < mp2[num]){
                    mp[a[r]]++;
                    
                    if(mp[num] >= mp2[num]){
                        ok = true;
                        mp[a[r]]--;
                        break;
                    }
                    r++;
                    
                }else {
                    break;
                }
            }
        }if(ok){
            mn = min(mn, r-l+1);
        }
    }cout << mn;
    
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen("main.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("main.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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