답안 #205640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205640	2020-02-29T11:12:27 Z	Kastanda	Rope (JOI17_rope)	C++11	0 / 100	7 ms	1916 KB

rope

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, m, Mxc, A[N], C[N], dp[N][2][2];
inline void smin(int &a, int b) {a = min(a, b);}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &A[i]), C[A[i]] ++;
    for (int i = 1; i <= m; i ++)
        if (C[i] > C[Mxc])
            Mxc = i;
    for (int c = 1; c <= m; c ++)
    {
        int Mn = 0;
        for (int i = 1; i <= n; i ++)
            if (A[i] != c) Mn ++;
        for (int d = 1; d <= m; d ++)
            if (d != c)
            {
                if (c != Mxc && d != Mxc)
                    continue;
                int cls[2] = {c, d}, cnt[2] = {0, 0};
                memset(dp, 63, sizeof(dp));
                for (int i = 1; i <= n; i ++)
                {
                    cnt[0] += (A[i] != cls[0]);
                    cnt[1] += (A[i] != cls[1]);
                    dp[i][0][0] = dp[i][0][1] = cnt[0];
                    dp[i][1][0] = dp[i][1][1] = cnt[1];
                }
                for (int i = 1; i < n; i ++)
                    for (int w = 0; w <= 1; w ++)
                        for (int p = 0; p <= 1; p ++)
                        {
                            smin(dp[i + 1][w][!p], dp[i][w][p] + (A[i + 1] != cls[w]));
                            if (!p) smin(dp[i + 1][!w][1], dp[i][w][p] + (A[i + 1] != cls[!w]));
                        }
                for (int w = 0; w <= 1; w ++)
                    for (int p = 0; p <= 1; p ++)
                        Mn = min(Mn, dp[n][w][p]);
            }
        printf("%d\n", Mn);
    }
    return 0;
}

Compilation message

rope.cpp: In function 'int main()':
rope.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
rope.cpp:11:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]), C[A[i]] ++;
         ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1912 KB	Output is correct
2	Correct	6 ms	1912 KB	Output is correct
3	Correct	7 ms	1912 KB	Output is correct
4	Correct	6 ms	1912 KB	Output is correct
5	Correct	6 ms	1912 KB	Output is correct
6	Correct	7 ms	1916 KB	Output is correct
7	Correct	6 ms	1912 KB	Output is correct
8	Correct	6 ms	1912 KB	Output is correct
9	Correct	6 ms	1912 KB	Output is correct
10	Correct	6 ms	1912 KB	Output is correct
11	Correct	6 ms	1912 KB	Output is correct
12	Correct	6 ms	1912 KB	Output is correct
13	Correct	6 ms	1912 KB	Output is correct
14	Correct	6 ms	1912 KB	Output is correct
15	Correct	6 ms	1912 KB	Output is correct
16	Correct	6 ms	1912 KB	Output is correct
17	Correct	6 ms	1912 KB	Output is correct
18	Correct	6 ms	1912 KB	Output is correct
19	Incorrect	7 ms	1912 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1912 KB	Output is correct
2	Correct	6 ms	1912 KB	Output is correct
3	Correct	7 ms	1912 KB	Output is correct
4	Correct	6 ms	1912 KB	Output is correct
5	Correct	6 ms	1912 KB	Output is correct
6	Correct	7 ms	1916 KB	Output is correct
7	Correct	6 ms	1912 KB	Output is correct
8	Correct	6 ms	1912 KB	Output is correct
9	Correct	6 ms	1912 KB	Output is correct
10	Correct	6 ms	1912 KB	Output is correct
11	Correct	6 ms	1912 KB	Output is correct
12	Correct	6 ms	1912 KB	Output is correct
13	Correct	6 ms	1912 KB	Output is correct
14	Correct	6 ms	1912 KB	Output is correct
15	Correct	6 ms	1912 KB	Output is correct
16	Correct	6 ms	1912 KB	Output is correct
17	Correct	6 ms	1912 KB	Output is correct
18	Correct	6 ms	1912 KB	Output is correct
19	Incorrect	7 ms	1912 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1912 KB	Output is correct
2	Correct	6 ms	1912 KB	Output is correct
3	Correct	7 ms	1912 KB	Output is correct
4	Correct	6 ms	1912 KB	Output is correct
5	Correct	6 ms	1912 KB	Output is correct
6	Correct	7 ms	1916 KB	Output is correct
7	Correct	6 ms	1912 KB	Output is correct
8	Correct	6 ms	1912 KB	Output is correct
9	Correct	6 ms	1912 KB	Output is correct
10	Correct	6 ms	1912 KB	Output is correct
11	Correct	6 ms	1912 KB	Output is correct
12	Correct	6 ms	1912 KB	Output is correct
13	Correct	6 ms	1912 KB	Output is correct
14	Correct	6 ms	1912 KB	Output is correct
15	Correct	6 ms	1912 KB	Output is correct
16	Correct	6 ms	1912 KB	Output is correct
17	Correct	6 ms	1912 KB	Output is correct
18	Correct	6 ms	1912 KB	Output is correct
19	Incorrect	7 ms	1912 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1912 KB	Output is correct
2	Correct	6 ms	1912 KB	Output is correct
3	Correct	7 ms	1912 KB	Output is correct
4	Correct	6 ms	1912 KB	Output is correct
5	Correct	6 ms	1912 KB	Output is correct
6	Correct	7 ms	1916 KB	Output is correct
7	Correct	6 ms	1912 KB	Output is correct
8	Correct	6 ms	1912 KB	Output is correct
9	Correct	6 ms	1912 KB	Output is correct
10	Correct	6 ms	1912 KB	Output is correct
11	Correct	6 ms	1912 KB	Output is correct
12	Correct	6 ms	1912 KB	Output is correct
13	Correct	6 ms	1912 KB	Output is correct
14	Correct	6 ms	1912 KB	Output is correct
15	Correct	6 ms	1912 KB	Output is correct
16	Correct	6 ms	1912 KB	Output is correct
17	Correct	6 ms	1912 KB	Output is correct
18	Correct	6 ms	1912 KB	Output is correct
19	Incorrect	7 ms	1912 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	1912 KB	Output is correct
2	Correct	6 ms	1912 KB	Output is correct
3	Correct	7 ms	1912 KB	Output is correct
4	Correct	6 ms	1912 KB	Output is correct
5	Correct	6 ms	1912 KB	Output is correct
6	Correct	7 ms	1916 KB	Output is correct
7	Correct	6 ms	1912 KB	Output is correct
8	Correct	6 ms	1912 KB	Output is correct
9	Correct	6 ms	1912 KB	Output is correct
10	Correct	6 ms	1912 KB	Output is correct
11	Correct	6 ms	1912 KB	Output is correct
12	Correct	6 ms	1912 KB	Output is correct
13	Correct	6 ms	1912 KB	Output is correct
14	Correct	6 ms	1912 KB	Output is correct
15	Correct	6 ms	1912 KB	Output is correct
16	Correct	6 ms	1912 KB	Output is correct
17	Correct	6 ms	1912 KB	Output is correct
18	Correct	6 ms	1912 KB	Output is correct
19	Incorrect	7 ms	1912 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

답안 #205640

Compilation message

Subtask #1 0 / 15.0

Subtask #2 0 / 30.0

Subtask #3 0 / 10.0

Subtask #4 0 / 25.0

Subtask #5 0 / 20.0

Subtask #1
0 / 15.0

Subtask #2
0 / 30.0

Subtask #3
0 / 10.0

Subtask #4
0 / 25.0

Subtask #5
0 / 20.0