Submission #1030586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030586		vjudge1	Lottery (CEOI18_lot)	C++14	100 / 100	161 ms	8352 KiB

lot

#include<bits/stdc++.h>


using namespace std;

const int MAXN = 1e4 + 5;

int n, l, q, a[MAXN];

int mq[MAXN], nxt[MAXN] , ans[105][MAXN];

bool idx[MAXN];

vector<int> con;


void solve()
{
    cin >> n >> l;

    for(int i = 1; i <= n; i++) cin >> a[i];

    cin >> q;

    for(int i = 1; i <= q; i++)
    {
        cin >> mq[i];
        idx[mq[i]] = 1;

        con.push_back(mq[i]);
    }

    sort(con.begin(),con.end());
    con.erase(unique(con.begin(),con.end()),con.end());

    int k = con.size() + 1;

    for(int i = n; i >= 0; i--)
    {
        if(idx[i])k--;
        nxt[i] = k;
    }


    vector<int> f(n + 5,0);
    
    for(int len = 1; len <= n; len++)
    {
        for(int i = 1; i <= n; i++)
        {
            f[i] = 0;
        }
        for(int i = 1; i + len <= n; i++)
        {
            f[i] = f[i - 1] + (a[i] != a[i + len]);
        }
        for(int i = 1; i + l - 1 <= n; i++)
        {
            if(i + len + l - 1 > n)break;
            int cost = nxt[f[i + l - 1] - f[i - 1]];
            ans[cost][i]++;
            ans[cost][i + len]++;
        }
    }

    for(int i = 1; i <= con.size(); i++)
    {
        for(int j = 1; j <= n; j++)
        {
            ans[i][j] += ans[i - 1][j];
        }
    }
    
    // truy van 

    for(int i = 1; i <= q; i++)
    {
        int x = lower_bound(con.begin(),con.end(),mq[i]) - con.begin() + 1;
        for(int j = 1; j <= n - l + 1; j++)
        {
            cout << ans[x][j] << " \n"[j == n - l + 1];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'void solve()':
lot.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 1; i <= con.size(); i++)
      |                    ~~^~~~~~~~~~~~~

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