akhauriyash/Code-Regression huggingface dataset:
#pragma gcc optimize("Ofast")

#include "bits/stdc++.h"
using namespace std;
typedef int64_t lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef pair<int,pll> pip;
typedef pair<pll,int> ppi;
typedef pair<lld,pll> plp;
typedef pair<pll,lld> ppl;
typedef pair<pll,pll> ppp;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define jizz cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
inline void input(int &_x) {
    _x = 0;
    int _tmp = 1; char _tc = getchar();
    while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
    if(_tc == '-') _tc = getchar(), _tmp = -1;
    while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar();
    _x *= _tmp;
}
inline void output(int _x) {
    char _buff[20]; int _f = 0;
    if(_x == 0)putchar('0');
    while(_x > 0)
    {
        _buff[_f++] = _x%10+'0';
        _x /= 10;
    }
    for(_f-=1; _f >= 0; _f--)
        putchar(_buff[_f]);
    putchar('\n');
}
template<typename Iter>
ostream& _out(ostream &s, Iter b, Iter e) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}
template<class T1,class T2>
ostream& operator<<(ostream& out, pair<T1,T2> p) {
    return out << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) {
     return _out(s,c.begin(),c.end());
 }
#ifdef erd1
    #define pprint(x) cerr<<__PRETTY_FUNCTION__<<":"<<__LINE__<<" - "<<(#x)<<"="<<(x)<<endl
#else
    #define pprint(x)
#endif

// code starts here
vector<vector<bool>> G;
vector<bool> colo, cola;
vector<int> row;
signed main(){
    int n, cnt = 0;
    cin >> n;
    G.resize(n); colo.resize(n); cola.resize(n, 1); row.resize(n);
    for(auto& i: G)i.resize(n);
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < n; j++){
            ;
            if(G[i][j] = s[j] == '.'){
                row[i]++;
                colo[j] = 1;
            }else{
                cnt++;
                cola[j] = 0;
            }
        }
    }
    if(!cnt)return cout << -1 << endl, 0;
    int ans = INT_MAX;
    for(int i = 0; i < n; i++)
        ans = min(ans, row[i] + cola[i]);
    for(int i = 0; i < n; i++)ans += colo[i];
    cout << ans << endl;

}


Measured memory_bytes: 256
# 169A

#1.入力をちゃんと受け取ること
#ex：｢2 5」⇒ a = 2,  b = 5　みたいにしないといけない。
a, b = map(int, input().split())
#print(a)
#print(b)

#2.目的通りの計算をする
#ex：２つの整数ＡとＢの掛け算をやる
answer = a * b

#3.計算の結果を出力する
print(answer)

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

typedef long long ll;
ll x;

int main(void){
    // Your code here!
    cin >> x;
    
   
    
    ll quotient = x / 11;
    ll mod = x % 11;
    
    ll ans = 2 * quotient;
    if (0 < mod && mod <= 6) ans += 1;
    if (6 <  mod) ans += 2;
    cout << ans  << endl;
}


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

using namespace std;
using ll = long long;

template <typename K,typename V>
using umap = unordered_map<K,V>;
template <typename V>
using uset = unordered_set<V>;
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; }
#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(v) v.begin(),v.end()

#define INF 1'000'000'000'000 //10^12
#define MOD 1'000'000'007


ll gcd(ll a,ll b){
    if(b == 0){
        return a;
    }else{
        return gcd(b,a%b);
    }
}

int main(){

    int n;

    cin >> n;

    vector<vector<int>> alpha(n,vector<int>(26,0));

    string s[n];

    REP(i,n){
       cin >> s[i];
    }

    REP(i,n){
        REP(j,s[i].length()){
            

            alpha[i][s[i][j]-'a']++;
        }
    }

    vector<int> min_count(26,1000);

    REP(i,n){
        REP(j,26){
            min_count[j] = min(min_count[j],alpha[i][j]);
        }
    }

    string res = "";

    REP(i,26){
        REP(j,min_count[i]){
            res += (char)('a'+i);
        }
    }

    cout << res <<endl;

    return 0;
}


Measured memory_bytes: 3600
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define rep(i,n) for(int i=0;i<n;i++)
int gcd(int a, int b){
    int r=1;
    while(r!=0){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
typedef long long ll;
void revStr(char* str){
    int size = strlen(str);
    int i,j;
    char tmp = {0};
    for(i = 0, j = size - 1; i < size / 2; i++, j--){
        tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }return;
}
typedef struct{
    char name[20];
    int vl;
}data;

//昇順
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}


int kai(int n){
    if(n==0){
        return 1;
    }
    int sum=1;
    for(int i=1;i<=n;i++){
        sum*=i;
    }
    return sum;
}

int main(){
    char a[200002],b[200002];
    scanf("%s",a);
    scanf("%s",b);
    int cnt=0;
    int i=0;
    while(a[i]!=0){
        if(a[i]!=b[i]){
            cnt++;
        }else{
            ;
        }
        i++;
    }
    printf("%d",cnt);
}


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

int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    vector<int> order(N);
    for (int i = 0; i < N; i++) {
        order[A[i]-1] = i+1;
    }

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

Measured memory_bytes: 1536
def gcd(num1,num2):
    if num2==0:
        return num1
    return gcd(num2,num1%num2)
from collections import deque
n=int(input())
a=[int(i) for i in input().split()]
left_gcd=a[0]
right_gcd=a[-1]
left=deque([])
right=deque([])
for i in a:
    left_gcd=gcd(left_gcd,i)
    left.append(left_gcd)
for i in a[::-1]:
    right_gcd=gcd(right_gcd,i)
    right.append(right_gcd)
right=deque(reversed(right))
Max=max(right[1],left[-2])
for i in range(1,n-1):
    Max=max(Max,gcd(left[i-1],right[i+1]))
print(Max)

Measured memory_bytes: 14440
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();

        int a = x2 - x1;
        int b = y2 - y1;
        int x3 = x2 - b;
        int y3 = y2 + a;
        int x4 = x3 - a;
        int y4 = y3 - b;

        System.out.println(String.format("%d %d %d %d", x3, y3, x4, y4));
        sc.close();
    }

}


Measured memory_bytes: 23764
#include<iostream>
#include<string>
#include<cmath>
using namespace std; 
int main(){
  double h;
  double max=0,min=1000000;
  while (cin>>h){
    if(h>max)max=h;
    if(h<min)min=h;
  }
  cout<<max-min<<endl;  

  return 0;
}

Measured memory_bytes: 3256
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::input;
use std::collections::*;

fn main() {
    input! {
        a:i128,
        v:i128,
        b:i128,
        w:i128,
        t:i128,
    }
    let dist = (a - b).abs();
    let ans = if v <= w {
        "NO"
    } else if dist <= (v - w) * t {
        "YES"
    } else {
        "NO"
    };
    println!("{}", ans);
}

Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(c, i, n) for (int i = c; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main()
{
    int N;
    cin >> N;
    vector<string> S(N);
    rep(0, i, N)
    {
        cin >> S.at(i);
        sort(all(S.at(i)));
    }
    sort(all(S));
    ll ans = 0;
    ll count = 1;
    rep(0, i, N - 1)
    {
        if (S.at(i) == S.at(i + 1))
        {
            count++;
        }
        else
        {
            ans += count * (count - 1) / 2;
            count = 1;
        }
    }
    ans += count * (count - 1) / 2;
    cout << ans << endl;
}

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

#define N_MAX 300000

long long bit_foosum[N_MAX+1];
long long bit_num[N_MAX+1];

/*BITÌÝÏa*/
long long bit_sum(const long long* bit,int n) {
	long long sum=0;
	n++;
	while(n>0) {
		sum+=bit[n];
		n-=(n & (-n));/*ÅãÌ1Ìrbgðø­*/
	}
	return sum;
}

/*BITÉlðÁZ*/
void bit_add(long long* bit,int pos,long long num) {
	pos++;
	while(pos<=N_MAX) {
		bit[pos]+=num;
		pos+=(pos & (-pos));/*ÅãÌ1Ìrbgð«·*/
	}
}

typedef struct {
	int housyutu;
	int kyoyou;
	int index;
} bacteria_t;

bacteria_t bact[N_MAX];

/*úoÊÌ¸Å\[g*/
int comp_housyutu(const void* x,const void* y) {
	const bacteria_t* a=(const bacteria_t*)x;
	const bacteria_t* b=(const bacteria_t*)y;
	if((a->housyutu)>(b->housyutu))return 1;
	if((a->housyutu)<(b->housyutu))return -1;
	if((a->kyoyou)>(b->kyoyou))return 1;
	if((a->kyoyou)<(b->kyoyou))return -1;
	return 0;
}

/*eÊÌ¸AúoÊÌ~Å\[g*/
int comp_kyoyou(const void* x,const void* y) {
	const bacteria_t* a=(const bacteria_t*)x;
	const bacteria_t* b=(const bacteria_t*)y;
	if((a->kyoyou)>(b->kyoyou))return 1;
	if((a->kyoyou)<(b->kyoyou))return -1;
	if((a->housyutu)<(b->housyutu))return 1;
	if((a->housyutu)>(b->housyutu))return -1;
	return 0;
}

int main(void) {
	int N;
	int i;
	int result;
	int now_result;
	int now_result2;
	long long now_kyoyou;
	int left,right,mid;
	scanf("%d",&N);
	for(i=0;i<N;i++) {
		scanf("%d %d",&bact[i].housyutu,&bact[i].kyoyou);
	}
	/*úoÊÌ¸Å\[g*/
	qsort(bact,N,sizeof(bacteria_t),comp_housyutu);
	/*ÝÏaðßé*/
	for(i=0;i<N;i++) {
		bit_add(bit_foosum,i,bact[i].housyutu);
		bit_add(bit_num,i,1);
		bact[i].index=i;
	}
	/*eÊÌ¸Å\[g*/
	qsort(bact,N,sizeof(bacteria_t),comp_kyoyou);
	result=0;
	for(i=0;i<N;i++) {
		now_kyoyou=bact[i].kyoyou;
		/*ñªTõ*/
		left=0;right=N-1;
		now_result=0;
		while(left<=right) {
			mid=(left+right)/2;
			now_result2=bit_sum(bit_num,mid);
			if(bit_sum(bit_foosum,mid)>now_kyoyou*now_result2) {
				/*üçÈ¢*/
				right=mid-1;
			} else {
				/*üé*/
				if(now_result<now_result2)now_result=now_result2;
				left=mid+1;
			}
		}
		if(now_result>result)result=now_result;
		/*iÔÚÌ÷¶¨ðO·*/
		bit_add(bit_foosum,bact[i].index,-bact[i].housyutu);
		bit_add(bit_num,bact[i].index,-1);
	}
	printf("%d\n",result);
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

void selection(int n, int data[]){
  int min ;
  int test[100];
  int tmp,key,counter = 0;
  for (int k = 0; k < n; k ++){
        test[k] = data[k];
      }
  //i-nまでのminを探索
  //i:既ソートの右端index
  //j:未ソートの左端index
  for (int i = 0; i < n-1 ; i ++ ){ //未ソートの右端でループ
    min = test[i+1];//既ソートの左端の値をminの初期値に
    key = i+1; // keyの初期化
    for (int j = i+1; j < n; j ++ ){
      //最小値とそのindexの探索
      
      if (test[j]< min){
        min = test[j];
        key = j;
      }
    }
    //既ソートのminが未ソートの右端よりも小さい場合にswap
    if (test[i] > min){
    //data[i]にminを、data[j]にdata[i]を代入
      tmp = test[i];
      test[i] = min;
      test[key] = tmp;
      counter += 1; 
    
    }
  }
  //結果の出力
  for (int i = 0; i < n ; i ++ ){
    if (i > 0) printf(" ");
    printf("%d",test[i]);
  }
  printf("\n");
  printf("%d\n",counter);
}

int main(void){
  //入出力処理
  int n,data[100];
  scanf("%d",&n);
  for (int i = 0; i < n ; i ++ ){
    scanf("%d",&data[i]);
  }
  selection(n,data);
  return 0;
}







Measured memory_bytes: 2052
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int W = sc.nextInt();
        int H = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();

        System.out.println(solve(W, H, x, y));

        sc.close();
    }

    static String solve(int W, int H, int x, int y) {
        return String.format("%f %d", W / 2.0 * H, (x * 2 == W && y * 2 == H) ? 1 : 0);
    }
}

