oj.uz

Submission #1006987

# Submission time Handle Problem Language Result Execution time Memory
1006987 2024-06-24T10:34:23 Z 3as8 Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 15328 KB 
#include "closing.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;


#define ll long long
#define pll pair<ll, ll>

ll n;
vector<pair<ll, ll> > graph[N];
ll dist[N][2];

void dfs(ll startIndex, ll ind, ll p = -1, ll dep = 0) {


    dist[startIndex][ind] = dep;
    for(auto [el, w] : graph[startIndex]) {
        if(el == p) continue;

        dfs(el, ind, startIndex, dep + w);
    }

}


ll ans;
ll k;
void calc(ll a, ll b, ll c, ll d, ll A, ll B, ll C, ll D) {

    ll sum = a + b + c + d;
    ll num = A + B + C + D;

    if(sum <= k) {
       // cout<<" => "<<sum<<" "<<k<<": "<<num + 2<<endl;
        ans = max(ans, num + 2);
    }

}

void d(vector<ll>& preX, vector<ll>& arr, ll X) {

    preX[X] = 0;
    for(int i = X - 1; i >=0; i--) {
        preX[i] = ( 2 * preX[i + 1]) + arr[i];
    }
    for(int i = X + 1; i < n; i++) {
        preX[i] = ( 2 * preX[i - 1]) + arr[i - 1];
    }

}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) {

    ans = LLONG_MIN;
    n = N;
    k = K;
    for(int i = 0 ; i < n; i++ ) {
        graph[i].clear();
    }

    vector<ll> arr(n);

    for(int i = 0; i < n - 1; i++) {
        arr[i] = W[i];
    }

    if(X > Y) swap(X, Y);

    vector<ll> preX(n), preY(n);
    d(preX, arr, X);
    d(preY, arr, Y);

    /*for(int i = 0; i < n; i++) {
        cout<<preX[i]<<" ";
    }
    cout<<endl;

      for(int i = 0; i < n; i++) {
        cout<<preY[i]<<" ";
    }
    cout<<endl;*/


    //cout<<"PHASE 1"<<endl;
    for(int lX = X, lXN = 0; lX >= 0; lX--, lXN++) {
        for(int rX = X, rXN = 0; rX < n; rX++, rXN++) {
            for(int lY = Y, lYN = 0; lY >= 0; lY--, lYN++) {
                for(int rY = Y, rYN = 0; rY < n; rY++, rYN++) {

                    if(rX >= lY) continue;

                  //  cout<<lX<<" "<<rX<<" "<<lY<<" "<<rY<<endl;

                    calc(preX[lX], preX[rX], preY[lY], preY[rY], lXN, rXN, lYN, rYN);
                }
            }
        }
    }

   // cout<<"PHASE 2"<<endl;
    for(int M = X, mN = 0; M >= 0; M--, mN++) {


        for(int lX = M - 1, lXN = 0; lX >= 0; lX--, lXN++) {
            vector<ll> preNX(n);
            d(preNX, arr, lX);
            for(int rY = Y, rYN = 0; rY < n; rY++, rYN++) {

             //   cout<<lX<<" "<<M<<" "<<rY<<endl;
                calc(preNX[M], max(preX[M], preY[M]), 0, preY[rY], lXN, rYN, (mN * 2) + 1, 0);
            }
        }

    }

  //  cout<<"PHASE 3"<<endl;

     for(int M = X + 1, mN = 0; M < Y; M++, mN++) {

        for(int lX = X, lXN = 0; lX >= 0; lX--, lXN++) {
            for(int rY = Y, rYN = 0; rY < n; rY++, rYN++) {

               // cout<<lX<<" "<<M<<" "<<rY<<endl;
                calc(preX[lX], preX[M - 1], preY[M + 1], max(preX[M], preY[M]), lXN, rYN, (Y - X + 1) - 2 + 1 , 0);
            }
        }

    }

       // cout<<"PHASE 4"<<endl;

      for(int M = Y, mN = 0; M < n; M++, mN++) {

        for(int lX = X, lXN = 0; lX >= 0; lX--, lXN++) {
            for(int rY = M, rYN = 0; rY < n; rY++, rYN++) {
                vector<ll> preNX(n);
                d(preNX, arr, rY);
                   // cout<<lX<<" "<<M<<" "<<rY<<endl;
                calc(preNX[M], max(preX[M], preY[M]), 0, preX[lX], lXN, rYN, (mN * 2) + 1, 0);
            }
        }

    }




    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 15328 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 5976 KB Output is correct
2 Incorrect 1 ms 5980 KB 1st lines differ - on the 1st token, expected: '30', found: '19'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

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

Subtask #6
0.0 / 11.0

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

Subtask #7
0.0 / 10.0

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

Subtask #8
0.0 / 10.0

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

Subtask #9
0.0 / 17.0

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