akhauriyash/Code-Regression huggingface dataset:
#include <valarray>
#include <cstdio>
using namespace std;
typedef valarray<int>V;
main(){
	int i,j,n,m,a,b,c,t;
	for(;scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&t),n;){
		V x(n*n);
		V e(n*n);
		V z(n*n);
		V s(n);
		x[0]=b;
		x[1]=c;
		e[0]=1;
		for(i=1;i<n-1;i++){
			x[i*n+i-1]=a;
			x[i*n+i]=b;
			x[i*n+i+1]=c;
			e[i*n+i]=1;
		}
		x[i*n+i-1]=a;
		x[i*n+i]=b;
		e[i*n+i]=1;
		for(;t;t>>=1){
			const V &_x=e;
			const V &_y=x;
			if(t&1){
				for(i=0;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=(_x[slice(i*n,n,1)]*_y[slice(j,n,n)]).sum()%m;
				e=z;
			}
			for(i=0;i<n;i++)for(j=0;j<n;j++)z[i*n+j]=(_y[slice(i*n,n,1)]*_y[slice(j,n,n)]).sum()%m;
			x=z;
		}
		for(i=0;i<n;i++)scanf("%d",&s[i]);
		const V &r=e;
		for(i=0;i<n-1;i++)printf("%d ",(r[slice(i*n,n,1)]*s).sum()%m);
		printf("%d\n",(r[slice(i*n,n,1)]*s).sum()%m);
	}
}

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

int main(){
    int n,m;
    cin >> n >> m;
    int vector2[100][100]={{}};
    int vector[100]={};
    rep(i,n){
        rep(j,m) cin >> vector2[i][j];
    }
    rep(i,m) cin >> vector[i];

    rep(i,n){
        int x=0;
        rep(j,m) x+=vector2[i][j]*vector[j];
        cout << x << endl;
    }
    return 0;
}


Measured memory_bytes: 3132
#include <cstdio>
#include <cstdlib>
#include <queue>

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

