Submission #736458

#	Time	Username	Problem	Language	Result	Execution time	Memory
736458		study	Lottery (CEOI18_lot)	C++17	45 / 100	95 ms	65536 KiB

lot

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

const int N = 1e4+1;

int a[N], diff[N][N], ans[N][N];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,l;
    cin >> n >> l;
    for (int i=0; i<n; ++i){
        cin >> a[i];
    }
    for (int i=1; i<n-l+1; ++i){
        for (int j=0; j<l; ++j){
            if (a[i+j] != a[j]) diff[0][i]++;
        }
        ans[0][diff[0][i]]++;
        ans[i][diff[0][i]]++;
    }
    for (int i=1; i<n-l+1; ++i){
        for (int j=i+1; j<n-l+1; ++j){
            diff[i][j] = diff[i-1][j-1]-(a[i-1] != a[j-1])+(a[i+l-1] != a[j+l-1]);
            ans[i][diff[i][j]]++;
            ans[j][diff[i][j]]++;
        }
    }
    for (int i=0; i<n; ++i){
        for (int j=1; j<=l; ++j){
            ans[i][j] += ans[i][j-1];
        }
    }
    int q;
    cin >> q;
    while (q--){
        int k;
        cin >> k;
        for (int i=0; i<n-l+1; ++i) cout << ans[i][k] << ' ';
        cout << '\n';
    }
	return 0;
}

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