Submission #1138261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138261		poat	Homecoming (BOI18_homecoming)	C++20	0 / 100	73 ms	102208 KiB

homecoming

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

const long long NMax = 1e6 + 10, inf = 1e9;
long long n, k, a[NMax * 3], b[NMax * 3], pref[NMax * 3];
long long suf[NMax][2][2], pre[NMax * 2 + 10][2][2];   

long long f(long long i, long long x, long long y)
{
    if(x == 0)
        return 0ll;
    if(y == 0)
        return (a[i] - (pref[i + k - 1] - pref[i - 1]));    
    
    return a[i] - b[i];
}
long long f2(long long i, long long x, long long y)
{
    if(y == 0)
        return 0ll;
    if(x == 0)
        return a[i] - (pref[i + k - 1] - pref[i - 1]);
    return a[i] - b[i + k - 1];
}

long long solve(int N, int K, int *A, int *B)
{
    if(N <= 100)
        assert(0);
    n = N, k = K;
    for(long long i = 1; i <= n; i++)
        a[i] = A[i - 1];
    for(long long i = 1; i <= n; i++)
    {
        b[i] = B[i - 1];
        pref[i] = pref[i - 1] + b[i];
    }
    for(long long i = n + 1; i <= n * 3; i++)
    {
        a[i] = a[i - n];
        b[i] = b[i - n];
        pref[i] = pref[i - 1] + b[i];
    }
    
    // cout << f2(2, 1, 1);
    // exit(0);

    for(long long i = 0; i <= n * 2; i++)
    {
        for(long long k = 0; k < 2; k++)
            suf[i][k][0] = suf[i][k][1] = -inf;
    }
    suf[n][0][0] = 0;
    suf[n][1][1] = f(n, 1, 0);
    for(long long i = n - 1; i >= 1; i--)
    {
        for(long long k1 = 0; k1 < 2; k1++)
        {
            for(long long k2 = 0; k2 < 2; k2++)
            {
                for(long long z = 0; z < 2; z++)
                    suf[i][k1][k2] = max(suf[i][k1][k2], f(i, k1, z) + suf[i + 1][z][k2]);
            }
        }
    }

    for(long long i = 0; i <= n * 2; i++)
    {
        for(long long k = 0; k < 2; k++)
            pre[i][k][0] = pre[i][k][1] = -inf;
    }
    pre[n + 1][0][0] = 0;
    pre[n + 1][1][1] = f2(n + 1, 0, 1);
    for(long long i = n + 2; i <= n * 2; i++)
    {
        for(long long k1 = 0; k1 < 2; k1++)
        {
            for(long long k2 = 0; k2 < 2; k2++)
            {
                for(long long z = 0; z < 2; z++)
                    pre[i][k1][k2] = max(pre[i][k1][k2], f2(i, z, k2) + pre[i - 1][k1][z]);
            }
        }
    }
    
    

    long long mx = 0;
    for(long long i = 1; i <= n; i++)
    {
        long long j = i + n - 1;
        for(long long x = 0; x < 2; x++)
        {
            for(long long y = 0; y < 2; y++)
            {
                for(long long z = 0; z < 2; z++)
                {
                    for(long long h = 0; h < 2; h++)
                    {
                        if(i == 1)
                            mx = max(mx, suf[i][x][y]);
                        else
                            mx = max(mx, suf[i][x][y] + pre[j][z][h] + f(n, y, z));
                    }
                }
            }
        }
    }
    return 0ll;
}

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