Submission #36073

#	Time	Username	Problem	Language	Result	Execution time	Memory
36073		huynd2001	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1797 ms	160412 KiB

bulldozer

/*huypheu
15
10 3 30
5 10 -17
4 -5 14
0 -3 -9
-2 3 17
6 9 -19
-9 -6 -14
-2 -3 10
-3 -3 30
8 1 -28
9 -9 -5
7 -5 -24
-8 -10 5
-7 2 20
10 -3 -13
*/

//https://oj.uz/problem/view/JOI17_bulldozer
#include <bits/stdc++.h>
#define int long long
#define oo (LLONG_MAX/2)
using namespace std;

struct ite
{
	int val,lef,rig,tot;
}it[100007];

int x[20007],y[20007];
int pos[20007];
int c[20007],ar[20007];

void build(int node,int l,int r)
{
	if(l>r) return ;
	if(l==r)
	{
		it[node].lef=max(0ll,ar[l]);
		it[node].rig=max(0ll,ar[l]);
		it[node].tot=ar[l];
		it[node].val=max(0ll,ar[l]);
		return ;
	}
	int mid=(l+r)/2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
	it[node].lef=max(it[node*2].lef,it[node*2].tot+it[node*2+1].lef);
	it[node].rig=max(it[node*2+1].rig,it[node*2+1].tot+it[node*2].rig);
	it[node].tot=it[node*2].tot+it[node*2+1].tot;
	it[node].val=max(it[node*2].rig+it[node*2+1].lef,max(it[node*2].val,it[node*2+1].val));
	return ;
}

void update(int node,int l,int r,int m,int p)
{
	if(l>r) return ;
	if(l==r)
	{
		it[node].lef=max(0ll,p);
		it[node].rig=max(0ll,p);
		it[node].tot=p;
		it[node].val=max(0ll,p);
		return ;
	}
	int mid=(l+r)/2;
	if(m<=mid) update(node*2,l,mid,m,p); else update(node*2+1,mid+1,r,m,p);
	it[node].lef=max(it[node*2].lef,it[node*2].tot+it[node*2+1].lef);
	it[node].rig=max(it[node*2+1].rig,it[node*2+1].tot+it[node*2].rig);
	it[node].tot=it[node*2].tot+it[node*2+1].tot;
	it[node].val=max(it[node*2].rig+it[node*2+1].lef,max(it[node*2].val,it[node*2+1].val));
	return ;
}
	vector <int> vo;
	vector <pair<pair<int,int> ,pair<int,int> > > va;
double cura,curb;
vector <pair<int,int> > vnone;

map <pair<int,int> ,int> mapu;
vector <pair<int,int> > vip[4000007];

pair<int,int> fap(int a,int b)
{
	if(b==0) return make_pair(1,0);
	int k=__gcd(a,b);
	a/=k;
	b/=k;
	if(b<0) b=-b,a=-a;
	return make_pair(a,b);
}

bool kem_hon(int a,int b)
{
	if(x[a]!=x[b]) return (x[a]<x[b]); else return (y[a]<y[b]);
}

bool cmp(pair<int,int> a,pair<int,int> b)
{
	return (a.first*b.second>b.first*a.second);
}

bool cmp2(int a,int b)
{
	return ((double)y[a]/(double)cura-(double)x[a]/(double)curb<(double)y[b]/(double)cura-(double)x[b]/(double)curb);
}

bool cmp3(pair<int,int> a,pair<int,int> b)
{
	if(a.first!=b.first) return kem_hon(a.first,b.first); else return kem_hon(a.second,b.second);
}

bool cmp4(pair<pair<int,int>,pair<int,int> > x,pair<pair<int,int>,pair<int,int> > y)
{
	if(x.first!=y.first) return cmp(x.first,y.first); else return cmp3(x.second,y.second);
}

int n;

void swapy(int a,int b)
{
	int c,d;
	c=pos[a],d=pos[b];
	update(1,1,n,d,ar[c]);
	update(1,1,n,c,ar[d]);
	swap(ar[c],ar[d]);
	swap(pos[a],pos[b]);
	swap(vo[pos[a]-1],vo[pos[b]-1]);
	return ;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> x[i] >> y[i] >> c[i];
	}
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			pair<int,int> s;
			s=fap((y[j]-y[i]),(x[j]-x[i]));
			int si=i,sj=j;
			if(kem_hon(sj,si)) swap(si,sj);
			va.push_back(make_pair(s,make_pair(si,sj)));
		}
	}
	sort(va.begin(),va.end(),cmp4);
	// for(int i=0;i<va.size();i++) cout << va[i].first.first << "/" << va[i].first.second << endl;
	for(int i=1;i<=n;i++) vo.push_back(i);
		cura=1,curb=0;
	if(va.size()>0) cura=va[va.size()-1].first.first,curb=va[va.size()-1].first.second;
	// cout << cura << "/" << curb << endl;
	if(curb==0) curb=1; else cura--;
	sort(vo.begin(),vo.end(),cmp2);
	for(int i=0;i<vo.size();i++)
	{
		pos[vo[i]]=i+1;
		ar[i+1]=c[vo[i]];
	}
	build(1,1,n);
	int ans=it[1].val;
	// for(int i=0;i<vo.size();i++) cout << vo[i] << " ";cout << endl;
	for(int i=0;i<va.size();i++)
	{
		swapy(va[i].second.first,va[i].second.second);
		// for(int i=0;i<vo.size();i++) cout << vo[i] << " ";cout << endl;
		if(i==va.size()-1 || va[i].first!=va[i+1].first) ans=max(ans,it[1].val);
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:160:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vo.size();i++)
              ~^~~~~~~~~~
bulldozer.cpp:168:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<va.size();i++)
              ~^~~~~~~~~~
bulldozer.cpp:172:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i==va.size()-1 || va[i].first!=va[i+1].first) ans=max(ans,it[1].val);
      ~^~~~~~~~~~~~~

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