akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }

struct Tmp
{
public:

  int mH, mW;

  vector<vector<char>> table;
  vector<vector<int>> memo;
  int res;

  Tmp(int H, int W);
  void query(int h, int w);
  void reset();
  void rec(int h, int w, int x);
};

Tmp::Tmp(int H, int W)
  : mH(H)
  , mW(W)
  , table(H, vector<char>(W))
  , memo(H, vector<int>(W, -1))
  , res(-1)
{}

void Tmp::query(int h, int w)
{
  rec(h, w, 0);
  int ret{};
  for (auto& r : memo) {
    for (auto& c : r) {
      chmax(ret, c);
    }
  }
  chmax(res, ret);
  reset();
}

void Tmp::rec(int h, int w, int x)
{
  if (h < 0 || w < 0 || h >= mH || w >= mW) {
    return;
  }
  if (table[h][w] == '#') {
    return;
  }
  if (memo[h][w] == -1) {
    memo[h][w] = x;
  }
  else {
    if (!chmin(memo[h][w], x)) {
      return;
    }
  }
  auto r = memo[h][w];

  rec(h-1, w, r+1);
  rec(h+1, w, r+1);
  rec(h, w-1, r+1);
  rec(h, w+1, r+1);
}

void Tmp::reset()
{
  boost::for_each(memo, [](auto& r){
    boost::fill(r, -1);
  });
}


void solve(void)
{
  int H, W; cin >> H >> W;
  Tmp t(H, W);
  for (auto& row : t.table) {
    for (auto& cell : row) {
      cin >> cell;
    }
  }
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      t.query(i, j);
    }
  }
  auto res = t.res;
  auto ans = res;
  cout << ans << CRLF;
  return;
}

int main(void)
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  solve();

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>

using namespace std;

int N, M, sz, edges, frq[3], ap[100009];
long long ans = 0;
bool ok = 1;
vector < pair < int, char > > v[100009];

void dfs (int nod, int val)
{
    if (ap[nod] != -1)
    {
        if (ap[nod] != val)
            ok = 0;
        return ;
    }
    ap[nod] = val, frq[val] ++, sz ++;
    for (auto it = v[nod].begin (); it != v[nod].end (); it ++)
        dfs (it->first, (val + it->second) % 3), edges ++;
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d %d", &N, &M);
for (int i=1; i<=M; i++)
{
    int x, y;
    scanf ("%d %d", &x, &y);
    v[x].push_back ({y, 1}), v[y].push_back ({x, 2});
}
for (int i=1; i<=N; i++)
    ap[i] = -1;
for (int i=1; i<=N; i++)
    if (ap[i] == -1)
    {
        ok = 1, frq[0] = frq[1] = frq[2] = sz = 0, edges = 0, dfs (i, 0), edges /= 2;
        if (!ok) ans += 1LL * sz * sz;
        else
        {
            if (frq[0] == 0 || frq[1] == 0 || frq[2] == 0) ans += edges;
            else ans += 1LL * frq[0] * frq[1] + 1LL * frq[1] * frq[2] + 1LL * frq[2] * frq[0];
        }
    }
printf ("%lld\n", ans);
return 0;
}


Measured memory_bytes: 10752
#include <cstdio>
#include <cstdlib>

int main() {
  int a, b, c, d;
  scanf("%d %d %d %d", &a, &b, &c, &d);

  if (abs(a-c) <= d) {
    puts("Yes");
  } else if (abs(a-b) <= d && abs(b-c) <= d) {
    puts("Yes");
  } else {
    puts("No");
  }
}

