akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
ll qp(ll a,ll n){
	ll ans=1;//printf("%lld %lld\n",a,n);
	while(n){
		if(n&1)ans=ans*a%MOD;
		a=a*a%MOD;
		n/=2;
	}
	return ans;
}
int a[100010];
int main(){
	int n,m=0;scanf("%d",&n);
	bool ok=1;
	for(int i=0;i<n;++i){
		int x;
		scanf("%d",&x);
		if(i==0){
			if(x!=0)ok=0;
		}
		else a[x]++;
		m=max(m,x);
	}
	if(!ok)printf("0\n");
	else {
		ll ans=1;
		if(a[0])ans=0;
		ll t=1;
		for(int i=1;i<=m;++i){
			ans=ans*qp(t,a[i])%MOD;
			t=a[i];
		}
		printf("%lld\n",ans);
	}

	return 0;
}

Measured memory_bytes: 640
#coding:utf-8
MOD = 10**9+7
f = [1]
for i in range(10**5+5):
    f.append(f[-1]*(i+1)%MOD)
    
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % MOD
    
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

min_sum = 0
max_sum = 0
ans = 0
for i in range(N-K+1):
    #最小を固定して、残りのk-1個を右側から選ぶ全パターン
    min_sum += A[i] * nCr(N-i-1, K-1)
    #最大を固定して、残りのk-1個を左側から選ぶ全パターン
    max_sum += A[-i-1] * nCr(N-i-1, K-1)
    
    min_sum %= MOD
    max_sum %= MOD
    
ans += max_sum - min_sum

    
print(ans if ans >= 0 else ans + MOD)

Measured memory_bytes: 18544
/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/
 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x
 
using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;
 
const ll MODBASE = 1000000007LL;
const int MAXN = 110;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

string s;
int n;

bool isPalin(int l, int r) {
    int e = r;
    FOR(i,l,r) {
        if (s[i] == s[e]) {
            e--;
        }
        else return false;
    }
    return true;
}

bool solve() {
    if (n == 1) return true;
    if (isPalin(1, n) && isPalin(1, (n-1)/2) && isPalin((n+3)/2, n)) return true;
    return false;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> s;
    n = SZ(s);
    s = " " + s;
    if (solve()) cout << "Yes";
    else cout << "No";
    return 0;
}


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

using namespace std;

/**
 *  Name: Chris M. Perez
 *  University: Interamerican University Metro Campus
 *
**/

#define endl '\n'
#define MOD 10e18
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define gcd(x , y) __gcd(x , y)
#define all(x) (x).begin() , (x).end()
#define forn(i , a , b) for(int i=(a);i<(b);i++)
#define forrange(j , a , b) for(int j=(a);j<=(b);j++)
#define nestedforn(i , a , b , j , c , d) for(int i=(a);i<=(b);i++) for(int j=(c);j<=(d);j++)
#define sort_all(x) sort(all(x))
#define zeros_at_beginning(x) __builtin_clz(x)
#define zeros_at_end(x) __builtin_ctz(x)
#define ones(x) __builtin_popcount(x)
#define parity_even_or_odd_ones __builtin_parity(x)

typedef vector<int> vi;
typedef pair<int , int> pii;
typedef tuple<int , int , int> tiii;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef long long int lli;

             
inline int input(){
  int n;
  scanf("%d" , &n);
  return n;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);
  cout << fixed;

#ifdef LOCAL_DEFINE
  freopen("input.txt" , "rt" , stdin);
#endif
  
  int n; cin >> n;
  int m; cin >> m;
  vector<int> l(m , 0);
  forn(i , 0 , n){
    int x; cin >> x;
    forn(j , 0 , x){
      int z; cin >> z; z--;
      l[z]++;
    }  
  } 
  ll k = 0;
  forn(i , 0 , m) if(l[i] == n) k++;
  cout << k << endl; 
  
   
#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    string s,t;
    cin >> s >> t;
    ll n=s.length(),m=t.length();
    ll ans=INT_MAX;
    for(int i=0;i<n-m+1;i++){
        ll tc=0;
        for(int j=0;j<m;j++){
            if(t[j]!=s[i+j]){
                tc++;
            }
        }
        ans=min(ans,tc);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3628
#[allow(unused_imports)]
use std::collections::HashSet;
#[allow(unused_imports)]
use std::cmp::max;
#[allow(unused_imports)]
use std::cmp::min;

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let hw = read_vec::<usize>();
    let h = hw[0];
    let w = hw[1];
    let mut masu:Vec<Vec<char>> = Vec::with_capacity(h);
    for _i in 0..h {
        let row = read::<String>().chars().collect::<Vec<char>>();
        masu.push(row);
    }


    let answer = solve(h, w, &masu);
    println!("{}", answer);
}

fn solve(h: usize, w:usize, masu: &Vec<Vec<char>>) -> usize {
    let mut max_val : usize = 0;
    // dp[i][j]: masu[i][j]にランプをおいた場合に照らすマスの数。
    //           masu[i][j]の場合は[0, 0]
    //           そうでなければ[<縦で照らすマス>, <横で照らすマス>]、但し自身のマスは含まない。
    let mut dp = vec![vec![vec![0; 2]; w]; 2];

    for i in 0..h {
        let i_dp = i % 2;
        for j in 0..w {
            if masu[i][j] == '#' {
                dp[i_dp][j][0] = 0; 
                dp[i_dp][j][1] = 0; 
            } else {
                // 縦
                if i == 0 || masu[i-1][j]=='#' {
                    let mut i1 = i+1;
                    while i1<h && masu[i1][j] != '#' {
                        i1 += 1;
                    }
                    dp[i_dp][j][0] = i1 - i - 1;
                }  else {
                    dp[i_dp][j][0] = dp[(i-1) % 2][j][0];
                }

                // 横
                if j == 0 || masu[i][j-1] == '#' {
                    let mut j1 = j + 1;
                    while j1 < w && masu[i][j1] != '#' {
                        j1 += 1;
                    }
                    dp[i_dp][j][1] = j1 - j - 1;
                } else {
                    dp[i_dp][j][1] = dp[i_dp][j-1][1];
                }
                
                let val = dp[i_dp][j][0] + dp[i_dp][j][1] + 1;
                max_val = max(max_val, val);
            }
            //println!("{}, {} -> {}, {}",i, j, dp[i][j][0], dp[i][j][1] );
        }
    }
    
    
    return max_val;
}

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

using namespace std;

#define ll long long




void solve() {

	int a, b, c;
	cin >> a >> b >> c;
	cout << max(0, c - a + b);
	




	
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	solve();

	return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



int main()
{	
	int n, x;

	while (true)
	{
		cin >> n >> x;
		if (n == 0 && x == 0) break;

		int ans = 0;

		for (int i = 1; i <= n-2; i++)
		{
			for (int j = i+1; j <= n-1; j++)
			{
				int k = x - i - j;
				if (k > j && k <= n) ans++;
			}
		}

		cout << ans << endl;
	}

	return 0;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m,c,count=0;
  cin >> n >> m >> c;
  int b[m],a[n][m];
  for(int i=0;i<m;i++)cin >>b[i];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)cin >>a[i][j];
  }
  for(int i=0;i<n;i++){
    int ans=0;
    for(int j=0;j<m;j++){
      ans+=a[i][j]*b[j];
    }
    ans+=c;
    if(ans>0)count++;
  }
  cout << count <<endl;
}

Measured memory_bytes: 256
import heapq
N = int(input())
*a, = map(int, input().split())

l, r = [], []
for i in range(N):
    heapq.heappush(l, a[i])
    heapq.heappush(r, -a[3*N-i-1])

lsum, rsum = [sum(l)], [sum(r)]
for i in range(N):
    heapq.heappush(l, a[i+N])
    lsum.append(lsum[-1] + a[i+N] - heapq.heappop(l))
    heapq.heappush(r, -a[3*N-i-N-1])
    rsum.append(rsum[-1] - a[3*N-i-N-1] - heapq.heappop(r))

ans = -float('inf')
for i in range(N+1):
    t = lsum[i]+rsum[N-i]
    if ans < t:
        ans = t
print(ans)


Measured memory_bytes: 123680
//g++  5.4.0

#include<bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define int long long
#define ld long double
#define pb push_back
#define pii pair< int,int >
#define fast ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;



signed main()
{
    fast;
    int n,k;
    cin >> n >> k;
    vector<int> a(n) , dp(k+1,0);
    for(int i=0 ; i<n ; i++ ) cin >> a[i];
    
    for(int i=0 ; i<=k ; i++ )
    {
        if( dp[i] ) continue;
        for( auto j : a )
        {
            if( j+i > k ) break;
            dp[ j+i ] = 1;
        }
    }
    if( dp[ k ] ) cout << "First\n";
    else          cout << "Second\n";
}





Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int W, H, N;
  cin >> W >> H >> N;
  vector<int> Waxis(W+1,0);
  vector<int> Haxis(H+1,0);
  vector<vector<int>> grid(N, vector<int>(3,0));
  
  for (int i =0; i< N ; i++){
    for (int j=0 ; j < 3; j++){
      cin >> grid.at(i).at(j);
    }
  }
/*imptest
  cout << W << " " << H << " " << N << endl;
  for (int i =0; i< N ; i++){
    for (int j=0; j < 3; j++){
      cout << grid.at(i).at(j)<< " ";
    }
    cout << endl;
  }
*/ 
  for (int i=0; i< N; i++){
    if(grid.at(i).at(2) == 1){//xより小さいところを塗る
      for (int j = 0; j < grid.at(i).at(0) ;j++){
        Waxis.at(j)++;
      }
    }
    else if(grid.at(i).at(2) == 2){//xより大きいところ
      for (int j = grid.at(i).at(0)+1 ; j<W+1 ;j++){
        Waxis.at(j)++;
      }
    }
    else if(grid.at(i).at(2) == 3){//yより小さいところ
      for (int j = 0; j < grid.at(i).at(1) ;j++) {
        Haxis.at(j)++;
      }
    }
    else if(grid.at(i).at(2) == 4){
      for (int j = grid.at(i).at(1)+1 ; j<H+1 ;j++){
        Haxis.at(j)++;
      }
    }
  }

    int Hcount =0;
    int Wcount =0;
    for (int i =0; i< W+1; i++){
//      cout << Waxis.at(i) << " ";
      if(Waxis.at(i)==0) Wcount++;
    }
//    cout << endl;
    for (int i =0; i< H+1; i++){
//      cout << Haxis.at(i) << " ";
      if(Haxis.at(i)==0) Hcount++;
    }
//    cout << endl;
    if(Wcount ==0 || Hcount == 0) cout << 0 << endl;
    else cout << (Wcount-1) * (Hcount-1) << endl;

}
//  cout << Waxis.at(5) << endl;


Measured memory_bytes: 3608
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

	vector<int> p(n), v(n);
	rep(i, n*(n-1)/2) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;

		int e = 0, f = 0;
		if(c == d) {
			e = 1;
			f = 1;
		} else if(c > d) {
			e = 3;
		} else {
			f = 3;
		}

		p[a-1] += e;
		p[b-1] += f;
		v[a-1] += e;
		v[b-1] += f;
	}

	sort(v.begin(), v.end(), greater<int>());

	rep(i, n) {
		rep(j, v.size()) {
			if(p[i] != v[j]) continue;
			cout << j + 1 << endl;
			break;
		}
	}

	return 0;
}

Measured memory_bytes: 1216
//package kadai3;
import java.util.*;
public class Main {
	public boolean overlap(int[][] table, int h, int v) { //????±????????????????????????????????????????????????????
		for(int i = 0; i < table.length; i++) {
			if(table[h][v] == table[i][v] && i != h) return false;
		}
		return true;
	}
	void doIt() {
		Scanner sc = new Scanner(System.in);
		Main check = new Main();
		int N = sc.nextInt();
		int[] point = new int[N];
		int[][] num = new int[N][3]; 
		for(int i = 0; i < N; i++) {
			num[i][0] = sc.nextInt();
			num[i][1] = sc.nextInt(); 
			num[i][2] = sc.nextInt();
		}
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < N; j++) {
				if(check.overlap(num, j, i)) point[j] += num[j][i];
			}
		}
		for(int i = 0; i < N; i++) System.out.println(point[i]);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		new Main().doIt();
	}

}

Measured memory_bytes: 20800
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1)
#define IOS ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll mininf = -922337203685477;
const ll nax = 0;
int n, arr[55], ans=0;

int main(){
	IOS
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> arr[i];
		if(arr[i]!=i) ans++;
	}
	if(ans>2) cout << "NO" << '\n';
	else cout << "YES" << '\n';
}


Measured memory_bytes: 3620
cnt_st0 = 0
cnt_st1 = 0
in_str = str(input())
for i, m in enumerate(in_str):
  if i % 2 == 0:
    if str(m) == '0':
      cnt_st1 += 1
    else:
      cnt_st0 += 1
  else:
    if str(m) == '0':
      cnt_st0 += 1
    else:
      cnt_st1 += 1
print(min(cnt_st0, cnt_st1))

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

int main()
{
    int a, b;
    cin >> a >> b;
    if (a < b)
    {
        rep(i, b) cout << a;
    }
    else
    {
        rep(i, a) cout << b;
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

		while(true){
			int from = sc.nextInt();
			int to = sc.nextInt();
			if(from == 0 && to == 0) break;

			if(first) first = false;
			else System.out.println();

			boolean flg = true;
			for(int i=from;i<=to;i++){
				if(isLeap(i)){
					flg = false;
					System.out.println(i);
				}
			}

			if(flg) System.out.println("NA");
		}
	}

	private static boolean isLeap(int y){
		if(y % 4 == 0){
			if(y % 100 == 0){
				if(y % 400 == 0) return true;
				return false;
			}
			return true;
		}
		return false;
	}
}

Measured memory_bytes: 12000
A = int(input().rstrip())
B = int(input().rstrip())
C = int(input().rstrip())
X = int(input().rstrip())
count = 0

for a_500 in range(A+1):
    for b_100 in range(B+1):
        for c_050 in range(C+1):
            value = (500 * a_500) + (100 * b_100) + (50 * c_050)
            if value == X:
                count += 1

print(count)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define bug1(x) cout<<#x<<" = "<<x<<endl
#define bug2(x,y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define bug3(x,y,z) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
#define bug4(x,y,z,m) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<" "<<#m<<" = "<<m<<endl

using namespace std;

class Debugger {
public:
	template<typename T>
	void printVector(vector<T> const &vec, bool printSize=true){
		if(printSize){
			cout << vec.size() << endl;
		}
		for(auto &elem : vec){
			cout << elem << " ";
		}
		cout << endl;
	}

	template<typename T>
	void printMatrix(vector<vector<T>> const &matrix){
		cout << matrix.size()<< " ";
		if(!matrix.empty()){
			cout << matrix[0].size();
		}
		cout << endl; 
		for(auto &vec : matrix){
			printVector(vec, false);
		}
		cout << endl;
	}
};

const int maxN = 100005;

class TaskD {
private:
	Debugger debugger;
	long long k;
	int ans = -1;
	vector<int> to;
	vector<bool> vis;

	void dfs(int u, vector<int> &curr){
		if(k == 0){
			if(ans == -1){
				ans = u;	
			}
			return;
		}
		if(vis[u]){
			vector<int> cycle;
			while(curr.back() != u){
				cycle.push_back(curr.back());
				curr.pop_back();
			}
			cycle.push_back(u);
			reverse(cycle.begin(), cycle.end());
			if(ans == -1){
				ans = cycle[k % cycle.size()];
			}
			return;
		}
		vis[u] = true;
		curr.push_back(u);
		k--;
		dfs(to[u], curr);
	}

public:
	void solveOne(int it){
		int n;
		cin >> n >> k;
		to.assign(n, 0);
		for(int i = 0; i < n; i++){
			cin >> to[i];
			to[i]--;
		}
		vis.assign(n, false);
		vector<int> ret;
		dfs(0, ret);
		cout << ans + 1 << endl;
	}

	void solve(){
		int tc = 1;
		for(int it = 1; it <= tc; it++){
			solveOne(it);
		}
	}
};


int main(){
	ios_base::sync_with_stdio(false);
	TaskD solver;
	solver.solve();
	return 0;
}


Measured memory_bytes: 17224
def main():
    N = int(input())
    A = list(map(int, input().split()))
    pos = []
    neg = []
    for i in range(N):
        if A[i] < 0:
            neg.append(A[i])
        else:
            pos.append(A[i])
    pos.sort()
    neg.sort(reverse=True)
    ans = sum(map(abs, A))
    if len(pos) == N:
        x = pos.pop(0)
        ans -= x * 2
        neg.append(x)
    elif len(neg) == N:
        x = neg.pop(0)
        ans += x * 2
        pos.append(x)
    print(ans)
    n = 1
    p = 1
    x = pos[0]
    y = neg[0]
    while p < len(pos):
        print(y, pos[p])
        y -= pos[p]
        p += 1
    while n < len(neg):
        print(x, neg[n])
        x -= neg[n]
        n += 1
    print(x, y)


if __name__ == "__main__":
    main()


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

int main(){
  int n;
  cin >> n;
  int c = 0;
  int m = n;
  while(n >= 1){
    c += n % 10;
    n /= 10;
  }
  //cout << n << " " << c << endl;

  if(m % c == 0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
from copy import copy


def bubble_sort(org_A):
    A = copy(org_A)
    for i in range(len(A)):
        for j in range(len(A) - 1, i, -1):
            if int(A[j][1]) < int(A[j - 1][1]):
                A[j], A[j - 1] = A[j - 1], A[j]
    return A


def selection_sort(org_A):
    A = copy(org_A)
    n = len(A)
    for i in range(n):
        mini = i
        for j in range(i, n):
            if int(A[j][1]) < int(A[mini][1]):
                mini = j
        if mini != i:
            A[i], A[mini] = A[mini], A[i]
    return A

n = int(input())
A = input().split()
B = bubble_sort(A)
C = selection_sort(A)
print(' '.join(B))
print('Stable')
print(' '.join(C))
if B == C:
    print('Stable')
else:
    print('Not stable')



Measured memory_bytes: 6344
#include <bits/stdc++.h>
using namespace std;
int h1,m1,h2,m2,t1,t2,l;
int ans=0;
int main(){
	cin>>h1>>m1>>h2>>m2>>l;
	t1=h1*60+m1,t2=h2*60+m2;
	for(ans=t1;ans<=t2-l;ans++);
	cout<<ans-t1-1<<'\n';
	return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <cctype>
#include <functional>
#include <vector>
#include <cstdlib>
using namespace std;

typedef pair<int,int> pii;

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

int main(){
	int INF = (int)1e9;

	vector<vector<char> > field(108, vector<char>(108, '#') );
	vector<vector<int> > tm(108, vector<int>(108, 1) );

	int w, h;
	scanf("%d%d", &w, &h);
	for(int i = 3; i < h + 3; ++i){
		scanf(" %s", &field[i][3]);
		field[i][w + 3] = '#';
	}

	vector<pii> roll(2);

	queue<pii> q;
	for(int i = 3; i < h + 3; ++i){
		for(int j = 3; j < w + 3; ++j){
			switch( field[i][j] ){
				case '#':
					for(int y = i - 2; y <= i + 2; ++y)
					for(int x = j - 2; x <= j + 2; ++x){
						int t = 4 - max(abs(y - i), abs(x - j));
						tm[y][x] = max(tm[y][x], t);
					}
					break;
				case 'S':
					roll[1] = pii(i, j);
					field[i][j] = '1';
					break;
				case 'G':
					roll[0] = pii(i, j);
					field[i][j] = '0';
					break;
				case 'M':
					field[i][j] = '0' + roll.size();
					roll.push_back( pii(i, j) );
					break;
			}
		}
	}

	
	int n = roll.size();
	vector<vector<int> > dist(n, vector<int>(n, INF) );
	
	for(int i = 1; i < n; ++i){
		vector<vector<int> > d(108, vector<int>(108, INF) );
		d[roll[i].first][roll[i].second] = 0;
		
		priority_queue<pii,vector<pii>,greater<pii> > pq;
		pq.push( pii(0, roll[i].first * 1000 + roll[i].second) );
		
		while( !pq.empty() ){
			pii p = pq.top();
			pq.pop();

			int y = p.second / 1000;
			int x = p.second % 1000;

			if( d[y][x] != p.first ) continue;

			if( isdigit( field[y][x] ) ){
				dist[i][field[y][x] - '0'] = p.first;
			}

			int c = p.first + tm[y][x];

			for(int j = 0; j < 4; ++j){
				int ny = y + dy[j];
				int nx = x + dx[j];
				
				if( field[ny][nx] != '#' && d[ny][nx] > c ){
					d[ny][nx] = c;
					pq.push( pii(c, ny * 1000 + nx) );
				}
			}

		}
	}

	int last = 1 << n;
	vector<vector<int> > dp(n, vector<int>(last, INF) );
	dp[1][2] = 0;

	for(int S = 0; S < last; ++S){
		for(int i = 0; i < n; ++i){
			if( S & 1 << i ){
				for(int j = 0; j < n; ++j){
					if( !(S & 1 << j) ){
						int next = S | 1 << j;
						dp[j][next] = min(dp[j][next], dp[i][S] + dist[i][j]);
					}
				}
			}
		}
	}
	
	printf("%d\n", dp[0].back());
}

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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int>a(n);
  for(int i = 0;i < n;i++) cin >> a[i];
  int left,right;
  for(int i = 0;i < n;i++){
    if(a[i]==1){
      left=i;
      right=n-1-left;
    }
  }
  int ans=0;
  ans+=(left+k-2)/(k-1);
  right-=ans*(k-1)-left;
  if(right>0);
  ans+=(right+k-2)/(k-1);
  
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

int main(){
    //方針
    //毎日満足度は低下し続ける
    //満足度上昇の方法はコンテスト開催のみ
    //開催されてないコンテストを放置すると低下が著しくなる
    //実際にコンテストを開いた時の満足度上昇が最大のものを採用してみる
    //低下をなくせる分を上昇と捉えると、c_i(d-last(d,i)) + s_{d,i} だけペイすると考えられる？→あんまり適当じゃない
    //r日ずつ全探索を[D/r+1]回繰り返す
    //探索パターン数は26^rで、シミュレーションには26r回かかる、これを[D/r+1]回繰り返すので
    //計算量はO(D26^{r+1})
    //r = 3が限界
    int D;cin>>D;
    int c[26],last[26]={},s[365][26],lastcpy[26];
    REP(i,26) cin>>c[i];
    REP(i,D) REP(j,26) cin>>s[i][j];
    constexpr int r = 3;
    int up,ptncpy;
    int res[r],calcres[r],reslast[26];
    for(int i=0;i<D;i+=r){
        int tmp = -1e9;
        for(int pattern = 0; pattern < 26*26*26; pattern++){
            up = 0; ptncpy = pattern;
            memcpy(lastcpy,last,sizeof(int)*26);
            REP(j,r){
                if(i+j>=D) break;
                calcres[j] = ptncpy%26;
                REP(k,26){
                    if(calcres[j] == k){
                        last[k] = i+j;
                        up += s[i+j][k];
                    }
                    else up -= c[i+j]*(i+j - last[k]);
                }
                ptncpy /= 26;
            }
            
            if(tmp<up){
                tmp = up;
                memcpy(res, calcres, sizeof(int)*r);
                memcpy(reslast, last, sizeof(int)*26);
            }
            memcpy(last, lastcpy, sizeof(int)*26);
        }
        memcpy(last, reslast, sizeof(int)*26);
        REP(j,r) if(i+j<D){
            cout<<res[j]+1<<endl;
        }
    }
}


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

int calc(int x) {
    int y = 0;
    while (x) y += x % 10, x /= 10;
    return y;
}

int main() {
    int n, ans = 1e9;
    cin >> n;
    for (int i = 1; i < n; i++) ans = min(ans, calc(i) + calc(n - i));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n;
	std::cin >> n;
	std::vector<int> x(n);
	rep(i,n) std::cin >> x[i];
	int min = 1e9;
	for(int i=1;i<=100;i++) {
		int sum = 0;
		rep(j,n) sum+=(x[j]-i)*(x[j]-i);
		min = std::min(min, sum);
		debug(i,min);
	}
	print(min);

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define f(i,a,b) for(int i = a; i < b; i++)
#define MAX 1000000010
using namespace std;
typedef long long int ll;
int dp[110][100010],v[110],w[110];
int main(){
	int n,x,ans=0;
	cin>>n>>x;
	f(i,0,n) cin>>w[i+1]>>v[i+1];
	f(i,0,n+1)
		f(j,1,100010) dp[i][j]=MAX;
	f(i,1,n+1){
		f(j,1,100010){
			if(j>=v[i]) dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	f(i,0,100010) if(dp[n][i]<=x) ans=i;
	cout<<ans; 
}

Measured memory_bytes: 41216
N = int(input())
B = [[[0 for k in range(10)] for j in range(3)] for i in range(4)]
for i in range(N):
    b,f,r,v = map(int,input().split())
    B[b-1][f-1][r-1] += v
for i in range(4):
    for j in range(3):
        for k in range(10):
            print(' {}'.format(B[i][j][k]),end='')
        print()
    if i != 3:
        print('####################' )



Measured memory_bytes: 5624
in_=int(input())
size=10001
l=[[] for i in range(size)]
for i in range(in_):
  num=int(input())
  r=num%size
  if num in l[r]:
    l[r].remove(num)
  else:
    l[r].append(num)
sum=0
for li in l:
  sum=sum+len(li)
print(sum)
  
  
  

Measured memory_bytes: 8176
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char s;
	int a;
	for(int i=0;i<4;i++)
	{
		cin>>s;
		if(s=='+')
		    a+=1;
		if(s=='-')
		    a-=1;
	}
	cout<<a;
}

Measured memory_bytes: 256
{-# LANGUAGE FlexibleContexts #-}

import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import Control.Monad.ST
import qualified Control.Monad.State as State
import Control.Monad
import Control.Applicative
import qualified Data.Set as Set
import qualified Debug.Trace as DT
import qualified Data.Maybe as MB
import qualified Data.List as L

import qualified Data.ByteString.Char8 as BS



data Edge a = Edge {edgeFrom :: Int, edgeTo :: Int, edgeDist :: a} deriving Show
newtype Graph a = Graph (V.Vector [Edge a]) deriving Show

emptyGraph :: Int -> Graph a
emptyGraph n = Graph (V.replicate n [])

constructGraph :: Int -> [Edge a] -> Graph a
constructGraph n edges = runST $ do
  g <- V.thaw $ (\(Graph b) -> b) (emptyGraph n)
  forM edges $ \e@(Edge s t d) -> do
    VM.modify g (e:) s
  return . Graph =<< V.freeze g

dijkstra :: Integral a => Graph a -> Int -> (V.Vector (Maybe a))
dijkstra (Graph graph) src = runST $ do
  ret <- VM.replicate n Nothing
  check <- VM.replicate n False

  let
    loop = do
      isNull <- Set.null <$> State.get

      when (not isNull) $ do
        (dist,cur) <- State.state Set.deleteFindMin

        checked <- State.lift $ VM.read check cur
        State.lift $ VM.write check cur True

        when (not checked) $ do

          forM_ (graph V.! cur) $ \(Edge _ next d) -> do
            a <- State.lift $ VM.read ret next

            if a == Nothing then do
              State.lift $ VM.write ret next (Just $ dist+d)
              State.modify $ Set.insert (dist+d, next)
              
              else do
              let (Just dist') = a

              when (dist + d < dist') $ do
                State.lift $ VM.write ret next (Just $ dist+d)

                (State.lift $ VM.read check next) >>= \b -> do
                  when (not b) $ do
                    State.modify $ Set.insert (dist+d, next)
        loop
      
  VM.write ret src (Just 0)
  State.runStateT loop (Set.singleton (0,src))
  V.freeze ret
  
  where
    n = V.length graph



readInts = map (fst . MB.fromJust . BS.readInt) . BS.words <$> BS.getLine
  
main :: IO ()
main = do
  [n,m] <- readInts :: IO [Int]

  edges <- concat <$> do
    replicateM m $ do
      [u,v] <- readInts :: IO [Int]
      return $ [(Edge (u-1) ((v-1)+n) 1), (Edge ((u-1)+n) ((v-1)+2*n) 1), (Edge ((u-1)+2*n) (v-1) 1)]

  [s,t] <- readInts :: IO [Int]

  let
    g = constructGraph (3*n) edges
    dist = dijkstra g (s-1)

  let ans = dist V.! (t-1)

  print $
    case ans of
      Nothing -> -1
      Just x -> x`div`3  

  return ()


Measured memory_bytes: 148860
<?php
//error_reporting(0);
//$N = trim(fgets(STDIN));
list($N,$R) = explode(" ",trim(fgets(STDIN)));
//$A = array_map('intval',explode(" ",trim(fgets(STDIN))));
//function chmax(&$a,$b) {if ($a<$b){$a=$b;return true;}return false;}
//function chmix(&$a,$b) {if ($a>$b){$a=$b;return true;}return false;}


if ($N < 10) {
  printf("%d\n",$R+100*(10-$N));
}
else {
  printf("%d\n",$R);
}


Measured memory_bytes: 4856
#include <iostream>
#include <cmath>

int main(){
    unsigned long long n;
    std::cin>>n;
    unsigned long long sqrt=(unsigned long long)std::sqrt((double)n)+1;
    unsigned long long ans=1000000000000;
    for(unsigned long long i=1;i<=sqrt;++i){
        if(n%i==0){
            unsigned long long a=i+n/i-2;
            if(ans>a){
                ans=a;
            }
        }
    }
    std::cout<<ans;
    return 0;
}

Measured memory_bytes: 256
//I Guds namn
#include <cmath>
#include <iostream>

using namespace std;

typedef long long ll;

const ll MAXN = 100 * 1000 + 13, MOD = 1000 * 1000 * 1000 + 7;

ll fact[MAXN];

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	ll n, m; cin >> n >> m;
	if(abs(n - m) > 1)
	{
		cout << 0 << endl;
		return 0;
	}
	fact[1] = 1;
	for(ll i = 2;i < MAXN;i++)
		fact[i] = (i * fact[i - 1]) % MOD;
	ll ans = (fact[n] * fact[m]) % MOD;
	if(m == n)
		ans *= 2;
	ans %= MOD;
	cout << ans << endl;
	return 0;
}

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

int main(){
    int a,b;cin>>a>>b;
    string Int;
    if(a<=b){
        for(int i=0;i<b;i++){
            Int.append(to_string(a));
        }
    }
    else{
        for(int i=0;i<a;i++){
            Int.append(to_string(b));
        }
    }
    cout<<Int<<endl;
}


Measured memory_bytes: 256
fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let n: usize = s.trim().parse().ok().unwrap();

    s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let a: Vec<usize> = s
        .trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect();

    let mut cnt: Vec<u64> = vec![0; n + 1];
    let mut ans: u64 = 1;
    let modulo: u64 = 1000000007;

    cnt[0] = 3;
    for i in 0..n {
        ans = ans * cnt[a[i]] % modulo;
        cnt[a[i] + 1] += 1;
        cnt[a[i]] -= 1;
    }
    println!("{}", ans);
}

Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
typedef long long l;
int main()
{
	l x;
	cin>>x;
	for(l a=-1000;a<1000;a++)
	{
		for(l b=-1000;b<1000;b++)
		{
			if((a*a*a*a*a)-(b*b*b*b*b)==x)
			{
				cout<<a<<" "<<b<<endl;
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3544
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = (a);i<=(b);i++)
#define ROF(i,a,b) for(int i = (a);i>=(b);i--)
#define MST(a,x) memset(a,x,sizeof(a))
#define ll long long
#define PB push_back
#define PH push
#define MP make_pair
#define FT first
#define SD second
#define N 100005
#define M 51
#define INF 500
#define MOD 924844033
#define MOD2 1000000009
#define eps 1e-7
using namespace std;
inline int Max(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^b;
}
inline int Min(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^a;
}


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    int n;
    while(cin>>n)
    {
        a = b = 1;

        FOR(i,1,n)
        {
            ll aa,bb;
            cin>>aa>>bb;
            ll c = max(a/aa,b/bb);
            if(aa*c<a||bb*c<b)c++;
            a = c*aa;
            b = c*bb;
        }
        cout<<a+b<<endl;

    }
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define inf LLONG_MAX>>2
#define MAX 1000000
#define mod 1000000007
#define pb push_back
#define f(i,a,n,x) for ((i)=(a);(i)<(n);(i)+=(x))
#define fd(i,a,n,x) for ((i)=(a);(i)>=(n);(i)-=(x))
#define fi first
#define se second
#define mk make_pair
#define pi pair
#define vt vector
#define ms multiset
using namespace std;
void read(vt<ll> &a,ll n){ll i,temp;f(i,0,n,1){cin>>temp;a.pb(temp);}}
ll fa[MAX];
ll power(ll p,ll q){
    ll res=1;
    p%=mod;
    while(q){
        if (q&1)
            res=(res*p)%mod;
        q>>=1;
        p=(p*p)%mod;
    }
    return res;
}
ll fact(ll n){
    if (n<=1)
        return fa[n]=1;
    if (fa[n])
        return fa[n];
    return fa[n]=(n*fact(n-1))%mod;
}
ll ncr(ll n,ll r){
    if (!r)
        return 1;
    return (((fact(n)*power(fact(n-r),mod-2))%mod)*power(fact(r),mod-2))%mod;
}
void solve(){
    ll n;
    cin>>n;
    if (n>=30)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 3640
from itertools import product

n = int(input())
a = []
xy = []

for _ in range(n):
    ea = int(input())
    new = []
    for _ in range(ea):
        x, y = map(int, input().split())
        x -= 1
        new.append([x, y])

    xy.append(new)

ans = 0
for pat in product([1, 0], repeat=n):
    bl = True
    for i, e in enumerate(pat):
        if e:
            for x, y in xy[i]:
                if pat[x] != y:
                    bl = False

    if bl:
        ans = max(ans, sum(pat))

print(ans)


Measured memory_bytes: 3064
button = [
  [".", ",", "!", "?", " "],
  ["a", "b", "c"],
  ["d", "e", "f"],
  ["g", "h", "i"],
  ["j", "k", "l"],
  ["m", "n", "o"],
  ["p", "q", "r", "s"],
  ["t", "u", "v"],
  ["w", "x", "y", "z"]]

n = int(raw_input())
for _ in xrange(n):
  s = raw_input()
  inbut = 0
  count = 0
  output = ""
  for i in xrange(len(s)):
    if s[i] == "0":
      if inbut == 0: continue
      output += button[inbut-1][(count-1) % len(button[inbut-1])]
      inbut = 0
      count = 0
    else:
      inbut = int(s[i])
      count += 1
  print output

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

int main() {
  long N, x = 0, a = 0, b = 0, flag = 0;
  string ans = "YES";
  cin >> N;
  
  for (int i = 1; i <= N; i++) {
    cin >> x;
    if (i != x && flag == 2) break;
    if (i != x && flag == 1) {
      if (x == a && i == b) ans = "YES";
      flag = 2;
    }
        if (i != x && flag == 0) {
      a = i;
      b = x;
      flag = 1;
      ans = "NO";
    }
  }
  
  cout << ans << endl;
}


Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
using namespace std;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }

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

ll lcm(ll a, ll b){
  return a * b / gcd(a,b);
}

int main() {
    int n; cin >> n;
    vint a(n);
    rep(i, n) cin >> a[i];
    sort(all(a)); reverse(all(a));
    ll l = lcm(a[0], a[1]);
    FOR(i, 2, n) {
        // dump(l);
        l = lcm(l, a[i]);
    }
    dump(l);
    ll ans = 0;
    // rep(i, n) ans += ((l - 1) % a[i]);
    rep(i, n) ans += a[i] - 1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
object Main extends App {

  val n = scala.io.StdIn.readInt()


  def solve() =  {
    val list: Seq[Double] = (1 to 9).map(_.toDouble)
    val divisions = (1 to 9).map { num => n.toDouble / num }
    val isKuKu = divisions.exists(list.contains)
    if(isKuKu) "Yes" else "No"
  }

  println(solve)

}


Measured memory_bytes: 27456
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define mset(s, _) memset(s, _, sizeof s)
#define ALL(a) (a).begin(), (a).end()
using namespace std;

int main(void) {
  string s, t;
  cin >> s >> t;

  int n, m;
  n = s.length();
  m = t.length();

  int dp[n + 1][m + 1];
  rep(i, 0, n) {
    rep(j, 0, m) { dp[i][j] = 0; }
  }

  rep(i, 1, n) {
    rep(j, 1, m) {
      if (s[i - 1] == t[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
      }
    }
  }

  string ans = "";
  int x = n;
  int y = m;
  while (x > 0 && y > 0) {
    if (dp[x][y] == dp[x - 1][y]) {
      x--;
    } else if (dp[x][y] == dp[x][y - 1]) {
      y--;
    } else {
      x--;
      y--;
      ans.push_back(s[x]);
    }
  }

  reverse(ALL(ans));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 35456
package main

import "fmt"

func getMin(nums []int) (min int) {
	min = nums[0]
	for i := 0; i < len(nums); i++ {
		if nums[i] < min {
			min = nums[i]
		}
	}
	return
}

func main() {
	var N, T int
	fmt.Scan(&N, &T)
	var c []int
	for i := 0; i < N; i++ {
		var ci, ti int
		fmt.Scan(&ci, &ti)
		if ti <= T {
			c = append(c, ci)
		}
	}
	if len(c) == 0 {
		fmt.Println("TLE")
	} else {
		fmt.Println(getMin(c))
	}
}


Measured memory_bytes: 512
#関数リスト
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n = I()
mylist = LI()
mylist.sort(reverse=True)

result = mylist[0]

if n % 2==0:
    for i in range(1,n//2):
        result += mylist[i]*2
    print(result)
else:
    for i in range(1,n//2):
        result += mylist[i]*2
    temp = (n-1)//2
    result += mylist[temp]
    print(result)

Measured memory_bytes: 91932
/**
 *    author:  tourist
 *    created: 19.12.2019 15:42:22       
**/
#include <bits/stdc++.h>

using namespace std;

class matching {
 public:
  vector<vector<int>> g;
  vector<int> pa;
  vector<int> pb;
  vector<int> was;
  int n, m;
  int res;
  int iter;

  matching(int _n, int _m) : n(_n), m(_m) {
    assert(0 <= n && 0 <= m);
    pa = vector<int>(n, -1);
    pb = vector<int>(m, -1);
    was = vector<int>(n, 0);
    g.resize(n);
    res = 0;
    iter = 0;
  }

  void add(int from, int to) {
    assert(0 <= from && from < n && 0 <= to && to < m);
    g[from].push_back(to);
  }

  bool dfs(int v) {
    was[v] = iter;
    for (int u : g[v]) {
      if (pb[u] == -1) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    for (int u : g[v]) {
      if (was[pb[u]] != iter && dfs(pb[u])) {
        pa[v] = u;
        pb[u] = v;
        return true;
      }
    }
    return false;
  }

  int solve() {
    while (true) {
      iter++;
      int add = 0;
      for (int i = 0; i < n; i++) {
        if (pa[i] == -1 && dfs(i)) {
          add++;
        }
      }
      if (add == 0) {
        break;
      }
      res += add;
    }
    return res;
  }

  int run_one(int v) {
    if (pa[v] != -1) {
      return 0;
    }
    iter++;
    return (int) dfs(v);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  matching mat(n - 1, n);
  vector<vector<int>> gr(n);
  for (int i = 0; i < n - 1; i++) {
    int foo;
    cin >> foo;
    while (foo--) {
      int bar;
      cin >> bar;
      --bar;
      mat.add(i, bar);
      gr[bar].push_back(i);
    }
  }
  if (mat.solve() != n - 1) {
    cout << -1 << '\n';
    return 0;
  }
  int start = -1;
  for (int i = 0; i < n; i++) {
    if (mat.pb[i] == -1) {
      start = i;
      break;
    }
  }
  vector<pair<int, int>> res(n - 1);
  vector<bool> was(n, false);
  vector<int> que(1, start);
  was[start] = true;
  for (int b = 0; b < (int) que.size(); b++) {
    int x = que[b];
    for (int v : gr[x]) {
      int y = mat.pa[v];
      if (!was[y]) {
        was[y] = true;
        que.push_back(y);
        res[v] = make_pair(y, x);
      }
    }
  }
  if ((int) que.size() != n) {
    cout << -1 << '\n';
    return 0;
  }
  for (int i = 0; i < n - 1; i++) {
    cout << res[i].first + 1 << " " << res[i].second + 1 << '\n';
  }
  return 0;
}


Measured memory_bytes: 15096
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode
import sys
sys.setrecursionlimit(10 ** 6)

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

def RI():
    return list(map(int,input().split()))

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

n,k = MI()
a = RI()

for i in range(n):
    ddict[ a[i] ] += 1

d = sorted( ddict.items(), key=lambda x:x[1], reverse=True )
# print(d)

e = d[k:]
c = 0
for i in range(len(e)):
    c += e[i][1]
print(c)

Measured memory_bytes: 133124
#include <stdio.h>

long long abs(long long A);
int main(void)
{
    long long X,K,D,q,r,ans=0;
    scanf("%lld %lld %lld",&X,&K,&D);
    X=abs(X);
    D=abs(D);
    q=X/D;
    r=X%D;

    if(K<=q){
        ans=X-K*D;
        // printf("A");
    } else {
        if((K-q)%2==0){
            ans=r;
            // printf("B");
        } else {
            ans=abs(D-r);
            // printf("C");
        }
    }
    printf("%lld",ans);
    return 0;
}

long long abs(long long A)
{
    if(A<0) A=(-1)*A;
    return A;
}


Measured memory_bytes: 1736
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
// ============ template finished ============

int main()
{
    ll K;
    cin >> K;

    ll num = 0;
    rep(i, K) {
        (num *= 10) %= K;
        (num += 7) %= K;
        if (num == 0) {
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 3592
import java.awt.print.Printable;
import java.util.Scanner;
import javax.sound.midi.SysexMessage;
  
public class Main{      
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        while(true){
            int x = sc.nextInt();
            int y = sc.nextInt();
        
            if(x==0&&y==0)
                break;

            for (int i = 0;i<x;i++) 
            {
                for (int j = 0;j<y;j++)
                {
                    if(i%2==0){
                        if(j%2==0)
                            System.out.print("#");
                        else
                            System.out.print(".");
                    }
                    else
                    {
                        if(j%2==0)
                            System.out.print(".");
                        else
                            System.out.print("#"); 
                    }
                }
                System.out.println();
            }
            System.out.println();
        }
        sc.close();
        
    }   
}


Measured memory_bytes: 35040
#include<stdio.h>
#include<queue>
using namespace std;
vector<int> g[100001];
int len[2][100001]; 
void bfs(int p,int now)
{
	len[p][now]=1;
	int i,j;
	queue<int> q;
	q.push(now);
	while(!q.empty())
	{
		i=q.front();
		q.pop();
		for(j=0;j<g[i].size();++j)
			if(!len[p][g[i][j]])
				len[p][g[i][j]]=len[p][i]+1,q.push(g[i][j]);
	}
}
int main()
{
	int n,s,e,i;
	scanf("%d",&n);
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&s,&e);
		g[s].push_back(e);
		g[e].push_back(s);
	}
	bfs(0,1);
	bfs(1,n);
	s=0;
	for(i=1;i<=n;++i)	s+=len[0][i]<=len[1][i];
	if(s > (n-s))	puts("Fennec");
	else 		puts("Snuke");
	return 0;
}

Measured memory_bytes: 6656
//Solution for aoj 0568:Pasta
#include <iostream>
using namespace std;
const int surplus = 10000;
int n, k, a, b, ans;
int pasta[101][4][2], save[101];
void dp(int day){
	if (day > n)
		return;
	if (save[day]){
		for (int i = 1; i <= 3; i++){
			if (save[day] != i)
				pasta[day][save[day]][0] += pasta[day - 1][i][0] + pasta[day - 1][i][1];
			else
				pasta[day][i][1] += pasta[day - 1][i][0];
		}
		pasta[day][save[day]][0] %= surplus;
		pasta[day][save[day]][1] %= surplus;
	}
	else{
		for (int i = 1; i <= 3; i++){
			for (int j = 1; j <= 3; j++){
				if (i != j){
					pasta[day][i][0] += pasta[day - 1][j][0] + pasta[day - 1][j][1];
				}
				else{
					pasta[day][i][1] += pasta[day - 1][j][0];
				}
			}
			pasta[day][i][0] %= surplus;
			pasta[day][i][1] %= surplus;
		}
	}
	dp(day + 1);
}
int main(){
	cin >> n >> k;
	for (int i = 0; i < k; i++){
		cin >> a >> b;
		save[a] = b;
	}
	if (save[1])
		pasta[1][save[1]][0] = 1;
	else{
		for (int i = 1; i <= 3; i++){
			pasta[1][i][0] = 1;
		}
	}
	dp(2);
	for (int i = 1; i <= 3; i++){
		ans += pasta[n][i][0] + pasta[n][i][1];
	}
	ans %= surplus;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1168
# coding: utf-8
    
def main():
    N = int(input())
    S = input()[:N]

    min_count = count = S[1:].count('E')
    for i in range(1, N):
        if S[i - 1] == 'W':
            count += 1
        if S[i] == 'E':
            count -= 1
            if count < min_count:
                min_count = count

    print(min_count)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3676