akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define N 300
#define M 100000
using namespace std;
int n, a[N], b[N];

struct Edge
{
    struct edge{ int v, nxt; }e[M];
    int tot, hd[N];
    void init(){ tot = 0, memset(hd, 0, sizeof(hd)); }
    void add(int u, int v){ e[++tot].v = v, e[tot].nxt = hd[u], hd[u] = tot; }
}e;

struct Bipartite
{
    int n;
    int result[N + 1], state[N + 1];//M:y集合点数,下标从1开始 result[y]:x集合中对应的当前匹配边,state[y]:当前匹配轮now是否遍历到y点(state[y]==now说明遍历到)
    bool hungary(int u, int now)//now:x集合的遍历起点,下标从1开始
    {
        for(int i = e.hd[u]; i; i = e.e[i].nxt)
        {
            int v = e.e[i].v;
            if(state[v] == now) continue;
            state[v] = now;
            if(!result[v] || hungary(result[v], now))
            {
                result[v] = u;
                return 1;
            }
        }
        return 0;
    }
    void init()
    {
        memset(result, 0, sizeof(result));
        memset(state, 0, sizeof(state));
        //addedge()//伪代码:x集合点[1,N]连向[1,M],可以共用编号[1,max(N,M)]
    }
    int matchNum(int _n)
    {
        n = _n;
        int cnt = 0;
        init();
        for(int i = 1; i <= n; i ++)
            if(hungary(i, i)) cnt ++;
        return cnt;
    }
}bi;


