比赛 EYOI与SBOI开学欢乐赛4th 评测结果 AWWAWAAAWA
题目名称 烟雾与火焰 最终得分 60
用户昵称 yrtiop 运行时间 0.285 s
代码语言 C++ 内存使用 1.18 MiB
提交时间 2022-09-12 21:03:54
显示代码纯文本
#include <bits/stdc++.h>
typedef long long ll;

ll gcd(ll x,ll y) {
    return y ? gcd(y , x % y) : x;
}

ll n,x,y,z;
std::unordered_map<ll,bool> s;

int main() {
	freopen("burnTokyo.in","r",stdin);
	freopen("burnTokyo.out","w",stdout);
    scanf("%lld %lld %lld %lld",&n,&x,&y,&z);
    if(x > y)std::swap(x , y);
    if(x > z)std::swap(x , z);
    if(y > z)std::swap(y , z);

    ll t = x * y - x - y;
    ll ans = 1;
    -- n;
    
	if(t <= 0) {
		printf("%lld\n",n + 1);
		return 0;
	}
	
	if(n > t) {
		ans += n - t;
		n = t;
	}

    std::priority_queue<ll> q;
    q.emplace(0);
    while(!q.empty()) {
        t = q.top();
        q.pop();
        if(t > n)break ;
        if(t + x <= n&&!s[t + x]) {
            s[t + x] = true;
            q.emplace(t + x);
            ++ ans;
        }
        if(t + y <= n&&!s[t + y]) {
            s[t + y] = true;
            q.emplace(t + y);
            ++ ans;
        }
        if(t + z <= n&&!s[t + z]) {
            s[t + z] = true;
            q.emplace(t + z);
            ++ ans;
        }
    }

    printf("%lld",ans);
    return 0;
}