oj.uz

Submission #43383

# Submission time Handle Problem Language Result Execution time Memory
43383 2018-03-15T09:28:38 Z funcsr Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 652 ms 64404 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[201][201][201];
int solve(int N, int CS, int CF) {
  rep(i, N+1) rep(j, N+1) rep(k, N+1) dp[i][j][k] = 0;
  //cout<<"CS="<<CS<<", CF="<<CF<<"\n";
  dp[0][CS][CF-(CS<CF)] = 1;
  int s = 0;
  rep(i, N) {
    int n = N-1-i;
    rep(j, N+1) {
      rep(k, N+1) {
        if (dp[i][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 (i == N-2 && x != k) continue;
            if(k-(x<=k)>=0) {
              add(dp[i+1][x][k-(x<=k)], dp[i][j][k]);
            }
            else if (i == N-2) add(s, dp[i][j][k]);
          }
        }
        else {
          for (int x=0; x<j; x++) {
            if (i < N-2 && x == k) continue;
            if (i == N-2 && x != k) continue;
            if (k-(x<=k)>=0) {
              add(dp[i+1][x][k-(x<=k)], dp[i][j][k]);
            }
            else if (i == N-2) add(s, dp[i][j][k]);
          }
        }
      }
    }
  }
  //rep(j, N+1) rep(k, N+1) add(s, dp[N-1][j][k]);
  /*
  if (N%2 == 1) {
    rep(j, N+1) if (j > 0) add(s, dp[N-2][j][0]);
  }
  else {
    rep(j, N+1) rep(k, N+1) if (k>0) add(s, dp[N-2][j][k]);
  }
  */
  //cout<<"s="<<s<<"\n";
  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 2 ms 376 KB Output is correct
2 Correct 2 ms 608 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 1064 KB Output is correct
4 Correct 3 ms 2000 KB Output is correct
5 Correct 3 ms 2000 KB Output is correct
6 Correct 4 ms 2016 KB Output is correct
7 Correct 3 ms 2016 KB Output is correct
8 Correct 3 ms 2016 KB Output is correct
9 Correct 4 ms 2128 KB Output is correct
10 Correct 3 ms 2140 KB Output is correct
11 Correct 3 ms 2140 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 1064 KB Output is correct
4 Correct 3 ms 2000 KB Output is correct
5 Correct 3 ms 2000 KB Output is correct
6 Correct 4 ms 2016 KB Output is correct
7 Correct 3 ms 2016 KB Output is correct
8 Correct 3 ms 2016 KB Output is correct
9 Correct 4 ms 2128 KB Output is correct
10 Correct 3 ms 2140 KB Output is correct
11 Correct 3 ms 2140 KB Output is correct
12 Correct 611 ms 32368 KB Output is correct
13 Correct 378 ms 32368 KB Output is correct
14 Correct 76 ms 32368 KB Output is correct
15 Correct 590 ms 32620 KB Output is correct
16 Correct 94 ms 32620 KB Output is correct
17 Correct 626 ms 32620 KB Output is correct
18 Correct 181 ms 32620 KB Output is correct
19 Correct 637 ms 32620 KB Output is correct
20 Correct 652 ms 32620 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 1064 KB Output is correct
4 Correct 3 ms 2000 KB Output is correct
5 Correct 3 ms 2000 KB Output is correct
6 Correct 4 ms 2016 KB Output is correct
7 Correct 3 ms 2016 KB Output is correct
8 Correct 3 ms 2016 KB Output is correct
9 Correct 4 ms 2128 KB Output is correct
10 Correct 3 ms 2140 KB Output is correct
11 Correct 3 ms 2140 KB Output is correct
12 Correct 611 ms 32368 KB Output is correct
13 Correct 378 ms 32368 KB Output is correct
14 Correct 76 ms 32368 KB Output is correct
15 Correct 590 ms 32620 KB Output is correct
16 Correct 94 ms 32620 KB Output is correct
17 Correct 626 ms 32620 KB Output is correct
18 Correct 181 ms 32620 KB Output is correct
19 Correct 637 ms 32620 KB Output is correct
20 Correct 652 ms 32620 KB Output is correct
21 Runtime error 96 ms 64404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -