akhauriyash/Code-Regression huggingface dataset:
def str2bitstr(chs):
    val = int(chs)
    tmp = bin(val)[2:]
    tmp2 = '0' * (60 - len(tmp))
    return tmp2 + tmp


n = int(input())
a = list(map(str2bitstr, input().split()))

cnts = [0] * 60

for item in a:
    for i, ch in enumerate(item):
        if ch == '1':
            cnts[i] += 1

ret = 0
now = 1

for i in range(1, 61):
    kumi = cnts[-i] * (n - cnts[-i]) % (10 ** 9 + 7)
    ret += kumi * now % (10 ** 9 + 7)
    now *= 2 % (10 ** 9 + 7)
    ret = ret % (10 ** 9 + 7)

print(ret % (10 ** 9 + 7))


Measured memory_bytes: 155372
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define rv(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long LL;
const int M = 120000;
const int inf = 0x3f3f3f3f;
int n,m,k,s;
int main() {
	cin>>n>>k>>s;
	fo(i,1,k) cout<<s<<' ';
	int c=0;
	fo(i,k+1,n){
		++c;
		if(c<s) cout<<1<<' ';
		else {
			c=0;
			cout<<s+1<<' ';
		}
	}
	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef vector<llong> V;

#define _ cin.tie(0);ios::sync_with_stdio(false);
llong n,x;
int main(){ _;
  cin>>n>>x;
  V a(n);
  REP(i,n) cin>>a[i];
  llong ans=0;
  REP(i,n-1){
    llong tempadd = a[i]+a[i+1];
    if(tempadd > x){
      ans+=tempadd-x;
      a[i+1]=max(a[i+1]-(tempadd-x),0LL);
    }
  }
  cout<<ans<<endl;
    
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
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;}

// 0 false, 1 true 
// string to int : -48
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

const int MAX = 2100;

long long fac[MAX], finv[MAX], inv[MAX];

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

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

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll n, k;
    cin >> n >> k;
    ll red = n - k;

    COMinit();

    
    rep(i,k){
        cout << COM(red+1, i+1) * COM(k-1, i) % MOD<< endl;
    }
    



}

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

int T, f[2][1 << 13], a_win, b_win;
bool a[2][13];

bool in_mask(int j, int i) {
	if(j < 0 || j > 12) return false;
	if((1 << j) & i) return true;
	return false;
}

int main() {
	cin >> T;
	while(T--) {
		a_win = b_win = 0;
		for(int i = 0; i < 13; ++i) a[0][i] = a[1][i] = false;
		for(int i = 0; i < 6; ++i) {
			int x;
			cin >> x;
			x--;
			a[0][x] = true; a_win += 1 << x;
		}
		for(int i = 0; i < 13; ++i) if(!a[0][i] && i != 6) a[1][i] = true, b_win += 1 << i;
		memset(f, -1, sizeof f);
		for(int i = (1 << 13) - 1; i >= 0; --i) {
			int st = 1, nd = 0; bool flag0 = true;
			for(int j = 0; j < 13; ++j)
				if(a[0][j] && !in_mask(j, i) && (in_mask(j - 1, i) || in_mask(j + 1, i))) {
					//if(i == (1 << 6)) cout << j << endl;
					st = 0, nd = 1, flag0 = false;
				}
			f[st][i] = 0;
			//if(i == (1 << 6)) cout << st << ' ' << nd << ' ' << flag0 << endl;
			for(int j = 0; j < 13; ++j)
				if(a[st][j] && !in_mask(j, i) && (in_mask(j - 1, i) || in_mask(j + 1, i)))
					if(f[nd][i ^ (1 << j)] != -1)
						f[st][i] |= !f[nd][i ^ (1 << j)];
			f[nd][i] = 0; bool flag1 = true;
			for(int j = 0; j < 13; ++j)
				if(a[nd][j] && !in_mask(j, i) && (in_mask(j - 1, i) || in_mask(j + 1, i)))
					if(f[st][i ^ (1 << j)] != -1)
						f[nd][i] |= !f[st][i ^ (1 << j)], flag1 = false;
			if(flag1) f[nd][i] = !f[st][i];
			if((i & a_win) == a_win && (i && b_win) != b_win) f[1][i] = 0;
			if((i & b_win) == b_win && (i && a_win) != a_win) f[0][i] = 0;
		}
		int mask = 0;
		for(int i = 0; i < 6; ++i) mask += 1 << i;
		for(int i = 7; i < 12; ++i) mask += 1 << i;
		if(f[0][1 << 6]) cout << "yes\n"; else cout << "no\n";
	}
}


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

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    dp = [inf for i in range(n + 1)]
    ans = [1]
    x = 6
    while x <= n:
        ans.append(x)
        x = x * 6
    x = 9
    while x <= n:
        ans.append(x)
        x = x * 9
    ans.sort()
    for i in ans:
        dp[i] = 1
    for i in range(1, n + 1):
        if not i in ans:
            a = bisect.bisect_left(ans, i)
            for k in range(a):
                #print(i,ans[k], a)
                dp[i] = min(dp[i - ans[k]] + 1, dp[i])
    print(dp[n])

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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


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

int main()
{
    int R;
    while(scanf("%d",&R)!=EOF)
    {
        if(R<1200&&R>=0)
            printf("ABC\n");
        else if(R<2800)
            printf("ARC\n");
        else if(R<=4208)
            printf("AGC\n");
    }
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
typedef pair<int, int>P;
const int INF = 1e15;
const int MOD = 1e9 + 7;
const double PI = 3.14159265358979323846;

signed main() {
	int K, A, B;
	cin >> K >> A >> B;
	if (-A + B <= 2) {
		int ans = 1 + K;
		cout << ans;
		return 0;
	}
	if (A - 1 >= K) {
		int ans = 1 + K;
		cout << ans;
		return 0;
	}
	K -= A - 1;
	int num = K / 2 * (-A + B);
	if (K & 1)num++;
	num += A;
	cout << num;
}

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

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  int n;
  cin >> n;
  map<int,int> x;
  R(i,n){
    int pom;
    cin >> pom;
    x[pom]++;
  }
  cin >> n;
  R(i,n){
    int pom;
    cin >> pom;
    if(x[pom] == 0){
      cout << "NO\n";
      return 0;
    }
    x[pom]--;
  }
  cout << "YES\n";
}


Measured memory_bytes: 12800
import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = list(map(int, readline().split()))
    t = 0
    for v in itertools.combinations(a, 2):
        t += v[0] * v[1]
    print(t)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 38512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int a[100010];
int n,m;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int aa, bb;
    cin >> aa >> bb;
    a[aa]++;
    a[bb]++;
  }
  for (int i = 1; i <= n; i++) {
    if (a[i] & 1) {
      cout << "NO\n";
      return 0;
    }
  }
  cout << "YES\n";
  return 0;
}


Measured memory_bytes: 768
#include <stdio.h>

int n, A[50];

// 入力値のMから選んだ要素を引いていく再帰関数
int solve(int i, int m) {
    if (m == 0) return 1;  // 要素iから最後のn-1の要素まで足してmになる場合はtrue
    if (i >= n) return 0;  // 要素iから最後のn-1の要素まで足してmにならない場合はfalse
    int res = solve(i + 1, m) || solve(i + 1, m - A[i]);  // 各要素ごとに足すか足さないかで分岐する(mから要素分引くことで合計を表現)
    return res;
}

int main() {
    int q, M, i;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &q);
    for (i = 0; i < q; i++) {
        scanf("%d", &M);
        if (solve(0, M)) {
            printf("yes\n");
        }
        else {
            printf("no\n");
        }
    }

    return 0;
}


Measured memory_bytes: 2104
# frozen_string_literal: true

_ = gets.to_i
A = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)
C = gets.split.map(&:to_i)

s = 0
before = -1

A.each do |i|
  s += B[i - 1]
  s += C[before - 1] if i == before.succ
  before = i
end

puts s

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

#define rep0(i, n) for(int i=0; i<(int)(n);i++)
#define rep1(i, n) for(int i=1; i<=(int)(n);i++)
#define all(x) (x).begin(), (x).end()
#define debug(a) if(flagdebug){cout << "debug (" #a "):" << endl << (a) << endl;}

typedef uint64_t ulint;
typedef int64_t lint;
using namespace std;

lint 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;
bool flagdebug = false;

int main(){
//////////////////////////////////////////////////////
    // flagdebug = true;

    cin >> a;


    cout << a + a * a + a * a * a << endl;

//////////////////////////////////////////////////////
// Ctrl + Opt + N to make
    return 0;
}


Measured memory_bytes: 3628
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    int A  = sc.nextInt();
    int B  = sc.nextInt();
    
    if((A-B)%2==0){
    System.out.print((B-A)/2+A);
      }else{
	System.out.print("IMPOSSIBLE");
      }
}
}

Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<vector>

class DICE{
    public:
        int rear,back,right,left,up,down,TNP;

        void North();
        void East();
        void West();
        void South();
};

//北に1回動くときのサイコロの目の変化を記述
void DICE::North(){
    TNP=up;
    up=rear;
    rear=down;
    down=back;
    back=TNP;
}
//東に1回動くときのサイコロの目の変化を記述
void DICE::East(){
    TNP=up;
    up=left;
    left=down;
    down=right;
    right=TNP;
}
//西に1回動くときのサイコロの目の変化を記述
void DICE::West(){
    TNP=up;
    up=right;
    right=down;
    down=left;
    left=TNP;
}
//南に1回動くときのサイコロの目の変化を記述
void DICE::South(){
    TNP=up;
    up=back;
    back=down;
    down=rear;
    rear=TNP;
}


int main(){
    int Up,Rear,Right,Left,Back,Down;
    DICE DICE_1;
    std::cin>>Up>>Rear>>Right>>Left>>Back>>Down;
 
    int i,n;
    int up_ans,rear_ans;
    std::vector<int> ans;

    std::cin>>n;
    for(i=0;i<n;i++){

        DICE_1.up=Up;
        DICE_1.rear=Rear;
        DICE_1.right=Right;
        DICE_1.left=Left;
        DICE_1.back=Back;
        DICE_1.down=Down;

        std::cin>>up_ans>>rear_ans;
        
        if(rear_ans==DICE_1.up||rear_ans==DICE_1.down){
            while(DICE_1.rear!=rear_ans){
                DICE_1.South();
            }
            while(DICE_1.up!=up_ans){
                DICE_1.East();
            }
        }else{
            DICE_1.North();
            while(DICE_1.up!=rear_ans){
                DICE_1.West();
            }
            DICE_1.South();
            while(DICE_1.up!=up_ans){
                DICE_1.East();
            }
        }
        ans.push_back(DICE_1.right);
    }

    for(i=0;i<n;i++){
        std::cout<<ans[i]<<std::endl;
    }
//    std::cout<<DICE_1.up<<std::endl;
    return 0;   
}



Measured memory_bytes: 3128
#include <iostream>


using namespace std;
 
int main()
{
    int a, b;
    cin >> a >> b;
    int count = 0;
    
    if (a <= b) {
      count = a;
    }
    else if (a > b) {
      count = a - 1;
    }
    
    cout << count;
    return 0;
}

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

using namespace std;

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

  int N;
  cin >> N;
  string S;
  cin >> S;

  int result = 0;
  for (int base = 0; base < N; ++base) {
    auto* str = &S[base];
    const auto len = N - base;
    vector<int> matched(len);
    int lookup = 0;
    for (int offset = 1; offset < len;) {
      for (; offset + lookup < len && str[offset + lookup] == str[lookup];
           ++lookup) {
      }
      if (lookup <= offset) {
        result = max(result, lookup);
      }
      matched[offset] = lookup;
      if (lookup <= 1) {
        lookup = 0;
        ++offset;
        continue;
      }
      int offset0 = 1;
      for (; offset0 < lookup; ++offset0) {
        auto lookup0 = matched[offset0];
        auto offset1 = offset + offset0;
        if (len <= offset1 || offset + lookup <= offset1 + lookup0) {
          break;
        }
        if (offset0 + lookup0 <= offset1) {
          result = max(result, lookup0);
        }
        matched[offset1] = lookup0;
      }
      offset += offset0;
      lookup -= offset0;
    }
  }

  cout << result << endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h> 
    #define ll long long
    #define pb push_back
    #define ld double
    using namespace std;
     
    const int mod = 1e9+7;
     
     
     
     
    int main(){
       int n,k;
      cin>>n>>k;
      vector<int> arr(n);
      for(int i=0;i<n;i++)
      cin>>arr[i];
      int dp[n+2][k+1];
      memset(dp,0,sizeof(dp));
     
      for(int i=0;i<=k && i<=arr[0];i++)
        dp[1][i]=1;
      
      for(int i=2;i<=n;i++){
        for(int j=0;j<=k;j++){
          dp[i][j]= dp[i-1][j]%mod;
          if(j-1>=0)
            dp[i][j]=(dp[i][j] + dp[i][j-1])%mod;
          if(j-1 - arr[i-1] >=0)
            dp[i][j]=(dp[i][j]-dp[i-1][j-1-arr[i-1]]+mod)%mod;
        }
      }
      /*for(int i=1;i<=n;i++)
      {for(int j=0;j<=k;j++)
        cout<<dp[i][j]<<" ";
       cout<<"\n";
      }*/
      cout<<dp[n][k]<<"\n";
    return 0; 
    }

Measured memory_bytes: 43336
N = int(input())
ans = 0
for i in reversed(range(1,N+1)):
    cnt = 0
    if i % 2 == 0:
        continue
    for j in reversed(range(1,N+1)):
        if i % j == 0:
            cnt += 1
        if cnt > 8:
            break
    else:
        if cnt == 8:
            ans += 1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int k,a,b; cin>>k>>a>>b;
  bool fl=false;
  for(int i=a; i<=b; ++i)if(i%k==0)fl=true;

  if(fl)cout<<"OK"<<endl;
  else cout<<"NG"<<endl;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef int64_t Int;
using namespace std;
 
int main(){
    int A, B, M;
    vector<int> a(100010), b(100010);

    cin >> A >> B >> M;
    int mina = 1e8, minb = 1e8;
    rep(i, A){
        cin >> a[i];
        mina = min(mina, a[i]);
    }
    rep(i, B){
        cin >> b[i];
        minb = min(minb, b[i]);
    }

    int ans = mina + minb;

    rep(i, M){
        int x, y, c; cin >> x >> y >> c;
        x--; y--;
        ans = min(ans, a[x]+b[y]-c);
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int MOD;
int add(int x, int y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}

const int N = 5010;
int n;
int dp[N];

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &n, &MOD);
	dp[n] = 1;
	for (int p = n; p > 0; p--) {
		int z = p;
		z -= max(0, p - (n + 1) / 2);
		z -= max(0, p - n / 2 - 1);
		if (z <= 0) throw;
		for (int x = n; x > z; x--) {
			dp[x - z] = add(dp[x - z], dp[x]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = add(ans, dp[i]);
	printf("%d\n", ans);

	return 0;
}


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

int cnt[200005];

signed main(){
  
  int N, K;
  cin>>N>>K;
  
  int ans = 0;
  
  for(int i=1;i<=N;i++){
    
    if( ( i + i ) % K == 0 ){
      int num = ( N + i ) / K - i / K;
      ans += pow( num, 2 );
    }
    
  }
  
  cout<<ans<<endl;
  
  return 0;
}


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

int main(){
    u_int a, end = 0;
    std :: vector<int> v = {};
    while(std :: cin >> a){
        if(a == 0){
            std :: cout << v.at(end-1) << std :: endl;
            v.pop_back();
            end--;
        } else{
            v.push_back(a);
            end++;
        }
    }
}


Measured memory_bytes: 2980
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

int main()
{
    int n;
    cin >> n;
    vector<ll> l(n + 1);
    l[0] = 2;
    l[1] = 1;
    repl(i, 2, n + 1) {
        l[i] = l[i - 1] + l[i - 2];
    }
    cout << l[n] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int x, y, ans;

	cin >> x >> y;

	ans = abs(abs(x) - abs(y));

	if (abs(x) == abs(y))
		ans = 1;
	else if ((x < 0 && y > 0) || (x > 0 && y < 0))
		ans++;
	else if (x > y)
	{
		if (x >= 0 && y <= 0)
			ans++;
		else
			ans += 2;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  string n;
  cin >> n;
  string op1,op2,op3;
  int a,b,c,d;
  a=n[0]-'0';
  b=n[1]-'0';
  c=n[2]-'0';
  d=n[3]-'0';
  if(a+b+c+d==7){
      op1='+';
      op2='+';
      op3='+';
  }
  else if(a+b+c-d==7){
      op1='+';
      op2='+';
      op3='-';
  }
  else if(a+b-c-d==7){
      op1='+';
      op2='-';
      op3='-';
  }
  else if(a-b-c-d==7){
      op1="-";
      op2="-";
      op3="-";
  }
  else if(a-b-c+d==7){
      op1='-';
      op2='-';
      op3='+';
  }
  else if(a-b+c+d==7){
      op1='-';
      op2='+';
      op3='+';
  }
  else if(a+b-c+d==7){
      op1='+';
      op2='-';
      op3='+';
  }
  else{
      op1='-';
      op2='+';
      op3='-';
  }
  
  
  cout<<n[0]<<op1<<n[1]<<op2<<n[2]<<op3<<n[3]<<"=7"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
constexpr int M = 1e9 + 7;
constexpr int MAXN = 2e5 + 5;
#define pii pair<int, int>
typedef long long LL;
typedef unsigned long long uLL;
using namespace std;
LL n, k, fac[MAXN], rev_fac[MAXN];
inline LL qpow(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) res = res * a % M;
        a = a * a % M;
        b >>= 1;
    }
    return res;
}
inline LL getC(LL m, LL n) {
    return rev_fac[n - m + 1] * qpow(fac[m], M - 2) % M;
}
int main(){
    LL res = 0;
    cin >> n >> k;
	fac[0] = rev_fac[n + 1] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % M;
    for (int i = n; i >= 1; i--) rev_fac[i] = rev_fac[i + 1] * i % M;
    for (LL i = 0; i <= min(n - 1, k); i++) {
        res = (res + getC(i, n) * getC(n - i - 1, n - 1) % M * qpow(n, M - 2) % M) % M;
    }
    cout << res << endl;
	return 0;
}

Measured memory_bytes: 3328
import sys
sys.setrecursionlimit(10**8)

def f(b,n):
  if b>n:
    return n
  else:
    return f(b,n//b)+n%b

n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  ans=10**18
  for i in range(2,int(n**0.5)+1):
    if f(i,n)==s:
      ans=i
      break
  if ans!=10**18:
    print(ans)
  else:
    for i in range(1,int(n**0.5)+1):
      tb=(n-s)//i+1
      if tb==1:
        continue
      if f(tb,n)==s:
        ans=min(ans,tb)
    if ans!=10**18:
      print(ans)
    else:
      print(-1)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int i,j,a,b,c,k,d,n,x[10][10];
int main()
{
  for(cin>>n>>d;i<n;i++)for(j=0;j<d;j++)cin>>x[i][j];
  for(i=0;i<n-1;i++){
    for(k=1;k<n-i;k++){
      for(a=0,j=0;j<d;j++)a+=pow(x[i][j]-x[i+k][j],2);
      b=sqrt(a);if(pow(b,2)==a)c++;
    }
  }
  cout<<c;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

int n;
int x[1<<18];
int dp[18][1<<18];
int ans[18][1<<18];
int getdp(int lb, int dat)
{
    if(lb == -1) return x[dat];
    int& ret = dp[lb][dat];
    if(~ret) return ret;
    if((1 << lb) & dat)
    {
        ret = std::max(getdp(lb-1, dat), getdp(lb-1, dat-(1<<lb)));
    }
    else
    {
        ret = getdp(lb-1, dat);
    }
    return ret;
}
int chk(int lb, int dat)
{
    if(lb == -1) return 0;
    int& ret = ans[lb][dat];
    if(~ret) return ret;
    ret = 0;
    if((1 << lb) & dat)
    {
        ret = std::max(chk(lb-1, dat), getdp(lb-1, dat)+getdp(lb-1, dat-(1<<lb)));
    }
    else
    {
        ret = chk(lb-1, dat);
    }
    return ret;
}
int main()
{
    scanf("%d", &n);
    for(int i=0;i<(1<<n);i++)
    {
        scanf("%d", &x[i]);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<(1<<n);j++)
        {
            ans[i][j] = dp[i][j] = -1;
        }
    }
    int prev = 0;
    for(int i=1;i<(1<<n);i++)
    {
        prev = std::max(prev, chk(n-1, i));
        printf("%d\n", prev);
    }
}

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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int inf = 1e9;
const int maxn = 110;
int A[maxn];

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
        FOR(i,0,n)
            cin >> A[i];
        int ans = inf;
        FOR(x,0,n-1) {
            int a,b; a = b = 0;
            FOR(i,0,x+1)
                a += A[i];
            FOR(i,x+1,n)
                b += A[i];
            ans = min(ans,abs(a-b));
        }
        cout << ans << endl;
    }
    return 0;
}


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

class Program
{
    public static void Main()
    {


        var a = int.Parse(Console.ReadLine());
        var s = Console.ReadLine();

        if(a >= 3200)
        {
            Console.WriteLine(s);
        }
        else
        {
            Console.WriteLine("red");
        }

    }
}

Measured memory_bytes: 11092
#[allow(unused_imports)]
use std::cmp::max;
#[allow(unused_imports)]
use std::fmt;
#[allow(unused_imports)]
use std::fmt::Debug;
#[allow(unused_imports)]
use std::io;
#[allow(unused_imports)]
use std::str::FromStr;

fn main() {
    let input = get_vec_input();
    let a: u64 = input[0];
    let b: u64 = input[1];
    let k: u64 = input[2];
    let mut count = 0u64;
    for i in (1..100 + 1).rev() {
        if a % i == 0 && b % i == 0 {
            count += 1;
            if count == k {
                println!("{}", i);
                break;
            }
        }
    }
}

#[allow(dead_code)]
fn get_digit(value: i64) -> i64 {
    let mut digit = 0i64;
    let mut value = value;
    while value != 0 {
        value /= 10;
        digit += 1;
    }
    digit
}

#[allow(dead_code)]
fn sum_digit2(value: String) -> u32 {
    return value.chars().fold(0u32, |a, b| a + b.to_digit(10).unwrap());
}

#[allow(dead_code)]
fn sum_digit(value: i64) -> i64 {
    if value < 10 {
        return value;
    }
    return sum_digit(value / 10) + value % 10;
}

#[allow(dead_code)]
fn update_max<T>(left: &mut T, right: T)
where
    T: std::cmp::Ord + std::clone::Clone,
{
    if *left < right {
        *left = right.clone();
    }
}

#[allow(dead_code)]
fn update_min<T>(left: &mut T, right: T)
where
    T: std::cmp::Ord + std::clone::Clone,
{
    if *left > right {
        *left = right.clone();
    }
}

#[allow(dead_code)]
fn get_vec_input<T>() -> Vec<T>
where
    T: FromStr,
    T::Err: Debug,
{
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("Failed to read line");
    let vec: Vec<T> = input
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();
    vec
}

#[allow(dead_code)]
fn get_tuple_input() -> (u64, f32) {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    let mut iter = s.trim().split_whitespace();
    let c: u64 = iter.next().unwrap().parse().unwrap();
    let n: f32 = iter.next().unwrap().parse().unwrap();
    (c, n)
}

#[allow(dead_code)]
fn get_string_input() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    s.trim().to_string()
}


Measured memory_bytes: 4476
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include<math.h>
#include<map>
#include<set>
using namespace std;
#define INF 1100000000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,int> P;


int main(){
  ll N,A[2][110000],s[2];
  P S[110000];
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>A[0][i]>>A[1][i];
    A[0][i]*=-1; A[1][i]*=-1;
    S[i].first=A[0][i]+A[1][i]; S[i].second=i;
  }
  sort(S,S+N);

  for(int i=0;i<N;i++){
    s[i%2]+=A[i%2][S[i].second];
  }
  cout<<(s[0]-s[1])*(-1)<<endl;
}


