akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)
typedef int long long ll;
using namespace std;

int main(){
    string s;
    cin>>s;
    for(int i=1;i<=s.size()-2;i++){
        int ssize=s.size()-i;
        string ss=s.substr(0,s.size()-i);
        
        if(ssize%2==0){
            string t1=ss.substr(0,ssize/2);
            string t2=ss.substr(ssize/2,ssize/2);
          //  cout<<t1<<" "<<t2<<endl;
            if(t1==t2){
                cout<<ss.size()<<endl;return 0;
            }
        }
        /*else{
            string t1=ss.substr(0,ss.size()/2);
            string t2=ss.substr(ss.size()/2,ss.size()/2);
            if(t1==t2){
                cout<<ss.size()<<endl;
                return 0;
            }
        }*/
        
    }
    
    
    
    
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

vector <int> g[200005], vert[5];
int perm[200005], col[5];

void dfs(int v, int pr, int h)
{
	col[h]++;
	vert[h].pb(v);
	for (int i = 0; i < (int) g[v].size(); i++)
	{
	 	int u = g[v][i];
	 	if (u == pr) continue;
	 	dfs(u, v, h ^ 1);
	}
	return;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	int n;
 	cin >> n;
 	for (int i = 1; i < n; i++)
 	{
 	 	int u, v;
 	 	cin >> u >> v;
 	 	g[u].pb(v), g[v].pb(u);
 	}

 	dfs(1, -1, 0);

 	if (col[1] >= col[0]) swap(col[0], col[1]), swap(vert[0], vert[1]);
 	if (col[0] >= n - n / 3)
 	{
 		vector <int> spis1, spis2;
 		for (int i = 1; i <= n; i++) if (i % 3 != 0) spis1.pb(i);
 		for (int i = 1; i <= n; i++) if (i % 3 == 0) spis1.pb(i);
 		for (int i = 0; i < (int) vert[0].size(); i++) spis2.pb(vert[0][i]);
 		for (int i = 0; i < (int) vert[1].size(); i++) spis2.pb(vert[1][i]);

 		for (int i = 0; i < n; i++) perm[spis2[i]] = spis1[i];
 	}        
 	else
 	{
 		vector <int> spis1, spis2;
 		for (int i = 1; i <= n; i++) if (i % 3 == 1) spis1.pb(i);
 		for (int i = 1; i <= n; i++) if (i % 3 == 0) spis1.pb(i);
 		for (int i = 1; i <= n; i++) if (i % 3 == 2) spis1.pb(i);
 		for (int i = 0; i < (int) vert[0].size(); i++) spis2.pb(vert[0][i]);
 		for (int i = 0; i < (int) vert[1].size(); i++) spis2.pb(vert[1][i]);

 		for (int i = 0; i < n; i++) perm[spis2[i]] = spis1[i];
   	}


	for (int i = 1; i <= n; i++) cout << perm[i] << ' ';
	cout << '\n';
 	return 0;
}

Measured memory_bytes: 22000
#include <stdio.h>
int main(void){
int i=0;
int a;
int y=0,z=0;
for(;~scanf("%d",&a);)i++?a%2?z--:a%4?y++:z++:0;
puts((!y&&z>-2||y&&z+1)?"Yes":"No");
}

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

int main() {
    int N, W;
    cin >> N >> W;
    vector<pair<int, int>> A(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> A.at(i).first >> A.at(i).second;
    }

    vector<vector<long long>> dp(N + 1, vector<long long>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            if (A.at(i).first > j) {
                dp.at(i).at(j) = dp.at(i - 1).at(j);
            }
            else {
                dp.at(i).at(j) = max(dp.at(i - 1).at(j - A.at(i).first) + A.at(i).second, dp.at(i - 1).at(j));
            }
        }
    }

    cout << dp.at(N).at(W) << endl;
}

Measured memory_bytes: 80256
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0]);
    const S = arg.slice(1, N + 1).sort();
  
	let map = {};
	let max = 0;
  
	for(let i in S) {
    	if(map[S[i]]) {
        	map[S[i]]++;
        } else {
        	map[S[i]] = 1;
        }
      
      	max = Math.max(max, map[S[i]]);
    }
    
    let answer = [];
  
	for(let key in map) {
        if(map[key] === max) {
            answer.push(key);
        }
    }
    
    console.log(answer.join("\n"));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

using namespace std;

using ll = long long;

int Color(int r) {
    if (r < 400) return 0;
    else if (r < 800) return 1;
    else if (r < 1200) return 2;
    else if (r < 1600) return 3;
    else if (r < 2000) return 4;
    else if (r < 2400) return 5;
    else if (r < 2800) return 6;
    else if (r < 3200) return 7;
    else return 8;
}

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

    int n;
    cin >> n;

    array<int, 9> c;
    fill(c.begin(), c.end(), 0);
    for (int i = 0, a; i < n; ++i) {
        cin >> a;
        ++c[Color(a)];
    }

    int cnt = count_if(c.begin(), c.end() - 1, [](int x) { return 0 < x; });
    cout << (cnt == 0 ? 1 : cnt) << ' ' << cnt + c[8] << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <functional>
#include <array>

using namespace std;

int main(){
    int64_t N, M, P;
    while(true){
        cin >> N >> M >> P;
        if(N == 0 && M == 0 && P == 0) break;
        vector<int64_t> vec(N);
        int64_t sum = 0;
        for(int i = 0; i < N; ++i){
            cin >> vec[i];
            sum += vec[i];
        }
        int64_t po = sum * (100 - P);
        if(vec[M-1] == 0){
            cout << 0 << endl;
        } else {
            cout << po / vec[M-1] << endl;
        }
    }
}


Measured memory_bytes: 3012
#include<stdio.h>

int main(){

  int x,y,d;

  scanf("%d%d",&x,&y);

  if(x >= y){

    d = x % y;
    
    while(d!=0){
      
      x = y;
      y = d;
      d = x % y;
    }
    printf("%d\n",y);
  }

  else{
    
    d = y % x;

    while(d!=0){
      
      y = x;
      x = d;
      d = y % x;
    }
    printf("%d\n",x);
  }

  return 0;
}



Measured memory_bytes: 2124
package main

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

func insertionSort(a []int, n int, g int) ([]int, int) {
	cnt := 0
	for i := g; i < n; i++ {
		v := a[i]
		j := i -g
		for j >= 0 && a[j] > v {
			a[j+g] = a[j]
			j = j - g
			cnt++
		}
		a[j+g] = v
	}
	return a, cnt
}

func shellSort(a []int, n int) ([]int, []int, int) {
	cnt, tmp := 0, 0
	var g []int
	for h := 1; h <= n; h = 3*h+1 {
		g = append(g, 0)
		copy(g[1:], g[0:])
		g[0] = h
	}
	for i := 0; i < len(g); i++ {
		a, tmp = insertionSort(a, n, g[i])
		cnt += tmp
	}
	return a, g, cnt
}

func String(A []int) string {
	return strings.Trim(fmt.Sprint(A), "[]")
}

func Stringln(A []int) string {
	text := strings.Trim(fmt.Sprint(A), "[]")
	return strings.Replace(text, " ", "\n", -1)
}

func main() {
	n := 0
	scanner := bufio.NewScanner(os.Stdin)
	if scanner.Scan() {
		n, _ = strconv.Atoi(scanner.Text())
	}
	a := make([]int, n)
	for i := range a {
		if !scanner.Scan() {
			break
		}
		a[i], _ = strconv.Atoi(scanner.Text())
	}
		g, count := []int{}, 0
		a, g, count = shellSort(a, n)
		fmt.Println(len(g))
		fmt.Println(String(g))
		fmt.Println(count)
		fmt.Println(Stringln(a))
}


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

using namespace std;

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

    bool ret = true;
    for (int i = 1; i < n; i++) {
        int tmp;
        cin >> tmp;
        if (tmp < ma - 1)ret = false;
        ma = max(ma, tmp);
    }

    cout << (ret ? "Yes" : "No") << endl;
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n)   FOR(i,0,n)
#define RREP(i,n)   RFOR(i,0,n)
#define SORT(s) sort(s.begin(), s.end())
#define P pair<int, int>
#define mp make_pair
using namespace std;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {if (v.empty()) {ostr << "{ }"; return ostr;}
    ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) {ostr << ", " << *itr;}
    ostr << "}";
    return ostr;}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

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

vector<int> uniq(vector<int> vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return vec;}

vector<ll> divisor(ll n) {
vector<ll> ret;
for(int64_t i = 1; i * i <= n; i++) {
  if(n % i == 0) {
    ret.push_back(i);
    if(i * i != n) ret.push_back(n / i);
  }
}
  sort(begin(ret), end(ret));
  return (ret);
}
void permu(int n){
  vector<int> perm(n);
  REP(i, n) perm[i] = i;
do{
  cout << perm  << endl;
}
while (next_permutation(perm.begin(), perm.end()));
return;}

vector<pair<ll, int>> prime_div(ll n){
  vector<pair<ll, int>> res;
  for (ll i=2; i*i <= n;i++){
    if (n%i == 0){
      int a = 0;
      while(n%i == 0){
        n /= i;
        a++;
      }
      pair<ll, int> tmp;
      tmp.first = i;
      tmp.second = a;
      res.push_back(tmp);
    }
  }
  if (n != 1){
    pair<ll, int> now;
    now.first = n;
    now.second = 1;
    res.push_back(now);}
  return res;
}


// printf("%.10f\n" , ans);
int main(void){
  ios::sync_with_stdio(false);
  int k, n;
  cin >> k >> n;
  vector<int> a(n);
  REP(i, n) cin >> a[i];
  int tmp;
  tmp = k + a[0];
  a.push_back(tmp);
  int total = 0;
  vector<int> diff(n);
  REP(i, n){
    diff[i] = a[i+1] - a[i];
    total += diff[i];
  }
  sort(diff.rbegin(), diff.rend());
  int ans = total - diff[0];
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 4852
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;

/* short */
#define pb push_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)

/* REPmacro */
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOREACH(x, a) for(auto x : a)

/* exchange */
#define CHMIN(a, b) (a) = min((ll)(a), (ll)(b))
#define CHMAX(a, b) (a) = max((ll)(a), (ll)(b))

/* function */
#define IN(x) cin >> x
#define DEBUG(x) cerr << (x) << " "
#define LN() cerr << "\n"
#define PRINT(x) cout << (x) << endl
#define BR cout << endl

/* const */
const int ARRAY = 100005;
const int INF = 1001001001; // 10^9
const ll LINF = 1001001001001001001; // 10^18
const int MOD = 1e9 + 7;

ll N = 0;
ll K = 0;
ll t;
ll ret = 0;
string s;
ll M;

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

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

int main(void){
  IN(N);
  IN(M);
  vl a(N);
  REP(i, N) {
    IN(t);
    a[i] = t >> 1;
  }
  ll L = 1;
  vl cnt(N, 0);

  REP(i, N) {
    while(!(a[i] >> (cnt[i]) & 1)) {
      cnt[i]++;
    }
  }
  if (count(ALL(cnt), cnt[0]) != N) {
    PRINT(0);
    return 0;
  }

  L = 1;
  REP(i, N) {
    L = lcm(L, a[i]);
  }

  // DEBUG(L);
  ret = M/L - M/(2*L);
  
  PRINT(ret);
}


Measured memory_bytes: 1792
#include<stdio.h>
int main() {
  int i, m, n, a, b, c;
  scanf("%d", &m);
  for (i = 0; i < m; i ++) {
    scanf("%d %d %d", &a, &b, &c);
    if (a >= b && a >= c) {
      n = a * a - b * b - c * c;
     } else if (b >= a && b >= c) {
      n = b * b - a * a - c * c;
     } else {
      n = c * c - a * a - b * b;
     }
     if (n) printf("NO\n"); else printf("YES\n");
  }
  return 0;
}

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

int main() {
	char s;
	cin >> s;
		if(s == 'A'){
			cout << "T";
		}else if(s == 'T'){
			cout << "A";
		}else if(s == 'C'){
			cout << "G";
		}else if(s == 'G'){
			cout << "C";
		}
	
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <map>
#include <set>
#include <list>
#include <deque>
#include <queue>
#include <stack>
#include <forward_list>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <bitset>
#include <memory>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <cstdint>

using namespace std;

set<int> prime;

void calc_prime(int mm) {
    int cur = 2;
    while(cur <= mm) {
        for(auto itr = prime.begin();itr != prime.end();itr++) {
            if(cur % *itr == 0)
                goto not_prime;
        }
        prime.insert(cur);
    not_prime:
        cur++;
    }
}

int main(void) {
    int a,b;
    cin >> a >> b;
    if(a * b == 15)
        cout << "*" << endl;
    else if(a+b == 15)
        cout << "+" << endl;
    else
        cout << "x" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr long long LLINF = 1LL << 62;
constexpr double EPS = 1e-9;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
  }
} initializer;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (it != vec.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &pa) {
  return os << "(" << pa.first << ", " << pa.second << ")";
}

template<typename Tuple, size_t N>
struct TuplePrinter {
  static void print(const Tuple &t) {
    TuplePrinter<Tuple, N-1>::print(t);
    cout << ", " << get<N-1>(t);
  }
};

template<typename Tuple>
struct TuplePrinter<Tuple, 1> {
  static void print(const Tuple &t) {
    cout << get<0>(t);
  }
};

template<typename... T>
ostream &operator<<(ostream &os, const tuple<T...> &tup) {
  os << "(";
  TuplePrinter<decltype(tup), sizeof...(T)>::print(tup);
  return os << ")";
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &se) {
  os << "{";
  for (auto it = se.begin(); it != se.end(); ++it) {
    if (it != se.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &ma) {
  os << "{";
  for (auto it = ma.begin(); it != ma.end(); ++it) {
    if (it != ma.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  return os << "}";
}

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }


int main() {
  int n, m, k; cin>>n>>m>>k;
  vector<long long> a(n), b(m);
  rep(i, n) cin>>a[i];
  rep(i, m) cin>>b[i];
  rep(i, n-1) a[i+1] += a[i];
  rep(i, m-1) b[i+1] += b[i];

  int ans = upper_bound(b.begin(), b.end(), k) - b.begin();
  rep(i, n) {
    int cur = i+1;
    long long rem = k - a[i];
    if (rem < 0) continue;
    int pos = upper_bound(b.begin(), b.end(), rem) - b.begin();
    ans = max(ans, cur + pos);
  }
  print(ans);

  return 0;
}

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

namespace Practice
{
    class Program
    {
        const int WHITE = 0;
        const int GRAY = 1;
        const int BLACK = 2;
        static void Main(string[] args)
        {
            SolveA(args);
            //SolveB(args);
            //SolveC(args);
            //SolveD(args);


        }
        static void SolveA(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[,] m = new int[n, n];
            for(int i=0;i<n;++i)
            {
                string[] szarr = Console.ReadLine().Split(' ');
                //int u = int.Parse(szarr[0]);
                int k = int.Parse(szarr[1]);
                for(int j=0;j<k;++j)
                {
                    int v =int.Parse( szarr[j+ 2]);
                    int idx = v - 1;
                    m[i, idx] = 1;
                }
            }
            int[] color = new int[n];
            int[] d = new int[n];
            for(int i=0;i<d.Length;++i)
            {
                d[i] = -1;
            }
            var q = new Queue<int>();
            BFS(0, color, d, q, m);
            for (int i=0;i<n;++i)
            {
                string sz = string.Format("{0} {1}", i + 1, d[i]);
                Console.WriteLine(sz);
            }
        }
        static void BFS(int s, int[] color, int[] d, Queue<int> q, int[,] m)
        {
            color[s] = GRAY;
            d[s] = 0;
            q.Enqueue(s);
            while(q.Count >= 1)
            {
                int u = q.Dequeue();
                for(int v = 0;v<d.Length;++v)
                {
                    if(m[u,v] != 0 && color[v] == WHITE)
                    {
                        color[v] = GRAY;
                        d[v] = d[u] + 1;
                        q.Enqueue(v);
                    }
                }
                color[u] = BLACK;
            }
         }
        static int Next(int[,] m , int u, int[] color)
        {
            for(int i=0;i<m.GetLength(0);++i)
            {
                if(m[u,i] == 1 && color[i] == WHITE)
                {
                    return i;
                }
            }
            return -1;
        }
    }

}



Measured memory_bytes: 10100
n, k = map(int, input().split())
num = [0] * k
for i in range(1, n+1):
    num[i % k] += 1
ans = 0
for a in range(k):
    b = (k-a) % k
    c = (k-a) % k
    if ((b+c) % k != 0):
        continue
    ans += num[a] * num[b] * num[c]
print(ans)


Measured memory_bytes: 10268
s = STDIN.gets()

if s.length == 1
  puts "0"
  exit
end

def flip(a)
  if a == "0"
    return "1"
  else
    return "0"
  end
end

cnt = 0
before = "2"
s.each_char do |a|
  if a == before
    a = flip(a)
    cnt += 1
  end
  before = a
end

puts cnt


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

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, M; cin >> N >> M;
	int mi = 1, ma = N;
	for (int i = 0; i < M; i++) {
		int L, R; cin >> L >> R;
		mi = max(mi, L);
		ma = min(ma, R);
	}
	cout << max(0, ma - mi + 1) << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>


#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
// rep(i,1,10) is from 1 to 9 and rep(I,10,1) is from 9 to 1
#define repn(i,a,b)   for(int i=a;i>=b;i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define pf push_front
#define eb emplace_back //FASTER THAN PUSH BACK!
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define mi multiset<int>
#define mii multiset<pii>
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";

// #define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>


// using namespace __gnu_pbds;
using namespace std;

int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}

int modp(int a,int n)
{
    if(n==0) return 1;
    if(n==1) return a;
    int res=modp(a,n/2);
    if(n%2==0) return (res*res);
    else return (a*res*res);
}



void solve()
{
    int t,n,m,i,k,l,r,u,v,w,j,s,sum=0,pos=-1,flag=0,count=0;
    string S,T,U;
    int a,b;
    cin>>S;
    if(S=="ABC") cout<<"ARC";
    else cout<<"ABC";
}


signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3644
#include <iostream>

using namespace std;
using ll = long long;

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll ans = a * c;
  ans = max(ans, a * d);
  ans = max(ans, b * d);
  ans = max(ans, b * c);
  cout << ans << endl;
}


Measured memory_bytes: 3632
#include <cstdio>
#include <vector>

int n, m;
std::vector<int> g[8];
bool v[8];
int ans;

void check(){
	bool f = true;
	for(int i=0; i<n; ++i) f &= v[i];
	if(f) ++ans;
}

void dfs(int n){
	v[n] = true;
	check();
	for(int i=0; i<g[n].size(); ++i)
		if(!v[g[n][i]])
			dfs(g[n][i]);
	v[n] = false;
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; ++i){
		int a, b;
		scanf("%d %d", &a, &b);
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
	v[0] = true;
	for(int i=0; i<g[0].size(); ++i){
		dfs(g[0][i]);
	}
	printf("%d\n", ans);
}

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

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int k;
	cin >> k;
	vector<int> freq(k);
	for(int& x : freq) cin >> x;
	int minv = 1000000, maxv = -1;
	for(int x : freq){
		minv = min(minv, x); maxv = max(maxv, x);
	}
	int sum = 0;
	for(int x : freq) sum += x;
	if(minv * 2 < maxv){
		cout << -1 << '\n';
		return 0;
	}
	vector<int> ans;
	int maxworks = 0;
	while((int)ans.size() < sum){
		bool found = false;
		for(int nxt = 0; nxt < k; nxt++){
			vector<int> cans = ans;
			cans.push_back(nxt);
			int cmaxworks = maxworks;
			{
				if((int)cans.size() >= k){
					vector<int> d(k, 0);
					for(int i = 0; i < k; i++){
						d[cans[(int)cans.size() - 1 - i]]++;
					}
					bool works = true;
					for(int i = 0; i < k; i++) if(!d[i]) works = false;
					if(works) cmaxworks = (int)cans.size();
				}
			}
			vector<int> cfreq = freq;
			cfreq[nxt]--;
			if(cfreq[nxt] < 0) continue;
			vector<int> known;
			for(int f = cmaxworks; f < (int)cans.size(); f++) known.push_back(cans[f]);
			vector<int> zk = known;
			sort(zk.begin(), zk.end());
			if(unique(zk.begin(), zk.end()) != zk.end()) continue;
			bool ok = false;
			{
				vector<int> dfreq = cfreq;
				for(int i = 0; i < k; i++) dfreq[i]--;
				multiset<int> g;
				for(int f : dfreq) g.insert(f);
				if(*g.rbegin() <= 2 * *g.begin()) ok = true;
			reverse(known.begin(), known.end());
				for(int a : known){
					g.erase(g.find(dfreq[a]));
					dfreq[a]++;
					g.insert(dfreq[a]);
					if(*g.rbegin() <= 2 * *g.begin()) ok = true;
				}
			}
			{
				vector<int> dfreq = cfreq;
				for(int i = 0; i < k; i++) dfreq[i]--;
				for(int a : known){
					dfreq[a]++;
				}
				multiset<int> g;
				for(int f : dfreq) g.insert(f);
				vector<int> cur(k, 0);
				for(int a : known) cur[a] = 1;
				for(int b = cmaxworks - 1; b >= 0; b--){
					if(cur[cans[b]]) break;
					cur[cans[b]] = 1;
					int a = cans[b];
					g.erase(g.find(dfreq[a]));
					dfreq[a]++;
					g.insert(dfreq[a]);
					if(*g.rbegin() <= 2 * *g.begin()) ok = true;
				}
			}
			{
				vector<int> dfreq = cfreq;
				for(int i = 0; i < k; i++) dfreq[i]--;
				vector<int> cur(k, 0);
				for(int a : known) cur[a] = 1;
				int minval = 1000000;
				for(int b : dfreq) minval = min(minval, b);
				for(int i = 0; i < k; i++){
					if(cur[i]) continue;
					if(dfreq[i] > 2 * minval){
						dfreq[i]--;
						cur[i]--;
					}
				}
				int ming = 100000, maxg = 0;
				for(int b : dfreq) ming = min(ming, b);
				for(int b : dfreq) maxg = max(maxg, b);
				if(ming * 2 >= maxg){
					ok = true;
				}
			}
			if(ok){
				ans.push_back(nxt);
				maxworks = cmaxworks;
				found = true;
				freq[nxt]--;
				break;
			}
		}
		// for(int b : ans) cerr << b << ' ';
		// cerr << '\n';
		assert(found);
	}
	for(int b : ans) cout << b+1 << ' ';
	cout << '\n';
}

Measured memory_bytes: 3712
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MAX 2999
#define S Count
#define B b
#define W w
int n,k,B[MAX][MAX],W[MAX][MAX],K;
int Count(int opt,int x,int y,int xx,int yy)
{
	if(opt==1)
		return B[xx][yy]-B[xx][y-1]-B[x-1][yy]+B[x-1][y-1];
	return w[xx][yy]-W[xx][y-1]-W[x-1][yy]+W[x-1][y-1];
}
int read()
{
	int x;
	scanf("%d",&x);
	return x;
}
int main()
{
	n=read();k=read();K=2*k;
	for(int i=1;i<=n;++i)
	{
		int x=read()%K+1,y=read()%K+1,col=0;
		char ch[2];scanf("%s",ch);
		B[x][y]+=ch[0]=='B';W[x][y]+=ch[0]=='W'; 
	}
	for(int i=1;i<=k<<1;++i)
		for(int j=1;j<=k<<1;++j)
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1],
			w[i][j]+=w[i-1][j]+w[i][j-1]-w[i-1][j-1];
	int ans=0,res=0;
	for(int x=1;x<=k;++x)
		for(int y=1,b,w;y<=k;++y)
			b=1,w=2,res=S(b,1,1,x,y)+S(b,x+k+1,1,K,y)+S(b,x+k+1,y+k+1,K,K)+S(b,1,y+k+1,x,K)+S(b,x+1,y+1,x+k,y+k)+S(w,x+1,1,x+k,y)+S(w,x+k+1,y+1,K,y+k)+S(w,x+1,y+k+1,x+k,K)+S(w,1,y+1,x,y+k),ans=max(ans,res),res=S(w,1,1,x,y)+S(w,x+k+1,1,K,y)+S(w,x+k+1,y+k+1,K,K)+S(w,1,y+k+1,x,K)+S(w,x+1,y+1,x+k,y+k)+S(b,x+1,1,x+k,y)+S(b,x+k+1,y+1,K,y+k)+S(b,x+1,y+k+1,x+k,K)+S(b,1,y+1,x,y+k),ans=max(ans,res);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 49408
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL unsigned long long 
using namespace std;

const int maxx=1e6+10;
const int mod=998244353;
LL num[maxx],n,x,la;
LL ans=1;

LL qp(LL a,LL b){
	LL res=1;
	a=a%mod;
	while(b){
		if(b&1) res=(res*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return res;
}

int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		if(i==1&&x){printf("0"); return 0;}
		if(i!=1&&x==0){printf("0");return 0;} 
		la=max(la,x);num[x]++;
	} 
	for(int i=1;i<=la;i++){
		ans*=qp(num[i],num[i+1]);
		ans%=mod;
	}
	ans%=mod;
	printf("%lld",ans);
	return 0;
}
 


Measured memory_bytes: 896
#include<stdio.h>
long long int n, a[100100],m,r;
int main(){
	int i;
	scanf("%lld",&n);
	scanf("%lld",&a[0]);
	m=2;
	r=a[0]-1;
	for(i=1;i<n;i++){
		scanf("%lld", a+i);
		if(m == a[i]){
			m++;
		}else if(a[i]>m){
			r=r+(a[i]-1)/m;
		}
	}
	printf("%lld",r);
}

Measured memory_bytes: 896
package main

import "fmt"

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

func main() {
	var x, a, b int
	fmt.Scan(&x, &a, &b)

	if abs(x-a) < abs(x-b) {
		fmt.Println("A")
	} else {
		fmt.Println("B")
	}
}


Measured memory_bytes: 512
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here! 
        Scanner sc = new Scanner(System.in);
        int start = sc.nextInt();
        int goal = sc.nextInt();
        
        if (start == goal) {
            System.out.println(0);
            return;
        }
        if (start * -1 == goal) {
            System.out.println(1);
            return;
        }
        
        if (start == 0) {
            if (start < goal) {
                System.out.println(goal - start);
            } else {
                System.out.println(start - goal + 1);
            }
            return;
        }
        if (goal == 0) {
            if (start < goal) {
                System.out.println(goal - start);
            } else {
                System.out.println(start - goal + 1);
            }
            return;
        }
        
        int count = 0;
        if (start < 0) {
            if (goal < 0) {
                if (start < goal) {
                    count = goal - start;
                } else {
                    count = start - goal + 2;
                }
            } else {
                start *= -1;
                count++;
                if (start < goal) {
                    count += goal - start;
                } else {
                    count += start - goal;
                }
            }
        } else {
            if (goal < 0) {
                goal *= -1;
                count++;
                if (start < goal) {
                    count += goal - start;
                } else {
                    count += start - goal;
                }
            } else {
                if (start < goal) {
                    count = goal - start;
                } else {
                    count = start - goal + 2;
                }
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 35688
fun main(args: Array<String>) {
    agc003b()
}

fun agc003b() {
    val n = readLine()!!.toInt()
    val aList = (1..n).map { readLine()!!.toLong() }.toLongArray()

    var answer = 0L

    var before = 0L
    for (a in aList) {
        val curr = before + a
        answer += curr / 2
        before = if (a > 0) curr % 2 else 0
    }

    println(answer)
}


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

#define N 100000
#define mod_32(n) (n&((1<<5)-1))
int prime[(N>>5)+1];
 
void init(){
	memset(prime,-1,sizeof(prime));
	prime[0] = prime[0] - (1<<0) - (1<<1);
	for(int i=2;i*i <= N;i++){
		if( prime[i>>5] & (1 << mod_32(i)) ){
			for(int j=i*i;j<=N;j+=i){
				prime[j>>5] -= (prime[j>>5] & (1<<mod_32(j)));
			}
		}
	}
}
inline bool isprime(int n){
	return !!(prime[n>>5] & (1<<mod_32(n)));
}


int main(){
	init();
	vector<long long> p;
	for(int i = 2 ; i <= 100000 ; i++){
		if( isprime(i) ){
			p.push_back(i);
		}
	}
	long long m,a,b;
	while(scanf("%lld%lld%lld",&m,&a,&b) && m ){
		long long ans = 0;
		long long A = 0;
		
		for(int i = 0 ; i < p.size() ; i++){
			//cout << i << " " << m << " " << p[i] << endl;
			int j = upper_bound(p.begin()+i,p.end(),m/p[i]) - p.begin();
			j = upper_bound(p.begin()+i,p.begin()+j,p[i]*b/a) - p.begin() - 1;
			if( j < i ) continue;
			//cout << p[i] << " " << p[j] << endl;
			//cout << "OK" << p[i] << " " << p[j] << " " << 1.0 * p[i] / p[j] << endl;
			if( p[i] * p[j] > m ) continue;
			if( p[i] * p[j] <= m && a*p[j] <= p[i]*b){
				if( p[i]*p[j] > ans ){
					ans = p[i]*p[j];
					A = p[i];
				}
			}
		}
		cout << A << " " << ans / A << endl;
	}
	
}

Measured memory_bytes: 1372
s = input()
ok = True
if s.count("N") >= 1:
    if s.count("S") == 0:
        ok = False
if s.count("S") >= 1:
    if s.count("N") == 0:
        ok = False

if s.count("E") >= 1:
    if s.count("W") == 0:
        ok = False

if s.count("W") >= 1:
    if s.count("E") == 0:
        ok = False
if ok:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
pub fn main() {
    use std::io::Read;
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    
    let a: u64 = iter.next().unwrap().parse().unwrap();
    let b: u64 = iter.next().unwrap().parse().unwrap();

    let ret = a/2%2 ^ (if (a-1)%2==0 {a-1} else {0}) ^ (b+1)/2%2 ^ (if b%2==0 {b} else {0});
    println!("{}", ret);
}


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

int main() {
  int A, B, C, D;
  
  cin >> A >> B >> C >> D;
  
  if (A+B > C+D){
    cout << "Left" << endl;
  }
  else if (A+B < C+D){
    cout << "Right" << endl;
  }
  else {
    cout << "Balanced" << endl;
  }

}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(void)
{
  int a,b,c; cin>>a>>b>>c;
  
  if((a==b)&&(b!=c)){puts("Yes");}
  else if((a==c)&&(c!=b)){puts("Yes");}
  else if((b==c)&&(c!=a)){puts("Yes");}
  else{puts("No");}
  
  return 0;
}


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


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int x,y;
    cin>>x>>y;
    bool check = false;
    for(int i=1;i<=x;++i){
        int left = x - i;
        if(2*i + 4*left ==y || 4*i + 2*left ==y) check = true;
    }
    cout<<(check? "Yes" : "No");
    return 0;
}


Measured memory_bytes: 3660
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

#setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	s = int(rl())

	def binom_tables(n, q):
		fact = [1 for _ in range(n + 1)]
		inv = [1 for _ in range(n + 1)]
		for i in range(1, n+1):
			fact[i] = (fact[i-1] * i) % q
			inv[i] = pow(fact[i], q-2, q)
		return fact, inv

	F, I = binom_tables(s + 700, MOD)

	def binom(n, k, q):
		return (F[n]*((I[k]*I[n-k])%q))%q

	ans = 0
	for r in range(1, 700):
		objects = s - 3*r
		if objects + r - 1 < objects or objects < 0: 
			break
		x = binom(objects + r - 1, objects, MOD)
		ans += x
		ans %= MOD 

	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Measured memory_bytes: 70408
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    def merge(self,a,b): return self.ptr.merge(a,b)
    def same(self,a,b): return self.ptr.same(a,b)
    def leader(self,a): return self.ptr.leader(a)
    def size(self,a): return self.ptr.size(a)
    def groups(self): return self.ptr.groups()
"""
import os
try:
    from dsu import *
except:
    open('dsu.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b dsu.pyx')

N,Q=map(int,input().split())
TUV=[list(map(int,input().split())) for i in range(Q)]
d=dsu_(N)
for t,u,v in TUV:
    if t==0:
        d.merge(u,v)
    else:
        print(1 if d.same(u,v) else 0)

Measured memory_bytes: 46352
#include <bits/stdc++.h>
#define int int64_t
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define REPP(i, n) for (int i = 1; (i) < (int)(n+1); ++ (i))
#define REPR(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i=(m)-1; i>=(n); i--)
#define ALL(v) v.begin(), v.end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define SORTR(c) sort((c).begin(),(c).end(),greater<int>());
#define BIT(n) (1LL<<(n))
#define PCNT(x) __builtin_popcountll(x)
#define GCD(x,y) __gcd(x,y)
#define LCM(x,y) x/__gcd(x,y)*y
#define PB push_back
#define MP make_pair
#define endl "\n"
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
using namespace std;
using Graph = vector<vector<int> >;
using WeightedGraph = vector<vector<pair<int, int> > >;
typedef long double LD;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
const int INF = 2000000000;
const long double PI = acosl(-1);
const int MOD = 1000000007;
void print() {cout << endl;}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head; if (sizeof...(tail) != 0) cout << " ";print(forward<Tail>(tail)...);}
template <class T> void print(vector<T> &vec) {for (auto& a : vec) {cout << a; if (&a != &vec.back()) cout << " ";} cout << endl;}
template <class T> void print(vector<vector<T>> &df) { for (auto& vec : df) { print(vec);}}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int ans = 0;
    
    int N, X, T;
    cin >> N >> X >> T;
    ans = ceil((LD)N/X);
    ans *= T;
    cout << ans << endl;
    
    
    
    return 0;
}

/*
cd ~/Desktop/Programming/AtCoder/contest/abc176/abc176_a && sh shellscripts/test_cpp.sh
cd ~/Desktop/Programming/AtCoder/contest/abc176/abc176_a && sh shellscripts/etest_cpp.sh
cd ~/Desktop/Programming/AtCoder/contest/abc176/abc176_a && sh shellscripts/submit_cpp.sh
*/


Measured memory_bytes: 3580
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


int main() {

    int n; cin >> n;
    vector<int> b(n);
    vector<int> ans;
    vector<int>::iterator it;

    rep(i,n) cin >> b[i];

    it = ans.begin();

    rep(i,n){
        if(b[i] > ans.size()+1){
            cout << -1;
            return 0;
        }else{
            ans.insert(ans.begin()+b[i]-1,b[i]);
        }
    }

    rep(i,ans.size()){
        cout << ans[i] << endl;
    }


    return 0;
}


Measured memory_bytes: 3628
from collections import deque
from bisect import bisect_left as bl
N = int(input())
A = [int(input()) for i in range(N)]

de = deque([])
de.append(A[0])
for a in A[1:]:
    ind = bl(de, a)
    if ind == 0:
        de.appendleft(a)
    else:
        de[ind-1] = a

print(len(de))

Measured memory_bytes: 54488
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define crap ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define assign(x,val) memset(x,val,sizeof(x))
const ll mod=1e9+7;
void solve(){
    int w,a,b;cin>>w>>a>>b;
    int x,y;
    x=min(a,b);
    y=max(a,b);
    if(x+w>=y){
    cout<<0;return;}
    cout<<y-(x+w);
}
int main() {
    crap;
	int t=1;
	//cin>>t;
	while(t--){
	    solve();
	}
	return 0;
}

Measured memory_bytes: 892
import java.util.Scanner;
import java.lang.String;

public class Main {

    public static void main(String[] args) {
        int A1;
        int num = 0;
        Scanner scan = new Scanner(System.in);
        String S = scan.nextLine();
        A1 = S.length();
        for(int i=0; i<(A1/2); i++){
            if(S.charAt(i) != S.charAt(A1-i-1)){
                num++;
            }
        }
        System.out.println(num);
    }
}

Measured memory_bytes: 22740
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <list>
#include <utility>
using namespace std;
#define MS0(I) memset(I, 0, sizeof(I));
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, s, n) for(int i = (s); i < (n); ++i)
#define MAX 100000
typedef long long LL;
typedef unsigned long long ULL;
int main(void){	
    int n,a,b; scanf("%d %d %d", &n, &a, &b);
    int ret;
    printf("%d", ret = n*a > b ? b : n*a);
    return 0;
} 


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

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n); for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
typedef pair<int, int> P;
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

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;
}
ll kaijo(ll x){
  ll z=1;
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i <=n;i++){
    num*=yakusu[i];
  }
  return num;
}


//cout<<""<<endl;
int main(){
  ll N,K;cin>>N>>K;vl a(N);
  rep(i,N){
    cin>>a[i];
  }

  ll ans=100000000000;
  for(int tmp ; tmp<(1<<(N-1));tmp++){
    bitset<14> s(tmp);
    ll cnt=0;
    ll ok=1;
    ll ma=a[0];
    if(N==1)ans=0;
    else{
      for(int i=0;i<N-1;i++){
      if(a[i+1]>ma)ok++;
      if(s.test(i)){
        if(ma<a[i+1])ma=a[i+1];
        else{
          cnt+=-a[i+1]+ma+1;
          ma++;ok++;
        }
      }
      else ma =max(ma,a[i+1]); 
    }
    if(ok>=K)ans=min(ans,cnt);
  
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;int n,x,tot;bitset<4000010> bs;
int main(){cin>>n,bs[0]=1;while(n--){cin>>x;tot+=x;bs|=(bs<<x);}for(int i=(tot+1)/2;;i++){if(bs[i]==1){cout<<i<<endl;return 0;}}return 0;}


Measured memory_bytes: 1664
import java.math.*;
import java.io.*;
import java.util.*;

public class Main {

	public static long func(int wt[] , int val[] , int k , int n)
	{
		long dp[][] = new long[n+1][k+1];
		for(int i = 0; i <= n; i++)
		{
			dp[i][0] = 0;
		}
		for(int i = 1; i <= k; i++)
		{
			dp[0][i] = 0;
		}
		for(int i = 1; i<= n; i++)
		{
			for(int j = 1; j <= k; j++)
			{
				if(wt[i - 1] > j)
				{
					dp[i][j] = dp[i-1][j];
				}
				else
				{
					dp[i][j] = Math.max((long)val[i - 1] + (long)dp[i - 1][j - wt[i - 1]] , dp[i-1][j]);
				}
			}
		}
		return dp[n][k];
	}

	public static void main(String[] args) throws Exception
	{
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int k = sc.nextInt();
    	int wt[] = new int[n];
    	int val[] = new int[n];
    	for(int i = 0 ; i < n ; i++)
    	{
    		wt[i] = sc.nextInt();
    		val[i] = sc.nextInt();
    	}

    	System.out.println(func(wt , val , k , n));
    }

}




Measured memory_bytes: 127572
#include<bits/stdc++.h>
using namespace std;
#define ll long long
main()
{
    int a,b,c;
    ll k;
    scanf("%d%d%d%lld",&a,&b,&c,&k);
    int ans=a-b;
    if(k%2==1)ans*=-1;
    printf("%d\n",ans);
    return 0;
}



Measured memory_bytes: 764
#include <iostream>

using namespace std;

long long gcm(long long a, long long b) {
    if (a < b) {
        long long w = a;
        a = b;
        b = w;
    }

    while (b != 0) {
        long w = a % b;
        a = b;
        b = w;
    }

    return a;
}

long long lcm(long long a, long long b) {
    return a / gcm(a, b) * b;
}

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;

    long long cnt_c = ((b - b % c) - (a % c == 0 ? a : (a - a % c + c))) / c + 1;
    long long cnt_d = ((b - b % d) - (a % d == 0 ? a : (a - a % d + d))) / d + 1;

    long long cd = lcm(c, d);
    long long cnt_cd = ((b - b % cd) - (a % cd == 0 ? a : (a - a % cd + cd))) / cd + 1;

    cout << (b - a + 1) - (cnt_c + cnt_d - cnt_cd) << endl;
}


Measured memory_bytes: 256
import math
MOD = 10 ** 9 + 7

N = int(input())

prime_list = [2]
for i in range(2, N + 1):
    if all(i % j != 0 for j in range(2, math.ceil(math.sqrt(i)) + 1)):
        prime_list.append(i)

d = {}
for prime in prime_list:
    d[prime] = 0


for i in range(2, N + 1):
    num = i
    for prime in prime_list:
        if num % prime == 0:
            while True:
                d[prime] += 1
                num /= prime
                if num % prime != 0:
                    break 

ans = 1
for key in d.keys():
        ans *= (d[key] + 1)
        ans %= MOD
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>

int main(void){
        int n;
        scanf("%d",&n);
        int a[100010];
        for(int i=0;i<=100000;++i) a[i]=0;
        for(int i=0;i<n;++i){
                int l,r;
                scanf("%d %d",&l,&r);
                a[l]++;
                a[r+1]--;
        }
        for(int i=1;i<=100000;++i){
                a[i]+=a[i-1];
        }
        int ans=0;
        for(int i=0;i<=100000;++i){
                if(a[i]>0) ans++;
        }
        printf("%d",ans);
        return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 1000000000000000000;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}
 
ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}
 
ll RS(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P < 0) {
        return 0;
    }
    if(P%2==0){
        ll t = RS(N, P/2, M);
        return t*t % M;
    }
    return N * RS(N, P-1, M) % M;
}

ll fac[4000010], finv[4000010], inv[4000010];

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 4000010; i++)
    {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll solve(ll a,ll b) {
    ll cnt = mod(a * COM(a + b + 2,b) % MOD + 2 * COM(a + b + 2,b) - b - 1);
    return cnt * inv[b + 1] % MOD; 
}

int main() {
    ll r1,c1,r2,c2;
    cin >> r1 >> c1 >> r2 >> c2;
    COMinit();
    cout << mod(solve(r2,c2) + solve(r1 - 1,c1 - 1) - solve(r1 - 1,c2) - solve(r2,c1 - 1)) << endl;
}

Measured memory_bytes: 93952
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

const int mod = 1e9 + 7;
void add_self (int & a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}
int mul (int a, int b) {
	return (ll) a * b % mod;
}

const int mx = 1e5 + 10;
vector < int > adj[mx];
int dp[mx][2];

void dfs (int u, int p = -1) {
	dp[u][0] = dp[u][1] = 1;
	for (int v : adj[u]) {
		if (v != p) {
			dfs (v, u);
			dp[u][1] = mul (dp[u][1], dp[v][0]);
			int x = dp[v][0]; add_self (x, dp[v][1]);
			dp[u][0] = mul (dp[u][0], x);
		}
	}
}

int main() {
	int n; scanf ("%d", &n);
	for (int i = 1; i < n; i++) {
		int x, y; scanf ("%d%d",&x,&y);
		--x, --y;
		adj[x].push_back (y);
		adj[y].push_back (x);
	}
	dfs (0);
	int answer = dp[0][0];
	add_self (answer, dp[0][1]);
	printf ("%d\n", answer);
	return 0;
}



Measured memory_bytes: 13440
#include<bits/stdc++.h>
using namespace std;
int n,some=0;
long long res=1;
string s1, s2;
int main(){
  cin>>n>>s1>>s2;
  for(int i=0;i<n;i++){
    if(i==0){
      if(s1[i]==s2[i]){res*=3;some=1;}
      else{res*=6;i++;some=0;}
    }else{
      if(s1[i]==s2[i]){
        some==0 ? res*=1 : res*=2;
        some=1;
      }else{
        some==0 ? res*=3 : res*=2;
        i++;some=0;
      }
    }
  }
  printf("%lld",res%1000000007);
  return 0;
}

Measured memory_bytes: 256