akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;

ll dp[1003][(1 << 12) + 3];

int main() {
	int n, m; cin >> n >> m;
	vector<int> a(m), b(m), c(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i];
		for (int j = 0; j < b[i]; j++) {
			int k; cin >> k;
			k--;
			c[i] |= 1 << k;
		}
	}
	vector<ll> dp((1 << 12) + 3, 1e18);
	dp[0] = 0;

	for (int i = 0; i < m; i++) {
		for (int j = (1 << n) - 1; j >= 0; j--) {
			dp[j | c[i]] = min(dp[j | c[i]], dp[j] + a[i]);
		}
	}
	if (dp[(1 << n) - 1] != 1e18) cout << dp[(1 << n) - 1] << endl;
	else cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>    
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll n, cc;

int main() {
	cin >> n >> cc;
	ll s[100000], t[100000], c[100000];
	ll tt[200002] = {};
	ll sm[200002] = {};
	for(ll i = 0; i < n; i++){
		cin >> s[i] >> t[i] >> c[i];
	}
	
	for(ll i = 1; i <= cc; i++){
		for(ll j = 0; j <= 200002; j++){tt[j] = 0;}
		for(ll j = 0; j < n; j++){if(c[j] == i){tt[2*s[j]-1]++, tt[2*t[j]]--;}}
		for(ll j = 1; j < 200002; j++){tt[j] += tt[j-1];}
		for(ll j = 0; j < 200002; j++){if(tt[j]>0){sm[j]++;}}
	}
	ll max = 0;
	for(ll j = 0; j < 200002; j++){if(sm[j]>max){max = sm[j];}}
	cout << max;
	return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
 
using namespace std;
 
void fail() {
  cout << -1 << endl;
  exit(0);
}
 
int main() {
  int N;
  cin >> N;
  string A[500], C[500];
  uint64_t B[500], D[500];
  int H = N, W = N;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if(x == 0) A[i] = "and";
    else A[i] = "or";
  }
 
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if(x == 0) C[i] = "and";
    else C[i] = "or";
  }
  for(int i = 0; i < N; i++) {
    cin >> B[i];
  }
  for(int i = 0; i < N; i++) {
    cin >> D[i];
  }
 
  uint64_t ans[500][500] = {{}};
  for(int i = 0; i < 64; i++) {
    vector< vector< int > > decide(H, vector< int >(W, -1));
    vector< pair< int, int > > latte, malta;
 
    for(int j = 0; j < H; j++) {
      if(A[j] == "and") {
        if((B[j] >> i) & 1) for(int k = 0; k < W; k++) decide[j][k] = 1;
        else latte.emplace_back(j, 0);
      } else {
        if((~B[j] >> i) & 1) for(int k = 0; k < W; k++) decide[j][k] = 0;
        else latte.emplace_back(j, 1);
      }
    }
    for(int j = 0; j < W; j++) {
      if(C[j] == "and") {
        if((D[j] >> i) & 1) {
          for(int k = 0; k < H; k++) if(decide[k][j] == 0) fail();
          for(int k = 0; k < H; k++) decide[k][j] = 1;
        } else malta.emplace_back(j, 0);
      } else {
        if((~D[j] >> i) & 1) {
          for(int k = 0; k < H; k++) if(decide[k][j] == 1) fail();
          for(int k = 0; k < H; k++) decide[k][j] = 0;
        } else malta.emplace_back(j, 1);
      }
    }
 
    if(min(latte.size(), malta.size()) >= 2) {
      for(int j = 0; j < latte.size(); j++) {
        for(int k = 0; k < malta.size(); k++) {
          decide[latte[j].first][malta[k].first] = (j + k) & 1;
        }
      }
    } else if(latte.size() == 1) {
      for(auto &p : malta) {
        bool ex = false;
        for(int j = 0; j < H; j++) ex |= decide[j][p.first] == p.second;
        decide[latte[0].first][p.first] = ex ? latte[0].second : p.second;
      }
      bool f = false;
      for(int k = 0; k < W; k++) f |= decide[latte[0].first][k] == latte[0].second;
      if(!f) fail();
    } else if(malta.size() == 1) {
      for(auto &p : latte) {
        bool ex = false;
        for(int k = 0; k < W; k++) ex |= decide[p.first][k] == p.second;
        decide[p.first][malta[0].first] = ex ? malta[0].second : p.second;
      }
      bool f = false;
      for(int j = 0; j < H; j++) f |= decide[j][malta[0].first] == malta[0].second;
      if(!f) fail();
    } else {
      for(auto &p : latte) {
        bool f = false;
        for(int k = 0; k < W; k++) f |= decide[p.first][k] == p.second;
        if(!f) fail();
      }
      for(auto &p : malta) {
        bool f = false;
        for(int j = 0; j < H; j++) f |= decide[j][p.first] == p.second;
        if(!f) fail();
      }
    }
    for(int j = 0; j < H; j++) {
      for(int k = 0; k < W; k++) {
        ans[j][k] |= ((uint64_t) (decide[j][k] & 1)) << i;
      }
    }
  }
 
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) cout << ans[i][j] << " ";
    cout << endl;
  }
}

Measured memory_bytes: 8468
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
int main()
{
  int a,b; cin >> a >> b;

  vector<vector<char>> res(99, vector<char>(99, '.'));
  rep(i,99) {
    rep(j,99) {
      if(i % 4 != 3) {
	if(j % 4 != 3) res[i][j] = '#';
      }
      // else if(i % 4 == 1) {
      // 	if(j % 2 == 0) res[i][j] = '#';
      // }
    }
  }
  
  rep(i,99) {
    res[0][i] = '#';
    res[98][i] = '#';
    res[i][0] = '#';
    res[i][98] = '#';
  }
  
  rep(i,99) {
    rep(j,93) {
      if(i > 3 && i % 4 == 2) res[i][j] = '#';
    }
  }

  
  int x = 1, y = 1;
  while(--a > 0) {
    res[x][y] = '.';
    y += 4;
    if(y >= 99) {
      y = 1;
      x += 4;
    }
  }

  x = 6; y = 91;
  while(--b) {
    res[x][y] = '.';
    y -= 4;
    if(y < 0) {
      y = 91;
      x += 4;
    }    
  }
  
  cout << 99 << " " << 99 << "\n";
  rep(i,99) {
    rep(j,99) {
      cout << res[i][j];
    }
    cout << "\n";
  }
  
  return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations
    #from itertools import accumulate, product, permutations
    from math import floor, ceil

    #mod = 1000000007

    x,y = input().split()
    if x<y:
        print('<')
    elif x>y:
        print('>')
    else:
        print('=')
        

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <string>
#include<algorithm>
#include<map>
#include <vector>
#include <cassert>
#include<cmath>
using namespace std;

int main() {
	int i, j,k;
	int N,K;
	int maxj = -1;
	int sum = 0;
	int l[100];
	cin >> N >> K;
	for (i = 0; i < N; ++i) {
		cin >> l[i];
	}
	sort(l, l+N, greater <int>());


	for (i = 0; i < K; ++i) {
		sum += l[i];
	}
	cout << sum;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int h,w;
  cin >> h >> w;
  while(h!=0){
    int i,j;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
 cout << "#";
      }
      cout << endl;
    }
    cout << endl;
    cin >> h >> w;
  }
  return 0;
}


Measured memory_bytes: 3080
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

fn main() {
  let s = read::<String>();
  let front: &str = &s[0..2];
  let back: &str = &s[2..];

  let f_num: i32 = front.parse().unwrap();
  let b_num: i32 = back.parse().unwrap();

  if within_month(f_num) && within_month(b_num) {
    println!("AMBIGUOUS");
  } else if within_month(f_num) {
    println!("MMYY");
  } else if within_month(b_num) {
    println!("YYMM");
  } else {
    println!("NA");
  }

}

fn within_month(num: i32) -> bool {
  return num <= 12 && num >= 1;
}


Measured memory_bytes: 4352
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
int main(void){
    list <int> L;
    string command;
    int n,t;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> command;
        if(command[0]== 'i'){
            cin >> t;
            L.push_front(t);
        }else if(command[6]== 'L'){
            L.pop_back();
        }else if(command[6]== 'F'){
            L.pop_front();
        }else{
            cin >> t;
            for(list<int>::iterator j = L.begin();j!=L.end();j++){
                if(*j==t){
                    L.erase(j);
                    break;
                }
            }
        }
    }
    int i = 0;
    for(list<int>::iterator j = L.begin();j!=L.end();j++){
        if(i++)cout << ' ';
        cout << *j;
    }
    cout << '\n';
    return 0;
}


Measured memory_bytes: 34404
#include <iostream>
using namespace std;
int n, a, b, x, ca, cb, cc;
int main() {
	cin>>n>>a>>b;
	for(int i=0; i<n; i++) {
		cin>>x;
		if(x<=a) ca++;
		else if(x<=b) cb++;
		else cc++;
	}
	cout<<min(ca, min(cb, cc));
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
using namespace std;
int main() {
	string S;
	
	int y, m, d;
	for (int i = 0; i < 10000; i++) {
		cin >>S>> y >> m >> d;
		if (S == "#") {
			return 0;
		}
		if (y > 31) {
			cout<< "?"<< " " << y - 30 << " " << m << " " << d << endl;
		}
	 else if (y<31) {
			cout <<S<<" "<<y<<" "<<m<<" "<<d<< endl;
			
		}
		else if (y == 31 && m >=5) {

			
			cout << "?"<<" "<<y-30<<" "<<m<<" "<< d <<endl;
			
		}
		else if (y == 31 && m <= 4) {
			cout << S<<" "<<y<<" "<<m<<" "<<d << endl;
			
		}
		
		
	}
	
		return 0;
	}


Measured memory_bytes: 3228
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e15;

vector<int> divisor(int n){
    vector<int> res;
    for(int i=1;i*i<=n;i++){
    if(n%i==0){
            res.push_back(i);
            if(i!=n/i) res.push_back(n/i);
        }
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int ans = 0;
    rep(i, 1, n + 1){
        if(i % 2){
            vector<int> d = divisor(i);
            if(d.size() == 8) ans++;
        }
    }
    cout << ans << endl;
}

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

using namespace std;
typedef long long ll;
int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll > v;
    for (ll i = 0; i< n ;i++) {
        ll x;
        cin >> x;
        v.push_back(x);
    }
    if(k>=n) {
        cout << 0 << endl;
        return 0;
    }
    sort(v.begin(),v.end(),greater<ll>());
    ll sum = 0;
    for (auto i = v.begin()+k ; i != v.end(); i++) {
        sum += *i;
    }
    cout << sum << endl;
    return 0;

}


Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define fi first
#define se second
#define co(a) cout<<a<<endl
#define sz size
#define bgn begin()
#define en end()
#define pb(a) push_back(a)
#define pop pop_back
template<class T>
 void cou(vector<vector<T>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
//template<>
 void cou(vector<vector<char>> a){
  int b=a.size();
  int c=a[0].size();
  fo(i,b){
    fo(j,c){
      cout<<a[i][j];
      if(j==c-1)
        cout<<endl;
      else
        cout<<' ';
    }
  }
}
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
 bool prime(int a){
   if(a<2)
     return false;
   else if(a==2)
     return true;
   else if(a%2==0)
     return false;
   double b=sqrt(a);
    for(int i=3;i<=b;i+=2){
      if(a%i==0){
        return false;
      }
    }
   return true;
 }
signed main(){
  int a;
  cin>>a;
  cout<<a*a*a<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
typedef pair<int,int> pii;
#define mp make_pair
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=200010,Mod=1e9+7;
int n,a[N],b[N],f[5010][5010],fac[N],fai[N],inv[N];
int C(int n,int m){return 1ll*fac[n]*fai[m]%Mod*fai[n-m]%Mod;}
int main()
{
	n=gi();
	for(int i=1;i<=n;i++)a[i]=gi(),b[i]=gi();
	fac[0]=fai[0]=inv[0]=inv[1]=1;
	for(int i=1;i<=8000;i++)fac[i]=1ll*fac[i-1]*i%Mod;
	for(int i=2;i<=8000;i++)inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
	for(int i=1;i<=8000;i++)fai[i]=1ll*fai[i-1]*inv[i]%Mod;
	for(int i=1;i<=n;i++)f[-a[i]+2001][-b[i]+2001]++;
	for(int i=1;i<=4001;i++)
		for(int j=1;j<=4001;j++)
			f[i][j]=(1ll*f[i][j-1]+f[i-1][j]+f[i][j])%Mod;
	int ans=0;
	for(int i=1;i<=n;i++)ans=(ans+f[a[i]+2001][b[i]+2001])%Mod;
	for(int i=1;i<=n;i++)ans=(ans-C(a[i]+b[i]+a[i]+b[i],a[i]+a[i])+Mod)%Mod;
	printf("%d\n",1ll*ans*inv[2]%Mod);
	return 0;
}


Measured memory_bytes: 81792
#include<iostream>

using namespace std;
int main(){
  int N;
  int H[20]={};
  int count=0;
  int i,j;
  int flag;
  
  cin >> N;
  
  for(i=0;i<N;i++){
    cin >> H[i];
  }
  
  for(i=0;i<N;i++){
    flag=0;
    for(j=0;j<i;j++){
      if(H[i]<H[j]){
      	flag=1;
        break;
      }
    }
    if(flag==0){
      count++;
    }
  }
  cout << count;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18
#define mod 1000000007

int main () {
    ll r, l ;
    cin >> l >> r ;
    if(r - l > 3000){
        cout << 0 << endl ;
        return 0 ;
    }        
    ll ans = INF ;
    for(ll i = l; i <= r; i++){
        for(ll j = l; j <= r; j++){
            if(i >= j) continue ;
            ll t = (i%2019 * j%2019) % 2019 ;
            ans = min(ans, t) ;
        }
    }
    cout << ans << endl ;
}

Measured memory_bytes: 3608
#include <stdio.h>

#define WHITE 1
#define GRAY 0
#define BLACK -1
#define INF 100000000
#define N 100

void bfs(int);
void enqueue(int);
int dequeue(void);

int Q[N+1],d[N+1],c[N+1],ts,n,S[N+1][N+1],k[N+1];
int head, tail;

int main()
{
  int i,j,u,min;

  scanf("%d",&n);

  head = 0;
  tail = 1;

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

    for(j=0;j<k[u];j++){
      scanf("%d",&S[u][j]);
    }
  }

  bfs(1);
  for(i=1;i<=n;i++)  {
    if(d[i]==INF) d[i]=-1;
    printf("%d %d\n",i,d[i]);
  }

  return 0;
}

void bfs(int s){
  int i,u,v;
  for (u=1;u<=n;u++){
    c[u] = WHITE;
    d[u] = INF;
  }
  c[s] = GRAY;
  d[s] = 0;

  enqueue(s);

  while(head!=tail){
    u = dequeue();
    for(i=0;i<k[u];i++){
      v=S[u][i];
      if (c[v] == WHITE){
    c[v] = GRAY;
    d[v] = d[u] + 1;
    enqueue(v);
      }
      c[u] = BLACK;
    }
  }
}

void enqueue(int x){
  Q[tail] = x;
  if (tail + 1 == n) tail = 0;
  else tail++;
}

int dequeue(void){ 
  int x;
  x = Q[head];
  if (head + 1 == n) head = 0;
  else head++;
  return x;
}

Measured memory_bytes: 636
N,K=map(int, input().split())
P=list(map(int, input().split()))
saikoro=[1+0.5*sai for sai in range(1000)]

ruiseki=0
for i in range(K):
	ruiseki+=saikoro[P[i]-1]

ans=ruiseki
for k in range(N-K):
	ruiseki=ruiseki-saikoro[P[k]-1]+saikoro[P[K+k]-1]
	ans=max(ans,ruiseki)
	
print(ans)

Measured memory_bytes: 98936
#include <stdio.h>

#define N 3

int main(void) {
	int asumi_kana[N];
	int i, j;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &asumi_kana[i]) != 1) return 1;
	}
	for (i = N - 1; i > 0; i--) {
		for (j = 0; j < i; j++) {
			if (asumi_kana[j] > asumi_kana[j + 1]) {
				int kitamura_eri = asumi_kana[j];
				asumi_kana[j] = asumi_kana[j + 1];
				asumi_kana[j + 1] = kitamura_eri;
			}
		}
	}
	printf("%d", asumi_kana[0]);
	for (i = 1; i < N; i++) printf(" %d", asumi_kana[i]);
	putchar('\n');
	return 0;
}



Measured memory_bytes: 2140
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn main() {
    let input = read_stdin();
    let mut a = 0;
    let mut b = 1;
    for d in input.trim().bytes().map(|b| (b - b'0') as isize) {
        let tmp_a = std::cmp::min(a + d, b + 10 - d);
        let tmp_b = std::cmp::min(a + d + 1, b + 9 - d);
        a = tmp_a;
        b = tmp_b;
    }
    println!("{}", a);
}


Measured memory_bytes: 4352
#include<iostream>
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
using namespace std;
int main()
{
    fastio;
    long long n,a,b,i;
    cin>>n>>a>>b;
    if(a>b)
    {
        cout<<0;
    }
    else if(n==1 && a!=b)
    {
        cout<<0;
    }
    else
    {
        n--;
        cout<<(a+(n*b))-(b+(n*a))+1;
    }
    return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#include <unistd.h>
#define inf 1000000007LL
#define INF 1000000000000000007LL
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
#define ll long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vll vector<long long>
#define vpii vector< pair<int,int> >
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define bit(i) (1LL<<(i))
#define log(x) (63-__builtin_clzll(x))
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i, n) for(int i=1; i<=(n); ++i)
#define pv(...) cerr<<'\n',dbg(#__VA_ARGS__, __VA_ARGS__)
#define ps(x) {cerr<<#x<<":\n:";for(auto q:(x)){cerr<<q<<" ";}cerr<<'\n';}
#define pa(x, xs) {cerr<<#x<<":\n:";for(int q=0; q<=(xs); ++q){cerr<<x[q]<<" ";}cerr<<'\n';}
#define pal(x, xs) {cerr<<'\n'<<#x<<":\n";for(int q=0; q<=(xs); ++q){cerr<<q<<": "<<setw(q? 3-(int32_t)log10(q):3)<<x[q]<<'\n';}cerr<<'\n';}
#define ppii(x, xs) {cerr<<'\n'<<#x<<":\n";for(int q=0; q<=(xs); ++q){cerr<<q<<": "<<setw(q? 6-(int32_t)log10(q):6)<<x[q].first<<" "<<setw(5)<<x[q].second<<'\n';}cerr<<'\n';}
#define pm(x, xn, xm) {cerr<<'\n'<<#x<<":\n";for(int qa=0; qa<=(xn); ++qa){for(int qb=0; qb<=(xm); ++qb){cerr<<setw(6)<<x[qa][qb]<<" ";}cerr<<'\n';}cerr<<'\n';}
#define endr cerr<<'\n'
#define endl '\n'
#ifndef DEBUG
#define cerr if(0)cout
#define pv(...) if(0)endr
#define ps(x) if(0)endr
#define pa(x, xs) if(0)endr
#define pal(x, xs) if(0)endr
#define ppii(x, xs) if(0)endr
#define pm(x, xn, xm) if(0)endr
#endif
using namespace std;
template<class T> void dbg(const char* xn, T x){cerr<<xn<<": "<<x<<"\n";} template<class T, class... TA> void dbg(const char* xn, T x, TA... t){while(*xn!=',')cerr<<*xn++;cerr<<": "<<x<<",";dbg(xn+1, t...);}
template<class T> inline bool upd_max(T &x, T y){return y>x?x=y,true:false;} template<class T> inline bool upd_min(T &x, T y){return y<x?x=y,true:false;}
const int N = 1000007;
#define int long long

int n, a[N], odd = 0, evenNot4 = 0, div4 = 0, groupsEven = 0;


bool check()
{
  if (evenNot4 == 0) return odd <= div4 + 1;
  return odd <= div4;
}

void solve()
{
  cin>>n;
  rep1(i, n) cin>>a[i];

  for (int i=1; i<=n; ++i)
  {
    if (a[i]&1) ++odd;
    else if (a[i]%4 == 0) ++div4;
    else ++evenNot4;
  }

  cout<<(check()? "Yes\n" : "No\n");
}

int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(NULL);
cout<<fixed<<setprecision(10);

  solve();

return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <map>

using namespace std;
 
int main(void) {
	long long N;
	cin >> N;
	long long res = 0;
	vector<long long> input;
	input.reserve(N);
	for (long long i = 0; i < N; i++) {
		long long tmp;
		cin >> tmp;
		res ^= tmp;
		input.emplace_back(tmp);
	}
	for (long long i = 0; i < N; i++) {
		cout << (res ^ input[i]);
		if (i == N - 1) {
			cout << endl;
		} else {
			cout << ' ';
		}
	}
	return 0;
}


Measured memory_bytes: 4800
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [10 ** 18] * (2 * 10 ** 4 + 1)
dp[0] = 0
for a, b in AB:
    for i in range(H):
        dp[i + a] = min(dp[i + a], dp[i] + b)

ans = min(dp[H:])
print(ans)


Measured memory_bytes: 42220
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin >> n;
    vector< int > v(n);
    for(int i=0;i<n;i++) cin >> v[i];
    sort(v.begin(),v.end(),greater< int >());
    int comfort = n-1;
    int i=0;
    long long int result = 0;
    while(comfort)
    {
        result+=v[i];
        comfort-=1;
        if(comfort==0) break;

        if(i==0)
        {
            i++;
            continue;
        }
        result+=v[i];
        comfort-=1;
        i++;
    }

    cout << result << endl;
    return 0;
}



Measured memory_bytes: 4040
A, B, C, D = map(int, input())

result = None

for i in [0,1]:
    tmp = A + B if i == 0 else A - B
    for j in [0,1]:
        tmp2 = tmp + C if j == 0 else tmp - C
        for k in [0,1]:
            tmp3 = tmp2 + D if k == 0 else tmp2 - D
            if tmp3 == 7:
                result = [i, j, k]



def f(i):
    if i == 0:
        return '+'
    else:
        return '-'


result = [f(x) for x in result]

print(str(A) + result[0] + str(B) + result[1] + str(C) + result[2] + str(D) + '=7')


