Submission #151752

#	Time	Username	Problem	Language	Result	Execution time	Memory
151752		SorahISA	Boat (APIO16_boat)	C++14	31 / 100	736 ms	8216 KiB

boat

#include <bits/stdc++.h>
using namespace std;

const long long mod = 1E9 + 7;

int main() {
	int n;
	cin >> n;
	
	vector<vector<long long>> pre_dp;
	long long boat[n][2];
	for (int i = 0; i < n; ++i) {
		cin >> boat[i][0] >> boat[i][1];
		pre_dp.push_back(vector<long long>(boat[i][1] - boat[i][0] + 1, 1));
	}
	
	long long answer = 0;
	for (int i = 0; i < n; ++i) {
		int sz = pre_dp[i].size();
		for (int j = 0; j < sz; ++j) {
			for (int k = 0; k < i; ++k) {
				if (boat[i][0] + j > boat[k][1]) {
					pre_dp[i][j] += pre_dp[k][boat[k][1] - boat[k][0]];
				}
				else if (boat[i][0] + j <= boat[k][0]) {
					// do nothing
				}
				else {
					pre_dp[i][j] += pre_dp[k][boat[i][0] + j - boat[k][0] - 1];
				}
			}
			
			answer += pre_dp[i][j];
			if (j) pre_dp[i][j] += pre_dp[i][j - 1];
			pre_dp[i][j] %= mod;
		}
		answer %= mod;
	}
	
	answer %= mod;
	cout << answer << '\n';
	
	return 0;
}

/*
int main() {
	int n;
	cin >> n;
	
	long long boat[n][2];
	for (int i = 0; i < n; ++i) {
		cin >> boat[i][0] >> boat[i][1];
	}
	
	long long dp[n], answer = 0;
	for (int i = 0; i < n; ++i) {
		dp[i] = 1;
		for (int j = 0; j < i; ++j) {
			if (boat[j][0] < boat[i][0]) {
				dp[i] += dp[j];
			}
		}
		dp[i] %= mod;
		answer += dp[i];
	}
	
	answer %= mod;
	cout << answer << '\n';
	
	return 0;
}
*/

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