제출 #1309503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309503		haught_veath	Fuel Station (NOI20_fuelstation)	C++20	0 / 100	3092 ms	14392 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6;
const int inf = 1e18;
int dp[maxn];
struct information{
  int x,f,r;
  bool operator <(const information a)const {
    return x < a.x;
  }
};
int n,h;
vector<information> a;
bool check(int x){
    int m = a.size();
    fill(dp, dp + m, -1);
    dp[0] = x;

    for(int i = 1; i < m; i++){
        for(int j = 0; j < i; j++){
            if(dp[j] < 0) continue;
            int cost = dp[j] - (a[i].x - a[j].x);
            if(cost >= 0){
                dp[i] = max(dp[i], min(cost, a[i].r) + a[i].f);
            }
        }
        if(a[i].x >= h && dp[i] >= 0) return true;
    }
    return false;
}

void solve(){
  int l = 0, r = inf;
  int ans = 0;
  while(l <= r){
    int mid = (l+r)/2;
    if(check(mid)) {
      r = mid-1;
      ans = mid;
    }
    else l = mid + 1;
  }
  cout << ans;
}
signed main(){
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);
  cin >> n >> h;
  a.resize(n+1);
  for(int i = 1;i<=n;i++)
    cin >> a[i].x >> a[i].f >> a[i].r;
  
  a.push_back({h,0,inf});
  sort(a.begin()+1,a.end());
  solve();
  
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 12
• Subtask 5: 0 / 19
• Subtask 6: 0 / 11
• Subtask 7: 0 / 21