結果

問題 No.3800 Screw manufacturing
コンテスト
ユーザー 👑 qand
提出日時 2026-11-13 23:36:59
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,025 ms / 2,000 ms
+ 69µs
コード長 4,752 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,326 ms
コンパイル使用メモリ 401,976 KB
実行使用メモリ 37,764 KB
最終ジャッジ日時 2026-11-13 23:37:36
合計ジャッジ時間 35,280 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge1_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

// https://qandori.github.io/cp-library/
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using std::cin, std::cout, std::cerr;
#define vec vector
typedef long double ld;
#if LONG_MAX == 2147483647L
#undef long
#define long long long
#endif
#define uint unsigned int
#define ulong unsigned long
#define overload3(a, b, c, name, ...) name
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep2(__i__, n)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define per2(i, n) per3(i, 0, n)
#define per1(n) per2(__i__, n)
#define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define CP_ALL_SELECT(first, ...) first
#define CP_ALL_RANGE(a) std::begin(a), std::end(a)
#define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__)
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit()
#define sz(a) static_cast<int>(a.size())
#ifndef DEBUG
#define cerr \
	if (false) cerr
#undef endl
#define endl '\n'
#endif
inline auto operator^=(vector<bool>::reference a, bool b) noexcept {
	if (b) a.flip();
	return a;
}
inline auto operator&=(vector<bool>::reference a, bool b) noexcept {
	if (!b) a = false;
	return a;
}
inline auto operator|=(vector<bool>::reference a, bool b) noexcept {
	if (b) a = true;
	return a;
}
inline ostream &operator<<(ostream &os, __int128_t value) {
	ostream::sentry s(os);
	if (s) {
		__uint128_t tmp = value;
		if (value < 0) tmp = -tmp;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		if (value < 0) --d, *d = '-';
		const int len = std::end(buffer) - d;
		if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit);
	}
	return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
	return os << a.first << ' ' << a.second;
};
template <typename T>
ostream &operator<<(ostream &os, vector<T> a) {
	const int n = a.size();
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &a) {
	return is >> a.first >> a.second;
}
template <typename T, size_t n>
ostream &operator<<(ostream &os, array<T, n> a) {
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &a) {
	for (T &i : a) is >> i;
	return is;
}
template <typename T, typename S>
bool chmin(T &x, S y) {
	if ((T)y < x) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T, typename S>
bool chmax(T &x, S y) {
	if (x < (T)y) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T>
void operator++(vector<T> &a) {
	for (T &i : a) ++i;
}
template <typename T>
void operator--(vector<T> &a) {
	for (T &i : a) --i;
}
template <typename T>
void operator++(vector<T> &a, int) {
	for (T &i : a) i++;
}
template <typename T>
void operator--(vector<T> &a, int) {
	for (T &i : a) i--;
}
void init(), solve();
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
	init();
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
// #define COMB_MAX 1e6
// #include "lib/math/comb.hpp"
// #include "lib/fps/fps.hpp"
// #include "lib/math/mint.hpp"
void init() {}
struct S {
	long a, b, r;
};
long t;
long calc(vec<S> d) {
	long p = -t, q = -t;
	for (auto [a, b, r] : d) {
		p += t;
		q = max(q + t, p + a);
		long pp = p + r * a;
		long qq = q + r * b;
		chmax(qq, pp + b);
		p = pp, q = qq;
	}
	return q;
}
void solve() {
	int n;
	cin >> n >> t;
	vec<S> a(n);
	rep(i, n) cin >> a[i].r;
	rep(i, n) cin >> a[i].a >> a[i].b;
	vec<S> x, y;
	for (S &s : a) {
		if (s.a < s.b) x.push_back(s);
		else y.push_back(s);
	}
	auto f = [&](vec<S> &a, int ty) {
		if (ty == 0) sort(all(a), [&](S &s1, S &s2) { return s1.a < s2.a; });
		if (ty == 1) sort(all(a), [&](S &s1, S &s2) { return s1.a > s2.a; });
		if (ty == 2) sort(all(a), [&](S &s1, S &s2) { return s1.b < s2.b; });
		if (ty == 3) sort(all(a), [&](S &s1, S &s2) { return s1.b > s2.b; });
		if (ty == 4) sort(all(a), [&](S &s1, S &s2) { return s1.a - s1.b > s2.a - s2.b; });
		if (ty == 5) sort(all(a), [&](S &s1, S &s2) { return s1.a - s1.b < s2.a - s2.b; });
	};
	long ans = LONG_MAX;
	rep(loop, 2) {
		rep(i, 6) {
			rep(j, 6) {
				f(x, i), f(y, j);
				vec<S> o;
				for (S &s : x) o.push_back(s);
				for (S &s : y) o.push_back(s);
				chmin(ans, calc(o));
			}
		}
		swap(x, y);
	}
	cout << ans / (24 * 60) << ' ';
	ans %= 24 * 60;
	cout << ans / 60 << ' ';
	ans %= 60;
	cout << ans << endl;
	return;
}
0