akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

#define INF 1000000007
#define LINF 1000000000000000007

using namespace std;

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

int n, a[10000];

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	
	ll cnt = 0;
	for(int i = 0; i < n; i++){
		while(a[i] % 2 == 0){
			a[i] /= 2;
			cnt++;
		}
	}
	
	cout << cnt << endl;
	
	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, T;
    cin >> N >> T;

    vector<ll> A(N);

    REP(i, N){
        cin >> A[i];
    }

    ll minA = A[0];
    ll maxN = 0;
    
    ll ans = 0;
    for(ll i=1; i<N; i++){
        if(A[i] - minA == maxN){
            ans++;
        }
        if(A[i] -minA > maxN){
            ans = 1;
            maxN = A[i] -minA;
        }
        minA = min(minA, A[i]);
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
	string s, t;
	cin >> s >> t;
	
	int ans = t.length();
	for(int st=0; st<=s.length()-t.length(); st++){
		int diff = 0;
		for(int i=0; i<t.length(); i++){
			if(t[i] != s[st+i]) diff++;
		}
		ans = min(ans, diff);
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 3600
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

MOD = 10**9 + 7

S = [int(x) for x in readline().rstrip().decode('utf-8')]
LS = len(S)

dp0 = [0] * (LS+1) # そこまでフル
dp1 = [0] * (LS+1) # 以下任意
dp0[0] = 1

for i,x in enumerate(S,1):
    if x == 0:
        dp0[i] = dp0[i-1]
        dp1[i] = dp1[i-1] * 3
    else:
        dp0[i] = dp0[i-1] * 2
        dp1[i] = dp0[i-1] + dp1[i-1] * 3
    dp0[i] %= MOD
    dp1[i] %= MOD

answer = dp0[-1] + dp1[-1]
if answer >= MOD:
    answer -= MOD
print(answer)

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

int main()
{
  int h,w; cin >> h >> w;
  vector<string> a(h);
  rep(i, h) cin >> a[i];
  rep(i, w+2) cout << "#";
  cout << endl;

  rep(i, h) {
    cout << "#";
    cout << a[i];
    cout << "#";
    cout << endl;
  }

  rep(i, w+2) cout << "#";
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main(void){
  int a,b,c;
  scanf("%d%d%d",&a,&b,&c);
  if(a==b && b==c){
    printf("No");
    return 0;
  }
  if(a!=b && b!=c && a!=c){
    printf("No");
    return 0;
  }
  printf("Yes");
} 

Measured memory_bytes: 1724
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    int d = a / b;
    int r = a%b;
    double f = (double)a / (double)b;
    cout << d << ' ' << r<<' ';
    printf("%.9f\n", f);
}


Measured memory_bytes: 3256
#include <bits/stdc++.h>
// Hey! 僕の提出を見てくれてありがとう.
// ロボ子さん可愛いぞ！！！！！君もV沼にはまろう↓
// https://www.youtube.com/channel/UCDqI2jOz0weumE8s7paEk6g
using namespace std;
using ll = long long;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}//a,bの最大公約数(gcd)を求める
ll lcm(ll a,ll b){return abs(a*b)/gcd(a,b);}//a,bの最小公倍数(lcm)を求める
vector<ll> enum_div(ll n){vector<ll> ret;for(int i=1 ; i*i<=n ; i++){if(n%i == 0){ret.push_back(i);if(i!=1 && i*i!=n)ret.push_back(n/i);}}ret.push_back(n);return ret;}
//↑nの約数を求める
vector<bool> IsPrime; void sieve(size_t max){if(max+1 > IsPrime.size())IsPrime.resize(max+1,true);IsPrime[0] = false;IsPrime[1] = false;for(size_t i=2; i*i<=max; ++i)if(IsPrime[i])for(size_t j=2; i*j<=max; ++j)IsPrime[i*j] = false;}
//↑エラトステネスの篩で素数を求める
#define roundup(divisor,dividend) (divisor + (dividend - 1)) / dividend //切り上げ割り算
#define all(x) (x).begin(),(x).end() //xの初めから終わりまでのポインタ
#define size_t ll //size_tは自動でllに変換される
#define pb(x) push_back(x)
#define pri_queue priority_queue //優先度付きキュー
#define syo(x) fixed << setprecision(x) //iostreamで小数をx桁表示
//sortを降順にする時は greater<型>()
void solve(long long N, long long M, std::vector<long long> a, std::vector<long long> b){
  vector<pair<ll,ll>>x;
  for (int i = 0; i < M; i++) {
    x.pb(make_pair(b[i],a[i]));
  }
  sort(all(x));
  ll ans = 0,t = 0;
  for (int i = 0; i < M; i++) {
    if(t <= x[i].second){
      ans++;
      t = x[i].first;
    }
  }
  cout << ans << endl;
}

int main(){
    long long N;
	scanf("%lld",&N);
	long long M;
	scanf("%lld",&M);
	std::vector<long long> a(M);
	std::vector<long long> b(M);
	for(int i = 0 ; i < M ; i++){
		scanf("%lld",&a[i]);
		scanf("%lld",&b[i]);
	}
    solve(N, M, std::move(a), std::move(b));
}


Measured memory_bytes: 3956
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <math.h>
#include <cstdlib>
#include <cctype>
#include <random>

using namespace std;

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

   x -= a; 
   while (true) {
    if (x - b < 0) {
        break;
    } 
    x -= b;        
   }
    cout << x << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int bubble_sort(int A[], int N){
  int num = 0, i = 0, j;
  bool flag = true;
  while(flag) {
    flag = false;
    for(j = N-1; j > i; j--) {
      if(A[j] < A[j-1]) {
        swap(A[j], A[j-1]);
        flag = true;
        num++;
      }
    }
    i++;
  }

  return num;
}

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

  num = bubble_sort(A, N);

  for(i = 0; i < N; i++) {
    if(i) cout<<" ";
    cout<<A[i];
  }
  cout<<endl;
  cout<< num<< endl;

  return 0;
}



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
  int n,a[200000];
  ll sum=0,b[200000];
  cin>>n;
  a[0]=0;
  b[0]=0;
  ll mod=1e9+7;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    b[i]=(a[i-1]+b[i-1])%mod;
  }
  for(int i=1;i<=n;i++){
    sum=(sum+a[i]*b[i]%mod)%mod;
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 5944
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int num;
  cin>>num;
  num%=10;
  if(num==2||num==4||num==2||num==5||num==7||num==9)
    cout<<"hon";
  else if (num==0||num==1||num==6||num==8)
    cout<<"pon";
  else cout<<"bon";
  
 return 0; 
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> Es(N);
    while (M--){
        int a, b;
        cin >> a >> b;
        Es[a - 1].push_back(b - 1);
    }
    int right = N + 1;
    int count = 0;
    for (int i = 0; i < N; ++i){
        if (right == i){
            ++count;
            right = N + 1;
        }
        if (Es[i].size() > 0){
            right = min(right, *min_element(Es[i].begin(), Es[i].end()));
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 5760
use input::*;
use std::cmp::*;
use std::collections::HashSet;
use std::collections::VecDeque;
use std::io::*;
use std::num::*;
use std::str::*;

mod input {
    use super::*;
    pub fn read<T: FromStr>() -> T {
        stdin()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>()
            .parse::<T>()
            .ok()
            .unwrap()
    }
    pub fn string() -> String {
        read()
    }
    pub fn int() -> i64 {
        read()
    }
    pub fn char() -> char {
        read::<String>().pop().unwrap()
    }
    pub fn vecchar() -> Vec<char> {
        string().chars().collect()
    }
    pub fn vecint(n: i64) -> Vec<i64> {
        let mut vec = Vec::new();
        for i in 0..n {
            vec.push(int())
        }
        vec
    }
}
fn main() {
    let n = int() as usize;
    let s = vecchar();

    let mut indexes = Vec::new();
    for i in 0..10 {
        let mut v = VecDeque::new();
        for j in 0..n {
            if s[j] == i.to_string().chars().collect::<Vec<char>>()[0] {
                v.push_back(j)
            }
        }
        indexes.push(v);
    }

    let mut ans = 0;
    for k in 0..1000 {
        let k = format!("{:>03}", k).chars().collect::<Vec<char>>();
        let first = k[0] as usize - '0' as usize;
        let second = k[1] as usize - '0' as usize;
        let last = k[2] as usize - '0' as usize;
        let f = indexes[first].front();
        let l = indexes[last].back();
        ans += match (f, l) {
            (Some(ff), Some(ll)) => {
                let mut a = 0;
                for i in &indexes[second] {
                    if ff < i && i < ll {
                        a = 1;
                    }
                }
                a
            }
            _ => 0,
        };
    }
    println!("{}", ans)
}


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

using namespace std;

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	int c = 1, ans = 0;
	for (int i = 0; i < n; i++)
		if (a[i] != c) {
			ans++;
		} else {
			c++;
		}
	cout << (ans >= n ? -1 : ans) << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <cstdio>

int main()
{
  int n;
  scanf("%d", &n);
  int ans = 0;
  for (int i = 0; i < n; ++i)
  {
    int l, r;
    scanf("%d%d", &l, &r);
    ans += r - l + 1;
  }
  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
G=[]
E=[]
$<.map{|l|a,b=l.split.map &:to_i;b&&(E<<[a,b];(G[a]||=[])<<b;(G[b]||=[])<<a)}

puts [*1..$.,*E].map{|w|
  d=0
  w=*w
  f=w.size
  (
    *a=1
    z=*z,*w
    w.pop(1e9).map{|v|w=[*w,*b=G[v]-z];a<<b.size}
    d+=1
    f*=a.max
  )until w.empty?
  [d,f]
}.min

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


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

int main( void )
{
  string s;
  cin >> s;
  int atA, atZ;
  
  atA = INT_MAX;
  atZ = -INT_MAX;
  for( int i = 0; i < s.size(); i++ ) {
    if( s.at( i ) == 'A' && i < atA )
      atA = i;
    if( s.at( i ) == 'Z' && i > atZ )
      atZ = i;
  }

  cout << atZ - atA + 1 << endl;
}

Measured memory_bytes: 3716
W,H,N=map(int,input().split())
x1=0
x2=W
y1=0
y2=H
for i in range(N):
    x,y,a=map(int,input().split())
    if a==1:
        x1=max(x1,x)
    elif a==2:
        x2=min(x,x2)
    elif a==3:
        y1=max(y1,y)
    elif a==4:
        y2=min(y,y2)
if x2<x1 or y2<y1:
    print(0)
    exit()
xx=x2-x1
yy=y2-y1
print(xx*yy)

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
    vector<int> A(3, 0);
    int K; cin >> A[0] >> A[1] >> A[2] >> K;
    sort(A.begin(), A.end(), greater<int>());
    for (int i = 0; i < K; i++) {
        A[0] *= 2; sort(A.begin(), A.end(), greater<int>());
    }
    printf("%d\n", A[0] + A[1] + A[2]);
}


Measured memory_bytes: 3724
#![allow(unused_imports, unused_macros)]
use std::io::Write;
use std::collections::{VecDeque, HashMap, BinaryHeap, BTreeMap};

struct IO<'a> {
    sw: std::str::SplitWhitespace<'a>,
    out: Vec<u8>,
}

impl IO<'_> {
    pub fn read<T>(&mut self) -> T where
        T: std::str::FromStr,
        <T as std::str::FromStr>::Err: std::fmt::Debug {
        self.sw.next().unwrap().parse().unwrap()
    }
}

impl std::io::Write for IO<'_>  {
    fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
        std::io::Write::write(&mut self.out, buf)
    }
    fn flush(&mut self) -> std::io::Result<()> {
        std::io::Write::flush(&mut self.out)
    }
}

