Submission #23225

#	Time	Username	Problem	Language	Result	Execution time	Memory
23225		14kg	Boat (APIO16_boat)	C++11	9 / 100	1189 ms	7940 KiB

boat

#include <stdio.h>
#include <map>
#include <set>
#include <algorithm>
#define MOD 1000000007
#define min2(x,y) (x<y?x:y)

using namespace std;
int n, w_len;
long long d[501][1503];
bool check[501][1503];
pair<int, int> r[501], w[1503];
set<int> S;
map<int,int> M;

long long f(int lev, int y) {
	if (lev == 0) return 1;
	if (!check[lev][y]) {
		check[lev][y] = true, d[lev][y] = f(lev - 1, y);
		for (int i = r[lev].first; i <= min2(r[lev].second, y); i++) {
			long long temp = f(lev - 1, i - 1), temp2 = w[i].second - w[i].first + 1;
			temp = (temp*temp2);
			d[lev][y] = (d[lev][y] + temp) % MOD;
		}
	} return d[lev][y];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &r[i].first, &r[i].second);
		S.insert(r[i].first), S.insert(r[i].second);
	}

	auto it1 = S.begin(), it2 = it1;
	
	it2++, w[++w_len] = { 0,*it1 - 1 };
	while (it2 != S.end()) {
		M[*it1] = ++w_len, w[w_len] = { *it1,*it1 };
		if (*it1 + 1 <= *it2 - 1) w[++w_len] = { *it1 + 1,*it2 - 1 };
		it1++, it2++;
	} M[*it1] = ++w_len, w[w_len] = { *it1,*it1 };

	for (int i = 1; i <= n; i++) {
		r[i].first = M[r[i].first];
		r[i].second = M[r[i].second];
	}

	long long res = f(n, w_len);
	printf("%lld", res ? res - 1 : MOD- 1);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
boat.cpp:30:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &r[i].first, &r[i].second);
                                            ^

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