oj.uz

Submission #1089589

# Submission time Handle Problem Language Result Execution time Memory
1089589 2024-09-16T18:37:07 Z noyancanturk Homecoming (BOI18_homecoming) C++17
0 / 100
 38 ms 41044 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 41044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -