Submission #365351

#	Time	Username	Problem	Language	Result	Execution time	Memory
365351		kostia244	Homecoming (BOI18_homecoming)	C++17	0 / 100	45 ms	12140 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;
vector<int> tooka, tookb;
struct seg {
	int n;
	vector<ll> tree;
	seg(int n) {
		n = a.size();
		while(n & (n-1)) n += n&-n;
		tree.resize(2*n, 1ll<<60);
	}
	template<int SET>
	void upd(int pos, ll val) {
		for(SET ? (tree[pos+=n]=val) : (tree[pos+=n]+=val); pos/=2;)
			tree[pos] = min(tree[2*pos], tree[2*pos+1]);
	}
	ll query() { return tree[1]; }
	ll query(int l, int r) {
		ll res = 0;
		for(l += n, r += n; l < r; l>>=1,r>>=1) {
			if(l&1) res = min(res, tree[l++]);
			if(r&1) res = min(res, tree[--r]);
		}
		return res;
	}
};
//ll get(const vector<ll> &a, int l, int r) {
//	return a[r] - (l?a[l-1]:0);
//}
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;
		dp.pop_back();
		dp.back() = max(dp.back(), bk);
		lazyadd += b[i], best += b[i];
		dp.back() += a[i];
 		if(i < n-fil) {
		dp.push_front(ne0-lazyadd);
		best = max(best, ne0);} else dp.push_front(-inf-lazyadd);
		best = max(dp.back()+lazyadd, best);
		//for(auto i : dp) cout << i+lazyadd << " "; cout << endl;
		//cout << best+lazyadd << endl;
	}
	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);
	for(auto &i : b) i *= -1;
	//for(int i = 1; i < n; i++)
	//	a[i] += a[i-1], b[i] += b[i-1];
	ll ans = 0;
	//for(auto i : a) cout << i << " "; cout << endl;
	//for(auto i : b) cout << i << " "; cout << endl;
	for(int i = 0; i < k; i++) ans = max(ans, naive1(i));
	return ans;
}

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