oj.uz

Submission #43384

# Submission time Handle Problem Language Result Execution time Memory
43384 2018-03-15T09:36:28 Z funcsr Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 32072 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 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) {
    rep(j, N+1) rep(k, N+1) dp[1][j][k] = 0;
    int n = N-1-i;
    rep(j, N+1) {
      rep(k, N+1) {
        if (dp[0][j][k] == 0) continue;
        //cout<<"dp["<<i<<"]["<<j<<"]["<<k<<"]="<<dp[i][j][k]<<"\n";
        if (i%2 == 0) {
          for (int x=j; x<n; x++) {
            if (i < N-2 && x == k) continue;
            if(k-(x<=k)>=0) {
              add(dp[1][x][k-(x<=k)], dp[0][j][k]);
            }
          }
        }
        else {
          for (int x=0; x<j; x++) {
            if (i < N-2 && x == k) continue;
            if (k-(x<=k)>=0) {
              add(dp[1][x][k-(x<=k)], dp[0][j][k]);
            }
          }
        }
      }
    }
    swap(dp[0], dp[1]);
  }
  int s = 0;
  rep(j, N+1) {
    rep(k, N+1) {
      if ((N-2)%2 == 0) {
        if (j == 0 && k == 0) add(s, dp[0][j][k]);
      }
      else {
        if (k <= j-1) add(s, dp[0][j][k]);
      }
    }
  }
  return s;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int N, CS, CF;
  cin >> N >> CS >> CF;
  /*
  if (N == 2) {
    cout << 1 << "\n";
    return 0;
  }
  */
  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 86 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 86 ms 31712 KB Output is correct
3 Correct 294 ms 31912 KB Output is correct
4 Correct 442 ms 31912 KB Output is correct
5 Correct 466 ms 31924 KB Output is correct
6 Correct 433 ms 31924 KB Output is correct
7 Correct 418 ms 31940 KB Output is correct
8 Correct 439 ms 31940 KB Output is correct
9 Correct 451 ms 31944 KB Output is correct
10 Correct 437 ms 32072 KB Output is correct
11 Correct 426 ms 32072 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 86 ms 31712 KB Output is correct
3 Correct 294 ms 31912 KB Output is correct
4 Correct 442 ms 31912 KB Output is correct
5 Correct 466 ms 31924 KB Output is correct
6 Correct 433 ms 31924 KB Output is correct
7 Correct 418 ms 31940 KB Output is correct
8 Correct 439 ms 31940 KB Output is correct
9 Correct 451 ms 31944 KB Output is correct
10 Correct 437 ms 32072 KB Output is correct
11 Correct 426 ms 32072 KB Output is correct
12 Execution timed out 2029 ms 32072 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 86 ms 31712 KB Output is correct
3 Correct 294 ms 31912 KB Output is correct
4 Correct 442 ms 31912 KB Output is correct
5 Correct 466 ms 31924 KB Output is correct
6 Correct 433 ms 31924 KB Output is correct
7 Correct 418 ms 31940 KB Output is correct
8 Correct 439 ms 31940 KB Output is correct
9 Correct 451 ms 31944 KB Output is correct
10 Correct 437 ms 32072 KB Output is correct
11 Correct 426 ms 32072 KB Output is correct
12 Execution timed out 2029 ms 32072 KB Time limit exceeded
13 Halted 0 ms 0 KB -