akhauriyash/Code-Regression huggingface dataset:
/**
 * @brief 最大公約数について扱います
 * @date  2016/03/30
 */



//****************************************
// 必要なヘッダファイルのインクルード
//****************************************

#include <iostream>
#include <cstdint>
#include <tuple>



//****************************************
// オブジェクト形式マクロの定義
//****************************************

//#define NUMBER_THEORY_BEGIN namespace nt {
//#define NUMBER_THEORY_END }



//****************************************
// 型シノニム
//****************************************

using int_t = std::int64_t;
using bit_t = std::uint32_t;
using gcdtrpl_t = std::tuple<int_t, int_t, int_t>;


//****************************************
// 関数の定義
//****************************************

/**
 * @brief  ユークリッドのアルゴリズム(以下、EUCLIDとする)を用いて2つの整数の最大公約数を効率よく計算する
 *
 * @note   EUCLIDはGCD再帰定理に基づいて再帰コードとして書かれている
 *         ただし、入力aとbは任意の非負整数である
 *
 * @note   GCD再帰定理...任意の非負整数aと任意の正整数bに対して次式が成り立つ
 *           gcd(a, b) = gcd(b, a mod b)
 *
 * @note   EUCLIDの全体の実行時間は再帰呼び出しの実行回数に比例する
 *         漸化式 F(k+2) = F(k+1) + Fkによって定義されるフィボナッチ数Fkを利用すると、以下の補題が成り立つ
 *
 *         (補題) a > b >= 0であり、しかもEUCLID(a, b)の呼び出しがk >= 1回の再帰呼び出しを実行するなら、
 *               a >= F(k+2)および b >= F(k + 1)が成り立つ
 *
 *         補題から、次に示す定理が成り立つ
 *         (Lameの定理) 任意の整数k >= 1に対して、a > b >= 0かつb < F(k+1)ならば、
 *                     EUCLID(a, b)の実行では再帰呼び出しの回数はkより少ない
 *
 *         Lameの定理の上界はそれ以上改善できない(best possible)ことを示すことができる
 *         連続するフィボナッチ数がEUCLIDに対する最悪の場合の入力である. EUCLID(F3, F2)は1回だけ
 *         再帰呼び出しをすることと、k >= 2に対してF(k+1) mod Fk = F(k-1)であることから、次式を得る
 *           gcd(F(k+1), Fk) = gcd(Fk, (F(k+1) mod Fk))
 *                           = gcd(Fk, F(k-1))
 *         したがって、EUCLID(F(k+1), Fk)はちょうどk-1回だけ再帰を繰り返すから、Lameの定理の上界に一致する
 *
 * @note   Fkは近似的に(φ^k)/√5(φは黄金比(1+√5)/2)であるから、EUCLIDにおける再帰呼び出しの回数はΟ(lgb)である
 *         実際には、もっとタイトに1+logφ(b/gcd(a,b))に改善できる
 *
 * @param  int_t a   非負整数a
 * @param  int_t b   非負整数b
 * @return a mod b  aとbの最大公約数
 */
int_t euclid_gcd(int_t a, int_t b)
{
    if (b == 0) {
        return a;
    }
    else {
        return euclid_gcd(b, a % b);
    }
}



/**
 * @brief  ユークリッドのアルゴリズム拡張版
 *
 * @note   手続きEXTENDED-EUCLIDは任意の整数の対を入力とし、式 d = gcd(a, b) = ax + byを満たす
 *         (d, x, y)という形式の3項組を返す
 *
 * @note   EUCLIDでの再帰呼び出しの回数はEXTENDED-EUCLIDでの再帰呼び出しの回数に等しいから、
 *         EUCLIDとEXTENDED-EUCLIDの実行時間は定数倍の範囲内で同じである
 *        すなわち、a > b > 0に対して、再帰呼び出しの回数はΟ(lgb)である
 */
gcdtrpl_t extended_gcd(int_t a, int_t b)
{
    if (b == 0) {
        return std::make_tuple(a, 1, 0);
    }
    else {
        int_t d_, x_, y_, d, x, y;
        std::tie(d_, x_, y_) = extended_gcd(b, a % b);
        d = d_; x = y_; y = x_ - (a / b) * y_;
        return std::make_tuple(d, x, y);
    }
}


/**
 * @brief  2つの非負整数a, bの最小公倍数を求めます
 *
 * @param  int_t a 非負整数a
 * @param  int_t b 非負整数b
 * @return a * b / gcd(a, b)
 */
int_t lcm(int_t a, int_t b)
{
    return a * b / euclid_gcd(a, b);
}



//****************************************
// エントリポイント
//****************************************

int main()
{
    using namespace std;
    
    int_t a, b, x, y, d;
    cin >> a >> b;


    tie(d, x, y) = extended_gcd(a, b);

    cout << x << " " << y << endl;

    return 0;
}

Measured memory_bytes: 3096
// Aizu Vol0 0089: The Shortest Path on A Rhombic Path
// 2017.7.30

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

char *gets(char *);
char buf[500];

#define MAX 100

int a[MAX + 5];
int s[MAX + 5], t[MAX + 5];

int GetInts(void)
{
	char *p = buf;
	int i = 0, d;

	while (*p) {
		while (isspace(*p) || *p == ',') p++;
		if (!*p) break;
		d = 0;
		while (isdigit(*p)) d = 10 * d + (*p++ - '0');
		a[i++] = d;
	}
	return i;
}

int main()
{
	int i, n, max;

	max = 0;
	while (gets(buf) != NULL) {
		n = GetInts();
		if (n > max) {
			max = n;
			t[0] = s[0] + a[0];
			for (i = 1; i < n - 1; i++) {
				if (s[i - 1] >= s[i]) t[i] = s[i - 1] + a[i];
				else t[i] = s[i] + a[i];
			}
			t[n - 1] = s[n - 2] + a[n - 1];
		} else {
			for (i = 0; i < n; i++) {
				if (s[i] >= s[i+1]) t[i] = s[i] + a[i];
				else t[i] = s[i+1] + a[i];
			}
		}
		for (i = 0; i < n; i++) s[i] = t[i];
	}
	printf("%d\n", s[0]);
	return 0;
}

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

int main()
{
    long long h,w;
    long long ans = 10000000000;
    cin>>h>>w;
    long long i,a,b,c;
    long long check = 0;
    for(i = 1; i < h; i++)
    {
        a = i*w;
        b = (h-i)*(w/2);
        c = h*w-(a+b);
        check = abs(max(a,(max(b,c)))-min(a,min(b,c)));
        if(check < ans && a*b*c != 0)ans = check;
        b = (h-i)/2*w;
        c = h*w-(a+b);
        check = abs(max(a,(max(b,c)))-min(a,min(b,c)));
        if(check < ans && a*b*c != 0)ans = check;
    }
    for(i = 1; i < w; i++)
    {
        a = i*h;
        b = (w-i)*(h/2);
        c = h*w-(a+b);
        check = abs(max(a,(max(b,c)))-min(a,min(b,c)));
        if(check < ans && a*b*c != 0)ans = check;
        b = (w-i)/2*h;
        c = h*w-(a+b);
        check = abs(max(a,(max(b,c)))-min(a,min(b,c)));
        if(check < ans && a*b*c != 0)ans = check;
    }
    cout << ans << endl;
}

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

#define ll long long
#define eb emplace_back
#define nl '\n'
#define deb(x) cerr << #x" = " << x << nl
#define in() ( { int a ; scanf("%d", &a); a; } )

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

string s[N];
int32_t main()
{
    int n, m, k; cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> s[i];
        s[i] = "#" + s[i];
    }
    int ans = 1e9;
    for(int mask = 0; mask < (1 << (n - 1)); mask++){
        int cnt = __builtin_popcount(mask);
        vector<int> cur(cnt + 1, 0);
        int p = mask | (1 << (n - 1));
        int ultimate = 1;
        //deb(mask);
        for(int j = 1; j <= m; j++){
            //for(auto x: cur) cout << x << ' ';
        //cout << nl;
            int ok = 1;
            vector<int> extra;
            int pp = 0;
            for(int i = 1; i <= n; i++){
                pp += s[i][j] == '1';
                if((p >> (i - 1))&1) extra.eb(pp), pp = 0;
            }
            for(auto x: extra){
                //cout << x << ' ';
                if(x > k){
                    ultimate = 0;
                    break;
                }
            }
            //cout << nl;
            if(ultimate == 0) break;
            for(int i = 0; i < extra.size(); i++){
                cur[i] += extra[i];
                if(cur[i] > k){
                    ok = 0; break;
                }
            }
            if(!ok){
                cnt++;
                cur = extra;
            }
        }
        if(ultimate){
            ans = min(ans, cnt);
            //cout << mask <<  ' ' << cnt << nl;
        }
    }
    cout << ans << nl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i=0; i<N; i++) cin >> A[i];
    sort(A, A+N, greater<int>());
    int sum = 0;
    for (int i=1; i<N; i++) sum += A[i];
    if (A[0] < sum) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int> > Matrix;


int main(){
  int n, m;
  cin >> n >> m;
  vector<int> x(m);
  rep(i, m) cin >> x[i];
  sort(ALL(x));
  if (n >= m) {
    cout << 0 << endl;
    return 0;
  }
  vector<ll> d(m-1);
  rep(i, m-1){
    d[i] = (ll)x[i+1]- x[i];
  }
  sort(ALL(d));
  ll ans = (ll)x[m-1] - x[0];
  rep(i, n-1){
    ans -= d.back();
    d.pop_back();
  }
  cout << ans << endl;
}


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

const int N = 1e6 + 10;
int n, m, ans, sum, a[N], jmp[N];

template <class T> inline void in(T &x) {
	x = 0; int f = 1; char ch = getchar();
	for (; ch<'0' || ch>'9';) {if (ch=='-') f=-1; ch = getchar();}
	for (; ch>='0' && ch<='9';) x = x*10 + ch-'0', ch = getchar();
	x *= f;
}

int main() {
	int x; in(n);
	for (int i = 1; i < n; ++i) in(a[i]);
	for (int i = 1; i < n; ++i) {
		for (int j = sum + 1; j <= sum + a[i]; ++j)
			jmp[j] = (i > 2) ? (2 * sum - j) : j;
		sum += a[i];
	}
	for (int i = 0; i <= sum; ++i)
		if (jmp[i] > 0) jmp[i] = jmp[jmp[i]];
	for (in(m); m --;) {
		in(x);
		ans = sum - x;
		if (ans > 0) ans = jmp[ans];
		printf("%d\n", 2 * a[1] - ans);
	}
	return 0;
}

Measured memory_bytes: 8320
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] s = new int[10001];
		s[0] = 1;
		for (int i = 1; i <= 10000; i++)
			s[i] = s[i - 1] + i;
		while (sc.hasNextInt()) {
			int n = sc.nextInt();
			System.out.println(s[n]);
		}
	}
}

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  
  if (B / A > C){
    cout << C << endl;
  }
  else if (B / A < C){
    cout << B / A << endl;
  }
  else {
    cout << C << endl;
  }

}

Measured memory_bytes: 256
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

#xの約数を昇順に列挙 O(√N)
def Enumeration(x):
    low = []
    high = []
    for i in range(1,x):
        if i**2 >= x:
            if i**2 == x:
                low.append(i)
            break
        if x%i == 0:
            low.append(i)
            high.append(x//i)
    return high+low[::-1]  #降順
#    return low+high[::-1]

def main():
    n,k = map(int,ipt().split())
#    n = 500
#    k = 1
#    a = [10**6 for i in range(n)]
    a = [int(i) for i in ipt().split()]
    sm = sum(a)
    ys = Enumeration(sm)

    for i in ys:
        nm = 0
        vs = [j%i for j in a]
        vs.sort()
        l = 0
        r = n-1
        rs = 0
#        print(vs)
        while l <= r:
            if rs == 0:
                rs = vs[l]
                nm += rs
                l += 1
            if l > r:
                break
            if rs+vs[r] >= i:
                rs = rs-(i-vs[r])
                r -= 1
            else:
                vs[r] += rs
                rs = 0
#        print(i,nm,rs)
        if nm <= k and rs == 0:
            print(i)
            exit()


    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 75412
#include<iostream>
using namespace std;
int main(){
  int i=1,n; 
  cin>>n;
 while(i<n){
   i*=2;
   }
   if(i<=n){
   cout<<i<<endl;
   }
   else if(i>n){
   cout<<i/2<<endl;
   }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N;
  cin >> N;
  int A[100010], B[100010];

  int idx = -1;
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    if (idx < 0 || A[i] > A[idx]) idx = i;
  }
  cout << A[idx] + B[idx] << endl;

  return 0;
}

Measured memory_bytes: 1024
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const int maxn = 2e5 + 10, snd = 1e5 + 10;

vector<int> g[maxn];
int mt[maxn];
int used[maxn];
int cn = 1;
vector<ll> prm = { 0, 1 };
ll dsu[maxn * 2], sz[maxn * 2];
pair<ll, ll> c3[maxn * 2];

ll find(int v) {
	if (dsu[v] == v) return v;
	else return dsu[v] = find(dsu[v]);
}

void uni(int v, int u) {
	u = find(u);
	v = find(v);

	if (sz[u] > sz[v]) swap(u, v);
	if (u != v) {
		dsu[u] = v;
		sz[v] += sz[u];
		c3[v].first += c3[u].first;
		c3[v].second += c3[u].second;
	}
}

bool dfs(int v) {
	if (used[v] == cn) return false;

	used[v] = cn;

	ll rnd = rand() % 2;
	if (rnd == 1) {
		for (int i = 0; i < g[v].size(); i++) {
			int u = g[v][i];
			if (mt[u] == -1 || dfs(mt[u])) {
				mt[u] = v;
				return true;
			}
		}
	}
	else {
		for (int i = 0; i < g[v].size(); i++) {
			int u = g[v][1 - i];
			if (mt[u] == -1 || dfs(mt[u])) {
				mt[u] = v;
				return true;
			}
		}
	}


	return false;
}

vector<tuple<ll, ll, ll>> rcnt[snd];
int main()
{
	fastInp;

	ll n, h, w;
	cin >> n >> h >> w;

	ll vals = 0, ans = 0;
	vector<tuple<ll, ll, ll>> vec;
	for (int i = 0; i < n; i++) {
		dsu[i] = i;
		c3[i] = { 1, 0 };
		sz[i] = 1;
	}

	for (int i = n; i < n + h; i++) {
		dsu[i] = i;
		c3[i] = { 0, 1 };
		sz[i] = 1;
	}
	for (int i = n + h; i < n + h + w; i++) {
		dsu[i] = i;
		c3[i] = { 0, 1 };
		sz[i] = 1;
	}

	for (int i = 0; i < n; i++) {
		ll r, c, a;
		cin >> r >> c >> a;
		r--; c--;
		rcnt[a].push_back({ a, r, c });
	}

	for (int i = snd - 1; i >= 0; i--) {
		for (auto cur : rcnt[i]) vec.push_back(cur);
	}

	ll cnt = 0;
	ll hw = h + w;
	for (int i = 0; i < n; i++) {
		ll r = get<1>(vec[i]), c = get<2>(vec[i]), a = get<0>(vec[i]);
		r += n;
		c += h + n;
		r = find(r);
		c = find(c);
		if (c == r) {
			if (min(c3[c].first + 1ll, c3[c].second) > min(c3[c].first, c3[c].second)) {
				ans += a;
				uni(c, i);
			}
		}
		else {
			if (min(c3[c].first, c3[c].second) + min(c3[r].first, c3[r].second) < min(c3[c].first + c3[r].first + 1ll, c3[c].second + c3[r].second)) {
				ans += a;
				uni(c, i);
				c = find(c);
				uni(c, r);
			}
		}
		/*if (mt[r] == -1 || mt[c + h + 1] == -1) {
			vals++;
			cnt++;
			g[i].push_back(r);
			g[i].push_back(c + h + 1);
			if (mt[r] == -1) {
				mt[r] = i;
			}
			else {
				mt[c + h + 1] = i;
			}
			ans += a;
			continue;
		}
		cn++;
		vals++;

		g[i].push_back(r);
		g[i].push_back(c + h + 1);
		cnt += dfs(i);

		if (cnt >= vals) {
			ans += a;
			continue;
		}
		else {
			vals--;
		}*/
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 25964
n = [int(input()) for _ in range(5)]
min = 11
a = 0

if n.count(n[0]) == len(n):
    y = 0
    for i in range(len(n)-1):
        y += n[i] + (10 - n[i] % 10)
    y += n[-1]
    print(y)
    exit()


for i in range(len(n)):
    
    if not(n[i] % 10 == 0 or n[i] < 10):
        if min > n[i] % 10:
            min = n[i] % 10
            a = n[i]

for j in range(len(n)):
    
    if n[j] % 10 != 0:
        if n[j] != a:
            n[j] = n[j] + (10 - n[j] % 10)


print(sum(n))



Measured memory_bytes: 3188
import sys
input = sys.stdin.readline

# B - Robot Arms
n = int(input())
robots = []

for i in range(n):
	x, l = map(int, input().split())
	left = x - l
	right = x + l
	robots.append([left, right])

robots.sort(key=lambda x: x[1])
prev_robot = -sys.maxsize
ans = 0

for r in robots:
	if r[0] >= prev_robot:
		ans += 1
		prev_robot = r[1]

print(ans)

Measured memory_bytes: 58332
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    string a,b,c;
    cin>>a>>b>>c;
    string s = {a[0],b[0],c[0]};
    transform(s.begin(), s.end(), s.begin(), ::toupper);
    cout<<s<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		String ans = S.replace("eraser", "")
				.replace("erase", "")
				.replace("dreamer", "")
				.replace("dream", "");
		System.out.println(ans.equals("") ? "YES" :"NO");
	}
}

Measured memory_bytes: 30160
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

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

	vector<int> dp(x + 1, false);
	dp[0] = 1;
	for (int i = 0; i <= x; ++i) {
		for (int j = 100; j <= 105; ++j) {
			if (i + j <= x) {
				dp[i + j] |= dp[i];

			}
		}
	}
	cout << (dp[x] ? 1 : 0) << endl;

	return 0;
}


Measured memory_bytes: 640
n=int(input())
x=list(map(int, input().split()))
min_=10**9
for i in range(min(x),max(x)+1,1):
  #print(i)
  sum_=0
  for j in range(n):
    sum_+=(x[j]-i)**2
  if sum_<min_: min_=sum_
  #print(min_)
print(int(min_))

Measured memory_bytes: 3060
n = int(input())
x_l = {}
for i in range(n):
    x,l = map(int, input().split())
    x_l[x] = l
if n ==1 :
    print(1)
    exit()
del_num = 0
sort_x = sorted(x_l.keys())
min_max = [max(0, sort_x[0] - x_l[sort_x[0]]), min(10**9, sort_x[0] + x_l[sort_x[0]])]
for i in sort_x[1:]:
    if min_max[1] >  (i - x_l[i]):
        del_num+=1
        min_max[1] = min(min_max[1], x_l[i] + i) 
    else:
        min_max[1] = (i + x_l[i])
print(n-del_num)

Measured memory_bytes: 17892
#include"iomanip"
#include"iostream"
#include"limits"
#include"cmath"
#include"vector"
#include"algorithm"
#include"list"
#include"queue"
#include"stack"
#include"set"
#include"unordered_set"
#include"map"
#include"unordered_map"
#include"string"
#include"cstring"
#include"assert.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define mp make_pair
#define pb push_back
#define mset(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int x=1;
	int n,k;
	cin>>n>>k;
	while(n--)
	{
		x=min(2*x,x+k);
	}
	cout<<x<<'\n';
}

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



int main() {
    int H,W;
    cin>>H>>W;
    vector<vector<int>> S(H,vector<int>(W));
    rep(i,H){
        rep(j,W){
            char s;
            cin>>s;
            if(s=='.'){S.at(i).at(j)=1;}
            else{S.at(i).at(j)=-1;}
        }
    }
    vector<vector<int>> dp(H,vector<int>(W));
    if(S.at(0).at(0)==1){dp.at(0).at(0)=0;}
    else{dp.at(0).at(0)=1;}
    for(int j=1;j<W;j++){
        if(S.at(0).at(j)==S.at(0).at(j-1)){
            dp.at(0).at(j)=dp.at(0).at(j-1);
        }
        else{dp.at(0).at(j)=dp.at(0).at(j-1)+1;}
    }
    for(int i=1;i<H;i++){
        if(S.at(i).at(0)==S.at(i-1).at(0)){
            dp.at(i).at(0)=dp.at(i-1).at(0);
        }
        else{dp.at(i).at(0)=dp.at(i-1).at(0)+1;}
        for(int j=1;j<W;j++){
            int a,b;
            if(S.at(i).at(j)==S.at(i-1).at(j)){
                a=dp.at(i-1).at(j);
            }
            else{a=dp.at(i-1).at(j)+1;}
            if(S.at(i).at(j)==S.at(i).at(j-1)){
                b=dp.at(i).at(j-1);
            }
            else{b=dp.at(i).at(j-1)+1;}
            dp.at(i).at(j)=min(a,b);
        }
    }
    //cout<<dp.at(H-1).at(W-1)<<endl;
    /*rep(i,H){
        rep(j,W){
            cout<<dp.at(i).at(j);
        }
        cout<<endl;
    }*/
    int ans=dp.at(H-1).at(W-1);
    ans++;
    ans/=2;
    cout<<ans<<endl;
}

Measured memory_bytes: 892
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

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

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

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  // TODO minus case
}

template <class T>
std::ostream &operator<<(std::ostream &s, const std::vector<T> &v) {
  if (v.empty())
    return s;
  s << *v.begin();
  for (auto iter = v.begin() + 1; iter != v.end(); ++iter)
    if (std::is_fundamental<T>::value)
      s << " " << *iter;
    else
      s << std::endl << *iter;
  return s;
}

int main() {
  // Input
  int A, P;
  std::cin >> A >> P;

  // Main
  std::cout << (3 * A + P) / 2 << std::endl;

  // Output

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int S,h,m,s;
    cin >> S;
    h = S / 3600;
    m = (S % 3600) / 60;
    s = (S % 3600) % 60;
    cout << h << ':' << m << ':' << s <<"\n" ;
}


Measured memory_bytes: 3100
n,m=[int(i) for i in input().split(" ")]
x=[int(i) for i in input().split(" ")]

if m<=n:
    print(0)
    exit()

x.sort()
intervals=[]
for i in range(m-1):
    intervals.append(x[i+1]-x[i])

intervals.sort()
result=x[len(x)-1]-x[0]
for i in range(n-1):
    result-=intervals.pop()
print(result)


Measured memory_bytes: 13960
#include "bits/stdc++.h"
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define forn(i, x, n) for (int i = x; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define nl '\n'
#define precision(n) setprecision(n)
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long double ld;
typedef long long ll;

int main() { _
    int n; cin >> n;
    ll sA = 0;
    ll mB = -1;
    
    forn(i, 0, n) {
        ll a, b;
        cin >> a >> b;
        sA += a;
        if (a > b) {
            if (mB == -1) mB = b;
            else mB = min(mB, b);
        }
    }

    if (mB == -1) cout << 0;
    else cout << (sA - mB);
    cout << nl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
	int c = sc.nextInt();
        if(a<b && b<c){
        System.out.println("Yes");
        }else{
        System.out.println("No");
        }
    }
}
 

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

using namespace std;
int a[105];
int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    int count=0;
    for(int j=1; j<=n; j+=2){
        if(a[j]%2!=0){
            count++;
        }
    }
    cout<<count;
    
}

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

typedef long long ll;
using namespace std;

struct UnionFind {
    vector<int> road;
    vector<int> train;
    vector<int> both;

    UnionFind(int N) : road(N), train(N), both(N) {
        road = vector<int>(N, -1);
        train = vector<int>(N, -1);
    }

    int roadRoot(int n) {
        return (road[n] < 0) ? n : road[n] = roadRoot(road[n]);
    }

    int trainRoot(int n) {
        return (train[n] < 0) ? n : train[n] = trainRoot(train[n]);
    }

    void roadUnite(int x, int y) {
        int rx = roadRoot(x);
        int ry = roadRoot(y);
        if (rx == ry)
            return;
        if (road[roadRoot(rx)] > road[roadRoot(ry)])
            swap(rx, ry);
        road[rx] += road[ry];
        road[ry] = rx;
    }

    void trainUnite(int x, int y) {
        int rx = trainRoot(x);
        int ry = trainRoot(y);
        if (rx == ry)
            return;
        if (train[trainRoot(rx)] > train[trainRoot(ry)])
            swap(ry, rx);
        train[rx] += train[ry];
        train[ry] = rx;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k, l;
    cin >> n >> k >> l;
    UnionFind tree(n + 1);
    for (int i = 0; i < k; i++) {
        int p, q;
        cin >> p >> q;
        tree.roadUnite(p, q);
    }
    for (int i = 0; i < l; i++) {
        int r, s;
        cin >> r >> s;
        tree.trainUnite(r, s);
    }
    map<pair<int, int>, int> m;
    for (int i = 1; i <= n; i++) {
        pair<int, int> k(tree.roadRoot(i), tree.trainRoot(i));
        m[k]++;
    }
    for (int i = 1; i <= n; i++) {
        pair<int, int> k(tree.roadRoot(i), tree.trainRoot(i));
        cout << m[k] << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 14368
X = int(input())
Y = X // 100

for a in range(Y+1):
    for b in range(Y-a+1):
        for c in range(Y-a-b+1):
            for d in range(Y-a-b-c+1):
                for e in range(Y-a-b-c-d+1):
                    for f in range(Y-a-b-c-d-e+1):
                        count = a + b + c + d + e + f
                        if b+c*2+d*3+e*4+f*5 == X - (count*100):
                            print(1)
                            exit()

print(0)

Measured memory_bytes: 44968
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        for (int i  = 0; i < n; ++i)
            in.nextInt();

        int ans = 0;
        int cur = 0;
        while (cur < n - 1) {
            // System.err.println(cur);
            ++ans;
            cur += k - 1;
        }

        System.out.println(ans);
    }
}

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

#define W 10000  //W represents the max total weight of items
#define N 100  //N represents the max total number of items
#define V 1000 //V represents the max weight of an item

int value[N],weight[N];
int n,m;  //n represents the total number of items,m represents the total weight of items
						//value[N],weight[W] represent the value and weight of items respectively

void input();  //input the information of items 
void max_value(); //calculate the max value

int main()
{ 
	input();
    return 0;  
}

void input()     //input the information of items 
{
	while(1)
	{
		//cout<<"Please enter number of items and knapsack capacity in one line:"<<endl;
		cin>>n>>m;
		if(n<1||n>N||m<1||m>W)
		{
			cout<<"The input value is out of range!"<<endl;
			cin.clear();
		}
		else 
			break;
	}
	int i;
	for(i=0;i<n;i++)
	{
		value[i]=0;
		weight[i]=0;
	}
	i=0;
	while(1)
	{
		for(;i<n;i++)
		{
			//cout<<"Please input value and weight of item["<<i+1<<"] in one line:"<<endl;
			cin>>value[i]>>weight[i];
			if(value[i]<1||value[i]>V||weight[i]<1||weight[i]>V)
			{
				//cout<<"Please enter a number between 1 and 1000!"<<endl;
				cin.clear();
				break;
			}
		}
		
		if(i>=n)
			break;
	}
	max_value();
}

void max_value()
{ 
	vector<vector<int> > c(n+1,vector<int>(m+1));  //the max value matrix
	int i,w;

	for(i=0;i<=n;i++)     //initialize the 
		c[i][0]=0;
	for(w=1;w<=m;w++)
		c[0][w]=0;

    for(i = 1; i <= n; i++)  
    {  
        for(w = 1; w <= m; w++)  
        {  
            if(w < weight[i-1])  
            {  
                c[i][w] = c[i - 1][w];
            }  
            else  
            {  
                int x =c[i-1][w];  
                int y = c[i][w - weight[i-1]] + value[i-1];  
                c[i][w] = x < y ? y : x; 
            }  
        }  
    }  
	cout<<c[n][m]<<"\r\n";
}



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

namespace agc030_a
{
    class Program
    {
        static void Main(string[] args)
        {
            var text = Console.ReadLine();
            var list = text.Split(' ').ToList().Select(x => int.Parse(x)).ToList();

            var a = list[0];
            var b = list[1];

            var c = a * 3 + b;
            Console.WriteLine((int)(c / 2));
        }
    }
}


Measured memory_bytes: 13268
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
#include <functional>
#include <numeric>
//#include "bits/stdc++.h"
using namespace std;
//using namespace std::vector;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)

#define huge 1000000007
typedef long long int ll;
ll gcd(ll a, ll b);

int main(void) {

	ll N = 0;
	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll D = 0;
	ll M = 0;
	ll T = 0;
	//ll M = 0;
	ll h[1000] = {};
	ll b[100] = {};
	//ll c[100] = {};
	//ll d[100] = {};

	//ll v[3] = {};
	//ll *c, *s, *n;
	//string S,T,U[52];
	ll count = 10;
	ll count2 = 0;
	float sum = 0;
	ll min = 1000000000000;
	ll max = 0;
	ll smax = 0;
	ll max2 = 0;
	ll smax2 = 0;
	int tmax = 0;
	int tmax2 = 0;
	int flag = 0;
	char temp,head;
	//int is = 0;
	
	
	//char p;


	

	

	//cin >> S;
	
	//b = (ll *)malloc(M * sizeof(ll));
	//vector<pair<int,int>> ch(50);

	cin >> N;
	

	//x = (ll *)malloc((N+1) * sizeof(ll));
	//c = (ll *)malloc((N) * sizeof(ll));
	//cin >> D >> G;
	//vector<pair<int,int>> tr(M);
	//vector<pair<int,int>> qes(Q);
	//sort(c.begin(), c.end());
	
	//cout << c[2] - c[1] << endl;

	if (N == 7 || N == 5 || N == 3)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	/*A = N / 1000;
	N %= 1000;
	B = N / 100;
	N %= 100;
	C = N / 10;
	N %= 10;
	D = N;*/
	


	//cin >> N >> M;

	//vector<pair<int,int>> c(M);
	////vector<pair<int, int>> e(M);
	//vector<ll> d(M);

	//rep(i, 0, M) {
	//	cin >> c[i].first >> c[i].second;
	//	//e[i].first = c[i].first;
	//	//e[i].second = c[i].second;

	//}
	////sort(c.begin(), c.end());

	//

	//rep(i, 0, M) {

	//	
	//	
	//	rep(j, 0, M) {
	//		if (c[i].first == c[j].first && c[j].second < c[i].second) {
	//			d[i]++;
	//			//cout << j << endl;
	//		}
	//	}
	//	cout << std::setfill('0') << std::right << std::setw(6) << c[i].first;
	//	cout << std::setfill('0') << std::right << std::setw(6) << d[i]+1 << endl;
	//}

	return 0;

}

ll gcd(ll a, ll b) {
	
	/* 自然数 a > b を確認・入替 */
	if (a<b) {
		ll tmp = a;
		a = b;
		b = tmp;
	}
	ll x = b;
	ll y = a;
	/* ユークリッドの互除法 */
	ll r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}


	return y/b*x;
}



Measured memory_bytes: 384
#include<iostream>
#include<math.h>
#include<algorithm>
#include<string>
using namespace std;
#define int long long
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define vi vector<int>
#define vstr vector<string>
#define vbool vector<bool>
#define vvi vector<vector<int> >
#define mii map<int,int>
#define pb push_back
#define pii pair<int,int>
#define vpair vector<pii > 
#define mkp make_pair
#define scan(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) {cout<<a[i]<<' ';}cout<<'\n'
#define mem(a,v) memset(a,v,sizeof(a))
#define loop(i,a,b) for (int i = a; i < b; i++)
#define loope(i,a,b) for (int i = a; i <= b; i++)
#define FastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PRECISION std::cout.unsetf ( std::ios::fixed );std::cout.precision(9)
#define PI 3.14159265
#define S second
#define F first
#define CHECK cout<<"CHEDEDWB"<<endl
#define br '\n'
int mod = 1e9+7;
int inf = 1e18;
int m_inf = INT_MIN;
int MOD = 100001;

int32_t main()
{
	FastIO; PRECISION;
	int a,b,c,k;
	cin>>a>>b>>c>>k;
	int sum = 0;
	if(a>0 && k>0)
	{
		if(a<=k)
		{
			sum += a;
			k -= a;
			a = 0;
			//cout<<sum<<endl;
		}
		else
		{
			sum += k;
			a -= k;
			k = 0;
		}
	}
	//cout<<k<<"abc"<<endl;
	if(b>0 && k>0)
	{
		if(b<=k)
		{
			k -= b;
			b = 0;
			//cout<<sum<<endl;
		}
		else
		{
			b -= k;
			k = 0;
		}
	}
	//cout<<k<<"abc"<<endl;
	if(c>0 && k>0)
	{
		if(c<=k)
			{
			sum -= c;
			k -= c;
			c = 0;
			//cout<<sum<<endl;
		}
		else
		{
			sum -= k;
			c -= k;
			k = 0;
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 3224
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

func main() {
	n := oneInt()
	as := scanNums(n)

	ans := calc(as)

	fmt.Println(ans)
}

func calc(as []int) int64 {
	var minusCount int
	for _, ai := range as {
		if ai < 0 {
			minusCount++
		}
	}
	var answer int64
	if minusCount%2 == 0 {
		for _, ai := range as {
			answer += int64(abs(ai))
		}
	} else {
		s := make([]int, 0, len(as))
		for _, ai := range as {
			s = append(s, abs(ai))
		}
		sort.Ints(s)
		answer = int64(s[0] * -1)
		for _, si := range s[1:] {
			answer += int64(si)
		}
	}
	return answer
}

func oneInt() int {
	var a int
	fmt.Scan(&a)
	return a
}

func nextWord(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func scanNums(n int) (nums []int) {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < n; i++ {
		s := nextWord(sc)
		num, _ := strconv.Atoi(s)
		nums = append(nums, num)
	}
	return nums
}

func abs(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}


Measured memory_bytes: 5888
#include<stdio.h>
#include<string.h>
int main(void){
    char s[101];
    scanf("%s",s);
    int a = strlen(s);
    for (int i = 0; i < a; i++)
    {
        s[i] = 'x';
    }
    printf("%s\n",s);
    
}

Measured memory_bytes: 1632
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
g=[[] for i in range(n)]
c=[]
dc={}
for i in range(n-1):
    a,b=LI_()
    c.append((a,b))
    g[a].append(b)
    g[b].append(a)
    dc[(a,b)]=0

mxd=0
mxi=0
for i in range(n):
    m=len(g[i])
    if m==1:
        mxd=m
        mxi=i
        
#vには最短距離をセット & -1 で未訪問フラグ

v=[-1]*(n)

def bfs(x):
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        col=0
        for i in g[c]:
            if v[i]==-1:
                if v[c]==col and c!=x:col+=1
                p.append(i)
                v[i]=col
                dc[(c,i)]=col
                dc[(i,c)]=col
#                show(i,c,col)
                col+=1
    return

bfs(mxi)
print(max(v)+1)
for i,j in c:
    print(dc[(i,j)]+1)
    
#show(v)


Measured memory_bytes: 102940
#include<bits/stdc++.h>
using namespace std;
#define inf 100000000000000000
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
void mahakal(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	freopen("error.txt","w",stderr);
	#endif
}

ll arr[4][2]={{0 , -1},{0,1},{1,0},{-1, 0}};

ll solve(vector<string>& vec , ll h ,ll w , ll x , ll y){
	vector<vector<ll>> dist(h , vector<ll>(w , -1));
	queue<pair<ll,ll>> q;
	q.push({x,y});
	ll ans = 0 ;
	dist[x][y]=0;
	while(!q.empty()){
		x=q.front().f;
		y=q.front().s;
		q.pop();
		ans= max(ans , dist[x][y]);
		for(ll i=0;i<4;i++){
			ll nx=x+arr[i][0];
			ll ny=y+arr[i][1];
			if(nx<0 || ny<0 || nx>=h || ny>=w || vec[nx][ny]=='#')continue;
			if(dist[nx][ny]==-1){
				dist[nx][ny]=dist[x][y]+1;
				q.push({nx,ny});
			}
		}
	}
	return ans ;
}

int main(){
	//mahakal();fast;

	ll h , w;
	cin>>h>>w;
	vector<string> vec;
	for(ll i=0;i<h;i++){
		string str;
		cin>>str;
		vec.pb(str);
	}
	ll ans = 0 ;
	for(ll i=0;i<h ;i++){
		for(ll j=0 ; j<w ;j++){
			if(vec[i][j]=='#')continue;
			ans = max(solve(vec , h , w , i , j) , ans);
		}
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <iomanip>
#include <cstdio>
#include <new>
#include <vector>
#include <cstdlib>
#include <string>
#include <set>
#include <tuple>　
#include<map>
#include<queue>

using namespace std;


int main() {
	int N;
	cin >> N;
	vector<int> d(N);

	for (int i = 0; i < N; ++i) {
		cin >> d.at(i);
	}

	sort(d.begin(), d.end());
	reverse(d.begin(), d.end());

	int ans = 1;

	for (int i = 1; i < N; ++i) {
		if (d.at(i) < d.at(i - 1)) ans += 1;
	}

	cout << ans << endl;
}

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

long long int gcd(long long int a, long long int b) {
		if (b == 0) return a;
		return gcd(b, a%b);
	}
	
long long int lcm(long long int a, long long int b) {
		return a/gcd(a,b)*b;
	}
	
int main() {
	long long int n;
	cin >> n;
	long long int t[n];
	for(int i=0;i<n;i++) {
		cin >> t[i];
	}
	long long int lcmtmp = t[0];

	for(int i=0;i<n;i++){
		if(lcmtmp % t[i]!= 0)
			lcmtmp = lcm(lcmtmp,t[i]);
	}
	
	cout << lcmtmp << endl;
	
	return 0;
}

Measured memory_bytes: 256
object Main extends App {

  import scala.io.StdIn._
  import scala.math._

  solve
  def solve: Unit ={
    val n = readLine.trim.toInt
    if (n == 0) return
    val powers = readLine.trim.split(' ').map(_.toLong)
    val sum = powers.sum
    val target = (powers.sum + 1) / 2
    val left = powers.take(n / 2).map(it ⇒ List(0L, it)).foldLeft(List(0L)){case (l, r) ⇒ l.flatMap(it ⇒ r.map(_ + it))}.sorted
    val right = powers.drop(n / 2).map(it ⇒ List(0L, it)).foldLeft(List(0L)){case (l, r) ⇒ l.flatMap(it ⇒ r.map(_ + it))}.sorted.toArray
    println(
      left.map{a ⇒
        lowerBound(right, target - a).let{it ⇒ if (right.indices.contains(it)) right(it) else right.last} + a
      }.map{it ⇒ math.abs(sum - it - it)}.min
    )

    solve
  }
  def upperBound[T <: Ordered[T]](array: Array[T], target: T): Int = {
    var left = 0
    var right = array.length
    while(left < right){
      val mid = (left + right) / 2
      if (array(mid) <= target){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }
  def lowerBound[T](array: Array[T], target: T)(implicit ordering: Ordering[T]): Int = {
    var left = 0
    var right = array.length
    while (left < right){
      val mid = (left + right) / 2
      if (ordering.compare(array(mid), target) < 0){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }
  def lowerBound[T <: Ordered[T]](array: Array[T], target: T): Int = {
    var left = 0
    var right = array.length
    while (left < right){
      val mid = (left + right) / 2
      if (array(mid) < target){
        left = mid + 1
      }else {
        right = mid
      }
    }
    right
  }

  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}


Measured memory_bytes: 57740
import java.util.Scanner;
public class Main {
	public static void main(String[] args)throws Exception{
		Scanner stdIn=new Scanner(System.in);
		int N=stdIn.nextInt();
		long lcm=0;
		for(int i=0;i<N;i++){
			long T=stdIn.nextLong();
			if(i==0)
				lcm=T;
			else{
				if(lcm!=T)
					lcm=lcm/GCD(lcm,T)*T;
			}
		}
		System.out.println(lcm);
	}
	static long GCD( long a, long b ) {
        if( a < b ) { long temp = a; a = b; b = temp; }
        if( b < 1 ) return -1;

        if( a % b == 0 ) return b;
        return GCD( b, a % b );
    }
}


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

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

int direction(char c) {
	int dir;
	if(c == '^')
		dir = 1;
	else if(c == 'v')
		dir = 0;
	else if(c == '>')
		dir = 3;
	else
		dir = 2;
	return dir;
}

int main() {
	int T;
	cin >> T;
	for(int t = 0; t < T; t++) {
		int H, W, N;
		vector<string> board;
		string command;
		cin >> H >> W;
		for(int i = 0; i < H; i++) {
			string s;
			cin >> s;
			board.push_back(s);
		}
		cin >> N >> command;
		char c;
		int x, y;

		for(int i = 0; i < board.size(); i++) {
			for(int j = 0; j < board[i].size(); j++) {
				c = board[i][j];
				if(c == '^' || c == 'v' || c == '>' || c == '<') {
					x = j;
					y = i;
				}
			}
		}
		vector<string> res = board;
		for(int i = 0; i < command.size(); i++) {
			if(command[i] == 'S') {
				int dir = direction(res[y][x]);
				int nx = x + dx[dir], ny = y + dy[dir];
				while(0 <= nx && nx < W && 0 <= ny && ny < H) {
					if(res[ny][nx] == '*') {
						res[ny][nx] = '.';
						break;
					}
					else if(res[ny][nx] == '#') {
						break;
					}

					nx += dx[dir];
					ny += dy[dir];
				}
			}
			else {
				int c = command[i];
				if(c == 'U') {
					if(y > 0 && res[y-1][x] == '.') {
						res[y][x] = '.';
						y--;
					}
					res[y][x] = '^';
				}
				else if(c == 'D') {
					if(y < H-1 && res[y+1][x] == '.') {
						res[y][x] = '.';
						y++;
					}
					res[y][x] = 'v';
				}
				else if(c == 'R') {
					if(x < W-1 && res[y][x+1] == '.') {
						res[y][x] = '.';
						x++;
					}
					res[y][x] = '>';
				}
				else {
					if(x > 0 && res[y][x-1] == '.') {
						res[y][x] = '.';
						x--;
					}
					res[y][x] = '<';
				}
			}
		}

		if(t) cout << endl;
		for(int i = 0; i < res.size(); i++)
			cout << res[i] << endl;
	}
}

Measured memory_bytes: 1212
#include<iostream>
#include<string>
using namespace std;
string s,t;
int main(){
  cin>>s>>t;
  int i;
  for(int i=s.size()-t.size();i>=0;i--){
    if(s[i]=='?' || s[i]==t[0]){
      int j=1;
      while(j<t.size()){
	if(s[i+j]==t[j] || s[i+j]=='?'){
	  j++;
	}else{
	  break;
	}
      }
      if(j==t.size()){
	for(int k=0;k<t.size();k++){
	  s[i+k]=t[k];
	}
	for(int k=0;k<s.size();k++){
	  if(s[k]=='?')s[k]='a';
	}
	cout<<s<<endl;return 0;
      }
    }
  }
  cout<<"UNRESTORABLE"<<endl;
  return 0;
}


Measured memory_bytes: 256
//
//  main.cpp
//  Study
//
//  Created by 佐々木勇星 on 2020/03/12.
//  Copyright © 2020 佐々木勇星. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <map>

using namespace std;


int main(int argc, const char * argv[]) {


    int n, ans = 0;
    cin >> n;
    int d[n];
    
    for(int i=0; i<n; i++) cin >> d[i];
    
    for(int i=0; i<n-1; i++)
    {
        for (int j=i+1; j<n; j++)
        {
            ans += d[i] * d[j];
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define llong long long
int n,m;
int nu[100100];
llong sum[100100];
int main()
{
    scanf("%d%d",&n,&m);
    llong ans=0;
    for(int i=1;i<=n;++i)
        scanf("%d",&nu[i]);
    for(int i=2;i<=n;++i)
    {
        if(nu[i]>=nu[i-1])
        {
            ans+=nu[i]-nu[i-1];
            sum[nu[i-1]+2]++;
            sum[nu[i]+1]--;
        }
        else
        {
            ans+=nu[i]+m-nu[i-1];
            sum[nu[i-1]+2]++;
            sum[m+1]--;
            sum[0]+=m-nu[i-1]-1;
            sum[1]++;
            sum[nu[i]+1]--;
        }
    }
//    cout<<"ans: "<<ans<<endl;
    for(int i=2;i<=m;++i)sum[i]+=sum[i-1];
//    for(int i=0;i<=m;++i)cout<<sum[i]<<" ";cout<<endl;
    for(int i=2;i<=n;++i)
        if(nu[i]>=nu[i-1])
            sum[nu[i]+1]-=nu[i]-nu[i-1]-1;
        else sum[nu[i]+1]-=nu[i]+m-nu[i-1]-1;
//    for(int i=0;i<=m;++i)cout<<sum[i]<<" ";cout<<endl;
    llong ma=0;
    for(int i=1;i<=m;++i)
    {
        sum[i]+=sum[i-1];
        ma=max(ma,sum[i]);
    }
//    for(int i=0;i<=m;++i)cout<<sum[i]<<" ";cout<<endl;
    ans-=ma;
    printf("%lld\n",ans);
    return 0;
}


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

int main()
{
  string s;
  cin>>s;
  bool ok=false;
  char tmp = s[0];
  for(char c: s){
    if(tmp==c)  continue;
    else{
      ok = true;
      break;
    }
  }

  if(ok)  cout<<"Yes"<<endl;
  else  cout<<"No"<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
typedef long long ll;
using namespace std;
ll a7=1000000007;
ll inf=1000000000000000;
typedef pair<ll,ll> l_l;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back


ll min(ll a,ll b){
    if(a<b)return a;
    return b;
}
ll max(ll a,ll b){
    if(a>b)return a;
    return b;
}
ll gcd(ll x,ll y){
    if(x<y) return gcd(y,x);
    if(y==0) return x;
    return gcd(y,x%y);
}

int main(){
    ll a,b;cin>>a>>b;
    ll g=gcd(a,b);
    cout<<(a*b)/g<<endl;
    
    
    return 0;
}




Measured memory_bytes: 256
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

a, b, c, k = ril()
if abs(a - b) > 10**18:
    print('Unfair')
elif k % 2 == 0:
    print(a - b)
else:
    print(b - a)

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

int main(){
  string S;
  cin >> S;
  bool n=false,w=false,s=false,e=false;
  for(int i=0;i<S.size();i++){
    if(S.at(i)=='N'){
      n=true;
    }
    else if(S.at(i)=='W'){
      w=true;
    }
    else if(S.at(i)=='S'){
      s=true;
    }
    else{
      e=true;
    }
  }
  if((n && s && w && e) || (n && s && !w && !e) || (!n && !s && w && e)){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}   

Measured memory_bytes: 3600
class point():
    def __init__(self,arg_x,arg_y):
        self.x = arg_x
        self.y = arg_y
 
def calc_len(a,b):
    from math import sqrt
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
 
x1,y1,x2,y2 = map(float,input().split())
 
p1 = point(x1,y1)
p2 = point(x2,y2)
 
print("%.10f"%calc_len(p1,p2))


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

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;

int main(){
	int N; cin>>N;
	int ans = 0;
	int i = 1;
	for(; ans < N; ++i){
		ans += i;
	}
	int rest = ans - N;
	for(int j = 1; j<i; ++j){
		if(j == rest)continue;
		cout<<j<<endl;
	}
	return 0;
}

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

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();
		String c = sc.next();
		String ans = a.substring(0,1) + b.substring(0,1) + c.substring(0,1);
		System.out.println(ans);
	}

}

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


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

   long long n;
   cin>>n;
   map<long long, long long> m;
   long long a[n];
   long long sum=0;
   for(int i=0; i<n; i++)
   	 {cin>>a[i]; m[a[i]]++; sum+=a[i];}

   long long k;
   cin>>k;

   while(k--)
   { long long l,r;
   	 cin>>l>>r;

   	 sum-=l*m[l];
   	 sum+= r*m[l];
   	 m[r]+= m[l];
   	 m[l]=0;

   	 cout<<sum<<endl;
      


   }



 }

Measured memory_bytes: 10288
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
    int n,c,d = 1e9+9,e=0;
    cin >> n;
    int a[n];
    rep(i,n) cin >> a[i];
    sort(a,a+n);
    c = a[n-1];
    rep(i,n-1){
        if(abs(c/2+1-a[i])<d){
                d = abs(c/2+1-a[i]);
                e = i;
        }
        if(c%2==0){
            if(abs(c/2-a[i])<d){
                d = abs(c/2-a[i]);
                e = i;
            }
        } 
    } 
    cout << c << ' ' <<  a[e] << endl; 
}

Measured memory_bytes: 640
import Data.Char
import Data.List
import qualified Data.ByteString.Char8 as B
main=putStrLn.unwords.map show.solve.tail.unfoldr(B.readInt.B.dropWhile isSpace)=<<B.getContents
solve as=[n,r]where
  n=maximum as
  r=maximumBy(\a b->compare(f a)(f b))$filter(n>)as
  f=min=<<(n-)

Measured memory_bytes: 10840