Submission #1141173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141173		hennessey	Maze (JOI23_ho_t3)	C++20	0 / 100	207 ms	220196 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

vector <int> arr = {};
vector <vector <vector <int>>> dp(2002, vector <vector <int>>(2002, vector <int>(2, -1)));
int dps(int c1, int c2, int n, int end, int t) {
    if((c2-c1) < 0) {
        if(t == 0) {
            int v = arr[c1-1];
            return abs(end-v)*(n+1);
        } else {
            int v = arr[c2+1];
            return abs(end-v)*(n+1);
        }
    }
    if(dp[c1][c2][t] != -1) {
        return dp[c1][c2][t];
    }
    int totalm = 1e18;
    int v1 = c1+(n-(c2+1));
    if(t == 0) {
        int data = dps(c1+1, c2, n, end, 0)+((arr[c1]-arr[c1-1])*(v1+1));
        int data2 = dps(c1, c2-1, n, end, 1)+((arr[c2]-arr[c1-1])*(v1+1));
        totalm = min(data, data2);
    } else {
        int data = dps(c1+1, c2, n, end, 0)+((arr[c2+1]-arr[c1])*(v1+1));
        int data2 = dps(c1, c2-1, n, end, 1)+((arr[c2+1]-arr[c2])*(v1+1));
        totalm = min(data, data2);
    }
    return dp[c1][c2][t] = totalm;
}

signed main() {
    //your code goes here
    int n, l;
    cin >> n >> l;
    for(int i = 0; i < n; i++) {
        int num;
        cin >> num;
        arr.push_back(num);
    }
    sort(arr.begin(), arr.end());
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j][0] = -1;
                dp[i][j][1] = -1;
            }
        }
        int s, g, t;
        cin >> s >> g >> t;
        int data = dps(1, n-1, n, g, 0)+abs(s-arr[0]);
        int data2 = dps(0, n-2, n, g, 1)+abs(s-arr[n-1]);
        // cout << data << " " << data2 << " " << abs(arr[0]) << endl;
        if((min(data, data2)+n) <= t) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6