Submission #1138438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138438		poat	Homecoming (BOI18_homecoming)	C++17	62 / 100	203 ms	327680 KiB

homecoming

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

const int NN = 2e6 + 5;
long long pref[NN * 2];
int arr[NN * 2], brr[NN * 2];
int n, k;
   
long long f(int i, int x, int y)
{
    if(x == 0)
        return 0ll;
    if(y == 0)
        return (arr[i] - (pref[i + k - 1] - pref[i - 1]));    
    return arr[i] - brr[i];
}
long long f2(int i, int x, int y)
{
    if(y == 0)
        return 0ll;
    if(x == 0)
        return arr[i] - (pref[i + k - 1] - pref[i - 1]);
    return arr[i] - brr[i + k - 1];
}

long long solve(int N, int K, int *A, int *B)
{
    n = N, k = K;
    if(K == 1)
    {
        long long sum = 0;
        for(int i = 0; i < N; i++)
            sum += ((int) max(0, A[i] - B[i]));
        return sum;
    }
    for(int i = 0; i < N * 2; i++)
    {
        arr[i] = A[i % N];
        brr[i] = B[i % N];
    }
    pref[0] = brr[0];
    for(int i = 1; i < N * 2; i++)
        pref[i] = pref[i - 1] + brr[i];
    
    long long dp1[N][3][3], dp2[N][3][3];
    for(int i = 0; i < N; i++)
    {
        for(int k2 = 0; k2 < 2; k2++)
            dp1[i][k2][0] = dp1[i][k2][1] = dp2[i][k2][0] = dp2[i][k2][1] = -1e16; 
    }
    dp1[N - 1][0][0] = 0ll;
    dp1[N - 1][1][1] = f(N - 1, 1, 0);
    for(int i = N - 2; i >= 0; i--)
    {
        for(int p = 0; p < 2; p++)
        {
            for(int z = 0; z < 2; z++)
            {
                for(int h = 0; h < 2; h++)
                    dp1[i][p][z] = max(dp1[i][p][z], dp1[i + 1][h][z] + f(i, p, h)); 
            }
        }
    }
    dp2[0][0][0] = 0;
    dp2[0][1][1] = f2(N, 0, 1);
    for(int i = 1; i < N; i++)
    {
        for(int p = 0; p < 2; p++)
        {
            for(int z = 0; z < 2; z++)
            {
                for(int h = 0; h < 2; h++)
                    dp2[i][p][z] = max(dp2[i][p][z], dp2[i - 1][p][h] + f2(i, h, z));
            }
        }
    }
    long long mx = 0;
    for(int i = 0; i < N; i++)
        mx += (A[i] - B[i]);
    mx = max({mx, dp1[0][0][0], dp1[0][0][1]});
    for(int i = 1; i < N; i++)
    {
        int j = i - 1;
        for(int h = 0; h < 2; h++)
        {
            for(int z = 0; z < 2; z++)
            {
                for(int p = 0; p < 2; p++)
                {
                    long long res = dp1[i][0][h] + dp2[j][z][p];
                    if(h && z && K > 1)
                        res = res + pref[K - 2];
                    mx = max(mx, res);   
                }
            }
        }
    }
    
    return mx;
}

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