Measured memory_bytes: 3712
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

deque<int> L;
vector<int> G[100010];
int visited[100010];
int n, m;
int ans[100010];

bool visit(int i) {
    if (visited[i] == 1) return false;
    if (!visited[i]) {
        visited[i] = 1;
        for(auto next: G[i]) {
            visit(next);
        }
        visited[i] = 2;
        L.push_front(i);
    }
    return true;
}

bool topological() {
    rep(i, n) {
        bool istopo = true;
        if (!visited[i]) istopo = visit(i);
        if(!istopo) return false;
    }
    return true;
}



int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, n + m - 1) {
        int s, t; cin >> s >> t;
        s--; t--;
        G[s].push_back(t);
    }
    topological();
    rep(i, L.size()) {
        for(auto next : G[L[i]]) {
            ans[next] = L[i] + 1;
        }
    }

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

    return 0;
}


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

int main() {

    int n, m, c;
    cin >> n >> m >> c;

    vector<int> B(m);
    vector<vector <int>> A(n, vector<int>(m) );

    for (int i = 0; i < m; i++) {
        cin >> B[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> A[i][j];
        }
    }

    int sum = 0;
    int cnt = 0;
    
    for (int i = 0; i < n; i++) {

        sum = 0;

        for (int j = 0; j < m; j++)
            sum += A[i][j] * B[j];

        if(sum + c > 0) cnt++;
    }

    cout << cnt << endl;

    return 0; 

}

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

int main(void) {
    int N;
    cin>>N;
    vector<int> A(N+1), B(N);
    for(int i = 0; i < N + 1; ++i) {
        cin>>A[i];
    }
    for(int i = 0; i < N; ++i) {
        cin>>B[i];
    }

    long long count = 0;
    for(int i = 0; i < N; ++i) {
        if(A[i] > B[i]) {
            count += B[i];
        } else if(A[i] + A[i + 1] > B[i]) {
            count += B[i];
            A[i + 1] -= B[i] - A[i];
        } else {
            count += A[i] + A[i + 1];
            A[i + 1] = 0;
        }
    }
    printf("%lld\n", count);

    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
	int N,M;
	int A[10000];
	int B=0;
	cin>>N>>M;
	for(int i=0;i<M;i++){
		cin>>A[i];
  		B=B+A[i];
    }
  	if(N>=B)
      cout<<N-B<<endl;
  	else
      cout<<-1<<endl;
}

Measured memory_bytes: 3632
from collections import Counter

n=int(input())
s=['n']+list(input())
ans=10**6
c=Counter(s)
le,lw=0,0
for i in s:
    if i=='E':
        le+=1
    elif i=='W':
        lw+=1
    ans=min(ans,lw+c['E']-le)
print(ans)

Measured memory_bytes: 8524
#!/usr/bin/env python3
import sys


def solve(N: int, s: "List[int]"):
    mod = [s[i]%10 for i in range(N)]
    if sum(mod)%10!=0:
        print(sum(s))
        return 
    
    s.sort()
    for ss in s:
        if ss%10!=0:
            print(sum(s)-ss)
            return 
    
    print(0)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    s = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, s)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
#include <random>
#include <time.h>
#include <unordered_set>

using namespace std;
using Int = long long;

constexpr double EPS = 1e-10;
constexpr long long MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for (int i = 0;i < 60; i++) {
        if (n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

long long my_mod_pow(long long x, long long n) {
	long long ret = 1;
	for (; n > 0; n >>= 1, x = x * x % MOD) {
		if (n & 1) {
			ret = ret * x % MOD;
		}
	}
	return ret;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fastInput() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main(void) {
    long long a, b, c; cin >> a >> b >> c;
    long long left = a * b * 4;
    long long right = (c - a - b) * (c - a - b);
    if (c - a - b <= 0) {
        cout << "No" << endl;
        return 0;
    }
    if (left < right) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


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

int main() {
  int q,w,e,r; cin>>q>>w>>e>>r;
  cout << (q+w+1)/2;
}

Measured memory_bytes: 3584
//------------------------------------------
// C++ templete 
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

//typedef
//------------------------------------------
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

//REPEAT
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//container util
//------------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for (auto v : (V)) cout << v << " "
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())

//constant
//------------------------------------------
const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//math
//------------------------------------------
int QP(int a,int b){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int QP(int a,int b,int MOD){int ans=1;do{if(b&1)ans=1ll*ans*a%MOD;a=1ll*a*a%MOD;}while(b>>=1);return ans;}
int GCD(int a,int b){return b?GCD(b,a%b):a;}

//debug
//------------------------------------------
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//動的計画法で役に立つ関数
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
  
    int N; cin >> N;

    VVI A(N, VI(3));
    REP(i, N) cin >> A.at(i).at(0) >> A.at(i).at(1) >> A.at(i).at(2);
    VVI dp(N+1, VI(3,0));
    
    FOR(i,1, N+1)
    {
        REP(j, 3)
        {
            REP(k, 3)
            {
                if (j==k) continue;
                chmax(dp.at(i).at(k), dp.at(i-1).at(j)+A.at(i-1).at(k)); 
            }
        }
    }

    cout << max({dp.back().at(0),dp.back().at(1),dp.back().at(2)} ) << endl;
  
    return 0;
}



Measured memory_bytes: 11136
import heapq
def main():
    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    p.sort(reverse=True)
    q.sort(reverse=True)
    r.sort(reverse=True)
    h = []
    for i in p[:X]:
        heapq.heappush(h, (i, 'r'))
    for i in q[:Y]:
        heapq.heappush(h, (i, 'g'))
    a = sum(p[:X]) + sum(q[:Y])
    ra = 0
    ga = 0
    i = 0
    while h:
        t = heapq.heappop(h)
        if r[i] < t[0]:
            break
        if t[1] == 'r' and ra <= X:
            a += r[i]
            a -= t[0]
            ra += 1
            i += 1
        elif t[1] == 'g' and ga <= Y:
            ga += 1
            a += r[i]
            a -= t[0]
            i += 1
        if ra == X and ga == Y:
            break
        if i >= C:
            break
    return a
print(main())


Measured memory_bytes: 29856
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<string>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n0,n) for(int i=n0;i<n;i++)
#define Com(i,j,n) for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++)
#define W(x) cout<<x<<endl;
#define Debug(x) cout<<"#DEBUG "<<x<<endl;
#define INF (1<<29)
//a...z==97...122
using namespace std;
int min(int x,int y){if(y<x)return y;else return x;}
int max(int x,int y){return x+y-min(x,y);}
int fact(int x){int i=1;rep(j,x){i*=(j+1);} return i;}
int main()
{
    int n,c;
    cin>>n>>c;
    int D[c][c];
    rep(i,c)
    {
        rep(j,c)
        {
            cin>>D[i][j];
        }
    }
    int cnt[3][c];
    rep(i,3)
    {
        rep(j,c)
        {
            cnt[i][j]=0;
        }
    }
    int clo;
    rep(i,n)
    {
        rep(j,n)
        {
            
            cin>>clo;
            clo--;
            cnt[(i+j+2)%3][clo]++;
        }
    }
    int m=INF,w;
    rep(i,c)
    {
        rep(j,c)
        {
            rep(k,c)
            {
                if(i!=j&&j!=k&&k!=i)
                {
                    w=0;
                    rep(l,c)w+=D[l][i]*cnt[0][l];
                    rep(l,c)w+=D[l][j]*cnt[1][l];
                    rep(l,c)w+=D[l][k]*cnt[2][l];
                    m=min(m,w);
                }
                
            }
        }
    }
    W(m)
    return 0;
}

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

#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
#define endl "\n" 
#define all(c) c.begin(),c.end()
#define present(c,element) (c.find(element)!=c.end())
#define cpresent(c,element) (find(c,element)!=c.end())
#define forr(i,a,b) for(int i=a;i<int(b);i++)
#define tr(i,a) for(auto i:a)
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
const double PI=acos(-1);
const ll mod=1e9+7;

// vector<int> adj[100005];
// vi dp(100005, 0);
// vector<bool> vis(100005, false);

// void dfs(int v)
// {
// 	vis[v]=true;
// 	for(int i=0;i<adj[v].size();i++)
// 	{
// 		if(!vis[adj[v][i]])
// 			dfs(adj[v][i]);
// 		dp[v]=max(dp[v], 1+dp[adj[v][i]]);
// 	}
// }

void add(ll &a, ll b)
{
    a+=b;
    if(a>=mod)a-=mod;
}
void sub(ll &a, ll b)
{
    a-=b;
    if(a<0)a+=mod;
}
ll mul(ll a, ll b)
{
    return ((a*b)%mod);
}



int32_t main()
{
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

int test=1;
//cin>>test;
while(test--)
{
	int n, w, x, y;
	cin>>n;
	//double a[n];
	// for(int i=0;i<n;i++)
	// {
	// 	// for(int j=0;j<w;j++)
	// 	// {
	// 	 	cin>>p[i];
	// 	// }
	// }
	double dp[n+1][n+1];
	// dp[0]=1;
	// for(int i=1;i<=n;i++)
	// {

	// 	if(a[i][0]=='#')dp[i][0]=0;
	// 	else dp[i][0]=dp[i-1][0];
	// }
	// for(int i=1;i<w;i++)
	// {
	// 	if(a[0][i]=='#')dp[0][i]=0;
	// 	else dp[0][i]=dp[0][i-1];
	// }
	memset(dp, 0.0, sizeof(0));
	dp[0][0]=1.0;
	for(int i=1;i<=n;i++)
	{
		double p;
		cin>>p;
		for(int j=0;j<=i;j++)
		{
			if(j==0)dp[i][j]=dp[i-1][j]*(1-p);
			else dp[i][j]=dp[i-1][j]*(1-p)+dp[i-1][j-1]*p;
			// if(a[i][j]=='#')
			// 	dp[i][j]=0;
			// // else if(a[i-1][j]=='#'&&dp[i][j-1]=='#')
			// // 	dp[i][j]=0;
			// // else if(dp[i-1][j]=='#')
			// // 	dp[i][j]=dp[i][j-1];
			// // else if(dp[i][j-1]=='#')
			// // 	dp[i][j]=dp[i-1][j];
			// else
			// 	dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;

		}
	}
	double ans=0.0;
	// forr(i,0,h)
	// {
		forr(j,n/2+1,n+1)
		ans+=dp[n][j];
	// 	cout<<endl;
	// }
	cout<<fixed<<setprecision(10)<<ans<<endl;

}
return 0;
}










Measured memory_bytes: 70400
#include <iostream>

using namespace std ;

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

    cin >> a >> b >> c;
    if (a+b == c){
        cout << "Yes";
        return 0 ;
    }
    if (a+c == b){
            cout << "Yes";
            return 0;
    }
    if (b+c == a){
        cout << "Yes";
        return 0;
    }
cout << "No";
return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;

public class Main {
	public static void main(String[] args) {
		print();
	}

	public static void print() {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			String str = br.readLine();
			int weeks = Integer.parseInt(str);
			int debt = 100000;
			for(int i = 0; i < weeks; i++){
				debt = new BigDecimal(debt * 1.05).setScale(-3, BigDecimal.ROUND_CEILING).intValueExact();
			}
					System.out.println(debt);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 24476
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int N;
	int* a;
	int i;
	int cont = 0;
	scanf("%d", &N);
	a = (int*)malloc(sizeof(int) * N);
	for (i = 0; i < N; i++) {
		scanf("%d", a + i);
	}
	for (i = 0; i < N-1; i++) {
		if (a[i] == a[i + 1]) {
			cont++;
			i++;
		}
	}
	printf("%d\n", cont);
	free(a);
	return 0;
}

Measured memory_bytes: 128
import java.io.PrintWriter
import kotlin.math.max

fun main() {
    val pw = PrintWriter(System.out)

    val (a, b, n) = readInputLine().split(" ").map { it.toLong() }

    fun f(a: Long, b: Long, n: Long): Long {
        return a * n / b - a * (n / b)
    }

    if (n >= b) {
        pw.println(f(a, b, (b - 1L)))
    } else {
        pw.println(f(a, b, n))
    }

    pw.flush()
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 36412
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m;
struct node{
	int x,y,z;
}a[MAXN];
int f[MAXN];
bool is_f[MAXN];
int find(int x)
{
	return f[x]?f[x]=find(f[x]):x;
}
void group(int x,int y)
{
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy)
		f[fx]=fy;
}
int main() 
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y>>a[i].z;
		group(a[i].x,a[i].y);	
	}
	for(int i=1;i<=n;i++)
		is_f[find(i)]=1;
	int ans=0;
	for(int i=1;i<=n;i++)
		ans+=is_f[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2304
N=input()

k=len(N)
A='9'*(k-1)

if N[0]==1:
    if N[1:]==A:
        print(k*9-8)
    else:
        print((k-1)*9)

else:
    if N[1:]==A:
        print(int(N[0])+(k-1)*9)
    else:
        print(int(N[0])+(k-1)*9-1)

Measured memory_bytes: 9060
import math
while True:
  a, x, b = input().split()
  a = int(a)
  b = int(b)
  if x == "+":
    print(a+b)
  elif x == "-":
    print(a-b)
  elif x == "/":
    print(math.floor(a/b) )
  elif x == "*":
    print(a*b)
  else:
    break



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

ll mod = 1e9+7;

int main() {
    int N;
    cin >> N;
    vector<ll> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];
    sort(C.begin(), C.end());
    vector<ll> pow(N+1, 1);
    for (int i = 1; i <= N; i++) pow[i] = pow[i-1]*2%mod;
    vector<ll> sum(N+1, 0);
    sum[0] = C[0];
    for (int i = 1; i < N; i++){
        sum[i] = (sum[i-1]+C[i])%mod;
    }
    vector<ll> dp(N, 0);
    dp[0] = C[0]*2%mod;
    for (int i = 1; i < N; i++) {
        dp[i] = dp[i-1]*4;
        dp[i] += C[i]*2*pow[i]%mod*pow[i]%mod;
        dp[i] += sum[i-1]*4*pow[i-1]%mod*pow[i-1]%mod;
        dp[i] %= mod;
    }
    cout << dp[N-1] << endl;
    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()
using namespace std;
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;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;
//木の連結成分の個数は頂点数ー辺の数

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll n; cin >> n;
    ll res=0;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        if(a>b)swap(a,b);
        res+=a*(n-b+1);
    }
    ll ans=0;
    for(ll i=1;i<=n;i++){
        ans+=((n-i+1)*(n-i+2))/2;
    }
    cout << ans-res << endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define R register
#define ll long long
#define mp make_pair
#define pii pair<int, int>
using namespace std;
const double PI = acos(-1);

int a, b, x, sz;

template <class T>
inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = ch == '-', ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

int main() {
    read(a), read(b), read(x);
    sz = a * a * b;
    if (x * 2 >= sz) {
        double h = (double) (sz - x) / a / a * 2;
        printf("%.10lf\n", atan2(h, a) * 180 / PI);
    }
    else {
        double h = (double) x / b / a * 2;
        printf("%.10lf\n", atan2(b, h) * 180 / PI);
    }
    return 0;
}

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

vector<int> adj[200200];
int vis[200200];

int ma = 0;
void dfs(int x){
	if(vis[x]) return;
	ma++;
	vis[x] = 1;
	for(auto xx : adj[x]){
		dfs(xx);
	}
	return;
}
int main(){
	
	int n,m; cin>>n>>m;
	for(int i = 0; i < m; i++){
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	int ans = 1;
	for(int i = 1; i <= n; i++){
		ma = 0;
		if(!vis[i]) dfs(i);
		ans = max(ans,ma);
	}
	cout<<ans<<"\n";
	
	
}

Measured memory_bytes: 21492