int main()
{
//    freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d", &n);
    e.init();
    for(int i = 1; i <= 2 * n; i ++) scanf("%d%d", &a[i], &b[i]);
    for(int i = 1; i <= n; i ++)
    {
        for(int j = n + 1; j <= 2 * n; j ++)
        {
            if(a[i] < a[j] && b[i] < b[j]) e.add(i, j);
        }
    }
    printf("%d\n", bi.matchNum(n));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using Z=long long;
Z S(vector<pair<int,int>> a){
sort(a.begin(),a.end());Z A=0;
priority_queue<int,vector<int>,greater<>> Q;
for(auto [k,d]:a){
Q.emplace(d);A+=d;
while(Q.size()>k)A-=Q.top(),Q.pop();
}return A;}
int main(){
	int q; scanf("%d",&q);
	rep(_,q){
		int n; scanf("%d",&n);
		Z sum=0;
		vector<pair<int,int>> L,R;
		rep(i,n){
			int k,l,r; scanf("%d%d%d",&k,&l,&r);
			if     (l>r) L.emplace_back( k ,l-r), sum+=r;
			else if(r>l) R.emplace_back(n-k,r-l), sum+=l;
			else         sum+=l;
		}
		cout<<sum+S(L)+S(R)<<endl;
	}

}


Measured memory_bytes: 7188
def s()
  gets().chomp
end
def i()
  gets.to_i
end
def li()
  gets.split.map(&:to_i)
end
def ili()
  n = gets.to_i
  as = gets.split.map(&:to_i)
  [n, as]
end

def dijkstra(s, e, cost, size)
  if s==e
    return 0
  end
  dp = {}
  dp[s] = 0
  undefined_node = {}
  size.times{|i|
    if i != s
      undefined_node[i] = cost[s][i]
    end
  }
  while undefined_node.length != 0
    min = undefined_node.min_by{|_, v| v}
    stock = {}
    temp = undefined_node.clone
    temp.each{|k, v|
      if min[1] == v
        undefined_node.delete(k)
        if k == e
          return v
        end
        dp[k] = v
        stock[k] = v
      end
    }

    stock.each{|k, v|
      undefined_node.each{|k2, v2|
        undefined_node[k2] = v + cost[k][k2] < v2 ?  v + cost[k][k2] : v2
      }
    }
  end
end

h, w  = li()
cs = []
10.times{
  cs << li()
}
as = []
h.times{
  as << li()
}

res = 0
dist = Array.new(10)
10.times{|i|
  dist[i] = dijkstra(i, 1, cs, 10)
}
h.times{|i|
  w.times{|j|
    if as[i][j] != -1
      res += dist[as[i][j]]
    end
  }
}
puts res

Measured memory_bytes: 2556
#include<bits/stdc++.h>
using namespace std;
int main(){
   int A,B,K;cin>>A>>B>>K;
   for(int i=1;i<K+1;i++){
     if(i%2==1){
       if(A%2==0){
             B+=A/2;
             A/=2;
}else{    B+=(A-1)/2;
             A=(A-1)/2;
}
}else{if(B%2==0){
             A+=B/2;
             B/=2;
}else{    A+=(B-1)/2;
             B=(B-1)/2;
}
}
}
  cout<<A<<" "<<B<<endl;
}

Measured memory_bytes: 256
from collections import Counter
n,*a=map(int,open(0).read().split())
l=[0]*n
r=[0]*n
for i,c in enumerate(a):
  l[i]+=c+i+1
  r[i]+=i+1-c
L=Counter(l)
R=Counter(r)
def count(A):
  ret=0
  for i in A.values():
    ret+=i*(i-1)//2
  return ret
print(count(L+R)-count(L)-count(R))

Measured memory_bytes: 174932
package main
 
import (
  "fmt"
  "os"
  "bufio"
  "strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
  sc.Split(bufio.ScanWords)
  s := nextStr()
  t := nextStr()
  a := nextInt()
  b := nextInt()
  u := nextStr()
  
  if s == u {
    fmt.Println(a - 1, b)
  } else if t == u {
    fmt.Println(a, b - 1)
  }
}


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

using namespace std;

#define ll long long int
#define ld long double
#define pii pair<int,int>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define bit(a,b) ((a>>b)&1)
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const ll mx = 1e6+1, Mod = 1e9+7;

ll a, b, c, k;

int main()
{
    cin >> a >> b >> c >> k;
    if(k%2)
        cout << b-a << '\n';
    else
        cout << a-b << '\n';
    return 0;
}












Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#define fo(i,a,b) for(i=a;i<=b;i++)

using namespace std;

const int maxn=2005;

int dis[maxn],fi[maxn],ne[maxn*2],dui[maxn*2],qc[maxn],duii[maxn*2];
bool bz[maxn];
int i,j,k,l,m,n,x,y,z,ans,tot,now;

void add(int x,int y){
    if (fi[x]==0) fi[x]=++now; else ne[qc[x]]=++now;
    qc[x]=now; dui[now]=y; duii[now]=x;
}
void dfs(int x){
    bz[x]=true;
    int i=fi[x];
    while (i){
        if (bz[dui[i]]==true){
            i=ne[i];
            continue;
        }
        dis[dui[i]]=dis[x]+1;
        dfs(dui[i]);
    }
}
void work1(){
    k=k/2;
    ans=n;
    fo(i,1,n){
        memset(bz,false,sizeof(bz));
        dis[i]=0;
        dfs(i); tot=0;
        fo(j,1,n) if (dis[j]>k) tot++;
        ans=min(ans,tot);
    }
}
void work2(){
    k=(k+1)/2;
    ans=n;
    fo(i,1,now){
        memset(bz,false,sizeof(bz));
        dis[dui[i]]=dis[duii[i]]=1;
        bz[dui[i]]=bz[duii[i]]=true;
        dfs(dui[i]);
        dfs(duii[i]); tot=0;
        fo(j,1,n) if (dis[j]>k) tot++;
        ans=min(ans,tot);

    }
}
int main(){
   // freopen("c.in","r",stdin);
   // freopen("c.out","w",stdout);
    scanf("%d%d",&n,&k);
    fo(i,1,n){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    if (k%2==0) work1(); else work2();
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
 
int main()
{
  int q;
  while (cin >> q, q != -1){
    double x = q / 2.0;
    while (fabs(pow(x, 3) - q) >= 0.00001 * q){
      x = x - (pow(x, 3) - q) / (3 * x * x);
    }
    printf("%f\n", x);
  }
  return (0);
}

Measured memory_bytes: 1184
#include <iostream>
#include <string>
using namespace std;
int w,h;
string s[51];
const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};

void dfs(int ai, int aj, char c) {
  if (s[ai][aj] == '.') {
    s[ai][aj] = (c == 'W') ? 'w' : 'b' ;
  } else if ((s[ai][aj] == 'b' && c == 'W') ||
             (s[ai][aj] == 'w' && c == 'B')) {
    s[ai][aj] = 'o'; 
  }
  
  for (int z = 0; z < 4; z += 1) {
    int ti = ai + di[z], tj = aj + dj[z];
    if (ti < 0 || tj < 0 || ti >= h || tj >= w) continue;
    if (s[ti][tj] == 'B' || s[ti][tj] == 'W') continue;
    
    if ((s[ti][tj] == '.') || 
      (s[ti][tj] == 'b' && c == 'W') ||
      (s[ti][tj] == 'w' && c == 'B')) {
      dfs(ti, tj, c);
    }
  }
}

void solve() {
  for(int i=0;i<h;i++) cin>>s[i];
  
  for(int i=0;i<h;i++)
  for(int j=0;j<w;j++)
  if (s[i][j] == 'B' || s[i][j] == 'W') {
    dfs(i, j, s[i][j]);
  }
  
  int bc = 0, wc = 0;
  for(int i=0;i<h;i++)
  for(int j=0;j<w;j++)
  if (s[i][j] == 'b') {
    bc++;
  } else if (s[i][j] == 'w') {
    wc++;
  }
  
  cout<<bc<<" "<<wc<<endl;
}

int main (int argc, char const* argv[]) {
  while (cin>>w>>h, w||h) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;

int main(){
  string s,t;
  cin >> s >> t;
  int n=s.size();
  int ans=0;
  rep(i,n){
    if(s[i]!=t[i]) ans++;
  }
  cout << ans;
  return 0;
}

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

int N;
int moon[2][11]= {
  {0,20,19,20,19,20,19,20,19,20,19},
  {0,20,20,20,20,20,20,20,20,20,20}
};

bool check(int y){
  if( y%3 == 0 ) return true;
  return false;
}

int solve(int Y,int M,int D){
  int ret = 0;
  for(int y=1;y<=Y;y++){
    bool leap = check(y);
    for(int m=1;m<=10;m++){
      for(int d=1;d<=moon[leap][m];d++){
	ret++;
	if( y == Y && m== M && d == D ) return ret;
      }
    }
  }
  return 0;
}

int main(){
  cin >> N;
  for(int ttt=0;ttt<N;ttt++){
    int Y1,M1,D1;
    cin >> Y1 >> M1 >> D1;
    cout << solve(1000,1,1) - solve(Y1,M1,D1) << endl;
  }
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t N, M;
  cin >> N >> M;
  vector<int64_t> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  vector<int64_t> sum(N+1);
  for(int i=0; i<N; i++){
    sum.at(i+1) = vec.at(i) + sum.at(i);
  }
  
  int64_t ok = 0;
  int64_t ng = 1000000000000000000;
  
  vector<int64_t>::iterator pos;
  int64_t idx;
  
  while(ng - ok > 1){
    int64_t mid = (ok+ng)/2;
    int64_t cnt = 0;
    for(int i=0; i<N; i++){
      pos = lower_bound(vec.begin(),vec.end(),mid-vec.at(i));
      idx = distance(vec.begin(),pos);
      cnt += N - idx;
    }
    if(cnt < M){
      ng = mid;
    }
    else{
      ok = mid;
    }
  }
  //cout << ok << endl;
  
  int64_t ans = 0;
  int64_t equal = 0;
  int64_t over = 0;
  for(int i=0; i<N; i++){
    pos = lower_bound(vec.begin(),vec.end(),ok-vec.at(i));
    idx = distance(vec.begin(),pos);
    if(idx < N){
      ans += vec.at(i)*(N-idx) + sum.at(N) - sum.at(idx);
    }
    over += N - idx;
    //cout << idx  << " " << ans<< endl;
  }
  if(over > M){
    ans -= ok*(over-M);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include<cstdio>  
#include<cstring>  
#include<algorithm>  
#include<iostream>  
#include<string>  
#include<vector>  
#include<stack>  
#include<bitset>  
#include<cstdlib>  
#include<cmath>  
#include<set>  
#include<list>  
#include<deque>  
#include<map>  
#include<queue>
using namespace std;
typedef long long ll;
const ll inf=1<<29;
const ll Maxn=1e6;

int a[Maxn];

int main(){
	int n,sum=0;
	cin>>n;
	for(int i=1;i<=2*n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+1+2*n);
	for(int i=1;i<=2*n;i+=2){
		sum+=a[i];
	}
	printf("%d",sum);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n;
ll a,b;
int t[5010];
ll dp[5010][5010];
int pos[5010];

void solve(){
  cin >> n >> a >> b;
  vector<P> v;
  rep(i,n){
    cin >> t[i];
    t[i]-=1;
    pos[t[i]]=i;
  }
  
  rep(i,n+1){
    rep(j,n+1){
      dp[i][j]=INF;
    }
  }
  dp[0][0]=0;
  rep(i,n+1){
    rep(x,n+1){
      if(pos[i]>=x)dp[i+1][x]=min(dp[i+1][x],dp[i][x]+b);
      else dp[i+1][x]=min(dp[i+1][x],dp[i][x]+a);
      if(t[x]==i)dp[i+1][x+1]=min(dp[i+1][x+1],dp[i][x]);
      dp[i][x+1]=min(dp[i][x+1],dp[i][x]);
    }
  }
  rep(i,n+1){
    rep(j,n+1){
      //cout << i << " " << j << " " << dp[i][j] << endl;
    }
  }
  cout << dp[n][n] << endl;
}

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

Measured memory_bytes: 196096
/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */

#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int64_t, int64_t>;
constexpr int64_t kInf = INT64_MAX / 2L;

// std::cout << std::setprecision(20) << 1.1 << endl;

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

  int64_t V, E;
  cin >> V >> E;
  // const int64_t L = static_cast<int64_t>(T.length());
  vector<vector<int64_t>> connected(V + 1);
  vector<Pair> edges;
  for (int64_t i = 0; i < E; ++i) {
    int64_t a, b;
    cin >> a >> b;
    connected[a].emplace_back(b);
    connected[b].emplace_back(a);
    edges.emplace_back(a, b);
  }
  int64_t result = 0;
  for (const auto &edge : edges) {
    vector<bool> visited(V + 1, false);
    queue<int64_t> q;
    auto Visit = [&](const int64_t vertex) {
      visited[vertex] = true;
      for (const auto &next : connected[vertex]) {
        if ((edge.first == vertex && edge.second == next) || (edge.first == next && edge.second == vertex)) {
          // DO NOTHING
        } else {
          if (!visited[next]) {
            visited[vertex] = true;
            q.emplace(next);
          }
        }
      }
    };
    Visit(1);
    while (!q.empty()) {
      int64_t v = q.front();
      q.pop();
      Visit(v);
    }
    bool is_bridge = false;
    for (int64_t v = 1; v <= V; ++v) {
      if (!visited[v]) {
        is_bridge = true;
      }
    }
    if (is_bridge) {
      ++result;
    }
  }
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>

int main(void) {
	int N;
	long sum = 0;
	
	scanf("%d", &N);
	
	for(int i = 1; i <= N; i++) {
		if(i % 3 == 0)	continue;
		if(i % 5 == 0)	continue;
		sum += i;
	}
	
	printf("%ld\n", sum);
	
	return 0;
}


Measured memory_bytes: 1736
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = tuple(map(int, readline().split()))
cnt = 0
for i in range(n):
    if a[i] % 2 == 0:
        cnt += 1
print(3 ** n - 2 ** cnt)


Measured memory_bytes: 2940
from functools import lru_cache


R, C = list(map(int, input().split()))
grid = []
for r in range(R):
    grid.append(list(input().rstrip()))


@lru_cache(maxsize=None)
def minDist(r, c):
    color = int(grid[r][c] == "#")

    best = float("inf")
    if r == 0 and c == 0:
        return color
    if r >= 1:
        best = min(
            best,
            int(grid[r][c] != grid[r - 1][c] and color)
            + minDist(r - 1, c),
        )
    if c >= 1:
        best = min(
            best,
            int(grid[r][c] != grid[r][c - 1] and color)
            + minDist(r, c - 1),
        )
    return best


print(minDist(R - 1, C - 1))


Measured memory_bytes: 53848
n, m = map(int, input().split())
if n >= m:
    print(0)
    exit()

lx = sorted(list(map(int, input().split())))

ld = sorted([lx[i+1]-lx[i] for i in range(m-1)])
if n == 1:
    print(sum(ld))
else:
    print(sum(ld[:-(n-1)]))

Measured memory_bytes: 13960
#include<stdio.h>
int main(){
  int n,i,a,b,max,s,d[1000010];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&a,&b);
    d[a]++;
    d[b+1]--;
  }
  s=1;
  for(i=max=0;i<n+2;i++){
    s+=d[i];//printf("%d ",s);
    if(max<s&&i<=s)max=i;
  }//printf("\n");
  printf("%d\n",max-1);
  return 0;
}

Measured memory_bytes: 2916
from collections import deque

N, M = [int(v) for v in input().split()]

ad_l = [[] for _ in range(N)]

for _ in range(M):
    a,b = [int(v) for v in input().split()]
    ad_l[a-1].append(b-1)
    ad_l[b-1].append(a-1)

visited = [-1 for _ in range(N)]


queue = deque([0])

while queue:
    now = queue.pop()
    for n in ad_l[now]:
        if visited[n] != -1: continue
        visited[n] = now + 1
        queue.appendleft(n)

visited = visited[1:]

if -1 in visited:
    print("No")
else:
    print("Yes")
    for v in visited:
        print(v)


Measured memory_bytes: 37568
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
typedef long long ll;
using namespace std;

const int N=2010,inf=1e8;
char mp[N][N];
int n,m,ans,f[N][N];

int main(){
	scanf("%d%d",&n,&m);
	rep(i,1,n) rep(j,1,m) scanf(" %c",&mp[i][j]);
	rep(i,1,n) rep(j,1,m){
		if (mp[i][j]=='#') f[i][j]=0; else f[i][j]=inf;
		if (i>1) f[i][j]=min(f[i][j],f[i-1][j]+1);
		if (j>1) f[i][j]=min(f[i][j],f[i][j-1]+1);
	}
	for (int i=n; i; i--) for (int j=m; j; j--){
		if (i<n) f[i][j]=min(f[i][j],f[i+1][j]+1);
		if (j<m) f[i][j]=min(f[i][j],f[i][j+1]+1);
	}
	rep(i,1,n) rep(j,1,m) ans=max(ans,f[i][j]);
	printf("%d\n",ans);
	return 0;
}

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

#define int long long
#define double long double

using namespace std;

#define REP(i, a, b) for (int(i) = (a); i < (b); (i)++)
#define rep(i, n) REP(i, 0, n)
#define PER(i, a, b) for (int(i) = (a - 1); i >= (b); (i)--)
#define per(i, n) PER(i, n, 0)
#define each(i, n) for (auto &i : n)
#define clr(a) memset((a), 0, sizeof(a))
#define mclr(a) memset((a), -1, sizeof(a))
#define all(a) (a).begin(), (a).end()
#define dum(val) cerr << #val " = " << val;
#define dump(val) cerr << #val " = " << val << endl;
#define FILL(a, v) fill(a, a + sizeof(a) / sizeof(*a), v)

typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const int mod = 1e9 + 7;
const int INF = 1e9;

void print(int bit) {
	per(i, 16) {
		if (bit & (1 << i)) {
			cout << 1;
		} else {
			cout << 0;
		}
	}
	cout << endl;
}

signed main() {
	int n, k;
	cin >> n >> k;

	vector<int> a(n), b(n);
	rep(i, n) {
		cin >> a[i] >> b[i];
	}
	auto calc = [&](int lim) {
		int res = 0;

		rep(i, n) {
			if ((lim | a[i]) == lim) {
				res += b[i];
			}
		}

		return res;
	};

	int ans = calc(k);
	per(i, 31) {
		if (k & (1 << i)) {
			int k_ = k & ~(1 << i);
			rep(j, i) {
				k_ |= (1 << j);
			}
			ans = max(ans, calc(k_));
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
def main():
    n = int(input())
    h = list(map(int, input().split()))

    score = []

    j = 0
    for i in range(n-1):
        if i != 0:
            j = next_j
        cnt = 0
        while True:
            if j >= n-1 or h[j] < h[j+1]:
                score.append(cnt)
                next_j = j+1
                break
            else:
                h[j] >= h[j+1]
                cnt += 1
                j += 1

    if n == 1:
        print(0)
    else:
        print(max(score))

if __name__ == '__main__':
    main()

Measured memory_bytes: 20552
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b % a, a);
}
int main () {
    long long n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    long long lcm = 1;
    for (int i = 0; i < n; i++) {
        lcm = lcm / gcd(lcm, a[i]) * a[i];
        if (lcm / 2 > m) {
            puts("0");
            return 0;
        }
    }
    for (int i = 0; i < n; i++) {
        if ((lcm / a[i]) % 2 == 0) {
            puts("0");
            return 0;
        }
    }
    long long ba = lcm / 2;
    cout << (m-ba)/lcm + 1 << endl;
}

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

using namespace std;

int N, M;
vector<bool> used;
vector<vector<int>> graph;

int dfs(int u, int c) {
  if (c == N - 1) return 1;

  int res = 0;
  for (auto v : graph[u]) {
    if (used[v]) continue;
    used[v] = true;
    res += dfs(v, c + 1);
    used[v] = false;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> M;
  used.assign(N, false);
  graph.assign(N, vector<int>());
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    graph[a].emplace_back(b);
    graph[b].emplace_back(a);
  }
  used[0] = true;
  cout << dfs(0, 0) << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define _ << ' ' <<
using namespace std;
using ll = long long;

const string z = "RGB";
ll a[4000][3];

int main()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = n - 1; i >= 0; --i)
        a[i][z.find(s[i])] = 1;
    for (int i = n - 2; i >= 0; --i)
        for (int j = 0; j < 3; ++j)
            a[i][j] += a[i + 1][j];

    ll sol = 0;
    for (int i = 0; i < n - 2; ++i)
    {
        for (int j = i + 1; j < n - 1; ++j)
        {
            if (s[j] == s[i]) continue;
            int t = 3 - z.find(s[i]) - z.find(s[j]);
            sol += a[j + 1][t];
            if (j + j - i < n && s[j + j - i] == z[t])
                sol--;
        }
    }
    cout << sol;
}


Measured memory_bytes: 3720
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>

using namespace std;


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

	int n, i, j, k;
	cin >> n;
	vector<int> h(n), dp(n, -1000000000);
	for (i = 0; i < n; i++) cin >> h[i];
	dp[0] = 0;
	for (i = 1; i < n; i++) {
		dp[i] = dp[i - 1] + abs(h[i] - h[i - 1]);
		if (i > 1) dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
	}

	cout << dp[n - 1] << "\n";
	

	return 0;
}




Measured memory_bytes: 1152
def getlooptime(warpmap, start='1'):
    warpmap_ = warpmap.copy()    
    counter = 0

    for _ in range(N):

        counter += 1

        nextmap = warpmap_[start]

        if type(nextmap) == int:
            return counter - 1, (counter - 1) - (nextmap - 1)
        
        warpmap_[start] = counter
        start = nextmap

def getterminal(warpmap, n, start):
    warpmap_ = warpmap.copy()

    if n == 0:
        return start
    else:
        for _ in range(1, n + 1):
            nextmap = warpmap_[start]
            start = nextmap

        return nextmap


N, K = map(int, input().split())
A = list(map(int, input().split()))

warpmap = {}

for town_num, to_warp in enumerate(A):
    
    town_num = town_num + 1
    warpmap[f"{town_num}"] = f"{to_warp}"

pasttime, looptime = getlooptime(warpmap=warpmap, start='1')

if K > pasttime:
    print(getterminal(warpmap=warpmap, n=(K - pasttime) % looptime, start=getterminal(warpmap=warpmap, n=pasttime, start='1')))
else:
    print(getterminal(warpmap=warpmap, n=K, start='1'))

Measured memory_bytes: 70372
#include<stdio.h>

int n,m,res;
char op;

int main() {
 while(true){
  scanf("%d %c %d",&n,&op,&m);
  if(op=='?')break;
  switch(op){
   case '+': res=n+m;break;
   case '-': res=n-m;break;
   case '*': res=n*m;break;
   case '/': res=n/m;break;
  }
  printf("%d\n",res);
 }
 return 0;
}

Measured memory_bytes: 1028
package main

import (
	"fmt"
)

func main() {
	var a, b int

	for {
		fmt.Scan(&a, &b)
		if a == 0 && b == 0 {
			return
		}
		if a > b {
			fmt.Printf("%d %d\n", b, a)
			continue
		}
		fmt.Printf("%d %d\n", a, b)
	}
}



Measured memory_bytes: 1232
#include <iostream>

using namespace std;


int gcd(int x, int y) {
  int mod = x % y;
  if(mod == 0) {
    return y;
  }
  return gcd(y, mod);
}

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

  long total = 0;
  for(int i = 1; i <= K; i++) {
    for(int j = 1; j <= K; j++) {
      for(int k = 1; k <= K; k++) {
        total += gcd(gcd(i, j), k);
      }
    }
  }

  cout << total;

  return 0;
}



Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
#define ALL(v) v.begin(), v.end()
#define vmax(v) *max_element(ALL(v))
#define vmin(v) *min_element(ALL(v))
#define chmax(x, a) x = max(x, a)
#define chmin(x, a) x = min(x, a)

int main() {
    int N; cin >> N;
    map<ll, ll> p, n;
    set<ll> ps, ns;
    ll tmp;
    rep(i, N) {
        cin >> tmp;
        p[i + tmp]++; ps.insert(i+tmp);
        n[i - tmp]++;
    }
    vector<ll> vecP(ALL(ps));
    ll ans = 0;
    rep(i, vecP.size()) {
        ans += p[vecP[i]] * n[vecP[i]];
    }
    cout << ans << endl;

}


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

int main() {
  int N, K, a=1;
  cin >> N >> K;
  for (int i = 0; i < N; i++){
    if (a > K){
    a += K;
    continue;
    }
    
    a *= 2;
  }
  cout << a << endl;
}

Measured memory_bytes: 3576
H=10800
D=H*8
d=[0]*D
c=0
for i in[0]*input():a,b=map(int,raw_input().split());c+=a;d[c%D]+=1;c+=b
d*=2
r=range(D+H)
for i in r:d[i+1]+=d[i]
print max(d[i+H]-d[i-1]for i in r)

Measured memory_bytes: 9460
n=int(input())
mod=10**9+7
arr = {}
def factorization(k):
    temp=k
    for i in range(2,int(-(-k**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp//=i
            if i in arr:
                arr[i]+=cnt
            else:
                arr[i]=cnt
    if temp!=1:
        if temp in arr:
                arr[temp]+=1
        else:
            arr[temp]=1
    if arr==[]:
        if k in arr:
                arr[k]+=1
        else:
            arr[k]=1
for i in range(1,n+1):
    factorization(i)
ans=1

for value in arr.values():
    ans*=(value+1)
    
# print(arr)
print(ans%mod)




# x=0
# k = ans
# for i in range(1,int(k**0.5)+1):
#     if k%i==0:
#         x+=1
#         if i!=n//i:
#             x+=1
# print(x%mod)




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

int main(void){
    int N,S,M;
    S=0;
    cin>>N;
    int p[N];
    cin>>p[0];
    M=p[0];

    for(int i=1;i<N;i++){
        cin>>p[i];
        if(M>=p[i]){
            S=S+p[i];
        }else{
            S=S+M;
            M=p[i];
            
        }
    }
    cout<< S+M/2 <<endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <cstdlib>
#include <stack>

using namespace std;

typedef long long LL;
#define FAST ios::sync_with_stdio(false);
const int MaxN = 105;

int main()
{
	int a,b;
	char c;
	cin >> a >> c >> b;
	if(c == '+')cout << a+b << endl;
	else cout << a - b << endl;
	return 0;
	}

Measured memory_bytes: 256
//### In The Name Of GOD ###

// %% Remember; (((He))) is The (((Accepter))) %%

#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;

#define int ll
#define pb push_back
#define bp pop_back
#define pf push_front
#define fp pop_front
#define X first
#define Y second
#define IO ios_base::sync_with_stdio(false);
#define sz(a) (int)(a.size())
#define sg(a, b) (a + b - 1) / b

const int MOD = 1000 * 1000 * 1000 + 7;
const int INF = 2 * 1000 * 1000 + 200;
const int MAXN = 100 * 1000 + 1;
const int MLOG = 18;
const int NMAX = 1 * 1000;

signed main(){
  IO;
  int n, x;
  cin >> n >> x;
  int a[n], ans = 0;
  cin >> a[0];
  if(a[0] > x) ans -= x - a[0], a[0] = x;
  // cout << ans;
  for(int i = 0; i < n - 1; i++){
    cin >> a[i + 1];
    if(a[i] + a[i + 1] > x)ans += a[i + 1] - x + a[i],a[i + 1] = x - a[i];
  }
  cout << ans;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main(){
  ll n ; cin>> n ;
  vector<ll> A(n) ; rep(i,n) cin>>A[i] ;
  map<ll,map<ll,ll>> mp ;
  rep(i,n){
    ll k= A[i] ;
    ll cnt = 0;
    while(k%2==0){
      k/=2 ;
      cnt++ ;
    }
    cnt-- ;
    mp[cnt][n-k]++ ; //大小逆に入れる
  }
  ll ans= 0;
  for( auto u : mp){
    ll plus=0 ;
    auto v= u.se ;
    for(auto t: v ){
      if(t.se<=0) continue ;
      ll x= n- (t.fi) ;
      ll base = 1ll ;
      while(base<= x){
        base*= 2 ;
      }
       if(x==1){
         plus = (t.se)/2 ;
       }
       else{
         plus = min(v[n-(base-x)],t.se) ;
       }
       ans+= plus ;
       v[n-(base-x)]-= plus ;
       
    }
  }
  cout<<ans<<endl ;
 return 0 ; 
}



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

int main(void) {
    int N;cin>>N;
    double result = 0.0;
    for (int i = 0; i < N; i++) {
        double x;
        string u;
        cin>>x>>u;
        if (u == "JPY") result += x;
        else result += x * 380000.0;
   }
    printf("%.6f\n", result);
    return 0;
}

Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100010;
ll L[maxn];
int n,m,k;
vector<pair<int,int> >edge[maxn];

void dfs(int u,int v,ll sum)
{
    L[u]=sum;
    for(int i=0;i<edge[u].size();i++)
    {
        if(edge[u][i].first==v)continue;
        dfs(edge[u][i].first,u,sum+1LL*edge[u][i].second);
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[a].push_back(make_pair(b,c));
        edge[b].push_back(make_pair(a,c));
    }
    cin>>m>>k;
    dfs(k,-1,0LL);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        cout<<L[a]+L[b]<<endl;
    }
}







Measured memory_bytes: 14336
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<stdlib.h>
#define MIN(a,b) a>b?b:a
int main() {
	int n,m,i,j,min,cnt,nn;
	int *C, *T;
	scanf("%d%d", &n, &m);
	n += 1;
	min = n;
	C = (int*)malloc(sizeof(int)*m);
	T = (int*)calloc(n*m,sizeof(int));
	for (i = 0; i < m; i++) scanf("%d", C + i);
	for (j = 0; j < n; j++) T[j] = j;
	
	for (i = 1; i < m; i++) {
		for (j = 0; j < n; j++) {
			if(j<C[i]) T[n*i + j] = T[n*(i - 1) + j];
			else T[n*i + j] = MIN(T[n*(i-1)+j],T[(n*i)+j-C[i]]+1);
		}
	}
	for (i = 1,j=0; i <=m; i++,j++) if (min > T[(n-1)*i+j])min = T[(n-1)*i+(j)];
	//for (i = 0; i < m*n; i++) { printf("%2d ", T[i]); if ((i+1)%n == 0&&i!=0)puts(""); }
	printf("%d\n", min);
	free(C); free(T);
	return 0;
}

Measured memory_bytes: 4256
from collections import defaultdict

def check(a, pre):
    ans = 0
    while a % 2 == 0:
        ans += 1
        a //= 2
        if ans == pre:
            break
    return ans


def main():
    num = int(input())
    data = list(map(int, input().split()))

    ans = check(data[0], 10 ** 10)
    for i in range(1, num):
        ans = min(ans, check(data[i], ans))
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38512
#include <iostream> 
#include <algorithm>
using namespace std;
long long gcd(long long x, long long y)
{
	long long c;
	long long m = x, n = y;
	while (y != 0)
	{
		c = x%y;
		x = y;
		y = c;
	}
	return m / x*n;
}
int main()

{
	int n;
	int i;
	while (cin >> n)
	{
		long long m, s, l;
		cin >> m;
		if (n == 1)
			cout << m << endl;
		else if (n > 1)
		{
			cin >> l;
			s = gcd(l, m);
			for (i = 0; i < n - 2; i++)
			{
				cin >> m;
				s = gcd(s, m);
			}
			cout << s << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  LL N;
  cin >> N;
  if (N == 0) {
    cout << 0;
    return 0;
  }
  string ans = "";
  while (N != 0) {
    if (N % 2 == 0) {
      ans = "0" + ans;
    } else{
      ans = "1" + ans;
      --N;
    }
    N /= (-2);
  }
  cout << ans << endl;

  return 0;
}


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

int w,h;
int field[51][51];
void dfs(int x,int y);

int main(){
	while(cin>>w>>h&&w!=0&&h!=0){
		for(int y=0;y<h;y++){
			for(int x=0;x<w;x++){
				cin>>field[y][x];
			}
		}
		int count=0;
		for(int y=0;y<h;y++){
			for(int x=0;x<w;x++){
				if(field[y][x]==1){
					dfs(x,y);
					count++;
				}
			}
		}
		cout<<count<<endl;
	}

}

void dfs(int x,int y){
	field[y][x]=-1;
	for(int i=-1;i<=1;i++){
		for(int j=-1;j<=1;j++){
			int mx=x+i;
			int my=y+j;

			if(mx<0||my<0||mx>=w||my>=h)continue;
			if(field[my][mx]==1){
				dfs(mx,my);
			}
		}
	}
}

Measured memory_bytes: 3272
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <bits/stdc++.h>

using namespace std;

int main()
{
#ifdef _MSC_VER
	freopen("f.in", "r", stdin);
#endif
	std::ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n * 3);
	for (int i = 0; i < n * 3; i++) {
		cin >> a[i];
		--a[i];
	}
	vector<vector<int>> f(n, vector<int>(n, -1000000));
	int offset = 0;
	vector<pair<pair<int, int>, int>> updates;
	int opt = 0;
	vector<int> local(n, -1000000);
	f[a[0]][a[1]] = f[a[1]][a[0]] = 0;
	local[a[0]] = local[a[1]] = 0;
	for (int index = 2; index + 2 < n * 3; index += 3) {
		vector<int> b(3);
		for (int k = 0; k < 3; k++) {
			b[k] = a[index + k];
		}
		if (b[0] == b[1] && b[0] == b[2]) {
			++offset;
			continue;
		}
		updates.clear();
		for (int i = 0; i < 3; i++) {
			for (int j = i + 1; j < 3; j++) {
				int k = 3 - i - j;
				updates.push_back(make_pair(make_pair(b[i], b[j]), opt));
				updates.push_back(make_pair(make_pair(b[i], b[j]), f[b[k]][b[k]] + 1));
			}
		}
		for (int i = 0; i < 3; i++) {
			int j = (i + 1) % 3;
			int k = (j + 1) % 3;
			for (int x = 0; x < n; x++) {
				updates.push_back(make_pair(make_pair(b[i], x), local[x]));
				if (b[j] == b[k]) {
					updates.push_back(make_pair(make_pair(b[i], x), f[x][b[j]] + 1));
				}
			}
		}
		for (const auto& update : updates) {
			int x = update.first.first;
			int y = update.first.second;
			int val = update.second;
			if (val > f[x][y]) {
				f[x][y] = f[y][x] = val;
				opt = max(opt, val);
				local[x] = max(local[x], val);
				local[y] = max(local[y], val);
			}
		}
	}
	opt = max(opt, f[a.back()][a.back()] + 1);
	int ret = opt + offset;
	cout << ret << endl;
	return 0;
}


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

int main()
{


    int k;
    cin>>k;
    string s;
    cin>>s;

    if(s.length()>k)
    {
        for(int i=0; i<k; i++)
        {
            cout << s[i];
        }
        cout << "...";
    }
    else cout << s << endl;



    return 0;
}





Measured memory_bytes: 3588
// tzl ak IOI! 

#include<bits/stdc++.h>

#define HEAP priority_queue
#define rep(i, n) for(int i = 0, _end_ = (n); i < _end_; ++i)
#define per(i, n) for(int i = (n) - 1; i >= 0 ; --i)
#define forn(i, l, r) for(int i = (l), _end_ = (r); i <= _end_; ++i)
#define nrof(i, r, l) for(int i = (r), _end_ = (l); i >= _end_; --i)
#define FOR(a, b) for(auto (a): (b))
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define X first
#define Y second
#define eps 1e-6
#define pi 3.1415926535897932384626433832795
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
#define FILL(a, b) memset((a), (b), sizeof((a)))
#define MCPY(a, b) memcpy((a), (b), sizeof((b)))

using namespace std;

typedef long long LL;
typedef double flt;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef pair<int,int> pii;
typedef pair<int,LL> pil;
typedef pair<LL,int> pli;
typedef pair<LL,LL> pll;
typedef vector<pil> vil;
typedef vector<pii> vii;
typedef vector<pli> vli;
typedef vector<pll> vll;

const int iinf = 1e9 + 7;
const LL linf = 1ll << 60;
const flt dinf = 1e60;

template <typename T>
inline void scf(T &x)
{
	bool f = 0; x = 0; char c = getchar();
	while((c < '0' || c > '9') && c != '-') c = getchar();
	if(c == '-') { f = 1; c = getchar(); }
	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	if(f) x = -x; return;
}

template <typename T1, typename T2>
void scf(T1 &x, T2 &y) { scf(x); return scf(y); }

template <typename T1, typename T2, typename T3>
void scf(T1 &x, T2 &y, T3 &z) { scf(x); scf(y); return scf(z); }

template <typename T1, typename T2, typename T3, typename T4>
void scf(T1 &x, T2 &y, T3 &z, T4 &w) { scf(x); scf(y); scf(z); return scf(w); }

inline char mygetchar(){ char c = getchar(); while(c == ' ' || c == '\n') c = getchar(); return c; }

template <typename T>
void chkmax(T &x, const T &y){ if(y > x) x = y; return; }

template <typename T>
void chkmin(T &x, const T &y){ if(y < x) x = y; return; }

#ifdef ONLINE_JUDGE
#define debug(x,c) ;
#else
#define DEBUG
#define debug(x,c) cerr<<#x<<"="<<x<<c;
#endif

void TZL();

void RANK1();

#define tzl int
#define ak main
#define IOI ()
tzl ak IOI
{
#undef tzl
#undef ak
#undef IOI

	TZL();
	RANK1();

#define tzl return
#define caisi 0
#define myy ;
	tzl caisi myy
#undef tzl
#undef caisi
#undef myy
}

//---------------------------head----------------------------

const int N = 1e5 + 100;

int n;
vi g[N];
bool f[N];

void TZL()
{
	scf(n);
	rep(i, n - 1)
	{
		int u, v; scf(u, v);
		g[u].pb(v); g[v].pb(u);
	}
	return;
}

void dfs(int u, int fa = 0)
{
	int cnt = 0;
	for(int v: g[u]) if(v != fa)
	{
		dfs(v, u);
		cnt += (f[v]);
	}

	if(cnt > 1)
	{
		puts("First");
		exit(0);
	}
	f[u] = cnt ? 0 : 1;
	return;
}

void RANK1()
{
	if(n == 2)
	{
		puts("Second");
		return;
	}

	forn(i, 1, n) if(SZ(g[i]) > 1)
	{
		dfs(i);
		puts(f[i] ? "First" : "Second");
		return;
	}
}

Measured memory_bytes: 5888
chg={"A":0,"B":1,"C":2}
chg2=[i for i in "ABC"]
cup=[False]*3
cup[0]=True
while True:
    try:
        a,b=input().split(",")
    except:
        break
    cup[chg[a]],cup[chg[b]]=cup[chg[b]],cup[chg[a]]
print(chg2[cup.index(True)])

Measured memory_bytes: 7508
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		int A = int.Parse(str[0]);
		int B = int.Parse(str[1]);
		int h = 100;
		int w = 100;
		int[,]X = new int[h,w];
		Console.WriteLine(h + " " + w);
		for(var i=h/2;i<h;i++){
			for(var j=0;j<w;j++){
				X[i,j] = 1;
			}
		}
		A -= 1;
		B -= 1;
		int ix = h/2+1;
		int iy = 1;
		while(A>0){
			X[ix,iy] = 0;
			A -= 1;
			iy += 2;
			if(iy >= w){
				iy -= w;
				ix += 2;
			}
		}
		ix = 1;
		iy = 1;
		while(B>0){
			X[ix,iy] = 1;
			B -= 1;
			iy += 2;
			if(iy >= w){
				iy -= w;
				ix += 2;
			}
		}
		for(var i=0;i<h;i++){
			string stra = "";
			for(var j=0;j<w;j++){
				if(X[i,j] == 1){
					stra += "#";
				} else {
					stra += ".";
				}
			}
			Console.WriteLine(stra);
		}
	}
}

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

int main(void){
    int n;
    cin >> n;
    vector<int> v((int)1e5, 0);
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        v.at(a)++;
    }
    int ans = 0;
    for(int i=0; i<(int)1e5; i++){
        int cnt = v.at(i);
        if(i > 0){
            cnt += v.at(i-1);
        }
        if(i<(int)1e5-1){
            cnt += v.at(i+1);
        }
        ans = max(ans,cnt);
    }

    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		ans += b - a + 1;
	}
	cout << ans << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(a)  (a).begin(),(a).end()
typedef long long ll;
ll mod=1000000007;

int main() {
  int x,a ;cin >>x>>a;
  if(x>=a) {
    cout << 10 << endl;
  } else {
    cout << 0 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	static Scanner sc = new Scanner(System.in);
	static int[] a, b;
	public static void main(String[] args) {
		while(read()){
			solve();
		}
	}
	static boolean read(){
		if(!sc.hasNext())return false;
		a = new int[4];
		b = new int[4];
		for(int i = 0; i < a.length; i++)a[i] = sc.nextInt();
		for(int j = 0; j < b.length; j++)b[j] = sc.nextInt();
		return true;
	}
	static void solve(){
		int hit = 0, blow = 0, check = 0;
		for(int i = 0; i < a.length; i++){
			for(int j = 0; j < b.length; j++){
				if(a[i] == b[i]){
					hit++;
					check = i;
					break;
				}
				if(a[i] == b[j])blow++;
			}
		}
		System.out.println(hit + " " +blow);
	}
}

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

#define int long long
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define endl "\n"
#define printarr(arr, n) for(int i = 0; i < n; i++) cout << arr[i] << " "; cout << endl;
#define pii pair<int,int>
#define mp(x, y) make_pair(x, y)
#define debug(x) cout << "#debug " << x << endl;
#define print2D(arr, n) cout << "\n_____________________\n";  for(int i = 1; i  <= n; i++){	for(int j = 1; j <= n; j++){cout << arr[i][j] << " ";}cout << endl;}cout << "\n_____________________\n";
#define mii map<int,int>
#define printmap(mm) for(map<int,int>::iterator itr = mm.begin(); itr!=mm.end(); itr++) cout << itr->first << "->" << itr->second << " "; cout << endl;
#define iterm(mm) for(map<int,int>::iterator itr = mm.begin(); itr!=mm.end(); itr++)
#define NO cout << "NO"; return 0;
#define MO 1000000007
#define N 100100
#define MX 2000000000

void preprocess(){
	
}

signed main(){
	FAST_IO;
	#ifndef ONLINE_JUDGE
	//freopen("/home/divakar/programs/input.txt","r",stdin);
	//freopen("/home/divakar/programs/output.txt","w",stdout);
	#endif
	clock_t clk = clock();

	preprocess();
	int t=1;
	//cout << " dsf ";
	//cin >> t; 
	while(t--){

		int n, x;
		cin >> n >> x;
		int w[n], v[n];
		for (int i = 0; i < n; ++i)
		{
			cin >> w[i] >> v[i];
		}

		int dp[n][N];

		memset(dp,0,sizeof(dp));

		for (int i = w[0]; i < N; ++i)
		{
			dp[0][i] = v[0];
		}

		for (int i = 1; i < n; ++i)
		{
			for (int j = 0; j < w[i]; ++j)
			{
				dp[i][j] = dp[i-1][j];
			}

			for (int j = w[i]; j < N; ++j)
			{
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
			}
		}

		cout << dp[n-1][x] << endl;







        
		//cout << "ENDOFTEST "<< t << "\n";
	}









	// #ifndef ONLINE_JUDGE
	// clk = clock() - clk;
	// cout << "Time Elapsed: " << fixed << setprecision(10) << ((long double)clk)/CLOCKS_PER_SEC << "\n";
	// #endif
	return 0;
}






















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

int main() {
int n;
cin>>n;
string s1 = "hon",s2 =  "pon", s3 = "bon";
int x = n%10;
 if(x==2 || x==4 || x==5 || x==7 || x==9){
 	cout<<s1;
 }else if(x==0 || x==1 || x==6 || x==8){
 	cout<<s2;
 	
 }else{
 	cout<<s3;
 }
return 0;
}

Measured memory_bytes: 3620
#include <iostream>

using namespace std;

int main(int argc, const char *argv[]) {
  int N, a;
  cin >> N;

  for(int i = 0; i< 10; i++){
    a = i * 100 + i * 10 + i;
    if(N <= a){
      cout << a << endl;
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;
int main()
{
    int a;
    int count = 1;
    while(1){
        cin >> a;
        if(a != 0){
          printf("Case %d: %d\n",count,a);
          count ++;
        } 
        else break;


    }







    return 0;
}


Measured memory_bytes: 3128
#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <stack>
#include <unordered_map>
#include <utility>
#include <vector>

// Aliases
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

using std::cout;
using std::cerr;
using std::cin;
using std::endl;
using std::string;
using std::vector;

template <class T = i64>
vector<T> read_vector(const u64 n)
{
    vector<T> vec;
    vec.reserve(n);
    for (u64 i = 0; i < n; i++)
    {
        T v;
        cin >> v;
        vec.emplace_back(v);
    }

    return vec;
}

int main()
{
    u32 n;
    cin >> n;
    auto vec = read_vector<u32>(n);
    u32 sum = 0;
    for (u32 i = 0; i < n; i++)
    {
        for (u32 j = i + 1; j < n; j++)
        {
            sum += vec[i] * vec[j];
        }
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

using namespace std;
struct Rule {
	bool rightAssoc;
	string operators;
};
vector<Rule> g_rules;

struct Node {
	char op;
	Node *left, *right;
	Node(char o, Node *l = NULL, Node *r = NULL) :
		op(o), left(l), right(r)
	{ }
};

struct Result {
	int p;
	Node *v;
};

Result expr(int depth, const string &s, int p);
Result factor(const string &s, int p);
Result var(const string &s, int p);

Result expr(int depth, const string &s, int p){
	if(depth == g_rules.size()){ return factor(s, p); }
	Rule &rule = g_rules[depth];
	Result r = expr(depth + 1, s, p);
	Node *rmost = NULL;
	bool first = true;
	while(rule.operators.find(s[r.p]) != string::npos){
		Result q = expr(depth + 1, s, r.p + 1);
		if(rule.rightAssoc && first){
			Node *node = new Node(s[r.p], r.v, q.v);
			r.v = rmost = node;
			first = false;
		}else if(rule.rightAssoc){
			Node *node = new Node(s[r.p], rmost->right, q.v);
			rmost->right = node;
			rmost = rmost->right;
		}else{
			r.v = new Node(s[r.p], r.v, q.v);
		}
		r.p = q.p;
	}
	return r;
}
Result factor(const string &s, int p){
	Result r;
	if(s[p] == '('){
		r = expr(0, s, ++p);
		++r.p;
	}else{
		r = var(s, p);
	}
	return r;
}
Result var(const string &s, int p){
	Result r;
	r.v = new Node(s[p++]);
	r.p = p;
	return r;
}

void recur(Node *node){
	if(islower(node->op)){
		cout << node->op;
	}else{
		cout << "(";
		recur(node->left);
		cout << node->op;
		recur(node->right);
		cout << ")";
	}
	delete node;
}

int main(){
	int T;
	cin >> T;
	while(T--){
		int G;
		cin >> G;
		g_rules = vector<Rule>(G);
		for(int i = 0; i < G; ++i){
			string assoc, op;
			cin >> assoc;
			g_rules[i].rightAssoc = (assoc == "R");
			int opnum;
			cin >> opnum;
			while(opnum--){
				cin >> op;
				g_rules[i].operators.push_back(op[0]);
			}
		}
		int N;
		cin >> N;
		while(N--){
			string input;
			cin >> input;
			Result r = expr(0, input, 0);
			recur(r.v);
			cout << endl;
		}
		if(T != 0){ cout << endl; }
	}
	return 0;
}

Measured memory_bytes: 932
function Main(input) {
	var inputInt = parseInt(input, 10);
	var count = 0;
  	var max = parseInt('1000000000', 4);
    for(var i = 0; i <= max; i++) {
      var num4 = i.toString(4);
      if (num4.indexOf('0') >= 0 ) {
        continue;
      }
      num4 = num4.replace(/3/g, '7').replace(/2/g, '5').replace(/1/g, '3')
      if (parseInt(num4, 10) > inputInt) {
        break;
      }
      var a7 = num4.indexOf('7');
      var a5 = num4.indexOf('5');
      var a3 = num4.indexOf('3');
      if (a7 >= 0 && a5 >= 0 && a3 >= 0) {
      	count++;
      }
    }
    console.log(count);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 10400