Measured memory_bytes: 3064
// https://atcoder.jp/contests/abc175/tasks/abc175_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 CEIL(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int X, K, D;
    cin >> X >> K >> D;
    // if (abs(X) >= K * D) {
    if (K <= abs(X) / D) {
        cout << abs(X) - K * D << endl;
    } else {
        // 正の絶対値が最小
        int b = abs(X) - abs(X) / D * D;
        // 負の絶対値が最小
        // int c = abs(abs(X) - ((1 + a / D) * D));
        int c = abs(abs(X) - (abs(X) / D) * D - D);
        // 移動回数の偶奇によって分岐
        int bMove = abs(X) / D;
        if ((K - bMove) % 2 == 0) {
            cout << b << endl;
        } else {
            cout << c << endl;
        }
        // if ((K - abs(X) / D) % 2 == 0)
        //     cout << abs(X) - (abs(X) / D) * D;
        // else
        //     cout << abs(abs(X) - (abs(X) / D) * D - D);
    }

    return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,j;
    cin>>n>>m>>j;
    if(n==m && m==j)
    {
        cout<<"No";
    }
    else if((n==m) || m==j || n==j)
    {
       cout<<"Yes";
    }
        else
        {
            cout<<"No";
        }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string st;
    cin>>st;
    if (st=="SUN") cout<<7;
    if (st=="TUE") cout<<5;
    if (st=="MON") cout<<6;
    if (st=="WED") cout<<4;
    if (st=="THU") cout<<3;
    if (st=="FRI") cout<<2;
    if (st=="SAT") cout<<1;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<P>> Graph;


int main(){
  
  int n;
  cin >> n;
  ll a[n];  
  REP(i,n){
    cin >> a[i];
  }
  
  REP(i,n-1){
    a[i+1] += a[i];
  }
  
  ll ans = 2000000000;
  
  REP(i,n-1){
    ans = min(ans,abs(a[i] - (a[n-1] - a[i])));
  }
  
  cout << ans << endl;
  
 
 return 0;
}

Measured memory_bytes: 1792
//c++
#include<iostream>
#include<string>
using namespace std;

int main()
{
  int a;
  int b;
  
  cin >> a;
  cin >> b;
  
  if(a >= 13){
    cout<<b<<endl;
  }else if(a >= 6 && a <= 12){
    cout<<b / 2<<endl;
  }else{
    cout<<"0"<<endl;
  }
}
    


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

using namespace std;
using ll = long long;

const int N = 3e5 + 5;

mt19937 rnd(51515);

int a[N];

main() {
#ifdef ONPC
  freopen("a.in", "r", stdin);
#endif
  ios :: sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; ++i)
  {
    cin >> a[i];
  }
  sort(a + 1, a + 1 + n);
  ll ans = 0;
  for (int i = 1; i <= n - k; ++i)
  {
    ans += a[i];
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)n;i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
#define REP(i,b,e) for(int i=b;i<(int)e;i++)
typedef long long ll;
typedef map<ll,ll> mll;
typedef vector<ll> vll;
ll INF=1e18;
int inf=1e9+1000;

string alpha="abcdefghijklmnopqrstuwvxyz";

ll mod=998244353;

ll N,A,B,K;
ll frac[300002];


ll mul(ll a,ll b){
    return (a%mod)*(b%mod)%mod;
}

ll power(ll a,ll b){
    if(b==0) return 1;
    else if(b==1) return a%mod;
    else if(b%2==0) return ((power(a,b/2)%mod)*(power(a,b/2)%mod)%mod);
    else return ((((power(a,b/2)%mod)*((power(a,b/2)%mod))%mod)*(a%mod))%mod);

}

ll dive(ll a,ll b){
    return  mul(a, power(b,mod-2));
}

int main(){
    cin>>N>>A>>B>>K;
    frac[0]=1;
    rep(i,N){
        frac[i]=mul(i,frac[i-1]);
    }
    ll ans=0;
    ll j=0;
    Rep(i,N+1){
        if((K-A*i)%B==0&&(K-A*i)/B>=0&&(K-A*i)/B<=N){
            j=(K-A*i)/B;
            ans+=mul(dive(frac[N],mul(frac[i],frac[N-i])),dive(frac[N],mul(frac[j],frac[N-j])));
        }
    }
    cout<<ans%mod<<endl;

    return 0;
}




Measured memory_bytes: 2560
#include <iostream>
#include <math.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
#include <map>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (b>0&&b - a > b) {
		cout << "Zero";
		return 0;
	}
	if (a > 0) {
		cout << "Positive";
		return 0;
	}
	if ((b - a) % 2 == 0)cout << "Negative";
	else cout << "Positive";
}


Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
N = I()
sl = [S() for _ in range(N)]
#AC = WA = TLE = RE = 0
print('AC x '+ str(sl.count('AC')))
print('WA x '+ str(sl.count('WA')))
print('TLE x '+ str(sl.count('TLE')))
print('RE x '+ str(sl.count('RE')))

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

int main(){
	int N, i, R = 0, B = 0;
	scanf("%d", &N);
	char *S = (char *)malloc(sizeof(char) * (N + 1));
	scanf("%s", S);
	for(i = 0; i < N; i++){
		if(S[i] == 'R'){
			R++;
		}
		else{
			B++;
		}
	}
	if(R > B){
		printf("Yes\n");
	}
	else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>

int main(){
	int n;
	unsigned long long int sum = 0;
	int in;
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &in);
		sum += in;
	}
	
	printf("%d\n", sum / n);
	
	return 0;
}

Measured memory_bytes: 1020
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cmath>

using namespace std;

int cnt = 1; // time stamp
vector<int> seen, visited;

void dfs(vector<vector<int> > graph, int v) {
    if (seen[v] != 0) return;
    seen[v] = cnt;
    cnt++;
    for (int i = 0; i < graph[v].size(); i++) {
        dfs(graph, graph[v][i]);
    }
    visited[v] = cnt;
    cnt++;
}

int main() {
    int n;
    cin >> n;
    vector<vector<int> > graph(n+1);
    for (int i = 1; i <= n; i++) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; j++) {
            int v;
            cin >> v;
            graph[u].push_back(v);
        }
    }
    seen.assign(n+1, 0);
    visited.assign(n+1, 0);
    for (int i = 1; i <= n; i++) dfs(graph, i);
    for (int i = 1; i <= n; i++) {
        cout << i << " " << seen[i] << " " << visited[i] << endl;
    }
}



Measured memory_bytes: 3692
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=305;
int n,a[maxn];
double exp[maxn][maxn][maxn];
bool vis[maxn][maxn][maxn];
double solve(int cnt1,int cnt2,int cnt3)
{
    if(vis[cnt1][cnt2][cnt3])
        return exp[cnt1][cnt2][cnt3];
    vis[cnt1][cnt2][cnt3]=true;
    if(cnt1+cnt2+cnt3==0)
        return exp[cnt1][cnt2][cnt3]=0.0;
    double res=(double)n;
    if(cnt1) res+=solve(cnt1-1,cnt2,cnt3)*cnt1;
    if(cnt2) res+=solve(cnt1+1,cnt2-1,cnt3)*cnt2;
    if(cnt3) res+=solve(cnt1,cnt2+1,cnt3-1)*cnt3;
    res/=(double)(cnt1+cnt2+cnt3);
    return exp[cnt1][cnt2][cnt3]=res;
}
int main()
{
    scanf("%d",&n);
    int cnt1=0,cnt2=0,cnt3=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==1) cnt1++;
        if(a[i]==2) cnt2++;
        if(a[i]==3) cnt3++;
    }
    double ans=solve(cnt1,cnt2,cnt3);
    printf("%.12lf\n",ans);
    return 0;
}


Measured memory_bytes: 125200
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        
        String s = scan.next();
        String t = scan.next();
        
        char[] ss = new char[s.length()];
        char[] tt = new char[t.length()];
        
        for(int i=0;i<s.length();i++)
        {
            ss[i] = s.charAt(i);
        }
        
        for(int i=0;i<t.length();i++)
        {
            tt[i] = t.charAt(i);
        }
        
        Arrays.sort(ss);
        Arrays.sort(tt);
      
      	int len = Min(ss.length,tt.length);
        
        for(int i=0;i<len;i++)
        {
            if(ss[i]<tt[tt.length-i-1])
            {
                System.out.println("Yes");
                return;
            }
            else if(ss[i]==tt[i])
            {
                continue;
            }
            else
            {
                System.out.println("No");
                return;
            }
        }
        
        if(s.length()<t.length())
        {
            System.out.println("Yes");
            
        }
        else
        {
            System.out.println("No");
        }
    }
  
  	static int Min(int a,int b){
      	int min = a;
      	if(b<a)
        {
			min = b;
        }
      	return min;
  	}
}

Measured memory_bytes: 22484
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>

using namespace std;

string s;
int n = 0;

int main()
{
    cin >> s;
    for(int i = 1; i < (int) s.length(); i++) {
        if(s.at(i) != s.at(i-1)) n++;
    }

    cout << n << endl;
    return 0;
}


Measured memory_bytes: 512
n=int(input())
P=[int(x) for x in input().split()]
ans=0

for i in range(0,n-2):
    X=[P[i],P[i+1],P[i+2]]
    if min(X)!=P[i+1] and max(X) !=P[i+1]:
        ans+=1
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59

int main(){
  ll i,j;
  ll n,m;
  cin>>n>>m;
  ll a[n];
  map<ll,ll> ma;
  ll ans=0;
  for(i=0;i<n;i++) {
    cin>>a[i];
    ans+=a[i]*m;
  }
  for(i=0;i<m;i++){
    ll x;
    cin>>x;
    ma[x]++;
  } 

  VI c(202020,0);
  for(auto it=ma.begin();it!=ma.end();++it){
    for(j=1;j*(it->first)<202020;j++){
      c[j*(it->first)]+=it->first*(it->second);
    }
  }
  for(i=1;i<202020;i++){
    c[i]+=c[i-1];
  }

  for(i=0;i<n;i++) ans-=c[a[i]];
  cout<<ans<<endl;  
  
  return 0;
}

//いもすほうはつよい


Measured memory_bytes: 18132
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>

