답안 #151752

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
151752	2019-09-04T14:46:44 Z	SorahISA	Boat (APIO16_boat)	C++14	31 / 100	736 ms	8216 KB

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.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	3 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	380 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	3 ms	404 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	3 ms	348 KB	Output is correct
17	Correct	3 ms	380 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	3 ms	376 KB	Output is correct
20	Correct	3 ms	376 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	3 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	380 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	3 ms	404 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	3 ms	348 KB	Output is correct
17	Correct	3 ms	380 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	3 ms	376 KB	Output is correct
20	Correct	3 ms	376 KB	Output is correct
21	Correct	672 ms	7232 KB	Output is correct
22	Correct	693 ms	7160 KB	Output is correct
23	Correct	659 ms	6904 KB	Output is correct
24	Correct	731 ms	7544 KB	Output is correct
25	Correct	699 ms	7516 KB	Output is correct
26	Correct	661 ms	7900 KB	Output is correct
27	Correct	714 ms	8056 KB	Output is correct
28	Correct	714 ms	7928 KB	Output is correct
29	Correct	736 ms	8088 KB	Output is correct
30	Correct	712 ms	8216 KB	Output is correct
31	Correct	702 ms	8184 KB	Output is correct
32	Correct	712 ms	8172 KB	Output is correct
33	Correct	682 ms	7972 KB	Output is correct
34	Correct	678 ms	8036 KB	Output is correct
35	Correct	365 ms	7672 KB	Output is correct
36	Correct	434 ms	7800 KB	Output is correct
37	Correct	429 ms	7928 KB	Output is correct
38	Correct	448 ms	7800 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	5 ms	504 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	Correct	4 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	376 KB	Output is correct
4	Correct	3 ms	376 KB	Output is correct
5	Correct	3 ms	376 KB	Output is correct
6	Correct	3 ms	376 KB	Output is correct
7	Correct	3 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	380 KB	Output is correct
11	Correct	3 ms	376 KB	Output is correct
12	Correct	3 ms	376 KB	Output is correct
13	Correct	3 ms	404 KB	Output is correct
14	Correct	3 ms	376 KB	Output is correct
15	Correct	3 ms	376 KB	Output is correct
16	Correct	3 ms	348 KB	Output is correct
17	Correct	3 ms	380 KB	Output is correct
18	Correct	3 ms	376 KB	Output is correct
19	Correct	3 ms	376 KB	Output is correct
20	Correct	3 ms	376 KB	Output is correct
21	Correct	672 ms	7232 KB	Output is correct
22	Correct	693 ms	7160 KB	Output is correct
23	Correct	659 ms	6904 KB	Output is correct
24	Correct	731 ms	7544 KB	Output is correct
25	Correct	699 ms	7516 KB	Output is correct
26	Correct	661 ms	7900 KB	Output is correct
27	Correct	714 ms	8056 KB	Output is correct
28	Correct	714 ms	7928 KB	Output is correct
29	Correct	736 ms	8088 KB	Output is correct
30	Correct	712 ms	8216 KB	Output is correct
31	Correct	702 ms	8184 KB	Output is correct
32	Correct	712 ms	8172 KB	Output is correct
33	Correct	682 ms	7972 KB	Output is correct
34	Correct	678 ms	8036 KB	Output is correct
35	Correct	365 ms	7672 KB	Output is correct
36	Correct	434 ms	7800 KB	Output is correct
37	Correct	429 ms	7928 KB	Output is correct
38	Correct	448 ms	7800 KB	Output is correct
39	Runtime error	5 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
40	Halted	0 ms	0 KB	-

답안 #151752

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0