akhauriyash/Code-Regression huggingface dataset:
s=input()
n=len(s)
dp=[list(0 for i in range(13)) for j in range(n)]
MOD=10**9+7
if s[0]=="?":
    for k in range(0,10):
        dp[0][k]+=1
else:
    dp[0][int(s[0])]+=1
for i in range(0,n-1):
    for k in range(13):
        if s[i+1]=="?":
            for j in range(10):
                ct=(k*10+j)%13
                dp[i+1][ct]+=dp[i][k]
                dp[i+1][ct]%=MOD
        elif s[i+1]!="?":
            tmp=(int(s[i+1])+k*10)%13
            dp[i+1][tmp]+=dp[i][k]
            dp[i+1][tmp]%=MOD
print(dp[n-1][5])

Measured memory_bytes: 66524
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)


using namespace std;
using ll = long long;

const int mod = 1000000007;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main(void)
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    int n,k;
    cin >> n >> k;
    mint N=n,K=k,ans=0;
    for(int i=k;i<=n+1;i++)
    {
        mint I=i;
        ans +=N*I-I*I+I+1;
    }
     cout << ans << endl;

    return 0;
}


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

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

int main() {
  int N, K, M = 1e9 + 7;
  cin >> N >> K;
  long ans = 0;
  vector<long> DP(K + 1);
  for (int i = K; i >= 1; i--) {
    DP.at(i) = modpow(K / i, N, M);
    for (int j = i + i; j <= K; j += i) DP.at(i) -= DP.at(j);
    ans += i * DP.at(i) % M;
  }
  cout << ans % M << "\n";
}

Measured memory_bytes: 3988
local function range(b, e)
  local t = {}
  for i=1,e-b+1 do
    t[i] = b+i-1
  end
  return t
end
local function all(t, f)
  for k,v in pairs(t) do
    if not f(v) then
      return false
    end
  end
  return true
end

local function map(t, f)
  local nt = {}
  for k,v in pairs(t) do
    nt[k] = f(v)
  end
  return nt
end

local H, W = io.read("n", "n", "l")
local A = {}
for h=1,H do
  A[h] = {}
  for w=1,W do
    local a = io.read(1)
    A[h][w] = a
  end
  io.read("l")
end

local rangeh = range(1,H)
local rangew = range(1,W)

RH = map(rangeh, function(h) return all(rangew, function(w) return A[h][w]=='.' end) end)
RW = map(rangew, function(w) return all(rangeh, function(h) return A[h][w]=='.' end) end)


for h=1,H do
  if not RH[h] then
    for w=1,W do
      if not RW[w] then
        io.write(A[h][w])
      end
    end
    print()
  end
end



Measured memory_bytes: 2892
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    a = list(map(int, input().split()))
    L = [0]*(N+1)
    R = [0]*(N+1)
    for i in range(N):
        L[i+1] = L[i]^a[i]
        R[N-i-1] = R[N-i]^a[N-i-1]
    ans = [None]*N
    for i in range(N):
        ans[i] = L[i]^R[i+1]
    print(*ans)
    # print(L,R)


if __name__ == "__main__":
    main()

Measured memory_bytes: 43472
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n, x;
	cin >> n >> x;
	int ans = 1;
	int sum = 0;
	while (n--)
	{
		int val;
		cin >> val;
		sum += val;
		if (sum > x) break;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
use utf8;
use warnings;
use strict;

use feature qw/say/;

chomp(my $line = <>);
my ($n, $k) = split(/ /, $line);

my $cnt = 0;
my $a = 1;
while ($a < $n) {
    $a *= $k;
    $cnt++;
}
my $ret = $a == $n ? $cnt + 1 : $cnt;
say $ret;

Measured memory_bytes: 768
#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)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

ll dp[404][404];
ll a[401],sum[404];
int main(){
    int n;
    cin>>n;
    rep(i,n) cin>>a[i];
    rep(i,n) sum[i+1]=sum[i]+a[i];
    memset(dp,0x3f,sizeof(dp));
    rep(i,n) dp[i][i]=0;
    rep(i,n)for(int j=i-1;j>=0;--j){
        FOR(k,j,i){
            dp[j][i]=min(dp[j][i],dp[j][k]+sum[i+1]-sum[j]+dp[k+1][i]);
        }
    }
    cout<<dp[0][n-1]<<endl;
    return 0;
}


Measured memory_bytes: 1536
n,m=map(int,input().split())
H=list(map(int,input().split()))
x=[1]*n
for i in range(m):
    a,b=map(int,input().split())
    if H[a-1]>H[b-1]:
        x[b-1]=0
    elif H[a-1]==H[b-1]:
        x[a-1]=0
        x[b-1]=0
    else:
        x[a-1]=0

print(sum(x))

Measured memory_bytes: 19924
num=int(input())
cardList=[input().split(" ")for i in range(num)]
pattern=["S","H","C","D"]
notOwned=[]
for i in range(4):
    for j in range(1,14):
        if not([pattern[i],str(j)] in cardList):
            notOwned.append(pattern[i]+" "+str(j))
for i in notOwned:
    print(i)


Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> VI;
typedef vector<VI> VVI;
typedef pair<ll, ll> P;
#define FOR(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const ll INF = numeric_limits<ll>::max();
int main()
{
    int n, k; cin >> n >> k;
    VI p(n); rep(i, n) cin >> p[i];
    ll s = 0;
    ll ans = 0;
    rep(i, k) {
        s += p[i];
    }
    ans = s;
    rep(i, n-k) {
        s -= p[i];
        s += p[k+i];
        ans = max(ans, s);
    };
    double ad = (double)((ans + k)*0.5);
    printf("%f", ad);
    return 0;
}

Measured memory_bytes: 4732
#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)
#define ALL(a)     (a).begin(),(a).end()
#define RALL(a)     (a).rbegin(),(a).rend()
#define PRINT(a)   cout << (a) << endl

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second

#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

using ll = long long int;
using P = pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;

template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

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

const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;

int main(){
  int n,k;
  cin >> n >> k;
  vi a(n);
  REP(i,n)cin >> a[i];

  REP(i,n-k){
    cout << (a[i] < a[i+k] ? "Yes" : "No") << endl;
  }
}



Measured memory_bytes: 4000
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++ )
#define dump(x) cerr << #x << " = " << (x) << endl;
#define int long long

int gcd(int x, int y) {
    if(x < y) return gcd(y, x);
    else if (y == 0) return x;
    else return gcd(y, x % y);
}

int a(int N) {
    return ( N - 1 ) * 3;
}

signed main(void){

    int N; cin >> N;
    int X; cin >> X;
    X = min(X, N - X);

    cout << a(N / gcd(N, X)) * gcd(N, X) << endl;

    return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
typedef long long ll;


int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n){
        cin >> a[i];
    }
    int maxbit = log(*max_element(a.begin(), a.end())) / log(2) + 1; //sqrt(4) = 2 4 = 100 3bits
    maxbit = 60;
    ll ans = 0;
    rep(i, maxbit){
        ll bits[2] = {};
        rep(j, n){
            if(a[j] & (1LL << i)){ //i番目のbitが1
                bits[1]++;
            }else{
                bits[0]++;
            }
        }
        //ans = (ans % MOD + (1LL * (bits[1] * bits[0]) % MOD * ((1LL << i) % MOD)) % MOD) % MOD;
        //ans +=((1LL*bits[0]*bits[1])%MOD*(1LL << i)%MOD) % MOD;
        ans = (ans%MOD+(1LL*(bits[0]*bits[1])%MOD*((1LL<<i)%MOD))%MOD)%MOD;
        //ans %= MOD;
        //cout << i+1 << ":" << bits[0] << " " << bits[1] <<  endl;
    }
    cout << ans%MOD << endl;
}


Measured memory_bytes: 2560
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <vector>
#include <stdio.h>
#include <fstream>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <algorithm>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <bits/stdc++.h>

#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mp make_pair
#define inf 1000000007
#define mod 1000000007
#define pii pair <int, int>
#define all(x) x.begin(), x.end()
#define FOR(i, x, y) for (int i = x; i <= y; i++)
//#define tr(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

//using namespace __gnu_pbds;

using namespace std;

//template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

string s;

int main()
{
	cin >> s;
	FOR (i, 0, s.length()-1)  {
		if (s[i]==',') cout << " ";
		else
			cout << s[i];
	}
}


Measured memory_bytes: 384
#include<iostream>
    #include<string>
    #include <cmath>
    #include <algorithm>
    #include <vector>
    #include <cstdint>
    #include <map>
    #define MOD 1000000007
    using namespace std;
    typedef long long ll;
     
    int main(){
     
    int a,b;
    cin >> a >> b;
     
    int ans = b/100 - a/100 - 1;
     
    if(a/10000 + (a/1000 % 10)*10 >= a%100) ans++;
    if(b/10000 + (b/1000 % 10)*10 <= b%100) ans++;
     
    cout << max(ans,0) << endl;
     
    return 0;
    }

Measured memory_bytes: 256
#include<stdio.h>
char p[101000];
int n, K, s;
int main(){
    int i;
    scanf("%s",p);
    scanf("%d",&K);
    for(i=0;p[i];i++);
    n=i;
    if(K>n*25){
        s = 0;
        for(i=0;i<n;i++){
            s += ('a'-p[i]+26)%26;
        }
        for(i=0;i<n;i++)p[i]='a';
        p[n-1] += (K-s%26 + 26)%26;
        printf("%s\n",p);
        return 0;
    }
    for(i=0;i<n;i++){
        if(p[i]!='a' && K >= ('a'-p[i]+26)%26){
            K -= ('a'-p[i]+26)%26;
            p[i]='a';
        }
    }
    p[n-1] = (p[n-1]-'a'+K)%26 + 'a';
    printf("%s\n",p);
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	int x,a;
	cin>>x>>a;
	cout<<(x<a?0:10)<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
 
int main() {
  for(int tci = 0;; tci++) {
    int N,M; scanf("%d%d", &N, &M); if(!N) break;
    pair<int,int> *pd = new pair<int,int>[N];
    int ept = 0;
    for(int i = 0; i < N; i++) {
      scanf("%d%d", &pd[i].second, &pd[i].first);
      ept += pd[i].second * pd[i].first;
    }
    sort(pd, pd+N);
    reverse(pd, pd+N);
    int x = M;
    for(int i = 0; i < N && x > 0; i++) {
      ept -= min(pd[i].second, x) * pd[i].first;
      x -= pd[i].second;
    }
    printf("%d\n", ept);
  }
  return 0;
}

Measured memory_bytes: 3440
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
using namespace std;
int n;
string s;
/*
map<int,int> dp[444][2];
int solve(int l,int jf,int bit){ 
  if(dp[l][jf].find(bit) != dp[l][jf].end()) return dp[l][jf][bit];
  if(l == (int)s.size()) return 1;

  int res = 0;
  if(s[l] == '?'){
    res += solve(l+1,1,(bit<<1) & ((1<<n)-1)); // J
    res += solve(l+1,0,((bit<<1) & ((1<<n)-1)) | ((jf)?1:0)); //O
    if(!(bit & 1<<(n-2)) || !((l+1)%n)) res += solve(l+1,0,(bit<<1) & ((1<<n)-1)); //I
  }else if(s[l] == 'J'){
    res += solve(l+1,1,(bit<<1) & ((1<<n)-1)); // J
  }else if(s[l] == 'O'){
    res += solve(l+1,0,((bit<<1) & ((1<<n)-1)) | ((jf)?1:0)); //O
  }else if(s[l] == 'I' && (!(bit & 1<<(n-2)) || !((l+1)%n))){
    res += solve(l+1,0,(bit<<1) & ((1<<n)-1)); //I
  }
  return dp[l][jf][bit] = res % 100000;
}
*/
int num[1<<22];
vector<int> nm;
int a;
void mk_num(int i,int f){
  if(i > 20){
    num[a] = (int)nm.size();
    nm.push_back(a);
    return;
  }
  a <<= 1;
  mk_num(i+1,0);
  if(!f){
    a |= 1;
    mk_num(i+1,1);
  }
  a >>= 1;
  return;
}

int dp[2][33333][2];
int main(void){
  int m;
  cin >> m >> n;
  for(int i = 0; i < m; i++){
    string ss;
    cin >> ss;
    s += ss;
  }
  mk_num(0,0);
  int M = 1;
  for(int i = 0; i < (int)s.size(); i++){
    if(s[i] == '?'){
      M *= 3;
      M %= 100000;
    }
  }
  dp[0][0][0] = 1;
  for(int i = 0; i < (int)s.size(); i++){
    int now = i%2;
    int next = (i+1)%2;
    memset(dp[next],0,sizeof(dp[next]));
    for(int j = 0; j < (int)nm.size(); j++){
      for(int k = 0; k < 2; k++){
	dp[now][j][k] %= 100000;
	if(s[i] == '?' || s[i] == 'J') dp[next][num[(nm[j]<<1) & ((1<<n)-1)]][1] += dp[now][j][k];
	if(s[i] == '?' || s[i] == 'O') dp[next][num[(nm[j]<<1) & ((1<<n)-1) | ((k)?1:0)]][0] += dp[now][j][k]; 
	if((s[i] == '?' || s[i] == 'I') && (!(nm[j] & 1<<(n-2)) || !((i+1)%n)))
	  dp[next][num[(nm[j]<<1) & ((1<<n)-1)]][0] += dp[now][j][k]; 
      }
    }
  }
  int res = 0;
  for(int j = 0; j < (int)nm.size(); j++){
    for(int k = 0; k < 2; k++){
      res += dp[(int)s.size() % 2][j][k];
      res %= 100000;
    }
  }
  cout << (M - res + 100000)%100000 << endl;
  //cout << M - solve(0,0,0) << endl;
}

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

using namespace std;

const int maxn = 100005;

int n, ans, h[maxn], f[maxn];

int main (void)
{
	scanf("%d", &n);
	for(register int i=1; i<=n; ++i)
		scanf("%d", &h[i]);
	for(register int i=2; i<=n; ++i)
	{
		if(h[i] <= h[i-1]) f[i] = f[i-1] + 1;
		else f[i] = 0;
		ans = max(ans, f[i]);
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(){
	
	string s;
	cin >> s;
	
	
	bool isBad = false;
	rep(i,s.size()-1){
		if(s[i] == s[i+1]){
			isBad = true;
			break;
		}
	}
	
	if(isBad) cout << "Bad" << endl;
	else cout << "Good" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                           \
  cerr << __LINE__ << ": " << #x << " = {";        \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
    cerr << ((hoge) ? "," : "") << x[hoge];        \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<string> ans;
  string s;
  function<void(int, int)> rec = [&](int i, int c) {
    if (i == N) {
      ans.push_back(s);
      return;
    }
    for (int j = 0; j < c; j++) {
      s += 'a' + j;
      rec(i + 1, c);
      s.pop_back();
    }
    s += 'a' + c;
    rec(i + 1, c + 1);
    s.pop_back();
  };
  rec(0, 0);
  sort(ans.begin(), ans.end());
  for (auto a : ans) cout << a << '\n';
  return 0;
}


Measured memory_bytes: 7404
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) ((x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
const double PI = acos(-1);
const int mod = 1e9+7;
const long long INF = (1LL << 60);
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(ll a, ll b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmax(T &a, const T &b){ if(a < b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(a > b){ a=b; return 1; } return 0; }



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

  ll a, b;
  cin >> a >> b;

  if(a == b){
    cout << "Draw" << endl;
  }else if(a > b){
    if(b == 1) cout << "Bob" << endl;
    else cout << "Alice" << endl;
  }else{
    if(a == 1) cout << "Alice" << endl;
    else cout << "Bob" << endl;
  }

  return 0;
}

Measured memory_bytes: 3588
N = int(input())
l = [0]*N
count_1 = 0
count_2 = 0
count_3 = 0
count_4 = 0
for i in range(N):
  l[i] = input()
  if l[i] == 'AC':
    count_1 += 1
  if l[i] == 'WA':
    count_2 += 1
  if l[i] == 'TLE':
    count_3 += 1
  if l[i] == 'RE':
    count_4 += 1
print('AC','x',count_1)
print('WA','x',count_2)
print('TLE','x',count_3)
print('RE','x',count_4)
  

Measured memory_bytes: 16176
#include <cstdio>
typedef long long ll;

void max(ll &a, ll b) {if (a < b) a = b;}
int main()
{
	ll a, b, c, d;
	scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
	ll ans = -(1ll<<62);
	max(ans, a*c);
	max(ans, a*d);
	max(ans, b*c);
	max(ans, b*d);
	printf("%lld\n", ans);
}


Measured memory_bytes: 1732
#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 x, h, n, m, l;
    cin >> x >> h >> n >> m >> l;
    if ((n + l) <= x && (n - l) >= 0)
    {
        if ((m + l) <= h && (m - l) >= 0)
            cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3108
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	ans := 0
	for i := 1; i <= N; i++ {
		if i%10 == 0 {
			continue
		}
		h, t := f(i)
		if h == t {
			ans++
		}
		k := 10
		for target := t*k + h; target <= N; target = t*k + h {
			rest := len(strconv.Itoa(target)) - 2
			for i := 1; i <= rest; i++ {
				target += 9 * pow(10, i)
			}
			if target <= N {
				ans += count(target)
			} else {
				mx := N
				for mx%10 != h {
					mx--
				}
				ans += count(mx)
			}
			k *= 10
		}
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}

func count(n int) int {
	str := strconv.Itoa(n)
	mid := str[1 : len(str)-1]
	res, _ := strconv.Atoi(mid)
	return res + 1
}

func f(n int) (int, int) {
	if n < 10 {
		return n, n
	}
	tail := n % 10
	var head int
	n /= 10
	for {
		rest := n % 10
		n /= 10
		if n == 0 {
			head = rest
			break
		}
	}
	return head, tail
}


Measured memory_bytes: 5504
import Data.List

count :: [Int] -> Int
count [] = 0
count (x:[]) = 0
count (x:y:[]) = 0
count (x:y:z:ll) = count (y:z:ll) + if x < y && y < z || x > y && y > z then 1 else 0

main = do
  n <- readLn :: IO Int
  xs <- map read . words <$> getLine :: IO [Int]
  putStrLn . show $ count xs


Measured memory_bytes: 508
#include <iostream>
#include <fstream>
#include <sstream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>

//#define DEBUG 1

#define int long long
#define for0(i,n) for (int i=0; i<n; i++)
#define iter(c) for(auto it=c.begin(); it!=c.end(); it++)
#define iter2(c) for(auto it2=c.begin(); it2!=c.end(); it2++)
#define pb push_back
#define ms(a,z) memset(a,z,sizeof(a));
#define mp make_pair
#define X first
#define Y second
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define all(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define pmod(x,m) (((x)%(m)+m)%m)
#ifdef int
#define read(x) scanf("%lld",&x);
#else
#define read(x) scanf("%d",&x);
#endif

#ifdef DEBUG
#define nl cout<<"\n";
#define pr(x) cout<<(x)<<" ";
#define prl(x) cout<<#x " = "<<x<<endl;
#define prp(x) cout<<"("<<(x).first<<" "<<(x).second<<") ";
#define printv(v) {for(int _=0; _<sz(v); _++) cout<<v[_]<<" "; cout<<"\n";}
#define printa(a,s) {for (int _=0; _<s; _++) cout<<a[_]<<" "; cout<<"\n";}
#define print2D(a,m,n) {for (int _=0; _<m; _++) {for (int __=0; __<n; __++) cout<<a[_][__]<<" "; cout<<"\n";} cout<<"\n";}
#define debug cout<<"ok at line "<<__LINE__<<endl;
#else
#define nl
#define pr(x)
#define prl(x)
#define prp(x)
#define printv(v)
#define printa(a,s)
#define print2D(a,m,n)
#define debug
#endif

using namespace std;

typedef long long ll;

const int INF = 2147483647;
const long long INFL = 9223372036854775807LL;
const double EPSILON = 0.00000001;
const long long MOD = 1000000007;

int32_t main()
{
    #ifdef DEBUG
    freopen("A.txt","r",stdin);
    //freopen("","w",stdout);
    #endif

    int N; 
    cin >> N;
    bool found = false;
    for (int x=1; x<=3500; x++) {
        if (found) break;
        for (int y=1; y<=3500; y++) {
            int den = 4*x*y - N*(x+y);
            int num = N*x*y;
            if (den > 0 and num%den == 0) {
                int z = num/den;
                cout<<x<<" "<<y<<" "<<z<<endl;
                found = true;
                break;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b)  for(int i=(a),i##formax=(b);i< i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formin=(b);i>=i##formin;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max((x),(y))
#define mins(x,y) x=min((x),(y))
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define all(a) ((a).begin()),((a).end())
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define bit(n) (1LL<<(n))
typedef long long ll;
typedef __int128_t lll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>using P=pair<T,Y>;
template<class T,class Y>ostream& operator<<(ostream&o,P<T,Y>&p){return o<<"("<<p.fi<<","<<p.se<<")";}
template<class T>ostream& operator<<(ostream&o,V<T>&v){for(T&t:v)o<<t<<",";return o<<endl;}
template<class T>void uniq(V<T>&v){sort(all(v));v.erase(unique(all(v)), v.end());}

lll gcd(lll a,lll b,lll&x,lll&y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return(x%m+m)%m;}
ll modPow(lll a,lll n,ll m){lll p=1;for(;n;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return p;}
//V<ll>F,R;void setF(int n,int mod){F=R=V<ll>(++n);F[0]=1;FOR(i,1,n)F[i]=F[i-1]*i%mod;R[n-1]=modInv(F[n-1],mod);FORR(i,n-1,1)R[i-1]=R[i]*i%mod;}
//ll comb(int a,int b,int m){return a<b||b<0?0:F[a]*R[b]%m*R[a-b]%m;}

const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7; //998244353;
const int N = 1e5;
int n, k, b[4];
string s;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ans = 0;
  cin >> n >> k >> b[3] >> b[0] >> b[2] >> s;
  FOR(i, 0, n){
    if(i>=k && s[i]==s[i-k]){
      s[i] = '*';
    }else{
      ans += b[s[i]-'p'];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <sstream>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;

const int MAX_N = 100000;

string s;
int x, y;

int dpx[MAX_N];
int dpy[MAX_N];
int offset = MAX_N / 2;
bool init = true;

int update(int f, int *dp) {
    queue<int> q;
    for (int i = 0; i < MAX_N; ++i) {
        if (dp[i] == 1) {
            q.push(i + f);
            if (!init) q.push(i - f);
            dp[i] = 0;
        }
    }
    while (! q.empty()) {
        dp[q.front()] = 1;
        q.pop();
    }
    return 0;
}

int main() {
    cin >> s;
    cin >> x >> y;

    int c = 0;
    int oddeven = 0;
    dpx[offset] = 1;
    dpy[offset] = 1;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'F') {
            c++;
            if (i != s.size() - 1) {
                continue;
            }
        }
        if (oddeven % 2 == 0) {
            update(c, dpx);
        } else {
            update(c, dpy);
        }
        c = 0;
        oddeven++;
        init = false;
    }

    if (dpx[offset + x] == 1 && dpy[offset + y] == 1) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 384
n = int(input())
a = list(map(int, input().split()))
memo = {}
memo[n] = 0
ans = []
for i in range(n)[::-1]:
    tmp = i + 1
    tmp2 = 2 * tmp
    cnt = 0
    while tmp2 <= n:
        cnt += memo[tmp2]
        tmp2 += tmp
    if cnt % 2 == 1 and a[i] == 0:
        ans.append(tmp)
        memo[tmp] = 1
    elif cnt % 2 == 0 and a[i] == 1:
        ans.append(tmp)
        memo[tmp] = 1
    else:
        memo[tmp] = 0
print(len(ans))
print(" ".join(map(str, ans)))
        
        
        

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

using namespace std;

#define MAX 150
typedef pair<int,int> pii;

int N,T,L,B;
int arr[MAX];

double solve(){
  double dp[MAX][MAX]; //dp[ターン数][どのマスにいるか]
  memset(dp,0,sizeof(dp));
  dp[0][0] = 1;
  for(int i = 1 ; i <= T ; i++){
    for(int j = 0 ; j < N ; j++){
      for(int k = 0 ; k < 6 ; k++){
        if(dp[i-1][j] == 0) continue;
        int next = j+(k+1);
        if(next > N){
          next = next - 2*(next-N);
        }
        switch(arr[next]){
        case 0:
          dp[i][next] += dp[i-1][j]/6;
          break;
        case 1:
          dp[i+1][next] += dp[i-1][j]/6;
          break;
        case 2:
          dp[i][0] += dp[i-1][j]/6;
          break;
        }
      }
    }
  }
  double res = 0;
  for(int i = 1 ; i <= T ; i++){
    res += dp[i][N];
  }
  return res;
}

int main(){
  int in;
  while(cin >> N >> T >> L >> B, N){
    memset(arr,0,sizeof(arr));
    for(int i = 0 ; i < L ; i++){
      cin >> in;
      arr[in] = 1;
    }
    for(int i = 0 ; i < B ; i++){
      cin >> in;
      arr[in] = 2;
    }
    printf("%.8f\n",solve());
  }
  return 0;
}

Measured memory_bytes: 1368
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

using namespace std;
using ll = long long;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7

void solve() {
  ll n, x; cin >> n >> x;
  vector<ll> a(n); rep(i, n) cin >> a[i];
  sort(a);

  vector<ll> b(n);
  for (int i = 0; i < n; i++) {
    if (a[i] <= x) {
      b[i] = a[i];
      x -= a[i];
    }
  }
  if (x > 0) b[n - 1] += x;

  int ans = 0;
  rep(i, n) {
    if (a[i] == b[i]) ans++;
  }
  outl(ans);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**5+1)

N, M = map(int, input().split())
graph = {i+1:[] for i in range(N)}

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)

"""
dp[v]: ノードv(1~N)を始点とした最大長
"""
dp = [0] * (1+N)

def max_length_from(v):
    if dp[v] != 0:
        return dp[v]
    max_length = 0
    for vv in graph[v]:
        tmp = max_length_from(vv) + 1
        if tmp > max_length:
            max_length = tmp
    dp[v] = max_length
    return max_length

for v in range(1, N+1):
    max_length_from(v)

print(max(dp))


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

const int MOD = (int)1e9+7;

int main(){
	int N;
	cin >> N;
	priority_queue<double,vector<double>,greater<double>> pq;
	for(int i=0;i<N;i++){
		int v;
		cin >> v;
		pq.push(v);
	}

	for(int i=0;i<N-1;i++){
		double x=pq.top();
		pq.pop();
		double y=pq.top();
		pq.pop();
		pq.push((x+y)/2);
	}
	double ans=pq.top();
	printf("%9f\n",ans);

	return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
X=[]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a,b])
    
I=[e for i,e in X if i==1]

E=[i for i,e in X if e==n]



if set(I)&set(E)!=set():
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 45444
<?php
$n = fgets(STDIN);
$a = explode(' ', fgets(STDIN));
rsort($a);
$p = 0;
for($i = 0; $i < $n; $i++){
  if($i %2 ===0){
    $p += $a[$i];
  }else{
    $p -= $a[$i];
  }
}
echo $p;
?>

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

typedef long long ll;


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(NULL);
	
	ll k;
	cin >> k;
	ll cnt = 7;
	for (int i = 1; i <= 1e7; i++) {
		if (cnt % k == 0) {
			cout << i << '\n';
			return 0;
		}
		cnt = cnt * (ll)10 + (ll)7;
		cnt %= k;
	}
	cout << -1 << '\n';
}

Measured memory_bytes: 3164
#include <stdio.h>
#include <algorithm>
#include <map>

using namespace std;

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
	
struct Node{
	Node *l,*r,*p;
	int s,v,m;
	Node():l(NULL),r(NULL),p(NULL){}
	static int Size(Node* x){
		return x?x->s:0;
	}
	static int Mini(Node* x){
		return x?x->m:1145141919;
	}
	Node* Update(){
		s=1+Size(l)+Size(r);
		m=min({v,Mini(l),Mini(r)});
		return this;
	}
	int Pos(){
		if(p&&p->l==this) return -1;
		if(p&&p->r==this) return 1;
		return 0;
	}
	void Rotate(){
		Node *q=p,*c;
		if(Pos()==1){
			c=l;
			l=p;
			p->r=c;
		}else{
			c=r;
			r=p;
			p->l=c;
		}
		if(c) c->p=p;
		p=p->p;
		q->p=this;
		if(p&&p->l==q) p->l=this;
		if(p&&p->r==q) p->r=this;
		q->Update();
	}
	Node* Splay(){
		while(p){
			int a=Pos(),b=p->Pos();
			if(b&&a==b) p->Rotate();
			if(b&&a!=b) p->Rotate();
			Rotate();
		}
		return Update();
	}
	Node* Idx(int i){
		if(i<Size(l)) return l->Idx(i);
		else if(i>Size(l)) return r->Idx(i-Size(l)-1);
		return Splay();
	}
} d[200000];

pair<Node*,Node*> Split(Node* x,int i){
	if(i<0) return MP((Node*)NULL,x);
	x=x->Idx(i);
	Node* c=x->r;
	if(c) c->p=NULL;
	x->r=NULL;
	return MP(x->Update(),c);
}

Node* Merge(Node* a,Node* b){
	if(!a||!b) return a?a:b;
	while(a->r) a=a->r;
	b->p=a->Splay();
	a->r=b;
	return a->Update();
}

int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	Node* w=NULL;
	REP(i,n){
		scanf("%d",&d[i].v);
		w=Merge(w,d[i].Update());
	}
	REP(_,q){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(x==0){
			auto r=Split(w,z);
			auto q=Split(r.first,z-1);
			auto p=Split(q.first,y-1);
			w=Merge(Merge(p.first,q.second),Merge(p.second,r.second));
		}else if(x==1){
			auto q=Split(w,z);
			auto p=Split(q.first,y-1);
			printf("%d\n",p.second->m);
			w=Merge(Merge(p.first,p.second),q.second);
		}else{
			w=w->Idx(y);
			w->v=z;
			w->Update();
		}
	}
}

Measured memory_bytes: 10564
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int MAXN = 234567;
const LL MOD = (LL)1e9 + 7;
LL fac[MAXN], invfac[MAXN];

LL add(LL a, LL b) {
    LL sum = (a + b);
    if (sum >= MOD) sum -= MOD;
    return sum;
}

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

LL qpow(LL n, LL k) {
    LL base = n, ans = 1;
    while (k) {
        if (k & 1) ans = mul(ans, base);
        base = mul(base, base);
        k >>= 1;
    }
    return ans;
}

void init() {
    fac[0] = invfac[0] = fac[1] = invfac[1] = 1;
    for (int i = 2; i < MAXN; i++)
        fac[i] = mul(fac[i - 1], i);
    invfac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 1; i--)
        invfac[i] = mul(invfac[i + 1], i + 1);
}

LL C(int n, int m) {
    if (m > n) return 0;
    LL ans = mul(fac[n], invfac[m]);
    return mul(ans, invfac[n - m]);
}

LL H(int a, int b) {
    LL ans = fac[a + b - 1];
    ans = mul(ans, invfac[a]);
    return mul(ans, invfac[b - 1]);
}

int main() {
    init();
    int N, K;
    scanf("%d %d", &N, &K);
    LL ans = 0;
    for (int i = 0; i <= min(N - 1, K); i++) {
        LL cur_ans = C(N, i);
        LL offs = H(i, N - i);
        ans = add(ans, mul(cur_ans, offs));
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 3968
#include <iostream>
using namespace std;
int n, x, y, a[100009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (x < a[i]) x = a[i];
	}
	int e = x + 1;
	for (int i = 0; i < n; i++) {
		if (a[i] == x) continue;
		if (2 * a[i] < x && e > x - 2 * a[i]) {
			y = a[i];
			e = x - 2 * a[i];
		}
		if (2 * a[i] >= x && e > 2 * a[i] - x) {
			y = a[i];
			e = 2 * a[i] - x;
		}
	}
	cout << x << ' ' << y << "\n";
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 25, M = 1e6 + 25, oo = 1e9+7, mxmsk = 1 << 16;
const long long OO = 1e18+25;
    
#define f first
#define s second

int n, m;
int main() {
    scanf("%d%d",&n,&m);
        if(n*500 >= m)
        {
            printf("Yes\n");
            return 0;
        }
    printf("No");
    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

N = ii()

l_x = []
l_y = []
for i in range(N):
    x, y = mi()
    l_x.append([i, x])
    l_y.append([i, y])
l_x.sort(key=lambda x:x[1])
l_y.sort(key=lambda x:x[1])

path = []
for i in range(N-1):
    path.append([l_x[i][0], l_x[i+1][0], l_x[i+1][1]-l_x[i][1]])
    path.append([l_y[i][0], l_y[i+1][0], l_y[i+1][1]-l_y[i][1]])
path.sort(key=lambda x:x[2])

T = UnionFind(N)
cnt = 0
for i in range(2*N-2):
    s, t, d = path[i][0], path[i][1], path[i][2]
    if not T.same(s, t):
        T.unite(s, t)
        cnt += d

print(cnt)

Measured memory_bytes: 63688
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>
#include <cassert>
#include <bitset>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define EL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

void dfs(int n, int i, int upto, std::string s) {
	rep(j,upto+1) {
		if(i==n-1) print(s+(char)('a'+j));
		else {
			dfs(n,i+1,std::max(upto,j+1),s+(char)('a'+j));
		}
	}
}

signed main() {
	int n;
	std::cin >> n;
	dfs(n,0,0,"");
	return 0;
}


Measured memory_bytes: 1536
n=gets.chomp.to_i
v=gets.chomp.split(" ").map { |e| e.to_i }
even = []
odd = []

for i in 0..n-1 do

  if i%2 == 0
    even[i/2] = v[i]
  else
    odd[i/2] = v[i]
  end
end

even = even.sort
odd = odd.sort

half = n/2
dp_even=0
dp_odd=0
max_even = 0
max_odd = 0
indx_even = 0
indx_odd = 0
string_even = even[0]
string_odd = odd[0]

for i in 0..half-1 do
  if even[i] != even[indx_even]

    if dp_even > max_even
      string_even = even[indx_even]
      max_even = dp_even
    end
    indx_even = i
    dp_even = 0
  end


  if even[i] == even[indx_even]
    dp_even += 1
  end

end

if dp_even > max_even
  string_even = even[half-1]
  max_even = dp_even
end


for i in 0..half-1 do
  if odd[i] != odd[indx_odd]
    if dp_odd > max_odd && string_even != odd[indx_odd]
      max_odd = dp_odd
    end
    indx_odd = i
    dp_odd = 0
  end

  if odd[i] == odd[indx_odd]
    dp_odd += 1
  end
end


if dp_odd > max_odd && string_even != odd[half-1]
  max_odd = dp_odd
end

max_1 = max_even+max_odd


dp_even=0
dp_odd=0
max_even = 0
max_odd = 0
indx_even = 0
indx_odd = 0
string_even = even[0]
string_odd = odd[0]


for i in 0..half-1 do
  if odd[i] != odd[indx_odd]
    if dp_odd > max_odd
      string_odd = odd[indx_odd]
      max_odd = dp_odd
    end
    indx_odd = i
    dp_odd = 0
  end

  if odd[i] == odd[indx_odd]
    dp_odd += 1
  end
end


if dp_odd > max_odd
  max_odd = dp_odd
  string_odd = odd[half-1]
end

for i in 0..half-1 do
  if even[i] != even[indx_even]

    if dp_even > max_even && string_odd != even[indx_even]
      string_even = even[indx_even]
      max_even = dp_even
    end
    indx_even = i
    dp_even = 0
  end


  if even[i] == even[indx_even] && string_odd != even[half-1]
    dp_even += 1
  end

end

if dp_even > max_even
  string_even = even[half-1]
  max_even = dp_even
end

max2 = max_even + max_odd

max = max2 > max_1 ? max2 : max_1


puts 2*half - max


Measured memory_bytes: 10784
//Radhe Radhe
#include<bits/stdc++.h>
#define ll long long
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
using namespace std;

int main()
{
    fast_io
    ll i,j,n,k,cnt1=0;
    string s;
    cin>>s>>k;
   for(i=0;s[i];i++)
    {
        if(s[i]=='1') cnt1++;
        else break;
    }
    if(cnt1<k){
        cout<<s[cnt1]<<endl;
    }
    else
        cout<<1<<endl;
    return 0;
}





Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define fi first
#define se second
#define mk make_pair
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int main(){
  int n,m,a[100001]={};
  cin>>n>>m;
  set<pair<int,int> >s;
  while(m--){
    int p1,p2;
    cin>>p1>>p2;
    if(p1>p2)swap(p1,p2);
    a[p1]++;
    a[p2]++;
  }
  r(i,n)if(a[i]%2){cout<<"NO"<<endl;goto L;}
  cout<<"YES"<<endl;L:;
}

Measured memory_bytes: 640
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static final int BIG_NUM = 2000000000;
	public static final int MOD = 1000000007;

	public static void main(String[] args) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		final int SIZE = 105;

		Stack stack = new Stack(SIZE);
		int num_1 = 0,num_2 = 0;

		try {

			String input_str[] = br.readLine().split("\\s+");
			for(int i = 0; i < input_str.length; i++){
				switch(input_str[i]){
				case "+":

					num_2 = stack.pop_NUM();
					num_1 = stack.pop_NUM();
					stack.push_NUM(num_1+num_2);
					break;

				case "-":

					num_2 = stack.pop_NUM();
					num_1 = stack.pop_NUM();
					stack.push_NUM(num_1-num_2);
					break;

				case "*":

					num_2 = stack.pop_NUM();
					num_1 = stack.pop_NUM();
					stack.push_NUM(num_1*num_2);
					break;

				default:

					stack.push_NUM(Integer.parseInt(input_str[i]));
					break;
				}
			}

			System.out.println(stack.pop_NUM());

		} catch (IOException e) {
			// TODO 自動生成された catch ブロック
			e.printStackTrace();
		}



	}
}

class Stack{

	private int NUM[];
	private int index_NUM;

	Stack(int arg_size){
		NUM = new int[arg_size];
		index_NUM = 0;
	}
	public void push_NUM(int num){

		NUM[index_NUM++] = num;
	}
	public int pop_NUM(){
		index_NUM--;
		return NUM[index_NUM];
	}

	public boolean is_Empty(){

		return index_NUM == 0;
	}
}


Measured memory_bytes: 24668
from bisect import bisect_left as bl
from collections import deque
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
n,m = map(int,input().split())
H = set([float("INF"),-float("INF")])
V = set([float("INF"),-float("INF")])
nl = []
ml = []
for i in range(n):
    a,b,c = map(int,input().split())
    H |= set([a,b])
    V.add(c)
    nl.append([a,b,c])
for i in range(m):
    c,a,b = map(int,input().split())
    V |= set([a,b])
    H.add(c)
    ml.append([a,b,c])
def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C
H ,dx = compress(H)
V, dy = compress(V)

h = len(H)+2
w = len(V)+2
d = [[0]*3001 for i in range(3001)]
checkh = [[0]*3001 for i in range(3001)]
checkv = [[0]*3001 for i in range(3001)]

for a,b,c in nl:
    s = dx[a]
    g = dx[b]
    t = dy[c]
    
    for x in range(s,g):
        checkh[x][t] = 1

for a,b,c in ml:
    s = dy[a]
    g = dy[b]
    t = dx[c]
    
    for y in range(s,g):
        checkv[t][y] = 1


def bfs(x,y):
    ans = 0
    sx = bl(H,0)-1
    sy = bl(V,0)-1
    q = deque([])
    q.append((sx,sy))
    d[sx][sy] = 1
    while q:
        h,v = q.popleft()
        ans += (H[h+1]-H[h])*(V[v+1]-V[v])
        if h != 0 and checkv[h][v] == 0 and d[h-1][v] == 0:
            d[h-1][v] = 1
            q.append((h-1,v))
        if v != 0 and checkh[h][v] == 0 and d[h][v-1] == 0:
            d[h][v-1] = 1
            q.append((h,v-1))
        if h != len(H)-2 and checkv[h+1][v] == 0 and d[h+1][v] == 0:
            d[h+1][v] = 1
            q.append((h+1,v))
        if v != len(V)-2 and checkh[h][v+1] == 0 and d[h][v+1] == 0:
            d[h][v+1] = 1
            q.append((h,v+1))
    print("INF" if ans ==float("INF") else ans)

bfs(0,0)



Measured memory_bytes: 367712
#include <iostream>

#define SWAP(type, a, b) { type work = a; a = b; b = work; }

using namespace std;

void my_qsort(int *array, size_t size);
void qsort_rec(int *array, int begin, int end);
inline int select_pivot(const int *array, int begin, int end);

int main() {
    int num;
    int input[100000];
    int ans = 0;

    cin >> num;
    for (int i = 0; i < num; i++){
        cin >> input[i];
    }
    my_qsort(input, num);
    ans = input[(num/2)] - input[(num/2)-1];

    cout << ans << "\n";
    return 0;
}

void my_qsort(int *array, size_t size)
{
    qsort_rec(array, 0, (int)(size - 1));
}
void qsort_rec(int *array, int begin, int end)
{
    int pivot = select_pivot(array, begin, end);
    int i = begin;
    int j = end;
    
    while(1) {
        while(array[i] < pivot) { ++i; }
        while(array[j] > pivot) { --j; }
    
        if (i >= j) { break; }
        SWAP(int, array[i], array[j]);
        i++;
        j--;
    }

    if (i - begin >= 2) {
        qsort_rec(array, begin, i-1);
    }
    
    if (end - j >= 2) {
        qsort_rec(array, j + 1, end);
    }
}
inline int select_pivot(const int *array, int begin, int end)
{
    return array[(begin + end) / 2];
} 

Measured memory_bytes: 768
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
#include <queue>
#include <list>
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
const int INF = 1 << 21;
using pii = std::pair<int, int>;
#define SORT(v) std::sort(v.begin(), v.end())
int F[100][15];
int main(void) {
	int N, t, a;
	
	std::cin >> N;
	long long T, A, n = 0;
	
	T = 1;
	A = 1;
	for (int i = 0; i < N; i++) {
		std::cin >> t >> a;
		n=std::max((T+t-1)/t,(A+a-1)/a);
		
		T = n * t;
		A = n * a;
	}
	long long sum = 0;
	sum = T + A;
	std::cout << sum << std::endl;
	return 0;
}

Measured memory_bytes: 256