답안 #43372 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43372	2018-03-15T04:43:14 Z	top34051	Boat (APIO16_boat)	C++14	36 / 100	2000 ms	14752 KB

boat

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define X first
#define Y second

const int maxn = 2e3 + 5;
const ll mod = 1e9 + 7;

int n,m;
int a[maxn], b[maxn];

vector<int> pos;
pii itv[maxn];
ll rec[maxn][maxn];

ll dp[maxn][maxn];

ll fac[maxn], invfac[maxn];

ll add(ll x, ll y) { return ((x+y)%mod + mod)%mod; }

ll mul(ll x, ll y) { return ((x*y)%mod + mod)%mod; }

ll inv(ll x, ll y) { return 1<x ? y - inv(y%x, x)*y/x : 1; }

ll combi1(ll x, ll y) {
    return x<y ? 0 : mul(fac[x], mul(invfac[y], invfac[x-y]));
}

ll combi2(ll x, ll y) {
    if(x<y) return 0;
    ll res = invfac[y];
    for(ll i=x-y+1;i<=x;i++) res = mul(res, i);
//    printf("combi %lld %lld : %lld\n",x,y,res);
    return res;
}

void init() {
	//get interval
	for(int i=1;i<=n;i++) {
		pos.push_back(a[i]);
		pos.push_back(b[i]+1);
	}
	sort(pos.begin(),pos.end());
	pos.erase(unique(pos.begin(),pos.end()),pos.end());
	for(int i=0;i<pos.size()-1;i++) itv[++m] = {pos[i],pos[i+1]-1};
//	for(int i=1;i<=m;i++) printf("[%d, %d] ",itv[i].X,itv[i].Y);
//	printf("\n");
	//fac and invfac
	fac[0] = 1; invfac[0] = inv(fac[0], mod);
//    printf("fac %d = %lld inv = %lld\n",1,fac[1],invfac[1]);
	for(int i=1;i<=m;i++) {
		fac[i] = mul(fac[i-1], i);
		invfac[i] = inv(fac[i], mod);
//		printf("fac %d = %lld inv = %lld\n",i,fac[i],invfac[i]);
	}
	//precompute
	for(int i=1;i<=m;i++) {
        ll sz = itv[i].Y-itv[i].X+1;
        for(int use=1;use<=n;use++) rec[i][use] = combi2(sz,use);
	}
}

ll solve() {
    ll res = 0;
	for(int i=0;i<=m;i++) dp[0][i] = 1;
	for(int x=1;x<=n;x++) {
		for(int i=1;i<=m;i++) {
			dp[x][i] = dp[x][i-1];
			if(a[x]<=itv[i].X && itv[i].Y<=b[x]) {
				ll cnt = 1;
				ll sz = itv[i].Y-itv[i].X+1;
				for(int y=x-1;y>=0;y--) {
					ll sum = 0;
					for(int use=1;use<=cnt;use++) sum = add(sum, mul(rec[i][use], combi1(cnt-1,use-1)));
//					printf("------- x = %d i = %d : y = %d    =>   %lld\n",x,i,y,sum);
					dp[x][i] = add(dp[x][i], mul(dp[y][i-1], sum));
					if(a[y]<=itv[i].X && itv[i].Y<=b[y]) cnt++;
				}
			}
//			printf("dp %d %d = %lld\n",x,i,dp[x][i]);
		}
		res = add(res, dp[x][m]);
	}
	return res;
}

int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
	init();
	printf("%lld",solve());
}

Compilation message

boat.cpp: In function 'void init()':
boat.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size()-1;i++) itv[++m] = {pos[i],pos[i+1]-1};
               ^
boat.cpp: In function 'long long int solve()':
boat.cpp:75:8: warning: unused variable 'sz' [-Wunused-variable]
     ll sz = itv[i].Y-itv[i].X+1;
        ^
