oj.uz

Submission #41833

# Submission time Handle Problem Language Result Execution time Memory
41833 2018-02-21T11:15:29 Z IvanC Boat (APIO16_boat) C++14
27 / 100
 121 ms 9232 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 101;
const ll MOD = 1e9 + 7;
ll dp[MAXN][2*MAXN][MAXN],dp2[MAXN][2*MAXN];
ll precalc[MAXN],A[MAXN],B[MAXN],N,M;
vector<ll> intervalos;
ll binary_expo(ll val,ll pot){
	if(pot == 0) return 1LL;
	if(pot % 2 == 0){
		ll davez = binary_expo(val,pot/2);
		return (davez*davez) % MOD;
	} 
	return (val*binary_expo(val,pot-1)) % MOD;
}
int main(){
	cin >> N;
	for(int i = 1;i<=N;i++){
		cin >> A[i] >> B[i];
		B[i]++;
		intervalos.push_back(A[i]);
		intervalos.push_back(B[i]); 
	}
	sort(intervalos.begin(),intervalos.end());
	intervalos.erase(unique(intervalos.begin(),intervalos.end()),intervalos.end());
	M = intervalos.size() - 2;
	ll tot = 0;
	for(int v = M;v>=0;v--){
		ll tam = intervalos[v+1] - intervalos[v];
		ll vaiate = min(tam,N);
		for(ll i = 2;i<=vaiate;i++){
			precalc[i] = (tam - i + 1)*binary_expo(i,MOD-2);
			precalc[i] %= MOD;
		}
		for(ll i = N;i>=1;i--){
			if(!(A[i] <= intervalos[v] && intervalos[v+1] <= B[i] )) continue;
			dp[i][v][1] = 1;
			for(ll j = i+1;j<=N;j++){
				for(ll u = v + 1;u<=M;u++){
					dp[i][v][1] += dp2[j][u];
				}
			}
			dp[i][v][1] %= MOD;
			dp[i][v][1] = (dp[i][v][1] * tam) % MOD;
			for(ll j = i + 1;j<=N;j++){
				for(ll k = 2;k<=vaiate;k++){
					dp[i][v][k] += dp[j][v][k-1];
				}
			}
			dp2[i][v] = dp[i][v][1];
			for(ll k = 2;k<=vaiate;k++){
				dp[i][v][k] %= MOD;
				dp[i][v][k] *= precalc[k];
				dp[i][v][k] %= MOD;
				dp2[i][v] += dp[i][v][k];
			}
			dp2[i][v] %= MOD;
			tot += dp2[i][v];
			tot %= MOD;
		}
	}
	cout << tot << endl;
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 6388 KB Output is correct
2 Correct 68 ms 6388 KB Output is correct
3 Correct 71 ms 6388 KB Output is correct
4 Correct 70 ms 6456 KB Output is correct
5 Correct 80 ms 6944 KB Output is correct
6 Correct 101 ms 9132 KB Output is correct
7 Correct 106 ms 9204 KB Output is correct
8 Correct 108 ms 9208 KB Output is correct
9 Correct 121 ms 9232 KB Output is correct
10 Correct 106 ms 9232 KB Output is correct
11 Correct 86 ms 9232 KB Output is correct
12 Correct 78 ms 9232 KB Output is correct
13 Correct 84 ms 9232 KB Output is correct
14 Correct 86 ms 9232 KB Output is correct
15 Correct 89 ms 9232 KB Output is correct
16 Correct 35 ms 9232 KB Output is correct
17 Correct 29 ms 9232 KB Output is correct
18 Correct 31 ms 9232 KB Output is correct
19 Correct 30 ms 9232 KB Output is correct
20 Correct 32 ms 9232 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -