oj.uz

Submission #359966

# Submission time Handle Problem Language Result Execution time Memory
359966 2021-01-27T11:32:13 Z teehandsome Fuel Station (NOI20_fuelstation) C++11
13 / 100
 176 ms 8960 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e14+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

int n,d;
vector<ll> B;
struct dt {
    int x,a,b;
    bool operator<(const dt &r) {
        return x<r.x;
    };
};
vector<dt> shop;
ll ans = INF;

bool ok(ll f) {
    ll sum=0;
    ll f_rem=INF;
    for(int i=0;i<n+1;i++) {
        if(shop[i].b<f) continue;
        f_rem=min(f_rem,f+sum-shop[i].x);
        sum+=shop[i].a;
    }
    if(f_rem>=0) {
        ans=min(ans,f-f_rem);
        //cout<<f-f_rem<<endl; return true;
    }
    return false;
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>d;
    for(int i=0;i<n;i++) {
        int x,a,b; cin>>x>>a>>b;
        shop.push_back({x,a,b});
        B.push_back(b);
    }
    sort(all(shop)); shop.push_back({d,0,d});
    sort(all(B)); B.erase(unique(all(B)),end(B));
    for(auto e:B) {
        if(ok(e)) {
//            return 0;
        }
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 0 ms 364 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 148 ms 8712 KB Output is correct
2 Correct 166 ms 8812 KB Output is correct
3 Correct 163 ms 8812 KB Output is correct
4 Correct 145 ms 8812 KB Output is correct
5 Correct 141 ms 8812 KB Output is correct
6 Correct 176 ms 8812 KB Output is correct
7 Correct 148 ms 8812 KB Output is correct
8 Correct 141 ms 8812 KB Output is correct
9 Correct 151 ms 8940 KB Output is correct
10 Correct 141 ms 8812 KB Output is correct
11 Correct 149 ms 8812 KB Output is correct
12 Correct 144 ms 8780 KB Output is correct
13 Correct 149 ms 8760 KB Output is correct
14 Correct 148 ms 8812 KB Output is correct
15 Correct 142 ms 8812 KB Output is correct
16 Correct 152 ms 8812 KB Output is correct
17 Correct 141 ms 8812 KB Output is correct
18 Correct 169 ms 8960 KB Output is correct
19 Correct 151 ms 8812 KB Output is correct
20 Correct 149 ms 8812 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 21.0

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