akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>
#include <time.h>
#include <tuple>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = (1LL << 60) - 1;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,N) for(int i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second
#define N_SIZE (1LL << 20)
#define NIL -1
#define MAX_N 100100 * 3

int n;
int f[100][100];
ll ans = 0;

int main() {
	cin >> n;
	rep(i, n)rep(j, n)cin >> f[i][j];
	rep(i, n) {
		FOR(j, i + 1, n) {
			ans += min(f[i][j], f[j][i]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3136
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)

	xs := make([]int, n+1)
	for i := range xs {
		xs[i] = 1
	}
	for i := 2; i <= n; i++ {
		for j := 1; i*j <= n; j++ {
			xs[i*j]++
		}
	}
	ans := 0
	for i := 1; i <= n; i++ {
		ans += i * xs[i]
	}
	fmt.Println(ans)
}


Measured memory_bytes: 82556
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int v[10] = {};
  rep(i, 0, 4) {
    int n;
    cin >> n;
    v[n]++;
  }

  if (v[1] == 1 && v[9] == 1 && v[7] == 1 && v[4] == 1)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}


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

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define F first
#define S second

using ll = long long;
using P = pair<int,int>;

// n C x: n個からx個選ぶパターン数
int choose(int n, int x) {
  int p = 1, q = 1;
  rep(i, x) {
    p *= (n - i);
    q *= (i + 1);
  }
  return p / q;
}

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

  int res = 0;
  if (n >= 2) res += choose(n, 2);
  if (m >= 2) res += choose(m, 2);

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
input_nk = gets.chomp
n,m = input_nk.split.collect{ |item| item.to_i}
min = 1
max = n
m.times do |i|
  input = gets.chomp
  l,r = input.split.collect{ |item| item.to_i}
  min = l if l >= min
  max = r if r <= max
end
result = 0
if max >= min
  result = max - min + 1
end
puts result

Measured memory_bytes: 3836
#include<bits/stdc++.h>
#define int long long int
using namespace std;
vector<int> V[100005];
#undef int
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
#define int long long int
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	//cin >> t;
	while (t--) {
		int n, m;
		cin >> n >> m;
		int arr[n + 1];
		for (int i = 1; i <= n; i++)
			cin >> arr[i];
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			V[a].push_back(b);
			V[b].push_back(a);
		}
		int count = 0;
		for (int i = 1; i <= n; i++) {
			int flag = 1;
			for (auto j : V[i]) {
				if (arr[i] <= arr[j])
					flag = 0;
			}
			count += flag;
		}
		cout << count << endl;
	}
	return 0;
}

Measured memory_bytes: 10296
N = int(input())
AB = []
asum = 0
bmax = 0
for n in range(N):
  a,b = [int(x) for x in input().split(' ')]
  asum += a
  if bmax <= b:
    bmax = b
  AB.append((a,b))
  
res = 'Yes'
if asum > bmax:
  res = 'No'
else:
  ABsort = sorted(AB,key=lambda x:x[1])
  t = 0
  for x in ABsort:
    a,b = x
    t += a
    if b < t:
      res = 'No'
      break
print(res)


Measured memory_bytes: 33412
#include <stdio.h>

int main(){
  int a[20],b[20],c[20];
  int n,s=0;

  scanf("%d",&n);
  
  for (int i = 1;i <= n;i++){
    scanf("%d",&a[i]);
  }
  for (int i = 1;i <= n;i++){
    scanf("%d",&b[i]);
  }
  for (int i = 1;i <= n - 1;i++){
    scanf("%d",&c[i]);
  }
  for(int i = 1;i <= n;i++){
    if (a[i+1]-a[i] == 1){
      s+=b[a[i]] + c[a[i]];
    }else{
      s+=b[a[i]];
    }
  }
  printf("%d",s);
  return 0;
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


class Program
{
    static void Main(string[] args)
    {
        var s = Console.ReadLine().ToCharArray();
        var t = Console.ReadLine().ToCharArray();

        var a = 0;

        for (int i = 0; i < 3; i++)
        {
            if (s[i] == t[i]) a++;
        }

        Console.WriteLine(a);
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
typedef int64_t LL;
#define rep(i,N) for(int i=0;i<(int)N;i++)
using namespace std;
int main()
{
  LL N,M,s,x,tmp,count=0;
  priority_queue<LL> item;
  cin>>N>>M;
  rep(i,N){cin>>x;item.push(x);}
  while(count<M)
  {
    tmp=item.top();
    tmp/=2;
    count++;
    item.pop();
    item.push(tmp);
    if(item.top()==0)break;
  }
  rep(i,N){s+=item.top();item.pop();}
  cout<<s<<endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	int N, M, X;
	cin >> N >> M >> X;
	int count = 0;
	for (int i = 0; i < M; i++)
	{
		int tmp;
		cin >> tmp;
		if (tmp < X)
			count++;
	}

	cout << min(count, M - count) << endl;
	return;
}

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

	int stop;
	cin >> stop;

	return 0;
}

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

#define ll long long

using namespace std;

const int N = (int)2e5 + 7;

bool Q;
struct Line {
	mutable ll k, m, p;
	bool operator < (const Line& o) const {
		return (Q ? p < o.p : k > o.k);
	}
};

struct LineContainer : multiset < Line > {
	const ll inf = LLONG_MAX;
	
	ll div(ll a, ll b) {
		return a / b - ((a ^ b) < 0 && a % b);
	}
	
	bool isect(iterator x, iterator y) {
		if (y == end()) {
			x->p = inf;
			return false;
		}
		if (x->k == y->k) x->p = (x->m > y->m) ? -inf : inf;
		else x->p = div(x->m - y->m, y->k - x->k);
		return x->p >= y->p;
	}
	
	void add(ll k, ll m) {
		iterator z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, y = erase(y));
	}
	ll get(ll x) {
		Q = 1; auto l = *lower_bound({0, 0, x}); Q = 0;
		return l.k * x + l.m;
	}
};

ll dp[N], h[N];
int n;
ll c;

ll sqr(ll x) {
	return x * x;
}

main() {
	scanf("%d %lld", &n, &c);
	LineContainer ch;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &h[i]);
	}
	ch.add(-2 * h[1], sqr(h[1]));
	for (int i = 2; i <= n; i++) {
		dp[i] = ch.get(h[i]) + sqr(h[i]) + c;
		ch.add(-2 * h[i], dp[i] + sqr(h[i]));
	}
	cout << dp[n];
}


Measured memory_bytes: 15872
#include <iostream>
using namespace std;
#define MAX 1000000
int cnt = 0;
int m = 0;
int n;
int A[MAX];
int G[MAX];

void insertionSort(int A[], int n, int g){
    for(int i = g; i < n; i++){
        int v = A[i];
        int j = i - g;
        while(j >= 0 && A[j] > v){
            A[j + g] = A[j];
            j = j - g;
            cnt++;
        }
        A[j + g] = v;
    }
}

void shellSort(int A[], int n){
    int i = 0, j = 1;
    while(n >= j){
        G[i++] = j;
        j *= 3 + 1;
        m++;
    }
    for(int i = m - 1; i >= 0; i--){
        insertionSort(A, n, G[i]);
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> A[i];
    shellSort(A, n);
    cout << m << endl;
    for(int i = m - 1; i >= 0; i--){
        cout << G[i];
        if(i != 0) cout << " ";
    }
    cout << endl;
    cout << cnt << endl;
    for(int i = 0; i < n; i++){
        cout << A[i] << endl;
    }
    return 0;
}



Measured memory_bytes: 6996
#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int>A;
    int q;
    cin>>q;
    while(q--){
        int query;
        cin>>query;
        if(query==0){
            int x;
            cin>>x;
            A.push_back(x);
        }
        else if(query==1){
            int p;
            cin>>p;
            cout<<A[p]<<endl;
        }
        else    A.pop_back();
    }
    return 0;
}


Measured memory_bytes: 3840
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m=map(int,input().split())
A=UnionFind(n)
for i in range(m):
  x,y,z=map(int,input().split())
  A.union(x-1,y-1)
print(A.group_count())

Measured memory_bytes: 7856
S = input()
T = input()

n = len(S)
m = len(T)

res = []

for i in range(n-m+1):
    for j in range(m):
        if S[i+j] != "?":
            if S[i+j] != T[j]:
                break
    else:
        text = ""
        for x in S[:i]+T+S[i+m:]:
            if x == "?":
                text += "a"
            else:
                text += x
        res.append(text)

if res:
    print(min(res))
else:
    print("UNRESTORABLE")

Measured memory_bytes: 9020
import sys
from functools import lru_cache

input = sys.stdin.readline


ans = 0
X = []
A = 0

@lru_cache(maxsize=None)
def solve(i, selected, total):
    global X, ans

    if i == len(X):
        if selected != 0 and total == (selected * A):
            return 1
        return 0

    ret = 0
    ret += solve(i + 1, selected + 1, total + X[i])
    ret += solve(i + 1, selected, total)
    return ret


def main():
    global X, ans, A
    N, A = [int(x) for x in input().split()]
    X = [int(x) for x in input().split()]

    print(solve(0, 0, 0))

    
if __name__ == '__main__':
    main()


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

using namespace std;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


signed main(){
    int h, w;
    cin >> h >> w;
    int k;
    cin >> k;
    vector<string> s(h);
    for(auto& x : s)
        cin >> x;

    vector<int> f(h, 0);
    vector<int> l;
    for(int i = 0; i < h; ++i){
        if(count(s[i].begin(), s[i].end(), '#') == 0){
            f[i] = 1;
        }
        else{
            l.emplace_back(i);
        }
    }
    vector<vector<int>> v(h, vector<int>(w));
    int cnt = 1;
    for(int i = 0; i < h; ++i){
        if(!f[i]){
            int t = 0;
            for(int j = 0; j < w; ++j){
                v[i][j] = t + cnt;
                if(s[i][j] == '#')
                    ++t;
            }
            cnt += t;
            for(int j = 0; j < w; ++j)
                if(v[i][j] == cnt)
                    --v[i][j];
        }
    }
    for(int i = 0; i < h; ++i){
        if(f[i]){
            auto it = lower_bound(l.begin(), l.end(), i);
            if(it == l.end())
                --it;
            int idx = *it;
            for(int j = 0; j < w; ++j)
                v[i][j] = v[idx][j];
        }
    }
    for(auto& x : v){
        for(int i = 0; i < w; ++i){
            cout << x[i] << " \n"[i == w - 1];
        }
    }
}


Measured memory_bytes: 1280
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner std = new Scanner(System.in);
		while(true){
			String x = std.next();
			int ans = 0;
			if(x.equals("0")){
				break;
			}else{
				for(int i=0; i<x.length(); i++){
					ans += Integer.parseInt(String.valueOf(x.charAt(i)));
				}
			}
			System.out.println(ans);
		}
	}
}

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

typedef long long ll;

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

int main() {
  string s;
  cin >> s;
  int N;
  N = s.size();
  int ans;
  rep(i,N-1) {
    if (i%2 == 0) {
      continue;
    } 
    int a = 1;
    rep(j,(i+1)/2) {
      if (s[j] != s[j+(i+1)/2]) {
        a = 0;
      }
    } 
    if (a == 1) {
      ans = i+1;
    }

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

Measured memory_bytes: 3608
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


A, B =  list(map(int, sys.stdin.readline().split()))
print(math.ceil((A + B) / 2) )

Measured memory_bytes: 63980
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
 
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int a,b;
	string s;
	cin >> a >> b >> s;
	if(s[a] != '-'){
		cout << "No\n";
		return 0;
	}
	rep(i,a+b+1){
		if(i == a) continue;
		if(!(s[i] >= '0' && s[i] <= '9')){
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
using namespace std;
#define MOD 1000000007
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

Int dp[5400];
Int p[5400];
Int n, a, b;
int main(){
  fill(dp, dp + 5400, LINF);
  cin >> n >> a >> b;
  p[n] = n;
  for(int i = 0;i <= n;i++){
    if(i != n){cin >> p[i];p[i]--;}
    Int tmp = 0;
    Int maxima = -1;
    for(int j = i-1;j >= 0;j--){
      if(p[j] > p[i])tmp += a;
      else{
	if(p[j] > maxima){
	  dp[i] = min(dp[i], dp[j] + tmp);
	  maxima = p[j];
	}
	tmp += b;
      }
    }
    dp[i] = min(dp[i], tmp);
  }
  cout << dp[n] << endl;
  return 0;
}

Measured memory_bytes: 384
_ = input()

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

for i in range(len(a)):
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j+1] = a[j]
        j -= 1
    a[j+1] = key
    print(' '.join(map(str,a)))



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

int main() {
  int N;
  cin >> N;
  long long max=0;
  long long ans=0;
  long long a[N];
  for (int i = 0; i < N; ++i) {
    cin >> a[i];
    if (a[i] > max ) {
      max = a[i];
    }
    else {
      ans = ans + (max - a[i]);
    }
  }  
  cout << ans << endl;
}

Measured memory_bytes: 5188
#include <bits/stdc++.h>
#include <math.h>
#include <iostream>
#include <stdlib.h>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(void){
    string S,T;
    cin >> S;
    cin >> T;
    int count = 0;
    for(int i=0;i<3;i++){
        if(S[i]==T[i]) count += 1;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    vll cnt(n + 1, 0);
    for (ll i = 1; i <= n; i++) {
        for (ll j = i; j <= n; j += i) {
            cnt[j]++;
        }
    }
    ll ans = 0;
    for (ll i = 1; i <= n; i++) ans += i * cnt[i];
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 81344
import java.io.PrintWriter

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

fun solve(out: PrintWriter) {
    val n = readInteger()
    val dList = readIntegerList()
    val countMap = elementCountMap(dList)
    var sum = n
    var ABCSum = 0
    var min = -1
    var max = -1
    for (key in countMap.keys.sorted()) {
        ABCSum += countMap[key]!!

        if (min == -1 && ABCSum == sum - ABCSum) {
            min = key
        }

        if (max == -1 && ABCSum > sum - ABCSum) {
            max = key
        }
    }

    if (min != -1) {
        println(max - min)
    } else {
        println(0)
    }
}

/**
 * O(n)
 */
fun <T>elementCountMap(list: List<T>): Map<T, Int> {
    val countMap = mutableMapOf<T, Int>()
    for (e in list) {
        countMap[e] = (countMap[e] ?: 0) + 1
    }
    return countMap
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 60292
#include<cstdio>
inline void read(int&r)
{
	register char c;r=0;
	do c=getchar();while(c<'0'||c>'9');
	do r=r*10+c-'0',c=getchar();while(c>='0'&&c<='9');
}

char s[200001];
int first[200001];
int a[200001],b[200001],q[400001];
struct ac{ int to,nx; }e[400001];
void readedge()
{
	static int L=1,u,v;read(u),read(v);
	e[L].to=v,e[L].nx=first[u],first[u]=L++;
	e[L].to=u,e[L].nx=first[v],first[v]=L++;
	(s[u]=='A'?a:b)[v]++;
	(s[v]=='A'?a:b)[u]++;
}

int main()
{
	int n,u,t=0,i,j;
	scanf("%d%d%s",&n,&t,s+1);
	while(t--)readedge();
	for(u=1,t=0;u<=n;u++)if(!a[u]||!b[u])q[t++]=u;
	for(i=0;i<t;i++)
		for(j=first[u=q[i]];j;j=e[j].nx)
			if(!--(s[u]=='A'?a:b)[e[j].to]&&(s[u]=='A'?b:a)[e[j].to])
				q[t++]=e[j].to;
	puts(t==n?"No":"Yes");
}

Measured memory_bytes: 7296
void main()
{
    long n = rdElem;

    long[][] tree = new long[][](n);
    foreach (i; 0 .. n-1)
    {
        long a, b;
        rdVals(a, b);
        --a, --b;
        tree[a] ~= b, tree[b] ~= a;
    }

    long[] BFS(long start)
    {
        long[] result = new long[n];
        result[] = -1;
        result[start] = 0;
        long[] que;
        que ~= start;
        while (!que.empty)
        {
            long f = que[0];
            que.popFront;
            foreach (x; tree[f])
            {
                if (result[x] != -1) continue;
                result[x] = result[f] + 1;
                que ~= x;
            }
        }
        return result;
    }

    long[] dist1 = BFS(0), dist2 = BFS(n-1);

    long cnt;
    foreach (x, y; zip(dist1, dist2))
    {
        if (x <= y) ++cnt;
        else --cnt;
    }

    writeln(cnt > 0 ? "Fennec" : "Snuke");
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 15228
#include <stdio.h>

int main() {
    int a;
    char s[100];
    char r[] = "red";


    scanf("%d", &a);
    scanf("%s", s);

    if (a >= 3200){
        printf("%s\n", s);
    } else
        printf("%s\n", r);

    return 0;
}

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

int main() {
int i,n,s=0,s2=0;
cin>>n;
int w[n];
for(i=0;i<n;i++){
    cin>>w[i];
    s+=w[i];
}
int m=s;
for(i=0;i<n;i++){
    s2+=w[i];
    s-=w[i];
    m=min(m,abs(s-s2));
}
cout<<m<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag,
		tree_order_statistics_node_update> ordered_set;

#define el				'\n'
#define sz(v)			((int)((v).size()))
#define all(v)          ((v).begin()),((v).end())
#define clr(v, d)		memset(v, d, sizeof(v))

double const EPS = 1e-8, PI = acos(-1);
const int N = 100 + 9, M = 1e5 + 9, OO = (int) 1e9 + 1;
const long long MOD = 1e9 + 7, INF = 1e13 + 9;

typedef long long ll;

void OUTPUT() {
	cout << fixed << setprecision(0);
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}

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

int n, w, wei[N], val[N];
ll mem[N][M];

ll dp(int i, int w) {
	if (i == n)
		return 0;
	ll &ret = mem[i][w];

	if (ret != -1)
		return ret;
	ll take = 0, leave = 0;
	if (w >= wei[i])
		take = dp(i + 1, w - wei[i]) + val[i];
	leave = dp(i + 1, w);
	return ret = max(take, leave);
}

int main() {
//	INPUT();
	OUTPUT();

	cin >> n >> w;

	for (int i = 0; i < n; i++) {
		cin >> wei[i] >> val[i];
	}

	clr(mem, -1);

	cout << dp(0, w);

	return 0;

}


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

int	main() {
	int N;
	cin >>N;
	int a=sqrt(2*N);
	while (2*N>a*(a+1))
		a++;
	int S=0;
	vector<int> A(0);
	int i=a;
	while(i>0) {
		if (i<=N-S) {
			S +=i;
			A.push_back(i);
			i--;
		} else {
			i=N-S;
		}
	}
	for (int i=0; i<A.size(); i++)
		cout <<A.at(i) <<endl;
	return 0;
};


Measured memory_bytes: 384
n,a,b = map(int,input().split())
mod=7+10**9
ans = pow(2 , n , mod)

def comb(n,c,mod):
  s=1
  t=1
  for i in range(1,c+1):
    s=s*i%mod
  for j in range(n-c+1,n+1):
    t=t*j%mod
  return (t*pow(s,mod-2,mod))%mod

print((ans-1-comb(n,a,mod)-comb(n,b,mod))%mod)

Measured memory_bytes: 3064
while True:
    s = raw_input().split()
    a = int(s[0])
    b = int(s[2])
    if s[1] == "?":
        break
    elif s[1] == '+':
        print a + b
    elif s[1] == '-':
        print a - b
    elif s[1] == '*':
        print a * b
    elif s[1] == '/':
        print a / b

Measured memory_bytes: 6384
program ABC_086_B_121
   integer cval, i
   character(3) a, b
   character(6) c   
   read(*, *) a, b
   c = trim(a) // trim(b)
   read(c, *) cval
   do i = 4, 320
       if( i ** 2 <= cval) then
	       if( i ** 2 == cval) then
		       write(*, *) 'Yes'
			   exit
		   end if
	   else
	       write(*, *) 'No'
		   exit
	   end if
   end do
end program ABC_086_B_121

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define ll unsigned long long
using namespace std;
int main(){
    ll tmp=0,ans=0,A,N;cin>>N;
    REP(i,N){
        ll k;cin>>k;
        if(i!=0){
            if(A>=k){
                tmp++;
                if(i==N-1){
                    ans=max(ans,tmp);
                }
            } else {
                ans=max(ans,tmp);
                tmp=0;
            }
        }
        A=k;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pr;
typedef vector<pr> vpr;
typedef long long ll;

int main()
{
    int n;
    cin >> n;
    int max1 = 0;
    int max2 = 0;
    int maxid = -1;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        if (max1 < a)
        {
            max2 = max1;
            max1 = a;
            maxid = i;
        }
        else if (max2 < a)
        {
            max2 = a;
        }
    }

    for (int i = 0; i < n; i++)
    {
        if (i == maxid)
        {
            cout << max2 << endl;
        }
        else
        {
            cout << max1 << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<int(n);++i)
using namespace std;
template<class A>void pr(A a){cout << a << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;p(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;p(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;p(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for(int j=0;j<N;++j) {}

int main(void) {
  int n,x;cin>>n>>x;
  int L[n+10];
  REP(i,n) cin>>L[i];
  int d[n+10];
  d[0]=0;
  for(int j=1;j<n+1;++j) {
    d[j]=d[j-1]+L[j-1];
  }
  int sum = 0;
  REP(i,n+1) {
    if(d[i]<=x) sum+=1;
  }
  pr(sum);
  return 0;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    S = input()
    S = S.lstrip('W').rstrip('B')
    L = len(S)
    left = 0
    ans = 0
    for i in range(L):
        if S[i]=='W':
            ans += i-left
            left += 1
    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 3500
#include <stdio.h>
#include <string.h>
char t1[1510];
char t2[1510];
char t3[1510];
int main(){
    int n;
    int a,b;
    int i,j;
    char t;
    scanf("%s",&t1);
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s",&t3);
        if(strcmp(t3,"replace")==0){
            scanf("%d %d %s",&a,&b,&t2);
            for(j=0;j<b-a+1;j++){
                t1[a+j]=t2[j];
            }
        }
        else if(strcmp(t3,"reverse")==0){
            scanf("%d %d",&a,&b);
            while(a<b){
                t=t1[a];
                t1[a]=t1[b];
                t1[b]=t;
                a++;
                b--;
            }
        }
        else if(strcmp(t3,"print")==0){
            scanf("%d %d",&a,&b);
            for(j=a;j<b+1;j++){
                printf("%c",t1[j]);
            }
            puts("");
        }
    }
    return 0;
}


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

int main(){
  int N;cin>>N;
  vector<int>h(N);
  for(int i=0;i<N;i++) cin>>h.at(i);
  
  bool OK=true;
  
  for(int i=1;i<N;i++){
    int d=h.at(i)-h.at(i-1);
    
    if(d<0)
      OK=false;
    else if(d>0)
      h.at(i)--;
  }
  
  if(OK)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
}

Measured memory_bytes: 640
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
		int N = scan.nextInt();

		// mapにkeyとvalue格納
		for (int i = 0; i < N; i++) {
			map.put(scan.nextInt(), i + 1);
		}

		for (Integer val : map.values()) {
			System.out.print(val + " ");
		}
	}
}

Measured memory_bytes: 72208
import itertools
import math
N = int(input())
rs = [list(map(int, input().split())) for _ in range(N)]
total = 0
for p in list(itertools.permutations(range(N))):
    dist = 0
    start = rs[p[0]]
    for i in p[1:]:
        dist += ((rs[i][0] - start[0]) ** 2 + (rs[i][1] - start[1]) ** 2 ) ** (1/2)
        start = rs[i]
    total += dist
print(total / math.factorial(N))

Measured memory_bytes: 10020
n=int(input())
c=input()
from collections import Counter
w=Counter(c)["W"]
r=0
ans=w
for i in range(n-1,-1,-1):
    if c[i]=="W":
        w-=1
    else:
        r+=1
    ans=min(ans,max(r,w))
print(ans)
        

Measured memory_bytes: 74288
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	string s, t;
	cin >> s >> t;
	
	for(int i = 0; i < s.size(); ++i) {
		if( s[i] != t[i] ) {
			cout << "No" << endl;
			return 0;
		}
	}
	
	cout << "Yes" << endl;
	
	return 0;
}


Measured memory_bytes: 3620
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int n,m;
string s;
int main(void){
  while(cin >> n && n){
    cin >> m;
    cin >> s;
    int res = 0;
    for(int i = 0; i < m; i++){
      if(s[i] != 'I') continue;
      int j;
      for(j = 0;i+j*2+2 < m && s[i+j*2+1] == 'O' && s[i+j*2+2] == 'I'; j++);
      res += max(j-n+1,0);
      i += j*2;
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 2104
# dpF - LCS
def main():
    S, T = tuple(input().rstrip() for _ in range(2))
    n, m = len(S), len(T)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if S[i - 1] == T[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
    ans = []
    while n > 0 and m > 0:
        if dp[n][m] == dp[n - 1][m]:
            n -= 1
        elif dp[n][m] == dp[n][m - 1]:
            m -= 1
        else:
            n -= 1
            m -= 1
            ans += [S[n]]
    print(*ans[::-1], sep="")


if __name__ == "__main__":
    main()

Measured memory_bytes: 113116
#include<bits/stdc++.h>
using namespace std;
#define ll long long                                    // long long省略
#define pb push_back                                    // push_back省略
#define mp make_pair                                    // make_pair省略
#define fi first                                        // first省略
#define se second                                       // second省略
#define itn int                                         // int誤字保険
#define count cout                                      // cout誤字保険
#define vecotr vector                                   // vector誤字保険
#define ednl endl                                       // endl誤字保険
#define opt() cin.tie(0); ios::sync_with_stdio(false)   // 入出力速度改善

#define rep(i,l,r) for(ll i=(l);i<(r);i++)               // 範囲[l, r)で刻み1のfor文(順方向)
#define repp(i,l,r,k) for(ll i=(l);i<(r);i+=(k))         // 範囲[l, r)で刻みkのfor文(順方向)
#define rrep(i,l,r) for(ll i=(r-1);i>=(l);i--)           // 範囲[l, r)で刻み1のfor文(逆方向)
#define rrepp(i,l,r,k) for(ll i=(r-1);i>=(l);i-=(k))     // 範囲[l, r)で刻みkのfor文(逆方向)
#define all(x) (x).begin(), (x).end()                   // vectorのポインタ位置指定用
#define max(p,q)((p)>(q)?(p):(q))                       // max拡張
#define min(p,q)((p)<(q)?(p):(q))                       // min拡張
#define bit(n,m)(((n)>>(m))&1)                          // 変数nのm番目のbitを取り出す

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

int dy[]={0, 1, 0, -1};                                 // 4方向近傍
int dx[]={1, 0, -1, 0};                                 // 4方向近傍

int main(){
    ll a,b;cin>>a>>b;
  	if(a>=13) cout << b << ednl;
    else if(a>=6) cout << b/2 << ednl;
    else cout << 0 << endl;
}


Measured memory_bytes: 256
#include<iostream>

int calcHour(int s);
int calcMin(int s);
int calcSec(int s);

int main()
{
	int num, hour, min, sec;

	std::cin >> num;

	hour = calcHour(num);
	min = calcMin(num);
	sec = calcSec(num);

	std::cout << hour << ':' << min << ':' << sec << std::endl;

	return 0;
}

int calcHour(int s)
{
	int H = s / 3600;
	return H;
}

int calcMin(int s)
{
	int M = (s % 3600) / 60;
	return M;
}

int calcSec(int s)
{
	int S = (s % 3600 % 60);
	return S;
}



Measured memory_bytes: 3104
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

using namespace std;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using P = pair<int,int>;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int dp[3003][3003];

int main() {
    int n,t; cin >> n >> t;
    vector<P> f(n);
    rep(i,n) {
        int ai, bi; cin >> ai >> bi;
        f[i] = P(ai,bi);
    }
    sort(all(f));
    
    rep(i,n) {
        rep(j,t+1) {
            dp[i+1][j] = dp[i][j];
            if(j>=f[i].fi) dp[i+1][j] = max(dp[i+1][j],dp[i][j-f[i].fi]+f[i].se);
        }
    }
    int ans = dp[n][t];
    for (int i = 1; i<=n; ++i) {
        int mx = 0;
        for (int j = i; j<=n; ++j) mx=max(mx,f[j].se);
        ans = max(ans, dp[i][t-1]+mx);
    }
    cout << ans << endl;
    return 0;
}















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

typedef long long ll;
int n,m,p;
ll d[2555];
ll d2[2555];
const ll INF = -1e15;
struct edge{
  int from,to,cost;

  edge(int f, int t, int c) : from(f),to(t),cost(c) {}
};

vector<edge> g,g2;

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

  for(int i = 0; i < m; i++) {
    int a,b,c;
    cin >> a >> b >> c;
    a--,b--;
    g.push_back(edge(a,b,c-p));
    g2.push_back(edge(b,a,c-p));
  }

  for(int i = 0; i < n; i++) {
    d[i] = INF;
    d2[i] = INF;
  }
  d[0] = 0;
  d2[n-1] = 0;
  
  for(int i = 0; i < n - 1; i++) {
    for(int j = 0; j < g.size(); j++) {
      edge e = g[j];
      if(d[e.from] == INF) continue;
      if(d[e.to] < d[e.from] + e.cost) d[e.to] = d[e.from] + e.cost;
    }
  }
  ll ans = d[n-1];
   for(int i = 0; i < n - 1; i++) {
    for(int j = 0; j < g.size(); j++) {
      edge e = g[j];
      if(d[e.from] == INF) continue;
      if(d[e.to] < d[e.from] + e.cost) d[e.to] = d[e.from] + e.cost;
    }
   }
   
   for(int i = 0; i < n; i++) {
     for(int j = 0; j < g2.size(); j++) {
       edge e = g2[j];
       if(d2[e.from] == INF || d[e.from] == INF) continue;
       if(d2[e.to] < d2[e.from] + e.cost) {
	 d2[e.to] = d2[e.from] + e.cost;
	 if(i == n-1) {
	   cout << -1 << endl;
	   return 0;
	 }
       }
     }
   }
  
   
   
   if(ans == d[n-1]) cout << max(ans,0ll) << endl;
   else cout << -1 << endl;
  
}


Measured memory_bytes: 512
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <stack>

using namespace std;

#define mod 1000000007

int main()
{
	int n;
	cin >> n;
	int graph[101][101] = {};
	for(int i = 0; i < n; i++){
		int u, k;
		cin >> u >> k;
		u--;
		for(int j = 0; j < k; j++){
			int v;
			cin >> v;
			v--;
			graph[u][v] = 1;
		}
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << graph[i][j];
			if(j == n - 1) cout << endl;
			else cout << " ";
		}
	}
}

Measured memory_bytes: 3112
n = int(input())
h = list(map(int, input().split()))

dp = [0, abs(h[1]-h[0])]
if n >2:
    for i in range(2,n):
        dp.append(min(abs(h[i]-h[i-2])+dp[-2], abs(h[i]-h[i-1])+dp[-1]))
else:
    print(dp[-1])
    exit()

print(dp[-1])

Measured memory_bytes: 13928
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        a: usize, 
        b: usize
    }
    println!("{}", if (a * b) % 2 == 0 { "Even" } else { "Odd" })
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>

using namespace std;

int N, M;
bool e[8][8];

int ans = 0;
bool visited[8];

void dfs(int n,int node) {

	if (n == N) {
		ans++;
		return;
	}

	for (int i = 0; i < N; i++) {
		if (e[node][i] && !visited[i]) {
			visited[i] = true;
			dfs(n + 1, i);
			visited[i] = false;
		}
	}

}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		e[a][b] = e[b][a] = true;
	}
	
	visited[0] = true;
	dfs(1, 0);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 10000

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}



int main(){
  int n,i,j,c=0,key,A[N];
  scanf("%d",&n);
  for(i = 1;i <= n;i++)
    scanf("%d",&A[i]);
 for(i = 1;i <= n;i++){
    key = A[i];    
j = i - 1;
    while(j >=0 && A[j] > key){
      A[j+1] = A[j];
      j--;
    }
  A[j+1] = key;
    trace(A,n);
  }

  return 0;
}


Measured memory_bytes: 2072
#include<iostream>

using namespace std;

int min(int a,int b)
{
	if(a<b)
		return a;
	else
		return b;
}

int mod(int a)
{
	if(a>0)
		return a;
	else
		return -a;
}


int main(){

	int n,i;
	cin >> n;
	int h[n+1],a[n+1];
	for(i=1;i<=n;i++)
		cin >> h[i];

	a[1] = 0;
	a[2] = mod(h[2]-h[1]);

	for(i=3;i<=n;i++)
		a[i] = min(a[i-2]+mod(h[i]-h[i-2]) , a[i-1]+mod(h[i]-h[i-1]));


	cout << a[n] << endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

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

int main(){
  int h, w;
  cin >> h >> w;
  vector<vector<int>> p(h, vector<int>(w));
  rep(i,h){
    rep(j,w)
      cin >> p[i][j];
  }
  int n=0;
  queue<tuple<int, int, int, int>> ans;
  rep(i,h){
    rep(j,w-1){
      if(p[i][j]%2){
        p[i][j]--;
        p[i][j+1]++;
        n++;
        ans.emplace(i+1, j+1, i+1, j+2);
      }
    }
  }
  rep(i,h-1){
    if(p[i][w-1]%2){
        p[i][w-1]--;
        p[i+1][w-1]++;
        n++;
        ans.emplace(i+1, w, i+2, w);
    }
  }
  cout << n << endl;
  while(!ans.empty()){
    tuple<int, int, int, int> res = ans.front();
    ans.pop();
    cout << get<0>(res) << ' ' << get<1>(res) << ' ' << get<2>(res) << ' ' << get<3>(res) << endl;
  }
  return 0;
}

Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vlli vector<ll>
#define vi vector<int>
#define vs vector<string>
#define vplli vector< pair< ll,ll> >
#define plli pair< ll,ll >
#define vps vector< pair< string, string> >
#define vpi vector< pair< int, int> >
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define forn(i,a,n) for(ll i=a;i<n;i++)
#define forr(i,n,a) for(ll i=n-1;i>=a;i--)
#define scan(arr,a,n) for(int i=(a);i<(n);i++)cin>>(arr)[i];
#define print(arr,a,n) for(int i=(a);i<(n);i++)cout<<(arr)[i]<<' ';

const ll inf = 1e18;
const ll N = 1e6 +2;
ll c[N] = {};
ll add(ll x, ll y) {ll res = x + y; return (res >= mod ? res - mod : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= mod ? res % mod : res);}
ll sub(ll x, ll y) {ll res = x - y; return (res < 0 ? res + mod : res);}
ll power(ll x, ll y) {ll res = 1; x %= mod; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}
ll mod_inv(ll x) {return power(x, mod - 2);}

int main(){
	fast;
	ll a, ans = 1;
	cin>>a;
	c[a]++;
	while(1){
		ans++;
		if(a%2 == 0){
			a/=2;
		} else {
			a = 3*a + 1;
		}
		if(c[a]>0){
			break;
		} else {
			c[a]++;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3660
# 2019/06/02
# AtCoder Grand Contest 010 - A

# For the answer:
# Count odd or even
# odd count is odd(&evenccnt >= 1): yes

# Input
n = int(input())
a = list(map(int, input().split()))

# Count odd or even
oddcnt = 0
evencnt = 0
for i in range(n):
    if a[i] % 2 == 1:
        oddcnt += 1
    else:
        evencnt += 1

if evencnt >= 1:
    oddcnt += 1
    if oddcnt % 2 == 1:
        ans = "YES"
    else:
        ans = "NO"
else: 
    if oddcnt % 2 == 0:
        ans = "YES"
    else:
        ans = "NO"

# Output
print(ans)


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

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

// type
using ll = int_fast64_t;
using ull = uint_fast64_t;
using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
//using pair<T1, T2> = p12;

//container
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())
#define ALL(v) v.begin(),v.end()

//repetition
#define REP(n) for(int i=0; i<(n); i++)
#define REPj(n) for(int j=0; j<(n); j++)
#define REPinit(i,a,n) for(int i=(a); i<(n); i++)
#define REPinitj(j,a,n) for(int j=(a); j<(n); j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

//constant

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//Optimizer
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

/* 
	add utility Algorithm
*/

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    int H;
    int ans = 0;
    REPinit(i, 0, N) {
        cin >> H;
        if (H >= K) ans++;
    }

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


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n;
  cin>>n;
  vector<Int> as(n);
  for(Int i=0;i<n;i++) cin>>as[i];

  map<Int, Int> cnt;
  for(Int a:as) cnt[a]++;

  Int res=0;
  for(auto p:cnt) res+=p.second*(p.second-1)/2;

  for(Int i=0;i<n;i++){
    Int ans=res;
    ans-=cnt[as[i]]*(cnt[as[i]]-1)/2;
    cnt[as[i]]--;
    ans+=cnt[as[i]]*(cnt[as[i]]-1)/2;
    cnt[as[i]]++;
    cout<<ans<<newl;
  }

  return 0;
}


Measured memory_bytes: 11136
#include <iostream>

int SumDigits(int num);

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

  if (n % SumDigits(n) == 0) {
    std::cout << "Yes" << std::endl;
  }
  else {
    std::cout << "No" << std::endl;
  } 

  return 0;
}

int Pow(const int base, const int power) {
  int res = 1;
  for (int i = 0; i < power; ++i) res *= base;
  return res;
}

int FindDigit(const int num) {
  int digit = 1;
  while (num / Pow(10, digit) != 0) ++digit;
  return digit;
}

int SumDigits(int num) {
  const int power = FindDigit(num) - 1;
  int sum = 0;
  for (int i = power; i >= 0; --i) {
    sum += num / Pow(10, i);
    num = num % Pow(10, i);
  }
  return sum;
}


Measured memory_bytes: 3612