Submission #1136775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136775		Unforgettablepl	Marathon Race 2 (JOI24_ho_t3)	C++20	81 / 100	759 ms	1114112 KiB

Main

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

#define int long long

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,f;
    cin >> n >> f;
    vector<int> balls(n+2);
    for(int i=1;i<=n;i++)cin>>balls[i];
    sort(balls.begin()+1, balls.begin()+1+n);
    balls[0]=balls[1];
    balls[n+1]=balls[n];
    vector DP(2,vector(n+1,vector(n+1,vector(2,(int)1e15))));
    DP[0][0][0][0]=0;
    DP[0][0][0][1]=balls[n]-balls[1];
    DP[1][0][0][1]=0;
    DP[1][0][0][0]=balls[n]-balls[1];
    for(int start=0;start<2;start++){
        for(int l=0;l<=n;l++) {
            for(int r=0;l+r<=n;r++) {
                if(l==0 and r==0)continue;
                // If end = 0
                if(l==0) {
                    DP[start][l][r][1]=DP[start][l][r-1][1]+(l+r)*(balls[n-r+2]-balls[n-r+1])+1;
                } else if(r==0) {
                    DP[start][l][r][0]=DP[start][l-1][r][0]+(l+r)*(balls[l]-balls[l-1])+1;
                } else {
                    DP[start][l][r][0]=min(DP[start][l-1][r][0]+(l+r)*(balls[l]-balls[l-1])+1,DP[start][l-1][r][1]+(l+r)*(balls[n-r+1]-balls[l])+1);
                    DP[start][l][r][1]=min(DP[start][l][r-1][1]+(l+r)*(balls[n-r+2]-balls[n-r+1])+1,DP[start][l][r-1][0]+(l+r)*(balls[n-r+1]-balls[l])+1);
                    DP[start][l][r][0]=min(DP[start][l][r][0],DP[start][l][r][1]+(l+r+1)*(balls[n-r+1]-balls[l]));
                    DP[start][l][r][1]=min(DP[start][l][r][1],DP[start][l][r][0]+(l+r+1)*(balls[n-r+1]-balls[l]));
                }
            }
        }
    }
    int q;
    cin >> q;
    for(int i=1;i<=q;i++) {
        int s,g,t;
        cin >> s >> g >> t;
        // Answer Query
        int ans = 1e15;
        int l = upper_bound(balls.begin()+1,balls.begin()+1+n,g)-balls.begin()-1;
        if(l!=0) ans = min(ans,DP[0][l][n-l][0]+abs(balls[0]-s)+(n+1)*abs(balls[l]-g));
        if(l!=0) ans = min(ans,DP[1][l][n-l][0]+abs(balls[n+1]-s)+(n+1)*abs(balls[l]-g));
        if(l!=n) ans = min(ans,DP[0][l][n-l][1]+abs(balls[0]-s)+(n+1)*abs(balls[l+1]-g));
        if(l!=n) ans = min(ans,DP[1][l][n-l][1]+abs(balls[n+1]-s)+(n+1)*abs(balls[l+1]-g));
        if(ans<=t)cout<<"Yes\n";
        else cout<<"No\n";
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 10 / 10
• Subtask 6: 19 / 19
• Subtask 7: 0 / 19