結果

問題 No.2808 Concentration
ユーザー watasou1543watasou1543
提出日時 2024-06-26 19:43:44
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 13,296 bytes
コンパイル時間 9,311 ms
コンパイル使用メモリ 189,604 KB
実行使用メモリ 16,000 KB
最終ジャッジ日時 2024-07-08 17:50:49
合計ジャッジ時間 18,343 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 WA -
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
testcase_47 -- -
testcase_48 -- -
testcase_49 -- -
testcase_50 -- -
testcase_51 -- -
testcase_52 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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,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);
}
0