akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int a[100005][4];
int dp[100005][4];
int n;

int func(int ind, int flag) {

	if (ind == n) return 0;

	if (dp[ind][flag] != -1) return dp[ind][flag];

	int maxi = 0;
	if (flag == 0) {
		maxi = max(maxi, a[ind][1] + func(ind + 1, 1));
		maxi = max(maxi, a[ind][2] + func(ind + 1, 2));
		maxi = max(maxi, a[ind][3] + func(ind + 1, 3));
	}
	else if (flag == 1) {
		maxi = max(maxi, a[ind][2] + func(ind + 1, 2));
		maxi = max(maxi, a[ind][3] + func(ind + 1, 3));
	}
	else if (flag == 2) {
		maxi = max(maxi, a[ind][1] + func(ind + 1, 1));
		maxi = max(maxi, a[ind][3] + func(ind + 1, 3));
	}
	else {
		maxi = max(maxi, a[ind][1] + func(ind + 1, 1));
		maxi = max(maxi, a[ind][2] + func(ind + 1, 2));
	}

	return dp[ind][flag] = maxi;
}

int main() {

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= 3; j++) {
			cin >> a[i][j];
		}
	}

	memset(dp, -1, sizeof dp);

	cout << func(0, 0);

	return 0;
}


Measured memory_bytes: 14476
bool isChecked(int fh, int fw, int i, int j){
	if( (fh&(1<<i))==0 && (fw&(1<<j))==0 )return true;
	else return false;
}

void main(){
	int h, w, k;
	readf("%d %d %d\n", &h, &w, &k);
	string[] table;
	foreach(i; 0..h){
		table ~= readln().chomp();
	}
	int cnt;
	// 塗りつぶしを行う行
	foreach(fill_h; 0..2^^h){
		// 塗りつぶしを行う列
		foreach(fill_w; 0..2^^w){
			// 塗りつぶし後の黒いマスの数え上げ
			int blkcell;
			foreach(i, line; table){
				foreach(j, c; line){
					if( isChecked(fill_h, fill_w, i.to!int(), j.to!int()) ){
						if(c=='#')blkcell++;
					}
				}
			}
			if(blkcell==k)cnt++;
		}
	}
	cnt.writeln();
}

import std.stdio, std.conv, std.algorithm, std.numeric, std.string, std.math;

// 1要素のみの入力
T _scan(T= int)(){
	return to!(T)( readln().chomp() );
}

// 1行に同一型の複数入力
T[] _scanln(T = int)(){
	T[] ln;
	foreach(string elm; readln().chomp().split()){
		ln ~= elm.to!T();
	}
	return ln;
}


Measured memory_bytes: 2888
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
using LL = long long;
using P = pair<int,int>;

