akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner stdin=new Scanner(System.in);
		int H;
		int W;
		
		while(true){
			H=stdin.nextInt();
			W=stdin.nextInt();
			if(H==0 && W==0) {break;}
			for(int i=1;i<=H;i++){
				for(int j=1;j<=W;j++){				
					if((i%2)==1&&(j%2)==1 || (i%2)==0&&(j%2)==0 )System.out.print("#");
					else System.out.print(".");				
						}
			
				System.out.print("\n");
		}
		System.out.print("\n");
	}
	}
}



Measured memory_bytes: 37948
n = int(input())
a = list(map(int, input().split()))

exists_odd = False
result = 0
while not exists_odd:
    for i in range(n):
        if a[i] % 2 != 0:
            exists_odd = True

        a[i] //= 2

    if not exists_odd:
        result += 1

print(result)


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

//	vector
template<typename T>
vector<T> trialDivision(T a) {
	vector<T> res;
	T i = 2;
	while (i * i <= a) {
		if (a % i == 0) {
			a /= i;
			res.push_back(i);
		}
		else ++i;
	}
	if (a != 1) res.push_back(a);
	return res;
}

int main() {
	int n;
	cin >> n;
	cout << n << ':';
	for (int& i : trialDivision(n)) cout << ' ' << i;
	cout << endl;
}


Measured memory_bytes: 3140
// 3_codefestival2017final_c
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define INF (1e16)
#define MOD (1000000007)
typedef long long ll;

int func(int bit){
    int now = 0;
    int ans = 12;
    for(int i = 1; i <= 23; i++){
        if(bit & (1 << i)){
            ans = min(ans, i - now);
            now = i;
        }
    }
    ans = min(ans, 24 - now);
    return ans;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v(13);
    rep(i, 13){
        v[i] = 0;
    }
    v[0] = 1;
    rep(i, n){
        int d;
        cin >> d;
        v[d]++;
    }

    int ans = 0;

    rep(i, (1 << 24)){
        if((i & 1) == 0) continue;

        int a, b;
        int flag = 0;
        for(int j = 1; j <= 11; j++){
            if(i & (1 << j)) a = 1;
            else a = 0;

            if(i & (1 << (24 - j))) b = 1;
            else b = 0;

            if(a + b > v[j] || (a + b == 0 && v[j] > 0)){
                flag = 1;
                break;
            }
            if(a + b < v[j]){
                ans = max(ans, 0);
                flag = 1;
                break;
            }
        }
        if((i & (1 << 12)) && v[12] == 0){
            flag = 1;
        }
        if((i & (1 << 12)) == 0 && v[12] > 0){
            flag = 1;
        }

        if(v[0] > 1){
            flag = 1;
            ans = max(ans, 0);
        }
        if(v[12] > 1){
            flag = 1;
            ans = max(ans, 0);
        }

        if(flag) continue;

        ans = max(ans, func(i));
    }

    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N; cin >> N;
    FOR(X,1,50000){
        if ((int)floor((double)X*1.08) == N) { cout << X; return 0; }
    }
    cout << ":(";
}



Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
//priority_queue<long long, vector<long long>, greater<long long>> pq;

const double TL = 1.5 * CLOCKS_PER_SEC;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define clr(x, y) memset(x, y, sizeof(x))
#define forn(i, n) for (int i = 0; i < n; i++)
#define LL long long
const double pi = acos(-1.0);


LL a, b, c, k;

