Submission #1232409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232409		Hamed_Ghaffari	Lottery (CEOI18_lot)	C++20	100 / 100	427 ms	8280 KiB

lot

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

const int MXN = 10003, MXQ = 103;

int n, l, q, a[MXN], ans[MXQ][MXN], k[MXQ], ord[MXQ], dp[MXN], cnt[MXN];

inline int dif(int x, int y) {
    int res = 0;
    if(x>0 && y>0 && a[x-1]!=a[y-1]) res--;
    if(a[x+l-1]!=a[y+l-1]) res++;
    if(x==0 || y==0)
        for(int i=0; i+1<l; i++) res += a[x+i]!=a[y+i];
    return res;
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> l;
    for(int i=0; i<n; i++) cin >> a[i];
    cin >> q;
    for(int i=0; i<q; i++) {
        cin >> k[i];
        ord[i] = i;
    }
    sort(ord, ord+q, [&](int i, int j) { return k[i] < k[j]; });
    for(int i=0; i<n-l+1; i++) {
        fill(cnt, cnt+l+1, 0);
        for(int j=n-l; j>=0; j--)
            cnt[dp[j] = dif(i, j) + (j?dp[j-1]:0)]++;
        int ptr=0, sum=0;
        for(int j=0; j<q; j++) {
            while(ptr<=k[ord[j]])
                sum += cnt[ptr++];
            ans[ord[j]][i] = sum-1;
        }
    }
    for(int i=0; i<q; i++) {
        for(int j=0; j<n-l+1; j++)
            cout << ans[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}

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