oj.uz

Submission #830702

# Submission time Handle Problem Language Result Execution time Memory
830702 2023-08-19T09:38:59 Z vjudge1 Safety (NOI18_safety) C++17
4 / 100
 504 ms 262144 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int nmax = 200002;
ll S[nmax];
ll dp[5005][5005];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int N;
    ll H;
    cin >> N >> H;
    for(int i=1; i<=N; i++) {
        cin >> S[i];
    }
    deque<pair<ll,ll>>dd;
    for(int i=0; i<=5000; i++) dp[1][i] = abs(S[1]-i);
    for(int i=2; i<=N; i++) {
        dd.clear();
        for(int j=0; j<=min(5000ll, H); j++) {
            while(!dd.empty() && dd.back().fi > dp[i-1][j]) {
                dd.pop_back();
            }
            dd.push_back({dp[i-1][j],j});
        }
        pair<ll,ll>sem;
        for(int j=0; j<=5000; j++) {
            if(!dd.empty() && dd.front().se < j-H) {
                dd.pop_front();
            }
            sem = dd.front();
            dp[i][j] = sem.fi + abs(S[i]-j);
            if(j-H+1 <= 5000) {
                while(!dd.empty() && dd.back().fi > dp[i-1][j+H+1]) {
                    dd.pop_back();
                }
                dd.push_back({dp[i-1][j+H+1], j+H+1});
            }
        }
    }
    ll jwb = LLONG_MAX;
    for(int i=0; i<=5000; i++) {
        jwb = min(jwb, dp[N][i]);
    }
    cout << jwb << endl;
    return 0;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 3 ms 724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
4.0 / 4.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 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 504 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 3 ms 724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 3 ms 724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 3 ms 724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 3 ms 724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Runtime error 3 ms 724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -