답안 #73126 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73126	2018-08-27T18:07:03 Z	win11905	Lottery (CEOI18_lot)	C++11	100 / 100	1118 ms	9252 KB

#include <bits/stdc++.h>
using namespace std;

const int N = 2e4+5;
const int O = 10001;
const int Q = 105;

int n, l, q;
int cnt[N];
int A[N], dp[2][N], ans[Q][N], v[Q];

int main() {
    scanf("%d %d", &n, &l);
    for(int i = 1; i <= n; ++i) scanf("%d", A+i);
    scanf("%d", &q);
    for(int i = 0; i < q; ++i) scanf("%d", v+i);
    for(int i = 2-l; i <= n-l+1; ++i) {
        int z = (O+i)&1;
        memset(cnt, 0, sizeof cnt);
        for(int j = 2-l; j <= n-l+1; ++j) {
            dp[z][O+j] = dp[z^1][O+j-1];
            int a = i+l-1, b = j+l-1;
            int c = i-1, d = j-1;
            if(a >= 1 && b >= 1 && a <= n && b <= n)
                dp[z][O+j] += A[a] != A[b];
            if(c >= 1 && d >= 1 && c <= n && d <= n)
                dp[z][O+j] -= A[c] != A[d];
            if(i >= 1 && j >= 1) 
                cnt[dp[z][O+j]]++;
        }
        for(int j = 1; j <= n; ++j)
            cnt[j] += cnt[j-1];
        if(i >= 1) for(int j = 0; j < q; ++j)
            ans[j][i] = cnt[v[j]];
    }
    for(int i = 0; i < q; ++i) {
        for(int j = 1; j <= n-l+1; ++j) {
            printf("%d ", ans[i][j]-1);
        }
        puts("");
    }
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:14:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%d", A+i);
                                 ~~~~~^~~~~~~~~~~
lot.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
lot.cpp:16:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < q; ++i) scanf("%d", v+i);
                                ~~~~~^~~~~~~~~~~

