Submission #952373

#	Time	Username	Problem	Language	Result	Execution time	Memory
952373		vjudge306	Fuel Station (NOI20_fuelstation)	C++17	56 / 100	3064 ms	8812 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
//#define int long long
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
struct in {
int a; int b; int c;
};
bool ss(in a, in b) {
return a.a<b.a;
}
int main() {

    x_x
    int n,d; cin>>n>>d; in ar[n]; int mn=INT_MAX;
    for (auto&i:ar) cin>>i.a>>i.c>>i.b, mn=min(mn,i.b);
    sort(ar, ar+n,ss);
    if (n==1) {
        int x=d; int y=max(ar[0].a, d-ar[0].c); if (y>ar[0].b) y=d;
        cout<<min(x,y);
    }
    else if(mn==(1e9)) {
        ll f=0, x=0; ll s=f;
        for (int i=0; i<n&&ar[i].a<d; i++) {
            f-=(ar[i].a-x), x=ar[i].a;
            if(f<0)s+=(f*-1),f=0;
             f+=ar[i].c;
        }
        f-=(d-x); if(f<0) s+=(f*-1);
        cout<<s;
    }
    else if(d<=10000) {
       //int ans=d;
        for (int z=1; z<=d; z++) {
    ll f=z, x=0; bool ok=1;
        for (int i=0; i<n; i++) {
            f-=(ar[i].a-x), x=ar[i].a;
            if(f<0){ok=0; break;}
            if (z<=ar[i].b) f+=ar[i].c;
        }
        if ((d-x)>f)ok=0;
        if (ok) {cout<<z; break;}
        }
    }
    else if(n<=16) {
        int nm=(1<<n); ll ans=d;
        for (int z=1;z<nm;++z) {
           int mn=d;
            for (int i=0; i<n; i++)
                if (z&(1<<i))mn=min(mn,ar[i].b);

       ll f=0, x=0; ll s=0; bool ok=1;
        for (int i=0; i<n; i++) {
            f-=(ar[i].a-x), x=ar[i].a;
            if(f<0)s+=(f*-1),f=0;
            if (s>mn) {ok=0; break;}
            if(z&(1<<i))f+=ar[i].c;
        }
        if(ok)ans=min(ans,s);
        }
        cout<<ans;
        }
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 0 / 12
• Subtask 5: 19 / 19
• Subtask 6: 0 / 11
• Subtask 7: 0 / 21