akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        // Here your code !
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] tmpArray = br.readLine().split(" ");
        int m = Integer.parseInt(tmpArray[0]);
        int n = Integer.parseInt(tmpArray[1]);
        
        //System.out.println("m "+m+" n "+n);
        
        if(m < n){
            int tmp = m;
            m = n;
            n = tmp;
        }
        
        if(m - n >= 2){
            System.out.println(0);
        }
        else {
            int combination;
            
            if(m == n){
                combination = 2;
            }
            else {
                combination = 1;
            }
            int mod = 1000000007;
            System.out.println((long)(Calc.Fact(m,mod) * Calc.Fact(n,mod) * combination)%mod);
        }
    }
}

class Calc {
    static long Fact(int n){
        long result = 1;
        for(int i = n; i >= 1;i--){
            result *= i;
        }
        
        System.out.println("fact("+n+") = "+result);
        return result;
    }
    
    static long Fact(int n, int mod){
        long result = 1;
        for(int i = n; i >= 1;i--){
            result *= i;
            result %= mod;
        }
        
        //System.out.println("fact("+n+") = "+result);
        return result;
    }
    
    static int combination(int n, int p){
        
        
        int result = 1;
        /*
        if(n - p < p){
            p = n-p;
        }
        
        for(int i = p; i > 1; i--){
            
        }*/
        
        return result;
    }
}

Measured memory_bytes: 21204
#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
int v[10001], w[10001];
ll cache[101][100001];

ll calc(int W, int n) {
	if(W < 0) {
		return INT_MIN;
	}
	
	if(n==0 || W==0) {
		return 0;
	}
	
	if(cache[n][W]!=-1) {
		return cache[n][W];
	}
	
	if(w[n] > W) {
		cache[n][W] = calc(W, n-1);
		return cache[n][W];
	}
	
	
	cache[n][W] = max(calc(W-w[n], n-1) + v[n], calc(W, n-1));
	return cache[n][W];
}
int main() {
	int n,W;
	cin>>n>>W;   
	for (int i=1; i<=n; i++) {
		cin>>w[i]>>v[i];
	}
	
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=W;j++) {
			cache[i][j] = -1;
		}
	}
	
	cout << calc(W,n);
	return 0;
}

Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
//BEGIN CUT HERE
// prohibited to push an element less than popped one
// Key: int or long long
template<typename K,typename V>
struct RadixHeap{
  static constexpr int bit = sizeof(K) * 8;
  array<vector< pair<K, V> >, bit> vs;

  int size;
  K last;
  RadixHeap():size(0),last(0){}

  bool empty() const{return size==0;}

  inline int getbit(int a){
    return a?bit-__builtin_clz(a):0;
  }

  inline int getbit(long long a){
    return a?bit-__builtin_clzll(a):0;
  }

  void emplace(K key,V val){
    size++;
    vs[getbit(key^last)].emplace_back(key,val);
  }

  pair<K, V> pop(){
    if(vs[0].empty()){
      int idx=1;
      while(vs[idx].empty()) idx++;
      last=min_element(vs[idx].begin(),vs[idx].end())->first;
      for(auto &p:vs[idx]) vs[getbit(p.first^last)].emplace_back(p);
      vs[idx].clear();
    }
    --size;
    auto res=vs[0].back();
    vs[0].pop_back();
    return res;
  }
};
//END CUT HERE
//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n,m,r;
  cin>>n>>m>>r;

  using P = pair<int, int>;
  vector< vector<P> > G(n);
  for(int i=0;i<m;i++){
    int s,t,d;
    cin>>s>>t>>d;
    G[s].emplace_back(t,d);
  }

  const int INF = numeric_limits<int>::max();
  RadixHeap<long long, long long> pq;
  vector<int> dist(n,INF);
  dist[r]=0;
  pq.emplace(dist[r],r);
  while(!pq.empty()){
    P p=pq.pop();
    int v=p.second;
    if(dist[v]<p.first) continue;
    for(auto& e:G[v]){
      int u=e.first,c=e.second;
      if(dist[u]>dist[v]+c){
        dist[u]=dist[v]+c;
        pq.emplace(dist[u],u);
      }
    }
  }

  for(int i=0;i<n;i++){
    if(dist[i]==INF) cout<<"INF\n";
    else cout<<dist[i]<<"\n";
  }
  cout<<flush;
  return 0;
}


Measured memory_bytes: 14736
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define pq          priority_queue
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         1000000007
#define inf         INT_MAX-100
#define vl          vector<ll>
#define vvl         vector<vector<ll>>
#define F           first
#define S           second
#define db          double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
//const int N;

