제출 #1290912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290912		al_reem_2010	Martian DNA (BOI18_dna)	C++20	40 / 100	2095 ms	3132 KiB

dna

// اَللَهُمَ صَلِ عَلَىَ مُحَمَدٍ وَ آلِ مُحَمَدٍ
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <thread>
#include <fstream>
#include <stack>
using namespace std ;
#define int long long
#define pb push_back
#define si size()
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define applejuice ios::sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
const int inf=1e18 ;
const int mod=1e9+7 ;
const int maxn=2*1e5+7 ;
int tt=1 ;
int a[maxn] , cnt[maxn] , cnt1[maxn] ;
void solve()
{
    int n , r , k ;
    cin >> n >> r >> k ;
    //cout << n << " " << k << " " << r << "\n" ;
    for(int i=0 ; i<n ; i++) {cin >> a[i] ;}
    int x , cntt ;
    //cout << "done " ;
    for(int i=0 ; i<k ; i++) {cin >> x >> cntt ; cnt[x]=cntt ;}
    //cout << "done 2" ;
    int s=1 , e=n , mid , ans=-1 ;
    //cout << "!!" ;
    while(s<=e)
    {
        mid=(s+e)/2 ;
        bool A=0 ;
        for(int i=0 ; i<mid ; i++) {cnt1[a[i]]+=1 ;}
        bool B=1 ;
        for(int i=0 ; i<r ; i++) {B=(cnt[i]<=cnt1[i] ? B : 0) ;}
        A=(A|B) ;
        for(int i=0 ; mid+i<n ; i++)
        {
            B=1 ;
            cnt1[a[i]]-=1 ;
            cnt1[a[mid+i]]+=1 ;
            for(int i=0 ; i<r ; i++) {B=(cnt[i]<=cnt1[i] ? B : 0) ;}
            A=(A|B) ;
        }
        if(A) {ans=mid ; e=mid-1 ;}
        else {s=mid+1 ;}
        for(int i=0 ; i<r ; i++) {cnt1[i]=0 ;}
    }
    if(ans==-1) {cout << "impossible" ; return ;}
    cout << ans ;
}
signed main()
{
    //wrong
    applejuice ;
    //cin >> tt ;
    while(tt--) {solve() ;}
}
/*
 5 2 2
 0 1 1 0 1
 0 1
 1 1
 */

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