macro_rules! write_vec {
    ($io:expr, $v:tt) => {
        for (i, _v) in $v.iter().enumerate() {
            write!($io, "{:?}{}", _v, if i == $v.len()-1 {"\n"} else {" "})?;
        }
    };
}

macro_rules! write_rep {
    ($io:expr, $v:tt) => (
        write!($io, "{:?}\n", $v)?;
    );
    ($io:expr, $v:tt, $($arg:tt),+) => (
        write!($io, "{:?} ", $v)?;
        write_rep!($io, $($arg),+);
    );
}

fn main() -> Result<(), std::io::Error> {
    let mut buf = String::new();
    std::io::Read::read_to_string(&mut std::io::stdin(), &mut buf)?;
    let sw = buf.split_whitespace();
    let mut io = IO { sw, out: Vec::new() };
    solve(&mut io)?;
    std::io::Write::write_all(&mut std::io::stdout(), &io.out)?;
    Ok(())
}

// AtCoder Beginner Contest 178 F - Contrast
fn solve(io: &mut IO) -> Result<(), std::io::Error> {
    let n: usize = io.read();
    let mut a_cnt: Vec<usize> = vec![0; n+1];
    for _ in 0..n {
        let a: usize = io.read();
        a_cnt[a] += 1;
    }
    let mut b_vec: Vec<usize> = vec![0; n];
    let mut b_cnt: Vec<usize> = vec![0; n+1];
    
    for i in 0..n {
        let b = io.read();
        b_vec[i] = b;
        b_cnt[b] += 1;
    }
    for i in 1..=n {
        if a_cnt[i]+b_cnt[i] > n {
            writeln!(io, "No")?;
            return Ok(())
        }
    }
    let mut cap: usize = 0;
    for i in 0..n {
        a_cnt[i+1] += a_cnt[i];
        b_cnt[i+1] += b_cnt[i];
        cap = cap.max(b_cnt[i+1].saturating_sub(a_cnt[i]))
    }
    writeln!(io, "Yes")?;
    for i in 0..n {
        write!(io, "{}", b_vec[(i+cap)%n])?;
        if i == n-1 {
            writeln!(io)?;
        } else {
            write!(io, " ")?;
        }
    }
    Ok(())
}

Measured memory_bytes: 10884
N,M=input().split()
N=int(N)
M=int(M)
H= [int(x) for x in input().split()]
S = []
i=0
for i in range(M):
    A,B=input().split()
    A=int(A)
    B=int(B)
    if H[A-1]<=H[B-1]:
        S.append(A)
    if H[A-1]>=H[B-1]:
        S.append(B)
    i+=1
S=list(set(S))
b=N-len(S)
print(b)

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second
#define lwb lower_bound
#define upb upper_bound
#define all(x) (x).begin(),(x).end()

signed main() {
#ifdef _DEBUG
  // freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> H(n + 1);
  for (int i = 1; i <= n; i++) cin >> H[i];
  vector<vector<int>> adj(n + 1);
  for (int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int flag = 1;
    for (auto j : adj[i]) {
      if (H[j] >= H[i]) {
        flag = 0;
        break;
      }
    }
    ans += flag;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 9792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>

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

int iin() {
    int i;
    scanf("%d", &i);
    return i;
}

long long llin() {
    long long i;
    scanf("%lld", &i);
    return i;
}

double din() {
    double i;
    scanf("%lf", &i);
    return i;
}

char cin() {
    char c;
    scanf("%c", &c);
    return c;
}

void stin(char *s) {
    scanf("%s", s);
}

void iout(int i) {
    printf("%d\n", i);
}

void llout(long long i) {
    printf("%lld\n", i);
}

void dout(double i) {
    printf("%lf\n", i);
}

void cout(char c) {
    printf("%c\n", c);
}

void stout(char *s) {
    printf("%s\n", s);
}

int main() {
    int tmp1 = iin(), tmp2, max = 0, k, i;
    REP(i, 4) {
      tmp2 = iin();
      if (max < (tmp2 - tmp1)) max = tmp2 - tmp1;
    }
    k = iin();
    if (k < max) stout(":(");
    else stout("Yay!");
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    ll n, C;
    cin >> n >> C;

    vvl d(C, vl(C));
    rep(i, C) {
        rep(j, C) {
            cin >> d[i][j];
        }
    }

    vvl e(C, vl(3));  // e[x][y] : 色xで塗られている (i+j)%3 = y となるマスの個数
    rep(i, n) {
        rep(j, n) {
            ll c;
            cin >> c;
            c--;
            e[c][(i+j)%3]++;
        }
    }

    ll ans = INF;
    rep(x, C) {  // (i+j)%3 = 0 となるマスを色xで塗る
        rep(y, C) {  // (i+j)%3 = 1 となるマスを色yで塗る
            rep(z, C) {  // (i+j)%3 = 2 となるマスを色zで塗る
                if(x == y || y == z || z == x) {
                    continue;
                }
                ll now = 0;
                rep(u, C) {
                    now += d[u][x]*e[u][0];
                    now += d[u][y]*e[u][1];
                    now += d[u][z]*e[u][2];
                }
                chmin(ans, now);
            }
        }
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var ret = long.Parse(Console.ReadLine().Trim());
        for (int i = 1; i < n; i++)
        {
            var t =long.Parse(Console.ReadLine().Trim());
            ret =  Lcm(ret, t);
        }
        Console.WriteLine(ret);
    }
    public static long Lcm(long a, long b)
    {
        if (a < b) return Lcm(b, a);
        var ta = a;
        var tb = b;
        while (b != 0)
        {
            var wk = a % b;
            a = b;
            b = wk;
        }
        var ww = ta / a;
        return ww * tb;
    }
}

Measured memory_bytes: 13140
class UnionFind
  def initialize(n)
    @size = Array.new(n, 1)
    @rank = Array.new(n, 0)
    @parent = []

    (0..n).each do |i|
      @parent[i] = i
    end
  end

  def find(x)
    if @parent[x] == x
      x
    else
      @parent[x] = find(@parent[x])
    end
  end

  def unite(x, y)
    x = find(x)
    y = find(y)
    return if x == y

    if @rank[x] < @rank[y]
      @parent[x] = y
      @size[y] += @size[x]
    else
      @parent[y] = x
      @size[x] += @size[y]

      @rank[x] += 1 if @rank[x] == @rank[y]
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  def size(x)
    @size[find(x)]
  end
end

N, M = gets.split.map(&:to_i)
uf = UnionFind.new(N + 1)
M.times do
  a, b = gets.split.map(&:to_i)

  uf.unite(a, b)
end

puts (1..N).map { |x| uf.find(x) }.uniq.size - 1


Measured memory_bytes: 20944
#include <iostream>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a==b){
		cout<<"Draw";
	}
	else if(a==1){
		cout<<"Alice";
	}
	else if(b==1){
		cout<<"Bob";
	}
	else if(a>b){
		cout<<"Alice";		
	}
	else if(b>a){
		cout<<"Bob";
	}	
	return 0;
}

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

// int/long:		-2147483648 - 2147483648 (-2^31 <= int < 2^31)
// long/long long:	-9223372036854775808 - 9223372036854775807 (-2^63 <= long < 2^63)

#define	INF (1<<29)
//536870912

// lower_bound(A.begin(), A.end(), N)
// upper_bound(...

// bit: &/and, |/or, ^/xor, ~/not

#define	MOD 1000000007

int	main() {
	int N;
	cin >>N;
	vector<int> a(N);
	for (int i=0; i<N; i++)
		cin >>a.at(i);
	int ix=N-1;
	while (ix>=0) {
		cout <<a.at(ix) <<' ';
		ix -=2;
	}
	ix=-1-ix;
	while(ix<N) {
		cout <<a.at(ix) <<' ';
		ix +=2;
	}
	cout <<endl;
	return 0;
}



Measured memory_bytes: 2944
#include <stdio.h>

int main(void)
{
	int i=0, z, j, s, t;
	int n[100000];
	int count[100000];
	int dd=0;
	
	while (scanf("%d", &n[i]) != EOF){
		i++;
		dd++;
	}
	
	for (i=0; i<dd; i++){
		for (z=0; z<=9; z++){
			for (j=0; j<=9; j++){
				for (s=0; s<=9; s++){
					for (t=0; t<=9; t++){
						if ((z+j+s+t) == n[i]){
							count[i]++;
						}
					}
				}
			}
		}
	}
	
	for (i=0; i<dd; i++){
		printf("%d\n", count[i]);
	}
	
	return 0;
}

Measured memory_bytes: 604
#include<stdio.h>
#include<string.h>
#define N 1000

int Max(int a, int b){
	if(a >= b){
		return a;
	} else {
		return b;
	}
}

int lcs(char x[], char y[]){
	int i, j;
	int c[N+1][N+1];
	int m = strlen(x);
	int n = strlen(y);
	int max = 0;
	
	char x1[m+1] , y1[n+1];
	
	x1[0] = ' ';
	for(i = 1; i <= m; i++ ){
		x1[i]=x[i-1];
	}
	y1[0] = ' ';
	for(i = 1; i <= n; i++ ){
		y1[i]=y[i-1];
	}
	
	for(i = 0; i <= m; i++){
		c[i][0] = 0;
	}
	
	for(j = 1; j <= n; j++){
		c[0][j] = 0;
	}
	
	for(i = 1; i <= m; i++){
		for(j = 1; j <= n; j++){
			if(x1[i]==y1[j]){
				c[i][j] = c[i-1][j-1] + 1;
			} else {
				c[i][j] = Max(c[i-1][j], c[i][j-1]);
			}
			max = Max(max, c[i][j]);
		}
	}
	
	return max;
}

int main( void ){
	
	char s1[N] , s2[N];
	
	int n;
	
	scanf( "%d" , &n );
	
	for( int i = 0; i < n; i++ ){
		scanf( "%s" , s1 );
		scanf( "%s" , s2 );
		printf( "%d\n" , lcs(s1 , s2) );
	}
	
	return 0;
}


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

namespace Project {
    class Program {
        static void Main(string[] args) {
            var cr = new CR();

            var N = cr.i;
            var Y = cr.i;

            for (var z = 0; z <= N; z++) {
                for (var y = 0; y <= N - z; y++) {
                    var x_yen = Y - (5000 * y) - (1000 * z);
                    if (x_yen % 10000 != 0)continue;
                    var x = x_yen / 10000;
                    if (x + y + z == N) {
                        Console.WriteLine(x + " " + y + " " + z);
                        return;
                    }
                }
            }

            Console.WriteLine("-1 -1 -1");
        }