Measured memory_bytes: 36068
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const long long LINF = 1000000000000000018ll;
const int INF = 1000000009;
const int mod = 1000000007;
const int mod2 = 998244353;

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

std::map<long long, int> prime_factor(long long n) {
  std::map<long long, int> res;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if (n != 1) {
    res[n] = 1;
  }
  return res;
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::setprecision(20) << std::fixed;

  long long n;
  cin >> n;

  auto ps = prime_factor(n);

  long long ans = 0;

  for (auto it = ps.begin(); it != ps.end(); it++) {
    long long e = it->second;
    long long add = 0;
    for (long long i = 1; i <= e; i++) {
      if (i * (1 + i) / 2 <= e) {
        add = i;
      }
    }
    ans += add;
  }
  cout << ans << "\n";

  return 0;
}

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

using namespace std;

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

  vector<int> vec[10];
  for (int i = 0; i < m; i++) {
	int k;
	cin >> k;
	for (int j = 0; j < k; j++) {
	  int tmp;
	  cin >> tmp;
	  vec[i].push_back(tmp);
	}
  }
  int p[10];
  for (int i = 0; i < m; i++)
	cin >> p[i];

  int res = 0;

  for (int i = 0; i < (1 << n); i++) {
	vector<int> tmp;
	bool flg = false;
	for (int j = 0; j < n; j++) {
	  if (1 & (i >> j))
		tmp.push_back(1);
	  else
		tmp.push_back(0);
	}

	for (int j = 0; j < m; j++) {
	  int on = 0;
	  for (int s : vec[j]) {
		if (tmp[s - 1])
		  on++;
	  }
	  if (on % 2 == p[j]) {
		flg = true;
	  } else {
		flg = false;
		break;
	  }
	}
	if (flg)
	  res++;
  }
  
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE ViewPatterns #-}
{-# LANGUAGE TupleSections #-}
{-# LANGUAGE MultiWayIf #-}

import Control.Monad
import Control.Monad.ST
import Control.Monad.State
import Control.Applicative
import Data.List
import Data.Array
import Data.Array.IO
import Data.Maybe
import Data.Bits
import Data.Ord
import Data.Ratio
import Data.Int
import Data.Char
import qualified Data.ByteString.Char8 as BS
import qualified Data.Set as Set
import Data.Tuple
import Data.Function
import Text.Printf
import Debug.Trace
import Numeric

modifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)

listToTuple2 [a,b] = (a,b)
listToTuple3 [a,b,c] = (a,b,c)
listToTuple4 [a,b,c,d] = (a,b,c,d)
listToTuple5 [a,b,c,d,e] = (a,b,c,d,e)

getWords = getLine >>= return . words

readIntBS = fst . fromJust . BS.readInt

for = flip map

main :: IO ()
main = do
  (h,w) <- listToTuple2 . map read . words <$> getLine :: IO (Int,Int)
  field <- lines <$> getContents

  mapM_ putStrLn $ transpose $ filter (any (=='#')) $ transpose (filter (any (=='#')) field)


Measured memory_bytes: 2044
input1 = input()
input2 = input()

if len(input1) == (len(input2) - 1):
    for i in range(len(input1)):
        if input1[i] == input2[i]:
            pass
        else:
            print("No")
            exit()
    print("Yes")
        
else:
    print("No")
    

Measured memory_bytes: 9040
s=input()
l=len(s)
space=l-1
ans=0

for i in range(2**space):
    t=[0]*space
    for j in range(space):
        if ((i>>j)&1)==1:
            t[-j-1]="+"

    fomula=s[0]
    for k in range(1, l):
        if t[k-1]==0:
            fomula=fomula+s[k]
        else:
            fomula=fomula+t[k-1]+s[k]
    
    add=eval(fomula)
    ans+=add

print(ans)

Measured memory_bytes: 3064
#include <stdio.h>
char s[200010];
int c[2020], inv = 202;
int main() {
    int ans = 0, tt = 1, cur = 0;
    scanf("%s", s);
    c[0] = 1;
    for (int i = 0; s[i]; i++) {
        int x = s[i] - '0';
        cur = (cur * 10 + x) % 2019;
        tt = (tt * inv) % 2019;
        ans += c[(cur * tt) % 2019];
        c[(cur * tt) % 2019]++;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1936
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    vector<int64_t> b(N, 0);
    
    for (int i = 0; i < N; i++){
        cin >> a.at(i);
        b.at(a.at(i) - 1)++;
    }
    int64_t sum = 0;
    for (int i = 0; i < N; i++){
        if (b.at(i) >= 2) {
            sum += (b.at(i) - 1) * b.at(i) / 2;
        }
    }
    
    for (int i = 0; i < N; i++){
        cout << sum - b.at(a.at(i) - 1) + 1 << endl;
    }
}

Measured memory_bytes: 4992
for r in range(input()):
	snake=raw_input()
	L=len(snake)
	if L>5 and snake == ">'" + "="*((L-4)/2) + "#" + "="*((L-4)/2) + "~":
		print "A"
	elif L>5 and snake == ">^" + "Q="*((L-4)/2) + "~~":
		print "B"
	else:
		print "NA"

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

int main() {
	int n;
	cin>>n;
	string s;
	cin>>s;
	int r=0,b=0;
	for(int i=0;i<n;i++){
		if(s[i]=='R')r++;
		else b++;
	}
	if(r>b)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


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

using namespace std;

int main() {
    int x, ans = 0;
    scanf("%d", &x);
    ans += 1000*(x/500);
    x -= 500*(x/500);
    ans += 5*(x/5);
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll W, H, N;
    cin >> W >> H >> N;
    ll min_x = 0, max_x = W;
    ll min_y = 0, max_y = H;
    for (ll i = 0; i < N; i++) {
        ll x, y, a;
        cin >> x >> y >> a;
        if (a == 1) {
            min_x = max(min_x, x);
        } else if (a == 2) {
            max_x = min(max_x, x);
        } else if (a == 3) {
            min_y = max(min_y, y);
        } else {
            max_y = min(max_y, y);
        }
    }

    cout << max((max_x - min_x), (ll)0) * max((max_y - min_y), (ll)0) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#define int long long
using namespace std;

signed main() {
	int a, b, c; cin >> a >> b >> c;
	int s = b / c - (max(a - 1, 0ll)) / c;
	if (a == 0)s++;
	cout << s << endl;
}

Measured memory_bytes: 256
//E.H//
# include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;
int n,m;
bool memo[100005];
int byk[100005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    memo[1]=1;
    for(int i=1;i<=n;i++){
        byk[i]=1;
    }
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        if(memo[a]==1){
            memo[b]=true;

        }
        byk[a]--;
        byk[b]++;
        if(byk[a]==0) memo[a]=false;
        //cout<<i<<" "<<byk[a]<<" "<<byk[b]<<endl;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(memo[i] && byk[i]>0){
            //cout<<i<<endl;
            ans++;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4016
import java.io.IOException;
    import java.math.BigDecimal;
    import java.math.BigInteger;
     
    public class Main {
        private static final StringBuilder builder = new StringBuilder();
        public static void main(String[] args) {
            int a = readInt(), b = readInt(), c = readInt(), k = readInt();
            for (int i = 0; i < k; i++) {
                if (a >= b) b *= 2;
                else if (b >= c) c *= 2;
                else break;
            }
     
            if (a < b && b < c) System.out.print("Yes");
            else System.out.print("No");
     
        }
     
        private static void read() {
            builder.setLength(0);
            while (true) {
                try {
                    int b = System.in.read();
                    if (b == ' ' || b == '\n' || b == -1) {
                        break;
                    } else {
                        builder.appendCodePoint(b);
                    }
                } catch (IOException e) {
                    break;
                }
            }
        }
     
        private static int readInt() {
            read();
            return Integer.parseInt(builder.toString());
        }
     
        private static int readInt(int radix) {
            read();
            return Integer.parseInt(builder.toString(), radix);
        }
     
        private static long readLong() {
            read();
            return Long.parseLong(builder.toString());
        }
     
        private static long readLong(int radix) {
            read();
            return Long.parseLong(builder.toString(), radix);
        }
     
        private static BigInteger readBigInteger() {
            read();
            return new BigInteger(builder.toString());
        }
     
        private static BigInteger readBigInteger(int radix) {
            read();
            return new BigInteger(builder.toString(), radix);
        }
     
        private static double readDouble() {
            read();
            return Double.parseDouble(builder.toString());
        }
     
        private static BigDecimal readBigDecimal() {
            read();
            return new BigDecimal(builder.toString());
        }
     
        private static float readFloat() {
            read();
            return Float.parseFloat(builder.toString());
        }
     
        private static void skipLine() {
            while (true) {
                try {
                    int b = System.in.read();
                    if (b == '\n' || b == -1) {
                        break;
                    }
                } catch (IOException e) {
                    break;
                }
            }
        }
     
        private static void skip() {
            while (true) {
                try {
                    int b = System.in.read();
                    if (b == ' ' || b == '\n' || b == -1) break;
                } catch (IOException e) {
                    break;
                }
            }
        }
     
    }

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

typedef pair<int,int>   pii;
typedef vector< pii >  vii;
typedef long long int 	ll;

#define pb push_back
#define fe first
#define se second
#define all(a) (a).begin(),(a).end()
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define scn(n) scanf("%d",&n)
#define prn(n) printf("%d\n",n)
#define scnl(n) scanf("%lld",&n)
#define lldout(n) printf("%lld\n",n)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mset(A, val) memset(A, val, sizeof(A))
#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	  const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const ll mod = 1e9 + 7ll;
const int N = (int)1e5 + 7;

int main(){
	
	fast_io;
	int n;
	cin>>n;
	vector<int> ar(n);
	rep(i,0,n) cin>>ar[i];
	sort(all(ar));
	ll ans=0;
	rep(i,0,n){
		int k=n-1;
		rep(j,n,i+1){
			while(k>j&&ar[k]>=ar[i]+ar[j]) k--;
			ans+= (ll) max(k-j,0);
		}
		// trace(i,k,ans);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 384
#include <iostream>

int main()
{
	int n;
	int residentNums[4][3][10] = {};
	std::cin >> n;
	for (int i = 0; i < n; i++)
	{
		int building;
		int floor;
		int room;
		int residentNum;
		std::cin >> building >> floor >> room >> residentNum;
		residentNums[building-1][floor-1][room-1] += residentNum;
	}
	for (int b = 0; b < 4; b++)
	{
		if (b > 0)
		{
			std::cout << "####################" << '\n';
		}
		for (int f = 0; f < 3; f++)
		{
			for (int r = 0; r < 10; r++)
			{
				std::cout << " " << residentNums[b][f][r];
				if (r == 9)
				{
					std::cout << '\n';
				}

			}
		}
	}

	return 0;
}

Measured memory_bytes: 3104
v, e = gets.split.map(&:to_i)
g = v.times.map{[]}
rg = v.times.map{[]}
e.times do
  s,t = gets.split.map(&:to_i)
  g[s] << t
  rg[t] << s
end
arr = rg.map.with_index{|a, i| i if a.empty? }.compact
until arr.empty?
  s = arr.shift
  p s
  g[s].each{|t| rg[t].delete(s); arr << t if rg[t].empty?}
end

Measured memory_bytes: 13116
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <cmath>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t K,N;

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N>>K;

	long double res = 0;
	for (int32_t i = 1; i <= N; i++)
	{
		long double add = 1;
		for (int32_t kkk = K;!(kkk <= i); kkk= (kkk + 1) / 2) {
			add /= 2;
		}
		res += add;
	}
	out 
		<< std::fixed << std::setprecision(13) << res / N << endl;


	return 0;
}
#endif


Measured memory_bytes: 384
n, a, b = map(int, input().split())

mod = 10**9+7


def comb(x, y):
    numer = 1
    denom = 1
    for i in range(1, y+1):
        numer *= n+1-i
        numer %= mod
        denom *= i
        denom %= mod
    denom = pow(denom, mod-2, mod)
    return numer * denom


print((pow(2, n, mod)-1-comb(n, a)-comb(n, b)) % mod)


Measured memory_bytes: 40116
/*{{{*/
#include<bits/stdc++.h>

typedef long long ll;

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

#define vl vector<ll>
#define pll pair<ll,ll>

#define DEBUG(x) cout<<#x<<": "<<x<<endl

using namespace std;
/*}}}*/

int main() {
  ll n;
  cin >> n;
  vl a(n);
  REP(i,n) cin >> a[i];
  ll rest = 1000;
  ll kab = 0;
  vector<bool> sell(n);
  vector<bool> buy(n);
  REP(i,n){
    if(i<n-1){
      sell[i] = a[i] >= a[i+1];
      buy[i] = a[i] <= a[i+1];
    }else{
      sell[i] = true;
      buy[i] = false;
    }
  }
  REP(i,n){
    if(sell[i]){
      rest += kab*a[i];
      kab = 0;
    }
    if(buy[i]){
      kab += rest/a[i];
      rest %= a[i];
    }
    //DEBUG(rest);
  }

  cout << rest << endl;
  return 0;
}


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

S = input()
i = 0
dif = 100000

while i <= len(S) - 3:
    nuki = int(S[i:i+3])
    # print(nuki)
    sa = 753 - nuki if nuki <= 753 else nuki - 753
    # print(sa)
    if sa <= dif:
        dif = sa
    i += 1

print(dif)



Measured memory_bytes: 2940
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		for(int i=0;i<=10000;i++) {
			if(a*i % b == c) {
				System.out.println("YES");
				System.exit(0);
			}
		}
		System.out.println("NO");
	}
}

Measured memory_bytes: 23124
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int64_t L,R;
  cin >> L >> R;
  int mod;
  int ans=2019;
  long long a=L%2019,b=R%2019;
  if((R-L)>=2018){
    for(int i=0;i<2018;i++){
      for(int j=i;j<=2018;j++){
        mod = (i*j)%2019;
        ans = min(ans ,mod);
      }
    }cout << ans << endl;
  }else{
    if(a<b){
      for(int i=a;i<b;i++){
        for(int j=i+1;j<=b;j++){
          mod = (i*j)%2019;
          ans = min(ans ,mod);
        }
      }
    }else{
      for(int i=0;i<b;i++){
        for(int j=i+1;j<=b;j++){
          mod = (i*j)%2019;
          ans = min(ans ,mod);
        }
      }for(int i=a;i<2018;i++){
        for(int j=i+1;j<=2018;j++){
          mod = (i*j)%2019;
          ans = min(ans ,mod);
        }
      }
    }
    cout << ans <<endl;
  }
}


Measured memory_bytes: 3552
from collections import Counter
n = int(input())
v = list(map(int,input().split()))
a = []
b = []
for i in range(0,n,2):
    a.append(v[i])
    b.append(v[i+1])
a = Counter(a)
b = Counter(b)
p = a.most_common()[0][1]
q = b.most_common()[0][1]

if a.most_common()[0][0] == b.most_common()[0][0]:
    if p == n//2:
        if q == n//2:
            print(n-p-q+n//2)
        else:
            print(n-q-b.most_common()[1][1])
    else:
        if q != n//2:
            
            print(min(n-p-b.most_common()[1][1],n-q-a.most_common()[1][1]))
        else:
            print(n-q-a.most_common()[1][1])
            
    
        
            
        

else:
    print(n-p-q)



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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

#define PI (2*acos(0.0))
#define eps 1e-9
#define pcase cout<<"Case "<<++cs<<":"
#define pb push_back
#define endl "\n"
#define watch(x) cout << (#x) << " is " << (x) << endl;
#define show(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi] << " "; cout << endl;
#define showpair(v) for(int fi = 0; fi < v.size(); fi++) cout << v[fi].first << " " << v[fi].second << endl;
#define mp make_pair
#define ff first
#define ss second
#define fu cout << "lol" << endl;
#define precision(n) cout << fixed << setprecision(n);
#define lb lower_bound
#define up upper_bound
#define vscan for(i = 0;i<n;i++){cin>>in; v.pb(in);}
#define all(a) a.begin(), a.end()
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define mem(a,val) memset(a,val,sizeof(a))
#define loop(i,n) for(i = 0; i < n; i++)
#define TC() ull T; cin>>T; while(T--)
#define IN(x) {scanf("%d",&x);}
#define LL(x) {scanf("%lld",&x);}
#define CC(x) {scanf("%c",&x);}
#define pfl(x) printf("%d\n",x)
#define pfll(x) printf("%lld\n",x)
#define newl puts("")
#define space printf(" ")
#define MOD 1000000007
#define inf 10000000000

const int N = 1e5+10;
ll dp[N][105];

int main()
{
    int i = 0, j = 0, cs = 0, in;
    int n, w; cin>>n>>w;
    vii v;
    for(i = 0; i < n; i++){
        int a, b; cin>>a>>b; v.pb({a,b});
    }
    for(i = 0; i <= w; i++){
        if(i >= v[0].ff) dp[i][1] = v[0].ss;
    }
    for(i = 2; i <= n; i++){
        for(j = 0; j <= w; j++){
            dp[j][i] = dp[j][i-1];
            if(j >= v[i-1].ff) dp[j][i] = max(dp[j][i], dp[j-v[i-1].ff][i-1] + v[i-1].ss);
        }
    }
    cout << dp[w][n] << endl;
    return 0;
}


Measured memory_bytes: 82304
#include <iostream>
using namespace std;
 
const int maxn = 50;
 
typedef struct 
{
	int parent;
	int left;
	int right;
}Node;
 
Node T[maxn];
int n;
 
void preorder(int u)
{
	if(u==-1)
		return ;
	cout << " "<<u;
	preorder(T[u].left);
	preorder(T[u].right);
}
 
void inorder(int u)
{
	if(u==-1)
		return ;
	inorder(T[u].left);
	cout << " "<<u;
	inorder(T[u].right);
}
 
void postorder(int u)
{
	if(u==-1)
		return ;
	postorder(T[u].left);
	postorder(T[u].right);
	cout << " "<<u;
}
 
int main ()
{
	int i;
	cin >> n;
	for(i=0;i<n;i++)
	{
		T[i].parent=-1;
		T[i].left=-1;
		T[i].right=-1;
	}
	int id,rchild,lchild;
	for(i=0;i<n;i++)
	{
		cin >> id >> lchild >> rchild;
		T[id].left=lchild;
		T[id].right=rchild;
		if(rchild!=-1)
			T[rchild].parent=id;
		if(lchild!=-1)
			T[lchild].parent=id;
	}
	int root;
	for(i=0;i<n;i++)
	{
		if(T[i].parent==-1)
		{
			root=i;
		}
	}
	cout << "Preorder\n" ;
	preorder(root);
	cout <<"\nInorder\n";
	inorder(root);
	cout << "\nPostorder\n";
	postorder(root);
	cout << endl;
	return 0;
}



Measured memory_bytes: 3092
n = int(input())
ans = ''
i = 0
if n == 0:
    print(0)
    exit()
while n != 0:
    if n % ((-2) ** (i + 1)) == 0:
        ans = '0' + ans
    else:
        ans = '1' + ans
        n -= (-2) ** i
    i += 1
print(ans)

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

int a, b;

void read() {
    cin >> a >> b;
}


void work() {
    if (a > b) {
        swap(a, b);
    }
    cout << string(b, a + '0') << endl;
}


int main() {
    read();
    work();
    return 0;
}


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

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int INF = pow(2,29);
const int MOD = 1000000007;

int main() {
  int N, H, W; cin >> N >> H >> W;
  int result = (N-H+1) * (N-W+1);
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll mod = 1e9 + 7;

int main(){
	ll h, w;
	cin >> h >> w;
	ll ans = (h * w + 1) / 2;
	if (h == 1 || w == 1) {
		cout << 1 << endl;
		return 0;
	}
	cout << ans << endl;
}

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

typedef long long ll;
const int INF = 1e9;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	string s;
	cin>>s;
	if (s[2] == s[3] && s[4] == s[5]){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
as = gets.split.map(&:to_i)
MAX = 2 * 10**5

cs = Array.new(MAX + 1, 0)
# それぞれの数が配列に何個あるか数える
as.each do |a|
  cs[a] += 1
end


sum = cs.inject(0) do |r, v|
  r + v * (v - 1) / 2
end

as.each do |a|
  diff = (cs[a] - 1) # c * (c - 1) / 2 - (c - 1) * (c - 2) / 2
  puts sum - diff
end

Measured memory_bytes: 23172
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s, t;
    cin >> s >> t;
    int n = (int)t.size();
    int m = (int)s.size();
    int answer = INT_MAX;
    for (int i = 0; i < m - n + 1; i++) { 
        int minRemovedChar = 0;
        for (int j = 0; j < n; j++) { 
            if (t[j] != s[i + j]) { 
                minRemovedChar++; 
            } 
        } 
        answer = min(minRemovedChar, answer); 
    } 
    cout << answer << "\n";
    return 0;
}

Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
vector<int>dp(100001);
//bottum up
int mincost(vector<int>arr,int n)
{

    if(n<2 || n>100000)
    return 0;
    //base case
  dp[1]=0;
  dp[2]=abs(arr[1]-arr[0]);
  if(n==2)
  return dp[n];
 
  
//   //look up
//   if(dp[n]!=-1)
//     return dp[n];
  
  for(int i=3;i<=n;i++)
  {
    dp[i]=min(dp[i-1]+abs(arr[i-1]-arr[i-1-1]),dp[i-2]+abs(arr[i-1]-arr[i-2-1]));
    
  }
  return dp[n];
  
  }
  
 
 
int main()
{
  int N;
  cin>>N;
  vector<int>height;
  int h;
  
  //memset(dp,-1,sizeof(dp));
 for(int i=0;i<N;i++)
 {
    cin>>h;
    height.push_back(h);
 }
  
  cout<<mincost(height,N);
  return 0;
}


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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<int, int> P;


ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

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

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/******************************************
** A main function is start from here  ****
*******************************************/
int main(){
  int N;
  int A[200000];
  cin >> N;
  int target = 1;
  int atk = 0;
  rep(i, N) {
    cin >> A[i];
    if(A[i]== target)target++;
    else atk++;
  }

  if(atk==N)cout << -1;
  else cout << atk;
  
  
  return 0;
}


Measured memory_bytes: 1024
// created by mtnshh
 
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
 
#define ll long long
#define ld long double
 
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
 
#define err() cout<<"=================================="<<endl;
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl
 
#define pb push_back
#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second
 
#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
#define endl "\n"
 
const ll logN = 20;
const ll M = 1000000007;
const ll INF = 1e12;
#define PI 3.14159265
 
const ll N = 100005;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n;
	cin>>n;
	ll ans=0;
	ll A[6] = {1, 10 ,99+1, 999+1, 9999+1, 99999+1};
	rep(i,1,n+1){
		ll dig=0;
		ll a=i;
		ll p=1;
		while(a){
			dig++;
			a=a/10;
			p=p*10;
		}
		p=p/10;
		ll b =  i - i%10 - (i/p)*p;
		b=b/10;
		ll e = i%10;
		ll f = i/p;
		dig-=1;
		ll q=10;
		ll s=1;
		if(e!=0){
			rep(j,0,dig){
				rep(k,0,s){
					ll r = e*q + k*10 + f;
					if(r<i)	ans+=2; 
				}
				q=q*10;
				s=s*10;
			}
		}
		if(e==f and dig!=0)	ans+=3;	
		else if(e==f)	ans++;
	}
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 384
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

//conversion
//------------------------------------------
inline 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();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

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

LL N,a[10001],c=0;

int main(void){
    cin>>N;
    REP(i,N){
        cin>>a[i];
        while(-1){
            if(a[i]%2==0){
                a[i]/=2;
                c++;
            }
            else{
                break;
            }
        }
    }
    cout<<c<<endl;
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define NAME "H"
#define vt vector
#define ll long long
#define fi first
#define se second
#define pb push_back
#define time ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

void init()
{
    freopen(NAME".inp","r",stdin);
    freopen(NAME".out","w",stdout);
}

const int N=1e3+3,mod=1e9+7;
int n,m;
char a[N][N];

void inp()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>a[i][j];
}

ll f[N][N] {0};

void solve()
{
    f[1][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i==1 && j==1) continue;
            if(a[i][j]=='.') f[i][j]=f[i-1][j]+f[i][j-1];
            else f[i][j]=0;
            f[i][j]%=mod;
        }
    }
    cout<<f[n][m]%mod;
}

void out()
{
    solve();
}

int main()
{
    //init();
    inp();
    out();
}


Measured memory_bytes: 9088
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N;
	in >> N;

	LL ans = 1145148101919;
	for (LL i = 1; i <= sqrt(N); ++i)
	{
		if (N % i == 0) ans = std::min(ans, i - 1 + N / i - 1);
	}
	out << ans << std::endl;
}


Measured memory_bytes: 256
H,W = gets.split.map(&:to_i)
S = H.times.map { gets.chomp }

failed = false
H.times do |i|
  W.times do |j|
    # #だったら上下左右をチェック
    u,d,l,r = false
    if S[i][j] == '#'
      u = true if i != 0 && S[i-1][j] == '#'
      d = true if i != H-1 && S[i+1][j] == '#'
      l = true if j != 0 && S[i][j-1] == '#'
      r = true if j != W-1 && S[i][j+1] == '#'

      # 上下左右全部が.だったら失敗
      unless u || d || l || r
        failed = true
        break
      end
    end
    break if failed
  end
  break if failed
end

if failed
  puts 'No'
else
  puts 'Yes'
end

Measured memory_bytes: 1788
//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"

#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1LL<<60LL)
typedef long long ll;

using namespace std;

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

Measured memory_bytes: 256
# util functions

# debug
$debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if $debugFlag

def pd(str)
  p str if $debugFlag
end

def printd(str)
  print str if $debugFlag
end

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if lc != 0
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

nn = inputs[0][0]
str = inputs[1][0]

# input check
if $debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

# body
if $debugFlag
  p nn
  p str
end

ans = 1
cur = str[0]

if nn == 1
  puts 1
  exit
end

for i in 1..nn-1
  if str[i] != cur
    ans += 1
    cur = str[i]
  end
end

puts ans


Measured memory_bytes: 2044
#include <iostream>
#include <vector>
#include <algorithm>

#define INF 998244353
#define int long long

using namespace std;

signed main()
{
    int N;
    cin >> N;
    vector<int> D(N - 1);
    vector<int> distance(N, 0);
    int first;
    cin >> first;
    for (int i = 0; i < N - 1; i++)
    {
        cin >> D[i];
    }

    int ans;

    if (first != 0)
    {
        ans = 0;
    }
    else
    {
        distance[0]++;
        sort(D.begin(), D.end());
        ans = 1;
        for (int i = 0; i < N - 1; i++)
        {
            if (D[i] == 0 || distance[D[i] - 1] == 0)
            {
                ans = 0;
                break;
            }
            else
            {
                distance[D[i]]++;
                ans = ans * distance[D[i] - 1] % INF;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long X, hp=0;
    cin >> X;

    if(X>=500){
        hp=1000*(X/500);
        X=X%500;
    }
    if(X>=5){
        hp=hp+(5*(X/5));
    }
     cout << hp <<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

double rounding(double x){
    double x1=x*10000;
    int tmp=(int)(x*1000);
    double x2=(double)tmp*10;
    if(x1-x2>=5) return ((double)tmp+1)/1000;
    else return x;
}

double zero(double x){
    if(x==0||x==-0) return 0;
    else return x;
}
int main(void){
    int a,b,c,d,e,f;
    double x,y;
    while(scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&f)==6){
        printf("%.3f %.3f\n",zero(rounding((double)(c*e-b*f)/(double)(a*e-b*d))),zero(rounding((double)(c*d-a*f)/(double)(b*d-a*e))));
    }
    return 0;
}


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

using namespace std;

int a[1000001];

int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    bool ch = false;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        if (a[i] == i+1) {
            ch = true;
        }
    }
    if (!ch) {
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (a[i] == i+1 && i != n-1) {
            if (a[i+1] != i+1) {
                swap (a[i],a[i+1]);
                ans++;
            } else {
                if (i < n-2) {
                    swap (a[i],a[i+2]);
                } else {
                    swap (a[i],a[i-2]);
                }
            }
        } else if (a[i]==i+1 && i == n-1) {
            swap(a[i],a[i-1]);
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> a(N+1);
    int b = 1, ans = 0;
    for(int i = 0; i < N; ++i) cin >> a[i+1];
    for(int i = 1; i < N+1; ++i){
        ++ans;
        b = a[b];
        if(b == 2) break;
        else if(i == N) ans = -1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3756
MOD = (10**9)+7

def wari(x):
    return pow(x,MOD-2,MOD)

N,K = map(int,input().split())
fact = [1]*(N+1)#階乗入れます
for i in range(1,N+1,1):
    fact[i] =  (i*fact[i-1])%MOD

ans = [0]*(K+1)

for i in range(1,K+1,1):
    if i > N - K + 1:
        break
    ans[i] = (fact[K-1]*fact[N-K+1])%MOD
    ans[i] = (ans[i]*wari(fact[K-i]))%MOD
    ans[i] = (ans[i]*wari(fact[i-1]))%MOD
    ans[i] = (ans[i]*wari(fact[N-K-i+1]))%MOD
    ans[i] = (ans[i]*wari(fact[i]))%MOD
    

print(" ".join(list(map(str,ans[1:K+1]))))

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

int main(){
    int N;
    cin >> N;
    int d[N];
    for(int i=0; i<N; i++){
        cin >> d[i];
    }
    sort(d,d+N);
    cout << d[N/2] - d[N/2-1] << endl;

    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(void){
    int n,k,i;
    scanf("%d\n",&n);
    
    char s[n];
    for (i=0; i<n; i++){
        scanf("%c",&s[i]);
    }
    
    scanf("%d",&k);
    
    for (i=0; i<n; i++){
        if(s[i]!=s[k-1]){
            s[i] = '*';
        }
        printf("%c",s[i]);
    }
    
    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)


int main()
{
    int N;
    int ans[101][101];
    int hmax[101][101];
    scanf("%d", &N);

    REP(l, 101) REP(w, 101)
    {
        ans[l][w] = -1;
    }
    REP(l, 101) REP(w, 101)
    {
        hmax[l][w] = 1000000300;
    }

    REP(i, N)
    {
        int x, y, h;
        scanf("%d %d %d", &x, &y, &h);

        REP(l, 101) REP(w, 101) if (ans[l][w] != -2)
        {
            int estimated_top = h + abs(l - x) + abs(w - y);
            if (h > 0)
            {
                if (ans[l][w] == -1) ans[l][w] = estimated_top;
                else if (ans[l][w] != estimated_top) ans[l][w] = -2;
            }
            else
            {
                if (estimated_top < hmax[l][w]) hmax[l][w] = estimated_top;
            }
        }
    }

    REP(l, 101) REP(w, 101) if (ans[l][w] > 0 && hmax[l][w] >= ans[l][w]) printf("%d %d %d", l, w, ans[l][w]);
}


Measured memory_bytes: 256