oj.uz

Submission #1006923

# Submission time Handle Problem Language Result Execution time Memory
1006923 2024-06-24T09:51:51 Z Amr Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 12780 KB 
// 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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 12780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Incorrect 1 ms 6492 KB 1st lines differ - on the 1st token, expected: '30', found: '35'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6488 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -