Submission #1089591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089591		noyancanturk	Homecoming (BOI18_homecoming)	C++17	100 / 100	153 ms	165392 KiB

homecoming

#include"homecoming.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back

using lint = long long;

lint solve(int N, int K, int *A, int *B){
  int n=N,k=K;
  lint a[n],b[2*n];
  for(int i=0;i<n;i++)
    a[i]=A[i],b[i]=B[i];
  lint ans=0;
  {
    for(int i=n;i<2*n;i++)b[i]=0;
    lint pref[2*n];
    for(int i=0;i<2*n;i++)pref[i]=b[i]+(i?pref[i-1]:0);
    auto p=[&](int l,int r)->lint {
      if(l)return pref[r]-pref[l-1];
      return pref[r];
    };
    lint dp[n][2];
    dp[0][0]=dp[0][1]=a[0]-p(0,k-1);
    for(int i=1;i<n;i++){
      dp[i][0]=max(dp[i-1][0]-b[i+k-1],dp[i-1][1]-p(i,i+k-1))+a[i];
      dp[i][1]=max(dp[i-1][1],dp[i][0]);
    }
    ans=max(ans,dp[n-1][1]);
  }
  {
    for(int i=n;i<2*n;i++)b[i]=b[i-n];
    lint pref[2*n];
    for(int i=0;i<2*n;i++)pref[i]=b[i]+(i?pref[i-1]:0);
    auto p=[&](int l,int r)->lint {
      if(l)return pref[r]-pref[l-1];
      return pref[r];
    };
    lint dp[n][2];
    dp[0][0]=a[0]-p(0,k-1);
    dp[0][1]=max(dp[0][0],0ll);
    for(int i=1;i<n;i++){
      dp[i][0]=max(dp[i-1][0]-b[i+k-1],dp[i-1][1]-p(i,i+k-1))+a[i];
      dp[i][1]=max(dp[i-1][1],dp[i][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