Submission #861509

#	Time	Username	Problem	Language	Result	Execution time	Memory
861509		iskhakkutbilim	Homecoming (BOI18_homecoming)	C++17	100 / 100	195 ms	180960 KiB

homecoming

#ifndef EVAL
#include "homecoming.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll inf = 1e17;


ll solve(int n, int k, int a[], int b[]){
	vector< vector<ll> > dp(n, vector<ll>(2, -inf));
	vector<ll> pref(n);
	pref[0] = b[0];
	for(int i = 1;i < n; i++){
		pref[i] = pref[i-1] + b[i];
	}	
	ll ans = 0; 
	dp[0][1] = a[0] - pref[k-1];
	for(int i = 1;i < n; i++){
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
		dp[i][1] = max(dp[i-1][0] + a[i] - (pref[min(n-1, i + k-1)] - pref[i-1]), 
				   dp[i-1][1] + a[i] - (i + k-1 < n ? b[i+k-1] : 0LL));
	}
	ans = max(ans, dp[n-1][0]);
	ans = max(ans, dp[n-1][1]);
	for(int i = 0;i < n; i++) dp[i][0] = dp[i][1] = -inf;
	dp[0][0] = 0;
	for(int i = 1;i < n; i++){
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
		dp[i][1] = max(dp[i-1][0] + a[i] - (pref[min(n-1, i + k-1)] - pref[i-1] + (i + k-1 >= n ? pref[i+k-1-n] : 0LL)), 
					dp[i-1][1] + a[i] - b[(i + k-1) % n]);
	}
	
	
	ans = max(ans, dp[n-1][0]);
	ans = max(ans, dp[n-1][1]);
	return ans;
}

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