        private class CR {
            System.IO.TextReader _r;
            Queue<string> _d;
            public CR() { _r = Console.In; _d = new Queue<string>(); }
            string Read() {
                while (_d.Count == 0)
                    foreach (var v in _r.ReadLine().Split(' '))
                        if (v != "")_d.Enqueue(v);
                return _d.Dequeue();
            }
            public int i { get { return int.Parse(Read()); } }
            public string s { get { return Read(); } }
        }
    }
}

Measured memory_bytes: 11220
fn main() {
    let mut sc = cin();
    while sc.read() {
        let n: i64 = sc.next();
        let mut ans = 20;
        for i in 1..n+1 {
            if n < i*i {
                break;
            }
            if n % i != 0 {
                continue;
            }
            let a = format!("{}", i).len().into();
            let b = format!("{}", n / i).len();
            use std::cmp::*;
            ans = min(ans, max(a, b));
        }
        println!("{}", ans);
    }
}

#[allow(dead_code)]
fn cin() -> Scanner<std::io::Stdin> {
    Scanner::new(std::io::stdin())
}

#[allow(dead_code)]
pub struct Scanner<T> {
    buf: Vec<u8>,
    len: usize,
    idx: usize,
    next: Option<String>,
    reader: T,
}

#[allow(dead_code)]
impl<Reader: std::io::Read> Scanner<Reader> {
    fn new(r: Reader) -> Scanner<Reader> {
        Scanner {
            buf: vec![0; 8192],
            len: 0,
            idx: 0,
            next: None,
            reader: r,
        }
    }

    fn next<T: std::str::FromStr>(&mut self) -> T {
        self.wrapped::<T>().unwrap()
    }

    fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.next()).collect()
    }

    fn mat<T: std::str::FromStr>(&mut self, r: usize, c: usize) -> Vec<Vec<T>> {
        (0..r).map(|_| self.vec(c)).collect()
    }

    fn vec_char(&mut self) -> Vec<char> {
        self.read();
        self.next.take().unwrap().chars().collect()
    }

    fn mat_char(&mut self, r: usize) -> Vec<Vec<char>> {
        (0..r).map(|_| self.vec_char()).collect()
    }

    fn wrapped<T: std::str::FromStr>(&mut self) -> Option<T> {
        self.read();
        self.next.take().and_then(|s| s.parse::<T>().ok())
    }

    fn read(&mut self) -> bool {
        if self.next.is_some() {
            return true;
        }
        let mut s = String::with_capacity(16);
        while let Some(c) = self.get_char() {
            if !c.is_whitespace() {
                s.push(c);
            } else if !s.is_empty() {
                break;
            }
        }
        self.next = if !s.is_empty() { Some(s) } else { None };
        self.next.is_some()
    }

    fn get_char(&mut self) -> Option<char> {
        if self.idx == self.len {
            match self.reader.read(&mut self.buf[..]) {
                Ok(l) if l > 0 => {
                    self.idx = 0;
                    self.len = l;
                }
                _ => return None,
            }
        }
        self.idx += 1;
        Some(self.buf[self.idx - 1] as char)
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<iomanip>
#include<sstream>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

ll n, m, a[20], p[20], f[1 << 20];

int main(){
	cin >> n >> m;
	rep(i, n) cin >> a[i];
	rep(i, n) cin >> p[i];
	rep(i, 1 << n){
		ll t = 1;
		rep(j, n) if(i & 1 << j){
			ll u = a[j] / __gcd(t, a[j]);
			if(1.0 * t * u < 1.5e18) t *= u;
			else t = m + 1;
		}
		f[i] = m / t;
	}
	rep(i, n) rep(j, 1 << n) if(j & 1 << i) f[j] -= f[j ^ 1 << i];
	
	long double ans = 0;
	rep(i, 1 << n){
		long double e = 1;
		rep(j, n) e *= (i & 1 << j ? p[j] : 100 - p[j]) / 100.0l;
		ans += e * (m - abs(f[i]));
	}
	cout << fixed << setprecision(20) << ans << endl;
	
	return 0;
}

Measured memory_bytes: 9436
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define mem(a,b) memset(a,b,sizeof(a))
#define eb emplace_back
#define mp make_pair
using namespace std;
const int MAX_N=15;
vector<int> v[MAX_N];
vector<int> G[MAX_N];
set<int> kind;
map<int,int> color;
int n,m;
bool vis[MAX_N];
bool dfs(int x){
    vis[x]=true;
    for(auto y:v[x]){
        if(color[y]==1){
            return false;
        }
        color[y]=-1;
    }
    for(auto y:G[x]){
        if(color[y]==-1){
            return false;
        }
        kind.insert(y);
        color[y]=1;
        if(!vis[y])
            if(!dfs(y)){
                return false;
            }
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>m;
        for(int j=0;j<m;j++){
            int x,y;
            cin>>x>>y;
            x--;
            if(y==0)
                v[i].eb(x);
            else
                G[i].eb(x);
        }
    }
    int ans=0;
    for(int i=0;i<(1<<n);i++){
        kind.clear();
        color.clear();
        mem(vis,0);
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                kind.insert(j);
            }
        }
        bool flag=true;
        for(auto x:kind){
            if(!dfs(x)){
                flag=false;
                break;
            }
        }
        for(auto x:kind){
            for(auto y:v[x]){
                if(kind.count(y)){
                    flag=false;
                    break;
                }
            }
        }
        if(flag){
            ans=max(ans,(int)kind.size());
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
n, q = map(int, input().split())
s = input()
cum = [0] * (n + 1)
for i in range(2, n + 1):
    cum[i] = cum[i - 1]
    if s[i - 2:i] == "AC":
        cum[i] += 1

ans = [0] * q

for i in range(q):
    l, r = map(int, input().split())
    ans[i] = cum[r] - cum[l]
print(*ans, sep='\n')

Measured memory_bytes: 52056
#include <bits/stdc++.h>
using namespace std;
void solve()
{
   

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

    int dp[n];
    memset(dp,0,sizeof(dp));
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++)
    dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));

    cout<<dp[n-1]<<"\n";
     

}
void tool() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
}
int32_t main() {
	tool();
	
		solve();
	return 0;
}

