akhauriyash/Code-Regression huggingface dataset:
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <algorithm>
#include <functional>
#include <utility>
#include <string>
#define typeof(x) __typeof__(x)
#define int long long int
#define double long double
#define mod(x) ((x % MOD) + MOD) % MOD
#define ceil(x,m) ((x)+(m)-1)/(m)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);--i)

#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) UB(c,x)-LB(c,x)
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (s).find(e)!=(s).end()
#define PB push_back
#define MP make_pair
#define vec vector

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

using namespace std;

typedef pair<int,int> P;
struct edge { int to, cost; };

const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator << (ostream& s, const vector<T>& v) {
   int len = v.size();
   s << "[";
   for (int i = 0; i < len; i++) { s << v[i]; if (i < len - 1) s << " "; }
   s << "]";
   return s;
}

signed main()
{
   int N, K; cin >> N >> K;
   vec<vec<int>> b(K+1, vec<int>(K+1,0)), w(K+1, vec<int>(K+1, 0));
   int x, y, flag; char c;
   rep(i, 0, N) {
      cin >> x >> y >> c;
      flag = ((x/K) + (y/K) + (c=='W')) & 1;
      x %= K; y %= K;
      if (flag) {
         w[x+1][y+1] += 1;
      } else {
         b[x+1][y+1] += 1;
      }
   }

   rep(i, 0, K) {
      rep(j, 0, K) {
         b[i+1][j+1] += b[i+1][j] + b[i][j+1] - b[i][j];
         w[i+1][j+1] += w[i+1][j] + w[i][j+1] - w[i][j];
      }
   }

   int MAX = 0;
   rep(i, 0, K) {
      rep(j, 0, K) {
         MAX = max(MAX,
               (b[K][K] - b[i+1][K] - b[K][j+1] + 2*b[i+1][j+1]) +
               (w[i+1][K] + w[K][j+1] - 2*w[i+1][j+1]) );
         MAX = max(MAX,
               (w[K][K] - w[i+1][K] - w[K][j+1] + 2*w[i+1][j+1]) +
               (b[i+1][K] + b[K][j+1] - 2*b[i+1][j+1]) );
      }
   }
   cout << MAX << endl;
   return 0;
}


Measured memory_bytes: 16000
import time

start = time.time()

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
B = [0]*N
days = 0
games_amount = 0

for i in range(N*(N-1)//2):
    games = 0
    played = set()
    for j in range(N):
        if len(A[j]) == 0 or j in played or A[j][0] in played:
            continue
        if A[A[j][0]][0] == j:
            t1 = A[j].pop(0)
            played.add(t1)
            played.add(A[t1].pop(0))
            games += 1
            games_amount += 1
    if games == 0:
        print(-1)
        exit(0)
    else:
        days += 1
    if games_amount == N*(N-1)//2:
        break
    if time.time() - start > 1.9:
        print(N*(N-1)//2)
        exit(0)
print(days)

Measured memory_bytes: 35056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn for(int i=0;i<n;i++)
#define pb push_back
#define pob pop.back()
int main()
{
    int n;
    cin>>n;
    string t,s;
    set<string> ss;
    cin>>s;
    int m;
    for(int i=1;i<n;i++)
    {
         ss.insert(s);
        t=s;
        cin>>s;
         if(t[t.size()-1]!=s[0] || ss.count(s)) {cout<<"No"; return 0;}
    }
    cout<<"Yes";
    return 0;
    
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int  i = a; i <= (n); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
#define init(n) int n;cin>>n;int a[n];rep(i,n)cin>>a[i];
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long int> vll;
typedef vector<pii> vii;
ll mod=1000000007;
ll add(ll a,ll b){
    return (a+b)%mod;
}
ll mul(ll a, ll b){
    return (a*b)%mod;
}
struct node
{
    ll x,y;    
};
int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);   
    // freopen("output.txt", "w", stdout);
    // #endif
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T;T=1;
    // cin>>T;
    while(T--){
        int a,b;cin>>a>>b;
        if(a!=1&&b!=1)cout<<1;
        if(a!=2&&b!=2)cout<<2;
        if(a!=3&&b!=3)cout<<3;
    }
    return 0;   
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

void solve(){
  long long n, s = 0; cin >> n;
  vector<int> a(n), ans(n);
  for(int i = 0; i < n; i++){
    cin >> a[i];
    if(i % 2 == 0) s += a[i];
    else s -= a[i];
  }
  ans[0] = s;
  for(int i = 1; i < n; i++){
    s = -(s - a[i - 1]) + a[i - 1];
    //cout << a[i - 1] << endl;
    //cout << s << endl;
    ans[i] = s;
  }
  for(int i = 0; i < n; i++){
    cout << ans[i] << " ";
  }
  cout << endl;
  return;
}

int main(){
  solve();
  return 0;
}


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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> ans(m+1, 0);
    for(int i = 0; i < n; i++){
        int k;
        cin >> k;
        for(int j = 0; j < k; j++){
            int a;
            cin >> a;
            ans[a]++;
        }
    }

    int ans0 = 0;
    for(int i = 1; i <= m; i++){
        if(ans[i] == n) ans0++;
    }
    cout << ans0 << endl;
    return 0;
}

Measured memory_bytes: 3588
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))

int s[26];
int main(){
	while(1){
		char c=getchar();
		if(c==10)break;
		s[c-'a']++;
	}
	rep(i,0,26)if(!s[i]){
		putchar('a'+i);
		return 0;
	}
	puts("None");
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
  int n;
  cin >> n;
  ll ans=1;
  vector<ll> a(n);
  bool ok=false;
  for(int i=0;i<n;++i){
    cin >> a[i];
    if(a[i]==0){
      ok=true;
    }
  }

  if(ok){
    cout << "0" << endl;
    return 0;
  }
  ll m1=pow(10,9);
  ll m2=pow(10,9);
  ll keta1=0;
  ll keta2=0;
  ll tmp;
  for(int i=0;i<n;++i){
    if(ans>m1 && a[i]>m2){
      cout << "-1" << endl;
      return 0;
    }else if(ans*a[i]>m1*m2){
      cout << "-1" << endl;
      return 0;
    }
    ans=ans*a[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4048
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <tuple>
#include <queue>
#include <set>
#include <cstdio>
#include <climits>
#include <cmath>
#include <array>
#include <functional>
#include <list>
#include <iomanip>
#include <set>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const double eps=1e-9;
const int inf=1e9;
typedef pair<int,int> P;
struct edge{int u,v,cost;};
int V,E;
list<int> out;
vi G[100005];
bool visited[100005];
int N;
int indeg[100005];
void bfs(int s)
{
  queue<int> q;
  q.push(s);
  visited[s]=true;
  while(!q.empty())
    {
      int u=q.front();q.pop();
      out.push_back(u);
      for(int i=0;i<G[u].size();i++)
	{
	  int v=G[u][i];
	  indeg[v]--;
	  if(indeg[v]==0 && !visited[v])
	    {
	      visited[v]=true;
	      q.push(v);
	    }
	}
    }
}

void tsort()
{
  for(int i=0;i<V;i++)
    {
      indeg[i]=0;
    }
  for(int u=0;u<V;u++)
    {
      for(int i=0;i<G[u].size();i++)
	{
	  int v=G[u][i];
	  indeg[v]++;
	}
    }
  for(int u=0;u<V;u++) if(indeg[u]==0 && !visited[u]) bfs(u);
  for(list<int>::iterator it=out.begin();it!=out.end();it++)
    {
      cout << *it << endl;
    }
}

int main(void)
{
  cin >> V >> E;
  for(int i=0;i<E;i++)
    {
      int s,t;
      cin >> s >> t;
      G[s].push_back(t);
    }
  tsort();
  return 0;
}



Measured memory_bytes: 6116
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast,no-stack-protector") 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>


#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(i, l, r) for (int i = l; i < r; i++)
#define repb(i, r, l) for (int i = r; i > l; i--)
#define sz(a) (int)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp(a, b) make_pair(a, b)
#define ret(a) {cout << a; exit(0);}

using namespace std;

mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

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

const int N = 2e5 + 1;
bool ok[5][300];
main(){
	string s;
	cin >> s;
	s = '$' + s;
	ok[1]['R'] = ok[1]['U'] = ok[1]['D'] = 1;
	ok[0]['L'] = ok[0]['U'] = ok[0]['D'] = 1;
	for(int i = 1 ; i < sz(s) ; i++)
		if(!ok[i&1][s[i]]){
			ret("No");
		}
	cout << "Yes";
		
	s = '$' + s;
		
}

Measured memory_bytes: 256
use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let h_a = lines.next().unwrap().unwrap();
    let mut h_a = h_a.split_whitespace();
    let h: i32 = h_a.next().unwrap().parse().unwrap();
    let a: i32 = h_a.next().unwrap().parse().unwrap();
    let ans = if h % a == 0 { h / a } else { h / a + 1 };
    println!("{}", ans);
}


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

int main(){
   int n,ans=0,mx=0;
   scanf("%d",&n);
  
  vector<int> h(n);
  cin >> h[0];
  rep(i,n){
    cin >> h[i];
    if(h[i-1]>=h[i]) ans ++;
    else {
      mx = max(mx,ans);
      ans =0;
    }
  }
   cout << max(mx,ans);
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
	int l,r,d;
	cin>>l>>r>>d;
	int ans=0;
	for(int i=l;i<=r;i++){
		if(i%d==0){
			ans++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3532
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
int main() {
  int n,k,count=0;
  string s;
  vector<int>si,so;
  cin >> n >> k>>s;
  char c=s[0];
  if(c=='0')
    si.push_back(0);
  rep(i,n){
    if (c==s[i]) {
      count++;
    } else {
      if (c == '0')
        so.push_back(count);
      else
        si.push_back(count);
      count=1;
      c=s[i];
    }
  }
  if (c == '0'){
    so.push_back(count);
    si.push_back(0);
  }else
    si.push_back(count);
  int ss=so.size();
  if(ss<=k){
     cout<<n; 
  }else{
    int sum=0;
    rep(i,k)
      sum+=si[i]+so[i];
    sum+=si[k];
    int ans=sum;
    for(int i=k;i<ss;i++){
       sum+=si[i+1]+so[i]-(si[i-k]+so[i-k]);
       ans=max(ans,sum); 
    }
    cout<<ans;
  }
  return 0;
}


Measured memory_bytes: 1020
def main():
    M=10**9+7
    N=10**5*2
    fac=[0]*(N+1)
    fac[0]=b=1
    for i in range(1,N+1):fac[i]=b=b*i%M
    inv=[0]*(N+1)
    inv[N]=b=pow(fac[N],M-2,M)
    for i in range(N,0,-1):inv[i-1]=b=b*i%M
    n,*t=open(0).read().split()
    n=int(n)
    e=[[]for _ in range(n)]
    for a,b in zip(*[map(int,t)]*2):
        e[a-1]+=b-1,
        e[b-1]+=a-1,
    o=[]
    s=[0]
    f=[1]*n
    while s:
        v=s.pop()
        f[v]=0
        o+=v,
        l=[]
        for w in e[v]:
            if f[w]:
                l+=w,
                s+=w,
        e[v]=l
    sz1,sz2=[0]*n,[0]*n
    dp1,dp2=[0]*n,[0]*n
    c=[[]for _ in range(n)]
    for v in o[::-1]:
        s=b=1
        c1,c2=[1],[1]
        for w in e[v]:
            u=sz1[w]
            b=b*dp1[w]*inv[u]%M
            c1+=b,
            s+=u
        b=1
        for w in e[v][::-1]:
            b=b*dp1[w]*inv[sz1[w]]%M
            c2+=b,
        c[v]=c1,c2[-2::-1]
        sz1[v]=s
        dp1[v]=b*fac[s-1]%M
    # print(dp1)
    sz2[0]=1
    dp2[0]=1
    for v in o:
        l=len(e[v])
        c1,c2=c[v]
        uv=sz2[v]-1
        tv=dp2[v]*inv[uv]
        uv+=sz1[v]
        for w,l,r in zip(e[v],c1,c2):
            tw=l*r%M
            uw=uv-sz1[w]-1
            dp2[w]=tv*tw*fac[uw]%M
            sz2[w]=uw+2
    # print(dp2)
    a=[]
    for dp1,dp2,sz1,sz2 in zip(dp1,dp2,sz1,sz2):
        sz1-=1
        sz2-=1
        a+=str(dp1*dp2*inv[sz1]*inv[sz2]*fac[sz1+sz2]%M),
    print('\n'.join(a))
main()

Measured memory_bytes: 169452
N=int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort(reverse=True)
Arev=sorted(A, reverse=True)
Brev=sorted(B)
atai=0
s=0
for i in range(len(A)):
    if A[i]==B[i]:
        atai=A[i]
        s+=1
C=[]
for i in range(len(A)):
    C.append(A[i]-B[i])
if s>0:
    hajime=C.index(0)
if s==0:
    print("Yes")
    print(*B)
else:
    Acount=A.count(atai)
    Bcount=B.count(atai)
    if N-Acount<Bcount:
        print("No")
    else:
        afirst=A.index(atai)
        alast=N-1-Arev.index(atai)
        bfirst=B.index(atai)
        blast=N-1-Brev.index(atai)
        t=min(afirst,bfirst)
        if t>=s:
            for i in range(0,s):
                B[hajime+i]=B[i]
                B[i]=atai
        else:
            for i in range(0,t):
                B[hajime+i]=B[i]
                B[i]=atai
            ss=s-t
            for i in range(0,ss):
                B[hajime+t+i]=B[-i-1]
                B[-i-1]=atai
        print("Yes")
        print(*B)

Measured memory_bytes: 41876
a,b=map(int,input().split())
s=list(input())
a_i=s[0:a]
b_i=s[a+1:]
ans=""
for i in range(a):
    ans+=a_i[i]
for i in range(b):
    ans+=b_i[i]
if s[a]=="-" and ans.isdigit():
    print("Yes")
else:
    print("No")
    

Measured memory_bytes: 3060
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"
 
using namespace std;
 
constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-9;
 
//int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;
 
void Calculate_Depth(vector<vector<int>>&edge, vector<int>&depth, int stnode) {
	depth[stnode] = 0;
	queue<int>Q;
	Q.push(stnode);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto i : edge[cn]) {
			if (depth[i] > depth[cn] + 1) {
				depth[i] = depth[cn] + 1;
				Q.push(i);
			}
		}
	}
	return;
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
 
	cin >> N >> M;
	vector<vector<int>>edge(N);
	for (int i = 0; i < M; i++) {
		cin >> L >> R;
		L--, R--;
		edge[L].push_back(R);
		edge[R].push_back(L);
	}
	vector<int>dis(N, MOD);
	Calculate_Depth(edge, dis, 0);
	cout << "Yes\n";
	for (int i = 1; i < N; i++) {
		for (auto j : edge[i]) {
			if (dis[j] == dis[i] - 1) {
				cout << j + 1 << endl;
				break;
			}
		}
	}
}

Measured memory_bytes: 10256
#include<bits/stdc++.h>
using namespace std;
 int flag=0;
int main()
{

   int n,m;
   cin>>n;
   char s[n];
   cin>>s;
   if(n%2!=0) cout<<"No"<<endl;
   else {
   for(int i=0;i<n/2;i++)
   {
       if(s[i]!=s[i+n/2] )flag=1;
   }
   if(flag==1) cout<<"No"<<endl;
   else cout<<"Yes"<<endl;
   }
   return 0;


}


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

#define mod 1000000007

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

using namespace std;
typedef long long ll;
const long long INF = 1LL << 60;

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

int main(void){
	
	int N;
	
	cin >> N;
	
	int h[N];
	
	rep(i, N)
		cin >> h[i];

	ll dp[N];

	rep(i, N) 
		dp[i] = INF;

	dp[0] = 0;

	rep(i, N){
		chmin(dp[i], dp[i-1] + abs(h[i] - h[i-1]));
		if(i > 1)
			chmin(dp[i], dp[i-2] + abs(h[i] - h[i-2]));
	}

	cout << dp[N-1] << endl;
	
	return 0;
}

Measured memory_bytes: 1408
# coding: utf-8

count = int(input())
numbers = [int(i) for i in input().rstrip().split(" ")]
average = sum(numbers) / count

def calc_single_cost(x, y):
    return (x - y) ** 2

def calc_total_cost(avg, targets):
    cost = 0
    for x in targets:
        cost += calc_single_cost(avg, x)
    return cost

cost = []
for candidate in [int(average), int(average) + 1]:
    cost.append(calc_total_cost(candidate, numbers))

print(min(cost))



Measured memory_bytes: 3316
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in);) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        String a = sc.next();
        System.out.println(a.replaceAll(",", " "));
    }
}

Measured memory_bytes: 23124
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long N = long.Parse(str[0]);
		long X = long.Parse(str[1]);
		long[]A = new long[N];
		string[] str2 = Console.ReadLine().Split();
		long ct = 0;
		long ans = 1;
		for(var i=0;i<N;i++){
			A[i] = long.Parse(str2[i]);
			ct+=A[i];
			if(ct<=X){
				ans++;
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 13140
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    ll n; cin >> n;
    vector<ll> h(n+2,0);
    rep(i,n) cin >> h[i+1];
    ll ret = 0;
    const int h_max = 110;
    for(int i = 1; i < h_max; i++){
        ll temp = 0;
        rep(j,n+1){
            if(h[j] < i && i <= h[j+1])temp++;
        }
        ret += temp;
    }

    cout << ret << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<vector<ll>> matrix;//matrix A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
typedef vector<bool> vb;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(b<a){a=b;return 1;}return 0;}
ll llpow(ll e,ll x){ll res=1LL;while(x){if(x&1)res*=e;e*=e;x/=2;}return res;}
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007 //998244353



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

    // solution comes here

    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    ll X = abs(a-c), Y=abs(d-b);
    rep(i, Y) cout << "U";
    rep(i, X) cout << "R";
    rep(i, Y) cout << "D";
    rep(i, X+1) cout << "L";

    rep(i, Y+1) cout << "U";
    rep(i, X+1) cout << "R";
    cout << "DR";
    rep(i, Y+1) cout << "D";
    rep(i, X+1) cout << "L";
    cout << "U" << nl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <numeric>
#include <limits>
#include <type_traits>
#include <locale>

using namespace std;
#define SAY_YES cout << "YES" << endl;
#define SAY_Yes cout << "Yes" << endl;
#define SAY_NO cout << "NO" << endl;
#define SAY_No cout << "No" << endl;
#define IFYES(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "YES" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "NO" << endl;  \
    }
#define IFYes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "Yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "No" << endl;  \
    }
#define IFyes(TRUE_OR_FALSE)   \
    if (TRUE_OR_FALSE)         \
    {                          \
        cout << "yes" << endl; \
    }                          \
    else                       \
    {                          \
        cout << "no" << endl;  \
    }
#define DEBUG_OUTPUT_ARRAY(XXX, ONE)                            \
    for (int i = 0; i < (ONE); i++)                             \
    {                                                           \
        cout << "DEBUG: i = " << i << " -> " << XXX[i] << endl; \
    }
#define DEBUG_OUTPUT_ARRAY2(XXX, ONE, TWO)                             \
    for (int i = 0; i < (ONE); i++)                                    \
    {                                                                  \
        cout << "<<< i = " << i << " >>>" << endl;                     \
        for (int j = 0; j < (TWO); j++)                                \
        {                                                              \
            cout << "DEBUG: j = " << j << " -> " << XXX[i][j] << endl; \
        }                                                              \
    }
#define DEBUG_OUTPUT_ARRAY2_BOX(XXX, ONE, TWO) \
    for (int i = 0; i < (ONE); i++)            \
    {                                          \
        cout << i << "  ";                     \
        for (int j = 0; j < (TWO); j++)        \
        {                                      \
            cout << XXX[i][j] << " ";          \
        }                                      \
        cout << endl;                          \
    }

typedef pair<long long int, long long int> pll;


const long long int mod = 1000000007;
const long long int INF = 1e18;
const long double PI=3.14159265358979323; 

long long int N,M,A[200020],memo[200200]={};
string S;

long long int sum(long long int x){
    return x*(x+1)/2;
}
int main()
{
    cout << fixed << setprecision(18);
    cin>>N;
    cout<<sum(N)-3*sum(N/3)-5*sum(N/5)+15*sum(N/15)<<endl;

}    


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#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 FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};



ll n;
map<pair<string, ll>, ll> memo;
bool notHaveAGC(string s){
  bool ans = true;
  REP(i, 4){
    string t = s;
    if(i != 0){
      char tmp = t[i-1];
      t[i-1] = t[i];
      t[i] = tmp;
    }

    ll pos = t.find("AGC");
    if(pos != string::npos)
      ans = false;
  }

  return ans;
}



ll  dfs(string s, ll cur){
  if(memo[make_pair(s, cur)] != 0)
    return memo[make_pair(s, cur)];
  if(cur == n)
    return 1;

  ll sum = 0;
  string target = "ATCG";
  string last3 = s.substr(1, 3);
  REP(i, target.size()){
    if(notHaveAGC(last3+target[i]))
      sum += dfs(last3+target[i], cur+1);
    sum %= MOD;
  }


  memo[make_pair(s, cur)] = sum;
  return sum;
}



