MELE2 - ELEVATOR II

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#define long long long
#define li pair<long, int>
#define X first
#define Y second
const long oo = 1000000000000000001ll;
const int N = 100005;
using namespace std;
long res, n;
long k[4];
long d[N];

void Dijkstra() {
    priority_queue<li, vector<li>, greater<li> > Q;
    int u, v; long du;
    Q.push(li(0, 0));
    for(int i = 1; i < k[1]; i++) d[i] = oo;
    while (Q.size()) {
        u = Q.top().Y; du = Q.top().X; Q.pop();
        if (du != d[u]) continue;
        for(int i = 2; i <= 3; i++) {
            v = (u + k[i]) % k[1];
            if (d[v] > d[u] + k[i]) {
                d[v] = d[u] + k[i];
                Q.push(li(d[v], v));
            }
        }
    }
}

int main()
{
    cin >> n; cin >> k[1] >> k[2] >> k[3]; sort(k + 1, k + 4);
    Dijkstra();
    n--;
    for(int i = 0; i < k[1]; i++) {
        if (d[i] > n) continue;
        res += (n - i) / k[1] - (d[i] - i) / k[1] + 1;
    }
    cout << res;
    return 0;
}

Download