oj.uz

Submission #36052

# Submission time Handle Problem Language Result Execution time Memory
36052 2017-12-05T01:06:41 Z huynd2001 Bulldozer (JOI17_bulldozer) C++14
0 / 100
 8 ms 1024 KB 
/*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 ((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 (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;
}

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1024 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 8 ms 1024 KB Output is correct
11 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1024 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 8 ms 1024 KB Output is correct
11 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1024 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 8 ms 1024 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 8 ms 1024 KB Output is correct
7 Correct 8 ms 1024 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 8 ms 1024 KB Output is correct
11 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -