akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RNG(i,from,to) for(int i=(from); i<(int)(to); i++)
#define gcd(i,j) __gcd((i), (j))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vecll;
template<typename S, typename T> string to_string(pair<S, T> p) { return "("+to_string(p.first)+","+to_string(p.second)+")"; }
template<typename T> string to_string(T p[2]) { return "["+to_string(p[0])+","+to_string(p[1])+"]"; }
template<typename T> void println(T e){ cout << to_string(e) << endl; }
template<typename T> void println(const vector<T>& v){ cout << "[";for(const auto& e : v){ cout << to_string(e) << ","; }cout << "]";cout << endl; }
template<typename T> void println(const vector<vector<T>>& vv){ for(const auto& v : vv){ println(v); } }
template<typename Iter> void println(Iter first, Iter last){ for(auto it=first; it != last; it++){ cout << *it << " "; }; cout << endl; }
template<typename T> T mod_pow(T x, T n, const T &p) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; }
template<typename T> T mod_inv(T x, const T &p) { return mod_pow(x, p-2, p); }
const ll DVSR = 1e9+7;


int main(int argc, char const *argv[])
{
  ll A,B,C,D; cin >> A >> B >> C >> D;
  cout << min(A,B) + min(C,D) << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#include<set>
#include<complex>
#include<map>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define CC puts("-------ok--------");
#define all(in) in.begin(), in.end()
using namespace std;
typedef pair<int, int> pii;
#define MAX 99999999
int main(){
    int n;
    cin>>n;
    vi v(n+1,0);
    rep(i,n*(n-1)/2){
        pii a,b;
        cin>>a.first>>b.first;cin>>a.second>>b.second;
        if(a.second==b.second){v[a.first]++; v[b.first]++;}
        else{
            a.second>b.second ? v[a.first]+=3:v[b.first]+=3;
        }
    }
        vi hoge;
        rep(i,n)hoge.push_back(v[i+1]);
        sort(hoge.begin(),hoge.end(),greater<int>());
        rep(i,n){
            for(int j=0;j<n;j++){
                if(hoge[j]==v[i+1]){cout<<j+1<<endl; break;}
            }
        }
    }

Measured memory_bytes: 3152
def main():
  n, a, b = list(map(int, input().split()))
  if(a == 0):
    print(0)
    return
  p = n % (a+b)
  if(p <= a):
    print(a * (n // (a+b)) + p)
  else:
    print(a * (1 + n//(a+b)))
  return

main()

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


def solve(A: int, B: int, C: int, D: int):
    L = A + B
    R = C + D

    if L > R:
        print("Left")
    elif L < R:
        print("Right")
    else:
        print("Balanced")


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long int 
#define INF 1e9+5
signed main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    vector<int> dp(n,INF);
    dp[0]=0;
    for(int i=0;i<n;i++)
    {
        for(int j:{i+1,i+2})
        {
            if(j<n)
            dp[j]=min(dp[j],dp[i]+abs(a[i]-a[j]));
        }
    }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <numeric>

int main()
{
	int n, m;

	std::cin >> n >> m;

	std::vector<std::vector<int> > v(n, std::vector<int>(n, 0));

	for (int i = 0; i < m; i++) {
		int a, b;

		std::cin >> a >> b;
		a--;
		b--;
		v[a][b]++;
		v[b][a]++;
	}

	for (int i = 0; i < n; i++) {
		std::cout << std::accumulate(v[i].begin(), v[i].end(), 0) << std::endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;

	void run() {
		Scanner sc = new Scanner(System.in);
//		for(;;) {
			int n = sc.nextInt();
			long ans[][] = new long[2][21];
			ans[0][sc.nextInt()] = 1;
			for(int i=0;i<n-2;i++) {
				int val = sc.nextInt();
				fill(ans[i%2==0? 1:0],0);
				for(int j=0;j<=20;j++) {
					if(j+val<=20) ans[i%2==0?1:0][j+val] += ans[i%2==0?0:1][j];
					if(j-val>=0)  ans[i%2==0?1:0][j-val] += ans[i%2==0?0:1][j];
				}
//				debug(val);
//				debug(ans[i%2==0?1:0]);
			}
			System.out.println(ans[n%2][sc.nextInt()]);
//		}
	}
	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define endl '\n'
#define inf 9223372036854775807
#define maxn 3000001
#define mod (ll)(1e9+7)
#define int ll
 
using namespace std;
 
void io(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}

int t,n,d,l,r;


int32_t main(){
io();
IOS;    
		cin>>n>>d;
		int ans=0;
		while(n--){
			int x,y;cin>>x>>y;
			int sum=x*x+y*y;
			if(sum<=d*d){
				ans++;
			}
		}
		cout<<ans<<endl;


       



        

        


        
    
        
        
                


 
        
 
 
 
        
 
 
 
 
        
        
 
        
        
 
    
    
    
    
 
 
       
 
 
 
 
      
   
 
 
 
 
}

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

using namespace std;
typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> PI; 
typedef pair<LL,LL> PLL;
typedef unsigned long long ULL;
typedef pair<double,double> PD;

#define FOR(x, b, e) for(int x = b; x<= (e); x++)
#define FORD(x, b, e) for(int x = b; x>= (e); x--)
#define REP(x, n) for(int x = 0; x<(n); ++x)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())

#define PB push_back
#define IN insert
#define ST first
#define ND second
#define INF 2000000011
#define MOD 1000000007

#define MAXSIZE 3005

double dp[MAXSIZE][MAXSIZE];	//[tura][p. wyrzucenia]

int n;

int main(){	//fajne nawet, ej
	
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n;
	
	dp[0][0]=1; //p. nie wyrzucenia wgl
	
	FOR(i,1,n){
		double d;
		cin>>d;
		double odwr=1-d;
		
		FOR(j,0,i){
			dp[i][j]+=dp[i-1][j]*odwr;
			dp[i][j+1]+=dp[i-1][j]*d;
		}
	}
	
	double wyn=0;
	FOR(i,n/2+1,n)
		wyn+=dp[n][i];
	
	cout.precision(10);
	cout<<wyn;
	
	return 0;
}


Measured memory_bytes: 68992
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << ele << endl
#define print10(ele) cout << fixed << setprecision(10) << ele << endl

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  int n, m;
  cin >> n >> m;
  ivec s(m);
  svec c(m);
  REP(i, m) { cin >> s[i] >> c[i]; }
  svec ans(n);
  REP(i, n) { ans[i] = "a"; }
  REP(i, m) {
    if (ans[s[i] - 1] != "a" && ans[s[i] - 1] != c[i]) {
      print(-1);
      return 0;
    }
    ans[s[i] - 1] = c[i];
  }
  if (ans[0] == "0") {
    if (ans.size() == 1) {
      print(ans[0]);
      return 0;
    }
    print(-1);
  } else {
    REP(i, n) {
      if (ans.size() == 1 && ans[0] == "a") {
        print(0);
        return 0;
      }
      if (ans[0] == "a" && i == 0)
        cout << 1;
      else
        cout << (ans[i] != "a" ? ans[i] : "0");
    }
    cout << endl;
  }

  return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<vector>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)//初期値a,i<bの範囲でループ
#define REP(i,n) FOR(i,0,n)//初期値0,i<nの範囲でループ
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;



int main(){
    int n;
    ll a[200400];
    cin>>n;
    REP(i,n)cin>>a[i];
    ll b[200400];
    int hn=n/2;
    if(n%2==0){
        REP(i,n){
            if(i%2==1)b[hn-(i+1)/2]=a[i];
            if(i%2==0)b[hn+i/2]=a[i];
        }
    }
    else{
        REP(i,n){
            if(i%2==1)b[hn+(i+1)/2]=a[i];
            if(i%2==0)b[hn-i/2]=a[i];
        }
    }
    REP(i,n)cout<<b[i]<<" ";
    //else REP(i,n)cout<<b[n-i]<<" ";
    
    

    return 0;
}

Measured memory_bytes: 5248
def main():
    n = int(input())
    l = []
    
    if(n<0 or n>1000000000):
        main()
    
    
    if(n!=0):
        h1 = int(n/500)*1000
        ar = n - (int(n/500)*500)
        h1+=int(ar/5)*5
        h2 = int(n/5)*5
        
        l.append(h1)
        l.append(h2)
        print(max(l))
    else:
        print(0)

main()    


Measured memory_bytes: 3064
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()

#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
#define MAX_N (100001)
typedef long long ll;

using namespace std;

int fac[200001];
int rfac[200001];

int combi(int n, int r) {
	//if (r < 0 || n < r) return 0;
	//if (n - r < r) return combi(n, n - r);
	int res = 1;
	res = res * fac[n] %MOD;
	res = res * rfac[n - r] % MOD;
	res = res * rfac[r]%MOD;
	//cout << n << " " << r << " " << res << endl;
	return res;
}

int modpow(int n, int a) {
	int res = 1;
	while (a > 0) {
		if (a & 1) res = res * n % MOD;
		n = n * n % MOD;
		a >>= 1;
	}
	return res;
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	fac[0] = rfac[0] = 1;
	for (int i = 1; i < 200001; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		rfac[i] = modpow(fac[i], MOD - 2);
	}
	int h, w; cin >> h >> w;
	int a, b; cin >> a >> b;
	int ans = 0;
	rep(i, h - a) {
		int k = (combi(b + i -1, b - 1) * combi(h + w - 2 - b - i, w - b - 1))%MOD;
		//cout << k << endl;
		ans = (ans + k) % MOD;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main(){
    ll n, m; cin >> n >> m;
    ll dp [n + 1];
    memset(dp, -1, sizeof(dp));
    vector<ll> a(n + 1);

    rep(i, m){
        cin >> a[i];
        dp[a[i]] = 0;
    }

    dp[0] = 1;
    if(a[0] != 1){
        dp[1] = 1;
    }
    _rep(i, 2, n + 1){
        if(dp[i] == -1){
            dp[i] = dp[i - 1] + dp[i - 2];
            dp[i] %= mod;
        }
    }
    //cout << dp[1] << " " << dp[2] << endl; 
    cout << dp[n] << endl;
}

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

int main(){
  int dx[8]={1,0,-1,0,1,-1,-1,1};
  int dy[8]={0,1,0,-1,1,1,-1,-1};
  
  int h,w;
  cin >> h >> w;
  
  string s[50];
  rep(i,h) cin >> s[i];

  rep(i,h){
    rep(j,w){
      if(s[i][j]=='#') continue;

      int count=0;
      rep(k,8){
	int x = i+dx[k];
	int y = j+dy[k];

	if(x<0 or h<=x) continue;
	if(y<0 or w<=y) continue;
	if(s[x][y] == '#') count++;
      }

      s[i][j] = char('0'+count);
    }
  }

  rep(i,h) cout << s[i] << endl;
  
  return 0;
}


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

int main() {
  int n, m, p = 0, ans = 0;

  cin >> n >> m;

  vector<int> a(n);

  for (int i = 0; i < m; i++) {
    int k;
    cin >> k;
    for (int j = 0; j < k; j++) {
      int s;
      cin >> s;
      s--;
      a[s] |= 1 << i;
    }
  }

  for (int i = 0; i < m; i++) {
    int x;
    cin >> x;
    p |= x << i;
  }

  for (int s = 0; s < (1 << n); s++) {
    int t = 0;
    for (int i = 0; i < n; i++) {
      if (s >> i & 1) {
        t ^= a[i];
      }
    }
    if (t == p) ans++;
  }

  cout << ans;

  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;                                                                                                                          

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();

        if(a < b) {
            System.out.println("a < b");
        } else if (a > b) {
            System.out.println("a > b");
        } else {
            System.out.println("a == b");
        }
    }
}

Measured memory_bytes: 25928
# coding: utf-8
import sys

d = {}
for line in sys.stdin:
    s = line.strip()
    if not s in d: 
        d[s] = 1
    else:
        d[s] += 1

max_num = max(d.values())

ans = [int(key) for key, value in d.items() if value == max_num]
for i in sorted(ans):
    print(i)



Measured memory_bytes: 5604
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		double a=0;
		int i=0;
		while(a<n) {
			i++;
			a=Math.floor((i)*1.08);
			
			
		}
		if(n==a) {
			System.out.println(i);
		}
		else {
			System.out.println(":(");
		}
		
	}
}

Measured memory_bytes: 22996
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
K = int(input())

if e-d <= K and e-c <= K and e-b <= K and e-a <= K and d-c <= K and d-b <= K and d-a <= K and c-b <= K and c-a <= K and b-a <= K:
  print("Yay!")
else:
  print(":(")

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

#define ll long long int
#define str string

ll MOD = 1000000007, INFL = 1ll << 60, INF = 1 << 30, mod = 1e9 + 7, Max = INF, Min = -1;
double a = 0, b = 0, c = 0, n = 0, sum = 0;
ll A[500000] = {}, B[500000] = {}, ruiseki[500000] = {}, dp[100][10] = {};
int dy[] = { 0, 0, 1, -1 }, dx[] = { 1, -1, 0, 0 };
vector <ll> v;
str S, T;
bool check = false, check2 = false;

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

int main() {

	//Code Line
	cin >> n;
	a = n;
	for (int i = 0; i < 2; i++) {
		n *= a;

	}
	cout << n << endl;


	return 0;
}



Measured memory_bytes: 256
#include<math.h>
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define    ll   long long int
#define    py   printf("Yes\n")
#define    pn   printf("No\n")
#define    in   cin>>
using namespace std;

ll f(ll n)
{
  return n*n*n*n*n;
}
int main()
{
  ll i,j,x,a,b;
  in x;
  for ( i = -500; i <=500; i++)
  {
    for ( j = -500; j <=500; j++)
    {
      if(f(i)-f(j)==x){
        a=i;
        b=j;
      }
    }
  }
  cout<<a<<" "<<b<<endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
int judg(){
  int A, B, C, K, sum = 0;
  cin >> A >> B >> C >> K;
  if (K < 0) return sum;
  
  if(K - A > 0){
    K -= A;
    sum += A;
  }else
    return sum + K;

  if(K - B > 0) K -= B;
  else return sum;

  return sum - K;
}

int main()
{
  cout << judg() << endl;
  return 0;
}

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

typedef long long ll;

int main() {
    int n;cin>>n;
    
    ll L[87];
    L[0]=2;
    L[1]=1;
    
    for(int i=2;i<=n;++i){
        L[i]=L[i-1]+L[i-2];
    }
    cout<<L[n]<<endl;
	return 0;
}

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



int main(){
    int N;
    cin >> N;
    vector<tuple<int, int>> xy;
    int x_i, y_i;
    tuple<int, int> data;
    for (int i = 0; i < N; i++){
        cin >> x_i >> y_i;
        data = make_tuple(x_i, y_i);
        xy.push_back(data);
    }
    long double distance_sum = 0;
    sort(xy.begin(), xy.end());
    do {
        int now_x, now_y;
        int tar_x, tar_y;
        now_x = get<0>(xy.at(0));
        now_y = get<1>(xy.at(0));
        for (auto xy_i: xy){
            tar_x = get<0>(xy_i);
            tar_y = get<1>(xy_i);
            distance_sum += sqrt(pow((now_x - tar_x), 2) + pow((now_y - tar_y), 2));
        }
    }while(next_permutation(xy.begin(), xy.end()));
    int num_route = 1;
    for(int i = 1; i <= N; i++){
        num_route *= i;
    }
    cout << fixed << setprecision(15) << distance_sum / num_route << endl;
}

Measured memory_bytes: 3848
N,M,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

a,b = [0],[0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])

ans,j = 0,M
for i in range(N+1):
    if a[i]>K:
        break    
    while b[j]>K-a[i]:
        j -= 1    
    ans = max(ans,i+j)
print(ans)

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


int main() {
	ll H;
	cin >> H;
	ll ans = 1;
	int i = 0;
	while (H > 1) {
		H = H / 2;
		i++;
		ans += pow(2, i);
	}

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

Measured memory_bytes: 256
N = int(input())

mod = 10**9+7

dic = {}
L = [1]*(N+1)
L[0] = 0
L[1] = 0
for i in range(2, N+1):
    j = 2
    while i*j < N+1:
        L[i*j] = 0
        j += 1
        
for i in range(N+1):
    if L[i] == 1:
        dic[i] = 0

if N > 1:
    for i in range(2, N+1):
        j = 2
        while i > 1:
            if L[j] == 1 and i%j == 0:
                dic[j] += 1
                i //= j
            else:
                j += 1
            
    ans = 1
    for i in dic:
        if dic[i] > 0:
            ans *= (dic[i]+1)
            ans %= mod
else:
    ans = 1
        
print(ans)

Measured memory_bytes: 3064
def test_case():
    while True:
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            break
        lead_s = '.'.join(['#' for _ in range(b)])[:b]
        lead_d = '#'.join(['.' for _ in range(b)])[:b]
        for idx, _ in enumerate(range(a)):
            if idx % 2 == 0:
                print(lead_s)
            else:
                print(lead_d)
        print('')


if __name__ == "__main__":
    test_case()



Measured memory_bytes: 5620
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
  ll n,m,k;
  cin>>n>>m>>k;
  vector<ll> a(n);
  vector<ll> b(m);
  for(ll &x : a) cin>>x;
  for(ll &x : b) cin>>x;
  int i=0;
  while(i<n && k-a[i]>=0)
  {
    k-=a[i++];
  }
  int ans = i;
  for(int j=0;j<m;j++)
  {
    //cout<<(k)<<endl;
    while(i>0 && k-b[j]<0)
    {
      i--;
      k = k+a[i];
    }
    if(b[j]>k) break;
    k = k-b[j]; 
    ans = max(ans,i+j+1);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 6352
import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    if ANS[x + 1] is None:
        x1 = f(x + 1)
        ANS[x + 1] = x1
    else:
        x1 = ANS[x + 1]

    if ANS[x + 2] is None:
        x2 = f(x + 2)
        ANS[x + 2] = x1
    else:
        x2 = ANS[x + 2]

    ans = x1 + x2
    # ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)


Measured memory_bytes: 494308
#include<bits/stdc++.h>
using namespace std;
#define lli long long
#define llmax LLONG_MAX   //ranges are defined in climits
#define llmin LLONG_MIN
#define imax INT_MAX
#define imin INT_MIN
#define pb push_back
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);
  int sx,sy,tx,ty;cin>>sx>>sy>>tx>>ty;
  for(int i=0;i<(ty-sy);i++)  cout<<"U";
  for(int i=0;i<(tx-sx);i++)  cout<<"R";
  for(int i=0;i<(ty-sy);i++)  cout<<"D";
  for(int i=0;i<(tx-sx);i++)  cout<<"L";

  cout<<"L";
  for(int i=0;i<=(ty-sy);i++)  cout<<"U";
  for(int i=0;i<=(tx-sx);i++)  cout<<"R";
  cout<<"D";
  cout<<"R";
  for(int i=0;i<=(ty-sy);i++)  cout<<"D";
  for(int i=0;i<=(tx-sx);i++)  cout<<"L";
  cout<<"U";
	return 0;
}

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

using namespace std;

using ll = long long;

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

    string s;
    cin >> s;
    cout << s[0] + to_string(s.size() - 2) + s.back() << endl;

    return 0;
}


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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int cou = 0;
    for(int i = a; i <= b; i++) {
        if(c % i == 0) cou++;
    }
    cout << cou << endl;
    return 0;
}


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

int main() {
  int N,M,A,B,i;
cin>>N>>M;
B=1;
A=M;
i=M/N;
while(i>1){
if(M%i==0){
B=i;
break;
}
i=i-1;
}
cout<<B<<endl;
}

Measured memory_bytes: 256
// abc136c.cpp : Build Stairs
#include <bits/stdc++.h>
using namespace std;
#define in(x) cin>>(x)
void bye(auto x, int code=0){cout<<(x)<<endl;exit(code);}

int main(){
  int n; in(n);
  int a = -1;
  for(int i=0;i<n;i++){
    int h; in(h);
    if(a>h) bye("No"); else if(a<h) a = --h;
  }
  bye("Yes");
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main()
{
	char S[20];
	int cnt = 0,i,max;
	scanf("%s", S);
	max = 0;
	for (i = 0; i < strlen(S)+1; i++)
	{
		if (S[i] == 'A' || S[i] == 'G' || S[i] == 'T' || S[i] == 'C')
			cnt++;
		else
		{
			if(cnt>max)
				max = cnt;
			cnt = 0;
		}
	}
	printf("%d", max);
	return 0;
}

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    if (a * b % 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define float long double


int32_t main()
{
	
	IOS
	int n;cin>>n;
	int mn=LLONG_MAX,nc=0,sum=0;
	for(int i=0;i<n;i++)
	{
		int x;cin>>x;sum+=abs(x);nc+=x<0;mn=min(mn,abs(x));
	}
	if(nc&1)sum-=mn<<1;
	cout<<sum<<endl;
}
			

	
	
			
	
		
			
	
		
	
			
	
	
	
	
	

	

	

	
		


Measured memory_bytes: 256
# include <bits/stdc++.h>
# define pb push_back
# define ll long long
# define fi first
# define se second
# define all(vc) vc.begin(),vc.end()
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
# define DEBUG

using namespace std;

const int N = 1e2 + 7;
const int mod = 1e9 + 7;

int n, a[N];
double ans, b;

int main()
{
    speed;
    /// Author: Dilshod--Imomov
    #ifdef DEBUGd
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif // DEBUG
    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> a[i];
        b = 1;
        b /= a[i];
        ans += b;
    }
    ans = 1 / ans;
    cout << setprecision(15) << ans;
}



Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int n;
  int *prime;
  int i,j;
  while(cin >> n){
    //init
    prime = new int[n+1];
    for(i=0; i<=n; i++) prime[i] = 0;

    //素数判定
    for(i=2; i*i<=n; i++){
      if(prime[i] == 0){
	prime[i] = 1; //iは素数
	for(j=2; i*j<=n; j++){//倍数ふるい落とし
	  prime[i*j] = -1;//i*jは素数じゃない
	}
      }
    }
    for(i=i; i<=n; i++){
      if(prime[i] == 0) prime[i] = 1;
    }
    
    //output
    int ans=0;
    for(i=2; i<=n; i++){
      if(prime[i] == 1) {
	ans ++;
	//cout << "prime:" << i << endl;;
      }
    }
    cout << ans << endl;

    delete[] prime;
  }
  return 0;
}

Measured memory_bytes: 5356
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(void) {
	double n;
	cin >> n;
	double ans = n * 2 * acos(-1);
	cout << ans;
}

/*
9   3**2 1
27  3**3 2
81  3**4 3

11121213131415161516
3234566667

	
	*/


Measured memory_bytes: 3784
#include <iostream>
#include <string>

using namespace std;

#define ll long long

string O, E, ans = "";

int main(){
    cin >> O >> E;

    for(int i = 0; i < E.size(); i++){
        ans.push_back(O[i]);
        ans.push_back(E[i]);
    }
    if(O.size() > E.size()) ans.push_back(O.back());

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    #define Mod 1000000007
    #define INF 1e9
    #define INFL 9e18
    #define EPS 1e-9
    #define pb push_back
    #define mp make_pair
    #define SET(a) memset(a,-1,sizeof(a))
    #define CLR(a) memset(a,0,sizeof(a))
    #define CPY(a,b) memcpy(a,b,sizeof(a))
    #define N 200005
    #define fs first
    #define sc second
    #define UNIVISITED 0
    #define EXPLORED 1
    #define VISITED 2

    using namespace std;
    typedef  long long int ll;
    typedef pair<ll,ll> ii;
    typedef vector <ii> vii;
    typedef vector <ll> vi;
   

   


    int main()
    {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b,c,d;
   cin>>a>>b>>c>>d;

ll p=a+b;
ll q=c+d;
if(p>q)
  cout<<"Left";
else if(p==q)
  cout<<"Balanced";
else
  cout<<"Right";




    return 0;


    }

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <limits>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define x first
#define y second
#define sf scanf
#define pf printf
#define vec vector
#define pb push_back
#define mp make_pair
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define clr(a,b) memset(a,b,sizeof(a))
#define bin_cnt(x) __builtin_popcount(x)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define srep(sub,s) for(int sub=s&(s-1);sub;sub=(sub-1)&s)
#define irep(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define irrep(i,a) for(__typeof(a.rbegin()) i=a.rbegin();i!=a.rend();i++)
#define inf numeric_limits<int>::max()
#define finf numeric_limits<double>::infinity()
#define eps 1e-8
#pragma GCC optimize ("O3")
#define o3 __attribute__((optimize("O3")))
#pragma comment(linker, "/STACK:32505856")

template<class T> inline T sqr(T a) {return a*a;}
template<class T> inline int gmin(T&a,T b) {if(a>b){a=b;return 1;}return 0;}
template<class T> inline int gmax(T&a,T b) {if(a<b){a=b;return 1;}return 0;}
inline int dcmp(const double &a) {return a>eps?1:(a<-eps?-1:0);}
struct Initializer{Initializer(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}}initializer;

#define N 100010
int n, m;
int ans;
map<pii,int> res;
map<int,int> raw, raw_cpy,
             mod, mod_cpy,
             par;

int main() {
    sf("%d%d", &n, &m);
    rep(i, 1, n) {
        int k;
        sf("%d", &k);
        raw[k]++;
        raw_cpy[k]++;
    }

    /// 凑相同的对子
    irep(it, raw_cpy) {
        if (it -> y >= 2) {
            int add = (it -> y) / 2;
            int rem = (it -> y) % 2;
            int mm = (it -> x) % m;
            par[mm] += add;
//            par_cpy[mm] += add;
            raw[it -> x] = rem;
//            pf("raw[%d] = %d\n", it->x, rem);
            ans += add;
        }
    }

    ///剩下的单个的数，对m取模，再相互配对
    irep(it, raw) {
        int ind = (it -> x) % m;
        int amt = (it -> y);
        if (amt > 0) {
            mod[ind] += amt;
            mod_cpy[ind] += amt;
        }
    }

    irep(it, mod_cpy) {
        int p = it -> x;
        int q = m - p;
//        pf("mod[%d] = %d\n", p, it->y);

        if (p == 0) {
            ans += mod[0] / 2;
            mod[0] %= 2;
            continue;
        }
        if (p == q) {
            ans += mod[p] / 2;
            mod[p] %= 2;
            break;
        }
        if (p > q) break;

        int add = min(mod[p], mod[q]);
        mod[p] -= add;
        mod[q] -= add;
        ans += add;
    }

    ///最后剩下的单个的数，考虑拆对子
    irep(it, mod) {
        int p = it -> x;
        int q = m - p;
        if (par.find(q) != par.end()) {
            int parq = par[q];
            int add = min(parq * 2, it -> y);
            ans += add / 2;
        }
    }

    pf("%d\n", ans);
    return 0;
}


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

#define iota(i,n,b,s) for(int i=int(b);i!=int((b)+(s)*(n));i+=(s))
#define range(i,n,m) iota(i,(((n)>(m))?((n)-(m)+1):((m)-(n)+1)),(n),((n)>(m)?-1:1))
#define rep(i,n) iota(i,(n),0,1)

#define INF (1e9)
#define EPS (1e-9)
#define cons(a,b) (make_pair(a,b))
#define car(a) (a.first)
#define cdr(a) (a.second)
#define cadr(a) (car(cdr(a)))
#define cddr(a) (cdr(cdr(a)))
#define all(a) a.begin(), a.end()
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;

typedef long long Integer;
typedef double Real;

template<class S, class T>
ostream& operator<<(ostream& os, pair<S,T> p) {
  os << '(' << car(p) << ", " << cdr(p) << ')';
  return os;
}

template<class T>
ostream& operator<<(ostream& os, vector<T> v) {
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

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

int main() {

more:

  int n; cin >> n;
  if (!n) return 0;

  map<int,int> s;
  vector<int> xs(n);
  vector<int> ys(n);
  rep (i, n) cin >> xs[i];

  for (int k = 0; ; ++k) {
    s.clear();
    for (int x : xs) {
      s[x]++;
    }

    bool ac = true;
    rep (i, n) {
      int x = s[xs[i]];
      if (xs[i] != x) {
        xs[i] = x;
        ac = false;
      }
    }
    if (ac) {
      cout << k << endl;
      cout << xs << endl;
      break;
    }
  }

  goto more;
}

Measured memory_bytes: 1212
h,w = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))

c = [[0] * w for _ in range(h)]
li = [[0,0]]
hw = [0,0]
dir = 'r'

while len(li) < h*w:
    if dir == 'r':
        if hw[1] < h-1:
            if [hw[0], hw[1]+1] not in li:
                hw[1] += 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'd'
        else:
            dir = 'd'
    elif dir == 'd':
        if hw[0] < w-1:
            if [hw[0]+1, hw[1]] not in li:
                hw[0] += 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'l'
        else:
            dir = 'l'
    elif dir == 'l':
        if hw[1] > 0:
            if [hw[0], hw[1]-1] not in li:
                hw[1] -= 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'u'
        else:
            dir = 'u'
    else:
        if hw[0] > 0:
            if [hw[0]-1, hw[1]] not in li:
                hw[0] -= 1
                li.append([hw[0], hw[1]])
            else:
                dir = 'r'
        else:
            dir = 'r'

count = 0

for i in range(n):
    for _ in range(a[i]):
        c[li[count][1]][li[count][0]] = i+1
        count += 1

for i in range(h):
    for j in range(w):
        print(c[i][j],end = ' ')
    print()


Measured memory_bytes: 4852
import sys
N=int(input())
data=[]
for i in range (N):
    X=int(input())
    data.append(X)
button=data[0]
count=1
while button!=2:
    button=data[button-1]
    count+=1
    if count>=N:
        print(-1)
        sys.exit()
print(count)

Measured memory_bytes: 7084
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define endl '\n';
typedef long long ll;
typedef long double ld;
using namespace std;


int main() {
  int n;
  cin >> n;
  vector<int> w(n);
  for (int &x : w) cin >> x;
  int R = accumulate(w.begin(), w.end(), 0);
  int L = 0;
  int ans = 1e9;
  for (int t = 0; t < n - 1; t++) {
    L += w[t];
    R -= w[t];
    ans = min(ans, abs(L - R));
  }
  cout << ans << endl;
  return 0;
}

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

int main(){
    ll N,M;
    cin >> N >> M;
    vector<ll> H(N);
    vector<ll> L(N);
    rep(i,N) cin >> H[i];
    rep(i,M){
        ll A,B;
        cin >> A >> B;
        A = A - 1;
        B = B - 1;
        if(H[A] > H[B]) L[B] = 1;
        else if(H[A] == H[B]) L[A] = L[B] = 1;
        else L[A] = 1;
    }
    int ans = 0;
    rep(i,N){
        if(L[i] == 0) ans++;
    }
    cout << ans << endl;
}

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

int main(){

    int N;
    cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) cin >> A[i];

    long long min = *min_element(A.begin(), A.end());
    long long max = *max_element(A.begin(), A.end());

    cout << max - min << endl;

    return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let p: Vec<usize> = (0..n).map(|_| read()).collect();
    
    let mut cnt = 0;
    for i in 0..n-2 {
        if (p[i] < p[i+1] && p[i+1] < p[i+2]) || (p[i] > p[i+1] && p[i+1] > p[i+2]) {
            cnt += 1;
        }
    }
    println!("{}", cnt);
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


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

string s;

void solve()
{
    string ans;
    if (s == "Sunny")
        ans = "Cloudy";
    else if (s == "Cloudy")
        ans = "Rainy";
    else
    {
        ans = "Sunny";
    }
    cout << ans;
}

int main()
{
    cin >> s;

    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define siz(v) (ll)(v).size()
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define repr(i, a, n) for (ll i = n - 1; (ll)a <= i; i--)
#define lb lower_bound
#define ub upper_bound
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 + 99);
vector<ll> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
template <typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <typename T>
T mpow(T a, T n)
{
   T res = 1;
   for (; n; n >>= 1)
   {
      if (n & 1)
         res = res * a;
      a = a * a;
   }
   return res;
}

//cin.tie(0);ios::sync_with_stdio(false);

signed main()
{
   string s;
   cin >> s;
   ll k, ans = 0, cnt = 1;
   cin >> k;
   bool same = true;

   rep(i, 0, siz(s))
   {
      if (s[i] != s[0])
         same = false;
   }

   if (same)
   {
      cout << (k * siz(s)) / 2 << endl;
      return 0;
   }
   
   vector<int> v(0);

   rep(i, 0, siz(s) - 1)
   {
      if (s[i] == s[i + 1])
      {
         cnt++;
      }
      else
      {
         v.pb(cnt);
         cnt = 1;
      }
   }
   v.pb(cnt);

   if (s[0] == s.back())
   {
      ans += (k - 1) * ((v[0] + v.back()) / 2);
      ans+=v[0]/2;
      ans+=v.back()/2;
      
      rep(i, 1, siz(v) - 1)
      {
         ans += k * (v[i] / 2);
      }
   }
   else
   {
      rep(i, 0, siz(v))
      {
         ans += k * (v[i] / 2);
      }
   }

   cout << ans << endl;
}

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  
  if(c==0){
    cout << "YES" << endl;
    return 0;
  }
  
  if(a<b)swap(a,b);
  while(a%b!=0){
    a %= b;
    swap(a,b);
  }
  
  puts(c%b==0?"YES":"NO");
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#define ll long long
#define md 1000000007
#define pr(x) cerr<<#x<<"="<<x<<endl;
using namespace std;
ll n,m,ans,i;
int main ()
{
	scanf("%lld %lld",&n,&m);
	if (abs(n-m)>1) 
	{
		cout<<0<<endl;
		return 0;
	}
	if (n==m) 
	{
		ans=1;
		for (i=1;i<=n;i++)ans=i*ans%md;
		for (i=1;i<=m;i++)ans=i*ans%md;
		printf("%lld\n",ans*2%md);
		return 0;
	}
	ans=1;
	for (i=1;i<=n;i++)ans=i*ans%md;
	for (i=1;i<=m;i++)ans=i*ans%md;
	printf("%lld\n",ans);
	return 0;
	
}

Measured memory_bytes: 256
n,m,k=map(int,input().split())
mod=998244353
N=n
fac=[1]*(N+3)
inv=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+2],mod-2,mod)
for i in range(N+2,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    if r>n or r<0:
        return 0
    return fac[n]*inv[n-r]*inv[r]%mod
ans=pow(m,n,mod)
for i in range(k+1,n):
    ans-=comb(n-1,i)*m*pow(m-1,n-i-1,mod)%mod
    ans%=mod
print(ans)

Measured memory_bytes: 73968
/*Author: Gautam*/
 
 
#include<bits/stdc++.h>
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
#define MOD 1000000007
#define ull unsigned long long int
#define newline cout<<endl
 
 
/* TYPE DEFINITIONS */
typedef     long long       ll;
typedef     vector<ll>     vi;
typedef     pair<int,int>   pi;
 
 
 
/* ALGEBRA */
bool isPrime(ull n) 
{ 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (ull i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 
 
ll binpow(ll a, ll b, ll m) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
 
/* MACROS */
 
#define  all(A)         (A).begin() , (A).end()
#define  arrall(A,n)    (A),((A)+(n))
#define  rall(A)        (A).rbegin() , (A).rend()
#define  sz(A)          (int)(A).size()
#define  pb             push_back
#define  ppb            pop_back
#define  mp             make_pair
#define  ln(X)          (int)(X).length()
#define  square(X)      ((X)*(X))
#define  cube(X)        ((X)*(X)*(X))
#define  forn(i, n)  for (int i = 0; i < int(n); i++)
#define  forr(i, n)  for (int i = int(n - 1); i >= 0; i--)
#define  fora(i, a, b)  for (int i = int(a); i <= int(b); i++)
#define  forb(i, a, b)  for (int i = int(a); i >= int(b); i--)
#define  fore(it, a)    for(__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) 
void solve()
{  
    int n;
    cin>>n;
    int a;
    if(n&1)a=(n/2)+1;
    else a=n/2;
    cout<<fixed<<setprecision(8)<<(float)a/n<<endl;
}
    
int main()
{
 
    FastIO;
    ll t=1;
    
    //cin>>t;
    while(t--)
    {  // memo();
        solve();
    }
}

Measured memory_bytes: 256
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; i++)

int main()
{
  int n,k;
  cin >> n >> k;
  ll h[n];rep(i,n)cin>>h[i];
  ll mi = 10000000010;
  sort(h, h + n);

  rep(i,n-k+1){
    mi=min(mi,abs(h[i]-h[i+k-1]));
  }
  cout << mi << endl;

  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define loop(i,a,b) for(ll i=a; i<b; i++)
#define revloop(i,a,b) for(ll i=a; i>=b; i--)
#define pb push_back
#define vl vector<ll>
#define vvl vector<vl>
#define pl pair<ll,ll>
#define vpl vector<pl>
#define all(c) (c).begin(), (c).end()
#define sz(a) ((a).size())
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i!=(c).end(); i++))
#define mp make_pair
#define ss second
#define ff first
const ll INF = 1e13;
const ll N = 200001;
const ll mod=998244353;
const ll E = 1e5+10;
bool prime(ll x)
{
	if(x<2) return false;
	for(ll i=2; i*i<=x; i++) if(x%i==0) return false;
	return true;
}
vl fac(N);
void fact()
{
	fac[0]=1;
	loop(i,1,N) fac[i]=(fac[i-1]*i)%mod;
}
vl edges[E];
bool visited[E];
ll d[N];
void dfs(ll i)
{
	visited[i]=1;
	d[i]=-1;
	for(int v : edges[i])
	{
		if(!visited[v]) dfs(v);
		d[i] = max(d[i], d[v]);
	}
	d[i]++;
}
void solve()
{
  ll n,m;
  cin>>n>>m;
  while(m--)
  {
  	ll a,b;
  	cin>>a>>b;
  	edges[a].pb(b);
  }
  ll ans = 0;
  loop(i,1,n+1)
  {
  	if(!visited[i]) dfs(i);
  	ans = max(ans, d[i]);
  }
  cout<<ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t=1;
    //cin>>t;
    while(t--) solve();
 return 0;
}

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

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

  int n;
  string s;
  cin >> n >> s;
  int cum = 0;
  int m = 0;
  for (char &c : s) {
    (c == 'I') ? cum++ : cum--;
    m = max(m, cum);
  }
  cout << m << '\n';
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

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

  if((H % 3 == 0) || (W % 3 == 0)){
    cout << 0 << endl;
    return 0;
  }

  ll h1 = H / 2;
  ll h2 = H / 2 + H % 2;
  ll s1, s2, s3;
  ll dif1 = (ll)pow(10, 10);

  rep2(i, 1, W){
    s1 = h1 * i;
    s2 = h2 * i;
    s3 = H * (W - i);
    
    dif1 = min(dif1, max(s2, s3) - min(s1, s3));
  }

  ll w1 = W / 2;
  ll w2 = W / 2 + W % 2;
  ll dif2 = (ll)pow(10, 10);

  rep2(i, 1, H){
    s1 = i * w1;
    s2 = i * w2;
    s3 = (H - i) * W;

    dif2 = min(dif2, max(s2, s3) - min(s1, s3));
  }
  
  cout << min(dif1, min(dif2, min(H, W))) << endl;
  
  return 0;
}


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll A, B, M;
    cin >> A >> B >> M;
    vec a(A), b(B), x(M), y(M), c(M);
    REP(i,0,A) cin >> a[i];
    REP(i,0,B) cin >> b[i];
    REP(i,0,M) cin >> x[i] >> y[i] >> c[i];

    ll mn = INF;
    REP(i,0,M) mn = MIN(mn,a[x[i]-1]+b[y[i]-1]-c[i]);
    ASC(a);
    ASC(b);
    PR(MIN(mn,a[0]+b[0]));

    return 0;
}

/*



*/

Measured memory_bytes: 7220
N = int(input())
W = [input() for i in range(N)]

if not len(W) == len(set(W)):
	print('No')
	exit()

for i in range(1,N):
	if not W[i-1][-1] == W[i][0]:
		print('No')
		exit()
	elif i == N-1:
		print('Yes')
		exit()

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

int main() {
  double ans;
  int N;
  cin >> N;
  vector<double> vect(N);
  for (int i = 0; i < N; i++){
    cin >> vect.at(i);
    ans += 1/vect.at(i);
  }
  cout << 1/ans << endl;
}

Measured memory_bytes: 256
#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    n = int(input())
    ans=10**12
    for a in range(1,10**6+1):
        if n%a==0:
            b=n//a
        ans=min(ans,a+b-2)
    print(ans)

if __name__=="__main__":
    main()

Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for (int i = 0; i < (n); ++i)
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin >> n;
    vector<pair<int,int>> u,v;
    rep(i,n){
        string s;cin >> s;
        int cnt=0,mi=0;
        rep(j,s.size()){
            if(s[j]=='('){
                cnt++;
            }
            else{
                cnt--;
            }
            chmin(mi,cnt);
        }
        if(cnt>=0){
            u.push_back({mi,cnt});
        }
        else{
            v.push_back({cnt-mi,cnt});
        }
    }
    sort(u.begin(),u.end(),greater<pair<int,int>>());
    sort(v.begin(),v.end(),greater<pair<int,int>>());
    int sum=0;
    for(auto x:u){
        if(sum+x.first<0){
            cout << "No" << endl;
            return 0;
        }
        sum+=x.second;
    }
    for(auto x:v){
        if(sum+x.second-x.first<0){
            cout << "No" << endl;
            return 0;
        }
        sum+=x.second;
    }
    cout << (sum?"No":"Yes") << endl;
}

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

int main() {
  int N, X, T;
  cin >> N >> X >> T;
  
  int cnt = 0;
  
  cnt += N / X;
  if (N % X != 0) cnt++;
  
  cout << (cnt * T) << endl;
  
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> PLL;
#define chmax(x, y) do { x = max(x, y); } while(0)
#define chmin(x, y) do { x = min(x, y); } while(0)
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (ll i = static_cast<ll>(a); i < static_cast<ll>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;

ull A;
double B;

signed main() {
  cin >> A >> B;
  cout << (ull)((A * (ull)round(B * 100)) / 100) << endl;
  return 0;
}


Measured memory_bytes: 3776
#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
  int k, x;
  cin >> k >> x;
  
  bool is_first = true;
  for (int i = x-k+1; i<=x+k-1; i++) {
    if (is_first) {
      is_first = false;
    } else {
      cout << " ";
    }
    cout << i;
  }
  
  cout << endl;
  
  return 0;
}


Measured memory_bytes: 256