oj.uz

답안 #382268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382268 2021-03-26T21:21:48 Z vishesh312 Martian DNA (BOI18_dna) C++17
0 / 100
 32 ms 1388 KB 
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

using ll = long long;
const int mod = 1e9+7;

void solve(int tc) {
    int n, k, r;
    cin >> n >> k >> r;
    vector<int> v(n), a(k);
    vector<bool> need(k);
    for (auto &x : v) cin >> x;
    int req = 0;
    while (r--) {
        int b, q;
        cin >> b >> q;
        a[b] = q;
        req += q;
        need[b] = true;
    }
    int l = 0;
    r = 0;
    int ans = 1e9, cmp = 1e9;
    while (r < n-1) {
        while (!req) {
//          cout << "l r : " << l << " " << r << '\n';
            ans = min(ans, r-l+1);
            if (need[v[l]]) {
//              cout << "v[l] a[v[l]] : " << v[l] << " " << a[v[l]] << '\n';
                a[v[l]]++;
                if (a[v[l]] > 0) req++;
            }
            ++l;
        }
        while (req and r < n) {
            ++r;
            if (need[v[r]]) {
//              cout << "v[r] a[v[r]] " << v[r] << " " << a[v[r]] << '\n';
                if (a[v[r]] > 0) --req;
                a[v[r]]--;
//              cout << "a[v[r]] : " << a[v[r]] << '\n';
            }
        }
    }
    if (ans == cmp) cout << "impossible\n";
    else cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tc = 1;
    //cin >> tc;
    for (int i = 1; i <= tc; ++i) solve(i);
    return 0;
}

Subtask #1
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 1388 KB Output isn't correct
2 Halted 0 ms 0 KB -