akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;


int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
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;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


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

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

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

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



int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	vector<vector<int>> c(3, vector <int>(3));
	
	
	rep(i, 0, 3) {
		rep(j, 0, 3) {
			cin >> c[i][j];
		}	
	}

	vector<int> a(3);
	vector<int> b(3);

	a[0] = 0;
	b[0] = c[0][0] - a[0];
	b[1] = c[0][1] - a[0];
	b[2] = c[0][2] - a[0];

	a[1] = c[1][0] - b[0];
	a[2] = c[2][0] - b[0];

	rep(i, 0, 3) {
		rep(j, 0, 3) {
			if (c[i][j] != (a[i] + b[j])) {
				cout << "No" << endl;
				return 0;
			}
				
		}
	}

	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric>
#include <set>
#include <cstdlib>
#include <queue>
#include <map>
#include <cstdio>

using namespace std;

typedef long long llint;
typedef long double ld;
#define inf 1e18
#define mod 1000000007
//priority_queue<llint,vector<llint>,greater<llint>> que;
//priority_queue<llint> q;

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

llint W,H,x,y,r;

void solve(){
  cin >> W >> H >> x >> y >> r;
  if(x-r<0 || y-r<0 || x+r>W || y+r>H) cout << "No";
  else cout << "Yes";
  cout << endl;
}

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



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

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> V(N), C(N);
    for(int i=0;i<N;i++)cin >> V.at(i);
    for(int i=0;i<N;i++)cin >> C.at(i);

    vector<int> profit(N);
    for(int i=0;i<N;i++)profit.at(i) = V.at(i) - C.at(i);
    int sum_profit = 0;
    for(int i=0;i<N;i++){
        if(profit.at(i) > 0)sum_profit += profit.at(i);
    }

    cout << sum_profit << endl;
}

Measured memory_bytes: 256
def fun():
    N = int(input())
    W = []
    for n in range(N):
        W.append(input())
    for i, w in enumerate(W):
        if i==0:
            prev_w = w
            continue
        for wn in W[:i]:
            if w == wn:
                print('No')
                return 
        if prev_w[-1] != w[0]:
            print('No')
            return
        prev_w = w
    print('Yes')
    return

fun()


Measured memory_bytes: 3064
n = int(input())
count = 0
check = 0
for i in range(1,n+1):
    a, b = map(int, input().split())
    if a == b:
        count+=1
        if count >= 3:
            check = 1
    elif a != b:
        count = 0

if check == 1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<int(n);++i)
#define rep1(i,n) for(int i=1;i<=int(n);++i)
#define all(a) a.begin(),a.end()
#define lb(s,x) lower_bound(all(s),x)-s.begin()
#define debug(x) cout<<#x<<": "<<x<<endl
#define INF 1e9

typedef pair<int,int> Node; // v,com
typedef pair<int,Node> P;  // dp[Node],Node
typedef P Edge;           // int,Node

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        return (h1<<10)^h2;
    }
};

priority_queue<P,vector<P>,greater<P>> qu;
unordered_map<Node,vector<Edge>,pair_hash> g;
unordered_map<Node,int,pair_hash> dp;

int N,M;

void dijkstra(Node start){
    qu.push({dp[start]=0,start});
    while(qu.size()){
        P pr=qu.top(); qu.pop();
        Node v = pr.second;
        if(v==make_pair(N-1,-1))return;
        if(dp[v] < pr.first)continue;

        for(Edge e:g[v]){
            Node to = e.second;
            int cost = e.first;
            if(dp.count(to)==0 || dp[to] > dp[v]+cost){
                dp[to] = dp[v]+cost;
                qu.push({dp[to],to});
            }
        }
    }
}


int main(void){
    cin>>N>>M;
    rep(i,M){
        int p,q,c;
        scanf("%d %d %d",&p,&q,&c);
        p--,q--;
        if(g.count({p,c})==0){
            g[{p,c}].push_back({0,{p,-1}});
            // g[{p,c}] = {};
            g[{p,-1}].push_back({1,{p,c}});
            // g[{p,-1}] = {};
        }
        if(g.count({q,c})==0){
            g[{q,c}].push_back({0,{q,-1}});
            // g[{q,c}] = {};
            g[{q,-1}].push_back({1,{q,c}});
            // g[{q,-1}] = {};
        }
        g[{p,c}].push_back({0,{q,c}});
        g[{q,c}].push_back({0,{p,c}});
        // g[{p,c}] = {};
        // g[{q,c}] = {};
    }

    // cout<<"pushback done"<<endl;

    dijkstra({0,-1});
    if(dp.count({N-1,-1})==0){
        cout<<-1<<endl;
    }else {
        cout<<dp[{N-1,-1}]<<endl;
    }
    return 0;
}


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

#define INF 100100100
#define MOD 1000000007

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

int main(int argc, char const* argv[]){
   ios::sync_with_stdio(false);
   cin.tie(0);

   int N,i;
   cin>>N>>i;
   cout<<N-i+1<<endl;

   return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n)cin >> a[i];
    vector<ll> srt(n);
    iota(ALL(srt), 0);
    sort(ALL(srt), [&](int x, int y){
        return a[x] < a[y];
    });
    ll ans = 0;
    for(int i = 0; i < n; i+=2){
        if(srt[i]&1)ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll calc_keta(ll n){
    if(n==0) return 1;

    ll keta = 0;
    while(n!=0){
        keta++;
        n /= 10;
    }
    return keta;
}

ll my_pow(ll a, ll n){
    ll ret = 1;
    FOR(i, 0, n){
        ret *= a;
    }
    return ret;
}

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

    // input
    ll N;
    cin >> N;

    ll keta = calc_keta(N);
    
    ll c = N / my_pow(10, keta-1);
    
    ll a = my_pow(10, keta-1);
    ll rest = N % a;
    
    if(rest == my_pow(10, keta-1) - 1){
        // c999999
        p(c + 9 * (keta-1));
    }else{
        p(c + 9 * (keta-1) - 1);
    }

    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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; }
template<typename T>
struct BIT{
    //1-index
    //0-indexで取ると無限ループする
    private:
    V<T> arr;
    int n;

    public:
    BIT(int siz){
        n=siz;
        arr.assign(n+1,0);
    }
    //一点更新 aにvを加える
    void add(T a,T v){
        //x+=(x&-x) 初項a,それ以降a<=2^Nが列挙
        for(T x=a;x<=n;x+=(x&-x)){
            arr[x]+=v;
        }
    }
    T sum(T a){
        // 1からaまでの区間和
        T ret=0;
        for(T x=a;x>0;x-=(x&-x))ret+=arr[x];
        return ret;
    }
    T lower_bound(T w){// 区間和がw以上となる最小のindを返す
        if(w<=0)return 0;
        T x,r=1;//xは横の位置,rはrank
        while(r<n)r<<=1;
        for(T k=r;k>0;k>>=1){
            if(x+k<=n&&arr[x+r]<w){
                w-=arr[x+r];
                x+=k;
            }
        }
        return x+1;
    }
    T get(T x){//x番目に大きい数
        if(x<=0) return 0;
        T N=1;
        while(N*2<=n)N*=2;
        T v=0;
        for(T i=N;i>0;i/=2){
            if(v+i<=n&&arr[v+i]<x){
                x-=arr[v+i];
                v+=i;
            }
        }
        return v+1;
    }
    T query(int l,int r){
        return sum(r)-sum(l);
    }
};
ll n;
V<ll> a(n);
V<int> d;
ll C(ll x){
    d.assign(n,0);
    BIT<ll> bit(2*n+50);
    for(int i=0;i<n;i++){
        if(a[i]>x)d[i]=-1;
        else d[i]=1;
    }
    int now=10;
    ll res=0;
    for(int i=0;i<n;i++){
        bit.add(n+now,1);
        now+=d[i];
        res+=bit.sum(n+now-1);
    }
    return res;
}
int main(){
    cin>>n;
    a.resize(n);
    for(int i=0;i<n;i++)cin>>a[i];
    ll l=0,r=1e10;
    while(r-l>1){
        ll mid=(l+r)/2;
        if(C(mid)>(n+1)*n/2/2)r=mid;
        else l=mid;
    }
    cout<<r<<"\n";
}

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

const int DIM = 105;

int arr[DIM], ans[DIM];

int main(void) {
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i]; }
	for (int p = n; p >= 1; --p) {
		bool ok = false;
		for (int i = p; i >= 1; --i) {
			if (arr[i] == i) {
				ans[p] = i; ok = true;
				for (int j = i + 1; j <= p; ++j) {
					arr[j - 1] = arr[j]; }
				ok = true; break; } }
		if (!ok) {
			cout << -1; return 0; } }
	for (int i = 1; i <= n; ++i) {
		cout << ans[i] << 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;
    }else if(a < b){
        cout << "a < b" << endl;
    }else if(a == b){
        cout << "a == b" << endl;
    }

    return 0;
}



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

int main(){
  int n, m, c, cnt=0;
  cin >> n >> m >> c;
  vector<int>a(m), b(m);
  for(int i=0; i<m; i++)cin >> a[i];
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++)cin >> b[j];
    if(inner_product(a.begin(), a.end(), b.begin(), c)>0)cnt++;
  }
  cout << cnt;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
ll n;
int main(){
    int n;
    cin>>n;
    vector<int> v(n,0);
    rep(i,n) cin>>v[i];
    int cnt=1;
    int min=v[0];
    rep(i,n){
        if(i==0){
            continue;
        }
        else{
            if(v[i]>min) continue;
            else{
                min=v[i];
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);i++)

int main(){
    string a,b;
    cin>>a>>b;
    if(a.size()!=b.size()){
        if(a.size()>b.size())cout<<"GREATER"<<endl;
        else cout<<"LESS"<<endl;
        return 0;
    }
    for(int i=0;i<a.size();i++){
        if(a[i]!=b[i]){
            if(a[i]>b[i])cout<<"GREATER"<<endl;
            else cout<<"LESS"<<endl;
            return 0;
        }
    }
    cout<<"EQUAL"<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

#define N 5

void BubbleSort(int *a, int n);


int main(void){
  int i, num[N];

  for(i = 0; i < N; i++){
    scanf("%d", &num[i]);
  }
  BubbleSort(num, N);
  printf("%d", num[0]);
  for(i = 1; i < N; i++){
    printf(" %d", num[i]);
  }
  printf("\n");
  return 0;
}


void BubbleSort(int *a, int n){
  int flag, i, j, temp;

  for(i = n; i > 0; i--){
    flag = 0;
    for(j = 1; j < i; j++){
      if(a[j-1] < a[j]){
	temp = a[j-1];
	a[j-1] = a[j];
	a[j] = temp;
	flag = 1;
      }
    }
    if(flag == 0)  break;
  }
}

Measured memory_bytes: 600
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

const int MAX_N = 100000;
const int MAX_E = 100000;
struct edge{ ll from, to, cost; };
edge es[MAX_E]; //辺
ll d[MAX_N]; //最短距離
ll n,m; //頂点数、辺数

bool bellmanford(int s){
    rep(i,n) d[i] = INF;
    d[0] = 0;
    rep(i,n){
        bool update = false;
        rep(j,m){
            edge e = es[j];
            if (d[e.from] == INF) continue;
            if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                update = true;
            }
        }
    if (!update) break;
    }
    bool negative[MAX_N];
    rep(i,n) negative[i] = false;
    rep(i,n) {
        rep(j,m){
            edge e = es[j];
            if (d[e.from] == INF) continue;
            if (d[e.to] > d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
                negative[e.to] = true;
            }
            if (negative[e.from]) negative[e.to] = true;
        }
    }
    if (negative[n-1]) return false;
    return true;
}

int main(){
    cin >> n >> m;
    ll a,b,c;
    rep(i,m){
       cin >> a >> b >> c;
       edge e = {a-1,b-1,-c};
       es[i] = e;
    }
    bool t = bellmanford(0);
    if (t){
        cout << -d[n-1] << endl;
    }else{
        cout << "inf" << endl;
    }

}




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

int main() {
  char c;
  cin >> c;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cout <<"vowel"<<endl;
  else cout <<"consonant"<<endl;
}


Measured memory_bytes: 256
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def f(S, T):
    N = len(S)
    F = [[0 for _ in range(N)] for __ in range(N)]
    
    for i in range(N):
        for j in range(N):
            SS = S[i]
            TT = T[j]
            if TT == (0, 0):
                F[i][j] = 1 if SS == (0, 1) else 0
            elif TT == (0, 1):
                if SS == (1, 0):
                    return None
                F[i][j] = 1
            elif TT == (1, 0):
                if SS == (0, 1):
                    return None
                F[i][j] = 0
            else:
                F[i][j] = 0 if SS == (1, 0) else 1

    return F


def main():
    N, L = read_values()
    A = read_list()

    r = 0
    for i in range(N - 1):
        if A[i] + A[i + 1] >= L:
            r = i
            break
    else:
        print("Impossible")
        return

    print("Possible")
    
    for i in range(r):
        print(i + 1)
    for i in range(N - 2, r - 1, -1):
        print(i + 1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 15980
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}

int main() {
  int a, b;
  cin >> a >> b;
  bool exist = 0;
  REPC(c, 1, 3) {
    if ((a * b * c) % 2 == 1) {
      exist = 1;
      break;
    }
  }
  Yes(exist);

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

int main() {
  int N, A, B; cin >> N >> A >> B;
  string S; cin >> S;

  int na = 0, nb = 0;
  rep(i, N) {
    string result = "No";
    if (S[i]=='a') {
      if (na+nb<A+B) {
        result = "Yes";
        na++;
      }
    }
    else if (S[i]=='b') {
      if (na+nb<A+B && nb<B) { 
        result = "Yes";
        nb++;
      }
    }
    cout << result << endl;
  }
  return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;
const int LOG_N = 17;

vector<int> G[MAX_N];

int par[LOG_N][MAX_N];
int depth[MAX_N];

void dfs(int u,int p,int d)
{
    par[0][u] = p;
    depth[u] = d;
    rep(i,G[u].size()){
        if(G[u][i] != p){
            dfs(G[u][i],u,d+1);
        }
    }
}

int lca(int u,int v)
{
    if(depth[u] > depth[v]){
        swap(u,v);
    }
    rep(i,LOG_N){
        if((depth[v] - depth[u]) >> i & 1){
            v = par[i][v];
        }
    }
    if(u == v){
        return u;
    }
    for(int i=LOG_N-1;i>=0;i--){
        if(par[i][u] != par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}

int main()
{
    int n;
    cin >> n;
    rep(i,n){
        int m;
        scanf("%d",&m);
        rep(j,m){
            int x;
            scanf("%d",&x);
            G[i].pb(x);
        }
    }
    dfs(0,-1,0);
    rep(i,LOG_N-1){
        rep(j,n){
            if(par[i][j] < 0){
                par[i+1][j] = -1;
            }else{
                par[i+1][j] = par[i][par[i][j]];
            }
        }
    }
    int q;
    cin >> q;
    rep(i,q){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}

Measured memory_bytes: 20264
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int cnt[3];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s; cin>>s;
	for(int i=0;i<s.length();i++) cnt[s[i]-'a']++;
	sort(cnt,cnt+3);
	if(cnt[2]-cnt[0]>1)
	{
		cout<<"NO\n";
	}
	else
	{
		cout<<"YES\n";
	}
}	


Measured memory_bytes: 512
/*
 * “My code isn't a mess! It's organised chaos!”
 */

/*
 * short     2^15-1 ~ 3e4
 * int       2^31-1 ~ 2e9
 * long x86  2^31-1 ~ 2e9
 * long long 2^63-1 ~ 9e18
 */

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define fr(a,b) for (int a=0; a<b; ++a)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007ll;
const int infty = numeric_limits<int>::max();
struct _{_(){ios_base::Init i;ios_base::sync_with_stdio(0);cin.tie(0);}}_;
void err() {cerr << endl;}
template<typename T, typename... Ts>
void err(T a, Ts... as) {cerr << a << ' '; err(as...);}

 /*
  * Всегда прогоняй макс-тест перед 
  * нажатием «Отослать». Всегда.
  */ 

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

    cout << (a+b)%24 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;

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 _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()

const int mod = 1e9+7;

int d;
vector<int> c;
vector<vector<int>> s;
vector<int> last(26, 0);

ll calculate(int date, int choice) {
    ll ans = 0;
    ans += s[date][choice];
    last[choice] = -1;
    rep (i, 26) {
        last[i]++;
        ans -= last[i] * c[i];

    }
    return ans;
}

vector<int> argsort(vector<int> v) {
    vector<int> indices(v.size());
    iota(indices.begin(), indices.end(), 0);
    // ソートする。
    sort(indices.begin(), indices.end(), [&v](int i1, int i2) {
        return v[i1] < v[i2];
    });
    return indices;
}

int greedy(int date) {
    vector<int> score(26, 0);
    rep (i, 26) {
        score[i] = s[date][i] + last[i] * c[i];
    }
    vector<int> indices = argsort(score);
    last[indices[25]] = 0;
    return indices[25];
}

int main() {
    cin >> d;
    c.resize(26);
    rep (i, c.size()) {
        scanf("%d", &c[i]);
    }
    s.resize(d, vector<int>(26));
    rep (i, d) {
        rep (j, c.size()) {
            cin >> s[i][j];
        }
    }
    ll default_score = 0;
    vector<int> default_res(d);
    rep (i, d) {
        default_res[i] = greedy(i);
        default_score += calculate(i, default_res[i]);
    }
    random_device rnd;
    mt19937 mt(rnd());
    uniform_int_distribution<> rand26(0, 25), rand365(0, 364);

    rep (i, 120000) {
        int p = rand26(mt);
        int q = rand365(mt);
        auto changed_res = default_res;
        changed_res[q] = p;
        ll changed_score = 0;
        rep (j, 26) {
            last[j] = 0;
        }
        rep (j, d) {
            changed_score += calculate(j, changed_res[j]);
        }
        if (changed_score > default_score) {
            default_res = changed_res;
            default_score = changed_score;
        }
    }

    rep (i, d) {
        cout << default_res[i] + 1 << endl;
    }
}




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

int main(){
  int n;
  string s;
  cin>>n>>s;
  
  int x=0;
  int ans=0;
  
  for(int i=0;i<size(s)/sizeof(char);i++){
    if(s[i]=='I')x++;
    else x--;
    
    ans=max(ans,x);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3624
# n = int(input())
s = input()
# a, b = map(int, input().split())
# l = list(map(int, input().split()))

a = (len(s) - 1) // 2
b = (len(s) + 3) // 2 - 1
aa = s[0: a]
bb = s[b:]

if aa == bb:
    print("Yes")
else:
    print("No")


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}

    mint operator-() const { return mint(-x); }

    mint &operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }

    mint &operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod - 2);
    }

    mint &operator/=(const mint a) {
        return (*this) *= a.inv();
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }
};

struct combination {
    vector<mint> fact, ifact;

    combination(int n) : fact(n + 1), ifact(n + 1) {
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }

    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n] * ifact[k] * ifact[n - k];
    }
} comb(2000005);

mint f(int n, int k) {
    if (n < 0) return 0;
    // nPk = nCk * k!
    mint res = comb(n, k);
    res *= comb.fact[k];
    return res;
}

ll sum(ll l, ll r) {
    return (l + r) * (r - l + 1) / 2;
}

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

    mint ans;
    for (int i = K; i <= N + 1; i++) {
        ll l = sum(0, i - 1);
        ll r = sum(N - i + 1, N);
        ans += r - l + 1;
    }
    cout << ans.x << endl;
}


Measured memory_bytes: 34192
from collections import defaultdict
from collections import Counter

N,M = map(int,input().split())

A = defaultdict(list)
D = defaultdict(list)
DLen = defaultdict(int)
for i in range(N+M-1):
    a,b = map(int,input().split())
    A[a].append(b)
    #D[b].append(a)
    DLen[b] += 1

start = 0
for i in range(1,N+1):
    if DLen[i] == 0:
        start = i
        break
        
D[start].append(0)
Search = [(start,A[start])]
Stepd = [start]

while Search:
    now,NEX = Search.pop()
    for s in NEX:
        if DLen[s]>=2:
            DLen[s] -= 1
        else:
            D[s] = [now]
            Stepd.append(s)
            Search.append((s,A[s]))
            
for i in range(1,N+1):
    print(D[i][0])

Measured memory_bytes: 54668
#include <bits/stdc++.h>
using namespace std;
#define senor_SR ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

typedef long long ll;
typedef long double ld;
typedef int32_t i32;

#define int long long
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define pf push_front

#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define RFOR(i,a,b) for(ll i=a;i>=b;i--)
#define FILL(a,b,c) for(ll i=0;i<c;i++) a[i]=b;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()

#define endl "\n"
#define setpri(x) setprecision(x)
#define vp(x) cout<<#x<<" : "<< (x)<<" | "
#define yes cout<<"Yes"<<endl
#define no cout<<"No"<<endl
#define farr(a,n) for(long long i=0;i<n;i++) cin>>a[i];
#define fvec(vec,n) for(long long i=0;i<n;i++) {ll tmp;cin>>tmp;vec.pb(tmp);}
#define parr(a,n) for(long long i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;
#define prvec(v) for(long long i=v.size()-1;i>=0;i--) cout<<v[i]<<" "; cout<<endl;
#define pvecpair(v) for(long long i=0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<endl;

