답안 #92672 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92672	2019-01-04T09:52:24 Z	toloraia	Money (IZhO17_money)	C++14	100 / 100	1406 ms	215824 KB

money

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

const int MAXN = 1e6;

int n;
int a[MAXN + 5];
int b[MAXN + 5];
int A[MAXN + 5][25], B[MAXN + 5][25];
int le[MAXN + 5];
int dp[MAXN + 5];
int BI[MAXN + 5];

int datvla (int l, int r){
    if (l > r)
        return n + 1;
    int x = BI[r - l + 1];
    return min (A[l][x], B[r][x]);
}

int main()
{
    BI[2] = 1;
    for (int i = 3; i <= MAXN; i++){
        BI[i] = BI[i - 1];
        if ((i & (i - 1)) == 0)
            BI[i]++;
    }
    cin>>n;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    for (int i = 1; i <= MAXN; i++)
        b[i] = n + 1;
    for (int i = n; i >= 1; i--)
        b[a[i]] = i;
    for (int i = 1; i <= MAXN; i++){
        A[i][0] = b[i];
        B[i][0] = b[i];
    }
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= MAXN; j++){
            A[j][i] = A[j][i - 1];
            if (j + (1<<(i - 1)) <= MAXN)
                A[j][i] = min (A[j][i], A[j + (1<<(i - 1))][i - 1]);
            B[j][i] = B[j][i - 1];
            if (j - (1<<(i - 1)) >= 1)
                B[j][i] = min (B[j][i], B[j - (1<<(i - 1))][i - 1]);
        }
    le[1] = 1;
    for (int i = 2; i <= n; i++){
        le[i] = i;
        if (a[i] >= a[i - 1])
            le[i] = le[i - 1];
    }
    dp[1] = 1;
    for (int i = 2; i <= n; i++){
        int I = i;
        for (int j = 19; j >= 0; j--){
            if (I - (1<<j) < le[i])
                continue;
            if (datvla (a[I - (1<<j)] + 1, a[i] - 1) >= I - (1<<j))
                I -= (1<<j);
        }
        dp[i] = dp[I - 1] + 1;
    }
    cout<<dp[n]<<endl;
    return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	668 ms	203896 KB	Output is correct
2	Correct	703 ms	203896 KB	Output is correct
3	Correct	721 ms	204000 KB	Output is correct
4	Correct	696 ms	203896 KB	Output is correct
5	Correct	718 ms	204024 KB	Output is correct
6	Correct	737 ms	203996 KB	Output is correct
7	Correct	672 ms	203896 KB	Output is correct
8	Correct	675 ms	203868 KB	Output is correct
9	Correct	696 ms	203892 KB	Output is correct
10	Correct	664 ms	203896 KB	Output is correct
11	Correct	662 ms	204024 KB	Output is correct
12	Correct	738 ms	203924 KB	Output is correct
13	Correct	721 ms	204060 KB	Output is correct
14	Correct	788 ms	203896 KB	Output is correct
15	Correct	780 ms	203824 KB	Output is correct
16	Correct	796 ms	203900 KB	Output is correct

Subtask #2
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	668 ms	203896 KB	Output is correct
2	Correct	703 ms	203896 KB	Output is correct
3	Correct	721 ms	204000 KB	Output is correct
4	Correct	696 ms	203896 KB	Output is correct
5	Correct	718 ms	204024 KB	Output is correct
6	Correct	737 ms	203996 KB	Output is correct
7	Correct	672 ms	203896 KB	Output is correct
8	Correct	675 ms	203868 KB	Output is correct
9	Correct	696 ms	203892 KB	Output is correct
10	Correct	664 ms	203896 KB	Output is correct
11	Correct	662 ms	204024 KB	Output is correct
12	Correct	738 ms	203924 KB	Output is correct
13	Correct	721 ms	204060 KB	Output is correct
14	Correct	788 ms	203896 KB	Output is correct
15	Correct	780 ms	203824 KB	Output is correct
16	Correct	796 ms	203900 KB	Output is correct
17	Correct	786 ms	203896 KB	Output is correct
18	Correct	781 ms	204024 KB	Output is correct
19	Correct	783 ms	203896 KB	Output is correct
20	Correct	793 ms	203896 KB	Output is correct
21	Correct	799 ms	203896 KB	Output is correct
22	Correct	780 ms	203984 KB	Output is correct
23	Correct	749 ms	203896 KB	Output is correct
24	Correct	800 ms	203896 KB	Output is correct
25	Correct	797 ms	203896 KB	Output is correct
26	Correct	663 ms	203892 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	668 ms	203896 KB	Output is correct
2	Correct	703 ms	203896 KB	Output is correct
3	Correct	721 ms	204000 KB	Output is correct
4	Correct	696 ms	203896 KB	Output is correct
5	Correct	718 ms	204024 KB	Output is correct
6	Correct	737 ms	203996 KB	Output is correct
7	Correct	672 ms	203896 KB	Output is correct
8	Correct	675 ms	203868 KB	Output is correct
9	Correct	696 ms	203892 KB	Output is correct
10	Correct	664 ms	203896 KB	Output is correct
11	Correct	662 ms	204024 KB	Output is correct
12	Correct	738 ms	203924 KB	Output is correct
13	Correct	721 ms	204060 KB	Output is correct
14	Correct	788 ms	203896 KB	Output is correct
15	Correct	780 ms	203824 KB	Output is correct
16	Correct	796 ms	203900 KB	Output is correct
17	Correct	786 ms	203896 KB	Output is correct
18	Correct	781 ms	204024 KB	Output is correct
19	Correct	783 ms	203896 KB	Output is correct
20	Correct	793 ms	203896 KB	Output is correct
21	Correct	799 ms	203896 KB	Output is correct
22	Correct	780 ms	203984 KB	Output is correct
23	Correct	749 ms	203896 KB	Output is correct
24	Correct	800 ms	203896 KB	Output is correct
25	Correct	797 ms	203896 KB	Output is correct
26	Correct	663 ms	203892 KB	Output is correct
27	Correct	798 ms	203892 KB	Output is correct
28	Correct	818 ms	203896 KB	Output is correct
29	Correct	799 ms	203896 KB	Output is correct
30	Correct	804 ms	203900 KB	Output is correct
31	Correct	808 ms	203900 KB	Output is correct
32	Correct	810 ms	203888 KB	Output is correct
33	Correct	816 ms	203888 KB	Output is correct
34	Correct	810 ms	203892 KB	Output is correct
35	Correct	776 ms	203896 KB	Output is correct
36	Correct	782 ms	203912 KB	Output is correct
37	Correct	779 ms	203896 KB	Output is correct
38	Correct	774 ms	203896 KB	Output is correct

