akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long double ldbl;
typedef long long ll;
typedef double dbl;
const ldbl E = 2.71828182845904523536;
const ldbl pi = acos(-1);
const dbl eps = 1e-9;
const ll mod = 1e9+7;
const ll inf = 1LL<<30;
#define countones(x) __builtin_popcount (x);
int dcmp(double x, double y)
{
    return fabs(x - y) <= eps ? 0 : x < y ? -1 : 1;
};

string convertostring(long long  num)
{
    stringstream ss;
    ss << num;
    return ss.str();
}
void PLAY()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    cout << fixed << setprecision(2);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int N=1e5+2;
int n;
ll mem[N];
vector<ll>v;
ll sol(ll i)
{
    if(i==n-1)
        return 0;

    ll &ret=mem[i];
    if(ret!=-1)
        return ret;
    ret=inf;
    ll p1=0,p2=0;
    if(i+1<=n-1)
        ret=min(ret,abs(v[i]-v[i+1])+sol(i+1));
    if(i+2<=n-1)
        ret=min(ret,abs(v[i]-v[i+2])+sol(i+2));
    return ret;
}
int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        ll a;
        cin>>a;
        v.push_back(a);
    }

    memset(mem,-1,sizeof mem);
    cout<<sol(0);
}


Measured memory_bytes: 5108
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long int
#define M 1000000007
#define pie 3.141592653589793238
using namespace std;


signed main(){  
    string s; cin >> s;
    int n = s.size();
    int sum = 0;
    for(int i=0; i<n; i++){
        sum += s[i]-'0';
    }
    if(sum%9){
        cout << "No";
    }
    else{
        cout << "Yes";
    }
    return 0;
}

Measured memory_bytes: 3716
# -*- coding:utf-8 -*-
from collections import Counter

def check(n, a):
    count = Counter(a)
    if n % 2 == 1 and (0 not in count or count[0] != 1):
        return False
    for i in range(1 + (n % 2), n+1, 2):
        if i not in count or count[i] !=2:
            return False
    return True

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))

    if not check(N,A):
        print(0)
    else:
        if N > 1:
            c = 2
            for _ in range((N // 2) - 1):
                c = c * 2 % (int(1e9) + 7)
            print(c)
        else:
            print(1)


Measured memory_bytes: 14820
#include <bits/stdc++.h>
#ifdef DEMETRIO
#define deb(...) fprintf(stderr,__VA_ARGS__)
#define deb1(x) cerr << #x << " = " << x << endl
#else
#define deb(...) 0
#define deb1(x) 0
#endif
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;

int q[2];
vector<int> g[100005];
int c[100005];
int n,m;

bool dfs(int x, int cc){
	c[x]=cc;q[cc]++;
	for(int y:g[x]){
		if(c[y]<0){
			if(!dfs(y,!cc))return false;
		}
		else if(c[y]==c[x])return false;
	}
	return true;
}

int main(){
	scanf("%d%d",&n,&m);
	fore(i,0,m){
		int x,y;
		scanf("%d%d",&x,&y);x--;y--;
		g[x].pb(y);g[y].pb(x);
	}
	ll r;
	memset(c,-1,sizeof(c));
	if(dfs(0,0))r=1LL*q[0]*q[1]-m;
	else r=1LL*n*(n-1)/2-m;
	printf("%lld\n",r);
	return 0;
}

Measured memory_bytes: 6528
from collections import deque


def main():
    vertex = int(input())
    tree = [[] for _ in range(vertex + 1)]
    color = [0] * (vertex + 1)
    parent = [0] * (vertex + 1)
    order = []
    ab = []
    for i in range(vertex - 1):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
        ab.append([a, b])
    queue = deque([1])

    # 木の親を決める
    while queue:
        now = queue.popleft()
        order.append(now)
        for t in tree[now]:
            if not t == parent[now]:
                parent[t] = now
                queue.append(t)

    # 色番号を割り当てる
    for ord in order:
        ng = color[ord]
        color_num = 1
        for t in tree[ord]:
            if not t == parent[ord]:
                if color_num == ng:
                    color_num += 1
                color[t] = color_num
                color_num += 1

    print(max(color))
    for a, b in ab:
        if a == parent[b]:
            print(color[b])
        else:
            print(color[a])


if __name__ == '__main__':
    main()



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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

vector<ll> pw2(51,1);
vector<ll> pw10(19,1);

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}
ll myceil(ll x,ll y){
	if(x<=y) return 1;
	else if(x%y==0) return x/y;
	else return x/y+1;
}

//a,b x
int main(){
	ll N; cin>>N;
	vector<ll> C(N-1);
	vector<ll> S(N-1);
	vector<ll> F(N-1);
	rep(i,N-1) cin>>C[i]>>S[i]>>F[i];

	rep(i,N-1){//駅i~N-2まで
		ll tmp=0;//到着時間
		for(int j=i+1;j<=N-1;j++){
			//駅jへの到着時間
			if(tmp<=S[j-1]) tmp=S[j-1]+C[j-1];
			else{
				tmp=myceil(tmp,F[j-1])*F[j-1]+C[j-1];
			}
		}
		cout<<tmp<<endl;
	}
	cout<<0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,k=map(int,input().split())
    if(2*k>n+1):
        print(-1)
        return
    
    h=(2*k+3*n-1)//2
    for i in range((n+1)//2):
        print(k+2*i,h-i,k+2*n+i)
    for i in range(n//2):
        print(k+1+i*2,k+2*n-1-i,k+2*n+((n-1)//2)+i+1)
resolve()

Measured memory_bytes: 50080
using System;
using System.Collections;

class program
{

    static bool[,] graph = new bool[10, 10];
    static Stack stack = new Stack();
    static int ans = 0;

    static void dps(int root, int N)
    {
        stack.Push(root);

        if (stack.Count == N)
        {
            ans++;
            stack.Pop();
            return;
        }

        for(int i = 1; i <= N; i++)
        {
            if (graph[root, i] == true)//rootからiへの辺が存在する
            {
                if (!stack.Contains(i))//そのパスでiを訪問したことがない
                {
                    dps(i, N);
                }
            }
        }

        stack.Pop();
        return;

    }


    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);


        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                graph[i, j] = false;
            }
        }

        for(int i = 0; i < M; i++)
        {
            input = Console.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            graph[a, b] = true;
            graph[b, a] = true;

        }

        int root = 1;
        dps(root, N);

        Console.WriteLine(ans);

    }
}

Measured memory_bytes: 4440
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int main (int argc, char const *argv[])
{
    int64_t X;

    scanf("%"PRId64, &X);

    if ((X == 7) || (X == 5) || (X == 3)) {
        puts("YES");
    } else {
        puts("NO");
    }

    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
#define N 200020
#define y1 ysgh
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[N];
struct Seg{
	int l,r;
	Seg(int _l=0,int _r=0){l=_l,r=_r;}
	inline bool empty(){
		return l>r;
	}
	inline Seg operator & (const Seg b){
		return Seg(max(l,b.l),min(r,b.r));
	}
	inline Seg operator ^ (const Seg b){
		return l==b.l?Seg(b.r+1,r):Seg(l,b.l-1);
	}
};
struct state{
	Seg p;
	int val;
	state(Seg _p,int _v=0){p=_p,val=_v;}
	inline state operator + (const state b){
		return state(p&b.p,val+b.val);
	}
	inline state operator + (const int qwq){
		return state(p,val+qwq);
	}
	inline bool operator < (const state b){
		return val<b.val;
	}
};
vector<state> dp[N],now;
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	dp[0].push_back({{0,0},0});
	for(int i=1;i<=n+1;++i){
		Seg lim={0,a[i]};
		now.clear();
		for(auto u:dp[i-1]){
			state x0={Seg(u.p.l,a[i])&lim,0};
			state x1={Seg(0,u.p.l-1)&lim,1};
			state y0={Seg(a[i]-a[i-1]+u.p.l,a[i])&lim,0};
			state y1={Seg(0,a[i]-a[i-1]+u.p.l-1)&lim,1};
			now.push_back(x0+y0+u.val);
			now.push_back(x0+y1+u.val);
			now.push_back(x1+y0+u.val);
			now.push_back(x1+y1+u.val);
		}
		sort(now.begin(),now.end());
		for(auto u:now){
			Seg gu=u.p;
			for(auto t:dp[i]){
				Seg d=t.p&gu;
				if(!d.empty())gu=gu^d;
				if(gu.empty())break;
			}
			if(!gu.empty()){
				dp[i].push_back({gu,u.val});
			}
		}
	}
	printf("%d\n",dp[n+1][0].val);
	return 0;
}



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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
using tp = tuple<ll, ll, ll>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

//グラフ関連
struct Edge {
    ll to, cap, rev;
    Edge(ll _to, ll _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    ll n;
    cin >> n;
    Graph g(n);
    REP(i, n - 1) {
        ll a, b;
        cin >> a >> b;
        add_edge(g, --a, --b, 1, true, 1);
    }
    auto dfs = [&](auto &&self, int v, int p) -> ll {
        ll con = 0;
        for(auto e : g[v]) {
            if(e.to == p)
                continue;
            ll d = self(self, e.to, v);
            if(d == -1)
                return -1;
            con += d;
        }
        if(con == 0) {
            return 1;
        } else if(con == 1) {
            return 0;
        } else {
            return -1;
        }
    };

    ll ret = dfs(dfs, 0, -1);
    if(ret == 0) {
        cout << "Second" << en;
    } else {
        cout << "First" << en;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*
    ll t;
    cin >> t;
    while(t--)*/
    solve();

    return 0;
}


Measured memory_bytes: 12428
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <bitset>
using namespace std;

#define int long long

signed main() {
    char a;
    cin >> a;

    cout << ((int) a  <= 90 ? 'A' : 'a') << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
#define INF (1LL << 60)
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,k,n) for(int i=(k);(i)<(n);(i)++)
#define REP(i,n) for(int i = 0;(i)<(n);(i)++)
#define REPR(i,n) for(inti = n; i >= 0; i--)

int main() {
	int a, b, c;
	cin >> a >> b >> c;
  	cout << a * b / 2;
}



Measured memory_bytes: 256
n,m,l=map(int, input().split())
a=[list(map(int, input().split())) for i in range(n)]
b=[list(map(int, input().split())) for i in range(m)]
for i in a:
    result = []
    for j in zip(*b):
        result.append(sum([a * b for (a,b) in zip(i, j)]))
    print(*result)

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

int main(){
  long long A;
  long long B;
  
  cin >> A >> B;
  
  long long buf = A - (2 * B);
  
  if(buf >= 0){  
    cout << buf;
    return 0;
  }
  cout << 0;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
class Main{
	Scanner sc=new Scanner(System.in);
	int[] yama=new int[10];
	void s(){
		for(int i=0; i<10; i++){
			yama[i]=sc.nextInt();
		}
		for(int i=0; i<9; i++){
			for(int j=i; j<10; j++){
				if(yama[i]<=yama[j]){
					int a =yama[j];
					yama[j]=yama[i];
	  			  	yama[i]=a;
				}
			}
		}
		for(int j=0; j<3; j++){
			System.out.println(yama[j]);
		}
	}
	public static void main(String[]agrs){
		new Main().s();
	}
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e19;
//const int INF=(1<<30);


int main(){
  ll ans=0;
  ll n;
  cin >> n;

  ans = n*(n+1)/2;
  ans -= (n/3)*(3+(n/3)*3)/2;
  ans -= (n/5)*(5+(n/5)*5)/2;
  ans += (n/15)*(15+(n/15)*15)/2;

  cout << ans << endl;
}



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

using namespace std;

typedef long long int ll;

#define FOR(i,l,r) for(i=l;i<r;i++)

#define REP(i,n) FOR(i,0,n)

#define ALL(x) x.begin(),x.end()

#define P pair<ll,ll>

#define F first

#define S second

signed main(){

  ll N,i,ans;cin>>N;

  cout<<1-N<<endl;

  return 0;

}

Measured memory_bytes: 3620
N = int(input())
b = list(map(int,input().split()))
c =[]
while b:
    a = 0
    for i in range(len(b)-1,-1,-1):
        if i+1 == b[i]:
            a = b.pop(i)
            c.append(a)
            break
    if a == 0:
        print(-1)
        exit()
for i in range(len(c)-1,-1,-1):
    print(c[i])


Measured memory_bytes: 9148
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

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

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # すべての頂点に対して親を検索する
    def all_find(self):
        for n in range(len(self.par)):
            self.find(n)


UF = UnionFind(N)
for iam in range(N):
    for friend in F[iam]:
        UF.union(iam, friend)

ans = [UF.size[UF.find(iam)] - 1 for iam in range(N)]
for iam in range(N):
    ans[iam] -= len(F[iam])

for iam in range(N):
    for block in B[iam]:
        if UF.same(iam, block):
            ans[iam] -= 1

print(*ans, sep=' ')

Measured memory_bytes: 48452
n,m=map(int,input().split())
a=list(map(int,input().split()))

import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
x=1
for i in range(n):
  x=lcm(x,a[i]//2)

power=[0]*n
for i in range(n):
  while a[i]%2==0:
    a[i]//=2
    power[i]+=1
    
if power.count(power[0])==n:  
  print((m+x)//(2*x))
else:
  print(0)

Measured memory_bytes: 85768
#include<stdio.h>

#define MAX 10000
#define NIL -1

void setDepth(int,int);
int Height(int);
int getSibling(int);
void print (int);

typedef struct{
  int parent;
  int left;
  int right;
}node;

node t[MAX];
int n,D[MAX],H[MAX];

int main(){
  int i,v,l,r,root=0;

  scanf("%d",&n);

  for(i=0;i<=n-1;i++){
    t[i].parent=NIL;
  }

  for(i=0;i<=n-1;i++){
    scanf("%d %d %d",&v,&l,&r);

    t[v].left=l;
    t[v].right=r;

    if(l!=NIL) t[l].parent=v;
    if(r!=NIL) t[r].parent=v;
  }

  for(i=0;i<=n-1;i++){
    if(t[i].parent==NIL) root=i;
  }

  setDepth(root,0);
  Height(root);

  for(i=0;i<=n-1;i++){
    print(i);
  }

  return 0;
}

void setDepth(int u,int d){
  
  if(u==NIL) return;
  
  D[u]=d;
  setDepth(t[u].left,d+1);
  setDepth(t[u].right,d+1);
}

int Height(int u){
  int h1=0,h2=0;

  if(t[u].left!=NIL) h1=Height(t[u].left)+1;
  if(t[u].right!=NIL) h2=Height(t[u].right)+1;

  if(h1<h2) return H[u]=h2;
  return H[u]=h1;
}

int getSibling(int u){

  if(t[u].parent==NIL) return NIL;

  if(t[t[u].parent].left!=u && t[t[u].parent].left!=NIL)
    return t[t[u].parent].left;

  if(t[t[u].parent].right!=u && t[t[u].parent].right!=NIL)
    return t[t[u].parent].right;

  return NIL;
}

void print(int u){
  int cnt=0;
  
  printf("node %d: ",u);
  printf("parent = %d, ",t[u].parent);
  printf("sibling = %d, ",getSibling(u));

  if(t[u].left!=NIL) cnt++;
  if(t[u].right!=NIL) cnt++;

  printf("degree = %d, ",cnt);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(t[u].parent==NIL) printf("root\n");
  else if(t[u].left==NIL && t[u].right==NIL) printf("leaf\n");
  else printf("internal node\n");
}



Measured memory_bytes: 2108
#include <iostream>
#include <set>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <map>
#include <stack>
#include <unordered_map>
using namespace std;

typedef long long ll;

int main() {
  int H, W, N;
  cin >> H >> W;
  cin >> N;
  unordered_map<int, vector<int>> row_blocks;
  set<pair<int, int>> blocks;

  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    row_blocks[y].push_back(x);
    blocks.insert(make_pair(x, y));
  }

  for (int i = 0; i < W; i++) {
    if (row_blocks[i].size() > 0) {
      sort(row_blocks[i].begin(), row_blocks[i].end());
    }
    row_blocks[i].push_back(H);
  }

  int x = 0;
  int res = 1e9;
  for (int y = 0; y < W; y++) {
    int block_x = *upper_bound(row_blocks[y].begin(), row_blocks[y].end(), x);
    res = min(res, block_x);
    if (x + 1 == block_x) {
      break;
    } else {
      x++;
    }
    while (blocks.count(make_pair(x, y + 1)) && !blocks.count(make_pair(x, y))) {
      x++;
    }
    if (x >= H || blocks.count(make_pair(x, y))) {
      break;
    }
  }
  cout << res << endl;
  return 0;
}



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

int main() {
  int n,s;
  cin >> n >> s;
  ll mod = 998244353;
  field dp(n+1,vector<ll>(s+1,0));
  dp[0][0] = 1;
  rep(i,0,n) {
    ll a;
    cin >> a;
    rep(j,0,s+1) {
      dp[i+1][j] += dp[i][j]*2;
      dp[i+1][j] %= mod;
      if (j+a <= s) {
        dp[i+1][j+a] += dp[i][j];
        dp[i+1][j+a] %= mod;
      }
    }
  }
  cout << dp[n][s] << endl;
  return 0;
}


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

#define MAX 55
#define INF (1<<29)
 
int N, M;
int memo[MAX][MAX][MAX][MAX][2][2];
vector<int> a, b;
 
int get_point(int turn, int al, int ar, int bl, int br)
{
    int ap = 0, bp = 0;   
    bool astop = 0, bstop = 0;
    for (int i = ar-1, j = br-1; i >= al || j >= bl; turn ^= 1) {
        if (turn == 0) {
            if (a[i] == -1) {
                bstop = 1;
            } else if (!astop) {
                ap += a[i];
            }
            i--;
        } else {
            if (b[j] == -1) {
                astop = 1;
            } else if (!bstop) {
                bp += b[j];
            }
            j--;
        }
    }
    return ap - bp;
}
 
int solve(int n, int m, int fn, int fm, int turn, int pass)
{    
    int res = memo[n][m][fn][fm][turn][pass];
    if (res != INF) {
        return res;
    }      
 
    res = (turn == 0 ? -INF : INF);
    
    if (turn == 0) {
        if (pass == 1) {
            res = max(res, 0);
        } else {
            res = max(res, solve(fn, fm, fn, fm, 1, (n == fn && m == fm))
                      + get_point(1, n, fn, m, fm));               
        }
        if (fn < N) {
            res = max(res, solve(n, m, fn+1, fm, 1, 0));
        }
    } else {
        if (pass == 1) {
            res = min(res, 0);
        } else {
            res = min(res, solve(fn, fm, fn, fm, 0, (n == fn && m == fm))
                      + get_point(0, n, fn, m, fm));   
        }
        if (fm < M) {
            res = min(res, solve(n, m, fn, fm+1, 0, 0));
        }        
    }
    
    return (memo[n][m][fn][fm][turn][pass] = res);
}
 
void init()
{
    fill(memo[0][0][0][0][0],
         memo[MAX-1][MAX-1][MAX-1][MAX-1][2], INF);
}
 
int main()
{
    cin >> N >> M;
    a.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    b.resize(M);
    for (int i = 0; i < M; i++) {
        cin >> b[i];
    }
    init();
    cout << solve(0, 0, 0, 0, 0, 0) << endl;
    return 0;
}

Measured memory_bytes: 146096
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int Max = 1e6 + 5;

int lst[Max];
string ls[Max];
map<string, int> ma1, ma2;

int main()
{
	int n, d, x;
	cin >> n >> d >> x;
	ll res = x;
	for (int i = 1;i <= n;i++)
	{
		int t;
		scanf("%d", &t);
		res += (1 + (d - 1) / t);
	}
	cout << res;
}

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

int main(){
	ios::sync_with_stdio(false);
	int N; cin>>N;
	map<string,int> mp;
	rep(i,N){
		string s; cin>>s;
		mp[s]++;
	}

	int nmax=0;
	for(auto x:mp){
		nmax = max(nmax, x.second);
	}

	for(auto x:mp){
		if(x.second == nmax){
			cout << x.first << endl;
		}
	}
	
}

Measured memory_bytes: 19220
while True:
    try:
        i = float(input())
        if i <= 48.0: print("light fly")
        elif i <= 51.0: print("fly")
        elif i <= 54.0: print("bantam")
        elif i <= 57.0: print("feather")
        elif i <= 60.0: print("light")
        elif i <= 64.0: print("light welter")
        elif i <= 69.0: print("welter")
        elif i <= 75.0: print("light middle")
        elif i <= 81.0: print("middle")
        elif i <= 91.0: print("light heavy")
        else: print("heavy")
    except:
        break

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


void mark(int mp[10][10],int y,int x){
  int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
  for(int i=0;i<4;i++) {
    int nx=x+dx[i],ny=y+dy[i];
    if(nx<0||ny<0||nx>=10||ny>=10)continue;
    mp[ny][nx]=!mp[ny][nx];
  }
  mp[y][x]=!mp[y][x];
}

bool check(int mp[10][10]){
  for(int i=0;i<10;i++)
    for(int j=0;j<10;j++)if(mp[i][j])return 0;
  return 1;
}

int main(){
  int q;
  cin>>q;
  while(q--){
    int mp[10][10],b[10][10];
    for(int i=0;i<10;i++)for(int j=0;j<10;j++)cin>>mp[i][j],b[i][j]=mp[i][j];

    int ans[10][10]={};
    for(int i=0;!check(mp);i++){
      for(int j=0;j<10;j++)for(int k=0;k<10;k++) mp[j][k]=b[j][k];
      for(int j=0;j<10;j++)for(int k=0;k<10;k++) b[j][k]=mp[j][k];

      for(int j=0;j<10;j++)if((ans[0][j]=((i>>j)%2)))mark(mp,0,j);
      for(int j=1;j<10;j++)
	for(int k=0;k<10;k++)
	  if((ans[j][k]=mp[j-1][k]))mark(mp,j,k);
    }

    for(int i=0;i<10;i++){
      for(int j=0;j<10;j++){
	if(j) cout <<" ";
	cout << ans[i][j];
	assert(ans[i][j]==0||ans[i][j]==1);
      }
      cout <<endl;
    }
  }
  return 0;
}

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

#define ll long long
#define pii pair <int, int>
#define x first
#define y second

using namespace std;

int n, L, R = INT_MAX, rez;
pii v[100001];
int a[100001], b[100001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    int len = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].x >> v[i].y;
        L = max(L, v[i].x);
        R = min(R, v[i].y);
        len = max(len, v[i].y - v[i].x + 1);
    }
    rez = len + max(0, R - L + 1);
    sort(v + 1, v + n + 1);
    L = 0, R = INT_MAX;
    for (int i = 1; i < n; ++i) {
        L = max(L, v[i].x);
        R = min(R, v[i].y);
        a[i] = max(0, R - L + 1);
    }
    L = 0, R = INT_MAX;
    for (int i = n; i > 1; --i) {
        L = max(L, v[i].x);
        R = min(R, v[i].y);
        b[i] = max(0, R - L + 1);
    }
    for (int i = 1; i < n; ++i)
        rez = max(rez, a[i] + b[i + 1]);
    return cout << rez, 0;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

const int N = 100010;

char s[N];
int len;
int stop[N];
int ans[N];

vector<int> L_pos;
vector<int> R_pos;

void walk(int index) {
    int ori = s[index];
    int cur_index = index;
    vector<int> path;
    while (true) {
        path.push_back(cur_index);
        int step = (s[cur_index] == 'R' ? 1 : -1);
        cur_index += step;
        if (s[cur_index] != ori) {
            break;
        }
    }
    for (const auto &v : path) {
        stop[v] = cur_index;
    }
}

int main() {
    memset(stop, 0xff, sizeof stop);
    scanf("%s", s);
    len = strlen(s);
    for (int i = 0; s[i]; i++) {
        if (s[i] == 'L') {
            L_pos.push_back(i);
        } else {
            R_pos.push_back(i);
        }
    }
    for (int i = 0; s[i]; i++) {
        if (s[i] == 'L') {
            auto it = lower_bound(R_pos.begin(), R_pos.end(), i);
            int stop_index = *(--it);
            stop[i] = stop_index;
        } else {
            auto it = lower_bound(L_pos.begin(), L_pos.end(), i);
            int stop_index = *it;
            stop[i] = stop_index;
        }
    }
    for (int i = 0; s[i]; i++) {
        int stop_index = stop[i];
        int time = abs(stop_index - i);
        if (time % 2 == 0) {
            ans[stop_index]++;
        } else {
            stop_index += (s[stop_index] == 'R' ? 1 : -1);
            ans[stop_index]++;
        }
    }
    for (int i = 0; s[i]; i++) {
        printf("%d%c", ans[i], " \n"[i + 1 == len]);
    }
    return 0;
}

Measured memory_bytes: 1916
nlist=input()
ans=0
if nlist[0]=="+":
    ans+=1
else:
    ans-=1
if nlist[1]=="+":
    ans+=1
else:
    ans-=1
if nlist[2]=="+":
    ans+=1
else:
    ans-=1
if nlist[3]=="+":
    ans+=1
else:
    ans-=1
print(ans)

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int n = s.size();

    if(s[0] == 'o' || s[n-1] == 'o')
        cout << 'o' << endl;
    else
        cout << 'x' << endl;

    return 0;
}

Measured memory_bytes: 0
fn main() {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    let n: u32 = line.trim().parse().unwrap();
    for i in 1..10 {
        if &n % i == 0 && &n / i <= 9 {
            print!("Yes");
            return;
        }
    }
    print!("No")
}


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

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    int cnt = 0, cnt_b = 0;
    rep(i, 0, s.size()){
        if(s[i] == 'c') cout << "No" << endl;
        else if(s[i] == 'a'){
            if(cnt + cnt_b < a + b){
                cout << "Yes" << endl;
                cnt++;
            }
            else cout << "No" << endl;
        }
        else{
            if(cnt + cnt_b < a + b && cnt_b < b){
                cout << "Yes" << endl;
                cnt_b++;
            }
            else cout << "No" << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3748
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;
#define all(x) x.begin(),x.end()
const ll INF = 1e9;
const ll mod = 1e9 + 7;

int digit(ll x) {
    if (x / 10 == 0) return 1;
    return digit(x / 10) + 1;
}

ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    return ((a * b == 0)) ? 0 : (a / gcd(a,b) * b);
}

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};


//////////////////////////////////////////////////////////////////////////////////////

int main(){
    int n,x,t;
    cin >> n >> x >> t;

    if (n % x == 0) {
        cout << (n / x) * t << endl;
    }
    else {
        cout << (n / x) * t + t << endl;
    }
}



Measured memory_bytes: 3636
// 3_abc112_c
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define INF (1e16)
#define MOD (1000000007)
typedef long long ll;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<vector<int>> v(n, vector<int>(3));
    int nonzero = -1;
    rep(i, n){
        cin >> v[i][0] >> v[i][1] >> v[i][2];
        if(nonzero == -1 && v[i][2] > 0){
            nonzero = i;
        }
    }

    rep(cx, 101){
        rep(cy, 101){
            int flag = 1;
            int ch = v[nonzero][2] + abs(v[nonzero][0] - cx) + abs(v[nonzero][1] - cy);

            rep(i, n){
                int x = v[i][0];
                int y = v[i][1];
                int h = v[i][2];

                if(h != max(ch - abs(x - cx) - abs(y - cy), 0)){
                    flag = 0;
                    break;
                }
            }

            if(flag){
                cout << cx << " " << cy << " " << ch << endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(n) rep(i,n)
#define all(n) n.begin(),n.end()

const int MAXN = 3000, MAXM = 100, C = 0, T = 1;
const int INF = 1 << 28;
int cost[2][MAXM + 10][MAXM + 10];

int main()
{
    int n, m;
    while(cin >> n >> m && n)
    {
        int a, b, cc, ct;
        REP(MAXM)rep(j,MAXM)rep(e,2)cost[e][i][j] = INF;
        REP(n)
        {
            cin >> a >> b >> cc >> ct; a--; b--;
            cost[C][a][b] = cost[C][b][a] = min(cc, cost[C][a][b]);
            cost[T][a][b] = cost[T][b][a] = min(ct, cost[T][a][b]);
        }

        int k, p, q, r;
        cin >> k;
        int d[MAXM] = {}, used[MAXM] = {};
        rep(s,k)
        {
            cin >> p >>q >> r; p--; q--;
            memset(used,0, sizeof(used));
            REP(m) d[i] = INF;
            d[p] = 0;
            while(true)
            {
                int v = -1;
                rep(i, m)if(!used[i] && (v == -1 || d[i] < d[v])) v = i;
                if(v == -1) break;
                used[v] = true;
                rep(i,m) d[i] = min(d[i], d[v] + cost[r][v][i]);
            }
            cout << d[q] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 1248
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>
#include<deque>
#include<cmath>





using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const ll INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;


string perm(string s) {
    string res = s;
    vector<int> cnt(256, 0);
    string mp;
    mp.resize(256);
    int n = s.size();
    for (int i = 0, id = 0; i < n; ++i) {
        if (cnt[s[i]] == 0) {
            mp[s[i]] = 'a' + id;
            ++cnt[s[i]];
            ++id;
        }
    }
    for (int i = 0; i < n; ++i) {
        res[i] = mp[s[i]];
    }
    return res;

}

void solve() {
    string s, t;
    cin >> s >> t;
    int n = s.size();
    string r1 = perm(s), r2 = perm(t);
    if (r1 == r2) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }


}


//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();



#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


Measured memory_bytes: 1300
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A, remain;
  cin >> N >> A;
  
  remain = N % 500;
 
  if (remain <= A) {
    cout << "Yes" << endl;
  }
  else { 
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <list>
#include <map>
#include <string>
#include <algorithm>

void a(std::istream& in)
{
    int a;
    in >> a;

    std::cout << a + a * a + a * a * a;
}

int main(int, char* [])
{
    a(std::cin);
    return 0;
}


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define lf long double
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef pair <ll,ll> ii;
typedef vector <ll> vi;
typedef vector <ii> vii;
typedef vector <bool> vb;
typedef vector <vector <ll> > vv;
typedef vector <vector <vector<ll> > > vvv;
typedef vector <string> vs;
typedef vector <lf> vf;
#define tr1(x) cerr << #x << ": " << x << endl
#define tr2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl
#define tr3(x,y,z) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define tr4(x,y,z,w) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#w<<": "<<w<<endl
#define trv(a) cerr<<#a<<": ";for(ll zz=0;zz<a.size();zz++) cerr<<a[zz]<<" ";cerr<<endl
#define trset(s) cerr<<#s<<": ";for(auto &i:s) cerr<<i<<" ";cerr<<"\n"
#define mod 1000000007ll
#define inf 9999999999999999ll
#define nl endl
#define sz(x) (ll)(x).size()
#define all(x) x.begin(), x.end()
#define modulo 998244353ll



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    n%=k;
    ll ans=n;
    ans=min(ans,abs(n-k));
    cout<<ans<<nl;
} 


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

using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define pb(x) push_back(x)
#define int long long

signed main(void) {
  int N, M;
  cin >> N >> M;

  int food[M];

  // init food
  rep(i, M) {
    food[i] = 0;
  }

  int K, A;
  rep(i, N) {
    cin >> K;
    rep(j, K) {
      cin >> A;
      food[A-1]++;
    }
  }

  int ans = 0;
  rep(i, M) {
    if (food[i] == N) {
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#define REP(i, n) for(long long int i=0; i<(n); i++)
#define FOR(i, a, n) for(long long int i=(a); i<(n); i++)
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<char> vc;

int main(){
    int N;
    cin>>N;
    vl A(N);
    vector<pair<ll, int>> B(N);
    REP(i, N){
        cin >> A[i];
        int tmp;cin>>tmp;
        B[i] = make_pair(tmp, i);
    }

    sort(B.begin(), B.end());
    string ans = "Yes";
    ll sum = 0l;
    REP(i, N){
        sum += A[B[i].second];
        if(sum > B[i].first){
            ans = "No";
            break;
        }
    }

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

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;

int main(){
    char x;
    cin>>x;
    if(x>='a'&&x<='z') puts("a");
    else puts("A");
}


Measured memory_bytes: 3548
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define dme cout<<"IMPOSSIBLE"<<endl;return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
//12:15~
const int mod=1e9+7;
const llint big=1e16+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
int main(void){
	llint a=2,b=1,n;cin>>n;n--;
	while(n--){b=a+b;a=b-a;}
	cout<<b<<endl;
}


Measured memory_bytes: 256
def main(N, Ls):
    L_max = max(Ls)
    L_sum = sum(Ls) - L_max
    if L_max < L_sum:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main(int(input()), list(map(int, input().split(' '))))

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
const int N=100001;
int fa[N],h,t,u,v,s,n,i,to;
set<int>S[N];
set<int>::iterator it;
map<pair<int,int>,int>ma;
pair<int,int>q[N];
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
	n=rd();
	for (i=1;i<=2*n-2;i++){
		u=rd();v=rd();
		S[u].insert(v);S[v].insert(u);
		ma[mp(u,v)]++,ma[mp(v,u)]++;
		if (ma[mp(u,v)]==2) q[t++]=mp(u,v);
	}
	for (i=1;i<=n;i++) fa[i]=i;
	while (h<t){
		u=find(q[h].first),v=find(q[h++].second);
		S[u].erase(v);S[v].erase(u);
		if (S[u].size()<S[v].size()) swap(u,v);
		for (it=S[v].begin();it!=S[v].end();it++){
			to=*it;
			S[to].erase(v);
			ma[mp(v,to)]=ma[mp(to,v)]=0;
			S[u].insert(to);S[to].insert(u);
			ma[mp(u,to)]++;ma[mp(to,u)]++;
			if (ma[mp(u,to)]==2) q[t++]=mp(u,to);
		}
		fa[v]=u;S[v].clear();
	}
	for (i=1;i<=n;i++) s+=fa[i]==i;
	puts(s==1?"YES":"NO");
}

Measured memory_bytes: 56576
#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
//#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;

struct edge {
    int to;
    int from;
    int cost;
};

vector<vector<edge>> G(2500 + 8);
vector<edge> es;
vector<ll> d(2500 + 8,0);
int V, E, p;

void shortest_path(int s){
    for (int i = 0; i < V;++i)
        d[i] = INF;
    d[s] = 0;
    REP(lo,V){
        bool update = false;
        for (int i = 0; i < E;i++){
            edge e = es[i];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if (!update)
            break;
    }
    ll old = d[V - 1];
    REP(lo, V)
    {
        bool update = false;
        for (int i = 0; i < E; i++)
        {
            edge e = es[i];
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost)
            {
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
        if (!update)
            break;
    }
    if (old != d[V-1]) d[V - 1] = 1;
    else if (-d[V-1] <= 0)
        d[V - 1] = 0;
}

int main()
{
    ciosup;
    cin >> V >> E >> p;
    REP(i,E){
        int a,b,c;
        cin >> a >> b >> c;
        --a;
        --b;
        edge e;
        e.to = b;
        e.from = a;
        e.cost = p - c;
        es.emplace_back(e);
    }
    shortest_path(0);
    cout << -d[V - 1] << endl;
}

Measured memory_bytes: 512
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp3
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var days = int.Parse(Console.ReadLine());

            var scoreDownCoefficients = Console.ReadLine().Split(" ")
                .Select((x, i) => (score: int.Parse(x), questionNumber: i + 1))
                .OrderByDescending(x => x.score)
                .ToDictionary(x => x.questionNumber, x => x.score);

            Hoge(days, scoreDownCoefficients);
        }

        private static void Hoge(int days, IReadOnlyDictionary<int, int> scoreDownCoefficients)
        {
            var lastDictionary = new Dictionary<int, int>();

            foreach (var today in Enumerable.Range(1, days))
            {
                var downScoreDictionary = GetAll(today, lastDictionary, scoreDownCoefficients);

                var scoreUpNumber = Console.ReadLine().Split(" ")
                    .Select((score, i) => (score: int.Parse(score), questionNumber: i + 1))
                    .OrderByDescending(x =>
                    {
                        lastDictionary.TryGetValue(x.questionNumber, out var lastHeld);

                        return x.score - downScoreDictionary.Values.Sum() + downScoreDictionary[x.questionNumber];
                    })
                    .First();

                lastDictionary[scoreUpNumber.questionNumber] = today;

                Console.WriteLine(scoreUpNumber.questionNumber);
            }
        }

        private static Dictionary<int, int> GetAll(int today, Dictionary<int, int> lastDictionary, IReadOnlyDictionary<int, int> scoreDownCoefficients)
        {
            return Enumerable.Range(1, 26).Select(x =>
                {
                    lastDictionary.TryGetValue(x, out var lastHeld);
                    return (QuestionNumber: x, DownScore: (today - lastHeld) * scoreDownCoefficients[x]);
                })
                .ToDictionary(x => x.QuestionNumber, x => x.DownScore);
        }
    }
}


Measured memory_bytes: 30296
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

#define INF (i64)(1e18)
#define MOD (i64)(1e9+7)
#define REP(i, n) for(i64 i = 0; i < (n); i++)
#define RREP(i, n) for(i64 i = (n)-1; i >= 0; i--)
#define RANGE(i, a, b) for(i64 i = (a); i < (b); i++)
#define RRANGE(i, a, b) for(i64 i = (b)-1; i >= (a); i--)
#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) ((i64)(v).size())
template<class T> inline void chmax(T &a, const T &b) { if (a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if (a > b) a = b; }

int main() {
  string s;
  cin >> s;
  string t = "";
  int ans = 0;
  REP(i, SIZE(s)) {
    if (SIZE(t) == 0 || s[i] == t.back()) {
      t.push_back(s[i]);
    } else {
      t.pop_back();
      ans++;
    }
  }
  cout << ans * 2 << endl;

  return 0;
}


Measured memory_bytes: 3760
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
a, b, x = MAP()
y = 2*x/b/a
h = x/(a**2)
left = b-h

if x <= a*a*b/2:
    print(degrees(atan(b/y)))
else:
    print(degrees(atan(2*left/a)))


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

int main(){
    int N , M;
    cin >> N >> M;
    int s[M];
    char c[M];
    //cout << N << " " << M << endl;
    for(int i = 0; i < M; i++){
        cin >> s[i] >> c[i];
      //  cout << s[i] << " " << c[i] << endl;
    }

    for(int i = 0; i < 1000; i++){
        int num = to_string(i).length();
        if(num == N){
            int count = 0;
            for(int j = 0; j < M; j++){
                string str = to_string(i);
                if( str[s[j] - 1 ] == c[j]){
                    count += 1;
                }
            }
            if(count == M){
                cout << i << endl;
                return 0;
            }
        }

    }
    cout << -1 << endl;
}

Measured memory_bytes: 256