oj.uz

Submission #703758

# Submission time Handle Problem Language Result Execution time Memory
703758 2023-02-28T09:38:47 Z 600Mihnea Boat (APIO16_boat) C++17
31 / 100
 1505 ms 524288 KB 
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>

using namespace std;

typedef long long ll;
const int M = (int)1e9 + 7;
const int FACTN = 300000 + 7;

int add(int a, int b) {
	a += b;
	if (a >= M) return a - M;
	if (a < 0) return a + M;
	return a;
}

int mul(int a, int b) {
	return a * (ll)b % M;
}

int add(int a, int b, int c) {
	return add(add(a, b), c);
}

int mul(int a, int b, int c) {
	return mul(mul(a, b), c);
}

int add(int a, int b, int c, int d) {
	return add(add(a, b, c), d);
}

int mul(int a, int b, int c, int d) {
	return mul(mul(a, b, c), d);
}

int add(int a, int b, int c, int d, int e) {
	return add(add(a, b, c, d), e);
}

int mul(int a, int b, int c, int d, int e) {
	return mul(mul(a, b, c, d), e);
}

int add(int a, int b, int c, int d, int e, int f) {
	return add(add(a, b, c, d, e), f);
}

int mul(int a, int b, int c, int d, int e, int f) {
	return mul(mul(a, b, c, d, e), f);
}

int add(int a, int b, int c, int d, int e, int f, int g) {
	return add(add(a, b, c, d, e, f), g);
}

int mul(int a, int b, int c, int d, int e, int f, int g) {
	return mul(mul(a, b, c, d, e, f), g);
}

int add(int a, int b, int c, int d, int e, int f, int g, int h) {
	return add(add(a, b, c, d, e, f, g), h);
}

int mul(int a, int b, int c, int d, int e, int f, int g, int h) {
	return mul(mul(a, b, c, d, e, f, g), h);
}

int pw(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b /= 2;
	}
	return r;
}

int dv(int a, int b) {
	return mul(a, pw(b, M - 2));
}

void addup(int& a, int b) {
	a = add(a, b);
}

void mulup(int& a, int b) {
	a = mul(a, b);
}

void dvup(int& a, int b) {
	a = dv(a, b);
}

int fact[FACTN], ifact[FACTN];

void computeFACT() {
	fact[0] = 1;
	for (int i = 1; i < FACTN; i++) fact[i] = mul(fact[i - 1], i);
	ifact[FACTN - 1] = dv(1, fact[FACTN - 1]);
	for (int i = FACTN - 2; i >= 0; i--) ifact[i] = mul(ifact[i + 1], i + 1);
}

int getCOMB(int n, int k) {
	return mul(fact[n], mul(ifact[k], ifact[n - k]));
}

const int N = 500 + 7;
int n;
int low[N], high[N];
vector<int> dp[N];

signed main()
{
#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif

	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> low[i] >> high[i];
		assert(low[i] <= high[i]);
		dp[i].resize(high[i] - low[i] + 1, 1);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j < i; j++)
		{
			for (int y = low[i]; y <= high[i]; y++)
			{
				if (high[j] <= y - 1)
				{
					addup(dp[i][y - low[i]], dp[j].back());
				}
				else
				{
					if (low[j] <= y - 1)
					{
						addup(dp[i][y - low[i]], dp[j][y - 1 - low[j]]);
					}
				}
			}	
		}
		int cur = 0;
		for (auto& it : dp[i])
		{
			addup(cur, it);
			it = cur;
		}
	}
	int sol = 0;
	for (int i = 1; i <= n; i++)
	{
		addup(sol, dp[i].back());
	}
	cout << sol << "\n";
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 356 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 356 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1063 ms 3768 KB Output is correct
22 Correct 1002 ms 3668 KB Output is correct
23 Correct 958 ms 3664 KB Output is correct
24 Correct 1072 ms 3860 KB Output is correct
25 Correct 1045 ms 3904 KB Output is correct
26 Correct 1402 ms 4092 KB Output is correct
27 Correct 1469 ms 4152 KB Output is correct
28 Correct 1434 ms 4168 KB Output is correct
29 Correct 1505 ms 4180 KB Output is correct
30 Correct 1282 ms 4308 KB Output is correct
31 Correct 1261 ms 4064 KB Output is correct
32 Correct 1292 ms 4188 KB Output is correct
33 Correct 1208 ms 4124 KB Output is correct
34 Correct 1274 ms 4180 KB Output is correct
35 Correct 610 ms 3980 KB Output is correct
36 Correct 758 ms 4100 KB Output is correct
37 Correct 755 ms 4140 KB Output is correct
38 Correct 789 ms 4016 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 237 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 356 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 356 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1063 ms 3768 KB Output is correct
22 Correct 1002 ms 3668 KB Output is correct
23 Correct 958 ms 3664 KB Output is correct
24 Correct 1072 ms 3860 KB Output is correct
25 Correct 1045 ms 3904 KB Output is correct
26 Correct 1402 ms 4092 KB Output is correct
27 Correct 1469 ms 4152 KB Output is correct
28 Correct 1434 ms 4168 KB Output is correct
29 Correct 1505 ms 4180 KB Output is correct
30 Correct 1282 ms 4308 KB Output is correct
31 Correct 1261 ms 4064 KB Output is correct
32 Correct 1292 ms 4188 KB Output is correct
33 Correct 1208 ms 4124 KB Output is correct
34 Correct 1274 ms 4180 KB Output is correct
35 Correct 610 ms 3980 KB Output is correct
36 Correct 758 ms 4100 KB Output is correct
37 Correct 755 ms 4140 KB Output is correct
38 Correct 789 ms 4016 KB Output is correct
39 Runtime error 237 ms 524288 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -