akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define MAX (100000)
#define pii pair<int, int>

/////////////////////////////////////////////////////////

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
ll mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  ll tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

ll comb(ll n, ll r){
	ll res = 1;
  rep(i, 0, r){
    res *= n - i;
    res /= i + 1;
  }
  return res;
}

/////////////////////////////////////////////////////////

void Main() {
  int x, y; cin >> x >> y;
  int res;
  if(x > y && y > 0) res = 1 + (x - y) + 1;
  else if(x > y && y == 0) res = 1 + (x - y);
  else if(y >= x && x >= 0) res = y - x;
  else if(x > 0 && 0 > y){
    if(x >= - y) res = 1 + (x + y);
    else res = (- x - y) + 1;
  }
  else if(y > 0 && 0 > x){
    if(y >= - x) res = 1 + (x + y);
    else res = (- x - y) + 1;
  }
  else if(0 == x && x > y) res = (x - y) + 1;
  else if(0 > x && x > y) res = 1 + (x - y) + 1;
  else if(0 >= y && y >= x) res = y - x;
  cout << res << endl;
}

/////////////////////////////////////////////////////////

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256
S = input()

d_set = set()
for s in S:
    d_set.add(s)

if ("N" in d_set and "S" not in d_set) or  ("S" in d_set and "N" not in d_set) or  ("E" in d_set and "W" not in d_set) or ("W" in d_set and "E" not in d_set):
    print("No")
else:
    print("Yes")

Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<n; i++)
#define REP(i,x,n) for (int i=x; i<n; i++)
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;

int main(){
   int w, h, x, y;
   cin >> w >> h >> x >> y;
   double ans = (double)w * h / 2;
   int num = (w == x * 2 && h == y * 2)? 1 : 0;
   printf("%.6f %d\n", ans, num);
   return 0;
}


Measured memory_bytes: 3744
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>

using namespace std;

void solve(){
    int a, b;
    char op;
    while(cin >> a >> op >> b){
        if(op == '+'){
            cout << a+b << endl;
        }else if(op == '*'){
            cout << a*b << endl;
        }else if(op == '-'){
            cout << a-b << endl;
        }else if(op == '/'){
            cout << a/b << endl;
        }else{
            return;
        }
    }
}

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

Measured memory_bytes: 3052
#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {
	int A, B, K;
	cin >> A >> B >> K;

	int la = A, ra = A + K - 1;
	int lb = B - K + 1, rb = B;

	if (ra > B) ra = B;
	if (ra >= lb) lb = ra + 1;

	for (int i = la; i <= ra; i++) cout << i << endl;
	for (int i = lb; i <= rb; i++) cout << i << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first  
#define S second
#define ll long long
#define pb push_back
#define pr pair<ll,ll>

const ll N=1e5+9,mod=1e9+7,inf=1e18;


int main(int argc, char const *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
   ll n,m;
   cin>>n>>m;
   for(int i=1;i<=max(n,m);i++)cout<<min(n,m);
   cout<<"\n";
   

	
	
	return 0;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    string S;
    cin >> S;
    string s = "No";
    if (S[0] == S[1] && S[0] == S[2] || S[1] == S[2] && S[1] == S[3])
        s = "Yes";
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cstdio>
#include<iostream>
using namespace std;
int main(void){
	int H,W,co=0;
	cin>>H>>W;
	char a[H][W+1]={0};
	int b[H][W+1]={0};
	for(int i=0;i<H;i++){
		for(int j=1;j<=W;j++){
			cin>>a[i][j];
			if(a[i][j-1]==0&&a[i][j]=='.'){
				b[i][j]=-1;
				a[i][j]=0;
			}
			else if(a[i][j]=='c'){
				b[i][j]=0;
				co=0;
			}
			else{
				co++;
				b[i][j]=co;
			}
		}
		co=0;
	}
	for(int i=0;i<H;i++){
		for(int j=1;j<=W;j++){
			if(j==W){cout<<b[i][j];}
			else{cout<<b[i][j]<<" ";}
			
		}
		cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 3120
using System;
using System.Linq;
using System.Collections.Generic;

class Program {
    static void Main() {
        string str;
        while((str = Console.ReadLine()) != "-") {
            int m = int.Parse(Console.ReadLine());
            for(int i = 0; i < m; i++) {
                int h = int.Parse(Console.ReadLine());
                str = str.Substring(h) + str.Substring(0, h);
            }
            Console.WriteLine(str);
        }
    }
}


Measured memory_bytes: 17964
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<string.h>
#include<math.h>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<assert.h>
using namespace std;
typedef long long ll;

const int max_n = 1e5 + 1;
const ll INF = 2*1e9;
 
int N, K;
ll h[max_n];
ll d[max_n];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		cin >> h[i];
	
	d[0] = 0;
	for (int i = 1; i < N; i++)
	{
		d[i] = INF;
		for (int j =max(0,i - K); j < i; j++) 
			d[i] = min(d[i], d[j] + abs(h[j] - h[i]));
	}
	cout << d[N - 1];
}

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

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

    vector<pair<long long, long long>> v(n);
    long long a, b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        v[i] = make_pair(a, b);
    }

    long long t = 0;
    long long r = 0;
    long long d;
    for (int i = n - 1; i >= 0; i--) {
        d = (t + v[i].first) % v[i].second;
        if (d != 0) {
            t += v[i].second - d;
        }
    }

    cout << t << endl;
}


Measured memory_bytes: 1792
N = gets.to_i
counts = Array.new(100000+1, 0)
sum = 0
A = gets.split.each do |i|
  i = i.to_i
  counts[i] += 1
  sum += i
end
Q = gets.to_i

1.upto(Q) do
  b, c = gets.split.map(&:to_i)
  num = counts[b]
  sum += (c - b) * num
  puts sum
  counts[b] = 0
  counts[c] += num
end


Measured memory_bytes: 23320
#include <cstdio>
#include <algorithm>

int main()
{
  int n, k;
  scanf("%d %d", &n, &k);
  int ans = 1;
  for (int i = 0; i < n; ++i)
  {
    ans = std::min(ans + k, ans * 2);
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    unsigned long long int a;
    long double b,prod;
    cin>>a>>b;
    prod=a*b;
    cout<<(unsigned long long int)prod;
    return 0;
}

Measured memory_bytes: 3748
// Dont hack this or I hack ur mama
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#define ll long long 
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define EPS (1e-9)
using namespace std;

////////////// END OF TEMPLATE
const int nmax = 100100;
ll fact[nmax];
const ll mod = 1000000007;
int N,M;
void pre()
{
	fact[0] = 1;
	fact[1] = 1;
	
	for(int i = 2;i<nmax-5;++i)
		fact[i] = fact[i-1] * i % mod;
}
void read()
{
	cin >> N >> M;
	if( N < M)
		swap(N,M);
	if( N - M > 1)
		cout << 0 << endl;
	else
	{
		pre();
		ll ans = fact[N] * fact[M] %mod;
		if(N == M)
			ans = ans * 2LL %mod;
		cout << ans << endl;
	}

}
void solve()
{

}
int main()
{
	std::ios::sync_with_stdio(false);
	read();
	solve();
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define f(i,j,k) for(int i=j;i<k;i++)
using namespace std;
int main(){
    long long a,b,ans=1;
    cin>>a>>b;
    a-=1;
    b-=1;
    if(b==0){
        cout<<0<<endl;
    }
    else{
        while(1){
            if(a*ans>=b){
                break;
            }
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
X,Y,A,B,C = map(int, raw_input().split())
P = map(int, raw_input().split())
Q = map(int, raw_input().split())
R = map(int, raw_input().split())
 
Ps = sorted(P, reverse=True)
Qs = sorted(Q, reverse=True)
Rs = sorted(R, reverse=True)

Z = sorted(Ps[:X] + Qs[:Y] + Rs ,reverse=True)
print sum(Z[:X+Y])

Measured memory_bytes: 71536
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    vector<ll> x(n);
    for (int i = 0; i < n; i++)
    {
        cin >> x[i];
    }
    ll ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        ans += min((x[i + 1] - x[i]) * a, b);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4012
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<string.h>
#include<sstream>
#include<math.h>
#include<cctype>
#include<stdlib.h>
#include <cstring>
#include<cstdlib>
#include<cstdio>
#include<functional>
using namespace std;
typedef long long LL;
int main()
{
	int n;
	while (cin >> n)
	{
		LL a = 0, b = 0;
		set<LL>s1,s2,s3;
		priority_queue <LL>pq1,pq2;
		while (n--)
		{
			int num;
			cin >> num;
			if (s1.count(num))
			{
				if (s2.count(num))
				{
					if (s3.count(num))
						pq1.push(num);
					else
						s3.insert(num);
				}
				else
				{
					s2.insert(num);
					pq2.push(num);
				}
			}
			else
				s1.insert(num);
		}
		if (!pq1.empty())
			a = b = pq1.top();
		if (pq2.size() > 1)
		{
			a = max(a, pq2.top());
			pq2.pop();
			b = max(b, pq2.top());
		}
		cout << a*b << endl;
	}
	return 0;
}

Measured memory_bytes: 5240
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
typedef long long ll;
const ll MOD=1000000007;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
long long combi(long long n, long long k) {
  if (n == k || k == 0)
    return 1;
  else {
    return combi(n - 1, k - 1) + combi(n - 1, k);
  }
}
int main(void){
    // Your code here!
    int n; cin >> n;
    vector<ll> a(n);
    vector<ll> ans(n,0);
    rep(i,n) cin >> a[i];
    map<ll,ll> mp;
    map<ll,ll> mp2;
    rep(i,n){
        mp[a[i]]++;
    }
    for ( auto x:mp){
        mp2[x.first] = x.second*(x.second-1)/2;
    }
    ll sum = 0;
    for (auto x:mp2){
        sum += x.second;
    }
    rep(i,n){
        if ( mp[a[i]] < 2) {
            cout << sum << endl;
            continue;
        }else if (mp[a[i]] == 2){
            cout << sum - 1 << endl;
        }else{
        ll res = sum - mp2[a[i]] + (mp[a[i]]-1)*(mp[a[i]]-2)/2;
        cout << res << endl;
        }
    }
}


Measured memory_bytes: 21760
#include<bits/stdc++.h>
 
#define INF 1000000007
#define LINF 1000000000000000007
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> P;


int a[4];

int main(){
	for(int i = 0; i < 4; i++){
		cin >> a[i];
	}
	
	if(abs(a[0]-a[2]) <= a[3] || abs(a[0]-a[1]) <= a[3] && abs(a[1]-a[2]) <= a[3]){
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
	
	return 0;
}

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

using namespace std;

template <long long Mod> struct ModInt { /* {{{ */
  long long v;
  constexpr ModInt(const long long x = 0) {
    v = x % Mod;
    if (v < 0) {
      v += Mod;
    }
  }
  constexpr ModInt operator+(const ModInt rhs) const {
    return ModInt(*this) += rhs;
  }
  constexpr ModInt operator-(const ModInt rhs) const {
    return ModInt(*this) -= rhs;
  }
  constexpr ModInt operator*(const ModInt rhs) const {
    return ModInt(*this) *= rhs;
  }
  constexpr ModInt operator/(const ModInt rhs) const {
    return ModInt(*this) /= rhs;
  }
  const ModInt &operator+=(const ModInt rhs) {
    v += rhs.v;
    if (v >= Mod) {
      v -= Mod;
    }
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt rhs) {
    if (v < rhs.v) {
      v += Mod;
    }
    v -= rhs.v;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt rhs) {
    v = v * rhs.v % Mod;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt rhs) {
    long long exp = Mod - 2;
    while (exp) {
      if (exp & 1) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp >>= 1;
    }
    return *this;
  }
  friend ostream &operator<<(ostream &s, ModInt<Mod> m) {
    s << m.v;
    return s;
  }
  friend istream &operator>>(istream &s, ModInt<Mod> m) {
    s >> m.v;
    return s;
  }
}; /* }}} */

const int mod = 1e9 + 7;
using modint = ModInt<mod>;

int main() {
  int r1, c1, r2, c2;
  cin >> r1 >> c1 >> r2 >> c2;
  modint fact[2000005];
  fact[0] = 1;
  for (int i = 1; i < 2000005; i++) {
    fact[i] = fact[i - 1] * i;
  }
  auto count = [&](int r, int c) -> modint {
    return fact[r + c] / fact[r] / fact[c];
  };
  modint ans = count(r2 + 1, c2 + 1) - count(r2 + 1, c1) - count(r1, c2 + 1) +
               count(r1, c1);
  cout << ans << endl;

  return 0;
}
/* vim:set fdm=marker: */


Measured memory_bytes: 15872
import std.algorithm, std.conv, std.range, std.stdio, std.string;

void readV(T...)(ref T t){auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(typeof(v));r.popFront;}}
void readA(T)(size_t n,ref T t){t=new T(n);auto r=readln.splitter;foreach(ref v;t){v=r.front.to!(ElementType!T);r.popFront;}}
void readM(T...)(size_t n,ref T t){foreach(ref v;t)v=new typeof(v)(n);foreach(i;0..n){auto r=readln.splitter;foreach(ref v;t){v[i]=r.front.to!(ElementType!(typeof(v)));r.popFront;}}}
void readS(T)(size_t n,ref T t){t=new T(n);foreach(ref v;t){auto r=readln.splitter;foreach(ref j;v.tupleof){j=r.front.to!(typeof(j));r.popFront;}}}

void main()
{
  int x; readV(x);
  int a; readV(a);
  int b; readV(b);
  writeln((x-a)%b);
}


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

int main() {
  int N, l ,r ,ans;
  ans = 0;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> l >> r;
    ans += r-l+1;
  }
  cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(a)      (a).begin(),(a).end()
#define debug_array(a,n) for (ll bccc=(0); bccc<(n); bccc++) cout<<a[bccc]<<" "
#define debug_vector(a) for(ll bccc=(0); bccc<(a.size());bccc++) cout<<a[bccc]<<" "
#define F           first
#define S           second
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
typedef long long ll;
using namespace __gnu_pbds;
typedef tree<pair<ll,ll>,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
/* ll t = 0;
ordered_multiset me;
...
me.insert({x, t++});
me.erase(me.lower_bound({x, 0}));
cout << me.order_of_key({x, 0}) << "\n";

///////////   t is insertion time
*/
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
typedef long double lld;
lld pi=3.14159265358;
ll powr(ll a,ll b)
{
    ll c=1;
    ll i;
    for(i=0;i<b;i++)
        c*=a;
    return c;
}
ll hell=1000000007;
//ll hell=998244353   ;
ll power(ll x, ll y, ll p)
{
    ll res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
// to generate random number , use rng() ... eg cout<<rng();
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    ll n,i,k;
    ll maxi=0;
    ll gcd=0;
    cin>>n>>k;
    for(i=0;i<n;i++)
    {
        ll p;
        cin>>p;
        gcd=__gcd(gcd,p);
        maxi=max(maxi,p);
    }
    if(((k%gcd)==0) && (k<=maxi))
        cout<<"POSSIBLE";
    else
        cout<<"IMPOSSIBLE";
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;

class Program
{
	static void Main(string[] args)
    {
    	var input = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
   		var bc = input[1] / input[2];
        var ac = input[0] == 0 ? -1 : (input[0]-1)  / input[2];
        Console.WriteLine(bc-ac);
    }
}

Measured memory_bytes: 13396
import java.util.Scanner;

public class Main {
	public static void main(String arges[]){
		String p;
		Scanner sc = new Scanner (System.in);
		p = sc.next();
		int len = p.length();
		for(int i=len-1; i>=0;i--){
				System.out.print(p.charAt(i));
		}
		System.out.println();
		
	}
}

Measured memory_bytes: 17128
#include<iostream>
#include<queue>

void bfs(char map[], int score[],int w,int h) {
	int x = 0;
	int y = 0;
	score[y*w + x] = 1;
	std::queue<std::pair<int, int>>Q;
	Q.push(std::make_pair(0, 0));
	while (!Q.empty()) {
		std::pair<int, int>q = Q.front();
		x = q.first;
		y = q.second;
		Q.pop();
		int dx[] = { 0,0,1,-1 };
		int dy[] = { 1,-1,0,0 };
		for (int i = 0; i < 4; i++) {
			int a = x + dx[i];
			int b = y + dy[i];
			if (a < 0 || b < 0 || a >= w || b >= h)continue;
			if (map[b*w + a] == '.'&&score[b*w + a] == -1) {
				score[b*w + a] = score[y*w + x] + 1;
				Q.push(std::make_pair(a, b));
			}
		}
	}
}

int main() {
	int h, w;
	std::cin >> h >> w;

	char *map = new char[h*w];
	int *score = new int[h*w];
	for (int i = 0; i < h*w; i++) {
		std::cin >> map[i / w * w + i % w];
		score[i] = -1;
	}
	bfs(map, score, w,h);
	int white = 0;
	for (int i = 0; i < h*w; i++) {
		if (map[i / w * w + i % w] == '.')white++;
	}
	if (score[h*w - 1] == -1)printf("-1");
	else printf("%d", white - score[h*w - 1]);
}

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

using namespace std;

typedef unsigned long long ll;

const int N = 200100;

ll x[N];
int n;
ll c;

ll calc(int k) {
    ll s = (n + k - 1) * c;
    for (int i = n - 1; i >= 1; --i) {
        int j = n - i + 1;
        int t = j / 2;
        t = min(t, k);
        j += t - 1;
        ll k1 = j / t;
        ll k2 = k1 + 1;
        k1 *= k1;
        k2 *= k2;
        ll m2 = j % t;
        ll m1 = t - j % t;
        s += (x[i] - x[i - 1]) * (k1 * m1 + k2 * m2 + t);
    }
    return s;
}

int main() {
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    //uniform_int_distribution<int>(l, r)(rng);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> c;
    ++n;
    x[0] = 0;
    for (int i = 1; i < n; ++i) {
        cin >> x[i];
    }
    ll ans = 0;
    int l = 1, r = n;
    while (r - l > 0) {
        int t = (r - l) / 3;
        int m1 = l + t;
        int m2 = r - t;
        ll t1 = calc(m1);
        ll t2 = calc(m2);
        if (r - l == 1) {
            ans = min(t1, t2);
            break;
        }
        if (r - l == 2) {
            ll t3 = calc(l + 1);
            ans = min(t1, t2);
            ans = min(ans, t3);
            break;
        }
        if (t1 > t2) {
            l = m1;
        } else {
            r = m2;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 1792
#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>;

int main() {
  int n;
  cin >> n;
  int d = n % 10;
  n /= 10;
  int c = n % 10;
  n /= 10;
  int b = n % 10;
  n /= 10;
  int a = n % 10;
  bool op1IsPlus = true;
  bool op2IsPlus = true;
  bool op3IsPlus = true;

  int N = 3;
  // 列挙して
  for (int bit = 0; bit < (1 << N); bit++) {
    vector<int> s;
    for (int i = 0; i < N; i++) {
      if (bit & (1 << i)) {
        s.push_back(i);
      }
    }
    // 計算
    int tmpValue = a;
    if (find(s.begin(), s.end(), 0) != s.end()) {
      tmpValue += b;
      op1IsPlus = true;
    } else {
      tmpValue -= b;
      op1IsPlus = false;
    }
    if (find(s.begin(), s.end(), 1) != s.end()) {
      tmpValue += c;
      op2IsPlus = true;
    } else {
      tmpValue -= c;
      op2IsPlus = false;
    }
    if (find(s.begin(), s.end(), 2) != s.end()) {
      tmpValue += d;
      op3IsPlus = true;
    } else {
      tmpValue -= d;
      op3IsPlus = false;
    }
    if (tmpValue == 7) {
      break;
    }
  }

  char op1 = op1IsPlus ? '+' : '-';
  char op2 = op2IsPlus ? '+' : '-';
  char op3 = op3IsPlus ? '+' : '-';

  string result = to_string(a) + op1 + to_string(b) + op2 + to_string(c) + op3 + to_string(d) + "=7";
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val s = readLine()!!
    println(when(s) {
        "SUN"->7
        "MON"->6
        "TUE"->5
        "WED"->4
        "THU"->3
        "FRI"->2
        "SAT"->1
        else ->0
    })
}


Measured memory_bytes: 31720
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>

using namespace std;
using ll = long long int;

int main()
{
  int n;
  cin >> n;
  vector<ll> apples(n);
  for(int i = 0; i < n; i++)
  {
    ll a;
    cin >> a;
    apples[i] = a;
  }
  bool flag = false;
  for(auto e : apples)
  {
    if(e % 2 == 1)
    {
      flag = true;
    }
  }
  if(flag)
  {
    cout << "first" << endl;
  }else{
    cout << "second" << endl;
  }
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
vector<int> A[28];
string s,t;

int main() {
  cin >> s >> t;
  for(int i = 0; i < s.length(); i++) {
    A[s[i] - 'a'].push_back(i);
  }
  /* for(int i = 0; i < 27; i++) {
    for(int j = 0; j < A[i].size(); j++) {
      cout << char(i + 'a') <<"   "<<A[i][j] << endl;
    }
    }*/
  ll ans = 1;
  int p = -1;
  for(int i = 0; i < t.length(); i++) {
    int u = t[i] - 'a';
    if(A[u].size() == 0) {
      cout << -1 << endl;
      return 0;
    }
    int nextp = upper_bound(A[u].begin(),A[u].end(),p) - A[u].begin();
   
    //   cout << "nextp = "<<nextp << endl;
    if(nextp == A[u].size()) {
      ans += (s.length() - p - 1);
      nextp = upper_bound(A[u].begin(),A[u].end(),-1) - A[u].begin();
      //  cout << nextp << endl;
      ans += A[u][nextp] + 1;
      p = A[u][nextp];
    }
    else {
      if(i == 0) p = 0;
      ans += A[u][nextp] - p;
      p = A[u][nextp];
    }
    // cout << "ans = "<<ans << endl;
  }

  cout << ans << endl;
}
  


Measured memory_bytes: 1216
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int main()
{
    int N, tmp;
    cin >> N;
    vector<int> res(N+1);
        for(int x = 1; x <= sqrt(N); ++x)
        {
            for(int y = 1; y <= sqrt(N); ++y)
            {
                for(int z = 1; z <= sqrt(N); ++z)
                {
                    tmp = x*x + y*y + z*z + x*y + y*z + z*x;
                    if(tmp <= N)
                    res[tmp]++;
                }
            }
        }
    for(int i = 1; i <= N; ++i)
    {
        cout << res[i] << "\n";
    }
    return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
const int P=1e9+7;
const int N=1e3+5;
struct Mar{
	int v[2][2];
}x,ans;
Mar operator * (Mar x,Mar y){
	Mar ans;
	for(int i=0;i<2;i++)
		for(int j=0;j<2;j++){
			ans.v[i][j]=0;
			for(int k=0;k<2;k++)
				ans.v[i][j]=(ans.v[i][j]+1LL*x.v[i][k]*y.v[k][j])%P;
		}
	return ans;
}
long long fsp(long long x,long long y){
	long long ans=1;
	while(y){
		if(y&1)	ans=ans*x%P;
		x=x*x%P,y>>=1;
	}
	return ans;
}
long long n;
char s[N][N];
int h,w,s1,s2,rl,ud,cnt;
int main(){
	scanf("%d%d%lld",&h,&w,&n);
	for(int i=1;i<=h;i++)
		scanf("%s",s[i]+1);
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
			if(s[i][j]=='#'){
				s1+=s[i][j-1]=='#';
				s2+=s[i-1][j]=='#';
				++cnt;
			}
	for(int i=1;i<=h;i++)
		if(s[i][1]=='#'&&s[i][w]=='#')	++rl;
	for(int i=1;i<=w;i++)
		if(s[1][i]=='#'&&s[h][i]=='#')	++ud;
	if((rl&&ud)||n<2){
		puts("1");
		return 0;
	}
	if(!rl&&!ud){
		printf("%lld\n",fsp(cnt,n-1));
		return 0;
	}
	if(ud)	swap(s1,s2),swap(rl,ud);

	x.v[0][0]=cnt,x.v[0][1]=s1;
	x.v[1][1]=rl,ans.v[0][0]=ans.v[1][1]=1,--n;
	while(n){
		if(n&1)	ans=x*ans;
		x=x*x,n>>=1;
	}
	printf("%d\n",(ans.v[0][0]-ans.v[0][1]+P)%P);
	return 0;
}


Measured memory_bytes: 1280
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
    string s;
    cin >> s;
    int white_even = 0;
    int black_even = 0;
    int white_odd = 0;
    int black_odd = 0;
    for(int i = 0; i < s.size(); i++){
        if (i % 2 == 0) {
            if (s[i] == '0') {
                white_even++;
            }else{
                black_even++;
            }
        }else{
            if (s[i] == '0') {
                white_odd++;
            }else{
                black_odd++;
            }       
        }
    }
    int ans;
    ans = min(white_even + black_odd, white_odd + black_even);
    cout << ans << '\n';
    
}

Measured memory_bytes: 512
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
constexpr int MOD = 1000000007;
constexpr int INF = 2000000000;
using namespace std;


int main() {
	int t;
	cin >> t;
	int n, k;
	int house[100001];
	for (int h = 0; h < t; h++) {
		vector<int> a;
		cin >> n >> k;
		for (int i = 0; i < n; i++) {
			cin >> house[i];
		}
		if (n <= k) {
			cout << 0 << endl;
			continue;
		}
		for (int i = 0; i + 1 < n; i++) {
			a.emplace_back(house[i + 1] - house[i]);
		}
		sort(a.begin(), a.end());
		int ans = house[n-1]-house[0];
		for (int i = 0; i < k - 1; i++) {
			ans -= a[n - i - 2];
		}
		cout << ans << endl;
	}
}

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

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

bool a[5][5][5][2];
int M1,M2;
int alpha[30], beta[30];

inline bool isValid(int x,int y,int z) { return 0 <= x && x < 5 && 0 <= y && y < 5 && 0 <= z && z < 5; }

bool ok(bool type,int v){
  if( !type ) rep(i,M1) if( alpha[i] == v ) return true;
  if(  type ) rep(i,M2) if(  beta[i] == v ) return true;
  return false;
}

void print(int type){
  rep(z,5) {
    if( z ) puts("");
    rep(y,5) {
      rep(x,5) {
	cout << a[z][y][x][type];
      } puts("");
    }
  }
}

int main(){
  int N,CNT=1;
  bool fu = 1;
  while( cin >> N, N ){
    if( !fu ) puts("");
    fu = false;
    rep(z,5) rep(y,5) {
      string s;
      cin >> s;
      rep(x,5) a[z][y][x][0] = (s[x]=='0'?false:true);
    }

    //print(0);

    cin >> M1; rep(i,M1) cin >> alpha[i];
    cin >> M2; rep(i,M2) cin >> beta[i];
    printf("Case %d:\n",CNT++);
    rep(i,5) rep(j,5) rep(k,5) a[i][j][k][1] = false;

    int phase = 0;    
    rep(day,N) { 
      rep(z,5) rep(y,5) rep(x,5) {
	int cur = phase&1;
	int next = (phase+1)&1;
	bool type = a[z][y][x][cur];
	int cnt = 0;
	for(int dz=-1;dz<=1;dz++){
	  for(int dy=-1;dy<=1;dy++){
	    for(int dx=-1;dx<=1;dx++){
	      if( dz == 0 && dy == 0 && dx == 0 ) continue;
	      int nz = z + dz, ny = y + dy, nx = x + dx;
	      if( !isValid(nx,ny,nz) ) continue;
	      bool v = a[nz][ny][nx][cur];
	      //cout << "(" << nx << "," << ny << "," << nz << ") " << a[nz][ny][nx][cur] << "!!" << endl;
	      if( v ) ++cnt;
	      /*
	      if( !type &&  v ) ++cnt;
	      if(  type && !v ) ++cnt;
	      */
	    }	

	  }	
	}

	if( !type ) a[z][y][x][next] = ( ok(type,cnt) ) ? true : false;
	if(  type ) a[z][y][x][next] = ( ok(type,cnt) ) ? true : false;

      }
      ++phase;
    }

    print(phase&1);

  }
  return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int a,b;
    cin >> a >> b;
    int ans=0;
    if(a<=b){
        for(int i=0;i<b;i++){
            ans*=10;
            ans+=a;
        }
        cout << ans << endl;
    }else{
        for(int i=0;i<a;i++){
            ans*=10;
            ans+=b;
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String args[])
	{
		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int ar[]=new int[n];
		for(int i=0;i<n;i++)
		{
			ar[i]=scan.nextInt();
			
		}
		Arrays.sort(ar);
		if(n%2==1)
		{
			System.out.println(0);
		}else {
			int div=(int) Math.ceil(n/2);
			System.out.println(ar[div]-ar[div-1]);
		}
	}
}


Measured memory_bytes: 49744
#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 vector<vector<int> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

string t;
int ans,p,r,s;
void janken(int x){
    if(t[x]=='r')ans+=p;
    if(t[x]=='s')ans+=r;
    if(t[x]=='p')ans+=s;
    return;
}
int main(){
    int n,k;
    cin >> n >> k >> r >> s >> p;
    ans=0;
    cin >> t;
    rep(i,k){
        janken(i);
    }
    for(int i=k;i<n;i++){
        if(t[i]==t[i-k]){
            t[i]='z';
        }
        else janken(i);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
#1行目
hoge = gets.chomp.to_i - 1

#2行目読み込み
b = gets.chomp.split(" ").map!{|i| i.to_i}

a = []
b[hoge] = 1000000000
b[hoge+1] = 1000000000

a[0] = b[0]

for i in 1..hoge do
  if b[i-1] < b[i]
  a[i] = b[i-1]
else
  a[i] = b[i]
end
end

p a.inject(:+)

Measured memory_bytes: 1788
use proconio::{input, fastout};

#[fastout]
fn main() {
  input!{
      X: i32
  }
  println!("{}",
            if X < 600 {
                8
            } else if X < 800 {
                7
            } else if X < 1000 {
                6
            } else if X < 1200 {
                5
            } else if X < 1400 {
                4
            } else if X < 1600 {
                3
            } else if X < 1800 {
                2
            } else {
                1
            } 
           );
}


Measured memory_bytes: 2192
//プログラミングコンテスト チャレンジブックの 2-6 区間節を参照
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, a, b) for(int i = a, i##_len = (b); i < i##_len; ++i)

const int MAX_SQRT_B = 320; // 約sqrt(1e5);
bool is_prime_small[MAX_SQRT_B];
bool is_prime[3*MAX_SQRT_B+100]; // is_prime[0] := Xが素数かどうか

int main()
{
    int X;
    cin >> X;
    for(int i = 0; i*i <= X; ++i) is_prime_small[i] = true;
    for(int i = 0; i < 3*MAX_SQRT_B; ++i) is_prime[i] = true;

    for(int i = 2; i*i <= X; ++i) {
        if(is_prime_small[i]) {
            for(int j = 2*i; j*j <= X; j += i) is_prime_small[j] = false;
            for(int j = (X%i)? (X/i+1)*i - X : 0; j < 3*MAX_SQRT_B; j += i) is_prime[j] = false;
        }
    }

    for(int i = 0; i < 3*MAX_SQRT_B; ++i) if(is_prime[i]) {
        cout << (i+X) << endl; break;
    }
    return 0;
}

Measured memory_bytes: 256
S = input()

d = S

left = 0
right = len(d) - 1

count = 0
while left < right:
    #print(f'{left=}, {right=}')
    if d[right] == d[left]:
        left += 1
        right -= 1
    else:
        if d[right] == 'x':
            count += 1
            right -= 1
        elif d[left] == 'x':
            count += 1
            left += 1
        else:
            count = -1
            print(-1)
            break

if count != -1:
    print(count)


Measured memory_bytes: 3316
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <typeinfo>
#include <cmath>
using namespace std;

int main(){
    int N;
    std::cin >> N;
    
    std::vector<int> x(110000);
    std::vector<int> y(110000);
    std::vector<int> t(110000);
    x[0] = 0;
    y[0] = 0;
    t[0] = 0;
    for (int i = 1; i < N+1; ++i)
    {
        std::cin >> t[i] >> x[i] >> y[i];
    }
    bool can = true;
    for (int i = 1; i < N+1; ++i)
    {
        int time = t[i] - t[i-1];
        int dis = abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]);
        if(((time - dis)%2 != 0)||(time - dis < 0)){
            // std::cout << "No" << "\n";
            // exit(1);
            can = false;
        }
    }
    if (can) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 1536
m,d = gets.chomp.split(" ").map(&:to_i)
cnt = 0
for i in 1..m do
  for j in 20..d do
    zzz= j/10
    yyy= j%10
    next unless 2 <= yyy
    if i == zzz*yyy
      #print "i=",i,"\n"                                                                 
      #print "zzz=",zzz,"\n"                                                             
      #print "yyy=",yyy,"\n"                                                             
      cnt+=1
    end
  end
end
print cnt,"\n"


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long ll;
int main(void){
    ll d,t,s;
    cin>>d>>t>>s;
    if(s*t>=d){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <algorithm>
#define INF 1000000000
using namespace std;
long long dp[1006][1006] = { 0 };
int main(){
	int n, m;
	scanf("%d %d", &n,&m);
	int d[1001],c[1001];
	for(int i=1;i<=n;i++) cin>>d[i];
	for(int i=1;i<=m;i++) cin>>c[i];
	for(int i=0;i<1001;i++){
		for(int j=0;j<1001;j++){
			dp[i][j]=INF;
		}
	}
	for(int i=0;i<m;i++) dp[0][i]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j]=min(dp[i][j-1],dp[i-1][j-1]+d[i]*c[j]);
		}
	}
	long long ans=INF;
	for(int i=1;i<=m;i++){
		if(ans>dp[n][i]) ans=dp[n][i];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 11096
#include<bits/stdc++.h>
using namespace std;
#define ll	long long 
#define ld long double
#define pb push_back
#define pf push_front
#define mp make_pair
int gcd(int a, int b) 
{ 
	if (a == 0) 
		return b; 
	return gcd(b % a, a); 
} 
int invertBits(int num) 
{  
    int x = log2(num) + 1; 
    for (int i = 0; i < x; i++)  
       num = (num ^ (1 << i));  
   
    return num; 
} 
///////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
	ll int a,b,c,d;
	cin>>a>>b>>c>>d;
	ll int lcm=(c*d)/__gcd(c,d);
	ll int m1=b/c-(a-1)/c;
	ll int m2=b/d-(a-1)/d;
	ll int m3=b/lcm-(a-1)/lcm;
	cout<<(b-a+1)-(m1+m2-m3);
	return 0;
}

Measured memory_bytes: 256
N, K = list(map(int, input().split()))
A = list(map(lambda x: int(x) - 1, input().split()))

now = 0
seen = []
while True:
    seen.append(now)
    teleporter = A[now]
    A[now] = 'used'
    if teleporter == 'used':
        break
    else:
        now = teleporter  

loop_s = seen.index(seen[-1])
size = len(seen) - loop_s - 1

if K <= loop_s:
    print(seen[K] + 1)
else:
    print(seen[loop_s +(K - loop_s) % size] + 1)

Measured memory_bytes: 32376
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define RREP(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define INF 1000000000000
typedef long long ll;

int main()
{
  ll a, b, c, d, ans;
  cin >> a >> b >> c >> d;
  //正正正正
  if (a >= 0 && b >= 0 && c >= 0 && d >= 0)
  {
    ans = b * d;
  }
  //正正負負
  else if ((a >= 0 && b >= 0 && c < 0 && d <= 0) || (a < 0 && b <= 0 && c >= 0 && d >= 0))
  {
    if (a > 0)
    {
      ans = a * d;
    }
    else
    {
      ans = c * b;
    }
  }
  //正正負正
  else if ((a >= 0 && b >= 0 && c <= 0 && d >= 0) || (a <= 0 && b >= 0 && c >= 0 && d >= 0))
  {
    ans = b * d;
  }
  //負負負負
  else if (a <= 0 && b <= 0 && c <= 0 && d <= 0)
  {
    ans = a * c;
  }
  //負負負正
  else if ((a <= 0 && b <= 0 && c <= 0 && d >= 0) || (a <= 0 && b >= 0 && c <= 0 && d <= 0))
  {
    ans = a * c;
  }
  //負正負正
  else
  {
    ans = max(a * c, b * d);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3600
from math import sqrt

n = int(input())
s = int(input())

def f(b, n):
    if n < b:
        return n
    else:
        return f(b, n//b)+(n%b)

def solve(n, s):
    if s == n:
        print(n+1)
        return
    elif s > n:
        print(-1)
        return
    else:
        for i in range(2, int(sqrt(n))+1):
            if f(i, n) == s:
                print(i)
                return
            
        for i in range(int(sqrt(n)), 0, -1):
            b = (n-s)/i+1
            if b == int(b) and f(int(b), n) == s:
                print(int(b))
                return

        print(-1)
        return

solve(n, s)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int inf = 1e6;
inline int read()
{
  int p=0; int f=1; char ch=getchar();
  while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();}
  while(ch>='0' && ch<='9'){p=p*10+(ch-'0'); ch=getchar();}
  return p*f;
}
struct node{int x,y,next;}edge[N]; int len,first[N];
void ins(int x,int y){len++; edge[len].x=x; edge[len].y=y; edge[len].next=first[x]; first[x]=len;}
int n,kk; int l[N],r[N]; int op[N],val[N]; bool bkk=1;

void dfs(int x,int f)
{
  if(val[x] != -1) l[x] = r[x] = val[x],op[x] = val[x]&1;
  else l[x]=-inf,r[x]=inf,op[x]=-1;
  for(int k=first[x];k!=-1;k=edge[k].next)
  {
    int y=edge[k].y;
    if(y==f) continue;
    dfs(y,x);
    if((op[x] == -1) || ((op[x] ^1) == op[y]) || (op[y]==-1))
    {
      l[x] = max(l[x], l[y] - 1);
      r[x] = min(r[x], r[y] + 1);
      if(~op[y]) op[x] = op[y] ^ 1;
    }
    else{bkk=0; return ;}
  }
}

void dfs2(int x,int fa)
{
  if(val[x]==-1)
  {
    if(fa==0)
    {
      for(int i=l[x];i<=r[x];i++) if((i&1) == op[x]){val[x]=i; break;}
    }
	else
	{
	  if(l[x] <= val[fa]-1 && val[fa] - 1 <= r[x]) val[x]=val[fa]-1;
	  else val[x] = val[fa]+1;
	}
  }
  for(int k=first[x];k!=-1;k=edge[k].next)
  {
    int y=edge[k].y;
    if(y==fa) continue;
    dfs2(y,x);
  }
}

int main()
{
  n=read(); len=0; memset(first,-1,sizeof(first));
  for(int i=1;i<n;i++){int x,y; x=read(); y=read(); ins(x,y); ins(y,x);}
  kk=read(); for(int i=1;i<=n;i++) val[i] = -1;
  for(int i=1;i<=kk;i++){int x=read(),v=read(); val[x]=v;}
  dfs(1,0);
  for(int i=1;i<=n;i++)
  {
    if(l[i] > r[i]){bkk=0; break;}
    if((op[i] != -1) && (l[i] == r[i] && (l[i] & 1) != op[i])){bkk=0; break;}
  }
  if(!bkk) printf("No\n");
  else
  {
    printf("Yes\n");
    dfs2(1,0);
    for(int i=1;i<=n;i++) printf("%d\n",val[i]);
  }
  return 0;
}

Measured memory_bytes: 11008
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    int V[n], C[n];
    REP(i, n) cin >> V[i];
    REP(i, n) cin >> C[i];

    int ma =-1;
    for(int mask=0; mask < (1 << n); mask++){
        int X=0,Y=0;
        for(int i=0; i<n; i++)
            if( (mask >> i) &1){
                // cout << "Vi is " << V[i] << " Ci is " << C[i] << endl;
                X+=V[i];  
                Y+=C[i];
            } 
        ma = max(ma, X-Y);
    }
    cout << ma << endl;

    return 0;
}

Measured memory_bytes: 256
import itertools

n = int(input())
a, b =map(int, input().split())
points = list(map(int, input().split()))

cnt = 0
first = []
second = []
third = []
for i in points:
    if i <= a:
        first.append(i)
    elif a+1 <= i and i <= b:
        second.append(i)
    else:
        third.append(i)

ans = min(len(first), len(second), len(third))
print(ans)

Measured memory_bytes: 8832
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<iomanip>
#include<vector>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
using ll = long long;
const int M = 100000;


int main() {
	int n,a,x[50];
	ll ans, dp[55][55][2555];

	cin >> n >> a;
	rep(i,0,n) cin >> x[i];

	//dp[i][j][k]はx[0]~x[i]までの中からj個選んだ時、k=Σx;
	dp[0][0][0]=1;
	rep(i,0,n){
		rep(j,0,i+1) {
			rep(k,0, 2501) {
				//not select;
				dp[i + 1][j][k] += dp[i][j][k];
				//select;
				dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
			}
		}
	}
	ans=0;
	for(int i=1;i<n+1;i++)
		ans += dp[n][i][a*i];

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

Measured memory_bytes: 57600
count = 9
dp = [[[str(i)] for i in range(10)] for j in range(100)]
ans = [i for i in range(1,10)]

keta = 0
while count < 10**5:
    for i in range(10):
        curr = []
        for elem in dp[keta][i]:
            top = int(elem[0])
            if top > 0:
                curr += [str(top-1) + elem]
                if top > 1:
                    ans += [int(str(top-1) + elem)]
            if top < 9:
                curr += [str(top+1) + elem]
                ans += [int(str(top+1) + elem)]
            curr += [str(top) + elem]
            if top > 0 :
                ans += [int(str(top) + elem)]
        dp[keta+1][i] = curr
        count += len(curr)
    keta += 1

ans.sort()

K = int(input())
print(ans[K-1])

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

int N, A[200010], ans;

int main() {
	cin >> N >> A[0];
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
	}
	sort (A, A+N+1);
	ans = A[1]-A[0];
	for (int i = 1; i < N; i++) {
		int x = A[i+1]-A[i];
		ans = __gcd(ans, x);
	}
	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 640
nazo=int(input())
b=nazo%100
a=int(nazo/100)

if 1<=a<=12 and 1<=b<=12:
  print("AMBIGUOUS")
elif a==0 and 1<=b<=12:
  print("YYMM")
elif 1<=a<=12 and b==0:
  print("MMYY")
elif a>12 and 1<=b<=12:
  print("YYMM")
elif 1<=a<=12 and b>12:
  print("MMYY")
else:
  print("NA")

Measured memory_bytes: 3060
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author champon
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1e18
#define ceill(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
ll mod = 1e9+7;
void ans(bool b, ostream& out=cout){ out << (b ? "Yes" : "No") << endl; }
void ans2(bool b, ostream& out=cout){ out << (b ? "YES" : "NO") << endl; }
template<typename T> inline bool chmax(T &a, T b){ if(a<b) a=b; return a<b; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a) a=b; return b<a; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){fill((T*)array, (T*)(array+N), val);}
int dx[] = {1, 0, -1, 0, 1, -1, 1, -1};
int dy[] = {0, 1, 0, -1, 1, -1, -1, 1};

#ifndef INCLUDE_DEBUG_HPP
#define INCLUDE_DEBUG_HPP

class debug
{
public:
    template<typename T> void vdeb(T vec);
    template<typename T1, typename T2> void adeb(T1 *arr, T2 n);
    template<typename T> void mdeb(T mp);
};

#endif //INCLUDE_DEBUG_HPP

template<typename T> void debug::vdeb(T vec)
{
    cout << "#vector set debug" << endl;
    for(auto vv : vec) cout << vv << " ";
    cout << endl;
}

template<typename T1, typename T2> void debug::adeb(T1 *arr, T2 n)
{
    cout << "#adebug" << endl;
    for(int i=0; i<=n; i++) cout << arr[i] << " ";
    cout << endl;
}

template<typename T> void debug::mdeb(T mp)
{
    cout << "#map pair debug" << endl;
    for(auto const& m : mp) cout << m.first sp m.second << endl;
}
debug dbg;

class ATwoCoins {
public:
	void solve(std::istream& in, std::ostream& out)
	{
	    int a, b, c;
	    in >> a >> b >> c;
	    if(a + b >= c) ans(true, out);
	    else ans(false, out);
	}
};


int main() {
	ATwoCoins solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

namespace AtCoder {
    class Practice {
        static void Main() => CustomMain();

        static void Solve() {
            var s = ReadString();

            var b = new bool[3];
            for (int i = 0; i < 3; i++) {
                b[s[i] - 'a'] = true;
            }

            WriteAnswer(b.All(x => x == true) ? "Yes" : "No");
        }


        static void CustomMain() {
#if DEBUG
            // ファイルからテストケースを読み込む
            global::Common.ChangeStdIn();
            // 時間計測
            var stopwatch = new Stopwatch();
            stopwatch.Start();
#endif
            // 出力高速化
            var streamWriter = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
            Console.SetOut(streamWriter);
            // 回答
            Solve();
#if DEBUG
            stopwatch.Stop();
            Console.WriteLine(stopwatch.Elapsed);
#endif
            Console.Out.Flush();
        }

        static string ReadString() => Console.ReadLine().Trim();
        static int ReadInt() => int.Parse(ReadString());
        static long ReadLong() => long.Parse(ReadString());
        static float ReadFloat() => float.Parse(ReadString());
        static double ReadDouble => double.Parse(ReadString());

        static string[] ReadStringArray() => ReadString().Split(' ');
        static int[] ReadIntArray() => Array.ConvertAll(ReadString().Split(' '), int.Parse);
        static long[] ReadLongArray() => Array.ConvertAll(ReadString().Split(' '), long.Parse);
        static float[] ReadFloatArray() => Array.ConvertAll(ReadString().Split(' '), float.Parse);
        static double[] ReadDoubleArray() => Array.ConvertAll(ReadString().Split(' '), double.Parse);

        static T TypeConversion<T>(string s) {
            if (typeof(T) == typeof(int)) {
                return (T) Convert.ChangeType(int.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(long)) {
                return (T) Convert.ChangeType(long.Parse(s), typeof(T));
            } else if (typeof(T) == typeof(double)) {
                return (T) Convert.ChangeType(double.Parse(s), typeof(T));
            } else {
                return (T) Convert.ChangeType(s, typeof(T));
            }
        }

        static void ReadMulti<T, U>(out T a, out U b) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
        }

        static void ReadMulti<T, U, V>(out T a, out U b, out V c) {
            var str = ReadStringArray();
            a = TypeConversion<T>(str[0]);
            b = TypeConversion<U>(str[1]);
            c = TypeConversion<V>(str[2]);
        }

        static void WriteAnswer(object ans) => Console.WriteLine(ans);

        static bool IsOdd(long num) {
            return (num & 1) == 1;
        }

        static bool IsEven(long num) {
            return (num & 1) == 0;
        }

        static long GCD(long a, long b) {
            return b != 0 ? GCD(b, a % b) : a;
        }
    }
}

Measured memory_bytes: 11220