akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <numeric>

/* debug macros */
#ifdef WAFDAYO
#define DBG_LINE() {std::cerr<<"\e[2m[L"<<__LINE__<<"]\e[m ";}
#define DBG_PRINT(s,t,u) {std::cerr<<(s)<<" \e[2m=\e[m \e[1m"<<(t)<<"\e[m"<<(u);}
#define SELECT_7TH(x1,x2,x3,x4,x5,x6,x7,...) x7
#define dbg1(x1) DBG_PRINT(#x1,x1,std::endl)
#define dbg2(x1,x2) DBG_PRINT(#x1,x1,", ")dbg1(x2)
#define dbg3(x1,x2,x3) DBG_PRINT(#x1,x1,", ")dbg2(x2,x3)
#define dbg4(x1,x2,x3,x4) DBG_PRINT(#x1,x1,", ")dbg3(x2,x3,x4)
#define dbg5(x1,x2,x3,x4,x5) DBG_PRINT(#x1,x1,", ")dbg4(x2,x3,x4,x5)
#define dbg6(x1,x2,x3,x4,x5,x6) DBG_PRINT(#x1,x1,", ")dbg5(x2,x3,x4,x5,x6)
#define dbg(...) DBG_LINE()\
SELECT_7TH(__VA_ARGS__,dbg6,dbg5,dbg4,dbg3,dbg2,dbg1)(__VA_ARGS__)
#else
#define dbg(...) {}
#endif

/* utility functions */
struct read_item{read_item(){};
template<class T>operator T(){T t;std::cin>>t;return t;}};
char splf(int i,int n){return(i+1<n)?' ':'\n';};
template<bool up>
struct _RI{int i;_RI(int a):i(a){}
int operator*(){return i;}void operator++(){i+=(up?1:-1);}
bool operator!=(const _RI& r){return up?i<r.i:i>=r.i;}};
template<bool up>
struct _RX{_RI<up> x,y;_RI<up> begin(){return x;}_RI<up> end(){return y;}
_RX(int a,int b):x(up?a:(a-1)),y(b){}_RX(int a):_RX(up?0:a,up?a:0){}};
typedef _RX<true> range;
typedef _RX<false> revrange;

/* types and constants */
typedef int64_t i64;
typedef uint64_t u64;
// const i64 inf = (i64)1.05e18;
// const int inf = (int)1.05e9;

using namespace std;

int gcd(int a, int b) {
	if(a < b) {
		swap(a, b);
	}
	return (b == 0) ? a : gcd(b, a % b);
}

int pow(int x, int n) {
	int y = 1;
	for(auto i : range(n)) {
		y = y * x;
	}
	return y;
}

vector<pair<i64,int>> decomp(const i64 n) {

	i64 m = n;
	vector<pair<i64,int>> ps;
	for(i64 d = 2; d * d <= n; d++) {
		if(m % d != 0) {
			continue;
		}
		ps.push_back({d, 0});
		while(m % d == 0) {
			m = m / d;
			ps[ps.size() - 1].second += 1;
		}
	}
	if(m > 1) {
		ps.push_back({m, 1});
	}

	return ps;
}

int main() {

	const i64 N = read_item();

	auto rs = decomp(N - 1);
	i64 ans = 1;
	for(auto r : rs) {
		ans = ans * (r.second + 1);
	}
	ans = ans - 1;
	dbg(ans);

	auto ps = decomp(N);
	const int m = ps.size();
	vector<i64> qs(m);
	for(auto i : range(m)) {
		qs[i] = pow(ps[i].first, ps[i].second);
	}

	for(auto bit : range(1, (1 << m))) {

		int g = 0;

		for(auto i : range(m)) {
			if(bit & (1 << i)) {
				g = gcd(g, ps[i].second);
			}
		}

		i64 prod_g = 1;
		i64 rem = 1;
		for(auto i : range(m)) {
			if(bit & (1 << i)) {
				prod_g = prod_g * pow(ps[i].first, ps[i].second / g);
			} else {
				rem = rem * qs[i];
			}
		}

		dbg(prod_g, rem, g);

		for(auto d : range(1, g + 1)) {
			if(g % d != 0) {
				continue;
			}
			i64 prod = pow(prod_g, g / d);
			if(rem % prod != 1) {
				continue;
			}
			dbg(prod);
			ans += 1;
		}
	}

	printf("%lld\n", ans);

	return 0;
}

/* wafdayo~~~ */


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int h,w,n;
	cin >> h >> w >> n;
	if(n==0){
		cout << h << endl;
		return 0;
	}
	vector<pair<int,int> > p(n);
	for(int i = 0; i < n; i++){
		// cin >> p[i].first >> p[i].second;
		cin >> p[i].second >> p[i].first;
	}
	// char m[100][100];
	// for(int i = 0; i < 100; i++){
	// 	for(int j = 0; j < 100; j++){
	// 		m[i][j] = 'o';
	// 	}
	// }
	// for(int i = 0; i < n; i++){
	// 	m[p[i].second][p[i].first] = 'x';
	// }

	// for(int i = w; i >=1; i--){
	// 	for(int j = 1; j <= h; j++){
	// 		cout << m[i][j];
	// 	}
	// 	printf("\n");
	// }
	sort(all(p));
	// int ans = h;
	// for(int i = 0; i < n; i++){
	// 	if(p[i].first-1 <= ans && p[i].first > p[i].second){
	// 		ans = p[i].first-1;
	// 		m[p[i].second][p[i].first] = '!';
	// 	}
	// }
	// cout << ans << endl;

	// for(int i = w; i >=1; i--){
	// 	for(int j = 1; j <= h; j++){
	// 		cout << m[i][j];
	// 	}
	// 	printf("\n");
	// }

	int d = 0;
	vector<int> res;
	// int y_now = 0;
	for(int i = 0; i < n; i++){
		// if(p[i].first != y_now) y_now = p[i].first;
		if(p[i].first == p[i].second-d) d++;
		else if(p[i].first<p[i].second-d) res.push_back(p[i].second-1);
	}

	int ans = h;
	for(int i = 0; i < res.size(); i++){
		ans = min(ans,res[i]);
	}
	// if(ans == h) ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 2176
import sys


def solve(A: int, B: int):
    print(A*B)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9056
from math import sqrt

_ = input()
x = [float(i) for i in input().split()]
y = [float(i) for i in input().split()]

def f1(x, y):
    return sum([abs(t[0] - t[1]) for t in zip(x, y)])
    
def f2(x, y):
    return sqrt(sum([pow(t[0] - t[1], 2) for t in zip(x, y)]))

def f3(x, y):
    return pow(sum([ pow(abs(t[0] - t[1]), 3) for t in zip(x, y)]), 1.0 / 3.0)
    
def f4(x, f):
    return max([abs(t[0] - t[1]) for t in zip(x, y)])
    
print(f1(x, y))
print(f2(x, y))
print(f3(x, y))
print(f4(x, y))


Measured memory_bytes: 5716
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <string>
#include <cmath>
#include <cassert>
#define SIZE 20
#define INF 1000000000000000LL

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

map <P,ll> dp[SIZE][SIZE];
ll A[SIZE];

ll solve(int l,int r,int a,int b)
{
	if(dp[l][r].count(P(a,b))) return dp[l][r][P(a,b)];
	if(l==r) return (ll) (a+b)*A[l];
	ll ret=INF;
	for(int i=l;i<=r;i++)
	{
		ll sum=(ll) (a+b)*A[i];
		if(l<i) sum+=solve(l,i-1,a,a+b);
		if(i<r) sum+=solve(i+1,r,a+b,b);
		ret=min(ret,sum);
	}
	return dp[l][r][P(a,b)]=ret;
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++) scanf("%lld",&A[i]);
	if(n==2)
	{
		printf("%lld\n",A[0]+A[1]);
	}
	else
	{
		ll ret=A[0]+A[n-1];
		ret+=solve(1,n-2,1,1);
		printf("%lld\n",ret);
	}
	return 0;
}


Measured memory_bytes: 8320
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
#define maxn 2010
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define pii pair<int, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define IL inline
#define ss system
using namespace std;

int A, B;
ll C[maxn][maxn], S[maxn][maxn], Si[maxn][maxn], ans = 0;
const ll p = 1e9 + 7;
template <class T> void read (T &x) {
  char ch = x = 0;
  bool fl = false;
  while (!isdigit(ch))
    fl |= ch == '-', ch = getchar();
  while (isdigit(ch))
    x = x * 10 + ch - '0', ch = getchar();
  x = fl ? -x : x;
}
ll calc(int x, int y) {
  int z = min(x, y);
  if (z < 0)
    return 0;
  return (S[x][z] * (y + 1) - Si[x][z] + p) % p;
}
void init() {
  C[0][0] = 1;
  for (int i = 0; i < maxn; i++) {
    S[0][i] = 1;
  }
  for (int i = 1; i < maxn; i++) {
    for (int j = 0; j <= i; j++) {
      C[i][j] = ((j ? C[i - 1][j - 1] : 0) + C[i - 1][j]) % p;
      S[i][j] = ((j ? S[i][j - 1] : 0) + C[i][j]) % p;
      Si[i][j] = ((j ? Si[i][j - 1] : 0) + C[i][j] * j) % p;
    }
  }
}
int main() {
  read(A), read(B), init();
  for (int x = 0; x <= A; x++) {
    for (int y = 0; y <= B - 1; y++) {
      ll tmp = calc(y - 1, A - x - y) + !y;
      ans = (ans + tmp * C[B - 1][y]) % p;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 93440
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

typedef long long int ll;
const int MAX_N = 100010;
struct UnionFind {
    int node[MAX_N];
    UnionFind() {}
    void init() {
        memset(node, -1, sizeof(node));
    }

    int find(int x) {
        return (node[x] < 0 ? x : node[x] = find(node[x]));
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    int size(int x) {
        return -node[find(x)];
    }

    void unite(int x, int y) {
        x = find(x), y = find(y);
        if(same(x, y)) return;
        // y を x に統合
        node[x] += node[y];
        node[y] = x;
    }
};

struct Query {
    // q: mark -> 0, query -> 1
    int q, v;
    Query() {}
    Query(int a, int b) : q(a), v(b) {}
};

vector< vector<int> > G;
int N, Q, mark[100010], parent[100010];
Query qs[100010];
UnionFind uf;

int main() {
    while(1) {
        // init
        uf.init();
        memset(mark, 0, sizeof(mark));
        memset(parent, -1, sizeof(parent));
        G.clear();

        scanf("%d%d", &N, &Q);
        if(N == Q && Q == 0) break;
        G.resize(N);

        for(int i=1; i<N; i++) {
            int par; scanf("%d", &par); par--;
            G[par].push_back(i);
            parent[i] = par;
        }

        for(int i=0; i<Q; i++) {
            char mode; int v;
            scanf(" %c%d", &mode, &v); v--;
            qs[i] = Query(mode == 'Q', v);
            if(mode == 'M') mark[v]++;
        }

        for(int i=1; i<N; i++) {
            if(!mark[i]) {
                uf.unite(parent[i], i);
            }
        }

        ll ans = 0;
        for(int i=Q-1; i>=0; i--) {
            // mark
            if(qs[i].q == 0) {
                if(--mark[qs[i].v] == 0) {
                    int par = parent[qs[i].v];
                    if(par < 0) continue;
                    uf.unite(par, qs[i].v);
                }
            }
            // query
            else {
                ans += uf.find(qs[i].v) + 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}


Measured memory_bytes: 9872
N = int(input())
S = input()

dp = [[0] * (N + 1) for _ in range(N + 1)]
ans = 0

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if i >= j: break
        if S[i] == S[j]:
            dp[i][j] = min(1 + dp[i + 1][j + 1], j - i)
            if dp[i][j] > ans:
                ans = dp[i][j]
print(ans)


Measured memory_bytes: 229676
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
      double a = sc.nextDouble();
      double b = sc.nextDouble();
      int n = sc.nextInt();
      int sum = 0;
      a %= b;
      for (int i = 0; i < n; i++) {
        sum += a*10/b;
        a = a*10%b;
      }
      System.out.println(sum);
    }
  }
}

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

using Int = int;
using Bool = bool;
template <class T>
using Vector = std::vector<T>;

struct Circle {
    Int x, y, r;
    Circle(Int x = 0, Int y = 0, Int r = 0) : x(x), y(y), r(r) {}
};

Bool intersect(Circle a, Circle b) {
    Int dx = a.x - b.x, dy = a.y - b.y, sr = a.r + b.r;
    return dx * dx + dy * dy < sr * sr;
}

constexpr Int N = 24;
Vector<Int> dp(1 << N);
Vector<Int> c;
Vector<Vector<Int>> on;

Int dfs(Int b) {
    if (dp[b] >= 0) return dp[b];

    dp[b] = __builtin_popcountll(b);
    Vector<Bool> isleaf(N, false);

    for (Int v = N - 1; v >= 0; --v) {
        if ((b >> v) & 1) {
            isleaf[v] = true;
            for (Int u : on[v]) {
                isleaf[u] = false;
            }
        }
    }

    for (Int v = 0; v < N; ++v) {
        for (Int u = 0; u < v; ++u) {
            if (isleaf[u] && isleaf[v] && c[u] == c[v]) {
                dp[b] = std::min(dp[b], dfs(b - (1 << u) - (1 << v)));
            }
        }
    }
    return dp[b];
}

Bool solve() {
    Int n;
    std::cin >> n;
    if (n == 0) return false;

    Vector<Circle> d(n);
    c.resize(n);
    for (Int i = 0; i < n; ++i) {
        std::cin >> d[i].x >> d[i].y >> d[i].r >> c[i];
    }

    on.clear();
    on.resize(n);
    for (Int v = 0; v < n; ++v) {
        for (Int u = 0; u < v; ++u) {
            if (intersect(d[u], d[v])) {
                on[u].push_back(v);
            }
        }
    }

    std::fill(dp.begin(), dp.end(), -1);
    std::cout << n - dfs((1 << n) - 1) << std::endl;
    return true;
}

int main() {
    while (solve()) {}
    return 0;
}



Measured memory_bytes: 68092
// #pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define String std::string
#define fi first
#define se second
#define mp std::make_pair
#define Pair std::pair<int, int>
#define Map std::map< int, int >
#define Vector std::vector<int>
 
using std::cin;
using std::cout;
using std::endl;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int N = 100000 + 5;
const int M = 1000 + 5;
const int K = 1e7 + 5;
const int MOD = 1e9 + 7;
const int inv2 = 500000004;
const int LOG = 40;
const ull BASE = 19260817;
const int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };
const int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };
const double PI = acos(-1);

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<class T>
inline T readT() {
    T res = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + ch - '0';
    return res * f;
}
#define read readT<int>

namespace Comb{
inline void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
    if (!b) g = a, x = 1, y = 0;
    else exgcd(b, a % b, g, y, x), y -= x * (a / b);
}
 
inline ll inv(ll a) {
    ll g, res, tmp;
    exgcd(a, MOD, g, res, tmp);
    return ((res % MOD) + MOD) % MOD;
}
 
ll f[N], invFact[N];
 
inline void prepare() {
    f[0] = 1;
    int n = 200000;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD;
    invFact[n] = inv(f[n]);
    for (int i = n - 1; i >= 1; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}
 
inline ll C(int n, int m) {
    if (!m) return 1;
    if (n == m) return 1;
    if (m > n) return 0;
    if (m < 0) return 0;
    return f[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}
}

int n, ans, a, b, dis[N];
bool flag;
std::vector<int> g[N];

void dfs(int x, int fa, int dep) {
    if (!flag) dis[x] = dep;
    else if (dep >= dis[x]) return (void)(ans = std::max(ans, dis[x]));
    for (auto to : g[x]) {
        if (to == fa) continue;
        dfs(to, x, dep + 1);
    }
    if (flag && g[x].size() == 1) ans = std::max(ans, dis[x] - 1);
}

int main() {
    cin >> n >> a >> b;
    // if (a == b) return puts("0"), 0;
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(b, -1, 0);
    flag = true;
    dfs(a, -1, 0);
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 12544
X=int(input())
#ldp=[0 for i in range(X+1)]
ldp=[0 for i in range(max(106,X+1))]
#if X>=100:
for i in range(100,106):
    ldp[i]=1
if X>=105:
    for i in range(106,X+1):
        if sum(ldp[i-105:i-99])>=1:
            ldp[i]=1

print(ldp[X])


Measured memory_bytes: 3864
#include <iostream>
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;

void solve(std::string S, std::string T){
    int count = 0;
    REP(i, 3) if (S[i] == T[i]) count++;
    cout << count << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::string S;
    std::cin >> S;
    std::string T;
    std::cin >> T;
    solve(S, T);
    return 0;
}


Measured memory_bytes: 256
url = "https://atcoder.jp/contests/abc161/tasks/abc161_c"

def main():
    n, m = list(map(int, input().split()))

    anss = []
    ans = 1
    while ans != 0:
        if n > m:
            ans = n % m
            n = ans
        else:
            ans = abs(n - m)
            n = ans
        if ans in anss:
            break
        else:
            anss.append(ans)
    print(min(anss))


if __name__ == '__main__':
    main()




Measured memory_bytes: 2940
#include<stdio.h>
int main(void)
{
	int a,b,c,d,e,f,g;
	scanf("%d%d%d",&a,&b,&c);
	g=a+b;
	e=a+c;
	f=b+c;
	if(e<g){
		d=g;
		g=e;
		e=d;
		}
	if(f<e){
		d=e;
		e=f;
		f=e;
		}
	if(e<g){
		d=g;
		g=e;
		e=d;
		}
	printf("%d\n",g);
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pp;
#define MAXN 605
#define MAXM 1005
#define MAXP 50
#define A first
#define B second
#define MP make_pair
#define PB push_back
const ll INF = 2e9+13;
const ll MOD = 1e9+7;
const ll BASE = 5839283;
int N;
char ar[MAXN][MAXN];

inline ll madd(ll a, ll b) { return (a+b)%MOD; }
inline ll mmul(ll a, ll b) { return (a*b)%MOD; }

ll po[MAXN], ipo[MAXN];
ll pmod(ll a, ll b)
{
	ll ret = 1LL;
	while(b) {
		if(b%2) ret = mmul(ret, a);
		a = mmul(a, a);
		b /= 2LL;
	} return ret;
}

ll rha[MAXN][MAXN];
ll cha[MAXN][MAXN];

ll get1(int row, int l, int r)
{
	ll ha = madd(rha[row][r], MOD-rha[row][l-1]);
	return mmul(ha, ipo[l-1]);
}

ll get2(int col, int l, int r)
{
	ll ha = madd(cha[r][col], MOD-cha[l-1][col]);
	return mmul(ha, ipo[l-1]);
}
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for(int i=1; i<=N; i++) {
		string s; cin >> s;
		for(int j=1; j<=N; j++) {
			ar[i][j] = s[j-1];
			ar[i+N][j] = s[j-1];	
			ar[i+N][j+N] = s[j-1];
			ar[i][j+N] = s[j-1];
		}
	}
	po[0] = ipo[0] = 1;
	for(int i=1; i<MAXN; i++) {
		po[i] = mmul(po[i-1], BASE);
		ipo[i] = pmod(po[i], MOD-2);
	}
	for(int i=1; i<2*N; i++) 
		for(int j=1; j<2*N; j++) 
			rha[i][j] = madd(rha[i][j-1], mmul(ar[i][j]-'a'+1, po[j-1]));
			
		
	for(int j=1; j<2*N; j++) 
		for(int i=1; i<2*N; i++) 
			cha[i][j] = madd(cha[i-1][j], mmul(ar[i][j]-'a'+1, po[i-1]));

	// now try
	int ans = 0;
	for(int i=1; i<=N; i++) { // A = i-1
		for(int j=1; j<=N; j++) { // B = j-1
			bool f = 0;
			for(int k=0; k<N-1; k++) {
				if(get1(i+k, j+k+1, j+N-1) != get2(j+k, i+k+1, i+N-1)) {
					f = 1;
					break;
				}
			}
			if(!f) {
				ans++;
			}
		}
	}
	cout << ans << endl;
	
}

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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

Int dp[1001][1001];

int main() {
    Int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (Int i = 0; i < h; i++) {
        cin >> s[i];
    }
    dp[0][0] = 1;
    for (Int i = 0; i < h; i++) {
        for (Int j = 0; j < w; j++) {
            if (s[i][j] == '#') continue;
            dp[i][j + 1] += dp[i][j];
            dp[i][j + 1] %= mod;
            dp[i + 1][j] += dp[i][j];
            dp[i + 1][j] %= mod;
        }
    }
    dump(dp[h - 1][w - 1]);
    return 0;
}

Measured memory_bytes: 9088
N=int(input())
A=list(map(int,input().split()))

mod=10**9+7

S=[A[0]]
for i in range(1,N):
    S.append(S[-1]^A[i])

if S[-1]==0:
    sss=max(S)
    data=[[] for i in range(sss+1)]

    for i in range(N):
        data[S[i]].append(i)

    count_0=[0]*N
    for u in data[0]:
        count_0[u]+=1
    for i in range(1,N):
        count_0[i]+=count_0[i-1]
    
    ans=pow(2,len(data[0])-1,mod)

    for i in range(1,sss+1):
        if data[i]:
            h=data[i]
            l=len(h)
            dp=[1,1]
            for j in range(1,l):
                d=[0,0]
                num=count_0[h[j]]-count_0[h[j-1]]
                d[0]=(dp[0]+dp[1]*num)%mod
                d[1]=(dp[0]+dp[1]+dp[1]*num)%mod
                dp=d
            ans=(ans+dp[1])%mod

else:
    qqq=S[-1]
    h=[]
    count_0=[0]*N
    for i in range(N):
        if S[i]==qqq:
            h.append(i)
        elif S[i]==0:
            count_0[i]=1

    for i in range(1,N):
        count_0[i]+=count_0[i-1]
    
    ans=0

    l=len(h)
    dp=[1,1]
    for j in range(1,l):
        d=[0,0]
        num=count_0[h[j]]-count_0[h[j-1]]
        d[0]=(dp[0]+dp[1]*num)%mod
        d[1]=(dp[0]+dp[1]+dp[1]*num)%mod
        dp=d
    ans=(ans+dp[0])%mod
print(ans)        

Measured memory_bytes: 134624
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int h0,m0,s0,t0,h1,m1,s1,t1,T = 0,H = 0,M = 0,S = 0,a;
    for(int i = 0;i < 3;i++){
        scanf("%d%d%d%d%d%d",&h0,&m0,&s0,&h1,&m1,&s1);
        t0 = h0 * 3600 + m0 * 60 + s0;
        t1 = h1 * 3600 + m1 * 60 + s1;
        T = t1 - t0;
        S = T % 60;
        a = T - S;
        M = a / 60;
        if(M >= 60){
            H = M / 60;
            M = M - 60 * H;
        }
        printf("%d %d %d\n",H,M,S);
    }


    return 0;
}

Measured memory_bytes: 1188
use proconio::{input, fastout};
#[fastout]
fn main() {
  input!{
    n:usize,
    a:[usize;n]
  }
  let mut x = vec![0; 100000+2];
  for i in 0..n {
      x[a[i] + 1] += 1;
      x[a[i]] += 1;
      if a[i] != 0 { x[a[i]-1] += 1; }
  }
  println!("{}",x.iter().max().unwrap());
}


Measured memory_bytes: 3792
#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define int long long
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
int n,sum;
int a[200010];
int b[200010];
int h[200010];
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],h[a[i]]++;
	for(int i=1;i<=n;i++){
		b[i]=h[i]*(h[i]-1)/2;
		sum+=b[i];
	}
	for(int i=1;i<=n;i++){
		cout<<sum-b[a[i]]+(h[a[i]]-1)*(h[a[i]]-2)/2<<endl;
	}

	return 0;
}


Measured memory_bytes: 6272
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    int a=0,m=0;
    for(int i=0;i<4;i++){
        if(s[i]=='+'){
            a++;
        }
        else{
            m++;
        }
    }
    cout<<a-m<<endl;
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8

S = input()
word = []
for i in S:
	word.append(i)
ans = list(set(word))
a = 0
for i in word:
    if i == word[0]:
        a += 1
    else:
        pass

if len(ans) == 2:
    if a == 2:
        print("Yes")
    else:
        print("No")
else:
    print("No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
    int n, m;
    cin >> n >> m;
    vector<int> vec(m);
    for (int i = 0; i < m; i++)
    {
        cin >> vec.at(i);
    }
    long long sum = 0;

    for (int i = 0; i < m; i++)
    {
        sum += vec.at(i);
    }

    long long r = n - sum;

    if (r < 0)
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << r << endl;
    }
    return 0;
}


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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> p(n);
	rep(i, n) cin >> p[i];
	double ans = 0.0;
	vector<double> tot(n);
	rep(i, n) {
		if(i==0) tot[i] = (double) (p[i] + 1.0) / 2.0;
		else tot[i] = tot[i-1] + (double) (p[i] + 1.0) / 2.0;
	}
	rep(i, n-k+1) {
		double now;
		if(i == 0) now = tot[i+k-1];
		else now = tot[i+k-1] - tot[i-1];
		ans = max(ans, now);
	}
	printf("%.10f\n", ans);
	return 0;
}

Measured memory_bytes: 2560
import sys
X, N = map(int, sys.stdin.readline().rstrip().split())
P = list(map(int, sys.stdin.readline().rstrip().split()))
P = set(P)
for i in range(1000):
    if X - i not in P:
        print(X - i)
        exit()
    if X + i not in P:
        print(X + i)
        exit()


Measured memory_bytes: 9180
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for (int i = 0; i < (int)c; i++)
#define all(v) v.begin(), v.end()
const int inf = 1000000000; //10^9
using ll = long long;
using P = pair<int,int>;
//加算代入演算子は+=！！！！！

int main() {
    string a, x, c;
    cin >> a >> x >> c;
    cout <<  "A" << (char)x.at(0) << "C" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
long long n,k,h;
int a[100];
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
     cin>>n>>k;
     for(int i=1;i<=n;i++)
     {
        cin>>a[i];
     }
     sort(a+1,a+n+1,cmp);
     for(int i=1;i<=k;i++)
     {
        h=h+a[i];
     }
     cout<<h<<endl;
    return 0;
}

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

int main() {
  int n; cin >> n;
  vector<int> arr(n);
  for (auto &a : arr) cin >> a;
  set<int> s;
  for (auto &a : arr) s.insert(a);
  cout << s.size() << endl;
  return 0;
}


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

