oj.uz

Submission #115247

# Submission time Handle Problem Language Result Execution time Memory
115247 2019-06-06T11:00:22 Z oolimry Rice Hub (IOI11_ricehub) C++14
17 / 100
 1000 ms 1832 KB 
#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;
int besthub(int R, int L, int X[], long long B)
{
    vector<int> untaken;
    for(int i = 0;i < R;i++){
        untaken.push_back(X[i]);
    }
    //untaken.push_back(4 * L);
    sort(untaken.begin(),untaken.end());
    reverse(untaken.begin(),untaken.end());
    deque<int> left, right; ///front-closest, back-furthest
    long long acc = 0;
    int ans = 0;
    for(int i = 1;i <= L;i++){
        bool stop = false;
        while(!right.empty() && right.front() == i-1){
            right.pop_front();
            left.push_front(i-1);
        }
        acc -= right.size();
        acc += left.size();

        while(true){
            if(acc > B){
                if(right.empty()){
                    acc -= abs(left.back() - i);
                    left.pop_back();
                }
                else if(left.empty()){
                    acc -= abs(right.back() - i);
                    untaken.push_back(right.back());
                    right.pop_back();
                    stop = true;
                }
                else{
                    if(abs(right.back() - i) > abs(left.back() - i)){
                        acc -= abs(right.back() - i);
                        untaken.push_back(right.back());
                        right.pop_back();
                        stop = true;
                    }
                    else{
                        acc -= abs(left.back() - i);
                        left.pop_back();
                    }
                }
            }
            else{
                if(stop) break;
                ans = max(ans, (int)(left.size() + right.size()));
                if(untaken.empty()){
                    break;
                }
                acc += abs(untaken.back() - i);
                right.push_back(untaken.back());
                untaken.pop_back();
            }
        }
    }
    return ans;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 428 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 2 ms 256 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 256 KB Output is correct
25 Correct 2 ms 384 KB Output is correct
26 Correct 2 ms 256 KB Output is correct
27 Incorrect 2 ms 256 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 9 ms 256 KB Output is correct
4 Correct 12 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Incorrect 2 ms 384 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 6 ms 740 KB Output is correct
3 Execution timed out 1071 ms 1832 KB Time limit exceeded
4 Halted 0 ms 0 KB -