| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 205640 | 2020-02-29T11:12:27 Z | Kastanda | Rope (JOI17_rope) | C++11 | 7 ms | 1916 KB |
// 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
| # | Verdict | Execution time | Memory | 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 | - |
| # | Verdict | Execution time | Memory | 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 | - |
| # | Verdict | Execution time | Memory | 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 | - |
| # | Verdict | Execution time | Memory | 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 | - |
| # | Verdict | Execution time | Memory | 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 | - |