int main() {
  int i, j;
  P coords[90010];
  int cost[90010] = {};
  int H, W, D;
  scanf("%d %d %d", &H, &W, &D);
  int a;
  for (i = 0; i < H; i++) {
    for (j = 0; j < W; j++) {
      scanf("%d", &a);
      P xy = P(i, j);
      coords[a-1] = xy;
    }
  }
  /*for (i = 0; i < H*W; i++) {
    printf("(%d,%d) ", coords[i].first, coords[i].second);
    }*/
  int Q;
  scanf("%d", &Q);
  int L[100010], R[100010];
  for (i = 0; i < Q; i++) {
    scanf("%d %d", &L[i], &R[i]);
  }
  for (i = 0; i < D; i++) {
    for (j = D; j < H*W-i; j += D) {
      int dx = abs(coords[i+j].first - coords[i+j-D].first);
      int dy = abs(coords[i+j].second - coords[i+j-D].second);
      //printf("%d %d ", dx, dy);
      cost[i+j] = cost[i+j-D] + dx + dy;
    }
  }
  /*for (i = 0; i < H*W; i++) {
    printf("(%d,%d) ", coords[i].first, coords[i].second);
    printf("%d ", cost[i]);
    printf("\n");
    }*/
  for (i = 0; i < Q; i++) {
    int ans = cost[R[i]-1] - cost[L[i]-1];
    printf("%d\n", ans);
  }
  return 0;
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;

int main(){
    DRI(N);
    VI a;
    REP(i,3*N){
        DRI(x);
        a.PB(x);
    }
    sort(ALL(a));
    LL an=0;
    REP(i,N)an+=a[SZ(a)-i*2-2];
    cout<<an<<endl;
    return 0;
}


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

int main() {
  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  vector<int>B(N);
  for(int i=0;i<N;i++){
    B.at(A.at(i)-1)=i+1;
  }
  for(int i=0;i<N;i++){
    cout<<B.at(i)<<" ";
  }
  cout<< endl;
}
    


Measured memory_bytes: 1664
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

int main()
{
	int X, A, B;
	cin >> X >> A >> B;

	X = X - A;
	

	cout << X % B << endl;
	

	
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) x.begin(),x.end()
#define db(x) cout<<#x<<"="<<x<<endl
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF (1e9)
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;



void Main(){

  string S;
  cin>>S;

  string word={"dreamdreamereraseeraser"};

  bool where[2][23]={};
  int ct=0;
  where[0][22]=true;

  rep(i,S.length()){
    char c = S[i];

    rep(j,23){
      where[1-ct][j]=false;
    }

    rep(j,23){
      if(where[ct][j]==true){
        if(j==4 or j==11 or j==16){
          where[ct][22] = true;
        }

        if(j==22){
          if(c=='d'){
            where[1-ct][0]=true;
            where[1-ct][5]=true;
          }
          if(c=='e'){
            where[1-ct][12]=true;
            where[1-ct][17]=true;
          }
        }
        else if(word[j+1]==c){
          where[1-ct][j+1]=true;
        }
      }
    }
    ct=1-ct;
  }
  if(where[ct][4] or where[ct][11] or where[ct][16] or where[ct][22]){
    cout << "YES" <<"\n";
    return;
  }

  cout << "NO" <<"\n";
}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <functional>

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
inline int in(){ int x; scanf("%d",&x); return x;}

//----------union find------------------- begin
namespace UF {
#define MAX_N  10000
  int par[MAX_N], rank[MAX_N];

  void init(int n){
    int i;
    rep(i,n){ par[i] = i; rank[i] = 0;}
  }

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

  void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(rank[x] < rank[y]) par[x] = y;
    else {
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }

  bool same(int x, int y){ return find(x) == find(y);}
}
//--------------------------------------- end

struct Edge {
  int from, to, cost;

  Edge(int from_, int to_, int cost_){
    from = from_;
    to = to_;
    cost = cost_;
  }
  bool operator < (const Edge& a) const {
    return cost < a.cost;
  }
};

int main(){
  int i,j,k;
  int s,d;

  while(scanf("%d %d",&s,&d)){
    if(s == 0 && d == 0) break;
    vector<Edge> edges;

    rep(i,s) rep(j,d){
      int t = in();
      if(t == 0) continue;
      edges.push_back(Edge(i,s+j,t));
    }
    rep(i,d-1) for(j = i+1; j < d; j++){
      int t = in();
      if(t == 0) continue;
      edges.push_back(Edge(s+i,s+j,t));
    }

    //-------------begin here-----------
    sort(edges.begin(),edges.end());

    int ans = 0;
    int n = edges.size();
//    rep(i,n) cout << edges[i].cost << endl;
    UF::init(n);
    for(i = 1; i < s; i++) UF::unite(i,0);
    rep(i,n){
      if(UF::same(edges[i].from, edges[i].to)) continue;
      ans += edges[i].cost;
      UF::unite(edges[i].from, edges[i].to);
    }

    printf("%d\n",ans);
  }

  return 0;
}

Measured memory_bytes: 0
// Problem : E - Crested Ibis vs Monster
// Contest : AtCoder Beginner Contest 153
// URL : https://atcoder.jp/contests/abc153/tasks/abc153_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/coder3101/cp-editor)
#define arr v
#include<bits/stdc++.h>
using namespace std;
int main()
{
        int h,n;
        cin >> h >> n;
        vector<int> v(h+1,1e9+5);
        v[0]=0;
        for(int i=0;i<n;i++)
        {
                int de,cos;
                cin >> de >> cos;
                for(int j=0;j<=h;j++)
                {
                        if(j<=de)
                        v[j]=min(v[j],cos);
                        else
                        v[j]=min(v[j],v[j-de]+cos);
                        //cout << v[j+de] <<" ";
                }
                for(int j=h-1;j>=0;--j)
                {
                        arr[j]=min(arr[j],arr[j+1]);
                }
        }      
        cout << v[h] << endl;  
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#undef int
#define mk make_pair
#define pb push_back
typedef pair<int, int> pii;
const int mod = 1000000007;
const int INF = 1000000009;
const long long INFL = 1000000000000000018ll;

int N, M;
int tobari[100100];

int par[100100];

void init()
{
    for(int i = 0; i < N; i++){
        par[i] = i;
    }
}

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

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

void unite(int x, int y)
{
    x = root(x);
    y = root(y);
    if(x == y)return;
    if(x > y) par[x] = y;
    else par[y] = x;
}

signed main()
{
    cin >> N >> M;
    init();
    memset(tobari, -1, sizeof(tobari));
    for(int i = 0; i < N; i++){
        int K;
        cin >> K;
        for(int j = 0; j < K; j++){
            int a;
            cin >> a;
            if(~tobari[a]){
                unite(i, tobari[a]);
            }
            else{
                tobari[a] = i;
            }
        }
    }
    string ans = "YES";
    for(int i = 1; i < N; i++){
        if(!same(i, i - 1)){
            ans = "NO";
        }
    }
    cout << ans << endl;

    return 0;
}

/*



*/


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

typedef long long int ll;
typedef unsigned long long int ull;
#define rep(i,n) for(auto i=0;i<(n);i++)
#define rep1(i,n) for(auto i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()

using namespace std;


struct init{ init(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20); }; }aaaaaaa;



int main(){
  ll a, b;
  cin >> a >> b;

  ll x = 1;
  ll cnt = 0;
  while(x < b){
    x += a-1;
    cnt++;
  }

  cout << cnt << endl;


  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <ctype.h>

using namespace std;

int main () {
    char c;
    while (true) {
        scanf("%c", &c);

        if (isalpha(c)) {
            if (islower(c)) cout << (char)toupper(c);
            else cout << (char)tolower(c);
        } else cout << c;

        if (c == '\n') break;
    }
}


Measured memory_bytes: 3132
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(p, q):
    t, a = q
    pt, pa = p

    nt = max((pt - 1) // t + 1, 1)
    na = max((pa - 1) // a + 1, 1)

    n = max(nt, na)

    return (n * t, n * a)


def main():
    N = int(input())
    p = (1, 1)
    for _ in range(N):
        q = read_list()
        p = f(p, q)
    
    print(sum(p))


if __name__ == "__main__":
    main()



Measured memory_bytes: 3064
#include <iostream>
#include <cstdlib>

int main(void) {
  int N, M, X;
  int *A;
  int costL=0, costR=0;
  bool flag=true;
  int j, k;
  std::cin >> N >> M >> X;
  A = (int *) malloc(sizeof(int) * (M));
  for (int i=0;i < M;i++) {
    std::cin >> A[i];
    if ((A[i] > X) && (flag)) {
      j = i;
      flag=false;
    }
  }

  costL = j;
  costR = M - j;


  if (costL > costR) {
    std::cout << costR << std::endl;
  } else {
    std::cout << costL << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
moji = input()
flag = 0
answer = []

for i in range(0,len(moji)):
    if flag == 1:
        flag = 0
        continue
    if moji[i] == "2":
        answer.append("k")
    elif moji[i] == "3":
        answer.append("s")
    elif moji[i] == "4":
        answer.append("t")
    elif moji[i] == "5":
        answer.append("n")
    elif moji[i] == "6":
        answer.append("h")
    elif moji[i] == "7":
        answer.append("m")
    elif moji[i] == "8":
        answer.append("y")
    elif moji[i] == "9":
        answer.append("r")
    elif moji[i] == "0":
        i+=1
        flag = 1
        if moji[i] == "T":
            answer.append("wa")
        elif moji[i] == "D":
            answer.append("wo")
        elif moji[i] == "U":
            answer.append("nn")
    elif moji[i] == "T":
        answer.append("a")
    elif moji[i] == "L":
        answer.append("i")
    elif moji[i] == "U":
        answer.append("u")
    elif moji[i] == "R":
        answer.append("e")
    elif moji[i] == "D":
        answer.append("o")

for i in answer:
    print(i, end="")

print()



Measured memory_bytes: 5596
N,M=map(int,input().split())
A=[tuple(map(int,input().split())) for _ in range(N)]
B=[tuple(map(int,input().split())) for _ in range(M)]

for i in range(N):
  x,y=A[i]
  temp=10**9
  ans=1
  for j in range(M):
    X,Y=B[j]
    manhattan=abs(x-X)+abs(y-Y)
    if temp>manhattan:
      temp=min(temp,manhattan)
      ans=j+1
  else:
    print(ans)

Measured memory_bytes: 8996
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

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

    vector<ll> dp(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (ll j = 1; j * i <= n; j++) {
            dp[i * j]++;
        }
    }

    ll ans = 0;
    for (ll i = 1; i <= n; i++) {
        ans += (dp[i] * i);
    }
    cout << ans << endl;

}


Measured memory_bytes: 81380
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
/*bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
} */
int main()
{
     ll t,a,b,c;
     cin>>a>>b>>c;
     cout<<c<<" "<<a<<" "<<b<<endl;
}


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

int main(){
    ll n;
    cin>>n;
    vector<ll> vec(n+1,0);
    REP(i,n){
        vec[i]+=1;
        ll tmp = 2;
        while(i*tmp<=n){
            vec[i*tmp]+=1;
            tmp++;
        }
    }

    ll ans =0;
    REP(i,n){
        ans+=i*vec[i];
    }

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

Measured memory_bytes: 81396
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]==s[i+1]){
			cout<<i+1<<" "<<i+2;
			return 0;
		}
	}
	if(s.size()>=3){
		for(int i=0;i<s.size()-2;i++){
			if(s[i]==s[i+2]){
				cout<<i+1<<" "<<i+3;
				return 0;
			}
		}
	}
	cout<<-1<<" "<<-1;
	return 0;
}

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

int main() {
  int w, h, x, y, r;
  std::cin >> w >> h >> x >> y >> r;
  std::string ans = "No";

  if (x > 0 && x + r <= w) {
    if (y > 0 && y + r <= h) {
      ans = "Yes";
    }
  }

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



Measured memory_bytes: 3216
package main

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

var sc = bufio.NewScanner(os.Stdin)

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

}

type node struct {
	item int
	prev *node
}

func main() {
	sc.Split(bufio.ScanWords)
	var n, q int
	fmt.Scanf("%d %d", &n, &q)

	groups := make([]*node, n)
	for i := 0; i < n; i++ {
		groups[i] = &node{item: i, prev: nil}
	}

	for i := 0; i < q; i++ {
		com, x, y := next(), next(), next()
		if com == 0 {
			var parentX, parentY *node
			for parentX = groups[x]; parentX.prev != nil; parentX = parentX.prev {
				continue
			}
			for parentY = groups[y]; parentY.prev != nil; parentY = parentY.prev {
				continue
			}
			if parentX.prev != nil || parentY.prev != nil {
				panic(fmt.Sprintf("%v, %v", parentX, parentY))
			}
			if parentX.item != parentY.item {
				parentX.prev = parentY

			}

		} else {
			var parentX, parentY *node
			for parentX = groups[x]; parentX.prev != nil; parentX = parentX.prev {
				continue
			}
			for parentY = groups[y]; parentY.prev != nil; parentY = parentY.prev {
				continue
			}
			if parentX.item == parentY.item {
				fmt.Println("1")
			} else {
				fmt.Println("0")
			}
		}
	}

}



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

const int maxn(105);

int n, b[maxn], p[maxn], a[maxn], id[maxn];
vector <int> ans;

inline void Insert(int x, int v) {
	int i;
	if (a[n]) puts("-1"), exit(0);
	for (i = n; i > x; --i) a[i] = a[i - 1];
	a[x] = v;
}

inline int Cmp(int x, int y) {  return p[x] < p[y];  }

inline void Ins(int x) {
	int i;
	ans.push_back(x);
	if (a[n]) puts("-1"), exit(0);
	for (i = n; i > x; --i) a[i] = a[i - 1];
	a[x] = x;
}

int main() {
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; ++i) scanf("%d", &b[i]);
	if (b[1] != 1) return puts("-1"), 0;
	for (i = 1; i <= n; ++i) Insert(b[i], i);
	for (i = 1; i <= n; ++i) p[a[i]] = i, id[i] = i;
	memset(a, 0, sizeof(a));
	sort(id + 1, id + n + 1, Cmp);
	for (i = 1; i <= n; ++i) Ins(b[id[i]]);
	for (i = 1; i <= n; ++i) if (a[i] != b[i]) return puts("-1"), 0;
	for (j = (int)ans.size(), i = 0; i < j; ++i) printf("%d\n", ans[i]);
	return 0;
}

Measured memory_bytes: 256
n = int(input())
txy = [[0,0,0]] + [[int(item) for item in input().split()] for _ in range(n)]

for i in range(n+1):
    if i == 0:
        continue
    t, x, y = txy[i-1]
    nt, nx, ny = txy[i]
    if abs(nx - x) + abs(ny - y) > nt - t:
        print("No")
        exit()
    if (abs(nx - x) + abs(ny - y)) % 2 != (nt - t) % 2:
        print("No")
        exit()
print("Yes")

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

using namespace std;

const int mod = 1000000007;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

int main()
{
    int a,b,c;
    cin >> a >> b >> c;

    cout << max(c - (a-b), 0) << endl;
}

Measured memory_bytes: 256
import math 
insu=[[0]*1001 for i in range(1001)]
for i in range(1, 1001):
    n=i
    for j in range(2, 1001):
        while n%j==0:
            n=n//j
            insu[i][j]+=1
n=int(input())
new=[1]*1001
for i in range(1,n+1):
    for j in range(1001):
        new[j]+=insu[i][j]
ans=1
for n in new:
    ans*=n
print(ans%(10**9+7))

Measured memory_bytes: 10996
//Problem 1102F DP+Bitmasking
#include<bits/stdc++.h>

#define hell                         1000000007
#define __lcm(a,b)                   (a*b)/__gcd(a,b)
#define ll                           long long
#define vll                          vector<ll>
#define pll                          vector< pair<ll,ll> >
#define pb                           push_back
#define mp                           make_pair
#define all(v)                       v.begin(),v.end()
#define bs                           binary_search
#define F                            first
#define S                            second
#define rep(i,a,b)                   for(ll i=a;i<b;i++)
#define pcont(a)                     for(auto i:a) cout<<i<<" ";cout<<endl;
#define ret(x)                       return cout<<x,0;
#define dbg(x)                       cerr << #x << " is " << x << endl;
#define endl                           '\n'

#define MAX 100005
using namespace std;

ll h,n;
ll a[1001],b[1001];
ll dp[10001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin >> h >> n;
    rep(i,0,n) cin >> a[i] >> b[i];
    
    dp[0]=0;
    rep(hh,1,h+1) {
    	dp[hh]=1e15;
    	rep(i,0,n) {
    		if(hh>=a[i]) dp[hh]=min(dp[hh],b[i]+dp[hh-a[i]]);
    		else dp[hh]=min(dp[hh],b[i]);
    	}
    }
    cout << dp[h] << endl;
}

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

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

int main() {
    int n,x;
    cin >> n >> x;
    int pos = 0, cnt = 0;
    rep(i,n){
        if(pos <= x){
            cnt++;
        }
        int l; cin >> l;
        pos += l;
    }
    if(pos <= x) cnt++;
    cout << cnt << endl;
}


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

#define coutv(v) for (int i = 0; i < (v).size(); ++i) cout << v[i] << ' '; cout << endl;
#define coutvv(v) for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cout << v[i][j] << ' '; cout << endl;}
#define debugv(v) {for (int i = 0; i < (v).size(); ++i) cerr << v[i] << ' '; cerr << endl;}
#define debugvv(v) {for (int i = 0; i < (v).size(); ++i) {for (int j = 0; j < (v[i]).size(); ++j) cerr << v[i][j] << ' '; cerr << endl;}}
#define TC int TESTCASE; cin >> TESTCASE; while (TESTCASE--)
typedef long long ll;




int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "ACL";
    }
}


Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void ntrim(char*);
char** makeLines(int*);
void aruku(char**,int,int,int,int,int,int,char*);


int main(void){
	
	int lineban=1;
	char** lines=makeLines(&lineban);
	
	int sx=1,sy=1,step=0;int dir=0;int x=0,y=0;
	if(lines[2][1]=='1'){sx=1;sy=2;dir=0;}else{sx=1;sy=3;dir=1;}
	
	char* path=(char*)calloc(10,sizeof(char));
	aruku(lines,sx,sy,sx,sy,step,dir,path);
	
	printf("%s\n",path);
	free(path);
	free(lines);

return 0;
}


void ntrim(char *str) {  
  char *p;  
  p=strchr(str,'\n');  
  if(p!=NULL) {  
    *p = '\0';
  }  
}  

char** makeLines(int *lineban){
	char** line=(char**)calloc(1,sizeof(char*));
	char* s;
	size_t len;
	int w=0;
	int sz=0;
	while(sz=getline(&s,&len,stdin)>0 && s[0]!='\n'){
		line=realloc(line,((*lineban)+5)*sizeof(char*));
		if((*lineban)==1){line[0]=(char*)calloc(strlen(s)+5,sizeof(char));line[1]=(char*)calloc(strlen(s)+5,sizeof(char));}
		line[(*lineban)+1]=(char*)calloc(sz+5,sizeof(char));
		line[0][(*lineban)+1]='0';
		int pt=1;
		ntrim(s);
		sprintf(line[(*lineban)+1],"%c%s%c%c",'0',s,'0','\0');
		if(w<strlen(s)){w=sz;}
		(*lineban)++;
	}
	line[0]=realloc(line[0],(w+2)*sizeof(char));
	line[1]=realloc(line[1],(w+2)*sizeof(char));
	for(int i=0;i<w+1;i++){line[0][i]='0';line[1][i]='0';}line[0][w+1]='\0';line[1][w+1]='\0';

	line[(*lineban)+1]=(char*)calloc(w+2,sizeof(char));
	line[(*lineban)+2]=(char*)calloc(w+2,sizeof(char));
	
	for(int i=0;i<w+1;i++){line[(*lineban)+1][i]='0';line[(*lineban)+2][i]='0';}
	line[(*lineban)+1][w+1]='\0';
	line[(*lineban)+2][w+1]='\0';
	return line;
}

void aruku(char** line,int x,int y,int sx,int sy,int step,int dir,char* path){
	if(dir==0)strcat(path,"R");
	else if(dir==3)strcat(path,"U");
	else if(dir==1)strcat(path,"D");
	else{ strcat(path,"L");}
	if(strlen(path)-step<10){path=realloc(path,(strlen(path)+10)*sizeof(char));}
	
	if(sx==x && sy==y && step>0)return;
	switch(dir){
	case 0:
		if(line[y-1][x+1]=='1'){x=x+1;y=y-1;dir=3;}
		else if(line[y][x+1]=='1'){x=x+1;y=y;dir=0;}
		else if(line[y+1][x+1]=='1'){x=x+1;y=y+1;dir=1;}
		else{dir=2;}
		step++;
		aruku(line,x,y,sx,sy,step,dir,path);
		break;
	case 1:
		if(line[y+1][x]=='1'){x=x;y=y+1;dir=0;}
		else if(line[y+2][x]=='1'){x=x;y=y+2;dir=1;}
		else if(line[y+1][x-1]=='1'){x=x-1;y=y+1;dir=2;}
		else{dir=3;}
		step++;
		aruku(line,x,y,sx,sy,step,dir,path);
		break;
	case 2:
		if(line[y+1][x]=='1'){x=x;y=y+1;dir=1;}
		else if(line[y][x-1]=='1'){x=x-1;y=y;dir=2;}
		else if(line[y-1][x]=='1'){x=x;y=y-1;dir=3;}
		else{dir=0;}
		step++;
		aruku(line,x,y,sx,sy,step,dir,path);
		break;
	
		case 3:
		if(line[y-1][x-1]=='1'){x=x-1;y=y-1;dir=2;}
		else if(line[y-2][x]=='1'){x=x;y=y-2;dir=3;}
		else if(line[y-1][x]=='1'){x=x;y=y-1;dir=0;}
		else{dir=1;}
		step++;
		aruku(line,x,y,sx,sy,step,dir,path);
		break;
	}
	return;
}




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

bool IsPrime(int num)
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

int main()
{
    int max = pow(10, 5);
    vector<bool> prime(max + 1, false);
    vector<int> prime_ismo(max + 1, 0);

    rep(i, max + 1)
    {
        if (IsPrime(i))
            prime[i] = true;
    }

    for (int i = 3; i < max + 1; i += 2)
    {
        if (prime[i] && prime[(i + 1) / 2])
            prime_ismo[i]++;
    }
    rep(i, max + 1) prime_ismo[i + 1] += prime_ismo[i];
    int Q;
    cin >> Q;
    vector<int> ans(Q, 0);
    rep(i, Q)
    {
        int l, r;
        cin >> l >> r;
        ans[i] = prime_ismo[r] - prime_ismo[l - 1];
    }

    rep(i, Q) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 1408
import sys
import math
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n = ni()
a = na()
asum = sum(a)
s1 = 0
for ai in a:
    s0 = s1
    s1 += ai
    if s1 >= asum//2:
        print(min(asum-2*s0, 2*s1 - asum))

        exit()


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

int counter(int );

int main(void){

    int a,b;
    int tmp, cnt = 0;
    int value = 0;

    scanf("%d %d", &a, &b);
    cnt = counter(b);
    
    value = a * cnt + b;

    if(sqrt((double)value) - (int)(sqrt((double)value))){
            printf("No\n");
            }
            else
            printf("Yes\n");

    return 0;
}


int counter(int data){

    int tmp, carry = 1;
    tmp = data;

    while(tmp / carry)
        carry = carry * 10;

    return carry;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define Rep(i,s,f) for(int i=(int)s;i<(int)f;i++)
using ll=long long;
using namespace std;


int main()
{
	ll N,M;
	cin>>N>>M;
	if(N>=M/2)
	{
		cout<<M/2<<endl;
		return 0;
	}
	M+=N*2;
	cout<<M/4<<endl;
	return 0;
}


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

int main() {

  vector<char> data(3);
  for(int i=0;i<3;i++){
    cin >> data[i];
  }
  
  if(data[0]==data[1] && data[1]==data[2]) cout << "No" << endl;
  else cout << "Yes" << endl;
    
}

Measured memory_bytes: 256
package main
import (
  "bufio"
  "os"
  "strconv"
  "strings"
  "fmt"
)

var reader = bufio.NewReaderSize(os.Stdin, 1000000)
var writer = bufio.NewWriter(os.Stdout)
func NextLine() string {
  buffer := make([]byte, 0)
  for true {
    line, isPrefix, err := reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer, line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func NextInt(A ...*int) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.Atoi(L[i])
  }
}
func NextIntVec(A *[]int) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]int, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.Atoi(l)
  }
}
func NextFloat(A ...*float64) {
  L := strings.Split(NextLine(), " ")
  for i, a := range A {
    *a, _ = strconv.ParseFloat(L[i], 64)
  }
}
func NextFloatVec(A *[]float64) {
  L := strings.Split(NextLine(), " ")
  (*A) = make([]float64, len(L))
  for i, l := range L {
    (*A)[i], _ = strconv.ParseFloat(l, 64)
  }
}
func Write(s interface{}) {
  fmt.Fprintln(writer, s)
}
func WriteIntVec(A []int) {
  S := make([]string, len(A))
  for i, a := range A {
    S[i] = strconv.Itoa(a)
  }
  Write(strings.Join(S, " "))
}
func Output() {
  _ = writer.Flush()
}

func MaxInt(A ...int) int {
  max := A[0]
  for _, a := range A {
    if max < a { max = a }
  }
  return max
}
func MinInt(A ...int) int {
  min := A[0]
  for _, a := range A {
    if a < min { min = a }
  }
  return min
}
func SumInt(A ...int) int {
  sum := 0
  for _, a := range A {
    sum += a
  }
  return sum
}
func AbsInt(x int) int {
  if x < 0 { x = -x }
  return x
}

func Solve(){
  var N, X, Y int
  NextInt(&N, &X, &Y)
  X, Y = X - 1, Y - 1
  D := make([][]int, N)
  Q := make([]int, 0)
  var q int
  for i := range D {
    D[i] = make([]int, N)
    for j := range D[i] { D[i][j] = N }
    D[i][i] = 0
    Q = append(Q, i)
    for 0 < len(Q) {
      q = Q[0]
      Q = Q[1:]
      if q < N - 1 && D[i][q + 1] == N {
        D[i][q + 1] = D[i][q] + 1
        Q = append(Q, q + 1)
      }
      if 0 < q && D[i][q - 1] == N {
        D[i][q - 1] = D[i][q] + 1
        Q = append(Q, q - 1)
      }
      if q == X && D[i][Y] == N {
        D[i][Y] = D[i][X] + 1
        Q = append(Q, Y)
      }
      if q == Y && D[i][X] == N {
        D[i][X] = D[i][Y] + 1
        Q = append(Q, X)
      }
    }
  }
  A := make([]int, N)
  for i := range D {
    for _, d := range D[i][i + 1:] {
      A[d]++
    }
  }
  for _, a := range A[1:] {
    Write(a)
  }
}

func main() {
  Solve()
  Output()
}

Measured memory_bytes: 49408
import java.io.*;
import java.util.StringTokenizer;

