akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(void)
{
	ll l, r;
	cin >> l >> r;

	if (l - r > 2018)
	{
		cout << 0 << endl;
		return 0;
	}
	for (ll i = l; i < r; ++i)
	{
		if (i % 2019 == 0)
		{
			cout << 0 << endl;
			return 0;
		}
	}
	ll ans = 100000;
	for (ll i = l; i < r; ++i)
	{
		for (ll j = l + 1; j <= r; ++j)
		{
			ans = min(ans, ((i % 2019) * (j % 2019)) % 2019);
		}
	}
	cout << ans << endl;

	/* ll a, b;
	a = l, b = r;
	a %= 2019, b %= 2019;
	ll ans = 100000;
	if (a > b)
	{
		int tmp = a;
		a = b;
		b = tmp;
		a = 0;
	}
	for (ll i = a; i < b; ++i)
	{
		for (ll j = a + 1; j <= b; ++j)
		{
			ans = min(ans, (i * j) % 2019);
		}
	}
	if (ans == 100000)
	{
		ans = 0;
	}
	cout << ans << endl;*/
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define big ((ll)(1e9) + 7)

int main()
{
  ll n,m;
  cin >> n >> m;
  vector<ll> A(m);
  vector<ll> B(m);
  for(ll i = 0;i < m;i++)
  {
    cin >> A[i] >> B[i];
  }
  vector<vector<ll> > G(n);
  bool flag = 0;
  for(ll i = 0;i < m;i++)
  {
    if(A[i] == 1 || B[i] == 1) flag = 1;
    G[A[i]-1].push_back(B[i]-1);
    G[B[i]-1].push_back(A[i]-1);
  }

  if(!flag)
  {
    cout << "No" << endl;
    return 0;
  }

  vector<ll> v(n);
  vector<ll> check(n,0);
  queue<ll> q;
  q.push(0);
  while(!q.empty())
  {
    ll num = q.front();
    check[num] = 1;
    q.pop();
    for(ll i = 0;i < G[num].size();i++)
    {
      ll see = G[num].at(i);
      if (check[see] == 0)
      {
        q.push(see);
        check[see] = 1;
        v[see] = num + 1;
      }
    }
  }
  cout << "Yes" << endl;
  for (ll i = 1; i < n; i++)
  {
    cout << v[i] << endl;
  }
}


Measured memory_bytes: 16688
while True:
    a, op, b = input().split()
    a = int(a)
    b = int(b)
    if op == "+":
        print(a+b)
    elif op == "-":
        print(a-b)
    elif op == "*":
        print(a*b)
    elif op == "/":
        print(a//b)
    else:
        break


Measured memory_bytes: 5596
//http://abc071.contest.atcoder.jp/tasks/abc071_a
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <numeric>
#include <functional>
#include <list>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <complex>

using namespace std;

#define REP(i,m,n) for(int i=m;i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define ALL(x) (x).begin(),(x).end()

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

const ll inf = INT_MAX;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int di[][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

int main(){

	int x,a,b;
	cin >> x >> a >> b;
	string str =  std::abs(x-a) <= std::abs(x-b) ? "A" : "B";
	cout << str << endl;

	return 0;
}


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

using namespace std;

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

int main(){
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  string s,t;
  cin>>s>>t;
  int cnt=0;
  rep(i,0,3){
    if(s[i]==t[i]){cnt++;}
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 256
def floor_sum(n, m, a, b)
  res = 0

  if a >= m
    res += (n - 1) * n * (a / m) / 2
    a %= m
  end

  if b >= m
    res += n * (b / m)
    b %= m
  end
  
  y_max = (a * n + b) / m
  
  return res if y_max == 0

  x_max = (m * y_max - b + a - 1) / a
  res += (n - x_max) * y_max + floor_sum(y_max, a, m, a * x_max - m * y_max + b)
  res
end

t = gets.to_s.to_i

ans = []
t.times do
  n, m, a, b = gets.split.map { |e| e.to_i }
  ans << floor_sum(n, m, a, b)
end

puts ans


Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

int main(){
    int n, m; cin >> n >> m;
    vector<int> p(m), y(m);
    vector<vector<int>> pref(n);
    rep(i,m){
        cin >> p[i] >> y[i];
        --p[i];
        pref[p[i]].push_back(y[i]);
    }
    rep(i,n) sort(ALL(pref[i]));
    rep(i,m){
        int v = p[i];
        printf("%06d", v+1);
        int id = lower_bound(ALL(pref[v]),y[i]) - pref[v].begin();
        printf("%06d\n", id+1); 
    }
    return 0;
}

Measured memory_bytes: 7808
mod = 10**9+7
N = int(input())
s = input()
dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1
for i in range(1, N):
    if s[i-1] == '>':
        dp[i][0] = dp[i-1][0]
        for j in range(1, N-i):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod
    else:
        for j in range(N-1)[::-1]:
            dp[i][j] = (dp[i][j+1]+dp[i-1][j+1])%mod
print(sum(dp[-1])%mod)

Measured memory_bytes: 112348
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <string.h>
#include <cmath>
#include <queue>
#include <string>
#include <stack>
#include <utility>
#include <queue>
#include <cmath>
#define mp make_pair
#define pii pair<int,int> 
#define ff first
#define ss second
#define ll long long 
#define vi vector<int>

using namespace std;

int D,a,b,c,p,q,r,s,g1,g2;

bool cek;

int gcd(int a,int b)
{
	return b!=0? gcd(b,a%b): a;
}

/*bool cek()
{
	for(int z=1;z*z<=D;z++)
	{
		if(z*z==D) 
		{
			printf("tes\n");
			return true;
		}
	}
	return false;
}*/

int main()
{
	while(scanf("%d%d%d", &a,&b,&c),(a||b||c))
	{
		cek=true;
		D=b*b-(4*a*c);
		if(a==0&&b==0&&c==0)break;
		for(int z=0;z*z<=D;z++)
		{
			if(z*z==D) 
			{
				//printf("tes\n");
				cek=false;
				break;
			}
		}
		if(D<0||cek)
		{
			//printf("Impossible\n");
			puts("Impossible");
			continue;
		}
		//printf("%d\n",D);
		else
		{
			p=2*a;
			q=-(-b+sqrt(D));
			r=2*a;
			s=-(-b-sqrt(D));
			g1=gcd(p,q);
			g2=gcd(r,s);
			p/=g1;
			q/=g1;
			r/=g2;
			s/=g2;
			if(p<0)
			{
				p*=-1;
				q*=-1;
			}
			if(r<0)
			{
				r*=-1;
				s*=-1;
			}
			if(p<r||(p==r&&q<s))
			{
				swap(p,r);
				swap(q,s);
				swap(g1,g2);
			}
			printf("%d %d %d %d\n",p,q,r,s);
		}
	}
	return 0;
}

Measured memory_bytes: 1196
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cmath>
#include <vector>
#include <string>

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

using namespace std;

int main()
{
    int N, K;
    long long int h[100001];
    scanf("%d %d", &N, &K);
    REP(i, N)
        scanf("%lld ", &h[i]);
    sort(h, h+N);
    //REP(i, N)
    //    cout << h[i] <<endl;
    long long int ans = 1000000001;
    REP(i, N-K+1) {
        long long int tmp = h[i+K-1]-h[i];
        if(tmp<ans)
            ans = tmp;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>

#define M 1046527
#define NIL -1
#define L 14

char H[M][L];


int getChar(char ch){
	if(ch == 'A') return 1;
	else if(ch == 'C') return 2;
	else if(ch == 'G') return 3;
	else if(ch == 'T') return 4;
	else return 0;
}


long long getKey(char str[]){
	long long sum = 0, p = 1, i;
	for(i = 0; i < strlen(str); i++){
		sum += p*(getChar(str[i]));
		p *= 5;
	}
	return sum;
}

int h1(int key){return key % M;}
int h2(int key){return 1 + (key % (M - 1));}

int find(char str[]){
	long long key, i, h;
	key = getKey(str);
	for(i = 0;;i++){
		h = (h1(key) + i * h2(key)) % M;
		if(strcmp(H[h], str) == 0) return 1;
		else if(strlen(H[h]) == 0) return 0;
	}
	return 0;
}

int insert(char str[]){
	long long key, i, h;
	key = getKey(str);
	for(i = 0;; i++){
		h = (h1(key) + i * h2(key)) % M;
		if(strcmp(H[h], str) == 0) return 1;
		else if(strlen(H[h]) == 0){
			strcpy(H[h], str);
			return 0;
		}
	}
	return 0;
}

int main(void){
	int i, n, h;
	char str[L], com[9];
	for(i = 0; i < M; i++) H[i][0] = '\0';
	scanf("%d", &n);
	for(i = 0; i < n; i++){
		scanf("%s %s", com, str);

		if(com[0] == 'i'){
			insert(str);
		}else{
			if(find(str)){
				printf("yes\n");
			}else{
				printf("no\n");
			}
		}
	}
	return 0;
}

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

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;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

ll XOR(ll a){
    if(a % 4 == 1)return 1;
    else if(a % 4 == 3)return 0;
    else if(a == 0)return 0;
    else return (XOR(a-1)^a);
}
signed main()
{   
    gearup;
    int a,b,c; cin >> a >> b >> c;
    cout << min(b/a,c) << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#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 ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

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

    int con = 0, ans = 0;
    bool flag = true;
    REP(i, 3){
        if(S[i] == 'R') {
            con++;
            ans = max(ans, con);
        }
        else{
            ans = max(ans, con);
            con = 0;
        }
    }
    ans = max(ans, con);

    cout << ans << endl;
}

Measured memory_bytes: 3628
#include<iostream>
#define atcode 114
using namespace std;
long long a,b,x,tot;
main(){
    cin>>a>>b>>x;
    if (a%x) a+=x-(a%x);
    b-=b%x;
    if (a<=b) cout<<(b-a)/x+1<<endl;
    else cout<<0<<endl;
    return 0;
}

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

ll i,j,z;
ll A,B,C,N,K,H,W;
string S,T;

int main()
{
	cin>>H>>W;
	int h,w;
	cin>>h>>w;
	cout<<(H-h)*(W-w)<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-12, PI = acos(-1);
const int N = 1e5 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

vector<int> adj[N];
int start, endd, best = OO;
int vis[N][5];

void dfs(int node, int type, int cnt) {
  if(type == 0 && node == endd) {
    best = min(best, cnt);
    return;
  }
  if(vis[node][type] <= cnt)
    return;
  vis[node][type] = cnt;
  for(auto it: adj[node]) {
    dfs(it, (type + 1) == 3 ? 0 : type + 1, cnt + (type + 1 == 3));
  }
}

bool can = 0;
void bfs(int node, int type, int cnt) {
  queue<pair<int, pair<int, int>>> q;
  q.push({node, {type , cnt}});
  while(!q.empty()) {
    auto it = q.front();
    q.pop();
    if(it.first == endd && it.second.first == 0) {
      cout << it.second.second;
      can = 1;
      return;
    }
    vis[it.first][it.second.first] = cnt;
    for(auto ii: adj[it.first]) {
      int nxtType = (it.second.first == 2) ? 0 : it.second.first + 1;
      int nxtCnt = it.second.second + (nxtType == 0);
      if(vis[ii][nxtType] > nxtCnt) {
        vis[ii][nxtType] = nxtCnt;
        q.push({ii, {nxtType, nxtCnt}});
      }
    }
  }
}

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  int n, m, u, v;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> u >> v;
    adj[u].push_back(v);
  }
  cin >> start >> endd;
  memset(vis, '?', sizeof vis);
  bfs(start, 0, 0);
  if(!can)
    cout << -1;
  return 0;
}


Measured memory_bytes: 7680
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    s=list(input())
    k=int(input())
    l=['*']*n
    for i in range(n):
        if s[i]==s[k-1]:
            l[i]=s[k-1]
    print(''.join(l))
resolve()

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define FOR(i,a,n) for(i=(a);i<(n);i++)
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
int res[200];
int add[200];
int main(void)
{
	ll n;
	int m,size,s=0,i;
	scanf("%lld",&n);
	for(m=50;n<(1LL<<m)-1;m--);
	//printf("%d\n",1<<m);
	FOR(i,1,m+1) res[i-1]=i;
	n-=(1LL<<m)-1;
	size=m;
	for(i=m-1;i>=0;i--){
		if(n<(1LL<<i)) continue;
		m++;
		add[i]=m;
		n-=(1LL<<i);
	}
	printf("%d\n",m*2);
	FOR(i,0,size){
		if(add[i]) printf("%d ",add[i]);
		printf("%d ",res[i]);
	}
	FOR(i,0,m) printf("%d%c",i+1,i==m-1?'\n':' ');
	return 0;
}
    

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

int main(){
    int n, m;
    cin >> n >> m;
    dsu d(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        d.merge(a, b);
    }
    int ans = 0;
    rep(i, n){
        if (d.leader(i) == i) ans++;
    }
    cout << ans - 1 << endl;
}


Measured memory_bytes: 3816
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=1000000000;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main(){
    string s,u="keyence";
    cin >> s;
    for (int i = 0; i <= 7; i++) {
        if(s.substr(0,i)+s.substr(s.length()-(7-i),7-i)==u){
            puts("YES");
            return 0;
        }
    }   
    puts("NO");
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long i64;
using std::cout;
using std::endl;
using std::cin;

int n;
std::vector<int> g;

int main() {
	cin >> n; g.resize(n);
	for(int i = 0; i < n; i++) {
		int a; cin >> a;
		
		g[i] = ((i + a) % n);
	}
	
	std::set<int> cycle, noncycle;
	for(int i = 0; i < n; i++) {
		if(cycle.count(i)) continue;
		if(noncycle.count(i)) continue;
		std::vector<int> used;
		std::set<int> st;
		
		int tmp = i, pos = 0;
		while(!st.count(tmp)) {
			if(cycle.count(tmp)) {
				pos = -1;
				break;
			} else if(noncycle.count(tmp)) {
				pos = 1;
				break;
			}
			used.push_back(tmp);
			st.insert(tmp);
			
			tmp = g[tmp];
		}
		
		bool f = false;
		if(!pos) {
			for(auto v : used) {
				f |= (v == tmp);
				if(f) cycle.insert(v);
				else noncycle.insert(v);
			}
		} else {
			for(auto v : used) noncycle.insert(v);
		}
	}
	
	cout << cycle.size() << endl;
	return 0;
}



Measured memory_bytes: 12984
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;

int main(){
  int A,B,X;
  cin>>A>>B>>X;
  if(A<=X&&X<=A+B){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
}


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

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

	int mask = 0;
	for (int i = 0; i < K; i++) {
		int d;
		cin >> d;
		mask |= 1 << d;
	}

	for (int i = n; i < 1000000; i++) {
		int t = i;
		int m = 0;
		while (t > 0) {
			m |= 1 << (t % 10);
			t /= 10;
		}
		if ((mask & m) == 0) {
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
n,d = map(int,input().split())
x = []
for i in range(n):
    xi = [int(i) for i in input().split()]
    x.append(xi)
count = 0
ans = 0
for i in range(n-1):
    for l in range(i+1,n):
        ans = 0
        for j in range(d):
            ans += (x[i][j]-x[l][j])**2

        ans = ans **(1/2)
        if ans == int(ans):
            count += 1
print(count)
    

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, s, N) for(ll i{s}; i < N; i++)
#define rem(i, N, s) for(ll i{N}; i > s; i--)
using namespace std;using ll = long long int;using ld = long double;using P = pair<ll,ll>;const int MOD = (int)1e9+7;const string rt = "\n";const string sp = " ";/* 最大公約数 */template<typename T> T gcd(T a, T b){return b != 0 ? gcd(b, a % b) : a;}/* UnionFind */template<typename T> struct UnionFind{vector<T> par;UnionFind(T n) : par(n, -1){}void init(T n){par.assign(n, -1);}T root(T x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(T x, T y){return root(x) == root(y);}bool merge(T x, T y){x = root(x); y = root(y);if(x == y) return false;if(par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};/* コンビネーション */template<typename T> ll combpm(T N_, T C_) {const int NUM_=400001;static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];if (fact[0]==0) {inv[1]=fact[0]=factr[0]=1;for (int i=2;i<=NUM_;++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%MOD, factr[i]=factr[i-1]*inv[i]%MOD;}if(C_<0 || C_>N_) return 0;return factr[C_]*fact[N_]%MOD*factr[N_-C_]%MOD;}/* 多次元ベクター */template<class T>vector<T> mvec(size_t a){return vector<T>(a);}template<class T, class... Ts>auto mvec(size_t a, Ts... ts){return vector<decltype(mvec<T>(ts...))>(a, mvec<T>(ts...));}/* テスト関数 */void test(ll n){cout << "test" << n << endl;}/* 小数点以下 */void fixsp(ll n){cout << fixed << setprecision(n);}void defsp(ll n){cout << defaultfloat << setprecision(n);}/* 重み付きUnionFind */struct WUnionFind {vector<int> par;vector<int> rank;WUnionFind(int n = 1) {init(n);}void init(int n = 1) {par.resize(n); rank.resize(n);for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0;}int root(int x) {if (par[x] == x) {return x;}else {int r = root(par[x]);return par[x] = r;}}bool issame(int x, int y) {return root(x) == root(y);}bool merge(int x, int y) {x = root(x); y = root(y);if (x == y) return false;if (rank[x] < rank[y]) swap(x, y);if (rank[x] == rank[y]) ++rank[x];par[y] = x;return true;}};/* IO高速化 */void fastio(){ios::sync_with_stdio(false);cin.tie(NULL);}
/* ここからコード開始 */

int main(){
  fastio;
  ll N, x;
  cin >> N >> x;
  vector<ll> a(N);
  for(auto&& i : a){
    cin >> i;
  }
  sort(all(a));
  ll sum{};
  for(auto&& i : a){
    x -= i;
    if(x < 0) break;
    sum++;
  }
  if(x > 0) sum--;
  cout << sum << rt;
}

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

int main() {
  string S,T;
  cin >> S >> T;
  int sum=0;
  
  for(int i=0;i<S.size();i++){
    if(S.at(i)!=T.at(i)) sum += 1;
  }
  
  cout << sum << endl;
}



Measured memory_bytes: 3916
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, A[int(1e5 + 5)];
Pil P[int(1e5 + 5)];
multiset <ll> st = {0, 0};

int main(){
  scanf("%d", &N);
  st.insert(N + 1);
  st.insert(N + 1);

  for (int i = 1; i <= N; i++){
    scanf("%d", A + i);
    P[i] = {A[i], i};
  }
  sort(P + 1, P + N + 1, greater<Pil>());
  st.insert(P[1].se);

  ll ans = 0;
  for (int i = 2; i <= N; i++){
    ll now = P[i].se; st.insert(now);

    auto L1 = st.find(now); L1--;
    auto L2 = st.find(now); L2--; L2--;

    auto R1 = st.find(now); R1++;
    auto R2 = st.find(now); R2++; R2++;

    ll sum = (*L1 - *L2) * (*R1 - now);
    sum += (*R2 - *R1) * (now - *L1);

    ans += ll(P[i].fi) * sum;
  }
  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 10288
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <map>
#define MAXN ()
#define INF (0x7fffffff)
#define LL long long
#define pii pair<int, in>
using namespace std;

int main()
{
	LL a, b, c, k, maxa;
	scanf("%lld%lld%lld", &a, &b, &c);
	scanf("%lld", &k);
	maxa = max(max(a, b), c);
	if (a == maxa)
		printf("%lld", a * (1 << k) + b + c);
	else if (b == maxa)
		printf("%lld", b * (1 << k) + c + a);
	else if (c == maxa)
		printf("%lld", c * (1 << k) + a + b);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPS(i, x) for (int i = 1; i <= (int)(x); 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 FORS(i, m, n) for (int i = m; i <= n; i++)
#define bit(n) (1LL << (n))
#define INF 2e9
#define MOD (1000000007)
#define EPS 1e-9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long long int lli;
#define MAXN 100001
vector< vector< lli > > group(MAXN);
vector< lli > aff(MAXN);
lli merge(lli m, lli n) {
  lli gmLen = group[m].size();
  lli gnLen = group[n].size();
  if (gnLen > gmLen) {
    swap(m, n);
    swap(gmLen, gnLen);
  }
  REP(i, gnLen) {
    group[m].push_back(group[n][i]);
    aff[group[n][i]] = m;
  }
  return -((gmLen + gnLen) * (gmLen + gnLen - 1) - gmLen * (gmLen - 1) -
           gnLen * (gnLen - 1)) /
         2;
}
// mergeで減るか。
bool same(lli m, lli n) { return aff[m] == aff[n]; }
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  lli N, M;
  cin >> N >> M;
  vector< int > A(M), B(M);
  REP(i, M) {
    cin >> A[i] >> B[i];
    A[i]--;
    B[i]--;
  }
  lli ans = N * (N - 1) / 2;

  REP(i, N) {
    group[i].assign(1, i);
    aff[i] = i;
  }
  vector< lli > result(M);
  REPR(i, M - 1) {
    result[i] = ans;
    if (!same(A[i], B[i])) {
      lli ga = aff[A[i]];
      lli gb = aff[B[i]];
      // cout << ga << " " << gb << "\n";
      ans += merge(ga, gb);
    }
  }
  REP(i, M) { cout << result[i] << "\n"; }
}

Measured memory_bytes: 16880
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define ld          long double
#define endl        "\n"

const int mod = 1e9+7;

inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }



void solve() {  
    int n, m; cin >> n >> m;
    int tot = 0;
    int a[n];
    for(int i=0; i<n; i++) { cin >> a[i]; tot += a[i]; }
    int cnt = 0;
    for(int i=0; i<n; i++) {
        if(a[i] * 4 * m >= tot) {
            cnt++;
        }
    }
    if(cnt >= m) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;

    while(T--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long
#define _GLIBCXX_DEBUG
const int INF=1e15;

signed main(){
    int N;cin>>N;
    vector<int>A(N);
    REP(i,N)cin>>A[i];
    sort(A.rbegin(),A.rend());
    int d=N/2;
  	if(N%2==0)--d;
    int ans=0;
    REP(i,N){
        if(i<d)ans+=A[i]*2;
        if((i==d||i==d+1)&&N%2==1)ans-=A[i];
      	if(i==d&&N%2==0)ans+=A[i];
        if(i==d+1&&N%2==0)ans-=A[i];
        if(i>d+1)ans-=A[i]*2;
    }
  	int bans=0;
  	sort(A.begin(),A.end());
  	REP(i,N){
        if(i<d)bans+=A[i]*2;
        if((i==d||i==d+1)&&N%2==1)bans-=A[i];
      	if(i==d&&N%2==0)bans+=A[i];
        if(i==d+1&&N%2==0)bans-=A[i];
        if(i>d+1)bans-=A[i]*2;
    }
  	ans=max(ans,bans*(-1));
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int NUM=60000,UPTO=sqrt(NUM);
int main(){
    bool pris[NUM];
    fill(pris,pris+NUM,true);
    pris[0]=pris[1]=false;
    for(int i=2;i<=UPTO;i++){
        if(pris[i]){
            for(int j=i*i;j<NUM;j+=i){
                pris[j]=false;
            }
        }
    }
    int n;
    while(scanf("%d",&n)!=-1){
        int ll=-1,l=-1;
        for(int i=2;i<NUM;i++){
            if(pris[i]){
                if(i>n){
                    if(pris[n]) printf("%d %d\n",ll,i);
                    else printf("%d %d\n",l,i);
                    break;
                }
                ll=l;
                l=i;
            }
        }
    }
}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
const int INFTY = 1000000000;
int cnt = 0;

void merge(int A[],int left,int mid,int right) {
	int n1, n2;
	int *L, *R;
	n1 = mid - left;
	n2 = right - mid;
	L = new int[n1 + 1];
	R = new int[n2 + 1];
	for(int i = 0; i < n1; i++)
		L[i] = A[left + i];
	for(int i = 0; i < n2; i++)
		R[i] = A[mid + i];
	L[n1] = INFTY;
	R[n2] = INFTY;
	int i = 0;
	int j = 0;
	for (int k = left; k < right ; k++) {
		if( L[i] <= R[j]) {
			A[k] = L[i++];
			cnt++;
		}
		else { 
			A[k] = R[j++];
			cnt++;
		}
	}
	delete [] L;
	delete [] R;
}

void mergeSort(int A[], int left, int right) {
	int mid;
	if (left+1 < right) {
		mid = (left + right)/2;
		mergeSort(A,left, mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}
int main () {
	int n;
	int* A;
	cin >> n;
	A = new int[n];
	for(int i = 0; i < n; i++)
		cin >> A[i];
	mergeSort(A, 0, n);
	for(int i = 0; i < n - 1; i++)
		cout << A[i] << ' ';
	cout << A[n - 1] << endl
		 << cnt << endl;
	return 0;
}

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


def solve(N: int):
    ret = 'ABC' + str(N)
    print(ret)
    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
def root(x):
    path = []
    while P[x] != x:
        path.append(x)
        x = P[x]
    for node in path:
        P[node] = x
    return x
def check(x,y):
    if root(x) == root(y):
        return 1
    else:
        return 0
def unite(x,y):
    P[root(x)] = root(y)        

n = int(input())
P = [i for i in range(n)]
omomi = []
for k in range(n):
    s = list(map(int,input().split()))
    for l in range(n):
        if s[l] != -1:
            omomi.append([s[l],k,l])
omomi.sort()
ans = 0
for yee in range(len(omomi)):
    if check(omomi[yee][1],omomi[yee][2]) == False:
            unite(omomi[yee][1],omomi[yee][2])
            ans+=omomi[yee][0]
print(ans)            


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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> d(n);
    rep(i,k) {
        int m;
        cin >> m;
        rep(j,m){
            int a;
            cin >> a;
            d[a-1] = 1;
        }
    }
    int ans = 0;
    rep(i,n) if (d[i] == 0) ++ans;
    cout << ans << endl;
    return 0;
}

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

void solve(std::istream &ist, std::ostream &ost)
{
    /* ------- 宣言と入力 ------- */

    int N;
    ist >> N;

    vector<int> h;

    for (int i = 0; i < N; i++)
    {
        int input;
        ist >> input;
        h.emplace_back(input);
    }

    /* ------- 計算 ------- */

    vector<int> dp;

    dp.emplace_back(0);
    dp.emplace_back(abs(h.at(1) - h.at(0)));

    for (int i = 2; i < N; i++)
    {
        int step_1_jump = dp.at(i - 1) + abs(h.at(i) - h.at(i - 1));
        int step_2_jump = dp.at(i - 2) + abs(h.at(i) - h.at(i - 2));
        int min_small = min(step_1_jump, step_2_jump);
        dp.emplace_back(min_small);
    }

    ost << dp.at(N - 1) << endl;
}

#ifndef WOMAIN
int main()
{
    solve(std::cin, std::cout);
    return 0;
}
#endif


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

using namespace std;

int main(){
	string s;
	cin>>s;
	int count = 0;
	int ans = 0;
	for(int i=0;i<s.size();i++){
		if(s[i]=='R')
		count++;
		else
		count=0;
		ans=max(ans,count);
}
cout<<ans;
}


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

using namespace std;
int x[15][15];
bool check(int x){
	for(int i=1;i*i<=x;i++){
		if(i*i==x)return true;
	}
	return false;
}
int main(){
	int n,d;
	cin>>n>>d;
	for(int i=0;i<n;i++){
		for(int j=0;j<d;j++){
			cin>>x[i][j];
		}
	}
	int num=0;
	for(int i=0;i<n;i++){
		for(int j=i;j<n;j++){
			int ans=0;
			for(int k=0;k<d;k++){
				ans+=abs(x[i][k]-x[j][k])*abs(x[i][k]-x[j][k]);
			}
			if(check(ans))num++;
		}
	}
	cout<<num;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG
#define dump(a) cerr<<#a<<"="<<a<<endl
#define dumparr(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define dump(a) 
#define dumparr(a,n) 
#endif
#define FOR(i, a, b) for(int i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(int i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;

const ll INF=(1LL<<50);

template<class S,class T>
std::ostream& operator<<(std::ostream& os,pair<S,T> a){
  os << "(" << a.first << "," << a.second << ")";
  return os;
}
template<class T>
std::ostream& operator<<(std::ostream& os,vector<T> a){
  os << "[ ";
  REP(a.size()){
    os<< a[i] << " ";
  }
  os<< " ]";
  return os;
}

bool junjo(ll a,ll b,ll c){
  return (a<b&&b<c)||(c<b&&b<a);
}
void solve(long long n, std::vector<long long> p){
  ll ans=0;
  REP(n-2){
    if(junjo(p[i],p[i+1],p[i+2])){
      ++ans;
    }
  }
  cout<<ans<<endl;
}

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>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

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

    cin.tie(0);
    cout.tie(0);
    //freopen("a.in", "r", stdin);

    int n;
    cin >> n;
    vector<long double> v(n + 1, 0);
    for(int i = 1; i <= n; i ++)
        cin >> v[i];

    vector<vector<long double>> dp(n + 1, vector<long double> (n + 1, 0));
    dp[0][0] = 1;

    for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= n; j ++) {
            dp[i][j] = dp[i - 1][j] * (1 - v[i]);
            if(j > 0)
                dp[i][j] += dp[i - 1][j - 1] * v[i];
        }

    long double ans = 0;
    for(int i = 1; i <= n; i ++)
        if(i > (n - i))
            ans += dp[n][i];

    cout << setprecision(10) << fixed << ans;


    return 0;
}


Measured memory_bytes: 141056
num = [int(x) for x in input().split()]
ans = 0

#A
r = [x%2 for x in num]
if 2 == len(set(r)):
    ans += 1
    if sum(r) == 1:
        r = [1-x for x in r]

num = [num[i] + r[i] for i in range(len(num))]

#B
df = [max(num) - num[i] for i in range(len(num))]
ans += sum([x/2 for x in df])

print(int(ans))

Measured memory_bytes: 3316
n, m = map(int, input().split())
ac = [0]*n
wa = [0]*n
for _ in range(m):
    p, s = input().split()
    p = int(p)-1
    if s == 'AC':
        ac[p] = 1
    elif s == 'WA' and ac[p] == 0:
        wa[p] += 1

ans, pen = 0, 0
for i in range(n):
    if ac[i]:
        ans += 1
        pen += wa[i]
print(ans, pen)

Measured memory_bytes: 10356
#include <bits/stdc++.h>
		using namespace std;
		typedef long long ll;
		#define PI 3.14159265358979
		#define EPS 1e-8
		#define mod  998244353
		#define fi first
		#define se second
		#define mp make_pair
		#define pb push_back
		#define endl "\n"
			 
		const ll INF=1e15;	
		const int N=2e5+50;
		 

		 
		long long binpow(long long a, long long b, long long m) {
			a %= m;
			long long res = 1;
			while (b > 0) {
				if (b & 1)
					res = res * a % m;
				a = a * a % m;
				b >>= 1;
			}
			return res;
		}
		
		ll modinverse(ll a,ll m)
		{
			return binpow(a,m-2,m);
		}
		
			
		
		
		int main()
		{
			ios_base::sync_with_stdio(false);
			cin.tie(NULL);cout.tie(0);
		
			ll n,m;
			
			cin>>n>>m;
			
			vector<ll> v(n+1);
			
			for(ll i=1;i<=n;i++)
			{
				cin>>v[i];
			}
			
			ll dp[3005][3005];
			
			for(ll i=0;i<=n;i++)
			{
				for(ll j=0;j<=m;j++)
				{
					if(j==0)
						{
							dp[i][j]=1;
							continue;
						}
						
					dp[i][j]=0;
				}
			}
			
			for(ll i=1;i<=n;i++)
			{
				for(ll j=1;j<=m;j++)
				{
					dp[i][j]=dp[i-1][j];
					if(j-v[i]>=0)
					{
						dp[i][j]+=(dp[i-1][j-v[i]])*modinverse(2LL,mod);
						dp[i][j]%=mod;
					}
				}
			}
			
			ll ans=dp[n][m]*binpow(2,n,mod) %mod;
			cout<<ans;
		}
			
			
		


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

int main() {
   long long n,cnt=0;
   cin >> n;
   vector<string> s(n);
   map <string,long long> sums;

   rep(i,n) {
       cin >> s[i];
       sort (s.at(i).begin(),s.at(i).end());

   }
   rep(i,n){
       if(sums.count(s[i])==0){
           sums[s[i]] =1;
       }
       else {
           sums[s[i]]++;
       }
   }
   long long ans = 0;
   //sort(s.begin(),s.end());

   for (auto itr = sums.begin();itr != sums.end();++itr){
       if(itr->second > 1){
           long long tmp = itr->second - 1;
           ans += (tmp*(tmp+1))/2;

       }
   }
   cout << ans << endl;
   
}






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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define debug if(true)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int main(){
	int n,i,j;
	scanf("%d",&n);
	// printf("n: %d\n",n);
	ll sum = 0;
	for(i=1;i<=n;i++){
		if(i%3 == 0 || i %5 == 0){continue;}
		// printf("halo\n");
		sum += i;
	}
	printf("%lld\n",sum);
	return 0;
};

Measured memory_bytes: 3812
# coding: utf-8
# Your code here!
K=int(input())

al=[]
cand=[1,2,3,4,5,6,7,8,9]

temp=[]
for _ in range(9):
    for item in cand:
        if int(str(item)[-1])!=0:
            temp.append(int(str(item)[-1])-1+item*10)
        temp.append(int(str(item)[-1])+item*10)
        if int(str(item)[-1])!=9:
            temp.append(int(str(item)[-1])+1+item*10)
    al+=cand
    cand=temp[:]
    al=list(set(al))
    al.sort()
al+=temp
al=list(set(al))
al.sort()
print(al[K-1])



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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define Rep(i,n) for(ll i = 1; i <= n; i++)
#define sz(x) ll(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<ll,ll>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const ll dx[] = {0,1,0,-1,1,1,-1,-1};
const ll dy[] = {1,0,-1,0,1,-1,-1,1};
const ll inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }

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

int main(){
    ll n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    ll g = gcd(n,m);
    ll l = 1LL*n/g*m;
    n /= g; m /= g;
    bool ok = true;
    for(ll i = 0; i < g; i++) {
        if(s[i*n] != t[i*m]) ok = false;
    }
    if(ok) cout << l << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 3764
class Solver
  attr_reader :lines, :n

  def initialize(line, n)
    @lines = [line]
    @n = n
  end

  def exec
    n.times do |i|
      cur_lines = @lines.dup
      cur_lines.each_with_index do |line, i|
        koch
      end
    end

    puts_result
  end

  def puts_result
    lines.each(&:puts_result)
  end

  def koch
    line = lines[0]

    p1 = line.start_point
    p2 = line.end_point
    angle = line.angle

    length_x = p2.x - p1.x
    length_y = p1.y < p2.y ? p2.y - p1.y : p1.y - p2.y
    length_x_devide3 = length_x / 3
    length_y_devide3 = length_y / 3

    length_y_salt = p1.y < p2.y ? 1 : -1

    s = Point.new(length_x_devide3 + p1.x, p1.y + (length_y_devide3 * length_y_salt))
    t = Point.new(length_x_devide3 * 2 + p1.x, p1.y + ((length_y_devide3 * 2) * length_y_salt))

    case angle
    when 0
      if p1.x < p2.x
        ux = p1.x + length_x / 2
        uy = p1.y + Math.sqrt((length_x_devide3 ** 2) - (length_x_devide3 / 2) ** 2)
      else
        ux = p1.x + length_x / 2
        uy = p1.y - Math.sqrt((length_x_devide3 ** 2) - (length_x_devide3 / 2) ** 2)
      end
    when 60
      ux = p1.x
      uy = t.y
    when 120
      ux = p2.x
      uy = s.y
    end

    u = Point.new(ux, uy)

    line1 = Line.new(p1, s, angle)
    line2 = Line.new(s, u, angle + 60)
    line3 = Line.new(u, t, angle + 120)
    line4 = Line.new(t, p2, angle)

    lines.shift
    lines.push(line1, line2, line3, line4)
  end
end

class Line
  attr_accessor :start_point, :end_point, :angle

  def initialize(start_point, end_point, angle)
    @start_point = start_point
    @end_point = end_point
    @angle = cast_angle(angle)
  end

  def cast_angle(angle)
    return angle if angle < 180
    return 0 if angle == 180

    angle - 180
  end

  def puts_result
    puts "#{@start_point.x.floor(8)} #{@start_point.y.floor(8)}"
    puts "#{@end_point.x.floor(8)} #{@end_point.y.floor(8)}" if @end_point.x == 100
  end
end

class Point
  attr_reader :x, :y

  def initialize(x, y)
    @x = x
    @y = y
  end
end

n = gets.to_i

start_point = Point.new(0, 0)
end_point = Point.new(100.to_f, 0)
line = Line.new(start_point, end_point, 0)

Solver.new(line, n).exec


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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
//#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

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;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vin(Vi &v){REP(i,0,(v).size()) cin>>v[i];}
void vin(Vi &v,Vi &v2){REP(i,0,(v).size()) cin>>v[i]>>v2[i];}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
void accum(Vi &v){REP(i,1,(v).size()) v[i]+=v[i-1];}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}


void solve(long long N){
    cout<<(N-1)/2<<endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
signed main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


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

using namespace std;
const int NIL = -1;

struct node {
	int parent;
	int left;
	int right;
};

vector<int> pre;
vector<int> ino;
int n;

void reconstruct(int l, int r)
{
	static int k = 0;
	if (l >= r) return;
	int c = pre[k];
	k++;
	int i = 0;
	for (i = 0; i < n; ++i) {
		if (ino[i] == c) break;
	}
	reconstruct(l, i);
	reconstruct(i + 1, r);
	static int m = 0;
	if (m++ > 0) printf(" ");
	printf("%d", c);

}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int v;
		scanf("%d", &v);
		pre.push_back(v);
	}
	for (int i = 0; i < n; ++i) {
		int v;
		scanf("%d", &v);
		ino.push_back(v);
	}
	reconstruct(0, n);
	printf("\n");
}

Measured memory_bytes: 1052
# -*- coding: utf-8 -*-
import io, sys


def main():
    X,K,D = list(map(int, sys.stdin.readline().split()))

    X = abs(X)
    quo = X // D
    if quo >= K:
        X = X - K*D
        print( abs(X) )
        
    else:
        X %= D
        K -= quo

        if K % 2 == 0:
            print( abs(X) )
            
        else:
            print( abs(X-D) )


if __name__ == "__main__":
    main()


Measured memory_bytes: 9172
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF 2147483647//int max
const int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;

int div_ct(int n) {
  int c = 0;
  int k;
  for ( k = 1; k <= n; k++ ) { 
    if ( n % k == 0 ) { c++; } 
  }
  return c;
}

int main() {
    int n;
    cin >> n;
    if(n < 105)cout << 0 << endl;
    else if(n <135)cout << 1 << endl;
    else if(n <165)cout << 2 << endl;
    else if(n <189)cout << 3 << endl;
    else if(n <195)cout << 4 << endl;
    else if(n <201)cout << 5 << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

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

int main() {
  int N;
  cin>>N;
  vector<double> v(N);
  for(int i=0; i<N; i++){
    cin>>v.at(i);
  }
  sort(v.begin(),v.end());
  double ans=(v.at(0)+v.at(1))/2;
  for(int i=2; i<N; i++){
    ans=(ans+v.at(i))/2;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3760
from collections import defaultdict
def resolve():
    n, m = map(int, input().split())
    h = list(map(int, input().split()))

    d = defaultdict(list)
    for _ in range(m):
        ai, bi = map(lambda x: int(x) - 1, input().split())
        d[ai].append(bi)
        d[bi].append(ai)

    bad = []
    ans = 0
    for i in range(n):
        if -1 in d[i]:
            continue
        flg = True
        for nei_peak in d[i]:
            if h[i] <= h[nei_peak]:
                flg = False
                break

        if flg:
            ans += 1
            for nei_peak in d[i]:
                d[nei_peak] = [-1]

    print(ans)
resolve()

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

int main(){

    int N;
    cin >> N;
    vector<int> P(N);
    rep(i, N) cin >> P[i];

    int min = 0;
    int count = 1;
    rep(j, N){
        if(j == 0) min = P[0];
        else{
            if(P[j] <= min){
                count++;
                min = P[j];
            }
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

const int MAX_N=51;
const int MAX_W=5050;

int N, A;
int x[50];
int value;

long long dp[MAX_N][MAX_W];

long long  get0(int i, int j){
	if (dp[i][j+2500]!=-6000){
		return dp[i][j+2500];
	}
	long long res=0;
	if (i==N) {
		if (j==0) res=1;
	}
	else {
		res=get0(i+1, j+x[i]) + get0(i+1, j);
	}
	return dp[i][j+2500]=res;
}

int main()
{

	for (int i = 0; i < MAX_N; i++){
		for (int j = 0; j < MAX_W; j++){
			dp[i][j] = -6000;
		}
	}

	cin >> N >> A;
	for (int i=0; i < N; i++){
			cin >> value;
			x[i] = value - A;
	}

	cout << get0(0, 0)-1 <<endl;

	return 0;
}


Measured memory_bytes: 2304
import numpy as np
N, D = [int(i) for i in input().split()]
Positions = np.array([[int(i) for i in input().split()] for j in range(N)])
ans = 0
for i, x in enumerate(Positions):
    for y in Positions[i + 1:]:
        if np.linalg.norm(x - y).is_integer():
            ans += 1
print(ans)

Measured memory_bytes: 12444
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <math.h>

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

using namespace std;

int main(){
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	
	for(int i = 0; i < n; i++){
		cin >> h.at(i);
	}
	sort(h.begin(), h.end());
	long long min_diff = LONG_MAX;
	for(int i = 0; i < n-k+1; i++){
		int max_height = h.at(i+k-1);
		int min_height = h.at(i);
		if(max_height - min_height < min_diff) min_diff = max_height - min_height;
	}
	cout << min_diff << endl;;
}

Measured memory_bytes: 3708
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

#define ll long long 
#define mod 1000000007

int main()
{
	ll n,k;
	cin>>n>>k;
	if(n<k) swap(n,k);
	if(n%3LL==0 || k%3LL==0)
	{
		cout<<0<<endl;
		return 0;
	}
	ll s1,s2,d1,d2,s3=INT_MAX,d3=INT_MAX;
	for(ll i=1;i<k;i++)
	{
		ll q1=i*n;
		ll q2=n/2*(k-i);
		ll q3=(n-n/2)*(k-i);
		 s1=max(q1,max(q2,q3));
		 s2=min(q1,min(q2,q3));
		 s3=min(s3,s1-s2);
	}
	//ll re1=s1-s2;
	swap(n,k);
	for(ll i=1;i<k;i++)
	{
		ll q1=i*n;
		ll q2=n/2*(k-i);
		ll q3=(n-n/2)*(k-i);
		 d1=max(q1,max(q2,q3));
		 d2=min(q1,min(q2,q3));
		 d3=min(d3,d1-d2);
	}
	//ll re2=d1-d2;
	cout<<min(n,min(s3,d3))<<endl;
	return 0;
}

Measured memory_bytes: 256
def minHeapify(x)
  l = 2*x
  r = 2*x+1
  if l <= $n && $heap[l][0] < $heap[x][0]
    minimum = l
  else
    minimum = x
  end
  if r <= $n && $heap[r][0] < $heap[minimum][0]
    minimum = r
  end
  if minimum != x
    $heap[x], $heap[minimum] = $heap[minimum], $heap[x]
    minHeapify(minimum)
  end
end
 
def extract
  key = $heap[1]
  $heap[1] = $heap[$n]
  $n -= 1
  minHeapify(1)
  key
end
 
def insert(key)
  $n += 1
  $heap[$n] = key
  i = $n
  while i > 1 && $heap[i/2][0] > $heap[i][0]
    $heap[i], $heap[i/2] = $heap[i/2], $heap[i]
    i /= 2
  end
end

def dijkstra(n, l, route, cost_d, cost_e)
  done = (n+1).times.map{ [false] * (l+1) }
  while true
    e, s, r = extract
    return e if s == n
    next if done[s][r]
    done[s][r] = true
    route[s].each do |t|
      insert([e + cost_e[s][t], t, r])
      insert([e, t, r - cost_d[s][t]]) if r >= cost_d[s][t]
    end
  end
end

loop do
  n, m, l = gets.split.map(&:to_i)
  break if n == 0
  $heap = []
  $n = 0
  route = (n+1).times.map{ [] }
  cost_d = (n+1).times.map{ [0] * (n+1) }
  cost_e = (n+1).times.map{ [0] * (n+1) }
  m.times.map do
    s, t, d, e = gets.split.map(&:to_i)
    route[s] << t
    route[t] << s
    cost_d[s][t] = cost_d[t][s] = d
    cost_e[s][t] = cost_e[t][s] = e
  end
  insert([0, 1, l])
  p dijkstra(n, l, route, cost_d, cost_e)
end

Measured memory_bytes: 13088