akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
#define clr(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define PI acos(-1.0)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const int INF=0x3f3f3f3f;
const int maxn=1e5+10;
int dp[1<<16],V[maxn],cnt[16];
int n,x,y,a;
inline int Count(int x)
{
	int ans=0;
	for(int i=0;i<=15;++i) if(x&(1<<i)) ans++;
	return ans;
}
int Work(int S)
{
    if(S==0) return 0;
    if(dp[S]!=-1) return dp[S];
    dp[S]=INF;
    for(int i=1;i<16;i++)
    {
    	if(S&(1<<i))
            for(int j=1;j<16;j++)
            {
            	
            	if(S&(1<<j))
                {
                    int cs=S^(1<<i)^(1<<j)^(1<<(i^j));
                    if(Count(cs)<Count(S)) 
					{
						if(((1<<(i^j)) & S) == (1<<(i^j))) dp[S]=min(dp[S], Work(cs) + 2);
						else dp[S]=min(dp[S], Work(cs) + 1 ); 
					}
                }
			}
	}
    return dp[S];
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&x,&y,&a);
        V[x]^=a; V[y]^=a;
    }
    for(int i=0;i<n;i++) if(V[i]) cnt[V[i]]++;
    int ans=0,s=0;
    for(int i=0;i<16;i++) ans+=cnt[i]/2, s^=(cnt[i]&1)<<i;
    memset(dp,-1,sizeof dp);
    ans+=Work(s);
    printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int max=-1,min=200010;
	vector<int> v;
	string s;
	cin >> s;
	bool flag =true;
	for(int i=0; i<s.size(); i++){
		if(s[i] == 'A' && flag == 1){
			v.push_back(i);
			flag = false;
		}else if(s[i] == 'Z' && flag == 0) v.push_back(i);
	}
	for(int i=0; i<v.size(); i++){
		if(max < v[i]) max = v[i];
		if(v[i] < min) min = v[i];
	}
	cout << max-min+1 << endl;
	
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL << 60;

int main(){
    int N,M; long long K;
    cin >> N >> M >> K;
    vector<long long> A(N),B(M),SA(N+1,0),SB(M+1,0);
    for(int i = 0; i < N; i++) cin >> A[i], SA[i+1] = SA[i] + A[i];
    for(int i = 0; i < M; i++) cin >> B[i], SB[i+1] = SB[i] + B[i];
    SB.push_back(INF);
    int res = 0;
    for(int i = 0; i <= N; i++){
        long long rem = K - SA[i];
        if(rem < 0)continue;
        int id = upper_bound(SB.begin(),SB.end(),rem) - SB.begin();
        res = max(res,i + id - 1);
    }
    cout << res << endl;

}




Measured memory_bytes: 11176
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n+1;i++)
#define sort(A) sort(A.begin(),A.end())
#define reverse(A) reverse(A.begin(),A.end())
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> vv;


int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(a);
  reverse(a);
  int ans = 0;
  rep(i,n){
    if(i%2 == 0) ans += a[i];
    else ans -= a[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin; using std::cout;
const int maxn = 200200;
typedef long long ll;
const int mod = 998244353;
inline ll pow(ll a,int b,int ans = 1) {
	for(;b;b >>= 1,a = a * a % mod) if(b & 1)
		ans = ans * a % mod;
	return ans;
}
inline ll inverse(int x){ return pow(x, mod - 2); }
int n;
int a[maxn][3];
int id[maxn], rev[maxn], o[maxn];
int c[maxn];
void no(){ puts("No"); exit(0); }
void yes(){ puts("Yes"); exit(0); }
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	rep(i, 0, 2) rep(j, 1, n) cin >> a[j][i];
	rep(i, 1, n) {
		int*a=::a[i];
		if(a[1]%3!=2)no();
		if(a[1]-a[0]==1&&a[2]-a[1]==1) rev[i]=0;
		else if(a[0]-a[1]==1&&a[1]-a[2]==1) rev[i]=1;
		else no();
		if(o[id[i]=(a[1]+1)/3]) no();
		o[id[i]]=1;
		c[id[i]&1]^=rev[i];
	}
	rep(i, 1, n) for(;id[i] != i;) {
		if(i + id[i] & 1) no();
		c[(id[i]&1)^1]^=1;
		std::swap(id[i], id[id[i]]);
	}
	c[0]||c[1]? no() : yes();
}


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

fn main() {
    let a: f64 = read();
    let h: f64 = read();

    let result = (a / h).ceil();

    println!("{}", result);
}

/// Example
/// ```
///
///  let n: i32 = read();
///
///  let mut xs = Vec::new();
///  for _ in 0..n {
///      xs.push(read::<i32>() + 1000);
///  }
/// ```
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string s, t;
    int c = 0;
    cin >> s;
    cin >> t;
    for(int i = 0; i < s.length(); i++) {
        if(s[i] != t[i]) c++;
    }
    cout << c << endl;

    return 0;
}

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

#define ll long long
#define ull unsigned long long 
#define endl '\n'
#define pii pair<int, int>
#define all(a) a.begin(),a.end()

template <typename T>
inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; }

int main(){
    int n;
    cin >> n;
    vector<ll> a(n+1), b(n);
    for(int i=0; i<=n; ++i)
        cin >> a[i];

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

    ll ans = 0;
    for(int i=0; i<n; ++i){
        ans += min(b[i], a[i]);
        b[i] -= min(b[i], a[i]);

        ans += min(b[i], a[i+1]);
        a[i+1] -= min(b[i], a[i+1]);
    }

    cout << ans;
}


Measured memory_bytes: 4756
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

template <typename T>
struct RollingHash
{
	T& ary;
	int size;
	int n;
	vector<ll> factor;
	ll b = 0;
	ll mod = 0;
	ll hash = 0;
	int index = -1;

	RollingHash(T& _ary, int _size, int _n, ll _b = (ll)1e8 + 7, ll _mod = (ll)1e9 + 7) : ary(_ary)
	{
		size = _size;
		n = _n;
		b = _b;
		mod = _mod;
		auto temp = 1ll;
		for (auto i = 0; i < n; ++i)
		{
			factor.push_back(temp);
			temp = temp * b % mod;
		}
		for (auto i = 0; i < n; ++i)
		{
			hash = (hash + ary[i] * factor[n - i - 1] % mod) % mod;
		}
	}

	bool moveNext() {
		if (index + n >= size)
		{
			return false;
		}
		if (index < 0)
		{
			++index;
			return true;
		}

		hash = (((hash - ary[index] * factor[n - 1]) % mod) + mod) % mod;
		hash = hash * b % mod;
		hash = (hash + ary[index + n]) % mod;
		++index;
		return true;
	}

	ll getHash() { return hash; }
	int getIndex() { return index; }
};

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

	auto temp = s;
	while (s.length() < t.length())
	{
		s += temp;
	}
	auto len = (int)s.length();
	s = s + s + s + s;

	auto b1 = (ll)1e5 + 7;
	auto b2 = (ll)1e8 + 7;
	RollingHash<string> hash1(t, t.length(), t.length(), b1);
	RollingHash<string> hash2(t, t.length(), t.length(), b2);

	RollingHash<string> r1(s, s.length(), t.length(), b1);
	RollingHash<string> r2(s, s.length(), t.length(), b2);
	vector<int> num((int)s.length());
	while (r1.moveNext() != false)
	{
		r2.moveNext();
		if (r1.getHash() == hash1.getHash()
			&& r2.getHash() == hash2.getHash())
		{
			auto index = r1.getIndex();
			++num[index];
		}
	}
	for (auto i = (int)s.length() - 1; i >= (int)t.length(); --i)
	{
		if (num[i - (int)t.length()] > 0)
		{
			num[i - (int)t.length()] += num[i];
		}
	}

	auto ans = -1;
	for (auto i = 0; i < len; ++i)
	{
		ans = max(num[i], ans);
	}

	if (ans * t.length() >= 2 * len)
	{
		ans = -1;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 39616
class BinTree
  attr_accessor :node
  def initialize(n)
    @node = Array.new(n){Node.new()}
  end
  def preorder(n=root())
    str = ""
    return str if n < 0
    #root
    str << sprintf(" %s", n)
    #left
    str << preorder(node[n].left)
    #right
    str << preorder(node[n].right)
    return str
  end
  def inorder(n=root())
    str = ""
    return str if n < 0
    #left
    str << inorder(node[n].left)
    #root
    str << sprintf(" %s", n)
    #right
    str << inorder(node[n].right)
    return str
  end
  def postorder(n=root())
    arr = []
    return [] if n < 0
    #left
    arr += postorder(node[n].left)
    #right
    arr += postorder(node[n].right)
    arr += [n]
  end
  def root
    #find root
    r = 0
    node.size.times {|i|
      if node[i].parent == -1 then
        r = i
        break
      end
    }
    return r
  end
  def add(i, l, r)
    node[i].left = l
    node[i].right = r
    node[l].parent = i unless l == -1
    node[r].parent = i unless r == -1
  end
  def order_to_tree(preorder, inorder)
    i = preorder[0]
    idx_root = inorder.index(i)
    if idx_root == 0 then
      inorder_left = []
    else
      inorder_left = inorder[0..idx_root-1]
    end

    inorder_right = inorder - [i] - inorder_left
    preorder_right = preorder - [i] - inorder_left
    preorder_left = preorder - [i] - preorder_right

    if inorder_left.size == 1 then
      node[i].left = inorder_left[0]
      node[inorder_left[0]].parent = i
    end
    if inorder_right.size == 1 then
      node[i].right = inorder_right[0]
      node[inorder_right[0]].parent = i
    end
    if inorder_left.size > 1 then
      node[i].left = self.order_to_tree(preorder_left, inorder_left)
      node[node[i].left].parent = i
    end    
    if inorder_right.size > 1 then
      node[i].right = self.order_to_tree(preorder_right, inorder_right)
      node[node[i].right].parent = i
    end
    return i
  end
end

class Node
  attr_accessor :parent, :left, :right
  def initialize
    @parent = -1
    @left = -1
    @right = -1
  end
end

n = gets.to_i
tree = BinTree.new(n)

preorder = gets.split.map(&:to_i).map{|i| i -= 1}
inorder = gets.split.map(&:to_i).map{|i| i -= 1}

tree.order_to_tree(preorder, inorder)

puts tree.postorder().map{|i| i += 1}.join(" ")

Measured memory_bytes: 8764
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <cmath>
#include <stack>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}


void solve(long long N, std::vector<long long> P){
  vector<ll> v(N+1);
  for(ll i=0; i<N; i++) {
    v[P[i]] = i;
  }
  ll ans = 0;
  ll cnt = 0;
  ll prev = -1;
  for(ll i=1; i<N+1; i++) {
    if(v[i]>prev) cnt++;
    else {
      ans = max(ans, cnt);
      cnt = 1;
    }
    prev = v[i];
  }
  ans = max(ans, cnt);
  std::cout << N-ans << std::endl;
}

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



Measured memory_bytes: 3328
#include<stdio.h>
#include<stdlib.h>

#define ROOT 0
#define INTERNAL 1
#define LEAF 2

typedef struct{
  int id;
  int k;
  int p;
  int d;
  char type[14];
  int *child;
}DATA;

DATA Node[100000];


int depthsearch(int, int);

int main(){
  int i, j, n, idtemp, c, type;
  
  scanf("%d", &n);
  if(n >= 1 && n <= 100000){
    for(i = 0; i < n; i++) Node[i].p = -1;
    
    for(i = 0; i < n; i++){
      scanf("%d", &idtemp);
      Node[idtemp].id = idtemp;
      scanf("%d", &Node[idtemp].k);
      Node[idtemp].child = (int *)malloc(sizeof(int) * Node[idtemp].k);
      for(j = 0; j < Node[idtemp].k; j++){
	scanf("%d", &c);
	Node[idtemp].child[j] = c;
	Node[c].p = idtemp;
      }
    }

    for(i = 0; i < n; i++){
      Node[i].d = depthsearch(0, i);
      printf("node %d: parent = %d, depth = %d, ", i, Node[i].p, Node[i].d);
      
      if(Node[i].p == -1) printf("root, [");
      else if(Node[i].k != 0) printf("internal node, [");
      else printf("leaf, [");


      
      for(j = 0; j < Node[i].k; j++){
	if(j == Node[i].k - 1)
	  printf("%d", Node[i].child[j]);
	else
	  printf("%d, ", Node[i].child[j]);
      }
      printf("]\n");
    }

  }
  return 0;
}

int depthsearch(int d, int ids){
  
  if(Node[ids].p == -1) return d;
  
  ids = Node[ids].p;
  d = depthsearch(d + 1, ids);
 
  return d;
}



Measured memory_bytes: 9152
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100005;

int n,A[MAXN];
int cnt[2][MAXN];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&A[i]);
		cnt[i&1][A[i]]++;
	}
	int mx[2][2]={{-1,-1},{-1,-1}},val[2][2]={0};
	for(int k=0;k<2;k++)
	{
		for(int i=1;i<MAXN;i++)
			if(mx[k][0]<cnt[k][i])
				mx[k][0]=cnt[k][i],val[k][0]=i;
		for(int i=1;i<MAXN;i++)
			if(i!=val[k][0]&&mx[k][1]<cnt[k][i])
				mx[k][1]=cnt[k][i],val[k][1]=i;
	}
	int ans=0x3F3F3F3F;
	if(val[0][0]!=val[1][0])
		ans=min(ans,n-mx[0][0]-mx[1][0]);
	if(val[0][0]!=val[1][1])
		ans=min(ans,n-mx[0][0]-mx[1][1]);
	if(val[0][1]!=val[1][0])
		ans=min(ans,n-mx[0][1]-mx[1][0]);
	if(val[0][1]!=val[1][1])
		ans=min(ans,n-mx[0][1]-mx[1][1]);
	printf("%d\n",ans);
	
	return 0;
}


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

