akhauriyash/Code-Regression huggingface dataset:
class Bit:
    def __init__(self, n):
        sz = 1
        while n >= sz:
            sz *= 2
        self.size = sz
        self.data = [0]*sz

    def sum(self, i):
        assert i > 0
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        assert i > 0
        while i < self.size:
            self.data[i] += x
            i += i & -i

import bisect
N = int(raw_input())
a = [int(x)-1 for x in raw_input().split()]
weight = [1] * N
M = 10**9+7
def factorial(n):
    acc = 1
    for i in xrange(1, 1 + n):
        acc = (acc * i) % M
    return acc
def inv(n):
    return pow(n, M-2, M)
for i in xrange(N-1):
    weight[N-2-i] = (weight[N-1-i] * (i+1)) % M
missing = list(set(xrange(N)) - set(a))
missing.sort()
n_missing = len(missing)
sum_missing = sum(missing)
avg_missing = sum_missing * inv(n_missing)
n_present = N - n_missing
n_rows = factorial(n_missing)
acc = 0
i_missing = 0
i_present = 0
missing_lt_tot = 0
#present_values = []
present_values_bit = Bit(N+5)
inv_n_missing = inv(n_missing)
inv_2 = inv(2)
for i, (w, x) in enumerate(zip(weight, a)):
    if x == -1:
        ai = avg_missing
        bi = (i_missing * inv_2 + i_present - missing_lt_tot * inv_n_missing) % M
        i_missing += 1
    else:
        ai = x
        #bi = sum(1 for present_value in present_values if present_value < x)
        bi = present_values_bit.sum(x + 1)
        #present_values.append(x)
        present_values_bit.add(x + 2, 1)
        '''
        missing_lt = 0
        for j in missing:
            if j < a[i]:
                missing_lt += 1
        '''
        missing_lt = bisect.bisect(missing, a[i])
        missing_lt_tot += missing_lt
        #print '@', missing_lt, n_missing, i_missing, n_rows
        bi += missing_lt * inv_n_missing * i_missing
        bi %= M
        i_present += 1
    #print x, (ai * n_rows) % M, (bi * n_rows) % M, w
    acc = (acc + (((ai - bi) * n_rows) % M) * w) % M
print (acc + n_rows) % M


Measured memory_bytes: 127868
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static char[] s;
	public static void main(String[] args) throws IOException{
		Scanner in = new Scanner(System.in);
		int t = in.nextInt();
		while(t-->0){
			s = in.next().toCharArray();
			cur = 0;
			System.out.println(exp());
		}
	}
	
	public static int cur;
	public static int exp(){
		int val = add();
		while(s[cur] == '+' || s[cur] == '-'){
			if(s[cur++] == '+'){
				val += add();
			}else val -= add();
		}
		return val;
	}
	
	public static int add(){
		int val = mult();
		while(s[cur] == '*' || s[cur] == '/'){
			if(s[cur++] == '*'){
				val *= mult();
			}else val /= mult();
		}
		return val;
	}
	
	public static int mult(){
		if(s[cur] == '('){
			cur++;
			int val = exp();
			cur++;
			return val;
		}else{
			return num();
		}
	}
	
	public static int num(){
		int d = 0;
		int sign = 1;
		if(s[cur] == '-'){
			sign = -1;
			cur++;
		}
		while(cur < s.length && Character.isDigit(s[cur])){
			d *= 10;
			d += s[cur++]-'0';
		}
		return d*sign;
	}
}

Measured memory_bytes: 17172
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
 
#include <bits/stdc++.h>
 
#define int ll
//#define double long double
#define endl '\n'
#define all(C) (C).begin(), (C).end()
#define rall(C) (C).rbegin(), (C).rend()
#define mp make_pair 
#define pb emplace_back
#define dbg(x) cerr << #x << " : " << x << endl
#define PI 3.1415926535
 
using namespace std;
        
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair <int, int>;
using pld = pair <ld, ld>;

/*
const ll MAX_MEM = 3e6;
char MEM[MAX_MEM];
ll MEM_POS = 0;
void* operator new(size_t x)
{
    auto ret = MEM + MEM_POS;
    MEM_POS += x;
    assert(MEM_POS < MAX_MEM);
    return ret;
}
void operator delete(void*)
{}
*/
        
template <class T>
istream& operator>> (istream &in, vector <T> &a)
{
    for (auto &i : a)
        in >> i;
    return in;
}
        
template <class T> 
ostream& operator<< (ostream &out, vector <T> a)
{
    for (auto &i : a)
        out << i << ' ';
    return out;
}
        
template <class T, class U>
istream& operator>> (istream &in, pair <T, U> &p)
{
    in >> p.first >> p.second;
    return in;
}
        
template <class T, class U>
ostream& operator<< (ostream &out, pair <T, U> p)
{
    out << p.first << " " << p.second << " ";
    return out;
}
        
inline void Start()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    //freopen("lol.in", "r", stdin);
    //freopen("lol.out", "w", stdout);
}

