akhauriyash/Code-Regression huggingface dataset:
using System;

namespace AtCoder.Problems
{
    public class ProblemA
    {
        public static void Main(string[] args)
        {
            var s = new SolveA();
            s.Solve();
        }

        public class Scanner
        {
            private string[] _s;
            private int _i;
            private readonly char[] _separators = new char[] {' '};

            public Scanner()
            {
                _s = new string[0];
                _i = 0;
            }

            public string Next()
            {
                if (_i < _s.Length) return _s[_i++];
                string st = Console.ReadLine();
                while (st == "") st = Console.ReadLine();
                _s = st.Split(_separators, StringSplitOptions.RemoveEmptyEntries);
                if (_s.Length == 0) return Next();
                _i = 0;
                return _s[_i++];
            }

            public int NextInt() => int.Parse(Next());
            public long NextLong() => long.Parse(Next());
            public ulong NextULong() => ulong.Parse(Next());
            public double NextDouble() => double.Parse(Next());

            public int[] GetIntArray(int n, int add = 0)
            {
                int[] array = new int[n];
                for (int i = 0; i < n; i++)
                {
                    array[i] = NextInt() + add;
                }
                return array;
            }

            public long[] GetLongArray(int n, long add = 0)
            {
                long[] array = new long[n];
                for (int i = 0; i < n; i++)
                {
                    array[i] = NextLong() + add;
                }
                return array;
            }

            public double[] GetDoubleArray(int n, double add = 0)
            {
                double[] array = new double[n];
                for (int i = 0; i < n; i++)
                {
                    array[i] = NextDouble() + add;
                }
                return array;
            }

            public string[] GetStringArray(int n)
            {
                string[] array = new string[n];
                for (int i = 0; i < n; i++)
                {
                    array[i] = Next();
                }
                return array;
            }
        }
    }

    public class SolveA
    {
        public void Solve()
        {
            var cin = new ProblemA.Scanner();
            var s = cin.Next();
            var t = cin.Next();

            var result = GetAnswer(s,t);
            Console.WriteLine(result);
        }

        public string GetAnswer(string s, string t)
        {
            return t.StartsWith(s) ? "Yes" : "No";
        }
    }
}

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

string str;
int last[256];
int cost[216000];
int nxt[216000];
char chr[216000];
int main(){
  cin >> str;
  fill(last, last + 256, str.size() + 1);
  cost[str.size() + 1] = 0;
  for(int i = str.size();i >= 0;i--){
    cost[i] = 216000;
    for(int j = 'a';j <= 'z';j++){
      int to = last[j];
      if(cost[to] + 1 < cost[i]){
	cost[i] = cost[to] + 1;
	nxt[i] = to;
	chr[i] = j;
      }
    }
    if(i > 0)last[str[i-1]] = i;
  }

  string ans = "";
  int now = 0;
  while(now <= str.size()){
    ans += chr[now];
    now = nxt[now];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2308
def main():
	from collections import deque
	n, m, *AB = map(int, open(0).read().split())
	g = [[] for _ in range(n + 1)]
	s, t = AB[:2]
	for a, b in zip(*[iter(AB)] * 2):
		g[a] += [b]
		g[b] += [a]
	vis = [0] * (n + 1)
	vis[s] = vis[t] = 1
	c = 2
	ans = deque([s, t])

	def f(s, f):
		nonlocal c
		q = [s]
		while q:
			cur = q.pop()
			for nxt in g[cur]:
				if not vis[nxt]:
					q += [nxt]
					vis[nxt] = 1
					c += 1
					f(nxt)
					break
	f(s, ans.appendleft)
	f(t, ans.append)
	print(c)
	print(*ans)

if __name__=="__main__":
	main()


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

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> F;
  vector<int> S;
  for(int i=0; i<M; i++){
    int a, b;
    cin >> a >> b;
    if(a==1) F.push_back(b-1);
    if(b==1) F.push_back(a-1);
    if(a==N) S.push_back(b-1);
    if(b==N) S.push_back(a-1);
  }
  
  vector<int> div(N);
  for(int i=0; i<F.size(); i++) div.at(F.at(i))++;
  for(int i=0; i<S.size(); i++) div.at(S.at(i))++;
  string ans = "IMPOSSIBLE";
  for(int i=0; i<N; i++){
    if(div.at(i)>1) ans = "POSSIBLE";
  }
  cout << ans << endl;
}

Measured memory_bytes: 2036
#include <bits/stdc++.h>
typedef long long ll;
const int INF=1e9,MOD=1e9+7,ohara=1e6;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(ll i=(a);i<(b);i++)
#define rrrep(i,a,b) for(ll i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl

ll n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

int main(void){
       cin.tie(0);
    ios::sync_with_stdio(false);
      
    cin>>s;
    rep(i,Size(s)){
        if(s[i]=='9')s[i]='1';
        else s[i]='9';
    }
    Cout(s);
    return 0;
}


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

const int M = 1300000;

bool p[M];

void prime() {
  fill(p, p+M, true);
  p[0] = p[1] = false;
  for(int i = 2; i*i < M; i++) {
    if(p[i]) {
      for(int j = 2; i*j < M; j++) {
        p[i*j] = false;
      }
    }
  }
}

int main() {
  prime();
  int n;
  while(cin >> n, n) {
    int ans = 0;
    for(int i = n; !p[i]; i--) ans++;
    for(int i = n; !p[i]; i++) ans++;
    cout << ans << endl;
  }
}

Measured memory_bytes: 2428
#include<stdio.h>
#include<stdlib.h>
int cmp(const void*a,const void*b){return *(int*)a-*(int*)b;}
int main(){
    int n,count=0;
    scanf("%d",&n);
    int p[n];
    for(int i=0;i<n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<n-1;i++){
        int q[3];
        q[0]=p[i-1];q[1]=p[i];q[2]=p[i+1];
        qsort(q,3,sizeof(int),cmp);
        if(p[i]==q[1])
            count++;
    }
    printf("%d\n",count);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
#define loop(n)      for(int i=0;i<(n);i++)
#define lp(x,s,e)    for(int x=(s);x<(e);x++)
#define lpe(x,s,e)    for(int x=(s);x<=(e);x++)
#define MP make_pair
#define PB push_back
#define all(a)  a.begin(),a.end()
#define clr(x,val) memset((x),(val),sizeof(x))
#define endl '\n'

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int a,b;
    cin>>a>>b;
    if(a%2==0||b%2==0){
        cout<<"No";
        return 0;}
     cout<<"Yes";
     return 0;

}

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

int main(){
  vector<int> n(4);
  cin >> n[0] >> n[1] >> n[2] >> n[3];

  sort(n.begin(),n.end());

  string ret = "YES";

  if(n[0] != 1 || n[1] != 4 || n[2] != 7 || n[3] != 9)ret = "NO";

  cout << ret << endl;
}


Measured memory_bytes: 256
//#pragma GCC optimize(2)
#include<cstdio>
#define L 1<<23
#define C (c=*A++)
#define ENS //__attribute__((optimize("-O2")))
#define NES //__attribute__((optimize("-O2"))) __inline__ __attribute__((always_inline))
#define N 131073

struct node{long long s,t;NES bool operator<(const node&b){return (s==b.s&&t<b.t)||s<b.s;}}v[N<<5],t1[N],t2[N];
int n,l[N],r[N],a[N],lf[N],rf[N],cnt,wt,ss[19];char fl[L],*A=fl;long long mid;
NES void read(int&x){char c;for(x=0;'0'>C||c>'9';);while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+c-48,C;}NES void print(long long x){if(!x)putchar(48);else{for(wt=0;x;ss[++wt]=x%10,x/=10);for(;wt;putchar(ss[wt--]+48));}}
NES bool dfs(int x)
{
	if(!l[x])return v[lf[x]=rf[x]=++cnt]=(node){a[x],a[x]},true;int le=l[x],ri=r[x];
	if(!dfs(le)||!dfs(ri))return false;int s1=0,s2=0,i,j;
	for(lf[x]=cnt+1,j=rf[ri],i=rf[le];i>=lf[le];i--)
	{
		for(;j>=lf[ri]&&v[i].t+v[j].s>mid;j--);
		if(j+1==lf[ri])break;t1[++s1]=(node){v[i].s,v[j].t};
	}
	for(j=rf[le],i=rf[ri];i>=lf[ri];i--)
	{
		for(;j>=lf[le]&&v[i].t+v[j].s>mid;j--);
		if(j+1==lf[le])break;t2[++s2]=(node){v[i].s,v[j].t};
	}int p1=s1,p2=s2;
	if(p1||p2)
		if(!p2||(p1&&t1[p1]<t2[p2]))v[++cnt]=(node){t1[p1].s+a[x],t1[p1].t+a[x]},p1--;
		else v[++cnt]=(node){t2[p2].s+a[x],t2[p2].t+a[x]},p2--;
	while(p1||p2)
		if(!p2||(p1&&t1[p1]<t2[p2])){if(v[cnt].t>t1[p1].t+a[x])v[++cnt]=(node){t1[p1].s+a[x],t1[p1].t+a[x]};p1--;}
		else{if(v[cnt].t>t2[p2].t+a[x])v[++cnt]=(node){t2[p2].s+a[x],t2[p2].t+a[x]};p2--;}
	return(rf[x]=cnt)>=lf[x];
}
ENS int main()
{int i,fa;long long le,ri;
	for(fl[fread(fl,1,L,stdin)]=EOF,read(n),i=2;i<=n;read(a[i]),ri+=a[i],i++)if(read(fa),l[fa])r[fa]=i;else l[fa]=i;
	for(;ri&&(cnt=0,mid=ri>>1,dfs(1));ri>>=1);for(le=mid;le<ri;mid=(le+ri)>>1,cnt=0,dfs(1)?ri=mid:le=mid+1);print(ri);
}

Measured memory_bytes: 26880
#include<bits/stdc++.h>
using namespace std;
int main(){
  while(1){
    int n,m,sum1=0,sum2=0,ans1,ans2,d,max=100000,count=0;
    int s[110],t[110];
    cin >> n >> m;
    if(n == 0 && m == 0) break;
    for(int i=0; i<n; i++){
       cin >> s[i];
       sum1 += s[i];
     }
    for(int i=0; i<m; i++){
      cin >> t[i];
      sum2 += t[i];
    }
    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(sum1+t[j]-s[i]==sum2+s[i]-t[j]){
          if(max>s[i]+t[j]){
            max=s[i]+t[j];
            ans1=s[i];
            ans2=t[j];
            count++;
          }
        }
      }
    }
    if(count != 0) cout << ans1 << " " << ans2 << endl;
    else cout << -1 << endl;
  }
  return 0;
}

    /*d = abs(sum1-sum2);
    if(d%2 == 0){
      d = d/2;
      for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
          if(abs(s[i]-t[j]) == d){
              if(max > s[i]+t[j]){
              ans1 = s[i];
              ans2 = t[j];
              max = ans1 + ans2;
              count++;
            }
          }
        }
      }
      if(count != 0) cout << ans1 << " " << ans2 << endl;
      else cout << -1 << endl;
    }
    else {
      cout << -1 << endl;
    }
  }
  return 0;
}*/



Measured memory_bytes: 3084
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

s = ins()
mx = [0]*26
cur = [0]*26
for c in s:
    for j in range(26):
        d = chr(ord('a')+j)
        if c==d:
            cur[j] = 0
        else:
            cur[j] += 1
            mx[j] = max(mx[j],cur[j])
    #ddprint(f"c {c}")
    #ddprint(cur)
    #ddprint(mx)
print(min(mx))


Measured memory_bytes: 39536
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		String[] sArray = s.split("");
		String[] tArray = t.split("");
		Arrays.sort(sArray);
		Arrays.sort(tArray, Comparator.reverseOrder());
		System.out.println(String.join("", sArray).compareTo(String.join("", tArray)) < 0 ? "Yes" : "No");
		sc.close();
	}
}

Measured memory_bytes: 21844
#define MOVE 0
#define TREE 1
#define JUMP 2
m[15][15],D[15][15];
X,Y,x,y,d;
main(){
	for(;scanf("%d%d",&X,&Y),X;){
		for(y=0;y<Y;y++)
			for(x=0;x<X;x++)
				scanf("%d",&m[x][y]);
		for(x=0;x<X;x++)
			D[x][0]=m[x][0]!=TREE;
		for(y=1;y<Y;y++){
			for(x=0;x<X;x++){
				d=0;
				if(m[x][y]!=TREE){
					if(m[x][y-1]==MOVE)
						d+=D[x][y-1];
					if(y-2>=0&&m[x][y-2]==JUMP)
						d+=D[x][y-2];
				}
				if(m[x][y]==MOVE){
					if(x-1>=0&&m[x-1][y-1]==MOVE)
						d+=D[x-1][y-1];
					if(x+1<X&&m[x+1][y-1]==MOVE)
						d+=D[x+1][y-1];
				}
				D[x][y]=d;
			}
		}
		d=0;
		for(x=0;x<X;x++){
			d+=D[x][Y-1];
			if(Y-2>=0&&m[x][Y-2]==JUMP)
				d+=D[x][Y-2];
		}
		printf("%d\n",d);
	}
	exit(0);
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define MOD 1000000007
#define INF 1 << 30

using namespace std;
typedef long long ll;

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

int main(void) {
	int num, i, j, ans = 1;
	ll a, b, g, k;
	cin >> a >> b;
	g = gcd(a, b);
	k = (ll)sqrt(g) + 2;
	vector<int> d(k, true);
	for (i = 2; i < k; i++) {
		if (d[i]) {
			for (j = i << 1; j < k; j += i)
				d[j] = false;
			if (g % i == 0) {
				ans++;
				while (g % i == 0)
					g /= i;
			}
		}
	}
	if (g != 1)
		ans++;
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define POP pop_back()
#define ll long long
#define db double
#define POP pop_back()
#define endl '\n'
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const ll inF = 0x3f3f3f3f3f3f3f3f;
struct node{
	int w , v;
};
node a[maxn];
ll dp[maxn];
int main(){
	int n , c;cin >> n >> c;
	int w , v , tmp = 0;
	for(int i = 1;i <= n;i++)cin >> a[i].w >> a[i].v , tmp+=a[i].v;
	for(int i = 1;i <= tmp;i++)dp[i] = inF;
	for(int i = 1;i <= n;i++){
		for(int j = tmp;j >= a[i].v;j--){
			dp[j] = min(dp[j] , dp[j-a[i].v] + a[i].w);
		}
	}
	int ans = 0;
	for(int i = tmp;i >= 1;i--){
		if(dp[i] <= c){
			ans = i;
			break;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <iostream>
#include <random>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include <fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using qll = queue<ll>;
using vb = vector<bool>;
using mll = map<ll, ll>;
using sll = stack<ll>;
using vec = vector<double>;
using mat = vector<vec>;
#define REP(i,n) for(ll i(0);(i)<(n);(i)++)
#define rep(i,n) for(ll i(0);(i)<(n);(i)++)
#define ALL(a) a.begin(), a.end()
#define elnd endl //* missspell check
const ll INF = 1LL << 60;
const double EPS = 1E-8;
//* Solve Ax = b. A is a square matrix in O(n^3)
//* Return 0-length vector if unsolvable/not-unique
//* partial pivoting
vec GaussJordan(const mat &A, const vec &b){
    ll n = A.size();
    mat B(n, vec(n+1)); //* last columb for solution
    //* initialize B
    REP(i, n) REP(j, n) B[i][j] = A[i][j];
    REP(i, n) B[i][n] = b[i];

    REP(i, n){
        ll pivot = i;
        for(ll j = i; j < n; j++){
            if(abs(B[j][i]) > abs(B[pivot][i])) pivot = j;
        }
        swap(B[i], B[pivot]); //* swap i-th row and pivot-th row
        if(abs(B[i][i]) < EPS) return vec();

        for(ll j = i+1; j <=n; j++) B[i][j] /= B[i][i];
        //* eliminition
        for(ll j = 0; j < n; j++){
            if(i != j){
                for(ll k = i+1; k <= n; k++) B[j][k] -= B[j][i] * B[i][k];
            }
        }
    }
    //* prepare solution
    vec x(n);
    for(ll i=0; i < n; i++) x[i] = B[i][n];
    return x;
}

//! http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0004&lang=ja
int main(){
    mat A(2, vec(2));
    vec b(2);
    while(scanf("%lf %lf %lf %lf %lf %lf",&A[0][0],&A[0][1],&b[0],&A[1][0],&A[1][1],&b[1])!=EOF){
        vec x = GaussJordan(A, b);
        printf("%.3lf %.3lf\n",x[0],x[1]);
    }
    return 0;
}


Measured memory_bytes: 3224
import java.io.*;

public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    int[] cnt = new int[5];

    String[] in;

    for(int i = 0; i < 3; i++){
      in = br.readLine().split(" ");
      int a = Integer.parseInt(in[0]);
      int b = Integer.parseInt(in[1]);
      cnt[a]++;
      cnt[b]++;
    }

    br.close();

    boolean ok = true;

    for(int i = 1; i <= 4; i++){
      if(cnt[i] > 2) ok = false;
    }

    System.out.println(ok ? "YES" : "NO");
    
  }
}


Measured memory_bytes: 23252
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MOD = 1e9 + 7;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int dp[2][2005];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int s;
	cin >> s;
	int ans = 0;
	repn(i, 3, s + 1) dp[0][i] = 1;
	ans += dp[0][s];
	repn(i, 1, (s / 3) + 1){
		repn(j, 3, s + 1) repn(k, i * 3, s - j + 1) if(dp[1 - (i & 1)][k]){
			dp[i & 1][k + j] += dp[1 - (i & 1)][k];
			if(dp[i & 1][k + j] >= MOD) dp[i & 1][k + j] -= MOD;
		}
		ans += dp[i & 1][s];
		if(ans >= MOD) ans -= MOD;
		rep(j, 2005) dp[1 - (i & 1)][j] = 0;
	}
	cout << ans << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 3664
#define DEBUG 0

/**
 * File    : E.cpp
 * Author  : Kazune Takahashi
 * Created : 5/19/2019, 9:22:36 PM
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <functional>
#include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(10101010));
#include <chrono> // std::chrono::system_clock::time_point start_time, end_time;
// start = std::chrono::system_clock::now();
// double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N, M;
vector<int> V[100010];
bool visited[100010];

bool dfs(int v)
{
  if (visited[v])
  {
    return false;
  }
  visited[v] = true;
  for (auto x : V[v])
  {
    dfs(x);
  }
  return true;
}

int main()
{
  cin >> N >> M;
  for (auto i = 0; i < M; i++)
  {
    int x, y, z;
    cin >> x >> y >> z;
    x--;
    y--;
    V[x].push_back(y);
    V[y].push_back(x);
  }
  fill(visited, visited + 100010, false);
  int ans = 0;
  for (auto i = 0; i < N; i++)
  {
    if (dfs(i))
    {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 8960
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int a;
    cin>>a;
    int s[a];
    for (int i=0;i<a;i++){
        cin>>s[i];
    }
    sort(s,s+a,greater<int>());
    int p=0,q=0;
    for (int i=0;i<a;i+=2){
        p+=s[i];
    }
    for (int i=1;i<a;i+=2){
        q+=s[i];
    }
    cout<<p-q<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define N (1000000000+7)
typedef pair<int,int> P;
typedef long long ll;
int d[100010][3];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n,m;
char board[1010][1010];

struct edge{
    int to,cost;
};


vector<edge>graph[100010];

void explore(int s){
    queue<P> node;
    node.push(P(s,0));
    for(int i=0;i<100010;i++){
        for(int j=0;j<3;j++){
            d[i][j]=1000000000;
        }
    }
    d[s][0]=0;
    while(!node.empty()){
        P p=node.front();
        node.pop();
        for(int i=0;i<(int)graph[p.first].size();i++){
            P np =make_pair(graph[p.first][i].to,(p.second+1)%3);
            if(d[np.first][np.second]>d[p.first][p.second]+1){
                d[np.first][np.second]=d[p.first][p.second]+1;
                node.push(np);
            }
        }
    }
}

int main(void){
    int u,v,s,t;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>u>>v;
        graph[u].push_back({v,1});
    }
    cin>>s>>t;
    explore(s);
    if(d[t][0]==1000000000)cout<<-1<<endl;
    else cout<<d[t][0]/3<<endl;
    return 0;
}

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


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

  int n;
  cin >> n;
  n%=10;
  if(n==3) cout <<"bon" << endl;
  else if(n== 0 || n==1 || n==6 || n==8){
    cout <<"pon" << endl;
  }
  else cout << "hon" << endl;
  
  return 0;
    

}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,M;
ll V[101010];
ll E[101010];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) V[i]=1;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(uf[x]==uf[y]) {
			E[uf[x]]++;
		}
		else {
			V[uf[x]]=V[uf[y]]=V[uf[x]]+V[uf[y]];
			E[uf[x]]=E[uf[y]]=E[uf[x]]+E[uf[y]]+1;
			uf(x,y);
		}
	}
	
	ll cur=max(V[uf[0]],V[uf[1]]);
	FOR(i,N) if(uf[i]==i) {
		ret+=V[i]*(V[i]-1)/2-E[i];
		if(i!=uf[0] && i!=uf[1]) {
			ret+=cur*V[i];
			cur+=V[i];
		}
	}
	cout<<ret<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 6256
#include <iostream>
#include <vector>

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

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

  vector<int> ti(n);
  for(int i=0; i<n; i++){
    cin >> ti[i];
  }

  long long ans = 0;
  if( 1 < n ){
    for(int i=0; i<n-1; i++){
      if( (ti[i+1] - ti[i]) >= t ) ans += t;
      else ans += ti[i+1] - ti[i];
    }
    ans += t;
    cout << ans << endl;
  }else{
    cout << t;
  }


  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<map>
#include<cassert>
#define rep(i, n) for ( int i = 0; i < n; i++)
using namespace std;
 
#define MAX 10
#define PMAX 23
#define HOUSE 3
#define SPACE 0
#define SMOKE 1
#define START 2
#define BLOCK 4
 
int H, W, n;
 
class State{
public:
  unsigned short pi, pj, total;
  bool V[PMAX];
 
  State(){total = 0;}
 
  bool operator < ( const State &s) const{
    if ( pi != s.pi ) return pi < s.pi;
    if ( pj != s.pj ) return pj < s.pj;
    for ( int i = 0; i < n; i++ ){
      if ( V[i] == s.V[i] ) continue;
      return V[i] < s.V[i];
    }
    return false;
  }
};
 
static int di[4] = {0, -1, 0, 1};
static int dj[4] = {1, 0, -1, 0};
 
int  G[MAX+2][MAX+2], I[MAX+2][MAX+2];
 
main(){
  int si, sj;
 
  while(1){
    cin >> W >> H;
    if ( W == 0 && H == 0 ) break;
    int total = 0;
    n = 0;
    for ( int i = 0; i < H+2; i++ )
      for ( int j = 0; j < W+2; j++ ) G[i][j] = BLOCK;
    for ( int i = 1; i <= H; i++ ){
      for ( int j = 1; j <= W; j++ ){
    cin >> G[i][j];
    if ( G[i][j] == START ){ si = i; sj = j;}
    if ( G[i][j] == SMOKE ) { total++; I[i][j] = n++; }
      }
    }
 
    State s = State();
     
    for ( int i = 0; i < n; i++ ) s.V[i] = true;
 
    map<State, int> M;
    State v;
 
    int ni, nj;
    M[s] = 0;
     
    for ( int r = 0; r < 4; r++ ){
      ni = si + di[r];
      nj = sj + dj[r];
 
      while(1){
    if ( G[ni][nj] == SMOKE && s.V[I[ni][nj]] ){
      v = s;
      v.pi = ni;
      v.pj = nj;
      v.V[I[ni][nj]] = false;
      v.total = 1;
      M[v] = 1;
      break;
    } else if ( G[ni][nj] == BLOCK ) break;
    ni += di[r];
    nj += dj[r];
      }
    }
 
    map<State, int>::iterator it;
     
    int presize = M.size();
 
    int cc = 0;
    int x = 0;
    bool f;
    map<State, int> nM;
 
    while(1){
      nM.clear();
      f = true;
      for ( it = M.begin(); it != M.end(); it++ ){
    State cur = (*it).first;
    int cost = (*it).second;
    if ( cost == 0 ) continue;
 
    for ( int r = 0; r < 4; r++ ){
      ni = cur.pi + di[r];
      nj = cur.pj + dj[r];
 
      while(1){
        if ( G[ni][nj] == SMOKE && cur.V[I[ni][nj]]){
          v = cur;
          v.pi = ni;
          v.pj = nj;
          v.V[I[ni][nj]] = false;
          v.total++;
          f = false;
          nM[v] += cost;
          break;
        } else if ( ni == si && nj == sj && cur.total == total ){
          x += cost;
          break;
        } else if ( G[ni][nj] == BLOCK ) {
          break;
        }
        ni += di[r];
        nj += dj[r];
      }
    }
      }
      if ( f ) break;
      M = nM;
    }
 
    cout << x << endl;
  }
}

Measured memory_bytes: 30668
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;
using System.Runtime.InteropServices.ComTypes;
using System.Xml.Schema;
using System.ComponentModel.DataAnnotations;
using System.Security.Cryptography;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var N = Sarray()[0];
            memo = new long[N + 1].Select(_ => new Dictionary<string, long>()).ToArray();
            WriteLine(dfs(N, "TTT"));
        }
        static bool ok(string last4)
        {
            for (var i = 0; i < 4; ++i)
            {
                var t = last4.ToCharArray();
                if (1 <= i)
                    (t[i - 1], t[i]) = (t[i], t[i - 1]);
                if (string.Join("", t).Contains("AGC"))
                    return false;
            }
            return true;
        }
        static Dictionary<string, long>[] memo;
        static long dfs(long cur, string last3)
        {
            if (memo[cur].ContainsKey(last3))
                return memo[cur][last3];
            if (cur == 0) return 1;
            var ret = 0L;
            foreach (var c in "ACGT")
                if (ok(last3 + c))
                    ret = (ret + dfs(cur - 1, last3.Substring(1, 2) + c)) % Mod;
            return memo[cur][last3] = ret;
        }


        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
        static public (T a, T b, T c, T d) Slice4<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)),
            (T)Convert.ChangeType(t[3], typeof(T)));
        }
    }
}

Measured memory_bytes: 47112
n = int(input())
a = [[0]*n for i in range(n)]
pos = [i for i in range(n)]

def bipartite_graph(pos, level):
    pos1 = pos[:len(pos)//2]
    pos2 = pos[len(pos)//2:]  
    for i in pos1:
        for j in pos2:
            a[i][j] = level
    if len(pos1) >= 2:
        bipartite_graph(pos1, level + 1)
    if len(pos2) >= 2:
        bipartite_graph(pos2, level + 1)

bipartite_graph(pos, 1)
for i in range(n):
    print(*a[i][i+1:])

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

int main() {
	int h,w;
	
	for(;;){
		cin >> h >> w;
		if(h>0 && w>0){
			for(int i=0; i<h; i++){
				for(int j=0; j<w; j++){
					cout << "#";
					if(j+1==w){
						cout << endl;
					}
				}
				if(i+1==h){
					cout << endl;
				}
			}
		}else if(h==0 && w==0){
			break;
		}
	}
	return 0;
	
}

Measured memory_bytes: 1152
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

int main()
{
    int n, x, max;
    int a, b, c;
    int ans;

    while (1) {
        scanf("%d%d", &n, &x);
        if (n == 0 && x == 0) break;

        ans = 0;
        max = x; if (max > n) max = n;
        for (a = 1; a <= max; a++) {
            for (b = a + 1; b <= max; b++) {
                c = x - a - b;
                if (c > b && c <= n) ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}



Measured memory_bytes: 2044
def selection_sort(numbers, n, key=lambda x: x):
    """selection sort method

    Args:
        numbers: a list of numbers to be sorted
        n: len(numbers)
        key: sort key

    Returns:
        sorted numberd, number of swapped times
    """
    x = []
    for data in numbers:
        x.append(data)

    counter = 0

    for i in range(0, n):
        min_j = i
        for j in range(i, n):
            if key(x[j]) < key(x[min_j]):
                min_j = j
        if min_j != i:
            x[min_j], x[i] = x[i], x[min_j]
            counter += 1
    return x, counter


def bubble_sort(numbers, n, key=lambda x: x):
    """bubble sort method

    Args:
        numbers: a list of numbers to be sorted by bubble sort
        n: len(list)
        key: sort key

    Returns:
        sorted list
    """
    x = []
    for data in numbers:
        x.append(data)

    flag = True
    counter = 0
    while flag:
        flag = False
        for index in range(n - 1, 0, -1):
            if key(x[index]) < key(x[index - 1]):
                x[index], x[index - 1] = x[index - 1], x[index]
                flag = True
                counter += 1
    return x, counter


def insertion_sort(numbers, n, key=lambda x: x):
    """insertion sort method

    Args:
        numbers: a list of numbers to be sorted
        n: len(numbers)

    Returns:
        sorted list
    """
    for i in range(1, n):
        target = numbers[i]
        index = i - 1
        while index >= 0 and target < numbers[index]:
            numbers[index + 1] = numbers[index]
            index -= 1
        numbers[index + 1] = target

    return numbers


def is_stable(list1, list2):
    """check stablity of sorting method used in list2

    Args:
        list1: sorted list(bubble sort)
        list2: sorted list(some sort)

    Returns:
        bool
    """
    flag = True
    for index, data in enumerate(list1):
        if list2[index] != data:
            flag = False
            break

    return flag


length = int(raw_input())
cards = raw_input().split()
bubble_sorted_card, bubble_swapped = bubble_sort(numbers=cards, n=length, key=lambda x: int(x[1]))
selection_sorted_card, selection_swapped = selection_sort(numbers=cards, n=length, key=lambda x: int(x[1]))
print(" ".join(bubble_sorted_card))
print("Stable")
print(" ".join(selection_sorted_card))

if is_stable(bubble_sorted_card, selection_sorted_card):
    print("Stable")
else:
    print("Not stable")

Measured memory_bytes: 6476
import sys
from functools import reduce


def input():
    return sys.stdin.readline()[:-1]


def mm(a, b):
	ans = a*b
	if ans > 10**18:
		return 0
	else:
		return a*b

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

if 0 in A:
	print(0)
else:
	ans = reduce(mm, A)
	
	if ans == 0:
		print(-1)
	else:
		print(ans)
		


Measured memory_bytes: 81856
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
#include <stack>
#include <queue>
#include <cassert>
//#include <bits/stdc++.h>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
//#define int ll
typedef long long ll;

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

string yn(bool x){
    return x ? "Yes" : "No";
}

int main(){
    int n,m; cin >> n >> m;
    int X,Y; cin >> X >> Y;
    
    int x[n],y[m];
    
    rep(i,n) cin >> x[i];
    rep(i,m) cin >> y[i];
    
    sort(x,x+n);
    sort(y,y+m);
    
    bool ans = 1;
    
    Rep(i,-100,101){
        
        if(i<=X or Y<i) continue;
        
        ans = 1;
        rep(j,n){
            if(x[j]>=i) ans = 0;
        }
        rep(j,m){
            if(y[j]<i) ans = 0;
        }
        
        if(ans){
            cout << "No War" << endl;
            return 0;
        }
    }
    
    cout << "War" << endl;
}












Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) { a = b; return 1; }
  return 0; }
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) { a = b; return 1; }
  return 0; }

int ketasu(int n){
  int i = 0;
  while(n != 0){
    n /= 10;
    i++;
  }
  return i;
}

//一番上位の桁の値を求める関数
int saijoi(int n){
  int k = ketasu(n);
  if(k == 1) return n;
  else{
    return n/pow(10,k-1);
  }
}

int main(void){
  int n; cin >> n;
  int ans = 0;
  map<P, int> count;
  for(int i = 1; i <= n; i++){
    int joi,kai;
    joi = saijoi(i);
    kai = i%10;
    P p = make_pair(joi,kai);
    if(count[p] == 0) count[p] = 1;
    else count[p]++;
  }
  for(int i = 1; i <= 9; i++){
    for(int j = 1; j <= 9; j++){
      P p1 = make_pair(i,j);
      P p2 = make_pair(j,i);
      ans += count[p1]*count[p2];
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#![allow(unused)]

use std::{cell, cmp, collections, convert, fmt, io, iter, ops, str};

use cell::{Cell, RefCell};
use cmp::Ordering::{Equal, Greater, Less};
use collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, LinkedList, VecDeque};
use io::{Read, Write};

#[cfg(feature = "debug")]
macro_rules! debug {
    ($($args: tt)*) => { eprint!($($args)*) };
}

#[cfg(feature = "debug")]
macro_rules! debugln {
    ($($args: tt)*) => { eprintln!($($args)*) };
}

#[cfg(not(feature = "debug"))]
macro_rules! debug {
    ($($args:tt)*) => {};
}

#[cfg(not(feature = "debug"))]
macro_rules! debugln {
    ($($args:tt)*) => {};
}

macro_rules! vmax {
    ($x: expr, $y: expr) => { cmp::max($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::max($x, vmax!($($args),*)) };
}

macro_rules! vmin {
    ($x: expr, $y: expr) => { cmp::min($x, $y) };
    ($x: expr, $($args: expr),*) => { cmp::min($x, vmin!($($args),*)) };
}

fn main() {
    let _ = parse_line::<usize>();
    let nums = {
        let mut n = parse_vec::<u64>();
        n.sort_by(|a, b| b.cmp(a));
        n
    };

    // let f = |m| nums.iter().map(|n| m % n).sum::<u64>();
    //
    // let lcm = nums.iter().fold(1, |acc, &x| lcm(acc, x));

    println!("{}", nums.iter().sum::<u64>() - nums.len() as u64);
}

fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        //
    }
}

fn read_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().to_owned()
}

fn read_word() -> String {
    const CAPACITY: usize = 16;

    let mut stdin = io::stdin();
    let mut byte: [u8; 1] = [0];

    loop {
        let mut buf = Vec::with_capacity(CAPACITY);

        loop {
            let res = stdin.read(&mut byte);

            if res.unwrap_or(0) == 0 || byte[0] <= b' ' {
                break;
            } else {
                buf.push(byte[0]);
            }
        }

        if !buf.is_empty() {
            return String::from_utf8(buf).unwrap();
        }
    }
}

fn parse_line<T: str::FromStr>() -> T {
    read_line().parse().ok().unwrap()
}

fn parse_word<T: str::FromStr>() -> T {
    read_word().parse().ok().unwrap()
}

fn parse_vec<T: str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn flush() {
    io::stdout().flush();
}

fn next_prime(x: i32) -> i32 {
    for i in (x + 1).. {
        if is_prime(i) {
            return i;
        }
    }

    panic!("attempt to add with overflow");
}

fn is_prime(x: i32) -> bool {
    let ceil = f64::from(x).sqrt().ceil() as i32;
    x == 2 || (2..(ceil + 1)).all(|i| x % i != 0)
}

fn bit_high(bits: u64, pos: u64) -> bool {
    bits & (1 << pos) != 0
}


Measured memory_bytes: 4352
class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9 + 7
comb = Combination(n, MOD)

a = sorted(a, reverse = True)
ans = 0

for i in range(n):
    if n - i - 1 < k - 1:
        break
    ans += a[i] * comb.combination(n - i - 1, k - 1)
    ans %= MOD
    
a = sorted(a)
for i in range(n):
    if n - i - 1 < k - 1:
        break
    ans -= a[i] * comb.combination(n - i - 1, k - 1)
    ans %= MOD
print(ans)

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

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

    vector<int> l(N);
    for (size_t i = 0; i < N; i++)
    {
        cin >> l[i];
    }
    sort(l.begin(), l.end());
    reverse(l.begin(), l.end());

    int snake = 0;
    for (size_t i = 0; i < K; i++)
    {
        snake += l[i];
    }
    cout << snake << endl;
}


Measured memory_bytes: 3632
sx,sy,tx,ty = map(int,input().split())
dx = tx-sx
dy = ty-sy
print("U"*dy+"R"*dx+"D"*dy+"L"*(dx+1)+"U"*(dy+1)+"R"*(dx+1)+"DR"+"D"*(dy+1)+"L"*(dx+1)+"U")

Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <iomanip>


using namespace std;

int main()
{
    double x1,y1,x2,y2;
    
    cin >>x1>>y1>>x2>>y2;
    
    cout << fixed<<setprecision(4)<<sqrt(pow(x2-x1,2)+pow(y2-y1,2))<<endl;
    
    return 0;
}



Measured memory_bytes: 3224
# APC001B - Two Arrays
import sys

input = sys.stdin.readline


def main():
    n = int(input())
    A = tuple(map(int, input().split()))
    B = tuple(map(int, input().split()))
    cnt = 0
    for a, b in zip(A, B):
        if a > b:
            cnt += a - b
        else:
            cnt -= (b - a) // 2
    print("Yes" if cnt <= 0 else "No")


if __name__ == "__main__":
    main()

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

int main() {
	string s;
	string t[4] = {"maerd", "remaerd", "esare", "resare"};
	bool ans = true;
	cin >> s;
	int idx = s.length()-1;
	int tl[4] = {5, 7, 5, 6};
	while(idx>=0) {
		bool any_add = false;
		rep(i,4) {
			bool add = true;
			//t[i]がsの後ろに当てはまるか判定
			rep(j, tl[i]) {
				if (s[idx-j] != t[i][j]) add = false;
			}
			if (add) {
				any_add = true;
				idx -= t[i].length();
				break;
			}
		}
		if (!any_add) {
			ans = false;
			break;
		}
	}
	if (ans) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}


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

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


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

	int N, K;
	cin >> N >> K;

	int G = -1, M = -1;
	for(int i = 0; i < N; i++) {
		int A;
		cin >> A;
		if(G == -1) G = A;
		else G = gcd(G, A);
		M = max(M, A);
	}

	if(K % G == 0 && K <= M) {
		cout << "POSSIBLE" << endl;
	}
	else {
		cout << "IMPOSSIBLE" << endl;
	}
}


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

#ifdef DEBUG
#include ".inc/debug.hpp"
#else
#define debug(...) 42
#define rdfile(...) 42
#endif

long long nxt[100010][30]; // next[i][j] := i以降に出る文字jの位置

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // rdfile("_input.txt");

    string s, t;
    cin >> s >> t;

    bool exist[30] = {};
    for (char c : s) {
        exist[c - 'a'] = true;
    }
    for (char c : t) {
        if (!exist[c - 'a']) {
            cout << -1 << endl;
            return 0;
        }
    }

    // init
    for (int i=0; i<100010; ++i) {
        for (int j=0; j<30; ++j) {
            nxt[i][j] = -1;
        }
    }
    
    for (int i=(int)s.size()-1; i>=0; --i) {
        for (int j=0; j<30; ++j) {
            nxt[i][j] = nxt[i+1][j];
        }
        nxt[i][s[i] - 'a'] = i;
    }

    long long ans = 0, k = -1;
    for (int i = 0; i < (int)t.size(); ++i) {
        if (nxt[k+1][t[i]-'a'] >= 0) {
            ans += nxt[k+1][t[i]-'a'] - k;
            k = nxt[k+1][t[i]-'a'];
        } else {
            ans += nxt[0][t[i]-'a'] + (int)s.size() - k;
            k = nxt[0][t[i]-'a'];
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 24016
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

int main(){
  string s;

  while(cin >> s){
    int ans = 0;

    for(int i = (s[0] == '-' ? 2 : 0); i < s.size(); i++){
      string left_str = s.substr(0, i);
      string right_str = s.substr(i);

      if(right_str.size() >= 2 && right_str[0] == '0') continue;

      int L = atoi(left_str.c_str());
      int R = atoi(right_str.c_str());
      int x = (L + R) / 2;
      int y = -(L - R) / 2;

      if(x >= 0 && y >= 0 && x - y == L && x + y == R){
        ans++;
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1204
N = int(input())
W = list(map(int, input().split()))

min_diff = sum(W)
for t in range(N):
    S_1 = sum(W[:t])
    S_2 = sum(W[t:])
    min_diff = min(min_diff, abs(S_1 - S_2))

print(min_diff)

Measured memory_bytes: 3060
#include <stdio.h>
int main(void){
    int i, j, W, H;
    while(1){
        scanf("%d %d", &H, &W);
        if(H == 0 && W == 0){
            break;
        }
        for(i = 0; i < H; i++){
            for(j = 0; j < W; j++){
                if((i % 2 == 0 && j % 2 ==0) || (i % 2 && j % 2)){
                    printf("#");
                }else{
                    printf(".");
                }
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}



Measured memory_bytes: 2112
N, T = map(int, input().split())

ct_list = []
for i in range(N):
    ct_list.append(list(map(int, input().split())))

min_cost = 10000

for ct in ct_list:
    if ct[1] <= T and ct[0] < min_cost:
        min_cost = ct[0]

if min_cost != 10000:
    print(min_cost)
else:
    print("TLE")

Measured memory_bytes: 3060
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, C = LI()
    D = []
    c = []
    m0 = collections.defaultdict(int)
    m1 = collections.defaultdict(int)
    m2 = collections.defaultdict(int)
    for _ in range(C):
        D.append(LI())
    for __ in range(N):
        c.append(LI_())
    for row in range(N):
        for col in range(N):
            color = c[row][col]
            if (row + col) % 3 == 0:
                m0[color] += 1
            elif (row + col) % 3 == 1:
                m1[color] += 1
            else:
                m2[color] += 1
    min_cnt = inf
    for c0 in range(C):
        for c1 in range(C):
            for c2 in range(C):
                cnt = 0
                if c0 == c1 or c1 == c2 or c2 == c0:
                    continue

                for orig_c0, num in m0.items():
                    cnt += (D[orig_c0][c0] * num)

                for orig_c1, num in m1.items():
                    cnt += (D[orig_c1][c1] * num)

                for orig_c2, num in m2.items():
                    cnt += (D[orig_c2][c2] * num)
                min_cnt = min(min_cnt, cnt)
    print(min_cnt)
main()



Measured memory_bytes: 72792
N, M = map(int, input().split())
H = [0]+[int(h) for h in input().split()]
AB=[[] for n in range(N+1)]
for a, b in [[int(x) for x in input().split()] for m in range(M)]:
  AB[a].append(b)
  AB[b].append(a)
#print(AB)

ans=0
for i, ab in enumerate(AB):
  # rule2
  if not len(ab):
    ans+=0
  
  # rule1
  for j in ab:
    if H[i]<=H[j]:
      break
  else:
    ans+=1

print(ans-1) # decrease Observatroy index 0


Measured memory_bytes: 39744