using namespace std;

typedef vector<int> VI;

int main ( void )
{
	int n, m;
	while ( cin >> n >> m, n | m ) {
		int t_sum = 0, h_sum = 0;
		VI t_hand( n ), h_hand( m );

		for ( int i = 0; i < n; ++i ) {
			cin >> t_hand[i];
			t_sum += t_hand[i];
		}
		for ( int i = 0; i < m; ++i ) {
			cin >> h_hand[i];
			h_sum += h_hand[i];
		}

		int t_card = 101, h_card = 101;

		for ( int i = 0; i < n; ++i ) {
			for ( int j = 0; j < m; ++j ) {
				int t = t_sum - t_hand[i] + h_hand[j],
					h = h_sum - h_hand[j] + t_hand[i];
				if ( t == h && ( t_hand[i] + h_hand[j] < t_card + h_card ) ) {
					t_card = t_hand[i];
					h_card = h_hand[j];
				}
			}
		}

		if ( t_card + h_card == 202 ) {
			cout << -1 << endl;
		}
		else {
			cout << t_card << ' ' << h_card << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1196
import collections
import math

N = input()

A = [int(i) for i in raw_input().split()]

ruiseki = [0]

sum_ = 0

for i in range(N):
    sum_ += A[i]
    ruiseki.append(sum_)


c = collections.Counter(ruiseki)
#print(c)

ret = 0


for k, v in c.items():
    if(v>1):
        ret += v * (v-1) /2
 #       print(k,v,ret)

print(ret)


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


static const int MAX_NUM = 10001;

int FindRoot(int elem[], int target)
{
    int parent;

    parent = target;
    for (;;) {
        if (parent == elem[parent]) {
            break;
        }
        else {
            parent = elem[parent];
        }
    }

    return parent;
}

void Unite(int elem[], int t1, int t2)
{
    int p1, p2;

    p1 = FindRoot(elem, t1);
    p2 = FindRoot(elem, t2);

    elem[p2] = p1;

    return;
}

bool Same(int elem[], int t1, int t2)
{
    bool ret;
    int p1, p2;

    p1 = FindRoot(elem, t1);
    p2 = FindRoot(elem, t2);

    if (p1 == p2) {
        ret = true;
    }
    else {
        ret = false;
    }

    return ret;
}

int main(void)
{
    int i;
    int num, qnum;
    int q;
    int t1, t2;
    int elem[MAX_NUM];

    scanf("%d %d", &num, &qnum);
    for (i = 1; i <= num; i++) {
        elem[i] = i;
    }

    for (i = 0; i < qnum; i++) {
        scanf("%d %d %d", &q, &t1, &t2);
        switch (q) {
        case 0 :
            Unite(elem, t1, t2);
            break;
        case 1 :
            if (Same(elem, t1, t2) == true) {
                printf("1\n");
            }
            else {
                printf("0\n");
            }
            break;
        default :
            break;
        }
    }
    return 0;
}

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

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vllin3(a,b,c,n) vll (a)(n);vll (b)(n);vll (c)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vlling(x,n) (x).assign(n,0);FOR(i,0,n-1){cin >>(x)[i];}
#define vlling2(a,b,n) (a).assign(n,0);(b).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vlling3(a,b,c,n) (a).assign(n,0);(b).assign(n,0);(c).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=998244353;
ll INF=100000000000001;
vector<ll> value; // ノードの値を持つ配列
ll N;             // 葉の数
 
void update(ll i, ll x) {
    // i 番目の葉の値を x に変える
    i += N - 1; // i 番目の葉のノード番号
    value[i] = x;
    while (i > 0) {
        i = (i - 1) / 2; // ノード i の親ノードの番号に変える
        value[i] = min(value[i * 2 + 1],
                       value[i * 2 + 2]); // 左右の子の min を計算しなおす
    }
}
 
ll query(ll a, ll b, ll k, ll l, ll r) {
    // [a, b) の区間に対するクエリについて
    // ノード k （区間 [l, r) 担当）が答える
    if (r <= a || b <= l) return INF; // 区間が被らない場合は INF を返す
    if (a <= l && r <= b)
        return value[k]; // ノード k の担当範囲がクエリ区間 [a, b)
                         // に完全に含まれる
    else {
        ll c1 = query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子に値を聞く
        ll c2 = query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子に値を聞く
        return min(c1, c2); // 左右の子の値の min を取る
    }
}
signed main(){
    llin(m);
    llin(n);
    llin(mm);
    llin(nn);
    sal((nn==1?1:0))
}


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

using namespace std;

int main(void)
{
    long A, B;
    cin >> A >> B;

    int count = 1;

    long L, S;

    if (A > B)
    {
        L = A;
        S = B;
    }
    else
    {
        L = B;
        S = A;
    }

    int f = 0;
    while (S % 2 == 0)
    {
        if (f == 0)
        {
            if (L % 2 == 0)
            {
                count++;
            }
            f = 1;
        }
        S /= 2;
    }

    for (long i = 3; i * i <= S; i += 2)
    {
        int flag = 0;
        while (S % i == 0)
        {
            if (flag == 0)
            {
                if (L % i == 0)
                {
                    count++;
                }
                flag = 1;
            }
            S /= i;
        }
    }
    if (S != 1)
    {
        if (L % S == 0)
        {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#define div 1000000000+7 
using namespace std;
typedef long long ll;

int main(){
  ll count = 0;
  string s;
  cin >> s;
  for(int i = 1; i < s.length(); i++){
    if((s[i] == 'W' && s[i-1] == 'B') || (s[i] == 'B' && s[i-1] == 'W')){
      count++;
    }else{
    }
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

int main(){
    int a,b;
    int sum,dec,pro;
    int max;
    scanf("%d %d",&a,&b);

    sum = a+b;
    dec = a-b;
    pro = a*b;
    
    max = sum;
    if(max<dec)
        max = dec;
    if(max<pro)
        max = pro;

    printf("%d\n",max);

    return 0;
}

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

int main(){
  std::string sent;
  int gyou,num=0;
  std::cin >> gyou;
  getline(std::cin, sent);
  for(int i=0;i<gyou;++i){
    num=0;
    getline(std::cin, sent);
    std::string bef="Hoshino",aft="Hoshina";
    while(num!=-1){
      num=(int)(sent.find(bef));
      if(num!=-1){
      sent.replace(num,bef.size(),aft);
      }
    }
    std::cout << sent << std::endl;
  }
  return 0; 
}

Measured memory_bytes: 1216
C = []
C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))
C.append(list(map(int, input().split())))

B = [[0,0,0],[0,0,0],[0,0,0]]
N = int(input())
for i in range(N):
  b = int(input())
  for j in range(3):
    for k in range(3):
      if C[j][k]==b:
        B[j][k]=1
  
ans = 'No'
#Row
for j in range(3):
  if B[j][0] == 1 and B[j][1] == 1 and B[j][2] == 1:
    ans = "Yes"

#Col
for j in range(3):
  if B[0][j] == 1 and B[1][j] == 1 and B[2][j] == 1:
    ans = "Yes"

if B[0][0] == 1 and B[1][1] == 1 and B[2][2] == 1:
  ans ="Yes"
if B[0][2] == 1 and B[1][1] == 1 and B[2][0] == 1:
  ans = 'Yes'

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
//なぜWAかわからない07.27
int main(){
    int N;
    cin >> N;

    vector<long long> a(N+1); 
    vector<long long> b(N);
    for (int i = 0; i < N+1; i++){
        cin >> a.at(i);
    }
    for (int i = 0; i < N; i++){
        cin >> b.at(i);
    }

    long long count = 0;
    long long tmp = 0; 
    for (int i = 0; i < N; i++){
        if (a.at(i) > b.at(i)){
            count += b.at(i);
        }

        else{
            count += a.at(i);
            tmp = b.at(i) - a.at(i);
        
            if (a.at(i+1) > tmp){
                long long s = a.at(i+1) - tmp;
                a.at(i+1) = s;
                count += tmp;
            }
            else{
                count += a.at(i+1);
                a.at(i+1) = 0;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
char s[10],ns[10];
int i=0,j=0;
scanf("%s",s);

while(s[i]!='\0')
{
if(s[i]=='B')
{
if(j==0);
else
j--;
}
else
ns[j++]=s[i];
i++;
}
ns[j]='\0';
printf("%s",ns);
}


Measured memory_bytes: 256
#include<cstdio>
#include <iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<functional>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<numeric>

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

ll N, A, B;
ll X[100010];

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

	ll ans = 0;
	for (int i = 1; i < N; i++) {
		ll a = X[i] - X[i - 1];
		ans += min(a*A,B);
	}
	cout << ans << endl;
	return 0;
}


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

int main() {

	string S;
    cin >> S; 
	int s = S.size();
	int count = 0;
	for(int i=0;i<s/2;i++){
		if(S.at(i) != S.at(s-1-i)){
			count++;
		}
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

string s;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	ll k;
	cin >> s >> k;
	ll n = s.size();
	
	if(s[0] == s[n-1]){
		bool flag = true;
		rep(i, 1, n){if(s[i] != s[0]){flag = false;}}
		if(flag){print(n*k/2)}
		else{
			ll cnts = 1;
			while(s[cnts] == s[0]){cnts++;}
			ll cnte = 1;
			while(s[n-1-cnte] == s[n-1]){cnte++;}
			s += s;
			s = s.substr(cnts, n);
			vector<ll> c;
			char b = 'A';
			ll cnt = 0;
			rep(i, 0, n){
				if(s[i] == b){cnt++;}
				else{
					c.push_back(cnt);
					cnt = 1;
					b = s[i];
				}
			}
			
			ll ans = 0;
			rep(i, 0, c.size()){ans += c[i]/2;}
			ans *= k;
			ans += (cnt/2)*(k-1);
			ans += cnts/2;
			ans += cnte/2;
			print(ans)
		}
	}
	else{
		ll ans = 0;
		for(ll i = 1; i < n; i++){
			if(s[i] == s[i-1]){
				ans++;
				i++;
			}
		}
		print(ans*k)
	}
	
	return 0;
}

Measured memory_bytes: 380
import heapq

N,M = input().split()
N = int(N)
M = int(M)
price_list = input().split()
 
heap_list = []
for i in price_list:
  heapq.heappush(heap_list, int(i) * (-1))

for _ in range(M):
  max_num = heapq.heappop(heap_list)
  heapq.heappush(heap_list, int(max_num /2))
  
print(sum(heap_list) * (-1))

Measured memory_bytes: 14228
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
#include <stdio.h>
using namespace std;

long long MOD = 1000000007;

int main() {
    
    int N;
    cin >> N;
    vector<long long> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];
    }
    sort( A.begin(), A.end() );

    deque<long long> dq;
    for ( int i = 0; i < N; i++ ) {
        dq.push_back(A[i]);
    }

    long long ans1 = 0;
    long long a,b;
    a = b = dq.front();
    dq.pop_front();

    bool t = true;
    while ( !dq.empty() ) {
        long long c,d;
        if ( t ) {
            c = dq.back();
            dq.pop_back();
            if ( dq.empty() ) {
                ans1 += abs(a-c); break;
            }
            d = dq.back();
            dq.pop_back();

            // cout << c << " " << d << endl;

            ans1 += abs(a-c) + abs(b-d);
            a = c; b = d;
        }
        else {
            c = dq.front();
            dq.pop_front();
            if ( dq.empty() ) {
                ans1 += abs(a-c); break;
            }
            d = dq.front();
            dq.pop_front();

            // cout << c << " " << d << endl;

            ans1 += abs(a-c) + abs(b-d);
            a = c; b = d;
        }
        t = !t;
    }

    for ( int i = 0; i < N; i++ ) {
        dq.push_back(A[i]);
    }

    
    long long ans2 = 0;
    a = b = dq.back();
    dq.pop_back();

    t = false;
    while ( !dq.empty() ) {
        long long c,d;
        if ( t ) {
            c = dq.back();
            dq.pop_back();
            if ( dq.empty() ) {
                ans2 += abs(a-c); break;
            }
            d = dq.back();
            dq.pop_back();

            // cout << c << " " << d << endl;

            ans2 += abs(a-c) + abs(b-d);
            a = c; b = d;
        }
        else {
            c = dq.front();
            dq.pop_front();
            if ( dq.empty() ) {
                ans2 += abs(a-c); break;
            }
            d = dq.front();
            dq.pop_front();

            // cout << c << " " << d << endl;

            ans2 += abs(a-c) + abs(b-d);
            a = c; b = d;
        }
        t = !t;
    }


    cout << max(ans1,ans2) << endl;

    return 0;
}


Measured memory_bytes: 1820
#include<bits/stdc++.h>
#define GO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
const int Max = 2e3 + 5;
const int Mod = 1e9 + 7;

int main()
{
	GO;
	int n;
	cin >> n;
	vec a;
	ll sum = 0;
	for (int i = 0; i < n; i++)
	{
		ll x;
		cin >> x;
		a.push_back(x);
		sum += (i & 1 ? -x : x);
	}
	sum /= 2;
	for (int i = 0; i < n; i++)
	{
		cout << 2*sum << ' ';
		sum = a[i] - sum;
	}
	return 0;
}

Measured memory_bytes: 2292
#include <bits/stdc++.h>
using namespace std;
#define boost  ios_base::sync_with_stdio(0);
#define N 1000
#define ll long long int
#define pb push_back
#define f first
#define s second
#define fo(i,a,b) for(i = a; i < b; i++)
#define foe(i, a,b) for(i = a; i <= b; i++)
#define tc long long int t; cin >> t; while(t--)
#define vect vector <ll>
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll>>
#define be begin
#define en end
ll mod = 1e9+7;

int main(){
boost;
ll i;
ll n,m;
cin >> n >> m;
ll dp[n+1][m+1];
char x;
ll j;
for(i = 1; i <=n; i++){
for(j = 1; j <= m; j++){
  cin >> x;
if(x == '#'){
dp[i][j] = 0;
}
else{
dp[i][j] = -1;
}
}
}
dp[1][1]=1;
for(i = 2; i<= n; i++){
if(dp[i][1] != 0 && dp[i-1][1] != 0){
dp[i][1] = 1;
}
else dp[i][1]=0;
}
for(i = 2; i<= m; i++){
if(dp[1][i] != 0 && dp[1][i-1] != 0){
dp[1][i] = 1;}
else dp[1][i]=0;
}

for(i = 2; i <= n; i++){
for(j = 2; j <= m; j++){
if(dp[i][j] != 0){
dp[i][j] = (dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
}
}
}

/*for(int i=1;i<=n;i++)
{
  for(int j=1;j<=m;j++)
  cout<<dp[i][j]<<" ";
  cout<<"\n";
}*/

cout << dp[n][m]% mod;

return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define hash dhsjakhd
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;

unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
std::mt19937 eng(seed);

uniform_int_distribution<> DD(0, (1ll << 31));

ll random2(){
    return (ll(DD(eng))*(1ll << 31) + ll(DD(eng))) & ((1ll << 62ll)-1);
}

ll n,m,T,k,q;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const ll MAXN = 300001;
const ll MAXD = 1000001;

ld mob[MAXD] = {0};
vector<vi> PF(MAXD, vi());

bool inp[MAXD] ={0};

bool notp[MAXD] = {0};

ll totmob[MAXD] = {0};

vl A;

vector<vi> F(MAXD, vi());

const ll inv2 = 499122177;

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

    //freopen("input.txt","r",stdin);
    //freopen("autput.txt","w",stdout);
    ll a,b,c,d,e;
/*
    rep(c1,1,mod){
        ll c2 = c1;
        if((c2*2 )% mod == 1)cerr << c2 << "  !!!!!!\n";
    }
*/
    notp[1] = 1;
    rep(c1,2,MAXD){
        if(!notp[c1]){
            PF[c1].push_back(c1);
            for(ll c2 = c1+c1; c2 < MAXD; c2+=c1){
                PF[c2].push_back(c1);
                notp[c2] = 1;
            }
        }
    }

    rep(c1,1,MAXD){
        mob[c1] += 1.0 / ld(c1);
        for(int c2 = c1+c1; c2 < MAXD; c2 += c1){
            mob[c2] -= mob[c1];
        }

    }

    cin >> n;
    rep(c1,0,n){
        cin >> a;
        inp[a] = 1;
        A.push_back(a);
    }

    rep(c1,1,MAXD){
        for(int c2 = c1; c2 < MAXD; c2+=c1){
            if(inp[c2]){
                F[c2].push_back(c1);
            }
        }
    }


    rep(c1,0,n){
        trav(f,F[A[c1]]){
            totmob[f] += round(A[c1] * mob[f]);
            totmob[f] %= mod;
            //cerr << f << " " << totmob[f] << "\n";
        }
    }

    ll ans = 0;

    rep(c1,0,n){
        trav(f,F[A[c1]]){
            ans += A[c1] * totmob[f];
            ans %= mod;
        }
        ans -= A[c1];
        ans += mod;
        ans %= mod;
    }
    cout << (ans*inv2)%mod << "\n";

    return 0;
}


Measured memory_bytes: 127856
#include<stdio.h>
#include<string.h>
void LCSLength(void);

char X[1001], Y[1001];

int c[1001][1001];

int n, m;

main(){
  int i, q;

  scanf("%d",&q);

  for(i = 0; i < q; i++){

    scanf("%s", X);

    scanf("%s", Y);

    LCSLength();

    printf("%d\n", c[m][n]);
  }

  return 0;
}

void LCSLength(void){

  int i, j;

  m = strlen(X);

  n = strlen(Y);

  for(i = 1; i <= m; i++){

    c[i][0] = 0;

  }

  for(j = 0; j <= n; j++){

    c[0][j] = 0;

  }

  for(i = 1; i <= m; i++){
    for(j = 1; j <= n; j++){

      if(X[i-1] == Y[j-1])
      c[i][j] = c[i - 1][j - 1] + 1;



      else  if(c[i - 1][j] >= c[i][j-1])

	c[i][j] = c[i - 1][j];

      else c[i][j] = c[i][j -1];
    }
  }
}

Measured memory_bytes: 4516
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef vector<ull> vul;
#define For(i, n) for(ll i = 0; i < n; i++)
#define len(n) (ll)(n).size()
#define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define Sort(a) sort(a.begin(), a.end())

ll dp[(ll)1e5];
vl h;
ll n, k;

int main() {
    FAST_IO;
    cin >> n >> k;
    h.resize(n);
    For(i, n) cin >> h[i];
    for (ll i = 1; i < n; i++) dp[i] = -1;
    For(i, n) {
        for (ll z = 1; z <= k && i + z < n; z++) {
            if (dp[i + z] != -1) dp[i + z] = min(dp[i + z], dp[i] + abs(h[i] - h[i + z]));
            else dp[i + z] = dp[i] + abs(h[i + z] - h[i]);
        }
    }
    cout << dp[n - 1] << '\n';
    return 0;
}

Measured memory_bytes: 4780
N = int(input())
score = [list(map(int, input().split())) for _ in range(N)]
players = [0 for _ in range(N)]
for play in list(zip(*score)):
    for i, p in enumerate(play):
        if play.count(p) == 1:
            players[i] += p
print(*players, sep='\n')

Measured memory_bytes: 7644
//#include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<numeric>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<map>
#include<stack>
#include<queue>
#include<ctype.h>
#include <fstream>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dy[4]={0,1,0,-1};
//----------program from here----------

int main(){
    int a=0, b=0, c;
    cin >> a >> b;
    c=b-a;
    cout << (c*(c-1))/2-a << endl;
}

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

int r[100005] , p[100005];

void makeSet(int x){
  for(int i=1;i<=x;i++){
    p[i]=i;
    r[i]=0;
  }
}

int findSet(int x){
  if(x != p[x]){
    p[x] = findSet(p[x]);
  }
  return(p[x]);
}

void link(int x,int y){
  int X = findSet(x);
  int Y = findSet(y);
  if(r[X] > r[Y]){
    p[Y] = X;
  } else {
    p[X] = Y;
    if(r[X] == r[Y]){
      r[Y]++;
    }
  }
}

signed main(){
  int n , m , x , y , p[100005] , ans=0;
  cin>>n>>m;

  makeSet(n);

  for(int i=1;i<=n;i++){
    cin>>p[i];
  }
  
  for(int i=0;i<m;i++){
    cin>>x>>y;
    link(x , y);
  }

  for(int i=1;i<=n;i++){
    if(findSet(i) == findSet(p[i])){
      ans++;
    }
  }

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


Measured memory_bytes: 1408
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <cctype>
#include <cassert>
#include <queue>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,b,e) for(int i = (b); i <= (e); i++)
#define INF (1001001001)
#define EPS (1e-15)

#define pr(x) do{cerr << (#x) << " = " << (x) << endl;}while(0)
#define pri(x,i) do{cerr << (#x) << "[" << i << "] = " << (x[i]) << endl;}while(0)
#define pra(x) do{rep(__i,(x).size()) pri(x,__i);}while(0)
#define pran(x,n) do{rep(__i,n) pri(x,__i);}while(0)
#define pral(x) do{cerr << (#x) << " =";rep(__i,(x).size()) cerr<<" "<<(x[__i]);cerr<<endl;}while(0)
#define prar(x,b,e) do{repr(__i,b,e) pri(x,__i);}while(0)

typedef long long ll;
typedef pair<int, int> pint;
typedef vector<int> vint;
typedef vector<pint> vpint;

template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class T,size_t n> ostream& operator<<(ostream &os, const array<T,n> &t) {os<<"{"; rep(i,n) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool CHMAX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool CHMIN(T &l,const T &r){return l>r?l=r,1:0;}

ll MOD = 1000000007;

function<void(int,int)> tensi_no_3p=[&](int v,int d){
};

int in() {
	int a;
	scanf("%d ", &a);
	return a;
}

int main() {
	string s;
	int K;
	cin >> s >> K;
	vector<string> tops(K);
	rep(i,K) tops[i] = "~";
	int len = s.size();
	rep(i, len) repr(k, 1, min(5, len - i)) {
		string ss = s.substr(i, k);
		rep(t, tops.size()) {
			if (ss == tops[t]) break;
			if (ss < tops[t]) {
				//pr(ss);
				for (int u = tops.size() - 1; u >= t + 1; u--) tops[u] = tops[u - 1];
				tops[t] = ss;
				break;
			}
		}
	}
	cout << tops[K - 1] << endl;
	return 0;
}


Measured memory_bytes: 256