Submission #1180000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180000		pcheloveks	Homecoming (BOI18_homecoming)	C++20	0 / 100	160 ms	327680 KiB

homecoming

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")

#include "homecoming.h"
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset

#define endl '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;

const ll DIM = 700007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 998244353;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;

const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };

FILE* stream;

long long int solve(int N, int K, int* A, int* B) {
    vector<vector<vector<ll>>> F(2, vector<vector<ll>>(2 * N + 7, vector<ll>(2 * N + 7, 0)));
    vector < ll > p(2 * N + 1, 0);

    long long int res = 0;
    if (K != 1) {
        p[0] = B[0];
        for (int i = 1; i < 2 * N; i++) {
            if (i < N) p[i] = p[i - 1] + B[i];
            else p[i] = p[i - 1] + B[i - N];
        }
        for (int L = 2 * N - 1; L >= 0; L--) {
            for (int R = L; R < 2 * N; R++) {
                if (R - L + 1 < K || R - L + 1 > N) continue;
                else if (R - L + 1 == K) {
                    F[0][L][R] = 0;

                    if (L != 0) F[1][L][R] = p[R] - p[L - 1];
                    else F[1][L][R] = p[R];

                    F[1][L][R] *= -1;
                    if (L < N) F[1][L][R] += A[L];
                    else F[1][L][R] += A[L - N];
                }
                else {
                    for (int x = L + 1; x <= R; x++) {
                        F[0][L][R] = max(F[0][L][R], max(F[0][x][R], F[1][x][R]));
                    }

                    ll a, b;
                    if (L < N) a = A[L];
                    else a = A[L - N];

                    if (L < N) b = B[L];
                    else b = B[L - N];

                    F[1][L][R] = F[1][L + 1][R] + a - b;

                    for (int x = L + K; x <= R; x++) {
                        if (L != 0) F[1][L][R] = max(F[1][L][R], -(p[L + K - 1] - p[L - 1]) + a + max(F[0][x][R], F[1][x][R]));
                        else F[1][L][R] = max(F[1][L][R], -(p[L + K - 1]) + a + max(F[0][x][R], F[1][x][R]));
                    }
                }
                if (R - L + 1 == N) {
                    res = max(res, F[0][L][R]);
                    res = max(res, F[1][L][R]);
                }
                cout << L << " " << R << " " << F[0][L][R] << endl;
            }
        }
    }
    else {
        for (int i = 0; i < N; i++) {
            if (A[i] - B[i] >= 0) res += A[i] - B[i];
        }
    }
    return res;
}

/*
3 2
40 80 100
140 0 20
*/

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