akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxh=18;
const int maxn=(1<<maxh)|1;
const int kcz=1000000007;
int h,n,L,p[maxn],sz[maxn],dfn[maxn],clk,tp[maxn],temp[maxn],top,sta[maxn];
ll val[maxn],invval[maxn],ans,cur[maxn],tot[maxn][2];
inline int LCA(int x,int y)
{
    int i;
    for(i=0;(x^y)>>(i+1);i++);
    return (x&y)>>(i+1);
}
inline bool cmp(int x,int y) { return dfn[x]<dfn[y]; }
void solve(int l,int r,int lca)
{
    if(l==r) return;
    int mid=(l+r)>>1,i,t;
    solve(l,mid,lca<<1),solve(mid+1,r,(lca<<1)|1);
    for(i=l;i<=r;i++) temp[i-l]=p[i],tp[p[i]]=i<=mid,cur[p[i]]=val[i]*invval[lca>>/*1*/tp[p[i]]]%kcz*val[p[i]]%kcz;
    // for(i=l;i<=r;i++) printf("%lld ",cur[p[i]]); printf("\n");
    sort(temp,temp+r-l+1);
    t=r-l+1;
    for(i=1;i<=r-l;i++) temp[t++]=LCA(temp[i-1],temp[i]);
    sort(temp,temp+t,cmp);
    // printf("%lld\n",ans); for(i=0;i<t;i++) printf("%d ",temp[i]); printf("\n");
    for(i=0,top=-1;i<t;i++)
    {
        while(top>=0 && (dfn[sta[top]]>dfn[temp[i]] || dfn[sta[top]]+sz[sta[top]]<=dfn[temp[i]]))
        {
            if(top)
            {
                (ans+=(tot[top][0]*tot[top-1][1]+tot[top][1]*tot[top-1][0])%kcz*invval[sta[top-1]>>1]%kcz*invval[sta[top-1]])%=kcz;
                (tot[top-1][0]+=tot[top][0])%=kcz,(tot[top-1][1]+=tot[top][1])%=kcz;
            }
            top--;
        }
        top++;
        sta[top]=temp[i],tot[top][0]=tot[top][1]=0;
        if(L&temp[i]) tot[top][tp[temp[i]]]=cur[temp[i]];
    }
    while(top>0)
    {
        (ans+=(tot[top][0]*tot[top-1][1]+tot[top][1]*tot[top-1][0])%kcz*invval[sta[top-1]>>1]%kcz*invval[sta[top-1]])%=kcz;
        (tot[top-1][0]+=tot[top][0])%=kcz,(tot[top-1][1]+=tot[top][1])%=kcz;
        top--;
    }
}
void dfs(int u)
{
    if(u>=n) return;
    dfn[u]=clk++;
    dfs(u<<1),dfs((u<<1)|1);
}
int main()
{
    int i;
    scanf("%d",&h),L=1<<(h-1),n=1<<h;
    for(i=L;i<n;i++) scanf("%d",&p[i]),p[i]+=L-1;
    for(invval[0]=invval[1]=1,i=2;i<n;i++)
        invval[i]=kcz-(kcz/i)*invval[kcz%i]%kcz;
    for(val[1]=1,i=2;i<n;i++)
        val[i]=i*val[i/2]%kcz,(invval[i]*=invval[i/2]%kcz)%=kcz;
    for(i=1;i<n;i++) sz[i]=0;
    for(i=n-1;i;i--) sz[i]++,sz[i>>1]+=sz[i];
    clk=0,dfs(1);
    // for(i=1;i<n;i++) printf("%d ",dfn[i]); printf("\n");
    ans=0,solve(L,n-1,1);
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 13028
import { count } from 'console';

process.stdin.resume();
process.stdin.setEncoding('utf8');

// 標準入力取込
let gInput = '';
process.stdin.on('data', (chunk) => (gInput += chunk));
process.stdin.on('end', () => main(gInput.split(/\r?\n/)));

// 解答
function main(inputs: string[]): void {
  const [n, m, x] = inputs[0].split(' ').map(Number);

  // 参考書の金額
  let priceList: number[] = [];
  // 各アルゴリズムの理解度
  let textList: number[][] = [];
  // 理解度x以上となる参考書の組み合わせ
  let knowledgeList: number[][] = [];
  // 最小金額
  let result = -1;

  // 入力値より参考書の金額、理解度を設定
  for (let i = 0; i < n; i++) {
    let list = inputs[i + 1].split(' ').map(Number);
    priceList.push(list[0]);
    textList.push(list.slice(1, m + 1));
  }

  // 理解度x以上となる参考書の組み合わせを取得
  for (let i = 0; i < n; i++) {
    let list = getKnowledgeList(i, n, m, x, [i], new Array(m).fill(0), textList);

    if (list.length > 0) {
      if (knowledgeList.length > 0) {
        for (let j = 0; j < list.length; j++) {
          knowledgeList.push(list[j]);
        }
      } else {
        knowledgeList = list;
      }
    }
  }

  // 参考書の金額の最小値を取得
  for (const knowledge of knowledgeList) {
    let sum = 0;
    for (const price of knowledge) {
      sum += priceList[price];
    }
    if (result === -1 || result > sum) {
      result = sum;
    }
  }

  console.log(result);
}

// 理解度x以上となる参考書の組み合わせを取得
function getKnowledgeList(
  j: number,
  n: number,
  m: number,
  x: number,
  list: number[],
  sumList: number[],
  textList: number[][],
): number[][] {
  let knowledgeList: number[][] = [];

  let tempSumList = new Array(m).fill(0);

  for (let i = 0; i < m; i++) {
    tempSumList[i] = sumList[i] + textList[j][i];
  }

  if (checkUnderstand(tempSumList, x)) {
    return [list];
  }

  for (let i = j + 1; i < n; i++) {
    knowledgeList = knowledgeList.concat(
      getKnowledgeList(i, n, m, x, list.concat([i]), tempSumList, textList),
    );
  }
  return knowledgeList;
}

// 理解度x以上を満たすかどうかチェック
function checkUnderstand(numList: number[], x: number): boolean {
  let check = true;

  for (const num of numList) {
    if (num < x) {
      check = false;
      break;
    }
  }

  return check;
}


Measured memory_bytes: 34784
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
using P = pair<int,int>;
const int MOD = 1000000007;

int main() {
    int n,t,a,index;
    double res,ans=100000;
    cin>>n>>t>>a;
    vector<double> h(n);
    rep(i,n) {
        cin>>h[i];
        res=t-h[i]*0.006;
        res=abs(a-res);
        ans=min(ans,res);
        if (res==ans) index=i+1;
    }
    cout<<index<<endl;
}


Measured memory_bytes: 256
import java.util.*;
    public class Main {
     
    	public static void main(String[] args) {
    			
    		Scanner scan =new Scanner(System.in);
    		
    		int a=Integer.parseInt(scan.next());
    		int b=Integer.parseInt(scan.next());
    		int c=Integer.parseInt(scan.next());
    		
    		System.out.print(a+b>=c?"Yes":"No");

;
    		
     
    }
    }
// end 
    

Measured memory_bytes: 23380
#https://atcoder.jp/contests/abc051/tasks/abc051_b

k,s=map(int,input().split())

count=0

for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z<=k:
            #print(x,y,z)
            count+=1

print(count)

Measured memory_bytes: 40684
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		while(true){
			int n=sc.nextInt();
			if(n==0){
				break;
			}
			double[] s=new double[n];
			double ave=0,std=0;
			for(int i=0;i<n;i++){
				s[i]=sc.nextDouble();
				ave+=s[i];
			}
			ave/=n;
			for(int i=0;i<n;i++){
				std+=Math.pow(s[i]-ave,2);
			}
			std=Math.sqrt(std/n);
			System.out.println(std);
		}
	}
}


Measured memory_bytes: 39524
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String a = "A";
		String z = "Z";
		int ans1 = 0;
		int ans2 = 0;
		int flag1 = 0;
		int flag2 = 0;

		sc.close();

		for(int i=0; i<s.length(); i++){
			if(flag1==0){
				if(a.equals(String.valueOf(s.charAt(i)))){
					ans1 = i;
					flag1 = 1;
				}
			}
		}

		for(int i=(s.length()-1); i>=0; i--){
			if(flag2==0){
				if(z.equals(String.valueOf(s.charAt(i)))){
					ans2 = i;
					flag2 = 1;
				}
			}
		}

		System.out.println(ans2-ans1+1);

	}
}

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

int main(){
  int k,s;
  cin >> k >> s;
  int cnt =0;

  for(int i=0; i<=k; i++){
    for(int j=0; j<=k; j++){
      if((s-i-j) <= k && 0 <= s-i-j) cnt++;
    }
  }

  cout << cnt <<endl;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};


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

  ll n,x;
  cin >> n >> x;
  vll a(n);
  REP(i, n)
    cin >> a[i];

  vll dp(2, 0);
  dp[0] = 1;
  REP(i, n){
    if(a[i]%2==0){
      dp[0] *= 2;
      dp[1] *= 2;
    }
    else{
      vll p = dp;
      dp[0] = p[0]+p[1];
      dp[1] = p[0]+p[1];
    }
  }

  cout << dp[x] << endl;

}


Measured memory_bytes: 256
// ref: https://img.atcoder.jp/arc092/editorial.pdf
// ref: https://qiita.com/shihou22/items/2e9522344917c0e39a00

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;
using namespace std;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N; cin >> N;
//    vector<pair<int,int>> vA(N); for(int i=0; i<N; ++i){ cin >> vA[i].first >> vA[i].second; } sort(vA.begin(), vA.end());
    vector<pair<int,int>> vA(N); for(int i=0; i<N; ++i){ cin >> vA[i].second >> vA[i].first; } sort(vA.begin(), vA.end());
    vector<pair<int,int>> vB(N); for(int i=0; i<N; ++i){ cin >> vB[i].first >> vB[i].second; } sort(vB.begin(), vB.end());
    
    int cnt = 0;
    for(int ib=0; ib<N; ++ib){
//        for(int ia=0; ia<N; ++ia){
        for(int ia=N-1; ia>=0; --ia){
//            if(! (vA[ia].first<vB[ib].first && vA[ia].second<vB[ib].second) ){ continue; }
            if(! (vA[ia].second<vB[ib].first && vA[ia].first<vB[ib].second) ){ continue; }
            ++cnt;
            vA[ia].first  = INT_MAX;
            vA[ia].second = INT_MAX;
            break;
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

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

namespace debug
{
    public static partial class Program
    {
        public static void Main()
        {
            long r = Console.ReadLine().ToLong();
            Console.WriteLine(3 * r * r);
        }
    }

    public static partial class Program
    {
        //テンプレここから
        private static long GCD(long aaa, long bbb) => bbb == 0 ? aaa : GCD(bbb, aaa % bbb);
        public static long LCM(long aaa, long bbb) => aaa * bbb / GCD(aaa, bbb);
        public static long ToLong(this double ddd) => (long) ddd;
        public static long ToLong(this string str) => long.Parse(str);
        public static long[] ToLong(this IEnumerable<string> strs) => strs.Select(x => x.ToLong()).ToArray();
        public static long[] ArrayLongs(this string str, char opr = ' ') => str.Split(opr).ToLong();
        public static long Diff(long aaa, long bbb) => Math.Abs(Math.Max(aaa, bbb) - Math.Min(aaa, bbb));
        public static long Sign(this long iii) => Math.Sign(iii);
        public static bool IsEven(this long iii) => iii % 2 == 0;
        public static readonly int[] Dx = {0, -1, 0, 1};
        public static readonly int[] Dy = {-1, 0, 1, 0};
        public const int MOD = 1000000007;
        public const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        public const string alphabet = "abcdefghijklmnopqrstuvwxyz";
        public static long ToLong(this char ccc) => ccc.ToString().ToLong();
        public static string Join(this IEnumerable<string> array, string sep = "") => string.Join(sep, array);
        public static string Join(this IEnumerable<char> array, string sep = "") => string.Join(sep, array);

        public static string JoinToStr(this IEnumerable<long> array, string sep = "")
            => array.Select(xxx => xxx.ToString()).Join(sep);

        //テンプレここまで
    }
}

Measured memory_bytes: 13140
import collections
N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(N))

cnt = 0
for i in c.values():
    a = i
    b = 1
    while a - b >= 0:
        cnt += 1
        a -= b
        b += 1

print(cnt)

Measured memory_bytes: 65676
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[5][105];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=n;j++)
        cin>>dp[i][j];
    for(int i=1;i<=2;i++)
        for(int j=1;j<=n;j++)
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])+dp[i][j];
    cout<<dp[2][n]<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,v;
int p(int a,int b,int c){
	return (char(b)=='+')?(a+c):(a-c);
}
int main(){
	cin>>v;
	
	a=v/1000;
	b=v/100-a*10;
	c=v/10-a*100-b*10;
	d=v%10;
	
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				if(p(p(p(a,i*2+43,b),j*2+43,c),k*2+43,d)==7){
					cout<<a;
					cout<<char(i*2+43);
					cout<<b;
					cout<<char(j*2+43);
					cout<<c;
					cout<<char(k*2+43);
					cout<<d;
					cout<<"=7"<<endl;
					return 0;
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,a[100],b[100],ans[100]={};
	cin>>n>>m;
	for(int i=0;i<m;i++)
		cin>>a[i];
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cin>>b[j];
			if(b[j]==a[i])
				ans[j]++;
			else
				ans[a[i]-1]++;
		}
	}
	for(int i=0;i<n;i++)
		cout<<ans[i]<<endl;
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INT_INF = 2147483647;
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; }

int main(){
  string s;
  cin >> s;
  int n = s.size();
  stack<char> q;
  rep(i,n){
    if(q.size()==0){
      q.push(s[i]);
      continue;
    }
    if(s[i]=='S')q.push('S');
    else{
      if(q.top()=='S')q.pop();
      else q.push('T');
    }
  }
  cout << q.size() << endl;
  return 0;
}


Measured memory_bytes: 644
/*#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;*/
#include<stdio.h>
#include<stdlib.h>

#define MAX 2000001
#define VMAX 10000

int main()
{
    unsigned short *A,*B;
    int C[VMAX+1];
    int n,i;
    //cin>>n;
    scanf("%d",&n);

    A=(unsigned short *)malloc(sizeof(unsigned short)*n+1);
    B=(unsigned short *)malloc(sizeof(unsigned short)*n+1);
  // A=malloc(sizeof(short) * n+1);
   // B=malloc(sizeof(short) * n+1);

    for(i=0;i<VMAX;i++)
        C[i]=0;

    for(i=0;i<n;i++)
    {
       // cin>>A[i+1];
       scanf("%hu",&A[i+1]);
        C[A[i+1]]++;
    }

    for(i=1;i<=VMAX;i++)C[i]=C[i]+C[i-1];

    for(i=1;i<=n;i++)
    {
        B[C[A[i]]]=A[i];
        C[A[i]]--;
    }

    for(i=1;i<=n;i++)
    {
        if(i>1) printf(" ");// cout<<" ";
        //cout<<B[i];
        printf("%d",B[i]);
    }
    //cout<<endl;
    printf("\n");
    return 0;
}

Measured memory_bytes: 10532
#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define rep(i,n) for(int i=0;i<n;i++)
constexpr int INF = numeric_limits<int>::max()/2;
constexpr long long LINF = numeric_limits<long long>::max()/3;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
template<typename T> ostream& operator<<(ostream& os,const set<T>& st){ os<<"{"; for(T v:st) os<<v<<","; os <<"}"; return os; }
template<typename T,typename U> inline void chmax(T &x,U y){ if(y>x) x = y; }
template<typename T,typename U> inline void chmin(T &x,U y){ if(y<x) x = y; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
//constexpr double eps = 1e-14; 
constexpr double eps = 1e-10; 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

bool isp(int n){
    if(n == 2) return false;
    for(int i=2;i*i<=n;i++){
        if(n%i == 0) return true;
    }
    return false;
}

void solve(int n){
    int l,u;
    l = n-1;
    u = n+1;

    if(!isp(n)){
        cout << 0 << endl;
        return;
    }

    while(isp(u)) u++;
    while(isp(l)) l--;
    cout << u - l << endl;
}

int main(){
    int n;
    while(1){
        cin >> n;
        if(!n) break;
        solve(n);
    }
}

Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  int A, B, C, D;
  cin >> N;
  A = N / 1000;
  B = (N - A * 1000) / 100;
  C = (N - A * 1000 - B * 100) / 10;
  D = (N - A * 1000 - B * 100 - C * 10) / 1;
  if (A == B && B== C && C== D) {
	cout << "Yes" << endl;
    }
  else if ((A == B && B == C) || (B == C && C == D)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

int main(void){
  char a[10],b[5];
  int x;
  int i;
  scanf("%s %s",a,b);
  strcat(a,b);
  x=atoi(a);
  for(i=0;i<x/2;i++){
    if (i*i==x) {
      puts("Yes");
      return 0;
    }
  }
  puts("No");
  return 0;
}


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

bool check(vector<long> a, int c, long k){
  long tmp=0;
  for(int i=0;i<a.size();i++){
    if(a[i]<=c)continue;
    tmp+= a[i]/c;
    if(a[i]%c==0)tmp--;
    // cout << tmp << endl;
  }
  if(tmp<=k) return true;
  else  return false;
}

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

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

  int l=0;
  int r=1000000000;
  while(r-l>1){
    int c = (l+r)/2;
    if(check(a,c,k)){
      // cout << c << " yes" << endl;
      r=c;
    } else {
      // cout << c << " no" << endl;
      l=c;
    }
  }

  cout << r << endl;
  return 0;
}


Measured memory_bytes: 6316
Case_num = 1
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    List = [[0] * (W + 1)] * (N + 1) #????????? w??\????????°n??\?????§??????????????????????????§
    for i in range(1,N + 1):
        v,w = map(int,input().split(","))
        for j in range(W,w - 1,-1):
            List[i][j] = max(List[i - 1][j] ,List[i - 1][j - w] + v)
    print("Case",Case_num,end = ":\n")
    print(List[N][W])
    print(List[N].index(List[N][W]))
    Case_num += 1

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

// why am I so weak

const int MOD = 1e9 + 7;

int n;
int a[100055];
map<int, int> c;

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

	int zero = 0;

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

		if (a[i] == 0) zero++;
		c[a[i]]++;
	}

	int cur;

	if (n & 1) {
		if (zero != 1) {
			puts("0");
			return 0;
		}

		cur = 2;
	} else {
		if (zero != 0) {
			puts("0");
			return 0;
		}

		cur = 1;
	}

	for ( ; cur <= n - 1; cur += 2) {
		if (c[cur] != 2) {
			puts("0");
			return 0;
		}	
	}

	int res = 1;

	for (int i = 0; i < n / 2; i++) res = (res << 1) % MOD;

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

	return 0;
}


Measured memory_bytes: 3584
n,k=map(int,input().split())
*s,=input()
g=[]
t=1
for i in range(1,n):
    if s[i]==s[i-1]:
        t+=1
    else:
        g.append(t)
        t=1
g.append(t)
for i in range(1,len(g)):
    g[i]+=g[i-1]
g=[0]+g+[g[-1]]
a=0
for i in range(s[0]=='1',len(g),2):
    a=max(a,g[i]-g[max(0,i-2*k-1)])
print(a)

Measured memory_bytes: 54480
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
    char s[105];
    while(~scanf("%s",s))
    {
         int i=strlen(s);
         if(i<3&&i>100)continue;
         cout<<s[0]<<i-2<<s[i-1]<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>

using namespace std;

#define sz			size()
#define lgt			length()
#define rep(i,n)	for (int i = 0; i < n; i++)
#define ALL(X)		(X).begin(),(X).end()
#define RALL(X)		(X).rbegin(),(X).rend()
#define pb			push_back
#define SORT(a)		sort(ALL(a));
#define RSORT(a)	sort(RALL(a));
#define mp			make_pair
#define dump(x)		cerr<<#x<<" = "<<(x)<<endl;
#define fir			first
#define sec			second

typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<string> vs;

int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
vs form(string a,char s){vs v;string b;rep(i,a.lgt){if(a[i]==s){v.pb(b);b="";}else b+=a[i];}v.pb(b);return v;}
vi formint(string a,char s){vi v;string b;rep(i,a.lgt){if(a[i]==s){v.pb(toInt(b));b="";}else b+=a[i];}v.pb(toInt(b));return v;}

const double EPS=1e-10,PI=acos(-1.0);
const int INF=2100000000;

int dp[128][4][4];
int s[128];

int main(void)
{
	rep(i,128){
		s[i]=-1;
		rep(j,4)rep(k,4)dp[i][j][k]=0;
	}
	int n,k,a,b;
	cin>>n>>k;
	rep(i,k){
		cin>>a>>b;
		s[a]=b-1;
	}
	
	for(int i=1;i<=n;i++){
		if(i==1){
			rep(j,3){
				if(s[i]!=-1&&s[i]!=j)continue;
				dp[1][j][0]=1;
			}
		}
		else if(i==2){
			rep(j,3){
				if(s[i]!=-1&&s[i]!=j)continue;
				rep(k,3)dp[2][j][k]+=dp[1][k][0];
			}
		}
		else
		rep(j,3){
			if(s[i]!=-1&&s[i]!=j)continue;
			rep(k,3){
				rep(m,3)dp[i][j][k]+=dp[i-1][k][m];
				if(j==k)dp[i][j][k]-=dp[i-1][j][k];
				dp[i][j][k]%=10000;
			}
		}
	}
	
	int res=0;
	rep(i,9)res+=dp[n][i/3][i%3];
	cout<<res%10000<<endl;
	//rep(j,9){for(int i=1;i<=n;i++)cout<<dp[i][j/3][j%3]<<" ";cout<<endl;}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>

int main(){
    int H, W;
    std::cin >> H >> W;
    int arr[H][W], dp[H][W];
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            char c;
            std::cin >> c;
            arr[i][j] = c == '#';
        }
    }
    dp[0][0] = arr[0][0];
    for (int i = 1; i < H; ++i) {
        dp[i][0] = dp[i-1][0] + (arr[i][0]==1&&arr[i-1][0]==0);
    }
    for (int i = 1; i < W; ++i) {
        dp[0][i] = dp[0][i-1] + (arr[0][i]==1&&arr[0][i-1]==0);
    }
    for (int i = 1; i < H; ++i) {
        for (int j = 1; j < W; ++j) {
            dp[i][j] = std::min(
                    dp[i-1][j] + (arr[i][j]==1&&arr[i-1][j]==0),
                    dp[i][j-1] + (arr[i][j]==1&&arr[i][j-1]==0)
                    );
        }
    }
    std::cout << dp[H-1][W-1];
}

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

    long N, K;

    cin >> N;
    cin >> K;

    // vector<long long> p(N);
    long p;
    vector<long long> sum_list(N+1);
    sum_list[0] = 0;

    for(long i=0; i<N; i++){
        cin >> p;
        sum_list[i+1] += p + sum_list[i]; 
    }

    long long ans = 0;
    long long exp = 0;

    for(long i=0;i < (N-K+1); i++){
        exp = sum_list[i+K] - sum_list[i] + K;
        if(exp > ans){
            ans = exp;
        }
    }

    cout << setprecision(10) << (double)ans / 2.0 << endl;

    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull B=100000007;

vector<int> contain(string a,string b){
  int al=a.size(),bl=b.size();
  vector<int> ans;
  if(al>bl)return ans;
  
  ull t=1;
  for(int i=0;i<al;i++)t*=B;

  int ah=0,bh=0;
  for(int i=0;i<al;i++)ah=ah*B+a[i];
  for(int i=0;i<al;i++)bh=bh*B+b[i];

  for(int i=0;i+al<=bl;i++){
    if(ah==bh)ans.push_back(i);
    if(i+al<bl)bh=bh*B+b[i+al]-b[i]*t;
  }
  return ans;
}

int main(){
  string t,p;
  cin>>t>>p;
  vector<int> ans=contain(p,t);
  for(int i=0;i<ans.size();i++)printf("%d\n",ans[i]);
  return 0;
}



Measured memory_bytes: 9456
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef long double ld;
typedef unsigned long long ull;
#define X first
#define Y second
#define mp make_pair
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class X> using indexed_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int M = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int modpow(int n, int k, int MOD);

/**************** code starts here ****************/

struct DSU {
	vector<int> P, S;
	DSU(int n) {
		P.resize(n+1);
		S.resize(n+1, 1);
		for (int i = 1; i <= n; i++) P[i] = i;
	}
	
	int find(int x) {
		while (x != P[x]) x = P[x];
		return x;
	}
	
	void merge(int a, int b) {
		a = find(a); b = find(b);
		if (S[a] < S[b]) swap(a, b);
		
		S[a] += S[b];
		P[b] = a;
	}
	
	int same(int a, int b) {
		return find(a) == find(b);
	}
} D(100001);

int n, m; 
vector<pair<int, int>> a(100001);
vector<int> v(100001);
vector<int> taken(100001);

void poppingfever() {
	cin >> n >> m;
	if (n < 2*(n - m - 1)) {cout << "Impossible"; return;}

	for (int i = 0; i < n; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		D.merge(x, y);
	}
	sort(a.begin(), a.begin() + n);

	int k = 2*(n - m - 1);
	int ans = 0;

	for (int i = 0; i < n; i++) {
		if (k == 0) break;
		int u, w;
		tie(w, u) = a[i];

		if (v[D.find(u)] == 0) {
			v[D.find(u)] = 1;
			taken[u] = 1;

			ans += w;
			k--; 
		}
	}

	for (int i = 0; i < n; i++) {
		int u, w;
		tie(w, u) = a[i];

		if (k == 0) break;
		if (taken[u] == 0) {
			taken[u] = 1;
			k--;
			ans += w;
		}
	}

	cout << ans;
}

/**************************************************/

signed main() {
	#ifdef fastfurioustransform
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
 
	//ios::sync_with_stdio(0); cin.tie(0);
	//cout << fixed << setprecision(12);
 
	poppingfever();
 
	return 0;
}

int modpow(int n, int k, int MOD) {
	int ans = 1; n %= MOD;
	while (k > 0) {
		if (k & 1) ans = (ans*n) % MOD;
		k >>= 1; n = (n*n) % MOD;
	}
	return ans;
}

Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#define rep(i, n) for(int i=0; i<n; i++)
using namespace std;

int main(){
  long long H;
  cin >> H;

  long long count = 0;

  while(H != 0){
    H /= 2;
    count++;
  }

  cout << (long long)pow(2, count)-1 << endl;

  return 0;
}


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

int N;
string S;

int main(){
    cin>>N>>S;

    if(N%2==1){
        cout<<"No"<<endl;
    }else{
        for(int i=0;i<N/2;i++){
            if(S[i]!=S[i+N/2]){
                cout<<"No"<<endl;
                return 0;
            }
        }
        cout<<"Yes"<<endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP2(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(v) (v).begin(),(v).end()
#define INF 2e9
typedef long long ll;

int main()
{
  int n;
  cin>>n;
  map<int,int> cnt1,cnt2;
  REP(i,n/2){
    int v1,v2;
    cin>>v1>>v2;
    cnt1[v1]++;
    cnt2[v2]++;
  }

  vector<pair<int,int>> cnt1v,cnt2v;
  for(auto e:cnt1) cnt1v.emplace_back(make_pair(e.second,e.first));
  for(auto e:cnt2) cnt2v.emplace_back(make_pair(e.second,e.first));
  sort(ALL(cnt1v),greater<pair<int,int>>());
  sort(ALL(cnt2v),greater<pair<int,int>>());
  if(cnt1v[0].second==cnt2v[0].second){
    cout<<n-max(cnt1v[0].first+cnt2v[1].first,cnt1v[1].first+cnt2v[0].first)<<endl;
  }else{
    cout<<n-cnt1v[0].first-cnt2v[0].first<<endl;
  }

	return 0;
}

Measured memory_bytes: 6136
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Main {
	private static final int X = 0;
	private static final int Y = 1;
	
	public static void main(String[] args) {
		ArrayList<String> result = new ArrayList<String>();
		ArrayList<Double> a = new ArrayList<Double>();
		ArrayList<Double> b = new ArrayList<Double>();
		ArrayList<Double> c = new ArrayList<Double>();
		ArrayList<Double> d = new ArrayList<Double>();
		Scanner sc = new Scanner(System.in);
		
		try{
			while(true){
				String input = sc.nextLine();
				String[] data = input.split(",");

				a.add(Double.valueOf(data[0]));
				a.add(Double.valueOf(data[1]));
				b.add(Double.valueOf(data[2]));
				b.add(Double.valueOf(data[3]));
				c.add(Double.valueOf(data[4]));
				c.add(Double.valueOf(data[5]));
				d.add(Double.valueOf(data[6]));
				d.add(Double.valueOf(data[7]));
				
				if(areCross(a, b, c, d)){
					result.add("YES");
				}
				else{
					result.add("NO");
				}
				
				a.clear();
				b.clear();
				c.clear();
				d.clear();
			}
		}catch(NoSuchElementException e){
			//何もしない
		}
		
		for(int i = 0; i < result.size(); i++){
			System.out.println(result.get(i));
		}
	}
	
	public static boolean areCross(
			ArrayList<Double> p1,
			ArrayList<Double> p2,
			ArrayList<Double> p3,
			ArrayList<Double> p4){
		boolean a = false;
		boolean b = false;
		//p1p3とp2,p4
		if(isInBiggerArea(p1, p3, p2) && !(isInBiggerArea(p1, p3, p4))){
			a = true;
		}
		if(!(isInBiggerArea(p1, p3, p2)) && isInBiggerArea(p1, p3, p4)){
			a =  true;
		}

		//p2p4とp1
		if(isInBiggerArea(p2, p4, p1) && !(isInBiggerArea(p2, p4, p3))){
			b = true;
		}
		if(!(isInBiggerArea(p2, p4, p1)) && isInBiggerArea(p2, p4, p3)){
			b = true;
		}
		if(a && b){
			return true;
		}
		else{
			return false;
		}
	}
	
	private static boolean isInBiggerArea(
			ArrayList<Double> p1,
			ArrayList<Double> p2,
			ArrayList<Double> target){
			double result = (target.get(Y) - p1.get(Y)) * (p2.get(X) - p1.get(X)) + (p2.get(Y) - p1.get(Y)) * (p1.get(X) - target.get(X));
			if(result > 0){
				return true;
			}
			else{
				return false;
			}
	}
}

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

int main (){
   string s;
   cin >> s;
   int x;
   x=s.length();
   
   rep(i,x){
       cout << "x";
   }
    return 0;
}


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

using Int = long long int;
using UInt = unsigned long;

int main (void) {
    char c;

    cin >> c ;

    if (c == 'a') {
        cout << "vowel" << endl;
    }else if (c == 'e') {
        cout << "vowel" << endl;
    }else if (c == 'i') {
        cout << "vowel" << endl;
    }else if (c == 'o') {
        cout << "vowel" << endl;
    }else if (c == 'u') {
        cout << "vowel" << endl;
    }else{
        cout << "consonant" << endl;
    }

    return 0;
    
}

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

using namespace std;

int main() {
	int n;
	map <string, int> verdict;

	verdict["AC"] = 0;
	verdict["WA"] = 0;
	verdict["TLE"] = 0;
	verdict["RE"] = 0;

	cin >> n;

	for (int i = 0; i < n; i++) {
		string s;

		cin >> s;
		verdict[s]++;
	}

	cout << "AC" << " x " << verdict["AC"] << "\n";
	cout << "WA" << " x " << verdict["WA"] << "\n";
	cout << "TLE"<< " x " << verdict["TLE"] << "\n";
	cout << "RE" << " x " << verdict["RE"] << "\n";

	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 INF=1001001001;
vector<pair<int64_t,int64_t>>pppp(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
 
int main() {
 int N;
 cin>>N;
 int A=N/1000;
 int B=N/100%10;
 int C=N/10%10;
 int D=N%10;
 char a,b,c;
 for(int i=0;i<=1;i++){ 
   for(int j=0;j<=1;j++){
     for(int k=0;k<=1;k++){
       int sum=A;
       if(i==1){a='+';sum+=B;}
       if(i==0){a='-';sum-=B;}
       if(j==1){b='+';sum+=C;}
       if(j==0){b='-';sum-=C;}
       if(k==1){c='+';sum+=D;}
       if(k==0){c='-';sum-=D;}
       if(sum==7){cout<<A<<a<<B<<b<<C<<c<<D<<"=7"<<endl;return 0;}
     }
   }
 }
 
 return 0;
}

Measured memory_bytes: 3616
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = I()
print(x[K-1])

Measured memory_bytes: 38256
def fun(d):
	cnt = 0
	for i in d:
		cnt+= i*d[i]
	return cnt

from collections import defaultdict
d = defaultdict(int)
n = int(input())
A = list(map(int,input().split()))
for i in range(n):
	d[A[i]]+=1
q = int(input())
cnt = sum(A)
for i in range(q):
	b,c = map(int,input().split())
	if b in d:
		cnt+=(-b*d[b] + c*d[b])
		d[c]+=d[b]
		d[b]=0
		#print(cnt,d)
	print(cnt)



Measured memory_bytes: 21452
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

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

    set<char> s_set, t_set;
    for(auto c: s) s_set.insert(c);
    for(auto c: t) t_set.insert(c);

    map<char, vector<int>> c2idx;
    for(int i=0; i < s.length(); i++) {
        c2idx[s[i]].push_back(i);
    }

    for(auto c: t_set) {
        if (c2idx[c].size() == 0) {
            cout << -1 << endl;
            return 0;
        }
    }

    int t_length = t.length();
    int s_length = s.length();
    int s_idx = -1;
    int t_idx = 0;
    ll w = 0;

    for(int t_idx = 0; t_idx < t_length; t_idx++) {

        s_idx += 1;
        auto lb_itr = lower_bound(c2idx[t[t_idx]].begin(), c2idx[t[t_idx]].end(), s_idx);
        if(lb_itr == c2idx[t[t_idx]].end()) {
            s_idx = c2idx[t[t_idx]][0];
            w += ll(1);
        } else {
            s_idx = *lb_itr;
        }
    }

    ll ans = ll(s_length) * w + ll(s_idx + 1);
    cout << ans << endl;

    return 0;
}

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

int main() {
  int N;
  cin>>N;
  vector<int64_t> a(N+1);
for (int i=0;i<=N;i++) {
  cin>>a.at(i);
}
  vector<int64_t> b(N);
for (int i=0;i<N;i++) {
  cin>>b.at(i);
}
  int64_t Z=0;
  for(int i=0;i<N;i++){
    if(a.at(i)>=b.at(i)){
      Z+=b.at(i);
    }
    else if(a.at(i)+a.at(i+1)<=b.at(i)){
      Z+=a.at(i)+a.at(i+1);
      a.at(i+1)=0;
    }
    else{
      Z+=b.at(i);
      a.at(i+1)=a.at(i)+a.at(i+1)-b.at(i);
    }
  }
  cout<<Z<<endl;
  
}

Measured memory_bytes: 1792
import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)

    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(key=lambda t: t[0])
idx = compress([xy_i[1] for xy_i in xy])
lbit = BIT(N)
rbit = BIT(N)

for i in range(N):
    rbit.add(i, 1)
    
ans = 0
MOD = 998244353

for i in range(N):
    y = xy[i][1]
    rbit.add(idx[y], -1)
    a = i-lbit.acc(idx[y])
    b = lbit.acc(idx[y])
    c = rbit.acc(idx[y])
    d = N-1-i-rbit.acc(idx[y])
    add = 2*pow(2, N-1, MOD)-1
    add = (add-(pow(2, a, MOD)-1))%MOD
    add = (add-(pow(2, b, MOD)-1))%MOD
    add = (add-(pow(2, c, MOD)-1))%MOD
    add = (add-(pow(2, d, MOD)-1))%MOD
    add = (add-(pow(2, a+b, MOD)-pow(2, a, MOD)-pow(2, b, MOD)+1))%MOD
    add = (add-(pow(2, b+c, MOD)-pow(2, b, MOD)-pow(2, c, MOD)+1))%MOD
    add = (add-(pow(2, c+d, MOD)-pow(2, c, MOD)-pow(2, d, MOD)+1))%MOD
    add = (add-(pow(2, d+a, MOD)-pow(2, d, MOD)-pow(2, a, MOD)+1))%MOD
    ans += add
    ans %= MOD
    lbit.add(idx[y], 1)

print(ans)

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

    string A, B, C;
    cin >> A >> B >> C;

    int ans = 0;

    for (int i = 0; i < N; i++){
        if (A.substr(i, 1) == B.substr(i, 1) && B.substr(i, 1) != C.substr(i, 1)){
            ans++;
        }
        else if (B.substr(i, 1) == C.substr(i, 1) && A.substr(i, 1) != B.substr(i, 1)){
            ans++;
        }
        else if (A.substr(i, 1) == C.substr(i, 1) && A.substr(i, 1) != B.substr(i, 1)){
            ans++;
        }
        else if (A.substr(i, 1) != B.substr(i, 1) && B.substr(i, 1) != C.substr(i, 1) && A.substr(i, 1) != C.substr(i, 1)){
            ans += 2;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin >> n;
    int ac=0,tle=0,re=0,wa=0;
    for(int i=0;i<n;i++)
    {
        string temp; cin >> temp;
        if(temp=="AC") ac++;
        else if(temp=="TLE") tle++;
        else if(temp=="WA") wa++;
        else if(temp=="RE") re++;
    }
    printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n",ac,wa,tle,re);
    return 0;
}



Measured memory_bytes: 3720
# coding: utf-8

def get_kouyaku(a:int, b:int):
    if a % b == 0:
        return b
    return get_kouyaku(b, a % b)


monster_count = int(input())
monsters = [int(i) for i in input().rstrip().split(" ")]

ans = monsters[0]
for i in range(1, monster_count):
    ans = get_kouyaku(ans, monsters[i])

print(ans)

Measured memory_bytes: 14224
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 100000000
#define INF 1000000000000000000
#define MOD 1000000007
#define mod 1000000007
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //-------------------------------
    set<ll>s;
    ll q;cin>>q;
    while(q--){
        ll a,x;cin>>a>>x;
        if(a==0){
            s.insert(x);
            cout<<s.size()<<endl;
        }
        else if(a==1){
            cout<<s.count(x)<<endl;
        }
        else if(a==2){
                s.erase(x);
        }
        else{
            ll l=x;
            ll r;cin>>r;
            auto left=s.lower_bound(l);
            auto right=s.upper_bound(r);
            for(auto it=left;it!=right;it++){
                cout<<*it<<endl;
            }
        }
    }
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------





































Measured memory_bytes: 12408
# AtCoder Beginner Contest 165: C (2020/05/02)
import itertools
N, M, Q = map(int, input().split())
ans = 0
a = [0 for i in range(Q)]
b = [0 for i in range(Q)]
c = [0 for i in range(Q)]
d = [0 for i in range(Q)]
for j in range(Q):
    a[j], b[j], c[j], d[j] = map(int, input().split())
seq = [i+1 for i in range(M)]
As = list(itertools.combinations_with_replacement(seq, N))
ans = 0
for j in range(len(As)):
    A = As[j]
    max = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            max = max + d[i]
    if ans < max:
        ans = max
print(ans)

Measured memory_bytes: 21552
#include <bits/stdc++.h>
using namespace std;
const double pi=2*acos(0.0);
double inff=1.0/0.0;
#define ll           long long int
#define inf          1000000000LL
#define MOD          1000000007
#define pb           push_back
#define sz(x)        (int)x.size()
#define mp           make_pair
#define lbd          lower_bound
#define ubd          upper_bound
#define ipair        pair<ll,ll> 
#define all(v)       v.begin(),v.end()
#define watch(x)     cout<<(#x)<<" is "<<(x)<<endl;
#define rep(a,b,c)   for(a=(int)b;a<(int)c;a++)
#define rep2(a,b,c)  for(a=(int)b;a<(int)c;a+=2)  
#define bac(a,b,c)   for(a=(int)b;a>=(int)c;a--)
#define se           second
#define f            first
#define ios          ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
#define mem(a,val)   memset(a,val,sizeof a)
#define endl         "\n"
#define mxn          200005
#define vi           vector<ll>
#define vii          vector<ipair> 
#define si           set<ll> 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
/*Variables Start*/
ll x,y,n,i,z,j,k,w,u,q,m,t;
double dp[3001][3001];double p[3001];
/*Variables End*/
void solve()
{
  cin>>n;
  rep(i,1,n+1) cin>>p[i];
  dp[0][0]=1;
  rep(i,1,n+1)
  {
    rep(j,0,i)
    {
      dp[j][i]+=dp[j][i-1]*(1-p[i]);
      dp[j+1][i]+=dp[j][i-1]*p[i];
    }
  }
  double w=0;
  rep(i,n/2+1,n+1)
  {
    w+=dp[i][n];
  }
  cout<<setprecision(10)<<fixed;
  cout<<w<<endl;
}
int main() 
{ 
  int TESTS=1;
  ios;
  while(TESTS--)
  {
    solve();
  }  
}

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

def main():
    N = int(input())
    S = input().strip()

    Prev = '_'
    Ans = 0
    for Si in S:
        if Si != Prev:
            Ans += 1
        Prev = Si
    print(Ans)


if __name__ == "__main__":
    main()


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

typedef long long ll;
#define rep(i,x) for(int i=0;i<x;i++)
#define put(ans)    cout << ans << endl;

double kaijyo(int n){
    int k(1);
    for(int i=n;i>0;i--){
        k *= i;
    }

    return k;
}

double distance(int x[],int y[],int i,int j){
    int dx = (x[i] - x[j]) * (x[i] - x[j]);
    int dy = (y[i] - y[j]) * (y[i] - y[j]);
    return sqrt(dx+dy);
}

int main(){
    ll a,b,c;
    cin >> a >> b >> c;

    ll less_side(min({a*b,b*c,c*a}));


    ll another_side(0);
    if(less_side==a*b){
        another_side = c;
    }else if(less_side==b*c){
        another_side = a;
    }else{
        another_side = b;
    }

    if(another_side%2==0){
        cout << 0 << endl;
    }else{
        cout << less_side << endl;
    }

    return 0;
}

Measured memory_bytes: 3620
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn vec<T, F: FnMut(usize) -> T>(n: usize, mut f: F) -> Vec<T> {
    (0..n).map(|i| f(i)).collect()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    let a: Vec<usize> = vec(n, |_| scan(tokens));
    let b: Vec<usize> = vec(n, |_| scan(tokens));
    let c: Vec<usize> = vec(n - 1, |_| scan(tokens));
    let mut ans: usize = b.iter().sum();
    for i in 0..n - 1 {
        if a[i] + 1 == a[i + 1] {
            ans += c[a[i] - 1];
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
require 'set'
def bfs(start_node)
    return 0 if start_node.is_goal?
    reached = Set[start_node]
    dist = 1
    queue = [start_node]
    until queue.empty?
        next_queue = Set.new
        until queue.empty?
            node = queue.shift
            node.next_nodes.each do |next_node|
                return dist if next_node.is_goal?
                next if reached.include?(next_node)
                reached << next_node
                next_queue << next_node
            end
        end
        dist += 1
        queue = next_queue.to_a
    end
    return nil
end

class Array
    def is_goal?
        self[0] == self[2] && self[1] == self[3]
    end

    def next_nodes
        a = []
        [[1, 0], [-1, 0], [0, 1], [0, -1]].each do |dx, dy|
            x1, y1 = self[0..1]
            if $field[y1+dy][x1+dx] == 0
                x1 += dx
                y1 += dy
            end
            x2, y2 = self[2..3]
            if $field[y2-dy][x2-dx] == 0
                x2 -= dx
                y2 -= dy
            end
            a << [x1, y1, x2, y2]
        end
        return a
    end
end

loop do
    w, h = gets.split.map(&:to_i)
    break if w == 0
    x1, y1 = gets.split.map(&:to_i)
    x2, y2 = gets.split.map(&:to_i)

    $field = (1..h).map { gets.split.map(&:to_i) }
    $field = [Array.new(w, 1)] + $field + [Array.new(w, 1)]
    $field.map! {|r| [1] + r + [1]}

    puts bfs([x1, y1, x2, y2]) || 'NA'
end



Measured memory_bytes: 38704