//LLONG_MAX
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
using namespace std;

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

	for (int i = 0; i < 100; i++)
	{
		int a = 7 * i;
		int b = N - a;
		if (b >= 0 && b % 4 == 0)
		{
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}







Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100

int main(void)
{
    int i, j;

    char ring[MAX + 1];
    char make[MAX + 1];
    scanf("%s %s", ring, make);

    char ring2[MAX * 2 + 1];
    for (i = 0; (ring2[i] = ring[i]) != '\0'; i++){
        ;
    }
    int len_ring = i;
    for (i = 0; (ring2[len_ring + i] = ring[i]) != '\0'; i++){
        ;
    }

    for (i = 0; make[i] != '\0'; i++){
        ;
    }
    int len_make = i;

    enum {YES, NO} y_n;
    y_n = NO;
    for (i = 0; i < len_ring; i++){
        if (ring2[i] == make[0]){
            for (j = 0; j < len_make; j++){
                if (ring2[i + j] == make[j]){
                    y_n = YES;
                    continue;
                }else{
                    y_n = NO;
                    break;
                }
            }
            if (y_n == YES){
                break;
            }else{
                continue;
            }
        }
    }

    if (y_n == YES){
        printf("Yes\n");
    }else{
        printf("No\n");
    }

    return 0;
}

Measured memory_bytes: 944
def gcd(x, y):
    a = x
    b = y
    while True:
        r = a % b
        if r == 0:
            break
        a = b
        b = r
    return b


N = int(input())
A = list(map(int, input().split()))

B = sorted(A)
b = B[0]

for i in range(1, N):
    b = gcd(b, B[i])

print(b)


Measured memory_bytes: 14228
#include <stdio.h>

int main(void)
{
	int data[100];
	int max = 0;
	int n;
	int i;
	
	for (i = 0; i < 100; i++){
		data[i] = 0;
	}
	
	while (scanf("%d", &n) != EOF){
		data[n]++;
		if (data[n] > max){
			max = data[n];
		}
	}
	
	for (i = 0; i < 100; i++){
		if (max == data[i]){
			printf("%d\n", i);
		}
	}
	
	return (0);
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1e8

int main(){
	int n,m,s,a,b;
	while(cin>>n>>m>>s>>a>>b,n){
		s--; a--; b--;
		vvi f(n,vi(n,INF));
		rep(i,n)f[i][i]=0;
		
		rep(i,m){
			int p,q,c;
			cin>>p>>q>>c;
			p--; q--;
			f[p][q]=c;
		}
		
		rep(k,n)rep(i,n)rep(j,n){
			f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
		}
		
		int ans=INF;
		rep(i,n){
			ans=min(ans,f[s][i]+f[i][a]+f[i][b]);
		}
		cout<<ans<<endl;
	}
	return 0;
}



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


def solve(D: int, G: int, p: "List[int]", c: "List[int]"):
    w = 2 ** D
    ret = float('inf')
    for i in range(w):
        s = 0
        cc = 0
        ri = 0
        for j in range(D):
            if ((i >> j) & 1) == 1:
                s += 100 * (j + 1) * p[j] + c[j]
                cc += p[j]
            else:
                ri = j
        if s < G:
            for j in range(p[ri] - 1):
                s += 100 * (ri + 1)
                cc += 1
                if G <= s:
                    break
        if G <= s:
            ret = min(ret, cc)
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    D = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    p = [int()] * (D)  # type: "List[int]" 
    c = [int()] * (D)  # type: "List[int]" 
    for i in range(D):
        p[i] = int(next(tokens))
        c[i] = int(next(tokens))
    result = solve(D, G, p, c)
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 6036
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;
public class Main {
	static Scanner sc = new Scanner(System.in);static void p(int i) {System.out.println(i);}static void p(long i) {System.out.println(i);}static void p(String i) {System.out.println(i);}static void p(double i) {System.out.println(i);}
	
	
	public static void main(String[] args) {
		int n=sc.nextInt();
		int x=sc.nextInt();
		Random r=new Random();
		int a[]=new int[n+1];
		
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		a[n]=x;
		Arrays.sort(a);
		
		long mi=1000000009;
		
		for(int i=1;i<=n;i++) {
			//p(i+"ba "+(a[i]-a[i-1]));
			if(a[i]-a[i-1]==0)continue;
			mi=Math.min(a[i]-a[i-1], mi);
		}
		
		ArrayList<Long> cc=new ArrayList<>(100);
		
		for(long i=1;i*i<=mi;i++) {
			if(mi%i==0) {
				cc.add(i);
				cc.add(mi/i);
			}
		}
		
		Collections.sort(cc);
		Collections.reverse(cc);
	
		for(int g=0;g<cc.size();g++) {
			mi=cc.get(g);
			//p("MIMIMI"+mi);
			boolean xx=true;
			for(int i=1;i<=n;i++) {
				if((a[i]-a[i-1])%mi!=0) {
					xx=false;
					break;
				}
			}
			if(xx)break;
		}
		p(mi);
		
		
	}
	
}
	


Measured memory_bytes: 49636
use proconio::input;

fn median(a: &Vec<i64>) -> i64 {
    let n = a.len();
    a[n/2] + if n%2 == 1 { 0 } else { a[n/2-1] }
}

fn main() {
    input! {
        n : usize
    };
    let mut a = vec![0; n];
    let mut b = vec![0; n];
    for i in 0..n {
        input! {
            u : i64,
            v : i64
        };
        a[i] = u;
        b[i] = v;
    }
    a.sort();
    b.sort();
    println!("{}", median(&b) - median(&a) + 1);
}


Measured memory_bytes: 9724
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using static Scanner;

class Program
{
    static void Main(string[] args) {
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Solve();
        Console.Out.Flush();
    }
    static void Solve() {
        int N = ScanInt(), K = ScanInt();
        var nums = new int[N + 1];
        for (int i = 0; i < N; i++) {
            var A = ScanInt();
            nums[A]++;
        }
        var list = new List<int>();
        foreach (var v in nums) {
            if (v > 0) list.Add(v);
        }
        var answer = 0;
        if (list.Count > K) {
            list.Sort();
            for (int i = 0; i < list.Count - K; i++) answer += list[i];
        }
        Console.WriteLine(answer);
    }
}

public static class Scanner
{
    static readonly Stream stream = Console.OpenStandardInput();
    static readonly byte[] buffer = new byte[1024];
    static int length, p;
    static bool isEof;
    private static byte ConsoleIn() {
        if (isEof) return 0;
        if (p < length) return buffer[p++];
        p = 0;
        if ((length = stream.Read(buffer, 0, 1024)) > 0) return buffer[p++];
        isEof = true;
        return 0;
    }
    public static char GetChar() {
        var by = ConsoleIn();
        while ((by < '!' || '~' < by) && !isEof) by = ConsoleIn();
        return (char) by;
    }
    public static int ScanInt() {
        var temp = 0;
        for (var ch = GetChar(); '0' <= ch && ch <= '9'; ch = (char) ConsoleIn()) {
            temp = temp * 10 + ch - '0';
        }
        return temp;
    }
}

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
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;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}
struct edge {
  ll to, cost;
};

ll divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  ll a = ret.size();
  return a;
}

bool IsPrime(int num) {
  if (num < 2) return false;
  else if (num == 2) return true;
  else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

  double sqrtNum = sqrt(num);
  for (int i = 3; i <= sqrtNum; i += 2) {
      if (num % i == 0)
      {
          // 素数ではない
          return false;
      }
  }

  // 素数である
  return true;
}

int main() {
  int N; cin >> N;
  vector<ll> tmp(N + 1, 0); tmp[1] = 1;
  for (ll i = 1; i <= N; i++) for (ll j = i; j <= N; j += i)
        tmp[j] += 1;
  ll ans = 0;
  for(int i = 1; i <= N; ++i) {
    ans += i * tmp[i];
    //cout << i << " " << tmp[i] << endl;
  }
  cout << ans - 1 << endl;
}

Measured memory_bytes: 81364
inf = 10**10
N, M = map(int, input().split())
E = []
edge = [[inf]*N for _ in range(N)]
for i in range(N):edge[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    E.append((a-1, b-1))
    edge[a-1][b-1] = c
    edge[b-1][a-1] = c
flag = [[False]*N for _ in range(N)]
def warshall_floyd(d):
    next_v = [[set([i]) for i in range(N)] for j in range(N)]
    for i in range(N):
        for a in range(N):
            for b in range(N):
                if d[a][b] > d[a][i]+ d[i][b]:
                    d[a][b] = d[a][i]+ d[i][b]
                    next_v[a][b] = next_v[a][i].copy()
                elif d[a][b] == d[a][i]+ d[i][b]:
                    next_v[a][b]|=next_v[a][i]
    return (next_v, d)
next_v, d = warshall_floyd(edge)    
ans = M
for a, b in E:
    if any(b in next_v[a][i] or a in next_v[b][i] for i in range(N)):
        ans -= 1
print(ans)
    

Measured memory_bytes: 46960
N, K = map(int, input().split())
A = list(map(int, input().split()))


# 最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


g = A[-1]
for i in A[:-1]:
    g = gcd(g, i)

a = max(A)
if (a - K) % g == 0 and a >= K:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 14224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
const int N = 1e6+5;
int fac[N], ifac[N];
void init(int n=1e6){
	fac[0]=ifac[0]=1;for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);
	ifac[n]=qpow(fac[n],mod-2);for(int i=n-1;i;i--)ifac[i]=mul(ifac[i+1],i+1);
}
inline int binom(int a,int b){
	if(b<0||b>a)return 0;
	return mul(fac[a],mul(ifac[b],ifac[a-b]));
}
int n,k;

int main()
{
	init();
	cin >> n >> k;
	int ans=0;
	if(n > k){puts("0");return 0;}
	for(int A=0;A<=k;A++)if(A>=k-A){
		int B=k-A;
		if(A==k-A){
			ans = add(ans, sub(binom(A+B-1,A), binom(A+B-1,2*A-n+1)));
		}else{
			ans = add(ans, sub(binom(A+B,A), binom(A+B,2*A-n+1)));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 8064
#include<cstdio>

char s[100010],t[100010];int n;

bool work()
{
	for(int i=1;i<=n;i++)
	{
		bool f=s[i]=='x';
		f^=t[i]=='W';
		f^=t[i-1]=='W';
		t[i+1]=f?'W':'S';
	}
	return t[n]==t[0]&&t[n+1]==t[1];
}


int main()
{
	scanf("%d%s",&n,s),s[n]=s[0];
	if(t[0]='S',t[1]='S',work())goto print;
	if(t[0]='S',t[1]='W',work())goto print;
	if(t[0]='W',t[1]='S',work())goto print;
	if(t[0]='W',t[1]='W',work())goto print;
	puts("-1");
	return 0;
 print:
	t[n]=0,puts(t);
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = int(a); i < int(b); i++)
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

int main() {
    string S;
    cin >> S;
    
    bool flg = true;
    rep(i, S.size() - 1) {
        repi(j, i + 1, S.size()) {
            if(S.at(i) == S.at(j)) {
                flg = false;
                break;
            }
        }
    }

    cout << (flg ? "yes" : "no") << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>;

int main(void)
{
	double x1,x2,y1,y2,x;
	scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
	x=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
	printf("%lf",x);
	return 0;
}

Measured memory_bytes: 652
def count(s,t):
  c = 0
  for i in range(k):
    if s[i] != t[i]:
      c += 1
  return c

s = input()
n = len(s)
t = input()
k = len(t)
ans = 10000
for i in range(n-k+1):
  ans = min(ans,count(s[i:i+k],t))
print(ans)

Measured memory_bytes: 9056
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <random>
#include <algorithm>
#include <functional>

using namespace std;
typedef long long ll;

const int INF = (1 << 30) - 1;
const ll INFLL= (1LL << 61) - 1;
const int MOD = 1000000007;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  ll N;
  cin>>N;
  cout<<N*N*N<<endl;
}


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


const ll NINF = (ll)(-1e18);
int main() {
    int n;
    scanf("%d", &n);
    vector<vector<ll>> a(n, vector<ll>(n));
    for (auto &j: a) for (auto &i: j) scanf("%lld", &i);
    vector<ll> dp(1<<n);
    vector<ll> sm(1<<n, NINF);

    dp[0] = 0ll;
    for (int i=1; i<(1<<n); i++) {
        dp[i] = 0ll;
        for (int j=i; j>0; j = (j-1) & i) {
            
            if (sm[j]==NINF) {
                ll tempsm = 0;
                for (int k=0; k<n; k++) {
                    if ((1<<k) & j) {
                        for (int l=k+1; l<n; l++) {
                            if (((1<<l)&j)) {
                                tempsm += a[l][k];
                            }
                        }
                    }
                }
                sm[j] = tempsm;
            }
            dp[i] = max(dp[i], sm[j]+dp[i & (~j)]);
        }

    }

    printf("%lld\n", dp[(1<<n)-1]);
}

Measured memory_bytes: 1408