akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class Main {
    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int n = in.nextInt();
        final int m = in.nextInt();
        final Map<Integer, List<Integer>> edges = new HashMap<>();
        final int[][] cost = new int[n][3];
        // -1 means not visited.
        for (int i = 0; i < n; i++) {
            Arrays.fill(cost[i], Integer.MIN_VALUE);
        }


        for (int i = 0; i < m; i++) {
            final int from = in.nextInt();
            final int to = in.nextInt();
            edges.compute(from - 1, (key, list) -> {
                if (list == null) {
                    list = new ArrayList<>();
                }
                list.add(to - 1);
                return list;
            });
        }
        final int s0 = in.nextInt() - 1;
        final int t0 = in.nextInt() - 1;
        final List<int[]> nodes = new ArrayList<>();
        nodes.add(new int[]{s0, 0});
        cost[s0][0] = 0;
        while (!nodes.isEmpty()) {
            final int[] from = nodes.remove(0);
            if (from[0] == t0 && from[1] == 0) {
                System.out.println(cost[from[0]][0] / 3);
                return;
            }

            for (Integer to : edges.getOrDefault(from[0], new ArrayList<>())) {
                final int state = from[1];
                final int nextState = (state + 1) % 3;
                if (cost[to][nextState] == Integer.MIN_VALUE) {
                    cost[to][nextState] = cost[from[0]][state] + 1;
                    nodes.add(new int[]{to, nextState});
                }
            }
        }
        System.out.println(-1);
    }
}


Measured memory_bytes: 109140
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> //__gnu_pbds::gp_hash_table<int, int> table;
//priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  //min heap

typedef int OwO;
typedef double UwU;

#define int long long
#define double long double
#define INF 1000000000
#define PI 3.14159265358979323846
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vvi vector<vector<int>>
#define vi vector<int>

using namespace std;

OwO main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  string s;
  cin >> s;
  int curr = s[0]-'0';
  int out = 0;
  for(int x = 1; x<s.size(); x++){
    if(curr == s[x]-'0'){
      out++;
    }
    curr ^= 1;
  }
  cout << out << endl;

  return 0;
}

Measured memory_bytes: 512
N = int(input().rstrip())
s = [input().rstrip() for i in range(N)]
M = int(input().rstrip())
t = [input().rstrip() for i in range(M)]

max = 0
for i in set(s + t):
    sum = 0
    for j in s:
        if i == j:
            sum += 1
    for j in t:
        if i == j:
            sum -= 1
    if sum > max:
        max = sum

print(max)

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

#define REP(i,n) for(int i=0;i<n;++i)
#define REPR(i,n) for(int i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define INF 999999999
#define SUR 1000000007
#define pb(a) push_back(a)
#define pf(a) push_front(a)
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int n;
  scanf("%d", &n);

  vector<int> v;
  SV(n,v);

  int odd = 0;
  REP(i,n){
    if(v[i] % 2 == 1){
      odd++;
    }
  }

  if(odd % 2 == 0){
    printf("YES\n");
  }else{
    printf("NO\n");
  }
  return 0;
}



Measured memory_bytes: 892
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <stdio.h>
#include <string.h>
#include <cstdlib>
#include <math.h>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <sstream>
#define INF 2000000000
using namespace std;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
#define sign cout<<"-----------"<<endl;
#define ll long long
#define PL pair<long long, long long>
#define P pair<int,int>
#define mk make_pair
#define en endl
#define WHITE 0
#define BLACK 2
#define GRAY 1
#define RE return 0
#define int ll


signed main(){
  string s,t;
  cin>>s>>t;
  s+=s;
  for(int i=0; i<s.size()/2; i++){
    bool succeed=true;
    for(int j=0; j<t.size(); j++){
      if(t[j]!=s[i+j]) {
        succeed=false;
        break;
      }
    }
    if(succeed){
      cout<<"Yes"<<en;
      return 0;
    }
  }

  cout<<"No"<<en;
  return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author emli
 */


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

class CManyRequirements {
public:

    void run(vector<vector<int>> &x,vector<int> a,int n,int m,int q,int &best){
        if (a.size() == n){
            int sum = 0;

            for (int i = 0; i < q; ++i) {
                if (a[x[i][1] - 1] - a[x[i][0] - 1] == x[i][2] )
                    sum += x[i][3];
            }
            best = max(best,sum);
            return;
        }

        int last = !a.empty() ? a.back() : 0;
        for (int i = last; i < m; ++i) {
            a.push_back(i);
            run(x,a,n,m,q,best);
            a.pop_back();
        }
    }
    void solve(std::istream& cin, std::ostream& cout) {
		ios::sync_with_stdio(false);
        cin.tie(nullptr);

        int n,m,q;

        cin >> n >> m >> q;

        vector<vector<int>> x(q,vector<int>(4));

        for (int i = 0; i < q; ++i) {
            for (int j = 0; j < 4; ++j) {
                cin >> x[i][j];
            }
        }

        int best = INT_MIN;
        run(x,{},n,m,q,best);

        cout << best << endl;


	}
};


int main() {
	CManyRequirements solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define Would
#define you
#define please

ll mod = 1e9 + 7;

ll POW(ll A, ll B) {
	if (B == 0) return 1;
	if (B % 2 == 0) {
		ll hannbunn = POW(A, B / 2);
		return hannbunn * hannbunn % mod;
	}
	else {
		return A * POW(A, B - 1) % mod;
	}
}

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


	int N;
	cin >> N;
	int A[100100];
	map<int, int> MAP;
	rep(i, N + 1) {
		cin >> A[i];
		MAP[A[i]]++;
	}
	int ooi = 0;
	for (auto itr : MAP) {
		if (itr.second == 2) {
			ooi = itr.first;
			break;
		}
	}
	int K1 = -1, K2;
	rep(i, N + 1) {
		if (A[i] == ooi) {
			if (K1 == -1) K1 = i;
			else K2 = i;
		}
	}
	int K = K1 + N - K2;

	ll comb[100100] = {};
	comb[0] = 1;
	rep1(i, N + 1) {
		comb[i] = comb[i - 1] * (N + 2 - i) % mod;
		comb[i] = comb[i] * POW(i, mod - 2) % mod;
	}

	ll comb2[100100] = {};
	comb2[0] = 1;
	rep1(i, K) {
		comb2[i] = comb2[i - 1] * (K + 1 - i) % mod;
		comb2[i] = comb2[i] * POW(i, mod - 2) % mod;
	}

	rep1(i, N + 1) {
		ll kotae = (comb[i] - comb2[i - 1] + mod) % mod;
		co(kotae);
	}

	Would you please return 0;
}

Measured memory_bytes: 7936
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1000000;
const int MOD = 1000000007;
vector<pair<int,int>> hen[100000];
int mk[2][100000];
bool used[100000]={},tdd[100000]={};
void dfs(int a){

  used[a]=true;
  for(int i=0;i<hen[a].size();i++){
 
    if(used[hen[a][i].first]){

      continue;
    }
    if(tdd[a]){
     swap(mk[0][hen[a][i].second],mk[1][hen[a][i].second]);
      tdd[a]=!tdd[a];
      tdd[hen[a][i].first]=!tdd[hen[a][i].first];
    }
    dfs(hen[a][i].first);
    if(tdd[hen[a][i].first]){
      swap(mk[0][hen[a][i].second],mk[1][hen[a][i].second]);
      tdd[a]=!tdd[a];
      tdd[hen[a][i].first]=!tdd[hen[a][i].first];
    }
  }
}
signed main() {
int n,m;
cin>>n>>m;
int A,b;
for(int i=0;i<m;i++){
  cin>>A>>b;A--;b--;
  mk[0][i]=A;mk[1][i]=b;
  hen[A].push_back(make_pair(b,i));
  hen[b].push_back(make_pair(A,i));
  tdd[A]=!tdd[A];
}

dfs(0);
if(tdd[0])cout<<-1;
else{
  for(int i=0;i<m;i++)cout<<mk[0][i]+1<<' '<<mk[1][i]+1<<endl;
}

}


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

int main() {
    int A, B, a[3];
    cin >> A >> B;
    a[0] = A+B;
    a[1] = A-B;
    a[2] = A*B;
    sort(a, a+3);
    cout << a[2] << "\n";
}

Measured memory_bytes: 384
#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 ALL(v) (v).begin(),(v).end()

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

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

const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-10;

ll n, l, q;
ll x[112345];
ll db[25][112345];

int main() {
	cin >> n;
	REP(i, n) scanf("%lld", x + i);
	cin >> l >> q;
	
	fill(db[0], db[25], INF);
	REP(i, n) {
		int pos = upper_bound(x, x + n, x[i] + l) - x - 1;
		db[0][i] = pos;
	}
	FOR(i, 1, 25) REP(j, n) db[i][j] = db[i - 1][ db[i - 1][j] ];
	
	while (q--) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (a > b) swap(a, b);
		a--; b--;
		
		ll cnt = 0;
		
		while (a < b) {
			int l = 0, r = 25;
			while (r - l > 1) {
				int m = (r + l) / 2;
				if (db[m][a] < b) l = m;
				else r = m;
			}
			cnt += 1 << l;
			a = db[l][a];
		}
		
		printf("%lld\n", cnt);
	}
	
	return 0;
}

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

using ll = long long;

#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define clr(a, b) memset(a, b, sizeof(a))
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REPD(i, a, b) for(int i=(int)(a)-1; i>=(int)(b); --i)

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

    int N, x;
    cin >> N >> x;
    N = 2*N - 1;
    if(x == N || x == 1) {
        cout << "No\n";
    } else {
        vector<int> res(N, -1);
        if(N == 2) {
            res[0] = 1, res[1] = 2;
        } else {
            res[N/2] = x;
            res[N/2 + 1] = N;
            res[N/2 - 1] = 1;
            deque<int> dq(N);
            iota(all(dq), 1);
            dq.pop_front();
            dq.pop_back();
            int f = 0;
            REP(i, N/2 + 2, N) {
                if(!f) {
                    if(dq.front() == x) dq.pop_front();
                    res[i] = dq.front();
                    dq.pop_front();
                } else {
                    if(dq.back() == x) dq.pop_back();
                    res[i] = dq.back();
                    dq.pop_back();
                }
                f ^= 1;
            }
            f = 1;
            REPD(i, N/2 - 1, 0) {
                if(!f) {
                    if(dq.front() == x) dq.pop_front();
                    res[i] = dq.front();
                    dq.pop_front();
                } else {
                    if(dq.back() == x) dq.pop_back();
                    res[i] = dq.back();
                    dq.pop_back();
                }
                f ^= 1;
            }

            cout << "Yes\n";
            REP(i, 0, N)
                cout << res[i] << "\n";
        }
    }
    return 0;
}


Measured memory_bytes: 4812
#include <stdio.h>
#include <stdlib.h>
#define LENGTH_N 16
#define LENGTH_CV 256
#define NUM_ELEMENT 128

void split_str_space(char str[], char result[][6], int split_num) {
	int i = 0, j = 0, k = 0;
	while (i < LENGTH_CV && j < split_num) {
		if (str[i] == ' ' || str[i] == '\0') {
			while( str[++i] == ' ' || str[i] == '\0'){}
			j++;
			result[j][k] = '\0'; 
			k = 0;
			continue;
		}
		result[j][k++] = str[i++];
	}
}

int main(void) {

	char input_N[LENGTH_N];
	fgets(input_N, LENGTH_N - 1, stdin);
	int N = atoi(input_N);
	
	char input_V[LENGTH_CV];
	char input_C[LENGTH_CV];
	char num_array_V[NUM_ELEMENT][6];
	char num_array_C[NUM_ELEMENT][6];
	
	fgets(input_V, LENGTH_CV - 1, stdin);
	fgets(input_C, LENGTH_CV - 1, stdin);

	split_str_space(input_V, num_array_V, N);
	split_str_space(input_C, num_array_C, N);
	
	int sum = 0;
	for (int i = 0; i < N ; i++){
		int v = atoi(num_array_V[i]);
		int c = atoi(num_array_C[i]);
		if (v - c > 0) sum += v - c;
	}
	
	printf("%d", sum); 

}

Measured memory_bytes: 128
//-- Araz Jabrayilov --
//-- araz17---zuna#1041 --

#include <bits/stdc++.h>

#define ll long long
#define endl '\n'
#define F first
#define S second

using namespace std;

///int a[1005];

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

    int n = 0;
    int x = 0;

    cin >> n;

    string s;

    set <string> se;

    for(int i = 1; i <= n; i++){
        cin >> s;


        if(se.count(s) == 0){
            se.insert(s);
            x++;
        }

    }

    cout << x << endl;


    return 0;
}


Measured memory_bytes: 19248
#include<bits/stdc++.h>
using namespace std;
int dp[1000000];
int main()
{
    int i,j,k,l,m,n;
    cin>>n>>k;
    int a[n+10];

    for(i=0;i<n;i++)cin>>a[i];
      for(i=0;i<n;i++)dp[i] = INT_MAX;
    dp[0] = 0;
    dp[1] = abs(a[0]-a[1]);
    for(i=2;i<n;i++)
    {

        for(j=1;j<=k && j<=i;j++)
        dp[i] = min(dp[i-j]+abs(a[i]-a[i-j]),dp[i]);
    }

    cout<<dp[n-1]<<endl;
}



Measured memory_bytes: 1024
import itertools

n, m, x = map(int, input().split())
a = []
c = []
for i in range(n):
    line = list(map(int, input().split()))
    c.append(line[0])
    line.pop(0)
    a.append(line)
p = list(map(list, list(itertools.product([0,1], repeat=n))))
flag = 1
min_money = 10**10
for pattern in p:
    flag_1 = 0
    alg = [0 for i in range(m)]
    money = 0
    for i in range(n):
        if pattern[i]:
            money += c[i]
            for j in range(m):
                alg[j] += a[i][j]
    for i in range(m):
        if alg[i] < x:
            flag_1 = 1
    if flag_1:
        continue
    min_money = min(money, min_money)
    flag = 0
if flag:
    print(-1)
else:
    print(min_money)



Measured memory_bytes: 74396
#![allow(unused_imports)]
use itertools::Itertools;
use proconio::{input, marker::*};
use std::cmp::*;
use std::collections::HashMap;
use std::collections::*;
use superslice::*;
use whiteread::parse_line;
 
 
fn main() {
    let (a, b, _, k): (i64, i64, i64, i64) = parse_line().unwrap();
    // a 1のカード b 0のカード c -1のカード k枚選ぶ 最大値を求める
    let mut current = k;
    if current < a {
        println!("{}", current);
        return;
    } else {
        current = current - a;
    }
    if current <= b {
        println!("{}", a);
        return;
    } else {
        current = current - b;
    }
    println!("{}", a - current);
}


Measured memory_bytes: 2184
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args)
	{
		new Main().run();
	}
	
	public void run()
	{
		Scanner file = new Scanner(System.in);
		int R = file.nextInt();
		int G = file.nextInt();
		int B = file.nextInt();
		int[] ints = new int[]{R,G,B};
		int N = file.nextInt();
		int[][] dp = new int[4][N+1];
		dp[0][0] = 1;
		for(int i = 1;i<dp.length;i++)
		{
			for(int j = 0;j<dp[i].length;j++)
			{
				dp[i][j] = dp[i-1][j];
				if(ints[i-1]<=j)
					dp[i][j] += dp[i][j-ints[i-1]];
			}
		}
		System.out.println(dp[3][N]);
	}
	
}


Measured memory_bytes: 22100
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long a = sc.nextLong();
		long b = sc.nextLong();

		long c = b - a;

		long answer = 0;

		if (c % 2 == 0) {
			answer = c / 2;
		} else {
			if (n - b > a - 1) {
				answer = a + (c - 1) / 2;
			} else {
				answer = n - b + 1 + (c - 1) / 2;
			}
		}

		System.out.println(answer);
	}

}


Measured memory_bytes: 22740
using System;
using System.Linq;

class Program {

    private static int count;
    private static bool[,] route;
    private static bool[] visit;
    private static int N;
    static void Main(string[] args) {
        N = Cin.Ni();
        int M = Cin.Ni();
        route = new bool[N, N];
        visit = new bool[N];
        for (int i = 0; i < M; i++) {
            int a = Cin.Ni() - 1;
            int b = Cin.Ni() - 1;
            route[a, b] = true;
            route[b, a] = true;
        }
        visit[0] = true;
        DFS(0);
        Console.WriteLine(count);
    }
    public static void DFS(int start) {
        if (visit.All(v => v)) {
            count++;
            return;
        }
        for (int i = 0; i < visit.Length; i++) {
            if (route[start, i] && visit[i] == false) {
                visit[i] = true;
                DFS(i);
                visit[i] = false;
            }
        }
        return;
    }
}


public class Cin {
    private static string[] s = new string[0];
    private static int i = 0;

    private static char[] cs = new char[] { ' ' };

    public static string Next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return Next();
    }

    public static int Ni() {
        return int.Parse(Next());
    }

    public static long NextLong() {
        return long.Parse(Next());
    }

    public static double NextDouble() {
        return double.Parse(Next());
    }

}


Measured memory_bytes: 3160
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <bitset>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <sstream>
#include <fstream>
//#include <tuple>
#include <set>
#include <string.h>
#include <functional>

#define X first
#define Y second
#define MP make_pair
//#define MT make_tuple
#define REP(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
#define FOR(i, n) REP(i, 0, n)
typedef long long ll;
using namespace std;
const int MAX = 500;

template<class T, class U>
void convert(T &t, U &u)
{
	stringstream ss;
	ss << t;
	ss >> u;
}

int main()
{
	string n;
	while ( cin >> n ){
		if ( cin.eof() ) break;

		string ans;

		FOR( i, n.size() ){
			if( n[i] == '@' ){
				FOR(j, n[i + 1] - '0'){
					ans.push_back( n[i + 2] );
				}
				i += 2;
			}
			else{
				ans.push_back( n[i] );
			}
		}

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

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

using namespace std;

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

	int n;
	cin >> n;
	string s,t;
	cin >> s >> t;
	for(int i=0; i<s.length(); i++){
		cout << s[i] << t[i];
	}
	return 0;
}

Measured memory_bytes: 3560
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

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

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n;cin>>n;n--;
  cout<<n/2<<endl;

  return 0;

}


Measured memory_bytes: 764
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                ans = max(ans,dist[nx][ny])
                d.append([nx,ny])

print(ans)


Measured memory_bytes: 214504
def insertion(A):
    for i in range(len(A)):
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = key
        print(' '.join([str(x) for x in A]))

N = int(input())
A = [int(x) for x in input().strip().split(' ')]
insertion(A)

Measured memory_bytes: 7724
using System;
using System.Collections.Generic;

class Program
{
    public static void Main(string[] args)
    {
        Program pg = new Program();
        pg.Exe();
    }
    public void Exe()
    {
        int[] ary = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        int way = ary[1];
        int num = ary[0];
        ary = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

        List<Observatory> ob_list = new List<Observatory>();
        for(int i = 0; i < num; i++)
        {
            ob_list.Add(new Observatory(ary[i]));
        }
        for(int i = 0; i < way; i++)
        {
            ary = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int a = ary[0] - 1;
            int b = ary[1] - 1;
            if(ob_list[a].high > ob_list[b].high)
            {
                ob_list[b].best = false;
            }
            else if(ob_list[a].high < ob_list[b].high)
            {
                ob_list[a].best = false;
            }
            else
            {
                ob_list[a].best = false;
                ob_list[b].best = false;
            }
        }
        int ans = 0;
        foreach (Observatory item in ob_list)
        {
            if(item.best) ans++;
        }

        Console.WriteLine(ans);
    }
}
class Observatory
{
    public int high;
    public List<int> way_list;
    public bool best;
    public Observatory(int high)
    {
        this.high = high;
        this.way_list = new List<int>();
        this.best = true;
    }
}



Measured memory_bytes: 56696
def want(x,y):

    ret = 0

    for i in xy:
        ret = max(ret, ((i[0]-x)**2+(i[1]-y)**2)**0.5)

    return ret


def want2(x):

    ly = miny
    ry = maxy

    while ry-ly > 10**(-7) and ry-ly > (ry / (10**6)):

        m1 = (ly*2+ry)/3
        m2 = (ly+ry*2)/3

        rm1 = want(x,m1)
        rm2 = want(x,m2)

        if rm1 > rm2:
            ly = m1
        else:
            ry = m2

    ansy = (ly+ry)/2
    return want(x,ansy)
    
    

N = int(input())

xy = []
minx = float("inf")
maxx = float("-inf")
miny = float("inf")
maxy = float("-inf")

for i in range(N):

    x,y = map(int,input().split())
    xy.append([x,y])

    minx = min(minx,x)
    miny = min(miny,y)
    maxx = max(maxx,x)
    maxy = max(maxy,y)


lx = minx
rx = maxx

while rx-lx > 10**(-7) and rx-lx > (rx / (10**6)):

    m1 = (lx*2+rx)/3
    m2 = (lx+rx*2)/3

    rm1 = want2(m1)
    rm2 = want2(m2)

    if rm1 > rm2:
        lx = m1
    else:
        rx = m2

print ((rm1+rm2)/2)

    


Measured memory_bytes: 43612
import collections
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

n,M=map(int,input().split())
m=10**9+7
 
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+100):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

def primes(n):
  is_prime=[True]*(n+1)
  is_prime[0]=False
  is_prime[1]=False
  for i in range(2,int(n**0.5)+1):
    if not is_prime[i]:
      continue
    for j in range(i*2,n+1,i):
      is_prime[j]=False
  return [i for i in range(n+1) if is_prime[i]]

def fact(n):
  l=primes(int(n**0.5)+1)
  L=[]
  for i in range(len(l)):
    while n%l[i]==0:
      n=n//l[i]
      L.append(l[i])
    if n==1:
      break
  if n!=1:
    L.append(n)
  return L

x=list(collections.Counter(fact(M)).values())
ct=1
for i in range(len(x)):
  ct*=cmb(x[i]+n-1,n-1,m)
  ct%=m
print(ct)

Measured memory_bytes: 15680
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define __ %=Mod
using namespace std;

const int maxn = 405;
const ll Mod = 1e9+7;

int n,N;
int a[maxn],b[maxn];
ll f[maxn][maxn][200];
int as[maxn],bs[maxn];

ll g[maxn][maxn];

int main()
{
	scanf("%d",&n); N=n/3;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),as[a[i]]=i;
	for(int i=1;i<=n;i++) scanf("%d",&b[i]),bs[b[i]]=i;
	
	//if(a[1]==b[1]) return puts("0"),0;
	f[1][1][0]=1ll;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=0;k<=N;k++) if(f[i][j][k])
	{
		ll tmp=f[i][j][k];
		if(bs[a[i]]<=j||as[b[j]]<=i)
		{
			if(a[i]==b[j])
			{
				if(k) (f[i+1][j+1][k-1]+=tmp*(ll)k%Mod)__;
				continue;
			}
			if(bs[a[i]]<=j) (f[i+1][j][k]+=tmp)__;
			else (f[i][j+1][k]+=tmp)__;
			continue;
		}
		(f[i+1][j+1][k+1]+=tmp)__;
		if(!k) continue;
		(f[i+1][j][k-1]+=tmp*(ll)k%Mod)__;
		(f[i][j+1][k-1]+=tmp*(ll)k%Mod)__;
		(f[i+1][j+1][k-2]-=tmp*(ll)k%Mod*(k-1)%Mod)__;
	}
	ll re=0;
	for(int i=N+1;i<=n+1;i++)
		(re+=f[i][n+1][0]+f[n+1][i][0])__;
	(re-=f[n+1][n+1][0]-Mod)%=Mod;
	
	g[0][0]=1ll;
	for(int i=0;i<n;i++) for(int j=0;j<=i;j++) if(g[i][j])
	{
		if(i-j<N) (g[i+1][j]+=g[i][j])__;
		if(j<2*N&&(i-j)*2>j) (g[i+1][j+1]+=g[i][j]*(ll)((i-j)*2-j)%Mod)__;
	}
	(re*=g[n][2*N])__;
	printf("%lld\n",re);
	
	return 0;
}


Measured memory_bytes: 255488
W,H,N = gets.split.map(&:to_i)
x = Array.new
y = Array.new
a = Array.new
for i in 0..N-1
    x[i],y[i],a[i] = gets.split.map(&:to_i)
end

x_min = Array.new
x_max = Array.new
y_min = Array.new
y_max = Array.new
x_min[0] = 0
x_max[0] = W
y_min[0] = 0
y_max[0] = H
for i in 0..N-1 
    if a[i] == 1
        x_min.push(x[i])
    elsif a[i] == 2
        x_max.push(x[i])
    elsif a[i] == 3
        y_min.push(y[i])
    elsif a[i] == 4
        y_max.push(y[i])
    end
end

if x_max.min-x_min.max > 0 && y_max.min-y_min.max > 0
    puts ((x_max.min-x_min.max) * (y_max.min-y_min.max))
else
    puts 0
end



Measured memory_bytes: 1916
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef struct D{int t;vector<int>d;}D;
int N,r=99;
vector<int>s,a;
map<vector<int>,int>F;

bool ch(D t)
{
	for(int i=0;i<N;i++)
		if(a[i]!=t.d[i])return false;
	return true;
}

int main()
{
	for(;scanf("%d",&N),N;)
	{
		for(int i=0,t;i<N;i++)
		{
			scanf("%1d",&t);
			s.push_back(t);
		}
		for(int i=0,t;i<N;i++)
		{
			scanf("%1d",&t);
			a.push_back(t);
		}
		r=99;
		queue<D>Q;
		D ins={0,s};
		Q.push(ins);
		while(!Q.empty())
		{
			D tmp=Q.front();Q.pop();
			if(F.find(tmp.d)!=F.end()&&F[tmp.d]<tmp.t)continue;
			if(ch(tmp))
			{
				r=min(r,tmp.t);
				continue;
			}
			for(int i=0;i<N;i++)
			{
				if(a[i]!=tmp.d[i])
				{
					int mov=(10+(a[i]-tmp.d[i]))%10;
					for(int k=i+1;k<=N;k++)
					{
						ins=tmp;
						for(int j=i;j<k;j++)
						{
							ins.d[j]=(ins.d[j]+mov)%10;
						}
						if(F.count(ins.d)==0)
						{
							ins.t++;
							Q.push(ins);
							F[ins.d]=ins.t;
						}
					}
					break;
				}
			}
		}
		s.clear();
		a.clear();
		F.clear();
		printf("%d\n",r);
	}
}

Measured memory_bytes: 2984
let () =
  Scanf.scanf "%d" @@ fun n ->
  let g = Array.init n (fun _ -> []) in
  for _ = 1 to n-1 do
    Scanf.scanf " %d %d" @@ fun a b ->
    g.(a-1) <- b-1 :: g.(a-1);
    g.(b-1) <- a-1 :: g.(b-1)
  done;

  let dists_from s =
    let res = Array.make n n in
    let rec dfs x d =
      res.(x) <- d;
      g.(x) |> List.iter @@ fun y ->
        if d+1 < res.(y) then dfs y (d+1)
    in dfs s 0;
    res
  in

  let f = dists_from 0 in
  let s = dists_from (n-1) in
  let rec loop i v =
    if i >= n then (if v > n/2 then "Fennec" else "Snuke")
    else loop (i+1) (if f.(i) <= s.(i) then v+1 else v)
  in loop 0 0 |> print_endline

Measured memory_bytes: 20608
#include<bits/stdc++.h>
using namespace std;
map<int,int> aa;
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    vector<int> v;
    while(n--)
    {
    int x;
    cin >> x;
    aa[x]++;
    if(aa[x]==2)
    {
    v.push_back(x);
    aa[x]=0;
    }
    }
    sort(v.begin(),v.end());
    if(v.size()<=1){
    cout << 0;
    }
    else
    {
    long long ans=(long long)v[v.size()-1]*(long long)v[v.size()-2];
    cout << ans;
    }
}


Measured memory_bytes: 4992
def main():
    n = int(input())
    f = [0 for _ in range(200 ** 2 * 6)]
    for x in range(1, 111):
        for y in range(1, 111):
            for z in range(1, 111):
                f[x * x + y * y + z * z + x * y + y * z + z * x] += 1
    for i in range(1, n + 1):
        print(f[i])


if __name__ == '__main__':
    main()



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

int main(void) {
    int N, X, count=0, M;
    cin >> N;
    vector<int> m(N);
    cin >> X;

    for(int i=0;i<N;i++){
      cin >> M;
      X -= M;
      m[i] = M;

    }
    sort(m.begin(), m.end());

      while(X>=m[0]){
        X-=m[0];
        count++;
      }

    cout<< count+N << endl ;

    return 0;
}


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

int cnt[257];

char S[10];

int main(){
	scanf(" %s", S);
	
	memset(cnt, 0, sizeof(cnt));
	for(int i = 0; i < 4; i ++){
		cnt[S[i]-'A'] ++;
	}
	
	int cnt2 = 0;
	for(int i = 0; i < 256; i ++){
		if(cnt[i] == 2){
			cnt2 ++;
		}
	}
	if(cnt2 == 2){
		printf("Yes");
	}else{
		printf("No");
	}
}


Measured memory_bytes: 256
#include<cstdio>
#include<vector>
#include<algorithm>

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

using namespace std;

typedef long long ll;

class union_find{
	vector<int> a;
public:
	union_find(int n):a(n,-1){}
	int find(int x){
		if(a[x]<0) return x;
		return a[x]=find(a[x]);
	}
	void unite(int x,int y){
		x=find(x),y=find(y);
		if(x!=y){ a[x]+=a[y]; a[y]=x; }
	}
	int size(int x){ return -a[find(x)]; }
};

struct edge{
	int u,v,cost;
	bool operator<(const edge &e)const{ return cost<e.cost; }
};

int main(){
	int n; scanf("%d",&n);
	static edge E[199999];
	rep(i,n-1){
		int u,v,cost; scanf("%d%d%d",&u,&v,&cost);
		E[i]=(edge){u,v,cost};
	}
	sort(E,E+n-1);

	ll ans=0;
	union_find U(n);
	rep(i,n-1){
		int u=E[i].u,v=E[i].v,cost=E[i].cost;
		ans+=(ll)cost*U.size(u)*U.size(v);
		U.unite(u,v);
	}
	printf("%lld\n",ans);

	return 0;
}

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

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;

	vector<int> cnts( 100002 );
	for( int i = 0; i < N; ++i ) {
		int x;
		cin >> x;

		cnts[x] += 1;
		cnts[x+1] += 1;
		cnts[x+2] += 1;
	}

	int result = 0;
	for( int i = 0; i < cnts.size(); ++i ) {
		if( cnts[i] > result ) {
			result = cnts[i];
		}
	}

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


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define EPS 1e-12

int main(void)
{
  int a, b;
  cin >> a >> b;

  if(a == b) cout << "Draw" << endl;
  else if(a == 1) cout << "Alice" << endl;
  else if(b == 1) cout << "Bob" << endl;
  else if(a < b) cout << "Bob" << endl;
  else if(b < a) cout << "Alice" << endl;

  return 0;
}


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	int c=0;
	for(int i=0; i<n; i++)
	{
		int a;
		cin >> a;
		if(a%2!=0)
		{
			c++;
		}
	}
	if(c%2==0)
	{
		cout << "YES";
	}
	else
	{
		cout << "NO";
	}
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<utility>


int main(){
    int bingo[3][3];
    std::map<int, int> mpX, mpY;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            std::cin >> bingo[i][j];
            mpX[bingo[i][j]] = i + 1; // to 1 origin
            mpY[bingo[i][j]] = j + 1; // to 1 origin
        }
    }
    int n;
    std::cin >> n;
    for(int i = 0; i < n; i++){
        int b;
        std::cin >> b;
        int x = mpX[b];
        int y = mpY[b];
        if(x == 0 && y == 0) continue;
        else{
            bingo[x - 1][y -1] = 0;
        }
    }

    // check bingo
    bool isBingo = false;
    // tate
    for(int i = 0; i < 3; i++){
        if(bingo[0][i] == 0 && bingo[1][i] == 0 && bingo[2][i] == 0){
            isBingo = true;
            break;
        }
    }

    // yoko
    for(int i = 0; i < 3; i++){
        if(bingo[i][0] == 0 && bingo[i][1] == 0 && bingo[i][2] == 0){
            isBingo = true;
            break;
        }
    }

    // naname
    if(bingo[0][0] == 0 && bingo[1][1] == 0 && bingo[2][2] == 0){
        isBingo = true;
    }
    if(bingo[2][0] == 0 && bingo[1][1] == 0 && bingo[0][2] == 0){
        isBingo = true;
    }

    if(isBingo){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		String[] lines = line.split(" ");
		int N = Integer.parseInt(lines[0]);
		int K = Integer.parseInt(lines[1]);

		double ans = 0;
		for(int i = 1; i < N+1; i++) {
			int count = 1;
			while(K > i*count) {
				count *= 2;
			}
			ans += 1/(double)count;
		}
		System.out.println(ans / N);
	}

}


Measured memory_bytes: 35836
// Aaradhya Beri
#pragma GCC optimze("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
#define w(x) int x; cin>>x; while(x--)
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;

int powm(int a, int b) {
    int res=1;
    while(b) {
        if(b&1)
            res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
 

signed main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cout<<fixed<<setprecision(8);
    int n;
    cin>>n;
    string s;
    cin>>s;
    int l = s.length();
    if(l <= n)
        cout<<s<<endl;
    else
    {
        s.resize(n);
        s += "...";
        cout<<s<<endl;
    }
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>

using namespace std;

int main(){

    int N, Y;
    cin >> N >> Y;
    int i;
    for(i = 0; i <= Y/10000; i++){
        int n = Y - i * 10000;
        int j;
        for(j = 0; j <= n/5000; j++){
            int l = n - 5000 * j;
            if(l == 1000 * (N - i - j)){
                cout << i << " " << j << " " << N - i - j << endl;
                return 0;
            }
        }

    }
    cout << "-1 -1 -1" << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
 
main()
{
int a,b;
   while(1){
    scanf("%d %d",&a,&b);
    if((a|b)==0)break;
    if(b<a)std::swap(a,b);
    printf("%d %d\n",a,b);
    }
}


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

using namespace std;

int red,stup;
int d;
int grid[305][305];
pair<int,int> x[305*305];
int ans[305*305];

int main(){
	cin >> red >> stup >> d;
	for(int i = 0; i < red; i++){
		for(int j = 0; j < stup; j++){
			cin >> grid[i][j];
			x[grid[i][j]].first = i+1;
			x[grid[i][j]].second = j+1;
		}
	}
	for(int i = 1; i <= d; i++){
		ans[i] = 0;
	}
	for(int i = 1; i <= red*stup-d; i++){
		ans[i+d] = ans[i] + abs(x[i+d].first - x[i].first) + abs(x[i+d].second - x[i].second);
	}
	int q;
	cin >> q;
	while(q--){
		int l,r;
		cin >> l >> r;
		if(l == r) cout << 0 << endl;
		else{
			cout << ans[r]-ans[l] << endl;
		}
	} 
}

Measured memory_bytes: 2560
N,M = map(int,input().split())

favo_count_of_food = [0 for _ in range(M)]

for i in range(N):
    answers = list(map(int,input().split()))
    for answer in answers[1:]:
        favo_count_of_food[answer-1] += 1
        
print(favo_count_of_food.count(N))
        

Measured memory_bytes: 3060
#include <stdio.h>
int main(void){
    
    int a,b,c;
    
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    
    if(a<b&&b<c){
    puts("Yes");
    }
    
    else {
    puts("No");
    }
    
   
    
    return 0;
}


Measured memory_bytes: 2044
H, W = map(int, input().split())
N = int(input())
A = [int(_) for _ in input().split()]

grid = [[0] * W for h in range(H)]

h, w = 0, 0
for n in range(N):
    while A[n] > 0:
        A[n] -= 1
        grid[h][w] = n + 1
        if h % 2 == 0:
            w += 1
            if w == W:
                h += 1
                w = W - 1
        elif h % 2 == 1:
            w -= 1
            if w == -1:
                h += 1
                w = 0
for item in grid:
    print(*item)

Measured memory_bytes: 3916
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

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

const int INF = 1001001001;

int main(){
    int N;
    cin >> N;
    vector<P> x(N), y(N);
    
    for(int i = 0; i < N; ++i){
        int temp;
        cin >> temp;
        x[i] = P(temp, i);
        cin >> temp;
        y[i] = P(temp, i);
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    
    vector<vector<P>> graph(N);     // (cost, to)
    for(int i = 0; i < N - 1; ++i){
        P p1 = x[i];
        P p2 = x[i + 1];
        int temp = p2.first - p1.first;
        graph[p1.second].push_back(P(temp, p2.second));
        graph[p2.second].push_back(P(temp, p1.second));
        
        p1 = y[i];
        p2 = y[i + 1];
        temp = p2.first - p1.first;
        graph[p1.second].push_back(P(temp, p2.second));
        graph[p2.second].push_back(P(temp, p1.second));
    }
    
    ll res = 0;
    vector<int> mincost(N, INF);
    vector<bool> used(N, false);
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, 0));          // (現在の部分最小全域木からのcost, coord)
    mincost[0] = 0;
    
    while(!que.empty()){
        P p = que.top();
        que.pop();
        
        if(used[p.second])      continue;
        
        used[p.second] = true;
        if(mincost[p.second] == p.first)       res += p.first;
        
        for(int i = 0; i < graph[p.second].size(); ++i){
            P t = graph[p.second][i];
            mincost[t.second] = min(mincost[t.second], t.first);
            que.push(P(t.first, t.second));
        }
    }
    
    cout << res << endl;
}

Measured memory_bytes: 12020
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder2 {
	class Program {
		static void Main(string[] args) {

	
		var inputArray = retreiveStringArray();
			var inputCount = 1;

			// 不正な入力は処理しない
			if (inputArray.Length != inputCount) {
				Console.WriteLine("invalid input");
				return;
			}
			var S = inputArray[0];
			var T = S.Replace('?', 'D');

			//答えの出力
			var ans = T;
			Console.WriteLine(ans);

		}

		/// <summary>
		/// スペースで区切られた文字列配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static string[] retreiveStringArray() {
			var inputArray = Console.ReadLine().Split(' ');
			return inputArray;
		}

		/// <summary>
		/// スペースで区切られた整数配列の入力を受け取る
		/// </summary>
		/// <returns></returns>
		private static long[] retreiveLongArray() {
			var inputArray = Console.ReadLine().Split(' ');
			var longArray = inputArray.Select(s => long.Parse(s));
			return longArray.ToArray();
		}
	}
}

Measured memory_bytes: 26976
import math

n, d = map(int, input().split())
pts = [list(map(int, input().split())) for _ in range(n)]


def dist2(pt0, pt1):
    d = 0
    for x0, y0 in zip(pt0, pt1):
        d += (x0 - y0)**2
    return d


count = 0
for i in range(n):
    for j in range(i + 1, n):
        d2 = dist2(pts[i], pts[j])
        if int(math.sqrt(d2))**2 == d2:
            count += 1
print(count)

Measured memory_bytes: 38256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define first_more_idx(ve, num) upper_bound(all(ve), num)-ve.begin() // idx = first_more_idx(ve,num); if(idx = ve.size()) , then not exist
#define first_lessequal_idx(ve, num) lower_bound(all(ve), num)-ve.begin()
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > >
#define pq_pair_ts priority_queue <pair<ll,ll> > // only sort first param
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
ll power(ll x, ll n){if(n == 0) return 1;return  (n%2)? x*power(x, n-1)%MOD : power(x*x%MOD, n/2);}
ll dx[]={0, 0, -1, 1};
ll dy[]={1, -1, 0, 0};// up,down,left right


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string S;
    cin >> S;
    
    ll num[512345];
    rep(i, S.size()  + 1) num[i] = 0 ;
    
    for(ll i = 0; i < S.size(); i++){
        if(S[i] == '<') num[i+1] = num[i] + 1;
    }
    
    for(ll i =S.size() - 1 ; i >=0; i--){
        if(S[i] == '>') num[i] = max(num[i] , num[i+1] + 1LL);
    }
    ll ans = 0 ;
    rep(i, S.size() + 1){
        ans += num[i] ;
    }

    cout << ans << endl;
    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 4764
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <iterator>
#include <numeric>
#include <cstdint>
#include <cmath>
#include <bitset>
#include <string>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <random>
#include <chrono>

#define N_TIMES(i, n)     for ( uint64_t i = 0;     i <  n; ++i )
#define N_TIMES_REV(i, n) for (  int64_t i = n - 1; i >= 0; --i )

template<typename T> using maximum_heap = std::priority_queue<T, std::vector<T>, std::less<T>>;
template<typename T> using minimum_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
std::istream& operator>>(std::istream &is, std::vector<T> &v)
{
  for (typename std::vector<T>::size_type i = 0; i < v.size(); ++i) {
    is >> v[i];
  }
  return is;
}

using namespace std;

struct Pair
{
  uint64_t p, q;
  Pair(uint64_t p, uint64_t q) : p(p), q(q) {}
  uint64_t min() const { return std::min(p, q); }
  bool operator<(const Pair &rhs) const {
    return this->min() < rhs.min();
  }
  bool operator>(const Pair &rhs) const {
    return this->min() > rhs.min();
  }
};

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

  vector<uint64_t> A(N);
  cin >> A;

  maximum_heap<uint64_t> heap;
  N_TIMES(n, N) { heap.push(A[n]); }

  uint64_t sum = 0, first = heap.top();
  heap.pop();

  maximum_heap<Pair> ring;
  ring.emplace(first, first);

  while (!heap.empty()) {
    uint64_t x = heap.top(); heap.pop();

    Pair ps = ring.top(); ring.pop();
    sum += ps.min();

    ring.emplace(ps.p, x);
    ring.emplace(x, ps.q);
  }

  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 10580
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
const int MAX = 1010;
const int INF = MAX * MAX * 10;
int dp[2][4][4][MAX][MAX]={};
int ts[MAX][MAX]={};

signed main(){
  int h,w;
  cin>>h>>w;
  vector<string> vs(h);
  for(int i=0;i<h;i++) cin>>vs[i],vs[i]=".."+vs[i]+"..";
  vs.emplace(vs.begin(),string(w+4,'.'));
  vs.emplace(vs.begin(),string(w+4,'.'));
  vs.emplace_back(string(w+4,'.'));
  vs.emplace_back(string(w+4,'.'));
    
  for(int i=0;i<MAX;i++)
    for(int j=0;j<MAX;j++)
      for(int pp=0;pp<2;pp++)
        for(int pd=0;pd<4;pd++)
          for(int cd=0;cd<4;cd++)
            dp[pp][pd][cd][i][j]=INF;

  for(int pp=0;pp<2;pp++)
    for(int pd=0;pd<4;pd++)
      for(int cd=0;cd<4;cd++)
        dp[pp][pd][cd][2][2]=0;

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

  for(int i=2;i<=h+1;i++){
    for(int j=2;j<=w+1;j++){
      int cy=i,cx=j;
      for(int pp=0;pp<2;pp++){
        int py=cy-dy[pp],px=cx-dx[pp];
        for(int pd=0;pd<4;pd++){
          for(int cd=0;cd<4;cd++){
            cnt++;
            ts[py][px]=ts[cy][cx]=cnt;
            for(int k=0;k<4;k++){
              if(pd!=k) ts[py+dy[k]][px+dx[k]]=cnt;
              if(cd!=k) ts[cy+dy[k]][cx+dx[k]]=cnt;
            }
            int dist=dp[pp][pd][cd][cy][cx];
            for(int npp=0;npp<2;npp++){              
              int npd=cd,ncy=cy+dy[npp],ncx=cx+dx[npp];              
              if(ts[ncy][ncx]!=cnt) continue;
              int sum=0;
              int tmp[4]={};
              for(int k=0;k<4;k++){
                int ty=ncy+dy[k],tx=ncx+dx[k];
                if(ts[ty][tx]!=cnt&&isdigit(vs[ty][tx]))
                  tmp[k]=vs[ty][tx]-'0';
                sum+=tmp[k];                
              }
              for(int ncd=0;ncd<4;ncd++){
                int ndist=dist+sum-tmp[ncd];
                chmin(dp[npp][npd][ncd][ncy][ncx],ndist);                
              }
            }
          }
        }
      }      
    }    
  }
  
  int ans=INF;  
  for(int pp=0;pp<2;pp++)
    for(int pd=0;pd<4;pd++)
      for(int cd=0;cd<4;cd++)
        chmin(ans,dp[pp][pd][cd][h+1][w+1]);  
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 136428