답안 #643425

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643425	2022-09-22T03:09:00 Z	devariaota	Martian DNA (BOI18_dna)	C++17	100 / 100	31 ms	2636 KB

dna

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=2e5+5;
const int INF=1e9;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
int n, k, r, arr[maxn], cnt[maxn], hrs[maxn], x, y, ans=INF, ls=1, tot;
bool use[maxn];
int main() {
    ok
    cin >> n >> k >> r;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }
    for(int i=1; i<=r; i++) {
        cin >> x >> y;
        hrs[x]=y;
    }
    for(int i=1; i<=n; i++) {
        while(tot<r && ls<=n) {
            cnt[arr[ls]]++;
            if(!use[arr[ls]] && cnt[arr[ls]]>=hrs[arr[ls]] && hrs[arr[ls]]) {
                tot++;
                use[arr[ls]]=1;
            }
            ls++;
        }
        if(tot==r) {
            ans=min(ans, ls-i);
        }
        cnt[arr[i]]--;
        if(use[arr[i]] && cnt[arr[i]]<hrs[arr[i]]) {
            tot--;
            use[arr[i]]=0;
        }
    }
    if(ans==INF) cout << "impossible";
    else cout << ans;
}

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	1092 KB	Output is correct
2	Correct	13 ms	1052 KB	Output is correct
3	Correct	14 ms	1120 KB	Output is correct
4	Correct	13 ms	1120 KB	Output is correct
5	Correct	16 ms	1404 KB	Output is correct
6	Correct	12 ms	1108 KB	Output is correct
7	Correct	13 ms	1068 KB	Output is correct
8	Correct	18 ms	1864 KB	Output is correct
9	Correct	16 ms	1092 KB	Output is correct
10	Correct	12 ms	1108 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	1752 KB	Output is correct
2	Correct	23 ms	1612 KB	Output is correct
3	Correct	20 ms	1620 KB	Output is correct
4	Correct	12 ms	1064 KB	Output is correct
5	Correct	27 ms	1884 KB	Output is correct
6	Correct	31 ms	2636 KB	Output is correct
7	Correct	17 ms	1108 KB	Output is correct
8	Correct	21 ms	1188 KB	Output is correct
9	Correct	12 ms	1108 KB	Output is correct
10	Correct	17 ms	1124 KB	Output is correct
11	Correct	14 ms	1040 KB	Output is correct
12	Correct	13 ms	1108 KB	Output is correct
13	Correct	21 ms	1440 KB	Output is correct
14	Correct	12 ms	1004 KB	Output is correct
15	Correct	14 ms	1120 KB	Output is correct
16	Correct	18 ms	1920 KB	Output is correct
17	Correct	16 ms	1100 KB	Output is correct
18	Correct	13 ms	1056 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	0 ms	212 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	0 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	0 ms	340 KB	Output is correct
32	Correct	0 ms	212 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct