oj.uz

Submission #43387

# Submission time Handle Problem Language Result Execution time Memory
43387 2018-03-15T09:43:33 Z funcsr Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 31936 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 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;
    if (i%2 == 0) {
      rep(j, n+1) {
        rep(k, n+1) {
          if (dp0[j][k] == 0) continue;
          for (int x=j; x<n; x++) if (x != k) add(dp1[x][k-(x<=k)], dp0[j][k]);
        }
      }
    }
    else {
      rep(j, n+1) {
        rep(k, n+1) {
          if (dp0[j][k] == 0) continue;
          for (int x=0; x<j; x++) if (x != k) add(dp1[x][k-(x<=k)], dp0[j][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 52 ms 31608 KB Output is correct
2 Correct 84 ms 31712 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31608 KB Output is correct
2 Correct 84 ms 31712 KB Output is correct
3 Correct 288 ms 31792 KB Output is correct
4 Correct 433 ms 31936 KB Output is correct
5 Correct 432 ms 31936 KB Output is correct
6 Correct 433 ms 31936 KB Output is correct
7 Correct 414 ms 31936 KB Output is correct
8 Correct 423 ms 31936 KB Output is correct
9 Correct 438 ms 31936 KB Output is correct
10 Correct 434 ms 31936 KB Output is correct
11 Correct 450 ms 31936 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31608 KB Output is correct
2 Correct 84 ms 31712 KB Output is correct
3 Correct 288 ms 31792 KB Output is correct
4 Correct 433 ms 31936 KB Output is correct
5 Correct 432 ms 31936 KB Output is correct
6 Correct 433 ms 31936 KB Output is correct
7 Correct 414 ms 31936 KB Output is correct
8 Correct 423 ms 31936 KB Output is correct
9 Correct 438 ms 31936 KB Output is correct
10 Correct 434 ms 31936 KB Output is correct
11 Correct 450 ms 31936 KB Output is correct
12 Execution timed out 2037 ms 31936 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 31608 KB Output is correct
2 Correct 84 ms 31712 KB Output is correct
3 Correct 288 ms 31792 KB Output is correct
4 Correct 433 ms 31936 KB Output is correct
5 Correct 432 ms 31936 KB Output is correct
6 Correct 433 ms 31936 KB Output is correct
7 Correct 414 ms 31936 KB Output is correct
8 Correct 423 ms 31936 KB Output is correct
9 Correct 438 ms 31936 KB Output is correct
10 Correct 434 ms 31936 KB Output is correct
11 Correct 450 ms 31936 KB Output is correct
12 Execution timed out 2037 ms 31936 KB Time limit exceeded
13 Halted 0 ms 0 KB -