제출 #1251531

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251531		VahanAbraham	Closing Time (IOI23_closing)	C++20	21 / 100	1093 ms	25924 KiB

closing

#define _CRT_SECURE_NO_WARNINGS
#include "closing.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
#include <random>
#include <chrono>
#include <bitset>
#include <cassert>
using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen(".in", "r", stdin); freopen(".out", "w", stdout);

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}
ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 200005;
const ll oo = 1000000000000000000, MOD = 1000000007;

vector<pair<int,ll>> g[N];
ll ans[3][N];

void dfs(int u, int ty,int p,ll sum) {
    for (pair<int, ll> num : g[u]) {
        if (num.fr != p) {
            ans[ty][num.fr] = sum + num.sc;
            dfs(num.fr, ty, u, sum + num.sc);
        }
    }
}


int max_score(int N, int X, int Y, long long K, std::vector<int> U,
    std::vector<int> V, std::vector<int> W) {
    int n = N, x = X, y = Y;
    ll k = K;
    if (x >= y) {
        while (1) {

        }
    }
    for (int i = 0; i < n; ++i) {
        g[i].clear();
    }
    for (int i = 0; i < n; ++i) {
        ans[0][i] = ans[1][i] = 0;
    }
    for (int i = 0; i < n - 1; ++i) {
        g[U[i]].pb({ V[i],W[i] });
        g[V[i]].pb({ U[i],W[i] });
    }
    dfs(x, 0, -1, 0);
    dfs(y, 1, -1, 0);
    int pat = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int rx = min(x + i - 1, n - 1), ly = max(y - j + 1, 0), qan = 0;
            ll sm = 0;
            for (int ind = 0; ind < n; ++ind) {
                if (ind >= x && ind <= rx && ind>=ly && ind<=y) {
                    sm += max(ans[0][ind], ans[1][ind]);
                    qan += 2;
                }
                else {
                    if (ind >= ly && ind <= y) {
                        sm += ans[1][ind];
                        if (ly == y) {
                            if (ans[1][ind] != 0) {
                                while (1) {

                                }
                            }
                        }
                        ++qan;  
                    }
                    if (ind >= x && ind <= rx) {
                        sm += ans[0][ind];
                        if (rx == x) {
                            if (ans[0][ind] != 0) {
                                while (1) {

                                }
                            }
                        }
                        ++qan;
                    }
                }
            }
            if (x == 254 && y == 499 && i == 1 && j == 1) {

            }
            qan += max(x - ly, 0);
            qan += max(rx - y, 0);
            ll mnac = k - sm;
            if (mnac >= 0) {
                sm = 0;
                int minchev = min(x, ly) - 1;
                ll sm1 = 0;
                while (minchev >= 0 && sm1+ans[0][minchev]<=mnac) {
                    sm1 += ans[0][minchev];
                    --minchev;
                    ++qan;
                }
                ++minchev;
                pat = max(pat, qan);
                for (int ind = max(y, rx) + 1; ind < n; ++ind) {
                    mnac -= ans[1][ind];
                    if (mnac < 0) {
                        break;
                    }
                    while (minchev < min(x, ly) && sm1>mnac) {
                        sm1 -= ans[0][minchev];
                        --qan;
                        ++minchev;
                    }
                    ++qan;
                    pat = max(pat, qan);
                }
            }
        }
    }
    /*if (pat == 0) {
        cout << "GTAV" << " " << x << " " << y << " " << n << " " << k << endl;
    }*/
    return pat;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 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