oj.uz

Submission #149950

# Submission time Handle Problem Language Result Execution time Memory
149950 2019-09-01T07:27:16 Z 등수만큼 신재웅 생일빵 때림 (10대)(#3628, kjp4155, GodTe, JWoong148) Organizing the Best Squad (FXCUP4_squad) C++17
100 / 100
 1008 ms 56236 KB 
#include <bits/stdc++.h>

using namespace std;

#define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 6,5,4,3,2,1))
#define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
#define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,_6,N,...) N
#define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
#define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
#define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
#define macro_dispatcher___(macro, nargs) macro ## nargs
#define Debug1(a)           cout<<#a<<"="<<(a)<<"\n"
#define Debug2(a,b)         cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define Debug3(a,b,c)       cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define Debug4(a,b,c,d)     cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define Debug5(a,b,c,d,e)   cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define Debug6(a,b,c,d,e,f) cout<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define Debug(...) macro_dispatcher(Debug, __VA_ARGS__)(__VA_ARGS__)
#define DA(a,s,n) cout<<#a<<"=["; printarray(a,s,n); cout<<"]\n"

#define TT1 template<class T>
#define TT1T2 template<class T1, class T2>
#define TT1T2T3 template<class T1, class T2, class T3>
template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v);
TT1T2 ostream& operator << (ostream& os, const pair<T1, T2>& p){ return os <<"("<<p.first<<", "<< p.second<<")"; }
TT1 ostream& operator << (ostream& os, const vector<T>& v){       bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
template<class T, size_t N> ostream& operator << (ostream& os, const array<T, N>& v) {     bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const set<T1, T2>&v){    bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const multiset<T1,T2>&v){bool f=1;os<<"[";for(auto& i : v) { if (!f)os << ", ";os<<i;f=0;}return os << "]"; }
TT1T2T3 ostream& operator << (ostream& os, const map<T1,T2,T3>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
TT1T2 ostream& operator << (ostream& os, const multimap<T1, T2>& v){ bool f = 1; os << "["; for (auto& ii : v) { if (!f)os << ", "; os << "(" << ii.first << " -> " << ii.second << ") "; f = 0; }return os << "]"; }
TT1T2 ostream& operator << (ostream& os, priority_queue<T1, T2> v) { bool f = 1; os << "["; while (!v.empty()) { auto x = v.top(); v.pop(); if (!f) os << ", "; f = 0; os << x; } return os << "]"; }
TT1T2 void printarray(const T1& a, T2 l, T2 r){ for (T2 i = l; i<=r; i++) cout << a[i] << (i<r?" ":""); }

void cio(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
}

#define tt() printf("%.4f sec\n", (double) clock() / CLOCKS_PER_SEC )

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()
#define geti1(X) cin >> X
#define geti2(X,Y) cin >> X >> Y
#define geti3(X,Y,Z) cin >> X >> Y >> Z
#define geti4(X,Y,Z,W) cin >> X >> Y >> Z >> W
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)

#define endl '\n'

typedef tuple<int,int,int> t3;
typedef tuple<int,int,int,int> t4;
void die(){printf("-1\n"); exit(0);}
int xx[4] = {1,-1,0,0}, yy[4] = {0,0,1,-1};

#include "squad.h"

int N;
struct Line{
	ll a, b, idx;
};

ostream& operator << (ostream& os, const Line& l) {
	return os << "(" << l.a << ", " << l.b << ", " << l.idx << ")";
}

ll ccw(pll a, pll b){
	return a.Fi * b.Se - a.Se * b.Fi;
}
int vis[500500];
vector<Line> CVA1, CVA2, CVB1, CVB2;

vector<Line> getCVX(vector<Line> v){
	sort(all(v), [](Line a, Line b) -> bool {
		if( a.a == b.a ) return a.b < b.b;
		return a.a < b.a;
	});
	vector<Line> V;
	for (auto e : v) {
		V.push_back(e);
		while( V.size() >= 3 ){
			Line l3 = V[sz(V)-1], l2 = V[sz(V)-2], l1 = V[sz(V)-3];
			if( (l3.b-l1.b) * (l2.a-l1.a) >= (l2.b-l1.b) * (l3.a-l1.a) ) {
				V.pop_back();
				V.pop_back();
				V.push_back(l3);
			}
			else break;
		}
	}
	return V;
}
vector<ll> A, D, P;
void Init(std::vector<int> _A, std::vector<int> _D, std::vector<int> _P){
	for(auto e : _A) A.pb(e);
	for(auto e : _D) D.pb(e);
	for(auto e : _P) P.pb(e);
	// A = _A, D = _D, P = _P;
	N = sz(A);
	vector<Line> v;
	for(int i = 0; i < N; i++)  v.push_back({P[i], A[i], i});
	CVA1 = getCVX(v);
	for(auto e : CVA1) vis[e.idx] = 1;
	v.clear();
	for(int i = 0; i < N; i++) if( !vis[i] ) v.push_back({P[i], A[i], i});
	CVA2 = getCVX(v);

	v.clear();
	rep(i,N) vis[i] = 0;
	for(int i = 0; i < N; i++)  v.push_back({P[i], D[i], i});
	CVB1 = getCVX(v);
	for(auto e : CVB1) vis[e.idx] = 1;
	v.clear();
	for(int i = 0; i < N; i++) if( !vis[i] ) v.push_back({P[i], D[i], i});
	CVB2 = getCVX(v);

	// Debug(CVA1, CVA2, CVB1, CVB2);
}


int getMax(ll X, ll Y, vector<Line>& cvx){
	assert( sz(cvx) > 0 );
	if( sz(cvx) == 1 ) return 0;

	int low = 0, high = sz(cvx)-2, res = 0;
	while( low <= high ){
		int mid = (low+high)/2;
		Line l1 = cvx[mid], l2 = cvx[mid+1];
		if( l1.a * Y + l1.b * X < l2.a * Y + l2.b * X ) {
			res = mid; low = mid+1;
		} else high = mid-1;
	}
	return res+1;
}

long long BestSquad(int _X, int _Y){
	ll X,Y;
	X = _X, Y = _Y;
	vector<int> idxa, idxb;
	ll ans = -10;
	int a1 = getMax(X, Y, CVA1);
	for(int dd : {-1, 0, 1}) {
		if( !(0 <= a1+dd && a1+dd < sz(CVA1) ) ) continue;
		idxa.push_back(CVA1[a1+dd].idx);
	}

	if( sz(CVA2) >= 1 ){
		int a2 = getMax(X, Y, CVA2);
		for(int dd : {-1, 0, 1}) {
			if( !(0 <= a2+dd && a2+dd < sz(CVA2) ) ) continue;
			idxa.push_back(CVA2[a2+dd].idx);
		}
	}

	int b1 = getMax(X, Y, CVB1);
	for(int dd : {-1, 0, 1}) {
		if( !(0 <= b1+dd && b1+dd < sz(CVB1) ) ) continue;
		idxb.push_back(CVB1[b1+dd].idx);
	}

	if( sz(CVB2) >= 1 ){
		int b2 = getMax(X, Y, CVB2);
		for(int dd : {-1, 0, 1}) {
			if( !(0 <= b2+dd && b2+dd < sz(CVB2) ) ) continue;
			idxb.push_back(CVB2[b2+dd].idx);
		}
	}

	for(auto ia : idxa) for(auto ib : idxb) {
		if( ia == ib ) continue;
		ll t = X * A[ia] + Y * P[ia] + X * D[ib] + Y * P[ib];
		ans = max(ans, t);
	}
	return ans;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 383 ms 36796 KB Output is correct
4 Correct 381 ms 36792 KB Output is correct
5 Correct 24 ms 3996 KB Output is correct
6 Correct 289 ms 55968 KB Output is correct
7 Correct 292 ms 56236 KB Output is correct
8 Correct 292 ms 56224 KB Output is correct

Subtask #2
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 12 ms 768 KB Output is correct
3 Correct 698 ms 36796 KB Output is correct
4 Correct 730 ms 36788 KB Output is correct
5 Correct 31 ms 2108 KB Output is correct
6 Correct 894 ms 47036 KB Output is correct
7 Correct 881 ms 47048 KB Output is correct
8 Correct 833 ms 47036 KB Output is correct

Subtask #3
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 383 ms 36796 KB Output is correct
4 Correct 381 ms 36792 KB Output is correct
5 Correct 24 ms 3996 KB Output is correct
6 Correct 289 ms 55968 KB Output is correct
7 Correct 292 ms 56236 KB Output is correct
8 Correct 292 ms 56224 KB Output is correct
9 Correct 6 ms 384 KB Output is correct
10 Correct 12 ms 768 KB Output is correct
11 Correct 698 ms 36796 KB Output is correct
12 Correct 730 ms 36788 KB Output is correct
13 Correct 31 ms 2108 KB Output is correct
14 Correct 894 ms 47036 KB Output is correct
15 Correct 881 ms 47048 KB Output is correct
16 Correct 833 ms 47036 KB Output is correct
17 Correct 110 ms 2936 KB Output is correct
18 Correct 12 ms 768 KB Output is correct
19 Correct 753 ms 36788 KB Output is correct
20 Correct 754 ms 36792 KB Output is correct
21 Correct 38 ms 2664 KB Output is correct
22 Correct 926 ms 56228 KB Output is correct
23 Correct 956 ms 56224 KB Output is correct
24 Correct 1008 ms 56224 KB Output is correct