oj.uz

Submission #1009800

# Submission time Handle Problem Language Result Execution time Memory
1009800 2024-06-28T05:07:03 Z devariaota Martian DNA (BOI18_dna) C++17
68 / 100
 2000 ms 15688 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define inf LLONG_MAX
#define pb push_back
#define lc 2*pos+1
#define rc 2*pos+2
#define halleluya  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
signed main(){
halleluya
    int n,k,re;cin>>n>>k>>re;
    int num[n];
    map<int,int>req;
    map<int,int>freq;
    vector<int>jum;

    for (int i=0;i<n;i++)cin>>num[i];    
    while (re--){
        int x,y;cin>>x>>y;
        req[x]=y;
        jum.pb(x);
    }

    // for (int i=0;i<n;i++){
    //     for (auto x:jum) {
    //         if (0<i) freq[{i,x}]=freq[{i-1,x}];
    //         if (x==num[i]) freq[{i,x}]++;
    //     }
    // }
    int l=0,r=1;
    freq[num[0]]++;
    freq[num[1]]++;
    int ans=inf;
    while(l<=r){
        bool sal=1;
        for (auto x:jum){
            while (freq[x]<req[x] && r+1<n){
                r++;  
                freq[num[r]]++;
            }
            if (freq[x]<req[x] && r==n-1) sal=0;
            
        }
        if (sal) ans=min(ans,r-l+1);
        freq[num[l]]--;
        l++;
    }
    if (ans==inf)cout<<"impossible";
    else cout<<ans;
}

// impossible -> jumlah kurang atau emang gaada substringnya 
// harus consecutive
// constraint r 
// cuman perlu shortest
// sliding window?
// cuma save jumlah k 
// n*k

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 452 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 456 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2396 KB Output is correct
2 Correct 10 ms 2396 KB Output is correct
3 Correct 36 ms 2396 KB Output is correct
4 Correct 35 ms 2432 KB Output is correct
5 Correct 185 ms 8124 KB Output is correct
6 Correct 38 ms 2396 KB Output is correct
7 Correct 56 ms 2396 KB Output is correct
8 Correct 238 ms 15688 KB Output is correct
9 Correct 104 ms 3408 KB Output is correct
10 Correct 45 ms 2396 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 404 KB Output is correct
13 Correct 2 ms 664 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 2 ms 600 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 600 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 32.0

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