Measured memory_bytes: 4336
#include <cstdio>

int main(){
    int N,M,X,Y;
    scanf("%d %d %d %d",&N,&M,&X,&Y);
    int x[N];
    for(int i = 0; i < N; i++){
        scanf("%d",&x[i]);
    }
    int y[M];
    for(int i = 0; i < M; i++){
        scanf("%d",&y[i]);
    }

    if(Y - X < 1){
        printf("War\n");
        return 0;
    }else{
        int max_x = x[0];
        for(int i = 0; i < N; i++){
            if(x[i] > max_x){
                max_x = x[i];
            }
        }
        int min_y = y[0];
        for(int i = 0; i < M; i++){
            if(y[i] < min_y){
                min_y = y[i];
            }
        }

        if(max_x < Y && X < min_y && max_x < min_y){
            printf("No War\n");
            return 0;
        }else{
            printf("War\n");
            return 0;
        }
    }

}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n;
  vector<string>s;
  cin >> n;
  bool flag = true;
  for(int i = 0; i < n; ++i) {
    string a;
    cin >> a;
    if(!i) s.push_back(a);
    else {
      int l = s.size();
      for(int j = 0; j < l; ++j) {
        if(a == s[j]) flag = false;
      }
      if(s[l - 1][s[l - 1].size() - 1] != a[0]) flag = false;
      if(flag) s.push_back(a);
    }
  }
  if(flag) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;
int main(){
    int N,M,X,Y;
    cin>>N>>M>>X>>Y;
    int max_value = -111;
    for(int i =0;i<N;i++){
        int x;
        cin>>x;
        max_value = max(max_value,x);
    }
    for(int i = 0;i<M;i++){
        int y;
        cin>>y;
        if(y<=max_value){
            cout<<"War"<<endl;
            return 0;
        }
    }
    if(max_value+1>X && max_value < Y){cout<<"No War"<<endl;}
    else{cout<<"War"<<endl;}
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int mu=998244353,N=200005;
long long dp[N][3][3][2];
char s[N];
int n,r,l;
int check(){
	int t=0;
	for (int i=1;i<l;i++) if (s[i]==s[i-1]) t++;
	if (t==l-1) return 2;
	if (t) return 0;
	return 1;
}
int main(){
	scanf("%s",s);
	l=strlen(s);
	if (l==1){
		puts("1");
		return 0;
	}
	if(l==2){
		if (s[0]==s[1]) puts("1");
		else puts("2");
		return 0;
	} 
	if (l==3){
		if (s[0]!=s[1] && s[1]!=s[2] && s[0]!=s[2])
		puts("3");
		else if (s[0]==s[1] && s[1]==s[2]) puts("1");
		else if (s[0]==s[1] && s[1]!=s[2]) puts("6");
		else if (s[0]!=s[1] && s[1]==s[2]) puts("6");
		else puts("7");
		return 0;
	}
	for (int i=0;i<l;i++) r=(r+s[i]-'0')%3;
	//printf("%d\n",r);
	int tt=check();
	if(tt==2) {
		puts("1");
		return 0;
	}
	dp[1][1][1][0]=dp[1][0][0][0]=dp[1][2][2][0]=1;
	for (int i=1;i<=l;i++)
		for(int j=0;j<=2;j++)//上一位 
			for (int k=0;k<=2;k++)//余数 
				for (int now=0;now<=2;now++)//这一位 
				{
					int t=(now+j)%3,rk=(k+now)%3;
					if (now==j) dp[i+1][now][rk][1]=(dp[i+1][now][rk][1]+dp[i][j][k][0]+dp[i][j][k][1])%mu;
					else {
						(dp[i+1][now][rk][1]+=dp[i][j][k][1])%=mu;
						(dp[i+1][now][rk][0]+=dp[i][j][k][0])%=mu;
					}
				}			
	printf("%d\n",(dp[l][1][r][1]+dp[l][0][r][1]+dp[l][2][r][1]+tt)%mu);	 
}

Measured memory_bytes: 28672
#include <bits/stdc++.h>
using namespace std;
#define ll                      long long int
#define pb                      push_back
#define MOD                     1000000007
#define inf                     3e18
#define ld                      long double
//#define mp                      make_pair
#define vpll                    vector<pair<ll,ll>>
#define sll                     set<ll>
#define usll                    unordered_set<ll>
#define vll                     vector<ll>
#define vld                     vector<ld>
#define vvll                    vector<vector<ll>>
#define vvld                    vector<vector<ld>>
#define pll                     pair<ll,ll>
#define vvpll                   vector<vector<pair<ll,ll>>>
#define pqll                    priority_queue<ll>
#define mll                     map<ll,ll>
#define mlc                     map<ll,char>
#define um                      unordered_map
#define umll                    um<ll,ll>
#define umlc                    um<ll,char>
#define umcl                    um<char,ll>
#define all(x)                  x.begin(),x.end()
#define fi                      first
#define se                      second
#define test                    ll Testcases;cin>>Testcases;while(Testcases--)
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define db(...)                 __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << " "<< name << " : " << arg1 <<'\n'; }
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...);
}

void inp_out()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
    #endif
}

int main()
{
	fastIO
	//inp_out();
	ll n,ans=0;
	cin>>n;
	for(ll i=1;i<=n;++i)
	{
		for(ll j=1;j<=n;++j)
		{
			ll val=__gcd(i,j);
			for(ll k=1;k<=n;++k)
			{
				ans+=__gcd(val,k);
			}
		}	

	}
	cout<<ans;
	return 0;
}



Measured memory_bytes: 3640
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = new int[3];
        for (int i = 0; i < arr.length; i++)
            arr[i] = sc.nextInt();
        Arrays.sort(arr);
        System.out.println((arr[2] - arr[1]) + (arr[1] - arr[0]));
    }
}


Measured memory_bytes: 35856
#include<stdio.h>

int main(void)
{

	int N, M;
	int A[200002];
	scanf("%d", &N);

	for (int i = 0;i < 200002;i++)
		A[i] = 0;
	for (int i = 2; i <= N;i++) {
		scanf("%d", &M);
		A[M]++;
	}

	for (int i = 1; i <= N;i++) {
		printf("%d\n", A[i]);
	}
	
	return 0;
}

Measured memory_bytes: 2504
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
	int n, counter = 0, i1=0, j1=0;
	vector <int> a, b;
	string s;
	cin >> n >> s;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'W') {
			a.push_back(i);
		}
		else {
			b.push_back(i);
		}
	}
	reverse(b.begin(), b.end());
	while (i1 < a.size() && j1 < b.size() && a[i1] < b[j1]) {
		counter++;
		i1++;
		j1++;
	}
	cout << counter;
}

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


int main(void) {
  long double threadthold = 1.0;
  for (int i = 0; i < 18; i++) {
    threadthold *= 10.0;
  }

  long long int n;
  scanf("%lld", &n);

  int zero_flag = 0;
  long double num[n];
  for (long long int i = 0; i < n; i++) {
    scanf(" %Lf", &num[i]);
    if (!num[i]) {
      zero_flag = 1;
      break;
    }
  }

  if (zero_flag) {
    printf("0\n");
  } else {
    int over_flag = 0;
    long double result = 1.0;
    for (long long int i = 0; i < n; i++) {
      result *= num[i];
      if (result > threadthold) {
        over_flag = 1;
        break;
      }
    }

    if (over_flag) printf("-1\n");
    else printf("%lld\n", (long long int) result);
  }

  return 0;
}


Measured memory_bytes: 3272
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define IFOR(i, m, n) for (ll i = n - 1; i >= m; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define FOREACH(x, a) for (auto&(x) : (a))
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())

int main() {
  ll n, k;
  cin >> n >> k;
  vector<ll> s(n + 1, 0);
  REP(i, n) {
    ll a;
    cin >> a;
    s[i + 1] = s[i] + a;
  }
  ll m = 0;
  REP(i, n - k + 1) { m = max(m, s[i + k] - s[i]); }

  double ans = (k + m) / 2.0;
  cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 1792
S = input()
n = len(S)

def isCyclic(S):
    n = len(S)
    #print(S)
    ans = True
    for i in range(n):
        if S[i] != S[n - i - 1]:
            ans = False
            break
    return ans

if isCyclic(S) and isCyclic(S[:(n - 1) // 2]) and isCyclic(S[(n + 1) // 2:]):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 38384
#include <stdio.h>

int main() {
	int year, month, day;
	scanf ("%d/%d/%d", &year, &month, &day);
	
	if (year != 2018){
		year = 2018;
	}
	else {
		year = 2018;
	}
	printf ("%d/%02d/%02d", year, month, day);
	return 0;
}

Measured memory_bytes: 1724
#include<bits/stdc++.h>                                                   //---------------------------------------------------------------
                                                                    
# define ll long long   
# define ld long double                                               
# define mod 1000000007                                                   
# define MAX 100005
# define pi 3.141592653589793238                                                                                  //shortcut keys
                                                                                
# define pb push_back                                                                     
# define mp make_pair                                                     
                                                                  
# define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);        //---------------------------------------------------------------                                       
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n],b[n],c[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
	}
	ll dp[3][n+1]={0};
	dp[0][1]=a[0];dp[1][1]=b[0];dp[2][1]=c[0];
	for(int i=1;i<n;i++)
	{
		dp[0][i+1]=max(dp[1][i]+a[i],dp[2][i]+a[i]);
		dp[1][i+1]=max(dp[0][i]+b[i],dp[2][i]+b[i]);
		dp[2][i+1]=max(dp[1][i]+c[i],dp[0][i]+c[i]);	
	}
	ll ans=0;
	for(int i=0;i<3;i++)
	ans=max(ans,dp[i][n]);
	cout<<ans;
}

Measured memory_bytes: 3712
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int a[10000],n,i,j;
	long min,max,sum=0;
	cin>>n;
	for(i=0;i<n;i++){
	cin>>a[i];
	sum=sum+a[i];
	}
	sort(a,a+n);
	for(j=0;j<n;j++){
	min=a[0];
	max=a[n-1];
	}
	cout<<min<<" "<<max<<" "<<sum<<endl;
return 0;
}


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

int main(){
  int n;
  int a;
  cin >> n;
  vector<int>vec(n);
  
  for(int i=1;i<n;i++){
    cin >> a;
    vec.at(a-1) += 1;
  }
  for(int i=0;i<n;i++){
    cout << vec.at(i) << endl;
  }
}

Measured memory_bytes: 4056
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(' ').map { it.toInt() }
    val b = readLine()!!.split(' ').map { it.toInt() }

    var cnt = 0L
    for (i in 0 until n) {
        if (a[i] < b[i]) cnt += (b[i] - a[i]) / 2
        if (a[i] > b[i]) cnt -= (a[i] - b[i])
    }
    println(if (cnt >= 0L) "Yes" else "No")
}


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

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

    string s;
	cin >> s;
	if(s[2] == s[3] && s[4] == s[5]) cout << "Yes";
    else cout << "No";