#define endl '\n'
#define ll long long
#define rint register int

#define re register
#define pb(x) push_back(x);
#define ce(x) cout << x << '\n';

using db = long double;
using pll = pair < ll, ll >;
#define scan(a, n) 		for(int i = 0; i < n; i++)cin >> a[i];

#define rep(i,x,n,inc) for(i=x ; i<n ; i+=inc)
#define repr(i,x,n,inc) for( i=x ; i>n ; i+=inc)
#define all(a)      (a).begin(),(a).end()
#define unique_sort(x) sort(all(x)), x.resize(distance(x.begin(), unique(all(x))))

#define mp(a,b) make_pair(a,b)
#define ff first
#define ss second
#define hell 1000000007
#define infl LLONG_MAX

#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Fill(s,v) memset(s,v,sizeof(s))
#define cout_p(x, p) cout << fixed << setprecision((p)) << x << endl     //print with precision

#define tc(tt) \
    ll tt;    \
    cin >> tt; \
    for (ll _tt = 0; _tt < tt; _tt++) // testcase 

int32_t main() {
	ios::sync_with_stdio(0); 		cin.tie(0); cout.tie(0);

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

	ll t, i, x, j, y, 	z, k, n;
	cin >> n >> k;
	ll a[n], b[n];
	scan(a, n);

	rep(j, 0, k, 1) {
		memset(b, 0, sizeof(b));
		rep(i, 0, n, 1) {
			ll mi = max(0LL, i - a[i]), mx = min(n - 1, i + a[i]);
			b[mi]++;
			if (mx < n - 1)
				b[mx + 1]--;
		}
		bool br = true;
		rep(i, 1, n, 1) {
			b[i] += b[i - 1];
			br = br && (a[i] == b[i]);
		}


		rep(i, 0, n, 1)	{
			if (a[i] != b[i])	br = false;
			a[i] = b[i];
		}
		if (br)	break;
	}

	rep(i, 0, n, 1)	cout << a[i] << " ";
}


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

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

    for(int i=0;i<S.length();i++){
        switch (i%2)
        {
        case 0:
            if(!(S.at(i)=='R'||S.at(i)=='U'||S.at(i)=='D')){
                cout<<"No"<<endl;
                return 0;
            }else continue;
        case 1:
            if(!(S.at(i)=='L'||S.at(i)=='U'||S.at(i)=='D')){
                cout<<"No"<<endl;
                return 0;
            }else continue;
        default:
            break;
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 256
using System;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int ans = 0;

            int N = int.Parse(Console.ReadLine());

            string[] s = Console.ReadLine().Split(' ');

            int[] A = new int[N];

            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse(s[i]);
            }

            Array.Sort(A);

            ans = A[1];

            for(ans = A[1];ans > 0;ans--)
            {
                int check = 0;
         

                for(int i=0;i<N;i++)
                {
                    if(A[i] % ans != 0)
                    {
                        check++;
                    }

                    if (check > 1)
                        break;
                }

                if(check < 2)
                    break;

            }
            Console.WriteLine(ans.ToString());
        }
    }
}


Measured memory_bytes: 26972
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	
	int N, P, W, G, Y;
	cin >> N;
	
	P, W, G, Y= 0;
	
	for(int i=0; i<N; i++){
		
		string S;
		cin >> S;
	
		if(S=="P"){
			
			P += 1;
			
		}
		else if(S=="W"){
			
			W += 1;
			
		}
		else if(S=="G"){
			
			G += 1;
			
		}
		else{
			
			Y += 1;
			
		}
		
	}
	
	if(P >0 && W> 0 && G> 0 && Y >0){
		
		cout << "Four" ;
		
	}
	else{
		
		cout << "Three" ;
	}
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD = 1000000007;

     signed main(){
int n;
cin>>n;
vector<int> x,y;int a;

    for(int i=0;i<n;i++){
        cin>>a;
        if((n+i)%2)x.push_back(a);
        else y.push_back(a);
    }
    for(int i=0;i<x.size();i++)cout<<x[x.size()-1-i]<<' ';
    for(int i=0;i<y.size();i++)cout<<y[i]<<' ';


     }


 


 






    





      

        


Measured memory_bytes: 4980
import itertools
queen=[-1]*8
N=int(input())
de=[]
for i in range(N):
    x,y =list(map(int,input().split()))
    de.append(x)
    queen[x]=y
def check(n):#nはクイーンの個数
    for y in range(n):
        if crshu(queen[y],y):return False
    return True
def crshu(x,y):
    for y1 in range(y):
        x1=queen[y1]
        if x1-y1==x-y or x1+y1==x+y:return True
    return False
def board():
    king=[]
    for i in range(8):
        king.append([i,queen[i]])
    for i in range(8):
        for j in range(8):
            if [i,j] in king:
                print("Q",end="")
            else:
                print(".",end="")
        print()
    exit()

def search(n,y):
    if n==y:
        if check(8):
            board()
    else:
        if y in de:
            search(n,y+1)
        else:
            for i in range(n):
                if i not in queen :
                    queen[y]=i
                    search(n,y+1)
                    for l in range(y+1,8):
                        if l not in de:
                            queen[l]=-1
search(8,0)



Measured memory_bytes: 5656
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define vl vector<ll>
#define pl pair<ll,ll>
#define mp make_pair
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) for(ll i=0;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(),(v).end()
using namespace std;
ll n,m,h,w;
map<ll,ll>ma;
signed main() {
    cin>>n;
    rep(i,n){
        cin>>m;
        auto itr = ma.find(m);
        if( itr != ma.end() )itr->second++;
        else ma.emplace(m,1);
    }
    for(auto itr = ma.begin(); itr != ma.end(); ++itr) {
        ll x=itr->first,y=itr->second;
        if(y>1){
            w=h;
            h=max(h,x);
        }
        if(y>3){
            w=max(w,x);
            h=max(h,x);
        }
    }
    cout<<w*h<<endl;
}

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

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

    long long ans = 0;

    for(int bit = 0; bit < (1<<(int)(s.size())-1); bit++){
        long long add = 0;
        for(int i=0; i<(int)(s.size())-1; i++){
            add *= 10;
            add += s[i] - '0';
            if(bit & (1<<i)){
                ans += add;
                add = 0;
            }
        }

        add *= 10;
        add += s[s.size()-1] - '0';
        ans += add;
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 3612
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<algorithm> 
#define bye return 0
#define speedOne ios::sync_with_stdio(false)
#define speedtwo cin.tie(0)
typedef long long int lli;
typedef long long ll;
using namespace std;
int main()
{
    vector<int> v;
    int a, b, c;
    cin >> a >> b;
    for(int i=0; i<a; ++i){
        cin >> c;
        v.push_back(c);
    }
    
    sort(v.begin(), v.end());
    
    int sum = 0;
    for(int i=0; i<b; ++i){
        sum = sum+v[i];
    }
    
    cout << sum << endl;
	bye;
}

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

#define  SZ(items) (int)items.size()
#define  CLR(a)  memset(a,0,sizeof(a))
#define  SET(a)  memset(a,-1,sizeof(a))

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

template <class T> inline T gcd(T a, T b) { while (b) { a = a%b; swap(a, b); } return a; }




int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int a, b,k;
	cin >> a >> b >> k;

	int t = 0;
	int d = 1;

	vector<int> items;

	while (d<=min(a,b))
	{
		if (a%d == 0 && b%d == 0)
		{
			t++;

			items.push_back(d);

		}

		d++;
	}

	sort(items.rbegin(), items.rend());

	cout << items[k-1] <<endl;
	


	return 0;
}


Measured memory_bytes: 892
#include <iostream>
#include <cmath>
using namespace std;
long long s, n, mn = 1e9;
int main() {
	cin>>s;
	for(; s; s/=10) {
		n = s % 1000;
		mn = min(mn, (long long)abs(n - 753));
	}
	cout<<mn;
	return 0;
}

Measured memory_bytes: 256
// Shift-JIS（シフトジス）

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int X, A;
    cin >> X >> A;
    if (X < A)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << 10 << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int main()
{
    int n;
    cin>>n;
    int arr[n],dp[n];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
     cin>>arr[i];
     dp[0]=0;
     dp[1]=abs(arr[1]-arr[0]);
     for(int i=2;i<n;i++)
     {
         dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i-2]-arr[i]));
     }
     cout<<dp[n-1]<<endl;
}

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

using namespace std;

const int NIL = -1;

struct Node {
    int parent;
    int left_child;
    int right_child;
    int depth;
    int height;
};

class BinaryTree {
private:
    vector<Node> nodes;
    int root; // 根のid

    void setNodes(int size)
    {
        for (int i = 0; i < size; i++)
        {
            int id, left, right;
            cin >> id >> left >> right;
            if (left != NIL)
            {
                nodes[id].left_child = left;
                nodes[left].parent = id;
            }
            if (right != NIL)
            {
                nodes[id].right_child = right;
                nodes[right].parent = id;
            }
        }
    }