int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n;
  ll ans = dfs("TTTT", 0);
  cout << ans << endl;

}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
typedef long long ll;
//ll par[2000010],sizem[2000010],sizel[2000010],size[2000010],a,b,q1,q2,q3,x,y;
ll a[100005],n;
ll dp[3001][3001][3];
ll solve(ll i,ll j,ll player=1)
{
	if(i>j)
		return 0;
	if(i>n)
		return 0;
	if(j<1)
		return 0;
	ll maxi = -1;
	ll max2 = -1;
	if(dp[i][j][player]!=-1)
		return dp[i][j][player];
	ll &ans = dp[i][j][player];
	if(player==1)
		ans=max(a[i]+solve(i+1,j,2),a[j]+solve(i,j-1,2));
	if(player==2)
		ans=min(-a[j]+solve(i,j-1,1),-a[i]+solve(i+1,j,1));
	return ans;
}

int main()
{
	cin>>n;
	for (int i = 1; i <= n; ++i)
	{
		cin>>a[i];
	}
	memset(dp,-1,sizeof(dp));
	cout<<solve(1,n,1)<<endl;
	return 0;
}

Measured memory_bytes: 211584
#include <bits/stdc++.h>
using namespace std;
int main(){
    string o="",e="";
    cin >> o >> e;
    
    int all = o.size();
    
    for(int i=0;i < o.size();i++){
        cout << o[i];
        if(i < e.size())cout << e[i];
    }
    
    return 0;
}


Measured memory_bytes: 3604
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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; }

const int MAX_DP = 1000000000;

int main()
{	
	int H, W;
	cin >> H >> W;

	vector<string> S(H);

	rep(i, H)
	{
		cin >> S[i];
	}

	//dp[i][j] := (i, j)に行くまでのコストの最小値
	vector<vector<int>> dp(H, vector<int>(W, MAX_DP));

	dp[0][0] = S[0][0] == '#' ? 1 : 0;

	rep(i, H)
	{
		rep(j, W)
		{
			//左方向から
			if (j > 0)
			{
				int fromLeft = dp[i][j - 1];
				if (S[i][j - 1] == '.' && S[i][j] == '#') fromLeft++;

				chmin(dp[i][j], fromLeft);
			}

			//上方向から
			if (i > 0)
			{
				int fromTop = dp[i - 1][j];
				if (S[i - 1][j] == '.' && S[i][j] == '#') fromTop++;

				chmin(dp[i][j], fromTop);
			}
		}
	}

	cout << dp[H - 1][W - 1] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int D;
  cin>>D;
  vector<int> c(26);
  for(int &i:c)
    cin>>i;
  vector<vector<int>> s(D,vector<int>(26));
  for(vector<int> &v:s)
    for(int &i:v)
      cin>>i;
  vector<int> t(D);
  vector<int> A(26,0);
  int mzint=0;
  for(int i=0;i<D;i++){
    int mzi=mzint,mzin=0,k;
    for(int j=0;j<26;j++)
      mzi-=(i+1-A[j])*c[j];
    for(int j=0;j<26;j++){
      int l=mzi+s[i][j]-(i+1-A[j])*c[j];
      if(l>mzin){
        k=j;
        mzin=l;
      }
    }
    A[k]=i+1;
    mzint=mzin;
    t[i]=k+1;
  }
  int M=18000000,ans=mzint;
  while(M--){
    int d=rand()%D,q=rand()%26,ans2=ans;
    ans+=s[d][q]-s[d][t[d]-1];
    int mae=-1,ato=D;
    for(int i=d-1;i>=0;i--){
      if(t[i]==t[d]){
        mae=i;
        break;
      }
    }
    for(int i=d+1;i<D;i++){
      if(t[i]==t[d]){
        ato=i;
        break;
      }
    }
    ans-=(ato-d)*(d-mae)*c[t[d]-1];
    mae=-1,ato=D;
    for(int i=d;i>=0;i--){
      if(t[i]==q+1){
        mae=i;
        break;
      }
    }
    for(int i=d;i<D;i++){
      if(t[i]==q+1){
        ato=i;
        break;
      }
    }
    ans+=(ato-d)*(d-mae)*c[q];
    if(ans2<ans)
      t[d]=q+1;
    else
      ans=ans2;
  }
  for(int i:t)
    cout<<i<<endl;
}

Measured memory_bytes: 3700
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define MAXSIZE 200
#define MAXL 100
typedef long long int lli;

