Submission #112305

#	Time	Username	Problem	Language	Result	Execution time	Memory
112305		reda	Lottery (CEOI18_lot)	C++14	45 / 100	3086 ms	9464 KiB

lot

#include <bits/stdc++.h>
#define MAXN 10005
using namespace std;
int arr[MAXN];
int dp[MAXN][MAXN]={0};
int ans[MAXN];
int main ()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,l,k,q;
    cin>>n>>l;
    for(int i=1;i<=n;i++)
        cin>>arr[i];
    if(n<=2000){
    for(int i=1;i<=n-l+1;i++)
    {
        for(int j=i+1;j<=n-l+1;j++)
        {
            int x=0;
            for(int p=0;p<l;p++)
                if (arr[i+p]!=arr[j+p])x++;
            dp[j][x]++;
            dp[i][x]++;
        }
    }
    for(int i =1; i<=n-l+1; i++)
        for (int j =0; j<= l; j++)
                dp[i][j+1]+= dp[i][j];
    cin>>q;
    while(q--)
    {
        cin>>k;
        for(int i=1;i<=n-l+1;i++)
            cout<<dp[i][k]<<' ';
        cout<<endl;
    }
    }
    else
    {
        cin>>q>>k;
            for (int i=1;i<=n-l+1;i++)
            {
                for (int j =i+1;j<=n-l+1;j++)
                {
                    int x=0;
                    for(int p=0;p<l;p++)
                        if (arr[i+p]!=arr[j+p])x++;
                    if(x<=k)
                    {
                    ans[i] ++;
                    ans[j] ++;
                    }
                }
            cout <<ans[i]<<' ';
            }
    }
    return 0;
}

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