akhauriyash/Code-Regression huggingface dataset:
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

right = [[0]*w for _ in range(h)]
left = [[0]*w for _ in range(h)]
up = [[0]*w for _ in range(h)]
down = [[0]*w for _ in range(h)]

for i in range(h):
    if s[i][0] == ".":
        left[i][0] = 1
    if s[i][w-1] == ".":
        right[i][w-1] = 1

for j in range(w):
    if s[0][j] == ".":
        down[0][j] = 1
    if s[h-1][j] == ".":
        up[h-1][j] = 1
        
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            if j > 0:
                left[i][j] = left[i][j-1] + 1
            if i > 0:
                down[i][j] = down[i-1][j] + 1

for i in range(h)[::-1]:
    for j in range(w)[::-1]:
        if s[i][j] == ".":
            if i < h-1:
                up[i][j] = up[i+1][j] + 1
            if j < w-1:
                right[i][j] = right[i][j+1] + 1
ans = 0
for i in range(h):
    for j in range(w):
        count = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
        if ans < count:
            ans = count
print(ans)

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

int main(){
  int N,M;
  cin >> N >> M;
  int A=0;
  for (int i=0; i<M; i++){
    int x;
    cin >> x;
    A += x;
  }
  if( N-A >= 0)
    cout << N - A <<endl;
  else
    cout << -1 <<endl;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    int ans = 0;
    for (int i = 0; i < k; i++) {
        ans += arr[i];
    }
    cout << ans << endl;
    return 0;
}



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

long inf = 1000000007;


int main() {
	long long n; cin >> n;
	
	long long total = 0;
	cout << fixed << setprecision(20);
	for (long long i = 1; i <= n; i++) {
		if (i % 3 != 0 and i % 5 != 0) {
			total += i;
		}
	}
	cout << total << endl;
}


Measured memory_bytes: 3596
class dice:
    def __init__(self,label):
        self.top, self.front, self.right, self.left, self.rear, self.bottom \
                = label
    def roll(self,op):
        if   op=='N': self.top, self.front, self.bottom, self.rear = \
                                self.front, self.bottom, self.rear , self.top
        elif op=='E': self.top, self.left , self.bottom, self.right = \
                                self.left , self.bottom, self.right, self.top
        elif op=='W': self.top, self.right, self.bottom, self.left = \
                                self.right, self.bottom, self.left , self.top
        elif op=='S': self.top, self.rear , self.bottom, self.front = \
                                self.rear , self.bottom, self.front, self.top
    def print_top(self): print(self.top)
   
label = list(map(int,input().split()))
op_list = list(input())
d = dice(label)
for op in op_list:
    d.roll(op)
d.print_top()


Measured memory_bytes: 5600
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define per(i,a,b) for (int i=(a); i>=(b); i--)
using namespace std;

const int maxn = 200005;
int f[maxn], ans, n, p;

int main() {
	scanf("%d", &n);
	rep (i, 1, n) {
		scanf("%d", &p);
		f[p] = f[p-1] + 1;
		ans = max(ans, f[p]);
	}
	printf("%d\n", n - ans); 
	
	return 0;
}

Measured memory_bytes: 1532
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 10
using namespace std;

void Print(vector<int> &vec)
{
    printf("%d", vec[0]);
    for (unsigned i = 1; i < vec.size(); i++)
    {
        printf(" %d", vec[i]);
    }
    printf("\n");
}

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

    vector<int> vec(n), prevec, nextvec;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &vec[i]);
    }

    prevec.assign(vec.begin(), vec.end());
    if (true == prev_permutation(prevec.begin(), prevec.end()))
    {
        Print(prevec);
    }

    Print(vec);
    nextvec.assign(vec.begin(), vec.end());
    if (true == next_permutation(nextvec.begin(), nextvec.end()))
    {
        Print(nextvec);
    }


    return 0;
}



Measured memory_bytes: 3264
import math 
import sys
read_=sys.stdin.buffer.readline

K=int(read_())
ans=0
for a in range(1,K+1):
    for b in range(1,K+1):
        x=math.gcd(a,b)
        for c in range(1,K+1):
            ans+=math.gcd(x,c)
print(ans)

Measured memory_bytes: 9232
k,n=map(int,input().split())
a=list(map(int,input().split()))

s=[]
for i in range(len(a)):
    if not i==len(a)-1:
        s.append(abs(a[i+1]-a[i]))
    else:
        s.append(k-a[i]+a[0])

s.remove(max(s))
print(sum(s))

Measured memory_bytes: 26444
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define all(v) v.begin(),v.end()
#define mem(v,x) memset(v,x,sizeof(v))
#define N 200005

