Submission #962992

#	Time	Username	Problem	Language	Result	Execution time	Memory
962992		LucaIlie	Lottery (CEOI18_lot)	C++17	100 / 100	726 ms	6352 KiB

lot

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 10000;
const int MAX_Q = 100;
int v[MAX_N], ind[MAX_N + 1], diag[MAX_N + 1], m[MAX_Q + 1], p[MAX_Q + 1];
short good[MAX_N][MAX_Q + 1];

int main() {
    cin.tie( NULL );
    cout.tie( NULL );
    ios_base::sync_with_stdio( false );

    int n, k;

    cin >> n >> k;
    for ( int i = 0; i < n; i++ )
        cin >> v[i];

    int q;
    cin >> q;
    for ( int i = 1; i <= q; i++ ) {
        cin >> m[i];
        ind[m[i]] = i;
    }
    for ( int i = n - 1; i >= 0; i-- ) {
        if ( ind[i] == 0 )
            ind[i] = ind[i + 1];
    }

    for ( int d = 1; d < n; d++ ) {
        for ( int i = 0; i < n; i++ )
            diag[i] = 0;

        for ( int i = 0; i < n - d; i++ ) {
            int j = i + d;
            if ( v[i] == v[j] )
                continue;
            int l = min( k, i + 1 );
            diag[i - l + 1]++;
            diag[i + 1]--;
        }

        for ( int i = 1; i < n; i++ )
            diag[i] += diag[i - 1];
        for ( int i = 0; i < n - d; i++ ) {
            int j = i + d;
            if ( i <= n - k && j <= n - k ) {
                good[i][ind[diag[i]]]++;
                good[j][ind[diag[i]]]++;
            }
        }
    }

    for ( int i = 1; i <= q; i++ )
        p[i] = i;
    sort( p + 1, p + 1 + q, []( int i, int j ) {
        if ( m[i] == m[j] )
            return i > j;
        return m[i] < m[j];
    } );
    for ( int i = 0; i < n; i++ ) {
        for ( int j = 2; j <= q; j++ )
            good[i][p[j]] += good[i][p[j - 1]];
    }

    for ( int i = 1; i <= q; i++ ) {
        for ( int j = 0; j <= n - k; j++ )
            cout << good[j][i] << " ";
        cout << "\n";
    }

    return 0;
}

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