#pragma region watasou /* the pen is mightier than the sword. -エドワード・ブルワー=リットン- KCLC44TH watasou1543. */ #include #include using namespace std; using namespace atcoder; //マクロ宣言 #define rep(i, a, b) for (ll i = a; i < b; i++) #define Rrep(i, a, b) for (ll i = a; i >= b; i++) using ll = long long; using ld = long double; using pii = pair; using pli = pair; using pll = pair; using Graph = vector>; using V = vector; const ll mod=998244353; const ll MOD=1000000007; const ll INF=1000000000000000000; const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const string abc="abcdefghijklmnopqrstuvwxyz"; string Y = "Yes"; string N = "No"; #define gcd __gcd #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define fi first #define se second #define fix(n) fixed << setprecision(n) #define print(n) cout << n << endl #define si size() #define in(n) insert(n) //関数宣言 template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } #define YES(n) cout << ((n) ? "YES" : "NO" ) << endl #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl #define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE" ) << endl #define Possible(n) cout << ((n) ? "Possible" : "Impossible" ) << endl ll jou(ll N,ll k){ ll i=0; ll p=N; ll Ans=0; while(k>=(1<>Gra; mapvisited;// false=not visited, true=visited void DFS(int pos){ visited[pos]=true; for(int i : Gra[pos]){ if(visited[i]==false){ DFS(i); } } } vector > pri(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } const vectordx = {0, 1, 0, -1}; const vectordy = {1, 0, -1, 0}; vector> BFS(int H, int W, const vector &G, pair s) { vector> dist(H, vector(W, -1)); //すべての頂点を未訪問に初期化 queue> que; //初期条件 (頂点sを初期頂点とする) dist[s.first][s.second] = 0; que.push(s); // sを探索済み頂点に // BFS開始 while (!que.empty()) { pair v = que.front(); que.pop(); //頂点vからたどれる頂点を全て調べる for (int i = 0; i < 4; i++) { int X = dx[i] + v.first; int Y = dy[i] + v.second; if (X < 0 || X >= H || Y < 0 || Y >= W) continue; //すでに発見済みの頂点は探索しない if (dist[X][Y] != -1 || G[X][Y] == '#') continue; //新たな未探索点xについて距離情報を更新してキューに挿入 dist[X][Y] = dist[v.first][v.second] + 1; que.push(make_pair(X, Y)); } } return dist; } vectorsosuu(long long n){ vector isprime(n+1, true); // 0, 1 は予めふるい落としておく isprime[0] = isprime[1] = false; // ふるい for (int p = 2; p <= n; ++p) { // すでに合成数であるものはスキップする if (!isprime[p]) continue; // p 以外の p の倍数から素数ラベルを剥奪 for (int q = p * 2; q <= n; q += p) { isprime[q] = false; } } return isprime; } // a^n mod を計算する long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // Union-Find struct UnionFind { vector par, rank, siz; // 構造体の初期化 UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { } // 根を求める int root(int x) { if (par[x]==-1) return x; // x が根の場合は x を返す else return par[x] = root(par[x]); // 経路圧縮 } // x と y が同じグループに属するか (= 根が一致するか) bool same(int x, int y) { return root(x)==root(y); } // x を含むグループと y を含むグループを併合する bool unite(int x, int y) { int rx = root(x), ry = root(y); // x 側と y 側の根を取得する if (rx==ry) return false; // すでに同じグループのときは何もしない // union by rank if (rank[rx]P; struct edge{int to;ll cost;ll num;}; mapr; vector dijkstra(vector> graph, int n, int start, ll INF,ll now){ priority_queue,greater

