Submission #148524

#	Time	Username	Problem	Language	Result	Execution time	Memory
148524		욱방켜!! (twitch.tv/wookje) (#200)	최적의 팀 구성 (FXCUP4_squad)	C++17	19 / 100	177 ms	15688 KiB

squad

#include "squad.h"
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int MX = 300002;

int N;
ll a[MX], d[MX], p[MX];
ll dpref[MX], dsuf[MX];
bool subtask2 = true;

void Init(std::vector<int> A, std::vector<int> D, std::vector<int> P){
	N = A.size();
	for(int i=0; i<N; i++){
		a[i] = A[i], d[i] = D[i], p[i] = P[i];
		if(d[i] != 1) subtask2 = false;
	}
}

long long BestSquad(int X, int Y){
	if(subtask2){
		;
		// todo...
	}

	for(int i=0; i<N; i++){
		a[i] = a[i]*X + p[i]*Y;
		d[i] = d[i]*X + p[i]*Y;
	}
	dpref[0] = d[0];
	for(int i=1; i<N; i++) dpref[i] = max(d[i], dpref[i-1]);
	dsuf[N-1] = d[N-1];
	for(int i=N-2; i>=0; i--) dsuf[i] = max(d[i], dsuf[i+1]);

	// pick i!=j to maximize a[i]+d[j]
	ll ans = -1;
	for(int i=0; i<N; i++){
		ll val = a[i];
		ll dmax = -1;
		if(i) dmax = max(dmax, dpref[i-1]);
		if(i != N-1) dmax = max(dmax, dsuf[i+1]);
		ans = max(ans, val+dmax);
	}
	return ans;
}

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