QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#311199#8137. 'Ello, and What Are You After, Then?ucup-team088WA 1742ms12504kbC++177.8kb2024-01-22 04:11:572024-01-22 04:11:58

Judging History

你现在查看的是最新测评结果

  • [2024-01-22 04:11:58]
  • 评测
  • 测评结果:WA
  • 用时:1742ms
  • 内存:12504kb
  • [2024-01-22 04:11:57]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
#include<array>
#include<chrono>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
//ll mod = 1;
constexpr ll mod = 998244353;
//constexpr ll mod = 1000000007;
const int mod17 = 1000000007;
const ll INF = (ll)mod17 * mod17;
typedef pair<int, int>P;

#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;

using ld = double;
typedef pair<ld, ld> LDP;
const ld eps = 1e-10;
const ld pi = acosl(-1.0);

template<typename T>
void chmin(T& a, T b) {
	a = min(a, b);
}
template<typename T>
void chmax(T& a, T b) {
	a = max(a, b);
}
template<typename T>
vector<T> vmerge(vector<T>& a, vector<T>& b) {
	vector<T> res;
	int ida = 0, idb = 0;
	while (ida < a.size() || idb < b.size()) {
		if (idb == b.size()) {
			res.push_back(a[ida]); ida++;
		}
		else if (ida == a.size()) {
			res.push_back(b[idb]); idb++;
		}
		else {
			if (a[ida] < b[idb]) {
				res.push_back(a[ida]); ida++;
			}
			else {
				res.push_back(b[idb]); idb++;
			}
		}
	}
	return res;
}
template<typename T>
void cinarray(vector<T>& v) {
	rep(i, v.size())cin >> v[i];
}
template<typename T>
void coutarray(vector<T>& v) {
	rep(i, v.size()) {
		if (i > 0)cout << " "; cout << v[i];
	}
	cout << "\n";
}
ll mod_pow(ll x, ll n, ll m = mod) {
	if (n < 0) {
		ll res = mod_pow(x, -n, m);
		return mod_pow(res, m - 2, m);
	}
	if (abs(x) >= m)x %= m;
	if (x < 0)x += m;
	//if (x == 0)return 0;
	ll res = 1;
	while (n) {
		if (n & 1)res = res * x % m;
		x = x * x % m; n >>= 1;
	}
	return res;
}
//mod should be <2^31
struct modint {
	int n;
	modint() :n(0) { ; }
	modint(ll m) {
		if (m < 0 || mod <= m) {
			m %= mod; if (m < 0)m += mod;
		}
		n = m;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
bool operator<(modint a, modint b) { return a.n < b.n; }
modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; }
modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; }
modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, ll n) {
	if (n == 0)return modint(1);
	modint res = (a * a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	if (a == 0)return 0;
	return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }
modint operator/=(modint& a, modint b) { a = a / b; return a; }
const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[a - b];
}

ll gcd(ll a, ll b) {
	a = abs(a); b = abs(b);
	if (a < b)swap(a, b);
	while (b) {
		ll r = a % b; a = b; b = r;
	}
	return a;
}
template<typename T>
void addv(vector<T>& v, int loc, T val) {
	if (loc >= v.size())v.resize(loc + 1, 0);
	v[loc] += val;
}
/*const int mn = 2000005;
bool isp[mn];
vector<int> ps;
void init() {
	fill(isp + 2, isp + mn, true);
	for (int i = 2; i < mn; i++) {
		if (!isp[i])continue;
		ps.push_back(i);
		for (int j = 2 * i; j < mn; j += i) {
			isp[j] = false;
		}
	}
}*/

//[,val)
template<typename T>
auto prev_itr(set<T>& st, T val) {
	auto res = st.lower_bound(val);
	if (res == st.begin())return st.end();
	res--; return res;
}

//[val,)
template<typename T>
auto next_itr(set<T>& st, T val) {
	auto res = st.lower_bound(val);
	return res;
}
using mP = pair<modint, modint>;
mP operator+(mP a, mP b) {
	return { a.first + b.first,a.second + b.second };
}
mP operator+=(mP& a, mP b) {
	a = a + b; return a;
}
mP operator-(mP a, mP b) {
	return { a.first - b.first,a.second - b.second };
}
mP operator-=(mP& a, mP b) {
	a = a - b; return a;
}
LP operator+(LP a, LP b) {
	return { a.first + b.first,a.second + b.second };
}
LP operator+=(LP& a, LP b) {
	a = a + b; return a;
}
LP operator-(LP a, LP b) {
	return { a.first - b.first,a.second - b.second };
}
LP operator-=(LP& a, LP b) {
	a = a - b; return a;
}

