Submission #25559

#	Time	Username	Problem	Language	Result	Execution time	Memory
25559		kajebiii	Boat (APIO16_boat)	C++14	100 / 100	1799 ms	8128 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 5e2 + 10, MAX_C = MAX_N * 2, MOD = 1e9 + 7;

int N, Nr[MAX_N][2], Dy[2][MAX_C][MAX_N], Sum[MAX_C];
vector<int> Co;
void add(int &a, int b) {
	if((a+=b) >= MOD) a -= MOD;
	if(a<0) a += MOD;
}
int pow(int a, int b) {
	int r = 1, p = a;
	while(b) {
		if(b&1) r = 1ll * r * p % MOD;
		p = 1ll * p * p % MOD;
		b >>= 1;
	}
	return r;
}
int Calc[MAX_C][MAX_N];
int main() {
	cin >> N; 
	REPO(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Nr[i][j] += j, Co.push_back(Nr[i][j]);
	Co.push_back(0);
	sort(ALL(Co)); Co.erase(unique(ALL(Co)), Co.end());
	REPO(i, N) REP(j, 2) Nr[i][j] = lower_bound(ALL(Co), Nr[i][j]) - Co.begin();

	int cN = SZ(Co);
	for(int i=0; i+1<cN; i++) {
		Calc[i][0] = 1;
		int v = Co[i+1] - Co[i];
		for(int j=1; j<=N; j++)
			Calc[i][j] = 1ll * Calc[i][j-1] * (v-j+1) % MOD * pow(j, MOD-2) % MOD;
	}
	Dy[0][0][0] = Dy[0][0][1] = 1;
	REPO(i, N) {
		int n = i&1, o = 1-n;
		for(int j=0; j<Nr[i][1]-1; j++) {
			if(j) Sum[j] = Sum[j-1]; else Sum[j] = 0;
			Sum[j] = (Sum[j] + Dy[o][j][0]) % MOD;
		}
		for(int k=0; k<=i; k++) for(int j=0; j<cN; j++) Dy[n][j][k] = Dy[o][j][k];
		for(int j=Nr[i][0]; j<Nr[i][1]; j++) {
			for(int k=i; k>=1; k--) {
				add(Dy[n][j][k+1], Dy[n][j][k]);
				add(Dy[n][j][0], 1ll * Dy[n][j][k] * Calc[j][k+1] % MOD);
			}
			add(Dy[n][j][1], Sum[j-1]);
			add(Dy[n][j][0], 1ll * Sum[j-1] * Calc[j][1] % MOD);
		}
		/*
		for(int j=0; j+1<cN; j++) {
			printf("[%d ~ %d]\n", Co[j], Co[j+1]);
			for(int k=0; k<=i; k++) printf("%d ", Dy[n][j][k]); puts("");
		}
		*/
	}
	int ans = 0;
	for(int j=1; j<cN; j++) add(ans, Dy[N&1][j][0]);
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:36:84: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REPO(i, N) REP(j, 2) scanf("%d", &Nr[i][j]), Nr[i][j] += j, Co.push_back(Nr[i][j]);
                                                                                    ^

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