Submission #96061

#	Time	Username	Problem	Language	Result	Execution time	Memory
96061		HIR180	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1771 ms	133812 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,cur;
int x[4005],y[4005],w[4005];
vector<pair<P,vector<int> > >vi;
P1 za[4005];
bool cmp(const int&p,const int&q){
	//cur-p-q
	P a = za[cur].fi,b = za[p].fi,c = za[q].fi;
	ll val = 1LL*(b.fi-a.fi)*(c.sc-a.sc)-1LL*(b.sc-a.sc)*(c.fi-a.fi);
	if(val) return val > 0LL;
	else return 1LL*(b.fi-a.fi)*(b.fi-a.fi)+1LL*(b.sc-a.sc)*(b.sc-a.sc) < 1LL*(c.fi-a.fi)*(c.fi-a.fi)+1LL*(c.sc-a.sc)*(c.sc-a.sc);
}
bool eq(P a,P b,P c){
	return 1LL*(b.fi-a.fi)*(c.sc-a.sc)-1LL*(b.sc-a.sc)*(c.fi-a.fi) == 0;
}
bool cmp2(const pair<P,vector<int> >&p,const pair<P,vector<int> >&q){
	P a = mp(0,0),b = p.fi,c = q.fi;
	ll val = 1LL*(b.fi-a.fi)*(c.sc-a.sc)-1LL*(b.sc-a.sc)*(c.fi-a.fi);
	return val > 0ll;
}
bool cmp3(const P1 &a,const P1&b){
	if(a.fi.sc != b.fi.sc){
		return a.fi.sc < b.fi.sc;
	}
	else{
		return a.fi.fi > b.fi.fi;
	}
}
int rev[4005],now[4005]; //rev[i] .. where is node i on segtree

struct segtree{
	ll seg[(1<<13)],L[(1<<13)],R[(1<<13)],sum[(1<<13)];
	void update(int k,int val){
		k += (1<<12)-1;
		seg[k] = max(0ll,1LL*val);
		L[k] = max(0ll,1LL*val);
		R[k] = max(0ll,1LL*val);
		sum[k] = 1LL*val;
		
		while(k>0){
			k = (k-1)/2;
			sum[k] = sum[k*2+1]+sum[k*2+2];
			L[k] = max(L[k*2+1],sum[k*2+1]+L[k*2+2]);
			R[k] = max(R[k*2+2],sum[k*2+2]+R[k*2+1]);
			seg[k] = max(max(seg[k*2+1],seg[k*2+2]),R[k*2+1]+L[k*2+2]);
		}
	}
	ll query(){ return seg[0]; }
	int get(int k){ return sum[k+(1<<12)-1]; }
}seg;
bool used[4005][4005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&x[i],&y[i],&w[i]);
		za[i] = mp(mp(x[i],y[i]),i);
	}
	sort(za+1,za+n+1,cmp3);
	for(int i=1;i<=n;i++){
		vector<int>vec;
		for(int j=i+1;j<=n;j++){
			int X = za[j].fi.fi-za[i].fi.fi,Y = za[j].fi.sc-za[i].fi.sc;
			{
				vec.push_back(j);
			}
		}
		cur = i;
		sort(vec.begin(),vec.end(),cmp);
		vector<int>L; L.clear(); L.pb(za[i].sc);
		for(int j=0;j<vec.size();j++){
			L.pb(za[vec[j]].sc);
			if(j+1 != vec.size() && eq(za[i].fi,za[vec[j]].fi,za[vec[j+1]].fi)){
				continue;
			}
			if(used[L[0]][L[1]]) {L.clear(); L.pb(za[i].sc); continue;}
			P p = mp(za[vec[j]].fi.fi-za[i].fi.fi,za[vec[j]].fi.sc-za[i].fi.sc);
			vi.pb(mp(p,L));
			for(int k=0;k<L.size();k++) for(int l=k+1;l<L.size();l++) used[L[k]][L[l]] = used[L[l]][L[k]] = 1;
			L.clear(); L.pb(za[i].sc);
		}
	}
	sort(vi.begin(),vi.end(),cmp2);
	//0+eps kara start
//	sort(za+1,za+n+1,cmp3);
	for(int i=1;i<=n;i++){
		seg.update(i,1LL*w[za[i].sc]);
		rev[za[i].sc] = i; now[i] = za[i].sc;
	}
	ll ans = seg.query();
	for(int i=0;i<vi.size();i++){
		vector<int>&hoge = vi[i].sc;
		int e = -1;
		for(int j=0;j<hoge.size();j++){
			int hs = hoge.size(); int f = rev[hoge[hs-1-j]];
			assert(e==-1 || abs(e-f) == 1); e = f;
			seg.update(rev[hoge[j]],w[now[f]]);
		}
		for(int j=0;;j++){
			int hs = hoge.size();
			int f = rev[hoge[j]],g = rev[hoge[hs-1-j]];
			if(0 >= hs-1-j*2) break;
			swap(now[f],now[g]);
			swap(rev[hoge[j]],rev[hoge[hs-1-j]]);
		}
		if(i+1 != vi.size() && eq(mp(0,0),vi[i].fi,vi[i+1].fi)) continue;
		ans = max(ans,seg.query());
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:79:8: warning: unused variable 'X' [-Wunused-variable]
    int X = za[j].fi.fi-za[i].fi.fi,Y = za[j].fi.sc-za[i].fi.sc;
        ^
bulldozer.cpp:79:36: warning: unused variable 'Y' [-Wunused-variable]
    int X = za[j].fi.fi-za[i].fi.fi,Y = za[j].fi.sc-za[i].fi.sc;
                                    ^
bulldozer.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<vec.size();j++){
               ~^~~~~~~~~~~
bulldozer.cpp:89:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(j+1 != vec.size() && eq(za[i].fi,za[vec[j]].fi,za[vec[j+1]].fi)){
       ~~~~^~~~~~~~~~~~~
bulldozer.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<L.size();k++) for(int l=k+1;l<L.size();l++) used[L[k]][L[l]] = used[L[l]][L[k]] = 1;
                ~^~~~~~~~~
bulldozer.cpp:95:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<L.size();k++) for(int l=k+1;l<L.size();l++) used[L[k]][L[l]] = used[L[l]][L[k]] = 1;
                                              ~^~~~~~~~~
bulldozer.cpp:107:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vi.size();i++){
              ~^~~~~~~~~~
bulldozer.cpp:110:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<hoge.size();j++){
               ~^~~~~~~~~~~~
bulldozer.cpp:122:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i+1 != vi.size() && eq(mp(0,0),vi[i].fi,vi[i+1].fi)) continue;
      ~~~~^~~~~~~~~~~~
bulldozer.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
bulldozer.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&x[i],&y[i],&w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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