mt19937 mt(time(0));

const string drul = "DRUL";
string senw = "SENW";
//DRUL,or SENW
//int dx[4] = { 1,0,-1,0 };
//int dy[4] = { 0,1,0,-1 };

//------------------------------------


void solve() {
	int b, c, s; cin >> b >> c >> s;
	int n; cin >> n;
	vector<vector<int>> f(n), t(n), e(n);
	rep(i, n) {
		int len; cin >> len;
		f[i].resize(len);
		t[i].resize(len);
		e[i].resize(len);
		rep(j, len)cin >> f[i][j] >> t[i][j] >> e[i][j];
	}
	auto can = [&](ld x)->bool {
		ld maup = -INF;
		ld madow = -INF;
		rep(i, n) {
			int nsz = f[i].size(); nsz -= b; chmax(nsz, 1);
			vector<ld> vs;
			rep(j, f[i].size()) {
				ld val = e[i][j] * t[i][j] - t[i][j] * x;
				vs.push_back(val);
			}
			auto can2 = [&](ld vx) {
				vector<ld> ts;
				rep(j, f[i].size()) {
					ld v = f[i][j] * (vs[j] - vx);
					ts.push_back(v);
				}
				sort(all(ts), greater<ld>());
				ts.resize(nsz);
				ld sum = 0;
				rep(i, ts.size())sum += ts[i];
				return sum >= 0;
			};
			ld le = -mod17, ri = mod17;
			rep(_, 60) {
				ld mid = (le + ri) / 2;
				if (can2(mid))le = mid;
				else ri = mid;
			}
			chmax(maup, le);
		}
		if (maup >= 0)return true;
		rep(i, n) {
			int nsz = f[i].size(); nsz -= b; chmax(nsz, 1);
			vector<ld> vs;
			rep(j, f[i].size()) {
				ld val = e[i][j] * t[i][j] - t[i][j] * x;
				vs.push_back(val);
			}
			auto can3 = [&](ld vx) {
				vector<ld> pre, las;
				rep(j, f[i].size()) {
					if (vs[j] >= 0) {
						pre.push_back(f[i][j] * (vs[j]-maup));
					}
					else {
						las.push_back(-vx * f[i][j]);
					}
				}
				sort(all(pre), greater<ld>());
				sort(all(las), greater<ld>());
				vector<ld> ts;
				for (auto v : pre)ts.push_back(v);
				for (auto v : las)ts.push_back(v);
				ts.resize(nsz);
				ld sum = 0;
				rep(i, ts.size())sum += ts[i];
				return sum >= 0;
			};
			ld le = -mod17, ri = mod17;
			rep(_, 60) {
				ld mid = (le + ri) / 2;
				if (can3(mid))le = mid;
				else ri = mid;
			}
			chmax(madow, le);
		}
		//cout << x << " " << maup << " " << madow << "\n";
		ld v = maup * s + madow * c;
		return v >= 0;
	};
	ld le = 0, ri = 10000;
	rep(_, 40) {
		ld mid = (le + ri) / 2;
		if (can(mid))le = mid;
		else ri = mid;
	}
	cout << le << "\n";
}



signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	//init_f();
	//init();
	//while(true)
	//expr();
	//int t; cin >> t; rep(i, t)
	solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12072kb

input:

0 1 6
2
1
1 1 1
2
1 10 1
1 10 10

output:

6.9999999960

result:

ok found '7.0000000', expected '7.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 12056kb

input:

2 1 2
1
4
10 2 1
10 1 1
1 10 1
1 1 10

output:

5.9090909053

result:

ok found '5.9090909', expected '5.9090909', error '0.0000000'

Test #3:

score: -100
Wrong Answer
time: 1742ms
memory: 12504kb

input:

14 1000 1000
1000
30
113 80 1188
92 145 1074
130 56 1296
139 102 1142
60 76 1317
128 126 1208
73 120 1155
91 89 1197
115 64 979
80 118 592
110 97 556
83 105 578
94 51 848
98 134 757
107 138 1038
105 143 892
92 72 893
88 103 961
87 148 879
105 84 823
85 134 607
100 82 1084
199 58 801
138 85 743
214 1...

output:

1424.2190374262

result:

wrong answer 1st numbers differ - expected: '1453.3645790', found: '1424.2190374', error = '0.0200538'