akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;
class Main{
	static final long MOD = 1_000_000_007; // 10^9+7
	static final int MAX = 2_147_483_646; // intMax 
	static final int INF = 1_000_000_000; // 10^9  
	public static void main(String[] args) throws Exception{
		hayami saori = new hayami();
		int n = saori.saori_hayami();
		long ans = 1L;
		long[] a = new long[n];
		for(int i = 0;i < n;i++){
			a[i] = saori.saorihayami();
			if(a[i] == 0){
				System.out.println(0);
				return;
			}
		}
		for(int i = 0;i < n;i++){
			if(ans > 1000000000000000000L/a[i]){
				System.out.println(-1);
				return;
			}
			ans *= a[i];
		}
		System.out.println(ans);
		saori.close();
	}
}

class hayami implements Closeable {
	private final InputStream in = System.in;
	private final byte[] hayami = new byte[1024];
	private int Hayami = 0;
	private int saori = 0;
	private boolean HayamiSaori() {
		if (Hayami < saori) {
			return true;
		}else{
			Hayami = 0;
			try {
				saori = in.read(hayami);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (saori <= 0) {
				return false;
			}
		}
		return true;
	}
	private int SaoriHayami() { 
		if (HayamiSaori()) {
            return hayami[Hayami++];
         }else{
             return -1;
         }
	}
	private static boolean hayami_saori(int hayami) { 
		return 33 <= hayami && hayami <= 126;
	}
	public boolean hayamisaori() { 
		while(HayamiSaori() && !hayami_saori(hayami[Hayami])) Hayami++; return HayamiSaori();
	}
	public String nextHayami() {
		if (!hayamisaori()) throw new NoSuchElementException();
		StringBuilder hayamin = new StringBuilder();
		int saori = SaoriHayami();
		while(hayami_saori(saori)) {
			hayamin.appendCodePoint(saori);
			saori = SaoriHayami();
		}
		return hayamin.toString();
	}
	public long saorihayami() {//nextLong
		if (!hayamisaori()) throw new NoSuchElementException();
		long hayami = 0;
		boolean misao = false;
		int saori = SaoriHayami();
		if (saori == '-') {
			misao = true;
			saori = SaoriHayami();
		}
		if (saori < '0' || '9' < saori) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= saori && saori <= '9') {
				hayami *= 10;
				hayami += saori - '0';
			}else if(saori == -1 || !hayami_saori(saori)){
				return misao ? -hayami : hayami;
			}else{
				throw new NumberFormatException();
			}
			saori = SaoriHayami();
		}
	}
	public int saori_hayami() {//nextInt
		long hayami = saorihayami();
		if (hayami < Integer.MIN_VALUE || hayami > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) hayami;
	}
	public double Hayamin() { //nextDouble
		return Double.parseDouble(nextHayami());
	}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
    }
    
}


Measured memory_bytes: 34164
N=int(input())
a=list(map(int,input().split()))
ans=[[0]*30 for _ in range(N)]

if sum(a)==0:
    print(' '.join(['0']*N))
    exit(0)

i=29

while i>=0:
    curbit=[aa%2 for aa in a]

    s=sum(curbit)

    if s%2==0:
        for j in range(N):
            ans[j][i]=curbit[j]
    else:
        for j in range(N):
            ans[j][i]=0 if curbit[j] else 1



    a=[aa//2 for aa in a]
    
    i-=1

print(' '.join([str(int(''.join([str(aaa) for aaa in aa]),2)) for aa in ans]))

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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define all(x) x.begin(),x.end() 
#define size(x) ll(x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

int main() {
  string s;
  cin >> s;
  int n = s.length();
  int cnt,ans = cnt = 0;
  rep(i,n) {
    if(s[i] == 'A' or s[i] == 'C' or s[i] == 'G' or s[i] == 'T') {
      cnt++;
      ans = max(ans,cnt);
    }else{
      cnt = 0;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3624
use std::io::{BufRead, stdin};

fn main() {
    let stdin = stdin();
    let mut stdin = stdin.lock();

    let mut s = String::new();
    stdin.read_line(&mut s).unwrap();
    let s = s.trim();

    let mut p = String::new();
    stdin.read_line(&mut p).unwrap();
    let p = p.trim();

    println!("{}",
        if (s.to_owned() + s).find(p).is_some() {
            "Yes"
        } else {
            "No"
        }
    )
}


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

using namespace std;

string f(const string &s) {
    string res;
    for (auto c:s) if (c != '0') res += c;
    return res;
}

int main() {
    string t = "AKIHABARA";
    int a[] = {0, 4, 6, 8};
    set<string> st;
    for (unsigned int bit = 0; bit < (1u << 4u); ++bit) {
        string tt = t;
        for (unsigned int j = 0; j < 4; ++j) {
            if (bit & (1u << j)) {
                tt[a[j]] = '0';
            }
            st.insert(f(tt));
        }
    }

    string s;
    cin >> s;
    if (st.find(s) != st.end()) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

#include <cmath>

#define int long long

using namespace std;

signed main() {
  int n;
  cin >> n;

  map<string, vector<string>> m;

  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;

    string t = s;
    sort(t.begin(), t.end());
    m[t].push_back(s);
  }

  int ans = 0;

  for (auto it = m.begin(); it != m.end(); it++) {
    int n = it->second.size();
    ans += n * (n - 1) / 2;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 25216
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h,w;
  while(cin >> h >> w && h||w){
    for(int i=0;i<h;i++){
	for(int j=0;j<w;j++) cout << "#";
	cout << endl;
      }
    cout << endl;
  }
}



Measured memory_bytes: 3076
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr ll INF = 1e16;

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

ll max(ll a, ll b) {return a < b ? b : a; }
ll min(ll a, ll b) {return a > b ? b : a; }
double maxf(double a, double b) { return a < b ? b : a; }

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

  if(s[2] == s[3] && s[4] == s[5]){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }

  return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
map<int,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		M[x]^=1;
	}
	int ret=0;
	FORR(r,M) ret+=r.second;
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 4992
#include<iostream>
#include<math.h>
#include<string>
#include<stack>/*** LIFO *** stack<type> var;
push(), top():to get data, pop():to remove, size(), empty() ***/
using namespace std;

#define Fp(I, STAT, END) for(int I = STAT; I < END; I++)
#define Fm(I, STAT, END) for(int I = STAT; I > END; I--)

int main(){
    int N, M;
    cin >> N >> M;
    int s, c, tmp[N] = {}, ans = 0, flag = 1;
    Fp(i, 0, M){
        cin >> s >> c;
        if(tmp[s - 1] == 0 || tmp[s - 1] == c){
            if(N != 1 && s == 1 && c == 0){
                cout << -1 << endl;
                return 0;
            }else{
                if(N == 1 && c == 0) flag = 0;
                tmp[s - 1] = c;
            }
        }else{
            cout << -1 << endl;
            return 0;
        }
    }
    Fp(i, 0, N) ans += tmp[i] * pow(10, N - i - 1);
    if((ans - pow(10, N - 1)) < 0 && flag && N != 1) ans += pow(10, N - 1);
    cout << ans << endl;
}


Measured memory_bytes: 256
package main

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

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

var sc = bufio.NewScanner(os.Stdin)

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

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

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

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

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func bitCount(bits int) int {

	bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555)
	bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333)
	bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f)
	bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff)
	return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff)
}

func rem(bs []int, num int) int {
	for i := 0; i < len(bs); i++ {
		if (bs[i] ^ num) < num {
			num ^= bs[i]
		}
	}
	return num
}

func solve() {
	N := getInt()
	a := make([]int, N)
	for i := 0; i < N; i++ {
		a[i] = getInt()
	}
	s := getString()

	b := make([]int, 0)
	for i := N - 1; i >= 0; i-- {
		if s[i] == '1' {
			if rem(b, a[i]) == 0 {
				continue
			}
			out(1)
			return
		} else {
			r := rem(b, a[i])
			if r == 0 {
				continue
			}
			b = append(b, r)
			for i := len(b) - 1; i > 0; i-- {
				if b[i] > b[i-1] {
					b[i], b[i-1] = b[i-1], b[i]
				}
			}
		}
	}
	out(0)
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, 1000000)
	T := getInt()
	for i := 0; i < T; i++ {
		solve()
	}
	//	out(1 << 62)
	// out(int(1e18))
}


Measured memory_bytes: 2684
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<utility>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pi acos(-1)
#define pb push_back
#define all(v) v.begin(),v.end()
using namespace std;
typedef pair<int,int> p;
typedef long long ll;

int main(){
	int x,y,z;
	cin>>x>>y>>z;
	if(x<(y+2*z))cout<<0<<endl;
	else{
		x-=(y+2*z);
		cout<<1+x/(y+z)<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
candy_map = []
candy_map.append(list(map(int, input().split())))
candy_map.append(list(map(int, input().split())))
dp = [[0] * n for _ in range(2)]
dp[0][0] = candy_map[0][0]
for i in range(1,n):
    dp[0][i] = dp[0][i-1] + candy_map[0][i]
dp[1][0] = dp[0][0] + candy_map[1][0]
for i in range(1,n):
    dp[1][i] = candy_map[1][i] + max(dp[0][i],dp[1][i-1])
print(dp[1][-1])


Measured memory_bytes: 9228
import sys
input = sys.stdin.readline


h, w, d = map(int, input().split())
num_to_x = [0] * (h*w+1)
num_to_y = [0] * (h*w+1)

for y in range(h):
    line = list(map(int, input().split()))
    for x, num in enumerate(line):
        num_to_x[num] = x
        num_to_y[num] = y

costs = [0] * (h*w+1)

for start in range(1, d+1):
    cost = 0
    num = start
    sx, sy = num_to_x[num], num_to_y[num]
    while num <= h*w:
        nx, ny = num_to_x[num], num_to_y[num]
        cost += abs(nx-sx) + abs(ny-sy)
        costs[num] = cost
        sx, sy = nx, ny
        num += d

q = int(input())

for _ in range(q):
    l, r = map(int, input().split())
    print(costs[r] - costs[l])

Measured memory_bytes: 9528
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    HashSet<String> hs = new HashSet<String>();
    for(int i = 0;i<n;i++){
      hs.add(sc.next());
    }
    int ans = hs.size();
    System.out.println(ans);

  }
}


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

constexpr int INF = 1e9;
int main() {
  int N, M, R; cin >> N >> M >> R;
  vi r(R);
  rep(i, R) {
    cin >> r[i]; --r[i];
  }

  vector<vi> edge(N, vi(N, INF));
  rep(i, M) {
    int a, b, c; cin >> a >> b >> c;
    --a, --b;
    edge[a][b] = edge[b][a] = c;
  }

  rep(k, N) rep(i, N) rep(j, N)
    edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);

  int ans = INF;
  sort(begin(r), end(r));
  do {
    int tmp = 0;
    rep(i, R-1)
      tmp += edge[r[i]][r[i+1]];
    ans = min(ans, tmp);
  } while (next_permutation(begin(r), end(r)));

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 384
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

a,b=map(int,input().split())
print(math.ceil(a/b))

Measured memory_bytes: 38384
a=raw_input()
b=raw_input()
ans='z'*51
for i in xrange(len(a) - len(b) + 1):
 w = False
 for j in xrange(len(b)):
  if a[j+i] != '?' and a[j+i] != b[j]:
   w = True
   break
 if w:
  continue
 res = ''
 for j in xrange(len(a)):
  if j >= i and j < i + len(b):
   res += b[j - i]
  elif a[j] == '?':
   res += 'a'
  else:
   res += a[j]
 ans = min(ans, res)
if len(ans) > 50:
 ans = 'UNRESTORABLE'
print ans

Measured memory_bytes: 29676
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <chrono>
#include <algorithm>

using namespace std;
using namespace std::chrono;

int N;
int ans[100001];
int coin[12] = {1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049};

void solve(int x) {
 for (int i=1; i<=x; i++) { // looking for solutions for i = x
   for (int j=0; j<=11; j++) { // testing all of the coins, since the "bottom level" has been verified.
     if (coin[j] <= i) {
       int subsol = ans[i-coin[j]] + 1;
       if (subsol < ans[i]) {
         ans[i] = subsol;
       }
     }
   }
 }

}

int main() {
  ans[0] = 0;
  for (int i=1; i<=100000; i++) {
    ans[i] = 10000;
  }
  cin >> N;
  
  solve(N);
  
  cout << ans[N];
  return 0;
}

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

dp = [[0 for _ in range(N)] for _ in range(N)]

for index in range(N):
    dp[index][index] = A[index]

for i in range(N - 2, -1, -1):
    for j in range(i + 1, N):
        l = A[i] - dp[i+1][j]
        r = A[j] - dp[i][j-1]
        dp[i][j] = max(l,r)

print(dp[0][N-1])


Measured memory_bytes: 119900
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MAXN = (int) 2e5;

int p[MAXN + 1];

struct Data {
    int sef;
    int nr0, nr1;
    bool operator <(const Data &other) const {
        if(1LL * nr0 * other.nr1 == 1LL * other.nr0 * nr1)
            return sef < other.sef;
        return 1LL * nr0 * other.nr1 > 1LL * other.nr0 * nr1;
    }
}v[MAXN + 1];

multiset <Data> mst;
multiset <Data> :: iterator it;

int myfind(int x) {
    if(v[x].sef == 0)
        return x;
    return v[x].sef = myfind(v[x].sef);
}

inline void myunion(int x, int y) {
    x = myfind(x);
    y = myfind(y);
    v[y].nr0 += v[x].nr0;
    v[y].nr1 += v[x].nr1;
    v[x].sef = y;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, x;
    ios::sync_with_stdio(false);
    cin >> n;
    for(i = 2; i <= n; i++) {
        cin >> p[i];
    }
    for(i = 1; i <= n; i++) {
        cin >> x;
        if(x == 0)
            v[i].nr0 = 1;
        else
            v[i].nr1 = 1;
        if(i > 1)
            mst.insert({i, v[i].nr0, v[i].nr1});
    }
    ll ans = 0;
    for(i = 1; i < n; i++) {
        it = mst.begin();
        mst.erase(mst.begin());
        int nod = myfind(p[it -> sef]);
        ans += 1LL * v[nod].nr1 * v[it -> sef].nr0;
        if(nod != 1)
            mst.erase(mst.find({nod, v[nod].nr0, v[nod].nr1}));
        myunion(it -> sef, nod);
        if(nod != 1)
            mst.insert({nod, v[nod].nr0, v[nod].nr1});
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 15872
use std::io::*;
use std::str::FromStr;

#[derive(Clone)]
struct Edge {
    dst: usize,
    id: usize,
}

type Graph = Vec<Vec<Edge>>;

fn dfs(graph: &Graph, v: usize, par: usize, pcolor: usize, colors: &mut Vec<usize>) {
    let mut color = 0;
    for edge in &graph[v] {
        if edge.dst == par {
            continue;
        }

        color += 1;
        if color == pcolor {
            color += 1;
        }

        colors[edge.id] = color;
        dfs(graph, edge.dst, v, color, colors);
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let n: usize = sc.next();
    let mut graph: Graph = vec![vec![]; n];
    for id in 0..(n - 1) {
        let u = sc.next::<usize>() - 1;
        let v = sc.next::<usize>() - 1;
        graph[u].push(Edge { dst: v, id: id });
        graph[v].push(Edge { dst: u, id: id });
    }

    let mut colors = vec![0; n - 1];
    dfs(&graph, 0, 0, 0, &mut colors);

    let &k = colors.iter().max().unwrap();
    println!("{}", k);

    for c in colors {
        println!("{}", c);
    }
}

/* ========== Scanner ========== */

struct Scanner<R: Read> {
    reader: R,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn read<T: FromStr>(&mut self) -> Option<T> {
        let token = self
            .reader
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            token.parse::<T>().ok()
        }
    }

    fn next<T: FromStr>(&mut self) -> T {
        if let Some(s) = self.read() {
            s
        } else {
            writeln!(stderr(), "Terminated with EOF").unwrap();
            std::process::exit(0);
        }
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.next()).collect()
    }

    fn char(&mut self) -> char {
        self.next::<String>().chars().next().unwrap()
    }
}


Measured memory_bytes: 14716
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000

struct Bitset{
	using ull = unsigned long long;
	vector<ull> b;
	int n;
	Bitset(int x){
		n = x;
		b.resize((n+63)/64,0);
	}
	
	int get(int x){
		return (b[x>>6]>>(x&63))&1;
	}
	
	void set(int x,int y){
		b[x>>6] |= 1ULL<<(x&63);
		if(!y)b[x>>6] ^= 1ULL<<(x&63);
	}
	
	Bitset &operator&=(const Bitset &another){
		rep(i,b.size()){
			b[i] &= another.b[i];
		}
		return (*this);
	}
	
	Bitset operator&(const Bitset &another)const{
		return (Bitset(*this)&=another);
	}
	
	Bitset &operator|=(const Bitset &another){
		rep(i,b.size()){
			b[i] |= another.b[i];
		}
		return (*this);
	}
	
	Bitset operator|(const Bitset &another)const{
		return (Bitset(*this)|=another);
	}
	
	Bitset &operator^=(const Bitset &another){
		rep(i,b.size()){
			b[i] ^= another.b[i];
		}
		return (*this);
	}
	
	Bitset operator^(const Bitset &another)const{
		return (Bitset(*this)^=another);
	}
	
	Bitset &operator>>=(int x){
		if(x&63){
			rep(i,b.size()-1){
				b[i] >>= (x&63);
				b[i] ^= (b[i+1]<<(64-(x&63)));
			}
			b.back() >>= (x&63);
		}
		
		x>>=6;
		rep(i,b.size()){
			if(i+x<b.size())b[i] = b[i+x];
			else b[i]=0;
		}
		return (*this);
	}
	
	Bitset operator>>(int x)const{
		return (Bitset(*this)>>=x);
	}
	
	Bitset &operator<<=(int x){
		if(x&63){
			for(int i=b.size()-1;i>=1;i--){
				b[i] <<= (x&63);
				b[i] ^= b[i-1]>>(64-(x&63));
			}
			b[0] <<= x&63;
		}
		
		x>>=6;
		for(int i=b.size()-1;i>=0;i--){
			if(i-x>=0)b[i] = b[i-x];
			else b[i] = 0;
		}
		return (*this);
	}
	
	Bitset operator<<(int x)const{
		return (Bitset(*this)<<=x);
	}
	
};

int main(){
	
	int N;
	cin>>N;
	
	vector<int> A(N);
	int S = 0;
	
	for(int i=0;i<N;i++){
		cin>>A[i];
		S += A[i];
	}
	
	
	Bitset B(4000001);
	B.set(0,1);
	
	for(int i=0;i<N;i++){
		B |= (B<<A[i]);
	}
	
	int k = (S+1)/2;
	
	for(int i=k;true;k++){
		if(B.get(k)){
			cout<<k<<endl;
			return 0;
		}
	}
 
	
	return 0;
}
 


Measured memory_bytes: 4848
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    W,H,x,y=MI()
    ans=(W*H)/2
    if x==W/2 and y==H/2:
        print(ans,1)
    else:
        print(ans,0)
    
    

main()


Measured memory_bytes: 61916
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
//#include <cassert>
//#include <array>
//#include <queue>
//#include <stack>
//#include <vector>
//#include <map>
//#include <set>
#include <unordered_map>
//#include <unordered_set>

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP1(i, n) for (int i = 1; i <= (int)(n); i++)

#define MAX 1000000007

using namespace std;

int combination(int n, int r) {
	if (r * 2 > n) r = n - r;
	int dividend = 1;
	int divisor = 1;
	long long ans = 1;
	for (unsigned int i = 1; i <= r; ++i) {
		ans *= (n - i + 1) % MAX;
		//divisor i
		while (ans % i != 0) {
			ans += MAX;
		}
		ans /= i;
		ans %= MAX;
	}
	return ans;
}

int N, M;
unordered_map<int, int> um;

void solve() {
	cin >> N >> M;

	int factor_max = floor(sqrt(M));
	for (int factor = 2; factor <= factor_max; factor++)
	{
		if (M%factor == 0) {
			um[factor]++;
			M /= factor;
			if (M == 1) {
				break;
			}
			else {
				factor--;
			}
		}
	}
	if (M != 1) {
		um[M]++;
	}

	unsigned long long ans=1;
	for (const auto &e : um) {
		ans *= combination(N - 1 + e.second,e.second);
		ans %= MAX;
	}

	cout << ans << endl;

	return;
}

int main() {
	solve();
	return 0;
}



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

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define gcd __gcd
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

const ll L = 1e5+5;

ll a[L], b[L], c[L];
ll ans[L][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    ll N;
    cin >> N;

    for(ll i=0; i<N; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
    }

    ans[0][0] = max(b[0], c[0]);
    ans[0][1] = max(a[0], c[0]);
    ans[0][2] = max(a[0], b[0]);

    for(ll i=1; i<N; i++)
    {
        ans[i][0] = max(ans[i-1][1]+a[i], ans[i-1][2]+a[i]);
        ans[i][1] = max(ans[i-1][0]+b[i], ans[i-1][2]+b[i]);
        ans[i][2] = max(ans[i-1][0]+c[i], ans[i-1][1]+c[i]);    
    }

    // for(ll i=0; i<N; i++)
    // {
    //     cout << ans[i][0] << " " << ans[i][1] << " " << ans[i][2] << endl;
    // }

    cout << max(ans[N-1][0], max(ans[N-1][1], ans[N-1][2])) << endl;

    return 0;
}

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

int main() {

	long long  s;
	scanf("%lld", &s);
	deque<int> deq;
	while(s > 0) {
		deq.push_front(s % 10);
		s = s / 10;
	}
	int ans = 1e9;
	int n = deq.size();
	for(int i = 0; i < n - 2; i++) {
		int a = abs((deq[i] * 100 + deq[i + 1] * 10 + deq[i + 2]) - 753);
		ans = min(a, ans);
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main(){

    int N, M;
    vector<vector<int>> dest;
    queue<int> next;
    next.push(0);

    cin >> N >> M;
    dest.resize(N);

    vector<bool> seen(N, false);
    vector<int> info(N, false);
    seen[0] = true;

    for (int i = 0; i < M; i++){
        int a, b;
        cin >> a >> b;
        dest[a - 1].push_back(b - 1);
        dest[b - 1].push_back(a - 1);
    }

    while(!next.empty()){
        int now = next.front();
        next.pop();

        for (int i = 0; i < dest[now].size(); i++){
            if(!seen[dest[now][i]]){
                seen[dest[now][i]] = true;
                next.push(dest[now][i]);
                info[dest[now][i]] = now + 1;
            }
        }
    }

    cout << "Yes" << endl;
    for (int i = 1; i < N; i++){
        cout << info[i] << endl;
    }
}

Measured memory_bytes: 10272
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;

typedef long long ll;

const ll INF = 1e18;
const int BIG = 1e9;
const int maxN = 100 * 1000 + 9;
const string FILENAME = "sample";

ll a, b, c, d;

void read(){
	cin >> a >> b >> c >> d;
}

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

ll lcm(ll a, ll b){
	return (a / gcd(a, b)) * b;
}

ll countDivisible(ll n, ll num0, ll num1){
	return n / num0 + n / num1 - n / lcm(num0, num1);
}

void solv(){
	ll ans = countDivisible(b, c, d);
	ans -= countDivisible(a - 1, c, d);
	ans = (b - a + 1) - ans;

	cout << ans << '\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
#ifdef h4h4
	freopen((FILENAME + ".inp").c_str(), "r", stdin);
	freopen((FILENAME + ".out").c_str(), "w", stdout);
#endif

	read();
	solv();

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define HEAP_SIZE 500500

int n;

void maxHeapfy(int *A, int i) {
  int largest;
  int left = 2*i;
  int right = 2*i+1;

  if (left <= n && A[left] > A[i]) {
    largest = left;
  } else {
    largest = i;
  }
  if (right <= n && A[right] > A[largest]) {
    largest = right;
  }

  if (largest != i) {
    int tmp;
    tmp = A[i];
    A[i] = A[largest];
    A[largest] = tmp;

    maxHeapfy(A, largest);
  }
}

void buildMaxHeap(int *A) {
  int i;
  for (i = n/2; i >= 1; i--) {
    maxHeapfy(A, i);
  }
}

int main(void) {
  int i;
  int A[HEAP_SIZE];
  scanf("%d", &n);
  for(i = 1; i <= n; i++) {
    scanf("%d", &A[i]);
  }

  buildMaxHeap(A);

  for (i = 1; i <= n; i++) {
    printf(" %d", A[i]);
  }
  putchar('\n');

  return 0;
}

Measured memory_bytes: 2556
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int main()
{
    double X,K,D;
    cin >> X >> K >> D;
    if(abs(X) >= K*D){
        cout << (ll)(min(abs(X + K*D), abs(X - K*D))+0.1) << endl;
    }else{
        ll k = abs(X)/D;
        ll nX = (ll)(min(abs(X + k*D), abs(X - k*D))+0.1);
        K -= k;
        if(0 == (ll)K%2){
            cout << nX << endl;
        }else{
            cout << (ll)abs(nX-(ll)D) << endl;
        }
    }
}

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

int main(){
  int N, M, T, temp, temp2[10010] = {}, count = 0;

  cin>>N>>M>>T;

  for(int i = 0; i < N; i++){
    cin>>temp;
    for(int j = temp - M + 1; (j <= temp + M )&& j <= T; j++ ){
      temp2[j] = 1;
    }
  }
  for(int i = 1; i <= T; i++){
    if(!temp2[i])count++;//cout<<temp2[i]<<endl;
  }

  cout<<count<<endl;
  
  return 0;
}



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

const int inf = 555555;

int main(){

  int n,m;

  cin >> n >> m;

  int coin[m];

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

  int dp[m+1][n+1];

  for(int i=0; i<n+1; i++){
    dp[0][i] = inf;
  }

  for(int i=1; i<m+1; i++){
    for(int j=0; j<n+1; j++){
      if(j < coin[i-1]){
        dp[i][j] = dp[i-1][j];
      }
      else{
        if(dp[i][j-coin[i-1]] == inf){
          dp[i][j] = 1;
        }else{
          dp[i][j] = min(dp[i-1][j] ,dp[i][j-coin[i-1]] + 1);
        }
      }
    }
  }

  cout << dp[m][n] << endl;

  return 0;
}

Measured memory_bytes: 7176
import sys
import numpy as np

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

H, W = lr()
A = np.array([lr() for _ in range(H)])
B = np.array([lr() for _ in range(H)])
diff = np.abs(A - B)

X = (H+W) * 80
L = X + X + 1 #真ん中を0とする、最後に-X
dp = [[None] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][X+diff[0][0]] = 1; dp[0][0][X-diff[0][0]] = 1 #非負整数のみでも良い
for h in range(H):
    for w in range(W):
        if h == 0 and w == 0:
            continue
        di = diff[h][w]
        x = np.zeros(L, np.bool)
        if h > 0:
            x[di:] |= dp[h-1][w][:L-di]
            x[:L-di] |= dp[h-1][w][di:]
        if w > 0:
            x[di:] |= dp[h][w-1][:L-di]
            x[:L-di] |= dp[h][w-1][di:]
        dp[h][w] = x

dp = dp[-1][-1][X:]
possible = np.where(dp==1)[0]
answer = possible.min()
print(answer)
#


Measured memory_bytes: 173488
import sys #sys.stdin.readline()
import heapq #heap
from collections import defaultdict
fastinp = lambda: sys.stdin.readline().split(' ')
inp = lambda: input().split(' ')
ml = lambda x, y=int: list(map(y, x))
debug = lambda *args: print(*args, sep=' | ')
n = int(inp()[0])
nums = ml(inp())
flag = True
for num in nums:
    if num%2 == 0:
        if num%3 == 0 or num%5 == 0:
            continue
        else:
            flag = False
            break
if not flag:
    print("DENIED")
else:
    print("APPROVED")


Measured memory_bytes: 3316
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;



int main()
{
	long long int i, j, k, l, m, n, sum, flag, N, M;
	sum = 0;
	flag = 0;
	cin >> N;
	if (N < 1200)
		cout << "ABC" << endl;
	else if (N < 2800)
		cout << "ARC" << endl;
	else
		cout << "AGC" << endl;



    return 0;
}



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

using namespace std;

int main(){
    const int64_t INF = 1e18;
    const int INF_INT = 1e9;
    int n, m, l;
    cin >> n >> m >> l;
    vector<vector<int64_t>> D(n + 1, vector<int64_t>(n + 1, INF));
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        D[a][b] = c;
        D[b][a] = c;
    }

    for (int i = 0; i <= n; i++)
        D[i][i] = 0;

    for (int k = 0; k <= n; k++){
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= n; j++){
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
    vector<vector<int>> DP(n + 1, vector<int>(n + 1, INF_INT));
    for (int i = 0; i <= n; i++){
        DP[i][i] = 0;
        for (int j = 0; j <= n; j++){
            if (D[i][j] <= l)
                DP[i][j] = 0;
        }    
    }

    for (int k = 0; k <= n; k++){
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= n; j++){
                DP[i][j] = min(DP[i][j], DP[i][k] + DP[k][j] + 1);
            }
        }
    }

    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int s, t;
        cin >> s >> t;
        cout << (DP[s][t] == INF_INT ? -1 : DP[s][t]) << endl;
    }
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
int main() {
  int ibingo[3][3];
  bool bingo[3][3];
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      bingo[i][j] = false;
    }
  }
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      cin >> ibingo[i][j];
    }
  }
  int N, b;
  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> b;
    for(int j = 0; j < 3; j++) {
      for(int k = 0; k < 3; k++) {
        if(b == ibingo[j][k]) bingo[j][k] = true;
      }
    }
  }
  for(int i = 0; i < 3; i++) {
    if(bingo[i][0] == bingo[i][1] && bingo[i][1] == bingo[i][2] && bingo[i][0] == true) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  for(int i = 0; i < 3; i++) {
    if(bingo[0][i] == bingo[1][i] && bingo[0][i] == bingo[2][i] && bingo[0][i] == true) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  if(bingo[0][0] == bingo[1][1] && bingo[1][1] == bingo[2][2] && bingo[0][0] == true) {
    cout << "Yes" << endl;
    return 0;
  }
  if(bingo[0][2] == bingo[1][1] && bingo[1][1] == bingo[2][0] && bingo[0][2] == true) {
    cout << "Yes" << endl;
    return 0;
  }
  cout << "No" << endl;
//////////////////////////////////////
  /*
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      cout << ibingo[i][j] << " ";
    }
    cout << endl;
  }
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      cout << bingo[i][j] << " ";
    }
    cout << endl;
  } 
  */
}

Measured memory_bytes: 3640
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n = in.nextInt();
		int q = in.nextInt();
		String s = in.next();
		int[] l = new int[q];
		int[] r = new int[q];
		for (int i = 0; i < q; i++) {
			l[i] = in.nextInt();
			r[i] = in.nextInt();
		}
		solve(s, l, r);
		in.close();
	}

	private static void solve(String s, int[] l, int[] r) {
		int[] c = new int[s.length() - 1];
		int ct = 0;
		for (int i = 0; i < s.length() - 1; i++) {
			if (s.charAt(i) == 'A' && s.charAt(i + 1) == 'C')
				ct++;
			c[i] = ct;
		}
		for (int i = 0; i < l.length; i++)
			solvePrint(c, l[i], r[i]);
	}

	private static void solvePrint(int[] c, int l, int r) {
		if (l == 1)
			System.out.println(c[r - 2]);
		else
			System.out.println(c[r - 2] - c[l - 2]);
	}
}

Measured memory_bytes: 92736
def a168(n):

    ans = ""
    aaa = n[-1]
    hon = [2,4,5,7,9]
    pon = [0,1,6,8]
    bon = [3]

    if int(aaa) in hon:
        ans = "hon"
    elif int(aaa) in pon:
        ans = "pon"
    else:
        ans = "bon"

    return ans

def main():
    n = list(str(input()))
    print(a168(n))

if __name__ == '__main__':
    main()

Measured memory_bytes: 9196
#include <bits/stdc++.h>
using namespace std;
int main(){
  int x,a,b; cin>>x>>a>>b;
  if(a>=b){
    cout<<"delicious"<<endl;
  }else if(b-a>x){
    cout<<"dangerous"<<endl;
  }else{
    cout<<"safe"<<endl;
  }
}


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

typedef long long ll;
typedef unsigned long long ull;

using S = pair<modint998244353, modint998244353>;
using F = pair<modint998244353, modint998244353>;

S op(S a, S b){ return S{a.first + b.first, a.second + b.second};}
S e(){ return S{0, 0};}
S mapping(F f, S x){ return S{f.first * x.first + f.second * x.second, x.second};}
F composition(F f, F g){ return F{f.first * g.first, f.first * g.second + f.second};}
F id(){ return F{1, 0};}

int main()
{
    ll N, Q;
    cin >> N >> Q;
    vector<S> A(N, S(0, 1));
    int Ai;
    for(int i=0;i<N;i++){
        cin >> Ai;
        A[i].first = Ai;
    }
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(A);

    ll t, l, r, b, c;
    vector<ll> res;
    for(int i=0;i<Q;i++){
        cin >> t >> l >> r;
        if(t == 0){
            cin >> b >> c;
            seg.apply(l, r, F{b, c});
        }else if(t == 1){
            res.push_back(seg.prod(l, r).first.val());
        }else{ abort();}
    }
    for(auto v : res) cout << v << endl;

    return 0;
}

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

ll k, a, b, c, ans;

int main() {
	scanf("%lld%lld%lld", &k, &a, &b);
	if (b - a <= 1 || k + 1 < a) printf("%lld\n", k + 1);
	else {
		ans = k + 1, c = a - 1, k -= c;
		ans = max(ans, (ll)(k / 2) * (b - a) + a + (k % 2));
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math;

void main()
{
    auto N = readln.chomp.to!int;
    wchar[][] MAP;
    MAP.length = N;
    foreach (ref line; MAP) {
        auto cs = readln.chomp.to!(wchar[]);
        line = cs ~ cs;
    }

    int cnt;
    foreach (o; 0..N) {
        void check() {
            foreach (i; 0..N) {
                foreach (j; i..N) {
                    if (MAP[i][o+j] != MAP[j][o+i]) return;
                }
            }
            ++cnt;
        }
        check();
    }
    writeln(cnt * N);
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x;
    cin>>x;
    int n1 = x/500;
    int n2 = ((x)-500*(x/500))/5;
    cout<<1000*1ll*(n1)+5*1ll*n2<<"\n";
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int N, int L)
        {
            if (L > 0)
            {
                return Enumerable.Range(L + 1, N - 1).Sum();
            }
            else if (L + N - 1 < 0)
            {
                return Enumerable.Range(L, N - 1).Sum();
            }
            else
            {
                return Enumerable.Range(L, N).Sum();
            }
        }
        static void Main(string[] args)
        {
            int[] V = ReadInts();
            Console.WriteLine(Solve(V[0], V[1]));
        }
    }
}


Measured memory_bytes: 11220
#include <iostream>

using namespace std;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	while (1) {
		c -= b;
		if (c <= 0) {
			cout << "Yes";
			break;
		}
		a -= d;
		if (a <= 0) {
			cout << "No";
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 3592
import java.io.*;
import java.util.*;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static Scanner sc = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int[] size; // size of subtree, including self
    List<Integer>[] graph;
    long[] dp,ans;
    final long mod = 1000000000+7;
    long[] frac,inv; // inv[i] = the inversion of i! mod M
    public static void main(String[] args) throws IOException {
        Main main = new Main();
//        main.solve();
//        out.flush();
        System.out.println(main.solve());
    }
    long solve() throws IOException{
        long n = sc.nextLong();
        if(n==2) return 1;
        long res1 = helper(n-1).size();
        Set<Long> set = helper(n);
        long res2 = 0;
        for(long div:set){
            // test whether k can be div
            long backup = n;
            while(backup%div==0) backup /= div;
            if(backup%div==1L) res2 ++;
        }
        return res1+res2;
    }
    Set<Long> helper(long n){
        // returns all the divisors except 1
        Set<Long> ans = new HashSet<>();
        for(long i=1;i*i<=n;i++){
            if(n%i==0){
                ans.add(i); ans.add(n/i);
            }
        }
        ans.remove(1L);
        return ans;
    }
}



Measured memory_bytes: 23892
#include<bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
   if(b==0) return a;
   else return gcd(b,a%b);
}
int main(void){
   int N;
   cin>>N;
   vector<long long> T(N);
   for(int i=0;i<N;i++){
      cin>>T[i];
   }
   long long ans=1;
   for(int i=0;i<N;i++){
      ans=ans/gcd(ans,T[i]);
      ans*=T[i];
   }
   cout<<ans<<endl;
   return 0;
}

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

#define PI 3.14159265

int main(void)
{
	double a, b, c, S, L, h;

	scanf("%lf", &a);
	scanf("%lf", &b);
	scanf("%lf", &c);
	c = c * PI / 180.0;

	h = sin(c) * b;
	S = a * h / 2;
	L = a + b + sqrt(a * a + b * b + (-2) * a * b * cos(c));

	printf("%.5lf\n", S);
	printf("%.5lf\n", L);
	printf("%.5lf\n", h);

	return 0;
}

Measured memory_bytes: 1968
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace A
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var xa = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            Console.WriteLine(xa[0] < xa[1] ? 0 : 10);
        }
    }
}


Measured memory_bytes: 13396
#include <iostream>

int main(){
  int n;
  int h[100];
  std::cin >> n;
  for(int i = 0; i < n; i++) std::cin >> h[i];

  int ret = 1;
  for(int i = 1; i < n; i++){
    bool can_see = true;
    for(int j = 0; j < i; j++){
      if(h[j] > h[i]){
        can_see = false;
        break;
      }
    }
    if(can_see)
      ret++;
  }

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


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
l=[-1]*20
a=0
t=-1
for i in range(N):
    for j in range(20):
        if (A[i]>>j)%2:
            if t<l[j]:
                t=l[j]
            l[j]=i
    a+=i-t
print(a)

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

t_zero = [-1] * N

t = 0
a = 1

while t_zero[a-1] == -1:
  if t == K:
    break
  t_zero[a-1] = t
  t += 1
  a = A[a-1]
else:
  k = (K - t_zero[a-1]) % (t - t_zero[a-1])
  for _ in range(k):
    a = A[a-1]
print(a)

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

int main() {
	int h, w;
	int c[10][10], a[200][200];
	cin >> h >> w;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			cin >> c[i][j];
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> a[i][j];

	for (int k = 0; k < 10; k++)
		for (int i = 0; i < 10; i++)
			for (int j = 0; j < 10; j++)
				c[i][j] = min(c[i][j], c[i][k] + c[k][j]);

	int ans = 0;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			if (a[i][j] != -1)
				ans += c[a[i][j]][1];

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

Measured memory_bytes: 384
# -*- coding: utf-8 -*-

s = input()[::-1]
w = [
    "dream"[::-1]
    ,"dreamer"[::-1]
    ,"erase"[::-1]
    ,"eraser"[::-1]
]

while len(s)>0:
    if s.startswith(w[0]):
        s = s[len(w[0]):]
    elif s.startswith(w[1]):
        s = s[len(w[1]):]
    elif s.startswith(w[2]):
        s = s[len(w[2]):]
    elif s.startswith(w[3]):
        s = s[len(w[3]):]
    else:
        break

if len(s)==0:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3188
#include<iostream>

using namespace std;

int main (){
int x;
  cin>>x;
  x %= 10;
  if(x == 3){
    cout<<"bon"<<endl;
  }else if((x==0)||(x==1)||(x==6)||(x == 8)){
    cout<<"pon"<<endl;
  }else{
    cout<<"hon"<<endl;
  }

  return 0;
}

Measured memory_bytes: 3636
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (c - (a - b) < 0) cout << 0 << endl;
	else cout << c - (a - b) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long a,b,x[10000],sum=0;
cin>>a>>b;
for(int i=0;i<a;i++)
{
    cin>>x[i];
}
sort(x,x+a);
for(int i=0;i<b;i++)
{
    sum+=x[i];
}
cout<<sum<<endl;
}


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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cerr<<v[i][j]<<" ";}cerr<<endl;}


typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
//const ll MOD = 1000000007;
const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { -1,0, 1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
// #define mp make_pair
//#define endl '\n'

void out(int x1, int y1, int x2, int y2, int x3, int y3) {
  cout << x1 << " " << y1 << " " << x2 << " " << y2 << " " << x3 << " " << y3 << endl;
}

int main() {
  ll s;
  cin >> s;
  ll x2 = sqrt(s);
  ll y1 = x2;
  if (x2 * y1 == s) {
    out(0, 0, 0, y1, x2, 0);
    return 0;
  }

  while (x2 * y1 < s) {
    x2++;
    if (x2 * y1 >= s) break;
    y1++;
  }

  ll diff = x2 * y1 - s;
  ll x1 = diff, y2 = 1;
  out(0, 0, x1, y1, x2, y2);
}


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

using namespace std;

int main()
{
  	int N, M, X;
  	cin >> N >> M >> X;
  	vector<int> A(M);
  	for(int i = 0; i < M; i++){
      	cin >> A.at(i);
    }
  	int c = 0;
  	for(int i = 0; A.at(i) < X; i++){
      	c++;
    }
  	cout << min(c, M - c);
  	return 0;
}

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

int main(){
	long n = 0;
	long b = 0, f = 0, r = 0, v = 0;
	long rn = 0, rn2 = 0;
	vector<long> a(120, 0);

	cin >> n;

	for (long i = 0; i < n; i++){
		cin >> b >> f >> r >> v;
		rn = (b - 1) * 30 + (f - 1) * 10 + (r - 1);
		a[rn] += v;
	}

	for (long i = 0; i < 4; i++){
		for (long j = 0; j < 3; j++){
			for (long k = 0; k < 10; k++){
				rn2 = i * 30 + j * 10 + k;
				cout << " " << a[rn2];
			}
			cout << endl;
		}
		if (i != 3){
			cout << "####################" << endl;
		}
	}
}

Measured memory_bytes: 1200