akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
//#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define big bignum
#define lowbit(x) (x & -x)
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define R register
#define For(i, j, k) for(R int i = (j), ED = (k); i <= ED; ++i)
#define Rep(i, j, k) for(R int i = (j), ED = (k); i >= ED; --i)
#define Cross(i, j, k) for(R int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 100011;
const ll INF = 5e16;
const ll P = 1e9 + 7;

namespace IO {

	inline char gc() {
		static char buf[100000], *p1 = buf, *p2 = buf;
		return (p1 == p2) && (p2 = (p1 = buf) +
			fread (buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
	}

	#define dd ch = getchar()
	inline ll read() {
		R ll x = 0; R int f = 0; R char dd;
		for (; !isdigit (ch); dd) f ^= (ch == '-');
		for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
		return f? -x: x;
	}
	#undef dd

	inline void write( ll x ) {
		if (x < 0) putchar ('-'), x = -x;
		if (x > 9) write (x / 10); putchar (x % 10 | 48);
	}

	inline void wrn ( ll x ) { write (x); putchar (' '); }

	inline void wln ( ll x ) { write (x); putchar ('\n'); }

	inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using IO::wln;
using IO::read;

namespace Cesare {

	ll n, k, Ans = 0, Sz[N], fa[N], fac[N], inv[N], Vis[N];

	vector <ll> E[N];

	inline ll power ( ll a, ll b, ll res = 1 ) { 
		for (; b; b >>= 1, a = a * a % P) 
			res = (b & 1)? res * a % P: res; return res;
	}
	
	inline ll Inv ( ll a ) { return power(a, P - 2); }
	
	inline void Init() {
		fac[0] = inv[0] = 1;
		For ( i, 1, N - 5 ) 
			fac[i] = fac[i - 1] * i % P, inv[i] = Inv(fac[i]);
	}
	
	inline ll A ( ll n, ll m ) {
//		cout << "!" << n << " " << m << endl;
		if (m < 0 || n < m) return 0;
		return fac[n] * inv[n - m] % P;
	}

	inline void dfs ( ll u, ll Fa ) {
		For ( i, 1, E[u].size() ) {
			ll v = E[u][i - 1];
			if (v != Fa) fa[v] = u, dfs(v, u);
		}
	}

	inline void Dfs ( ll u ) {
		ll c = fa[u]? 1: 0;
//		if (k - c - 1 >= Sz[u]) 
		Ans = Ans * A(k - c - 1, Sz[u] - c) % P;
		For ( i, 1, E[u].size() ) 
			if (fa[u] != E[u][i - 1]) Dfs(E[u][i - 1]);
	}

	int main() {
		Init();
		n = read(), k = Ans = read();
		for (R int i = 1, u, v; i < n; ++i) 
			++Sz[u = read()], ++Sz[v = read()],
			E[u].push_back(v), E[v].push_back(u);
		fa[1] = 0;
		dfs(1, 0), Dfs(1); 
		return wln(Ans), 0;
	}

}

int main()
{
	return Cesare::main();
}

/*

*/






Measured memory_bytes: 12160
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using System.Runtime.CompilerServices;
using static MyUtil;

class MyUtil
{
    public static int[] ReadIntArray()
    {
	return ReadLine().Split().Select(x => int.Parse(x)).ToArray();
    }
}

class Program
{
    public static void Main()
    {
	int n = int.Parse(ReadLine());
	int[] a = ReadIntArray();

	double x = 0;
	for (int i = 0; i < n; i++)
	{
	    x += 1.0 / ((double) a[i]);
	}

	WriteLine(String.Format("{0:#.######}", 1.0/x));
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
  int k, n;
  cin >> k >> n;
  vector<int> a(n);
  REP(i, n) cin >> a[i];
  ll ans = 0, MX = 0;
  REP(i, n) {
    ll tmp;
    if(i!=n-1) tmp = a[i+1] -a[i];
    else tmp = k + a[0] -a[n-1];
    ans += tmp;
    chmax(MX, tmp);
  }
  ans -= MX;
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	
	public static class Point{
		public int x,y;
		
		public Point(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	public static final Point[] c_move = {
		                   new Point(-1,-2) , new Point(0,-2) , new Point(1,-2) ,
		new Point(-2,-1) ,                                                        new Point(2,-1) ,
		new Point(-2, 0) ,                                                        new Point(2, 0) ,
		new Point(-2, 1) ,                                                        new Point(2, 1) ,
		                   new Point(-1, 2) , new Point(0, 2) , new Point(1, 2)
	};
	
	public static boolean dive(int x, int y, int cur_num, Point[] s_array, int limit){
		boolean done = false;
		
		if(limit <= cur_num){
			return true;
		}
		
		for(Point move : c_move){
			int m_x = x + move.x;
			int m_y = y + move.y;
			
			if(m_x < 0 || m_x > 9 || m_y < 0 || m_y > 9){
				continue;
			}
			
			int s_x = s_array[cur_num].x;
			int s_y = s_array[cur_num].y;
			
			if((s_x - 1) <= m_x && m_x <= (s_x + 1) && (s_y - 1) <= m_y && m_y <= (s_y + 1)){
				done = dive(m_x, m_y, cur_num+1,s_array,limit);
			}
			
			if(done){
				break;
			}
		}
		
		return done;
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int c_x = sc.nextInt();
			int c_y = sc.nextInt();
			
			if(c_x == 0 && c_y == 0){
				break;
			}
			
			int s_num = sc.nextInt();
			Point[] sp_array = new Point[s_num];
			for(int i = 0; i < s_num; i++){
				sp_array[i] = new Point(sc.nextInt() , sc.nextInt());
			}
			
			System.out.println(dive(c_x,c_y,0,sp_array,s_num) ? "OK" : "NA");
		}
		
	}
	
}

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

using namespace std;
using ll = long long;

int main() {
    ll n;
    string s;
    cin >> n;
    cin >> s;
    vector<ll> w(n), e(n);
    for (ll i = 0; i < n; i++) {
        if (s[i] == 'W') {
            w[i] = 1;
        }
        else {
            e[i] = 1;
        }
    }
    for (ll i = 0; i < n-1; i++) {
        w[i+1] += w[i];
    }
    for (ll i = n-1; i >= 1; i--) {
        e[i-1] += e[i];
    }
    
    ll idx = 0;
    ll d = (ll)1e9;
    for (ll i = 0; i < n; i++) {
        if (d > (w[i] + e[i])) {
            d = (w[i] + e[i]);
            idx = i;
        }
        cerr << w[i] << ' ' << e[i] << endl;
    }
    
    ll ans = 0;
    for (ll i = 0; i < idx; i++) {
        if (s[i] == 'W') {
            ans++;
        }
    }
    for (ll i = idx + 1; i < n; i++) {
        if (s[i] == 'E') {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

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

#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define nyan "(=^･ω･^=)"
#define mkp make_pair
#define lP pair<ll, ll>
#define iP pair<int,int>

using namespace std;
typedef long long ll;

int N, b[100],c[100];
bool f[100];

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> b[i];
	}
	for (int i = 0; i < N; ++i) {
		if (b[i] > i + 1) {
			cout << -1 << endl;
			return 0;
		}
	}
	for (int i = 1; i <= N; ++i) {
		for (int j = N - 1; j >= 0; --j) {
			if (f[j])continue;
			if (b[j] == c[j] + 1) {
				f[j] = true;
				cout << b[j] << endl;
				for (int k = j; k < N; ++k) {
					++c[k];
				}
				break;
			}
		}
	}
	return 0;
}

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

int main(){
	int n;cin>>n;
	int a[n];
	int ans=100;
	for(int i=0;i<n;i++){
		int d=0;
		cin>>a[i];
		while(a[i]%2==0){
			a[i]/=2;
			d++;
		}
		ans=min(ans,d);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20);
#define int long long
main() {
    INCANT;
    int n, a;
    cin >> n;

    multiset<int> s;
    priority_queue<int> q;

    for(int i = 0; i < 1 << n; i++){
        cin >> a;
        s.insert(a);
    }
    
    auto itr = s.end();
    itr--;
    q.push(*itr);
    s.erase(itr);
    
    while(s.size()){
        auto tmp = q;
        while(!tmp.empty()){
            itr = s.lower_bound(tmp.top()); tmp.pop();
            if(itr == s.begin()){
                cout << "No" << endl;
                return 0;
            }
            itr--;
            q.push(*itr);
            s.erase(itr);
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 16748
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    S = input().rstrip()

    res = 'Yes'

    if S[2] != S[3]:
        res = 'No'

    if S[4] != S[5]:
        res = 'No'

    print(res)



main()


Measured memory_bytes: 2940
from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[(f.numerator, f.denominator)] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for (a, b) in ct.keys():
    if (a, b) in visited:
        continue
    inv = Fraction(-b, a)
    ia, ib = inv.numerator, inv.denominator
    visited.add((a, b))
    visited.add((ia, ib))
    tmp = pow(2, ct[(a, b)], MOD) + pow(2, ct[(ia, ib)], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)


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

int A[2][102];
int sum[2][102];

int main() {
  memset(A, 0, sizeof(A));
  memset(sum, 0, sizeof(sum));
  int N;
  cin >> N;
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < N; ++j)
      cin >> A[i][j];

  for (int i = 0; i < 2; ++i) {
    int s = 0;
    for (int j = 0; j < N + 1; ++j) {
      sum[i][j] = s;
      s += A[i][j];
    }
  }

  int ans = 0;
  for (int down = 0; down < N; ++down) {
    ans = max(ans, sum[0][down] + A[0][down] + (sum[1][N] - sum[1][down]));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
from operator import itemgetter

n = int(input())

temp_list = []
for i in range(n):
    s, p = input().split()
    temp_list.append((i + 1, s, int(p)))

temp_list.sort(key=itemgetter(2), reverse=True)
temp_list.sort(key=itemgetter(1))

for i in range(n):
    print(temp_list[i][0])

Measured memory_bytes: 3064
N = int(input())
dp = [list(map(int, input().split())) for i in range(N)]

for i in range(N-1):
  for j in range(3):
    maxN = 0
    for k in range(3):
      if j==k: continue
      maxN = max(maxN, dp[i][k])
    dp[i+1][j] += maxN

print(max(dp[-1]))

Measured memory_bytes: 61656
N = int(input())

XY = []
parity = []
for _ in range(N):
    xy = list(map(int, input().split()))
    XY.append(xy)
    parity.append(sum(xy))


def check(ds, l, xy):
    x = 0
    y = 0
    for i in range(len(ds)):
        if l[i] == "R":
            x += ds[i]
        elif l[i] == "L":
            x -= ds[i]
        elif l[i] == "U":
            y += ds[i]
        elif l[i] == "D":
            y -= ds[i]
        else:
            raise Exception

    return (x == xy[0]) & (y == xy[1])


if len(list(set([i % 2 for i in parity]))) == 2:
    print(-1)

elif parity[0] % 2 == 0:
    print(33)
    ds = [1, 1] + [2 ** k for k in range(1, 32)]
    print(*ds)
    for xy in XY:
        rev_ans = ""
        curr_x, curr_y = 0, 0
        for d in ds[::-1]:
            x_diff = xy[0] - curr_x
            y_diff = xy[1] - curr_y
            if abs(x_diff) >= abs(y_diff):
                if x_diff >= 0:
                    rev_ans += "R"
                    curr_x += d
                else:
                    rev_ans += "L"
                    curr_x -= d
            else:
                if y_diff >= 0:
                    rev_ans += "U"
                    curr_y += d
                else:
                    rev_ans += "D"
                    curr_y -= d

        print(rev_ans[::-1])
        # print(check(ds, list(rev_ans[::-1]), xy))


else:  # odd
    print(32)
    ds = [2 ** k for k in range(32)]
    print(*ds)
    for xy in XY:
        rev_ans = ""
        curr_x, curr_y = 0, 0
        for d in ds[::-1]:
            x_diff = xy[0] - curr_x
            y_diff = xy[1] - curr_y
            if abs(x_diff) >= abs(y_diff):
                if x_diff >= 0:
                    rev_ans += "R"
                    curr_x += d
                else:
                    rev_ans += "L"
                    curr_x -= d
            else:
                if y_diff >= 0:
                    rev_ans += "U"
                    curr_y += d
                else:
                    rev_ans += "D"
                    curr_y -= d

        print(rev_ans[::-1])
        # print(check(ds, list(rev_ans[::-1]), xy))


Measured memory_bytes: 44272
from collections import Counter
n=int(input())
a=list(map(int, input().split()))
b=[]
for i in a:
    b.append(i)
    b.append(i-1)
    b.append(i+1)
c=Counter(b)
count=0
for i in c.keys():
    if c[i]>count:
        count=c[i]
print(count)

Measured memory_bytes: 27360
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define rep(i, st, n) for (int i = (st); i < (n); ++i)
 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using ld = long double;
 
template <typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template <typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }

const int MAXN = 4000006;
const int MOD = 998244353;
int add(int x, int y)
{
    x += y;
    if (x >= MOD) x -= MOD;
    return x;
}
void vadd(int &x, int y)
{
    x += y;
    if (x >= MOD) x -= MOD;
}
int sub(int x, int y)
{
    x -= y;
    if (x < 0) x += MOD;
    return x;
}
int mult(int x, int y)
{
    return x * (ll)y % MOD;
}
int fact[MAXN];
int rfact[MAXN];
int rev[MAXN];
int bpow(int x, ll y)
{
    int res = 1;
    for (; y; y >>= 1, x = mult(x, x))
    {
        if (y & 1) res = mult(res, x);
    }
    return res;
}
int cnk(int n, int k)
{
    if (n < k) return 0;
    return mult(fact[n], mult(rfact[n - k], rfact[k]));
}

signed main()
{
#ifdef DEBUG
    freopen("in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fact[0] = rfact[0] = fact[1] = rfact[1] = 1;
    rev[1] = 1;
    for (int i = 2; i < MAXN; ++i)
    {
        rev[i] = MOD - mult(rev[MOD % i], MOD / i);
        //rev[i] = bpow(i, MOD - 2);
        fact[i] = mult(fact[i - 1], i);
        rfact[i] = mult(rfact[i - 1], rev[i]);
    }

    int n, m;
    cin >> n >> m;
    int Ans = 0;
    for (int d = 0; d <= min(n, m); ++d)
    {
        int s = 3 * m - d;
        if (s & 1) continue;
        int ans = 0;
        vadd(ans, cnk(s / 2 + n - 1, n - 1));
        if (d >= 1)
        {
            ans = sub(ans, mult(d, cnk(s / 2 - m + n - 2, n - 2)));
        }
        ans = sub(ans, mult(n, cnk(s / 2 - m - 1 + n - 1, n - 1)));
        vadd(Ans, mult(ans, cnk(n, d)));
    }
    cout << Ans << '\n';
          
    return 0;
}

Measured memory_bytes: 47104
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}

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

    string s; cin >> s;
    cout << (s == "ABC" ? "ARC" : "ABC") << endl;

    return 0;
}


Measured memory_bytes: 3648
N = int(input())
S = input()
S = list(S)

d = []
for n in range(1, N):
    if S[n-1] == S[n]:
        d.append(n)

cnt = 0
for i in d:
    i -= cnt
    del S[i]
    cnt += 1
    
print(len(S))

Measured memory_bytes: 13684
N, M = map(int, input().split())

# それぞれの桁を-1を初期状態とする
t = [-1] * N
# m回入力させる
for _ in range(M):
    s, c = map(int, input().split())
    s -= 1
    # もし初期値と違ってかつ左からs番目が入力値cと違ったら-1を出力
    if t[s] != -1 and t[s] != c:
        print(-1)
        exit()
    # そうじゃなければtのs番目にcを挿入
    t[s] = c

# もし1桁じゃない複数桁なら
if N != 1:
    # 先頭が0の場合エラーにする
    if t[0] == 0:
        print(-1)
        exit()

    # 先頭が何も入力されていない場合は最小値である1を挿入
    if t[0] == -1:
        t[0] = 1

    # もしi桁目が未入寮だったら最小値0を代入
    for i in range(1, N):
        if t[i] == -1:
            t[i] = 0
# もし1桁で1桁目が未入力なら0とする
else:
    if t[0] == -1:
        t[0] = 0

# 文字列なのでスペースなしにする
print(''.join(map(str, t)))

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
#define ll long long
#define en "\n"
const ll inf = 1e9;
const ll mod = 1e9 + 7;
using namespace std;
int dp[100005][4] = {0};
int main(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int a, b, c, n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a>>b>>c;
        dp[i][1] = max(dp[i - 1][2], dp[i - 1][3]) + a;
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][3]) + b;
        dp[i][3] = max(dp[i - 1][1], dp[i - 1][2]) + c;
    }
    cout<<max(dp[n][1], max(dp[n][2], dp[n][3]));
    return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
int main(void){
  int i,n,m;
  for(i=1;;i++){
    scanf("%d %d",&n,&m);
    if(n==0 && m==0)break;
    if(n>m)printf("%d %d\n",m,n);
    else printf("%d %d\n",n,m);
  }
  return 0;
}



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

using namespace std;

int N, ans;
char sir[109], aux[109], old[109];

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%s", sir + 1), N = strlen (sir + 1), ans = N + 1;
bool okT = 1;
for (int i=1; i<=N; i++)
    if (sir[i] != sir[1])
        okT = 0;
if (okT) ans = 0;
for (char c = 'a'; c <= 'z'; c ++)
{
    for (int i=1; i<=N; i++)
        aux[i] = sir[i];
    for (int stp = 1; stp < N; stp ++)
    {
        for (int i=1; i<=N - stp + 1; i++)
            old[i] = aux[i];
        bool ok = 1;
        for (int i=1; i<=N - stp; i++)
        {
            if (old[i] == c || old[i + 1] == c) aux[i] = c;
            else aux[i] = old[i];
            ok &= (aux[i] == c);
        }
        if (ok)
        {
            if (stp < ans)
                ans = stp;
            break;
        }
    }
}
printf ("%d\n", ans);

return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector<long long>v[200005];
long long dp[1002][1002],vis[1002][1002];

int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    
      long long n,i,j,k,sum=0,count=0,ans=0,x=0,y=0,l,r,m,mod=1000000007;
      cin>>n>>m;
      char c[n][m];
      for(i=0;i<n;i++)
      {
          for(j=0;j<m;j++)
          cin>>c[i][j];
      }
      
      for(i=0;i<n;i++)
      {
          for(j=0;j<m;j++)
          {
              if(i==0 && j==0)
              {
                  dp[i][j]=1;
              }
              else if(i==0)
              {
                  if(c[i][j]=='#')
                  dp[i][j]=0;
                  else
                  dp[i][j]=dp[i][j-1];
              }
              else if(j==0)
              {
                  if(c[i][j]=='#')
                  dp[i][j]=0;
                  else
                  dp[i][j]=dp[i-1][j];
              }
              else
              {
                   if(c[i][j]=='#')
                  dp[i][j]=0;
                  else
                  dp[i][j]=(dp[i-1][j]+dp[i][j-1])%mod;
              }
          }
      }
     
      cout<<dp[n-1][m-1];
	return 0;
}

Measured memory_bytes: 17004
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define random_shuffle asdasdd

int n;
string s;

int main() { 

  scanf("%d\n", &n);
  getline(cin, s);

  int ans = 0;
  for (int i = 0; i + 2 < n; i++) {
    if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
N,M,X,Y=map(int,input().split())
 
x=list(map(int,input().split()))
 
y=list(map(int,input().split()))

if max(x)+1<=min(y):
  for i in range(X+1,Y+1):
    if i>=max(x)+1 and i<=min(y):
      print('No War')
      exit()
print('War')

Measured memory_bytes: 3060
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n, m, x = LI()
    ca = LIR(n)
    ans = inf
    for mask in range(1 << n):
        tmp = [0] * m
        t = 0
        for i in range(n):
            if mask & (1 << i):
                for j in range(m):
                    tmp[j] += ca[i][j + 1]
                t += ca[i][0]
        if sum(map(lambda a: a < x, tmp)):
            continue
        ans = min(ans, t)
    if ans == inf:
        print(-1)
    else:
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 78944
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, X, Y):
    MOD = 10**9+7

    xs = 0
    for i in range(N):
        xs += (i-(N-(i+1)))*X[i]
        xs %= MOD
    ys = 0
    for i in range(M):
        ys += (i-(M-(i+1)))*Y[i]
        ys %= MOD
    return xs*ys % MOD


def main():
    N, M = read_int_n()
    X = read_int_n()
    Y = read_int_n()
    print(slv(N, M, X, Y))


if __name__ == '__main__':
    main()


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

using namespace std;

#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define MP make_pair
#define PB push_back
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
const double pi=acos(-1.0);
typedef pair<int, int> PII;
typedef long int int32;
typedef unsigned long int uint32;
typedef long long int int64;
typedef unsigned long long int  uint64;
typedef long long ll;
inline ll add(ll a, ll b){a += b; if(a >= MOD)a -= MOD; return a;}
inline ll sub(ll a, ll b){a -= b; if(a < 0)a += MOD; return a;}
inline ll mul(ll a, ll b){return (ll)((ll) a * b %MOD);}


#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
vector<int> tree[100000+5];
int dp[100000+5][2];

// int psum1[100000+5];
// int psum0[100000+5];

void dfs(int u, int p)
{
    int c_count = 0;
    vector<int> dp0;
    vector<int> dp1;
    int c2 = LONG_MAX;
    for(int c : tree[u])
    {
        if(c==p)    continue;
        dfs(c, u);
        dp0.push_back(dp[c][0]);
        dp1.push_back(dp[c][1]);
        c2 = min(c2, dp[c][0]);
        c_count++;
    }
    if(c_count==0)
    {
        dp[u][0]=1;
        dp[u][1]=1;
    }
    else
    {
        int lp = 1;
        int l2 = 1;
        REP(i, c_count)
            // psum0[i+1] = psum0[i]+dp0[i], psum1[i+1] = psum1[i]+dp1[i];
            lp = mul(lp, add(dp0[i], dp1[i])) , l2 = mul(l2, dp0[i]);
        dp[u][0] = lp;
        dp[u][1] = l2;
    }
    // cout << u << " " << dp[u][0] << " " << dp[u][1] << " " << psum1[c_count] << " "<< psum0[c_count] << "\n";
}
signed main()
{
    IOS
    int n;
    cin >> n;
    REP(i, n-1)
    {
        int u,v;
        cin >> u >> v;
        u--;v--;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    dfs(0, -1);
    int ans = add(dp[0][0],dp[0][1]);
    cout << ans;
}

Measured memory_bytes: 18432
#include<bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; i++) 
#define _FOR(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
int n, m, V, w[10000], v[10000], dp[100000], ans;
int main(){
    cin >> n >> m;
    FOR(i, 1, n) {
        cin >> w[i] >> v[i];
        V += v[i];
    }
    memset(dp, 999999, sizeof(dp));
    dp[0] = 0;
    FOR(i, 1, n) {
        _FOR(j, V, v[i]) {
            dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    _FOR(i, V, 0) {
        if(dp[i] <= m) {
            ans = i;
            break;
        }
    }
    cout << ans;
    
    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
	int a, b;
	
	scanf("%d %d", &a, &b);
	
	int d    =         a / b;
	int r    =         a % b;
	double f = (double)a / b;
	
	printf("%d %d %f\n", d, r, f);
	
	return 0;
}

Measured memory_bytes: 2720
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        sc.close();

        // 主処理
        long result = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int j2 = 1; j2 <= n; j2++) {
                    result += gcd3(i, j, j2);
                }
            }
        }

        // 出力
        System.out.println(result);
    }

    public static int gcd3(int a, int b, int c) {

        int bc = gcd(b, c);

        int temp;
        while ((temp = a % bc) != 0) {
            a = bc;
            bc = temp;
        }
        return bc;
    }

    public static int gcd(int a, int b) {
        int temp;
        while ((temp = a % b) != 0) {
            a = b;
            b = temp;
        }
        return b;
    }
}


Measured memory_bytes: 35664
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    a = LI()
    cumsum = [0 for _ in range(N+1)]
    for i in range(N):
        cumsum[i+1] = a[i] + cumsum[i]
    d = collections.Counter(cumsum[1:])
    cnt = 0
    for a in d.keys():
        if a == 0:
            cnt += d[a]
        cnt += d[a] * (d[a] - 1) // 2
    print(cnt)


main()



Measured memory_bytes: 45180
#include <bits/stdc++.h>
#define __count __builtin_popcount
#define __countll __builtin_popcountll
#define X first
#define Y second
#define mst(x) memset(x,0,sizeof(x))
#define mst1(x) memset(x,-1,sizeof(x))
#define ALL(c) (c).begin(),(c).end()
#define FOR(i,n) for(int i=0;i<n;i++)
#define FOR1(i,n) for(int i=1;i<=n;i++)
#define FORit(it,c) for(__typeof(c.begin()) it=c.begin();it!=c.end();++it)
#define pb push_back
#define RI(x) scanf("%d",&x)
#define RID(x) int x;RI(x)
using namespace std;
typedef long long LL;
const int N = 2e5+7;
int n;
int a[N];

vector<int> Edge[N];
int v[N];
int V;
bool visit(int x){return v[x] == V;}

int max_level;
int dfs(int x, int level){
  v[x] = V;
  if(a[x] == 2) {
    max_level = level;
    return 1;
  }
  int res = 0;
  for(auto nxt: Edge[x]) {
    if(visit(nxt)) continue;
    res += dfs(nxt, level + 1);
  }
  if(res == 1) {
    a[x] = (max_level/2 < level)?2:1;
    return 1;
  }
  else return 0;
}

void dfs2(int x, int c){
  v[x] = V;
  if(a[x] == 0) a[x] = c;
  for(auto nxt: Edge[x]){
    if(visit(nxt)) continue;
    dfs2(nxt, a[x]);
  }
}

void add(int x, int y){
  Edge[x].push_back(y);
  Edge[y].push_back(x);
}
int main(){
  RI(n);
  FOR(i,n){
    RID(x); RID(y);
    add(x,y);
  }
  a[1] = 1, a[n] = 2;
  V++;
  dfs(1,0);
  V++;
  dfs2(1, 1);
  int res = 0;
  FOR1(i,n){
    assert(a[i] != 0);
    if(a[i] == 1) res++;
    else res --;
  }
  if(res > 0 ) puts("Fennec");
  else puts("Snuke");
}


Measured memory_bytes: 15360
#include <bits/stdc++.h>
using namespace std;
#define NAME "Knapsack1"
#define ll long long
int n,m;
int w;
int v;
ll  dp[100001];
int main(){
    //ifstream cin(NAME".inp");
    //ofstream cout(NAME".out");
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>w>>v;
        for(int j=m;j>=w;j--)
            if (dp[j] < dp[j-w] + v) dp[j] = dp[j-w] + v;
    }
    cout<<dp[m];
}



Measured memory_bytes: 4412
use std::io::Read;

fn solve(g: &Vec<Vec<usize>>, s1: usize, s2: usize) -> (i64, i64) {
    let mut color = vec![-1; g.len()];
    let mut res = 1;
    color[s1] = 1;
    if s2 != !0 { color[s2] = 1; res += 1; }
    let mut cur = 1;
    loop {
        let mut mx = 0;
        for i in 0..g.len() {
            if color[i] != cur { continue }
            let mut cnt = 0;
            for &t in &g[i] {
                if color[t] != -1 { continue; }
                cnt += 1;
                color[t] = cur + 1;
            }
            mx = std::cmp::max(mx, cnt);
        }
        if mx == 0 { break }
        res *= mx;
        if res >= 1 << 60 { return (100000, 1 << 60) }
        cur += 1;
    }
    (cur, res)
}

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).ok();
    let mut it = buf.split_whitespace();
    let n = it.next().unwrap().parse::<usize>().unwrap();
    let mut g = vec![Vec::new(); n];
    for _ in 0..n-1 {
        let a = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let b = it.next().unwrap().parse::<usize>().unwrap() - 1;
        g[a].push(b);
        g[b].push(a);
    }
    let mut res = (100000, 0);
    for i in 0..n {
        res = std::cmp::min(res, solve(&g, i, !0));
        for &t in &g[i] {
            if t < i {
                res = std::cmp::min(res, solve(&g, i, t));
            }
        }
    }
    println!("{} {}", res.0, res.1);
}


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

int main(){
	int r,c,**a;

	scanf("%d %d",&r,&c);
	a=(int**)malloc((r+1)*sizeof(int*));
	for(int i=0;i<(r+1);i++){
		a[i]=(int*)malloc((c+1)*sizeof(int));
	}

	for(int i=0;i<r;i++){
		a[i][c]=0;
		for(int j=0;j<c;j++){
			scanf("%d",&a[i][j]);
			a[i][c]+=a[i][j];
		}
	}
	
	for(int i=0;i<(c+1);i++){
		a[r][i]=0;
		for(int j=0;j<r;j++){
			a[r][i]+=a[j][i];
		}
	}

	for(int i=0;i<(r+1);i++){
		for(int j=0;j<(c);j++){
			printf("%d ",a[i][j]);
		}
		printf("%d\n",a[i][c]);
	}
	return 0;
}


Measured memory_bytes: 2052
#include <stdio.h>

int main(void) {
  int i, j, k, n, p[] = {1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 2, 23, 234, 2345, 23456, 234567, 2345678, 23456789, 3, 34, 345, 3456, 34567, 345678, 3456789, 4, 45, 456, 4567, 45678, 456789, 5, 56, 567, 5678, 56789, 6, 67, 678, 6789, 7, 78, 789, 8, 89, 9};
  scanf("%d", &n);
  int a[n], ans = -1;
  for(i = 0; i < n; ++i) scanf("%d", &a[i]);
  for(i = 0; i < n; ++i) for(j = i + 1; j < n; ++j) for(k = 0; k < 45; ++k) if(a[i] * a[j] == p[k] && ans < a[i] * a[j]) ans = a[i] * a[j];
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 2736
#入力
a = input()
#空のリスト
ans = []
for c in a:#cが0文字目からaまで
    if c != "B": #Bでなければアペンド
        ans.append(c)
    else:
        if len(ans) != 0 :ans.pop()#Bであってさらにリストがからでなければpop
 
print("".join(ans)) #listをくっつけた文字にできる

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll INF=mod*mod;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(x) (x).begin(),(x).end()
ll min(ll a,ll b){
  if(a>b){
    return b;
    }
      else{
        return a;
      }
  }
  
  ll max(ll a,ll b){
    if(a>b){
      return a;
    }
    else{
      return b;
    }
  }

ll power(ll a,ll b){
 ll ans=1;
 for(ll i=1;i<=b;i++){
ans*=a;
  }
  return ans;
}

 ll gcd(ll m,ll n){
 	if(n==0){
       return m;
     }
   return gcd(n,m%n);
 }
ll lcm(ll a,ll b){
  ll g=gcd(a,b);
  return a/gcd(a,b)*b;
		

}
int main(){
  
  ll N;
  cin>>N;
  string S;
cin>>S;

ll ans=0;
  rep(i,10){
    rep(j,10){
rep(k,10){//後ろから見ていく
  ll sum=0;
  ll now=N-1;
  for(ll l=N-1;l>=0;l--){
if(S[l]-'0'==k){
  sum++;
  now=l;
  break;
}
  }

  for(ll m=now-1;m>=0;m--){
if(S[m]-'0'==j){
sum++;
  now=m;
  break;
}
  }

for(ll n=now-1;n>=0;n--){
if(S[n]-'0'==i){
sum++;
  now=n;
  break;
}
}
  

if(sum==3){
ans++;
}
}
    }
  }

  cout<<ans<<endl;
}


    

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
int lcm(int x,int y){
  return x/__gcd(x,y)*y;
}
int mod_pow(int x,int n,int mod){
  int res=1;
  while(n>0){
    if(n&1) (res*=x)%=mod;
    (x*=x)%=mod;
    n>>=1;
  }
  return res;
}

int euler_phi(int n){
  int res=n;
  for(int i=2;i*i<=n;i++){
    if(n%i==0){
      res=res/i*(i-1);
      for(;n%i==0;n/=i);
    }
  }
  if(n!=1) res=res/n*(n-1);
  return res;
}
signed main(){
  int n,b;
  cin>>n;
  b=n;
  map<int,int> m;
  for(int i=2;i*i<=n;i++){
    if(n%i) continue;
    while(n%i==0) n/=i,m[i]++;
  }
  if(n!=1) m[n]++;
  if(b==n){
    cout<<1<<endl;
    return 0;
  }
  int ans=1LL;
  for(auto p:m){
    if(p.second>1){
      cout<<-1<<endl;
      return 0;
    }
    ans=lcm(ans,p.first-1);
  }
  if(__gcd(b,ans)!=1LL){
    cout<<-1<<endl;
    return 0;
  }
  int phi=euler_phi(ans);
  //cout<<phi<<endl;
  int tmp=phi;
  for(int i=2;i*i<=phi;i++){
    if(phi%i) continue;
    if(mod_pow(b,i,ans)==1) tmp=min(tmp,i);
    if(mod_pow(b,phi/i,ans)==1) tmp=min(tmp,phi/i);
  }
  cout<<tmp<<endl;
  return 0;
}

Measured memory_bytes: 3088
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using std::swap;
using std::max;
using std::min;
using std::sort;

typedef long long LL;

const int N = 1010;

int n;
int a[N], b[N];

int main() {
  int ans = 0; scanf("%d", &n);
  for (int i = 1; i <= n - 1; ++i)
    scanf("%d", &b[i]);
  ans += b[1]; ans += b[n - 1];
  for (int i = 1; i <= n - 2; ++i)
    ans += min(b[i], b[i + 1]);
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
using ll = long long;
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using pll = pair<long long,long long>;
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
const long long INF = 1LL << 60;
const long long MOD = 1000000007;

//最大最小の入れ替え
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
//以上テンプレ
int main(){
    ll N,K;
    cin>>N>>K;
    vector<pll> vec(N);
    rep(i,N){
        ll c,d;
        cin>>c>>d;
        vec.at(i).first=c;
        vec.at(i).second=d;
    }
    sort(all(vec));
    rep(i,N){
        K-=vec.at(i).second;
        if(K<1){
            cout<<vec.at(i).first<<endl;
            return 0;
        }
    }
    }


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define srt(i) sort(i.begin(), i.end())
#define rvt(i) sort(i.begin(), i.end(), greater<int>())

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

  vector<int> arr(n+1);
  rep(i,n-1){
    int a;
    cin >> a;
    arr.at(a)+=1;
  }

  for(int i=1; i<=n; i++) cout << arr.at(i) << endl;

}

Measured memory_bytes: 3988
n = int(input())
lis = list(map(int, input().split()))

ban = [0] * n

tmp = 0
for i in lis:
    ban[i-1] += 1

for i in ban:
    tmp += i*(i-1)//2
    
for i in lis:
    print(tmp+(1-ban[i-1]))

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

  if(data=='A'){
    cout<<"T"<<endl;
  }else if(data=='T'){
    cout<<"A"<<endl;
  }else if(data=='G'){
    cout<<"C"<<endl;
  }else if(data=='C'){
    cout<<"G"<<endl;
  }


  return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef int in;
#define int long long
#define pb push_back
#define f first
#define s second
#define double long double
const int MAX=2e5+5;
const int MAX2=2e5+4;
const int MAAX=2e18;
const int MOD=1e9+7;

in main()
{
int a,b;
cin>>a>>b;
int ans=(a*b+1)/2;
if(min(a,b)==1)
    cout<<1<<endl;
    else
cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define ll long long int
#define w(t) int t;cin>>t; while(t--)
#define mp make_pair
#define fi first
#define se second
#define fr(n) for(int i=0;i<n;i++)
#define um unordered_map
#define pqm priority_queue <int, vector<int>, greater<int> >
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    ll sum=0;
    int i=1;
    while(i<=n){
    	if(i%5==0 || i%3==0){
    		i++;
		}
		else{
			sum+=i;
			i++;
		}
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 3652
# -*- coding: utf-8 -*-
#mitsui d
import sys
import math
import collections
#sys.setrecursionlimit(100000)

n=int(input())

s=input()
#tmp = input().split()
#s = list(map(lambda a: int(a), tmp))

sfirst=[]
slast=[]
for i in range(0,10):
	sfirst.append(n)
	slast.append(0)
for i in range(0,n):
	if(sfirst[int(s[i])]>i):
		sfirst[int(s[i])]=i
	if(slast[int(s[i])]<i):
		slast[int(s[i])]=i
#print(s)
#print(sfirst)
#print(slast)

ans=0

for i in range(0,10):
	for j in range(0,10):
		for k in range(0,10):
			flg=0
			for index in range(sfirst[i]+1,slast[k]):
				if(flg==0)and(s[index]==str(j)):
					flg+=1
					ans+=1
					break
print(ans)

Measured memory_bytes: 3436
#include <iostream>
using namespace std;
int main()
{
	for(int i=0;i<3;i++)
	{
		int sh,sm,ss; cin >> sh >> sm >> ss ;
		int fh,fm,fs; cin >> fh >> fm >> fs ;
		int h,m,s,tmp;
		tmp=(fh*3600+fm*60+fs)-(sh*3600+sm*60+ss);
		h=tmp/3600; s=tmp%60;
		m=(tmp-h*3600)/60;
		cout << h << ' ' << m << ' ' << s << endl;
	}
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <math.h>

int main(){
	long long a, b, c;
	scanf("%lld%lld%lld",&a,&b,&c);
    if(c-a-b<0) puts("No");
	else puts(4*a*b<(c-a-b)*(c-a-b)?"Yes":"No");
}


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

#include <math.h>
#include <iomanip>
#include <vector>
#include <queue>
#include <climits>
using Graph = vector<vector<int>>;
const double PI = 3.14159265358979323846;
#define int long long


signed main() {

	const int SIZE = 300;

	string D, T, S;
	cin >> S>>T;

	int ls, lt;
	
	ls = S.length();
	lt = T.length();

	int min = lt;

	for (int i = 0; i < ls-lt+1; i++) {
		int tmp = lt;
		for (int j = 0; j < lt; j++) {
			if (S[i + j] == T[j]) tmp--;
		}
		if (min > tmp) {
			min = tmp;
		}
	}


	cout << min << endl;

	cin >> min;

	return 0;


}



Measured memory_bytes: 3592
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int N;

int main(int argc, char* argv[]) {
  cin >> N;
  bool has_yellow = false;
  for (int i = 0; i < N; i++) {
    char S;
    cin >> S;
    if (S == 'Y')
      has_yellow = true;
  }

  cout << (has_yellow ? "Four" : "Three") << endl;
  return 0;
}


Measured memory_bytes: 3608
def numConvertHalf(numbers):
    for i in range(len(numbers)):
        numbers[i] = int(numbers[i]/2)

def checkEven(numbers):
    for i in range(len(numbers)):
        if(numbers[i] % 2 == 1):
            return False
    return True

N = int(input())
numbers = list(map(int,input().split()))
count = 0
while checkEven(numbers):
    numConvertHalf(numbers)
    count += 1
print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <cmath>
#include <functional>
#include <set>
#include <string>
#include <stdlib.h>
#include <iomanip>
#include <utility>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define ii pair<int,int>
#define mp make_pair
#define pb push_back
#define iii pair<ii,int >
#define ff first
#define ss second
#define vi vector<int>
#define vc vector<char>
 
using namespace std;


int main(){
	int n;
	cin >> n;
	ll arr[n];
	FOR(i,n)cin >> arr[i];
	ll dp[n][n];
	FOR(i,n)FOR(j,n)dp[i][j] = 0;
	ll pref[n];
	pref[0] = arr[0];
	FORE(i,1,n-1)pref[i] = pref[i-1] + arr[i];
	FOR(k,n){
		FOR(i,n-k){
			if(k == 0){
				dp[i][i+k] = arr[i];
			}else if(k == 1){
				dp[i][i+k] = max(arr[i],arr[i+1]);
			}else{
				dp[i][i+k] = max(arr[i] + (pref[i+k] - pref[i]) - dp[i+1][i+k] ,
				 arr[i+k] + pref[i+k-1] - ((i>0)?pref[i-1]:0) - dp[i][i+k-1]);
			}
		}
	}
	ll x = dp[0][n-1];
	ll y = pref[n-1] -x;
	cout << x - y << endl;
	return 0;
}


Measured memory_bytes: 70656
//g++ -std=c++14 test.cpp -o test.out
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

long long int A,B,K;
long long int ans1,ans2;

void solve(){
	long long int diff = A-K;
	if(diff>=0){
		ans1 = diff;
		ans2 = B;
		return;
	}
	ans1 = 0;
	diff = B+diff;
	if(diff>=0){
		ans2 = diff;
		return;
	}
	ans2 = 0;
	return;
}

int main(){
	cin >> A >> B >> K;

	solve();

	cout << ans1 << ' ' << ans2;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int n,h=0,next;
  cin>>n;
  bool flag=true;
  for(int i=0;i<n;i++){
    cin >> next;
    if( h > next)flag=false;
    else if(h < next)next--;
    h=next;
  }
  if(flag)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <map>
//#include <set>
//#include <list>
//#include <cmath>
//#include <ctime>
//#include <deque>
//#include <queue>
//#include <stack>
//#include <string>
//#include <bitset>
//#include <cstdio>
//#include <limits>
//#include <vector>
//#include <climits>
//#include <cstring>
//#include <cstdlib>
//#include <fstream>
//#include <numeric>
//#include <sstream>
//#include <iomanip>
//#include <iostream>
//#include <algorithm>
//#include <unordered_map>

using namespace std;

#define file freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.141592653589793238462643383279502884
#define MAX 1000100
#define mod 1000000007
#define EPS 1E-9
#define int long long
#define endl "\n"

int fix(int cur, int m)
{
    return ((cur%m) + m) % m;
}

int fast_power(int x, int y,int m)
{
    if (y == 0)
        return 1;
    int temp = fast_power(x, y / 2, m) ;
    temp = (temp*temp)% m;
    if (y % 2 != 0)
        temp = (temp*x)% m;
    return temp;

}
double n,k;

int summation(int itr)
{
    int res=itr,acum=0;
    int cnt=0,tmp=1;
    for(int i=1;res<k;i*=2)
    {
        cnt++;
        res+=(itr*i);
        if(res>=k)
            break;
    }
    return cnt;

}


int32_t main()
{
    //freopen("C:/Users/Joe/Desktop/tests/in11.txt", "r", stdin);
    //freopen("C:/Users/Joe/Desktop/tests/out11.txt", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.tie(0);

    int t=1;
    //cin >> t;
    while(t--)
    {
        cin >> n >> k;
        double prob,sum=0,partial_prob;
        prob=(1/n);
        for(int i=1;i<=n;i++)
        {
            int numberOfTimes=summation(i);
            partial_prob=prob*pow(0.5,numberOfTimes);
            sum+=partial_prob;
        }
        cout << fixed << setprecision(9) << sum << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import numpy as np
n,m = map(int,input().split())
ac, wa = [0] * n, [0] * n
for i in range(m):
  p,s = input().split()
  p = int(p)-1
  if s == 'AC':
    ac[p] = 1
  if s == 'WA' and ac[p] == 0:
    wa[p] += 1
print('{} {}'.format(sum(ac), np.dot(ac, wa)))

Measured memory_bytes: 15564