akhauriyash/Code-Regression huggingface dataset:
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let h: usize = input();
    let _w: usize = input();
    let c: Vec<String> = (0..h).map(|_| input()).collect();
    for s in c {
        println!("{}", s);
        println!("{}", s);
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 100100100100100100;//10^17
const ll MOD = 1000000007;


ll combination(ll n, ll r){
    if(n < r) return 0;
    if(r == 0||r == n) return 1;
    else if(r == 1) return n;
    return (combination(n - 1, r - 1) + combination(n - 1, r));
}

bool checkKaibun(string str){
    string checkStr = str;
    reverse(checkStr.begin(), checkStr.end());
    if(str == checkStr) return true;
    else return false;
}

int keta(ll num){
    int digits = 0;
    while(num > 0){
        num /= 10;
        digits++;
    }
    return digits;
}


ll mpow(ll x, ll n){//繰り返し二乗法 計算量O(logN)
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans * x % MOD;
        x = x * x % MOD;
        n  = n >> 1;
    }
    return ans;
}

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



int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while(a >= 1 && c >= 1){
        c -= b;
        if(c < 1)break;
        a -= d; 
    }
    if(c < 1) cout << "Yes" << endl;
    else cout << "No" << endl;
} 

Measured memory_bytes: 3640
#include <stdio.h>		// standard input output
#include <iostream>		// input output stream, cin cout( console in console out)
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>		// input output manipulation

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

int main() {
  int N;
  cin >> N;
  int ans;
  for(int i = 1; i < 11; i++){
    if(i*1000 >= N){
      ans = i*1000 - N;
      break;
    }
  }
  cout << ans << endl; // 標準出力
}

Measured memory_bytes: 3636
import heapq
n,m = map(int,input().split())
ab = [[] for _ in range(m+1)]
for i in range(n):
  a,b = map(int,input().split())
  if a < m+1:
    ab[a].append(b)
lst = []
now = 0
ans = 0
heapq.heapify(lst)
for i in range(1,m+1):
  for j in ab[i]:
    heapq.heappush(lst,-j)
  #heapq.heapify(lst)
  if lst:
    ans -= heapq.heappop(lst)
print(ans)

Measured memory_bytes: 18492
#include <iostream>
#include <vector>
using namespace std;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
using ll = long long;

int N, M;
Graph G;
vector<int> us, vs;

bool rec(int v, int p, int target, ll &path) {
    if (v == target) {
        path = 0;
        return true;
    }
    for (auto e : G[v]) {
        if (e.first == p) continue;
        if (rec(e.first, v, target, path)) {
            path |= (1LL << e.second);
            return true;
        }
    }
    return false;
}

ll solve() {
    vector<ll> paths(M, 0);
    for (int i = 0; i < M; ++i) rec(us[i], -1, vs[i], paths[i]);
    ll res = 0;
    for (ll bit = 0; bit < (1<<M); ++bit) {
        ll val = 0; 
        for (int i = 0; i < M; ++i) if (bit & (1LL<<i)) val |= paths[i];
        ll remnum = N - 1 - __builtin_popcountl(val);
        if (__builtin_popcountl(bit) % 2 == 0) res += 1LL << remnum;
        else res -= 1LL<<remnum;
    }
    return res;
}

int main() {
    cin >> N;
    G.assign(N, vector<Edge>());
    for (int i = 0; i < N-1; ++i) {
        int x, y; cin >> x >> y; --x, --y;
        G[x].emplace_back(y, i);
        G[y].emplace_back(x, i);
    }
    cin >> M;
    us.resize(M), vs.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> us[i] >> vs[i];
        -- us[i], --vs[i];
    }
    cout << solve() <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
#define pq_pair_tB priority_queue <pair<ll,ll>, vector<pair<ll,ll> > , greater<pair<ll,ll> > > 
#define pq_pair_ts priority_queue <pair<ll,ll> > //第二成分の大きさが関係ない
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}


vector<ll> lst;
map<ll,ll> cnt;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N ;
    cin >> N;
    vector<ll> A;
    
    rep(i,N){
        ll inp; cin >> inp;
        A.pb(inp);
    }

    for(ll i = A.size()-2;i >= 0; i--){
        A[i] += A[i+1];
    }
    rep(i,N){
        lst.pb(A[i]);
        cnt[A[i]]++;
    }
    rmsame(lst);
    ll ans = 0;
    cnt[0]++;
    rep(i,lst.size()){
        ll num = cnt[lst[i]];
        ll ret = 0;
        if(num >= 2){
            ret = num * (num-1);
            ret /= 2;
        }
        ans += ret;
    }
    
    cout << ans << endl;
    
    
    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 15856
MOD = 998244353

def convolution(a, b):
    def butterfly(arr):
        n = len(arr)
        h = (n - 1).bit_length()
        sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,
                842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p] * now
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (l - r) % MOD
                now *= sum_e[(~s & -~s).bit_length() - 1]
                now %= MOD


    def butterfly_inv(arr):
        n = len(arr)
        h = (n - 1).bit_length()
        sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543,
                109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)
        for ph in range(1, h + 1)[::-1]:
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p]
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (MOD + l - r) * inow % MOD
                inow *= sum_ie[(~s & -~s).bit_length() - 1]
                inow %= MOD

    n = len(a)
    m = len(b)
    if not n or not m: return []
    if min(n, m) <= 50:
        if n < m:
            n, m = m, n
            a, b = b, a
        res = [0] * (n + m - 1)
        for i in range(n):
            for j in range(m):
                res[i + j] += a[i] * b[j]
                res[i + j] %= MOD
        return res
    z = 1 << (n + m - 2).bit_length()
    a += [0] * (z - n)
    b += [0] * (z - m)
    butterfly(a)
    butterfly(b)
    for i in range(z):
        a[i] *= b[i]
        a[i] %= MOD
    butterfly_inv(a)
    a = a[:n + m - 1]
    iz = pow(z, MOD - 2, MOD)
    for i in range(n + m - 1):
        a[i] *= iz
        a[i] %= MOD
    return a


def atcoder_practice2_f():
    import sys
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]

    print(*convolution(A, B))


if __name__ == "__main__":
    atcoder_practice2_f()


Measured memory_bytes: 196524
#include<iostream>
#include<algorithm>
#include <numeric>
using namespace std;

int main(){
	int n, p;

	while (cin >> n >> p, n + p){
		int a[1000] = { 0 };
		int i = 0;
		int b = p;

		while (true){
			if (b == 0){
				b = a[i];
				a[i] = 0;
			}
			else{
				b--;
				a[i]++;
			}
			if (a[i] == p){
				cout << i << endl;
				break;
			}
			i++;
			if (i == n) i = 0;

		}
	}
	return 0;
}

Measured memory_bytes: 1160
from itertools import combinations


def solve(N, Ss):
    caps = {c: set() for c in 'MARCH'}
    for s in Ss:
        caps.setdefault(s[0], set()).add(s)
    sum = 0
    for d in combinations('MARCH', 3):
        sum += len(caps[d[0]]) * len(caps[d[1]]) * len(caps[d[2]])
    return sum


if __name__ == "__main__":
    N = int(input())
    Ss = [input() for _ in range(N)]
    print(solve(N, Ss))


Measured memory_bytes: 15912
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
signed main(){
  init_io();
  ll n,ans=0,mb=10000000000000;
  bool all=true;
  cin >> n;
  vector<ll> a(n),b(n);
  vector<P> ab;
  for(int i=0;i<n;i++){
    cin >> a[i] >> b[i];
    ans += a[i];
    if(a[i]!=b[i]) all = false;
  }
  if(all){
    cout << "0\n";
    return 0;
  }
  for(int i=0;i<n;i++){
    if(a[i]>b[i]){
      mb = min(mb,b[i]);
    }
  }
  cout << ans - mb<<endl;
}


Measured memory_bytes: 640
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    s = S()
    m = II()
    ans = ["I", "L", "M", "U"]
    nu = 0
    stack = []
    bf = int(s[0])
    for num,si in enumerate(s):
        if si == "+":
            bf += int(s[num+1])
        elif si == "*":
            bf *= int(s[num + 1])
    if bf == m:
        nu += 1
    stack = []
    bf = 0
    for num, si in enumerate(s):
        if si == "*":
            s[num + 1] = int(s[num + 1]) * int(s[num - 1])
            s[num - 1] = 0
    for si in s:
        if si != "*" and si != "+":
            bf += int(si)
    if bf == m:
        nu += 2
    print(ans[nu])    

    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()



Measured memory_bytes: 8196
N=int(input())
S=input()

arr_init="ABCDEFGHIJKLMNOPQRSTUVWXYZ"
arr="ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ"

arr_new = arr[N:N+26]

print(''.join(list(map(lambda x:arr_new[arr_init.index(x)], S))))

Measured memory_bytes: 3060
#include <vector>
#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

vector<string> split(string &str, const char *delim){
	vector<string> result;
	int cutAt;
	while( (cutAt = str.find_first_of(delim)) != str.npos ){
		if(cutAt > 0){
			result.push_back(str.substr(0, cutAt));
		}
		str = str.substr(cutAt + 1);
	}
	if(str.length() > 0){
		result.push_back(str);
	}
	return result;
}

void reversepoland(string &exp){
	vector<string> token = split(exp," ");
	vector<double> resolveNumber;
	vector<string> resolveString;
	for(int i=0;i<token.size();i++){
		char *p=NULL;
		double d=strtod(token[i].c_str(),&p);
		if(p-token[i].c_str()==token[i].size()){
			resolveNumber.push_back(d);
			resolveString.push_back(token[i]);
		}else{
			double d2=resolveNumber[resolveNumber.size()-1],d1=resolveNumber[resolveNumber.size()-2];
			resolveNumber.pop_back(),resolveNumber.pop_back();
			string s2=resolveString[resolveString.size()-1],s1=resolveString[resolveString.size()-2];
			resolveString.pop_back(),resolveString.pop_back();
			double ret;
			if(token[i]=="+"){ret=d1+d2;}
			else if(token[i]=="-"){ret=d1-d2;}
			else if(token[i]=="*"){ret=d1*d2;}
			else if(token[i]=="/"){ret=d1/d2;}
			resolveNumber.push_back(ret);
			resolveString.push_back("("+s1+token[i]+s2+")"); 
		}
	}
	printf("%f\n",resolveNumber[0]);
}
int main(){for(string str;getline(cin,str);reversepoland(str));}

Measured memory_bytes: 0
import java.util.Scanner

object Main {


  def solve(sc: => Scanner): Unit = {
    println(if (sc.nextInt
      + sc.nextInt * 5
      + sc.nextInt * 10
      + sc.nextInt * 50
      + sc.nextInt * 100
      + sc.nextInt * 500
      >= 1000
    ) (1) else (0))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)

    solve(sc)
  }
}

Measured memory_bytes: 45092
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath> 
#define ll long long
using namespace std;
int main(){
	string str;
	int h,w;
	cin>>h>>w;
	for(int i=0;i<h;i++){
		cin>>str;
		cout<<str<<endl;
		cout<<str<<endl;
	}
		
	
	
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
int a[maxn],b[maxn];
int fac[32];

int main()
{
    int N,K;
    scanf("%d%d",&N,&K);
    ll res=0;
    for(int i=0;i<N;i++){
        scanf("%d%d",&a[i],&b[i]);
        if((a[i]|K)==K) res+=b[i];
    }
    for(int i=0;i<=30;i++)
        fac[i]=1<<i;
    for(int i=1;i<=30;i++){
        if(K&fac[i]){
            ll cnt=0;
            int tmp=(K^fac[i])|(fac[i]-1);//把当前位置为0，前面位不变，后面位全为1
            for(int j=0;j<N;j++)
                if((a[j]|tmp)==tmp) cnt+=b[j];
            res=max(res,cnt);
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int maxn = 200010;
typedef long long ll;

int n,m,k;
int mod;
ll ans=0;
int a[maxn];

void test(const int A[])
{
	for (int i=1;i<=n;i++)
		cout << A[i] << " ";
	cout << endl;
}

void test(const vector<int> V)
{
	for (int i=0;i<V.size();i++)
		cout << V[i] << " ";
	cout << endl;
}

void solve()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	
	sort(a+1,a+n+1);
	int cunts = n-2;
	ans += a[n];
	int i = n-1;
	int flag = 1;
	while(cunts)
	{
		if(flag)
		{
			ans += a[i];
			flag = 0;
			cunts--;
		}
		else
		{
			ans += a[i];
			flag = 1;
			i--;
			cunts--;
		}
	}
	
	cout << ans << endl;
}

int main()
{
	int t;
	t = 1;
	while(t--)
	{
		solve();
	}
} 

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

int main() {
  
  int n;
  cin >> n;
  
  int v[n], c[n];
  REP(i,n) cin >> v[i];
  REP(i,n) cin >> c[i];
  
  int all = 1 << n;
  int m = 0;
  REP(k,all) {
    int x = 0, y = 0;
    REP(i,n) {
      if ((k >> i) & 1) {
        x += v[i], y += c[i];
      }
    }
    m = max(m, x-y);
  }
  
  cout << m << endl;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using  namespace std;
 
struct Set{
    int a, b;
};
 
bool up_a(const Set &x, const Set &y){
  return x.b < y.b;
}
 
int main() {
  int n, m, ans;
  cin >> n >> m;
  
  Set sets[m];
  vector<int> vec(1,0);
  
  for(int i=0; i<m; i++) {
    int a, b; 
    cin >> sets[i].a >> sets[i].b;
  }
  sort(sets, sets+m, up_a);
  
  ans = 0;
  for(int i=0; i<m; i++) {
    if(*max_element(vec.begin(), vec.end()) < sets[i].a) {
      vec.push_back(sets[i].b-1);
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
num = int(input())
b_list = list(map(int, input().split(" ")))

b_list.append(b_list[num-2])
ans_list = []
ans_list.append(b_list[0])

for i in range(1, num, 1):
    ans_list.append(min(b_list[i-1], b_list[i]))

print(sum(ans_list))

Measured memory_bytes: 3060
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

n = int(input())
ans = 0
while True:
    if is_prime(n):
       ans = n
       break
    else:
        n += 1

print(ans)

Measured memory_bytes: 3060
#include <iostream>
#define mod 2019
using namespace std;
int s[3005];
int main(int argc, char** argv) {
	string a;
	cin >> a;
	int n=a.size();
	a=' '+a;
	s[0]=1;
	int ksm=1,invksm=1;
	long long ans=0,now=0;
	for(int i=1;i<=n;i++)
	{
		now*=10,now+=a[i]-'0',now%=mod;
//		cout << now << " ";
		ans+=s[now*invksm%mod],++s[now*invksm%mod];
		ksm*=10,invksm*=202,ksm%=mod,invksm%=mod;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3376
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
const ll mod = 1e9 + 7;

int main()
{
    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<int> count(n + 1);
    rep(i, n - 1)
    {
        if (s[i] == 'A' && s[i + 1] == 'C')
            count[i + 1]++;
    }
    rep(i, n) count[i + 1] += count[i];
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << count[r - 1] - count[l - 1] << endl;
    }
    return 0;
}


Measured memory_bytes: 1408
li = [0] * 4
N = int(input())
for i in range(N):
    result = input()
    if result == "AC":
        li[0] += 1
    if result == "WA":
        li[1] += 1 
    if result == "TLE":
        li[2] += 1
    if result == "RE":
        li[3] += 1
line = "AC x {0}\nWA x {1}\nTLE x {2}\nRE x {3}".format(li[0], li[1], li[2], li[3])
print(line)

Measured memory_bytes: 9188
#include "bits/stdc++.h"
using namespace std;
using ll=long long;

#include <vector>
#include <functional>

template <typename T,typename E>
struct LazySegmentTree{
   using F=std::function<T(T,T)>;
   using G=std::function<T(T,E,int,int)>;
   using H=std::function<E(E,E)>;

   int n;
   std::vector<T> dat;
   std::vector<E> laz;
   const F f;
   const G g;
   const H h;
   const T d1;
   const E d0;

   LazySegmentTree(int n_,const F f,const G g,const H h,const T d1,const E d0):f(f),g(g),h(h),d1(d1),d0(d0)
   {
      n=1;
      while(n_>n) n<<=1;
      dat.assign(2*n,d1);
      laz.assign(2*n,d0);
   }

   void set(int k,const T &x){
      dat[k+n]=x;
   }
   void build(){
      for(int k=n-1;k>0;--k) dat[k]=f(dat[2*k],dat[2*k+1]);
   }
   void eval(int k,int l,int r){
      if(laz[k]==d0) return;
      dat[k]=g(dat[k],laz[k],l,r);
      if(k<n){
         laz[2*k]=h(laz[2*k],laz[k]);
         laz[2*k+1]=h(laz[2*k+1],laz[k]);
      }
      laz[k]=d0;
   }
   void update(int a,int b,E x,int k=1,int l=0,int r=-1){
      if(r<0) r=n;
      eval(k,l,r);
      if(r<=a||b<=l) return;
      if(a<=l&&r<=b){
         laz[k]=h(laz[k],x);
         eval(k,l,r);
      }
      else{
         update(a,b,x,2*k,l,(l+r)/2);
         update(a,b,x,2*k+1,(l+r)/2,r);
         dat[k]=f(dat[2*k],dat[2*k+1]);
      }
   }
   T query(int a,int b,int k=1,int l=0,int r=-1){
      if(r<0) r=n;
      eval(k,l,r);
      if(r<=a||b<=l) return d1;
      if(a<=l&&r<=b) return dat[k];
      T vl=query(a,b,2*k,l,(l+r)/2);
      T vr=query(a,b,2*k+1,(l+r)/2,r);
      return f(vl,vr);
   }
};

/*

-RMinimumQ and RUpdateQ
f=[](T x,T y){ return min(x,y); };
g=[](T x,E y,int l,int r){ return y; };
h=[](E x,E y){ return y; };

-RSumQ and RAddQ
f=[](T x,T y){ return x+y; };
g=[](T x,E y,int l,int r){ return x+(r-l)*y; };
h=[](E x,E y){ return x+y; };

-RMinimumQ and RAddQ
f=[](T x,T y){ return min(x,y); };
g=[](T x,E y,int l,int r){ return x+y; };
h=[](E x,E y){ return x+y; };

-RSumQ and RUpdateQ
f=[](T x,T y){ return x+y; };
g=[](T x,E y,int l,int r){ return (r-l)*y; };
h=[](E x,E y){ return y; };

*/

int main(){
   int n,q;
   cin>>n>>q;
   using T=ll;
   using E=ll;
   auto f=[](T x,T y){ return min(x,y); };
   auto g=[](T x,E y,int l,int r){ return x+y; };
   auto h=[](E x,E y){ return x+y; };
   LazySegmentTree<ll,ll> seg(n,f,g,h,INT_MAX,0);
   for(int i=0;i<n;++i) seg.set(i,0);
   seg.build();
   for(int i=0;i<q;++i){
      int com;
      cin>>com;
      int s,t,x;
      cin>>s>>t;
      if(com==0){
         cin>>x;
         seg.update(s,t+1,x);
      }
      else{
         cout<<seg.query(s,t+1)<<endl;
      }
   }
}



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

const string YES = "YES";
const string NO = "NO";

void solve(std::string S) {
    ll a = 0, b = 0, c = 0;
    rep(i, S.length()) {
        if (S[i] == 'a') {
            a++;
        } else if (S[i] == 'b') {
            b++;
        } else {
            c++;
        }
    }
    if (abs(a - b) <= 1 && abs(a - c) <= 1 && abs(b - c) <= 1) {
        cout << YES << endl;
    } else {
        cout << NO << endl;
    }
}

int main() {
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


Measured memory_bytes: 3792
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const int INF=1e9;
const ll MX = 1e18;
const ll MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
#define YN {puts("YES");}else{puts("NO");}
const ll MAX = 1000001;
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll i = 2; i < MAX; 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(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}
ll llpow(ll n,ll i){ll cnt=n;  for(ll j=0;j<i-1;j++){n*=cnt;}return n;}

int main() {
  int r,d,x;
  cin>>r>>d>>x;
  rep(i,10){
    x=x*r-d;
    cout<<x<<endl;
  }
}


Measured memory_bytes: 3608
MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a * MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 4000

fac  = [1,1]
finv = [1,1]
inv  = [1,1]

def COMinit():
    for i in range(2, MAX):
        fac.append(fac[i - 1] * i % MOD)
        inv.append(MOD - inv[MOD%i] * (MOD // i) % MOD)
        finv.append(finv[i - 1] * inv[i] % MOD)

def mod_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

COMinit()
N, K = map(int, input().split())

for i in range(1, K+1):
    res = mod_mul(mod_COM(K-1, i-1), mod_COM(N-K+1, i))
    print(res)



Measured memory_bytes: 3824
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iomanip>
#include<map>
#include<cstring>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const ll LLINF = 1LL<<60;
/* -- template -- */
int cnt[100000];
int main(){
    int H, W; cin >> H >> W;
    string S[H];
    rep(i, H)cin >> S[i];
    int wide[H][W], height[H][W];
    //maxv = max(wide[i][j] + height[i][j], maxv);
    rep(i, H){
        int k = 0;
        rep(j, W){
            if(S[i][j] == '#'){
                k = 0;
            }else{
                ++k;
            }
            wide[i][j] = k;
        }
    }
    rep(i, H){
        for(int j = W - 1;j > 0;--j){
            if(wide[i][j - 1] > 0 && wide[i][j] != 0){
                wide[i][j - 1] = wide[i][j];
            }
        }
    }
    rep(j, W){
        int k = 0;
        rep(i, H){
            if(S[i][j] == '#'){
                k = 0;
            }else{
                ++k;
            }
            height[i][j] = k;
        }
    }
    rep(j, W){
        for(int i = H - 1;i > 0;--i){
            if(height[i - 1][j] > 0 && height[i][j] != 0){
                height[i - 1][j] = height[i][j];
            }
        }
    }
    int maxv = 0;
    rep(i, H){
        rep(j, W){
            maxv = max(maxv, wide[i][j] + height[i][j]);
        }
    }
    cout << maxv - 1 << endl;
}


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

#define ll long long
#define endl "\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int mod = 1e9 + 7;
const int MAX = 1e5 + 1;

void solve()
{
	int n, x, t;
	cin >> n >> x >> t;
	int time = 0;
	while(n > 0)
	{
		n -= x;
		time += t;
	}
	cout << time << endl;
}

int main()
{
	IOS
	int t = 1;
	//cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}


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

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPr(i, n) for(int i = (n)-1; i >= 0; --i)
#define FORq(i, m, n) for(int i = (m); i <= (n); ++i)
#define FORqr(i, m, n) for(int i = (n); i >= (m); --i)
#define MP make_pair
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x, 0, sizeof(x))
#define FILL(x, y) memset(x, y, sizeof(x))
#define MM(x) memset(x, -1, sizeof(x))
#define ALL(x) (x).begin(), (x).end()
#define DB(x) cerr << #x << " = " << x << endl
#define DB2(x, y)                                                              \
    cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define DEBUG                                                                  \
    int x12345;                                                                \
    cin >> x12345;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
const long long MOD = 1e9 + 7;
///////////////////////////////////////////////
// for template
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;
}
///////////////////////////////////////////////
/// 🍈( '-' 🍈 |AC|
int main() {
    int H1,M1,H2,M2,K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    int L = (H2 - H1) * 60 + (M2 - M1);
    int ans = L - K;
    cout << ans << endl;
}

Measured memory_bytes: 3636
#!/usr/bin/env python3

n = int(input())
N_list = list(map(int, input().split()))

ans = 1e10
for i in range(n):
    # 各N_list[i]について2の素因数をカウント
    j = 0
    while N_list[i] % 2 == 0:
        N_list[i] = N_list[i] / 2
        j += 1
    if ( j < ans):
        ans = j

print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define F first
#define S second
#define ld long douroote
#define pb push_back
#define sz size
#define ll long long
#define ull unsigned long long
#define INF 0x7f7f7f7f
#define sc(a) scanf("%d",&a)
#define scll(a) scanf("%lld",&a)
#define scd(a) scanf("%lf",&a)
#define scc(a) scanf(" %c",&a)
#define scs(a) scanf(" %s",a)
#define me(a,b) memset(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define allr(a,n) a,a+n
#define loop(a,s,e) for(ll a=s;a<=e;a++)
#define read_arr(a,s,n) for(int i=s;i<n+s;i++){sc(a[i]);}
#define read_arr_ll(a,s,n) for(int i=s;i<n+s;i++){scll(a[i]);}
#define err(a,s) cerr<<a<<s;
#define err_arr(a,s,n) for(int i=s;i<n+s;i++){cerr<<a[i]<<" ";}cerr<<endl;
#define prtll(x) printf("%lld",x);
#define prt(x) printf("%d",x);
using namespace std;
const int N=5e2+10;
ll n,a[N],mem[N][N],pr[N];
ll oo=1e18;
ll dp(int i,int j){
if(i==j){mem[i][j]=0;return 0;}
ll &ret=mem[i][j];
if(ret!=-1){return ret;}
ret=oo;
ll sum=0;
loop(k,i,j){sum+=a[k];}
loop(k,i,j-1){
//ll sum=(pr[k+1]-pr[i]+pr[j+1]-pr[k+1]);
ret=min(ret,dp(i,k)+dp(k+1,j)+sum);
}
return ret;
}
int main(){
me(mem,-1);
scll(n);
read_arr_ll(a,0,n);
ll ans=dp(0,n-1);
printf("%lld\n",ans);
}
/**
**/


Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int INF=1e9+5;
const int N=3000+5;
const int mod=998244353;

int h,w;
int k;
string s[15];
int ans=INF;
vector<vector<int>> sum;

void solve(int mask){
	vector<int> vec;
	vec.push_back(0);
	for(int i=0;i<h;++i){
		if((mask>>i)&1) vec.push_back(i+1);
	}
	vec.push_back(h);
	int l=0;
	int cnt=0;
	bool check=1;
	for(int j=1;j<=w;++j){
		for(int i=0;i<(int)vec.size()-1;++i){
			int num=sum[vec[i+1]][j]-sum[vec[i]][j]-sum[vec[i+1]][l]+sum[vec[i]][l];
			if(num>k){
				if(j-l==1){
					check=0;
					break;
				}
				++cnt;
				l=--j;
			}
		}
		if(!check) break;
	}
	int num_cut=__builtin_popcount(mask);
	if(check) ans=min(ans,num_cut+cnt);
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>h>>w>>k;
	for(int i=0;i<h;++i) cin>>s[i];
	sum.resize(h+1,vector<int>(w+1));
	for(int i=0;i<h+1;++i){
		for(int j=0;j<w+1;++j) sum[i][j]=0;
	}
	
	for(int i=1;i<=h;++i){
		for(int j=1;j<=w;++j){
			 int val=s[i-1][j-1]-'0';
			sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+val;
		}
	}
	//~ for(int i=0;i<=h;++i){
		//~ for(int j=0;j<=w;++j){
			//~ cout<<sum[i][j]<<" ";
		//~ }
		//~ cout<<endl;
	//~ }
	//~ cout<<endl;
	for(int mask=0;mask<(1<<h);++mask){
		solve(mask);
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 2000010;
const int oo = 1e9;

int n , m , k;
int main() {
	//freopen("input.txt", "r", stdin);
	cin >> n >> m >> k;
	for(int rows = 0 ; rows <= n ; rows++){
		for(int cols = 0 ; cols <= m ; cols++){
			if(rows*m+cols*n-2*rows*cols == k){
				puts("Yes");
				return 0;
			}
		}
	}
	puts("No");
	return 0;
}

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

using namespace std;

#define ll long long
#define ini(arr, val) memset(arr, (val), sizeof(arr))
#define loop(i,n)  for(ll i=0; i<n; i++)
#define loop1(i,n)  for(ll i=1; i<=n; i++)

#define all(a)      (a).begin(),(a).end()
#define exist(s,e)  (s.find(e)!=s.end())
#define dbg(x)  cout << #x << " = " << x << endl
#define pt(x) cout<<x<<"\n"
#define pts(x) cout<<x<<" "

#define mp make_pair
#define pb push_back
#define F first
#define S second


#define inf (int)1e9
#define infll 1e18
#define eps 1e-9
#define PI 3.1415926535897932384626433832795
#define mod 1000000007


#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test   int t; cin>>t; while(t--)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef set<int> si;

typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pll> vpll;
typedef vector<vl> vvl;
typedef map<ll,ll> mll;
typedef set<ll> sl;


int dirx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int diry[] = { -1, 0, 1, -1, 1, -1, 0, 1 };



//===========================DEBUG======================//
#define XOX 1
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

//================================================================//



//////////////////////////////////////////////////////////////////////////////////////////
//                      main starts
//////////////////////////////////////////////////////////////////////////////////////////
int const lmt=1e5+5;


int main(){
 //    #ifndef ONLINE_JUDGE
 //    freopen("../../input.txt", "r", stdin);
 //    freopen("../../output.txt", "w", stdout);
	// #endif
    fast

    ll k,a,b; cin>>k>>a>>b;
    ll val = k* ((a+k-1)/k );
    pt((val<=b?"OK":"NG"));
}


/*



*/





Measured memory_bytes: 3604
#include<bits/stdc++.h>
#define int long long 
#define rap(i,n) for(int i=0;i<n;++i)
using namespace std;
signed main(){
  int n,a=0;
  cin>>n;
  if(n%2!=0) cout<<n/2<<"\n";
  else cout<<n/2-1<<"\n";
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
    int H, W;
    while(1){
        cin >> H;
        cin >> W;
        if(H == 0){
            break;
        }
        for(int i=0; i<H; i++){
            for(int j=0; j<W; j++){
                cout << '#';
            }
            cout << endl;
        }
        cout << endl;
    }
}


Measured memory_bytes: 3096
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::f64::consts::*;

#[allow(unused)]
const INF: usize = std::usize::MAX / 4;
#[allow(unused)]
const M: usize = 1000000007;

fn main() {
    input! {
        a: usize,
        b: usize,
        c: usize,
        k: usize,
    }
    let mut ok = false;
    for x in 0..=k {
        for y in 0..=k {
            for z in 0..=k {
                if x + y + z <= k {
                    if a * 2usize.pow(x as u32) < b * 2usize.pow(y as u32)
                        && b * 2usize.pow(y as u32) < c * 2usize.pow(z as u32)
                    {
                        ok = true;
                    }
                }
            }
        }
    }
    if ok {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

int main() {
  ll n;
  cin >> n;
  vec a(n);
  vec s(n);
  for(ll i=0;i<n;i++) {
    cin >> a[i];
    s[i]=a[i];
  }
  sort(s.begin(),s.end());
  map<ll,ll> change;
  for(ll i=0;i<n;i++) {
    change[s[i]]=i%2;
  }
  ll ans=0;
  for(ll i=0;i<n;i+=2) {
    ans+=change[a[i]];
  }
  cout << ans << endl;
}

Measured memory_bytes: 8064
#include <stdio.h>

int main(void){
  int n;
  scanf("%d",&n);

  char cha[n];

  scanf("%s",cha);
  int sum=1;

  for(int i=0;i<n-1;i++){
    if(cha[i]!=cha[i+1])sum++;
  }
  printf("%d",sum);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
bitset<maxn> pr; 
void sieve(){
	pr.set();
	pr[0] = pr[1] = 0;
	for(int i = 2; i*i < maxn; ++i){
		if(pr[i])
			for(int j = i*i; j < maxn; j+=i) 
				pr[j] = 0;
	}
}
int main() {
	sieve();
	vector<int> suma(maxn, 0);
	for(int i = 1; i < maxn; ++i) suma[i] = suma[i - 1] + (pr[i] and pr[(i + 1)/2]);
	int q,l,r;
	cin >> q;
	while(q--){
		cin >> l >> r;
		cout << suma[r] - suma[l - 1] << endl;  
	}
	
	return 0;
}


Measured memory_bytes: 4608
# include <bits/stdc++.h>
using namespace std;
long long n,m,a[100005],sum,ans,k;
int main()
{
	cin>>n>>m;
	for (int i=1; i<=n; i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	k=(sum+4*m-1)/(4*m);
	for (int i=1; i<=n; i++)
	{
		if (a[i]>=k) ans++;
	}
	if (ans>=m) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

Measured memory_bytes: 256
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　redcoderになるためAtCoderを巡る旅をしてます。

　　　 　 ＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　 ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣/ヽ
*/




#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

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

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

    int r; cin >> r;
    int ans = 3 * pow(r, 2);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef string str;
#define rep(i, n) for(int i=0; i<n; ++i)
#define REP(i, n) for(int i=1; i<=n; ++i)
#define all(obj) (obj).begin(), (obj).end()
using P = pair<int, int>;
const int inf = 1e9;
const ll INF = 1e18;
const ll MOD = 1e9+7;
const ll MAX = 1e9+7;
template<typename T> T factorial(T n){
    if(n==1) return 1;
    else return n*factorial(n-1)%MOD;
}
template<typename T> T Pow(T x, T n, T m){
    if(n == 0) return 1;
    if(n % 2 == 0) return Pow(x * x % m, n / 2, m);
    else return x * Pow(x, n - 1, m) % m;
}
template<typename T> T combination(T n, T k, T m){
    return factorial<T>(n) * Pow<T>(factorial(k), m-2, m) % m * Pow<T>(factorial(n-k), m-2, m) % m;
}
struct edge{
    int to; // 辺の行き先
    int weight; // 辺の重み
    edge(int t, int w) : to(t), weight(w) { }
};
using graph = vector<vector<edge>>;
using Graph = vector<vector<int>>;

int bfs(vector<vector<char>> maze, int h, int w, int sx, int sy){
    queue<P> q;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    int d[h][w];
    int ans = 0;
    rep(i, h){
        rep(j, w){
            d[i][j] = inf;
        }
    }
    q.push(P(sx, sy));
    d[sx][sy] = 0;
    while(!q.empty()){
        P p = q.front();
        q.pop();
        rep(i, 4){
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            if(0 <= nx && nx < h && 0 <= ny && ny < w && maze[nx][ny] != '#' && d[nx][ny] == inf){
                q.push(P(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
                ans = max(ans, d[nx][ny]);
            }
        }
    }
    return ans;
}

int main(){
    int h, w; cin >> h >> w;
    vector<vector<char>> maze(h, vector<char>(w));
    rep(i, h){
        rep(j, w){
            cin >> maze[i][j];
        }
    }
    int ans = 0;
    rep(sx, h){
        rep(sy, w){
            if(maze[sx][sy] == '.'){
                ans = max(ans, bfs(maze, h, w, sx, sy));
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 2000000000
typedef long long ll;
bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
    int H,W,A,B;
    cin >>H >> W >> A >>B;


    rep(i,H){
        rep(j,W){
            if(i<B){
                if(j<A){
                    cout << 0;
                }else{
                    cout << 1;
                }
            }else{
                if(j<A){
                    cout << 1;
                }else{
                    cout << 0;
                }
            }
        }
        cout << endl;
    }
    //cout << N << endl;
    
    
    return 0;
    

}

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

int main() {
	// your code goes here
	int n;
	cin>>n;
	int check = n%1000;
	int check2= n/1000;
	int pay = (check2+1)*1000;
	if(check)cout<<pay-n;
	else cout<<0;
	
	
	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
int main() {
    int k, a, b;
    cin >> k >> a >> b;
    for(int i = a; i <= b; i++) {
        if(i % k == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}


Measured memory_bytes: 3596
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

#define DEBUG 0
#define REP(i, n) for (int i = 0; i < (n); i++) 
typedef long long ll;
typedef pair<int,int> pint;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;
using namespace std;


int cnt_digits(ll N){
    int digits=0;
    while(N>0){
    N/=10;
    digits++;
    }
    return digits;
}


//構成にpushback
//約数を列挙せずとも構成としてやっちゃう
int main() { 

    ll n;
    cin >> n;

    ll res = MOD;

    for(ll a = 1; a*a <= n; ++a)
    {
        if(n % a == 0)
        {
            ll b = n/a;
            //桁数調べ
            ll keta_a = cnt_digits(a);
            ll keta_b = cnt_digits(b);

            res = min(res, max(keta_a,keta_b));

        }
    }

    cout << res << endl;

    return 0;

}

Measured memory_bytes: 256
/* - - - - - - - - - - - - - - -
	User : 		VanishD
	problem :
	Points : 	
- - - - - - - - - - - - - - - */
# include <bits/stdc++.h>
# define 	ll 		long long
using namespace std;
const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
int read(){
	int tmp = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9'){ if (ch == '-') fh = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9'){ tmp = tmp * 10 + ch - '0'; ch = getchar(); }
	return tmp * fh;
}
const int N = 200010;
char s[N];
int main(){
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	scanf("\n%s", s + 1);
	int l = strlen(s + 1);
	int ans = l;
	for (int i = 1; i <= l / 2; i++)
		if (s[i] != s[i + 1]) ans = min(ans, l - i);
	for (int i = 1; i <= l / 2; i++)
		if (s[l - i + 1] != s[l - i]) ans = min(ans, l - i);
	printf("%d\n", ans);
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  
  string x[n], u[n];
  
  for(int i = 0; i < n; i++)
    cin >> x[i] >> u[i];
  
  double sum;
  
  for(int i = 0; i < n; i++){
    if(u[i] == "BTC")
      sum += stod(x[i]) * 380000.0;
    else
      sum += stoi(x[i]) * 1.0;
  }
  
  cout << sum << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  int N;
  cin>>N;
  string s;
  map<string,int> score;
  for(int i=0;i<N;i++){
    cin>>s;
    score[s]++;
  }
  cout<<score.size()<<endl;
}

Measured memory_bytes: 19224
fn main() {
    a();
}

fn first_words(s: &String) -> usize  {
    let bytes = s.as_bytes();
    for (i,&item) in bytes.iter().enumerate() {
        if item == b' ' {
            return i;
        }
    }
    s.len()
}

fn a() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let nums: Vec<i32> = s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
    println!("{}",(nums[0] - 1)*(nums[1] - 1));
}


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

int main(){
int n;string s;
cin>>n>>s;
int sum[n+1];
sum[0]=0;
for(int i=1;i<=n;i++){
    sum[i]=sum[i-1]+(s[i-1]=='.');
}
int ans=n;
for(int i=0;i<=n;i++){
    int a=sum[n]+i-2*sum[i];
    ans=min(a,ans);
}
cout<<ans;

}

Measured memory_bytes: 1404
#include<stdio.h>
int main()
{
	int temp=0;
	int input=0;
	int i=0;
	scanf("%d",&input);
	int a[100];
	for(i=1;i<=input;i++){
		a[temp]=i;
		temp++;
	}
	int cnt=0;
	for(i=0;i<input;i++){
		if(a[i]%2==1){
			cnt++;
		}
	}
	printf("%.10f",(1.0*cnt)/(1.0*input));
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define LL long long
#define maxn 200010
using namespace std;
int color[maxn],head[maxn],tot,n,Size[maxn],sum[maxn];
LL ans[maxn];
struct node{
	int to,next;
}e[maxn<<1];
void add_edge(int u,int v){
	tot++,e[tot].to=v,e[tot].next=head[u],head[u]=tot;
}
LL get_num(LL x){
	return x*(x+1)/2;
}
void dfs(int u,int fa){
	int v,b,c,t,dt;
	LL pre;
	Size[u]=1,c=color[u], pre=sum[c];//非u子树已算出的c颜色为根的节点数量
	for(b=head[u];b;b=e[b].next){
		v=e[b].to;
		if(v==fa)continue;
		t=sum[c];
		dfs(v,u);
		dt=sum[c]-t;//遍历了v之后，c颜色对应的变化量
		Size[u]+=Size[v];
		ans[c]-=get_num(Size[v]-dt);//两个c颜色之间的，其他颜色节点数量
	}

	sum[c]=pre+Size[u];//总的c颜色为根的节点数量
	//cout << "u: " << u << "    pre: " << pre << "     c: " << c << "    sum: " << sum[c] << "     Size: " << Size[u] << endl;
}
int main(){
	int i,u,v;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&color[i]);
	for(i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		add_edge(u,v),add_edge(v,u);
	}
	for(i=1;i<=n;i++)ans[i]=get_num(n);
	dfs(1,0);
	for(i=1;i<=n;i++)ans[i]-=get_num(n-sum[i]);//n-sum[i]指离树根最近的i颜色之外的其他颜色(整棵树扣除所有以i颜色为根的子树)数量
	for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
	return 0;
}


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

int abs(int n)
{
  return n>0?n:-n;
}

int main()
{
  int x,n;
  std::cin>>x>>n;
  
  std::vector<int> p(101);
  for(int i=0;i<=101;i++)
  {
    p[i]=i;
  }
  for(int i=0;i!=n;i++)
  {
    int t;
    std::cin>>t;
    p[t]=-1;
  }
  
  int result=0;
  for(int i=x;i>=0;i--)
  {
    if(p[i]!=-1)
    {
      result=p[i];
      break;
    }
  }
  for(int i=x;i<=101;i++)
  {
    if(p[i]!=-1)
    {
      result=abs(x-p[i])<abs(x-result)?p[i]:result;
      break;
    }
  }
  
  std::cout<<result<<std::endl;
  
  return 0;
}

Measured memory_bytes: 3628