#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
struct Point
{
ll x, y;
Point(ll _x = 0, ll _y = 0)
{
x = _x;
y = _y;
}
void input()
{
cin >> x >> y;
}
};
const int MAXN = 2010;
int n;
pair < Point, ll > spot[MAXN];
void input()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
spot[i].first.input();
cin >> spot[i].second;
}
}
struct Fraction
{
ll num, dev;
Fraction(ll _num = 0, ll _dev = 0)
{
num = _num;
dev = _dev;
}
void rationalize()
{
ll nod = __gcd(num, dev);
if (nod < 0)
nod = - nod;
num /= nod;
dev /= nod;
}
bool operator < (const Fraction f) const
{
/// num / dev < f.num / f.dev
return (num * f.dev) < (f.num * dev);
}
};
bool cmp(pair < Point, ll > p1, pair < Point, ll > p2)
{
if (p1.first.x != p2.first.x)
return p1.first.x < p2.first.x;
return p1.first.y > p2.first.y;
}
const ll INF = 1e18;
struct Node
{
ll val[2];
Node()
{
val[0] = INF;
val[1] = -INF;
}
};
Node unite(Node lf, Node rf)
{
Node mf;
mf.val[0] = min(lf.val[0], rf.val[0]);
mf.val[1] = max(lf.val[1], rf.val[1]);
return mf;
}
Node tree[4 * MAXN];
ll pref[MAXN];
void build(int root, int left, int right)
{
if (left == right)
{
tree[root].val[0] = tree[root].val[1] = pref[left];
return;
}
int mid = (left + right) / 2;
build(root * 2, left, mid);
build(root * 2 + 1, mid + 1, right);
tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
}
void update(int root, int left, int right, int pivot)
{
if (left == right)
{
tree[root].val[0] = tree[root].val[1] = pref[left];
return;
}
int mid = (left + right) / 2;
if (pivot <= mid)
update(root * 2, left, mid, pivot);
else
update(root * 2 + 1, mid + 1, right, pivot);
tree[root] = unite(tree[root * 2], tree[root * 2 + 1]);
}
Node query(int root, int left, int right, int qleft, int qright)
{
if (left > qright || right < qleft)
return Node();
if (left >= qleft && right <= qright)
return tree[root];
int mid = (left + right) / 2;
return unite(query(root * 2, left, mid, qleft, qright),
query(root * 2 + 1, mid + 1, right, qleft, qright));
}
int position[MAXN], swapped[MAXN][MAXN];
Fraction get_slope(Point p1, Point p2)
{
if (p1.x > p2.x)
swap(p1, p2);
Fraction slope(p2.y - p1.y, p2.x - p1.x);
slope.rationalize();
return slope;
}
void simulate()
{
if (n == 1)
{
ll result = 0;
result = max(result, spot[1].second);
cout << result << endl;
return;
}
sort(spot + 1, spot + n + 1, cmp);
for (int i = 1; i <= n; i ++)
position[i] = i;
vector < pair < Fraction, pair < int, int > > > events;
for (int i = 1; i <= n; i ++)
for (int j = i + 1; j <= n; j ++)
{
Fraction slope(spot[j].first.y - spot[i].first.y,
spot[j].first.x - spot[i].first.x);
slope.rationalize();
events.push_back({slope, {i, j}});
}
sort(events.begin(), events.end());
ll sum = 0, result = 0;
for (int i = 1; i <= n; i ++)
{
sum += spot[i].second;
if (sum < 0)
sum = 0;
result = max(result, sum);
pref[i] = pref[i - 1] + spot[i].second;
}
//cout << "begin " << tree[1].best_sum << " " << cur << endl;
build(1, 0, n);
set < pair < Fraction, int > > change;
for (int i = 1; i < n; i ++)
{
Fraction slope(spot[i + 1].first.y - spot[i].first.y,
spot[i + 1].first.x - spot[i].first.x);
slope.rationalize();
change.insert({slope, i});
}
///for (pair < Fraction, pair < ll, ll > > event : events)
while(!change.empty())
{
Fraction cur = (*change.begin()).first;
cout << "----------------" << endl;
while(!change.empty())
{
if (cur < (*change.begin()).first)
break;
int pivot = (*change.begin()).second;
//cout << "points: " << endl;
//for (int i = 1; i <= n; i ++)
//{
// cout << spot[i].first.x << " : " << spot[i].first.y << endl;
//}
//cout << "pivot " << pivot << " " << (*change.begin()).first.num << " / " << (*change.begin()).first.dev << endl;
//cout << "swap " << postion[pivot] << " : " << postion
change.erase(change.begin());
if (pivot > 1 && !swapped[position[pivot - 1]][position[pivot]])
change.erase({get_slope(spot[pivot].first, spot[pivot - 1].first), pivot - 1});
if (pivot + 2 <= n && !swapped[position[pivot + 1]][position[pivot + 2]])
change.erase({get_slope(spot[pivot + 2].first, spot[pivot + 1].first), pivot + 1});
pref[pivot] -= spot[pivot].second;
pref[pivot] += spot[pivot + 1].second;
///update(1, 0, n, pivot);
/**Node lf = query(1, 0, n, 0, pivot), rf = query(1, 0, n, pivot, n);
result = max(result, pref[pivot] - lf.val[0]);
result = max(result, rf.val[1] - pref[pivot]);*/
swapped[position[pivot]][position[pivot + 1]] = 1;
swapped[position[pivot + 1]][position[pivot]] = 1;
swap(position[pivot], position[pivot + 1]);
swap(spot[pivot], spot[pivot + 1]);
if (pivot > 1 && !swapped[position[pivot - 1]][position[pivot]])
change.insert({get_slope(spot[pivot].first, spot[pivot - 1].first), pivot - 1});
if (pivot + 2 <= n && !swapped[position[pivot + 1]][position[pivot + 2]])
change.insert({get_slope(spot[pivot + 2].first, spot[pivot + 1].first), pivot + 1});
}
sum = 0;
for (int i = 1; i <= n; i ++)
{
sum += spot[i].second;
if (sum < 0)
sum = 0;
result = max(result, sum);
}
//Fraction slope = event.first;
/**pair < ll, ll > pivots = event.second;
//cout << pivots.first << " : " << pivots.second << endl;
assert(abs(position[pivots.first] - position[pivots.second]) == 1);
int pivot = min(position[pivots.first], position[pivots.second]);
pref[pivot] -= spot[pivot].second;
pref[pivot] += spot[pivot + 1].second;
swap(spot[position[pivots.first]], spot[position[pivots.second]]);
swap(position[pivots.first], position[pivots.second]);
update(1, 0, n, pivot);
Node lf = query(1, 0, n, 0, pivot), rf = query(1, 0, n, pivot, n);
result = max(result, pref[pivot] - lf.val[0]);
result = max(result, rf.val[1] - pref[pivot]);*/
/**
sum = 0, cur = 0;;
for (int i = 1; i <= n; i ++)
{
sum += spot[i].second;
if (sum < 0)
sum = 0;
cur = max(cur, sum);
//result = max(result, sum);
}
cout << "step " << tree[1].best_sum << " " << cur << endl;*/
}
cout << result << endl;
}
void solve()
{
input();
simulate();
}
int main()
{
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
1304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
1304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
1304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
1304 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
