Submission #1238447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238447		ksu2009en	봉쇄 시간 (IOI23_closing)	C++20	0 / 100	31 ms	6724 KiB

closing

#include "closing.h"

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

ll n, x, y, k;

vector<pair<ll, ll>> d[3007];

int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n = N, x = X, y = Y, k = K;
    
    if(x > y)
        swap(x, y);
    
    vector<ll> w(n);
    
    for(int i = 0; i < n - 1; i++){
        d[U[i]].push_back({V[i], W[i]});
        d[V[i]].push_back({U[i], W[i]});
        
        w[min(U[i], V[i])] = W[i];
    }
    
    vector<ll> a(n), b(n), c(n);

    for(int i = x - 1; i >= 0; i--)
        a[i] = a[i + 1] + w[i];
    
    for(int i = x + 1; i < n; i++)
        a[i] = a[i - 1] + w[i - 1];
    
    for(int i = y - 1; i >= 0; i--)
        b[i] = b[i + 1] + w[i];
    
    for(int i = y + 1; i < n; i++)
        b[i] = b[i - 1] + w[i - 1];
    
    for(int i = 0; i < n; i++)
        c[i] = max(a[i], b[i]);
    
    vector<ll> p1(n), p2(n), p3(n);
    
    for(int i = 0; i < n; i++){
        if(i != 0){
            p1[i] = p1[i - 1],
            p2[i] = p2[i - 1],
            p3[i] = p3[i - 1];
        }
        
        p1[i] += a[i];
        p2[i] += b[i];
        p3[i] += c[i];
    }
    
    ll ans  = 0;
    
    for(int i = 0; i <= y; i++){
        vector<pair<ll, ll>> vec;
        vector<ll> ind(n, -1);
        
        for(int j = min((int)x, i - 1); j >= 0; j--)
            vec.push_back({a[j], j});
        
        for(int j = max((int)y, i + 1); j < n; j++)
            vec.push_back({b[j], j});

        sort(vec.begin(), vec.end());
        
        for(int j = 0; j < (ll)(vec.size()); j++)
            ind[vec[j].second] = j;
        
        ll cur = -1, sum = 0, cnt = 0, non_del = 0;
        
        if(i > x)
            cnt += p1[i - 1] - p1[x];
        if(i <= y)
            cnt += p2[y] - (i != 0 ? p2[i - 1] : 0);
        
//        if(i == 3){
//            for(auto j: vec)
//                cout << j.first << ' ' << j.second << endl;
//        }
        
        for(int j = i; j < n; j++){
            cnt += c[j];
            
            if(j <= y)
                cnt -= b[j];
            
//            if(i == 3){
//                cout << "cnt    " << j << ' ' << cnt << endl;
//            }
            
            if(ind[j] != -1){
                vec[ind[j]].second = -1;
                
                if(ind[j] <= cur){
                    sum -= vec[ind[j]].first;
                    non_del--;
                }
            }
            
            if(y < i || j < x)
                continue;
            
            while(cur >= 0 && cnt + sum > k){
                if(vec[cur].second == -1){
                    cur--;
                    continue;
                }
                
                sum -= vec[cur].first;
                cur--;
                
                non_del--;
            }
            
            while(cur + 1 < vec.size()){
                if(vec[cur + 1].second == -1){
                    cur++;
                    continue;
                }
                
                if(cnt + vec[cur + 1].first + sum <= k){
                    sum += vec[cur + 1].first;
                    cur++;
                    
                    non_del++;
                }
                else
                    break;
            }
            
            if(cnt + sum <= k){
//                cout << " !! " << i << ' ' << j << ' ' << cur << ' ' << sum << ' ' << non_del << endl;
                ans = max(ans, (j - i + 1) * 2 + non_del);
                
//                cout << "      ANS       " << i << ' ' << j << " CNT : " << cnt << endl;
//                if(ans == 6){
//                }
            }
        }
    }
    
    ll l1 = x, r1 = x, l2 = y, r2 = y, cnt = 2, sum = 0;
    
    while(sum <= k){
        ll val1 = (l1 - 1 >= 0 ? a[l1 - 1] : (ll)(1e18));
        ll val2 = (r1 + 1 < l2 ? a[r1 + 1] : (ll)(1e18));
        
        ll val3 = (l2 - 1 > r1 ? b[l2 - 1] : (ll)(1e18));
        ll val4 = (r2 + 1 < n ? b[r2 + 1] : (ll)(1e18));
        
        ll s = min({val1, val2, val3, val4});
        
        if(sum + s > k)
            break;
        
        cnt++;
        sum += s;
        
        if(val1 == s)
            l1--;
        else if(val4 == s)
            r2++;
        else if(val2 == s)
            r1++;
        else
            l2--;
    }
    
    ans = max(ans, cnt);
    
    return ans;
}

/*
 
 1
 7 2 5 8
 0 1 2
 1 2 3
 2 3 4
 3 4 2
 4 5 5
 5 6 3
 
 1
 7 2 4 24
 0 1 2
 1 2 3
 2 3 4
 3 4 2
 4 5 5
 5 6 3
 
 */

• 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