oj.uz

Submission #1006842

# Submission time Handle Problem Language Result Execution time Memory
1006842 2024-06-24T09:15:15 Z Amr Closing Time (IOI23_closing) C++17
21 / 100
 1000 ms 11252 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];
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;
    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];
    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;
            for(int j = fx; j >= 0; j--)
            {
                our+=disx[j];
                if(dif-our>=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 4444 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 1087 ms 11252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 0 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 0 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 5 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 4 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4552 KB Output is correct

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 0 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 0 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 0 ms 4444 KB Output is correct
14 Correct 1 ms 4444 KB Output is correct
15 Correct 0 ms 4444 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 5 ms 4444 KB Output is correct
20 Correct 1 ms 4444 KB Output is correct
21 Correct 4 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 1 ms 4444 KB Output is correct
24 Correct 1 ms 4552 KB Output is correct
25 Correct 2 ms 4444 KB Output is correct
26 Execution timed out 1047 ms 4700 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 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 4444 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 4444 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 4444 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 4444 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -