oj.uz

Submission #1013135

# Submission time Handle Problem Language Result Execution time Memory
1013135 2024-07-03T08:22:24 Z TrinhKhanhDung Fuel Station (NOI20_fuelstation) C++14
13 / 100
 96 ms 4948 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 5e5 + 10;

int N, D;
tuple<int, int, int> a[MAX];

bool OK(int x){
    ll cur = x;
    for(int i=1; i<=N+1; i++){
        cur -= (get<0>(a[i]) - get<0>(a[i - 1]));
        if(cur < 0) return false;
        if(cur <= get<2>(a[i])) cur += get<1>(a[i]);
    }
    return true;
}

void solve(){
    cin >> N >> D;
    for(int i=1; i<=N; i++){
        cin >> get<0>(a[i]) >> get<1>(a[i]) >> get<2>(a[i]);
    }
    sort(a + 1, a + N + 1);
    a[N + 1] = make_tuple(D, 0, 0);

    int l = 1, r = D;
    while(l < r){
        int m = (l + r) >> 1;
        if(OK(m)){
            r = m;
        }
        else{
            l = m + 1;
        }
    }
    cout << r << '\n';
}


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("split.inp", "r", stdin);
//    freopen("split.out", "w", stdout);

    int tt = 1;
//    cin >> tt;

    while(tt--){
        solve();
    }

    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 4948 KB Output is correct
2 Correct 84 ms 4468 KB Output is correct
3 Correct 86 ms 4476 KB Output is correct
4 Correct 80 ms 4688 KB Output is correct
5 Correct 78 ms 4696 KB Output is correct
6 Correct 85 ms 4692 KB Output is correct
7 Correct 74 ms 4472 KB Output is correct
8 Correct 71 ms 4716 KB Output is correct
9 Correct 88 ms 4692 KB Output is correct
10 Correct 73 ms 4744 KB Output is correct
11 Correct 79 ms 4716 KB Output is correct
12 Correct 73 ms 4700 KB Output is correct
13 Correct 73 ms 4688 KB Output is correct
14 Correct 82 ms 4692 KB Output is correct
15 Correct 80 ms 4688 KB Output is correct
16 Correct 96 ms 4692 KB Output is correct
17 Correct 85 ms 4696 KB Output is correct
18 Correct 84 ms 4724 KB Output is correct
19 Correct 84 ms 4692 KB Output is correct
20 Correct 87 ms 4472 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -