akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
    int w, h, n;
    cin >> w >> h >> n;
    int xmin = 0;
    int xmax = w;
    int ymin = 0;
    int ymax = h;
    for(int i=0; i<n; i++){
        int x,y,a;
        cin >> x >> y >> a;
        if(a == 1){
            xmin = max(xmin, x);
        }else if(a == 2){
            xmax = min(xmax,x);
        }else if(a == 3){
            ymin = max(ymin,y);
        }else if(a == 4){
            ymax = min(ymax,y);
        }
    }
    
    cout << max(0, xmax-xmin)*max(0, ymax-ymin) << endl;
    return 0;
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()
	s := next()
	ans := 0

	for i := 0; i+3 <= n; i++ {
		if s[i:i+3] == "ABC" {
			ans++
		}
	}

	fmt.Println(ans)
}

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

int main() {
    int N, M;
    int num;
    cin >> N >> M;
    for (int i=M/N; i>0; i--) {
        if ((M - N * i) % i == 0) {
            num = i;
            break;
        }
    }
    cout << num << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define mk make_pair

template <class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

void solve()
{
    ll a,b,c;
    cin>>a>>b>>c;
    swap(a,b);
    swap(a,c);
    cout<<a<<" "<<b<<" "<<c<<endl;
}

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

    // ll t;
    // cin >> t;

    // while (t--)
    // {
    //     solve();
    // }
    solve();
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

        int N = sc.nextInt();
        int M = sc.nextInt();
        int ans = 0;

        ans = N * (N - 1) / 2 + M * (M - 1) / 2;

        System.out.println(ans);
    }
}


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

int main() {
  string s;
  cin >> s;
  if(s.at(2) == s.at(3) && s.at(4) == s.at(5)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
n, a, b, k = map(int, input().split())

M = 998244353
fact_n = [0 for m in range(n+1)]
fact_inv = [0 for m in range(n+1)]


def mod_pow(a, n):
    x = 1
    while n > 0:
        if n & 1:
            x = x * a % M

        a = a * a % M
        n >>= 1

    return x


def combination(n, r):
    if n == 0 and r == 0:
        return 1
    elif n < r or n < 0:
        return 0

    return fact_n[n] * fact_inv[r] * fact_inv[n-r] % M


def main():
    fact_n[0] = fact_inv[0] = 1
    for i in range(1, n+1):
        fact_n[i] = fact_n[i-1] * i % M

    fact_inv[n] = pow(fact_n[n], M-2, M)
    for i in range(n-1, 0, -1):
        fact_inv[i] = fact_inv[i+1] * (i+1) % M

    com = 0
    for i in range(n+1):
        if (k-a*i) % b == 0 and k - a * i >= 0:
            j = (k-a*i) // b
            com += combination(n, i) * combination(n, j) % M

    print(com % M)


if __name__ == '__main__':
    main()


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

int main() {

int N;
int D;

cin >> N;
cin >> D;
 
if( N % (1+2*D)==0){
  cout << N / (1+2*D) << endl;
}
  else if (N % (1+2*D)!=0) {
  cout << N / (1+2*D)+1 << endl;
}
}

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

int main(){
  int i,j,cnt=0;
  int n;
  cin>>n;
  int a[n];
  for(i=0;i<n;i++)cin>>a[i];
  for(i=0;i<n;i++)a[i]=2-a[i]%2;
  int prod=1,p3=1;
  for(i=0;i<n;i++){
    prod*=a[i];
    p3*=3;
  }
  cout<<p3-prod;
}

Measured memory_bytes: 256
//2019/3/15
//解説みた
import java.util.Scanner;
public class Main {

	static int N, A, B, C;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();

		A = sc.nextInt();

		B = sc.nextInt();

		C = sc.nextInt();

		int[] l = new int[N];

		for(int i=0;i<N;i++) {

			l[i] = sc.nextInt();
		}
		System.out.println(dfs(0,0,0,0,l));
	}

	static int dfs(int cur, int a, int b, int c, int[] l) {

		if(cur==N) {

			if((Math.min(Math.min(a, b),c)>0))

				return (Math.abs(A-a) + Math.abs(B-b) + Math.abs(C-c) - 30);

			else return 1000000000;
		}

		int res0 = dfs(cur+1,a,b,c,l);

		int res1 = dfs(cur+1,a+l[cur],b,c,l)+10;

		int res2 = dfs(cur+1,a,b+l[cur],c,l)+10;

		int res3 = dfs(cur+1,a,b,c+l[cur],l)+10;

		int min0 = Math.min(res0, res1);

		int min1 = Math.min(res2, res3);

		return Math.min(min0, min1);
	}

}


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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    int ans = 0;
    rep(i,n){
        if((i+1)%2==1 && a[i]%2==1){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	while (true) {
		int n, m;
		int tsum = 0, hsum = 0;
		cin >> n >> m;
		if (n == 0 && m == 0) return 0;
		vector<int>t;
		vector<int>h;
		for (int i = 0; i < n + m; i++) {
			int num;
			cin >> num;
			if (i < n) {
				t.push_back(num);
				tsum += num;
			}
			else {
				h.push_back(num);
				hsum += num;
			}
		}
		sort(t.begin(), t.end());
		sort(h.begin(), h.end());
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if ((tsum-t[i]+h[j])==(hsum-h[j]+t[i])) {
					cout << t[i]<<" "<<h[j] << endl;
					goto e; 
				}
			}
		}
		cout << "-1" << endl;
	e:;
	}
	return 0;
}


Measured memory_bytes: 3056
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int a[10],b[10],c[10];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t;cin>>t;
	int cnt=0;
	while(cnt<2){
		cnt++;
	for(int i=1;i<=t;i++){
		cin>>a[i];
		if(cnt==1) b[i]=a[i];
		c[i]=a[i]; 
		}
	}
	sort(a+1,a+1+t);
	int num1=0,num2=0,ans=0;
	do{
		ans++;
		int flag1=0,flag2=0;
		for(int i=1;i<=t;i++){
			if(a[i]!=b[i]) flag1=1;
			if(a[i]!=c[i]) flag2=1;
		}
		if(flag1==0) num1=ans;
		if(flag2==0) num2=ans;
	}while(next_permutation(a+1, a+t+1));
	cout<<abs(num1-num2)<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep( i, n ) for( int ( i ) = 0; ( i ) < ( n ); ( i )++ )
#define repr( i, n ) for( int ( i ) = ( n ); ( i ) >= 0; ( i )-- )
#define FOR( i, m, n ) for( int ( i ) = ( m ); ( i ) < ( n ); ( i )++ )
#define all( x ) ( x ).begin(), ( x ).end()
typedef long long lint;
using namespace std;

int main( void ){
	
	string str;
	int m;
	int d;
	
	cin >> str;
	
	m = stoi(str.substr(5,2));
	d = stoi(str.substr(8,2));
	
	if( m < 5){
		cout << "Heisei" << endl;
	}else if( m >= 5){
		cout << "TBD" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>
const int oo=2139063143;
const int N=30010000;
const int P=998244353;
using namespace std;
typedef long long LL;
typedef double db;
//char buf[1<<24],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template <typename T>
inline void sc (T &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
template <typename T>
inline void print (T x)
{
	if (x< 0) putchar('-'),x=-x;
	if (x>=10) print(x/10);
	putchar(x%10+'0');
}
template <typename T>
inline void pr (T x) { print(x),putchar('\n'); }
void del(int &x,int y) { x+=y; x=x>=P?x-P:x; }
int ksm (int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) ans=(LL)ans*a%P;
		a=(LL)a*a%P,b>>=1;
	}
	return ans;
}
int jc[N],inv[N];
void init (int n)
{
	jc[0]=1;
	for (int i=1; i<=n; i++)
		jc[i]=(LL)i*jc[i-1]%P;
	inv[n]=ksm (jc[n],P-2);
	for (int i=n-1; i>=0; i--)
		inv[i]=(LL)inv[i+1]*(i+1)%P;
}
int C(int n,int m) { return (n< 0||m< 0||m> n)?0:(LL)jc[n]*inv[m]%P*inv[n-m]%P; }
int T(int n,int m) { return C(n+m-1,m-1); }
int calc (int n,int odd,int sum)
{
	int ans=0;
	for (int i=odd; i>=0; i-=2)
	{
		int las=sum-i;
		int g=(LL)C(n,i)*T(las>>1,n)%P;
		del(ans,g);
	}
	return ans;
}
int main ()
{
	// freopen (".in","r",stdin);
	// freopen (".out","w",stdout);
	int n,m; sc(n),sc(m);
	init (n+m*2);
	int ans=calc (n,m,3*m);
	int g=(LL)n*calc (n,m-1,m-1)%P;
	del(ans,P-g);
	pr(ans);
	return 0;
}


Measured memory_bytes: 18560
N = int(input().strip())
route = [tuple(map(int, input().strip().split(" "))) for i in range(N)]

start = (0, 0, 0)
goal = True

for r in route:
    t = r[0] - start[0]
    d = abs(r[1]-start[1]) + abs(r[2]-start[2])
    if d % 2 == t % 2 and t >= d: # match even/odd and can reach dest in time
        pass
    else:
        goal = False
        break
    start = r

if goal:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 17432
#include<iostream>
#include<numeric>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<climits>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define pll pair<ll,ll>
#define rep(i,from,to) for(int i=from;i<to;i++)
#define repd(i,from,till) for(int i=from;i>=till;i--)
#define waste ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e9+1
#define mod 1e9+7
#define inf1 1e18+1
#define pie 3.14159265358979323846
#define N 100005

using namespace std;

int solve(){
    string s;
    cin>>s;
    rep(i,0,s.length()){
    	if(i%2==1){
    		if(s[i]=='R'){
			cout<<"No"<<endl;
			return 0;
			}		
		}
		else{
			if(s[i]=='L'){
				cout<<"No"<<endl;
				return 0;
			}
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}
int main(){
    waste;
    int t;
    //cin>>t;
    t=1;
    while(t--){
       	solve();
}

    }

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

typedef long long ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int Mx=1e6+11;
const double PI = acos(-1);
#define MOD 1000000007

#define nl '\n'
#define pb push_back
#define F first
#define S second
#define I insert
#define mp make_pair

#define sz(x) x.size()
#define tt int t; cin>>t; while(t--)
#define be(a) (a).begin(),(a).end()
#define rbe(a) (a).rbegin(),(a).rend()
#define mem(a,b) memset(a,b,sizeof(a))
#define yes cout<<"YES"<<nl
#define no cout<<"NO"<<nl

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define frac cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

void solve()
{
  int n,m;
  cin>>n>>m;
  int a[m];
  vi v;
  for(int i=0;i<m;i++)
  {
    cin>>a[i];
  }
  sort(a,a+m);
  for(int i=1;i<m;i++)
  {
    v.pb(a[i]-a[i-1]);
  }
  sort(be(v));
  ll sum=0;
  for(int i=0;i<(m-n);i++)
  {
    sum+=v[i];
  }
  cout<<sum<<nl;
}

int main()
{
    fio;
    solve();
    return 0;
}


Measured memory_bytes: 4220
#include <iostream>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define in(v) cin>>v;
#define out(v) cout<<v<<"\n"

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  string s; in(s);
  int N = s.length();

  int ans = 1e4;
  rep(i, N) {
    string t = s;
    while (true) {
      bool flag = true;
      int N = t.length();
      rep(j, N) {
        if (t[j] != s[i])
          flag = false;
      }
      if (flag) {
        ans = min(ans, (int)(s.length() - t.length()));
        break;
      }
      string t2 = "";
      rep(j, N - 1) {
        if (t[j+1] == t[i])
          t2 += t[j+1];
        else
          t2 += t[j];
      }
      t = t2;
    }
  }
  out(ans);

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define N 300010
using namespace std;
int num[N],sum[N];
int n;
bool check(int x)
{
	int ans=0;
	for(int i=1;i<=n;i+=2)
	if(ans+x<=sum[i]) ans=min(ans,sum[i+1]);
	return x+ans<=sum[n];
}
int main()
{
	scanf("%d",&n);
	int a[2]={0,0};
	for(int i=1;i<=n;i++) scanf("%d",&num[i]),a[i&1]+=num[i];
	if(n&1)
	{
		for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(i&1?1:-1)*num[i];
		int l=0,r=a[0]+a[1],ans=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(check(mid)) l=mid+1,ans=mid;
			else r=mid-1;
		}
		printf("%d %d\n",a[0]+ans,a[1]-ans);
	}
	else printf("%d %d\n",max(a[0],a[1]),min(a[0],a[1]));
	return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#define INF INT_MAX
using namespace std;

int N;
int p[15];
int MAX;
int sum;

int main(){
	cin >> N;
	for (int i = 0; i < N; i++){
		cin >> p[i];
		if (MAX < p[i]){
			MAX = p[i];
		}
		sum += p[i];
	}

	sum = sum - MAX;
	sum += MAX / 2;

	cout << sum << endl;
	
	return 0;
}

Measured memory_bytes: 256
import collections

n = int(input())
v = [ int(i) for i in input().split()]

c1 = collections.Counter(v[::2]).most_common()
c2 = collections.Counter(v[1::2]).most_common()

if c1[0][0] != c2[0][0]:
  ans = n - c1[0][1] - c2[0][1]
elif len(c1) >=2 and len(c2) >= 2:
  if c1[1][1] > c2[1][1]:
    ans = n - c1[1][1] - c2[0][1]
  else:
    ans = n - c1[0][1] - c2[1][1]
elif len(c1) >= 2 and len(c2) == 1:
  ans = n - c1[0][1]
elif len(c1) == 1 and len(c2) >= 2:
  ans = n - c2[0][1]
else:
  ans = n - c1[0][1]

print(ans)

 

    
  

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

using namespace std;

int main() {

	int d, t, s, minute;
	cin >> d >> t >> s;

	if (d % s) {
		minute = d / s + 1;
	}
	else {
		minute = d / s;
	}

	if (minute <= t)
		std::cout << "Yes\n";
	else
		std::cout << "No\n";

	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <class T>
inline bool chmin(T& a, T b) {
   if (a > b) {
      a = b;
      return true;
   }
   return false;
}
template <class T>
inline bool chmax(T& a, T b) {
   if (a < b) {
      a = b;
      return true;
   }
   return false;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;

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

   ll a, b, c, k;
   cin >> a >> b >> c >> k;
   ll ans = 0;
   ans += min(a, k);
   k -= a;
   k -= b;
   if (k > 0) {
      ans -= k;
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 3672
#include <iostream>
#include <set>

#define rep(i,n) for(int i=0; i<(n); ++i)

int main(){
    int n; std::cin >> n;
    std::set<std::string> ss;
    rep(i,n){
        std::string s; std::cin >> s;
        ss.insert(s);
    }
    std::cout << ss.size() << std::endl;
    return 0;
}

Measured memory_bytes: 19176
#include <iostream>
#include <numeric>

int main(){
  
  int N =0;
  std::string S;
  
  std::cin >> N >> S;
  
  // 一つ目の条件が当てはまるものを数える
  long long R = 0;
  long long G = 0;
  long long B = 0;
  for(char c : S){
    if(c == 'R'){
      R++;
    }
    else if(c == 'G'){
      G++;
    }
    else{
      B++;
    }
  }
  long long first_sum = R*G*B;
  
  // 二つ目の対象に当てはまらないものを数える
  long long second_sum = 0;
  
  if( 3 <= N ){
    for(int i = 0; i < N-2; i++){
      for(int j = i+1; j < N-1; j++){
        int k = 2*j-i;
        if( N <= k ){
          continue;
        }
        else if(S.at(i) != S.at(j)){
          if(S.at(i) != S.at(k)){
            if(S.at(j) != S.at(k)){
              second_sum++;
            }
          }
        }
      }
    }
  }
  
  std::cout << first_sum-second_sum << std::endl;
  
  return 0;
}

Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
    int R[MAX], n ;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> R[i];
    }
    
    int maxv = -2000000000; // 十分小さい値を初期値に設定
    int minv = R[0];
    
    for (int i = 1; i < n; i++) { // ここで毎回R[i]を読み込めば、配列は不要
        maxv = max(maxv, R[i] - minv); // 最大値を更新
        minv = min(minv, R[i]); // ここまでの最小値を保持しておく
    }
    
    cout << maxv << endl;
    return 0;
}


Measured memory_bytes: 3872
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
 
N = ii()
A = li()
 
for i in reversed(range(N)):
#for i in reversed(range(N//2)):
    ind = 2*(i+1)
    while(ind-1 < N):
        A[i] ^= A[ind-1]
        ind += i+1
 
print(sum(A))

ans = ''
for i in range(N):
    if A[i] == 1:
        ans += str(i+1) + ' '
if ans != '':
    print(ans[:-1])

Measured memory_bytes: 8600
z = list(map(int, input().split()))
l = list(map(int, input().split()))
count = 0
t = 0
for i in range(0, z[0]+1):
  if (i-1) >= 0:
    count += l[i-1]
  if count <= z[1]:
    t += 1
print(t)



Measured memory_bytes: 2940
#include <iostream>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;

const int N = 100100;
VI edges[N];

ll dp[N];

void dfs(int v, int par) {
  VL ch;
  ll orl = 0;
  for (auto w: edges[v]) {
    if (w == par) { continue; }
    dfs(w, v);
    ch.push_back(dp[w]);
    orl |= dp[w];
  }
  vector<int> hb(64);
  REP(b, 0, 64) {
    int cnt = 0;
    for (ll t: ch) {
      if (t & (1LL << b)) {
	cnt += 1;
      }
    }
    hb[b] = cnt;
  }
  int c = 0;
  REP(b, 0, 64) {
    if (hb[b] >= 2) {
      c = b + 1;
    }
  }
  int t = -1;
  REP(b, c, 64) {
    if (hb[b] == 0) {
      t = b;
      break;
    }
  }
  ll mask = 1LL << t;
  dp[v] = (orl & ~(mask - 1)) | mask;
}

// This was implemented after the author read the editorial.
int main(void){
  int n;
  cin >> n;
  REP(i, 0, n - 1) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  dfs(0, -1);
  int b = 0;
  REP(i, 0, 64) {
    if (dp[0] & 1LL << i) {
      b = i;
    }
  }
  cout << b << endl;
}


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

int n, m;
int s[100005], t[100005];
vector<int> edge[10005], redge[10005];
bool used[10005];
vector<int> ord;
int comp[10005];
set<int> usedin, usedout;

void dfs1(int a){
  if(used[a]) return;
  used[a]=true;
  for(int i=0; i<edge[a].size(); i++)
    dfs1(edge[a][i]);
  ord.push_back(a);
}

void dfs2(int a, int c){
  if(used[a]) return;
  used[a]=true;
  comp[a]=c;
  for(int i=0; i<redge[a].size(); i++)
    dfs2(redge[a][i], c);
}

int main(){
  cin >> n >> m;
  for(int i=0; i<m; i++){
    cin >> s[i] >> t[i];
    edge[s[i]].push_back(t[i]);
    redge[t[i]].push_back(s[i]);
  }
  fill(used, used+n, false);
  for(int i=0; i<n; i++) dfs1(i);
  int cnt=0;
  fill(used, used+n, false);
  for(int i=n-1; i>=0; i--) 
    if(!used[ord[i]]) dfs2(ord[i], cnt++);
//  fill(noin, noin+n, 1);
//  fill(noout, noout+n, 1);
  for(int i=0; i<m; i++){
    if(comp[s[i]]!=comp[t[i]]){
//      noout[comp[s[i]]]=0;
//      noin[comp[t[i]]]=0;
      usedout.insert(comp[s[i]]);
      usedin.insert(comp[t[i]]);
    }
  }
  int ans=0;
  if(cnt>1){
    ans=max(cnt-usedout.size(), cnt-usedin.size());
  }
  cout << ans << endl;
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    int N; cin >> N;
    vector<ll> a(N);
    unordered_map<ll, int> m1, m2;
    rep(i, N) cin >> a[i];
    rep(i, N){
        m1[a[i]] = i;
    }
    sort(all(a));
    rep(i, N){
        m2[a[i]] = i;
    }

    ll res = 0;
    for(auto p: m1){
        if(p.second%2 != m2[p.first]%2) res++;
    }

    cout << res/2 << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 16448
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define rep(i,n) for(int (i) = 0, i_len = n; (i) < (i_len); ++(i))
#define repp(i,n) for(int (i) = 1, i_len = n; (i) <= (i_len); ++(i))
#define per(i,n) for(int (i) = n-1; (i) >= 0; --(i))
#define perr(i,n) for(int (i) = n; (i) > 0; --(i))
#define sz(x) ((int)(x).size())
#define popcnt __builtin_popcount
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).begin(),(v).end(),greater<>()
#define debug(x) cerr << #x << ':' << x << '\n'
#define Pi 3.1415926535
#define MOD 1000000007
using namespace std;
using ll = long long;
using pint = pair<int,int>;
using itn = int;
using vint = vector<int>;
template<class T,class S> inline bool chmax(T& a, S b){if(a<b){a = b; return true;} return false;}
template<class T,class S> inline bool chmin(T& a, S b){if(a>b){a = b; return true;} return false;}
template<class T> T gcd(T a, T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a, T b){return a*b/gcd(a,b);}
void yes(){cout << "Yes" << '\n';}
void no(){cout << "No" << '\n';}

int solve(){
    int a,b,h,m; cin >> a >> b >> h >> m;
    cout << sqrt(a*a + b*b - 2*a*b*cos(abs((2*Pi*h/12+2*Pi*m/60/60*5)-2*Pi*m/60))) << endl;


    return 0;
}

int main(){
    cin.tie(0);
    cout << fixed << setprecision(10);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 4204
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	long long int a=0,b=0,c=0,n=0,ans=0,count=0,h,w ;
	string s;
	vector<int> x;
	cin >>h>>w>> n;
	a = max(h, w);
	ans = n / a;
	if (n % a != 0)ans++;
	
	cout << ans <<endl;
	
}

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

using namespace std;

int main()
{
	stack<int> S;
	int a,b;
	string t;
	while (cin >> t)
	{
		if (t[0] == '+')
		{
			a = S.top(); S.pop();
			b = S.top(); S.pop();
			S.push(a+b);
		}
		else if (t[0] == '-')
		{
			a = S.top(); S.pop();
			b = S.top(); S.pop();
			S.push(b-a);	
		}
		else if (t[0] == '*')
		{
			a = S.top(); S.pop();
			b = S.top(); S.pop();
			S.push(a*b);
		}
		else
			S.push(stoi(t));
	}
	cout << S.top() << endl;
}



Measured memory_bytes: 3180
N, M = map(int, input().split())
a=[]
step=[0]*200000
total=1
count=0
num=0

for i in range(M):
    a.append(int(input()))

for x in range(M):
    num=a[x]-a[x-1]
    if(num==1):
        print(0)
        exit(0)
    else:
        num=0

step[0]=1
for k in range(1,N+1):
    if M!=0:
        if k==a[count]:
            step[k]=0
            if count<M-1:
                    count +=1
        else:
            if k>0:
                step[k]+=step[k-1]
            if k>1:
                step[k]+=step[k-2]
    else:
        if k > 0:
            step[k] += step[k - 1]
        if k > 1:
            step[k] += step[k - 2]



print(step[N]%1000000007)

Measured memory_bytes: 463476
#include <bits/stdc++.h>
#define inar ll ar[n];for(ll i=0;i<n;i++) cin>>ar[i];
#define loop for(ll i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(NULL);
  #define endl "\n"
  #define inf ll(1e19)
  #define mod int(1e9 +7)
typedef long long int ll;
using namespace std;

#define INFI LLONG_MAX
int32_t main()
{
	ll n;
	cin>>n;
	inar
ll sum=0;
for(int i=0;i<n;i++)
sum+=ar[i];
int mp=(sum/n)+(sum%n!=0);
int mp2=(sum/n);
  ll ans=0;
  ll ans2=0;
    for(int i=0;i<n;i++)
    {
		ans+=(abs(ar[i]-mp)*abs(ar[i]-mp));
		ans2+=(abs(ar[i]-mp2)*abs(ar[i]-mp2));
}
cout<<min(ans,ans2);
}


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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define wait(sec) usleep((sec) * 1000000)
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main(){
//    random_device rnd;
//    mt19937 mt(rnd());
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if(a % b == 0){
        cout << 0 << endl;
    }
    else{
        cout << 1 << endl;
    }
}


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

// why am I so weak

int n;
int a[100055];
int dp[100055];
vector<int> g[100055];

void dfs(int v, int par = -1) {
	vector<int> vec;
	for (auto u : g[v]) {
		dfs(u);
		vec.push_back(dp[u] + 1);
	}

	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());

	for (int i = 0; i < (int)vec.size(); i++) {
		dp[v] = max(dp[v], vec[i] + i);
	}
}
int main() {
	scanf("%d", &n);

	for (int i = 1; i < n; i++) {
		scanf("%d", &a[i]);
		g[--a[i]].push_back(i);
	}

	dfs(0);

	printf("%d\n", dp[0]);

	return 0;
}


Measured memory_bytes: 15872
package main

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

type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func main() {
	sc := NewScanner()
	N, K := sc.nextFloat(), sc.nextFloat()
	var ans float64 = 0
	var p float64
	for p = 1; p <= N; p++ {
		point := p
		val := 1 / N
		var count float64 = 0
		var m float64 = 1
		for {
			if point*m >= K {
				break
			}
			m *= 2
			count++
		}
		ans += val * 1 / (math.Pow(2, count))
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MOD 1000000007

void solve()
{
	ll x;
	cin>>x;
	if(x<1200)
		cout<<"ABC";
	else
		cout<<"ARC";
	return;
}

int main()
{
	fast;
	ll q=1;
	// cin>>q;
	while(q--)
		solve();
	return 0;
}



Measured memory_bytes: 3620
n=int(input())
a=list(map(int,input().split()))
import collections

c=collections.Counter(a)
d={}
for i in c:
    if c[i]>1:
        d.setdefault(i,c[i])
e=sorted(d,reverse=True)
if len(e)>1:
    if d[e[0]]>3:
        print(e[0]**2)
    else:
        print(e[0]*e[1])
else:
    print(0)

Measured memory_bytes: 18216
#include<iostream>
#include<vector>
#include<utility>
using namespace std; 
typedef long long ll;
typedef pair<int,int> T;
vector<T> v[200000];
ll ans[200000];
void dfs(int from,int now,ll cost){
    ans[now] = cost;
    //cout << from << " " << now << " " << cost << endl;
    for(int i=0;i<v[now].size();i++){
        if(v[now][i].first == from)continue;
        ll cost2 = cost + (ll)v[now][i].second;
        dfs(now,v[now][i].first,cost2);
    }
}

int main(){
    int n;cin >> n;
    for(int i=0;i<n-1;i++){
        int a,b,c;cin >> a >>b >> c;
        a--;b--;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    //cout << "a" << endl;
    int q,k;cin >> q >> k;
    k --;
    dfs(k,k,0);
    for(int i=0;i<q;i++){
        int x,y;cin >> x >> y;x--;y--;
        cout << ans[x] + ans[y] << endl;
    }
    return 0;
}

Measured memory_bytes: 16640
#include <iostream>

int main()
{
    int a, b;
    char op;

    while (std::cin >> a >> op >> b)
    {
        int x;

        if (op == '?') break;

        switch (op)
        {
            case '+':
                x = a + b;
                break;
            case '-':
                x = a - b;
                break;
            case '*':
                x = a * b;
                break;
            case '/':
                x = a / b;
                break;
            default:
                break;
        }

        std::cout << x << std::endl;

    }

    return 0;
}



Measured memory_bytes: 3108
//yukicoder@cpp14
//author:luckYrat(twitter:@luckYrat_)
//競技プログラミングから逃げるな
//https://www.youtube.com/watch?v=z_B9iJ8r4ic

//せんげん！
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <bitset>

#include <cctype>
#include <utility>
#include <climits>


//なまえくーかん！
using namespace std;
using ll = long long;
using P = pair<ll,ll>;

//てーすう！
const int mod = 1000000007;
const int inf = (1<<30)-1;
const ll linf = (1LL<<62LL)-1;
const double EPS = (1e-10);

//でふぁいん！
#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)

//みじかく！
#define pb push_back
#define fir first
#define scn second
#define ednl endl

//いぇすのー！
#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")

//きんぼーnほーこー！！
P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる

計算量は変わらないが楽できるシリーズ
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる
*/
int dp[2][2020];
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
int main(){
  string s;cin>>s;
  int ans = 0;
  for(int i = 0; s.size() > i; i++){
    dp[0][0] += 1;
    for(int j = 0; 2020 > j; j++){
      dp[1][(j*10+s[i]-'0')%2019] += dp[0][j];
    }
    ans += dp[0][0];
    for(int j = 0; 2020 > j; j++){
      dp[0][j] = dp[1][j];
      dp[1][j] = 0;
    }
  }
  ans += dp[0][0];
  cout << ans-s.size() << endl;

}


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

using namespace std;

typedef long long ll;

ll C[55][55];

int main()
{
	int n, s, a0 = 0, a1 = 0;
	scanf("%d%d", &n, &s);
	for(int i = 0; i <= 50; i++)
		for(int j = 0; j <= 50; j++) C[i][j] = !j ? 1 : C[i - 1][j - 1] + C[i - 1][j];
	for(int i = 1; i <= n; i++) {
		int a;
		scanf("%d", &a);
		if(a & 1) a1++; else a0++;
	}
	ll ans = 0;
	if(a1 == 0) printf("%lld\n", s == 0 ? 1ll << a0 : 0); else printf("%lld\n", 1ll << (a0 + a1 - 1));
	return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log,pi
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？


n=ii()
arr=limii()
ans=[0]*n
for i in arr:
    ans[i-1]+=1
for i in ans:
    print(i)




Measured memory_bytes: 94980
#include<stdio.h>
int main()
{
  int x,y,i,stack,Max;

  scanf("%d%d",&x,&y);
  
  if(x > y){
    stack = x;
    x = y;
    y = stack;
  }
  while(1){
    if(y%x==0){
      Max = x;
      break;
    }
    else{
      stack = x;
      x = y%x;
      y = stack;
    }
}
  printf("%d\n",Max);
}



Measured memory_bytes: 2140
import java.util.Scanner;

public class Main {
	public int[] v;
	public int[] w;
	public int wMax;
	public int n;
	public int[][] memo;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int iocase = 1;
		Main m = new Main();
		m.wMax = sc.nextInt();
		while(m.wMax != 0){
			m.n = sc.nextInt();
			m.memo = new int[m.n + 1][m.wMax + 1];
			m.v = new int[m.n];
			m.w = new int[m.n];
			sc.nextLine();
			for(int i = 0; i < m.n; i++){
				String str = sc.nextLine();
				String[] split = str.split(",");
				m.v[i] = Integer.parseInt(split[0]);
				m.w[i] = Integer.parseInt(split[1]);
			}
			int max = 0;
			for(int i = m.n - 1; i >= 0; i--){
				for(int j = 0; j <= m.wMax; j++){
					if(j + m.w[i] > m.wMax){
						m.memo[i][j] = m.memo[i + 1][j];
					}else{
						m.memo[i][j] = Math.max(m.memo[i + 1][j], m.memo[i + 1][j + m.w[i]] + m.v[i]);
					}
				}
			}
			System.out.println("Case " + iocase +":");
			System.out.println("" + m.memo[0][0]);
			for(int i = 0; i < m.wMax; i++){
				if(m.memo[0][0] != m.memo[0][i + 1]){
					System.out.println("" + (m.wMax - i));
					break;
				}
			}
			iocase++;
			m.wMax = sc.nextInt();
		}
		
		sc.close();
	}
}

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

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pct __builtin_popcount

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

#define N 1010
int n, m;
string a[N];
int d[N][N];
queue<PII> q;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i ++) cin >> a[i];
	for (int i = 0; i < n; i ++)
		for (int j = 0; j < m; j ++) {
			if (a[i][j] == '#') {
				q.push(mp(i, j));
			} else {
				d[i][j] = -1;
			}
		}
	while (!q.empty()) {
		PII _x = q.front(); q.pop();
		int x = _x.fi, y = _x.se;
		for (int dd = 0; dd < 4; dd ++) {
			int xx = x+dx[dd], yy = y+dy[dd];
			if (0 <= xx && xx < n && 0 <= yy && yy < m && d[xx][yy] == -1) {
				d[xx][yy] = d[x][y] + 1;
				q.push(mp(xx, yy));
			}
		}
	}
	int S = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j ++) S = max(S, d[i][j]);
	cout << S << endl;
	return 0;
}


Measured memory_bytes: 10112
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

import numpy as np

N = int(readline())
A = np.array(readline().split(),np.int32)

def test(x):
    # 答はx以上
    B = (A >= x)
    # 連番の左側にフラグを立てる
    flag = np.zeros(N+N-1,np.bool)
    flag[:-1] = (B[:-1] == B[1:])
    # 最寄りの連番を探す
    """ version違いでボツ
    L = np.where(flag[:N])[0].max(initial=-1) + 1
    R = np.where(flag[N-1:-1])[0].min(initial=N-1) + N - 1
    """
    x = np.where(flag[:N])[0]
    L = x.max() + 1 if len(x) >= 1 else 0
    x = np.where(flag[N-1:-1])[0]
    R = x.min() + N - 1 if len(x) >= 1 else N+N-2
    if (N-1)-L > R-(N-1):
        return B[R]
    else:
        return B[L]

left = 0 # 答はleft以上
right = N+N+10 # 答はright未満
while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        left = mid
    else:
        right = mid
answer = left
print(answer)

Measured memory_bytes: 31432
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  string s;
  int cnt=0,N;
  cin>>N>>s;
  for(int i=0;i<N-1;i++){
    if(s[i]!=s[i+1]) cnt++;
  }
  cout<<cnt+1<<endl;
}	


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;

#define ASC(a) a.begin(), a.end()		// 昇順ソート 例：sort(ASC(a));
#define DESC(a) a.rbegin(), a.rend()	// 降順ソート 例:sort(DESC(a));
#define rep(i, n) for(int i = 0; i < n; ++i)
//#define rep(i, a, n) for(int i = a; i < n; ++i)
#define Rep(i, n) for(int i = 1; i < n; ++i)
#define In(a) rep(i, n) cin>>a[i];
#define ANS(s) cout << s << endl
#define inc(a, b) cin >> a >> b;
#define only_unique(vec) vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
#define souwa(vec) accumulate(ASC(vec), 0)

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

typedef long long ll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }


// 4,8方向に探索する際に用いる配列
//int dx[4] = { 0,  0, 1, -1 };
//int dy[4] = { 1, -1, 0,  0 };
//int dx[8] = { 1, 0, -1,  0, 1, -1, -1,  1 };
//int dy[8] = { 0, 1,  0, -1, 1,  1, -1, -1 };


// ────────────────────────────────────────────────────
int  main() {
	while (1) {
		int n; cin >> n;
		if (!n) break;
		
		vi s(n), p(n), q(n), r(n);
		rep(i, n) cin >> s[i] >> p[i] >> q[i] >> r[i];
		int P, Q, R, C; cin >> P >> Q >> R >> C;

		vi ans;
		rep(i, n) {
			if (p[i] <= P && q[i] <= Q && r[i] <= R) {
				int tmp = p[i] * 4 + q[i] * 9 + r[i] * 4;
				if (tmp <= C) {
					ans.push_back(s[i]);
				}
			}
		}
		if (!ans.size()) cout << "NA" << endl;
		else {
			rep(i, ans.size()) {
				cout << ans[i] << endl;
			}
		}
	}
}



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

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

    vector <set <int>> st(26), ts(26);
    rep (i, s.size()) {
        st[s[i] - 'a'].insert(t[i]);
        ts[t[i] - 'a'].insert(s[i]);
    }

    bool ans = true;
    rep (i, 26) ans &= st[i].size() < 2;
    rep (i, 26) ans &= ts[i].size() < 2;
    cout << (ans ? "Yes" : "No") << endl;

    return 0;
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int s, d, m;
int k[303];
int w[303][303], p[303][303];
int f[303];

int dp[303][303];
int dp2[303][303];

signed main(){
  while(cin >> s >> d >> m) {
    rep(i, s) {
      cin >> k[i];
      rep(j, k[i]) cin >> w[i][j] >> p[i][j];
      //rep(j, k[i]) cout<<w[i][j]<<"-"<<p[i][j]<<endl;
    }
    rep(i, d) cin >> f[i];
    memset(dp, -1, sizeof(dp));
    rep(i, s) {
      dp[i][0] = 0;
      rep(j, k[i]) {
	for(int l = m; l >= p[i][j]; l--) {
	  if(dp[i][l-p[i][j]] == -1) continue;
	  dp[i][l] = max(dp[i][l], dp[i][l-p[i][j]] + w[i][j]);
	}
      }
      //for(int j=0;j<=m;j++) cout<<j<<":"<<dp[i][j]<<endl;
    }
    memset(dp2, -1, sizeof(dp2));
    dp2[0][0] = 0;
    rep(i, d) {
      //cout<<i<<":"<<f[i]<<endl;
      //rep(j, m+1) {
      for(int j = m; j >= 0; j--) {
	for(int l = m; l >= j; l--) {
	  if(dp2[i][l-j] == -1 || dp[f[i]][j] == -1) continue;
	  dp2[i+1][l] = max(dp2[i+1][l], dp2[i][l-j] + dp[f[i]][j]);
	}
      }
    }
    int ansp, answ = -1;
    rep(i, m+1) {
      //cout << i << " "<<dp2[i]<<endl;
      if(answ < dp2[d][i]) {
	answ = dp2[d][i];
	ansp = i;
      }
    }
    cout << answ << " " << ansp << endl;
  }
  
  return 0;
}

Measured memory_bytes: 4960
#include <iostream>

using namespace std;

int main()
{
    string k;
    cin>>k;
    int counter = 0;
    int upper = 0;
    int cc = 0;
    for(int i = 2 ; i < k.size();i++)
    {
        if(k[i]=='C')
        {
            counter++;
            cc = i;
        }
    }
    for(int i = 0 ; i < k.size();i++)
    {
        if (isupper(k[i]))
        {
            upper++;
        }
    }
    if(counter == 1 && k[0]=='A' && islower(k[1]) && upper == 2&& cc != k.size()-1)
    {
        cout<<"AC"<<endl;
    }
    else if (k[1]== 'c'|| k[1]=='C')
    {
        cout<<"WA"<<endl;
    }
    else
    {
        cout<<"WA"<<endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int K, A, B;
  cin >> K >> A >> B;
  
  for (int i = A; i <= B; i++) {
    if(i % K == 0) {
        cout << "OK" << endl;
        break;
    }
    if(i == B) {
        cout << "NG" << endl;
    }
  }
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int a[N+5];
int main(){
	int n,k,maxx=0;
	scanf("%d%d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
		maxx=max(maxx,a[i]);
	}
	int g=__gcd(a[0],a[1]);
	for(int i=1;i<n;i++){
		g=__gcd(g,a[i]);
	}
	if(maxx>=k&&k%g==0)printf("POSSIBLE\n");
	else printf("IMPOSSIBLE\n");
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<climits>
#include<set>
#include<map>
#include<stack>
#define ll long long
using namespace std;

int main() {
    vector<vector<ll>> c(3, vector<ll>(3));
    vector<ll> sa(3), sb(3);
    for (ll i = 0; i < 3; i++)
    {
        for (ll j = 0; j < 3;j++){
            cin >> c[i][j];
        }
    }
    ll sa1 = c[0][0] - c[1][0];
    ll sa2 = c[1][0] - c[2][0];
    ll sb1 = c[0][0] - c[0][1];
    ll sb2 = c[0][1] - c[0][2];
    for (ll i = 0; i < 3; i++)
    {
        if(c[i][0]-c[i][1]!=sb1){
            cout << "No" << endl;
            exit(0);
        }
        if (c[i][1] - c[i][2] != sb2)
        {
            cout << "No" << endl;
            exit(0);
        }
    }
    for (ll j = 0; j < 3; j++)
    {
        if (c[0][j] - c[1][j] != sa1)
        {
            cout << "No" << endl;
            exit(0);
        }
        if (c[1][j] - c[2][j] != sa2)
        {
            cout << "No" << endl;
            exit(0);
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
from collections import defaultdict


def factorize(n: int) -> dict:
    f = defaultdict(int)
    while n % 2 == 0:
        f[2] += 1
        n //= 2
    p = 3
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 2
    if n != 1:
        f[n] += 1
    return f


MOD = 10**9 + 7
n = int(input())
a = tuple(map(int, input().split()))

MAX_a = max(a)
iinv = [1] * (MAX_a + 1)
for i in range(2, MAX_a + 1):
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD

a_fac = []
lcm_fac = defaultdict(int)
for a_i in a:
    a_fac_i = factorize(a_i)
    a_fac.append(a_fac_i)
    for k, v in a_fac_i.items():
        lcm_fac[k] = max(lcm_fac[k], v)

lcm = 1
for k, v in lcm_fac.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD

ans = 0
for i in range(n):
    ans += lcm * iinv[a[i]]
    ans %= MOD

print(ans)


Measured memory_bytes: 47104
#include <stdio.h>
#include <stdlib.h>

//降順
int compare(const void *a, const void *b){
  return *(int *)b - *(int *)a;
}

int main(){
  int N, K;
  int l[60] = {};
  int l_tot = 0;
  scanf("%d%d", &N, &K);
  for(int i = 0; i < N; i++){
    scanf("%d", &l[i]);
  }
  qsort(l, N, sizeof(int), compare);
  for(int i = 0; i < K; i++){
    l_tot += l[i];
  }
  printf("%d\n", l_tot);
  return 0;
}


Measured memory_bytes: 128
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(buf.readLine());
        StringBuilder sb = new StringBuilder();

        int num = 0;
        for(int j=3; j<=n; j++){
            if(j%3==0){
                sb.append(" "+j);
            } else {
                num = j;
                while(num != 0){
                    if(num%10==3){
                        sb.append(" "+j);
                        break;
                    } else{
                        num = num/10;
                    }
                }
            }

        }
        System.out.println(sb);
    }
}

Measured memory_bytes: 26200