oj.uz

Submission #108396

# Submission time Handle Problem Language Result Execution time Memory
108396 2019-04-29T06:03:17 Z nxteru Boat (APIO16_boat) C++14
9 / 100
 1036 ms 7144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 1000000007
#define PB push_back
ll n,a[505],b[505],dp[505][1005],s[1005][505],f[505],ans;
vector<ll>cm;
int main(void){
    scanf("%lld",&n);
    f[1]=1;
    for(int i=2;i<n;i++)f[i]=M-(M/i)*f[M%i]%M;
    for(int i=0;i<n;i++){
		scanf("%lld%lld",a+i,b+i);
		a[i]--;
		cm.PB(a[i]);
		cm.PB(b[i]);
	}
	sort(cm.begin(),cm.end());
	cm.erase(unique(cm.begin(),cm.end()),cm.end());
	for(int i=0;i<n;i++){
		a[i]=lower_bound(cm.begin(),cm.end(),a[i])-cm.begin();
		b[i]=lower_bound(cm.begin(),cm.end(),b[i])-cm.begin();
	}
	for(int i=1;i<cm.size();i++){
		ll p=cm[i]-cm[i-1];
		s[i][0]=1;
		for(ll j=1;j<n;j++){
			s[i][j]=s[i][j-1]*(p+j-1LL)%M*f[j]%M;
		}
	}
	for(int i=0;i<n;i++){
		ll p=1;
		for(int j=1;j<=b[i];j++){
			if(j>a[i]){
				dp[i][j]=p;
				ans=(ans+p*s[j][1]%M)%M;
			}
			for(int k=0;k<i;k++)p=(p+dp[k][j]*s[j][i-k]%M)%M;
		}
	}
	printf("%lld\n",ans);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<cm.size();i++){
              ~^~~~~~~~~~
boat.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
boat.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",a+i,b+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 6332 KB Output is correct
2 Correct 583 ms 6172 KB Output is correct
3 Correct 672 ms 6228 KB Output is correct
4 Correct 613 ms 6192 KB Output is correct
5 Correct 605 ms 6232 KB Output is correct
6 Correct 659 ms 6308 KB Output is correct
7 Correct 933 ms 6308 KB Output is correct
8 Correct 828 ms 6304 KB Output is correct
9 Correct 935 ms 6436 KB Output is correct
10 Correct 806 ms 6392 KB Output is correct
11 Correct 895 ms 6464 KB Output is correct
12 Correct 1036 ms 6332 KB Output is correct
13 Correct 835 ms 6364 KB Output is correct
14 Correct 683 ms 6392 KB Output is correct
15 Correct 590 ms 6400 KB Output is correct
16 Correct 103 ms 3064 KB Output is correct
17 Correct 66 ms 3064 KB Output is correct
18 Correct 56 ms 3072 KB Output is correct
19 Correct 63 ms 3192 KB Output is correct
20 Correct 63 ms 3064 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 6332 KB Output is correct
2 Correct 583 ms 6172 KB Output is correct
3 Correct 672 ms 6228 KB Output is correct
4 Correct 613 ms 6192 KB Output is correct
5 Correct 605 ms 6232 KB Output is correct
6 Correct 659 ms 6308 KB Output is correct
7 Correct 933 ms 6308 KB Output is correct
8 Correct 828 ms 6304 KB Output is correct
9 Correct 935 ms 6436 KB Output is correct
10 Correct 806 ms 6392 KB Output is correct
11 Correct 895 ms 6464 KB Output is correct
12 Correct 1036 ms 6332 KB Output is correct
13 Correct 835 ms 6364 KB Output is correct
14 Correct 683 ms 6392 KB Output is correct
15 Correct 590 ms 6400 KB Output is correct
16 Correct 103 ms 3064 KB Output is correct
17 Correct 66 ms 3064 KB Output is correct
18 Correct 56 ms 3072 KB Output is correct
19 Correct 63 ms 3192 KB Output is correct
20 Correct 63 ms 3064 KB Output is correct
21 Incorrect 934 ms 7144 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 6332 KB Output is correct
2 Correct 583 ms 6172 KB Output is correct
3 Correct 672 ms 6228 KB Output is correct
4 Correct 613 ms 6192 KB Output is correct
5 Correct 605 ms 6232 KB Output is correct
6 Correct 659 ms 6308 KB Output is correct
7 Correct 933 ms 6308 KB Output is correct
8 Correct 828 ms 6304 KB Output is correct
9 Correct 935 ms 6436 KB Output is correct
10 Correct 806 ms 6392 KB Output is correct
11 Correct 895 ms 6464 KB Output is correct
12 Correct 1036 ms 6332 KB Output is correct
13 Correct 835 ms 6364 KB Output is correct
14 Correct 683 ms 6392 KB Output is correct
15 Correct 590 ms 6400 KB Output is correct
16 Correct 103 ms 3064 KB Output is correct
17 Correct 66 ms 3064 KB Output is correct
18 Correct 56 ms 3072 KB Output is correct
19 Correct 63 ms 3192 KB Output is correct
20 Correct 63 ms 3064 KB Output is correct
21 Incorrect 934 ms 7144 KB Output isn't correct
22 Halted 0 ms 0 KB -