akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int main(){
	long long N;
	long long *a_height;
	long long *takasa;
	long long cur_max, sum=0;

	cin >> N;

	a_height = new long long[N];
	takasa = new long long[N];

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

	takasa[0] = 0;
	cur_max = a_height[0];

	for(int i=1;i<N;i++){
		if(cur_max > a_height[i]){
			takasa[i] = cur_max-a_height[i];
		}
		else{
			takasa[i]=0;
			cur_max = a_height[i];
		}
		sum += takasa[i]; 
	}

	cout << sum << endl;

	delete[] a_height;
	delete[] takasa;
}

Measured memory_bytes: 6372
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod =1e+9+7;

int main(){
    ll l,r,d; cin>>l>>r>>d;
    ll ans=0;
    for(int i=1;i<=r;i++){
        if(i>=l&&i%d==0){
            ans++;
        }
    }
    cout<<ans<<endl;
}





























































































Measured memory_bytes: 3620
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <map>
#define MAXN ()
#define INF (0x7fffffff)
#define LL long long
#define pii pair<int, in>
using namespace std;

int main()
{
	int a, b, ans = 0;
	scanf("%d%d", &a, &b);
	for (int i = 1; i <= a; i++)
	{
		if (a <= b || i < a)
			++ans;
	}
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define rep(i, n) for (int i=0; i < n; i++)
#define repd(i, n) for (int i = n-1; i > -1; i--)
#define repran(i, a,b) for (int i = a; i<b;i++)
#define all(x) (x).begin(), (x).end()
#define v(T) vector<T>
#define vv(T) vector<v(T)>
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
template<class T>bool chmax(T &a, const T &b){
    if (a < b) {a = b; return true;}
    return false;
}
template<class T>bool chmin(T &a, const T &b){
    if (a > b) {a = b; return true;}
    return false;
}
const int inf = 10000;
int dp[10050];
int main()
{
    int h, n;
    cin >> h >> n;
    memset(dp, inf, sizeof(dp));
    dp[0] = 0;
    vi a(n), b(n);
    rep(i, n) cin >> a[i] >> b[i];
    rep(i, n){
        for(int j = 0; j<=h;j++){
            int nj = min(j+a[i], h);
            dp[nj] = min(dp[nj], dp[j]+b[i]);
        }
    }
    cout << dp[h] << endl;
}



Measured memory_bytes: 3632
start = Time.now
D = gets.to_i
@c = gets.split.map(&:to_i)
@s = Array.new D
D.times do |i|
  @s[i] = gets.split.map(&:to_i)
end

t = Array.new D
score = 0
last = Array.new 26, 0
D.times do |i|
  best = -99999999999
  res = nil
  base_c = 0
  26.times do |t|
    base_c += (i - last[t] + 1) * @c[t]
  end
  
  26.times do |t|
    diff = @s[i][t]
    diff -= base_c
    diff += @c[t] * (i - last[t] + 1)

    if diff > best
      best = diff
      res = t
    end
  end
  score +=  best
  last[res] = i + 1
  t[i] = res
end

@q = Array.new
def calc_pena t
  kei = Array.new(26, (1+D)*D/2)
  last = Array.new(26, 0)
  t.each_with_index do |_t, i|
    kei[_t] -= (i+1 - last[_t]) * (D - i)
    last[_t] = i + 1
  end
  res = 0
  26.times do |i|
    res += kei[i] * @c[i]
  end
  res
end
pena = calc_pena(t)
base_score = score + pena

while(Time.now - start < 1.9) do
  100.times do
    d = rand(D)
    old = t[d]
    rep = rand(26)
    new_t = t.dup
    new_t[d] = rep
    new_base_score = base_score - @s[d][old] + @s[d][rep]
    new_pena = calc_pena(new_t)
    if new_base_score - new_pena > base_score - pena
      t = new_t
      base_score = new_base_score
      pena = new_pena
    end
  end
end
t.each do |_t|
  puts _t + 1
end

Measured memory_bytes: 18020
#pragma GCC optimize(2)
#include <iostream>
using namespace std;
int main()
{
	int x,a,b;
	cin>>x>>a>>b;
	if(x>a)
	{
		x-=a;
		while(x-b>=0)
		{
			x-=b;
		}
		while(x-a>=0)
		{
			x-=a;
		}	
	}
	cout<<x;
}


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

ll N, W;

struct item
{
	ll v;
	ll w;
};
vector<item> Is(201);

int main(void)
{
	cin >> N >> W;
	for (int n = 0; n < N; n++)
	{
		cin >> Is[n].w >> Is[n].v;
	
	}

	vector<ll> defV(W + 1, 0);
	vector<vector<ll>> dp(N + 1, defV);

	for (ll n = 0; n < N; n++)
	{
		for (ll w = 0; w <= W; w++)
		{
			if (w >= Is[n].w)
			{
				dp[n + 1][w] = max(dp[n + 1][w], dp[n][w - Is[n].w] + Is[n].v);
			}
			dp[n + 1][w] = max(dp[n + 1][w], dp[n][w]);
		}
	}

	cout << dp[N][W] << endl;
}

Measured memory_bytes: 80256
n,m,q = map(int,input().split())
sum_=0

import itertools
 
A_kouho = []
for i in itertools.combinations_with_replacement(range(1, m+1), n):
    i = (1,) + i + (m,)
    A_kouho.append(i)
#print(A_kouho)

four_r = []
for j in range(q):
  Q = list(map(int, input().split()))
  four_r.append(Q)
#print(four_r)

max_ = 0
for A in A_kouho:
  sum_ = 0
  for j in four_r:
    #print('%d %d'%(A[j[1]]-A[j[0]],j[2]))
    if A[j[1]]-A[j[0]]==j[2]:
      sum_+=j[3]
    if sum_>max_: max_=sum_
print(max_)
    

Measured memory_bytes: 22964
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

vvll to;
ll ansd = -1, ansdidx = -1;
void dfs(ll u, ll p, ll d){
  if(to[u].size() == 1 && to[u][0] == p){
    if(ansd < d){
      ansd = d;
      ansdidx = u;
    }
    return;
  }

  for(ll v : to[u]){
    if(v != p){
      dfs(v, u, d + 1);
    }
  }
}

ll anse = -1, anseidx = -1;
void efs(ll u, ll p, ll d){
  if(to[u].size() == 1 && to[u][0] == p){
    if(anse < d){
      anse = d;
      anseidx = u;
    }
    return;
  }

  for(ll v : to[u]){
    if(v != p){
      efs(v, u, d + 1);
    }
  }
}

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n;
  cin >> n;

  to.resize(n);
  rep(i, n-1) {
    ll a, b;
    cin >> a >> b;
    a--, b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  dfs(0, 0, 0);
  efs(ansdidx, 0, 0);

  //cout << anse << endl;
  string ans = (anse % 3 == 1) ? "Second" : "First";

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 23508
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.ascii;
import std.concurrency;
void times(alias fun)(int n) {
    foreach(i; 0..n) fun();
}
auto rep(alias fun, T = typeof(fun()))(int n) {
    T[] res = new T[n];
    foreach(ref e; res) e = fun();
    return res;
}
// fold was added in D 2.071.0.
template fold(fun...) if (fun.length >= 1) {
    auto fold(R, S...)(R r, S seed) {
        static if (S.length < 2) {
            return reduce!fun(seed, r);
        } else {
            return reduce!fun(tuple(seed), r);
        }
    }
}

void main() {
    readln.chomp.to!long.pipe!"(a-1)/11*2+((a+10)%11<6?1:2)".writeln;
}


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

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  bool ok = true;
  int n;
  cin >> n;
  map<int, bool> mp;
  for(int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    if(mp[x]) ok = false;
    mp[x] = true;
  }
  cout << (ok ? "YES" : "NO") << '\n';
}

Measured memory_bytes: 9600
#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        bool prime[1000000] = {false};
        // falseで初期化
        prime[1] = true;
        prime[2] = false;
        int count = 0;
        
        // エラトステネスのふるい
        for(int j = 2; j * j <= n ; j++){
            if(!prime[j]){
                for (int k = 2; k*j <= n;k++){
                   prime[j*k] = true;
                }
            }
        }
        // falseだと素数
        for(int i = 1;i<=n;i++){
            if(!prime[i]) count = count +1;
        }
        cout << count << endl;
    }
    return 0;
}

Measured memory_bytes: 2144
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

class Main implements Runnable {
	public static void main(String[] args) {
		long t = System.currentTimeMillis();
		new Main().run();
		// new Thread(null, new Main(), "",
		// Runtime.getRuntime().maxMemory()).start();
		System.err.println(System.currentTimeMillis() - t);
	}

	@SuppressWarnings("unchecked")
	public void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int c = 0;
		String ans = "";
		for (int i = 0; i < n; ++i) {
			if (s.charAt(i) == '(') {
				++c;
			} else {
				--c;
			}
			if (c == -1) {
				ans = '(' + ans;
				c = 0;
			}
			ans=ans+s.charAt(i);
		}
		while (c > 0) {
			ans = ans + ')';
			--c;
		}
		System.out.println(ans);
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

Measured memory_bytes: 21844
A = int(input())
B = int(input())
C = int(input())
X = int(input())
count = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            price = 500*i + 100*j + 50*k
            if price == X:
                count += 1
print(count)

Measured memory_bytes: 3060
#include<cstdio>
#include<queue>
#include<utility>
#include<cstring>
#include<stack>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<map>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
bool cmp_P(const P &a,const P &b){
  return a.second < b.second;
}
int main()
{
  int tmp=0,dt,nt=0,dx,dy,nx=0,ny=0,f=1,N,x[100001],y[100001],t[100001];
  cin >> N;
  REP(i,N)
    cin >> t[i] >> x[i] >> y[i];
  REP(i,N){
    dx = abs(nx-x[i]);
    dy = abs(ny-y[i]);
    dt = abs(nt-t[i]);
    if(dx + dy > dt){
      f = 0;
      break;
    }else{
      tmp = dt-(dx+dy);
      if(tmp % 2){
        f = 0;
        break;
      }
    }
  }
  if(!f)
    cout << "No" << endl;
  else
    cout << "Yes" << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

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



Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl; 有効桁数指定
// *min_element(c + l, c + r) *max_element(c + l, c + r) 配列の中のmin-max
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// ~ は、-1の時だけfalse
// struct Edge {
//   int to, id;
//   Edge(int a, int b): to(a), id(b) {}
// };

int a[10][10];


int main(){

	int n,m;cin>>n>>m;

	rep(i,m) {
		int c,d;cin>>c>>d;c--;d--;
		a[c][d]=a[d][c]=1;
	}

    int array[n-1];

    rep(i,n-1) array[i]=i+1;

	ll ans =0;

    do{
    	bool ok = true;
    	if (!a[0][array[0]]) ok = false;
    	rep(i,n-2) {
    		if (!a[array[i]][array[i+1]]) {
				ok = false;
				break;
    		}
    	}
    	if (ok) ans++;
    }while(next_permutation(array,array+n-1));

	cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main (void){

	long N;
	long a[100000];
	long ans,i,j;
	
	ans = 0;
	scanf("%ld", &N);
	
	for(i=0;i<N;i++){;
		scanf("%ld", &a[i]);
	}
	
	for(i = 0; i<N; i++){
		if(a[i]-1>i){
			if(a[a[i]-1]-1==i){
				ans++;
			}
		}
	}
	
	printf("%ld\n", ans);

	return 0;
}

Measured memory_bytes: 896
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			long n = scanner.nextLong();
			String str = Long.toString(n);
			int result = 9 * (str.length() - 1);
			int val = Integer.valueOf(String.valueOf(str.charAt(0)));
			result += val;
			String subStr = str.substring(1);
			if (!subStr.matches("^9*$")) {
				result--;
			}
			System.out.println(result);
		}
	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(100005);
	rep(i, n) {
		int p;
		scanf("%d", &p);
		a[p]++, a[p + 1]++, a[p + 2]++;
	}
	int ans = 0;
	rep(i, 100005) ans = max(ans, a[i]);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 640
#include <cstdio>

typedef long long ll;

template<typename T> inline bool chkmax(T &x, T y){ x < y ? x = y, true : false; }

const int MAXN = 5e3 + 10, MAXM = 210;

int n, m;
ll a[MAXN], b[MAXN][MAXM], mat[MAXN][MAXN];
int L[MAXN][MAXM], R[MAXN][MAXM];

int s[MAXN], top = 0;

int main() {
    scanf("%d%d", &n, &m);
    a[0] = a[1] = 0;
    for (int i = 2; i <= n; ++i) {    
        ll x;
        scanf("%lld", &x);
        a[i] = a[i - 1] + x;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%lld", &b[i][j]);
    
    for (int j = 1; j <= m; ++j) {
        top = 0;
        for (int i = 1; i <= n; ++i) {
            while (top and b[s[top]][j] < b[i][j])
                --top;
            L[i][j] = top ? s[top] + 1 : 1;
            s[++top] = i;
        }
        top = 0;
        for (int i = n; i; --i) {
            while (top and b[s[top]][j] < b[i][j])
                --top;
            R[i][j] = top ? s[top] - 1 : n;
            s[++top] = i;
        }

        for (int i = 1; i <= n; ++i) {
            mat[L[i][j]][i] += b[i][j];
            mat[i + 1][R[i][j] + 1] += b[i][j];
            mat[i + 1][i] -= b[i][j];
            mat[L[i][j]][R[i][j] + 1] -= b[i][j];
        }
    }

    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
        for (int j = i; j <= n; ++j)
            chkmax(ans, mat[i][j] - a[j] + a[i]);
    }

    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 212864
#include <cmath>
#include <string.h>
#include <iostream>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <algorithm>

#define rep(i, n) for (int i = 0; i < n; i++)
#define rep_nested(i, s, n) for (int i = s; i <= n; i++)
#define ll long long
#define ull unsigned long long

const int N = 500;
const ll INF = 1000000007;

using namespace std;

template <class T>
T limit(T n, T k) {
	return (n > k) ? k : n;
}

int main() {
	int count = 0;
	string s;
	map<char, int> m;
	
	cin >> s;
	
	rep(i, (int)s.length()) {
		m[s[i]]++;
	}
	
	rep(i, (int)m.size()) {
		count++;
	}
	
	cout << ((count == 2) ? "Yes" : "No") << endl;
	
    return 0;
}

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

int main(){
	int a,b,c,k,sum=0;
	cin>>a>>b>>c>>k;
	
	if(a>=k){
		cout<<k<<endl;
		return 0;
	}
	
	sum+=a;
	k-=a;
	
	if(b>=k){
		cout<<sum<<endl;
		return 0;
	}
	
	k-=b;
	cout<<sum-min(k,c)<<endl;
	return 0;
}

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

int main(){
	string S,T;
	cin >> S >> T;
    int tlength = T.length();
    int slength = S.length();
    int i=0;
    string sub;
    int count = 0;
    vector<int> counts;
    while(slength >= tlength + i){
        count=0;
    	sub = S.substr(i, tlength);
        for(int j=0; j<tlength; j++){
          if(sub[j] != T[j]){
            count++;
          }
        }
      counts.push_back(count);
      i++;
    }
  cout << *min_element(counts.begin(), counts.end()) << endl;
}

Measured memory_bytes: 3640
sa=input()
sb=input()
sc=input()
k="a"
while True:
  if k=="a":
    if len(sa)==0:
      print("A")
      exit()
    else:
      k=sa[0]
      sa=sa[1:]
  if k=="b":
    if len(sb)==0:
      print("B")
      exit()
    else:
      k=sb[0]
      sb=sb[1:]
  if k=="c": 
    if len(sc)==0:
      print("C")
      exit()
    else:
      k=sc[0]
      sc=sc[1:]


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef long double ld;
const ll INF=(ll)1e18;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ll(1e18)
#define MOD 1000000007
#define print(a); for(auto x:a)cout<<x<<" "; cout<<"\n";
#define mset(a); memset(a,0,sizeof(a));

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    ll n;cin>>n;
    ll a=100.0;
    ll cnt=0;
    while(a<n){
        a=a*1.01;
        cnt++;
    }
    cout<<cnt<<"\n";
}



Measured memory_bytes: 3636
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()

int n, w, d;
Pi p[1010], q[1010], D[1010];

int get(int x,int y,int dir){
	// 3 0
	// 2 1
	if(dir == 0){
		if(w - x > d - y)return x + (d - y);
		else return w + d - (y + (w - x));
	}
	else if(dir == 1){
		if(w - x > y)return w + d + w - (x + y);
		else return w + d - (y - (w - x));
	}
	else if(dir == 2){
		if(x > y)return w + d + w - (x - y);
		else return w + d + w + (y - x);
	}
	else{
		if(x >= d - y)return x - (d - y);
		else return w + d + w + (x + y);
	}
	// [0, 2*(w+d)-1]
}

bool comp(const Pi &a, const Pi &b){
	return a.Se != b.Se ? a.Se < b.Se : a.Fi < b.Fi;
}

void solve(int tc){
	scanf("%d%d%d", &n, &w, &d);
	for(int i=0;i<n;i++){
		int x, y;
		char ch[2];
		scanf("%d%d%s", &x, &y, ch);
		if(ch[0] == 'E'){
			p[i].Fi = get(x, y, 0);
			p[i].Se = get(x, y, 1);
		}
		else if(ch[0] == 'S'){
			p[i].Fi = get(x, y, 1);
			p[i].Se = get(x, y, 2);
		}
		else if(ch[0] == 'W'){
			p[i].Fi = get(x, y, 2);
			p[i].Se = get(x, y, 3);
		}
		else{
			p[i].Fi = get(x, y, 3);
			p[i].Se = get(x, y, 0);
		}
	}
	
	sort(p, p+n, comp);
	//for(int i=0;i<n;i++)printf("%d %d\n", p[i].Fi, p[i].Se);puts("");puts("");
	
	
	int ans = ~0u>>1;
	int SZ = 2 * (d + w);
	for(int i=0;i<n;i++){
		//put at p[i].Se;
		int top = 0;
		for(int j=i+1;j<n;j++){
			if(p[j].Se != p[i].Se && p[j].Fi > p[i].Se && p[j].Fi < p[j].Se)q[top++] = Pi(p[j].Fi - p[i].Se, p[j].Se - p[i].Se);
		}
		for(int j=0;j<i;j++){
			if(p[j].Se != p[i].Se && (p[j].Fi > p[i].Se || p[j].Fi < p[j].Se))q[top++] = Pi((p[j].Fi - p[i].Se + SZ) % SZ, p[j].Se - p[i].Se + SZ);
		}
		
		
		//for(int i=0;i<top;i++)printf("%d %d\n", q[i].Fi, q[i].Se);puts("");
		
		int z = 0, mx = 0;
		D[z++] = Pi(0, 0);
		for(int j=0;j<top;j++){
			int v = (lower_bound(D, D+z, Pi(q[j].Fi-1, 100001)) - 1)->Se;
			D[z++] = Pi(q[j].Se, mx = max(mx, v + 1));
		}
		ans = min(ans, mx + 1);
	}
	printf("%d\n", ans);
}

int main(){
	int Tc = 1;// scanf("%d",&Tc);
	for(int i=1;i<=Tc;i++){
		solve(i);
	}
	return 0;
}

Measured memory_bytes: 3248
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <functional>
#include <set>
#include <map>
#include <deque>

using namespace std;

struct Process{char name[10]; int time;};

Process Stack[100000];
int p = 0;

void push(Process data){
    Stack[p] = data;

    ++p;
}

Process pop(){
    Process ret;
    ret = Stack[0];


    for (int i = 1; i < p; ++i) {
        Stack[i - 1] = Stack[i];
    }

    --p;

    return ret;
}

int main(){
    int time_sum=0;

    int n, q;

    cin >> n >> q;

    Process tmp;
    for (int i = 0; i < n; ++i) {
        cin >> tmp.name >> tmp.time;

        if (tmp.time > q){
            time_sum += q;
            tmp.time -= q;
            push(tmp);
        }else{
            time_sum += tmp.time;
            printf("%s %d\n", tmp.name, time_sum);
        }
    }

    while (p > 0){
        tmp = pop();

        if (tmp.time > q){
            time_sum += q;
            tmp.time -= q;
            push(tmp);
        }else{
            time_sum += tmp.time;
            printf("%s %d\n", tmp.name, time_sum);
        }
    }
}

Measured memory_bytes: 3368
'use strict';
const p = s => console.log(s);

function main(input) {
  let a,b,c,d;
  [a,b,c,d] = input[0].trim().split(" ").map(i => parseInt(i));

  while(1) {
    c -= b;
    a -= d;
    if(c <= 0) {
      p('Yes');
      break;
    }

    if(a <= 0) {
      p('No');
      break;
    }
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim().split("\n"));


Measured memory_bytes: 29628
package main

import (
	"fmt"
	"sort"
)

func main() {
	// Code for A - Candy Distribution Again
	var N, x int
	fmt.Scan(&N, &x)

	a := make([]int, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&a[i])
	}

	sort.Sort(sort.IntSlice(a))

	var ans int = 0
	for i := 0; i < N-1; i++ {
		if a[i] <= x {
			x -= a[i]
			ans++
		}
	}

	if x == a[N-1] {
		ans++
	}

	fmt.Println(ans)

}


Measured memory_bytes: 1844
#!/usr/bin/env python3
import sys
from itertools import chain
import numpy as np

# from itertools import combinations as comb
# form bisect import bisect_left, bisect_right, insort_left, insort_right
# from collections import Counter


def solve(N: int, A: "List[int]", B: "List[int]"):
    A = np.sort(A)
    B = np.sort(B)
    if N % 2 == 1:
        l = A[N // 2]
        r = B[N // 2]
        return r - l + 1
    else:
        l2 = A[N // 2 - 1] + A[N // 2]
        r2 = B[N // 2 - 1] + B[N // 2]
        return r2 - l2 + 1


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # N, A, B = map(int, line.split())
    N = int(next(tokens))  # type: int
    AB = np.array(list(map(int, tokens)), dtype=np.int32)
    A = AB[0::2]
    B = AB[1::2]
    answer = solve(N, A, B)
    print(answer)


if __name__ == "__main__":
    main()


Measured memory_bytes: 101432
N = int(input())
a = [0,0,0,1,1,1,2,3,4,6,9]
s = 0
for nums in a:
  s += nums
if N <= 10:
  print(a[N])
else:
  while len(a)<=N:
    a.append(1+s-a[-1]-a[-2])
    s += a[-1]
  p = 10**9+7
  print(a[-1]%p)
    

Measured memory_bytes: 9304
#8:47
MOD=10**9+7
INT_MAX=10**18+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
def power(a,x):
    res=1
    while(x>0):
        if x&1:
            res=(res*a)%MOD
        a=(a*a)%MOD
        x//=2
    return res%MOD
def NCR_MOD(n,r):
    num=1
    for i in range(n,n-r,-1):num=(num*i)%MOD
    for j in range(1,r+1):num=(num*power(j,MOD-2))%MOD
    return num
#################################################################################
s=input()
x=int(s[-1])
if x==2 or x==4 or x==5 or x==7 or x==9:
    print('hon')
elif x==3:
    print('bon')
else:
    print("pon")
    


Measured memory_bytes: 61896
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        Deque<Integer> deq = new ArrayDeque<Integer>();
        
        for (int i = 0; i < s.length; i++) {
            char ch = s[i].charAt(0);
            if (ch == '+' || ch == '-' || ch == '*') {
                int o2 = deq.pop();
                int o1 = deq.pop();
                
                deq.push((ch == '+') ? o1 + o2 : (ch == '-') ? o1 - o2 : o1 * o2);
                
            } else {
                deq.push(Integer.parseInt(s[i]));
            }
        }
        
        System.out.println(deq.pop());
    }
}


Measured memory_bytes: 26300
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    int h,w,n;
    cin>>h>>w>>n;
    int color[h][w];
    int a[n];
    rep(i,n)cin>>a[i];
    int x=0,y=0;
    rep(i,n){
        rep(j,a[i]){
            color[y][x]=i+1;
            if(y%2){
                if(x==0)y++;
                else x--;
            }else{
                if(x==w-1){
                    y++;
                }else x++;
            }
        }
    }
    rep(i,h){
        rep(j,w){
            cout << color[i][j];
            if(j!=w-1)cout << " ";
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
/*int abs(int a,int b){
  int c=max(a,b)-min(a,b);
  return c;
}*/
signed main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  double a,q=10000,w=0;
  double b[10000];
  double c=0;
  cin>>a;
  for(int i=0;i<a;i++){
    cin>>b[i];
    c+=b[i];
  }
  c/=a;
  for(int i=0;i<a;i++){
    //cout<<abs(b[i]-c)<<" "<<q<<"\n";
    if(abs(b[i]-c)<q) w=i,q=abs(b[i]-c);
  }
  cout<<w<<"\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 +10 ;
const int inf = 0x3f3f3f3f ;
struct st{int p,b,c;};
bool operator < (st a,st b){return a.c>b.c;}
inline int read(){
	char c;int f=1 ;
	while ((c=getchar())<'0' || c>'9') if (c=='-') f=-1 ;
	int res=c-'0' ;
	while ((c=getchar())>='0' && c<='9') res=res*10+c-'0' ;
	return res*f ; 
}
map<int ,vector<int> > E[N] ; 
map<int,int > d[N] ; 
vector <int> G[N];
priority_queue <st> q ;
int n,m;
int main(){
	n=read();m=read() ;
	for (int i=1;i<=m;i++){
		int a,b,c ;
		a=read();b=read();c=read();a--;b-- ;
		E[a][c].push_back(b) ;E[b][c].push_back(a) ;
		G[a].push_back(c) ;G[b].push_back(c) ; 
	}
	d[0][0]=0;q.push({0,0,0}) ;
	while(!q.empty()){ //一波Dijkstra 
		st p=q.top();q.pop() ;
		if (d[p.p][p.b]!=p.c){
			continue ;
		}
		if (d[p.p].find(0)==d[p.p].end() || d[p.p][0]>p.c){
			d[p.p][0]=p.c ;
			q.push({p.p,0,p.c}) ;
 		}
 		if (p.b==0){
 			for (int i=0;i<G[p.p].size();i++){
 				int v=G[p.p][i] ;
 				if (d[p.p].find(v)==d[p.p].end() || d[p.p][v]>p.c+1){
 					d[p.p][v]=p.c+1 ;
 					q.push({p.p,v,p.c+1}) ;
				 }
			 }
			continue ; 
		}
		for (int i=0;i<E[p.p][p.b].size();i++){
			int v=E[p.p][p.b][i] ;
			if (d[v].find(p.b)==d[v].end() || d[v][p.b]>p.c){
				d[v][p.b]=p.c ;
				q.push({v,p.b,p.c}) ;
			}
		}
	}
	int ans=inf ;
	for (map<int,int>::iterator p=d[n-1].begin();p!=d[n-1].end();p++) ans=min(ans,p->second) ;
	if (ans==inf) printf("-1\n") ;
	else printf("%d\n",ans) ;
}

Measured memory_bytes: 85552
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    int n,c=0,d,m; cin>>n;
    int arr[n],brr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    for(int i=0;i<n;i++)cin>>brr[i];
    for(int i=0;i<n;i++){
        int j=i,d=0,m=0;
        for(int k=0;k<=j;k++){
            d=d+arr[k];
        }
        for(int l=j;l<n;l++){
            m=m+brr[l];
        }
        d=d+m;
        c=max(c,d);
    } cout<<c;
}


Measured memory_bytes: 3572
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;
constexpr int MOD = 1e9 + 7;
using ll = long long;
template <typename T> T In() {
    T t;
    cin >> t;
    return t;
}
template <typename T> vector<vector<T>> Vec2(int i, int j, T ini = 0) {
    vector<vector<T>> vec(i, vector<T>(j, ini));
    return move(vec);
}
template <typename T> vector<vector<vector<T>>> Vec3(int i, int j, int k, T ini = 0) {
    vector<vector<vector<T>>> vec(i, vector<vector<T>>(j, vector<T>(k, ini)));
    return move(vec);
}


int main() {
    string S = In<string>();
    int N = S.length();
    auto dp = Vec2<ll>(N+1, 13, 0);
    dp[0][0] = 1;
    for(int n = 1; n <= N; n++) {
        auto fun = [&dp,n](int s) {
            for(int j = 0; j < 13; j++) {
                int m = (j * 10 + s) % 13;
                dp[n][m] = (dp[n][m] + dp[n - 1][j]) % MOD;
            }
        };
        char c = S[n - 1];
        if(c=='?'){
            for(int s = 0; s < 10; s++){
                fun(s);
            }
        }
        else{
            fun(c - '0');
        }
    }
    cout << dp[N][5] << endl;
}


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

int main(void) {
    int N;

    cin>>N;

    int count=0;
    int c[215];

    for(int i=0;i<=N;i++){
      c[i]=0;
    }

    int i=1;

    while(i<=N){
      for(int j=1;j<=N;j++){
        if((i%j)==0) c[i]++;
      }

      i += 2;
    //  cout<<i<<endl;
    }


    for(int i=0;i<=N;i++){
      if(c[i] == 8) count++;
      //  cout<<c[i]<<endl;
    }


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


Measured memory_bytes: 256
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [k, n] <- getIntList
    (a : as) <- getIntList
    let x = maximum $ zipWith (-) as (a : as)
    let y = k + a - (last as)
    print $ k - (max x y)

Measured memory_bytes: 19836
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
int n;
pair < pair < int , int > , int > t[1005];
bool cmp( pair < pair < int, int > , int > a , pair < pair < int , int > , int > b )
{
	return b.first.first+b.first.second>a.first.first+a.first.second;
}
ll dp[50005];
int main(){
	cin>>n;
	for(int i=0;n>i;i++)
	{
		cin>>t[i].first.first>>t[i].first.second>>t[i].second;
	}
	sort(t,t+n,cmp);
	fill(dp,dp+20003,-1e18);
	dp[0]=0;
	for(int i=0;n>i;i++)
	{
		int val=t[i].second;
		int waga=t[i].first.first;
		int wyt=t[i].first.second;
		for(int j=wyt;j>=0;j--)
			if(dp[j]>=0)
				dp[j+waga]=max(dp[j+waga],dp[j]+val);
	}
	ll out=0;
	for(int i=0;20005>=i;i++)
		out=max(out,dp[i]);
	cout<<out;
	return 0;
}


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

using namespace std;

int main() {
	int n,k;
	cin>>n>>k;
	int a[n];
	for(int i=0; i<n; i++) {
	    cin>>a[i];
	}
	sort(a,a+n);
	
	vector<int> dp(k+1, 0);
	for(int i=0; i<=k; i++) {
	    for(int j=0; j<n; j++) {
	        if(i==0) {
	            dp[i] = 2;
	        }
	        if(a[j]<=i) {
	           dp[i] = max(dp[i-a[j]],dp[i]);
	        } else break;
	    }
	    if(i!=0 && dp[i] == 2) {
	        dp[i] = 1;
	    } else dp[i] = 2;
	}
	
	/*for(int i=0; i<=k; i++) {
	        cout<<dp[i]<<" ";
	}*/
	//cout<<endl;
	cout<<(dp[k]==1?"First":"Second");
	
	return 0;
}

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

bool	CMPA(vector<int> a, vector<int> b) {
	return (a.at(1)<=b.at(1));
}

int	main() {
	int N;
	cin >>N;
	vector<vector<int>> a(N, vector<int> (2, 0));
	vector<vector<int>> c(N, vector<int> (2, 0));
	for (int i=0; i<N; i++) 
		cin >>a.at(i).at(0) >>a.at(i).at(1);
	for (int i=0; i<N; i++) 
		cin >>c.at(i).at(0) >>c.at(i).at(1);
	// Date input done
	sort(a.begin(), a.end(), CMPA);
	reverse(a.begin(), a.end());
	sort(c.begin(), c.end());
	int S=0;
	vector<bool> A(N, true);
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			if (!A.at(j))
				continue;
			if (a.at(j).at(1)>c.at(i).at(1))
				continue;
			if (a.at(j).at(0)>c.at(i).at(0))
				continue;
			S++;
			A.at(j)=false;
			break;
		}
	}
	cout <<S <<endl;
	return 0;
};


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int min(int& a, int& b){return a<b?a:b;}
void pre_calc(int&, int&, vector<int>&, vector<int>&);
int main(){
    int N, K;
    
    cin>>N>>K;
    vector<int> V(N, 0);
    vector<int> dp(N, INT32_MAX);

    for(int i=0;i<N;i++)cin>>V[i];
    pre_calc(N, K, V, dp);

    cout<<dp[N-1]<<endl;


    return 0;
}

void pre_calc(int& n, int& k, vector<int>& V, vector<int>& dp){ 
    dp[0]=0;
    for(int i=1;i<n;i++){
        for(int j=1;j<=k;j++){
            int pos = i-j;
            if(pos<0)break;
            dp[i]=min(dp[i], dp[pos]+abs(V[i]-V[pos]));
        }
    }
}

Measured memory_bytes: 1024
mod = 10 ** 9 + 7
N, K = map(int, input().split())
cnt = [0 for i in range(K+1)]
for i in range(K, 0, -1):
    tmp_sum = pow(K//i, N, mod)
    for j in range(2, 10**7+1):
        if i*j > K:
            break
        tmp_sum -= cnt[i*j]
    cnt[i] = tmp_sum
ans = sum(cnt[i]*i for i in range(1,K+1)) % mod
print(ans)

Measured memory_bytes: 11308
# coding: utf-8
# Here your code !
while True:
    a,b = map(int, input().split())
    
    if a == b == 0:
        break
    
    for i in range(a):
        for j in range(b):
            if (i + j) % 2 == 0:
                print("#",end="")
            else:
                print(".",end="")
        print()
        
    print()

Measured memory_bytes: 8948
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MAX = 1000;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L

int main() {
	int N, M; cin >> N >> M;
	int ans = 0;
	if (N > 1) {
		ans += N * (N-1) / 2;
	}
	if (M > 1) {
		ans += M * (M-1) / 2;
	}
	cout << ans << endl;
}

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

#include <vector>
#include <functional>

using namespace std;

template<typename T>
class SegmentTree
{
    int n;
    function<T(T,T)> op;
    vector<T> V;

    T q(int l, int r)
    {
        if (l >= r)
            return V[0];
        T a = q((l+1)/2, r/2);
        if (l%2 != 0)
            a = op(a, V[l]);
        if (r%2 != 0)
            a = op(a, V[r-1]);
        return a;
    }

public:
    SegmentTree(int n_, function<T(T,T)> op, T init):
        op(op)
    {
        n = 1;
        while (n < n_)
            n *= 2;
        V = vector<T>(2*n, init);
        for (int i=n-1; i>0; i--)
            V[i] = op(V[i*2], V[i*2+1]);
    }

    T get(int p) const
    {
        return V[p+n];
    }

    void set(int p, T v)
    {
        p += n;
        V[p] = v;
        for (p/=2; p>0; p/=2)
            V[p] = op(V[p*2], V[p*2+1]);
    }

    //  init OP v[l] OP v[l+1] OP ... OP v[r-1]
    T query(int l, int r)
    {
        if (r<=l)
            return -1;
        return q(l+n, r+n);
    }
};


int main()
{
    int N;
    cin>>N;
    vector<int> X(N), D(N);
    for (int i=0; i<N; i++)
        cin>>X[i]>>D[i];

    vector<pair<int,int>> XD(N);
    for (int i=0; i<N; i++)
        XD[i] = make_pair(X[i], D[i]);
    sort(XD.begin(), XD.end());
    for (int i=0; i<N; i++)
        X[i] = XD[i].first,
        D[i] = XD[i].second;

    vector<long long> T(N);
    SegmentTree<int> ST(N, [&](int x, int y){return max(x, y);}, -1);

    T[N-1] = 2;
    int N2 = 1;
    while (N2<N)
        N2 *= 2;

    for (int i=N-2; i>=0; i--)
    {
        int di = i;
        for (int b=N2; b>0; b/=2)
            if (di+b<N && X[di+b]<X[i]+D[i])
                di += b;

        int x = max(di, ST.query(i+1, di+1));
        ST.set(i, x);
        T[i] = (T[i+1] + (x+1<N ? T[x+1] : 1))%998244353;
    }

    //for (int t: T)
    //    cout<<" "<<t;
    //cout<<endl;

    cout<<T[0]<<endl;
}


Measured memory_bytes: 7040
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)

int main(){
  int M1, D1, M2, D2;
  cin >> M1 >> D1 >> M2 >> D2;
  if(M2 == M1+1){
    cout << 1 << endl;
  }
  else if(M1 == 12 && M2 == 1){
    cout << 1 << endl;
  }
  else{
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define mod 1000000007
#define calc(x) (1LL*((x&1)?0:pw[x>>1]))
#define add_edge(u,v) to[tot]=v;pre[tot]=lst[u];lst[u]=tot++
int lst[5005],to[10005],pre[10005],tot,sz[5005],dp_sz[5005],n;
long long dp[5005][5005][2],pw[5005]={1},tmp[5005][2],ans=0;
void init_dfs(int u,int fa)
{
	sz[u]=1;
	for (int i=lst[u];~i;i=pre[i])
	{
		if (to[i]==fa) continue;
		init_dfs(to[i],u);
		sz[u]+=sz[to[i]];
	}
}
void dfs(int u,int fa)
{
	dp[u][0][0]=1;
	for (int i=lst[u];~i;i=pre[i])
	{
		int v=to[i];
		if (v==fa) continue;
		dfs(v,u);
		memset(tmp,0,sizeof(tmp));
		for (int x=dp_sz[u];x>=0;x--)
		{
			for (int y=dp_sz[v];y>=0;y--)
			{
				tmp[x+y][0]=(tmp[x+y][0]+dp[u][x][0]*dp[v][y][0])%mod;
				tmp[x+y][0]=(tmp[x+y][0]+dp[u][x][1]*dp[v][y][1])%mod;
				tmp[x+y][1]=(tmp[x+y][1]+dp[u][x][0]*dp[v][y][1])%mod;
				tmp[x+y][1]=(tmp[x+y][1]+dp[u][x][1]*dp[v][y][0])%mod;
			}
		}
		memcpy(dp[u],tmp,sizeof(tmp));
		dp_sz[u]+=dp_sz[v];
	}
	if (u)
	{
		for (int x=dp_sz[u];x>=0;x--)
		{
			dp[u][sz[u]][0]=(dp[u][sz[u]][0]+dp[u][x][1]*calc(sz[u]-x))%mod;
			dp[u][sz[u]][1]=(dp[u][sz[u]][1]+dp[u][x][0]*calc(sz[u]-x))%mod;
		}
	}
	dp_sz[u]++;
}
int main()
{
	memset(lst,-1,sizeof(lst));
	scanf("%d",&n);
	for (int i=1;i<=n;i++) pw[i]=pw[i-1]*(i*2-1)%mod;
	for (int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		--u,--v;
		add_edge(u,v);
		add_edge(v,u);
	}
	init_dfs(0,-1);dfs(0,-1);
	for (int i=0;i<=n;i++)
	{
		ans=(ans+dp[0][i][0]*calc(n-i))%mod;
		ans=(ans-dp[0][i][1]*calc(n-i))%mod;
	}
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}

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

int main(){
	int w,h,n;
	scanf("%d %d %d",&w,&h,&n);
	int x[n],y[n],a[n];
	int i;
	
	int xmax = w, xmin = 0, ymax = h, ymin=0;

	for(i=0;i<n;i++){
		scanf("%d %d %d",&x[i],&y[i],&a[i]);
	}
	
	for(i=0;i<n;i++){
		if(a[i]==1){
//			xmin=max(xmin,x[i]);
			if(x[i]>xmin){
				xmin = x[i];
			}
		}else if(a[i]==2){
//			xmax=min(xmax,x[i]);
			if(x[i]<xmax){
				xmax=x[i];
			}
		}else if(a[i]==3){
//			ymin=max(ymin,y[i]);
			if(y[i]>ymin){
				ymin=y[i];
			}
		}else if(a[i]==4){
//			ymax=min(ymax,y[i]);
			if(y[i]<ymax){
				ymax=y[i];
			}
		}
		if((xmax-xmin)*(ymax-ymin)<=0){
			printf("0\n");
			return 0;
		}
	}
	printf("%d\n",(xmax-xmin)*(ymax-ymin));
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
void upt(map<int,int> &f,int j,int v){
	if(!f.count(j)) f[j]=v;
	else f[j]=min(f[j],v);
}
map<int,int> f[N];
// f_{i,j} 表示代价为 j 时,最小的状态 c_i 是多少. 
int n,a[N];
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	f[1][0]=a[1]; f[1][1]=0;
	for(int i=2;i<=n;++i){
		for(auto [v,j]:f[i-1]){
			if(f[i-1].begin()->first < v-2) break;
			if(j+min(a[i]-a[i-1],0)>0) upt(f[i],v+2,0);
			if(j+min(a[i]-a[i-1],0)<=a[i]) upt(f[i],v+1,max(0,j+min(a[i]-a[i-1],0)));
			if(j+max(a[i]-a[i-1],0)<=a[i]) upt(f[i],v,j+max(a[i]-a[i-1],0)); 
		}
	}
	int ans=1e9;
	for(auto [v,j]:f[n])
		ans=min(ans,v+(j!=0));
	cout<<ans;
	return 0; 
}

Measured memory_bytes: 51184
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main(void){
    int n=0,R[MAX],maxv,minv;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> R[i];
    }
    maxv = -1000000000;
    minv = R[0];
    for (int i = 1; i < n; i++){
       maxv = max(maxv, R[i] - minv);
       minv = min(minv, R[i]);
    }
    cout << maxv << endl;
    return 0;
}


Measured memory_bytes: 3876
s=str(input())
n=len(s)
l=[0]*(n+1)
c=0
for i in range(n):
    if s[i]=='<':
        c+=1
        l[i+1]=c
    else:
        c=0
d=0
for i in range(n-1,-1,-1):
    if s[i]=='>':
        d+=1
        l[i]=max(d,l[i])
    else:
        d=0
print(sum(l))

Measured memory_bytes: 46536
#include<bits/stdc++.h>
using namespace std;
#define ALL(A) A.begin(),A.end()
const long long mod=1000000007;
int main(){
    int n,a,b,c;
    cin>>n;
    while(1)
    {
        int m=n;
        c=m%10;m/=10;b=m%10;m/=10;a=m;
        if(a==b&&b==c)
        break;
        n++;
    }
    cout<<n<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
 
using namespace std;
const double eps=1e-8;
 
struct Point
{
	double x,y;
};
 
Point p[505];
 
double dist(Point A,Point B)
{
	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
 
/***返回三角形的外心 */
Point circumcenter(Point A,Point B,Point C)
{
	Point ret;
	double a1=B.x-A.x,b1=B.y-A.y,c1=(a1*a1+b1*b1)/2;
	double a2=C.x-A.x,b2=C.y-A.y,c2=(a2*a2+b2*b2)/2;
	double d=a1*b2-a2*b1;
	ret.x=A.x+(c1*b2-c2*b1)/d;
	ret.y=A.y+(a1*c2-a2*c1)/d;
	return ret;
}
 
/***c为圆心，r为半径 */
void min_cover_circle(Point *p,int n,Point &c,double &r)
{
	random_shuffle(p,p+n);
	c=p[0]; r=0;
	for(int i=1;i<n;i++)
	{
		if(dist(p[i],c)>r+eps)   //第一个点
		{
			c=p[i]; r=0;
			for(int j=0;j<i;j++)
				if(dist(p[j],c)>r+eps)  //第二个点
				{
					c.x=(p[i].x+p[j].x)/2;
					c.y=(p[i].y+p[j].y)/2;
					r=dist(p[j],c);
					for(int k=0;k<j;k++)
						if(dist(p[k],c)>r+eps)  //第三个点
						{   //求外接圆圆心，三点必不共线
							c=circumcenter(p[i],p[j],p[k]);
							r=dist(p[i],c);
						}
				}
		}
	}
}
 
int main()
{
	int n;
	Point c;
	double r;
	while(~scanf("%d",&n)&&n)
	{
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		min_cover_circle(p,n,c,r);
		printf("%.18lf",r);
	}
	return 0;
}

Measured memory_bytes: 256
#[macro_use]
mod input {

use std;
use std::io;

const SPLIT_DELIMITER: char = ' ';

#[macro_export]
#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

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

#[allow(dead_code)]
pub fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[allow(dead_code)]
pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
where
    T: std::str::FromStr,
{
    let mut v: Vec<Vec<T>> = Vec::new();

    for _ in 0..line {
        let vec_line = input_vector();
        v.push(vec_line);
    }
    v
}

#[allow(dead_code)]
pub fn input_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
{
    let mut v: Vec<T> = Vec::new();

    let s = input_line_str();
    let split_result = s.split(SPLIT_DELIMITER);
    for z in split_result {
        let buf = match z.parse() {
            Ok(r) => r,
            Err(_) => panic!("Parse Error"),
        };
        v.push(buf);
    }
    v
}

#[allow(dead_code)]
pub fn str2vec(s: &str) -> Vec<char> {
    let mut v: Vec<char> = Vec::new();
    for c in s.chars() {
        v.push(c);
    }
    v
}

}

#[allow(unused_imports)]
use input::*;

use std::collections::VecDeque;

const INF: usize = 999_999_999_999;

fn main() {
    let (n, m): (usize, usize);
    input!(n, m);

    let mut graph = vec![vec![Vec::new(); 3]; n];
    let mut dist = vec![vec![INF; 3]; n];
    let mut used = vec![vec![false; 3]; n];
    let mut queue = VecDeque::new();
    for _ in 0..m {
        let (u, v): (usize, usize);
        input!(u, v);
        graph[u - 1][0].push((v - 1, 1));
        graph[u - 1][1].push((v - 1, 2));
        graph[u - 1][2].push((v - 1, 0));
    }
    let (s, t): (usize, usize);
    input!(s, t);
    dist[s - 1][0] = 0;
    for edge in &graph[s - 1][0] {
        queue.push_front((1, edge.0, edge.1));
        used[edge.0][edge.1] = true;
    }
    while !queue.is_empty() {
        let state = queue.pop_back().unwrap();
        if dist[state.1][state.2] < state.0 {
            continue;
        }
        dist[state.1][state.2] = state.0;
        for edge in &graph[state.1][state.2] {
            if dist[edge.0][edge.1] > state.0 + 1 && !used[edge.0][edge.1] {
                used[edge.0][edge.1] = true;
                queue.push_front((state.0 + 1, edge.0, edge.1));
            }
        }
    }
    if dist[t - 1][0] == INF {
        println!("-1");
    } else {
        println!("{}", dist[t - 1][0] / 3);
    }
}

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

using namespace std;
 
typedef long long int ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector <string> vs;
typedef vector<vector<int>> vvi;
typedef pair<int,int> pi;

//#define int ll
#define forl(i,a,b) for (int i = a; i < b; i++)
#define rfor(i,b,a) for (int i = b; i >= a; i--)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define srt(x) sort(x.begin(), x.end())
#define sumup(x) accumulate(x.begin(), x.end(), 0)
#define PI 3.141592653589793238
#define MOD 1000000007
#define loop(n) for(int i = 0; i < n; i++)
#define rloop(n) for(int i = n-1; i >= 0; i--)

void io() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}

void solve() {
    ll x;
    cin>>x;
    for(int i=-200; i<=200; i++) {
        for(int j=-200; j<=200; j++) {
            ll a = pow(i,5) - pow(j,5);
            if(a==x) {
                cout<<i<<" "<<j;
                return;
            }
        }
    }
    return;
}
int32_t main() {
    io();
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3968
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

void OutputError(std::string s) {
  cerr << "\033[93m" << s << "\033[m" << endl;
  return;
}

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  char b;
  cin >> b;
  if (b == 'A') {
    cout << "T";
  } else if (b == 'C') {
    cout << "G";
  } else if (b == 'G') {
    cout << "C";
  } else {
    cout << "A";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
def resolve():
  a = list(map(int, input().split()))
  a.sort()
  ans = 0
  ans += a[2] - a[1]
  a[1] = a[2]
  a[0] += ans
  ans += (a[2] - a[0]) // 2
  a[0] += ((a[2] - a[0]) // 2) * 2
  if a[0] != a[2]:
    ans += 2
  print(ans)

  return

if __name__ == "__main__":
  resolve()


Measured memory_bytes: 3060