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

// Define
using ll = int64_t;
using ul = uint64_t;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ul MAX = ULONG_MAX;
const char nl = '\n';

#define elif else if
#define def inline auto
#define run __attribute__((constructor)) def _

// Debug
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i < _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i > _##i; --i)
#define rep(i, n) inc(i, 0, n)
#define be(c) begin(c), end(c)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("-O3")
#pragma GCC target("avx")

signed main() {
    int n, m;
    cin >> n >> m;
    using pii = pair<int, int>;
    vector<pii> pis(n);
    for(auto& e: pis) {
        cin >> e.first >> e.second;
    }
    sort(be(pis));
    ll ans = 0;
    int bought = 0;
    rep(i, n) {
        auto& e = pis[i];
        auto b = min(m - bought, e.second);
        ans += (ll)e.first*b;
        bought += b;
        if (bought == m) break;
    }
    cout << ans << nl;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 2000009
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
#define calc(sx,sy,tx,ty) cbn((tx)+(ty)-(sx)-(sy),(tx)-(sx))
using namespace std;

int x[3][2],y[3][2],fac[N],inv[N];
int solve(int sx,int sy,int tx,int ty){
	int i,l=x[1][0],r=x[1][1],u=y[1][0],v=y[1][1]; ll ans=0;
	for (i=l; i<=r; i++){
		ans+=(ll)(v+i+1)*calc(sx,sy,i,v)%mod*calc(i,v+1,tx,ty)%mod;
		ans-=(ll)(u+i)*calc(sx,sy,i,u-1)%mod*calc(i,u,tx,ty)%mod;
	}
	for (i=u; i<=v; i++){
		ans+=(ll)(r+i+1)*calc(sx,sy,r,i)%mod*calc(r+1,i,tx,ty)%mod;
		ans-=(ll)(l+i)*calc(sx,sy,l-1,i)%mod*calc(l,i,tx,ty)%mod;
	}
	return ans%mod;
}
int main(){
	int i,j,k,l; ll ans=0;
	for (i=0; i<3; i++)
		for (j=0; j<2; j++) scanf("%d",&x[i][j]);
	for (i=0; i<3; i++)
		for (j=0; j<2; j++) scanf("%d",&y[i][j]);
	fac[0]=inv[0]=inv[1]=1;
	for (i=1; i<N; i++) fac[i]=(ll)fac[i-1]*i%mod;
	for (i=2; i<N; i++) inv[i]=mod-(ll)inv[mod%i]*(mod/i)%mod;
	for (i=2; i<N; i++) inv[i]=(ll)inv[i-1]*inv[i]%mod;
	x[0][0]--; x[2][1]++;
	y[0][0]--; y[2][1]++;
	for (i=0; i<2; i++)
		for (j=0; j<2; j++)
			for (k=0; k<2; k++)
				for (l=0; l<2; l++)
					ans+=solve(x[0][i],y[0][j],x[2][k],y[2][l])*((i+j+k+l&1)?-1:1);
	printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}


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

void solve(long long N){
    vector<long long> ans(N+1);
    ans[0] = 2; ans[1] = 1;
    for(int i=2; i<=N; i++) {
        ans[i] = ans[i-1] + ans[i-2];
    }
    cout << ans[N] << endl;
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


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

using namespace std;

int main(void)
{
  string S;
  cin >> S;
  stack<char>v;
  int c = 0;
  for(int i=0;i<S.length();i++){
    if(v.empty())
      v.push(S[i]);
    else{
      if(S[i]!=v.top()){
        c+=2;
        v.pop();
      } else{
        v.push(S[i]);
      }
    }
  }
  cout << c;
  return 0;
}

Measured memory_bytes: 512
import std.stdio; // readln
import std.array; // split
import std.conv; // to
import std.typecons;

bool[][] g;

void main(){
	string[] s = split(readln());
	int N = to!int(s[0]);
	int M = to!int(s[1]);
	g = new bool[][](N,N);

	alias Tuple!(int,int) pair;
	pair[] p = new pair[](M);
	for(int i = 0; i < M; i++){
		s = split(readln());
		int a = to!int(s[0]);
		int b = to!int(s[1]);
		a--; b--;

		p[i] = pair(a,b);
		g[a][b] = g[b][a] = true;
	}

	int cnt = 0;
	for(int i = 0; i < M; i++){
		bool[] used = new bool[](N);
		foreach (ref elem; used) {
			elem = false;
		}

		g[p[i][0]][p[i][1]] = g[p[i][1]][p[i][0]] = 0;
		dfs(0,used);
		g[p[i][0]][p[i][1]] = g[p[i][1]][p[i][0]] = 1;
		if(!check(used)){
			cnt++;
		}
	}

	writeln(cnt);
}

void dfs(int cur, bool[] used){
	used[cur] = true;
	for(int i = 0; i < g.length; i++){
		if(g[cur][i] && !used[i]){
			dfs(i, used);
		}
	}
}

bool check(bool[] used){
	for(int i = 0; i < used.length; i++){
		if(!used[i]) return false;
	}
	return true;
}


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

long long f[100005];
int main() {
	int n, W;
	scanf("%d%d",&n, &W);
	while (n--) {
		int w, v;
		scanf("%d%d", &w, &v);
		for (int i=W-w; i>=0; i--) f[i+w]=max(f[i+w], f[i]+v);
	}
	printf("%lld\n", f[W]);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 998244353
using namespace std;
int main() {
    long double a, b, c;
    cin >> a >> b >> c;
    long double d = 0.00000000000001;
    if(sqrtl(a) + sqrtl(b) + d < sqrtl(c)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct tree{
    size_t n,r,md;
    vector<vector<int>> e;
    vector<int> pa,d;
    explicit tree(int n_){
        n=n_;
        e.resize(n);
    }
    void add(int a,int b){
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    void r_dfs(int i,int p=-1,int D=0){
        pa[i]=p;d[i]=D;md=max(md,(size_t)D);++D;
        for(auto j:e[i]) if(j!=p) r_dfs(j,i,D);
    }
    void r_i(int r_){
        pa.resize(n);d.resize(n);r=r_;md=0;
        r_dfs(r);
    }
    int r2(){
        r_i(0);
        int m=0,M=0;
        fr(i,n) m=max(m,d[i]);
        fr(i,n) if(d[i]==m) M=i;
        pa.clear(),d.clear();
        r_i(M);
        m=0;
        fr(i,n) m=max(m,d[i]);
        return m;
    }
    void f(vector<bool>&vis,int u,int v){
        if(d[u]<d[v]) swap(u,v);
        while(d[u]>d[v]){
            vis[u]=true;
            u=pa[u];
        }
        while(u!=v){
            vis[u]=true;
            vis[v]=true;
            u=pa[u];
            v=pa[v];
        }
    }
};

vector<ll> p2(50,1);

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    fr(i,49) p2[i+1]=p2[i]*2;
    int n,m,a,b;
    in>>n;
    tree t(n);
    fr(i,n-1){
        in>>a>>b;
        --a,--b;
        t.add(a,b);
    }
    in>>m;
    vector<int> u(m),v(m);
    fr(i,m) in>>u[i]>>v[i],--u[i],--v[i];
    ll ans{};
    t.r_i(0);
    fr(d,(1<<m)){
        int c=__builtin_popcount(d);
        vector<bool> vis(n);
        fr(i,m) if((d>>i)&1){
            t.f(vis,u[i],v[i]);
        }
        int cnt{};
        Fr(i,n-1) if(!vis[i]) ++cnt;
        if(c&1) ans-=p2[cnt];
        else ans+=p2[cnt];
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int_inf 1000000000 //1e9
#define ll_inf  1000000000000000000 //1e18

using namespace std;

int main(){
	int n; cin>>n;
	double x;	string u;
	double ans=0;
	
	for(int i=0; i<n; i++){
		cin>>x>>u;
		if(u=="BTC") x*=380000;
		ans+=x;
	}
	cout<<ans<<endl;	
	
	
	return 0;
}




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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

ll f(ll x) {
    ll cnt = (x + 1) / 2;
    if ((x + 1) % 2) {
        return cnt % 2 + x;
    } else {
        return cnt % 2;
    }
}

void Main() {
    ll A, B;
    cin >> A >> B;
    cout << (f(A - 1) ^ f(B)) << '\n';
}

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


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

int main() {
	int n;
	cin >> n;
	string s[n];
	for(int i=0;i<n;i++){
		cin >> s[i];
	}
	
	bool rule = true;
	
	for(int i=0;i<n;i++){
		if(rule == true){
			for(int j=0;j<i;j++){
				if(s[i]==s[j]){
					cout << "No" << endl;
					rule = false;
					break;
				}
			}
		}
	}

	for(int i=0;i<n-1;i++){
		if(rule==true){
			char last = s[i][s[i].length() -1];
			if(last != s[i+1][0]){
				cout << "No" << endl;
				rule = false;
				break;
			}
		}
	}
	
	if(rule == true){
		cout << "Yes" << endl;
	}
	return 0;
}

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

// Defination {{{
#define PI std::pair<int, int>
#define mk std::make_pair
#define reg register
#define ll long long
#define rep(i, a, b) for(reg int i = a; i <= b; ++i)
#define per(i, a, b) for(reg int i = a; i >= b; --i)
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
// }}}

template<typename T> T max(T a, T b) { return a > b ? a : b; }
template<typename T> T min(T a, T b) { return a < b ? a : b; }

template<typename T> void read(T &x) {
    x = 0; reg char ch = getchar(); reg int f = 1;
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    x *= f;
}

#define MOD 1000000007
#define N 105

int n, m;

int pos[100005], siz[100005], from[100005];
ll f[N][100005];

void solve() {
    int nx, tot = 0;
    for (int i = 1; i <= m; i = nx + 1) {
        pos[++tot] = m / i;
        nx = m / (m / i);
        siz[tot] = nx - i + 1;
    }
    std::sort(pos + 1, pos + tot + 1);
    rep (i, 1, tot) from[i] = std::lower_bound(pos + 1, pos + tot + 1, m / pos[i]) - pos;
    rep (i, 0, tot) f[0][i] = 1;
    rep (i, 1, n) {
        rep (j, 1, tot) {
            f[i][j] = (f[i - 1][from[j]] * siz[j] % MOD + f[i][j - 1]) % MOD;
        }
    }
    printf("%lld\n", f[n][tot]);
}

int main() {
    read(m), read(n);
        solve();
        return 0;
}


/*
 _____  ____    _____
|__  / |  _ \  |__  /
  / /  | |_) |   / / 
 / /_  |  _ <   / /_ 
/____| |_| \_\ /____|
  

 _____________________________________ 
/ noname.cpp is created by zrz who is \
\ weak                                /
 ------------------------------------- 
        \   ^__^
         \  (^^)\_______
            (__)\       )\/\
             U ||----w |
                ||     ||

*/


Measured memory_bytes: 80256
n = gets.to_i
ary = []
n.times do 
  ary << gets.chomp.chars.sort.join
end
ary = ary.sort

cnt = 1
ans = 0

for i in 1 .. n - 1
  if ary[i] == ary[i - 1]
    ans += cnt
    cnt += 1
  else
    cnt = 1
  end
end

puts ans


Measured memory_bytes: 26104
#include <stdio.h>
#include <string.h>

int main(void){
    char S[200001];
    char T[200001];
    memset(&S,'\0',sizeof(S));
    memset(&T,'\0',sizeof(T));
    scanf("%s",S);
    scanf("%s",T);
    
    int size = strlen(S);

    char alpha[26];
    memset(&alpha,'\0',sizeof(alpha));
    int flag = 0;
    for(int i = 0;i<size;i++){
        if(alpha[T[i] - 'a'] == '\0'){
            alpha[T[i] - 'a'] = S[i];
        }else if(alpha[T[i] - 'a'] != S[i]){
            printf("No\n");
            return 0;
        }
        for(int j = 0;j<26;j++){
            if(alpha[j] == S[i]){
                flag++;
            }
            if(flag > 1){
                printf("No\n");
                return 0;
            }
        }
        flag = 0;
    }
    // printf("S %s\n",S);
    // printf("T %s\n",T);
    printf("Yes\n");
    return 0;
}

Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    public void solve(BufferedReader stdin, PrintWriter stdout) throws NumberFormatException, IOException {
        String[] line = stdin.readLine().split(" ");
        long a = Long.parseLong(line[0]);
        long b = Long.parseLong(line[1]);
        long c = Long.parseLong(line[2]);
        long k = Long.parseLong(line[3]);
        if (k % 2 == 0) {
            stdout.println(a - b);
        } else {
            stdout.println(b - a);
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter stdout = new PrintWriter(System.out, false);
        new Main().solve(stdin, stdout);
        stdout.flush();
    }
}


Measured memory_bytes: 21460
#include<iostream>
#include<cstring>
using namespace std;
char a[12];
int main()
{
cin>>a;
for(int i=0;i<4;i++)
cout<<a[i];
cout<<" ";
for(int i=4;i<12;i++)
cout<<a[i];
cout<<endl;
return 0;
}

Measured memory_bytes: 256
#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <cctype> 
#include <string> 
#include <cstring> 
#include <ctime> 

using namespace std;

#define _int64 long long

char a[100][100];
char b[100][100];

int main()
{
  int i,j,k,l,m,n,b1;
  scanf("%d%d",&n,&m);
  for (i=0;i<n;i++)
    scanf("%s",a[i]);
  for (i=0;i<m;i++)
    scanf("%s",b[i]);
  for (i=0;i<=n-m;i++)
  {
    for (j=0;j<=n-m;j++)
    {
      b1=1;
      for (k=0;k<m;k++)
        for (l=0;l<m;l++)
          if (a[i+k][j+l]!=b[k][l]) b1=0;
      if (b1==1) break;
    }
    if (b1==1) break;
  }
  if (b1==1) printf("Yes\n");
  else printf("No\n");
  return 0;
}

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

#define FOR(i, a, b) for(int i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(int i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)
#define DEBUG_PRINT(...) fprintf(stderr, __VA_ARGS__)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
void print_pair(pi a){
  cerr<<"("<<a.first<<", "<<a.second<<") ";
}
template<int T1, int T2>
void print_2d(int a[T1][T2], int x, int y){
  For(i, x){
    For(j, y){
      cerr<<a[i][j]<<" ";
    }
    cerr<<endl;
  }
}



int main(){
  int N;
  cin>>N;
  int ans=0;
  while(N!=0){ans+=N%10;N/=10;}
  if(ans==1)ans=10;
  cout<<ans<<endl;
  return 0;
}



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


int main () {
  string c1, c2, c3;
  cin >> c1 >> c2 >> c3;
  cout << c1.at(0) << c2.at(1) << c3.at(2) << endl;
}

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

#define MAX 200000
#define SENTINEL 2000000000
typedef long long llong;

int L[MAX / 2 + 2], R[MAX / 2 + 2];

llong merge(int A[], int left, int mid, int right) {
  int i, j, k;
  llong cnt = 0;
  int n1 = mid - left;
  int n2 = right - mid;
  for ( i = 0; i < n1; i++ ) L[i] = A[left + i];
  for ( i = 0; i < n2; i++ ) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  i = j = 0;
  for ( k = left; k < right; k++ ) {
    if ( L[i] <= R[j] )
      A[k] = L[i++];
    else {
      A[k] = R[j++];
      cnt += n1 - i;  // = mid + j - k - 1
    }
  }
  return cnt;
}

llong mergeSort(int A[], int left, int right) {
  int mid;
  llong v1, v2, v3;
  if ( left + 1 < right ) {
    mid = (left + right) / 2;
    v1 = mergeSort(A, left, mid);
    v2 = mergeSort(A, mid, right);
    v3 = merge(A, left, mid, right);
    return v1 + v2 + v3;
  } else return 0;
}

int main() {
  int A[MAX], n, i;

  cin >> n;
  for ( i = 0; i < n; i++ )
    cin >> A[i];

  llong ans = mergeSort(A, 0, n);
  cout << ans << endl;

  return 0;
}


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

int N,M,Q;
char S[2010][2010];
int B[2010][2010] = {{0}},T[2010][2010] = {{0}},Y[2010][2010] = {{0}};

int main(){
	cin >> N >> M >> Q;
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			cin >> S[i][j];
			if(S[i][j]=='1') B[i][j]++;
			if(j>=2 && S[i][j]=='1' && S[i][j-1]=='1') Y[i][j]++;
			if(i>=2 && S[i][j]=='1' && S[i-1][j]=='1') T[i][j]++;
		}
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			if(j>=2){
				B[i][j] += B[i][j-1];
				Y[i][j] += Y[i][j-1];
				T[i][j] += T[i][j-1];
			}
		}
	}
	for(int i=1;i<=N;i++){
		for(int j=1;j<=M;j++){
			if(i>=2){
				B[i][j] += B[i-1][j];
				T[i][j] += T[i-1][j];
				Y[i][j] += Y[i-1][j];	
			}
		}
	}
/*	for(int i=0;i<=N;i++){
		for(int j=0;j<=M;j++){
			if(j!=M) cout << Y[i][j] << " ";
			else cout << Y[i][j] << endl;
		}
	}*/
	int x1,y1,x2,y2;
	for(int i=0;i<Q;i++){
		cin >> x1 >> y1 >> x2 >> y2;
		int b = B[x2][y2]-B[x1-1][y2]-B[x2][y1-1]+B[x1-1][y1-1];
		int y = Y[x2][y2]-Y[x1-1][y2]-Y[x2][y1]+Y[x1-1][y1];
		int t = T[x2][y2]-T[x2][y1-1]-T[x1][y2]+T[x1][y1-1];
		//cout << b << " " << y << " " << t << endl;
		cout << b - (y+t) << endl;
	}
}

Measured memory_bytes: 53120
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}

const int INF = 1e18+1;
const int MINF = -1e18-1;

signed main() {
    int N, K;
    cin >> N >> K;
    int z = 0;
    vi p, m;
    rep(i, N) {
        int a;
        cin >> a;
        if(a > 0) p.pb(a);
        else if(a < 0) m.pb(a);
        else z++;
    }
    SORT(p); SORT(m);
    int pn = (p.size()*(p.size()-1)/2)+(m.size()*(m.size()-1)/2); //積が正のペアの個数
    int mn = p.size()*m.size(); //積が負のペアの個数
    int zn = z*p.size()+z*m.size()+(z*(z-1))/2; //積が0のペアの個数

    int res;
    //K番目が負である場合
    if(K <= mn) {
        int l=MINF, r=0, mid;
        while(abs(l-r) > 1) {
            mid = (l+r)/2;
            int cnt = 0, j=0;
            //しゃくとり法
            rep(i, m.size()) {
                while(j<p.size() && mid < m[i]*p[j]) j++;
                cnt += p.size()-j;
            }
            if(cnt >= K) r = mid;
            else l = mid;
        }
        res = r;
    }

    //K番目が0である場合 
    else if(K <= mn+zn) {
        res = 0;
    }

    //K番目が正である場合 
    else {
        int l=0, r=INF, mid;
        while(abs(r-l) > 1) {
            mid = (l+r)/2;
            int cnt = 0;
            rep(i, p.size()) {
                auto it = upper_bound(ALL(p), mid/p[i]);
                cnt += it - p.begin();
                if(mid/p[i] >= p[i]) cnt--;
            }
            rep(i, m.size()) {
                auto it = lower_bound(ALL(m), mid/m[i]);
                cnt += m.end()-it;
                if(mid/m[i] <= m[i]) cnt--;
            }
            if(cnt/2+mn+zn < K) l = mid;
            else r = mid;
        }
        res = r;
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 2420
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

YES = "YES"  # type: str
NO = "NO"  # type: str

def solve(X: int):
    return YES if X in [7, 5, 3] else NO


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    result = solve(X)
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5124
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>

using namespace std;

int main() {
   int n, m;
   cin >> n >> m;
   cout << (n - 1) * (m - 1) << endl;
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <map>
#define ll long long
const int MOD = 1e9+7;
using namespace std;

ll fact[400001];

ll modpow(ll x, ll y){
	ll res = 1;
	while(y > 0){
		if (y & 1) res = res * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return res;
}

ll factinv(ll n){
	return modpow(fact[n], MOD-2);
}

ll modper(ll n, ll r){
	ll res = 1;
	for (int i = 0; i < r; i++){
		res = res * (n-i) % MOD; 
	}
	return res;
}

ll comb(ll n, ll r){
	return (fact[n]*factinv(r)%MOD)*factinv(n-r)%MOD;
}


int main(){
	ll n, k;
	cin >> n >> k;
	fact[0] = 1;
	for (int i = 1; i <= 400000; i++){
		fact[i] = fact[i-1]*i%MOD;
	}

	if (n == 2){
		if (k%2) cout << 2 << endl;
		else cout << 1 << endl;
		return 0;	
	}
	if (k >= n - 1){
		cout << comb(2*n-1, n) << endl;
		return 0;
	}else{
		ll ans = 0;
		for (int i = 0; i <= k; i++){
			ans += comb(n, i)*comb(n-1, n-i-1);
			ans %= MOD;
		}
		cout << ans << endl;
	}
	return 0;
}

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

#define pb(x) push_back(x);
#define in(y) insert(y);
#define tt(t) while(t--)
#define itr ::iterator it;
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define si set<int>                      
#define msi map<string, int>
#define new cout<<endl
#define ff(n) for(int i=0;i<n;i++)
#define all(v) sort(v.begin(),v.end())

using namespace std;

int main(){
	string s;
	cin>>s;
	int x,y;
	ff(s.size()){
	if(s[i]=='A'){ x=i; break;}}
	
	ff(s.size())
	if(s[i]=='Z') y=i;
	
	cout<<y-x+1;
    return 0;
}


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

int main() {
  int A,B,C,X,Y;
  cin >> A >> B >> C >> X >> Y;
  int cost1,cost2,cost3;
  
  cost1=A*X+B*Y;
  if(X<=Y){
    cost2=2*C*X+B*(Y-X);
  }
  else{
    cost2=2*C*Y+A*(X-Y);
  }
    
  
  cost3=2*C*max(X,Y);
  
  cout << min({cost1,cost2,cost3}) << endl;
}

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

ll gcd(ll a, ll b){
  return (b != 0) ? gcd(b, a%b) : a;
}

int main(){
  int n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n){
    cin >> a[i];
    a[i] -= (i+1);
  }
  sort(a.begin(), a.end());
  ll ans = 0;
  rep(i, n){
    ans += abs(a[(n+1)/2-1] - a[i]);
  }
  
  cout << ans << endl;
  
}

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

struct info{
    string color;
    int weight;
    info(){}
    info(string c, int w):color(c),weight(w){}
    bool operator<(const info& a) const{ return weight < a.weight; }
    bool operator>(const info& a) const{ return weight > a.weight; }
};

int main(){

    int n; cin >> n;
    vector<info> a(n);
    for(int i = 0; i < n; i++){
        string color; cin >> color;
        int w; cin >> w;
        a[i] = info(color, w);
    }

    sort(a.begin(), a.end());
    a.push_back(info("end", -1));
    
    //for(int i = 0; i <= n; i++) cout << a[i].color << " " << a[i].weight << endl;
    int m; cin >> m;
    
    int idx = 0;
    int cnt = 0;
    for(int i = 0; i < m; i++){
        string str; cin >> str;
        
        //cout << idx << endl;
        while(true){
            if(str == a[idx].color){
                cnt++;
                int num = a[idx].weight;
                //cout << "before" << idx << endl;
                while(num == a[idx].weight){
                    idx++;
                    if(idx == n) break;
                }
                //cout << "after" << idx << endl;
                break;
            }else{
                idx++;
            }

            if(idx >= n) break;
        }

        if(idx >= n) break;
    }
    //cout << cnt << endl;
    if(cnt == m) cout << "Yes" << endl;
    else cout << "No" << endl;




    return 0;
}


Measured memory_bytes: 13644
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<pair<int,int> , null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update> 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
// #define endl '\n'
#define int int64_t
#define double long double
#define fdt fuck donald trump
mt19937 rnd(time(0));
const int MAXN = 100001;

int n, m;
int a[MAXN];

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
	// freopen("FDT.txt","r",stdin);
	int n, k;
	cin >> n >> k;
	if(k > n)
		cout << min(n, abs(k - n));
	else{
		int m = (n%k == 0? n: (n/k + 1)*k);
		m/= k;
		m--;
		cout << min(n - m*k, abs(k - (n - m*k)));
	}
}


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

ll next_minimum(ll key){
	ll g=key, dsum=0;
	while(g>0){
		dsum += g%10;
		g /= 10;
	}
	int d=1;
	bool flag=1;
	ll res=key, nsum=dsum;
	while(flag){
		ll c=key, sum=dsum;
		for(int i=0; i<d; ++i){
			sum -= c%10;
			c /= 10;
		}
		flag=(c>0);
		for(int i=0; i<d; ++i){
			c *= 10;
			c += 9;
			sum += 9;
		}
		if(res*sum>c*nsum){
			res=c;
			nsum=sum;
		}
		++d;
	}
	return res;
}

int main() {
	int K;
	cin >> K;
	ll ans=0;
	for(int i=0; i<K; ++i){
		ans=next_minimum(ans+1);
		cout << ans << endl;
	}
	return 0;
}

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

int main(){
  int N,A=0,B=0;
  cin >> N;
  vector<int> a(N);
  for(int i=0;i<a.size();i++){
    cin >> a.at(i);
  }
  sort(a.begin(),a.end(),greater<int>());
  for(int i=0;i<a.size();i++){
    if(i%2==0){
      A += a.at(i);
    }else{
      B += a.at(i);
    }
  }
  cout << A-B << endl;
  return 0;
}

Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Data.List

main :: IO ()
main = do
  [n, q] <- f
  unless (n == 0 && q == 0) $ do
    solve <$> (sort <$> replicateM n g) <*> replicateM q readLn >>= mapM_ putStrLn
    main
  where
    f = map read <$> words <$> getLine
    g = (\[en, eby, wy] -> (read wy, read wy - read eby + 1, en)) <$> words <$> getLine

solve :: [(Int, Int, String)] -> [Int] -> [String]
solve yt = map f
  where
    f q = let (_, ys) = break (\(y, _, _) -> y >= q) yt
          in case ys of
              (lwy, fwy, en):_ | fwy <= q -> unwords [en, show (q - fwy + 1)]
              _ -> "Unknown"



Measured memory_bytes: 7468
#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> tp;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<LL, pii> plpii;
typedef pair<LD, LD> pdd;
typedef pair<LD, int> pdi;
typedef pair<LD, LL> pdl;
typedef pair<int, LD> pid;
typedef pair<LL, LD> pld;
const int mod = 1e9 + 7;
const int hf = 999983;
const int N = 1e6;
int cnt[4];
LD dp[305][305][305];
bool vis[305][305][305];
int n;
LD dfs(int a, int b, int c){
    if(a == 0 && b == 0 && c == 0) return 0;
    if(vis[a][b][c]) return dp[a][b][c];
    vis[a][b][c] = 1;
    int sum = a+b+c;
    LD rem = (LD)n/sum;
    LD ans = 0;
    if(a > 0){
        LD prob = (LD)a/sum;
        ans += prob*(dfs(a-1, b, c) + rem);
    }
    if(b > 0){
        LD prob = (LD)b/sum;
        ans += prob*(dfs(a+1, b-1, c) + rem);
    }
    if(c > 0){
        LD prob = (LD)c/sum;
        ans += prob*(dfs(a, b+1, c-1) + rem);
    }
    return dp[a][b][c] = ans;
}
int main(){
    int a;
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d", &a);
        cnt[a]++;
    }
    printf("%.10Lf\n", dfs(cnt[1], cnt[2], cnt[3]));
}


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


//#define int long long 


const int N = 2e5 + 7;

tuple <int, int, int> pt[N];

int aa[N], cnt[N];

int32_t main() {
	ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;
	set <int> st;
	for(int i = 1; i <= n; ++i) {
		int x, y; cin >> x >> y;
		pt[i] = make_tuple(x, y, i);
		st.insert(i);
	}

	sort(pt + 1, pt + n + 1);

	vector <pair <int, int> > v;

	for(int i = n; i >= 1; i--) {
		int x, y, j; tie(x, y, j) = pt[i];
		v.push_back(make_pair(*st.begin(), y));
		st.erase(y);
	}

	sort(v.begin(), v.end());

	vector <pair <int, int> > ans;

	for(auto z: v) {
		if(ans.empty() || ans.back().second < z.first) ans.push_back(z);
		else {
			ans[ans.size() - 1].second = max(ans[ans.size() - 1].second, z.second);
		}
	}

	for(auto z: ans) {
		for(int i = z.first; i <= z.second; ++i) {
			aa[i] = z.second - z.first + 1;
		}
	}
	for(int i = 1; i <= n; i++) {
		int x, y, j; tie(x, y, j) = pt[i];
		cnt[j] = aa[y];
	}

	for(int i = 1; i <= n; i++) cout << cnt[i] << endl;
}

Measured memory_bytes: 18100
#include<iostream>
using namespace std;
int main(){
int n,a;
cin >> n;
int t[n],x[n],y[n];
for(int i=0;i<n;i++)
cin >> t[i] >> x[i] >> y[i];
for(int i=0;i<n;i++)
{
a=t[i]-x[i]-y[i];
if(a<0 or a%2!=0)
{
cout << "No";
return 0;
}}
cout << "Yes";
return 0;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int c2i(char c) {
  return isupper(c) ? c-'A' : c-'a'+26;
}

char i2c(int i) {
  return i < 26 ? i+'A' : i-26+'a';
}

const int n = 52;
int G[n][n];
bool used[1000];
vector<char> path;
void dfs(int u, int& cnt, int e, const int& E) {
  if(e == E) {
    //rep(i, path.size()) cout << path[i] << " ";
    //cout << endl;
    ++cnt;
    return;
  }
  for(int v = 0; v < n; ++v) {
    if(G[u][v] != -1 && !used[G[u][v]]) {
      used[G[u][v]] = true;
      //path.push_back(i2c(v));
      dfs(v, cnt, e+1, E);
      //path.pop_back();
      used[G[u][v]] = false;
      if(cnt >= 2) return;
    }
  }
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  string s;
  while(cin >> s, s != "#") {
    int len = s.size();
    if(len <= 2) {
      cout << "No Results" << endl;
      continue;
    }

    fill(G[0], G[n], -1);
    int E = 0;
    vint in(n, 0), out(n, 0);
    rep(i, len-1) {
      int from = c2i(s[i]), to = c2i(s[i+1]);
      if(G[from][to] == -1) {
	G[from][to] = E++;
	++out[from];
	++in[to];
      }
    }
    int D = 0;
    rep(i, n) D += max(0ll, in[i]-out[i]);
    if(D == 0) cout << E+1 << endl;
    else if(D != 1) cout << E+D << endl;
    else if(E+1 < len) cout << E+1 << endl;
    else {
      fill(used, used+E, false);
      int cnt = 0;
      //path.push_back(s[0]);
      dfs(c2i(s[0]), cnt, 0, E);
      //path.pop_back();
      if(cnt == 2) cout << E+1 << endl;
      else cout << E+2 << endl;
    }
  }

  return 0;
}



Measured memory_bytes: 3080
#include <iostream>
using namespace std;
int main(void){
    int i,j,a,b,p;
    string x,y;
    int n,m;
    n=0;
    m=0;
    cin>>x>>y;
    a=x.size();
    b=y.size();
    int chart[a+1][b+1];
    for(i=0;i<a+1;i++){
        for(j=0;j<b+1;j++){
            if(i==0||j==0){
                chart[i][j]=0;
                continue;
            }    
            m=chart[i][j-1];
            if(x[i-1]==y[j-1]&&m<chart[i-1][j-1]+1)
            m=chart[i-1][j-1]+1;
            n=chart[i-1][j];
            if(m<n)
            chart[i][j]=n;
            else
            chart[i][j]=m;
        }
    }
    int k=0;
    int o=chart[a][b];
    string answer;
    for(i=0;i<a;i++){
        for(j=k;j<b;j++){
            if(o!=chart[a-i][b-j])
            break;
            if(chart[a-i][b-j]-1==chart[a-i-1][b-j-1]&&x[a-i-1]==y[b-j-1]){
                answer=y[b-j-1]+answer;
                k=j+1;
                o--;
                break;
            }
        }
    }
    cout<<answer<<endl;
}

Measured memory_bytes: 35456
#include<iostream>

int main(){
    int W, a, b;
    std::cin >> W >> a >> b;
    int ret = 0;
    if(a + W <= b) ret = b - (a + W);
    else if(b + W <= a) ret = a - (b + W);
    std::cout << ret << std::endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int x[]=new int[n];
		double c=0;
		for(int i=0;i<n;i++) {
			x[i]=sc.nextInt();
			c+=x[i];
		}
		Arrays.sort(x);
		int d=0;
		

		c=Math.round(c/n);
		

		for(int i=0;i<n;i++) {
			d+=Math.pow(x[i]-c,2);
		}
		System.out.println(d);
	}

}


Measured memory_bytes: 22100
n, m, c = map(int, input().split())
b_lists = list(map(int, input().split()))
a_lists = []
for _ in range(n):
    tmp = list(map(int, input().split()))
    a_lists.append(tmp)

ans = 0
for i in a_lists:
    cond = c
    for j in range(m):
        cond += i[j]*b_lists[j]
    if cond > 0:
        ans += 1

print(ans)

Measured memory_bytes: 9200
#include <stdlib.h>
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
const ll INF=0x3f3f3f3f;
#define mod 1000000007
#define mem(a,b) memset(a,b,sizeof(a))
//__builtin_popcount
using namespace std;
//priority_queue
const ll MAX=100000;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
ll kc(ll a,ll b)
{
    ll c=1;
    while(b)
    {
        if(b&1)c=(c*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return c;
}
bool cmp(double x,double y)
{
    return x>y;
}
int F[50003*3];
int Find(int a)
{
    return F[a]<0?a:F[a]=Find(F[a]);
}
int same(int a,int b)
{
    if(Find(a)==Find(b))return 1;
    return 0;
}
int up1(int a,int b)
{
    int x,y;
    x=Find(a);
    y=Find(b);
    if(x!=y)
    F[x]=y;
    return 0;
}
vector<int>q[MAX+10];
int de[MAX+10];
int out[MAX+10];
void dfs(int a,int fa)
{
    for(auto i:q[a])
    {
        if(de[i]==0)
        {
            de[i]=de[a]+1;
              dfs(i,a);
        }
        else if(de[i]>de[a]){

            cout<<a<<" "<<i<<endl;
            out[a]++;
        }
    }
    if(out[a]%2)
    {  if(fa!=0)
        {
            cout<<a<<" "<<fa<<endl;
        out[a]++;
        }
           }
    else {
       if(fa!=0)
       {
     cout<<fa<<" "<<a<<endl;
        out[fa]++;
       }
    }
}
int main()
{
 int n,m;
   cin>>n>>m;
   if(m%2)
   {
       cout<<-1<<endl;
       return 0;
   }
   for(int i=1;i<=m;i++)
   {
       int x,y;
       cin>>x>>y;
       q[x].push_back(y);
       q[y].push_back(x);
   }
   de[1]=1;
   dfs(1,0);
}


Measured memory_bytes: 15488
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
 
int main(){
	
	int n;
	cin >> n;
	vector<int>dp(3);

	for(int day=0;day<n;day++){
		vector<int>new_dp(3,0);
		vector<int>c(3);
		for(int i=0;i<3;i++)
		{
			cin >>c[i];
		}			

		for(int i=0;i<3;++i){
			for(int j=0;j<3;++j){
				
				if(i!= j){
					new_dp[j] = max(new_dp[j],dp[i]+c[j]);
				}
			}
		}
		dp = new_dp;
	}
 		
 	cout << max(dp[2],max(dp[0],dp[1])) << endl;
}

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

using namespace std;

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

    int first = inp/100;
    int second = inp%100;

    // YM MY
    if(second <= 12 && first <= 12 && second > 0 && first > 0){
        cout << "AMBIGUOUS" << endl;
    }
    // YM
    else if(second <= 12 && second > 0){
        cout << "YYMM" << endl;
    }
    // MY
    else if(first <= 12 && first > 0){
        cout << "MMYY" << endl;
    }
    else{
        cout << "NA" << endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int N;
  cin >> N;
  int ans=(N-1)/2;
  cout << ans << endl;
}

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

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

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

    sort(a.begin(), a.end());
    int mn = a[0];

    for (int i = 1; i < n; i++) {
        mn = __gcd(mn, a[i]);
    }

    cout << mn << endl;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	auto M=in();
	
	out(24+(24-M));
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <math.h>

using namespace std;

#define x first
#define y second
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define SZ(x) int(x.size())
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = b-1; i >= a; i--)
#define DBG(x) cerr << (#x) << "=" << x << "\n";
#define ll long long
#define inf 1000000007
#define mod 998244353//1000000007
#define N 200005

template<typename U, typename V> void Min(U &a, const V & b){if(a > b)a = b;}
template<typename U, typename V> void Max(U &a, const V & b){if(a < b)a = b;}
template<typename U, typename V> void add(U &a, const V & b){a = (a + b) % mod;}
template<typename U> U gcd(U a, U b){
    if(a == 0)return b;
    if(b == 0)return a;
    if(a >= b)return gcd(a % b, b);
    else return gcd(a, b % a);
}
int pow(int a, int b){
    int ans = 1;
    while(b){
        if(b & 1)ans = 1LL * ans * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return ans;
}

char s[205];
int d[205], c[205];
vi e, g[205];
int dfs(int u, int fa = -1){
    e.pb(u);
    for(auto &v : g[u]) {
        if(v == fa)continue;
        if(!d[v]){
            d[v] = d[u] + 1;
            if(!dfs(v, u))return 0;
        }
        else if((d[u] - d[v]) % 2 == 0)return 0;
    }
    return 1;
}
int go(int u){
    queue<int>q;
    q.push(u);
    c[u] = 1;
    int K = 1;
    while(!q.empty()){
        u = q.front(); q.pop();
        Max(K, c[u]);
        for(auto &v : g[u])if(!c[v]){
            c[v] = c[u] + 1;
            q.push(v);
        }
    }
    return K;
}
int main(){
    int T, n, m, i, j, k, ca = 0, K;
    scanf("%d", &n);
    rep(i, 0, n){
        scanf("%s", s);
        rep(j, 0, n)if(s[j] == '1')g[i].pb(j);
    }
    int sum = 0;
    rep(i, 0, n)if(!d[i]){
        e.clear();
        if(!dfs(i)){
            puts("-1");
            return 0;
        }
        int ans = 0;
        for(auto &u : e){
            for(auto &v : e)c[v] = 0;
            Max(ans, go(u));
        }
        sum += ans;
    }
    printf("%d\n", sum);
}


Measured memory_bytes: 436
W,H,N = map(int, input().split())
abc = [list(map(int, input().split())) for _ in range(N)]
w1=0
h1=0
w2=W
h2=H

for i in range(0,N):
    if abc[i][2] ==1:
        w1 = max(w1,abc[i][0])
    elif abc[i][2] ==2:
        w2 = min(w2,abc[i][0])
    elif abc[i][2] ==3:
        h1 = max(h1,abc[i][1])
    elif abc[i][2] ==4:
        h2 = min(h2,abc[i][1])

res = max((w2-w1),0)*max((h2-h1),0)
print(res)

Measured memory_bytes: 3064
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

use std::collections::HashMap;


struct UFT {
    par: Vec<usize>,
    rank: Vec<usize>,
}

impl UFT {
    fn new(n: usize) -> Self {
        let mut par = Vec::with_capacity(n);
        let mut rank = Vec::with_capacity(n);
        for i in 0..n {
            par.push(i);
            rank.push(0);
        }
        UFT {
            par: par,
            rank: rank
        }
    }

    fn find(&mut self, n: usize) -> usize {
        if self.par[n] == n {
            n
        } else {
            let par = self.par[n];
            let result = self.find(par);
            self.par[n] = result;
            result
        }
    }

    fn unite(&mut self, l: usize, r: usize) {
        let (l, r) = (self.find(l), self.find(r));

        if l == r {
            return;
        }

        if self.rank[l] < self.rank[r] {
            self.par[l] = r;
        } else {
            self.par[r] = l;
            if self.rank[l] == self.rank[r] {
                self.rank[l] += 1;
            }
        }
    }
}



#[allow(dead_code)]
fn solve(n: usize, ps: Vec<(usize, usize)>, rs: Vec<(usize, usize)>) -> Vec<usize> {
    let mut ps_t = UFT::new(n);
    for (p, q) in ps {
        ps_t.unite(p, q);
    }
    let mut rs_t = UFT::new(n);
    for (r, s) in rs {
        rs_t.unite(r, s);
    }
    let mut h = HashMap::new();
    for i in 0..n {
        let p = ps_t.find(i);
        let r = rs_t.find(i);
        *h.entry((p, r)).or_insert(0) += 1;
    }

    let mut res = Vec::with_capacity(n);
    for i in 0..n {
        let p = ps_t.find(i);
        let r = rs_t.find(i);
        res.push(h[&(p, r)]);
    }
    res
}

fn main() {
    input!{
        n: usize,
        k: usize,
        l: usize,
        ps: [(usize1, usize1); k],
        rs: [(usize1, usize1); l],
    }
    let res = solve(n, ps, rs);
    for r in res {
        print!("{} ", r);
    }
    println!("");
}


Measured memory_bytes: 30240
use std::io;
use std::cmp;


// read a line(without line feed)
fn read_line() -> String {
    let mut in_str = String::new();
    io::stdin().read_line(&mut in_str).unwrap();
    return in_str.trim().to_string();
}

// read wods on a line
pub fn read_words_in_line() -> Vec<String> {
    let s = read_line();
    return s.split_whitespace().map(|x| x.to_string()).collect::<Vec<String>>()
}

// read type t on a line
pub fn read_t_in_line<T : std::str::FromStr>() -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for e in read_words_in_line().iter().map(|x| x.parse::<T>()) {
        if let Ok(r) = e {
            v.push(r);
        }
        else{
            return Vec::new();
        }
    }
    return v;
}

// sort slice
pub fn sort<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort();
}
// sort slice by reverse order
pub fn sort_rev<T : std::cmp::Ord>(slice : &mut [T]) {
    slice.sort_by(|x, y| y.cmp(x));
}

pub fn min<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::min(a, b);
}

pub fn max<T : std::cmp::Ord>(a : T, b : T) -> T{
    return cmp::max(a, b);
}


fn main() {
    
    let _n = read_t_in_line::<i32>()[0];
    let v = read_t_in_line::<i32>();
    let c = read_t_in_line::<i32>();
    let mut sum = 0;
    for i in 0..v.len() {
        sum += max(0, v[i] - c[i]);
    }
    println!("{}", sum);
}



Measured memory_bytes: 4352
#include <iostream>
using namespace std;
 
int main()
{
    while(true){
        int n;
        cin >> n;
 
        if(n==0)
            break;
 
        char c[100];
        for(int i=0; i<n; i++){
            cin >> c[i];
        }
 
        int cnt[26] = {0};
 
        for(int i=0; i<n; i++){
            cnt[(int)(c[i]-'A')]++;
 
            int max1 = -1;
            int max2 = -1;
 
            for(int j=0; j<26; j++){
                if(cnt[j]>max1){
                    max2 = max1;
                    max1 = cnt[j];
                }
                else if(cnt[j]>max2){
                    max2 = cnt[j];
                }
            }
 
            if(max1-max2>n-(i+1)){
                for(int j=0; j<26; j++){
                    if(cnt[j]==max1){
                        cout << (char)(j+'A') << ' ';
                        break;
                    }
                }
                cout << (i+1) << endl;
                break;
            }
 
            if(i==n-1){
                cout << "TIE" << endl;
                break;
            }
        }
    }
 
    return 0;
}

Measured memory_bytes: 3112
//Vol5 588
#include<stdio.h>
#include<string.h>
int main()
{
	int n,s=0;
	char c,l='+';
	while(1){
		scanf("%d\n",&n);
		scanf("%c",&c);
		if(l=='+'){
			s+=n;
		}else if(l=='-'){
			s-=n;
		}else if(l=='*'){
			s*=n;
		}else{
			s/=n;
		}
		l=c;
		if(c=='='){
			printf("%d\n",s);
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 2720
#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<string> s(n);
    rep(i, n){
        cin >> s.at(i);
    }
    
    int max_ = 0;
    map<string, int> m;
    rep(i, n){
        m[s.at(i)]++;
        max_ = max(m[s.at(i)], max_);
    }
    
    for(auto p : m){
        if(p.second == max_) cout << p.first << endl;
    }
    return 0;
}

Measured memory_bytes: 26752
x, n = map(int, input().split())
if n != 0:
  p = list(map(int, input().split()))
  for i in range(101):
    if x-i not in p:
      ans = x - i
      break
    
    elif x+i not in p:
      ans = x + i
      break
else:
  ans = x

print(ans)

Measured memory_bytes: 61900
import math

def is_integer(n):
    try:
        float(n)
    except ValueError:
        return False
    else:
        return float(n).is_integer()
      
N, D = map(int, input().split())
lst = []
for i in range(N):
  lst.append(list(map(int, input().split())))
sum = 0
for i in range(N-1):
  for j in range(i+1, N):
    ans = 0
    for k in range(D):
      ans += (lst[i][k] - lst[j][k])**2
    if(is_integer(math.sqrt(ans))):
      sum +=1
print(sum)
 

Measured memory_bytes: 3064
#include <stdio.h>

int main() {
	int n;
	scanf("%d", &n);
	char arr[10000];
	scanf("%s", arr);
	for(int i = 0; arr[i] != '\0'; i++) {
		if(arr[i] + n > 'Z') {
			printf("%c", arr[i] + n - 26);
		}
		else {
			printf("%c", arr[i] + n);
		}
	}
	puts("");
	return 0;
}

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

int main(void){
	double a, b, c, d, e, f;
	while(cin >> a >> b >> c >> d >> e >> f){
		double x, y;
		x=(c*e-b*f)/(a*e-b*d);
		y=(a*f-c*d)/(a*e-b*d);
		if(x>-0.001 && x<=0) x=0;
		if(y>-0.001 && y<=0) y=0;

		cout.setf(ios::fixed);
		cout.precision(3);
		cout << x << " " << y << endl;
	}
	return 0;
}

Measured memory_bytes: 0