Submission #1227981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227981		MuhammadSaram	Homecoming (BOI18_homecoming)	C++20	44 / 100	1095 ms	172528 KiB

homecoming

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

using namespace std;

#define ll long long

const int M = 2e6 + 1;

ll seg[M*2],lz[M*2],dp[M],pre[M*2],b[M*2],a[M],n;

void push(int v,int lc,int rc)
{
	seg[lc]+=lz[v],seg[rc]+=lz[v];
	lz[lc]+=lz[v],lz[rc]+=lz[v];
	lz[v]=0;
}

void modify(int l,int r,ll x,int v=0,int s=0,int e=n)
{
	if (l>=e or r<=s)
		return;
	if (l<=s && e<=r)
	{
		seg[v]+=x;
		lz[v]+=x;
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	push(v,lc,rc);
	modify(l,r,x,lc,s,mid);
	modify(l,r,x,rc,mid,e);
	seg[v]=max(seg[lc],seg[rc]);
}

ll get(int l,int r,int v=0,int s=0,int e=n)
{
	if (l>=e or r<=s)	
		return 0;
	if (l<=s && e<=r)
		return seg[v];
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	return max(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}

ll solve1(int l,int r,int k)
{
	for (int i=0;i<2*n;i++)
		pre[i+1]=pre[i]+b[i];
	dp[n-1]=a[n-1]-(pre[n-1+k]-pre[n-1]);
	modify(n-1,n,dp[n-1]+pre[n+k-1]-pre[n-1]);
	ll ans=0;
	for (int i=n-2;i>=l;i--)
	{
		modify(i+1,min((int)n,i+k+1),-b[i+k]);
		dp[i]=a[i]+max(0ll,get(0,n))-(pre[i+k]-pre[i]);
		modify(i,i+1,dp[i]+pre[i+k]-pre[i]);
	}
	for(int i=l;i<r;i++)
		ans=max(ans,dp[i]);
	return ans;
}

ll solve(int N,int k,int A[],int B[])
{
	n=N;
	for (int i=0;i<n;i++)
		b[i]=b[i+n]=B[i],a[i]=A[i],seg[i]=seg[i+n]=lz[i]=lz[i+n]=0;
	ll ans=solve1(k-1,n,k);
	for (int i=k-2;i>=0;i--)
	{
		for (int i=0;i<2*n;i++) seg[i]=lz[i]=0;
		b[i+n]=0;
		ans=max(ans,solve1(i,i+1,k));
	}
	return ans;
}

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