#474278 (C++14) No.1043 直列大学

提出ソース

結果

問題	No.1043 直列大学
ユーザー	kaage
提出日時	2020-05-01 21:58:18
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	123 ms / 2,000 ms
コード長	14,950 bytes
コンパイル時間	2,310 ms
コンパイル使用メモリ	135,880 KB
実行使用メモリ	175,428 KB
最終ジャッジ日時	2024-06-02 02:50:06
合計ジャッジ時間	5,838 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	74 ms 175,372 KB
testcase_01	AC	74 ms 175,424 KB
testcase_02	AC	76 ms 175,300 KB
testcase_03	AC	75 ms 175,224 KB
testcase_04	AC	74 ms 175,384 KB
testcase_05	AC	75 ms 175,360 KB
testcase_06	AC	74 ms 175,428 KB
testcase_07	AC	76 ms 175,368 KB
testcase_08	AC	75 ms 175,220 KB
testcase_09	AC	96 ms 175,340 KB
testcase_10	AC	100 ms 175,316 KB
testcase_11	AC	117 ms 175,364 KB
testcase_12	AC	123 ms 175,260 KB
testcase_13	AC	114 ms 175,176 KB
testcase_14	AC	120 ms 175,276 KB
testcase_15	AC	123 ms 175,300 KB
testcase_16	AC	117 ms 175,364 KB
testcase_17	AC	104 ms 175,332 KB
testcase_18	AC	103 ms 175,384 KB
testcase_19	AC	110 ms 175,224 KB
testcase_20	AC	101 ms 175,340 KB
testcase_21	AC	110 ms 175,352 KB
testcase_22	AC	110 ms 175,308 KB
testcase_23	AC	117 ms 175,352 KB
testcase_24	AC	104 ms 175,184 KB
testcase_25	AC	112 ms 175,300 KB
testcase_26	AC	113 ms 175,356 KB
testcase_27	AC	93 ms 175,336 KB
testcase_28	AC	112 ms 175,412 KB
testcase_29	AC	84 ms 175,392 KB
testcase_30	AC	103 ms 175,336 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define REP(i, n) for(int i=1;i<=(int)(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef std::pair<lint, lint> P;
constexpr int INF = INT_MAX / 10;
constexpr lint LINF = LLONG_MAX / 2;
constexpr double eps = 1e-9;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};

template<class T, class Alloc = std::allocator<T>>
class Vector {

	using traits = std::allocator_traits<Alloc>;

public:

	using value_type = T;
	using allocator_type = Alloc;
	using size_type = unsigned int;
	using difference_type = int;
	using reference = T&;
	using const_reference = const T&;
	using pointer = typename traits::pointer;
	using const_pointer = typename traits::const_pointer;

	class iterator {

	public:

		using difference_type = int;
		using value_type = Vector::value_type;
		using pointer = Vector::pointer;
		using reference = Vector::reference;
		using iterator_category = std::random_access_iterator_tag;

	private:

		pointer p;

	public:

		iterator()noexcept :p() {}
		iterator(const Vector& base, difference_type index) noexcept :p(base.e + index) {}
		iterator(const iterator& i) :p(i.p) {}

		iterator& operator=(const iterator& i) = default;
		iterator& operator=(iterator&& i)noexcept = default;

		iterator& operator++() {
			p++;
			return *this;
		}

		iterator operator++(int) {
			iterator res = *this;
			p++;
			return res;
		}

		iterator operator+(const difference_type& x)const {
			iterator res = *this;
			return res += x;
		}

		iterator& operator+=(const difference_type& x) {
			p += x;
			return *this;
		}

		iterator& operator--() {
			p--;
			return *this;
		}

		iterator operator--(int) {
			iterator res = *this;
			p--;
			return res;
		}

		iterator operator-(const difference_type x)const {
			iterator res = *this;
			return res -= x;
		}

		difference_type operator-(const iterator& i)const {
			return p - i.p;
		}

		iterator& operator-=(const difference_type x) {
			p -= x;
			return *this;
		}

		reference operator*()const {
			return *p;
		}

		reference operator[](const difference_type x)const {
			return *(p + x);
		}

		bool operator<(const iterator& i)const {
			return p < i.p;
		}

		bool operator<=(const iterator& i)const {
			return p <= i.p;
		}

		bool operator==(const iterator& i)const {
			return p == i.p;
		}

		bool operator>(const iterator& i)const {
			return p > i.p;
		}

		bool operator>=(const iterator& i)const {
			return p >= i.p;
		}

		bool operator!=(const iterator& i)const {
			return p != i.p;
		}

	};

	class const_iterator {

	public:

		using difference_type = int;
		using value_type = Vector::value_type;
		using pointer = const Vector::pointer;
		using reference = const Vector::reference;
		using iterator_category = std::random_access_iterator_tag;

	private:

		pointer p;

	public:

		const_iterator()noexcept :p() {}
		const_iterator(const Vector& base, difference_type index) noexcept :p(base.e + index) {}
		const_iterator(const const_iterator& i) :p(i.p) {}

		const_iterator& operator=(const const_iterator& i)noexcept = default;
		const_iterator& operator=(const_iterator&& i)noexcept = default;

		const_iterator& operator++() {
			p++;
			return *this;
		}

		const_iterator operator++(int) {
			const_iterator res = *this;
			p++;
			return res;
		}

		const_iterator operator+(const difference_type x)const {
			const_iterator res = *this;
			return res += x;
		}

		const_iterator& operator+=(const difference_type x) {
			p += x;
			return *this;
		}

		const_iterator& operator--() {
			p--;
			return *this;
		}

		const_iterator operator--(int) {
			const_iterator res = *this;
			p--;
			return res;
		}

		const_iterator operator-(const difference_type x)const {
			const_iterator res = *this;
			return res -= x;
		}

		difference_type operator-(const const_iterator& i)const {
			return p - i.p;
		}

		const_iterator& operator-=(const difference_type x) {
			p -= x;
			return *this;
		}

		reference operator*()const {
			return *p;
		}

		reference operator[](const difference_type x)const {
			return *(p + x);
		}

		bool operator<(const const_iterator& i)const {
			return p < i.p;
		}

		bool operator<=(const const_iterator& i)const {
			return p <= i.p;
		}

		bool operator==(const const_iterator& i)const {
			return p == i.p;
		}

		bool operator>(const const_iterator& i)const {
			return p > i.p;
		}

		bool operator>=(const const_iterator& i)const {
			return p >= i.p;
		}

		bool operator!=(const const_iterator& i)const {
			return p != i.p;
		}

	};

	using reverse_iterator = std::reverse_iterator<iterator>;
	using const_reverse_iterator = std::reverse_iterator<const_iterator>;

private:

	pointer e;
	size_type length = 0, cap = 1;
	Alloc alloc;

	static_assert(std::is_same<T, typename Alloc::value_type>::value, "The allocator value type is not matched the Vector value type.");
	static_assert(!std::is_const<T>::value, "This library forbids containers of const elements");

public:

	Vector() :Vector(Alloc()) {}

	explicit Vector(const Alloc& a)noexcept :alloc(a) {
		e = alloc.allocate(cap);
	}

	explicit Vector(size_type n, const Alloc& a = Alloc()) :alloc(a) {
		while (cap < n)cap *= 2;
		e = alloc.allocate(cap);
		rep(i, n)emplace_back();
	}

	explicit Vector(size_type n, const_reference value, const Alloc& a = Alloc()) :alloc(a) {
		while (cap < n)cap *= 2;
		e = alloc.allocate(cap);
		rep(i, n)emplace_back(value);
	}

	template<class InputIter>
	Vector(InputIter first, InputIter last, const Alloc& a = Alloc()) :alloc(a) {
		e = alloc.allocate(cap);
		for (InputIter i = first; i != last; i++) {
			emplace_back(*i);
		}
	}

	Vector(const Vector& x, const Alloc& a = Alloc()) :alloc(a) {
		while (cap < x.length)cap *= 2;
		length = x.length;
		e = alloc.allocate(cap);
		rep(i, x.length)traits::construct(alloc, e + i, *(x.e + i));
	}

	Vector(Vector&& x, const Alloc& a = Alloc()) :alloc(a) {
		cap = x.cap;
		length = x.length;
		e = x.e;
		x.e = nullptr;
	}

	~Vector() {
		if (e != nullptr) {
			rep(i, length)traits::destroy(alloc, e + i);
			alloc.deallocate(e, cap);
		}
	}

	Vector& operator=(const Vector& x) {
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		length = x.length;
		cap = 1;
		while (cap < length)cap *= 2;
		e = alloc.allocate(cap);
		rep(i, length)traits::construct(alloc, e + i, *(x.e + i));
		return *this;
	}

	Vector& operator=(Vector&& x) {
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		cap = x.cap;
		length = x.length;
		e = x.e;
		x.e = nullptr;
		return *this;
	}

private:

	void extension() {
		pointer e_ = alloc.allocate(cap * 2);
		rep(i, length)traits::construct(alloc, e_ + i, *(e + i));
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		e = e_;
		cap *= 2;
	}

	void extension(size_type n) {
		unsigned int r = 1;
		while (cap * r < n)r *= 2;
		if (r == 1)return;
		pointer e_ = alloc.allocate(cap * r);
		rep(i, length)traits::construct(alloc, e_ + i, *(e + i));
		rep(i, length)traits::destroy(alloc, e + i);
		alloc.deallocate(e, cap);
		e = e_;
		cap *= r;
	}

public:

	template<class InputIter>
	void assign(InputIter first, InputIter last) {
		size_type cnt = 0;
		for (InputIter i = first; i != last; i++) {
			if (cnt == cap) {
				length = std::max(length, cnt);
				extension();
			}
			traits::construct(alloc, e + cnt, *i);
			cnt++;
		}
	}

	void assign(size_type n, const_reference value) {
		extension(n);
		std::fill(e, e + n, value);
	}

	template<class... Args>
	void emplace_back(Args&&... args) {
		if (length == cap)extension();
		traits::construct(alloc, e + length, std::forward<Args>(args)...);
		length++;
	}

	void push_back(const_reference value) {
		emplace_back(value);
	}

	void push_back(T&& value) {
		emplace_back(std::move(value));
	}

	void pop_back() {
		traits::destroy(alloc, e + length);
		length--;
	}

	void reserve(size_type n) {
		extension(n);
	}

	iterator erase(iterator pos) {
		const iterator res = pos;
		iterator t = pos; t++;
		for (iterator i = pos; t != end(); i++, t++) {
			*i = std::move(*t);
		}
		pop_back();
		return res;
	}

	iterator erase(iterator first, iterator last) {
		const iterator res = first;
		typename iterator::difference_type d = last - first;
		for (iterator i = first; i + d != end(); i++) {
			*i = std::move(*(i + d));
		}
		rep(i, d)pop_back();
		return res;
	}

	void swap(Vector& x) {
		std::swap(length, x.length);
		std::swap(cap, x.cap);
		std::swap(e, x.e);
	}

	void clear() {
		while (length)pop_back();
	}

	size_type size()const {
		return length;
	}

	void resize(size_type  n, const_reference value = T()) {
		extension(n);
		while (n < length)pop_back();
		length = n;
		std::fill(e, e + n, value);
	}

	size_type capacity()const {
		return cap;
	}

	bool empty()const {
		return !length;
	}

	reference operator[](const size_type pos)const {
		return e[pos];
	}

	pointer data() {
		return e;
	}

	reference front() {
		return *e;
	}

	reference back() {
		return *(e + length - 1);
	}

	iterator begin() noexcept {
		return iterator(*this, 0);
	}

	const_iterator begin()const noexcept {
		return const_iterator(*this, 0);
	}

	const_iterator cbegin()const noexcept {
		return const_iterator(*this, 0);
	}

	iterator rbegin()noexcept {
		return reverse_iterator(*this, 0);
	}

	const_iterator rbegin()const noexcept {
		return const_reverse_iterator(*this, 0);
	}

	const_iterator crbegin()const noexcept {
		return const_reverse_iterator(*this, 0);
	}

	iterator end() noexcept {
		return iterator(*this, length);
	}

	const_iterator end()const noexcept {
		return const_iterator(*this, length);
	}

	const_iterator cend()const noexcept {
		return const_iterator(*this, length);
	}

	iterator rend()noexcept {
		return reverse_iterator(*this, length);
	}

	const_iterator rend()const noexcept {
		return const_reverse_iterator(*this, length);
	}

	const_iterator crend()const noexcept {
		return const_reverse_iterator(*this, length);
	}

};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
lint mypow(lint a, lint b) {
	if (!b)return 1;
	if (b & 1)return mypow(a, b - 1) * a;
	lint memo = mypow(a, b >> 1);
	return memo * memo;
}
lint modpow(lint a, lint b, lint m) {
	if (!b)return 1;
	if (b & 1)return modpow(a, b - 1, m) * a % m;
	lint memo = modpow(a, b >> 1, m);
	return memo * memo % m;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(Vector<T>& vec) {
	rep(i, vec.size() - 1)std::cout << vec[i] << " ";
	std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(T l, T r) {
	T rprev = r;
	rprev--;
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
std::string to_string(Vector<int>& vec) {
	std::string res = "[";
	rep(i, vec.size() - 1)res += std::to_string(vec[i]) + ", ";
	res += std::to_string(vec.back()) + "]";
	return res;
}
template<unsigned int modulo = 1000000007>
class ModInt {
	lint value;
public:
	ModInt() : value(0) {}
	template<typename T>
	ModInt(T value = 0) : value(value) {
		if (value < 0)value = -(lint)(-value % modulo) + modulo;
		this->value = value % modulo;
	}
	inline operator int()const { return value; }
	inline ModInt& operator+=(const ModInt& x) {
		value += x.value;
		if (value >= modulo)value -= modulo;
		return *this;
	}
	inline ModInt& operator++() {
		if (value == modulo - 1)value = 0;
		else value++;
		return *this;
	}
	inline ModInt operator-()const {
		return ModInt(0) -= *this;
	}
	inline ModInt& operator-=(const ModInt& x) {
		value -= x.value;
		if (value < 0)value += modulo;
		return *this;
	}
	inline ModInt& operator--() {
		if (value == 0)value = modulo - 1;
		else value--;
		return *this;
	}
	inline ModInt& operator*=(const ModInt& x) {
		value = value * x.value % modulo;
		return *this;
	}
	inline ModInt& operator/=(ModInt rhs) {
		int exp = modulo - 2;
		while (exp) {
			if (exp & 1)*this *= rhs;
			rhs *= rhs;
			exp >>= 1;
		}
		return *this;
	}
	template<typename T> ModInt operator+(const T& rhs)const { return ModInt(*this) += rhs; }
	template<typename T> ModInt& operator+=(const T& rhs) { return operator+=(ModInt(rhs)); }
	template<typename T> ModInt operator-(const T& rhs)const { return ModInt(*this) -= rhs; }
	template<typename T> ModInt& operator-=(const T& rhs) { return operator-=(ModInt(rhs)); }
	template<typename T> ModInt operator*(const T& rhs)const { return ModInt(*this) *= rhs; }
	template<typename T> ModInt& operator*=(const T& rhs) { return operator*=(ModInt(rhs)); }
	template<typename T> ModInt operator/(const T& rhs)const { return ModInt(*this) /= rhs; }
	template<typename T> ModInt& operator/=(const T& rhs) { return operator/=(ModInt(rhs)); }
};
template<unsigned int T>
std::istream& operator>>(std::istream& ist, ModInt<T>& x) {
	lint a;
	ist >> a;
	x = a;
	return ist;
}
lint n, m, v[110], r[110], a, b;
ModInt<> dp[2][110][100010];
int main() {
	std::cin >> n >> m;
	rep(i, n)std::cin >> v[i];
	rep(i, m)std::cin >> r[i];
	std::cin >> a >> b;
	dp[0][0][0] = 1;
	rep(i, n) {
		rep(j, 100001) {
			if (j + v[i] <= 100000)dp[0][1][j + v[i]] += dp[0][0][j];
			dp[0][1][j] += dp[0][0][j];
		}
		rep(j, 100001) {
			dp[0][0][j] = dp[0][1][j];
			dp[0][1][j] = 0;
		}
	}
	dp[1][0][0] = 1;
	rep(i, m) {
		rep(j, 100001) {
			if (j + r[i] <= 100000)dp[1][1][j + r[i]] += dp[1][0][j];
			dp[1][1][j] += dp[1][0][j];
		}
		rep(j, 100001) {
			dp[1][0][j] = dp[1][1][j];
			dp[1][1][j] = 0;
		}
	}
	ModInt<> ans = 0;
	rep(i, 100000)dp[0][0][i + 1] += dp[0][0][i];
	REP(i, 100000) {
		ans += dp[1][0][i] * (dp[0][0][std::min((lint)100000, i * b)] - dp[0][0][std::min((lint)100000, i * a - 1)]);
	}
	std::cout << ans << std::endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード