oj.uz

Submission #156769

# Submission time Handle Problem Language Result Execution time Memory
156769 2019-10-07T10:41:55 Z brcode Safety (NOI18_safety) C++14
0 / 100
 17 ms 632 KB 
#include <iostream>
#include <deque>
using namespace std;
const int MAXN = 5e3+5;
const int MAXK = 5e3+5;
deque<pair<int,int>> d1;
int dp[3][MAXK];
int arr[MAXN];
int main(){
    int n,h;
    cin>>n>>h;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=min(MAXK-1,h);j++){
            int hold = dp[(i-1)%2][j];
            while(d1.size() && d1.back().first>hold){
                d1.pop_back();
            }
            d1.push_back(make_pair(hold,j));

        }
        for(int j=0;j<MAXK;j++){

            dp[i%2][j] = d1.front().first+abs(j-arr[i]);
            if(j<=10){
             //   cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<d1.front().first<<" "<<d1.front().second<<endl;
            }
            if(d1.front().second == j-h){
                d1.pop_front();
            }
            if(j+1+h<MAXK){
                int hold = dp[(i-1)%2][j+1+h];
                while(d1.size() && d1.back().first>hold){
                    d1.pop_back();
                }
                d1.push_back(make_pair(hold,j+h+1));
            }

        }
        while(d1.size()){
            d1.pop_back();
        }
    }
    int ans = 1e9;
    for(int i=1;i<MAXK;i++){
        ans = min(ans,dp[n%2][i]);
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Incorrect 3 ms 376 KB Output isn't correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 11.0

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

Subtask #8
0 / 22.0

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

Subtask #9
0 / 29.0

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