oj.uz

답안 #106966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106966 2019-04-21T10:45:30 Z maksim_gaponov Boat (APIO16_boat) C++14
0 / 100
 6 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0)
		x += MOD;
	return x;
}

void run() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		// assert(a[i] == b[i]);
	}
	vector<vector<int>> dp(n);
	vector<int> dp0(n);
	for (int i = 0; i < n; ++i) {
		if (i == 0)
			dp0[i] = 1;
		else
			dp0[i] = dp[i - 1].back();
		dp[i].resize(b[i] - a[i] + 1);
		for (int j = a[i]; j <= b[i]; ++j) {
			dp[i][j - a[i]] = 0;
			if (j != a[i]) {
				dp[i][j - a[i]] += dp[i][j - a[i] - 1];
			} else {
				dp[i][j - a[i]] += dp0[i];
			}
			if (i > 0) {
				int val = 0;
				if (j - 1 >= a[i - 1]) {
					if (j - 1 > b[i - 1])
						val = dp[i - 1].back();
					else
						val = dp[i - 1][j - a[i - 1] - 1];
				}
				else {
					val = dp0[i - 1];
				}
				dp[i][j - a[i]] += val;
			} else {
				dp[i][j - a[i]] += 1;
			}
			dp[i][j - a[i]] %= MOD;
		}
	}
	int ans = dp.back().back();
	ans--;
	ans = mod(ans);
	cout << ans << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -