akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(NULL);
int a[3][3];
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
cin>>a[i][j];
int n; cin>>n;
while(n--)
{
	int x; cin>>x;
	for(int i=0;i<3;i++)
	for(int j=0;j<3;j++)
	{
		if(a[i][j]==x)
		a[i][j]=-1;
	}
}
int ct4=0;
for(int i=0;i<3;i++)
{
int ct1=0,ct2=0,ct3=0;
for(int j=0;j<3;j++)
{
	if(a[i][j]==-1)
	ct1++;
	if(a[j][i]==-1)
	ct2++;
	if(a[j][j]==-1)
	ct3++;
	if(i+j==2)
	{
		if(a[i][j]==-1)
		ct4++;
	}
}
if(ct1==3||ct2==3||ct3==3)
{
	cout<<"Yes"; 
	return 0;
}
}
if(ct4==3)
{
		cout<<"Yes"; 
	return 0;
}

cout<<"No";
}


Measured memory_bytes: 256
<?php
$input = file_get_contents('php://stdin');
$inarr = explode(" ", $input);

$n = intval($inarr[0]);
$a = intval($inarr[1]);
$b = intval($inarr[2]);

if($a==0){
	echo "0";
  	exit();
}

$num = (int)floor($n/($a+$b));
$fraction = $n%($a+$b);
$total = $num * $a;
if($fraction>$a){
    $total+=$a;
}
else{
    $total+=$fraction;
}

//echo $total;
printf("%s\n", $total);
?>

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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
using ll = long long;


int main() {
    int n, a, b; cin >> n >> a >> b;
    int c = 0, d = 0, e = 0;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        if(x <= a) c++;
        if(a < x && x <= b) d++;
        if(b < x) e++;
    }

    cout << min({c, d, e}) << endl;

    return 0;
}


Measured memory_bytes: 3604
h, w = gets.strip.split.map(&:to_i)
c = 10.times.map { gets.strip.split.map(&:to_i) }
a = h.times.map { gets.strip.split.map(&:to_i) }

10.times do |via|
  10.times do |from|
    10.times do |to|
      c[from][to] = c[from][via] + c[via][to] if c[from][to] > c[from][via] + c[via][to]
    end
  end
end

p a.flatten.select {|e| e>=0 }.map {|e| c[e][1] }.inject(:+)



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

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int MOD = 1e9+7;
const ll INF = 1e16;

int cnt(int x) {
    int total = 0;
    for(int i=1; i*i<=x; i++) {
        if(x%i == 0) {
            if(x/i == i)
                total++;
            else
                total += 2;
        }
    }
    return total;
}

int main() {
    FASTIO
    
    int n;
    cin >> n;
    
    int tuples = 0;
    for(int i=1; i<=n-1; i++) {
        tuples += cnt(n-i);
    }
    
    cout << tuples << "\n";
    
    return 0;
}

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

int main() {
  int n; cin>>n;
  vector<int> L(n);
  rep(i, 0, n) cin>>L[i];

  sort(L.begin(), L.end());
  int ans=0;
  rep(i, 0, n) {
    rep(j, i+1, n) {
      int x=L[i]+L[j];
      int r=lower_bound(L.begin(), L.end(), x)-L.begin();
      int l=j+1;
      ans+=max(0, r-l);
    }
  }
  cout<<ans<<endl;
  return 0;
}


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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DMP(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%lld",x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

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

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

template<class T>
T Sq(const T& t){
	return t*t;
}

const int inf=LLONG_MAX/3;

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}
void No(){
	cout<<"No"<<endl;
	exit(0);
}

signed main(){
	int h=read(),w=read();
	vi freq(26,0);
	REP(i,h){
		string s=readString();
		for(auto c:s)
			freq[c-'a']++;
	}
	int p[3]{0,0,0};
	p[2]=h/2*w/2;
	if(h%2+w%2==0){
	}else if(h%2+w%2==1){
		if(h%2==0)swap(h,w);
		p[1]=w/2;
	}else{
		p[1]=h/2+w/2;
		p[0]=1;
	}
	REP(k,2){
		int s=1<<k;
		REP(i,26)if(freq[i]%(s*2)==s){
			if(p[k]){
				freq[i]-=s;
				p[k]--;
			}else No();
		}
	}
	Yes();
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  string ns;
  getline(cin, ns);
  const int N = ns.size();
  int bills = 0, carry = 0;
  for (int i = N - 1; i >= 0; --i) {
    int d = (ns[i] - '0') + carry;
    carry = d / 10;
    d %= 10;
    if (d < 5) {
      bills += d;
    } else if (d == 5) {
      bills += d;
      carry = (i > 0) && (ns[i - 1] - '0') >= 5;
    } else {
      bills += 10 - d;
      carry = 1;
    }
  }
  bills += carry;
  cout << bills << '\n';
}


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

public class Main {

  public static void main(String[] args) {
    new Main().run();
  }

  public void run() {

    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      final int n = Integer.parseInt(in.readLine());

      String line = in.readLine();
      int[] seq = new int[n];
      int[] ref = new int[n];
      char regex = ' ';
      boolean isContinue = true;
      for(int i=0, offset=0,next=0; isContinue; i++, offset = ++next) {
        if((next = line.indexOf(regex,offset)) == -1) {
          next = line.length();
          isContinue = false;
        }
        ref[i] = seq[i] = Integer.parseInt(line.substring(offset,next));
      }

      Arrays.parallelSort(ref);

      final int d = n>>1;
      final int p = ref[d];
      final int r = ref[d];
      final int l = ref[d-1];
      StringBuilder buf = new StringBuilder();
      for(int i=0; i<n; i++) {
        if(seq[i] < p) buf.append(r).append('\n');
        else buf.append(l).append('\n');
      }

      System.out.print(buf);
    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

Measured memory_bytes: 54192
/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-8
#define M_PI 3.141592653589793
#define bsize 512

#define ldouble long double
using namespace std;

#define bs 1000000007

const int N = 600031;

int n;

int ds(int x){
	if (x==0)
		return 0;
	return ds(x/10)+x%10;
}

int main(){
//	freopen("apache.in","r",stdin);
//	freopen("apache.out","w",stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
//	cin.tie(0);

	cin>>n;
	int res=1e9;
	for (int a=1;a<n;a++){
		int b=n-a;
		res=min(res,ds(a)+ds(b));
	}
	cout<<res<<endl;

//	cin.get(); cin.get();
	return 0;
}


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

#define INF ((1<<30)-1)
#define LLINF (1LL<<60)
#define EPS (1e-10)

int main() {
    int K, A, B;
    cin >> K >> A >> B;
    for (int i=A; i<=B; ++i) {
        if (i%K == 0) {
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
}


Measured memory_bytes: 3620
using System;

public class Problem_C
{
  public static void Main()
  {
    var N = int.Parse(Console.ReadLine());
    var top = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    var middle = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    var bottom = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
    Array.Sort(top);
    Array.Sort(bottom);

    long ans = 0;
    for (int i = 0; i < N; i++)
    {
      long t = LowerBound(top, middle[i]);
      long b = UpperBound(bottom, middle[i]);
      if (b < N) ans += t * (N - b);
    }
    Console.WriteLine(ans);
  }

  private static int LowerBound(int[] arr, int val)
  {
    int first = 0, last = arr.Length - 1, mid;
    while (first <= last)
    {
      mid = (first + last) >> 1;
      if (val > arr[mid]) first = mid + 1;
      else last = mid - 1;
    }
    return first;
  }

  private static int UpperBound(int[] arr, int val)
  {
    int first = 0, last = arr.Length - 1, mid;
    while (first <= last)
    {
      mid = (first + last) >> 1;
      if (val >= arr[mid]) first = mid + 1;
      else last = mid - 1;
    }
    return first;
  }
}


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

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

    ll lim = sqrt(n) + 1;    
    vector<ll> div(n+1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; i*j <= n; j++) {
            div[i*j]++;
        }
    }

    ll sol = 0;
    for (int i = 1; i <= n; i++) {
        sol += i * div[i];
    }
    cout << sol << endl;
}

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

using namespace std;

typedef long long ll;
typedef pair<int,int> P;

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

    int n,m;cin>>n>>m;
    map<int,int> mp;//(値, 個数)
    vector<set<int>> st(m);// st[i]:=余りiの値集合 
    vector<int> sum(m,0),ps(m,0);//sum[i],ps[i]:=余りiの個数,ペア数
    for(int i=0;i<n;i++){
        int x;cin>>x;
        mp[x]++;
        st[x%m].insert(x);
        sum[x%m]++;
    }
    int res=0;
    res += sum[0]/2;
    if(m%2==0){
        res += sum[m/2]/2;
        st[m/2].clear();
    }
    for(int i=1;i<m;i++){
        if(st[i].size()==0) continue;
        for(auto itr=st[i].begin();itr!=st[i].end();itr++){
            int x=*itr;
            ps[i] += mp[x]/2;
        }
    }
    for(int i=1;i<=m/2;i++){
        if(m%2==0 && i==m/2) continue;
        int j=m-i;
        if(sum[i]<sum[j]){
            swap(sum[i],sum[j]);
            swap(ps[i],ps[j]);
        }
        res += sum[j];
        res += min((sum[i]-sum[j])/2, ps[i]);
    }
    cout<<res<<endl;
}


Measured memory_bytes: 15104
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    println!("ABC{:03}", n);
}


Measured memory_bytes: 4352
def divisors(n)
  p = []
  2.upto((n**0.5)) do |i|
    break if i > n / i
    while n % i == 0
      p << i
      n /= i
    end
  end
  p << n if n != 1
  p
end
n,p = gets.chomp.split(" ").map(&:to_i)
hash = Hash.new(0)
ans = 1
divisors(p).each do |x|
  hash[x] += 1
  if hash[x] >= n
    ans *= x
    hash[x] = 0
  end
end
puts ans


Measured memory_bytes: 14544
from collections import defaultdict, deque
    
N, Q = map(int, input().split())

edge = defaultdict(set)
for i in range(N-1):
    a, b = map(int, input().split())
    edge[a].add(b)
    edge[b].add(a)

score = [0]*(N+1)
for j in range(Q):
    p, x = map(int, input().split())
    score[p]+=x
    
q = deque()
q.append(1)
visited = [0]*(N+1)
while q:
    v = q.pop()
    visited[v]=1
    for u in edge[v]:
        if visited[u]:
            continue
        else:
            score[u]+=score[v]
            q.append(u)

for i in range(1, N+1):
    print(score[i], end=' ')

Measured memory_bytes: 89032
/*
 * ----------------------------------------------------------------------------
 *  (: Bismillahir Rahmanir Rahim :) 
 * File: /home/grim/Programming/Atcoder/Today/A_Don_t_be_late.cpp
 * Project: /home/grim/Programming/Atcoder/Today
 * Created Date: Saturday, August 29th 2020, 6:07:39 pm
 * Author: Grim Firefly :)
 * Author Mail : GrimFirefly1@gmail.com
 * -----
 * Last Modified: Sat Aug 29 2020
 * Modified By: Grim Firefly :)
 * -----
 *   ________        .__           ___________.__                  _____ .__          
 *  /  _____/_______ |__|  _____   \_   _____/|__|_______   ____ _/ ____\|  |  ___.__.
 * /   \  ___\_  __ \|  | /     \   |    __)  |  |\_  __ \_/ __ \\   __\ |  | <   |  |
 * \    \_\  \|  | \/|  ||  Y Y  \  |     \   |  | |  | \/\  ___/ |  |   |  |__\___  |
 *  \______  /|__|   |__||__|_|  /  \___  /   |__| |__|    \___  >|__|   |____// ____|
 *         \/                  \/       \/                     \/              \/     
 * 
 *           |\_|\
 *           | a_a\
 *           | | "]
 *       ____| '-\___
 *      /.----.___.-'\
 *     //        _    \
 *    //   .-. (GF)  /|
 *   |'|  /\:  .--  / \
 *  // |-/  \_/____/\/~|
 * |/  \ |  []_|_|_] \ |
 * | \  | \ |___   _\ ]_}
 * | |  '-' /   '.'  |
 * | |     /    /|:  | 
 * | |     |   / |:  /\
 * | |     /  /  |  /  \
 * | |    |  /  /  |    \
 * \ |    |/\/  |/|/\    \
 *  \|\ |\|  |  | / /\/\__\
 *   \ \| | /   | |__
 *        / |   |____)
 *        |_/
 * ----------------------------------------------------------------------------
 */

//Code Start
#include <bits/stdc++.h>
using namespace std;

//constant
#define PI acos(-1.0)
#define SZ 10000
#define mod 1000000007
//typedef
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
typedef unsigned un;
typedef pair<int, int> pii;
typedef vector<int> vi;

//Debug Setting up
#define watch(x) cout << (#x) << "=" << x << endl
#define watch2(x, y) cout << (#x) << "=" << x << " & " << (#y) << "=" << y << endl;
#define watchara(wow)     \
    for (auto x : wow)    \
    {                     \
        cout << x << " "; \
    }                     \
    cout << "\n"

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

//defining something
#define F first
#define S second

//Main Function Start From Here
void solve()
{
    double a, b, c;
    cin >> a >> b >> c;
    if (a / c <= b)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No\n";
    }
}

int main()
{
    fast_io;

    solve();

    return 0;
}

Measured memory_bytes: 3724
import heapq as hq
import math

def discount(price):
    return math.ceil(price / 2)

N,M = map(int,input().split())
A = list(map(lambda x: int(x)* -1,input().split()))
hq.heapify(A)

for _ in range(M):
    a = discount(hq.heappop(A))
    hq.heappush(A,a)

print(sum(A)* -1)

Measured memory_bytes: 14536
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>

using namespace std;

bool trace(
  const vector<vector<int>>& edges,
  vector<int>& paths,
  vector<bool>& visited
) {
  const auto last = paths[paths.size()-1];
  for (const auto& next: edges[last]) {
    if (visited[next]) continue;
    visited[next] = true;
    paths.push_back(next);
    if (trace(edges, paths, visited)) return true;
    paths.pop_back();
    visited[next] = false;
  }
  for (const auto& next: edges[paths[0]]) if (!visited[next]) return false;
  return true;
}


int main()
{
  int N, M;
  cin >> N >> M;
  vector<vector<int>> edges(N, vector<int>());
  vector<int> degrees(N, 0);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    edges[a].push_back(b);
    edges[b].push_back(a);
    ++degrees[a];
    ++degrees[b];
  }

  vector<pair<int, int>> orders;
  orders.reserve(N);
  for (int i = 0; i < degrees.size(); ++i) {
    orders.push_back(make_pair(degrees[i], i));
  }
  sort(orders.begin(), orders.end());

  for (const auto order: orders) {
    auto vertex = order.second;
    vector<int> paths;
    vector<bool> visited(N, false);
    paths.reserve(N);
    paths.push_back(vertex);
    visited[vertex] = true;
    if (trace(edges, paths, visited)) {
      cout << paths.size() << endl;
      for (int i = 0; i < paths.size(); ++i) {
        if (i) cout << " ";
        cout << (paths[i] + 1);
      }
      cout << endl;
      break;
    }
  }

  return 0;
}

Measured memory_bytes: 14080
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
int main(){
	string number;
	while(1){
		int sum=0;
		cin >> number;
		if(number=="0") break;
		for(int i=0;i<(int)number.size();i++){
			sum+=number[i]-'0';
		}
		cout << sum << endl;
	}
}
				


Measured memory_bytes: 3196
import sys 
import numpy as np   
import collections 

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


readline = sys.stdin.readline 

N = int(input())

fact = prime_factorize(N)
collections_fact = collections.Counter(fact)

pre_z = 0
duplicate_num = 1
counter = 0
for z in fact:
    if z != pre_z:
        N /= z
        counter += 1
        duplicate_num = 1
    else:
        duplicate_num += 1
        duplicate_z = z**duplicate_num 
        if N % duplicate_z == 0:
            N /= duplicate_z
            counter += 1
    pre_z = z 

print(counter)



Measured memory_bytes: 27116
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		int X = sc.nextInt();
		sc.close();

		if (X == 3 || X == 5 || X == 7) {
			out.println("YES");
		} else {
			out.println("NO");
		}

	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}


Measured memory_bytes: 20692
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

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

    int N;
    cin >> N;
    vector<int> F(N);
    REP(i, N) {
        int bit = 0;
        REP(j, 10) {
            int d;
            cin >> d;
            bit += d << j;
        }
        F[i] = bit;
    }
    vector<vector<int>> P(N, vector<int>(11));
    REP(i, N) {
        REP(j, 11) {
            cin >> P[i][j];
        }
    }
    int ans = -1e9;
    for (int bit = 1; bit < 1 << 10; bit++) {
        int tmp = 0;
        REP(i, N) {
            int cnt = __builtin_popcount(F[i] & bit);
            tmp += P[i][cnt];
        }
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}

Measured memory_bytes: 384
-- https://github.com/minoki/my-atcoder-solutions
import Data.Char (isSpace)
import Data.List (unfoldr)
import qualified Data.ByteString.Char8 as BS

main = do
  xs <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  print $ 1 + length (takeWhile (/= 0) xs)


Measured memory_bytes: 3736
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;

const ll INF = LONG_LONG_MAX;

