oj.uz

Submission #605697

# Submission time Handle Problem Language Result Execution time Memory
605697 2022-07-25T23:17:31 Z ignaciocanta Kangaroo (CEOI16_kangaroo) C++14
100 / 100
 45 ms 31688 KB 
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
 
using tint = long long;
using ld = long double;
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)	
 
using pi = pair<int,int>;
using pl = pair<tint,tint>;
using vi = vector<int>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vvi = vector<vi>;
using vl = vector<tint>;
using vb = vector<bool>;
 
#define pb push_back
#define pf push_front
#define rsz resize
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sz(x) (int)(x).size()
#define ins insert
 
#define f first
#define s second
#define mp make_pair
 
#define DBG(x) cerr << #x << " = " << x << endl;
 
const int mod = 998244353; 
const int MOD = 1e9+7;
const int MX = 2005;
const tint INF = 1e18; 
const int inf = 2e9;
const ld PI = acos(ld(-1)); 
const ld eps = 1e-5;
 
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const int DX[8] = {1, -1, 0, 0, 1, 1, -1, -1};
const int DY[8] = {0, 0, 1, -1, 1, -1, -1, 1};
 
template<class T> void remDup(vector<T> &v){ 
    sort(all(v)); v.erase(unique(all(v)),end(v));
}
 
template<class T> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; 
} 
template<class T> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; 
}
 
bool valid(int x, int y, int n, int m){
    return (0<=x && x<n && 0<=y && y<m);
}
 
int cdiv(int a, int b) { return a/b+((a^b)>0&&a%b); } 
int fdiv(int a, int b) { return a/b-((a^b)<0&&a%b); } 
 
void NACHO(string name = ""){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(sz(name)){
        freopen((name+".in").c_str(), "r", stdin);
        freopen((name+".out").c_str(), "w", stdout);
    }
}

tint dp[MX][MX];

int main(){
	NACHO();
	int n, st, en; cin >> n >> st >> en;
	// usamos dp connected component.
	// sea dp(i, j) la cantidad de conjuntos ordenados de chunks que 
	// cumplen lo pedido usando los numeros 1...i
	// y tal que hay j chunks de numeros.
	// a su vez en cada chunk el primer salto es 
	// de un numero menor a un mayor y el ultimo de un mayor a un menor
	// para poder "pegar" chunks.
	// supongamos que tengo (132) (564) y quiero meter el 7
	// puedo crear una componente nueva (132) (564) (7)
	// o (7) (132) (564) o puedo mergear dos componentes
	// (132)(7)(564) -> (1327564)
	dp[1][1] = 1LL;
	FOR(i, 1, n+1){
		FOR(j, 1, n+1){
			if(i == en || i == st){
				// o lo agrego al de la primer componente o creo una nueva
				dp[i][j] = (dp[i][j] + dp[i-1][j] % MOD + dp[i-1][j-1] % MOD) % MOD;
			}else{
				// uso el i para mergear dos componentes
				dp[i][j] = (dp[i][j] + dp[i-1][j+1] * j % MOD) % MOD;
				// uso el i para crear una componente nueva
				// en principio tengo j lugares, pero si ya coloque al
				// st o al en tengo menos lugares
				int availablePlaces = j - (st < i) - (en < i);
				dp[i][j] = (dp[i][j] + dp[i-1][j-1] * availablePlaces % MOD) % MOD;
			}
		}
	}
	cout << dp[n][1] << "\n";
}

Compilation message

kangaroo.cpp: In function 'void NACHO(std::string)':
kangaroo.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen((name+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
kangaroo.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen((name+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 456 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct
14 Correct 1 ms 1364 KB Output is correct
15 Correct 2 ms 1364 KB Output is correct
16 Correct 1 ms 1352 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 1 ms 1236 KB Output is correct
19 Correct 1 ms 1356 KB Output is correct
20 Correct 1 ms 1364 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 1364 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct
14 Correct 1 ms 1364 KB Output is correct
15 Correct 2 ms 1364 KB Output is correct
16 Correct 1 ms 1352 KB Output is correct
17 Correct 1 ms 1364 KB Output is correct
18 Correct 1 ms 1236 KB Output is correct
19 Correct 1 ms 1356 KB Output is correct
20 Correct 1 ms 1364 KB Output is correct
21 Correct 6 ms 6356 KB Output is correct
22 Correct 7 ms 6868 KB Output is correct
23 Correct 7 ms 7764 KB Output is correct
24 Correct 45 ms 31672 KB Output is correct
25 Correct 42 ms 31584 KB Output is correct
26 Correct 41 ms 31688 KB Output is correct
27 Correct 42 ms 31548 KB Output is correct
28 Correct 27 ms 23720 KB Output is correct