Submission #1149814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149814		Cookie197	Marathon Race 2 (JOI24_ho_t3)	C++20	62 / 100	182 ms	63372 KiB

Main

// Cookie197 
// i am absolute trash
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include <cassert>
#include<random>
using namespace std;
#define i_am_trashQ_Q ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pii pair<ll,ll>
#define mp make_pair
#define mod 998244353
//#define mod 1000000007
#define endl "\n"
#define inf (ll)1e18
#define out(x) cout << #x << " = " << x <<endl
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << "  second = " << x.second << endl

ll n,l,q,m;
ll x[500005];
ll pos[500005], balls[500005], pre[500005], suf[500005];

ll dp[2005][2005][2];


void solve(){
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) dp[i][j][0] = dp[i][j][1] = inf;
    ll s,g,t; cin>>s>>g>>t;
    dp[1][0][0] = abs(s - pos[1]);
    dp[1][0][1] = inf;
    dp[0][1][1] = abs(s - pos[m]);
    dp[0][1][0] = inf;
    
    for (int i=2;i<=m;i++){
        dp[i][0][0] = dp[i-1][0][0] + (pre[i-1] + 1) * (pos[i] - pos[i-1]);
        //cout<<i<<"  "<<0<<"  "<<0<<"    "<<dp[i][0][0]<<endl;
    }
    for (int j=2;j<=m;j++){
        dp[0][j][1] =  dp[0][j-1][1] + (suf[j-1] + 1) * (pos[m-j+2] - pos[m-j+1]);
        //cout<<0<<"  "<<j<<"  "<<1<<"    "<<dp[0][j][1]<<endl;
    }
    for (int i=1;i<=m;i++){
        for (int j=1;i+j<=m;j++){
            ll r = inf;
            r = min(r, dp[i-1][j][0] + (pos[i] - pos[i-1]) * (pre[i-1] + suf[j] + 1));
            r = min(r, dp[i-1][j][1] + (pos[m-j+1] - pos[i]) * (pre[i-1] + suf[j] + 1));
            r = min(r, dp[i][j-1][0] + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j-1] + 1 + pre[i] + suf[j] + 1));
            r = min(r, dp[i][j-1][1] + (pos[m-j+2] - pos[m-j+1]) * (pre[i] + suf[j-1] + 1) + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j] + 1));
            dp[i][j][0] = r;

            r = inf;
            r = min(r, dp[i-1][j][0] + (pos[i] - pos[i-1]) * (pre[i-1] + suf[j] + 1) + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j] + 1));
            r = min(r, dp[i-1][j][1] + (pos[m-j+1] - pos[i]) * (pre[i-1] + suf[j] + 1 + pre[i] + suf[j] + 1));
            r = min(r, dp[i][j-1][0] + (pos[m-j+1] - pos[i]) * (pre[i] + suf[j-1] + 1));
            r = min(r, dp[i][j-1][1] + (pos[m-j+2] - pos[m-j+1]) * (pre[i] + suf[j-1] + 1));
            dp[i][j][1] = r;

            //cout<<i<<"  "<<j<<"  "<<0<<"    "<<dp[i][j][0]<<endl;
            //cout<<i<<"  "<<j<<"  "<<1<<"    "<<dp[i][j][1]<<endl;
        }
    }

    ll ans = inf;
    for (int i=0;i<=m;i++){
        if (i != 0) ans = min(ans, dp[i][m-i][0] + abs(pos[i] - g) * (n+1));
        if (i != m) ans = min(ans, dp[i][m-i][1] + abs(pos[i+1] - g) * (n+1));
    }
    //out(ans);
    if (ans + n <= t) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

signed main(){
    i_am_trashQ_Q
    cin>>n>>l;
    for (int i=1;i<=n;i++){
        cin>>x[i];
    }
    sort(x+1,x+1+n);
    int last = -1;
    for (int i=1;i<=n;i++){
        if (x[i] != last){
            m++;
            pos[m] = x[i];
            balls[m] = 1;
            last = x[i];
        }else balls[m]++;
    }
    for (int i=1;i<=m;i++) pre[i] = pre[i-1] + balls[i];
    for (int i=1;i<=m;i++) suf[i] = suf[i-1] + balls[m-i+1];

    for (int i=1;i<=m;i++){
        //cout<<"# "<<balls[i]<<"  "<<pre[i]<<"  "<<suf[i]<<"  "<<pos[i]<<endl;
    }
    
    cin>>q;
    if (q > 10) return 0;
    while(q--){
        solve();
    }
}

• 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