oj.uz

Submission #43389

# Submission time Handle Problem Language Result Execution time Memory
43389 2018-03-15T09:58:14 Z funcsr Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 2000 ms 13532 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
inline void add(int &x, int v) { x += v; if (x >= MOD) x -= MOD; }

int dp[2][2001][2001];
int T[2001][2001];
int solve(int N, int CS, int CF) {
  rep(j, N+1) rep(k, N+1) dp[0][j][k] = 0;
  dp[0][CS][CF-(CS<CF)] = 1;
  rep(i, N-2) {
    int n = N-1-i;
    rep(j, n+1) rep(k, n+1) dp[(i+1)%2][j][k] = 0;
    rep(j, n+1) rep(k, n+1) T[j][k] = dp[i%2][j][k];
    rep(j, n) rep(k, n+1) add(T[j+1][k], T[j][k]);
    if (i%2 == 0) {
      rep(k, n+1) {
        rep(x, n) {
          if (x == k) continue;
          add(dp[(i+1)%2][x][k-(x<=k)], T[x][k]);
        }
      }
    }
    else {
      rep(k, n+1) {
        rep(x, n+1) {
          if (x == k) continue;
          add(dp[(i+1)%2][x][k-(x<=k)], T[n][k]);
          add(dp[(i+1)%2][x][k-(x<=k)], MOD-T[x][k]);
        }
      }
    }
  }
  int s = 0;
  rep(j, 2) {
    rep(k, 2) {
      if ((N-2)%2 == 0) {
        if (j == 0 && k == 0) add(s, dp[(N-2)%2][j][k]);
      }
      else {
        if (k <= j-1) add(s, dp[(N-2)%2][j][k]);
      }
    }
  }
  return s;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int N, CS, CF;
  cin >> N >> CS >> CF;
  CS--, CF--;
  int s = solve(N, CS, CF);
  CS = N-1-CS, CF = N-1-CF;
  add(s, solve(N, CS, CF));
  cout << s << "\n";
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 480 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 480 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 1008 KB Output is correct
5 Correct 2 ms 1008 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 2 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 2 ms 1024 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 2 ms 1024 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 480 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 1008 KB Output is correct
5 Correct 2 ms 1008 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 2 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 2 ms 1024 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 2 ms 1024 KB Output is correct
12 Correct 62 ms 3364 KB Output is correct
13 Correct 52 ms 3364 KB Output is correct
14 Correct 51 ms 3364 KB Output is correct
15 Correct 67 ms 3492 KB Output is correct
16 Correct 52 ms 3492 KB Output is correct
17 Correct 66 ms 3492 KB Output is correct
18 Correct 40 ms 3492 KB Output is correct
19 Correct 63 ms 3492 KB Output is correct
20 Correct 66 ms 3492 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 480 KB Output is correct
3 Correct 2 ms 808 KB Output is correct
4 Correct 3 ms 1008 KB Output is correct
5 Correct 2 ms 1008 KB Output is correct
6 Correct 2 ms 1024 KB Output is correct
7 Correct 2 ms 1024 KB Output is correct
8 Correct 3 ms 1024 KB Output is correct
9 Correct 2 ms 1024 KB Output is correct
10 Correct 2 ms 1024 KB Output is correct
11 Correct 2 ms 1024 KB Output is correct
12 Correct 62 ms 3364 KB Output is correct
13 Correct 52 ms 3364 KB Output is correct
14 Correct 51 ms 3364 KB Output is correct
15 Correct 67 ms 3492 KB Output is correct
16 Correct 52 ms 3492 KB Output is correct
17 Correct 66 ms 3492 KB Output is correct
18 Correct 40 ms 3492 KB Output is correct
19 Correct 63 ms 3492 KB Output is correct
20 Correct 66 ms 3492 KB Output is correct
21 Execution timed out 2031 ms 13532 KB Time limit exceeded
22 Halted 0 ms 0 KB -