제출 #101017

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101017		autumn_eel	Bulldozer (JOI17_bulldozer)	C++14	20 / 100	32 ms	512 KiB

bulldozer

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

struct Point{
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
};
double norm(Point p){
	return p.x*p.x+p.y*p.y;
}
double abs(Point p){
	return sqrt(norm(p));
}

Point operator-(Point a,Point b){
	return Point(b.x-a.x,b.y-a.y);
}
double det(Point a,Point b){
	return a.x*b.y-a.y*b.x;
}

struct Line{
	Point a,b;
	Line(){}
	Line(Point a,Point b):a(a),b(b){}
};
double dist(Line l,Point p){
	return det(p-l.a,l.b-l.a)/abs(l.b-l.a);
}


Point p[200];
ll w[200];

int main(){
	int n;cin>>n;
	if(n>100)abort();
	bool ok=true;
	rep(i,n){
		scanf("%lf%lf%lld",&p[i].x,&p[i].y,&w[i]);
		if(p[i].y){
			ok=false;
		}
	}
	if(n==1){
		cout<<max(w[0],0LL)<<endl;
		return 0;
	}
	if(ok){
		vector<pair<double,int>>v;
		rep(i,n){
			v.push_back(make_pair(p[i].x,w[i]));
		}
		sort(v.begin(),v.end());
		ll Max=0;
		rep(i,n){
			ll sum=0;
			for(int j=i;j<n;j++){
				sum+=w[j];
				Max=max(Max,sum);
			}
		}
		cout<<Max<<endl;
		return 0;
	}
	ll ans=0;
	rep(i,n)for(int j=i+1;j<n;j++){
		Line l(p[i],p[j]);
		vector<pair<double,int>>v;
		for(int k=0;k<n;k++){
			v.push_back(make_pair(dist(l,p[k]),w[k]));
		}
		sort(v.begin(),v.end());
		ll Min=0,sum=0,Max=0;
		int id=-1;
		rep(i,v.size()){
			sum+=v[i].second;
			Max=max(Max,sum-Min);
			Min=min(Min,sum);
			if(v[i].first==0)id=i;
		}
		swap(v[id-1],v[id]);
		Min=0,sum=0,Max=0;
		rep(i,v.size()){
			sum+=v[i].second;
			Max=max(Max,sum-Min);
			Min=min(Min,sum);
		}
		ans=max(ans,Max);
	}
	cout<<ans<<endl;
}

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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
bulldozer.cpp:80:3: note: in expansion of macro 'rep'
   rep(i,v.size()){
   ^~~
bulldozer.cpp:2:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n)for(int i=0;i<(n);i++)
                              ^
bulldozer.cpp:88:3: note: in expansion of macro 'rep'
   rep(i,v.size()){
   ^~~
bulldozer.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lf%lf%lld",&p[i].x,&p[i].y,&w[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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