Submission #26581

#	Time	Username	Problem	Language	Result	Execution time	Memory
26581		dwarn	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2061 ms	217712 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define all(v) (v).begin(),(v).end()
#define trav(x,v) for(auto &x : (v))
#define sz(v) (int)(v).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

struct ST {
	int n;
	vector<ll> sum, mx, mn, ans;
	ST(int _n) : n(_n){
		while(__builtin_popcount(n) > 1) ++n;
		sum.resize(2*n);
		mn.resize(2*n);
		mx.resize(2*n);
		ans.resize(2*n);
	}
	void upd(ll dif, int pos){
		for(pos += n; pos; pos /= 2){
			sum[pos] += dif;
			mn[pos] = min(0LL, sum[pos]);
			ans[pos] = mx[pos] = max(0LL, sum[pos]);
			if(pos < n){
				mn[pos] = min(mn[pos], min(mn[2*pos], sum[2*pos]+mn[2*pos+1]));
				mx[pos] = max(mx[pos], max(mx[2*pos], sum[2*pos]+mx[2*pos+1]));

				ans[pos] = max(ans[pos], max(ans[2*pos],ans[2*pos+1]));
				ans[pos] = max(ans[pos], mx[2*pos+1]+sum[2*pos]-mn[2*pos]);
			}
		}
	}
};

int ren[int(4e6)];
vector<vi> ls[int(2e6+10)];
int pos[int(2e6+10)], xs[2000], ys[2000], zs[2000];

int main(){
	rep(i,0,2e6+10) pos[i] = -1;

	int n;
	scanf("%d",&n);

	rep(i,0,n) scanf("%d %d %d",xs+i,ys+i,zs+i);

	auto vec = [&](int i, int j){
		int dx = xs[i]-xs[j], dy = ys[i]-ys[j];
		int g = dy==0 ? dx : __gcd(dx, dy);
		dx /= g, dy /= g;
		if(dx<0 || (dx==0 && dy<0)){
			dx = -dx, dy = -dy;
		}
		return pii(dx,dy);
	};

	vector<pair<pii,int>> vs;

	rep(i,0,n) rep(j,0,i){
		vs.emplace_back(vec(i,j), i*n+j);
	}
	sort(all(vs), [&](pair<pii,int> &a, pair<pii,int> &b){
		return (ll)a.first.second*b.first.first-(ll)a.first.first*b.first.second>0;
	});
	int num = 0;
	for(int l = 0, r = 0; l < sz(vs); l = r){
		while(r < sz(vs) && vs[l].first == vs[r].first) ++r;
		rep(k,l,r) ren[vs[k].second] = num;
		++num;
	}

	rep(i,0,n){
		rep(j,0,i) pos[ren[i*n+j]] = -2;
		rep(j,i+1,n){
			int r = ren[n*j+i];
			if(pos[r] == -2) continue;
			if(pos[r] == -1){
				pos[r] = sz(ls[r]);
				ls[r].push_back(vi(1,i));
			}
			ls[r][pos[r]].push_back(j);
		}
		rep(j,0,i) pos[ren[i*n+j]] = -1;
		rep(j,i+1,n) pos[ren[j*n+i]] = -1;
	}

	vi perm(n);
	rep(i,0,n) perm[i] = i;
	sort(all(perm), [&](int i, int j){
		return xs[i]<xs[j]||(xs[i]==xs[j] && ys[i]<ys[j]);
	});
	vi mynum(n);
	rep(i,0,n) mynum[perm[i]] = i;
	ST tree(n);
	rep(i,0,n)
		tree.upd(zs[i], mynum[i]);
	ll ans = tree.ans[1];

	vector<ll> todo(n);
	rep(i,0,num){
		trav(v, ls[i]){
			int mn = n+1, mx = -1;
			trav(k, v){
				mn = min(mynum[k], mn);
				mx = max(mynum[k], mx);
			}

			trav(k, v)
				todo[mynum[k]] = -zs[k];

			trav(k, v)
				mynum[k] = mx + mn - mynum[k];

			trav(k, v)
				tree.upd(todo[mynum[k]] + zs[k], mynum[k]);
			trav(k, v) todo[mynum[k]] = 0;

		}
		ans = max(ans, tree.ans[1]);
	}

	printf("%lld\n",ans);
	exit(0);

}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bulldozer.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i,0,n) scanf("%d %d %d",xs+i,ys+i,zs+i);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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