Submission #107864

#	Time	Username	Problem	Language	Result	Execution time	Memory
107864		Just_Solve_The_Problem	Boat (APIO16_boat)	C++11	0 / 100	3 ms	384 KiB

boat

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)507;
const int mod = (int)1e9 + 7; 

int add(int a, int b) {
	return (a + b) % mod;
}

int mul(int a, int b) {
	return (a * 1LL * b) % mod;
}

int n;
vector<int> L, R;
int dp[N];
int pref[2][N];

main() {
	scanf("%d", &n);
	L.resize(n);
	R.resize(n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &L[i], &R[i]);
	}
	memset(pref, 0, sizeof(pref));
	memset(dp, 0, sizeof(dp));
	ll ans = 0;
	for (int j = 1; j < N; j++) {
		if (L[0] <= j && j <= R[0]) {
			pref[0][j] = 1;
		}
		pref[0][j] += pref[0][j - 1];
	}
	for (int i = 1; i < n; i++) {
		for (int j = 1; j < N; j++) {
			if (L[i] <= j && j <= R[i]) {
				pref[i & 1][j] += pref[(i & 1) ^ 1][j - 1];
				if (pref[i & 1][j] >= mod) pref[i & 1][j] -= mod;
				dp[j] = pref[i & 1][j];
			}
			pref[i & 1][j] += pref[i & 1][j - 1];
			pref[(i & 1) ^ 1][j - 1] = 0;
		}
		pref[(i & 1) ^ 1][N - 1] = 0;
	}
	for (int i = L[n - 1]; i <= R[n - 1]; i++) {
		ans += dp[i];
		if (ans >= mod) ans -= mod;
	}
	cout << ans;
}

Compilation message (stderr)

boat.cpp:23:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
boat.cpp: In function 'int main()':
boat.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
boat.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &L[i], &R[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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