akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 1e6 + 55;

int per[20];

int used[20];

int cnt[20];

int dp[30][30];

int c[30][30];

ll f[MAXN], f_inv[MAXN];

ll pow_mod(ll a, ll st){
	ll ans = 1ll;
	for(; st; st /= 2){
		if (st & 1){
			ans = (ans * a) % MOD;
		}
		a = (a * a) % MOD;
	}
	return ans;
}

ll get_c(int i, int j){
	if (i < 0 || j < 0 || j > i){
		return 0ll;
	}
	ll ans = (f[i] * f_inv[j]) % MOD;
	ans = (ans * f_inv[i - j]) % MOD;
	return ans;
}

ll get_v(ll i, ll j){
	return get_c(i - j + 1, j);
}

void solve(){
	int n;
	cin >> n;
	n--;
	int lim = n + 10;
	f[0] = 1;
	REPN(i, 1, lim){
		f[i] = (f[i - 1] * i) % MOD;
	}
	f_inv[lim] = pow_mod(f[lim], MOD - 2);
	for(int i = lim - 1; i >= 0; i--){
		f_inv[i] = (f_inv[i + 1] * (i + 1)) % MOD;
	}
	
	ll ans = 0ll;
	for(int j = n; j >= 0; j--){
		ll v_cur = get_v(n - 2, j);
		ll v_last = get_v(n - 2, j + 1);
		ll cnt_all = v_cur * (n - j) % MOD;
		ll cnt_dif = (v_last * (j + 1)) % MOD;
		ll cur_cnt = (cnt_all - cnt_dif + MOD) % MOD;
		
		//cout << j << " " << v_cur << " " << v_last << " " << cur_cnt << endl;
		ll cur_val = (cur_cnt * f[n - j]) % MOD;
		cur_val = (cur_val * f[j]) % MOD;
		ans = (ans + cur_val) % MOD;
		
		//cout << n - j << " " << cur_val << endl;
	}
	cout << ans << endl;
	
	/*int n = 30;
	dp[0][0] = 1;
	dp[1][0] = dp[1][1] = 1;
	REPN(i, 2, n){
		dp[i][0] = dp[i - 1][0];
		REPN(j, 1, n){
			dp[i][j] = dp[i - 1][j] + dp[i - 2][j - 1];
		}
	}
	REPN(i, 0, n){
		printf("%02d: ", i);
		REPN(j, 0, i){
			printf("%06d ", dp[i][j]);
		}
		putchar('\n');
	}*/
	
	/*int f = 1;
	REPN(n, 2, 11){
		f *= (n - 1);
		int ans = 0;
		REP(i, 0, n - 1){
			per[i] = i;
		}
		REPN(i, 0, n){
			cnt[i] = 0;
		}
		REP(j, 0, f){
			REP(i, 0, n){
				used[i] = 0;
			}
			int cur = 0;
			REP(i, 0, n - 1){
				int ind = per[i];
				if (!used[ind]){
					used[ind] = 1;
					cur++;
				}
				if (!used[ind + 1]){
					used[ind + 1] = 1;
					cur++;
				}
				if (cur == n){
					ans += i + 1;
					cnt[i + 1]++;
					break;
				}
			}
			next_permutation(per, per + n - 1);
		}
		printf("**************\n%d %d\n", n, ans);
		REPN(i, 1, n){
			printf("%d %d\n", i, cnt[i]);
		}
	}*/
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 15872
#include<iostream>
using namespace std;
int main(){
  int Data[50][4]={};
  int mid, fin, re, cnt = 0;
  while(cnt <= 50 && cin >> mid >> fin >> re){

    if(mid == -1 && fin == -1 && re == -1) break;
    Data[cnt][0] = mid;
    Data[cnt][1] = fin;
    Data[cnt][2] = re;
    if(mid == -1 || fin == -1) Data[cnt][3] = 4;
    else if(mid+fin >= 80) Data[cnt][3] = 0;
    else if(65 <= mid+fin && mid+fin < 80) Data[cnt][3] = 1;
    else if(50 <= mid+fin && mid+fin < 65) Data[cnt][3] = 2;
    else if(30 <= mid+fin && mid+fin < 50) {
      if(re >= 50) Data[cnt][3] = 2;
      else Data[cnt][3] = 3;
    }
    else if(mid+fin < 30) Data[cnt][3] = 4;
    cnt++;
  }

  for(int i=0; i<cnt; i++){
    switch(Data[i][3]){
      case 0: cout << "A\n"; break;
      case 1: cout << "B\n"; break;
      case 2: cout << "C\n"; break;
      case 3: cout << "D\n"; break;
      case 4: cout << "F\n"; break;
    }
  }
  return 0;
}



Measured memory_bytes: 3080
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


# aとbの最大公約数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# aとbの最小公倍数
def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def main():
    S = input()

    ans = 0
    for i in range(len(S)):
        for j in range(i + 1, len(S) + 1):
            t = S[i:j]

            ok = True
            for c in t:
                if c not in "ACGT":
                    ok = False
            if ok:
                ans = max(ans, len(t))

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3952
#include <stdio.h>

long long is753(long long n);
long long dfs(long long num);

long long n;
long long dn[] = {7, 5, 3};

long long main()
{

	scanf("%lld", &n);

	printf("%lld\n", dfs(0));

	return 0;
}

long long is753(long long n)
{
	long long cnt[10] = {};

	while (n) {
		cnt[n % 10]++;
		n = n / 10;
	}

	return (cnt[3] && cnt[5] && cnt[7]);
}

long long dfs(long long num)
{
	long long res = 0;

	if (is753(num) && num <= n) {
		res = 1;
	} else if (num > n) {
		return 0;
	}
	
	num = num * 10;
	for (long long i = 0; i < 3; i++) {
		res += dfs(num + dn[i]);
	}

	return res;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
vector<string> t;
string s;
int k;
int main(){
    cin>>s>>k;
    int n = s.size();
    for(int i=0;i<n;i++){
        for(int j=1;j<min(n-i+1,6);j++) t.push_back(s.substr(i,j));
    }
    sort(t.begin(),t.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    cout<<t[k-1]<<'\n';
    return 0;
}


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

bool f(string s){
  int n = s.size();
  bool ans = true;
  for (int i = 0; i < n/2; i++)
  {
    if(s[i]!=s[n-1-i]) ans = false;
  }
  return ans;
}

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

  string s1=s.substr(0,n/2);
  string s2=s.substr(n/2+1,n/2);

  if(f(s)&&f(s1)&&f(s2)) puts("Yes");
  else puts("No");  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int n;
    cin>>n;
    ll a[n];
    rep(i,n)    cin>>a[i];
    ll b[n]={};
    rep(i,n){
        if(i%2==0)  b[0]+=a[n-i-1];
        else    b[0]-=a[n-i-1];
    }
    for(int i=1;i<n;i++)    b[i]=2*a[i-1]-b[i-1];
    rep(i,n)    cout<<b[i]<<' ';
    cout<<endl;
    return 0;
}

Measured memory_bytes: 2816
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    int c=a+b;
    int d=a*b;
    int e=a-b;
    printf("%d\n",max({c,d,e}));
    return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().split())
wlist = []
for i in range(n):
    wlist.append(int(input()))

ma = sum(wlist) + 1
mi = max(wlist) - 1
while (ma - mi > 1):
    mid = (ma + mi)//2
    truck = [0for i in range(k)] ## k개
    i = 0
    gobigger = 0
    for w in wlist:
        if(truck[i] + w <= mid):
            truck[i] = truck[i] + w
        else:
            i = i+1
            if (i == k):
                gobigger = 1
                break
            truck[i] = truck[i] + w
    if (gobigger == 1):
        mi = mid
    else:
        ma = mid
    
print(ma)
        


Measured memory_bytes: 9564
n,c,k = map(int,input().split())
t = list(int(input()) for i in range(n))
t.sort()
ans = 0
x = t[0]
y = 1
for i in range(1,n):
    if x+k < t[i] or y >= c:
        ans += 1
        x = t[i]
        y = 1
    else:
        y += 1
print(ans+1)

Measured memory_bytes: 13308
#include<stdio.h>

int main(){
  int i, j, n, min, v, count = 0;
  int A[100];

  scanf("%d",&n);
  for(i = 0; i < n; i++) scanf("%d",&A[i]);

  for(i = 0; i < n; i++){
    min = i;
    for(j = i; j < n; j++){
      if(A[j] < A[min]) min = j;
    }

    if(i != min){
      v = A[i];
      A[i] = A[min];
      A[min] = v;
      count++;
    }
    printf("%d",A[i]);
    if(i != n - 1) printf(" ");
  }
  printf("\n%d\n",count);

  return 0;
}

Measured memory_bytes: 604
#include <stdio.h>
int main(void)
{
    int a,b[2000],i,j,n=0,m,x,y,z=0;
    char s[100];

    scanf("%d",&a);
    scanf("%s",s);

    for (size_t i = 0; i < a; i++)
    {
      if((s[i]=='A')&&(s[i+1]=='B')&&(s[i+2]=='C')) z++;
    }
    
    printf("%d",z);
    return 0;
}

Measured memory_bytes: 128
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define mod 1000000007
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define Min(a,b) a=min(a,b);
#define ret return puts("-1"),0;
#define N 500055
//#define int ll
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}
int n,m,num[17],cnt[70005],f[70005],x,y,v,a[N],b[N],ans;
vector<int> vec[20];
void dp(int S){
    F(i,0,num[16]) cnt[i]=cnt[i>>1]+(i&1),vec[cnt[i]].push_back(i),f[i]=inf;
    f[S]=0;
    D(i,16,1)
        for (int j=0;j<vec[i].size();j++){
            int s=vec[i][j];
            if (f[s]==inf) continue;
            F(x,0,15)
                F(y,0,15){
                    if (!(s&num[x])||!(s&num[y])||x==y) continue;
                    Min(f[s^num[x]^num[x^y]^num[y]],f[s]+1+((s&num[x^y])>0));
                }
        }
}
signed main(){
	n=read();
	F(i,1,n-1){
		x=read();y=read();v=read();
		a[x]^=v;a[y]^=v;
	}
	F(i,0,n-1) b[a[i]]++;
	F(i,1,15) ans+=b[i]/2;
	num[0]=1;F(i,1,16) num[i]=num[i-1]*2;
	int sum=0;F(i,1,15) sum+=num[i]*(b[i]&1);
	dp(sum);
	wrn(f[0]+ans);
	return 0;
}

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

int main(){
   int N,K; cin >> N >> K;
   vector<int> A(N);
   for(int i=0; i<N; i++){
       cin >> A.at(i);
   } 
    //一度に(K-1)個の要素を最小値(1)にできる
    
    int ans;
    if((N-1)%(K-1) == 0)
        ans = (N-1)/(K-1);
    else
        ans = (N-1)/(K-1)+1;
    
    cout << ans << endl;
}

Measured memory_bytes: 3692
using System;
using System.Text;

public class Test
{
	static public void Main( )
	{
		while( true ) { 
			String[] data = Console.ReadLine().Split( ' ' );
			var H = Int32.Parse( data[0] );
			var W = Int32.Parse( data[1] );
			if( 0 == H && 0 == W ) break;
			
			String w = "";
			for( var i=0; i<152; i++ ) {
				w += "#.";
			}
			StringBuilder output = new StringBuilder();
			for( var i=0; i<H; i++ ) {
				output.Append( w.Substring( (i&1), W ) ).Append( "\n" );
			}
			output.Append( "\n" );
			Console.Write( output );
		}
	}
}

Measured memory_bytes: 5920
#include<iostream>
using namespace std;
int main(){
  
  int in[3][3],out[3][3],time[3][3],second_out,second_in,time_stay;
  
  for(int i=0 ; i < 3 ; i++){
    cin >>in[i][0]>>in[i][1]>>in[i][2];
    cin >>out[i][0]>>out[i][1]>>out[i][2];
  }
  
  for(int i=0 ; i < 3 ; i++){
    second_in=3600*in[i][0]+60*in[i][1]+in[i][2];
    second_out=3600*out[i][0]+60*out[i][1]+out[i][2];
    
    time_stay = second_out - second_in;
    
    time[i][0]=time_stay/3600;
    time_stay=time_stay%3600;
    time[i][1]=time_stay/60;
    time_stay=time_stay%60;
    time[i][2]=time_stay;
  } 
  
  for(int i=0 ; i < 3 ; i++){
    cout <<time[i][0]<<" "<<time[i][1]<<" "<<time[i][2]<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>

int n;
int a[500010];
void f(int i){
	int idx=i;
	if(2*i  <=n&&a[2*i  ]>a[idx])idx=2*i;
	if(2*i+1<=n&&a[2*i+1]>a[idx])idx=2*i+1;
	if(idx!=i){
		int t=a[i];
		a[i]=a[idx];
		a[idx]=t;
		f(idx);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=n;i>0;i--)f(i);
	for(int i=1;i<=n;i++)printf(" %d",a[i]);
	puts("");
}


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

using ll = unsigned long long;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int t;
  cin >> t;
  
  while (t--) {
    ll n, a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    
    map<ll, ll> mp; // number, minimum cost from N
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; // cost, number
    mp[n] = 0;
    mp[0] = 1e18;
    pq.push(make_pair(0, n));
    
    while (!pq.empty()) {
      auto [cost, num] = pq.top();
      pq.pop();
      if (mp[num] < cost || num == 0) continue;
      if (cost >= mp[0]) break;
      
      if (mp[0] > cost + d * num) {
        mp[0] = cost + d * num;
      }
      
      for (auto i : {-1, 0, 1}) {
        if ((num + i) % 2 != 0) continue;
        ll num2 = num + i, cost2 = cost + d * abs(i);
        if (mp.find(num2 / 2) == mp.end()) {
          mp[num2 / 2] = cost2 + a;
          pq.push(make_pair(cost2 + a, num2 / 2));
        }
        else if (mp[num2 / 2] > cost2 + a) {
          mp[num2 / 2] = cost2 + a;
          pq.push(make_pair(cost2 + a, num2 / 2));
        }
      }
      
      for (auto i : {-2, -1, 0, 1, 2}) {
        if ((num + i) % 3 != 0) continue;
        ll num2 = num + i, cost2 = cost + d * abs(i);
        if (mp.find(num2 / 3) == mp.end()) {
          mp[num2 / 3] = cost2 + b;
          pq.push(make_pair(cost2 + b, num2 / 3));
        }
        else if (mp[num2 / 3] > cost2 + b) {
          mp[num2 / 3] = cost2 + b;
          pq.push(make_pair(cost2 + b, num2 / 3));
        }
      }
      
      for (auto i : {-4, -3, -2, -1, 0, 1, 2, 3, 4}) {
        if ((num + i) % 5 != 0) continue;
        ll num2 = num + i, cost2 = cost + d * abs(i);
        if (mp.find(num2 / 5) == mp.end()) {
          mp[num2 / 5] = cost2 + c;
          pq.push(make_pair(cost2 + c, num2 / 5));
        }
        else if (mp[num2 / 5] > cost2 + c) {
          mp[num2 / 5] = cost2 + c;
          pq.push(make_pair(cost2 + c, num2 / 5));
        }
      }
    }
    
    cout << mp[0] << '\n';
  }
}

Measured memory_bytes: 4416
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
ll pret[100005][2], pres[100005][2]; 
int main(){
	fastio;
	string s, t; cin >> s >> t;
	for (ll i = 1; i <= s.length(); i++){
		pres[i][0] = pres[i - 1][0]; pres[i][1] = pres[i - 1][1];
		if (s[i - 1] == 'A') pres[i][0]++; else pres[i][1]++;
	}
	for (ll i = 1; i <= t.length(); i++){
		pret[i][0] = pret[i - 1][0]; pret[i][1] = pret[i - 1][1];
		if (t[i - 1] == 'A') pret[i][0]++; else pret[i][1]++;
	}
	ll q; cin >> q;
	while (q--){
		ll a, b, c, d; cin >> a >> b >> c >> d;
		ll cnta1 = pres[b][0] - pres[a - 1][0], cntb1 = pres[b][1] - pres[a - 1][1];
		ll cnta2 = pret[d][0] - pret[c - 1][0], cntb2 = pret[d][1] - pret[c - 1][1];
		ll cnt1 = 2 * cnta1 + cntb1, cnt2 = 2 * cnta2 + cntb2;
		if ((cnt2 - cnt1) % 3 == 0) cout << "YES\n";
		else cout << "NO\n";
	}
}

Measured memory_bytes: 4048
house = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
n = int(input())
for i in range(n):
    b, f, r, v = map(int, input().split())
    house[b-1][f-1][r-1] += v
for i in range(4):
    for j in range(3):
        for k in range(10):
            print(" " + str(house[i][j][k]), end="")
        print()
    if j == 3 - 1 and i != 4 - 1:
        print("#" * 20)

Measured memory_bytes: 7732
//By Don4ick
#include <bits/stdc++.h>

#define y2 dsfgs

const int N = (int)2005;

using namespace std;

int n, m, q, a[N][N], b[N][N], c[N][N];

int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	ios_base::sync_with_stdio(false);

	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
	{
		string s;

		cin >> s;
		for (int j = 0; j < m; j++)
		{
			if (s[j] == '1')
				a[i][j + 1] = 1;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 2; j <= m; j++)
		{
			b[i][j] += b[i][j - 1];
			if (a[i][j] == 1 && a[i][j - 1] == 1)
				b[i][j]++;			
		}
	}
	for (int i = 2; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			c[i][j] += c[i - 1][j];
			if (a[i][j] == 1 && a[i - 1][j] == 1)
				c[i][j]++;
		}		
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
		}
	}
	while(q--)
	{
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int cnt = 0;
		for (int i = x1; i <= x2; i++)
		{
			cnt += b[i][y2] - b[i][y1];
		}
		for (int i = y1; i <= y2; i++)
		{
			cnt += c[x2][i] - c[x1][i];
		}
		cout << a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1] - cnt << endl;
	}
	return 0;
}



Measured memory_bytes: 48896
use proconio::input;

fn main() {
    input!{
        a:i32,
        b:i32,
        c:i32,
        k:usize,
    };
    let (mut a,mut b,mut c) = (a,b,c);
    let mut cnt = 0 ;
    while a>=b {
        b*=2;
        cnt+=1;
    }
    while b>=c {
        c*=2;
        cnt+=1;
    }
    
    let ans = if cnt<=k { "Yes" } else {"No"};
    println!("{}",ans);
    
    
}



Measured memory_bytes: 2108
#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ll long long 
#define pb push_back
#define mp make_pair
#define pii pair<ll,ll>
#define ff first
#define ss second
#define vi vector<ll>
#define vii vector<vector<ll>>
#define vpi vector<pii>
#define mod 1000000007
#define MOD 1000000007
#define full(a) a.begin(),a.end()
#define inf INT_MAX
#define minf INT_MIN
#define dd double
#define fori(x,n) for(ll i=x;i<n;i++)
#define umap unordered_map<ll,ll>
#define mmap map<ll,ll>
#define mm 998244353

ll power(ll a, ll n,ll m) 
{ 
    if (n == 0) 
        return 1; 
    ll p = power(a, n / 2,m) % m; 
    p = (p * p) % m; 
    if (n & 1) 
        p = (p * a) % m; 
    return p; 
} 


int32_t main() 
{ 
  
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif  
 
    ll t;
    t=1;
    // cin>>t;
    while(t--){
      ll n;
      cin>>n;
      ll maxa=0,mini=1e15;
      ll maxa1 = -1e15,mini1=1e15;

      fori(0,n){
        ll x,y;
        cin>>x>>y;
        maxa = max(maxa,x+y);
        mini = min(mini,x+y);
        maxa1 = max(maxa1,x-y);
        mini1 = min(mini1,x-y);
      }

      cout<<max({maxa1-mini1,maxa-mini});





    }
     
      

      

    

    
return 0;
}     



Measured memory_bytes: 3648
import java.util.*;

public class Main {

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

	class Edge{
		int to;
		int cost;

		Edge(int to, int cost){
			this.to=to;
			this.cost=cost;
		}
	}
	boolean used[];
	boolean ans=true;
	int d[];
	int INF = 10000*2000000+1;
	ArrayList<ArrayList<Edge>> g = new ArrayList<ArrayList<Edge>>();
	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		d = new int[n];
		used = new boolean[n];
		for(int i=0; i<n; i++) g.add(new ArrayList<Edge>());
		for(int i=0; i<n; i++) d[i]=INF;
		for(int i=0; i<m; i++) {
			int l=sc.nextInt();
			int r=sc.nextInt();
			int d=sc.nextInt();
			l--;r--;
			g.get(l).add(new Edge(r,d));
			g.get(r).add(new Edge(l,-d));
		}
		for(int i=0; i<n; i++) {
			if(!used[i]) {
				dfs(i);
			}
		}
		if(ans) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

		sc.close();
	}

	private void dfs(int r) {
		ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
		stack.push(r);
		while(!stack.isEmpty()) {
			int u=stack.pop();
			for(Edge e : g.get(u)) {
				if(!used[e.to]) {
					d[e.to] = d[u]+e.cost;
					used[e.to]=true;
					stack.push(e.to);
				}else {
					if(d[e.to] != d[u]+e.cost) {
						ans = false;
					}
				}
			}
		}
	}
}


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

struct C{char s;int n,o;};

int partition(C c[],int l, int r){
	int x=c[r].n;
	int i=l-1;
	for(int j=l;j<r;j++){
		if(c[j].n<=x){
			i++;
			swap(c[i],c[j]);
		}
	}
	swap(c[i+1],c[r]);
	return i+1;
}

void quickSort(C c[],int l,int r){
	if(l<r){
		int p=partition(c,l,r);
		quickSort(c,l,p-1);
		quickSort(c,p+1,r);
	}
}

bool isStable(int n, C c[]){
	for(int i=1;i<n;i++){
		if(c[i-1].n==c[i].n){
			if(c[i-1].o>c[i].o){
				return false;
			}
		}
	}
	return true;
}

int main(){
	int n;
	cin >> n;
	C c[n];
	for(int i=0;i<n;i++){
		cin >> c[i].s >> c[i].n;
		c[i].o=i;
	}
	quickSort(c,0,n-1);
	if(isStable(n,c)){
		cout << "Stable" << endl;
	}else{
		cout << "Not stable" << endl;
	}
	for(int i=0;i<n;i++){
		cout << c[i].s << " " << c[i].n << endl;
	}
	return 0;
}



