akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define MP(a, b) make_pair(a, b)
#define F first
#define S second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int n, m;
vector<pi>s;
int dp[1024];

int main(){
  while(scanf("%d", &n) && n){
    s.clear();
    int h, r;
    rep(i, n){
      scanf("%d%d", &h, &r);
      s.push_back(MP(h, r));
    }
    scanf("%d", &m);
    rep(i, m){
      scanf("%d%d", &h, &r);
      s.push_back(MP(h, r));
    }

    sort(s.begin(), s.end());
    memset(dp, 0, sizeof(dp));

    int res = 0;
    rep(i, s.size()){
      dp[i] = 1;
      rep(j, i) if(s[j].F < s[i].F && s[j].S < s[i].S){
	dp[i] = max(dp[i], dp[j] + 1);
      }
      res = max(res, dp[i]);
    }
    printf("%d\n", res);
  }
  return 0;
}

Measured memory_bytes: 1204
#ifdef __GNUC__
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#endif

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>

#include <string>
#include <cstring>
#include <vector>
#include <valarray>
//#include <array>//x C++ (G++ 4.6.4)

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <cassert>//assert();
#include <fstream>
/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)

/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#define PII pair<int,int>
/////////
using namespace::std;

// 最大公約数
template<class T>
inline T gcd(T a, T b){return b == 0 ? a : gcd(b, a % b);}
// 最小公倍数
template<class T>
inline T lcm(T a, T b){return a * b / gcd(a, b);}
////////////////////////////////

inline void solve(){
	int N,MA,MB;
	cin >> N >> MA >> MB;
	vector<int> A(N),B(N),C(N);
	for(int i=0;i<N;++i){
		cin >> A[i] >> B[i] >> C[i];
	}
	vector< vector<int> > dp(401,vector<int>(401,-1) );
	dp[0][0] = 0;
	int H,L;
	for(int i=0;i<N;++i){
		for(int a=400;a>=0;--a){
			for(int b=400;b>=0;--b){
				if( dp[a][b] >= 0 ){//ある
					H = dp[a][b] + C[i];
					L = dp[ a+A[i] ][ b+B[i] ];
					if( L > 0 ){
						dp[ a+A[i] ][ b+B[i] ] = min( H, L );
					}else{
						dp[ a+A[i] ][ b+B[i] ] = H;
					}
				}
			}
		}
	}
	int ans = (int)1e9;
	for(int mul=1;;++mul){
		if( MA*mul > 400 || MB*mul > 400 ) break;
		if( dp[MA*mul][MB*mul] >= 0 ){
			ans = min(ans,dp[MA*mul][MB*mul] );
		}
	}
	if( ans == (int)1e9 ){
		ans = -1;
	}
	cout << ans << endl;
}

signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	//std::cout << std::fixed;//小数を10進数表示
	//cout << setprecision(16);//小数をいっぱい表示する。16?

	solve();
}


Measured memory_bytes: 896
#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define rep(X, Y) for (int(X) = 0; (X) < (Y); ++(X))
#define rrep(X, Y) for (int(X) = (Y)-1; (X) >= 0; --(X))
#define all(X) (X).begin(), (X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
#define print(x) cout << x << endl
#define INF 1e16

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

void solve(long long N, long long K, std::vector<long long> a) {
  vl accB(N + 1);
  vl accW(N + 1);
  rep(n, N) {
    accB[n + 1] = accB[n];
    accW[n + 1] = accW[n];
    if (a[n] > 0) {
      accB[n + 1] += a[n];
    } else {
      accW[n + 1] += a[n];
    }
  }

  ll all = accB[N] - accB[0];
  ll maxNum = -INF;
  for (ll i = 0; i <= N - K; i++) {
    // 白で塗る -> 黒で塗られているところの点数を減らす
    ll tmp1 = all - (accB[i + K] - accB[i]);

    // 黒で塗る
    ll tmp2 = all + (accW[i + K] - accW[i]);

    maxNum = max(maxNum, max(tmp1, tmp2));
  }

  print(maxNum);
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long K;
  scanf("%lld", &K);
  std::vector<long long> a(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &a[i]);
  }
  solve(N, K, std::move(a));
  return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>

using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
typedef pair<ll,ll> P2;
typedef pair<P2,int> PP;
ll INF=1000000000000000000ll;

struct edge{
	int t;
	ll c;
};

int n,m,q;
vector<edge> G[100001];
P2 room[100001];
PP query[100001];
ll sd[100001],gd[100001];
ll ggd[100001];
int ans[400000];
int bit[400000];

void add(int k,int a){
	k++;
	while(k<=200000){
		bit[k]+=a;
		k+=k&-k;
	}
}

int sum(int k){
	int res=0;
	while(k>0){
		res+=bit[k];
		k-= k& -k;
	}
	return res;
}

void dijk(){
	for(int i=0;i<n;i++)sd[i]=INF;;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,0));
	while(que.size()){
		P p=que.top();
		que.pop();
		int v=p.second;
		ll c=p.first;
		if(sd[v]<c)continue;
		sd[v]=c;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(sd[e.t]>c+e.c){
				sd[e.t]=c+e.c;
				que.push(P(c+e.c,e.t));
			}
		}
	} 
}

void dijk2(){
	for(int i=0;i<n;i++)gd[i]=INF;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push(P(0,n-1));
	while(que.size()){
		P p=que.top();
		que.pop();
		int v=p.second;
		ll c=p.first;
		if(gd[v]<c)continue;
		gd[v]=c;
		for(int i=0;i<G[v].size();i++){
			edge e=G[v][i];
			if(gd[e.t]>c+e.c){
				gd[e.t]=c+e.c;
				que.push(P(c+e.c,e.t));
			}
		}
	} 
}


int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int f,t;
		ll c;
		scanf("%d%d%lld",&f,&t,&c);
		edge e;
		e.c=c;
		e.t=t;
		G[f].push_back(e);
		e.t=f;
		G[t].push_back(e);
	}
	scanf("%d",&q);
	for(int i=0;i<q;i++){
		ll s,g;
		scanf("%lld%lld",&s,&g);
		query[i]=PP(P2(s,g),i);
	}
	dijk();
	dijk2();
	for(int i=0;i<n;i++)room[i]=P2(sd[i],gd[i]),ggd[i]=gd[i];
	sort(ggd,ggd+n);
	int gsize=unique(ggd,ggd+n)-ggd;
	for(int i=0;i<n;i++)room[i].second=lower_bound(ggd,ggd+gsize,room[i].second)-ggd;
	sort(query,query+q);
	sort(room,room+n);
	int j=0;
	for(int i=0;i<q;i++){
		while(j<n && room[j].first<=query[i].first.first){
			add(room[j].second,1);
			++j;
		}
		int p=lower_bound(ggd,ggd+gsize,query[i].first.second)-ggd;
		ans[query[i].second]=j-sum(p);
	}
	for(int i=0;i<q;i++)printf("%d\n",ans[i]);
	return 0;
}

Measured memory_bytes: 19916
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

bool check(string s) {
    rep(i, s.size() - 1) {
        if(s[i] != s[i + 1])
            return false;
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    set<char> cset;
    for(char c : s)
        cset.insert(c);
    int res = INF;
    for(char c : cset) {
        int tmp = 0;
        string s2 = s;
        while(!check(s2)) {
            int now = 0;
            tmp++;
            string s_new = "";
            while(now + 1 < s2.size()) {
                if(s2[now] == c || s2[now + 1] == c)
                    s_new += c;
                else
                    s_new += '0';
                now++;
            }
            s2 = s_new;
        }
        res = min(res, tmp);
    }
    cout << res << endl;
    return 0;
}

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

#define INF (1<<30)

int main(){
	int a,b,AB,x,y;	cin>>a>>b>>AB>>x>>y;

	int limit=max(x,y)*2;

	int ans=INF;
	for(int i=0; i<=limit; i++){
		// ABピザを買うべき数を全探索。
		int need_A=max(0, x-(i/2)), need_B=max(0, y-(i/2));
		int cost=(i*AB)+(need_A*a)+(need_B*b);

		ans=min(ans,cost);
	}

	cout<<ans<<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++)

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000 //10^9:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

int main(){
    int D;
    cin>>D;
    vector<int> c(26);
    rep(i,26){ 
        cin>>c[i];
    }
    vector<vector<int>> s(D ,vector<int>(26));
    rep(d,D) rep(j,26) cin>>s[d][j];
    int t;
    vector<vector<int>> last(D ,vector<int>(26));
    int v=0;
    vector<int> kaisai_bi(26);
    int ans=18398+s[1][16];
    rep(j,26){
        if(j==16)continue;
        else if(j==0)ans-=c[j]*(2-1);
        else ans-=c[j]*(2-0);
    }
    rep(d,D) {
        cin>>t;
        t--;
        v+=s[d][t];
        kaisai_bi[t]=d+1;
        rep(j,26) last[d][j]=kaisai_bi[j];
        rep(j,26){ 
            v-=c[j]*(d+1-last[d][j]);
            }
//        cout<<v<<endl;
    }
    int m;
    cin>>m;
//    cout<<"m="<<m<<endl;
    rep(i,m){
        int dd,q;
        cin>>dd>>q;
        q--;
        int j=0;
        while(last[dd-1][j]!=dd || j>=26) j++;
        if(j==26){ 
            cout<<"error"<<endl;
            return 0;
        }
//        cout<<j+1<<"->"<<q+1<<endl;
        v-=s[dd-1][j];
        for(int d=dd-1;d<D;d++){ 
            if(last[d][j]==dd){
                v+=c[j]*(d+1-last[d][j]);
//                cout<<d+1<<" "<<last[d][j]<<"->";
                last[d][j]=(d==0? 0 : last[d-1][j]);
//                cout<<last[d][j]<<endl;
                v-=c[j]*(d+1-last[d][j]);
            }
            else{ 
//                cout<<d+1<<" ";
                break;
            }
        }
        
        v+=s[dd-1][q];
        int before=last[dd-1][q];
        for(int d=dd-1;d<D;d++){ 
            if(last[d][q]==before){ 
                v+=c[q]*(d+1-last[d][q]);
//                cout<<d+1<<" "<<last[d][q]<<"->";
                last[d][q]=dd;
//                cout<<last[d][q]<<endl;
                v-=c[q]*(d+1-last[d][q]);
            }
            else{ 
//                cout<<d+1<<endl;
                break;
            }
        }
        cout<<v<<endl;
    }
    return 0;
}


Measured memory_bytes: 3664
#include<iostream>
using namespace std;
int main(){
  int n[101];
  int i;
  int num;
  cin >> num;
  for(i=0;i<num;i++) cin >> n[i];
  cout << n[num-1];
  for(i=1;i<num;i++) cout <<" "<< n[num-i-1];
  cout << endl;
  return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
struct topological_sort {
  const int n;
  const vector<vector<int>>& grh;
  vector<int> sorted;
  vector<int> ckd;
  bool flg;
  topological_sort (
      const vector<vector<int>>& grh
    ) :
    n(grh.size()),
    grh(grh),
    sorted(),
    ckd(n, 0),
    flg(false)
    {
      for (int i = 0; i < n; i++) {
        flg |= (ckd[i] == 0 && dfs(i));
      }
    }
  bool dfs (int crr) {
    if (ckd[crr] == 1) return true;
    if (ckd[crr] == 2) return false;
    bool ret = false;
    ckd[crr] = 1;
    for (int nxt : grh[crr]) {
      ret |= dfs(nxt);
    }
    ckd[crr] = 2;
    sorted.insert(sorted.begin(), crr);
    return ret;
  }
  bool has_cycle () {return flg;}
};
int main() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> grh(n);
  for (int i = 0; i < m; i++) {
    int s, t;
    cin >> s >> t;
    grh[s].push_back(t);
  }
  topological_sort tps(grh);
  cout << (tps.has_cycle() ? 1 : 0) << endl;
  return 0;
}


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

int main()
{
	int N, M; cin >> N >> M;
	vector<int> A(M), B(M);
	for (int i = 0; i < M; i++) {
		cin >> A[i] >> B[i];
		A[i]--;
		B[i]--;
	}

	vector<long long> ans(M+1);
	vector<int> Tree(N, -1);
	vector<int> Treesize(N, 1);
	long long fuben = (long long)N * (N - 1) / 2;

	ans[M] = fuben;

	for (int i = M - 1; i > 0; i--) {
		int Ap = A[i], Bp = B[i];
		while (Tree[Ap] != -1) Ap = Tree[Ap];
		while (Tree[Bp] != -1) Bp = Tree[Bp];

		if (Ap != Bp) {
			fuben -= (long long)Treesize[Ap] * Treesize[Bp];
			if (Treesize[Ap] < Treesize[Bp]) swap(Ap, Bp);
			Tree[Bp] = Ap;
			Treesize[Ap] += Treesize[Bp];
		}

		ans[i] = fuben;
	}

	for (int i = 1; i <= M; i++) {
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 3712
n = int(input())
maximum_profit = -10**9

r0 = int(input())
r_min = r0
for i in range(1, n):
    r1 = int(input())
    r_min = min(r0, r_min)
    maximum_profit = max(maximum_profit, r1 - r_min)
    r0 = r1
print(maximum_profit)

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

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

long long MOD = 1000000000 + 7;

int main(){
  cout << setprecision(10);
  string S,T;
  cin >> S;
  cin >> T;

  int n = S.size();
  int m = T.size();

  vector<vector<int>> dp(n+1, vector<int>(m+1,0));
  string ans = "";
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      if(S[i-1] == T[j-1]){
        dp[i][j] = dp[i-1][j-1] + 1;
      } else { 
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }
  cerr << dp[n][m] << endl;

  while(n > 0 && m > 0){
    if(dp[n][m] == dp[n-1][m]){
      n--;
    } else if(dp[n][m] == dp[n][m-1]){
      m--;
    } else { 
      ans += S[n-1];
      n--;
      m--;
    }
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  
}


Measured memory_bytes: 35584
import numpy as np

def gcd(v1, v2):
    if v1 == 0 or v2 == 0:
        return max(v1, v2)
#     print(v1, v2, v1%v2)
    if v1 % v2 == 0:
        return v2
    return gcd(v2, v1%v2)

N = int(input())

A = list(map(int, input().split()))
L = np.zeros(N+1)
R = np.zeros(N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
#     print(N-i-1, N-i, N-i-1)
    R[N-i-1] = gcd(R[N-i], A[N-i-1])
M = []
for j in range(N):
    M.append(gcd(L[j], R[j+1]))

print(int(max(M)))

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

using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    int a,b;
    cin >> a >> b;
    
    if ((a+b)%2 == 0) cout << (a+b)/2;
    else cout << (a+b+1)/2;
    
    return 0;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define debug(x) {cerr<<#x<<" = "<<(x)<<endl;}
using namespace std;
ll a[200005],b[200005],qzha[200005]={0},qzhb[200005]={0},k;
int m,n,ans=-1;
int findm(ll k)//剩k分钟，还能从第二堆里读几本
{
    if(k<qzhb[1])
        return 0;
    if(k>=qzhb[m])
        return m;
    int pos = upper_bound(qzhb+1,qzhb+1+m,k) - qzhb - 1;
    //debug(k)debug(pos)
    return pos;
    /*
    int l=0,r=m,mid;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(qzhb[mid]>k)//读不完mid本
            r=mid;//往小的找
        else
            l=mid+1;
    }
    return l;
    */
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        qzha[i]=qzha[i-1]+a[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
        qzhb[i]=qzhb[i-1]+b[i];
    }

    for(int i=0;i<=n;i++)
    {
        if(qzha[i]>k)
            break;
        int book=i;
        ll remind=k-qzha[i];
        book += findm(remind);
        ans=max(ans,book);
    }
    cout<<max(ans,0);
    return 0;
}




Measured memory_bytes: 9900
#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long 
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
# define trace(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
  stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
string to_string(char c) { return "'" + string(1, c) + "'";}
string to_string(string s) { return '"' + s + '"';}
string to_string(bool f) { if(f) return "True"; else return "False";}
string to_string(const char* s) { return to_string((string) s);}
template<typename A> string to_string(A);
template<typename A, typename B> string to_string(pair<A, B> p){
  return "(" + to_string(p.first) + ": " + to_string(p.second) + ")";}
template<typename A> string to_string(A v) {bool f = false; string r = "{"; 
  for (auto x: v) {if (f) r += ", "; r += to_string(x); f = true;} return r += "}";}
template<typename A> string to_string(vector<vector<A>> v) {string r; 
  for (auto x: v) r += "\n" + to_string(x); return r;}
int Nerr;
template<typename A> string to_string(A *p) {return to_string(vector<A>(p, p + Nerr));}
void err(istream_iterator<string>) { cerr << endl; }
template<typename T,typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
  cerr << *it << " = " << to_string(a) << "; "; err(++it, args...); }
template<typename T> void kek(T ans) {cout << ans << endl; exit(0);}
#define Lu(...) [&] (auto &&u) { return __VA_ARGS__; }
#define Luv(...) [&] (auto &&u, auto &&v) { return __VA_ARGS__; }

/************/

signed main()
{
	ios_base::sync_with_stdio(0);
	int TESTS=1;
	// cin>>TESTS;
	while(TESTS--)
	{   
		int h1,m1,h2,m2,k;
		cin >> h1 >> m1 >> h2 >> m2 >> k;
		int time = 0;
		time += (h2-h1) * 60;
		time += (m2-m1);
		cout << max(0ll, time-k) << endl;
	}
}

Measured memory_bytes: 3616
/*
author : seryu
title : ABC166A_"A?C"
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(all(x), val), x.end())
typedef long long ll;
typedef pair<int, int> P;
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; }
ll MOD = 1000000007;
int INF = 1001001001;

void solve()
{
	string s;
	cin >> s;
	if(s == "ABC")cout << "ARC" << endl;
	else cout << "ABC" << endl;
	return;
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 3664
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector <vector <ll>> matrix;

#define endl "\n"
#define mt make_tuple
#define mp make_pair

template <typename T1, typename T2>
bool umax(T1 &a, const T2&b) { return a < b ? a = b, 1 : 0;}
template <typename T1, typename T2> 
bool umin(T1 &a, const T2 &b) {return a > b ? a = b, 1 : 0;}
template <typename T>
T sqr(T a) {return a * a;}

mt19937 rng(20010709);
const int INF = 1000000001;
const int N = 200005;

struct ConvexHullTrick {
    struct Line {
        ll k, b;

        Line(ll k = 0, ll b = 0) : k(k), b(b) { }

        ll get(ll x) {
            return k * x + b;
        }
    };

    ld inter(const Line &a, const Line &b) {
        return (ld)(b.b - a.b) / (a.k - b.k);
    }

    ConvexHullTrick() { }
    vector <Line> lines;

    void add(const Line &a) {
        if (!lines.empty() && (lines.back().k == a.k)) {
            if (a.b >= a.b)
                return;
            else
                lines.pop_back();
        }

        while ((lines.size() > 1) && (inter(lines[lines.size() - 2], a) <= inter(lines[lines.size() - 2], lines.back())))
            lines.pop_back();

        lines.push_back(a);
    }

    ll get(ll x) {
        int l = 1, r = lines.size() - 1;
        ll result = lines.front().get(x);

        for (int iter = log2(lines.size()) + 2; (iter > -1) && (l <= r); iter++) {
            int mid = (l + r) / 2;

            if (lines[mid - 1].get(x) < lines[mid ].get(x)) {
                umin(result, lines[mid - 1].get(x));
                r = mid - 1;
            } else {
                l = mid + 1; 
            }
        } 

        return min(result, lines[r].get(x));
    }
};

int n;
ll c, h[N];
ConvexHullTrick CHT;

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

    cin >> n >> c;

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

    CHT.add(ConvexHullTrick::Line(-2 * h[0], sqr(h[0]) + c));
    ll dp = 0;

    for (int i = 1; i < n; i++) {
        dp = CHT.get(h[i]) + sqr(h[i]);
        CHT.add(ConvexHullTrick::Line(-2 * h[i], dp + sqr(h[i]) + c));
    }

    cout << dp << endl;

    return 0;
}

Measured memory_bytes: 7920
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.StringTokenizer

fun main(args: Array<String>) {
    val sc = FastScanner(System.`in`)

    val n = sc.nextLong()

    for (h in 1..3500) {
        for (x in 1..3500) {
            val up = n * x * h
            val down = 4 * x * h - n * h - n * x
            if (down <= 0 || up % down != 0L) continue
            val w = up / down
            println("$h $x $w")
            return

        }
    }

}


class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}




Measured memory_bytes: 31392
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

using namespace std;

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

typedef long long ll;

int main(){
	int sum = 0;
	
	REP(i,10){
		int a;
		
		cin >> a;
		
		sum += a;
	}
	
	cout << sum << endl;
	
	return 0;
}

Measured memory_bytes: 3076
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

  
n,m = (int(i) for i in input().split())
k = []
uf = UnionFind(m)
for i in range(n):
  a = []
  a = list(int(i) for i in input().split())
  a.pop(0)
  k.append(a)
for i in k:
  tmp = i[0]
 #言語ごとに同じ人がいたらunion
  for j in i[1:]:
   uf.union(tmp,j)
    
 #任意の二人が同じunionに属するか？
b = uf.find(k[0][0])
for k in k[1:]:
  if b == uf.find(k[0]):
    continue 
  else:
    print('NO')
    exit()
print('YES')

Measured memory_bytes: 29776
package main

import "fmt"

func main() {
	var N, K int
	fmt.Scan(&N, &K)
	t := N % K
	fmt.Println(min(t, abs(K-t)))
}
func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}


Measured memory_bytes: 512
N,M = map(int,input().split())
mod = pow(10,9)+7

def f(x,mod):
    k = 1
    res = 1
    while k<x:
        k+=1
        res*=k
        res %= mod
    return res

if abs(N-M)>1:print(0)
elif abs(N-M)==1:
    a = f(min(N,M),mod)
    print(pow(a,2,mod)*max(N,M)%mod)
else:
    a = f(N,mod)
    print(2*pow(a,2,mod)%mod)

Measured memory_bytes: 3064
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math

# x 個の玉を y グループに分ける場合の数 (1個以上の玉のグループ)
def f2(x, y):
    n = x + y - 1
    r = y - 1
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


# x 個の玉を y グループに分ける場合の数 (0個以上の玉のグループ)
def f(x, y):
    if x < y:
        return 0
    if x == 0 and y == 0:
        return 1
    # if x == 0:
    #     return 0
    if y == 0:
        return 0
    return f2(x - y, y)


# Example: N = 5, K = 3
N, K = list(map(int, input().split()))

for i in range(1, K + 1):
    result = f(K, i) * (
        f(N - K, i - 1) +
        f(N - K, i) +
        f(N - K, i) +
        f(N - K, i + 1)
    )
    print(result % 1000000007)


Measured memory_bytes: 3316
#include <iostream>

typedef long long ll;

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

#define debug(x) cout << #x << "=" << x << endl;

using namespace std;

//A.Restaurant

//８００円のランチ
//１５食ごとに２００円のキャッシュバック
//食べた数 N が与えられる

//払った金額 x ともらった金額 y の差 x-y を求める

int calcReCush(int N){

    int eatNum = 15;
    int reCush = 200;
    
    return (N / eatNum) * reCush;
}

int main(void){

    int N;
    cin >> N;

    int LunchPrice = 800;
    int x = LunchPrice * N;
    int y = calcReCush(N);

    cout << x - y << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long int ll;
typedef vector<pair<ll,ll> > Q;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(int)(n);i++)

int main()
{
  int n,m;
  map<string,int> mp;
  cin>>n;
  rep(i,n)
  {
    string s;
    cin>>s;
    //まだ無かったらmapに追加
    if(mp.find(s)==mp.end()) mp[s]=1;
    //すでにmapにあったら増やす
    else mp[s]++;
  }
  cin>>m;
  rep(i,m)
  {
    string s;
    cin>>s;
    if(mp.find(s)==mp.end()) mp[s]=-1;
    else mp[s]--;
  }

  int max=0;
  for(auto ln=mp.begin();ln!=mp.end();ln++)
  {
    if(max<ln->second) max=ln->second;
  }
  cout<<max<<endl;
}

Measured memory_bytes: 256
N = int(input())
b = list(map(int, input().split()))
a = [b[0]]
for i in range(1,N-1):
    if b[i-1] < b[i]:
        a.append(b[i-1])
    else:
        a.append(b[i])
a.append(b[len(b)-1])
print(sum(a))

Measured memory_bytes: 3060
import java.util.Scanner;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int loop;
		String output = "Yes";
		Scanner sc = null;

		try {
			sc = new Scanner(System.in);

			String line = sc.next();
			loop = Integer.parseInt(line);
			line = sc.nextLine();

			//?????????????????????
			int[][] diceList = new int[loop][6];
			for (int i = 0; i < loop; i++) {
				line = sc.nextLine();
				Dice di = new Dice(line);
				diceList[i] = di.surface;
				}
			//?????????????????¨????????????
			for (int i = 0; i < diceList.length - 1; i++) {
				for (int j = i + 1; j < diceList.length; j++) {
					//??????????????§??????
					if (Dice.diceCheck(diceList[i], diceList[j])) {
						output = "No";
						break;
					}
				}
			}
			System.out.println(output);
		} finally {
			sc.close();
		}
	}

}
//?????????????????????
class Dice{

	int[] surface;

	public Dice(String s){

		String[] work;

		work = s.split(" ");

		surface = new int[work.length];

		for (int i = 0; i < work.length; i++) {
			surface[i] = Integer.parseInt(work[i]);
		}
	}

	///????????????????????????????????????
	public static int[] diceroll(int[] di , String com){
		int n = 0;
		int[] dice = di;

		//???????????????
			switch (com) {
			case "N":
				n = dice[0];
				dice[0] = dice[1];
				dice[1] = dice[5];
				dice[5] = dice[4];
				dice[4] = n;
				break;

			case "S":
				n = dice[0];
				dice[0] = dice[4];
				dice[4] = dice[5];
				dice[5] = dice[1];
				dice[1] = n;
				break;

			case "W":
				n = dice[0];
				dice[0] = dice[2];
				dice[2] = dice[5];
				dice[5] = dice[3];
				dice[3] = n;
				break;

			case "E":
				n = dice[0];
				dice[0] = dice[3];
				dice[3] = dice[5];
				dice[5] = dice[2];
				dice[2] = n;
				break;

			default:
				System.out.println("other");
				break;
			}
		return dice;

	}

	///?????????????????????
	public static boolean diceCheck(int[] diceOne , int[] diceTwo){

		String command;

		boolean anser = false;
		for (int j = 0; j < 4; j++) {

			for (int k = 0; k < 4; k++) {
				if (!Arrays.equals(diceOne, diceTwo)) {
					command = "N";
					diceOne = Dice.diceroll(diceOne, command);
					command = "W";

					for (int l = 0; l < 4; l++) {
						diceOne = Dice.diceroll(diceOne, command);
						if (Arrays.equals(diceOne, diceTwo)) {
							anser = true;
							break;
						}
					}

				}else{
					anser = true;
					break;
				}
			}
			//
			if (!Arrays.equals(diceOne, diceTwo)) {
				command = "W";
				diceOne = Dice.diceroll(diceOne, command);
			}else{
				anser = true;
				break;
			}
		}
		return anser;

	}
}

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

int w,h,ans;

struct Ling{
	int a[21][21];
	int sx,sy,gx,gy,cost;
};

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


Ling go(Ling ling,int d){
	ling.cost++;
	if(ling.a[ling.sy+dy[d]][ling.sx+dx[d]]==1){
		ling.sx=-1;
		return ling;
	}

	while(ling.a[ling.sy][ling.sx]==0){
		ling.sy+=dy[d];
		ling.sx+=dx[d];
		if(ling.sx<0 || ling.sy<0 || ling.sx>=w || ling.sy>=h){
			ling.sx=-1;
			return ling;
		}
	}
	if(ling.a[ling.sy][ling.sx]==3)
		return ling;

	ling.a[ling.sy][ling.sx]=0;
	ling.sy-=dy[d];
	ling.sx-=dx[d];
	return ling;
}



void dfs(Ling ling){
	if(ling.cost>=10 || (ans>0 && ling.cost>ans))
		return;

	for(int d=0;d<4;d++){
		Ling nextling=go(ling,d);
		if(nextling.a[nextling.sy][nextling.sx]==3){
			if(ans==-1)
				ans=nextling.cost;
			else ans=min(nextling.cost,ans);
			continue;
		}
		else if(nextling.sx==-1)
			continue;

		dfs(nextling);
	}
}

void solve(){
	ans=-1;
	Ling ling;
	ling.cost=0;
	for(int y=0;y<h;y++){
		for(int x=0;x<w;x++){
			cin>>ling.a[y][x];
			if(ling.a[y][x]==2){
				ling.sx=x;
				ling.sy=y;
				ling.a[y][x]=0;
			}
			if(ling.a[y][x]==3){
				ling.gx=x;
				ling.gy=y;
			}
		}
	}
	dfs(ling);
	cout<<ans<<"\n";
}


int main(){
	cin>>w>>h;
	while(w!=0){
		solve();
		cin>>w>>h;
	}
	return 0;
}

Measured memory_bytes: 900
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>

#define int long long
#define double long double
#define endl '\n'
#define gcd __gcd
#define f first
#define s second
#define what_is(x) cerr << #x << " is " << x << endl;
#define all(x) x.begin(), x.end()
const int inf = __LONG_LONG_MAX__;

using namespace std;

void fast_io() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

bool isprime(int x) {
	for (int i = 2; i * i <= x; i++)
		if (x % i == 0)
			return false;

	return true;
}

signed main() {
  fast_io();

  int x;
  cin >> x;

  while (!isprime(x))
  	x++;

  cout << x << "\n";

  return 0;
}


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

typedef int i32;
typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;


template<typename First, typename Second, typename Third>
struct triple {
   First first;
   Second second;
   Third third;
};


#define debug(x)  cerr<<x<<"\n";
#define loop(i,n) for(i32 i = 0; i < n; ++i)
#define pi  pair<int,int>
#define ti  tuple<int,int,int>
#define mt  make_tuple
#define mk  make_pair
#define vi  vector<int>
#define vll vector<i64>
#define fastInOut ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pr(a) for(auto x:a) cout<<x<<" ";
#define prmap(m) for(auto x:m) cout<<x.first<<" "<<x.second<<"\n";
using namespace std;

i64 n,m,k; 
int main(){
	string s1,s2;
	cin>>s1>>s2;
	cout<<(s2+s1);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define INF 1000000001
using namespace std;
int dp[100005];
int main(){
      int n,tmp; cin >> n;
      fill(dp,dp+n,INF);
      for (int i = 0;i < n; i++){
            cin >> tmp;
            *lower_bound(dp,dp+n,tmp) = tmp;
      }
      cout << lower_bound(dp,dp+n,INF) - dp<<endl;
}

Measured memory_bytes: 1548
#include <bits/stdc++.h>
using namespace std;
const long long N = 5e5+5 , M = 1e9+7, OO = 0x3f3f3f3f;
typedef long long ll;
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);
const double Pii = 3.14159265359;
ll n, m;
ll fac[N];
ll c[N];

ll power(ll a, ll b, ll m){
    if(!b)  return 1;
    ll t = power(a, b>>1, m)%m;
    return ((t*t)%m * (b&1 ? a : 1)%m)%m;
}
ll modInverse(ll n, ll m)
{
    return power(n, m-2, m);
}

void Calc()
{
    c[0]=1;
    for(int r=1; r<=n; ++r)
    {
        c[r] = (((fac[n]*modInverse(fac[r], M))%M)*modInverse(fac[n-r], M))%M;
    }
}



ll P(ll m, ll n)
{
    ll ret = 1;
    while(n--)
    {
        ret*=m;
        ret%=M;
        m--;
    }
    return ret;
}


int main()
{
    FIO
    cin >> n >> m;
    fac[0]=1;
    for (int i=1; i<=m; i++)
        fac[i]=(fac[i-1]*i)%M;
    Calc();

    bool f = 1;
    ll no = 0;
    ll st = 1;
    if(n%2 == 0) f=0;
    //for(int i=0; i<=n; ++i) cout << c[i] << " ";
    //cout << endl;
    for(int i=n; i>0; --i)
    {
        if(f) no += ((st*c[i])%M);
        else no -= ((st*c[i])%M);
        //cout << st << " " << c[i] << " " <<  no << endl;
        f = !f;
        st*=((m-i)+1);
        st%=M;
    }
    ll tot=P(m, n);
    //cout << tot << " " << no << endl;
    cout << ((tot-no+M*M)%M * tot)%M << endl;


    return 0;
}



Measured memory_bytes: 11364
N, M = map(int, input().split())
s, c = [0]*M, [0]*M
for i in range(0, M):
    s[i], c[i] = map(int, input().split())
a = [0]*N
for i in range(0, M):
    a[s[i]-1] = c[i]
for i in range(0, M):
    for j in range(i, M):
        if (s[i] == s[j] and c[i] != c[j]) or (s[i] == 1 and c[i] == 0 and N != 1):
            print (-1)
            break
    else:
        continue
    break
else:
    if N > 1 and a[0] == 0:
        a[0] = 1
    map_res = map(str, a)
    res = "".join(map_res)
    print (res)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
        int n, m;
        cin >> n >> m;
        int h[100001];
        int hh;
        int ans = 0;
        int a[100001];
        int b[100001];
        int aa, bb;
        vector<int> vec[100001];
        for(int i = 1; i <= n; i++){
                cin >> hh;
                h[i] = hh;
        }

        for(int i = 0; i < m; i++){
                cin >> aa >> bb;
                a[i] = aa; b[i] = bb;
                vec[aa].push_back(bb);
                vec[bb].push_back(aa);
        }



        for(int i = 1; i <= n; i++){
                bool goodten = true;
                for(int j = 0; j < vec[i].size(); j++){
                        if(h[i] <= h[vec[i].at(j)]){
                                goodten = false;
                                break;
                        }


                }
                if(goodten == true){
                        ans++;
                }
        }
        cout << ans << endl;
}


Measured memory_bytes: 9144
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define INF (int)1e9+4
#define INFL (ll)1e18+4
#define md (int)1e9+7
#define mx 10000000  //use fixed<<setprecion
#define mk make_pair
#define pi pair<int,int>
#define ss second
#define ff first
#define pb emplace_back
#define onell(x) __builtin_popcountll(x)
#define one(x) __builtin_popcount(x)
#define maxi(a) *max_element(a.begin(),a.end());
#define mini(a) *min_element(a.begin(),a.end());
#define all(s) s.begin(),s.end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(x, a) for (auto& x: a)
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>b;i--)
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sz(x) ((long long)x.size())
#define mez(s) memset(s,0,sizeof s)
#define mex(s) memset(s,-1,sizeof s)
#define metr(s) memset(s,true, sizeof s)
typedef vector<int> vi;
typedef vector<ll>vl;
typedef map<int,int> mp;
typedef queue<int> que;
typedef vector<pi> vp;
const int mxn=1e6+67;int gh[mxn];
void solve(){
int n=0,x=0,y=0,z=0;
cin>>n;vi a(n);
rep(i,0,n){
	cin>>a[i];
	gh[a[i]]++;
}bool all=0,pair=0;
rep(i,2,mxn){
	int c=0;
	for(int j=i;j<mxn;j+=i){
		c+=gh[j];
	}
	if(c==n)all=true;
	if(c>1)pair=true;
}
if(!pair)cout<<"pairwise coprime";
else if(!all)cout<<"setwise coprime";
else cout<<"not coprime";
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t=1;
  //cin>>t;
  while(t--){
  	solve();
  }
  return 0;
}


Measured memory_bytes: 10988
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll C(ll x,ll y){
	return (x*(x-1))/2;
}
int main(){
	ll n,total=0,sum=1;
	scanf("%lld",&n);
	string a[n+1],s;
	for(ll i=1;i<=n;i++){
		cin>>a[i];
		sort(a[i].begin(),a[i].end());
	}
	sort(a+1,a+n+1);
	s=a[1];
	for(ll i=2;i<=n;i++){
		if(a[i]==s){
			sum++;
		}
		else{
			total+=C(sum,2);
			sum=1;
			s=a[i];
		}
	}
	total+=C(sum,2);	
	printf("%lld",total);
	return 0;
}

Measured memory_bytes: 7296
//g++  5.4.0  hursh29  
#include <bits/stdc++.h>
#define debug(x) cout  << #x << " " << x << "\n"
#define speedup ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ll long long int
#define MOD 998244353
using namespace std ;  
#define endl cout << "\n"
ll ans ; 
void solve(){

    int n ;  cin >> n ; 
    double t ; 
    if(n%2)  {  
    t =  n/2 +1 ; 
    t /= (double)n ; 
    }
    else 
        t = 1/2.0 ; 
    
    printf("%0.13lf",t) ;
}
int32_t main() {  
	ll test = 1 ; 
	   //cin >> test  ; 
	while(test--)
		solve() ; 

    return 0 ; 
}   

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();


int main() {
    int m;
    cin >> m;
    ll d, c;
    ll digit_sum = 0, digit_nums = 0;
    while(m--) {
        cin >> d >> c;
        digit_sum += d*c;
        digit_nums += c;
    }
    ll target = (digit_sum - 1) % 9 + 1;
    cout << (digit_sum - target) / 9 + (digit_nums-1) << endl;

    return 0;
}




Measured memory_bytes: 256
n=int(input())
s=[input() for _ in range(n)]
ans=0
for i in s:
    ans+=i.count("AB")
endA=[]
startB=[]
AND=[]
for i in s:
    if i[0]=="B" and i[-1]=="A":
        AND+=[i]
    elif i[0]=="B":
        startB+=[i]
    elif i[-1]=="A":
        endA+=[i]
MIN=min(len(endA),len(startB))
if not AND:
    print(ans+MIN)
elif endA or startB:
    print(ans+MIN+len(AND))
else:
    print(ans+len(AND)-1)

Measured memory_bytes: 3828
n = int(input())
a = list(map(int, input().split()))

b = [-1] * (n + 2)

mid = n // 2
left = mid - 1
right = mid + 1

b[mid] = a[0]

for i in range(1, n):
  if not i % 2 == n % 2:
    b[left] = a[i]
    left -= 1
  else:
    b[right] = a[i]
    right += 1

for i in b:
  if i < 0:
    continue
  print(i, end=" ") 

Measured memory_bytes: 26180
from itertools import combinations

N,K = map(int,input().split())
h = [int(input()) for _ in range(N)]

'''
res = 10**10
for i in combinations(h,K):
    tmp = max(i) - min(i)
    res = min(res,tmp)
'''

d = sorted(h)
res = 1e+9
for i in range(N-K+1):
    res = min(res,d[i+K-1] - d[i])
print(res)

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

int main(){
  int n;
  int64_t a = 2ll,b = 1ll;
  cin >> n;
  for(int i = 0; i < n - 1; i++){
    a += b;
    swap(a,b);
  }
  cout << b << endl;
  return 0;
}


Measured memory_bytes: 3636
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10, MOD = 1e9+7;
const ll OO = 2e18;
int n, k , q;
int cnt[N];
int main() {
	
	cin >> n >> k >> q;;
	for (int i = 1; i <= q; ++i) {
		int x;
		cin >> x;
		cnt[x]++;
	}
	for (int i = 1; i <= n; ++i) {

		if (k + cnt[i] - q > 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;

	}
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
import sys


YYMM = "YYMM"
MMYY = "MMYY"
AMBIGUOUS = "AMBIGUOUS"
NA = "NA"

def solve(S):
    a= S//100
    b= S % 100
    if 1 <= a <=12 and 1 <= b <= 12:
        print(AMBIGUOUS)
    elif 1 <= a <= 12:
        print(MMYY)
    elif 1 <= b <= 12:
        print(YYMM)
    else:
        print(NA)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


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


void solve(long long N, std::vector<long long> p){
  sort(p.begin(), p.end());

  int total = 0;

  for (int i=0;i<N;i++) {
    total += p[i];
  }

  cout << total - p[N-1] / 2 << endl;
}

// Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> p(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&p[i]);
    }
    solve(N, std::move(p));
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << endl;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
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;}

// 0 false, 1 true 
// stringの数字をint型にしてアスキーコードになったら -48する
// 切り上げ　ceil(a)


int main() {
    ll h;
    cin >> h;
    
    ll tmp = 1;
    ll ans = 0;
    while(h >= 1){
        ans += tmp;
        h = h / 2;
        tmp = tmp * 2;
    }

    cout << ans << endl;

}


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

int main() {
    int n, l;
    cin >> n >> l;
    vector<string> s(n);
    rep(i,n) cin >> s[i];
    sort(s.begin(), s.end());
    rep(i,n) cout << s[i];
    cout << endl; 
    return 0;
}

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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


#include "bits/stdc++.h"

template<typename T>
using Matrix = std::vector<std::vector<T>>;

ll mod;
template<typename T>
Matrix<T> add(const Matrix<T>& a, const Matrix<T>& b) {
	int n = a.size(), m = a[0].size();
	assert(a.size() == b.size() && a[0].size() == b[0].size());
	Matrix<T> res(n, std::vector<T>(m, 0));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			res[i][j] = a[i][j] + b[i][j] % mod;
		}
	}
	return res;
}

template<typename T>
Matrix<T> mult(const Matrix<T>& a, const Matrix<T>& b) {//a:n*m matrix,b:m*l matrix
	int n = a.size(), m = a[0].size(), l = b[0].size();
	Matrix<T> res(n, std::vector<T>(l, 0));
	for (int i = 0; i < n; ++i) {
		for (int k = 0; k < m; ++k) {
			for (int j = 0; j < l; ++j) {
				res[i][j] += a[i][k] * b[k][j] % mod;
			}
		}
	}
	REP(i, n)REP(j, l)res[i][j] %= mod;
	return res;
}

template<typename T>
Matrix<T> fact(Matrix<T> a, long long n) {
	Matrix<T>  e(a.size(), std::vector<T>(a.size(), 0));
	for (int i = 0; i < (int)a.size(); ++i) {
		e[i][i] = 1;
	}
	while (n >= 1) {
		if (n & 1) e = mult(e, a);
		a = mult(a, a);
		n /= 2;
	}
	return e;
}
using ull =  unsigned long long;
ull po(ull a, ull n, ull m) {
	if (n == 0)return 1;
	ll d = po(a, n / 2, m);
	if (n & 1)return a * d % m * d % m;
	return d * d % m;
}
ull inv(ull a, ull m) {
	return po(a, m - 2, m);
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, a, b;
	cin >> n >> a >> b >> mod;


	auto calc = [&](ll s, ll le, ll k) {
		ll t = 1;
		REP(j, k)t *= 10;

		Matrix<ll> cols = { {t % mod ,1}, {0,1} };
		Matrix<ll> colt = { {t % mod,1,mod - 1}, {0,t % mod,1},{0,0,1} };

		cols = fact(cols, le - 1);
		colt = fact(colt, le - 1);
		auto ress = mult(cols, Matrix<ll>({ {1},{1} }));
		auto rest = mult(colt, Matrix<ll>({ {0},{(t + 1) % mod},{1} }));
		return (ress[0][0] * s % mod - rest[0][0] * (b % mod) % mod + mod) % mod;
	};
	ull d = 0, ans = 0;
	for (int i = 17; i >= 0; --i) {
		ll t = 1;
		REP(j, i)t *= 10;

		ll r = (10 * t - a + b - 1) / b;
		ll l = (t - a + b - 1) / b;
		if (l >= n)continue;
		l = max(l, 0ll);
		r = min(r, n);
		if (l >= r)continue;
		ans += calc((a + b * (r - 1)) % mod, r - l, i + 1) * po(10, d, mod) % mod;
		ans %= mod;
		d += (r - l) * (i + 1);
	}
	cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n); for(int i = 0;i < (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
long double pi = acos(-1);
const int INF = 1001001001;


// 最小公倍数を求める
int euqlid (int a, int b){
  int temp;
  temp = a % b;
  if(temp == 0)return b;
  return euqlid(b,temp);
}
ll conbination(ll a,ll b){
  ll u = 1;
  ll d = 1;
  while(b != 0){
    u *= a;
    d *= b;
    a--;
    b--;
  }
  return u / d;
}
int strtoint(char s){
  return (int(s-'0'));
}
int fact(int n){
  if(n == 1)return 1;
  return n * fact(n-1);
  }


int main(){
int a,b,x;
cin >> a >> b >> x;
cout << (a + b >= x and x >= a?"YES":"NO") << endl;
}

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


string a;
string b;
int main(){
	cin >> a;
	cin >> b;
	for (int i = 0; i < a.size(); i++){
		string z;
		z.push_back(a.back());
		a.insert(0, z);
		a.pop_back();
		if (a == b){
			puts("Yes");
			return 0;
		}
	}
	if (a == b){
		puts("Yes");
	}
	else{
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>

#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

typedef long long int64;

using namespace std;

int64 mod = 1000000007;

int main() {
	ios_base::sync_with_stdio(0);
    vector<int64> d(100, 1);
	for (int64 i = 1; i < 100; ++i) d[i] = (d[i - 1] * 2) % mod;
	int64 n;
	cin >> n;
	vector<int64> a(n);
	for (int64 i = 0; i < n; ++i) cin >> a[i];
	int64 ans = 0;
	for (int64 j = 0; j < 60; ++j) {
	    int64 sum = 0;
		for (int64 i = 0; i < n; ++i) {
		    if (a[i] & (1ll << j)) {
			   ++sum;
			}
		}
		int64 add = sum;
        add *= (n - sum);
		add %= mod;
		add *= d[j];
		add %= mod;
		ans += add;
		ans %= mod;
	}
	
	
	cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
 
int main(int argc, const char * argv[])
{
 
    int data[100] = {0};
    int i, n, max = 0;
     
    while (scanf("%d", &n) != EOF) {
        data[n]++;
    }
     
    for (i = 0; i < 100; i++) {
        if (max < data[i]) {
            max = data[i];
        }
    }
     
    for (i = 0; i< 100; i++) {
        if (max == data[i]) {
            printf("%d\n", i);
        }
    }
     
     
    return 0;
}

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

int main() {
  int a, b, c, d, aya;
  cin >> a;
  b = a / 100;
  aya = b;
  a = a - b * 100;
  c = a / 10;
  aya = aya + c;
  a = a - c * 10;
  d = a / 1;
  aya = aya + d;
  cout << aya << endl;
}


Measured memory_bytes: 256