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


long long int Exp(long long int exp_n,long long int exp_e, long long exp_mod);


int main(){
  long long int N,K,tmp;
  cin >> N >> K;
  long long int A[N+1];
  long long int B[N+1];
  long long int a=1,b=1;
  A[0]=0;
  B[0]=0;
  for(long long int i=0;i<N;i++){
    cin >> tmp;
    if(tmp>=0){
      A[a]=tmp;
      a++;
    }else if(tmp < 0){
      B[b]=abs(tmp);
      b++;
    }
  }
  long long int k = a-1;
  long long int l = b-1;
  int c=0;
  long long int O=1;


  sort(A, A+a);
  sort(B, B+b);
  
  
  if(K==N){
    for(int i=1;i<a;i++){
      O = O * A[i];
      if(O > 1000000007){
        O = O%1000000007;
      }
    }
    for(int i=1;i<b;i++){
      O = O * (1000000007 - B[i]);
      if(O > 1000000007){
        O = O%1000000007;
      }
    }
  }else if(K%2==1 && l==N){
    for(long long int i=0;i<K;i++){
      O = O * B[i+1];
      if(O > 1000000007){
        O = O%1000000007;
      }
    }
    O = 1000000007 - O;
  }else{
    for(int i=0;i<K;i++){
      if(A[k]*A[k-1] > B[l]*B[l-1] || i==K-1){
        O = O * A[k];
        //cout << A[k] << endl;
        k--;
      }else{
        O = O * B[l];
        //cout << "-" << B[l] <<endl; 
        l--;
        if(O > 1000000007){
          O = O%1000000007;
        }
        O = O * B[l];
        //cout << "-" << B[l] <<endl;
        l--;
        i++;
      }
      if(O > 1000000007){
        O = O%1000000007;
      }
    }
  }
  
  cout << O <<endl;;
  
  return 0;
}


long long int Exp(long long int exp_n,long long int exp_e, long long int exp_mod){
  long long int exp_o = 1;
  long long int exp_x=exp_n;
  long long int exp_tmp;
  
  while(0<exp_e){
    exp_tmp = exp_e/2;
    if(exp_e - exp_tmp*2 == 1){
      exp_o = exp_o*exp_x;
      if(exp_o>exp_mod){
        exp_o=exp_o%exp_mod;
      }
    }
    
    exp_x = exp_x*exp_x;
    if(exp_x>exp_mod){
      exp_x=exp_x%exp_mod;
    }
    exp_e = exp_tmp;
  }
  return exp_o;
}


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

#define pb push_back
#define fi first
#define se second
#define mem(x,n) memset(x,n,sizeof(x))
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define foreach(it,l) for(auto it=(l).begin();it!=(l).end();it++)
#define pnl printf("\n")
#define endl '\n'
#define len(x) (x).length()

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<int> VI;
const double EPS=1e-10;
//const double PI=acos(-1.0);
const int INF=1<<30;
const LL LLINF=1ll<<60;
const int MOD=1e9+7;
const int xx[8]={1,0,-1,0,1,-1,1,-1};
const int yy[8]={0,1,0,-1,-1,1,1,-1};

void fastio(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }

/***********************************\
     _____ _             _
    /  __ \ |           (_)
    | /  \/ | __ _ _ __  _  ___
    | |   | |/ _` | '_ \| |/ _ \
    | \__/\ | (_| | |_) | |  __/
     \____/_|\__,_| .__/|_|\___|
                  | |
                  |_|
\***********************************/

int asd[100005];

int main(){
	int tc;
	scanf("%d",&tc);
	while(tc--){
		int x,y;
		scanf("%d%d",&x,&y);
		for(int i=x;i<=y;i++){
			asd[i]++;
		}
	}
	int cnt=0;
		for(int i=1;i<=100000;i++){
			if(asd[i]!=0) cnt++;
		}
	printf("%d",cnt);		
	return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void run() {
		int[] array = new int[3];
		Scanner scan = new Scanner(System.in);
		int tmp = scan.nextInt();
		while (tmp != 0) {
			tmp--;
			for (int i = 0; i < 3; i++) array[i] = scan.nextInt();
			// check
			boolean ch = false;
			for (int i = 0; i < 3; i++) {
				int j = (i+1) % 3;
				int k = (i+2) % 3;
				if(array[i]*array[i] + array[j]*array[j] == array[k]*array[k]) ch = true;
			}
			// output
			if(ch) System.out.println("YES");
			else System.out.println("NO");
		}
	}
}


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

int main(void)
{
	int table[256];
	char roma_num[128];
	int num;
	int len;
	int i;

	table['I'] = 1;
	table['V'] = 5;
	table['X'] = 10;
	table['L'] = 50;
	table['C'] = 100;
	table['D'] = 500;
	table['M'] = 1000;

	while (~scanf("%s", roma_num)){
		len = strlen(roma_num);
		num = table[roma_num[len - 1]];
		for (i = len - 2; i >= 0; i--){
			num += table[roma_num[i]] * (table[roma_num[i + 1]] > table[roma_num[i]] ? -1 : 1);
		}
		printf("%d\n", num);
	}

	return (0);
}

Measured memory_bytes: 540
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <random>
#include <chrono>
using namespace std;

const int maxn = 1e5 + 5;

typedef long long LL;

int n, m;
int x[maxn], y[maxn];
const LL mod = 1e9 + 7;

int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        scanf("%d", &x[i]);
    }
    for(int i = 1;i <= m;i++){
        scanf("%d", &y[i]);
    }
    LL pre1 = 0, pre2 = 0, suf1 = 0, suf2 = 0;
    for(int i = 1;i <= n;i++){
        pre1 += 1LL * (i - 1) * x[i];
    }
    for(int i = n;i >= 1;i--){
        suf1 += 1LL * (n - i) * x[i];
    }
    for(int i = 1;i <= m;i++){
        pre2 += 1LL * (i - 1) * y[i];
    }
    for(int i = m;i >= 1;i--){
        suf2 += 1LL * (m - i) * y[i];
    }
    pre1 = (pre1 % mod + mod) % mod;
    suf1 = (suf1 % mod + mod) % mod;
    pre2 = (pre2 % mod + mod) % mod;
    suf2 = (suf2 % mod + mod) % mod;
    LL ans = ((pre1 * pre2 + suf1 * suf2 - pre1 * suf2 - pre2 * suf1) % mod + mod) % mod;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
from fractions import gcd
A, B, C, D = map(int, input().split())

cmul = (B // C) - ((A - 1) // C)
dmul = (B // D) - ((A - 1) // D)
CD = C * D // gcd(C, D)
cdmul = (B // CD) - ((A - 1) // CD)

print((B - A + 1) - (cmul + dmul - cdmul))


Measured memory_bytes: 5688
#include <bits/stdc++.h>
using namespace std;
 
int main() { 
  int A;
  int B;
  int C;
  int D;
    
  cin >> A >> B >> C >> D;
  
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B < C + D) {
    cout << "Right" << endl;
  } 
  else {
    cout << "Balanced" << endl;
  }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define ll long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

using namespace std;

const ll N = 3e5 + 5;

int n, k;
int a[N];
int dp[N];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for (int i = 1; i <= n; i++)
        cin>>a[i];
    dp[1] = 0;
    for (int i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + abs (a[i] - a[i - 1]);
        for (int j = i - 2; j >= i - k && j >= 1; j--)
            dp[i] = min (dp[i], dp[j] + abs (a[i] - a[j]));
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
using namespace std;
typedef long long lli;
const int maxn = 305;
const lli INF = 2e15;
int n, m;
int L;
lli adj[2][maxn][maxn];

void ReadInput()
{
    fill_n(&adj[0][0][0], sizeof(adj) / sizeof(adj[0][0][0]), INF);
    cin >> n >> m >> L;
    for(int i = 0; i < m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;
        --x; --y;
        adj[0][x][y] = adj[0][y][x] = w;
    }
}

void Init()
{
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                adj[0][i][j] = min(adj[0][i][j], adj[0][i][k] + adj[0][k][j]);

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            adj[1][i][j] = adj[0][i][j] <= L ? 1 : INF;
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                adj[1][i][j] = min(adj[1][i][j], adj[1][i][k] + adj[1][k][j]);
}

void Solve()
{
    int Q;
    cin >> Q;
    for(; Q > 0; --Q)
    {
        int s, t;
        cin >> s >> t;
        --s; --t;
        cout << (adj[1][s][t] == INF ? -1 : adj[1][s][t] - 1) << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Init();
    Solve();
}


Measured memory_bytes: 2048
// https://atcoder.jp/contests/abc154/tasks/abc154_c
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    vector<int> V(N);
    REP(i, N) { cin >> V[i]; }
    double sum = 0, maxv = 0;
    REP(i, K) {
        sum += (V[i] + 1) * 0.5;
        maxv = max(maxv, sum);
    }
    FOR(i, K, N) {
        sum += (V[i] + 1) * 0.5 - (V[i - K] + 1) * 0.5;
        maxv = max(maxv, sum);
    }
    printf("%.10f\n", maxv);

    return 0;
}


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

using namespace std;

int main()
{
  int N, M, X, Y; cin >> N >> M >> X >> Y;
  vector<int> x(N), y(M);
  for (int i = 0; i < N; ++i) cin >> x[i];
  for (int i = 0; i < M; ++i) cin >> y[i];

  sort(x.begin(), x.end());
  sort(y.begin(), y.end());

  if (x.back() < y.front() and X < y.front() and y.front() <= Y) {
    cout << "No War";
  } else {
    cout << "War";
  }
}

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

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

	char x, y;
	cin >> x >> y;
	char answer = '=';
	
	if (x - y > 0) {
		answer = '>';
	} else if (x - y < 0) {
		answer = '<';
	}
	
	cout << answer << endl;
	return 0;
}

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

int main()
{

    //freopen("input.txt","r",stdin);
    //ios_base::sync_with_stdio(false);cin.tie(0);
    //cout.precision(5);cout<<fixed;
    
    int n;
    cin>>n;
    
    if(n<=999)cout<<"ABC\n";
    else cout<<"ABD\n";
    
   return 0;
}



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

int main()
{
    long long x;
    scanf("%lld",&x);
    long long i;
    long long y=100;
    for(i=0;y<x;i++)
    {
        y=y+y*0.01;
    }
    printf("%lld\n",i);
    return 0;
}


Measured memory_bytes: 3816
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<cctype>
#include<cstring>
#include<utility>
const int inf=0x7fffffff;
typedef long long int ll;
using namespace std;
int a[105][105];
int b[105][105];
int main()
{
#ifdef DEBUG
	freopen("in", "r", stdin);
//	freopen("out", "w", stdout);
#endif
	int n,m,l;
	scanf("%d%d%d", &n,&m,&l);
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%d", &a[i][j]);
		}
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=l;j++){
			scanf("%d", &b[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=l;j++){
			ll sum=0;
			for(int k=1;k<=m;k++){
				sum+=a[i][k]*b[k][j];
			}
			printf("%lld",sum);
			if(j!=l)printf(" ");
		}
		printf("\n");
	}

	
	//insert code
	return 0;
}
//1_7_d.cc

Measured memory_bytes: 1288
#include <bits/stdc++.h>
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(), greater<ll>())
#define vfind(v, target) find(v.begin(), v.end(), target)
#define notFound(v, target) (vfind(v, target) == v.end())
#define ll long long
#define rep(i, s, g) for (ll i = (s); i < (g); i++)
#define MOD 1000000007
using namespace std;

int main()
{
  ll K; cin >> K;
  string S; cin >> S;
  if (S.size() <= K) cout << S << endl;
  else cout << S.substr(0, K) + "..." << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>=10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int k,int mod){
	int res=1,bas=x;
	while(k){
		if(k&1) res=1ll*res*bas%mod;
		bas=1ll*bas*bas%mod,k>>=1;
	}
	return res;
}
char s[7];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%s",s+1);
	if(s[3]==s[4]&&s[5]==s[6]) puts("Yes");
	else puts("No");
	return 0;
}

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