Measured memory_bytes: 4280
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main()
{
    long long n;
    cin>>n;
    long long *arr=new long long[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    long long *pre=new long long[n];
    pre[0]=arr[0];
    for(int i=1;i<n;i++)
    {
        pre[i]=(arr[i]+pre[i-1])%mod;
    }
    long long sum=0;
    for(int i=0;i<n-1;i++)
    {
        sum=(sum+(arr[i]*(pre[n-1]-pre[i])))%mod;
    }
    cout<<(sum+mod)%mod<<endl;
}

Measured memory_bytes: 6748
#include <bits/stdc++.h>
using namespace std;
#define ll long long
using  P=pair<ll,ll>;
int main(){
  long double W,H,x,y;
  cin>>W>>H>>x>>y;
  cout<<H*W/2<<" ";
  if(2*x==W && 2*y==H){cout<<1<<endl;}
  else{cout<<0<<endl;}
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,m,i,count=0,shurui=0;
    cin >>n>>m;
    vector <int> a(200000,n+1);
    for(i=0;i<n;i++){
        int x;
        cin >>x;
        if(a[x-1]==n+1){
            a[x-1]=1;
        }else a[x-1]++;
    }
    sort(a.begin(),a.end());
    for(i=0;i<n;i++){
        if(a[i]!=n+1){
            shurui++;
        }else break;
    }
    for(i=0;i<shurui-m;i++){
        count+=a[i];
    }
    cout<<count<<endl;
}

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

int main()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    rep(i, n)
    {
        cin >> a.at(i) >> b.at(i) >> c.at(i);
    }

    // i日目(0<=i<=n)に行動jを取った時の最大値をdp(i, j)とする
    // ただし0日目は0

    vector<vector<int>> dp(n + 1, vector<int>(3));
    rep(j, 3)
    {
        dp.at(0).at(j) = 0;
    }

    rep(i, n)
    {
        dp.at(i + 1).at(0) = max(dp.at(i).at(1), dp.at(i).at(2)) + a.at(i); // i+1日目にAを選ぶ
        dp.at(i + 1).at(1) = max(dp.at(i).at(0), dp.at(i).at(2)) + b.at(i); // i + 1日目にBを選ぶ
        dp.at(i + 1).at(2) = max(dp.at(i).at(0), dp.at(i).at(1)) + c.at(i); // i + 1日目にCを選ぶ
    }
    int ans = max(dp.at(n).at(0), max(dp.at(n).at(1), dp.at(n).at(2))); // 最終日の最大値を調べる
    cout << ans << endl;
}


Measured memory_bytes: 6912
using System;

namespace atcoderA
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int X = int.Parse(Console.ReadLine());
            int A = int.Parse(Console.ReadLine());
            int B = int.Parse(Console.ReadLine());
            int donut = (X - A) / B;
            Console.WriteLine(X - A - B * donut);
        }
    }
}

Measured memory_bytes: 11092
using System;
class Program
{
    static void Main()
    {
        int sec = int.Parse(Console.ReadLine());
        int h = sec/3600;
        int m = (sec-3600*h)/60;
        int s = (sec-3600*h)%60;
        Console.WriteLine("{0}:{1}:{2}",h,m,s);
    }
}

Measured memory_bytes: 9172
//以下のような、たてH cm よこ W cm のチェック柄の長方形を描くプログラムを作成して下さい。
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    for(int i=0;;i++){
      int H = sc.nextInt();
      int W = sc.nextInt();
      int a = W/2;
      int b = W%2;
      if(H == 0 && W == 0) break;
      for(int j=0;j<H;j++){
        if(j%2==0){
          for(int k=0;k<a;k++){
            System.out.printf("#.");
          }
          if(b==1){
            System.out.printf("#\n");
          }else{
            System.out.printf("\n");
          }
        }else{
          for(int k=0;k<a;k++){
            System.out.printf(".#");
          }
          if(b==1){
            System.out.printf(".\n");
          }else{
            System.out.printf("\n");
          }
        }
      }
      System.out.printf("\n");
    }
  }
}



Measured memory_bytes: 54220
// ARC 077E
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
int a[111111],b[111111],e[111111],f[111111];
LL s[222222];
vector<int> B[222222],E[222222];
int main()
{
	int n,m,i,j,x,sf;
	LL ss,ans,k;
	cin>>n>>m;
	for(i=1;i<=n;i=i+1)
		cin>>a[i];
	k=0;
	for(i=1;i<n;i=i+1){
		b[i]=a[i]+1;
		e[i]=a[i+1]+1;
		if(b[i]>e[i])
			e[i]+=m;
		k+=(LL)e[i]-b[i];
		B[b[i]].push_back(i);
		E[e[i]].push_back(i);
	}
	s[1]=0;
	ss=0;
	sf=0;
	for(i=2;i<=m+m+1;i=i+1)
	{
		for(j=0;j<B[i].size();j=j+1){
			x=B[i][j];
			f[x]=1;
			sf++;
			ss+=(LL)b[x]-1;
		}
		for(j=0;j<E[i].size();j=j+1){
			x=E[i][j];
			f[x]=0;
			sf--;
			ss-=(LL)b[x]-1;
		}
		s[i]=(LL)sf*(i-1)-ss;
	}
	ans=0;
	for(i=1;i<=m;i=i+1)
		ans=max(ans,s[i]+s[m+i]);
	cout<<(LL)k-ans<<endl;
	return 0;
}

Measured memory_bytes: 18688
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

void print_vec(std::vector<int> v) {
    for(auto i : v) {
        cout << i;
    }
    cout << endl;
}

int cmp(int a, int b) {
    return a > b;
}

