Submission #389081

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
389081	2021-04-13T15:27:46 Z	mosiashvililuka	Boat (APIO16_boat)	C++14	36 / 100	34 ms	25356 KB

boat

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,mod=1000000007LL,sub1,f[509],DPI[509],pas,li,dp[1509],dpp[1509],dp2[1509][509],dpp2[1509][509],fct[509],C[1509][509],len[1509],wu[1509];
pair <long long, long long> p[509],l[5009];
map <long long, long long> m,n;
map <long long, long long>::iterator it,tt;
long long xar(long long q, long long w){
	if(w==0) return 1LL;
	long long qw=xar(q,w/2);
	if(w%2==0) return (qw*qw)%mod; else return ((qw*qw)%mod*q)%mod;
}
long long dv(long long q, long long w){
	return (q*xar(w,mod-2))%mod;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<=a; i++){
		cin>>p[i].first>>p[i].second;
		if(p[i].first!=p[i].second){
			sub1=1;
		}
	}
	if(sub1==0){
		DPI[a]=1;
		for(i=a-1; i>=1; i--){
			for(j=i+1; j<=a; j++){
				if(p[j].first>p[i].first){
					DPI[i]+=DPI[j];
					if(DPI[i]>=mod) DPI[i]-=mod;
				}
			}
			DPI[i]++;
			if(DPI[i]>=mod) DPI[i]-=mod;
		}
		for(i=1; i<=a; i++){
			pas+=DPI[i];
			if(pas>=mod) pas-=mod;
		}
		cout<<pas;
		return 0;
	}
	for(i=1; i<=a; i++){
		m[p[i].first]=1;
		m[p[i].second]=1;
	}
	
	for(it=m.begin(); it!=m.end(); it++){
		li++;
		l[li].first=(*it).first;
		l[li].second=(*it).first;
		tt=it;tt++;
		if(tt!=m.end()&&(*it).first+1<=(*tt).first-1){
			li++;
			l[li].first=(*it).first+1;
			l[li].second=(*tt).first-1;
		}
	}
	/*cout<<li<<endl;
	for(i=1; i<=li; i++){
		cout<<l[i].first<<" "<<l[i].second<<endl;
	}*/
	for(i=1; i<=li; i++){
		n[l[i].first]=l[i].second;
	}
	for(i=1; i<=li; i++){
		len[i]=l[i].second-l[i].first+1;
		C[i][0]=1;
		for(j=1; j<=min(a,len[i]); j++){
			zx=dv(len[i]-j+1,j);
			C[i][j]=(C[i][j-1]*zx)%mod;
			//cout<<len[i]<<" "<<j<<"  "<<C[i][j]<<endl;
		}
	}
	for(ii=a; ii>=1; ii--){
		for(i=0; i<=li+2; i++){
			dpp[i]=dp[i];
			for(j=0; j<=a+2; j++){
				dpp2[i][j]=dp2[i][j];
			}
		}
		for(i=1; i<=li; i++){
			if(l[i].second<p[ii].first||l[i].first>p[ii].second) continue;
			wu[i]++;
			for(j=i+1; j<=li; j++){
				/*dpp[i]+=dp[j]*len[i];
				dpp[i]%=mod;*/
				dpp2[i][1]+=dp[j];
				if(dpp2[i][1]>=mod) dpp2[i][1]-=mod;
			}
			dpp2[i][1]++;
			if(dpp2[i][1]>=mod) dpp2[i][1]-=mod;
			for(j=1; j<wu[i]; j++){
				dpp2[i][j+1]+=dp2[i][j];
				if(dpp2[i][j+1]>=mod) dpp2[i][j+1]-=mod;
			}
			dpp[i]=0;
			for(j=1; j<=wu[i]; j++){
				//if(j>len[i]) break;
				dpp[i]+=dpp2[i][j]*C[i][j];
				//if(dpp[i]>=mod) dpp[i]-=mod;
				dpp[i]%=mod;
			}
		}
		for(i=1; i<=li; i++){
			dp[i]=dpp[i];
			for(j=0; j<=a+2; j++){
				dp2[i][j]=dpp2[i][j];
			}
		}
/*		for(i=1; i<=li; i++) cout<<dp[i]<<" ";
		cout<<endl;*/
	}
	//cout<<dp2[2][1]<<endl;
	
	pas=0;
	for(i=1; i<=li; i++){
		pas+=dp[i];
		if(pas>=mod) pas-=mod;
	}
	cout<<pas;
	return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct

Subtask #2
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Runtime error	25 ms	25356 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	5068 KB	Output is correct
2	Correct	29 ms	5168 KB	Output is correct
3	Correct	30 ms	5144 KB	Output is correct
4	Correct	32 ms	5068 KB	Output is correct
5	Correct	29 ms	5068 KB	Output is correct
6	Correct	33 ms	5068 KB	Output is correct
7	Correct	34 ms	5144 KB	Output is correct
8	Correct	33 ms	5064 KB	Output is correct
9	Correct	33 ms	5068 KB	Output is correct
10	Correct	33 ms	5164 KB	Output is correct
11	Correct	28 ms	5076 KB	Output is correct
12	Correct	26 ms	5112 KB	Output is correct
13	Correct	27 ms	5068 KB	Output is correct
14	Correct	29 ms	5156 KB	Output is correct
15	Correct	27 ms	5148 KB	Output is correct
16	Correct	11 ms	2448 KB	Output is correct
17	Correct	11 ms	2380 KB	Output is correct
18	Correct	11 ms	2380 KB	Output is correct
19	Correct	10 ms	2380 KB	Output is correct
20	Correct	11 ms	2536 KB	Output is correct

Subtask #4
0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	1 ms	332 KB	Output is correct
18	Correct	1 ms	332 KB	Output is correct
19	Correct	1 ms	332 KB	Output is correct
20	Correct	1 ms	332 KB	Output is correct
21	Runtime error	25 ms	25356 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Submission #389081

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0