akhauriyash/Code-Regression huggingface dataset:
Limit = 2000 #上限を決める
CMB = [[0]*(Limit+1) for _ in range(Limit+1)]
def cmb_table(Limit):
  for i in range(Limit+1):
    for j in range(Limit+1):
      if j == 0 or j == i: #端っこの場合
        CMB[i][j] = 1
      else:
        CMB[i][j] = CMB[i-1][j-1] + CMB[i-1][j]

cmb_table(Limit) #これ必須！
#print(CMB[3][2])
N,K = map(int,input().split())
MOD = pow(10,9)+7
red = N-K
blue = K
for i in range(1,K+1):
  p = CMB[blue-1][i-1]%MOD
  #print(p,i)
  if i-1 > red:
    print(0)
  else:
    ans = p*CMB[red+1][i]%MOD
    print(ans)


Measured memory_bytes: 370664
#include<stdio.h>
int lb(int l,int r,int n,int *d){
  int m=(l+r)/2;
  if(l==r)return m;
  return n<=d[m]?lb(l,m,n,d):lb(m+1,r,n,d);
}
int ub(int l,int r,int n,int *d){
  int m=(l+r)/2;
  if(l==r)return m;
  return n<d[m]?ub(l,m,n,d):ub(m+1,r,n,d);
}
int cnt(int l,int r,int n,int *d){return ub(l,r,n,d)-lb(l,r,n,d);}
int n,m,s,g,r,t,a,b,l,ta[100010],to[600010],nt[600010],q[600010];
int main(){
  int c[2][100010]={};
  int i,f[100010]={};
  long long ans=0;
  scanf("%d %d %d %d",&n,&m,&s,&g);
  for(i=0;i<n;i++)ta[i+1]=-1;
  for(i=0;i<m;i++){
    scanf("%d %d",&a,&b);
    nt[i  ]=ta[to[i+m]=a];
    nt[i+m]=ta[to[i  ]=b];
    ta[a]=i  ;
    ta[b]=i+m;
  }
  q[t=0]=s;
  c[0][0]=0;
  f[s]=1;
  for(r=1;r-t;t++){
    if(q[t]==g)l=c[0][t];//printf("%d %d\n",q[t],c[0][q[t]]);
    for(i=ta[q[t]];i+1;i=nt[i]){//printf("%d ",c[0][q[t]]);
      if(f[to[i]])continue;//printf("%d ",c[0][q[t]]);
      c[0][r]=c[0][t]+1;//printf(":%d %d %d\n",q[t],c[0][r],to[i]);
      f[to[i]]=1;
      q[r++]=to[i];
    }
  }//printf("\n");
  m=r;//printf("%d %d\n",r,l);
  //for(i=0;i<r;i++)printf("%d ",c[0][i]);printf("\n");
  q[t=0]=g;
  f[g]=2;
  for(r=1;r-t;t++){
    ans+=cnt(0,m-1,l-2-c[1][t],c[0]);
    //printf("%d %d %d\n",a,c[1][t],q[t]);
    for(i=ta[q[t]];i+1;i=nt[i]){
      if(f[to[i]]-1)continue;
      c[1][r]=c[1][t]+1;
      f[to[i]]=2;
      q[r++]=to[i];
    }
  }
  printf("%lld\n",ans);
  return 0;
}
      

Measured memory_bytes: 7432
/*
ЗАПУСКАЕМ ВЫСОКОГО
░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
   
    
    
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }  
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define next next228
#define rank rank228


int main() {
    long long A, B;
    cin >> A >> B;
    bitset<60> bitA(A);
    bitset<60> bitB(B);
    int r = -1, k = -1;
    for (int i = 59; i >= 0; i--) {
        if (bitA.test(i) != bitB.test(i)) {
            r = i;
            break;
        }else{
            bitA.reset(i);
            bitB.reset(i);
        }
    }
    A = bitA.to_ullong();
    B = bitB.to_ullong();
    if (r == -1){
        cout << 1 << endl;
    } else {
        for (int i = r - 1; i >= 0; i--) {
            if (bitB.test(i)) { 
                k = i;
                break;
            }
        }
        if (pow(2, k + 1) >= A) {
            cout << dec << (long long)((1LL << (r + 1)) - A) << endl;
        }else{
            cout << dec << (2 * (long long)((1LL << r) - A) + (1LL << (k + 1))) <<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);    
        int n = Integer.parseInt(sc.next());
        String S = sc.next();
        String[] s = S.split("");
        int i=0;
        int j=n-1;
        int count = 0;
        while(i<j) {
            while(i<n) {
                if(s[i].equals("W")) {
                    break;
                }
                i++;
            }
            
            while(0<j) {
                if(s[j].equals("R")) {
                    break;
                }
                j--;
            }
            
            if(i<j) {
                String swap = s[i];
                s[i] = s[j];
                s[j] = swap;
                count++;
                i++;
                j--;
            }
        }
        System.out.println(count);
        
    }
}


Measured memory_bytes: 65944
#include <bits/stdc++.h>
#define INF 100100100
#define MOD 1000000007

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

#define FOR(i,n) for(ll i=0;i<n;i++)

struct edge{ll to,cost;};

int main(int argc, char const* argv[]){
   ios::sync_with_stdio(false);
   cin.tie(0); 
   string s;
   cin >> s;
   int ans = 700;
   for(int i=0;i<3;i++)
      if(s[i] == 'o')ans+=100;
   cout << ans << endl;
   return 0;
}


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

int main() {
    long long k, a, b;
    cin >> k >> a >> b;

    long long ans;

    ans = ((k - a + 1) / 2 * (b - a)) + k - (k - a + 1) / 2 * 2 + 1;
    ans = max(ans, k + 1);
    
    cout << ans << endl;
}


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

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> res(N, 0);
    for(int i = 0; i < K; i++) {
        int d;
        cin >> d;
        for(int i = 0; i < d; i++) {
            int A;
            cin >> A;
            A--;
            res[A]++;
        }
    }
    int ans = 0;
    for(int i = 0; i < N; i++) {
        if(res[i] == 0) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>

int main(){
    int r, g, b;
    std::cin>>r>>g>>b;
    std::cout<<((100 * r + 10 * g + b) % 4 == 0 ?
            "YES" : "NO")<<std::endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cctype>
#include<climits>
#include<bitset>
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define ull unsigned long long int
#define rep(i,n) for(i=0;i<n;i++)
#define fin(ans) cout<<(ans)<<endl
#define INF INT_MAX
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define vvc vector<vector<char> >
#define vvs vector<vector<string> >
#define P 1000000007
using namespace std;
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;}
const long long LLINF=1LL<<60;
//set<int>::iterator it;


int main(void){ios::sync_with_stdio(false);cin.tie(0);
//////////////////////////////////////////////////////
	
	int sw=0;
	int i,j;
	int n,m,k,t;
	cin>>n>>m;
	vector<vector<int> > v(m,vector<int>());
	for(i=0;i<m;i++){
		cin>>k;
		for(j=0;j<k;j++){
			cin>>t;
			v[i].push_back(t);
		}
	}
	int p[m];
	rep(i,m)cin>>p[i];
	int ans=0;
	vector<int> st(n*n,0);
	vector<int> swn(m,0);
	int onsw;
	for(sw=0;sw<pow(2,n);sw++){//すべてのスイッチ 
		onsw=0;
		rep(i,n*n)st[i]=0;
		rep(i,m)swn[i]=0;
		t=sw;
		i=0;
		while(t>0){
			st[i]=t%2;
			t/=2;
			i++;
		}
//		for(i=0;i<n;i++)cout<<st[i];
//		cout<<endl;
		rep(i,m){//各電球 
			rep(j,v[i].size()){//スイッチがオンか 
				if(st[v[i][j]-1]==1)swn[i]++;
			}
			if(swn[i]%2==p[i])onsw++;
		}
		if(onsw==m)ans++;
	}	
	fin(ans);
	
	
	
//////////////////////////////////////////////////////
return 0;}











Measured memory_bytes: 256
# set
num_people = gets.chomp.to_i
who_is_boss = gets.chomp.split(" ").map(&:to_i)
boss = 0
count_arr = Array.new(num_people, 0)

# main
0.upto(who_is_boss.length - 1) do |i|
  boss = who_is_boss[i] - 1
  count_arr[boss] += 1
end

0.upto( count_arr.length - 1 ) do |j|
  print ("#{count_arr[j]}\n")
end

Measured memory_bytes: 35776
import string


def main():
  alpha = string.ascii_lowercase

  def to_n(X, n, list_=[]):
    X_dumy = X
    while X_dumy > 0:
      list_.insert(0, X_dumy % n)
      X_dumy = int(X_dumy/n)
    return list_

  N = int(input())
  res = N
  counter = 0
  while res > 0:
    counter += 1
    res -= 26**counter

  res += 26**counter
  res -= 1
  idx = to_n(res, 26)
  # print(len(idx), counter)
  while len(idx) < counter:
    idx.insert(0, 0)
  # print(res)
  # print(idx)
  print('{:<}'.format(''.join(list(map(lambda i: alpha[i], idx)))))

if(__name__ == '__main__'):
  main()

Measured memory_bytes: 9868
#####################################################################################################
##### ナップサック問題　（価値が小さい場合）
#####################################################################################################
"""

経路を状態の添え字に取るような事は無い
経路の末端の情報のみを横軸の添え字に取ることが多い
例：一年生　⇒　k項目までの総和
   パスタ　⇒　k日目に食べたパスタ
   暑い日々⇒　k日目に着た服

DPテーブルにおいて、ある値以降の全てで 1 となる場合、
その値でDPテーブルを切ってしまって、
indexがその値を超えるごとに、DPテーブルの上限に +1 をしていくというアイデアで計算量を減らせる
例: https://atcoder.jp/contests/tdpc/submissions/14958104

初期条件を常に意識するように！

ベンチマーク
（重複なし）
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4641577#1
(重複あり)
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4641577#1

"""


import sys
input = sys.stdin.readline



M, W = map(int, input().split())                                # M: 品物の種類 W: 重量制限
single = True                                                   # True = 重複なし

price_list = [0]
weight_list = [0]
for _ in range(M):
    weight, price = map(int, input().split())
    price_list.append(price)
    weight_list.append(weight)


################################################################################################################################################

V = sum(price_list)
dp_max = W + 1                                                  # 総和重量の最大値


dp = [[dp_max] * (V + 1) for _ in range(M + 1)]                 # 左端と上端の境界条件で W, M を一個ずつ多めに取る
""" dp[item <= M ][weight <= V] = 価値を固定した時の"最小"重量 """

for item in range(M+1):                                         # 左端の境界条件
    dp[item][0] = 0                                             # 価値 0 を実現するのに必要な品物の個数は 0 個

# for weight in range(W+1):                                     # 上端の境界条件
#     dp[0][weight] = dp_min                                    # 0 種類の品物で実現できる価値総額は存在しない　（dpの初期化で自動的に課せる場合が多い）


for item in range(1,M+1):                                       # 境界条件を除いた M 回のループ（※ f[item] = g.f[item-i] の漸化式なので、list index out of range となる）
    for price in range(1, V+1):
        if price < price_list[item]:                            # price (総価値) < price_list[item] (品物の価値) の時は無視してよい
            dp[item][price] = dp[item - 1][price]
        else:
            temp = dp[item - single][price - price_list[item]] + weight_list[item]  # single = True: 重複なし
            if temp < dp[item-1][price]:                        # min(dp[item-1][price], temp)
                dp[item][price] = temp
            else:
                dp[item][price] = dp[item-1][price]

print(max(price for price in range(V+1) if dp[M][price] <= W))

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

#define len_sequence_max 200000U

#define max(a, b) (((a) > (b)) ? (a) : (b))

int task_C (const unsigned int* len_sequence, unsigned int val_sequence[])
{
	// arrays for this function
	unsigned int maxval_left [len_sequence_max];
	unsigned int maxval_right[len_sequence_max];

	// support variables for this function
	register unsigned int itr;

	// STEP.01
	// initialize the array to store the maximum values of the given seuquence
	maxval_left [                0U] = 0U;
	maxval_right[*len_sequence - 1U] = 0U;

	// STEP.02
	// search the maximum values of the given sequence
	for (itr = 0U;                 itr < *len_sequence - 1U; itr++) { maxval_left [itr + 1U] = max(maxval_left [itr], val_sequence[itr]); }
	for (itr = *len_sequence - 1U; itr > 0U;                 itr--) { maxval_right[itr - 1U] = max(maxval_right[itr], val_sequence[itr]); }

	// STEP.03
	// output the answer of this task
	for (itr = 0U; itr < *len_sequence; itr++) { printf("%d\n", max(maxval_left[itr], maxval_right[itr])); }
	
	// STEP.END
	return EXIT_SUCCESS;
}

int main (void)
{
	// variables for main process
	unsigned int N;

	// arrays for main process
	unsigned int A[len_sequence_max];

	// support variables for main process
	register int rtvl;

	// STEP.01
	// read out the given data
	// (the length of the given sequence)
	rtvl = scanf("%d", &N);

	// STEP.02
	// read out the given data
	// (the value of the given sequence)
	for (register size_t itr = 0; itr < N; itr++) { rtvl = scanf("%d", &A[itr]); }

	// STEP.04
	// calculate & output the answer of this task
	rtvl = task_C(&N, A);

	// STEP.END
	return EXIT_SUCCESS;
}

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

int main(){
    int x,y,xx,yy,cntx=0,cnty=0;
    cin>>x>>y>>xx>>yy;

    cntx=abs(x-xx);
    cnty=abs(y-yy);

    if(x<=xx&&y<=yy) cout<<xx-cnty<<" "<<yy+cntx<<" "<<xx-cnty-cntx<<" "<<yy+cntx-cnty<<endl;
    else if(x>=xx&&y>=yy) cout<<xx+cnty<<" "<<yy-cntx<<" "<<xx+cnty+cntx<<" "<<yy-cntx+cnty<<endl;
    else if(x>=xx&&y<=yy) cout<<xx-cnty<<" "<<yy-cntx<<" "<<xx-cnty+cntx<<" "<<yy-cntx-cnty<<endl;
    else if(x<=xx&&y>=yy) cout<<xx+cnty<<" "<<yy+cntx<<" "<<xx+cnty-cntx<<" "<<yy+cntx+cnty<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define MOD 1000000007
#define INF 93193111451418101
#define MIN -93193111451418101
#define EPS 1e-11
using namespace std;

int main() {
  ll grid[4][4];
  REP(i, 3) {
    REP(j, 3) { cin >> grid[i][j]; }
  }
  REP(i, 3) {
    if (grid[i][0] - grid[i][1] != grid[0][0] - grid[0][1] ||
        grid[i][1] - grid[i][2] != grid[0][1] - grid[0][2]) {
      cout << "No" << endl;
      return 0;
    }
  }
  REP(i, 3) {
    if (grid[0][i] - grid[1][i] != grid[0][0] - grid[1][0] ||
        grid[1][i] - grid[2][i] != grid[1][0] - grid[2][0]) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 256
#import collections 
#=input()
n=int(input())
#=map(int,input().split())
#=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]
cnt = 0
hey = 0
for a in range(1, n):
    for b in range(a, n):
        if a * b >= n:
            break
        if a != b:
            cnt += 1
        else:
            hey += 1
print(cnt * 2 + hey)

Measured memory_bytes: 9144
import re
s = input()

ans = ""
tmp_ans = ""
for i in range(len(s)):
    if re.fullmatch(r"[ATGC]", s[i]):
        tmp_ans += s[i]
    else:
        if len(ans) < len(tmp_ans):
            ans = tmp_ans
        tmp_ans = ""

if len(ans) < len(tmp_ans):
    ans = tmp_ans

print(len(ans))


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

int main(void) {
	int n,m,flag;
	char a[50][51],b[50][51];
	
	scanf("%d %d",&n,&m);
	
	for (int i = 0;i < n;i++) {
		scanf("%s",a[i]);
	}
	for (int i = 0;i < m;i++) {
		scanf("%s",b[i]);
	}
	
	for (int i = 0;m+i <= n;i++) {
		for (int j = 0;m+j <= n;j++) {
			if (!strncmp(a[i]+j,b[0],m)) {
				flag = 1;
				for (int k = 1;k < m;k++) {
					if (strncmp(a[i+k]+j,b[k],m)) {
						flag = 0;
						break;
					}
				}
				if (flag) {
					printf("Yes\n");
					return 0;
				}
			}
		}
	}
	printf("No\n");
	
	return 0;
}


Measured memory_bytes: 128
//g++ -std=gnu++14 a.cpp
//#include <bits/stdc++.h>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
#include <math.h>

using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;
#define P pair<int,int>

vector<int> di = {-1,0,1,0};
vector<int> dj = {0,-1,0,1};
vector<string> s(20);
vector<vector<int>> dist(20,vector<int>(20,INF));

void update(int i, int j,int x, queue<P> &q){
  if(dist[i][j] != INF)return;
  dist[i][j] = x;
  P p(i,j);
  q.push(p);
  //if(!q.empty())cout << "pushしたよ" << endl;

  return;
}

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> s(H);
  rep(i,H)cin >> s[i];
  int ans = 0;
  rep(i,H)rep(j,W){
    if(s[i][j] == '#')continue;
    rep(a,20)rep(b,20)dist[a][b] = INF;
    queue<P> q;
    update(i,j,0,q);
    while(!q.empty()){
      int ni = q.front().first;
      int nj = q.front().second;
      q.pop();
      rep(a,4){
        int nni = ni + di[a];
        int nnj = nj + dj[a];
        if(nni < 0 || nni >= H)continue;
        if(nnj < 0 || nnj >= W)continue;
        if(s[nni][nnj] == '#')continue;
        update(nni,nnj,dist[ni][nj]+1,q);
      }
    }
    rep(a,H)rep(b,W){
      if(dist[a][b] == INF)continue;
      if(ans < dist[a][b])ans = dist[a][b];
    }
    /*
    rep(a,H){
      rep(b,W){
        cout << dist[a][b] << " ";
      }
      cout << endl;
    }*/
  }
  cout << ans << endl;
}


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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    ll n;
    cin >> n;
    ll ans = 0;
    FOR(i, 1, n+1){
        if(i%3 == 0 || i%5 == 0) continue;
        ans += i;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



string s;
int k;
void solve(){
	cin >> s >> k;
	int n = s.size();
	
	for(int i = 0; i < n; i++){
		if(k < 26-(s[i]-'a')) continue;
		if(s[i] != 'a'){
			k-=26-(s[i]-'a');
			s[i] = 'a';
		}
	}
	s[n-1] = (char)(s[n-1]+k%26);
	cout << s << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 592
import java.io.*;
import  java.util.*;
import static java.lang.System.in;

public class Main{
    static int n,m;
    static long[] head,pos;
    public static void main(String[] args)throws IOException{
        Scanner sc = new Scanner(System.in);
        //BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        //String[] buf = reader.readLine().split(" ");
        char[] s = sc.next().toCharArray();
        char[] di = new char[]{'A','C','G','T'};
        HashSet<Character> dic = new HashSet<>();
        for(char w:di) dic.add(w);
        int ans = 0;
        for(int i=0;i<s.length;i++){
            if(!dic.contains(s[i])) continue;
            int j = i+1;
            while(j<s.length&&dic.contains(s[j])) j++;
            ans = Math.max(ans,j-i);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 23252
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
  int ans=0;
  int max=0;
  char s[4];
  scanf("%s",s);

  for(int i=0;i<3;i++)
  {
    if(s[i]=='S') ans*=0;
    else ans+=1;
    if(max<ans) max=ans;
  }

  printf("%d\n",max);

  return 0;
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(...) out(__VA_ARGS__);cout<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void out(){} template<class T,class... U> void out(T t,U ...u){cout<<t<<" ";out(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(string, S);
  print(S[2] == S[3] && S[4] == S[5] ? "Yes" : "No");
}


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

using namespace std;

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

	vector<int> a(n);
	for (auto &v : a) cin >> v;

	vector<int> box(n);
	for (int i = n; i >= 1; i--) {
		int ball = 0;
		for (int j = i + i; j <= n; j+=i) {
			ball += box[j - 1];
		}

		box[i - 1] = ball % 2 != a[i - 1];
	}

	vector<int> b;
	for (int i = 0; i < n; i++) {
		if (box[i]) {
			b.push_back(i + 1);
		}
	}

	cout << b.size() << endl;
	for (int i = 0; i < (int)b.size(); i++) {
		if (i) cout << " ";
		cout << b[i];
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3064
using System;
using System.Linq;

namespace AGC115_A
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine();

            var b = 0;
            long cnt = 0;
            foreach (var i in Enumerable.Range(0, s.Length))
            {
                if (s[i] == 'B') b++;
                if (s[i] == 'W') cnt += b;
            }

            Console.WriteLine(cnt);
        }
    }
}


Measured memory_bytes: 13240
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//大小比較(大)
long long int big(long long int a, long long int b) {
	if (a >= b) {
		return a;
	}
	else {
		return b;
	}
}

//大小比較(小)
long long int small(long long int a, long long int b) {
	if (a >= b) {
		return b;
	}
	else {
		return a;
	}
}

main() {
	long long int n, m, k = 0;
	char str[5];
	scanf("%lld%lld", &n,&m);

	if (m >= n) { printf("0"); }
	else { printf("%lld", n - m); }

	
}


Measured memory_bytes: 128
import java.util.*;

public class Main {
	  public static void main(String args[]){
      	Scanner scan = new Scanner(System.in);
            
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int d = scan.nextInt();
            
        if( a*b >= c*d )System.out.println(a*b);
        else System.out.println(c*d);
	  }
}

Measured memory_bytes: 21332
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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;}
const int P = 1000000007;
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z temp.cpp
//./a.out






int main(void){ios::sync_with_stdio(false);cin.tie(0);
///////////////////////////////////////////////////////
int n;
cin >> n;
string w[n],s[n];
rep(i,n){
    cin >> w[i];
    s[i] = w[i];
}

sort(s,s+n);


for(int i=0;i<n-1;i++){
    if(s[i]==s[i+1]){
        cout << "No" << endl;
        return 0;
    }
}


    rep(i,n-1){
        if(w[i][w[i].size()-1]==w[i+1][0]){
         
         if(i == n-2){

             cout << "Yes" << endl;
         }
     }
     else{
         cout << "No" << endl;
         return 0;
     }
  }

///////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    p,q=map(int,input().split())
    g=math.gcd(p,q)

    p//=g
    q//=g

    
    
    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []
    
        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)
    
        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break
    
            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0
    
        return [prime for prime in prime_list if prime != 0]
    
    
    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""
    
        if num <= 1:
            # 例えば1を食ったときの対処の仕方は問題によって違うと思うのでそのつど考える。
            # cf. https://atcoder.jp/contests/abc110/submissions/12688244
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)
    
            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452
    
            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1
    
            return dict_counter

    d=prime_factorization_2(q)
    ans=1
    for k in d.keys():
        ans*=k
    print(ans)
resolve()


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

typedef long long ll;
typedef pair<ll, ll> pll;

#define m0(x) memset(x, 0, sizeof(x))
#define all(x) x.begin(), x.end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define asort(x) sort(all(x));
#define dsort(x, t) sort(x.begin(), x.end(), greater<t>());
#define dump(x)  cout << #x << " = " << (x) << endl
#define vuniq(v) v.erase(unique(v.begin(), v.end()), v.end());
#define minse(m, s) m.insert(make_pair(s, 1));
#define mfin(m, s) m.find(s) != m.end()

#define YES(n) cout << ((n) ? "YES" : "NO" ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl

const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

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

    double ans = (double)(v[0] + v[1]) / 2;
    for (int i = 2; i < n; i++) {
        double value = (double)(ans + v[i]) / 2;
        ans = value;
    }
    
    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

Measured memory_bytes: 3732
// stdin
macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}


// Test
macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

#[allow(dead_code)]
fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 {
        return x;
    }
    gcd(y, x % y)
}

#[test]
fn test_primes() {
    assert_eq!(primes(1), vec![1]);
    assert_eq!(primes(140), vec![1, 2, 2, 5, 7])
}

#[allow(dead_code)]
fn primes(num: i64) -> Vec<i64> {
    let mut ans = vec![1];
    let mut cur = num;
    for i in 2.. {
        if i * i > num { break; }
        if cur % i == 0 {
            while cur % i == 0 {
                ans.push(i);
                cur /= i;
            }
        }
    }
    if cur > 1 {
        ans.push(cur);
    }
    return ans;
}


test! {
r"RRS
" => r"2",

r"SSS
" => r"0",

r"RSR
" => r"1"
}

use proconio::{input, fastout};
use proconio::source::auto::AutoSource;

fn solve(src: &str) -> String {
    let source = AutoSource::from(src);
    input! {
       from source,
       s:String,
    }
    let s: String = s;
    // todo s can be str?

    let ans = if s.contains("RRR") {
        "3"
    } else if s.contains("RR") {
        "2"
    } else if s.contains("R") {
        "1"
    } else {
        "0"
    };

    format!("{}", ans.to_string())
}



#[fastout]
fn main() {
    println!("{}", solve(&stdin!()));
}



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

void f(const string &s, int &x, int &y) {
  if (s == "AB") x = 0, y = 1;
  else if (s == "AC") x = 0, y = 2;
  else x = 1, y = 2;
  return;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  vector<int> a(3);
  cin >> n >> a[0] >> a[1] >> a[2];
  
  vector<string> s(n);
  for (int i = 0; i < n; i++) cin >> s.at(i);
  
  vector<int> ans;
  if (a[0] + a[1] + a[2] == 0) {
    cout << "No\n";
    return 0;
  }
  else if (a[0] + a[1] + a[2] == 1) {
    for (int i = 0; i < n; i++) {
      int x, y;
      f(s.at(i), x, y);
      if (a[x] == 0 && a[y] == 0) {
        cout << "No\n";
        return 0;
      }
      else {
        if (a[x] == 0) ans.emplace_back(x);
        else ans.emplace_back(y);
        swap(a[x], a[y]);
      }
    }
  }
  else {
    int x, y;
    f(s.at(0), x, y);
    if (a[x] == 0 && a[y] == 0) {
      cout << "No\n";
      return 0;
    }
    for (int i = 0; i < n; i++) {
      f(s.at(i), x, y);
      if (a[x] == 0) {
        ans.emplace_back(x);
        a[x]++;
        a[y]--;
      }
      else if (a[y] == 0) {
        ans.emplace_back(y);
        a[y]++;
        a[x]--;
      }
      else if (a[x] == 1 && a[y] == 1) {
        if (i != n - 1) {
          int x2, y2;
          f(s.at(i + 1), x2, y2);
          if (x == x2 || x == y2) {
            ans.emplace_back(x);
            a[x]++;
            a[y]--;
          }
          else {
            ans.emplace_back(y);
            a[y]++;
            a[x]--;
          }
        }
        else {
          ans.emplace_back(x);
          a[x]++;
          a[y]--;
        }
      }
      else {
        if (a[x] < a[y]) {
          ans.emplace_back(x);
          a[x]++;
          a[y]--;
        }
        else {
          ans.emplace_back(y);
          a[y]++;
          a[x]--;
        }
      }
    }
  }
  
  cout << "Yes\n";
  for (int i = 0; i < ans.size(); i++) {
    cout << (char) (ans.at(i) + 'A') << '\n';
  }
}

Measured memory_bytes: 7020
from bisect import bisect
from collections import defaultdict
def main():
	n, k = map(int, input().split())
	*a, = map(int, input().split())
	idx = defaultdict(list)
	for i, x in enumerate(a):
		idx[x].append(i)
	m = (k * n).bit_length()
	dub = [[-1] * n for _ in range(m)]
	for i, x in enumerate(a):
		if i == idx[x][-1]:
			dub[0][i] = n + idx[x][0] - i
		else:
			dub[0][i] = idx[x][bisect(idx[x], i)] - i
	# print(dub[0])
	for i in range(m - 1):
		for j in range(n):
			if dub[i][j]<n*k and dub[i][j]!=-1:
				dub[i + 1][j] = dub[i][j] + 1 + dub[i][(j + dub[i][j] + 1) % n]
	# print(dub)
	now = -1
	for i in range(m - 1, -1, -1):
		if dub[i][(now+1)%n]!=-1 and now + 1 + dub[i][(now + 1) % n] < n * k:
			now += 1 + dub[i][(now + 1) % n]
	# print(now)
	if now == n * k:
		print("")
		exit()
	b = a[(now + 1) % n:]
	# print(b)
	inQ = {x: False for x in b}
	Q = []
	for x in b:
		if inQ[x]:
			while Q[-1] != x:
				inQ[Q.pop()] = False
			Q.pop()
			inQ[x] = False
		else:
			inQ[x] = True
			Q.append(x)
	print(" ".join(map(str, Q)))

if __name__ == '__main__':
	main()


Measured memory_bytes: 190784
#include <stdio.h>
int main (){
int N,flag= 0,j=0;
scanf("%d",&N);
char S [N];
scanf("%s",S);
for (int i =N/2;i < N; i++){
	if(N % 2 != 0){
		flag++;
		break;
	}else if (S[j] == S[i]){
		j++;
		
	}else {
		flag++;
		break;
	}
}
	flag != 0 ? puts ("No") : puts ("Yes");
	
	return 0;
}

Measured memory_bytes: 1640
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include"bits/stdc++.h"
using namespace std;
//#define int long long
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int> P;
constexpr long long inf = 1e17;
constexpr int mod = 1000000007;
int V[270000], W[270000];
int v[100006], L[100006];
ll dp[512][100006];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	rep(i, n)cin >> V[i] >> W[i];
	int q; cin >> q;
	dp[0][W[0]] = V[0];
	rep(j, 100000)dp[0][j + 1] = max(dp[0][j], dp[0][j + 1]);
	for (int i = 1; i < min(n, 511); i++) {
		rep(j, 100001) {
			dp[i][j] = max(dp[i][j], dp[(i - 1)>>1][j]);
			if (j + W[i] <= 100000)dp[i][j + W[i]] = max(dp[i][j + W[i]], dp[(i - 1)>>1][j] + V[i]);
		}
		rep(j, 100000)dp[i][j + 1] = max(dp[i][j], dp[i][j + 1]);
	}
	rep(i, q) {
		cin >> v[i] >> L[i]; v[i]--;
		vector<int>t;
		while (v[i] >= 511) {
			t.emplace_back(v[i]);
			v[i] = (v[i] - 1) >>1;
		}
		ll ans = 0;
		ll v2, w2;
		rep(j, 1 << t.size()) {
			v2 = 0, w2 = 0;
			rep(k, t.size()) {
				if (j&(1 << k)) {
					v2 += V[t[k]];
					w2 += W[t[k]];
				}
			}
			if (w2 <= L[i]) {
				ans = max(ans, v2 + dp[v[i]][L[i] - w2]);
			}
		}
		cout << ans << "\n";
	}
}

Measured memory_bytes: 405744
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
  
 int N;
  int A;
  cin >> N >> A;
  int x=N%500;
  if (x <=A) {
    cout << "Yes" << endl;
  }
else {
  cout << "No" << endl;
}
}


Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdlib.h>
using namespace std;

int main()
{
	string a, b;
	cin >> a;
	cin >> b;

	int count = 0;
	for (int i = 0; i < 3; i++) {
		if (a[i] == b[i])
			count++;
	}

	cout << count << endl;

	return 0;
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;
/*
Node treeMinimum(Node x){


}
*/
Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key) return u;
  
  if(k<u->key)return treeSearch(u->left,k);
  else return treeSearch(u->right,k); 

}
/*
Node treeSuccessor(Node x){


}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y

  if(z.left==NIL || z.right == NIL) y=z;
  else y=treeSuccessor(z);

  if(y.left==NIL) x=y.left;
  else x= y.right;

  if(x!=NIL) x.p=y.p;

  if(y.p==NIL) 

}
*/
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key) x=x->left;
    else x=x->right;
  }
  z->parent=y;

  if(y==NIL) root=z;
  else if(z->key< y->key) y->left=z;
  else y->right=z;

}

void inorder(Node u){
  if(u!=NIL) {
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }


}
void preorder(Node u){
  if(u!=NIL){
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }

}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);

      //  if ( t != NIL ) printf("yes\n");
      //  else printf("no\n");
    } 
    else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } 
    else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } 

    
    /*else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
    */
  }

  return 0;
}

Measured memory_bytes: 24040
#include<bits/stdc++.h> 
using namespace std;
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define pii pair<ll,ll>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
# define ll long long int
int main() 
{ 
  
  int n;
  cin>>n;
  double a[3000];
  int i,j;
  for(i=1;i<=n;i++)
  	cin>>a[i];
 double  dp[3000][3000];
 dp[1][0]=1-a[1];
  dp[1][1]=a[1];
  for(i=2;i<=n;i++)
  	dp[i][0]=dp[i-1][0]*(1-a[i]);
for(i=2;i<=n;i++)
  	dp[i][i]=dp[i-1][i-1]*a[i];
  for(i=2;i<=n;i++)
  	for(j=1;j<i;j++)
  	{
  		dp[i][j]=dp[i-1][j-1]*a[i]+dp[i-1][j]*(1-a[i]);
  	}
long double ans=0;
for(j=n/2+1;j<=n;j++)
	ans+=dp[n][j];
cout<<fixed<<setprecision(9);
cout<<ans<<endl;
}


Measured memory_bytes: 70272
n,c,*x=`dd`.split.map &:to_i;*s=0
x.map{|e|s<<s[-1]+e}
r=[]
(1..n).map{|k|t=5*s[n]+(k+n)*c;(n-k*2).step(1,-k){|o|t+=2*s[o]};r<<t}
p r.min

Measured memory_bytes: 28036
H, W = map(int, input().split())
C = [list(input()) for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]
for y in range(H):
  for x in range(W):
    check = 0
    if C[y][x] == "#":
      for i in range(4):
        nx = x + X[i]
        ny = y + Y[i]
        if 0 <= nx < W and 0 <= ny < H and C[ny][nx] == "#":
          check = 1
          break
      if check == 0:
        print("No")
        exit()
print("Yes")
      

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

using namespace std;

using ll = long long int;
using vi = vector<int>;
#define f(n) for(int i = 0; i < n; i++)
#define fj(n) for(int j = 0; j < n; j++)
#define fk(n) for(int k = 0; k < n; k++)
#define ci(n) cin >> n;
#define ic(n) int n; cin >> n;
#define lc(n) int n; cin >> n;
#define all(a) a.begin(), a.end()
#define pri(a, n) for(int i = 0; i < n; i++) cout << a[i] << " "; cout << "\n";
#define sc(a, n) int a[n] = {0}; for(int i = 0; i < n; i++) cin >> a[i];
#define scl(a, n) ll a[n] = {0}; for(int i = 0; i < n; i++) cin >> a[i];
#define pb push_back
#define eb emplace_back
#define int long long
const int inf = 2e9, mxp = 10, maxn = 1e6;



void solve(int ci)
{
    ic(n)
    sc(a, n)
    int am[maxn + 1] = {0};
    f(n) am[a[i]]++;
    int d[maxn + 1] = {0};
    for(int i = 1; i <= maxn; i++)
    {
        if(am[i] == 0) continue;
        for(int j = 2 * i; j <= maxn; j += i) d[j] = 1;
        if(am[i] > 1) d[i] = 1;
    }
    int ans = 0;
    for(int i = 1; i <= maxn; i++) if(d[i] == 0) ans += am[i];
    cout << ans;
}

signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    f(t) solve(i + 1);
}


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

int main() {
  int N;
  cin>> N;
  vector<int>vec(N);
  for(int i=0;i<N;i++){
    cin>>vec.at(i);
  }
  
    int p=vec.at(0) ;
  for(int i=0;i<N;i++) { 
   
   if(i==N-1){
     cout<<-1<<endl;}
   else if(p==2){
      cout<<i+1<<endl;
      break;}
   else if(p==1){
      cout<<-1<<endl;
      break;}
    else
    { p=vec.at(p-1);}
     }

}


     
     
    





Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <queue>
#include <tuple>
#include <cstring>

#define INF 100000000

using namespace std;

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    int serch_max = min(a,b);
    int ans = -1;
    int cnt = 0;
    for(int i = serch_max;i>0;i--)
    {
        if(a%i == 0&&b%i == 0)
        {
            cnt++;
            ans = i;
        }
        if(cnt == c)
        {
            cout << ans << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

/*------------------------------------------------------------------*/


int main(){
    ll n, k; cin >> n >> k;
    cout << k * ll(pow(k - 1, n - 1))<< endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int A,B,K;
  cin>>A>>B>>K;
  int count=0;
  for(int i=min(A,B);i>=1;i--){
    if(A%i==0&&B%i==0)count++;
    if(K==count){
      cout<<i<<endl;
      return 0;
    }
  }
  return 0;
}

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

using namespace std;

void color(vector<vector<pair<int, bool>>>& t, vector<int>& a, int i) {
    for (pair<int, bool> p : t[i]) {
        if (a[p.first] == -1) {
            if (p.second) {
                a[p.first] = a[i];
            } else {
                a[p.first] = 1 - a[i];
            }
            color(t, a, p.first);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, bool>>> t(n);
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        t[x - 1].push_back({ y - 1, z % 2 == 0 });
        t[y - 1].push_back({ x - 1, z % 2 == 0 });
    }
    int answer = 0;
    vector<int> a(n, -1);
    for (int i = 0; i < n; ++i) {
        if (a[i] == -1) {
            a[i] = 0;
            color(t, a, i);
            ++answer;
        }
    }
    cout << answer << endl;
}


Measured memory_bytes: 12416
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#define int long long
#define mod(int)(1000000007)
using namespace std;
int test[213456], cnt[213456], ans[213456];
signed main() {
	int n, k, a = 0, b, ans = 0; 
	cin >> n >> k;
	for (int h = 9; h <= 7 * (n - 1); h++) {
		if (h % 7 != 0 && h % 7 != 1) {
			if (h * 9 % 11 == k) {
				ans++;
			}
		}
		if (h % 7 == 0 && h * 9 % 11 == k) { a = h; break; }
	}
	if (a != 0) {
		ans += (7 * n - a) / 77 * 5;
		for (int h = (7 * n - a) / 77 * 77 + a; h <= 7 * (n - 1); h++) {
			if (h % 7 != 0 && h % 7 != 1) {
				if (h * 9 % 11 == k) {
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

 public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        boolean found = false;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='7'){
                found =true;
            }
        }
        if(found) {
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 32508
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INF = 999999999;
const int MOD = (int)1e9 + 7;
const int EPS = 1e-9;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n, x;
  int m;
  int mn = INF;
  cin >> n >>x;
  REP(i,n){
      cin >> m;
      x-=m;
      mn = min(m,mn);
  }
  cout <<  x/mn + n << endl;
}

Measured memory_bytes: 256
//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;
int main(void){
    ll N,M,C;cin>>N>>M>>C;
    vector<ll> B(M);
    REP(i,M)cin>>B[i];
    vector<vi> A(N,vi(M,0));
    WREP(i,N,j,M)cin>>A[i][j];
    ll cnt=0;
    REP(i,N){
        ll sm=0;
        REP(j,M){
            sm+=A[i][j]*B[j];
        }
        if(sm+C>0)cnt++;
    }
    cout<<cnt<<"\n";
}

Measured memory_bytes: 256