제출 #36045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36045		huynd2001	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	9 ms	1024 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<int,int> > v;
double cura,curb;
vector <pair<int,int> > vnone;

map <pair<int,int> ,vector <pair<int,int> > > mapu;

pair<int,int> fap(int a,int b)
{
	int k=__gcd(a,b);
	a/=k;
	b/=k;
	if(b<0) b=-b,a=-a;
	return make_pair(a,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 (y[a]*curb-cura*x[a]<y[b]*curb-cura*x[b]);
}

bool cmp3(pair<int,int> a,pair<int,int> b)
{
	if(a.first!=b.first) return (x[a.first]<x[b.first]); else return (x[a.second]<x[b.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()
{
	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(x[si]>x[sj]) swap(si,sj);
			if(mapu.find(s)==mapu.end())
			{
				mapu[s]=vnone;
				mapu[s].push_back(make_pair(si,sj));
				v.push_back(s);
			}
			else mapu[s].push_back(make_pair(si,sj));
		}
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=1;i<=n;i++) vo.push_back(i);
	cura=v[v.size()-1].first,curb=v[v.size()-1].second;
	if(curb==0) curb=1; else cura--;
	sort(vo.begin(),vo.end(),cmp2);
	for(int i=0;i<(int)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 j=0;j<vo.size();j++) cout << vo[j] << " ";
	// 		cout << endl;
	for(int i=0;i<(int)v.size()-1;i++)
	{
		vector <pair<int,int> > sub=mapu[v[i]];
		sort(sub.begin(),sub.end(),cmp3);
		for(int j=0;j<sub.size();j++)
		{
			swapy(sub[j].first,sub[j].second);
		}
		// for(int j=0;j<vo.size();j++) cout << vo[j] << " ";
		// 	cout << endl;
		ans=max(ans,it[1].val);
	}
	cout << ans << endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:163:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<sub.size();j++)
               ~^~~~~~~~~~~

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