Measured memory_bytes: 128
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {
    int h,a;
    string ans;
    cin>>h>>a;
    int k;
    int sum =0;
    while(a--){
        cin>>k;
        sum +=k;
    }
    if(h<=sum)
        ans ="Yes";
    else{
    ans = "No";
    }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
const int mod = 1E9 + 7;
const int inf = 1 << 29;

int main() {
  int n, m;
  cin >> n >> m;
  int a, b;
  vector<vector<int>> map(n, vector<int>());
  vector<int> ans(n, -1);
  deque<int> que;
  rep(i, m) {
    cin >> a >> b;
    map[a - 1].push_back(b - 1);
    map[b - 1].push_back(a - 1);
  };
  int r;
  int num_path;
  //   rep(i, n) {
  //     cout << "room " << i << ": ";
  //     rep(j, map[i].size()) { cout << map[i][j] << " "; }
  //     cout << endl;
  //   }
  que.push_back(0);
  while (!que.empty()) {
    r = que.front();
    num_path = map[r].size();
    if (num_path == 0) {
      cout << "No" << endl;
      return 0;
    }
    rep(i, num_path) {
      if (ans[map[r][i]] != -1) continue;
      que.push_back(map[r][i]);
      ans[map[r][i]] = r;
    }
    que.pop_front();
  }
  cout << "Yes" << endl;
  for (int i = 1; i < n; ++i) {
    cout << ans[i] + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 10228
#include<bits/stdc++.h>

using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    if((a==1 && b==2) || (a==2 && b==1)) cout << 3 << endl;
    else if((a==1 && b==3) || (a==3 && b==1)) cout << 2 << endl;
    else if((a==2 && b==3) || (a==3 && b==2)) cout << 1 << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> *gr;
ll *dp;ll *sz;
ll *ans;
const ll mx=200002;
ll fact[mx],inv[mx];
ll m=1e9+7;ll n;
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
void init()
{
    fact[0]=1;
    inv[0]=1;
    for(int i=1;i<mx;i++)
    {
        fact[i]=(fact[i-1]%m * i%m)%m;
        inv[i]=binpow(fact[i],m-2,m);
    }
}
void dfs(ll src,ll par)
{
    for(int i=0;i<gr[src].size();i++)
    {
        ll j=gr[src][i];
        if(j!=par){
            dfs(j,src);
        sz[src]+=sz[j];
        }
    }
}
void dfs1(ll src,ll par)
{
    for(int i=0;i<gr[src].size();i++)
    {
        ll j=gr[src][i];
        if(j!=par)
        {
            dfs1(j,src);
            ll p=dp[j];
            ll q=inv[sz[j]];
            p=(p%m *q%m)%m;
            dp[src]=(dp[src]%m * p%m)%m;
        }
    }
}
void dfs2(ll src,ll par) /// re-rooting step (very carefully done)
{
    ans[src]=dp[src];
    for(int i=0;i<gr[src].size();i++)
    {
        ll j=gr[src][i];
        if(j!=par)
        {
            ll a=dp[src];ll b=dp[j];
            dp[src]=(dp[src]%m * inv[n-1]%m)%m;
            dp[src]=(dp[src]%m * fact[n-sz[j]-1]%m)%m;
            dp[src]=(dp[src]%m * fact[sz[j]]%m)%m;
            dp[src]=(dp[src]%m * binpow(dp[j],m-2,m)%m)%m;
            dp[j]=(dp[j]%m * dp[src]%m)%m;
            dp[j]=(dp[j]%m * fact[n-1]%m)%m;
            dp[j]=(dp[j]%m * inv[sz[j]-1]%m)%m;
            dp[j]=(dp[j]%m * inv[n-sz[j]]%m)%m;
            dfs2(j,src);
            dp[src]=a;dp[j]=b;
        }
    }
}
int main() {
    ll t;
    t=1;
    init();
    while(t--) /// get diameter nothing else
    {
        cin>>n;
        gr=new vector<ll> [n];
        sz=new ll[n];
        dp=new ll[n];ans=new ll[n];
        for(int i=0;i<n-1;i++)
        {
            ll x,y;cin>>x>>y;
            x--;y--;
            gr[x].push_back(y);
            gr[y].push_back(x);
        }
       for(int i=0;i<n;i++)
            {sz[i]=1;}
       dfs(0,-1);
       for(int i=0;i<n;i++)
        dp[i]=fact[sz[i]-1];
       dfs1(0,-1);
       dfs2(0,-1);
        for(int i=0;i<n;i++)
        cout<<ans[i]<<"\n";
    }
}


Measured memory_bytes: 22512
#include<bits/stdc++.h>
#define range(i,a,b) for(long long i = (a); i < (b); i++)
#define rep(i,b) for(long long i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;
 
template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}
template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

int main(){
	int n, m;
	while(cin >> n >> m, n){
		map<int,int> a;
		rep(i,n){
			int d, v;
			cin >> d >> v;
			a[d] = max(a[d], v);
		}

		int sum = 0;
		rep(i,m){
			sum += a[i + 1];
		}
		cout << sum << endl;
	}
}



Measured memory_bytes: 3128
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <tuple>
#include <set>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
#define out(S) cout<<(S)<<endl;
#define REP(i,b) for(size_t i=0;i<(b);i++)
#define rREP(i,b) for(int i=(b)-1;i>=0;i--)
#define FOR(i,a,b) for(size_t i=(a);i<(b);i++)
#define rFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define Foreach(item,collection) for(auto item:collection)
#define mod(i) ((i) % (ll)(1e9 + 7))
ll modpow(ll i, ll j) { ll tmp = 1; while (j) { if (j % 2)tmp = mod(tmp*i); i = mod(i*i); j /= 2; }return tmp; }
#define divmod(a,b) (mod(a * modpow((ll)b,(ll)(1e9 + 5))))
#define Yes out("Yes")
#define No out("No")
#define NO out("NO")
#define YES out("YES")
#define INF 1e10;
#define ShowAll(collection) for(auto i:collection){out(i);}
#define IfOut(condition,text) if((condition)){out(text);return 0;}
#define IfeOut(condition,itext,etext) if(condition){out(itext);return 0;}else{out(etext);return 0;}
#define Select(collection,condition,result) Foreach(i,collection){result+=condition;}
#define GetAuto(_N,vect) {cin>>_N;vect.resize(_N);REP(i,_N){cin>>vect[i];}}
#define beginend(vec) (vec).begin(),(vec).end()
#define pb(item) push_back(item)
#define removeAll(vec,deleg) auto itr=remove_if(beginend(vec),deleg);vec.erase(itr,vec.end());
void removeAt(string& s, int index) { s.erase(index, 1); }
template<typename T> void removeAt(vector<T>& v, int index) { v.erase(v.begin() + index); }
ll manhattanDistance(ll x1, ll y1, ll x2, ll y2) { return (abs(x2 - x1) + abs(y2 - y1)); }
vector<ll> sieveOfEratosthenes(int max) {ll prime;double sqrtmax = sqrt(max);vector<ll> primeVec, searchVec;FOR(i, 2, max + 1) searchVec.push_back(i);do{prime = searchVec[0];primeVec.push_back(prime);auto itr = remove_if(beginend(searchVec), [=](ll x)->bool {return x%prime == 0; });searchVec.erase(itr, searchVec.end());} while (prime < sqrtmax);primeVec.reserve(primeVec.size() + searchVec.size());primeVec.insert(primeVec.end(), beginend(searchVec));return primeVec;}


int main() {
	int R0, W0, C, R;
	vi ans;
	while (cin>>R0>>W0>>C>>R)
	{
		if (!R0 && !W0 && !C && !R) break;
		if ((double)R0 / W0 >= C) { ans.pb(0); continue; }
		ans.pb((int)ceil((double)(C*W0 - R0) / R));
	}
	ShowAll(ans);
	return 0;
}

Measured memory_bytes: 3144
#include<stdio.h>
int main(){
    int A,i,F[45];
    
    scanf("%d",&A);
    F[0] = 1;
    F[1] = 1;
    
    for(i=2;i<=44;i++)
    {
        F[i] = F[i-2] + F[i-1];
    }
    printf("%d\n",F[A]);
    return 0;
}



Measured memory_bytes: 2108
#include<stdio.h>

int main(void)

{

  int x, y, z, a, b, c, s, t;

  scanf("%d", &s);
  for (t=0;t<s;t++)
    {

  scanf("%d %d %d", &x, &y, &z);


  a = x*x + y*y;
  b = y*y + z*z;
  c = z*z + x*x;

  if(a==z*z || b==x*x || c==y*y) printf("YES\n");

  else printf("NO\n");

    }  


  return 0;

}

Measured memory_bytes: 580
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define all(x) x.begin(),x.end()
#define F first
#define S second
#define fo(i,n) for(int i=0;i<(n);i++)
#define inp(a) int a;cin>>a;
#define inpa(a,n)vector<int> a(n);fo(i,n)cin>>a[i];
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
using namespace std;
#define int ll
// #define MAX 20
#define INF (int)1e18

template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.F<<','<< P.S<<')';}

void f(int ind,string curr,int n,int ma)
{
	if(ind==n)
	{
		cout<<curr<<'\n';
		return;
	}
	fo(i,ma+1)
	{
		f(ind+1,curr+(char)(i+'a'),n,ma);
	}
	if(ma!=25)
		f(ind+1,curr+(char)(ma+1+'a'),n,ma+1);
}

signed main()
{
	fio
	inp(n)
	f(0,"",n,-1);
	printclock;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)


#define rrep(i,a,b) for(int i=a;i>=b;i--)
int N, M, A, B;
int D[1010];
//-----------------------------------------------------------------
int solve() {
	int cnt = N;
	rep(i, 0, N) {
		if (D[i] < A) {
			cnt = i;
			break;
		}
	}
	if (M <= N - cnt) return cnt;
	
	rrep(i, cnt - 1, 0) {
		if (B < D[i]) return i + 1;
	}

	return 0;
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> M >> A >> B;
	rep(i, 0, N) cin >> D[i];

	cout << solve() << endl;
}

Measured memory_bytes: 3108
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define EPS 1e-9
//#define PI 3.14159265358979

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	int M;
	if (N > 0)
		M = A[0].size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

typedef pair< int, int > pii;
typedef long long ll;

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	cin >> N >> K;
	vector< int > level;
	int i = 1;
	while (i <= N) {
		int j = N / i;
		if (i <= j) {
			level.push_back(1);
			i++;
		} else {
			level.push_back(N / j - i + 1);
			i = N / j + 1;
		}
	}
	//cout << level;
	vector< vector< int > > dp(K + 1, vector< int >(level.size(), 0));
	vector< vector< int > > S(K + 1, vector< int >(level.size() + 1, 0));
	dp[0][0] = 1;
	rep(j, level.size() + 1) S[0][j] = 1;
	rep(i, K) rep(j, level.size()) {
		(dp[i + 1][j] = S[i][level.size() - j] * level[j]) %= MOD;
		(S[i + 1][j + 1] = S[i + 1][j] + dp[i + 1][j]) %= MOD;
	}
	int ans = 0;
	cout << S[K][level.size()] << endl;
	return 0;
}

