Submission #1201533


Source Code Expand

#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define _ << " _ " <<
#define TRACE(x) cerr << #x << " = " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug
//#define TRACE(x)

using namespace std;

typedef long long llint;

const int MAXN = 105;
const int MOD = 1e9 + 7;

inline int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }

int n, a[MAXN], dp[MAXN][MAXN][MAXN];

int f(int i, int idx, int tot) {
  if (i < 0) return 1;
  if (dp[i][idx][tot] != -1) return dp[i][idx][tot];

  int ret = 0;

  int add_first = (a[i-1] == a[i]) ? 0 : 1;
  int add_last = (a[2*n-1-i] == a[2*n-2-i]) ? 0 : 1;

  FOR(j, 1, tot + 1) {
    int rem = max(abs(j - idx) - 1, 0);
    int new_idx = (idx < j) ? idx + 1 : j;
    ret = add(ret, f(i-1, new_idx+add_first, tot-rem+add_first+add_last));
  }

  //TRACE(i _ idx _ tot _ ret);
  return dp[i][idx][tot] = ret;
}

int main(void) {
  memset(dp, -1, sizeof(dp));
  scanf("%d",&n);
  REP(i, 2*n-1) scanf("%d",&a[i]);
  sort(a, a + (2*n-1));

  printf("%d\n",f(n-1,1,1));
  
  return 0;
}

Submission Info

Submission Time
Task F - Prefix Median
User mislav
Language C++14 (GCC 5.4.1)
Score 2000
Code Size 1288 Byte
Status AC
Exec Time 22 ms
Memory 4736 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
                 ^
./Main.cpp:50:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i, 2*n-1) scanf("%d",&a[i]);
                                  ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 2000 / 2000
Status
AC × 3
AC × 54
Set Name Test Cases
Sample 00_example_01.txt, 00_example_02.txt, 00_example_03.txt
All 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt
Case Name Status Exec Time Memory
00_example_01.txt AC 3 ms 4736 KB
00_example_02.txt AC 3 ms 4736 KB
00_example_03.txt AC 3 ms 4736 KB
01.txt AC 22 ms 4736 KB
02.txt AC 17 ms 4736 KB
03.txt AC 5 ms 4736 KB
04.txt AC 4 ms 4736 KB
05.txt AC 3 ms 4736 KB
06.txt AC 9 ms 4736 KB
07.txt AC 22 ms 4736 KB
08.txt AC 3 ms 4736 KB
09.txt AC 22 ms 4736 KB
10.txt AC 3 ms 4736 KB
11.txt AC 3 ms 4736 KB
12.txt AC 3 ms 4736 KB
13.txt AC 7 ms 4736 KB
14.txt AC 12 ms 4736 KB
15.txt AC 3 ms 4736 KB
16.txt AC 8 ms 4736 KB
17.txt AC 3 ms 4736 KB
18.txt AC 3 ms 4736 KB
19.txt AC 3 ms 4736 KB
20.txt AC 3 ms 4736 KB
21.txt AC 3 ms 4736 KB
22.txt AC 3 ms 4736 KB
23.txt AC 3 ms 4736 KB
24.txt AC 3 ms 4736 KB
25.txt AC 3 ms 4736 KB
26.txt AC 4 ms 4736 KB
27.txt AC 3 ms 4736 KB
28.txt AC 8 ms 4736 KB
29.txt AC 3 ms 4736 KB
30.txt AC 3 ms 4736 KB
31.txt AC 3 ms 4736 KB
32.txt AC 3 ms 4736 KB
33.txt AC 3 ms 4736 KB
34.txt AC 3 ms 4736 KB
35.txt AC 5 ms 4736 KB
36.txt AC 3 ms 4736 KB
37.txt AC 7 ms 4736 KB
38.txt AC 3 ms 4736 KB
39.txt AC 3 ms 4736 KB
40.txt AC 3 ms 4736 KB
41.txt AC 5 ms 4736 KB
42.txt AC 9 ms 4736 KB
43.txt AC 3 ms 4736 KB
44.txt AC 10 ms 4736 KB
45.txt AC 3 ms 4736 KB
46.txt AC 3 ms 4736 KB
47.txt AC 3 ms 4736 KB
48.txt AC 4 ms 4736 KB
49.txt AC 6 ms 4736 KB
50.txt AC 3 ms 4736 KB
51.txt AC 3 ms 4736 KB