Submission #1251367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251367		minhpk	Lottery (CEOI18_lot)	C++20	45 / 100	403 ms	49468 KiB

lot

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int a, b;
    cin >> a >> b;
    int rows = a - b + 1;
    int *z = new int[a+1];
    for(int i = 1; i <= a; i++){
        cin >> z[i];
    }

    short *fdata = new short[(rows+1)*(b+1)];
    short **f = new short*[rows+2];
    for(int i = 1; i <= rows; i++){
        f[i] = fdata + i*(b+1);
        memset(f[i], 0, (b+1)*sizeof(short));
    }

    for(int i = 2; i + b - 1 <= a; i++){
        int sta = 1, sta1 = i, cur = 0;
        for(int j = 0; j < b; j++){
            if(z[sta + j] != z[sta1 + j])
                cur++;
        }
        f[sta][cur]++;
        f[sta1][cur]++;
        for(int j = i + b; j <= a; j++){
            if(z[sta] != z[sta1])
                cur--;
            sta++; sta1++;
            if(z[sta + b - 1] != z[sta1 + b - 1])
                cur++;
            f[sta][cur]++;
            f[sta1][cur]++;
        }
    }

    for(int i = 1; i <= rows; i++){
        for(int k = 1; k <= b; k++){
            f[i][k] += f[i][k-1];
        }
    }

    int Q;
    cin >> Q;
    while(Q--){
        int x;
        cin >> x;
        if(x > b) x = b;
        for(int i = 1; i <= rows; i++){
            cout << f[i][x] << (i<rows?' ':'\n');
        }
    }

    delete[] z;
    delete[] fdata;
    delete[] f;

    return 0;
}

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