    void set_depth(int index, int depth)
    {
        nodes[index].depth = depth;
        if (nodes[index].left_child != NIL)
            set_depth(nodes[index].left_child, depth + 1);
        if (nodes[index].right_child != NIL)
            set_depth(nodes[index].right_child, depth + 1);
    }

    int set_height(int index)
    {
        int h1 = 0;
        int h2 = 0;
        if(nodes[index].left_child != NIL)
            h1 = set_height(nodes[index].left_child) + 1;
        if(nodes[index].right_child != NIL)
            h2 = set_height(nodes[index].right_child) + 1;
        int h = max(h1, h2);
        nodes[index].height = h;
        return h;
    }

public:
    BinaryTree(int size)
    {
        for (int i = 0; i < size; i++)
            nodes.push_back(Node{NIL, NIL, NIL, NIL});
        setNodes(size);
        for (root = 0; root < size; root++)
        {
            if (type(root) == "root")
                break;
        }
        set_depth(root, 0);
        set_height(root);
    }

    vector<Node> getNodes() { return nodes; }

    int sibling(int index)
    {
        int parent = nodes[index].parent;
        if(parent == NIL)
            return -1;
        else
        {
            int left = nodes[parent].left_child;
            int right = nodes[parent].right_child;
            if (left != index)
                return left;
            else
                return right;
        }
    }

    string type(int index)
    {
        if (nodes[index].parent == NIL)
            return "root";
        else if (nodes[index].left_child == NIL && nodes[index].right_child == NIL)
            return "leaf";
        else
            return "internal node";
    }

    int degree(int index)
    {
        int degree = 0;
        if (nodes[index].right_child != NIL)
            degree++;
        if (nodes[index].left_child != NIL)
            degree++;
        return degree;
    }
};

int main()
{
    int n;
    cin >> n;
    BinaryTree tree(n);
    vector<Node> nodes = tree.getNodes();
    for (int i = 0; i < n; i++)
    {
        cout << "node " << i << ": parent = " << nodes[i].parent
             << ", sibling = " << tree.sibling(i) << ", degree = " << tree.degree(i)
             << ", depth = " << nodes[i].depth << ", height = " << nodes[i].height
             << ", " << tree.type(i) << endl;
    }
}


Measured memory_bytes: 3184
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <bitset>
#include <numeric>
#include <math.h>
#include <tuple>
#include <queue>
#include <set>

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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(){
    cin.tie(0);
   	ios::sync_with_stdio(false);

    ll N, K;
    cin >> N >> K;

    vector<ll> x(N);
    
    for(int i = 0; i < N; i++){
        cin >> x[i];
    }

    ll ind_0 = 0;
    for(int i = 0; i < N; i++){
        if(x[i] >= 0){
            ind_0 = i;
            break;
        }
    }

    vector<ll> ans(N-K+1);

    int loc_pos;
    int loc_neg;
    for(int i = 0; i < N-K+1; i++){
        if(x[i] < 0 && x[i+K-1] < 0){
            ans[i] = abs(x[i]);
        }else if(x[i] < 0 && x[i+K-1] >= 0){
            ans[i] = max(abs(x[i]), abs(x[i+K-1])) + 2 * min(abs(x[i]), abs(x[i+K-1]));
        }else{
            ans[i] = abs(x[i+K-1]);
        }
    }

    cout << *min_element(ans.begin(), ans.end()) << endl;
    return 0;
}


Measured memory_bytes: 1408
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<utility>
#include<functional>
#include<cfenv>
#include<cmath>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<set>

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define vint vector<int>
#define vvint vector<vint>
#define P pair<ll,ll>
#define INT_MAX 2147483647
#define MOD 998244353
#define PI 3.14159265358979323846
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long ll;

#define MAX 1000000000000

int main(void) {
	int n; cin >> n;
	n--;
	vint b(n);
	rep(i, n) {
		cin >> b[i];
	}
	int ans = b[0];
	for (int i = 1; i <n; i++) {
		ans += min(b[i-1], b[i]);
	}
	ans += b[n - 1];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3596
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]

