akhauriyash/Code-Regression huggingface dataset:
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (ql:quickload '(:cl-debug-print :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)
#-swank (disable-debugger) ; for CS Academy

;; BEGIN_INSERTED_CONTENTS
(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare #.OPT
           #-swank (sb-kernel:ansi-stream in))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (sb-impl::ansi-stream-read-byte in nil #.(char-code #\Nul) nil))))
    (let* ((result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul.")))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (* 10 (the (integer 0 #.(floor most-positive-fixnum 10)) result))))
              (return result)))))))

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

;; Body

(define-modify-macro minf (new-value)
  (lambda (x y) (min x y)))

(defun main ()
  (declare #.OPT)
  (let* ((n (read))
         (k (read))
         (hs (make-array n :element-type '(unsigned-byte 32)))
         (dp (make-array n :element-type '(unsigned-byte 32) :initial-element #xffffffff)))
    (declare ((unsigned-byte 31) n k))
    (setf (aref dp 0) 0)
    (dotimes (i n)
      (setf (aref hs i) (read-fixnum)))
    (dotimes (i n)
      (let ((h (aref hs i))
            (d (aref dp i)))
        (loop for dest from (+ i 1) to (min (+ i k) (- n 1))
              do (minf (aref dp dest) (+ d (abs (- h (aref hs dest))))))))
    (println (aref dp (- n 1)))))

#-swank (main)


Measured memory_bytes: 17380
import Control.Applicative

areaAndCirc :: Num a => [a] -> [a]
areaAndCirc [a, b] = [a*b, 2 * (a + b)]

getList :: Read a => IO [a]
getList = map read . words <$> getLine

main = putStrLn . unwords . map show . areaAndCirc . map read . words =<< getLine

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

using namespace std;
using ll = long long;

int n, m;
vector<int> s, c;

bool ok(string str){
    if(str.size() != n) return false;
    for(int i = 0; i < m; i++){
        if(str[s[i]] != (char)(c[i]+'0')) return false;
    }
    return true;
}

string solve(){
    for (int i = 0; i <= 999; i++)
    {
        stringstream iss; iss << i;
        string str = iss.str();
        if(ok(str)) return str;
    }
    return "-1";
}

int main(){
    cin >> n >> m;
    s.resize(m); c.resize(m);
    for (int i = 0; i < m; i++)
    {
        cin >> s[i] >> c[i];
        s[i]--;
    }
    cout << solve() << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;
#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define pb push_back
#define re(x) memset(x, 0, sizeof x)
#define int long long
template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}
template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}
const int N = 100010;
//LL n, Q, m;
//LL len[N], val[N], ans[N];
//void calc(LL x, LL v) {
//	if(!x) return;
//	int p = upper_bound(len + 1, len + 1 + m, x) - len - 1;
//	if(!p) { ans[1] += v, ans[x + 1] -= v;}
//	else {
//		val[p] += (x / len[p]) * v;
//		calc(x % len[p], v);
//	}
//}
int q,n,len[N],val[N],ans[N],m;
void doit(int x,int v) {
  if (!x) return;
  int t = upper_bound(len+1,len+m+1,x) - len - 1;
  if (t == 0) ans[1] += v, ans[x+1] -= v;
  else {
    val[t] += (x / len[t]) * v;
    doit(x % len[t],v);
  }
}
signed main() {
int x;
  scanf("%lld%lld",&n,&q);
  len[++m] = n;
  for (int i = 1 ; i <= q ; ++ i) {
    scanf("%lld",&x);
    while (m && len[m] >= x) -- m;
    len[++m] = x;
  }
  val[m] = 1;
  for (int i = m ; i >= 2 ; -- i) {
    val[i-1] += val[i] * (len[i] / len[i-1]);
    doit(len[i] % len[i-1],val[i]);
  }
  ans[1] += val[1];
  ans[len[1]+1] -= val[1];
  for (int i = 2 ; i <= n ; ++ i)
    ans[i] += ans[i-1];
  for (int i = 1 ; i <= n ; ++ i)
    printf("%lld\n",ans[i]);
  return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
	int N;
	cin >> N;
	int num = N;
	int sum = 0;
	while(num > 0){
		sum += num % 10;
		num /= 10;
	}
	if(N % sum == 0) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

int main(){
    int n,c,ans=0;
    cin >> n;
    vector<int> v(n);
    for(int i=0;i<n;i++) cin >> v[i];
    for(int i=0;i<n;i++){
         cin >> c;
         if(v[i]-c>0)    ans+=(v[i]-c);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
int dp[N];
int ksm(int x, int y){
    int ans = 1;
    while (y){
        if (y&1) ans = 1ll*ans*x%mod;
        x = 1ll*x*x%mod;
        y >>= 1;
    }
    return ans;
}
int main(void){
    IOS;
    int n, k; cin >> n >> k;
    int ans = 0;
    for (int i = k; i >= 1; --i){
        dp[i] = ksm(k/i, n);
        for (int j = 2*i; j <= k; j += i){
            dp[i] = ((dp[i]-dp[j])%mod+mod)%mod;
        }
        ans = (1ll*ans+1ll*i*dp[i])%mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    ll n;cin>>n;
    vector<ll> a(n),b(n),A,B;
    rep(i,n) cin>>a[i]>>b[i];
    vector<pair<ll,int>> p(n);
    rep(i,n) p[i]={a[i]+b[i],i};
    sort(p.rbegin(),p.rend());
    int tmp=0;
    while(true){
        A.push_back(p[tmp].second);tmp++;
        if(tmp==n)break;
        B.push_back(p[tmp].second);tmp++;
        if(tmp==n)break;
    }
    ll res=0;
    rep(i,A.size())res+=a[A[i]];
    rep(i,B.size())res-=b[B[i]];
    cout<<res<<endl;
}


Measured memory_bytes: 7364
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define repo(i,N) for(int i = 1; i < (N); i++)
//#define int long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//#define num 1000000007
#define pi acos(-1.0)
//cout << fixed << setprecision (10);   小数点以下１０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//string s = to_string(int数);
//int n = stoi(string文字列);

int main() {
  string s;
  cin >>s;
  
  cout << ((s[0]==s[1] && s[1]!=s[2] && s[2]==s[3]) ||
           (s[0]==s[2] && s[2]!=s[1] && s[1]==s[3]) ||
           (s[0]==s[3] && s[1]!=s[3] && s[2]==s[1]) ?"Yes":"No") << endl;
  
  
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N, K;
  while (cin >> N >> K) {
    if (K == 1) {
      cout << 0 << endl;
      continue;
    }
    int mn = 1;
    int mx = N - (K - 1);
    int res = mx - mn;
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
int n;
unsigned long long ans = 0;

int main() {
    scanf("%d", &n);
    for (int j = 1; j <= n; ++j) {
        int k = n / j;
        ans += (long long)k * (k + 1) * j / 2;
    }
    printf("%llu\n", ans);
    return 0;
}


Measured memory_bytes: 3784
k = int(input())
candili = []
for i in range(1, 1000):
    candili.append(i)

tmpli = []
for i in candili:
    for j in range(1, 15):
        tmpli.append(int(str(i) + "9" * j))
tmpli = list(set(tmpli))

tmp2li = []
for i in tmpli:
    if i <= 10 ** 15:
        tmp2li.append(i)
candili += tmp2li
candili = list(set(candili))
candili.sort()

def S(n):
    return sum(int(i) for i in str(n))

conli = []

for i in candili:
    conli.append(i/S(i))

ansli = []
for i in range(len(conli)):
    for j in range(i, len(conli)):
        if conli[i] > conli[j]:
            break
    else:
        ansli.append(candili[i])

for i in range(k):
    print(ansli[i])

Measured memory_bytes: 44504
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

int main(){
  string s;
  cin >> s;

  int F, E;

  for(int i=0; i<s.size(); ++i){
    if(s[i] == 'A'){
      F = i;
      break;
    }
  }

  for(int i=s.size(); i>-1; --i){
    if(s[i] == 'Z'){
      E = i;
      break;
    }
  }
  cout << E-F+1;

}

Measured memory_bytes: 640
import itertools
import math

N = int(input())
P = int(''.join(input().split()))
Q = int(''.join(input().split()))

N_list = []
for i in itertools.permutations(range(1,N+1)):
    N_list.append(int(''.join([str(x) for x in i])))

pointer1 = 0
pointer2 = 0

for i,x in enumerate(N_list):
  if x == P:
    pointer1 = i
  if x == Q:
    pointer2 = i
    
print(abs(pointer1 - pointer2))

Measured memory_bytes: 4752
n, k = map(int,input().split())
s = input()
sakidata = [1]
lastdata = [0]
#data... わける.

mode = False
for cnt, i in enumerate(s):
	if mode:
		if i == "0":
			lastdata.append(cnt)
			mode = False
	else:
		if i == "1":
			sakidata.append(cnt+1)
			mode = True

if mode:
	lastdata.append(cnt+1)

sakidata.append(n)
lastdata.append(n)

ans = 0

#print(sakidata)
#print(lastdata)

for i in range(len(lastdata)-k):
	targ = lastdata[i+k]-sakidata[i]+1
	ans = max(targ, ans)
	
if len(lastdata)-k < 1:
	ans = n

print(ans)

Measured memory_bytes: 13200
H,W=map(int,input().split())
S=[]
for i in range(H):
    S.append(list(input()))
for h in range(H):
    for w in range(W):
        #print('S[h][w] ',S[h][w])
        if S[h][w]=='#':
            continue
        x1 = max(0,w-1)
        x2 = min(W,w+2)
        y1 = max(0,h-1)
        y2 = min(H,h+2)
        cnt=0
        for h2 in range(y1,y2):
            for w2 in range(x1,x2):
                if S[h2][w2]=='#':
                    cnt+=1
        #print(h,w,cnt)
        S[h][w]=str(cnt)
for i in range(H):
    print(''.join(S[i]))


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

#define MAX 100000

int main() {
	int N, K;
	int x[MAX];
	int ans = INT_MAX;
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> x[i];
	}
	for (int i = 0; i < N - K + 1; i++) {
		int d = min(abs(x[i + K - 1]) + x[i + K - 1] - x[i],
					abs(x[i]) + x[i + K - 1] - x[i]);
		ans = min(ans, d);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
'use strict';
(function(stdin) {
  //declare function
  function countSumX(array) {
    var n = array[0];
    var x = array[1];
    var result = 0;
    for (var max = n; max > parseInt(x / 3); max--) {
      for (var min = 1; min < max - 1; min++) {
        var mid = x - max - min;
        if (mid > min && mid < max) {
          result += 1;
        }
      }
    }
    return result;
  }
  //declare variable
  var inputs = stdin.toString().trim().split('\n');
  var cloneInputs = inputs.slice(0, inputs.indexOf('0 0'));
  cloneInputs = cloneInputs.map(function(v) {
    return v.split(' ').map(Number);
  });
  //main
  console.log(cloneInputs.map(countSumX).join('\n'));

  //display
  // console.log(cloneInputs);
})(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 15800
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void)
{
	int d,t,s;
	scanf("%d %d %d",&d,&t,&s);
	if(d%s==0){
		if(d/s<=t)	printf("Yes\n");
		else	printf("No\n");
	}
	else{
		if(d/s+1<=t)	printf("Yes\n");
		else	printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 1648
import java.util.*;

class Main {
public static void main(String[] args){

Scanner sc = new Scanner(System.in);
ArrayList<Integer> li = new ArrayList<>();
li.add(sc.nextInt());
li.add(sc.nextInt());
li.add(sc.nextInt());
Collections.sort(li);
int total = li.get(0) + li.get(1);
System.out.println(total);


}
}

Measured memory_bytes: 22736
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	int n,a[22],b,c[22],i,ans=0;
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a[i]; --a[i];
	}
	for(i=0; i<n; ++i){
		cin >> b;
		ans += b;
	}
	for(i=1; i<n; ++i){
		cin >> c[i];
	}
	for(i=1; i<n; ++i){
		if(a[i]-a[i-1]==1){
			ans += c[a[i]];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    int x;
    int y;
    int S;
    int M;
    scanf("%d %d", &x, &y);
    S = x*y;
    M = 2*x + 2*y;
    printf("%d %d\n",S,M);
    return 0;
}



Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
typedef long long ll;
//isPrime
//modpow modinv
long long int modfact(long long int n,long long int mod){
  if(n){
    return n*modfact(n-1,mod)%mod;
  }else{
    return 1;
  }

}
int main() {
  cout << fixed << setprecision(10);
  ll n;
  cin >> n;
  cout << modfact(n,MOD) << endl; 
}



Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

pair<ll,ll> rec(ll x,ll pre,vector<vector<ll>> &edge){
    if(edge[x].size() == 0 || (edge[x].size() == 1 && pre != -1)){
        return make_pair(1,1);
    }
    pair<ll,ll> ret = make_pair(1,1);
    for(int i = 0; i < edge[x].size(); i++){
        if(edge[x][i] != pre){
            auto tmp = rec(edge[x][i],x,edge);
            ret.first *= ((tmp.first + tmp.second)%MOD);
            ret.first %= MOD;
            ret.second *= (tmp.first);
            ret.second %= MOD;           
        }
    }
    return ret;
}

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

    vector<vector<ll>> edge(n+1);
    for(int i = 0; i < n-1; i++){
        ll x,y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    auto ans = rec(1,-1,edge);
    cout << (ans.first + ans.second)%MOD << endl;
    
    return 0;
}

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

int main(){
    ll N ;
    cin >> N ;
    for(ll i = 1 ; i < 3501 ; i++ ){
        for(ll j = 1 ; j < 3501 ; j++ ){
        if( (4*i*j-N*i-N*j) > 0 ){
            if( (N*i*j)%(4*i*j-N*i-N*j) == 0 )
        {
            ll ans = (N*i*j)/(4*i*j-N*i-N*j)  ;
            cout <<  i << ' ' <<  j << ' ' << ans  ;
            return 0 ;
        }
    }
        }
    }     
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <functional>
#include <map>
#include <set>
#include <cmath>
#include <string>
#define SIZE 200005
#define INF 1000000005LL

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

int n;

int main()
{
	scanf("%d",&n);
	int m=n;
	int ans=0;
	while(m>0){
		ans += (m%10);
		m = m/10;
	}
	if(n%ans==0)printf("Yes\n");
	else printf("No\n");
	return 0;
}


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

int main(){
    int h,w; cin>>h>>w;
    vector<vector<int>> c(10,vector<int>(10));
    rep(i,10){
        rep(j,10){
            cin>>c[i][j];
        }
    }
    vector<int> num(10);
    rep(i,h){
        rep(j,w){
            int a; cin>>a;
            if(a>=0) num[a]++;
        }
    }
    bool x=true;
    while(x){
        x=false;
        rep(i,10){
            rep(j,10){
                if(i==j)continue;
                if(i==1 || j==1)continue;
                if(c[i][j]+c[j][1]<c[i][1]){
                    c[i][1]=c[i][j]+c[j][1];
                    x=true;
                }
            }
        }
    }
    ll ans=0;
    rep(i,10){
        ans+=c[i][1]*num[i];
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m;
char jz[101][101];
void dfs(int y,int x)
{
    if(jz[y][x]=='0')
        for(int dy=-1;dy<=1;dy++)
            for(int dx=-1;dx<=1;dx++)
			{
                int nx=dx+x,ny=dy+y;
                if(0<=ny&&ny<n&&0<=nx&&nx<m&&jz[ny][nx]=='#')
                	jz[y][x]+=1;
            }
    return;
} 
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
		{
            cin>>jz[i][j];
            if(jz[i][j]=='.')
            	jz[i][j]='0';
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            dfs(i,j);
    for(int i=0;i<n;i++)
	{
        for(int j=0;j<m;j++)
            cout<<jz[i][j];
        cout<<endl;
    }
    return 0;
}

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

#define debug(x)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sq(x) ((x) * (x))
#define PRECISION 30

using namespace std;

template<class T> int check_mod(T a, T b) { return (a % b) ? 1 : 0; }
template<class T> void maxi(T &a, T b) { a = max(a, b); return; }
template<class T> void mini(T &a, T b) { a = min(a, b); return; }

bool is_prime(int a) { if (a == 2) return true; if (!(a & 1) || a == 1) return false; for (int i = 3; i * i <= a; i += 2) if (!(a % i)) return false; return true; }
bool is_prime(ll a) { if (a == 2) return true; if (!(a & 1) || a == 1) return false; for (ll i = 3; i * i <= a; i += 2) if (!(a % i)) return false; return true; }
bool is_palindrome(string s) { int len = (int)s.length(); int mid = len >> 1; for (int i = 0; i < mid; i++) if (s[i] != s[len - i - 1]) return false; return true; }
int gcd(int a, int b) { while (b) { int mod = a % b; a = b; b = mod; } return a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int binpow(int a, int b) { int res = 1; while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; }
int binpow(int a, int b, int MODULO) { int res = 1; while (b) { if (b & 1) { res *= a; res %= MODULO; } a *= a;  a %= MODULO; b >>= 1; } return res; }
ll gcd(ll a, ll b) { while (b) { ll mod = a % b; a = b; b = mod; } return a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll binpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll MODULO) { ll res = 1; while (b) { if (b & 1) { res *= a; res %= MODULO; } a *= a;  a %= MODULO; b >>= 1; } return res; }
string binary(int N) { if (!N) return "0"; string bin = ""; while (N) { bin += '0' + (N & 1); N >>= 1; } reverse(all(bin)); return bin; }
string binary(ll N) { if (!N) return "0"; string bin = ""; while (N) { bin += '0' + (N & 1); N >>= 1; } reverse(all(bin)); return bin; }
           
const int INF = 2147483547;           // Max int value - 100 so it will not overflow
const int MODULO = 1000000007;
const int _MODULO = 998244353;
const ll INF64 = 9223372036854775707; // Max long long value - 100 so it will not overflow
const ll MODULO64 = 1000000007;
const ll _MODULO64 = 998244353;
const double epsilon = 10e-6;
const double PI = acos(-1);

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	auto t1 = chrono::high_resolution_clock::now();
    #define debug(x) cerr << #x << " = " << x << "\n";                        
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int h, a;
	cin >> h >> a;
	cout << (h + a - 1) / a << '\n';
#ifdef LOCAL
	auto t2 = chrono::high_resolution_clock::now();
	cerr << "Running time " << chrono::duration_cast<chrono::nanoseconds>(t2 - t1).count() << " nanoseconds" << endl;
#endif
	return 0;
}

Measured memory_bytes: 892
//
// Created by yjq on 2019/11/7.
//
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i <= b; i++)
const int N = 100+100;
using namespace std;

int a[N],n,maxx,minn,sum[N];

int main(){
    scanf("%d",&n);
    maxx = 0, minn = n+1;
    rep(i,1,n) scanf("%d",&a[i]), maxx = max(maxx,a[i]), minn = min(minn,a[i]), sum[a[i]]++;
    int tp = (maxx+1)/2;
    if(minn < tp) printf("Impossible\n");
    else{
        int jud = 1;
        if(maxx%2 == 0 && sum[tp] != 1) jud = 0;
        if(maxx%2 == 1 && sum[tp] != 2) jud = 0;
        if(maxx == 1 && n != 2) jud = 0;
        rep(i,tp+1,maxx){
            if(sum[i] < 2) jud = 0;
        }
        if(jud) printf("Possible\n");
        else printf("Impossible\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin>>S;
  int count = 0;
  for(int i=0;i<3;i++){
    if(S.at(i)==S.at(i+1)){
      count++;
    }
  }
  
  if(count>=1){
    cout<<"Bad"<<endl;
  }
  else{
    cout<<"Good"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;



void main() {
    double a, b, x;
    scan(a, b, x);

    double ok = 0, ng = 90;

    bool check(double t) {
        auto r = DtR(t);
        if (b / tan(r) <= a) {
            return a * b^^2 / tan(r) / 2 >= x;
        }
        else {
            return a^^2 * b - a^^3 * tan(r) / 2 >= x;
        }
    }

    foreach (_ ; 0 .. 200) {
        auto mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }

    writefln("%.12f", ok);
}

double DtR(double t) {
    return t / 180 * PI;
}

void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x > arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;
    foreach (arg; args) if (x < arg) {
        x = arg;
        isChanged = true;
    }
    return isChanged;
}

void yes(bool ok, string y = "Yes", string n = "No") {
    return writeln(ok ? y : n);
}

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

int func(int n) {
        if (n < 10) return n;
        return func(n/10) + n % 10;
    }

int main() {
    int n;
    cin >> n;
    
    int s = func(n);
    
    if (n % s == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner

object Main extends App{
  val sc = new Scanner(System.in)

  val n = sc.nextInt
  val m = sc.nextInt

  val lrSeq = Seq.fill(m)((sc.nextInt, sc.nextInt))

  val lM = lrSeq.map(_._1).max
  val rm = lrSeq.map(_._2).min

  val res =
    if(lM > rm) 0
    else rm - lM + 1

  println(res)
}


Measured memory_bytes: 79724
#include <bits/stdc++.h>
using namespace std;
int main () {
    int a, b, c;
    cin >> a >> b >> c;
    int d;
    cin >> d;
    if (abs(a-c) <= d || (abs(a-b) <= d && abs(b-c) <= d)) {
        puts("Yes");
    }
    else {
        puts("No");
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i < n; i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define P pair<int, int>
typedef long long ll;
const ll mod = 1e9+7;

//繰り返し自乗法による累乗計算
//a**n
ll pow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = pow(a, n/2);
    return res * res;
  }
  return a * pow(a, n-1);
}
//繰り返し自乗法によるmod累乗計算
//a**n (mod)
ll modpow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = modpow(a, n/2);
    return res * res % mod;
  }
  return a * modpow(a, n-1) % mod;
}
//組み合わせ
//nCa
ll com(ll n, ll a){
  ll x = 1, y = 1;
  rep(i,a){
    x *= n-i;
    y *= i+1;
  }
  ll res = x / y;
  return res;
}
//組み合わせ(mod)
//nCa (mod)
ll modcom(ll n, ll a){
  ll x = 1, y = 1;
  rep(i, a){
    x = x * (n-i) % mod;
    y = y * (i+1) % mod;
  }
  ll ans = x * modpow(y, mod-2) % mod;
  return ans;
}
//gcd 最大公約数
ll gcd(ll x, ll y){
  if(x % y == 0) return y;
  return gcd(y, x%y);
}
//lcm 最小公倍数
ll lcm(ll x, ll y){
  return x * y / gcd(x, y);
}
//ngcd n個の最大公約数
ll ngcd(vector<ll> a){
  ll res;
  res = a[0];
  for(ll i = 1; i < a.size() && res != 1; i++) {
    res = gcd(a[i], res);
  }
  return res;
}
//nlcm n個の最小公倍数
ll nlcm(vector<ll> a) {
  ll res;
  res = a[0];
  for (ll i = 1; i < a.size(); i++) {
    res = lcm(res, a[i]);
  }
  return res;
}
// 素数判定
bool isprime(ll x){
  ll i;
  if(x < 2) return false;
  else if(x == 2) return true;
  if(x % 2 == 0) return false;
  for(i = 3; i*i <= x; i += 2){
    if(x % i == 0) return false;
  }
  return true;
}
// 桁和
ll digsum(ll x){
  ll res = 0;
  while(x > 0){
    res += x % 10;
    x /= 10;
  }
  return res;
}


int main(){
  int x, y, z;
  cin >> x >> y >> z;
  REP(i, x){
    if(y*i + z*(i+1) > x){
      cout << i-1 << endl;
      return 0;
    }
  }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=2147483647;
int n,dat[400010];
void init(int n_){
  n=1;
  while(n<n_){
    n=n*2;
  }
  for(int i=0;i<2*n-1;i++){
    dat[i]=INF;
  }
}
void update(int x,int a){
  x+=(n-1);
  dat[x]=a;
  while(x>0){
    x=(x-1)/2;
    dat[x]=min(dat[2*x+1],dat[2*x+2]);
  }
}
int query(int a,int b,int k=0,int l=0,int r=n){
  if(r<=a || b<=l){
    return INF;
  }
  if(a<=l && r<=b){
    return dat[k];
  }
  else{
    int vl=query(a,b,2*k+1,l,(l+r)/2);
    int vr=query(a,b,2*k+2,(l+r)/2,r);
    return min(vl,vr);
  }
}
void set(int i,int x){
  dat[i+n-1]=x;
}
void build(){
  for(int k=n-2;k>=0;k++){
    dat[k]=min(dat[2*k+1],dat[2*k+2]);
  }
}
int main(){
  int i,n,q,a,b,c;
  cin >> n >> q;
  init(n);
  for(i=0;i<q;i++){
    cin >> a >> b >> c;
    if(a==0){
      update(b,c);
    }
    else{
      cout << query(b,c+1) << endl;
    }
  }
}


Measured memory_bytes: 4116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll m = 1e9+7;
 
ll productOfSubsetSums(vector <ll> arr) 
{ 
    ll ans = 1; 
    for (ll i = 0; i < arr.size(); ++i ) 
        ans = ans * (arr[i] + 1)%m; 
    	ans %= m;
    return ans-1;
}
 
int main(){
	ll n;
	cin >> n;
	vector <ll> alpha(26,0);
	string a;
	cin >> a;
	for (int z=0;z<a.size();z++){
		alpha[a[z]-'a']++;
	}
	cout << productOfSubsetSums(alpha) << endl;
	cin >> n;
}

Measured memory_bytes: 512
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static void main(String[] args) throws Exception {

		int N = nextInt();
		int M = nextInt();
		int X = nextInt();
		int[][] x = new int[N][];
		for(int i=0;i<N;i++){
			x[i]=nextInts();
		}
		long ans = Long.MAX_VALUE;

		for(int i=1;i<(1<<N);i++){
			int[] p = new int[N];
			for(int k=0;k<N;k++){
				if(((i>>k)&1)==1){
					p[k]=1;
				}else{
					p[k]=0;
				}
			}
//			System.out.println(Arrays.toString(p));
			int[] s = new int[M+1];
			Arrays.fill(s,0);
			for(int k=0;k<N;k++){
				if(p[k]==0)
					continue;
				for(int m=0;m<M+1;m++){
					s[m]+=x[k][m];
				}
			}
			boolean flg = true;
//			System.out.println(Arrays.toString(s));
			for(int k=1;k<M+1;k++){
				if(s[k]<X){
					flg=false;
					break;
				}
			}
			if(flg){
				ans=Math.min(ans, s[0]);
			}
		}
		if(ans==Long.MAX_VALUE){
			ans=-1;
		}
		System.out.println(ans);
	}


	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}


Measured memory_bytes: 27728
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int flag=0;
	for(int i=0;i<26;i++){
		for(int j=0;j<15;j++){
			if((4*i+7*j)==n||n==0){
						flag=1;
						break;	
			}
		}
	}
	if(flag)
	printf("Yes");
	else
	printf("No");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	string s;
	map<string,int> m;
	scanf("%d",&t);
	for(int i=0;i<t;i++) {
		cin>>s;
		m[s]++;	
	}
	printf("%d\n",m.size());
	
}

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

int main(){
    int a; cin >> a;
    string str; cin >> str;
    if(a>=3200) cout << str << endl;
    else cout << "red" << endl;
}


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

int main(){
    string s,t;
    cin>>s>>t;
    if(s.size()<t.size()){
        cout<<"UNRESTORABLE"<<endl;
        return 0;
    }
    for(int i=s.size()-t.size();i>=0;i--){
        bool flag=true;
        for(int j=0;j<t.size();j++){
            if(s[i+j]!='?'&&s[i+j]!=t[j]){
                flag=false;
                break;
            }
        }
        if(flag){
            for(int j=0;j<s.size();j++){
                if(i<=j&&j<i+t.size())cout<<t[j-i];
                else if(s[j]=='?')cout<<"a";
                else cout<<s[j];
            }
            cout<<endl;
            return 0;
        }
    }
    cout<<"UNRESTORABLE"<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
const int B=250;
int N,Q;
long long A[100000];
long long L[100000/B],R[100000/B],mid[100000/B],S[100000/B];
void calc(int id)
{
	int l=id*B,r=min(id*B+B,N);
	long long Lmin=0,Lsum=0;
	L[id]=R[id]=mid[id]=0;
	for(int k=l;k<r;k++)
	{
		Lsum+=A[k];
		if(Lmin>Lsum)Lmin=Lsum;
		L[id]=max(L[id],Lsum);
		mid[id]=max(mid[id],Lsum-Lmin);
	}
	S[id]=Lsum;
	long long Rsum=0;
	for(int k=r-1;k>=l;k--)
	{
		Rsum+=A[k];
		R[id]=max(R[id],Rsum);
	}
}
long long get()
{
	long long ans=0;
	long long cummax=0;
	for(int i=0;i<=N/B;i++)
	{
		ans=max(ans,mid[i]);
		ans=max(ans,cummax+L[i]);
		cummax=max(cummax+S[i],R[i]);
	}
	return ans;
}
int main()
{
	cin>>N>>Q;
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
	}
	for(int i=0;i<=N/B;i++)
	{
		calc(i);
	}
	cout<<get()<<endl;
	for(;Q--;)
	{
		int k;long long x;cin>>k>>x;
		k--;
		A[k]=x;
		calc(k/B);
		cout<<get()<<endl;
	}
}



Measured memory_bytes: 3896
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)

    val N = sc.nextInt()
    val P = Array.fill(N)(sc.nextInt()).sorted(Ordering.Int.reverse)

    println(P.head / 2 + P.tail.sum)
  }

}

Measured memory_bytes: 25536
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func line() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	input := strings.Split(line(), " ")
	a, _ := strconv.Atoi(input[0])
	b, _ := strconv.Atoi(input[1])
	c, _ := strconv.Atoi(input[2])
	count := 0
	for ; b >= a && count < c; count++ {
		b -= a
	}
	fmt.Printf("%d\n", count)
}


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

int main()
{
    string b;

    cin >> b;

    if(b=="A"){
        cout << "T" << endl;
    }
    else if(b=="T"){
        cout << "A" << endl;
    }
    else if(b=="G"){
        cout << "C" << endl;
    }
    else if(b=="C"){
        cout << "G" <<endl;
    }
    return 0;
}

Measured memory_bytes: 256
b1,b2,b3=(int(x) for x in input().split())

if (b1==0 or 1) and (b2==0 or 1) and (b3==0 or 1):
    if b1==1 and b2==0 and b3==0 or b1==0 and b2==1 and b3==0 or b1==0 and b2==0 and b3==0:
        print("Close")
    
    elif b1==1 and b2==1 and b3==0 or b1==0 and b2==0 and b3==1:
        print("Open")



Measured memory_bytes: 5600
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx 1
int solve(vector<int>&arr, int to)
{
	int ret = 0;
	for(int x:arr){
		ret+=(x-to)*(x-to);
	}
	return ret;
}
int main()
{	
	ios_base::sync_with_stdio(0);
	int n;
	while(cin>>n){
		vector<int> arr(n);
		for(int i=0; i<n; i++)
			cin>>arr[i];
		int ans =1000000000;
		for(int i=-100; i<=100; i++){
			ans = min(ans, solve(arr,i));
		}
		cout<<ans<<endl;
	}
}



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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

using namespace std;
using ll = long long;

const double PI = 3.14159265358979;

void solve()
{
  int a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;

  vector<bool> w_seen(f / 100 + 1, false);
  vector<bool> s_seen(f + 1, false);

  vector<int> w;
  vector<int> s;

  queue<int> que;
  que.push(0);
  while(!que.empty())
  {
    int now = que.front();
    que.pop();

    if (now > f / 100) continue;
    if (w_seen[now]) continue;

    w_seen[now] = true;
    w.emplace_back(now);
    que.push(now + a);
    que.push(now + b);
  }

  que.push(0);
  while(!que.empty())
  {
    int now = que.front();
    que.pop();

    if (now > f) continue;
    if (s_seen[now]) continue;

    s_seen[now] = true;
    s.emplace_back(now);
    que.push(now + c);
    que.push(now + d);
  }

  sort(ALL(w));
  sort(ALL(s));

  int ans_sw = 100;
  int ans_s = 1;
  for(const auto& wv : w)
  for(const auto& sv : s)
  {
    if (wv * e < sv) break;

    int sw = wv * 100 + sv;
    if (sw > f) break;

    if (ans_s * sw <= sv * ans_sw)
    {
      ans_s = sv;
      ans_sw = sw;
    }
  }

  cout << ans_sw << " " << ans_s;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3624
n,x = map(int,input().split())
if n != 1:
  l = list(map(int,input().split()))
  i = 0
  cnt = 0
  ans = 0
  while cnt <= x :
    if i == n:
      print(n+1)
      exit()
    ans += 1
    cnt += l[i]
    i += 1
  print(ans)
else:
  l = int(input())
  if l <= x:
    print(2)
  else:
    print(1)

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

int main()
{
    int N;
    vector<int> A;
    cin >> N;
    for (int i = 0; i < N; ++i){
        int a;
        cin >> a;
        A.push_back(a);
    }
    sort(A.rbegin(), A.rend());
    int Alice = 0;
    int Bob = 0;
    for (int i = 0; i < N; ++i)
    {
        if (i % 2 == 0){
            Alice += A[i];
        }
        else{
            Bob += A[i];
        }
    }
    cout << Alice - Bob << endl;
}

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

int main() {
	int a,b;
	while(cin>>a>>b){
		int cnt=1;
		for(int i=10;;i*=10){
			if((a+b)/i>=1) cnt++;
				else break;
		}
		cout<<cnt<<endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <string.h>
int main()
{
    int i,len;
    char str[20];
	char temp;
	scanf("%s",&str);
	len=strlen(str);
	for(i=0;i<len/2;i++)
	{
		temp=str[i];
		str[i]=str[strlen(str)-1-i];
		str[strlen(str)-1-i]=temp;
	}
	for (i=0;i<len;i++)
	{
		printf("%c",str[i]);
	}
	printf("\n");
    return 0;
}

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

int main(void) {
    int W,H,N;cin>>W>>H>>N;
    int x[N],y[N],a[N];
    for (int i = 0; i < N; i++) cin>>x[i]>>y[i]>>a[i];
    int x_max = W;
    int x_min = 0;
    int y_max = H;
    int y_min = 0;
    for (int i = 0; i < N; i++) {
        switch (a[i]) {
            case 1:
                x_min = max(x_min, x[i]);
            break;
            case 2:
                x_max = min(x_max, x[i]);
            break;
            case 3:
                y_min = max(y_min, y[i]);
            break;
            case 4:
                y_max = min(y_max, y[i]);
            break;
        }
    }
    if (x_min >= x_max || y_min >= y_max) cout << 0 << endl;
    else cout << (x_max - x_min) * (y_max - y_min) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm> 
#include <cstdlib>
#include <map>
#include <queue>
using namespace std;
int main(){
    int N,K;
    cin >> N >> K;
    int h[N];
    for(int i=0;i<N;i++){
        cin >> h[i];
    }

    sort(h,h+N);
    int ans=1000000000,sa;
    for(int i=0;i<N-K+1;i++){
        sa = h[i+K-1]-h[i];
        ans = min(ans,sa);
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
using namespace std;

bool isP(int x) {
  for (int i = 1; i * i <= x; i++) {
    if (i * i == x) {
      return true;
    }
  }
  return false;
}

int main() {
  int n, d;

  while (cin >> n >> d) {
    int x[10][10];

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

    int ans = 0;

    for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
        int sum = 0;
        for (int k = 0; k < d; k++) {
          int diff = x[i][k] - x[j][k];
          sum += diff * diff;
        }

        if (isP(sum)) {
          ans++;
        }
      }
    }

    cout << ans << endl;
  }
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long int ll;

string intToString(int num){
	string str;
	while( num != 0){
		int digit = num % 10;
		num /= 10;
		str.push_back( digit);
	}
	return str;
}

bool isPalindromic(string str){
	int n = str.size();
	for(int i = 0; i < n/2; i++){
		if( str[i] != str[n-i-1]) return false;
	}
	return true;
}

int main(){
	int n,m,x;
	cin>>n>>m>>x;
	vector<int> left(n+1,0);
	vector<int> right(n+1,0);
	for(int i = 0; i < m; i++){
		int a;
		cin>>a;
		left[a] = 1;
		right[a] = 1;
	}
	for(int i = 1 ; i <= n; i++){
		left[i] = left[i] + left[i-1];
	}
	for(int i = n-1; i >= 0; i--){
		right[i] = right[i] + right[i+1];
	}
	int ans = 0;
	ans = min(left[n] - left[x],right[0] - right[x]);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
// using Graph = vector<vector<Edge>>;
using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int X;
  cin >> X;
  if (X >= 30)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using namespace std;

// long long gcd(long long a, long long b){
//     if (a < b){
//         a ^= b;
//         b ^= a;
//         a ^= b;
//     }
//     return b ? gcd(b, a % b) : a;
// }

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

int main(){
    long long n,d[200001],m,t[200001];
    map<long long, long long> mpd,mpt;
    cin >> n;
    rep(i,n){
        cin >> d[i];
        mpd[d[i]]++;
    }
    cin >> m;
    rep(i,m){
        cin >> t[i];
        mpt[t[i]]++;
    }
    
    rep(i,m){
        if(mpt[t[i]] > mpd[t[i]]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    
    return 0;
}


Measured memory_bytes: 28416
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
#define all(a)  (a).begin(), (a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i = 0; i < n; i++)
#define repR(i,n) for(int i = n; i >= 0; i--)
#define FOR(i,m,n) for(int i = m; i < n; i++)
#define PB push_back
#define MP make_pair
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

    int x = 1;
    while (s > 4 || s == 3) {
        s = (s % 2 == 0 ? s / 2 : s * 3 + 1);
        x++;
    }

    cout << x+3 << endl;
    return 0;
}


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

using namespace std;

int main(){

  int a,b,c;
  cin >> a >> b >> c;
  if ((a + b) >= c){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef vector<ll> v1;
typedef vector<v1> v2;
typedef vector<v2> v3;

typedef unordered_map<ll, unordered_map<ll, ll>> graph;

const ll INF = 1ll << 50;
const ll mod = 1000000007;

ll n;
tuple<ll,ll,ll> a;
tuple<ll,ll,ll> b;
ll x = 0;
ll ans = 0;

vector<ld> get_rate(tuple<ll,ll,ll> a, tuple<ll,ll,ll> b){
    vector<ld> r(3);
    ll ga, sa, ba;
    tie(ga, sa, ba) = a;
    ll gb, sb, bb;
    tie(gb, sb, bb) = b;
    r[0] = (ld)ga/(ld)gb;
    r[1] = (ld)sa/(ld)sb;
    r[2] = (ld)ba/(ld)bb;
    return r;
}

ll inc(ll x, tuple<ll,ll,ll> a, tuple<ll,ll,ll> b){
    v1 av(3);
    tie(av[0], av[1], av[2]) = a;
    v1 bv(3);
    tie(bv[0], bv[1], bv[2]) = b;
    v1 dp(5000*5000+10, -INF);
    ll dp_size = 5000*5000+10;
    dp[0] = 0;
    for(ll i = 0;i < dp_size;i++){
        for(ll j = 0;j < 3;j++){
            if(i+av[j] < dp_size)
                dp[i+av[j]] = max(dp[i+av[j]], dp[i] + bv[j] - av[j]);
        }
    }
    return *max_element(dp.begin(),dp.begin()+x+1) + x;


}


int main(){
    cin >> n;
    ll g, s, br;
    cin >> g >> s >> br;
    a = make_tuple(g,s,br);
    cin >> g >> s >> br;
    b = make_tuple(g,s,br);
    // for(ll i = 0;i <= n;i++){
    //     x = max(x, inc(i, a, b) + (n-i));
    // }
    // for(ll i = 0;i <= x;i++){
    //     ans = max(ans, inc(i, b, a) + (x-i));
    // }
    x = inc(n, a, b);
    ans = inc(x, b, a);
    cout << ans << endl;



}


Measured memory_bytes: 198616
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
using namespace std;
#define INF 100000000
#define MAXN 220

typedef long long ll;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

int D[MAXN];

int N, K, T, U, V, L;

int main(void) {
    cin >> N >> K >> T >> U >> V >> L;
    if (U >= V) {
        cout << 1.0 * L / U << endl;
        return 0;
    }
    D[0] = 0;
    for (int i = 1; i <= N; i++) {
        cin >> D[i];
    }
    D[N+1] = L;
    int cur = 0; // 今の位置がどのポイントを超えたところか(例えばD[1]の人参を超えたらcur = 1)
    double pos = 0, time = 0; // 位置,時間
    int car = 0; // 持ってる人参の数
    bool boost = false; // ダッシュしてるかどうか
    double boost_time = 0; // ダッシュの残り時間
    while (cur < N+1) {
        double next;
        if (!boost) {
            next = D[cur+1];
            time += (next - pos) / U;
            cur++;
            boost = true;
            boost_time = T;
        } else {
            // ダッシュが先に切れるかそれとも次の人参が先に来るか
            // ダッシュが先に切れる
            if (pos + boost_time * V < D[cur + 1]) {
                next = pos + boost_time * V;
                time += boost_time;
                if (car > 0) {
                    boost_time = T;
                    car--;
                } else {
                    boost = false;
                    boost_time = 0;
                }
            } else {
                next = D[cur+1];
                cur++;
                time += (next - pos) / V;
                if (car < K) {
                    car++;
                    boost_time -= (next - pos) / V;
                } else {
                    boost_time = T;
                }
            }
        }
        pos = next;
    }
    printf("%.10f\n", time);
    return 0;
}

Measured memory_bytes: 1196