답안 #41834 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41834	2018-02-21T11:19:01 Z	IvanC	Boat (APIO16_boat)	C++14	36 / 100	2000 ms	4776 KB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 501;
const ll MOD = 1e9 + 7;
ll dp[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--){
		memset(dp,0,sizeof(dp));
		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][1] = 1;
			for(ll j = i+1;j<=N;j++){
				for(ll u = v + 1;u<=M;u++){
					dp[i][1] += dp2[j][u];
				}
			}
			dp[i][1] %= MOD;
			dp[i][1] = (dp[i][1] * tam) % MOD;
			for(ll j = i + 1;j<=N;j++){
				for(ll k = 2;k<=vaiate;k++){
					dp[i][k] += dp[j][k-1];
				}
			}
			dp2[i][v] = dp[i][1];
			for(ll k = 2;k<=vaiate;k++){
				dp[i][k] %= MOD;
				dp[i][k] *= precalc[k];
				dp[i][k] %= MOD;
				dp2[i][v] += dp[i][k];
			}
			dp2[i][v] %= MOD;
			tot += dp2[i][v];
			tot %= MOD;
		}
	}
	cout << tot << endl;
	return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	4140 KB	Output is correct
2	Correct	235 ms	4320 KB	Output is correct
3	Correct	243 ms	4576 KB	Output is correct
4	Correct	234 ms	4576 KB	Output is correct
5	Correct	234 ms	4576 KB	Output is correct
6	Correct	243 ms	4576 KB	Output is correct
7	Correct	261 ms	4576 KB	Output is correct
8	Correct	254 ms	4576 KB	Output is correct
9	Correct	250 ms	4576 KB	Output is correct
10	Correct	248 ms	4744 KB	Output is correct
11	Correct	245 ms	4744 KB	Output is correct
12	Correct	253 ms	4744 KB	Output is correct
13	Correct	256 ms	4744 KB	Output is correct
14	Correct	246 ms	4744 KB	Output is correct
15	Correct	245 ms	4744 KB	Output is correct
16	Correct	50 ms	4744 KB	Output is correct
17	Correct	54 ms	4744 KB	Output is correct
18	Correct	50 ms	4764 KB	Output is correct
19	Correct	52 ms	4764 KB	Output is correct
20	Correct	50 ms	4776 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	4140 KB	Output is correct
2	Correct	235 ms	4320 KB	Output is correct
3	Correct	243 ms	4576 KB	Output is correct
4	Correct	234 ms	4576 KB	Output is correct
5	Correct	234 ms	4576 KB	Output is correct
6	Correct	243 ms	4576 KB	Output is correct
7	Correct	261 ms	4576 KB	Output is correct
8	Correct	254 ms	4576 KB	Output is correct
9	Correct	250 ms	4576 KB	Output is correct
10	Correct	248 ms	4744 KB	Output is correct
11	Correct	245 ms	4744 KB	Output is correct
12	Correct	253 ms	4744 KB	Output is correct
13	Correct	256 ms	4744 KB	Output is correct
14	Correct	246 ms	4744 KB	Output is correct
15	Correct	245 ms	4744 KB	Output is correct
16	Correct	50 ms	4744 KB	Output is correct
17	Correct	54 ms	4744 KB	Output is correct
18	Correct	50 ms	4764 KB	Output is correct
19	Correct	52 ms	4764 KB	Output is correct
20	Correct	50 ms	4776 KB	Output is correct
21	Execution timed out	2036 ms	4776 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	98 ms	4776 KB	Output is correct
2	Correct	74 ms	4776 KB	Output is correct
3	Correct	96 ms	4776 KB	Output is correct
4	Correct	89 ms	4776 KB	Output is correct
5	Correct	103 ms	4776 KB	Output is correct
6	Correct	133 ms	4776 KB	Output is correct
7	Correct	128 ms	4776 KB	Output is correct
8	Correct	129 ms	4776 KB	Output is correct
9	Correct	130 ms	4776 KB	Output is correct
10	Correct	119 ms	4776 KB	Output is correct
11	Correct	104 ms	4776 KB	Output is correct
12	Correct	99 ms	4776 KB	Output is correct
13	Correct	105 ms	4776 KB	Output is correct
14	Correct	99 ms	4776 KB	Output is correct
15	Correct	105 ms	4776 KB	Output is correct
16	Correct	48 ms	4776 KB	Output is correct
17	Correct	42 ms	4776 KB	Output is correct
18	Correct	43 ms	4776 KB	Output is correct
19	Correct	41 ms	4776 KB	Output is correct
20	Correct	41 ms	4776 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	238 ms	4140 KB	Output is correct
2	Correct	235 ms	4320 KB	Output is correct
3	Correct	243 ms	4576 KB	Output is correct
4	Correct	234 ms	4576 KB	Output is correct
5	Correct	234 ms	4576 KB	Output is correct
6	Correct	243 ms	4576 KB	Output is correct
7	Correct	261 ms	4576 KB	Output is correct
8	Correct	254 ms	4576 KB	Output is correct
9	Correct	250 ms	4576 KB	Output is correct
10	Correct	248 ms	4744 KB	Output is correct
11	Correct	245 ms	4744 KB	Output is correct
12	Correct	253 ms	4744 KB	Output is correct
13	Correct	256 ms	4744 KB	Output is correct
14	Correct	246 ms	4744 KB	Output is correct
15	Correct	245 ms	4744 KB	Output is correct
16	Correct	50 ms	4744 KB	Output is correct
17	Correct	54 ms	4744 KB	Output is correct
18	Correct	50 ms	4764 KB	Output is correct
19	Correct	52 ms	4764 KB	Output is correct
20	Correct	50 ms	4776 KB	Output is correct
21	Execution timed out	2036 ms	4776 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #41834

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0