Submission #365369

#	Time	Username	Problem	Language	Result	Execution time	Memory
365369		kostia244	Homecoming (BOI18_homecoming)	C++17	62 / 100	1087 ms	91120 KiB

homecoming

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#include"homecoming.h"
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
int n, k;
vector<ll> a, b;
ll naive1(int fil) {
	deque<ll> dp;
	const ll inf = 1ll<<50;
	for(int i = 0; i <= k; i++)
		dp.push_back(i == fil ? 0 : -inf);
	ll best = 0, lazyadd = 0;
	for(int i = 0; i < n; i++) {
		ll bk = dp.back();
		ll ne0 = best+lazyadd;
		dp.pop_back();
		dp.back() = max(dp.back(), bk);
		dp.back() += a[i];
		lazyadd += b[i];
		best = max(best, dp.back());
		if(i < n-fil) {
			dp.push_front(ne0-lazyadd);
			best = max(best, dp.front());
		} else dp.push_front(-inf-lazyadd);
	}
	return best+lazyadd;
}
long long solve(int N, int K, int *A, int *B) {
	n = N, k = K;
	a = vector<ll>(A, A+n);
	b = vector<ll>(B, B+n);
	reverse(all(a));
	reverse(all(b));
	for(auto &i : b) i *= -1;
	ll ans = 0;
	for(int i = 0; i < k; i++) ans = max(ans, naive1(i));
	return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 31 / 31
• Subtask 4: 0 / 38