oj.uz

Submission #783064

# Submission time Handle Problem Language Result Execution time Memory
783064 2023-07-14T14:46:05 Z minhcool Kangaroo (CEOI16_kangaroo) C++17
51 / 100
 2000 ms 111976 KB 
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e2 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, st, en, dp[N][N][N][2];

void add(int &a, int b){
    a = (a + b) % mod;
}

#ifdef local
void process(){
    cin >> n >> st >> en;
    dp[2][1][2][0] = dp[2][2][1][1] = 1;
    for(int num = 3; num <= n; num++){
        for(int st_ind = 1; st_ind <= num; st_ind++){
            for(int en_ind = 1; en_ind <= num; en_ind++){
                if(st_ind == en_ind) continue;
                for(int lst = 1; lst < en_ind; lst++){
                    if(lst == st_ind) continue;
                    // we are deleting en_ind
                    add(dp[num][st_ind][en_ind][0], dp[num - 1][st_ind - (st_ind > en_ind)][lst][1]);
                }
                for(int lst = en_ind + 1; lst <= num; lst++){
                    if(lst == st_ind) continue;
                    // we are deleting en_ind
                    add(dp[num][st_ind][en_ind][1], dp[num - 1][st_ind - (st_ind > en_ind)][lst - 1][0]);
                }
            }
        }
    }
    cout << (dp[n][st][en][0] + dp[n][st][en][1]) % mod;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    //freopen("abc.inp", "r", stdin);
    //freopen("abc.out", "w", stdout);
	process();
}
#endif

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 5 ms 4072 KB Output is correct
5 Correct 4 ms 3796 KB Output is correct
6 Correct 4 ms 3924 KB Output is correct
7 Correct 3 ms 3408 KB Output is correct
8 Correct 5 ms 3796 KB Output is correct
9 Correct 4 ms 3924 KB Output is correct
10 Correct 4 ms 3916 KB Output is correct
11 Correct 4 ms 3792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 5 ms 4072 KB Output is correct
5 Correct 4 ms 3796 KB Output is correct
6 Correct 4 ms 3924 KB Output is correct
7 Correct 3 ms 3408 KB Output is correct
8 Correct 5 ms 3796 KB Output is correct
9 Correct 4 ms 3924 KB Output is correct
10 Correct 4 ms 3916 KB Output is correct
11 Correct 4 ms 3792 KB Output is correct
12 Correct 1499 ms 95460 KB Output is correct
13 Correct 1167 ms 84288 KB Output is correct
14 Correct 1493 ms 95444 KB Output is correct
15 Correct 1522 ms 96496 KB Output is correct
16 Correct 1503 ms 95456 KB Output is correct
17 Correct 1530 ms 96556 KB Output is correct
18 Correct 972 ms 76484 KB Output is correct
19 Correct 1437 ms 93532 KB Output is correct
20 Correct 1524 ms 96420 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 5 ms 4072 KB Output is correct
5 Correct 4 ms 3796 KB Output is correct
6 Correct 4 ms 3924 KB Output is correct
7 Correct 3 ms 3408 KB Output is correct
8 Correct 5 ms 3796 KB Output is correct
9 Correct 4 ms 3924 KB Output is correct
10 Correct 4 ms 3916 KB Output is correct
11 Correct 4 ms 3792 KB Output is correct
12 Correct 1499 ms 95460 KB Output is correct
13 Correct 1167 ms 84288 KB Output is correct
14 Correct 1493 ms 95444 KB Output is correct
15 Correct 1522 ms 96496 KB Output is correct
16 Correct 1503 ms 95456 KB Output is correct
17 Correct 1530 ms 96556 KB Output is correct
18 Correct 972 ms 76484 KB Output is correct
19 Correct 1437 ms 93532 KB Output is correct
20 Correct 1524 ms 96420 KB Output is correct
21 Execution timed out 2066 ms 111976 KB Time limit exceeded
22 Halted 0 ms 0 KB -