Submission #63238

#	Time	Username	Problem	Language	Result	Execution time	Memory
63238		kingpig9	Boat (APIO16_boat)	C++11	100 / 100	749 ms	5364 KiB

boat

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2018, MOD = 1e9 + 7;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

inline void addeq (int &x, int y) {
	x += y;
	if (x >= MOD) {
		x -= MOD;
	}
}

inline int add (int x, int y) {
	addeq(x, y);
	return x;
}

inline int subtr (int x, int y) {
	x -= y;
	if (x < 0) {
		x += MOD;
	}
	return x;
}

inline int mult (int x, int y) {
	return ll(x) * y % MOD;
}

inline void multeq (int &x, int y) {
	x = mult(x, y);
}

int N;
int A[MAXN], B[MAXN];
int inda[MAXN], indb[MAXN];
vector<int> vals;
int len[MAXN];
int dp[MAXN][MAXN];	//dp[position][Where is your thing?]
int pdp[MAXN][MAXN];
int inv[MAXN];

int main() {
	//precomputation
	inv[1] = 1;
	for (int i = 2; i < MAXN; i++) {
		inv[i] = mult(inv[MOD % i], MOD - MOD / i);
	}

	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &A[i], &B[i]);
		B[i]++;
		vals.push_back(A[i]);
		vals.push_back(B[i]);
	}

	sort(all(vals));
	vals.resize(unique(all(vals)) - vals.begin());
	for (int i = 1; i <= N; i++) {
		A[i] = lower_bound(all(vals), A[i]) - vals.begin();
		B[i] = lower_bound(all(vals), B[i]) - vals.begin();
	}
	for (int i = 1; i < vals.size(); i++) {
		len[i] = vals[i] - vals[i - 1];
	}

	for (int i = 0; i < vals.size(); i++) {
		dp[0][i] = 1;
	}

	for (int i = 0; i < vals.size(); i++) {
		dp[0][i] = 1;
	}

	for (int i = 1; i <= N; i++) {
		for (int j = A[i] + 1; j <= B[i]; j++) {
			dp[i][j] = mult(len[j], dp[i - 1][j - 1]);
			int cho = len[j] - 1;
			int npos = 1;
			for (int k = i - 1; k >= 1; k--) {
				if (A[k] + 1 <= j && j <= B[k]) {
					npos++;
					multeq(cho, mult(len[j] + npos - 2, inv[npos]));	//did thru examples...not as clear at first, but you will understand.
					addeq(dp[i][j], mult(cho, dp[k - 1][j - 1]));
				}
			}
		}

		dp[i][0] = 1;
		for (int j = 1; j < vals.size(); j++) {
			addeq(dp[i][j], subtr(add(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]));
		}
	}
	printf("%d\n", subtr(dp[N][vals.size() - 1], 1));
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < vals.size(); i++) {
                  ~~^~~~~~~~~~~~~
boat.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vals.size(); i++) {
                  ~~^~~~~~~~~~~~~
boat.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vals.size(); i++) {
                  ~~^~~~~~~~~~~~~
boat.cpp:101:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < vals.size(); j++) {
                   ~~^~~~~~~~~~~~~
boat.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:62: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: 42 / 42