oj.uz

Submission #705059

# Submission time Handle Problem Language Result Execution time Memory
705059 2023-03-03T10:08:33 Z 600Mihnea Boat (APIO16_boat) C++17
31 / 100
 1502 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]));
}

int dumb(vector<pair<int, int>> segs)
{
	int n = (int)segs.size();
	vector<vector<int>> dp(n);
	for (int i = 0; i < n; i++)
	{
		assert(segs[i].first <= segs[i].second);
		dp[i].resize(segs[i].second - segs[i].first + 1, 1);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			for (int y = segs[i].first; y <= segs[i].second; y++)
			{
				if (segs[j].second <= y - 1)
				{
					addup(dp[i][y - segs[i].first], dp[j].back());
				}
				else
				{
					if (segs[j].first <= y - 1)
					{
						addup(dp[i][y - segs[i].first], dp[j][y - 1 - segs[j].first]);
					}
				}
			}
		}
		int cur = 0;
		for (auto& it : dp[i])
		{
			addup(cur, it);
			it = cur;
		}
	}
	int sol = 0;
	for (int i = 0; i < n; i++)
	{
		addup(sol, dp[i].back());
	}
	return sol;
}

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
	
	int n;
	cin >> n;
	vector<pair<int, int>> v(n);
	for (auto& it : v)
	{
		cin >> it.first >> it.second;
	}
	
	cout << dumb(v) << "\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 2 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 1 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 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 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 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 2 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 1 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 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 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1038 ms 3768 KB Output is correct
22 Correct 977 ms 3736 KB Output is correct
23 Correct 934 ms 3548 KB Output is correct
24 Correct 1046 ms 3856 KB Output is correct
25 Correct 1029 ms 3924 KB Output is correct
26 Correct 1375 ms 4096 KB Output is correct
27 Correct 1464 ms 4172 KB Output is correct
28 Correct 1419 ms 4052 KB Output is correct
29 Correct 1502 ms 4304 KB Output is correct
30 Correct 1189 ms 4224 KB Output is correct
31 Correct 1242 ms 4180 KB Output is correct
32 Correct 1232 ms 4260 KB Output is correct
33 Correct 1211 ms 4136 KB Output is correct
34 Correct 1201 ms 4180 KB Output is correct
35 Correct 602 ms 3984 KB Output is correct
36 Correct 725 ms 4108 KB Output is correct
37 Correct 640 ms 4144 KB Output is correct
38 Correct 740 ms 4036 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 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 2 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 1 ms 340 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 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 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1038 ms 3768 KB Output is correct
22 Correct 977 ms 3736 KB Output is correct
23 Correct 934 ms 3548 KB Output is correct
24 Correct 1046 ms 3856 KB Output is correct
25 Correct 1029 ms 3924 KB Output is correct
26 Correct 1375 ms 4096 KB Output is correct
27 Correct 1464 ms 4172 KB Output is correct
28 Correct 1419 ms 4052 KB Output is correct
29 Correct 1502 ms 4304 KB Output is correct
30 Correct 1189 ms 4224 KB Output is correct
31 Correct 1242 ms 4180 KB Output is correct
32 Correct 1232 ms 4260 KB Output is correct
33 Correct 1211 ms 4136 KB Output is correct
34 Correct 1201 ms 4180 KB Output is correct
35 Correct 602 ms 3984 KB Output is correct
36 Correct 725 ms 4108 KB Output is correct
37 Correct 640 ms 4144 KB Output is correct
38 Correct 740 ms 4036 KB Output is correct
39 Runtime error 245 ms 524288 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -