akhauriyash/Code-Regression huggingface dataset:
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    debug("size %ld: ", arr.size()); \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif


int main(void) {
    string str;
    cin >> str;
    stack<char> stack;
    for(int i = 0; i < str.length(); i++) {
        char ch = str[i];
        switch(ch) {
            case 'S':
                stack.push('S');
                break;
            case 'T':
                if((!stack.empty()) && stack.top() == 'S') {
                    stack.pop();
                } else {
                    stack.push('T');
                }
                break;
            default:
                break;
        }
        debug("size: %ld\n", stack.size());
    }
    cout << stack.size() << endl;
    return 0;
}

Measured memory_bytes: 3724
#include <stdio.h>
#include <string.h>

int main(void)
{
    char str[20];
    int len, i;

    scanf("%s", str);

    len = strlen(str);

    for(i=len-1; i>=0; i--) {
        printf("%c", str[i]);
    }
    printf("\n");

    return (0);
}

Measured memory_bytes: 524
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    h, w = get_li()
    S = get_data(h, [str])
    horizontal = [[0 for _ in range(w)] for _ in range(h)]
    for i in range(h):
        indices = [j for j, x in enumerate(S[i]) if x == '#'] + [w]
        for a, b in zip([-1] + indices, indices):
            count = b - a - 1
            for j in range(a + 1, b):
                horizontal[i][j] = count
    vertical = [[0 for _ in range(w)] for _ in range(h)]
    for j in range(w):
        indices = [i for i, x in enumerate([S[k][j] for k in range(h)]) if x == '#'] + [h]
        for a, b in zip([-1] + indices, indices):
            count = b - a - 1
            for i in range(a + 1, b):
                vertical[i][j] = count
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, horizontal[i][j] + vertical[i][j] - 1)
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()


Measured memory_bytes: 138604
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>



int main() {
    int n; std::cin >> n;
    if (n == 1) std::cout << "Hello World" << std::endl;
    else {
        int a, b; std::cin >> a >> b;
        std::cout << a + b << std::endl;
    }
    return 0;
}


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

int main() {
	int n, k;
	cin >> n >> k;

	int l[k], r[k];

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

	long long dp[n+1];
	long long dpsum[n+1];
	for(int i=0;i<=n;i++){
		dp[i] = 0;
		dpsum[i] = 0;
	}
	dp[1] = 1;
	dpsum[1] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<k;j++){
			int li = i - r[j];
			int ri = i - l[j];
			if(ri < 1) continue;
			if(li < 1) li = 1;
			dp[i] += (dpsum[ri] - dpsum[li-1]);
			dp[i] %= 998244353;
		}
		dpsum[i] = (dpsum[i-1] + dp[i]);
	}
  	cout << dp[n] << endl;
  	return 0;
}

Measured memory_bytes: 6760
#include<stdio.h>
#include<stdlib.h>
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;
Node head, tail;
void inorder(Node node){
  if(node != tail){
    inorder(node->left);
    printf(" %d", node->key);
    inorder(node->right);
  }
}
void preorder(Node node){
  if(node != tail){
    printf(" %d", node->key);
    preorder(node->left);
    preorder(node->right);
  }
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while (x != NIL){
    y = x;
    if (z->key < x->key)x = x->left;
    else x = x->right ;
    z->parent = y;
  }
  if (y == NIL)root = z;
        else if (z->key < y->key) y->left = z;
        else y->right = z;
}
Node find ( Node A, int x){
  while(A!=NIL && x!=A->key){
    if(x < A->key)
      A=A->left;
    else A=A->right;
  }
  return A;
  }

int main(){
  int n, i, x;
  char com[20];
  Node a;
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    }
   else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
  }
       else if ( com[0] == 'f' ){
	 scanf("%d",&x);
	 a=find(root,x);
	 if(a==NIL)printf("no\n");
	 else printf("yes\n");
  }

  }

  return 0;
}



Measured memory_bytes: 20476
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
bool vis[1000][1000];
int main() {
	ll n,a,b;cin>>n>>a>>b;
ll ans=(n/(a+b));ans*=a;
ans+=min(a,n%(a+b));
cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<complex>
using namespace std ;
typedef vector<int> vi ;
typedef vector<vi> vvi ;
typedef vector<string> vs ;
typedef pair<int, int> pii; 
typedef long long ll ;

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

int gcd (int a , int b){
  if(b>0)
    return gcd(b,a%b);
  else 
    return a;
}
int lcm(int a,int b){
  return ((a / gcd(a,b)) * b);
}
int main(void){
  int a,b;
  while(cin >> a >> b){
    cout<< gcd(a,b) << " " << lcm(a,b) << endl;
  }
}

Measured memory_bytes: 1160
#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 <stdio.h>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);++i)
#define urep(i,a,n) for(ll i = (a);i>=(n);--i)
#define all(x) (x).begin(),(x).end()
#define INF 1e18
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N,M,X,Y,A,B,C,D,Q,K,R,W,H,P,L;
ll ans;
string S,T;
ll y[101010];
ll a[101010];
ll b[101010];
ll t[101010];
ll p[101010];
ll n[101010];
ll l[101010];
ll r[101010];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
struct Edge{
	ll to,cost;
	 Edge(ll to, ll cost) : to(to), cost(cost) {}
};
typedef vector<vector<Edge> > AdjList;
AdjList graph;
vector<ll> dist;

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	vector<ll> size;
    UnionFind(ll N) : par(N),size(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) par[i] = i;
		for(ll i = 0; i < N; i++) size[i] = 1;
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
	ll GetSize(ll x){
		return size[root(x)];
	}

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		size[ry]+=size[rx];

    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};
int main() {
    cin>>N;
    vector<pair<ll,ll> >v;
    if(N%2==1){
        rep(i,1,N+1){
            rep(j,i,N+1){
                if(i+j!=N && i!=j){
                    v.push_back(make_pair(i,j));
                }
            }
        }
    }else{
        rep(i,1,N+1){
            rep(j,i,N+1){
                if(i+j!=N+1 && i!=j){
                    v.push_back(make_pair(i,j));
                }
            }
        }
    }
    cout<<v.size()<<endl;
    rep(i,0,v.size()){
        cout<<v[i].first<<" "<<v[i].second<<endl;
    }
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

typedef long long ll;

inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0' || '9'<ch)ch=getchar();
	while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
	return x;
}

const int N=2009;
const int M=N*N;
const int md=1e9+7;

int n,k;
ll fac[M],inv[M];
int f[N][N];

inline ll chk(ll a){if(a>=md)a-=md;return a;}

inline ll qpow(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
			ret=ret*a%md;
		a=a*a%md;
		b>>=1;
	}
	return ret;
}

inline void init()
{
	fac[0]=1;
	for(int i=1;i<M;i++)
		fac[i]=fac[i-1]*(ll)i%md;
	inv[M-1]=qpow(fac[M-1],md-2);
	for(int i=M-2;i>=0;i--)
		inv[i]=inv[i+1]*(ll)(1+i)%md;
}

inline ll c(ll a,ll b)
{
	return fac[a]*inv[b]%md*inv[a-b]%md;
}

int main()
{
	n=read();
	k=read();
	init();
	if(k==1)return puts("1"),0;

	f[0][0]=1;
	long long ans=1;
	for(int i=0;i<=n;i++)
	{
		if(i)ans=ans*i%md;
		for(int j=i;j<=n;j++)
		{
			if(i)f[i][j]=f[i-1][j];
			if(j>i)f[i][j]=chk(f[i][j]+1ll*c(i+j*(k-1)-1,k-2)*f[i][j-1]%md);
		}
	}
	printf("%lld\n",(long long)f[n][n]*ans%md);
	return 0;
}


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

int main()
{
    string S;
    string T;
    cin >> S >> T;
    T.pop_back();

    if (S == T)
    {
        cout << "Yes";
    }
    else
    {
        cout <<"No";
    }
    
    
}

Measured memory_bytes: 3624
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
int n,x,y;
int dis[2010][2010];
int ans[2020];
int main(){
    //freopen("data.in","r",stdin);
    cin>>n>>x>>y;
    int len=y-x+1;
    for(int i=1;i<x;i++){
        for(int j=i+1;j<=n;j++){
            if(j<=x) dis[i][j]=j-i;
            else if(j>=y) dis[i][j]=j-i-(y-x)+1;
            else{
                int d2=min(j-x,y-j+1);
                dis[i][j]=x-i+d2;
            }
        }
    }
    for(int i=x;i<=y;i++){
        for(int j=x+1;j<=n;j++){
            if(j<=y){
                dis[i][j]=min(j-i,y-j+1+i-x);
            }
            else{
                dis[i][j]=min(y-i,i-x+1)+j-y;
            }
        }       
    }
    for(int i=y+1;i<=n;i++){
        for(int j=i+1;j<=n;j++)
            dis[i][j]=j-i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            ans[dis[i][j]]++;
        }
    }   
    for(int i=1;i<n;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

Measured memory_bytes: 19328
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
constexpr int Inf = 2100000010;
constexpr ll INF= 2000000000000000000;
constexpr ll MOD = 998244353;
const double PI = 3.1415926535897;
typedef pair<int,int> P;
typedef pair<int,P> PP;

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

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

ll mod(ll val, ll M) {
    val = val % M;
    if(val < 0) {
        val += M;
    }
    return val;
}

template<typename T>
T RS(T N, T P, T M){
    if(P == 0) {
        return 1;
    }
    if(P < 0) {
        return 0;
    }
    if(P % 2 == 0){
        ll t = RS(N, P/2, M);
        if(M == -1) return t * t;
        return t * t % M;
    }
    if(M == -1) {
        return N * RS(N,P - 1,M);
    }
    return N * RS(N, P-1, M) % M;
}

vector<ll> one(200020);

struct S {
    int len;
    ll val;
};

S op(S a,S b) {
    return S{a.len + b.len,(a.val * RS(10ll,(ll)b.len,MOD) + b.val) % MOD};
}

S e() {
    return S{0,0};
}

S mapping(int a,S x) {
    if(a == 0) {
        return x;
    }
    else {
        return S{x.len,one.at(x.len) * a % MOD};
    }
}

int composition(int f,int g) {
    if(f == 0) {
        return g;
    }
    else {
        return f;
    }
}

int id() {
    return 0;
}

int main() {
    int N,Q;
    cin >> N >> Q;
    for(int i = 1;i < N;i++) {
        one.at(i) = (one.at(i - 1) * 10 + 1) % MOD;
    }
    lazy_segtree<S,op,e,int,mapping,composition,id> seg(N);
    for(int i = 0;i < N;i++) {
        seg.set(i,S{1,1});
    }
    for(int i = 0;i < Q;i++) {
        int L,R,D;
        cin >> L >> R >> D;
        L--;
        R--;
        seg.apply(L,R + 1,D);
        S ret = seg.all_prod();
        cout << ret.val << endl;
    }
}

Measured memory_bytes: 17280
#include <stdio.h>
#include <string.h>

int main(void) {
  int i, j, n, m;
  char s[120], t[120];
  scanf("%s", s);
  scanf("%s", t);
  n = strlen(s), m = strlen(t);
  for(i = 0; i < n; ++i) for(j = i + 1; j < n; ++j) if(s[i] > s[j]) {
    char tmp;
    tmp = s[i], s[i] = s[j], s[j] = tmp;
  }
  for(i = 0; i < m; ++i) for(j = i + 1; j < m; ++j) if(t[i] < t[j]) {
    char tmp;
    tmp = t[i], t[i] = t[j], t[j] = tmp;
  }
  if(strcmp(s, t) < 0) printf("Yes");
  else printf("No");
  return 0;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifndef __MACRO_H__
#define __MACRO_H__

#define all(collection)  (collection).begin(), (collection).end()		// begin to end
#define rep(i, begin, end) for (ll i = begin; i < end; i++)				// repeat
#define repr(i, begin, end) for (ll i = begin; end < i; i--)			// repeat reverse

#endif

class ABC134D
{
public:
	ABC134D()
	{
		cin >> n;
		a.resize(n+1);
		rep(i, 1, n+1)
			cin >> a[i];
	}
	void Run(void)
	{
		vector<ll> ans(n + 1);


		repr(i, n, 0)
		{
			if (n < i * 2)
				ans[i] = a[i];
			else
				ans[i] = (SumAns(i, ans) % 2 == a[i]) ? 0 : 1;
		}

		cout << count(all(ans), 1) << endl;
		rep(i, 1, n + 1)
		{
			if (ans[i] == 1)
				cout << i << " ";
		}
	}
private:
	ll SumAns(ll s, vector<ll>& ans)
	{
		ll count = 0;

		ll i = s * 2;
		while (i <= n)
		{
			count += ans[i];
			i += s;
		}

		return count;
	}
	ll n;
	vector<ll> a;
};

int main(void)
{
	ABC134D abc134d;
	abc134d.Run();

	return 0;
}



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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359
#define inf 2147483647
#define INF 9223372036854775807
#define mod 1000000007
#define mod2 998244353
#define Graph vector<vector<int>>

int main() {
    int N; cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; i++) {
        cin >> X.at(i);
        Y.at(i) = X.at(i);
    }
    sort(Y.begin(), Y.end());
    int left = Y.at(N / 2 - 1), right = Y.at(N / 2);
    for (int i = 0; i < N; i++) {
        if (X.at(i) <= left) {
            cout << right << endl;
        }
        else {
            cout << left << endl;
        }
    }
    return 0;
}

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

int main()
{
    long long N, Q, B, C;
    long long sum;

    std::cin >> N;

    int A[N];
    std::unordered_map<long long, long long> count;

    for(int i=0; i< N; i++)
        std::cin >> A[i];

    sum = 0;
    for(int i=0; i<N;i++)
        sum += A[i];

    for(int i = 0; i< N; i++)
        count[A[i]]++;

    std::cin >> Q;

    while(Q--)
    {
        std::cin >> B >> C;

        sum -= (B*count[B]);
        sum += (C*count[B]);

        count[C] += count[B];
        count[B] = 0;

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

}

Measured memory_bytes: 7452
#include<cstdio>
#include<algorithm>
using std::max;
struct node{
	int to,nxt;
}edge[1000100];
int head[1000100],cnt,Maxn[1000100],ans[1000100],n,x,y;
int Fa[1001000];
void addedge(int x,int y){
	edge[++cnt].to=y;
	edge[cnt].nxt=head[x];
	head[x]=cnt;
}
void dfs(int x,int maxn,int u,int se){
	maxn=max(maxn,x),se=max(se,x);
	Maxn[x]=maxn;
	if(maxn==x||se<=Maxn[Fa[maxn]])ans[maxn]++;
	else ans[u]++;
	for(int i=head[x];i;i=edge[i].nxt){
		int upup=edge[i].to;
		if(upup==Fa[x])continue;
		Fa[upup]=x;
		dfs(upup,maxn,maxn==x?upup:u,maxn==x?0:se);
	}
}
void calc(int x,int fa){
	ans[x]+=ans[fa];
	for(int i=head[x];i;i=edge[i].nxt){
		int upup=edge[i].to;
		if(upup==fa)continue;
		calc(upup,x);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		addedge(x,y);
		addedge(y,x);
	}
	dfs(1,0,0,0);
	calc(1,0);
	for(int i=2;i<=n;i++)
		printf("%d ",ans[i]-1);
	return 0;
}

Measured memory_bytes: 33280
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
	char ch = getchar();
	int x = 0, flag = 1;
	for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
	for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
	return x * flag;
}
void write(int x) {
	if (x < 0) putchar('-'), x = -x;
	if (x >= 10) write(x / 10);
	putchar(x % 10 + 48);
}

const int Maxn = 5009, Mod = 1e9 + 7;
struct edge {
	int to, nxt;
}g[Maxn << 1];
int n, head[Maxn], e;
int fac[Maxn], invFac[Maxn];

LL fpm(LL base, LL tims) {
	LL r = 1;
	while (tims) {
		if (tims & 1) r = 1ll * r * base % Mod;
		base = 1ll * base * base % Mod;
		tims >>= 1;
	}
	return r;
}

void add(int u, int v) {
	g[++e] = (edge){v, head[u]}, head[u] = e;
}

void init() {
	clar(head, -1); e = 0;
	n = read();
	rep (i, 2, n) {
		int u = read(), v = read();
		add(u, v), add(v, u);
	}

	fac[0] = 1;
	rep (i, 1, n + 2) fac[i] = fac[i - 1] * 1ll * i % Mod;
	invFac[n + 2] = fpm(fac[n + 2], Mod - 2);
	drep (i, n + 1, 0) invFac[i] = invFac[i + 1] * (i + 1ll) % Mod;
}

int size[Maxn];
void dfsPre(int u, int pa) {
	size[u] = 1;
	for (int i = head[u]; ~i; i = g[i].nxt) {
		int v = g[i].to;
		if (v != pa) {
			dfsPre(v, u);
			size[u] += size[v];
		}
	}
}

int cen, branch, flag;
void dfsRt(int u, int pa) {
	int	bbs = size[1] - size[u];
	for (int i = head[u]; ~i; i = g[i].nxt) {
		int v = g[i].to;
		if (v != pa) {
			dfsRt(v, u);
			bbs = max(bbs, size[v]);
		}
	}
	if (bbs < branch) branch = bbs, cen = u, flag = 0;
	else if (bbs == branch) flag = 1; 
}

LL C(int n, int m) {
	return (n < m) ? 0 : (fac[n] * 1ll * invFac[m] % Mod * invFac[n - m] % Mod);
}

LL dp[2][Maxn], s[Maxn];

void solve() {
	dfsPre(1, 0); branch = INT_MAX; dfsRt(1, 0);
	if (flag) {
		cout << fac[n / 2] * 1ll * fac[n / 2] % Mod << endl;
		return ;
	}
	rep (i, 1, n) size[i] = 0;
	dfsPre(cen, 0);
	int deg = 0, sum = 0;
	for (int i = head[cen]; ~i; i = g[i].nxt) s[++deg] = size[g[i].to];
	sort(s + 1, s + deg + 1);
	dp[0][0] = 1;
	rep (i, 1, deg) {
		clar(dp[i & 1], 0);
		drep (j, (sum += s[i]), 0) {
			LL &res = dp[i & 1][j]; res += dp[(i & 1) ^ 1][j];
			rep (k, 1, min(1ll * j, s[i])) 
				(res += dp[(i & 1) ^ 1][j - k] * 1ll * C(s[i], k) % Mod * C(s[i], k) % Mod * fac[k] % Mod) %= Mod;
		}
	}
	LL ans = fac[n];
	rep (i, 1, n - 1) {
		LL res = ((dp[deg & 1][i] * ((i & 1) ? -1ll : 1ll) * fac[n - i] % Mod) + Mod) % Mod;
		(ans += res) %= Mod;
	}
	cout << ans << endl;
}

int main() {
//	freopen("bosky.in", "r", stdin);
//	freopen("bosky.out", "w", stdout);

	init();
	solve();

#ifdef Qrsikno
	debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
	return 0;
}



Measured memory_bytes: 640
#include <stdio.h> 
int pow2(int n){
  int a = 1;
  for(int i = 0;i < n;i++){
    a = a*2;
  }
  return a;
}
 
void makeBinary(int num, int digit, int array[digit]) {
  int copiedNum = num;
  for (int i = digit - 1; i >= 0; i--) {
  	if (copiedNum >= pow2(i)) {
  	  array[i] = 1;
  	  copiedNum -= pow2(i);
	} else {
  	 array[i] = 0;
    }
  }
}
 
 
int main(void){
  int H, W, K;
  scanf("%d",&H);
  scanf("%d",&W);
  scanf("%d",&K);
 
  int matrix[W][H];
  for(int y = 0;y < H;y++){
	char str[256];
    scanf("%s",str);
    for(int x = 0;x < W;x++){
      matrix[x][y] = str[x] == '#';
    }
  }
  int answer = 0;
  for(int permY = 0;permY < pow2(H);permY++){
    int binaryY[H];
    makeBinary(permY,H,binaryY);
    for(int permX = 0;permX < pow2(W);permX++){
      int binaryX[W];
      makeBinary(permX,W,binaryX);
 	  int result = 0;
  	  for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
        result += matrix[x][y] && binaryX[x] && binaryY[y];
        }
      }
      answer += result == K;
    }
  }
  printf("%d",answer);
  return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int inf = 1001001001;
 
int main(){

    ll n,ans=0;
    cin >> n;
    vector<ll> data(n);
    vector<ll> dp(n+1,0);
    dp.at(0)=0;
    rep(i,n){
        cin >> data.at(i);
    }
    rep(i,n+1){
        if(i==0) continue;
        dp.at(i)=dp.at(i-1)+data.at(i-1);
    }

    map<ll,ll> cnt;
    for(ll i=0; i<=n; i++){
        cnt[dp.at(i)]++;
    }

    for(auto it : cnt){
        ll num=it.second;
        ans+=num*(num-1)/2;
    }

    cout << ans << endl;
    
    
 
}

Measured memory_bytes: 15872
fun main(args: Array<String>) {
    val (n, t) = readLine()!!.split(' ').map(String::toLong)
    val tList = readLine()!!.split(' ').map(String::toLong)

    var result = 0L
    for (i in 0 until (tList.size - 1)) {
        result += Math.min(t, tList[i + 1] - tList[i])
    }
    println(result + t)
}


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

// {U}{INT,LONG,LLONG}_{MAX,MIN}
#define INF         INT_MAX/3
#define LLINF       LLONG_MAX/3
#define MOD         (1000000007LL)
#define MODA(a, b)  a=((a)+(b))%MOD
#define MODP(a, b)  a=((a)*(b))%MOD
#define inc(i, l, r)   for(int i=(l);i<(r);i++)
#define dec(i, l, r)   for(int i=(r)-1;i>=(l);i--)
#define pb          push_back
#define se          second
#define fi          first
#define mset(a, b)  memset(a, b, sizeof(a))

using LL  = long long;
using G   = vector<vector<int>>;

int di[] = {0, -1, 0, 1};
int dj[] = {1, 0, -1, 0};
// }}}

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
    int n;cin >> n;
    vector<int> a(n);
    inc(i, 0, n) cin >> a[i];
    sort(a.begin(), a.end());
    int ans1 = a[n-1];
    int ans2 = a[0];
    int mmin = 1000000005;
    inc(i, 0, n){
        int aa = a[i];
        if(ans1%2 == 0){
            int d = abs(ans1/2 - aa);
            if(d < mmin){
                ans2 = aa;
                mmin = d;
            }
        }else{
            int d = min(abs(ans1/2 - aa), abs(ans1/2 - aa + 1));
            if(d < mmin){
                ans2 = aa;
                mmin = d;
            }
        }
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}


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

int main(){
  int a, N, M;
  cin >> N >> M;
  vector<int> load(N);

  while(cin >> a){
    load[a - 1]++;
  }

  rep(i, N){
      cout << load[i] << endl;
  }
}


Measured memory_bytes: 256
/*
  AOJ #1568
  title:String Conversion
  @kankichi57301
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


char s[100001],t[100001];
int s_cnt[26],t_cnt[26];
int n;

int comp( const void * a , const void * b ) {

  if( *( int * )a > *( int * )b ) {
    return 1;
  }
  else
  if( *( int * )a == *( int * )b ) {
    return 0;
  }
  return -1;
}

int solve(int s_c[],int t_c[])
{
  int i,ret;

  qsort(s_c,26,sizeof(int),comp);
  qsort(t_c,26,sizeof(int),comp);

  for(i=0,ret=0;i<26;i++)
    if(s_c[i]>t_c[i])
      ret += (s_c[i]-t_c[i]);
  return(ret);
}
int main()
{
  int i,ret;
  
  
  scanf("%d",&n);
  scanf("%s",s);
  scanf("%s",t);
  for(i=0;i<n;i++)
    {
      s_cnt[s[i]-'a']++;
      t_cnt[t[i]-'a']++;
    }


  ret=solve(s_cnt,t_cnt);
  printf("%d\n",ret);
  return(0);
}



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

int modpow(int a,int n,int p){
    int res=1;
    while(n>0){
        if (n&1) res=res*a%p;
        a=a*a%p; n>>=1;
    }
    return res;
}

int modinv(int a,int p){
    return modpow(a,p-2,p);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int p; cin >> p;
    vector<int> a(p);
    for (int i=0;i<p;++i) cin >> a[i];
    for (int i=0;i<p;++i){
        int t=1;
        for (int j=0;j<p;++j) if (i!=j) (t*=(i-j+p)%p)%=p;
        a[i]*=modinv(t,p);
    }
    vector<vector<int>> dp(2,vector<int>(p+1,0));
    dp[0][0]=1;
    int cur=0,nxt=1;
    for (int i=0;i<p;++i){
        for (int j=0;j<p+1;++j){
            (dp[nxt][j]=p-dp[cur][j]*i%p)%=p;
            if (j) (dp[nxt][j]+=dp[cur][j-1])%=p;
        }
        swap(nxt,cur);
    }
    vector<int> inv(p),res(p,0);
    for (int i=0;i<p;++i) inv[i]=modinv(i,p);
    for (int i=0;i<p;++i){
        if (a[i]==0) continue;
        if (!i) for (int j=0;j<p;++j){
            (res[j]+=dp[cur][j+1]*a[i]%p)%=p;
        } else {
            (res[0]+=p-dp[cur][0]*inv[i]%p*a[i]%p)%=p;
            int pre=(p-dp[cur][0]*inv[i]%p)%p;
            for (int j=1;j<p;++j){
                (res[j]+=p-(dp[cur][j]-pre+p)%p*inv[i]%p*a[i]%p)%=p;
                pre=(p-(dp[cur][j]-pre+p)%p*inv[i]%p)%p;
            }
        }
    }
    for (int i=0;i<p;++i) cout << res[i] << (i!=p-1?' ':'\n');
}

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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(int i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define sz(x) ((int)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using vs  = vector<string>;
using pii = pair<int,int>;
constexpr ll inf = 1ll<<61;
constexpr ll mod = 1e9+7;
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T>void add(T &a, const T &b){a += b; a %= mod;}

signed main(){
  int a,b; cin >> a >> b;
  if(a <= 5){
    cout << 0 << endl;
  }else if(a <= 12){
    cout << b/2 << endl;
  }else{
    cout << b << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, mod = 1e9 + 7, inf = 0x3f3f3f3f;
struct e{
    ll x, y;
}a[55];
bool cmp(e a, e b){return a.x == b.x ? a.y < b.y : a.x < b.x;}
map<pair<ll, ll>, ll> mp;
bool p[55];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i].x >> a[i].y;
    sort(a, a + n, cmp);
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < n; ++j){
            if (i == j) continue;
            ++mp[make_pair(a[i].x - a[j].x, a[i].y - a[j].y)];
        }
    }
    ll cnt = 0, ansx = 0, ansy = 0;
    for (auto e : mp){
        if (e.second > cnt){
            cnt = e.second;
            ansx = e.first.first;
            ansy = e.first.second;
        }
    }
    
    cout << n - cnt << endl;
    return 0;
}


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

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define REP2(i,n) for(int i=0;i<(int)(n);i++)
#define REP3(i,m,n) for(int i=m;i<(int)(n);i++)
#define REP4(i,m,n,s) for(int i=m;(s>0 and i<(int)(n)) or (s<0 and i>(int)(n));i+=s)
#define REP(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define REPIT(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define PIS(x) printf("%d ",x)
#define PN() putchar('\n')
#define PRINTARR(a,b) for(int i=0;(a+i)!=(b);i++){cout << *(a+i) << " ";}PN();
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define MT make_tuple

typedef pair<int, int> PII;
typedef tuple<int, int, int> T3I;
typedef long long LL;
typedef unsigned long long ULL;

void RI() {}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d", &head);
    RI(tail...);
}
void RLL() {}
template<typename... T>
void RLL( LL& head, T&... tail ) {
    scanf("%lld", &head);
    RLL(tail...);
}
void print() {putchar('\n');}
template<typename T, typename... U>
void print(T head, U... tail) {
    cout << head << " ";
    print(tail...);
}

const int MOD = 1000000007;
#define MAX_N 100005

int A[MAX_N];
int B[MAX_N];

int msb(int a) {
    return 32 - __builtin_clz(a);
}

int main()
{
    int N, K;
    RI(N, K);
    REP(i, N) {
        RI(A[i], B[i]);
    }
    int msbK = msb(K);

    LL ans = 0;
    REP(i, N) {
        if((A[i] | K) <= K) {
            ans += B[i];
        }
    }

    REP(i, msbK+1) {
        if((K & (1 << i)) == 0) {
            continue;
        }
        int KK = (K ^ (1 << i)) | ((1 << i) - 1);
        LL ans0 = 0;
        REP(i, N) {
            if((A[i] | KK) <= KK) {
                ans0 += B[i];
            }
        }
        ans = max(ans0, ans);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll=int64_t;
int main(){
  ll n,x,m,i,j,d,q,r,ans;
  cin>>n>>x>>m;
  vector<ll> a(m+1),b(m+2);
  a[0]=x; b[1]=x;
  set<ll> s={x};
  for(i=1;i<m+1;i++){
    a[i]=a[i-1]*a[i-1]%m;
    b[i+1]=b[i]+a[i];
    if(i==n-1){
      cout<<b[n]<<endl;
      return 0;
    }
    else if(s.count(a[i])) break;
    else s.insert(a[i]);
  }
  for(j=0;j<i;j++) if(a[j]==a[i]) break;
  d=i-j;
  q=(n-i)/d;
  r=(n-i)%d;
  ans=b[i]+q*(b[i+1]-b[j+1]);
  if(r>0) ans+=b[j+r]-b[j];
  cout<<ans<<endl;
}

Measured memory_bytes: 7212
package main

import (
	"fmt"
)

const (
	 	Cake	= 4
		Donut	= 7
)

func main() {
	var N int
	
	fmt.Scan(&N)

	value := N

	for true {
		if value < 0 {
			fmt.Println("No")
			break
		}

		if MultiplesOf(Cake,value) || MultiplesOf(Donut,value) {
			fmt.Println("Yes")
			break
		}
		
		value -= Donut
	}

}

func MultiplesOf(multiple,number int) bool{
	if iToB(number % multiple) { 
		return false
	}
	return true
}

func iToB(num int) bool {
	if num != 0 {
		return true
	} else {
		return false
	}
}


Measured memory_bytes: 512
use std::fs;
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: ident,2) => {
        (parse!($it), parse!($it))
    };
    ($it: ident,3) => {
        (parse!($it), parse!($it), parse!($it))
    };
    ($it: ident,4) => {
        (parse!($it), parse!($it), parse!($it), parse!($it))
    };
    ($it: ident, $n: expr) => {
        (&mut $it).take($n).map(|e| e.parse().unwrap()).collect();
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    let n = parse!(it);
    let mut a: Vec<i64> = parse!(it, n);
    let Mi = a.iter().enumerate().max_by_key(|&(i, &x)| x).unwrap().0;
    let mi = a.iter().enumerate().min_by_key(|&(i, &x)| x).unwrap().0;
    println!("{}", 2 * (n - 1));
    if a[Mi] >= -a[mi] {
        for i in 0..n {
            if i == Mi {
                continue;
            }
            println!("{} {}", Mi + 1, i + 1);
            a[i] += a[Mi]
        }
        for i in 1..n {
            println!("{} {}", i, i + 1);
            a[i] += a[i - 1]
        }
    } else {
        for i in 0..n {
            if i == mi {
                continue;
            }
            println!("{} {}", mi + 1, i + 1);
            a[i] += a[mi]
        }
        for i in (1..n).rev() {
            println!("{} {}", i + 1, i);
            a[i] += a[i - 1];
        }
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


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

int main() {
  int n;
  cin >> n;
  
  vector<int> kusi(2 * n);
  
  for (int i = 0; i < n; i++){
    cin >> kusi.at(2 * i) >> kusi.at(2 * i + 1);
  }
  
  sort(kusi.begin(), kusi.end());
  
  int ans = 0;
  
  for (int i = 0; i < n; i++){
    
    ans += min(kusi.at(2 * i), kusi.at(2 * i + 1));
    
  }
  
  cout << ans << endl;
  
}



Measured memory_bytes: 3548
let isPrime n =
    if n < 2 then false
    elif n = 2 then true
    else
        let r = n |> float |> sqrt |> ceil |> int
        [for i in 2..r -> n % i = 0] |> List.contains true |> not

let rec loop n = if isPrime n then n else loop (n + 1)

stdin.ReadLine() |> int |> loop |> printfn "%d"

Measured memory_bytes: 14940
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/
#define N 101010
void build(){

}
LL n , a[ N ];
vector<int> v[ N ];
void init(){
  n = getint();
  for( int i = 1 ; i <= n ; i ++ )
    a[ i ] = getint();
  for( int i = 1 ; i < n ; i ++ ){
    int ai = getint();
    int bi = getint();
    v[ ai ].push_back( bi );
    v[ bi ].push_back( ai );
  }
}
LL go( int now , int prt ){
  bool leaf = true;
  LL ret = 0 , mx = 0 , res = 0;
  for( int son : v[ now ] ){
    if( son == prt ) continue;
    leaf = false;
    LL tmp = go( son , now );
    if( tmp < 0 ){
      puts( "NO" );
      Bye;
    }
    LL mr = min( ret , tmp );
    mr = min( mr , ( res + tmp ) / 2 );
    ret += tmp;
    mx += mr;
    res = res + tmp - mr - mr;
  }
  if( leaf ) return a[ now ];
  if( ret < a[ now ] || ret - a[ now ] > mx ){
    puts( "NO" );
    Bye;
  }
  return ret - 2 * ( ret - a[ now ] );
}
void solve(){
  int rt = -1;
  for( int i = 1 ; i <= n ; i ++ )
    if( v[ i ].size() > 1u ){
      rt = i;
      break;
    }
  if( rt == -1 ){
    puts( a[ 1 ] == a[ 2 ] ? "YES" : "NO" );
    Bye;
  }
  if( go( rt , rt ) == 0 )
    puts( "YES" );
  else
    puts( "NO" );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 13184
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

ll solve(string &s1,string &s2,int k)
{
    ll ans=0;
    for(int i=0;i<s2.size();i++)
    {
        if(s2[i]!=s1[i+k]) ans++;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    // cin>>t;
    while(t--)
    {
        string s1,s2;cin>>s1>>s2;
        ll min_=s1.size();
        for(int i=0;i<s1.size()-s2.size()+1;i++)
        {
            min_=min(min_,solve(s1,s2,i));
        }
        cout<<min_;
    }
}

Measured memory_bytes: 3656
#include <bits/stdc++.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

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 = 1e18;
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

bool cmp(pair<pii, ll> a, pair<pii, ll> b) {
  if (a.first.first + a.first.second != b.first.first + b.first.second) {
    return a.first.first + a.first.second < b.first.first + b.first.second;
  }
  else {
    return a.second > b.second;
  }
}

int main() {
  int n;
  cin >> n;
  vector<pair<pii, ll> > wsv(n);
  rep (i, n) {
    cin >> wsv[i].first.first >> wsv[i].first.second >> wsv[i].second;
  }
  sort(all(wsv), cmp);
  //DEBUG_VEC(wsv);
  int W = 20000;
  vll dp(n + 1, vl(W + 1, -INF));
  dp[0][0] = 0;
  rep (i, n) {
    int w = wsv[i].first.first, s = wsv[i].first.second, v = wsv[i].second;
    rep (j, W + 1) {
      dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
      if (j > s) continue;
      chmax(dp[i + 1][j + w], dp[i][j] + v);
    }
  }
  ll ans = -INF;
  rep (j, W + 1) {
    chmax(ans, dp[n][j]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 160640
#include <iostream>

using namespace std;

int main(void){
  string S;
  cin >> S;
  //入力終了

  int N = S.size();
  
  //最初に，末尾の文字を消去しておく
  S.erase(N-1);
  
  for(int i=0; i<N; i++){
    //1文字ずつ末尾から消していく
    S.erase(N-1-i);
    //文字列の長さが奇数なら偶文字列でない
    if(S.size()%2 == 1)
      continue;

    //
    bool flag = true;

    int n = S.size();
    //偶文字列かの判定
    for(int i=0; i<n/2; i++){
      if(S[i] != S[i+n/2])
	flag = false;
    }
    
    //解答
    if(flag){
      cout << n << endl;
      return 0;
    }
  }
  
  return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[305][305];
int main()
{
    int a,b,c,d,e,f;
    scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
    if(a>b){int t=a;a=b;b=t;}
    int m=a*e,sum=0,x=a;
    for(int i=0;i<=m/c;i++)
    {
        for(int j=0;j<=m/d;j++)
        {
            if(i*c+j*d>m)continue;
            if(a*100+i*c+j*d>f)continue;
            if((i*c+j*d)>sum) sum=i*c+j*d;
        }
    }
    int y=b/a*sum;
    m=b*e;
    for(int i=0;i<=m/c;i++)
    {
        for(int j=0;j<=m/d;j++)
        {
            if(i*c+j*d>m)continue;
            if(b*100+i*c+j*d>f)continue;
            if(i*c+j*d>y&&i*c+j*d>sum)
            {sum=i*c+j*d;x=b;}
        }
    }
    if((a+b)*100<f)
    {
        m=(a+b)*e;
        y=(a+b)/x*sum;
        for(int i=0;i<=m/c;i++)
        {
            for(int j=0;j<=m/d;j++)
            {
                if(i*c+j*d>m)continue;
                if((a+b)*100+i*c+j*d>f)continue;
                if(i*c+j*d>y&&i*c+j*d>sum)
                {sum=i*c+j*d;x=a+b;}
            }
        }
    }
    cout<<x*100+sum<<" "<<sum<<endl;
}

Measured memory_bytes: 256
A, B = map(int, input().split())

Min8 = A // 0.08 + 1
Min10 = B // 0.1 + 1

Max10 = (B+1) // 0.1
Max8 = (A+1) // 0.08

if Min10 >= Min8 and Max8 >= Min10:
    print(int(Min10))
elif Min8 >= Min10 and Max10 >= Min8:
    print(int(Min8))
else:
    print(-1)


Measured memory_bytes: 3064
fun main(args: Array<String>) {
    val (T1, T2) = readInputLine().split(" ").map { it.toLong() }
    val (A1, A2) = readInputLine().split(" ").map { it.toLong() }
    val (B1, B2) = readInputLine().split(" ").map { it.toLong() }
    
    var P = (A1 - B1) * T1
    var Q = (A2 - B2) * T2
    
    if (P > 0L) {
        P *= -1L
        Q *= -1L
    }
    
    if (P + Q < 0L) {
        println(0)
    } else if (P + Q == 0L) {
        println("infinity")
    } else {
        val S = P * -1L / (P + Q)
        val T = P * -1L % (P + Q)
        
        if (T == 0L) {
            println(S * 2L)
        } else {
            println(S * 2L + 1L)
        }
    }
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 37996
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i <= (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int main()
{
	int n, Y;
	cin >> n >> Y;
	int num1 = Y / 10000;
	int num2 = Y / 5000;
	rep(x,num1)rep(y,num2){
		int res = Y - (10000 * x + 5000 * y);
		if(res>=0 && res%1000==0 && x+y+(res/1000)==n){ 
			int z = res/1000;
			printf("%d %d %d\n", x, y, z); 
			return 0;
		}
	}
	printf("-1 -1 -1\n");
}


Measured memory_bytes: 384
#include <iostream>
#include <string> 
using namespace std; 
int main(){

 int a=0,b=0;
 int ans=0;
   
  cin >> a >> b ;
  ans = (a * b) % 2;
  if(ans == 1){
  	cout << "Odd" << endl;
  }else{
  	cout << "Even" << endl;
  }
  

}


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

using namespace std; //ごめんなさい
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()
#define rep(i,N) for(int i=0;i<N;i++)

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

  int N;
  cin>>N;
  vector<int>A(N);
  for(int i=0;i<N;i++)cin>>A[i];
  vector<int>dp(N,-1);
  for(int i=0;i<N;i++){
    int l=-1,r=N,m;
    while(r-l>1){
      m=(r+l)/2;
      if(dp[m]>=A[i])l=m;
      else r=m;
    }
    dp[r]=max(A[i],dp[r]);
    dp[0]=max(dp[0],A[i]);
  }
  ll ans=0;
  for(int i=0;i<N;i++)if(dp[i]!=-1)ans=i;
  cout<<ans+1<<endl;
  return 0;
}


Measured memory_bytes: 1024
n,m=map(int,input().split())

A=[[0 for i in range(m)] for j in range(n)]
b=[0 for i in range(m)]

for i in range(n):
    A[i]=list(map(int,input().split()))

for j in range(m):
    b[j]=int(input())

for j in range(n):
    result=0
    for i in range(m):
        result+=A[j][i]*b[i]
    print(result)


Measured memory_bytes: 6024
import java.util.*;

class Main{
    void solve(){
        Scanner scan = new Scanner(System.in);
        double t = scan.nextInt();
        double x = scan.nextInt();
        System.out.println(t / x);
        scan.close();
    }
    
    public static void main(String[] args){
        new Main().solve();
    }
}


Measured memory_bytes: 27212
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,n;
    while(cin>>a>>b>>n){
        int sum=0;
        a%=b;
        for(int i=1;i<=n;i++){
            a*=10;
            sum+=a/b;
            a%=b;
                }

        cout<<sum<<endl;
    }
}

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

int main(){
    int N; cin >> N;
    vector<int> L(N);
    for(int i = 0; i < N; ++i) cin >> L[i];
    sort(L.begin(), L.end());
    int ans = 0;
    for(int i = 0; i < N-2; ++i){
        for(int j = i+1; j < N-1; ++j){
            for(int k = j+1; k < N; ++k){
                if(L[k] >= L[i] + L[j]) break;
                else{
                    if((L[j]-L[i])< L[k]){
                        ans++;
                    }
                }
            }
        }
    }
    cout << ans << endl;
}

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

int main(){
  int X;
  bool B = false;
  cin >> X;

  do{
    if(X==2)
    B = true;
    else if(!(X<2)){
      if(!(X%2==0)){
        double sqrtNum = sqrt(X);
        for(int i=3;i<=sqrtNum;i+=2){
          if(X%i==0){
            B = false;
            X++;
            break;
          }else
          B = true;
        }
      }else
      X++;
    }else
    X++;
  }while(B==false);
  cout << X << endl;
}


Measured memory_bytes: 256
"use strict";
function Main(input) {
    let cin = new Inputer(input);
    let N = cin.getInt(), V = cin.getIntArray(N), C = cin.getIntArray(N);
    let VC = V.map((v, i) => v - C[i]);
    let ans = VC.reduce((ac, v) => ac + (v > 0 ? v : 0), 0);
    console.log(ans);
}
class Inputer{constructor(t){if(typeof t=='undefined')throw new Error('引数（stdin）を省略できません！');this.cnt=0,this.items=t.split(/\n|\s/)}getInt(){return this.items[this.cnt++]-0}getIntArray(t){if(typeof t=='undefined')throw new Error('引数（1以上）を省略できません！');let r=new Array(t);for(let e=0;e<t;e++)r[e]=this.getInt();return r}getStr(){return this.items[this.cnt++]}getStrArray(t){if(typeof t=='undefined')throw new Error('引数（1以上）を省略できません！');let r=new Array(t);for(let e=0;e<t;e++)r[e]=this.getStr();return r}}
if (typeof window == "undefined") Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7628