oj.uz

Submission #391731

# Submission time Handle Problem Language Result Execution time Memory
391731 2021-04-19T15:46:55 Z ollel Martian DNA (BOI18_dna) C++14
0 / 100
 2000 ms 5748 KB 
#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.0

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

Subtask #2
0 / 24.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 5748 KB Time limit exceeded
2 Halted 0 ms 0 KB -