return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int main(){
  int h, w; cin >> h >> w;
  vector<string> a(h);
  for(int i=0; i<h; i++) cin >> a[i];
  vector<vector<long long>> d(h, vector<long long>(w, 0));
  d[0][0] = 1;
  for(int i=0; i<w; i++) {
    if (a[0][i] == '#') break;
    d[0][i] = 1;
  }
  for(int i=0; i<h; i++) {
    if (a[i][0] == '#') break;
    d[i][0] = 1;
  }
  for(int i=1; i<h; i++) {
    for(int j=1; j<w; j++) {
      if (a[i][j] == '#') continue;
      d[i][j] = (d[i-1][j] + d[i][j-1]) % mod;
    }
  }
  cout << d[h-1][w-1] << endl;


}

// EOF

Measured memory_bytes: 9216
S =[i+1 for i in xrange(13)]
H =[i+1 for i in xrange(13)]
C =[i+1 for i in xrange(13)]
D =[i+1 for i in xrange(13)]
#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

n = input()
for i in xrange(n):
    c, a = raw_input().split()
    if c == "S":
        for j in xrange(len(S)): 
            if S[j-1] == int(a):
             del S[j-1]
    elif c == "H":
        for j in xrange(len(H)): 
            if H[j-1] == int(a):
             del H[j-1]      
    elif c == "C":
        for j in xrange(len(C)): 
            if C[j-1] == int(a):
             del C[j-1]      
    elif c == "D":
        for j in xrange(len(D)): 
            if D[j-1] == int(a):
             del D[j-1]

for i in xrange(len(S)):
    print "S " + str(S[i])
    
for i in xrange(len(H)):
    print "H " + str(H[i])    
    
for i in xrange(len(C)):
    print "C " + str(C[i])    
    
for i in xrange(len(D)):
    print "D " + str(D[i])   

Measured memory_bytes: 6432
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
int w[15],l[15];
int a[15];
bool cmp(const int &a,const int &b)
{
	if(w[a] != w[b]) return w[a] > w[b];
	if(l[a] != l[b]) return l[a] < l[b];
	return a < b;
}
int main()
{
	while(1)
	{
		int n;
		cin >> n;
		if(n == 0) return 0;
		char h[15];
		fill(w,w+15,0);
		fill(l,l+15,0);
		for(int i=0;i<15;i++) a[i] = i;
		for(int i=0;i<n;i++)
		{
			scanf(" %c",&h[i]);
			for(int j=1;j<n;j++)
			{
				int x; cin >> x;
				if(x == 0) w[i]++;
				else if(x == 1) l[i]++;
			}
		}
		sort(a,a+n,cmp);
		for(int i=0;i<n;i++) cout << h[a[i]] << endl;
	}
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

#define DIV 1000000007
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	string s; cin >> s;
	ll n = s.size();
	vector<ll> alp(26);
	for (int i = 0; i < n; i++) {
		alp[s[i] - 'a']++;
	}

	ll ans = n * (n - 1) / 2 + 1;
	for (int i = 0; i < 26; i++) {
		ans -= alp[i] * (alp[i] - 1) / 2;
	}
	cout << ans << endl;
}


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

#define MAX_N 100000
typedef long long int ll;

ll dp[MAX_N];

int main() {
  int n, k, h[MAX_N];

  std::cin >> n >> k;
  for(int i = 0; i < n; ++i) {
    std::cin >> h[i];
  }

  dp[0] = 0;
  for(int i = 1; i < n; ++i) {
    dp[i] = dp[i - 1] + std::abs(h[i] - h[i - 1]);
    for(int j = 2; j <= k; ++j) {
      if(i - j >= 0) dp[i] = std::min(dp[i], dp[i - j] + std::abs(h[i] - h[i - j]));
    }
  }

  std::cout << dp[n - 1] << std::endl;
}


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

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

	vector<int> vec(n);
	rep(i, n) cin >> vec[i];

	int ans = 1e9;
	for (int i = 1; i <= 100; i++) {
		int sum = 0;
		for (int x : vec)
			sum += pow(x - i, 2);

		ans = min(ans, sum);
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}

class BIT{
  constructor(n){
    this.a = Array(n+1).fill(0);
  }
  add(val,id){
    for(var x=val,i=id;i<this.a.length;i+=i&-i)this.a[i]+=x;
  }
  get(id){
    for(var r=0,i=id;i;i-=i&-i)r+=this.a[i];
    return r;
  }
}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));

function main(){
  var n = next();
  var q = next();
  var c = nexts(n);
  var cc = xArray("[1]",n);
  var bit = new BIT(n+1);
  var map = new Set();
  for(var i = 0; i < n; i++){
    var t = --c[i];
    cc[t].push(i+1);
    if(!map.has(t))map.add(t), bit.add(1,i+1);
  }
  for(var i = 0; i < n; i++){
    cc[i].push(n+1);
  }
  var lr = Array(q);
  for(var i = 0; i < q; i++){
    lr[i] = [next(), next(), i];
  }
  lr.sort((a,b)=>a[0]-b[0]);
  var ans = Array(q), id = 1;
  for(var i = 0; i < q; i++){
    var [l,r,ix] = lr[i];
    while(id < l){
      var cr = c[id-1];
      var idx = ++cc[cr][0];
      bit.add(-1,id);
      bit.add(1,cc[cr][idx]);
      id++;
    }
    ans[ix] = bit.get(r);
  }
  return ans.join("\n");
}

Measured memory_bytes: 342412