답안 #43359 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43359	2018-03-14T17:38:04 Z	top34051	Boat (APIO16_boat)	C++14	36 / 100	2000 ms	16108 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
	pos.push_back(0); pos.push_back(2e9);
	for(int i=1;i<=n;i++) {
		pos.push_back(a[i]);
		pos.push_back(b[i]);
	}
	sort(pos.begin(),pos.end());
	pos.erase(unique(pos.begin(),pos.end()),pos.end());
	for(int i=0;i<pos.size();i++) {
		if(i!=0 && pos[i-1]+1<=pos[i]-1) itv[++m] = {pos[i-1]+1,pos[i]-1};
		itv[++m] = {pos[i],pos[i]};
	}
//	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=1;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:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size();i++) {
               ^
boat.cpp: In function 'long long int solve()':
boat.cpp:79:8: warning: unused variable 'sz' [-Wunused-variable]
     ll sz = itv[i].Y-itv[i].X+1;
        ^
boat.cpp: In function 'int main()':
boat.cpp:96:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
boat.cpp:97: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	741 ms	14296 KB	Output is correct
2	Correct	739 ms	14408 KB	Output is correct
3	Correct	739 ms	14408 KB	Output is correct
4	Correct	738 ms	14432 KB	Output is correct
5	Correct	738 ms	14672 KB	Output is correct
6	Correct	740 ms	14672 KB	Output is correct
7	Correct	738 ms	14672 KB	Output is correct
8	Correct	741 ms	14672 KB	Output is correct
9	Correct	736 ms	14736 KB	Output is correct
10	Correct	740 ms	14736 KB	Output is correct
11	Correct	739 ms	14736 KB	Output is correct
12	Correct	740 ms	14736 KB	Output is correct
13	Correct	737 ms	14736 KB	Output is correct
14	Correct	741 ms	14736 KB	Output is correct
15	Correct	736 ms	14736 KB	Output is correct
16	Correct	146 ms	14736 KB	Output is correct
17	Correct	158 ms	14736 KB	Output is correct
18	Correct	152 ms	14736 KB	Output is correct
19	Correct	158 ms	14736 KB	Output is correct
20	Correct	154 ms	14736 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	741 ms	14296 KB	Output is correct
2	Correct	739 ms	14408 KB	Output is correct
3	Correct	739 ms	14408 KB	Output is correct
4	Correct	738 ms	14432 KB	Output is correct
5	Correct	738 ms	14672 KB	Output is correct
6	Correct	740 ms	14672 KB	Output is correct
7	Correct	738 ms	14672 KB	Output is correct
8	Correct	741 ms	14672 KB	Output is correct
9	Correct	736 ms	14736 KB	Output is correct
10	Correct	740 ms	14736 KB	Output is correct
11	Correct	739 ms	14736 KB	Output is correct
12	Correct	740 ms	14736 KB	Output is correct
13	Correct	737 ms	14736 KB	Output is correct
14	Correct	741 ms	14736 KB	Output is correct
15	Correct	736 ms	14736 KB	Output is correct
16	Correct	146 ms	14736 KB	Output is correct
17	Correct	158 ms	14736 KB	Output is correct
18	Correct	152 ms	14736 KB	Output is correct
19	Correct	158 ms	14736 KB	Output is correct
20	Correct	154 ms	14736 KB	Output is correct
21	Execution timed out	2036 ms	16108 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	268 ms	16108 KB	Output is correct
2	Correct	203 ms	16108 KB	Output is correct
3	Correct	250 ms	16108 KB	Output is correct
4	Correct	304 ms	16108 KB	Output is correct
5	Correct	328 ms	16108 KB	Output is correct
6	Correct	702 ms	16108 KB	Output is correct
7	Correct	715 ms	16108 KB	Output is correct
8	Correct	670 ms	16108 KB	Output is correct
9	Correct	697 ms	16108 KB	Output is correct
10	Correct	698 ms	16108 KB	Output is correct
11	Correct	287 ms	16108 KB	Output is correct
12	Correct	189 ms	16108 KB	Output is correct
13	Correct	212 ms	16108 KB	Output is correct
14	Correct	228 ms	16108 KB	Output is correct
15	Correct	277 ms	16108 KB	Output is correct
16	Correct	130 ms	16108 KB	Output is correct
17	Correct	108 ms	16108 KB	Output is correct
18	Correct	127 ms	16108 KB	Output is correct
19	Correct	102 ms	16108 KB	Output is correct
20	Correct	149 ms	16108 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	741 ms	14296 KB	Output is correct
2	Correct	739 ms	14408 KB	Output is correct
3	Correct	739 ms	14408 KB	Output is correct
4	Correct	738 ms	14432 KB	Output is correct
5	Correct	738 ms	14672 KB	Output is correct
6	Correct	740 ms	14672 KB	Output is correct
7	Correct	738 ms	14672 KB	Output is correct
8	Correct	741 ms	14672 KB	Output is correct
9	Correct	736 ms	14736 KB	Output is correct
10	Correct	740 ms	14736 KB	Output is correct
11	Correct	739 ms	14736 KB	Output is correct
12	Correct	740 ms	14736 KB	Output is correct
13	Correct	737 ms	14736 KB	Output is correct
14	Correct	741 ms	14736 KB	Output is correct
15	Correct	736 ms	14736 KB	Output is correct
16	Correct	146 ms	14736 KB	Output is correct
17	Correct	158 ms	14736 KB	Output is correct
18	Correct	152 ms	14736 KB	Output is correct
19	Correct	158 ms	14736 KB	Output is correct
20	Correct	154 ms	14736 KB	Output is correct
21	Execution timed out	2036 ms	16108 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #43359

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