akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
#ARC100 C

import sys
import math
import bisect
import time
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = [a[i] - (i+1) for i in range(n)]
b.sort()
if n % 2:
    c = b[n//2]
else:
    c = (b[n//2]+b[n//2-1])//2
ans = 0
for i in range(n):
    ans += abs(a[i] -(c + i+1))
print(ans)


Measured memory_bytes: 91984
#include <cstdio>
#include <unistd.h>
#include <algorithm>
#include <vector>
using namespace std;

using i64 = long long;

#define REP(i, n) for (int i = 0, i##_len = n; i < i##_len; ++i)
#define RREP(i, n) for (int i = n; i-- > 0;)

const int is = 1 << 17;
char ib[is], *ip = ib + is, it;
inline char getc() {
//	if (ip == ib + is) { fread_unlocked(ib, 1, is, stdin); ip = ib; }
	if (ip == ib + is) { read(STDIN_FILENO, ib, is); ip = ib; }
	return *ip++;
}
inline i64 scan() {
	i64 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;
}

const int os = 1 << 17;
char ob[os], *op = ob, ot;
inline void putc(const char c) {
	*op++ = c;
	if (op == ob + os) { fwrite_unlocked(ob, 1, os, stdout); op = ob; }
}
// x shoud be greater than or equal to zero
inline void write(i64 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]);
	}
}

signed main() {
  i64 N = scan();
  i64 M = scan();
  vector<i64> A(N);
  REP(i, N) A[i] = scan();
  sort(A.begin(), A.end());
  vector<i64> S(N + 1);
  REP(i, N) S[i + 1] = S[i] + A[i];
  i64 h_ng = 0;
  i64 h_ok = A[N - 1] * 2 + 1;
  i64 h = h_ok;
  while (h_ok > h_ng + 1) {
    h = h_ng + h_ok >> 1;
    i64 q = 0;
    i64 gt = 0;
    RREP(i, N) {
      while (gt < N && !(A[i] + A[gt] > h)) gt++;
      q += N - gt;
    }
    if (q <= M) {
      h_ok = h;
    } else {
      h_ng = h;
    }
  }
  h = h_ok;
  i64 s = 0;
  i64 q = 0;
  i64 gt = 0;
  RREP(i, N) {
    while (gt < N && !(A[i] + A[gt] > h)) gt++;
    q += N - gt;
    s += S[N] - S[gt] + A[i] * (N - gt);
  }
  write(s + (M - q) * h);
  fwrite_unlocked(ob, 1, op - ob, stdout);
}


Measured memory_bytes: 1920
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int main(){
    int N, K;
    int d;
    int cnt;
    int A[100];
    int i, j;

    for(i = 0; i < 100; i++){
        A[i] = 0;
    }

    scanf("%d %d", &N,&K);

    for(i = 0; i < K; i++){
        scanf("%d", &d);
        for(j = 0; j < d; j++){
            scanf("%d", &cnt);
            A[cnt-1]++;
        }
    }

    cnt = 0;
    for(i = 0; i < N; i++){
        if(A[i] == 0){
            cnt++;
        }
    }

    printf("%d\n",cnt);

    return 0;
}


Measured memory_bytes: 1688
using System;

namespace ABC105_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = long.Parse(Console.ReadLine());
            if (N == 0)
            {
                Console.WriteLine(0);
                return;
            }

            string r = "";
            while (N != 0)
            {
                if (N % 2 == 0)
                {
                    r = "0" + r;
                }
                else
                {
                    N--;
                    r = "1" + r;
                }
                N /= -2;
            }
            Console.WriteLine(r);
        }
    }
}


Measured memory_bytes: 11220
#include <stdio.h>
#define REP(i, n) for(i = 0; i < n; ++i)
#define FOR(i, a, b) for(i = a; i < b; ++i)

void yes_or_no(char boolean){
    if(boolean){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
}

int main(){
    int N;
    scanf("%d\n", &N);
    printf("%d\n", N * (N + 1) / 2);
    return 0;
}

Measured memory_bytes: 128
using System;
using System.IO;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;
using Debug = System.Diagnostics.Debug;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;


static class P
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();
        int current = s.Count(x => x == '.');
        int res = current;
        for (int i = 0; i < n; i++)
        {
            current += s[i] == '#' ? 1 : -1;
            res = Min(res, current);
        }
        Console.WriteLine(res);
    }
}


Measured memory_bytes: 11744
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main()
{
  char a;
  cin >> a;
  if (a <= 'Z')
    cout << 'A' << endl;
  else
    cout << 'a' << endl;

  return 0;
}


Measured memory_bytes: 3624
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int N = getint();
	int dp[2], h[2] = {};
	dp[0] = 1e9;
	dp[1] = 1e9;

	int H = getint();
	int kotae = 0;
	rep(i, N - 1) {
		h[i & 1] = H;
		dp[i & 1] = kotae;
		H = getint();
		kotae = 1e9;
		chmin(kotae, dp[0] + abs(h[0] - H));
		chmin(kotae, dp[1] + abs(h[1] - H));
	}

	printf("%d", kotae);

	Would you please return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int n;
    scanf("%d", &n);
    char str[n + 1];
    scanf("%s", str);
    int sum = 0;
    for (int i = 0; i < n - 2; ++i)
    {
        if (str[i] == 'A' && str[i + 1] == 'B' && str[i + 2] == 'C')
            sum++;
    }
    printf("%d\n", sum);
    return 0;
}

