akhauriyash/Code-Regression huggingface dataset:
#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cmath"
#include "bitset"
#include "queue"
#include "functional"
#include "map"
#include "unordered_map"

#define lp(n) for (int i = 0; i < n; i++)
#define LP(n,i) for (int i = 0; i < n; i++)
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nya_n "(=^･ω･^=)"
typedef long long ll;
using namespace std;

int n, w, dp[100][300][101], w1, v, wi, ans;
bool dpb[100][300][101];
int main() {
	cin >> n >> w;
	cin >> w1 >> v;
	
	lp(100) {
		LP(300, j) {
			LP(101, k) {
				dpb[i][j][k] = false;
			}
		}
	}
	dp[0][0][0] = 0;
	dp[0][0][1] = v;
	dpb[0][0][0] = true;
	dpb[0][0][1] = true;
	lp(n - 1) {
		cin >> wi >> v;
		wi -= w1;
		LP(3*(i+1)+1, j) {
			LP(i+2, k) {
				if (dpb[i][j][k]) {
					if (dpb[i][j + wi][k + 1]) {
						dp[i + 1][j + wi][k + 1] = max(dp[i][j + wi][k + 1], dp[i][j][k] + v);;
					}
					else dp[i + 1][j + wi][k + 1] = dp[i][j][k] + v;
					dpb[i + 1][j + wi][k + 1] = true;
					if (!dpb[i + 1][j][k]) {
						dpb[i + 1][j][k] = true;
						dp[i + 1][j][k] = dp[i][j][k];
					}
				}
			}
		}
	}
	ans = 0;
	lp(300) {
		LP(101,j) {
			if (i + j*w1>w)
				break;
			if (dpb[n - 1][i][j])
				ans = max(ans, dp[n - 1][i][j]);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 14848
import numpy
N, K = map(int, input().split())
p = list(map(int, input().split()))

lis = list()

p = [(i + 1)/2 for i in p ]
numpy.set_printoptions(precision=16)

cumSum = numpy.cumsum(p)

cumSum2 = list(cumSum)

cumSum2.insert(0,0)

for i in range(0, N-K+1):
    lis.append(cumSum2[K+i] - cumSum2[i])

print('{:.12f}'.format(max(lis)))

Measured memory_bytes: 36776
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))

print(-sum(a))

Measured memory_bytes: 14380
#pragma GCC optimize("O3")
#include <bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
vector<bool> prime;
void make(ll num){
    prime.resize(num,true);
    prime[0]=false;
    for(ll i=0;i*i<num;i++){
        if(prime[i]){
            for(ll j=2;(i+1)*j<=num;j++){
                prime[(i+1)*j-1]=false;
            }
        }
    }
}
bool used[1000005];
int main(){
    make(1000100);
    V<ll> d;
    for(int i=0;i<1000;i++){
        if(prime[i])d.emplace_back(i+1);
    }
    int n;
    cin>>n;
    V<ll> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    ll g=a[0];
    for(int i=1;i<n;i++){
        g=GCD(g,a[i]);
    }
    bool ok=true;
    reverse(all(a));
  //  bool sp=true;
    for(int i=0;i<n;i++){
       // if(a[i]!=1)sp=false;
        for(int j=0;j<d.size();j++){
            if(a[i]%d[j]==0){
                while(a[i]%d[j]==0)a[i]/=d[j];
                if(used[d[j]]){
                    ok=false;
                }
                else{
                    used[d[j]]=true;
                }
            }
        }
        if(prime[a[i]-1]){
           if(used[a[i]]){
                    ok=false;
                }
                else{
                    used[a[i]]=true;
                }
        }
        if(!ok)break;
    }
    if(ok){
        cout<<"pairwise coprime"<<"\n";
    }
    else {
        cout<<(g==1?"setwise coprime":"not coprime")<<"\n";
    }
}


Measured memory_bytes: 11068
n, a, b, c = map(int, input().split())
abc = [a, b, c]
l = [int(input()) for _ in range(n)]
ans = 10**9
now = [[0, 0] for _ in range(4)]

def dfs(depth, l):
    global ans, now
    if depth == n:
        tmp = 0
        for i in range(3):
            if now[i][1] == 0:
                return
            tmp += abs(abc[i] - now[i][0]) + 10 * (now[i][1] - 1)
        ans = min(ans, tmp)
        return
    for i in range(4):
        now[i][0] += l[depth]
        now[i][1] += 1
        dfs(depth + 1, l)
        now[i][0] -= l[depth]
        now[i][1] -= 1

dfs(0, l)
print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char arr[] = str.toCharArray();
        if (arr.length % 2 != 0){
            System.out.println("No");
            return;
        }
        for (int i = 0; i < arr.length - 1; i++){
            if (arr[i] != 'h' && arr[i] != 'i') {
                System.out.println("No");
                return;
            }
            if (arr[i] == 'h' && arr[i + 1] != 'i') {
                System.out.println("No");
                return;
            }else if (arr[i] == 'i' && arr[i + 1] != 'h') {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
        return ;
    }
}


Measured memory_bytes: 23124
#include <iostream>
#include <cmath>

using namespace std;

int main() {

  int n, d;
  cin>>n>>d;
  int x[n], y[n];
  int ans = 0;
  for(int i = 0; i<n; i++){
    cin>>x[i]>>y[i];
    if(sqrt(pow(x[i],2) + pow(y[i], 2)) <= d) ans++;
  }
  
  cout<<ans;
  return 0;
} 
 
  

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

#define IOS		    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ld 		    long double
#define ll 		    long long int
#define ull 	   	unsigned long long int
#define pb		    push_back
#define mp		    make_pair
#define F		    first
#define S		    second
#define lb		    lower_bound
#define ub		    upper_bound
#define deb(x)      cout<<"#x "<<x<<"\n";
#define trace(x,y)  cout<<"#x "<<x<<" #y "<<y<<"\n";


const int mod = 1e9;
bool sortByFirst(const pair<int,int>& a, const pair<int,int>& b){
    return a.F < b.F;
}
int main(){
    IOS;
    ll x;
    cin >> x;
    ld am=100;
    ll bal = 100;
    int cnt = 0;
    while(bal < x){
      am *= 1.01;
      bal = (ll)am;
      am = (ld)bal;
      cnt++;
    }
    cout<<cnt<<"\n";
return 0;
}

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


namespace Library
{
    public class Miscelleneous
    {
        public static void print(object j){Console.WriteLine(j.ToString());}
        public static void print(string s){Console.WriteLine(s);}
        
        
        public static void Main(){
            int[] I;
            string[] ss;
            string s;
            int Rect=0,Equi=0;
            while(true){
                s=Console.ReadLine();
                if(string.IsNullOrEmpty(s))break;
                ss=s.Split(',');
                I=new int[ss.Length];
                for(int i=0;i<ss.Length;i++)
                    I[i]=int.Parse(ss[i]);
                
                if(I[2]*I[2]-I[0]*I[0]==I[1]*I[1])Rect++;
                if(I[0]==I[1])Equi++;
            }
            print(Rect);
            print(Equi);
        }
    }
}

Measured memory_bytes: 9108
while True:
    m,f,r = map(int, raw_input().split())
    s = m + f
    if m == -1 and f == -1 and r == -1: break
    elif m == -1 or f == -1 or s < 30: g=5
    elif 30 <= s and s < 50:
        if r >= 50: g=2
        else: g=3
    elif 50 <= s and s < 65: g=2
    elif 65 <= s and s < 80: g=1
    else: g=0
    print 'ABCDEF'[g]

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

public class BinarySearch{
	public static void Main()
	{
		Console.ReadLine();
		var sList = ReadLineAndToIntList();
		Console.ReadLine();
		var tList = ReadLineAndToIntList();
	
		int count = 0;
	
		foreach (var t in tList)
		{
			if(sList.BinarySearch(t) > -1) count++;
		}
		
		Console.WriteLine(count);
	}
	
	//??????????????????????????????
	public static List<int> ReadLineAndToIntList()
	{
		return Console.ReadLine().Split().Select (c => int.Parse(c)).ToList();
	}
}

Measured memory_bytes: 15112
#include <bits/stdc++.h>
#define repd(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

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

    int s1, s2;
    s1 = S / 100;
    s2 = S % 100;

    if ((s1 > 0 && s1 <= 12) && (s2 <= 12 && s2 > 0))
    {
        cout << "AMBIGUOUS" << endl;
    }
    else if (s1 <= 99 && (s2 > 0 && s2 <= 12))
    {
        cout << "YYMM" << endl;
    }
    else if ((s1 > 0 && s1 <= 12) && s2 <= 99)
    {
        cout << "MMYY" << endl;
    }
    else
    {
        cout << "NA" << endl;
    }

    return 0;
}


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

class Main{
	public static void main(String[] args) {

		BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in));
		String str="";
		double hayasa=0;
		int kai=0;
		double byou=0;
		double takasa=0;
		boolean takai=false;
		for(int kk=0; kk<2;) {
			try {
				str=bfr.readLine();
				if(str.equals("")) {
					System.exit(0);
				}
				
				else if(str=="") {
					System.exit(0);
				}
				hayasa=Double.parseDouble(str);
				byou=hayasa/9.8;
				takasa=4.9*byou*byou;
				for(int i=1; i>0; i++) {
					if(takai==false && takasa+5<=i*5) {
						kai=i;
						break;
					}
				}
				System.out.println(kai);
			}catch(IOException e) {

			}catch(NullPointerException e) {
			    System.exit(0);
			}
		}
	}
}


Measured memory_bytes: 24396
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>

// MAX LL 9,223,372,036,854,775,807 = 2^63 -1 ~ 9* 1e18
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, s, n) for(int i=s; i<n; i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;

long long factorial(long long i){ // 階乗
 if(i > 0)
   return i * factorial(i-1);
 else
   return 1;
}
//// a^n mod
long long modpow(long long a, long long n, long long mod) {
 long long res = 1;
 while (n>0) {
   if(n & 1) res = res * a % mod;
   a = a * a % mod;
   n >>= 1;
 }
 return res;
}

//// a^(-1) mod
long long modinv(long long a, long long mod) {
 return modpow(a, mod-2, mod);
}

int main() {
  const ll MOD = (ll)(1e9) + 7;
  ll n, a, b;
  cin >> n >> a >> b;

  ll ans = 1;
  // ans = 2^n;

  ll tmp_n = n;
  ll d = 2;
  while (tmp_n>0)
  {
    if(tmp_n%2==1) {
      ans *= d;
      ans %= MOD;
    }
    tmp_n >>= 1;
    d = d * d;
    d %= MOD;
    //cout << ans << endl;
  }
  ans--; // 0本の花束はNG;

  // a;
  ll ng_a = 1;
  rep(i, a) {
    ng_a *= (n - i);
    ng_a %= MOD;
  }
  rep(i, a) {
    ng_a *= modinv(i + 1, MOD);
    ng_a %= MOD;
  }

  // b;
  ll ng_b = 1;
  rep(i, b) {
    ng_b *= (n - i);
    ng_b %= MOD;
  }
  rep(i, b) {
    ng_b *= modinv(i + 1, MOD);
    ng_b %= MOD;
  }

  ans = ans + MOD - ng_a;
  ans %= MOD;
  ans = ans + MOD - ng_b;
  ans %= MOD;

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.first << ' ' << p.second << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}
#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define MOD 1000000007
#define zeros(x) x&(x-1)^x
#define fi first
#define se second
#define NMAX 405

long long dp[22][(1 << 21)  + 5], ok[22][22];
vector<int> st[22];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int n;
	cin >> n;

	for(int i = 0;  i < n; ++i)
		for(int j = 0; j < n; ++j){
			cin >> ok[i][j];

			if(ok[i][j])
				st[i].push_back(j);
		}

	for(int j = 0; j < n; ++j)
		if(ok[0][j])
			dp[0][(1 << j)] = 1;
	for(int i = 1; i < n; ++i)
		for(int msk = 0; msk < (1 << n); ++msk)
			if(dp[i - 1][msk])
				for(auto j: st[i])
					if(!((1 << j) & msk))
						dp[i][msk | (1 << j)] = (dp[i][msk | (1 << j)] + dp[i - 1][msk]) % MOD;
	cout << dp[n - 1][(1 << n) - 1] << '\n';
	return 0;
}

Measured memory_bytes: 309504
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, Dep[110], chk, MM[110];
int rr = 1e9, ww[110][110];
long long res = -1;
vector<int>E[110];
void DFS(int a, int pp) {
	for (auto &x : E[a]) {
		if (x == pp)continue;
		Dep[x] = Dep[a] + 1;
		DFS(x, a);
	}
}
void Do1(int a, int r) {
	if (rr < r)return;
	if (rr > r) {
		rr = r, res = -1;
	}
	Dep[a] = 0;
	DFS(a, 0);
	int i;
	for (i = 0; i <= n; i++)MM[i] = 0;
	for (i = 1; i <= n; i++) {
		MM[Dep[i]] = max(MM[Dep[i]], (int)E[i].size());
	}
	long long c = 1;
	for (i = n; i >= 0; i--) {
		if (!MM[i])continue;
		if (i)MM[i]--;
		if(MM[i])c = c*MM[i];
	}
	if (res == -1 || res > c)res = c;
}
void Del(int a, int b) {
	int i;
	for (i = 0; i < E[a].size(); i++) {
		if (E[a][i] == b) {
			swap(E[a][i], E[a][E[a].size() - 1]);
			E[a].pop_back();
			break;
		}
	}
}
void Add(int a, int b) {
	E[a].push_back(b);
	E[b].push_back(a);
}
void Do2(int a, int b, int r) {
	Del(a, b);
	Del(b, a);
	n++;
	chk = 1;
	Add(a, n);
	Add(b, n);
	Do1(n, r);
	Del(a, n);
	Del(n, a);
	Del(b, n);
	Del(n, b);
	n--;
	Add(a, b);
}
int main() {
	int i, a, b, j;
	scanf("%d", &n);
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		ww[a][b] = ww[b][a] = 1;
		E[a].push_back(b);
		E[b].push_back(a);
	}
	for (i = 1; i <= n; i++) {
		Dep[i] = 0;
		DFS(i, 0);
		int Mx = 0;
		for (j = 1; j <= n; j++) {
			Mx = max(Mx, Dep[j]);
		}
		Do1(i, Mx + 1);
	}
	for (i = 1; i <= n; i++) {
		 for(int x=1;x<=n;x++) {
			 if (!ww[i][x])continue;
			for (j = 1; j <= n; j++)Dep[j] = 0;
			DFS(i, x);
			int M1 = 0, M2 = 0;
			for (j = 1; j <= n; j++)M1 = max(M1, Dep[j]);
			for (j = 1; j <= n; j++)Dep[j] = 0;
			DFS(x, i);
			for (j = 1; j <= n; j++)M2 = max(M2, Dep[j]);
			Do2(i, x, max(M1, M2) + 1);
		}
	}
	printf("%d %lld\n", rr, res);
}

Measured memory_bytes: 256
S = input()
if S == 'SSS':
  print(0)
elif S == 'SSR':
  print(1)
elif S == 'SRS':
  print(1)
elif S == 'SRR':
  print(2)
elif S == 'RSS':
  print(1)
elif S == 'RSR':
  print(1)
elif S == 'RRS':
  print(2)
else:
  print(3)

  

Measured memory_bytes: 9036
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <random>
#include <cassert>
#include <numeric>
#define ll long long int
#define LL unsigned long long
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
using namespace std;

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};
const int MOD = 1000000007;



int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    int ans = 0;
    rep(i,n){
        if(a[a[i]-1] == i+1) ans++;
    }
    cout << ans / 2 << endl;
}


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

vector<int> h;
int n, r;
int get_h(int x) {
    return h[x + 23];
}

void set_h(int x, int k) {
    h[x + 23] = k;
} 

double get_t(int x, int k) {
    if (abs(x) >= r) return 100; 
    return k - sqrt(r * r - x * x) + r;
}

int main(){
    while(1) {
        cin >> r >> n;
        if (r == 0) break;
        h = vector<int>(50, 0);
        REP(i, n) {
            int li, ri, hi;
            cin >> li >> ri >> hi;
            for (int j = li; j < ri; ++j) {
                set_h(j, max(get_h(j), hi));
            }
        }
        double ans = 100;
        for (int x = -20; x <= 20; ++x) {
            ans = min(ans, get_t(x, get_h(x)));
            ans = min(ans, get_t(x + 1, get_h(x)));
        }
        cout << fixed << setprecision(10) << ans << endl;
    }
    return 0;
}


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

