제출 #43359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43359		top34051	Boat (APIO16_boat)	C++14	36 / 100	2036 ms	16108 KiB

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());
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 0 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42