Subtask #4
55.0 / 55.0

#	결과	실행 시간	메모리	Grader output
1	Correct	668 ms	203896 KB	Output is correct
2	Correct	703 ms	203896 KB	Output is correct
3	Correct	721 ms	204000 KB	Output is correct
4	Correct	696 ms	203896 KB	Output is correct
5	Correct	718 ms	204024 KB	Output is correct
6	Correct	737 ms	203996 KB	Output is correct
7	Correct	672 ms	203896 KB	Output is correct
8	Correct	675 ms	203868 KB	Output is correct
9	Correct	696 ms	203892 KB	Output is correct
10	Correct	664 ms	203896 KB	Output is correct
11	Correct	662 ms	204024 KB	Output is correct
12	Correct	738 ms	203924 KB	Output is correct
13	Correct	721 ms	204060 KB	Output is correct
14	Correct	788 ms	203896 KB	Output is correct
15	Correct	780 ms	203824 KB	Output is correct
16	Correct	796 ms	203900 KB	Output is correct
17	Correct	786 ms	203896 KB	Output is correct
18	Correct	781 ms	204024 KB	Output is correct
19	Correct	783 ms	203896 KB	Output is correct
20	Correct	793 ms	203896 KB	Output is correct
21	Correct	799 ms	203896 KB	Output is correct
22	Correct	780 ms	203984 KB	Output is correct
23	Correct	749 ms	203896 KB	Output is correct
24	Correct	800 ms	203896 KB	Output is correct
25	Correct	797 ms	203896 KB	Output is correct
26	Correct	663 ms	203892 KB	Output is correct
27	Correct	798 ms	203892 KB	Output is correct
28	Correct	818 ms	203896 KB	Output is correct
29	Correct	799 ms	203896 KB	Output is correct
30	Correct	804 ms	203900 KB	Output is correct
31	Correct	808 ms	203900 KB	Output is correct
32	Correct	810 ms	203888 KB	Output is correct
33	Correct	816 ms	203888 KB	Output is correct
34	Correct	810 ms	203892 KB	Output is correct
35	Correct	776 ms	203896 KB	Output is correct
36	Correct	782 ms	203912 KB	Output is correct
37	Correct	779 ms	203896 KB	Output is correct
38	Correct	774 ms	203896 KB	Output is correct
39	Correct	963 ms	209484 KB	Output is correct
40	Correct	1060 ms	213240 KB	Output is correct
41	Correct	917 ms	208376 KB	Output is correct
42	Correct	879 ms	207868 KB	Output is correct
43	Correct	861 ms	206712 KB	Output is correct
44	Correct	1032 ms	215672 KB	Output is correct
45	Correct	1014 ms	215824 KB	Output is correct
46	Correct	1014 ms	215644 KB	Output is correct
47	Correct	1105 ms	215624 KB	Output is correct
48	Correct	1004 ms	215660 KB	Output is correct
49	Correct	1137 ms	215572 KB	Output is correct
50	Correct	1185 ms	215712 KB	Output is correct
51	Correct	1233 ms	215540 KB	Output is correct
52	Correct	1135 ms	215796 KB	Output is correct
53	Correct	1224 ms	215716 KB	Output is correct
54	Correct	1238 ms	215672 KB	Output is correct
55	Correct	1242 ms	215624 KB	Output is correct
56	Correct	1161 ms	215672 KB	Output is correct
57	Correct	1149 ms	215604 KB	Output is correct
58	Correct	1188 ms	215736 KB	Output is correct
59	Correct	1208 ms	215532 KB	Output is correct
60	Correct	1285 ms	215556 KB	Output is correct
61	Correct	1406 ms	215528 KB	Output is correct
62	Correct	1394 ms	215732 KB	Output is correct

답안 #92672

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 16.0 / 16.0

Subtask #3 20.0 / 20.0

Subtask #4 55.0 / 55.0

Subtask #1
9.0 / 9.0

Subtask #2
16.0 / 16.0

Subtask #3
20.0 / 20.0

Subtask #4
55.0 / 55.0