oj.uz

답안 #514563

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
514563 2022-01-18T09:19:53 Z amunduzbaev Bulldozer (JOI17_bulldozer) C++14
0 / 100
 2 ms 944 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array

const int N = 2005;
long double const eps = 1e-16;

struct ST{
	ar<long long, 4> tree[N * 4];
	void merge(ar<long long, 4>& x, ar<long long, 4>& a, ar<long long, 4>& b){
		x[0] = max({a[0], b[0], a[2] + b[1]});
		x[1] = max({a[1], a[3] + b[1]});
		x[2] = max({b[2], b[3] + a[2]});
		x[3] = a[3] + b[3];
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){ 
			tree[x] = {max(v, 0), max(v, 0), max(v, 0), v}; return;
		} int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		merge(tree[x], tree[x<<1], tree[x<<1|1]);
	}
}tree;

/*

5
5 1 5
4 2 2
3 3 -2
2 4 3
1 5 -1

6
2 2 10
4 1 10
5 2 10
2 5 10
4 4 -5
5 5 10

*/

long long res;
struct node{
	int s, x, y, i, j;
};

node get(int x, int y){
	node res;
	if(x < 0 && y < 0) x *= -1, y *= -1;
	res.s = (x < 0 || y < 0) * -1;
	res.x = x, res.y = y;
	return res;
}
bool operator < (node& a, node& b){
	if(a.s != b.s) return a.s < b.s;
	if(a.s < 0) swap(a, b);
	return (a.x * b.y < b.x * a.y);
}

void check(vector<ar<int, 3>>& a, int n){
	sort(a.begin(), a.end(), [&](auto& a, auto& b){
		if(a[0] != b[0]) return a[0] < b[0];
		return a[1] > b[1];
	});
	vector<node> tt;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(a[i][0] == a[j][0]) continue;
			tt.push_back(get(a[j][1] - a[i][1], a[i][0] - a[j][0]));
			tt.back().i = i, tt.back().j = j;
		}
	} vector<int> pos(n), used(n);
	for(int i=0;i<n;i++) pos[i] = i, tree.sett(i, a[i][2]);
	res = max(res, tree.tree[1][0]);
	sort(tt.begin(), tt.end()); //{
	for(int l=0;l<(int)tt.size();){
		int k = l;
		while(k < (int)tt.size() && !(tt[l] < tt[k])){
			int i = tt[k].i, j = tt[k].j; k++;
			swap(pos[i], pos[j]);
			tree.sett(pos[i], a[i][2]), 
			tree.sett(pos[j], a[j][2]);
		} while(l < k) used[tt[l].i] = used[tt[l].j] = 0, l++;
		res = max(res, tree.tree[1][0]);
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 3>> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	} 
	
	check(a, n);
	for(auto& x : a) swap(x[0], x[1]);
	check(a, n);
	cout<<res<<"\n";
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Incorrect 2 ms 560 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Incorrect 2 ms 560 KB Output isn't correct
6 Halted 0 ms 0 KB -