oj.uz

Submission #793002

# Submission time Handle Problem Language Result Execution time Memory
793002 2023-07-25T12:19:24 Z algorithm16 Boat (APIO16_boat) C++14
27 / 100
 2000 ms 4288 KB 
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,a[505],b[505],dp[1505][2][505],inv[505],mod=1e9+7;
vector <int> v,v1;
vector <vector<int> > v2;
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 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=1;i<=n;i++) {
		inv[i]=exp(i,mod-2);
	}
	for(int i=0;i<v.size()-1;i++) {
		for(int j=0;j<=n;j++) {
			dp[i][n%2][j]=1;
		}
	}
	for(int x=n-1;x>=0;x--) {
		for(int idx=0;idx<v.size()-1;idx++) {
			for(int cnt=0;cnt<=x;cnt++) {
				int ret=0;
				ret=sum(ret,dp[idx][(x+1)%2][cnt]); // 0
				if(v[idx]>=a[x] && v[idx+1]-1<=b[x]) {
					if(cnt<=v[idx+1]-1-v[idx]) ret=sum(ret,mul(dp[idx][(x+1)%2][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(dp[i][(x+1)%2][1],v[i+1]-v[i]));
				}
				dp[idx][x%2][cnt]=ret;
				//cout << idx << " " << x << " " << cnt << "  " << ret << "\n";
			}
		}
	}
	cout << dp[0][0][0]-1;
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i=0;i<v.size()-1;i++) {
      |              ~^~~~~~~~~~~
boat.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int idx=0;idx<v.size()-1;idx++) {
      |                 ~~~^~~~~~~~~~~
boat.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=idx+1;i<v.size()-1;i++) {
      |                     ~^~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 4288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 4288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 828 ms 1516 KB Output is correct
2 Correct 750 ms 1508 KB Output is correct
3 Correct 793 ms 1492 KB Output is correct
4 Correct 830 ms 1492 KB Output is correct
5 Correct 884 ms 1508 KB Output is correct
6 Correct 1315 ms 1492 KB Output is correct
7 Correct 1296 ms 1624 KB Output is correct
8 Correct 1287 ms 1504 KB Output is correct
9 Correct 1325 ms 1512 KB Output is correct
10 Correct 1321 ms 1496 KB Output is correct
11 Correct 903 ms 1504 KB Output is correct
12 Correct 751 ms 1508 KB Output is correct
13 Correct 758 ms 1492 KB Output is correct
14 Correct 805 ms 1496 KB Output is correct
15 Correct 865 ms 1508 KB Output is correct
16 Correct 213 ms 884 KB Output is correct
17 Correct 183 ms 852 KB Output is correct
18 Correct 190 ms 852 KB Output is correct
19 Correct 171 ms 852 KB Output is correct
20 Correct 209 ms 888 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 4288 KB Time limit exceeded
2 Halted 0 ms 0 KB -