akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main {
	static PrintWriter out;
	static StringBuilder sb;
	static int n, m, k;
	static long mod = 998244353;
	static Boolean[][][] memo;
	static String s;
	static HashMap<Integer, Integer> nums;
	static ArrayList<Integer>[] ad;
	static int inf = 1000000;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		long n = sc.nextInt();
		for (long i = -1000; i <= 1000; i++) {
			for (long j = -1000; j <= 1000; j++) {
		//		System.out.println((i * i * i * i * i)+" "+(j * j * j * j * j));
				if (i * i * i * i * i - j * j * j * j * j == n) {
					System.out.println(i+" "+j);
					return;
				}
			}
		}
		out.flush();
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public int[] nextArrInt(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public long[] nextArrLong(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

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

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))
#define rep(i,a,b) for(int (i)=int(a);(i)<int(b);(i)++)
#define rrep(i,a,b) for(int (i)=int(a);(i)>=int(b);(i)--)

#define put(a) cout << (a) << endl
#define puts(a) cout << (a) << " "

#define llint long long int

#define INF (long long)(1e9+1)
#define MOD (long long)(1e9+7)
#define INF64 (long long)(1e18+1)

#define F first
#define S second

#define Pii  pair<int,int>
#define Pll  pair<long long,long long>
#define Piii pair<int,pair<int,int>>
#define Plll pair<long long,pair<long long,long long>>

#define Vll(a,b,c)    vector<vector<long long>> (a)((b),vector<long long>((c))
#define Vlll(a,b,c,d) vector<vector<vector<long long>>> (a)((b),vector<vector<long long>>((c),vector<long long>((d)))

#define MAX_N 1000000

llint my_binary_search(llint ary[], llint key, llint left, llint right) {
	llint middle;
	if (right < left) {
		return -(INF64);
	} else {
		middle = left + (right - left) / 2;
		if (ary[middle] > key) {
			return my_binary_search(ary, key, left, middle - 1);
		} else if (ary[middle] < key) {
			return my_binary_search(ary, key, middle + 1, right);
		} else {
			return middle;
		}
	}
}

struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	
	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for(int i = 0; i < N; i++) par[i] = i;
	}
	
	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}
	
	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}
	
	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
llint N;

int main (void)
{
	//INPUT
	// llint N;
	cin >> N;
	vector<pair<llint,llint> > P(N);
	rep(i,0,N) {
		llint buf1,buf2;
		cin >> buf1 >> buf2;
		llint left,right;
		left=buf1-buf2;
		right=buf1+buf2;
		P[i] = make_pair(left,right);
	}
	
	sort(P.begin(),P.end());
	
	
	// llint res[N][N];
	
	// rep(i,0,N) {
	// 	rep(j,0,N) {
	// 		res[i][j] = 0;
	// 	}
	// }
	
	
	llint left=0;
	llint right=0;
	
	//SOLVE
	
	llint ans=0;
	
	vector<llint> use(N,1);
	
	rep(i,0,N-1) {
		// left = P[i].F;
		if (use[i] == 0) continue;
		
		right = P[i].S;
		rep(j,i+1,N) {
			if(use[j] == 0) continue;
			
			if(right > P[j].F) {
				if (right < P[j].S) {
					//jを使わない
					use[j] = 0;
				} else {
					right = P[j].S;
					use[i] = 0;
				}
			} else {
				break;
			}
		}
	}
	
	
	
	//OUTPUT
	
	rep(i,0,N) {
		if(use[i] == 1) {
			ans++;
		}
	}
	cout << ans << endl;
	
	return 0;
}






Measured memory_bytes: 2560
H, W = map(int, input().split())
S = []

# マップ作成
S.append("."*(W+2))
for i in range(H):
    S.append("."+input()+".")
S.append("."*(W+2))

# サーチング用マップ
search = [[0]*W for i in range(H)]

# 地雷位置確認探査機
dx = [1, 0, -1, 0, 1, 1, -1, -1]
dy = [0, 1, 0, -1, 1, -1, 1, -1]

# サーチ
for y in range(1, H+1):
    for x in range(1, W+1):
        count = 0

        for i in range(8):
                if S[y+dy[i]][x+dx[i]] == "#":
                    count +=1
                search[y-1][x-1] = count

                if S[y][x] == "#":
                    search[y-1][x-1] = "#"

# リストを外して表記
for i in range(H):
    row = list(map(str, search[i]))
    print(''.join(row))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int H, W;
int a[510][510];
using P = tuple<int, int, int, int>;
vector<P> v;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> H >> W;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> a[i][j];
    }
  }
  for (int i = 0; i < H-1; i++) {
    for (int j = 0; j < W; j++) {
      if (a[i][j] & 1) {
        v.emplace_back(i, j, i+1, j);
        a[i+1][j]++;
      }
    }
  }
  for (int j = 0; j < W-1; j++) {
    if (a[H-1][j] & 1) {
      v.emplace_back(H-1, j, H-1, j+1);
      a[H-1][j+1]++;
    }
  }
  cout << v.size() << endl;
  for (int i = 0; i < v.size(); i++) {
    int p, q, r, s;
    tie(p, q, r, s) = v[i];
    cout << p+1 << " " << q+1 << " " << r+1 << " " << s+1 << endl;
  }

  return 0;
}

Measured memory_bytes: 5232
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vi vector<int>
#define vint vector<int> 
#define inf 1000000000
#define mod 1000000007

int power(int a, int b)
{
    int prod = 1;
    while(b)
    {
        if(b&1)
        prod = (prod*a);
        a = (a*a);
        b >>= 1;
    }
    return prod;
}

int main()
{
	int n;
	cin >> n;
	int a[n];
	for(int i = 0 ; i < n ; i++)
		cin >> a[i];

	ll dp[n];
	dp[0] = 0;
	dp[1] = abs(a[0]-a[1]);
	for(int i = 2 ; i < n ; i++)
		dp[i] = min(dp[i-1]+abs(a[i-1]-a[i]) , dp[i-2] + abs(a[i]-a[i-2]));

	cout << dp[n-1];
 	return 0;

}




Measured memory_bytes: 1408
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A&lang=ja

import sys
sys.setrecursionlimit(10 ** 9)

V, E = map(int, input().split())

cost = [[float("inf")]*V for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    cost[s][t] = d

dp = [[float("inf")]*(V) for _ in range((1<<V))]

dp[0][0] = 0                                # どこにも訪れていない状態で、頂点0を出発点とする。
                                            # 最後に頂点0に戻ってくるために頂点0にフラグは立てないようにしている。

for S in range(1<<V):
    for v in range(V):
        if not (1<<v)&S:                    # vをすでに訪れている場合を除く
            dp[S|(1<<v)][v] = min(dp[S][u] + cost[u][v] for u in range(V))
                                            # "if (1<<u)&S" が必要に見えるが、Sにuが含まれないようなdpテーブルは、
                                            # dp[0][0]を除いて全てinfから動かない（漸化式の左辺に現れない）ので、自動的に除かれる。
                                            # 逆に、"if (1<<u)&S"を入れようとすると、初期化を"dp[1][0]=0"として、
                                            # かつ最後に頂点0に戻る場合を別に処理する必要があるので少し面倒。

if dp[(1<<V)-1][0] == float("inf"):
    print(-1)
else:
    print(dp[(1<<V)-1][0])




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

using u64 = std::uint64_t;
constexpr u64 inf = std::numeric_limits<u64>::max();

#define REP(i, n) for (u64 i = 0; i < (n); ++i)

namespace io {
  constexpr int is = 1 << 17;
  char ib[is], *ip = ib + is, it;
  inline char getc() {
    if (ip == ib + is) { read(STDIN_FILENO, ib, is); ip = ib; }
    return *ip++;
  }
  inline u64 scan() {
    u64 r = 0;
    if (ip + 16 > ib + is) while ((it = getc()) & 16) r = r * 10 + it - '0';
    else while ((it = *ip++) & 16) r = r * 10 + it - '0';
    return r;
  }
  constexpr int os = 1 << 17;
  char ob[os], *op = ob, ot;
  inline void putc(const char c) {
    *op++ = c;
    if (op == ob + os) { write(STDOUT_FILENO, ob, os); op = ob; }
  }
  /* x shoud be greater than or equal to zero */
  inline void print(u64 x) {
    char d[20];
    int i = 0;
    while (true) {
      d[i] = x % 10 + 48;
      x /= 10;
      ++i;
      if (x <= 0) break;
    }
    while (i--) {
      putc(d[i]);
    }
  }
  inline void flush() {
    write(STDOUT_FILENO, ob, op - ob);
  }
}

using P = pair<u64, u64>;

u64 collect(const vector<vector<u64>> &G, const vector<u64> &H, u64 u, u64 v, u64 p) {
  if (u == v) return 0;
  for (auto e : G[u]) {
    u64 t = H[e] ^ u;
    if (t == p) continue;
    u64 s = collect(G, H, t, v, u);
    if (s != inf) {
      return s | (1ULL << e);
    }
  }
  return inf;
}

signed main() {
  u64 n = io::scan();
  auto G = vector<vector<u64>>(n);
  auto H = vector<u64>(n);
  REP(i, n - 1) {
    u64 a = io::scan() - 1;
    u64 b = io::scan() - 1;
    G[a].push_back(i);
    G[b].push_back(i);
    H[i] = a ^ b;
  }
  u64 m = io::scan();
  auto paths = vector<u64>(m, 0);
  REP(j, m) {
    u64 u = io::scan() - 1;
    u64 v = io::scan() - 1;
    paths[j] = collect(G, H, u, v, -1);
  }
  u64 ans = 0;
  REP(s, 1ULL << m) {
    u64 mask = 0;
    REP(j, m) {
      if ((s >> j) & 1) {
        mask |= paths[j];
      }
    }
    if (__builtin_parityll(s)) {
      ans -= 1LL << (n - 1 - __builtin_popcountll(mask));
    } else {
      ans += 1LL << (n - 1 - __builtin_popcountll(mask));
    }
  }
  io::print(ans);
  io::flush();
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <string>
#include <map>
#include <stack>
//#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define urept(soeji, start, n) for (int soeji = start; soeji < n; soeji++)
#define drept(soeji, start, n) for (int soeji = start; soeji > n; soeji--)
int main(void)
{
    int N;
    cin >> N;
    int l[N];
    for (int i = 0; i < N; i++)
    {
        cin >> l[i];
    }
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            for (int k = j + 1; k < N; k++)
            {
                if (l[i] + l[j] > l[k] && l[j] + l[k] > l[i] && l[k] + l[i] > l[j] && l[i] != l[j] && l[j] != l[k] && l[i] != l[k])
                {
                    cnt++;
                }
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

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

int main(void){
    int N, flg=1, p=0;
    cin >> N;
    string w[110];
    string used[110];
    for(int i=0;i<N;i++) cin >> w[i];
    used[p] = w[0];
    p++;
    for(int i=1;i<N;i++){
        for(int j=0;j<i;j++){
            if(w[i]==used[j]) flg=0;
        }
        if(flg==1){
            used[p] = w[i];
            p++;
        }
        if(w[i][0]!=w[i-1][w[i-1].size()-1]) flg=0;
    }
    if(flg==1) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int d, ans, m, x, q;
int c[30], s[370][30], t[370], lst[30];

int main() {
	int i, j, r, l;
	cin >> d;
	for(i=1; i<=26; i++) cin >> c[i];
	for(i=1; i<=d; i++) for(j=1; j<=26; j++) cin >> s[i][j];
	for(i=1; i<=d; i++) {
		cin >> t[i];
		ans += s[i][t[i]];
		lst[t[i]] = i;
		for(j=1; j<=26; j++) ans -= c[j] * (i-lst[j]);
	}
	cin >> m;
	while(m--) {
		cin >> x >> q;
		ans -= s[x][t[x]];
		ans += s[x][q];
		for(r=x+1; r<=d && t[r]!=t[x]; r++);
		for(l=x-1; l>=1 && t[l]!=t[x]; l--);
		ans -= c[t[x]] * (r-x) * (x-l);
		for(r=x+1; r<=d && t[r]!=q; r++);
		for(l=x-1; l>=1 && t[l]!=q; l--);
		ans += c[q] * (r-x) * (x-l);
		t[x] = q;
		cout << ans << endl;
	}
}

Measured memory_bytes: 3664
import math

def is_prime(x):
    if x == 2:
        return True

    if x % 2 == 0 or x < 2:
        return False

    i = 3
    x_sqrt = math.sqrt(x)
    while i <= x_sqrt:
        if x % i == 0:
            return False
        i += 2

    return True

if __name__ == "__main__":
    n = int(input())
    count = 0
    for i in range(n):
        if is_prime(int(input())):
            count += 1

    print(count)

Measured memory_bytes: 7804
from operator import mul
from functools import reduce
def cmb(n,r):
    r=min(n-r,r)
    if r==0:
        return 1
    over=reduce(mul,range(n,n-r,-1))
    under=reduce(mul,range(1,r+1))
    return over//under

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

data=[0]*(N+1)
for a in A:
    data[a]+=1

num=0
for i in range(N+1):
    if data[i]>=2:
        num+=cmb(data[i],2)
        
for k in range(N):
    if data[A[k]]>=2:
        print(num-data[A[k]]+1)
    else:
        print(num)
        

Measured memory_bytes: 85072
#include <iostream>
using namespace std;
int main(){
  int N;
  cin >> N;
  int A[201];
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  
  int count = 0;
  while(true){
    bool can = false;
    
    for(int i = 0; i < N; i++){
      if(A[i] % 2 != 0){
        can = true;
      }
    }
      
    if(can){
      break;
    }
      
    for(int i = 0; i < N; i++){
      A[i] /= 2;
    }
    count++;
  }
  cout << count << endl;
}
    


Measured memory_bytes: 3668
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class AFrog1 {
        public void solve(int testNumber, inputClass sc, PrintWriter out) {
            int n = sc.nextInt();
            int[] tab = new int[n];
            for (int i = 0; i < n; i++) {
                tab[i] = sc.nextInt();
            }

            int[] dp = new int[n];

            for (int i = 1; i < n; i++) {
                dp[i] = Integer.MAX_VALUE;
            }

            for (int i = 0; i < n - 1; i++) {
                dp[i + 1] = Math.min(dp[i + 1], dp[i] + Math.abs(tab[i] - tab[i + 1]));
                if (i != n - 2) {
                    dp[i + 2] = Math.min(dp[i + 2], dp[i] + Math.abs(tab[i] - tab[i + 2]));
                }
            }
            out.println(dp[n - 1]);
        }

    }

    static class inputClass {
        BufferedReader br;
        StringTokenizer st;

        public inputClass(InputStream in) {

            br = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 32056
n = int(input())
a = list(map(int, input().split()))
ls = [0]*(n+1)
ans = []
for i in reversed(list(range(n))):
    if sum(ls[::i+1][1:]) % 2 != a[i]:
        ls[i+1] = 1
        ans.append(i+1)
print(sum(ls))
if ans: print(' '.join(map(str, ans)))

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

int main() {
  int H,R;
  cin >> H >> R;
   if(R>0){
   if(H+R>0){
  cout<< 1 <<endl;
  } else if(H+R<0) {
    cout<< -1  <<endl;
  }
  if(H+R==0){
   cout<< 0  <<endl;
  } 
 }
  return 0;
  
}


Measured memory_bytes: 3092
//
// Created by Nivras on 2017/5/16.
//

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int MAXN = 110000;

long long weight[MAXN];

bool check(const long long load, const long long carNum, const long long goodNum) {
    int cnt = 0;
    for (int i = 0; i < carNum; i++) {
        int nowWeight = 0;
        while (nowWeight + weight[cnt] <= load) {
            nowWeight += weight[cnt];
            cnt++;
            if (cnt == goodNum) {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    long long int n, k;
    scanf("%lld%lld", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &weight[i]);
    }

    long long left = 0;
    long long right = 10000 * 100000;
    long long mid;
    while (right - left > 1) {
        mid = (left + right) / 2;
        if (check(mid, k, n)) {
            right = mid;
        }
        else {
            left = mid;
        }
    }
    printf("%lld\n", right);

    return 0;
}

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


 int main()
 {
     int long long a, b, c, k;
     cin >> a >>b >>c >>k;
     if(k<=a) cout << k;
     else if (k <= a+b ) cout << a;
     else cout << a - (k-a-b);


 }


Measured memory_bytes: 3588
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
use std::collections::HashMap;
fn main() {
    input!{
        n:usize,
        k:usize,
        an:[usize;n],
    }
    let mut map = HashMap::new();
    for &a in &an {
        *map.entry(a).or_insert(0) += 1;
    }
    let mut sub:Vec<(usize,usize)> = map.into_iter().collect::<Vec<(usize,usize)>>();
    sub.sort_by(|a,b|b.1.cmp(&a.1));
    let ans:usize = sub.iter().skip(k).map(|&(_,v)|v).fold(0,|y,x| y + x);
    println!("{}",ans);
}


Measured memory_bytes: 17172
import java.util.Scanner;

public class Main {

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

	void solve() {
		Scanner sc = new Scanner(System.in);
		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		int c = Integer.parseInt(sc.next());
		sc.close();

		System.out.println(Math.min(b/a, c));
	}
}

Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;

int n, a[200005], b[200005];
const int MAX = 200005;
ll ans;

struct segment_tree {
	int t[2*MAX];
	void build() {
		for(int i = 0; i < n; i++) t[i + n] = a[i];
		for(int i = n-1; i >= 1; i--) t[i] = min(t[i<<1], t[i<<1|1]);
	}
	// [l,r]
	int query(int l, int r) {
		++r;
		int ret = MAX;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1) ret = min(ret, t[l++]);
			if(r & 1) ret = min(ret, t[--r]);
		}
		return ret;
	}
} st;

void dfs(int l, int r) {
	int ret = st.query(l, r), pos = b[ret];
	ans += 1LL * ret * (r-pos+1) * (pos-l+1);
	if (l <= pos-1) dfs(l, pos-1);
	if (pos+1 <= r) dfs(pos+1, r);
	return;
}

int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n;
	FOR(i, n) {
		cin >> a[i];
		b[a[i]] = i;
	}
	st.build();
	dfs(0, n-1);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 9600
#include <iostream>
#include<map>
#include<string>
#include<vector>
#include<map>
#include <algorithm>
using namespace std;
int n,t,x,y;
string ans="Yes";
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>t>>x>>y;
		if (x+y>t || (t-x-y)%2!=0) ans="No";
	}
	cout<<ans<<endl;;
}


Measured memory_bytes: 256
program main
  
  implicit none
  integer :: a, b, c, d
  
  read(*,*) a, b, c, d

  !while( a <= 0 .or. c <= 0 ) 
  do
    c = c - b
    if( c <= 0 ) exit
    a = a - d
    if( a <= 0 ) exit
  end do
  
  if( a <= 0 )then
    print*, "No"
  else
    print*, "Yes"
  end if
end program main


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

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

ll n,cnt,ans,a[ohara],b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k;
ld doua;
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>>n>>x;
    rep(i,n){
        cin>>a[i];
        a[i]=abs(a[i]-x);
    }
    ans=a[0];
    rrep(i,1,n){
        ans=__gcd(ans,a[i]);
    }
    Cout(ans);
    return 0;
}


Measured memory_bytes: 1024
import copy
n=int(input())
a=[0]+list(map(int,input().split()))+[0]
b=[]
ans=0
for i in range(n+1):
    t=abs(a[i]-a[i+1])
    b.append(t)
    ans+=t
for i in range(1,n+1):
    tmp=copy.deepcopy(ans)
    tmp-=b[i-1]
    tmp-=b[i]
    tmp+=abs(a[i-1]-a[i+1])
    print(tmp)

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

string s, t ; int sn , tn ; 
int dp[3001][3001];

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

	sn = s.size(); tn = t.size();
	for(int i = 0 ; i<=sn ; i++)
	{
		for(int j= 0 ; j<=tn ; j++)
		dp[i][j]=0 ; 
	}
	
	for(int i = 1; i<=sn; i++)
	{
		for(int j =1 ; j<=tn ; j++)
		{
			if(s[i-1]==t[j-1])
			dp[i][j]= dp[i-1][j-1]+1; 
			else
			dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}
	}
	int x = sn, y = tn ; 
	string ans = "";
	while(x>0&&y>0)
	{
		if(dp[x][y]==dp[x][y-1])
		y--; 
		else if(dp[x][y]==dp[x-1][y])
		x--; 
		else
		{
			ans = s[x-1]+ ans ; 
			x--; 
			y--; 
		}
	}
	cout<<ans;
	return(0);
}


Measured memory_bytes: 35456
#include <algorithm>
#include <bitset>
#include <cassert>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <sstream>
#include <stdio.h>
#include <string>
#include <vector>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define POW(n) ((n) * (n))
#define ALL(a) (a).begin(), (a).end()
#define dump(v) (cerr << #v << ": " << v << endl)
#define cerr                                                                   \
  if (true)                                                                    \
  cerr

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<unsigned long long> vull;

// ll n = to_T<ll>("114514")
template <class T> T to_T(const string &s) {
  istringstream is(s);
  T res;
  is >> res;
  return res;
}
template <class T> string to_s(const T &a) {
  ostringstream os;
  os << a;
  return os.str();
}

void solve(long long A, long long B) {
  if (A == 1)
    A += 100;
  if (B == 1)
    B += 100;

  string ans = "Draw";
  if (A < B)
    ans = "Bob";
  else if (B < A)
    ans = "Alice";

  cout << ans << endl;
}

int main() {
  ios::sync_with_stdio(false);
  long long B;
  long long A;
  cin >> A;
  cin >> B;
  solve(A, B);
  return 0;
}


Measured memory_bytes: 256
def calc(n, p):
    count = 0
    for i in range(1, n-1):
        if p[i-1] < p[i] and p[i] < p[i+1]:
            count += 1
            continue
        if p[i-1] > p[i] and p[i] > p[i+1]:
            count += 1
            continue
    return count
print(calc(int(input()), [int(a) for a in input().split()]))

Measured memory_bytes: 3064
from collections import defaultdict
import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        return self.size[self.find(x)]

N, K, L = map(int, input().split())
uf1 = UnionFind(N+1)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.unite(p, q)
uf2 = UnionFind(N+1)
cnt = [defaultdict(int) for _ in range(N+1)]
for i in range(1, N+1):
    cnt[i][uf1.find(i)] = 1
for _ in range(L):
    r, s = map(int, input().split())
    if uf2.same(r, s):
        continue
    a = uf2.find(r)
    b = uf2.find(s)
    uf2.unite(r, s)
    c = uf2.find(r)
    if a == c:
        for k, v in cnt[b].items():
            cnt[c][k] += v
    else:
        for k, v in cnt[a].items():
            cnt[c][k] += v
ans = [0] * (N+1)
for i in range(1, N+1):
    ans[i] = cnt[uf2.find(i)][uf1.find(i)]
print(*ans[1:])

Measured memory_bytes: 151184
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<stack>
#include<queue>
#include<string>
#include<deque>
#include<set>
#include<vector>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
int a[100005];

int main()
{
     ll n,m;
     while(~scanf("%lld %lld",&n,&m))
    
    {
    	printf("%lld\n",n*n-m);
	}
     
     return 0;
        
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn=2e5+10;
int pos[maxn];
int a[maxn];
int nx[maxn];
int pe[maxn];
LL ans=0;
template<class T>void read(T &x)
{
	bool f=0;char ch=getchar();x=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	if(f) x=-x;
}
int main()
{
	int n;
	read(n);
	for(int i=1;i<=n;i++)
	{
		read(a[i]);
		pos[a[i]]=i;
	}
	for(int i=0;i<=n+1;i++)
	{
		pe[i]=i-1;
		nx[i]=i+1;
	}
	for(int i=n;i>=1;i--)
	{
		ans+=1ll*i*(nx[pos[i]]-pos[i])*(pos[i]-pe[pos[i]]);
		pe[nx[pos[i]]]=pe[pos[i]];
		nx[pe[pos[i]]]=nx[pos[i]];
	}
	printf("%lld\n",ans);
	return 0;
}

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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

int main() {
	string s;
	cin >>s;
	if (s.size()%2) {
		cout <<"No\n";
		return 0;
	}
	for (int i=0 ; i<s.size() ; i++) {
		if (i%2==0 and s[i]!='h') {
			cout <<"No\n";
			return 0;
		}
		if (i%2 and s[i]!='i') {
			cout <<"No\n";
			return 0;
		}
	}
	cout <<"Yes\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
//a=0x61=97
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
typedef long double  ld;
typedef string str;
typedef pair<int,int> pairii;
typedef vector<int> veci;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(2)
int main() {
  int n,d,x;
  cin>>n>>d>>x;
  int p[n];
  rep(i,n){
    cin>>p[i];
    x+=(d/p[i]);
    x+=(bool)(d%p[i]);
  }
  cout<<x<<endl;
}

Measured memory_bytes: 256
/* ****TCIITB**** */

#include<bits/stdc++.h>
#define io          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;

#define N  200007
ll parent[N];
ll sz[N];
ll getparent(ll child)
{
  if(child==parent[child])
  {
    return child;
  }
  else
  {
    ll tmp=getparent(parent[child]);
    
    parent[child]=tmp;
    return tmp;
  }
}
void merge(ll x,ll y)
{
	ll p1=getparent(x);
	ll p2=getparent(y);
	if(p1==p2)
		return ;
	parent[p1]=p2;
	sz[p2]+=sz[p1];
	sz[p1]=0;
}
int main()
{
	
	io
	
	rep(i,1,N)
	{
		parent[i]=i;
		sz[i]=1;
	}
	ll n,m;
	cin>>n>>m;
	rep(i,0,m)
	{
		ll x,y;
		cin>>x>>y;
		merge(x,y);
	}
	ll mx=0;
	rep(i,1,n+1)
	{
		mx=max(mx,sz[getparent(i)]);
	}
	cout<<mx;

}

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

int main(){
    int K,S,X,Y,Z;
    int res=0;
    cin >> K >> S;
    for (X=0; X<=K; ++X){
        for (Y=0; Y<=K; ++Y){
            Z = S-X-Y;
            if (0<=Z && Z<=K) ++res;
        }
    }
    cout << res << endl;
}

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

int main(){
  string s;
  int n;
  cin >> s >> n;

  stack<int> t;
  t.push(s[0]-'0');
  for(int i=1;i<s.size();i+=2){
    int tmp = s[i+1]-'0';
    if(s[i] == '*')t.top() *= tmp;
    else t.push(tmp);
  }
  int M = 0;
  while(t.size()){
    M += t.top(), t.pop();
  }

  int L = s[0]-'0';
  for(int i=1;i<s.size();i+=2){
    int tmp = s[i+1]-'0';
    if(s[i] == '*')L *= tmp;
    else L += tmp;
  }

  if(M == n && L == n)cout << "U";
  else if(M == n)cout << "M";
  else if(L == n)cout << "L";
  else cout << "I";
  cout << endl;
}

Measured memory_bytes: 1212
import java.io.*;
import java.util.*;
import java.math.BigInteger;
public class Main {

static long[] list=new long[87];

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

  // String nyuA=sc.nextLine();
//  String nyuB=sc.nextLine(); 
 

   String[] s=sc.nextLine().split(" ");
 //    String[] t=sc.nextLine().split("");

   String nyuA=sc.nextLine();


//int N=Integer.parseInt(nyuA);
int A=Integer.parseInt(s[0]);
int B=Integer.parseInt(s[1]);
int C=Integer.parseInt(s[2]);

int K=Integer.parseInt(nyuA);

int[] num={A,B,C};
Arrays.sort(num);


for(int i=0;i<K;i++){
num[2]*=2;
}
int res=0;
for(int i=0;i<num.length;i++){
res+=num[i];
}

System.out.println(res);



}

}



Measured memory_bytes: 23764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<string> v;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        v.push_back(s);
    }

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

    for(int i=0;i<n;i++){
        cout << v[i];
    }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
  bool check=false;
  int a,b,c;
  int i=0;
  
  cin>>a>>b;
  c=b;
  while(c>=0){
      if(c%2==0 && i+c/2==a){
          check = true;
      } 
      i++;
      c=b-4*i;      
  }
  
  if(check==true){cout<<"Yes\n";}else{cout<<"No\n";}
  return 0;
}

Measured memory_bytes: 3436
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <queue>
#include <stack>
#include <utility>
#include <tuple>
#include <string>
#include <functional>
#include <map>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;

using ii = pair < int , int >;
using ti = tuple < int ,int ,int >;
using lint = long long;
using ll = pair < lint , lint >;

int main(){
	//freopen("in.txt","r",stdin);
	int s[3][3];
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			scanf("%d",&s[i][j]);
		}
	}
	int d[3][2];
	for(int i=1;i<3;i++){
		for(int j=0;j<3;j++){
			d[i][j] = s[i][j] - s[i-1][j];
		}
		if(d[i][0]==d[i][1] && d[i][1]==d[i][2]){

		}
		else{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
}


Measured memory_bytes: 256
n = int(input())
ans = 0
cnt = dict()
for i in range(n):
    s = input()
    try:
        cnt[s] += 1
    except:
        cnt[s] = 1
m = int(input())
for i in range(m):
    s = input()
    try:
        cnt[s] -= 1
    except:
        cnt[s] = -1

for i in cnt.values():
    ans = max(ans, i)
print(ans)


Measured memory_bytes: 3060
s = input()
n = len(s)
MOD = 2019
mods = [0] * MOD
mods[0] = 1

prev = 0
for i in range(n-1, -1, -1):
    mod = int(s[i]) * pow(10, n-i, MOD) % MOD
    mod = (mod + prev) % MOD
    mods[mod] += 1
    prev = mod

ans = 0
for i in range(MOD):
    ans += mods[i] * (mods[i] - 1) // 2
print(ans)


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

vector<int> color(100000, 0);
map<pair<int, int>, int> w;

void dfs(const vector<vector<int>> &g, int v, int p){
	for(auto nv: g[v]){
		if(nv == p) continue;
		
		if(w.at(make_pair(v, nv)) % 2 == 1) color[nv] = !color[v];
		else color[nv] = color[v];
		dfs(g, nv, v);
	}
}



int main() {
	
	int n;
	cin >> n;
	
	vector<vector<int>> g(n);
	rep(i, n-1){
		int u, v, l;
		cin >> u >> v >> l;
		u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
		w[make_pair(u, v)] = l;
		w[make_pair(v, u)] = l;
	}
	color[0] = 0;
	dfs(g, 0, -1);
	
	rep(i, n){
		cout << color[i] << endl;
	}
	
	return 0;
}

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

int main() {
  int n,k;
  cin>>n>>k;
  vector<long> h(n);
  for (size_t i = 0; i < n; i++) {
    cin>>h[i];
  }
  sort(h.begin(),h.end());
  long sa = 1000000000;
  for (size_t i = 0; i < n-k+1; i++) {
    sa = min(sa,h[i+k-1]-h[i]);
  }
  cout<<sa;
}

Measured memory_bytes: 1024
import sys
input = sys.stdin.buffer.readline


def calc(s_list):
    cnt = 0
    while len(s_list) > 1:
        cnt += 1
        s1 = s_list.pop()
        s2 = s_list.pop()
        new = str(s1 + s2)
        if len(new) == 1:
            s_list.append(int(new))
        else:
            s_list.append(int(new[0]))
            s_list.append(int(new[1]))

    return cnt


M = int(input())
D = []
C = []
for _ in range(M):
    d, c = map(int, input().split())
    D.append(d)
    C.append(c)

ten_num = [0] * 10
for i in range(10):
    ten_num[i] = calc([i] * 10)

ans = 0
s_list = []
for i in range(M):
    d, c = D[i], C[i]
    while c > 10:
        div, mod = divmod(c, 10)
        ans += ten_num[d] * div
        c = div + mod
    s_list.extend([d] * c)

ans += calc(s_list)
print(ans)


Measured memory_bytes: 123292
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
int main()
{
	int  n;
	scanf("%d", &n);
	n = n % 1000;
	if (n == 0)
	{
		printf("0");
	}
	else
	{
		printf("%d", 1000 - n);
	}
	return 0;
}


Measured memory_bytes: 1732
N,M=input().split()
N =int(N)
M =int(M)
a= list(map(int,input().split()))
dict={}
ans = 0
p = 0
dict[0] = 1
for i in range(N):
    p = (p+a[i])%M
    if p not in dict:
        dict[p] = 1
    else:
        ans +=dict[p]
        dict[p] += 1
print(ans)


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"
*/

int main()
{
    int N; cin >> N;
    int A[N];
    rep(i, N) A[i] = 0;
    rep(i, N-1){
        int Ai; cin >> Ai;
        A[Ai-1]++;
    }
    rep(i, N) cout << A[i] << endl;
}

Measured memory_bytes: 4408
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<set>
using namespace std;
typedef vector<int> vi;

int dance(string s,int foot)
{
  int pannelonfoot[]={0,2};
  int cnt=0;
  for(int i=0;i<s.size();i++)
  {
    int pannel=((int)(s[i]-'0')-1)%3;
    if(foot==0)
    {
      if(pannelonfoot[1]<pannel)
      {
        cnt++;
        pannelonfoot[1]=pannel;
      }
      else
      {
        pannelonfoot[0]=pannel;
        foot=(foot+1)%2;
      }
    }
    else
    {
      if(pannel<pannelonfoot[0])
      {
        cnt++;
        pannelonfoot[0]=pannel;
      }
      else
      {
        pannelonfoot[1]=pannel;
        foot=(foot+1)%2;
      }
    }
  }
  return cnt;
}

int main()
{
  while(1)
  {
    string s;
    cin >> s;
    if(s=="#") break;
    cout << min(dance(s,0),dance(s,1)) << endl;
  }
    return 0;
}



Measured memory_bytes: 3128
#include <bits/stdc++.h>
#include <cassert>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ok() puts(ok?"Yes":"No");
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using gt = greater<int>;
using minq = priority_queue<int, vector<int>, gt>;
using P = pair<ll,ll>;
const ll LINF = 1e18L + 1;
const int INF = 1e9 + 1;
//clang++ -std=c++11 -stdlib=libc++ 

int main() {
  ll N,C; cin >> N >> C;
  vector<vll> line(C, vll(100005));
  rep(i,N) {
    ll s,t,c; cin >> s >> t >> c;
    c--;
    // if (line[c][s-1]!=-1) 
    line[c][s-1]++;
    line[c][t]--;
  }
  rep(i, 100003) {
    rep(c, C) {
      line[c][i+1] += line[c][i];
    }
  }
  ll ans = 0;
  // vll sum(100005);
  rep(i, 100003) {
    ll num = 0;
    rep(c, C) {
      if (line[c][i] == 2) num--;
      num += line[c][i];
    }
    // sum[i+1] += sum[i] + num;
    chmax(ans, num);
  }
  // rep(i, 100003) chmax(ans, sum[i]);
  cout << ans << endl;
  return 0;

}

Measured memory_bytes: 27512
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int a[3][3];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin >> a[i][j];
    }
  }

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

  bool bingo[3][3];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      bingo[i][j] = false;
    }
  }

  for(int i=0;i<n;i++){
    for(int j=0;j<3;j++){
      for(int k=0;k<3;k++){
        if(b[i] == a[j][k]){
          bingo[j][k] = true;
        }
      }
    }
  }

  bool ok = false;
  for(int i=0;i<3;i++){
    if(bingo[i][0] == true && bingo[i][1] == true && bingo[i][2] == true){
      ok = true;
    }
    else if(bingo[0][i] == true && bingo[1][i] == true && bingo[2][i] == true){
      ok = true;
    }
  }

  if(bingo[0][0] == true && bingo[1][1] == true && bingo[2][2] == true){
    ok = true;
  }
  if(bingo[0][2] == true && bingo[1][1] == true && bingo[2][0] == true){
    ok = true;
  }

  if(ok) cout <<"Yes"<<endl;
  else cout << "No"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define MA 200000
#define INF 114514810
using namespace std;
long long n, m;
long long d[MA], t[MA];
int main() {
  cin >> n;
  rep(i, n) {
    scanf("%d", &d[i]);
  }
  cin >> m;
  rep(i, m) {
    scanf("%d", &t[i]);
  }
  sort(d, d + n);
  sort(t, t + m);
  bool fla;
  long long k = 0;
  for (int i = 0; i < m; i++) {
    fla = false;
    for (int j = k; j < n; j++){
      if (t[i] == d[j]){
        k = j + 1;
        fla = true;
        break;
      }
    }
    if (!fla) break;
  }

  printf("%s\n", ((fla) ? "YES" : "NO"));
  return 0;
}


Measured memory_bytes: 3328
#include <stdio.h>

int main(void){
  int a,b;
  int i,j;

  while( 1 ){
    if( scanf("%d %d ",&a,&b)!=2 )
      break;

    a += b;
    i=1;
    j=0;
    while( 1 ){
      if( a<i )break;
      i*=10;
      j++;
    }
    printf("%d\n",j);
  }

  return 0;
}

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

int main(){
	int a, p;
	cin >> a >> p;
    p += a*3;
    int ans = p/2;
	cout << ans << endl;
}

Measured memory_bytes: 256
[n,k]=[int(x) for x in input().split()]
P=[int(x) for x in input().split()]

E=[0]*n #期待値=E[i]
S=[0]*(n+1) #累積和=S[i+1]=E[0]+E[1]+...+E[i](S[0]=0)

for i in range(n):
	E[i]=(1+P[i])/2
	S[i+1]=S[i]+E[i]
max=0
for i in range(k,n+1):
	if S[i]-S[i-k] > max:
		max=S[i]-S[i-k]
print(max)

Measured memory_bytes: 25188
#include <bits/stdc++.h>
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x - 1; i < y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define eps 1e-9
#define all(x) (x).begin(), (x).end()
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int N = 5005;
const int K = 5005;
int n, k;
int a[N];
int dp1[N][N], dp2[N][N];
 
int main() 
{
	n = read();
	k = read();
	rep(i, 1, n) a[i] = read();
	dp1[0][0] = 1;
	dp2[0][0] = 1;

	int j = n - 1;
	rep(i, 1, n)
	{
		rep(s, 1, K)
		{
			if (s + a[i] < K) dp1[i + 1][s + a[i]] |= dp1[i][s];
			dp1[i + 1][s] |= dp1[i][s];
			if (s + a[j] < K) dp2[i + 1][s + a[j]] |= dp2[i][s];
			dp2[i + 1][s] |= dp2[i][s];
		}
	 	j --;
	}
	rep(i, 1, n)
		rep(j, 2, K) 
			dp2[i][j] += dp2[i][j - 1];
	int ans = 0;
	rep(i, 1, n)
		rep(j, 1, K) 
		{
			if (!dp1[i][j]) continue;
			int x = k - a[i] - j;
			int y = k - 1 - j;
			if (y < 0) break;
			if (dp2[n - i - 1][y] - (x - 1 >= 0 ? dp2[n - i - 1][x - 1] : 0) == 0) continue;
			ans ++;
			break;
		}
	printf("%d\n", n - ans);
	return 0;
}


