제출 #1141174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141174		hennessey	Marathon Race 2 (JOI24_ho_t3)	C++20	62 / 100	1601 ms	220428 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: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19