signed main()
{
    Start();
    int n, x;
    cin >> n >> x;
    if (x == 1 || x == 2 * n - 1)
        return cout << "No", 0;
    cout << "Yes\n";
    if (n == 2)
        return cout << "1\n2\n3", 0;
    if (x != 2 * n - 2)
    {
    vector <int> used(2 * n), a(2 * n - 1);
    a[n - 1] = x - 1, a[n - 2] = x, a[n - 3] = x + 1, a[n] = x + 2;
    used[x - 1] = used[x] = used[x + 1] = used[x + 2] = 1;
    for (int i = 0, j = 1; i < 2 * n - 1; ++i)
    {
        if (a[i])
            continue;
        while (used[j])
            ++j;
        a[i] = j, used[j] = 1;
    }
    for (auto &i : a)
        cout << i << endl;
    }
    else
    {
    vector <int> used(2 * n), a(2 * n - 1);
    a[n - 1] = x + 1, a[n - 2] = x, a[n - 3] = x - 1, a[n] = x - 2;
    used[x + 1] = used[x] = used[x - 1] = used[x - 2] = 1;
    for (int i = 0, j = 1; i < 2 * n - 1; ++i)
    {
        if (a[i])
            continue;
        while (used[j])
            ++j;
        a[i] = j, used[j] = 1;
    }
    for (auto &i : a)
        cout << i << endl;
    }
    return 0;
}




Measured memory_bytes: 4736
M, D = map(int, input().split())

result = 0
for m in range(1, M+1):
    for d in range(1, D+1):
        if m >= 4 and d >= 22:
            d10, d1 = map(int, str(d))
            if d10 >= 2 and d1 >= 2 and d1 * d10 == m:
                result += 1
print(result)


Measured memory_bytes: 40304
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int dp[200020]= {};
int s[200020] = {};
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		s[i] = a;
	}
	for (int i = n; i >= 1; i--) {
		int thissum = 0;

		for (int j = i+i; j <= n; j = j + i) {
			thissum = thissum + dp[j];
		}

		if (thissum % 2 != s[i]) {
			dp[i] = 1;
		}
	}

	int sum = 0;
	for (int i = 1; i <= n; i++) {
		sum = sum + dp[i];
	}
	cout << sum <<endl;
	for (int i = 1; i <= n; i++) {
		if (dp[i] == 1) {
			cout << i << " ";
		}
	}
}

Measured memory_bytes: 2432
// AOJ 	2509: Sim Forest 2013
// 2018.1.3 bal4u@uu

#include <stdio.h>
#include <math.h>

char *s_time[3] = {"Day", "Night", "All"};
int id_time[3] = {0,1,2}, len_time[3] = {4,6,4};
int tr_time['Z'];

int tbl[3][2][20160];		// day/night/all, weekday/all, 20160 = 2*7*24*60

char buf[50], *bp;

int in()
{
	int n = 0;
	while (*bp >= '0') n = (n<<3) + (n<<1) + (*bp++ & 0xf);
	bp++;
	return n;
}

int main()
{
	int s, n, t, weekday, time, p, m, i, j, k, cnt, ans;

	for (i = 0; i < 3; i++) bp = s_time[i], tr_time[*bp] = id_time[i];

	// imos method
	tbl[0][0][ 6*60+1] = 1, tbl[0][0][18*60+1] = -1;		// day    6:00-18:00
	tbl[1][0][18*60+1] = 1, tbl[1][0][24*60+1] = -1;		// night 18:00-24:00
	tbl[1][0][      1] = 1, tbl[1][0][ 6*60+1] = -1;		// night  0:00- 6:00
	tbl[2][0][      1] = 1, tbl[2][0][24*60+1] = -1;		// all    0:00-24:00

	for (i = 0; i < 3; i++) for (j = 0; j <= 24*60+2; j++) tbl[i][0][j+1] += tbl[i][0][j];

	// for all weekday
	for (i = 0; i < 3; i++) for (j = 0; j < 24*60; j++) for (t = 0, k = 0; k < 7; k++, t += 24*60)
		tbl[i][1][j+t] = tbl[i][0][j];
	

	while (1) {
		fgets(bp=buf, 50, stdin);
		s = in(), n = in(), t = in();
		if (*bp == 'N') break;				// None -> exit
		weekday = (*bp == 'A'),  bp += 4;
		time = tr_time[*bp],     bp += len_time[time];
		p = in(), m = in();

		ans = 0;
		for (i = 0; i < 10085; i++) {		// 10085 = 7*24*60+5
			cnt = 0;
			for (k = i, j = 0; j < m; j++, k += t) {
				if (tbl[time][weekday][k % 10080] && tbl[time][weekday][(k+s) % 10080]) cnt++;
			}
			if (cnt > ans) ans = cnt;
		}
		printf("%.10lf\n", 1-pow(1-1.0/p, ans*n));
	}
	return 0;
}



Measured memory_bytes: 2024
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<string>
#include<time.h>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using str = string;
template<typename T>
using vec = vector<T>;

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

int h, w;
vec<str> sts;
queue<int> blacks;
int wcnt;
int idx(int x, int y) { return y * w + x; }

int main() {
    cin >> h >> w;
    sts.resize(h);
    wcnt = 0;
    rep(i, h) cin >> sts[i];
    vector<bool> fs(h * w);
    rep(y, h)rep(x, w)if (sts[y][x] == '.') {
        ++wcnt;
        fs[idx(x, y)] = true;
    }
    else {
        blacks.push(idx(x, y));
        fs[idx(x, y)] = false;
    }
    int ret = 0;
    int revcnt = 0;
    while (revcnt < wcnt) {
        ++ret;
        int loops = blacks.size();
        rep(i, loops) {
            int x = blacks.front() % w;
            int y = blacks.front() / w;
            blacks.pop();
            if (x > 0 && fs[(idx(x - 1, y))]) {
                fs[(idx(x - 1, y))] = false;
                revcnt++;
                blacks.push(idx(x - 1, y));
            }
            if (x < w - 1 && fs[(idx(x + 1, y))]) {
                fs[(idx(x + 1, y))] = false;
                revcnt++;
                blacks.push(idx(x + 1, y));
            }
            if (y > 0 && fs[(idx(x, y - 1))]) {
                fs[(idx(x, y - 1))] = false;
                revcnt++;
                blacks.push(idx(x, y - 1));
            }
            if (y < h - 1 && fs[(idx(x, y + 1))]) {
                fs[(idx(x, y + 1))] = false;
                revcnt++;
                blacks.push(idx(x, y + 1));
            }
        }
    }
    cout << ret << endl;
    return 0;
}

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

