Submission #792835

#	Time	Username	Problem	Language	Result	Execution time	Memory
792835		IvanJ	Boat (APIO16_boat)	C++17	0 / 100	10 ms	16340 KiB

boat

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 505;
const int MOD = 1e9 + 7;

int add(int x, int y) {x += y;if(x >= MOD) x -= MOD;return x;}
int sub(int x, int y) {x -= y;if(x < 0) x += MOD;return x;}

int n;
int a[maxn], b[maxn];

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d%d", a + i, b + i);
	
	vector<int> dp(1e6 + 1, 0), pref(1e6 + 1, 0);
	int maxi = 0;
	for(int i = 0;i < n;i++) {
		maxi = max(maxi, b[i]);
		for(int j = a[i];j <= b[i];j++) {
			if(i == 0) dp[j] = 1;
			else {
				if(j - 1 >= a[i - 1]) {
					int sum = pref[j - 1];
					dp[j] = add(dp[j], sum);
				}
			}
		}
		if(i == 0) dp[0] = 1;
		
		//for(int j = 0;j <= maxi;j++) cout << dp[j] << " ";
		//cout << "\n";
		
		pref[0] = dp[0];
		for(int j = 1;j <= maxi;j++) 
			pref[j] = add(pref[j - 1], dp[j]);
	}
	printf("%d\n", sub(pref[maxi], (n > 1) ? dp[0] : 0));
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
boat.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d%d", a + i, b + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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