oj.uz

Submission #23225

# Submission time Handle Problem Language Result Execution time Memory
23225 2017-05-05T07:34:41 Z 14kg Boat (APIO16_boat) C++11
9 / 100
 1189 ms 7940 KB 
#include <stdio.h>
#include <map>
#include <set>
#include <algorithm>
#define MOD 1000000007
#define min2(x,y) (x<y?x:y)

using namespace std;
int n, w_len;
long long d[501][1503];
bool check[501][1503];
pair<int, int> r[501], w[1503];
set<int> S;
map<int,int> M;

long long f(int lev, int y) {
	if (lev == 0) return 1;
	if (!check[lev][y]) {
		check[lev][y] = true, d[lev][y] = f(lev - 1, y);
		for (int i = r[lev].first; i <= min2(r[lev].second, y); i++) {
			long long temp = f(lev - 1, i - 1), temp2 = w[i].second - w[i].first + 1;
			temp = (temp*temp2);
			d[lev][y] = (d[lev][y] + temp) % MOD;
		}
	} return d[lev][y];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &r[i].first, &r[i].second);
		S.insert(r[i].first), S.insert(r[i].second);
	}

	auto it1 = S.begin(), it2 = it1;
	
	it2++, w[++w_len] = { 0,*it1 - 1 };
	while (it2 != S.end()) {
		M[*it1] = ++w_len, w[w_len] = { *it1,*it1 };
		if (*it1 + 1 <= *it2 - 1) w[++w_len] = { *it1 + 1,*it2 - 1 };
		it1++, it2++;
	} M[*it1] = ++w_len, w[w_len] = { *it1,*it1 };

	for (int i = 1; i <= n; i++) {
		r[i].first = M[r[i].first];
		r[i].second = M[r[i].second];
	}

	long long res = f(n, w_len);
	printf("%lld", res ? res - 1 : MOD- 1);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
boat.cpp:30:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &r[i].first, &r[i].second);
                                            ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7808 KB Output is correct
2 Correct 3 ms 7808 KB Output is correct
3 Correct 6 ms 7808 KB Output is correct
4 Correct 3 ms 7808 KB Output is correct
5 Correct 6 ms 7808 KB Output is correct
6 Correct 6 ms 7808 KB Output is correct
7 Correct 3 ms 7808 KB Output is correct
8 Correct 3 ms 7808 KB Output is correct
9 Correct 6 ms 7808 KB Output is correct
10 Correct 3 ms 7808 KB Output is correct
11 Correct 3 ms 7808 KB Output is correct
12 Correct 6 ms 7808 KB Output is correct
13 Correct 3 ms 7808 KB Output is correct
14 Correct 3 ms 7808 KB Output is correct
15 Correct 6 ms 7808 KB Output is correct
16 Correct 3 ms 7808 KB Output is correct
17 Correct 0 ms 7808 KB Output is correct
18 Correct 0 ms 7808 KB Output is correct
19 Correct 0 ms 7808 KB Output is correct
20 Correct 0 ms 7808 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7808 KB Output is correct
2 Correct 3 ms 7808 KB Output is correct
3 Correct 6 ms 7808 KB Output is correct
4 Correct 3 ms 7808 KB Output is correct
5 Correct 6 ms 7808 KB Output is correct
6 Correct 6 ms 7808 KB Output is correct
7 Correct 3 ms 7808 KB Output is correct
8 Correct 3 ms 7808 KB Output is correct
9 Correct 6 ms 7808 KB Output is correct
10 Correct 3 ms 7808 KB Output is correct
11 Correct 3 ms 7808 KB Output is correct
12 Correct 6 ms 7808 KB Output is correct
13 Correct 3 ms 7808 KB Output is correct
14 Correct 3 ms 7808 KB Output is correct
15 Correct 6 ms 7808 KB Output is correct
16 Correct 3 ms 7808 KB Output is correct
17 Correct 0 ms 7808 KB Output is correct
18 Correct 0 ms 7808 KB Output is correct
19 Correct 0 ms 7808 KB Output is correct
20 Correct 0 ms 7808 KB Output is correct
21 Incorrect 1189 ms 7940 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 7808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7808 KB Output is correct
2 Correct 3 ms 7808 KB Output is correct
3 Correct 6 ms 7808 KB Output is correct
4 Correct 3 ms 7808 KB Output is correct
5 Correct 6 ms 7808 KB Output is correct
6 Correct 6 ms 7808 KB Output is correct
7 Correct 3 ms 7808 KB Output is correct
8 Correct 3 ms 7808 KB Output is correct
9 Correct 6 ms 7808 KB Output is correct
10 Correct 3 ms 7808 KB Output is correct
11 Correct 3 ms 7808 KB Output is correct
12 Correct 6 ms 7808 KB Output is correct
13 Correct 3 ms 7808 KB Output is correct
14 Correct 3 ms 7808 KB Output is correct
15 Correct 6 ms 7808 KB Output is correct
16 Correct 3 ms 7808 KB Output is correct
17 Correct 0 ms 7808 KB Output is correct
18 Correct 0 ms 7808 KB Output is correct
19 Correct 0 ms 7808 KB Output is correct
20 Correct 0 ms 7808 KB Output is correct
21 Incorrect 1189 ms 7940 KB Output isn't correct
22 Halted 0 ms 0 KB -