oj.uz

Submission #262837

# Submission time Handle Problem Language Result Execution time Memory
262837 2020-08-13T09:50:25 Z hohohaha Boat (APIO16_boat) C++14
9 / 100
 1648 ms 40068 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long

#define ii pair<int, int>
#define vii vector<ii>

#define iii pair<int, ii>
#define viii vector<iii>

#define ld long double
#define li long long

#define eb emplace_back
#define vi vector<int>
#define fi first
#define se second

const int mod = 1e9+7, maxn = 505;

int n, l[maxn], r[maxn], low[maxn][maxn], up[maxn][maxn], C[maxn][6*maxn], back[6*maxn][maxn], fac[maxn], dp[maxn][6*maxn][2], sdp[maxn][6*maxn];
vi all;
vii seg; 

void add(int& a, int b)
{
	a = (a+b)%mod;
}
int mul(int a, int b)
{
	return a*b%mod;
}
int binpow(int x, int k)
{
	if(!k) return 1;
	int t = binpow(x, k/2);
	if(k&1) return mul(mul(t, t), x);
	return mul(t, t);
}
int inv(int x)
{
	return binpow(x, mod-2);
}
void init()
{
	for(int i=0; i<=n; i++)
	{
		if(!i) fac[i] = 1;
		else fac[i] = mul(fac[i-1], i);
	}
}
signed main()
{
	cin>>n;
	init();
	for(int i=1; i<=n; i++)
	{
		cin>>l[i]>>r[i];
		all.eb(l[i]-1);
		all.eb(r[i]+1);
		all.eb(l[i]);
		all.eb(r[i]);
	}
	all.eb(0);
	for(int i=1; i<=n; i++)
	{
		low[i][i] = l[i]; 
		up[i][i] = r[i];
		for(int j=i+1; j<=n; j++)
		{
			low[i][j] = max(low[i][j-1], l[j]);
			up[i][j] = min(up[i][j-1], r[j]);
		}
	}
	sort(begin(all), end(all));
	seg.eb(0, 0);
	for(int i=1; i<all.size(); i++)
	{
//		cout<<all[i-1]+1<<" "<<all[i]<<endl;
		if(all[i]-all[i-1]) seg.eb(all[i-1]+1, all[i]);
	}
	for(int i=1; i<seg.size(); i++)
	{
//		cout<<i<<" "<<endl;
		int range = seg[i].se - seg[i].fi+1;
		for(int j=0; j<=min(range, n); j++)
		{
//			cout<<j<<endl;
			if(!j) back[i][j]=1;
 			else back[i][j] = mul(back[i][j-1], range - j+1);
 			C[j][i] = mul(back[i][j], inv(fac[j]));
		}
	}
	dp[0][0][0] = 1;
	for(int i=0; i<=n; i++)
	{
		for(int k=0; k<seg.size(); k++)
		{
			if(i)
			{
				if(!k)
				{
					dp[i][k][0] = 1;
					dp[i][k][1] = 0;
				}
				else
				{
					for(int j=1; j<=i; j++)
					{
						add(dp[i][k][0], dp[j-1][k][1]);
						if(low[j][i]<=seg[k].fi and seg[k].se<=up[j][i])
						{
//							cout<<sdp[j-1][k-1]<<" "<<C[i-j+1][k]<<" "<<back[k][j-i+1]<<endl;
							add(dp[i][k][1], mul(sdp[j-1][k-1], C[i-j+1][k]));
//							cout<<j<<" "<<i<<" "<<k<<"fick \n";
//							cout<<low[j][i]<<" "<<up[j][i]<<e0ndl;
						}
					}
				}
//				cout<<i<<" "<<k<<": 0: "<<dp[i][k][0]<<" 1: "<<dp[i][k][1]<<endl;
			}
			add(sdp[i][k], dp[i][k][0]);
			add(sdp[i][k], dp[i][k][1]);
			if(k) add(sdp[i][k], sdp[i][k-1]);
		}
	}
	int ans = sdp[n][seg.size()-1]-1;
	while(ans<0) add(ans, mod);
	cout<<ans;	
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:79:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=1; i<all.size(); i++)
      |               ~^~~~~~~~~~~