using namespace std;


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	ll n,W;
	cin>>n>>W;
	ll w[n+1];
	ll v[n+1];
	for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i];
	}
    ll dp[101][100005];
	mem(dp,-1);
	for(int i=0;i<=n;i++){
        dp[i][0] = 0;
	}
	for(int i=1;i<=n;i++){
        for(int j=1;j<100005;j++){
            if(v[i]>j){
                dp[i][j] = -1;
            }
            else if(dp[i-1][j-v[i]]!=-1){
                dp[i][j] = (dp[i][j]==-1)?w[i]+dp[i-1][j-v[i]] : min(dp[i][j], w[i]+dp[i-1][j-v[i]]);
                if(dp[i-1][j]!=-1){
                    dp[i][j] = min(dp[i][j], dp[i-1][j]);
                }
            }
            if(dp[i-1][j]!=-1){
                if(dp[i][j]!=-1)
                    dp[i][j] = min(dp[i][j], dp[i-1][j]);
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
	}
	ll ans = 0;
	for(ll i=0;i<100005;i++){
        if(dp[n][i]!=-1 && dp[n][i]<=W)
            ans = i;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 79232
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 200005;
const int mod = 1000000007;

int n;
ll m;
int a[maxn];

ll solve(ll mid){
  ll ret = 0;
  for(int i=0;i<n;i++){
    if(a[i]>=0){
      int l = i+1, r = n-1, ans = i;
      while(l<=r){
        int m = (l+r)>>1;
        if(a[m]*(ll)a[i]<=mid){
          ans = m;
          l = m+1;
        } else r = m-1;
      }
      ret += ans - i;
    } else {
      int l = i+1, r = n-1, ans = n;
      while(l<=r){
        int m = (l+r)>>1;
        if(a[m]*(ll)a[i]<=mid){
          ans = m;
          r = m - 1;
        } else l = m+1;
      }
      ret += n - ans;
    }
  }
  return ret;
}

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
  cin>>n>>m;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a, a+n);
  ll l = -1000000000L * 1000000000L, r = -l;
  ll ret = r;
  while(l<=r){
    ll mid = (l+r)/2;
    if(solve(mid)>=m){
      ret = mid;
      r = mid - 1;
    } else l = mid+1;
  }
  cout<<ret<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define uniq(x) (x).erase(unique(all(x)),(x).end())

typedef long long ll;

void solve(void){
    ll N, A, B;
    cin >> N >> A >> B;
    cout << max((A+B*(N-1)) - (A*(N-1)+B) + 1, 0LL) << endl;
}

int main(void){
  solve();
  return 0;
}


Measured memory_bytes: 256
// 標準入力から一行を読み取り、指定の型に変換する
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()
}

// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let n_k: Vec<i32> = read_vec();
    let hn: Vec<i32> = read_vec();

    let mut number: i32 = 0;

    for i in 0..n_k[0] as usize
    {
        number += if hn[i] >= n_k[1] { 1 } else { 0 };
    }

    println!("{}", number);
}


Measured memory_bytes: 4352
a, b, c = [int(i) for i in input().split()]
k = int(input())


while k >= 1 and b <= a:
    b = 2 * b
    k -= 1

while k >= 1 and c <= b:
    c = 2 * c
    k -= 1

if a < b and b < c:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9176
#include <vector>
#include <iostream>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;

int main(){
    string a,b;
    cin >> a >> b;
    if(a.length()>b.length()){
        cout << "GREATER";
        return 0;
    }else if(a.length()<b.length()){
        cout << "LESS";
        return 0;
    }
    if(a==b){
        cout << "EQUAL";
        return 0;
    }
    for(int i=0;i<a.length();i++){
        if(a[i]>b[i]){
            cout << "GREATER";
            break;
        }else if(a[i]<b[i]){
            cout << "LESS";
            break;
        }else{
            continue;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N;
    cin >> N;

    // Make vector
    vector<int> vec(N);
    for(int i=0; i<N; i++){
        cin >> vec.at(i);
    }

    // count Mochi
    int math;
    int count=0;
    for(int i=0; i<N; i++){
        math = vec.at(i);

        for(int j=0; j<N; j++){
            if(math < vec.at(j)){
                math = vec.at(j);
            }
        }

        for(int j=0; j<N; j++){
            if(math == vec.at(j)){
                vec.at(j) = 0;
            }
        }

        if(math != 0){
            count++;
        }
    }
    cout << count << endl;
}

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

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

  vector<int> x(n);
  for (int i = 0; i < n; i++) {
    cin >> x.at(i);
  }

  vector<int> y(n);
  for (int i = 0; i < n; i++) {
    cin >> y.at(i);
  }

  // p = 1〜3 の場合
  vector<int> p_list = {1, 2, 3};
  for (int i = 0; i < (int)p_list.size(); i++) {
    int p = p_list.at(i);

    double summation = 0;
    for (int i = 0; i < n; i++) {
      int dif = x.at(i) - y.at(i);
      // 絶対値をとる
      if (dif < 0) { dif = dif * -1; }
      dif = pow(dif, p);
      summation += dif;
    }

    // cout << "summation: " << summation << endl;

    double root = pow(summation, (1.0 / p));
    printf("%.6f\n", root);
  }

  // p = 無限の場合
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int dif = x.at(i) - y.at(i);
    if (dif < 0) { dif = dif * -1; }
    ans = max(ans, dif);
  }
  printf("%.6f\n", (double)ans);
  return 0;
}



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

int main(){
  string S ; 
  cin >> S ; 
  int N = S.size() ; 
  long long K ; cin >> K ;
  char ans  ; 
  
  for(long long i = 0 ; i < K ; i++){
    ans = S.at(i) ; 
    if(ans != '1' ){
      break ; 
    }
  }
  cout << ans << endl ; 
}

Measured memory_bytes: 3576
#include <stdio.h>

#define MOD_BY 1000000007

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int N;

int memo[1234567][2][2];

int kugyu(int pos, int zero, int nine) {
	int answer = 0;
	int i;
	if (pos >= N) return zero && nine;
	if (memo[pos][zero][nine]) return ~memo[pos][zero][nine];
	for (i = 0; i <= 9; i++) {
		answer = add(answer, kugyu(pos + 1, zero || i == 0, nine || i == 9));
	}
	return ~(memo[pos][zero][nine] = ~answer);
}

int main(void) {
	if (scanf("%d", &N) != 1) return 1;
	printf("%d\n", kugyu(0, 0, 0));
	return 0;
}


Measured memory_bytes: 95396
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    ll n, k;
    ll ans = -INF;
    cin >> n >> k;

    vector<ll> p(n), c(n);

    for (int i = 0; i < n; i++)
    {
        cin >> p[i];
        p[i]--;
    }

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

    for (int i = 0; i < n; i++)
    {
        ll cycle_sum = 0;
        ll next_i = i;
        ll cycle_cnt = 0;

        while (true)
        {
            cycle_cnt++;
            next_i = p[next_i];
            cycle_sum += c[next_i];
            if (next_i == i)
            {
                break;
            }
        }

        next_i = i;
        ll cnt = 0;
        ll path = 0;

        while (true)
        {
            cnt++;
            path += c[next_i];

            if (cnt > k)
            {
                break;
            }

            ll score = path + max(0ll, cycle_sum) * ((k - cnt) / cycle_cnt);

            ans = max(ans, score);

            next_i = p[next_i];

            if (next_i == i)
            {
                break;
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3724
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<iomanip>

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

#define debug(x) cout<<(#x)<<"="<<(x)<<", ";
#define debug1(x) debug(x) cout<<'\n';
#define debug2(x1, x2) debug(x1) debug(x2) cout<<'\n';
#define debug3(x1, x2, x3) debug(x1) debug(x2) debug(x3) cout<<'\n';
#define debug4(x1, x2, x3, x4) debug(x1) debug(x2) debug(x3) debug(x4) cout<<'\n';
#define debug5(x1, x2, x3, x4, x5) debug(x1) debug(x2) debug(x3) debug(x4) debug(x5) cout<<'\n';

#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sort(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb(x) emplace_back(x);

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<int, int, lli> tiil;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;

int main(){
	fast_io
	string s; cin>>s;
	rep(i,s.size()){
		if(s[i]=='1') cout<<"9";
		else if(s[i]=='9') cout<<"1";
		else cout<<s[i];	
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int a,b,c,d,e;
    int k;
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    scanf("%d",&d);
    scanf("%d",&e);
    scanf("%d",&k);

if(k>=e-a){
    if(k>=d-a){
        if(k>=c-a){
            if(k>=b-a){
                printf("Yay!\n");
            }
        }
}
}
else{
printf(":(\n");
}
return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>

using namespace std;

string s;
char a[3];

int main(){
    for(int i=0;i<3;i++){
        cin>>s;
        a[i]=s[i];
    }
    printf("%c%c%c\n",a[0],a[1],a[2]);
}


Measured memory_bytes: 256
n = int(input())

li_hi = list()
a = 1
b = 1
for i in range(n):
    li_hi.append(list(map(int, input().split())))

for l in li_hi:
    w = max(-(-a // l[0]), -(-b // l[1]))
    a = w * l[0]
    b = w * l[1]

print(a + b)



Measured memory_bytes: 3188
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

using ld= long double;

vector<int>primes;
void hurui(const int amax) {
	static bool flag = false;
	if (flag)return;
	vector<int>sos;
	sos = vector<int>(amax + 1, true);
	sos[0] = false; sos[1] = false;
	for (int i = 2; i <= amax; ++i) {
		if (sos[i]) {
			for (int j = 2 * i; j <= amax; j += i)sos[j] = false;
		}
	}
	for (int i = 0; i <= amax; ++i) {
		if (sos[i]) {
			primes.push_back(i);
		}
	}
	flag = true;
}

long long int K;

ld solve(long long int now_num,int pr_id,int use_max,ld now_val) {
	if (use_max == 0) {
		return now_val;
	}
	if (primes.size() == pr_id) {
		return now_val;
	}
	else {
		ld ans=now_val;
		int now_use = 0;
		long long int pr_sum=1;
		long long int div_sum=1;
		ld next_val=now_val*pr_sum/div_sum;
		long long int next_num=now_num;
		while (next_num<=K) {
			ans=max(ans,solve(next_num,pr_id+1,now_use,next_val));

			now_use++;
			div_sum*=primes[pr_id];
			pr_sum+=div_sum;
			next_val=now_val*pr_sum/div_sum;
			next_num*=primes[pr_id];
		}

		return ans;
	}
}
int main() {
	hurui(1e3);
	int case_id=0;
	while (true) {
		cin>>K;
		if(!K)break;
		ld ans=solve(1,0,1000,1);
		cout<<setprecision(10)<<fixed<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3248
#include <bits/stdc++.h>
#define cinf(n,x) for(int i=0;i<(n);i++) cin >> x[i];
typedef long long int ll;
using namespace std;

int main(){
	int h,w; cin >> h >> w;
	string s[60];
	int dh[]={-1,-1,-1,0,0,1,1,1};
	int dw[]={-1,0,1,-1,1,-1,0,1};

	for(int i=0;i<h;i++) 
		cin >> s[i];
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(s[i][j]=='.'){
				int cnt=0;
				for(int k=0;k<8;k++){
					int x = j +dw[k];
					int y = i +dh[k];
					if(0<=x && x<=w && 0 <=y && y <=h && s[y][x]=='#') cnt++;
				}
				s[i][j]= '0'+cnt;
			}
		}
	}
	for(int i=0;i<h;i++){
		cout << s[i]<< endl;
	}
}

Measured memory_bytes: 256
n = gets.to_i
ss = n.times.map{gets.chomp}

hash = Hash.new(0)
ss.shift.chars.each do |c|
	hash[c] += 1
end

ss.each do |s|
	temp = Hash.new(0)
	s.chars.each do |c|
		temp[c] += 1
	end
	hash.keys.each do |k|
		hash[k] -= [hash[k] - temp[k] , 0].max
	end
end

ans = []
hash.keys.sort.each do |k|
	if hash[k] > 0
		ans << k * hash[k]
	end
end

puts ans.join

Measured memory_bytes: 1788
from sys import stdin
a,b = [int(x) for x in stdin.readline().rstrip().split()]
x = a * 25 // 2
if a % 2 == 1:
    x += 1
y = b * 10
ant = 0
while int(x * 0.08) == a:
    if int(x * 0.1) == b:
        ant = 1
        print(x)
        break
    x += 1
if ant == 0:
    print(-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1000000007;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }
template<class itr, class itr2> bool next_sequence2(itr first, itr last, itr2 first2, itr2 last2){ itr now = last; itr2 now2 = last2; while(now != first){ now--, now2--; (*now)++; if((*now) == (*now2)){ (*now) = 0; }else{ return true; } } return false; }

int main(){
    int N;
    cin >> N;
    lint A[N];
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    lint ans = 1e18, now = 0;
    lint sum = accumulate(A, A + N, 0ll);
    for(int i = 0; i < N; i++){
        ans = min(ans, abs(sum - now * 2));
        now += A[i];
        ans = min(ans, abs(sum - now * 2));
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>

int main(){
  std::string s;
  std::cin>>s;
  if(s[0]!='A'){
    std::cout<<"WA"<<std::endl;
    return 0;
  }else{
    int cnt=0;
    for(int i=1;i<s.size();++i){
      if(s[i]>='a' && s[i]<='z')cnt++;
    }
    if(cnt != s.size()-2){
      std::cout<<"WA"<<std::endl;
      return 0;
    }else{
      int cntc=0;
      for(int i=2;i<=s.size()-2;++i){
        if(s[i]=='C')cntc++;
      }
      if(cntc==1){
        std::cout<<"AC"<<std::endl;
      }else{
        std::cout<<"WA"<<std::endl;
      }
    }
  }

}


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

const int mod = 1e9 + 7;

#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()

#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define plii pair<pair<ll, int>, int>
#define piii pair<pii, int>
#define viii vector<pair<pii, int> >
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define ms(x, v) memset(x, v, sizeof x)
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;

#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)

#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#define ASST(x, l, r) assert( x <= r && x >= l )

const ll M=1e9+7;
ll power(ll a,ll n)
{
  if(n==0)
    return 1;
  else if(n==1)
  return n;
  ll z=power(a,n/2);
  if(n&1)
    return ((z%M*z%M)%M*a%M)%M;
  else
    return (z%M*z%M)%M;
}
 bool sortbysecdesc(const pair<int,int> &a,const pair<int,int> &b){
      return a.second>b.second;
}
// vl g[100010];
// void dfs(ll x,bool vis[],int*dp,map<ll,ll> black){
//   vis[x]=true;
//   for(auto it : g[x]){
//     if(!vis[it]){
//       dfs(it,vis,dp,black);
//       dp[x]+=dp[it];
//     }
//   }
//   if(black.find(x)!=black.end()){
//     dp[x]+=1;
//   }
// }

// vl a(1000000)      ;

int main(){
 ios_base::sync_with_stdio(0);
 ll n,m,x,y;
 cin >> n >> m >> x >> y;
 vl a(n),b(m);
 ll i;
 for(i=0;i<n;i++){
   cin >> a[i];
 }
 for(i=0;i<m;i++){
   cin >> b[i];
 }
 sort(a.begin(),a.end());
 sort(b.begin(),b.end());
 ll ai=a[n-1],bi=b[0];
 ll z;
 for(z=x+1;z<=y;z++){
   if(ai<z && bi>=z){
     cout << "No War";
     return 0;
   }
 }
 cout << "War";
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main(void)
{
	char c;

	while(1){
		cin.get(c);
		if(c=='.') break;
			
		stack<char> s;
		if(c=='(' || c=='[') s.push(c);
		else if(c==')' || c==']') s.push(c);

		while(1){
			cin.get(c);
			if(c=='.') {
				cin.get(c);
				if(c=='\n') break;
			}

			if(c=='(' || c=='[') s.push(c);
				
			else if(c==')'){
				if(!s.empty() && s.top()=='(') s.pop();
				else s.push(c);
			}
			else if(c==']'){
				if(!s.empty() && s.top()=='[') s.pop();
				else s.push(c);
			}
		}

		if(s.empty()) cout << "yes" << endl;
		else cout << "no" << endl;

	}

	return 0;
} 

Measured memory_bytes: 1160
from collections import deque


def main():
    n, q = [int(i) for i in input().split()]
    P = [input().split() for i in range(n)]
    process = deque()
    process.extend([
        {'name': p[0], 'time': int(p[1])}
        for p in P
    ])
    sum_time = 0
    while len(process):
        p = process.popleft()
        if p['time'] <= q:
            sum_time += p['time']
            print(p['name'], sum_time)
        else:
            sum_time += q
            p['time'] -= q
            process.append(p)


if __name__ == "__main__":
    main()



Measured memory_bytes: 29640
n = int(input())
 
items=[]

for i in range(n):
  line = list(map(int, input().split()))
  items.append({'a':line[0], 'b':line[1]})
  
sorted_items = sorted(
  items,
  key = lambda x: (x['b'],x['a'])
)


sum = 0
answord = 'Yes'

for i in range(n):
  sum += sorted_items[i]['a']
  if sum > sorted_items[i]['b']:
    answord = 'No'
    break
    
print(answord)

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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
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;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
    //ll a = x*(x-1);
    //ll b = 2;
    //return a/b;
}



int main(){
    ll n,m;
    cin >> n >> m;
    if(n>=2&&m>=2){
        cout << (n-2)*(m-2) << endl;
    }else if(n==1&&m==1){
        cout << 1 << endl;
    }else if(n==1||m==1){
        cout << max(n,m)-2 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ignore ignore
#define pb emplace_back
#define mt make_tuple
#define gcd __gcd
#define bitcount(x)  __builtin_popcount(x)
#define bitcountll(x)  __builtin_popcountll(x)
// Input
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp(p) in2(p.F,p.S)
#define llin(a) cin >> a
#define inl(a) scanf("%lld",&a)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
// Output
#define pr(a) printf("%d ",a)
#define pr2(a,b) printf("%d %d\n",a,b)
#define pr3(a,b,c) printf("%d %d %d\n",a,b,c)
#define prp(p) pr2(p.F,p.S)
#define out(a) printf("%d\n",a)
#define outl(a) printf("%lld\n",a)
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define pinttwod(mat,i,j,n,m) rep(i,n){rep(j,m)pr(mat[i][j]);   lin;}
#define plltwod(mat,i,j,n,m)  rep(i,n){rep(j,m)llpr(mat[i][j]); lin;}
#define byes printf("YES\n")
#define bno printf("NO\n")
#define yes printf("Yes\n")
#define no printf("No\n")
#define lin printf("\n")
// Iterator
#define rep(i,n) for(i=0;i<n;++i)
#define rrep(i,n) for(i=n-1;i>=0;--i)
#define lp(i,a,b) for(i=a;i<b;++i)
#define rlp(i,a,b) for(i=a;i>=b;--i)
#define all(vec) vec.begin(),vec.end()
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
// function
#define sz(x) x.size()
#define inrange(i,a,b) (i>=a && i<=b)
#define FLUSH fflush(stdout)
#define precision(x) cout << setprecision(x) << fixed
#define remax(a,b) a=max(a,b)
#define remin(a,b) a=min(a,b)
#define bhardo(mat,i,j,n,m,t) rep(i,n){rep(j,m)mat[i][j]=t;}
// Debug
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define ck printf("continue\n")
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
	cerr << *it << " = " << a << "\n";
	err(++it, args...);
}
// Data Type
#define ll long long int
#define ii pair<int,int>
#define pli pair<ll,int>
#define triple tuple<int,int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
// Constant
const double PI = acos(-1);
const double eps = (1e-9);
const ll INF = 1e18;
const int M = (1e9)+7;
const int N = (1e5)+5;  // check the limit, man
void solve()
{
    int n,k;
    in2(n,k);
    int x=0;
    while(n>0)
        x++,n/=k;
    out(x);
}
int main()
{
    int t;
    t=1;
    //in(t);
    while(t--)
        solve();
}






Measured memory_bytes: 256
import numpy as np

n, m, c = map(int, input().split())
B = np.array(list(map(int, input().split())))
A = np.array([np.array(list(map(int, input().split()))) for _ in range(n)])

ans = 0
for i in range(n):
  if np.dot(A[i], B) + c > 0:
    ans += 1
    
print(ans)

Measured memory_bytes: 13396
#include <iostream>
#include <string>
using namespace std;
string str,tmp;
int solve(string judge)
{
      for(int i=0;i<judge.length();i++){
            if(str[0]!=judge[i])continue;
            for(int j=i+1;j<judge.length();j++)
            {
                  if(j>=judge.length())break;
                  if(str[1]!=judge[j])continue;
                  for(int k=2;;k++){
                        if(k==str.length())return 1;
                        if(i+(j-i)*k>=judge.length())break;
                        if(str[k]!=judge[i+(j-i)*k])break;

                  }
            }

      }
      return 0;
}

int main()
{
      int x,ctn = 0;
      cin >> x >> str;
      for (int i = 0;i < x ; i++){
            cin >> tmp;
            ctn += solve(tmp);
      }
      cout << ctn << endl;
      return 0;
}

Measured memory_bytes: 1212
#include"bits/stdc++.h"

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef pair<LL, LL> PLL;
typedef vector<PLL> VPLL;
typedef priority_queue<LL> PQ_DESC;
typedef priority_queue<LL, VL, greater<LL>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;
typedef priority_queue<VL> PQ_DESC_VL;
typedef priority_queue<VL, vector<VL>, greater<VL>> PQ_ASC_VL;
typedef priority_queue<PLL> PQ_DESC_PLL;
typedef priority_queue<PLL, vector<PLL>, greater<PLL>> PQ_ASC_PLL;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
//#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SORT_DESC(c) sort((c).rbegin(),(c).rend())
#define REV(c) reverse((c).begin(), (c).end())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF*(LL)INF;
const int MOD = 1e9+7;

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

LL modpow(LL a, LL n) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

void Main()
{
    int n;cin>>n;
    int result = n%1000;
    if(result!=0){
        result = 1000-result;
    }
    cout<<result<<endl;
    
	return;
}

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

Measured memory_bytes: 3632
import numpy as np
import math
import sys
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

s = list(input())
s.reverse()
v = []
v.append(list("dream"))
v.append(list("erase"))
v.append(list("eraser"))
v.append(list("dreamer"))
for i in range(4):
    v[i].reverse()

now = 0
while(1):
    check = False
    for i in range(4):
        if now+len(v[i]) > len(s): continue
        tmp = ''.join(s[now:now+len(v[i])])
        x = ''.join(v[i])
        if tmp == x:
            check = True
            now += len(v[i])
        if check: break
    if not check: break
    if now == len(s): break

if check: print("YES")
else: print("NO")

Measured memory_bytes: 13404
#include <stdio.h>

int main(){
    int S;
    int Sec[4];
    int S1,S2,S3,S4;
    int i;
    unsigned char flag = 0;
    scanf("%d",&S);
    Sec[0] = S / 1000;
    Sec[1] = (S % 1000 ) / 100;
    Sec[2] = (S % 100) / 10;
    Sec[3] = S % 10;
    //printf("%d %d %d %d",S1,S2,S3,S4);
    for(i=1;i<4;i++){
        if(Sec[i-1] == Sec[i]) flag = 1;
    }

    if(flag==1){
        printf("Bad\n");
    }else{
        printf("Good\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
	long N;cin>>N;
	vector<long> A(5);
	for(int i=0;i<5;i++){
		cin>>A[i];
	}long k=*min_element(A.begin(),A.end());
	cout<<5+(N-1)/k<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << max(c - (a - b), 0) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
map<int,int> mp;
int a[200010];
int main(int argc, char const *argv[])
{
	int n;cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	for(int i=0;i<n;i++){
		if(mp[a[i]]>1){
			cout<<"NO"<<endl;
			return 0;
		}
	}
	cout<<"YES"<<endl;
	return 0;
}

Measured memory_bytes: 10368
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;cin>>N;
  vector<int>A(N);for(int i=0;i<N;i++)cin>>A[i];
  int ans=0,t=1;
  for(int i=0;i<N;i++){
    if(A[i]!=t)ans++;
    else {t++;}
  }
  cout<<(t==1?-1:ans);
  
}

Measured memory_bytes: 1024
//INCLUDE
//------------------------------------------
#include <bits/stdc++.h>
//DEFINE
//------------------------------------------
#define ll long long
#define ld long double
#define ALLv(a)  (a).begin(),(a).end()
#define ALL(a,n)  (a),(a)+n
#define vi vector<long long>
#define vd vector<long double>
#define vs vector<string>
//CONST
//------------------------------------------
#define INF 1010000000000000017LL
#define MOD 1000000007LL
#define EPS 1e-12
#define PI 3.14159265358979323846
//REPEAT
//------------------------------------------
#define   FOR(i,m,n) for(ll (i)=(m);   (i)<(n);  (i)++)
#define   REP(i,n)   for(ll (i)=0;     (i)<(n);  (i)++)
#define  REPS(i,x)   for(ll (i)=1;     (i)<=(x); (i)++)
#define  RREP(i,x)   for(ll (i)=(x)-1; (i)>=0;   (i)--)
#define RREPS(i,x)   for(ll (i)=(x);   (i)> 0;   (i)--)
#define  WREP(i,in,j,jn) REP(i,in)REP(j,jn)
//-----------------------------------------
#define dcml(n) fixed<<setprecision(n)
using namespace std;
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; }
ll Factorial(ll n){ ll m=1;while(n>=1)m*=n--;return m; }
ll pow(ll a, ll b, ll mod=INF){
    ll res=1;
    while(b>0){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll getDigit(ll num){
    ll digit=0; 
    while(num!=0){num/=10;digit++;}
    return digit;
}
ll D,N;
ll cnt=0;
vi a(3);
void dfs(ll sm,ll d=1,ll c3=0, ll c5=0, ll c7=0){
    ll x=sm%10;
    (x==3?c3:x==5?c5:c7)++;
    if(sm>N)return;
    if(d>D)return;
    if(c3>0 and c5>0 and c7>0)cnt++;

    sm*=10;
    for(auto r:a){
        dfs(sm+r,d+1,c3,c5,c7);
    }
    return;
}
int main(void){
    cin>>N;
    D=getDigit(N);
    a={3,5,7};
    for(auto r:a){
        dfs(r);
    }
    cout<<cnt<<"\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const int64_t LINF=8931145141919364364,LMOD=998244353;
// const int dy[]={0,-1,0,1,1,-1,-1,1};
// const int dx[]={1,0,-1,0,1,1,-1,-1};

int main() {
	int64_t t[2], a[2], b[2], d[2];
	rep(i,2) cin >> t[i];
	rep(i,2) cin >> a[i];
	rep(i,2) cin >> b[i];
	d[0] = a[0] * t[0] - b[0] * t[0];
	d[1] = a[1] * t[1] - b[1] * t[1];
	if(d[0] + d[1] == 0) {
		cout << "infinity" << endl;
		return 0;
	}
	if(d[0] < 0) {
		d[0] *= -1;
		d[1] *= -1;
	}
	int64_t dd = d[0] + d[1];
	if(d[0] > 0 and dd > 0) {
		cout << 0 << endl;
		return 0;
	}
	// cerr << d[0] << " " << dd << endl;
	int64_t ans = (d[0] / (-dd)) * 2;
	if(d[0] % dd != 0) ans++; 
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
A=[]
for i in range(2):
    a=[]
    for j in map(int,input().split()):
        a.append(j)
    A.append(a)
S=[]
for i in range(1,n+1):
    si=0
    for j in range(1,i+1):
        si+=A[0][j-1]
    for j in range(i,n+1):
        si+=A[1][j-1]
    S.append(si)
print(max(S))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using  namespace std;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 ///freopen("testcase.txt","r",stdin);

   long long int  i,n,sum=0;
   cin>>n;
   for(i=0;i<n;i++)
   {
       sum+=i;
   }
   cout<<sum<<endl;
   return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXS 10
int n;
string s;
long long ans;
long long dfs(int loc,long long sum)
{
  long long res = 0;
  if(loc > n-1) 
  {
    return sum;
  }
  for(int i=loc;i<n;i++)
    {
      long long cnt=0;
      for(int j=loc;j<=i;j++)
	cnt=cnt*10+s[j]-'0';

      res += dfs(i+1,sum+cnt);
    }
	return res;
}
int main(int argc,char const* argv[])
{
  cin >> s;
  n=s.size();
  ans = dfs(0,0);

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

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

#define MOD 1000000007

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


template <class T>
ostream &operator<<(ostream &o, const vector<T>&obj) {
    o << "["; for (int i = 0; i < (int)obj.size(); ++i) o << (i > 0 ? ", " : "") << obj[i]; o << "]"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const vector<vector<T>>&obj) {
    o << "[" << endl; for (int i = 0; i < (int)obj.size(); ++i) o << "  " << obj[i] << endl; o << "]"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const pair<T, U>&obj) {
    o << "(" << obj.first << ", " << obj.second << ")"; return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, const map<T, U>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const set<T>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const multiset<T>&obj) {
    o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}
template <class T>
ostream &operator<<(ostream &o, const queue<T>&obj) {
    queue<T> obj_cp = obj;
    bool first = true;
    o << "{";
    while (!obj_cp.empty()) { o << (!first ? ", " : "") << obj_cp.front(); obj_cp.pop(); first = false; }
    o << "}"; return o;
}

void print() {
    cout << "\n";
}
template<class Head, class... Body>
void print(Head head, Body... body) {
    cout << head << " ";
    print(body...);
}

int main(int argc, char const *argv[]) {
    int N;
    cin >> N;
    vector<unsigned int> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    unsigned int all = 0;
    for (int i = 0; i < N/2; ++i) {
        all ^= (a[i*2] ^ a[i*2+1]);
    }

    for (int i = 0; i < N; ++i) {
        cout << (all ^ a[i]);
        if (i < N-1) cout << " ";
        else cout << endl;
    }

    return 0;
}


Measured memory_bytes: 4020
#include<bits/stdc++.h>
using namespace std;
#define D double
#define lli long long int
#define testcase int t;cin>>t;while(t--)
#define fast_io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb push_back
#define P pair<int,int>
/*bool isprime(lli n)
{
    if(n==1) return 0;
    for(lli i=2;i<=n/2;i++)
    {
        if(n%i==0) return 0;
    }
    return 1;
}
bool issemiprime(lli n)
{
    for(int i=2;i<n;i++)
    {
        if(isprime(i)&&isprime(n/i)&&n%i==0&&i!=n/i){
            return 1;
        }
    }
    return 0;
}
lli extendedgcd(lli q,lli r1,lli r2,lli r,lli s1,lli s2,lli s,lli t1,lli t2,lli t)
{
if(r2==0) return r1;
	r1=r2;
        r2=r;
        s1=s2;
        s2=s;
        t1=t2;
        t2=t;
        q=r1/r2;
        r=r1%r2;
        s=s1-(s2*q);
        t=t1-(t2*q);
return extendedgcd(q,r1,r2,r,s1,s2,s,t1,t2,t);
}
lli gcd(lli a,lli b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
void SOE()
{
    for(lli i=2;i<=100000;i++)
    {
        if(sieve[i]) continue;
        for(lli x=i;x<=100000;x+=i)
        {
            sieve[x]+=1;
        }
    }
}*/
/*bool func(pair<int,int> a,pair<int,int> b)
{
    return a.first<b.first;
}
int dfs(vector<vector<int>> g,int n)
{
    if(g[n].size()==0) return 0;
    if(dp[n]!=-1) return dp[n];
    for(auto x:g[n])
    {
        dp[n]=max(dp[n],1+dfs(g,x));
    }
    return dp[n];
}*/
void solve()
{
    lli n;
    cin>>n;
    double h[n];
    for(int i=0;i<n;i++)
    {
        cin>>h[i];
    }
    D dp[n+1][n+1];
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<n+1;i++)
    {
        for(int j=0;j<=i;j++)
        {
            if(j==0)
            {
                dp[i][j]=(1.0-h[i-1])*dp[i-1][j];
            }
            else{
                dp[i][j]=(h[i-1]*dp[i-1][j-1])+((1.0-h[i-1])*dp[i-1][j]);
            }
        }
    }
    double res=0.0;
    for(int i=n;i>(n/2);i--)
    {
        res+=dp[n][i];
    }
    cout<<fixed<<setprecision(10)<<res;
}
int main()
{
    fast_io;
    solve();
}


Measured memory_bytes: 74116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxN = 100 * 1000 + 9;
const int MOD = 1e9 + 7;
const double EPS = 1e-18;

ll n, k;

void read(){
  cin >> n >> k;
}

void solv(){
  long double ans = 0.00;
  for(int i = 1; i <= n; i++){
    ll cur = i;
    ll de = 1;
    while(cur < k){
      cur *= 2;
      de *= 2;
    }

    //cerr << i << ' ' << de << '\n';
    ans += (1.00 / n) * (1.00 / de);
  }

  cout << ans << '\n';
}

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

  cout << setprecision(10) << fixed;

  read();
  solv();

  return 0;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
ans=-1
if n>=2:
  for i in range(10**(n-1),10**n):
    k=['0']+list(str(i))
    judge=True
    for j in lst:
      if k[j[0]]!=str(j[1]):
        judge=False
        break
    if judge:
      ans=i
      break

elif n==1:
  for i in range(10):
    k=['0']+list(str(i))
    judge=True
    for j in lst:
      if k[j[0]]!=str(j[1]):
        judge=False
        break
    if judge:
      ans=i
      break
print(ans)


Measured memory_bytes: 63012
#include <stdio.h>
int main(void)


{
	int a, b, c, d;
	scanf("%d %d %d", &a,&b,&c);
	if(a>b)
	{
		d = b;
		b = a;
		a = d;
	}
	if(b>c)
	{
		d = b;
		b = c;
		c = d;
		
	}
	if(b<a)
	{
		d = b;
		b = a;
		a = d;
	}
	printf("%d %d %d\n",a,b,c);
	return 0;
}

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

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

    set<char> set;

    bool b = false;
    for (char c : s) {
        if (set.find(c) == set.end())
            set.insert(c);
        else {
            b = true;
            break;
        }
    }

    cout << (b ? "no" : "yes") << endl;
}

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

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MAX_N 100000
#define INF 1e9

using ll = long long;

const ll mod = LLONG_MAX;

/*
長さがそれぞれL[i]であるようなN本紐があります。
これらの紐を切って、
同じ長さの紐をK本作る時の最長の長さを求めなさい。
答えは小数点以下2桁までを切り捨てで出力しなさい。

1<=N<=100000
1<=K<=100000
1<=L<=1000000

入力
N=4
K=11
L=={8.02,7,43,4,57,5.39}

出力 2.00
*/

int N,K;
double L[MAX_N];

//条件を満たすか判定
bool C(double x){
  int num = 0;
  REP(i,N){
    num+=(int)(L[i]/x);
  }
  return num>=K;
}

void solve(){
  //解の存在範囲を初期化
  double lb = 0,ub =INF;

  //解の存在範囲が十分に狭くなるまで繰り返す
  REP(i,100){
    double mid=(lb+ub)/2;
    if(C(mid)) lb = mid;
    else ub=mid;
  }
  printf("%.2f\n",floor(ub*100)/100);
}

int main(){
  int ia=0,ib=0,ic=0;
  char a,b,c,x='a';
  string Sa,Sb,Sc;
  cin>>Sa>>Sb>>Sc;
  while(1){
    if(x=='a'){
      x=Sa[ia];
      if(ia==Sa.size()){
        cout<<'A'<<endl;
        return 0;
      }
      ia++;
    }
    if(x=='b'){
      x=Sb[ib];
      if(ib==Sb.size()){
        cout<<'B'<<endl;
        return 0;
      }
      ib++;
    }
    if(x=='c'){
      x=Sc[ic];
      if(ic==Sc.size()){
        cout<<'C'<<endl;
        return 0;
      }
      ic++;
    }

  }
  return 0;
}


Measured memory_bytes: 256
#!usr/bim/python
#! -*- coding: utf-8 -*-

n = raw_input()
n = int(n)

s1 = raw_input()
s2 = raw_input()

ans = 1

mod = 1000000007

i = 0

if s1[i] == s2[i]:
    ans = ans * 3
    i += 1
else:
    ans = ans * 6
    i += 2

while i < n:
    if s1[i-1] == s2[i-1]:
        if s1[i] == s2[i]:
            ans = ans * 2 % mod
            i += 1
        else:
            ans = ans * 2 % mod
            i += 2
    else:
        if s1[i] == s2[i]:
            i += 1
        else:
            ans = ans * 3 % mod
            i += 2

print ans


Measured memory_bytes: 2568
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;
typedef long long ll;

int main() {
	string s;
	cin >> s;
	int a[3];
	for (int i = 0; i < 3; i++)
	{
		a[i] = (int)s[i];
	}
	sort(a, a + 3);

	if (a[0] == 'a'&&a[1] == 'b'&&a[2] == 'c')
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

}

Measured memory_bytes: 256