int main(void){
  int N;
  cin >> N;
  for(int i = 1; i <= 9; i++){
    for(int j = 1; j <= 9; j++){
      if(i*j == N){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int ans = Math.min(b,d) - Math.max(a,c);
        
        if(ans > 0){
            System.out.println(ans);    
        }else{
            System.out.println("0");
        }
    }
}

Measured memory_bytes: 22608
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}
string YN(bool v) { return v ? "Yes":"No"; }
void uniq(VI& es) { sort(ALL(es)); es.erase(unique(ALL(es)), es.end()); }

#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll a,b,c,d,e;
	string s;
	while(cin>>a>>b>>c>>d>>e) {
		auto A = VI{a,b,c,d,e};
		ll ans=0;
		REP(i, 5) if(A[i]==0) ans=i+1;
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3156
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const int H = 5000;
const int K = H/2;
int dp[H+1][H+1];
ll dp2[H+1];

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

	int n;
	ll m;
	cin >> n >> m;
	int k = (n-1)/2;
	int h = n;

	ll cou = 0;
	dp[0][0] = 1;
	for (int i = 1; i <= k; ++i) {
		for (int s = h; s >= 0; --s) {
			for (int b = 1; (b <= s) && ((k-i)*b <= h-s); ++b) {
				dp[b][s] = (dp[b-1][s] + dp[min(b, s-b)][s-b]);
				if (dp[b][s] > m) dp[b][s] -= m;
			}
		}
	}

	dp2[0] = 1;
	for (int s = 1; s <= h; ++s) {
		dp2[s] = (dp[s][s] + dp2[s-1]) % m;
	}

	// Case n = 6
	// a + b + c > e + f
	// -> c-a + c-b + c > c+e + c+f
	// -> c > a+b+e+f

	ll res = 0;
	for (int x = 1; x <= n; ++x) {
		for (int s = 0; s < x; ++s) {
			int a = n-x;
			int b = x-1 - s;
			res = (res + dp2[s] * dp[min(a, b)][b]) % m;
			if (n % 2 == 0 && b >= k && x < n) {
				res = (res + dp2[s] * dp[min(a-1, b-k)][b-k]) % m;
			}
		}
	}
	cout << res << '\n';

	// \sum_{i = 1}^{k+1} v_{i} > \sum_{i = n-k}^{n} v_{i}

	// 1. 1 <= v1 <= ... <= vn <= n
	// 2. v1 + ... + vk > vk+1 + ... + vn

	// When n = 2k+1, sum of first k+1 must be greater than sum of last k
	// When n = 2k, sum of first k must be greater than sum of last k-1

	// To get sum s from n first, with each at most b, the number of ways
	// equals the number of ways to select b unordered integers from [0 ... n] with duplicates allowed that sum to s
	// DP[a][b][s]: number of ways to get sum at most s with a elements each between 0 and b
	// DP[a][b][s] = \sum_{k = 0}^{b} DP[a-1][k][s-k]

	// case n = 2k + 1
	// \sum vk+i - vk-i < vk

	// \sum di <= 

	// Resulting sum is at least k * x
	// Sum at most x, elements nondecreasing
	// Cannot even have v0 < 0, so we don't need the bound requirement
	// Unfortunately can have vn > n :(((
	// n^2 log n too large memory usage

	// Bound requirement is also clear!
	// size of dp at i: \sum_{b = 0}^{H/(i+1)} H-(i+1)*b ~ (i+1) * (H/(i+1))^2 = H^2 / (i+1) -> H^2 log H states
	// Memory usage is H^2, so that's an issue
	// Go bottom-up? Maintain current B, 

	// DP[a][b][s]: ways to have a elements sum to exactly s s.t. every element is at most b

	// case n = 2k+1:
	// 	ans = \sum_{x = 1}^{n} \sum_{s = 0}^{x-1} DP[k][x][s] DP[k][n-x][x-(1+s)]
	// case n = 2k+2:
	// 	ans = \sum_{x = 1}^{n} \sum_{s = 0}^{x-1} DP[k][s][s] (DP[k][n-x][x-(1+s)] + DP[k][n-x-1][x-(1+s+k)])


}


Measured memory_bytes: 96768
S, T = [str(input()) for _ in range(2)]
ans_list = []
for i in range(len(S)):
    if not i+len(T) <= len(S):
        break
    else:
        tmp = S
        # S[i:i+len(T)]のチェック
        flag = True
        for j in range(i, i+len(T)):
            if S[j] == '?':
                # tmp[j] = T[j-i]
                tmp = tmp[:j] + T[j-i] + tmp[j+1:]
            elif S[j] == T[j-i]:
                continue
            else:
                flag = False
                break
        if flag:
            ans_list.append(tmp.replace('?', 'a'))
if ans_list:
    print(sorted(ans_list)[0])
else:
    print('UNRESTORABLE')

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

int main(void) {
    int n,ans=0;
    cin>>n;
    vector<int> v(n);
    vector<int> c(n);
    rep(i,n){cin>>v[i];}
    rep(i,n){cin>>c[i];}
    rep(i,n){
        if(v[i]>c[i]){
            ans+=(v[i]-c[i]);
        }
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll=long long;
using P=pair<int,int>;
int main(){
    string s,t;
    cin>>s>>t;
    int ans=1e9;
    rep(si,s.size()){
        if(si >s.size()-t.size()) continue;
        int cnt=0;
        rep(i,t.size()){
            if(s.at(si+i) != t.at(i)) cnt++;
        }
        ans=min(ans,cnt);
    }
        cout<<ans<<endl;
}


Measured memory_bytes: 3588
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		double x1, y1, x2, y2, x3, y3, xp, yp, xg, yg;
		StringTokenizer st;

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			st = new StringTokenizer(line);
			x1 = Double.parseDouble(st.nextToken());
			y1 = Double.parseDouble(st.nextToken());
			x2 = Double.parseDouble(st.nextToken());
			y2 = Double.parseDouble(st.nextToken());
			x3 = Double.parseDouble(st.nextToken());
			y3 = Double.parseDouble(st.nextToken());
			xp = Double.parseDouble(st.nextToken());
			yp = Double.parseDouble(st.nextToken());
			xg = (x1 + x2 + x3) / 3;
			yg = (y1 + y2 + y3) / 3;
			boolean b = true;
			b &= (linear(x1, y1, x2, y2, xp, yp)
					* linear(x1, y1, x2, y2, xg, yg) > 0);
			b &= (linear(x2, y2, x3, y3, xp, yp)
					* linear(x2, y2, x3, y3, xg, yg) > 0);
			b &= (linear(x3, y3, x1, y1, xp, yp)
					* linear(x3, y3, x1, y1, xg, yg) > 0);
			if (b)
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}

	static double linear(double x1, double y1, double x2, double y2, double xp,
			double yp) {
		return (y2 - y1) * xp - (x2 - x1) * yp + y2 * (x2 - x1) - x2
				* (y2 - y1);
	}
}

Measured memory_bytes: 16952
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

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

	map<Int, Int> mp;
	mp[0] = 1;
	for (int i = 0; i < N; ++i) {
		if (i > 0) { A[i] += A[i - 1]; }
		++mp[A[i]];
	}

	Int ans = 0;
	for (auto it = mp.begin(); it != mp.end(); ++it) {
		Int x = it->second;
		ans += x * (x - 1) / 2;
	}
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 17012
p = input()
s = input()

n = len(p)
for x in range(n):
    flag = True
    for y in range(len(s)):
        if p[(x + y) % n] != s[y]:
            flag = False
            break
    if(flag):
        break

if(flag):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 5560
var
    a,b,c:longint;
    s:string;
    ans:boolean;
begin
    readln(s);
    c:=pos('+',s);
    if c=0 then 
             begin 
               c:=pos('-',s); 
               ans:=true;
             end;
    val(copy(s,1,c-2),a);
    val(copy(s,c+2,length(s)-c-1),b);
    if ans then writeln(a-b) 
             else writeln(a+b);
end.

Measured memory_bytes: 128
n, m = map(int, input().split())
uv = [list(map(int, input().split())) for _ in range(m)]
s, t = map(int, input().split())

alist = [[] for _ in range(3*n)]
for u, v in uv:
    u, v = u-1, v-1
    alist[u].append(n+v)
    alist[n+u].append(2*n+v)
    alist[2*n+u].append(v)


# BFS
queue = [s-1]
visited = [-3]*(3*n)
visited[s-1] = 0
while len(queue) > 0:
    q = queue.pop(0)
    for v in alist[q]:
        if visited[v] < 0:
            queue.append(v)
            visited[v] = visited[q] + 1
print(visited[t-1]//3)




Measured memory_bytes: 79668
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		Main ins = new Main(in);
		ins.calc();
		ins.showResult();
	}

	Main(BufferedReader in) throws IOException {
		String[] tokens = in.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		int K = Integer.parseInt(tokens[1]);

		int[] d = new int[K];
		List<Integer>[] A = new List[K];
		for (int i = 0; i < K; ++i) {
			d[i] = Integer.parseInt(in.readLine());
			tokens = in.readLine().split(" ");
			List<Integer> list = new ArrayList<>();
			for (int j = 0; j < d[i]; ++j) {
				list.add(Integer.parseInt(tokens[j]));
			}
			A[i] = list;
		}

		Set<Integer> set = new HashSet<>();
		for (int i = 1; i <= N; ++i) {
			set.add(i);
		}
		for (List<Integer> list : A) {
			for (int j = 0; j < list.size(); ++j) {
				set.remove(list.get(j));
			}
		}
		System.out.println(set.size());
	}

	void calc() {
	}

	void showResult() {
	}

}


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

using namespace std;
#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
//rep…「0からn-1まで」の繰り返し
#define rep2(i,s,n) for(long long i=s; i<=(long long)(n);i++)
//rep2…「sからnまで」の繰り返し
#define repr(i,s,n) for(long long i=s;i>=(long long)(n);i--)
//repr…「ｓからnまで」の降順の繰り返し

typedef long long ll;

const int inf = 1e9+7;
const int mod = 1e9+7;

int main(){
    string s,t;
    cin>>s>>t;

    int l=s.size()-t.size()+1;

    int ans=inf;

    rep(i,l){
        string S=s.substr(i,t.size());
        int cnt=0;

        rep(i,t.size()){
            if(S[i]!=t[i])cnt++;
        }

        ans=min(ans,cnt);
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 3628
#include<iostream>
#include<string>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define ll long long
int main(){
	ll N;
	cin >> N;
	ll i=1;
	ll ans=0;
	while(i*i <= N){
		if(N%i==0)ans=i + N/i-2;
		i++;
	}
	cout << ans;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cmath>
#include <algorithm>
#include <deque>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pi> vpi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

double EPS = 1e-9;
int INFi = 1000000005;
long long INFll = 1000000000000000005ll;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};
ll MOD = 1000000007;

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((ll)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
// #define mp make_pair
// #define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)
#define show(x) cout << #x << " = " << x << endl;



int main(){

  int a, b;
  string str;
  cin >> a >> b >> str;
  if(str.size() != (a + b + 1)){
    cout << "No" << endl;
    return 0;
  }else{
    REP(i,(a+b+1)){
      if(i == a){
        if(str[i] != '-'){
          cout << "No" << endl;
          return 0;
        }
      }else{
          if(str[i] < '0' || str[i] > '9'){
            cout << "No" << endl;
            return 0;
          }
        
      }
    }
  }
  cout << "Yes" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<bitset>
#define REP(i,x,y) for(ll i=x;i<=y;i++)
typedef long long ll;
using namespace std;
ll const MAX = 5005;
ll a[MAX];
bitset<MAX> b[MAX];
bitset<MAX> c[MAX];
ll d[MAX];

int main() {
	ll n, k;
	cin >> n >> k;
	ll ans = 0;
	REP(i, 1, n) {
		cin >> a[i];
		if (a[i] >= k) {
			i--;
			n--;
		}
	}
	b[0][0] = 1;
	c[n + 1][0] = 1;
	REP(i, 1, n-1) {
		b[i] = b[i - 1] | (b[i - 1] << a[i]);
		c[n + 1 - i] = c[n - i + 2] | (c[n - i + 2] << a[n + 1 - i]);
	}
	REP(i, 1, n) {
		bool flag = 1;
		d[0] = 1;
		REP(j, 1, k) {
			d[j] = d[j - 1] + (c[i+1][j] == 1);
		}
		REP(j, 0, k) {
			if (b[i-1][j] == 1) {
				ll x, y;
				x = k - a[i] - j;
				y = k - 1 - j;
				//cにx以上y以下の元があるかどうかを調べたい
				if (y < 0) {
					flag = 1;
					break;
				}
				if (x <= 0) {
					flag = 0;
					break;
				}
				else {
					if (d[y] - d[x - 1] != 0) {
						flag = 0;
						break;
					}
				}
			}
		}
		ans += flag;
	}
	cout << ans << endl;
}

Measured memory_bytes: 6528
//
//AtCoder Beginner Contest 167
//A - Registration
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()

using ll = long long;

const double PI = 3.14159265358979323846;
const int MOD = 1000000007;

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

int main()
{
    string s,t;

    cin >> s >> t;

    string t1 = t.substr(0, s.size());

    if ((t1==s) && (s.size()+1==t.size())){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}


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

dp = [[[0 for k in range(2501)] for j in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
    x = X[i-1]
    dp[i][1][x] += 1
    for j in range(1,i+1):
        for k in range(1,2501):
            if k-x > 0:
                dp[i][j][k] += dp[i-1][j-1][k-x] + dp[i-1][j][k]
            else:
                dp[i][j][k] += dp[i-1][j][k]

ans = 0

for j in range(1,N+1):
    ans += dp[N][j][j*A]
print(ans)


Measured memory_bytes: 95964
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

a, b, c = na()

print(a * b // 2)

Measured memory_bytes: 3060
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

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

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

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    int am2, bm2;
    int ans;
    if (n % 2) {
        am2 = a[n / 2];
        bm2 = b[n / 2];

        ans = bm2 - am2 + 1;
    } else {
        am2 = a[n / 2 - 1] + a[n / 2];
        bm2 = b[n / 2 - 1] + b[n / 2];

        ans = bm2 - am2 + 1;
    }

    cout << ans << endl;
}


Measured memory_bytes: 6348
#include <iostream>
#include <vector>
#include <cmath>


using namespace std;  

int main(void){
  int N;
  cin >> N;
  
  int ans = 0;
  for(int i = 0; i < 10; i++){
    if((int)pow(2,i+1) > N){
      ans = (int)pow(2,i);
      break;
    }
  }
  cout << ans;
}





Measured memory_bytes: 256
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

t=int(input())
result=[]
for i in range(t):
    a,b,c,d=list(map(int,input().split()))
    if b>d:
        result.append('No')
    elif a<b:
        result.append('No')
    elif a%b>c:
        result.append('No')
    elif b-c-1<gcd(b,d):
        result.append('Yes')
    else:
        result.append('No')

for r in result:
    print(r)



Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#include<bitset>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<numeric>
#include<set>
#include<math.h>
using namespace std;

const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};

#define rep(i,x) for(int i=0;i<x;i++)
#define re(i,x,y) for(int i=x;i<y;i++)

long long INF=1e9;
const int mod=10007;
#define ll long long

int main(){
    ll n,k;
    cin>>n>>k;
    vector<ll>a(n),b(n);
    vector<pair<ll,ll> > P(n);
    rep(i,n){
        cin>>a[i]>>b[i];
        P[i]=make_pair(a[i],b[i]);
    }
    sort(P.begin(),P.end());
    ll sum=0,ans;
    rep(i,n){
        sum+=P[i].second;
        if(sum>=k){
            ans=P[i].first;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

using ll = long long;

// DPの添字は宝箱が開いているかどうかのbit列
ll dp[1<<12];
ll a[1000];
ll s[1000];
const ll INF = 1LL << 50;
int main()
{
    ll N, M;
    cin >> N >> M;
    for(ll i = 0; i < M; ++i){
        cin >> a[i];
        ll b;
        cin >> b;
        for(ll j = 0; j < b; ++j){
            ll c;
            cin >> c;
            s[i] |= (1 << (c-1));
        }
    }
    
    // 宝箱が開いている状態の最小コストをDPで求めて、各鍵で更新していく
    for(auto& v : dp){ v = INF; }
    dp[0] = 0;
    for(ll m = 0; m < M; ++m){
        for(ll i = 0; i < (1<<N); ++i){
            dp[i | s[m]] = min(dp[i | s[m]], dp[i] + a[m]); 
        }
    }
    auto ans = dp[(1<<N)-1];
    if(ans == INF){ cout << -1 << endl; }
    else{ cout << ans << endl; }
}


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

typedef vector <int> VI;
typedef vector <VI> VVI;

int main( void )
{
	int n, datacases = 1;
	while ( cin >> n && n )
	{
		VVI image( n, VI( n, 0 ) );

		int x = 0, y = 0, time = 1;
		bool phase = false;

		while ( x != n-1 || y != n-1 )
		{
			image[x][y] = time;
			if ( phase )
			{
				if ( x < n-1 && y == 0 )
				{
					x++;
					phase = !phase;
				}
				else if ( x == n - 1 )
				{
					y++;
					phase = !phase;
				}
				else
				{
					x++;
					y--;
				}
			}
			else
			{
				if ( y < n-1 && x == 0 )
				{
					y++;
					phase = !phase;
				}
				else if ( y == n - 1 )
				{
					x++;
					phase = !phase;
				}
				else
				{
					x--;
					y++;
				}
			}
			time++;
		}
		image[n-1][n-1] = time;

		cout << "Case " << datacases << ":" << endl;
		for ( int i = 0; i < n; i++ )
		{
			for ( int j = 0; j < n; j++ )
			{
				cout << setw(3) << image[i][j];
			}
			cout << endl;
		}

		datacases ++;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>

using namespace std;
typedef long long ll;

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

string calc(ll a,int n){
    string s;
    ll num=a-1;
    for(int i=n;i!=0;--i){
       // cout<<num/(ll)pow(26,i)<<endl;
        int r=num/(ll)pow(26,i);
        s.push_back('a'+num/pow(26,i));
        num=num-r*pow(26,i);
    }
    s.push_back('a'+num%26);

    return s;
}

int main(){
    ll N;
    scanf("%lld",&N);
    string s;
    int i=1;
    ll min=1;
    ll max=26;
    ll sagaku=26;

    for(i=0;i!=14;++i){
     //cout<<"min:"<<min<<" max:"<<max<<endl;
        if(min<=N&N<=max){
            break;
        }

        min=max+1;
        sagaku*=26;
        max+=sagaku;
        
    }

   //cout<<"i:"<<i<<endl;

    ll c=N-(min-1);

  // cout<<c<<endl;

    cout<<calc(c,i)<<endl;


    

}


Measured memory_bytes: 4180
#include <iostream>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#define ll long long 

using namespace std;

int main(){
	string s;
	string ans;
	ans = "CODEFESTIVAL2016";
	int count = 0;
	cin >> s;
	for (int i = 0; i < 16; ++i)
	{
		if (s[i] != ans[i])
		{
			count++;
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <tuple>
#include <vector>

using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define INF (1e9)

int main() {
    int P, Q, R;
    cin >> P >> Q >> R;

    int ans = min({P + Q, Q + R, R + P});

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


Measured memory_bytes: 256
#include <stdio.h>

int judge(int,int);

int main(void){
  int A[4],B[4],i,sumA,sumB;

  sumA = sumB = 0;

  for( i = 0 ; i < 4 ; i++ ){
    scanf("%d" ,&A[i]);
    sumA += A[i];
  }

  for( i = 0 ; i < 4 ; i++ ){
    scanf("%d" ,&B[i]);
    sumB += B[i];
  }

  printf("%d\n" ,judge(sumA,sumB));

  return 0;
}

int judge(int sumA,int sumB){

  if( sumA >= sumB ) return sumA;
  else return sumB;

}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for (int i = a; i < (int)b; ++i)
#define rrep(i, n) for (int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> cnt(n + 1);
	for (int i = 1; i * i <= n; ++i) {
	  for (int j = 1; j * j <= n; ++j) {
		for (int k = 1; k * k <= n; ++k) {
		  int v = i * i + j * j + k * k + i * j + j * k + k * i;
		  if (v > n) continue;
		  cnt[v]++;
		}
	  }
	}
	rep (i, n) cout << cnt[i + 1] << endl;
	
    return 0;
}



Measured memory_bytes: 3636
from collections import deque

def bfs():
    d = [[10**3] * w for i in range(h)]

    # 移動4方向のベクトル
    dh = [1, 0, -1, 0]
    dw = [0, 1, 0, -1]

    global sh
    global sw
    que = deque([])
    que.append((sh, sw))
    d[sh][sw] = 0
    chk = []
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            if 0 <= nh < h and 0 <= nw < w and maze[nh][nw] != "#" and d[nh][nw] == float(10**3):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nh, nw))
                d[nh][nw] = d[p[0]][p[1]] + 1
                
    return d[p[0]][p[1]]

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
maze = tuple(maze)

res = set()
# スタート地点をキューに入れ、その点の距離を0にする
for i in range(h):
  for j in range(w):
      if maze[i][j] == ".":
          sh = i
          sw = j
          res.add(bfs())
          
print(max(res))

Measured memory_bytes: 3316
def three_nums(n, x):
    res = 0
    if (x <= 5):
        return 0
    if ((0.5 * n * (n+1)) < x):
        return 0
     
    for a in range(1, n+1):
        for b in range(a+1, n+1):
            for c in range(b+1, n+1):
                if (a + b + c == x):
                    res += 1
    return res

if __name__ == "__main__":
    while True:
        n, x = map(int, input().split())
        if n == x == 0:
            break
        print(three_nums(n, x))
    



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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll w, h;
	cin >> w >> h;
	priority_queue<int,vi,greater<int>> a, b;
	REP(i, w) {
		int c;
		cin >> c;	
		a.push(c);
	}
	REP(i, h) {
		int c;
		cin >> c;
		b.push(c);
	}

	ll ans = 0, cnt = 0;
	int cntw = 0, cnth = 0;
	while (cnt < (w+1)*(h+1) - 1) {
		if (!a.empty()&&!b.empty()) {

			if (a.top() <= b.top()) {
				ans += a.top()*(h + 1 - cnth);
				cnt += h + 1 - cnth;
				cntw++;
				a.pop();
			}
			else {
				ans += b.top()*(w + 1 - cntw);
				cnt += w + 1 - cntw;
				cnth++;
				b.pop();
			}
		}
		else if (!a.empty()) {
			ans += a.top()*(h + 1 - cnth);
			cnt += h + 1 - cnth;
			cntw++;
			a.pop();
		}
		else {
			ans += b.top()*(w + 1 - cntw);
			cnt += w + 1 - cntw;
			cnth++;
			b.pop();
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1400
#include <stdio.h>

/** Application main entry point. */
int main (
  int argc,
  char *argv[ ]
  )
{
  int ch;

  while ( 1 )
  {
    ch = getchar ( );

    if ( ch == EOF ) break;

    putchar ( ch >= 'a' && ch <= 'z'
      ? ch - 'a' + 'A'
      : ch );

    if ( ch == '\n' ) break;
  }

  return ( 0 );
}

Measured memory_bytes: 0
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

n,m = map(int, input().split())
s = input()
t = input()

if s[0] != t[0]:
    print(-1)
    exit()

g = lcm(n,m)

if n < m:
    sm = n
    bi = m
    ls = s
    bs = t
else:
    sm = m
    bi = n
    ls = t
    bs = s
a = g//sm
b = g//bi
flg = False
for i in range(sm):
    p = i * a
    if p % b == 0:
        if bs[p//b] != ls[i]:
            flg = True
            break
if flg:
    print(-1)
else:
    print(g)


Measured memory_bytes: 5432
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;
int main() {
	int ans = 10000;
	int X;
	string S;
	cin >> S;
	for (int i = 0; i < S.size() - 2; i++) {
		X = 0;
		for (int j = 0; j < 3; j++) {
			X += (S[i + j] - '0')*pow(10, 2 - j);
		}
		if (ans > abs(X - 753))ans = abs(X - 753);
	}
	cout << ans << endl;
	return 0;
}

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

int main(){ 
  int a;
  cin>>a;
  
  while(a>0){
    int b=sqrt(a);
    if(b*b==a){
      cout<<a<<endl;
      return 0;
    }
    for(int i=0;i<11;i++){
      if(i*i*i==a){
        cout<<a<<endl;
        return 0;
      }
    }
    for(int i=0;i<6;i++){
      if(i*i*i*i==a){
        cout<<a<<endl;
        return 0;
      }
    }
    for(int i=0;i<4;i++){
      if(i*i*i*i*i==a){
        cout<<a<<endl;
        return 0;
      }
    }
    for(int i=0;i<4;i++){
      if(i*i*i*i*i*i==a){
        cout<<a<<endl;
        return 0;
      }
    }
    if(a==128){
      cout<<a<<endl;
      return 0;
    }
    a--;
  }
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    from collections import Counter
    M = max(A)
    C = Counter(A)
    table = [False] * (M + 1)
    for c in C:
        for j in range(c+c, M + 1, c):
            table[j] = True
    ans = 0
    for a in A:
        if table[a] or C[a] > 1:
            continue
        ans += 1
    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

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


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

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(obj) (obj).begin(), (obj).end()
#define bit(n) (1LL << (n))

using namespace std;

typedef long long ll;

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int h,w; cin>>h>>w;
  
  int x[8] = {1,1,0,-1,-1,-1,0,1};
  int y[8] = {0,-1,-1,-1,0,1,1,1};
  
  string b[50];
  
  rep(i,h) {
    cin>>b[i];
  }
  
  rep(i,h) {
    rep(j,w) {
      char c = b[i][j];
      
      if(c=='#') continue; 
      
      int num = 0;
      rep(k,8) {
        
        int ni = i+y[k];
        int nj = j+x[k];
        
        if(ni<0 or ni>=h) continue;
        if(nj<0 or nj>=w) continue;
          
        char tc = b[ni][nj];
        if(tc=='#') ++num;
      }
      
      b[i][j] = char('0' + num);
    }
  }
  
  rep(i,h) cout<<b[i]<<endl;
}

Measured memory_bytes: 3656
#include <iostream>
#include <bits/stdc++.h>
#include <deque>
#include <vector>
#include<cstdio>
#include<string>
using namespace std;
int main()
{
    long long n,c=0,r=0;
    cin>>n;
    long long a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        if(a[i+1]<=a[i])
        {
            c++;
        }
        else
        {
            if(c>r) r=c;
            c=0;
        }
    }
    cout<<r;
}


Measured memory_bytes: 1024
H, W = map(int, input().split())

if H * W % 3 == 0:
    print(0)
    exit()

S = H * W
a = (S // 3 // H) - 10
b = (S // 3 // W) - 10

ans1 = float('inf')
ans2 = float('inf')
for i in range(a, a + 30):
    if i <= 0 or i >= W:
        continue
    x = i * H
    y = (W - i) * (H//2)
    z = S - x - y
    ans1 = min(ans1, max(x, y, z) - min(x, y, z))

for i in range(b, b + 30):
    if i <= 0 or i >= H:
        continue
    x = i * W
    y = (H - i) * (W//2)
    z = S - x - y
    ans2 = min(ans2, max(x, y, z) - min(x, y, z))
print(min(ans1, ans2, H, W))


Measured memory_bytes: 38256
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define _repargs(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _repargs(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
//#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p = 0) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template
ll N, A, B, C, D;
const ll inf = 1LL << 62;

int two[2] = {0, -1};
int two2[2] = {0, 1};
int three[3] = {0, -1, -2};
int three2[3] = {0, 2, 1};
int five[5] = {0, -1, -2, -3, -4};
int five2[5] = {0, 4, 3, 2, 1};


ll dfs(ll K, map<ll, ll> &M) {
//    output(K);
    if(K == 0) return 0;
    if(K == 1) return D;
    if(M[K] > 0) return M[K];
    ll ret;
    if(inf / D <= K) ret = inf;
    else ret = K * D;
    if(K + two[K % 2] > 0) ret = min(ret, D * abs(two[K % 2]) + A + dfs((K + two[K % 2]) / 2, M));
    if(K + two2[K % 2] > 0) ret = min(ret, D * abs(two2[K % 2]) + A + dfs((K + two2[K % 2]) / 2, M));
    if(K + three[K % 3] > 0) ret = min(ret, D * abs(three[K % 3]) + B + dfs((K + three[K % 3]) / 3, M));
    if(K + three2[K % 3] > 0) ret = min(ret, D * abs(three2[K % 3]) + B + dfs((K + three2[K % 3]) / 3, M));
    if(K + five[K % 5] > 0) ret = min(ret, D * abs(five[K % 5]) + C + dfs((K + five[K % 5]) / 5, M));
    if(K + five2[K % 5] > 0) ret = min(ret, D * abs(five2[K % 5]) + C + dfs((K + five2[K % 5]) / 5, M));
    return M[K] = ret;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    
    int T;
    cin >> T;
    rep(t, T) {
        cin >> N >> A >> B >> C >> D;
        map<ll, ll> M;
        ll ans = dfs(N, M);
        output(ans);
    }
    
    return 0;
}


Measured memory_bytes: 4356
a, b, c, d = gets.split.map(&:to_i)

count = b - a + 1
lcm = c.lcm(d)

cc = (b / c) - (a / c)
cc += 1 if a % c == 0
dc = (b / d) - (a / d)
dc += 1 if a % d == 0
lc = (b / lcm) - (a / lcm)
lc += 1 if a % lcm == 0

puts count - (cc + dc - lc)


Measured memory_bytes: 1788
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>
#include <math.h>
#include <bitset>

#define P pair
#define X first
#define Y second
#define VSORT(v) sort(v.begin(), v.end())
#define VREV(v) reverse(v.begin(), v.end())
#define VMAX_P(v) max_element(v.begin(), v.end())
#define VMIN_P(v) min_element(v.begin(), v.end())
#define VMAX_IDX(v) distance(v.begin(), VMAX_P(v))
#define VMIN_IDX(v) distance(v.begin(), VMIN_P(v))
#define VCOPY(src, dst) copy(src.begin(), src.end(), back_inserter(dst))
#define SUPPER(src, dst) transform(src.begin(), src.end(), dst.begin(), toupper);
#define SLOWER(src, dst) transform(src.begin(), src.end(), dst.begin(), tolower);

using namespace std;
using ll = long long;

int main(int argc, const char *argv[])
{
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
}


Measured memory_bytes: 256
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]
graph = [[] for _ in range(N)]
idx = {}
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    idx[(a, b)] = i
    idx[(b, a)] = i

ans = [-1] * (N - 1)

stack = [(0, -1)]
seen = [False] * N
while stack:
    v, color = stack.pop()
    seen[v] = True
    c = 0
    for u in graph[v]:
        if seen[u]:
            continue
        c += 1
        if c == color:
            c += 1
        ans[idx[(v, u)]] = c
        stack.append((u, c))
print(max(ans))
print(*ans, sep='\n')


Measured memory_bytes: 104924