Submission #1309498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309498		haught_veath	Fuel Station (NOI20_fuelstation)	C++20	0 / 100	3094 ms	15296 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){
  memset(dp,-1,sizeof(dp));
  dp[0]  = x;
  a[0] = {0,0,0};
  for(int i = 1;i < a.size();i++)
  {
    dp[i] = -1;
    for(int j = 0;j < i ;j++)
    {
      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] != -1)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