oj.uz

Submission #637733

# Submission time Handle Problem Language Result Execution time Memory
637733 2022-09-02T21:16:23 Z lovrot Boat (APIO16_boat) C++11
36 / 100
 1427 ms 25388 KB 
#include <bits/stdc++.h> 

#define ll long long
#define pii pair<ll, ll> 
#define X first
#define Y second
#define pb push_back

using namespace std; 

const int N = 1010;
const ll MOD = 1e9 + 7;

ll n, intcnt, l[N], r[N];
ll siz[N], fact[N], povrh[N][N], inv[N];
ll dp[N][N], calc[N][N];

int u[N][N];

vector<pii> intv;
vector<ll> v;

ll add(ll a, ll b){ 
	return (a + b >= MOD ? a + b - MOD : a + b);
}

ll mult(ll a, ll b){ 
	return a * b % MOD;
}

ll fastpow(ll b, ll e){ 
	ll ret = 1;
	while(e){
		if(e & 1) ret = mult(ret, b);
		b = mult(b, b);
		e >>= 1;
	}
	return ret;
}

ll divd(ll a, ll b){ 
	return mult(a, fastpow(b, MOD - 2));
}

void precompute(){ 
	fact[0] = 1;
	for(int i = 1; i < N; i++){ 
		fact[i] = mult(fact[i - 1], i);
		inv[i] = fastpow(fact[i], MOD - 2);
	}

	for(int i = 0; i < N; i++){ 
		for(int j = 0; j <= i; j++){ 
			if(j == 0 || j == i) povrh[i][j] = 1;
			else povrh[i][j] = add(povrh[i - 1][j - 1], povrh[i - 1][j]);
		}
	}
	
	for(int i = 0; i < intcnt; i++){
		ll sfact = 1; 
		for(ll k = 1; k <= n; k++){ 
			ll sfact = 1;
			for(ll j = 1; j <= k; j++){ 
				sfact = mult(sfact, siz[i] - j + 1);
				calc[i][k] = add(calc[i][k], mult(povrh[k - 1][j - 1], mult(sfact, inv[j])));
			}
		}
	}
}

ll DP(int x, int b){ 
	if(b >= intcnt) return 1;
	if(dp[x][b] != -1) return dp[x][b];

	dp[x][b] = DP(x, b + 1);

	int cnt = 0;
	for(int i = x; i < n; i++){ 
		cnt += u[i][b];
		if(u[i][b]) dp[x][b] = add(dp[x][b], mult(calc[b][cnt], DP(i + 1, b + 1)));
	}

	return dp[x][b];
}

int main(){ 
	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dp[i][j] = -1;

	scanf("%lld", &n);

	for(int i = 0; i < n; i++){ 
		scanf("%lld%lld", &l[i], &r[i]);
		v.pb(l[i]);
		v.pb(r[i]);
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());

	for(int i = 0; i < v.size(); i++){ 
		if(i != 0 && v[i - 1] < v[i] - 1){ 
			intv.pb({v[i - 1] + 1, v[i] - 1});
		}
		intv.pb({v[i], v[i]});
	}

	intcnt = intv.size();
 
	for(int i = 0; i < intcnt; i++) siz[i] = intv[i].Y - intv[i].X + 1;

	for(int i = 0; i < n; i++){
		for(ll j = 0; j < intcnt; j++){ 
			if(intv[j].X >= l[i] && intv[j].Y <= r[i]){ 
				u[i][j] = true;
			}
		}
	}

	precompute();
	
	printf("%lld\n", add(DP(0, 0), MOD - 1));
	return 0;
}

Compilation message

boat.cpp: In function 'void precompute()':
boat.cpp:60:6: warning: unused variable 'sfact' [-Wunused-variable]
   60 |   ll sfact = 1;
      |      ^~~~~
