Submission #391731

#	Time	Username	Problem	Language	Result	Execution time	Memory
391731		ollel	Martian DNA (BOI18_dna)	C++14	0 / 100	2070 ms	5748 KiB

dna

#include <bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define lso(x) x&(-x)

int n, k, r;
vi dna;
vi minr;
map<int,int> cmp;
vi ocs;

bool yes() {
  rep(i,0,r) {
    if (ocs[i] < minr[i]) return false;
  }
  return true;
}

int main()
{
  cin>>n>>k>>r;
  dna.resize(n);
  minr.resize(r);
  rep(i,0,n) cin>>dna[i];
  int b, q, cm=0;
  rep(i,0,r) {

    cin>>b>>q;
    cmp[b] = cm;cm++;

    minr[cmp[b]] = q;
  }
  ocs.resize(r, 0);
  int s = 0, e = 0, minl = 10000000;
  if (cmp.find(dna[0]) != cmp.end()) ocs[cmp[dna[0]]]++;
  while (e < n) {
    if (yes()) { minl = min(minl, e - s);
      if (cmp.find(dna[s]) != cmp.end()) ocs[cmp[dna[s]]]--;
      s++;
    }
    else { e++;
      if (cmp.find(dna[e]) != cmp.end()) ocs[dna[e]]++;
    }
  }
  if (minl!=10000000) cout << minl+1 << endl;
  else cout << "impossible" <<endl;
}

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