제출 #149493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
149493		Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	19 / 100	3111 ms	206220 KiB

squad

#include "squad.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

struct cht {
	vector<ar<int, 2>> v;
	int a[1<<18], b[1<<18], qt;
	void al(int a, int b) {
		v.push_back({a, b});
	}
	void init() {
		sort(v.begin(), v.end());
		for(ar<int, 2> vi : v) {
			while(qt&&vi[0]==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-vi[0])>=(ll)(vi[1]-b[qt-1])*(a[qt-2]-a[qt-1]))
				--qt;
			a[qt]=vi[0];
			b[qt]=vi[1];
			++qt;
		}
	}
	ll qry(ll x, ll y) {
		int lb=0, rb=qt-1;
		while(lb<rb) {
			int mb=(lb+rb)/2;
			if(a[mb]*x+b[mb]*y>a[mb+1]*x+b[mb+1]*y)
				rb=mb;
			else
				lb=mb+1;
		}
		return a[lb]*x+b[lb]*y;
	}
} ca[19][2], cd[19][2];

int n, k;

void Init(vector<int> a, vector<int> d, vector<int> p) {
	n=a.size();
	while(1<<k<n)
		++k;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<k; ++j) {
			ca[j][i>>j&1].al(a[i], p[i]);
			cd[j][i>>j&1].al(d[i], p[i]);
		}
	}
	for(int j=0; j<k; ++j) {
		for(int l : {0, 1}) {
			ca[j][l].init();
			cd[j][l].init();
		}
	}
}

ll BestSquad(int x, int y) {
	ll ans=0;
	for(int i=0; i<k; ++i) {
		ans=max(ans, ca[i][0].qry(x, y)+cd[i][1].qry(x, y));
		ans=max(ans, cd[i][0].qry(x, y)+ca[i][1].qry(x, y));
	}
	return ans;
}

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

squad.cpp: In member function 'void cht::init()':
squad.cpp:17:12: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    while(qt&&vi[0]==a[qt-1]||qt>1&&(ll)(b[qt-1]-b[qt-2])*(a[qt-1]-vi[0])>=(ll)(vi[1]-b[qt-1])*(a[qt-2]-a[qt-1]))
          ~~^~~~~~~~~~~~~~~~

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