Submission #703765

#	Time	Username	Problem	Language	Result	Execution time	Memory
703765		600Mihnea	Boat (APIO16_boat)	C++17	31 / 100	1458 ms	524288 KiB

boat

#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];

int lagrange(vector<pair<int, int>> have, int x)
{
	for (auto& it : have)
	{
		if (it.first == x)
		{
			return it.second;
		}
	}
	int y = 0;
	for (int j = 0; j < (int)have.size(); j++)
	{
		int p = 1;
		for (int m = 0; m < (int)have.size(); m++)
		{
			if (m != j)
			{
				mulup(p, dv(add(x, -have[m].first), add(have[j].first, -have[m].first)));
			}
		}
		addup(y, mul(have[j].second, p));
	}
	return y;
}

int f(int x)
{
	return add(mul(3, x, x, x), mul(x, x));
}

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

	//{
	//	vector<pair<int, int>> lol;
	//	lol.push_back({ 1, f(1) });
	//	lol.push_back({ 2, f(2) });
	//	lol.push_back({ 3, f(3) });
	//	lol.push_back({ 4, f(4) });
	//	for (int i = 1; i <= 10; i++)
	//	{
	//		cout << i << " : " << f(i) << " vs " << lagrange(lol, i) << "\n";
	//	}
	//	exit(0);
	//}

	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 make = min(high[i] - low[i] + 1, i);
		vector<pair<int, int>> pts;
		for (int d = 0; d < make; d++)
		{
			int pz = (int)dp[i].size() - 1 - d;
			pts.push_back({ pz, dp[i][pz] });
		}
		for (int pz = 0; pz < (int)dp[i].size(); pz++)
		{
			//assert(dp[i][pz] == lagrange(pts, pz));
		}
		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 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42