MELE2 - ELEVATOR II

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<queue>
#define MAX   100100
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
ll a,b,c,n;
ll d[MAX];
ll res;
void swap(ll &a,ll &b) {
    ll sw;
    sw=a;a=b;b=sw;
}
void init(void) {
    scanf("%lld",&n);
    scanf("%lld",&a);
    scanf("%lld",&b);
    scanf("%lld",&c);
    if (a<=b && a<=c) swap(a,c);
    else if (b<=c && b<=a) swap(b,c);
    ll i;
    for (i=1;i<=c;i=i+1) d[i]=n+1;
}
void dijkstra(void) {
    priority_queue<ii,vector<ii>,greater<ii> > q;
    while (!q.empty()) q.pop();
    d[0]=0;
    q.push(ii(0,0));
    ll px,py;
    ii p;
    while (!q.empty()) {
        p=q.top();q.pop();
        px=p.first;py=p.second;
        if (d[(py+a)%c]>px+a) {
            d[(py+a)%c]=px+a;
            q.push(ii(px+a,(py+a)%c));
        }
        if (d[(py+b)%c]>px+b) {
            d[(py+b)%c]=px+b;
            q.push(ii(px+b,(py+b)%c));
        }
    }
}
ll f(ll x,ll mod) {
    if (x<mod) return (0);
    return ((x-mod)/c+1);
}
void process(void) {
    dijkstra();
    res=0;
    ll i;
    //for (i=0;i<c;i=i+1) printf("%lld ",d[i]); printf("\n");
    for (i=0;i<c;i=i+1)
        if (d[i]<n) res=res+f(n-1,i)-f(d[i]-1,i);
    printf("%lld ",res);
}
int main(void) {
    init();
    process();
    return 0;
}

Download