akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <limits>
#include <ios>
#include <iomanip>
using namespace std;

#define rep(i,N) for(int i=0; i<N; i++)
#define revrep(i,N) for(int i=N-1; i>=0; i--)

typedef long long ll;

int main(void)
{
    string s,t;
    cin >> s >> t;

    int dp[s.size()][t.size()];

    rep(i,s.size()){
        rep(j,t.size()){
            if (i == 0 && j == 0) {
                if (s[i] == t[j]){
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = 0;
                }
            } else if (i == 0 && j != 0) {
                if (s[i] == t[j]){
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            } else if (i != 0 && j == 0) {
                if (s[i] == t[j]){
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            } else {
                if (s[i] == t[j]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }

            /*{
                rep(x,i+1){
                    rep(y, j+1){
                        cout << right << setw(2) << dp[x][y] << ",";
                    }
                    cout << endl;
                }
                cout << "------" << endl;
            }*/
        }
    }
    string ans = "";
    int i = s.size()-1;
    int j = t.size()-1;
    while(true){
        if (i > 0 && dp[i-1][j] == dp[i][j]) {
            i--;
            continue;
        } else if (j > 0 && dp[i][j] == dp[i][j-1]) {
            j--;
            continue;
        } else if (i == 0 && j == 0){
            if (dp[i][j] == 1) {
                ans = s[i] + ans;
            }
            break;
        } else {
            //cout << i << "," << j << ":" << ans << endl;
            ans = s[i] + ans;
            if(i>0)i--; 
            if(j>0)j--;
        }
    }

    cout << ans << endl;

}


Measured memory_bytes: 35456
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
struct Edge {
	int to, nxt;
} edge[2 * maxn];
int tot, head[maxn], n, color[maxn];
void init() {
	tot = 0;
	memset(head, -1, sizeof head);
}
void add(int u, int v) {
	edge[tot].to = v;
	edge[tot].nxt = head[u];
	head[u] = tot++;
}
int ppp;
bool dfs(int x, int y, int z) {
	if (y == n) {
		ppp = z - 1;
		return 1;
	}
	for (int i = head[y]; i != -1; i = edge[i].nxt) {
		if (edge[i].to != x) {
			if (dfs(y, edge[i].to, z + 1)) {
				if (y != 1)
				if (z <= (ppp + 1) / 2) {
					color[y] = 0;
				} else {
					color[y] = 1;
				}
				return 1;
			}
		}
	}
	return 0;
} 
void work(int x) {
	for (int i = head[x]; i != -1; i = edge[i].nxt) {
		int y = edge[i].to;
		if (color[y] == -1) {
			color[y] = color[x];
			work(y);
		}
	}
}
int main()
{
	int x, y;
	
	scanf("%d", &n);
	init();
	memset(color, -1, sizeof color);
	color[1] = 0, color[n] = 1;
	for (int i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
	dfs(1, 1, 0);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (color[i] != -1) {
			work(i);
		}
	}
	for (int i = 1; i <= n; i++) {
		ans += color[i];
		//printf("%d ", color[i]);
	}
	puts(n > 2 * ans ? "Fennec" : "Snuke");
}

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

#define ll long long
#define mp make_pair
#define rep(i, a, b) for(int i = (a);i <= (b);i++)
#define per(i, a, b) for(int i = (a);i >= (b);i--)

using namespace std;

typedef pair<int, int> pii;
typedef double db;
const ll mod = 1e9 + 7;
const int N = 1e6 + 50;
ll n, m, a[N], l = 0; 
ll p[N], ans = 1;
inline ll read(){
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1; ch = getchar();}
	while(ch >='0' && ch <='9'){x = (x<<3)+(x<<1)+(ch^48); ch = getchar();}
	return x*f;
}
ll pow(ll a, ll b){
	ll res = 1;
	while(b){
		if(b & 1) res = res*a%mod;
		a = a*a%mod;
		b >>= 1; 
	}
	return res;
} 
int main(){
//	freopen("input.in","r",stdin);
//	freopen("output.out","w",stdout);
	n = read(); m = read();
	p[0] = 1; p[1] = 1;
	rep(i, 1, 1<<17) p[i] = p[i-1]*i%mod; 
	ll u = m;
	for(int i = 2;i*i <= m;i++){
		if(m%i == 0){
			ll sum = 0;
			while(m%i == 0){
				a[++l] = i; m /= i;
				sum++;
			} 
			ans = ans * p[n+sum-1]%mod * pow(p[n-1], mod-2)%mod * pow(p[sum], mod-2)%mod; 
		}
	}
	if(m>1) ans = ans*n%mod;
	printf("%lld\n", ans);
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    string s;
    getline(cin,s);
    
    for(int i=0;i<s.size();i++){
        if('a'<=s[i] && s[i]<='z') s[i]='A'+(s[i]-'a');
        else if('A'<=s[i] && s[i]<='Z') s[i]='a'+(s[i]-'A');
    }

    cout << s << endl;
    
    return 0;
}


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

class Dice{
public:
    Dice(){
        number = new int[6];
        work = new int[6];
    };
    ~Dice(){
        delete[] number;
        delete[] work;
    };
    void SetLabel(int index,int num){
        number[index]=num;
    };
    void roll(char dst){
		for(int i = 0; i < 6; i++) work[i] = number[i];
		switch(dst){
		case 'E':
			SetNumber(work[3],work[1],work[0],work[5],work[4],work[2]);
			break;
		case 'N':
			SetNumber(work[1],work[5],work[2],work[3],work[0],work[4]);
			break;
		case 'S':
			SetNumber(work[4],work[0],work[2],work[3],work[5],work[1]);
			break;
		case 'W':
			SetNumber(work[2],work[1],work[5],work[0],work[4],work[3]);
			break;
		}
	};
    int returnPeek(){
        return number[0];
    };

private:
    void SetNumber(int n0,int n1,int n2,int n3,int n4,int n5){
        number[0]=n0;
        number[1]=n1;
        number[2]=n2;
        number[3]=n3;
        number[4]=n4;
        number[5]=n5;
    }

private:
    int* number;
    int* work;
};

int main(){
    Dice dice;
    int label;
    char ch;
    for(int i=0;i<6;i++){
        scanf("%d",&label);
        dice.SetLabel(i,label);
    }
    getchar();
    while((ch =getchar())!='\n'){
        dice.roll(ch);
    }
    printf("%d\n",dice.returnPeek());
}


Measured memory_bytes: 3216
#include <stdio.h>

int main(void) {
	int result_kosuu;
	int result_num[100];
	long long id;
	long long result;
	int minus;
	int agari;
	int i;
	while(1) {
		scanf("%lld",&id);
		if(id==0)break;
		if(id<0) {
			minus=1;
			id=-id;
		} else minus=0;
		agari=0;
		result_kosuu=0;
		while(id>0) {
			if(minus) {
				if(id%10!=0) {
					result_num[result_kosuu++]=10-id%10;
					agari=1;
				} else {
					result_num[result_kosuu++]=0;
					agari=0;
				}
			} else {
				result_num[result_kosuu++]=id%10;
				agari=0;
			}
			id/=10;
			id+=agari;
			minus=!minus;
		}
		for(i=result_kosuu-1,result=0;i>=0;i--) {
			result=result*10+result_num[i];
		}
		printf("%lld\n",result);
	}
	return 0;
}

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

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 100100;
bool is[N];
int kol[N];
int n;

int main () {
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	cin >> n;
	memset(is, 0, sizeof(is));
	memset(kol, 0, sizeof(kol));
	forn(i, n)
		kol[i] = 1;
	int m;
	cin >> m;
	is[0] = 1;
	forn(i, m) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		if (is[u]) {
			is[v] = 1;
		}
		if (kol[u] == 1) {
			is[u] = 0;
		}
		kol[u]--, kol[v]++;
	}
	int ans = 0;
	forn(i,  n)
		ans += is[i];
	cout << ans << endl;
	return 0;
}


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

using namespace std;

template<typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T> p) {
    out << "(" << p.first << "," << p.second << ")";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for (auto a: v)
        out << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename S, typename T>
ostream& operator<<(ostream& out, const map<S, T>& M) {
    for (auto m: M)
        cout << "(" << m.first << "->" << m.second << ") ";
    return out;
}

template<typename S, typename T>
pair<S, T> operator+(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

template<typename S, typename T>
pair<S, T> operator-(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

long  long gcd(long long a, long long  b) {
    if (!b)
        return a;
    return gcd(b, a % b);
}

long long solve() {
    long long  a, b;
    cin >> a >> b;
    return a / gcd(a, b) * b;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    long long ans = solve();
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define reps(i,n) for (int i=1;i<=(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rreps(i,n) for (int i=(n);i>0;i--)
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>
template<class T> inline bool chmin(T &a, T b) {if (a>b) {a = b; return 1;} return 0;};
template<class T> inline bool chmax(T &a, T b) {if (a<b) {a = b; return 1;} return 0;};
typedef long long int ll;
const long long INF = 1LL << 60;

int main(){
  int N, M; cin >> N >> M;
  pii e[M];
  vector<vector<int>> G(N);
  rep(i,M){
    int a, b; cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
    e[i] = {a,b};
  }


  int cnt = 0;
  rep(i,M){
    queue<int> q;
    q.push(0);
    bool connected[N] = {};
    while (!q.empty()){
      int v = q.front(); q.pop();
      connected[v] = true;
      for (int next_v : G[v]){
        if ((e[i].first==v && e[i].second==next_v) || (e[i].first==next_v && e[i].second==v)) continue;
        if (connected[next_v]) continue;
        q.push(next_v);
      }
    }

    rep(i,N) {
      if (connected[i]==0) {
        cnt++;
        break;
      }
    }
  }

  cout << cnt << endl;

  
  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e3 + 11;
const int mod = 1e9 + 7;
int head[N], nex[N<<1], to[N<<1],  size;
int fa[N], n, m;
LL X;
LL wei[N<<1], mi[N], t[N];
struct edge{
	int u, v;
	LL w;
}e[N];
bool cmp(edge a, edge b){
	return a.w < b.w;
}
int find(int x){
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void add(int x, int y, int z){
	to[++size] = y, nex[size] = head[x], head[x] = size, wei[size] = z;
}
LL dfs(int u, int ed, int fa){
	for(int i = head[u];i;i = nex[i]){
		int v = to[i];
		if(v == fa)continue;
		if(v == ed)return wei[i];
		LL res = dfs(v, ed, u);
		if(res != -1)return max(res, wei[i]);
	}
	return -1;
}
int main(){
	cin>>n>>m>>X;
	mi[0] = 1;
	for(int i = 1;i <= m; i++){
		scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].w);
		mi[i] = (mi[i-1] << 1) % mod;
	}
	sort(e + 1, e + 1 + m, cmp);
	for(int i = 1;i <= n; i++)fa[i] = i;
	LL mn = 0, ans = 0;
	for(int i = 1;i <= m; i++){
		int u = e[i].u, v = e[i].v, w = e[i].w;
		int fu = find(u), fv = find(v);
		if(fu == fv){
//			int res = dfs(u, v, fa)
			t[i] = w - dfs(u, v, u);
		}
		else{
			fa[fu] = fv;
			t[i] = -1;
			mn += w;
			add(u, v, w); add(v, u, w);
		}
	}
//	printf("mn=%lld\n", mn);
	if(X < mn){
		return puts("0"), 0;
	}
	if(mn == X)ans = 1LL * (mi[n-1] - 2) * mi[m-n+1] % mod;
	int cnt1 = 0, cnt2 = 0;
	for(int i = 1;i <= m; i++){
		if(t[i] == -1)continue;
		if(mn + t[i] == X)cnt1++;
		if(mn + t[i] > X)cnt2++;
//		printf("i=%d t=%d\n", i, t[i]);
	}
//	printf("cnt1=%d cnt2=%d\n", cnt1, cnt2);
	ans = (ans + 2LL * (mi[cnt1] - 1) % mod * mi[cnt2] % mod) % mod;
	cout<<ans<<endl;
	return 0;
}

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

int main(){
    int n,k;
    double p;
    cin >> n >> k;
    vector<double> v(n+1,0);
    double sofar = 0;
    for(int i =1;i<=n;i++){
		cin >> p;
		sofar+=(p+1)/2;
		v[i] = sofar;
	}
	//for(auto x: v) cout << x << " ";
	cout << endl;
	double maxi=0;
	for(int i = 0;i<n-k+1;i++){
		//cout << i - (n-1) << endl;
		maxi = max(maxi, v[i+k] - v[i]);
	}
    cout << setprecision(10) << maxi;
    
}


Measured memory_bytes: 1792
N = int(input())
P = list(map(int, input().split(' ')))

cnt = 0
for n in range(0, N-2, 1):
  p1 = P[n]
  p2 = P[n+1]
  p3 = P[n+2]
  min_p = min(p1,p2,p3)
  max_p = max(p1,p2,p3)
  if (min_p != p2) and (max_p != p2):
    cnt += 1

print(cnt)

Measured memory_bytes: 3064
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, w = LI()
wv = LIR(n)
weight = [wv[i][0] for i in range(n)]
value = [wv[i][1] for i in range(n)]
# dp[i][j] : 重さ制限 j 、品物 i までを選べる状態での価値の最大値
dp = [[0] * (w + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(w + 1):
        if j - weight[i] >= 0:  # 品物 i が選べるかどうか
            dp[i + 1][j] = max(
                dp[i][j],  # 選ばない
                dp[i][j - weight[i]] + value[i]  # 選ぶ
            )
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][w])


Measured memory_bytes: 149616
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <map>
#include <cassert>
using namespace std;
using VI = vector<int>;

int four;
int two;
int odd;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a % 4 == 0) four++;
        else if (a % 2 == 0) two++;
    }
    odd = n - four - two;
    
    if (two == 0) {
        if (odd <= four + 1) {
            cout << "Yes" << endl;
            return 0;
        }
        cout << "No" << endl;
        return 0;
    }
    
    if (odd <= four) {
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
walist = [0]*n
aclist = [0]*n

for i in range(m):
  p,s = input().split()
  if s == 'AC':
    aclist[int(p)-1] = 1
  elif s == 'WA' and aclist[int(p)-1] == 0:
    walist[int(p)-1] += 1 
    
for i in range(n):
  if aclist[i] == 0:
    walist[i] = 0
    
print(sum(aclist),sum(walist))

Measured memory_bytes: 4596
package main

import (
	"fmt"
)


func main() {
	var a, b int
	fmt.Scan(&a,&b)
	
	ans := b
	
	if a>=6 && a<13 {
		ans=b/2 
	} else if a<6 {
		ans=0
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
// ナップサック問題

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct Goods {int value, weight;};

int main() {
    int N, W;
    while(cin >> N >> W) {
        vector<Goods> goods(N);
        for(auto& g: goods) cin >> g.value >> g.weight;

        vector<int> dp(W + 1, 0);
        for(const auto& g: goods)
//             for(int w = W; w - g.weight >= 0; --w) dp[w] = max(dp[w], dp[w - g.weight] + g.value);
            for(int w = g.weight; w <= W; ++w) dp[w] = max(dp[w], dp[w - g.weight] + g.value);

        cout << *max_element(dp.begin(), dp.end()) << endl;
    }
}

Measured memory_bytes: 1232
def p_e():
    n = int(input())
    *A, = map(int, input().split())
    mod = 1000000007
    dp = [0] * 3
    ans = 1
    for a in A:
        num = 0
        flg = True
        # print(dp)
        for j in range(3):
            if dp[j] == a:
                if flg:
                    dp[j] += 1
                    flg = False
                num += 1
        ans *= num
        ans %= mod

    print(ans)
    
p_e()

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

#define LL long long int 
#define ii pair<int, int>
#define x first
#define y second
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<ii>
#define mp make_pair
#define pb push_back
#define INF int(1e9)
#define MOD 1000000007
#define TAM int(2e5)

using namespace std;

int main () {
    ios_base::sync_with_stdio(false);

    int n;
    
    cin >> n;

    vi arr(n), counter(n);

    for(int i=0; i<n-1; i++) {
        cin >> arr[i];
        arr[i]--;
        counter[arr[i]]++;
    }

    for(int i : counter) cout << i << endl;


    return 0;
}

Measured memory_bytes: 4840
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
const int Nmax=200010;

int main() {
	int N;
	int A,B;
	cin >> N >> A >> B;
	if(abs(A-B)%2 == 0) cout << "Alice" << endl;
	else cout << "Borys" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>

using namespace std;

class Status{
public:
  int wx, wy, cx, cy;
  int cost;
};

int w, h;
int tx, ty;
int gx, gy;
char data[7][7];
bool vis[7][7];
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
int rdx[]={0, -1, 0, 1};
int rdy[]={1, 0, -1, 0};
int bfs(Status);
bool dfs(int, int);
main(){
  while(1){
    cin >> w >> h;
    if(w==0 && h==0) break;
    Status tmp;
    tmp.cost=0;
    for(int i=0;i<h;i++){
      for(int j=0;j<w;j++){
	cin >> data[i][j];
	if(data[i][j]=='2'){
	  data[i][j]='0';
	  tmp.cx=j;
	  tmp.cy=i;
	}
	if(data[i][j]=='4'){
	  data[i][j]='0';
	  tmp.wx=j;
	  tmp.wy=i;
	}
	if(data[i][j]=='3'){
	  gx=j;
	  gy=i;
	  data[i][j]='0';
	}
      }
    }

    cout << bfs(tmp) << endl;
  }
  return 0;
}

int bfs(Status in){
  Status u, v;
  queue<Status> Q;
  Q.push(in);
  bool visited[7][7][7][7];
  for(int a=0;a<h;a++){
    for(int b=0;b<w;b++){
      for(int c=0;c<h;c++){
	for(int d=0;d<w;d++){
	  visited[a][b][c][d]=false;
	}
      }
    }
  }
  visited[in.cy][in.cx][in.wy][in.wx]=true;
  while(!Q.empty()){
    u=Q.front(), Q.pop();
    if(u.cx==gx && u.cy==gy) return u.cost;
    for(int i=0;i<4;i++){
      ty=u.cy+dy[i];
      tx=u.cx+dx[i];
      if(ty>=0 && ty<h){
	if(tx>=0 && tx<w){
	  if(data[ty][tx]=='0'){
	    int rtx=u.cx+rdx[i], rty=u.cy+rdy[i];
	    if(rty>=0 && rty<h){
	      if(rtx>=0 && rtx<w){
		if(data[rty][rtx]=='0' && !visited[rty][rtx][u.cy][u.cx]){
		  for(int j=0;j<h;j++){
		    for(int k=0;k<w;k++){
		      vis[j][k]=false;
		    }
		  }
		  data[u.cy][u.cx]='1';
		  if(dfs(u.wy, u.wx)){
		    v.wy=u.cy;
		    v.wx=u.cx;
		    v.cy=rty;
		    v.cx=rtx;
		    v.cost=u.cost+1;
		    visited[v.cy][v.cx][v.wy][v.wx]=true;
		    Q.push(v);
		  }
		  data[u.cy][u.cx]='0';
		}
	      }
	    }
	  }
	}
      }
    }
  }
  return -1;
}

bool dfs(int y, int x){
  bool ans=false;
  if(y==ty && x==tx) return true;
  vis[y][x]=true;
  for(int i=0;i<4;i++){
    int ttx=x+dx[i];
    int tty=y+dy[i];
    if(tty>=0 && tty<h){
      if(ttx>=0 && ttx<w){
	if(!vis[tty][ttx] && data[tty][ttx]=='0'){
	  if(dfs(tty, ttx)) ans=true;;
	}
      }
    }
  }
  return ans;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
using namespace std;
ll n,t,x,y,m,q;

int main(){
      ios_base::sync_with_stdio(false); cin.tie(NULL);
      cin>>n>>x>>m;
      vector<ll>ans;
      map<ll,ll>ma;
      ma[x]=1;
      ll ind=0,sum=0;
      ans.push_back(x);
      for(int i=1;i<min(n,m);i++){
        ans.push_back((ans.back()*ans.back())%m);
        if(ma[ans.back()]){
          ind=ma[ans.back()];
          ans.pop_back();
          break;
        }
        else
          ma[ans.back()]=i+1;
      }
      ll pre[ans.size()+1]={0};
      for(int i=1;i<=ans.size();i++){
        pre[i]+=pre[i-1]+ans[i-1];
      }
      if(ans.back()==0){
        cout<<pre[ans.size()];
      }
      else if(ind!=0){
        sum=pre[ans.size()]-pre[ind-1];
        sum=((n-ind+1)/(ans.size()-ind+1))*sum;
        sum+=pre[ind-1];
        if((n-ind+1)%(ans.size()-ind+1))
          sum+=(pre[ind+(n-ind)%(ans.size()-ind+1)]-pre[ind-1]);
        cout<<sum;
      }
      else{
        cout<<pre[n];
      }
}

Measured memory_bytes: 7212
#include <iostream>

using namespace std;

int main(void) {
    int64_t A, B;
    cin >> A >> B;

    int64_t ans = 0;
    while(A%4) {
        ans ^= A++;
    }
    while((B+1)%4) {
        ans ^= ++B;
    }

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


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define all(V) (V).begin(), (V).end() 
#define x first
#define y second

using namespace std;

typedef long long ll;
template <typename T> using V = vector <T>;

V <V <int>> DP;
V <V <int>> T;  
const ll mod = 1e9 + 7;

bool ok(bool c0, bool c1) {
	if(c0) return 1;
	return c1;
}

int solve(int u, int par, bool clr) {
	if(DP[u][clr] != -1) {
		return DP[u][clr];
	}
	int &ans = DP[u][clr];
	ans = 1;
	for(auto v : T[u]) {
		if(v != par) {
			ll cur = 0;
			for(int c = 0; c <= 1; c++) {
				if(ok(clr, c)) {
					cur = (cur + solve(v, u, c)) % mod;
				}
			}
			ans = (ans * cur) % mod;
		}
	}
	return ans;
}

int main() {fio;
	
	int n;
	cin >> n;
	T.resize(n);
	DP.resize(n, V <int> (2, -1));
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;
		T[u].push_back(v);
		T[v].push_back(u);
	}
	cout << (solve(0, -1, 0) + solve(0, -1, 1)) % mod;

    return 0;
}

Measured memory_bytes: 18176
def main():
    L, R = (int(i) for i in input().split())
    MOD = 2019
    R = min(L + 2020, R)
    ans = 2020
    for i in range(L, R):
        for j in range(i+1, R+1):
            # print(i, j)
            ans = min(ans, (i*j) % MOD)
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
  int x;
  cin >> x;
  if(x<1200){
    cout << "ABC" << endl;
  }else{
    cout << "ARC" << endl;
  }
}


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

using namespace std;

class State{
  public:
  int x, y, n;
  State(int x, int y, int n): x(x), y(y), n(n) {};
};

bool operator<(const State &lhs, const State &rhs){
  return (lhs.n > rhs.n);
}

int main(){
  int H, W, Ch, Cw, Dh, Dw;
  string tmp;
  cin >> H >> W;
  cin >> Ch >> Cw >> Dh >> Dw;
  vector<string> grid;
  vector<vector<int>> cost;
  
  for (int i=0; i<H; i++){
    cin >> tmp;
    grid.emplace_back(tmp);
    cost.emplace_back(vector<int>(W, 1e7));
  }
  
  priority_queue<State> Q;
  Q.emplace(Cw-1, Ch-1, 0);
  bool reached = false;
  while (!Q.empty()){
    State s = Q.top();
    Q.pop();
    if (s.x == Dw-1 && s.y == Dh-1) {
      cout << s.n << "\n";
      reached = true;
      break;
    }
    if (cost[s.y][s.x] <= s.n) continue;
    else {
      cost[s.y][s.x] = s.n;
    }
    for (int dx=-1; dx<=1; dx += 2){
      if (s.x + dx >= W || s.x + dx < 0 || s.y >= H || s.y < 0) continue;
      if (grid[s.y][s.x+dx] != '#'){
        Q.emplace(s.x+dx, s.y, s.n);
      }
    }
    for (int dy=-1; dy<=1; dy += 2){
      if (s.x >= W || s.x < 0 || s.y + dy >= H || s.y + dy < 0) continue;
      if (grid[s.y+dy][s.x] != '#'){
        Q.emplace(s.x, s.y+dy, s.n);
      }
    }
    for (int dx=-2; dx<=2; dx++){
      for (int dy=-2; dy<=2; dy++){
        if (s.x + dx >= W || s.x + dx < 0 || s.y + dy >= H || s.y + dy < 0) continue;
        if (grid[s.y+dy][s.x+dx] != '#'){
          Q.emplace(s.x+dx, s.y+dy, s.n+1);
        }
      }
    }
  }
  if (!reached){
    cout << -1 << "\n";
  }
  return 0;
}

Measured memory_bytes: 11180
def Expand_Euclid(a,b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1

    return x0,y0
#================================================
N=int(input())
p=q=1
for _ in range(N):
    T,A=map(int,input().split())
    d=T*q-A*p

    alpha,beta=Expand_Euclid(A,T)
    beta=-beta

    x=(-d*alpha+(T-1))//T
    y=(-d*beta+(A-1))//A
    K=max(x,y)

    p+=T*K+d*alpha
    q+=A*K+d*beta
print(p+q)


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

int main(){
    char C;
    cin>>C;
    if(C=='A'){
        cout<<"T"<<endl;
    }else if(C=='T'){
        cout<<"A"<<endl;
    }else if(C=='G'){
        cout<<"C"<<endl;
    }else if(C=='C'){
        cout<<"G"<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream> 
#include <cstdio>
#include <cmath>

using namespace std;

#define For(i , a , b) for (int i = a , _b = b ; i <= _b ; ++i)
#define Ford(i , a  ,b) for (int i = a , _b = b : i >= _b ; --i)
#define Rep(i , n) for (int i = 0 , _n = n ; i < _n ; ++i)
#define sz(A) ((int)A.size())
#define LL(x) (x << 1)
#define RR(x) ((x << 1) | 1)

typedef pair<int , int> pt;

const int maxn = 5000 + 123;
int n,m;
int a[maxn];
int b[maxn][222];
long long prefSum[maxn];

void ReadData() {
	cin >> n >> m;
	For(i,1,n - 1) cin >> a[i];
	For(i,1,n) For(j,1,m) cin >> b[i][j];
	For(i,2,n) prefSum[i] = prefSum[i - 1] + a[i - 1];
}

const int lg = 14;
int prelog2[maxn];
struct Rmq {
	int a[maxn], table[maxn][lg + 3];
	int n;

	void build(int _a[maxn], int _n) {
		n = _n;
		For(i,1,n) a[i] = _a[i];

		For(i,1,n) table[i][0] = a[i];
		For(j,0,lg - 1) For(i,1,n) if (i + (1 << (j + 1)) - 1 <= n) {
			table[i][j + 1] = max(table[i][j], table[i + (1 << j)][j]);
		}
	}
	int get(int l, int r) {
		if (r < 0) return 0;
		int z = prelog2[r - l + 1];
		return max(table[l][z], table[r - (1 << z) + 1][z]);
	}
} sTable[204];

long long calF(int l, int r) {
	long long res = 0;
	For(j,1,m) {
		res += sTable[j].get(l,r);
	} 
	return res - (prefSum[r] - prefSum[l]);
}

long long dp[maxn];
void Go(int l, int r, int opL, int opR) {
	if (l > r) return;
	int mid = (l + r) >> 1;
	int opMid = opL;
	long long val = calF(opMid, mid);
	For(i,opL + 1, opR) if (i <= mid) {
		long long z = calF(i, mid);
		if (z > val) {
			val = z;
			opMid = i;
		}
	}
	dp[mid] = val;
	Go(l, mid - 1, opL, opMid);
	Go(mid + 1, r, opMid, opR);
}

int kval[maxn];
void init() {
	For(i,1,5000) prelog2[i] = (int) log2(i);

	For(j,1,m) {
		For(i,1,n) kval[i] = b[i][j];
		sTable[j].build(kval, n);
	}
}

void Process() {
	init();

	Go(1,n,1,n);
	//For(i,1,n) For(j, i ,n) cout << calF(i,j) << endl;

	long long res = 0;
	For(i,1,n) res = max(res, dp[i]);

	cout << res << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
//	freopen("input.inp" , "r" , stdin);
	ReadData();
	Process();

	return 0;

}			

Measured memory_bytes: 77824
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List
import qualified Data.IntSet as S

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    n <- getInt
    as <- replicateM n getInt
    let ss = map snd . filter fst . zip (cycle [True, False]) $ sort as
    let cs = map snd . filter fst . zip (cycle [True, False]) $ as
    let set = S.fromList ss
    let ans = length $ filter (flip S.notMember set) cs
    print ans

Measured memory_bytes: 36484
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int d[100010][25];
int dp[(1<<20)+10];

int main(void){
	          int i,j;

	      	  cin.tie(0);
	      	  ios_base::sync_with_stdio(false);

	          int N,M;
	          cin >> N >> M;
	          for(i=1;i<=N;i++){
	        	  int x;
	        	  cin >> x;
	        	  for(j=1;j<=M;j++){
	        		  if(x==j) d[i][j]=d[i-1][j]+1;
	        		  else d[i][j]=d[i-1][j];
	        	  }
	          }

	          for(i=1;i<(1<<M);i++) dp[i]=1e9;

	          for(i=0;i<(1<<M);i++){
	        	  int p=0;
	        	  for(j=0;j<M;j++){
	        		  if(i&(1<<j)){
	        			  p+=d[N][j+1];
	        		  }
	        	  }

	        	  for(j=0;j<M;j++){
	        		  if((i&(1<<j))==0){
	        			  int q=p+d[N][j+1];
	        			  int x=d[N][j+1]-(d[q][j+1]-d[p][j+1]);

	        			  dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+x);
	        		  }
	        	  }

	          }

	          cout << dp[(1<<M)-1] <<'\n';

	          return 0;
}

Measured memory_bytes: 16868
package main

import "fmt"

func main() {
        var n int
        fmt.Scan(&n)
        a := make([]int, n)
        for i := range a {
                fmt.Scan(&a[i])
        }

        col := 1
        mag := 0
        i := 1
        for {
                if i >= len(a) || a[i] != a[i-1] {
                        if col >= 2 {
                                mag += col / 2
                        }
                        col = 0
                }
                if i >= len(a) {
                        break
                }
                col++
                i++
        }
        fmt.Println(mag)
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int health = scanner.nextInt();
        int attack = scanner.nextInt();

        int answer = health / attack;
        int nokori = health % attack;
        if(nokori > 0) {
            answer ++;
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
#define int long long int
// #include "Template.cpp"
#define endl "\n"

void solve()
{
    int r, g, b, k; cin >> r >> g >> b >> k;
    while(g <= r && k > 0) {
        g = g*2;
        k --;
    }
    while(b <= g && k > 0) {
        b = b*2;
        k --;
    }
    if(r < g && g < b) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 3684
#include <bits/stdc++.h>
class union_find {
 public:
  using tp = std::vector<size_t>::size_type;
  // 取り扱う型.

  explicit union_find(const tp n) : parent(n), rank(n, 0), cache() {
    for (tp i = 0; i < n; i++) {
      parent[i] = i;
    }
    cache.reserve(n);
  }

  tp root(tp n) {
    // 番号nの親を求める. ついでに経路圧縮を行う.

    while (parent[n] != n) {
      // 根になるまで親を探索. ついでにキャッシュ変数に追加.
      cache.push_back(n);
      n = parent[n];
    }
    for (const auto i : cache) {
      // キャッシュ変数に追加された子の親を経路圧縮.
      parent[i] = n;
    }
    cache.clear();
    return n;
  }

  bool same(tp x, tp y) {
    // xとyが同じグループに属しているか計算.
    return root(x) == root(y);
  }

  void unite(const tp x, const tp y) {
    // xとyを同じグループにする.
    const auto x_root = root(x);
    const auto y_root = root(y);

    if (x_root == y_root) {
      // 根が同じなら元から同じグループ.
      return;
    }

    if (rank[x_root] < rank[y_root]) {
      // rankの大きい方の根を統合後の根にする.
      parent[x_root] = y_root;
    } else if (rank[y_root] < rank[x_root]) {
      // rankの大きい方の根を統合後の根にする.
      parent[y_root] = x_root;
    } else {
      // rankが同じなら, どっちかを根にして根になったほうのランクを上げる.
      parent[x_root] = y_root;
      rank[x_root]++;
    }
  }

 private:
  std::vector<tp> parent;
  // 親の番号を格納. 自分が根なら parent[i] == i になる.
  std::vector<tp> rank;
  // 自分の下に何段分の子があるかを格納.
  std::vector<tp> cache;
  // root計算のときに経路圧縮を行うためのキャッシュ変数.
};

int main() {
  int64_t n, m;
  std::cin >> n >> m;
  std::vector<int64_t> p(n);
  for (auto & i : p) {
    std::cin >> i;
  }

  union_find uf(n);

  for (int64_t i = 0; i < m; i++) {
    uint64_t x, y;
    std::cin >> x >> y;
    uf.unite(x - 1, y - 1);
  }

  int64_t count = 0;

  for (int64_t i = 0; i < n; i++) {
    if (uf.same(i, p[i] - 1)) {
      count++;
    }
  }

  std::cout << count << std::endl;
  return 0;
}


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

using namespace std;

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

    string s;

    cin>>s;

    cin >> k;

    for(int i=0;i<s.size();i++)
    {
        if(s[i]!=s[k-1]) cout<<"*";

        else cout<<s[i];
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	int a, b, c, d, e, k;
	cin >> a >> b >> c >> d >> e >> k;
	if (e - a <= k) {
		cout << "Yay!" << endl;
	}
	else {
		cout << ":(" << endl;
	}
}

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

int main(){
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  for(int i = 0; i < N; ++i) cin >> A[i];
  vector<vector<int>> dp(N+1,vector<int>(K,false)), dp_ = dp;
  dp[0][0] = true;
  for(int i = 0; i < N; ++i){
    int a = A[i];
    dp[i+1] = dp[i];
    for(int j = K-1; j >= 0; --j){
      if(!dp[i][j]) continue;
      if(j+a >= K) continue;
      dp[i+1][j+a] = true;
    }
  }
  dp_[N][0] = true;
  for(int i = N-1; i >= 0; --i){
    int a = A[i];
    dp_[i] = dp_[i+1];
    for(int j = K-1; j >= 0; --j){
      if(!dp_[i+1][j]) continue;
      if(j+a >= K) continue;
      dp_[i][j+a] = true;
    }
  }
  int ans = 0;
  for(int i = 0; i < N; ++i){
    //if(A[i] >= K) continue;
    // cerr << i << endl;
    // for(auto e : dp[i]) cerr << e << " ";
    // cerr << endl;
    // for(auto e : dp_[i+1]) cerr << e << " ";
    // cerr << endl;
    int k = K-1;
    bool f = true;
    for(int j = 0; j < K; ++j){
      if(!dp[i][j]) continue;
      while(j+k >= K-A[i] and k >= 0 and !dp_[i+1][k]) --k;
      // cerr << j << " " << k << endl;
      if(dp_[i+1][k] and j+k < K and j+k+A[i] >= K){
        f = false;
        break;
      }
    }

    if(f){
      // cerr << A[i] << endl;
      ++ans;
    }
  }
  cout << ans << endl;
}


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

using lint = long long;

class UnionFind{
    vector<int> par;
    vector<long long> wei;
    int groupCount;

public:
    UnionFind(int n = 0){
        init(n);
    }

    void init(int n = 0){
        par.resize(n);
        fill(par.begin(), par.end(), -1);

        wei.resize(n);
        fill(wei.begin(), wei.end(), 0LL);

        groupCount = n;

        return;
    }

    int root(int x){
        if(par[x] < 0){
            return x;
        }
        int r = root(par[x]);
        wei[x] += wei[par[x]];
        return par[x] = r;
    }

    bool same(int x, int y){
        return root(x) == root(y);
    }

    int size(int x){
        return -par[root(x)];
    }

    long long weight(int x){
        root(x);
        return wei[x];
    }

    long long diff(int x, int y){
        return weight(y) - weight(x);
    }

    bool unite(int x, int y, long long w = 0){
        w += weight(x) - weight(y);

        x = root(x);
        y = root(y);

        if(x == y){
            return false;
        }

        if(par[y] < par[x]){
            swap(x, y);
            w = -w;
        }

        par[x] += par[y];
        par[y] = x;
        wei[y] = w;
        --groupCount;

        return true;
    }

    int size(void){
        return groupCount;
    }
};

struct edge{
    int from, to;
    lint cost;

    bool operator<(const edge& rhs) const {
        return cost < rhs.cost;
    }
};

int main(){
    int n;
    while(cin >> n, n){
        int m;
        cin >> m;

        vector<edge> es;
        for(int i = 0 ; i < m ; ++i){
            int a, b;
            lint d;
            char c;
            cin >> a >> c >> b >> c >> d;
            es.push_back({a, b, d / 100LL - 1LL});
        }

        sort(es.begin(), es.end());
        UnionFind uf(n);
        lint ans = 0;
        for(int i = 0 ; i < m ; ++i){
            if(uf.unite(es[i].from, es[i].to)){
                ans += es[i].cost;
            }
        }

        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 3172
class RollingHash:

    def __init__(self, string, root, mod):
        self.root = root
        self.mod = mod
        self.hs = [0] * (len(string) + 1)
        self.pw = [1] * (len(string) + 1)
        for i in range(len(string)):
            self.hs[i + 1] = (self.hs[i] * self.root + ord(string[i])) % self.mod
            self.pw[i + 1] = self.pw[i] * self.root % self.mod

    def get_hash(self, l, r):
        "get the hash of s[l:r] (0 <= l <= r <= len(s))"
        return (self.hs[r] - self.hs[l] * self.pw[r - l]) % self.mod

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.get_hash(index.start, index.stop)
        else:
            return 0


RHMOD = (1 << 61) - 1
class RollingHashMOD61:
    """
    MOD == 2 ** 61 - 1
    参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
    """


    def __init__(self, string, root):
        self.root = root
        self.hs = [0] * (len(string) + 1)
        self.pw = [1] * (len(string) + 1)
        for i in range(len(string)):
            tmp = self.hs[i] * self.root + ord(string[i])
            self.hs[i + 1] = (tmp >> 61) + (tmp & RHMOD)
            tmp = self.pw[i] * self.root
            self.pw[i + 1] = (tmp >> 61) + (tmp & RHMOD)

    def get_hash(self, l, r):
        "get the hash of s[l:r] (0 <= l <= r <= len(s))"
        return (self.hs[r] - self.hs[l] * self.pw[r - l]) % RHMOD
        

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.get_hash(index.start, index.stop)
        else:
            return 0
        
if __name__ == "__main__":
    N = int(input())
    S = input()

    MOD = 2 ** 61 - 1
    root = 10000

    rh = RollingHashMOD61(S, root)

    ok = 0
    ng = N
    while ng - ok > 1:
        mid = (ok + ng) // 2
        hashes = dict()
        flg = False
        for i in range(N - mid + 1):
            hashofsub = rh[i:i+mid]
            if hashofsub in hashes:
                if i >= hashes[hashofsub] + mid:
                    flg = True
                    break
            else:
                hashes[hashofsub] = i
        
        if flg:
            ok = mid
        else:
            ng = mid

    print(ok)


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

int main() {
    int a;
    string s;
    cin >> s;
    int answer = 0;
    for (int i = 0; i < 3; i++) {
    
        if (s[i] == '1') {
            answer++;
        }
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define double long double
#define int long long
#define mii map<int,int>
#define low lower_bound
#define upp upper_bound
#define inf 1000000007 //10^9+7
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
signed main() {
	int n;
	string s;
	cin>>n>>s;
	stack<char>st;
	int b=0,c=0;
	rep(i,n) {
		char a=s[i];
		if(a=='(') st.push('(');
		else {
			if(!st.empty()) {
				if(st.top()=='(') {
					st.pop();
				}
				else {
					st.push(')');
				}
			}
			else {
				st.push(')');
			}
		}
	}
	int m=st.size();
	rep(i,m) {
		if(st.top()=='(') {
			c++;
			st.pop();
		}
		else {
			b++;
			st.pop();
		}
	}
	rep(i,b) cout<<"(";
	rep(i,n) cout<<s[i];
	rep(i,c) cout<<")";
	cend;
}


Measured memory_bytes: 256
# include <iostream>
using namespace std;
int v[110],n,m,i,nr;
int main () {
    cin>>n>>m;
    for(i=1;i<=m;i++){
        cin>>v[i];
        nr+=v[i]%2;
    }
    if(nr>2){
        cout<<"Impossible";
        return 0;
    }
    if(m==1){
        if(v[1]==1)
            cout<<"1\n1\n1\n";
        else
            cout<<v[1]<<"\n"<<2<<"\n"<<1<<" "<<v[1]-1<<"\n";
        return 0;
    }
    for(i=1;i<=m;i++)
        if(v[i]%2==1)
            swap(v[i],v[1]);
    for(i=2;i<=m;i++)
        if(v[i]%2==1)
            swap(v[i],v[m]);
    for(i=1;i<=m;i++)
        cout<<v[i]<<" ";
    cout<<"\n";
    if(v[1]==1)
        cout<<m-1<<"\n";
    else
        cout<<m<<"\n"<<v[1]-1<<" ";
    for(i=2;i<m;i++)
        cout<<v[i]<<" ";
    cout<<v[m]+1<<"\n";
    return 0;
}


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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	long long n, s; cin >> n >> s;
	long long ans = -1;
	int i;
	long long ii;
	if(n < s) {
		cout << -1;
		return 0;
	}
	for(i = 2; 1LL * i * i <= n; ++ i) {
		long long ss = 0, t = n;
		while(t) {
			ss += t % i;
			t /= i;
		}
		if(ss == s) {
			ans = i;
			break;
		}
	}
	if(ans == -1) {
		for(; i >= 1; -- i) {
			if((n - s) % i == 0) {
				ii = (n - s) / i + 1;
				if(ii > i && ii * i + n % ii == n) {
					ans = ii;
					break;
				}
			}
		}
		if(ans == -1) {
			if(n == s) ans = n + 1;
		}
	}
	cout << ans;
	return 0;
}

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

int main()
{
    int n = 0;
    int edge = 0;
    int max,count = 0;
    cin >> n;
    while(n > 0)
    {
        cin >> edge;
        if(edge > max)
            max = edge;
        count += edge;
        --n;
    }
    if(count > (max << 1))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3616
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

int main(){
  int n,x;
  long long ans,now = 2;
  scanf("%d %lld",&n,&ans);
  ans--;
  for(int i=0;i<n-1;i++){
    long long a;
    scanf("%lld",&a);
    if(a==now){
      now++;
      continue;
    }
    ans += (a-1)/now;
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 128
#include<vector>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<vector>
using namespace std;
const int mo=1e9+7;
#define int long long
typedef vector<int> vint;
main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    scanf("%d",&n);
    vint a(n+1);
    for(int i=1;i<=n;i++)scanf("%d",begin(a)+i);
    vint x(n+1,0);
    vint res;
    for(int i=n;i>0;i--)
    {
        int cnt=0;
        for(int j=i;j<=n;j+=i)cnt^=x[j];
        if(cnt!=a[i])
        {
            x[i]=1;
            res.emplace_back(i);
        }
    }
    cout<<res.size()<<endl;
    for(int i=0;i<res.size();i++)printf(i==0?"%d":" %d",res[i]);
    puts("");

}

Measured memory_bytes: 5108
import numpy as np


def check(x):
    dp = np.zeros(k, np.bool)
    dp[0] = True
    for e in a[:x] + a[x+1:]:
        dp[e:] |= dp[:-e]

    return dp[-a[x]:].any()


n, k = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

lb = -1
ub = n
while ub - lb > 1:
    m = (lb + ub) // 2
    if check(m):
        ub = m
    else:
        lb = m

print(ub)


Measured memory_bytes: 27836
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
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; }


using namespace std;

int main(){
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.size(), m = t.size();
    vector<vector<int>> is(26);
    rep(i, n) is[s[i]-'a'].push_back(i);
    rep(i, n) is[s[i]-'a'].push_back(i+n);
    ll ans = 0;
    int p = 0;
    rep(i, m) {
        int c = t[i] - 'a';
        if (is[c].size() == 0) {
            puts("-1");
            return 0;
        }
        p = *lower_bound(is[c].begin(), is[c].end(), p)+1;
        if (p >= n) {
            p -= n;
            ans += n;
        }

    }
    ans += p;
    cout << ans << endl;
    return 0;



}

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


struct listnode{
 int val;
 listnode*  next;};


int32_t main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int ans=max(a*c,a*d);
  int ans2=max(b*c,b*d);

  cout<<max(ans,ans2);

  
  
  
return 0;
}

Measured memory_bytes: 3632
from sys import stdin
from itertools import groupby
import numpy as np

h,w = [int(x) for x in stdin.readline().rstrip().split()]
n = int(stdin.readline().rstrip())
li = list(map(int,stdin.readline().rstrip().split()))

lin = np.asarray([0]*h*w)
now = 0
point = 0
for i in range(n):
    point += 1
    for j in range(now,li[i]+now):
        lin[j] = point
    now += li[i]

lin = np.reshape(lin,(h,w)).tolist()

for i in range(h):
    if i%2 == 1:
        lin[i] = lin[i][::-1]
    print(*lin[i])

Measured memory_bytes: 13168
#include<algorithm>
#include<cstdio>
#define LL long long
using namespace std;
const int mod=1e9+7;
int n,m,N,sl,fh,ans,a[20],fac[1<<16],ifc[1<<16],num[1<<16],dp[20][1<<16];
int rd()
{
	sl=0;fh=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
	return sl*fh;
}
int _pow(int k,int i)
{
	int t=1;
	for(;i;i>>=1,k=1ll*k*k%mod)
		if(i&1)
			t=1ll*t*k%mod;
	return t;
}
LL C(int x,int y) {return 1ll*fac[x]*ifc[y]%mod*ifc[x-y]%mod;}
void upd(int &x,int y) {x+=y; if(x>=mod) x-=mod;}
int main()
{
	n=rd();m=rd();N=1<<n;fac[0]=1;
	for(int i=m;i;--i) a[i]=rd();
	for(int i=1;i<N;++i) fac[i]=1ll*i*fac[i-1]%mod,num[i]=num[i>>1]+(i&1);
	ifc[N-1]=_pow(fac[N-1],mod-2);
	for(int i=N-1;i;--i) ifc[i-1]=1ll*i*ifc[i]%mod;
	if(!m) {printf("%lld\n",1ll*N*fac[N-1]%mod); return 0;}
	dp[0][0]=1;
	for(int i=1;i<=m;++i)
	{
		for(int j=0;j<N;++j)
			if(dp[i-1][j])
				for(int k=1;k<=n;++k)
					if(!((j>>k-1)&1)&&N-a[i]-j>=(1<<k-1)-1)
						dp[i][j|(1<<k-1)]=(dp[i][j|(1<<k-1)]+dp[i-1][j]*C(N-a[i]-j,(1<<k-1)-1)%mod*fac[1<<k-1])%mod;
		for(int j=0;j<N;++j) upd(dp[i][j],dp[i-1][j]);
	}
	for(int i=0;i<N;++i) dp[m][i]=1ll*dp[m][i]*fac[N-i-1]%mod;
	for(int i=0;i<N;++i)
		if(num[i]&1) upd(ans,mod-dp[m][i]);
		else upd(ans,dp[m][i]);
	printf("%lld\n",1ll*N*ans%mod);
	return 0;
}

Measured memory_bytes: 4992
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc= new Scanner(System.in);
		while(true){
			int H=sc.nextInt();
			int W=sc.nextInt();
			if(H==0&&W==0){
				break;
			}else{
				for(int i=0;i<H;i++){
					if(i%2==0){
						for(int j=0;j<W;j++){
							if(j%2==0){
								System.out.print("#");
							}else{
								System.out.print(".");
							}
						}
					}else{
						for(int j=0;j<W;j++){
							if(j%2==0){
								System.out.print(".");
							}else{
								System.out.print("#");
							}
						}						
					}
					System.out.println();
				}
				System.out.println();
			}
		}
	}
}

Measured memory_bytes: 35312
N,x,*as=$<.read.split.map(&:to_i)
sum = as.inject(&:+)
as.sort!
if x < as[0]
    puts 0
elsif sum < x
    puts N-1
else
    ret = 0
    as.each do |a|
        if a <= x
            ret += 1
            x -= a
        else
            break
        end
    end

    puts ret
end

Measured memory_bytes: 1788