akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    ll N, M;
    cin >> N >> M;

    if (N == 1) {
        print(M == 1 ? 1 : M - 2);
    } else if(M == 1) {
        print(N - 2);
    }  else {
        print((N - 2) * (M - 2));
    }
    
}


Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Integer n=Integer.valueOf(new Scanner(System.in).nextLine());
		double even=0;
		for(int i=1;i<=n;i++) {
			even+=i%2==0?0:1;
		}
		System.out.println(even/n);
	}
}

Measured memory_bytes: 23252
#include<stdio.h>

int main()
{
	int n, m;
	
	while(scanf("%d %d", &n, &m))
	{
		bool ok = 1, go = 0;
		
		if(n == 0 && m == 0)
		{
			break;
		}
		
		for(int i = 0; i < n; i++)
		{
			if(ok)
			{
				go = 1;
				for(int j = 0; j< m; j++)
				{
					if(go)
					{
						printf("#");
						go = 0;
					}
					else
					{
						printf(".");
						go = 1;
					}
				}
				printf("\n");
				ok = 0;
			}
			else
			{
				go = 1;
				for(int j = 0; j< m; j++)
				{
					if(go)
					{
						printf(".");
						go = 0;
					}
					else
					{
						printf("#");
						go = 1;
					}
				}
				printf("\n");
				ok = 1;
			}
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2604
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

li = [[]] * (H * W)
for i in range(H):
  for j in range(W):
    li[A[i][j] - 1] = [j, i]

cost = [[0 for _ in range((H * W) // D + 1)] for _ in range(D)]
for i in range(H * W):
  d, m = divmod(i, D)
  if d > 0:
    cost[m][d] = cost[m][d - 1] + abs(li[i][0] - li[i - D][0]) + abs(li[i][1] - li[i - D][1]) 

# print(cost)

for l, r in LR:
  print(cost[(l - 1) % D][(r - 1) // D] - cost[(l - 1) % D][(l - 1) // D])

Measured memory_bytes: 89820
/*
    talk is cheap
    feelings fade

    love is real
    but so is change
*/

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

signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    //int t=1 ; cin>>t ; while(t--)
    {
        int n;
        cin >> n;

        cout << n * (n - 1) / 2 << '\n'; 
        
    }
    
    cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
    return 0;
}



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

bool binary(vector<int> v,int x)
{
  int l,r,med;
  l=0; r=v.size()-1;
  while(l<r){
    if(v[r]==x or v[l]==x) return true;
    med=(r+l)/2;
    if(x>v[med]) l=med+1;
    else if(x<v[med]) r=med-1;
    else return true;
  }
  return false;
}

int main()
{
  int n,q,c=0;
  vector<int> s,t;
  
  //input
  cin>>n; s.resize(n);
  for(int i=0; i<n; i++) cin>>s[i];
  cin>>q; t.resize(q);
  for(int i=0; i<q; i++) cin>>t[i];
  
  //process
  for(int i=0; i<q; i++) if(binary(s,t[i])) c++;
  cout<<c<<endl;
  return 0;
}


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

int main() {
	int N;
	cin >> N;
	int p, q, r, s, t, u;
	u = N / 100000;
	p = (N - u * 100000) / 10000;
	q = (N - u * 100000 - p * 10000) / 1000;
	r = (N - u * 100000 - p * 10000 - q * 1000) / 100;
	s = (N - u * 100000 - p * 10000 - q * 1000 - r * 100) / 10;
	t = N - u * 100000 - p * 10000 - q * 1000 - r * 100 - s * 10;

	if (u > 0)
		cout << 90909 << endl;
	else if (p > 0)
		cout << 909 + 10000 * (p - 1) + q * 1000 + r * 100 + s * 10 + t + 1 << endl;
	else if (q > 0)
		cout << 909 << endl;
	else if (r > 0)
		cout << 9 + 100 * (r - 1) + s * 10 + t + 1 << endl;
	else if (s > 0)
		cout << 9 << endl;
	else
		cout << t << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define INF 1e9+7
int main() {
	int a, b;
	cin >> a >> b;
	cout << (a - 1)*(b - 1);

}


Measured memory_bytes: 764
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define UNTIL(p) while(!(p))

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

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

#define PUTS(x) cout << (x) << endl;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a,b;
    cin>>a>>b;
    int n = a.size();
    bool yes = false;
    REP(i,n)
    {
        if(a == b)
        {
            yes = true;
            break;
        }
        char c = b[n -1];
        for(int j = n - 1; j >= 1; j--)
        {
            b[j] = b[j - 1];
        }
        b[0] = c;
    }
    if(yes)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
	int nn[4];
	scanf("%1d%1d%1d%1d",&nn[0],&nn[1],&nn[2],&nn[3]);
	int i,j;
	for(i=0;i< 1<<3;i++)
	{
		int n=nn[0],t=i;
		for(j=1;j<=3;j++)
		{
			if(t%2 == 0)
				n += nn[j];
			else
				n -= nn[j];
			t /= 2;
		}
		if(n == 7)
			break;
	}
	printf("%d",nn[0]);
	for(j=1;j<=3;j++)
	{
		if(i%2 == 0)
			printf("+");
		else
			printf("-");
		printf("%d",nn[j]);
		i /= 2;
	}
	printf("=7\n");
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int N;
    scanf("%d", &N);
    int A[N];
    for (int i=0; i<N; i++){
        scanf("%d", &A[i]);
    }
    int max = 0;
    int max2 = 0;
    for (int i=0; i<N; i++){
        if(A[i] >= max){
            max2 = max;
            max = A[i];
        }
        else if(A[i] >= max2){
            max2 = A[i];
        }
    }
    for (int i=0; i<N; i++){
        if(max == A[i]){
            printf("%d\n", max2);
        }
        else printf("%d\n", max);
    }
    return 0; 
}


Measured memory_bytes: 2304
s_list = list()

while True:
    h,w = map(int,input().split())
    s_pair = [h,w]
    if s_pair == [0,0]:
        break
    s_list.append(s_pair)

for pair in s_list:
    for h in range(pair[0]):
        for w in range(pair[1]):
            print('#', end='')
        print('')
    print('')



Measured memory_bytes: 7012
import java.util.Scanner;

public class Main {

	Scanner sc;

	Main() {
		sc = new Scanner(System.in);
	}

	void run() {
		int map[][] = new int[201][17];

		for (int i = 0; i < 201; i++) {
			for (int m = 2; m <= 16; m++) {
				String a = Integer.toString(i, m);
				boolean ok = true;
				for (char c : a.toCharArray()) {
					ok = Character.isDigit(c);
					if (!ok) {
						break;
					}
				}
				if (ok) {
					map[i][m] = Integer.valueOf(a);
				} else {
					map[i][m] = Integer.MAX_VALUE;
				}
			}
		}

		for (;;) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();

			if ((a & b & c) == -1) {
				break;
			}

			int now = b;

			boolean ok = false;
			for (int m = 2; m < 17; m++) {
				if (map[a][m] == b) {
					ok = true;
					break;
				}
			}

			if (!ok) {
				System.out.println(-1);
				continue;
			}

			for (int i = a + 1; i <= c; i++) {
				int next = Integer.MAX_VALUE;
				for (int m = 2; m < 17; m++) {
					if (map[i][m] >= now) {
						next = Math.min(next, map[i][m]);
					}
				}
//				System.out.println(i+" "+next);
				now = next;
			}
			if (now == Integer.MAX_VALUE) {
				System.out.println(-1);
			} else {
				System.out.println(now);
			}
		}
	}

	public static void main(String[] args) {
		Main m = new Main();
		m.run();
	}

}

Measured memory_bytes: 13000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

ll n,ans[15],ANS;
vector<pair<ll,ll>>ch[15];
void dep(ll now){
	if(now==n){
		bool fi=true;
		for(ll i=0;i<n;i++){
			if(ans[i]){
				for(ll j=0;j<ch[i].size();j++){
					ll ko=ch[i][j].second;
					ll num=ch[i][j].first;
					if(ans[num]!=ko){
						fi=false;
					}
				}
			}
		}
		if(fi){
			ll cnt=0;
			for(ll i=0;i<n;i++){
				if(ans[i]){
					cnt++;
				}
			}
			ANS=max(ANS,cnt);
		}
		return;
	}
	ans[now]=0;dep(now+1);
	ans[now]=1;dep(now+1);
}
int main() {
	cin>>n;
	for(ll i=0;i<n;i++){
		ll now;
		cin>>now;
		for(ll j=0;j<now;j++){
			ll x,y;
			cin>>x>>y;
			x--;
			ch[i].push_back(make_pair(x,y));
		}
	}
	dep(0);
	cout <<ANS;
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define divup(a,b) ( ( (a) + ( (b) - 1u) ) / (b) ) // a/b の余り切り上げ
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
ll mod = 1000000007;
ll mod9 = 1000000009;

signed main(){
    ll n;
    cin>>n;
    vector<ll> a(n-1,0);
    vector<ll> ans(n,0);
    rep(i,n-1){
        cin>>a[i];
    }
    rep(i,n-1){
        ans[a[i]-1]++;
    }
    rep(i,n) cout<<ans[i]<<endl;
}


Measured memory_bytes: 6428
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main {

	public static void main(String[] args) {
		Task task = new Task();
		task.solve();
	}

	public static class Task {
		static final long MOD = (long) 1e9 + 7;

		public void solve() {
			Scan sc = new Scan();
			int n = (int) sc.scanLong();
			char[] carr = new char[n];
			int[] whites = new int[n];
			for (int i = 0; i < n; ++i) {
				carr[i] = sc.scanChar();
				whites[i] = carr[i] == '.' ? 1 : 0;
				if (i > 0)
					whites[i] += whites[i - 1];
			}
			int res = whites[n - 1];
			for (int i = 0; i < n; ++i) {
				res = Math.min(res, whites[n-1]-whites[i] + (i+1-whites[i]));
			}
			System.out.println(res);
		}
	}

	public static class Scan {
		private byte[] buf = new byte[1024];
		private int index;
		private InputStream in;
		private int total;

		public Scan() {
			in = System.in;
		}

		public int scan() {
			if (total < 0)
				throw new InputMismatchException();
			if (index >= total) {
				index = 0;
				try {
					total = in.read(buf);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				if (total <= 0)
					return -1;
			}
			return buf[index++];
		}

		public long scanLong() {
			long integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public double scanDouble() throws IOException {
			double doub = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doub *= 10;
					doub += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doub += (n - '0') * temp;
						n = scan();
					} else
						throw new InputMismatchException();
				}
			}
			return doub * neg;
		}

		public String scanString() {
			StringBuilder sb = new StringBuilder();
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			while (!isWhiteSpace(n)) {
				sb.append((char) n);
				n = scan();
			}
			return sb.toString();
		}

		public char scanChar() {
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			return (char) n;
		}

		private boolean isWhiteSpace(int n) {
			if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
				return true;
			return false;
		}
	}
}


Measured memory_bytes: 34128
import java.io.*;
import java.util.*;

class Main{
	public static void main(String[] args){
		solve();
	}

	public static void solve(){
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		if(x<y){
			int tmp = x;
			x = y;
			y = tmp;
		}

		while(true){
			int a = x % y;
			if(a==0){
				break;
			}
			x = y;
			y = a;
		}

		System.out.println(y);
	}
}




Measured memory_bytes: 26388
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	h := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&h[i])
	}

	sort.Ints(h)

	if len(h) >= k {
		fmt.Println(sum(h[:len(h)-k]))
	} else {
		fmt.Println(0)
	}

}

func sum(data []int) int {
	sum := 0
	for _, d := range data {
		sum += d
	}
	return sum
}


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

int main() {
	// your code goes here
	int n;
	cin>>n;
	vector<int>vec(n+2,0);
	for(int i=1;i<=n;i++)
	cin>>vec[i];
	unordered_map<int,int>mp;
	for(int i=1;i<=n;i++)
	mp[i+vec[i]]++;
	long long count=0;
	for(int i=1;i<=n;i++)
	count+=mp[i-vec[i]];
	cout<<count;
	return 0;
}

Measured memory_bytes: 19432
N=int(input())
S=input()
ans = 0
d={'R':0,'G':0,'B':0}
R,G,B=[],[],[]
for i in S:
    d[i]+=1
    R.append(d['R'])
    G.append(d['G'])
    B.append(d['B'])
for i in range(N-2):
    for j in range(i+1,N-1):
        s = [S[i],S[j]]
        if len(set(s))==2:
            if 'R' not in s:
                ans += R[-1]-R[j]
            elif 'G' not in s:
                ans += G[-1]-G[j]
            else:
                ans += B[-1]-B[j]
            if 0<=2*j-i<N and len(set([S[i],S[j],S[2*j-i]]))==3:
                ans -=1
print(ans)

Measured memory_bytes: 74476
S=input()

N=len(S)
if N==1:
    print(eval(S))
    exit()
t=[S[0]]*(2*N-1)
for i in range(1,N):
    t[2*i-1]=''
    t[2*i]=S[i]
ans=0
for i in range(1<<(N-1)):
    p=t[:]
    j=1
    while i:
        if i&1:
            p[2*j-1]='+'
        i>>=1
        j+=1
    ans+=eval(''.join(p))
print(ans)


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

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)

/***** MAIN *****/
signed main() {
  int n, ans=0;
  scanf("%d", &n);

  int boxes[n];
  REP(i,n) scanf("%d", &boxes[i]);
  if(n == 1) {
    cout << "Yes\n";
    return 0;
  }

  bool continueFlag = false;
  REPS(i,1,n) {
    int upDiff = boxes[i] - boxes[i-1];
    if(upDiff >= 1) {
      continueFlag = false;
    } else if(upDiff == 0) {
      // keep the status
    } else if(upDiff == -1) {
      if(continueFlag) {
        cout << "No\n";
        return 0;
      }
      continueFlag = true;
    } else {
      cout << "No\n";
      return 0;
    }
  }
  cout << "Yes";
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 640
def myAnswer(N:int,M:int) -> int:
   if(N == 1 and M == 1): return 1
   if(min(N,M) == 1): return max(N,M) - 2
   if(min(N,M) == 2): return 0
   return N*M - (max(N,M) * 2 + (min(N,M) - 2) * 2)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   print(myAnswer(N,M))
if __name__ == '__main__':
   main()

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

int a[100100];
int b[100100];
int res[100100];
ll dp[100100];
const int mod = 1e9 + 7;

int main(void){
  fill(res,res+100100,-1);
  fill(dp,dp+100100,-1);
  int n;
  cin >> n;
  for(int i = 1;i <= n;++i){
    int temp;
    cin >> temp;
    a[i] = temp;
  }
  for(int i = 1;i <= n;++i){
    int temp;
    cin >> temp;
    b[i] = temp;
  }
  if(a[1] > b[1] ||
     b[n] > a[n]){
    cout << "0" << endl;
    return 0;
  }
  res[1] = a[1];
  for(int i = 2;i <= n;++i){
    if(a[i] > a[i-1])res[i] = a[i];
  }
  res[n] = b[n];
  for(int i = n-1;i >= 1;--i){
    if(b[i] > b[i+1]){
      if(b[i] > a[i]){
	cout << "0" << endl;
	return 0;
      }
      res[i] = b[i];
    }
  }
  dp[0] = 1;
  for(int i = 1;i <= n;++i){
    if(res[i] != -1){
      dp[i] = dp[i-1];
    }else {
      dp[i] = dp[i-1] * min(a[i],b[i]);
      dp[i] %= mod;
    }
  }
  cout << dp[n] << endl;
  return 0;
}


Measured memory_bytes: 2176
from collections import Counter as C
n = int(input())
v = [int(a) for a in input().split()]

k1 = C(v[::2]).most_common()[0][0]
v1 = C(v[::2]).most_common()[0][1]

if v1 == n/2:
    k2 = 0
    v2 = 0
else:
    k2 = C(v[::2]).most_common()[1][0]
    v2 = C(v[::2]).most_common()[1][1]

k3 = C(v[1::2]).most_common()[0][0]
v3 = C(v[1::2]).most_common()[0][1]

if v3 == n/2:
    k4 = 0
    v4 = 0
else:
    k4 = C(v[1::2]).most_common()[1][0]
    v4 = C(v[1::2]).most_common()[1][1]

if k1 != k3:
    print (n - v1 - v3)
else:
    print (min(n - v1 - v4, n - v2 - v3))

Measured memory_bytes: 17116
#include <iostream>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n;i++)
int main(void) {
	ll x, sum = 0, y, l;cin >> x >> y;vector<ll> v(x);
	rep(i, x) cin >> v[i];
	sort(v.begin(), v.end());
	for (int i = 0; i < x - y;i++) {
		sum += v[i];
	}
	cout << sum << endl;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int main()
{
	int n,ans;
	long long f[45]={2};
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		f[i]=f[i-1]*2+2;
	}
	printf("%lld\n",f[n]);
	return 0;
}

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

#define pb push_back
#define ll long long
#define pi pair<int,int>
#define pii pair<int,pi>
#define pl pair<ll,ll>
#define pll pair<ll,pl>
#define debug cout<<"debugging"<<endl
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int I_LIMIT = 999999999;
ll L_LIMIT = 19999999999999999;
ll mod = 1000000007;
vector <int> v[100005];

void solve()
{
    ll n,i,a1=0,a2=0,a3=0,a4=0,a=0;
    cin>>n;
    ll A[n][2];
    for(i=0;i<n;i++)
        cin>>A[i][0]>>A[i][1];
    
    ll maxma=-L_LIMIT,maxmb=-L_LIMIT,minma=L_LIMIT,minmb=L_LIMIT;

    for(i=0;i<n;i++)
    {
        maxma = max(maxma,A[i][0]+A[i][1]);
        minma = min(minma,A[i][0]+A[i][1]);
        maxmb = max(maxmb,A[i][0]-A[i][1]);
        minmb = min(minmb,A[i][0]-A[i][1]);
    }
    //cout<<maxma<<" "<<maxmb<<" "<<minma<<" "<<minmb<<"\n";
    for(i=0;i<n;i++)
    {
        a1 = abs(maxma-(A[i][0]+A[i][1]));
        a2 = abs(minma-(A[i][0]+A[i][1]));
        a3 = abs(maxmb-(A[i][0]-A[i][1]));
        a4 = abs(minmb-(A[i][0]-A[i][1]));
        a = max(a,max(max(a1,a2),max(a3,a4)));
    }
    cout<<a<<"\n";
    return;
}
int main()
{
    IOS;
    int t;
    //cin>>t;
    //for(int i=1;i<=t;i++)
        solve();
}


Measured memory_bytes: 9020
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
#include<queue>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=0;(i)<(n);(i)++)
#define FOR(i,m,n) for(int i=(m);(i)<(n);(i)++)
typedef long long ll;

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

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

int main()
{
	string S;
	int K;
	cin >> S >> K;
	char ans;
	int i = 0;
	while (1)
	{
		if (S[i] != '1')
		{
			ans = S[i];
			break;
		}
		else
			i++;
	}
	if (K <= i)
		ans = '1';
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <bitset>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
#include <sstream>
#include <math.h>

using namespace std;

#define ll long long int
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecchar vector<char>
#define vecstr vector<string>
#define vecbool vector<bool>
#define vec2bool vector<vector<bool>>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,j,b) for(ll s = j;s < b;s++)
#define forllde(s,j) for(ll s = j;s > 0;s--)

#define Pi 3.1415926535897932384626

int main() {
	ll n, ans = 0;
	string s;
	bool flag = false;

	cin >> n;

	ll ac=0, wa=0, tle=0, re=0;

	vecstr result(n);

	forll(i, 0, n)
		cin >> result[i];

	forll(i, 0, n)
	{
		if (result[i] == "AC")
		{
			ac++;
		}
		else if (result[i] == "WA")
		{
			wa++;
		}
		else if (result[i] == "TLE")
		{
			tle++;
		}
		else if (result[i] == "RE")
		{
			re++;
		}
	}

	cout << "AC x " << ac << "\n" << "WA x " << wa << "\n" << "TLE x " << tle << "\n" << "RE x " << re;
}


Measured memory_bytes: 6420
import sys
input = sys.stdin.readline
import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

from collections import deque
n = int(input())
st = deque([])

edge = deque([[] for i in range(n)])
for i in range(n):
    x,y = map(int,input().split())
    st_append = st.append
    st_append((i,x,y))
    
from operator import itemgetter
bb = tuple(sorted(st,key=itemgetter(1)))
chk = tuple(sorted(st,key=itemgetter(2)))
#print(bb,chk)

for i in range(n-1):
  x = bb[i][0]
  y = bb[i+1][0]
  z = bb[i+1][1]-bb[i][1]
  edge[x].append((z,y))
  edge[y].append((z,x))
  
for i in range(n-1):
  a = chk[i][0]
  b = chk[i+1][0]
  c = chk[i+1][2]-chk[i][2]
  edge[a].append((c,b))
  edge[b].append((c,a))
  
edge = tuple(edge)
print(prim_heap())

Measured memory_bytes: 113200
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define vector2(a,b,c) vector<vector<int>> a(b/*縦！w*/,vector<int>(c/*横！w*/))
#define INF 1e10
#define MOD 1e9+7
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; }
using Graph = vector<vector<int>>;
int a,b;
char c[30][30];
int e=0;
int dx[4]={0,0,1,-1},dy[4]={-1,1,0,0};
int bfs(int x,int y){
int d[30][30];
  rep(i,a)rep(j,b)
  d[i][j]=-1;
  queue<P> q;
  d[x][y]=0;
  q.push(P(x,y));
  while(q.size()){
  P p=q.front();
    q.pop();
    rep(i,4){
    int nx=p.first+dx[i],ny=p.second+dy[i];
      if(0<=nx&&nx<a&&0<=ny&&ny<b&&d[nx][ny]==-1&&c[nx][ny]=='.'){
      q.push(P(nx,ny));
        d[nx][ny]=d[p.first][p.second]+1;
      }
    }
  }
  rep(i,a)rep(j,b){
    if(e<d[i][j])
      e=d[i][j];
    }
  return e;
}
signed main(){
  cin>>a>>b;
  rep(i,a)rep(j,b)
    cin>>c[i][j];
  priority_queue<int> que;
  rep(i,a)rep(j,b){
  if(c[i][j]=='.'){
    que.push(bfs(i,j));
    e=0;
    }
  }
  cout<<que.top()<<endl;
}

Measured memory_bytes: 256
#n = int(input())
x, k, d = map(int, input().split())
#l = list(map(int,input().split()))
#l = [list(map(int,input().split())) for i in range(n)]

x_abs = abs(x)
movenum = x_abs//d
if movenum >= k:
    ans = x_abs-d*k
else:
    x_abs -= d*movenum
    numleft = k-movenum
    if numleft % 2 == 0:
        ans = x_abs
    else:
        ans = abs(x_abs-d)
print(ans)


Measured memory_bytes: 9048
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)
INF = 1<<32


def solve(N: int, A: "List[int]"):
    ans = 1
    t = 1
    for i in range(N):
        # if A[i] == 1 or A[i] == 100:
        #     t *= 2
        #     continue

        t *= 3
        if A[i]%2 == 0:
            ans *= 2
        
    print(t-ans)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
import java.util.HashMap;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int h= sc.nextInt();
		int w = sc.nextInt();
		int n = sc.nextInt();
		Point [] p=  new Point[n];
		HashMap<Point, Integer> map = new HashMap<Point, Integer>();
		for(int i=0;i<n;i++) {
			int a= sc.nextInt()-1;
			int b = sc.nextInt()-1;
			p[i] = new Point(a,b);
			for(int x=a-1;x<=a+1;x++) {
				for(int y=b-1;y<=b+1;y++) {
					if(x>=1 && x<(h-1) && y>=1 && y<(w-1))
					map.put(new Point(x,y),map.getOrDefault(new Point(x,y),0)+1);
				}
			}
		}
		long ret[] = new long[10];
		long tot =0;
		for(Point key : map.keySet()) {
//			System.out.println(map.get(key) + " " + key.a + " " + key.b);
			ret[map.get(key)]++;
			tot++;
		}
		StringBuilder sb = new StringBuilder();
		ret[0] = (long) (h-2)*(w-2)-tot;

		for(int i=0;i<10;i++) {
			sb.append(ret[i]);
			sb.append("\n");
			
		}
		System.out.println(sb.toString());
		
	}
	static class Point{
		int a;
		int b;
		public Point(int a,int b) {
			this.a = a;
			this.b = b;
		}
		@Override
		public int hashCode() {
			return 1297273*a+1299827*b;
		}
		@Override
		public boolean equals(Object o) {
			Point c = (Point)o;
			return (c.a==a && c.b==b);
		}
	}

}


