akhauriyash/Code-Regression huggingface dataset:
using System;
class Program
    {
        static void Main(string[] args)
        {
            string[] input1 = Console.ReadLine().Split(' '); 
            Console.WriteLine((Sum(int.Parse(input1[0])) * Sum(int.Parse(input1[1]))) % MOD);
        }     
        private const int MOD = 1000000007;
        static long Sum(int n){
            string[] input3 = Console.ReadLine().Split(' ');
            long Sum = 0;
            for (int i = 0; i < n; i++) {
                 Sum += long.Parse(input3[i]) * (2 * i - n + 1); 
            }
            return Sum % MOD;
         }                        
    }

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

const int Maxn = 100005;

int n, m;
int X[Maxn];
vector <int> seq;

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++)
        scanf("%d", &X[i]);
    sort(X, X + m);
    int res = X[m - 1] - X[0];
    for (int i = 0; i + 1 < m; i++)
        seq.push_back(X[i + 1] - X[i]);
    sort(seq.rbegin(), seq.rend());
    int tk = n - 1;
    for (int i = 0; i < seq.size() && i < tk; i++)
        res -= seq[i];
    printf("%d\n", res);
    return 0;
}


Measured memory_bytes: 1276
#include<iostream>
#include<cstdio>

int n,a[15];

int main()
{
	int i;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",a+i);
	int t1=1,t2=1;
	for(i=1;i<=n;i++)
	{
		t1*=3;
		if(a[i]%2==0) t2*=2;
	}
	printf("%d",t1-t2);
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7; 

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF_INT (1<<30)
#define INF_LL (1ll<<62)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

ll N,D,A,ans=0,now=0,to=0,x,h;

int main(){
    cin>>N>>D>>A;
    ll cnt[N];
    pair<ll,ll> p[N+1];
    rep(i,N){
        cin>>x>>h;
        p[i]=make_pair(x,h);
        cnt[i]=0;
    }
    p[N]=make_pair(INT64_MAX,0); 
    sort(p,p+N);
    rep(i,N){
        now+=cnt[i];
        while(true){
            if(p[to].first-p[i].first>2*D)break;
            to++;
        }
        if(now<((p[i].second+A-1)/A)){
            ll sa = (p[i].second+A-1)/A - now;
            ans+=sa;
            now+=sa;
            cnt[to]-=sa;
        }
    }
    out(ans);

    
    
}

Measured memory_bytes: 4992
#include<iostream>
#include<stdio.h>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#pragma warning(disable: 4996)
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;
using ll = long long;



int main() {
	ll N, K;
	cin >> N >> K;

	ll a = N % K;
	
	ll b = fabs(a - K);

	if (a <= b) { cout << a << endl; }
	else {
		cout << b << endl;
	}
	return 0;
}

Measured memory_bytes: 256
str = gets.chomp
n = gets.chomp.to_i
n.times do 
  c, p1, p2, p3 = gets.chomp.split /\s/

  p1 = p1.to_i
  p2 = p2.to_i

  case c
  when "print"
    puts str[p1..p2] 
  when "reverse"
    str[p1..p2] = str[p1..p2].reverse
  when "replace"
    str[p1..p2] = p3
  end
end


Measured memory_bytes: 6948
#include <iostream>
#include <sstream>
#include <algorithm>
#include <functional>
#include <iterator>
#include <bitset>
#include <string>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>

typedef   signed long long int slli;
typedef unsigned long long int ulli;
const slli MAX_SLLI = 0x7FFFFFFFFFFFFFFF;
const slli MIN_SLLI = 0x8000000000000000;
const ulli MAX_ULLI = 0xFFFFFFFFFFFFFFFF;
const ulli MIN_ULLI = 0x0000000000000000;

#define N_TIMES(i, n)     for (ulli i = 0;     i <  n; ++i)
#define N_TIMES_REV(i, n) for (slli i = n - 1; i >= 0; --i)

#ifdef __DEBUG__
template<typename T>
std::ostream& operator<<(std::ostream &os, const std::list<T> &list)
{
  const std::string delim = ", ";
  typename std::list<T>::const_iterator itr = list.begin();
  while (itr != list.end()) {
    os << *itr;
    ++itr;
    if(itr != list.end()) os << delim;
  }
  return os;
}

template<typename T>
std::ostream& operator<<(std::ostream &os, const std::vector<T> &v)
{
  const std::string delim = ", ";
  for (unsigned n = 0; n < v.size(); ++n) {
    os << v[n];
    if((n + 1) < v.size()) os << delim;
  }
  return os;
}
#endif

const unsigned BITS_WIDTH = 1e+5 + 10;
typedef std::bitset<BITS_WIDTH> Animals;

#ifdef __DEBUG__
std::ostream& operator<<(std::ostream &os, const Animals &a)
{
  os << a.to_string();
  return os;
}
#endif

bool search(unsigned N, const std::string &s, Animals &result)
{
  std::vector<Animals> dp[2];
  dp[0] = std::vector<Animals>();
  dp[1] = std::vector<Animals>();
  
  N_TIMES(i, 4) {
    dp[0].emplace_back(3 - i);
  }
  
  for (unsigned n = 1; n <= N; ++n) {
    for (const Animals &a : dp[(n - 1) % 2]) {
      Animals b(a);
      if (s[n - 1] == 'o') {
        b[n + 1] = a[n] ?  a[n - 1] : !a[n - 1];
      } else {
        b[n + 1] = a[n] ? !a[n - 1] :  a[n - 1];
      }
      dp[n % 2].push_back(b);
    }
    
    if ((n + 1) <= N) dp[(n - 1) % 2].clear();
  }
  
  for (const Animals &a : dp[N % 2]) {
    if ((a[0] == a[N + 0]) && (a[1] == a[N + 1])) {
      result = Animals(a);
      return true;
    }
  }
  
  return false;
}

int main()
{
  unsigned N;
  std::cin >> N;
  
  std::string s;
  std::cin >> s;
  
  Animals a;
  if (!search(N, s, a)) {
    std::cout << -1 << std::endl;
  } else {
    for (unsigned n = 1; n <= N; ++n) {
      std::cout << (a[n] ? 'S' : 'W');
    }
    std::cout << std::endl;
  }
  
  return 0;
}

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

using namespace std;

int main()
{
  long long int a, b, x, ansA, ansB;
  scanf("%lld %lld %lld", &a, &b, &x);

  ansB = b / x;

  if (a == 0)
    ansA = -1;
  else
    ansA = (a - 1) / x;

  printf("%lld", ansB - ansA);
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.__q = l
        heapq.heapify(self.__q)
        return

    def push(self, n):
        heapq.heappush(self.__q, n)
        return

    def pop(self):
        return heapq.heappop(self.__q)


MOD = int(1e09) + 7
INF = int(1e15)


def calc(N):
    return sum(int(x) for x in str(N))


def main():
    # sys.stdin = open("sample.txt")
    S = Scanner.string()
    if len(S) == 26:
        if list(S) == list(reversed(list(string.ascii_lowercase))):
            print(-1)
            return
        i = 0
        for i in reversed(range(25)):
            if S[i] < S[i+1]:
                break
        ans = S[:i]
        k = S[i]
        for s in sorted(S[i+1:]):
            if k < s:
                ans += s
                break
        print(ans)
        return
    else:
        T = Counter(S)
        for c in string.ascii_lowercase:
            if T[c] == 0:
                print(S + c)
                return
    return


if __name__ == "__main__":
    main()


Measured memory_bytes: 41020
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >> n;
  int ans = INT_MAX;
  auto chmin = [&](int &a, int b){
    if(a > b){a = b;}
  };
  for(int i = 0; i < n; i++){
    int p; cin >> p;
    int cnt = 0;
    while(p % 2 == 0){
      cnt++;
      p /= 2;
    }
    chmin(ans, cnt);
  }
  cout << ans << endl;
}

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

int main() {
    int i,j,k,n,f,c,t[2][100],a[2][100],b[2][100];
    while(cin >> n && n!=0) {
	for (i=0;i<2;i++) for (j=0;j<n;j++) { cin >> t[i][j]; a[i][j]=999; b[i][j]=j;}
	for (i=0;i<2;i++) {
	     for (j=0;j<n;j++) if (t[i][j]==2) { for (k=j;t[i][k]==2;k++) b[i][k]=j-1; j=k;} 
	     for (j=n-1;j>=0;j--) { if (t[i][j]==1) { for (k=j;t[i][k]==1;k--) { b[i][k]=j; if (k==0) break; } j=k;}}
	 }
	if (b[0][0]>=0) a[0][b[0][0]]=0; 
	if (b[1][0]>=0) a[1][b[1][0]]=0;
	c=0; f=1; 
	while(f==1) {
		f=0;
		for (i=0;i<2;i++) for (j=0;j<n;j++) { 
		if (a[i][j]==c) {
		if (b[0][0]==n-1) { f=100; j=i=n+1; break;}	
		if (b[1-i][j]>=0) if (a[1-i][b[1-i][j]]==999) {a[1-i][b[1-i][j]]=c+1; f=1;}
		if (b[1-i][j+1]>=0) if (a[1-i][b[1-i][j+1]]==999) {a[1-i][b[1-i][j+1]]=c+1; f=1;}
		if (b[1-i][j+2]>=0 && j+2<n) if (a[1-i][b[1-i][j+2]]==999) {a[1-i][b[1-i][j+2]]=c+1; f=1;}
		    }
     	}
     	if (f==1) if (a[0][n-1]<999 || a[1][n-1]<999) { f=100+c+1; break;}
     	if (f==0) break;
     	c++;
	}
	if (f==0) cout << "NA" << endl; else cout << f-100 << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define lcm(x, y) ((x) * (y) / __gcd((x), (y)))
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#define mp make_pair
#include <iostream>
#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

int main()
{
    fastinput;
    LL n, i, j, k, t;
    cin >> n;
    long double p[n + 1];
    long double dp[n + 1][n + 1];

    for(i=1;i<=n;i++)
    {
        cin>>p[i];
        //debug(p[i]);
    }
    for(i=1;i<=n;i++)
    {
        //debug(i);
        for(j=0;j<=n;j++)
        {
            //debug(j);
            dp[i][j]=0;
        }
    }

    dp[1][1]=p[1];
    dp[1][0]=1-p[1];

    for(i=2;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]*(1-p[i]);
    }

    for(i=2;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            dp[i][j]=p[i]*dp[i-1][j-1]+(1-p[i])*dp[i-1][j];
        }
    }

    /*for(i=1;i<=n;i++)
    {
        for(j=0;j<=n;j++)
        {
            cout<<"dp["<<i<<"]["<<j<<"] is "<<dp[i][j]<<endl;
        }
    }*/

    long double ans=0;

    for(i=n/2+1;i<=n;i++)
    {
        ans+=dp[n][i];
    }

    printf("%.10Lf\n",ans);





    return 0;
}

/* stuff you should look for
    * int overflow, 
    * array bounds,
    * edge cases (constraints ZERO)
    * Overlapping of Indices on addition/subtraction
    * special cases (n=1?), set tle,
    * see nested loop does not have same LOOP CONTROL VARIABLES,
*/


Measured memory_bytes: 140928
n=int(input())
B=list(map(int,input().split()))  
C=[0]*n
C[0]=B[0]
C[1]=B[0]
for i in range(1,n-1):
    if C[i]>B[i]:
        C[i+1]=B[i]
        C[i]=B[i]
    else:
        C[i+1]=B[i]
print(sum(C))
    



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

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ; 
ll _abs (ll x ) { return (x>0?x:-x); }

const int N = 1e5+5   ;

int dp[N][3] ;  // max fun at day i new activity day with j 
int fun[N][3] , n ;  // FUN AT DAY i activitiy j 
int solve (int i , int l ){
    int& r  =dp[i][l] ; 
    if( r != -1 )return r; 
    if( i== n )return 0 ; 
    for(int j=0;j<3;j++)if(l!=j)r=max(fun[i][j]+solve(i+1,j),r); 
    return r ; 
}
int main(){
    cin>> n ; 
    for(int i =0 ; i < n ;i++ ){
        cin>>fun[i][0]>>fun[i][1]>>fun[i][2]; 
    }
    // base case 
  //  memset(dp,-1,sizeof dp ) ; cout<<solve(0,3)<<endl; return 0 ; 
    for(int i=0;i<3;i++)dp[0][i] = fun[0][i]; 
    for(int i=1;i<n;i++){
        for(int j = 0 ; j < 3 ; j++ ){// new activity
            for(int k=0;k<3;k++){// last activity
                if( j != k ) // cant be same activity twice
                    dp[i][j] = max(dp[i][j] , dp[i-1][k] + fun[i][j]); 
            }
        }
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl; 
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <string.h>
#include<iomanip>
#include <iterator>
#include <locale>

#define all(a) a.begin(),a.end()
#define VV(T) vector<vector< T > >
#define rep(i,N) for(int i = 0; i <N; i++)
#define repsg(i,s,g) for(int i = s; i <g; i++)
#define name(x) #x
using namespace std;

const int INF = INT_MAX;
const long long INFL =LONG_LONG_MAX;
const double PI = atan(1)*4;
const int MOD = pow(10,9)+7;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

typedef long long ll,LL;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
typedef pair<int,int> pii;
typedef pair<LL, LL> pLL;


// vector入力
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) is >> x;
    return is;
}
// vector出力
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
    for(int i=0; i<vec.size(); i++){
        os << vec[i] << ( i+1 == vec.size() ? "" : " " );
    }
    return os;
}

ll gcb(ll a, ll b){/// ユークリッドの互除法: O(log)
    
    if(b == 0) return a;
    
    return gcb(b,a%b);
}


ll lcm(ll a, ll b){
    
    return  a/gcb(a,b) * b; ///gcbは約数
}

int getDigit(ll num){
    return log10(abs(num))+1;
}


int main() {
    ll n;cin>>n;vector<ll>A(n);cin>>A;
    map<ll,ll> mp;
    mp[0]++;
    mp[A[0]]++;
    for(auto i = 1;i<n;i++){
        A[i] += A[i-1];
        mp[A[i]]++;
    }
    
    ll ans = 0;
    
    for(auto v:mp){
        ans += ((v.second)*(v.second-1))/2;
    }
    cout<<ans<<endl;
    
    return 0;
}










Measured memory_bytes: 14336
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	k := nextInt()
	list := make([]int, n)
	full := 0
	absmin := 999
	absminIdx := 0

	for i := 0; i < n; i++ {
		list[i] = k + i
		full += list[i]

		if abs(list[i]) < absmin {
			absmin = abs(list[i])
			absminIdx = i
		}
	}

	fmt.Println(full - list[absminIdx])

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

// ---- readfunc
func scanInit() {
	const cap = 64 * 1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1788
eval"N,K="+`tr \\  ,`
m=10**9+7
*I=x=y=1
s=0
1.upto([N,K+1].min){|i|s+=x*y
I<<r=i<2?1:m/i*-I[m%i]%m
x=x*(N-i+1)*r%m
y=y*(N-i)*r%m}
p s%m

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

vector<int> v(1e5+7);

ll solve(int n)
{
    ll sum = 0;
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        if (i % 2) {
            if (sum + v[i] <= 0) ans += abs(sum + v[i]) + 1, sum = 1;
            else sum += v[i];
        }

        else {
            if (sum + v[i] >= 0) ans += abs(sum + v[i]) + 1, sum = -1;
            else sum += v[i];
        }
    }

    return ans;
}

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

    ll ans = solve(n);

    for (int i = 0; i < n; i++) v[i] *= -1;
    ans = min(ans, solve(n));

    cout << ans;
}


