Submission #792894

#	Time	Username	Problem	Language	Result	Execution time	Memory
792894		IvanJ	Boat (APIO16_boat)	C++17	9 / 100	4 ms	340 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 mult(ll x, ll y) {return x * y % MOD;}
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, m;
int a[maxn], b[maxn];
int dp[maxn * 3], pref[maxn * 3], sum[maxn * 3];

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d%d", a + i, b + i);
	
	set<int> s;
	s.insert(0);
	for(int i = 0;i < n;i++) 
		s.insert(a[i]), s.insert(b[i]), s.insert(b[i] + 1);
	
	vector<int> v(all(s));
	m = v.size();
	dp[0] = sum[0] = 1;
	for(int i = 0;i < m;i++) 
		pref[i] = 1;
	
	for(int i = 0;i < n;i++) {
		int lo = 0, hi = 0;
		for(int j = 0;j < m;j++) {
			if(v[j] == a[i]) lo = j;
			if(v[j] == b[i]) hi = j;
		}
		
		for(int j = hi;j >= lo;j--) {
			sum[j] = add(sum[j], mult(pref[j - 1], v[j + 1] - v[j]));
			dp[j] = add(dp[j], pref[j - 1]);
		}
	
		for(int j = 0;j < m;j++) {
			pref[j] = sum[j];
			if(j) pref[j] = add(pref[j], pref[j - 1]);
		}
	}
	printf("%d\n", sub(pref[m - 1], 1));
	return 0;
}

Compilation message (stderr)

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

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