akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair<long long ,long long> ii; 	

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,t;
	cin >> n >> t;
	vector <vector<ll>> dp(n,vector<ll>(6001,0));
	vector <ii> food(n);
	for (int z=0;z<n;z++){
		cin >> food[z].first >> food[z].second;
	}
	sort(food.begin(),food.end());
	ll ans = 0;
	for (int x=food[0].first;x<=t+food[0].first-1;x++){
		dp[0][x] = food[0].second;
		ans = max(ans,dp[0][x]);
	}
	for (int z=1;z<n;z++){
		for (int x=1;x<=t+food[z].first-1;x++){
			dp[z][x] = max(dp[z-1][x],dp[z][x]);
			dp[z][x] = max(dp[z][x],dp[z][x-1]);
			if (x >= food[z].first){
				dp[z][x] = max(dp[z][x],dp[z-1][x-food[z].first]+food[z].second);
			}
			ans = max(dp[z][x],ans);
		}
	}
	cout << ans << endl;
}


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


int main() {
  int k;
  cin >> k;
  string s;
  cin >> s;
  
  if (s.size() > k) {
    cout << s.substr(0, k) << "..." << endl;
  } else {
    cout << s << endl;
  }
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define p pair<LL,LL>
#define x first
#define y second
int main(){
	LL n;
	cin >> n;
	p val[n];
	for(LL i = 0; i < n; i++) cin >> val[i].x >> val[i].y;
	for(LL i = 0; i < n; i++){
		val[i].x += val[i].y;
	}
	LL ans = 0;
	sort(val,val+n);
	reverse(val,val+n);
 
	for(LL i = 0; i < n; i++){
		val[i].x -= val[i].y;
	}
	LL k = n/2;
	LL dp[k+1][k+1];
	for(LL i = 0; i <= k; i++){
		for(LL j = 0; j <= k; j++){
			dp[i][j] = 1e17;
		}
	}
	dp[0][0] = 0;
	for(LL i = 0; i <= k; i++){
		for(LL j = 0; j <= k; j++){
			if(i > 0){
				dp[i][j] = min(dp[i][j], dp[i-1][j] +(i-1)*val[i+j-1].x + (i)*val[i+j-1].y);
			}
			if(j > 0){
				dp[i][j] = min(dp[i][j], dp[i][j-1] +(j)*val[i+j-1].x + (j-1)*val[i+j-1].y);
			}
			//cout << dp[i][j] << " ";
		}
		//cout << endl;
	}
	LL z = dp[k][k];
	if((n % 2) == 1){
		LL dp2[k+1][k+1][2];
		for(LL i = 0; i <= k; i++){
			for(LL j = 0; j <= k; j++){
				dp2[i][j][0] = dp2[i][j][1] = (LL)1e17;
			}
		}
		dp2[0][0][0] = 0;
		for(LL i = 0; i <= k; i++){
			for(LL j = 0; j <= k; j++){
				for(LL r = 0; r <= 1; r++){
					if(i > 0){
						dp2[i][j][r] = min(dp2[i][j][r], dp2[i-1][j][r] +(i-1)*val[i+j+r-1].x + (i)*val[i+j-1+r].y);
					}
					if(j > 0){
						dp2[i][j][r] = min(dp2[i][j][r], dp2[i][j-1][r] +(j)*val[i+j+r-1].x + (j-1)*val[i+j-1+r].y);
					}
					if(r > 0){
						dp2[i][j][r] = min(dp2[i][j][r], dp2[i][j][r-1]+k*val[i+j+r-1].x+k*val[i+j+r-1].y);
					}
				}
			}
		}
		z = dp2[k][k][1];
	}
	cout << z << endl;
}

Measured memory_bytes: 110336
#include<iostream>
using namespace std;
int main(){
int N,ans=0;
int l[1000];
int n[1000];
cin>>N;
for(int i=0;i<N;i++){cin>>l[i]>>n[i];}
for(int i=0;i<N;i++){ans=ans+n[i]-l[i]+1;}
cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

struct Card{
  char suit;
  char value;
};

struct Card C1[101], C2[101];

void trace(struct Card C[], int n)
{
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%c%c",C[i].suit, C[i].value);
  }
  printf("\n");
}

void Bubble(struct Card CB[], int n)
{
  struct Card CB2[101];
  int i,j,mini;
  for(i=0 ; i<n ; i++)
    {
      for(j=n ; j >= i+1 ; j--)
	{
	  if(CB[j].value < CB[j-1].value)
	    {
	      CB2[j] = CB[j];
	      CB[j] = CB[j-1];
	      CB[j-1] = CB2[j];
	    }
	}
    }
  trace(CB,n);
  printf("Stable\n");
}

void Selection(struct Card CS[], int n)
{
  struct Card CS2[101];
  int i,j,mini,count,flag=0;
  for(i=0 ; i<=n ; i++)
    {
      mini = i;
      count=0;
      for(j=i ; j<=n ; j++)
	{
	  if(CS[j].value < CS[mini].value)
	    {
	      mini = j;
	      count=1;
	    }
	}
      if(count==1)
	{
	  CS2[i] = CS[i];
	  CS[i] = CS[mini];
	  CS[mini] = CS2[i];
	}
      if(CS[i].suit != C1[i].suit)
	flag = 1;
    }
  trace(CS,n);
  if(flag==1)
    printf("Not stable\n");
  else printf("Stable\n");
}

int main(){
  
  int n, i,j,mini;
  char ch;

  scanf("%d%c", &n, &ch);
  for ( i = 1; i <= n; i++ ){
    scanf("%c%c%c", &C1[i].suit, &C1[i].value, &ch);
    C2[i]=C1[i];
  }

  Bubble(C1, n);
  Selection(C2, n);
  return 0;
}

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

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif
#if __cplusplus <= 201402L
template <typename T>
T gcd(T a, T b) { return ((a % b == 0) ? b : gcd(b, a % b)); }
template <typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }
#endif
using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
 public:
  string s, t;
  void solve() {
    cin >> s >> t;
    int ls = s.size(), lt = t.size();
    s = '.' + s;
    t = ',' + t;
    vector<vector<vector<int>>> dp(ls + 1, vector<vector<int>>(lt + 1, vector<int>(3)));
    for (int i = 1; i <= ls; ++i) {
      for (int j = 1; j <= lt; ++j) {
        if (s[i] == t[j]) {
          dp[i][j] = {dp[i - 1][j - 1][0] + 1, 1, 1};
        } else {
          if (dp[i - 1][j][0] > dp[i][j - 1][0]) {
            dp[i][j] = {dp[i - 1][j][0], 1, 0};
          } else {
            dp[i][j] = {dp[i][j - 1][0], 0, 1};
          }
        }
      }
    }
    string ans;
    int x = ls, y = lt;
    while (x > 0 && y > 0) {
      if (dp[x][y][1] == 1 && dp[x][y][2] == 1) {
        ans.push_back(s[x]);
      }
      auto tmp = dp[x][y];
      x -= tmp[1];
      y -= tmp[2];
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
  }
};

}  // namespace Problem

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);
  // std::cout << std::fixed << std::setprecision(12);

  Problem::Solver sol;
  sol.solve();
  return 0;
}


Measured memory_bytes: 493056
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

N,M=LI()
graph=[[False]*8 for _ in range(8)]

for _ in range(M):
  a,b=LI()
  a-=1
  b-=1
  graph[a][b]=True
  graph[b][a]=True

def dfs(v,visited):
  all_visited=True
  for i in range(N):
    if not visited[i]:
      all_visited=False
  if all_visited:
    return 1

  ret=0
  for i in range(N):
    if not graph[v][i]:
      continue
    if visited[i]:
      continue
    visited[i]=True
    ret+=dfs(i,visited)
    visited[i]=False

  return ret

visited=[False]*N
visited[0]=True
print(dfs(0,visited))


Measured memory_bytes: 10720
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define dump(a) cout << a << endl; 

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; }

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文
int main() {
	int a, b;
	cin >> b >> a;
	dump(b * b - a);
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 200005
#define P pair<int,int>
#define ll long long
#define mod 1000000007

ll one[300005];
int n;

int main(){
	cin >> n;
	for (int i = 0 ;i<n;++i){
		ll x;
		cin >> x;
		int pos = 0;
		while(x){
			if (x&1){
				++one[pos];
			}
			x /= 2;
			++pos;
		}
	}
	ll ans = 0;
	for (int i = 61; i >= 0; --i){
		ans = (ans*2)%mod;
		ans = (ans + (one[i])*(n - one[i]))%mod;
	}
	cout << ans << endl;

}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std;

const int N=510,mod=1e9+7;
int n,C[N][N],f[N][N];

int dfs(int n,int x){
	if (!n) return!x;
	int &g=f[n][x];
	if (g) return g-1;
	for (int y=x?x:x+2; y<=n; y+=2){
		int s=0;
		rep(z,0,y) s=(s+1ll*C[y][z]*dfs(n-y,abs((x+z*2-y)/2)))%mod;
		g=(g+1ll*C[n][y]*s)%mod;
	}
	return g++;
}

int main(){
	scanf("%d",&n);
	rep(i,0,n) for(int j=C[i][0]=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	int ans=1ll*(dfs(n-1,0)+dfs(n-1,1))*n%mod;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384
n,q=map(int,input().split())
#Range Minimum Query
seg=[]
cnt=-1
inf=2**31-1
while 2**cnt<=n:
	cnt+=1
	seg.append([inf for _ in range(2**cnt)])

def f(i,j):
	Range=(2**(cnt-i)*j,2**(cnt-i)*(j+1)-1)
	if Range[0]>y or Range[1]<x:
		return inf
	elif Range[0]>=x and Range[1]<=y:
		return seg[i][j]
	else:
		return min(f(i+1,2*j),f(i+1,2*j+1))
for _ in range(q):
	c,x,y=map(int,input().split())
	if c==0:
		seg[-1][x]=y
		x//=2
		for j in range(1,cnt+1):
			seg[-j-1][x]=min(seg[-j][x*2],seg[-j][x*2+1])
			x//=2
	else:
		print(f(0,0))



Measured memory_bytes: 8840
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
const ll INF = 1000000000000;
const ll mod = 1000000007;
ll test[12345678][2], aa[1234][1234], bb[1234][1234];
ll dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
char maze[1234][1234];
signed main() {
	ll n, m, k, cnt = 1, ans = 0; cin >> n >> m;
	for (int h = 2; h <= 9; h++) {
		for (int i = 2; i <= 9; i++) {
			if (h * 10 + i <= m && h * i <= n) {
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main(){
    int r, c;
    cin >> r >> c;
    int t[r+1][c+1] = {};
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> t[i][j];
            t[i][c] += t[i][j];
            t[r][j] += t[i][j];
            t[r][c] += t[i][j];
        }
    }
    for(int i = 0; i <= r; i++){
        for(int j = 0; j <= c; j++){
            if(j > 0) cout << " ";
            cout << t[i][j];
        }
        cout << endl;
    }
    return 0;
}



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

int main() {
	int n;
  	cin>>n;
  
  	//1桁が9
  	//3桁が900
  	//5桁が90000
  
  	int waru;
  	int m=n;
  
  	while(m>=10){
    	waru++;
      	m /=10;
    }
  
  if(waru==0){
  	cout<<n<<endl;
  }
  
  else if(waru==1){
  	cout<<9<<endl;
  }
  
  else if(waru==2){
  	cout<<n-90<<endl;
  }
  
  else if(waru==3){
  	cout<<909<<endl;
  }
  //-9999+900+9
  else if(waru==4){
  	cout<<n-9090<<endl;
  }
  
  else if(waru==5){
  	cout<<90909<<endl;
  }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int num = sc.nextInt();
  int[] numbers = new int[num];
  for (int i = 0; i < num; i++) {
   numbers[i] = sc.nextInt();
  }
  Arrays.sort(numbers);
  System.out.println(Math.abs(numbers[0] - numbers[num-1]));
 }
}

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



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

    int cnt = 0, len = 0;
    for (int i = 1; i <= n; i++){
        int p;
        cin >> p;
        if (p == i) len++;
        else{
            cnt += (len + 1) / 2;
            len = 0;
        }
    }
    cnt += (len + 1) / 2;

    cout << cnt << endl;
    
    return 0;
}

Measured memory_bytes: 256
from collections import deque

n = int(input())
x = input()

memo = {0: 0}

def solve(X):
    x = X
    stack = deque([])
    while x:
        if x in memo:
            break
        stack.append(x)
        x = x % bin(x).count("1")
    cnt = memo[x] + 1
    while stack:
        x = stack.pop()
        memo[x] = cnt
        cnt += 1
    return cnt - 1



ans = []
px = x.count("1")

memo1 = [1 % (px - 1)] if px > 1 else []
memo2 = [1 % (px + 1)]
x1 = 0
x2 = 0

for i in range(n):
    if px > 1:
        memo1.append(memo1[-1] * 2 % (px-1))
    memo2.append(memo2[-1] * 2 % (px+1))

for i in range(n):
    if x[-i-1] == '1':
        if px > 1:
            x1 += memo1[i]
            x1 %= (px-1)
        x2 += memo2[i]
        x1 %= (px+1)

for i in range(n):
    if x[-i-1] == "1":
        if px > 1:
            ans.append(solve((x1-memo1[i])%(px-1)) + 1)
        else:
            ans.append(0)
    else:
        ans.append(solve((x2+memo2[i])%(px+1)) + 1)


for ansi in reversed(ans):
    print(ansi)


    

        


Measured memory_bytes: 101088
# coding: utf-8
# Your code here!

N = int(input())
T = list(map(int, input().split()))
M = int(input())

# print(N)
# print(T)
# print(M)

for i in range(M):
    T2 = T.copy()
    # print(i)
    P, X = map(int, input().split())
    # print(P)
    # print(X)
    T2[P - 1] = X
    # print(T2)
    print(sum(T2))

Measured memory_bytes: 3060
#include<stdio.h>
int main(void)
{
    int x;
    scanf("%d",&x);
    if(x>=1&&x<=9){
        if(x==3||x==5||x==7)
        {
                printf("YES\n");
        }
        else
            printf("NO\n");
    }
    return 0;
}


Measured memory_bytes: 128
import sys
input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())
a=list(mii())
b=list(mii())
k = []
j = 0
na= 0
c = 0
for i in range(n):
    if a[i]<b[i]:
        na +=b[i]-a[i]
        c+=1
    elif a[i] > b[i]:
        k.append(a[i]-b[i])
k.sort()
while na > 0 and k:
    na -=k[-1]
    k.pop(-1)
    c +=1
if na > 0:print(-1)
else:print(c)

Measured memory_bytes: 18760
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s,t;
    cin>>s>>t;
    int m=t.length();
    int n=s.length();
    int ans=-1;
    for(int i=n-m;i>=0;i--){
        for(int j=i;j<i+m;j++){
            if(s[j]!=t[j-i] && s[j]!='?'){
                break;
            }
            if(j==i+m-1)
                ans=i;
        }
        if(ans!=-1){
            for(int j=i;j<i+m;j++){
                s[j]=t[j-i];
            }
            break;
        }
    }
    if(ans==-1)
        cout<<"UNRESTORABLE"<<endl;
    else{
        for(int i=0;i<n;i++){
            if(s[i]=='?'){
                s[i]='a';
            }
        }
        cout<<s<<endl;
    }
    return 0;
}


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

H = list(map(int, input().split()))

A = [[] for i in range(N)]
for m in range(M):
    a, b = map(int, input().split())
    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

ans = 0
for i in range(N):
    ma = -1
    for h in A[i]:
        ma = max(ma, H[h])

    if ma < H[i]:
        ans += 1

print(ans)

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

int main() {
  int L, R;
  cin >> L >> R;
  if (R - L > 2017) {
    cout << 0 <<endl;
  }
  else {
    int N = R - L + 1;
    vector<int> p(N);
    for (int i = L; i < R + 1; i++) {
      p.at(i - L) = i % 2019;
    }
    int m = 2018;
    for (int i = 0; i < N - 1; i++) {
      for (int j = i + 1; j < N; j++) {
        m = min(m, (p.at(i) * p.at(j)) % 2019);
      }
    }
    cout << m <<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
const unsigned int M = 1000000007; 
#define all(v) (v).begin(), (v).end()
#define rall(v) v.rbegin(),v.rend()
#define  pb push_back
#define mpp make_pair
#define int  long long
#define N 100002
#define endl "\n"
#define fr(i,n) for(int i=0;i<n;i++)
int power(int x,int y){int res=1;while(y>0){if(y&1)res=x*res; y=y>>1;x=x*x;}return res;}
int power(int x,int y,int mod){int res=1;while(y>0){if(y&1)res=x*res%mod; y=y>>1;x=x*x%mod;}return res;}

using namespace std;


void nik()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
	#endif
}




 signed main()
{
//nik();

int t=1;
//cin>>t;

while(t--)
{	
	int n,k;
	cin>>n>>k;
	int a[n+1];
	for(int i=1;i<=n;i++)cin>>a[i];
		
	int dp[n+1]={0};
dp[0]=1e17;
	for(int i=2;i<=n;i++)
	{
		dp[i]=1e17;
		for(int j=1;j<=k;j++)
		{
			if(i-j>=1){
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
			}
		}
		
		
	}

	cout<<dp[n]<<endl;
	//for(int i:dp)cout<<i<<" ";

}
 return 0;
}



Measured memory_bytes: 1792
def gcd(x,y):
	a = max(x,y)
	b = min(x,y)

	while a%b!=0:
		r = a%b
		a=b
		b=r
	return b

def main():
	x,y = map(int,input().split())
	print(gcd(x,y))

if __name__ == '__main__':
	main()


Measured memory_bytes: 5600
#include <iostream>

using namespace std;

typedef long long ll;

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

ll lcm(ll a, ll b){
    ll g = gcd(a, b);
    return a / g * b;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    ll ans = 1LL;

    for (int i = 0; i < N; i++) {
        ll T;
        cin >> T;
        ans = lcm(ans, T);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int h = sc.nextInt(), w = sc.nextInt();
            if (h == 0 && w == 0) break;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    System.out.print("#");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}


Measured memory_bytes: 35148
//https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d
//D - Saving Snuuk
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

template< typename T >
struct edge {
	int src, to;
	T cost;
	edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
	edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}
	edge &operator=(const int &x) {
		to = x;
		return *this;
	}
	operator int() const { return to; }
};

template< typename T>
struct node {
	vector<edge<T>> edges;
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< node< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
vector< T > dijkstra(const WeightedGraph< T > &g, int s, vector<int>& prev) {
	const auto INF = numeric_limits<T>::max();
	vector<T> dist(g.size(), INF);
	prev.assign(g.size(),-1);

	using Pi = pair<T, int>; //dist,node id
	priority_queue<Pi, vector<Pi>, greater<Pi>> que;
	dist[s] = 0;
	que.emplace(dist[s], s);
	while(!que.empty()) {
		T cost;
		int idx; //node id
		tie(cost, idx) = que.top();
		que.pop();
		if(dist[idx] < cost)
			continue;
		for(auto &e : g[idx].edges) {
			auto next_cost = cost + e.cost;
			if(dist[e.to] <= next_cost)
				continue;
			dist[e.to] = next_cost;
			prev[e.to] = idx;
			que.emplace(dist[e.to], e.to);
		}
	}
	return dist;
}

int main() {
#if LOCAL&01
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#else
    cin.tie(0);
    ios::sync_with_stdio(false);
#endif
    ll n,m,s,t; cin>>n>>m>>s>>t;
    WeightedGraph<ll> graph_a(n+1), graph_b(n+1);
    REP(i,m){
        ll u,v,a,b; cin>>u>>v>>a>>b;
        graph_a.at(u).edges.emplace_back(v,a);
        graph_a.at(v).edges.emplace_back(u,a);
        graph_b.at(u).edges.emplace_back(v,b);
        graph_b.at(v).edges.emplace_back(u,b);
    }
    vector<int> tmp;
    constexpr ll INF=numeric_limits<ll>::max();
    auto res_a = dijkstra(graph_a,s,tmp);
    auto res_b = dijkstra(graph_b,t,tmp);
    vector<ll> a_b(res_a.size());
    REP(i,a_b.size()){
        auto ra = res_a.at(i);
        auto rb = res_b.at(i);
        if (ra>=INF||rb>=INF) {
            a_b.at(i)=-1;//INF;
        }else{
            a_b.at(i)=1e15-(ra+rb);
        }
    }
    vector<ll> ans(a_b.size());
    ll max_a=0;
    for(ll i=a_b.size()-1;i>=0;--i){
        auto v=a_b.at(i);
        max_a=max(max_a,v);
        ans.at(i)=max_a;
    }
    FOR(i,1,ans.size()){
        cout<<ans.at(i)<<endl;
    }
#if 0
    REP(i,n){
        ll ans=INF;
        FOR(j,i+1,n+1){
            //if(i>=j)continue;
            auto ra = res_a.at(j);
            auto rb = res_b.at(j);
            if (ra>=INF||rb>=INF) continue;
            ans=min(ra+rb,ans);
        }
        ans=1e15-ans;
        cout<<ans<<endl;
    }
#endif
    return 0;
}

Measured memory_bytes: 20168
import java.util.*

fun main(args:Array<String>){
    val (l,r) = readLine()!!.split(" ").map{it.toLong()}
    var ans = 2020L
    val n = Math.min(r, l + 2020)
    for(i in l .. n){
        for(j in i + 1 .. n){
            ans = Math.min(ans, i % 2019 * j % 2019)
        }
    }
    println(ans)
}

Measured memory_bytes: 38040
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    repeat(i, n) cin >> a[i];
    repeat(i, n) cin >> b[i];
    repeat(i, n) cin >> c[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    
    lint ans = 0;
    repeat(i, n) {
        lint pa = distance(a.begin(), lower_bound(a.begin(), a.end(), b[i]));
        lint pc = distance(upper_bound(c.begin(), c.end(), b[i]), c.end());
        ans += pa * pc;
        //dump(pa); dump(pc); dump(ans); el;
    }
    cout << ans << endl;
}

    

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<short,short> pii;
const int MOD = 1e9 + 7;
const int N = 8000+50;
const int offset = 2000 + 10;

LL quick_inverse(LL n) {
	LL ret = 1;
	int exponent = MOD - 2;
	for (int i = exponent; i; i >>= 1, n = n * n % MOD) {
		if (i & 1) {
			ret = ret * n % MOD;
		}
	}
	return ret;
}

LL invf[N], factor[N];
void get_factorial_inverse(int n) {
	factor[0] = 1;
	for (int i = 1; i <= n; ++i) {
		factor[i] = i * factor[i - 1] % MOD;
	}
	invf[n] = quick_inverse(factor[n]);
	for (int i = n-1; i >= 0; --i) {
		invf[i] = invf[i + 1] * (i + 1) % MOD;
	}
}

int A[200010], B[200010];

LL Map[offset*2+10][offset*2+10];
bool vis[offset*2+10][offset*2+10];

LL calc_x(int n)
{
    LL ans = 0;
    int max_range = 0;
    for (int i=1; i<=n; i++)
    {
        Map[offset + A[i]][offset + B[i]]++;
        Map[offset - A[i]][offset - B[i]]++;
        max_range = max(max_range, A[i]);
        max_range = max(max_range, B[i]);
    }
    queue<pii> q;
    q.push(pii(offset + max_range, offset + max_range));
    vis[offset + max_range][offset + max_range] = true;
    while(!q.empty())
    {
        pii node = q.front(); q.pop();
        int x = node.first, y = node.second;
        if (x < offset && y < offset && Map[x][y])
        {
            LL times = Map[x][y];
            Map[x][y] = (Map[x+1][y] + Map[x][y+1]) % MOD;
            ans += (times * Map[x][y]) % MOD;
        }
        else
        {
            if (x < offset + max_range) Map[x][y] += Map[x+1][y];
            if (y < offset + max_range) Map[x][y] += Map[x][y+1];
            Map[x][y] %= MOD;
        }
        if (x > offset - max_range && !vis[x-1][y])
            q.push(pii(x-1,y)), vis[x-1][y] = true;
        if (y > offset - max_range && !vis[x][y-1])
            q.push(pii(x,y-1)), vis[x][y-1] = true;
    }
    return ans;
}

LL f(int x, int y)
{
    return (((factor[x+y] * invf[x]) % MOD) * invf[y]) % MOD;
}

LL calc_t(int n)
{
    LL ans = 0;
    for (int i=1; i<=n; i++)
        ans = (ans + f(2*A[i], 2*B[i])) % MOD;
    return ans;
}

int main()
{
    get_factorial_inverse(8010);
    int n;
    scanf("%d", &n);
    for (int i=1; i<=n; i++)
    {
        scanf("%d%d", A+i, B+i);
    }
    LL ans = 0;
    ans += calc_x(n);
    ans -= calc_t(n);
    ans %= MOD;
    ans = (ans + MOD) % MOD;
    ans *= invf[2];
    ans %= MOD;
    ans = (ans + MOD) % MOD;
    cout << ans;
}


Measured memory_bytes: 143744
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int a = stdIn.nextInt();
		int b = stdIn.nextInt();
		int c = stdIn.nextInt();
		if(a+b+c>=22) {
			System.out.println("bust");
		}else {
			System.out.println("win");
		}
	}

}


Measured memory_bytes: 22996
#include <stdio.h>
int main(void){
	int m,n,i,l,r,max=1,min,ans=0;
	scanf("%d %d",&n,&m);
	min = n;
	for(i=0;i<m;i++){
		scanf("%d %d",&l,&r);
		if(max<l) max = l;
		if(min>r) min = r;
	}
	if(min - max<0) ans = 0;
	else ans = min - max +1;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 128
#include <cstdio>           // printf(), scanf()
#include <algorithm>        // fill(), lower_bound()

using namespace std;
static const int MAX_N = 100000;
static const int INF = 1000000000;

int A[MAX_N];
int dp[MAX_N];
int n;

int
lis()
{
	fill(dp, dp + n, INF);
	for (int i = 0; i < n; ++i)
		*lower_bound(dp, dp + n, A[i]) = A[i];

	return lower_bound(dp, dp + n, INF) - dp;
}

int
main(int argc, char** argv)
{
	int i;

	scanf("%d", &n);
	for (i = 0; i < n; ++i)
		scanf("%d", &A[i]);

	printf("%d\n", lis());
	return 0;
}

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

using namespace std;

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

#define _upgrade ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back

//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}

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

const ll mod = 1e9 + 7;
const ll inf = 1<<29;
const long double pi = 3.14159265358979323846;

// ****************************************CODE***************************************//

int main() {
    _upgrade;

    string s;
    cin >> s;

    for(int i = 0; i < s.length(); i++){
        cout << "x";
    }

    return 0;
}

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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;
const int INF = pow(2, 30) - 1;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

vector<bool> prime_table(int n)
{
    vector<bool> prime(n + 1, true);
    if (n >= 0)
        prime[0] = false;
    if (n >= 1)
        prime[1] = false;
    for (int i = 2; i * i <= n; i++)
    {
        if (!prime[i])
            continue;
        for (int j = i + i; j <= n; j += i)
        {
            prime[j] = false;
        }
    }
    return prime;
}


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

    ll Q;
    string S;
    cin >> Q;
    vector<ll> l(Q),r(Q);
    REP(i,Q){
        cin >> l.at(i) >> r.at(i);
    }

    auto t=prime_table(100000+10);

    vector<ll> vec(100000+10);
    REP(i,vec.size()){
        vec.at(i) = 0;
    }

    for (ll i = 3; i <= 100000; i=i+2) {
        ll j = (i + 1) / 2;
        if(t.at(i)==1&&t.at(j)==1){
            vec.at(i) = vec.at(i - 2) + 1;
        }
        else{
            vec.at(i) = vec.at(i - 2);
        }
    }

    REP(i,Q){
        if(l.at(i)==1){
            cout << vec.at(r.at(i)) - vec.at(l.at(i)-1) << endl;
        }
        else{
            cout << vec.at(r.at(i)) - vec.at(l.at(i)-2) << endl;
        }
        
    }
}


Measured memory_bytes: 5576
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.WriteLine(Solve());
        //Solve();
        return;
    }

    public static string Solve()
    {
        int[] input = ReadInts();
        int a = input[0], b = input[1];
        string ans = "";
        if (a > b)
        {
            for (int i = 0; i < a; i++)
            {
                ans += b.ToString();
            }
        }
        else
        {
            for (int i = 0; i < b; i++)
            {
                ans += a.ToString();
            }
        }
        return ans;
    }

    private static string Read() { return Console.ReadLine(); }
    private static int ReadInt() { return int.Parse(Read()); }
    private static long ReadLong() { return long.Parse(Read()); }
    private static double ReadDouble() { return double.Parse(Read()); }
    private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
    private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
    private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
}


Measured memory_bytes: 11092
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;


int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int K;
    cin >> K;

    deque<int> que;

    const int INF = 1 << 30;
    vector<int> dis(K, INF);
    dis[1] = 1;
    que.push_back(1);

    while (!que.empty()) {
        int x = que.front();
        que.pop_front();

        int d = dis[x];

        {
            int nx = (x + 1) % K;
            if (dis[nx] > d + 1) {
                dis[nx] = d + 1;
                que.push_back(nx);
            }   
        }
        {
            int nx = (x * 10) % K;
            if (dis[nx] > d) {
                dis[nx] = d;
                que.push_back(nx);
            }
        }
    }

    cout << dis[0] << '\n';

    return 0;
}

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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define trav(a, x) for (auto& a : x)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;
#define INF (1ll<<60)

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
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 first = true; string res = "{";
for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); }
res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

bool F[102][10];
ll P[102][11];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int N;
    cin >> N;
    REP(i, N) REP(j, 10) cin >> F[i][j];
    REP(i, N) FOR(j, 0, 10) cin >> P[i][j];
    ll ret = LLONG_MIN;
    FOR(a, 1, (1 << 10) - 1) {
        ll sum = 0;
        REP(i, N) {
            ll open = 0;
            for (int j = 0; j < 10; j++) {
                if (a & (1 << j)) {
                    open += F[i][j];
                }
            }
            sum += P[i][open];
        }
        ret = max(sum, ret);
    }
    cout << ret << endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int K, S;
  int cou = 0;
  cin >> K >> S;
  for (int i=0; i<K+1; i++){
    for (int j=0; j<K+1; j++){
      if (S-i-j <= K && 0<=S-i-j) cou += 1;
    }
  }cout << cou << endl;
}

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

using namespace std;

int main()
{
	long int n;
	scanf("%ld", &n);

	double ceilodd = sqrt(n*1.0);

	bool divisable = false;

	printf("%ld:", n);

	while (n % 2 == 0)
	{
		printf(" 2");
		n /= 2;
	}

	while (n % 3 == 0)
	{
		printf(" 3");
		n /= 3;
	}

	double tmp;

	for (long int i = 5; i <= ceilodd; i += 2)
	{
		divisable = false;
		
		tmp = sqrt(1.0*i);
		for (long int j = 3; j <= tmp; j += 2)
		{
			if (i%j == 0)
			{
				divisable = true;
				break;
			}
		}

		if (divisable == false)
		{
			while (n%i == 0)
			{
				printf(" %ld", i);
				n /= i;
				if (n == 1)break;
			}
			if (n == 1)break;
		}

	}
	
	if (n != 1)
		printf(" %ld", n);


		printf("\n");
	
	return 0;
}

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

using namespace std;

int main(){
  int N, X, Y;
  cin >> N >> X >> Y;
  int x = X-1, y = Y-1;
  int i,j;
  int dis;
  vector<int> ans(N-1,0);
  for(i=0; i<N-1; i++){
    for(j=i+1; j<N; j++){
      dis = min(j-i-1, abs(i-x)+abs(j-y));
      ans.at(dis)++;
    }
  }
  for(i=0; i<N-1; i++){
    cout << ans[i] << endl;
  }
  return 0;
}

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

const int maxn = 1e5 + 10;
int fa[maxn];

int find(int a) {
	return a == fa[a] ? a : fa[a] = find(fa[a]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		fa[a] = b;
	}
}

int main() {
	int n, m;
	cin >> n >> m; for (int i = 0; i <= n; i++)fa[i] = i;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		merge(x, y);
	}
	set<int>s;
	for (int i = 1; i <= n; i++) {
		s.insert(find(i));
	}
	cout << s.size() - 1 << endl;
}

Measured memory_bytes: 7896
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define rep(i, n) for(int i=0;i<(int)(n);i++)

int main(void){
	int a, b;
	scanf("%d%d",&a,&b);
	printf("%d\n",6-a-b);
    return 0; 
}


Measured memory_bytes: 128
n = int(input())
before = [0, 0]
for i in range(n):
    t, a = map(int, input().split())
    if t >= before[0] and a >= before[1]:
        before = [t, a]
    else:
        mul = max((before[0]-1)//t+1, (before[1]-1)//a+1)
        before = [t*mul, a*mul]

print(sum(before))

Measured memory_bytes: 3064
#include <stdio.h>
#define N 1000000
int left_key(int);
int right_key(int);
void maxHeapify(int);

int n,A[N+1];
int main()
{
  int i;
  scanf("%d",&n);
  
  for(i=1;i<=n;i++)
    {
      scanf("%d",&A[i]);
    }
  
  for(i=n/2;i>=1;i--) //???????????°?????????????????§???n/2
    {
      maxHeapify(i);
    }
  
  for(i=1;i<=n;i++)
    {
      printf(" %d",A[i]);
    }
  
  printf("\n");
  return 0;
}
void maxHeapify(int x)
{
  int l=0,r=0,largest=0;
  int es_largest=0; //??\???????????????????????¨???
  l=left_key(x);
  r=right_key(x);
  
  if(l<=n&&A[l]>A[x]) largest=l;
  else largest=x;
  
  if(r<=n&&A[r]>A[largest]) largest=r;
  
  if(largest!=x)
    {
      es_largest=A[largest];
      A[largest]=A[x];
      A[x]=es_largest;
      maxHeapify(largest);
    }
} 

int left_key(int x)
{
  return 2*x;
}
int right_key(int x)
{
  return 2*x+1;
}

Measured memory_bytes: 4612
import Control.Monad

lunlunNum = [1..9] ++ (lunlunNum >>= lunlunGen)

lunlunGen :: Int -> [Int]
lunlunGen x = do 
  let d = x `mod` 10
  t <- [d - 1, d, d + 1]
  guard $ t >= 0 && t <= 9
  return $ 10 * x + t

main = do
  n <- readLn 
  print $ lunlunNum !! (n - 1)

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

#define ll long long
#define INF 99999999
#define INF_LL 1LL << 60
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

ll nCr(ll n,ll r){
    if(r==1)return n;
    if(r==2)return n*(n-1)/2;
    return n*(n-1)*(n-2)/6;
}

int main()
{
    int N;
    cin >> N;
    vector<ll> A(N);
    vector<ll>nums(N+1,0);
    rep(i,N)
    {
        cin >> A[i];
        nums[A[i]-1]++;
    }
    ll total = 0;
    rep(i, nums.size())
    {
        total += nCr(nums[i],2);
        //total += nums[i] * (nums[i]-1) /2;
    }

    rep(i,N)
    {
        ll tmp = nums[A[i]-1]-1;
        cout << total - tmp << endl;
    }
}


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

int main() {
    ll X, Y;
    cin >> X >> Y;

    int ans = 0;
    while (X <= Y) {
        X *= 2;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <vector>
#include <cfloat>
#include <string>
#include <cmath>
#include <set>
#include <cstdlib>
#include <map>
#include <ctime>
#include <iomanip>
#include <functional>
#include <deque>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <stack>
#include <climits>
#include <sys/time.h>
#include <cctype>

using namespace std;

typedef long long ll;

// ????????°????????§??°
#define MAX_V 100000

vector <int> graph[MAX_V];
bool vis[MAX_V];
// ord:??±???????????¢?´¢??§??????????????????????¨?????????????
// lowlink:????????????????????\??????0?????\??????dfs??§??????????????£???????????????1????????£?????????????????????????°????ord
int ord[MAX_V], parent[MAX_V], lowlink[MAX_V], timer;

set <int> ap;

vector <pair<int, int> > edges;
vector <pair<int, int> > bridge;

void dfs(int current, int prev) {
  ord[current] = lowlink[current] = timer;
  timer++;

  vis[current] = true;

  int next;
  for (int i = 0; i < graph[current].size(); i++) {
    next = graph[current][i];
    if (!vis[next]) {
      parent[next] = current;

      dfs(next, current);
      lowlink[current] = min(lowlink[current], lowlink[next]);
    }else if (next != prev) {
      lowlink[current] = min(lowlink[current], ord[next]);
    }
  }
}

// 1.??°??????????????£???????????????????????¶
void init_art() {
  memset(vis, false, sizeof(vis));
  timer = 1;
  dfs(0, -1);
}

// 2.?????????????????????
void make_artpoints(int n) {
  int np = 0;
  for (int i = 1; i < n; i++) {
    int p = parent[i];
    if (p == 0) np++;
    else if (ord[p] <= lowlink[i]) ap.insert(p);
  }

  if (np > 1) ap.insert(0);
}

int main() {
  int v, e;
  cin >> v >> e;

  for (int i = 0; i < e; i++) {
    int s, t;
    cin >> s >> t;
    graph[s].push_back(t);
    graph[t].push_back(s);
    if (s > t) swap(s, t);
    edges.push_back(make_pair(s, t));
  }
  sort(edges.begin(), edges.end());
  init_art();
  make_artpoints(v);
  for (set<int>::iterator it = ap.begin(); it != ap.end(); it++) {
    cout << *it << endl;
  }
}

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

int n, ans = 1;
map<char, int> cnt;
char s[300000];

int main() {
    scanf("%d%s", &n, s);
    for(int i = 0; i < n; ++i) cnt[s[i]]++;
    for(auto g : cnt) {
        ans = 1LL * ans * (g.second + 1) % 1000000007;
    }
    cout << ans - 1;
    return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        taskA();
    }

    public static void taskA(){

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();

        int count = 0;

        for(int i = 1; i <= n; i++){
            if(i % 2 != 0) count++;
        }

        double d = (double) count / n;

        System.out.println(d);
    }
}


Measured memory_bytes: 22996
#include<bits/stdc++.h>
#define mp make_pair
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define sci(x) scanf("%d",&x)
#define scs(s) scanf("%s",s)
#define scc(c) scanf("%c",c)
#define scd(d) scanf("%lf",&d)
#define scld(ld) scanf("%Lf",&ld)
using namespace std;

//********************************************
//Error tracking
#define show(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

vector<string> split(const string& s, char c) {
    vector<string> v;
    stringstream ss(s);
    string x;
    while (getline(ss, x, c))
        v.emplace_back(x);
    return move(v);
}

void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
    cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
    err(++it, args...);
}
//********************************************

const int NMAX = 100005;

int n, a[NMAX];

int main()
{
 //   freopen("input","r",stdin);
  //  freopen("output","w",stdout);
    cin.sync_with_stdio(false);
	
	int i;
	cin >> n;
	for (i = 1; i <= n; i++) cin >> a[i];

	int nr = 0, last = 0;
	for (i = 2; i <= n; i++)
		if (last == 0)
		{
			if (a[i] > a[i - 1]) last = 1;
			else if (a[i] < a[i - 1]) last = 2;
		}
		else if (a[i] == a[i - 1]) continue;
		else if (last == 1 && a[i] > a[i - 1]) continue;
		else if (last == 2 && a[i] < a[i - 1]) continue;
		else
		{
			nr++;
			last = 0;
		}

	nr++; //last

	cout << nr << "\n";
    return 0;   
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <stdio.h>
#include <cstdlib>
#include <map>
#include <set>
#include <stack>
#define Endl endl

typedef  long long ll ;
using namespace  std;
ll mod=1e9+7;




int main(){


    int n;cin>>n;
    int tt=n/1000;
    if(tt*1000==n) cout<<0<<endl;
    else{
        cout<<(tt+1)*1000-n<<endl;
    }

    return 0;
}


Measured memory_bytes: 3176
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

int main(void){
	int N,A,B,d;
	cin>>N>>A>>B;
	d=abs(A-B);
	if(d%2==1){
		printf("Borys\n");
	}else{
		printf("Alice\n");
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  double a,b;
  cin>>a;
  b=a/3;
  cout<<fixed<<setprecision(12)<<b*b*b;
}


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

int main(){
	int n;
	cin >> n;
	long long count = 0;
	vector<int> a(n), b(n), c(n);
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	for(int i=0; i<n; i++){
		cin >> b[i];
	}
	for(int i=0; i<n; i++){
		cin >> c[i];
	}
	sort(a.begin(), a.end());
	sort(c.begin(), c.end());
	for(auto i: b){
		vector<int>::iterator c_itr = upper_bound(c.begin(), c.end(), i);
		auto a_itr = lower_bound(a.begin(), a.end(), i);
		int c_num = c.end() - c_itr;
		count += (long)c_num * (a_itr - a.begin());
	}
	cout << count;
	return 0;
}



Measured memory_bytes: 1408
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

int main() {
	string S;
	cin >> S;
	int ans = 0;
	for (int i = 0; i < S.size() - 1; i++) {
		if(S.at(i) == S.at(i + 1)){
			if (S.at(i + 1) == '0') {
				S.at(i + 1) = '1';
			}
			else {
				S.at(i + 1) = '0';
			}
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 512
def SelectionSort(A, N):
    cnt=0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[minj] > A[j]:
                minj = j
        if minj != i:
            cnt +=1
        A[i], A[minj] = A[minj], A[i]       
    return A, cnt

N = int(input())
A = list(map(int, input().split()))

ans, cnt = SelectionSort(A, N)

print(*A)
print(cnt)


Measured memory_bytes: 5608