oj.uz

Submission #768312

# Submission time Handle Problem Language Result Execution time Memory
768312 2023-06-27T21:59:17 Z Yell0 Martian DNA (BOI18_dna) C++17
0 / 100
 50 ms 7132 KB 
#include <bits/stdc++.h>

using namespace std;
const int MN=2e5+2;
int N,K,R,d[MN],req[MN],f[MN];

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>N>>K>>R;
  for(int i=1;i<=N;++i) cin>>d[i];
  set<int> needs;
  for(int i=1;i<=R;++i) {
    int b,q;
    cin>>b>>q;
    req[b]=q;
    needs.insert(b);
  }
  int l=1,r=1;
  for(;r<=N;++r) {
    if(needs.empty()) break;
    if(++f[d[r]]==req[d[r]]) needs.erase(d[r]);
  }
  if(r>N) {
    cout<<"impossible\n";
    return 0;
  }
  int ans=r-l;
  for(;l<=N;++l) {
    --f[d[l]];
    while(f[d[l]]<req[d[l]]&&r<=N) {
      ++req[d[r]];
      ++r;
    }
    if(r>N) {
      cout<<ans<<'\n';
      return 0;
    }
    ans=min(ans,r-l-1);
  }
  cout<<ans<<'\n';
  return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 7132 KB Output isn't correct
2 Halted 0 ms 0 KB -