Measured memory_bytes: 128
n = int(input())
list1 = [list(map(int,input().split(" "))) for i in range(n)]
dp = [[0,0,0] for _ in range(n)]
dp[0] = list1[0]
for i in range(1,n):
    dp[i][0] = list1[i][0] + max(dp[i-1][1],dp[i-1][2])
    dp[i][1] = list1[i][1] + max(dp[i-1][2],dp[i-1][0])
    dp[i][2] = list1[i][2] + max(dp[i-1][0],dp[i-1][1])
print(max(dp[-1]))

Measured memory_bytes: 47280
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define ll long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,k,t;

pii p[maxn];

int main()
{
    scanf("%d",&n);
    for(int i = 0,x,l; i < n; i++) 
    {
        scanf("%d%d",&x,&l);
        p[i].first = x+l;
        p[i].second = x-l;
    }
    sort(p,p+n);
    int ans = 0;
    int cur = -inf;
    for(int i = 0; i < n; i++) 
    {
        if(cur <= p[i].second)
        {
            ans++;
            cur = p[i].first;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, n1, n2, n4, n5, ans = 0;
  cin >> A >> B;
  for(int i = A; i <= B; i++){
    n5 = i / 10000;
    n4 = (i % 10000) / 1000;
    n2 = (i % 100) / 10;
    n1 = i % 10;
    if ((n5 == n1) && (n4 == n2)) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
long i;
cin>>i;
if(i==0){
cin>>i;
if(i==0){
cin>>i;
if(i==0)cout<<"Close"<<endl;
else cout<<"Open"<<endl;
}else{
cin>>i;
cout<<"Close"<<endl;
}
}else{
cin>>i;
if(i==0)cout<<"Close"<<endl;
else cout<<"Open"<<endl;
cin>>i;
}
return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  char a, b;
  cin >> a >> b;
  if (a == b)
    cout << "=" << endl;
  else if(a < b) cout << "<" << endl;
  else cout << ">" << endl;
}

Measured memory_bytes: 3580
n,m=map(int,input().split())
a=set()
for i in range(m):
  a.add(int(input()))
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if 1 in a:
  dp[1]=0
else:
  dp[1]=1
if n==1:
  print(dp[1])
  exit()
if 2 in a:
  dp[2]=0
else:
  dp[2]=dp[1]+1
for i in range(3,n+1):
  if i in a:
    dp[i]=0
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[n])


Measured memory_bytes: 11884
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
random_device rnd;
mt19937 mt(rnd());

const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1e9 + 7;
int main()
{
    int n, m;
    cin >> n >> m;
    VVI v(n, VI(m));
    rep(i, n) rep(j, m)
    {
        cin >> v[i][j];
        v[i][j]--;
    }
    VI p(n, 0);
    int ans = IINF;
    map<int, bool> used;
    rep(j, m)
    {
        map<int, int> mp;
        rep(i, n)
        {
            mp[v[i][p[i]]]++;
        }
        int delid = -1;
        int delnum = 0;
        rep(i, m)
        {
            if (mp[i] > delnum)
            {
                delnum = mp[i];
                delid = i;
            }
        }
        chmin(ans, delnum);
        used[delid] = true;
        rep(i, n)
        {
            while (used[v[i][p[i]]])
                p[i]++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
/**
 *      purpose : ABC 114 D
 *      author  : kyomukyomupurin
 *      created : 2018-12-04 14:50:31
**/

#include <bits/stdc++.h>
using namespace std;
typedef int64_t int64;
typedef pair<int, int> pii;
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define fi first
#define se second
#define print(x) cout << (x) << '\n'

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(__null);
    
    int n; cin >> n;
    if (n == 1){
        print(0); return 0;
    }
    map<int, int> fact;

    for (int i = 2; i <= n; ++i){
        int t = i;
        for (int j = 2; j * j <= t; ++j){
            if (t % j != 0) continue;
            while (t % j == 0){
                t /= j;
                ++fact[j];
            }
        }
        if (i != 1) ++fact[t];
    }

    int cnt2 = 0, cnt4 = 0, cnt14 = 0, cnt24 = 0, cnt74 = 0;
    for (int i = 2; i <= n; ++i){
        if (fact[i] >= 2) ++cnt2;
        if (fact[i] >= 4) ++cnt4;
        if (fact[i] >= 14) ++cnt14;
        if (fact[i] >= 24) ++cnt24;
        if (fact[i] >= 74) ++cnt74;
    }

    print(cnt74 + cnt24 * (cnt2 - 1) + cnt14 * (cnt4 - 1) + (cnt4 * (cnt4 - 1)) / 2 * (cnt2 - 2));
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int count=0;
    string s,t;
    cin>>s>>t;
    for(int i=0;i<3;i++)
    {
        if(s[i]==t[i])
            count++;
    }
    cout<<count<<endl;
    return 0;
}


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



Measured memory_bytes: 3100
#include <stdio.h>

int main()
{
	int a, b, c, d,e,f;
	int x = 0, y = 0;
	int z, z_;
	int ans_a = 0, ans_b = 0, ans_c = 0, ans_d = 0;
	double m,n,max = 0;
	scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f);

	m = 1.0 * e / 100;
	for (int i = 0; i <= 30; i++)
	{
		int ii = a * 100 * i;
		if (f < ii) break;
		for (int j = 0; j <= 30; j++)
		{
			int jj = b * 100 * j;
			if (f < jj + ii) break;
			for (int k = 0; k < 5000; k++)
			{
				int kk = c * k;
				if (f < ii + jj + kk) break;
				for (int l = 0; l < 5000; l++)
				{
					int ll = d * l;
					if (f < ii + jj + kk + ll) break;
					x = a*i * 100 + b*j * 100;
					y = c*k + d*l;
					if (f >= x + y && x != 0)
					{
						n = 1.0 * y / x;
						if (m >= n)
						{
							if(max <= n)
							{
								max = n;
								z = ii + jj;
								z_ = kk + ll;
							}
						}
					}
				}
			}
		}
	}
	//if (z == 0)
	//{
	//	printf("%d %d", 100 * a * 1, 0);
	//}
	//else
	//{
		printf("%d %d", z + z_, z_);
	//}
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
int main (void)
{
    int a, h, m, s;
    scanf("%d", &a);
    h = a / 3600;
    a = a % 3600;
    m = a / 60;
    s = a % 60;
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(j,n) for(int j = 0; j < (n); ++j)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define drep2(j,n) for(int j = (n)-1; j >= 0; --j)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define srep2(j,s,t) for (int j = s; j < t; ++j)
#define srep3(k,s,t) for (int k = s; j < t; ++k)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  string O,E;
  cin >> O >> E;
  string ans = "";
  rep(i,sz(E)) {
    ans = ans + O[i];
    ans = ans + E[i];
  }
  if(sz(O) > sz(E)) {
    ans = ans + O[sz(O)-1];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <functional>
#include <algorithm>

int N, M;

int main(int argc, char const *argv[]) {
  scanf("%d %d\n", &N, &M);
  std::vector<int> divs;
  for (int i = 2; i * i <= M; i++) {
    if(M%i == 0){
      divs.push_back(i);
      divs.push_back(M/i);
    }
  }
  divs.push_back(1);
  divs.push_back(M);
  std::sort(divs.begin(), divs.end(), std::greater<int>());

  for (auto div : divs) {
    if(M / div >= N){
      printf("%d\n", div);
      return 0;
    }
  }
  printf("1\n");
  return 0;
}


Measured memory_bytes: 256
uses math;
var
	N,A,ans,p,now,tmp:int64;
	j,k:Longint;
begin
	read(N,A);
	ans:=N;
	for k:=1 to 39 do begin
		p:=floor(power(N,1/(k+1)));
		if p=1 then break;
		now:=1;
		for j:=1 to k do now:=now*p;
		for j:=0 to k do begin
			tmp:=A*k+p*k+j+(N+now-1)div now;
			if ans>tmp then ans:=tmp;
			now:=now div p*(p+1);
			if now>N then break;
		end;
	end;
	writeln(ans);
end.

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

#define debug(x) cout << #x << " = " << x << endl
#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

const int MAX = 100 + 5;
char mat[MAX][MAX];

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

	int a, b;
	cin >> a >> b;

	memset(mat, '#', sizeof mat);
	fori(i, 51, 100 + 1) {
		fori(j, 1, 100 + 1) {
			mat[i][j] = '.';
		}
	}

	int used_a = 1, used_b = 1;

	for(int i = 1; used_a < a && i <= 50; i += 2) {
		for(int j = 1; used_a < a && j <= 100; j += 2) {
			mat[i][j] = '.';
			used_a++;
		}
	}

	for(int i = 100; used_b < b && i >= 51; i -= 2) {
		for(int j = 1; used_b < b && j <= 100; j += 2) {
			mat[i][j] = '#';
			used_b++;
		}
	}

	cout << 100 << " " << 100 << '\n';
	fori(i, 1, 100 + 1) {
		fori(j, 1, 100 + 1) {
			cout << mat[i][j];
		}
		cout << '\n';
	}

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define N 20
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,a[N];
map<pair<int,int>,ll> mp[N][N];
ll dfs(int l,int r,int x,int y){
	if(l+1>=r)return 0;
	if(mp[l][r].count({x,y}))return mp[l][r][make_pair(x,y)];
	ll tot=inf;
	for(int i=l+1;i<r;++i){
		tot=min(tot,1LL*(x+y)*a[i]+dfs(l,i,x,x+y)+dfs(i,r,x+y,y));
	}
	return mp[l][r][make_pair(x,y)]=tot;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	printf("%lld\n",dfs(1,n,1,1)+a[1]+a[n]);
	return 0;
}




Measured memory_bytes: 20076
import Control.Applicative
import Data.Array.Unboxed
import Data.Maybe
import Data.List
import Data.Int

main = do
  [n,l] <- map read . words <$> getLine :: IO [Int64]
  as <- listArray (1,n) . map read . words <$> getLine :: IO (UArray Int64 Int64)

  let ans = find (\i -> as!i + as!(i+1) >= l) [1..n-1]

  case ans of
    Nothing -> putStrLn "Impossible"
    Just x -> do
      putStrLn "Possible"
      mapM_ print $ [1..x-1] ++ (reverse [x..n-1])


Measured memory_bytes: 36732
#include <bits/stdc++.h>
using namespace std;
#define rep(i, c) for (int i = 0; i < (int)c; i++)
int main()
{
	int n;
	scanf("%d", &n);
	vector<int> s(n);
	int sum = 0;
	rep(i, n) {
		scanf("%d", &s[i]);
		sum += s[i];
	}
	if(sum % 10 == 0) {
		sort(s.begin(), s.end());
		rep(i, n) {
			if (s[i] % 10) { //s[i]が10の倍数でなければ
				sum -= s[i];
				break;
			}
		}
	}
	if(sum % 10 == 0) sum = 0;
	printf("%d\n", sum);
	return 0;
}

Measured memory_bytes: 3768
Main(function(input) {
	input = input.trim().split('\n');
	input.shift();
	input.forEach(function(line) {
		var tmp = line.split(' ');
		var c = +tmp[0];
		var a = +tmp[1];
		var n = +tmp[2];
		var ans = 0;
		var min;

		/**
		 * CAN pattern
		 */
		min = Math.min(c, a, n);
		c -= min;
		a -= min;
		n -= min;
		ans += min;

		/**
		 * CCA pattern
		 */
		min = Math.min(Math.floor(c / 2), a);
		c -= min * 2;
		a -= min;
		ans += min;

		/**
		 * CCC pattern
		 */
		ans += Math.floor(c / 3);

		console.log(ans);
	});
});

function Main(main) {
	var input = '';

	process.stdin.resume();
	process.stdin.setEncoding('utf8');
	process.stdin.on('data', function(chunk) {
		input += chunk;
	});
	process.stdin.on('end', function() {
		main(input);
	});
};

Measured memory_bytes: 16456
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	int LEN = 0;
	
	void doIt() {
		 int n = sc.nextInt();
		 int x[] = new int[n];
		 int y[] = new int[n];
		 for(int i = 0; i < n; i++) {
			 x[i] = sc.nextInt();
			 y[i] = sc.nextInt();
		 }
		 double sum = 0;
		 for(int i = 0; i < n; i++) {
			 for(int j = 0; j < n; j++) {
				 sum += dis(x[i], x[j], y[i], y[j]);
			 }
		 }
		 System.out.println(sum / n);
		 
	}
	
	double dis(int x1, int x2, int y1, int y2) {
		return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
	}
	
	
	public static void main(String[] args) {
		new Main().doIt();
	}
}


Measured memory_bytes: 23120
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int main(){
    int r, d, xi;
    cin >> r >> d >> xi;
    for(int i = 0; i < 10; i++){
        int xi2 = r * xi - d;
        cout << xi2 << endl;
        xi = xi2;
    }
    return 0;
}


Measured memory_bytes: 256
x1, y1, x2, y2 = map(int, input().split())

xd = x2 - x1
yd = y2 - y1
x3 = x2 - yd
y3 = y2 + xd
x4 = x3 - xd
y4 = y3 - yd

print(x3, y3, x4, y4)


Measured memory_bytes: 2940
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        long ans = 0;
        long w = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'W') {
                ans += i - w;
                w += 1;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 26496
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define true 1
#define false 0
int solve(int,int);
int A[20];
int n;
int main(){
  int q,key;
  int i,j,sol;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    j=0;
    sol=solve(j,key);
    if(sol==true)printf("yes\n");
    if(sol==false)printf("no\n");
  }
  return 0;
}
int solve(int i,int key){
  int res;
  if(key==0)return true;
  if(i>=n)return false;
  res = solve(i + 1, key) || solve(i + 1, key - A[i]);
  return res;
}



Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

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

  if(a>k){
    a-=k;
  }else{
    k-=a;
    a=0;
    if(b>k){
      b-=k;
    }else{
      b=0;
    }
  }

  cout<<a<<" "<<b<<endl;

  return 0;
}

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

int main() {
  char S , T ;
  int y , m  , d ; 
  cin >> y >> S >> m >> T >> d ; 
   
  
  if(  m > 4){
    cout << "TBD" << endl ; 
    return 0  ; 
  }

  else {
    cout << "Heisei" << endl ; 
  }
}

Measured memory_bytes: 3636
#include<stdio.h>
#include<algorithm>
using namespace std;

#define VMAX 10001
int n, _min = VMAX;
int A[1000];
int B[1000];  //計数カウンタ
int T[10001]; //添え字と要素でサイクル先を示す
int solve(){

    int ans = 0;

    bool V[1000]; //訪れたかどうかを示す
    for(int i=0; i<n; i++){
        B[i] = A[i];
        V[i] = false;
    }
    sort(B, B+n);
    for(int i=0; i<n; i++) T[B[i]] = i; //計数カウンタ
    for(int i=0; i<n; i++){
        if(V[i]) continue; //ほかのサイクルを探す
        int cur = i; //サイクルのスタート地点
        int S = 0; //サイクル内の要素の合計
        int m = VMAX; //サイクル内の要素の最小値
        int an = 0; //サイクル内の要素の数
        while(1){
            V[cur] = true;
            an++;
            int v = A[cur]; //要素
            m = min(m, v);
            S += v;
            cur = T[v]; //サイクル内の次の要素！
            if(V[cur]) break; //サイクルを一周した
        }
        ans += min(S+(an-2)*m, m+S+(an+1)*_min);
    }
    return ans;
}

int main(){

    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &A[i]);
        if(A[i] < _min) _min = A[i];
    }

    int ans = solve();
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 2840
#pragma GCC optimize("O3", "unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define ll long long

signed main() {
	int L; cin >> L;
	vector<ll> a(L);
	for (int i = 0; i < L; ++i)
		cin >> a[i];

	vector<vector<ll>> dp(L + 1);
	for (int i = 0; i <= L; ++i)
		dp[i].resize(5, 0LL);

	for (int i = 1; i <= L; ++i) {
		ll ai = a[i - 1];
		// dp[i][0]の決定
		dp[i][0] = dp[i - 1][0] + ai;
		// dp[i][1]の決定
		ll tmp = ai & 1LL;
		if (ai == 0) tmp += 2LL;
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + tmp;
		// dp[i][2]の決定
		tmp = (ai + 1) & 1LL;
		dp[i][2] = min({ dp[i - 1][0],dp[i - 1][1],dp[i - 1][2] }) + tmp;
		// dp[i][3]の決定
		tmp = ai & 1LL;
		if (ai == 0) tmp += 2LL;
		dp[i][3] = min({
			dp[i - 1][0],dp[i - 1][1],dp[i - 1][2],dp[i - 1][3]
			}) + tmp;
		// dp[i][4]の決定
		dp[i][4] = min({
			dp[i - 1][0],dp[i - 1][1],dp[i - 1][2],dp[i - 1][3],dp[i - 1][4]
			}) + ai;
	}

	ll ans = min({ dp[L][0],dp[L][1],dp[L][2],dp[L][3],dp[L][4] });
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 15872
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		String[] blue = new String[n];
		for(int i = 0; i < n; i++) {
			blue[i] = scan.next();
		}


		int m = scan.nextInt();

		String[] red = new String[m];
		for(int i = 0; i < m; i++) {
			red[i] = scan.next();
		}

		int resultscore = 0;

		for(int roop = 0; roop < n; roop++){

			int score = 0;

			for(int k = 0; k < n; k++) {
				if(blue[k].equals(blue[roop]))score = score + 1;
			}
			for(int j = 0; j < m; j++) {
				if(red[j].equals(blue[roop])) score = score - 1;
			}

			if(resultscore < score) {
				resultscore = score;
			}
		}

		if(resultscore < 0)resultscore = 0;

		System.out.println(resultscore);



	}

}

Measured memory_bytes: 21716
const gcdb = (a, b) => b ? gcdb(b, a % b) : a
function gcd() {
    let res = arguments[0]
    for (var i = 1; i < arguments.length; i++) {
        res = gcdb(res, arguments[i]); 
    }
    return res 
}

const input = require("fs").readFileSync("/dev/stdin", "utf8")

;(input => {
 
    const lines = input.split('\n')
    const K = lines[0] - 0

    let ans = 0
    for (let i = 1; i <= K; i++) {
        for (let j = 1; j <= K; j++) {
            for (let k = 1; k <= K; k++) {
                ans += gcd(i, j, k)
            }
        }
    }

    console.log(ans)

})(input)


Measured memory_bytes: 35784
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    ll L, R;
    cin >> L >> R;
    if (R - L + 1 >= 2019)
    {
        cout << 0 << endl;
        return;
    }

    ll ans = 100000000;
    for (ll i = L; i <= R; ++i)
    {
        for (ll j = i + 1; j <= R; ++j)
        {
            chmin(ans, (i * j) % 2019);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<stack>
#include<set>
using namespace std;
#define pb push_back
#define POP pop_back()
#define ll long long
#define db double
#define POP pop_back()
#define endl '\n'
#define PII pair<int,int>
#define FI first
#define SE second
#define VI vector<int>
#define QI queue<int>
#define SI stack<int>
#define debug cout<<"debug"<<endl;
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define ULL unsigned long long
#define fo(i,a,b) for (int i=a;i<=b;++i)
#define fd(i,a,b) for (int i=a;i>=b;--i)
#define mem(x,a) memset(x,a,sizeof(x))
const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int main(){
	ll x;cin >> x;
	for(ll i = 0;i <= 3000;i++){
		for(ll j = 0;j < i;j++){
			if(pow(i,5) - pow(j,5) == x){
				cout << i << " " << j << endl;
				return 0;
			}
			if(pow(i,5) + pow(j,5) == x){
				cout << i << " " << -j << endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 4060
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

inline long long read()
{
    char c;long long out=0,f=1;
    for (c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    if (c=='-'){f=-1;c=getchar();}
    for (;c>='0'&&c<='9';c=getchar()){out=(out<<3)+(out<<1)+c-'0';}
    return out*f;
}
void write(long long x)
{
	if (x<0){putchar('-');write(-x);return;}
    if (x>9){write(x/10);}
	putchar(x%10+'0');
}

int main()
{
	int d;
	
	cin>>d;
	
	switch (d)
	{
		case 25:
			puts("Christmas");
			break;
		case 24:
			puts("Christmas Eve");
			break;
		case 23:
			puts("Christmas Eve Eve");
			break;
		case 22:
			puts("Christmas Eve Eve Eve");
			break;
	}
	
	return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <unordered_map>
#include <limits>

std::vector<int> dp;
std::vector<int> cost;

int sol ( int i ) {
  if ( dp[i] != -1 ) return dp[i];

  int cost_min = std::numeric_limits<int>::max();
  for(int j=1; j<=2; j++) if ( (i-j) >= 0 ) cost_min = std::min( cost_min, sol(i-j) + std::abs(cost[i]-cost[i-j]) );

  return dp[i] = cost_min;
}

int main (void) {

  int N;
  std::cin >> N;

  cost.resize(N);
  for(int i=0; i<N; i++) std::cin >> cost[i];

  dp.assign(N,-1);
  dp[0] = 0;

  std::cout << sol(N-1) << std::endl;

  return 0;
}

Measured memory_bytes: 7296
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(register LL i = (a), i##_end_ = (b); i <= i##_end_ ; ++i)
#define drep(i, a, b) for(register LL i = (a), i##_end_ = (b); i >= i##_end_ ; --i)
typedef long long LL;
LL read() {
	LL x = 0, flag = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 3) + (x << 1) + (ch - 0x30);
		ch = getchar();
	}
	return flag * x;
}

#define Maxn 100009
LL n, a[Maxn], b[Maxn];
LL ans = 0;
int main() {
#ifdef Qrsikno
	freopen("AGC009_A.in","r",stdin);
	freopen("AGC009_A.out","w",stdout);
#endif
	n = read();
	rep(i, 1, n) a[i] = read(), b[i] = read();
	drep(i, n, 1) {
		(a[i] += ans) %= b[i];
		if(!a[i]) continue;
		ans += b[i] - a[i];	
	}
	printf("%lld\n", ans);
	return 0;
}




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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  vector<int> a{0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
  int x, y;
  cin >> x >> y;
  cout << (a[x] == a[y] ? "Yes" : "No") << endl;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
const double pi = acos(-1);
const int SIZE = 1 << 17;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
long long fac[200005], finv[200005], inv[200005];
vector<long long>dij;
struct edge { long long to, cost; };
vector<vector<edge> >G;

int n, k[200005], l[200005], ans;
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> k[i];
		l[i] = k[i];
	}
	sort(k, k + n);

	for (int i = 0; i < n; ++i) {
		if (l[i] <= k[(n - 1) / 2]) { ans = k[n / 2]; }
		else { ans = k[(n - 1) / 2]; }
		cout << ans << endl;
	}
}

Measured memory_bytes: 3712
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    if(c >= a && c <= b){
      System.out.println("Yes");
    }
    else
      System.out.println("No");
  }
}


Measured memory_bytes: 21076
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int mod=1e9+7,N=2e3+50;
inline int add(int x,int y) {return (x+y>=mod)?(x+y-mod):(x+y);}
inline int mul(int x,int y) {return (LL)x*y%mod;}
inline int power(int a,int b) {
    int rs=1;
    for(;b;b>>=1,a=mul(a,a)) if(b&1) rs=mul(rs,a);
    return rs;
}
int n,k,dp[N][N],fac[N*N*2],ifac[N*N*2];
inline int C(int x,int y) {return mul(ifac[x-y],mul(fac[x],ifac[y]));}
int main() {
    cin>>n>>k; int l=2*n*k;
    if(k==1) {puts("1"); return 0;}
    fac[0]=1;
    for(int i=1;i<=l;i++) fac[i]=mul(fac[i-1],i);
    ifac[l]=power(fac[l],mod-2);
    for(int i=l-1;~i;i--) ifac[i]=mul(ifac[i+1],i+1);
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=i;j++) {
            if(j==i) dp[i][j]=dp[i][j-1];
            else dp[i][j]=add(dp[i][j-1],mul(dp[i-1][j],C(k-2+(i-1)*k-(i-j-1),k-2)));
        }
    printf("%d\n",mul(dp[n][n],fac[n]));
}

Measured memory_bytes: 82176
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int a,b;

int main(){
	cin>>a>>b;
	cout<<a*b<<endl;
}

Measured memory_bytes: 3640
def Main(K, N, A):
    dist = [0]*N
    for i in range(1, N):
        dist[i-1] = A[i] - A[i-1]
    dist[N-1] = K - A[N-1] + A[0]
    return sum(dist) - max(dist)

def main():
    K, N = map(int, input().split())
    A = list(map(int, input().split()))
    print(Main(K, N, A))

if __name__ == '__main__':
    main()

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

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

    int a = 0, b = 0, c = 0;
    std::cin >> a >> b >> c;
    std::unordered_map<char, int> d;
    ++d[a]; ++d[b]; ++d[c];
    if (d[5] == 2 && d[7] == 1)
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;

    return 0;
}


Measured memory_bytes: 3612
#include <stdio.h>
 
int main(void)
{
    int n, a[100], i;
 
    scanf("%d\n", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (i = n - 1; i >= 0 ; i--) {
        printf("%d", a[i]);
        if (i != 0) printf(" ");
    }
    printf("\n");
}


Measured memory_bytes: 2136
def main():
    import numpy as np
    A=[]
    for _ in range(3):
        A.append(list(map(int,input().split())))
    
    R=np.zeros((3,3))
    K=[]
    for a in A:
        K+=a

    N=int(input())
    for i in range(N):
        b=int(input())
        if b not in K:
            continue
        
        idx=K.index(b)
        R[idx//3,idx%3]=1

    if any( all(x) for x in R.tolist()) or any(all(x) for x in R.T.tolist()):
        print('Yes')
    elif R[0,0] and R[1,1] and R[2,2] or R[0,2] and R[1,1] and R[2,0]:
        print('Yes')
    else:
        print('No')
        
main()


Measured memory_bytes: 20608
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Y = sc.nextInt();
		Y /= 1000;
		sc.close();
		for(int i = 0; i <= N; i++) {
			for(int j = 0; j <= N; j++) {
				if(i + j > N) break;
				int k = N - (i + j);
				int t = i + 5 * j + 10 * k;
				if(t == Y) {
					System.out.println(k + " " + j + " " + i);
					System.exit(0);
				}
			}
		}
		System.out.println("-1 -1 -1");
	}
}

Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
int main()
{
    int h, w, m;
    cin >> h >> w >> m;
    set<P> c;
    map<int,int> mph, mpw;
    int hmax = 0, wmax = 0;
    rep(i, m){
        int a, b;
        cin >> a >> b;
        --a;--b;
        c.emplace(a,b);
        mph[a]++;mpw[b]++;
        hmax = max(hmax, mph[a]);
        wmax = max(wmax, mpw[b]);
    }
    vector<int> hidx, widx;
    for (auto p : mph){
        if (p.second==hmax) hidx.push_back(p.first);
    }
    for (auto p : mpw){
        if (p.second==wmax) widx.push_back(p.first);
    }
    int ans = hmax+wmax-1;
    for (int i: hidx){
        for (int j : widx){
            if (c.find({i,j})==c.end()) {
                ans++;
                cout << ans << endl;
                return 0;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 49504
#include<iostream>
#include<queue>
using namespace std;
#include<iostream>
#include<cstdlib>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define fir first
#define sec second

const int N = 100;
const int inf =(1<<25);
enum{A=0,B=1};
enum{WIN=1,LOSE=0,UNKNOWN=-1};
class st{
public:
  bool who;//previous move
  int a,b;
  int cost;
};

int win[2][N][N];
int deg[2][N][N];
int cost[2][N][N];
vector<int> edge[N];
int revdeg[N];

void solve(int n,int ta,int tb){
  rep(j,n)rep(k,n){
    cost[A][j][k]=0,cost[B][j][k]=0;
    win[A][j][k]=win[B][j][k]=UNKNOWN;
  }

  //dge ini
  rep(i,n){
    rep(j,n){
      deg[A][i][j]=edge[i].size();
      deg[B][i][j]=edge[j].size();
    }
  }

  //initial state
  queue<st> Q;
  rep(i,n){
    win[A][i][i]=LOSE;
    cost[A][i][i]=0;
    Q.push((st){A,i,i,0});
  }

  while(!Q.empty()){
    st now = Q.front();Q.pop();
    int cur=now.who==A?now.b:now.a;
    
    rep(i,edge[cur].size()){
      bool nexw=!now.who;
      int  next=edge[cur][i];
      int  nexa=now.who==A?now.a:next;
      int  nexb=now.who==B?now.b:next;
      if (win[nexw][nexa][nexb] != UNKNOWN)continue;
      
      cost[nexw][nexa][nexb]=max(cost[nexw][nexa][nexb],now.cost+1);
      
      deg[nexw][nexa][nexb]--;
      if (win[now.who][now.a][now.b] == LOSE){//B only
	cost[nexw][nexa][nexb]=now.cost+1;
	win[nexw][nexa][nexb]=WIN;
	Q.push((st){nexw,nexa,nexb,now.cost+1});
      }else if (deg[nexw][nexa][nexb] == 0){
	//A only
	win[nexw][nexa][nexb]=LOSE;
	cost[nexw][nexa][nexb]=now.cost+1;
	Q.push((st){nexw,nexa,nexb,now.cost+1});
      }
    }
  }
  
  if (win[A][ta][tb]==LOSE)cout << cost[A][ta][tb]/2<<endl;
  else cout << "infinity"<<endl;
}

main(){
  int te;
  cin>>te;
  while(te--){
    int n;
    cin>>n;
    rep(i,n)edge[i].clear(),revdeg[i]=0;
    rep(i,n){
      rep(j,n){
	bool a;cin>>a;
	if (a){
	  edge[i].push_back(j);
	  revdeg[j]++;
	}	
      }
      edge[i].push_back(i);
      revdeg[i]++;
    }

    int a,b;
    cin>>a>>b;
    solve(n,a,b);
  }
  return false;
}

Measured memory_bytes: 0
def cin; gets.split.map(&:to_i) end
def cout(*x); puts x.join(" ") end

# exit if $0 != __FILE__

a = gets.to_i
b = gets.to_i
c = gets.to_i
d = gets.to_i
e = gets.to_i
k = gets.to_i
if e-a <= k then
  puts 'Yay!'
  exit
end
puts ':('


Measured memory_bytes: 1788
import java.util.*;
public class Main {
   	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        int k = sc.nextInt();
        long mod = 1000000007;
        long [] [] pascal = new long [2001][2001];
        for(int i=0;i<=2000;i++){
        for(int j=0;j<=i;j++){if(j==0 || j==i){pascal[i][j]=1;}
                             else{pascal[i][j]=(pascal[i-1][j-1]+pascal[i-1][j])%mod;}
                             }
        }
        for(int i=1;i<=k;i++){long a = pascal[k-1][i-1];
                              long b = pascal[n-k+1][i];
                              System.out.println((a*b)%mod);}                            	
	}
}


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

//頂点数がN,枝数がM
//BellmanFord BF(N, M);
//適宜add(edge)
//BF.comp(出発点)でdに最短路長が入る
//負の有向閉路には3種類存在することに注意する

template<typename T> class BellmanFord {
public:
  struct edge {
    int from, to;
    T cost;
  };
  int V;
  T inf;
  vector<T> d;
  vector<edge> es;
  BellmanFord(int node_size) : V(node_size), inf(numeric_limits<T>::max() / 2), d(V, inf) {}
  void add(int from, int to, T cost) {
    es.push_back((edge) {from, to, cost});
  }
  //sからの最短路長およびsからたどり着ける負の閉路の検出(trueなら負の閉路が存在する)
  bool solve(int s) {
    int cnt = 0;
    d[s] = 0;
    while (cnt < V) {
      bool update = false;
      for (auto& e : es) {
        if (d[e.from] != inf && d[e.to] > d[e.from] + e.cost) {
          d[e.to] = d[e.from] + e.cost;
          update = true;
        }
      }
      if (!update) break;
      cnt++;
    }
    return (cnt == V);
  }
  //すべての負の閉路の検出(trueなら負の閉路が存在する)
  bool find_negative_loop() {
    fill(d.begin(), d.end(), (T)0);
    int cnt = 0;
    while (cnt < V) {
      bool update = false;
      for (auto& e : es) {
        if (d[e.to] > d[e.from] + e.cost) {
          d[e.to] = d[e.from] + e.cost;
          update = true;
        }
      }
      if (!update) break;
      cnt++;
    }
    return (cnt == V);
  }
  // s, t 間の最短距離が非有界
  bool shortest_path_infinite(int s, int t) {
    d[s] = 0;
    for (int i = 0; i < 2 * V - 1; i++) {
      for (auto& e : es) {
        if (d[e.from] != inf && d[e.to] > d[e.from] + e.cost) {
          d[e.to] = d[e.from] + e.cost;
          if (i >= V-1) {
            if (e.to == t) return true;
            d[e.to] = -inf;
          }
        }
      }
    }
    return false;
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  BellmanFord<long> BF(N);
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    BF.add(--a, --b, -c);
  }
  if (BF.shortest_path_infinite(0, N - 1)) return cout << "inf" << "\n", 0;
  cout << -BF.d.at(N - 1) << "\n";
}

Measured memory_bytes: 384
N, K = map(int, input().split())
plus = []
minus = []
zero = 0
for i in map(int, input().split()):
    if i > 0:
        plus.append(i)
    elif i < 0:
        minus.append(i)
    else:
        zero += 1
plus.sort()
minus.sort(reverse=True)


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok, ng = -10 ** 19, 10 ** 19
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    cnt = 0
    if mid >= 0:
        cnt += len(plus) * len(minus)
        if mid > 0:
            cnt += zero * (zero - 1) // 2 + zero * (N - zero)
            for a in (plus, minus):
                l, r = 0, len(a) - 1
                while l < r:
                    while l < r and a[l] * a[r] >= mid:
                        r -= 1
                    cnt += r - l
                    l += 1
    else:
        r = len(minus) - 1
        for l in range(len(plus)):
            while r >= 0 and plus[l] * minus[r] < mid:
                r -= 1
            cnt += len(minus) - (r + 1)

    if cnt < K:
        ok = mid
    else:
        ng = mid

print(ok)


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

#define ll long long
#define ull unsigned long long 
#define endl '\n'

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

    string ans;
    for(int i=0; i<7; ++i){
        string fs = s.substr(0, i);
        string ls = s.substr(n-7+i);
        ans = fs+ls;

        if(ans == "keyence"){
            cout << "YES";
            return 0;
        }

    }

    cout << "NO";
}


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

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

  vector<int> city(N,0);
  vector<int> a(M), b(M);

  for(int i = 0; i < M; i++){
    cin >> a[i] >> b[i];
  }

  for(int i = 0; i < M; i++){
    city.at(a[i]-1)++;
    city.at(b[i]-1)++;
  }

  for(int i = 0; i < N; i++){
    cout << city[i] << endl;
  }
}


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

#define rep(x, y) for (int i = (x); i < (y); i++)

typedef long long ll;

using namespace std;

void solve() {
    int n;
    cin >> n;

    int h[n];
    rep(0, n) cin >> h[i];

    int cnt = 0;
    bool possible;
    rep(1, n) {
        possible = true;
        for (int j = 0; j < i; j++) {
            if (i != j && h[i] < h[j]) {
                possible = false;
                break;
            }
        }

        if (possible) cnt++;
    }

    cout << (cnt + 1) << endl;
}

int main() {
    solve();

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define int long long
#define endl '\n'
#define INF 1000000000000000000
#define EPS 1e-10
#define PI 3.141592653589793238
#define all(a) a.begin(),a.end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define fi first
#define se second
#define pb push_back
#define double long double
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
typedef complex<double> com;
template<class T, class S> bool chmax(T &a, const S &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T, class S> bool chmin(T &a, const S &b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll n, ll m) { return (m ? gcd(m, n%m) : n); }
ll lcm(ll n, ll m) { return n / gcd(n, m)*m; }


signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	//modcalc();

	string s;
	cin >> s;
	cout << (s.substr(0, 4) == "YAKI" ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
s = input()
t = input()

dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]: #末尾が共通なら使った方がいい
            dp[i+1][j+1] = dp[i][j]+1
        else: #そうでないなら片方を削除
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
            
#復元
x = len(s)
y = len(t)
res = ''
while(dp[x][y]):
    if dp[x][y-1]==dp[x][y]: #行けるだけ左に
        y -= 1
    elif dp[x-1][y]==dp[x][y]: #行けるだけ上に
        x -= 1
    else:
        res = s[x-1] + res
        x -= 1
        y -= 1

print(res)

Measured memory_bytes: 147628