oj.uz

Submission #1089591

# Submission time Handle Problem Language Result Execution time Memory
1089591 2024-09-16T18:40:41 Z noyancanturk Homecoming (BOI18_homecoming) C++17
100 / 100
 153 ms 165392 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 {
      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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 31572 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 153 ms 165392 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct
5 Correct 6 ms 3892 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 37 ms 31572 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 153 ms 165392 KB Output is correct
14 Correct 3 ms 1884 KB Output is correct
15 Correct 6 ms 3892 KB Output is correct
16 Correct 148 ms 165240 KB Output is correct
17 Correct 59 ms 34420 KB Output is correct
18 Correct 92 ms 44352 KB Output is correct
19 Correct 95 ms 90176 KB Output is correct
20 Correct 119 ms 148212 KB Output is correct
21 Correct 89 ms 87584 KB Output is correct