Submission #1089589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089589		noyancanturk	Homecoming (BOI18_homecoming)	C++17	0 / 100	38 ms	41044 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 {
      return pref[r]-pref[l-1];
    };
    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 {
      return pref[r]-pref[l-1];
    };
    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;
}

Compilation message (stderr)

homecoming.cpp: In function 'lint solve(int, int, int*, int*)':
homecoming.cpp:19:30: warning: array subscript -1 is below array bounds of 'lint [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   19 |       return pref[r]-pref[l-1];
      |                      ~~~~~~~~^
homecoming.cpp:34:30: warning: array subscript -1 is below array bounds of 'lint [(<anonymous> + 1)]' {aka 'long long int [(<anonymous> + 1)]'} [-Warray-bounds]
   34 |       return pref[r]-pref[l-1];
      |                      ~~~~~~~~^

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