제출 #1136769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136769		gyg	Lottery (CEOI18_lot)	C++17	45 / 100	61 ms	16196 KiB

lot

#include <bits/stdc++.h>
using namespace std;
#define arr array 
const int N = 2e3 + 5, K = 2e3 + 5;

int n, k;
arr<int, N> a;
int q;

arr<arr<int, N>, N> lk;
void prcmp() {
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i] != a[j]) continue;
            int dst = min(i, k);
            lk[i][j]++, lk[i - dst][j - dst]--;
            lk[j][i]++, lk[j - dst][i - dst]--;
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) cout << lk[i][j] << " ";
    //     cout << '\n'; 
    // }

    for (int d = -n + 1; d <= n - 1; d++) {
        int sm = 0;
        for (int i = n; i >= 1; i--) {
            int j = i + d;
            if (j < 1 || n < j) continue;
            sm += lk[i][j], lk[i][j] = sm;
        }
    }

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) cout << lk[i][j] << " ";
    //     cout << '\n'; 
    // }
}

void cmp(int df) {
    for (int i = 1; i <= n - k + 1; i++) {
        int cnt = 0;
        for (int j = 1; j <= n - k + 1; j++)
            if (j != i) cnt += (lk[i][j] >= k - df);
        cout << cnt << " ";
    }
    cout << '\n';
}

signed main() {
    // freopen("in", "r", stdin);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> q; 
    prcmp();
    for (int i = 1; i <= q; i++) { int x; cin >> x; cmp(x); }
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20