akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

int main()
{
	int a,b,c,d,e,f,g,h;
	cin>>a;
	cin>>b;
	cin>>c;
	cin>>d;
	cin>>e;
	if(e<d)
	{
		f=e-50;
		if(a<b)
		{
			if(a<c){cout<<a+f<<endl;}
			else{cout<<c+f<<endl;}
		}
		else
		{
			if(b<c){cout<<b+f<<endl;}
			else{cout<<c+f<<endl;}
		}
	}
	else
	{
		f=d-50;
		if(a<b)
		{
			if(a<c){cout<<a+f<<endl;}
			else{cout<<c+f<<endl;}
		}
		else
		{
			if(b<c){cout<<b+f<<endl;}
			else{cout<<c+f<<endl;}
		}
		
	}
    
	return 0;

}

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

int main(){
      int S;
      cin >> S;
      int L = S/100;
      int M = S%100;
      if(L >= 1 && L <= 12){
            if(M >= 1 && M <= 12)cout << "AMBIGUOUS" << endl;
            else cout << "MMYY" << endl;
            }else{
                 if(M >= 1 && M <= 12 )cout << "YYMM" << endl;
                  else cout << "NA" << endl;
            }
}

Measured memory_bytes: 384
import sys

sys.setrecursionlimit(10000)

ERROR_INPUT = 'input is invalid'
OPECODE = ['+', '-', '*']
BUF = []


def main():
    stack = get_input()
    ans = calc_stack(stack=stack)
    print(ans)


def calc_stack(stack):
    if stack[-1] in OPECODE:
        BUF.append(stack[-1])
        stack.pop()
        return calc_stack(stack=stack)
    else:
        right_num = int(stack[-1])
        stack.pop()
        if stack[-1] in OPECODE:
            BUF.append(right_num)
            BUF.append(stack[-1])
            stack.pop()
            return calc_stack(stack=stack)
        else:
            left_num = int(stack[-1])
            stack.pop()
            stack.append(calc(left_num, right_num, BUF[-1]))
            BUF.pop()
            stack.extend(reversed(BUF))
            BUF.clear()

        if len(stack) == 1:
            return stack[0]
        else:
            return calc_stack(stack=stack)


def calc(left, right, ope):
    if ope == '+':
        return left + right
    elif ope == '-':
        return left - right
    elif ope == '*':
        return left * right


def get_input():
    inp = input().split(' ')
    opecode_count = 0
    OPECODE_count = 0

    for i in inp:
        if i in OPECODE:
            opecode_count += 1
        elif int(i) < 0 or int(i) > 10**6:
            print(ERROR_INPUT)
            sys.exit(1)
        else:
            OPECODE_count += 1

    if opecode_count < 1 or opecode_count > 100:
        print(ERROR_INPUT)
        sys.exit(1)

    if OPECODE_count < 2 or OPECODE_count > 100:
        print(ERROR_INPUT)
        sys.exit(1)

    return inp


main()

Measured memory_bytes: 11540
#include<bits/stdc++.h>
using namespace std;
#define pb          push_back
#define m_p			make_pair
#define rep(i,a,b)	for(int i=a;i<b;i++)
#define sz(x)       (int)x.size()
#define f			first
#define debug		cout<<"##########3"<<endl
#define mod			1000000007
#define ll			long long int
#define lMax		LLONG_MAX
// queue<int> , prefix_sum(a,a+n) , reverse(a,a+n) , priority_queue <int> max heap , priority_queue <int, vector<int>, greater<int> > min heap;
// == precedence gretaer then &
ll n,m;
ll arr[305];
long double dp[305][305][305];
long double fn(int a, int b, int c){

	if(dp[a][b][c]>-0.5)
		return dp[a][b][c];
	long double q = 0;
	if(a+b+c==0)
	return q;
	if(a>0)
	q+=fn(a-1,b,c)*a;
	if(b>0)
	q+=fn(a+1,b-1,c)*b;
	if(c>0)
	q+=fn(a,b+1,c-1)*c;
	q/=(long double)(a+b+c);
	q += n/(long double)(a+b+c);
	dp[a][b][c] = q;
	//cout<<a<<" "<<b<<" "<<c<<" "<<q<<endl;
	return q;
}
int main() {
    ll i, j, k, c=0, ans=0, t, z=0, x=0, y=0;
	cin>>n;
	rep(i,0,n){
		cin>>arr[i];
		if(arr[i]==1)
		x++;
		else if(arr[i]==2)
		y++;
		else if(arr[i]==3)
		z++;
	}
	rep(i,0,301) rep(j,0,301) rep(k,0,301)
	dp[i][j][k] = -1;
	
	printf("%.15Lf\n", fn(x, y, z));
 	return 0;
}

Measured memory_bytes: 438656
import numpy as np

def getDivisor(n):
    divisor = []
    tmp = n
    for i in range(2, int(n**0.5)+1):
        cnt = 1
        d = [1,]
        while tmp%i == 0:
            d.append(i**cnt)
            tmp //= i
            cnt += 1
        if cnt > 1:
            divisor.append(d)
    if tmp != 1:
        divisor.append([1,tmp])
    if divisor == []:
        divisor.append([1,n])
        
    divisor_mat = np.matrix(1) 
    for d in divisor:
        d = np.matrix(d)
        mat = []
        for dcol in divisor_mat:
            mat.append(dcol.T * d)
        divisor_mat = np.concatenate(mat)
    divisor_mat = np.array(divisor_mat.flatten())
    divisor_mat = np.array(divisor_mat[0].tolist())
    divisor_mat.sort()
    return divisor_mat

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

a = np.array(a)
sum_a = a.sum()
divisor = getDivisor(sum_a)
for d in divisor[::-1]:
  tmp = a % d
  idx = tmp.sum() // d
  tmp.sort()
  num_op = tmp[:-idx].sum()
  if num_op <= k:
    break
print(d)

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

using namespace std;

using ll = long long;

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int l = a + b;
    int r = c + d;
    if (l < r) cout << "Right\n";
    else if (l == r) cout << "Balanced\n";
    else cout << "Left\n";

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const string EMP = " ";
const ll INF = 1LL<<60;
const ll MOD = 1000000007;

int main(){
  int n,m; cin >> n >> m;
  if(n >= m){
    cout << 0 << endl;
    return 0;
  }
  vector<int> x(m);
  for(int i = 0; i < m; i++) cin >> x[i];

  sort(x.begin(), x.end());

  vector<int> d;

  for(int i = 1; i < m; i++){
    int dd = abs(x[i-1] - x[i]);
    d.push_back(dd);
  }
  sort(d.begin(), d.end());

  int ans = 0;
  for(int i = 0; i < m-n; i++){
    ans += d[i];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1276
Module _20190422

    Sub Main()

        Dim sRead As String = Console.ReadLine

        Dim iNum1 As Integer = sRead.Split(" ")(0)
        Dim iNum2 As Integer = sRead.Split(" ")(1)
        Dim iOrder As Integer = sRead.Split(" ")(2)

        Dim iMaxNum As Integer
        If iNum1 > iNum2 Then

            iMaxNum = iNum1

        Else

            iMaxNum = iNum2

        End If

        Dim iTempOrder As Integer = 0
        Dim iKotae As Integer

        For i As Integer = iMaxNum To 1 Step -1

            If iNum1 Mod i = 0 AndAlso iNum2 Mod i = 0 Then

                iTempOrder = iTempOrder + 1

            End If

            If iOrder = iTempOrder Then

                iKotae = i

                Exit For

            End If

        Next

        Console.WriteLine(iKotae)

    End Sub

End Module

Measured memory_bytes: 13268
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<bitset>
#include <sstream>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long ll;

int main()
{
    ll N,M;
    cin>>N>>M;
    ll actotal=0;
    ll mistotal=0;
    ll miscount[N]={0};
    bool ac[N]={false};
    for(ll i=0;i<M;i++)
    {
        ll p;
        string s;
        cin>>p>>s;
        if(ac[p-1]==false && s=="WA")
        {
            miscount[p-1]++;
        }
        else if(ac[p-1]==false && s=="AC")
        {
            ac[p-1]=true;
            actotal++;
        }
        
     
        
        

    }
    for(ll i=0;i<N;i++)
        {
            if(ac[i]==true)
            {
                mistotal+=miscount[i];

            }
        }


    cout<<actotal<<" "<<mistotal<<endl;    
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
const ll INF = (1ll << 60);

ll MOD = 1000000007;

ll permutation(ll x, ll y, ll mod) {
  ll ret = 1;
  for (ll i = 0; i < y; i++) {
    ret *= (x - i);
    ret %= mod;
  }
  return ret;
}

ll factorial(ll x, ll mod) { return permutation(x, x, mod); }

int main() {
  ll N;
  cin >> N;
  string S;
  cin >> S;

  ll ans = 1;
  ll x = 0;

  for (ll i = 0; i < 2 * N; i++) {
    if (S[i] == 'B') {
      if (x % 2 == 0) {
        x++;
      } else {
        ans *= x;
        ans %= MOD;
        x--;
      }
    } else {
      if (x % 2 == 1) {
        x++;
      } else {
        ans *= x;
        ans %= MOD;
        x--;
      }
    }
    if (x == -1) {
      ans = 0;
    }
  }
  if (x != 0) {
    ans = 0;
  }

  cout << ans * factorial(N, MOD) % MOD << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int main() {

 int a, b, c, d;
 cin>>a>>b>>c>>d;

 cout<<max(a*b,c*d)<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <numeric>
#include <utility>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <functional>
#include<iterator>
#include <ctime>
#include <queue>
#include <string>
#include <map>
#include <sstream>
#define MAX_U   10
#define MIN_U   0
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define form(i,a,b) for(int i=(a);i<(b);i++)
#define sz(x) ((int)(x).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
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();}
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<char> vc;
typedef vector<string> vs;
typedef queue<int> qi;
const int INF=numeric_limits<int>::infinity();
void printa(){cout<<"\n";}
template<class T, class... A>void printa(const T&first,const A&... rest){cout<<first;printa(rest...);}
template<class... A>void printa(const A&... rest){printa(rest...);}
void prints(){cout<<" ";}
template<class T, class... A>void prints(const T&first,const A&... rest){cout<<first;prints(rest...);}
template<class... A>void prints(const A&... rest){prints(rest...);}
template<typename T>struct norm : std::binary_function<T,T,T> {  T operator()(T x, T y) const { return std::max(x-y,y-x); }};
template<typename T>struct norm_less : std::binary_function<T,T,bool> {
  T value_;norm_less(T v) : value_(v) {} bool operator()(T x, T y) const { norm<T> f; return f(x,value_) < f(y,value_); }};
int factorial(int x){int f=1;for(int i=1;i<x+1;i++)f=f*i;return f;}
int sigma(int x){int s;for(int i=1;i<x+1;i++)s=s+i;return s;}
int middle(int x){if(x%2==0)return x/2;else return x/2+1;}
double heron(int a,int b,int c){double s;s=(a+b+c)/2;return sqrt(s*(s-a)*(s-b)*(s-c));}
double trapezium(int a,int b,int h){return (a+b)*h/2;}
double triangle(int a,int h){return a*h/2;}
void sorm(vector<int> vec){sort(vec.begin(),vec.end());}
void sorm_s(vector<string> vec){sort(vec.begin(),vec.end());}
void sorg(vector<int> vec){sort(vec.begin(),vec.end(),greater<int>());}
//int cmp( const void *p, const void *q ) {if( ＊(double＊)p > ＊(double＊)q ) return 1;if( ＊(double＊)p < ＊(double＊)q ) return -1;return 0;}

int main(void){
   cin.tie(0);
   ios::sync_with_stdio(false);
  double a,b,c,d,e=100000,g;
   //int ad,bd;
   unsigned long f=1;
   string st,tt,nt;
   vi ad,bd,cd,dd;
   vs A,W,B;
   int X=0;
   vs as,bs,cs,ds;
   vector<char> C;
   vector<pair<double,int>> pdi;
   string sa;
  // char cd;
   int flag=0,nfl,ta,tb;
   std::cin>>a>>b>>c;
   for(flag=0;flag<a;flag++){
       std::cin>>d;
       g=c-(b-(d*0.006));
       if(g<0)g*=-1;
       //prints(g);
       if(flag==0)e=g;
       else if(e>g){e=g;f=flag+1;}
   }
   printa(f);
   return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        MyReader r = new MyReader();   
        int[] a = r.ii();
        int N = a[0];
        int K = a[1];
        int ans;
        if(N<K){
            ans = 1;
        } else if(N%K == 0){
            ans = 0;
        } else{
            ans = N-K;
        }
        println(ans);
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Int(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long(ss[j]);            
            return ll;
        }
    }
}

Measured memory_bytes: 21076
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  
  while(cin >> n, n) {
    int a = n;
    int ans = 0;
    for(int st=1; st<n; st++) {
      a = n;
      for(int i=st; a>0; i++)
	a -= i;
      if(a == 0)
	ans ++;
    }
    cout << ans << endl;
  }
  
  return 0;
}

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

int main(void){
    int n;
    bool ans = true;
    cin >> n;
    int h[n];
    rep(i, n){
        cin >> h[i];
    }

    if(h[0] >= h[1])    h[0]--;

    rep(i, n-1){
        if(h[i] < h[i+1])   h[i+1]--;

        if(h[i] > h[i+1]){
            ans = false;
            break;
        }
    }
    if(ans)     cout << "Yes" << endl;
    else        cout << "No" << endl;
    return 0;
}

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

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

  int a, b, c, d;
  cin >> a >> b >> c >> d;
  int dy = d - b;
  int dx = c - a;
  string res = "";
  for (int i = 0; i < dy; i++) res += "U";
  for (int i = 0; i < dx + 1; i++) res += "R";
  for (int i = 0; i < dy + 1; i++) res += "D";
  for (int i = 0; i < dx + 1; i++) res += "L";
  for (int i = 0; i < 1; i++) res += "U";
  for (int i = 0; i < 1; i++) res += "L";
  for (int i = 0; i < dy + 1; i++) res += "U";
  for (int i = 0; i < dx + 1; i++) res += "R";
  for (int i = 0; i < dy + 1; i++) res += "D";
  for (int i = 0; i < dx; i++) res += "L";
  cout << res << '\n';
  return 0;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc112/tasks/abc112_a

#include <iostream>
using namespace std;

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  int n;

  cin >> n;

  if (n == 1)
    cout << "Hello World" << '\n';
  else
  {
    int a, b;
    cin >> a >> b;
    cout << a + b << '\n';
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
#include <string>
#include <iterator>
#include <vector>
 
using namespace std;

typedef long long ll;
typedef long double ld;
#define L(ID) ((ID*2)+1)
#define R(ID) ((ID*2)+2)
#define M(L,R) ((L+R)/2)
#define forr(start,end) for(int i = start; i < end; i++)
#define gap ' '
 
const int MAXN = 1e6 + 5;


int largest(int a, int b){
	return (a<b)?b:a;
}


int main() {
	int a = 0, b = 0;
	cin >> a >> b;
	if(a <= 0 and b > 0){
		cout << "Zero" << endl;
		return 0;
	}
	if(a == 0 or b == 0){
		cout << "Zero" << endl;
		return 0;
	}
	if(a > 0 and b > 0){
		cout << "Positive" << endl;
		return 0;
	}
	if(a % 2 == 0 and b % 2 != 0){
		cout << "Positive" << endl;
	}
	else if(a % 2 != 0 and b % 2 == 0){
		cout << "Positive" << endl;
	}
	else {
		cout << "Negative" << endl;
	}


    return 0;
} 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int i,x=0,y=0,ans=0,len;
string a;
int main()
{
    
    cin>>a;
    len=a.size();
    for(i=0;i<len;i++)
	{
        if(x==y)
		{
            x++;
            if(a[i]=='p')
				ans--;
        }
        else
		{
            y++;
            if(a[i]=='g')
				ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 512
n,w=[int(x) for x in input().split()]
dp=[0]*(w+1)
lw=w
for test in range(n):
    cw, v = [int(x) for x in input().split()]
    temp=[0]*(w+1)
    for i in range(1,w+1):
        if cw <= i :
            temp[i]=max(dp[i],v+dp[i-cw])
        else:
            temp[i]=max(dp[i],temp[i-1])
    dp=temp[:]
    #print(dp)
print(dp[w])

Measured memory_bytes: 76468
#include<bits/stdc++.h>
using namespace std;
int main(){
        string s;
        cin>>s;
        int size=s.size();
        if(size==1){
                cout<<s;
          		return 0;
        }
        long sum=0;
        for(int i=0;i<pow(2,size-1);i++){
                int t=i;
                int head=0,c=1;
                while(t!=0){
                        if(t%2==0){
                                c++;
                                t/=2;
                                continue;
                        }
                        sum+=atol(s.substr(head,c).c_str());
                        head+=c;
                        c=1;
                        t/=2;
                }
                sum+=atol(s.substr(head).c_str());
        }
        cout<<sum;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {

	var r, c int

	fmt.Scanln(&r, &c)

	table := make([][]int, r+1)
	for i := range table {
		table[i] = make([]int, c+1)
	}

	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			fmt.Scanf("%d", &table[i][j])
			table[i][c] += table[i][j]
			table[r][j] += table[i][j]
		}
		table[r][c] += table[i][c]
	}

	for _, tc := range table {
		for i, tcr := range tc {
			if i != c {
				fmt.Printf("%d ", tcr)
			} else {
				fmt.Printf("%d\n", tcr)
			}
		}
	}

}



Measured memory_bytes: 1820
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
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 const INF = 1e9+1;


int main()
{
    int n; ll a,b;
    cin >> n >> a >> b;
    a -= b;
    vl h(n);
    rep(i,n) cin >> h[i];

    auto C = [&](ll x) {
        ll cnt = 0;
        rep(i,n) {
            ll rem = max((ll)0,h[i]-b*x);
            cnt += (rem+a-1)/a;
        }
        return cnt <= x;
    };

    ll l = 0, r = INF;
    while(r-l>1) {
        int mid = (l+r)/2;
        if(C(mid)) r = mid;
        else l = mid;
    }

    cout << r << endl;
    return 0;
}

Measured memory_bytes: 4056
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define uniq(x) (x).erase(unique(ALL(x)),(x).end())
#define SORT(x) sort(ALL(x))
#define REV(x) reverse(ALL(x))
#define foreach(it,x) for(__typeof((x).begin()) it=(x).begin();it!=(x).end();it++)
#define debug(x) cerr<<#x<<"="<<(x)<<endl
#define gett() cerr<<"Time:"<<clock()<<"ms."<<endl
int n;
int hd[100100];
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>hd[i];
	sort(hd+1,hd+n+1);
	cout<<hd[n/2+1]-hd[n/2]<<endl;
	return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

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

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n;
string s;
void solve(){
	cin >> n >> s;
	
	int cnt = 0;
	int l = 0, r = 0;
	for(int i = 0; i < n; i++){
		if(s[i] == '(') cnt++;
		else cnt--;
		if(cnt < 0) chmax(l, abs(cnt));
	}
	cnt = 0;
	for(int i = n-1; i >= 0; i--){
		if(s[i] == ')') cnt++;
		else cnt--;
		if(cnt < 0) chmax(r, abs(cnt));
	}
	for(int i = 0; i < l; i++) cout << '(';
	cout << s;
	for(int i = 0; i < r; i++) cout << ')';
	cout << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;

bool hantei(long long x){
	for(long long i=2; i*i<=x; i++){
		if(x%i==0) return 0;
	}
	return x>1;
}

vector<ll> bunkai(ll x){
	vector<ll> a;
	if(hantei(x)) {
		a.push_back(x);
		a.push_back(1);
	}
	else{
		for(ll i=1; i*i<=x; i++){
			if(!(x%i)) {
				a.push_back(i);
				if(i*i==x) break;
				a.push_back(x/i);
			}
		}
	}
	sort(a.begin(),a.end());
	return a;
}
int main(){
	
	ll n; cin>>n;
	auto a = bunkai(n-1);
	auto b = bunkai(n);
	ll ans{};
	for(auto i:b){
		ll m = n;
		if(i==1) continue;
		while(!(m%i)) m/=i;
		ans += ((m%i)==1);
	}
	ans += a.size()-1;
	cout << ans << endl; 
	
}



Measured memory_bytes: 3580
#include<bits/stdc++.h>
#define mxn 300005
#define N 300001
using namespace std;
int seg[4*mxn], ara[mxn];
void update(int n, int s, int e, int indx, int val)
{
    if(s==indx && e==indx)
    {
        seg[n]= val;
        return;
    }
    if(s>indx || e<indx)return;
    int mid= (s+e)/2;
    update(n*2, s, mid, indx, val);
    update(n*2 +1, mid+1, e, indx, val);
    seg[n]= max(seg[n*2], seg[n*2 +1]);
    return;
}
int query(int n, int s, int e, int l, int r)
{
    if(s>=l && e<=r)return seg[n];
    if(s>r || e<l)return 0;
    int mid= (s+e)/2;
    return max(query(n*2, s, mid, l, r), query(n*2 +1, mid+1, e, l, r));
}
int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++)scanf("%d", &ara[i]), ara[i]++;
    int res= 0;
    for(int i=n; i>=1; i--)
    {
        int x= query(1, 1, N, max(ara[i]-k, 1), min(ara[i]+k, N));
        update(1, 1, N, ara[i], x+1);
        res= max(res, x+1);
    }
    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 9092
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define INF 1e18
#define fcout cout << fixed << setprecision(15)
#define int long long
#define endl "\n"
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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;};



signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	
	double a, b, h, m;
	cin >> a >> b >> h >> m;

	double H = 30.0 * h + 0.5 * m;
	double M = 6.0 * m;
	double kaku = abs(H - M);
	chmin(kaku, 360.0 - kaku);
	//cout << kaku << endl;
	kaku = kaku * M_PI / 180.0;
	//fcout << kaku << endl;

	double t = a * a + b * b - 2 * a * b * cos(kaku);
	fcout << pow(t, 0.5) << endl;
	return 0;
}

Measured memory_bytes: 4232
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys  # {{{
import os
import time
import re
from pydoc import help
import string
import math
from operator import itemgetter
from collections import Counter
from collections import deque
from collections import defaultdict as dd
import fractions
from heapq import heappop, heappush, heapify
import array
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy as dcopy
import itertools
# }}}

# pre-defined{{{
sys.setrecursionlimit(10**7)
INF = 10**20
GOSA = 1.0 / 10**10
MOD = 10**9+7
ALPHABETS = [chr(i) for i in range(ord('a'), ord('z')+1)]  # can also use string module
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def DP(N, M, first): return [[first] * M for n in range(N)]
def DP3(N, M, L, first): return [[[first] * L for n in range(M)] for _ in range(N)]
from inspect import currentframe
def dump(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' => '+repr(arg) for arg in args), file=sys.stderr)
# }}}

def local_input():# {{{
    from pcm.utils import set_stdin
    import sys
    if len(sys.argv) == 1:
        set_stdin(os.path.dirname(__file__) + '/test/' + 'sample-1.in')# }}}

def solve():
    s = input()
    res = ""
    for c in s:
        if c=='9':
            res += '1'
        else:
            res += '9'
    print(res)
    return 0

if __name__ == "__main__":# {{{
    try:
        local_input()
    except:
        pass
    solve()
# vim: set foldmethod=marker:}}}


Measured memory_bytes: 102892
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		String n = sc.next();
		char[] a = new char[n.length()];
		for (int i = 0; i < n.length(); i++) {
			if (n.charAt(i) == '1') {
				a[i] = '9';
			} else {
				a[i] = '1';
			}
		}
		System.out.println(a);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second

#define DUMP(x) cout<<#x<<":"<<(x)<<endl
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class T>
istream& operator>>(istream& is, vector<T>& xs){
  for(auto& x: xs)
	is >> x;
  return is;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& xs){
  for(unsigned int i=0;i<xs.size();++i)
	os << (i?" ":"") << xs[i];
  return os;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  int N;
  cin >> N;
  VI xs(N), ys(N);
  cin >> xs >> ys;

  int ans = 0;
  REP(i,29){
	VI bs(N);
	REP(j,N) bs[j] = ys[j] % (1<<(i+1));
	SORT(bs);

	for(auto x: xs){
	  int x_ = x % (1<<(i+1));
	  auto b1 = lower_bound(ALL(bs), 1*(1<<i) - x_);
	  auto e1 = lower_bound(ALL(bs), 2*(1<<i) - x_);
	  auto b2 = lower_bound(ALL(bs), 3*(1<<i) - x_);
	  auto e2 = lower_bound(ALL(bs), 4*(1<<i) - x_);
	  if(((e1-b1) + (e2-b2)) % 2)
		ans ^= 1<<i;
	}
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 2672
#include <bits/stdc++.h>
#define ll unsigned long long
#define pi 3.1415926535897932384626433832795
#define fin(a,n)  for(ll i=0;i<n;i++) cin>>a[i];
#define fout(a,n)  for(ll i=0;i<n;i++) cout<<a[i]<<" ";
int N = 1000000007;
using namespace std;

int main() 
{
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); cout.tie(NULL);
	int a,b,c;
	cin>>a>>b>>c;
	cout<<c<<" "<<a<<" "<<b<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m; cin>>n>>m;
    vector<ll> a(m);rep(i,m)cin>>a[i];
    rep(i,m)n-=a[i];
    if(n>=0)cout<<n<<endl;
    else cout<<-1<<endl;

    return 0;
}

Measured memory_bytes: 3736
#define _USE_MATH_DEFINES////////////////////////////////////////
#include<bits/stdc++.h>//////////////////////////////////////////
#define deb(...)/////////////////////////////////////////////////
#define DBP(...)/////////////////////////////////////////////////
#ifdef LOC///////////////////////////////////////////////////////
#include"debuglib.h"/////////////////////////////////////////////
#endif///////////////////////////////////////////////////////////
#define x first//////////////////////////////////////////////////
#define y second/////////////////////////////////////////////////
#define pb push_back/////////////////////////////////////////////
#define sz(x)int((x).size())/////////////////////////////////////
#define each(a,x)for(auto&a:(x))/////////////////////////////////
#define all(x)(x).begin(),(x).end()//////////////////////////////
#define rep(i,b,e)for(int i=(b);i<(e);i++)///////////////////////
using namespace std;using ll=long long;using Pii=pair<int,int>;//
using Vi=vector<int>;void run();int main(){cin.sync_with_stdio///
(0);cin.tie(0);cout<<fixed<<setprecision(18);run();return 0;}////
//-------------------------------------------------------------//

constexpr int MOD = 998244353;

ll modPow(ll a, ll e, ll m) { // a^e mod m
	ll t = 1 % m;
	while (e) {
		if (e % 2) t = t*a % m;
		e /= 2; a = a*a % m;
	}
	return t;
}

struct Zp {
	ll x; // Contained value, in range [0;MOD-1]
	Zp() {}
	Zp(ll a) : x(a%MOD) { if (x < 0) x += MOD; }
	#define OP(c,d) Zp& operator c##=(Zp r) { \
			x = x d; return *this; } \
		Zp operator c(Zp r) const { \
			Zp t = *this; return t c##= r; }
	OP(+, +r.x - MOD*(x+r.x >= MOD));
	OP(-, -r.x + MOD*(x-r.x < 0));
	OP(*, *r.x % MOD);
	OP(/, *r.inv().x % MOD);
	Zp inv() const { return pow(MOD-2); }
	Zp pow(ll e) const{ return modPow(x,e,MOD); }
	void print() { cerr << x; } // For deb()
};

constexpr int MAX_V = 1e6+5;

void run() {
	int n; cin >> n;
	Vi elems(n);
	each(e, elems) cin >> e;

	Vi cnt(MAX_V);
	each(e, elems) cnt[e]++;

	vector<Zp> mults(MAX_V);
	rep(i, 1, MAX_V) mults[i] = Zp(i).inv();

	Zp ans = 0;

	rep(i, 1, MAX_V) {
		for (int j = i*2; j < MAX_V; j += i) {
			mults[j] -= mults[i];
		}

		Zp sum = 0;
		for (int j = i; j < MAX_V; j += i) {
			sum += Zp(j) * cnt[j];
		}

		ans += sum*sum * mults[i];
	}

	each(e, elems) ans -= e;
	ans /= 2;
	cout << ans.x << endl;
}


Measured memory_bytes: 12800
#include <iostream>
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

int main()
{
    int N;
    cin >> N;
    vector<int> hist(N);
    rep(i, N) {
        int a;
        cin >> a;
        ++hist[a-1];
    }

    sort(hist.begin(), hist.end());

    vector<int> s(N+1);  //! s[i] = sum of hist[0..i) 
    for (int i = 1; i <= N; ++i) {
        s[i] = s[i-1] + hist[i-1];
    }

    int ans = N;
    int i = N;
    for (int k = 1; k <= N; ++k) {
        auto check = [&](int c) {
            while (0 < i && c <= hist[i-1]) --i;
            LL sum = c * (N-i) + s[i];
            bool ret = (c * k <= sum);
            return ret;
        };
        while (0 <= ans) {
            if (check(ans)) {
                break;
            } else {
                --ans;
            }
        }
        cout << ans << '\n';
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
using P=pair<int,int>;

int n,i;
vector<pair<int,int>> ab;

int main(){
    cin>>n;
    Graph G(n);

    for(i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        G[a].push_back({b});
        G[b].push_back({a});
        pair<int,int> p=make_pair(a,b);
        ab.push_back(p);
    }

    queue<int> que;
    vector<int> seen(n,0);
    vector<int> parent(n,0);
    int color=0;
    map<pair<int,int>,int> colorass;
    que.emplace(0);
    seen[0]=1;

    while(que.size()!=0){
        int state=que.front();
        que.pop();
        color=0;
        for(auto next:G[state]){
            if(seen[next]!=1){
                seen[next]=1;
                color++;
                if(parent[state]==color){
                    color++;
                }
                parent[next]=color;

                pair<int,int> p=make_pair(state,next);
                colorass[p]=color;

                que.push(next);
            }

        }
    }

    int max=0;
    for(auto i:ab){
        if(max<colorass[i]){max=colorass[i];}
    }
    cout<<max<<endl;

    for(auto i:ab){
        cout<<colorass[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 13812
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d,e=1;
	cin>>a>>b>>c>>d;
	while(1)
	{
		if(e%2==1)
		{
		if(c<b || c==b)
		{
			cout<<"Yes"<<endl;
			return 0;
		}
		else
		c=c-b;
		e++;
		continue;
	}
	if(e%2==0)
	{
		if(a<d || a==d)
		{
			cout<<"No"<<endl;
			return 0;
		}
		else
		a=a-d;
		e++;
		continue;
	}
	}
}

Measured memory_bytes: 3632
package main

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

func main() {
	a, b, x := float64(ReadInt()), float64(ReadInt()), float64(ReadInt())
	s := x / a
	var rad float64
	if s > a*b/2 {
		h := (a*b - s) * 2 / a
		rad = math.Atan2(h, a)
	} else {
		l := 2 * s / b
		rad = math.Atan2(b, l)
	}
	fmt.Println(rad / math.Pi * 180)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }


Measured memory_bytes: 1840
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 桁DP, Lを超えないものと保留のもの
MOD = 10 ** 9 + 7
L = sr()
dp = [1, 2]
length = len(L)
for i in range(1, length):
    prev = dp[:]
    if L[i] == '1':
        dp[0] = prev[0] * 3 + prev[1]
        dp[1] = prev[1] * 2
    else:
        dp[0] = prev[0] * 3
        dp[1] = prev[1]
    dp[0] %= MOD
    dp[1] %= MOD

answer = sum(dp)
print(answer%MOD)


Measured memory_bytes: 39856
n=int(input())
h=[int(i) for i in input().split()]
j=0
k=0
for i in range(1,len(h)):
  if h[i-1]>=h[i]:
    j+=1
  else:
    k=max(k,j)
    j=0
k=max(k,j)
print(k)

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

int gcd(int x, int y) {
    if(x < y) swap(x,y);
    while(y>0) {
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int x,y;
    cin >> x >> y;
    cout << gcd(x,y) << endl;
    return 0;
}


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

using vertex = pair<int, int>;  // <隣接する頂点, 長さ>
using graph = vector<vector<vertex>>;

vector<int> ans(100001);

void dfs(const graph &gr, int v /* vertex*/, int p /* parent */,
         int c /* color */) {
    ans[v] = c;
    for (auto e : gr[v]) {
        if (e.first == p) continue;  // 隣接する頂点が親ならなにもしない。
        if (e.second & 1) {
            dfs(gr, e.first, v, !c);  // 長さが奇数なら色を変えて次の探索へ。
        } else {
            dfs(gr, e.first, v, c);  // 長さが偶数なら色はそのままで次の探索へ。
        }
    }
}

int main() {
    int n;
    cin >> n;
    graph g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        g[u].push_back(vertex(v, w));
        g[v].push_back(vertex(u, w));
    }
    dfs(g, 0 /* 根の番号 */, -1 /* 根の親はないので存在しない値 */, 0);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << endl;
    }
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i=0; i<N; ++i) cin >> S[i];

    for (int i=0; i<N; ++i) reverse(S[i].begin(), S[i].end());
    sort(S.begin(), S.end(), [](auto a, auto b){return (int)a.size() > (int)b.size();});

    map<string, vector<int>> mp;
    ll res = 0;
    int cur = (int)S.front().size();
    for (int i=0; i<N; ++i) {
        int len = (int)S[i].size();
        if (cur >= len) {
            int dif = cur - len + 1;
            map<string, vector<int>> tmp;
            for (auto iter=mp.begin(); iter!=mp.end(); ++iter) {
                string sub = iter->first.substr(0, iter->first.size()-dif);
                for (int j=0; j<dif; ++j) iter->second[*(iter->first.end()-dif+j) - 'a'] = iter->second.back();
                if ((int)tmp[sub].size() == 0) {
                    tmp[sub] = iter->second;
                } else {
                    vector<int> &v = tmp[sub];
                    for (int j=0; j<27; ++j) v[j] += iter->second[j];
                }
            }
            mp.swap(tmp);
            cur -= dif;
        }
        string sub = S[i].substr(0, len-1);
        int pla = S[i].back() - 'a';
        if (mp[sub].size() == 0) mp[sub].assign(27, 0);
        else res += mp[sub][pla];
        vector<int> &v = mp[sub];
        ++v[pla];
        ++v.back();
    }

    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 37200
#include<bits/stdc++.h>
using namespace std;
int read(){
	int x=0,f=0;char ch=getchar();
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x;
}
const int N = 1e6;
int n,sum[1<<17],val[N],num[N],S,dp[1<<17];
int main()
{
	n = read();
	for(int i = 1;i < n;i++)
	{
		int a = read()+1,b = read()+1,w = read();
		val[a] ^= w;val[b] ^= w;
	}
	for(int i = 1;i <= n;i++) num[val[i]]++;
	int ans = 0;
	for(int i = 1;i < 16;i++)
	ans += num[i]/2,S |= ((num[i]&1)<<i-1);
	for(int i = 1;i < 1<<15;i++)
	{
		for(int j = 1;j < 16;j++)
		{
			sum[i] ^= j * ((i>>(j-1))&1);
			dp[i] += (i>>(j-1))&1;
		}
		dp[i]--;
	}
	dp[0] = 0;
	for(int i = 1;i < 1<<15;i++)
	{
		if(sum[i]) continue;
		for(int j = i;j;j=(j-1)&i)
		{
			if(sum[j]) continue;
			dp[i] = min(dp[i],dp[i^j]+dp[j]);
		}
	}
	cout<<ans+dp[S]<<endl;
	return 0;
}

Measured memory_bytes: 4280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,-1,0,1},dy={1,0,-1,0};



int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,k;cin >> n >> k;
	if(k==1) cout << 0 << endl;
	else cout << n-k << endl;
}

Measured memory_bytes: 892
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
int n;
int h[110];
int migi(int i){
    if(i==n) return i-1;
    if(h[i]==0) return i-1;
    else return migi(i+1);
}
int hidari(int j){
    if(j==-1) return 0;
    if(h[j]==0) return j+1;
    else return hidari(j-1);

}
int main(){
    int d;
    cin>>d;
    if(d==24) cout<<"Christmas Eve"<<endl;
    if(d==25) cout<<"Christmas"<<endl;
    if(d==22) cout<<"Christmas Eve Eve Eve"<<endl;
    if(d==23) cout<<"Christmas Eve Eve"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAXN 100007
using namespace std;
vector<int> g[MAXN],w[MAXN],v;
int sga[MAXN],dp[MAXN],cnt[16];
void dfs(int s,int f,int d)
{
	int x=0;
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s,w[s][i]);
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) x^=w[s][i];
	if(x!=d && s!=f) cnt[x^d]++;
}
int main()
{
	int n; cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int t1,t2,t3;
		cin>>t1>>t2>>t3;
		g[t1].push_back(t2);
		g[t2].push_back(t1);
		w[t1].push_back(t3);
		w[t2].push_back(t3);
	}
	dfs(0,0,0);
	int sol=0;
	for(int i=1;i<=15;i++) {sol+=cnt[i]/2; if(cnt[i]&1) v.push_back(i);}
	int m=v.size();
	for(int i=0;i<m;i++) sga[1<<i]=1;
	for(int i=0;i<(1<<m);i++)
	{
		int x=0;
		for(int j=0;j<m;j++) if((1<<j)&i) x^=v[j];
		if(x==0) sga[i]=__builtin_popcount(i)-1;
	}
	fill(dp,dp+MAXN,100000); dp[0]=0;
	for(int i=1;i<(1<<m);i++)
	{
		int sb=i;
		do
		{
			if(sga[sb]) dp[i]=min(dp[i],dp[i^sb]+sga[sb]);
        	sb = (sb-1) & i;
    	} while(sb!=0);
	}
	cout<<sol+dp[(1<<m)-1];
}


Measured memory_bytes: 20716
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n],b[n],c[n];
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i]>>c[i];
  }
  int na[n],nb[n],nc[n];
  na[0]=max(b[0],c[0]);
  nb[0]=max(a[0],c[0]);
  nc[0]=max(a[0],b[0]);
  for(int i=1;i<n;i++){
    na[i]=max(nb[i-1]+b[i],nc[i-1]+c[i]);
    nb[i]=max(na[i-1]+a[i],nc[i-1]+c[i]);
    nc[i]=max(na[i-1]+a[i],nb[i-1]+b[i]);
  }
  cout<<max(na[n-1],max(nb[n-1],nc[n-1]))<<endl;
  return(0);
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a,sum=0;
    cin>>n>>a;
    int arr[a];
    for(int i=0;i<a;i++)
    {
        cin>>arr[i];
        sum+=arr[i];
    }
    if(sum>=n)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}

Measured memory_bytes: 640
N = int(input())
ans = 0
maxCnt = 0

for i in range(1, N + 1):
    tmpCnt = 0
    tmp = i
    if i % 2 == 0:
        for j in range(i):
            tmp = tmp // 2
            tmpCnt += 1
            if tmp % 2 != 0:
                break
    if maxCnt <= tmpCnt:
        maxCnt = tmpCnt
        ans = i

print(ans)

Measured memory_bytes: 3060
use proconio::{input};
use std::cmp::{max, min};

fn main(){
    input!{
        n: usize,
        a: [i64;n]
    }
    let mut b: Vec<_> = a.into_iter().enumerate().collect();
    b.sort_by_key(|p| p.1);
    let diff = |a:usize, b:usize| -> i64 {
        (max(a, b) - min(a, b)) as i64
    };
    let mut dp = vec![0];
    while let Some((k, a)) = b.pop() {
        let len = dp.len();
        let mut next = vec![0; len + 1];
        for (i, v) in dp.into_iter().enumerate() {
            next[i] = max(next[i], v + a * diff(k, n - (len - i)));
            next[i+1] = max(next[i + 1], v + a * diff(k, i));
        }
        dp = next;
    }
    let ans = dp.into_iter().max().unwrap();
    println!("{}", ans);
}

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

int main(){
    int r, g, b, n;
    cin >> r >> g >> b >> n;

    long long int ans = 0;
    for(int i=0; i<=n/r; i++){
        for(int j=0; j<=n/g; j++){
            if(i * r + j * g > n) break;
            if((n - (i * r + j * g)) % b == 0) ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3596