Submission #1046337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046337		ymm	Cake 3 (JOI19_cake3)	C++17	100 / 100	2844 ms	12456 KiB

cake3

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

typedef double scal;
typedef vector<scal> poly;
const scal inf = 1e18;

#define MAX(x, y) ((x)>(y)?(x):(y))

__attribute__((optimize("O3,unroll-loops"),target("avx2,prefer-vector-width=128")))
void fast_mul(scal *__restrict dst, const scal *__restrict src1, const scal *__restrict src2, int n, int m)
{
	int constexpr S = 128;
	for (int l = 0; l < m; l += S) {
		int r = min(l + S, m);
		for (int i = 0; i < n; i++) {
			for (int j = l; j < r; j++)
				dst[i + j] = MAX(dst[i + j], src1[i] + src2[j]);
		}
	}
}

poly operator*(const poly &src1, const poly &src2)
{
	poly ans(src1.size() + src2.size() - 1, -inf);
	fast_mul(ans.data(), src1.data(), src2.data(), src1.size(), src2.size());
	return ans;
}

poly operator+(const poly &src1, const poly &src2)
{
	bool swp = src1.size() < src2.size();
	auto &a = swp? src2: src1;
	auto &b = swp? src1: src2;
	poly ans(a.size());
	Loop (i,0,b.size())
		ans[i] = MAX(a[i], b[i]);
	Loop (i,b.size(),a.size())
		ans[i] = a[i];
	return ans;
}

const int N = 200'010;
pair<scal, scal> arr[N];
int n, M;
scal ans = -inf;

void solve(int l, int r, poly *pl, poly *pm, poly *pr)
{
	if (r - l == 1) {
		if (pl) *pl = { -inf, arr[l].second + 2 * arr[l].first };
		if (pm) *pm = { 0, arr[l].second};
		if (pr) *pr = { -inf, arr[l].second - 2 * arr[l].first };
		return;
	}
	int m = (l + r)/2;
	poly Pll, Plm, Plr;
	poly Prl, Prm, Prr;
	solve(l, m, &Pll, pr || pm? &Plm: nullptr, pr? &Plr: nullptr);
	solve(m, r, pl? &Prl: nullptr, pl || pm? &Prm: nullptr, &Prr);
	if (r - l >= M) {
		Loop (i,0,M+1) {
			if (Pll.size() > i && Prr.size() > M-i)
				ans = max(ans, Pll[i] + Prr[M-i]);
		}
	}
	if (pm) *pm = Plm * Prm;
	if (pl) *pl = Pll * Prm + Prl;
	if (pr) *pr = Prr * Plm + Plr;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> M;
	Loop (i,0,n) {
		ll v, c;
		cin >> v >> c;
		arr[i].first = c;
		arr[i].second = v;
	}
	sort(arr, arr+n);
	solve(0, n, nullptr, nullptr, nullptr);
	cout << (ll)ans << '\n';
}

Compilation message (stderr)

cake3.cpp: In function 'void solve(int, int, poly*, poly*, poly*)':
cake3.cpp:68:19: warning: comparison of integer expressions of different signedness: 'std::vector<double>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   68 |    if (Pll.size() > i && Prr.size() > M-i)
      |        ~~~~~~~~~~~^~~
cake3.cpp:68:37: warning: comparison of integer expressions of different signedness: 'std::vector<double>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   68 |    if (Pll.size() > i && Prr.size() > M-i)
      |                          ~~~~~~~~~~~^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76