oj.uz

답안 #150271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
150271 2019-09-01T08:01:55 Z 본인 방금 올솔하는 상상함(#3610, gs18113, dennisstar, red1108) 최적의 팀 구성 (FXCUP4_squad) C++17
19 / 100
 297 ms 47996 KB 
#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

struct Point{
	long long x, y;
	int ind;
	bool operator <(const Point A) const{
		if(x==A.x) return y<A.y;
		return x<A.x;
	}
};
vector<Point> pa, pb;
int n;
bool chk(Point a, Point b, Point c){
	return (a.y-b.y)*(c.x-b.x) >= (b.y-c.y)* (b.x-a.x);
}
vector<Point> f(vector<Point> in){
	vector<Point> ret;
	for(auto i:in){
		while(ret.size()>1&&ret[ret.size()-1].y<=i.y) ret.pop_back();
		while(ret.size()>1&&chk(ret[ret.size()-2],ret[ret.size()-1],i)) ret.pop_back();
		ret.push_back(i);
	}
	return ret;
}
void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	n = A.size();
	for(int i=0;i<n;i++){
		pa.push_back({A[i],P[i],i});
		pb.push_back({D[i],P[i],i});
	}
	sort(pa.begin(), pa.end());
	sort(pb.begin(), pb.end());
	pa = f(pa);
	pb = f(pb);
	/*
	cout<<"pa --------------\n";
	for(auto i:pa){
		cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
	}
	cout<<"pb --------------\n";
	for(auto i:pb){
		cout<<i.x<<" "<<i.y<<" "<<i.ind<<"\n";
	}
	cout<<"end of debug-----\n";
	*/
	
}

long long BestSquad(int X, int Y){
	
	int l=0,r=pa.size()-2,inda=0,indb=0;
	while(l<r){
		int mid = (l+r)/2;
		if((pa[mid].y-pa[mid+1].y)*Y<(pa[mid+1].x-pa[mid].x)*X)
		{
			inda=max(inda,mid+1);
			l=mid+1;
		}
		else r=mid-1;
	}
	l=0;r=pb.size()-2;
	while(l<r){
		int mid = (l+r)/2;
		if((pb[mid].y-pb[mid+1].y)*Y<(pb[mid+1].x-pb[mid].x)*X)
		{
			indb=max(indb,mid+1);
			l=mid+1;
		}
		else r=mid-1;
	}
	//cout<<"inda : "<<inda<<" indb : "<<indb<<endl;
	long long ret=0;
	for(int i=-5;i<=5;i++){
		for(int j=-5;j<=5;j++){
			int aa=inda+i, bb=indb+j;
			if(0<=aa&&aa<pa.size()&&0<=bb&&bb<pb.size()&&pa[aa].ind!=pb[bb].ind){
				long long t = (pa[aa].x+pb[bb].x)*X+(pa[aa].y+pb[bb].y)*Y;
				//cout<<"check "<<aa<<" "<<bb<<" "<<t<<"\n";
				if(ret<t) ret=t;
			}
		}
	}
	return ret;
}

Compilation message

squad.cpp: In function 'long long int BestSquad(int, int)':
squad.cpp:78:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(0<=aa&&aa<pa.size()&&0<=bb&&bb<pb.size()&&pa[aa].ind!=pb[bb].ind){
              ~~^~~~~~~~~~
squad.cpp:78:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(0<=aa&&aa<pa.size()&&0<=bb&&bb<pb.size()&&pa[aa].ind!=pb[bb].ind){
                                   ~~^~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 276 ms 28904 KB Output is correct
4 Correct 285 ms 28900 KB Output is correct
5 Correct 24 ms 3476 KB Output is correct
6 Correct 292 ms 47988 KB Output is correct
7 Correct 297 ms 47992 KB Output is correct
8 Correct 279 ms 47996 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 276 ms 28904 KB Output is correct
4 Correct 285 ms 28900 KB Output is correct
5 Correct 24 ms 3476 KB Output is correct
6 Correct 292 ms 47988 KB Output is correct
7 Correct 297 ms 47992 KB Output is correct
8 Correct 279 ms 47996 KB Output is correct
9 Incorrect 6 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -