akhauriyash/Code-Regression huggingface dataset:
#include<iostream> 
#include<vector> 
#include<algorithm> 
#include<iomanip> 
#include<stack> 
#include<unordered_map>
#include<queue> 
#include<map>
#include<climits>
#include<set> 
#include<string> 
//#include<bits/stdc++.h> 
using namespace std; 
#define lld long long int 
#define eb emplace_back
//to insert pair use eb
#define mp make_pair
#define fi first
#define se second
#define pb push_back

#define X 1000000007
#define Y 998244353
#define E4 10000
#define E5 100000
#define E6 1000000
#define inf 1001001001
#define longinf 2001001001001001001
#define pi 3.1415926535

# define rec2(i,a,b) for(lld i=a;i<b;i++) 
#define rec(i,n) for(lld i=0;i<n;i++)
#define rev(i,a,b) for(lld i=b-1;i>=a;i--)
#define all(v) (v).begin(), (v).end()
#define large(v)  *max_element(all(v))
#define small(v)  *min_element(all(v)) 
#define v vector
const double EPS = 1e-6;

void google(int i)
{  cout<<"Case #"<<i<<":"<<endl; }

//prime sieve if needed 
//prime factors of number
lld prime[E6+1]; 
void sieve(lld n) 
{ rec(i,n+1) 
    prime[i]=1; 
   for(lld i=2;i*i<=n;i++) 
     { if(prime[i]!=1) 
          continue; 
         for(lld j=i*i;j<=n;j=j+i) 
          if(prime[i]==1)
           prime[j]=i; 
      }
}

lld gcd(lld a,lld b)
{
    if(a==0)
     return b; 
    return gcd(b%a,a); 
}

//fermat a^(m-2)%mod
lld binarymul(lld a,lld n,lld m)
{  lld res=1; 
 while(n) 
  { if(n%2) 
      { res=(res*a)%m; 
         n--; 
      } 
     a=(a*a)%m; 
     n/=2; 
  }
  return res; 
}
void contest(); 
int main()
{
   ios_base::sync_with_stdio(false); 
   cin.tie(0);
     #ifdef PUNEET_GOEL
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif
   //sieve(E6); 
    lld t; 
//    cin>>t; 
t=1; 
    rec(i,t) 
    {
     //google(i+1); 
      contest(); 
    }
	return 0;
}

void contest()
{ 
  lld n; 
  cin>>n; 
 string a; 
 cin>>a; 
 lld ans=0; 
  lld s=0,e=n-1; 
   while(s<=e) 
    { 
     if(a[s]=='R')
      { 
       while(s<=e && a[s]=='R') 
         s++; 
      }
     if(a[e]=='W')
      { 
       while(s<=e && a[e]=='W')
        e--; 
      } 
     if(s<e) 
      { swap(a[s],a[e]); 
         ans++; 
      }
    }
 //   cout<<a<<endl; 
   cout<<ans<<endl; 
}

Measured memory_bytes: 3780
#include<iostream>
#include<algorithm>
using namespace std;
int rui(int a,int b){
	if(b==0)return 1;
	return a*rui(a,b-1);
}
int main(){
	int N,P=0,Q=0,pre,num=0,re,a=0,b=0;
	bool te[10],flag;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>re;
		P+=re;
		P*=10;
	}
	P/=10;
	for(int i=0;i<N;i++){
		cin>>re;
		Q+=re;
		Q*=10;
	}
	Q/=10;
	for(int i=rui(10,N-1);i<rui(10,N);i++){
		pre=i;
		flag=false;
		for(int j=0;j<10;j++)te[j]=false;
		for(int j=0;j<N;j++){
			if(te[pre%10]||pre%10>N||pre%10==0){flag=true;break;}
			te[pre%10]=true;
			pre/=10;
		}
		if(!flag)num++;
		if(i==P)a=num;
		if(i==Q)b=num;
		if(a!=0 && b!=0)break;
	}
	cout<<max(a-b,b-a);
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

#define ABS(a) ((a) > (0) ? (a) : -(a))

i32 gcd (i32 a, i32 b) {
  a = ABS(a);
  b = ABS(b);
  if (a == 0) return b;
  if (b == 0) return a;
  i32 r = a % b;
  while (r > 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

int cmp (const void *a, const void *b) {
  i32 d = *(i32 *)a - *(i32 *)b;
  return d == 0 ? 0 : d < 0 ? -1 : 1;
}

void run (void) {
  i32 n;
  scanf ("%" SCNi32, &n);
  i32 *a = (i32 *) calloc (n + 1, sizeof (i32));
  for (i32 i = n; i >= 0; --i) {
    scanf ("%" SCNi32, a + i);
  }
  uint8_t *p = (uint8_t *) calloc (n + 1, sizeof (uint8_t));
  for (i32 i = 2; i <= n; ++i) {
    p[i] = 1;
  }
  for (i32 i = 2; i * i <= n; ++i) {
    if (p[i] == 0) continue;
    for (i32 j = i * i; j <= n; j += i) {
      p[j] = 0;
    }
  }
  i64 *dp = (i64 *) calloc (n + 1, sizeof (i64));
  i32 *ans = (i32 *) calloc (n + 1 + 30, sizeof (i32));
  i32 len = 0;
  for (i32 i = 2; i <= n; ++i) {
    if (p[i] == 0) continue;
    for (i32 j = 0; j <= n; ++j) {
      dp[j] = a[j];
    }
    const i32 prime = i;
    for (i32 j = n; j >= prime; --j) {
      dp[j - prime + 1] += dp[j];
      dp[j] = 0;
    }
    i32 ok = 1;
    for (i32 j = prime - 1; j >= 0; --j) {
      if (dp[j] != 0 && dp[j] % prime != 0) {
	ok = 0;
      }
    }
    if (ok) {
      ans[len++] = prime;
    }
  }
  i32 g = ABS(a[0]);
  for (i32 i = 1; i <= n; ++i) {
    g = gcd (g, a[i]);
  }
  for (i32 i = 2; i * i <= g; ++i) {
    if (g % i != 0) continue;
    ans[len++] = i;
    while (g % i == 0) {
      g /= i;
    }
  }
  if (g > 1) {
    ans[len++] = g;
  }
  qsort (ans, len, sizeof (i32), cmp);
  for (i32 i = 0; i < len; ++i) {
    if (i > 0 && ans[i - 1] == ans[i]) continue;
    printf ("%" PRIi32 "\n", ans[i]);
  }
}

int main (void) {
  run();
  return 0;
}


Measured memory_bytes: 384
## code borrowed from "maspy"

import numpy as np
import sys
buf = sys.stdin.buffer
 
H,W = map(int,buf.readline().split())
# 周りに壁を、0,1化、壁を0で持つ
grid = np.zeros((H+2,W+2),dtype=np.bool)
grid[1:-1,1:] = (np.frombuffer(buf.read(H*(W+1)),dtype='S1') == b'.').reshape((H,W+1))
 
# x軸方向の集計
def F(transpose):
  x = grid
  if transpose:
    x = (x.T).copy()
  x = np.ravel(x) # to 1D array
  L = len(x)
  
  left_zero = np.where(x,0,-np.arange(L)) # 左の壁のindexの-1倍
  np.minimum.accumulate(left_zero, out=left_zero)
  
  right_zero = np.where(x[::-1],0,np.arange(L)) # 逆順ソートした上で左の壁のindex
  np.maximum.accumulate(right_zero, out=right_zero)
  
  y = left_zero
  y += L-right_zero[::-1]
  
  return y.reshape(grid.T.shape).T if transpose else y.reshape(grid.shape)
  
answer = (F(False) + F(True)).max()-5
print(answer)

Measured memory_bytes: 208108
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, n) for (int i = 1; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int A, B, C;
    cin >> A >> B >> C;

    int mod = (A%2) + (B%2) + (C%2);

    int cnt = 0;
    if (mod == 3 || mod == 0) {

    }
    else {
        cnt++;
        int target = mod == 1 ? 1 : 0;
        if (mod == 1) {
            A += (A%2) == 0 ? 1 : 0;
            B += (B%2) == 0 ? 1 : 0;
            C += (C%2) == 0 ? 1 : 0;
        }
        else {
            A += (A%2) == 0 ? 0 : 1;
            B += (B%2) == 0 ? 0 : 1;
            C += (C%2) == 0 ? 0 : 1;
        }
    }

    int ma = max(max(A, B), C);
    cnt += (ma - A) / 2;
    cnt += (ma - B) / 2;
    cnt += (ma - C) / 2;

    put(cnt);

    return 0;
}

Measured memory_bytes: 3584
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll mod=1e9+7;
ll N;
ll memo[100010][2];
bool vis[100010][2];
vector<int>v[100010];
ll sol(int pos,int prec,bool col){//0=nero
  if(vis[pos][col])return memo[pos][col];
  vis[pos][col]=1;
  ll t=1;
  for(int i=0;i<v[pos].size();i++){
    if(v[pos][i]==prec)continue;
    t*=(sol(v[pos][i],pos,1)+sol(v[pos][i],pos,0)*col)%mod;
    t%=mod;
  }
  return memo[pos][col]=t%mod;
}
signed main(){
		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
		cin>>N;
		for(ll i=0;i<N-1;i++){
      int a,b;
      cin>>a>>b;
      a--;b--;
      v[a].push_back(b);
      v[b].push_back(a);
		}
		cout<<(sol(0,-1,0)+sol(0,-1,1))%mod;
    return 0;
}

Measured memory_bytes: 51968
/*
  Input: the input contains many data sets. First line in 
each data set are two integers: N (no of intervals) and M 
(amount of funding). There will be N lines ollowing the 
first line, and each line contains two integers: Di 
(distance of interval i) and Pi (level of danger of intercal
i). Imput ends when N=0, M=0 data set appears.

  Order of computation: we can compute the order of 
computation for each data set:
	3N+2N*log2(N)+MN+N => Order=4N+MN+2N*log2(N)

  The program takes 0.29 second to solve 93 cases.
*/

#include <algorithm>
#include <iostream>
#include <utility>
#include <math.h>
using namespace std;

int N, M; // N: No of intervals, M: funding
pair<int,int> PD[10010];
int main(){
	// put in data
	while (cin >> N >> M && N){
		int d, p; // d: distance, p: lv of danger
		for (int i=0; i<N; ++i){ 
		//Order=3N
			cin >> d >> p; 
			// Not sure whether this counts as 1 or 2
			PD[i] = make_pair(p, d);
		}
	// sort
		sort(PD, PD+N, greater<pair<int, int> >()); // modified
		// Order=2N*log2(N) 
		// I doubled complexity since it is a pair (not sure as well)
	// hire guards
		int result = 0;
		for( int index=0; index<N; index++) {
    if ( M > 0 ) {
    M -= PD[index].second;
        if ( M < 0 ) {
            result += -M * PD[index].first;
        }
    } else {
        result += PD[index].first*PD[index].second;
    }
}

	cout << result << endl;
	}
}

Measured memory_bytes: 3136
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
	int X, Y;
	cin >> X >> Y;

	if (X % Y == 0) {
		cout << -1 << endl;
	} else {
		rep(i, 10000000) {
			int num = i * X;
			if (num % Y) {
				cout << num << endl;
				return 0;
			}
		}
	}

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p=998244353;
int32_t main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t,n,i,j,k,l,r,l1;
    cin>>n>>k;
    vector<pair<int,int> > v;
    for(i=1;i<=k;i++)
    {
        cin>>l>>r;
        v.push_back({l,r});
    }
    sort(v.begin(),v.end());
  int dp[n+1];
  memset(dp,0,sizeof(dp));
 dp[0]=0;dp[1]=1;
 int dp1[n+1];
 dp[0]=0;
 dp[1]=1;
 dp1[0]=0;dp1[1]=1;
 for(i=2;i<=n;i++)
 {
     for(j=0;j<v.size();j++)
     {
         l=v[j].first,k=v[j].second;
         k=min(k,i);
         if(l<=k)
          {
              if(i==k)
               l1=((dp1[i-l]-dp1[i-k])%p+p)%p;
              else
               l1=((dp1[i-l]-dp1[i-k-1])%p+p)%p;
              dp[i]=(dp[i]+l1)%p;
          }
     }
     dp1[i]=(dp[i]+dp1[i-1])%p;
 }
    cout<<dp[n]%p;
}


Measured memory_bytes: 6728
N, K = map(int, input().split())
ans = [0] * N
for i in range(K):
    d = int(input())
    Alist = list(map(int, input().split()))
    for a in Alist:
        ans[a-1] += 1
c = 0
for i in range(N):
    if ans[i] == 0:
        c += 1
print(c)

Measured memory_bytes: 9180
#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
#define pb push_back
#define ld long double
#define pa pair<int,int>
#define pii pair<ll,ll>
#define st first
#define nd second
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

int main()
{
  BOOST;
  ll h;
  cin>>h;
  ll s=1;
  while (s<=h)s*=2;
  cout<<s-1;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int month, day, i;
	while (1){
		scanf("%d%d", &month, &day);
		if (month == 0) break;
		for (i = 2; i <= month; i++){
			switch(i){
				case 3:
					day += 29; break;
				case 5:
				case 7:
				case 10:
				case 12:
					day += 30; break;
				case 2:
				case 4:
				case 6:
				case 8:
				case 9:
				case 11:
					day += 31; break;
			}
		}
		switch(day%7){
			case 1: printf("Thursday\n"); break;
			case 2: printf("Friday\n"); break;
			case 3: printf("Saturday\n"); break;
			case 4: printf("Sunday\n"); break;
			case 5: printf("Monday\n"); break;
			case 6: printf("Tuesday\n"); break;
			case 0: printf("Wednesday\n"); break;
		}
	}
	return 0;
}

Measured memory_bytes: 580
while True:
    m,f,r=map(int,input().split())
    if m==-1 and f==-1 and r==-1:
        break
    if m+f>=80:
        print('A')
    if m+f>=65 and m+f<80:
        print('B')
    if m+f>=50 and m+f<65:
        print('C')
    if m+f>=30 and m+f<50:
        if m==-1 or f==-1:
            print('F')
        elif r>=50:
            print('C')
        else:
            print('D')
    if m+f<30:
        print('F')


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

using namespace std;

int n, dx[100005], dy[100005];
pair <int, int> a[100005];
char s[5];

double solve(double t) {
	double xmx = -1e18;
	double xmn = 1e18;
	double ymx = -1e18;
	double ymn = 1e18;
	
	for (int i = 0; i < n; i++) {
		double x = t * dx[i] + a[i].first;
		double y = t * dy[i] + a[i].second;
		xmx = max(xmx, x);
		xmn = min(xmn, x);
		ymx = max(ymx, y);
		ymn = min(ymn, y);
	}
	
	return (xmx - xmn) * (ymx - ymn);
}

int main() {
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) {
		scanf("%d%d%s", &a[i].first, &a[i].second, s);
		if (s[0] == 'U') dy[i] = 1;
		else if (s[0] == 'D') dy[i] = -1;
		else if (s[0] == 'L') dx[i] = -1;
		else dx[i] = 1;
	}
	
	double lb = 0.0;
	double ub = 1e9;
	double res = 1e18;
	
	for (int i = 0; i < 200; i++) {
		double lmid = (lb * 2 + ub) / 3;
		double rmid = (lb + ub * 2) / 3;
		double lv = solve(lmid);
		double rv = solve(rmid);
		
		res = min(res, lv);
		res = min(res, rv);
		
		if (lv > rv) lb = lmid;
		else ub = rmid;
	}
	
	printf("%.12lf\n", res);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n; cin >> n;
    vi a(n);
    rep(i, n){
        cin >> a[i];
        a[i]--;
    }
    ll cnt = 0;
    rep(i, n) if(i == a[a[i]]) cnt++;
    cout << cnt/2 << endl;
}

Measured memory_bytes: 3964
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    string s;
    cin>>s;
    int k=s.size();
    int maxn=k;
    for(int i=0;i<k-1;i++)
    {
        if(s[i]!=s[i+1])maxn=min(maxn,max(i+1,k-i-1));
    }
    cout<<maxn<<endl;
    return 0;
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

const int N = 505;

int i, n, m, q, x, y, dp[N][N];
vector<int> v[N];

int solve(int x, int y) {
  if(dp[x][y] != -1) return dp[x][y];

  int &r = dp[x][y];
  r = 0;
  for(int i = x; i <= y; ++i) {
    int st = 0, dr = v[i].size() - 1, ans = 0;
    while(st <= dr) {
      int pivot = (st + dr) / 2;
      if(v[i][pivot] <= y) ans = pivot + 1, st = ans;
      else dr = pivot - 1;
    }
    r += ans;
  }
  return r;
}

int main() {
  memset(dp, -1, sizeof(dp));
  scanf("%d %d %d", &n, &m, &q);
  while(m--) {
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
  }

  for(i = 1; i <= n; ++i) sort(v[i].begin(), v[i].end());

  while(q--) {
    scanf("%d %d", &x, &y);
    printf("%d\n", solve(x, y));
  }

  return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
double dp[301][301][301];
double solve(int x,int y,int z,int &n)
{
    if(x<0||y<0||z<0)
    return 0;
    if(x==0 && y==0 && z==0)
    return 0;
    if(dp[x][y][z] > -0.9)
    return dp[x][y][z];
    int rem = x+y+z;
    double exp = n + x*solve(x-1,y,z,n) + y*solve(x+1,y-1,z,n) + z*solve(x,y+1,z-1,n);
    return dp[x][y][z] = exp/rem;  
}
int main() 
{
    int n;
    cin>>n;
    memset(dp,-1,sizeof dp);
    int x;
    int first = 0,second = 0,third = 0;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(x==1)
        first++;
        else if(x==2)
        second++;
        else if(x==3)
        third++;
    }
    cout<<fixed<<setprecision(10)<<solve(first,second,third,n);
}


Measured memory_bytes: 213376
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int d = sc.nextInt();
		int n = sc.nextInt();
		sc.close();
		int h = (int) Math.pow(100,d);
		int present = h*n;
		if(n == 100) {
			present+=h;
		}
		System.out.println(present);
	}
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main() {
ll n,k;
cin>>n>>k;
ll a[n+1];
for(ll i=1;i<=n;i++){
cin>>a[i];
}
if(k>=n)
cout<<0<<endl;
else{
    sort(a+1,a+n+1);
    ll sum=0;
    for(ll i=1;i<=n-k;i++){
    sum+=a[i];}
    cout<<sum<<endl;
}
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

#define rep(i, n)      for (int i=0; i<int(n); i++)
#define rep3(i, s, n)  for (int i=int(s); i<int(n); i++)
#define rev_rep(i, n)  for (int i=int(n)-1; i>=0; i-=1)

#define MAX_N 110

int N, M;
int A[MAX_N];

int main() {
  cin >> N >> M;
  rep3(i, 1, N+1) cin >> A[i];

  // simuration
  rep3(k, 1, M+1) {
    int i = 1; // ?????????????????£???????????????
    while (true) {
      if (1 <= i && i <= N-1) {
        if ((A[i] % k) > (A[i+1] % k)) {
          // swap
          int g = A[i+1];
          A[i+1] = A[i];
          A[i]   = g;
          i = i + 1;
        }
        else {
          i = i + 1;
        }
      }
      if (i == N) {
        break;
      }
    }
  }
  rep3(i, 1, N+1) {
    cout << A[i] << "\n";
  }
  return 0;
}

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

#define mod 1000000007
#define LOCAL 0
#define pb push_back
#define ll long long

ll po(ll a,ll b){
	ll x = 1,y=a;
	while(b>0){
		if(b%2){
			x = x*y;
			x %= mod;
		}
		y=y*y;
		y%=mod;
		b/=2;
	}
	return x;
}

int main(){
	if(LOCAL){
    	freopen("C:/Users/gold/Desktop/sublime IO/input.txt","r",stdin);
    	freopen("C:/Users/gold/Desktop/sublime IO/output.txt","w",stdout);
	}
	int T = 1;
	//scanf("%d",&T);
	while(T--){
		int n;
		static ll a[2000005];
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%lld",&a[i]);
		}	
		sort(a,a+n);
		ll sum = a[0];
		int s = 0;
		for(int i=1;i<n;i++){
			if(a[i]>2ll*sum){
				s = i;
			}
			sum += a[i];
		}
		printf("%d\n",n-s);
	}
	return 0;	
}

Measured memory_bytes: 1024
//Written by Rhitwik Saha//
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define mp          make_pair
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vb          vector<bool>
#define vc          vector<char>
#define vii         vector<pii>
//#define mi          map<int,int>
//#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define ub(x)       upper_bound(x)
#define lb(x)       lower_bound(x)
#define endl        '\n'
#define file        freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define fastio      ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
// #define N 			1e5+5
#define M           1000000007
#define MAX         100005
#define mem0(a)     memset(a,0,sizeof(a))
#define prec        cout<<std::setprecision(9)<<std::fixed
#define forn(i,a,b)  for(int i=a;i<b;i++)
const double long rf=1e-14;
int i,j,k;

void Anon_mouS(){
	double long a,b,c;
    cin >> a >> b >> c;
    cout << ( sqrt(a) + sqrt(b) + rf < sqrt(c) ? "Yes" : "No" );
}

int32_t main(){
    fastio;
    // file;
    // sieve();
    int q=1;
    // cin>>q;
    while(q--)Anon_mouS();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using ll = long long;
int main(){
    int n;
    cin >> n;
    //{6k}から任意個、{6k-2,6k-4},{12k-3,12k-9}から1つ以上とってできる集合は常に条件を満たす
    //最小で{2,4,3,9}の4個,最大で{1..30000}\cap {6k,6k+2,6k+3,6k+4}=20000個なのでこれを構築すれば十分
    if(n==3)cout << "2 3 25" << endl;
    else{
        cout << "4 2 9 3";
        n-=4;
        int k=2;
        while(n>=2&&k<=5000){
            cout << " " << 6*k-4 << " " << 6*k-2;
            ++k;
            n-=2;
        }
        k=2;
        while(n>=2&&k<=2500){
            cout << " " << 12*k-9 << " " << 12*k-3;
            ++k;
            n-=2;
        }
        k=1;
        while(n>=1){
            cout << " " << 6*k;
            ++k;
            --n;
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
FILE* in = stdin; FILE* out = stdout;

const int MAX = 100001;

int n, m;
int a[MAX][2];
vector < pair <int, int> > v[MAX];
string ans[MAX];

int main(void) {
	// in = fopen("C.in", "rt");
	
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
	    int p, y;
	    fscanf(in, "%d %d", &p, &y);
	    v[p].push_back(make_pair(y, i));
    }
    for (int i = 0; i < MAX; i++) {
        sort(v[i].begin(), v[i].end());
        for (int c = 0; c < (int)v[i].size(); c++) {
            int idx = v[i][c].second;
            char buff[32];
            sprintf(buff, "%06d%06d", i, c + 1);
            ans[idx] = buff;
        }
    }
    for (int i = 0; i < m; i++) {
        fprintf(out, "%s\n", ans[i].c_str());
    }
	
	return 0;
}

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

int main(void) {
	int n, a, b, c, d;
	string s;
	cin >> n >> a >> b >> c >> d >> s;

	for (int i = a; i < max(c, d); i++) {
		if (s[i] == '#' && s[i + 1] == '#') {
			cout << "No" << endl;
			return 0;
		}
	}

	if (c < d) {
		cout << "Yes" << endl;
		return 0;
	}

	else if (d < c) {
		for (int i = b - 2; i < d - 1; i++) {
			if (s[i] == '.'&&s[i + 1] == '.'&&s[i + 2] == '.') {
				cout << "Yes" << endl;
				return 0;
			}
		}
		cout << "No" << endl;
		return 0;
	}
}

Measured memory_bytes: 640
a, b = map(int, input().split())

def small(a,b):
    return a < b
    
def big(a,b):
    return a > b 
    
def equal(a,b):
    return a == b

if small(a,b):
    print ("a < b")
elif big(a , b):
    print ("a > b")
elif equal(a , b):
    print ("a == b")
    


Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }

typedef long long ll;

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

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

const int INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9+7;

const double PI = acos(-1.0);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int N,T;
    cin>>N>>T;
    vector<pair<int,int>> vp;
    rep(i,N){
        int a,b;
        cin>>a>>b;
        vp.push_back({a,b});
    }
    sort(all(vp));
    vector<int> A(N),B(N);
    rep(i,N){
        A[i] = vp[i].first;
        B[i] = vp[i].second;
    }
    vector<vector<ll>> dp(N+1,vector<ll>(T+1,0));
    dp[0][0] = 0;
    rep(i,N){
        rep(t,T){
            chmax(dp[i+1][t], dp[i][t]);
            chmax(dp[i + 1][T], dp[i][T]);
            chmax(dp[i+1][min(t + A[i],T)], dp[i][t] + B[i]);
        }
    }
    ll ans = 0;
    rep(t,T+1){
        chmax(ans, dp[N][t]);
    }
    cout<<ans<<endl;
    /*
    rep(i,N+1){
        rep(t,T+1){
            cerr<<dp[i][t]<<" ";
        }
        cerr<<endl;
    }
    */
}

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

typedef pair<int,int> P;
typedef long long ll;

const int INF = 100000000;
const double PI=3.14159265358979323846;

int main () {
    string N;
    cin >> N;
    if (N.back()=='3') {
        cout << "bon" << endl;
    }
    else if (N.back()=='0' || N.back()=='1' || N.back()=='6' || N.back()=='8' ) {
        cout << "pon" << endl;
    }
    else {
        cout << "hon" << endl;
    }
}

Measured memory_bytes: 3628
#include<stdio.h>
#include<algorithm>
using namespace std;
int c[1100];
int d[1100];
int e[1100];
int fin[1100];
int next[1100];
int a,b;
int can(int M){
	for(int i=0;i<M;i++)fin[i]=0;
	for(int i=0;i<a;i++)next[i]=0;
	int last=0;
	int rem=a;
	for(int i=0;i<b;i++){
		for(int j=0;j<M;j++){
			if(fin[j]<=i){
				for(int k=0;k<a;k++){
					if(~next[k]&&next[k]<=i){
						next[k]=-1;
						fin[j]=i+c[k];
						last=max(last,fin[j]);
						rem--;
						break;
					}
				}
			}
		}
		for(int j=0;j<a;j++){
			if(~next[j]&&i==next[j]+d[j]){
				next[j]=next[j]+d[j]+e[j];
			}
		}
		if(!rem)break;
	}
	for(int i=0;i<a;i++)if(~next[i])last=9999999;
	if(last<=b)return 1;
	return 0;
}
int main(){
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)scanf("%d%d%d",c+i,d+i,e+i);
		int left=0;
		int right=1001;
		while(left+1<right){
			int M=(left+right)/2;
			if(can(M)){
				right=M;
			}else left=M;
		}
		int tr=right;
		for(int i=1;i<=10&&tr-i>0;i++){
			if(can(tr-i))right=tr-i;
		}
		printf("%d\n",right);
	}
}

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF = 100000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	static int n,e,t;
	static int w[302];
	static int g[1002],c[1002];
	static int s[1002][12];
	scanf("%d%d%d",&n,&e,&t);
	rep1(i,n)scanf("%d",&w[i]);
	rep(i,e){
		scanf("%d%d",&g[i],&c[i]);
		rep(j,c[i]){
			scanf("%d",&s[i][j]);
		}
	}
	rep1(i,n){
		if(w[i] == 0)w[i] = INF;
	}
	
	bool updata = true;
	while(updata){
		updata = false;
		rep(i,e){
			vector<int> vec;
			rep(j,c[i])vec.pb(w[s[i][j]]);
			sor(vec); rev(vec);
			int ret = 0;
			rep(j,vec.size())ret = max ( ret , vec[j] + j );
			if(w[g[i]] > ret){
				w[g[i]] = ret;
				updata = true;
			}
		}
	}
	
	if(w[t] == INF)puts("-1");
	else printf("%d\n",w[t]);
}

Measured memory_bytes: 1256
#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N=50,M=(1<<17)+5,mod=1e9+7; 
int n,x,y,z,st,dp[N][M],sum=1,k,ans;
signed main(){
	scanf("%lld%lld%lld%lld",&n,&x,&y,&z); 
	st=((1<<(x+y+z-1)))|(1<<(y+z-1))|(1<<(z-1));
	dp[0][0]=1;
	for(int i=1;i<=n;i++){ 
		sum=sum*10%mod; 
		for(int S=0;S<(1<<(x+y+z));S++)
			if(dp[i-1][S]&&(S&st)!=st)
				for(int c=1;c<=10;c++){ 
					k=((S<<c)|(1<<(c-1)))&((1<<(x+y+z))-1);
					dp[i][k]=(dp[i][k]+dp[i-1][S])%mod;
				} 
	} 
	for(int S=0;S<(1<<(x+y+z));S++)
		if((S&st)!=st) ans=(ans+dp[n][S])%mod;
	printf("%lld\n",(sum-ans+mod)%mod);
	return 0;
}

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

using namespace std;

int N, M;

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

  string S;
  cin >> N >> M >> S;

  vector<int> idx;
  int cur = S.size() - 1;
  while (cur != 0) {
    int i = max(0, cur - M);
    for (; i < cur; ++i) {
      if (S[i] == '0') {
        break;
      }
    }
    if (i == cur) {
      cout << -1 << endl;
      return 0;
    }
    idx.push_back(cur - i);
    cur = i;
  }
  bool first = true;
  for (auto it = idx.rbegin(); it != idx.rend(); ++it) {
    if (first) first = false;
    else cout << " ";
    cout << *it;
  }
  cout << endl;
}


Measured memory_bytes: 1096
using System;
using System.Linq;
class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();
        string x = "", y = "";
        int ans = 0;
        for (int i = 1; i < n; i++)
        {
            x = s.Substring(0, i);
            y = s.Substring(i);
            ans = Math.Max(ans, Count(x, y));
        }
        Console.WriteLine(ans);
    }
    static int Count(string s1, string s2)
    {
        string alp = "abcdefghijklmnopqrstuvwxyz";
        int count = 0;
        foreach (var c in alp)
            if (s1.Contains(c) && s2.Contains(c))
                count++;
        return count;
    }
}

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

using namespace std;

const int N = 10000 + 4, mod = 1e9+7;

long long n  , a , b  ;

long long fpow(long long a , long long b )
{
    if(!b)
        return 1;
    long long ret = fpow(a , b/2);
    ret = (ret*ret)%mod;
    if(b%2)
        ret = (ret*a)%mod;
    return ret ;
}

long long binomialCoeff(int n, int k)
{
    long long res = 1;
    if ( k > n - k )
        k = n - k;
    for (int i = 0; i < k; ++i)
    {
        res = (res  * (n - i) )%mod;
        res = (res *  fpow(i + 1 , mod-2 ))%mod;
    }
    return res;
}

int main()
{
    cin>>n>>a>>b;
    long long sol = (fpow(2 , n) - binomialCoeff(n , a) - binomialCoeff(n ,  b) - 1);
    sol = (sol%mod + mod)%mod;
    cout<<sol;
    return 0;
}



Measured memory_bytes: 256
//bismillahir rahmanir rahim            //Author:Fayed Anik
 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
//#define         ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define         ll                          long  long
#define         lf                          double
#define         pb(x)                       push_back(x)
#define         ull                         unsigned long long
#define         sfl(a)                      scanf("%lld",&a)
#define         sf(a)                       scanf("%d",&a)
#define         pf(a)                       printf("%d\n",a)
#define         pfl(a)                      printf("%lld\n",a)
#define         FOR(x,n)                    for(ll x=1;x<=n;++x)
#define         pii                         pair< ll , ll >
#define         mp(a,b)                     make_pair(a,b)
#define         UNIQUE(v)                   v.resize(distance(v.begin(),unique(v.begin(),v.end())))
#define         mod                         1000000007
#define         INF                         2e18
#define         EPS                         1e-15
#define         f1                          first
#define         f2                          second
#define         all(v)                      v.begin(),v.end()
#define         PI                          acos(-1)
#define         printminusone               printf("-1\n")
#define         bug                         printf("bug")
#define         FILEIN                      freopen("in.txt","r",stdin)
#define         FILEOUT                     freopen("out.txt","w",stdout)
 
//ll SET(ll mask,ll pos){ return mask = (mask | (1ll<<pos)); }
//ll RESET(ll mask,ll pos){ return mask = mask & ~(1ll<<pos); }
//bool CHECK(ll mask,ll pos) { return (bool) (mask & (1ll<<pos)); }
//priority_queue <ll, vector<ll>, greater<ll> > pq;
//int dx[]={0,0,1,-1,1,1,-1,-1};
//int dy[]={1,-1,0,0,1,-1,1,-1};

#define lim 200005

ll par[lim],sz[lim];

ll find(ll u){
    if(par[u]==u) return u;
    else return par[u] = find(par[u]);
}
void UNION(ll u,ll v){
    u = find(u);
    v = find(v);
    if( u!=v ){
        if(sz[u]>=sz[v]){
            sz[u] += sz[v];
            par[v] = par[u];
            sz[v] = 0;
        }
        else{
            sz[v] += sz[u];
            par[u] = par[v];
            sz[u] = 0;
        }
        
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll n,m,u,v;
    sfl(n),sfl(m);
    FOR(i,n) par[i] = i,sz[i]=1;
    FOR(i,m){
        sfl(u),sfl(v);
        UNION(u,v);
    }
    ll ans = 0;
    FOR(i,n) ans = max(ans,sz[i]);
    pfl(ans);
    return 0;
}

Measured memory_bytes: 6924
import java.util.Scanner;

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

        int a = 0;
        for (int i = 0; i < s.length(); i++) {
            a += Integer.parseInt(s.substring(i, i+1));
        }

        if (n % a == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 23380
import math
a,b,x = map(int,input().split())

if x >= a*a*b/2:
    y = (-1)*b + 2*x/(a**2)
    if b != y:
        d = math.atan(a / (b-y))
    else:
        print(0)
        exit()
else:
    y = 2*x/(a*b)
    d = math.atan(y/b)
print(90 - math.degrees(d))

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

int main() {
  int n; cin>>n;
  vector<int> a(n);
  rep(i, n) cin>>a[i];
  
  ll res=0,sum=0;
  int r=0;
  rep(l, n) {
    while (r<n&&(sum^a[r])==(sum+a[r])) {
      sum+=a[r];
      ++r;
    }
    res+=r-l;
    sum-=a[l];
  }
  cout<<res<<endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

ll A[200005], B[200005], C[200005];
int main(int argc, char *argv[])
{
	ll N;

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		B[A[i]]++;
	}

	ll sum = 0;
	for (int i = 1; i <= N; i++) {
		if (B[i] != 0) {
			C[i] = B[i] * (B[i] - 1) / 2;
			sum += C[i];
		}
	}

	for (int i = 1; i <= N; i++) {
		printf("%lld\n", sum - (B[A[i]] - 1));
	}

	return 0;
}

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


int main() {
	
	long long rlnth,vlnth;
	cin>>vlnth>>rlnth;
  long long ans;
	if(vlnth==1||rlnth==1)cout<<1<<endl;
	else if(vlnth%2==1&&rlnth%2==1){
		ans=vlnth*rlnth/2+1;
		cout<<ans<<endl;
	}else {
		ans=rlnth*vlnth/2;
		//cout<<rlnth*vlnth<<endl;
		cout<<ans<<endl;
	}
	return 0;
}


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

using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
typedef long long ll;
typedef pair<int,int> P;

int main(void){
	          int i;

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

	      	  int N;
	      	  cin >> N;
	      	  vector<P> v;
	      	  for(i=0;i<N;i++){
	      		  int x;
	      		  cin >> x;
	      		  v.push_back(P(x,i));
	      	  }

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

	      	  vector<P> u;
	      	  for(i=0;i<=(N-1)/2;i++){
	      		  u.push_back(P(v[i].second,v[(N+1)/2].first));
	      	  }

	      	  for(i=(N+1)/2;i<N;i++){
	      		  u.push_back(P(v[i].second,v[(N-1)/2].first));
	      	  }

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

	      	  for(i=0;i<N;i++){
	      		  cout << u[i].second << endl;
	      	  }

	          return 0;
}


Measured memory_bytes: 5616
#include <stdio.h>

int main(void) {
  int N;
  int a[55556] = {};
  scanf("%d", &N);
  a[0] = a[1] = 1;
  for (int i = 2; i <= 235; i++) {
    for (int k = 2; i*k <= 55556; k++) {
      a[i*k] = 1;
    }
  }

  int cnt = 1;
  printf("7");
  for (int i = 2; i <= 11111 && cnt < N; i++) {
    if (a[5*i+2] == 0) {
      cnt++;
      printf(" %d", 5*i+2);
    }
  }
  puts("");

  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(int argc, char **argv)
{
	ll n,x,t;
  cin>>n>>x>>t;
  ll time=0;
  while(n>0){
    n=n-x;
    time+=t;
  }
  cout<<time<<"\n";
	return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int main() {
  int n;
  cin >> n;
  vector<ll> x(n + 1, 0);
  for (int i = 1; i <= n; i++) {
    ll a;
    cin >> a;
    x[i] = x[i - 1] + a;
  }
  ll ans = 1e18;
  for (int i = 0; i < n; i++) {
    ll l = x[i];
    ll r = x[n] - x[i];
    ans = min(ans, abs(l - r));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4840
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    a, b = input().split()

    if a == b:
        print("H")
    else:
        print("D")


main()


Measured memory_bytes: 5284
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int64_t INF = 1'000'000'000'000'000;
int64_t N, ans;

bool isVertex(int x, int y, vector<int> X, vector<int> Y, vector<int64_t> H){
    //int64_t height = H[0] + abs(x - X[0]) + abs(y - Y[0]);
    int i=0;
    int64_t height;
    do{
        height = H[i] + abs(x - X[i]) + abs(y - Y[i]);
        i++;
    }while ( H[i-1] == 0 );

    for(int i=0;i<N;i++){
        /***
        if( height != H[i] + abs(x - X[i]) + abs(y - Y[i]) && H[i] != 0 ) return false;
        else if( H[i] == 0 && abs(x - X[i]) + abs(y - Y[i]) < height ) return false;
        ***/
        if( H[i] == 0 ){
            if( abs(x - X[i]) + abs(y - Y[i]) < height ) return false;
        } else{
            if( height != H[i] + abs(x - X[i]) + abs(y - Y[i]) ) return false;
        }
    }

    cout << x << " " << y << " " << height << endl;
    return true;
}

int main() {
    cin >> N;

    vector<int> X(N), Y(N);
    vector<int64_t> H(N);
    for(int i=0;i<N;i++)    cin >> X[i] >> Y[i] >> H[i];

    for(int i=0;i<101;i++){
        for(int j=0;j<101;j++){
            if( isVertex(j, i, X, Y, H) ) return 0;
        }
    }

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
map<__uint128_t,int>memo;

int M,N;
vector<string>v;
int dfs(__uint128_t t){
	int c=0;
	for(int i=0;i<N;i++){
		if(t&(__uint128_t)(1)<<i)c++;
	}
	if(c==1)return 0;
	if(memo.find(t)!=memo.end())return memo[t];
	int r=1<<30;
	for(int j=0;j<M;j++){
		__uint128_t a=0,b=0;
		for(int i=0;i<N;i++){
			__uint128_t e=(__uint128_t)(1)<<i;
			if(t&e)(v[i][j]=='0'?a:b)|=e;
		}
		if(a&&b)r=min(r,max(dfs(a),dfs(b))+1);
	}
	return memo[t]=r;
}

int main(){
	for(;cin>>M>>N,M;){
		v.resize(N);
		for(int i=0;i<N;i++)cin>>v[i];
		__uint128_t t=0;
		for(int i=0;i<N;i++)t|=(__uint128_t)(1)<<i;
		memo.clear();
		printf("%d\n",dfs(t));
	}
}

Measured memory_bytes: 2696
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define set0(a) memset ((a), 0 , sizeof(a))
#define set1(a) memset((a),-1,sizeof (a))
#define pi pair<int, int>
#define ps pair<string, string>
#define pl pair<long, long>
#define pll pair<long long, long long>
#define vll vector<long long>
#define vl vector<long>
#define vi vector<int>
#define vs vector<string>
#define vps vector< ps >
#define vpi vector< pi >
#define vpl vector< pl >
#define vpll vector< pll >
#define flash  ios_base::sync_with_stdio(false); cin.tie(NULL);
#define tc(t,T) for(long long t=0;t<T;t++)
#define rep(i,s,n,d) for(long long i=s;i<n;i=i+d)

bool sortbysec(const pll &a,
              const pll &b)
{
    return (a.second < b.second);
}
/*bool cxp pair<ll, pll> &a,
              const pair<ll, pll> &b)
{
    return (a.ff < b.ff);
}*/

void func(void)
{
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
}
ll gcd(ll a,ll b){
    if(b==0)return a;
    else gcd(b,a%b);
}
void printStack(stack<string> s){
    if(s.empty())return;

    string x=s.top();
    s.pop();
    printStack(s);
    cout<<x;
    s.push(x);

}



int main(){
      ll n,a,b,c;
    cin>>a>>b>>n;

        ll x=0;
    if(n>=b)
    x=b-1;
    else x=n;

    ll max1=(a*x)/b-a*(x/b);

    cout<<max1<<endl;


}


// 1 2 3 1 5 3 1 0 1 0 2
// 1 2 3 4 5 6 7 8 9 10 11






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

int main() {
  int N;
  cin >> N;
  vector<int> B(N - 1);
  for (int i = 0; i < N - 1; i++) cin >> B.at(i);

  int ans = B.at(0) + B.at(N - 2);
  for (int i = 0; i + 1 < N - 1; i++) ans += min(B.at(i), B.at(i + 1));

  cout << ans << "\n";
}

Measured memory_bytes: 256
SX,SY,TX,TY=map(int,input().split())
x=TX-SX
y=TY-SY
print(''.join(['U'*y,'R'*x,'D'*y,'L'*x,'L','U'*(y+1),'R'*(x+1),'D','R','D'*(y+1),'L'*(x+1),'U']))

Measured memory_bytes: 9064
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
/* テンプレートここまで */
ll gcd (ll a, ll b){
  if(b == 0) return a;
  return gcd(b, a%b);
}

int main() {
  ll N, K; cin >> N >> K;
  ll maxi = 0;
  vector<ll> a(N); 
  REP(i, N){
    cin >> a[i];
    maxi = max(maxi,a[i]);
    if(a[i] == K){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }

  if(maxi < K){
    cout << "IMPOSSIBLE" << endl;
    return 0;
  }

  ll g = a[0];
  REP(i, N-1){
    g = gcd(g, a[i+1]);
  }

  if(K%g == 0){
    cout << "POSSIBLE" << endl;
  }else{
    cout << "IMPOSSIBLE" << endl;
  }
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<iomanip>
#include<numeric>

using namespace std;
using ll = long long;
using ull = unsigned long long;
constexpr int mo = 1e9+7;
constexpr int  mod = mo;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<62;
template<int N>
class UF{
    vector<int> par;
    public:
    UF():par(N,-1){}
    int operator[](int x){return (par[x] == -1)?x:par[x] = operator[](par[x]);}
    void operator()(int x,int y){
        x = operator[](x);y = operator[](y);
        if(x > y)swap(x,y);
        par[y] = x;
    }
};
UF<200050> uf;
int main(){
    int n,h,w;
    cin>>n>>h>>w;
    vector<tuple<int,int,int>> vec;
    for(int i=0;i<n;++i){
        int r,c,a;
        cin>>r>>c>>a;
        r--;c--;
        vec.emplace_back(a,r,c);
    }
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    vector<bool> used(200050);
    ll ret = 0ll;
    for(int i=0;i<n;++i){
        int a,r,c;
        tie(a,r,c) = vec[i];
        if(!used[uf[r]] and !used[uf[c+h]]){
            if(uf[r] == uf[c+h]){
                used[uf[r]] = true;
            }else uf(r,c+h);
            ret += a;
        } else if(!used[uf[r]]){
            used[uf[r]] = true;
            ret += a;
        } else if(!used[uf[c+h]]){
            used[uf[c+h]] = true;
            ret += a;
        }
    }
    cout << ret << endl;
    return 0;
}



Measured memory_bytes: 2680
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <complex>
#include <numeric>
#include <string.h>
#include <random>
#include <cmath>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
double PI = 3.141592653589793238462643383279;
const double EPS = 1e-9;
const ll MOD = 1000000007;
//const ll MOD = 998244353
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++) {
        int x = i*108/100;
        if (x == n) {
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
}

Measured memory_bytes: 256
#include<algorithm> 
#include<iostream> 
#include<cstring> 
#include<climits> 
#include<cstdio> 
#include<queue> 
using namespace std;
#define MAXN 100
int n,k,m;
int G[MAXN+5][MAXN+5];
int main()
{
	scanf("%d%d",&n,&k);
	m=k;
	for(int i=3;i<=n;i++)
	{
		for(int j=i-1;j>=2;j--)
		{if(k==0)break;G[j][i]=1;k--;}
		if(k==0)break;
	}
	if(k){printf("-1");return 0;}
	printf("%d\n",n*(n-1)/2-m);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
		if(!G[i][j])printf("%d %d\n",i,j);
}

Measured memory_bytes: 256