답안 #482983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482983	2021-10-27T08:47:01 Z	DJeniUp	Martian DNA (BOI18_dna)	C++17	100 / 100	124 ms	5252 KB

dna

#pragma GCC Optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,pairll>pairlll;
typedef pair<pairll,pairll>pairllll;
typedef long double ld;
typedef pair<ll,string>pairls;

#define INF 1000000000000007
#define MOD 1000000007
#define pb push_back
#define fr first
#define sc second
#define endl '\n'

ll n,k,d[200007],f[200007];

int main() {
    
    cin>>n>>k>>k;
    for(int i=1;i<=n;i++){
         cin>>d[i];
    }
    for(int i=1;i<=k;i++){
        ll x,y;
        cin>>x>>y;
        f[x]=y;
    }
    ll l=1;
    ll r=0;
    ll res=INF;
    for(int i=1;i<=n;i++){
        
        r=i;
        f[d[r]]--;
        if(f[d[r]]==0)k--;
        while(l<r && f[d[l]]<0){
            f[d[l]]++;
            l++;
        }
        if(k==0)res=min(res,r-l+1);
    }
    if(res==INF)cout<<"impossible"<<endl;
    else cout<<res<<endl;

}

Compilation message

dna.cpp:1: warning: ignoring '#pragma GCC Optimize' [-Wunknown-pragmas]
    1 | #pragma GCC Optimize("O3")
      |

Subtask #1

16.0 / 16.0

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

Subtask #2

24.0 / 24.0

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

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	26 ms	1736 KB	Output is correct
2	Correct	31 ms	2164 KB	Output is correct
3	Correct	28 ms	2244 KB	Output is correct
4	Correct	27 ms	2176 KB	Output is correct
5	Correct	50 ms	3504 KB	Output is correct
6	Correct	26 ms	2172 KB	Output is correct
7	Correct	30 ms	2392 KB	Output is correct
8	Correct	54 ms	4600 KB	Output is correct
9	Correct	44 ms	2780 KB	Output is correct
10	Correct	27 ms	2156 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	0 ms	204 KB	Output is correct
18	Correct	1 ms	204 KB	Output is correct
19	Correct	1 ms	204 KB	Output is correct
20	Correct	1 ms	300 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Correct	1 ms	204 KB	Output is correct
23	Correct	1 ms	204 KB	Output is correct
24	Correct	0 ms	204 KB	Output is correct
25	Correct	0 ms	204 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	85 ms	2436 KB	Output is correct
2	Correct	71 ms	3916 KB	Output is correct
3	Correct	61 ms	3604 KB	Output is correct
4	Correct	30 ms	2132 KB	Output is correct
5	Correct	92 ms	4780 KB	Output is correct
6	Correct	124 ms	5252 KB	Output is correct
7	Correct	46 ms	2884 KB	Output is correct
8	Correct	51 ms	3140 KB	Output is correct
9	Correct	25 ms	2184 KB	Output is correct
10	Correct	28 ms	2232 KB	Output is correct
11	Correct	29 ms	2192 KB	Output is correct
12	Correct	27 ms	2176 KB	Output is correct
13	Correct	49 ms	3512 KB	Output is correct
14	Correct	25 ms	2172 KB	Output is correct
15	Correct	30 ms	2392 KB	Output is correct
16	Correct	59 ms	4664 KB	Output is correct
17	Correct	47 ms	2940 KB	Output is correct
18	Correct	26 ms	2116 KB	Output is correct
19	Correct	2 ms	332 KB	Output is correct
20	Correct	2 ms	332 KB	Output is correct
21	Correct	2 ms	332 KB	Output is correct
22	Correct	1 ms	316 KB	Output is correct
23	Correct	1 ms	332 KB	Output is correct
24	Correct	1 ms	332 KB	Output is correct
25	Correct	0 ms	296 KB	Output is correct
26	Correct	0 ms	296 KB	Output is correct
27	Correct	1 ms	204 KB	Output is correct
28	Correct	0 ms	204 KB	Output is correct
29	Correct	0 ms	204 KB	Output is correct
30	Correct	0 ms	204 KB	Output is correct
31	Correct	0 ms	204 KB	Output is correct
32	Correct	0 ms	204 KB	Output is correct
33	Correct	0 ms	204 KB	Output is correct