akhauriyash/Code-Regression huggingface dataset:
//author Eterna
#define Hello the_cruel_world!
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<utility>
#include<cmath>
#include<climits>
#include<deque>
#include<functional>
#include<numeric>
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))
#define ABS(x) ((x) >= 0 ? (x) : (-(x)))
#define pb(x) push_back(x)
#define lowbit(x) ((x) & (-(x)))
#define FRIN freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\in.txt", "r", stdin)
#define FROUT freopen("C:\\Users\\Administrator.MACHENI-KA32LTP\\Desktop\\out.txt", "w", stdout)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define outd(x) printf("%d\n", x)
#define outld(x) printf("%I64d\n", x)
#define memset0(arr) memset(arr, 0, sizeof(arr))
#define il inline
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int maxn = 1e5;
const int INF = 0x7fffffff;
const int mod = 1e9 + 7;
const double eps = 1e-7;
const double Pi = acos(-1.0);
inline int read_int() {
	char c;
	int ret = 0, sgn = 1;
	do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
	if (c == '-') sgn = -1; else ret = c - '0';
	while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
	return sgn * ret;
}
inline ll read_ll() {
	char c;
	ll ret = 0, sgn = 1;
	do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');
	if (c == '-') sgn = -1; else ret = c - '0';
	while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0');
	return sgn * ret;
}
char s[maxn + 5], now;
int n, k, cnt, m, res, sum, xxx;
bool first;
pair<int, int> arr[maxn + 5];
queue<int> q0, q1;
int main()
{
	n = read_int(), k = read_int();
	scanf("%s", s + 1);
	now = s[1];
	if (now == '1')first = true;
	for (int i = 1; i <= n; ++i) {
		if (s[i] == now)++cnt;
		else {
			arr[++m] = pii(now - '0', cnt);
			cnt = 1;
			now = s[i];
		}
	}
	arr[++m] = pii(now - '0', cnt);
	cnt = 0;
	for (int i = 1; i <= m; ++i) {
		if (arr[i].first == 1) sum += arr[i].second, res = max(res, sum), q1.push(arr[i].second);
		else if (arr[i].first == 0) {
			if (cnt < k) {
				++cnt;
				sum += arr[i].second;
				q0.push(arr[i].second);
			}
			else {
				sum += arr[i].second;
				sum -= q0.front(); q0.pop();
				q0.push(arr[i].second);
				if (!xxx) {
					xxx = 1;
					if (first) {
						sum -= q1.front(); q1.pop();
						first = false;
					}
				}
				else {
					sum -= q1.front(); q1.pop();
				}
			}
			res = max(res, sum);
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1408
# -*- coding: utf-8 -*-
import sys
import copy
from bisect import bisect_left

def main():
	N = int(input())
	
	if N == 1:
		print("Hello World")
	else:
		A = int(input())
		B = int(input())
		print(A+B)
	
	
if __name__ == "__main__":
	main()


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

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

    int a,b,c;
    a = n / 100;
    b = n % 100 / 10;
    c = n - a*100 - b*10;

    if(a == 7 || b == 7 || c == 7) cout << "Yes";
    else cout << "No";



}

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

int main()
{ 
	int N,Q;
	long long int K;
	int A[100000];
	int ans[100000];

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

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

	for (int i = 0; i < N; i++)
		ans[i] = -Q+K;

	for (int i = 0; i < Q; i++)
	{
		ans[A[i]-1]++;
	}

	for (int i = 0; i < N; i++)
	{
		if (ans[i] <= 0)
			printf("No\n");
		else
			printf("Yes\n");
	}
	

	return 0;
}
	

Measured memory_bytes: 1280
//わからなかったので解説を見た
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <math.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define REP2(i,n1,n2) for(int i=n1;i<n2;i++)
using namespace std;
typedef long long ll;

int main() {
    int a,b;
    cin >> a >> b;
    int c  = b-a;
    int d = 0;
    for(int i=0;i<c;++i){
        d += i;
    }
    int res = d-a;
    cout << res << endl;
    /*vector<pair<int,int>> pair1(n);
     vector<pair<int,int>> pair2(n);
     REP(i,n){
     int a,b;
     cin >> a >> b;
     pair1[i] = make_pair(a,b);
     }
     REP(i,n){
     int c,d;
     cin >> c >> d;
     pair2[i] = make_pair(c,d);
     }
     
     sort(pair1.begin(),pair1.end());
     sort(pair2.begin(),pair2.end());
     REP(i, n){
     cout << pair1[i].first << pair1[i].second <<endl;
     }
     int maxn = -1;
     int cand = -1;
     REP(i,n){
     REP(j,n){
     if(pair1[i].first<pair2[j].first){
     if(pair1[i].second>maxn){
     cand = i;
     }
     }
     }
     }
     /*REP(i, n){
     cout << pairs[i].first << pairs[i].second <<endl;
     }
     /*int n;
     int res = 100000;
     cin >> n;
     //vector<int> x(n);
     REP2(i,1,n/2+1){
     res = min(res,psum(i)+psum(n-i));
     if(psum(i)+psum(n-i)==1){
     cout << "i:" << i <<endl;
     }
     }
     cout << res << endl;*/
    return 0;
}



Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main(){
	int a,b,c,d;
	cin>>a;
	for(int i=1;i<=a;i++){
		cin>>b>>c>>d;
		if(b*b+c*c==d*d || c*c+d*d==b*b || b*b+d*d==c*c){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}

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

int main(){
  ll x,y;
  cin >> x >> y;
  if (x%y == 0) cout << -1 << endl;
  else cout << x << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3011;
const int P=1e9+7; 
int n,m;
ll f[N][N][2];
int main(){
	scanf("%d%d",&n,&m);
	if(n==1){
		ll ans=2;
		for(int i=1;i<=m;++i) ans=ans*2%P; 
		printf("%lld\n",ans);
		return 0;
	}
	f[0][0][0]=1;
	for(int i=1;i<=n;++i) f[0][i][1]=1;  
	for(int i=1;i<=m;++i){
		for(int j=2;j<n;++j){
			f[i][j][0]=(2*f[i-1][j][0]+f[i-1][j-1][0]+f[i-1][j+1][0])%P;
			f[i][j][1]=(2*f[i-1][j][1]+f[i-1][j-1][1]+f[i-1][j+1][1])%P;
		}
		f[i][1][0]=(f[i-1][1][1]+2*f[i-1][1][0]+f[i-1][0][0]+f[i-1][2][0])%P;
		f[i][1][1]=(f[i-1][1][1]+f[i-1][0][1]+f[i-1][2][1])%P;
		f[i][n][0]=(f[i-1][n][0]+f[i-1][n-1][0])%P;
		f[i][n][1]=(f[i-1][n][1]+f[i-1][n-1][1])%P;
		f[i][0][0]=(f[i-1][0][0]+f[i-1][1][1]+f[i-1][1][0])%P;
	}
	ll ans=0;
	for(int i=0;i<=n;++i) ans=(ans+f[m][i][0])%P;
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 141568
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<limits.h>
#include<utility>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(A) A.begin(),A.end()

int main() {
	ll n, k;
	cin >> n >> k;
	//cout << k << endl;
	vector<ll> a(n);
	vector<ll> b(n,LONG_MAX);
	vector<ll> c(n, LONG_MAX);
	rep(i, n) {
		cin >> a[i];
		a[i]--;
	}
	ll now = 0;
	ll next = a[0];
	ll i = 0;
	b[i] = now;
	c[0] = 0;
	ll loop = -1;
	while (true) {
		i++;
		b[i] = next;
		//cout << next << endl;
		if (c[next] == LONG_MAX) {
			c[next] = i;
		}
		else {
			loop = i - c[next];
			break;
		}
		now = next;
		next = a[now];

	}
	if (k <= i) {
		cout << b[k]+1 << endl;
	}
	else {
		//cout << loop << endl;
		//cout << i << endl;
		//cout << i - loop + (k - i + loop) % loop << endl;
		cout << b[i - loop + (k - i + loop) % loop]+1 << endl;
	}
}


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

namespace AC {
#define ll long long
#define PLL pair<ll, ll>
#define PDD pair<double, double>
#define PDPLL pair<double, PLL>
#define PLPLL pair<ll, PLL>
#define pb push_back
#define fi first
#define se second
#define ls rt << 1
#define rs rt << 1 | 1

    const ll N = 1e5 + 66;

    ll BUGS = 1;

    inline ll read(){
        ll x = 0;    bool flag = 1;   char ch = getchar();
        while(ch < '0' || ch > '9') { if(ch == '-') flag = 0; ch = getchar(); }
        while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
        if(flag) return x;  return (~(x - 1));
    }

    inline void read(ll arr[], ll s, ll e) { for(ll i = s; i <= e; ++i) arr[i] = read(); }

    inline void write(ll x){
        if(x < 0) { x = ~(x - 1); putchar('-'); }
        if(x > 9) write(x / 10); putchar(x % 10 + '0');
    }

    inline void print(ll x) { write(x); puts(""); }

    inline void print(ll arr[], ll s, ll e) {
        for(ll i = s; i <= e - 1; ++i) write(arr[i]), putchar(' ');
        write(arr[e]); puts("");
    }

    inline ll max3(ll a, ll b, ll c) { return max(a, max(b, c)); }

    inline ll min3(ll a, ll b, ll c) { return min(a, min(b, c)); }

    inline void debugNum(ll num, string ss) { cout << "BUGS" << BUGS++ << " : " << ss << " : " << num << endl; }

    inline void debugArr(ll arr[], ll s, ll e, string ss) {
        cout << "BUGS" << BUGS++ << " : " << ss << " : " << endl;
        for(ll i = s; i <= e; ++i) cout << "i : " << i << " val : " << arr[i] << endl;
    }

    inline void IO() {
        //ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
        //cout << setiosflags(ios::fixed) << setprecision(1); //保留小数点后1位
        //cout << setprecision(1); //保留1位有效数字
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
}using namespace AC;

ll arr[1100];

int main() {
    //IO();
    ll n = read(), k = read();
    read(arr, 1, n);
    sort(arr + 1, arr + 1 + n);
    ll ans = 0;
    for(ll i = 1; i <= k; ++i) {
        ans += arr[i];
    }
    print(ans);
    return 0;
}



Measured memory_bytes: 3600
while true
    n = gets.to_i
    break if n == 0
    arr = []
    n.times{
        p, d1, d2 = gets.chomp.split.map(&:to_i)
        arr << [p, d1 + d2]
    }
    arr.sort_by!{|p, d| d}
    puts arr.last.join(" ")
end


Measured memory_bytes: 7932
#include <ios>
#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

int main(int argc, const char *argv[])
{
  int n;
  cin >> n;

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

  double sum_inv = 0;
  for (auto n : a) {
    sum_inv += 1. / n; 
  }

  cout << fixed << setprecision(9) << 1. / sum_inv << "\n";
  return 0;
}

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


using namespace std;

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

	vector<int> a(n);
	vector<int> b(n);
	vector<int> c(n - 1);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
	}
	for (int i = 0; i < n-1; i++) {
		cin >> c[i];
	}

	int total=0;
	for (int i = 0; i < n; i++) {
		total += b[a[i]-1];
		if (i<n-1&&a[i+1] - a[i] == 1) {
			total += c[a[i]-1];
		}
	}

	cout << total;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = (int)1e9 + 7;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	int len = (int)1e7;
	
	
	void doIt() {
		int N = sc.nextInt();
		Map<String, Integer> map = new HashMap<>();
		map.put("AC", 0);
		map.put("WA", 0);
		map.put("TLE", 0);
		map.put("RE", 0);
		for(int i = 0; i < N; i++) {
			String S = sc.next();
			map.put(S, map.get(S) + 1);
		}
		System.out.println("AC x " + map.get("AC"));
		System.out.println("WA x " + map.get("WA"));
		System.out.println("TLE x " + map.get("TLE"));
		System.out.println("RE x " + map.get("RE"));
	}
	
	public static void main(String[] args) {
		new Main().doIt();
	}
 
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(a) (a).begin(), (a).end()

using namespace std;

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

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

    vector<int> m(N, 0);

    REP(i, M) {
        int A, B;
        cin >> A >> B;
        A--;
        B--;

        m[A] = max(m[A], H[B]);
        m[B] = max(m[B], H[A]);
    }

    int a = 0;
    REP(i, N) {
        if (H[i] > m[i]) a++;
    }

    cout << a << endl;

    return 0;
}


Measured memory_bytes: 4052
import java.util.Arrays;

public class Main {


  private static void solve() {
     int n = ni();
     int[] a = na(n);
     Arrays.sort(a);
     for (int i = 0, j = n - 1; i < j; i ++, j --) {
       int tmp = a[i];
       a[i] = a[j];
       a[j] = tmp;
     }
     int now = 0;
     for (; now < n - 1; now ++) {
       if (now + 1 >= a[now + 1]) break;
     }
     
     int cnt = 0;
     for (int v:  a) {
       if (v > now) {
         cnt ++;
       }
     }
     
     int dy = a[now] - now;
     int dx = cnt - now;
     
     System.out.println(dy % 2 == 1 && dx % 2 == 1 ? "Second" : "First" );
  }


  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 42080
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
/*ソートの時に使う
int sort(const void *a, const void *b){
    return *(int*)a-*(int*)b ;
}
    qsort (data,sizeof(data),sizeof(int),sort); 
*/
 
int main(void){
    long long n,m=0,a=0,r=0,c=0,h=0;
    scanf("%lld",&n);
    char s[n][12];
    for (int i=0; i<n; i++){
        scanf("%s",s[i]);
        if (s[i][0]=='M'){
            m++;
        } else if (s[i][0]=='A'){
            a++;
        } else if (s[i][0]=='R'){
            r++;
        } else if (s[i][0]=='C'){
            c++;
        } else if (s[i][0]=='H'){
            h++;
        }
    }
    long long ans;
    ans = m*a*r + m*a*c + m*a*h + m*r*c + m*r*h + m*c*h + a*r*c +a*r*h + a*c*h +r*c*h ;
    printf ("%lld\n",ans);
	return 0 ;
}

Measured memory_bytes: 1280
#include <cstdio>
#include <algorithm>
typedef long long ll;

const int N=200005,P=1000000007;
int n,Ans=1,Res;
int Head[N],Next[N<<1],To[N<<1],Val[N<<1],En;
int Vis[N],Sta[N],Top,w[N],f,a,b,c,s[N];

ll Inv(ll a,ll s=1){for(int b=P-2;b;b>>=1,a=a*a%P)if(b&1)s=s*a%P;return s%P;}
inline void Add(int x,int y,int z){Next[++En]=Head[x],To[Head[x]=En]=y,Val[En]=z;}

void DFS1(int x,int Fa)
{
    Vis[x]=2,Sta[++Top]=x;
    for(int i=Head[x],y;i;i=Next[i])
        if((y=To[i])!=Fa)
        {
            if(Vis[y]==2)
            {
                a=x,b=y,c=Val[i],++f;
                int Ts=Top;
                do if(w[--Ts]>c)a=Sta[Ts],b=Sta[Ts+1],c=w[Ts];
                while(Sta[Ts]!=y);
            }
            else if(!Vis[y])w[Top]=Val[i],DFS1(y,x);
        }
    Vis[x]=1,--Top;
}

void DFS2(int x,int Fa,int w)
{
    s[x]=1;
    for(int i=Head[x],y;i;i=Next[i])
        if((y=To[i])!=Fa&&y!=a&&(x!=a||y!=b))
            if(DFS2(y,x,Val[i]),Val[i]<w)
                s[x]+=s[y];
    Res=Res*Inv(s[x])%P;
}

int main()
{
    scanf("%d",&n),n<<=1;
    for(int i=1,x,y;i<=n;++i)scanf("%d%d",&x,&y),Add(x,y+n/2,x+y),Add(y+n/2,x,x+y);
    for(int i=1;i<=n;++i)Ans=(ll)Ans*i%P;
    for(int i=1,Tmp;i<=n;++i)
        if(!Vis[i])
        {
            f=0,DFS1(i,0);
            if(f!=1)return puts("0"),0;
            Res=1,DFS2(a,0,c);
            Tmp=Res,std::swap(a,b);
            Res=1,DFS2(a,0,c);
            Ans=Ans*ll(Tmp+Res)%P;
        }
    printf("%d\n",Ans);
    return 0;
}

Measured memory_bytes: 12288
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n=INT()
    k=INT()
    x=LIST()
    ans=0
    for i in x:
        ans+=2*min(abs(k-i),abs(0-i))
    print(ans)
if __name__ == '__main__':
    do()

Measured memory_bytes: 3064
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys


N,Q = map(int, input().split())
S = str(input())
lr = [[0 for j in range(2)] for i in range(Q)]
for i in range(Q):
  lr[i] = list(map(int, input().split()))

ac = [0] * N #start index of 'AC'
for i in range(N-1):
  if S[i:i+2] == 'AC':
    ac[i] += 1
ac = [0] + ac

# ac = cumsum of ac
for i in range(1,N+1):
  ac[i] = ac[i-1] + ac[i]

for l,r in lr:
  print(ac[r-1]-ac[l-1])

Measured memory_bytes: 76508
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define		int 			long long int
#define		pb				push_back
#define		fi(n)			for(int i=0;i<n;i++)
#define		fi1(n)			for(int i=1;i<n;i++)
#define		fj(n)			for(int j=0;j<n;j++)
#define		clr(x)			memset(x, 0, sizeof(x))
#define 	print(x)		for(auto a:x) cout<<a<<" ";cout<<"\n"
#define		nl 				"\n"
#define		vi				vector<int>
#define		si 				set<int>
#define		mp 				make_pair
#define		pairi			pair<int,int>
#define		vpairi			vector<pair<int,int>>
#define		ff				first
#define		ss				second
#define		inf 			1e9+10
#define 	input 			"C://Users//Piyush Aggarwal//Documents//Cpp files//input-output//input.txt"
#define 	output 			"C://Users//Piyush Aggarwal//Documents//Cpp files//input-output//output.txt"
#define 	error 			"C://Users//Piyush Aggarwal//Documents//Cpp files//input-output//error.txt"

int ctoi(char a){ int x=a-48 -49;return x;}
string itos(int a){
	string out_string;
	stringstream ss;
	ss<<a;
	out_string=ss.str();
	return out_string;
}
char itoc(int a){ return itos(a)[0];}
int pow(int e,int x){
	int ans=1;
	while(x>0){
		if(x&1) ans*=e;
		e*=e;
		x>>=1;
	}return ans;
}
string bin(int x){
	bitset<sizeof(1)*CHAR_BIT> bits(x);
	string b=bits.to_string(); return b;
}


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen(input, "r", stdin);
	freopen(output, "w", stdout);
	freopen(error, "w", stderr);
	#endif
	int T=1;
	// cin>>T;
	while(T--){
		int n,k,m,x,y,z;
		// cin>>n;
		string s,t;
		cin>>s>>t;
		int ans=INT_MAX;
		fi(s.length() - t.length() + 1){
			int cnt=0;
			for(int j=i;j<i+t.length();j++){
				if(s[j]!=t[j-i]) cnt++;
			}
			ans=min(ans,cnt);
		}
		cout<<ans<<nl;
		// vi a(n);
		// fi(n) cin>>a[i];


	}
	return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const double pi=acos(-1);
int main(){
  int n;
  cin >> n;
  ll m=1e18,M=-1e18,sum=0;
  rep(i,n){
    ll a;
    cin >> a;
    sum+=a;
    if(m>a)m=a;
    if(M<a)M=a;
  }
  cout << m << " " << M << " " << sum << endl;
  return 0;
}



Measured memory_bytes: 3112
#include <iostream>
#include <cstdio>
#include <string>
#define ll long long 
using namespace std;

int main() {
    ll n;
    string s;

    scanf("%lld", &n);
    cin >> s;

    ll w = 0;
    ll e = 0;

    for(ll i=0; i<n; i++) {
        if(s[i] == 'E') {
            e ++;
        }
    }
    
    ll ans = w+e;

    for (ll i=0; i<n; i++) {
        if(s[i] == 'W') {
            w ++;
        } else {
            e --;
        }

        ans = min(ans, w+e);
    }
    
    printf("%lld\n", ans);
}
    


Measured memory_bytes: 900
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit


def EulerTour(graph, root=1):
    N = len(graph) - 1
    parent = [0] * (N + 1)
    stack = [-root, root]
    tour = []
    ind_L = [0] * (N + 1)
    ind_R = [0] * (N + 1)
    i = -1
    while stack:
        v = stack.pop()
        tour.append(v)
        i += 1
        if v > 0:
            ind_L[v] = i
            p = parent[v]
            for w in graph[v]:
                if w == p:
                    continue
                parent[w] = v
                stack.append(-w)
                stack.append(w)
        else:
            ind_R[-v] = i
    return tour, ind_L, ind_R, parent


@njit('i8[:](i8[:],i8[:],i8[:],i8[:],i8[:])', cache=True)
def main(C, tour, ind_L, ind_R, parent):
    N = len(C) - 1
    removed = np.zeros(N + 1, np.int64)
    answer = np.full_like(removed, N * (N + 1) // 2)
    memo = np.zeros_like(answer)
    for v in tour:
        if v > 0:
            memo[v] = removed[C[parent[v]]]
        else:
            v = -v
            removed[C[v]] += 1
            p = parent[v]
            x = (ind_R[v] - ind_L[v]) // 2 + 1  # subtree size
            x -= removed[C[p]] - memo[v]
            answer[C[p]] -= x * (x + 1) // 2
            removed[C[p]] += x
    for i, x in enumerate(removed):
        x = N - x
        answer[i] -= x * (x + 1) // 2
    return answer


N = int(readline())
graph = [[] for _ in range(N + 1)]
C = np.zeros(N + 1, np.int64)
C[1:] = np.array(readline().split(), np.int64)
m = map(int, read().split())
for a, b in zip(m, m):
    graph[a].append(b)
    graph[b].append(a)

tour, ind_L, ind_R, parent = map(lambda x: np.array(x, np.int64), EulerTour(graph))

answer = main(C, tour, ind_L, ind_R, parent)
print('\n'.join(answer[1:].astype(str)))


Measured memory_bytes: 192728
#include <iostream>
using namespace std;
const int INF=0x3f3f3f3f,maxn=1111;
int a[maxn],n,m;
int main()
{
	int i,j,k,ans=0;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
}
	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			for(k=j+1;k<n;k++)
			{
				if(a[i]==a[j] || a[i]==a[k] || a[j]==a[k])
					continue;
				int x=a[i],y=a[j],z=a[k];
				if(x<y)
					swap(x,y);
				if(x<z)
					swap(x,z);
				if(y<z)
					swap(y,z);
				if(y+z>x && x-y<z)
					ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 3648
from math import factorial
N, K = map(int, input().split())

ans = 0
for i in range(K, N + 2):
    # print(i)

    tmp_min = (i - 1) * i / 2
    tmp_max = (N * (N + 1) / 2) - ((N - i) * (N - i + 1) / 2)
    # print(tmp_min, tmp_max)

    tmp = tmp_max - tmp_min + 1
    ans += tmp

print(int(ans % (10**9+7)))

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

int fact(int n) {
    return ((n == 1 || n == 0) ? 1 : n * fact(n - 1));
}

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i)
        cin >> x[i];
    for (int i = 0; i < n; ++i)
        cin >> y[i];
    int lex1 = 0, lex2 = 0;
    vector<int> used;
    for (int i = 0; i < n - 1; ++i) {
        int temp = x[i];
        for (int z : used)
            if (z < x[i])
                --temp;
        lex1 += fact(n - i - 1) * temp;
        used.push_back(x[i]);
    }
    used.clear();
    for (int i = 0; i < n - 1; ++i) {
        int temp = y[i];
        for (int z : used)
            if (z < y[i])
                --temp;
        lex2 += fact(n - i - 1) * temp;
        used.push_back(y[i]);
    }
    int lex = lex1 - lex2;
    cout << (lex < 0 ? lex - 2*lex : lex);
}

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

goukei = sum(A)
candidate = make_divisors(goukei)
tmp_goukei = 0
operation = 0
answer = 1
for c in candidate:
    mod_c = sorted([a % c for a in A], reverse=True)
    sum_c = sum(mod_c)
    #print(c, mod_c, sum_c)
    if sum_c % c != 0:
        continue
    counter = 0
    for a in mod_c:
        sum_c -= c
        counter += c - a
        if sum_c <= 0:
            break
    #print(c, a, counter)
    if counter <= K:
        answer = c
        break
    else:
        tmp_goukei = 0
        operation = 0
print(answer)


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

int main(){
	int n, k, Pmin, Pmax, P, wmax, sum = 0;
	cin >> n >> k;
	vector<int> w(n);
	for (int i = 0; i < n; i++){
		cin >> w[i];
		wmax = i == 0 ? w[0] : wmax < w[i] ? w[i] : wmax;
		sum += w[i];
	}
	if ((sum + n - 1) / n < wmax){
		Pmin = wmax;
	}
	else{
		Pmin = (sum + n - 1) / n;
	}
	Pmax = sum;
	P = Pmin + (Pmax - Pmin) / 2;

	bool isAllocable;
	int curwsum, curtrack;

	while(true){
		curwsum = 0;
		curtrack = 1;
		isAllocable = true;
		for (int i = 0; i < n; i++){
			if (curwsum + w[i] <= P){
				curwsum += w[i];
			}
			else{
				curtrack++;
				curwsum = w[i];
			}
			if (curtrack > k){
				isAllocable = false;
				break;
			}
		}
		if (isAllocable){
			Pmax = P;
		}
		else{
			Pmin = P + 1;
		}
		if (Pmin >= Pmax) break;
		P = Pmin + (Pmax - Pmin) / 2;
	}

	cout << Pmax << endl;

	return 0;
}


Measured memory_bytes: 3156
n,m=map(int,input().split())
a=[0]*n
List={}
a=list(map(int,input().split()))
for i in range(n):
  List.setdefault(a[i],0)
  List[a[i]]+=1
ans=0

for i in range(m):
  b,c=map(int,input().split())
  List.setdefault(c,0)
  List[c]+=b
  
List_sorted=sorted(List, reverse=True)

#print(List)
#print(List_sorted)
for i in List_sorted:
  if (List[i]<n):
    ans+=i*List[i]
    n-=List[i]
  else:
    ans+=i*n
    break
    
print(ans)

Measured memory_bytes: 32048
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<ii> a(n);
	vector<int> x(n);	
	for(int i = 0; i < n; ++i)
		cin >> a[i].second >> a[i].first;	
	sort(a.rbegin(), a.rend());
	vector<bool> used(n + 1, false);
	x[0] = 1;
	used[a[0].second] = true;
	for(int i = 1; i < n; ++i) {
		x[i] = x[i - 1];
		if(!used[a[i].second]) {
			++x[i];
			used[a[i].second] = true;
		}
	}
	fill(used.begin(), used.end(), false);
	priority_queue<int, vector<int>, greater<int>> pq;
	long long tot = 0, X = 0;
	for(int i = 0; i < k; ++i) {
		if(used[a[i].second]) pq.push(a[i].first);
		used[a[i].second] = true;
		tot += a[i].first;
		X = x[i];
	}
	long long r = tot;
	tot += X * X;
	for(int i = k; i < n; ++i) {
		if(pq.empty()) break;
		else if(!used[a[i].second]) {
			++X;
			r += a[i].first - pq.top();
			tot = max(tot, r + X * X);
			pq.pop();
			used[a[i].second] = true;
		}
	}
	cout << tot << '\n';
	return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;
public class Main
{
	public static void main(String arg[])
	{
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		while(n-->0)
		{
			char ch[] = in.next().toCharArray();
			int counta =0;
			int countb =0;
			boolean flag=false;
				if(ch[0]=='>'&&ch[1]=='\'' &&ch[ch.length-1]=='~'&&ch[ch.length-2]=='=')
				{
					int co=2;
					while(ch[co]!='#')
					{
						
						if(ch[co]=='=')
							counta++;
						else
						{
							counta=0;
							break;
						}
						co++;
						if(co==ch.length-1)
							break;
					}
					co++;
					while(ch[co]!='~')
					{
						if(ch[co]=='=')
							countb++;
						else 
						{
							counta=0;
							break;
						}
						co++;
					}
					if(counta==countb&&counta>0)
						System.out.println("A");
					else 
						System.out.println("NA");
					continue;
				}
				else
					if(ch[0]=='>'&&ch[1]=='^' &&ch[ch.length-1]=='~'&&ch[ch.length-2]=='~')
					{
						
						for(int co=2;co<ch.length-2;co+=2)
						{
							if(ch[co]=='Q'&&ch[co+1]=='=')
								flag = true;
							else 
							{
								flag = false;
								break;
							}
						}
					}
				System.out.println(flag==true ? "B":"NA");
			}
		}
	}

Measured memory_bytes: 12000
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iomanip>
#include<string>
#include <numeric>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main() {
	string s;
	cin >> s;
	if (s == "ani") { cout << "square1001" << endl; }
	else { cout << "e869120" << endl; }
	}



Measured memory_bytes: 3224
package main

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

var sc = bufio.NewScanner(os.Stdin)

func getInput() []int {
	sc.Split(bufio.ScanWords)

	sc.Scan()
	N, _ := strconv.Atoi(sc.Text())

	D := make([]int, N)
	for i := range D {
		sc.Scan()
		d, _ := strconv.Atoi(sc.Text())
		D[i] = d
	}

	return D
}

func main() {

	D := getInput()

	singleD := make([]int, 101)
	for i := range D {
		singleD[D[i]] = 1
	}
	sum := 0
	for sd := range singleD {
		sum += singleD[sd]
	}

	fmt.Println(sum)

}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<utility>
#include<queue>
#include<algorithm>
using namespace std;
int x,y,z;
int main(){
  cin>>x>>y>>z;
  cout<<(x-z)/(y+z)<<endl;
  return 0;
}


Measured memory_bytes: 256
//AnkitCode99 (DP)...
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"

const int N=3005;

int n, m;
string s, t;
int cache[N][N];

int dp(int i, int j)
{
	if(i==n)
		return 0;
	if(j==m)
		return 0;
	int &ans=cache[i][j];
	if(ans!=-1)
		return ans;
	if(s[i]==t[j])
		ans=1+dp(i+1, j+1);
	else
		ans=max(dp(i+1, j), dp(i, j+1));
	return ans;
}

void path(int i, int j)
{
	if(i==n)
		return;
	if(j==m)
		return;
	int ans=dp(i, j);
	if(s[i]==t[j])
	{
		cout<<s[i];
		return path(i+1, j+1);
	}
	else
	{
		if(ans==dp(i+1, j))
			return path(i+1, j);
		return path(i, j+1);
	}
}



int32_t main()
{
	IOS;
	memset(cache, -1, sizeof(cache));
	cin>>s>>t;
	n=s.size();
	m=t.size();
	int len=dp(0, 0);
	path(0, 0);
	return 0;
}


Measured memory_bytes: 35968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}
//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main(){
    int x,y;
    cin >> x;
    y = 200*(x/15);
    x *= 800;
    cout << x-y << endl; 

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
    int i,n;
    int count[10];
    int s[10000];

    while(scanf("%d",&n),n){
        for(i=0;i<10;i++){
            count[i]=0;
        }
        for(i=0;i<n;i++){
            scanf("%d",&s[i]);
            count[s[i]]++;
        }

        for(i=0;i<10;i++){
            for(n=0;n<count[i];n++){
                printf("*");
            }
            if(count[i]==0) printf("-");
            puts("");
        }
    }
    return 0;
}

Measured memory_bytes: 624
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll ; 
typedef long double ld ;
typedef pair<ll , ll> pll ;

const ll N = 2e5 + 30 , Mod = 1e9 + 7 ;
const ll SQ = 330 ;


ll a[N] ;
int main () {
    ios::sync_with_stdio(0), cin.tie(0) ;
    ll n ;
    cin >> n ;
    vector<ll> v ;
    for (int i = 0 ; i < n; i ++) {
    	cin >> a[i] ;
    	v.pb(a[i]) ;
	}
	sort(all(v)) ;
	for (int i = 0 ; i < n ; i ++) {
		a[i] = lower_bound(all(v) , a[i]) - v.begin() ;
	}
	ll ans = 0 ;
	for (int i = 0 ; i < n ; i ++) {
		if ((a[i] & 1) != (i & 1)) ans ++ ;
	}
	cout << ans / 2 ;
    
    return (0) ;
}

Measured memory_bytes: 1912
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define rep1(i,n) for(int i=1; i<(int)n; i++)
#define repa(i,a,n) for(int i=(a); i<(int)(n); i++)
#define all(vec) vec.begin(),vec.end()
using vi = vector<int>;
using vs = vector<string>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using psi = pair<string, int>;
const int dx[4] = {1, 0,-1, 0};
const int dy[4] = {0, 1, 0,-1};
const int mod = 1e9+7;
int gcd(int a, int b){if(a%b == 0){return(b);}else{return(gcd(b, a%b));}}
int lcm(int a, int b){return a / gcd(a, b)*b;}

int N, M, K, H, W, L, R, X;
//string S, T;

signed main(){
  int a, b, t;
  cin >> a >> b >> t;
  cout << (t/a)*b << endl;
  return 0;
}


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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]"):
    ret = 1
    A.sort()
    for a in A:
        ret *= a
        if ret > 10 ** 18:
            print(-1)
            return -1
    print(ret)
    return

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

if __name__ == '__main__':
    main()


Measured memory_bytes: 88656
#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() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(a.rbegin(), a.rend());
  int t = n-1;
  ll ans = 0;
  rep(i,n) {
    int s;
    if(i == 0) s = 1;
    else s = 2;
    rep(j,s) {
      if(t>0) {
      ans += a[i];
      t--;
    }
    }
  }
  cout << ans << endl;
}
    
  

Measured memory_bytes: 4036
//  A - Maximize the Formula
//  main.c

#include <stdio.h>

int main(int argc, const char * argv[]) {
    
    int a,b,c,d,e = 0;
    
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    
    if(a >= b){
        e = b;
        if(c >= a){
            d = (c * 10) + a;
        }else{
            d = (a * 10) + c;
        }
    }else{
        e = a;
        if(c >= b){
            d = (c * 10) + b;
        }else{
            d = (b * 10) + c;
        }
    }
    
    printf("%d\n",d+e);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef tuple<ll, ll, ll> T;

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> color(9,0);
    REP(i,n){
        int a;cin>>a;
        color[min(a/400,8)]++;
    }
    int ans=0;
    bool only=true;
    REP(i,8){
        if(color[i]>0){
            ans++;
            only=false;
        }
    }
    if(only) cout<<1<<" "<<ans+color[8]<<endl;
    else cout<<ans<<" "<<ans+color[8]<<endl;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;
// {{{ Modint
// using mint = modint<1000000007>;
// mint x = 2;
// std::cout << x.a << std::endl;
template <std::int64_t M>
class modint {
  public:
    int64_t a;

    explicit constexpr modint(const int64_t x = 0) noexcept :
      a((x % M + M) % M) {}
    constexpr int64_t &value() noexcept { return a; }
    constexpr const int64_t &value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
      return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
      return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
      return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
      return modint(*this) /= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept {
      a += rhs.a;
      if (a >= M) {
        a -= M;
      }
      return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept {
      if (a < rhs.a) {
        a += M;
      }
      a -= rhs.a;
      return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept {
      a = a * rhs.a % M;
      return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept {
      int64_t exp = M - 2;
      while (exp) {
        if (exp % 2) {
          *this *= rhs;
        }
        rhs *= rhs;
        exp /= 2;
      }
      return *this;
    }
    constexpr modint pow(ll t) const {
      if (!t) return modint(1);
      modint a = pow(t>>1);
      a *= a;
      if (t&1) a *= *this;
      return a;
    }
};
// }}}
using mint = modint<1000000007>;
const ll W = 0;
const ll B = 1;

ll N;
vector<ll> edges[100100];
vector<ll> edges2[100100];

// cur以下の部分木をcolで塗った時のパターン数
mint dp[100100][2];
vector<ll> vertices;

void dfs1(ll cur, ll par) {
  for (auto c: edges[cur]) {
    if (c == par)
      continue;
    edges2[cur].push_back(c);
    dfs1(c, cur);
  }
  vertices.push_back(cur);
}

signed main() {
  cin >> N;
  rep(i, N-1) {
    ll x, y;
    cin >> x >> y;
    x--; y--;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  dfs1(0, -1);
  //cout << "vertices:";
  //for (auto cur: vertices) {
  //  cout << cur << " ";
  //}
  //cout << endl;

  for (auto cur : vertices) {
    if (edges2[cur].size() == 0) {
      // 葉
      dp[cur][B] = mint(1);
      dp[cur][W] = mint(1);
    } else {
      // 内部ノード 
      // 自分を黒にする
      mint t = mint(1);
      for (auto c : edges2[cur]) {
        t *= dp[c][W];
      }
      dp[cur][B] = t;
      // 自分を白にする
      t = mint(1);
      for (auto c : edges2[cur]) {
        t *= dp[c][W] + dp[c][B];
      }
      dp[cur][W] = t;
    }
  }
  cout << (dp[0][W] + dp[0][B]).value() << endl;
  return 0;
}


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

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

	bool flag = true;
	int px = 0, py = 0, pt = 0;
	for (int i = 0; i < N; i++) {
		int t, x, y;
		cin >> t >> x >> y;

		int a = t - pt - abs(x - px) - abs(y - py);
		if (a >= 0 && a % 2 == 0);
		else flag = false;

		px = x; py = y; pt = t;
	}

	cout << (flag ? "Yes" : "No") << endl;

    return 0;
}



Measured memory_bytes: 888
def main():
    H, W = map(int, input().split())
    G = [ input() for _ in range(H) ]

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    for y in range(H):
        for x in range(W):
            flag = True
            if G[y][x] == ".":
                continue

            flag = False

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if nx < 0 or W <= nx or ny < 0 or H <= ny:
                    continue

                if G[ny][nx] == "#":
                    flag = True
                    break

            if not flag:
                print("No")
                return

    print("Yes")

main()


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

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

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

    int seq[N];
    for (int i = 1; i <= N; i++) {
        seq[i - 1] = i;
    }

    int resa, resb;
    int cnt = 1;
    do {
        for (int i = 0; i < N; i++) {
            if (a[i] == seq[i]) {
                if (i == N - 1) {
                    resa = cnt;
                }
            } else {
                break;
            }
        }
        for (int i = 0; i < N; i++) {
            if (b[i] == seq[i]) {
                if (i == N - 1) {
                    resb = cnt;
                }
            } else {
                break;
            }
        }
        cnt++;
    } while (next_permutation(seq, seq + N));

    cout << abs(resa - resb);
}


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

int main()
{
  long a, b, c;
  cin >> a >> b >> c;
  long r = c - a - b;
  bool big = false;
  if(r > 0){
    if((r * r) > (4 * a * b)) big = true;
  }
  if(big) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

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

    vector<int> d(n);
    for(int i=0; i<n; i++){
        cin >> d.at(i);
    }
    sort(d.begin(),d.end());
    d.erase(unique(d.begin(),d.end()), d.end());

    cout << d.size() << endl;
}

Measured memory_bytes: 256
n = int(input().strip())
p = list(map(int, (input().split())))
 
ans = []
 
for i in range(n):
    ans.append(p[i] - (i + 1))
 
ans = list(filter(lambda x: (x != 0), ans))
 
if (len(ans) == 0) or (len(ans) == 2 and sum(ans) == 0):
    print("YES")
else:
    print("NO")

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

int main() {
    /*変数定義，入力*/
    
    ll A;
    char b[4];
    ll result;

    cin >> A >> b[0] >> b[1] >> b[2] >> b[3];
    //rep(i, 4)cout << (int)b[i] << " ";
    
    
    result = (ll) A*(b[0]-48)*100 + A*(b[2]-48)*10 + A*(b[3]-48);
    result = result/100;
    cout << result << endl;
    //printf("%lld\n", result);

    return 0;

}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define Rint register int
using namespace std;
const int N = 203;
int t, n, k, ans; 
int main(){
	scanf("%d", &t);
	while(t --){
		scanf("%d%d", &n, &k);
		while(n % k){
			int b = n / k + 1;
			n -= ((n % k - 1) / b + 1) * b;
		}
		ans ^= n / k;
	}
	puts(ans ? "Takahashi" : "Aoki");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10],A,B,C;
int k[10],u[4],U[4];
int add,ans=2e9+7;

void dfs(int x){
	if(x>n){
		add=0;
		for(int i=1;i<=3;i++) u[i]=0,U[i]=0;
		for(int i=1;i<=n;i++){
			if(k[i]>0) u[k[i]]++,U[k[i]]+=a[i];
		}
		if(u[1]==0||u[2]==0||u[3]==0) return;
		add+=10*(u[1]+u[2]+u[3]-3);
		add+=abs(A-U[1])+abs(B-U[2])+abs(C-U[3]);
		ans=min(ans,add);
		return;
	}
	k[x]=0;dfs(x+1);
	k[x]=1;dfs(x+1);
	k[x]=2;dfs(x+1);
	k[x]=3;dfs(x+1);
}

int main(){
	scanf("%d",&n);
	scanf("%d %d %d",&A,&B,&C);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs(1);
	printf("%d\n",ans);
	
	return 0;
}

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

template <typename InputIterator>
typename InputIterator::value_type summation(InputIterator first,
                                             InputIterator last) {
  return std::accumulate(first, last, typename InputIterator::value_type());
}
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream &operator>>(std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t n, d;
  std::cin >> n >> d;
  std::vector<std::vector<int64_t>> x(n, std::vector<int64_t>(d));
  std::cin >> x;

  int64_t c = 0;

  for (int64_t i = 0; i < n; i++) {
    for (int64_t j = i + 1; j < n; j++) {
      int64_t s = 0;
      for (int64_t k = 0; k < d; k++) {
        s += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
      }

      int64_t ans = static_cast<int64_t>(std::sqrt(s));
      const auto ans1 = ans - 1;
      const auto ans2 = ans + 1;
      if (ans * ans == s || ans1 * ans1 == s || ans2 * ans2 == s) {
        c++;
      }
    }
  }
  std::cout << c << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int mx = 3005;

int n, a[mx];
int vis[mx][mx][2];
long long dp[mx][mx][2];

long long fun(int i, int j, int t){
    if(i > j) return 0;

    long long &ans = dp[i][j][t];
    if(vis[i][j][t]) return ans;
    vis[i][j][t] = 1;

        ans =          a[i] - fun(i+1, j, !t);
        ans = max(ans, a[j] - fun(i, j-1, !t));
    return ans;
}

int main(){

    cin.tie( nullptr );
    ios_base::sync_with_stdio(0);

    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    cout << fun(0, n-1, 0) << "\n";
    return 0;
}


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

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<char>> S(H+2, vector<char>(W+2, '.'));
    for (int i = 1; i < H+1; i++) {
        for (int j = 1; j < W+1; j++) {
            cin >> S[i][j];
        }
    }
    for (int i = 1; i < H+1; i++) {
        for (int j = 1; j < W+1; j++) {
            int cnt = 0;
            if (S[i][j] == '.') {
                if (S[i-1][j-1] == '#')
                    cnt++;
                if (S[i-1][j] == '#')
                    cnt++;
                if (S[i-1][j+1] == '#')
                    cnt++;
                if (S[i][j-1] == '#')
                    cnt++;
                if (S[i][j+1] == '#')
                    cnt++;
                if (S[i+1][j-1] == '#')
                    cnt++;
                if (S[i+1][j] == '#')
                    cnt++;
                if (S[i+1][j+1] == '#')
                    cnt++;
                char num = '0' + cnt;
                S[i][j] = num;
            }
        }
    }
    for (int i = 1; i < H+1; i++) {
        for (int j = 1; j < W+1; j++)
            cout << S[i][j];
        cout << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
   int x,y;
   cin>>x>>y;
   if(x>y&&y!=1){cout<<"Alice"<<endl;}
   else if(y>x&&x!=1){cout<<"Bob"<<endl;}
   else if(x==y){cout<<"Draw"<<endl;}
   else if(x==1&&y!=1){cout<<"Alice"<<endl;}
     else if(y==1&&x!=1){cout<<"Bob"<<endl;}
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

void print_ans(bool flag){
    if(flag){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }   
}

int main(){
    string s;
    cin >> s;
    bool ans = false;
    for(int i = 0; i < s.size(); i++){
        ans |= s[i] == '9';
    }
    print_ans(ans);
    return 0;
}


Measured memory_bytes: 256