oj.uz

답안 #149521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
149521 2019-09-01T06:40:30 Z Seishun Buta Yarou wa Yumemiru Shoujo no Yume wo Minai(#3781, zscoder, tmwilliamlin168) 최적의 팀 구성 (FXCUP4_squad) C++17
19 / 100
 3000 ms 209688 KB 
#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() {
		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, q[300000];

void Init(vector<int> a, vector<int> d, vector<int> p) {
	n=a.size();
	while(1<<k<n)
		++k;
	iota(q, q+n, 0);
	sort(q, q+n, [&](const int &i, const int &j) {
		return ar<int, 2>{a[i], p[i]}<ar<int, 2>{a[j], p[j]};
	});
	for(int i=0; i<n; ++i)
		for(int j=0; j<k; ++j)
			ca[j][q[i]>>j&1].al(a[q[i]], p[q[i]]);
	sort(q, q+n, [&](const int &i, const int &j) {
		return ar<int, 2>{d[i], p[i]}<ar<int, 2>{d[j], p[j]};
	});
	for(int i=0; i<n; ++i)
		for(int j=0; j<k; ++j)
			cd[j][q[i]>>j&1].al(d[q[i]], p[q[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;
}

Compilation message

squad.cpp: In member function 'void cht::init()':
squad.cpp:16: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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 9 ms 1408 KB Output is correct
3 Correct 808 ms 121056 KB Output is correct
4 Correct 833 ms 120228 KB Output is correct
5 Correct 42 ms 12664 KB Output is correct
6 Correct 726 ms 209688 KB Output is correct
7 Correct 664 ms 208156 KB Output is correct
8 Correct 723 ms 208488 KB Output is correct

Subtask #2
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 15 ms 1792 KB Output is correct
3 Correct 1667 ms 121584 KB Output is correct
4 Correct 1570 ms 122684 KB Output is correct
5 Correct 109 ms 6520 KB Output is correct
6 Execution timed out 3108 ms 167072 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1024 KB Output is correct
2 Correct 9 ms 1408 KB Output is correct
3 Correct 808 ms 121056 KB Output is correct
4 Correct 833 ms 120228 KB Output is correct
5 Correct 42 ms 12664 KB Output is correct
6 Correct 726 ms 209688 KB Output is correct
7 Correct 664 ms 208156 KB Output is correct
8 Correct 723 ms 208488 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 15 ms 1792 KB Output is correct
11 Correct 1667 ms 121584 KB Output is correct
12 Correct 1570 ms 122684 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Execution timed out 3108 ms 167072 KB Time limit exceeded
15 Halted 0 ms 0 KB -