Submission #583692

#	Time	Username	Problem	Language	Result	Execution time	Memory
583692		HIR180	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1158 ms	102064 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i=0;i<n;i++)
typedef pair<int,int> P;
typedef pair<int, P> P1;
#define a first
#define b second
#define mp make_pair
#define eb emplace_back
template<class t>using vc = vector<t>;
using S = array<int, 4>;

S op(S a, S b){
	S c{};
	c[3] = a[3] + b[3];
	c[2] = max(b[2], a[2]+b[3]);
	c[1] = max(a[1], a[3]+b[1]);
	c[0] = max(max(a[0], b[0]), a[2]+b[1]);
	return c;
}
S e(){
	return S{(int)-1e18, (int)-1e18, (int)-1e18, 0};
}
S seg[1<<12];
void update(int pos, S a){
	pos += (1<<11)-1;
	seg[pos] = a;
	while(pos){
		pos = (pos-1) / 2;
		seg[pos] = op(seg[pos*2+1], seg[pos*2+2]);
	}
}
int n, x[2005], y[2005], c[2005];
P dir[2005][2005];

signed main(){
	cin >> n;
	vc<P1>vec(n);
	rep(i, n) cin >> vec[i].b.a >> vec[i].b.b >> vec[i].a;
	
	sort(vec.begin(), vec.end(), [](P1 a, P1 b){
		return mp(a.b.b, a.b.a) < mp(b.b.b, b.b.a);
	});
	
	using d = long double;
	vc<pair<d,P>>ev;
	
	rep(i, n) for(int j=i+1;j<n;j++){
		auto p1 = vec[i].b;
		auto p2 = vec[j].b;
		if(p1 > p2) swap(p1, p2);
		int dx = p2.a - p1.a;
		int dy = p2.b - p1.b;
		
		if(p1.b <= p2.b){
			ev.eb(atan2((d)dy, (d)dx), mp(i, j));
			dir[i][j] = mp(dx, dy);
		}
		else{
			ev.eb(atan2((d)dy*-1, (d)dx*-1), mp(i, j));
			dir[i][j] = mp(-dx, -dy);
		}
	}
	
	sort(ev.begin(), ev.end());
	rep(i, (1<<12)) seg[i] = e();
	rep(i, n){
		int a = vec[i].a;
		update(i,S{max(0LL,a), max(0LL,a), max(0LL,a), a});
	}
	vc<int>rev(n);
	rep(i, n) rev[i] = i;
	
	int ans = seg[0][0];
	rep(_, ev.size()){
		d deg = ev[_].a;
		int u = ev[_].b.a;
		int v = ev[_].b.b;
		//swap
		update(rev[u], S{max(0LL, vec[v].a), max(0LL, vec[v].a), max(0LL, vec[v].a), vec[v].a});
		update(rev[v], S{max(0LL, vec[u].a), max(0LL, vec[u].a), max(0LL, vec[u].a), vec[u].a});
		
		swap(rev[u], rev[v]);
		
		bool ok = (_+1 == ev.size());
		if(!ok){
			P p = dir[ev[_].b.a][ev[_].b.b];
			P q = dir[ev[_+1].b.a][ev[_+1].b.b];
			
			if(p.b * q.a != p.a * q.b) ok = true;
			if(p.a * q.a + p.b * q.b < 0) ok = true;
		}
		if(ok){
			ans = max(ans, seg[0][0]);
		}
	}
	cout << ans << '\n';
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:4:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> >, std::allocator<std::pair<long double, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i, n) for(int i=0;i<n;i++)
......
   76 |  rep(_, ev.size()){
      |      ~~~~~~~~~~~~               
bulldozer.cpp:76:2: note: in expansion of macro 'rep'
   76 |  rep(_, ev.size()){
      |  ^~~
bulldozer.cpp:86:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> >, std::allocator<std::pair<long double, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   bool ok = (_+1 == ev.size());
      |              ~~~~^~~~~~~~~~~~
bulldozer.cpp:77:5: warning: unused variable 'deg' [-Wunused-variable]
   77 |   d deg = ev[_].a;
      |     ^~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 35 / 35
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20