# 二項係数計算用　階乗と逆元の初期化
def combination_mod_initialize(n, MOD=10**9+7):
    fac = [1]*(n+1)
    inv = [1]*(n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = inv[i-1] * pow(i, -1, MOD) % MOD
    return fac, inv

# 二項係数　高速
def combination_mod(n, r, fac, inv):
    return fac[n] * inv[r] * inv[n-r]


def main():
    N, K = NMI()
    A = NLI()
    A.sort()
    ans = 0
    fac, inv = combination_mod_initialize(N, MOD)

    for i in range(N):
        max_num = 0
        min_num = 0
        if i >= K-1:
            max_num = combination_mod(i, K-1, fac, inv)
        if N-1-i >= K-1:
            min_num = combination_mod(N-1-i, K-1, fac, inv)
        ans += (max_num - min_num) * A[i] % MOD
    print(ans%MOD)


if __name__ == "__main__":
    main()

Measured memory_bytes: 21388
#include<stdio.h>

int main()
{
 int n;
 int v[100005];
 int odd[100005];
 int even[100005];
 int i;
 int maxvalodd=0;
 int maxvaleven=0;
 int maxeven=-1;
 int maxevenindex=-1;
 int maxevenold=-1;
 int maxevenindexold=-1;
 int maxodd=-1;
 int maxoddindex=-1;
 int maxoddold=-1;
 int maxoddindexold=-1;
 int change;
 int changeodd;
 int changeeven;
 
 for(i=0;i<100005;i++)
 {
  even[i]=0;
  odd[i]=0;
 }

 scanf("%d",&n);
 for(i=0;i<n;i++) 
 {
  scanf("%d",&v[i]);
  if((i%2)==0)
  { 
   even[v[i]]++;
   if(v[i]>maxvaleven) maxvaleven=v[i];
  }else{
   odd[v[i]]++;
    if(v[i]>maxvalodd) maxvalodd=v[i];
  }
 }

 for(i=1;i<=maxvaleven;i++)
 {
  if(even[i]>=maxeven)
  {
   maxevenold=maxeven;
   maxevenindexold=maxevenindex;
   maxeven=even[i];
   maxevenindex=i;
  }else if(even[i]>=maxevenold)
  {
   maxevenold=even[i];
   maxevenindexold=i;
  }
 }

 for(i=1;i<=maxvalodd;i++)
 {
  if(odd[i]>=maxodd) 
  {
   maxoddold=maxodd;
   maxoddindexold=maxoddindex;
   maxodd=odd[i];
   maxoddindex=i;
  }else if(odd[i]>=maxoddold)
  {
   maxoddold=odd[i];
   maxoddindexold=i;
  }
 }

 if(maxoddindex==maxevenindex)
 {
  if(maxevenold==-1) maxevenold=0;
  if(maxoddold==-1) maxoddold=0;
  if((maxodd+maxevenold)>(maxeven+maxoddold))
  {
   maxeven=maxevenold;
  }else{
   maxodd=maxoddold;
  }
 }

 changeodd=n/2 - maxodd;
 changeeven=n/2 - maxeven;
 change=changeodd+changeeven;

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


Measured memory_bytes: 1280
#include <iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string> 
#define pii pair<int,int>
using namespace std;
const int mod=1e9+7;
const int N=1e3+5;
bool vis[N][N];
int dir[2][2] = {1,0,0,1}; 
int cnt[N][N];
queue<pii>q;
int main()
{
    int n,m;
    cin>>n>>m;//n行m列 
    vector<string> g(n);//图 
    for(int i=0;i<n;i++)
      cin>>g[i];
    q.push({0,0});//起点为0,0，入队 
    vis[0][0]=1;//标记为已访问 
    cnt[0][0]=1;//起点到起点的路径条数为1 
    while (!q.empty())
    {
        pii f=q.front();
        q.pop();//取队首元素 
        for(int i=0;i<2;i++)//这里要注意，只往下走或者往右走(题目要求) 
        {
            int x=f.first+dir[i][0],y=f.second+dir[i][1];
            if (x>=0&&x<n&&y>=0&&y<m&&g[x][y]== '.')//边界条件以及障碍物条件 
            {
                cnt[x][y]=(cnt[f.first][f.second]+cnt[x][y])%mod;//到x，y点的路径条数为其他路径条数(cnt[x][y])+当前路径条数cnt[f.first][f.second] 
                if(!vis[x][y])//如果没有访问过该点 
                {
                    vis[x][y]=1;//标记为已访问 
                    q.push({x,y});//将其加入队列以更新其其他可达点的cnt值
                	//因为只有向右和向下两个行走方向，所以队列中的元素出队前其cnt值已经计算完毕 
				}
            }
        }
    }
    cout<<cnt[n-1][m-1]<<endl;
    return 0;
}

Measured memory_bytes: 10468
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define prtd(var, i) cout << fixed << setprecision(i) << var << endl;
#define ll long long
using namespace std;

int main(){
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> a(n+1), b(m+1);
    for(int i = 1; i <= n; i++){
        ll tmp;
        cin >> tmp;
        a[i] = a[i-1] + tmp;
    }
    for(int i = 1; i <= m; i++){
        ll tmp;
        cin >> tmp;
        b[i] = b[i-1] + tmp;
    }

    ll ans = 0, j = 0;
    rep(i, n+1){
        if(a[i] > k) break;
        ll lb = upper_bound(b.begin(), b.end(), k-a[i]) - b.begin();
        
        lb--;
        //cout << a[i] << " " << lb +i<< endl;
        ans = max(ans, lb+i);
        
    }
    cout << ans << endl;
}

Measured memory_bytes: 6428
#include <stdio.h>
 
int main(void)
{
	long H, N, A[100010], i, damage;
	damage = 0;
 
	scanf("%ld%ld", &H, &N);
	for (i = 1; i <= N; i++) {
		scanf("%ld", &A[i]);
		damage += A[i];
	}
 
	if (damage >= H)
		printf("Yes");
	else
		printf("No");
	
	return 0;
}

Measured memory_bytes: 896
n = int(input())
p_list = list(map(int, input().split()))
p_dict = {}
for i, p in enumerate(p_list):
    p_dict[p] = i
res_list = []
for key in sorted(list(p_dict.keys())):
    res_list.append(str(p_dict[key]+1))
print(' '.join(res_list))

Measured memory_bytes: 24924
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  ll n;
  cin >> n;
  
  vector<pair<ll,ll>> p(n);
  rep(i,n){
  cin >> p[i].fi;
  p[i].se=i+1;
  }
  
  sort(all(p));
  
  rep(i,n){
  cout << p[i].se << " ";
  }
  

}


Measured memory_bytes: 2432
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <cmath>
#include <iomanip>
#include <numeric>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())
#define INF (ll)1e18
#define MOD (ll)1e9 + 7

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

int main()
{
    int n, m, x, y, x_[1000], y_[1000];
    cin >> n >> m >> x >> y;
    REP(i, n)
    cin >> x_[i];
    REP(i, m)
    cin >> y_[i];

    sort(x_, x_ + n);
    sort(y_, y_ + m);

    if (x_[n - 1] >= y_[0])
    {
        cout << "War" << endl;
        return 0;
    }

    int z1 = x_[n - 1] + 1;
    int z2 = y_[0];

    for (int i = z1; i <= z2; i++)
    {
        if (x < i && i <= y)
        {
            cout << "No War" << endl;

            return 0;
        }
    }

    cout << "War" << endl;

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i, m, n) for (int i = int(m); i < int(n); i++)
#define RREP(i, m, n) for (int i = int(n) - 1; i >= int(m); --i)
#define EACH(i, c) for (auto &(i) : c)
#define all(c) begin(c), end(c)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(begin(c), end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x) cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) \
    do           \
    {            \
    } while (0)
#define dump(x) \
    do          \
    {           \
    } while (0)
#define BR
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int, int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template <class T>
inline T sqr(T x) { return x * x; }

void solve()
{
    int n;
    cin >> n;
    VLL a(n);
    REP(i, 0, n)
    cin >> a[i];

    for (int i = n; i > 1; i -= 2)
    {
        cout << a[i - 1] << " ";
    }
    cout << a[0];
    for (int i = 2 + (n + 1) % 2; i <= n; i += 2)
    {
        cout << " " << a[i - 1];
    }
    cout << endl;
}

int main()
{
    solve();

    return 0;
}

Measured memory_bytes: 3712
n = int(input())
p = list(map(int, input().split()))
ans = 0

for i in range(1, n - 1):
    if p[i - 1] > p[i] > p[i + 1] or p[i - 1] < p[i] < p[i + 1]:
        ans += 1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define ll long long
#define MAXN 2000005
using namespace std;
using namespace __gnu_pbds;  

int a,b,c;

void solve()
{
    cin>>a>>b>>c;
    cout<<c<<" "<<a<<" "<<b<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	cout.tie(NULL);
    solve();
}


Measured memory_bytes: 384
N = int(input())
W = list(map(int, input().split()))
SumW = sum(W)
AveW = SumW / 2
 
temp = 0
for i in W:
  temp += i
  if temp >= AveW:
    if temp - AveW >= AveW - temp + i:
      print(int(SumW - (temp - i) * 2))
    else:
      print(int((temp * 2 - SumW)))
    break

Measured memory_bytes: 3064
#include <iostream>
#define rep(i,n) for (int i=0; i<n;i++)
using namespace std;

int bubbleSort(int a[], int n){
    int sw = 0;
    bool flag = 1;
    for(int i=0;flag;i++){
        flag = 0;
        for(int j=n-1; j >= i + 1; j--){
            if(a[j] < a[j-1]){
                swap(a[j], a[j-1]);
                flag = 1;
                sw++;
            }
        }
    }
    return sw;
}

int main(){
    int a[100], n, sw;
    cin >> n;
    rep(i,n) cin >> a[i];

    sw = bubbleSort(a,n);

    rep(i,n){
        if(i) cout << " ";
        cout << a[i];
    }
    cout << endl;
    cout << sw << endl;

    return 0;
}


Measured memory_bytes: 3116
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

int main() {
  int n, a, b, c, d;
  cin >> n >> a >> b >> c >> d; a--; b--; c--; d--;
  string s;
  cin >> s;
  if (d > c) {
    swap(a, b);
    swap(c, d);
  }
  for (int i = min(a, b); i <= max(c, d); i++) {
    if (i + 2 < n) {
      if (s[i] == '#' && s[i + 1] == '#' && s[i + 2] == '#') {
        cout << "No" << endl;
        return 0;
      }
    }
  }
  bool seen = 0;
  if (b > a) {
    for (int i = b; i <= d; i++) {
      if (i > 0 && i < n - 1) {
        seen |= (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.');
      }
    }
  }
  if (!seen && b > a) {
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <map>

using namespace std;
typedef long long int ll;

ll N, M, d;
string S, T;

ll gcd(ll x, ll y)
{
    if (x % y == 0)
    {
        return y;
    }
    else
    {
        return gcd(y, x % y);
    }
}

int main()
{
    cin >> N >> M >> S >> T;
    d = gcd(N, M);
    ll k1 = N / d;
    ll k2 = M / d;

    for (int i = 0; i < d; ++i)
    {
        if (S[i * k1] != T[i * k2])
        {
            printf("%d", -1);
            return 0;
        }
    }

    printf("%lld", k1 * k2 * d);
    return 0;
}

Measured memory_bytes: 512
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10000)

H, W = map(int, input().split())
C = tuple(map(int, input().split()))
D = tuple(map(int, input().split()))
S = [list(input()) for _ in range(H)]

d = [(0, 1), (1, 0), (0, -1), (-1, 0)]

def dfs(h, w, i):
    S[h][w] = i

    for dh, dw in d:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if S[nh][nw] != '.':
            continue
        dfs(nh, nw, i)

# 番号を振る
count = 1
for h in range(H):
    for w in range(W):
        if S[h][w] != '.':
            continue
        dfs(h, w, count)
        count += 1

# グラフを構築
graph = {}
for i in range(1, count):
    graph[i] = set()

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = h + dh
                nw = w + dw
                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                if S[nh][nw] == '#':
                    continue
                graph[S[h][w]].add(S[nh][nw])

start = S[C[0]-1][C[1]-1]
goal = S[D[0]-1][D[1]-1]

# 最短経路を求める
def bfs(start, goal):
    queue = deque([start])
    visited = set()
    visited.add(start)
    dist = defaultdict(int)
    dist[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
                dist[v] = dist[current_vertex] + 1
    return dist[goal] if goal in dist else -1

ans = bfs(start, goal)

print(ans)


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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define repp(i, start, to) for (li i = (li)(start); i < ((li)(to)); i++)

li a[200100];
li n;
li k;

inline bool check(li x) {
	li cnt = 0;
	rep(i, n) {
		if (a[i] < 0) {
			cnt += a + n - partition_point(a, a + n, [&](li b) {
				return a[i] * b > x;
			});
		} else {
			cnt += partition_point(a, a + n, [&](li b) {
				return a[i] * b <= x;
			}) - a;
		}
		if (a[i]*a[i] <= x) {
			cnt--;
		}
	}
	cnt /= 2;
	return cnt < k;
}

int main() {
	cin >> n >> k;
	rep(i, n) {
		cin >> a[i];
	}
	sort(a, a + n);

	const li INF = 1ll << 61;

	li left = -INF;
	li right = INF + 1;

	li cnt = 0;
	while (left + 1 < right) {
		li med = (left + right) / 2;
		if (check(med)) {
			left = med;
		} else {
			right = med;
		}
	}

	cout << right << endl;


	return 0;
}


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

int main() {
    int n, q;
    std::cin >> n >> q;

    std::vector<std::list<int>> Ls(n);

    for (int i = 0; i < q; i++) {
        int op;
        std::cin >> op;

        if (op == 0) {
            int t, x;
            std::cin >> t >> x;
            Ls[t].push_back(x);
        } else if (op == 1) {
            int t;
            std::cin >> t;
            for (auto it = Ls[t].begin(); it != Ls[t].end(); it++) {
                if (it != Ls[t].begin()) {
                    std::cout << " ";
                }
                std::cout << *it;
            }
            std::cout << std::endl;
        } else if (op == 2) {
            int s, t;
            std::cin >> s >> t;
            Ls[t].splice(Ls[t].end(), Ls[s]);
        }
    }
}



Measured memory_bytes: 18752
import java.util.Scanner;

public class Main {
  public static void main(String[] args) throws Exception {
    Scanner scanner = new Scanner(System.in);
    try {
      int n = scanner.nextInt();
      int m = scanner.nextInt();
      int L = scanner.nextInt();

      Graph g = new Graph(n);
      for (int i = 0; i < m; i++) {
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        long c = scanner.nextLong();
        a--;
        b--;
        g.setCost(a,b,c);
      }
      g.wf();
      // g.show();

      Graph h = new Graph(n);
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          if (i == j) continue;
          if (g.getCost(i, j) <= L) {
            h.setCost(i, j, 1L);
          }
        }
      }
      h.wf();
      // h.show();

      int q = scanner.nextInt();
      for (int i = 0; i < q; i++) {
        int s = scanner.nextInt();
        int t = scanner.nextInt();
        s--;
        t--;
        long num = h.getCost(s, t);
        if (num == 3000000000L) {
          System.out.println(-1);
        } else {
          System.out.println(num - 1);
        }
      }
    } finally {
      scanner.close();
    }
  }

}

class Graph {
  int n;
  long[][] g;

  public Graph(int n) {
    this.n = n;
    g = new long[n][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (i == j) {
          g[i][j] = 0;
        } else {
          g[i][j] = 3000000000L;
        }
      }
    }
  }

  public void setCost(int a, int b, long c){
    g[a][b] = c;
    g[b][a] = c;
  }

  public long getCost(int a, int b){
    return g[a][b];
  }

  public void wf() {
    for (int k = 0; k < n; k++) {
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
          long dist = g[i][k] + g[k][j];
          if (g[i][j] > dist) g[i][j] = dist;
        }
      }
    }
  }

  public void show() {
    System.out.println("---");
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        System.out.printf("%15d", g[i][j]);
      }
      System.out.println("\n");
    }
  }
}

Measured memory_bytes: 88576
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
#include <queue>
#include <math.h>
	using namespace std;
#define lol long long



	int main()
	{
		int N;
		cin >> N;
		vector<int> h(N + 1);
		for (int i = 0; i < N; i++) {
			cin >> h[i + 1];
		}
		vector<int> dp(N + 1);
		dp[0] = 1000000;
		h[0] = 1000000;
		dp[1] = 0;
		for (int i = 2; i < N + 1; i++) {
			dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]));
		}
		cout << dp[N] << endl;
	}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string S;
    cin >> S;

    vector<int> Chr(27,0);
    string alph = "abcdefghijklmnopqrstuvwxyz";
  
    for (int i = 0; i < S.size(); i++){
      for (int j = 0; j < 26 ; j++){
      if (S.at(i) == alph.at(j)) Chr.at(j)++;
      }       
    }
  
    string ans = "None";
    for (int i=0; i<26; i++){
      if (Chr.at(i) == 0){
        ans = alph.at(i);
        break;
      }
    }
    cout << ans << endl;
}


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

int main(){
  int m,d,x,i;

  while(1){
    cin>>m>>d;
    if(m==0&&d==0)break;
    x=0;
    for(i=1;i<m;i++){
      switch(i){
      case 1:
      case 3:
      case 5:
      case 7:
      case 8:
      case 10:
      case 12:
	x+=3;
	break;      
      case 2:
	x+=1;
	break;
      default:
	x+=2;
      }
    }
  switch((x+d-1)%7){
      case 0:
	cout<<"Thursday"<<endl;
	break;

      case 1:
	cout<<"Friday"<<endl;
	break;

      case 2:
	cout<<"Saturday"<<endl;
	break;

      case 3:
	cout<<"Sunday"<<endl;
	break;

      case 4:
	cout<<"Monday"<<endl;
	break;

      case 5:
	cout<<"Tuesday"<<endl;
	break;

      case 6:
	cout<<"Wednesday"<<endl;
	break;
  }
  }  
  return 0;
}  
  

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>
#include<iomanip>
#include <random>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(g);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double pi = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
ll mod = 1e9 + 7;


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

	int a, b, c;
	cin >> a >> b >> c;
	if (b - a == c - b) puts("YES");
	else
		puts("NO");
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e5 + 5, M = 2 * N + 5;


int main(){
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    ll x, nw = 100;
    scanf("%lld", &x);
    for(int i = 1 ; ; ++i){
        ll nxt = nw / 100;
        nw += nxt;
        if(nw >= x)
            return printf("%d\n", i), 0;
    }
}

Measured memory_bytes: 3800