| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1022357 | 0npata | Bulldozer (JOI17_bulldozer) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
include<bits/stdc++.h>
using namespace std;
#define float long double
#define int long long
const float PI = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679;
#define vec vector
struct SegNode {
int max_sss = 0;
int max_pref_sum = 0;
int max_suf_sum = 0;
int sum = 0;
SegNode merge(SegNode other) {
return {max(max(max_sss, other.max_sss), max_suf_sum+other.max_pref_sum),
max(max_pref_sum, sum+other.max_pref_sum),
max(other.max_suf_sum, max_suf_sum + other.sum),
sum + other.sum};
}
};
struct SegTree {
int n;
vec<SegNode> data;
SegTree(int in) {
n = 1;
while(n < in) n *= 2;
data = vec<SegNode>(n*2);
}
void set(int i, int val) {
i += n;
data[i] = SegNode {max(val, 0LL), max(val, 0LL), max(val, 0LL), val};
while(i > 1) {
i /= 2;
data[i] = data[i*2].merge(data[i*2+1]);
}
}
SegNode query(int l, int r, int i = 1, int ll = 0, int rr = -1) {
if(rr == -1) rr = n;
if(ll >= r || rr <= l) return {};
if(ll >= l && rr <= r) return data[i];
int mid = (ll+rr)/2;
return query(l, r, i*2, ll, mid).merge(query(l, r, i*2+1, mid, rr));
}
};
struct Point {
int x;
int y;
int w;
int i;
};
float angle(Point p1, Point p2) {
Point dif = {p2.x-p1.x, p2.y-p1.y};
return atan2(dif.y, dif.x);
}
float norm_angle(float angle) {
while(angle >= (float)2*PI) angle -= (float)2*PI;
return angle;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vec<Point> ps(n);
for(int i = 0; i<n; i++) {
cin >> ps[i].x >> ps[i].y >> ps[i].w;
}
auto comp_point = [](Point p1, Point p2) {
return p1.x == p2.x ? p1.y < p2.y : p1.x < p2.x;
};
sort(ps.begin(), ps.end(), comp_point);
for(int i = 0; i<n; i++) ps[i].i = i;
vec<pair<float, pair<int, int>>> evs(0);
for(int i = 0; i<n; i++) {
for(int j = i+1; j<n; j++) {
float cur_angle = angle(ps[i], ps[j]);
//cerr << "ANGLE: " << cur_angle << '\n';
float t1 = ((float)3)/2 * PI;
float t2 = ((float)1)/2 * PI;
float dif1 = (t1 + (float)2*PI) - cur_angle;
float dif2 = (t2 + (float)2*PI) - cur_angle;
dif1 = norm_angle(dif1);
dif2 = norm_angle(dif2);
// cerr << dif1 << ' ' << dif2 << '\n';
evs.push_back({dif1, {i, j}});
evs.push_back({dif2, {i, j}});
}
}
sort(evs.begin(), evs.end(), [&](auto ev1, auto ev2) {
if(ev1.first - ev2.first == 0) {
if(ev1.second.first == ev2.second.first) {
return comp_point(ps[ev1.second.second], ps[ev2.second.second]);
}
else {
return comp_point(ps[ev1.second.first], ps[ev2.second.first]);
}
}
else {
return ev1.first < ev2.first;
}
});
//vec<int> ap(n);
//iota(ap.begin(), ap.end(), 0);
int ans = 0;
SegTree st(n);
for(int i = 0; i<n; i++) st.set(i, ps[i].w);
auto eval = [&]() {
int mx = st.query(0, n).max_sss;
//cerr << mx << '\n';
ans = max(mx, ans);
};
evs.push_back({1'000, {}});
eval();
for(int ei = 0; ei < evs.size()-1; ei++) {
auto ev = evs[ei];
int i = ev.second.first;
int j = ev.second.second;
int temp = ps[i].i;
ps[i].i = ps[j].i;
ps[j].i = temp;
//cerr << "swapping: " << i << ' ' << j << " at angle: " << ev.first << '\n';
st.set(ps[i].i, ps[i].w);
st.set(ps[j].i, ps[j].w);
//swap(ap[ps[i].i], ap[ps[j].i]);
if(evs[ei+1].first - evs[ei].first == 0) continue;
eval();
}
//eval();
cout << ans << '\n';
}