Submission #500619

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
500619	2021-12-31 15:18:10	rainboy	Tortoise (CEOI21_tortoise)	C11	8 / 100	403 ms	332900 KiB

tortoise

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <string.h>
#define N 20
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int main() {
  static int aa[N], dp[1 << N][N][2], dq[1 << N][N][2];
  int n, i, b, t, s, s_, ans;
  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &aa[i]);
  for (b = 0; b < 1 << n; b++)
    for (i = 0; i < n; i++)
      dp[b][i][0] = dp[b][i][1] = INF;
  dp[0][0][0] = 0;
  for (t = 0; t <= (n - 1) * 2; t++) {
    s = 1 << (t + 1) / 2, s_ = 1 << (t + 2) / 2;
    for (b = 0; b < 1 << n; b += s)
      for (i = 0; i < n; i++)
        dq[b][i][0] = dq[b][i][1] = INF;
    for (b = 0; b < 1 << n; b += s)
      for (i = 0; i < n; i++) {
        if ((b & 1 << i) == 0 && aa[i] == 1)
          dp[b | 1 << i][i][1] = min(dp[b | 1 << i][i][1], dp[b][i][0]);
        if (aa[i] == -1)
          dp[b][i][0] = min(dp[b][i][0], dp[b][i][1]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

tortoise.c: In function 'main':
tortoise.c:13:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
tortoise.c:15:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27