Greater Integer, Better LCM

#include<bits/stdc++.h>
#define ll long long
#define N 200
#define FOR(i,n,m) for(int i=n;i<=m;i++)
#define For(i,n,m) for(int i=n;i>=m;i--)
using namespace std;
int n;
int p[N],q[N];
__int128 f[N][N],s[N];
__int128 a,b,ans;
inline void read(__int128 &X)
{
    X = 0;
    int w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    if (w) X = -X;
}
inline void print(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
void dfs(int k,__int128 A,__int128 B)
{
    if((A-a)+(B-b)>ans)return;
    if(A*s[k]<a||B*s[k]<b)return;
    if(k>n)
    {
        if(A<a||B<b)return;
        ans=min(ans,A-a+B-b);
        return;
    }
    FOR(i,0,q[k]-1)
    {
        dfs(k+1,A*f[k][q[k]],B*f[k][i]);
        dfs(k+1,A*f[k][i],B*f[k][q[k]]);
    }
    dfs(k+1,A*f[k][q[k]],B*f[k][q[k]]);
}
int main()
{
    cin>>n;
    FOR(i,1,n)
        std::cin>>p[i]>>q[i];
    read(a);read(b);
    FOR(i,1,n)
    {
        f[i][0]=1;
        FOR(j,1,q[i])
            f[i][j]=f[i][j-1]*p[i];
    }
    s[n+1]=1;
    For(i,n,1)
        s[i]=s[i+1]*f[i][q[i]];
    ans=(__int128)1e30;
    dfs(1,1,1);
    print(ans);
    return 0;
}

Jewels

#include<bits/stdc++.h>
using namespace std;
const int N = 610, M = 1000010;
int n, m;
long long value[510][510];
int c[510];
int c1[510];
long long la[510], lb[510];
long long update[510], min1;
int pre[510];
void bfs(int x) {
    int last = 0, ff = 0, now;
    memset(pre, 0, sizeof(pre));
    for (int i = 0; i <= n; i++)update[i] = 1e18;
    c1[last] = x;
    while (1) {
        c[last] = 1;
        min1 = 1e18;
        now = c1[last];
        for (int i = 1; i <= n; i++) {
            if (!c[i]) {
                if (update[i] > la[now] + lb[i] - value[now][i]) {
                    update[i] = la[now] + lb[i] - value[now][i];
                    pre[i] = last;
                }
                if (update[i] < min1)min1 = update[i], ff = i;
            }
        }
        for (int i = 0; i <= n; i++) {
            if (c[i])la[c1[i]] -= min1, lb[i] += min1;
            else update[i] -= min1;
        }
        last = ff;
        if (c1[last] == -1)break;
    }
    while (last)c1[last] = c1[pre[last]], last = pre[last];
}
void km() {
    memset(c1, -1, sizeof(c1));
    for (int i = 1; i <= n; i++) {
        memset(c, 0, sizeof(c));
        bfs(i);
    }
}
long long x[310], y[310], z[310], v[310];
signed main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld%lld%lld", &x[i], &y[i], &z[i], &v[i]);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            value[i][j] = -1e18;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            long long k = x[i] * x[i] + y[i] * y[i] + (z[i] + v[i] * (j - 1)) * (z[i] + v[i] * (j - 1));
            value[i][j] = -k;
        }
    }
    km();
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (c1[i] != -1)ans += value[c1[i]][i];
    }
    printf("%lld\n", -ans);
    return 0;
}