結果
| 問題 | No.2808 Concentration |
| ユーザー |
 watasou1543
|
| 提出日時 | 2024-07-01 21:01:01 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,158 bytes |
| コンパイル時間 | 4,748 ms |
| コンパイル使用メモリ | 189,508 KB |
| 実行使用メモリ | 9,600 KB |
| 最終ジャッジ日時 | 2024-07-08 17:51:27 |
| 合計ジャッジ時間 | 14,413 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,248 KB |
| testcase_02 | AC | 1 ms
5,248 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | AC | 1 ms
5,376 KB |
ソースコード
#pragma region watasou
/*
the pen is mightier than the sword.
-エドワード・ブルワー＝リットン-
KCLC44TH watasou1543.
*/
#include <bits/stdc++.h>
#include <atcoder/all>
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<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<ll>>;
using V = vector<ll>;
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 <typename T>
inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
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<<i)){
if(k&(1<<i)){
Ans+=p;
}
p*=p;
i++;
}
return Ans;
}
//DFS
map<ll,vector<ll>>Gra;
map<ll,bool>visited;// false=not visited, true=visited
void DFS(int pos){
visited[pos]=true;
for(int i : Gra[pos]){
if(visited[i]==false){
DFS(i);
}
}
}
vector<pair<long long, long long> > pri(long long N) {
vector<pair<long long, long long> > 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 vector<int>dx = {0, 1, 0, -1};
const vector<int>dy = {1, 0, -1, 0};
vector<vector<ll>> BFS(int H, int W, const vector<string> &G, pair<int, int> s) {
vector<vector<ll>> dist(H, vector<ll>(W, -1)); //すべての頂点を未訪問に初期化
queue<pair<int, int>> que;
//初期条件 (頂点sを初期頂点とする)
dist[s.first][s.second] = 0;
que.push(s); // sを探索済み頂点に
// BFS開始
while (!que.empty()) {
pair<int, int> 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;
}
vector<bool>sosuu(long long n){
vector<bool> 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<int> 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]<rank[ry]) swap(rx, ry); // ry 側の rank が小さくなるようにする
par[ry] = rx; // ry を rx の子とする
if (rank[rx]==rank[ry]) rank[rx]++; // rx 側の rank を調整する
siz[rx] += siz[ry]; // rx 側の siz を調整する
return true;
}
// x を含む根付き木のサイズを求める
int size(int x) {
return siz[root(x)];
}
};
//ワーシャルフロイド
Graph D;
void warshall_floyd(int n) {
for (int k = 0; k < n; k++){ // 経由する頂点
for (int i = 0; i < n; i++) { // 始点
for (int j = 0; j < n; j++) { // 終点
D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
}
}
}
}
ll string_mod(string s, ll mod){
ll rest = 0;
for(char c : s){
ll v = c-'0';
rest = (rest*10 + v) % mod;
}
return rest;
}
ll ro(ll a,ll b,Graph &G){
ll now=a;
rep(i,0,25){
if(b&(1LL<<i)){
now=G[now][i];
}
}
return now;
}
typedef pair<ll,int>P;
struct edge{int to;ll cost;ll num;};
map<ll,V>r;
vector<ll> dijkstra(vector<vector<edge>> graph, int n, int start, ll INF,ll now){
priority_queue<P,vector<P>,greater<P>>que;
vector<ll>dst(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]<d) continue;
for(int i=0;i<(int)graph[u].size();++i){
int v=graph[u][i].to;
ll cost=graph[u][i].cost;
ll num=graph[u][i].num;
ll l=r[num][0],d=r[num][1],k=r[num][2];
ll ok=k,ng=-1;
while(ok-ng>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<ll> topological_sort(vector<vector<ll>> &G, vector<ll> &indegree, int V) {
// トポロジカルソートを記録する配列
vector<ll> sorted_vertices;
// 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する
queue<int> 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 <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
os << "(" << p.first << "," << p.second << ")";
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p)
{
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
for (int i = 0; i < (int)v.size(); i++)
{
os << v[i] << (i + 1 != (int)v.size() ? " " : "");
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &v)
{
for (int i = 0; i < (int)v.size(); i++)
{
os << v[i] << endl;
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<vector<T>>> &v)
{
for (int i = 0; i < (int)v.size(); i++)
{
os << "i = " << i << endl;
os << v[i];
}
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
for (T &in : v)
is >> in;
return is;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, const map<T, S> &mp)
{
for (auto &[key, val] : mp)
{
os << key << ":" << val << " ";
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const set<T> &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 <typename T>
ostream &operator<<(ostream &os, const multiset<T> &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 <typename T>
ostream &operator<<(ostream &os, queue<T> q)
{
while (q.size())
{
os << q.front() << " ";
q.pop();
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, deque<T> q)
{
while (q.size())
{
os << q.front() << " ";
q.pop_front();
}
return os;
}
template <typename T>
ostream &operator<<(ostream &os, stack<T> st)
{
while (st.size())
{
os << st.top() << " ";
st.pop();
}
return os;
}
template <class T, class Container, class Compare>
ostream &operator<<(ostream &os, priority_queue<T, Container, Compare> 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<mint> &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<Mint> &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+1,0);
rep(i,0,n){
if(y[i]-x[i]<=s){
if(i==0){
dp[i+1]=z[i];
continue;
}
ll ok=i;
ll ng=-1;
while(ok-ng>1){
ll md=(ok+ng)/2;
if(x[i]-h>=y[md]){
ng=md;
}
else{
ok=md;
}
}
chmax(dp[i+1],dp[ng+1]+z[i]);
}
if(i!=0){
chmax(dp[i+1],dp[i]);
}
}
print(dp[n]);
}