Submission #48581

#	Time	Username	Problem	Language	Result	Execution time	Memory
48581		Namnamseo	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	1848 ms	94664 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

#define DBG if(0)

int n;

typedef tuple<int,int,int> Mine;

Mine p[2010];

struct Kumi {
	ll x, y;
	Kumi(ll x_=0, ll y_=0){
		x = x_; y = y_;
		if((x<0 && y==0) || y<0) x=-x, y=-y;
	}
	bool operator<(const Kumi& r) const {
		return x*r.y > y*r.x;
	}
	bool operator==(const Kumi& r) const {
		return x*r.y == y*r.x;
	}
};

void in(){
	read(n);
	//n = 2e3;
	//assert(RAND_MAX == 32767);
	for(int i=1; i<=n; ++i){
		if(1){
			int x, y, z; read(x, y, z);
			p[i] = make_tuple(x, y, z);
		} else {
			for(;;){
				int x=rand();
				int y=rand();
				//int x = (rand() << 15) + rand();
				//int y = (rand() << 15) + rand();
				x = min(x, int(1e9));
				y = min(y, int(1e9));
				bool flg=1;
				for(int j=1; j<i; ++j)
				if(get<0>(p[j]) == x && get<1>(p[j]) == y){
					flg=0;
					break;
				}
				if(flg){
					p[i] = make_tuple(x, y, min(int(1e9), 
					//	(rand()<<15) + rand()
						rand()
					));
					break;
				}
			}
		}
	}
}

Kumi operator-(const Mine& a, const Mine& b){
	return {get<1>(b)-get<1>(a), get<0>(a)-get<0>(b)};
}

pair<Kumi, int> kumis[2001*2000];
int Kn;

void Build(){
	for(int i=1; i<n; ++i){
		for(int j=i+1; j<=n; ++j){
			kumis[Kn++]= make_pair(p[i]-p[j], i);
			kumis[Kn++]= make_pair(p[i]-p[j], j);
		}
	}
	sort(kumis, kumis+Kn);
	Kn = unique(kumis, kumis+Kn) - kumis;
}

int ind[2010];
int rev[2010];

struct CuteSegtree {
	static const int M = 2048;
	ll sum[M<<1];
	ll ls[M<<1];
	ll rs[M<<1];
	ll mg[M<<1];
	int l[M<<1];
	int r[M<<1];
	void init(int L=1, int R=n, int p=1){
		l[p]=L; r[p]=R;
		if(L == R) return;
		int mid=(L+R)/2;
		init(L, mid, p*2);
		init(mid+1, R, p*2+1);
	}
	void put(int pt, ll v){
		int p=1;
		while(true){
			if(l[p] == r[p]) break;
			int mid=(l[p]+r[p])/2;
			p*=2;
			if(mid<pt) ++p;
		}
		sum[p] = v;
		ls[p] = rs[p] = mg[p] = max(0LL, v);
		p/=2;
		while(p){
			sum[p] = sum[p*2] + sum[p*2+1];
			ls[p] = max(ls[p*2], sum[p*2] + ls[p*2+1]);
			rs[p] = max(rs[p*2+1], sum[p*2+1] + rs[p*2]);
			mg[p] = max(rs[p*2] + ls[p*2+1], max(mg[p*2], mg[p*2+1]));
			p/=2;
		}
	}
	/*void put(int pt, ll v, int l=1, int r=n, int p=1){
		if(l == r){
			sum[p] = v;
			ls[p] = rs[p] = mg[p] = max(0LL, v);
			return;
		}
		int mid=(l+r)/2;
		if(pt <= mid) put(pt, v, l, mid, p*2); else put(pt, v, mid+1, r, p*2+1);
		sum[p] = sum[p*2] + sum[p*2+1];
		ls[p] = max(ls[p*2], sum[p*2] + ls[p*2+1]);
		rs[p] = max(rs[p*2+1], sum[p*2+1] + rs[p*2]);
		mg[p] = max(rs[p*2] + ls[p*2+1], max(mg[p*2], mg[p*2+1]));
	}*/
} seg;

int main()
{
	in();
	for(int i=1; i<=n; ++i) ind[i] = i;
	sort(ind+1, ind+n+1, [&](const int& a, const int& b){
		ll ax, ay; tie(ax, ay, ignore) = p[a];
		ll bx, by; tie(bx, by, ignore) = p[b];
		return ax < bx;
	});
	DBG { printf("Initial: "); for(int i=1; i<=n; ++i) printf("%d ", ind[i]); putchar(10); }
	seg.init();
	for(int i=1; i<=n; ++i){
		seg.put(i, get<2>(p[ind[i]]));
		rev[ind[i]]=i;
	}
	ll ans = seg.mg[1];
	Build();
	if(1) for(int i=0; i<Kn;){
		int j=i;
		vector<int> v;
		for(;j<Kn && kumis[i].x == kumis[j].x; ++j) v.pb(kumis[j].y);
		ll ccx = kumis[i].x.x, ccy=kumis[i].x.y;
		DBG { printf("Swap by %lld,%lld : ", ccx, ccy); for(int t:v) printf("%d ", t); putchar(10); }
		sort(all(v), [&](const int& a, const int& b){
			ll va = ccx*get<0>(p[a]) + ccy*get<1>(p[a]);
			ll vb = ccx*get<0>(p[b]) + ccy*get<1>(p[b]);
			if(va != vb) return va<vb;
			va = -ccy*get<0>(p[a]) + ccx*get<1>(p[a]);
			vb = -ccy*get<0>(p[b]) + ccx*get<1>(p[b]);
			return va < vb;
		});
		v.erase(unique(all(v)), v.end());
		//0.9s
		
		vector<int> indices;
		for(int t:v) indices.pb(rev[t]);
		sort(all(indices)); // 0.2s
		
		int m = indices.size();
		for(int i=0; i<m; ++i){
			ind[indices[i]]=v[i];
			rev[v[i]]=indices[i];
			seg.put(indices[i], get<2>(p[v[i]]));
		}
		ans = max(ans, seg.mg[1]);
		DBG { printf("Resulting: "); for(int i=1; i<=n; ++i) printf("%d ", ind[i]); putchar(10); }
		i=j;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'void read(int&)':
bulldozer.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
bulldozer.cpp: In function 'void read(ll&)':
bulldozer.cpp:7:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~

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