akhauriyash/Code-Regression huggingface dataset:
//:):):):):)
//I'M THE FASTEST MAN ALIVE!!!!

#include<bits/stdc++.h>
#define For(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define vi vector<int>
#define vii vector<vector<int>>
#define vll vector<long long>  
#define vd vector<double>
#define pi (int,int)
#define vpi vector<pair<int,int>>
#define vs vector<string>
#define mp make_pair
#define ll long long
#define vc vector<char>
#define rng(x) x.begin(),x.end()
#define B(x) x.begin()
#define E(x) x.end()
#define F first
#define S second
#define me max_element
#define ne min_element
#define LL "%I64d"
#define pie 3.1415926536
using namespace std;

void ans()
{
  ll n,i,cnt=0;
  cin>>n;
  vi a(n),b(n),ans;
  For(i,0,n) cin>>a[i]>>b[i];
  For(i,0,n)
  {
    if(a[i]==b[i]) cnt++;
    else{
      ans.pb(cnt);
      cnt=0;
    }
  }
  if (cnt>0) ans.pb(cnt);
  if(*me(rng(ans))>2) cout<<"Yes";
  else cout<<"No";
}

//OHH BHAI KAHA??? UPAR TOH DEKHO !!!
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  
  // int t;cin>>t;
  // sieve();
  // while(t--)
    ans();
  return 0;  
}

Measured memory_bytes: 3640
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long int ll;
#define MOD (1000000007);
#define INF (2e9)

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

	if(2*n>=m){
		cout<<m/2<<endl;
	}else{
		cout<<n+(m-2*n)/4<<endl;
	}

	return 0;
}

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

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

#define endl '\n'
#define int long long

const int N = 1e5+5;
int dp[N];

int32_t main()
{
	IOS;

	int n, k; cin >> n >> k;
	int a[n+5];
	memset(dp, 0, sizeof(dp));
	for(int i = 1; i <= n; i ++) 
		cin >> a[i];
	for(int stones = 0; stones <= k; stones ++) {
		for(int j = 1; j <= n; j ++) {
			if(stones - a[j] >= 0 and ! dp[stones - a[j]]) dp[stones] = 1;
		}
	}
	
	if(dp[k]) cout << "First" << endl;
	else cout << "Second" << endl;

	return 0;
}

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

using namespace std;
const int maxn = 200005;
struct Node{
    long long x,l,r;
}node[maxn],temp[maxn];
int main()
{
    long long n;
    cin >>n;
    for(int i=1; i<=n; i++){
        scanf("%lld",&node[i].x);
    }
    stack<int> s;
    for(int i=1; i<=n; i++){
        while(s.size() &&node[s.top()].x>=node[i].x)
            s.pop();
        if(s.empty()) node[i].l = 0;
        else    node[i].l = s.top();
        s.push(i);
    }
    while(!s.empty())
        s.pop();
     for(int i=n; i>=1; i--){
        while(s.size() &&node[s.top()].x>=node[i].x)
            s.pop();
        if(s.empty()) node[i].r = n+1;
        else    node[i].r = s.top();
        s.push(i);
    }
    long long sum =0;
    for(int i=1; i<=n; i++){
           // cout <<node[i].l << " "<<node[i].x << " "<<node[i].r <<endl;
            long long cnt = 1+(i-node[i].l-1)+(node[i].r-i-1)+(i-node[i].l-1)*(node[i].r-i-1);
           // cout <<cnt <<endl;
           // cout <<endl;
            sum += cnt*node[i].x;
    }
    cout <<sum <<endl;
    return 0;
}


Measured memory_bytes: 6400
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using Pc = pair<double, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.1415;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

//////////////////////////////////

vector<vector<int>> bingo(3, vector<int>(3));
vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

struct People {
	int index;
	int town;
	int year;
	People(int i, int t, int y) {
		index = i;
		town = t;
		year = y;
	}
};

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

struct UnionFind {
	vector<int>uf;

	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

ll getGcd(ll a, ll b) {
	if (a < b) {
		ll temp = b;
		b = a;
		a = temp;
	}

	ll r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}

int main() {
	int N; cin >> N;
	map<string, int>S;
	for (int i = 0; i < N;++i) {
		string str; cin >> str;
		S[str] = 1;
	}
	int ans = S.size();
	cout << ans << endl;
}



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

int a, d, n;

bool isPrime(int x) {
  int l = (int)sqrt(x);
  if(x == 1) return false;
  if(x == 2) return true;
  if(x % 2 == 0) return false;
  for(int i = 3; i <= l; i += 2) {
    if(x % i == 0) return false;
  }
  return true;
}

int solve() {
  int cnt = 0;
  int tmp = a;
  for(int i = 0; ; i++) {
    if(isPrime(tmp)) {
      cnt++;
      if(cnt == n) return tmp;
    }
    tmp += d;
  }
}

main() {
  while(1) {
    cin >> a >> d >> n;
    if(a == 0 && d == 0 && n == 0) break;
    
    cout << solve() << endl;
  }
}

Measured memory_bytes: 0
import math

N = int(input())
A = [int(i) for i in input().split()]

mul_num = 0
two_num = 0
other_num = 0

for i in A:
    if i % 4 == 0:
        mul_num += 1
    elif i % 2 == 0:
        two_num += 1
    else:
        other_num += 1

if mul_num + two_num//2 >= N // 2:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 14252
#include <bits/stdc++.h>
using namespace std;
typedef bool boool;
typedef long long ll;
#define vl vector<ll>
#define vb vector<boool>
#define vs vector<string>
#define vp vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define vvp vector<vector<pair<ll, ll>>>
#define mod 1000000007
#define all(x) x.begin(), x.end()
#define rep1(i, n) for (long long i=0; i<(long long)(n); i++)
#define rep2(i, s, e) for (long long i=(s); i<(long long)(e); i++)
#define GET_MACRO(_1,_2,_3,NAME,...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

struct UnionFind {
    vector<int> par;

    UnionFind(int n) : par(n, -1) { }

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {
        return -par[root(x)];
    }
};
/*
----------- usage ---------------------------------------
UnionFind uf(N); --- n個の要素を全て根として初期化
uf.merge(a, b); --- aとbが属するグループを併合
uf.issame(a, b) --- aとbが同じグループに属しているかを確認
uf.size(x); --- xが属するグループに含まれる要素数
---------------------------------------------------------
*/

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        uf.merge(a, b);
    }
    set<int> st;
    rep(i, n){
        st.insert(uf.root(i));
    }
    cout << (int)st.size() - 1 << endl;
    return 0;
}

Measured memory_bytes: 7680
import java.util.*;

public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		while(true){
			String result ="No";
			int gems_number = sc.nextInt();
			if(gems_number==0) break;
			int gems_checker =0;
			int[][] gems = new int[21][21];
			//Arrays.fill(gems,0);
			for(int i=0;i<gems_number;i++){
				int x = sc.nextInt();
				int y = sc.nextInt();
				gems[x][y] = 1;
			}
			int operation_counter = sc.nextInt();
			int xx=10,yy=10;
			for(int i=0;i<operation_counter;i++){
				String dir = sc.next();
				int dis = sc.nextInt();
				//check(dis,xx,yy,gems,dir,gems_checker,gems_number,result);
				if(result.equals("No")){
					if(dir.equals("N")){
						for(int j=1;j<=dis;j++){
							yy++;
							if(gems[xx][yy]==1){
								gems_checker++;
								gems[xx][yy]=0;
							}
							if(gems_number ==gems_checker){
								result = "Yes";
								break;
							}
						}
					}else if(dir.equals("S")){
						for(int j=1;j<=dis;j++){
							yy--;
							if(gems[xx][yy]==1){
								gems_checker++;
								gems[xx][yy]=0;
							}
							if(gems_number ==gems_checker){
								result = "Yes";
								break;
							}
						}
					}else if(dir.equals("W")){
						for(int j=1;j<=dis;j++){
							xx--;
							if(gems[xx][yy]==1){
								gems_checker++;
								gems[xx][yy]=0;
							}
							if(gems_number ==gems_checker){
								result = "Yes";
								break;
							}
						}
					}else{
						for(int j=1;j<=dis;j++){
							xx++;
							if(gems[xx][yy]==1){
								gems_checker++;
								gems[xx][yy]=0;
							}
							if(gems_number ==gems_checker){
								result = "Yes";
								break;
							}
						}
					}
				}
				//if(result.equals("Yes")) break;
			}
			System.out.println(result);
		}
	}
}

Measured memory_bytes: 35036
import heapq, sys
def input():
	return sys.stdin.readline()[:-1]

class DijkstraList():
	#隣接リスト版
	#同一頂点の複数回探索を防ぐため訪問した頂点数を変数cntで持つ
	def __init__(self, adj, start):
		self.list = adj
		self.start = start
		self.size = len(adj)

	def solve(self):
		self.dist = [10**30 for _ in range(self.size)]
		self.dist[self.start] = 0
		self.q = []
		self.cnt = 0

		heapq.heappush(self.q, (0, self.start))

		while self.q and self.cnt < self.size:
			u_dist, u = heapq.heappop(self.q)
			if self.dist[u] < u_dist:
				continue
			for v in self.list[u]:
				if self.dist[v] > u_dist + 1:
					self.dist[v] = u_dist + 1
					heapq.heappush(self.q, (self.dist[v], v))
			self.cnt += 1
		return

	def distance(self, goal):
		return self.dist[goal]

n, m = map(int, input().split())
adj = [[] for _ in range(3*n)]
for _ in range(m):
	u, v = map(int, input().split())
	adj[u-1].append(v-1+n)
	adj[u-1+n].append(v-1+2*n)
	adj[u-1+2*n].append(v-1)
s, t = map(int, input().split())
s, t = s-1, t-1

d = DijkstraList(adj, s)
d.solve()
ans = d.distance(t)
print(ans//3 if ans != 10**30 else -1)

Measured memory_bytes: 60036
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

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

    ll a,b,c,d,n,maxi=0,f=0,mini=INF,sum=0;
    ll m;
    cin>>n>>m;
    vector<ll> v(m);
    set<ll> s;
    rep(i,m) {
        cin>>a;
        s.insert(a);
    }
    ll dp[1000000];
    dp[0]=1;
    rep(i,n){
        if(s.find(i+1)==s.end()) dp[i+1]+=dp[i];
        if(i!=n-1&&s.find(i+2)==s.end()) dp[i+2]+=dp[i];
        dp[i+1]%=mod;
        dp[i+2]%=mod;
    }
    cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 9552
N,M = map(int,input().split())
A = []
for i in range(M):
    A.append(int(input()))
for i in range(M-1):
    if A[i+1]-A[i] == 1:
        print(0)
        exit()
L = []
k = [i for i in range(N+1)]
a = 0
for i in range(M):
    L.append(k[a:A[i]])
    a = A[i]+1
L.append(k[a:N+1])
ans = 1
B = [0,1]
for i in range(N-M):
    B.append(B[-2] + B[-1])
for i in range(len(L)):
    ans *= B[len(L[i])]
print(ans%1000000007)

Measured memory_bytes: 464792
import java.util.Scanner;

public class Main{
  static int warizan(int p){
    int n = p;
    int c = 0;//カウント
    while(true){
      n = n/100;
      if(n==0){
        break;
      }
      c += 1;
    }
    if(p%Math.pow(100,c)==0){
      return c;
    }else{
      return -1;
    }

  }
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int i=0;

    i = (int)Math.pow(100,n) * (m+m/100);
    System.out.println(i);
  }
}

Measured memory_bytes: 25300
n = int(input())
a = list(map(int, input().split()))
q = int(input())

cnt = {}
for i in a:
  if not i in cnt:
    cnt[i] = 0
  cnt[i] += 1
  
queries = []
for i in range(q):
  b, c = map(int, input().split())
  queries.append((b, c))

ans = sum(a)  
  
for (b, c) in queries:
  if b in cnt:
    ans -= cnt[b]*b
    ans += cnt[b]*c
    if not c in cnt:
      cnt[c] = 0
    cnt[c] += cnt[b]
    cnt[b] = 0
  print(ans)

Measured memory_bytes: 30568
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef std::int_fast64_t i64;
typedef std::uint_fast64_t u64;
typedef std::int_fast32_t i32;
typedef std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(std::vector<T>& vector, const typename std::vector<T>::size_type size) {
    vector.reserve(size);
    std::copy_n(std::istream_iterator<T>(std::cin), size, std::back_inserter(vector));
  }

  template <typename T, std::size_t N>
  void read(std::array<T, N>& array) {
    std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
  }
}

#endif

// main.cpp

class shop {
public:
  i64 unit_price;
  i64 stock;
};

namespace std {
  std::istream& operator>>(std::istream& is, shop& self) {
    return is >> self.unit_price >> self.stock;
  }
}

int main() {
  i64 N, M;
  std::cin >> N >> M;
  std::vector<shop> shops;
  tools::read(shops, N);

  std::sort(shops.begin(), shops.end(), [](const shop& x, const shop& y) { return x.unit_price < y.unit_price; });
  i64 answer = 0;
  for (const shop& shop : shops) {
    if (M <= shop.stock) {
      answer += shop.unit_price * M;
      M = 0;
      break;
    } else {
      answer += shop.unit_price * shop.stock;
      M -= shop.stock;
    }
  }

  std::cout << answer << std::endl;
  return 0;
}

