Submission #307518

#	Time	Username	Problem	Language	Result	Execution time	Memory
307518		wildturtle	Lottery (CEOI18_lot)	C++14	0 / 100	2887 ms	52568 KiB

lot

#include<bits/stdc++.h>
using namespace std;
int a,n,l,A[10004],C[10004],D[10004][102],ans[10004][102],t,r;
pair <int,int> B[10004];
set <pair <int,int>> st;
set <pair <int,int>>::iterator it;
int main() {
    cin>>n>>l;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
    }
    cin>>t;
    for(int i=1;i<=t;i++) {
        cin>>B[i].first;
        B[i].second=i;
    }
    sort(B+1,B+1+t);
    for(int i=1;i<=t;i++) {
        st.insert({B[i].first,i});
    }
    for(int d=1;d<=n-l;d++) {
        for(long long i=1;i<=n;i++)
        C[i]=0;
        for(int i=1;i<=n-d;i++) {
            r=i+d;
            if(A[i]!=A[r]) { C[i]=1; }
        }
        for(long long i=1;i<=n;i++) {
            //cout<<C[i]<<" ";
            C[i]+=C[i-1];
        }
        //cout<<endl;
        for(long long i=1;i+d+l-1<=n;i++) {
            r=i+l-1;
            a=C[r]-C[i-1];
            //cout<<a<<"-";
            it=st.upper_bound({a,-1});
            if(it==st.end()) { cout<<"*"; continue; }
            //cout<<(*it).second<<" ";
            D[i][(*it).second]++;
            D[i+d][(*it).second]++;
        }
        //cout<<endl;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=t;j++) {
            D[i][j]+=D[i][j-1];
        }
    }
    for(int i=1;i<=t;i++) {
        for(int j=1;j<=n;j++) {
            ans[j][B[i].second]=D[j][i];
        }
    }
    for(int i=1;i<=t;i++) {
        for(int j=1;j<=n-l+1;j++) {
            cout<<ans[j][i]<<" ";
        }
        cout<<endl;
    }
}

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