akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 100005;
const int M = 1000000007;

int n;
char s[N];

int main() {
  while (~scanf("%s", s)) {
    n = strlen(s);
    ll ans = 0;
    for (int i = 0; i < 1 << (n - 1); i++) {
      ll num = s[0] - '0';
      for (int j = 0; j < n - 1; j++) {
        if (i & (1 << j)) { ans += num; num = 0; }
        num = num * 10 + s[j + 1] - '0';
      }
      ans += num;
    }
    printf("%lld\n", ans);
  }
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int n = stdIn.nextInt();
		int m = stdIn.nextInt();
		
		boolean[] flag = new boolean[m];
		Arrays.fill(flag,true);
		
		for(int i = 0; i < n ; i++) {
			int k = stdIn.nextInt();
			int[]check = new int[k];
			for(int j = 0; j < k; j++) {
				check[j] = stdIn.nextInt();
				
				
				
			}
			
			
			for(int j = 0; j < m; j++) {
				boolean flag2 = false;
				for(int p = 0; p < k; p++) {
					if((j+1)==check[p]) {
						flag2 = true;
					}
				}
				if(!flag2) {
					flag[j] = false;
				}
				
				
				
			}
			
			
		}
		
		long cnt = 0;
		for(int i = 0; i < m; i++) {
			if(flag[i] == true) {
				cnt++;
			}
		}
		System.out.println(cnt);
		
	}

}


Measured memory_bytes: 23764
#include<stdio.h>
int main()
{
    int N, c;
    scanf("%d", &N);
    c=N%10;
    if(c==2||c==4||c==5||c==7||c==9)
    {
        printf("hon\n");
    }
    if(c==0||c==1||c==6||c==8)
    {
        printf("pon\n");
    }
    if(c==3)
    {
        printf("bon\n");
    }

    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

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

int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    priority_queue<ll> pq;
    int x,y,a,b,c;
    cin >> x >> y >> a >> b >> c;
    vector<ll> p(a),q(b),r(c);
    rep(i,a)cin >> p[i];
    rep(i,b)cin >> q[i];
    rep(i,c){
        cin >> r[i];
        pq.push(r[i]);
    }
    sort(ALL(p),greater<>());
    sort(ALL(q),greater<>());
    sort(ALL(r),greater<>());
    // p からx個選ぶ
    // q からy個選ぶ
    ll ans = 0;
    for(int i=0;i<x;i++)pq.push(p[i]);
    rep(i,y)pq.push(q[i]);
    for(int i=0;i<x+y;i++){
        ans += pq.top();pq.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 7664
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int height[100003];

int dp[100003];

int JumpFrog(int N){
    dp[1]=0;
    dp[2]=abs(height[2]-height[1]);
    for(int i=3;i<=N;i++){
        dp[i]=min(dp[i-1]+abs(height[i]-height[i-1]),dp[i-2]+abs(height[i]-height[i-2]));
    }
    return dp[N];
}

int main()
{
    int N;
    while(cin>>N){
        for(int i=1;i<=N;i++){
            cin>>height[i];
        }
        cout<<JumpFrog(N)<<endl;
    }

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N,a,d,M,K,x[200000],y[200000],z[200000];
int main(){
	cin>>N>>a>>d>>M;
	rep(i,M) cin>>x[i]>>y[i]>>z[i],y[i]--,z[i]--;
	cin>>K;
	K--;
	for(int i=M-1;i>=0;i--){
		if(x[i]==0){
			if(y[i]<=K&&K<=z[i]){
				K=y[i]+z[i]-K;
			}
		}
	}
	int v=a+d*K;
	rep(i,M){
		if(x[i]==0){
			if(y[i]<=K&&K<=z[i]){
				K=y[i]+z[i]-K;
			}
		}
		if(x[i]==1){
			if(y[i]<=K&&K<=z[i]){
				v++;
			}
		}
		if(x[i]==2){
			if(y[i]<=K&&K<=z[i]){
				v/=2;
			}
		}
	}
	cout<<v<<endl;
}

Measured memory_bytes: 5244
#include <bits/stdc++.h>
using namespace std;
 
 
int main()
{
 
    int64_t n;
    cin>>n;

    int64_t cnt4=0;
    int64_t cnt2=0;
    for(int i=0;i<n;i++){
        int64_t a;
        cin>>a;

        if(a%4==0)
            cnt4++;

        if(a%4!=0&&a%2==0)
            cnt2++;
    }

    if(n%2==0&&cnt4+cnt2/2>=n/2)
        cout<<"Yes"<<endl;
    else if(n%2==1&&cnt4+cnt2/2>=(n-1)/2)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
 
    return 0;
}   

Measured memory_bytes: 256
import math


def inlt():
    return(list(map(int, input().split())))


a, b, h, m = inlt()

theta = abs(.5 * (60 * h + m) - 6*m)
if theta > 180:
    theta = 360 - theta

# print(theta)

res = math.sqrt(a**2 + b**2 - 2*a*b*math.cos(math.radians(theta)))
print(res)


Measured memory_bytes: 9504
#include <iostream>
#include <map>
using namespace std;
int main(void){
    int n,m,c=0;
    map<int,int> p;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            p[a]++;
        }
    }
    for(auto x=p.begin();x!=p.end();x++){
        if(x->second==n){
            c++;
        }
    }
    cout<<c<<endl;
}


Measured memory_bytes: 256
from math import gcd
k = int(input())
a = 0
b = 0
ans = 0
memo =[[[0 for _1 in range(k+1)] for _ in range(k + 1)] for _2 in range(k + 1)]
for i in range(1, k + 1):
    for j in range(1, k + 1):
        a = gcd(i,j)
        for k in range(1, k + 1):
            ans += gcd(a,k)

print(ans)


Measured memory_bytes: 75416
<?php

    // AtCoder Beginner Contest 165
    // A - We Love Golf

    $k = in_int();
    list($a, $b) = in_ints();

    for ($i = $a; $i <= $b; $i++) {
        if ($i % $k == 0) {
            out('OK');
            break;
        }
    }
    if ($i > $b) {
        out('NG');
    }


    // -----------------------------------------------------
    function in() { return trim(fgets(STDIN)); }
    function in_int() { return (int)in(); }
    function in_vals() { return explode(' ', in()); }
    function in_ints() { return array_map('intval', in_vals()); }
    function out($s) { echo $s . PHP_EOL; }
    function yes() { out('Yes'); }
    function no() { out('No'); }


Measured memory_bytes: 16104
import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
from functools import lru_cache

INF = 1 << 60

# ここから書き始める
s = input()
q = int(input())
cnt = 0
left = []
right = []
for i in range(q):
    query = input().split()
    if len(query) == 1:
        cnt += 1
    else:
        f = query[1]
        c = query[2]
        if cnt % 2 == 0:
            if f == "1":
                # s = c + s
                left.append(c)
            else:
                # s += c
                right.append(c)
        else:
            if f == "1":
                # s += c
                right.append(c)
            else:
                # s = query[2] + s
                left.append(c)

left = left[::-1]
right = "".join(right)
left = "".join(left)
ans = "".join([left, s, right])
# print(right, s, left)
if cnt % 2 != 0:
    ans = ans[::-1]

print(ans)


Measured memory_bytes: 8420
#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

// aのp乗を求める関数
ll mpow(ll a, ll b){
	if(b==0){
		return 1;
	}else if(b%2==0){
		ll memo = mpow(a,b/2);
		return memo*memo%MOD;
	}else{
		return mpow(a,b-1)*a%MOD;
	}
}

signed main(){
	ll n,k; cin>>n>>k;
	ll cnt[k+1]; reps(i,k)cnt[i]=-1;
	REPS(i,k){
		cnt[i]=mpow(k/i,n);
		ll now=2;
		while(now*i<=k){
			cnt[i]-=cnt[now*i];
			cnt[i]+=MOD; cnt[i]%=MOD;
			now++;
		}
		// cerr<<i SP cnt[i]<<endl;
	}
	ll ans=0LL;
	reps(i,k)if(cnt[k]>0)ans+=(cnt[i]*i)%MOD;
	cout<<ans%MOD<<endl;


	return 0;
}


Measured memory_bytes: 4412
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
using namespace std;

const int N = 303;
int dist[N][N];

int main(){
	int n, m, l;
	scanf("%d %d %d", &n, &m, &l);
	memset(dist, oo, sizeof dist);
	for (int i=0; i<m; i++){
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		dist[u][v] = c;
		dist[v][u] = c;
	}
	for (int k=1; k<=n; k++){
		for (int i=1; i<=n; i++){
			for (int j=1; j<=n; j++){
				if(i != j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	for (int i=1; i<=n; i++){
		for (int j=1; j<=n; j++){
			if(i != j) {
				if(dist[i][j] <= l) dist[i][j] = 1;
				else dist[i][j] = oo;
			}
		}
	}
	
	for (int k=1; k<=n; k++){
		for (int i=1; i<=n; i++){
			for (int j=1; j<=n; j++){
				if(dist[i][k] == -1 || dist[k][j] == -1) continue ;
				if(i != j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	int q;
	scanf("%d", &q);
	while (q-- > 0){
		int u, v;
		scanf("%d %d", &u, &v);
		printf("%d\n", ((dist[u][v] != oo) ? dist[u][v]-1 : -1));
	}
}


Measured memory_bytes: 896
#include<iostream>
#include<vector>
#include <unordered_map>  
#include <algorithm>
#include <functional>
#include <map>
#include <string>
#include <sstream>
#include <cmath>
using namespace std;

int main() {
	string s;
	cin >> s;
	s[3] = '8';
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
bool is_prm(int n) {
    int bggst = sqrt(n) + 1;
    if(bggst >= n) bggst = n - 1;
    if(n == 1 || n == 0) return 0;
    if(n == 2) return 1;
    for(int i = 2; i <= bggst; ++i) {
        if(n % i == 0) return 0;
    }
    return 1;
}
int main() {
    int n, i;
    scanf("%d", &n);
    for(i = n; is_prm(i) == 0; ++i);
    printf("%d", i);
    return 0;
}

Measured memory_bytes: 128
from collections import Counter
import sys
input = sys.stdin.readline

mod = 10**9+7
n = int(input())
a = list(map(int, input().split()))

fact = [1] * (n+2)
fact_inv = [1] * (n+2)
for i in range(1, n+2):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = pow(fact[i], mod-2, mod)

def combination(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[k] * fact_inv[n-k] % mod

x = Counter(a).most_common(1)[0][0]
front = a.index(x)
back = a[::-1].index(x)

for k in range(1, n+2):
    ans = (combination(n+1, k) - combination(front + back, k-1)) % mod
    print(ans)



Measured memory_bytes: 65368
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	sc.Split(bufio.ScanWords)
	N := getInt()
	a := make([]int, N)
	b := make([]int, N)
	c := make([]int, N)
	for i := 0; i < N; i++ {
		a[i], b[i], c[i] = getInt(), getInt(), getInt()
	}

	var dp [100000][3]int
	dp[0][0] = a[0]
	dp[0][1] = b[0]
	dp[0][2] = c[0]
	for i := 1; i < N; i++ {
		dp[i][0] = max(dp[i-1][1]+a[i], dp[i-1][2]+a[i])
		dp[i][1] = max(dp[i-1][0]+b[i], dp[i-1][2]+b[i])
		dp[i][2] = max(dp[i-1][0]+c[i], dp[i-1][1]+c[i])
	}

	out(max(dp[N-1][0], max(dp[N-1][1], dp[N-1][2])))

}


Measured memory_bytes: 7168
#include <iostream>
#include <cstdio>
#include <vector>
#include <math.h>

using namespace std;

typedef long long int ll;
typedef long double ld;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define vsort(a) sort(a.begin(), a.end())
#define rev(a) reverse(a.begin(), a.end());

const int MOD = 1000000007;
const int INF = INT_MAX;



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

    int len = s.size();

    for (int i=0; i < len; i++){
        if (s[i] + n <= 'Z'){
            s[i] += n;
        }
        else {
            s[i] = s[i] - (26-n);
        }
    }

    cout << s << endl;

    
    return 0;
}




//              g++ -std=c++1z  

Measured memory_bytes: 632
#include <stdlib.h>
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <map>
     
    using namespace std;
     
     
    int main(void){
        long long x,y;
        cin >> x >> y;
      
      	long long tmp = x;
      	long long count = 1;
      	while(tmp <=y){
          tmp = tmp * 2;
          if(tmp > y){
            break;
          }
          count++;
        }
      cout << count << endl;
      return 0;
    }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int num[N],a[N];
int main(){
	int n;scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",a+i),num[a[i]]++;
	long long ans=0;
	for(int i=1;i<=n;i++)ans+=1ll*num[i]*(num[i]-1)/2;
	for(int i=0;i<n;i++)printf("%lld\n",ans-num[a[i]]+1);
	return 0;
}

Measured memory_bytes: 3712
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)

h,w=map(int,input().split())
maze = [[]for _ in range(h)]
for i in range(h):
    maze[i].extend(list(input()))

R=[[0 for i in range(w)]for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
B=[[0 for i in range(w)]for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        if j==0: L[i][j]=1
        else: L[i][j]=L[i][j-1]+1
        if i==0: U[i][j]=1
        else: U[i][j]=U[i-1][j]+1

for i in range(h):
    for j in range(w):
        if maze[h-1-i][w-1-j]=="#":continue
        if i==0:B[h-1-i][w-1-j]=1
        else: B[h-1-i][w-1-j] = B[h-i][w-1-j]+1
        if j==0:R[h-1-i][w-1-j]=1
        else: R[h-1-i][w-1-j] = R[h-1-i][w-j]+1


#print(*B,sep="\n")
#print("\n")
#print(*U,sep="\n")


ma=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=="#":continue
        ma=max(ma,R[i][j]+L[i][j]+U[i][j]+B[i][j]-3)

print(ma)


Measured memory_bytes: 312200
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;

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

int main() {

    ll N;
    cin >> N;
    ll A[N];
    ll sum = 0;
    rep(i,N){
        cin >> A[i];
        sum += A[i];
    }
    ll out[N];
    out[0] = 0;
    ll tmp = 0;
    ll out_sum = 0;
    while(tmp!=N-2){
        if(tmp==N-1){
            out[1] = out[N-1] + 2*(A[0]-A[N-1]);
            out_sum += out[1];
            tmp = 1;
        }else{
            out[tmp+2] = out[tmp] + 2*(A[tmp+1]-A[tmp]);
            out_sum += out[tmp+2];
            tmp += 2;
        }
    }
    rep(i,N){
        cout << out[i]+(sum-out_sum)/N;
        if(i==N-1) cout << endl;
        else cout << " ";
    }
    return 0;
}


Measured memory_bytes: 5104
#include <iostream>
#include <string>

using namespace std;

int main(void){
    int p=0;
    int q=0;
    int r=0;
    int num1=0;
    int num2=0;
    int num3=0;
    int min=0;

    cin >> p >> q >> r;

    num1=p+q;
    num2=q+r;
    num3=r+p;

    min=num1;

    if(min>=num2)min=num2;
    if(min>=num3)min=num3;

    cout << min << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define si(c) ((int)(c).size())
#define forsn(i,s,n) for(int i = (int)(s); i<((int)n); i++)
#define dforsn(i,s,n) for(int i = (int)(n)-1; i>=((int)s); i--)
#define all(c) (c).begin(), (c).end()
#define D(a) cerr << #a << "=" << (a) << endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair
 
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
 
const int MOD = 1e9 + 7;
const int HALF = MOD/2 + 1;
const int N = 2e5 + 10;
 
int n;
vi adj[N];

int merge(vector<pii> &a, vector<pii> &b) {
    if (si(a) < si(b)) swap(a,b);

    int n = si(a), m = si(b);
    forn(i,si(b)) {
        int t = m-1-i, q = n-1-i;
        a[q].second = ((ll)a[q].first * b[t].second % MOD) + ((ll)a[q].second * b[t].first % MOD);
        if (a[q].second >= MOD) a[q].second -= MOD;
        a[q].first = (ll)a[q].first*b[t].first%MOD;
    }
    return si(b);
}
 
vector<pii> dp[N];
void dfs(int u, int p) {
    dp[u].eb(HALF,HALF);

    int fix = 0;
    for (int v : adj[u]) if (v != p) {
        dfs(v,u);
        dp[v].eb(1,0);
        fix = max(fix, merge(dp[u], dp[v]));
    }
    forn(i,fix) {
        int t = si(dp[u])-1-i;
        dp[u][t].first = 1 - dp[u][t].second;
        if (dp[u][t].first < 0) dp[u][t].first += MOD;
    }
 
}
 
#include <sys/resource.h>
void expandStack() {
	struct rlimit rl;
	getrlimit(RLIMIT_STACK, &rl);
	rl.rlim_cur = rl.rlim_max;
	setrlimit(RLIMIT_STACK, &rl);
}

int main() {
    expandStack();
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> n;
    forn(i,n) {
        int p; cin >> p;
        adj[p].pb(i+1);
    }
    n++;
    dfs(0,0);
 
    int ans = 0;
    for (auto xy : dp[0]) {
        ans += xy.second;
        if (ans >= MOD) ans -= MOD;
    }
    forn(_,n) ans = 2*ans%MOD;
    cout << ans << endl;
 
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()

using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;

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

  string num = to_string(s.size() - 2);

  cout << s[0] + num + s[s.size() - 1] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n;
  cin >> n;
  int ans = 800*n;
  ans -= n/15 * 200;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3620
#include <stdio.h>

#define MAX 25
#define NIL -1

typedef struct Node_
{
    int parent;
    int left;
    int right;
} Node;

static Node Tree[MAX];
static int Depth[MAX];
static int Height[MAX];

static void setDepth(int i, int depth)
{
    if (i == NIL)
        return;
    Depth[i] = depth;
    setDepth(Tree[i].left, depth + 1);
    setDepth(Tree[i].right, depth + 1);
}

static int setHeight(int i)
{
    int h1 = 0;
    int h2 = 0;

    if (Tree[i].left != NIL)
        h1 = setHeight(Tree[i].left) + 1;
    if (Tree[i].right != NIL)
        h2 = setHeight(Tree[i].right) + 1;

    Height[i] = (h1 > h2) ? h1 : h2;
    return Height[i];
}

static int getSibling(int i)
{
    if (Tree[i].parent == NIL)
        return NIL;

    int left = Tree[Tree[i].parent].left;
    if (left != i && left != NIL)
        return left;

    int right = Tree[Tree[i].parent].right;
    if (right != i && right != NIL)
        return right;

    return NIL;
}

static void printNode(int i)
{
    int degree = 0;
    if (Tree[i].left != NIL)
        degree++;
    if (Tree[i].right != NIL)
        degree++;

    printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, ", i, Tree[i].parent, getSibling(i), degree, Depth[i], Height[i]);

    if (Tree[i].parent == NIL) {
        printf("root\n");
    } else if (Tree[i].left == NIL && Tree[i].right == NIL) {
        printf("leaf\n");
    } else {
        printf("internal node\n");
    }
}

int main()
{
    int n;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        Tree[i].parent = NIL;
    }

    for (int i = 0; i < n; i++) {
        int id, left, right;
        scanf("%d %d %d", &id, &left, &right);
        Tree[id].left = left;
        Tree[id].right = right;
        if (left != NIL) {
            Tree[left].parent = id;
        }
        if (right != NIL) {
            Tree[right].parent = id;
        }
    }

    int root = NIL;

    for (int i = 0; i < n; i++) {
        if (Tree[i].parent == NIL) {
            root = i;
            break;
        }
    }

    if (root >= 0) {
        setDepth(root, 0);
        setHeight(root);
    }

    for (int i = 0; i < n; i++) {
        printNode(i);
    }

    return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,k;
ll x[100005];
ll ans=10000000000000000;
int main(void){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    for(int l=0;l<=n-k;l++){
        int r=l+k-1;
        if(x[r]<=0){
            ans=min(ans,x[l]*(-1));
        }else if(x[l]>=0){
            ans=min(ans,x[r]);
        }else{
            ans=min(ans,x[r]+x[l]*(-2));
            ans=min(ans,x[r]*2+x[l]*(-1));
        }
    }
    cout<<ans<<endl;
    
}


Measured memory_bytes: 1024
package main

import (
    "fmt"
    "math"
)

func main() {
    a := scanInt()
    b := scanInt()
    k := scanInt()
    i := int(math.Min(float64(a), float64(b))) + 1
    for k > 0 {
        i = i - 1
        if (a % i == 0 && b % i == 0) {
            k = k - 1;
        }
    }
    fmt.Println(i)
}

func scanInt() (num int) {
    fmt.Scan(&num)
    return
}
func scanInts(len int) (nums []int) {
    var num int
    for i := 0; i < len; i++ {
        fmt.Scan(&num)
        nums = append(nums, num)
    }
    return
}
func scanString() (str string) {
    fmt.Scan(&str)
    return
}
func scanStrings(len int) (strs []string) {
    var str string
    for i := 0; i < len; i++ {
        fmt.Scan(&str)
        strs = append(strs, str)
    }
    return
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define LL long long int
#define MOD 998244353
#define MAXN 3000

/*
Consider of A with size k whose sum is S:
A_x1, A_x2, ..., A_xk

This subset will contribute 2^(N - k) to the final answer.
The reason is because we have two choices (include or not) for each indices other than x1, x2, .., xk.

Let's define a dp:
dp[i][j] = Sum of 2^(N - k) for all subset of {1, 2, .., i} whose sum is j.

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - A[i]]/2

The first term is obvious, that means we don't include i-th element.
The second term is quite tricky. Imagine dp[i - 1][j - A[i]] as sum of:
2^(N - k1) + 2^(N - k2) + ...

Because we add i-th element, the sum will transform to:
2^(N - (k1 + 1)) + 2^(N - (k2 + 1)) + ...
1/2 * (2^(N - k1) + 2^(N - k2) + ... )
*/

LL fastExponentiation(LL base, int p) {
    LL result = 1;
    while (p > 0) {
        if (p%2 == 1)
            result = (result * base)%MOD;

        base = (base * base)%MOD;
        p /= 2;
    }

    return result;
}

int N, S, A[MAXN + 3];
LL inv2, dp[MAXN + 3][MAXN + 3];

int main() {
    cin >> N >> S;
    for (int i = 1; i <= N; i++)
        cin >> A[i];

    inv2 = fastExponentiation(2, MOD - 2);

    for (int i = 0; i <= N; i++)
        dp[i][0] = fastExponentiation(2, N);

    for (int j = 1; j <= S; j++)
        dp[0][j] = 0;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= S; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= A[i]) {
                dp[i][j] = (dp[i][j] + (dp[i - 1][j - A[i]] * inv2)%MOD)%MOD;
            }
        }
    }

    cout << dp[N][S] << endl;
}


Measured memory_bytes: 73928
#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
typedef long int lint;
typedef vector<char> vchar;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
#define vsort(v) sort((v).begin(), (v).end())
#define vreverse(v) reverse((v).begin(), (v).end())
#define pb(a) push_back(a)
#define INF 1000000007
#define MOD 1e9+7
int main(){
  //input
  int n,i,j;cin>>n;
  vint c(n-1);vint s(n-1);vint f(n-1);
  for(i=0;i<n;i++){
  cin>>c[i]>>s[i]>>f[i];
  }
  vint t(n,0);
  //caricurate
  for(j=0;j<n;j++){//station
    for(i=j;i<n-1;i++){//case
      if(s[i]>=t[j]){t[j]=s[i];}
      else{t[j]=((t[j]/f[i])+((t[j]%f[i])?1:0))*f[i];}
      t[j]+=c[i];
    }
    cout<<t[j]<<endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  char s[13];
  scanf("%s", s);
  for (int i = 0; i < 4; i++) {
    printf("%c", s[i]);
  }
  printf(" ");
  for (int i = 4; i < 12; i++) {
    printf("%c", s[i]);
  }
  printf("\n");

  return 0;
}

Measured memory_bytes: 128
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

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

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn calc_inversion(a: &mut [u32]) -> usize {
    if a.len() == 1 {
        return 0;
    }
    let n = a.len();
    let m = n / 2;
    let mut ans = calc_inversion(&mut a[0..m]);
    ans ^= calc_inversion(&mut a[m..n]);
    let mut i = 0;
    let mut j = m;
    let mut b = vec![];
    while i < m && j < n {
        if a[i] <= a[j] {
            b.push(a[i]);
            i += 1;
        } else {
            ans ^= m - i;
            b.push(a[j]);
            j += 1;
        }
    }
    while i < m {
        b.push(a[i]);
        i += 1;
    }
    for i in 0..b.len() {
        a[i] = b[i];
    }
    ans
}

fn run() {
    input! {
        n: usize,
        k: usize,
        p: [u32; n],
    }
    if k < n {
        if k % 2 == 0 {
            println!("Yes");
            return;
        }
        let mut a = p.clone();
        if calc_inversion(&mut a) % 2 != 0 {
            println!("No");
        } else {
            println!("Yes");
        }
        return;
    }
    let mut a = vec![0; 2 * n];
    for i in 0..n {
        a[i] = p[i];
        a[i + n] = p[i];
    }
    let mut cnt = vec![0; 2 * n + 1];
    for i in 0..(2 * n - 1) {
        if a[i] > a[i + 1] {
            cnt[i] = 1;
        }
    }
    for i in (0..(2 * n - 1)).rev() {
        cnt[i] += cnt[i + 1];
    }
    for i in 0..n {
        if cnt[i] == cnt[i + n - 1] {
            println!("Yes");
            return;
        }
    }
    println!("No");
}

fn main() {
    run();
}



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

using namespace std;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1000000007;

using ll = long long;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}

double dp[301][301][301];
int n;
double rec(int i, int j, int k){
    if(i == 0 and j == 0 and k == 0) return 0.0;
    if(i < 0 or j < 0 or k < 0) return 0.0;
    if(dp[i][j][k] >= 0) return dp[i][j][k];

    double res = 0.0;
    if(i > 0) res += rec(i-1, j, k)*i;
    if(j > 0) res += rec(i+1, j-1, k)*j;
    if(k > 0) res += rec(i, j+1, k-1)*k;
    res += n;
    res *= 1.0/(i+j+k);
    return dp[i][j][k] = res;
}


int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    fill_n(**dp, 301*301*301, -1.0);
    cin >> n;

    int cnt[4] = {0};
    rep(x, n){
        int a; cin >> a;
        ++cnt[a];
    }
    cout << setprecision(10) << fixed << rec(cnt[1], cnt[2], cnt[3]) << endl;

    return 0;
}


Measured memory_bytes: 213376
def main():
    n = int(input())
    h = list(map(int, input().split()))
    x = [0] * n
    ans = 0
    
    for _ in range(110):
        pre  = False
        for i in range(n):
            if x[i] < h[i]:
                x[i] += 1
                if pre == False:
                    ans += 1
                    pre = True
            else:
                pre = False 
            
    print(ans)
    
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>

int main(){
	
	long long int N,ans=1000000000000;
	int i;
	scanf("%lld",&N);
	
	for(i=1;i<=sqrt(N);i++){
		if(N%i==0){
			if(ans>i+N/i-2){
				ans=i+N/i-2;
			}
		}
	}
	
	
	printf("%lld",ans);
	
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  
  int i;
  vector<int> a(n), b(n, -1);
  for(i = 0; i < n; i++){
    cin >> a.at(i);
  }
  
  i = 0;
  b.at(0) = 0;
  while(b.at(a.at(i) - 1) == -1){
    b.at(a.at(i) - 1) = b.at(i) + 1;
    i = a.at(i) - 1;
  }
  
  cout << b.at(1) << endl;
}

Measured memory_bytes: 1024
n = int(input())
blue = [input() for _ in range(n)]
m = int(input())
red = [input() for _ in range(m)]
r = 0

blue_kinds = {b: blue.count(b) for b in blue}
red_kinds = {r: red.count(r) for r in red}

for s in blue_kinds:
    dif = 0

    if s in red_kinds:
        dif = blue_kinds[s] - red_kinds[s]
    else:
        dif = blue_kinds[s]
    
    if dif > r:
        r = dif

print(r)

Measured memory_bytes: 3064
//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>	
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define ld long double
#define put(x) printf("%d\n",x)
#define min(x,y) ((x)>(y)?(y):(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define EPS 1e-8
#define mod 1000000007
#define INF 1000000000
using namespace std;
char *fs,*ft,buf[1<<15];
inline char getc()
{
	return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
    int x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const int MAXN=100010;
int n,s,k;
int main()
{
	//freopen("1.in","r",stdin);
	n=read();k=read();s=read();
	for(int i=1;i<=k;++i)printf("%d ",s);
	for(int i=k+1;i<=n;++i)
	{
		if(s==INF)printf("%d ",1);
		else printf("%d ",s+1);
	}
	return 0;
}


Measured memory_bytes: 1280
#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty ;; $n:expr) => {
        (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
    };
}

#[allow(unused_macros)]
macro_rules! get_chars {
    () => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().chars().collect::<Vec<_>>()
        }
    };
    ($n:expr) => {
        {
            (0..$n)
                .map(|_| get_chars!())
                .collect::<Vec<_>>()
        }
    };
}

use std::collections::HashSet;

fn main() {
    let (n, k) = get!(usize, usize);
    let mut res = HashSet::new();

    for _ in 0..k {
        get!(usize);
        let d = get!(usize;;);
        for ss in d.into_iter() {
            res.insert(ss);
        }
    }
    println!("{}", n - res.len());
}


Measured memory_bytes: 2144
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AtCoder solver = new AtCoder();
        solver.solve(1, in, out);
        out.close();
    }

    static class AtCoder {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            String str = in.next();
            int max = 0; // min is 0
            int current = 0;

            for (int i = 0; i < n; i++) {
                if (str.charAt(i) == 'I') {
                    current++;
                } else {
                    current--;
                }
                if (max < current)
                    max = current;
            }
            out.println(max);
        }

    }
}



Measured memory_bytes: 21844
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}

console.log(main());
function main(){
  p = o.l();
  return p[0]+p[1]+p[2]-Math.max(...p);
}

Measured memory_bytes: 7500
N=int(input())
A=list(map(int,input().split()))

listsum=[]
s=0
for i in range(N):
  s+=A[N-1-i]
  listsum.append(s)
  
S=0
for i in range(N-1):
  S+=A[i]*listsum[N-2-i]
  S=S%(10**9+7)
  
print (S)

Measured memory_bytes: 31444
const solve = (data, H, W, K, debug = 0) => {
  const _ = (i, j) => i * W + j;
  let result = 0;

  // Enumerate 2^H, 2^W
  for (let rows = 0; rows < 2 ** H; rows++) {
    for (let cols = 0; cols < 2 ** W; cols++) {
      // Count surviving black entries
      let count = 0;
      for (let i = 0; i < H; i++) {
        for (let j = 0; j < W; j++) {
          if (data[_(i, j)] && ((1 << i) & rows) && ((1 << j) & cols)) {
            count++;
          }
        }
      }

      if (count === K) {
        result++;
      }
    }
  }
  return result;
};

const main = async (istr, ostr) => {
  const readline = require('readline');
  const it = readline.createInterface({input: istr})[Symbol.asyncIterator]();
  const getLine = async () => (await it.next()).value;
  const getMany = async () => (await getLine()).split(' ');

  const [H, W, K] = (await getMany()).map(Number);
  const data = new Uint8Array(H * W);
  const _ = (i, j) => i * W + j;
  for (let i = 0; i < H; i++) {
    const line = await getLine();
    for (let j = 0; j < W; j++) {
      data[_(i, j)] = line[j] === '#';
    }
  }
  const result = solve(data, H, W, K);
  ostr.write(`${result}\n`);
};

if (require.main === module) {
  main(process.stdin, process.stdout);
}

Measured memory_bytes: 32252
#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>


#ifdef _DEBUG
#define typeof(X) std::identity<decltype(X)>::type //C++0x (for vs2010)
#else
#define typeof(X) __typeof__(X) // for gcc
#endif

#define sz(a)  int((a).size())
#define FOREACH(it, c) for (typeof((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define FOR(i,count) for (int i = 0; i < (int)(count); i++)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
const int MODULO = 100000 ;
const int INF = 100000000; //1e8

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef complex<double> Cd;

using namespace std;

int main()
{
	int t; cin>>t;
	bool nl = false;
	while(t--){
		int a[9][9]; FOR(i,9)FOR(j,9) cin>>a[i][j];
		bool b[9][9] = {};
		FOR(i,3)FOR(j,3){
			int b2[10] ={};
			FOR(k,3)FOR(l,3) b2[a[i*3+k][j*3+l]]++;
			FOR(k,10) if(b2[k] >= 2){
				FOR(l,3)FOR(m,3)
					if(a[i*3+l][j*3+m] == k) b[i*3+l][j*3+m] = true;
			}
		}
		FOR(i,9){
			int b2[10] ={};
			FOR(j,9) b2[a[i][j]]++;
			FOR(k,10) if(b2[k] >= 2){
				FOR(j,9) if(a[i][j] == k) b[i][j] = true;
			}
		}
		FOR(j,9){
			int b2[10] ={};
			FOR(i,9) b2[a[i][j]]++;
			FOR(k,10) if(b2[k] >= 2){
				FOR(i,9) if(a[i][j] == k) b[i][j] = true;
			}
		}

		if(nl) puts("");
		nl = true;
		FOR(i,9){
			FOR(j,9) printf("%c%d",b[i][j]?'*':' ',a[i][j]);
			puts("");
		}
	}
	return 0;
}

Measured memory_bytes: 1148
#include<iostream>
using namespace std;
int main(){
	int a;
	int b;
	int m;
	int ans;
	cin>>a;
	cin>>b;
	m=a+b;
	if(m>=24){
		ans=m%24;
	}else{
		ans=m;
	}
	cout<<ans<<"\n";
	
	return 0;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

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

    vi sum(n+1);
    int mi = 0;
    rep(i, n) {
        if(s[i] == '(') {
            sum[i+1] = sum[i]+1;
        } else {
            sum[i+1] = sum[i]-1;
            mi = min(mi, sum[i+1]);
        }
    }
    int x = sum[0] - mi;
    int y = sum[n] - mi;

    rep(i, x) {
        cout << '(';
    }
    cout << s;
    rep(i, y) {
        cout << ')';
    }
    cout << '\n';
}

Measured memory_bytes: 256
import sys
def input():
	return sys.stdin.readline().strip()

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

bigger = [0]*N
bigger_after = [0]*N
for i in range(N):
	for j in range(N):
		if A[i] > A[j]:
			bigger[i] += 1
			if j > i:
				bigger_after[i] += 1

total = 0
for i in range(N):
	total += K * bigger_after[i]
	total += K * (K - 1) * bigger[i] //2
	total = total % 1000000007
print(total)

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

#define each(i, c) for (auto& i : c)
#define mkp(a, b) make_pair(a, b)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> Pll;
const ll MOD = 1e9+7;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << ": " << p.second << ")"; return os; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ", "; os << ")"; return os; }
template<typename K, typename V> ostream& operator << (ostream& os, map<K, V> m) { os << "{"; each (i, m) os << i << ", "; os << "}"; return os; }

int main() {
  ll H, W;
  cin >> H >> W;

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

  ll ans = H*W;
  ans -= h*W;
  H -= h;
  ans -= H*w;

  cout << ans << endl;

  return 0;
}


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

using namespace std;
const int N=3e5+5;
#define F first
#define S second
pair<int, pair<int,int> > f(pair<int, pair<int,int> > x)
{
    int num=x.S.F;
    int cnt=x.S.S;
    return {num/(1<<cnt)-num/(1<<(cnt+1)),{num,cnt+1}};
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    priority_queue< pair<int, pair<int,int> > >pq;
    long long sum=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        sum+=x;
        pq.push(f({0,{x,0}}));
    }
    long long ans=0;

    while(m--)
    {
        pair<int, pair<int,int> > t =pq.top();
        pq.pop();
        if(t.F==0) break;
        ans+=t.F;
        pq.push(f(t));
    }

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


Measured memory_bytes: 1912
fn main() {
  let mut i = 1;
  let mut j = 1;
  let mut done = false;

  while !(i == 10) {
    while !(j == 10) {
      println!("{}x{}={}", i, j, i * j);
      j += 1;
    }
    j = 1;
    i += 1;
  }

}


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

#define ED return 0;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) long(pow(x,y))
const long long mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long int N, K;
    cin >> N >> K;
    long long int answer = 0;
    if(N < K){
        if(N*2 < K || K % 2 == 1){
            cout << 0 << endl;
        }
        else{
            cout << 1 << endl;
        }
        ED
    }
    for(long long int i = 0;i < K;i++){
        if(3 * i % K == i){
            long long int a;
            a = (N-i)/K+1;
            if(i == 0){
                a--;
            }
            answer += pow(a,3);
        }
    }
    cout << answer << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bitset<2000010>f;
int n,a,sum=0;
int main(){
	cin>>n;
	f[0]=1;
	for(int i=1;i<=n;i++){
		cin>>a;
		f|=f<<a;
		sum+=a;
	}
	for(int i=(sum+1)/2;i<=sum;i++){
		if(f[i]!=0){
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main() {
    ll n,m;
    cin >> n >> m;
    vector<ll> a;
    vector<ll> b;
    rep(i,m){
        ll c,d;
        cin >> c >> d;
        a.push_back(c);
        b.push_back(d);
    }
    cout <<max(0LL,1 + *min_element(b.begin(),b.end()) - *max_element(a.begin(),a.end()));
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 2036
N = int(input())
S = input()
dict = {}
for s in S:
    if s in dict:
        dict[s] += 1
    else:
        dict[s] = 1
ans = 1
for d in dict.values():
    ans *= (d+1)
print((ans-1) % (10 ** 9 + 7))

Measured memory_bytes: 3188
#include <iostream>
int main(void)
{
	long x, y;
	std::cin >> x >> y;
	if(std::abs(x) == std::abs(y)){
		if(x * y < 0) std::cout << 1 << std::endl;
		else std::cout << 0 << std::endl;
	}else{
		long k = std::abs(x) - std::abs(y);
		if(k > 0){
			std::cout << k + (x > 0) + (y > 0) << std::endl;
		}else{
			std::cout << -k + (x < 0) + (y < 0) << std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
import sys
import bisect as bi
import math
from collections import defaultdict as dd
import heapq
input=sys.stdin.readline
##import numpy as np
#sys.setrecursionlimit(10**7)
mo=10**9+7
def cin():
    return map(int,sin().split())
def ain():            
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
##def power(x, y):
##    if(y == 0):return 1
##    temp = power(x, int(y / 2))%mo
##    if (y % 2 == 0):return (temp * temp)%mo 
##    else:
##        if(y > 0):return (x * temp * temp)%mo 
##        else:return ((temp * temp)//x )%mo
##
##for _ in range(inin()):
n=inin()
l=ain()
l=sorted(l,reverse=True)
if(n%2==0):
    if(n>=4):
        print(l[0]+0+2*sum(l[1:(n-2)//2+1]))
    else:
        print(l[0])
else:
    if(n>=5):
        print(l[0]+0+2*sum(l[1:(n-2)//2+1])+l[(n-2)//2+1])
    else:
        print(l[0]+l[1])
    


    
    
    
    
    
    
    
    
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##
        
    
    
    
    
    
    
        
        
    
    
    
    


    





##def msb(n):n|=n>>1;n|=n>>2;n|=n>>4;n|=n>>8;n|=n>>16;n|=n>>32;n|=n>>64;return n-(n>>1) #2 ki power
##def pref(a,n,f):             
##    pre=[0]*n
##    if(f==0):         ##from beginning
##        pre[0]=a[0]
##        for i in range(1,n):
##            pre[i]=a[i]+pre[i-1]
##    else:              ##from end
##        pre[-1]=a[-1]
##        for i in range(n-2,-1,-1):
##            pre[i]=pre[i+1]+a[i]
##    return pre
##maxint=10**24 
##def kadane(a,size): 
##    max_so_far = -maxint - 1
##    max_ending_here = 0
##       
##    for i in range(0, size): 
##        max_ending_here = max_ending_here + a[i] 
##        if (max_so_far < max_ending_here): 
##            max_so_far = max_ending_here 
##  
##        if max_ending_here < 0: 
##            max_ending_here = 0   
##    return max_so_far


Measured memory_bytes: 32584
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int g = sc.nextInt();
		int b = sc.nextInt();
		if ((100*r + 10*g + b)%4 == 0)
			System.out.println("YES");
		else System.out.println("NO");
	}
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef pair<ll, int> PILL;
typedef pair<ll, ll> PLL;

const int MAX_N = 1e5+5;
const int M = 1e6;
const ll INF = (ll)(1e18);
const int inf = 1e9;
const ll MOD = 1000000007LL;

void solve() {

}

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

    int h, a;
    cin >> h >> a;

    cout << (h+a-1) / a;










    return 0;
}


Measured memory_bytes: 256