Submission #578773

#	Time	Username	Problem	Language	Result	Execution time	Memory
578773		AlperenT	Homecoming (BOI18_homecoming)	C++17	100 / 100	116 ms	16000 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;

const long long INF = 1e18;

long long solve(int n, int k, int *a, int *b){
	long long ans = 0;

	long long mx, cur, cost, nxtcost;

	for(int it = 1; it <= 2; it++){
		mx = (it == 1 ? -INF : 0);

		cost = accumulate(b, b + k, 0ll);

		cur = a[0] - cost;

		mx = max(mx, cur);

		for(int i = 1; i < n; i++){
			cost -= b[i - 1];

			if(i + k - 1 < n) nxtcost = b[i + k - 1];
			else if(it == 2) nxtcost = b[i + k - 1 - n];
			else nxtcost = 0;

			cur = max(a[i] + cur - nxtcost, a[i] - (cost + nxtcost) + mx);

			cost += nxtcost;

			mx = max(mx, cur);
		}

		ans = max(ans, mx);
	}

	return ans;
}

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