2.cpp

#include <bits/stdc++.h>
using namespace std;
 
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre(){


}

ll a[1<<21], f[60];
ll solve(long N, long M, vector<long> W, vector<long> V){
    ll n=N, m=M;
    f[0]=0;f[1]=1;f[2]=2;
    repA(i,3,52)f[i]=f[i-1]+f[i-2];
    
    ll ans=-1;
    n+=1;

    rep(i, ll(1<<n)){
        ll sum=0, val=0;
        rep(j,n-1)if(i&(1<<j)){
            sum+=W[j];
            val+=V[j];
        }
        if(sum==0)continue;

        int k=m/sum;
        int in = lower_bound(f,f+51, k)-f;
        if(f[in]!=k)in--;

        ans=max(ans,f[in]*val);
    }
    return ans;
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
    int t;cin>>t;
    int n,m;cin>>n>>m;
    vector<long> w,v;
    w.resize(n+1), v.resize(n+1);
    rep(i,n)cin>>w[i];
    rep(i,n)cin>>v[i];
    cout<<solve(n,m,w,v);
	return 0;
}
 

3.cpp

#include <bits/stdc++.h>
using namespace std;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre(){


}

const int MAXSIZE=100001;

int d[100001][5];

int solve(int N, int P[MAXSIZE], int Q[MAXSIZE], int R[MAXSIZE], int S[MAXSIZE]){
    int n=N;
    rep(i,n+1)rep(k,5)d[i][k]=INT_MAX;
    d[0][1]=0;
    d[0][2]=0;
    d[0][3]=0;
    d[0][4]=0;
   // rep(i,n+1){
   //     repA(k,1,4){
   //         cout << d[i][k] << " ";
   //     }
   //     cout << endl;
   // }
   // cout << "--------------------\n";

    rep(i,n){
        repA(k,1,4){
            if(k!=1)d[i+1][k]=min(d[i+1][k], d[i][1]+P[i]);
            if(k!=2)d[i+1][k]=min(d[i+1][k], d[i][2]+Q[i]);
            if(k!=3)d[i+1][k]=min(d[i+1][k], d[i][3]+R[i]);
            if(k!=4)d[i+1][k]=min(d[i+1][k], d[i][4]+S[i]);
        }
    }
    int ans=min(d[n][1], d[n][2]);
    ans=min(ans, d[n][3]);
    ans=min(ans, d[n][4]);
    return ans;
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();

    int t;//cin>>t;
    int p[MAXSIZE], q[MAXSIZE], r[MAXSIZE], s[MAXSIZE];
    rep(i,10){
    int n;n=100000;cin>>n;
    rep(i,n){
        p[i]=1000;
        q[i]=1000;
        r[i]=1000;
        s[i]=1000;
        cin>>p[i]>>q[i]>>r[i]>>s[i];
    }
    cout<<solve(n,p,q,r,s)<<endl;
    }


	return 0;
}

4

prob 4

4.cpp

#include <bits/stdc++.h>
using namespace std;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre(){


}

const int MAXSIZE=100001;

ll vis[100011]; vector<ll> d;
vector<pii> g[100011];


int solve(int N, int P[MAXSIZE], int Q[MAXSIZE], int R[MAXSIZE], int S[MAXSIZE]){
    int n=N;
    d.resize(4*n+10);
    rep(i,4*n+10)d[i]=1e12;
    g[0].pb(mp(P[0],1));
    g[0].pb(mp(Q[0],2));
    g[0].pb(mp(R[0],3));
    g[0].pb(mp(S[0],4));
    int cnt=1;
    repA(i,0,n-2){
        repA(b,1,4){
            if(b!=1)g[b+4*i].pb(mp(P[i+1], 1+4*i+4));
            if(b!=2)g[b+4*i].pb(mp(Q[i+1], 2+4*i+4));
            if(b!=3)g[b+4*i].pb(mp(R[i+1], 3+4*i+4));
            if(b!=4)g[b+4*i].pb(mp(S[i+1], 4+4*i+4));
        }
    }
    repA(b,1,4){
        if(b!=1)g[1+4*(n-1)].pb(mp(0, 4*n+1));
        if(b!=2)g[2+4*(n-1)].pb(mp(0, 4*n+1));
        if(b!=3)g[3+4*(n-1)].pb(mp(0, 4*n+1));
        if(b!=4)g[4+4*(n-1)].pb(mp(0, 4*n+1));
    }
    //rep(i,4*n){
    //    cout << i << endl;
    //    trav(it, g[i]){
    //        cout << "(" << it.fst << ", " << it.snd << ")" << " ";
    //    }
    //    cout << endl;
    //}

    priority_queue<pii> pq;
    pq.push(mp(0,0));
    d[0]=0;

    while(!pq.empty()){
        pii c = pq.top();pq.pop();
        int dist = c.fst;
        int u = c.snd;
        trav(it, g[u]){
            int v=it.snd;int w=it.fst;
            if(d[v] > dist+w){
                pq.push(mp(dist+w,v));
                d[v] = dist+w;
            }
        }
    }
    return d[4*n+1];
}

int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();

    int t;cin>>t;
    int p[MAXSIZE], q[MAXSIZE], r[MAXSIZE], s[MAXSIZE];
    int n;cin>>n;
    rep(i,n){
        cin>>p[i]>>q[i]>>r[i]>>s[i];
    }
    cout<<solve(n,p,q,r,s);


	return 0;
}

5.cpp

int lcs(int x, int y) {
    int ans = 0;
    int mask = 1;
    for(int i=0; i<23; i++) {
        int a = mask & x;
        int b = mask & y;
        // cout << "i: " << i << endl;
        // cout << "a: " << a << endl;
        // cout << "b: " << b << endl;
        if((a^b) == 0){
            mask = mask << 1;
            ans += 1;
        } else {
            break;
        }
    }
    return ans;
}


void update(int x, int y){
    A[x] = y;
}

void findval(int l, int r, int x) {
    int sum = 0;
    for(int i=l; i<=r; i++){
        sum += lcs(A[i], x);
    }
    cout << sum << endl;
}