제출 #1006900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1006900		3as8	봉쇄 시간 (IOI23_closing)	C++17	0 / 100	1045 ms	15188 KiB

closing

#include "closing.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;


#define ll long long
#define pll pair<ll, ll>

ll n;
vector<pair<ll, ll> > graph[N];
ll dist[N][2];

void dfs(ll startIndex, ll ind, ll p = -1, ll dep = 0) {


    dist[startIndex][ind] = dep;
    for(auto [el, w] : graph[startIndex]) {
        if(el == p) continue;

        dfs(el, ind, startIndex, dep + w);
    }

}


ll ans;
ll k;
void calc(ll a, ll b, ll c, ll d, ll A, ll B, ll C, ll D) {

    ll sum = a + b + c + d;
    ll num = A + B + C + D;

    if(sum <= k) {
       // cout<<" => "<<sum<<" "<<k<<": "<<num + 2<<endl;
        ans = max(ans, num + 2);
    }

}

void d(vector<ll>& preX, vector<ll>& arr, ll X) {

    preX[X] = 0;
    for(int i = X - 1; i >=0; i--) {
        preX[i] = ( 2 * preX[i + 1]) + arr[i];
    }
    for(int i = X + 1; i < n; i++) {
        preX[i] = ( 2 * preX[i - 1]) + arr[i - 1];
    }

}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {

    ans = LLONG_MIN;
    n = N;
    k = K;
    for(int i = 0 ; i < n; i++ ) {
        graph[i].clear();
    }

    vector<ll> arr(n);

    for(int i = 0; i < n - 1; i++) {
        arr[i] = W[i];
    }

    if(X > Y) swap(X, Y);

    vector<ll> preX(n), preY(n);
    d(preX, arr, X);
    d(preY, arr, Y);

    /*for(int i = 0; i < n; i++) {
        cout<<preX[i]<<" ";
    }
    cout<<endl;

      for(int i = 0; i < n; i++) {
        cout<<preY[i]<<" ";
    }
    cout<<endl;*/


    //cout<<"PHASE 1"<<endl;
    for(int lX = X, lXN = 0; lX >= 0; lX--, lXN++) {
        for(int rX = X, rXN = 0; rX < n; rX++, rXN++) {
            for(int lY = Y, lYN = 0; lY >= 0; lY--, lYN++) {
                for(int rY = Y, rYN = 0; rY < n; rY++, rYN++) {

                    if(rX >= lY) continue;

                  //  cout<<lX<<" "<<rX<<" "<<lY<<" "<<rY<<endl;

                    calc(preX[lX], preX[rX], preY[lY], preY[rY], lXN, rXN, lYN, rYN);
                }
            }
        }
    }

   // cout<<"PHASE 2"<<endl;
    for(int M = X, mN = 0; M >= 0; M--, mN++) {

        for(int lX = M, lXN = 0; lX >= 0; lX--, lXN++) {
            for(int rY = Y, rYN = 0; rY < n; rY++, rYN++) {

             //   cout<<lX<<" "<<M<<" "<<rY<<endl;
                calc(preX[lX] - preX[M], max(preX[M], preY[M]), 0, preY[rY], lXN, rYN, (mN * 2) + 1, 0);
            }
        }

    }

  //  cout<<"PHASE 3"<<endl;

     for(int M = X + 1, mN = 0; M < Y; M++, mN++) {

        for(int lX = X, lXN = 0; lX >= 0; lX--, lXN++) {
            for(int rY = Y, rYN = 0; rY < n; rY++, rYN++) {

               // cout<<lX<<" "<<M<<" "<<rY<<endl;
                calc(preX[lX], preX[M - 1], preY[M + 1], max(preX[M], preY[M]), lXN, rYN, (Y - X + 1) - 2 + 1 , 0);
            }
        }

    }

       // cout<<"PHASE 4"<<endl;

      for(int M = Y, mN = 0; M < n; M++, mN++) {

        for(int lX = X, lXN = 0; lX >= 0; lX--, lXN++) {
            for(int rY = M, rYN = 0; rY < n; rY++, rYN++) {

               // cout<<lX<<" "<<M<<" "<<rY<<endl;
                calc(preY[rY] - preY[M], max(preX[M], preY[M]), 0, preY[rY], lXN, rYN, (mN * 2) + 1, 0);
            }
        }

    }




    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17