#define INF 1e17+4
#define MINF 
#define MAX_INT 100000
#define MOD 1000000007
ll mod(ll n) { n %= MOD; if (n < 0) return n + MOD; else return n;}
// vector<int> adj[1000002];
// int vis[1000002],dep[1000002],siz[1000002];

// void dfs(ll cur,ll par)
// {
//     vis[cur]=1;siz[cur]=1;
//     for(auto x:adj[cur])
//     {
//         if(vis[x]!=1)
//         {
//             dep[x]=dep[cur]+1;
//             dfs(x,cur);
//             siz[cur]+=siz[x];
//         }    
//     }
// }

// bool myfunc1(const pair<int,int> &a, const pair<int,int> &b) { return ;}

void solve()
{
    int h1,s1,h2,s2;cin>>h1>>s1>>h2>>s2;
    int x1=h2/s1,m1=h2%s1;
    int x2=h1/s2,m2=h1%s2;
    int fg=0;
    while(h1>0 && h2>0)
    {
        if(fg==0)
            h2-=s1;
        else
            h1-=s2;
        fg=abs(fg-1);
    }
    if(h1<=0)
        no;
    else
        yes;

}

signed main()
{
    senor_SR;
    
    // ll t;cin>>t;while(t--)
        solve();
 
    return 0;
}

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

using namespace std;
#define N 500
#define C 150
#define CHANGE_RATE 0.5

int main()
{
    int d = 0;
    int c[26];
    int s[365][26];
    int t_c[C][365];
    int last[26] = {0};
    int score_c[C] = {0};
    int score = 0;
    int max_c = 0;

    cin >> d;

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

    for(int i = 0; i < d; i++)
    {
        for(int j = 0; j < 26; j++)
        {
            cin >> s[i][j];
        }
    }

    for(int i = 0; i < C; i++)
    {
        for(int j = 0; j < 365; j++)
        {
            t_c[i][j] = rand() % 26;
        }
    }

    for(int n = 0; n < N; n++)
    {
        score = 0;
        max_c = 0;
        for(int ca = 0; ca < C; ca++)
        {
            score_c[ca] = 0;
            for(int i = 0; i < 26; i++)
                last[i] = 0;

            for(int i = 0; i < d; i++)
            {
                for(int j = 0; j < 26; j++)
                {
                    if(t_c[ca][i] == j)
                    {
                        last[j] = 0;
                        score_c[ca] += s[i][j];
                    }
                    else
                    {
                        last[j]++;
                        score_c[ca] -= c[j] * last[j];
                    }
                }
            }
        }

        for(int ca = 0; ca < C; ca++)
        {
            if(score < score_c[ca])
            {
                score = score_c[ca];
                max_c = ca;
            }
        }
        //cout << score << endl;

        for(int ca = 0; ca < C; ca++)
        {
            if(ca == max_c) continue;
            for(int i = 0; i < d; i++)
            {
                if((rand() / (double)RAND_MAX) < CHANGE_RATE)
                {
                    t_c[ca][i] = rand() % 26;
                }
                else
                {
                    t_c[ca][i] = t_c[max_c][i];
                }
            }
        }
    }

    for(int i = 0; i < d; i++)
    {
        cout << ((t_c[max_c][i] % 26) + 1) << endl;
    }

    return 0;
}

Measured memory_bytes: 3888
#include <bits/stdc++.h>
using namespace std;
int main(){
    string A, B, C;
    cin >> A >> B >> C;
    if (A.at(A.size() - 1) == B.at(0) && B.at(B.size() - 1) == C.at(0)) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)j;i <= (int)k;i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
const int maxn=(int)1e6+5;
multimap<string,int> mp;
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int q;cin>>q;while(q--){
        int op;cin>>op;
        if(op==3){
            string l,r;
            cin>>l>>r;
            auto ed=mp.upper_bound(r);
            for(auto it=mp.lower_bound(l);it!=ed;it++){
                cout<<it->first<<' '<<it->second<<endl;
            }
        }else{
            string s;cin>>s;
            if(op==0){
                int x;cin>>x;
                mp.insert(make_pair(s,x));
                
            }
            if(op==1){
                auto ed=mp.upper_bound(s);
                for(auto it=mp.lower_bound(s);it!=ed;it++){
                    cout<<it->second<<endl;
                }
            }
            if(op==2)mp.erase(s);
        }
        
    }
}
/* 
- insert(keykey, xx): Insert an element formed by a pair of keykey and xx to MM.
- get(keykey): Print the value with the specified keykey. Print 0 if there is no such element.
- delete(keykey): Delete the element with the specified keykey.
- dump(LL, RR): Print all elements formed by a pair of the key and the value such that the key is greater than or equal to LL and less than or equal to RR in lexicographic order..
10
0 blue 6
0 red 1
0 blue 4
0 white 5
1 red
1 blue
2 red
1 black
1 red
3 w z
 */



Measured memory_bytes: 24864
#pragma region RegionDefs
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define reps(i,j,n) for(int i=(j),i##_len=(n);i<i##_len;++i)
#define repr(i,n) for(int i=(n);i>=0;--i)
#define all(x) begin(x),end(x)
using namespace std;
const int INF = 1e9;
template<class T=int> using P  = pair<T, T>;
template<class T=int> using V  = vector<T>;
template<class T=int> using PQ = priority_queue<T>;
template<class T=int> using PQG = priority_queue<T, V<T>, greater<T>>;
typedef long long ll;
const ll MOD = 1000000007LL;
void in() {}
template<class Head, class... Tail>
void in(Head&& head, Tail&&... tail)
{
    cin >> head;
    in(move(tail)...);
}
#define IN(...) ll __VA_ARGS__; in(__VA_ARGS__)
//時間が厳しいとき使う
#define INI(...) int __VA_ARGS__; in(__VA_ARGS__)
#define INS(T, ...) T __VA_ARGS__; in(__VA_ARGS__)
#define VIN(T, v, n) V<T> v(n); for(auto& _elem:v)cin>>_elem
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 y0 y__0
#define y1 y__1
#define j0 j__0
#define j1 j__1
#define YN(e) cout << ((e) ? "YES" : "NO") << endl
#define yn(e) cout << ((e) ? "Yes" : "No") << endl
#pragma endregion RegionDefs

void solve()
{
    IN(h, w);
    if (h == 1 || w == 1)
    {
        cout << 1 << endl;
        return;
    }
    cout << (h * w + 1) / 2 << endl;
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(numeric_limits<double>::max_digits10);

    solve();

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
using namespace std;

int main()
{
    int n,k,i;
    string s;
    cin >> n >> s >> k;
    char temp = s.at(k-1);
    for(i = 0;i < n;++i){
        if(s.at(i) != temp){
            s.at(i) = '*';
        }
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  string s;
  cin >>s;
  ll k;
  cin >>k;
  ll ss=s.size();
  vector <string> p;
  for(ll i=0;i<ss;i++){
    for(ll j=1;j<=k;j++){
      string l=s.substr(i,j);
      p.push_back(l);
    }
  }
  sort(p.begin(),p.end());
  p.erase(unique(p.begin(),p.end()),p.end());
  cout <<p[k-1]<<endl;
}


Measured memory_bytes: 1660
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
#include <chrono>
#include<unordered_map>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(u) (u).begin(),(u).end()

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

typedef pair<int, int> PII;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

int main()
{
	LL N, A, B;
	scanf("%lld%lld%lld", &N, &A, &B);
	if ((B - A) & 1)
	{
		LL v1 = A + (B - A - 1) / 2;
		LL v2 = N - B + 1 + (N - (A + N - B + 1)) / 2;

		printf("%lld\n", min(v1, v2));
	}
	else
		printf("%lld\n", (B - A) / 2);

	return 0;
}

// FOR GNU C++ use the following pattern:
// Uncomment the code below and change your main into main2
// It does not build in MS C++
// But it does increase the stack size from 256 MB on CF and uses GNU C++

//#include <Processthreadsapi.h>
//#include <iostream>
//#include <Synchapi.h>
//#include <windows.h>
//#include <process.h>
//
//DWORD WINAPI MyThreadFunction(LPVOID lpParam) {
//    main2(nullptr);
//    return 0;
//}
//int main() {
//    auto h = CreateThread(nullptr, 1024 << 20, MyThreadFunction, nullptr, STACK_SIZE_PARAM_IS_A_RESERVATION, nullptr);
//    WaitForSingleObject(h, INFINITE);
//}

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

long long dp[101][8];
long long coef[17];

bool rad[7];

int dfs(int i, int w) {
  if (w <= 0) {
    return 1;
  }
  if (w == i){
    return 1;   
  }
  else {
    if (i == 0) {
      int sum;
      rad[i] = false;
      sum = dfs(i + 1, w);
      rad[i] = true;
      sum += dfs(i + 1, w);
      return sum;
    }
    else {
      int sum = 0;
      if (rad[i - 1]){
        rad[i] = false;
        sum = dfs(i + 1, w);
      }
      else {
        rad[i] = false;
        sum = dfs(i + 1, w);
        rad[i] = true;
        sum += dfs(i + 1, w);
      }
      return sum;
    }
  }
}

void co(int w) {
  for (int i  = 0; i < 2 * w - 1; i++) {
    if (i % 2 == 0) {
      int above = (w - 2) - (i / 2);
      int below = (i / 2) - 1;
      coef[i] = dfs(0, above) * dfs(0, below); 
    }
    else {
      int above = (w - 3) - (i / 2);
      int below = (i / 2) - 1;
      coef[i] = dfs(0, above) * dfs(0, below);
    }
  }
}

int main(void) {
  int h, w, k;
  cin >> h >> w >> k;

  if (w == 1) {
    cout << 1 << endl;
    return 0;
  }

  co(w);

  // for(int i = 0; i < 2 * w - 1; i++)
  // {
  //   cout << coef[i] << endl;
  // }
  // cout << endl;

  // return 0;

  dp[0][0] = 1;
  for(int i = 1; i < w; i++)
  {
    dp[0][i] = 0;
  }
  
  for(int i = 0; i < h + 1; i++)
  {
    for(int j = 0; j < w; j++)
    {
      if (j == w - 1) 
        dp[i + 1][j] = (coef[2 * j] * dp[i][j] + coef[2 * j - 1] * dp[i][j - 1]) % 1000000007;
      else if (j == 0) 
        dp[i + 1][j] = (coef[0] * dp[i][j] + coef[1] * dp[i][j + 1]) % 1000000007;
      else 
        dp[i + 1][j] = (coef[2 * j - 1] * dp[i][j - 1] + 
                       coef[2 * j] * dp[i][j] +
                       coef[2 * j + 1] * dp[i][j + 1]) % 1000000007;
    }
  }

  // for(int i = 0; i < h + 1; i++)
  // {
  //   for(int j = 0; j < w; j++)
  //   {
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << endl;
  // }
    

  cout << dp[h][k - 1] << endl;

  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main 
{
	static List<Integer> prime = new ArrayList<Integer>();
	static boolean[] isPrime = new boolean[300000];
	static void primeCalc()
	{
		for(int i = 0; i < isPrime.length; ++i)
		{
			isPrime[i] = true;
		}
		isPrime[0] = isPrime[1] = false;
		for(int i = 2; i < isPrime.length; ++i)
		{
			if(isPrime[i])
			{
				prime.add(i);
				for(int j = 2 * i; j < isPrime.length; j += i)
				{
					isPrime[j] = false;
				}
			}
		}
	}
	public static void main(String[] args) 
	{
		primeCalc();
		Scanner stdIn = new Scanner(System.in);
		while(stdIn.hasNext())
		{
			int n = stdIn.nextInt();
			if(n == 0)
			{
				break;
			}
			int sum = 0;
			for(int i = 0; i < n; ++i)
			{
				sum += prime.get(i);
			}
			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 13000
#include<bits/stdc++.h>
using namespace std;
int n,a,b,c,i,j,d;
string s;
char x[5];
int main()
{
  for(cin>>a>>b,i=a;i<=b;i++){
    c=i/10000;d=i%10;
    if(c!=d)continue;
    c=(i%10000)/1000;d=(i%100)/10;
    if(c!=d)continue;
    j++;
  }
  cout<<j;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    int[] x = new int[N];
    for (int i = 0; i < N; i++) {
      x[i] = sc.nextInt();
      if (isMultiples(2, x[i])) {
        if (isMultiples(3, x[i]) || isMultiples(5, x[i])) {
          continue;
        }
	    System.out.println("DENIED");
        return;
      }
    }
    
    System.out.println("APPROVED");
  }
  public static boolean isMultiples(int multiples, int n) {
    return ((n % multiples) == 0);
  }
}

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

using namespace std;

typedef long long ll;

#ifdef RED
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = (int)1e6 + 5;
const ll inf = (ll)1e18 + 7;

int n, W;
ll dp[105][N];
ll w[N], v[N];

ll mnw(int i, int sum_v) {
  if (i == 0) {
    if (sum_v == 0)
      return 0;
    return inf;
  }
  if (dp[i][sum_v] != -1) {
    return dp[i][sum_v];
  }
  ll ans = mnw(i - 1, sum_v);
  if (v[i] <= sum_v)
    ans = min(ans, mnw(i - 1, sum_v - v[i]) + w[i]);
  return dp[i][sum_v] = ans;
}

int main() {
#ifdef RED
  freopen("a.in", "r", stdin);
#endif
  ios_base :: sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> W;
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> w[i] >> v[i];
    sum += v[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= sum; ++j) {
      dp[i][j] = -1;
    }
  }
  for (int i = sum; i >= 0; i--) {
    if (mnw(n, i) <= W) {
      cout << i;
      return 0;
    }
  }
  return 0;
}


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

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

  int less_than_1000 = n % 1000;
  int ans;
  if (less_than_1000 == 0) {
    ans = 0;
  } else {
    ans = 1000 - less_than_1000;
  }

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

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

#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple

using namespace std;

const int N = 1e5;

struct struk
{
    ll x, y;
};

vector<struk> polje;
ll sol[3010];
ll MOD = 1e9 + 7;
ll fakt[2*N + 10];
ll inv[2*N + 10];
ll n, m, t;

ll mul(ll a, ll b)
{
    return (a*b)%MOD;
}

ll inverz(ll a, ll k)
{
    if(k == 0) return 1;
    ll a2 = inverz(a, k/2);
    a2 = mul(a2, a2);
    if(k % 2 == 1) a2 = mul(a2, a);
    return a2;
}

ll binomniKoef(ll n, ll k)
{
    ll res = mul(fakt[n], inv[k]);
    res = mul(res, inv[n-k]);
    return res;
}

ll sub(ll a, ll b)
{
    a -= b;
    if(a < 0) a += MOD;
    return a;
}

bool sortiraj(struk a, struk b)
{
    if(a.y < b.y) return true;
    if(a.y > b.y) return false;
    return a.x < b.x;
}


void pred()
{
    fakt[0] = 1;
    for(ll i = 1; i <= 2*N; i++) fakt[i] = mul(fakt[i-1], i);

    for(ll i = 0; i <= 2*N; i++) inv[i] = inverz(fakt[i], MOD-2);

}

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

    pred();

    cin >> n >> m >> t;
    for(int i = 0; i < t; i++)
    {
        struk p;
        cin >> p.y >> p.x;
        polje.pb(p);
    }
    sort(polje.begin(), polje.end(), sortiraj);

    for(int i = 0; i < t; i++)
    {
        ll xkoor = polje[i].x;
        ll ykoor = polje[i].y;
        ll res = binomniKoef(xkoor + ykoor - 2, xkoor - 1);
        for(int j = 0; j < i; j++)
        {
            if(polje[i].x >= polje[j].x && polje[i].y >= polje[j].y)
            {
                ll xkoor2 = xkoor - polje[j].x + 1;
                ll ykoor2 = ykoor - polje[j].y + 1;
                ll tr = mul(sol[j], binomniKoef(xkoor2 + ykoor2 - 2, xkoor2 - 1));
                res = sub(res, tr);
            }
        }
        sol[i] = res;
    }
    ll resenje = binomniKoef(n + m - 2, n - 1);
    for(int i = 0; i < t; i++)
    {
        ll xkoor = m - polje[i].x + 1;
        ll ykoor = n - polje[i].y + 1;
        ll tr = mul(sol[i], binomniKoef(xkoor + ykoor - 2, xkoor - 1));
        resenje = sub(resenje, tr);
    }
    cout << resenje;

    return 0;
}


Measured memory_bytes: 3584
a, b = gets.split.map(&:to_i)
if a * b <= 0
    puts 'Zero' 
else
    if a > 0
        puts 'Positive'
    else
        if (b - a + 1) % 2 == 0
            puts 'Positive'
        else
            puts 'Negative' 
        end
    end
end

Measured memory_bytes: 1788
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define ll long long
using namespace std;



int main()
{
	int n;
	cin >> n;
	bool flag = false;

	for (int i = 1; i < 10; i++) {
		for (int j = i; j < 10; j++) {
			if (i * j == n) {
				flag = true;
				break;
			}
		}
		if (flag)break;
	}

	printf("%s", flag ? "Yes" : "No");

	return 0;
}



Measured memory_bytes: 384
import math
a,b,c=map(int,input().split())
C=(c/180)*math.pi
S=(a*b*math.sin(C))/2
L=a+b+(a**2+b**2-2*a*b*math.cos(C))**0.5
h=b*math.sin(C)
print("%.5f\n%.5f\n%.5f\n"%(S,L,h))

Measured memory_bytes: 7848
L,R = map(int,input().split())
if (R-L > 2019) : print(0)
else:
    m = 2019*2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            s = (i*j)%2019
            if (m > s):
                m = s
            if (m == 0):
                break

    print(m)

Measured memory_bytes: 3060
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    S = input().rstrip()
    K = int(input())

    ans = ""
    T = S[K - 1]
    for s in S:
        if s == T:
            ans = ans + T
        else:
            ans = ans + "*"

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9084