Submission #40882

#	Time	Username	Problem	Language	Result	Execution time	Memory
40882		gabrielsimoes	Boat (APIO16_boat)	C++14	31 / 100	1939 ms	8516 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
const int MAXN = 510;

int n;
int va[MAXN], vb[MAXN];
vector<ll> dp[MAXN];

int main() {
	va[0] = vb[0] = 0;
	dp[0].push_back(1);

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &va[i], &vb[i]);
		dp[i].resize(vb[i] - va[i] + 1);
	}

	ll ans = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < dp[i].size(); j++) {
			if (j > 0) {
				dp[i][j] += dp[i][j-1];
			}

			if (i > 0) {
				ans += dp[i][j];
				ans %= MOD;
			}

			ll cur = va[i] + j;

			for (int k = i+1; k <= n; k++) {
				if (cur < vb[k]) {
					int pos = max(cur - va[k] + 1, 0LL);
					dp[k][pos] += dp[i][j];
					dp[k][pos] %= MOD;
				}
			}
		}
	}

	printf("%lld\n", ans);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < dp[i].size(); j++) {
                     ^
boat.cpp:16:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
boat.cpp:18:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &va[i], &vb[i]);
                                 ^

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