int main() {
  ll N, M, L;

  cin >> N >> M >> L;

  vvll dist(N, vll(N, INF));
  vvll dist2(N, vll(N, INF));
  for (ll i = 0; i < N; i++) dist[i][i] = 0;
  for (ll i = 0; i < N; i++) dist2[i][i] = 0;
  for (ll i = 0; i < M; i++) {
    ll a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    dist[a][b] = dist[b][a] = c;
  }
  for (ll i = 0; i < N; i++) dist[i][i] = 0;

  for (ll k = 0; k < N; k++) {
    for (ll i = 0; i < N; i++) {
      for (ll j = 0; j < N; j++) {
        if (dist[i][k] != INF && dist[k][j] != INF)
          chmin(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  for (ll i = 0; i < N; i++) {
    for (ll j = 0; j < N; j++) {
      if (dist[i][j] <= L) dist2[i][j] = 1;
    }
  }

  for (ll k = 0; k < N; k++) {
    for (ll i = 0; i < N; i++) {
      for (ll j = 0; j < N; j++) {
        if (dist2[i][k] != INF && dist2[k][j] != INF)
          chmin(dist2[i][j], dist2[i][k] + dist2[k][j]);
      }
    }
  }

  ll Q;
  cin >> Q;
  for (ll i = 0; i < Q; i++) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    if (dist2[a][b] == INF)
      puts("-1");
    else
      cout << dist2[a][b] - 1 << endl;
  }

  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define cout16 cout << setprecision(16) 
#define rep(i,n) for(int i=0;i<n;i++ )
#define rep2(i,f,n) for(int i=f;i<n;i++ )
#define MAX(A) *max_element(A.begin(),A.end())
#define MIN(A) *min_element(A.begin(),A.end())
#define SORT(A) sort(A.begin(),A.end())
#define REV(A) reverse(A.begin(),A.end())
typedef long long int ll;
using vi = std::vector<int>;
using vvi = std::vector<std::vector<int>>;
using vll = std::vector<ll>;
using vvll = std::vector<std::vector<ll>>;
using P = std::pair<int,int>;
using vp = std::vector<P>;
using namespace std;
#define INF 1001001001
#define LL_INF 1001001001001001001
#define fi first
#define se second

int main(void) {
	int n = 5;
	vp p(n);
	rep(i,n){
		cin >> p[i].se;
		p[i].fi = p[i].se%10;
		if(p[i].fi==0) p[i].fi = 10;
	}
	SORT(p);
	int ans = p[0].se;
	rep2(i,1,n){
		p[i].se += 10-p[i].fi;
		ans += p[i].se;
	}
	cout << ans << endl;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define MAX_N 50000
#define INF 100000000
#define MOD 1000000007
#define RANK 1000000000
#define EPS 1e-10
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> IP;

int w, n;
int bit[MAX_N+1];
int x[MAX_N];
int sum[MAX_N+1];

int bsum(int i){
	int s = 0;
	while(i > 0){
		s += bit[i];
		i -= i&-i;
	}
	return s;
}

void add(int i){
	while(i <= n){
		bit[i]++;
		i += i&-i;
	}
}

bool check(int le){
    memset(bit,0,sizeof(bit));
    
    int prest = -1;
    int s, e, mid;
    int st, en;
    int v, q;
    
    for(int i = 1; i < n; i++){
        s = prest; e = i;
        while(e-s > 1){
            mid = (s+e)/2;
            if(sum[i+1]-sum[mid]-1 > w){
                s = mid;
            } else{
                e = mid;
            }
        }
        st = e;
        prest = st-1;
        if(i == n-1){
            en = i;
        } else{
            s = -1; e = i;
            while(e-s > 1){
                mid = (s+e)/2;
                if(w-sum[i+1]+sum[mid]+1 > (le-1)*(i-mid)){
                    e = mid;
                } else{
                    s = mid;
                }
            }
            en = s;
        }
        if(st > en) continue;
        if(st == 0) q = 1;
        else q = bsum(en)-bsum(st-1);
        if(q){
            add(i+1);
            if(i == n-1) return true;
        }
    }
    return false;
}

int solve(){
    rep(i,n) scanf("%d",x+i);
    rep(i,n){
        if(i == 0){
            sum[i+1] = x[i]+1;
        } else{
            sum[i+1] = sum[i]+x[i]+1;
        }
    }
    int ss = 0, ee = w, mid;
    while(ee-ss > 1){
        mid = (ss+ee)/2;
        if(check(mid)){
            ee = mid;
        } else{
            ss = mid;
        }
    }
    printf("%d\n",ee);
}

int main(){
    while(scanf("%d%d",&w,&n)){
        if(w == 0 && n == 0) break;
        solve();
    }
}

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

template <class T>
struct BIT {
	vector<T> data;
	BIT(ll n) {
		data.assign(n, 0);
	}

	T sum (ll i) {
		T res = 0;
		while (i > 0) {
			res += data[i];
			i -= i & -i;
		}
		return res;
	}

	void add(ll i, T x) {
		while (i < data.size()) {
			data[i] += x;
			i += i & -i;
		}
	}
};

int main() {
	ll N;
	cin >> N;
	vector<ll> a(N + 1);
	vector<ll> x(N);
	for (int i = 1; i <= N; ++i) { 
		cin >> a[i];
		x[i - 1] = a[i];
	}
	sort(x.begin(), x.end());
	x.erase(unique(x.begin(), x.end()), x.end());

	ll Mlen = (1 + N) * N / 2;
	ll Mlenc = (Mlen + 1) / 2;

	int l = 0, r = x.size();
	while (r - l > 1) {
		int mid = (r + l) / 2;

		vector<ll> d(N + 1, 0);
		for (int i = 1; i <= N; ++i) {
			if (a[i] >= x[mid]) { d[i] += d[i - 1] + 1; }
			else { d[i] += d[i - 1] - 1; }
		}

		BIT<ll> bit(2 * N + 2);
		ll inv = 0;
		for (int i = 0; i < N + 1; ++i) {
			inv += bit.sum(2 * N + 1) - bit.sum(d[i] + N + 1);
			bit.add(d[i] + N + 1, 1);
		}

		ll wl = (1 + N) * N / 2 - inv;
		if (wl >= Mlenc) { l = mid; }
		else { r = mid; }
	}

	cout << x[l] << endl;
	return 0;
}


Measured memory_bytes: 4192
s = input()
a = 0
z = 0
n = len(s)
for i in range(n):
    if s[i] == "A":
        a = i
        break
for i in range(n-1, -1, -1):
    if s[i] == "Z":
        z = i
        break

print(z-a+1)

Measured memory_bytes: 40048
n=int(input())
now=(0,0,0)
result=True
for i in range(n):
    t,a,b=[int(i) for i in input().split()]
    time=t-now[0]
    x=abs(a-now[1])
    y=abs(b-now[2])
    if (x+y-time)%2!=0 or (x+y)>time:
        result=False
    else:
        now=(t,a,b)
if result:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n;
int a[100100];

void solve() {
    sort(a, a+n);
    if (a[n-1] % 2 == 0) {
        int v = a[n-1] / 2;
        int c;
        int dif = inf;
        for (int i = 0; i < n-1; i++) {
            if (abs(a[i] - v) < dif) {
                dif = abs(a[i] - v);
                c = a[i];
            }
        }
        cout << a[n-1] << " " << c << endl;
    } else {
        int v0 = a[n-1] / 2, v1 = a[n-1] / 2 + 1;
        int c;
        int dif = inf;
        for (int i = 0; i < n-1; i++) {
            int v = min(abs(a[i] - v0), abs(a[i] - v1));
            if (v < dif) {
                dif = v;
                c = a[i];
            }
        }
        cout << a[n-1] << " " << c << endl;
    }
}

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

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

    input();
    solve();
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> Pi;
typedef unsigned long long ULL;
int gcd(int a,int b){if (b == 0) return a; return gcd(b , a%b);}
int lcm(int a, int b){ return a/gcd(a,b)*b;}
inline int read(){
    int f = 1, x = 0;char ch = getchar();
    while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
    while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}
const int maxn = 1e5 + 10;
int a[maxn];
int main(){
   // freopen("/Users/chutong/data.txt", "r", stdin);
    int H = read(),W = read();
    int h = read(),w = read();
    printf("%d\n",H*W-h*W-H*w+h*w);
    return 0;
}


Measured memory_bytes: 256
def resolve():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    if 1 not in A:
        print(-1)
        return
    sumA = 0
    try:
        i = 1
        while sumA + i <= N:
            sumA += A.index(i, (sumA + i - 1)) - (sumA + i - 1)
            i += 1
        print(sumA)
    except BaseException:
        sumA += N - (sumA + i - 1)
        print(sumA)


resolve()


Measured memory_bytes: 31608
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<math.h>
#include<bitset>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define LONG_INF 9223372036854775807
#define INF 1000000000LL
#define EPS 1e-10
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define dump(a) rep(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define all(v) v.begin(),v.end()
#define pb push_back

#define WA false
#define AC true

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

    int N, M, p, correct=0;
    string s;
    cin >> N >> M;
    vector<bool> submit(N+1, WA);
    vector<int> penalty(N+1, 0);
    rep(i, M){
        cin >> p >> s;
        if(submit[p]==WA && s=="WA") penalty[p]++;
        else if(submit[p]==WA && s=="AC"){
            submit[p]=AC;
            correct++;
        }
    }

    int spen = 0;
    for(int p=1; p<N+1; p++){
        if(submit[p]==WA) penalty[p]=0;
        spen += penalty[p];
    }

    cout << correct << " " << spen << endl;
    

    return 0;
}

Measured memory_bytes: 640
a=int(input())
b=list(map(int,input().split()))
c={}
for i in range(len(b)):
    try:
        c[b[i]]+=1
    except KeyError:
        c[b[i]]=1

    
for i in range(a):
    try:
        print(c[i+1])
    except KeyError:
        print(0)

Measured memory_bytes: 33472
def dfs(x, e, v)
    v[x] = true
    e[x].select{|i| !v[i]}.map{|i| dfs(i, e, v)}
end

n, m = gets.split.map(&:to_i)
ab = m.times.map{gets.split.map{|i| i.to_i-1}}
t = ab + ab.map{|i| [i.last, i.first]}
e = t.group_by(&:first).map{|k, h| [k, h.map(&:last)]}.sort{|a,b|a.first<=>b.first}.map(&:last)
ans = 0
ab.each do |a, b|
    e[a].delete(b)
    e[b].delete(a)
    v = Array.new(n, false)
    dfs(0, e, v)
    if v.count{|i|i} != n then
        ans += 1
    end
    e[a] << b
    e[b] << a
end
puts ans

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

struct edge{int to; ll cost;};
using P = pair<ll,int>;
const ll INF = 1e17;

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

void dijkstra(int n, int s, vector<vector<edge>>& g, vector<ll>& d){
  priority_queue<P,vector<P>,greater<P>> que;
  rep(i,n) d[i] = INF;
  d[s] = 0;
  que.push(P(0,s));
  while(!que.empty()){
    P p = que.top();
    que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(auto e : g[v]){
      if(d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

int main(){
  int h, w;
  cin >> h >> w;
  int sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  sx--; sy--; gx--; gy--;
  string s[h];
  rep(i,h) cin >> s[i];
  vector<vector<edge>> g(h*w);
  rep(i,h) {
    rep(j,w) {
      if(s[i][j] == '#') continue;
      rep(k,4) {
        int nx = i + dx[k], ny = j + dy[k];
        if(nx >= 0 and nx < h and ny >= 0 and ny < w and s[nx][ny] == '.') g[i*w+j].push_back(edge{nx*w+ny,0});
      }
      for(int x = -2; x <= 2; x++) {
        for(int y = -2; y <= 2; y++) {
          int nx = i + x, ny = j + y;
          if(nx >= 0 and nx < h and ny >= 0 and ny < w and s[nx][ny] == '.') g[i*w+j].push_back(edge{nx*w+ny,1});
        }
      }
    }
  }
  vector<ll> d(h*w);
  dijkstra(h*w,sx*w+sy,g,d);
  cout << (d[gx*w+gy] == INF ? -1 : d[gx*w+gy]);
  return 0;
}


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

template <typename T> T load() { T r; cin >> r; return r; }
template <typename T> vector<T> loadMany(int n) { vector<T> rs(n); generate(rs.begin(), rs.end(), &load<T>); return rs; }

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto n = load<int>();
	cout << n*n*n << '\n';
}

// yoyo them updated gcc


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

int main(){
    int n, m;
    while (1){
	vector<int> map, dice;
	int b;
	cin >> n >> m;
	if (n == 0 && m == 0) break;
	
	for (int i = 0; i < n; i++){
	    cin >> b;
	    map.push_back(b);
	}
	for (int i = 0; i < m; i++){
	    cin >> b;
	    dice.push_back(b);
	}
	int ans = 0, where = 0;
	for (int i = 0; i < m; i++){
	    where += dice[i];
	    where += map[where];
	    ans++;
	    if (where >= n-1) break;
	}
	cout << ans << endl;
    }
}

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

int main(int argc, char const *argv[]) {
    int N, D;
    cin >> N >> D;

    if (N%(2*D+1) == 0) {
        cout << N/(2*D+1) << endl;
    } else {
        cout << (N/(2*D+1))+1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var rdr = bufio.NewReaderSize(os.Stdin, 1000000)

func main() {
	n := nextInt()
	enmy := nextInts(n+1)
	helo := nextInts(n)

    cnt := 0
	for i, h := range helo {
        x := smaller(h, enmy[i])
        cnt += x
        h -= x
        x = smaller(h, enmy[i+1])
        cnt += x
        enmy[i+1] -= x
    }
    printInt(cnt)
}

func printInt(n int) {
    fmt.Println(n)
}

func next() (s string) {
    fmt.Scan(&s)
    return
}

func nextInt() (n int) {
    fmt.Scan(&n)
    return
}

func nextInts(n int) (arry []int) {
    arry = make([]int, n)
    for i:=0; i<n; i++ { fmt.Scan(&arry[i]) }
    return
}

func readLine() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, e := rdr.ReadLine()
		if e != nil {
			panic(e)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func nextSlice() []string {
	return strings.Split(readLine(), " ")
}

func atoi(a []string) (b []int) {
	b = make([]int, len(a))
	for i := range a {
		b[i], _ = strconv.Atoi(a[i])
	}
	return
}

func atof(a []string) (b []float64) {
	b = make([]float64, len(a))
	for i := range a {
		b[i], _ = strconv.ParseFloat(a[i], 64)
	}
	return
}

func scanSlice2(n int) (a []int, b []int) {
	a = make([]int, n)
	b = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}
	return
}

func scanFloatSlice2(n int) (a []float64, b []float64) {
	a = make([]float64, n)
	b = make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i], &b[i])
	}
	return
}

// ---------------------------------------------------

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func larger(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func smaller(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func sum(a []int) (ans int) {
	for i := range a {
		ans += a[i]
	}
	return
}

// ---------------------------------------------------

func yesOrNo(b bool) {
	if b {
		fmt.Println("Yes")
		return
	}
	fmt.Println("No")
}

func yesorNO(b bool) {
	if b {
		fmt.Println("YES")
		return
	}
	fmt.Println("NO")
}


Measured memory_bytes: 6016
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;

  REP(i, 9) {
    REP(j, 9) {
      if((i + 1) * (j + 1) == n) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<utility>
#include<stdbool.h>
using namespace std;
typedef long long ll;
#define N (1000000000+7)

int main(void) {
	ll x, y, ans = 1, a = 0;
	cin >> x >> y;
	a = x;
	while (true) {
		if (2*a <= y) {
			a *= 2;
			ans++;
		}
		else break;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k;
int h[100100];
int dp[100100];
int cost(int i,int j){
	return abs(h[i]-h[j]);
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>h[i];
	dp[1]=0;
	for(int i=2;i<=n;i++){
		dp[i]=2e9;
		for(int j=1;j<=k&&j<i;j++){
			dp[i]=min(dp[i],dp[i-j]+cost(i-j,i));
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}


Measured memory_bytes: 1024
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        E solver = new E();
        solver.solve(1, in, out);
        out.close();
    }

    static class E {
        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int H = in.nextInt();
            int N = in.nextInt();
            List<Magic> list = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                list.add(new Magic(in.nextInt(), in.nextInt()));
            }
            long ans = calc(H, list);
            out.println(ans);
        }

        private long calc(int H, List<Magic> list) {
            long[] dp = new long[H + 1];
            Arrays.fill(dp, (long) 1e16);
            dp[0] = 0;
            for (int i = 0; i <= H; i++) {
                for (Magic m : list) {
                    int a = Math.min(H, i + m.A);
                    dp[a] = Math.min(dp[a], dp[i] + m.B);
                }
            }
            return dp[H];
        }

        class Magic {
            int A;
            int B;

            Magic(int a, int b) {
                A = a;
                B = b;
            }

        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 21844
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll h, w;
	cin >> h >> w;
	vector<vector<char>> a(h, vector<char>(w));
	REP(i, h) REP(j, w) cin >> a[i][j];
	vector<vector<ll>> dp(h, vector<ll>(w, 0));
	for(ll i = h - 1; i >= 0; i--) for(ll j = w - 1; j >= 0; j--) {
		if(a[i][j] == '#') continue;
		if(i == h - 1 && j == w - 1) dp[i][j] = 1;
		if(i + 1 <= h - 1) dp[i][j] += dp[i + 1][j];
		if(j + 1 <= w - 1) dp[i][j] += dp[i][j + 1];
		dp[i][j] %= MOD;
	}
	cout << dp[0][0] << endl;
	return 0;
}

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


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define MAX pow(10,18)
typedef long long ll;

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

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#include <boost/foreach.hpp>
using namespace std;
#define ll long long
#define endl '\n'
#define rep(i, m, n) for (ll i = (ll)(m); i < (ll)(n); i++)
#define tr(it, c) for (iter(c) it = (c).begin(); it != (c).end(); it++)
#define PI 3.14159265358979323846
#define llinf LLONG_MAX
#define couttest cout << "test" << endl

void Main() {
  ll n, k;
  cin >> n >> k;
  ll a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);

  ll cnt = 0;
  ll L = -llinf, R = llinf;
  ll M;
  while (L + 1 != R) {
    M = (L + R) / 2;
    cnt = 0;
    rep(i, 0, n) {
      int l, r, m;
      l = i;
      r = n;
      if (a[i] < 0) {
        while (l + 1 != r) {
          m = (l + r) / 2;
          if (a[i] * a[m] <= M) {
            r = m;
          } else {
            l = m;
          }
        }
        cnt += n - r;
      } else {
        while (l + 1 != r) {
          m = (l + r) / 2;
          if (a[i] * a[m] <= M) {
            l = m;
          } else {
            r = m;
          }
        }
        cnt += l - i;
      }
    }
    if (cnt < k) {
      L = M;
    } else {
      R = M;
    }
  }

  cout << R << endl;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(NULL);
  Main();
  return 0;
}

Measured memory_bytes: 1792
/**
 * Dynamic Programming - Longest Common Subsequence
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int q = parseInt(br.readLine());
		for (int i = 0; i < q; i++) {
			String X = br.readLine();
			String Y = br.readLine();

			int[][] dp = new int[X.length() + 1][Y.length() + 1];
			int lcs = 0;
			for (int j = 1; j <= X.length(); j++) {
				for (int k = 1; k <= Y.length(); k++) {
					char x = X.charAt(j - 1);
					char y = Y.charAt(k - 1);
					if (x == y) {
						lcs = dp[j][k] = dp[j - 1][k - 1] + 1;
					} else {
						lcs = dp[j][k] = Math.max(dp[j][k - 1], dp[j - 1][k]);
					}
				}
			}
			System.out.println(lcs);
		}
	} //end main
}

Measured memory_bytes: 59772
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

using vll = vector<ll>;

void solve();

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

  solve();

  return 0;
}

#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)

#define inl(...)  \
  ll __VA_ARGS__; \
  in(__VA_ARGS__)

#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__);

void in() {}
template <typename T, class... U>
void in(T& t, U&... u) {
  cin >> t;
  in(u...);
}

void out() {
  cout << endl;
}
template <typename T, class... U>
void out(const T& t, const U&... u) {
  cout << t;
  if (sizeof...(u))
    cout << " ";
  out(u...);
}

#define rep(i, n) for (long long i = 0; i < n; i++)

void solve();
#ifndef ONLINE_JUDGE
#include "./lib.hpp"
#endif

void solve() {
  inl(H, W);

  ll res = 1LL << 62;
  for (int w = 1; w < W; w++) {
    vll S;
    S.push_back(H * w);

    ll w2 = (W - w) / 2;
    ll w3 = W - w - w2;
    S.push_back(H * w2);
    S.push_back(H * w3);
    sort(S.begin(), S.end());
    if (S.back() - S.front() < res)
      res = S.back() - S.front();

    S.clear();
    S.push_back(H * w);
    ll h2 = H / 2;
    ll h3 = H - h2;
    S.push_back(h2 * (W - w));
    S.push_back(h3 * (W - w));
    sort(S.begin(), S.end());
    if (S.back() - S.front() < res)
      res = S.back() - S.front();
  }

  swap(H, W);
  for (int w = 1; w < W; w++) {
    vll S;
    S.push_back(H * w);

    ll w2 = (W - w) / 2;
    ll w3 = W - w - w2;
    S.push_back(H * w2);
    S.push_back(H * w3);
    sort(S.begin(), S.end());
    if (S.back() - S.front() < res)
      res = S.back() - S.front();

    S.clear();
    S.push_back(H * w);
    ll h2 = H / 2;
    ll h3 = H - h2;
    S.push_back(h2 * (W - w));
    S.push_back(h3 * (W - w));
    sort(S.begin(), S.end());
    if (S.back() - S.front() < res)
      res = S.back() - S.front();
  }

  out(res);
}


Measured memory_bytes: 3568
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define p(s) cout<<(s)<<endl
#define REP(i,n,N) for(int i=n;i<N;i++)
#define RREP(i,n,N) for(int i=N-1;i>=n;i--)
#define CK(n,a,b) ((a)<=(n)&&(n)<(b))
#define F first
#define S second
typedef long long ll;
using namespace std;
const ll inf = 1e18;

int A,B,C,ans;
int main(){
    cin>>A>>B>>C;
    int mx=max({A,B,C});
    ans+=(mx-A)/2+(mx-B)/2+(mx-C)/2;
    A += (mx-A)/2*2;
    B += (mx-B)/2*2;
    C += (mx-C)/2*2;
    mx=max({A,B,C});
    int cnt=0;
    if(mx==A) cnt++;
    if(mx==B) cnt++;
    if(mx==C) cnt++;
    if(cnt<3)ans+=cnt;
    p(ans);
    return 0;
}


Measured memory_bytes: 256