akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
int main(){
    int n,h[200000],dp[200001]={0};
    cin>>n;
    for(int i=0;i<n;i++) cin>>h[i];
    dp[1]=max(h[0]-h[1],h[1]-h[0]);
    for(int i=1;i<n;i++) dp[i+1]=min(dp[i]+max(h[i]-h[i+1],h[i+1]-h[i]),dp[i-1]+max(h[i-1]-h[i+1],h[i+1]-h[i-1]));
    cout<<dp[n-1];
}

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

int main() {
  char C;
  cin >> C;
  if (C=='a' ||C=='i' ||C=='u' ||C=='e' ||C=='o'){
    cout << "vowel" << endl;
  }else{
    cout << "consonant" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"


using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

//long long int N, M, K, H, W, L, R;
long long int N, M, K, H, W, L, R;

struct Sushi {
	long long int a, b;
	bool operator <(const Sushi& s)const {
		return a + b < s.a + s.b;
	}
};

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

	cin >> N;
	vector<Sushi>v(N);
	for (auto &i : v)cin >> i.a >> i.b;
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	long long int ans = 0;
	for (int i = 0; i < N; i++) {
		if (i & 1) {
			ans -= v[i].b;
		}
		else ans += v[i].a;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<endl
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SUM(vec) accumulate(all(vec),0LL)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;}
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);}
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;}
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;}

int ctoi(char c){return c - '0';}

bool isOk(ll key,ll value){
  return key >= value;
}

ll binary_search(vector<ll> a,ll key){
  ll ok = a.size()-1;
  ll ng = 0;

  while(abs(ok - ng) > 1){
    ll mid = (ok + ng) / 2;
    if(isOk(key,a[mid]))ok = mid;
    else ng = mid;
  }
  return ok;
}

bool isPrime(ll n) {
	for (int i = 2; n >= i * i; ++i) {
		if(!(n % i))return false;
	}
  return true;
}
vector<ll> primes(ll n){
  vector<ll> v(1,1);
  for (ll i = 2; n >= i * i; ++i) {
		if(!(n % i)){
      v.pb(i);
	  }
  }
  if(v.size()==1)v.pb(n);
  return v;
}


int main() {
  cin.tie(0); ios::sync_with_stdio(0);
  ll n,m;cin>>n>>m;

  ll ans = 1;
  for(ll i = 2;i*i <= m;++i){
    int cnt = 0;
    while(m%i==0){
      if(++cnt%n==0){
        ans*=i;
      }
      m/=i;
    }
  }
  if(n==1)ans*=m;
  print(ans);
  return 0;
} 

Measured memory_bytes: 256
// 解説PDF見た
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)

int N, A, B, C;
int L[8];
const int INF = 1<<30;

int f(int n, int a, int b, int c) {
    if (n == 0) {
        if (a == 0 || b == 0 || c == 0) {
            // 無から竹は作れない
            return INF;
        } else {
            return abs(a - A) + abs(b - B) + abs(c - C) - 30;
        }
    }
    int l = L[n - 1];
    int ret0 = f(n - 1, a, b, c); // lは使わない
    int ret1 = f(n - 1, a + l, b, c) + 10; // lはaを作るのに使う
    int ret2 = f(n - 1, a, b + l, c) + 10; // lはaを作るのに使う
    int ret3 = f(n - 1, a, b, c + l) + 10; // lはaを作るのに使う
    return min({ret0, ret1, ret2, ret3});
}

int main() {
    cin >> N >> A >> B >> C;
    rep(i, N) {
        cin >> L[i];
    }
    cout << f(N, 0, 0, 0) << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
    int a,b;
    cin>>a>>b;
    cout<<max({a+b,a-b,a*b})<<endl;
    
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            int[] A = new int[n];

            for (int i = 0; i < n; i++)
            {
                A[i] = int.Parse(Console.ReadLine());
            }

            Console.WriteLine(GetLIS(A));
        }

        static int GetLIS(int[] A)
        {
            const int INFTY = int.MaxValue;
            int n = A.Length;

            int[] L = Enumerable.Repeat(INFTY, n).ToArray();
            int[] id = new int[n];
            int ret = 0;

            for (int i = 0; i < n; i++)
            {
                id[i] = LowerBound(L, A[i]);
                L[id[i]] = A[i];

                ret = Math.Max(ret, id[i] + 1);
            }

            return ret;
        }

        static int LowerBound(int[] arr, int value)
        {
            int low = 0;
            int high = arr.Length;
            int mid;

            while (low < high)
            {
                mid = ((high - low) >> 1) + low;        // (low + high) / 2
                if (arr[mid] < value) low = mid + 1;
                else high = mid;
            }
            return low;
        }
    }
}

Measured memory_bytes: 11680
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader br = null;
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			String input = br.readLine();
			String[] inputs = input.split(" ");
			int n = Integer.parseInt(inputs[0]);
			int a = Integer.parseInt(inputs[1]);
			int b = Integer.parseInt(inputs[2]);
			System.out.println(Math.min(n*a, b));
		} catch (Exception e) {
			e.printStackTrace();
		} finally {
			try {
				if(br != null) {
					br.close();
					br = null;
				}
			} catch (Exception e) {

			}
		}
	}
}


Measured memory_bytes: 21332
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#define INF 1<<30
using namespace std;
int main() {
	cin.tie(0);ios::sync_with_stdio(false);
	int V; cin >> V;
	vector<vector<pair<int, int>>> g(V);
	vector<int> dp(V);
	queue<int> q;

	//input
	for (int i = 0; i < V; i++) {
		int u, k; cin >> u >> k;
		for (int j = 0; j < k; j++) {
			int c, v;
			cin >> c >> v;
			g[u].push_back(make_pair(c, v));
		}
	}

	//initialize
	fill(dp.begin(), dp.end(), INF);
	dp[0] = 0;
	q.push(0);

	//Dijkstra
	while (!q.empty()) {
		int k = q.front(); q.pop();
		for (int i = 0; i < g[k].size();i++) {
			int next = g[k][i].first;
			int w = g[k][i].second;
			if (dp[k] + w < dp[next]) {
				dp[next] = dp[k] + w;
				q.push(next);
			}
		}
	}

	//output
	for (int i = 0; i < V;i++) {
		cout << i << " " << dp[i] << endl;
	}
}

Measured memory_bytes: 7768
#include<cstdio>
using namespace std;
char s[11];
int main()
{
    gets(s);
    if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I')
    {
        printf("Yes\n");
    }
    else
    printf("No\n");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=300005,INF=1<<30;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int ans=0;
    for(int i=0;i<5;i++){
        int a;cin>>a;
        ans+=a;
    }
    cout<<15-ans<<endl;
}



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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  while(1){
    C=C-B;
    if(C<=0) break;
    A=A-D;
    if(A<=0) break;
  }
  if(A<=0) cout << "No" << endl;
  else cout << "Yes" << endl;
}

Measured memory_bytes: 3604
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int[][] a = new int[2][n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = Integer.parseInt(sc.next());
            }
        }

        // 主処理
        int[][] dp = new int[2][n];
        for (int i = 0; i < 2; i++) {
            int pre = 0;
            for (int j = 0; j < n; j++) {
                if (i == 0) {
                    dp[i][j] = a[i][j] + pre;
                    pre = dp[i][j];
                } else {
                    dp[i][j] = Math.max(a[i][j] + pre, a[i][j] + dp[i - 1][j]);
                    pre = dp[i][j];
                }
            }
        }
        int result = dp[1][n - 1];

        // 出力
        System.out.println(result);
        sc.close();
    }
}


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

#define int long long

const int inf = 1e18;

signed main(){

  int N;
  int minimum = inf, maximum = 0;
  int minc = 0, maxc = 0;
  vector<int> a;

  cin>>N;

  a.resize(N);

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

    minimum = min(a[i], minimum);
    maximum = max(a[i], maximum);
  }

  if(maximum - minimum >= 2) {
    cout<<"No"<<endl;
    return 0;
  }

  for(int i = 0; i < N; i++){
    if(a[i] == maximum) maxc++;
    else minc++;
  }




  if(maximum == minimum) {
    if(N-1 == minimum) {
      cout<<"Yes"<<endl;
      return 0;
    }

    int x = N/2;

    if(minimum <= x) {
      cout<<"Yes"<<endl;
      return 0;
    } else {
      cout<<"No"<<endl;
      return 0;
    }
  } else {
    if(maxc == 1) {
      cout<<"No"<<endl;
      return 0;
    }
    int a = minc + 1;
    int b = minc + maxc/2;

    if(a <= maximum && maximum <= b){
      cout<<"Yes"<<endl;
      return 0;
    } else {
      cout<<"No"<<endl;
      return 0;
    }

  }


  return 0;
}


Measured memory_bytes: 1024
import Data.List

f :: [[Int]] -> [(Int,Int)]
f [] = []
f ((e:p:q:_):xs) = (e,p*q):(f xs)

g :: [(Int,Int)] -> [(Int,Int)]
g [] = []
g ((e,v):[]) = [(e,v)]
g ((e0,v0):(e1,v1):xs)
  | e0 == e1  = g ((e0,v0+v1):xs)
  | otherwise = ((e0,v0):(g ((e1,v1):xs)))

g' :: [(Int,Int)] -> [(Int,Int)]
g' [] = []
g' ((e,v):[]) = [(e,v)]
g' x@((e0,v0):xs) =
  let v = sum $ map snd $ filter (\(e,v) -> e0 == e) x
      y = filter (\(e,v) -> e0 /= e) xs
  in
    ((e0,v):(g' xs))

h :: [(Int,Int)] -> [Int]
h [] = []
h ((e,v):xs)
  | v >= 1000000 = (e:(h xs))
  | otherwise    = h xs

p [] = []
p ([]:xs) = ["NA"] ++ (p xs)
p (x:xs)  = (map show x) ++ (p xs)

ans ([0]:_) = []
ans (n:ns) =
  let d = take (n!!0) ns
      r = drop (n!!0) ns
      a = h $ g' $ f d
  in
    a:(ans r)

main = do
  c <- getContents
  let i = map (map read) $ map words $ lines c :: [[Int]]
      o = unlines $ p $ ans i
  putStr o

Measured memory_bytes: 5532
def bellman_ford(n, s, edges, init_val = float('inf')): 
    d = [init_val] * n
    d[s] = 0
    for _ in range(n):
        updated = False
        for vf, vt, w in edges:
            if d[vf] != init_val and d[vt] > d[vf] + w:
                d[vt] = d[vf] + w
                updated = True
        if not updated:
            break
    while updated: #閉路の存在
        updated = False
        for vf, vt, w in edges:
            if d[vt] > d[vf] + w:
                d[vt] = -float('inf')
                updated = True
    return d

n, m = map(int, input().split())
edges = []
for i in range(m):
    a, b, w = map(int, input().split())
    edges.append((a-1,b-1,-w))
d = bellman_ford(n, 0, edges)
print(-d[-1] if d[-1] != -float('inf') else 'inf')


Measured memory_bytes: 74736
#include <stdio.h>
#include <math.h>
int main(void){
    int a,b,c,d,n;
    while(scanf("%d",&n)!=EOF){
        int count=0;
        
        for(a=0;a<=9;a++){
            for(b=0;b<=9;b++){
                for(c=0;c<=9;c++){
                    for(d=0;d<=9;d++){
                        if(a+b+c+d==n){
                            count++;
                        }
                        
                    }
                }
            }
        }
        
    
    printf("%d\n",count);   
    }
    
}


Measured memory_bytes: 2040
import java.util.*;
import java.io.*;
import java.lang.*;

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

        int n = sc.nextInt();
        int k = sc.nextInt();

        ArrayList<Integer> arr = new ArrayList<Integer>();

        for (int i = 0; i<n; i++){
            arr.add(sc.nextInt());
        }

        Collections.sort(arr);
        int ans = 0;
        for (int i = 0; i<k; i++){
            ans += arr.get(i);
        }

        System.out.println(ans);
    }
}

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

class Root
{
    static T to<T>(string str)
    {
        return (T)Convert.ChangeType(str, typeof(T));
    }

    static string cin2str()
    {
        return System.Console.ReadLine().Trim();
    }

    static string[] cin2strs()
    {
        return cin2str().Split(' ');
    }

    static T cin2var<T>()
    {
        return to<T>(cin2str());
    }

    static T[] cin2arr<T>()
    {
        return cin2strs().Select(line => to<T>(line)).ToArray();
    }

    static void Swap<T>(ref T lhs, ref T rhs)
    {
        T temp = lhs;
        lhs    = rhs;
        rhs    = temp;
    }

    static void Main(string[] args)
    {
        var N   = cin2var<int>();
        int[] A = cin2arr<int>();

        var ans = new List<int>(A);
        ans.Sort();

        var match_count = 0;
        for (var i = 0; i < N; ++i) {
            if (A[i] == ans[i]) ++match_count;
        }

        if (match_count == N) {
            Console.WriteLine("0");
            return;
        }

        var Q = cin2var<int>();
        for (var i = 0; i < Q; ++i) {
            int[] P = cin2arr<int>();
            var  l  = P[0] - 1;
            var  r  = P[1] - 1;
            bool ml = A[l] == ans[l];
            bool mr = A[r] == ans[r];
            Swap<int>(ref A[l], ref A[r]);
            bool ml2 = A[l] == ans[l];
            bool mr2 = A[r] == ans[r];
            if (ml && !ml2) --match_count;
            if (mr && !mr2) --match_count;
            if (!ml && ml2) ++match_count;
            if (!mr && mr2) ++match_count;
            if (match_count == N) {
                Console.WriteLine("{0}", i + 1);
                return;
            }
        }

        Console.WriteLine("-1");
    }
}


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

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

  int D = 0;
  int ans = 1;
  rep(i, N) {
    int L;
    cin >> L;
    D = D + L;
    if (D <= X) ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
int main(void) {
  int n, m;
  ll x, y;
  cin >> n >> m;
  ll sumx = 0, sumy = 0;
  for (int i = 0; i < n; i++) {
    cin >> x;
    sumx = (sumx + ((2 * i - n + 1) * x + MOD) % MOD) % MOD;
  }
  for (int i = 0; i < m; i++) {
    cin >> y;
    sumy = (sumy + ((2 * i - m + 1) * y + MOD) % MOD) % MOD;
  }
  cout << sumx * sumy % MOD << endl;
  return 0;
}

Measured memory_bytes: 256
s = input()[::-1]
m = [0]*2019
m[0] = 1
d = 1
t = 0
for i in s:
    t += int(i)*d
    t %= 2019
    m[t] += 1
    d = (d*10)%2019


def c2(n):
    return n*(n-1)//2
print(sum([c2(i) for i in m]))

Measured memory_bytes: 9292
loop do
  x, y  = gets.split.map(&:to_i)

  if x == 0 && y == 0
    break
  else
    case x <=> y
    when -1, 0
      a, b = x, y
    when 1
      a, b = y, x
    end
    puts "#{a} #{b}"
  end
end

Measured memory_bytes: 6100
package main

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

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	k := getNextInt(scanner)
	mc := newModcom(n + k)
	fmt.Fprintln(writer, mc.choose(n+k-1, k-1))
}

type mint int64

func (mt mint) mod() mint {
	m := mint(1e9 + 7)
	mt %= m
	if mt < 0 {
		return mt + m
	}
	return mt
}
func (mt mint) inv() mint {
	return mt.pow(mint(0).sub(2))
}
func (mt mint) pow(n mint) mint {
	p := mint(1)
	for n > 0 {
		if n%2 == 1 {
			p.mulAs(mt)
		}
		mt.mulAs(mt)
		n >>= 1
	}
	return p
}
func (mt mint) add(x mint) mint {
	return (mt + x).mod()
}
func (mt mint) sub(x mint) mint {
	return (mt - x).mod()
}
func (mt mint) mul(x mint) mint {
	return (mt * x).mod()
}
func (mt mint) div(x mint) mint {
	return mt.mul(x.inv())
}
func (mt *mint) addAs(x mint) *mint {
	*mt = mt.add(x)
	return mt
}
func (mt *mint) subAs(x mint) *mint {
	*mt = mt.sub(x)
	return mt
}
func (mt *mint) mulAs(x mint) *mint {
	*mt = mt.mul(x)
	return mt
}
func (mt *mint) divAs(x mint) *mint {
	*mt = mt.div(x)
	return mt
}

type modcom struct {
	facs, invs []mint
}

func newModcom(n int) modcom {
	facs := make([]mint, n+1)
	invs := make([]mint, n+1)
	facs[0] = 1
	for i := 0; i < n; i++ {
		facs[i+1] = facs[i].mul(mint(i + 1))
	}
	invs[n] = facs[n].inv()
	for i := n - 1; i >= 0; i-- {
		invs[i] = invs[i+1].mul(mint(i + 1))
	}
	return modcom{
		facs: facs,
		invs: invs,
	}
}
func (mc *modcom) choose(n, k int) mint {
	return mc.facs[n].mul(mc.invs[k]).mul(mc.invs[n-k])
}



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

int main(){
	bool ya=true;
	int a, b, c;
	cin>>a>>b>>c;
	if((a>c)||(b<c)){
		ya=false;
	}
	if(ya){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int median(vector<int>);
int main(void){
    std::vector<int> v;
    int N;
    cin >> N;
    for(int i = 0; i < N ;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(),v.end());
    int m = median(v);
    if(v[N/2] >= m && v[N/2-1] <= m){
        cout << v[N/2] - v[N/2-1] << endl; 
        
    }else{
        
        cout << 0 << endl;
    }
}
int median(vector<int> c){
    size_t n = c.size() / 2;
    std::nth_element(c.begin(), c.begin() + n, c.end());
    return c[n];
}


Measured memory_bytes: 1144
#include<stdio.h>
#define MAX 100000

int A[MAX], n;

int partition(int p, int r) {
  int x, i, j, t;
  x = A[r];
  i = p - 1;
  for ( j = p; j < r; j++ ) {
    if ( A[j] <= x ) {
      i++;
      t = A[i]; A[i] = A[j]; A[j] = t;
    }
  }
  t = A[i + 1]; A[i + 1] = A[r]; A[r] = t;
  return i + 1;
}

int main() {
  int i, q;

  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) scanf("%d", &A[i]);

  q = partition(0, n - 1);

  for ( i = 0; i < n; i++ ) {
    if ( i ) printf(" ");
    if ( i == q ) printf("[");
    printf("%d", A[i]);
    if ( i == q ) printf("]");
  }
  printf("\n");

  return 0;
}



Measured memory_bytes: 2132
#include <stdio.h>
int main()
{
  char box[1200];
  int i;
  for(i=0;box[i-1]!='\n';i++)
    {
      scanf("%c",&box[i]);
      if(box[i]>=65 && box[i]<=90)box[i]+=32;
      else if(box[i]>=97 && box[i]<=122)box[i]-=32;
     }
  box[i-1]=0;
  printf("%s\n",box);
  return 0;
}

Measured memory_bytes: 524
import scala.io.StdIn

object Main extends App {

  val n = StdIn.readLine().trim.toInt
  var root: Node = null
  
  case class Node(key: Int, var parent: Node, var left: Node, var right: Node){
    private def getDefaultKey(p: Node) = if(p == null) -1 else p.key
    override def toString: String = s"Node($key, ${getDefaultKey(parent)} ${getDefaultKey(left)} ${getDefaultKey(right)})"
  }
  
  (0 until n).foreach { _ =>
    val command = StdIn.readLine()
    command.split(' ') match {
      case Array("insert", key) => insert(Node(key.toInt, null, null, null))
      case _ => {
        // print
        inorder(root)
        println("")
        preorder(root)
        println("")
      }
    }
  }
  
  
  def insert(z: Node) = {
    var y:Node = null
    var x:Node = root
    while(x != null){
      y = x
      if(z.key < x.key){
        x = x.left
      } else {
        x = x.right
      }
    }
    z.parent = y
    
    if(y == null){
      root = z
    } else if(z.key < y.key){
      y.left = z
    } else {
      y.right = z
    }
  }
  
  def preorder(n: Node): Unit = {
    print(" " + n.key)
    if(n.left != null) preorder(n.left)
    if(n.right != null) preorder(n.right)
  }

  def inorder(n: Node): Unit = {
    if(n.left != null) inorder(n.left)
    print(" " + n.key)
    if(n.right != null) inorder(n.right)
  }
  
}


Measured memory_bytes: 464468
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
	ll n;
	cin >> n;
	ll a,b;
	cin >> a >> b;

	if((b - a) % 2 == 0){
		cout << (b - a) / 2 << endl;
	}
	else{
		ll ans1 = a + (b - a - 1) / 2;
		ll ans2 = ((n - b) + 1) + (b - a - 1) / 2;
		cout << min(ans1,ans2) << endl;
	}
}


Measured memory_bytes: 3632
#include<stdio.h>
#define N 1000000
 
int a[N];
int cnt=0;
int G[N];
int m=1;
 
void insertionSort(int n,int g){
    for(int i=g;i<n;i++){
        int v=a[i];
        int j=i-g;
        while(j>=0 && a[j] > v){
            a[j+g]=a[j];
            cnt++;
            j=j-g;
        }
        a[j+g]=v;
    }
    return;
}
 
 
void shellSort(int n){
    int temp=n;
     
    G[0]=1;
     
    while(1){
        G[m]=G[m-1]*3+1;
        if(G[m] > n)break;
        m++;
    }
     
    for(int i=m-1;i>=0;i--)
        insertionSort(n,G[i]);
     
    return;
}
 
 
 
int main(){
    int n,i;
     
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
     
    shellSort(n);
     
     
    printf("%d\n",m);
    for(i=m-1;i>0;i--)
        printf("%d ",G[i]);
    printf("%d\n",G[0]);
     
    printf("%d\n",cnt);
     
    for(i=0;i<n;i++)
        printf("%d\n",a[i]);
     
    return 0;
}


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

const int LEN = 2000001;
static const int K = 10001;
int C[K];
int A[LEN];

void countingSort(int A[], int n)
{
    for (int i = 0; i < K; ++i)
    {
        C[i] = 0;
    }

    for (int i = 0; i < n; ++i)
    {
        ++C[A[i]];
    }

    for (int i = 1; i < K; ++i)
    {
        C[i] += C[i-1];
    }

    int *B = (int *)malloc(n * sizeof(int));

    for (int i = n-1; i >= 0; --i)
    {
        B[--C[A[i]]] = A[i];
    }

    for (int i = 0; i != n; ++i)
    {
        A[i] = B[i];
    }

    free(B);
}

int main()
{
    int n;

    scanf("%d", &n);

    for (int i = 0; i != n; ++i)
    {
        scanf("%d", &A[i]);
    }

    countingSort(A, n);

    for (int i = 0; i != n; ++i)
    {
        if (i) printf(" ");
        printf("%d", A[i]);
    }

    printf("\n");

    return 0;
}


Measured memory_bytes: 18332
# おなじみ 1/w = ...の形からもっていくとw = ..が導出できた

N = int(input())
for n in range(1, 3501):
    for h in range(1, 3501):
        t = 4 * n * h - N * (h + n)
        if t == 0 or t < 0:
            continue
        w = (N * n * h) / t
        if int(w) == w:
            w = int(w)
            print(h, n, w)
            exit()


Measured memory_bytes: 40796
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define LL long long
using namespace std;
const int N=1e5+10;
int n,m,cnt,a,ans,bin[N];
map<int,int> M;
int main()
{
	int i,j,k;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
	  scanf("%d",&a);
	  if (!M[a])  M[a]=++cnt,bin[M[a]]++;
	  else  bin[M[a]]++;
    }
    for (i=1;i<=cnt;i++)
      if (bin[i]%2==1)  ans++;  
    printf("%d",ans);
}

Measured memory_bytes: 5248
from collections import defaultdict

def main():
    n = int(input())
    d = defaultdict(int)
    count = 0
    for i in range(n):
        s = input()
        if d[s] == 0:
            count+=1
            d[s] += 1
        else:
            continue
    print(count)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 35440
import java.util.*;
import java.io.*;
public class Main{
  public static void main(String[] args){
    RapidScanner sc = new RapidScanner();
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    System.out.println(Math.min(a, b) + Math.min(c, d));
  }
}

class RapidScanner{
  BufferedReader reader;
  int index;
  String[] buffer;
  public RapidScanner(){
    reader = new BufferedReader(new InputStreamReader(System.in));
    try{
      buffer = reader.readLine().split(" ");
    }catch(Exception e){
      
    }
    index = 0;
  }
  
  public int nextInt(){
    if(index == buffer.length){
      try{
        buffer = reader.readLine().split(" ");
      }catch(Exception e){
        
      }
      index = 0;
    }
    return Integer.parseInt(buffer[index++]);
  }
}

Measured memory_bytes: 23252
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
LL go(int n){
    VI d;
    REP(i,n){
        DRI(x);
        d.PB(x);
    }
    sort(ALL(d));
    LL res=0;
    REPP(i,1,SZ(d)){
        res=(res+(LL)(d[i]-d[i-1])*i%MOD*(SZ(d)-i))%MOD;
    }
    return res;
}
int main(){
    DRII(n,m);
    cout<<go(n)*go(m)%MOD<<endl;
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
#define MEMS(a,b) memset(a,b,sizeof(a))
#define mp make_pair
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 ll MOD = 1e9+7;

#define T 26

int D;
ll C[30];
ll S[400][30];
ll ANS[400];

void input(){
    cin >> D;
    REP(i,T)
        scanf("%lld", &C[i]);
    REP(i,D)
        REP(j,T)
            scanf("%lld", &S[i][j]);
}

void output(){
    REP(i,D)
        printf("%lld\n", ANS[i]+1);
}

// O(DT) = O(365 * 26) = O(10 ** 4)
void calc_score(ll score[], ll ans[]){
    vector<int> last(T, -1);
    ll s = 0;
    REP(d,D){
        s += S[d][ans[d]];
        last[ans[d]] = d;

        REP(i,T){
            s -= C[i] * (d - last[i]);
        }
        score[d] = s;
    }
}

int main(){
    input();


    // greedy
    vector<ll> last(T, -1);
    REP(d, D){
        ll high = -1e15;
        ll t;
        ll minus = 0;
        REP(i, T){
            minus += C[i] * (d - last[i]);
        }

        REP(i, T){
            ll m = minus - C[i] * (d - last[i]);
            ll plus = S[d][i];
            ll val = plus - m;
            if(high < val){
                high = val;
                t = i;
            }
        }
        ANS[d] = t;
        last[t] = d;
    }

    //ll V[400];
    ll S[400];
    calc_score(S, ANS);
    ll score = S[D-1];

    //REP(i,15000){
    REP(i,30000){
        int day = rand() % 365;
        int cont = rand() % 26;
        int pre_val = ANS[day];
        ll pre_score = score;

        ANS[day] = cont;
        calc_score(S, ANS);

        if(S[D-1] <= pre_score){
            ANS[day]  = pre_val;
        }
        else{
            //printf("%lld -> %lld\n", pre_score, S[D-1]);
            score = S[D-1];
        }
    }
    //REP(d,D)
    //    cout << score[d] << endl;

    //REP(d,D)
    //    ANS[d] = V[d];
    output();
    return 0;
}


Measured memory_bytes: 3848
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  char c[h][w];
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      cin >> c[i][j];
    }
  }
  int ans = 0;
  for (int i = 0; i < (1 << h); ++i) {
    for (int j = 0; j < (1 << w); ++j) {
      char tmp[h][w];
      for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
          tmp[y][x] = c[y][x];
        }
      }
      for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
          if ((i >> y) & 1 || (j >> x) & 1) {
            tmp[y][x] = '@';
          }
        }
      }
      int cnt = 0;
      for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
          if (tmp[y][x] == '#') cnt++;
        }
      }
      if (cnt == k) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1]
dp = [1] * (amax+1)
ans = 0
for i in range(len(a)-1):
    p = a[i]
    if dp[p] == 1:          
        for q in range(amax//p+1):
            dp[p*q] = 0         
        if a[i] != a[i+1]: 
            ans += 1            
if dp[amax] == 1:        
  ans += 1
print(ans)

Measured memory_bytes: 32304
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

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

    Int a, b;
    string s;
    cin >> a >> s;
    s.erase(next(s.begin()));
    b = stoll(s);

    cout << a * b / 100 << endl;

    return 0;
}


Measured memory_bytes: 3648
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(void) {

	string x, y;

	cin >> x;

	y = x;

	swap(x.at(0), x.at(2));

	if (x == y)cout << "Yes\n";
	else cout << "No\n";

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vp = vector<Pii>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

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

  string s;
  cin >> s;
  if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) cout << "Bad" << endl;
  else cout << "Good" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define All(a) a.begin(),a.end()
#define INF 1000000007
const int MOD = 1000000007;
//accumulate(vec.begin(), vec.end(), 0)

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

int main(){
  int h,n;
  cin >> h >> n;
  int sum = 0;
  for(int i=0;i<n;i++){
    int a; cin >> a;
    sum += a;
  }
  if(h<=sum) cout<< "Yes" <<endl;
  else cout<< "No" <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <utility>
#include <climits>
#include <vector>
using namespace std;

#define ll long long int

const int MOD = 1000000007;

int max(int a, int b) {

	if (a > b)return a;
	else return b;

}
int main() {

	int A, B, C, D;
	cin >> A >> B >> C >> D;
	cout << max(A*B, C*D) << endl;

	return 0;
}

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

int main(void){
  long long N;
  scanf("%lld",&N);   
  for(long long i = (long long)sqrt(N);i > 0;i--){
    if(N % i == 0){
      printf("%lld\n",N / i + i - 2);
      return 0;
    }
  }
    return 0;
}
	


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
typedef long long ll;

using namespace std;

int n,m,r;
int rr[8];
bool used[8];
int d[200][200];
int minr;

int saiki(int g)
{
	cerr<<g<<endl;
	int m=99999999;
	int index;
	bool f=false;
	for(int i=0;i<r;i++)
	{
		if(used[i])
			continue;
		
		if(m>d[rr[i]][g])
		{
			m=d[rr[i]][g];
			index=i;
		}
	}
	used[index]=true;
	for(int i=0;i<r;i++)
	{
		if(!used[i])
			f=true;
	}
	if(f)
		minr = saiki(rr[index]);
	return minr+d[rr[index]][g];
}

int main()
{
	int ans=99999999;
	cin>>n>>m>>r;
	fill(d[0],d[200],99999999);
	fill(used,used+8,false);
	for(int i=0;i<r;i++)
	{
		cin>>rr[i];
		rr[i]--;
	}
	
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a--;
		b--;
		d[a][b]=c;
		d[b][a]=c;
	}

	//ワーシャルフロイド
	for(int k=0;k<n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}

	sort(rr,rr+r);
	minr=99999999;
	do
	{
		int t=0;
		for(int i=1;i<r;i++)
		{
			t += d[rr[i-1]][rr[i]];
		}
		if(minr>t)
			minr=t;
	}while(next_permutation(rr,rr+r));
	cout<<minr<<endl;
	return 0;
}

Measured memory_bytes: 384
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int wideLength = Integer.parseInt(sc.next());
        List<Integer> topList = new ArrayList<>();
        for(int x=1; x<= wideLength; x++) {
            topList.add(Integer.parseInt(sc.next()));
        }
        List<Integer> secondList = new ArrayList<>();
        for(int x=1; x<= wideLength; x++) {
            secondList.add(Integer.parseInt(sc.next()));
        }
        int res = 0;
        for(int x=1; x<= wideLength; x++) {
            int candy = 0;
            for(int y=1; y<=x; y++) {
                candy += topList.get(y-1);
            }
            for(int y=x; y<=wideLength; y++) {
                candy += secondList.get(y-1);
            }
            res = res>=candy?res:candy;
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 21844
n = int(input())
v = 'abcdefghijk'

w = []
def dfs(s,t):
  if len(s) == n:
    w.append(s)
    return
  u = len(set(s))
  for i in range(u+1):
    dfs(s+v[i],u+1)

dfs('a',1)

for i in w:
  print (i)

Measured memory_bytes: 17088
#include <stdio.h>

long long count_zero(long long n){
  long long count;
  
  if(n <= 4){
    return 0;
  }
  else{
    count = n / 5 + count_zero(n / 5);
  }
  
  return count;
}

int main(){
  long long n;
  long long count;
  
  scanf("%lld", &n);
  
  if(n % 2 == 1){
    printf("0\n");
    return 0;
  }
  else{
    count = count_zero(n / 2);
  }
  
  printf("%lld\n", count);
  
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>

using namespace std;

int main () {
  long long n,m;
  long long ans=0;
  cin >> n >> m;

  if (n * 2 > m) {
    ans = m/2;
  } else {
    ans = n;
    m -= n*2;
    ans += m/4;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
# nコマ, m地点
def func(n, m, x):
    x.sort()
    dis = []
    for i in range(1, len(x)):
        dis.append(x[i] - x[i-1])
    dis.sort()
    n = min(n, m)
    # print("n:{} dis:{}".format(n, dis))
    print(sum(dis[:m-n]))
# for i in range(1, 10):
    # func(i, 7, [-10, -3, 0, 9, -100, 2, 17])
"""
func(3, 5, [1, 2, 10, 12, 14])
func(3, 7, [-10, -3, 0, 9, -100, 2, 17])
func(100, 1, [-100])
"""
n, m = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
func(n, m, x)

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

bool kai(string S)
{
    rep(i, (int)S.size()) {
        if (S[i] != S[S.size() - i - 1]) {
            return false;
        }
    }
    return true;
}

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

    bool b = kai(S);
    if (!b) {
        cout << "No" << endl;
        return 0;
    }

    string S2 = S.substr(0, (S.size() - 1)/2);
    b = kai(S2);
    if (!b) {
        cout << "No" << endl;
        return 0;
    }

    int N = S.size();
    string S3 = S.substr((N + 3)/2 - 1, N);
    b = kai(S3);
    if (!b) {
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 3612
s = gets.chomp.split("")
(s.size - 1).times do |i|
  if s[i] == s[i + 1]
    puts "#{i + 1} #{i + 2}"
    exit
  elsif s[i] == s[i + 2]
    puts "#{i + 1} #{i + 3}"
    exit
  end
end
puts "-1 -1"

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

using namespace std;

long long gcd(long long a, long long b) {
  return !b ? a : gcd(b, a % b);
}

bool check(long long l, long long r, long long a, long long b) {
  b %= a;
  l += a - b, r += a - b;
  return r / a > (l - 1) / a;
}

int main() {
  int T;
  cin >> T;
  while (T--) {
    long long A, B, C, D;
    cin >> A >> B >> C >> D;
    puts(A < B || B > D || check(C + 1, B - 1, gcd(B, D), A) ? "No" : "Yes");
  }
  return 0;
}


Measured memory_bytes: 256
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
	int h, w, k, ans = 0;
	cin >> h >> w >> k;
	vector<string> b(h);
	for (int i = 0; i < h; ++i) {
		cin >> b[i];
	}
	for (int yf = 0; yf < 1 << h; ++yf) {
		for (int xf = 0; xf < 1 << w; ++xf) {
			int cnt = 0;
			for (int y = 0; y < h; ++y) {
				if (yf & (1 << y)) continue;
				for (int x = 0; x < w; ++x) {
					if (xf & (1 << x)) continue;
					cnt += b[y][x] == '#';
				}
			}
			ans += cnt == k;
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
	int a,b,c;

	cin >> a >> b >> c ;

	if (a+b>=c){
		cout << "Yes" << endl;
	}

	else {
		cout << "No" << endl;
	}

	return 0;
}

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

#define sf scanf
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define pb push_back

const int maxn = 150;

int n, a[maxn], b[maxn], tmp[maxn], len;

int main()
{
    sf("%d",&n);
    fo(i,1,n) sf("%d",&b[i]);
    len = n;
    fo(i,1,n)
    {
        bool sammi = false;
        for(int j = len; j >= 1; -- j) 
            if(b[j] == j)
            {
                int cur = 0;
                fo(k,1,j-1) tmp[++cur] = b[k];
                fo(k,j+1,len) tmp[++cur] = b[k];
                -- len;
                fo(i,1,len) b[i] = tmp[i];
                a[i] = j;
                sammi = true;
                break;    
            }
        if(!sammi) return 0 * printf("-1");
    }
    for(int i = n; i >= 1; -- i) printf("%d\n",a[i]);
    return 0;
}


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

using namespace std;


int main() {
    int N, K;
    cin >> N >> K;
    int g = -1;
    vector<int> D;
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        if (K <= A) D.push_back(A - K);
        if (g == -1) {
            g = A;
        } else {
            g = __gcd(g, A);
        }
    }
    for( auto d : D){
        if( d % g == 0 ){
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;


}


Measured memory_bytes: 892
// 16:32 - 17:04
#include <iostream>

using ll = long long;

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

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

ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

ll f(ll x, ll c, ll d) {
  ll res = x;
  res -= x / c;
  res -= x / d;
  res += x / lcm(c, d);
  return res;
}

int main() {
  ll a, b, c, d;
  std::cin >> a >> b >> c >> d;

  ll ans = f(b, c, d) - f(a - 1, c, d);
  std::cout << ans << '\n';

  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace lean {
    class Program {
        static void Main() {
            bool a = false;
            string[] str = Console.ReadLine().Split();
            int x = int.Parse(str[0]);
            int y = int.Parse(str[1]);
            for (int i = 0; i <= x; i++)
            {
                if ((i * 2) + (4 * (x - i)) == y)
                {
                    a = true;
                }
            }

            if (a)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 27528
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl

ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1e9;
const long long LINF = 1LL << 50;
#define int long long

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, x; cin >> n >> x;
	VE a(n); rep(i, n)cin >> a[i];
	int ans = 0;
	if (a[0] > x) {
		ans += a[0] - x;
		a[0] = x;
	}
	rep(i, n - 1) {
		if (a[i] + a[i + 1] > x) {
			int tmp = a[i] + a[i + 1] - x;
			ans += tmp;
			a[i + 1] -= tmp;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1024
# frozen_string_literal: true

N, X = gets.split.map(&:to_i)
CITIES = gets.split.map(&:to_i)

abs_list = CITIES.map {|city| (city - X).abs }.sort {|a, b| b <=> a }

def func(a, b)
  remainder = a % b
  if remainder > 0
    func(b, remainder)
  else
    b
  end
end

puts abs_list.inject(abs_list[0]) {|answer, val| func(val, answer) }


Measured memory_bytes: 10880
N=int(input())
S= [input() for i in range(N)]
AC_len=int(S.count('AC'))
WA_len=int(S.count('WA'))
TLE_len=int(S.count('TLE'))
RE_len=int(S.count('RE'))
print('AC x'+' '+str(AC_len))
print('WA x'+' '+str(WA_len))
print('TLE x'+' '+str(TLE_len))
print('RE x'+' '+str(RE_len))

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

#define N 200000 + 5

using namespace std;

int a[10][10];

int main(){
	int n, p, q, j, k, ans;
	scanf("%d", &n);
	ans = 0;
	j = 1;
	k = 10;
	for(int i = 1; i <= n; ++i){
		if(i == k){
			j = k;
			k *= 10;
		}
		p = i / j;
		q = i % 10;
		a[p][q]++;
	} 
	for(int i = 1; i < 10; ++i)
		for(int j = 1; j < 10; ++j)
			ans += a[i][j] * a[j][i]; 
	printf("%d", ans);
	return 0;
} 

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;
const int MOD = 1000000007;

const int max_a = 20005;

int main(){
    int H, N; cin >> H >> N;
    vector<int> A(N), B(N);
    rep(i,N) cin >> A[i] >> B[i];

    vector<ll> dp(max_a+1, INF);
    dp[0] = 0;

    rep(i,N){
        rep(j, max_a+1){
            if (j + A[i] > max_a) break;
            dp[j+A[i]] = min(dp[j+A[i]], dp[j]+B[i]);
        }        
    }

    ll ans = INF;
    for (int i = H; i <= max_a; i++){
        ans = min(ans, dp[i]);
    }
    
    cout << ans << endl;

}


Measured memory_bytes: 3640