Measured memory_bytes: 101256
#include <bits/stdc++.h>
using namespace std;

int main() {
  string A, B, C;
  cin >> A >> B >> C;

  char card = A[0];
  A.erase(0, 1);
  while (true) {
    switch (card) {
      case 'a':
        if (A.size() == 0) {
          cout << "A" << endl;
          return 0;
        }
        card = A[0];
        A.erase(0, 1);
        break;
      case 'b':
        if (B.size() == 0) {
          cout << "B" << endl;
          return 0;
        }
        card = B[0];
        B.erase(0, 1);
        break;
      case 'c':
        if (C.size() == 0) {
          cout << "C" << endl;
          return 0;
        }
        card = C[0];
        C.erase(0, 1);
        break;
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int A, B;
int main(){
    scanf("%d %d", &A, &B);
    if(A >= 1 && A <= 9 && B>=1 && B <= 9) printf("%d\n", A*B);
    else printf("-1\n");
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt()-1,a=sc.nextInt(),b=sc.nextInt(),c=sc.nextInt(),d=sc.nextInt();
        System.out.println(Math.min((n/a+1)*b,(n/c+1)*d));
    }
}


Measured memory_bytes: 26396
#include <stdio.h>

int main(int argc, const char * argv[]) {
    char w[101];
    scanf("%s",w);
    int alpha[26]={0};//各アルファベットのカウント数を格納
    
    for(int i=0; w[i]!='\0';i++){//文字列の最後まで出現頻度をカウント
        alpha[w[i]-'a']++; //文字列のi番目がどのアルファベットと一致するか。一致したところに＋１
    }
    
    for(int j=0;j<26;j++){//偶奇判定
        if(alpha[j]%2!=0){
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}



Measured memory_bytes: 128
def cmb(n,r,mod):
    if r<0 or r>n:return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod


mod=10**9+7
n,k=map(int,input().split())
g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,n+2):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1]%mod))

