Submission #1006923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006923		Amr	Closing Time (IOI23_closing)	C++17	0 / 100	1059 ms	12780 KiB

closing

// start at :10:36
#include "closing.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
const int M = 2e5+3;
ll n , k;
ll disx[M], disy[M] , ansx[M], ansy[M],prex[M];
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    // it's chain
    n = N , k = K;
    for(int i = 0; i <= n; i++) disx[i] = disy[i] = ansx[i] = ansy[i] = 0;
    for(int i = 0; i <= n+1; i++) prex[i] = 0;
    ll mainbest = 0;
    if(X>Y) swap(X,Y);
    ll x = X , y = Y;
    for(int i = x+1; i < n; i++) disx[i] = disx[i-1]+W[i-1];
    for(int i = x-1; i >= 0; i--) disx[i] = disx[i+1]+W[i];
    for(int i = y+1; i < n; i++) disy[i] = disy[i-1]+W[i-1];
    for(int i = y-1; i>=0; i--) disy[i] = disy[i+1]+W[i];
    prex[x] = 0;
    ll myour = 0;
    for(int i = x-1; i >= 0; i--)
    {
        myour+=disx[i];
        prex[i] = myour;
    }

   // for(int i = 0; i <= x; i++) cout << prex[i] << " "; cout << endl;
    ll tailx = X , taily = Y, sum = 0;
    while(sum<=k)
    {
        // make brute force
        ll fx = min(x-1,taily-1), fy = max(y+1,tailx+1);
        ll bestx = 0, dif = k-sum,besty = 0,best = 0;
        for(int i = fy; i < n ;i++) if(dif>=disy[i]) dif-=disy[i],besty++; else break;
        dif = k -sum;
        for(int i = fx; i >= 0; i--) if(dif>=disx[i]) dif-=disx[i],bestx++; else break;
        ll both = ((taily<x)*(x-taily)) + ((tailx>y)*(tailx-y));
        best = max(besty,bestx)+both;
        dif = k-sum;
        for(int i = fy; i < n ;i++)
        {
            dif-=disy[i];
            ll our = 0;
            /*ll l = -1 , r = fx+1;
            while(l+1<r)
            {
                ll mid = (l+r)/2;
                if(prex[mid]-prex[fx+1]<=dif) r = mid; else l = mid;
            }
            if(r!=fx+1);
            best = max(best,i-y+x-r);*/

            for(int j = fx; j >= 0; j--)
            {
                our+=disx[j];
                if(our-dif>=0) best = max(best,i-y+x-j);
            }

        }
        mainbest = max(mainbest,best+tailx-x+1+y-taily+1);

      //  cout << tailx << " " << taily << " " << sum << " " << best << " " << mainbest << " " << tailx-x+1+y-taily+1 << endl;

        if(taily==0&&tailx==n-1) break;
        // rise the sum
        if(taily==0)
        {
            sum+=disx[tailx+1]-ansy[tailx+1];
            ansx[tailx+1] = disx[tailx+1];
            tailx++;
        }
        else if(tailx==n-1)
        {
            sum+=disy[taily-1]-ansx[taily-1];
            ansy[taily-1] = disy[taily-1];
            taily--;
        }
        else
        {
            if(disx[tailx+1]-ansy[tailx+1] < disy[taily-1]-ansx[taily-1])
            {
                sum+=disx[tailx+1]-ansy[tailx+1];
                ansx[tailx+1] = disx[tailx+1];
                tailx++;
            }
            else
            {
                sum+=disy[taily-1]-ansx[taily-1];
                ansy[taily-1] = disy[taily-1];
                taily--;
            }
        }

    }
    return mainbest;
}

• 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