int main(){
    lli k, a, b;
    cin >> k >> a >> b;

    lli ans = 1;
    if(b - a < 3){
        cout << 1 + k << endl;
    }else{
        while(ans < a){
            ans++;
            k--;
            if(k == 0){
                break;
            }
        }

        if(k > 0){
            if(k % 2 == 0){
                ans += (b - a) * k / 2;
            }else{
                ans += (b - a) * (k - 1) / 2 + 1;
            }
        }   
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;

int main()
{
    vector<int> A(3);
    for(int i=0; i<3; i++) cin >> A[i];
    int S = 0;
    for(int i=0; i<3; i++) S+=A[i];
    if(S >= 22) cout << "bust\n";
    else cout << "win\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rv[30];
struct node{
  int id,left,right,par,sib,deg,dep,hei;
  string type;
  node(){par=sib=-1;}
  string val(){
    string res;
    res+="node "+to_string(id);
    res+=": parent = " +to_string(par);
    res+=", sibling = "+to_string(sib);
    res+=", degree = " +to_string(deg);
    res+=", depth = "  +to_string(dep);
    res+=", height = " +to_string(hei);
    res+=", "+type;
    return res;
  }
};
node t[30];
int dfs(int v,int d){
  t[v].dep=d;
  t[v].type="internal node";
  if(~t[v].left&&~t[v].right){
    t[rv[t[v].left ]].sib=t[v].right;
    t[rv[t[v].right]].sib=t[v].left;
    t[v].deg=2;
    return t[v].hei=max(dfs(rv[t[v].left],d+1),dfs(rv[t[v].right],d+1))+1;
  }else if(~t[v].left){
    t[v].deg=1;
    return t[v].hei=dfs(rv[t[v].left ],d+1)+1;
  }else if(~t[v].right){
    t[v].deg=1;
    return t[v].hei=dfs(rv[t[v].right],d+1)+1;
  }else{
    t[v].type="leaf";
    t[v].deg=0;
    return t[v].hei=0;
  }
}
signed main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++) cin>>t[i].id>>t[i].left>>t[i].right;
  for(int i=0;i<n;i++) rv[t[i].id]=i;
  for(int i=0;i<n;i++){
    //cout<<t[i].id<<":"<<t[i].left<<":"<<t[i].right<<endl;
    if(~t[i].left)  t[rv[t[i].left ]].par=t[i].id;
    if(~t[i].right) t[rv[t[i].right]].par=t[i].id;
  }
  for(int i=0;i<n;i++) if(t[i].par==-1) dfs(i,0),t[i].type="root";
  for(int i=0;i<n;i++) cout<<t[rv[i]].val()<<endl;
  return 0;
}

Measured memory_bytes: 3292
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;

int main(){
    string s;cin>>s;
    int K;cin>>K;
    REP(i,s.size()){
        if(s[i]!='a'&&K>='z'-s[i]+1){
            K-='z'-s[i]+1;
            s[i]='a';
        }
        if(i+1==s.size()){
            s[i]=(s[i]-'a'+K%26)%26+'a';
        }
    }
    cout<<s<<endl;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main()
{
	long long A[100][100] = {},
		      B[100][100] = {},
			  v;

	int n, m, l, i, j, k;
	cin >> n >> m >> l;
	
	for(i = 0; i < n; ++i){
		for(j = 0; j < m; ++j){
			cin >> A[i][j];
		}
	}

	for(i = 0; i < m; ++i){
		for(j = 0; j < l; ++j){
			cin >> B[i][j];
		}
	}

	for(i = 0; i < n; ++i){
		for(j = 0; j < l; ++j){
			v = 0;
			for(k = 0; k < m; ++k){
				v += A[i][k] * B[k][j];	
			}
			cout << v;
			if( j != l -1 )
				cout << " ";
		}
		cout << "\n";
	}

	return 0;
}

Measured memory_bytes: 1328
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define MOD 1000000007
const int INF = 1LL<<30;

int main(){
    int n;
    cin>>n;
    vector<ll> l(n),h(n);
    rep(i,n) cin>>l[i],h[i]=l[i];
    sort(all(h));
    ll a=h[n/2],b=h[n/2-1];

    //cout<<a<<" "<<b<<endl;
    rep(i,n){
        if(l[i]<=b) cout<<a<<endl;
        else cout<<b<<endl;
    }
    
}

Measured memory_bytes: 6372
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int digit(int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += x % 10;
		x /= 10;
	}
	return cnt;
}

bool x[4];

signed main() {
	int a, b;
	cin >> a >> b;
	cout << lcm(a, b) << endl;

	return 0;
}


Measured memory_bytes: 256
// #include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <climits>
#include <string>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <ctime>
#include <cassert>
#include <fstream>
#include <stack>
#include <random>
#include <atcoder/mincostflow>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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

template<typename T>
void vdeb(std::vector<T> &da) {
    for (int i = 0;i < da.size();i++) {
        if (i == da.size() - 1) std::cout << da[i];
        else std::cout << da[i] << ' ';
    }
    std::cout << '\n';
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
    for (int i = 0;i < da.size();i++) {
        std::cout << i << ' ';
        vdeb(da[i]);
    }
    std::cout << '\n';
}

using namespace std;
namespace ac = atcoder;

const ll ML = 1000000000;

int main() {
    int n, k;cin >> n >> k;
    vector<vector<ll>> da(n, vector<ll>(n));
    ac::mcf_graph<int, ll> g(n*2+2);
    rip(i,n,0) rip(j,n,0) {
        cin >> da[i][j];
        g.add_edge(i, j+n, 1, ML-da[i][j]);
    }
    rip(i,n,0) {
        g.add_edge(n*2, i, k, 0);
        g.add_edge(i+n, n*2+1, k, 0);
    }
    auto cp = g;
    auto ta = g.slope(n*2, n*2+1);
    pair<int, long long> me;
    for(auto i:ta) {
        if(chmax(me.second, ML*i.first-i.second)) me.first = i.first;
    }
    cp.flow(n*2, n*2+1, me.first);
    vector<string> ans(n, "");
    rip(i,n,0) rip(j,n,0) {
        if(cp.get_edge(i*n+j).flow) ans[i] += 'X';
        else ans[i] += '.'; 
    }
    cout << me.second << '\n';
    rip(i,n,0) cout << ans[i] << '\n';
}

Measured memory_bytes: 4096
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
const int maxn = 100005;

char S[maxn], RS[maxn];
using pii = std::pair<int, int>;
std::vector<pii> E;
int main() {
  scanf("%s", S + 1);
#ifdef LOCAL
  puts(S + 1);
#endif
  int n = strlen(S + 1);
  if(S[1] == '0' || S[n] == '1') {
    puts("-1"); return 0;
  }
  std::copy(S + 1, S + n, RS + 1);
  std::reverse(RS + 1, RS + n);
  for(int i = 1; i < n; i ++) {
    if(RS[i] != S[i]) {
      puts("-1"); return 0;
    }
  }
  int las = 1, lv = 1, cnt = 1;
  for(int i = 2; i <= (n / 2); i ++) {
    if(S[i] == '1') {
      int np = ++ cnt;
      E.push_back({np, las});
      int c = i - lv - 1;
      while(c --) E.push_back({np, ++ cnt});
      lv = i; las = np;
    }
  }
  int rt = ++ cnt;
  E.push_back({las, rt});
  int c = n - lv - 1;
  while(c --) E.push_back({rt, ++ cnt});
  for(const pii &e : E) {
    printf("%d %d\n", e.first, e.second);
  }
  return 0;
}

Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
auto setmin   = [](auto & a, auto b) { return (b <  a ? a = b, true : false); };
auto setmax   = [](auto & a, auto b) { return (b >  a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
auto fl = [](auto a, auto b) { assert(b != 0); return a / b - (a % b != 0 && ((a >= 0) != (b >= 0)) ? 1 : 0); };
auto ce = [](auto a, auto b) { assert(b != 0); return a / b + (a % b != 0 && ((a >= 0) == (b >= 0)) ? 1 : 0); };
auto mo = [](auto a, auto b) { assert(b != 0); a %= b; if(a < 0) { a += abs(b); } return a; };
LL gcd(LL a, LL b) { return (b == 0 ? a : gcd(b, a % b)); }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
#define bit(b, i) (((b) >> (i)) & 1)
#define SI(v) static_cast<int>(v.size())
#define RF(e, v) for(auto & e: v)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)

// ---- ----

int main() {
	int n, x, y;
	cin >> n >> x >> y;
	x--; y--;
	vector<vector<int>> g(n);
	inc(i, n - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].PB(b);
		g[b].PB(a);
	}
	
	const int INF = n;
	vector<int> dy(n, INF);
	function<void(int, int, int)> dfs_y = [&](int v, int p, int d) {
		dy[v] = d;
		RF(e, g[v]) {
			if(e == p) { continue; }
			dfs_y(e, v, d + 1);
		}
	};
	
	vector<int> f(n, 0);
	function<void(int, int, int)> dfs_x = [&](int v, int p, int d) {
		if(d > dy[v]) { return; }
		f[v] = 1;
		RF(e, g[v]) {
			if(e == p) { continue; }
			dfs_x(e, v, d + 1);
		}
	};
	
	dfs_y(y, -1, 0);
	dfs_x(x, -1, 0);
	
	int ans = 0;
	inc(v, n) {
		if(SI(g[v]) >= 2 && f[v] == 1) { setmax(ans, dy[v]); }
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 12928
#include <cstdio>

using namespace std;

int main(){
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		int sum = 0;
		int m = i;
		while(m){
			sum += m % 10;
			m /= 10;
		}
		if(sum >= a && sum <= b)
			ans += i;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
  int64_t x;
  mint(int64_t x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(int64_t t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  //for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> frac, ifrac;
  combination(int n):frac(n+1), ifrac(n+1) {
    assert(n < mod);
    frac[0] = 1;
    for (int i = 1; i <= n; ++i) frac[i] = frac[i-1]*i;
    ifrac[n] = frac[n].inv();
    for (int i = n; i >= 1; --i) ifrac[i-1] = ifrac[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return frac[n]*ifrac[k]*ifrac[n-k];
  }
} c(1000000);

//head

int n, m;
mint ans1, ans2;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  ans1 = c.frac[m]*c.ifrac[m-n];
  rep(i, n+1) {
    ans2 += c(n, i) * c.frac[m-i] * c.ifrac[m-n] * (i&1?mod-1:1);
  }
  cout << ans1 * ans2 << endl;
}

Measured memory_bytes: 18592
#include<iostream>
using namespace std;
int main(){
    int n;
    int b,f,r,v;
    
    int dim[4][3][10] = {0};
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> b >> f >> r >> v;
        
        dim[b - 1][f - 1][r - 1] += v;
    }
    
    for(int i = 0; i < 3; i++){
        for(int j = 0; j <= 2; j++){
            for(int k = 0; k <=9; k++){
                cout << " " << dim[i][j][k];
            }
            
            cout << endl;
        }
        
        cout << "####################" << endl;
        
    }
    
    for(int j = 0; j <= 2; j++){
        for(int k = 0; k <=9; k++){
            cout << " " << dim[3][j][k];
        }
        
        cout << endl;
    }
}



Measured memory_bytes: 3088
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
const int mod=1e9+7;
int a[3001][3001];
int dp[3001][3001][4];
//dp[i][j][k]  reach till i,j and took only k elements in this row
void cmax(int &x, int y)
{
  x=max(x,y);
}
int32_t main()
{
  #ifndef ONLINE_JUDGE
  freopen("in","r",stdin);
  freopen("out","w",stdout);
  #endif

  int n,r,c;cin>>r>>c>>n;
  int r1,c1,v1;
  for(int i=0;i<n;i++)
  {
    cin>>r1>>c1>>v1;
    a[c1][r1]=v1;
  }


  for(int i=1;i<=c;i++)
   { for(int j=1;j<=r;j++)
    {
      dp[i][j][0]=dp[i-1][j][0];
      
      for(int k=0;k<=3;k++)
        {cmax(dp[i][j][0],dp[i][j-1][k]);cmax(dp[i][j][1],dp[i][j-1][k]+a[i][j]);}
    //  cout<<dp[i][j][0]<<" ";
      for(int k=1;k<=3;k++)
      {
        cmax(dp[i][j][k],dp[i-1][j][k]);
        cmax(dp[i][j][k],dp[i-1][j][k-1]+a[i][j]);
      }

    }
    
  }

   
    int ans=0;
    for(int i=0;i<4;i++)cmax(ans,dp[c][r][i]);
    cout<<ans;


  
  
 
  

}

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

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

    vector<bool> flag(105);
    rep(i, n) {
        int a;
        cin >> a;
        flag[a] = true;
    }

    int sa = k, ans = 0;
    rep(i, 105) {
        if (flag[i])
            continue;

        if (abs(i - k) < sa) {
            sa = abs(i - k);
            ans = i;
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main() {
  int N,M,X,Y;
  cin>>N>>M>>X>>Y;
  
  // 100要素の配列で初期化
  vector<int> x(N);
  vector<int>y(M);
  for(int i=0;i<N;i++)
    cin>>x.at(i);
  for(int i=0;i<M;i++)
    cin>>y.at(i);
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  int ans=0;
  int tmp=X+1;
  for(int i=X;i<Y;i++){
    if(x.at(N-1)<tmp&&y.at(0)>=tmp){
      cout<<"No War"<<endl;
      ans=1;
      break;
    }
    tmp++;
  }
  if(ans==0)
    cout<<"War"<<endl;
}
  



Measured memory_bytes: 256
from math import *
a,b,x=map(int,input().split())
ans=(a*a*b)
if(x>=ans/2):
	ans=ans-x
	ans=ans/(a**3)
	ans=ans*2
	ans=atan(ans)
	print(ans*180/pi)
else:
	ans=(a*b*b)/2
	ans=ans/x
	ans=atan(ans)
	print(ans*180/pi)



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }


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

 vector<int> A(N);

 for(int i = 0; i < N; i++) cin >> A[i];

  ll ans = 0;
  ll h = 0;
 for(int i = 0; i < N; i++) {
   if(i == 0) { h = A[i]; }
   if(A[i] > h) { h = A[i]; }
   else ans += h - A[i]; 
   
 }

 cout << ans;

  return 0;
}

Measured memory_bytes: 4036
#include <bits/stdc++.h>
#define maxn 100086

using namespace std;

typedef long long ll;

int n, m;
ll k, e[maxn];
int x[maxn], a[maxn];
int b[maxn], c[maxn], d[maxn];

int main(){
	scanf("%d", &n);
	for(int i = 1;i <= n;i++) scanf("%d", &x[i]), b[i] = d[i] = i;
	scanf("%d%lld", &m, &k);
	for(int i = 1;i <= m;i++) scanf("%d", &a[i]), swap(b[a[i]], b[a[i] + 1]);
	while(k){
		if(k & 1){
			for(int i = 1;i <= n;i++) c[i] = d[b[i]];
			for(int i = 1;i <= n;i++) d[i] = c[i];
		}
		for(int i = 1;i <= n;i++) c[i] = b[b[i]];
		for(int i = 1;i <= n;i++) b[i] = c[i];
		k >>= 1;
	}
	for(int i = 1;i <= n;i++) printf("%lld\n", e[i] = e[i - 1] + x[d[i]] - x[d[i] - 1]);
}

Measured memory_bytes: 6528
using System;
using System.Linq;

namespace ABC158
{
    class B
    {
        static void Main(string[] args)
        {
            var a = Console.ReadLine().Split().Select(long.Parse).ToArray();
            var N = a[0];
            var A = a[1];
            var B = a[2];

            if (N % (A + B) == 0) Console.WriteLine((N / (A + B)) * A);
            else if (N % (A + B) <= A) Console.WriteLine((N / (A + B)) * A + (N % (A + B)));
            else Console.WriteLine((N / (A + B)) * A + A);

        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
long double const pi = std::acos(-1.0L);
typedef pair<int,int> P;

int main() {
  int n; cin >> n;
  vector<int> a(n);
  int mod = 1000000007;
  ll sum = 0;
  rep(i,n){
    cin >> a[i];
    sum+=a[i];
    sum%=mod;
  }
  ll ans = 0;
  rep(i,n){
    sum-=a[i];
    if(sum<0)sum+=mod;
    ans+=a[i]*sum;
    ans%=mod;
    }
  cout << ans << endl;
  return 0;
}

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

int main(){
  int A,B,C,D,flag;
  flag = 0;
  cin >> A >> B >> C >> D;
  while(A > 0 && C > 0){
    C = C-B;
    //cout << C << endl;
    if(C <= 0){
      flag = 1;
      break;
    }
    A = A-D;
    //cout << A << endl;
    if(A <= 0){
      break;
    }
  }
  if(flag == 1)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3636