제출 #1290923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290923		diyah999	Martian DNA (BOI18_dna)	C++20	100 / 100	44 ms	5128 KiB

dna

#include<bits/stdc++.h>
using namespace std;
#define w long long
#define mod 1000000007


int main(){
  ios_base::sync_with_stdio(0);cin.tie(0);
  
  w n,k,R;
  cin>>n>>k>>R;
  
  vector<w>v(n);
  for(w i=0;i<n;++i)cin>>v[i];
  
  vector<w>needed(n);
  w g=0;
  for(w i=0;i<R;++i){
    w z,c;
    cin>>z>>c;
    needed[z]=c;
    g+=c;
  }
  
  
  w ans=n+1;
  
  
  w l=1,r=n;
  while(l<=r){
    w m=(l+r)/2;
    
    w cnt_of_needed=g;
    
    vector<w>acquired(n);
    
    for(w i=0;i<m;++i){
      
     
      
      // cout<<v[i]<<' ';
      if(needed[v[i]]>0){
        
        if(acquired[v[i]]<needed[v[i]]){
          cnt_of_needed--;
        }
        acquired[v[i]]++;
      }
    }
    
    
    // cout<<endl<<cnt_of_needed;
    w i=m;
    while(cnt_of_needed!=0&& i<n){
      
      
      if(needed[v[i]]){
        
        if(acquired[v[i]]<needed[v[i]]){
          cnt_of_needed--;
        }
        acquired[v[i]]++;
      }
      
      if(needed[v[i-m]]){
        
        if(acquired[v[i-m]]<=needed[v[i-m]]){
          cnt_of_needed++;
        }
        acquired[v[i-m]]--;
      }
      // cout<<i<<" : "<<m<<' '<<cnt_of_needed<<endl;
      i++;
    }
    
    
    
    // cout<<m<<endl;
    if(cnt_of_needed==0){
      // cout<<m<<endl;
      ans=min(ans,m);
      r=m-1;
    }else l=m+1;
    
    // cout<<l<<endl;
  }
  
  if(ans==n+1)cout<<"impossible";
  else cout<<ans;
  
  
}

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