int main() {
    int k, t, a;
    vector<int> vec;
    cin >> k >> t;
    for(int i = 0; i < t; ++i) {
        cin >> a;
        vec.push_back(a);
    }
    sort(vec.begin(), vec.end(), cmp);
    int ret = vec[0] - 1;
    for(int i = 1; i < vec.size(); ++i) {
        if(ret > 0) {
            ret -= vec[i];
        } else {
            break;
        }
    }
    if(ret <= 0) {
        cout << 0 << endl;
    } else {
        cout << ret << endl;
    }
    return 0;
}


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

import sys

DEBUG = False

def read(t):
    return t(sys.stdin.readline().rstrip())


def read_list(t, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]


def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    n, m = read_list(int)
    a = read_list(int)
    work_days = sum(a)
    if work_days > n:
        print("-1")
        return
    print(n - work_days)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9884
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define DBG_N(hoge) cerr<<"!"<<" "<<(hoge)<<endl;
#define DBG cerr<<"!"<<endl;
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;
ll rui[333333];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;cin>>n;
  vi A(n);
  for(int i=0;i<n;i++){
    cin>>A[i];
    rui[i+1]+=rui[i]+A[i];
  }
  ll ans=llINF;
  for(int i=1;i<n;i++){
    ans=min(ans,abs(rui[i]-(rui[n]-rui[i])));
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
    int h,w,a,b;
    cin >> h >> w >> a >> b;
    cout << (h - a) * (w - b) << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		int work,n = sc.nextInt();
		String str;
		int[] s = new int[13];
		int[] h = new int[13];
		int[] c = new int[13];
		int[] d = new int[13];
		for(int i = 0; i < n; i++){
			str = sc.next();
			work = sc.nextInt();
			if(str.equals("S")){
				s[work-1] = 1;
			}else if(str.equals("H")){
				h[work-1] = 1;
			}else if(str.equals("C")){
				c[work-1] = 1;
			}else if(str.equals("D")){
				d[work-1] = 1;
			}
				
		}
		for(int i = 0; i < 13; i++){
			if(s[i] == 0){
				System.out.println("S " + (i+1));
			}
		}
		for(int i = 0; i < 13; i++){
			if(h[i] == 0){
				System.out.println("H " + (i+1));
			}
		}
		for(int i = 0; i < 13; i++){
			if(c[i] == 0){
				System.out.println("C " + (i+1));
			}
		}
		for(int i = 0; i < 13; i++){
			if(d[i] == 0){
				System.out.println("D " + (i+1));
			}
		}
		
	}
}

Measured memory_bytes: 26044
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 _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

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()
    return divisors

N, M = mi()
yakusu = make_divisors(M)
lim = M // N
ind = bisect.bisect_right(yakusu, lim)
ans = 1

print(yakusu[ind-1])

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

#define all(v) v.begin(), v.end()
#define mp make_pair
#define EPS (int)1e-9
#define PI acos(-1)
#define endl '\n'
#define pb push_back
#define fi first
#define se second

using namespace std;
using ld = long double;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 1000000007;


int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, x, fours = 0, evens = 0;
	cin >> n;

	for(int i = 0; i < n; i++)
	{
		cin >> x;

		if(x % 4 == 0)
			fours++;
		else if (x % 2 == 0)
			evens++;
	}

	int need_to_cover = n-(fours*2);

	if(need_to_cover <= 1 or need_to_cover <= evens)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;	
}

Measured memory_bytes: 384
h,w,k = map(int,input().split())
c = []

for i in range(h):
  c.append(input())
ans = 0
for markH in range(2**h):
  for markW in range(2**w):
    black = 0
    for i in range(h):
      for j in range(w):
        if (markH>>i)&1 and (markW>>j)&1 and c[i][j]=="#":
          black +=1
    if black == k:
      ans += 1