boat.cpp:84:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=1; i<seg.size(); i++)
      |               ~^~~~~~~~~~~
boat.cpp:99:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int k=0; k<seg.size(); k++)
      |                ~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 39916 KB Output is correct
2 Correct 1554 ms 40068 KB Output is correct
3 Correct 1480 ms 39824 KB Output is correct
4 Correct 1648 ms 39800 KB Output is correct
5 Correct 1495 ms 39872 KB Output is correct
6 Correct 1607 ms 39988 KB Output is correct
7 Correct 1646 ms 39932 KB Output is correct
8 Correct 1463 ms 39892 KB Output is correct
9 Correct 1504 ms 39800 KB Output is correct
10 Correct 1461 ms 39972 KB Output is correct
11 Correct 1500 ms 39800 KB Output is correct
12 Correct 1538 ms 39800 KB Output is correct
13 Correct 1488 ms 39800 KB Output is correct
14 Correct 1511 ms 39800 KB Output is correct
15 Correct 1511 ms 39928 KB Output is correct
16 Correct 222 ms 15608 KB Output is correct
17 Correct 228 ms 16120 KB Output is correct
18 Correct 225 ms 15736 KB Output is correct
19 Correct 224 ms 15996 KB Output is correct
20 Correct 228 ms 15864 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 39916 KB Output is correct
2 Correct 1554 ms 40068 KB Output is correct
3 Correct 1480 ms 39824 KB Output is correct
4 Correct 1648 ms 39800 KB Output is correct
5 Correct 1495 ms 39872 KB Output is correct
6 Correct 1607 ms 39988 KB Output is correct
7 Correct 1646 ms 39932 KB Output is correct
8 Correct 1463 ms 39892 KB Output is correct
9 Correct 1504 ms 39800 KB Output is correct
10 Correct 1461 ms 39972 KB Output is correct
11 Correct 1500 ms 39800 KB Output is correct
12 Correct 1538 ms 39800 KB Output is correct
13 Correct 1488 ms 39800 KB Output is correct
14 Correct 1511 ms 39800 KB Output is correct
15 Correct 1511 ms 39928 KB Output is correct
16 Correct 222 ms 15608 KB Output is correct
17 Correct 228 ms 16120 KB Output is correct
18 Correct 225 ms 15736 KB Output is correct
19 Correct 224 ms 15996 KB Output is correct
20 Correct 228 ms 15864 KB Output is correct
21 Incorrect 1554 ms 37016 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 5248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1504 ms 39916 KB Output is correct
2 Correct 1554 ms 40068 KB Output is correct
3 Correct 1480 ms 39824 KB Output is correct
4 Correct 1648 ms 39800 KB Output is correct
5 Correct 1495 ms 39872 KB Output is correct
6 Correct 1607 ms 39988 KB Output is correct
7 Correct 1646 ms 39932 KB Output is correct
8 Correct 1463 ms 39892 KB Output is correct
9 Correct 1504 ms 39800 KB Output is correct
10 Correct 1461 ms 39972 KB Output is correct
11 Correct 1500 ms 39800 KB Output is correct
12 Correct 1538 ms 39800 KB Output is correct
13 Correct 1488 ms 39800 KB Output is correct
14 Correct 1511 ms 39800 KB Output is correct
15 Correct 1511 ms 39928 KB Output is correct
16 Correct 222 ms 15608 KB Output is correct
17 Correct 228 ms 16120 KB Output is correct
18 Correct 225 ms 15736 KB Output is correct
19 Correct 224 ms 15996 KB Output is correct
20 Correct 228 ms 15864 KB Output is correct
21 Incorrect 1554 ms 37016 KB Output isn't correct
22 Halted 0 ms 0 KB -