Measured memory_bytes: 195840
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())
#define int long long
#define INF 1000000000000000
using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;
typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);

int fastpow(int x, int n, int m){
    int a = 1;
    IREP(i, 64){
        a = (a * a) % m;
        if(((n >> i) & 1) == 1) a = (a * x) % m;
    }
    return a;
}

class Combination
{
public:

    vec fact, invfact;
    int MAX_N, mod;

    Combination(int MAX_N, int mod): MAX_N(MAX_N), mod(mod) {
        fact = vec(MAX_N + 1);
        invfact = vec(MAX_N + 1);
        fact[0] = 1;
        FOR(i, 1, MAX_N + 1){
            fact[i] = (fact[i - 1] * i) % mod;
        }
        invfact[MAX_N] = fastpow(fact[MAX_N], mod - 2, mod);
        IREP(i, MAX_N){
            invfact[i] = (invfact[i + 1] * (i + 1)) % mod;
        }
    }

    int comb(int n, int r){
        if(r > n || r < 0 || n < 0) return 0;
        int a = fact[n];
        a = (a * invfact[r]) % mod;
        a = (a * invfact[n - r]) % mod;
        return a;
    }
};

signed main(){

    int H, W, A, B; cin >> H >> W >> A >> B;
    int mod = 1000000007;

    Combination C(H + W, mod);
    
    int ans = C.comb((H - 1) + (W - 1), W - 1);

    REP(i, B){
        int tmp = C.comb((H - A - 1) + i, i) * C.comb((A - 1) + (W - i - 1), W - i - 1);
        tmp %= mod;
        ans = (ans + (mod - tmp)) % mod;
    }

    cout << ans;
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

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

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

    sort(s.begin(), s.end());
    sort(t.rbegin(), t.rend());
 
    if(s < t){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        int a;
        cin>>a;
        if(a>=k)
            cnt++;
    }
    cout<<cnt<<endl;
}


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

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

	int N, T, A;
	cin >> N >> T >> A;

	vector<int> H( N );
	for( auto& v: H ) { cin >> v; }

	double tmin = DBL_MAX;
	int result = 0;

	for( int i = 0; i < N; ++i ) {
		double x = abs( A - (T - H[i] * 0.006) );
		if( x < tmin ) {
			tmin = x;
			result = i+1;
		}
	}

	cout << result << endl;
	return 0;
}


Measured memory_bytes: 256
h,w = gets.strip.split.map(&:to_i)
data = []
ay = Array.new(w+2,".")
data << ay.join("").to_s
h.times do
  ax = gets.strip.to_s
  data << "."+ax+"."
end
data << ay.join("").to_s

outcount = 0
#とにかく離れ小島が一個でもあればダメ
for i in 1..h
  for j in 1..w
    if data[i][j]=="#"
      if data[i-1][j]=="." && data[i+1][j]=="." && data[i][j-1]=="." && data[i][j+1]=="."
        outcount += 1
      end
    end
  end
end
if outcount != 0
  puts "No"
else
  puts "Yes"
end

Measured memory_bytes: 14204