A=[]
for i in range(k):
    print(cmb(n-k+1,i+1,mod)*cmb(k-1,i,mod)%mod)

Measured memory_bytes: 43248
from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[]
 for _ in range(n):
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()


Measured memory_bytes: 40096
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {

        // long startTime = System.currentTimeMillis();

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        String s = scanner.next();

        scanner.close();

        System.out.println(resolve(n, s));

        // System.out.println(System.currentTimeMillis() - startTime);
    }

    private static int resolve(int n, String s) {

        int max = 0;
        String x, y;
        for (int i = 1; i < n; i++) {
            x = s.substring(0, i);
            y = s.substring(i, n);
            int count = compare(x, y);
            if (max < count) {
                max = count;
            }
        }
        return max;
    }

    private static int compare(String x, String y) {
        List<String> listX = Arrays.asList(x.split("")).stream().distinct().collect(Collectors.toList());
        List<String> listY = Arrays.asList(y.split("")).stream().distinct().collect(Collectors.toList());
        return (int) listX.stream().filter(listY::contains).count();
    }
}


Measured memory_bytes: 28876
package main

import (
	"fmt"
)

func main() {
	var (
		n, a, b int
	)

	fmt.Scan(&n, &a, &b)

	sum := 0
	for i := 1; i <= n; i++ {
		p := i / 10000
		q := (i - p*10000) / 1000
		r := (i - p*10000 - q*1000) / 100
		s := (i - p*10000 - q*1000 - r*100) / 10
		t := i - p*10000 - q*1000 - r*100 - s*10
		u := p + q + r + s + t
		if u >= a && u <= b {
			sum += i
		}
	}

	fmt.Println(sum)
}


Measured memory_bytes: 1768
#include<stdio.h>
#include<math.h>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int main(void) {

	int n,a,b,c;

	cin >> n;

	a = n / 100;
	c = n % 10;
	b = ((n - c) / 10)%10;

	if (a == 7 || b == 7 || c == 7) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;

}


Measured memory_bytes: 3052
// @prefix atcoder
// @description atcoder template

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

// typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// rep
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(x) cerr << #x << ": " << x << '\n'
#define DEBUGP(x) cerr << #x << ": " << x.first << " \t" << x.second << '\n'
#define INF (1ll << 60)

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
const int MOD = 1e9 + 7;

int k;
string s;

signed main() {
  cin >> k;
  cin >> s;

  if (s.size() <= k) {
    cout << s << endl;
  } else {
    cout << s.substr(0, k) + "..." << endl;
  }
  return 0;
}


Measured memory_bytes: 3632
MOD = 998244353

class ModCombination
  attr_reader :fac, :inv, :finv, :mod

  def initialize(n, mod: MOD)
    @mod = mod
    @fac = [1, 1]
    @inv = [1, 1]
    @finv = [1, 1]

    (2..n).each do |i|
      @fac[i] = fac[i - 1] * i % mod
      @inv[i] = mod - inv[mod % i] * (mod / i) % mod
      @finv[i] = finv[i - 1] * inv[i] % mod
    end
  end

  def combination(n, k)
    return 0 if n < k
    return 0 if n < 0 || k < 0

    fac[n] * (finv[k] * finv[n - k] % mod) % mod
  end

  def repeated_combination(n, k)
    combination(n + k - 1, k)
  end
end

N, M, K = gets.split.map(&:to_i)
mc = ModCombination.new(N)

total = 1
m_mod = [1]

N.times do
  total *= M
  total %= MOD

  m_mod << (m_mod.last * (M - 1)) % MOD
end

(K + 1).upto(N - 1) do |c|
  v = mc.combination(N - 1, c)

  total -= M * v * m_mod[N - 1 - c]
  total %= MOD
end

puts total


Measured memory_bytes: 21016
S=input()
i=0
while i<len(S):
  if i%2==0:
    if S[i]=="L":
      print("No")
      exit()
    else:
      i+=1
  else:
    if S[i]=="R":
      print("No")
      exit()
    else:
      i+=1
print("Yes")


Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;

class UnionFind {
public:
    vector<int> par;
    UnionFind(int n) {
        par.resize(n);
        for(int i=0;i<n;i++) {
            par[i] = i;
        }
    }

    int root(int x) {
        return par[x] == x ? x:par[x] = root(par[x]);
    }

    // 今回不要
    bool same(int x, int y) {
        return root(x) == root(y);
    }

    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if(x==y) return ; 
            par[x] = y;
    }
};

int main(void) {
    int N,M,p,x,y;
    int cnt = 0;
    cin >> N >> M;

    UnionFind uf(N);   
    vector<int> tr(N);
    for(int i=0;i<N;i++) {
        cin >> p;
        p--;
        tr[i] = p;
    }

    for(int i=0;i<M;i++) {
        cin >> x >> y;
        x--;y--;
        // xとyを同じグループに属させる 
        uf.unite(x,y);
    }

    // グループ(木)毎にチェック。ってどうやるの？
    // root見れば良いだけ
    for(int i=0;i<N;i++) {
        if(uf.same(i, tr[i])) {
            cnt++;
        }
    }

    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;



int main() {
  ll n; cin >> n;
  map<ll, ll> ma;
  rep(i, 0, n){
    ll d; cin >> d;
    ma[d]++;
  }
  ll m; cin >> m;
  bool f = false;
  rep(i, 0, m){
    ll t; cin >> t;
    if(ma[t] > 0){
      ma[t]--;
      continue;
    }
    f = true;
  }
  if(f) cout << "NO" << endl;
  else cout << "YES" << endl;

  return 0;
}


Measured memory_bytes: 12800
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_N 100010

int N;
vector< vector<int> > A;

signed main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;
    A.assign(N, vector<int>(N, 0));
    REP(i, N) {
        REP(j, N-1) {
            cin >> A[i][j];
            A[i][j]--;
        }
    }

    // 各 A がどれだけ進んでいるか
    vector<int> prog(N, 0);
    // 最後までたどり着いたものの数
    int cnt = 0;

    vector<int> check;
    REP(i, N) { check.push_back(i); }

    int ans = 0;
    bool isChange = true;
    while(isChange) {
        isChange = false;
        ans++;

        vector<int> node_to(N, -1);  // i の指し先
        vector<int> next_check;
        for(auto& i : check) {
            if(prog[i] >= N - 1) { continue; }

            node_to[i] = A[i][prog[i]];
            if(node_to[node_to[i]] == i) {
                prog[i]++;
                if(prog[i] >= N - 1) { cnt++; }
                prog[node_to[i]]++;
                if(prog[node_to[i]] >= N - 1) { cnt++; }

                node_to[node_to[i]] = -1;
                node_to[i] = -1;
                isChange = true;
            }
        }
        for(auto& i : check) {
            if(prog[i] >= N - 1) { continue; }
            next_check.push_back(i);
        }
        check.clear();
        copy(next_check.begin(), next_check.end(), back_inserter(check));

        if(ans > 100000) {
            printf("%lld\n", N * (N - 1) / 2);
            return 0;
        }
    }

    ans--;
    if(cnt < N) {
        ans = -1;
    }
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 8192
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main() {
  string s;
  cin >> s;
  cout << s[0] << s.size() - 2 << s[s.size() - 1] << endl;
  return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる



int main() {
  string s;
  cin >> s;
  int n=s.size();
  
  vector<int> p(26,0);
  
  rep(i,n){
    for(char x='a';x<='z';x++){
      if(x==s[i]) p[x-'a']++;
    }
  }
  
  rep(i,26){
    if(p[i]%2==1){
    cout << "No" << endl;
    return 0;
    }
  }
  
  cout << "Yes" << endl;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vin(Vi &v){REP(i,0,(v).size()) cin>>v[i];}
void vin(Vi &v,Vi &v2){REP(i,0,(v).size()) cin>>v[i]>>v2[i];}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
void accum(Vi &v){REP(i,1,(v).size()) v[i]+=v[i-1];}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    int n;
    cin>>n;
    Vi a(n);
    vin(a);

    Vi b=a;
    sort(ALL(b));
    map<int,int> ma;
    REP(i,0,n){
        if(i%2==0) ma[b[i]]++;
    }
    // VPii za(n);
    // REP(i,0,n) za[i]=mp(i,a[i]);
    // REP(i,0,n) sort(ALL(za),comp);
    // REP(i,0,n) za[i].second=i;
    // REP(i,0,n) sort(ALL(za));

    int ans=0;
//    REP(i,0,n) cout<<za[i].first<<" "<<za[i].second<<endl;
    REP(i,0,n) if(i%2==0) if(!ma[a[i]]) ans++;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  int h,w;cin>>h>>w;
  vector<vector<char>> s(h,vector<char>(w));
  rep(i,h)rep(j,w)cin>>s[i][j];
  rep(i,h)rep(j,w){
    if(s[i][j]=='.'){
      s[i][j]='0';
      for(int dx=-1;dx<=1;dx++){
        for(int dy=-1;dy<=1;dy++){
          int nx=i+dx,ny=j+dy;
          if(0<=nx&&nx<h&&0<=ny&&ny<w){
          if(s[nx][ny]=='#')s[i][j]++;
          }
        }
      }
    }
  }
  rep(i,h)rep(j,w){
    cout<<s[i][j];
    if(j==w-1)cout<<endl;
  }
}

Measured memory_bytes: 3584
#include<iostream>
using namespace std;

int main(){

	int a, b;
	char op;

	while (true) {
		cin >> a >> op >> b;
		if (op == '?') {
			break;
		}
		int result;

		switch (op)
		{
		case '+':
			result = a + b;
			break;
		case '-':
			result = a - b;
			break;
		case '*':
			result = a * b;
			break;
		case '/':
			result = a / b;
			break;
		default:
			break;
		}
		cout << result << endl;
	}


	return 0;
}

Measured memory_bytes: 1160
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll INF=1e18;
const ull B=1000000007;//ハッシュの基数

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int left=0,right=n;
    while(right-left>1){
        int mid=(right+left)/2;
        ull t=1;
        for(int i=0;i<mid;i++) t*=B;
        set<ull> st;
        queue<ull> que;
        ull sh=0;
        for(int i=0;i<mid;i++) sh=sh*B+s[i];
        bool ok=0;
        for(int i=0;i+mid<=n;i++){
            if(st.count(sh)){
                ok=1;
                break;
            }
            que.push(sh);
            if(i>=mid-1){
                ull v=que.front();
                que.pop();
                st.insert(v);
            }
            if(i+mid<n) sh=sh*B+s[i+mid]-s[i]*t;
        }
        if(ok) left=mid;
        else right=mid;
    }
    cout<<left<<endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;

int main() {

  int D, G;
  cin >> D >> G;

  vector<pair<int,int>> PC(D);

  for (int i = 0; i < D; i++) {
    int p, c;
    cin >> p >> c;
    PC[i] = make_pair(p, c);
  }

  int answer = 1e9+7;

  // 1.100i点を完全に解く
  // 2.100i点を全く解かない
  // 3.100i点を中途半端に解く

  int current = 0;
  int count = 0;
  bool flg = false;
  
  // 3はないと過程した場合、1と2だけの全ての組み合わせをbit全探索で調べる
  for(int bits = 0; bits < (1 << D); bits++) {

    vector<int> bit;
    set<int, greater<int>> st;

    current = 0;
    count = 0;
    flg = false;

    for (int i = 0; i < D; i++) {
      if (bits & (1 << i)) {
        current += PC[i].first * 100 * (i + 1) + PC[i].second;
        count += PC[i].first;
      } else {
        st.insert(i);
      }
    }

    if (G <= current) {
      flg = true;
      answer = min(answer, count);
    } else {
      
      bool flg2 = true;
      int dif = G - current;

      while (flg2) {
        for (auto item:st) {
          int count_ = ceil((double) dif / ((item + 1) * 100));
          if (count_ < PC[item].first) {
            count += count_;
            answer = min(answer, count);
            flg2 = false;
            break;
          }
        }
        flg2 = false;
      }

    }

  }

  cout << answer << endl;

  return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <unordered_map>
#define inputarr(a,n) for(ll i=0;i<n;i++) cin>>a[i];
#define prllarr(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" ";
#define pb push_back
#define ll long long
#define mod 1000000007
#define foi ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define in(n) scanf("%lld",&n);
#define in2(x,y) scanf("%lld %lld",&(x),&(y));
#define in3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define out(n) printf("%lld\n",n);
#define out2(x,y) printf("%lld %lld\n",x,y);
#define test(t)  ll t; in(t);while(t--)
#define set(arr,n,s) for(ll i=0;i<n;i++){arr[i]=s;}


ll power(ll x,ll y,ll p){ll res=1;x=x%p;while(y>0){if(y&1){res=(res*x)%p;} y=y>>1;x=(x*x)%p;}return res;}
ll modInverse(ll a,ll p){return power(a,p-2,p);}//used with feemat little

ll gcd(ll x,ll y){if(x==0 || y==0){return max(y,x);}return gcd(y%x,x);}
ll gcdExtended(ll a,ll b,ll &x,ll &y){if(a==0){x=0;y=1;return b;}ll x1,y1;ll gcd = gcdExtended(b%a,a,x1,y1);x=y1-(b/a)*x1;y=x1;return gcd;}//o(log(b))
;
void prac(){
	#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   #endif 
}

ll n;
void multiply(vector<vector<ll> >& a,vector<vector<ll> >& b)
{
	ll c[53][53]={0};
	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++){
			for(ll k=0;k<n;k++){
				c[i][j]+=(a[i][k]*b[k][j]);
				c[i][j]%=mod;
			}
		}
	}
	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++){
			a[i][j]=c[i][j];
		}
	}
	return ;

}
void func(vector<vector<ll> >& a,ll k){
	if(k==1)return;
	vector<vector<ll> >dp(n,vector<ll>(n));
	dp=a;
	func(a,k/2);
	multiply(a,a);
	if(k%2==1){
		multiply(a,dp);
	}
	return ;
}




int main() 
{
  	// prac();
  	ll k;
  	in2(n,k)
  	vector<vector<ll> >arr(n,vector<ll>(n));
  	for(ll i=0;i<n;i++){
  		for(ll j=0;j<n;j++){
  			in(arr[j][i])
  		}
  	}
  	func(arr,k);
  	ll ans=0;
  	for(ll i=0;i<n;i++){
  		for(ll j=0;j<n;j++){
  			ans+=arr[i][j];
  		}
  	}
  	out((ans)%mod)

}
/*error-----
convert every int to long long eg-1LL
create array with proper analysis of problem constrain
check mod also
*/






Measured memory_bytes: 1536
#include <bits/stdc++.h>

#include <boost/algorithm/string/classification.hpp>  // is_any_of
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/math/tools/minima.hpp>
#include <boost/multi_array.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/optional.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>

#define rep(i, n) for (int i = 0; i < (n); ++i)

namespace adaptor = boost::adaptors;
using namespace std;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::replace_all;
using boost::algorithm::split;
using boost::math::tools::brent_find_minima;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP
void Main()
{
	const ll MOD = 1e9 + 7;
	int n, k;
	cin >> n >> k;
	ll sum;
	sum = 0;
	for (ll i = k; i <= n + 1; i++)
	{
		ll start;
		start = (i - 1) * i / 2;
		ll end;
		end = n * i - ((i - 1) * i / 2);
		sum += (end - start + 1);
		sum %= MOD;
	}
	cout << sum << endl;
}
// END

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	Main();
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int h, w, k;
int ans=9999999, tmp;
vector<int> bi, cnt, pcnt;
vector< vector<int> > board;

//0~pa-1を長さnで生成、合計pa^n個生成
void bitgen(int n) {

	//生成完了時の処理
	if (n == 0) {

		//for (int i = 0;i<bi.size();i++) cout << bi[i] << "  ";
		//cout << endl;

		int bsz = 1;
		for (int i = 0;i < bi.size();i++) bsz += bi[i];

		cnt.resize(bsz);
		pcnt.resize(bsz);
		int p, flag;
		tmp = 0;
		for (int j = 0;j < bsz;j++) cnt[j] = 0;
		
		for (int i = 0;i < w;i++) {
			//cout << i << " " << bsz << endl;
			p = 0;
			flag = 0;
			for (int j = 0;j < bsz;j++) pcnt[j] = 0;

			for (int j = 0;j < h;j++) {
				cnt[p] += board[j][i];
				pcnt[p] += board[j][i];
				if (bi[j]) p++;
			}

			for (int j = 0;j < bsz;j++) {
				if(cnt[j] > k) flag = 1;
				if (pcnt[j] > k) return;
			}

			//cout<< "w=" << i << " " << cnt[0] << " " << pcnt[0] << endl;
			if(flag){
				//cout << i << endl;
				for (int j = 0;j < bsz;j++) {
					//cout << cnt[j] << " dd " << pcnt[j] << endl;
					cnt[j] = pcnt[j];
				}
				tmp++;
			}

		}

		tmp += bsz-1;
		ans = min(ans, tmp);
		return;
	}

	//再帰部分
	for (int i = 0;i<2;i++) {
		bi[n - 1] = i;
		bitgen(n - 1);
	}
}

int main() {

	string s;
	cin >> h >> w >> k;

	board.resize(h);
	for (int i = 0;i<h;i++) board[i].resize(w);

	for (int i = 0;i<h;i++) {
		cin >> s;
		for (int j = 0;j<w;j++) {
			board[i][j] = (int)(s[j] - '0');
		}
	}

	/*for (int i = 0;i<h;i++) {
		for (int j = 0;j<w;j++) {
			cout << board[i][j];
		}
		cout << endl;
	}*/

	bi.resize(h-1);
	bitgen(h-1);

	cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>
using namespace std;

using ll = long long;

#define for_(i,a,b) for(int i = (a);i < (b);i++)
#define rfor_(i,a,b) for(int i = (b)-1;i >= (a);i--)
#define rep(i,n) for_(i,0,(n))
#define rrep(i,n) rfor_(i,0,(n))

int A[100][100];
int b[100];

int n, m;

int main(){
	cin.tie(0);
	
	cin>>n>>m;
	
	rep(i, n)rep(j, m)cin>>A[i][j];
	rep(i, m)cin>>b[i];
	
	rep(i, n) {
	    int c = 0;
	    rep(j, m)c += A[i][j]*b[j];
	    cout<<c<<endl;
	}

	return 0;
}



Measured memory_bytes: 3144
n = input()
keta = len(n)
n = int(n)

if keta == 1:
    print(n)
elif keta == 2:
    print(9)
elif keta == 3:
    print(n - 90)
elif keta == 4:
    print(909)
elif keta == 5:
    print(n - 9000  - 90 )
else:
    print(90909)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		
		long x = scan.nextLong();
		long count500 = 0;
		long count5 = 0;
		
		
		if(x % 500 >= 0) {
			count500 = (x - x % 500) / 500;
			x %= 500;
		}
		if(x % 5 >= 0) {
			count5 = (x - x % 5) / 5;
			x %= 5;
			
		}
		/*
		System.out.println(count500);
		System.out.println(count5);
		System.out.println(x);
		*/
		
		long ans = 1000 * count500 + 5 * count5;
		
		System.out.println(ans);
	}

}


Measured memory_bytes: 22740
import math
 
N,D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
 
ans = 0
 
for i in range(N-1):
    for j in range(i+1, N):
        d = 0
        for k in range(D):
            d += (X[i][k] - X[j][k])**2
        ans += math.sqrt(d).is_integer()
print(ans)

Measured memory_bytes: 9192
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int N;

int main() {
    cin >> N;
    int odd = 0, even = 0, four = 0;
    for (int i = 0; i< N; i++) {
        int a;
        cin >> a;
        if (a % 4 == 0) {
            four++;
        } else if (a % 2 == 0) {
            even++;
        } else {
            odd++;
        }
    }
    if (even == 0) --odd;
    cout << (odd <= four? "Yes": "No") << endl;
    
}




Measured memory_bytes: 256
input = require('fs').readFileSync('/dev/stdin', 'utf8')
S = input.split('\n').shift()
s = ['W', 'B']
b = S[0] == s[1]
cnt = 0
for (i=1;i<S.length;i++) {
    if (s[~~!b] == S[i]) {
        b = !b
        cnt++
    }
}
console.log(cnt)