print(ans)

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

	using namespace std;
	inline void FAST_IO(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

	int main(){
		FAST_IO();

		int n;
		cin >> n;
		vector<pair<int,int>> in(n);

		for(int i = 0; i < n; ++i){
			int a,b;
			cin >> a >> b;
			in[i] = {b,a};
		}
		sort(in.begin(), in.end());
		
		long long t = 0;
		for(int i = 0; i < n; ++i){
			t+=in[i].second;
			if(t > in[i].first){
				cout << "No" << endl;
				return 0;
			}
		}

		cout << "Yes" << endl;
	
		return 0;
	}

Measured memory_bytes: 1792
#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
using namespace std;

#define TEST 0
#if TEST
FILE* in = freopen("./Q.txt", "r", stdin);
FILE* out = freopen("./A.txt", "w", stdout);
#endif


char s[3] = "([";
char e[3] = ")]";

int main(int argc, const char * argv[]) {
    while(1){
        string line; getline(cin, line);
        if(line == ".") break;
        //cin.ignore();
        
        bool ok = true;
        stack<char> brackets;
        for(int i = 0; i < line.size(); i++){
            for(int j = 0; j < 2; j++){
                if (line[i] == s[j]) {
                    brackets.push(line[i]);
                } else if (line[i] == e[j]){
                    if(brackets.empty()){
                        ok = false;
                    } else {
                        ok = (brackets.top() == s[j]);
                        brackets.pop();
                    }
                }
            }
            if(!ok) break;
        }
        ok &= brackets.empty();
        cout << (ok ? "yes" : "no") << endl;
    }
#if TEST
    fclose(in);
    fclose(out);
#endif
}

Measured memory_bytes: 1180
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int main()
{
    int n,ans,_max,_min,x;
    while(~scanf("%d",&n)){
        _max=0;
        _min=INF;
        ans=0;
        map<int,int>m;
        while(n--){
            scanf("%d",&x);
            _max=max(_max,x);
            _min=min(_min,x);
            m[x]++;
        }
        for(int i=_min;i<=_max;i++)
            ans=max(m[i]+m[i-1]+m[i+1],ans);
        printf("%d\n",ans);
    }
    return 0;
}


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

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

n, k = LI()
a = LI()
a.sort(key = lambda x:abs(x), reverse = True)
ans = 1
p = 0
m = 0
plus = []
minus = []
use = []
f = 0
for i in range(n):
    if a[i] >= 0:
        p += 1
        if i < k:
            plus.append(a[i])
            use.append(a[i])
            ans *= a[i]
            ans %= mod
    else:
        m += 1
        if i < k:
            minus.append(a[i])
            f ^= 1
            use.append(a[i])
            ans *= -a[i]
            ans %= mod
if f:
    ans = -ans
if ans < 0:
    if k == n:
        print(ans % mod)
    elif p == 0:
        a.sort(key = lambda x:abs(x))
        ans = 1
        for i in range(k):
            ans *= -a[i]
            ans %= mod
        if k % 2:
            ans = -ans
        print(ans % mod)
    else:
        for i in range(k, n):
            if a[i] < 0:
                break
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans *= max(a[k:])
            print(ans % mod)
            quit()
        if plus:
            ans = -ans
            ans *= pow(plus[-1], mod-2, mod)
            ans %= mod
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans1 = plus[-1] * max(a[k:])
            ans2 = minus[-1] * min(a[k:])
            print(max(ans1, ans2) * ans % mod)
        else:
            ans = -ans
            ans *= pow(-minus[-1], mod-2, mod)
            ans %= mod
            ans *= max(a[k:])
            print(ans % mod)
else:
    print(ans)


Measured memory_bytes: 131292
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<int>
#define vvint vector<vint>
#define P pair<int,int>
#define INT_MAX 2147483647
#define MOD 1000000007
using namespace std;
typedef long long ll;


int main(void) {
	int a[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
	int k; cin >> k;
	cout << a[k - 1] << endl;
	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define vector2(a,b,c) vector<vector<int>> a(b/*縦！w*/,vector<int>(c/*横！w*/))
#define INF 1e10
#define MOD 1e9+7
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;
struct edge{int from,to,cost;};
signed main(){
  int a,b;
  cin>>a>>b;
  if(!(a==1||b==1)){
  if((a*b)%2==0)
    cout<<a*b/2;
    else
      cout<<a*b/2+1;
    }
  else{
  cout<<1;
  }
    
}


Measured memory_bytes: 256
#20131026

while true
	line = gets.chomp
	break if line == "."
	stack = []
	flag=true
	line.length.times{|index|
		break if !flag
		stack.push line[index] if /["("]|["\["]|["<"]/.match line[index]
		if /[")"]|["\]"]|[">"]/.match line[index]
			str = stack.pop
			flag = false if str == nil
			break if str == nil
			flag = false if !(str.bytes[0] == line[index].bytes[0]-1||str.bytes[0] == line[index].bytes[0]-2)
		end
	}
	flag = false if stack.length != 0
	puts "yes" if flag
	puts "no" if !flag
end

Measured memory_bytes: 6212
local mma = math.max
local t = {}
local tnormal = {}
local tlim = {}
local n, k = io.read("*n", "*n", "*l")
local digmax = 40
local kval = {}
for i = 1, digmax do kval[i] = 0 end
local kdig = 0
do
  local tk = k
  while 0 < tk do
    kdig = kdig + 1
    kval[kdig] = tk % 2
    tk = tk // 2
  end
  if k == 0 then kdig = 1 end
end
for i = 1, digmax do
  t[i], tnormal[i], tlim[i] = 0, 0, 0
end
local str = io.read()
local adigmax = 1
for v in str:gmatch("(%d+)") do
  local a = tonumber(v)
  local adig = 1
  for i = 1, digmax do
    if 0 < a then adig = i end
    t[i] = t[i] + (a % 2)
    a = a // 2
  end
  adigmax = mma(adigmax, adig)
end
digmax = mma(kdig, adigmax)
local mul = 1
for i = 2, digmax do
  mul = mul * 2
end
if kval[digmax] == 0 then
  tlim[digmax] = t[digmax] * mul
  tnormal[digmax] = 0
else
  tlim[digmax] = (n - t[digmax]) * mul
  tnormal[digmax] = t[digmax] * mul
end
mul = mul // 2
for i = digmax - 1, 1, -1 do
  if kval[i] == 0 then
    tlim[i] = tlim[i + 1] + t[i] * mul
    tnormal[i] = tnormal[i + 1] + mma(n - t[i], t[i]) * mul
  else
    tlim[i] = tlim[i + 1] + (n - t[i]) * mul
    tnormal[i] = mma(tlim[i + 1] + t[i] * mul,
                     tnormal[i + 1] + mma(n - t[i], t[i]) * mul)
  end
  mul = mul // 2
end
print(mma(tlim[1], tnormal[1]))


Measured memory_bytes: 5132
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

def binsearch2(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] > threshold:
            right = mid
        else:
            left = mid
    return right

def binsearch1(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if lst[mid] >= threshold:
            right = mid
        else:
            left = mid
    return left

ans = 0
for b in B:
    AtoB = binsearch1(b, A)
    BtoC = binsearch2(b, C)
    ans += (AtoB + 1) * (N - BtoC)
print(ans)

Measured memory_bytes: 23328
#include<stdio.h>
int main(void){
    int c[5];
    while(scanf("%d",&c[0])!=EOF){
        int i,j,n,work,count,flag,flag2=0;

        for(i=1;i<5;i++)scanf(",%d",&c[i]);
        for(i=0;i<4;i++){
            for(j=i+1;j<5;j++){
                if(c[i]>c[j]){
                    work=c[i];
                    c[i]=c[j];
                    c[j]=work;
                }
            }
        }
        count=0;
        flag=0;
        if(c[0]==1 &&c[1]==10){
            flag=1;
            c[0]=9;
        }
        for(i=0;i<4;i++){
            if(c[i]==c[i+1]-1)count++;
        }
        if(count==4)flag2=1;

        if(flag==1)c[0]=1;

        n=0;
        for(i=0;i<4;i++)
            for(j=i+1;j<5;j++)
                if(c[i]==c[j])
                    n++;
        switch( n ){
            case 1:
                puts("one pair");
                break;
            case 2:
                puts("two pair");
                break;
            case 3:
                puts("three card");
                break;
            case 4:
                puts("full house");
                break;
            case 6:
                puts("four card");
            break;
            default:
                if(flag2==1)puts("straight");
                else puts("null");
        }


    }
    return 0;
}

Measured memory_bytes: 580
# coding : utf-8
# Author:Code
S = raw_input()
arr = []
for i in range(4):
    if S[i] not in arr:
        arr.append(S[i])

if len(arr) != 2:
    print "No"
else:
    a = 0
    b = 0
    for i in range(4):
        if S[i] == arr[0]:
            a = a + 1
        elif S[i] == arr[1]:
            b = b + 1
    if a == 2 and b == 2:
        print "Yes"
    else:
        print "No"


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

int main() {
  int n, l;
  cin >> n >> l;
  vector<string> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v.at(i);
  }
  sort(v.begin(), v.end());
  string s = "";
  for (int i = 0; i < n; i++) {
    s += v.at(i);
  }
  cout << s << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll q,a,b;
int main()
{
	scanf("%I64d",&q);
	while(q--)
	{
		scanf("%I64d%I64d",&a,&b);
		if(a==b) {printf("%I64d\n",2*a-2); continue;}
		ll c=(ll)sqrt(a*b);
		if(c*c==a*b) c--;
		if(c*(c+1)<a*b) printf("%I64d\n",2*c-1); else printf("%I64d\n",2*c-2);
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
// static const int max_n = 110;
// static const llong max_cost = 2000000000000000;
// // vector<vector<llong>> matrix(max_n, vector<llong>(max_n, 0));
// // vector<vector<llong>> adj_matrix(max_n, vector<llong>(max_n, max_cost));
// vector<vector<pair<llong, int>>> adj_list(max_n);
// vector<llong> distance_table(max_n, max_cost);
// set<pair<llong, int>> points_sort_x;
// set<pair<llong, int>> points_sort_y;

// int N;



int main(){
    // int u, v;
    // bool updated = false;
    string S;
    cin >> S;
    bool is_ok = false;
    if(S[2]==S[3] && S[4]==S[5]){
        is_ok = true;
    }

    if(is_ok){
        printf("Yes\n");
    }else{
        printf("No\n");
    }


    return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long f,n;
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	f=2;
	for(int i=1;i<=n;i++)
	{
		f=f*2+2;
	}
	cout<<f<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 1e5 + 7;
const int Inf = 1 << 30;
int n;
int a[maxx];
int ans, res;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	if(n == 2) printf("%d %d\n", a[2], a[1]);
	else {
		res = a[n];
		int t1 = a[n] / 2;
		int t2 = a[n] / 2 + 1;
		int min0 = Inf;
		for(int i = 1; i <= n; i++) {
			int tmp = abs(a[i] - t1);
			if(tmp <= min0) {
				min0 = tmp;
				ans = a[i];
			}
		}
		printf("%d %d\n", res, ans);
	}
}

Measured memory_bytes: 640
#define _USE_MATH_DEFINES

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <unordered_set>
#include <queue>
#include <unordered_map>
#include <set>

#pragma GCC optimize("O3")

using namespace std;
using ll = long long;
using ull = unsigned long long;

#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; ++i)
#define repd(i, n) for(ll i = (n) - 1ll; i >= 0; --i)
#define FOR(i, a, b) for(ll i = a; i < ll(b); ++i)
#define FORD(i, a, b) for(ll i = a; i > ll(b); --i)
#define asort(array, size) std::sort(array, array + size)
#define cauto const auto&
#define bit(n) (1LL << (n))

int main()
{
    int x;
    cin >> x;
    cout << (x ? "0" : "1") << endl;
    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>//author::@whohet-->Het Patel
#define fasterthanlight ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define test int T; cin>>T; while(T--)
#define endl "\n"
#define int long long
#define uint unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vvi vector<vector<int>>
#define mii map<int,int>
#define msi map<string,int>
#define mis map<int,string>
#define pb push_back
#define mod 1000000007
#define PI 3.141592653589793238

using namespace std;

//author::@whohet-->Het Patel

signed main()
{
	fasterthanlight;
	string s;
	cin>>s;
	if(s=="ARC")
		cout<<"ABC";
	else
		cout<<"ARC";
	
}


Measured memory_bytes: 3568
#include <stdio.h>


int main() {

  int n,G[101][101];
  int i,j,k,l,u,a,t;


  scanf("%d",&n);

  for(i=0;i<n+1;i++)
    for(j=0;j<n+1;j++) {
      G[i][j] = 0;

    }

  for(i=0;i<n;i++){

    scanf("%d %d ",&k,&u);
    //    printf("u = %d\n",u);

    for(j=0;j<u;j++) {
      scanf("%d",&a);
      G[k -1][a-1] = 1;
      // printf("G[%d][%d] = 1\n",i,k-1);
    }
  }
    
  for(i=0;i<n;i++){
    for(j=0;j<n;j++) {
      printf("%d",G[i][j]);
      if(j != n-1) printf(" ");
    }
    printf("\n");
  }


  return 0;
}


Measured memory_bytes: 2112
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

const int INF = 1e9;
const long long LINF = 1e18;

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

    vector<int> A(N);
    map<int, int> setA;

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        setA[i + 1 - A[i]]++;

        // cout << "setA[ " << i + 1 - A[i] << " ] = " << setA[i + 1 - A[i]] << endl;
    }

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

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 20596