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

// 再帰・分割統治で与えられた整数リストから
// 与えられた整数mが作成できるかを判定する
// 整数リストの各要素に対して、選択する or しない
// の組み合わせを全探索する
bool CanCreateNumber(int i, int m, int n, int vecNum[]) {
    bool res = true;
    if (m==0) return true;
    if (i>=n) return false;
    // mから与えられた整数リストの各選択要素を引いていき
    // 0になった→整数リストでmが作れる
    // iがm以上になった→作れない
    res = CanCreateNumber(i+1, m, n, vecNum) || CanCreateNumber(i+1, m-vecNum[i], n, vecNum);
    return res;
}

int main() {
  int n = 0;
  int m = 0;
  int numTmp = 0;
  int vecA[3000];

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

  scanf("%d",&m);
  string strRes;
  for (int j = 0; j < m; j++)
  {
      scanf("%d",&numTmp);
      strRes = (CanCreateNumber(0, numTmp, n, vecA)) ? "yes" : "no";
      printf("%s\n",strRes.c_str());
  }
  return 0;
}


Measured memory_bytes: 3232
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
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() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S; cin >> S;
  vector<bool> dir(4, false);
  for(char c:S) {
    if(c == 'S') dir[0]=true;
    else if(c == 'N') dir[1]=true;
    else if(c == 'E') dir[2]=true;
    else dir[3]=true;
  }
  if(dir[0] && dir[1] && dir[2] && dir[3]) cout << "Yes" << endl;
  else if(dir[0] && dir[1] && !dir[2] && !dir[3]) cout << "Yes" << endl;
  else if(!dir[0] && !dir[1] && dir[2] && dir[3]) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        double a = sc.nextDouble();
        double b = sc.nextDouble();
        double c = sc.nextDouble();
        double d = sc.nextDouble();
        double ans = Math.sqrt(Math.pow((c-a), 2)+Math.pow((b-d), 2));


        System.out.println(ans);
        sc.close();
	}


}



Measured memory_bytes: 28016
#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
#define gridif(a,x,b) if((a)<=(x)&&(x)<(b))

using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
const int mod=1000000007;

int digitsum(int n,int b){
	if(b<2) return -1;
	if(n<b) return n;
	return digitsum(n/b,b)+n%b;
}
int mpow(int a,int x);
int m_inv(int n);
vector<int> split(int n,int a);
string xal_number(int n,int x);
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}
class Factorial{
private:
	vector<int> fac;
public:
	Factorial(int N){
		fac.push_back(1);
		rep(i,N) fac.push_back(fac[i]*(i+1)%mod);
	}
	int fact(int a){return fac[a];}
	int ifac(int a){return m_inv(fac[a]);}
	int cmb(int n,int r);
};
struct UnionFind {
    vector<int> par; // 親ノード
    UnionFind(int n = 1) { init(n);}
    void init(int n = 1) {
        par.resize(n);
        rep(i,n) par[i] = -1;
    }
    int root(int x) {
        if (par[x] <0) return x;
        else return par[x] = root(par[x]);      
    }
    int size(int x){ return -par[root(x)];}
    bool issame(int x, int y) {return root(x)==root(y);}
    bool connect(int x, int y);
};

signed main(){
	string a,b,c;
	cin>>a>>b>>c;
	if(a.back()==b.front()&&b.back()==c.front()) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
//***Wherever you are, and whatever you do, be in love.***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

vector<ll> g[100002];
ll vis[100002];
ll par[100002];

void dfs(ll u){
    queue<ll> q;
    q.push(0);
    while(!q.empty()){
        ll t=q.front();
        q.pop();
        if(vis[t]) continue;
        vis[t]=1;
        for(auto x:g[t]){
            if(vis[x]) continue;
            q.push(x);
            if(par[x]!=-1) continue;
            par[x]=t;
        }
    }
}

int main(){
    ll n,m,f=0;
    cin>>n>>m;

    forn(i,m){
        ll u,v;
        cin>>u>>v;
        u--;
        v--;
        g[u].pb(v);
        g[v].pb(u);
    }
    forn(i,n) par[i]=-1;
    dfs(0);
    forn(i,n){
        if(!vis[i]){
            f=1;
            break;
        }
    }
    if(f==1){
        cout<<"No";
        return 0;
    }
    cout<<"Yes"<<endl;
    for(ll i=1;i<n;i++) cout<<par[i]+1<<"\n";
}
  

Measured memory_bytes: 13952
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N;
    cin >> N;
    int ans = 0;
    if (N % 10 == 2) ans++;
    N /= 10;
    if (N % 10 == 2) ans++;
    N /= 10;
    if (N % 10 == 2) ans++;
    N /= 10;
    if (N % 10 == 2) ans++;
    
    cout << ans << endl;
}

Measured memory_bytes: 3596
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;
#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn main(){
    let line = read_as_vec::<u64>();
    let (n, h, w) = (line[0], line[1], line[2]);
    let mut ans: u64 = 0;
    for _ in 0..n{
        let line = read_as_vec::<u64>();
        let (a, b) = (line[0], line[1]);
        if h <= a && w <= b{
            ans += 1;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <queue>
#define mod 1000000007
#define ten5 100005
#define PI 3.1415926
using namespace std;

int dp[ten5];

int main()
{
    //int m,n,o=0,i,j,k;
    long long int sum=0,sum2=0,small=0;
    double ans=0.0,half;
    long long int m,n,o,i,j,k=0,now=0;
    set <int> sint;
    //float f,g,h;
    //char now,pre;
    string s;
    cin>>s>>n;
    for(i=0;i<s.size();i++)
    {
        if(s[i]!='1' || i==n-1)
        {
            cout<<s[i];
            break;
        }
    }
    return 0;
}





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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s= sc.next();
		if(s.indexOf("7")!=-1) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}


	}

}


Measured memory_bytes: 35488
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <unordered_map>
//#include"testlib.h"
#define endl "\n"
#define all(v) v.begin(),v.end()
#define allr(s) s.rbegin(),s.rend()
#define RT(s) return cout<<s,0
#define watch(x) cout << (#x)<<" = "<<x<<endl
#define sz(s)    (int)(s.size())
#define PI acos(-1)
#define EPS 1e-8
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
int dy[] = { 1, -1, 0, 0, -1, 1, 1, -1 };
int dx[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
void file() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
	//freopen("street.in", "r", stdin);
	//freopen("out.txt", "w", stdout);
#endif
}
void fast() {
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL);
}
const int N = 3e3 + 9;
ll mem[N][N];
int mod = 998244353;
int n, s;
vi v1;
ll fpow(ll x, ll p) {
	if (!p)
		return 1;
	ll sq = fpow(x, p / 2);
	sq *= sq;
	sq %= mod;
	if (p & 1)
		sq *= x;
	return sq % mod;
}
ll solve(int idx, int rem) {
	if (rem < 0) return 0;
	if (!rem)
		return fpow(2, n - (ll)idx);
	if (idx == n) return 0;
	ll& ret = mem[idx][rem];
	if (ret != -1) return ret;
	ret = 2 * solve(idx + 1, rem) + solve(idx + 1, rem - v1[idx]);
	ret %= mod;
	return ret;
}
int main() {
//	file();
	fast();
	memset(mem, -1, sizeof mem);
	cin >> n >> s;
	v1 = vi(n);
	for (auto& it : v1) cin >> it;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		//watch(solve(i + 1, s - v1[i]));
		ans += fpow(2, i) * solve(i + 1, s - v1[i]);
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 74584
#include<iostream>
using namespace std;
int main()
{
  int N,K,X,Y,i,sum;
  cin>>N>>K>>X>>Y;
  if(N>=K)
    {
  for(i=1;i<=K;i++)
    {
      sum =sum + X;
    }
  for(;i>K && i<=N;i++)
    {
      sum=sum + Y;
    }
    }else{
    for(i=1;i<=N;i++)
      {
        sum=sum+X;
          }
  }
  cout<<sum<<endl;
  return 0;
    }

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i,n) for(int i = 0; i < n; i++)
#define for1(i,n) for(int i = 1; i <= n; i++)
#define ford(i,n) for(int i = n-1; i >= 0; i--)
#define fore(i,a,b) for(int i = a; i <= b; i++)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
 
 
const  int MAXn= 3e5+5;
const  long long INF= 1e18;
const long long mod= 1e9+7;
 
 
int main(){
	ll n;
	cin >> n;
	if(n & 1) cout << 0;
	else {
	ll ans = 0;
	for(ll den = 10; n >= den; den *= 5) {
		ans += n / den;
	}
	cout << ans;
}
}
	


Measured memory_bytes: 384
n, m = map(int, input().split())
a = list(map(int, input().split()))

cum = [0]
for i in range(n):
    cum.append(cum[-1] + a[i])

cum_mod = []
for val in cum:
    cum_mod.append(val % m)

from collections import Counter

ctr = Counter(cum_mod)

ans = 0
for v in ctr.values():
    ans += v*(v-1)//2
print(ans)


Measured memory_bytes: 63896
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 998244353

using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int X, N; cin >> X >> N;
	map<int,bool> p;
	for (int i = 0; i < N; i++) {
		int a; cin >> a;
		p[a] = true;
	}
	int ans = 10000,sa=10000;
	for (int i = -100; i <= 1000; i++) {
		if (p[i]) continue;
		if (abs(i - X) < sa) {
			sa = abs(i - X);
			ans = i;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3676
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


class UnionFind:
    # Reference: https://note.nkmk.me/python-union-find/
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)


def main():
    N, M = map(int, readline().split())
    P = [int(s) - 1 for s in readline().split()]
    XY = map(int, read().split())

    uf = UnionFind(N)
    for x, y in zip(*[iter(XY)] * 2):
        uf.union(x - 1, y - 1)

    ans = 0
    for i, p in enumerate(P):
        if i == p or uf.same(i, p):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 30416
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;

class Prog
{
    public Prog() { }
    public static int Main()
    {
        new Prog().calc();
        return 0;
    }

    Scanner cin;
    long SQRX = 100000;

    public void calc()
    {
        cin = new Scanner();
        long X = cin.nextLong();
        long n = 1;

        while(n <= SQRX)
        { 
            if (n * (n + 1) / 2 >= X) break;
            n++;
        }

        Console.WriteLine(n);
        Console.Read();
    }
}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];  
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

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

#include <boost/math/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;

int main(void) {
    int N;
    mp::cpp_int ans = 1;
    mp::cpp_int T;

    cin >> N;
    for(int i=0;i<N;i++) {
        cin >> T;
        ans = boost::math::lcm(ans,T);
    }

    cout << ans << "\n";
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  int ans=0;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      ans+=(4*i+7*j==n);
    }
  }
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
// failed to generate code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> P1;
typedef pair<P, P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i, x) for (long long i = 0; i < x; i++)
#define repn(i, x) for (long long i = 1; i <= x; i++)
#define SORT(x) sort(x.begin(), x.end())
#define ERASE(x) x.erase(unique(x.begin(), x.end()), x.end())
#define POSL(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin())
#define POSU(x, v) (upper_bound(x.begin(), x.end(), v) - x.begin())

vector<vector<ll>> dp(3001, vector<ll>(3001, -1));

ll n;
vector<ll> a(3001);

ll rec(ll i, ll j) {
    if (dp[i][j] != -1) return dp[i][j];
    if (i == j) return dp[i][j] = a[i];
    return dp[i][j] = max(a[i] - rec(i + 1, j), a[j] - rec(i, j - 1));
}

int main() {
    cin >> n;
    rep(i, n) cin >> a[i];

    cout << rec(0, n - 1) << endl;
}


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

using namespace std;
int main()
{
	long long l[100001];
	long long Ans[4];
	int s = 0;

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> l[i];
	}

	sort(l, l + N);
	reverse(l, l + N);

	Ans[s] = l[0];
	
	for (int i = 1; i < N; i++) {
		if (Ans[s] == l[i]) {
			s++;
			Ans[s] = l[i];
			s++;
			Ans[s] = l[i + 1];
			i++;
		}
		else {
			Ans[s] = l[i];
		}
	}

	if (Ans[0] == Ans[1] && Ans[2] == Ans[3]) {
		cout << Ans[0] * Ans[2];
	}
	else cout << 0;

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define add push_back
#define f first
#define s second
#define pw(x) (1ll << (x))
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
const ll INF = (ll)1e9 + 2019;

const int N = 2e5 + 10;
int arr[N], t[N * 4], nl[N], nr[N];

int query(int v, int l, int r, int a, int b) {
	if (a > r || l > b) {
		return -INF;
	}
	if (a <= l && r <= b) {
		return t[v];
	}
	int m = (l + r) / 2;
	return max(query(v * 2, l, m, a, b), query(v * 2 + 1, m + 1, r, a, b));
}

void update(int v, int l, int r, int p, int x) {
	if (l == r) {
		t[v] = x;
		return;
	}
	int m = (l + r) / 2;
	if (p <= m) {
		update(v * 2, l, m, p, x);
	} else {
		update(v * 2 + 1, m + 1, r, p, x);
	}
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

void mane() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	memset(t, -1, sizeof(t));
	for (int i = 0; i < n; i++) {
		nl[i] = query(1, 0, n, 0, arr[i] - 1);
		update(1, 0, n, arr[i], i);
	}
	for (int i = 0; i < N * 4; i++) {
		t[i] = -n;
	}
	for (int i = n - 1; i >= 0; i--) {
		nr[i] = -query(1, 0, n, 0, arr[i] - 1);
		update(1, 0, n, arr[i], -i);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ans += (ll)arr[i] * (i - nl[i]) * (nr[i] - i);
		//cerr << i << " " << nl[i] << " " << nr[i] << endl;
	}
	cout << ans;
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	mane();
#ifdef flaax
	cout << endl; cerr << endl << "\t" << fixed << setprecision(12) << (ld)clock() / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

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

typedef vector<int> 	vi;
typedef vector<vi>		vvi;
typedef long long int	ll;

int main(){

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

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

	vi flips;
	int c;
	for(int i = 1; i <= n; i++){
		if(i >= k){
			c = 0;
			flips.push_back(c);
			continue;
		}
		
		double c_ = log2(k / (double)i);
		c = 1 + (int)c_;
		if(c > 0 && pow(2, c - 1) >= k / (double)i)
			c--;
		flips.push_back(c);
	}

	
	ll num = 0;
	ll f_max = *max_element(flips.begin(), flips.end());
	for(int flip : flips){
		num += pow(2, f_max - flip);
	}
	double ans = num / ((double)pow(2, f_max) * n);
	printf("%.13lf", ans);

	return 0;
}

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


int main()
{	
	int n,a;
	list<int>v;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a;
		if(i%2)v.push_front(a);
		else v.push_back(a);
	}
	if((n-1)%2==0)reverse(v.begin(),v.end());
	for(auto i=v.begin();i!=v.end();i++) 
	{
		if(i==v.begin())cout<<*i;
		else cout<<" "<<*i;
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 8448
#include<bits/stdc++.h>
using namespace std;
int n;
int a[104];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	int mx=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j)
			{
				if(a[i]-a[j]>mx) mx=a[i]-a[j];
			}
		}
	}
	cout<<mx<<endl;
    return 0;
}


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

int n;
int a[85];
long long stocks = -1, cur = 1000, ans;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	for (int i = 1; i < n; i++) {
		ans = max(cur, ans);
		if (stocks == -1) {
			if (a[i - 1] < a[i]) {
				stocks = cur / a[i - 1];
				cur = cur % a[i - 1];
			}
		} else {
			if (a[i - 1] > a[i]) {
				cur += stocks * a[i - 1];
				stocks = -1;
			}
		}
		ans = max(cur, ans);
	}
	if (stocks != -1) cur += stocks * a[n - 1];
	ans = max(cur, ans);
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3820
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
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,k;cin >> n >>k;
    ll a,b,c;cin >>a >> b >>c;
    ll ans=0;
    string s;
    cin >> s;
    rep(i,n){
        if(s[i]=='r'){
            if(i-k<0||(i-k>=0&&s[i-k]!='r')){
                ans+=c;
            }
            else s[i]='x';
        }
        if(s[i]=='s'){
            if(i-k<0||(i-k>=0&&s[i-k]!='s')){
                ans+=a;
            }
            else s[i]='x';
        }
        if(s[i]=='p'){
            if(i-k<0||(i-k>=0&&s[i-k]!='p')){
                ans+=b;
            }
            else s[i]='x';
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

//#include "atcoder/all"
//using namespace atcoder;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	string s, t;
	cin >> n >> s >> t;
	rep(i,n){
		bool ok = true;
		for(int j = i; j < n; ++j){
			if(s[j] != t[j-i]) ok = false;
		}
		if(ok){
			cout << n+i << endl;
			return 0;
		}
	}
	cout << 2*n << endl;
	return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int co;
int n,m;
int x[8][8];
int bend;
void dfs(int a,int b){
  /*/
  for(int i=0;i<n;i++){
    if(1<<i&b)cout << 1;
    else cout << 0;
  }
  cout << endl;
  /*/
  if(b==bend){
    co++;
    return;
  }
  /*/
  cout << a+1 << endl;
  /*/
  for(int i=0;i<n;i++){
    if(x[a][i]){
      if(1<<i&b)continue;
      b+=1<<i;
      dfs(i,b);
      b-=1<<i;
    }
  }
}
int main(){
  cin >> n >> m;
  for(int i=0;i<n;i++){
    bend+=1<<i;
  }
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    x[a][b]=1;
    x[b][a]=1;
  }
  dfs(0,1);
  cout << co << endl;
}

Measured memory_bytes: 256
//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);
const long double PI=3.14159265358979;

// Required random number generators

// mt19937 gen_rand_int(chrono::steady_clock::now().time_since_epoch().count());
// mt19937_64 gen_rand_ll(chrono::steady_clock::now().time_since_epoch().count());

//Required Functions

ll power(ll x,ll y) 
{ 
    if (y == 0) 
        return 1; 
    ll p = power(x, y/2) % MOD; 
    p = (p * p) % MOD; 
  
    return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

int main()
{
    #ifndef ONLINE_JUDGE
    if (fopen("INPUT.txt", "r"))
    {
        freopen ("INPUT.txt" , "r" , stdin);
        //freopen ("OUTPUT.txt" , "w" , stdout);
    }
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    clock_t clk;
    clk = clock();
//-----------------------------------------------------------------------------------------------------------//

    string S,T;
    cin>>S>>T;
    ll N=S.length();
    ll ans=0;
    FORI(i,0,N)
    {
        if(S[i]!=T[i])
        {
            ans++;
        }
    }
    cout<<ans<<endl;

//-----------------------------------------------------------------------------------------------------------//


    clk = clock() - clk;
    cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << endl;

    return 0;
}

Measured memory_bytes: 3976
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;

int t, n;

int main(){
	REP(i, 4){
		cin >> t >> n;
		if (t == 1)cout << 6000 * n << endl;
		else if (t == 2)cout << 4000 * n << endl;
		else if (t == 3)cout << 3000 * n << endl;
		else cout << 2000 * n << endl;
	}
}

Measured memory_bytes: 1160
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
def main():
    N = int(input())
    S = {}
    
    for i in range(N):
        tmp = input()
        if tmp in S:
            S[tmp] += 1
        else:
            S[tmp] = 1
            
    M = int(input())
    for i in range(M):
        tmp = input()
        if tmp in S:
            S[tmp] -= 1
        else:
            S[tmp] = -1
            
    ans = 0
    for v in S.values():
        if ans < v:
            ans = v
    
    print(ans)
    
	
if __name__ == "__main__":
	main()


Measured memory_bytes: 38384
# -*- coding: utf-8 -*-
n=int(input())
W=list(map(int,input().split()))
t=0
while sum(W[:t])<sum(W[t:]) and t<n:
  t=t+1
print(min(abs(sum(W[:t])-sum(W[t:])),abs(sum(W[:t-1])-sum(W[t-1:]))))

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


flag=True
for i in range(len(A)):
    if A[i]%2==0:
        if (A[i]%3)*(A[i]%5)!=0:
            print('DENIED')
            flag=False
            break
if flag:
    print('APPROVED')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 1, i##_end_ = (n); i <= i##_end_; ++i)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

ll n, sum;

void check(ll x) {
    ll m = x - 1, d = n / x;
    if(d < m) sum += m;
}

int main() {
    cin >> n;
    for(ll i = 1; i * i <= n; ++i) if(n % i == 0) {
        check(i);
        if(i != n / i) check(n / i);
    }
    printf("%lld\n", sum);
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

struct UFTree {
private:
	vector<int> mNode;
	vector<int> mRank;

public:
	UFTree(int n) : mNode(n), mRank(n)
	{
		for (int i = 0; i < n; i++) {
			mNode[i] = i;
		}
	}

	int find(int x)
	{
		if (mNode[x] == x) {
			return x;
		}
		else {
			mNode[x] = find(mNode[x]);
			return mNode[x];
		}
	}

	void unite(int x, int y)
	{
		int idxX = find(x);
		int idxY = find(y);

		if (idxX == idxY) {
			return;
		}

		if (mRank[idxX] > mRank[idxY]) {
			mNode[idxY] = idxX;
		}
		else {
			mNode[idxX] = idxY;
			if (mRank[idxX] == mRank[idxY]) {
				mRank[idxY]++;
			}
		}
	}

	bool isSameSet(int x, int y)
	{
		return find(x) == find(y);
	}
};


int main()
{
	int N, M;
	cin >> N >> M;

	vector<pair<int, int>> e(M);
	for (auto i = 0; i < M; ++i)
	{
		cin >> e[i].first >> e[i].second;
		--e[i].first;
		--e[i].second;
	}

	int ans = 0;
	for (auto i = 0; i < M; ++i)
	{
		UFTree t(N);
		for (auto j = 0; j < M; ++j)
		{
			if (i != j)
			{
				t.unite(e[j].first, e[j].second);
			}
		}

		auto p = t.find(0);
		for (auto j = 1; j < N; ++j)
		{
			if (p != t.find(j))
			{
				++ans;
				break;
			}
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*n
		self.rank = [0]*n
		self.cycle = [False]*n

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			self.cycle[x] = True
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.cycle[x] |= self.cycle[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.cycle[y] |= self.cycle[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)
	
	#サイクルは各連結成分に一つまで
	def isSafe(self, x, y):
		cx = self.cycle[self.find(x)] 
		cy = self.cycle[self.find(y)]
		return not((self.isSame(x,y) and (cx or cy)) or (cx and cy))

n,h,w,*l = map(int,open(0).read().split())
cards = sorted([(a,r-1,c-1) for r,c,a in zip(*[iter(l)]*3)])[::-1]
uf = UnionFind(h+w)
ans = 0

for a,r,c in cards:
	c += h
	if uf.isSafe(r,c):
		uf.unite(r,c)
		ans += a
print(ans)

Measured memory_bytes: 36940
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define int long long
#define str string
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define all(x) x.begin(),x.end()
signed main(){
  int A,B,C,N,K;
  str S,W,T;
  cin>>N>>S;
  cin>>K;
  rep(0,N){
    if(S.at(K-1)!=S.at(i)){
      S.at(i)='*';
    }

  }
      cout<<S<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
using namespace std;
int main(){
  int a,b;
  char op;
  cin >> a >> op >> b;
  while(op!='?'){
    int c;
    if(op=='+') c=a+b;
    if(op=='-') c=a-b;
    if(op=='*') c=a*b;
    if(op=='/') c=a/b;
    cout << c << endl;
    cin >> a >> op >> b;
  }
  return 0;
}


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main()
{
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a - c >= 0 && a - c <= d)
	{
		cout << "Yes\n";
	}
	else if (c - a >= 0 && c - a <= d)
	{
		cout << "Yes\n";
	}
	else if (a - b >= 0 && a - b <= d)
	{
		if (b - c >= 0 && b - c <= d)
		{
			cout << "Yes\n";
		}
		else if (c - b >= 0 && c - b <= d)
		{
			cout << "Yes\n";
		}
		else
		{
			cout << "No\n";
		}
	}
	else if (b - a >= 0 && b - a <= d)
	{
		if (b - c >= 0 && b - c <= d)
		{
			cout << "Yes\n";
		}
		else if (c - b >= 0 && c - b <= d)
		{
			cout << "Yes\n";
		}
		else
		{
			cout << "No\n";
		}
	}
	else
	{
		cout<<"No\n"; 
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((int)1e9 + 5)
#define MAXL ((ll)1e15 + 5)
#define MAX_X ((int)1e5 + 2)
#define pi (2.0*acos(0))
#define M ((int)1e6 + 7)
//#define MOD ((int)998244353 + 0)
#define NN ((int)1e5 + 7)
#define N ((int)5e3 + 7)
#define eps (0)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define logn 29
#define endl "\n"
#define mp make_pair
//#define int ll


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;

/*fast io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/




typedef tree < pair < int, pair < int, int > >,  null_type,  less < pair < int, pair < int, int > > >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).

int dpp[105][105];

string str[105];

int cost(int r , int c , int tor , int toc)
{
    int cnt = 0;
    if(str[r][c]=='#') cnt = -1;
    int sgnr = 1 , sgnc = 1;
    if(c==toc) sgnc = 0;
    else sgnr = 0;
    tor++;
    toc++;
    int prer = r , prec = c;
    while(1){
        r += sgnr;
        c += sgnc;
        if(r==tor || c==toc){
            if(str[prer][prec]=='#') cnt++;
            break;
        }
        else{
            if(str[r][c]=='.' && str[prer][prec]=='#') cnt++;
        }
        prer = r , prec = c;
    }
    return cnt;
}

int call(int row , int col, int n , int m)
{
    if(row>n || col>m) return MAX;
    if(row==n && col==m) return 0;
    if(dpp[row][col]!=-1) return dpp[row][col];
    int ans = MAX;
    for(int i = row+1; i<=n; i++){
        ans = min(ans , call(i,col,n,m) + cost(row,col,i,col));
    }
    for(int i = col+1; i<=m; i++){
        ans = min(ans , call(row,i,n,m) + cost(row,col,row,i));
    }

    return dpp[row][col] = ans;
}

int main()
{
    fastio;
    int n , m;
    cin>>n>>m;
    for(int i = 1; i<=n; i++){
        cin>>str[i];
        str[i] += ".";
        for(int j = m; j>0; j--) str[i][j] = str[i][j-1];
        //cout<<str[i]<<endl;
    }
    memset(dpp,-1,sizeof dpp);
    cout<<call(1,1,n,m)+(str[1][1]=='#')<<endl;
    return 0;
}


Measured memory_bytes: 384
function Main(input) {
	input = input.split("\n")
	const tmp = input[0].split(" ")

	const a = parseInt(tmp[0], 10)
	const b = parseInt(tmp[1], 10)

	console.log((a * b) % 2 ? "Yes" : "No")
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"))


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

int main(void){
  int sum = 0, p, n, cnt = 0;
  double ave = 0.0;
  while(scanf("%d,%d", &p, &n) != EOF){
    sum += p * n;
    cnt++;
    ave += n;
  }
  ave /= cnt;
  cout << sum << endl;
  cout << (int)(ave + 0.5) << endl;
  return 0;
}

Measured memory_bytes: 1204
#include <iostream>
#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 true;
    return false;
}

void solve(std::string S){
    int ans = 0;
    int count = 0;
    REP(i, S.size()) {
        if (S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T') count++;
        else count = 0;
        chmax(ans, count);
    }
    cout << ans << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
using namespace std;
 
int main()
{
    map<int,int>m;
    int n,r;
    cin>>n;
    for(int j=1;j<=100;j++)
    {
        for(int k=1;k<=100;k++)
        {
            for(int h=1;h<=100;h++)
            {
                r=(j*j)+(k*k)+(h*h)+(j*k)+(k*h)+(j*h);
                m[r]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        cout<<m[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 5236
#include<stdio.h>

int main()
{
    int n, i, ans=1, j=1;

    scanf("%d", &n);

    int P[n+2];

    for(i=1; i<=n ; i++){
        scanf("%d", &P[i]);
        if(i != P[i]){
            if(j==3){
                ans=0;
                break;
            }
            j++;
        }
    }

    if(ans)
        printf("YES\n");
    else
        printf("NO\n");

    return 0;
}



Measured memory_bytes: 1612
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
typedef long double ld;
typedef pair<int,int> P;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0L)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 10*10
#define EPS 1e-9

//----***パーツ***----
#define fr first
#define se second

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);cerr<<fixed<<setprecision(15);};}initial_;

signed main(){
  int N;cin>>N;
  vector<int> v(N);
  REP(i,0,N){
    cin>>v[i];
  }
  int ans=100000000000;
  REP(i,-100,101){
    int tmp=0;
    REP(j,0,N){
      tmp+=(v[j]-i)*(v[j]-i);
    }
    ans=min(tmp,ans);
  }
  print(ans)


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
 
int main() {
  long long int L, R;
  cin >> L >> R;
  
  R = min(R, L+2019);
  
  long long int result = INF;
  for (long long int i=L; i<R; i++) {
    for (long long int j=i+1; j<=R; j++) {
      result = min((i * j) % 2019, result);
    }
  }
  
  cout << result << endl;
  
  return 0;
}

Measured memory_bytes: 256
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=200000+10;

int w[N],cnt[20],f[1<<15],sxor[1<<15];

int main() {
	int n=read();
	for (re int i=1;i<n;++i) {
		int u=read()+1,v=read()+1,val=read();
		w[u]^=val,w[v]^=val;
	}
	for (re int i=1;i<=n;++i) ++cnt[w[i]];
	int ans=0,s=0;
	for (re int i=1;i<=15;++i) ans+=cnt[i]/2,s|=(cnt[i]&1)<<(i-1);
	for (re int i=1;i<(1<<15);++i) f[i]=f[i>>1]+(i&1);
	for (re int i=1;i<(1<<15);++i) --f[i];
	for (re int i=1;i<(1<<15);++i)
		for (re int j=1;j<=15;++j)
			if (i&(1<<(j-1))) sxor[i]^=j;
	for (re int i=1;i<(1<<15);++i) {
		if (sxor[i]) continue;
		for (re int j=i&(i-1);j;j=(j-1)&i)
			if (!sxor[j]) f[i]=min(f[i],f[j]+f[i^j]);
	}
	printf("%d\n",ans+f[s]);
	return 0;
}


Measured memory_bytes: 896
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N, K;
	in >> N >> K;
	std::vector<LL>A(N), B(N);
	rep(i, N) in >> A[i] >> B[i];

	LL ans = 0;
	for (LL i = 30; i >= 0; --i)
	{
		if (K&(1LL << i)) //もしもKのibit目が1だったら
		{
            //max は ibit目より下が1で埋まっている
			LL max = (K ^ (1LL << i)) | ((1LL << i) - 1), res = 0;
			rep(j, N)//各A[j]について
			{
				bool flag = true;
				rep(k, 31)// k=0 ~ 30について
				{
                    // kbit目についてもしもA[j]が1なのに maxが0だったらだめ
					if ((A[j] & (1LL << k)) && !(max&(1LL << k)))
					{
						flag = false;
						break;
					}
				}
				if (flag) res += B[j];
			}
			ans = std::max(ans, res);
		}
	}
	LL res = 0;
	rep(i, N) //各A[i]について
	{
        //これは常にKのビットと比較する
		bool flag = true;
		rep(j, 31)//j=0~30 jビット目について考える 
		{
            //もしもA[i]のjビット目が1 かつ Kのjビット目が立っていなかったらだめ ORを取るから
			if ((A[i] & (1LL << j)) && !(K&(1LL << j)))
			{
				flag = false;
				break;
			}
		}
        //A[i]の各ビットは全てKに含まれる
		if (flag) res += B[i];
	}
	ans = std::max(ans, res);

	out << ans << std::endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(bool b) { return to_string(int(b)); }
string to_string(char b) { return "'" + string(1, b) + "'"; }
template <typename A, typename B>
string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A>
string to_string(A v) {
	string res = "{";
	for (const auto& x : v) res += (res == "{" ? "" : ", ") + to_string(x);
	return res + "}";
}
void debug() { cerr << endl; }
template <typename Head, typename... Tail>
void debug(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug(T...);
}
#define db(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define db(...) 42
#endif
typedef long long ll;
typedef long double ld;
char str[200005];
vector<int> zalgo(string s) {
	// Maintain max r such that there is l <= i <= r with [l,r] being prefix substring
	int n = s.size(), l = 0, r = 0;
	vector<int> z(n);
	z[0] = n;
	for (int i = 1; i < n; ++i) {
		if (i > r) {
			l = r = i;
			while (r < n && s[r - l] == s[r]) ++r;
			z[i] = r - l;
			--r;
		} else {
			if (z[i - l] <= r - i) z[i] = z[i - l];
			else {
				l = i;
				while (r < n && s[r - l] == s[r]) ++r;
				z[i] = r - l;
				--r;
			}
		}
	}
	return z;
}
int main() {
	scanf("%s", str);
	ll L, R;
	scanf("%lld%lld", &L, &R);
	int n = strlen(str) / 2;
	string s(str, str + n);
	string t = s;
	auto z = zalgo(s);
	for (int i = 1; i < n; ++i) {
		if (z[i] + i >= n) {
			t = s.substr(0, i);
			break;
		}
	}
	db(s, t);
	int m = t.size();
	if (n % m == 0) {
		auto solve = [&](ll r, char c) {
			ll full = 0;
			for (int i = 0; i < m; ++i) full += t[i] == c;
			ll ret = full * (r / m);
			for (int i = 0; i < r % m; ++i) ret += t[i] == c;
			return ret;
		};
		for (char c = 'a'; c <= 'z'; ++c) printf("%lld ", solve(R, c) - solve(L - 1, c));
	} else {
		auto solve = [&](ll r, char c) {
			vector<ll> len = {n, n + m}, numc(2);
			for (int i = 0; i < n; ++i) numc[0] += s[i] == c;
			numc[1] = numc[0];
			for (int i = 0; i < m; ++i) numc[1] += t[i] == c;
			for (int i = 2;; ++i) {
				len.push_back(0);
				numc.push_back(0);
				len[i] = len[i - 1] + len[i - 2];
				numc[i] = numc[i - 1] + numc[i - 2];
				if (len[i] >= 1e18) break;
			}
			ll ret = 0;
			for (int i = (int)len.size() - 1; i >= 0; --i) {
				if (r <= len[i]) continue;
				ret += numc[i];
				r -= len[i];
			}
			assert(0 <= r && r <= len[0]);
			for (int i = 0; i < r; ++i) ret += s[i] == c;
			return ret;
		};
		for (char c = 'a'; c <= 'z'; ++c) printf("%lld ", solve(R, c) - solve(L - 1, c));
	}
}


Measured memory_bytes: 4300
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int x = sc.nextInt();
      int[] m = new int[n];
      int min = 10000;
      for(int i = 0;i < n;i++){
        m[i] = sc.nextInt();
      	min = Math.min(min,m[i]);
        x -= m[i];
      }
      int s = (x/min);
      System.out.println(n+s);
    }
}

Measured memory_bytes: 22996
#include <stdio.h>

inline static int gl(void){
    int x = 0;
    for(;;){
        unsigned int c = getchar_unlocked() - 48;
        if(c < 10){
            x = x*10 + c;
        }else{
            break;
        }
    }
    return x;
}

typedef struct{
    int y;
    int x;
} pos_t;

char a[512];
short out[512*512][4];

int main(void){
    int h=gl(), w=gl();
    char haveCoin = 0;
    int pos = 0;
    short old_y, old_x;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            int t = getchar_unlocked() - 48;
            getchar_unlocked();
            a[j] = t;
        }
        if(i%2==0){
            for(int j=0; j<w; j++){
                if(haveCoin){
                    out[pos][0]=old_y+1;
                    out[pos][1]=old_x+1;
                    out[pos][2]=i+1;
                    out[pos][3]=j+1;
                    pos++;
                }
                haveCoin ^= a[j]&1;
                old_y = i;
                old_x = j;
            }
        }else{
            for(int j=w-1; j>=0; j--){
                if(haveCoin){
                    out[pos][0]=old_y+1;
                    out[pos][1]=old_x+1;
                    out[pos][2]=i+1;
                    out[pos][3]=j+1;
                    pos++;
                }
                haveCoin ^= a[j]&1;
                old_y = i;
                old_x = j;
            }
        }
    }
    printf("%d\n", pos);
    for(int i=0; i<pos; i++){
        printf("%d %d %d %d\n", out[i][0], out[i][1], out[i][2], out[i][3]);
    }
    return 0;
}


Measured memory_bytes: 2944
package main

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

var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024*1024), bufio.MaxScanTokenSize)
}

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

func nextFloat() float64 {
	sc.Scan()
	f, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

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

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

func main() {
	N := nextInt()
	var count int
	for i := 0; i < N; i++ {
		a := nextInt()
		b := nextInt()
		if a == b {
			count++
		} else {
			count = 0
		}
		if count >= 3 {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")
}


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

int main(){
  int sum=0;
  int k;
  cin >> k;
  for(int i=1;i<=k;i++)
    for(int j=1;j<=k;j++)
      for(int l=1;l<=k;l++)
        sum +=  __gcd(__gcd(i,j),l);
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
using namespace std;
#define INF 2000000007
#define LINF 100000000000000007
#define MOD 1000000007
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repb(i, n) for (int i = n - 1; i >= 0; i--)
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define ARDEB(i,X) cout<< #X <<"["<<i<<"]: "<<X[i]<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define ARDEB(i,X) {}
#define END {}
#endif
//typedef long long int ll;
typedef pair<int,int> P;
struct edge{int to,cost;};
int ceil2(int a,int b){if(a%b){return a/b+1;}else{return a/b;}}
int n,k,ans;
int a[222222];
signed main(){
	cin>>n>>k;
	rep(i,n)cin>>a[i];
	int ng=0,ok=1000000001;
	while(abs(ok-ng)>1){
		int mid=(ok+ng)/2;
		int sum=0;
		for(int i=0;i<n;i++){
			sum+=ceil2(a[i],mid)-1;
		}
		if(sum<=k)ok=mid;
		else ng=mid;
	}
	cout<<ok<<endl;
}

Measured memory_bytes: 5164