답안 #108411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108411	2019-04-29T06:47:53 Z	nxteru	Boat (APIO16_boat)	C++14	100 / 100	1961 ms	12368 KB

boat

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
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,r[1005][505],l[505];
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=n-1;i>=0;i--){
		for(int j=1;j<cm.size();j++){
			if(a[i]<j&&j<=b[i])r[j][i]++;
			r[j][i]+=r[j][i+1];
		}
	}
	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][r[j][i]]%M)%M;
			}
			for(int k=0;k<i;k++)p=(p+dp[k][j]*s[j][r[j][k]-r[j][i]]%M)%M;
		}
	}
	printf("%lld\n",ans);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<cm.size();j++){
               ~^~~~~~~~~~
boat.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<cm.size();i++){
              ~^~~~~~~~~~
boat.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
boat.cpp:16: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

#	결과	실행 시간	메모리	Grader output
1	Correct	710 ms	10188 KB	Output is correct
2	Correct	659 ms	10316 KB	Output is correct
3	Correct	604 ms	10244 KB	Output is correct
4	Correct	628 ms	10240 KB	Output is correct
5	Correct	625 ms	10232 KB	Output is correct
6	Correct	694 ms	10392 KB	Output is correct
7	Correct	943 ms	10460 KB	Output is correct
8	Correct	901 ms	10308 KB	Output is correct
9	Correct	991 ms	10404 KB	Output is correct
10	Correct	1034 ms	10360 KB	Output is correct
11	Correct	907 ms	10208 KB	Output is correct
12	Correct	930 ms	10296 KB	Output is correct
13	Correct	1002 ms	10232 KB	Output is correct
14	Correct	1171 ms	10488 KB	Output is correct
15	Correct	1097 ms	10360 KB	Output is correct
16	Correct	63 ms	3832 KB	Output is correct
17	Correct	60 ms	3832 KB	Output is correct
18	Correct	60 ms	3832 KB	Output is correct
19	Correct	90 ms	3832 KB	Output is correct
20	Correct	60 ms	3836 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	710 ms	10188 KB	Output is correct
2	Correct	659 ms	10316 KB	Output is correct
3	Correct	604 ms	10244 KB	Output is correct
4	Correct	628 ms	10240 KB	Output is correct
5	Correct	625 ms	10232 KB	Output is correct
6	Correct	694 ms	10392 KB	Output is correct
7	Correct	943 ms	10460 KB	Output is correct
8	Correct	901 ms	10308 KB	Output is correct
9	Correct	991 ms	10404 KB	Output is correct
10	Correct	1034 ms	10360 KB	Output is correct
11	Correct	907 ms	10208 KB	Output is correct
12	Correct	930 ms	10296 KB	Output is correct
13	Correct	1002 ms	10232 KB	Output is correct
14	Correct	1171 ms	10488 KB	Output is correct
15	Correct	1097 ms	10360 KB	Output is correct
16	Correct	63 ms	3832 KB	Output is correct
17	Correct	60 ms	3832 KB	Output is correct
18	Correct	60 ms	3832 KB	Output is correct
19	Correct	90 ms	3832 KB	Output is correct
20	Correct	60 ms	3836 KB	Output is correct
21	Correct	935 ms	10660 KB	Output is correct
22	Correct	1230 ms	10616 KB	Output is correct
23	Correct	969 ms	10424 KB	Output is correct
24	Correct	984 ms	10584 KB	Output is correct
25	Correct	1000 ms	10596 KB	Output is correct
26	Correct	1310 ms	11248 KB	Output is correct
27	Correct	1409 ms	11280 KB	Output is correct
28	Correct	1497 ms	11132 KB	Output is correct
29	Correct	1498 ms	11128 KB	Output is correct
30	Correct	942 ms	10352 KB	Output is correct
31	Correct	958 ms	10360 KB	Output is correct
32	Correct	983 ms	10216 KB	Output is correct
33	Correct	959 ms	10400 KB	Output is correct
34	Correct	1067 ms	10316 KB	Output is correct
35	Correct	625 ms	10104 KB	Output is correct
36	Correct	676 ms	10400 KB	Output is correct
37	Correct	465 ms	10232 KB	Output is correct
38	Correct	663 ms	10204 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	2304 KB	Output is correct
2	Correct	8 ms	2304 KB	Output is correct
3	Correct	9 ms	2304 KB	Output is correct
4	Correct	11 ms	2304 KB	Output is correct
5	Correct	9 ms	2432 KB	Output is correct
6	Correct	10 ms	2508 KB	Output is correct
7	Correct	12 ms	2432 KB	Output is correct
8	Correct	9 ms	2432 KB	Output is correct
9	Correct	36 ms	2424 KB	Output is correct
10	Correct	9 ms	2432 KB	Output is correct
11	Correct	9 ms	2432 KB	Output is correct
12	Correct	9 ms	2432 KB	Output is correct
13	Correct	8 ms	2432 KB	Output is correct
14	Correct	9 ms	2304 KB	Output is correct
15	Correct	8 ms	2432 KB	Output is correct
16	Correct	5 ms	1664 KB	Output is correct
17	Correct	5 ms	1664 KB	Output is correct
18	Correct	6 ms	1664 KB	Output is correct
19	Correct	5 ms	1708 KB	Output is correct
20	Correct	5 ms	1664 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	710 ms	10188 KB	Output is correct
2	Correct	659 ms	10316 KB	Output is correct
3	Correct	604 ms	10244 KB	Output is correct
4	Correct	628 ms	10240 KB	Output is correct
5	Correct	625 ms	10232 KB	Output is correct
6	Correct	694 ms	10392 KB	Output is correct
7	Correct	943 ms	10460 KB	Output is correct
8	Correct	901 ms	10308 KB	Output is correct
9	Correct	991 ms	10404 KB	Output is correct
10	Correct	1034 ms	10360 KB	Output is correct
11	Correct	907 ms	10208 KB	Output is correct
12	Correct	930 ms	10296 KB	Output is correct
13	Correct	1002 ms	10232 KB	Output is correct
14	Correct	1171 ms	10488 KB	Output is correct
15	Correct	1097 ms	10360 KB	Output is correct
16	Correct	63 ms	3832 KB	Output is correct
17	Correct	60 ms	3832 KB	Output is correct
18	Correct	60 ms	3832 KB	Output is correct
19	Correct	90 ms	3832 KB	Output is correct
20	Correct	60 ms	3836 KB	Output is correct
21	Correct	935 ms	10660 KB	Output is correct
22	Correct	1230 ms	10616 KB	Output is correct
23	Correct	969 ms	10424 KB	Output is correct
24	Correct	984 ms	10584 KB	Output is correct
25	Correct	1000 ms	10596 KB	Output is correct
26	Correct	1310 ms	11248 KB	Output is correct
27	Correct	1409 ms	11280 KB	Output is correct
28	Correct	1497 ms	11132 KB	Output is correct
29	Correct	1498 ms	11128 KB	Output is correct
30	Correct	942 ms	10352 KB	Output is correct
31	Correct	958 ms	10360 KB	Output is correct
32	Correct	983 ms	10216 KB	Output is correct
33	Correct	959 ms	10400 KB	Output is correct
34	Correct	1067 ms	10316 KB	Output is correct
35	Correct	625 ms	10104 KB	Output is correct
36	Correct	676 ms	10400 KB	Output is correct
37	Correct	465 ms	10232 KB	Output is correct
38	Correct	663 ms	10204 KB	Output is correct
39	Correct	8 ms	2304 KB	Output is correct
40	Correct	8 ms	2304 KB	Output is correct
41	Correct	9 ms	2304 KB	Output is correct
42	Correct	11 ms	2304 KB	Output is correct
43	Correct	9 ms	2432 KB	Output is correct
44	Correct	10 ms	2508 KB	Output is correct
45	Correct	12 ms	2432 KB	Output is correct
46	Correct	9 ms	2432 KB	Output is correct
47	Correct	36 ms	2424 KB	Output is correct
48	Correct	9 ms	2432 KB	Output is correct
49	Correct	9 ms	2432 KB	Output is correct
50	Correct	9 ms	2432 KB	Output is correct
51	Correct	8 ms	2432 KB	Output is correct
52	Correct	9 ms	2304 KB	Output is correct
53	Correct	8 ms	2432 KB	Output is correct
54	Correct	5 ms	1664 KB	Output is correct
55	Correct	5 ms	1664 KB	Output is correct
56	Correct	6 ms	1664 KB	Output is correct
57	Correct	5 ms	1708 KB	Output is correct
58	Correct	5 ms	1664 KB	Output is correct
59	Correct	1289 ms	11512 KB	Output is correct
60	Correct	1226 ms	11456 KB	Output is correct
61	Correct	1164 ms	11356 KB	Output is correct
62	Correct	1242 ms	11512 KB	Output is correct
63	Correct	1157 ms	11616 KB	Output is correct
64	Correct	1593 ms	12292 KB	Output is correct
65	Correct	1807 ms	12300 KB	Output is correct
66	Correct	1961 ms	12260 KB	Output is correct
67	Correct	1682 ms	12368 KB	Output is correct
68	Correct	1928 ms	12340 KB	Output is correct
69	Correct	1419 ms	11400 KB	Output is correct
70	Correct	1488 ms	11388 KB	Output is correct
71	Correct	1426 ms	11512 KB	Output is correct
72	Correct	1510 ms	11420 KB	Output is correct
73	Correct	1422 ms	11648 KB	Output is correct
74	Correct	124 ms	4060 KB	Output is correct
75	Correct	141 ms	4160 KB	Output is correct
76	Correct	123 ms	4108 KB	Output is correct
77	Correct	143 ms	4148 KB	Output is correct
78	Correct	127 ms	4088 KB	Output is correct

답안 #108411

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 42.0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
42.0 / 42.0