int main()
{
  int N, y;
  cin >> N >> y;
  bool flag = 0;
  
  for(int i=0; i<=N; i++){
    for (int j=0; j<=N; j++){
      if ( 10000*i + 5000*j + 1000*(N-i-j) == y){
        
        if (N-i-j < 0)
          continue;
        
        cout << i << ' ' << j << ' ' << N-i-j;
        flag = 1;
        break;
      }
    }
  if (flag == 1)
    break;
  }
  if (flag == 0)
    cout << "-1" << ' ' << "-1" << ' ' << "-1";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  string S;
  cin>>N>>S;
  for(char i:S){
    char a=(char)(int)i+N;
    if(a>'Z')
      a=a-('Z'-'A'+1);
    cout<<a;
  }
  cout<<endl;
}

Measured memory_bytes: 3620
let () =
  let rec swap () =
    let a,b = Scanf.sscanf (read_line()) "%d %d" (fun a b -> if a < b then a,b else b,a) in
    if a != 0 || b != 0 then
      begin
        print_int a;
        print_string " ";
        print_int b;
        print_string "\n";
        swap ()
      end
  in
  swap ()
;;


Measured memory_bytes: 4508
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9


int main(){
	map<char,int> st;
	for(int i=0;i<4;i++){
		char tmp;
		cin>>tmp;
		st[tmp] ++;
	}

	if(st.size() == 2){
	    	bool f = true;
		for(auto it :st )
			if(it.second != 2) f =false;
			if(f){
			    cout<<"Yes"<<endl;
			}else{
				cout<<"No"<<endl;
			}
		
	}else{
		cout<<"No"<<endl;
	}


	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define SIZE 1001


int judge(char a[],char b[], int i){
	int j;
	for(j=0;b[j]!='\0';j++){
		if(a[i+j]=='\0')return 0;
		if(a[i+j]!=b[j])return 0;
	}
	return 1;
}


int main(void){
	char T[SIZE],P[SIZE];
	int i;
	scanf("%s",T);
	scanf("%s",P);
	for(i=0;T[i]!='\0';i++){
		if(judge(T,P,i)==1){
			printf("%d\n",i);
		}
	}
	return 0;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
struct INF { template<class T> operator T() { return numeric_limits<T>::max() / 2; } } INF;


int main(){

    ll n, x, m;
    cin >> n >> x >> m;

    V<ll> t;
    set<ll> st;
    t.push_back(x);
    st.insert(x);

    int cnt = 1;
    ll last = 0;
    for(;;) {
        ll a = t.back();
        last = a*a % m;
        if(st.find(last) != st.end()) {
            break;
        }
        else {
            cnt++;
            t.push_back(last);
            st.insert(last);
        }
    }

    V<ll> sums(cnt+1);
    int idx = 0;
    Rep(i,cnt) {
        if(t[i-1] == last) idx = i;
        sums[i] = sums[i-1] + t[i-1];
    }

    idx--;
    if(n <= cnt) {
        cout << sums[n] << endl;
    }
    else {
        n -= idx;
        ll roop = sums[cnt] - sums[idx];
        ll ans = n / (cnt-idx) * roop;
        ans += sums[n % (cnt-idx) + idx];

        cout << ans << endl;
    }
}

Measured memory_bytes: 6372
#pragma GCC optimize(2,3,"Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define in inline
namespace fast_io
{
	char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0,ny;
	in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
	in ll read()
	{
		ll x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;Bi=1;if(nc<0)return nc;
		x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*ny;
	}
	in db gf() {int a=read(),y=ny,b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi)*y:a);}
	in int gs(char *s) {char c,*t=s;while(c=gc(),c<=32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
	in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
	in void flush() {if(C>1<<22) ot();}
	template <typename T>
	in void write(T x,char t)
	{
		int y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
		if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
	}
	in void write(char *s) {int l=strlen(s);for(int i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
#define pb push_back
const int N=55;
int n,c,l[N],p[N];ll f[N*6][N];
ll solve()
{
	for(int i=0;i<=n*c;i++) for(int s=0;s<(1<<(n-1));s++) f[i][s]=0;
	f[n*l[n]][0]=1;
	for(int i=0;i<n*c;i++) if((i%n))
	{
		int x=p[i%n];
		for(int s=0;s<(1<<(n-1));s++) if(!(s&(1<<(x-1))))
		for(int j=i;j<=n*c;j++) f[min(n*c,max(j,i+n*l[x]))][s|(1<<(x-1))]+=f[j][s];
	}
	return f[n*c][(1<<(n-1))-1];
}
int main()
{
	n=read(),c=read();for(int i=1;i<=n;i++) l[i]=read();
	sort(l+1,l+n+1);for(int i=1;i<n;i++) p[i]=i;
	db ans=0;
	do{ans+=solve();}while(next_permutation(p+1,p+n));
	for(int i=1;i<n;i++) ans/=i*c;printf("%.12lf",ans);
	return ot(),0;
}
//Author: disangan233

Measured memory_bytes: 3856
from collections import deque

def main():
    N, u, v, *AB = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]
    for a, b in zip(*[iter(AB)] * 2):
        E[a].append(b)
        E[b].append(a)

    def game(s):
        D = [-1] * (N + 1)
        D[s] = 0

        Q = deque([s])
        while Q:
            a = Q.popleft()
            for b in E[a]:
                if D[b] != -1:
                    continue
                D[b] = D[a] + 1
                Q.append(b)

        return D[1:]

    taka = game(u)
    aoki = game(v)

    print(-1 + max(a for t, a in zip(taka, aoki) if t < a))

main()


Measured memory_bytes: 31732
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "]"; return os; }


LL iabs(LL v){
    if(v < 0) return -v;
    return v;
}

int main(){
    LL n;
    cin >> n;
    vector<LL> a(n);
    LL total = 0;
    for(LL i = 0; i < n; ++i){
        cin >> a[i];
        total += a[i];
    }
    LL best = 0;
    for(LL i = 0; i < n; ++i){
        LL diff = iabs(total - a[i] * n);
        if(diff < iabs(total - a[best] * n)){
            best = i;
        }
    }
    cout << best << endl;
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  vector<int> L(N);
  for(int i=0;i<N;++i) cin>>L[i];
  sort(L.begin(), L.end());
  int index;
  int ans = 0;
  for(int i=0;i<N;++i) {
    for(int j=i+1;j<N;++j) {
      index = lower_bound(L.begin(), L.end(), L[i]+L[j])-L.begin()-1;
      ans += index-j;
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 3644
//Depth first search

#include<stdio.h>
#define N 100
#define FIR 0
#define SEC 1
#define FIN 2

int n,remain,count;
int arr[N][N];
int state[N],first[N],second[N];

void countime(int l)
{
  int b;
  state[l] = SEC;
  first[l] = ++count;
 
  for(b = 1; b <= n; b++)
    {
      if(arr[l][b] == 0) continue;
      if(state[b] == FIR) countime(b);
    }
  state[l] = FIN;
  second[l] = ++count;
}

void worktime()
{
  int l;
  //initialize number & array
  count = 0;
  for(l = 1; l <= n; l++) state[l] = FIR;

  //start counting
  for(l = 1; l <= n; l++)
    {
      if(state[l] == FIR)
	{
	  countime(l);
	}
    }

  //output data
  for(l = 1; l <= n; l++)
    {
      printf("%d %d %d\n",l,first[l],second[l]);
    }
}


int main()
{
  int i, j, l, b;
  
  //input data
  scanf("%d",&n);
  for(i = 1; i <= n; i++)
    {
      for(j = 1; j <= n; j++)
	{
	  arr[i][j] = 0;
	}
    }
  
  for(i = 1; i <= n; i++)
    {
      scanf("%d %d",&l,&remain);
   
      for(j = 1; j <= remain; j++)
	{
	  scanf("%d",&b);

	  // printf("\n %d \n",b);

	  arr[l][b] = 1;
	}
    }

  //work
  worktime();

  return 0;
}



Measured memory_bytes: 2084
N = int(input())
S = [list(str(input())) for i in range(N)]
tmp = []
li = []
for i in range(N):
    tmp += S[i]
tmp = list(set(tmp))
for j in range(len(tmp)):
    flag = "True"
    count = 10**9
    for k in range(N):
        if S[k].count(tmp[j])==0:
            flag = "False"
            break
        else:
            count = min(S[k].count(tmp[j]),count)
    if flag=="True":
        for c in range(count):
            li.append(tmp[j])
li.sort()
print(''.join(li))

Measured memory_bytes: 3064
#include<iostream>

using namespace std;
int main() {
  int a, b;
  cin >> a >> b;
  if (a+b>=a-b&&a+b>=a*b)
    cout << a+b << endl;
  else if (a-b>=a+b&&a-b>=a*b)
    cout << a-b << endl;
  else if (a*b>=a+b&&a*b>=a-b)
    cout << a*b << endl;
}


Measured memory_bytes: 256
#include <iostream>		 // cout, endl, cin
#include <string>		 // string, to_string, stoi
#include <vector>		 // vector
#include <algorithm>	 // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>		 // pair, make_pair
#include <tuple>		 // tuple, make_tuple
#include <cstdint>		 // int64_t, int*_t
#include <cstdio>		 // printf
#include <map>			 // map
#include <queue>		 // queue, priority_queue
#include <set>			 // set
#include <stack>		 // stack
#include <deque>		 // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>		 // bitset
#include <cctype>		 // isupper, islower, isdigit, toupper, tolower
using namespace std;

int main()
{
	int a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	long long ans = min(a + b, 2 * c) * min(x, y);
	if(x >= y){
		ans += min(a, 2 * c) * (x - y);
	}
	else{
		ans += min(b, 2 * c) * (y - x);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include<iomanip>
#include <string>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<math.h>
#include<stack>
#include<set>
#include<map>
#include<cstdlib>
#define INF 1001001001001001001
#define MAX 2001001

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

using namespace std;

int main() {
	long long int x, k, d;
	cin >> x >> k >> d;

	long long int ans;
	if (k < INF / d) {
		if (abs(x) - k * d > 0)ans = abs(x) - k * d;
		else {
			long long int t;
			t = abs(x) / d;
			ans = abs(x) % d;
			if ((k - t) % 2 == 1)ans = d - ans;
		}
	}
	else {
		long long int t;
		t = abs(x) / d;
		ans = abs(x) % d;
		if ((k - t) % 2 == 1)ans = d - ans;
	}
	cout << ans << endl;
}

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

int main() {
  int A, B, C, X;
  cin >> A >> B >> C >> X;
  
  int count = 0;
  for( int i = 0; i <= A; i++ ){ //500円玉
    for( int j = 0; j <= B; j++ ){ //100円玉
      for( int k = 0; k <= C; k++ ){ //50円玉
        if( i*500 + j*100 + k*50 == X ){
          count++;
        }
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
    int main(void){
    	int n;
    	int num[100000]={0};
    	int num_sum[100000]={0};
    	int i;
    	scanf("%d",&n);
    	int a[n];
    	for(i=0;i<n;i++){
    		scanf("%d",&a[i]);
    	}
    	for(i=0;i<n;i++){
    		num[a[i]]++;
    	}
    	for(i=0;i<99998;i++){
    		num_sum[i] = num[i]+num[i+1]+num[i+2];
    	}
    	int max = 0;
    	for(i=0;i<100000;i++){
    		if(max < num_sum[i]){
    			max = num_sum[i];
    		}
    	}
    	printf("%d",max);
    	return 0;
    }

Measured memory_bytes: 1280
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef int long long ll;

int g[5]={5,7,5,7,7};
int main() {
    int n;
    while(true){
        cin>>n;
        if(n==0)break;

        vector<int> s;
        rep(i,n){
            string ss;
            cin>>ss;
            s.push_back((int)ss.size());
        }

        for(int i=0;i<n;i++){
            int st=i;int prew=0;
            int ind=0;
            while(st<n&&ind<5){
                prew+=s[st];
                st++;
                if(prew==g[ind]){
                    prew=0;ind++;
                }else if(prew>g[ind]){
                    break;
                }
            }
            if(ind==5){
                cout<<i+1<<endl;
                break;
            }


        }


    }

    return 0;
}



Measured memory_bytes: 3044
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
cumsumA = []

total = 0
for a in A:
    total += a
    cumsumA.append(total)
cumsumA.append(0)

l = 0
r = 10 ** 6
while l + 1 < r:
    num = (l+r)//2
    pair_idx = n-1
    count = 0
    for a in A:
        while a + A[pair_idx] < num and pair_idx >= 0:
            pair_idx -= 1

        count += pair_idx+1

    if count < m:
        r = num
        continue
    elif count >= m:
        l = num


ans = 0
count = 0
num = l
pair_idx = n-1
for a in A:
    while a + A[pair_idx] < num and pair_idx >= 0:
        pair_idx -= 1

    count += pair_idx+1
    ans += cumsumA[pair_idx] + a*(pair_idx+1)

diff = count - m
ans -= num * diff
print(ans)

Measured memory_bytes: 56948
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    stack<int> St1;
    stack<pair<int, int> > St2;
    char ch;
    int sum = 0;

    for (int i = 0; cin >> ch; i++) {
        if (ch == '\\') St1.push(i);
        else if (ch == '/' && St1.size() > 0) {
            int j = St1.top(); St1.pop();
            int a = i-j;
            sum += a;
            while (St2.size() > 0 && St2.top().first > j) {
                a += St2.top().second; St2.pop();
            }
            St2.push(make_pair(j, a));
        }
    }

    vector<int> ans;
    while (St2.size() > 0) {ans.push_back(St2.top().second); St2.pop();}
    reverse(ans.begin(), ans.end());

    cout << sum << endl;
    cout << ans.size();

    for (int i = 0; i < ans.size(); i++) {
        cout << " ";
        cout << ans[i];
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 3116
while 1:
    n, i, j = map(int, input().split())
    if n+i+j == 0:
        break
    i = 2**n - i
    up = [0]*n
    for k in range(n):
        if 2**(n-1-k) <= i:
            up[k] = 1
            i = 2**(n-k)-1 - i
    up.reverse()
    ans = ""
    j -= 1
    for k in range(n):
        if up[k]==0 and j < 2**(n-1-k):
            j = j
            ans += "R"
        elif up[k] == 0 and 2**(n-1-k) <= j:
            j = j - 2**(n-1-k)
            ans += "L"
        elif up[k] == 1 and j < 2**(n-1-k):
            j = 2**(n-1-k)-1 - j
            ans += "L"
        elif up[k] == 1 and 2**(n-1-k) <= j:
            j = 2**(n-k)-1 - j
            ans += "R"
    print(ans)

Measured memory_bytes: 7660
#include <bits/stdc++.h>
#include <typeinfo>
#include <cxxabi.h>
#ifdef LOCAL
  #include "dbgtoki.hpp"
  #define DUMP(i) dump((string)TOSTRING(i), demangle(typeid(i).name()), __LINE__ , i) 
#else
  #define DUMP(i) 
#endif
 
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(s) (s).begin(), (s).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()) , v.end());

using namespace std;
typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;

struct Edge{
public:
  int from,to,cost;
  Edge(){}
  Edge(int _from,int _to,int _cost){
    from = _from;
    to = _to;
    cost = _cost;
  }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;


const int EPS = 1e-9;
const int MOD = 1e9+7;



int main (){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,w;
  cin >> a >> b >> w;
  ll ans = b/w - a/w;
  if(a % w == 0)ans ++;
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,q[40003];
long long ans,c[50];
int main(){
	cin>>n;
	char _a;
	for(int i=1,_n=n+1;i<_n;i++){
		cin>>_a;
		switch(_a){
			case 'R':
				q[i]=1;
				break;
			case 'G':
				q[i]=2;
				break;
			case 'B':
				q[i]=4;
				break;
		}
		c[q[i]]++;
	}
	ans=1ll*c[1]*c[2]*c[4];
	for(int i=1,_m=n-1;i<_m;i++){
		for(int j=i+1,_n=n+1;j<_n;j++){
			ans-=((q[i]|q[j]|q[j+j-i])==7);
		}
	}
	cout<<ans;
	return 0;
}



Measured memory_bytes: 3628
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;typedef vector<ll> vll;
#define fill(a) memset(a, 0, sizeof (a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define each(it,s) for(auto it = s.begin(); it != s.end(); ++it)
#define unq(v) sort(all(v)),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define getpos(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ff first
#define ss second
#define pb push_back

const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int maxn = 2000100;

int main(){
        _ios;

        int n,m;
        cin>>n>>m;
        string N;
        rep(i,n){
            N+= m + '0';
        }
        string M;
        rep(i,m){
            M+=n+'0';
        }
        cout<<min(N,M)<<endl;



return 0;
}







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

int main(){
    string S;
    cin>>S;
    if(S.at(0)==S.at(1) || S.at(1)==S.at(2) || S.at(2)==S.at(3)) cout<<"Bad"<<endl;
    else cout<<"Good"<<endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1L<<32;
ll fac[MAX], finv[MAX], inv[MAX];

int main(){
  string s;cin>>s;
  string ans=s.substr(0,3);
  cout<<ans<<endl;
}




Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

string s;
int k;
map<char, vector<int>> m;
int main() {
  while (cin >> s >> k) {
    m.clear();
    set<string> v;
    int len = s.length();
    for (int i = 0; i < len; ++i) {
      m[s[i]].push_back(i);
      // printf("i = %d\n", i);
    }
    for (auto it : m) {
      // cout << it.first << " -> ";
      for (auto i : it.second) {
        // cout << i << ' ';
        for (int j = 1, cnt = 0; cnt < k && i+j <= len; ++cnt, ++j) {
          v.insert(s.substr(i, j));
        }
      }
      if (v.size() >= k) {
        break;
      }
    }
    int i = 0;
    for (auto it : v) {
      ++i;
      if (i == k) {
        cout << it << ' ';
        break;
      }
    } cout << endl;
    // break;
    // for (int i = 0; i < len; ++i) {
    //   for (int j = 1; i+j <= len; ++j) {
    //     v.push_back(s.substr(i, j));
    //   }
    // }
    // cout << "s=" << s << endl;
    // for (auto it : v) {
    //   cout << it << ' ';
    // } cout << endl;
    // sort(v.begin(), v.end());
    // auto it = unique(v.begin(), v.end());
    // v.resize(distance(v.begin(),it));
    // cout << v[k-1] << endl;
    // for (auto it : v) {
    //   cout << it << ' ';
    // } cout << endl;
  }
}


Measured memory_bytes: 384
def main():
    N, M = map(int, input().split())
    drink = [list(map(int, input().split())) for _ in range(N)]
    drink.sort(key=lambda x: x[0])

    ans = 0
    for d in drink:
        if M <= d[1]:
            ans += d[0] * M
            print(ans)
            exit()
        else:
            ans += d[0] * d[1]
            M -= d[1]


if __name__ == "__main__":
    main()


Measured memory_bytes: 29020
# -*- coding: utf-8 -*-
N = int(input())
A = [int(v) for v in input().split(' ')]

# 負の数が偶数 -> 全部+にできる
# 負の数が奇数 -> どれか一つが-になる
# 負の数の偶奇チェック
sign = 1
for a in A:
    if a != 0:
        sign *= a/abs(a)

abs_A = [abs(a) for a in A]

if sign > 0:
    print(sum(abs_A))
else:
    print(sum(abs_A)-min(abs_A)*2)

Measured memory_bytes: 14412
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H, N;
  cin >> H >> N;
  vector<pair<int, int>> magic(N);
  for(auto&& x:magic){
    cin >> x.first >> x.second; 
  }
  const int INF = (int)1e9+7;
  vector<int> dp(H+1, INF);
  dp[0] = 0;
  function<int(int)> solve
    = [&](int n){
    if(n < 0) return 0;
    if(dp[n] != INF) return dp[n];
    for(auto&& x:magic){
      dp[n] = min(
        dp[n],
        solve(n-x.first) + x.second);
    }
    return dp[n];
  };
  solve(H);
  cout << dp[H] << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define mod 998244353
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
const int maxn=1e5+10;
int dp[maxn][4];
vector<int> g[maxn];
int n,m;
int S,T;
queue<pii> que;
int main()
{
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&u,&v);
		g[v].emplace_back(u);
	}
	scanf("%d%d",&S,&T);
	memset(dp,-1,sizeof(dp));
	dp[T][0]=0;
	que.push(make_pair(T,0));
	pii cur;
	int sta,cst;
	while(!que.empty())
	{
		cur=que.front();
		que.pop();
		sta=(cur.second+1)%3;
		cst=dp[cur.first][cur.second];
		if(sta==0)cst++;
		for(int i=0;i<g[cur.first].size();i++)
		{
			int &to=g[cur.first][i];
			if(dp[to][sta]==-1)
			{
				dp[to][sta]=cst;
				que.push(make_pair(to,sta));
			}
		}
	}
	printf("%d\n",dp[S][0]);
	return 0;
}

Measured memory_bytes: 7296
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int count = 0;
        
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        
        if ( a == b && a == c ) {
            System.out.println( 1 );
        } else if ( a == b || a == c || b == c ){
            System.out.println( 2 );
        } else {
            System.out.println( 3 );
        }
    }
}

Measured memory_bytes: 9680
#include <stdio.h>

int main(void) {
	int N, i;
	scanf("%d", &N);
	int a[N];
	int count = 0;
	for(i = 0; i < N; i++){
		scanf("%d", &a[i]);
		while(a[i] % 2 == 0){
			a[i] = a[i] / 2;
			count++;
		}
	}

	printf("%d", count);
	
	return 0;
}

Measured memory_bytes: 256
from sys import stdin


def main():
    _ = int(stdin.readline().rstrip())
    Bs = [int(x) for x in stdin.readline().rstrip().split()]
    result = Bs[0]
    for i, B in enumerate(Bs[:-1]):
        result += min(B, Bs[i + 1])
    result += Bs[-1]
    print(result)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int L =sc.nextInt();
		int a = 0;
		int[] b = new int[N];
		for (int i = 1; i <= N; i++) {
			a += L + i - 1;
			for (int j = 1; j <= N; j++) {
				if (i != j) {
					b[j-1] += L + i -1;
				}
			}
		}
		int near = 100000;
		int ans = 0;
		for (int i = 0; i < N; i++) {
			int abs = Math.abs(a - b[i]);
			if (abs < near) {
				ans = b[i];
				near = abs;
			}
		}
		System.out.println(ans);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

Measured memory_bytes: 21332
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, a, b) for(ll i = ll(a); i <= ll(b); i++)
int main()
{
	ll n,x,cnt=0,p;
	cin>>n>>x;
	vector<ll> v;
	REP(i,0,n-1)
	{
		cin>>p;
		v.push_back(p);
	}
	sort(v.begin(),v.end());
	REP(i,0,n-1)
	{
		if(v[i]>x)
			break;
		x=x-v[i];
		cnt++;
		v[i]=0;
		if(x<v[i+1])
			break;
	}
	ll total=accumulate(v.begin(),v.end(),0);
	if(x>total)
		cnt--;
	cout<<cnt;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int i,j,n,u,k,v;
  int data[101][101];
  scanf("%d",&n);
  for( i = 1; i <= n; i++){
    for( j = 1; j <= n; j++){
      data[i][j]=0;
  	  }
  }
  for(i = 0; i < n; i++){
    scanf("%d",&u);
    scanf("%d",&k);
    for(j = 0; j < k; j++){
      scanf("%d",&v);
      data[u][v]=1;
	}
  }

  for(i = 1;i <=n;i++ ){
    for(j = 1; j <=n;j++){
      if(j==n){
	printf("%d",data[i][j]);
      }else{
	printf("%d ",data[i][j]);
      }
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const ll INF = 1001001001;
const ll LINF = 1001001001001001001;

void prvec(vector<ll> vec){
    ll n = vec.size();
    rep(i,n) cout << i << " " << vec.at(i) << "\n";
}

void pr2d(vector<vector<ll>> vvec){
    ll h = vvec.size();
    ll w = vvec.at(0).size();
    rep(i,h){
        rep(j,w){
            cout << vvec.at(i).at(j) << " ";
        }
        cout << "\n";
    }
}

int main(){
    ll n ;
    cin >> n;
    vector<ll> a(1000001,1);
    a.at(0) = 0;
    a.at(1) = 0;
    for(int i=2;i<=1000;i++){
        if(!a.at(i)) continue;
        ll x = i;
        while(true){
            x+=i;
            if(x>1e6) break;
          	a.at(x) = 0;
        }
    }

    vector<ll> b(1000001,0);
    rep(i,n){
        ll x; cin >> x;
        b.at(x)++;
    }
    bool pairwise = 1;
    bool setwise = 1;

    rep(i,1000001){
        if(!a.at(i)) continue;
        ll cnt = 0;
        ll x = i;
        while(x<=1e6){
            if(b.at(x)) cnt+=b.at(x);
            x+=i;
        }
        if(cnt>1) pairwise = 0;
        if(cnt==n){
            pairwise = 0, setwise = 0;
            break;
        }
        //cout << i << " " << cnt << endl;
    }
  	//cout << setwise << endl;
    if(pairwise){
        cout << "pairwise coprime" << endl;
    }else if(setwise){
        cout << "setwise coprime" << endl;
    }else{
        cout << "not coprime" << endl;
    }
    return 0;
}

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

 
int main(){
     
    int x, y, z;
    cin >> x >> y >> z;
    cout << (x-z)/(y+z) << endl;
    
    
}



Measured memory_bytes: 256
object Main extends App {
	val N = scala.io.StdIn.readInt
	val L = scala.io.StdIn.readLine.split(" ").map(_.toLong)

	val a = new Array[Long](N)

	a(0) = L(0)

	for(i<-1 until N){
		a(i) = a(i-1) + L(i)
	}
	
	var test = (2*a(0)-a(N-1)).abs

	for(i<-1 until N-1){
		val temp = (2*a(i)-a(N-1)).abs

		if(temp < test) test = temp
	}

	println(test)

}


Measured memory_bytes: 75136
# https://atcoder.jp/contests/m-solutions2019/submissions/5741430
from functools import reduce
from operator import mul
import sys

input = sys.stdin.readline

MOD = 10 ** 6 + 3


def mod_mul(x, y):
    return mul(x, y) % MOD


fact = [1]
for n in range(1, MOD):
    fact.append((fact[-1] * n) % MOD)
    # d>1 の数列を d=1 となる数列に変換する
    # MODの倍数を含む数列の積は0になるので,
    # MODの倍数を含まない区間の積が計算できればよい
    # そのような区間の右端はMOD-1であり,fact[MOD-1]が計算できればよい

inv_fact = [-1] * MOD
inv_fact[MOD - 1] = pow(fact[-1], MOD - 2, MOD)
for n in range(MOD - 2, -1, -1):
    inv_fact[n] = ((inv_fact[n + 1] * (n + 1)) % MOD)
    # inv_factは,inv(n!)にn,n-1,...を掛けるイメージ

Q = int(input())
ans = []
for _ in range(Q):
    x, d, n = map(int, input().split())

    if x == 0:
        ans.append(0)
        continue

    if d == 0:
        ans.append(pow(x, n, MOD))
        continue

    xd = (x * pow(d, MOD - 2, MOD)) % MOD
    if xd == 0:
        ans.append(0)
        continue

    if MOD - xd < n:
        ans.append(0)
        continue

    dn = pow(d, n, MOD)
    ans.append(reduce(mod_mul, (fact[xd + n - 1], inv_fact[xd - 1], dn)))
print(*ans, sep='\n')
# 逐次printより,最後に一括が速いかどうか
# python3では
# reduce,mod_mulなしのans一括と
# 逐次printのreduce,mod_mulありが同速度だった
# pypyだと速くなった気がする


Measured memory_bytes: 88912
#include <cstdio>
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
#include <cmath>
#include <iomanip>
#include <regex>
#include <queue>
#include <set>
#include <cassert>
using namespace std;
using ll = long long;
using plong = pair<ll,ll>;
const long MOD = 1000000007;

int main(){
    double A,B,H,M;
    cin>>A>>B>>H>>M;
    double ax = A * (cos((H*60.0+M)/720.0 * 2 * M_PI));
    double ay = A * (sin((H*60.0+M)/720.0 * 2 * M_PI));
    double bx = B * (cos(M/60.0 * 2 * M_PI));
    double by = B * (sin(M/60.0 * 2 * M_PI));

    double res = sqrt(pow(ay-by,2)+pow(ax-bx,2));
    printf("%.20f\n",res);
}


Measured memory_bytes: 4164
import math
words = lambda t : list(map(t, input().split()))
x,y = words(int)

MOD = 10**9+7

def modpow(a,b,mod):
    if b == 0: return 1
    if b % 2 == 0:
        h = modpow(a, b//2, mod)
        return (h * h) % mod
    else:
        return (a * modpow(a, b-1, mod)) % mod

def mod_comb(a,b,mod):
    #print(a,b)
    if a-b < b: return mod_comb(a,a-b,mod)
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a-i
        ans_div *= i+1
        ans_mul %= mod
        ans_div %= mod
    return (ans_mul * modpow(ans_div, mod-2, mod)) % mod


if (x+y) % 3 != 0:
    print(0)
elif x < (x+y)//3 or y < (x+y)//3:
    print(0)
else:
    k = (x + y) // 3
    #print(k, k, y-k)
    ans = mod_comb(k,y-k,MOD)
    print(ans)


Measured memory_bytes: 38512
import numpy as np

N, D = map(int, input().split())

X = []
for i in range(N):
    x = [int(n) for n in input().split()]
    X.append(x)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        distance = 0
        for k in range(D):
            distance += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k])
        distance = np.sqrt(distance)
        if distance.is_integer():
            ans += 1
print(ans)


Measured memory_bytes: 14440
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;


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


int main() {
	string str; cin >> str;

	int left = 0;
	int right = str.size() - 1;

	string L = "";
	string R = "";
	char x = 'x';
	int ans = 0;
	while(str.size() > 1) {
		if (str[0] == str[right]) {
			str = str.substr(1,str.size() - 2);
		}else if (str[0] != x and str[right] != x) {
			cout << -1 << endl;
			return 0;
		}else if (str[0] == x) {
			str = str + "x";
			ans++;
		}else if (str[right] == x) {
			str = "x" + str;
			ans++;
		}
		right = str.size() - 1;
	}

	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 628
#include<bits/stdc++.h>
#define ll long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;
const long double EPS = 0.0000000001;
const long double PI = (acos(-1));
const int MOD = 1000000007;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")




int main() {


    ll n,m; cin >> n;
    ll big;
    vector<ll> a(n),b(n);


    rep(i,n){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(a.begin(),a.end());
    big = a[n-1];
    if(big%2 == 0) m = big/2;
    else m = big/2+1;


    rep(i,n-1){
        a[i] = abs(a[i]-m);
    }

    sort(a.begin(),a.end()-1);

    cout << big << " ";
    if(find(b.begin(),b.end(),m-a[0]) == b.end()){
        cout << m + a[0];
    }else cout << m - a[0];

    return 0;
}


Measured memory_bytes: 4736