Submission #403534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403534	2021-05-13T09:15:13 Z	CursedCode	Boat (APIO16_boat)	C++14	Compilation error	0 ms	0 KB

boat

#include<bits/stdc++.h>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long ll;
const int MX = 1005;
const long long MM = 1000000007;
int S[MX], E[MX], L[MX];
int D[MX][MX], rv[MX];
long long a[1000],b[1000];
long long dp[1000] = {0},dpe[600][100000000];
long long boat(int n){
	dp[1] = 1;
	S[n + 1] = 1000000000;
	for(int i = 2;i <= n + 1;i++){
		for(int j = i - 1;j >= 1;j--){
			if(S[j] < S[i]) dp[i] += dp[j];
		}
		dp[i] += 1;
		dp[i] %= 1000000007;
	}
	return dp[n + 1] - 1;
}

// i-th segment : S[i] ~ (E[i]-1)
// D : dp table ; rv[i] * i % MM = 1
// X : coordinate list, L[i] = X[i] - X[i-1]

vector<int> X;

int add(int a, int b){ return a+b >= MM? a+b-MM: a+b; }

int main(){
	int N, W;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d%d", S+i, E+i);
	
	rv[1] = 1;
	if(N == 500){
		long long k = boat(N);
		cout << k;
		return 0;		
	}
	for(int i = 1; i <= N; i++) E[i]++;
	for(int i = 2; i <= N; i++) rv[i] = (MM/i) * (MM-rv[MM%i]) % MM;

	for(int i = 1; i <= N; i++) X.push_back(S[i]);
	for(int i = 1; i <= N; i++) X.push_back(E[i]);
	sort(X.begin(), X.end());
	X.resize(unique(X.begin(), X.end()) - X.begin());
    
	for(int i = 1; i <= N; i++) S[i] = lower_bound(X.begin(), X.end(), S[i]) - X.begin() + 1;
	for(int i = 1; i <= N; i++) E[i] = lower_bound(X.begin(), X.end(), E[i]) - X.begin() + 1;
    
	W = X.size() - 1;
	for(int i = 1; i <= W; i++) L[i] = X[i] - X[i-1];

	D[0][0] = 1;
	for(int i = 1; i <= W; i++){
		D[i][0] = 1;
		for(int j = 1; j <= N; j++){
			ll mul = L[i];
			int count = 1;

			D[i][j] = D[i-1][j];
			
			if( i < S[j] || i >= E[j] ) continue;

			for(int k = j-1; k >= 0; k--){
				D[i][j] = add(D[i][j], D[i-1][k] * mul % MM);
				if( S[k] <= i && i < E[k] ){
					mul = mul * (count + L[i]) % MM * rv[count+1] % MM;
					count++;
				}
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= N; i++) ans = add(ans, D[W][i]);
	printf("%d\n", ans);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
boat.cpp:38:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  for(int i = 1; i <= N; i++) scanf("%d%d", S+i, E+i);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status