GCD of Subsets

statements

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,k,m;
        cin>>n>>k>>m;
        int cnt=n/k-1;
        int ans=0;
        if(n<=m) ans=n;
        else if(n-cnt-1>=m) ans=1+cnt/2+m;
        else ans=1+m+(cnt-(m-(n-cnt-1)))/2;
        cout<<ans<<'\n';
    }
    return 0;
}

A - A Lot of Paintings

statements

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e7,N=2e5+10;
int n,b[N];
void print(){
    for(int i=1;i<=n;i++) cout<<b[i]<<' ';
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        int sum=0;
        for(int i=1;i<=n;i++){
            cin>>b[i];
            b[i]=b[i]*inf;
            sum+=b[i];
        }
        int need;
        if(sum==100*inf) need=0;
        else if(sum<100*inf){
            need=100*inf-sum;
            for(int i=1;i<=n;i++){
                if(b[i]<100*inf){
                    b[i]+=min(need,inf/2-1);
                    need-=min(need,inf/2-1);
                }
            }
        }
        else{
            need=sum-100*inf;
            for(int i=1;i<=n;i++){
                if(b[i]){
                    b[i]-=min(need,inf/2);
                    need-=min(need,inf/2);
                }
            }
        }
        if(need) cout<<"No\n";
        else{
            cout<<"Yes\n";
            print();
        }
    }
    return 0;
}

B - Blood Memories

statements

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
const int maxn=110,inf=-1e9;
int a[10],c[10];
struct Matrix {
    ll M[maxn][maxn];
    ll r, c;
    Matrix(ll row, ll col):r(row),c(col) {
        for(int i=0; i<row; i++)
            for(int j=0; j<col; j++)
                M[i][j] = inf;
    }
    void reset() {
        for(int i=0; i<r; i++) M[i][i] = 0;
    }
    Matrix operator*(const Matrix &B) const {
        Matrix Ans(r, B.c);
        for(int i=0; i<r; i++)
            for(int j=0; j<B.c; j++)
                for(int k=0; k<c; k++)
                    Ans.M[i][j] = max(Ans.M[i][j] , M[i][k] + B.M[k][j]);
        return Ans;
    }
    
    Matrix operator+(const Matrix &B) const {
        Matrix Ans(r, c);
        for(int i=0; i<r; i++)
            for(int j=0; j<c; j++)
                Ans.M[i][j] = (M[i][j] + B.M[i][j]);
        return Ans;
    }
    
    bool operator!=(const Matrix &B) const {
        for(int i=0; i<r; i++)
            for(int j=0; j<c; j++)
                if(M[i][j] != B.M[i][j])
                    return true;
        return false;
    }
};
Matrix qpow(Matrix T, ll p) {
    Matrix Ans(T.r,T.c);
    Ans.reset();
    while(p) {
        if(p & 1) Ans = Ans * T;
        T = T * T;
        p >>= 1;
    }
    return Ans;
}
int attack[100],cost[100];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m,k,R;
        cin>>n>>m>>k>>R;
        for(int i=0;i<n;i++) cin>>a[i]>>c[i];
        Matrix T((1<<n),(1<<n));
        for(int s=0;s<(1<<n);s++){
            int tmp_attack=0,tmp_cost=0;
            for(int i=0;i<n;i++){
                if((s>>i)&1){
                    tmp_attack+=a[i];
                    tmp_cost+=c[i];
                }
            }
            attack[s]=tmp_attack;
            cost[s]=tmp_cost;
        }
        for(int s=0;s<(1<<n);s++){
            if(cost[s]>m) continue ;
            for(int t=0;t<(1<<n);t++){
                if(cost[s]+__builtin_popcount(s&t)*k>m) continue ;
                T.M[s][t]=attack[s];
            }
        }
        T=qpow(T,R);
        Matrix dp((1<<n),1);
        for(int s=0;s<(1<<n);s++) dp.M[s][0]=0;
        dp=T*dp;
        int ans=0;
        for(int s=0;s<(1<<n);s++)
            ans=max(ans,dp.M[s][0]);
        cout<<ans<<'\n';
    }
    return 0;
}