akhauriyash/Code-Regression huggingface dataset:
# ABC 123 D

import heapq

used = []

def getNext(A, B, C, e):
    ret = []
    val = -e[0]
    idx = e[1]
    if idx[0] + 1 < len(A) and [idx[0]+1, idx[1], idx[2]] not in used:
        v = val - A[idx[0]] + A[idx[0]+1]
        ret.append((-v, [idx[0]+1, idx[1], idx[2]]))
        used.append([idx[0]+1, idx[1], idx[2]])
    if idx[1] + 1 < len(B) and [idx[0], idx[1]+1, idx[2]] not in used:
        v = val - B[idx[1]] + B[idx[1]+1]
        ret.append((-v, [idx[0], idx[1]+1, idx[2]]))
        used.append([idx[0], idx[1]+1, idx[2]])
    if idx[2] + 1 < len(C) and [idx[0], idx[1], idx[2]+1] not in used:
        v = val - C[idx[2]] + C[idx[2]+1]
        ret.append((-v, [idx[0], idx[1], idx[2]+1]))
        used.append([idx[0], idx[1], idx[2]+1])

    return ret

def resolve():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)
    heap = []
    heapq.heapify(heap)
    count = 0
    e = (-(A[0] + B[0] + C[0]), [0, 0, 0])
    heapq.heappush(heap, e)
    used = [e[1]]
    while count < K:
        val = heapq.heappop(heap)
        print(-val[0])
        count +=1
        next = getNext(A, B, C, val)
        for v in next:
            heapq.heappush(heap, v)


if __name__ == "__main__":
    resolve()


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

# define FOR(i,a,b) for (int i=(a);i<(b);i++)
# define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
# define REP(i, n) for (int i = 0; i < (int)(n); i++)
# define RREP(i,n) for (int i=(n)-1;i>=0;i--)

# define int(x) int x; scanf("%d",&x);
# define vint(v,n) vector<int> v(n); REP(i,n) scanf("%d", &v[i]);
# define string(x) string x; cin >> x;

using namespace std;

namespace utils{
  template <typename T> void print(vector<vector<T>> mat) {
    REP (i, mat.size()) {
      REP (j, mat[0].size()) cout << mat[i][j] << ' ';
      cout << endl;
    }
  }

  template <typename T> void print(vector<T> v) {
    REP (i, v.size())
      if (i >= v.size()-1)
	cout << v[i];
      else
	cout << v[i] << ' ';
    
    cout << endl;
  }

  template <typename T> pair<T, T> shape(vector<vector<T>> mat) {
    int d1, d2;

    d1 = mat.size();
    if (d1 > 0) d2 = mat[0].size();
    else int d2 = 0;
    cout << "(" << d1 << ", " << d2 << ")" << endl;
    return make_pair(0, 0);
  }

  template <typename T> vector<vector<T>> empty(int n, int m) {
    vector<vector<T>> mat(n, vector<T>(m));
    return mat;
  }
}


int main() {
  int(a);
  int(b);

  if(a + b < 10)
    cout << a + b << endl;
  else
    cout << "error" << endl;
  
}


Measured memory_bytes: 256
from collections import defaultdict as dd
tree = dd(list)
def dfs_route(tree,start,goal):
    visited = set()
    stack = list()
    visited.add(start)
    stack.append(start)
    while stack:
        node = stack[-1]
        if node == goal:
            return stack
        else:
            child = [x for x in tree[node] if x not in visited]
            if child == []:
                stack.pop()
            else:
                visited.add(child[0])
                stack.append(child[0])
n = int(input())
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
l = dfs_route(tree,1,n)
fl = l[(len(l)-1)//2]
sl = l[(len(l)+1)//2]
tree[fl].remove(sl)
tree[sl].remove(fl)
def gr(tree,start):
    island = set()
    rest = [start,]
    while rest:
        node = rest.pop()
        island.add(node)
        for x in tree[node]:
            if x not in island:
                rest.append(x)
    return(island)
if len(gr(tree,1))*2 > n:
  print("Fennec")
else:
  print("Snuke")

Measured memory_bytes: 34536
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>	
#include <cmath>
#include <string>
#include<math.h>//���炵���̂Œ���
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define Cout(s) cout<<s<<endl
using namespace std;
typedef long long ll;
string Yes(bool b) { if (b) { return "Yes"; } else { return "No"; } }
string YES(bool b) { if (b) { return "YES"; } else { return "NO"; } }
//================================================

int a = 1, b = 0, c, d, n, k = 0, ans = 0;
string s, t;
int mod = 1000000007;

int main()
{
	int s, w; cin >> s >> w;
	if (w >= s)cout << "unsafe" << endl;
	else cout << "safe" << endl;

	return 0;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define N 200005
using namespace std;
typedef long long ll;
ll n, m, i, j, v[N], k, p, cmmmc;
void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
}
int main()
{
    fast();
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
        v[i]/=2;
    }
    p=1;
    while(v[1]%2==0)
    {
        p=p*2;
        v[1]/=2;
    }
    for(i=2;i<=n;i++)
        {if(v[i]%p!=0||(v[i]/p)%2==0)
    {
        cout<<0;
        return 0;
    }
    v[i]/=p;
        }
    m/=p;
    cmmmc=v[1];
    for(i=2;i<=n;i++)
        cmmmc=cmmmc*v[i]/__gcd(cmmmc,v[i]);
    cout<<m/cmmmc-m/(2*cmmmc);
    return 0;
}


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

int main() {
	string o,e,pass;
	
	cin >> o >> e;

	for (int i = 0; i < o.length()+e.length(); i++) {
		if (i % 2 == 0)pass+=o[i/2];
		else pass+=e[i/2];
	}
	cout << pass << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;
int main() {
	LL a, b, c, d;
	cin >> a >> b >> c >> d;
	vector<LL> xy(4);
	xy[0] = b * d;
	xy[1] = a * c;
	xy[2] = b * c;
	xy[3] = a * d;
	sort(xy.begin(), xy.end());
	cout << xy[3] << endl;


	return 0;

}

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

#define ll long long
#define endl "\n"

void solve() {
  ll a, b, k, ans = 1;
  cin >> a >> b >> k;
  ans = __gcd(a, b);
  ll z = ans;
  for (ll i = z; i >= 1; --i) {
    if (a % i == 0 && b % i == 0) {
      ans = i;
      --k;
    }
    if (!k)
      break;
  }
  cout << ans << endl;
}

int main() {
  ll t;
  // cin >> t;
  t = 1;
  while (t--)
    solve();
  return 0;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll l,r;
	cin>>l>>r;
	if(r-l>=2019){
		cout<<0<<endl;
		return 0;
	}
	else{
		ll ans=5000;
		for(ll i=l;i<=r;i++){
			for(ll j=i+1;j<=r;j++){
				ans=min(ans,(i%2019*j%2019)%2019);
			}
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

void solve() {
	int x;
	cin >> x;
	if(x >= 30) cout << "Yes" << endl;
	else cout << "No" << endl;	
}

int main(){
	ios_base::sync_with_stdio(false);
	solve();
    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)

using namespace std;
#define ll long long
#define MAX_N 100000

int par[MAX_N]; // 親の番号
int depth[MAX_N];
int nGroup[MAX_N];
ll ans;

// n要素で初期化
void init(int n){
  for(int i=0; i<n; i++){
    par[i] = i;
    depth[i] = 0;
    nGroup[i] = 1;
  }
}
// 木の根を求める
int root(int x){
  if(par[x] == x){ // 根
    return x;
  } else {
    return par[x] = root(par[x]); // 経路圧縮
  }
}

// xとyが同じ集合に属するか否か
bool same(int x, int y){
  return root(x) == root(y);
}

// xとyの属する集合を併合
void unite(int x, int y){
  ans = 0;
  x = root(x);
  y = root(y);
  if(x == y) return;

  if(depth[x] < depth[y]){
    par[x] = y;
    ans = nGroup[x] * nGroup[y];
    nGroup[y] += nGroup[x];
    nGroup[x] = 0;
  } else {
    par[y] = x;
    ans = nGroup[x] * nGroup[y];
    nGroup[x] += nGroup[y];
    nGroup[y] = 0;
    if(depth[x] == depth[y])
      depth[x]++;
  }
}

int main(){
  init(MAX_N);
  int N, M;
  cin >> N >> M;
  vector<pair<int, int> > bridge;
  for(int i=0; i<M; i++) {
    int A, B;
    cin >> A >> B;
    bridge.push_back(pair<int, int>(A, B));
  }
  vector<int> vAns;
  for(int i=M-1; i>=0; i--){
    pair<int, int> tmp = bridge[i];
    int A = tmp.first, B = tmp.second;
    unite(A, B);
    vAns.push_back(ans);
  }
  ll tmp = 0;
  for(int i=M-1; i>=0; i--) {
    tmp += vAns[i];
    cout << tmp << endl;
  }
  return 0;
}


Measured memory_bytes: 4212
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>
#include<iostream>
#include<iomanip>
using namespace std;

long long mod_inverse(long long a) {
	/*a^{10^9+5}を計算すればよい*/
	int p = 1000000005;
	long long ret = 1;

	while (p > 0) {
		if (p % 2 == 1) {
			ret = (ret * a) % 1000000007;
		}
		a = (a * a) % 1000000007;

		p = p / 2;
	}

	return ret;

}

long long power2(long long n){
	long long ret = 1;
	long long a = 2;
	while (n > 0) {
		if (n % 2 == 1) {
			ret = (ret * a) % 1000000007;
		}
		a = (a * a) % 1000000007;

		n = n / 2;
	}

	return ret;

}
long long n, a, b;
long long ans = 0;

long long c = 1;
long long d = 1;

int main() {

	cin >> n >> a >> b;

	ans += power2(n);
	ans += 1000000006;
	ans = ans % 1000000007;
	for (int i = 0; i < a; i++) {
		c = (c * (n - i)) % 1000000007;
		d = (d * (i + 1)) % 1000000007;
	}

	ans = (ans + 1000000007 - (c * mod_inverse(d)) % 1000000007) % 1000000007;

	for (int i = a; i < b; i++) {
		c = (c * (n - i)) % 1000000007;
		d = (d * (i + 1)) % 1000000007;
	}
	ans = (ans + 1000000007 - (c * mod_inverse(d)) % 1000000007) % 1000000007;

	cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <istream>
#include <map>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i <= (n); ++i)
#define rep1(i,n) for (int i = 1; i <= (n); ++i)
#define REP(a,b) for (int i = a; i <= (b); ++i) 
using namespace std;
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
//
	int n;
	long long x = 0;
	int a; 
	cin >> n;
	vector<long long >L;
	rep0(i, n - 1) {
		cin >> a;

		if (a == 0) {
			cin >> x;
			L.push_back(x);
		}
		else if (a == 1) {
			cin >> x;
			printf("%lld\n", L[x]);
		}
		else {
			L.pop_back();
		}
	}
	return 0;
}


Measured memory_bytes: 5036
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

  string X; cin >> X;
  int N = X.size();
  stack<int> st;

  for (int i = 0; i < N; i++) {
    if (st.empty())
      st.push(X[i]);
    else if (X[i] == 'S') st.push('S');
    else {
      char c = st.top();
      if (c == 'S') st.pop();
      else st.push('T');
    }
  }
  cout << st.size() << '\n';
  return 0;
}

Measured memory_bytes: 1300
#include <stdio.h>
#include <algorithm>

#define BUF 200002
#define LIM_N 10002

char str[BUF];

int N, K;
char S[LIM_N];

void receive_input() {
	fgets(str, sizeof(str), stdin);
	sscanf(str, "%d %d", &N, &K);

	fgets(str, sizeof(str), stdin);
	sscanf(str, "%s", &S);
}

void initialize() {
}

int main(void) {
	receive_input();
	initialize();

	for (size_t i = 0; i < N; i++) {
		if (i == K-1) {
			printf("%c", S[i] - 'A' + 'a');
		} else {
			printf("%c", S[i]);
		}
	}

	return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"

using namespace std;
using LL = long long;

constexpr int N = 1e5 + 5;

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

    int a, b;
    cin >> a >> b;
    cout << 6 - a - b << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<utility>

using namespace std;

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

  int swaps{0};
  for (int i = 0; i < n; ++i)
    for (int j=n-1; j > i; --j)
      if (A[j] < A[j-1])
        swap(A[j], A[j-1]), swaps++;
  
  for (int i = 0; i < n; ++i)
    cout << ((i==0) ? "" : " ") << A[i];
  cout << endl << swaps << endl;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
vector<int> ki[220000],even,odd,one,two,zero;

void dfs(int now,int last = -1,int dist = 0){//始点からの距離が奇数となる頂点の番号、偶数(ryをoddとevenにぶち込むdfs
	if(dist%2)odd.push_back(now);
	else even.push_back(now);
	for(int next :ki[now]){
		if(next == last)continue;
		dfs(next,now,dist+1);
	}
}
//hitachi2020 problem C ThREE
//まず二点間の距離が３になるものを考える前に、二点間の距離が奇数になるような状況について考える（３は奇数だから）
//ある点からdfsをしてそこからの距離をd[i]とする (O(n)でできる)と、二点a,b間の距離はd[a]+d[b] - 2*lca(a,b)
//d[a]とd[b]の偶奇が一致したら、ab間の距離は偶数、そうでなければ奇数となる
//dの偶奇が異なるような二点(a,b)の組すべて（abの距離が奇数になるような二点のペアすべて）に対して、1-nのうち積or和が3の倍数になるペアを割り当てる
//mod3だと、(a,b) が(1,1),(2,2)のペア以外はすべて積か和が0(mod3)となる

int main()
{
	int n;
	cin >> n;
	vector<int> ans(n,0);
	rep(i,n-1){
		int a,b;
		cin >> a >> b;
		a--;b--;
		ki[a].push_back(b);
		ki[b].push_back(a);
	}
	dfs(0);
	int es = even.size();
	int os = odd.size();
	
	rep(i,n){
		if((i+1)%3 == 0)zero.push_back(i+1);
		else if((i+1)%3 == 1)one.push_back(i+1);
		else two.push_back(i+1);
	}
	
	//場合分けは3通り
	if(es <= n/3){//距離偶数となるような頂点の数がn//3以下
		rep(i,es){
			ans[even[i]] = zero.back();//まず距離偶数の頂点に3の倍数を突っ込む
			zero.pop_back();

		}
		rep(i,os){//残りを全部距離奇数の頂点に突っ込む
			if(two.size() > 0){
			    ans[odd[i]] = two.back();
				two.pop_back();
			}
			else if(one.size()> 0){
				ans[odd[i]] = one.back();
				one.pop_back();
			}
			else{
				ans[odd[i]] = zero.back();
				zero.pop_back();
			}
		}
		rep(i,n)cout << ans[i] << endl;

	
	}



	else if(os <= n/3){//さっきとやることおんなじ
		rep(i,os){
			ans[odd[i]] = zero.back();
			zero.pop_back();

		}
		rep(i,es){
			if(two.size() > 0){
			    ans[even[i]] = two.back();
				two.pop_back();
			}
			else if(one.size()> 0){
				ans[even[i]] = one.back();
				one.pop_back();
			}
			else{
				ans[even[i]] = zero.back();
				zero.pop_back();
			}
		}
		rep(i,n)cout << ans[i] << endl;
	
		

	}
	else{//距離奇数の頂点数も偶数の頂点数もn//3より大きいとき
		rep(i,os){
			if(one.size() > 0){//片方に1mod3を全部突っ込む
				ans[odd[i]] = one.back();
				one.pop_back();
			}
			else {
				ans[odd[i]] = zero.back();//余った分は0mod3を
				zero.pop_back();
			}
		}
		rep(i,es){
			if(two.size() > 0){
				ans[even[i]] = two.back();//もう片方に2mod3を突っ込む
				
				two.pop_back();
			}
			else {
				ans[even[i]] = zero.back();//残りは0
				zero.pop_back();
			}
		}
		rep(i,n)cout << ans[i] << endl;


	}

	return 0;
}

Measured memory_bytes: 22772
p=*0..gets.to_i;s=0;f=->a{a>p[a]?p[a]=f[p[a]]:a};a,b=$<.map(&:split).transpose.map{|a|i=0;a.map{|a|[a.to_i,i+=1]}.sort.each_cons(2).map{|(x,i),(y,j)|[y-x,i,j]}};(a+b).sort_by{|a|a[0]}.map{|c,*a|a,b=a.map(&f).sort;a<b&&(s+=c;p[b]=a)};p s

Measured memory_bytes: 53104
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define ll long long
const int N = 2e5 + 1;

void findAns()
{

    ll int n, k;
    cin >> n >> k;

    //cout << k;

    ll int data[n + 1];

    //int x;
    // unordered_set<int> remember;
    for (int i = 1; i <= n; i++)
    {
        cin >> data[i];
        //if (data[i] == 1) remember = i;

    }
    int index = 1;
    int remember[n + 1];

    for (int i = 1; i <= n; i++) remember[i] = -1;
    remember[0] = -1;
    remember[1] = 0;
    ll int count = 0;
    while (count <= k)
    {
        index = data[index];
        count++;
        if(count==k)
        {
             cout<<index;
             return;
        }
        if (remember[index] != -1) break;
        else
            remember[index] = count;
    }
    // if (count > k)
    // {
    //     cout << index;
    //     return;
    // }
    k -= count;
    k = k % (count - remember[index]);

    while (k--)
    {
        index = data[index];
    }
    cout << index;

}
int main()
{
// #ifndef ONLINE_JUDGE
//     freopen("in.txt", "r", stdin);
//     freopen("o1.txt", "w", stdout);
// #endif

    fastio;

    // ll int t;
    // cin >> t;

    // while (t--)
    findAns();
}

Measured memory_bytes: 5996
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
int main()
{
    fast_io;
    long long n, f=0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {

            //cout<<result<<' ';
            for(int k=1; k<=n; k++)
            {
                int result=gcd(i, j);
                f+=gcd(k, result);
            }
        }
    }
    cout<<f<<endl;
    return 0;
}

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

int main(){
    int a,b,c,d,e,f,g,h,n;
    while(cin >> n,n){
    	for(int i = 0;i < n;++i){
        	cin >> a >> b >> c >> d >> e >> f >> g >> h;
        	cout << (a*e - b*f - c*g - d*h) << " " << (a*f + b*e + c*h - d*g) << " " << (a*g - b*h + c*e + d*f) << " " << (a*h + b*g - c*f + d*e) << endl; 	
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, pii> piipii;
map<piipii, ll> dp;
int a[20];
 
ll dfs(int l, int r, int al, int ar){
    if(r-l+1 <= 2) return 0;
    if(dp.count(piipii(pii(l, r), pii(al, ar)))) return dp[piipii(pii(l, r), pii(al, ar))];
    ll res = 1e18;
    for(int i=l+1;i<=r-1;i++){
        res = min(res, a[i]*1ll*(al+ar) + dfs(l, i, al, al+ar) + dfs(i, r, al+ar, ar));
    }
    return dp[piipii(pii(l, r), pii(al, ar))] = res;
}
 
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    printf("%lld\n", dfs(1, n, 1, 1) + a[1] + a[n]);
}

Measured memory_bytes: 16640
/* title: Best Pizza
 * source: JOI2011-2012 Yosen No.3
 * hint:
 * トッピングをx個使用すると仮定した場合、
 * そのx個はカロリーが大きい方からx個選んだものが最適になる
 */



#include <iostream>
#include <vector>
#include <algorithm> // sort を使うため
#include <functional> // greater を使うため
#include <numeric> // accumulate を使うため
using namespace std;


int main()
{
	int N, A, B, C;
	cin >> N >> A >> B >> C;

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

	sort(toppings.begin(), toppings.end(), greater<int>());

	int best = 0;
	for(int x = 0; x <= N; x++) {
		int calory = C + accumulate(toppings.begin(), toppings.begin() + x, 0);
		int cost   = A + B * x;
		best = max(best, calory / cost);
	}

	cout << best << endl;
}

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


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

    if(S.at(2) == S.at(3) && S.at(4) == S.at(5))
    {
        std::cout << "Yes" << std::endl;
    }
    else
    {
        std::cout << "No" << std::endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

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

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }

#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }
template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template<class T, class V>
typename enable_if<is_class<T>::value == 0>::type fill(T &t, const V &v) {
    t = v;
}
template<class T, class V>
typename enable_if<is_class<T>::value != 0>::type fill(T &t, const V &v){
    for (auto &e : t) fill(e, v);
}





int main() {
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    
    int H, A;
    while (cin >> H >> A) {
        cout << (H + A-1) / A << endl;
    }
}


















Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define MOD (int) (1e9+7)
#define INF (int) 2e9
#define LLINF (ll) 2e18

int main(){
    int n, k, r, s, p;
    string t;
    cin >> n >> k >> r >> s >> p;
    cin >> t;

    bool result[n];
    rep(i, t.size()){
        if(i>=k){
            if(t[i]==t[i-k]){
                if(result[i-k]){
                    result[i] = false;
                }else{
                    result[i] = true;
                }
            }else{
                result[i] = true;
            }
        }else{
            result[i] = true;
        }
    }

    int ans = 0;
    rep(i, n){
        if(result[i]){
            if(t[i]=='r'){
                ans += p;
            }else if(t[i]=='s'){
                ans += r;
            }else{
                ans += s;
            }
        }
        // printf("%d\n", ans);    
    }

    cout << ans << endl;
    // printf("%d\n", N);
    return 0;
}

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

int n;

int main() {
  while (1) {
    if (scanf("%d", &n) != 1) break;

    int cnt = 0;
    for (int a=0; a<=9; a++) {
      for (int b=0; b<=9; b++) {
        for (int c=0; c<=9; c++) {
          for (int d=0; d<=9; d++) {
            if (a+b+c+d == n) cnt++;
          }
        }
      }
    }

    printf("%d\n", cnt);
  }
}

Measured memory_bytes: 2612
#include<bits/stdc++.h>
#include<cstring>
#include<climits>
#include<queue>
#include<unordered_set>
#include<algorithm>
#include<iomanip>
#include <typeinfo> 
#include <set>
#define ll long long int
#include <iostream>
using namespace std;
int mat[1005][1005];
int main() {
       
       int n;
       cin>>n;
       ll a[n];
       for(int i=0;i<n;i++){
       	cin>>a[i];
	   }
	   int cnt=0;
	   for(int i=0;i<n-2;i++){
	   	for(int j=i+1;j<n-1;j++){
	   		for(int k=j+1;k<n;k++){
	   			int s1=a[i],s2=a[j],s3=a[k];
	   			
	   			if(s1+s2>s3 && s1+s3>s2 && s2+s3>s1 && s1!=s2 && s1!=s3 && s2!=s3){
	   				cnt++;
	   				//cout<<s1<<" "<<s2<<" "<<s3<<endl;
				   }
			   }
		   }
	   }
	   if(n<3){
	   	cnt=0;
	   }
	   cout<<cnt<<endl;
		return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
    int H,W;
    cin>>H>>W;
     vector<vector<char>> A(H, vector<char>(W));
  	rep(i,H){
      rep(j,W){
        cin>>A[i][j];
      }
    }
     rep(i,H+2){
         rep(j,W+2){
             if(i==0||i==H+1){
                 cout<<"#";
             }
            else if(j==0||j==W+1){
                cout<<"#";
            }
            else{
                cout<<A[i-1][j-1];
            }
         }
         cout<<""<<endl;
     }
}


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

const int MAX_N = (int)1e5 + 5;
int depth[MAX_N], deg_out[MAX_N];
vector<int> G[MAX_N];

void dfs(int s, int p){
    for(auto u : G[s]){
        if(u==p) continue;
        if(depth[u]==-1){
            depth[u] = depth[s] + 1;
            dfs(u, s);
        } else if(depth[u]<depth[s]){
            printf("%d %d\n", u, s);
            deg_out[u]++;
        }
    }
    if(p==-1) return;
    if(deg_out[s]%2){
        printf("%d %d\n", s, p);
        deg_out[s]++;
    } else {
        printf("%d %d\n", p, s);
        deg_out[p]++;
    }
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N, M;
    cin>>N>>M;
    if(M%2){cout<<"-1"<<endl; return 0;}
    for(int i=0;i<M;i++){
        int a, b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    fill(depth, depth+N+1, -1);
    depth[1] = 0;
    dfs(1, -1);
    return 0;
}

Measured memory_bytes: 13952
N = int(input())
a = list(map(int, input().split()))

a_sort = sorted(a, reverse=True)

Asum = 0
Bsum = 0

for i in range(1, N+1):
  if i%2 != 0:
    Asum += a_sort[i-1]
  else:
    Bsum += a_sort[i-1]

print(Asum-Bsum)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
class Program
{
    static void Main()
    {   
        ReadLine();
        string[] text = ReadLine().Split(' ');
        int[] num = new int[text.Length];
        for (int i = 0; i < text.Length; i++){
            num[i] = int.Parse(text[i]);
        }

        int count = 0;
        bool flag = true;
        while (flag)
        {
            for (int i = 0; i < text.Length; i++)
            {
                if (num[i] % 2 == 0)
                {
                    num[i] /= 2;
                }else{
                    flag = false;
                    break;
                }
            }
            if (flag)
                count++;
        }


        WriteLine(count.ToString());
    }
}

Measured memory_bytes: 11092
#include<iostream>
using namespace std;
int main() {
	long long int H, W;
	cin >> H >> W;
	long long int ans = 0;
	if (H * W % 2 == 0) {
		ans = H * W / 2;
	}
	else {
		ans = H * W / 2 + 1;
	}
	if (H == 1 || W == 1) {
		ans = 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <iostream>

char in[4];
int a,b,c,d;
int main(){
  std::cin>>in;
  a=in[0]-'0';
  b=in[1]-'0';
  c=in[2]-'0';
  d=in[3]-'0';
  if(a+b+c+d==7)
    std::cout<<a<<'+'<<b<<'+'<<c<<'+'<<d;
  else if(a+b+c-d==7)
    std::cout<<a<<'+'<<b<<'+'<<c<<'-'<<d;
  else if(a+b-c+d==7)
    std::cout<<a<<'+'<<b<<'-'<<c<<'+'<<d;
  else if(a+b-c-d==7)
    std::cout<<a<<'+'<<b<<'-'<<c<<'-'<<d;
  else if(a-b+c+d==7)
    std::cout<<a<<'-'<<b<<'+'<<c<<'+'<<d;
  else if(a-b+c-d==7)
    std::cout<<a<<'-'<<b<<'+'<<c<<'-'<<d;
  else if(a-b-c+d==7)
    std::cout<<a<<'-'<<b<<'-'<<c<<'+'<<d;
  else
    std::cout<<a<<'-'<<b<<'-'<<c<<'-'<<d;
  
  std::cout<<"=7"<<std::endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,l,r) for (ll i=l;i<=r;i++)
typedef long long ll;
using namespace std;
string s,t;
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    cin>>s>>t;
    int d=__gcd(n,m);
    for (int i=0,j=0;i<n;i+=n/d,j+=m/d){
        if (s[i]!=t[j]) {
            puts("-1");
            return 0;
        }
    }
    printf("%lld\n",1ll*n/d*m);
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    cin >> s;
    cin >> t;
    int a = s.size();
    t.resize(a);
    if(t==s)
        cout << "Yes" <<endl;
    else
        cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
int main(void){
  double a,b;

  scanf("%lf",&a);
  scanf("%lf",&b);

  if(a>b){
    printf("GREATER\n");
  }else if(a<b){
    printf("LESS\n");
  }else if(a==b){
    printf("EQUAL\n");
  }

  return 0;

}



Measured memory_bytes: 128
#include <iostream>
#include <numeric>
#include <bits/stdc++.h>
using namespace std;
// long long -> lint
using lint = long long;
// fast cin and cout from hitonanode-san's code
// w/o 71 ms -> w/ 18 ms (tested on ABC148-D with C++14(GCC 5.4.1))
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;


int main(){
    // input
    int N, K;
    cin >> N >> K;
    priority_queue<lint> H;
    lint tmp;
    for( int i=0; i<N; i++ ){
        cin >> tmp;
        H.push(tmp);
    } 

    // calc
    lint ans = 0;
    for( int i=0; i<N; i++ ){
        tmp = H.top();
        H.pop();
        if( i >= K ) ans += tmp;
    } 

    // out
    cout << ans << endl;
} 

Measured memory_bytes: 2420
import java.util.*;
public class Main {
  public static void main(String args[]) {
    Scanner sc=new Scanner(System.in);
    int N=sc.nextInt();
   
    int count=0;
    for(int i=1;i<=N;++i) {
      int a=sc.nextInt();
      if(a%2==1&&i%2==1)
        count++;
    }
    System.out.println(count);
    
  }
}

Measured memory_bytes: 35944
#include <stdio.h>

int main(){
	long long x,i;
	scanf("%lld",&x);
	i = x/11;
	x -= 11*i;
	i *= 2;
	if(x>0&&x<7) i += 1;
	if(x>6&&x<11) i += 2;
	
	printf("%lld\n",i);
	
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
using namespace std;
int d[6][2]={
	{1,2},
	{-1,3},
	{1,-1},
	{4,5},
	{5,2},
	{2,1}
};
main()
{
	string s;
	while(cin>>s,s!="#")
	{
		int t=0;
		for(int i=0;i<s.size();i++)
		{
			t=d[t][s[i]-'0'];
			if(t<0)break;
		}
		cout<<(t==5?"Yes":"No")<<endl;
	}
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

#define MAX 1000

template <typename T>
struct edge {
    int from, to;
    T cost;
    edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
    bool operator<(const edge& e) const {
        return cost < e.cost;
    }
};

/*
    sからたどりつける負の閉路を検出したとき、空の vector を返す
    頂点数 V, 始点 s, 辺の集合 es, INF として LINF を使うとき :
    vector<ll> dist = BellmanFord(V, s, es, LINF);
*/
template <typename T>
vector<T> BellmanFord(int V, int s, vector<edge<T>>& es, const T INF = 1e9) {
    vector<T> dist(V, INF);
    dist[s] = 0;
    for (int i = 0; i < V - 1; i++) {
        for (edge<T>& e : es) {
            if (dist[e.from] == INF) continue;
            dist[e.to] = min(dist[e.to], dist[e.from] + e.cost);
        }
    }
    for (edge<T>& e : es) {
        if (dist[e.from] == INF) continue;
        if (dist[e.from] + e.cost < dist[e.to]) return vector<T>();
    }
    return dist;
}

template <typename T>
bool FindNegativeLoop(int V, vector<edge<T>>& es) {
    vector<T> dist(V, 0);
    for (int i = 0; i < V; i++) {
        for (edge<T>& e : es) {
            if (dist[e.to] > dist[e.from] + e.cost) {
                dist[e.to] = dist[e.from] + e.cost;
                if (i == V - 1) return true;
            }
        }
    }
    return false;
}

bool visited[MAX];
vector<int> G[MAX];

void dfs(int cur) {
    if (visited[cur]) return;
    visited[cur] = true;
    for (int to : G[cur]) {
        dfs(to);
    }
}

signed main() {
    int n, m;
    cin >> n >> m;
    int a[m], b[m];
    ll c[m];
    rep(i, m) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
        G[b[i]].emplace_back(a[i]);
    }
    dfs(n - 1);
    vector<edge<ll>> es;
    rep(i, m) {
        if (!visited[a[i]] || !visited[b[i]]) continue;
        es.emplace_back(a[i], b[i], -c[i]);
    }
    auto dist = BellmanFord(n, 0, es, LINF);
    if (dist.empty())
        cout << "inf" << endl;
    else
        cout << -dist[n - 1] << endl;
    return 0;
}

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 55;
//const int mod = 1000000007;
const int mod = 998244353;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  ll n; cin >> n;
  if(n%2==1) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 0;
  ll div = 10;
  while(div <= n) {
    ans += n/div;
    div *= 5;
  }
  cout << ans << endl;
}

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

#define mod 1000000007
#define MAX_N 200010
long long inv[MAX_N];
long long factorial[MAX_N];
long long inv_factorial[MAX_N];

void GetInv(){
    for (int i = 1; i < MAX_N; i++) {
        if (i == 1) inv[i] = 1;
        else {
            inv[i] = (mod - (mod / i) * inv[mod % i]) % mod;
            if (inv[i] < 0) inv[i] += mod;
        }
    }
}
void GetFactorial(){
    factorial[0] = 1; inv_factorial[0] = 1;
    for (int i = 1; i < MAX_N; i++) {
        factorial[i] = factorial[i-1] * i;
        factorial[i] %= mod;
        inv_factorial[i] = inv_factorial[i-1] * inv[i];
        inv_factorial[i] %= mod;
    }
}

int main() {
    GetInv(); GetFactorial();
    int n; cin >> n;
    vector<long long> v(n), sum(n+1, 0);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        sum[i+1] = sum[i] + v[i]; 
    }
    long long ans = factorial[n] * (sum[n] % mod) % mod;
    for (int d = 1; d < n; d++) {
        long long a = (sum[n] - sum[d] + sum[n-d]) % mod;
        long long b = factorial[n] * inv[d+1] % mod;
        ans += a * b % mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
	int n;
	long long int k;
	cin >> n >> k;
	auto ab = vector<pair<int, int>>(n);
	for(auto&& abab : ab) cin >> abab.first >> abab.second;
	sort(ab.begin(), ab.end());
	long long int cnt = 0;
	for(auto p : ab){
		cnt += p.second;
		if(k <= cnt){
			cout << p.first << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 1024
import sys 
sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
que = [0]
depth = [-1]*N
depth[0] = 0
while que:
    v = que.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        que.append(nv)
d_to_i = [[] for _ in range(N)]
for i in range(N):
    d_to_i[depth[i]].append(i)
for d in range(N)[::-1]:
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv]<depth[v]:
                continue
            if cnt[nv]:
                cnt[v].append(sum(cnt[nv])+1)
            else:
                cnt[v].append(1)
for i in range(N):
    res = N-1
    for j in cnt[i]:
        res-=j
    cnt[i].append(res)
ans = 0
p = [1]*N
for i in range(1, N):
    p[i] = p[i-1]*2%mod
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = p[N-1]-1
    for a in cnt[v]:
        res-=p[a]-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)







Measured memory_bytes: 115448
n=int(input())
a=[]
for i in range(n):
	b, c= input().split()
	a.append([b,int(c)])
x=input()
ans=0
for i in range(n):
	if a[n-i-1][0]==x:
		break
	ans+=a[n-i-1][1]
print(ans)

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

using namespace std;

int cnt[100000];

int main()
{
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  map<char, long long> m;
  cnt[0]++;
  for (int i = 0; i < n; i++)
  {
    cnt[i] += m[t[i]] % 1000000007;
    m[s[i]] = (cnt[i] + m[s[i]]) % 1000000007;
  }
  cout << cnt[n - 1] << endl;

  return 0;
}



Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

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

/*-------------------------------------------*/

int N, M, Q;
vector<vector<int>> G, ans;

void f(int v, int d, int c) {
    int i = d;
    while(i >= 0 && ans[v][i] == 0)
        ans[v][i--] = c;
    if(i != d)
        for(int u : G[v])
            f(u, d - 1, c);
}

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

    cin >> N >> M;
    G.resize(N);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    cin >> Q;
    vector<int> v(Q), d(Q), c(Q);
    rep(i, Q) {
        cin >> v[i] >> d[i] >> c[i];
        v[i]--;
    }

    ans.assign(N, vector<int>(11));
    while(Q--)
        f(v[Q], d[Q], c[Q]);

    rep(i, N) cout << ans[i][0] << endl;

    return 0;
}

Measured memory_bytes: 16248
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[1001][1001],x,y,ans=0;
	char b[1001][1001],c;
	
	priority_queue <pair<int,int> > xy;
	
	cin>>x>>y;
	
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			cin>>c;
			b[i][j]=c;
			if(c=='#') {
				a[i][j] = 0;
				xy.push(make_pair(i,j));
			}
			else a[i][j] = x + y -1;
		}
	}
		
//	while(!xy.empty()){
//		int xx = xy.top().first;
//		int yy = xy.top().second;
//		//cout<<xx<<yy<<'\n';
//		xy.pop();
//		for(int i=0;i<y;i++){
//			if(a[xx][i]==-1) a[xx][i] = abs(yy-i);
//			else a[xx][i] = min(a[xx][i],abs(yy-i)); 
//		}
//		for(int i =0;i<x;i++){
//			if(a[i][yy]==-1) a[i][yy] = abs(xx-i);
//			else a[i][yy] = min(a[i][yy],abs(xx-i));
//		}
//	}
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
//			if(a[i][j]==-1){
//				a[i][j] = x + y -1;
//			}
			if(i>0 && a[i-1][j]!=-1) a[i][j] = min(a[i][j],a[i-1][j]+1);
			if(i<x-1 && a[i+1][j]!=-1) a[i][j] = min(a[i][j],a[i+1][j]+1);
			if(j>0 && a[i][j-1]!=-1) a[i][j] = min(a[i][j],a[i][j-1]+1);
			if(j<y-1 && a[i][j+1]!=-1) a[i][j] = min(a[i][j],a[i][j+1]+1);
			//ans = max(ans,a[i][j]);
			//cout<<a[i][j];
		}
		//cout<<'\n';
	}
	for(int i=x-1;i>=0;i--){
		for(int j=y-1;j>=0;j--){
//			if(a[i][j]==-1){
//				a[i][j] = x + y -1;
//			}
			if(i>0 && a[i-1][j]!=-1) a[i][j] = min(a[i][j],a[i-1][j]+1);
			if(i<x-1 && a[i+1][j]!=-1) a[i][j] = min(a[i][j],a[i+1][j]+1);
			if(j>0 && a[i][j-1]!=-1) a[i][j] = min(a[i][j],a[i][j-1]+1);
			if(j<y-1 && a[i][j+1]!=-1) a[i][j] = min(a[i][j],a[i][j+1]+1);
			ans = max(ans,a[i][j]);
			//cout<<a[i][j];
		}
		//cout<<'\n';
	}
//	for(int i=0;i<x;i++){
//		for(int j=0;j<y;j++){
//			ans = max(ans,a[i][j]);
//		}
//	}
	cout<<ans<<'\n';
}

Measured memory_bytes: 12908
import sys
INF = 10**9
sys.setrecursionlimit(INF)


def main():
    n, k, *a = map(int, open(0).read().split())
    a = [i - 1 for i in a]
    # print(a)

    loc = [0]
    dist = {0: 0}
    for i in range(k):
        # print(loc, dist)
        if a[loc[-1]] in dist:
            ans = loc[dist[a[loc[-1]]] + (k - dist[a[loc[-1]]]) % (dist[loc[-1]] - dist[a[loc[-1]]] + 1)]
            break
        loc.append(a[loc[-1]])
        dist[loc[-1]] = i + 1
    else:
        ans = loc[-1]

    ans += 1
    print(ans)
    return(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 31716
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
points = []

for _ in range(N):
    x,y = inpl()
    t = math.atan2(y,x)
    points.append((t,x,y))

points.sort()

ans = 0
for s,[theta,x,y] in enumerate(points):
    tmpx = tmpy = 0
    for t in range(s,s+N):
        _,tx,ty = points[t%N]
        tmpx += tx
        tmpy += ty
        ans = max(ans,tmpx**2 + tmpy**2)

print(math.sqrt(ans))


Measured memory_bytes: 4456
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;


int main(){
    long a,b,c,d;
    cin >> a >> b >> c >> d;
    
    long v = a*c;
    if(a*d>v) v = a*d;
    if(b*c>v) v = b*c;
    if(b*d>v) v = b*d;
    cout << v << endl;

    return 0;
}


Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {

	public static String Y = "Yes";
	public static String N = "No";
	public static long MOD = (long) (Math.pow(10, 9) + 7);
	public static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int n = ni();
		int x = ni();
		int t = ni();

		if (n % x == 0) {
			out(t * n / x);
		} else {
			out(t * (n / x + 1));
		}

	}

	/*
	 * 以下メソッド集
	 */

	public static void permutation(String q, String ans) {
		// Base Case
		if (q.length() <= 1) {
			System.out.println(ans + q);
		}
		// General Case
		else {
			for (int i = 0; i < q.length(); i++) {
				permutation(q.substring(0, i) + q.substring(i + 1),
						ans + q.charAt(i));
			}
		}
	}

	static char[][] same(char[][] c, int h, int w) {

		char[][] a = new char[h][w];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				a[i][j] = c[i][j];
			}
		}
		return a;

	}

	static int countkuro(char[][] c) {

		int count = 0;
		for (char[] cc : c) {
			for (char ccc : cc) {
				if ('#' == ccc) {
					count++;
				}
			}
		}
		return count;
	}

	static void debug() {

		out("---");
	}

	static void debug(Object a) {

		out("-------");
		out(a);
		out("-------");
	}

	static int ketasuu(int n) {

		String str = "" + n;
		return str.length();
	}

	static int account(String str) {

		String target = "AC";
		int count = 0;
		int len = str.length();
		for (int i = 0; i < len - 1; i++) {
			if (target.equals(str.substring(i, i + target.length()))) {
				count++;
			}
		}
		return count;
	}

	static int ni() {

		return sc.nextInt();
	}

	static long nl() {

		return sc.nextLong();
	}

	static double nd() {

		return sc.nextDouble();
	}

	static String n() {

		return sc.next();
	}

	static char[] nc() {

		return sc.next().toCharArray();
	}

	static int kaijo(int n) {

		if (n == 0 || n == 1) {
			return 1;
		} else {
			return n * kaijo(n - 1);
		}
	}

	static int fib(int n) {

		return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
	}

	static long lcm(long m, long n) {

		return m * n / gcd(m, n);
	}

	static int lcm(int m, int n) {

		return m * n / gcd(m, n);
	}

	static long gcd(long a, long b) {

		return (b == 0) ? a : gcd(b, a % b);
	}

	static int gcd(int a, int b) {

		return (b == 0) ? a : gcd(b, a % b);
	}

	static void out(Object obj) {
		System.out.println(obj);
	}

	static void outn(Object obj) {
		System.out.print(obj);
	}

	static double max(double d, double e) {

		return Math.max(d, e);
	}

	static long max(long a, long b) {

		return Math.max(a, b);
	}

	static long min(long d, long e) {

		return Math.min(d, e);
	}

	static int min(int a, int b) {

		return Math.min(a, b);
	}
}

class XY {

	int h;
	int c;

	XY(int h, int c) {
		this.h = h;
		this.c = c;
	}
}


Measured memory_bytes: 35764
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

void solve()
{
	string s;
	cin>>s;
	if(s[s.length()-1]=='s')
		s += "es";
	else
		s += 's';
	cout<<s<<endl;
}

int main()
{
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}

Measured memory_bytes: 3624
p[169]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,0};
a;
main(b){
scanf("%d",&b);
printf("%d:",b);
while(p[a]){
if(b==1)break;
if(!(b%p[a]))b/=p[a],printf(" %d",p[a]);else a++;
}
if(b!=1)printf(" %d",b);
puts("");
}

Measured memory_bytes: 1836
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
*/

ll sa[100010]={},ta[100010]={},q;

void init(){
	string s,t;
	cin>>s>>t>>q;
	rep(i,s.size()){
		if(s[i]=='A')sa[i+1]=1+sa[i];
		if(s[i]=='B')sa[i+1]=2+sa[i];
	}
	rep(i,t.size()){
		if(t[i]=='A')ta[i+1]=1+ta[i];
		if(t[i]=='B')ta[i+1]=2+ta[i];
	}
	rep(i,q){
		ll a,b,c,d;
		cin>>a>>b>>c>>d;
		cout<<((sa[b]-sa[a-1])%3==(ta[d]-ta[c-1])%3?"YES":"NO")<<endl;
	}
}

int main(void){
	init();
	return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N; cin >> N;
  vector<ll> A(N);
  vector<ll> AA(1e5+10, 0);
  ll ans = 0;
  REPLL(i, N){
    cin >> A[i];
    AA[A[i]]++;
    ans += A[i];
  }
  ll Q; cin >> Q;
  vector<ll> B(Q);
  vector<ll> C(Q);
  REPLL(i, Q){
    cin >> B[i] >> C[i];
  }
  REPLL(i, Q){
    ans -= AA[B[i]]*B[i];
    ans += AA[B[i]]*C[i];
    AA[C[i]] += AA[B[i]];
    AA[B[i]] = 0;
    cout << ans << endl;
  }

}

Measured memory_bytes: 6364