Measured memory_bytes: 137112
S = input()
if S == 'SUN': print(7)
elif S == 'MON': print(6)
elif S == 'TUE': print(5)
elif S == 'WED': print(4)
elif S == 'THU': print(3)
elif S == 'FRI': print(2)
else: print(1) 

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

int main()
{
	int n, k;
	cin >> n >> k;
	bool snk[100];
	std::fill(std::begin(snk), std::end(snk), false);
	for (int i = 0; i < k; i++)
	{
		int d;
		cin >> d;
		for (int j = 0; j < d; j++)
		{
			int a;
			cin >> a;
			snk[a - 1] |= true;
		}
	}
	cout <<( n - std::count(std::begin(snk), std::end(snk), true)) << endl;
}

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

int main() {
    int N, M;
    cin>>N;
    M = 0;
    vector<int> a(N, 0), b(N, 0);
    REP(i, 0, N){
        cin >> a[i]; 
    }
    for(int i = N; i>0; i--){
        int j = i;
        int sum = 0;
        while(j <= N){
            sum += b[j-1];
            j += i;
        }
        if(sum%2 != a[i-1]){
            M++;
            b[i-1] = 1;
        }        
    }
    cout << M << endl;
    REP(i, 0, N){
        if(b[i]) cout << i+1 << " ";
    }
    if(M) cout << endl;
    return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define mod 1000000007
#define MOD 998244353
#define db(a) cout << a << endl
#define adb(a) for(auto i:a) cout << i << " "
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

long long w[100], v[100];
long long dp[2][100010];

int main()
{
    long long n, W;
    cin >> n >> W;

    long long i, j, ans = 0, maxi = 0;
    for(i=0;i<n;i++)
    {
        cin >> w[i];
        cin >> v[i];
        maxi += v[i];
    }

    //memset(dp, 0, sizeof(dp));
    for(i=1;i<=maxi;i++) dp[0][i] = INT_MAX;

    for(i=0;i<n;i++)
    {
        for(j=0;j<=maxi;j++)
        {
            if(v[i] <= j) dp[1-i%2][j] = min(dp[i%2][j-v[i]] + w[i], dp[i%2][j]);
            else dp[1-i%2][j] = dp[i%2][j];
        }
    }

    int row;
    if(n%2) row = 1;
    else row = 0;

    for(i=0;i<=maxi;i++) if(dp[row][i] <= W) ans = i;
    cout << ans << endl;
}


Measured memory_bytes: 1920
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define reps(i,a,b) for(int i=a;i<b;++i)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    string s;
    cin >> s;
    int q;
    cin >> q;
    while (q--) {
        string com, p; int a, b;
        cin >> com >> a >> b;
        if (com == "replace") {
            cin >> p;
            for (int i = a; i <= b; ++i) s[i] = p[i-a];
        } else if (com == "reverse") {
            reverse(s.begin() + a, s.begin() + b + 1);
        } else {
            cout << s.substr(a, b-a+1) << endl;
        }
    }
}



Measured memory_bytes: 3240
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
static const int MAX = 10000;
static const int INFTY = (1<<20);
 static const int WHITE = 0;
 static const int GRAY  = 1;
 static const int BLACK  = 2;

int n;
vector<pair<int , int > > adj[MAX];

void dijkstra() {
  priority_queue<pair<int ,int > > PQ;
  int color[MAX];
  int d[MAX];
  for(int i = 0;i<n;i++)  {
    d[i] = INFTY;
    color[i] = WHITE;
  }

  d[0]=0;
  PQ.push(make_pair(0,0));
  color[0] = GRAY;

  while(!PQ.empty()) {
    pair<int ,int > f= PQ.top();PQ.pop();
    int u = f.second;
    color[u]= BLACK;

    if(d[u]<f.first * (-1)) continue;
    for(int j=0;j<adj[u].size() ; j++) {
      int v=adj[u][j].first;
      if(color[v]== BLACK) continue;
      if(d[v] > d[u]+adj[u][j].second) {
        d[v]= d[u]+adj[u][j].second;


        PQ.push(make_pair(d[v]*(-1),v));
        color[v]= GRAY;
      }
    }
  }
  for(int i = 0;i<n;i++) {
    cout << i<<" " <<(d[i] == INFTY ? -1:d[i] ) << endl;

  }
}

int main() {
  int k,u,v,c;

  cin >> n;
  for(int i=0;i<n;i++) {
    cin>>u>>k;
    for(int j=0;j<k;j++){
      cin >> v >> c;
      adj[u].push_back(make_pair(v,c));
    }
  }

  dijkstra();

  return 0;
}

Measured memory_bytes: 8096
#include "bits/stdc++.h"

using namespace std;

using ll = long long;

const int MAX_H = 10000;
const ll inf = 1e15;
// dp[i]:=i減らすのに必要なコスト
vector<ll> dp(100010, inf);

int main() {
  ll h, n;
  cin >> h >> n;
  ll ret = inf;
  dp[0] = 0;
  for (int i = 0; i < n; i++) {
    ll a, b;
    cin >> a >> b;
    for (int j = 0; j < h; j++) {
      dp[j + a] = min(dp[j + a], dp[j] + b);
      if (j + a >= h) ret = min(ret, dp[j + a]);
    }
  }
  cout << ret << endl;
}


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

int main(){
    int N,K;
    cin >> N >> K;
    map<int, int> A;
    for(int i = 1; i<=N; i++) A[i] = 0;
    for (int i = 0; i<K; i++) {
        int tmp;
        cin >> tmp;
        for(int j = 0; j<tmp; j++) {
            int holder;
            cin >> holder;
            A[holder]++;
        }
    }
    int res = 0;
    for ( auto x : A) {
        if (x.second == 0) res++;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#define VIZ2 {printf("graph G{\n"); for(int i=1;i<=n;i++) for es(i,e) if(vb[e]>=i)printf("%d--%d;\n",i,vb[e]); puts("}");}
#define SZ 666666
int n,m,q; Edg
pii edt[SZ][11];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		adde(a,b);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int v,d,c;
		scanf("%d%d%d",&v,&d,&c);
		edt[v][d]=max(edt[v][d],
		pii(i,c));
	}
	for(int i=10;i>=1;--i)
	{
		for(int j=1;j<=n;j++)
		{
			edt[j][i-1]=max(edt[j][i-1],
			edt[j][i]);
			for esb(j,e,b)
				edt[b][i-1]=max(edt[b][i-1],
				edt[j][i]);
		}
	}
	for(int j=1;j<=n;j++)
		printf("%d\n",edt[j][0].se);
}


Measured memory_bytes: 19072
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; double w; };

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	for (;;) {
		int T; cin >> T;
		if (T == 0) break;
		vector<int> t(T);
		for (int j = 0; j < T; j++)
			cin >> t[j];
		int N; cin >> N;
		vector<int> a(100, 24);
		while (N--) {
			int D, M; cin >> D >> M;
			a[D - 1] = min(a[D - 1], M);
		}
		vector<int> dp(T, INT_MAX);
		dp[0] = 0;
		for (int d = 0; d < 100; d++) {
			for (int j = 0; j < T; j++)
				if (t[j] > a[d])
					dp[j] = INT_MAX;
			vector<int> _dp(T);
			for (int j = 0; j < T; j++)
				_dp[(j + 1) % T] = dp[j];
			int mini = INT_MAX;
			for (int j = 0; j < T; j++)
				mini = min(mini, dp[j]);
			_dp[0] = min(_dp[0], mini + 1);
			dp = _dp;
		}
		int mini = INT_MAX;
		for (int j = 0; j < T; j++)
			mini = min(mini, dp[j]);
		cout << mini << endl;
	}
}

Measured memory_bytes: 1216
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
	string s;
	cin >>s;
	int n = s.size();
	int sol = 0;
	bool b = false;
	for (int i=0 ; i<n ; i++) {
		if (i!=n-1) {
			if (s[i] == s[i+1] and b == false) {
				sol++;
				i++;
				b = true;
				continue;
			} else {
				sol++;
				b = false;
				continue;
			}
		}
		sol++;
	}
	printf("%d\n", sol);
	return 0;
}

Measured memory_bytes: 640
S = input()
ans = 10 ** 6
# 奇数番目が1のケース
temp = 0
for i in range(len(S)):
    if i & 1 :
        if S[i] == '0':
            temp += 1
    else:
        if S[i] != '0':
            temp += 1
ans = min(ans,temp)
# 奇数番目が0のケース
temp = 0
for i in range(len(S)):
    if i & 1 :
        if S[i] != '0':
            temp += 1
    else:
        if S[i] == '0':
            temp += 1
ans = min(ans,temp)
print(ans)

Measured memory_bytes: 3188
export class Main {
  static main(input: string): string {
    const tmp: string[] = input.split("\n");
    const [n, k]: number[] = tmp.shift().split(" ").map(int => parseInt(int));
    const h: number[] = tmp.shift().split(" ").map(int => parseInt(int));
    return `${h.filter(i => i >= k).length}`;
  }
}
console.log(Main.main(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 28608
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
#define show(x) cout << #x << " is " << x << "\n";
typedef vector<ll> vi;
#define fi first
#define se second
const ll inf = INT_MAX;
const ll mod = 1e9 + 7;

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2, mod);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

const ll N = 1e5 + 2;
vector<ll> adj[N];
bool visited[N];

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

	ll n, m;
	cin>>n>>m;
	ll u, v;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		adj[u].pb(v);
		
	}
	ll s, t;
	cin>>s>>t;
	
	ll dist[n+1][3];
	for(int i=0;i<=n;i++){
	    for(int j=0;j<=3;j++){
	        dist[i][j] = inf;
	    }
	}
	//memset(dist, inf, sizeof(dist));
	
	queue<pair<ll, ll > > q;
	q.push({s, 0});
	dist[s][0] = 0;
	while(!q.empty()){
		pair<ll, ll> temp = q.front();
		q.pop();
		for(auto er : adj[temp.first]){
			int yu = temp.second + 1;
			yu = yu%3;
			
			if(dist[er][yu] == inf){
				dist[er][yu] = dist[temp.first][temp.second] + 1;
				q.push({er, yu});
			}
		}
	}
	ll ans = dist[t][0];
	
	if(ans == inf) ans=-1;
	else ans/=3;
	
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 8064
N = int(input())
list_A = list(input().split())
list_a = list(map(int, list_A))

Alice = 0
Bob = 0

if N % 2 == 0:
    for _ in range(int(N / 2)):
        Max = max(list_a)
        Alice += Max
        list_a.remove(Max)

        Max = max(list_a)
        Bob += Max
        list_a.remove(Max)

else:
    for _ in range(int((N - 1) / 2)):
        Max = max(list_a)
        Alice += Max
        list_a.remove(Max)

        Max = max(list_a)
        Bob += Max
        list_a.remove(Max)

    Alice += list_a[0]

print(Alice - Bob)

Measured memory_bytes: 3064
#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, K, Q = map(int, input().split())

A = [0] * N
for i in range(Q):
    a = int(input())
    A[a-1] += 1

for i in range(N):
    if A[i] - Q + K - 1 >= 0:
        print('Yes')
    else:
        print('No')




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

int main(){

  while(1){
    int a, b;
    string op;
    cin>>a>>op>>b;
    if(op == "?") break;


    int  ans;
    if(op == "+") ans = a + b;
    if(op == "-") ans = a - b;
    if(op == "*") ans = a * b;
    if(op == "/") ans = a / b;

    cout<<ans<<endl;

  }
  return 0;
}



Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<char> vc;
#define INF __INT32_MAX__
#define LINF __LONG_LONG_MAX__

int main() {
    int N, M; cin >> N >> M;
    vi S(N), T(N), C(N); rep(i, N) { cin >> S[i] >> T[i] >> C[i]; }

    const int N_MAX = 100005;

    // 種類ごとに店にいた時刻を計測する
    // 各種類で求めた後に、全体で計算する

    vi mm(N_MAX);

    vi imos(N_MAX);
    for (int i = 1; i <= M; i++) {
        // 種類ごとに店にいた時刻を計測
        for (int j = 0; j < N_MAX; j++) imos[j] = 0;


        for (int j = 0; j < N; j++) {
            if (C[j] == i) {
                imos[S[j]]++;
                imos[T[j]]--;
            }
        }

        for (int j = 0; j < N_MAX - 1; j++) {
            imos[j + 1] += imos[j];
        }

        for (int j = 0; j < N_MAX - 1; j++) {
            if (imos[j] == 0 && imos[j + 1] == 1) {
                mm[j]++;
            } else if (imos[j] == 1) mm[j]++;
        }
    }
    int cnt = 0;
    rep(i, N_MAX) {
        cnt = max(cnt, mm[i]);
    }

    cout << cnt << endl;
}