int main(){
	int N;
	cin>>N;
	int preT=0,preX=0,preY=0;
	string ans="Yes";
	for(int i=0;i<N;i++){
		int T,X,Y;
		cin>>T>>X>>Y;
		int dx=abs(X-preX);
		int dy=abs(Y-preY);
		if(T-preT<dx+dy){
			ans="No";
		}else{
			if((T-preT)%2!=(dx+dy)%2){
				ans="No";
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

int n, arr[100100], k = 2;
bool vis[100100];
int dp[100100];

int func( int pos ) {
  if ( pos == n ) return 0;
  if (vis[pos]) return dp[pos];
  vis[pos] = 1;
  int res = 1e9;
  for (int i = 1; i <= k; ++i) {
    if ( pos + i <= n ) 
      res = min(res, func(pos + i) + abs(arr[pos] - arr[pos + i]));
  }
  return dp[pos] = res;
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> arr[i];
  cout << func(1) << endl;
  return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long maximum=numeric_limits<int>:: max();
long long minimum=numeric_limits<int>:: min();
ll a,b,c,d;
map<ll,ll> memo;
long long solve(ll n){
    if(n==0)return 0;
    if(n==1)return d;
    if(memo.count(n))return memo[n];
    ll pay = 1e18;
    if(n<pay/d)pay=n*d;
    ll a1=((n/2)*2);
    ll a2=((n+1)/2)*2;
    ll b1=((n/3)*3);
    ll b2=((n+2)/3)*3;
    ll c1=(n/5)*5;
    ll c2=((n+4)/5)*5;
    pay=min(pay,(llabs(n-a1))*d + a + solve(a1/2));
    pay=min(pay,(llabs(n-a2))*d + a + solve(a2/2));
    pay=min(pay,(llabs(n-b1))*d + b + solve(b1/3));
    pay=min(pay,(llabs(n-b2))*d + b + solve(b2/3));
    pay=min(pay,(llabs(n-c1))*d + c + solve(c1/5));
    pay=min(pay,(llabs(n-c2))*d + c + solve(c2/5));
    memo[n]=pay;
    return pay;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll t;cin>>t;
    while(t--){
        memo.clear();
        ll n;cin>>n>>a>>b>>c>>d;
        cout<<solve(n)<<"\n";
    }
    return 0;
}

Measured memory_bytes: 4404
def gcd(a, b):
    global queue
    r = a % b
    if r:
        d = a // b
        sb = queue.pop()
        sa = queue.pop()
        sc = tuple(map(lambda x, y: x - d * y, sa, sb))
        queue.append(sb)
        queue.append(sc)
        return gcd(b, r)
    else:
        return b


a, b = map(int, input().split())
queue = [(1, 0, a), (0, 1, b)]
g = gcd(a, b)
x, y, r = queue.pop()
print(x, y)

Measured memory_bytes: 7768
H,W = map(int,input().split())
mod = 10**9+7
M = []
for i in range(H):
    M.append(input())
dp = [[0 for i in range(W)] for j in range(H)]
dp[0][0] = 1
for i in range(H):
    for j in range(W):
        if i != H-1 and M[i+1][j] == '.':
            dp[i+1][j] += dp[i][j] % mod
        if j != W-1 and M[i][j+1] == '.':
            dp[i][j+1] += dp[i][j] % mod
print(dp[-1][-1]%mod)

Measured memory_bytes: 55644
n=int(input())
s=[int(input()) for i in range(n)]
memo=[[-1]*20000 for i in range(200)]
def dp(score, i):
    if i==n:
        if score%10==0:
            memo[i][score]=0
            return 0
        else:
            memo[i][score]=score
            return score
    if memo[i][score]>=0:
        return memo[i][score]
    memo[i][score]=max(dp(score+s[i-1], i+1), dp(score, i+1))
    return memo[i][score]
print(dp(0,0))

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

int main(){
    string s;
    cin >> s;
    int ans;
    if (s == "RRR") ans = 3;
    else if (s == "RRS") ans = 2;
    else if (s == "SRR") ans = 2;
    else if (s == "SSS") ans = 0;
    else ans = 1;

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


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <cstdint>
#include <iomanip>
#include <set>
using ll = long long;
#define fast_io(); std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0);

int main(){
    std::string s; std::cin >> s;

    std::vector<bool> v(26,0);
    for(int i=0; i<s.size(); i++){
        v[s[i]-'a'] = 1;
    }

    for(int i=0; i<26; i++){
        if(v[i]==0){
            std::cout << static_cast<char>('a'+i) << "\n";
            return 0;
        }
    }
    std::cout << "None" << "\n";
    return 0;
}

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

using namespace std;

typedef long long ll;

#define for(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)    for(i, 0, n)
#define sz(x)        ((int)(x).size())
#define inf          1<<25

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; }

//typedef vector<int> vi;
//typedef vector<long long> vl;
//typedef vector<double> vd;
//typedef pair<int,int> pii;
//typedef pair<long,long> pll;
//typedef long long ll;

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

int main() {
    int N, A;
    cin >> N >> A;
    
    N %= 500;
    cout << (N <= A ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;
int main(void){
	string s;
	cin >> s;
	string res;
	for(char c : s){
		if(c!='B')res.push_back(c);
		else if(res.size()>0)res.pop_back();
	}
	cout << res << endl;
}

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

int main(){
  int num, menu;
  cin >> num >> menu;
  vector<int> candidate(menu);
  for(int i = 0;i < num;++i){
    int num_menu;
    cin >> num_menu;
    for(int j = 0; j < num_menu;j++){
      int like_menu;
      cin >> like_menu;
      like_menu--;
      candidate[like_menu]++;
    }
  }
  int ans = 0;
  for(int i = 0; i < menu;++i){ 
	if(candidate[i] == num){
    	ans++;
    }
  }
  cout << ans << endl;
}

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

int main() {
    int k, a, b;
    cin >> k >> a >> b;
    for(int i = a; i <= b; ++i) {
        if(i % k == 0) {
            puts("OK");
            return 0;
        }
    }
    puts("NG");
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
main(){
long long i,j,k,l,n,m;
while(cin>>n){
long long x[n];
for(i=0;i<n;i++)cin>>x[i];
j=0;k=0;
for(i=0;i<n-1;i++){
    if(x[i]>=x[i+1]) j++;
    else j=0;
    if(j>k)k=j;

}
cout<<k<<endl;
} return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main(void)
{
  int n, a[100], max, min, i;
  
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  max=a[0];min=a[0];
  for(i=1;i<n;i++){
    if(max<a[i]) max=a[i];
    else if(min>a[i]) min=a[i];
  }
  printf("%d",max-min);
  return 0;
}

Measured memory_bytes: 128
n=int(input())
ti=list(map(int,input().split()))
m=int(input())
p=[]
x=[]
for i in range(m):
  pn,xn=map(int,input().split())
  p.append(pn)
  x.append(xn)
tsum=sum(ti)
for i in range(m):
  sa=ti[p[i]-1]-x[i]
  print(tsum-sa)

Measured memory_bytes: 9192
var
	L,R,ans,tmp,M,i,j:Longint;
begin
	read(L,R);
	M:=2019;
	ans:=M;
	if L<3 then begin
		if R<673 then writeln(1)
		else writeln(0);
		exit;
	end;
	if L+2017<=R then begin
		writeln(0);
		exit;
	end;
	for i:=L to R do begin
		for j:=1 to 50 do begin
			if i+j>R then break;
			tmp:=i mod M*(i+j)mod M;
			if ans>tmp then ans:=tmp;
		end;
	end;
	writeln(ans);
end.

Measured memory_bytes: 128
#include "bits/stdc++.h"

using namespace std;

#define Rep(b, e, i) for (int i = b; i <= e; i++)
#define Repr(e, b, i) for (int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n - 1, i)
#define repr(n, i) Repr(n - 1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(v) push_back(v)
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define bitcnt(x) __builtin_popcount(x)
#define fst first
#define snd second
#define Pqaz(T) priority_queue<T, vector<T>, greater<T>>
#define Pqza(T) priority_queue<T>
#define put(x) cout << x;
#define putsp(x) cout << x << ' ';
#define putbd cout << "---------------------------------------------" << endl;
#define putln(x) cout << x << endl;
#define debug(x) cerr << #x << "=" << x << endl;
#define ENJYU std::ios::sync_with_stdio(false) std::cin.tie(0);

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef complex<double> comp;
typedef vector<int> vec;
typedef vector<ll> vecll;
typedef vector<double> vecd;
typedef vector<vec> mat;
typedef vector<vecll> matll;
typedef vector<vecd> matd;

template <class T>
ostream &operator<<(ostream &o, const vector<T> &v)
{
	o << "{";
	for (int i = 0; i < (int)v.size(); i++) o << (i > 0 ? ", " : "") << v[i];
	o << "}";
	return o;
}

const int MAX = 200020;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const ll INFL = 1e18;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//const int dx[]={-1,-1,-1,0,1,1,1,0},dy[]={-1,0,1,1,1,0,-1,-1};

//********************************template END****************************************//

vector<int> enum_prime(int N)
{
	//N = sqrt(N + 1);
	bool prime[N+1];
	memset(prime, true, sizeof(prime));
	prime[0] = prime[1] = false;

	for (int i = 2; i <= N; i++)
	{
		if (!prime[i]) continue;
		for (int j = 2; i * j <= N; j++)
		{
			prime[i * j] = false;
		}
	}

	vector<int> ps;
	rep(N, i)
	{
		if (prime[i])
			ps.pb(i);
	}

	return ps;
}

void solve()
{
	vec ps = enum_prime(123456*2);
	int N;
	while(cin >> N)
	{
		if (N == 0) break;
		cout << upper_bound(all(ps), 2*N) - upper_bound(all(ps), N) << endl;
	}
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}



Measured memory_bytes: 3428
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod


#include <bits/stdc++.h>
using namespace std;
signed main(){
  int S;
  cin>>S;
  set<int> ans;
  ans.insert(S);
  for(int i=0; i<1000001; i++){
    if(S%2==0) S /=2;
    else S = S*3 +1;
    if(ans.count(S)){
     cout<<i+2<<endl;
      return 0;
    }
    ans.insert(S);
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int d[100],f[100],n,g[100][100],time=1;

int func(int m){
    d[m]=time++;
    int i,j;
    for(i=0;i<n;i++){
        if(g[m][i]==1 && d[i]==0){
            func(i);
        }
    }
    f[m]=time++;
}

int main(void){
    int i, j, u, k, v;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d %d",&u,&k);
        for(j=0;j<k;j++){
            scanf("%d",&v);
            g[u-1][v-1]=1;
        }
    }
    func(0);
    for(i=0;i<n;i++){
        if(d[i]==0){
            func(i);
        }
    }
    for(i=0;i<n;i++){
        printf("%d %d %d\n",i+1,d[i],f[i]);
    }
    return 0;
}

Measured memory_bytes: 2736
#include <iostream>
#include <stdio.h>
using namespace std;
int main(int argc, const char * argv[]) {
    int a,b;
    char op;
    while (1) {
        cin >> a >> op >> b;
        
        if (op =='?') break;
        if (op == '+'){
            cout << a+b << endl;
        }else if (op == '-'){
            cout << a-b << endl;
            
        }else if(op == '*'){
            cout << a*b <<endl;
        }else{
            cout << int(a/b) <<endl;
        }
    }
    // insert code here...
    //std::cout << "Hello, World!\n";
    return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<sstream>
#include<ios>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<string>
#include<numeric>
#include<set>
using namespace std;

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

  vector<pair<pair<int, int>, int> > py(m);
  for(int i = 0; i < m; i++){
    cin >> py[i].first.second >> py[i].first.first;
    py[i].second = i;
  }

  stable_sort(py.begin(), py.end());

  map<int, int> cntcity;
  vector<pair<int, string> > serial(m);
  for(int i = 0; i < m; i++){
    ostringstream oss;
    cntcity[py[i].first.second]++;
    serial[i].first = py[i].second;
    oss << setw(6) << setfill('0') << py[i].first.second;
    oss << setw(6) << setfill('0') << cntcity[py[i].first.second];
    serial[i].second = oss.str();
  }

  stable_sort(serial.begin(), serial.end());

  for(int i = 0; i < m; i++) cout << serial[i].second << endl;
  
  return 0;
}

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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;

template<typename T,typename U>bool chmin(T& a,const U& b){return a>b?(a=b,1):0;}
template<typename T,typename U>bool chmax(T& a,const U& b){return a<b?(a=b,1):0;}

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

vl lens(51),ps(51);

ll calc(ll n,ll x,map<tuple<ll,ll>,ll>& memo)
{
	if(memo.count(mt(n,x)))
		return memo[mt(n,x)];
	ll& res=memo[mt(n,x)];
	if(n==0)
		return res=x;
	if(x<1)
		return res;
	x--;
	if(x<lens[n-1])
		return res+=calc(n-1,x,memo);
	x-=lens[n-1];
	res+=ps[n-1];
	if(x<1)
		return res;
	x--;
	res++;
	if(x<lens[n-1])
		return res+=calc(n-1,x,memo);
	x-=lens[n-1];
	res+=ps[n-1];
	return res;
}

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	lens[0]=ps[0]=1;
	rep(i,50){
		lens[i+1]=2*lens[i]+3;
		ps[i+1]=2*ps[i]+1;
	}

	for(ll n,x;cin>>n>>x&&n|x;){
		map<tuple<ll,ll>,ll> memo;
		cout<<calc(n,x,memo)<<endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INF = 1e18;
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod = 1000000007;
//const int mod = 998244353;
struct mint {
  ll x;
  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;
  }
  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;}
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};
mint choose(int n,int a){
  mint x = 1,y=1;
  rep(i,a){
    x*= n-i;
    y*= i+1;
  }
  return x/y;
}
int main(){
  int n,k;cin>>n>>k;
  rep(i,k){
    mint res = choose(1+n-k,i+1)*choose(k-1,i);
    cout<<res.x<<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
using namespace std;
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr start, itr goal){ for(auto i = start; i != goal; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
#define mod long(1e9 + 7)
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl(long(n))
#define fcout cout << fixed << setprecision(20)
#define highest(x) (63 - __builtin_clzl(x))

int main(){
    long n;
    int k;
    cin >> n >> k;
    long ans = (n - 2) / 11 * 5;
    for(int i = 0; i < (n - 2) % 11; i++){
        for(int j = 0; j < 5; j++){
            ans += (((9 + i * 7 + j) * 9) % 11 == k);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    int i;
    int hight[9];
    int first = 0,second = 0,third = 0;
    for(i=0 ; i<=9 ; i++){
        scanf("%d\n",&hight[i]);
        if(first <= hight[i]){
            third = second;
            second = first;
            first = hight[i];    
        }
        if(first > hight[i] && second <= hight[i]){
            third = second;
            second = hight[i];
        }
        if(second > hight[i] && third <= hight[i]){
            third = hight[i];
        }
        }
    printf("%d\n%d\n%d\n",first,second,third );
    return 0;
}

Measured memory_bytes: 604
require 'prime'
io = STDIN
$prime=Array.new(10**5+1)
$like=Array.new(10**5+1){0}
Prime.each(10**5) do |pr|
  $prime[pr]=true
  if $prime[(pr+1)/2]
    $like[pr]=1
  end
end
rui=0
(10**5).times do |i|
  $like[i+1]+=$like[i]
end
q=io.gets.to_i
q.times do
  l,r=io.gets.split.map(&:to_i)
  puts $like[r]-$like[l-1]
end


Measured memory_bytes: 4504
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		int n,max;
		int minv;
		int R;
		Scanner scan = new Scanner(System.in);
		n=scan.nextInt();
		minv=scan.nextInt();
		R=scan.nextInt();
		max=R-minv;
		if(minv>R){
			minv=R;
		}
		for(int i = 2;i<n;i++){
			R=scan.nextInt();
			if(max<R-minv){
				max=R-minv;
			}
			if(minv>R){
				minv=R;
			}
		}
		scan.close();
		
		System.out.println(max);
	}
}


Measured memory_bytes: 99744
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S divup_L(S a, T b){
  return (a+b-1)/b;
}
int N;
int D;
int X;
int A[100];
int main(){
  int i, res;
  rd(N);
  rd(D);
  rd(X);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  res = X;
  for(i=0;i<N;i++){
    res += (divup_L(D,A[i]));
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190721-1

// --- original code ---
// int N, D, X, A[100];
// {
//   int i, res;
//   rd(N,D,X,A(N));
// 
//   res = X;
//   rep(i,N) res += (D /+ A[i]);
//   wt(res);
// }


Measured memory_bytes: 256
<?php
// $n = (int)trim(fgets(STDIN));
$input = explode(' ', trim(fgets(STDIN)));

$h = (int)$input[0];
$n = (int)$input[1];

$sum = 0;
$input = explode(' ', trim(fgets(STDIN)));
foreach ($input as $a) {
	$sum += (int)$a;
}
if ($h <= $sum) {
	echo 'Yes';
}else{
	echo 'No';
}

Measured memory_bytes: 12792
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    //input
    int n;cin >> n;
    string str; cin >> str;
    vector<char> alp{'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    vector<int> f(100,0);
    vector<int> l(100,0);
    vector<int> count(100,0);
    vector<int> ex(100,0);
 
    //compute
    int ans;
    ans = 0;
 
    for(int j = 0; j < 26; j++){
        for(int i = 0; i < n; i++){
            if(str.at(i) == alp[j]){
                f[j] = i;
                ex[j] = 1;
                break;
            }
        }
        for(int i = 0; i < n - 1;i++){
            if(str.at(n - 1 - i) == alp[j]){
                l[j] = n - 1 - i;
                break;
            }
                
    }
    }

    for(int i = 0; i < 26; i++) {
        if(l[i] < f[i]){
        }else if(ex[i] == 1){        
            for(int j = 0; j < l[i] - f[i] ;j++){
                count[f[i] + j] += 1;
            }
        }
    }

    sort(count.rbegin(),count.rend());

    ans = count[0];

    //output
    cout << ans << endl;

}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
#define llong long long
#define mkpr make_pair
#define x first
#define y second
#define iter iterator
#define riter reversed_iterator
#define y1 Lorem_ipsum_
#define tm dolor_sit_amet_
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 1e6;
char a[mxN+3];
int b[mxN+3];
int s[mxN+3];
int mn[mxN+3];
int n;

int main()
{
	scanf("%s",a+1); n = strlen(a+1);
	int cur = 0,cur2 = 0,lb = 0;
	for(int i=1; i<=n; i++) {b[i] = (a[i]=='1'?-1:1); s[i] = s[i-1]+b[i]; lb = min(lb,s[i]);}
	mn[n] = s[n]; for(int i=n-1; i>=0; i--) {mn[i] = min(s[i],mn[i+1]);}
	int ans = 0;
	for(int i=1; i<=n; i++)
	{
		if(a[i]=='?')
		{
			if(mn[i]-cur*2-2>=lb) {cur++; b[i] = -1;}
		}
	}
	for(int i=1; i<=n; i++) {s[i] = s[i-1]+b[i]; ans = max(ans,s[i]);}
	ans -= lb;
	
	for(int i=1; i<=n; i++) {b[i] = (a[i]=='1'?-1:1); s[i] = s[i-1]+b[i];}
	mn[n] = s[n]; for(int i=n-1; i>=0; i--) {mn[i] = min(s[i],mn[i+1]);}
	int ans2 = 0; lb--; cur = 0;
	for(int i=1; i<=n; i++)
	{
		if(a[i]=='?')
		{
			if(mn[i]-cur*2-2>=lb) {cur++; b[i] = -1;}
		}
	}
	for(int i=1; i<=n; i++) {s[i] = s[i-1]+b[i]; ans2 = max(ans2,s[i]);}
	ans2 -= lb;
	printf("%d\n",min(ans,ans2));
	return 0;
}
//	printf("ans=%d\n",ans);
//	printf("b: "); for(int i=1; i<=n; i++) printf("%d ",b[i]); puts("");
//	printf("s: "); for(int i=1; i<=n; i++) printf("%d ",s[i]); puts("");

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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL << 60;
const ll mod = 1000000007;



VI g[101010];


VLL v(101010,0);

VB used(101010, false);

set<int> s[101010];

int k;

void solve(int p) {
	used[p] = true;

	for (int t : g[p]) {
		if (used[t])continue;
		int cur = s[p].size();
		s[p].insert(t);
		s[t].insert(p);
		cur++;
		v[t] = max(0, (k - cur));
		solve(t);
	}

}



int main() {
	int n;
	cin >> n >> k;
	REP(i, n-1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	v[0] = k;
	solve(0);

	ll ans = 1;

	REP(i, n) {
		ans *= v[i];
		ans %= mod;
	}

	cout << ans << endl;
	
	

	return 0;
}

Measured memory_bytes: 26496
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define rep(i,n) for(int i=0; i<n; i++)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) //sortしてから使う
#define INF 2147483647
#define LLINF 9223372036854775807LL

int main(){
  double w,h; cin>>w>>h;
  double x,y; cin>>x>>y;
  cout <<  setprecision(10) << (double)(w*h)/2.0 << endl;
  if (x == (double)w/2 && y == (double)h/2) cout << 1 << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 3756
#include <stdio.h>
#include <algorithm>
using namespace std;
int N, S, T[50]; bool dp[51][834][1251];
int main() {
	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%d", &T[i]), S += T[i];
	dp[0][0][0] = true;
	for(int i = 1; i <= N; i++) {
		for(int j = 0; j <= S / 3; j++) {
			for(int k = 0; k <= S / 2; k++) {
				dp[i][j][k] = dp[i - 1][j][k];
				if(j - T[i - 1] >= 0) dp[i][j][k] |= dp[i - 1][j - T[i - 1]][k];
				if(k - T[i - 1] >= 0) dp[i][j][k] |= dp[i - 1][j][k - T[i - 1]];
			}
		}
	}
	int ret = 999999999;
	for(int i = 0; i <= S / 3; i++) {
		for(int j = 0; j <= S / 2; j++) {
			if(dp[N][i][j]) {
				ret = min(ret, max({i, j, S - i - j}));
			}
		}
	}
	printf("%d\n", ret);
	return 0;
}

Measured memory_bytes: 50356
#include<cstdio>
#include<functional>
#include<algorithm>
#include<queue>
#include<vector>
#define MM 210000000000000000
using namespace std;
typedef pair<long long,int> P;
vector<int> mati[100000],cost[100000];
int main(void)
{
	int i,n,m,j,b,c,d,p,s,t,r,v,e,flg[100000];
	long long leng[100000],a;

	priority_queue<P,vector<P>,greater<P> > que;
	P ppp;
	scanf("%d %d %d",&v,&e,&r);
	for(i=0;i<e;i++)	{
		scanf("%d %d %d",&s,&t,&d);
		mati[s].push_back(t);
		cost[s].push_back(d);
	}

	for(i=0;i<v;i++)	{
		leng[i]=MM;	flg[i]=0;
	}
	que.push(P(0,r));
	while(que.size()!=0)	{
		ppp=que.top();	que.pop();
		a=ppp.first;	b=ppp.second;
		if(a<leng[b])	{
			leng[b]=a;	flg[b]=1;
			for(i=0;i<mati[b].size();i++)	{
				if(flg[mati[b][i]]==0)	{
					que.push(P(a+cost[b][i],mati[b][i]));
				}
			}
		}
	}
	for(i=0;i<v;i++)	{
		if(leng[i]==MM)	printf("INF\n");
		else printf("%lld\n",leng[i]);
	}
	return 0;
}


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

int main() {
  int n;
  cin >> n;
  int x, ans[n];
  for (int i = 0; i < n; i++) {
    cin >> x;
    ans[x-1] = i+1;
  }

  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
}

Measured memory_bytes: 1152