Submission #110596

#	Time	Username	Problem	Language	Result	Execution time	Memory
110596		Pro_ktmr	Boat (APIO16_boat)	C++14	58 / 100	2037 ms	12420 KiB

boat

#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair

const LL MOD = 1000000007;

//累乗 O(log N)
long long power(long long x, int N){
	if(N == 1) return x;
	long long tmp = power(x, N/2);
	if(N%2 == 0) return tmp * tmp % MOD;
	else return tmp * tmp % MOD * x % MOD;
}

//逆元 O(log x)
long long inverse(long long x){
	return power(x, MOD-2);
}

//コンビネーション
struct Combination{
private:
	int N;
	vector<long long> fact, inv;
public:
	void init(int n){ //初期化する O(N)
		N = n;
		fact.push_back(1);
		inv.push_back(1);
		for(long long i=1; i<=N; i++){
			fact.push_back(fact.back()*i%MOD);
			inv.push_back(inverse(fact.back()));
		}
	}
	long long comb(int n, int k){ //nCkを求める O(1)
		return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
	}
};

Combination comb;

int N, a[500], b[500], A[500], B[500];
vector<int> v;
vector<int> ls[1000];

LL memo[1000][501];
LL culc(LL range, int num){
	if(num == 1) return range;
	LL ret = 0;
	LL tmp1 = range;
	LL tmp2 = range-1;
	for(int i=0; i<=num-2; i++){ //中のを何個使うか
		if(tmp2 == 0) break;
		tmp1 = tmp1 * tmp2 % MOD;
		tmp1 = tmp1 * inverse(i+2) % MOD;
		tmp2--;
		ret += tmp1 * comb.comb(num-2, i) % MOD;
	}
	return ret % MOD;
}

//a:=区間、b:=学校
LL dp[1000][500][2];
LL solve(int a, int b, int ok){
	if(a == v.size()-1) return 1;
	if(ok == 0 && b == N) return 0;
	if(ok == 1 && b == N) return 1;
	if(dp[a][b][ok] != -1) return dp[a][b][ok];
	if(ok == 0){
		dp[a][b][ok] = solve(a, b+1, 0);
		if(A[b] <= a && a < B[b]){
			int idx = lower_bound(ls[a].begin(), ls[a].end(), b) - ls[a].begin();
			for(int i=idx; i<ls[a].size()-1; i++){
				dp[a][b][ok] += memo[a][i-idx+1]*solve(a+1, ls[a][i]+1, 1);
				dp[a][b][ok] %= MOD;
			}
		}
	}
	else{
		dp[a][b][ok] = solve(a+1, b, 1);
		dp[a][b][ok] += solve(a, b, 0);
		dp[a][b][ok] %= MOD;
	}
	return dp[a][b][ok];
}

int main(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", a+i, b+i);
		b[i]++;
		v.PB(a[i]);
		v.PB(b[i]);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	for(int i=0; i<N; i++){
		A[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
		B[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
		for(int j=A[i]; j<B[i]; j++) ls[j].PB(i);
	}
	comb.init(N);
	for(int i=0; i<v.size(); i++){
		ls[i].PB(N);
		for(int j=0; j<N; j++) dp[i][j][0] = -1;
		for(int j=0; j<N; j++) dp[i][j][1] = -1;
		if(i != v.size()-1) for(int j=1; j<=ls[i].size(); j++) memo[i][j] = culc(v[i+1]-v[i], j);
	}
	printf("%d\n", (solve(0, 0, 1)-1+MOD)%MOD);
}

Compilation message (stderr)

boat.cpp: In function 'long long int solve(int, int, int)':
boat.cpp:67:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(a == v.size()-1) return 1;
     ~~^~~~~~~~~~~~~
boat.cpp:75:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=idx; i<ls[a].size()-1; i++){
                   ~^~~~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
boat.cpp:109:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i != v.size()-1) for(int j=1; j<=ls[i].size(); j++) memo[i][j] = culc(v[i+1]-v[i], j);
      ~~^~~~~~~~~~~~~
boat.cpp:109:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i != v.size()-1) for(int j=1; j<=ls[i].size(); j++) memo[i][j] = culc(v[i+1]-v[i], j);
                                    ~^~~~~~~~~~~~~~
boat.cpp:111:43: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  printf("%d\n", (solve(0, 0, 1)-1+MOD)%MOD);
                 ~~~~~~~~~~~~~~~~~~~~~~~~~~^
boat.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", a+i, b+i);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42