oj.uz

답안 #57233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57233 2018-07-14T09:57:20 Z ruhanhabib39 캥거루 (CEOI16_kangaroo) C++17
36 / 100
 2000 ms 504464 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long Long;
 
const Long MOD = 1000000007;
 
int N, cs, cf;
map<int,Long> dp[2][2000 + 10][2000 + 10];
 
Long f(int di, int l, int r, int lp) {
   if(l < 0 || r < 0 || l >= N || r >= N) return 0;
   if(dp[di][l][r].count(lp)) return dp[di][l][r][lp];
   if(l+r == 1) {
      return dp[di][l][r][lp] = (di && r) || (!di && l);
   }
   Long rs = 0;
   if(di) {
      rs = f(1,l+1,r-1,lp);
      if(l+1 != lp) rs += f(0, l, r-1, lp < l+1 ? lp : lp - 1);
   } else {
      rs = f(0,l-1,r+1,lp);
      if(l != lp) rs += f(1, l-1, r, lp < l ? lp : lp - 1);
   }
   rs %= MOD;
   return dp[di][l][r][lp] = rs;
}
 
int main() {
   //freopen("kangaroo.in", "r", stdin);
   //freopen("kangaroo.out", "w", stdout);
   scanf("%d%d%d", &N, &cs, &cf);
   if(cs > cf) swap(cs, cf);
   printf("%lld\n", (f(0,cs-1,N-cs,cf-1) + f(1,cs-1,N-cs,cf-1)) % MOD);
}

Compilation message

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:32:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &N, &cs, &cf);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 452 ms 379952 KB Output is correct
2 Correct 400 ms 379952 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 452 ms 379952 KB Output is correct
2 Correct 400 ms 379952 KB Output is correct
3 Correct 355 ms 380092 KB Output is correct
4 Correct 351 ms 380744 KB Output is correct
5 Correct 344 ms 380744 KB Output is correct
6 Correct 325 ms 381160 KB Output is correct
7 Correct 339 ms 381160 KB Output is correct
8 Correct 324 ms 381160 KB Output is correct
9 Correct 332 ms 381240 KB Output is correct
10 Correct 377 ms 381240 KB Output is correct
11 Correct 368 ms 381240 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 452 ms 379952 KB Output is correct
2 Correct 400 ms 379952 KB Output is correct
3 Correct 355 ms 380092 KB Output is correct
4 Correct 351 ms 380744 KB Output is correct
5 Correct 344 ms 380744 KB Output is correct
6 Correct 325 ms 381160 KB Output is correct
7 Correct 339 ms 381160 KB Output is correct
8 Correct 324 ms 381160 KB Output is correct
9 Correct 332 ms 381240 KB Output is correct
10 Correct 377 ms 381240 KB Output is correct
11 Correct 368 ms 381240 KB Output is correct
12 Execution timed out 2056 ms 504464 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 452 ms 379952 KB Output is correct
2 Correct 400 ms 379952 KB Output is correct
3 Correct 355 ms 380092 KB Output is correct
4 Correct 351 ms 380744 KB Output is correct
5 Correct 344 ms 380744 KB Output is correct
6 Correct 325 ms 381160 KB Output is correct
7 Correct 339 ms 381160 KB Output is correct
8 Correct 324 ms 381160 KB Output is correct
9 Correct 332 ms 381240 KB Output is correct
10 Correct 377 ms 381240 KB Output is correct
11 Correct 368 ms 381240 KB Output is correct
12 Execution timed out 2056 ms 504464 KB Time limit exceeded
13 Halted 0 ms 0 KB -