boat.cpp: In function 'int main()':
boat.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
boat.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
boat.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   scanf("%lld%lld", &l[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 25096 KB Output is correct
2 Correct 926 ms 25144 KB Output is correct
3 Correct 904 ms 25004 KB Output is correct
4 Correct 888 ms 24964 KB Output is correct
5 Correct 905 ms 24964 KB Output is correct
6 Correct 935 ms 25388 KB Output is correct
7 Correct 919 ms 25324 KB Output is correct
8 Correct 919 ms 25300 KB Output is correct
9 Correct 948 ms 25320 KB Output is correct
10 Correct 968 ms 25380 KB Output is correct
11 Correct 953 ms 25308 KB Output is correct
12 Correct 923 ms 25348 KB Output is correct
13 Correct 920 ms 25276 KB Output is correct
14 Correct 926 ms 25260 KB Output is correct
15 Correct 940 ms 25232 KB Output is correct
16 Correct 193 ms 18588 KB Output is correct
17 Correct 196 ms 18704 KB Output is correct
18 Correct 176 ms 18704 KB Output is correct
19 Correct 200 ms 19072 KB Output is correct
20 Correct 173 ms 18680 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 25096 KB Output is correct
2 Correct 926 ms 25144 KB Output is correct
3 Correct 904 ms 25004 KB Output is correct
4 Correct 888 ms 24964 KB Output is correct
5 Correct 905 ms 24964 KB Output is correct
6 Correct 935 ms 25388 KB Output is correct
7 Correct 919 ms 25324 KB Output is correct
8 Correct 919 ms 25300 KB Output is correct
9 Correct 948 ms 25320 KB Output is correct
10 Correct 968 ms 25380 KB Output is correct
11 Correct 953 ms 25308 KB Output is correct
12 Correct 923 ms 25348 KB Output is correct
13 Correct 920 ms 25276 KB Output is correct
14 Correct 926 ms 25260 KB Output is correct
15 Correct 940 ms 25232 KB Output is correct
16 Correct 193 ms 18588 KB Output is correct
17 Correct 196 ms 18704 KB Output is correct
18 Correct 176 ms 18704 KB Output is correct
19 Correct 200 ms 19072 KB Output is correct
20 Correct 173 ms 18680 KB Output is correct
21 Incorrect 1427 ms 23348 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 17684 KB Output is correct
2 Correct 26 ms 17568 KB Output is correct
3 Correct 26 ms 17628 KB Output is correct
4 Correct 34 ms 17632 KB Output is correct
5 Correct 28 ms 17596 KB Output is correct
6 Correct 32 ms 17636 KB Output is correct
7 Correct 38 ms 17620 KB Output is correct
8 Correct 30 ms 17628 KB Output is correct
9 Correct 30 ms 17656 KB Output is correct
10 Correct 32 ms 17604 KB Output is correct
11 Correct 28 ms 17680 KB Output is correct
12 Correct 27 ms 17688 KB Output is correct
13 Correct 27 ms 17620 KB Output is correct
14 Correct 28 ms 17680 KB Output is correct
15 Correct 30 ms 17620 KB Output is correct
16 Correct 17 ms 16468 KB Output is correct
17 Correct 16 ms 16572 KB Output is correct
18 Correct 17 ms 16596 KB Output is correct
19 Correct 15 ms 16468 KB Output is correct
20 Correct 16 ms 16604 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 25096 KB Output is correct
2 Correct 926 ms 25144 KB Output is correct
3 Correct 904 ms 25004 KB Output is correct
4 Correct 888 ms 24964 KB Output is correct
5 Correct 905 ms 24964 KB Output is correct
6 Correct 935 ms 25388 KB Output is correct
7 Correct 919 ms 25324 KB Output is correct
8 Correct 919 ms 25300 KB Output is correct
9 Correct 948 ms 25320 KB Output is correct
10 Correct 968 ms 25380 KB Output is correct
11 Correct 953 ms 25308 KB Output is correct
12 Correct 923 ms 25348 KB Output is correct
13 Correct 920 ms 25276 KB Output is correct
14 Correct 926 ms 25260 KB Output is correct
15 Correct 940 ms 25232 KB Output is correct
16 Correct 193 ms 18588 KB Output is correct
17 Correct 196 ms 18704 KB Output is correct
18 Correct 176 ms 18704 KB Output is correct
19 Correct 200 ms 19072 KB Output is correct
20 Correct 173 ms 18680 KB Output is correct
21 Incorrect 1427 ms 23348 KB Output isn't correct
22 Halted 0 ms 0 KB -