Submission #931230

#	Time	Username	Problem	Language	Result	Execution time	Memory
931230		vjudge1	Safety (NOI18_safety)	C++17	35 / 100	1683 ms	262144 KiB

safety

#include <bits/stdc++.h>
using namespace std;   
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n, h, mx = 0;
    cin >> n >> h;
    int v[n+1];

    for(int i=1; i<=n; i++) cin >> v[i], mx = max(mx, v[i]);
    h = min(h, mx);

    vector<vector<int> > dp(2, vector<int>(mx+1));
   
    for(int i=1; i<=n; i++) {
        for(int j=0; j<=mx; j++) {
            dp[1][j] = 1e9;
            int l=max(0, j-h), r=min(mx, j+h);
  
            while(r - l > 2) {
                int mid1 = l + (r - l) / 3;
                int mid2 = r - (r - l) / 3;
  
                if(dp[0][mid1] > dp[0][mid2]) l = mid1;
                else if(dp[0][mid1] < dp[0][mid2]) r = mid2;
                else l = mid1, r = mid2;
            }
  
            for(int p=l; p<=r; p++)
                dp[1][j] = min(dp[1][j], dp[0][p] + abs(v[i] - j));
        }
        swap(dp[0], dp[1]);
    }
   
    cout << *min_element(dp[0].begin(), dp[0].end()) << '\n';
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29