akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			while(true){
				/* input */
				int n = Integer.parseInt(br.readLine());
				if(n==0){
					break;
				}

				String tag = br.readLine();
				ArrayList<Panel> ps = parseTags(tag);

				for(int i=0;i<n;i++){
					String[] str = br.readLine().split(" ");
					int x = Integer.parseInt(str[0]), y = Integer.parseInt(str[1]);

					boolean found = false;
					Panel current = ps.get(0);
					while(true){
						if(!current.point(x, y)){
							break;
						}
						found = true;
						boolean c = false;
						for(Panel child : current.children){
							if(child.point(x, y)){
								c = true;
								current = child;
								break;
							}
						}
						if(!c) break;
					}
					if(found){
						System.out.println(current.name + " " + current.children.size());
					} else {
						System.out.println("OUT OF MAIN PANEL 1");
					}
				}
			}
			br.close();
		} catch (Exception e) {
			e.printStackTrace();
		} 
	}

	static class Panel{
		public String name;
		public int x1,x2,y1,y2;
		public ArrayList<Panel> children;

		public Panel(String name, String coordinates){
			this.name = name;
			String[] c = coordinates.split(",");
			this.x1 = Integer.parseInt(c[0]);
			this.y1 = Integer.parseInt(c[1]);
			this.x2 = Integer.parseInt(c[2]);
			this.y2 = Integer.parseInt(c[3]);
			this.children = new ArrayList<Panel>();
		}

		boolean point(int x, int y){
			if(x1<=x&&x<=x2&&y1<=y&&y<=y2){
				return true;
			} else {
				return false;
			}
		}

		public void output(){
			System.out.print(this.name + ":");
			System.out.println(this.x1 + ", " + this.x2 + ", " + this.y1 + ", " + this.y2);
			System.out.print("CHILDREN:");
			for(Panel p : this.children){
				System.out.print(" " + p.name);
			}
			System.out.println();
		}

		public boolean parentOf(Panel p){
			if(this.x1<p.x1&&this.x2>p.x2&&this.y1<p.y1&&this.y2>p.y2) return true;
			return false;
		}
	}
	
	public static ArrayList<Panel> parseTags(String tags){
		Stack<Panel> stack = new Stack<Panel>();
		ArrayList<Panel> p = new ArrayList<Panel>();
		String name, coordinates;
		while(true){
			int s = 0, t = 0, nexts = 0;
			while(tags.charAt(s)!='<'&&s<=tags.length()){
				s++;
				t++;
			}
			if(s>=tags.length()) break;
			while(tags.charAt(t)!='>'&&t<tags.length()){
				t++;
			}
			name = tags.substring(s+1,t);

			nexts = t;
			if(tags.substring(t).indexOf("<")>-1){
				while(tags.charAt(nexts)!='<'){
					nexts++;
				}
			} else {
				break;
			}
			if(tags.charAt(s+1)!='/'){
				coordinates = tags.substring(t+1,nexts);
				Panel pn = new Panel(name,coordinates);
				if(stack.size()>0) stack.peek().children.add(pn);
				stack.push(pn);
				p.add(pn);
			} else {
				stack.pop();
			}
			tags = tags.substring(nexts);
		}
		return p;
	}
}

Measured memory_bytes: 17028
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    a,b,c = map(int, input().split())
    if a+b+1>=c:
        print(b+c)
    else:
        print(b+c-(c-(a+b+1)))

if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-ffloat-store")  
#pragma GCC optimize ("-fno-defer-pop")
 
typedef long long int ll; 
typedef long double ld; 
 
#define MAX 200005
#define endl endl


int main()
{
	
	std::ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	ll k;
	cin>>k;
	
	ll start = 7;
	ll ans = 1;
	map <ll,ll> mp;
	mp[start]++;
	while(start%k != 0){
		start = (start*10+7)%k;
		ans++;
		if(mp[start]!=0){
			break;
		}
		mp[start]++;
	}
	if(start%k == 0){
		cout<<ans<<endl;
	}
	else{
		cout<<-1<<endl;
	}
}


Measured memory_bytes: 66140
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main(){
    for(;;){
	int a[4],b[4];
	cin>>a[0]>>a[1]>>a[2]>>a[3];
	cin>>b[0]>>b[1]>>b[2]>>b[3];
	if(cin.eof()) return 0;
	int hit=0,blow=0;
	for(int i=0;i<=3;i++){
		if(a[i]==b[i]) hit++;
		for(int j=0;j<=3;j++){
			if(j!=i && b[j]==a[i]) blow++;
		}
	}
	cout<<hit<<" "<<blow<<endl;	
    }
}

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

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

    int n, m;
    cin >> n >> m;

    const int M = 100010;
    vector<int> G[M];
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
    }

    priority_queue<int> pq;
    int ans = 0;
    for(int i = 1; i <= m; i++){
        for(int j = 0; j < G[i].size(); j++){
            pq.push(G[i][j]);
        }

        if(!pq.empty()){
            int t = pq.top();
            pq.pop();
            ans += t;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 8988
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		if(a>b) {
			System.out.println(a-1);
		}else {
			System.out.println(a);
		}
	}

}


Measured memory_bytes: 23892
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for l in range(A+1):
    for m in range(B+1):
        for n in range(C+1):
            if 500*l+100*m+50*n ==X:
                ans += 1
print(ans)

Measured memory_bytes: 3060
n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
point = 0
#全ての組み合わせ
for i in range(n-2):
    for j in range(i+1,n-1):
        k = j + j-i
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            point += 1
print(R*G*B-point)

Measured memory_bytes: 68068
fun main(args: Array<String>) {
    var str = readLine()
    if(str != null) {
        val ary = str.split(Regex("\\s+"))
        var data: Array<Int?> = arrayOfNulls(3)
        for(i in ary.indices) {
            data[i] = ary[i].toInt()
        }
        data.sort()
        println("${data[0]} ${data[1]} ${data[2]}")
    }
 }


Measured memory_bytes: 29564
A, B, C = (input() for i in range(3))
cnt_a = 0; cnt_b = -1; cnt_c = -1
current_card = A[cnt_a]
while True:
    if current_card == "a":
        cnt_a += 1
        if cnt_a == len(A):
            print("A")
            exit()
        else:
            current_card = A[cnt_a]
    elif current_card == "b":
        cnt_b += 1
        if cnt_b == len(B):
            print("B")
            exit()
        else:
            current_card = B[cnt_b]
    elif current_card == "c":
        cnt_c += 1
        if cnt_c == len(C):
            print("C")
            exit()
        else:
            current_card = C[cnt_c]


Measured memory_bytes: 3064
#include<stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j,key;
  int A[N+1];
  scanf("%d", &n);

  for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
  
  for(i = 1;i <= n;i++){ 
    key = A[i];
    j = i -1;
    while(j >= 0 && A[j] > key){
      A[j+1] = A[j];
      j--;
      A[j + 1] = key;
    }
    trace(A, n);
  }

  return 0;
}

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

int bit(int x)
{
	int res=0;
	while (x>1)
	{
		x/=2;
		res++;
	}
	return res;
}

int main()
{
	int i,j,k,n,tab[10];
	tab[0]=1;
	for (i=1;i<=10;i++)
	 tab[i]=2*tab[i-1];
	cin>>n;
	cout<<tab[bit(n)]<<"\n";
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);


using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){
    return (a%b+b)%b;
}
ll gcd(ll a, ll b){
    return b ? gcd(b, a%b) : a;
}
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}
void Yes(){
    cout << "Yes" << endl;
}
void No(){
    cout << "No" << endl;
}
void Judge(bool b){
    b ? Yes() : No();
}
void YES(){
    cout << "YES" << endl;
}
void NO(){
    cout << "NO" << endl;
}
void JUDGE(bool b){
    b ? YES() : NO();
}
ll powmod(ll b, ll e){
    ll r = 1; while(e > 0) {if(e&1) r = (r%MOD)*(b%MOD)%MOD; b = (b%MOD)*(b%MOD)%MOD; e >>= 1;} return r;
}
double distance(ll x1, ll y1, ll x2, ll y2){
    return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

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;
}
template<typename T>
void ppp(T n){
    cout << n << endl;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {
    return s << "(" << p.first << ", " << p.second << ")";
}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    int len = v.size();
    s << '[';
    for(int i = 0; i < len; ++i) {
        s << v[i]; if(i < len-1) s << ", ";
    }
    s << ']';
    return s;
}

struct aaa {
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);
    }
} fastio;


vector<long long> calc_divisor(long long n) {
    vector<long long> res;
    for(long long i = 1LL; i*i <= n; ++i) {
        if(n % i == 0) {
            res.push_back(i);
            long long j = n / i;
            if(j != i) res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}
int main(){

    ll n;
    cin >> n;
    int ans = INF;
    for(ll x : calc_divisor(n)) {
        if(x*x > n) break;
        chmin(ans, max((int)to_string(x).size(), (int)to_string(n/x).size()));
    }
    ppp(ans);

    return 0;
}


Measured memory_bytes: 384
#include <iostream>

using namespace std;

long long a[26], sol;
string s;

long long pov2(long long x){
  /*if (x == 0 || x == 1)
    return 0;*/
  return ( (long long)x * (long long)(x+1)) / 2;
}

int main(){
  cin >> s;

  for (int i = 0; i < s.length(); i++){
    a[s[i] - 'a']++;
  }
  sol = ((long long)s.length() * (long long)(s.length() + 1)) / 2;

  for (int i = 0; i < 26; i++){
    sol -= pov2(a[i]);
  }

  cout << sol + 1 << endl;
}


Measured memory_bytes: 640
fn main() {
    let whxy = read_vec::<f64>();
    let w = whxy[0];
    let h = whxy[1];
    let x = whxy[2];
    let y = whxy[3];

    let yn = if 2.0 * x == w && 2.0 * y == h {
        1
    } else {
        0
    };
    println!("{} {}", (w * h) / 2.0, yn);
}

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()
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
    int N,M;    cin>>N>>M;
    vector<int> k(M,0);
    vector<vector<int>> s(11,vector<int> (11,0));
    for(int i=0;i<M;i++){
        cin>>k[i];
        for(int j=0;j<k[i];j++){
            cin>>s[i][j];
            s[i][j]--;
        }
    }
    vector<int> p(M,0);
    for(int i=0;i<M;i++){
        cin>>p[i];
    }
    int ans=0;
    for(int bit=0;bit<(1<<N);bit++){    //全通り
        int countp=0;
        for(int i=0;i<M;i++){   //電球i
            int counts=0;
            for(int j=0;j<k[i];j++){    //スイッチごと
                if(bit & (1<<s[i][j])) {
                    counts++;
                }
            }
            if(counts%2==p[i]){
                countp++;
            }
        }
        if(countp==M){
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
counts = Counter(A)

ans = 0
for k, v in counts.items():
    tmp = v
    if k + 1 in counts.keys():
        tmp += counts[k + 1]
    if k - 1 in counts.keys():
        tmp += counts[k - 1]
    ans = max(tmp, ans)

print(ans)


Measured memory_bytes: 84568
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, a, b; cin >> x >> a >> b;
    if (-a + b <= 0) cout << "delicious\n";
    else if (x >= -a + b) cout << "safe\n";
    else cout << "dangerous\n";
    return 0;
}


Measured memory_bytes: 256
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(min(x,k+1)):
	for j in range(y):
		if (i+1)*(j+1)>k:
			break
		for l in range(z):
			if (i+1)*(j+1)*(l+1)<=k:
				ans.append(a[i]+b[j]+c[l])
			else:
				break
ans.sort()
for i in range(k):
	print(ans[-i-1])

Measured memory_bytes: 46064
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define per(i,n) for (int i = n - 1; i >= 0; --i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> inline T intceil(T a, T b) { return (a + (b - 1)) / b; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const long long MOD = 1e9+7;
#define precout() cout << std::fixed << std::setprecision(20);
const string alphabet = "abcdefghijklmnopqrstuvwxyz";
const int dy[4] = { 0, 1, 0, -1 };
const int dx[4] = { 1, 0, -1, 0 };
static const long double pi = acos(-1.0);

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

  int a,b; cin >> a >> b;
  cout << a * b << endl;
}


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

using namespace std;

int main()
{
    long int n;
    cin>>n;
    long int x=0, y=0;
    //long long int a[20];
    for(int i=0; i<n; i++)
    {
        long long int num;
        cin>>num;
        if(num%4==0)
        {
            x++;
        }
        else if(num%2==0)
        {
            y++;
        }

    }
    if((x+y/2)>=n/2)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007;
int dx[8] = {1,0,-1,0,1,1,-1,-1};
int dy[8] = {0,1,0,-1,1,-1,1,-1};
void chmin(long long &a, long long b) { if (a > b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return (a/g*b);
}
int main() {
    char a,b;
    cin >> a >> b;
    if(a == 'H' && b == 'H'){
        cout << 'H' << endl;
    }
    if(a == 'H' && b == 'D'){
        cout << 'D' << endl;
    }
    if(a == 'D' && b == 'H'){
        cout << 'D' << endl;
    }
    if(a == 'D' && b == 'D'){
        cout << 'H' << endl;
    }
    return 0;
}


Measured memory_bytes: 384
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

win_score_each_op_hand = {"r":P, "s":R, "p":S}

ans = 0
for i in range(K):
    tmp = T[i::K]
    b_hand = T[i]
    s = 1
    cum = []

    for j in range(1,len(tmp)):
        if b_hand == tmp[j]:
            s += 1
        else:
            cum.append([s, b_hand])
            s = 1
            b_hand = tmp[j]
    cum.append([s, b_hand])

    for j in range(len(cum)):
        if cum[j][0] == 1:
            ans += win_score_each_op_hand[cum[j][1]]
        elif cum[j][0] % 2 == 1:
            ans += win_score_each_op_hand[cum[j][1]] * (-(-cum[j][0] // 2))
        else:
            ans += win_score_each_op_hand[cum[j][1]] * (cum[j][0] // 2)

print(ans)

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

const int INF = 1e9 + 7;

int dp[15][1005]; // 二次元累積和

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  string s[h];
  for ( int i = 0; i < h; i++ ) { cin >> s[i]; }

  for ( int i = 1; i <= h; i++ ) {
    for ( int j = 1; j <= w; j++ ) {
      dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
      dp[i][j] += (s[i-1][j-1]-'0');
    }
  }

  int ans = INF;
  for ( int bit = 0; bit < (1<<(h-1)); bit++ ) {
    // h方向のcut場所
    int ans_h = 0;
    vector<int> cut_h;
    cut_h.push_back(0);
    for ( int i = 0; i < h-1; i++ ) {
      if ( bit & (1<<i) ) {
        cut_h.push_back(i+1);
        ans_h++;
      }
    }
    cut_h.push_back(h);

    // w方向 貪欲
    int ans_w = 0;
    int bef_w = 0;
    bool untenable = false;
    for ( int j = 1; j <= w; j++ ) {
      bool cuted = false;

      for ( int i = 1; i < cut_h.size(); i++ ) {
        int num1 = dp[cut_h[i]][j] - dp[cut_h[i-1]][j] - dp[cut_h[i]][bef_w] + dp[cut_h[i-1]][bef_w];
        if ( num1 > k ) {
          if ( j-1 == bef_w ) {
            untenable = true;
          } else {
            cuted = true;
            bef_w = j-1;
            ans_w++;
          }
          break;
        }
      }

      if ( cuted ) { j--; continue; }
      if ( untenable ) { ans_w = INF; break; }
    }

    ans = min(ans, (ans_h+ans_w));
  }

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


Measured memory_bytes: 3684
import numpy as np
from itertools import combinations

n, m, x = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(n)]
# print(n, m, x, lis)

ans = 10 ** 9
for i in range(1, n+1):
    combination = combinations(range(n), i)
    for comb in combination:
        init = np.zeros(m+1)
        for ind in list(comb):
            init = init + np.array(lis[ind])
        if np.amin(init[1:]) >= x:
            ans = min(ans, init[0])
if ans < 10**9:
    print(int(ans))
else:
    print(-1)


Measured memory_bytes: 27176
#include <stdio.h>

int a,b,c,d;


int main(void)
{
	
	
	scanf("%d %d",&a,&b);
	
	c = a * b;
	d = 2 * a + 2 * b;
	
	printf("%d %d\n", c , d);
	
	return 0;
}

Measured memory_bytes: 596
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int n = sc.nextInt();
			String[] s = new String[n];
			for(int i = 0; i < n; i++) {
				s[i] = sc.next();
			}
			Integer[] a = new Integer[8];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < 8; j++) {
					a[j] = s[i].charAt(j) - '0';
				}
				Arrays.sort(a);
				String t = "";
				for(int j = 0; j < 8; j++) {
					t += Integer.toString(a[j]);
				}
				int min = Integer.parseInt(t);
				Arrays.sort(a, Collections.reverseOrder());
				t = "";
				for(int j = 0; j < 8; j++) {
					t += Integer.toString(a[j]);
				}
				int max = Integer.parseInt(t);
				System.out.println(max - min);
			}
		}
		sc.close();
	}
}


Measured memory_bytes: 26192
#include<bits/stdc++.h>
using namespace std;
const int N = 200100;
bool vis[N]={false};
vector<int> G[N];
int counter=0;

void dfs(int n){
	if(vis[n]) return;
	vis[n]=1;
	counter++;
	for(auto &x:G[n]) dfs(x);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m; cin >> n >> m;
	for(int i=0; i<m; ++i){
		int u, v; cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	int nax=1;
	for(int i=1; i<=n; ++i){
		counter=0;
		if(vis[i]) continue;
		dfs(i);
		nax = max(nax , counter);
	}
	cout << nax << endl;
}


Measured memory_bytes: 20928
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int e[5];
	int i;
	for(i=0;i<4;i++){
		cin>>e[i];
	}
	sort(e,e+4);
	if(e[0]==e[1]&&e[2]==e[3]){
		cout<<"yes"<<endl;
	}
	else cout<<"no"<<endl;
	
	return 0;
}


Measured memory_bytes: 3176
n = int(input())
h_list = map(int, input().split())

max_count = 0
count = 0
pre_num = 0  # 下限値-1
for h in h_list:
  if h <= pre_num:
    count += 1
    if count >= max_count:
      max_count = count
  else:
    count = 0
  pre_num = h
print(max_count)

Measured memory_bytes: 11136
/*
 * atcoder/abc111/d.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

int N;
vector<ll> X, Y;
void solve() {
  cin >> N;
  X.resize(N); Y.resize(N);
  bool match = true;
  ll first;
  loop(n,0,N) {
    cin >> X[n] >> Y[n];
    if (n>0) {
      match &= ((X[n] + Y[n] - first) % 2) == 0;
    } else {
      first = X[n] + Y[n];
    }
  }
  if (!match) {
    cout << -1 << endl;
    return;
  }

  vector<ll> ds;
  for (int i=30; i>=0; i--) ds.push_back(1<<i);
  if (first % 2 == 0) ds.push_back(1);
  int M = ds.size();

  cout << M << endl;
  for (auto &&d: ds) cout << d << " ";
  cout << endl;

  loop(n,0,N) {
    ll u = X[n] + Y[n], v = X[n] - Y[n];
    for (auto &&d: ds) {
      int u_sign = 1, v_sign = 1;
      if (u >= 0 and v >= 0) {
        cout << "R";
        u_sign = -1; v_sign = -1;
      }
      if (u >= 0 and v < 0) {
        cout << "U";
        u_sign = -1; v_sign = 1;
      }
      if (u < 0 and v < 0) {
        cout << "L";
        u_sign = 1; v_sign = 1;
      }
      if (u < 0 and v >= 0) {
        cout << "D";
        u_sign = 1; v_sign = -1;
      }
      u += u_sign * d;
      v += v_sign * d;
    }
    cout << endl;
  }
}
int main() {
  // cout.precision(15); cout << fixed;

  solve();

  return 0;
}


Measured memory_bytes: 256
n = int(input())
A = list(map(int, input().split(' ')))
c = -1
stop = True 
while stop :
    c += 1
    for i in range(n):
        if A[i]%2 != 0:
            stop = False 
            break
        else: 
            A[i] = A[i]/2 
print(c)

Measured memory_bytes: 2940
while true
    d, e = gets.chomp.split.map(&:to_i)
    break if [d, e] == [0, 0]
    min = nil
    for north in 0..d
        east = d - north
        cost = Math.sqrt(north * north + east * east)
        zure = (cost - e).abs
        min = zure if min.nil? || min > zure
    end
    puts min
end


Measured memory_bytes: 6880
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner stdin = new Scanner(System.in);
        
        int n = stdin.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = stdin.nextInt();
        }
        
        int ans = IntStream.rangeClosed(-100, 100)
                           .map(x -> Arrays.stream(a).map(v -> (x - v) * (x - v)).sum())
                           .min()
                           .getAsInt();
        System.out.println(ans);
    }
}


Measured memory_bytes: 26964
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
template<class T> using vv=vector<vector<T>>;
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int N;
int M;
int cnt[214514];
int imos[214514];
int A[214514];

int main() {
  scanf("%d%d", &N, &M);
  rep(i, N) {
    scanf("%d", &A[i]);
    cnt[A[i]]++;
  }

  reps(i, 1, N+1) {
    if (!cnt[i]) continue;
    int l = max(0, i - cnt[i]);
    imos[l]++;
    imos[i]--;
  }

  reps(i, 1, N+1) {
    imos[i] += imos[i-1];
  }

  int ans = 0;
  rep(i, N) {
    assert(imos[i] >= 0);
    if (!imos[i]) ans++;
  }

  rep(i, M) {
    int x, y;
    scanf("%d%d", &x, &y);
    --x;
    int oldc = A[x];
    int l = oldc-cnt[oldc];
    if (l >= 0) {
      imos[l]--;
      if (imos[l] == 0) ans++;
    }

    cnt[oldc]--;
    A[x] = y;
    cnt[y]++;

    int nl = y-cnt[y];
    if (nl >= 0) {
      if (imos[nl] == 0) ans--;
      imos[nl]++;
    }
    printf("%d\n", ans);
  }
}


Measured memory_bytes: 3712
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, reverse = True)
c = 0
for i in a:
    if i >= sum(a)*(1/(4*m)) :
        c += 1
if c >= m :
    print('Yes')
    
else :
    print('No')

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int c = sc.nextInt();
		int[][] spread = new int[r][c];

		for(int i=0;i<r;i++) {
			for(int j=0;j<c;j++) {
				spread[i][j]=sc.nextInt();
			}
		}

		for(int i=0;i<r;i++) {
			int sum=0;
			for(int j=0;j<c;j++) {
				sum += spread[i][j];
				System.out.print(spread[i][j]+" ");
			}
			System.out.println(sum);
		}

		int total=0;
		for(int i=0;i<c;i++) {
			int sum=0;
			for(int j=0;j<r;j++) {
				sum += spread[j][i];
			}
			System.out.print(sum+" ");
			total += sum;
		}
		System.out.println(total);
	}

}



Measured memory_bytes: 41484
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num,init) vector<ll> name((num),(init));
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define mat(name,fnum,snum,init); vector<vector<ll>> name((fnum),vector<ll>((snum),(init)));
#define debugP int debug_point; cin>>debug_point;




int main(){
    int a[2];
    int b[2];
    int c,max;
    int ans1;
    int ans2;
    cin>>a[0]>>a[1]>>b[0]>>b[1]>>c>>max;
    double ans=-100.0;
    for(int i=0;i<=30&&a[0]*i*100<max;i++){
        for(int j=0;j<=30&&(a[0]*i+a[1]*j)*100<=max;j++){
            for(int k=0;k<3000&&(k*b[0])<=c*(a[0]*i+a[1]*j)*100;k++){
                for(int l=0;l<3000&&(k*b[0]+l*b[1])<=c*(a[0]*i+a[1]*j);l++){
                   if((i==1||j==1)&&((a[0]*i+a[1]*j)*100+b[0]*k+b[1]*l)<=max){
                    if(ans<(double)(k*b[0]*100+l*b[1]*100)/(double)((a[0]*i+a[1]*j)*100+k*b[0]+l*b[1])){
                        ans=(double)(k*b[0]*100+l*b[1]*100)/(double)((a[0]*i+a[1]*j)*100+k*b[0]+l*b[1]);
                        ans1=(a[0]*i+a[1]*j)*100+k*b[0]+l*b[1];
                        ans2=k*b[0]+l*b[1];
                    }
                   }
                }

            }
        }
    }
    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in))) {

			String in = br.readLine();
			String chr[] = in.split("");
			int a = Integer.parseInt(chr[0]);
			int b = Integer.parseInt(chr[1]);
			int c = Integer.parseInt(chr[2]);
			a = (a==1?9:1);
			b = (b==1?9:1);
			c = (c==1?9:1);
			 System.out.println(a*100+b*10+c);
		}
	}
}

Measured memory_bytes: 25340
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
vector<int>G[1<<17];
vector<int>s;
bool used[1<<17];
void dfs(int u)
{
	used[u]=1;
	for(int v:G[u])if(!used[v])dfs(v);
	s.push_back(u);
}
int cnt[1<<17];
int p[1<<17];
main()
{
	cin>>n>>m;
	for(int i=1;i<n+m;i++)
	{
		int u,v;cin>>u>>v;
		G[u].push_back(v);
		cnt[v]++;
	}
	int id=-1;
	for(int i=1;i<=n;i++)if(cnt[i]==0)
	{
		id=i;
		break;
	}
	dfs(id);
	reverse(s.begin(),s.end());
	for(int a:s)
	{
		for(int u:G[a])p[u]=a;
	}
	for(int i=1;i<=n;i++)cout<<p[i]<<endl;
}


Measured memory_bytes: 13044
#!/usr/bin/env python3
import sys
import itertools
INF = float("inf")


def solve(N: int, K: int, S: str):
    s = []
    buf = 0
    mode = S[0]
    for c in S:
        if c == mode:
            buf += 1
        else:
            s.append(buf)
            buf = 1
            mode = c
    s.append(buf)

    # 1始まり1終わり
    if S[0] == "0":
        s = [0]+s
    if S[-1] == "0":
        s = s+[0]
    # print(s)

    tot = [0]+list(itertools.accumulate(s))
    w = 2*K+1
    hint = [tot[i+w]-tot[i] for i in range(0, len(tot)-w, 2)]
    if len(hint) == 0:
        print(len(S))
    else:
        print(max(hint))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, K, S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10084
nu1,nu2,x,y = gets.chomp.split(" ").map(&:to_i)
x_c = gets.chomp.split(" ").map(&:to_i)
y_c = gets.chomp.split(" ").map(&:to_i)
x_ci = x_c.sort
y_ci = y_c.sort
ans = []

if x_ci[-1] >= y_ci[0]
  puts "War"
  exit
end


for i in x_ci[-1] + 1..y_ci[0]
  ans.push(i)
end
length = ans.length
count = 0
for i in 0..length - 1
  if ans[i] > x && ans[i] <= y
    count += 1
    break
  end
end

if count != 0
  puts "No War"
else
  puts "War"
end


Measured memory_bytes: 1788
#if defined(__GNUC__)
#include <bits/stdc++.h>
#define __int32 __int32_t
// __GNUC__
#else
#include "bits/stdc++.h"
#endif
using namespace std;

#define int long long

#define itn __int32
#define REP(i, n) for(itn (i) = 0; (i) < (n); ++(i))
#define REP2(i, x, n) for(itn (i) = x; (i) < (n); ++(i))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SORT(x) std::sort(ALL(x))
#define RSORT(x) std::sort(ALL(x), greater<decltype(x)::value_type>())
#define RSORT2(x, T) std::sort(ALL(x), greater<T>())
#define REVERCE(x) std::reverce(ALL(x))
#define ACM(x, y) std::accumulate(ALL(x), y)

#define INT_POW(x, y) [](int a, int b) -> int {int c = a; REP(i, b - 1){c *= a;} return c;}(x, y)
#define INT_POWM(x, y, m) [](int a, int b, int m) -> int {int c = a; REP(i, b - 1){c *= a; c %= m;} return c;}(x, y, m)
#define FCT(x) [](int a) -> int {int r = 1; REP(i, a){r *= i;} return r;}(x)

int gcd(int a, int b) {
	if (!b) {
		return a;
	}
	
	return gcd(b, a % b);
}

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

itn main() {
	std::ios::sync_with_stdio(false);

	int n;

	cin >> n;

	if (n == 1) {
		int t;
		cin >> t;

		cout << t;
		return 0;
	}

	int t1, t2;


	cin >> t1 >> t2;
	int res = lcm(t1, t2);

	REP2(i, 2, n) {
		int t;
		cin >> t;
		res = lcm(res, t);
	}

	cout << res;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <cmath>
#include <string>
using namespace std;
int main()
{
	long long a,b,z;
	char x;
	cin>>a>>x>>b;
	if(x=='+')
	{
		cout<<a+b;
	}
	else if(x=='-'){
		cout<<a-b;
	}
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
gates = []
for i in range(m):
    gates.append(list(map(int, input().split())))
candidate = [1, n]
for gate in gates:
    if candidate[0] < gate[0]:
        candidate[0] = gate[0]
    if gate[1] < candidate[1]:
        candidate[1] = gate[1]
if (candidate[1] >= candidate[0]):
    print(candidate[1] - candidate[0] + 1)
else:
    print(0)

Measured memory_bytes: 27340
#include<iostream>
#include<cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
int const mod=1e9+7;
ll q_pow(ll x,int n){
	ll res = 1;
	while(n){
		if(n&1) res=(res*x)%mod;
		n>>=1;
		x=(x*x)%mod; 
	}
	return res;
}
int main(){
	ll N;
	scanf("%lld",&N);
	ll s=(q_pow(10,N)-2*q_pow(9,N)+q_pow(8,N)+mod*2)%mod;
	printf("%lld\n",s);
	return 0;
} 


Measured memory_bytes: 3808
N, K = map(int, input().split())
mod = 10**9+7

ans = N-K+1
print(ans)
for i in range(2, K+1):
    ans = (ans * (N-K-i+2) * (K-i+1) * pow(i * (i-1), mod-2, mod)) % mod
    print(ans)


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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    ll count = 0;
    ll prev = -1;
    cin >> N;
    rep(i, N) {
        ll temp;
        cin >> temp;
        if(temp == prev) {
            count++;
            prev = -1;
        } else {
            prev = temp;
        }
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
n = gets.to_i
b = []

for i in 0...n
  b[i] = 0
end

while gets
  a = $_.split(" ").map(&:to_i)
  if a[2] > a[3] then
    b[a[0]-1] += 3
  elsif  a[2] < a[3] then
    b[a[1]-1] += 3
  else
    b[a[0]-1] += 1
    b[a[1]-1] += 1
  end
end
c = b.sort.reverse
for i in 0...n
  p c.index(b[i]) + 1
end



Measured memory_bytes: 7036
def gi; gets.to_i end
def gs; gets.chomp end
def gli; gets.split(' ').map(&:to_i) end
def d(n); Math.log10(n).to_i + 1 end
class Integer
  # 約数の組み合わせを列挙する
  def divisor_combinations
    (1..Math.sqrt(self).to_i).
      select { |i| self % i == 0 }.
      map { |i| [i, self / i] }
  end
end

N = gi
S = gs
puts S.scan(/ABC/).length


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll x;
	cin>>x;
	ll n;
	rep(i,1e9){
		if(i*(i+1)>=2*x){
			n=i;
			break;
		}
	}
	ll y=n*(n+1)/2-x;
	if(y<=n){
		cout<<n<<endl;
	}else{
		cout<<y<<endl;
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
	map<int,int> even,odd; //mapで各数列での要素の出現数を記録する
	for(int i = 0; i < n; i++){
		if(i%2==0) odd[v[i]]++;
		else even[v[i]]++;
	}

	int even_1=0,even_2=0,odd_1=0,odd_2=0;
	int e1=0,e2=0,o1=0,o2=0;
	int cnt = 0;
	for(auto itr = even.begin();  itr != even.end() ; ++itr){
		if(itr->second > cnt){
			cnt = itr->second;
			even_1 = itr->first;
		}
	}
	e1 = cnt;
	cnt = 0;
	for(auto itr = even.begin();  itr != even.end() ; ++itr){
		if(itr->second > cnt && itr->first != even_1){
			cnt = itr->second;
			even_2 = itr->first;
		}
	}
	e2 = cnt;

	cnt = 0;
	for(auto itr = odd.begin();  itr != odd.end() ; ++itr){
		if(itr->second > cnt){
			cnt = itr->second;
			odd_1 = itr->first;
		}
	}
	o1= cnt;
	cnt = 0;
	for(auto itr = odd.begin();  itr != odd.end() ; ++itr){
		if(itr->second > cnt && itr->first != odd_1){
			cnt = itr->second;
			odd_2 = itr->first;
		}
	}
	o2=cnt;

	if(even_1 == odd_1){
		cout << min(n-e1-o2, n-e2-o1) << endl;
	}else{
		cout << n-e1-o1 << endl;
	}

	return 0;
}

Measured memory_bytes: 8168
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main()
{
  int n, k;
  cin >> n >> k;
  vector<ll> h(n);
  for (auto &e : h)
    cin >> e;

  sort(h.begin(), h.end());
  ll nmin = 1e14;
  for (int i = 0; i < n - k + 1; ++i)
  {
    nmin = min(nmin, h[i + k - 1] - h[i]);
  }
  cout << nmin << endl;

  return 0;
}


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

long long int final_ans=0;

void func(string &S, int k, long long int ans, long long int sum){
  if(k==S.size()-1){
    final_ans += ans+sum+S[k]-'0';
    return;
  }
  // S[k]の直後に'+'を挿入する
  func(S,k+1,ans+sum+S[k]-'0',0);

  // S[k]の直後に'+'を挿入しない
  sum = (sum+S[k]-'0')*10;
  func(S,k+1,ans,sum);

  return;
}

int main(){
  string S; cin >>S;
  func(S,0,0,0);
  cout << final_ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdlib>
#include <cmath>

using namespace std;

int main(){
  int A,B;
  cin >> A >> B;
  if(A%3==0 || B%3==0 || (A+B)%3==0)  cout << "Possible" << endl;
  else  cout << "Impossible" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int NIL = -1;

struct Node {
    int parent;     //・節点 u の親ノード
    int left;       //・節点 u の最も左の子(left)
    int right;      //・節点 u のすぐ右の兄弟(right)
    int end;        //・節点 u 子の一番右の兄弟
}node;

vector<struct Node> T;  // ノード入れ

void GetChildren(int u,vector<vector<int>> &CL){    // CLが子のリスト
    int c;
    if(T[u].left != NIL)c = T[u].left;
    else return;
    while(c != NIL){
        CL[u].push_back(c); 
        c = T[c].right;
    }
    return;
}

///////////////////////////////// O(N)　のはず

int main(){
    int N,Q;cin >> N >> Q;
    T.resize(N+1);

    rep(i,N+1)T[i].parent = T[i].left = T[i].right = NIL; // 初期化

    int tmp1,tmp2; // tmp1 は親、tmp2　は追加される子

    rep(i,N-1){     //  ノードの入力
        cin >> tmp1 >> tmp2;
        if(T[tmp1].left == NIL)T[tmp1].left = T[tmp1].end = tmp2;
        else{
            int c = T[tmp1].end;
            T[c].right = tmp2;
            T[tmp1].end = tmp2;
        }
        T[tmp2].parent = tmp1;  //　親登録
    }

    vector<vector<int>> CL; //子リスト
    CL.resize(N+1);
    for(int i = 1;i < N+1;i++)GetChildren(i,CL);  //子リスト取得


    vector<LL> ct(N+1);   // カウンター配列

    int p,x;
    rep(i,Q){
        cin >> p >> x;
        ct[p] += x;
    }
    for(int i = 2;i < N+1;i++){
        ct[i] += ct[T[i].parent];
    }

    rep(i,N)cout << ct[i+1] << " ";

} 


//　答えはあってるけど　TLE
/*
    for(int i = 1;i < N+1;i++){
        for(auto j : CL[i]){
            ct[j] += ct[i];
        }
    }
*/

/*
            while(true){
                if(T[c].right == NIL){
                    T[c].right = tmp2;
                    break;
                }
                else{
                    c = T[c].right;
                }
            }
*/

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

int main() {
    long long int H,W;
    cin >> H;
    cin >> W;

    if ( H == 1 || W == 1 ) cout << 1;
    else if ( H % 2 == 0 ) cout << ( H / 2 ) * W;
    else {
        cout << ( (H+1) / 2 ) * W - ( W / 2 );

    }

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 10000000
int p[MAX + 1], pq[1000];

int main(){
  int n, i, j;
  p[0] = p[1] = 1;
  for(i = 2; i <= MAX / 2; ++i)
    if(p[i] == 0)
      for(j = i + i; j <= MAX; j += i)
	p[j] = 1;
  j = 0;
  for(i = 0; i < 1000; ++i) pq[i] = MAX + 1;
  for(i = 0; i <= MAX; ++i)
    if(p[i] == 0 && p[i + 2] == 0 && p[i + 6] == 0 && p[i + 8] == 0){
      pq[j] = i + 8;
      j++;
    }
  while(scanf("%d", &n) && n){
    for(i = 999; i >= 0; i--){
      if(pq[i] <= n){
	printf("%d\n", pq[i]);
	break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 39664
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <cstdlib>
#include <map>
#include <ctime>
#include <set>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <sstream>
#include <cstdio>
#include <bitset>
#include <iomanip>

using namespace std;

// long long dp[123456];
// long long h[12345];

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

    long long n;
    cin >> n;

    vector <long long> h(n);

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }

    vector <long long> dp(n, 0);

    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);

    for (int i = 2; i < n; ++i) {
        dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
                    dp[i - 2] + abs(h[i] - h[i - 2]));
    }

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

    return 0;
}

Measured memory_bytes: 1920
from itertools import permutations as perm
man = lambda a,b:abs(a[0]-b[0])+abs(a[1]-b[1])
N,M = map(int, input().split())

XY = []
for i in range(N):
    XY.append(list(map(int, input().split())))

inf = float('INF')
ans_lst = [[inf, 0] for i in range(N)]
for i in range(M):
    c,d = map(int, input().split())
    for j in range(N):
        if ans_lst[j][0] > man(XY[j], [c,d]):
            ans_lst[j] = [man(XY[j], [c,d]), i+1]
for i in range(N):
    print(ans_lst[i][1])


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

int main() {
    string reversi;
    cin >> reversi;
    int count = 0;
    char now_color = reversi[0];
    for (int i = 0; i < reversi.length(); i++) {
        if (now_color != reversi[i]) {
            count++;
            now_color = reversi[i];
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
long long dp[450][450];
int n;
long long fun(int a,int  b)
{
	if(a == b)return 1;
	else return 2;
}
int main()
{
		
	cin >> n;
	vector<long long > vec(n);
	long long po = 0;
	for(auto &a : vec)
		cin >> a, po += a;
	
	for(int x =0; x<n; x++)
	{
		for(int y =0; y<n; y++)
			dp[x][y] = 6e18;
	}
	for(int x =0; x<n; x++)
		dp[x][x] = vec[x];
	long long result = 6e18;
	for(int x = 1; x<n; x++)
	{
		for(int y = 0; y<n; y++)
		{
			
			for(int z= 0; z<x; z++)
			{
				dp[y][(y+x) % n] = min(dp[y][(z+y)%n]  + dp[(y+z+1)%n][(x+y) % n] , dp[y][(y+x)%n] );
			 }
			
			long long h = 0;
			if(y +x < n)
			{
				for(int g = y; g<= x + y; g++)
					h+= vec[g];
			}
			else
			{
				for(int g = y; g<= n-1; g++)
					h+= vec[g];
				for(int g = 0; g<= (x + y)%n; g++)
					h+= vec[g];
			}
			dp[y][(y+x)%n] += h ;

		}
	}
	result = dp[0][n-1];
	
	cout << result - po << "\n";
	
}


Measured memory_bytes: 1664
#define _USE_MATH_DEFINES

#include <bits/stdc++.h>
using namespace std;
using i32 = int; using i64 = long long int; using f64 = double; using str = string;
template <typename T> using vec = vector<T>;
template <typename T> using heap = priority_queue<T>;
#define times(n, i) for (i32 i = 0; i < (n); ++i)
#define range(a, b, i) for (i32 i = (a); i < (b); ++i)
#define upto(a, b, i) for (i32 i = (a); i <= (b); ++i)
#define downto(a, b, i) for (i32 i = (a); i >= (b); --i)
#define all(xs) (xs).begin(), (xs).end()
#define sortall(xs) sort(all(xs))
#define reverseall(xs) reverse(all(xs))
#define uniqueall(xs) (xs).erase(unique(all(xs)), (xs).end())
#define even(x) (((x) & 1) == 0)
#define odd(x) (((x) & 1) == 1)
#define append emplace_back
#define findge lower_bound
#define findgt upper_bound
const i64 MOD = 1000000007;
const f64 EPS = 1e-10;

i64 h, w;
str s[500];
bool a[500][500], b[500][500];

i32 main()
{
	cin >> h >> w;
	times(h, i) {
		cin >> s[i];
	}
	times(h, i) {
		range(1, w-1, j) {
			if (even(i)) {
				a[i][j] = true;
			}
			else {
				b[i][j] = true;
			}
		}
		a[i][0] = true;
		b[i][w-1] = true;
	}
	times(h, i) {
		times(w, j) {
			if (s[i][j] == '#') {
				a[i][j] = b[i][j] = true;
			}
		}
	}
	times(h, i) {
		times(w, j) {
			cout << (a[i][j] ? '#' : '.');
		}
		cout << endl;
	}
	cout << endl;
	times(h, i) {
		times(w, j) {
			cout << (b[i][j] ? '#' : '.');
		}
		cout << endl;
	}
    return 0;
}

Measured memory_bytes: 1536