Submission #149581

#	Time	Username	Problem	Language	Result	Execution time	Memory
149581		강력한 한방 필살기 (#200)	Organizing the Best Squad (FXCUP4_squad)	C++17	0 / 100	9 ms	5120 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using pi = pair<int,int>;
using lint = long long;
const int MAXN = 300005;

lint ccw(pi a, pi b, pi c){
	int dx1 = b.first - a.first;
	int dy1 = b.second - a.second;
	int dx2 = c.first - a.first;
	int dy2 = c.second - a.second;
	return 1ll * dx1 * dy2 - 1ll * dy1 * dx2;
}

struct query{
	pi V[MAXN];
	int par[MAXN], n;
	void init(vector<pi> v){
		vector<int> stk;
		for(int i=0; i<sz(v); i++){
			V[i + 1] = v[i];
			while(sz(stk) >= 2 && ccw(V[stk[sz(stk) - 2]], V[stk.back()], V[i + 1]) < 0){
				stk.pop_back();
			}
			if(sz(stk)) par[i + 1] = stk.back();
			stk.push_back(i + 1);
		}
	}
	pair<lint, int> get(int x, int y, int n){
		lint cur = -1;
		int cnt = 0;
		int pos = -1;
		for(int i=n; i; i=par[i]){
			lint qr = 1ll * x * V[i].first + 1ll * y * V[i].second;
			if(qr > cur){
				cur = qr;
				cnt = 0;
				pos = i;
			}
			if(qr == cur) cnt++;
		}
		if(cnt >= 2) pos = -1;
		return make_pair(cur, pos);
	}
}XP, YP;

int N;

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	N = sz(A);
	vector<pi> v, w;
	for(int i=0; i<N; i++){
		v.emplace_back(A[i], P[i]);
		w.emplace_back(D[i], P[i]);
	}
	XP.init(v);
	YP.init(w);
}

long long BestSquad(int X, int Y){
	auto qr1 = XP.get(X, Y, N);
	auto qr2 = YP.get(X, Y, N);
	if(qr1.second < 0 || qr2.second < 0 || qr1.second != qr2.second) return qr1.first + qr2.first;
	lint ret = -1e18;
	ret = max(ret, qr1.first + YP.get(X, Y, qr1.second - 1).first);
	ret = max(ret, qr2.first + XP.get(X, Y, qr2.second - 1).first);
	return ret;
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 28
• Subtask 3: 0 / 53