oj.uz

Submission #99944

# Submission time Handle Problem Language Result Execution time Memory
99944 2019-03-08T21:12:37 Z TadijaSebez Boat (APIO16_boat) C++11
9 / 100
 1320 ms 1532 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=505;
const int M=2*N;
const int K=1000050;
const int mod=1e9+7;
int mul(int x, int y){ return (ll)x*y%mod;}
int add(int x, int y){ x+=y;return x>=mod?x-mod:x;}
int sub(int x, int y){ x-=y;return x<0?x+mod:x;}
int pow(int x, int k){ int ans=1;for(;k;k>>=1,x=mul(x,x)) if(k&1) ans=mul(ans,x);return ans;}
int inv(int x){ return pow(x,mod-2);}
int F[K],I[K];
int binom(int n, int k){ return n<k?0:mul(F[n],mul(I[k],I[n-k]));}
int dp[N],tmp[N][N],l[N],r[N];
void calc()
{
	F[0]=1;for(int i=1;i<K;i++) F[i]=mul(F[i-1],i);
	I[K-1]=inv(F[K-1]);for(int i=K-2;~i;i--) I[i]=mul(I[i+1],i+1);
}
int bc[N];
int main()
{
	//calc();
	int n;
	scanf("%i",&n);
	vector<int> all;
	for(int i=1;i<=n;i++)
	{
		scanf("%i %i",&l[i],&r[i]);
		all.pb(l[i]);
		all.pb(r[i]+1);
	}
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	dp[0]=1;
	for(int t=1;t<all.size();t++)
	{
		int L=all[t]-all[t-1];
		bc[0]=1;
		for(int i=1;i<=n;i++) bc[i]=mul(bc[i-1],mul(L-i+1,inv(i)));
		for(int i=1;i<=n;i++) dp[i]=add(dp[i],dp[i-1]);
		for(int j=1;j<=n;j++)
		{
			for(int i=1;i<=n-j+1;i++)
			{
				if(all[t-1]<=r[i] && all[t-1]>=l[i]) tmp[i][j]=j==1?dp[i-1]:tmp[i-1][j-1];
				else tmp[i][j]=0;
			}
			if(j==1) for(int i=n;i>=1;i--) dp[i]=sub(dp[i],dp[i-1]);
			for(int i=1;i<=n-j+1;i++) dp[i]=add(dp[i],mul(tmp[i][j],bc[j]));
			for(int i=1;i<=n-j+1;i++) tmp[i][j]=add(tmp[i][j],tmp[i-1][j]);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=add(ans,dp[i]);
	printf("%i\n",ans);
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int t=1;t<all.size();t++)
              ~^~~~~~~~~~~
boat.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
boat.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&l[i],&r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 1400 KB Output is correct
2 Correct 1259 ms 1532 KB Output is correct
3 Correct 1213 ms 1528 KB Output is correct
4 Correct 1207 ms 1400 KB Output is correct
5 Correct 1169 ms 1528 KB Output is correct
6 Correct 1182 ms 1408 KB Output is correct
7 Correct 1190 ms 1404 KB Output is correct
8 Correct 1184 ms 1400 KB Output is correct
9 Correct 1244 ms 1408 KB Output is correct
10 Correct 1320 ms 1408 KB Output is correct
11 Correct 1266 ms 1408 KB Output is correct
12 Correct 1210 ms 1280 KB Output is correct
13 Correct 1192 ms 1280 KB Output is correct
14 Correct 1180 ms 1400 KB Output is correct
15 Correct 1188 ms 1404 KB Output is correct
16 Correct 263 ms 1280 KB Output is correct
17 Correct 255 ms 1400 KB Output is correct
18 Correct 216 ms 1408 KB Output is correct
19 Correct 232 ms 1528 KB Output is correct
20 Correct 241 ms 1504 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 1400 KB Output is correct
2 Correct 1259 ms 1532 KB Output is correct
3 Correct 1213 ms 1528 KB Output is correct
4 Correct 1207 ms 1400 KB Output is correct
5 Correct 1169 ms 1528 KB Output is correct
6 Correct 1182 ms 1408 KB Output is correct
7 Correct 1190 ms 1404 KB Output is correct
8 Correct 1184 ms 1400 KB Output is correct
9 Correct 1244 ms 1408 KB Output is correct
10 Correct 1320 ms 1408 KB Output is correct
11 Correct 1266 ms 1408 KB Output is correct
12 Correct 1210 ms 1280 KB Output is correct
13 Correct 1192 ms 1280 KB Output is correct
14 Correct 1180 ms 1400 KB Output is correct
15 Correct 1188 ms 1404 KB Output is correct
16 Correct 263 ms 1280 KB Output is correct
17 Correct 255 ms 1400 KB Output is correct
18 Correct 216 ms 1408 KB Output is correct
19 Correct 232 ms 1528 KB Output is correct
20 Correct 241 ms 1504 KB Output is correct
21 Incorrect 1045 ms 1504 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1148 ms 1400 KB Output is correct
2 Correct 1259 ms 1532 KB Output is correct
3 Correct 1213 ms 1528 KB Output is correct
4 Correct 1207 ms 1400 KB Output is correct
5 Correct 1169 ms 1528 KB Output is correct
6 Correct 1182 ms 1408 KB Output is correct
7 Correct 1190 ms 1404 KB Output is correct
8 Correct 1184 ms 1400 KB Output is correct
9 Correct 1244 ms 1408 KB Output is correct
10 Correct 1320 ms 1408 KB Output is correct
11 Correct 1266 ms 1408 KB Output is correct
12 Correct 1210 ms 1280 KB Output is correct
13 Correct 1192 ms 1280 KB Output is correct
14 Correct 1180 ms 1400 KB Output is correct
15 Correct 1188 ms 1404 KB Output is correct
16 Correct 263 ms 1280 KB Output is correct
17 Correct 255 ms 1400 KB Output is correct
18 Correct 216 ms 1408 KB Output is correct
19 Correct 232 ms 1528 KB Output is correct
20 Correct 241 ms 1504 KB Output is correct
21 Incorrect 1045 ms 1504 KB Output isn't correct
22 Halted 0 ms 0 KB -