akhauriyash/Code-Regression huggingface dataset:
import std.algorithm;
import std.array;
import std.bigint;
import std.bitmanip;
import std.conv;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T diff(T)(const ref T a, const ref T b) { return a > b ? a - b : b - a; }

T[] readToArray(T)() {
    return readln.split.to!(T[]);
}

void readInto(T...)(ref T ts) {
    auto ss = readln.split;
    foreach(ref t; ts) {
        t = ss.front.to!(typeof(t));
        ss.popFront;
    }
}

// 冪乗をmod取りつつ計算
ulong modPow(ulong a, ulong n, ulong m) {
    ulong r = 1;
    while (n > 0) {
        if(n % 2 != 0) r = r * a % m;
        a = a * a % m;
        n /= 2;
    }
    return r;
}

// フェルマーの小定理から乗法逆元を計算
// 定理の要請により法は素数
ulong modInv(ulong a, ulong m) {
    return modPow(a, m-2, m);
}

// mod取りつつ組み合わせを計算
// modInvを使っているので法は素数
ulong modComb(ulong n, ulong r, ulong m) {
    if (n == r) return 1;
    if (r == 0) return 1;
    if (n < r) return 0;

    ulong up = 1;
    ulong down = 1;
    for(ulong i = n-r+1; i <= n; i++) {
        up *= i;
        up %= m;
    }
    for(ulong i = 2; i <= r; i++) {
        down *= i;
        down %= m;
    }
    return up*modInv(down, m) % m;
}

ulong MOD = 1000000007;

void main() {
    ulong n, k;
    readInto(n, k);
    for (ulong i = 1; i <= k; i++) {
        writeln(modComb(n-k+1, i, MOD)*modComb(k-1, i-1, MOD) % MOD);
    }
}


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

int main() {
  int n;
  scanf("%d", &n);
  list<int> v;
  for(int i=0; i<n; i++) {
    char com[15];
    int x;
    scanf("%s", com);
    if (com[0]=='i') {
      scanf("%d", &x);
      v.push_front(x);
    } else if (com[6]=='F') {
      v.pop_front();
    } else if (com[6]=='L') {
      v.pop_back();
    } else if (com[0]=='d') {
      scanf("%d",&x);
      for (list<int>::iterator itr=v.begin(); itr!=v.end(); itr++) {
        if (*itr==x){
          v.erase(itr);
          break;
        }
      }
    }
  }
  int i = 0;
  for (list<int>::iterator itr=v.begin(); itr!=v.end(); itr++) { 
    if (i++) {
      cout << " " << flush;
    }
    cout << *itr;
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 34392
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N,x,y,z,i,l,A;
  cin >> N;
  y = 9999;
  
  for (i = 0; i < N; i++) {
    cin >> A;
    x = 0;
    for (; A % 2 == 0; A /= 2) { 
      x += 1;
    }
    if (y >= x) {
      z = x;
      y = x;
    }
    else {
      z = y;
    }
  }
  cout << z << endl;
}

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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aut(r,v) __typeof(v) r = (v)
#define each(it,o) for(aut(it,(o).begin()); it!=(o).end(); ++it)
#define reach(it,o) for(aut(it,(o).rbegin()); it!=(o).rend(); ++it)
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T1, typename T2> ostream& operator<<(ostream& o, const pair<T1, T2>& p)
{return o<<"("<<p.first<<", "<<p.second<<")";}
template<typename T>string join(const vector<T>&v, string del=", ")
{stringstream s;rep(i,v.size())s<<del<<v[i];return s.str().substr(del.size());}
template<typename T>ostream& operator<<(ostream& o, const vector<T>&v)
{if(v.size())o<<"["<<join(v)<<"]";return o;}
template<typename T>ostream& operator<<(ostream& o, const vector<vector<T> >&vv)
{int l=vv.size();if(l){o<<endl;rep(i,l){o<<(i==0?"[ ":",\n  ")<<vv[i]<<(i==l-1?" ]":"");}}return o;}
template<typename T>ostream& operator<<(ostream& o, const set<T>& st)
{vector<T> v(st.begin(),st.end());o<<"{ "<<join(v)<<" }";return o;}
template<typename T1, typename T2>ostream& operator<<(ostream& o, const map<T1, T2>& m)
{each(p,m){o<<(p==m.begin()?"{ ":",\n  ")<<*p<<(p==--m.end()?" }":"");}return o;}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const ll INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

template<typename T>
struct BIT{
    int N;
    vector<T> dat;
    BIT(int n) : N(n), dat(n+1,0){ }
    void add(int i, T num){
        for(int x = i+1; x <= N; x += (x & -x)) dat[x] += num;
    }
    T sum(int i){
        T ret = 0;
        for(int x = i+1; x > 0; x -= (x & -x)) ret += dat[x];
        return ret;
    }
    T sum(int i, int j){
        return sum(j) - sum(i-1);
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");

    int n, d, a;
    cin >> n >> d >> a;
    vector<pii> P;
    rep(i,n){
        int x, h;
        cin >> x >> h;
        P.emplace_back(x, h);
    }
    sort(all(P));

    ll ans = 0;
    BIT<ll> bit(n+1);
    rep(i,n){
        ll x = P[i].fi, h = P[i].se;
        h -= bit.sum(i);
        if(h <= 0) continue;
        ll m = (h+a-1) / a;
        ans += m;
        ll da = m * a;
        bit.add(i, da);
        int r = min(x + 2 * d, 1001001001ll);
        int j = upper_bound(P.begin(), P.end(), pii(r+1, -1)) - P.begin();
        bit.add(j, -da);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3568
#include <cstdio>
#include <cmath>
using namespace std;

#define EPS 1e-10

bool isequal(double a, double b)
{
	return fabs(a-b) < EPS;
}

int N,I[256];
double calc(int S, int A, int C)
{
	int R=S, cnt[256]={0};
	for(int i=0; i<N; i++)
	{
		R=(A*R+C)%256;
		cnt[(I[i]+R)%256]++;
	}
	
	double ret=0;
	for(int i=0; i<256; i++)
	{
		if(cnt[i]!=0)
		ret+=(1.0*cnt[i]/N)*log(1.0*cnt[i]/N);
	}
	
	
	return -ret;
}

int main()
{
	while(scanf("%d", &N), N)
	{
		for(int i=0; i<N; i++)
			scanf("%d", &I[i]);
			
		int as=99, aa=99, ac=99;
		double mi=1e10;
		for(int s=0; s<=15; s++)
		for(int a=0; a<=15; a++)
		for(int c=0; c<=15; c++)
		{
			double ret=calc(s,a,c);

			if(isequal(ret,mi))
			{
				if(s<as)
				{
					as=s; aa=a; ac=c;
				}
				else if(as==s&&a<aa)
				{
					aa=a; ac=c;
				}
				else if(as==s&&aa==a&&c<ac)
				{
					ac=c;
				}
			}
			else if(ret<mi)
			{
				mi=ret;
				as=s; aa=a; ac=c;
			}
		}
		
		printf("%d %d %d\n", as, aa, ac);
	}
}

Measured memory_bytes: 780
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,a,b) for(ll i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()

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

    ll s = 0;
    ll e = n;
    ll m = 0;
    bool f[n];
    string tmp;

    rep(i, 0, 20){
        if(i == 0){
            cout << 0 << endl;
            cin >> tmp;
            if(tmp == "Male"){
                rep(i, 0, n){
                    if(i % 2 == 0){
                        f[i] = true;
                    }else{
                        f[i] = false;
                    }
                }
            }else if(tmp == "Female"){
                rep(i, 0, n){
                    if(i % 2 == 0){
                        f[i] = false;
                    }else{
                        f[i] = true;
                    }
                }
            }else{
                return 0;
            }
        }else{
            m = (s + e) / 2;
            cout << m << endl;
            cin >> tmp;
            if(tmp == "Male"){
                if(f[m] == true){
                    s = m;
                }else{
                    e = m;
                }
            }else if(tmp == "Female"){
                if(f[m] == true){
                    e = m;
                }else{
                    s = m;
                }
            }else{
                return 0;
            }
        }
    }
}


Measured memory_bytes: 980
import sys
from collections import Counter
n = int(input())
c = list(input())
s = Counter(c)
if s['R'] == 0 or s['W'] == 0:
  print('0')
  sys.exit()
pos_w=0
pos_r=n-1
count = 0
for i in range(pos_w, n):
  if c[i] != 'W':
    continue
  pos_w = i
  for j in range(pos_r, -1, -1):
    if c[j] != 'R':
      continue
    pos_r = j
    if pos_w > pos_r:
      print(count)
      sys.exit()
    c[i] = 'R'
    c[j] = 'W'
    count += 1
    break

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

int main() {
	int n, k;
  	cin >> n >> k;
  	string a[n];
  	for (int i = 0; i < n; i++) cin >> a[i];
  	sort(a, a + n);
  	for (string s : a) cout << s;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int main(){
  ll n;cin >> n;
  vector<ll> a(n),c(61),t(61);
  t[0]=1;
  for(int i=1;i<61;i++){
    t[i]=t[i-1]*2;
    t[i]%=mod;
  }
  for(int i=0;i<n;i++){
    cin >> a[i];
    for(int j=0;j<61;j++){
      if((a[i]>>j)&1){
        c[j]++;
      }
    }
  }
  ll ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<61;j++){
      if((a[i]>>j)&1){
        ans+=t[j]*(n+mod-c[j]);
        ans%=mod;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 2560
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input! {
        x: usize,
    }
    if x == 0 {
        println!("1")
    } else {
        println!("0")
    }
}


Measured memory_bytes: 2164
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MAX=1000000007;

  
signed main() {
    int n;
    cin>>n;
    int k=1;
    int ans=0;
    for(int i=1;i<=n;i++){
      int i0=i;
      k=0;
      while(i0!=0){
        k++;
        i0/=10;
      }
      if(k%2==1)ans++;
    }
    cout<<ans;
    
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const LL MOD = 1000000007LL;
int main() {
	int N;
	cin >> N;
	string S[2];
	cin >> S[0] >> S[1];
	vector<int> v;
	int x = 0;
	while (x < N) {
		if (x + 1 < N&&S[0][x] == S[0][x + 1]) {
			v.push_back(0);
			x += 2;
		}
		else {
			v.push_back(1);
			x++;
		}
	}
	LL ans;
	if (v[0] == 0) ans = 6;
	else ans = 3;
	for (int i = 1; i < v.size(); i++) {
		if (v[i - 1] == 1) ans = (ans * 2) % MOD;
		else if (v[i] == 0) ans = (ans * 3) % MOD;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define N 100005
int l,r;
vector<int> vis[N];
int color[N];
int cnt[3];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n-1;i++)
    {
        cin>>l>>r;
        vis[l].push_back(r);
        vis[r].push_back(l);
    }
    queue<int> que;
    que.push(1);
    que.push(n);
    color[1]=1;
    color[n]=2;
    while(!que.empty())
    {
        int tmp=que.front();
        que.pop();
        cnt[color[tmp]]++;
        for(int i=0;i<vis[tmp].size();i++)
            if(color[vis[tmp][i]])
            continue;
        else
            color[vis[tmp][i]]=color[tmp],que.push(vis[tmp][i]);
    }
    if(cnt[1]>cnt[2])
        cout<<"Fennec"<<endl;
    else
        cout<<"Snuke"<<endl;
    return 0;
}


Measured memory_bytes: 6272
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define set_bits(a) __builtin_popcount(a)
#define pb push_back
#define pf push_front
#define mod 1000000007
#define M 998244353
#define fi first
#define se second
#define endl '\n'
#define INF 1e18
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


int main()
{
    string s;
    cin>>s;
    stack<char>st;
    ll i,j,n=s.length();


    for(i=0;i<n;i++)
    {
        char x = s[i];
        if(st.empty())
        {
            st.push(s[i]);
        }
        else
        {
            char p = st.top();
            if(p != x)
            {
                st.pop();
            }
            else
            {
                st.push(x);
            }
        }
    }

    ll ans = n - st.size();
    cout<<ans<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

typedef long long ll;
typedef pair<ll, ll> p;

int n, m, q;
ll res = 0;
vector<int> a, b, c, d;

void solve(vector<int> state){
  ll tmp = 0;
  for (int i = 0; i < q; ++i) {
    if(state[b[i]-1] - state[a[i]-1] == c[i]) tmp += d[i];
  }
  // print(state);
  // cout << tmp <<endl;
  chmax(res, tmp);
}

void dfs(int step, vector<int> state){
  if(step == n) {
    solve(state);
    return;
  }

  for (int i = 1; i <= m; ++i) {
    if(step >= 1) chmax(i, state[step-1]);
    state[step] = i;
    dfs(step+1, state);
  }
}


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >>  n >> m >> q;
  a = vector<int> (q);
  b = vector<int> (q);
  c = vector<int> (q);
  d = vector<int> (q);
  rep(i, q) cin >> a[i] >> b[i] >> c[i] >> d[i];
  dfs(0, vector<int> (n));
  cout << res << endl;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,k,sum=0;
    cin >> n >> k;
    vector<int>l(n); 
    for(int i=0;i<n;i++)
        cin >> l.at(i);
    sort(l.begin(),l.end(),greater<int>());
    for(int i=0;i<k;i++)
        sum+=l.at(i);
    cout << sum << endl;
}


Measured memory_bytes: 256
def main():
	N, M = [int(x) for x in input().split(" ")]
	A = [int(a) for a in input().split(" ")]
	D = []
	for i in range(len(A)):
		tmp = A[i]
		while tmp > 0:
			half = int(tmp / 2)
			D.append(tmp - half)
			tmp = half
	D.sort(reverse=True)
	print(sum(A) - sum(D[:M]))

main()

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

int A[201010];

signed main(void){ 
  
  string s ; cin >> s;
  int n = (int)s.size();
  string t = s.substr(0,(n-1)/2);
  string u = s.substr((n+1)/2,n);
  
  string tt = t; reverse(tt.begin(),tt.end());
  string uu = u; reverse(uu.begin(),uu.end());
  
  string ss = s; reverse(ss.begin(),ss.end());
  
  if( s == ss && t == tt && u == uu){ 
    cout<< "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
  
  
  return 0;
}
  

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define INT(x) int x; scanf("%d",&x)
#define INPUT(x) scanf("%d",&x)
#define REP1(x,n) for(int x = 0; x < n; x++)
#define REP2(x,s,e) for(int x = s; x <= e; x++)
#define RREP1(x,n) for(int x = n-1; x >= 0; x--)
#define RREP2(x,s,e) for(int x = s; x >= e; x--)
#define BR printf("\n")
#define INF 2000000000

typedef long long ll;
int A[100001];

int main(){
    INT(N);INT(L);
    REP2(i,1,N){
        INPUT(A[i]);
    }
    
    bool flag = 0;
    int i_m = 1;
    REP2(i,2,N){
        if (A[i] + A[i-1] >= L) {
            flag = 1;
            i_m = i-1;
            break;
        }
    }
    
    if (flag == 0) {
        cout << "Impossible" << endl;
    }else{
        vector<int> V;
        V.push_back(i_m);
        RREP2(i,i_m-1,1){
            V.push_back(i);
        }
        REP2(i,i_m+1,N-1){
            V.push_back(i);
        }
        cout << "Possible" << endl;
        RREP1(i,N-1){
            cout << V[i] << endl;
        }
    }
    
    return 0;
}

Measured memory_bytes: 1784
from functools import reduce

def main():
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 一文字のみを読み込み
    # s = input().rstrip().split(' ')
    
    # スペース区切りで標準入力を配列として読み込み
    # s = input().rstrip().split(' ')

    # 位置文字ずつ標準入力を配列として読み込み
    s = list(input().rstrip())
    # N, A = [int(_) for _ in input().split()]
    # X = [int(_) for _ in input().split()]
    sum = 0
    for i in range(1 << len(s)-1):
        e = s[0]
        for j in range(len(s)-1):
            # iのうち、jbit目が立っているか
            if(i & (1 << j)):
                e = e + '+' + s[j+1]
            else:
                e = e + s[j+1]
        sum += eval(e)
        
    print(sum)
if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.Arrays;
import java.util.Collections;

class Main {
    public static void main (String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        StringBuilder sb = new StringBuilder(sc.next());

        System.out.println(sb.reverse());
    }
}

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

using namespace std;

int main() {
    int A,B,C,X,Y;
    cin >> A >> B >> C >> X >> Y;

    int min_sum = 2000000000;
    int x, y;

    for(int i = 0; i <= 2*max(X, Y); i += 2) {
        x = X-i/2;
        y = Y-i/2;
        if(x <= 0) {
            x = 0;       
        } 
        if(y <= 0) {
            y = 0;
        }
        min_sum = min(min_sum, A*x + B*y + C*i);
    }

    cout << min_sum << endl;
	return 0;
}

Measured memory_bytes: 3612
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            flag = True
            if i != 0 and s[i-1][j] == '#':
                flag = False
            if i != h-1 and s[i+1][j] == '#':
                flag = False
            if j != 0 and s[i][j-1] == '#':
                flag = False
            if j != w-1 and s[i][j+1] == '#':
                flag = False
            if flag:
                print('No')
                exit()
print('Yes')


Measured memory_bytes: 9160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll find(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool unite(ll x, ll y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return find(x) == find(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[find(x)];
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int>ps(N);
    for(int i=0; i<N; i++)cin >> ps[i];
    UnionFind uf(N);
    uf.init(N);
    for(int i=0; i<M; i++){
        int xi, yi;
        cin >> xi >> yi;
        xi--;
        yi--;
        uf.unite(xi,yi);
    }
    int cnt = 0;
    for (int i=0; i<N; i++){
        if (uf.find(i) == uf.find(ps[i]-1))cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

template<typename T>
class MaximumFlow{
private:
  struct edge{int to; T cap; int rev;};
  vector<vector<edge> > Graph;
  vector<int> level, iter; //s??????????????¢,???????????§????????????
  void bfs(int s){
    fill(all(level), -1);
    queue<int> q;
    level[s]=0;
    q.push(s);
    while(!q.empty()){
      int v=q.front(); q.pop();
      for(auto e : Graph[v]){
        if(e.cap>0 && level[e.to]<0){
          level[e.to] = level[v]+1;
          q.push(e.to);
        }
      }
    }
  }
  T dfs(int v, int t, T f){
    if(v==t) return f;
    for(int &i=iter[v]; i<(int)Graph[v].size(); i++){
      auto &e = Graph[v][i];
      if(e.cap>0 && level[v]<level[e.to]){
        T d = dfs(e.to, t, min(f, e.cap));
        if(d>0){
          e.cap -= d;
          Graph[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
public:
  MaximumFlow(int n){
    Graph = vector<vector<edge> >(n, vector<edge>());
    level = vector<int>(n);
    iter = vector<int>(n);
  }
  T max_flow(int s, int t){
    T flow=0;
    while(true){
      bfs(s);
      if(level[t] < 0) break;
      fill(all(iter), 0);
      T f;
      while( (f=dfs(s,t,INF)) > 0){
        flow += f;
      }
    }
    return flow;
  }
  void add_edge(int from, int to, T cap){
    int tos = Graph[to].size(), froms = Graph[from].size();
    Graph[from].pb(((edge){to, cap, tos}));
    Graph[to].pb(((edge){from, 0, froms}));
  }
};

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

  vector<MaximumFlow<int>> flows(n, MaximumFlow<int>(2*n));
  rep(i,1,n) rep(j,1,n) if(i!=j) flows[i].add_edge(2*j, 2*j+1, 1);
  vector<int> f(n,0);

  rep(_,m){
    int a,b;
    cin>>a>>b;
    a--;b--;
    if(b==0) swap(a,b);
    if(f[b]<2){
      flows[b].add_edge(a*2+1,b*2,1);
      f[b] += flows[b].max_flow(1,b*2);
    }

    if(a!=0 && f[a]<1) f[a] += flows[a].max_flow(1,a*2);

    if(f[b]>=2 && (a==0 || f[a]>=1)) cout << "Yes\n";
    else cout << "No\n";

    rep(i,1,n) if(i!=b){
      flows[i].add_edge(a*2+1,b*2,1);
      flows[i].add_edge(b*2+1,a*2,1);
    }
  }

  return 0;
}

Measured memory_bytes: 34944
// Author : Mohamed Sameh
#include <bits/stdc++.h>
typedef long long ll ;
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SZ(a) (int)a.size()
#define Flush fflush(stdout);
using namespace std ;
const int N = 3000;
ll dp[N][N][2];
int a[N], n;
ll solve (int l = 0, int r = n-1, int turn = 0)
{
  if (l > r)return 0;
  ll &ret = dp[l][r][turn];
  if (~ret)return ret;
  if (turn)
  {
    ret = min(solve(l+1, r, !turn) - a[l] , solve(l, r-1, !turn) - a[r] );
  }else
  {
    ret = max(solve(l+1, r, !turn) + a[l] , solve(l, r-1, !turn) + a[r] );
  }
  return ret;
}
int main()
{
  memset(dp, -1, sizeof dp);
  cin >> n ;
  for (int i = 0; i < n; i++)
    cin >> a[i];
  cout << solve() <<"\n";
}


Measured memory_bytes: 141056
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int a,b,c,d;
    std::cin >> a >>b >>c >>d;
    int s=max(a,c);
    int e=min(b,d);
    if(s<e){
        std::cout << e-s << std::endl;
    }else{
        std::cout << 0 << std::endl;
    }
}


Measured memory_bytes: 256
from itertools import permutations
from collections import defaultdict
n, m = map(int, input().split())
routes = permutations(range(2, n+1), n-1)
count = 0

edges = defaultdict(list)

for _ in range(m):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

for route in routes:
    goal = True
    now_node = 1
    for way_index in range(len(route)):
        if not route[way_index] in edges[now_node]:
            goal = False
        now_node = route[way_index]
    if goal:
        count += 1
print(count)

Measured memory_bytes: 40816
x = [[int(i) for i in input().split()] for i in range(3)]
a,b = x[0][0]-x[0][1],x[0][0]-x[0][2]
c,d = x[0][0]-x[1][0],x[0][0]-x[2][0]
if all(x[j][0]-x[j][1]==a and x[j][0]-x[j][2]==b for j in range(3)):
 if all(x[0][k]-x[1][k]==c and x[0][k]-x[2][k]==d for k in range(3)): print("Yes")
 else: print("No")
else: print("No")

Measured memory_bytes: 3064
N = gets.to_i
data = N.times.map{ gets.split.map(&:to_i) }

flag = false

count = 0

t=x=y=0

N.times do |i|
  nt, nx, ny = data[i][0], data[i][1], data[i][2]
  dist = (nx - x).abs + (ny - y).abs
    
  break if t < (x + y).abs

  if nt - t >= dist
    if (nt - t).even? && dist.even? || (nt - t).odd? && dist.odd?
      count += 1
    end
  end
  
  t, x, y = nt, nx, ny
end

flag = true if count == N

puts flag == true ? 'Yes' : 'No'

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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)

//#define doutnl(args...) cout<<args
#define doutnl(...)
#define dout(args...) doutnl(args<<endl;)
#define dprintl(args...) dout("D:"<<__LINE__<<": " args)
#define dv(v) <<#v<<"="<<(v)<<"; "
#define darr(arr,s) <<#arr<<"={";REP(i,s)cout<<arr[i]<<",";cout<<"}; "
typedef long long ll;

int X,Y,Z;
vector<int> V;
int E[120],A[120];

double p[12000][120];
int n;
int main(){
	while(true){
		cin>>X>>Y>>Z;
		if(X==0) break;
		V.clear();
		REP(i,X){
			int temp;
			cin>>temp;
			V.push_back(temp);
		}
		REP(i,Y+1){A[i]=E[i]=0;}
		REP(m,12000)REP(i,Y+1){p[m][i]=0.0;}
		REP(i,Z){
			int n,e,a;
			cin>>n>>e>>a;
			E[n]=e;
			A[n]=a;
			
		}
		p[0][0]=1.0;
		REP(t,Y){
			REP (m,12000){
				if(p[m][t]==0)continue;
				REP(r,X){
					int d=V[r];
					int nxt=min(t+d,Y);
					int nm=m;
					if(E[nxt]==1)nxt=min(nxt+A[nxt],Y);
					else if(E[nxt]==2)nm+=A[nxt];
					else if(E[nxt]==3)nm=max(0,nm-A[nxt]);
					p[nm][nxt]+=p[m][t]/X;
				}
			}
		}
		
		REP(m,12){
			dprintl(dv(m*10)darr(p[m*10],Y+1))
		}
		
		
		double sum=0;
		REP(m,12000){
			sum+=p[m][Y]*m;
		}
		dprintl(dv(sum));
		cout<<(int)sum<<endl;
	}
		
	return 0;
}

Measured memory_bytes: 12464
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;
    static final int ALF = 26;

    Main() {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        long ans = 0;
        int N = sc.nextInt();
        int[] A = new int[N];
        int xor = 0;
        for(int i=0;i<N;i++){
            A[i]=sc.nextInt();
            xor ^= A[i];
        }
        for(int i=0;i<N;i++){
            pw.print(xor^A[i]);
            pw.print(" ");

        }
        pw.println();
        pw.flush();;
    }

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


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

tsk.sort(key=lambda x: x[1])
cnt = 0
A = [0]

for i in range(N):
    cnt += tsk[i][0]
    if cnt > tsk[i][1]:
        print("No")
        exit()
print("Yes")
#print(tsk)   

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

void solve() {
    int n;
    read(n);
    
    vt<int> a(n);
    read(a);
    
    int ans = 1e10;
    int sum = 0;
    FOR(n) {
        sum += a[i];
    }
    int sum2 = 0;
    FOR(i, n - 1) {
        sum -= a[i];
        sum2 += a[i];
        ans = min(ans, abs(sum - sum2));
    }
    print(ans);
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
    //read(tt);
    FOR(tt) {
        //write("Case #", i + 1, ": ");
        solve();
        
    }
    
}



Measured memory_bytes: 4784
/**
 *    author:  math2do
 *    created: 18.05.2020 22:39:56 IST
**/

#include <bits/stdc++.h>

using namespace std;

const double pi = acos(-1.0);

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(18);
  auto calc = [&] (int h, int m) {
    if (h == 12) h = 0;  
    if (m == 60) m = 0;  
    double ang_h = (double) 0.5 * (h * 60 + m);
    double ang_m = (double) 6.0 * m;
    double ang = abs(ang_h - ang_m);
    if (ang > 180.0) {
      ang = 360 - ang;
    }
    return ang;
  };
  int a, b, h, m;
  cin >> a >> b >> h >> m;
  double acute = calc(h, m);
  double c = sqrt(pow(a, 2) + pow(b, 2) - 2 * a * b * cos(acute * pi / 180.0));
  cout << c << endl;
  return 0;
}


Measured memory_bytes: 4124
#include <stdio.h>

int main(){
    int a,b;
    
    scanf("%d %d",&a,&b);
    if (a % 3 == 0 || b % 3 == 0 || (a+b) % 3 == 0) {
        printf("Possible");
    }
    else{
        printf("Impossible");
    }
    return 0;
}

Measured memory_bytes: 128
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 998244353;

fn main() {
    input! {
        a: usize,
        b: usize,
        c: usize,
        d: usize,
    }
    let mut dp = vec![vec![0; d + 1]; c + 1];
    dp[a][b] = 1;
    for i in a + 1..=c {
        dp[i][b] = b * dp[i - 1][b] % M;
    }
    for j in b + 1..=d {
        dp[a][j] = a * dp[a][j - 1] % M;
    }
    for i in a + 1..=c {
        for j in b + 1..=d {
            dp[i][j] = ((dp[i - 1][j] * j % M) + (dp[i][j - 1] * i % M) + M
                - ((i - 1) * (j - 1) * dp[i - 1][j - 1]) % M)
                % M;
        }
    }
    println!("{}", dp[c][d]);
}


Measured memory_bytes: 72500
#include <bits/stdc++.h>
using namespace std;
string S;
int main() {
	cin>>S;
	if(S=="RRR") {
		cout<<3<<endl;
	} else if(S=="RRS") {
		cout<<2<<endl;
	} else if(S=="SRR") {
		cout<<2<<endl;
	} else if(S=="RSR") {
		cout<<1<<endl;
	} else if(S=="SSR") {
		cout<<1<<endl;
	} else if(S=="RSS") {
		cout<<1<<endl; 
	} else if(S=="SRS") {
		cout<<1<<endl;
	} else if(S=="SSS") {
		cout<<0<<endl;
	}
}


Measured memory_bytes: 3592
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;


public class Main {// Main

	public static void main(String[] args) throws Exception {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		sc = new FastScanner(in);
		
		int n = sc.nextInt();
		sum = new long[1<<n];
		long[][] ar = input(n ,n);
		td = new long[(int) (Math.pow(2, n)+1)];
		Arrays.fill(td, Long.MAX_VALUE);
	
		fill( n ,ar);
		
	//	for(long avl : sum)System.out.println(avl);
		long ans = find(ar , n , ((1<<n)-1) );
		out.println(ans);
		out.flush();
	}
	static long[] td ; 
	static long[] sum;
	private static long find(long[][] ar, int n, int mask) {
		if(n==0)return 0 ;
		if(td[mask]!=Long.MAX_VALUE)return td[mask];
		long max = 0 ;
		for(int submask = mask ; submask!=0 ; submask = (submask-1)&(mask)) {
		
			
			
			long temp =sum[submask];
			long rr = find(ar , n  , (submask^mask));
			max = Math.max(max , temp +rr );
		}
		td[mask] = max;
		return max;
	}
	public static void fill(int n , long[][] arr) {
		for(int i = 1 ; i < (1<<n) ;i++) {
			sum[i] = cur(arr , i);
		}
	}

	private static long cur(long[][] arr, int i) {
		ArrayList<Integer> ar = new ArrayList<Integer>();
		int t = i ;
		int ind =0 ;
		while(t>0) {
			if((t&1)==1)ar.add(ind);
			t = t>>1;
			ind++;
		}
		
		int ma = ar.remove(ar.size()-1);
		long ans = sum[i ^ (1<<ma)] ;
		for(int in : ar) {
			ans =ans+ arr[in][ma];
			
		}
		return ans;
	}


	static long mod = 1000000007;
	public static long[][] input(int n, int m) throws Exception {

		long[][] arr = new long[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				arr[i][j] = sc.nextInt();
			}
		}
		return arr;
	}
	
	
	
	static BufferedReader in;
	static FastScanner sc;
	static PrintWriter out;

	static class FastScanner {
		BufferedReader in;
		StringTokenizer st;

		public FastScanner(BufferedReader in) {
			this.in = in;
		}

		public String nextToken() throws Exception {
			while (st == null || !st.hasMoreTokens()) {
				st = new StringTokenizer(in.readLine());
			}
			return st.nextToken();
		}

		public int nextInt() throws Exception {
			return Integer.parseInt(nextToken());
		}

		public long nextLong() throws Exception {
			return Long.parseLong(nextToken());
		}

		public double nextDouble() throws Exception {
			return Double.parseDouble(nextToken());
		}
	}
	
}


Measured memory_bytes: 44160
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;

int main()
{
	char s[101],p[101];
	bool f = false;
	cin >> s;
	cin >> p;
	for(int i = 0;i < strlen(s);i++){
		if(strncmp(s,p,strlen(p)) != 0){
			char temp = s[0];
			for(int j = 0;j < strlen(s);j++){
				if(j != strlen(s) - 1) s[j] = s[j + 1];
				else s[j] = temp;
			}
		}else{
				f = true;
				break;
		}
	}	
	if(f) cout << "Yes" << endl;
	else cout << "No" << endl;
	
	return 0;
}

Measured memory_bytes: 3152
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define MAXN 500005
#define P 1000000007
#define INF 0x3f3f3f3f
#define rint register int
#define LL long long
#define LD long double
#define pii pair<int,int>
using namespace std;

inline int add(int x, int y) {return x+y>=P?x+y-P:x+y;}
inline int sub(int x, int y) {return x>=y?x-y:x-y+P;}

int n, l[MAXN], r[MAXN], t[MAXN], f[MAXN];

struct Line {int k, b, id;} line[MAXN];
vector<Line> vec;

bool CMP1(Line x, Line y)
{
    if(x.k!=y.k) return x.k<y.k;
    return x.b<y.b;
}

bool CMP2(Line x, Line y)
{
    return x.b<y.b;
}

void update(int x, int y)
{
    for(; x<=n+1; x+=(x&-x)) t[x]=add(t[x], y);
}

int query(int x)
{
    int sum=0;
    for(; x; x-=(x&-x)) sum=add(t[x], sum);
    return sum;
}

int main()
{
    scanf("%d", &n);
    for(rint i=1; i<=n; ++i) scanf("%d%d", &line[i].b, &line[i].k);
    sort(line+1, line+n+1, CMP1);
    for(rint i=1; i<=n; ++i) line[i].id=i;
    sort(line+1, line+n+1, CMP2);
    l[n+1]=n+1;
    for(rint i=n; i>=1; --i) l[i]=min(l[i+1], line[i].id);
    for(rint i=1; i<=n; ++i) r[i]=max(r[i-1], line[i].id);
    update(1, 1);
    for(rint i=1; i<=n; ++i)
    {
        f[i]=sub(query(r[i]+1), query(l[i]-1));
        update(r[i]+1, f[i]);
    }
    printf("%d\n", sub(query(n+1), query(n)));
    return 0;
}

Measured memory_bytes: 12800
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int>P;
int a[1005]= { 0 };
int b[1005] = { 0 };
int na[1005] = { 0 };
int nb[1005] = { 0 };
int w, h;
int main() {
	cin >> w >> h;
	for (int i = 0; i < w; i++) {
		cin >> a[i];
		nb[i] = a[i];
	}
	for (int j = 0; j < h; j++) {
		cin >> b[j];
		na[j] = b[j];
	}
	for (int i = 0; i < w; i++) {
		vector<P>v;
		for (int j = 0; j < h; j++) {
			v.push_back(P(b[j], j));
		}
		sort(v.begin(), v.end());
		for (int k = 0; k < a[i]; k++) {
			if (h - 1 - k < 0) {
				cout << "0" << endl;
				return 0;
			}
			if (v[h - 1 - k].first <= 0) {
				cout << "0" << endl;
				return 0;
			}
			else {
				b[v[h - 1 - k].second]--;
			}
		}
	}
	swap(w, h);
	for (int i = 0; i < w; i++) {
		a[i] = na[i];
	}
	for (int j = 0; j < h; j++) {
		b[j] = nb[j];
	}
	for (int i = 0; i < w; i++) {
		vector<P>v;
		for (int j = 0; j < h; j++) {
			v.push_back(P(b[j], j));
		}
		sort(v.begin(), v.end());
		for (int k = 0; k < a[i]; k++) {
			if (h - 1 - k < 0) {
				cout << "0" << endl;
				return 0;
			}
			if (v[h - 1 - k].first <= 0) {
				cout << "0" << endl;
				return 0;
			}
			else {
				b[v[h - 1 - k].second]--;
			}
		}
	}
	cout << "1" << endl;
	return 0;
}


Measured memory_bytes: 3168
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <tuple>
#include <cassert>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define mp(a,b) make_pair((a), (b))
#define mt(a,b,c) make_tuple((a),(b),(c))

typedef long long ll;

int main(){
    int n; cin >> n;
    vector<int> a(n); rep(i,n) cin >> a[i];
    sort(all(a));
    cout << a[n/2] - a[n/2 - 1] << endl; 
    return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    // Your code here!
    string a,b,c;
    cin>>a>>b>>c;
    
    if(a[a.size()-1]==b[0] && b[b.size()-1]==c[0]) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

const ll MAX_N = 1 << 20;
const ll INF = pow(2, 31) - 1;
ll n;
vector<ll> dat(MAX_N, INF);

void init(ll _n) {
  ll temp = 1;
  while (_n >= temp) {
    temp *= 2;
  }
  n = temp;
}

void update(ll i, ll x) {
  i += n - 1;
  dat.at(i) = x;
  while (i != 0) {
    i = (i - 1) / 2;
    dat.at(i) = min(dat.at(i * 2 + 1), dat.at(i * 2 + 2));
  }
}

ll query(ll x, ll y, ll k = 0, ll l = 0, ll r = n) {
  if (r <= x || y <= l) {
    return INF;
  }
  if (x <= l && r <= y) {
    return dat.at(k);
  }
  else {
    ll lm = query(x, y, k * 2 + 1, l, (l + r) / 2);
    ll rm = query(x, y, k * 2 + 2, (l + r) / 2, r);
    return min(lm, rm);
  }
}

int main() {
  ll q;
  cin >> n >> q;
  init(n);
  for (ll i = 0; i < q; ++i) {
    ll com , x, y;
    cin >> com >> x >> y;
    if (com == 0) {
      update(x, y);
    }
    else {
      cout << query(x, y + 1) << "\n";;
    }
    // for (ll i = 0; i < n * 2 - 1; ++i) {
    //   cout << dat.at(i) << " ";
    // }
    // cout << "\n";
  }
}



Measured memory_bytes: 10856
def read():
    N, L = list(map(int, input().strip().split()))
    return N, L


def solve(N, L):
    tastes = [-1] * N
    min_abs_index = 0
    for i in range(N):
        tastes[i] = L + (i+1) - 1
        if abs(tastes[i]) < abs(tastes[min_abs_index]):
            min_abs_index = i
    return sum(tastes[0:min_abs_index]) + sum(tastes[min_abs_index+1:N])


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


Measured memory_bytes: 3064
n,m = map(int,input().split())
li = list(map(int,input().split()))
bc = [list(map(int,input().split())) for _ in range(m)]

bc.sort(key=lambda x:x[1],reverse=True)
l = []
ans = 0

for b,c in bc:
    l += [c]*b
    if len(l) > n:
        break
    
li += l
li.sort(reverse=True)
print(sum(li[:n]))


Measured memory_bytes: 110408
#include <iomanip>
#include <utility>
#include <algorithm>
#include <type_traits>
#include <set>
#include <string>
#include <iostream>
#include <fstream>
#include <cassert>
#include <memory>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <queue>
#include <vector>
#include <array>
#include <chrono>
#include <random>
#include <forward_list>
#include <iomanip>
#include <functional>
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <sstream>
#include <numeric>

using namespace std;
#define MFOR(i,end) for(size_t i = 0, end_i = (end); i < end_i; ++ i)

char S[1000000];

int main()
{
	std::cin >> S;
	//区間数-1
	char mode = S[0];
	int res = 1;
	for (auto i = S+1;*i != '\0';++i)
	{
		if (*i != mode) {
			++res;
			mode = *i;
		}
	}
	std::cout << res - 1 << std::endl;
}

Measured memory_bytes: 384
import networkx as nx

N, Q = [int(x) for x in input().split()]
UF = nx.utils.UnionFind()
for t, u, v in [[int(x) for x in input().split()] for i in range(Q)]:
    if t == 0:
        UF.union(u, v)
    else:
        print(int(UF[u] == UF[v]))


Measured memory_bytes: 100076
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#else
#define eprintf(...) 42
#endif
#define y0 y12345
#define y1 y54321
typedef unsigned long ul;
typedef long long ll;
//typedef pair<int, int> mpair;
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;}
using namespace std;

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
   	int n,m;cin>>n>>m;
	int ma=n, mi=1;
	rep(i, m){
		int a, b;
		cin>>a>>b;
		chmin(ma, b);
		chmax(mi, a);
	}
	if(ma >= mi){cout << ma - mi + 1<< endl;}else{cout << "0" << endl;}
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {

  int vert,horiz,diag;
  int rect=0,diam=0;

  while(scanf("%d,%d,%d",&vert,&horiz,&diag)!=EOF) {

    if(vert*vert+horiz*horiz==diag*diag) rect++;

    if(vert==horiz && vert+horiz>diag) diam++;

  }

  printf("%d\n",rect);

  printf("%d\n",diam);

  return 0;

}

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

const int mx = 3072;

double dp[mx];

int main() {
    int N;
    scanf("%d", &N);
    // dp[i] i coins have heads so far
    dp[0] = 1.0;
    for(int i =0 ;i < N; ++i){
        double p;
        scanf("%lf",&p);
        double _p = 1.0 - p;
        for(int j = i + 1; j >= 0; --j){
            dp[j] = j == 0 ? dp[j] * _p : dp[j] * _p + dp[j-1] * p;
        }
    }
    double ans = 0.0;
    for(int i = N ;i >= 0; --i )
    {
        if(i > N - i)
            ans += dp[i];
    }
    printf("%.10lf\n",ans);
    return 0;
}

Measured memory_bytes: 3800
#include<iostream>
using namespace std;
int main(){
	int N;
	int A[110];
	int B[110];
	int C[110];
	int D[110];
	int sum =0;
	int tmp =0;
	cin >> N;
	
	for(int i=1; i<N+1; i++){
		cin >> A[i];
	}
	for(int i=1; i<N+1; i++){
		cin >> B[i];
	}
	C[1] = 0;
	D[1] = 0;
	for(int i=1; i<N+1; i++){
		C[i+1] = C[i]+A[i];
		D[i+1] = D[i]+B[i];
	}
	for(int i=1; i<N+1; i++){
		sum += B[i];
	}
	for(int i=2; i<N+2; i++){
		int ans =0;
		ans = C[i]+sum-D[i-1];
		if(ans>tmp){
			tmp = ans;
		}
	}
		cout << tmp << endl;
	return 0;
}

 

Measured memory_bytes: 256
s = input()
MOD = 10**9+7

dp = [[0 for i in range(13)] for i in range(len(s)+1)]
dp[0][0] = 1

for i in range(len(s)):
  if s[i]=='?':
    for k in range(10):
      for j in range(13):
        dp[i+1][(j*10+k)%13] = (dp[i+1][(j*10+k)%13] + dp[i][j])%MOD
  else:
    t = int(s[i])
    for j in range(13):
      dp[i+1][(j*10+t)%13] = (dp[i+1][(j*10+t)%13] + dp[i][j])%MOD
print(dp[len(s)][5])

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int rgb=0;
	for(int i=0,t;i<3;++i){
		rgb*=10;
		cin>>t;
		rgb+=t;
	}
	cout<<(rgb%4==0?"YES"s:"NO"s)<<"\n"s;
}

Measured memory_bytes: 256
using System;

namespace ITP1_2_C
{
  class Program
  {
    static void Main(string[] args)
    {
      var tmp = "0";
      var input = Console.ReadLine();
      string[] line = input.Split(' ');
      if (int.Parse(line[0]) > int.Parse(line[1]))
      {
        tmp = line[0];
        line[0] = line[1];
        line[1] = tmp;

      }
      if (int.Parse(line[1]) > int.Parse(line[2]))
      {
        tmp = line[1];
        line[1] = line[2];
        line[2] = tmp;

      }
      if (int.Parse(line[0]) > int.Parse(line[1]))
      {
        tmp = line[0];
        line[0] = line[1];
        line[1] = tmp;

      }

      Console.WriteLine("{0} {1} {2}", line[0], line[1], line[2]);



    }


  }
}



Measured memory_bytes: 17948