oj.uz

Submission #1055227

# Submission time Handle Problem Language Result Execution time Memory
1055227 2024-08-12T15:43:43 Z Mokocraft Safety (NOI18_safety) C++14
0 / 100
 37 ms 3744 KB 
#include <iostream>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <cmath>
#include <queue>
/*
void showq(std::priority_queue<int> qL, std::priority_queue<int, std::vector<int>, std::greater<int>> qR)
{
    while(!qL.empty())
    {
        std::cout << qL.top() << ' ';
        qL.pop();
    }
    while(!qR.empty())
    {
        std::cout << ' ' << qR.top();
        qR.pop();
    }
    std::cout << std::endl;
    return;
}
*/
int main()
{
    //freopen("duotaB.txt", "r", stdin);

    int n, h;
    std::cin >> n >> h;

    int arr[n];
    for(int i = 0; i < n; i++)
        std::cin >> arr[i];

    std::priority_queue<int> qL;
    std::priority_queue<int, std::vector<int>, std::greater<int>> qR;

    int min = 0;
    qL.emplace(arr[0]);
    qR.emplace(arr[0]);

    //showq(qL, qR);

    for(int i = 1; i < n; i++)
    {
        if(arr[i] + h*i < qL.top())
        {
            qL.emplace(arr[i] + h*i);
            qL.emplace(arr[i] + h*i);
            min += qL.top() - arr[i] - i*h;
            qR.emplace(qL.top() - 2*i*h);
            qL.pop();
        }
        else if(arr[i] - h*i > qR.top())
        {
            qR.emplace(arr[i] - h*i);
            qR.emplace(arr[i] - h*i);
            min +=  arr[i] - i*h - qR.top();
            qL.emplace(qL.top() + 2*i*h);
            qR.pop();
        }
        else
        {
            qL.emplace(arr[i] + i*h);
            qR.emplace(arr[i] - i*h);
        }
         

        //showq(qL, qR);
    }

    std::cout << min;

    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 3744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Incorrect 0 ms 600 KB Output isn't correct
5 Halted 0 ms 0 KB -