제출 #1205980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1205980		PagodePaiva	Closing Time (IOI23_closing)	C++20	0 / 100	31 ms	5188 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 3010;
long long l[N], r[N];
int n;
long long v[N];
int x, y;
long long k;

int max_score(int NN, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
    n = NN;
    x = X;
    y = Y;
    k = K;
    for(int i = x-1;i >= 0;i--){
        l[i] = l[i+1] + (long long) W[i];
    }
    for(int i = x+1;i < n;i++){
        l[i] = l[i-1] + (long long) W[i-1];
    }
    for(int i = y-1;i >= 0;i--){
        r[i] = r[i+1] + (long long) W[i];
    }
    for(int i = y+1;i < n;i++){
        r[i] = r[i-1] + (long long) W[i-1];
    }
    int ans = 0;
    for(int l2 = 0;l2 < n;l2++){
        int l1 = 0, r1 = n-1;
        long long sum = 0;
        for(int i = 0;i < n;i++){
            sum += l[i];
            v[i] = l[i];
        }
        while(sum > k){
            if(l1 == r1){
                sum = 0;
                l1++;
            }
            else{
                long long v1 = (l1 == x ? -1e16 : v[l1]);
                long long v2 = (r1 == x ? -1e16 : v[r1]);
                if(v1 < v2){
                    r1--;
                    sum -= v2;
                }
                else{
                    l1++;
                    sum -= v1;
                }
            }
        }
        ans = max(ans, r1-l1+1);
        /*if(l2 == 4){
            cout << sum << ' ' << l1 << ' ' << r1 << '\n';
        }*/
        long long custo = k;
        for(int r2 = l2;r2 < n;r2++){
            custo -= r[r2];
            if(custo < 0)
                break;
            if(l1 <= r2 and r2 <= r1)
                sum -= v[r2];
            v[r2] = max(0LL, l[r2]-r[r2]);
            if(l1 <= r2 and r2 <= r1)
                sum += v[r2];
            while(sum > custo){
                if(l1 == r1){
                    sum = 0;
                    l1++;
                }
                else{
                    long long v1 = (l1 == x ? -1e16 : v[l1]);
                    long long v2 = (r1 == x ? -1e16 : v[r1]);
                    if(v1 < v2){
                        r1--;
                        sum -= v2;
                    }
                    else{
                        l1++;
                        sum -= v1;
                    }
                }
            }
            /*if(l2 == 4 and r2 == 5){
                cout << l1 << ' ' << r1 << '\n';
                for(int t = 0;t < n;t++){
                    cout << v[t] << ' ';
                }
                cout << '\n';
                cout << sum << '\n';
            }*/
            if(l1 != r1){
                while(v[r1+1] + sum <= custo and r1+1 < n){
                    r1++;
                }
            }
            /*if(l2 == 4 and r2 == 5){
                cout << l1 << ' ' << r1 << '\n';
                for(int t = 0;t < n;t++){
                    cout << v[t] << ' ';
                }
                cout << '\n';
                cout << sum << '\n';
            }*/
            if(ans < r1-l1+1 + r2-l2+1){
               /* cout << r1 << ' ' << l1 << ' ' << r2 << ' ' << l2 << '\n';
                for(int i = 0;i < n;i++)
                    cout << v[i] << ' ';
                cout << '\n';*/
            }
            ans = max(ans, r1-l1+1 + r2-l2+1);
        }
    }
    for(int i = 0;i <= n;i++){
        l[i] = r[i] = v[i] = 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