oj.uz

Submission #108394

# Submission time Handle Problem Language Result Execution time Memory
108394 2019-04-29T06:00:23 Z nxteru Boat (APIO16_boat) C++14
9 / 100
 1050 ms 7032 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)%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 666 ms 6184 KB Output is correct
2 Correct 609 ms 6212 KB Output is correct
3 Correct 606 ms 6264 KB Output is correct
4 Correct 618 ms 6396 KB Output is correct
5 Correct 693 ms 6308 KB Output is correct
6 Correct 751 ms 6520 KB Output is correct
7 Correct 971 ms 6460 KB Output is correct
8 Correct 988 ms 6520 KB Output is correct
9 Correct 934 ms 6364 KB Output is correct
10 Correct 880 ms 6432 KB Output is correct
11 Correct 753 ms 6452 KB Output is correct
12 Correct 981 ms 6584 KB Output is correct
13 Correct 1004 ms 6376 KB Output is correct
14 Correct 1050 ms 6404 KB Output is correct
15 Correct 867 ms 6496 KB Output is correct
16 Correct 53 ms 3064 KB Output is correct
17 Correct 56 ms 3064 KB Output is correct
18 Correct 61 ms 3064 KB Output is correct
19 Correct 55 ms 3192 KB Output is correct
20 Correct 55 ms 3064 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 6184 KB Output is correct
2 Correct 609 ms 6212 KB Output is correct
3 Correct 606 ms 6264 KB Output is correct
4 Correct 618 ms 6396 KB Output is correct
5 Correct 693 ms 6308 KB Output is correct
6 Correct 751 ms 6520 KB Output is correct
7 Correct 971 ms 6460 KB Output is correct
8 Correct 988 ms 6520 KB Output is correct
9 Correct 934 ms 6364 KB Output is correct
10 Correct 880 ms 6432 KB Output is correct
11 Correct 753 ms 6452 KB Output is correct
12 Correct 981 ms 6584 KB Output is correct
13 Correct 1004 ms 6376 KB Output is correct
14 Correct 1050 ms 6404 KB Output is correct
15 Correct 867 ms 6496 KB Output is correct
16 Correct 53 ms 3064 KB Output is correct
17 Correct 56 ms 3064 KB Output is correct
18 Correct 61 ms 3064 KB Output is correct
19 Correct 55 ms 3192 KB Output is correct
20 Correct 55 ms 3064 KB Output is correct
21 Incorrect 782 ms 7032 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 6184 KB Output is correct
2 Correct 609 ms 6212 KB Output is correct
3 Correct 606 ms 6264 KB Output is correct
4 Correct 618 ms 6396 KB Output is correct
5 Correct 693 ms 6308 KB Output is correct
6 Correct 751 ms 6520 KB Output is correct
7 Correct 971 ms 6460 KB Output is correct
8 Correct 988 ms 6520 KB Output is correct
9 Correct 934 ms 6364 KB Output is correct
10 Correct 880 ms 6432 KB Output is correct
11 Correct 753 ms 6452 KB Output is correct
12 Correct 981 ms 6584 KB Output is correct
13 Correct 1004 ms 6376 KB Output is correct
14 Correct 1050 ms 6404 KB Output is correct
15 Correct 867 ms 6496 KB Output is correct
16 Correct 53 ms 3064 KB Output is correct
17 Correct 56 ms 3064 KB Output is correct
18 Correct 61 ms 3064 KB Output is correct
19 Correct 55 ms 3192 KB Output is correct
20 Correct 55 ms 3064 KB Output is correct
21 Incorrect 782 ms 7032 KB Output isn't correct
22 Halted 0 ms 0 KB -