oj.uz

답안 #981840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
981840 2024-05-13T15:39:09 Z Requiem 캥거루 (CEOI16_kangaroo) C++17
100 / 100
 29 ms 32204 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "kangaroo"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 2009;
int dp[MAXN][MAXN],in=0,n,s,t;
int solve(int pos,int component,int in){
//    cout<<pos<<' '<<component<<endl;
    if (pos==n+1){
        if (component==1) return 1;
        else return 0;
    }
    int &res = dp[pos][component];

    if (res != -1) return res;
    res = 0;
    if (pos==s){

        if (component>0 && (in==0 || (in>0 && (component>1 || pos==n)))) res =(res + solve(pos+1,component,in+1))%MOD;
        res = (res + solve(pos+1,component+1,in+1))%MOD;
    }
    else if (pos == t) {
        if (component>0 && (in==0 || (in>0 && (component>1 || pos==n)))) res =(res + solve(pos+1,component,in+1))%MOD;
        res =(res + solve(pos+1,component+1,in+1))%MOD;
    }
    else{
        int mulfactor = component+1 - in;
        res = (res + solve(pos+1,component+1,in) * mulfactor)%MOD; // tao 1 tplt moi
        if (component>1){ //noi 2 tplt
            res = (res + solve(pos+1,component-1,in) * (component-1))%MOD;
        }
    }
    return res;
}
main()
{
    fast;
 //   freopen(TASKNAME".inp","r",stdin);
  //  freopen(TASKNAME".out","w",stdout);
    cin>>n>>s>>t;
    memset(dp,-1,sizeof(dp));
    int ans = solve(1,0,0);
    cout<<ans<<endl;
}

Compilation message

kangaroo.cpp:51:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main()
      | ^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 31836 KB Output is correct
2 Correct 5 ms 31836 KB Output is correct
3 Correct 5 ms 31836 KB Output is correct
4 Correct 4 ms 31836 KB Output is correct
5 Correct 5 ms 31836 KB Output is correct
6 Correct 5 ms 31832 KB Output is correct
7 Correct 4 ms 31836 KB Output is correct
8 Correct 4 ms 31928 KB Output is correct
9 Correct 5 ms 31836 KB Output is correct
10 Correct 5 ms 31896 KB Output is correct
11 Correct 5 ms 31832 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 31836 KB Output is correct
2 Correct 5 ms 31836 KB Output is correct
3 Correct 5 ms 31836 KB Output is correct
4 Correct 4 ms 31836 KB Output is correct
5 Correct 5 ms 31836 KB Output is correct
6 Correct 5 ms 31832 KB Output is correct
7 Correct 4 ms 31836 KB Output is correct
8 Correct 4 ms 31928 KB Output is correct
9 Correct 5 ms 31836 KB Output is correct
10 Correct 5 ms 31896 KB Output is correct
11 Correct 5 ms 31832 KB Output is correct
12 Correct 5 ms 31836 KB Output is correct
13 Correct 5 ms 31928 KB Output is correct
14 Correct 5 ms 31836 KB Output is correct
15 Correct 5 ms 31904 KB Output is correct
16 Correct 5 ms 31836 KB Output is correct
17 Correct 5 ms 31920 KB Output is correct
18 Correct 5 ms 31836 KB Output is correct
19 Correct 5 ms 31920 KB Output is correct
20 Correct 5 ms 31836 KB Output is correct

Subtask #4
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 31836 KB Output is correct
2 Correct 5 ms 31836 KB Output is correct
3 Correct 5 ms 31836 KB Output is correct
4 Correct 4 ms 31836 KB Output is correct
5 Correct 5 ms 31836 KB Output is correct
6 Correct 5 ms 31832 KB Output is correct
7 Correct 4 ms 31836 KB Output is correct
8 Correct 4 ms 31928 KB Output is correct
9 Correct 5 ms 31836 KB Output is correct
10 Correct 5 ms 31896 KB Output is correct
11 Correct 5 ms 31832 KB Output is correct
12 Correct 5 ms 31836 KB Output is correct
13 Correct 5 ms 31928 KB Output is correct
14 Correct 5 ms 31836 KB Output is correct
15 Correct 5 ms 31904 KB Output is correct
16 Correct 5 ms 31836 KB Output is correct
17 Correct 5 ms 31920 KB Output is correct
18 Correct 5 ms 31836 KB Output is correct
19 Correct 5 ms 31920 KB Output is correct
20 Correct 5 ms 31836 KB Output is correct
21 Correct 8 ms 32092 KB Output is correct
22 Correct 8 ms 32100 KB Output is correct
23 Correct 8 ms 32092 KB Output is correct
24 Correct 29 ms 32180 KB Output is correct
25 Correct 26 ms 32092 KB Output is correct
26 Correct 27 ms 32092 KB Output is correct
27 Correct 29 ms 32204 KB Output is correct
28 Correct 17 ms 32160 KB Output is correct