Submission #1150193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150193		Robert_junior	Martian DNA (BOI18_dna)	C++20	0 / 100	2096 ms	160140 KiB

dna

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define ins insert
#define pb push_back
#define F first
#define S second
const int N = 3e5 + 7, M = 5e5 + 7;
int a[N], p[N][101], mn[N];
void solve(){
    int n, m, k;
    cin>>n>>m>>k;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        for(int j = 0; j < m; j++){
            p[i][j] = p[i - 1][j];
        }
        p[i][a[i]]++;
    }
    for(int i = 1; i <= k; i++){
        int x, y;
        cin>>x>>y;
        mn[x] = y;
    }
    int ans = INT_MAX;
    for(int i = 1; i <= n; i++){
        int l = i, r = n;
        while(l <= r){
            int m1 = (l + r) / 2;
            bool ok = 1;
            for(int j = 0; j < m; j++){
                if(p[m1][j] - p[i - 1][j] < mn[j]){
                    ok = 0;
                    break;
                }
            }
            if(!ok){
                l = m1 + 1;
            }
            else{
                r = m1 - 1;
                ans = min(ans, m1 - i + 1);
            }
        }
    }
    if(ans == INT_MAX) cout<<-1;
    else cout<<ans;
}
main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin>>t; 
    for(int i = 1; i <= t; i++){
        //cout<<"Case "<<i<<": ";
        solve();
    }
}

Compilation message (stderr)

dna.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~

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