Skip to content

Instantly share code, notes, and snippets.

View Shafaet's full-sized avatar

Shafaet Ashraf Shafaet

View GitHub Profile
/*
* Shafaetsplanet.com
*/
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAX_N 100
#define MAX_W 1000
int n;
int dp[MAX_N+1][MAX_W+1];
int weight[MAX_N+1];
int cost[MAX_N+1];
int CAP;
int func(int i,int w)
{
if(i==n+1) return 0; //সব কিছু নেয়া হয়ে গেছে
i64 dp[70][70];
i64 nCr(int n,int r)
{
if(r==1) return n;
if(n==r) return 1;
if(dp[n][r]!=-1) return dp[n][r]; //ভ্যালু টেবিলে থাকলে নতুন করে হিসাব করা দরকার নেই,ভ্যালুটা রিটার্ণ করে দাও
else{
dp[n][r]=nCr(n-1,r)+nCr(n-1,r-1); //ভ্যালু টেবিলে সেভ করে রাখো
return dp[n][r];
}
vector<int>G[100];
void bfs(int n,int src)
{
queue<int>Q;
Q.push(src);
int visited[100]={0},level[100];
int parent[100];
visited[src]=1;
level[src]=0;
while(!Q.empty())
@Shafaet
Shafaet / 2d bfs
Last active August 29, 2015 13:56
#define pii pair<int,int>
int fx[]={1,-1,0,0}; //ডিরেকশন অ্যারে
int fy[]={0,0,1,-1};
int cell[100][100]; //cell[x][y] যদি -১ হয় তাহলে সেলটা ব্লক
int d[100][100],vis[100][100];
int row,col;
void bfs(int sx,int sy)
{
mem(vis,0);
vis[sx][sy]=1;
@Shafaet
Shafaet / LCA
Created March 25, 2014 08:43
LCA using Sparse Table
//LCA using sparse table
//Complexity: O(NlgN,lgN)
#define mx 100002
int L[mx]; //লেভেল
int P[mx][22]; //স্পার্স টেবিল
int T[mx]; //প্যারেন্ট
vector<int>g[mx];
void dfs(int from,int u,int dep)
{
T[u]=from;
@Shafaet
Shafaet / LCS
Created April 22, 2014 12:39
LCS
#define MAXC 1000
char A[MAXC],B[MAXC];
int lenA,lenB;
int dp[MAXC][MAXC];
bool visited[MAXC][MAXC];
int calcLCS(int i,int j)
{
if(A[i]=='\0' or B[j]=='\0') return 0;
if(visited[i][j])return dp[i][j];
@Shafaet
Shafaet / gist:0d7ece26ce90e9d2b2d4
Created December 12, 2015 15:41
Custom checker
1. Input to custom checker will be a directory. There are some unwanted white spaces (including line feeds) at the beginning and/or end. Make sure that you trim them off.
2. In the given directory, there exists a `request.json` file [sample file is attached]. One of the fields will be `expected_outputs` which contains a array of strings. There will be `n` elements in this array, representing the expected output of `n` test cases.
3. There will be `n` input files in the same directory. Suppose there are `n = 20` test cases, then input files will be named as `input00000.in`, `input00001.in`, `input00002.in`,..., `input00009.in`, `input00010.in`, `input00011.in` ,..., `input00019.in`.
4. Similarly, there will be `n` output files, named same as above. Eg. `ouptput00000.in`, `ouptput00001.in`, `ouptput00002.in`,..., `ouptput00009.in`, `ouptput00010.in`, `ouptput00011.in` ,..., `ouptput00019.in`. They are placed in the same directory.
5. You have to read respective input, output (and expected output, if require
1. Input to custom checker will be a directory. There are some unwanted white spaces (including line feeds) at the beginning and/or end. Make sure that you trim them off.
2. In the given directory, there exists a `request.json` file [sample file is attached]. One of the fields will be `expected_outputs` which contains a array of strings. There will be `n` elements in this array, representing the expected output of `n` test cases.
3. There will be `n` input files in the same directory. Suppose there are `n = 20` test cases, then input files will be named as `input00000.in`, `input00001.in`, `input00002.in`,..., `input00009.in`, `input00010.in`, `input00011.in` ,..., `input00019.in`.
4. Similarly, there will be `n` output files, named same as above. Eg. `ouptput00000.in`, `ouptput00001.in`, `ouptput00002.in`,..., `ouptput00009.in`, `ouptput00010.in`, `ouptput00011.in` ,..., `ouptput00019.in`. They are placed in the same directory.
5. You have to read respective input, output (and expected output, if require
//Programming Contest Template
//Shafaet Ashraf
#include <bits/stdc++.h>
#define stream istringstream
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define repv(i,n) for(int i=n-1; i>=0; i--)
#define repl(i,n) for(int i=1; i<=(int)n; i++)
#define replv(i,n) for(int i=n; i>=1; i--)
#define foreach(i,n) for(__typeof((n).begin())i =(n).begin();i!=(n).end();i++)