int main(){
	string S;
	cin >> S;
	if(S[0]==S[1] && S[2]==S[3] && S[0]!=S[2]){
		cout << "Yes" << endl;
	}
	else if(S[0]==S[2] && S[1]==S[3] && S[0]!=S[1]){
		cout << "Yes" << endl;
	}
	else if(S[0]==S[3] && S[1]==S[2] && S[0]!=S[1]){
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    s = input()
    print(700+s.count('o')*100)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
def powmod(b,r,mod)
  a = 1
  while r > 0
    if r%2 == 1
      a = a * b % mod
    end
    b = b * b % mod
    r /= 2
  end
  a
end

def factorial(n, mod)
  fs = [1]
  (1..n).each{ |k| fs << (fs[-1] * k) % mod }
  fs
end

def inv_factorial(n, mod)
  fs = [1]
  f = 1
  (1..n).each{ |k|
    f = f * k % mod
    fs << powmod(f, mod-2, mod)
  }
  fs
end

Mod = 998244353
K,N = gets.split.map(&:to_i)
$fs =     factorial(N+K, Mod)
$is = inv_factorial(N+K, Mod)

def hands(n,a,b)
  a = [a,0].max
  ans = 0
  d = 1
  #p [n,a,b]
  (0..b).each{ |r|
    m = n - r + a + r - 1
    k = r + a - 1
    unless m < 0 || k < 0 || m-k < 0
      v = $fs[b] * $is[r] % Mod * $is[b-r] % Mod * $fs[m] % Mod * $is[k] % Mod * $is[m-k] % Mod * d % Mod
      ans = (ans + v) % Mod
      #puts "#{[r,m,k]} C(#{b}, #{r}) * C(#{m}, #{k}) * 2^#{r} = #{v}"
    end
    d = (d << 1) % Mod
  }
  ans
end

(2..2*K).each{ |i|
  sr = [K, i-1].min
  ir = [i-sr, 1].max
  b = (sr-ir)/2+(i%2 > 0 ? 1 : 0)
  a = K-(sr-ir+1)
  #p [i,ir,sr,a,b]
  if i % 2 == 0
    p (hands(N, a, b) + hands(N-1, a, b)) % Mod
  else
    p hands(N, a, b)
  end
}

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

int main() {
  int n;
  cin >> n;
  if (n % 2 == 0) {
    cout << n / 2 << endl;
  } else {
    cout << (n / 2) + 1 << endl; 
  }
  return 0;
}

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

int main()
{
	char c;
	cin >> c;
	bool v = false;
	switch(c){
		case 'a': case 'e': case 'i': case 'o': case 'u':
			v = true;
			break;
	}
	cout << (v ? "vowel" : "consonant") << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main ()
{
	string a;
	cin>>a;
	int b=-1,c=-1;
	for(int i=0;i<a.length();i++)
	{
		if(a[i]=='C') b=i;
		if(a[i]=='F') c=i;
	}
	if(a=="CF")
	{
		cout<<"Yes";
		return 0;
	 } 
	if(b==-1||c==-1) cout<<"No";
	else if(b>c) cout<<"No";
	else cout<<"Yes";
}

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

int main(){
    int n;
    cin>>n;
    int ans;
    ans=n/111;
    ans=ans*111;
    if(n%111!=0&&n!=111){
        ans=ans+111;
    }
    cout<<ans<<endl;




    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
const int N=4093,p=1e9+7;
int c[N][N],s[N][N];
int A,B,n;
inline int qm(int x){return x<p?x:x-p;}
int main(){
	scanf("%d%d",&A,&B);n=A+B;
	for(int i=0;i<=n;++i){
		c[i][0]=s[i][0]=1;
		for(int j=1;j<=i;++j)c[i][j]=qm(c[i-1][j-1]+c[i-1][j]);
		for(int j=1;j<=n;++j)s[i][j]=qm(s[i][j-1]+c[i][j]);
		for(int j=1;j<=n;++j)s[i][j]=qm(s[i][j-1]+s[i][j]);
	}
	int ans=A+1;
	for(int i=0;i<=A;++i)
		for(int j=1;i+j<=A and j<B;++j)
			ans=(ans+1ll*c[B-1][j]*s[j-1][i])%p;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 129536
#include<bits/stdc++.h>
#define r(i,a,b) for(register int i=a;i<=b;i++)
#define ll long long
#define ull unsigned long long
#define ID(c) ('0'<=(c)&&(c)<='9')
#define pb push_back
using namespace std;
const int N=2e5+100;
inline int qr()
{
	int x=0,f=1;char c=getchar();
	for(;!ID(c);c=getchar()) if(c=='-') f=-1;
	for(; ID(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
	return x*f;
}
int n;
int a[N],b[N];vector<int> q,h; 
int id,tot;
int main()
{
	n=qr();
	r( i , 1 , n )
	{
		a[i] = qr();	
	} 
	r( i , 1 , n )     b[i] = qr();
	reverse(b+1 , b+1+n);
	r( i , 1 , n )
	{
		if(a[i] != b[i])    
					continue;
		    tot++,
		  h.pb(i);
		id = b[i];
	}
	r( i , 1 , n )
	{
		if(!tot) 	break;
		if(a[i] == b[i])
		continue;
		if(a[i]!=id && b[i]!=id)
		{
			--tot;
			q.pb(i);
		}
	}
	if( tot )  
	{
		printf("No\n");
		return 0;
	}
        for(int i=0;i<q.size();i++) 
		swap(b[h[i]],b[q[i]]);
        printf("Yes\n");
        r( i , 1 , n )
	printf("%d ",b[i]);		cout<<'\n';

	return 0;	
} 


Measured memory_bytes: 5740
#include <iostream>
#include <map>
using namespace std;
 #include <string>
int main(){
 map<string,int> gacha;
 int n;
  cin >> n;
  int kind=0;
  for(int i = 0; i < n; i++){
   string temp;
   cin >> temp;
   if(gacha[temp]!=1){
  	gacha[temp]=1;
   kind++;
   }
  }
  cout << kind << endl;
}

Measured memory_bytes: 18728
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

long long quick_pow(long long a, long long b){
	long long ans = 1;
	while (b){
		if (b & 1){
			ans = (ans * a) % MOD;
		}
		a = (a * a) % MOD;
		b /= 2;
	}
	return ans;
}

long long C(long long n, long long m){
	long long ans = 1;
	for (long long i = n - m + 1; i <= n; ++i){
		ans = (ans * i) % MOD;
	}
	long long p = 1;
	for (long long i = 1; i <= m; ++i){
		p = (p * i) % MOD;
	}
	ans = (ans * quick_pow(p, MOD - 2)) % MOD;
	return ans;
}

int main(){
	ios::sync_with_stdio(0);
	cout << setprecision(10) << fixed;
	long long x, y;
	cin >> x >> y;
	if ((x + y) % 3){
		cout << 0;
		return 0;
	}
	long long m = (2 * x - y) / 3;
	long long n = x - 2 * m;
	if (m < 0 || n < 0){
		cout << 0;
		return 0;
	}
	cout << C(n + m, n);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main(int argc, char* argv[]){
    int N, K;
    string S;
    cin >> N;
    cin >> S;
    cin >> K;

    char a = S[K-1];
    string ans;

    for(int i = 0; i < N; i++){
        if(S[i] != a)ans.push_back('*');
        else ans.push_back(S[i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()
test = ""
tmp = 0
for i in range(1, len(S)):
    j = -1 * i
    test = S[:j]
    tmp = len(test) // 2
    if len(test) % 2 == 0 and test[0:tmp] == test[tmp:]:
        print(len(test))
        exit()

Measured memory_bytes: 8980
#include <stdio.h>

int main(void) {
    char s[3];
    int count = 0;
    scanf("%s", s);
    for(int i=0; i < 3; i++) {
        if(s[i] == '1') {
            count++;
        }
    }

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

    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>

using namespace std;
typedef long long  ll;

ll div(string s, int d) 
{
//#    cout << ":" << s << ":" << d << endl;
    ll v = 0;
    string s1 = "";
    for(int i = 0; i < s.size(); i++) {
        s1 += s[i];
//#        cout << s1 << endl;
        if((d&(1<<i)) !=0) {
//#            cout << s1 << " ";
            v += stoll(s1);
            s1 = "";
        }
    }
    v+= stoll(s1);

//#    cout << s1 << endl;
    return v;

}


int main(void)
{
    string S;
    cin >> S;
//#    cout << S.size();
    ll cnt = 0;
//    div(S,0);
    for(int i = 0; i < (1<<(S.size()-1)); i++) {
        cnt += div(S, i);
    }
    cout << cnt <<endl;
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

const int MAXN = 1e6 + 10;
const int MM = 1e9 + 7;

int n, m;
char s[MAXN], t[MAXN];
int a[MAXN];

int main(){
    scanf("%d%d", &n, &m);
    if ((n & 1) && (m & 1))
        puts("Yes");
    else
        puts("No");
    return 0;
}


Measured memory_bytes: 256
#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 n, x, y;
  cin >> n >> x >> y;
  x--;
  y--;
  vector<int> ans(n);
  rep(i,n){
    for(int j=i+1;j<n;j++){
      int kyori = min(j-i,abs(x-i)+1+abs(y-j));
      //cout << i << ' ' << j << ' ' << kyori << endl;
      kyori--;
      ans[kyori] +=1;
    }
  }
  rep(i,n-1) cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
const int N = 3e3 + 10;
using namespace std;

int f[N][N][2];
int n, m;
const int mod = 1e9 + 7;
inline void add(int &x,int y)
{  
   x += y; 
   if(x >= mod) x %= mod;
}

namespace solver
{
  void solve()
  {
    scanf("%d%d",&n,&m);
    for(int i=0; i<=m; ++i) f[0][i][!i]=1;
    for(int i=0; i<m; ++i)
	  for(int j=0; j<=n; ++j)
	    for(int v=0; v<2; ++v)
		{
		  int val=f[i][j][v];
		  if(j)
		  {
		    add(f[i+1][j-1][v|(j==1)], val);
			add(f[i+1][j][v|(j==1)], val);
		  }
		  if(n-j)
		  {
		    add(f[i+1][j][v], val);
			add(f[i+1][j+1][v], val);
		  }
		}
    int ans=0;
    for(int i=0; i<=n; ++i) add(ans,f[m][i][1]);
    printf("%d\n",ans);
  }
}

int main() { solver :: solve();}

Measured memory_bytes: 70784
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <math.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
typedef pair<ll,ll> P;
long long int INF = 1e18;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
std::vector<P> tree[100010];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
#define p(x) cout<<x<<endl;
#define e cout<<endl;
#define pe(x) cout<<x<<" ";
#define re(i,a,b) for(i=a;i<=b;i++)
 
ll i,j,k,l,ii,jj;
ll n,m;
ll p[200005],q[200005],ran[200005];
ll h,w,x,y,ans=0,sum;



ll find(ll x){
	if(p[x]==x){
		return x;
	}else{
		return p[x] = find(p[x]);
	}
}

void unite(ll x,ll y){
	x = find(x);
	y = find(y);
	if(x==y)return;
	if(ran[x]<ran[y]){
		p[x]=y;
	}else{
		p[y]=x;
		if(ran[x]==ran[y])ran[x]++;
	}
}

int main(){
	cin>>n>>m;
	for(i=1;i<=n;i++){
		cin>>q[i];
		p[i]=i;
	}
	for(i=0;i<m;i++){
		cin>>x>>y;
		unite(x,y);
	}
	for(i=1;i<=n;i++){
		if(find(i)==find(q[i])){
			ans++;
		}
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 8832
#頂点xの親を求める
def find_parent(x):
    y=parent[x]
    if y<0:
        return x
    parent[x]=find_parent(y)
    return parent[x]

#頂点aと頂点bのグループをつなげる
def connect(a,b):
    c=find_parent(a)
    d=find_parent(b)
    if c==d:
        return
    if parent[c]<parent[d]:
        parent[c]+=parent[d]
        parent[d]=c
    else:
        parent[d]+=parent[c]
        parent[c]=d
    return

#N個の頂点、M本の道で、i個目の道がAi-Biとなるような
#グラフについてグループ化する
N,M,K=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]
parent=[-1]*(N+1)
for A,B in AB:
    connect(A,B)
ans=[0]*(N+1)
for i in range(1,N+1):
    ans[i]=-parent[find_parent(i)]-1
for A,B in AB:
    ans[A]-=1
    ans[B]-=1
for C,D in CD:
    if find_parent(C)==find_parent(D):
        ans[C]-=1
        ans[D]-=1
print(*ans[1:])

Measured memory_bytes: 113112
#include <iostream>
#include <numeric>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




int main() {
	int A, B,C;
	cin >>A>>B>>C;
	string s = "bust";
	if (A+B+C<22) {
		s = "win";
	}
	cout << s<< endl;
}

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

int A[200000];

main () {
  int n;
  scanf("%d", &n);

  int max = 0;
  int max_arg = 0;
  bool is_multiple_max = false;
  int next_max = 0;
  rep(i,n) {
    int a;
    scanf("%d", &a);
    if (a>max) {
      next_max = max;
      max = a;
      max_arg = i;
      is_multiple_max = false;
    }
    else if (a==max) {
      is_multiple_max = true;
    }
    else if (a > next_max) {
      next_max = a;
    }
  }

  rep(i,n) {
    if (i==max_arg && !is_multiple_max) {
      printf("%d\n", next_max);
    }
    else {
      printf("%d\n", max);
    }
  }

  return 0;
}


Measured memory_bytes: 1664
N = int(input())
A = input()
B = input()
C = input()
cnt = 0
for a, b, c in zip(A, B, C):
    s = {a, b, c}
    if len(s) == 1:
        pass
    elif len(s) == 2:
        cnt += 1
    else:  # len(s) == 3
        cnt += 2
print(cnt)

Measured memory_bytes: 3060
N, M, K = map(int, input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))

Asum=[0]
Bsum=[0]
for i, a in enumerate(A):
  Asum.append(Asum[i]+a)
for i, b in enumerate(B):
  Bsum.append(Bsum[i]+b)

ans, b = 0, M
for a, asum in enumerate(Asum):
  if asum > K:
    break
  while Bsum[b]>K - asum:
    b-=1
  ans = max(ans, a+b)
print(ans)
 


Measured memory_bytes: 47672
m,d = map(int,input().split())
cnt = 0
for i in range(1,m+1):
  for j in range(1,d+1):
    d_2 = j//10
    d_1 = j%10
    if d_2*d_1 == i and d_2 > 1 and d_1 > 1:
      cnt += 1
print(cnt)

Measured memory_bytes: 3060
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<queue>
#include<string>
#include<sstream>
#include<iostream>
#include<sstream>
#include<stack>
#include<map>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<math.h>
#include <cassert>
using namespace std;
typedef long long ll;

int main()
{
	int n, m;
	cin >> n >> m;
	printf("%d", (n * 3 + m) / 2);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i,n,k) for(ll i=(n);i<(k);i++)
#define ALL(a)  (a).begin(),(a).end()
ll ans=0;
void Main(){
    ll n;cin>>n;
    vector<ll> a(n);
    For(i,0,n) cin>>a[i];
    ll minimum=a[0];
    For(i,0,n){
        if(minimum>=a[i]){
            ans++;
            minimum=a[i];
        }
    }
    cout<<ans<<endl;
}
int main(){
    Main();
    return 0;
}

Measured memory_bytes: 1792
import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

print(ans)

Measured memory_bytes: 81428
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0; i < n; i++) {
			a[i] = sc.nextInt() - i - 1;
		}
		Arrays.sort(a);
		long sum = 0;
		int b = a[n / 2];
		for(int i = 0; i < n; i++) {
			sum += Math.abs(a[i] - b);
		}
		System.out.println(sum);
	}
}


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

const vector<int> dy = {1, -1, 0, 0};
const vector<int> dx = {0, 0, 1, -1};

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

    int H, W;
    cin >> H >> W;
    vector<string> A(H);
    for (auto &s : A) cin >> s;

    int cnt = 0;
    for (auto &S : A) {
        for (auto &c : S) {
            if (c == '.') cnt++;
        }
    }

    vector<vector<int> > dist(H, vector<int>(W, INT_MAX));
    queue<P> que;
    que.push(make_pair(0, 0));
    dist.at(0).at(0) = 1;
    while (!que.empty()) {
        auto p = que.front();
        que.pop();
        int y = p.first;
        int x = p.second;
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy.at(i);
            int nx = x + dx.at(i);
            if (ny < 0 || H <= ny) continue;
            if (nx < 0 || W <= nx) continue;
            if (A.at(ny).at(nx) == '#') continue;
            if (dist.at(ny).at(nx) > dist.at(y).at(x) + 1) {
                dist.at(ny).at(nx) = dist.at(y).at(x) + 1;
                que.push(make_pair(ny, nx));
            }
        }
    }

    cout << ((dist.at(H - 1).at(W - 1) == INT_MAX) ? -1 : cnt - dist.at(H - 1).at(W - 1)) << endl;

    return 0;
}

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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

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

  if (abs(a - c) <= d || (abs(a - b) <= d && abs(b - c) <= d)) cout << "Yes" << "\n";
  else cout << "No" << "\n";

  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/python3

import re

class Num:
    def __init__(this, x):
        this.x = x

    def __str__(this):
        return str(this.x)

    def __add__(this, that):
        return Num(this.x + that.x)

    def __sub__(this, that):
        return Num(this.x - that.x)

    def __truediv__(this, that):
        return Num(int(this.x / that.x))

    def __mul__(this, that):
        return Num(this.x * that.x)

    def __neg__(this):
        return Num(-this.x)

n = int(input())
for _ in range(n):
    expr = input()[0:-1]
    expr = re.sub(r'(\d+)', r'Num(\1)', expr)
    print(eval(expr))

Measured memory_bytes: 6740
# solution

import io
import math
import scipy.sparse
import numpy

data = int(input())

array1 = list(map(lambda x:int(x)*2,input().split()))

array2 = list(map(lambda x:int(x)*2,input().split()))

sumt = sum(array1)

maxv = [min(i, sumt-i) for i in range(sumt+1)]

counter = 0

for t,v in zip(array1,array2):
    for i in range(counter,counter+t+1):
        maxv[i] = min(maxv[i], v)
    counter += t

for i in range(sumt):
    maxv[i+1] = min(maxv[i+1], maxv[i] + 1)
for i in reversed(range(sumt)):
    maxv[i] = min(maxv[i], maxv[i+1] + 1)

print(sum(maxv) / 4)

Measured memory_bytes: 17072
from collections import Counter
import sys
n = int(input())
a = Counter(list(map(int,input().split())))

if n % 2 == 0:
    for k,v in a.items():
        if v != 2:
            print(0)
            sys.exit()

else:
    for k,v in a.items():
        if k == 0:
            if v != 1:
                print(0)
                sys.exit(0)
        else:
            if v != 2:
                print(0)
                sys.exit()
                
print(2**(n//2) % (10**9+7))

Measured memory_bytes: 14820
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
const ll INF = 1e9 + 7;
typedef pair<int,int> P;// pair型は２つの値の組を表せる

int main(){
    int A[3][3];
    bool ok[3][3];
    
    rep(i,3)rep(j,3){
        cin >> A[i][j];
        ok[i][j]=false;
    }
    int N; cin >> N;
    vector <int> B(N);
    rep(i,N){
        cin >> B[i];
        rep(j,3)rep(k,3){
            if(B[i]==A[j][k]) ok[j][k]=true;
        }
    }
    
    bool ans=false;
    rep(i,3){
        if (ok[i][0] && ok[i][1] && ok[i][2]) ans=true;
        if (ok[0][i] && ok[1][i] && ok[2][i]) ans=true;
    }
    
    if ( (ok[0][0] && ok[1][1] && ok[2][2]) || (ok[0][2] && ok[1][1] && ok[2][0]) ) ans=true;
    
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue> 
#include <stack>
#include <set>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()

const int MAX = 1000000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++)
	{
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k)
{
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
	int x, y; cin >> x >> y;
	int a, b;
	if ((x + y) % 3 != 0)
	{
		cout << 0 << endl;
		return 0;
	}
	int l = min(x, y);
	int r = max(x, y);
	if (l * 2 < r)
	{
		cout << 0 << endl;
		return 0;
	}
	a = (x + y) / 3;
	b = y - a;
	
	COMinit();

	cout << COM(a, b) << endl;
}


Measured memory_bytes: 23680
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
cd=[list(map(int,input().split())) for _ in range(n)]
ab=sorted(ab,key=lambda x: x[0])
cd=sorted(cd,key=lambda x: x[0])
s=set()
ans=0
for i in range(n):
    c,d=cd[i]
    y=-1
    for j in range(n):
        a,b=ab[j]
        if a<c and b<d:
            if y<b and j not in s:
                y=b
                ind=j
    if y!=-1:
        s.add(ind)
        ans+=1
print(ans)

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

int n,k,ans;
int l[50];

int main(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>l[i];
	}
	sort(l,l+n);
	for(int i=n-1;i>=n-k;i--){
		ans+=l[i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
A = [list( map(int, input().split()) ) for _ in range(3)]
N = int(input())
b = set([int(input()) for _ in range(N)])

def check(A, b):
    # 縦
    for j in range(3):
        cand = []
        for i in range(3):
            cand.append(A[i][j])
        if set(cand) <= b:
            return True
        
    # 横
    for i in range(3):
        cand = []
        for j in range(3):
            cand.append(A[i][j])
        if set(cand) <= b:
            return True

    # 斜め
    if set([A[0][0], A[1][1], A[2][2]]) <= b or set([A[0][2], A[1][1], A[2][0]]) <= b:
        return True

if check(A, b):
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3064
from itertools import accumulate
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

inv = [0] * (N + 1)
for i in range(1, N + 1):
    inv[i] = pow(i, mod - 2, mod)

cum = list(accumulate([0] + A))

ans = cum[N] % mod
for i in range(1, N):
    ans += (cum[N] - cum[i]) * inv[N - i + 1]
    ans %= mod
for j in range(N - 1):
    ans += cum[j + 1] * inv[j + 2]
    ans %= mod
for i in range(1, N - 1):
    ans -= cum[i] * (inv[2] - inv[N - i + 1]) * 2
    ans %= mod
for j in range(1, N - 1):
    ans += cum[j + 1] * (inv[2] - inv[j + 2]) * 2
    ans %= mod

for i in range(1, N + 1):
    ans = ans * i % mod
print(ans)



Measured memory_bytes: 94408
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

typedef long long swl;
typedef unsigned long long uwl;

int main() {
#ifdef  DEBUG
  ifstream in("input.txt");
  cin.rdbuf(in.rdbuf());
#endif  // for local.
  int n, k;
  cin >> n >> k;
  int rt_n = (int)floor(sqrt(n));
  int ptnn = n/(rt_n+1) + rt_n;
  uwl p_rng[ptnn];
  uwl ptnbf[ptnn];
  uwl ptnaf[ptnn];
  memset(ptnaf, 0, sizeof(ptnaf));
  memset(p_rng, 0, sizeof(p_rng));

  for (int i = 0; i < rt_n; i++) {
    ptnaf[i] = n / (i+1);
    p_rng[i] = 1;
  }
  for (int i = 1; i < n/(rt_n+1) + 1; i++) {
    ptnaf[ptnn-i] = i;
  }
  for (int i = 1; i < n/(rt_n+1) + 1; i++) {
    p_rng[ptnn-i] = ptnaf[i-1] - ptnaf[i];
  }
  
  for (int i = 2; i < k; i++) {
    swl bfttl = 0;
    memcpy(ptnbf, ptnaf, sizeof(ptnaf));
    memset(ptnaf,     0, sizeof(ptnaf));
    
    for (int i = 0; i < ptnn; i++) {
      bfttl = (bfttl + ptnbf[i] * p_rng[i]) % MOD;
    }
    ptnaf[0] = bfttl;
    for (int j = 1; j < ptnn; j++) {
      bfttl = (bfttl - (swl)ptnbf[ptnn-j] * (swl)p_rng[ptnn-j]) % MOD;
      bfttl = bfttl < 0 ? bfttl + MOD : bfttl;
      ptnaf[j] = bfttl;
    }
  }
  
  uwl ans = 0;
  for (int i = 0; i < ptnn; i++) {
    ans = (ans + ptnaf[i] * p_rng[i]) % MOD;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1664
import java.math.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    System.out.println(s.charAt(s.length() - 1) == 's' ? (s + "es") : (s + "s"));
  }
}


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

int main(){
  while(true){
    int n, m;
    cin >> n >> m;

    if(n==0 && m==0)
     break;

    int a[1000];
    for(int i=0; i<n; i++){
      cin >> a[i];
    }
    int sum = -1;
    for(int i=0; i<n-1; i++){
      for(int j=i+1; j<n; j++){
        int p = a[i]+a[j];
        if(p<=m && p>sum){
          sum = p;
        }
      }
    }
    if(sum!=-1){
      cout << sum << endl;
    }
    else{
      cout << "NONE" << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 3076
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
map<ll,pair<ll,int>> s;
set<pair<ll,int>> t;
ll inf = 10000000000;
ll solve(ll x){
    auto it = s.upper_bound(x);
    it--;
    auto p = *it;
    return p.second.first + p.second.second*(x - p.first);
}

int curve(int x){
    auto it = s.upper_bound(x);
    it--;
    auto p = *it;
    return p.second.second;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,h,w; cin >> h >> w;
    s[0] = {inf,0}; t.insert({inf,0});
    s[1] = {0LL,0}; t.insert({0LL,1});
    s[w + 1] = {inf,0}; 
    for(i=1;i<=h;i++){
        int a,b; cin >> a >> b;
        ll hi1 = solve(a - 1),hi2 = solve(b + 1),k = curve(b + 1);
        t.erase({solve(a),a}); s[a] = {hi1 + 1,1},t.insert({hi1 + 1,a});
        t.erase({solve(b + 1),b + 1}); s[b + 1] = {hi2,k},t.insert({hi2,b + 1});
        auto it = s.upper_bound(a);
        while(true){
            auto q = *it;
            if(q.first>b) break;
            t.erase({q.second.first,q.first}); s.erase(it++);
        }
        auto q = *t.begin();
        if(q.first + i<inf) cout << q.first + i << endl;
        else cout << -1 << endl;
    }
}

Measured memory_bytes: 28540
#include <stdio.h>
#include <math.h>

typedef struct{
  double x,y;
}Point_t;

void kock(int n,Point_t p1,Point_t p2){
  Point_t s,t,u;

  if(n==0) return;

  s.x=(2*p1.x+1*p2.x)/3;
  s.y=(2*p1.y+1*p2.y)/3;
  t.x=(1*p1.x+2*p2.x)/3;
  t.y=(1*p1.y+2*p2.y)/3;

  u.x=(t.x-s.x)*cos(M_PI/3)-(t.y-s.y)*sin(M_PI/3)+s.x;
  u.y=(t.x-s.x)*sin(M_PI/3)+(t.y-s.y)*cos(M_PI/3)+s.y;

  kock(n-1,p1,s);
  printf("%f %f\n", s.x,s.y);
  kock(n-1,s,u);
  printf("%f %f\n", u.x,u.y);
  kock(n-1,u,t);
  printf("%f %f\n", t.x,t.y);
  kock(n-1,t,p2);
}

int main(){
  int n;
  Point_t p1,p2;

  p1.x=0;
  p1.y=0;

  p2.x=100;
  p2.y=0;

  scanf("%d",&n);

  printf("%f %f\n",p1.x,p1.y);
  kock(n,p1,p2);
  printf("%f %f\n",p2.x,p2.y);

  return 0;
}

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

#define froop1(a,n) for(int i = a;i < n;i++)
#define froop2(a,n) for(int i = a;i > n;i--)
int main(){
	long long X,Y,Z,sw = 0;
  cin >> X >> Y >> Z;
  if(X > Y && X > Z){
    sw = 0;
  }else if(Y > X && Y > Z){
    sw = 1;
  }else{
sw = 2;
  }
  long long i,dist;
  switch(sw){
    case 0:
      i = X / 2;
      dist = abs((X - i - i) * Y * Z);
      cout << dist << endl;
      break;
          case 1:
      i = Y / 2;
      dist = abs((Y - i - i) * X * Z);
      cout << dist << endl;
      break;
        case 2:
      i = Z / 2;
      dist = abs((Z - i - i)* Y * X);
      cout << dist << endl;
      break;
  }
return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define rep(i,b) for(int i=0;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()

typedef long long ll;
int g[15][15];

int main() {
    int n;
    cin >> n;
    rep(i, n)rep(j, n) g[i][j] = -1;
    rep(i, n){
        int m;
        cin >> m;
        rep(j, m) {
            int a, x;
            cin >> a >> x;
            --a;
            g[i][a] = x;
        }
    }
    int ans = 0;
    rep(i, 1 << n) {
        vector<int> d(n);
        rep(j, n) if (i >> j&1) {
            d[j] = 1;
        }
        bool ok = true;
        rep(j, n) {
            if (d[j]) {
                rep(k, n) {
                    if (g[j][k] == -1) continue;
                    if (g[j][k] != d[k]) ok = false;
                }
            }
        }
        if (ok) ans = max(ans, __builtin_popcount(i));
    }
    cout << ans << endl;
    return 0;


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=100010;

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

    string s;
    cin>>s;
    if(s[2]==s[3]&&s[4]==s[5]){cout<<"Yes";}
    else{cout<<"No";}

    return (0);
}


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

int main() {
  ll n, x;
  cin >> n >> x;
  vector<ll> a(n + 1, 1), b(n + 1, 1);
  for (ll i = 1; i <= n; i++) {
    a[i] = 1 + a[i - 1] + 1 + a[i - 1] + 1;
    b[i] = b[i - 1] + 1 + b[i - 1];
  }
  ll ans = 0;
  for (ll i = n; i >= 1; i--) {
    if (x == 0) break;
    x--;
    if (x <= a[i - 1]) continue;
    ans += b[i - 1] + 1;
    x -= a[i - 1] + 1;
  }
  if (x) ans++;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3616
import scala.io.StdIn._

object Main {
  def main(args: Array[String]): Unit = {
    val s: List[String] = readLine().split("").toList
    println(solve(s))
  }

  def solve(strings: List[String]): Int = strings.foldLeft(0)((acc: Int, x: String) => if(x == "1") acc + 1 else acc)
}


Measured memory_bytes: 25284
import scala.io.StdIn.{readInt,readLine}

object Main {
  def main(args:Array[String]) = {
    var n = 0
    while( {n=readInt;n} != 0 ) {
      val a = new Array[Int](10)
      for(i<-1 to n) {
        val m = readInt
        a(m) += 1
      }
      a.foreach { x => if(x==0) println("-") else println("*"*x) }
    }
  }
}

Measured memory_bytes: 50916
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

llong x, y;

int main() {
    cin >> x >> y;

    if (llabs(x - y) <= 1) {
        cout << "Brown" << endl;
    }
    else {
        cout << "Alice" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
n,m,x,y=map(int, input().split())
x_l = list(map(int, input().split()))
y_l = list(map(int, input().split()))
if max(x_l)<y and max(x_l) < min(y_l) and x < min(y_l):
  print("No War")
else:
  print("War")


Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        scanner.nextLine(); // empty string
        final String a = scanner.nextLine();
        final String b = scanner.nextLine();
        final String c = scanner.nextLine();

        int result = 0;
        for (int idx = 0; idx < n; idx++) {

            final char charInA = a.charAt(idx);
            final char charInB = b.charAt(idx);
            final char charInC = c.charAt(idx);

            if (charInA == charInB && charInB == charInC) {
                continue;
            } else if (charInA == charInB || charInB == charInC || charInC == charInA) {
                result++;
            } else {
                result += 2;
            }

        }

        System.out.println(result);

    }

}


Measured memory_bytes: 23124
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Job {
  long duration;
  long limit;
};

int main() {
  long N, A, B;
  cin >> N;
  vector<Job> jobs;
  jobs.reserve(N);
  for (long l = 0; l < N; ++l) {
    Job j;
    cin >> j.duration >> j.limit;
    jobs.push_back(j);
  }
  std::sort(jobs.begin(), jobs.end(), [] (const Job& a, const Job& b) {
    if (a.limit != b.limit) {
      return a.limit < b.limit;
    }
    return a.duration < b.duration;
  });
  long time = 0;
  bool enable = true;
  for (Job j : jobs) {
    time += j.duration;
    if (time > j.limit) {
      enable = false;
      break;
    }
  }
  if (enable) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3456
let nil = -1

type t = {
  mutable parent : int;
  mutable left : int;
  mutable right : int;
}

let make () = {
  parent = nil;
  left = nil;
  right = nil;
}

let search_root t n =
  let rec doit i =
    if i = n then nil
    else if t.(i).parent = nil then i
    else doit (i + 1)
  in doit 0

let preorder t root f =
  let rec doit i =
    f i;
    if t.(i).left <> nil then doit t.(i).left;
    if t.(i).right <> nil then doit t.(i).right
  in doit root

let inorder t root f =
  let rec doit i =
    if t.(i).left <> nil then doit t.(i).left;
    f i;
    if t.(i).right <> nil then doit t.(i).right
  in doit root

let postorder t root f =
  let rec doit i =
    if t.(i).left <> nil then doit t.(i).left;
    if t.(i).right <> nil then doit t.(i).right;
    f i
  in doit root

let () =
  let n = read_int () in
  let t = Array.init n (fun _ -> make ()) in
  let rec read i =
    if i < n then begin
      let (id, l, r) = Scanf.scanf "%d %d %d\n" (fun id l r -> (id, l, r)) in
      t.(id).left <- l;
      t.(id).right <- r;
      if l <> nil then t.(l).parent <- id;
      if r <> nil then t.(r).parent <- id;
      read (i + 1)
    end in
  read 0;
  let root = search_root t n in
  print_endline "Preorder";
  preorder t root (fun i -> Printf.printf " %d" i); print_newline ();
  print_endline "Inorder";
  inorder t root (fun i -> Printf.printf " %d" i); print_newline ();
  print_endline "Postorder";
  postorder t root (fun i -> Printf.printf " %d" i); print_newline ()

Measured memory_bytes: 2392
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define INF 1000000000000000000
#define all(x) x.begin(), x.end()
#define PI 3.141592653589793

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N, 1);
    vector<int> B(N, 0);
    B[0] = 1;
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (B[a])
            B[b] = 1;
        if (A[a] == 1)
            B[a] = 0;
        A[a]--;
        A[b]++;
    }

    int res = 0;
    rep(i, N) if (A[i] && B[i]) res++;
    cout << res << endl;
}

Measured memory_bytes: 1024
a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())
# if (v-w)*t>=(b-a):print("YES")
# else:print("NO")
q = abs(a-b)
e = (v-w)*t
if q<=e:
	print("YES")
else:
	print("NO")

Measured memory_bytes: 9016
package main

import (
  "bufio"
  "fmt"
  "os"
  "strconv"
)

func main () {
  sc := bufio.NewScanner(os.Stdin)
  sc.Split(bufio.ScanWords)

  var length int
  var count int = 0

  if sc.Scan() { length, _ = strconv.Atoi(sc.Text()) }

  input := make([]int, length)

  for i := 0; i < length; i++ {
    if sc.Scan() { input[i], _ = strconv.Atoi(sc.Text()) }
  }

  for i := 0; i < length; i++ {
    for j := length-1; j >= i+1; j-- {
      if input[j] < input[j-1] {
        input[j], input[j-1] = input[j-1], input[j]
        count++
      }
    }
  }

  for i := 0; i < length-1; i++ {
    fmt.Printf("%d ", input[i])
  }
  fmt.Printf("%d\n%d\n", input[length-1], count)
}



Measured memory_bytes: 1092
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int M = 1e3;
char mmp[M][M], s[M][M];
int h, w, k, step[M][M], dr[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
struct TnT
{
    int x, y, step, flag;
};
bool vis[M][M];
void bfs(TnT sta)
{
    memset(step, 0, sizeof(step));
    step[sta.x][sta.y] = 1;
    memset(vis, false, sizeof(vis));
    vis[sta.x][sta.y] = true;
    queue<TnT>q;
    q.push(sta);
    while (!q.empty())
    {
        TnT gg = q.front();
        q.pop();
        for (int i = 0 ; i < 4 ; i++)
        {
            TnT gl = gg;
            gl.x += dr[i][0];
            gl.y += dr[i][1];
            if (gl.x >= 0 && gl.x < h && gl.y >= 0 && gl.y < w && mmp[gl.x][gl.y] != '#' && !vis[gl.x][gl.y])
            {
                gl.step++;
                step[gl.x][gl.y] = gl.step;
                vis[gl.x][gl.y] = true;
                q.push(gl);
            }
        }
    }
}
int main(void)
{
    scanf("%d%d%d", &h, &w, &k);
    for (int i = 0 ; i < h ; i++)
        scanf("%s", mmp[i]);
    TnT sta;
    for (int i = 0 ; i < h ; i++)
    {
        for (int j = 0 ; j < w ; j++)
        {
            if (mmp[i][j] == 'S')
            {
                sta.x = i, sta.y = j;
                break;
            }
        }
    }
    sta.step = 0, sta.flag = k;
    bfs(sta);
    int ans = 1000000000;
    for (int i = 0 ; i < h ; i++)
    {
        for (int j = 0 ; j < w ; j++)
        {
            if (step[i][j] != 0)
            {
                int gg = step[i][j], gl = 0;
                gl = gg / k + (gg % k != 0);
                gg = i;
                ans = min(ans, gl + gg / k + (gg % k != 0));
                gg = j;
                ans = min(ans, gl + gg / k + (gg % k != 0));
                gg = h - 1 - i;
                ans = min(ans, gl + gg / k + (gg % k != 0));
                gg = w - 1 - j;
                ans = min(ans, gl + gg / k + (gg % k != 0));
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


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

#define rep(i,n) for(ll i = 0; i < (n); i++)
#define REP(i,n) for(ll i = 1; i < (n); i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define yesorno(a) printf(a ? "yes\n" : "no\n")
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define YESorNO(a) printf(a ? "YES\n" : "NO\n") 
#define endl "\n"
using ll = long long;
using P = pair<int,int>;
using Pll = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


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

  int k, n;
  cin >> k >> n;
  vi a(n);
  rep(i,n) cin >> a[i];
  vi d(n);
  d[0] = (a[0] - 0) + k - a[n-1];
  REP(i,n){
    d[i] = a[i] - a[i-1];
  }
  sort(rall(d));
  int mx = d[0];
  int ans = k - mx;
  cout << ans << endl;
}

Measured memory_bytes: 1792
#!python3

import sys
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, M = iim()
    it = map(int, sys.stdin.read().split())

    d1 = defaultdict(list)

    for i, j in zip(it, it):
        d1[i].append(j)
        d1[j].append(i)

    ans = [0] * (N+1)
    dq = [1]
    visited = set([1])

    updated = True
    while updated:
        updated = False
        dq2 = []
        for i in dq:
            for j in d1[i]:
                if j in visited:
                    continue
                ans[j] = i
                dq2.append(j)
                visited.add(j)
                updated = True
        dq = dq2

    if len(visited) == N:
        print("Yes", *ans[2:], sep="\n")
    else:
        print("No")






if __name__ == "__main__":
    resolve()


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(10);
  cerr << fixed << setprecision(10);

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

  int minb = b * 10;
  int maxb = (b + 1) * 10;
  for (int i = minb; i < maxb; ++i) {
    if ((int)(i / 12.5) == a) {
      cout << i << '\n';
      return 0;
    }
  }
  cout << "-1" << '\n';

  return 0;
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  int ans=0;
  vector<int> foods(m,0);
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++){
      int s;
      cin>>s;
      foods[s-1]++;
    }
  }
  for(int i=0;i<m;i++){
    if(foods[i]==n){ans++;}
  }
   cout<<ans<<endl; 
}

Measured memory_bytes: 256
def solve():
    ans = float("inf")
#    print(x[2])
    for i in range(N-K+1):
        #print(i)
        ans = min(ans, abs(x[i])+abs(x[i]-x[i+K-1]), abs(x[i+K-1])+abs(x[i+K-1]-x[i]))
    print(ans)

if __name__=="__main__":
    N,K = list(map(int, input().split()))
    x = list(map(int, input().split()))
    solve()



Measured memory_bytes: 20040
def merge(A, left, mid, right):
	global count
	n1 = mid - left
	n2 = right - mid
	L=[]
	R=[]
	
#	for i in range(n1):
#		L.append(A[left + i])
#	for i in range(n2):
#		R.append(A[mid + i])
	L=A[left:mid]
	R=A[mid:right]

	L.append(10e10)
	R.append(10e10)
	i = 0
	j = 0
	for k in range(left , right):
		count +=1
		if L[i] <= R[j]:
			A[k] = L[i]
			i = i + 1
		else: 
 			A[k] = R[j]
 			j =	 j + 1

def mergeSort(A, left, right):
	if left+1 < right:
		mid = (left + right)//2
		mergeSort(A, left, mid)
		mergeSort(A, mid, right)
		merge(A, left, mid, right)
		
n = int(input())
A = list(map(int, input().split()))
count = 0
mergeSort(A, 0, n)
print(*A)
print(count)




Measured memory_bytes: 63708
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <climits>
#include <map>
#include <stack>
using namespace std;
#define M_PI 3.141592
#define toRad 2.0*M_PI/360.0
#define inin(x) int x;cin>>x;
#define all(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" "<<x<<endl;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define first second
#define second first
typedef pair<int, int> pii;
int w, n;
pii memo[1000][1200];
vector<pii> a;
pii dp(int num, int W)
{
	if (W > w)return pii(INT_MIN, INT_MAX);
	if (num == n)return pii(0, 0);
	if (memo[num][W].first != -1)return memo[num][W];
	pii ans;
	if (dp(num + 1, W).first == dp(num + 1, W + a[num].second).first + a[num].first)
	{
		if (dp(num + 1, W).second < dp(num + 1, W + a[num].second).second)
		{
			ans = dp(num + 1, W);
		}
		else
		{
			pii p = dp(num + 1, W + a[num].second);
			p.first += a[num].first;
			p.second += a[num].second;
			ans = p;
		}
	}
	else if (dp(num + 1, W).first > dp(num + 1, W + a[num].second).first + a[num].first)
	{
		ans = dp(num + 1, W);
	}
	else
	{
		pii p = dp(num + 1, W + a[num].second);
		p.first += a[num].first;
		p.second += a[num].second;
		ans = p;

	}
	return memo[num][W] = ans;
}

int main()
{
	int Case = 0;
	while (cin >> w&&w&&++Case)
	{
		memset(memo, -1, sizeof memo);
		a.clear();
		cin >> n;
		rep(i, n)
		{
			pii x;
			scanf("%d,%d", &x.first, &x.second);
			a.push_back(x);
		}
		sort(all(a));
		pii val = dp(0, 0), wei;
		cout << "Case " << Case << ":" << endl;
		cout << val.first << endl << val.second << endl;
	}
}

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

int N;
int P[200000];

int main(){

	cin >> N;

	for (int i=0; i<N; i++) {
		cin >> P[i];
	}

	int min_p = 200000;
	int ans = 0;
	for (int i=0; i<N; i++) {
		if (P[i] <= min_p) {
			ans++;
			min_p = P[i];
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>

using namespace std;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))

int main()
{
	int n, counter = 0;
	cin >> n;
	rep(i, 0, n - 1)
	{
		int a;
		cin >> a;
		if (a % 2 == 1)
		{
			++counter;
		}
	}
	if (counter % 2 == 0)
	{
		cout << "YES" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}


}

Measured memory_bytes: 256
import java.util.Scanner;

//String
public class Main{

	void run(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			char[] s = sc.next().toCharArray();
			while(n--!=0){
				StringBuilder sb = new StringBuilder();
				int i = 0;
				char a = ' ';
				int c = 0;
				while(i<s.length){
					if(a==' '){
						a = s[i];
						c++;
					}
					else if(a==s[i]){
						c++;
					}
					else{
						sb.append(c+""+a);
						a = s[i];
						c = 1;
					}
					i++;
				}
				sb.append(c+""+a);
				s = sb.toString().toCharArray();
			}
			System.out.println(s);
		}
	}

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

Measured memory_bytes: 13000
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}

int main(){
    long long a=1, b=1,n;
    cin>>n;
    rep(i,0,n){
        long long aa,bb;
        cin>>aa>>bb;
        if((a<=aa)&&(b<=bb)){a=aa,b=bb; continue;}

        long long time=max(a/aa+((a%aa)?1:0),
                           b/bb+((b%bb)?1:0) );
        a=aa*time;b=bb*time;
        //cout <<a<<b<<"\n";
    }
    cout<<a+b;
    return 0;
}


Measured memory_bytes: 256