Submission #575694

#	Time	Username	Problem	Language	Result	Execution time	Memory
575694		andrei_boaca	Lottery (CEOI18_lot)	C++14	100 / 100	901 ms	8304 KiB

lot

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int n,v[10005],l,q;
int sol[105][10005];
int cnt[10005];
struct date
{
    int poz,val;
} query[105];
bool comp(date a, date b)
{
    return a.val>b.val;
}
int where[10005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>l;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        query[i].poz=i;
        cin>>query[i].val;
        query[i].val=l-query[i].val;
    }
    sort(query+1,query+q+1,comp);
    for(int i=0;i<=l;i++)
    {
        where[i]=q+1;
        for(int j=1;j<=q;j++)
            if(i>=query[j].val)
            {
                where[i]=j;
                break;
            }
    }
    for(int dist=1;dist<=n;dist++)
    {
        for(int i=1;i<=n;i++)
            cnt[i]=0;
        for(int i=1;i<=n;i++)
        {
            int j=i+dist;
            if(j>n)
                break;
            if(v[i]==v[j])
            {
                int lft=max(1,i-l+1);
                int rgt=j;
                if(j+l-1>n)
                    rgt=n-l+1;
                rgt-=dist;
                if(lft<=rgt)
                {
                    cnt[lft]++;
                    cnt[rgt+1]--;
                }
            }
        }
        for(int i=1;i<=n;i++)
            cnt[i]+=cnt[i-1];
        for(int i=1;i+l-1<=n;i++)
        {
            int j=i+dist;
            if(j+l-1>n)
                break;
            int val=cnt[i];
            int poz=where[val];
            sol[poz][i]++;
            sol[poz][j]++;
        }
    }
    for(int poz=1;poz<=q;poz++)
        for(int i=1;i+l-1<=n;i++)
            sol[poz][i]+=sol[poz-1][i];
    for(int i=1;i<=q;i++)
    {
        int who=0;
        for(int j=1;j<=q;j++)
            if(query[j].poz==i)
            {
                who=j;
                break;
            }
        for(int j=1;j+l-1<=n;j++)
            cout<<sol[who][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