QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#320748 | #8214. Huge Oil Platform | ucup-team197# | WA | 1ms | 4212kb | C++20 | 6.5kb | 2024-02-03 20:56:14 | 2024-02-03 20:56:15 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <utility>
#include <iomanip>
#include <cmath>
#include <random>
#include <chrono>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
ld ans = 0;
struct Point{
ll x, y, w;
ll dot(Point p) const {return x * p.x + y * p.y;}
ll cross(Point p) const {return x * p.y - y * p.x;}
};
const int N = 400 + 3;
#define all(x) (x).begin(), (x).end()
int n;
Point p[N];
ll w[N];
vector<ld> st_ys;
struct SegmentTree{
struct Node{
ld sum_w, mx;
ld best_l, best_r;
Node(){
sum_w = mx = best_l = best_r = 0;
}
friend Node merge(const Node &l, const Node &r, int idx_l, int idx_r){
int mid = (idx_l + idx_r) / 2;
Node ret;
ret.sum_w = l.sum_w + r.sum_w;
ret.best_l = max(l.best_l, l.sum_w - 2 * (st_ys[mid + 1] - st_ys[idx_l]) + r.best_l);
ret.best_r = max(r.best_r, r.sum_w - 2 * (st_ys[idx_r] - st_ys[mid]) + l.best_r);
ret.mx = max(l.mx, r.mx);
ret.mx = max(ret.mx, l.best_r + r.best_l - 2 * (st_ys[mid + 1] - st_ys[mid]));
return ret;
}
} nd[4 * N];
void init(){
for(int i = 0; i < 4 * (st_ys.size()); ++i){
nd[i] = Node();
}
}
void update(int idx, ll w, int i = 0, int l = 0, int r = (int)st_ys.size() - 1){
if(idx < l || r < idx) return;
if(l == r){
nd[i].sum_w += w;
nd[i].best_l = nd[i].best_r = nd[i].mx = nd[i].sum_w;
return;
}
int mid = (l + r) >> 1;
update(idx, w, 2 * i + 1, l, mid);
update(idx, w, 2 * i + 2, mid + 1, r);
nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2], l, r);
}
ld query(int i = 0, int l = 0, int r = (int)st_ys.size() - 1){
return nd[i].mx;
}
} st;
ld solve2(vector<ll> &ys, vector<Point> &new_p, ll mid_x, ld div){
st_ys.resize(ys.size());
ld sum_w = 0;
for(int i = 0; i < ys.size(); ++i){
st_ys[i] = ys[i] / div;
}
for(int i = 0; i < new_p.size(); ++i){
sum_w += new_p[i].w;
}
if(sum_w < ::ans){
return 0;
}
st.init();
ld ans = 0;
for(int i = 0; i < new_p.size(); ++i){
st.update(lower_bound(all(ys), new_p[i].y) - ys.begin(), new_p[i].w);
if(i == (int)new_p.size() - 1 || new_p[i].x != new_p[i + 1].x){
ld cand = -2 * (new_p[i].x - mid_x) / div;
cand += st.query();
ans = max(ans, cand);
}
}
return ans;
}
ld solve(vector<ll> &xs, vector<ll> &ys, vector<Point> &new_p, ll mid_x, ld div){
sort(all(new_p), [&](auto l, auto r){
return l.x < r.x;
});
vector<Point> left_p, right_p;
for(int i = 0; i < new_p.size(); ++i){
if(new_p[i].x >= mid_x){
right_p.push_back(new_p[i]);
}
}
for(int i = (int)new_p.size() - 1; i >= 0; --i){
if(new_p[i].x <= mid_x){
left_p.push_back(Point{-new_p[i].x, new_p[i].y, new_p[i].w});
}
}
return max(solve2(ys, left_p, -mid_x, div), solve2(ys, right_p, mid_x, div));
}
clock_t timer = clock();
bool time_left(){
return (((float)clock() - (float)timer) / (float)CLOCKS_PER_SEC) <= 7.5;
}
set<pair<ll, ll>> s;
ll gcd(ll x, ll y){
if(!y) return x;
return gcd(y, x % y);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n; ++i){
cin >> p[i].x >> p[i].y >> p[i].w;
ans = max(ans, (ld)p[i].w);
}
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
shuffle(p, p + n, mt);
for(int i = 0; i < n && time_left(); ++i){
for(int j = i + 1; j < n; ++j){
vector<Point> new_p;
Point diff{p[j].x - p[i].x, p[j].y - p[i].y, 0};
ll g = gcd(abs(diff.x), abs(diff.y));
diff.x /= g;
diff.y /= g;
if(diff.x < 0){
diff.x = -diff.x;
diff.y = -diff.y;
}
if(s.count(pair{diff.x, diff.y})){
continue;
}
s.insert(pair{diff.x, diff.y});
for(int k = 0; k < n; ++k){
new_p.push_back(Point{p[k].cross(diff), p[k].dot(diff), p[k].w});
}
ll mid_x = new_p[i].x;
vector<ll> xs, ys;
for(int k = 0; k < n; ++k){
xs.push_back(new_p[k].x);
ys.push_back(new_p[k].y);
}
sort(all(xs));
xs.resize(unique(all(xs)) - xs.begin());
sort(all(ys));
ys.resize(unique(all(ys)) - ys.begin());
ld div = sqrt((ld)diff.x * diff.x + diff.y * diff.y);
ans = max(ans, solve(xs, ys, new_p, mid_x, div));
// cout << ans << " " << i << " " << j << endl;
}
}
if(time_left()){
for(int i = -10; i <= 10; ++i){
for(int j = -10; j <= 10; ++j){
if(!i && !j) continue;
vector<Point> new_p;
Point diff{i, j, 0};
ll g = gcd(abs(diff.x), abs(diff.y));
diff.x /= g;
diff.y /= g;
if(diff.x < 0){
diff.x = -diff.x;
diff.y = -diff.y;
}
if(s.count(pair{diff.x, diff.y})){
continue;
}
s.insert(pair{diff.x, diff.y});
for(int k = 0; k < n; ++k){
new_p.push_back(Point{p[k].cross(diff), p[k].dot(diff), p[k].w});
}
ll mid_x = new_p[i].x;
vector<ll> xs, ys;
for(int k = 0; k < n; ++k){
xs.push_back(new_p[k].x);
ys.push_back(new_p[k].y);
}
sort(all(xs));
xs.resize(unique(all(xs)) - xs.begin());
sort(all(ys));
ys.resize(unique(all(ys)) - ys.begin());
ld div = sqrt((ld)diff.x * diff.x + diff.y * diff.y);
ans = max(ans, solve(xs, ys, new_p, mid_x, div));
// cout << ans << " " << i << " " << j << endl;
}
}
}
cout << fixed << setprecision(12) << ans << "\n";
}
/*
4
1 1 10
1 7 10
4 3 10
2 8 10
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4212kb
input:
2 1 1 1 3 3 1
output:
1170281760988008689.750000000000
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '1170281760988008704.0000000', error = '1170281760988008704.0000000'