akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import java.util.Map.Entry;
import java.util.stream.Collectors;

/**
 * Main
 */
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		String[] S = new String[N];
		for (int i = 0; i < N; i++) {
			S[i] = sc.next();
		}
		sc.close();

		int maxDup = 1;
		Map<String, Integer> m = new HashMap<String, Integer>();

		for (String s: S) {
			int v;
			if (m.containsKey(s)) {
				// Mapに登録済み
				v = m.get(s) + 1;
				if (v > maxDup) {
					maxDup = v;
				}
			} else {
				// Mapに未登録
				v = 1;
			}
			m.put(s, v);
		}

		ArrayList<String> list = new ArrayList<String>();
		for (Entry<String, Integer> entry : m.entrySet()) {
			if (entry.getValue() == maxDup) {
				list.add(entry.getKey());
			}
		}
		Collections.sort(list);
		for (String s: list) {
			System.out.println(s);
		}
	}
}


Measured memory_bytes: 77380
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter

val br = BufferedReader(InputStreamReader(System.`in`))
val pw = PrintWriter(System.out)
fun main(args : Array<String>) {
    func()
    pw.flush()
}

fun func() {
    // 回答をここに書く
    val S = next()
    val s = when {
        S.substring((5..6)).toInt() > 4
                || (S.substring((5..6)).toInt() == 4 && S.substring((8..9)).toInt() > 30) -> {
            "TBD"
        }
        else -> "Heisei"
    }
    println(s)
}

// 入力取得
fun next() = br.readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun listOfString() = next().split(" ")
fun listOfInt() =listOfString().map { it.toInt() }
fun listOfLong() =listOfString().map { it.toLong() }

// 約数のList
fun divisor(value : Long) : List<Long> {
    val max = Math.sqrt(value.toDouble()).toLong()
    return (1..max)
        .filter { value % it == 0L }
        .map { listOf(it, value / it) }
        .flatten()
        .sorted()
}

// 範囲内の素数を取得
// fromだけ指定すると戻り値の個数で素数判定ができる
fun prime(from : Long, to : Long = from) : List<Long> {
    return (from..to).filter { i ->
        val max = Math.sqrt(i.toDouble()).toLong()
        (2..max).all { j ->  i % j != 0L }
    }
}

// 素因数分解
fun decom(value : Long) : List<Long>{
    if (value == 1L) return listOf(1)
    val max = Math.sqrt(value.toDouble()).toLong()
    return prime(2, max).filter { value % it == 0L }
}

// 最大公約数
fun gcd(a : Long, b : Long) : Long {
    return if (a % b == 0L) b else gcd(b, a % b)
}

// 文字列を入れ替え
fun swap(base : String, a : String, b : String) : String {
    return base.map {
        when (it) {
            a.toCharArray()[0] -> b
            b.toCharArray()[0] -> a
            else -> it.toString()
        }
    }.joinToString()
}

fun println(value : Any) {
    pw.println(value)
}

Measured memory_bytes: 29608
console.log(require('fs').readFileSync('/dev/stdin','utf8').trim().split(/[ |\n]/).slice(1).map((k,i,a)=>`node ${++i}: key = ${k}, `+((i-1)?`parent key = ${a[(i>>1)-1]}, `:'')+(2*i<=a.length?`left key = ${a[2*i-1]}, `:'')+(2*i<a.length?`right key = ${a[2*i]}, `:'')).join('\n'));


Measured memory_bytes: 16532
s=input()
k=int(input())
if len(set(s))==1:
    print(len(s)*k//2)
    exit(0)
ans=0
tmp=0
before=s[0]
t=0
flag=0
tmp2=0
hoge=0
for i in range(len(s)-1):
    if before==s[i+1]:
        t+=1
    else:
        if flag==0:
            hoge+=t
            flag=1
            tmp+=-(-t//2)
        elif i==len(s)-2:
            hoge+=t
            tmp+=-(-t//2)
        else:
            tmp+=-(-t//2)
            tmp2+=-(-t//2)
        t=0
        before=s[i+1]
tmp+=-(-t//2)
hoge+=t
tmp2+=-(-(hoge+1)//2)
if s[0]==s[-1]:
    print(tmp2*(k-1)+tmp)
else:
    print(tmp*k)

Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long int ll;
const int MAXN=1005;
int n,cnt=0,k;
int arr[MAXN];
ll num[MAXN*MAXN],ans=0;
vector<ll> vec[100];
bool flag[100];
void get_ans(int key){
	if(key==-1) return;
	int sz=vec[key].size();
	if(sz<k){
		get_ans(key-1);
		return;
	}
	flag[key]=true;
	for(int i=0;i<key;++i) vec[i].clear();
	for(int i=0;i<sz;++i){
		for(int j=0;j<key;++j)
			if((1ll<<j)&vec[key][i]) vec[j].push_back(vec[key][i]);
	}
	get_ans(key-1);
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i) scanf("%d",&arr[i]);
	for(int i=1;i<=n;++i){
		ll sum=0;
		for(int j=i;j<=n;++j){
			sum+=arr[j];
			num[++cnt]=sum;
		}
	}
	for(int i=1;i<=cnt;++i){
		for(int j=0;(1ll<<j)<=num[i];++j)
			if((1ll<<j)&num[i]) vec[j].push_back(num[i]);
	}
	get_ans(100);
	for(int i=0;i<100;++i)
		if(flag[i]) ans+=(1ll<<i);
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 80272
#!/usr/bin/env python3
from collections import defaultdict

n, *a = map(int, open(0).read().split())
ans = [0, 0]
d = defaultdict(int)
for i in a:
    d[i] += 1
    if d[i] > 1 and i > ans[0]:
        ans = sorted(ans + [i])[-2:]
        d[i] -= 2
print(ans[0] * ans[1])


Measured memory_bytes: 22428
#include <iostream>
using namespace std;
#include <iomanip>
#include <string>
#include <algorithm>

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

    int ans=0;
    if(n>1&&n!=0){
     ans+=n*(n-1)/2;
    }

    if(m>1&&m!=0){
     ans+=m*(m-1)/2;
    }

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

Measured memory_bytes: 256
n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split()))for _ in range(q)]
b=[0,0]
for i in range(1,n):
  b.append(b[-1])
  if s[i-1:i+1]=="AC":b[-1]+=1
for l,r in lr:print(b[r]-b[l])

Measured memory_bytes: 30696
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product

sys.setrecursionlimit(10000)

MOD = 998244353


def mul_mod(a, b):
    return (a % MOD) * (b % MOD) % MOD


def add_mod(a, b):
    return (a + b) % MOD


def sub_mod(a, b):
    return (a - b) % MOD


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()


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


def prepare(n):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


@mt
def slv(N, A, B, K):
    ans = 0

    FN, invs = prepare(N)
    for i in range(K // A + 1):
        if (K - i * A) % B == 0 and i <= N and (K - i * A) // B <= N:
            j = (K - i * A) // B
            error_print(i, j)
            ans = add_mod(ans,
                          mul_mod(FN * invs[i] * invs[N - i] % MOD,
                                  FN * invs[j] * invs[N - j] % MOD))

    return ans


def main():
    N, A, B, K = read_int_n()
    print(slv(N, A, B, K))


if __name__ == '__main__':
    main()


Measured memory_bytes: 18888
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;

long long modpow(long long a, long long n, long long m)
{
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long m)
{
    return modpow(a, m-2, m);
}

int main()
{
    long long x, y;
    cin >> x >> y;

    long long ans = 0;
    int n = (2 * y - x) / 3, m = (2 * x - y) / 3;
    if ((x + y) % 3 != 0 || n < 0 || m < 0) ans = 0;
    else {
        vector<long long> P(n + m + 1,1);
        for (int i = 1; i < n + m + 1; ++i) P[i] = P[i-1] * i % mod;
        ans = P[n + m] * modinv(P[n] * P[m] % mod, mod) % mod;
    }

    cout << ans << endl;
}

Measured memory_bytes: 5504
# coding=utf-8

N = int(input())
tree = [[]for x in range(N)]
depth = [0 for x in range(N)]
for _ in range(N-1):
    line = input().split(" ")
    a = int(line[0])-1
    b = int(line[1])-1
    c = int(line[2])
    tree[a].append((b, c))
    tree[b].append((a, c))

line = input().split(" ")
Q = int(line[0])
K = int(line[1])-1

# def dfs(v, p, d):
#     depth[v] = d
#     for e in tree[v]:
#         if e[0]==p:
#             continue
#         dfs(e[0], v, d+e[1])
# dfs(K, -1, 0)

s = [(K, -1, 0)]
while len(s)>0:
    (v, p, d) = s.pop()
    depth[v] = d
    for e in tree[v]:
        if e[0]==p:
            continue
        s.append((e[0], v, d+e[1]))


for _ in range(Q):
    line = input(" ").split(" ")
    x = int(line[0])-1
    y = int(line[1])-1
    print(str(depth[x]+depth[y]))


Measured memory_bytes: 47040
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <fstream>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
#include <cassert>
#pragma warning (disable: 4996)
using namespace std;

using ll = long long;
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

ll ll_gcd(ll a, ll b) {
    if (a < b) return ll_gcd(b, a);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

struct UnionFind {
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    if (n < 0)return 0;
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

ll merge_cnt(vector<ll>& a) {
    int n = a.size();
    if (n <= 1) { return 0; }

    ll cnt = 0;
    vector<ll> b(a.begin(), a.begin() + n / 2);
    vector<ll> c(a.begin() + n / 2, a.end());

    cnt += merge_cnt(b);
    cnt += merge_cnt(c);

    int ai = 0, bi = 0, ci = 0;
    while (ai < n) {
        if (bi < b.size() && (ci == c.size() || b[bi] <= c[ci])) {
            a[ai++] = b[bi++];
        }
        else {
            cnt += n / 2 - bi;
            a[ai++] = c[ci++];
        }
    }
    return cnt;
}

ll keta(ll n) {
    ll e = 0;
    while (n != 0) {
        e += n % 10;
        n /= 10;
    }
    return e;
}

int main() {
    vector<ll> z = {1,2,3,4,5,6,7,8,9};
    ll n;
    cin >> n;
    ll p = 1;
    ll now = 10;
    while (now<10000000000000000) {
        while (keta(z[z.size()-1])*now<keta(now)*z[z.size() - 1]) {
            z.pop_back();
        }
        z.push_back(now);
        now += p;
        if (now == p * 1000 - 1)p *= 10;
    }
    for (int i = 0; i < n; i++) {
        cout << z[i] << endl;
    }
}

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

int main()
{
	const int MAXN = 15, MAXBITN = 1 << MAXN;
	
	int n, bitn;
	int num[MAXN], dist[MAXN], money[MAXN];
	
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%d%d%d", &num[i], &dist[i], &money[i]);
	bitn = 1 << n;
		
	static double dp[MAXBITN][MAXN] = { 0 };
	static double speed[MAXBITN] = { 0 };
	static int his[MAXBITN][MAXN] = { 0 };
	
	for(int i = 1; i < bitn; ++i) {
	
		int prev = 0;
		while(!(i & (1 << prev))) ++prev;
		speed[i] = speed[i & ~(1 << prev)] + money[prev] * 20;
	}
	
	for(int i = 0; i < bitn; ++i) {
		speed[i] = 200.0 / (speed[i] + 70);
		for(int j = 0; j < n; ++j) {
			his[i][j] = -1;
			dp[i][j] = 1e10;
		}
	}
	
	for(int i = 0; i < n; ++i)
		dp[0][i] = dp[1 << i][i] = 0;
		
	for(int i = 1; i < bitn; ++i) {
		for(int j = 0; j < n; ++j) {
			
			int prev = i & ~(1 << j);
			
			for(int k = 0; k < n; ++k) {
				
				if(prev & (1 << k)) {
					
					double time = abs(dist[j] - dist[k]) / speed[prev];
					double sum = dp[prev][k] + time;
					//printf("[Debug] %f vs %f\n", dp[i][j], sum);
					if(dp[i][j] > sum) {
						his[i][j] = k;
						dp[i][j] = sum;
					}
				}
			}
		}
	}
	
	int idx = 0, ptr = n - 1;
	int mask = (1 << n) - 1;
	int ans[MAXN];
	
	for(int i = 0; i < n; ++i)
		idx = dp[mask][idx] > dp[mask][i] ? i : idx;
		
	ans[ptr--] = idx;
	while(his[mask][idx] != -1) {
		mask = mask & ~(1 << idx);
		idx = his[mask | (1 << idx)][idx];
		ans[ptr--] = idx;
	}
	
	for(int i = 0; i < n; ++i)
		printf("%d%c", num[ans[i]], i < n - 1 ? ' ' : '\n');
	
	return 0;
}

Measured memory_bytes: 6732
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

#define MOD 1000000007
int main(){
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n)cin >> a[i];

    ll ans = 0;
    rep(i, n){
        ll add = 0;
        rep(j, n)if(a[i] > a[j])add++;
        add *= (((k-1)*k)/2)%MOD;
        ans = (ans+add)%MOD;
    }
    ll cnt = 0;
    rep(i, n)for(ll j=i+1;j<n;++j)if(a[i] > a[j])cnt++;
    cnt = (cnt*k)%MOD;
    cout << (cnt+ans)%MOD << endl;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
x = list(map(int, input().split()))

if n >= m:
    print(0)
else:
    x = list(sorted(x))
    ku = []
    for i in range(len(x)-1):
        ku.append(abs(x[i]-x[i+1]))
    #print(ku)
    ku = list(sorted(ku))
    
    print(sum(ku[:m-n]))

Measured memory_bytes: 59176
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
int a,b;
int main(){
	scanf("%d%d",&a,&b);
	printf("%d\n",(a*3+b)/2);
	return 0;
}

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

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

  if(a == b){
    if(a == c){
      std::cout << 1 << std::endl;
    }else{
      std::cout << 2 << std::endl;
    }
  }else{
    if(a == c || b == c){
      std::cout << 2 << std::endl;
    }else{
      std::cout << 3 << std::endl;
    }
  }

}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    map<int,int> cnt;
    for (int i=0;i<N;++i){
        int A; cin >> A; ++cnt[A];
    }
    int ans=0;
    for (auto p:cnt) ans+=p.second&1;
    cout << ans << '\n';
}

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

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

    int coin = 0;
    for (int i = 0; i < 2; i++)
    {
        if (A > B)
        {
            coin += A--;
        }
        else
        {
            coin += B--;
        }
    }

    cout << coin << endl;
    return 0;
}

Measured memory_bytes: 256
def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    WLs = [0] * (K+1)
    for x in range(1, K+1):
        for A in As:
            if x-A < 0:
                break
            if WLs[x-A] == 0:
                WLs[x] = 1
                break

    if WLs[K]:
        print('First')
    else:
        print('Second')


solve()



Measured memory_bytes: 3828
class PriorityQueue

	Vector = Struct.new(:data, :value)
	def initialize a = 1, b = 0
		@heap = 0
		@node = []
		@option = a - b
	end

	private

	def maxHeapfy key
		left = 2 * key
		right = 2 * key + 1

		if left <= @heap && @node[left].value > @node[key].value
			largest = left
		else
			largest = key
		end

		largest = right	if right <= @heap && @node[right].value > @node[largest].value

		unless largest == key
			@node[key], @node[largest] = @node[largest], @node[key]
			maxHeapfy largest
		end
	end

	def max_extract!
		raise "Stack is empty!" if @heap < 1
		maxv = @node[1]
		@node[1] = @node[@heap]
		@heap -= 1
		maxHeapfy 1
		return maxv
	end

	def max_increaseKey i, vector
		return if vector.value < @node[i].value
		@node[i] = vector
		while i > 1 && @node[i / 2].value < @node[i].value
			@node[i], @node[i / 2] = @node[i / 2], @node[i]
			i = i / 2
		end
	end

	def max_insert! data, value
		@heap += 1
		@node[@heap] = Vector.new(nil,-Float::INFINITY)
		vector = Vector.new(data, value)
		max_increaseKey @heap, vector
	end


	def minHeapfy key
		left = 2 * key
		right = 2 * key + 1

		if left <= @heap && @node[left].value < @node[key].value
			minimum = left
		else
			minimum = key
		end

		minimum = right	if right <= @heap && @node[right].value < @node[minimum].value

		unless minimum == key
			@node[key], @node[minimum] = @node[minimum], @node[key]
			minHeapfy minimum
		end
	end

	def min_extract!
		raise "Stack is empty!" if @heap < 1
		minv = @node[1]
		@node[1] = @node[@heap]
		@heap -= 1
		minHeapfy 1
		return minv
	end

	def min_increaseKey i, vector
		return  if vector.value > @node[i].value
		@node[i] = vector
		while i > 1 && @node[i / 2].value > @node[i].value
			@node[i], @node[i / 2] = @node[i / 2], @node[i]
			i = i / 2
		end
	end

	def min_insert! data, value
		@heap += 1
		@node[@heap] = Vector.new(nil,Float::INFINITY)
		vector = Vector.new(data, value)
		min_increaseKey @heap, vector
	end

	public

	def push data, value
		if @option <= 0
			min_insert! data, value
		else
			max_insert! data, value
		end
	end

	def pop
		if @option <= 0
			min_extract!.data
		else
			max_extract!.data
		end
	end

	def empty?
		@heap < 1
	end

end

MAX = 10000
INFTY = Float::INFINITY
WHITE = 0
GRAY = 1
BLACK = 2
Datav = Struct.new(:first, :second)
$n = nil
$adj = Array.new(MAX){[]}

def dijkstra
	pq = PriorityQueue.new
	color = Array.new(MAX){WHITE}
	d = Array.new(MAX){INFTY}
	d[0] = 0
	pq.push Datav.new(0,0), 0
	color[0] = GRAY

	until pq.empty?

		f = pq.pop
		u = f.second
		color[u] = BLACK

		next	if d[u] < f.first * (-1)

		$adj[u].size.times do |j|
			v = $adj[u][j].first
			next if color[v] == BLACK
			if d[v] > d[u] + $adj[u][j].second
				d[v] = d[u] + $adj[u][j].second
				pq.push(Datav.new(d[v]*(-1), v), d[v]*(-1))
				color[v] = GRAY
			end
		end
	end

	$n.times do |i|
		puts "#{i} #{d[i] == INFTY ? -1 : d[i]}"
	end
end


$n = gets.to_i

$n.times do |i|
	s = gets.split.map(&:to_i)
	2.step(s[1]*2, 2) do |j| 
		$adj[s[0]] << Datav.new(s[j], s[j + 1])
	end
end

dijkstra()

Measured memory_bytes: 49588
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
		Scanner kb=new Scanner(System.in);
int size=kb.nextInt();
int a[][]=new int[size][3];
int x,y,z;
for(int i=0;i<size;i++){
	a[i][0]=kb.nextInt();
	a[i][1]=kb.nextInt();
	a[i][2]=kb.nextInt();
}
for(int i=0;i<size;i++){
x=a[i][0];
y=a[i][1];
z=a[i][2];
if(x*x+y*y==z*z||y*y+z*z==x*x||z*z+x*x==y*y){
	System.out.println("YES");
}else{
	System.out.println("NO");
}
}
	}

}

Measured memory_bytes: 32740
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#define INF 1000000000
#define LLINF 2000000000000000
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
// #define int long long

signed main(){
	string S;
	cin >> S;
	int n = S.length();
	int ans = 0;
	LOOP(i,n){
		if(S[i]!=S[n-i-1])ans++;
	}
	cout << ans/2 << endl;
}


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

long long n;
long long ans;

int main()
{
	cin >> n;
	for(int i=sqrt(n)+5;i>=1;i--)
		if(n%i==0)
		{
			ans=i+n/i-2;
			break;
		}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int
main(void) {
  int a, b, x, y, z;
  
  cin >> a;
  cin >> b;
  x = a + b;
  y = 2 * a - 1;
  z = 2 * b - 1;

  cout << max(x, max(y, z)) << endl;
  
  return 0;
}


Measured memory_bytes: 256
# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
# 
    
# 初期入力
    
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))
    
    
l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)


Measured memory_bytes: 179108
N = gets.to_i
A = readlines.map(&:to_i)

max1 = max2 = 0
A.each do |n|
  if max1 < n
    max1 = n
  elsif max2 < n
    max2 = n
  end
end
A.each {|n| puts n == max1 ? max2 : max1 }


Measured memory_bytes: 22140
n = int(input())
s = list(input())
import collections
c = collections.Counter(s)
e = c["E"]
w = 0
ans = float("Inf")
for i in range(n):
    if s[i] == "E":
        ans = min(ans,e+w-1)
    else:
        ans = min(ans,e+w)
    if s[i] == "W":
        w += 1
    else:
        w -= 1
print(ans)

Measured memory_bytes: 11608
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input_str[] = new String[2];
        Deque<String> list = new ArrayDeque<String>();
        StringBuilder ans = new StringBuilder();
        try {
            int N = Integer.parseInt(br.readLine());

            for (int loop = 0; loop < N; loop++) {
                input_str = br.readLine().split("\\s+");

                if (input_str[0].equals("insert")) {
                    list.addFirst(input_str[1]);
                } else if (input_str[0].equals("delete")) {
                    list.remove(input_str[1]);
                } else if (input_str[0].equals("deleteFirst")) {
                    list.removeFirst();
                } else if (input_str[0].equals("deleteLast")) {
                    list.removeLast();
                }
            }
            if (!list.isEmpty()) {
                ans.append(list.getFirst());
                list.removeFirst();
            }
            while (!list.isEmpty()) {
                ans.append(" ").append(list.getFirst());
                list.removeFirst();
            }
            System.out.println(ans.toString());
        } catch (NumberFormatException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}


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

const int N = 2e5 + 5;
struct lpl{
    int a, b; long long len;
    inline bool operator < (const lpl &A)const{
        return (len == A.len) ? ((a == A.a) ? (b > A.b) : (a > A.a)) : (len > A.len);
    }
};
int n, Q;
bool f[N];
vector<lpl> edge;
priority_queue<lpl> q;

inline int nxt(int t){return (t % n + 1);}

namespace MST{
    int fa[N];

    int find(int t){return (t == fa[t]) ? t : (fa[t] = find(fa[t]));}

    inline long long kruscal(){
        int tot = 0, A = 0, B = 0; long long ret = 0;
        //printf("\n");
        sort(edge.begin(), edge.end());
        for(int i = 0; i < edge.size(); ++i){
            //printf("%d %d %lld\n", edge[i].a, edge[i].b, edge[i].len);
        }
        for(int i = edge.size() - 1; i >= 0; --i){
            A = find(edge[i].a); B = find(edge[i].b);
            if(A == B) continue; tot++;
            fa[A] = B; ret += edge[i].len; if(tot == n - 1) return ret;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &Q);
    for(int i = 1; i <= n; ++i) MST::fa[i] = i;
    for(int a, b, c, i = 1; i <= Q; ++i){
        scanf("%d%d%d", &a, &b, &c); a++, b++;
        edge.push_back((lpl){a, b, c});
        q.push((lpl){a, nxt(a), c + 1});
        q.push((lpl){b, nxt(b), c + 2});
    }
    lpl now; int tot = 0;
    while(tot != n){
        now = q.top(); q.pop();
        if(!f[now.a]){
            tot++; f[now.a] = 1; edge.push_back((now));
            //printf("now!!!! %d %d %lld\n", now.a, now.b, now.len);
            q.push((lpl){now.b, nxt(now.b), now.len + 2});
        }
    }
    cout << MST::kruscal();
    return 0;
}

Measured memory_bytes: 18648
#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
//:/
#define pb push_back
#define mp make_pair
#define nt _ll128
#define ld double
long double PI =3.14159265;
using ll = long long;

const ll modo=998244353;
const ll ms=1e6+5;
const ll inf=1e17;


//ll ar[ms];
//ll mm[ms]={0};

map<int,int> m2;
map<int,int> m1;

int main()
{
    idfc;


    ll n;
    cin>>n;
    int q;
    cin>>q;

    ll ans=(n-2)*(n-2);

    int x,y;
    int a=n;
    int b=n;
    m1[n]=n;
    m2[n]=n;
    int lim;
    while(q--)
    {
        cin>>x>>y;
        //cout<<x<<" "<<y<<endl;
        if(x==1)
        {
            auto it=m1.lower_bound(y);
            b=it->second;
            ans-=(b-2);
            lim=min(y,(*m2.lower_bound(b)).second);
         //   cout<<b<<endl;
            while(true)
            {
                auto ii=m2.upper_bound(b);
                if(ii!=m2.begin())
                {
                    ii--;
                    if((*ii).second>=lim)m2.erase((*ii).first);
                    else break;
                }
                else break;
            }
            m2[b]=lim;
        }
        else{
            auto it=m2.lower_bound(y);
            b=it->second;
            ans-=(b-2);
            lim=min(y,(*m1.lower_bound(b)).second);

            while(true)
            {
                auto ii=m1.upper_bound(b);
                if(ii!=m1.begin())
                {
                    ii--;
                    if((*ii).second>=lim)m1.erase((*ii).first);
                    else break;
                }
                else break;
            }
            m1[b]=lim;
        }
    }

    cout<<ans;

    return 0;
}

Measured memory_bytes: 8216
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using ll = long long;
using namespace std;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
const double INF3 = 900000000000000;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()



int main() {
	int n, a[200010], c[200010];
	cin >> n;
	map<int, int>b;
	for (int i = 0;i < n;i++)cin >> a[i], b[i] = a[i], c[i] = a[i];
	sort(a, a + n);
	for (int i = 0;i < n;i++) {
		if (c[i] < a[n / 2 - 1])cout << a[n / 2] << endl;
		else if (c[i] == a[n / 2 - 1])cout << a[n / 2] << endl;
		else if (c[i] == a[n / 2])cout << a[n / 2 - 1] << endl;
		else cout << a[n / 2 - 1] << endl;
	}
}

Measured memory_bytes: 13056
#include <iostream>
#include <algorithm>
#include <array>
#include <cstdint>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <utility>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define rep(i,a,b) for(uint32 i = (a); i < (b); ++i)
#define bitget(a,b) (((a) >> (b)) & 1)
#define ALL(x) (x).begin(),(x).end()
#define C(x) std::cout << #x << " : " << x << std::endl
#define scanf scanf_s

using int32 = std::int_fast32_t;
using int64 = std::int_fast64_t;
using uint32 = std::uint_fast32_t;
using uint64 = std::uint_fast64_t;

template<typename T>
class hashmap64 {
	std::vector<std::pair<uint64, T>> map;
	uint64 mask, temp, count;
	uint64 hash64(uint64 key) {
		key = 0xFFFFFFFFFFFFFFFF & (~key ^ (~key << 13));
		key ^= key >> 19;
		return 0xFFFFFFFFFFFFFFFF & (key ^ (key << 17));
	}
public:
	hashmap64() :map(8192, std::make_pair(~static_cast<std::uint_fast64_t>(0), T())) {
		mask = 8191; count = 0;
	}
	hashmap64(size_t s) {
		s |= s << 1;
		s |= s >> 2;
		s |= s >> 4;
		s |= s >> 8;
		s |= s >> 16;
		s |= s >> 32;
		mask = s;
		count = 0;
		map.resize(s + 1, std::make_pair(~static_cast<std::uint_fast64_t>(0), T()));
	}
	T &operator[](uint64 suf) {
		temp = mask&hash64(suf);
		while (map[temp].first != suf) {
			temp = mask&(temp + 1);
		}
		return map[temp].second;
	}
	void insert(uint64 key, const T &value) {
		temp = mask&hash64(key);
		while (~map[temp].first) {
			if (map[temp].first == key) {
				map[temp].second = value;
				return;
			}
			temp = mask&(temp + 1);
		}
		map[temp] = std::make_pair(key, value);
		++count;
		if ((count << 1) > mask) {
			std::pair<uint64, T> mkey;
			uint64 t = mask;
			mask = mask << 1 | 1;
			map.resize(mask + 1, std::make_pair(~static_cast<std::uint_fast64_t>(0), T()));
			while (~map[t].first) {
				--t;
			}
			while (++t <= (mask >> 1)) {
				mkey = map[t];
				map[t].first = ~static_cast<std::uint_fast64_t>(0);
				temp = mask&hash64(mkey.first);
				while (~map[temp].first) {
					temp = mask&(temp + 1);
				}
				map[temp] = mkey;
			}
			for (t = 0;t <= mask >> 1;++t) {
				if (~map[t].first) {
					mkey = map[t];
					map[t].first = ~static_cast<std::uint_fast64_t>(0);
					temp = mask&hash64(mkey.first);
					while (~map[temp].first) {
						temp = mask&(temp + 1);
					}
					map[temp] = mkey;
				}
			}
		}
		return;
	}
	bool find(uint64 key) {
		temp = mask&hash64(key);
		while (~map[temp].first) {
			if (map[temp].first == key) {
				return true;
			}
			temp = mask&(temp + 1);
		}
		return false;
	}
	bool empty(void) {
		return !count;
	}
	size_t size(void) {
		return count;
	}
};

int main(void) {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	hashmap64<uint32> map(100000);
	uint32 n;
	std::cin >> n;
	int64 a, sum = 1e15;
	uint32 ans = 0;
	map.insert(sum, 0);
	rep(i, 0, n) {
		std::cin >> a;
		sum += a;
		if (map.find(sum)) {
			ans = std::max(ans, i + 1 - map[sum]);
		}
		else {
			map.insert(sum, i + 1);
		}
	}
	std::cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 15200
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
using namespace std;
typedef long long ll;

const ll MOD = 1e9+7;
int h[100000];
int main()
{
	int n;
	ll ans=0;
	cin>>n;
	bool f=true;
	for(int i=0;i<n;i++)
	{
		cin>>h[i];
	}
	if(h[0]!=1)
		h[0]--;
	for(int i=1;i<n;i++)
	{
		if(h[i]>h[i-1])
			h[i]--;
		else if(h[i]<h[i-1])
			f=false;
	}
	if(f)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

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


using namespace std;

const int maxn = 305,mod = 1e9+7;

int n,m;

vector<pair<int,int> > has[maxn];

int f[maxn][maxn][3],g[maxn][maxn][3];

void add(int &a,int b){
	a=(a+b)%mod;
}

void Work(){
	for(int i=0;i<3;i++)f[0][0][i]=1;
	for(int i=1;i<n;i++){
		memcpy(g,f,sizeof(g));
		memset(f,0,sizeof(f));
		for(int j=0;j<i;j++)
			for(int k=0;k<i;k++)
				for(int l=0;l<3;l++)if(g[j][k][l]){
					//cout<<i<<' '<<j<<' '<<k<<' '<<l<<' '<<g[j][k][l]<<endl;
					for(int x=0;x<3;x++){
						int t0,t1,t2;
						if(l==0){
							t0=i;t1=j;t2=k;
						}
						else if(l==1){
							t0=j;t1=i;t2=k;
						}
						else{
							t0=j;t1=k;t2=i;
						}
						if(x==0)t0=i+1;
						else if(x==1)t1=i+1;
						else t2=i+1;
						bool ok=1;
						for(auto x:has[i+1]){
							int cnt=(t0>=x.first)+(t1>=x.first)+(t2>=x.first);
							if(cnt!=x.second)ok=0;
						}
						if(ok){
							if(x==0)add(f[t1][t2][0],g[j][k][l]);
							else if(x==1)add(f[t0][t2][1],g[j][k][l]);
							else add(f[t0][t1][2],g[j][k][l]);
						}
					}
				}
	}
	int ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<3;k++)if(f[i][j][k])add(ans,f[i][j][k]);
	printf("%d\n",ans);
}

void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int l,r,x;
		scanf("%d%d%d",&l,&r,&x);
		has[r].push_back(make_pair(l,x));
		if(r==1&&l==1){
			if(x!=1){
				puts("0");
				exit(0);
			}
		}
	}
}

int main(){
	Init();
	Work();
	return 0;
}

Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
const int mx=200010;
const ll mod=1e9+7;


int main(){
  int a,b;
  cin >> a >> b;
  if(b%a==0){ cout<<a+b<<endl; } else { cout<<b-a<<endl; }

  return 0;
}


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

#ifdef LOCAL
#include "../lib/dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

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

  int N, M;
  cin >> N >> M;
  vector<vector<int>> to(N + 1);
  map<P, int> dir;
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    to[u].push_back(v);
    to[v].push_back(u);
    dir[P(u, v)] = 1;
    dir[P(v, u)] = 1;
  }
  if (M % 2 == 1) {
    cout << -1 << endl;
    return 0;
  }
  dump(to);
  dump(dir);
  queue<int> q;
  vector<int> used(N + 1);
  function<void(int, int)> dfs = [&](int v, int from) {
    if (used[v])
      return;
    used[v] = 1;
    for (auto& u : to[v]) {
      if (u == from)
        continue;
      dfs(u, v);
    }
    // ボトムアップ
    int sz = to[v].size();
    if (sz == 1) {
      dir[P(v, to[v][0])] = 0;
    } else {
      int outgoing = 0;
      for (int i = 0; i < sz; i++) {
        int u = to[v][i];
        if (dir[P(v, u)] && !dir[P(u, v)])
          outgoing++;
      }
      int cnt;
      if (outgoing % 2 == 0)
        cnt = 0;
      else
        cnt = 1;
      for (int i = 0; i < sz; i++) {
        int u = to[v][i];
        if (dir[P(v, u)] && dir[P(u, v)]) {
          if (cnt) {
            dir[P(u, v)] = 0; // 出力にする
            cnt--;
          } else {
            dir[P(v, u)] = 0; // 入力にする
          }
        }
      }
    }
  };
  dfs(1, 0);
  dump(dir);
  for (auto& m : dir) {
    int u, v;
    tie(u, v) = m.first;
    if (m.second) {
      cout << u << " " << v << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 35584
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class BKThCommonDivisor {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int a = in.nextInt(), b = in.nextInt();
            int k = in.nextInt();

            int answer = -1;
            for (int i = NumberTheory.gcd(a, b); i >= 1; i--) {
                if (a % i == 0 && b % i == 0) {
                    k--;
                }
                if (k == 0) {
                    answer = i;
                    break;
                }
            }

            out.println(answer);
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

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

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

    }

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

    }
}



Measured memory_bytes: 23636
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
	int N; 
	cin >> N; 
	int A[40] = {}; // A[i]の数は1を引くと(2^i)-1とxorされる
	int XOR = 0; 
	for(int i = 0; i < N; i++){
		int a; cin >> a; 
		XOR ^= a; 
		int count = 0; 
		while(a % 2 == 0){
			count ++; a /= 2; 
		}
		A[count + 1] ++; 
	}
	int R = XOR;
	vector<int> ans = {};  
	while(R > 0){
		int a = R; 
		int count = 0; 
		while(a > 0){
			count ++; 
			a = (a >> 1); 
		}
		R ^= (1 << count) - 1; 
		ans.push_back(count); 
	}
	int kotae = ans.size(); 
	bool possible = true; 
	for(int i = 0; i < kotae; i++){
		if(!A[ans[i]]) possible = false; 
	}
	if(possible) cout << kotae << endl; 
	else cout << -1 << endl; 
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    double[] arr = new double[n];
    double ans = 0;
    String[] s = br.readLine().split(" ");
    for(int i=0;i<n;i++)
      arr[i] = Double.parseDouble(s[i]);
    double[][] dp = new double[n+1][n+1];
    
    dp[0][0] = 1.0;
    for(int i=1;i<=n;i++){
      for(int j=0;j<=n;j++){
        if(j==0)
          dp[i][j] = dp[i-1][j]*(1.0-arr[i-1]);
        else
          dp[i][j] = arr[i-1]*dp[i-1][j-1] + (1-arr[i-1])*dp[i-1][j];
      }
    }
    
    for(int i=n/2+1;i<=n;i++)
      ans += dp[n][i];
    System.out.println(ans);
  }
}


Measured memory_bytes: 107208
//shan61916
#include <bits/stdc++.h>
	using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n" 
typedef long long ll;
typedef unsigned long long ull ;
typedef double dll ;

int main(){
 IOS
#ifdef SHAN
	freopen("input.txt" , "r" , stdin);
#endif
	ll n ;
	cin>>n ;
	ll a[n][3] ;
	for(ll i=0;i<n;i++)
	{
		for(ll j=0;j<3;j++)
		{
			cin>>a[i][j] ;
		}
	}
	ll dp[n][3]={0} ;
	dp[0][0]=a[0][0] ;
	dp[0][1]= a[0][1] ;
	dp[0][2]=a[0][2] ;
	for(ll i=1;i<n;i++)
	{
		for(ll j=0;j<3;j++)
		{
			ll mx=-1 ;
			for(ll k=0;k<3;k++)
			{
				 if(k!=j)
				 {
                    mx=max(mx,dp[i-1][k]) ;
				 }
			}
			dp[i][j]= a[i][j]+mx ;
		}
	}
	ll ans=-1 ;
	for(ll i=0;i<3;i++)
	{
		if(dp[n-1][i]>ans)ans= dp[n-1][i] ;
	}
   cout<<ans ;
 
	return 0;
}      // good night.

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

struct edge {
	int to, cost;
	edge(int t,int c):to(t),cost(c) {}
};
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};

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

int h,w,q;
int fld[2000][2000],x[2000][2000],y[2000][2000];

int calc(int a,int b,int c,int d) {
	int sum=fld[c][d],X=x[c][d],Y=y[c][d];

	if(a>0) sum-=fld[a-1][d];
	if(b>0) sum-=fld[c][b-1];
	if(a>0&&b>0) sum+=fld[a-1][b-1];

	X-=x[c][b];
	if(a>0) X+=x[a-1][b]-x[a-1][d];

	Y-=y[a][d];
	if(b>0) Y+=y[a][b-1]-y[c][b-1];

	//cout<<"a "<<a<<" b "<<b<<" c "<<c<<" d "<<d<<" sum "<<sum<<" x "<<X<<" y "<<Y<<endl;

	return sum-(X+Y);
}

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

	cin>>h>>w>>q;
	REP(i,h) {
		string t;
		cin>>t;
		REP(j,w) {
			fld[i][j]=t[j]-'0';
			if(fld[i][j]==1) {
				if(i>0&&fld[i-1][j]==1) y[i][j]=1;
				if(j>0&&fld[i][j-1]==1) x[i][j]=1;
			}
		}
	}
	FOR(i,1,h) {
		fld[i][0]+=fld[i-1][0];
		x[i][0]+=x[i-1][0];
		y[i][0]+=y[i-1][0];
	}
	FOR(j,1,w) {
		fld[0][j]+=fld[0][j-1];
		x[0][j]+=x[0][j-1];
		y[0][j]+=y[0][j-1];
	}
	FOR(i,1,h) {
		FOR(j,1,w) {
			fld[i][j]+=fld[i-1][j]+fld[i][j-1]-fld[i-1][j-1];
			x[i][j]+=x[i-1][j]+x[i][j-1]-x[i-1][j-1];
			y[i][j]+=y[i-1][j]+y[i][j-1]-y[i-1][j-1];
		}
	}
	REP(i,q) {
		int a,b,c,d;cin>>a>>b>>c>>d;
		a--,b--,c--,d--;
		cout<<calc(a,b,c,d)<<endl;
	}

	return 0;
}


Measured memory_bytes: 48768
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>

using namespace std;


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

  long long base = A + B;
  if(base < 0){
    base *= -1;
  }

  if(base % 2 == 0){
    cout << base/2 << endl;
  }
  else{
    cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import java.io.*;
class Main
{
	public static void main(String[] args)throws Exception
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int S=Integer.parseInt(br.readLine());
		int h,m,s;
		
		h=S/3600;
		m=S%3600/60;
		s=S%60;
		System.out.println(h+":"+m+":"+s);
	}
}

Measured memory_bytes: 24352
#include <bitset>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

long gcd(long& a, long b) {
	return b ? gcd(b, a % b) : a;
}

long lcm(long& a, long& b) {
	return a * b / gcd(a, b);
}

int main() {
	int N, ans = 0, i;
	cin >> N;
	vector<long> p(N);
	for (long& j : p) cin >> j;
	for (int j = 1; j < pow(2.0, N); ++j) {
		bitset<20> a = j;
		vector<long> b;
		for (i = 0; i < N; ++i) {
			if (a[i]) b.push_back(p[i]);
		}
		for (i = 1; i < b.size(); ++i) b[i] = lcm(b[i - 1], b[i]);
		for (i = 0; i < N; ++i) {
			if (!a[i]) {
				if (0 == b.back() % p[i]) break;
			}
		}
		if (N == i) ++ans;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3328
/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define BigInt      __int128
#define endl        '\n'
#define mii         map<ll int,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define sim         template < class c
#define ris         return * this
#define dor         > debug & operator <<
#define eni(x)      sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {

using namespace std;

sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug 
{
	~debug() 
	{ 
		cerr<<endl; 
	}
	eni(!=) cerr << boolalpha << i; ris; }
	eni(==) ris << range(begin(i), end(i)); }
	sim, class b dor(pair < b, c > d) 
	{
		ris << "(" << d.first << ", " << d.second << ")";
	}
	sim dor(rge<c> d) 
	{
	  	*this << "[";
	  	for (auto it = d.b; it != d.e; ++it)
	    	*this << ", " + 2 * (it == d.b) << *it;
	  	ris << "]";
	}
};
#define fuck(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define N  100005

ll int expo(ll int base,ll int exponent,ll int mod){
    ll int ans=1;
    while(exponent!=0){
        if(exponent&1) ans=(1LL*ans*base)%mod;
        base=(1LL*base*base)%mod;
        exponent>>=1;
    }
    return ans%mod;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
	// cin>>TESTS;
	while(TESTS--)
	{
		ll int k;
		cin >> k;
		ll int kk = 9 * k;
		ll int p10 = 1;
		for(ll int n = 1; n <= 10000000; n++)
		{
			p10 = (p10 * 10) % kk;
			ll int ans = (p10 + kk + kk - 1) % kk;
			ans = (ans * 7) % kk;
			if(ans == 0)
			{
				cout << n << endl;
				return 0;
			}
		}
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3636
#! /usr/bin/env python
# coding: utf-8


def slove(n, a):
    alice = 0
    bob = 0
    for i in range(n):
        if i%2 == 0:
            alice += a[i]
        else:
            bob += a[i]
    return alice - bob


if __name__ == "__main__":
    n = int(input())
    a = input().split(" ")
    a_lst = []
    for i in range(n):
        a_lst.append(int(a[i]))
    a_lst.sort()
    a_lst.reverse()
    print(slove(n, a_lst))

Measured memory_bytes: 3060
//#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define int long long
#define ll long long
#define str string
#define db double
#define ac() cout<<"Yes"<<endl;
#define wa() cout<<"No"<<endl;
#define ddd cout<<"---debug---"<<endl;
#define ff(a,b) for(signed (a)=1;(a)<=(b);(a)++)
#define fff(a,b) for(signed (a)=0;(a)<(b);(a)++)
#define re readdd()
#define pr(a) printtt(a)
#define pee puts("");
#define eee putchar(' ');
#define pss(a) push_back(a)
#define ps(a) push(a)
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}//
int ppow(int a,int b,int mod){a%=mod;//
int ans=1%mod;while(b){if(b&1)ans=(long long)ans*a%mod;
a=(long long)a*a%mod;b>>=1;}return ans;}
int readdd(){int x=0,f=1;char c=getchar();//
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
return f*x;}
void printtt(int x){if(x<0)putchar('-'),x=-x;
if(x>=10)printtt(x/10);putchar(x%10+'0');}
bool addd(int a,int b){return a>b;};
//
const int maxm=5e5+5;
map<int,int>mark;
char s[maxm];
int n,p;
signed main(){
    cin>>n>>p;
    scanf("%s",s+1);
    int ans=0;
    if(p==2||p==5){
        for(int i=1;i<=n;i++){
            if((s[i]-'0')%p==0){
                ans+=i;
            }
        }
    }else{
        int base=1;
        int sum=0;
        mark[0]=1;
        for(int i=n;i>=1;i--){
            sum=(sum+(s[i]-'0')*base)%p;
            ans+=mark[sum];
            mark[sum]++;
            base=base*10%p;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 1024