#1151903 (C++23) No.3459 Defeat Slimes

• 問題: No.3459 Defeat Slimes
• ユーザー: Taiki0715
• 提出日時: 2026-03-07 20:18:31
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 2,188 bytes
• コンパイル時間: 5,122 ms
• コンパイル使用メモリ: 388,916 KB
• 実行使用メモリ: 17,784 KB
• 最終ジャッジ日時: 2026-03-07 20:18:51
• 合計ジャッジ時間: 14,263 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 3
other	AC * 16 WA * 14

ソースコード

#include "bits/stdc++.h"
#include "atcoder/all"
using namespace std;
using namespace atcoder;
using ll=long long;
using mint=modint998244353;
#define rep3(i,a,b) for(int i=a;i<(b);i++)
#define rep2(i,n) rep3(i,0,n)
#define overload(a,b,c,d,...) d
#define rep(...) overload(__VA_ARGS__,rep3,rep2)(__VA_ARGS__)
#define all(x) x.begin(),x.end()
template<typename T>
istream&operator>>(istream&is,vector<T>&a){
	for(T&x:a)is>>x;
	return is;
}
template<typename T>
ostream&operator<<(ostream&os,const vector<T>&a){
	os<<'{';
	for(const T&x:a)os<<x<<',';
	os<<'}';
	return os;
}
template<typename T>
void operator++(vector<T>&a,int){
	for(T&x:a)x++;
}
template<typename T>bool chmin(T&a,T b){
	if(a>b){
		a=b;
		return true;
	}
	return false;
}
template<typename T>bool chmax(T&a,T b){
	if(a<b){
		a=b;
		return true;
	}
	return false;
}
#ifdef LOCAL
template<typename T>
void debug_rec(T a){
	cerr<<' '<<a<<'\n';
}
template<typename T1,typename... T2>
void debug_rec(T1 a,T2... b){
	cerr<<' '<<a;
	debug_rec(b...);
}
template<typename T1,typename... T2>
void debug(T1 a,T2... b){
	cerr<<"debug";
	debug_rec(a,b...);
}
#else
#define debug(...)
#endif
struct dat{
	ll c,l,x;
	bool operator<(const dat&rhs)const{
		return x<rhs.x;
	}
};
constexpr ll inf=3e18;
ll safe_mul(ll a,ll b){
	if(a==0)return 0;
	if(inf/a>b)return inf;
	return min(inf,a*b);
}
int main(){
	int n;
	ll y,z;
	cin>>n>>y>>z;
	vector<ll>stop(n+1);
	vector<dat>a(n);
	rep(i,n){
		ll c,l,x;
		cin>>c>>l>>x;
		a[i]={c,l,x};
		stop[i]=l;
	}
	stop[n]=z;
	sort(all(stop));
	stop.erase(unique(all(stop)),stop.end());
	sort(all(a),[&](dat lhs,dat rhs){
		return lhs.l<rhs.l;
	});
	priority_queue<dat>que;
	int ptr1=0,ptr2=0;
	ll ans=0;
	while(y<z){
		while(ptr1<n){
			if(a[ptr1].l<=y){
				que.push(a[ptr1++]);
			}
			else break;
		}
		if(que.empty()){
			cout<<"-1\n";
			return 0;
		}
		while(ptr2<(int)stop.size()&&y>=stop[ptr2])ptr2++;
		ll border=stop[ptr2];
		while(!que.empty()){
			auto [c,l,x]=que.top();
			que.pop();
			if(y+safe_mul(c,x)>=border){
				ll d=(border-y+x-1)/x;
				c-=d;
				y+=x*d;
				if(c)que.push({c,l,x});
				ans+=d;
				break;
			}
			else{
				y+=c*x;
				ans+=c;
			}
		}
	}
	cout<<ans<<endl;
}