Measured memory_bytes: 7500
#include <bits/stdc++.h>  // clang-format off
using namespace std;
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (int i = (a), lim_i = (b); i < lim_i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Mon Mar 16 20:03:54 JST 2020
 **/

signed main() {
    int a, b;
    cin >> a >> b;
    cout << (b - 1 + a - 1 - 1) / (a - 1) << endl;
}


Measured memory_bytes: 256
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i=(n); i>=0; --i)
#define FOR(i, n, m) for(int i=(m), i##_len=(n); i<i##_len; ++i)
#define EACH(i, v) for(const auto& i : v)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class Value>using vec = vector< Value >;
using ll = long long;
using P = pair< long long, long long >;
#define fi first
#define se second
#define el endl
#pragma endregion
void Main();

int main(){
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}

void Main(){
    ll R, G, B, N;
    cin >> R >> G >> B >> N;
    ll cnt = 0;
    REP(i, N/R+1){
        REP(j, N/G+1){
            int t = N-(R*i+G*j);
            if(t>=0 && t%B == 0){
                cnt++;
                //cout << i << " " << j << " " << t/B << el;
            }
        }
    }
    cout << cnt << el;
}



Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,M;cin>>N>>M;
  double S=0;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
    S+=A.at(i);
  }
  sort(A.begin(),A.end());
  cout<<fixed<<setprecision(2);
  cout<<(A.at(N-M)>=S/4/M?"Yes":"No")<<endl;
}


Measured memory_bytes: 3528
import itertools
N, M, Q = map(int,input().split())
ans = 0
A = []
B = []
C = []
D = []
for _ in range(Q):
    a, b, c, d = map(int,input().split())
    A.append(a-1)
    B.append(b-1)
    C.append(c)
    D.append(d)

ans = 0
for seq in itertools.combinations_with_replacement(range(M),N):
    tmp = 0
    for i in range(Q):
        if seq[B[i]] - seq[A[i]] == C[i]:
            tmp += D[i]
    ans = max(ans,tmp)

print(ans)

Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

/*
given weights and values array, each i-th means it weights[i] and values[i] 

find the maximum with given W 

3 8
3 30
4 50
5 60
dp[i][w] = i-th means consider up to i, w means the weight it used 
1. add it (if w >= weights[i])
dp[i][w] = dp[i-1][w-weights[i]] + values[i]
2. ignore it 
dp[i][w] = dp[i-1][w]

dp[c] = minimum weight to get to c.
ans = max(c in dp[c] that dp[c] > -1)

*/

int main() {
    const int INF = 1e9+7;
    int n;
    int W;
    //int ans = 0;
    ll ans = 0;
    scanf("%d%d", &n, &W);
    /*
    vector<int> weights(n);
    vector<int> values(n);
    ll sum_value = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &weights[i], &values[i]);
        sum_value += values[i];
    }
    
    vector<int> dp(sum_value+1, INF);
    
    dp[0] = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = sum_value-values[i]; j >= 0; j--) {
            int new_weight = weights[i] + dp[j];
            int new_value = values[i] + j;
            dp[new_value] = min(dp[new_value], new_weight);
            if (new_weight <= W) {
                ans = max(ans, new_value);    
            }
        }
    }
    
    */
    
    
    
    
    //vector<ll> dp(100001);
    unordered_map<ll, ll> dp;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        int weight;
        int value;
        vector<pair<ll, ll>> to_add;
        scanf("%d%d", &weight, &value);
        for (const auto& any : dp) {
            ll new_value = any.first + value;    
            ll new_weight = any.second + weight;
            if (new_weight <= W) {
                to_add.push_back({new_value, new_weight});
                ans = max(ans, new_value);
            }
        }
        while (!to_add.empty()) {
            pair<ll, ll> p = to_add.back();
            to_add.pop_back();
            if (dp.find(p.first) == dp.end()) {
                dp[p.first] = p.second;    
            }
            else {
                dp[p.first] = min(dp[p.first], p.second);    
            }
            
        }
        
    }
    
    /*
    //vector<ll> dp(W+1);
    unordered_map<ll, ll> dp;
    
    for (int i = 1; i <= n; i++) {
        int weight;
        int value;
        scanf("%d%d", &weight, &value);
        for (int w = W; w >= weight; w--) {
            if (w >= weight) {
                dp[w] = max(dp[w], dp[w-weight]+value); // add
                ans = max(ans, dp[w]);
            }
        }
    }
    */
    
    //printf("%d", ans);
    printf("%lld", ans);
	return 0;
}






Measured memory_bytes: 4392
#include <bits/stdc++.h>
#define LL long long
using namespace std;

struct U {
	LL a;
	LL b;
};
U f[200009];
int n;
LL sum;
bool cmp(U a,U b) {
	return a.b<b.b;
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		scanf("%lld %lld",&f[i].a,&f[i].b);
	}
	sort(f+1,f+n+1,cmp);
	for(int i=1; i<=n; i++) {
		if(sum+f[i].a<=f[i].b) {
			sum+=f[i].a;
		} else {
			printf("No");
			return 0;
		}
	}
	printf("Yes");
	return 0;
}

Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>

using namespace std;

int main()
{ int N; cin >> N;

 map<int,int> mp;
 
 for(int i = 0; i < N; i++){ int a; cin >> a; mp[a]++;} int cnt = 0;
 
 for(auto p:mp){
   int s = p.first;
   int t = p.second;
   
   if( t >= s){  cnt += t - s;}
   else{ cnt += t;}}
 
 cout << cnt << endl; return 0;}
 
 

Measured memory_bytes: 4736