void solve()
{
    ll n,k; cin>>n>>k;
    ll a[n];
    rep(i,0,n) cin>>a[i];
    ll dp[n];
    rep(i,0,n) dp[i]=inf;
    dp[0]=0;
    dp[1]=abs(a[0]-a[1]);
    rep(i,2,n)
    {
       rep(j,(i-k>0?(i-k):0),i) dp[i]=min(dp[j]+abs(a[i]-a[j]),dp[i]);
    }
    cout<<dp[n-1];
}
int main()
{
    ll T=1;
    //cin>>T;
    while(T--)
        solve();
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
	int i, N;
	long long t;
	int p[20010];
	long long a[20010], b[20010];
	scanf("%d", &N);
	for (i=0;i<N;i++) scanf("%d", &p[i]);

	for (i=1;i<=N;i++) {
		a[i] = i;
		b[i] = N-i+1;
	}
	t = (N-1) - 2;
	if (t>0) {
		if (a[p[0]] < b[p[0]]) b[p[0]] += t;
		else a[p[0]] += t;
	}
	for (i=1;i<N;i++) {
		t = a[p[i-1]] + b[p[i-1]];
		if (t < a[p[i]] + b[p[i]]) continue;
		else {
			t -= a[p[i]] + b[p[i]];
			if (a[p[i]]<b[p[i]]) {
				b[p[i]] += t+1;
				if (p[i]>1) if (b[p[i]] <= b[p[i]-1]) {
					a[p[i]] += b[p[i]] - (b[p[i]-1]-1);
					b[p[i]] = b[p[i]-1] - 1;
				} 
			} else {
				a[p[i]] += t+1;
				if (p[i]<N) if (a[p[i]] >= a[p[i]+1]) {
					b[p[i]] += a[p[i]] - (a[p[i]+1]-1);
					a[p[i]] = a[p[i]+1] - 1;
				} 
			}
		}
	}

//	for (i=1;i<N;i++) printf("%d ", a[i]); printf("%d\n", a[N]);
//	for (i=1;i<N;i++) printf("%d ", b[i]); printf("%d\n", b[N]);
	for (i=2;i<=N;i++) {
		if (a[i-1]>=a[i]) {
			b[i] += a[i] - a[i-1] - 1;
			a[i] = a[i-1] + 1;
		}
		if (b[i-1]<=b[i]) {
			a[i] += b[i] - b[i-1] + 1;
			b[i] = b[i-1] - 1;			
		}
	}
	if (b[N]<=0) {
		t = 1 - b[N];
		for (i=1;i<=N;i++) b[i] += t;
	}
	if (a[1]<=0) {
		t = 1 - a[1];
		for (i=1;i<=N;i++) a[i] += t;
	}
	for (i=1;i<N;i++) printf("%d ", a[i]); printf("%d\n", a[N]);
	for (i=1;i<N;i++) printf("%d ", b[i]); printf("%d\n", b[N]);
	return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define INF (1 << 30)
#define INFLL (1LL << 60)

int main() {
	map<int, bool> m;
	int a, b, c;
	cin >> a >> b >> c;
	m[a] = true;
	m[b] = true;
	m[c] = true;

	cout << m.size() << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n, k = map(int,input().split())
    d = list(input().split())


    ans = n

    Flag = False
    while True:
        for i in range(k):
            if list(str(ans)).count(d[i]) > 0:
                ans+=1
                Flag = True
                break
            if i == k -1:
                print(ans)
                exit()


if __name__ == "__main__":
        main()


Measured memory_bytes: 3060
pub fn read1<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn readn<T: std::str::FromStr>(delimiter: &str) -> Vec<T> {
    let s = read1::<String>();
    s.split(delimiter).map(|e| e.parse().ok().unwrap()).collect::<Vec<T>>()
}

fn main() {
    let ny = readn::<usize>(" ");
    let n = ny[0];
    let y = ny[1];

    for i in 0..(std::cmp::min(n, y / 10000) + 1) {
        for j in 0..(std::cmp::min(n - i, (y - 10000 * i) / 5000) + 1) {
            if 10000 * i + 5000 * j + 1000 * (n - i - j) == y {
                println!("{} {} {}", i, j, n - i - j);
                return;
            }
        }
    }

    println!("-1 -1 -1");
}

Measured memory_bytes: 4352
a,b,c,x,y=map(int,input().split())

ans=10**10

for i in range(10**5+1):
    a_cnt=max(0,x-i)
    b_cnt=max(0,y-i)
    
    total=i*2*c+a_cnt*a+b_cnt*b
    ans=min(ans,total)

print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
#include <list>
#include <iomanip>
#include <cctype>

using namespace std;

#define Int int64_t

void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

int vector_finder(std::vector<string> vec, string number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}

#include <sstream> 
std::vector<std::string> StringSplit(const std::string& str, char sep)
{
	std::vector<std::string> v;
	std::stringstream ss(str);
	std::string buffer;
	while (std::getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}

Int gcd(Int a, Int b) {
	return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
	return a * b / gcd(a, b);
}

bool comp(const string a, const string b) {
	return a.length() < b.length();
}

bool integer(double num) {
	return floor(num) == num;
}

int main() {
	int n,l; cin >> n>>l ;
	int sum = n * (n + 1) / 2 + (l - 1) * n;

	int minz = 1000000000;
	for (int i = 1; i <= n; i++) {
		minz = min(minz, abs(l + i - 1));
	}
	//cout << sum << endl;
	if (sum < 0) cout << sum + minz;
	else cout << sum - minz;

	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void) {
    int n, a, b;
    scanf("%d%d%d",&n,&a,&b);
    int i, j, k;
    int dgsum;
    int n2;
    int ans = 0;
    for(i=1;i<=n;i++) {
        dgsum = 0;
        n2 = i;
        while(n2%10!=0 || n2/10!=0){
            k = n2%10;
            dgsum = dgsum + k;
            n2 = n2/10;
        }
        if(dgsum>=a && dgsum<=b){
            ans = ans + i;
        }
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
vi dy = { 0,0,1,-1 };
vi dx = { 1,-1,0,0 };
constexpr auto INF = INT_MAX/2;
constexpr auto MOD = 1000000007;

vi h;
vi memo;

int dp(int x) {
	if (memo[x] != INF)return memo[x];
	if (x == 0)return 0;
	if (x == 1)return abs(h[1] - h[0]);
	int re = min(dp(x - 2) + abs(h[x - 2] - h[x]), dp(x - 1) + abs(h[x - 1] - h[x]));
	memo[x] = re;
	return re;
}


int main() {
	int n;
	cin >> n;
	h.resize(n);
	memo.assign(n, INF);
	rep(i, n)cin >> h[i];
	memo[0] = 0;memo[1] = abs(h[1] - h[0]);

	cout << dp(n-1) << endl;
}

Measured memory_bytes: 5760
n, k = map(int, input().split())

items = dict()
for _ in range(n):
    ta, tb = map(int, input().split())
    if ta in items.keys():
        items[ta] += tb
    else:
        items[ta] = tb

items = sorted(items.items())

tb = 0
key = 0
for key, val in items:
    tb += val
    if tb >= k:
        break
print(key)

Measured memory_bytes: 14564
n,x=gets.split.map &:to_i
if x<=1 or x>=2*n-1
  puts "No"
  exit
end
puts "Yes"
if n==2
  puts [1,2,3]
  exit
end
a=Array.new(2*n-1,-1)
c=[]
if x==2*n-2
  a[n-3]=1
  a[n-2]=x
  a[n-1]=2*n-1
  a[n]=x-1
  c=(2..2*n-4).to_a
else
  a[n-3]=2*n-1
  a[n-2]=x
  a[n-1]=1
  a[n]=x+1
  c=(2..x-1).to_a+(x+2..2*n-2).to_a
end

for i in 0...2*n-1
  if a[i]==-1
    a[i]=c.pop
  end
end
puts a

Measured memory_bytes: 6524
#きっぷの問題
num=input()
for i in range(0,8):
    t=[]
    k=i
    for j in range(0,3):
        if k>=2**(2-j):
            k=k-2**(2-j)
            t.append("+")
        else:
            t.append("-")
    a=int(num[0])
    for j in range(0,3):
        if t[j]=="+":
            a+=int(num[j+1])
        else:
            a-=int(num[j+1])
    if a==7:
        print(num[0]+t[0]+num[1]+t[1]+num[2]+t[2]+num[3]+"=7")
        break

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static final char[][] button = {
		{'.',',','!','?',' '},
		{'a','b','c'},
		{'d','e','f'},
		{'g','h','i'},
		{'j','k','l'},
		{'m','n','o'},
		{'p','q','r','s'},
		{'t','u','v'},
		{'w','x','y','z'},
		};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int i=0;i<n;i++) {
			char[] s = sc.next().toCharArray();
			StringBuilder ans = new StringBuilder();
			int a = 0,b = -1;
			for(int j=0;j<s.length;j++) {
				if (s[j] == '0') {
					if (a != 0) {
						ans.append(button[a-1][b]);
					}
					a = 0;
					b = -1;
				}else{
					a = s[j] - '0';
					b = (b + 1) % button[a-1].length;
				}
			}
			System.out.println(ans.toString());
		}
	}

}

Measured memory_bytes: 21560
import sys
l = sys.stdin.readline().strip()
N, K = map(int, l.split())
l = sys.stdin.readline().strip()
A = [0] + list(map(int, l.split())) 
visited = [-1] * (len(A)+1)

remain = K
crt = 1
entrance = -1
while remain > 0:
    remain -= 1
    # check visited
    if visited[crt] == -1:
        visited[crt] = K - remain
        crt = A[crt]
    else:
        entrance = crt
        crt = A[crt]
        break
#print(entrance, remain)

if entrance == -1:
    print(crt)
else:
    loop = (K-remain) - visited[entrance] 
 
    later = remain % loop
    for i in range(later):
        crt = A[crt]
    print(crt)


Measured memory_bytes: 93620
import sys
X = int(input())

for a in range(1000):
    A = a**5
    for b in range(1000):
        B = b**5
        if A - B == X:
            print(a, b)
            sys.exit()
        elif A + B == X:
            print(a, (-1)*b)
            sys.exit()


Measured memory_bytes: 9184
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def solve(a, b, c, d):
    if a < b or d < b:
        return False
    if b < c:
        return True

    g = gcd(b, d)
    return (b + a % g - g) <= c

t = int(input())
for i in range(t):
    a, b, c, d = map(int, input().split())
    if solve(a, b, c, d):
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main{

   public static void main(String[] args){
   
      Scanner reader = new Scanner(System.in);
      int home = reader.nextInt();
      
      double interm = -0.5 + Math.sqrt(0.25 + 2*home);
      if(interm%1.0 > 0) {
         System.out.println((int)(interm + 1));
      } else {
         System.out.println((int)interm);
      }
   }
}

Measured memory_bytes: 21716
S = input()

if len(S) % 2 != 0:
    middle = len(S) // 2
    S = S[:middle] + S[middle + 1:]

half_S = int(len(S)/2)

first_S = S[:half_S]
second_S = S[half_S:]
second_S = second_S[::-1]

count = 0
for i in range(len(first_S)):
    if first_S[i] != second_S[i]:
        count += 1

print(count)



Measured memory_bytes: 3060
s, k = input(), int(input())

ans = []
a = ord('z') + 1
for i in s:
    if a - ord(i) <= k and i != 'a':
        k -= a - ord(i)
        ans.append(ord('a'))
    else:
        ans.append(ord(i))
ans[-1] += k % 26
if ans[-1] >= a:
    ans[-1] -= 26
print(*map(chr, ans), sep='')


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;


#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    ll n,m,k;
    cin>>n>>m>>k;
    vector<ll> a(n+1),b(m+1);
    for (int i = 1; i <= n; i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for (int i = 1; i <= m; i++)
    {
        cin>>b[i];
        b[i]+=b[i-1];
    }
    ll ans=0;
    ll ai=0,bi=0;
    for (int i = 0; i <= n; i++)
    {
        if(a[i]<=k)
        {
            ai=i;
        }
        else break;
    }
    ans=max(ans,ai);
    for (int i = 0; i <= m; i++)
    {
        if(b[i]>k) break;
        while (ai>0 && a[ai]+b[i]>k)
        {
            ai--;
        }
        ans=max(ans,ai+i);
    }
    

    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6420
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x)
{
    x=0;
    static int p;p=1;
    static char c;c=getchar();
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
    x*=p;
}
int n,sum;
int a[110];
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	read(n);read(sum);
	for(int i=1;i<=n;i++)
		read(a[i]);
	sort(a+1,a+n+1);
	int tot=0;
	for(int i=1;i<=n&&sum;i++)
		if(sum>=a[i])sum-=a[i],tot++;
	if(sum&&tot==n)tot--;
	cout<<tot<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] v = new int[N];
		Arrays.setAll(v, i -> sc.nextInt());
		Arrays.sort(v);
		double ans = v[0];
		for(int i = 1; i < N; i++) {
			ans = (ans + v[i]) / 2;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 29396
import bisect

N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)

B = [A[-1]]
del A[-1]
for a in reversed(A):
    if B[-1] <= a:
        B.append(a)
    else:
        B[bisect.bisect_right(B,a)] = a
    # print(B)



print(len(B))



Measured memory_bytes: 56280
=begin
1
3
4
3
10
=end
n = gets.to_i

a = []
n.times do |i|
    a.push(gets.to_i)
end

m = a[1] - a[0]
b = a[0]

(1...a.size).each do |i|
    if a[i] - b > m then
        m = a[i] - b
    end

    if a[i] < b then
        b = a[i]
    end
end

print m, "\n"



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

int main() {
	long n,m,a,b,i,j,k,ans,cur,res;
	cin >> a >> b >> n;
	
	cur=0;
	/*
	for(i=0; i<=n; i++){
		res=floor(a*i/b)-a*floor(i/b);
		cur=max(cur,res);
		
	}
	cout << cur << endl;
	*/
	if(b-1>n){
		cout << floor(a*n/b)-a*floor(n/b);
	}else{
		
		cur=b-1;
		n-=cur;
		n/=b;
		cur+=b*n;
		// cout <<cur << endl;
		cout << floor(a*cur/b)-a*floor(cur/b);
		
	}
	
	
	return 0;
}

Measured memory_bytes: 3784
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <regex>
using namespace std;

int main(){
  string s;
  cin >> s;
  bool b = true;
  if (s.length() >= 3){
	  for(int a=0;a<s.length()-2;a++){
	    if(s[a] == s[a+1]){cout<<  to_string(a+1) + " " + to_string(a+2);b = !b; break;}
   		else if (s[a] == s[a+2]){cout<< to_string(a+1) + " " + to_string(a+3);b = !b; break;}
    	else if (s[a+1] == s[a+2]){cout<< to_string(a+1) + " " + to_string(a+3);b = !b; break;}
  	}
  }else if(s[0] == s[1]){
    cout << "1 2";
    b = !b;
  }
  if(b)cout << "-1 -1";
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define hii cout << "hii" << endl
#define int ll
#define endl '\n'
#define all(s) s.begin(), s.end()
 
template <class T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T> ostream& operator << (ostream &os, const set<T> &v) { for (T i : v) os << i << ' '; return os; }
template <class T, class S> ostream& operator << (ostream &os, const pair<T, S> &v) { os << v.first << ' ' << v.second; return os; }
template <class T, class S> ostream& operator << (ostream &os, const unordered_map<T, S> &v) { for (auto i : v) os << '(' << i.first << "=>" << i.second << ')' << ' '; return os; }
 
 
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <class Arg1> void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << endl; }
    template <class Arg1, class... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args) {
        const char* sep = strchr(names + 1, ',');
        cerr.write(names, sep - names) << " : " << arg1 << "  ";
        __f(sep + 1, args...);
    }
#else
#define trace(...) 0
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#endif // ifndef ONLINE_JUDGE

const int N = 4e5 + 5;
const int MAX = 250000 + 5;
const int M = 3e5;
const int mod = 998244353;
const int MOD = 998244353;
const int INF = 1e18;
const int LG = 21;

vector<int> v;
int cache[N];

int pow(int a, int b, int m)
{
	int ans=1;
	while(b)
	{
		if(b&1)
			ans=(ans*a)%m;
		b/=2;
		a=(a*a)%m;
	}
	return ans;
}

int f(int no)
{
	if(no == 0) return 0;
	int ret = 0;
	for(int i = 0; i < v.size(); i++)
	{
		ret += v[i] * pow(2, v.size() - i - 1, no);
		ret %= no;
	}
	return ret;
}

int dp(int no)
{
	if(no == 0)
	{
		return 0;
	}
	if(cache[no] != -1)
	{
		return cache[no];
	}
	int tot = __builtin_popcount(no);
	return cache[no] = 1 + dp(no % tot);
}

void solve()
{
	int n;
	cin >> n;
	int cnt = 0;
	memset(cache, -1, sizeof(cache));
	int no = 0;
	for(int i = 0; i < n; i++)
	{
		char ch;
		cin >> ch;
		v.push_back(ch - '0');
		cnt += v.back();
		if(ch == '0') continue;
	}
	int plus = cnt + 1;
	int minus = max(cnt - 1, 0LL);
	int plusans = f(plus);
	int minusans = f(minus);
	for(int i = 0; i < n; i++)
	{
		if(v[i] == 0)
		{
			int curr = plusans + pow(2, n - i - 1, plus) + plus;
			curr %= plus;
			cout << 1 + dp(curr) << endl;
		}
		else
		{
			if(minus == 0LL)
			{
				cout << 0 << endl;
				continue;
			}
			int curr = minusans - pow(2, n - i - 1, minus) + minus;
			curr %= minus;
			cout << 1 + dp(curr) << endl;
		}
	}
}
 
int32_t main() 
{	
	    int t = 1;
	    // cin >> t;
	while(t--)solve();
	return 0;
}

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

int main(void)
{
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int L = a+b;
  int R = c+d;
  
  if(L > R)
    cout << "Left" << endl;
  else if (L < R)
    cout << "Right" << endl;
  else if (L == R)
    cout << "Balanced" << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
/*                   وتزودوا فإن خير الزاد التقوى                    */
/*       وما تدري نفس ماذا تکسب غدا وما تدري نفس باي ارض تموت      */
#include <bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define endl '\n'
#define ll long long
#define PI acos(-1)
#define watch(x) cerr<<#x<<" = { "<<x<<" }\n"
#define sz(n) n.size();
#define Mo7med_Sayed fast();
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define RT(v) return cout<<v,0;
const double EPS = (1e-7);
const ll OO = INT_MAX, mod = 1e9 + 7;
void run() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#else
#endif
}
void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
ll n, m, k, t;
vector<ll>v;
ll dp[500][500];
ll solve(int l, int r) {
	if (l == r)return 0;
	ll &ret = dp[l][r];
	if (~ret)return ret;
	ret = 1e17;
	ll s= (l ? v[l - 1] : 0);
	for (int i = l; i < r; i++) {
		ret = min(ret, solve(l, i) + solve(i + 1, r) + (v[r] - s));
	}
	return ret;
}
int main()
{
	//run();
	Mo7med_Sayed;
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		v[i] += (i ? v[i - 1] : 0);
	}
	memset(dp, -1, sizeof dp);
	RT(solve(0, n -1));
}


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

int main() {
	int n, m, a,b;
	cin >> n >> m;
	vector<vector<int>> v(n+1);
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		cout << v[i].size() << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vb = vector<bool>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define LINF 1E17
#define EPS 1E-9
#define MOD 1000000007
#define PI 3.1415926535897932384

template<class S, class T>ostream& operator<<(ostream&os, pair<S, T>p) { os << "[" << p.first << ", " << p.second << "]"; return os; };
template<class S>auto&operator<<(ostream&os, vector<S>t) { bool a = 1; for (auto s : t) { os << (a ? "" : " ") << s; a = 0; } return os; }

//int dx[]={1,1,1,0,-1,-1,-1,0},dy[8]={1,0,-1,-1,-1,0,1,1,1};
//
constexpr ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }

int n, m, r, in, inn, innn;
vi rv;
vb visited;
int ans = INF;
vvi dist;

void f(int div,int pre,int dst) {
	if (div == r) {
		ans=min(ans,dst);
	}
	else {
		rep(i, r) {
			if (!visited[i]) {
				visited[i] = true;
				if (pre == -1)f(div+1, i, 0);
				else f(div + 1, i, dst+dist[rv[pre]][rv[i]]);
				visited[i] = false;
			}
		}
	}
}

int main() {
	cin >> n >> m >> r;
	rep(i, n) {
		vi tmp(n,INF);
		dist.push_back(tmp);
	}
	rep(i, r) {
		cin >> in;
		rv.push_back(in-1);
	}
	rep(i, m) {
		cin >> in >> inn >> innn;
		dist[in-1][inn-1] = innn;
		dist[inn - 1][in - 1] = innn;
	}
	rep(k, n) {
		rep(i, n) {
			rep(j, n) {
				dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	rep(i, r) {
		visited.push_back(false);
	}
	f(0, -1, 0);
	cout << ans << endl;
}


Measured memory_bytes: 384
# このコンテスト、つまり AtCoder Beginner Contest の略称は、
# アルファベット 3 文字で ABC となっております。
# そして、ABC のうち特定の回を指すときは、
# 何回目の ABC かを 3 桁の数字で表して後ろに付け、ABC680 のように呼びます。
# 例えば ABC680 は、680 回目の ABC のことを指します。
# では、N 回目の ABC はどのように表すでしょうか、これを出力するプログラムを作成してください。

n = gets.to_i

puts "ABC" + n.to_s

Measured memory_bytes: 1788
#include <stdio.h>

int c(void *a,void *b){
  return *(int*)a - *(int*)b;
}
int a[3];
int main(void){
  scanf("%d%d%d",a,a+1,a+2);
  qsort(a,3,4,c);
  printf("%d %d %d\n",*a,a[1],a[2]);
return 0;
}

Measured memory_bytes: 600
import std.algorithm;
import std.range;
import std.stdio;
import std.math;
import std.array;
import std.string;
import std.conv;

/// 数列の読み込み
auto readNums(T = int)() {
	return readln().chomp.split.map!(to!T).array;
}

/// 数の読み込み
auto readNum(T = int)() {
	return readNums!T.front;
}

/// 指定行数読み込み
auto readRows(size_t rows) {
	return generate(() => readln().chomp).take(rows).array;
}

void main() {
    const n = readNum();
    const s = readRows(1)[0];
    size_t maxCount = 0;
    foreach(i; 0 .. s.length) {
        bool[dchar] leftSet;
        bool[dchar] rightSet;
        s[0 .. i].each!(c => leftSet[c] = true);
        s[i .. $].each!(c => rightSet[c] = true);
        maxCount = max(maxCount, leftSet.keys.filter!(k => k in rightSet).count);
    }
    writefln("%s", maxCount);
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

ll N, Q;
Graph graph;
vector<ll> ans;
map<ll, ll> cnt;

void dfs(ll u, ll prev, ll c) {
    ll plus = cnt[u];
    ans[u] = c + plus;
    for (ll v: graph[u]) {
        if (v == prev) continue;
        dfs(v, u, c + plus);
    }
}

void solve() {
    cin >> N >> Q;
    graph.resize(N);
    ans.resize(N, 0);
    rep(i, N - 1) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    rep(i, Q) {
        ll p, x;
        cin >> p >> x;
        p--;
        cnt[p] += x;
    }
    dfs(0, -1, 0);
    rep(i, N) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


Measured memory_bytes: 46208
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>
#include <map>
#include <numeric>
#include <functional>
#include <utility>

using namespace std;

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

int main(void) {
  int a, b;
  cin >> a >> b;
  cout << (b % a == 0 ? a + b : b - a) << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))

mns = len([i for i in A if i < 0])

if mns % 2 == 0:
  ans = sum([abs(i) for i in A])
else:
  ans = sum([abs(i) for i in A]) - 2 * min([abs(i) for i in A])
  
print(ans)

Measured memory_bytes: 14332
N = int(input())
T = list(map(int, input().split()))
M = int(input())

P_X = []
X = []

for i in range(M):
    p_, x_ = map(int, input().split())
    P_X.append([p_, x_])

for i in range(M):
    p = P_X[i][0] - 1
    x = P_X[i][1]
    if N >= M:
        print(sum(T) -T[p] + x)
    else:
        if p < N :
            print(sum(T) -T[p] + x)
        else :
            print(sum(T))


Measured memory_bytes: 3064
use std::io::{stdin, Read};
use std::str::FromStr;

// https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
fn main() {
    let a = read::<usize>();
    let b = read::<usize>();
    let c = read::<usize>();
    let mut v = vec![a, b, c];
    v.sort();

    let total: usize = v.iter().sum();
    let diff = 3 * v[2] - total;
    if diff % 2 == 0 {
        println!("{}", diff / 2)
    } else {
        println!("{}", 2 + diff / 2)
    }
}


Measured memory_bytes: 4352
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <queue>
#include <stack>
#include <list>
#include <functional>
#include <numeric>

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

int main() {

	char S[112345];

	scanf("%s", S);

	int l = strlen(S);

	if (l % 2) {
		int c = 0;
		char f = S[l / 2];
		while (f == S[l / 2 - c] && f == S[l / 2 + c]) c++;
		printf("%d\n", l / 2 + c);
	}
	else {
		int c = 0;
		char f = S[l / 2];
		while (f == S[l / 2 - (c + 1)] && f == S[l / 2 + c]) c++;
		printf("%d\n", l / 2 + c);
	}

	return 0;
}


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

using namespace std;
#define ll long long
#define pb push_back
#define vi vector<int>
#define vll vector<long long>
#define inf 1000000100
#define infll 1LL << 50

int main()
{
    int n;
    cin >> n;
    int g = 0;
    set<int> colors;
    while(n--)
    {
        int a;
        cin >> a;
        if(a < 3200)
        {
            colors.insert(a/400);
        }
        else
        {
            g++;
        }
    }

    cout << max(1, (int)colors.size()) << " " << colors.size() + g << endl;

}


Measured memory_bytes: 256
S = input()
T = input()
if len(S) < len(T):
    print("UNRESTORABLE")
    exit()
for i in range(len(S) - len(T), -1, -1):
    for j in range(len(T)):
        if S[i+j] not in ("?", T[j]):
            break
    else:
        ans = S[:i].replace("?", "a") + T + S[i+len(T):].replace("?", "a")
        print(ans)
        exit()
print("UNRESTORABLE")


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

int main(){
	int x,a;
	cin >> x >> a;

	if(x < a) cout << 0 << endl;
	else cout << 10 << endl;

	return 0;
}

Measured memory_bytes: 256
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function main()
	n = readline() |> parseInt
	a = readline() |> split |> parseMap |> sort
	v = 0
	for i in 1:n-1
		v += a[n-i>>1]
	end	
	println(v)
end

main()

Measured memory_bytes: 193024
#include<stdio.h>
#include<string.h>

int y[9],m[9],d[9],i;
char s[9][20];

int main(){
	strcat(s[0],"pre-meiji");
	y[1]=1868;m[1]=9;d[1]=8;strcat(s[1],"meiji");
	y[2]=1912;m[2]=7;d[2]=30;strcat(s[2],"taisho");
	y[3]=1926;m[3]=12;d[3]=25;strcat(s[3],"showa");
	y[4]=1989;m[4]=1;d[4]=8;strcat(s[4],"heisei");
	while(scanf("%d%d%d",&y[0],&m[0],&d[0])!=EOF){
		for(i=4;i>=0;i--){
			if(i==0){printf("%s\n",s[0]);break;}
			if(y[0]>y[i]){
				printf("%s %d %d %d\n",s[i],y[0]-y[i]+1,m[0],d[0]);
				break;
			}else if(y[0]==y[i]){
				if(m[0]>m[i]){printf("%s %d %d %d\n",s[i],y[0]-y[i]+1,m[0],d[0]);break;}
				else if(m[0]==m[i] && d[0]>=d[i]){printf("%s %d %d %d\n",s[i],y[0]-y[i]+1,m[0],d[0]);break;}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
//last edited at 26.8.2015 by charis

#include<iostream>
using namespace std;

int gcd(int x, int y){
	int z[1000];
	z[0]=x, z[1]=y;
	int i=2;
	int t=1;
	while(t!=0){
		if(z[i-1]==0) break;
		int t=z[i-2]%z[i-1];
		z[i]=t;
		i++;
	}
	return z[i-2];
}

int main(){
	int x,y;
	cin >> x >> y;
	
	cout << gcd(x,y) << endl;
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define repf(i,a,b) for (int i = (a); i < (b); i++)
#define repi(i,a,b) for (int i = (a); i <= (b); i++)
#define repr(i,a,b) for (int i = (a); i >= (b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(all(x));
#define RSORT(x) sort(rall(x));
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vd = vector<double>;
using vb = vector<bool>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using tiii = tuple<int, int, int>;
const ll inf = 1ll<<29;
const ll mod = 1000000007;      
const double eps = 1e-9;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

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

int main() {
  int N, D; cin >> N >> D;
  int d = 2*D+1;
  cout << (N+(d-1))/d << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  string S;
  cin >> S;
  if (S=="ABC") cout << "ARC" << endl;
  else cout << "ABC" << endl;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

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

  int ans = 0, t = 0;
  for (int i = 0; i < s.size(); i ++) {
    if ((s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C') && i == s.size() - 1) {
      t ++;
      ans = max(ans, t);
    } else if (s[i] == 'A' || s[i] == 'T' || s[i] == 'G' || s[i] == 'C') {
      t ++;
    } else {
      ans = max(ans, t);
      t = 0;
    }
    
  }


  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void) {
	int m, n=0,s=0;
	scanf("%d%d", &m, &n);
	int a[2*100000];

	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	s = a[0] + m - a[n - 1];

	for (int i = 0; i < n - 1; i++) {
		if (a[i + 1] - a[i] > s) {
			s = a[i + 1] - a[i];
		}
	}
	printf("%d", m - s);
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
  ll n;
  cin>>n;
  ll arr[n];
  ll cnt0=0;
  map<ll,ll>m;
  for(ll i=0;i<n;++i)
  {
    cin>>arr[i];
    m[arr[i]]++;
  }
  for(auto y :m)
  {
      ll x=y.second;
      cnt0+=(x*(x-1)/2);
  }
  for(ll i=0;i<n;++i)
  {
      cout<<cnt0-(m[arr[i]]-1)<<endl;
  }
}


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

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
   	int a, b;cin>>a>>b;
    int o = b;
    rep(i, a){
        if(i == 0)continue;
        o *= (b-1);
    }
	cout << o << endl;
	return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

const ll MOD = (ll)(1e9 + 7);
const int SZ = 312345;
ll inv[SZ];
ll fact[SZ];
ll fact_inv[SZ];
ll choose(int n, int r) {
  if (n < 0 || r < 0 || n < r) return 0;
  return fact[n] * fact_inv[n-r] % MOD * fact_inv[r] % MOD;
}

ll solve(int N, int M, int K) {
  ll res = 0;
  for (int m = 0; m < M; m++) {
    res += (ll)m*(m+1)/2;
  }
  (res *= N) %= MOD;
  (res *= N) %= MOD;
  (res *= choose(N*M -2, K-2)) %= MOD;
  return res;
}


int main2() {
  int N = nextInt();
  int M = nextInt();
  int K = nextInt();

  ll ans = 0;
  ans += solve(N, M, K);
  ans += solve(M, N, K);
  ans %= MOD;
  cout << ans << endl;
  return 0;
}

int main() {

{
  inv[1] = 1;
  for (int i = 2; i < SZ; i++) inv[i] = inv[(int) (MOD % i)] * (MOD - MOD / i) % MOD;
  fact[0] = 1;
  for (int i = 1; i < SZ; i++) fact[i] = fact[i-1] * i % MOD;
  fact_inv[0] = 1;
  for (int i = 1; i < SZ; i++) fact_inv[i] = fact_inv[i-1] * inv[i] % MOD;
}


#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}


Measured memory_bytes: 7552
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

int F[110][20];
int P[110][20];

signed main()
{
    int N; cin>>N;
    REP(i,N) REP(j,10) cin>>F[i][j];
    REP(i,N) REP(j,11) cin>>P[i][j];

    int ans=-1e18;
    for(int S=1;S<(1<<10);S++){
        int sum=0;
        REP(i,N){
            int cnt=0;
            REP(j,10){
                if(F[i][j] and S>>j&1) cnt++;
            }
            sum+=P[i][cnt];
        }
        ans=max(ans,sum);
    }
    cout<<ans<<endl;

}


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

int main(){
    ll x;
    cin>>x;
    rep(a,1000){
        for(ll b=-999;b<1000;b++){
            if(pow(a,5)-pow(b,5)==x){
                cout<<a<<' '<<b<<endl;
                return 0;
            }
        }
    }

}

Measured memory_bytes: 4132
import sys
S=sys.stdin.readlines()
def floor_sum(n,m,a,b):
  r=0
  x,y,z=0,0,0
  while 1:
    if b>=m:
      x=b//m
    else:
      x=0
    if a>=m:
      y=a//m
    else:
      y=0
    r+=x*n
    b-=x*m
    r+=(y*n*(n-1))>>1
    a-=y*m
    x=(a*n+b)//m
    if x==0:
      break
    y=b-x*m
    z=y//a
    r+=(n+z)*x
    a,b,n,m=m,y-z*a,x,a
  return r

for i in range(int(S[0])):
  print(floor_sum(*list(map(int,S[i+1].split()))))

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

const int INF = 1001001001;
//const ll INF = 1000000000000000000;

ll a, b, v, w, t;

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

	sort(p.begin(), p.end());
	int ans = 0;
	rep(i,k) ans += p[i];
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
using namespace std;
int main(){
    //Seiranchan!
    string a,b,c;
    cin >> a >> b;
    
    if(a.size()-b.size()==1){
        REP(i,b.size()){
            cout << a[i] << b[i];
        }
        cout << a[a.size()-1];
    }else if(b.size()-a.size()==1){
        REP(i,a.size()){
            cout << a[i] << b[i];
        }
        cout << b[b.size()-1];
    }else{
        REP(i,a.size()){
            cout << a[i] << b[i];
        }
    }
    cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<array>
#include<cmath>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;


int main() {
	int n,p[15],ans=0;
	cin >> n;
	for (int i = 0; i < n;i++) {
		cin >> p[i];
	}
	sort(p,p+n);
	for (int i = 0; i < n-1; i++) {
		ans += p[i];
	}
	cout << int(ans + p[n - 1] / 2) << endl;
}

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

int main(){
    ll n; cin >> n;
    ll mid = 1;
    for(ll i = (ll)sqrt(n) + 1; i > 1; i--){
        if(n % i == 0){
            n = n / i;
            mid = i;
            break;
        }
    }
    cout << mid + n - 2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a) ;i < (b) ;i++)
#define repr(i, a, b) for (int i = (b) - 1 ;i >= a ;i--) 
int main(){
	string s ;
	cin>>s ;
	int i = 0 ;
	for ( ;i < s.size() ;i++)
		if (s[i] == 'C')break ;
	if (i == s.size()){
		cout<<"No"<<endl ;
		return 0 ;
	}
	int j = i + 1 ;
	for ( ;j < s.size() ;j++)
		if (s[j] == 'F')break ;
	if (j == s.size()){
		cout<<"No"<<endl ;
		return 0 ;
	}

	cout<<"Yes"<<endl ;
	return 0 ;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

    public static void solve(Scanner sc) {
        String a = sc.next();
        if (a.charAt(0) == a.charAt(1) && a.charAt(0) == a.charAt(2) || a.charAt(1) == a.charAt(2) && a.charAt(1) == a.charAt(3)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 23764
while True:
    l = input().split()
    h = int(l[0])
    w = int(l[1])
    if h == 0 and w == 0:
        break
    for i in range(h):
        if i % 2 == 0:
            for j in range(w):
                if j % 2 == 0:
                    print("#", end="")
                else:
                    print(".", end="")
        else:
            for j in range(w):
                if j % 2 != 0:
                        print("#", end="")
                else:
                    print(".", end="")
        print()
    print()

Measured memory_bytes: 7000
#include<iostream>
#include<algorithm>
using namespace std;
int a[55],k,n,ans;
int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++) 
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	for (int i=1;i<=k;i++) ans+=a[i];
	cout<<ans<<endl;
	return 0;
}

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

int main(void) {
    int K, T;
    cin >> K >> T;

    vector<int> a(T, 0);
    for(int i=0;i<T;i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    for(int i=0;i<T-1;i++) {
        a.back() -= a[i];
        a[i] = 0;
        if(a.back() <= 0) {
            cout << 0;
            return 0;
        }
    }


    cout << --a.back();

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
signed main(){
  int a,b,c=0,d,e;
  cin>>a>>b;
  d= max(a,b);
  e=min(a,b);
  c=d;
  d--;
  c=c+max(d,e);
  cout<<c<<"\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
  int64_t k;
  cin >> k;
  if(k%2==1) cout << 0 << endl;
  else{
    int64_t ans=0;
    while(k){
      k/=5;
      ans+=k/2;
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;

struct BIT{
    int N;
    vector<int> bit;

    void init(int n){
        N = n;
        bit.resize(N+1);
    }
    int sum(int i){
        int s = 0;
        while(i > 0){
            s += bit[i];
            i -= i&-i;
        }
        return s;
    }
    void add(int i, int x){
        while(i <= N){
            bit[i] += x;
            i += i&-i;
        }
    }
};


int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<P> pos(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
        pos[i] = P(a[i],i);
    }
    sort(pos.begin(), pos.end());
    BIT bit;
    bit.init(n);
    for(int i=0;i<n;i++){
        bit.add(i+1,1);
    }
    ll ans = 0, pre = -1;
    for(int i=0;i<n;){
        vector<int> ls;
        pre = pos[i].first;
        while(i<n && pos[i].first == pre){
            int idx = pos[i].second+1;
            ls.push_back(idx);
            bit.add(idx,-1);
            i++;
        }
        for(int idx : ls){
            int lhs, rhs;
            lhs = bit.sum(idx);
            rhs = bit.sum(n)-bit.sum(idx);
            ans += min(lhs,rhs);
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 4988
#include <iostream>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <complex>
#include <cstdio>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

double l[4],r[4],a,b;

int main(){
	while(cin>>a>>b){
		if(a>=1.1)l[0]++;
		else if(a>=0.6)l[1]++;
		else if(a>=0.2)l[2]++;
		else l[3]++;
		if(b>=1.1)r[0]++;
		else if(b>=0.6)r[1]++;
		else if(b>=0.2)r[2]++;
		else r[3]++;
	}
	for(int i=0;i<4;i++)cout<<l[i]<<" "<<r[i]<<endl;
}

Measured memory_bytes: 0
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (unfoldr)

main :: IO ()
main = do
  (n : m : _) <- map unsafeSignedDecimal . T.words <$> T.getLine :: IO [Int]
  as <- sequence . replicate m $ unsafeSignedDecimal <$> T.getLine :: IO [Int]
  let
    bs = unfoldr next (0, as)
      where
        next (i, as@(a : as')) | i < a = Just (True, (succ i, as))
                               | otherwise = Just (False, (succ i, as'))
        next (i, _) | i < n = Just (True, (succ i, []))
                    | otherwise = Nothing
    k = fst . foldr step (1, 0) $ bs
      where
        step True (k, l) = ((k + l) `mod` modulus, k)
        step False (k, _) = (0, k)
  print k

modulus = 10 ^ 9 + 7

unsafeSignedDecimal :: T.Text -> Int
unsafeSignedDecimal s = case T.signed T.decimal s of
  Right (n, _) -> n


Measured memory_bytes: 31612
#include<stdio.h>
int main(void){
  	int N,A,B;
	scanf("%d %d %d",&N,&A,&B);	
  	if(N*A>B){
    	printf("%d\n",B);
    }else{
    	printf("%d\n",N*A);
    }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <cmath>
#define INF 100000000000
#define MOD 1000000007
#define ll long long int
using namespace std;




int main(){
 int n,k; cin>>n>>k;
 cout<<n-k+1<<endl;
  return 0;
}

Measured memory_bytes: 256