Measured memory_bytes: 1792
/*Template by hemnath_d(Enlightened by chamow)*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define vec vector<ll>
#define pll pair<ll,ll>
#define fastread ios_base::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fx first
#define sx second
#define inf 100000000000000
#define minf -100000000000000
#define maxi 100005
ll n,k,arr[maxi];
ll memo[maxi];
ll solve(ll pos)
{
	if(pos==n-1)
		return 0;
	if(pos==n-2)
		return abs(arr[n-1]-arr[n-2]);
	if(memo[pos]!=-1)
		return memo[pos];
	ll ans=inf;
	for(ll i=pos+1;i<=min(pos+k,n);i++)
		ans=min(ans,solve(i)+abs(arr[i]-arr[pos]));
	memo[pos]=ans;
	return ans;
}
int main()
{
    fastread;
    cin>>n>>k;
    for(ll i=0;i<maxi;i++)
    	memo[i]=-1;
    for(ll i=0;i<n;i++)
    	cin>>arr[i];
    cout<<solve(0)<<endl;
    return 0;
}

Measured memory_bytes: 4992
module mod_modulo_util
  implicit none
  integer(8), parameter :: md = 1000000007_8
  integer(8), allocatable :: f(:), invf(:)
contains
  subroutine init(n)
    implicit none
    integer, intent(in) :: n
    integer :: i
    if (allocated(f)) deallocate(f)
    if (allocated(invf)) deallocate(invf)
    allocate(f(0:n),invf(0:n))
    f = 0_8
    invf = 0_8
    f(0) = 1_8
    do i = 1, n
      f(i) = mod(f(i-1)*int(i,8),md)
    end do
    invf(n) = inv(f(n))
    do i = n, 1, -1
      invf(i-1) = mod(invf(i)*int(i,8),md)
    end do
    return
  end subroutine init
  integer(8) function perm(n,k)
    implicit none
    integer, intent(in) :: n, k
    perm = 0_8
    if (n < 0 .or. k > n) return
    perm = mod(f(n)*invf(n-k),md)
    return
  end function perm
  integer(8) function comb(n,k)
    implicit none
    integer, intent(in) :: n, k
    comb = mod(perm(n,k)*invf(k),md)
    return
  end function comb
  integer(8) function homo(n,k)
    implicit none
    integer, intent(in) :: n, k
    homo = comb(n+k-1,k)
    return
  end function homo
  function inv(n) result(y)
    implicit none
    integer(8), intent(in) :: n
    integer(8) :: a, b, x, y, t, q
    a = mod(n,md)
    b = md
    x = 0_8
    y = 1_8
    do while (b /= 0_8)
      q = a/b
      t = b
      b = mod(a,b)
      a = t
      t = y
      y = x
      x = t-q*x
    end do
    y = mod(y,md)
    if (y < 0_8) y = y+md
    return
  end function inv
  function pow(a,b) result(r)
    implicit none
    integer(8), intent(in) :: a
    integer, intent(in) :: b
    integer :: i
    integer(8) :: r, p
    r = 1_8
    p = a
    do i = 0, 32
      if (btest(b,i)) r = mod(r*p,md)
      p = mod(p*p,md)
    end do
    return
  end function pow
  integer(8) function fact(n)
    implicit none
    integer, intent(in) :: n
    fact = 0_8
    if (n < 0) return
    fact = f(n)
    return
  end function fact
end module mod_modulo_util
program painting_machines
  use mod_modulo_util
  implicit none
  integer :: n, k
  integer(8) :: ans = 0_8
  read(*,*) n
  call init(n)
  ans = mod(mod(f(n)*f(n),md)*invf(n),md)
  do k = (n+1)/2, n-1
    ans = mod(ans+md-mod(mod(f(k-1)*f(k),md)*invf(2*k-n),md),md)
  end do
  write(*,'(i0)') ans
  stop
end program painting_machines

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
const ll INF = 2e18;
const int inf = 1e9+10;
const int maxN = 2e5 + 10;
const int maxD = 15;
const int maxH = 100; 
const int MOD = 998244353;


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

Measured memory_bytes: 3912
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>    // bitset
#include <cctype>    // isupper, islower, isdigit, toupper, tolower
#include <cmath>     // pow
#include <cstdint>   // int64_t, int*_t
#include <cstdio>    // printf
#include <deque>     // deque
#include <iomanip>   // setprecision
#include <iostream>  // cout, endl, cin
#include <map>       // map
#include <queue>     // queue, priority_queue
#include <set>       // set
#include <stack>     // stack
#include <string>    // string, to_string, stoi
#include <tuple>     // tuple, make_tuple
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <utility>       // pair, make_pair
#include <vector>        // vector
using namespace std;

// long long gcd(long long a, long long b) { return b != 0 ? gcd(b, a % b) : a;
// }

// int binary_search(int key) {
//     int ng = -1;
//     int ok = (int)a.size();
//     while(abs(ok - ng) > 1) {
//         int mid = (ok + ng) / 2;
//         if(isOK(mid, key))
//             ok = mid;
//         else
//             ng = mid;
//     }
//     return ok;
// }

// cout << fixed << setprecision(10);
// vector<vector<int>> vec(H, vector<int>(W))    // int H*W
// int MOD = 1000000007;

int main() {
    string s;
    cin >> s;
    int ans = 0;
    int L = s.length();
    for(int i = 0; i<L/2; i++){
        if(i==L-i-1) break;
        if(s[i] != s[L-i-1]) ans++;
    }
    cout << ans << endl;
}

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

int main(){
    char c;
    cin >> c;

    char memo[300];
    memo['A'] = 'T';
    memo['C'] = 'G';
    memo['G'] = 'C';
    memo['T'] = 'A';

    cout << memo[c] << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    string S;
    cin >> N >> S;
    int cnt = 0,p = 0,m = 0;
    for(auto c:S){
        if(c == '(')cnt++;
        else cnt--;
        if(cnt < 0){
            m++;
            cnt = 0;
        }
    }
    p = cnt;
    cout << string(m, '(') << S << string(p, ')') << endl;
}

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

int main(){
    stack<int> S1;
    stack<pair<int, int> > S2;
    char ch;
    int sum=0;
    for(int i=0;cin>>ch;i++){
        if(ch=='\\') S1.push(i);
        else if(ch=='/' && S1.size()>0){
            int j=S1.top(); S1.pop();
            sum+=i-j;
            int a=i-j;
            while(S2.size()>0 && S2.top().first>j){
                a+=S2.top().second; S2.pop();
            }
            S2.push(make_pair(j, a));
        }
    }

    vector<int> ans;
    while(S2.size()>0){ans.push_back(S2.top().second); S2.pop();}
    reverse(ans.begin(), ans.end());
    cout<<sum<<endl;
    cout<<ans.size();
    rep(i, ans.size()){
        cout<<" ";
        cout<<ans[i];
    }
    cout<<endl;

    return 0;
}


Measured memory_bytes: 3236
# Aizu Problem 00136: Frequency Distribution of Height
#
import sys, math, os, copy

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input2.txt", "rt")


limits = {1: [0, 165], 2: [165, 170], 3: [170, 175], 4: [175, 180],
          5: [180, 185], 6: [185, 9999999]}

dist = {k: 0 for k in range(1, 7)}
N = int(input())
for _ in range(N):
    h = float(input())
    for k in range(1, 7):
        if h < limits[k][1]:
            dist[k] += 1
            break
for k in range(1, 7):
    print("%d:%s" % (k, '*' * dist[k]))

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

typedef long long ll;
typedef pair<ll, ll> P;

const ll MOD = 1e9 + 7;
const ll inf = 1LL<<60;
const double eps = 1e-9;

const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
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; }

int main()
{
    int A, B, m;
    cin >> A >> B >> m;
    vector <ll> a(A), b(B), x(m), y(m), c(m);
    ll a_min = inf, b_min = inf;

    for (int i = 0; i < A; i++) {
        cin >> a[i];
        chmin(a_min, a[i]);
    }

    for (int i = 0; i < B; i++) {
        cin >> b[i];
        chmin(b_min, b[i]);
    }

    for (int i = 0; i < m; i++) cin >> x[i] >> y[i] >> c[i];

    ll ans = a_min + b_min;

    for (int i = 0; i < m; i++) {
        chmin(ans, a[x[i]-1] + b[y[i]-1] - c[i]);
    }

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 4224
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>
#include <set>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> void printvec(const vector<T>& v) {
  for (auto x : v) { cout << x << " "; }
  cout << endl;
}
template<class T> void printtree(const vector< vector<T> >& tree) {
  for (long long i = 0; i < tree.size(); ++i) {
    cout << i + 1 << ": "; printvec(tree[i]);
  }
}
template<class T, class U> void printmap(const map<T, U>& mp) {
  for (auto x : mp) { cout << x.first << "=>" << x.second << endl; }
}

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

#define rep(i, n) for(ll i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()
#define fr first
#define sc second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

int main(int argc, char** argv) {
  cin.tie(NULL);
  cout.tie(NULL);
  ios_base::sync_with_stdio(false);
  //cout << setprecision(10) << fixed;

  ll k;
  cin >> k;
  if (k <= 9) {
    cout << k << endl;
    return 0;
  }

  ll ans = 10;
  rep(i, k-10) {
    // compare 2 digit.
    vector<ll> ds;
    ll now = ans;
    while (now > 0) {
      ds.push_back(now % 10);
      now /= 10;
    }
    // cout << "ds: "; printvec(ds);

    // Here, ds has the digis in reverse order
    bool updated = false;
    rep(i, ds.size()-1) {
      ll lastD = ds[i];
      ll preD = ds[i+1];
      if (preD == 9) { // consider 9 case
        if (lastD == 8) {
          ++ds[i]; // update lastD
          updated = true;
        }
      } else if (preD + 1 > lastD) {
        ++ds[i]; // update lastD
        ll cur = ds[i]-1;
        updated = true;
      }
      if (updated) {
        ll cur = ds[i]-1;
        for (int j = i-1; j >= 0; --j) {
          ds[j] = max(cur, 0ll);
          --cur;
        }
        break; // break repeat
      }
      // Here, continue
    }
    if (!updated) { // ds is decreasing order
      ll n = ds.size();
      ll lastD = ds[n-1]; // most significant digit
      if (lastD < 9) {
        ds[n-1] = lastD + 1;
        ll cur = lastD;
        for (int j = n-2; j >= 0; --j) {
          ds[j] = max(cur, 0ll);
          --cur;
        }
      } else { // 9
        // create 10...0
        ds = vector<ll>(n+1);
        ds[n] = 1;
      }
    }
    reverse(all(ds));

    // Here, we convert vector to number
    ll nex = 0;
    for (int digit : ds) {
      nex *= 10;
      nex += digit;
    }
    ans = nex;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 

typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;


int main(int argc, char* argv[])
{
    int n,m;
    scanf("%d%d", &n, &m);

    vector<pair<int,int> > z;
    int i;
    for(i=0; i<n; i++) {
        int a;
        scanf("%d", &a);
        z.push_back(make_pair(a,1));
    }
    for(i=0; i<m; i++) {
        int b,c;
        scanf("%d%d", &b, &c);
        z.push_back(make_pair(c,b));
    }
    sort(z.rbegin(),z.rend());

    ll  sum=0;
    int cnt=0;
    for(i=0; i<n; i++) {
        int num=z[i].second;
        if(cnt+num>n) {
            sum+=((ll)z[i].first * (n-cnt));
            break;
        }
        else {
            sum+=((ll)z[i].first * z[i].second);
            cnt+=z[i].second;
        }
    }
    printf("%lld\n", sum);

    return 0;
}



Measured memory_bytes: 2420
object Main extends App {
	val pw = new java.io.PrintWriter(System.out)

	@scala.annotation.tailrec
	def loop(start: Int, end: Int)(f: Int => Unit): Unit =
		if (start < end) {
			f(start)
			loop(start + 1, end)(f)
		}

	val n, m = Scanner.nextInt
	val a = Array.fill(n)(-1)

	var flag = true

	loop(0, m) { _ =>
		val s, c = Scanner.nextInt
		if (a(s-1) != -1 && a(s-1) != c) flag = false
		else a(s-1) = c
	}

	if (n >= 2 && a(0) == -1) a(0) = 1
	val r = a.map(e => if (e == -1) "0" else s"$e").mkString.toInt.toString

	pw.println( if (flag && r.size == n) r.toInt else -1 )
	pw.flush()
}

object Scanner {
	private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0

	@inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
	@inline private def hasNextByte(): Boolean = if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else true
	@inline private def hasNext(): Boolean = {
		while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
		hasNextByte()
	}
	@inline private def readByte(): Byte = if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else -1

	def next(): String = {
		if(!hasNext()) ???
		val sb = new StringBuilder; var b = readByte()
		while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
		sb.toString
	}

	def nextInt(): Int = {
		val n = nextLong()
		if (n < Int.MinValue || Int.MaxValue < n) ???
		n.toInt
	}

	def nextLong(): Long = {
		if(!hasNext()) ???
		var minus = false; var b = readByte()
		if (b == '-') { minus = true; b = readByte() }

		@scala.annotation.tailrec
		def go (b: Byte, n: Long = 0): Long = if ('0' <= b && b <= '9') go(readByte(), n * 10 + b - '0') else if (minus) -n else n

		go(b)
	}

	def nextDouble(): Double = next().toDouble
}


Measured memory_bytes: 25660
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
using pli=pair<int64_t, int>;
using mii=map<int, int>;

int main() {
    int r;
    cin >> r;
    cout << r * r << endl;
    return 0;
}


Measured memory_bytes: 888
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

//		int N_year;
//		N_year = scan.nextInt();
//
//		if (N_year == 1) {
//			System.out.println("Hello world");
//
//		} else {
//			int A, B;
//
//			A = scan.nextInt();
//			B = scan.nextInt();
//
//			System.out.println((A + B));
//
//		}
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		if(N == 1) {
			System.out.println("Hello World");
		}
		else {
			int A = sc.nextInt(), B = sc.nextInt();
			System.out.println(A + B);
		}

	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 23124
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

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



int main(){
    int n,k,q;
    cin >> n >> k >> q;
    vector<int> a(q);
    rep(i,q) cin >> a[i];
    
    vector<int> score(n, k-q);
    rep(i,q){
        score[a[i]-1]++;
    }
    
    rep(i,n){
        if(score[i] > 0){
            cout << "Yes" << endl;
            
        }
        else{
            cout << "No" << endl;
        }
    }
}


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

using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;

#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define rrep(i,a) for(ll i=a-1;i>=0;i--)
#define MOD 1000000007

//debug
#define debug(arr) cerr<<#arr<<"(l"<<__LINE__<<") : ";for(auto x:arr)cerr<<x<<" ";cerr<<endl;

int main(){
  ll N;
  cin >> N;
  vector<string> slist;
  rep(i, N){
    string s;
    cin >> s;
    slist.push_back(s);
  }
  sort(slist.begin(), slist.end());

  vector<pair<ll,string>> count;
  string prev = "";
  for(auto s : slist){
    if(prev == s) count.back().first++;
    else count.emplace_back(1, s);
    prev = s;
  }
  sort(count.begin(), count.end());
  ll maxcnt = count.back().first;

  for(auto e: count){
    if(e.first == maxcnt) cout << e.second << endl;
    // cout << e.first << " " << e.second << endl;
  }
  return 0;
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

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

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    VI A(3); REP(i,3) cin >> A[i];
    SORT(A);
    int ans = A[2]-A[1] + (A[2]-(A[0]+A[2]-A[1])+1)/2 +(A[2]-(A[0]+A[2]-A[1]))%2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;


int N;
vector<vector<int>> F;
vector<vector<int>> P;

int ans = -1000000001;

void check(vector<int> A){
    
    int an = 0;
    rep(i,N){
        int nn = 0;
        rep(j,10) if(A[j]*F[i][j] != 0) nn++;
        an += P[i][nn];
    }
    ans = max(ans, an);
    
}


void dfs(vector<int> A, int i){
    int n = i;
    if(i == 10){
        int c = 0;
        rep(k,10) c += A[k];
        if(c != 0) check(A);
    }else{
        dfs(A, n+1);
        A[n] = 1;
        dfs(A, n+1);
    }
}



int main()
{
    cin >> N;
    F.assign(N, vector<int>(10, 1));
    P.assign(N, vector<int>(11, 1));
    rep(i,N) rep(j,10) cin >> F[i][j];
    rep(i,N) rep(j,11) cin >> P[i][j];
    
    vector<int> A(10, 0);
    dfs(A, 0);
    
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int h,w; cin>>h>>w;
    vector <vector<char>> map( h,vector <char>(w ));
    vector <vector<int>> data(h ,vector <int>(w ));
    vector <vector<int>> data2(h ,vector <int>(w ));
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>map[i][j];
            //cout<<map[i][j];
        }
        //cout<<endl;
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(map[i][j]=='.') {if(j-1>=0) data[i][j]= 1+ data[i][j-1]; else data[i][j]= 1;}
        }
    }
    for(int i=0;i<h;i++){
        for(int j=w-1;j>=0;j--){
            if(map[i][j]=='.')  if(j+1!=w&&map[i][j+1]!='#' ) data[i][j]= data[i][j+1]; 
        }
    }
    for(int i=0;i<w;i++){
        for(int j=0;j<h;j++){
            if(map[j][i]=='.') {if(j-1>=0) data2[j][i]= 1+ data2[j-1][i]; else data2[j][i]= 1;}
        }
    }
    for(int i=0;i<w;i++){
        for(int j=h-1;j>=0;j--){
            if(map[j][i]=='.')  if(j+1!=h&&map[j+1][i]!='#' ) data2[j][i]= data2[j+1][i]; 
        }
    }
    /*for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout<<data[i][j];
        }
        cout<<endl;
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cout<<data2[i][j];
        }
        cout<<endl;
    }*/
    int ans = 0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            ans= max(ans, data2[i][j]+data[i][j]-1);
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 35712
local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end
local function array(dimension, default_val) local n=dimension local m={}if default_val~=nil then m[1]={__index=function()return default_val end}end for i=2,n do m[i]={__index=function(p, k)local c=setmetatable({},m[i-1])rawset(p,k,c)return c end}end return setmetatable({},m[n])end
----
local A, B = read.nn()
for i=1,10000 do
    local pa, pb = i * 8 // 100, i * 10 // 100
    if pa == A and pb == B then
        print(i)
        return
    end
end
print(-1)


Measured memory_bytes: 760
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String[] line = scanner.nextLine().split(" ");

        int k = Integer.parseInt(line[0]);
        int s = Integer.parseInt(line[1]);

        int count = 0;
        for (int x = 0; x <= k; x++) {
            for (int y = 0; y <= k; y++) {
                int z = s - x - y;
                if (0 <= z && z <= k) count++;
            }
        }

        System.out.println(count);
    }

}



Measured memory_bytes: 21844
package main

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

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	ss := make([]string, 3)
	for i := range ss {
		ss[i] = next()
	}
	fmt.Printf("A%sC\n", string(ss[1][0]))
}


Measured memory_bytes: 640
from itertools import product
al=list(product([0,1],repeat=10))
n=int(input())
a=[list(map(int, input().split())) for i in range(n)]
p=[list(map(int, input().split())) for i in range(n)]
ans=-100000000000
for i in al:
    if sum(i)==0:continue
    q=0
    for j in range(n):
        count=0
        for k in range(10):
            if a[j][k]==1 and i[k]==1:
                count+=1
        q+=p[j][count]
    ans=max(ans,q)
print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <vector>
#include <bitset>
#include <cmath>
#include <utility>
#define Maxn 100005
#define Maxm 1000005
#define lowbit(x) x&(-x)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define PI acos(-1.0)
#define LL long long 
#define Inf (1LL<<62)
#define inf 0x3f3f3f3f
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
using namespace std;
int main()
{
	stack<int> s;
	int n,l,r;
	string str,str1,str2;
	bool ok[105];
	//input;output;
	while(cin>>n)
	{
		while(!s.empty())
			s.pop();
		str1.clear();
		str2.clear();
		l=r=0;
		memset(ok,false,sizeof(ok));
		cin>>str;
		for(int i=0;i<n;i++)
			if(str[i]=='(')
				s.push(i);
			else if(!s.empty())
			{
				int x=s.top();
				s.pop();
				ok[x]=ok[i]=true;
			}
		for(int i=0;i<n;i++)
			if(!ok[i])
				str[i]=='('?l++:r++;
		while(l--)
			str1+=")";
		while(r--)
			str2+="(";
		cout<<str2+str+str1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int digitSum(string S) {
    int ret = 0;
    for (char c : S) ret += c - '0';
    return ret;
}
int main() {
    string S;
    cin >> S;
    int a = S[0] - '0', n = S.size() - 1;
    if (n == 0) cout << S[0] << endl;
    else if (all_of(S.begin() + 1, S.end(), [](char c) { return c == '9'; })) cout << digitSum(S) << endl;
    else cout << a - 1 + 9 * n << endl;
}


Measured memory_bytes: 256
n = int(input())
adj = [[] for _ in range(n)]  # adjacence(隣接)の略

for (a,b,c) in (map(int, input().split()) for _ in range(n-1)):
    adj[a-1].append((b-1, c))
    adj[b-1].append((a-1, c))

q, k = map(int, input().split())
k -= 1
dist = [-1]*n  # 経由地から各頂点までのコスト
dist[k] = 0  # 経由地kをスタート地点とするため、コスト0に設定

stack = [k]  # 探索候補。経由地kをスタート地点にするため、先に積んでおく

while stack: # 探索候補がなくなるまで続ける
    now = stack.pop()
    for dest, cost in adj[now]:
        if dist[dest] != -1: # dest(目的地)までのコストがすでに設定されていればスルー
            continue
        dist[dest] = dist[now] + cost # コストを現地点までのコストと合算して算出
        stack.append(dest)

for _ in range(q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])

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

int main(void)
{
	int n, k, x, y;
	ll sum = 0;
	cin >> n >> k >> x >> y;

	if(n > k){
		for(int i = 0; i < k; i++)
			sum += x;
		for(int i = 0; i < n - k; i++)
			sum += y;
	}
	else{
		for(int i = 0; i < n; i++)
			sum += x;
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 256
from collections import deque

def bfs():
    d = [[float("INF")] * w for i in range(h)]
    d[0][0] = 0
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    que = deque([])
    que.append((0, 0))
    
    while que:
        p = que.popleft()
        if p[0] == h - 1 and p[1] == w - 1:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("INF"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    
    return d[h - 1][w - 1]
    
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
cnt = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
            cnt += 1
if bfs() == float("INF"):
    print("-1")
else:
    print(h * w - cnt - bfs() - 1) 


Measured memory_bytes: 3444
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define mod 1000000007
unordered_map<ll,vector<ll>> adj;
vector<ll> vis(300005,0);
vector<ll> p(100005,0);
ll c[100005];
ll cnt;
void dfs(ll node)
{
  if(vis[node])
    return;
  vis[node]=1;
  cnt++;
  for(auto i:adj[node])
    {
      dfs(i);
    }
}
int main()
{
    ll n,m;
    cin>>n>>m;
    ll a,b;
    map<pair<ll,ll>,ll> temp;
    while(m--)
    {
      cin>>a>>b;
      if(!temp[mp(a,b)])
      {
        adj[a].pb(b);
        adj[b].pb(a);
        temp[mp(a,b)]=1;
        temp[mp(b,a)]=1;
      }
    }
    ll i;
    ll mx=0;
    for(i=1;i<=n;i++)
    {
        cnt=0;
        if(!vis[i])
        {
          //cout<<i<<endl;
           dfs(i);
        }
        mx=max(cnt,mx);
    }
    cout<<mx;
}


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N, LIM; scanf("%d %d", &N, &LIM);
  vector<int> W(N), V(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d %d", &W[i], &V[i]);
  }

  vector<vector<int>> dp(N + 5, vector<int>(305, 0));

  for (int i = 0; i < N; ++i) {
    int diff = W[i] - W[0];
    for (int j = 300; j >= 0; --j) {
      if (j - diff < 0) { continue; }
      for (int p = i + 1; p >= 1; --p) {
        dp[p][j] = max(dp[p][j], dp[p - 1][j - diff] + V[i]);
      }
    }
  }

  int ans = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= 300; ++j) {
      if (1LL* i * W[0] + j <= LIM) {
        ans = max(ans, dp[i][j]);
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

int gcd(int a, int b) {
    if (b == 0)return a;
    return gcd(b, a % b);
}

class gcd_seg {
    VI dat;
    int n = 1;
public:
    gcd_seg(int _n){
        while (n < _n)n *= 2;
        dat.resize(2 * n - 1 , 0);
    }

    void update(int i, int x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            --i /= 2;
            dat[i] = gcd(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }

    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l)return 0;
        else if (a <= l && r <= b)return dat[k];
        else {
            int s = query(a, b, k * 2 + 1, l, (l + r) / 2);
            int t = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return gcd(s, t);
        }
    }
    int query(int a, int b) { return query(a, b, 0, 0, n); }
};

int main() {
    init();

    int n;
    cin >> n;
    gcd_seg seg(n);
    int in;
    FOR(i, 0, n) {
        cin >> in;
        seg.update(i, in);
    }

    int ans = 1;
    FOR(i, 0, n) {
        int a = (i > 0 ? seg.query(0, i) : 0);
        int b = (i < n - 1 ? seg.query(i + 1, n) : 0);
        chmax(ans, gcd(a, b));
    }
    cout << ans << "\n";
}

Measured memory_bytes: 1280