Submission #403502

#	Time	Username	Problem	Language	Result	Execution time	Memory
403502		CursedCode	Boat (APIO16_boat)	C++14	9 / 100	2069 ms	380 KiB

boat

#include<bits/stdc++.h>

using namespace std;
long long a[1000],b[1000];
long long dp[1000] = {0},dpe[200][200] = {0};
long long boat(int n){
	dp[1] = 1;
	a[n + 1] = 1000000000;
	for(int i = 2;i <= n + 1;i++){
		for(int j = i - 1;j >= 1;j--){
			if(a[j] < a[i]) dp[i] += dp[j];
		}
		dp[i] += 1;
		dp[i] %= 1000000007;
	}
	return dp[n + 1] - 1;
}
void notboat(int n){
	for(int i = 2;i <= n;i++){
		for(long long k = a[i];k <= b[i];k++){
			for(int j = i - 1;j >= 1;j--){
				for(long long pl = a[j];pl <= b[j];pl++){
					if(pl < k) dpe[i][k] += dpe[j][pl];
				}
			}
			dpe[i][k] %= 1000000007;
		}
	}
}
int main(){
	int n;
	cin >> n;
	int flag = 0;
	for(int i = 1;i <= n;i++){
		cin >> a[i] >> b[i];
		if(a[i] != b[i]) flag = 1;
	}
	if(flag == 0){
		long long k = boat(n);
		cout << k;
		return 0;
	}
	long long ans = 0;
	notboat(n);
	memset(dpe,1,sizeof(dpe));
	for(int i = 1;i <= n;i++){
		for(long long k = a[i];k <= b[i];k++){
			ans += dpe[i][k];
		}
	}
	cout << ans;
}

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