akhauriyash/Code-Regression huggingface dataset:
H, W = gets.split.map(&:to_i)
A = H.times.map { gets.chomp.chars }

queue = []
queue << [0, 0, [[0, 0]]]

DY = [1, 0]
DX = [0, 1]

def check_path(path)
  visited = Array.new(H) { Array.new(W, false) }

  path.each do |y, x|
    visited[y][x] = true
  end

  H.times do |y|
    W.times do |x|
      next if visited[y][x]
      return false if A[y][x] == '#'
    end
  end

  true
end

ans = false

until queue.empty?
  y, x, path = queue.shift

  next if A[y][x] == '.'

  if y == H - 1 && x == W - 1
    ans ||= check_path(path)
  end

  DY.zip(DX).each do |dy, dx|
    ny = y + dy
    nx = x + dx

    next if ny < 0 || nx < 0 || ny >= H || nx >= W

    queue << [ny, nx, path + [[ny, nx]]]
  end
end

if ans
  puts 'Possible'
else
  puts 'Impossible'
end


Measured memory_bytes: 5372
# define _CRT_SECUREj_NO_WARNINGS 1
# define _USE_MATH_DEFINES
# include <iostream>
# include <numeric>
# include <string>
# include <bitset>
# include <vector>
# include <algorithm>
# include <cstdlib>
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iomanip>
# include <queue>
# include <sstream>
# include <climits>
# include <cmath>
# include <list>
# include <functional>
# include <string>
# include <ctime>
# include <set>
# include <forward_list>
# include <map>
# include <stack>
using namespace std;
# define INF ((int)(1<<25))
# define REP(i,n) for(int i=0;i<(int)n;i++)
# define FOR(i,n) REP(i,n)
# define FORI(i,k,n) for(int i=k;i<(int)n;i++)
# define TORAD 2.0*M_PI/360.0
# define INT(x) int x;cin>>x;
# define ALL(x) (x).begin(),(x).end()
# define RALL(x) (x).rbegin(),(x).rend()
# define DEBUG(x) cout<<#x<<":"<<x<<endl;
# define EPS 1e-12
#ifdef _MSC_VER
#include <intrin.h>
#define __builtin_popcount __popcnt
#endif
typedef long long lint;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
const int dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
template<class T> void debug(T a) { for (auto i : a)cout << i << endl; }

int main()
{
	string a[3];
	while (cin >> a[0] >> a[1] >> a[2])
	{
		FOR(i, 3)
		{
			a[i] += a[i].back();
			int ans[2] = {};
			FORI(j, 1, a[i].size())
			{
				ans[a[i][j] == 'B']++;
			}
			cout << ans[0] << " " << ans[1] << endl;
		}
	}
}

Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
int main(){
    int A, B, C, D, N, ans=0;
    char tmp;
    string S;
    cin >> A >> B >> C >> D;
    ans = max(A*B, C*D);
    
    cout <<ans<<endl;
    
    // if(tmp == '-')
    // 	cout << A-B<<endl;
    // else
    // 	cout <<A+B<<endl;
    

    // string S;
    // cin >>S;
    // cout << S + "pp"<<endl;
    // if(A+B==C || B+C==A || C+A==B)
    // 	puts("Yes");
    // else
    // 	puts("No");
    	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define FORD(i,a,b) for(int i = (a); i >= (b); i--)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define M_PI 3.14159265358979323846
template<class C> void mini(C& _a4, C _b4) { _a4 = min(_a4, _b4); }
template<class C> void maxi(C& _a4, C _b4) { _a4 = max(_a4, _b4); }

template<class TH> void _dbg(const char *sdbg, TH h) { cerr << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
	while (*sdbg != ',')cerr << *sdbg++; cerr << '=' << h << ','; _dbg(sdbg + 1, a...);
}

template<class T> ostream& operator<<(ostream& os, vector<T> V) {
	os << "["; for (auto& vv : V) os << vv << ","; os << "]";
	return os;
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L, R> P) {
	return os << "(" << P.st << "," << P.nd << ")";
}


#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#endif

template<typename Out>
void split(const std::string &s, char delim, Out result) {
	std::stringstream ss(s);
	std::string item;
	while (std::getline(ss, item, delim)) {
		*(result++) = item;
	}
}

std::vector<std::string> split(const std::string &s, char delim) {
	std::vector<std::string> elems;
	split(s, delim, std::back_inserter(elems));
	return elems;
}

void trim(string & s) {
	int idx = 0;
	int n = s.size();
	REP(i, n) {
		if (s[i] != ' ' && s[i] != '\t') {
			s = s.substr(i);
			break;
		}
	}
	while (!s.empty()) {
		if (s.back() == ' ' || s.back() == '\t') {
			s.pop_back();
		}
		else {
			break;
		}
	}
}

bool usuwaj;
int nodes;
int32_t main(int32_t argc, char ** argv) {
	ios_base::sync_with_stdio(0);
	string s;
	cin >> s;
	int n = s.size();
	string ts = s;
	ts.erase(remove(ALL(ts), 'x'), ts.end());
	REP(i, ts.size()) {
		if (ts[i] != ts[ts.size() - i - 1]) {
			cout << -1 << endl;
			return 0;
		}
	}
	vector<int> xs;
	int co = 0;
	for (char c : s) {
		if (c == 'x') {
			co++;
		}
		else {
			xs.push_back(co);
			co = 0;
		}
	}
	xs.push_back(co);
	int l = 0;
	int r = xs.size() - 1;
	int res = 0;
	while (l < r) {
		res += abs(xs[l] - xs[r]);
		l++;
		r--;
	}
	cout << res << endl;
}

Measured memory_bytes: 1608
# coding: utf-8

def main():
    h, w = map(int, input().split())

    if h == 1 or w == 1:
        ans = 1
    elif h * w % 2 == 0:
        ans = h * w // 2
    else:
        ans = h * w // 2 + 1

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9112
from math import gcd
N, X = map(int, input().split())
x = list(map(int, input().split()))
x.append(X)
x.sort()
m = 0
for i in range(N):
    if m == 0:
        m = x[i+1]-x[i]
    else:
        m = gcd(m, x[i+1]-x[i])
print(m)


Measured memory_bytes: 20344
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
using namespace std;

int main(){
vector<string> v;
v.push_back("Sunny");
v.push_back("Cloudy");
v.push_back("Rainy");
v.push_back("Sunny");
string s;cin>>s;
for(int i=0;i<3;i++){
    if(s==v[i]){cout<<v[i+1];return 0;}
}
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;

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

	if (X < A) {
		cout << 0 << endl;
	}
	else {
		cout << 10 << endl;
	}
}

Measured memory_bytes: 3608
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define erep(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(),i.rend()
#define INF 1e9
const int mod = 1e9+7;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
  int n,k;
  cin >> n >> k;
  if(n % k) cout<< 1 << endl;
  else cout << 0 << endl;
}


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

int main(void){
  int i,len,min=1000,ans[4]={0};
  char str[301];

  scanf("%s", str);
  len=strlen(str);
  for(i=0;i<len;i++){
    if(str[i]=='K') ans[0]++;
    if(str[i]=='U') ans[1]++;
    if(str[i]=='P') ans[2]++;
    if(str[i]=='C') ans[3]++;
  }
  for(i=0;i<4;i++){
    if(ans[i]<min) min=ans[i];
  }
  printf("%d\n", min);

  return 0;
}


Measured memory_bytes: 536
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if(map.containsKey(a)) {
				map.put(a, map.get(a)+1);
			} else {
				map.put(a, 1);
			}
		}
		int time = map.size() - k < 0 ? 0 : map.size() - k;
		int l = map.values().stream().sorted().limit(time).mapToInt(f -> f).sum();
		System.out.println(l);
	}
}

Measured memory_bytes: 99792
R, G, B, N = map(int, input().split())

r = N // R
g = N // G
b = N // B

c = 0
for i in range(r+1):
    for j in range(g+1):
        n = N - i*R - j*G
        if n < 0:
            continue
        if n % B == 0:
            c += 1

print(c)


Measured memory_bytes: 40812
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
const int MOD = 1000000007;

// vector<p> cut(M);
// cut[i].second
// cut[i].first;
// REP(i,M){
//     int a,b;cin>>a>>b;
//     cut[i] = make_pair(b,a);//last first の順番
// }
//     for(int i=0; i<N;i++){
//     }
// sort(cut.begin(),cut.end()); //sort
// char '' str ""
int main(void)
{
    str S;
    int N,M;cin>>S;

    S[5] = ' ';
    S[13] = ' ';

    cout<<S<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s;
  cin >> s;
  int ans=0;
  for(int i=0;i<s.size();i++){
    int a=(int)s.at(i)-48;
    ans+=a;
  }
  if(ans%9==0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3708
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int mod = 1000000007;
const int INF = 1001001001;

int main(){
    int h,a;
    cin >> h >> a;
    if(h%a==0){
        cout << h/a << endl;
    }else{
        cout << (h/a) + 1 <<endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

void solve(long long N, vector<long long> x, vector<long long> y, vector<long long> h){
	ll rx, ry, rh;
	rep(cx, 101) {
		rep(cy, 101) {
			ll H;
			rep(i, N) {
				if (h[i] > 0) {
					H = h[i]+abs(x[i]-cx)+abs(y[i]-cy);
					break;
				}
			}
			bool flg = true;
			rep(i, N) {
				if (max(H-abs(x[i]-cx)-abs(y[i]-cy),0LL) != h[i]) flg = false;
			}
			if (flg) {
				rx = cx;
				ry = cy;
				rh = H;
			}
		}
	}
	cout << rx << " " << ry << " " << rh << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> y(N-1+1);
	vector<long long> x(N-1+1);
	vector<long long> h(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&x[i]);
		scanf("%lld",&y[i]);
		scanf("%lld",&h[i]);
	}
	solve(N, x, y, h);
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

const double eps = 1e-10;
const double inf = 1e+10;
const double pi = acos(-1.0);
int sgn(double a) { return a < -eps ? -1 : a > eps; }
using P = complex<double>;
namespace std {
  istream& operator>>(istream& i, P& p) { double x, y; i >> x >> y; p = P(x, y); return i; }
  ostream& operator<<(ostream& o, const P& p) { o << real(p) << ' ' << imag(p); return o; }
  bool operator<(const P& p, const P& q) { return sgn(real(p) - real(q)) ? sgn(real(p) - real(q)) < 0 : sgn(imag(p) - imag(q)) < 0; }
  bool operator>(const P& p, const P& q) { return q < p; }
  bool operator<=(const P& p, const P& q) { return !(p > q); }
  bool operator>=(const P& p, const P& q) { return !(p < q); }
}
bool eq(const P& p, const P& q) { return !(p < q) and !(p > q); }
double dot(const P& p, const P& q) { return real(conj(p) * q); }
double cross(const P& p, const P& q) { return imag(conj(p) * q); }

bool comp_y(const P& p, const P& q) {
  return sgn(imag(p) - imag(q)) ? sgn(imag(p) - imag(q)) < 0 : sgn(real(p) - real(q)) < 0;
}

double closest_pair(auto first, auto last) {
  int n = distance(first, last);
  if (n <= 1) return inf;
  auto mid = first + n / 2;
  double x = real(*mid), d = min(closest_pair(first, mid), closest_pair(mid, last));
  inplace_merge(first, mid, last, comp_y);
  V<P> a;
  for (auto itr = first; itr != last; ++itr) {
    if (sgn(abs(real(*itr) - x) - d) > 0) continue;
    for (auto itr2 = a.rbegin(); itr2 != a.rend(); ++itr2) {
      if (sgn(imag(*itr - *itr2) - d) > 0) break;
      d = min(d, abs(*itr - *itr2));
    }
    a.push_back(*itr);
  }
  return d;
}

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n; cin >> n;
  V<P> a(n); for (int i = 0; i < n; i++) cin >> a[i];
  sort(a.begin(), a.end());
  cout << fixed << setprecision(10) << closest_pair(a.begin(), a.end()) << '\n';
}


Measured memory_bytes: 7892
#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T>
using VEC = std::vector<T>;
template <class T>
using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail>
void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec) os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, map<T1, T2> &m) {
  os << "{";
  for (auto p : m) os << p << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}
#define ull unsigned long long
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1n(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init) \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;

int main() {
  int n;
  cin >> n;
  VEC<int> a(n);
  REP(i, 0, n) cin >> a[i];
  sort(ALL(a));
  int ans = 0;
  for (int nibeki = 1 << 30; nibeki > 1; nibeki >>= 1) {
    for (int left = 0, right = n - 1; left < right;) {
      if (a[left] < 1) {
        ++left;
      } else if (a[right] < 1) {
        --right;
      } else {
        int sum = a[left] + a[right];
        if (sum == nibeki) {
          a[left] = a[right] = -1;
          --right;
          ++left;
          ++ans;
        } else if (sum < nibeki)
          ++left;
        else if (sum > nibeki)
          --right;
      }
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>
  
int main(void){

	 ios::sync_with_stdio(false);	cin.tie(0);
	
	 int n,k,p;
	 string s,t;
  	 cin >> n;
 	 M m;
 	 REP(i,n){	int a; cin >> a; m[a]++;  }
	  V v;
	  for(auto a : m){
	    if(a.second>=2) v.push_back(a.first);
  	 	if(a.second>=4) v.push_back(a.first);
  	  }
 	 sort(v.rbegin(),v.rend());
 	 cout << (v.size() ? (ll)v[0]*v[1] : 0) << endl;
  	return 0;
}

Measured memory_bytes: 4992
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W = map(int, readline().split())
    ans = [0] * (H + 2)
    ans[0] = '#' * (W + 2)
    for i in range(1, H + 1):
        ans[i] = '#' + readline().strip() + '#'
    ans[H + 1] = '#' * (W + 2)

    print(*ans, sep='\n')

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 62208
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
          	var input_A = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
            var S = Console.ReadLine().ToCharArray();
            S[input_A[1]-1] = Char.ToLower(S[input_A[1]-1]);
            Console.WriteLine(S);
        }
    }
}


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

vector<ll> get_div(ll n){
	vector<ll> div;
	for(ll i(1);i*i<=n;++i){
		if(n%i == 0){
			div.push_back(i);
			if(i * i != n) div.push_back(n / i);
		}
	}
	sort(div.begin(),div.end());
	return div;
}

int main(){
	int n,k;
	cin >> n >> k;
	vector<ll> a(n);
	ll s(0);
	rep(i,n){
		cin >> a[i];
		s+=a[i];
	}
	vector<ll> div = get_div(s);
	ll ans(0);
	rep(i,div.size()){
		ll d = div[i];
		auto b = a;
		ll s1(0),s2(0);
		rep(j,n){
			b[j] %= d;
			s1 += d-b[j];
		}
		sort(b.begin(),b.end());
		rep(j,n){
			s2 += b[j];
			s1 -= d-b[j];
			if(s1 == s2) break;
		}
		if(s2 <= k && ans < d) ans = d;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
   
 int n,k; 
 cin >> n >> k;
 int ans =0;
 vector <int>p(n);
 rep(i,n) cin >> p[i];
 sort(p.begin(),p.end());
 //rep (i,n) cout << p[i] << " ";
 rep(i,k) ans +=p[i];


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

Measured memory_bytes: 3636
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, U, V = lr()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

def dfs(start): # 木グラフの時
    dist = [-1] * (N+1)
    dist[start] = 0
    stack = [start]
    while stack:
        s = stack.pop()
        for x in graph[s]:
            if dist[x] != -1:
                continue
            dist[x] = dist[s] + 1
            stack.append(x)
    return dist

dist_U = dfs(U)
dist_V = dfs(V)
answer = max(v for u, v in zip(dist_U, dist_V) if v > u) - 1
print(answer)


Measured memory_bytes: 62136
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()

int main(void)
{
    string s;cin >> s;

    int ans = 0;
    bool b = false;
    if(s[0] == 'R') {
        ans ++;
        b = true;
    }
    for(int i = 1; i < 3; i++) {
        if(s[i] == 'R' && b) {
            ans ++;
        } else if(s[i] == 'R' && !b) {
            ans = 1;
            b = true;
        } else {
            b = false;
        }
    }

    cout << ans << endl;
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)

typedef long long ll;

int main() {
	ll n, x;
	cin >> n >> x;
	
	ll ans = 0;
	ll a = x, b = n - x; //a < b
	if (a > b) swap(a, b);
	
	ans = a + b;
	while (true) {
		ans += (b / a) * 2 * a;
		if (b % a == 0) break;
		
		ll tmp = a;
		a = b % a;
		b = tmp;
	}
	ans -= a;
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a,const void *b){
  return *(int *)b - *(int *)a;
}

int main(void){
  int N;
  int i;
  int S=0;
  scanf("%d",&N);
  int a[N];
  for(i=0;i<N;i++) scanf("%d",&a[i]);
  qsort(a,N,sizeof(int),cmp);
  for(i=0;i<N;i++){
    if(i%2==0) S+=a[i];
    else S-=a[i];
  }
  printf("%d",S);
  return 0;
}


Measured memory_bytes: 128
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番

    if i==j:
        SCORE[i][j]=0
        return
        
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k

    if l==1:
        SCORE[i][j]=max(SCORE[i+1][j]+A[i],SCORE[i][j-1]+A[j-1])-k

    else:
        SCORE[i][j]=min(SCORE[i+1][j]-A[i],SCORE[i][j-1]-A[j-1])-k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[0][N])

Measured memory_bytes: 173320
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
//ranker
using namespace std;

#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using psi = pair<string, int>;
using D = double;


const int Max=10000000;
bool prime[Max];
int main(void){
    int in;
    for(int i=0;i<Max;i++)prime[i]=true;
    prime[1]=false;
    for(int i=2;i<Max;i++){
        if(prime[i]){
            for(int s=i*2;s<=Max;s+=i)prime[s]=false;
        }
    }
    while(cin>>in){
        int cnt=0;
        for(int i=1;i<=in;i++){
            if(prime[i])cnt++;
        }
        cout << cnt << "\n";
    }
    return 0;
}

Measured memory_bytes: 12776
n = int(input())
s = input()
ans = 0
for i in range(10):
    if str(i) in s:
        t = s[s.index(str(i))+1:]
        # print(t)
        for j in range(10):
            if str(j) in t:
                u = t[t.index(str(j))+1:]
                # print(u)
                for k in range(10):
                    if str(k) in u:
                        #print(i, j, k)
                        ans += 1

print(ans)


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

using namespace std;
 
#define MAX 1000
 
int solve(int size, char g[MAX][MAX])
{
    int dp[MAX][MAX];
     
    for (int i = 0; i < size; i++) {
        dp[0][i] = (g[0][i] == '*') ? 0 : 1;
        dp[i][0] = (g[i][0] == '*') ? 0 : 1;
    }
 
    int mw = 0;
    for (int i = 1; i < size; i++) {
        for (int j = 1; j < size; j++) {
            if (g[i][j] =='*') {
                dp[i][j] = 0;
            } else{
                dp[i][j] = min(dp[i-1][j-1] ,min(dp[i-1][j], dp[i][j-1])) + 1;
                mw = max(mw, dp[i][j]);
            }
        }
    }
    return mw;
}
 
int main()
{
    int n;
    char g[MAX][MAX];
    while (cin >> n, n) {
	for (int i = 0; i < n; i++) {
	    for (int j = 0; j < n; j++) {
		cin >> g[i][j];
	    }
	}
	cout << solve(n, g) << endl;
    }
    return 0;
}

Measured memory_bytes: 7924
#include<bits/stdc++.h>
#define maxn 200050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct node{
	int m,l,r;
	node(int m,int l,int r):m(m),l(l),r(r){}
	bool operator < (const node& x) const{
		return m>x.m;
	}
};
int dp[2][maxn][36]; 
int pos[maxn];
int a[2][maxn];
void makermq(int n,int f){  
    for(int i=0;i<n;i++) dp[f][i][0]=a[f][i];  
    for(int j=1;(1<<j)<=n;j++)  
        for(int i=0;i+(1<<j)-1<n;i++)  
            dp[f][i][j]=min(dp[f][i][j-1],dp[f][i+(1<<(j-1))][j-1]);  
}  
int rmq(int s,int v,int f){
    int k=(int)(log((v-s+1)*1.0)/log(2.0));  
    return min(dp[f][s][k],dp[f][v-(1<<k)+1][k]);  
}  
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n; cin>>n;
	mm(pos,0);
	for(int i=0;i<n;i++){
		int x; cin>>x;
		pos[x]=i;
		a[i&1][i]=x;
		a[(i&1)^1][i]=inf;
	}
	makermq(n,0),makermq(n,1);
	int x1=rmq(0,n-1,0);
	priority_queue<node>q;
	q.push(node(x1,0,n-1));
	while(!q.empty()){
		node x=q.top(); q.pop();
		int v1=x.m;
		int v2=rmq(pos[v1]+1,x.r,(pos[v1]&1)^1);
		cout<<v1<<" "<<v2<<" ";
		int pos1=pos[v1],pos2=pos[v2];
		if(pos1!=x.l) q.push(node(rmq(x.l,pos1-1,x.l&1),x.l,pos1-1));
		if(pos1+1!=pos2) q.push(node(rmq(pos1+1,pos2-1,(pos1+1)&1),pos1+1,pos2-1));
		if(pos2!=x.r) q.push(node(rmq(pos2+1,x.r,(pos2+1)&1),pos2+1,x.r));
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 60792
def main():
    N = int(input())
    a = list(map(int,input().split()))
    ANS = ""
    xor_all = 0
    for i in range(N):
        xor_all = xor_all^a[i]
    for i in range(N):
        if ANS != "":
            ANS += " "
        ANS += str(xor_all^a[i])
    print(ANS)
if __name__ == '__main__':
    main()

Measured memory_bytes: 31628
per_price, takahashi_all_money, count_satisfied_sound = map(int, input().split())

need_money_of_satisfied = count_satisfied_sound * per_price

if takahashi_all_money >= need_money_of_satisfied:
    print(count_satisfied_sound)
elif takahashi_all_money < need_money_of_satisfied:
    print(takahashi_all_money // per_price)

Measured memory_bytes: 9084
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

int gcd(int a, int b){
	if (b == 0)return a;
	return gcd(b, a % b);
}

//-----------------------ここから-----------


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

	int ans = 0;

	for(int i = 0; i <= a; i++){
		for(int j = 0; j <= b; j++){
			for(int k = 0; k <= c; k++){
				if(500 * i + 100 * j + 50 * k == x){
					ans++;
				}
			}
		}
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> a(n);
    rep(i, n)cin >> a[i];
    sort(a.begin(), a.end());
    ll INF = 200001;
    ll l = 1;
    ll r = INF;
    ll cnt;
    while(l + 1 < r){
        ll x = (l + r) / 2;
        cnt = 0;
        rep(i, n){
            int nl = -1;
            int nr = n;
            while(nl + 1 < nr){
                int nx = (nl + nr) / 2;
                if(a[i] + a[nx] > x)nr = nx;
                else nl = nx;
            }
            cnt += n - nr;
        }
        if(cnt >= m)l = x;
        else r = x;
    }
    cnt = 0;
    ll ans = 0;
    vector<ll> sum(n+1, 0);
    rep(i, n)sum[i+1] = sum[i] + a[i];
    rep(i, n){
        int nl = -1;
        int nr = n;
        while(nl + 1 < nr){
            int nx = (nl + nr) / 2;
            if(a[i] + a[nx] > l)nr = nx;
            else nl = nx;
        }
        cnt += n - nr;
        ll s = sum[n] - sum[nr] + (n-nr) * a[i];
        ans += s;
    }
    ans -= (cnt - m) * r;
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;
 
int D[100];
 
int main()
{
	int n, r=0;
	cin >> n;
	for (int i = 0; i < n; ++i)
    {
		cin >> D[i];
    }
	for (int i = 0; i < n; ++i)
	{
		for (int j= i + 1; j < n; ++j)
		{
			int x = D[i];
			int y = D[j];
          r = r + x*y;
		}	
	}
	cout << r;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define MOD 1000000007
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define FOR(a,n) for(int i=a;i<n;++i)
#define arrin(n) for(int i=0; i < n; ++i) cin>>arr[i];
#define arrout(n) for(int i=0; i < n; ++i) cout<<arr[i]<<" ";cout<<nl;
#define nl "\n"
#define mp make_pair
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
using namespace std;
 
int freq[2000000];
int main(){  
  fastio();
  int n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    int tmp;
    cin>>tmp;
    freq[tmp]++;
  }
  vector<int> v;
  for(int i=0;i<=n;i++){
    if(freq[i]) v.pb(freq[i]);
  }
  sort(v.begin(), v.end());
  int ans=0;
  for(int i=v.size()-k-1;i>=0;i--)ans+=v[i];
  cout<<ans;
  return 0;

} 



    

  

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

int main(){
    long long N, M;
    cin >> N >> M;
    priority_queue<long long, vector<long long>, greater<long long> > que;
    int i = 1;
    while(i*i <= M){
        if(M%i == 0){
            que.push(i);
            que.push(M/i);
        }
        i++;
    }
    while(que.top() < N){
        que.pop();
    }
    cout << M/que.top() << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
    int n;
    scanf("%d",&n);
    int i,j,cnt,devisor;
    cnt = 0;

    for(i=1;i<=n;i+=2){
        devisor=0;
        for(j=1;j<=i;j++){
        if(i%j==0){
            devisor++;
            }
        }
        if(devisor==8){
        cnt++;
        }
    }
    printf("%d",cnt);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    long long t , n;
    cin>>t>>n;
    if(t*500<n)
    cout<<"No";
    else
    cout<<"Yes";
    
    return 0;
}

Measured memory_bytes: 3520
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int H = Integer.parseInt(sc.next());
		int W = Integer.parseInt(sc.next());
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());

		sc.close();

		StringBuilder zeroSB = new StringBuilder();
		StringBuilder oneSB = new StringBuilder();

		for(int i = 1;i <= A;i++) {
			zeroSB.append("0");
			oneSB.append("1");
		}
		String zeroA = zeroSB.toString();
		String oneA = oneSB.toString();
		for(int i = A + 1;i <= W - A;i++) {
			zeroSB.append("0");
			oneSB.append("1");
		}
		String zeroWmA = zeroSB.toString();
		String oneWmA = oneSB.toString();

//		System.out.println(zeroA);
//		System.out.println(oneA);
//		System.out.println(zeroWmA);
//		System.out.println(oneWmA);

		for(int tate = 1;tate <= B;tate++) {
			System.out.print(zeroA);
			System.out.println(oneWmA);
		}
		for(int tate = B + 1;tate <= H;tate++) {
			System.out.print(oneA);
			System.out.println(zeroWmA);
		}

	}
}

Measured memory_bytes: 23636
import std.functional,
       std.algorithm,
       std.container,
       std.typetuple,
       std.typecons,
       std.bigint,
       std.string,
       std.traits,
       std.array,
       std.range,
       std.stdio,
       std.conv,
       std.format,
       std.math;

void main()
{
	auto ip = readln.chomp;
	if(ip[0] == ip[2]) writeln("=");
	else if(ip[0] < ip[2]) writeln("<");
	else writeln(">");
}

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

long long int gcm(long long a,long long b){
	long long r,tmp;
	if(a<b){
		tmp=a;
		a=b;
		b=tmp;
	}
	
	r=a%b;
	while(r!=0){
		a=b;
		b=r;
		r=a%b;
	}
	return b;
}

int main(){
	long long A,B,C,D;
	cin >> A >> B >> C >> D;
	long long ans=B-A+1;
	long long CD=C/gcm(C,D)*D;
	
	ans-=B/C+B/D-B/CD;
	A--;
	ans+=A/C+A/D-A/CD;
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <fstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b + c >= 22) cout << "bust";
    else cout << "win";
}


Measured memory_bytes: 3612
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip> // double
#include <cctype> // isupper, islower, toupper, tolower
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int ans(string s) {
    int sum = 0;
    rep(i,s.size()) {
      sum += (int)s[i] - '0';
    }
    return sum;
}

int main() {
  ios::sync_with_stdio(false);
  while(1) {
      string s;
      cin >> s;
      if(s == "0") break;
      int sum = ans(s);
      cout << sum << endl;
  }
}



Measured memory_bytes: 3204
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>



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

using namespace std;
int a,b,c,x;
int ans;
int main(){
  cin >> a >> b >> c >> x;
  REP(i,a+1){
    REP(j,b+1){
      REP(k,c+1){
        if(500*(i)+100*(j)+50*(k)==x) ans ++;
        //cout << i << " "<< j << " "<< k << endl;
        //cout << 500*(i)+100*(j)+50*(k) << endl;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main (void)
{
	int a,b;
	scanf("%d",&a);
	scanf("%d",&b);
	if(a>=1&&a<=1E+9)
	{
		if(b>=1&&b<=1E+9)
		{
			printf("%d %d %lf",a/b,a%b,(double)a/b);
		}
		else
		{
		}
		}
	else
	{
	}
	return 0;
}

Measured memory_bytes: 636
n,k=map(int,input().split())
a=list(map(int,input().split()))
def ligh(li):
  for x in range(k):
    if li==[n]*n:
      return li
    ne=[0]*(n+1)
    zr=[]
    lis=[]
    for (i,a) in zip(range(n),li):
      if a==0:
        zr.append(i)
      else:
        ne[max(0,i-a)]+=1
        ne[min(i+a+1,n)]-=1

    for i in range(1,n):
      ne[i]+=ne[i-1]
    for i in zr:
      ne[i]+=1
    li=ne[:-1]
    #print(li)
  return li

for i in ligh(a):
  print(i,end=" ")


Measured memory_bytes: 170312
#include"bits/stdc++.h"
//#include<bits/stdc++.h>
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long ll;
const ll mod = LLONG_MAX;

int main() {
	string w;
	cin >> w;
	int count[27] = {};
	rep(i, 0, w.size()) {
		count[w[i]-'a']++;
	}
	rep(i, 0, 27) {
		if (count[i] % 2 != 0) {
			print("No"); return 0;
		}
	}
	print("Yes");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
long long mod = 1000000007;
int main(){
    long long n,m,x,y;
    long long xsum,ysum,ans;
    cin >> n >> m;
    xsum = 0;
    ysum = 0;
    for(long long i=1;i<=n;i++){
        cin >> x;
        xsum += (2*i-n-1)*x;
        xsum %= mod;
    }
    for(long long i=1;i<=m;i++){
        cin >> y;
        ysum += (2*i-m-1)*y;
        ysum %= mod;
    }
    ans = xsum * ysum % mod;
    cout << ans << endl;
    return 0;
}


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

typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;

#define endl '\n'
#define ff first
#define ss second
#define int long long
#define pb push_back
#define f(i,l,r) for(ll i=l;i<=r;i++)
#define rf(i,r,l) for(ll i=r;i>=l;i--)
#define Max 5000001
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

#define d0(a) cout<<a<<' ';
#define d1(a) cout<<a<<endl;
#define d2(a,b) cout<<a<<' '<<b<<endl;
#define d3(a,b,c) cout<<a<<' '<<b<<' '<<c<<endl;
#define d4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
#define d5(a,b,c,d,e) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<endl;
#define d6(a,b,c,d,e,f) cout<<a<<' '<<b<<' '<<c<<' '<<d<<' '<<e<<' '<<f<<endl;

const ll N=1e5+5,mod=1e9+7,bit=61;
const ld PI=acos(-1.00);


signed main()
{
    fast;

    ll t=1;
    //cin>>t;
    while(t--)
    {
        ll x;
        cin>>x;
        ld c=100;
        for(int i=1;;i++)
        {
            c=(1.01)*(ld)c;
            c=(ll)c;
            if(c>=x)
            {
                cout<<i<<endl;
                return 0;
            }
        }
    }
    return 0;
}


















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

using namespace std;
int n,m;
int a[200009];
int main()
{
 int a,b;
 cin>>n>>m>>a>>b;
 if(n+m>a+b)
    cout<<"Left";
 else if(n+m<a+b)
    cout<<"Right";
 else cout<<"Balanced";
}


Measured memory_bytes: 256
import Data.List

main=do
    [a,b,c,d,e,f]<-map read.words<$>getLine::IO[Int]
    let (w,s) = maximumBy fc $ concatMap (\(e,w)-> map (\s->(w+s,s)) $ ss c d e) $ map (ee f e) $ ws f a b
    --
    putStrLn $ show w ++ " " ++ show s

ws f a b =[(aa*100*a+bb*100*b)|aa<-[0..f`div`(100*a)],bb<-[0..(f-100*aa*a)`div`(100*b)]]

ee f e w =(min ((w`div`100)*e) (f-w), w)
    
ss c d e = [(cc*c+dd*d)|cc<-[0..e`div`c], dd<-[0..(e-cc*c)`div`d]]

fc (w1,s1) (w2,s2) = compare (s1*w2) (s2*w1)

Measured memory_bytes: 99964
#include <bits/stdc++.h>
#include <unordered_set>
#include <stdio.h>

using namespace std;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define endl "\n"
#define PI 3.141592653589793
#define vi vector<int>
#define vll vector<long long>
#define p pair<int,int>
const int MOD = 1000000007;
inline double degcos(double ang) {return cos(ang*PI/180);}
inline double degsin(double ang) {return sin(ang*PI/180);}
#define rep(i,j,k,in) for (int i = j; i < k; i += in)
#define repr(i,j,k,in) for (int i = j; i > k; i -= in)
#define repll(i,j,k,in) for (ll i = j; i < k; i += in)
#define repllr(i,j,k,in) for (ll i = j; i > k; i -= in)

/*---END OF TEMPLATE---*/

int N;
const int MAXN = 200005;
unordered_map<int,int> mp;



struct Entry {
    int h;
    ll val;
} arr[MAXN];

struct Node {
    int L,R;
    ll mx;
}seg[4*MAXN];


void buildTree(int v, int L, int R) {
    seg[v].L = L;
    seg[v].R = R;
    if (L == R) {
        seg[v].mx = 0;
        mp[L] = v;
        return;
    }
    int mid = (L+R)/2;
    buildTree(v*2,L,mid);
    buildTree(v*2+1, mid+1,R);
    seg[v].mx = max(seg[v*2].mx,seg[v*2+1].mx);
}

void update(ll val, int U) {
    int v = mp[U];
    while (v > 0) {
        if (val > seg[v].mx) {
            seg[v].mx = val;
            v = v/2;
        }
        else break;
    }
}

ll query(int v, int QL, int QR) {
    int L = seg[v].L, R = seg[v].R;
    if (R < QL || QR < L) return 0;
    if (QL <= L && R <= QR) {
        return seg[v].mx;
    }
    return max(query(v*2,QL,QR),query(v*2+1,QL,QR));
}


int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    //ifstream fin("data.in");
    //ofstream fout("data.out");
    cin >> N;
    rep(i,0,N,1) {
        cin >> arr[i].h;
        arr[i].h--;
    }
    rep(i,0,N,1) {
        cin >> arr[i].val;
    }
    buildTree(1,0,N-1);
    rep(i,0,N,1) {
        ll nxtVal = query(1,0,arr[i].h)+arr[i].val;
        update(nxtVal,arr[i].h);
    }
    cout << query(1,0,N-1);

}

Measured memory_bytes: 22912
#include<bits/stdc++.h>
using namespace std;
#define maxn 100020
#define rep(i,l,r) for(register int i = l ; i <= r ; i++)
#define repd(i,r,l) for(register int i = r ; i >= l ; i--)
#define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++)
#define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--)
#define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next)
#define pb push_back
#define prev prev_
#define stack stack_
#define mp make_pair
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef pair<int,int> pr;

int a[maxn],n,s[maxn],cnt[maxn * 2],tmp = 1e5 + 5;
ll num;

inline void modify(int x,int d){
	for (register int i = x ; i <= n + tmp ; i += lowbit(i)) cnt[i] += d;
}
inline int query(int x){
	int res = 0;
	for (register int i = x ; i ; i -= lowbit(i)) res += cnt[i];
	return res;
}
inline ll cal(int mid){
	rep(i,1,n) s[i] = s[i - 1] + ((a[i] <= mid) ? 1 : -1);
	rep(i,1,n + tmp) cnt[i] = 0;
	ll res = 0;
	rep(i,1,n){
		modify(s[i - 1] + tmp,1);
		res += query(s[i] + tmp - 1);
	}
	return res;
}

int main(){
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",&a[i]);
	int l = 1 , r = 1e9 , ans = 0;
	num = (ll)n * (n + 1) / 4 + 1;
	while ( l <= r ){
		int mid = (l + r) >> 1;
		if ( cal(mid) >= num ) ans = mid , r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n",ans);
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
const int M = 18;
int dp[M][(1<<M)],a[M],b[M],val[M][(1<<M)];
int n;
int getVal(int prv, int mask)
{
	int t = __builtin_popcount(mask);
	t--;
	t = abs(t - prv);
	if(t%2)
		return b[prv];
	else
		return a[prv];
}
int solve(int x,int mask)
{
	if(mask+1 == (1<<n))
		return 0;
	if(dp[x][mask] != -1)
		return dp[x][mask];
	dp[x][mask] = 1e9;
	int z = getVal(x,mask);
	for(int j=0;j<n;j++)
	{
		if((mask&(1<<j))==0)
		{
			int newMask = (mask|(1<<j));
			int y = getVal(j,newMask);
			if(y>=z)
				dp[x][mask] = min(dp[x][mask], val[j][mask]+solve(j,newMask));
		}
	}
	return dp[x][mask];
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<n;i++)
		cin>>b[i];
	memset(dp,-1,sizeof(dp));
	int ans = 1e9;
	for(int i=0;i<n;i++)
	{
		for(int mask = 0;mask<(1<<n);mask++)
		{
			if((mask&(1<<i)))
				continue;
			int z = 0;
			for(int j=0;j<n;j++)
			{
				if(j<i)
				{
					if((mask&(1<<j))==0)
						z++;
				}
				if(j>i)
				{
					if((mask&(1<<j)))
						z++;
				}
			}
			val[i][mask] = z;
		}
	}
	for(int i=0;i<n;i++)
	{
		ans = min(ans,i+solve(i,(1<<i)));
	}
	if(ans!=1e9)
		ans/=2;
	if(ans==1e9)
		ans = -1;
	cout<<ans<<"\n";
	return 0;
}	

Measured memory_bytes: 37372
#-*- coding: utf-8 -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime
import re
import math
def sol(a, b):
    c = 1
    ans = 0
    if c >= b: return ans

    while c < b:
        c += a - 1
        ans += 1
    return ans



do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    # n = int(parsed_lines[0][0])
    # k = int(parsed_lines[0][1])
    S = parsed_lines[0][0]
    return S


if not do_submit:
    S = input_parse("""
    1905
    """)
    print(sol(S))

    S = input_parse("""
    0112
    """)
    print(sol(S))

    S = input_parse("""
    1700
    """)
    print(sol(S))

    S = input_parse("""
    0000
    """)
    print(sol(S))

    S = input_parse("""
    1001
    """)
    print(sol(S))



else:
    A, B = list(map(int, input().split()))
    #S = input()
    print(sol(A, B))

    # S = input().strip()
    # print(sol(S))





Measured memory_bytes: 3688
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()

d = []
for i in range(1,int(N**.5)+1):
    if N % i == 0:
        d.append(i)
        if i != N//i:
            d.append(N//i)

d.sort()
a = len(d)

if a % 2 == 0:
    print(d[(a-1)//2] + d[(a+1)//2] - 2)
else:
    print(d[(a-1)//2]*2 - 2)

Measured memory_bytes: 64664
from collections import defaultdict


class DisjointSet:

    def __init__(self, N):
        self.parents = [i for i in range(N)]
        self.count = N

    def find(self, x):
        path = []
        while self.parents[x] != x:
            x = self.parents[x]
            path.append(x)
        for p in path:
            self.parents[p] = x
        return x

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if self.find(root_x) != self.find(root_y):
            self.parents[root_x] = root_y
            self.count -= 1


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def read_oneless_ints():
    return [int(a)-1 for a in input().strip().split(' ')]


def solve():
    N, K, L = read_ints()
    disjoint_set_roads = DisjointSet(N)
    disjoint_set_railways = DisjointSet(N)

    for _ in range(K):
        u, v = read_oneless_ints()
        disjoint_set_roads.union(u, v)
    for _ in range(L):
        u, v = read_oneless_ints()
        disjoint_set_railways.union(u, v)
    G = defaultdict(list) # (p1, p2) -> [nodes]
    for i in range(N):
        G[(disjoint_set_roads.find(i), disjoint_set_railways.find(i))].append(i)
    answer = [None]*N
    for city_list in G.values():
        for city in city_list:
            answer[city] = len(city_list)
    for a in answer:
        print(a)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 140952