Measured memory_bytes: 5104
N=int(input())
i=0
for n in range(0,N):
    d1,d2=[int(x) for x in input().split(' ')]
    if d1==d2:
        i+=1
        if i >= 3:
            print("Yes")
            break
    else:
        i=0
if i < 3:
    print("No")

Measured memory_bytes: 9168
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define INF (1<<29)
int dp[10000][10000];
int main()
{
	fill(dp[0], dp[1000], INF);
	string s1, s2; cin >> s1 >> s2;
	int s1sz = s1.size(), s2sz = s2.size();
	for (int i = 0; i <= s1sz; ++i) {
		for (int j = 0; j <= s2sz; ++j) {
			if (i == 0) {
				dp[0][j] = j;
				continue;
			}
			else if (j == 0) {
				dp[i][0] = i;
				continue;
			}
			else {
				dp[i][j] = min(dp[i - 1][j - 1] + (s1[i - 1] != s2[j - 1]), min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
			}
		}
	}
	cout << dp[s1sz][s2sz] << endl;
}

Measured memory_bytes: 42144
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author ks96neko
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BAcCepted solver = new BAcCepted();
        solver.solve(1, in, out);
        out.close();
    }

    static class BAcCepted {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            String r = in.next();
            int rl = r.length();

            String r0 = r.substring(0, 1);
            String a = "A";

            String rb = r.substring(2, rl - 1);
            int c1 = rb.indexOf("C");
            int cn = rb.lastIndexOf("C");

            if (a.equals(r0)) {
                if (c1 != -1 && cn != -1) {
                    if (c1 != cn) {
                        out.println("WA");
                    } else {
                        for (int i = 1; i < rl; i++) {
                            if (r.charAt(i) != 'C' && Character.isUpperCase(r.charAt(i))) {
                                // System.out.println(i+"で　WA:なぜなら"+r.charAt(i)+"が大文字だから");
                                out.println("WA");
                                return;
                            }
                        }
                        out.println("AC");
                    }
                } else {
                    out.println("WA");
                }
            } else {
                out.println("WA");
            }
        }

    }
}



Measured memory_bytes: 23764
// abc125_c
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

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


template<typename T>
struct SegmentTree {
    using F = function<T(T, T)>;
    int n;
    F f;
    T ti;
    vector<T> dat;
    SegmentTree(F f, T ti, int n_) : f(f), ti(ti) {
        n = 1;
        while (n < n_) n <<= 1;
        dat.assign(n << 1, ti);
    }
    void update(int k, T x) {
        k += n - 1;
        dat[k] = x;
        while (k > 0){
            k = (k - 1) / 2;
            dat[k] = f(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r) {
        // [a, b)と[l, r)が交差しなければ単位元を返す
        if (r <= a || b <= l) return ti;

        // [a, b)が[l, r)を完全に含んでいればその節点の値
        if (a <= l && r <= b) return dat[k];

        int m = (l + r) / 2;
        T vl = query(a, b, k*2+1, l, m);
        T vr = query(a, b, k*2+2, m, r);
        return f(vl, vr);
    }
    T query(int a, int b) { // wrapper
        return query(a, b, 0, 0, n);
    }
};

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];

    auto f = [](int a, int b){return gcd(a, b);};
    int ti = 0;
    auto segtree = SegmentTree<int>(f, ti, N);

    REP(i, N) segtree.update(i, A[i]);

    int ans = segtree.query(0, N);
    REP(i, N){
        segtree.update(i, 0);
        ans = max(ans, segtree.query(0, N));
        segtree.update(i, A[i]);
    }
    print(ans);

    return 0;
}


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

int main() {
  long long A=100,X,B;
  cin >> X;
  for (int i=0 ; true ; i++){
    B=A*1.01;
    A=B;
    if (A>=X){
      cout << i+1 << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 3636