답안 #962992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
962992	2024-04-14T10:33:29 Z	LucaIlie	Lottery (CEOI18_lot)	C++17	100 / 100	726 ms	6352 KB

#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.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	23 ms	888 KB	Output is correct
14	Correct	18 ms	764 KB	Output is correct
15	Correct	20 ms	768 KB	Output is correct
16	Correct	19 ms	860 KB	Output is correct
17	Correct	18 ms	848 KB	Output is correct
18	Correct	21 ms	856 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	671 ms	2524 KB	Output is correct
2	Correct	659 ms	2524 KB	Output is correct
3	Correct	530 ms	2392 KB	Output is correct
4	Correct	546 ms	2496 KB	Output is correct
5	Correct	372 ms	1540 KB	Output is correct
6	Correct	488 ms	2396 KB	Output is correct
7	Correct	343 ms	1544 KB	Output is correct
8	Correct	398 ms	1940 KB	Output is correct
9	Correct	520 ms	2468 KB	Output is correct
10	Correct	489 ms	2488 KB	Output is correct
11	Correct	37 ms	896 KB	Output is correct
12	Correct	360 ms	1928 KB	Output is correct
13	Correct	407 ms	1728 KB	Output is correct
14	Correct	420 ms	1720 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	671 ms	2524 KB	Output is correct
2	Correct	659 ms	2524 KB	Output is correct
3	Correct	530 ms	2392 KB	Output is correct
4	Correct	546 ms	2496 KB	Output is correct
5	Correct	372 ms	1540 KB	Output is correct
6	Correct	488 ms	2396 KB	Output is correct
7	Correct	343 ms	1544 KB	Output is correct
8	Correct	398 ms	1940 KB	Output is correct
9	Correct	520 ms	2468 KB	Output is correct
10	Correct	489 ms	2488 KB	Output is correct
11	Correct	37 ms	896 KB	Output is correct
12	Correct	360 ms	1928 KB	Output is correct
13	Correct	407 ms	1728 KB	Output is correct
14	Correct	420 ms	1720 KB	Output is correct
15	Correct	537 ms	2468 KB	Output is correct
16	Correct	462 ms	2336 KB	Output is correct
17	Correct	516 ms	2528 KB	Output is correct
18	Correct	535 ms	2508 KB	Output is correct
19	Correct	500 ms	2772 KB	Output is correct
20	Correct	518 ms	2508 KB	Output is correct
21	Correct	495 ms	2516 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	344 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	23 ms	888 KB	Output is correct
14	Correct	18 ms	764 KB	Output is correct
15	Correct	20 ms	768 KB	Output is correct
16	Correct	19 ms	860 KB	Output is correct
17	Correct	18 ms	848 KB	Output is correct
18	Correct	21 ms	856 KB	Output is correct
19	Correct	671 ms	2524 KB	Output is correct
20	Correct	659 ms	2524 KB	Output is correct
21	Correct	530 ms	2392 KB	Output is correct
22	Correct	546 ms	2496 KB	Output is correct
23	Correct	372 ms	1540 KB	Output is correct
24	Correct	488 ms	2396 KB	Output is correct
25	Correct	343 ms	1544 KB	Output is correct
26	Correct	398 ms	1940 KB	Output is correct
27	Correct	520 ms	2468 KB	Output is correct
28	Correct	489 ms	2488 KB	Output is correct
29	Correct	37 ms	896 KB	Output is correct
30	Correct	360 ms	1928 KB	Output is correct
31	Correct	407 ms	1728 KB	Output is correct
32	Correct	420 ms	1720 KB	Output is correct
33	Correct	537 ms	2468 KB	Output is correct
34	Correct	462 ms	2336 KB	Output is correct
35	Correct	516 ms	2528 KB	Output is correct
36	Correct	535 ms	2508 KB	Output is correct
37	Correct	500 ms	2772 KB	Output is correct
38	Correct	518 ms	2508 KB	Output is correct
39	Correct	495 ms	2516 KB	Output is correct
40	Correct	702 ms	3276 KB	Output is correct
41	Correct	363 ms	2548 KB	Output is correct
42	Correct	514 ms	3288 KB	Output is correct
43	Correct	521 ms	2956 KB	Output is correct
44	Correct	501 ms	2952 KB	Output is correct
45	Correct	726 ms	6352 KB	Output is correct
46	Correct	373 ms	2800 KB	Output is correct
47	Correct	559 ms	6352 KB	Output is correct
48	Correct	535 ms	4732 KB	Output is correct
49	Correct	544 ms	5360 KB	Output is correct

답안 #962992

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0