Submission #1138236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138236		poat	Homecoming (BOI18_homecoming)	C++20	0 / 100	25 ms	21828 KiB

homecoming

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

const int NMax = 1e6 + 100, inf = 2e9;
int n, k, a[NMax * 3], b[NMax * 3], pref[NMax * 3];

int f(int i, int x, int y)
{
    if(x == 0)
        return 0;
    if(y == 0)
        return a[i] - (pref[i + k - 1] - pref[i - 1]);    
    return a[i] - b[i];
}
int f2(int i, int x, int y)
{
    if(y == 0)
        return 0;
    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)
{
    int n = N, k = K;
    for(int i = 1; i <= n; i++)
        a[i] = A[i - 1];
    for(int i = 1; i <= n; i++)
    {
        b[i] = B[i - 1];
        pref[i] = pref[i - 1] + b[i];
    }
    for(int 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, 0, 1);
    // return 0;

    int suf[n + 5][2][2] = {};
    for(int i = 0; i <= n * 2; i++)
    {
        for(int 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(int i = n - 1; i >= 1; i--)
    {
        for(int k1 = 0; k1 < 2; k1++)
        {
            for(int k2 = 0; k2 < 2; k2++)
            {
                for(int z = 0; z < 2; z++)
                    suf[i][k1][k2] = max(suf[i][k1][k2], f(i, k1, z) + suf[i + 1][z][k2]);
            }
        }
    }

    int pre[n * 2 + 5][2][2];
    for(int i = 0; i <= n * 2; i++)
    {
        for(int 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(int i = n + 2; i <= n * 2; i++)
    {
        for(int k1 = 0; k1 < 2; k1++)
        {
            for(int k2 = 0; k2 < 2; k2++)
            {
                for(int z = 0; z < 2; z++)
                    pre[i][k1][k2] = max(pre[i][k1][k2], f2(i, z, k2) + pre[i - 1][k1][z]);
            }
        }
    }
    return 123;
    
    int mx = 0;
    for(int i = 1; i <= n; i++)
    {
        int j = i + n - 1;
        for(int x = 0; x < 2; x++)
        {
            for(int y = 0; y < 2; y++)
            {
                for(int z = 0; z < 2; z++)
                {
                    for(int h = 0; h < 2; h++)
                    {
                        mx = max(mx, suf[i][x][y] + pre[j][z][h] + f(n, y, z));
                    }
                }
            }
        }
    }
    return mx;
    // cout << mx << '\n';
}

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