>que; vectordst(n,INF); dst[start]=0; que.push(P(0,start)); while(que.size()){ ll d=que.top().first; int u=que.top().second; que.pop(); if(dst[u]1){ ll md=(ok+ng)/2; if(l+d*(md)<=num-dst[v]){ md=ng; } else{ md=ok; } } cost+=num-dst[v]-(l+d*(ok)); if(dst[v]>d+cost){ dst[v]=d+cost; que.push(P(dst[v],v)); } } } return dst; } // グラフ、頂点の入次数、頂点数を受け取り、そのトポロジカルソートを記録した配列を返す関数 vector topological_sort(vector> &G, vector &indegree, int V) { // トポロジカルソートを記録する配列 vector sorted_vertices; // 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する queue que; for (int i = 0; i < V; i++) { if (indegree[i] == 0) { que.push(i); } } // キューが空になるまで、操作1~3を繰り返す while (que.empty() == false) { // キューの先頭の頂点を取り出す int v = que.front(); que.pop(); if(que.size()!=1){ print(N); exit(0); } // その頂点と隣接している頂点の入次数を減らし、0になればキューに追加 for (int i = 0; i < (int)G[v].size(); i++) { int u = G[v][i]; indegree[u] -= 1; if (indegree[u] == 0) que.push(u); } // 頂点vを配列の末尾に追加する sorted_vertices.push_back(v); } // トポロジカルソートを返す return sorted_vertices; } using mint =modint998244353; using Mint =modint1000000007; #define debug cout << "OK" << endl; #pragma region template template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << "," << p.second << ")"; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << (i + 1 != (int)v.size() ? " " : ""); } return os; } template ostream &operator<<(ostream &os, const vector> &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i] << endl; } return os; } template ostream &operator<<(ostream &os, const vector>> &v) { for (int i = 0; i < (int)v.size(); i++) { os << "i = " << i << endl; os << v[i]; } return os; } template istream &operator>>(istream &is, vector &v) { for (T &in : v) is >> in; return is; } template ostream &operator<<(ostream &os, const map &mp) { for (auto &[key, val] : mp) { os << key << ":" << val << " "; } return os; } template ostream &operator<<(ostream &os, const set &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, const multiset &st) { auto itr = st.begin(); for (int i = 0; i < (int)st.size(); i++) { os << *itr << (i + 1 != (int)st.size() ? " " : ""); itr++; } return os; } template ostream &operator<<(ostream &os, queue q) { while (q.size()) { os << q.front() << " "; q.pop(); } return os; } template ostream &operator<<(ostream &os, deque q) { while (q.size()) { os << q.front() << " "; q.pop_front(); } return os; } template ostream &operator<<(ostream &os, stack st) { while (st.size()) { os << st.top() << " "; st.pop(); } return os; } template ostream &operator<<(ostream &os, priority_queue pq) { while (pq.size()) { os << pq.top() << " "; pq.pop(); } return os; } ostream &operator<<(ostream &os, const mint &i) { os << i.val(); return os; } ostream &operator<<(ostream &os, const vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i].val() << (i + 1 != (int)v.size() ? " " : ""); } return os; } ostream &operator<<(ostream &os, const Mint &i) { os << i.val(); return os; } ostream &operator<<(ostream &os, const vector &v) { for (int i = 0; i < (int)v.size(); i++) { os << v[i].val() << (i + 1 != (int)v.size() ? " " : ""); } return os; } #pragma endregion template //-------------- ----------------------------------------------------------- #pragma endregion watasou /* 切り上げは(a+b-1)/bでできる cin忘れに注意 制約を見よう ヒントが多分ある N<=100だとO(N^3)かもしれない N<=10だとO(2^N)かもO(!N)かもしれない N<=9*(10^18)だとO(√N)の場合通らないことがある わかんなくなったら問題文を読み直そう */ /* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体 update(i,x): i 番目の要素を x に更新。O(log(n)) query(a,b): [a,b) での最小の要素を取得。O(log(n)) */ const V DX={1,0,0,-1}; const V DY={0,1,-1,0}; using MINT=modint; ll op(ll a,ll b){ return max(a,b); } ll e(){ return (ll)0; } /*using S = ll; using F = ll; S op(S a, S b){ return a+b; } S e(){ return ll(1e9)+1; } S mapping(F f, S x){ return x+f; } F composition(F f, F g){ return f+g; } F id(){ return 0; }*/ int main(){ ll n,s,h; cin >> n >> s >> h; V x(n),y(n),z(n); rep(i,0,n){ cin >> x[i] >> y[i] >> z[i]; } V dp(n,0); V rui(n,0); rep(i,0,n){ if(y[i]-x[i]<=s){ if(i==0){ dp[i]=z[i]; rui[i]=z[i]; continue; } ll ok=i; ll ng=-1; print(i); while(ok-ng>1){ ll md=(ok+ng)/2; if(x[i]-h>=y[md]){ ng=md; } else{ ok=md; } print(md); } if(ng!=-1)chmax(dp[i],rui[ng]+z[i]); } chmax(dp[i],dp[i-1]); rui[i]=max(rui[i-1],dp[i]); } print(dp[n-1]); print(dp); print(rui); }