boat.cpp: In function 'int main()':
boat.cpp:92:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
boat.cpp:93:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
                                                 ^

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	744 ms	14348 KB	Output is correct
2	Correct	739 ms	14348 KB	Output is correct
3	Correct	738 ms	14476 KB	Output is correct
4	Correct	749 ms	14496 KB	Output is correct
5	Correct	737 ms	14564 KB	Output is correct
6	Correct	744 ms	14564 KB	Output is correct
7	Correct	734 ms	14612 KB	Output is correct
8	Correct	736 ms	14644 KB	Output is correct
9	Correct	737 ms	14644 KB	Output is correct
10	Correct	732 ms	14644 KB	Output is correct
11	Correct	738 ms	14752 KB	Output is correct
12	Correct	736 ms	14752 KB	Output is correct
13	Correct	732 ms	14752 KB	Output is correct
14	Correct	733 ms	14752 KB	Output is correct
15	Correct	733 ms	14752 KB	Output is correct
16	Correct	143 ms	14752 KB	Output is correct
17	Correct	155 ms	14752 KB	Output is correct
18	Correct	148 ms	14752 KB	Output is correct
19	Correct	155 ms	14752 KB	Output is correct
20	Correct	161 ms	14752 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	744 ms	14348 KB	Output is correct
2	Correct	739 ms	14348 KB	Output is correct
3	Correct	738 ms	14476 KB	Output is correct
4	Correct	749 ms	14496 KB	Output is correct
5	Correct	737 ms	14564 KB	Output is correct
6	Correct	744 ms	14564 KB	Output is correct
7	Correct	734 ms	14612 KB	Output is correct
8	Correct	736 ms	14644 KB	Output is correct
9	Correct	737 ms	14644 KB	Output is correct
10	Correct	732 ms	14644 KB	Output is correct
11	Correct	738 ms	14752 KB	Output is correct
12	Correct	736 ms	14752 KB	Output is correct
13	Correct	732 ms	14752 KB	Output is correct
14	Correct	733 ms	14752 KB	Output is correct
15	Correct	733 ms	14752 KB	Output is correct
16	Correct	143 ms	14752 KB	Output is correct
17	Correct	155 ms	14752 KB	Output is correct
18	Correct	148 ms	14752 KB	Output is correct
19	Correct	155 ms	14752 KB	Output is correct
20	Correct	161 ms	14752 KB	Output is correct
21	Execution timed out	2033 ms	14752 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	150 ms	14752 KB	Output is correct
2	Correct	105 ms	14752 KB	Output is correct
3	Correct	134 ms	14752 KB	Output is correct
4	Correct	150 ms	14752 KB	Output is correct
5	Correct	167 ms	14752 KB	Output is correct
6	Correct	352 ms	14752 KB	Output is correct
7	Correct	340 ms	14752 KB	Output is correct
8	Correct	362 ms	14752 KB	Output is correct
9	Correct	364 ms	14752 KB	Output is correct
10	Correct	352 ms	14752 KB	Output is correct
11	Correct	159 ms	14752 KB	Output is correct
12	Correct	109 ms	14752 KB	Output is correct
13	Correct	111 ms	14752 KB	Output is correct
14	Correct	119 ms	14752 KB	Output is correct
15	Correct	144 ms	14752 KB	Output is correct
16	Correct	90 ms	14752 KB	Output is correct
17	Correct	75 ms	14752 KB	Output is correct
18	Correct	86 ms	14752 KB	Output is correct
19	Correct	78 ms	14752 KB	Output is correct
20	Correct	97 ms	14752 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	744 ms	14348 KB	Output is correct
2	Correct	739 ms	14348 KB	Output is correct
3	Correct	738 ms	14476 KB	Output is correct
4	Correct	749 ms	14496 KB	Output is correct
5	Correct	737 ms	14564 KB	Output is correct
6	Correct	744 ms	14564 KB	Output is correct
7	Correct	734 ms	14612 KB	Output is correct
8	Correct	736 ms	14644 KB	Output is correct
9	Correct	737 ms	14644 KB	Output is correct
10	Correct	732 ms	14644 KB	Output is correct
11	Correct	738 ms	14752 KB	Output is correct
12	Correct	736 ms	14752 KB	Output is correct
13	Correct	732 ms	14752 KB	Output is correct
14	Correct	733 ms	14752 KB	Output is correct
15	Correct	733 ms	14752 KB	Output is correct
16	Correct	143 ms	14752 KB	Output is correct
17	Correct	155 ms	14752 KB	Output is correct
18	Correct	148 ms	14752 KB	Output is correct
19	Correct	155 ms	14752 KB	Output is correct
20	Correct	161 ms	14752 KB	Output is correct
21	Execution timed out	2033 ms	14752 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #43372

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