Submission #52370

#	Time	Username	Problem	Language	Result	Execution time	Memory
52370		pzdba	Boat (APIO16_boat)	C++14	0 / 100	8 ms	2296 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;

int a[505], b[505];

map<int, int> ht;
map<int, int>::iterator its;
int rev[1005];

int dp[505][1005];

int main(){
	int n;
	scanf("%d", &n);
	for(int i=1;i<=n;i++){
		scanf("%d%d", &a[i], &b[i]);
		ht[a[i]] = 1;
		ht[b[i]] = 1;
	}
	int hv = 1;
	for(its = ht.begin();its != ht.end();its++) its->second = hv++, rev[hv-1] = its->first;
	for(int i=1;i<=n;i++) a[i] = ht[a[i]], b[i] = ht[b[i]];
	for(int i=1;i<=n;i++){
		if(i == 1){
			dp[i][0] = 1;
			for(int j=a[i];j<=b[i];j++){
				if(j == a[i]) dp[i][j] = 1;
				else dp[i][j] = (rev[j] - rev[j-1])%mod;
			}
		}
		else{
			dp[i][0] = dp[i-1][0]+1;
			for(int j=a[i];j<=b[i];j++){
				int c = 0;
				if(j == 1) c = 1;
				else c = rev[j]-rev[j-1];
				dp[i][j] = (dp[i][j] + 1)%mod;
				for(int k=0;k<=j-1;k++){
					dp[i][j] = (dp[i][j] + (LL)dp[i-1][k]*c)%mod;
				}
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=2*n;i++){
		ans = (ans + dp[n][i])%mod;
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

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

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