제출 #1157379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157379		mychecksedad	Marathon Race 2 (JOI24_ho_t3)	C++20	100 / 100	208 ms	134824 KiB

Main

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 5000+10, K = 52, MX = 30;
const ll INF = 1e16;

int n, m;
ll a[N], L, dp[M][M][2][2];
vector<pair<ll, int>> b;
vi pref;
vi suf;
ll cost(int pf, int sf, int last, int nxt){
  return (ll)(pref[pf] + suf[sf] + 1) * abs(b[last].ff - b[nxt].ff);
}
void solve(){
  cin >> n >> L;
  for(int i = 1; i <= n; ++i){
    cin >> a[i];
  }
  int q; cin >> q;
  sort(a+1, a+1+n);
  for(int i = 1; i <= n; ++i){
    if(b.empty() || b.back().ff != a[i]) b.pb({a[i], 1}); 
    else b.back().ss++;
  }
  b.insert(b.begin(), {b[0].ff, 0});
  b.pb({b.back().ff, 0});
  m = int(b.size()) - 2;

  if(m >= M-15){
    for(int i = 1; i <= q; ++i){
      int l, r, t; cin >> l >> r >> t;
      cout << "No" << '\n';
    }
    return;
  }
  pref.pb(0);
  for(int i = 1; i <= m; ++i){
    pref.pb(pref.back() + b[i].ss);    
  }
  pref.pb(pref.back());

  suf.pb(0);
  for(int i = m; i >= 1; --i){
    suf.pb(suf.back() + b[i].ss);    
  }

  suf.pb(suf.back());

  for(int i = 0; i <= m; ++i) for(int j = 0; j <= m; ++j) dp[i][j][0][0]=dp[i][j][0][1]=dp[i][j][1][0]=dp[i][j][1][1]=INF;
  dp[0][0][0][0] = 0;
  dp[0][0][0][1] = b.back().ff - b.front().ff;
  dp[0][0][1][0] = b.back().ff - b.front().ff;
  dp[0][0][1][1] = 0;
  for(int d = 1; d <= m; ++d){
    for(int l = 0; l <= d; ++l){
      int r = d - l;
      dp[l][r][0][0] = min({
        (l > 0 ? dp[l - 1][r][0][0] + cost(l - 1, r, l - 1, l) : INF),
        (l > 0 ? dp[l - 1][r][0][1] + cost(l - 1, r, m + 1 - r, l) : INF)
      });
      dp[l][r][0][1] = min({
        (r > 0 ? dp[l][r - 1][0][0] + cost(l, r - 1, l, m + 1 - r) : INF),
        (r > 0 ? dp[l][r - 1][0][1] + cost(l, r - 1, m + 1 - r + 1, m + 1 - r) : INF)
      });
      dp[l][r][1][0] = min({
        (l > 0 ? dp[l - 1][r][1][0] + cost(l - 1, r, l - 1, l) : INF),
        (l > 0 ? dp[l - 1][r][1][1] + cost(l - 1, r, m + 1 - r, l) : INF)
      });
      dp[l][r][1][1] = min({
        (r > 0 ? dp[l][r - 1][1][0] + cost(l, r - 1, l, m + 1 - r) : INF),
        (r > 0 ? dp[l][r - 1][1][1] + cost(l, r - 1, m + 1 - r + 1, m + 1 - r) : INF)
      });

      dp[l][r][0][0] = min(dp[l][r][0][0], dp[l][r][0][1] + cost(l, r, l, m + 1 - r));
      dp[l][r][0][1] = min(dp[l][r][0][1], dp[l][r][0][0] + cost(l, r, l, m + 1 - r));
      dp[l][r][1][0] = min(dp[l][r][1][0], dp[l][r][1][1] + cost(l, r, l, m + 1 - r));
      dp[l][r][1][1] = min(dp[l][r][1][1], dp[l][r][1][0] + cost(l, r, l, m + 1 - r));
    }
  }
  for(int i = 1; i <= q; ++i){
    ll s, e, t; cin >> s >> e >> t;
    int L = lower_bound(all(b), pair<ll,int>{e, -1}) - b.begin();
    ll ans = INF;
    for(int j = L-2; j <= L+2; ++j){
      if(j>=0&&j<=m){
        ans=min({ans, 
          dp[j][m-j][0][0] + abs(s - b[0].ff) + abs(b[j].ff - e) * (n+1),
          dp[j][m-j][0][1] + abs(s - b[0].ff) + abs(b[j + 1].ff - e) * (n+1),
          dp[j][m-j][1][0] + abs(b.back().ff - s) + abs(b[j].ff - e) * (n+1),
          dp[j][m-j][1][1] + abs(b.back().ff - s) + abs(b[j + 1].ff - e) * (n+1)
        });
      }
    }
    cout << (ans + n <= t ? "Yes" : "No") << '\n';
  }
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

• 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: 19 / 19