oj.uz

Submission #792984

# Submission time Handle Problem Language Result Execution time Memory
792984 2023-07-25T11:59:02 Z algorithm16 Boat (APIO16_boat) C++14
27 / 100
 1237 ms 524288 KB 
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,dp[1505][505][505],a[505],b[505],inv[505],mod=1e9+7;
vector <int> v;
int sum(int a,int b) {
	return (a+b)%mod;
}
int mul(int a,int b) {
	return ((long long)a*b)%mod;
}
int exp(int a,int b) {
	if(!b) return 1;
	int ret=exp(a,b/2);
	if(b%2==0) return mul(ret,ret);
	return mul(mul(ret,ret),a);
}
int rec(int idx,int x,int cnt) {
	if(idx>=v.size()-1) return 0;
	if(x>=n) return 1;
	if(dp[idx][x][cnt]!=-1) return dp[idx][x][cnt];
	int ret=0;
	ret=sum(ret,rec(idx,x+1,cnt)); // 0
	
	//if(idx==0 && x==1 && cnt==1) cout << ret << "\n";
	if(v[idx]>=a[x] && v[idx+1]-1<=b[x]) {
		if(cnt<=v[idx+1]-1-v[idx]) ret=sum(ret,mul(rec(idx,x+1,cnt+1),mul(v[idx+1]-v[idx]-cnt,inv[cnt+1])));
	}
	for(int i=idx+1;i<v.size()-1;i++) {
		if(v[i]>=a[x] && v[i+1]-1<=b[x]) ret=sum(ret,mul(rec(i,x+1,1),v[i+1]-v[i]));
	}
	dp[idx][x][cnt]=ret;
	//cout << idx << " " << x << " " << cnt << " " << ret << "\n";
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i=0;i<n;i++) {
		cin >> a[i] >> b[i];
		v.push_back(a[i]);
		v.push_back(b[i]);
		v.push_back(b[i]+1);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	/*for(int i=0;i<v.size()-1;i++) {
		cout << v[i] << " " << v[i+1]-1 << "\n";
	}*/
	/*for(int i=0;i<n;i++) {
		a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin();
		b[i]=lower_bound(v.begin(),v.end(),b[i])-v.begin();
	}*/
	for(int i=0;i<v.size()-1;i++) {
		for(int j=0;j<n;j++) {
			for(int k=0;k<=j;k++) {
				dp[i][j][k]=-1;
			}
		}
	}
	for(int i=1;i<=n;i++) {
		inv[i]=exp(i,mod-2);
	}
	cout << rec(0,0,0)-1;
	return 0;
}

Compilation message

boat.cpp: In function 'int rec(int, int, int)':
boat.cpp:21:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  if(idx>=v.size()-1) return 0;
      |     ~~~^~~~~~~~~~~~
boat.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i=idx+1;i<v.size()-1;i++) {
      |                  ~^~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i=0;i<v.size()-1;i++) {
      |              ~^~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 60392 KB Output is correct
2 Correct 323 ms 60400 KB Output is correct
3 Correct 458 ms 60376 KB Output is correct
4 Correct 435 ms 60396 KB Output is correct
5 Correct 471 ms 60360 KB Output is correct
6 Correct 1237 ms 60400 KB Output is correct
7 Correct 1082 ms 60400 KB Output is correct
8 Correct 1237 ms 60396 KB Output is correct
9 Correct 1099 ms 60408 KB Output is correct
10 Correct 1148 ms 60396 KB Output is correct
11 Correct 587 ms 60400 KB Output is correct
12 Correct 425 ms 60396 KB Output is correct
13 Correct 499 ms 60396 KB Output is correct
14 Correct 565 ms 60328 KB Output is correct
15 Correct 571 ms 60396 KB Output is correct
16 Correct 101 ms 29564 KB Output is correct
17 Correct 85 ms 28752 KB Output is correct
18 Correct 77 ms 28548 KB Output is correct
19 Correct 68 ms 28112 KB Output is correct
20 Correct 90 ms 29564 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 289 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -