oj.uz

Submission #792989

# Submission time Handle Problem Language Result Execution time Memory
792989 2023-07-25T12:04:50 Z algorithm16 Boat (APIO16_boat) C++14
27 / 100
 1106 ms 524288 KB 
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,a[505],b[505],inv[505],mod=1e9+7;
vector <int> v,v1;
vector <vector<int> > v2;
vector <vector<vector<int> > > dp;
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++) {
		dp.push_back(v2);
		for(int j=0;j<n;j++) {
			dp[i].push_back(v1);
			for(int k=0;k<=j;k++) {
				dp[i][j].push_back(-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:23:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  if(idx>=v.size()-1) return 0;
      |     ~~~^~~~~~~~~~~~
boat.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for(int i=idx+1;i<v.size()-1;i++) {
      |                  ~^~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:59:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i=0;i<v.size()-1;i++) {
      |              ~^~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 519 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 519 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 363 ms 10276 KB Output is correct
2 Correct 232 ms 10260 KB Output is correct
3 Correct 310 ms 10256 KB Output is correct
4 Correct 386 ms 10264 KB Output is correct
5 Correct 371 ms 10256 KB Output is correct
6 Correct 1016 ms 10264 KB Output is correct
7 Correct 1045 ms 10256 KB Output is correct
8 Correct 1089 ms 10264 KB Output is correct
9 Correct 1046 ms 10196 KB Output is correct
10 Correct 1106 ms 10260 KB Output is correct
11 Correct 537 ms 10260 KB Output is correct
12 Correct 365 ms 10260 KB Output is correct
13 Correct 416 ms 10256 KB Output is correct
14 Correct 457 ms 10272 KB Output is correct
15 Correct 483 ms 10260 KB Output is correct
16 Correct 83 ms 5160 KB Output is correct
17 Correct 59 ms 4948 KB Output is correct
18 Correct 71 ms 5004 KB Output is correct
19 Correct 55 ms 4920 KB Output is correct
20 Correct 76 ms 5152 KB Output is correct

Subtask #4
0 / 42.0

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