Submission #338626

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
338626	2020-12-23 14:07:42	couplefire	Homecoming (BOI18_homecoming)	C++17	100 / 100	195 ms	133740 KiB

homecoming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
using lint = long long;
const int MAXN = 4000005;
 
lint a[MAXN], b[MAXN], dp[MAXN];
 
long long solve(int N, int K, int *A, int *B){
  for(int i=1; i<=N; i++){
    a[i] = a[i+N] = A[i-1];
    b[i] = b[i+N] = B[i-1];
  }
  for(int i=1; i<=2*N; i++){
    a[i] += a[i-1];
    b[i] += b[i-1];
  }
  if(K == N){
    return max(0ll, a[N] - b[N]);
  }
  // First DP : Go across the interval
  lint ans = max(0ll, a[N] - b[N]);
  dp[N+1] = 0;
  lint curmax = -1e18;
  for(int i=N; i; i--){
    dp[i] = a[N] - a[i-1] - (b[N] - b[i-1]); // [i, N]
    dp[i] = max(dp[i], dp[i+1]); // Fuck it
    dp[i] = max(dp[i], curmax + b[i-1] - a[i-1]);
    curmax = max(curmax, dp[i] - b[i + K - 2] + a[i - 1]);
    if(i + K - 2 <= N) ans = max(ans, dp[i] + a[i-1] - b[i + K - 2]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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