Submission #1169358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169358		InvMOD	Martian DNA (BOI18_dna)	C++20	100 / 100	19 ms	2832 KiB

dna

#include<bits/stdc++.h>

using namespace std;


void solve()
{
    int n,K,R; cin >> n >> K >> R;

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

    vector<int> req(K), cnt(K);
    for(int i = 0; i < R; i++){
        int d; cin >> d >> req[d];
    }

    int bad = 0;
    for(int i = 0; i < K; i++){
        bad += (cnt[i] < req[i]);
    }

    int answer = INT_MAX;
    for(int i = 0, j = 0; i < n; i++){
        ++cnt[D[i]]; bad -= (cnt[D[i]] == req[D[i]]);

        while(j < i && cnt[D[j]] > req[D[j]]){
            --cnt[D[j]];
            j++;
        }
        //cout << i <<" " << j <<" " << bad << "\n";
        if(!bad) answer = min(answer, i - j + 1);
    }
    if(answer == INT_MAX) cout << "impossible\n";
    else cout << answer << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    solve();
    return 0;
}

Compilation message (stderr)

dna.cpp: In function 'int32_t main()':
dna.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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