Skip to content

Instantly share code, notes, and snippets.

@rvinamra

rvinamra/2.cpp

Last active December 9, 2019 19:33
Show Gist options
  • Save rvinamra/eaff89d9c24c6ef937218f3f0f9ec51e to your computer and use it in GitHub Desktop.
Save rvinamra/eaff89d9c24c6ef937218f3f0f9ec51e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
}
Raw
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;
}
Raw
4
prob 4
Raw
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;
}
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment