oj.uz

Submission #43388

# Submission time Handle Problem Language Result Execution time Memory
43388 2018-03-15T09:54:40 Z funcsr Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 32860 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 dp0[2001][2001];
int T[2001][2001];
int dp1[2001][2001];
int solve(int N, int CS, int CF) {
  rep(j, N+1) rep(k, N+1) dp0[j][k] = 0;
  dp0[CS][CF-(CS<CF)] = 1;
  rep(i, N-2) {
    int n = N-1-i;
    rep(j, n+1) rep(k, n+1) dp1[j][k] = 0;
    rep(j, n+1) rep(k, n+1) T[j][k] = dp0[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;
          //rep(j, x+1) add(dp1[x][k-(x<=k)], dp0[j][k]);
          add(dp1[x][k-(x<=k)], T[x][k]);
        }
      }
    }
    else {
      rep(k, n+1) {
        rep(x, n+1) {
          if (x == k) continue;
          //for (int j=x+1; j<=n; j++) add(dp1[x][k-(x<=k)], dp0[j][k]);
          add(dp1[x][k-(x<=k)], T[n][k]);
          add(dp1[x][k-(x<=k)], MOD-T[x][k]);
        }
      }
    }
    swap(dp0, dp1);
  }
  int s = 0;
  rep(j, 2) {
    rep(k, 2) {
      if ((N-2)%2 == 0) {
        if (j == 0 && k == 0) add(s, dp0[j][k]);
      }
      else {
        if (k <= j-1) add(s, dp0[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 51 ms 31736 KB Output is correct
2 Correct 82 ms 31736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31736 KB Output is correct
2 Correct 82 ms 31736 KB Output is correct
3 Correct 288 ms 31868 KB Output is correct
4 Correct 429 ms 31988 KB Output is correct
5 Correct 426 ms 32092 KB Output is correct
6 Correct 421 ms 32092 KB Output is correct
7 Correct 403 ms 32164 KB Output is correct
8 Correct 420 ms 32164 KB Output is correct
9 Correct 451 ms 32164 KB Output is correct
10 Correct 455 ms 32220 KB Output is correct
11 Correct 430 ms 32220 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31736 KB Output is correct
2 Correct 82 ms 31736 KB Output is correct
3 Correct 288 ms 31868 KB Output is correct
4 Correct 429 ms 31988 KB Output is correct
5 Correct 426 ms 32092 KB Output is correct
6 Correct 421 ms 32092 KB Output is correct
7 Correct 403 ms 32164 KB Output is correct
8 Correct 420 ms 32164 KB Output is correct
9 Correct 451 ms 32164 KB Output is correct
10 Correct 455 ms 32220 KB Output is correct
11 Correct 430 ms 32220 KB Output is correct
12 Execution timed out 2039 ms 32860 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 31736 KB Output is correct
2 Correct 82 ms 31736 KB Output is correct
3 Correct 288 ms 31868 KB Output is correct
4 Correct 429 ms 31988 KB Output is correct
5 Correct 426 ms 32092 KB Output is correct
6 Correct 421 ms 32092 KB Output is correct
7 Correct 403 ms 32164 KB Output is correct
8 Correct 420 ms 32164 KB Output is correct
9 Correct 451 ms 32164 KB Output is correct
10 Correct 455 ms 32220 KB Output is correct
11 Correct 430 ms 32220 KB Output is correct
12 Execution timed out 2039 ms 32860 KB Time limit exceeded
13 Halted 0 ms 0 KB -