int main() {
  //auto start_clock = clock();
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif

  LL ans = 0;
  cin >> a >> b >> c >> k;
  ans += min(a, k);
  k -= a + b;
  if (k > 0) {
    ans -= k;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
inp1=int(input())
inp=list(map(int,input().split()))

ans=0

c=1
t1=0
t2=0

for i in inp:
    if c%2==1:
        t1=1
    if i%2==1:
        t2=1
    if t1==1 and t2==1:
        ans+=1
    
    t1=0
    t2=0
    c+=1

print(ans)

Measured memory_bytes: 9120
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int main(void)
{
  int in;
  int count[101]={0};
  int i;
  int max=0;

  while(scanf("%d",&in)!=EOF)
    count[in]++;

  for(i=1;i<=100;i++){
    if(max<count[i])
      max=count[i];
  }

  for(i=1;i<=100;i++){
    if(max==count[i])
      printf("%d\n",i);
  }

  return 0;
}

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

int main(){
    int n;
    cin >> n;
    map<string, int> memo;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        if(memo.count(s)){
            memo[s]++;
            //memo.at(s)++;
        }else{
            memo[s] = 1;
        }
    }

    int maxnum = -1;
    for(auto p: memo){
        if(p.second > maxnum){
            maxnum = p.second;
        }
    }

    for(auto p: memo){
        if(p.second == maxnum){
            cout << p.first << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 19232
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=j; i<=k; i++)
#define FFOR(i, j, k) for(int i=j; i<k; i++)
#define DFOR(i, j, k) for(int i=j; i>=k; i--)
#define bug(x) cerr<<#x<<" = "<<x<<'\n'
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "B"
int n, l, r;
int ans;
int main(){
    #ifdef Megumin
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Megumin
    read(n);
    FOR(i, 1, n){
        read(l);
        read(r);
        ans+=r-l+1;
    }
    writeln(ans);
}

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

using namespace std;

int main() {
   string s;

   cin >> s;

   int min = 1000;
   for(int i=0;i<=s.size()-3;i++){
        int tmp = (s[i] - '0')*100 + (s[i+1] - '0')*10 + (s[i+2] - '0');
        tmp = abs(753 - tmp);
        if(tmp < min){
            min = tmp;
        }
   }
   cout << min << endl;
    return 0;
}


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

typedef struct{
	int a, b, c, d, e, f;
}Dice;

int main(void)
{
	Dice dice;
	char h[101];
	int i, temp;
	
	scanf("%d %d %d %d %d %d", &dice.a, &dice.b, &dice.c, &dice.d, &dice.e, &dice.f);
	scanf("%s", h);
	
	int length = strlen(h);
	
	for(i=0;i<length;i++){
		if(h[i]=='N'){
			temp=dice.a; dice.a=dice.b; dice.b=dice.f; dice.f=dice.e; dice.e=temp;
		}
		else if(h[i]=='S'){
			temp=dice.a; dice.a=dice.e; dice.e=dice.f; dice.f=dice.b; dice.b=temp;
		}
		else if(h[i]=='W'){
			temp=dice.a; dice.a=dice.c; dice.c=dice.f; dice.f=dice.d; dice.d=temp;
		}
		else if(h[i]=='E'){
			temp=dice.a; dice.a=dice.d; dice.d=dice.f; dice.f=dice.c; dice.c=temp;
		}
	}
	
	printf("%d\n", dice.a);
	
	return 0;
}


Measured memory_bytes: 2128
#include <cstdio>

int main()
{
  char b;
  scanf("%c", &b);

  switch (b) {
    case 'A':
      printf("T");
      break;
    case 'C':
      printf("G");
      break;
    case 'G':
      printf("C");
      break;
    case 'T':
      printf("A");
      break;
  }

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
string s,t;

int main(void){
	cin >> s;
	cin >> t;
	bool flag=true;
	for(int i=0;i<s.size();i++){
		if(s[i]!=t[i]){
			flag=false;
		}
	}
	printf("%s\n",flag?"Yes":"No");
	return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() 
{
  ll n;
  cin>>n;
  ll a[n];
  for(ll i=0;i<n;i++) cin>>a[i];
  sort(a,a+n);
  ll c=0;
  for(ll i=0;i<n-2;i++)
  {
    for(ll j=i+1;j<n-1;j++)
    {
      for(ll k=j+1;k<n;k++)
      {
        if(a[i]+a[j]>a[k] && a[i]!=a[j] && a[i]!=a[k] && a[k]!=a[j])
        {
          //cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<'\n';
          c++;
        }
      }
    }
  }
    cout<<c;
  return 0;
}


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

using namespace std;

int main()
{
    long long n,a,b;
    cin >> n >> a >> b;
    if(a == 0){
        cout << 0 << endl;
        return 0;
    }
    long long ans = 0;
    long long s = n/(a+b);
    ans = a*s + min(a, (n-(a+b)*s));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int MOD = 1000000007;
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Arrays.sort(nums);
        
        boolean clear = true;
        int answer = 0;
        if (n % 2 == 0) {
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    if (nums[i] - 1 != i) {
                        clear = false;
                        break;
                    }
                } else {
                    if (nums[i] != i) {
                        clear = false;
                        break;
                    }
                }
            }
        } else {
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    if (nums[i] != i) {
                        clear = false;
                        break;
                    }
                } else {
                    if (nums[i] - 1 != i) {
                        clear = false;
                        break;
                    }
                }
            }
        }
        
        if (clear) {
            answer = powWithMOD(2, n/2, MOD);
        }
        
        System.out.println(answer);
    }
    
    public static int powWithMOD(int a, int b, int MOD) {
        int answer = 1;
        for (int i = 1; i <= b; i++) {
                answer = answer * a % MOD;
            }
        return answer;
    }
}


Measured memory_bytes: 48996
N = int(input())
il1 = input().split()
A = [int(i) for i in il1]

employee = list(A)
employee.append(0)

for i in range(N):
    employee[i] = 0

for i in A:
    employee[i-1] = employee[i-1] + 1

for i in employee:
    print(i)


Measured memory_bytes: 33908
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <bitset>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
// constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

template <typename F>
class fix_point: F {
public:
  explicit constexpr fix_point(F&& f) noexcept: F(std::forward<F>(f)) {}

  template <typename... Args>
  constexpr decltype(auto) operator ()(Args&&... args) const {
    return F::operator ()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
static inline constexpr decltype(auto) make_fix_point(F&& f) noexcept {
  return fix_point<F>{std::forward<F>(f)};
}

int main() {
  size_t h, w;
  scanf("%zu %zu", &h, &w);

  std::vector<std::string> s(h);
  for (auto& si: s) {
    char buf[32];
    scanf("%s", buf);
    si = buf;
  }

  std::vector<int> memo(21_zu*21*21*21, -1);

  auto enc = [&](size_t u, size_t b, size_t l, size_t r) {
    return u + 21 * (b + 21 * (l + 21 * r));
  };

  auto grundy = make_fix_point([&](auto dfs, size_t u, size_t b, size_t l, size_t r) -> int {
      if (u >= b || l >= r) return 0;

      int& res = memo[enc(u, b, l, r)];
      if (res != -1) return res;

      std::bitset<21*21*21*21> bs;
      bs.flip();
      for (size_t i = u; i < b; ++i)
        for (size_t j = l; j < r; ++j) {
          if (s[i][j] != '.') continue;
          int cur = 0;
          cur ^= dfs(u, i, l, j);
          cur ^= dfs(i+1, b, l, j);
          cur ^= dfs(u, i, j+1, r);
          cur ^= dfs(i+1, b, j+1, r);
          bs.reset(cur);
        }

      res = bs._Find_first();
      return res;
  })(0_zu, h, 0_zu, w);

  puts((grundy > 0)? "First": "Second");
}



Measured memory_bytes: 3828
#include <stdio.h>

int cnt ;
char s[3] ;

int main(void){
    
    scanf ("%s",s) ;
    
    if ( s[0]=='a' || s[1]=='a' || s[2]=='a' ){
        cnt++ ;
    }
    
    if ( s[0]=='b' || s[1]=='b' || s[2]=='b' ){
        cnt++ ;
    }
    
    if ( s[0]=='c' || s[1]=='c' || s[2]=='c' ){
        cnt++ ;
    }
    
    if ( cnt==3 ){
        printf ("Yes\n") ;
    } else {
        printf ("No\n") ;
    }

    return 0 ;
}


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

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define SORT(v, n) sort(v, v+n)
#define pb(a) push_back(a)
#define vi vector<int>
#define ddvi vector<vector<int>>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
// ここに処理を記述

	int r;
	cin >> r;

	cout << r*r << "\n";

return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <utility>
using namespace std;
int gcd (int a , int b){
    if(a<b)
        swap(a,b);
    return b==0 ? a:gcd(b,a%b);
}
int lcm (int a , int b){
    return a/gcd(a,b)*b;
}
int main (){
    int a = 0;
    int b = 0;
    while (scanf("%d%d",&a,&b)!=EOF&&(a>0&&b>0&&a<=2000000000&&b<=2000000000)&&lcm(a,b)<=2000000000)
        cout<<gcd(a,b)<<' '<<lcm(a,b)<<endl;
    return 0;
}



Measured memory_bytes: 3048
extern crate core;

use std::io::{self, Read};

#[macro_use]
mod parser {
    macro_rules! input {
    ($s:expr=>$($t:tt)*) => {
        let mut lines=$s.split("\n");
        $(
            line_parse!(lines,$t);
        )*
    };
    }

    macro_rules! line_parse {
    ($lines:expr,($($name:ident:$t:tt)*)) => {
        let mut line=$lines.next().unwrap().split_whitespace();
        $(value_def!(line,$name,$t);)*
    };

    //複数行
    ($lines:expr,{$n:expr;$name:ident:$t:tt}) => {
        values_def!($lines,$n,$name,$t);
    };
    }

    macro_rules! value_def {
        ($line:expr, $name:ident, $t:tt) => {
            let $name = value!($line, $t);
        };
    }

    macro_rules! values_def {
        ($lines:expr, $n:expr, $name:ident, $t:tt) => {
            let $name = {
                let mut vec = Vec::new();
                for i in 0..$n {
                    let mut next = $lines.next().unwrap().split_whitespace();
                    vec.push(value!(next, $t));
                }
                vec
            };
        };
    }

    macro_rules! value {
    //配列
    ($line:expr,[$t:tt]) => {
        $line.map(|x|{
        let mut iter=::std::iter::once(x);
        value!(iter,$t)
        }).collect::<Vec<_>>()
    };
    //タプル
    ($line:expr,($($t:tt),*)) => {
        ($(value!($line,$t),)*)
    };
    //文字列
    ($line:expr,#) => {
        $line.next().unwrap()
    };
    //単一値
    ($line:expr,$t:ty) => {
        $line.next().unwrap().parse::<$t>().unwrap()
    };
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let output = solve(input.trim().to_string());
    println!("{}", output);
}

fn f(mut plus: bool, list: &Vec<i64>) -> i64 {
    let mut sum = 0;
    let mut count = 0;
    for &x in list {
        sum += x;
        if !plus && sum >= 0 {
            let k = sum - -1;
            count += k;
            sum -= k;
        } else if plus && sum <= 0 {
            let k = 1 - sum;
            count += k;
            sum += k;
        }
        plus = !plus;
    }
    count
}

fn solve(input: String) -> String {
    input!(input=>(n:usize)(list:[i64]));
    std::cmp::min(f(true, &list), f(false, &list)).to_string()
}

pub fn sum_seq(v: Vec<i64>) -> Vec<i64> {
    v.into_iter()
        .scan(0, |state, x| {
            *state = *state + x;
            Some(*state)
        })
        .collect()
}

macro_rules! tests {
    ($($name:ident: $input:expr=>$output:expr,)*) => {
        mod tests {
            $(
                #[test]
                fn $name() {
                    assert_eq!($output.trim().to_string(),super::solve($input.trim().to_string()));
                }
            )*
        }
    }
}

tests! {
    test1: "4\n1 -3 1 0" => "4",
    test2: "5\n3 -6 4 -5 7" => "0",
    test3: "6\n-1 4 3 2 -5 4" => "8",
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int N,M,Q;
vi num[MX], cur;

void test(int x, int y) {
    vi a = num[x];
    // for (int i: a) cout << "ZZ " << i << "\n";
    reverse(all(a));
    // for (int i: a) cout << "ZZ " << i << "\n";
    int ind = 0;
    vi A;
    for (int i = 0; i < sz(a) && ind < sz(cur); ) {
        while (i < sz(a) && a[i] > cur[ind]) i ++;
        if (i < sz(a)) {
            // cout << "OH " << i << " " << a[i] << "\n";
            A.pb(a[i]);
            ind ++; i ++;
        }
    }
    /*for (int i: A) cout << i << " ";
    cout << "BAD\n";
    exit(0);*/
    if (sz(A) < N) {
        if (sz(cur) < N && x < y) {
            cout << "No";
            exit(0);
        }
    }
    
    cur = A;
    /*F0R(i,sz(a)) if (a[i] > b[i]) {
        cout << "No";
        exit(0);
    }*/
}

int getback(int x) {
    if (sz(num[x])) return num[x].back();
    return -x;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M >> Q;
    // FOR(i,1,M+1) num[i].pb(-i);
    FOR(i,1,Q+1) {
        int x; cin >> x;
        num[x].pb(i);
    }
    FOR(i,1,M+1) sort(all(num[i]));
    vi z; FOR(i,1,M+1) z.pb(i); 
    sort(all(z),[](int a, int b){ return getback(a) < getback(b); });
    
    cur = num[z[M-1]]; reverse(all(cur)); while (sz(cur) > N) cur.pop_back();
    // for (int k: cur) cout << "IH " << k << "\n";
    // for (int k: num[z[M-2]]) cout << "HI " << k << "\n";
    // exit(0);
    F0Rd(i,M-1) test(z[i],z[i+1]);
    cout << "Yes";
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS

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

using namespace std;

#define ll long long

int dp[100005][3];

int solve(int day,int n,vector<int> arr[],int flag)
{
	int maxi=0;
	if(day==n)
		return 0;
	if(dp[day][flag]!=-1)
		return dp[day][flag];
	if(flag==0)
	{
		maxi=max(maxi,arr[day][0]+solve(day+1,n,arr,1));
		maxi=max(maxi,arr[day][1]+solve(day+1,n,arr,2));
		maxi=max(maxi,arr[day][2]+solve(day+1,n,arr,3));
	}
	else if(flag==1)
	{
		maxi=max(maxi,arr[day][1]+solve(day+1,n,arr,2));
		maxi=max(maxi,arr[day][2]+solve(day+1,n,arr,3));
	}
	else if(flag==2)
	{
		maxi=max(maxi,arr[day][0]+solve(day+1,n,arr,1));
		maxi=max(maxi,arr[day][2]+solve(day+1,n,arr,3));
	}
	else
	{
		maxi=max(maxi,arr[day][0]+solve(day+1,n,arr,1));
		maxi=max(maxi,arr[day][1]+solve(day+1,n,arr,2));
	}
	dp[day][flag]=maxi;
	return maxi;
}

int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif // ONLINE_JUDGE
	int n;
	cin>>n;
	vector<int> arr[n];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<3;j++)
		{
			int temp;
			cin>>temp;
			arr[i].push_back(temp);
		}
	}
	for(int i=0;i<100005;i++)
	{
		for(int j=0;j<3;j++)
			dp[i][j]=-1;
	}
	cout<<solve(0,n,arr,0);
}

Measured memory_bytes: 19528
#include<stdio.h>

int main(){
  int a;
  int n,i;
  int flag = 0;

  scanf("%d", &n);

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

    if(a % 2 == 0){
      if(a % 3 != 0 && a % 5 != 0) flag = 1;
    }
  }

  if(flag == 1) printf("DENIED\n");

  else printf("APPROVED\n");
  
  return 0;
}

Measured memory_bytes: 128
N, M = map(int, input().split())
cnt = [0]*N
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        cnt[B] += 1
    elif B == N:
        cnt[A] += 1

if 2 in cnt:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 4596
K,A,B=map(int,input().split())
if B-A<=2:
  print(K+1)
else:
  if A-1>=K:
    print(K+1)
  else:
    if (K-(A-1))%2:
      print(A+1+(B-A)*((K-A)//2))
    else:
      print(A+(B-A)*((K-A+1)//2))
  

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

int main() {
int N , M , C , count ,ans;
cin >> N >> M >> C;
vector<int> B(M);
vector<vector<int>> A(N, vector<int>(M));
count = 0;
ans = 0;
for (int i = 0; i < M ; i++){
  cin >> B[i];
}
for (int j = 0; j < N ; j++){
  for (int k = 0; k < M; k++){
    cin >> A[j][k];
    count += A[j][k] * B[k];
  }
  if (count + C > 0){
    ans++;
  }
  count = 0; 
}
cout << ans << endl;

}


Measured memory_bytes: 256
#include <iostream>
    using namespace std;
     
    int main(){
        int n; cin>>n;
        int arr[n];
        for(int i=0; i<n; i++){
            cin>>arr[i];
        }
        for(int i =0; i<n; i++){
            if(arr[i]%2==0 && arr[i]%3!=0 && arr[i]%5!=0){
                cout<<"DENIED"<<endl;
                return 0;
            }
        }
        cout<<"APPROVED"<<endl;
        return 0;
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <string>
#include <cmath>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<ll> vll;
 
#define all(v) v.begin(),v.end()
#define test() int t;cin>>t;while(t--) 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first
#define ss second
const ll mod = (ll)1e9 + 7;
ll power(ll x, ll a)
{
    if(a==0)return(1);
    ll z  = power(x, a/2);
    z = (z * z)%mod;
    if(a%2)z = (z * x)%mod;
    return(z);
}
int main()
{
    ll n;
    cin>>n;
    ll ans = (power((ll) 10, n) -2*power((ll) 9, n) + power((ll) 8, n))%mod;
    if(ans<0)ans+=mod;
    cout<<ans<<endl;
}


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

using ll    = long long;
using ull   = unsigned long long;
using veci  = vector<int>;
using vecll = vector<ll>;
#define EPS (1e-7)
#define INF (1e9)
#define PI  (acos(-1))
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define REP(i,n) for(int i= 0;i<(int)(n);++i)
#define pb push_back

veci enum_div(int n){
	veci ret;
	ret.pb(1);
	for(int i=1;i*i<n;i++){
		if(n%i==0){
			ret.pb(i);
			if(i != n/i){ret.pb(n/i);}
		}
	}
	ret.pb(n);
	return ret;
}
int gcb(int a,int b){return ((b == 0)? a : gcb(b,a%b));}
int gcd(int a,int b){return (a*b) / gcb(a,b);}

int main(){
	int n,m,x,y;
	veci nx,ny;
	string ans = "War";
	cin >> n >> m >> x >> y;
	REP(i,n){
		int tmp;
		cin >> tmp;
		nx.pb(tmp);
	}
	REP(i,m){
		int tmp;
		cin >> tmp;
		ny.pb(tmp);
	}
	sort(nx.begin(),nx.end());
	sort(ny.begin(),ny.end());
	FOR(i,-100,101){
		if(i > x && i <= y && nx.back() < i && ny.front() >= i){
			ans = "No War";
			break;
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main()
{
    ll N,K,p[1000],sum=0;
    cin >> N >>K;
    REP(i,N){
        cin >> p[i];
    }
    sort(p,p+N);
    REP(i,K){
        sum+=p[i];
    }
    cout << sum << endl;
    return 0;  
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>

int main(){
  int N; cin >> N;
  int L[N]; rep(i,N) cin >> L[i];
  sort(L,L+N);

  int cnt = 0;
  for (int i=0;i<N-2;i++){
    for (int j=i+1;j<N-1;j++){
      int k = lower_bound(L+j+1,L+N,L[i]+L[j]) - L;
      cnt += k-1-j;
    }
  }
  cout << cnt << endl;




  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 3612
using System;
using System.Collections.Generic;
using static System.Console;
using System.Linq;


class Program
{
    static bool isUsedAll(List<int> value) {
        bool[] result = { false, false, false };
        foreach(int x in value) {
            result[x] = true;
        }
        return result[0] && result[1] && result[2];
    }

    static int[] sins = { 3, 5, 7 };

    static int Result_Count = 0;
    static int N = 0;

    static void DFS(int target_depth,int depth,List<int> value) {
        if(target_depth == depth) {
            if (!isUsedAll(value)) return;
            long Val = 0;
            for(int c = 0;c < value.Count; c++) {
                Val += sins[value[c]] * (int)Math.Pow(10, c);
            }
            if (Val <= N && Val >= 0) {
                Result_Count++;
            }
            return;
        }
        for(int i = 0;i < 3; i++) {
            List<int> clone = new List<int>(value.ToArray());
            clone.Add(i);
            DFS(target_depth, depth + 1, clone);
        }
    }

    static void Main(string[] Args) {
        N = Int32.Parse(ReadLine());

        for(int Depth = 1 ; Depth <= 10; Depth++) {
            DFS(Depth, 0, new List<int>());
        }

        WriteLine(Result_Count);

        ReadLine();
    }
}

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

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int N, W;
int v[101], w[101];
int dp[101][10001];

int rec(int idx, int cap) {
    if (dp[idx][cap] >= 0) return dp[idx][cap];
    int ret;
    if (idx >= N) {
        ret = 0;
    }
    else if (cap < w[idx]) {
        ret = rec(idx+1, cap);
    }
    else {
        ret = max(rec(idx+1, cap), rec(idx+1, cap-w[idx])+v[idx]);
    }
    return (dp[idx][cap] = ret);
}

int main() {
    cin >> N >> W;
    rep(i, N) {
        cin >> v[i] >> w[i];
    }
    fill(dp[0], dp[N], -1);
    cout << rec(0, W) << endl;
    return 0;
}



Measured memory_bytes: 6996
void call(int n)
{
    int i = 1;
    int x;
 
    do {
        x = i;
        if (x % 3 == 0) {
            printf(" %d", i);
        }
        else {
            do {
                if (x % 10 == 3) {
                    printf(" %d", i);
                    x = 0;
                }
                else x /= 10;
            } while (x);
        }
    } while (++i <= n);
    putchar('\n');
}
 
#if 1
int main()
{
    int n;
 
    scanf("%d", &n);
    call(n);
    return 0;
}
#endif


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

using namespace std;

string a[1010];
long long dp[1010][1010];
long long mod = 1e9 + 7;
int main()
{
    int n , m;
    cin >> n >> m;
    for(int i = 0 ; i < n ; i++)
        cin >> a[i];

    dp[n-1][m-1] = 1;
    for(int i = n-1 ; i >= 0 ; i--)
        for(int j = m-1 ; j >= 0 ; j--)
            dp[i][j] += ((i+1 < n && a[i+1][j] == '.'? dp[i+1][j]%mod : 0) + (j+1 < m && a[i][j+1] == '.'? dp[i][j+1]%mod : 0))%mod;
    cout << dp[0][0] << '\n';
    return 0;
}


Measured memory_bytes: 9216
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <tuple>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <random>
#include <queue>
#include <deque>
#include <iterator>
#include <map>
#include <functional>
#include <numeric>
using namespace std;
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define pb(a) push_back(a)
#define llong long long
#define INF 1145141919
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
int dy[] = { 1, 0, -1, 0 };
int dx[] = { 0, 1, 0, -1 };
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }


int a[3][3];
bool b[3][3];

int main() {
	int n;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (a[j][k] == tmp) {
					b[j][k] = 1;
				}
			}
		}
	}
	int flg = 0;
	for (int i = 0; i < 3; i++) {
		if (b[i][0] == 1 && b[i][1] == 1 && b[i][2] == 1) {
			cout << "Yes" << endl;
			flg = 1;
			break;
		}else if (b[0][i] == 1 && b[1][i] == 1 && b[2][i] == 1) {
			cout << "Yes" << endl;
			flg = 1;
			break;
		}
	}
	if (flg == 0 && (b[0][0] == 1 && b[1][1] == 1 && b[2][2] == 1 || b[0][2] == 1 && b[1][1] == 1 && b[2][0] == 1)) {
		cout << "Yes" << endl;
		flg = 1;
	}
	if (flg == 0) {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
 
int main(void){
    int i,j,k,l;
    scanf("%d %d %d %d", &i,&j,&k,&l);
    while(1){
    k-=j;
    if(k<1){printf("Yes");return 0;}
    i-=l;
    if(i<1){printf("No");return 0;}
    }
  return 0;
}

Measured memory_bytes: 1736
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<deque>
#include<map>
#include<set>

using namespace std;

long Q, H, S, D, N;
long n[4], *c[4] = {&Q, &H, &S, &D};

int input(){
  cin >> Q >> H >> S >> D;
  cin >> N;
  return 0;
}

int main(){
  input();
  
  if( 2 * Q < H ){ H = 2 * Q; }
  if( 2 * H < S ){ S = 2 * H; }
  if( 2 * S < D ){ D = 2 * S; }
  long C = 4 * N, ret = 0;
  long w[4] = {1, 2, 4, 8};
  for( int i = 3; i>= 0; i-- ){
	if( *c[i] <= 0 ){ continue; }
	n[i] = C / w[i];
	ret += n[i] * *c[i];
	C -= n[i] * w[i];
  }
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 256
// In the name of God

#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline bool smin(T &a, const T &b)   { return a > b ? a = b : a;    }
template<typename T> inline bool smax(T &a, const T &b)   { return a < b ? a = b : a;    }

typedef long long LL;

const int N = (int) 0, mod = (int) 0;
int mark[26];
int main() {
	string s;
	cin >> s;
	if ((int) s.size() == 26) {
	for (int j = (int) s.size() - 1; j >= 0; --j) {
		memset(mark, 0, sizeof mark);	
		for (int i = 0; i < j; ++i) mark[s[i] - 'a'] = 1;
		int nxt = s[j] - 'a' + 1;
		while (nxt < 26 && mark[nxt]) ++nxt;
		if (nxt == 26) continue;
		string t = "";
		for (int i = 0; i < j; ++i) t += s[i];
		t += char(nxt + 'a');
		mark[nxt] = 1;
		cout << t << endl;
		return 0;
	}
	} else {
		for (int i = 0; i < (int) s.size(); ++i) mark[s[i] - 'a'] = 1;
		int nxt = 0;
		while (mark[nxt]) ++nxt;
		s += char(nxt + 'a');
		cout << s << endl;
		return 0;
	}
	cout << -1 << endl;
}



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

using namespace std;

int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    int n,k,h,ans=0;
    cin>>n>>k;
    while(n--)
    {
        cin>>h;
        if(h>=k) ans++;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 256
import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.List;
	import java.util.Map;
	import java.util.Map.Entry;
	import java.util.PriorityQueue;
	import java.util.Queue;
	import java.util.Scanner;
	import java.util.Set;

	public class Main{

		public static void main(String[] args) {

			Scanner scanner = new Scanner(System.in);
			String[] t = scanner.nextLine().split(" ");
			long w = Long.parseLong(t[0]);
			long h = Long.parseLong(t[1]);
			double m = w * h / 2.0;
			long x = Long.parseLong(t[2]);
			long y = Long.parseLong(t[3]);

			int ans = w == x * 2 && h == y * 2 ? 1 : 0;

			System.out.println(m + " " + ans);
		}
	}

Measured memory_bytes: 38904
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)

// https://ei1333.github.io/algorithm/cumulative-sum2d.html
template <class T> struct CumulativeSum2D {
    vector<vector<T>> data;

    CumulativeSum2D(int W, int H) : data(W + 1, vector<T>(H + 1, 0)) {}

    void add(int x, int y, T z) {
        ++x, ++y;
        if (x >= data.size() || y >= data[0].size())
            return;
        data[x][y] += z;
    }

    void build() {
        FOR(i, 1, data.size()) FOR(j, 1, data.size()) {
            data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
        }
    }

    T query(int sx, int sy, int gx, int gy) {
        return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
    }

    void print() {
        for (auto &x : data) {
            for (auto &y : x) {
                cout << y << " ";
            }
            cout << endl;
        }
    }
};

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    char c;
    int n, k, x, y;
    cin >> n >> k;
    CumulativeSum2D<int> s(k * 2, k * 2);
    REP(i, n) {
        cin >> x >> y >> c;
        if (c == 'W') {
            y += k;
        }
        y %= 2 * k;
        if (y >= k) {
            y -= k;
            x += k;
        }
        x %= 2 * k;
        // 上半分の黒色エリア
        s.add(x, y, 1);
        // 下半分の黒色エリア
        s.add((x + k) % (2 * k), y + k, 1);
    }
    // 二次元累積和
    s.build();
    // s.print();
    int maxv = 0;
    REP(x, k) REP(y, k) {
        int t = s.query(x, y, x + k, y + k);
        // 今までの最大値、今回の黒色の数、白色の数
        maxv = max({maxv, t, n - t});
    }
    cout << maxv << endl;
    return 0;
}


Measured memory_bytes: 16000
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

vector<ll> GetDivisors(ll n) {
  vector<ll> ret;
  for (ll d = 1; d * d <= n; ++d) {
    if (n % d == 0) {
      ret.push_back(d);
      if (n / d != d) ret.push_back(n / d);
    }
  }
  return ret;
}

int main() {
  ll N;
  cin >> N;
  
  int count = 0;
  vector<ll> divisors;
  
  divisors = GetDivisors(N - 1);
  count += divisors.size() - 1;  // exclude 1

  divisors = GetDivisors(N);
  for (auto K : divisors) {
    if (K == 1) continue;
    ll x = N;
    while (x % K == 0) {
      x /= K;
    }
    if (x % K == 1) ++count;
  }
  
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ran 111111
int n;
vector<int> e[ran];
int dep[ran];
bool cmp(int x,int y){
	return dep[x] < dep[y];
}
void dfs(int x){
	dep[x] = 0;
	int w = e[x].size();
	for(int i=0; i<w; i++)
		dfs(e[x][i]);
	sort(e[x].begin(),e[x].end(),cmp);
	for(int i=1; i<=w; i++)
		dep[x] = max(dep[x], dep[e[x][w-i]] + i);
}
int main(){
	scanf("%d",&n);
	for(int i=2; i<=n; i++){
		int x;
		scanf("%d",&x);
		e[x].push_back(i);
	}
	dfs(1);
	printf("%d\n",dep[1]);
	return 0;
}


Measured memory_bytes: 14208
#include <cstdio>
#include <stack>
#include <set>
#include <cmath>
#include <map>
#include <time.h>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <memory.h>
#include <cstdlib>
#include <queue>
#include <iomanip>
#define P pair<int, int>
#define LL long long
#define LD long double
#define PLL pair<LL, LL>
#define mset(a, b) memset(a, b, sizeof(a))
#define PI acos(-1.0)
#define random(x) rand() % x
using namespace std;
const int inf = 0x3f3f3f3f;
const LL __64inf = 0x3f3f3f3f3f3f3f3f;
const int MAX = 1e5 + 5;
const int Mod = 1e9 + 7;

int main()
{
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i = 0; i < n; i++)
        cin >> A[i];
    vector<int> gl(n), gr(n);
    gl[0] = A[0];
    gr[n-1] = A[n-1];
    for(int i = 1; i < n; i++)
        gl[i] = __gcd(A[i], gl[i-1]);
    for(int i = n-2; i >= 0; i--)
        gr[i] = __gcd(A[i], gr[i+1]);
    vector<int> G(n);
    G[0] = gr[1];
    G[n-1] = gl[n-2];
    for(int i = 1; i <= n-2; i++)
        G[i] = __gcd(gl[i-1], gr[i+1]);
    cout << *max_element(G.begin(), G.end()) << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define mp map<int,int>
#define pp make_pair
#define endl "\n"
#define vi vector<int>
#define vbl vector<bool>
#define ll long long 
#define clock high_resolution_clock::now()

// auto duration = duration_cast<microseconds>(stop - start);  cout<<duration.count();

const int INF = 1e9+5;
const int mod = 1e9 + 7;

using namespace std;
using namespace std::chrono;

const int mx = 1005;

char arr[mx][mx];

void add_self(int&a, int b){
    a+=b;
    if(a>=mod)a-=mod;
}


int main(){
    int h, w;
    cin>>h>>w;
    for(int row =0; row<h; row++){
        cin>>arr[row];
    }
    vector<vector<int>>dp(h, vector<int>(w));
    dp[0][0] = 1;
    for(int row = 0; row<h; row++){
        for(int col = 0; col<w; col++){
            for(int r : {row, row+1}){
                int c = col;
                if(r==row){
                    c = col+1;
                }
                if(r<h && c<w && arr[r][c]=='.'){
                    add_self(dp[r][c], dp[row][col]);
                }
            }
        }
    }
    cout<<dp[h-1][w-1]<<endl;
    

	return 0;
}
	
	


Measured memory_bytes: 8484
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
signed main()
{
int a,b;
cin>>a>>b;
if(a>9||b>9)
{
    cout<<-1;
    return 0;
}
else
{
    cout<<a*b;
    return 0;
}
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(ll i=0; i<n; i++)
#define repr(i, s, e) for(ll i=s; i>=e; i--)
#define reps(i, s, e) for(ll i=s; i<=e; i++)
#define inf 1e18
#define all(v) v.begin(),v.end()
#define vsort(v) sort(v.begin(), v.end())
#define vsortr(v) sort(v.begin(), v.end(), greater<ll>())
#define ceil(a, b) (a+b-1)/b
#define ok cout << "ok" << endl;
#define sp << " " <<
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ fill((T*)array, (T*)(array+N), val); }
template<typename T> inline bool chmax(T &a, T b){ if(a<b){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T &a, T b){ if(b<a){ a=b; return true; } return false; }
template<typename T> void vdebug(vector<T> v){ cout << "vdebug" << endl; for(auto vv : v){ cout << vv << " "; } cout << endl; }
template<typename T> void adebug(T arr[], ll n){ cout << "adebug" << endl; reps(i, 0, n){ cout << arr[i] << " "; } cout << endl; }
template<typename T1, typename T2> void mdebug(map<T1, T2> mp){ cout << "mdebug" << endl; for(auto const& m : mp){ cout << m.first sp m.second << endl; }}
template<typename T1, typename T2> void mldebug(multimap<T1, T2> mp){ cout << "mldebug" << endl; for(auto const& m : mp){ cout << m.first sp m.second << endl; }}
template<typename T1, typename T2> void mdebugr(map<T1, T2, greater<T1>> mp){ cout << "mdebug" << endl; for(auto const& m : mp){ cout << m.first sp m.second << endl; }}
template<typename T1, typename T2> void mldebugr(multimap<T1, T2, greater<T1>> mp){ cout << "mldebug" << endl; for(auto const& m : mp){ cout << m.first sp m.second << endl; }}
void ans(bool b){ if(b) cout << "Yes" << endl; else cout << "No" << endl; }
void ans2(bool b){ if(b) cout << "YES" << endl; else cout << "NO" << endl; }
int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};


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

    vector<ll> a;
    int n;
    ll l, tmpa, sum;
    cin >> n >> l;
    rep(i, n){
        cin >> tmpa;
        a.push_back(tmpa);
        sum += tmpa;
    }

    bool res = false;
    int start_index = -1;
    rep(i, n-1){
        if(a[i] + a[i+1] >= l){
            res = true;
            start_index = i+1;
        }
    }

    vector<int> reslist;
    if(res){
        int l=1, r=n-1;
        while(l < start_index || start_index < r){
            if(l < start_index){
                reslist.push_back(l++);
            }
            if(start_index < r){
                reslist.push_back(r--);
            }
        }
    }
    reslist.push_back(start_index);

    if(res){
        cout << "Possible" << endl;
        for(auto const& e : reslist){
            cout << e << endl;
        }
    }else{
        cout << "Impossible" << endl;
    }

    return 0;
}


Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
typedef long long ll;
const ll INF = pow(2, 63) - 1;
int main(){
    ll n, W;
    cin >> n >> W;
    vector<pair<ll, ll> > p;
    vector<ll> v(n), w(n);
    rep(i,n)cin >> v[i] >> w[i];
    int n2 = n / 2;
    rep(i,1 << n2){
        ll sv = 0, sw = 0;
        rep(j,n2)if(i >> j & 1){
            sv += v[j];
            sw += w[j];
        }
        p.push_back(make_pair(sw, sv));
    }
    sort(p.begin(), p.end());
    int m = 1;
    REP(i,1,1<<n2)if(p[m-1].second < p[i].second){
        p[m] = p[i];
        m++;
    }
    ll r = 0;
    rep(i, 1 << (n-n2)) {
        ll sw = 0, sv = 0;
        rep(j, n - n2)if(i >> j & 1) {
            sw += w[n2 + j];
            sv += v[n2 + j];
        }
        if(sw <= W) {
            pair<ll, ll> pp = make_pair(W - sw, INF);
            ll tmp_v = (lower_bound(p.begin(), p.begin() + m, pp) - 1)->second;
            r = max(r, sv + tmp_v);
        }
    }
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 19460
n = int(input())
m = n
k = int(n/2)
cou = 0

while (m > 0):
        if m%2 == 0:
                m = m//2
        else:
                m = (m-1)//2
        cou += 1
cou -= 1

#print(cou)

cost = [[0 for i in range(n)] for i in range(n)]

def p(a):
        for i in range(len(a)):
                print(a[i])

#p(cost)

nuri = 0

def mois(n,a,b,c,d):
        global nuri
        for i in range(a,b+1):
                for j in range(c+1,d+1):
                        cost[i][j] = n
                        cost[j][i] = n
                        if i == j:
                                nuri += 1
                        else:
                                nuri += 2
                
def secl(na,a,b):
        global nuri
        if a == b:
                return 
        else:
                
                mois(na,a,(a+b)//2,(a+b)//2,b)
                #p(cost)
                
                secl(na+1,a,(a+b)//2)
                
                secl(na+1,((a+b)//2)+1,b)

secl(1,0,n-1)
#print((1+2)//2)
#p(cost)

#print(nuri)

#p(cost)

for i in range(n-1):
        a = []
        for j in range(i+1,n):
                a.append(cost[i][j])
        print(*a)

Measured memory_bytes: 50268
# C
N = int(input())
As = list(map(int, input().split()))

humidai = []

humidai.append(0)
for i in range(len(As))[1::]:
    humidai.append(As[i-1]+humidai[i-1]-As[i] if As[i-1]+humidai[i-1]-As[i] > 0 else 0)

print(sum(humidai))

# B
# N = str(input())

# sum = 0
# for n in N:
#     sum += int(n)

# print('Yes' if sum % 9 == 0 else 'No')

# #A
# N, X, T = map(int, input().split())

# print(T * (N//X if N % X == 0 else N//X+1))


Measured memory_bytes: 32168
uses math;
var i,n,res:integer;
    a,f:array[1..100] of integer;
begin
  readln(n);
  for i:=1 to n do read(a[i]);
  f[1]:=a[1];
  for i:=2 to n do f[i]:=f[i-1]+a[i];
  res:=high(integer);
  for i:=1 to n - 1 do 
    res:=min(res,abs((f[n]-f[i]) - f[i]));
  write(res)
end.

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n, b;
    cin >> n;
    int a[n];
    fill(a, a+n, 0);

    for(int i = 0; i < n - 1; ++i) {
        cin >> b;
        a[b - 1]++;
    }

    for(int i = 0; i < n; ++i) {
        cout << a[i] << "\n";
    }
}

Measured memory_bytes: 3960