public class Main
{
    public static void main( String[] args )
    {
	BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
	try
	{
	    String line = "";

	    while( (line = br.readLine()) != null && !line.isEmpty() )
		{
		    StringTokenizer st = new StringTokenizer( line );
		    int a, b, c, d, e, f;
		    a = Integer.parseInt(st.nextToken());
		    b = Integer.parseInt(st.nextToken());
		    c = Integer.parseInt(st.nextToken());
		    d = Integer.parseInt(st.nextToken());
		    e = Integer.parseInt(st.nextToken());
		    f = Integer.parseInt(st.nextToken());

		    double det = a*e-b*d, x = (e*c-b*f)/det, y = (-d*c+a*f)/det;

		    if( x == -0.0 )
			x = 0.0;
		    if( y == -0.0 )
			y = 0.0;
	    
		    System.out.printf( "%.3f %.3f\n", x, y );
		}
	} catch( IOException ex )
	{
	    System.out.println("error");
	}
    }
}

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

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

const ll mod =  1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;   // INFの値は1152921504606846976

int main()
{
    int n;
    cin >> n;
    ll sum = 0;
    rep(i,n+1){
        if(i % 3 != 0 && i % 5 != 0){
            sum += (ll)(i);
        }
    }
    cout << sum;
}


Measured memory_bytes: 3636
n=int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))


a_sum=sum(a)
b_sum=sum(b)

c = a[:]

if a_sum< b_sum:
    print(-1)

    
else:
    sub_ab=[0 for i in range(n)]
    for i in range(n):
        sub_ab[i]=c[i]-b[i]

    if sum(1 for i in range(n) if sub_ab[i] > 0) == n:
        print(0)
              
    else:
        minus_value=sum(sub_ab[i] for i in range(n) if sub_ab[i] < 0)
        minus_number=sum(1 for i in range(n) if sub_ab[i] < 0)
        surplas=0
        m=0
        sub_ab_sorted=sorted(sub_ab, reverse=True)

        while surplas<abs(minus_value):
            surplas=sum(sub_ab_sorted[0:m+1])
            m+=1
        
        print(m+minus_number)

Measured memory_bytes: 142432
#include<stdio.h>
int f[5][5],i,j,a,y,x,p;
int main()
{
	for(;i<9;++i){
		char s[6];
		scanf("%s",s);
		for(j=0;j<4+i%2;++j){
			a=s[j]-48;
			f[i/2][j]|=a<<(1+i%2);
			f[i/2+i%2][j+!(i%2)]|=a<<3-i%2*3;
		}
	}
	do{
		do
			p=(p+1)%4;
		while(!((f[y][x]>>p)&1));
		putchar("URDL"[p]);
		x+=p?2-p:0;
		y+=p==3?0:p-1;
		p=(p+2)%4;
	}while(y!=0||x!=0||f[0][0]==6&&p==3);
	return !puts(""); 
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main(){
	int N, T;
	while(cin >> N >> T){
		int m = 0, M = 0, d = 0;
		int r = 0;
		cin >> m; M = m;
		for(int i=1;i<N;i++){
			int A; cin >> A;
			if(A < m) m = M = A;
			if(A > M){
				if(A-m >= d){
					if(A-m > d) r = 1;
					else if(A-m == d) ++r;
					d = A-m;
				}
				M = A;
			}
		}
		cout << r << endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ll long long
#define INF 999999999
using namespace std;
int main() {
  int k,a,b;
  std::cin >> k >> a >> b;
  bool ans = false;
  for (size_t i = a; i < b+1; i++) {
    if (i%k == 0) {
      ans = true;
    }
  }
  if (ans) {
    std::cout << "OK" << '\n';
  }
  else{
    std::cout << "NG" << '\n';
  }
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FILL(a, value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
 
typedef long long LL;
typedef pair<int, int> PII;

const int mod = 998244353;
const int MAX = 304;

int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}

int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}

int mult(int a, int b)
{
	return (LL)a * b % mod;
}

void updAdd(int& x, int val)
{
	x += val;
	if(x >= mod)
		x -= mod;
}

bool f[MAX][MAX][MAX];
int g[MAX][MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	f[0][0][0] = true;
	FOR(i, 0, SZ(s))
		FOR(c0, 0, SZ(s) + 1)
			FOR(c1, 0, SZ(s) + 1)
				if(f[i][c0][c1])
				{
					assert(2 * (c0 + c1) <= i);
					f[i + 1][c0][c1] = true;
					if(c0)
						f[i + 1][c0 - 1 + (s[i] == '0')][c1 + (s[i] == '1')] = true;
					if(c1)
						f[i + 1][c0 + (s[i] == '0')][c1 - 1 + (s[i] == '1')] = true;
					if(i + 1 < SZ(s))
					{
						f[i + 2][c0 + (s[i] == '0')][c1 + (s[i] == '1')] = true;
						f[i + 2][c0 + (s[i + 1] == '0')][c1 + (s[i + 1] == '1')] = true;
					}
				}
	g[SZ(s)][0][0] = 1;
	RFOR(i, SZ(s) + 1, 1)
		FOR(c0, 0, SZ(s) + 1)
			FOR(c1, 0, SZ(s) + 1)
			{
				updAdd(g[i - 1][c0][c1], g[i][c0][c1]);
				updAdd(g[i][c0 + (s[i - 1] == '1')][c1 + (s[i - 1] == '0')], g[i][c0][c1]);
			}
	int ans = mod - 1;
	FOR(i, 0, SZ(s) + 1)
		FOR(c0, 0, SZ(s) + 1)
			FOR(c1, 0, SZ(s) + 1)
				if(f[i][c0][c1])
				{
					//cerr << i << " " << c0 << " " << c1 << " " << g[i][c0][c1] << endl;
					updAdd(ans, g[i][c0][c1]);
				}
	cout << ans << "\n";
	return 0;
}


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

const int nm = 2e5;
int n, a[nm], s = 0;
int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		s ^= a[i];
	}
	for (int i = 0; i < n; ++i)
		cout << (a[i] ^ s) << endl;
}


Measured memory_bytes: 4344
// #include<iostream>
// #include<vector>
// #include<algorithm>
// using namespace std;
// 
// int main(){
//   int n,m,score=0;cin>>n;
//   vector<string> s(n);
//   for(int i=0;i<n;i++){
//     cin>>s[i];
//     for(int j=i-1;j<n;j++){
//       if(s[i]==s[j])score++;
//     }
//   }
//     cin>>m;
//     vector<string> t(m);
//   for(int i=0;i<m;i++){
//     cin>>t[i];
//     for(int j=i-1;j<m;j++){
//       if(s[i]==t[j])score--;
//     }
//   }
//   cout<<score<<endl;
//   return 0;
// }
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> blue(n);
    for (int i = 0; i < n; i++) {
        cin >> blue[i];
    }
    int m;
    cin >> m;
    vector<string> red(m);
    for (int i = 0; i < m; i++) {
        cin >> red[i];
    }

    int ans = 0;
    auto calc = [&](string s) {
        int buf = 0;
        for (string t: blue) {
            if (t == s) buf++;
        }
        for (string t: red) {
            if (t == s) buf--;
        }
        return buf;
    };

    for (string t: blue) {
        ans = max(ans, calc(t));
    }

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


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {
	int a,b;
	cin >> a >> b;
	if (a > b)cout << "a > b" << endl;
	if (b > a)cout << "a < b" << endl;
	if (a == b)cout << "a == b" << endl;
	return 0;

}


Measured memory_bytes: 3084
use std::io::{self, BufRead};

fn main() {
  let stdin = io::stdin();
  let mut lines = stdin.lock().lines();
  let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
  let mut ds: Vec<usize> = lines.next().unwrap().unwrap().split(' ').map(|x| x.parse().unwrap()).collect();
  ds.sort();
  let ans = ds[n/2] - ds[n/2-1];
  println!("{}", ans);
}

Measured memory_bytes: 6396
//
// Created by 童正阳 on 2018/9/14.
// https://abc044.contest.atcoder.jp/tasks/arc060_a
// 动态规划：dp[i][j]表示选i个数和为j的方法数
// 那么有：dp[i][j]=\sum{dp[i-1][j-a[k]], 1<=k<=N}
// 最终结果为：\sum{dp[i][i*A]}
//
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int N, A, x[51], sum[51];
ll dp[51][2501];
int main() {
    cin >> N >> A;
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= N; i++) {
        cin >> x[i];
        sum[i] = sum[i-1] + x[i];
    }
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int k = 1; k <= N; k++) {
        for (int i = k; i >= 1; i--) {
            for (int j = sum[k]; j >= x[k]; j--) {
                dp[i][j] += dp[i-1][j-x[k]];
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += dp[i][i*A];
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include <algorithm>
#include <numeric>
using namespace std;
# define maxi 100000
# define maxw 100000
# define maxn 100
using ll = long long;
ll gcd(ll a,ll b){
  if(b==0) return a;
    else return gcd(b,a%b);
}

ll lcm(ll a,ll b){
  ll g=gcd(a,b);
    return a/g*b;
}
int main() {
  ll n,t[maxn];
  cin>>n;
  for(int i(0);i<n;i++){
    cin>>t[i];
  }
  ll koubaisu=t[0];
  for(int i(1);i<n;i++){
    koubaisu=lcm(koubaisu,t[i]);
  }
  cout << koubaisu;
  return 0;
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin >> n;
  
  vector<int> x(n);
  int minimum = 1e9, maximum = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    x.at(a)++;
    minimum = min(minimum, a);
    maximum = max(maximum, a);
  }
  
  bool flag = true;
  if (maximum % 2 == 0) {
    if (minimum != maximum / 2 || x.at(minimum) != 1) flag = false;
    for (int i = minimum + 1; i <= maximum; i++) {
      if (x.at(i) <= 1) flag = false;
    }
    if (flag) cout << "Possible\n";
    else cout << "Impossible\n";
  }
  else {
    if (minimum != maximum / 2 + 1 || x.at(minimum) != 2) flag = false;
    for (int i = minimum + 1; i <= maximum; i++) {
      if (x.at(i) <= 1) flag = false;
    }
    if (flag) cout << "Possible\n";
    else cout << "Impossible\n";
  }
}

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

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

#define MOD 1000000007
#define INF 1000000000

using ll = long long int;
using namespace std;

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;



int main() {
    int N; cin >> N;
    vi A(N);
    rep(i,N) cin >> A[i];

    ll ans = 1;
    vi cnt(N+1, 0);
    cnt[0] = 3;

    rep(i, N){
        ans *= (cnt[A[i]] - cnt[A[i]+1]);
        ans %= MOD;
        cnt[A[i]+1]++;
    }

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


Measured memory_bytes: 1024
// #include<iostream>
// #include<vector>
// #include<algorithm>
// #include<map>
// #include<cstring>
// #include<math.h>
// #include<bitset>
// #include<queue>
// #include<set>
// #include<iomanip>
// #include<math.h>
// #include<assert.h>
// #include<string>
// #include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -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(){
  int A,B,C,D,E,F;
  cin >> A >> B >> C >> D >> E >> F;
  double M = 0;
  int w=0,s=0;
  for(int a=0; a<=30; a++){
    for(int b=0; b<=30; b++){
      for(int c=0; c<=3000; c++){
        if(a+b == 0){
          continue;
        }
        if((a*A+b*B)*100+c*C > F){
          continue;
        }
        int d;
        int melt;
        melt = (a*A+b*B)*E;
        int rem;
        if(c*C > melt){
          continue;
        }
        rem = min(melt-c*C, F-((a*A+b*B)*100+c*C));
        d = rem/D;
        double con;
        double temp_w,temp_s;
        temp_w = (a*A+b*B)*100;
        temp_s = c*C + d*D;
        con = (temp_s*100.0)/(temp_w+temp_s);
        if(M <= con){
          w = (a*A+b*B)*100;
          s = c*C + d*D;
          M = con;
        }
      }
    }
  }
  if(s == 0){
    cout << A*100 << " " << 0 << endl;
    return 0;
  }
  cout << w+s << " " << s << endl;
  return 0;
}


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

import bisect
import copy
import collections
import heapq
import itertools
import math
import numpy as np
from operator import itemgetter
import scipy.misc
import sys

"""
#### 入力例 ####
N, X = map(int, input().split())
x = list(map(int, input().split()))
S = [input() for n in range(N)]
C_ = [list(map(str, input().split())) for n in range(H)]
A = [list(map(int, input().split())) for n in range(H)]

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
"""


H, W, K = map(int, input().split())
C = [list(input()) for n in range(H)]

def main():
    C_ = np.array(C)
    row_list = collections.deque()
    for n in range(2**H):
        row_list.append([h for h in range(H) if not (n>>h) & 1])
    col_list = collections.deque()
    for n in range(2**W):
        col_list.append([w for w in range(W) if not (n>>w) & 1])
    buf_col_list = list(col_list)
    ans = 0
    while row_list:
        rows = row_list.pop()
        col_list = collections.deque(buf_col_list)
        while col_list:
            cols = col_list.pop()
            cnt = 0
            for h in rows:
                for w in cols:
                    if C_[h,w] == "#":
                        cnt+=1
            if cnt == K:
                ans+=1
    print(ans)
    return
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 31028
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn];
 int n;
 int b[maxn];
map<int,int>ma;
bool slove(int m)
{
    memset(b,0,sizeof(b));
    b[1]=m;
    for(int i=2;i<=n;i++)
    {
        int sum=a[i-1]-b[i-1]/2;
        if(sum<0)
            return true;
        b[i]=sum;
    }
   int sum=a[n]-b[1]/2;
     b[n]=sum;
   if(sum<0)
   return true;
    return false;


}
int main()
{

    cin>>n;
    int num=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(i%2==0)
            num-=a[i];
        else
            num+=a[i];

    }
    b[1]=num;
  for(int i=2;i<=n-1;i++)
    b[i]=2*a[i-1]-b[i-1];
  b[n]=2*a[n]-b[1];
  for(int i=1;i<=n;i++)
    cout<<b[i]<<' ';
  cout<<endl;


    return 0;
}


Measured memory_bytes: 2048
N, W = map(int, input().split())
w_list = []
v_list = []
for i in range(N):
    w, v = map(int, input().split())
    w_list.append(w)
    v_list.append(v)

MAX = 10**11 + 1
dp = [[MAX]*(N*10**3+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    for j in range(0, N*10**3+1):
        if j == 0:
            dp[i][j] = 0
        elif j >= v_list[i-1]:
            dp[i][j] = min(dp[i-1][j], w_list[i-1]+dp[i-1][j-v_list[i-1]])
        else:
            dp[i][j] = dp[i-1][j]
    #print(dp[i]) 
ans = 10**6 + 1
for k in range(N*10**3+1):
    if dp[N][k] <= W:
        ans = k
#print(dp[N])
print(ans)

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

int main()
{
	int n = 0;
	std::cin >> n;
	--n;

	std::vector<int> b(n);
	
	int inputNum = 0;

	for (int index = 0; index < n; ++index)
	{
		std::cin >> inputNum;
		b.at(index) = inputNum;
	}

	unsigned long long sum = b.at(n - 1);

	for (int index = n - 1; index > 0; --index)
	{
		sum += std::min(b.at(index), b.at(index - 1));
	}

	sum += b.at(0);

	std::cout << sum << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 2147483647;
const ll LINF = 9223372036854775807;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main(){
	int n, x, y; cin >> n >> x >> y;
	VI ans(n,0);
	for(int i=1;i<=n;i++){
		priority_queue<P> q;
		q.push({0,i});
		vector<bool> f(n+1,0);
		while(!q.empty()){
			int v=q.top().second;
			int d=q.top().first;
			q.pop();
			if(!f[v]){
				f[v]=1;
				ans[-d]++;
			}
			else
				continue;
			if(v==x) q.push({d-1,y});
			if(v==y) q.push({d-1,x});
			if(v!=n) q.push({d-1,v+1});
			if(v!=1) q.push({d-1,v-1});
		}
	}
	REP(i,n-1) cout << ans[i+1]/2 << endl;
	return 0;
}

Measured memory_bytes: 256
s=list(input())
s.reverse()
l=[1,10,9,12,3,4]
p=10**9+7
dp=[[0 for i in range(13)] for j in range(len(s))]
if s[0]=='?':
  for i in range(10):
    dp[0][i]+=1
else:
  dp[0][int(s[0])]+=1
for i in range(1,len(s)):
  if s[i]!='?':
    for j in range(13):
      dp[i][j]+=dp[i-1][(j-(int(s[i])*l[i%6]))%13]
      dp[i][j]%=p
  else:
    for j in range(13):
      for k in range(10):
        dp[i][j]+=dp[i-1][(j-k*l[i%6])%13]
        dp[i][j]%=p
print(dp[len(s)-1][5])

Measured memory_bytes: 69512
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <iomanip>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
const int inf = 1e9;
const ll linf = 1LL << 50;

int n, m;
set<int> st[9];

int main(int argc, char const* argv[])
{
	cin >> n >> m;
	vector<int> vec;
	for(int i = 0; i < n; i++)vec.pb(i);
	for(int i = 0; i < m; i++){
			int a, b;
			cin >> a >> b;
			a--; b--;
			st[a].insert(b);
			st[b].insert(a);
	}
	int res = 0;
	do{
			if(vec[0] != 0)continue;
			for(int i = 0; i < n - 1; i++){
					if(st[vec[i]].find(vec[i+1]) == st[vec[i]].end())break;
					if(i == n - 2)res++;
			}
	}while(next_permutation(vec.begin(), vec.end()));
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 888