Measured memory_bytes: 640
n,m,x=map(int,input().split())
cam = [list(map(int, input().split())) for i in range(n)]
ans=10000**12

for i in range(2**n):
    a=[0]*m
    cst=0
    for j in range(n):
        bag=[]
        if (i>>j)&1:
            cst+=cam[j][0]
            for k in range(1,m+1):
                a[k-1]+=cam[j][k]
    if all(elem >= x for elem in a):
        ans=min(ans,cst)
    
if ans<10000**12:
    print(ans)
else:
    print(-1)

Measured memory_bytes: 9180
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define min(a, b) (a > b ? b : a)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) { rep(_, n) cout << a[_] << " "; cout << endl; }
#define outp(a, n) { cout << endl; rep(_, n) cout << a[_].F << " " << a[_].S << endl; }
#define SZ(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
#define FIX(a) fixed << setprecision(a)
#define LB(v, n) (int)(lower_bound(all(v), n) - v.begin())
#define UB(v, n) (int)(upper_bound(all(v), n) - v.begin())
ll pow(ll a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll nck(int n, int k) { ll ret = 1; rep(i, k) {ret *= n - i; ret /= i + 1; } return ret; } // n <= 60
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }




ll dp[100001][2]; // a1 + ... + ai, j = 1 -> iを反転
void solve() {
    
    
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    // const ll INF = 1e18;
    // dp[0][0] = 0;
    // dp[0][1] = -INF;
    dp[1][0] = a[0];
    dp[1][1] = -a[0];
    
    rep3(i, 1, n) {
        dp[i + 1][0] = max(dp[i][0] + a[i], dp[i][1] - a[i]);
        dp[i + 1][1] = max(dp[i][0] - a[i], dp[i][1] + a[i]);
    }
    
    out(dp[n][0]);
    
    // rep(j, 2) { rep(i, n + 1) cout << dp[i][j] << " "; cout << endl; }
}


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



Measured memory_bytes: 2176
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll x;std::cin >> x;
  for(int i=1;i<=10000;i++){
    ll n = x;
    n-=i*100;
    if(n>=0&&n<=5*i){
      std::cout << 1 << '\n';
      return 0;
    }
  }
  std::cout << 0 << '\n';
  return 0;
}


Measured memory_bytes: 888
using System;

class Program {
    static void Main() {
        for (string line; (line = Console.ReadLine()) != "0";) {
            var L = int.Parse(line);
            var reached = false;

            for (var i = 1; i <= 12; i++) {
                var l = Console.ReadLine().Split(' ');
                L -= int.Parse(l[0]) - int.Parse(l[1]);

                if (L <= 0 && !reached) {
                    Console.WriteLine(i);
                    reached = true;
                }
            }
            
            if (!reached)
                Console.WriteLine("NA");
        }
    }
}

Measured memory_bytes: 9324
from collections import Counter
N, M = map(int, input().split())
mod = 10 ** 9 + 7


# 素因数分解
def prime_factorization(n):
    table = []
    for x in range(2, int(n**0.5)+2):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


# 重複組み合わせ（Nが小さきとき）
def nHk(n, k):
    value = 1
    nk = n + k - 1
    k = min(nk-k, k)
    for i in range(k):
        value = (value * nk) % mod
        nk -= 1
    for x in range(1, k + 1):
        value = (value * pow(x, mod-2, mod)) % mod
    return value


X = Counter(prime_factorization(M)).values()
ans = 1
for x in X:
    ans *= nHk(N, x) % mod

print(ans % mod)


Measured memory_bytes: 3316
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    long long a, b, c;
    cin >> a >> b >> c;
    if (a * b * 4 < (c - a - b) * (c - a - b) && (c - a - b) > 0)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
  size_t N, R;
  int T;
  scanf("%zu %zu %d", &N, &R, &T);

  std::vector<int> p(N);
  for (auto& pi: p) scanf("%d", &pi);

  int res = 0;
  std::vector<int> a(R);
  for (int i = 1; i <= T; ++i) {
    for (size_t j = 0; j < N; ++j) {
      size_t pos = (p[j] * i) % R;
      if (a[pos] == 0) {
        ++res;
      } else {
        --a[pos];
      }
    }

    if (i > 1) {
      for (size_t j = 0; j < N; ++j) {
        size_t pos = (p[j] * i) % R;
        ++a[pos];
      }
    }
  }

  printf("%d\n", res);
}



Measured memory_bytes: 2736
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    int left = A + B;
    int right = C + D;
    if (left > right) {
        cout << "Left" << endl;
    } else if (left < right) {
        cout << "Right" << endl;
    } else {
        cout << "Balanced" << endl;
    }
    return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>
int main(void){
    int A, B, K;
    int counter=1;
    int Kcount=0;
    int max;
    scanf("%d %d %d", &A, &B, &K);
    if (A>=B){
        max = A;
    }
    else{
        max = B;
    }
    counter =max;
    while(counter>0){
        if((A%counter ==0)&&(B%counter==0)){
            Kcount++;
            if(Kcount==K){
                printf("%d", counter);
            }
        }
        counter--;
    }
    return 0;
}

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

vector<int> p;

void precompute(const int& n, bool is_c[]) {
    for (int i = 2; i <= n; ++i) {
        if (!is_c[i]) p.push_back(i);
        for (int j = 0; j < p.size() && p[j] * i <= n; ++j) {
            is_c[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
}


int main() {
    int n;
    cin >> n;
    int a[n];
    int t(1), mx(1);
    bool paired(true);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    mx = max(mx, a[i]);
  }
  //cout << mx << endl;
  
         int is_p[mx + 1] = {};
  bool is_c[mx + 1] = {};
  precompute(mx, is_c);
  //cout << p.size() << endl;
    for (int i = 0; i < n; ++i) {
        if (i) {
            t = gcd(t, a[i]);
        } else {
            t = a[i];
        }
      if (a[i] == 1) continue;
      int xx = a[i];
      if (!paired) continue;
      if (!is_c[xx]) {
        if (++is_p[xx] > 1)
          paired = false;
        continue;
      }
        for (int pp: p) {
          //cout << pp << endl;
          if (pp > a[i]) break;
          if (a[i] % pp) continue;
          if (++is_p[pp] > 1) {
            paired = false;
            break;
          }
          while (a[i] % pp == 0) {
            a[i] /= pp;
          }
        }
      /*
        if (a[i] == xx) {
          is_p[xx]++;
          if (is_p[xx] > 1) {
            //cout << 'a' << xx << endl;
            paired = false;
          }
        }*/
    }
    if (t == 1) {
        if (paired) {
            cout << "pairwise coprime\n";
        } else {
            cout << "setwise coprime\n";
        }
    } else {
        cout << "not coprime\n";
    }
    return 0;
};

Measured memory_bytes: 12640
#include<iostream>
#include<list>
using namespace std;
int n;
main()
{
	while(cin>>n,n)
	{
		list<int>b;
		long sum=0;
		for(int i=0;i<n;i++)
		{
			int a;cin>>a;
			sum+=a;
			b.push_back(a);
		}
		bool f=0;
		for(long i=1;;i++)
		{
			if(i*(i+1)/2==sum)
			{
				f=1;
				break;
			}
			else if(i*(i+1)/2>sum)break;
		}
		if(!f)
		{
			cout<<-1<<endl;
			continue;
		}
		f=1;
		auto it=b.begin();
		int p=0;
		while(it!=b.end())
		{
			if(*it==p+1)
			{
				it++;
				p++;
			}
			else
			{
				f=0;
				break;
			}
		}
		if(f)
		{
			cout<<0<<endl;
			continue;
		}
		f=0;
		for(int i=1;i<=10000;i++)
		{
			int p=b.size();
			auto it=b.begin();
			while(it!=b.end())
			{
				if(*it>1)
				{
					--*it++;
				}
				else
				{
					it=b.erase(it);
				}
			}
			b.push_back(p);
			bool flag=1;
			it=b.begin();
			p=0;
			while(it!=b.end())
			{
				if(*it==p+1)
				{
					it++;
					p++;
				}
				else
				{
					flag=0;
					break;
				}
			}
			if(flag)
			{
				f=1;
				cout<<i<<endl;
				break;
			}
		}
		if(!f)cout<<-1<<endl;
	}
}



Measured memory_bytes: 3116
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
  string s, t;
  cin >> s >> t;
 
  std::sort(s.begin(), s.end());
  std::sort(t.begin(), t.end());
  std::reverse(t.begin(), t.end());
  if (s < t) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
 
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
typedef long long ll;

int main(){
  ll n;
  cin>>n;
  if(n%2==0){
    ll ans=0;
    for(ll i=10;i<lINF;i*=5){
      ans+=n/i;
    }
    cout<<ans<<endl;
  }
  else{
    cout<<0<<endl;
  }
  return(0);
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::collections::{HashSet,HashMap};
#[allow(unused_imports)]
use std::collections::{BTreeSet, BTreeMap};
#[allow(unused_imports)]
use std::collections::BinaryHeap;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input!{
        n:i32, m:i32,
    }
    let ans = (1900 * m + 100 * (n - m)) * i32::pow(2, m as u32);
    puts!("{}\n", ans);
    
}

Measured memory_bytes: 4352
#include<iostream>
#include<iomanip>
#include<string>
#include<queue>
#include<vector>
#include<algorithm>
#include<tuple>
#include<numeric>
#include<map>
#include<cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<(int) (n);i++)
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;}
using namespace std;
int main(){
  int n,cnt=1;
  cin>>n;
  vector<string>vec(n);
  rep(i,n){
    string s;
    cin>>s;
    vec[i]=s;
  }
  sort(vec.begin(),vec.end());
  string f1=vec[0],f2;
  rep(i,n){
    f2=vec[i];
    if(f1!=f2)cnt++;
    f1=f2;
  }
  cout<<cnt;

  return 0;
}


Measured memory_bytes: 9604
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iomanip>
   
using namespace std;
   
string str[2];
int s, n, t, m, lt, rt, t_w, t_t;
double p;
   
int conv(string s){
  string data[7] = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat"};  
  for(int i=0;i<7;i++) if(s == data[i]) return i;
  if(s == "All") return -1;
}
   
int calc(int s_w, int s_t){
  int cnt = 0;
  for(int k=0;k<m;k++){
    int f_w = s_w;
    int f_t = s_t + s;
    if(f_t >= 24 * 60){
      f_t -= 24 * 60;
      f_w = (f_w + 1) % 7;
    }
    bool f = false;
    if(t_w == -1 || (t_w == s_w && t_w == f_w)){
      if(t_t == 0){
        if(0 <= s_t && s_t < 24 * 60 && 0 <= f_t && f_t < 24 * 60) f = true;
      }
      if(t_t == 1){
        if(6 * 60 <= s_t && s_t < 18 * 60 && 6 * 60 <= f_t && f_t < 18 * 60) f = true;
      }
      if(t_t == 2){
        if(((18 * 60 <= s_t && s_t < 24 * 60) || (0 <= s_t && s_t < 6 * 60))
           && ((18 * 60 <= f_t && f_t < 24 * 60) || (0 <= f_t && f_t < 6 * 60))) f = true;
      }
    }
    if(f) cnt++;
    s_t += t;
    if(s_t >= 24 * 60){
      s_t -= 24 * 60;
      s_w = (s_w + 1) % 7;
    }
  }
  return cnt;
}
   
main(){
  while(cin >> s >> n >> t >> str[0] >> str[1] >> p >> m && (s|n|t|m) && str[0] != "None" && str[1] != "None"){
    t_w = conv(str[0]);
    if(str[1] == "All") t_t = 0;
    if(str[1] == "Day") t_t = 1;
    if(str[1] == "Night") t_t = 2;
    double ans = 0.0;
    for(int i=0;i<7;i++) for(int j=0;j<24*60;j++) ans = max(ans, 1.0 - pow((p - 1.0) / p, n * calc(i, j)));
    printf("%.10f\n", ans);
  }
}

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

int main (){
    int n;
    int ans=0;
    int sum=0;
    cin >> n;
    vector<int>step(n);
    rep(i,n){
        int num;
        cin >> num;
        step.at(i)=num;
    }
    rep(i,n-1){
        if(step.at(i+1)-step.at(i)<=0) sum++;
        else sum=0;
        ans=max(ans,sum); 
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int main(){
  int h,w; cin >> h >> w;
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      string s; cin >> s;
      if(s == "snuke")cout << char('A'+j) << i+1 << endl;
    }
  }
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
int n;
long long a[100000];
long long x[100000]={0};
int main()
{
	cin>>n;
    for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
    int s=1;
	for(int i=0;i<n;i++)
	{
		x[0]+=a[i]*s;
		s*=-1;
	}

	for(int i=n-1;i>0;i--)
	{
		x[i]=2*a[i]-x[(i + 1)%n];
	}
	for(int i=0;i<n;i++)
	{
		cout<<x[i]<<" ";
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 2816
#include<iostream>
using namespace std;
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a==1 && b==1){
    cout<<"Open"<<'\n';
  }
  else if(c==1){
    cout<<"Open"<<'\n';
  }
  else if(a==0 && b==0 && c==0){
    cout<<"Close"<<'\n';
  }
  else{
    cout<<"Close"<<'\n';
  }
  

    
  
  return(0);
}



Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <atcoder/all>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;
using namespace atcoder;
using LL = long long;
const LL mod = 998244353;

struct S{
  LL a, siz;
};

struct F{
  LL b, c;
  F(LL b, LL c): b(b), c(c) {}
};

S op(S x, S y){
  return S{(x.a + y.a) % mod, x.siz + y.siz};
}

S e(){
  return S{0LL, 0LL};
}

S mapping(F f, S x){
  return S{(f.b * x.a + f.c * x.siz) % mod, x.siz};
}

F composition(F f, F g){
  return F((g.b * f.b) % mod, (f.b * g.c + f.c) % mod);
}

F id(){
  return F(1, 0);
}

int main(){
  int N, Q;
  cin >> N >> Q;
  vector<S> A(N);
  rep(i,N){
    LL a;
    cin >> a;
    A[i] = S{a, 1LL};
  }
  lazy_segtree<S, op, e, F, mapping, composition, id> lseg(A);
  rep(i,Q){
    int q;
    cin >> q;
    if(q == 0){
      int l, r;
      LL b, c;
      cin >> l >> r >> b >> c;
      F f(b, c);
      lseg.apply(l, r, f);
    }
    else{
      int l, r;
      cin >> l >> r;
      S ans = lseg.prod(l, r);
      cout << ans.a % mod << endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 35512
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val vList = readLine()!!.split(' ').map(String::toDouble).sorted()
    var ans = vList[0]
    for (i in 1 until n) {
        ans = (ans + vList[i]) / 2.0
    }
    println(ans)
}

Measured memory_bytes: 37876
/* ファイル名：ITP1_5_C.c	*/
/* 内容：たてH cm よこ W cm のチェック柄の長方形を描く	*/
/*       チェック柄は'#'と'.'の2つの文字で描く			*/

/* include	*/
#include <stdio.h>

/* 外部変数宣言	*/

/* プロトタイプ宣言	*/

/* 関数名:main	*/
/* 処理内容:たてH cm よこ W cm のチェック柄の長方形を描く	*/
int main( void )
{
	/* 内部変数定義	*/
	/* 入力	*/
	int H;	/* たて	*/
	int W;	/* よこ	*/
	
	/*処理*/
	int i;	/* ループ用変数1	*/
	int j;	/* ループ用変数2	*/
	
	/* 無限ループ	*/
	while(1){
		scanf("%d %d",&H,&W);	/* たてとよこを取得	*/
		
		/* たてとよこに0が入力された場合	*/
		if((H == 0) 
		&& (W == 0)){
			break;	/* 処理を終了する*/
		}
		/* たてとよこに0以外が入力された場合 */
		else{
			/* たての長さだけループ	*/
			for(i = 0; i < H; i++){
				/* 奇数行を出力する場合	*/
				if((i + 1) % 2 == 1){
					for(j = 0; j < W; j++){
						/* 奇数列を出力する場合	*/
						if((j + 1) % 2 == 1){
							printf("#");	/* '#'を出力	*/
						}
						/* 偶数列を出力する場合	*/
						else{
							printf(".");	/* '.'を出力	*/
						}
					}
				}
				
				/* 偶数行を出力する場合	*/
				else{
					for(j = 0; j < W; j++){
						/* 奇数列を出力する場合	*/
						if((j + 1) % 2 == 1){
							printf(".");	/* '.'を出力	*/
						}
						/* 偶数列を出力する場合	*/
						else{
							printf("#");	/* '#'を出力	*/
						}
					}
				}
				printf("\n");/* 行の最後で改行を出力	*/
			}
			
			printf("\n");/* 次のデータセットの出力の為改行	*/
		}
	}
	return 0;
}



Measured memory_bytes: 2056
#include <iostream>
#include <cstdio>

using namespace std;

int dp[1 << 16];
int N;

const int MAX = 10000000;

int clearTime[20][20];

int minTime(int idx, int state) {
  int mn = clearTime[idx][0];
  for (int i = 0; i < N; i++) {
    if (state & (1 << i)) {
      mn = min(clearTime[idx][i + 1], mn);
    }
  }
  //printf("%d, %d, %d\n", idx, state, mn);
  return mn;
}

void print_state(int state) {
  printf("print state\n");
  for (int i = 0; i < N; i++) {
    if (state & (1 << i)) {
      printf("%d ", i);
    }
  }
  printf("\n");
}

void solve() {
  dp[0] = 0;
  for (int state = 1; state < (1 << N); state++) {
    int mn = MAX;
    for (int i = 0; i < N; i++) {
      if (state & (1 << i)) {
        int prevState = state & (~(1 << i));
        //print_state(prevState);
        mn = min(mn, minTime(i, prevState) + dp[prevState]);
      }
    }
    dp[state] = mn;
  }
  /*
  for (int i = 0; i < (1 << N); i++) {
    print_state(i);
    printf("%d\n", dp[i]);
  }
  */
  printf("%d\n", dp[(1 << N) - 1]);
}

void print_time() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= N; j++) {
      printf("%d ", clearTime[i][j]);
    }
    printf("\n");
  }
}

int main() {
  while (true) {
    scanf("%d ", &N);
    if (N == 0) {
      return 0;
    } 
    for (int i = 0; i < N; i++) {
      int t;
      scanf("%d ", &t);
      clearTime[i][0] = t;
      for (int j = 1; j <= N; j++) {
        scanf("%d ", &t);
        clearTime[i][j] = t;
      }
    }
    // print_time();
    solve();
  }
}

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

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

int main() {
    int X,A;
    cin >> X >> A;
    if(X<A){
        cout << 0 << endl;
    }else{
        cout << 10 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <list>
#include <algorithm>
#include <map>
#include <math.h>
#include <set>
#include <string>
#include <algorithm>
#include <list>
#include <string.h>
#include <unordered_map>
#include <ctype.h>
#include <queue>
#include <numeric>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <stack>
#include <ctime>
#define  lld  long long int
#define rep(i,start,end) for(lld i = start;i<end;i++)
#define newline cout << endl
#define fastio ios:: sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define in insert
#define mp make_pair
#define se second
#define fi first
#define starttime chrono::time_point<chrono::system_clock> start, end; start = chrono::system_clock::now()
#define showtime end = chrono::system_clock::now();  chrono::duration<double> elapsed_seconds = end - start; time_t end_time = chrono::system_clock::to_time_t(end); cout << "elapsed time: " << elapsed_seconds.count() << "s\n"
#define INF 1e17
lld MOD =  (lld)(1e19+7);
#define mh make heap
#define ph push_heap
#define poph pop_heap
#define openf   freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
using namespace std;
lld add(long long a, long long b){return ((a%MOD)+(b%MOD))%MOD;}
lld mul(long long a, long long b){return ((a%MOD)*(b%MOD))%MOD;}
lld sub(long long a, long long b){lld ans = ((a%MOD-b%MOD))%MOD; if(ans<0) ans += MOD; return ans;}
lld modInverse(lld a ){   lld m = MOD,m0 = m, y = 0, x = 1;  if (m == 1) return 0;   while (a > 1) {  lld q = a / m, t = m;  m = a % m, a = t, t = y;          y = x - q * y, x = t;   } if (x < 0)  x += m0; return x; } 
lld gcd(lld a, lld b){if (b == 0) return a; return gcd(b, a % b);}
void MAIN(lld i,lld t);
int get(){lld t;cin>>t; ; return t;}
template<class T> int logd(T name){cout<<name<<endl; return 0;}
void test(int t) { for(lld i = 0;i<t;i++){MAIN(i,t); cout <<endl;} }
lld power(lld x, lld y) { lld res = 1; x = x%MOD; if(x==0) return 0;   while (y > 0) {   if (y & 1)      res = (res*x)%MOD; y = y>>1; x = (x*x)%MOD;} return res; }
#define all(v) (v).begin(),(v).end()
lld popcount(lld x){return __builtin_popcountll(x);}
lld lcm(lld a,lld b){ return (a*b)/gcd(a,b);}

void MAIN(lld current_test_case,lld total_test_cases){
    lld n; cin >> n;
    cout << n*(1+n+n*n) << endl;

}   
int main(){  
    fastio;
    #ifndef ONLINE_JUDGE 
     openf
    #endif
    test(1);
    return 0;
}



Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};

int n,m;
int x[100010],y[100010];

int calc(int z[],int l){
  int ans=0;
  for(int k=1;k<=l;k++){
    ans+=((((k-1))*(z[k]%MOD))%MOD-((((l-k))*(z[k]%MOD)%MOD))%MOD+MOD)%MOD;
    ans%=MOD;
  }

  return ans;
}

signed main(){
  cin>>n>>m;
  for(int t=1;t<=n;t++)cin>>x[t];
  for(int t=1;t<=m;t++)cin>>y[t];

  cout<<((calc(x,n)%MOD)*(calc(y,m)%MOD))%MOD<<"\n";
  return 0;
}


Measured memory_bytes: 1792
N, Q = map(int, input().split())
S = input()
query = [input().split() for i in range(Q)]
AC = [0 for i in range(N+1)]

for i in range(N):
    AC[i+1] = AC[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
    L, R = int(query[i][0]), int(query[i][1])
    print(AC[R-1] - AC[L-1])

Measured memory_bytes: 37092
#include<bits/stdc++.h>
using namespace std;
#define rep(_,a,b) for(int _=a;_<b;_++)
#define per(_,a,b) for(int _=b-1;_>=a;_--)
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
typedef long long ll;

char a[10][10];
bool choose_hang[10],choose_lie[10];
int h,w,k,cnt,ans=0;

void dfs(int hang,int lie){
    if(hang<h){
        choose_hang[hang]=false;
        dfs(hang+1,lie);
        choose_hang[hang]=true;
        dfs(hang+1,lie);
    }
    else if(lie<w){
        choose_lie[lie]=false;
        dfs(hang,lie+1);
        choose_lie[lie]=true;
        dfs(hang,lie+1);
    }
    else if(hang>=h&&lie>=w){
        cnt=0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(a[i][j]=='#'&&choose_hang[i]&&choose_lie[j]==true) cnt++;
            }
        }
        if(cnt==k) ans++;
        return;
    }
}

int main(){
    scanf("%d%d%d",&h,&w,&k);
    rep(i,0,h){
        rep(j,0,w){
            cin>>a[i][j];
        }
    }
    dfs(0,0);
    cout<<ans;
}


Measured memory_bytes: 3712
# -*- coding: utf-8 -*-

import sys

def parse_input(lines_as_string = None):

    lines = []
    if lines_as_string is None:
        for line in sys.stdin:
            lines.append(line)
    else:
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    # 出力
    nm = lines[0].split(" ")
    n = int(nm[0])
    m = int(nm[1])

    rows = []
    for i in range(1, n+1):
        rows.append([int(e) for e in lines[i].split(" ")])

    return (n, m, rows)

def solve(n, m, rows):

    result = []
    for k in range(1, m + 1):
        tmp = []
        for i in range(0, n):
#            print(rows[i])
            r = rows[i]
#            print(r[1:r[0] + 1])
            if k in r[1:r[0]+1]:
               tmp.append(i+1)
        if len(tmp) == n:
            result.append(k)

    return len(result)

def main():

    n, m, rows = parse_input()
    print("%d" % solve(n, m, rows))

if __name__ == '__main__':

    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using i128 = boost::multiprecision::int128_t;
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using VVV = vector<VV>;
using VVVll = vector<VVll>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const ld PI    = acos(-1.0);
const int MOD  = int(1e9)+7;


int main() {
  int t; cin >> t;
  rep(_, t) {
    int n; cin >> n;
    Vll a(n); cin >> a;
    string s; cin >> s;

    Vll b;
    bool ans = true;
    drep(i, n) {
      for (auto v : b) chmin(a[i], a[i]^v);
      if (a[i]) {
        if (s[i] == '0') b.push_back(a[i]);
        else ans = false;
      }
    }
    cout << (ans ? 0 : 1) << "\n";
  }
  return 0;
}


Measured memory_bytes: 3592
from math import gcd, sqrt

def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main():
    n = int(input())
    a = list(map(int, input().split()))
    f = True
    divset = set()
    for v in a:
        st = Divisor_Set(v)
        st.remove(1)
        for el in st:
            if el in divset:
                f = False
                break
            divset.add(el)
        if not f:
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Measured memory_bytes: 196636
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn yn(result: bool) {
    if result {
        println!("Yes");
    } else {
        println!("No");
    }
}

use std::collections::BinaryHeap;
fn main() {
    let v = read_vec::<u32>();
    let n = v[0] as usize;
    let m = v[1];
    let a = read_vec::<u64>();
    let mut heap = BinaryHeap::new();
    for i in 0..n {
        heap.push(a[i]);
    }

    for i in 0..m {
        if let Some(k) = heap.pop() {
            heap.push(k/2);
        }
    }
    let ans = heap.iter().fold(0,|sum,x| sum+x);
    println!("{}", ans);
}


Measured memory_bytes: 9464