Subtask #1
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	616 KB	Output is correct
3	Correct	3 ms	616 KB	Output is correct
4	Correct	3 ms	616 KB	Output is correct
5	Correct	3 ms	616 KB	Output is correct
6	Correct	3 ms	616 KB	Output is correct
7	Correct	3 ms	716 KB	Output is correct
8	Correct	5 ms	796 KB	Output is correct
9	Correct	4 ms	796 KB	Output is correct
10	Correct	5 ms	796 KB	Output is correct
11	Correct	4 ms	796 KB	Output is correct
12	Correct	5 ms	796 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	616 KB	Output is correct
3	Correct	3 ms	616 KB	Output is correct
4	Correct	3 ms	616 KB	Output is correct
5	Correct	3 ms	616 KB	Output is correct
6	Correct	3 ms	616 KB	Output is correct
7	Correct	3 ms	716 KB	Output is correct
8	Correct	5 ms	796 KB	Output is correct
9	Correct	4 ms	796 KB	Output is correct
10	Correct	5 ms	796 KB	Output is correct
11	Correct	4 ms	796 KB	Output is correct
12	Correct	5 ms	796 KB	Output is correct
13	Correct	45 ms	796 KB	Output is correct
14	Correct	44 ms	960 KB	Output is correct
15	Correct	41 ms	960 KB	Output is correct
16	Correct	44 ms	1000 KB	Output is correct
17	Correct	46 ms	1000 KB	Output is correct
18	Correct	59 ms	1056 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	963 ms	1068 KB	Output is correct
2	Correct	1056 ms	1200 KB	Output is correct
3	Correct	1022 ms	1200 KB	Output is correct
4	Correct	978 ms	1200 KB	Output is correct
5	Correct	864 ms	1200 KB	Output is correct
6	Correct	962 ms	1200 KB	Output is correct
7	Correct	807 ms	1200 KB	Output is correct
8	Correct	830 ms	1200 KB	Output is correct
9	Correct	996 ms	1200 KB	Output is correct
10	Correct	1000 ms	1212 KB	Output is correct
11	Correct	87 ms	1212 KB	Output is correct
12	Correct	769 ms	1212 KB	Output is correct
13	Correct	805 ms	1212 KB	Output is correct
14	Correct	789 ms	1212 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	963 ms	1068 KB	Output is correct
2	Correct	1056 ms	1200 KB	Output is correct
3	Correct	1022 ms	1200 KB	Output is correct
4	Correct	978 ms	1200 KB	Output is correct
5	Correct	864 ms	1200 KB	Output is correct
6	Correct	962 ms	1200 KB	Output is correct
7	Correct	807 ms	1200 KB	Output is correct
8	Correct	830 ms	1200 KB	Output is correct
9	Correct	996 ms	1200 KB	Output is correct
10	Correct	1000 ms	1212 KB	Output is correct
11	Correct	87 ms	1212 KB	Output is correct
12	Correct	769 ms	1212 KB	Output is correct
13	Correct	805 ms	1212 KB	Output is correct
14	Correct	789 ms	1212 KB	Output is correct
15	Correct	1018 ms	1212 KB	Output is correct
16	Correct	983 ms	1212 KB	Output is correct
17	Correct	1012 ms	1216 KB	Output is correct
18	Correct	992 ms	1216 KB	Output is correct
19	Correct	933 ms	1216 KB	Output is correct
20	Correct	953 ms	1216 KB	Output is correct
21	Correct	950 ms	1216 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	616 KB	Output is correct
3	Correct	3 ms	616 KB	Output is correct
4	Correct	3 ms	616 KB	Output is correct
5	Correct	3 ms	616 KB	Output is correct
6	Correct	3 ms	616 KB	Output is correct
7	Correct	3 ms	716 KB	Output is correct
8	Correct	5 ms	796 KB	Output is correct
9	Correct	4 ms	796 KB	Output is correct
10	Correct	5 ms	796 KB	Output is correct
11	Correct	4 ms	796 KB	Output is correct
12	Correct	5 ms	796 KB	Output is correct
13	Correct	45 ms	796 KB	Output is correct
14	Correct	44 ms	960 KB	Output is correct
15	Correct	41 ms	960 KB	Output is correct
16	Correct	44 ms	1000 KB	Output is correct
17	Correct	46 ms	1000 KB	Output is correct
18	Correct	59 ms	1056 KB	Output is correct
19	Correct	963 ms	1068 KB	Output is correct
20	Correct	1056 ms	1200 KB	Output is correct
21	Correct	1022 ms	1200 KB	Output is correct
22	Correct	978 ms	1200 KB	Output is correct
23	Correct	864 ms	1200 KB	Output is correct
24	Correct	962 ms	1200 KB	Output is correct
25	Correct	807 ms	1200 KB	Output is correct
26	Correct	830 ms	1200 KB	Output is correct
27	Correct	996 ms	1200 KB	Output is correct
28	Correct	1000 ms	1212 KB	Output is correct
29	Correct	87 ms	1212 KB	Output is correct
30	Correct	769 ms	1212 KB	Output is correct
31	Correct	805 ms	1212 KB	Output is correct
32	Correct	789 ms	1212 KB	Output is correct
33	Correct	1018 ms	1212 KB	Output is correct
34	Correct	983 ms	1212 KB	Output is correct
35	Correct	1012 ms	1216 KB	Output is correct
36	Correct	992 ms	1216 KB	Output is correct
37	Correct	933 ms	1216 KB	Output is correct
38	Correct	953 ms	1216 KB	Output is correct
39	Correct	950 ms	1216 KB	Output is correct
40	Correct	1058 ms	2560 KB	Output is correct
41	Correct	754 ms	2560 KB	Output is correct
42	Correct	1040 ms	2628 KB	Output is correct
43	Correct	921 ms	2628 KB	Output is correct
44	Correct	1103 ms	2628 KB	Output is correct
45	Correct	1059 ms	8940 KB	Output is correct
46	Correct	823 ms	8940 KB	Output is correct
47	Correct	1057 ms	9252 KB	Output is correct
48	Correct	1118 ms	9252 KB	Output is correct
49	Correct	1065 ms	9252 KB	Output is correct

답안 #73126

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