| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 50010 |
2018-06-06T08:42:46 Z |
Costin Andrei Oncescu(#1280, SpaimaCarpatilor) |
Rope (JOI17_rope) |
C++11 |
|
3 ms |
964 KB |
#include<bits/stdc++.h>
using namespace std;
int N, M, a[109], ans[109], f[1000009], pf[1000009], sf[1000009];
const int K = 15;
bool dp[K + 1][(1 << K) + 2];
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
/*scanf ("%d %d", &N, &M);
for (int i=1; i<=N; i++)
{
int x;
scanf ("%d", &x);
f[x] ++;
}
pf[0] = 0, sf[M + 1] = 0;
for (int i=1; i<=M; i++)
pf[i] = max (pf[i - 1], f[i]);
for (int i=M; i>=1; i--)
sf[i] = max (sf[i + 1], f[i]);
for (int i=1; i<=M; i++)
printf ("%d\n", N - f[i] - max (pf[i - 1], sf[i + 1]));*/
dp[2][1] = dp[2][2] = dp[2][0] = dp[2][3] = 1;
for (int i=2; i<K; i++)
for (int msk = 0; msk < (1 << i); msk ++)
if (dp[i][msk])
{
for (int pf=1; pf<=i && pf + i <= K; pf++)
{
int aux = msk << pf;
for (int k=0; k<pf; k++)
if (msk & (1 << k))
aux |= 1 << (pf - 1 - k);
dp[i + pf][aux] = 1;
}
for (int sf=1; sf<=i && sf + i <= K; sf++)
{
int aux = msk;
for (int k=0; k<sf; k++)
if (msk & (1 << (i - 1 - k)))
aux |= 1 << (i + k);
dp[i + sf][aux] = 1;
}
}
/*for (int msk = 0; msk < (1 << K); msk ++)
if (dp[K][msk])
{
for (int i=0; i<K; i++)
if (msk & (1 << i)) printf ("1");
else printf ("0");
printf ("\n");
}*/
scanf ("%d %d", &N, &M);
for (int i=0; i<N; i++)
scanf ("%d", &a[i]);
for (int i=1; i<=M; i++)
ans[i] = N + 1;
for (int msk=0; msk<(1 << N); msk ++)
if (dp[N][msk])
{
int f[2][30];
memset (f, 0, sizeof (f));
for (int i=0; i<N; i++)
f[(msk >> i) & 1][a[i]] ++;
for (int i=1; i<=M; i++)
for (int j=1; j<=M; j++)
{
int curr = N - f[0][i] - f[1][j];
if (curr < ans[i]) ans[i] = curr;
if (curr < ans[j]) ans[j] = curr;
}
}
for (int i=1; i<=M; i++)
printf ("%d\n", ans[i]);
return 0;
}
Compilation message
rope.cpp: In function 'int main()':
rope.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &N, &M);
~~~~~~^~~~~~~~~~~~~~~~~
rope.cpp:61:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &a[i]);
~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
3 ms |
716 KB |
Output is correct |
| 6 |
Correct |
3 ms |
824 KB |
Output is correct |
| 7 |
Correct |
3 ms |
832 KB |
Output is correct |
| 8 |
Correct |
3 ms |
832 KB |
Output is correct |
| 9 |
Correct |
3 ms |
840 KB |
Output is correct |
| 10 |
Correct |
2 ms |
864 KB |
Output is correct |
| 11 |
Correct |
2 ms |
864 KB |
Output is correct |
| 12 |
Correct |
2 ms |
872 KB |
Output is correct |
| 13 |
Correct |
3 ms |
876 KB |
Output is correct |
| 14 |
Correct |
2 ms |
880 KB |
Output is correct |
| 15 |
Correct |
2 ms |
884 KB |
Output is correct |
| 16 |
Correct |
2 ms |
920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
924 KB |
Output is correct |
| 18 |
Correct |
2 ms |
928 KB |
Output is correct |
| 19 |
Correct |
3 ms |
932 KB |
Output is correct |
| 20 |
Correct |
2 ms |
936 KB |
Output is correct |
| 21 |
Correct |
3 ms |
936 KB |
Output is correct |
| 22 |
Correct |
2 ms |
944 KB |
Output is correct |
| 23 |
Correct |
3 ms |
948 KB |
Output is correct |
| 24 |
Correct |
2 ms |
948 KB |
Output is correct |
| 25 |
Correct |
2 ms |
948 KB |
Output is correct |
| 26 |
Correct |
3 ms |
960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
3 ms |
716 KB |
Output is correct |
| 6 |
Correct |
3 ms |
824 KB |
Output is correct |
| 7 |
Correct |
3 ms |
832 KB |
Output is correct |
| 8 |
Correct |
3 ms |
832 KB |
Output is correct |
| 9 |
Correct |
3 ms |
840 KB |
Output is correct |
| 10 |
Correct |
2 ms |
864 KB |
Output is correct |
| 11 |
Correct |
2 ms |
864 KB |
Output is correct |
| 12 |
Correct |
2 ms |
872 KB |
Output is correct |
| 13 |
Correct |
3 ms |
876 KB |
Output is correct |
| 14 |
Correct |
2 ms |
880 KB |
Output is correct |
| 15 |
Correct |
2 ms |
884 KB |
Output is correct |
| 16 |
Correct |
2 ms |
920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
924 KB |
Output is correct |
| 18 |
Correct |
2 ms |
928 KB |
Output is correct |
| 19 |
Correct |
3 ms |
932 KB |
Output is correct |
| 20 |
Correct |
2 ms |
936 KB |
Output is correct |
| 21 |
Correct |
3 ms |
936 KB |
Output is correct |
| 22 |
Correct |
2 ms |
944 KB |
Output is correct |
| 23 |
Correct |
3 ms |
948 KB |
Output is correct |
| 24 |
Correct |
2 ms |
948 KB |
Output is correct |
| 25 |
Correct |
2 ms |
948 KB |
Output is correct |
| 26 |
Correct |
3 ms |
960 KB |
Output is correct |
| 27 |
Incorrect |
2 ms |
964 KB |
Output isn't correct |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
3 ms |
716 KB |
Output is correct |
| 6 |
Correct |
3 ms |
824 KB |
Output is correct |
| 7 |
Correct |
3 ms |
832 KB |
Output is correct |
| 8 |
Correct |
3 ms |
832 KB |
Output is correct |
| 9 |
Correct |
3 ms |
840 KB |
Output is correct |
| 10 |
Correct |
2 ms |
864 KB |
Output is correct |
| 11 |
Correct |
2 ms |
864 KB |
Output is correct |
| 12 |
Correct |
2 ms |
872 KB |
Output is correct |
| 13 |
Correct |
3 ms |
876 KB |
Output is correct |
| 14 |
Correct |
2 ms |
880 KB |
Output is correct |
| 15 |
Correct |
2 ms |
884 KB |
Output is correct |
| 16 |
Correct |
2 ms |
920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
924 KB |
Output is correct |
| 18 |
Correct |
2 ms |
928 KB |
Output is correct |
| 19 |
Correct |
3 ms |
932 KB |
Output is correct |
| 20 |
Correct |
2 ms |
936 KB |
Output is correct |
| 21 |
Correct |
3 ms |
936 KB |
Output is correct |
| 22 |
Correct |
2 ms |
944 KB |
Output is correct |
| 23 |
Correct |
3 ms |
948 KB |
Output is correct |
| 24 |
Correct |
2 ms |
948 KB |
Output is correct |
| 25 |
Correct |
2 ms |
948 KB |
Output is correct |
| 26 |
Correct |
3 ms |
960 KB |
Output is correct |
| 27 |
Incorrect |
2 ms |
964 KB |
Output isn't correct |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
3 ms |
716 KB |
Output is correct |
| 6 |
Correct |
3 ms |
824 KB |
Output is correct |
| 7 |
Correct |
3 ms |
832 KB |
Output is correct |
| 8 |
Correct |
3 ms |
832 KB |
Output is correct |
| 9 |
Correct |
3 ms |
840 KB |
Output is correct |
| 10 |
Correct |
2 ms |
864 KB |
Output is correct |
| 11 |
Correct |
2 ms |
864 KB |
Output is correct |
| 12 |
Correct |
2 ms |
872 KB |
Output is correct |
| 13 |
Correct |
3 ms |
876 KB |
Output is correct |
| 14 |
Correct |
2 ms |
880 KB |
Output is correct |
| 15 |
Correct |
2 ms |
884 KB |
Output is correct |
| 16 |
Correct |
2 ms |
920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
924 KB |
Output is correct |
| 18 |
Correct |
2 ms |
928 KB |
Output is correct |
| 19 |
Correct |
3 ms |
932 KB |
Output is correct |
| 20 |
Correct |
2 ms |
936 KB |
Output is correct |
| 21 |
Correct |
3 ms |
936 KB |
Output is correct |
| 22 |
Correct |
2 ms |
944 KB |
Output is correct |
| 23 |
Correct |
3 ms |
948 KB |
Output is correct |
| 24 |
Correct |
2 ms |
948 KB |
Output is correct |
| 25 |
Correct |
2 ms |
948 KB |
Output is correct |
| 26 |
Correct |
3 ms |
960 KB |
Output is correct |
| 27 |
Incorrect |
2 ms |
964 KB |
Output isn't correct |
| 28 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
600 KB |
Output is correct |
| 4 |
Correct |
3 ms |
620 KB |
Output is correct |
| 5 |
Correct |
3 ms |
716 KB |
Output is correct |
| 6 |
Correct |
3 ms |
824 KB |
Output is correct |
| 7 |
Correct |
3 ms |
832 KB |
Output is correct |
| 8 |
Correct |
3 ms |
832 KB |
Output is correct |
| 9 |
Correct |
3 ms |
840 KB |
Output is correct |
| 10 |
Correct |
2 ms |
864 KB |
Output is correct |
| 11 |
Correct |
2 ms |
864 KB |
Output is correct |
| 12 |
Correct |
2 ms |
872 KB |
Output is correct |
| 13 |
Correct |
3 ms |
876 KB |
Output is correct |
| 14 |
Correct |
2 ms |
880 KB |
Output is correct |
| 15 |
Correct |
2 ms |
884 KB |
Output is correct |
| 16 |
Correct |
2 ms |
920 KB |
Output is correct |
| 17 |
Correct |
2 ms |
924 KB |
Output is correct |
| 18 |
Correct |
2 ms |
928 KB |
Output is correct |
| 19 |
Correct |
3 ms |
932 KB |
Output is correct |
| 20 |
Correct |
2 ms |
936 KB |
Output is correct |
| 21 |
Correct |
3 ms |
936 KB |
Output is correct |
| 22 |
Correct |
2 ms |
944 KB |
Output is correct |
| 23 |
Correct |
3 ms |
948 KB |
Output is correct |
| 24 |
Correct |
2 ms |
948 KB |
Output is correct |
| 25 |
Correct |
2 ms |
948 KB |
Output is correct |
| 26 |
Correct |
3 ms |
960 KB |
Output is correct |
| 27 |
Incorrect |
2 ms |
964 KB |
Output isn't correct |
| 28 |
Halted |
0 ms |
0 KB |
- |
