akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=100003,INF=1<<30;

int main(){
    
    int N,K;cin>>N>>K;
    vector<ll> A(N);
    
    ll sum=0;
    
    for(int i=0;i<N;i++){
        cin>>A[i];
        sum+=A[i];
    }
    
    vector<ll> B;
    
    for(ll i=1;i*i<=sum;i++){
        if(sum%i==0){
            B.push_back(i);
            B.push_back(sum/i);
        }
    }
    
    ll ans=0;
    
    for(int i=0;i<B.size();i++){
        
        ll Q=B[i];
        vector<pair<ll,ll>> S(N);
        
        for(int j=0;j<N;j++){
            S[j].first=A[j]%Q;
            S[j].second=Q-A[j]%Q;
        }
        
        sort(all(S));
        
        vector<ll> sum(N+1,0),sum2(N+1,0);
        
        for(int j=1;j<N+1;j++){
            sum[j]=sum[j-1]+S[j-1].first;
            sum2[j]=sum2[j-1]+S[j-1].second;
        }
        
        bool ok=false;
        
        for(int j=0;j<N+1;j++){
            if(sum[j]==sum2[N]-sum2[j]){
                if(sum[j]<=K) ok=true;
            }
        }
        
        if(ok) ans=max(ans,Q);
        
    }
    
    cout<<ans<<endl;
}


Measured memory_bytes: 256
n,t,s=map(int,raw_input().split())
ab=[map(int,raw_input().split()) for _ in xrange(n)]
dp=[[0]*(t+1) for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(1,t+1):
        if j<ab[i][1]:
            dp[i+1][j]=dp[i][j]
            continue
        if j-ab[i][1]<s<j:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
            continue
        dp[i+1][j]=max(dp[i][j],dp[i][j-ab[i][1]]+ab[i][0])
print(dp[n][t])

Measured memory_bytes: 221028
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000];
int main()
{
	cin>>n;
	for(int i=1;i<=2*n;i++)
	 cin>>a[i];
	sort(a+1,a+2*n+1);
	//for(int i=1;i<=2*n;i++)
	 //cout<<a[i]<<' ';
	long long o=0;
	for(int i=1;i<=2*n;i+=2)
	{
		o+=a[i];
	}
	cout<<o;
	return 0;
}

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

using namespace std;
typedef long long ll;

int main() {
  ll a, b, k;
  cin >> a >> b >> k;
  if (a > k) {
    cout << (a - k) << " " << b << endl;
  } else {
    k -= a;
    cout << 0 << " " << max(0LL, b - k) << endl;
  }
  return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <string>
#include <bitset>
#include <fstream>
#include <iomanip>

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef vector<pii> vii;

#define INF 1000000007ll
#define PB push_back
#define MP make_pair
#define X first
#define Y second
#define Min(a,b) (((a) < (b))?(a):(b))
#define Max(a,b) (((a) > (b))?(a):(b))
#define Abs(a) (((a) > 0)?(a):(-1)*(a))
#define cil(a,b) ( ((a)%(b) == 0)?((a)/(b)):((a)/(b)+1) )
#define SIZE 100010

int a[SIZE];

int main() {
   int n, k = 0, d = INF, m = 0;
   cin >> n;
   for (int i = 0 ; i < n ; ++i) {
      cin >> a[i];
      d = min (a[i], d);
      m = max (a[i], m); 
   }
   if (d != m - 1 && d != m) {
      cout << "No" << endl;
      return 0;
   }
   for (int i = 0 ; i < n ; ++i) {
      if (a[i] == d) ++k;
   }
   if (d == m) {
      if (k >= 2 * d || k == d + 1) cout << "Yes" << endl;  
      else cout << "No" << endl;
      return 0;
   }
   if (k > d || n - k < 2 * (d + 1 - k)) {
      cout << "No" << endl;
      return 0;
   }
   cout << "Yes" << endl;

   return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

using namespace std;

signed main() {
  IOS;
  int a, ac, i, minOne=10, ans=0;
  for (i = 0; i < 5; i++) {
    cin >> a;
    ac = (a+9)/10 * 10;
    ans += ac;
    if (a%10 > 0)
      minOne = min(minOne, a%10);
  }

  cout << ans - (10-minOne) << endl;
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

K = INT()

start = K // 50
avoid = start + 50 - K % 50

ans = []
for i in range(start, start+51):
    if i != avoid:
        ans.append(i)

print(len(ans))
print(*ans)


Measured memory_bytes: 3064
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    let v: Vec<i32> = buf.split_whitespace().map(|x| x.parse().unwrap()).collect();
    let (mut a, mut b, mut c) = (v[0], v[1], v[2]);
    let mut ans = 0_i32;
    loop {
        if a % 2 == 1 || b % 2 == 1 || c % 2 == 1 {
            break;
        }
        if a == b && b == c {
            ans = -1;
            break;
        }
        let (a_tmp, b_tmp, c_tmp) = (a, b, c);
        a = (b_tmp + c_tmp) / 2;
        b = (c_tmp + a_tmp) / 2;
        c = (a_tmp + b_tmp) / 2;
        ans += 1;
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1005,maxm=1005*1005;
struct node
{
    int from,to,next;
}edge[maxm<<1];
int head[maxn],tot=1,n,m;
void addedge(int u,int v)
{
    edge[++tot]=(node){u,v,head[u]};head[u]=tot;
}
int num;
int low[maxn],dfn[maxn],cnt,bridge[maxn];
void tarjan(int root,int id)
{
    low[root]=dfn[root]=++cnt;
    for(int i=head[root];i;i=edge[i].next)
    {
        if(i==(id^1))continue;
        int v=edge[i].to;
        if(!dfn[v])
        {
            tarjan(v,i);
            low[root]=min(low[root],low[v]);
            if(low[v]>dfn[root])
                bridge[++num]=i;
        }
        low[root]=min(low[root],dfn[v]);
    }
}
int haha()
{
		scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            int x,y;scanf("%d%d",&x,&y);
            addedge(x,y);addedge(y,x);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i,-1);
        printf("%d\n",num);
}
int sb=haha();
int main(){;}


Measured memory_bytes: 256
n = int(input())
count = 0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
l = make_divisors(n)
for i in range(len(l)):
  if l[i]-1 > 0 and n // (l[i]-1) == n % (l[i]-1):
    count += l[i]-1
print(count)

Measured memory_bytes: 3272
from sys import stdin
rs = lambda : stdin.readline().strip()
ri = lambda : int(rs())
ril = lambda : list(map(int, rs().split()))

MOD = 1_000_000_007

def pow(a, b):
    ret = 1
    while b > 0:
        if (b & 1) == 1:
            ret = ret * a % MOD
        a = a * a % MOD
        b >>= 1
    return ret

def main():
    N = ri()
    ans = pow(10, N) - pow(9, N) - pow(9, N) + pow(8, N)
    ans %= MOD
    print(ans)



if __name__ == '__main__':
    main()


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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;
const ll m=1LL<<32;

int main(){

  ll n,a,b;cin>>n>>a>>b;

  ll ans=a*(n/(a+b));
  if(n%(a+b)!=0){
    if(n%(a+b)<a)ans+=n%(a+b);
    else ans+=a;
  }
  out(ans);

  return 0;
}


Measured memory_bytes: 256
import sys
N,Y = map(int,input().split())

for i in range(N+1):
  for j in range(N-i+1):
    if (i)*10000 + (j)*5000 + (N-i-j)*1000 == Y:
      print(i,j,N-i-j)
      sys.exit()

print(-1,-1,-1)      

Measured memory_bytes: 8912
a=[0]*10**7
a[1]=int(input())
cnt=[a[1]]

def f(v):
  if v%2:
    return 3*v+1
  else:
    return v//2

for i in range(2,10**7+1):
  a[i] = f(a[i-1])
  if a[i] in cnt:
    print(i)
    break
  else:
    cnt.append(a[i])



Measured memory_bytes: 86788
#include <bits/stdc++.h>
#define rep( i, n ) for (long long i = 0; i < ( long long )(n); i++)

using namespace std;
typedef long long ll;


int main(){
	ll n,k;
	ll max = 0;
	cin>>n>>k;
	
	vector <int> p(n);
	rep( i , n ){
		cin>>p[ i ];
		if( i < k ) max+=p[i];
	}
	ll ob = max;
	for(long long i = 1 ; i < ( long long )(n-k+1) ; i++){
			ob = ob - p[i-1] + p[k+i-1];
			if(ob > max){
				 max = ob;
			}
	}
	cout << fixed << setprecision(10);
	cout<<((long double)max+(long double)k)/2.0;
}


Measured memory_bytes: 1024
private var N: Int = 0
private var h: List<Int> = emptyList()
private var INF = Long.MAX_VALUE
private val memo = mutableMapOf<Int, Long>()

fun main(args: Array<String>) {
    N = readLine()!!.toInt()
    h = readLine()!!.split(" ").map(String::toInt)

    println(jump(N - 1))

}

private fun jump(i: Int): Long {

    if (memo.containsKey(i)) {
        return memo[i]!!
    }

    if (i == 0) {
        return 0
    }

    var res = INF

    // 足場 i-1 から来た場合
    res = Math.min(res, jump(i - 1) + Math.abs(h[i] - h[i - 1]))

    // 足場 i-2 から来た場合
    if (i > 1) {
        res = Math.min(res, jump(i - 2) + Math.abs(h[i] - h[i - 2]))
    }

    memo[i] = res
    return res
}


Measured memory_bytes: 76052
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int cnt[MAXN];
int up(int x){
	while(x<MAXN and cnt[x]<2)
		x++;
	return x;	
}
int down(int x){
	while(x>0 and cnt[x]<2)
		x--;
	return x;	
}
int main(){
    //~ freopen("file.in", "r", stdin);
    int n;
    scanf("%d",&n);
	int ans=n;
    while(n--){
		int x;
		scanf("%d",&x);
		cnt[x]++;
	}
	int p1=up(1);
	int p2=down(MAXN-5);
	while(p1<=p2){
		cnt[p1]--;cnt[p2]--;
		ans-=2;
		p1=up(p1);p2=down(p2);
	}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 640
S=input()
K=int(input())
l = []
for alpha in [chr(i) for i in range(97, 97+26)]:
  indexs = [k for k, v in enumerate(list(S)) if v == alpha]
  for index in indexs:
    for j in range(index,min(index+6,len(S)+1)):
      sub_s = S[index:j]
      l.append(sub_s)
  l = sorted(list(set(l)))
  if '' in l:
    l.remove('')
  if len(l) >= K:
    break
print(l[K-1])


Measured memory_bytes: 4724
LARGE = 10 ** 9 + 7


def solve(n, x_list):

    n_1_fac = 1
    for i in range(2, n):
        n_1_fac *= i
        n_1_fac %= LARGE

    res = 0
    for i in range(n - 1):
        res += (x_list[n - 1] - x_list[i]) * n_1_fac * pow(n - 1 - i, LARGE - 2, LARGE)
        res %= LARGE

    x_left = 0
    x_right = 0
    for k in range(1, n - 1):
        x_right += x_list[n - 1 - k]
        x_left += x_list[k - 1]
        res += (x_right - x_left) * n_1_fac * pow(k, LARGE - 2, LARGE) * pow(k + 1, LARGE - 2, LARGE)
        res %= LARGE
    return res


def main():
    n = int(input())
    x_list = list(map(int, input().split()))
    res = solve(n, x_list)
    print(res)


def test():
    assert solve(3, [1, 2, 3]) == 5
    assert solve(12, [
        161735902, 211047202, 430302156, 450968417, 628894325, 707723857,
        731963982, 822804784, 880895728, 923078537, 971407775, 982631932
    ]) == 750927044


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 14480
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int S = sc.nextInt();
        int sum = 0;
        for(int X = 0; X <= K; X++){
        	for(int Y = 0; Y <= K; Y++){
        		int Z = S - (X+Y);
        		if((0 <= Z)&&(Z <= K)) sum++;
        	}
        }
        System.out.println(sum);
	}

}

Measured memory_bytes: 23764
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;



int main()
{
  long long a,b,x;
  cin>>a>>b>>x;
long long result = 0;
result =  b/x-a/x;
if(a%x == 0)
    result++;
cout<<result<<endl;


return 0;
}


Measured memory_bytes: 3632
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

func solve() {
	a, b := getInt(), getInt()

	ab := []string{strings.Repeat(strconv.Itoa(a), b), strings.Repeat(strconv.Itoa(b), a)}
	sort.Strings(ab)

	ans := ab[0]
	fmt.Fprintln(wr, ans)
}

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

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	maxBufSize := int(1e8)
	sc.Buffer(make([]byte, 4096), maxBufSize)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() (ret int) {
	sc.Scan()
	ret, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return
}

func getIntSlice(n int) (ret []int) {
	ret = make([]int, n)
	for i := range ret {
		ret[i] = getInt()
	}
	return
}

func getString() (ret string) {
	sc.Scan()
	ret = sc.Text()
	return
}

func getRunes() (ret []rune) {
	ret = []rune(getString())
	return
}


Measured memory_bytes: 640
N, M = map(int, input().split())
a_list = tuple(map(int, input().split()))
b_list = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

a_list = sorted(a_list, reverse=True)
b_list = sorted(b_list, reverse=True)
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        a_i += 1
        ans *= b_i
        ans %= mod
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i
        ans %= mod
    else:
        ans *= (a_i*b_i - (N * M - i))
        ans %= mod
print(ans % mod)



Measured memory_bytes: 3188
/**
 *    author:  FromDihPout
 *    created: 2020-06-16
**/

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<pair<int,int>> a(n);
    vector<int> permute(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].f >> a[i].s;
        permute[i] = i;
    }
    double sum = 0;
    do {
        double dist = 0;
        pair<int,int> prev = a[permute[0]];
        for (int i = 1; i < n; i++) {
            int index = permute[i];
            dist += sqrt(pow(a[index].f - prev.f, 2) + pow(a[index].s - prev.s, 2));
            prev = a[index];
        }
        sum += dist;
    } while (next_permutation(permute.begin(), permute.end()));
    for (int i = 1; i <= n; i++) {
        sum /= i;
    }
    printf("%.10f", sum);
    return 0;
}

Measured memory_bytes: 256
package main

// Solution for https://atcoder.jp/contests/abc071/tasks/arc081_a

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
)

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var n int
	con.Scan(&n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		con.Scan(&a[i])
	}
	sort.Slice(a, func(i, j int) bool { return a[i] > a[j] })
	p := 0
	q := []int{}
	for len(q) < 2 && p < len(a)-1 {
		if a[p] == a[p+1] {
			q = append(q, a[p])
			p++
		}
		p++
	}
	if len(q) == 2 {
		con.Println(q[0] * q[1])
	} else {
		con.Println(0)
	}
	return nil
}


Measured memory_bytes: 4308
#include <bits/stdc++.h>
#define int long long int
#define ldouble long double
#define vin vector<int> 
#define rep(i,a,n) for(i=(a);i<(n);i++)
#define INF (int)1000000007

//setprecision()<<

using namespace std;

void fin(int i,int n,vin &a){
    rep(i,0,n){
        cin>>a.at(i);
    } 
} 

signed main() {
    int i;
    int N;
    cin>>N;
    
        cout<<(N-1)/2<<endl;
    
return 0;
}

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

int  main() {
  string a,b;
  cin>>a>>b;
  int n=stoi(a+b);
  int ans=0;
  for(int i=0;i<1000;i++) {
    if(n==i*i) {
      ans++;
      cout<<"Yes"<<endl;
      break;
    }
  }
  if(ans==0) {
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
N,M=map(int,input().split())
X,Y=(list(map(int,input().split())) for i in range(2))
x1,x2=([0]*N for i in range(2))
y1,y2=([0]*M for i in range(2))
m=10**9+7
for i in range(N-1):
    x1[i+1]=(x1[i]+(X[i+1]-X[i])*(i+1))%m
    x2[i+1]=(x2[i]+x1[i])%m
for i in range(M-1):
    y1[i+1]=(y1[i]+(Y[i+1]-Y[i])*(i+1))%m
    y2[i+1]=(y2[i]+y1[i])%m
print(((x1[-1]+x2[-1])*(y1[-1]+y2[-1]))%m)

Measured memory_bytes: 27120
#include <iostream>

using namespace std;

int main(){
	int x = 0;
	int a = 0;
	int b = 0;

	cin >> x >> a >> b;

	if(a>=b){
		cout << "delicious" << endl;	
	}
	else{
		if(x>=b-a){cout << "safe" << endl;}
		else {cout << "dangerous" << endl;}
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vec = vector<int>;
using intk = int64_t;

int main() {
int N,M,X;
  cin >>N>>M>>X;
  vec A(M); 
  for(int i=0;i<M;i++) cin >>A[i];
  sort(A.begin(),A.end());
  int mae =0;
  int usiro =0;
  for(int i=0;i<M;i++){
   if(A[i] > X) mae++;
    else usiro++;
  }
  cout <<min(mae,usiro)<<endl;
}
  


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int k,v,N,i,j,A[1000];
  scanf("%d",&N);
  for(k=0;k<N;k++){
    scanf("%d",&A[k]);
  }
  for(k=0;k<N;k++){
    printf("%d",A[k]);
    if(k<N-1){
    printf(" ");
    }
    }
  for(i=1;i<=N-1;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    printf("\n");
    A[j+1]=v;
    for(k=0;k<N;k++){
      printf("%d",A[k]);
      if(k<N-1){
      printf(" ");
      }
    }
   
  }
  printf("\n");
  return 0;
}
  



Measured memory_bytes: 2072
//=================================
// Created on: 2018/07/04 15:12:12
//=================================
#include <bits/stdc++.h>
using namespace std;
int main()
{
    for (int N;;) {
        cin >> N;
        if (N == 0) { break; }
        vector<int> coeff1(10, 0);
        vector<int> coeff2(10, 0);
        set<int> nz;
        map<char, int> ind;
        for (int i = 0; i < N; i++) {
            string s;
            cin >> s;
            reverse(s.begin(), s.end());
            for (int j = 0, d = 1; j < s.size(); j++, d *= 10) {
                const char c = s[j];
                if (ind.find(c) == ind.end()) {
                    const int s = ind.size();
                    ind[c] = s;
                }
                const int in = ind[c];
                (i < N - 1 ? coeff1 : coeff2)[in] += d;
                if (j == s.size() - 1 and s.size() > 1) { nz.insert(in); }
            }
        }
        vector<int> num{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int div = 1;
        for (int i = 0; i < 10 - (int)ind.size(); i++) { div *= (i + 1); }
        int ans = 0;
        do {
            bool ok = true;
            for (const int nzz : nz) {
                if (num[nzz] == 0) {
                    ok = false;
                    break;
                }
            }
            if (not ok) { continue; }
            int left = 0, right = 0;
            for (int i = 0; i < ind.size(); i++) { left += coeff1[i] * num[i], right += coeff2[i] * num[i]; }
            if (left == right) { ans++; }
        } while (next_permutation(num.begin(), num.end()));
        cout << ans / div << endl;
    }
    return 0;
}



Measured memory_bytes: 3004
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    s = input()
#    s = "1"*10**5
    n = len(s)
    if n&1:
        t = 1
        sf = n//2-1
        so = n//2+1
        ss = s[n//2]
        while sf >= 0:
            if s[so] == ss == s[sf]:
                t += 1
                sf -= 1
                so += 1
            else:
                break
        print(t+n//2)
    else:
        if s[n//2] == s[n//2-1]:
            ss = s[n//2]
            t = 1
            sf = n//2-2
            so = n//2+1
            while sf >= 0:
                if s[so] == ss == s[sf]:
                    t += 1
                    sf -= 1
                    so += 1
                else:
                    break
            print(n//2+t)
        else:
            print(n//2)


    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 74908
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int MOD = 1000000007;

signed main()
{
    int n, k;
    cin >> n >> k;
    
    vi a(n);
    rep(i, n){
        cin >> a[i];
    }
    
    vector<vvi> dp(256, vvi(n+1, vi(n+1)));
    rep(i, n+1){
        dp[0][0][i] = 1;
    }
    
    rep(i, n) rep(m, n) rep(b, 256) {
        dp[b][m+1][i+1] = (dp[b][m+1][i] + dp[b^a[i]][m][i]) % MOD;
    }
    
    int ans = 0;
    ll f = 1;
    
    rep(m, n){
        f = (f * (m+1)) % MOD;
        ans = (ans + (dp[k][m+1][n] * f) % MOD) % MOD;
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 11520
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		execute();
	}
	
	private static final long WARU = 1000000007;
	
	private static void execute() {
		try (Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			long ans = 1;
			
			int[] arr = new int[3];
			for(int x=0; x<3; x++) {
				arr[x] = -1;
			}
			
			for(int i=0; i<n; i++) {
				int c = sc.nextInt();
				int b = 0;
				for(int x=0; x<3; x++) {
					if(c-1 == arr[x]) {
						if(b==0) {
							arr[x] = c;
						}
						b++;
					}
				}
				ans = ans*b%WARU;
			}
			
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 47588
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int k = sc.nextInt();
    long l = (long) (k * Math.pow(k - 1, n - 1));
    System.out.println(l);
  }

}

Measured memory_bytes: 35788
#include <algorithm>
#include <cstdio>
#include <deque>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int main(void) {
    int n;
    cin >> n;
    if (n % 2 != 0)
        n *= 2;
    cout << n << endl;
    return 0;
}

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

int main() {
  int n,a,b;
  cin >> n;
  a = n/100;
  b = n%10;
  if(a == b){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import fractions

from sys import stdin


def main():
    n = int(stdin.readline())
    t = [int(stdin.readline()) for _ in range(n)]
    dp = [0 for _ in range(n)]
    dp[0] = t[0]
    for i in range(1, n):
        dp[i] = t[i] * dp[i-1] // fractions.gcd(t[i], dp[i-1])
    print(dp[-1])


if __name__ == "__main__":
    main()


Measured memory_bytes: 5048
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
const int inf=1e9+7;
const ll INF=1e18;

int main(){
    int n;cin>>n;
    string s;cin>>s;
    int tmp=0;int r=0;
    rep(i,n){
        if(s[i]==')'){
            if(tmp)tmp--;
            else r++;
        }
        else tmp++;
    }
    string ans;
    rep(i,r)ans+='(';
    ans+=s;
    rep(i,tmp)ans+=')';
    cout<<ans<<endl;
}

Measured memory_bytes: 256
h,w=map(int,input().split())
l=[input() for _ in range(h)]
nb=[(0,1),(1,0),(0,-1),(-1,0)]
for i in range(h):
	for j in range(w):
		if l[i][j]=='#':
			for a,b in nb:
				if 0<=i+a<=h-1 and 0<=j+b<=w-1 and l[i+a][j+b]=='#':
					break
			else:
				print('No')
				exit()
print('Yes')
			

Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>
int main()
{
    int a,b,m=1,n=1;
    long int s=0,k,l,p=0;
    scanf("%d%d",&a,&b);
    int i,j;
    for(i=1;i<=b;i++){
       k=a*m;
       s=s+k;
       m=m*10;
    }
    for(j=1;j<=a;j++){
        l=b*n;
        p=p+l;
        n=n*10;
    }
    if(p>=s){
        printf("%d\n",p);
    }
    else{
        printf("%d\n",s);
    }
    return 0;

}


Measured memory_bytes: 1732
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}
//}}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int x;
	cin >> x;
	int sum = 100;
	int cnt = 1;
	while(sum <= x){
		if((x - sum) <= cnt * 5) return cout << 1 << '\n',0;
		sum += 100;
		++cnt;
	}
	cout << 0 << '\n';
	return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
#include <functional>
#include <numeric>
#include <cassert>
#include <algorithm>
#include <functional>
//#include "bits/stdc++.h"
using namespace std;
//using namespace std::vector;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)

#define huge 1000000007
typedef long long int ll;
ll gcd(ll a, ll b);
ll bur(ll N, ll X);
bool IsPrime(int num);

int main(void) {

	ll N = 0;
	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll D = 0;
	ll L = 0;
	ll P = 0;
	//ll T = 0;
	//ll M = 0;
	ll h[1000] = {};
	//ll b[100] = {};
	//ll c[100] = {};
	//ll d[100] = {};

	//ll v[3] = {};
	//ll *c, *s, *n;
	string S[50],T[50],U[52];
	ll count = 0;
	ll count2 = 0;
	float sum = 0;
	ll min = 1000000000000;
	ll max = 1;
	ll dist1 = 0;
	ll dist2 = 0;
	ll now = 0;
	int tmax = 0;
	int tmax2 = 0;
	//int flag = 0;
	char temp,head;
	//int is = 0;
	bool flag = false;
	
	//char p;

	ll all = 0;
	ll niku = 0;
	ll state = 2;
	bool down = true;
	

	//cin >> S;
	
	
	
	
	cin >> A >> B >> C;
	vector<int> tr(3);
	
	
	if((C-B)==(B-A))
	cout << "YES" << endl;
	else
		cout << "NO" << endl;

	//x = (ll *)malloc((N+1) * sizeof(ll));
	//c = (ll *)malloc((N) * sizeof(ll));
	//cin >> D >> G;
	//vector<pair<int,int>> tr(M);
	//vector<pair<int,int>> qes(Q);
	//sort(c.begin(), c.end());
	
	//cout << c[2] - c[1] << endl;

	
	/*A = N / 1000;
	N %= 1000;
	B = N / 100;
	N %= 100;
	C = N / 10;
	N %= 10;
	D = N;*/
	


	//cin >> N >> M;

	//vector<pair<int,int>> c(M);
	////vector<pair<int, int>> e(M);
	//vector<ll> d(M);

	//rep(i, 0, M) {
	//	cin >> c[i].first >> c[i].second;
	//	//e[i].first = c[i].first;
	//	//e[i].second = c[i].second;

	//}
	////sort(c.begin(), c.end());

	//

	//rep(i, 0, M) {

	//	
	//	
	//	rep(j, 0, M) {
	//		if (c[i].first == c[j].first && c[j].second < c[i].second) {
	//			d[i]++;
	//			//cout << j << endl;
	//		}
	//	}
	//	cout << std::setfill('0') << std::right << std::setw(6) << c[i].first;
	//	cout << std::setfill('0') << std::right << std::setw(6) << d[i]+1 << endl;
	//}

	return 0;

}

ll bur(ll N,ll X) {
	ll pan = 1;
	ll pat = 1;
	ll burg = 0;



	if (X > burg) {
		if (N == 0)
			return pat;


		burg += pan;
		burg += bur(N - 1, X);
		burg += pat;
		burg += bur(N - 1, X);
		burg += pan;


	}

	return burg;

}

ll gcd(ll a, ll b) {
	
	/* 自然数 a > b を確認・入替 */
	if (a<b) {
		ll tmp = a;
		a = b;
		b = tmp;
	}
	ll x = b;
	ll y = a;
	/* ユークリッドの互除法 */
	ll r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}


	return y/b*x;
}

bool IsPrime(int num)
{
	if (num < 2) return false;
	else if (num == 2) return true;
	else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			// 素数ではない
			return false;
		}
	}

	// 素数である
	return true;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define M 1000000007
int main(){
  int n,k,q,b;cin>>n>>k>>q;
  vector<int> a(n,k-q);
  for(int i=0;i<q;i++){
    cin>>b;a[b-1]++;
  }
  for(int i=0;i<n;i++){
    if(a[i]>0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-

"""
クイックソート
"""

N = int(input())
aN = [[None] * 2 for i in range(N)]
for i in range(N):
    suit, num = input().split()
    aN[i][0] = suit
    aN[i][1] = int(num)

def partition(p, r):
    # 今回は基準xの選び方が最後尾固定だけど、
    # これをうまく選ぶ方がクイックソートは高速になる
    x = aN[r][1]
    i = p-1
    for j in range(p, r):
        if aN[j][1] <= x:
            i = i+1
            aN[i], aN[j] = aN[j], aN[i]
    aN[i+1], aN[r] = aN[r], aN[i+1]
    # 基準となった末尾要素のindex
    return i+1

def quick_sort(p, r):
    if p < r:
        # 再帰処理の中でパーティションを使う
        q = partition(p, r)
        quick_sort(p, q-1)
        quick_sort(q+1, r)

# 安定比較用にライブラリで安定ソートする
aN2 = sorted(aN, key=lambda x: x[1])
quick_sort(0, N-1)

# クイックソートは安定ではないが、
# マージソートに対して、メモリ領域を使わない利点がある
if all([aN[i][0] == aN2[i][0] for i in range(N)]):
    print('Stable')
else:
    print('Not stable')

for i in range(N):
    print(*aN[i])



Measured memory_bytes: 19664
import sys

N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

for y in range(N-M+1):
    for x in range(N-M+1):
        for k in range(M):
            if A[y+k][x:x+M] != B[k]:
                break
        else:
            print("Yes")
            sys.exit()
print("No")

Measured memory_bytes: 3064
#include <set>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n; char c[3009][3009];
int main() {
	cin >> n;
	vector<int> x(n), y(n);
	vector<string> s(n);
	for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> s[i];
	vector<int> tx = x, ty = y;
	sort(tx.begin(), tx.end());
	tx.erase(unique(tx.begin(), tx.end()));
	sort(ty.begin(), ty.end());
	ty.erase(unique(ty.begin(), ty.end()));
	for (int i = 0; i < n; i++) {
		x[i] = lower_bound(tx.begin(), tx.end(), x[i]) - tx.begin();
		y[i] = lower_bound(ty.begin(), ty.end(), y[i]) - ty.begin();
		c[x[i]][y[i]] = s[i][0];
	}
	int ret = 0;
	for (int i = 0; i < n; i++) {
		vector<set<int> > px(tx.size());
		vector<set<int> > py(ty.size());
		for (int j = 0; j < n; j++) {
			px[x[j]].insert(y[j]);
			py[y[j]].insert(x[j]);
		}
		px[x[i]].erase(y[i]);
		py[y[i]].erase(x[i]);
		int cx = x[i], cy = y[i], cnt = 1;
		while (true) {
			if (c[cx][cy] == '<' || c[cx][cy] == '>') {
				set<int>::iterator it = py[cy].lower_bound(cx);
				if (c[cx][cy] == '<') {
					if (it == py[cy].begin()) break;
					else it--;
				}
				else if (it == py[cy].end()) break;
				cx = *it;
			}
			else {
				set<int>::iterator it = px[cx].lower_bound(cy);
				if (c[cx][cy] == '^') {
					if (it == px[cx].begin()) break;
					else it--;
				}
				else if (it == px[cx].end()) break;
				cy = *it;
				px[cx].erase(it);
			}
			px[cx].erase(cy);
			py[cy].erase(cx);
			cnt++;
		}
		ret = max(ret, cnt);
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 7852
#include <iostream>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

string S[2];
ll dp[60][9];

int main() {
  int N;
  cin >> N >> S[0] >> S[1];
  for (int j = 0; j < 3 * 3; j++) {
    int u = j / 3, d = j % 3;
    if (S[0][0] == S[1][0]) {
      dp[0][j] = u == d;
    } else {
      dp[0][j] = u != d;
    }
  }
  for (int i = 1; i < N; i++) {
    for (int j = 0; j < 3 * 3; j++) {
      for (int k = 0; k < 3 * 3; k++) {
        int u = j / 3, d = j % 3;
        int uu = k / 3, dd = k % 3;
        if (S[0][i] == S[1][i]) {
          dp[i][k] += dp[i-1][j] * (uu == dd) * (u != uu) * (d != dd);
        } else if (S[0][i-1] == S[0][i]) {
          dp[i][k] += dp[i-1][j] * (u == uu) * (d == dd);
        } else {
          dp[i][k] += dp[i-1][j] * (u != uu) * (d != dd) * (uu != dd);
        }
        dp[i][k] %= MOD;
      }
    }
  }
  ll res = 0;
  for (int j = 0; j < 3 * 3; j++) {
    res = (res + dp[N-1][j]) % MOD;
  }
  cout << res << endl;
  return 0;
}


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

int main(){
  int n;
  cin >> n;
  map<string, int> mp;
  for(int i = 0; i < n; i++){
  	string s; cin >> s;
  	mp[s]++;
  }
  
  int ans = 0;
  for(auto p: mp) ans++;
  cout << ans << endl;
}


Measured memory_bytes: 19192
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
static const int INF = 2000000000;



int main(){
  int a, b;
  cin >> a >> b;
  int keta = 0;
  int d = b;
  while (b > 0){
    b /= 10;
    keta++;
  }

  int c = a * pow(10, keta) + d;
  bool ok = false;
  rep(i, 331){
    if (i*i == c)ok = true;
  }
  if (ok) cout << "Yes\n";
  else cout << "No\n";
}

Measured memory_bytes: 256
class Problem
  attr_accessor *(?a..?z).to_a.map(&:to_sym)
  def initialize
    @n,@m = gets.split.map(&:to_i)
    @a = Array.new(n){ gets.split.map(&:to_i) }
  end

  def solve
    ans = 0
    [1,-1].repeated_permutation(3) do |signs|
      cnt = subtask(signs)
      ans = cnt if ans < cnt
    end
    ans
  end

  def subtask(signs)
    dp = n.times.map do |i|
      a[i].zip(signs).map{|a,b|a*b}.sum
    end
    dp.sort.reverse.take(m).sum
  end

  def show(ans)
    puts ans
  end
end

Problem.new.instance_eval do
  show(solve)
end


Measured memory_bytes: 14328
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

template<class T>
bool UpdateMax(T &a, const T &b){
  if(a<b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template<class T>
bool UpdateMin(T &a, const T &b){
  if(a>b){
    a=b;
    return true;
  }else{
    return false;
  }
}

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  lint n;
  cin>>n;
  vector<pair<lint,lint>> a(n+2);
  for(lint i = 1; i < n + 1; ++i){
    lint v;
    cin>>v;
    a[i]=make_pair(v,i);
  }
  a[0]=make_pair(INT32_MIN,0);
  a[n+1]=make_pair(INT32_MIN,n+1);
  std::sort(a.begin(), a.end());
  lint result=0;
  set<lint> itr;
  for(auto p:a){
    if(p.first==INT32_MIN){
      itr.insert(p.second);
      continue;
    }

    auto ri=itr.upper_bound(p.second);
    auto li=ri;
    li--;
    result+=p.first*(*ri-p.second)*(p.second-*li);
    itr.insert(p.second);
  }
  cout<<result<<endl;




  return 0;
}




Measured memory_bytes: 12800
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x%mod;
}

int mod_pow(int x, int y, int mood) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = res * x%mood;
		x = x * x%mood;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int h, w;
int ans = INF;

signed main() {
	cin >> h >> w;
	if (h % 3 == 0 || w % 3 == 0) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 1; i < h; i++) {
		if (w % 2)ans = min(ans, max({ i*w,(h - i)*(w / 2),(h - i)*(w / 2 + 1) }) - min({ i*w,(h - i)*(w / 2),(h - i)*(w / 2 + 1) }));
		else ans = min(ans, max(i*w, (h - i)*(w / 2)) - min(i*w , (h - i)*(w / 2)));
	}
	for (int i = 1; i < w; i++) {
		if (h % 2)ans = min(ans, max({ i*h,(w - i)*(h / 2),(w - i)*(h / 2 + 1) }) - min({ i*h,(w - i)*(h / 2),(w - i)*(h / 2 + 1) }));
		else ans = min(ans, max(i*h, (w - i)*(h / 2)) - min(i*h, (w - i)*(h / 2)));
	}
	ans = min(ans, min(h, w));
	cout << ans << endl;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc058/tasks/abc058_b
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    o = input()
    e = input()
    ans = ''
    for i in range(len(o)):
        ans += o[i]
        if i < len(e):
            ans += e[i]

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]
ans = 10**10
for i in range(2**N):
    cost = 0
    rikai = [0 for i in range(M)]
    for j in range(N):
        if i>>j&1:
            cost += A[j][0]
            for k in range(M):
                rikai[k] += A[j][k+1]
    if min(rikai) >= X:
        ans = min(ans,cost)
print(-1 if ans == 10**10 else ans)



Measured memory_bytes: 9212
n, k = gets.chomp.split(" ").map(&:to_i)
a = gets.strip.split(' ').map(&:to_i)
ans = 0
sum = 0
for i in 0..n-1 do
  sum = a[i] + sum
  if i>=k-1 then
    ans=sum if ans<sum
    sum=sum-a[i-k+1]
  end
end
puts (ans+k).to_f/2

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

int main(void){

    int N,T;cin>>N>>T;

    vector<pair<int, int>> ct(N);
    for (int i = 0; i < N; ++i) {
        int a, b; cin>>a>>b;
        ct[i] = make_pair(a, b);
    }

    sort(ct.begin(), ct.end());
    for (int i = 0; i < N; ++i) {
        if(ct[i].second <= T){
            cout<<ct[i].first<<endl;
            return 0;
        }
    }
    cout<<"TLE"<<endl;

    return 0;
}

Measured memory_bytes: 256
from sys import stdin


def main():
    s = next_str()

    best = 0
    cnt = 0
    flg = False

    for v in s:
        if v == 'A':
            flg = True
        if flg:
            cnt += 1
        if flg and v == 'Z':
            best = cnt

    print(best)


def next_int() -> int:
    return int(next_str())


def next_str() -> str:
    result = ""
    while True:
        tmp = stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
int main() {
  int n;cin>>n;
  
  vector<ll> vec(n);
  
  rep(i,n) cin>>vec[i];
  
  int count=0;
  rep(i,n) {
    if (vec[i]%2==1) {
      count++;
    }
  }
  
  if (count%2==1) {
    cout<<"NO"<<endl;
  }
  else {
    cout<<"YES"<<endl;
  }
  
  
  
}

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

int main(){
    int n, i, j;
    cin >> n;
    string s[n];
    cin >> s[0];
    for(i=1; i<n; i++){
        cin >> s[i];
        if(s[i-1][s[i-1].length()-1] != s[i][0]){
            cout << "No";
            return 0;
        }
        for(j=0; j<i; j++){
            if(s[j] == s[i]){
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    string[] str=Console.ReadLine().Split(' ');
     double A=double.Parse(str[0]);
     double B=double.Parse(str[1]);
      
     for(int i=1;i<=1250;i++){
       if(((int)(i*0.08)==A)&&((int)(i*0.1)==B)){
         Console.WriteLine(i);
       break;
       }
       
       if(i==1250){
         Console.WriteLine(-1);
       }
     }
     }
    
  }

}


Measured memory_bytes: 27276
#include <bits/stdc++.h>
using namespace std;
# define ll long long int
#define M 1000000007
#define ff first
#define ss second
#define pb push_back
#define inf 10000000000000

							
									//nestedcode


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,i,ans = 0,b,c,q;
   cin>>n;
   ll a[n+5];
   map<ll,ll> m;
   for(i=0;i<n;i++){
       cin>>a[i];
       ans += a[i];
       m[a[i]]++;
   }
   cin>>q;
   while(q--){
       cin>>b>>c;
       ans -= m[b]*b;
       ans += m[b]*c;

      
       m[c] += m[b];
        m[b] = 0;
        cout<<ans<<endl;
   }
}

Measured memory_bytes: 10304
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <string>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	long long n;
	cin >> n;

	long long ans = 0;
	for (long long i = 1; i * i <= n; ++i) {
		if (n % i == 0) {
			long long m = n / i - 1;
			if (m && n / m == n % m) {
				ans += m;
			}
			long long j = n / i;
			if (j != i) {
				m = n / j - 1;
				if (m && n / m == n % m) {
					ans += m;
				}
			}
		}
	}

	cout << ans << "\n";

	return 0;

}

Measured memory_bytes: 3648
#!/usr/bin/env python3
#ABC129 D

H,W = list(map(int,input().split()))
Lamp = [list(input()) for _ in range(H)]
field = [[True for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
            if Lamp[i][j] == '#':
                field[i][j] = False
L = [[1 for _ in range(W)] for _ in range(H)]
R = [[1 for _ in range(W)] for _ in range(H)]
U = [[1 for _ in range(W)] for _ in range(H)]
D = [[1 for _ in range(W)] for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j]:
            if i-1 >= 0:
                if field[i-1][j]:
                    D[i][j] = D[i-1][j]+1
            if j-1 >= 0:
                if field[i][j-1]:
                    L[i][j] = L[i][j-1]+1
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if field[i][j]:
            if i+1 < H:
                if field[i+1][j]:
                    U[i][j] = U[i+1][j]+1
            if j+1 < W:
                if field[i][j+1]:
                    R[i][j] = R[i][j+1]+1

for i in range(H):
    for j in range(W):
        ans = max(ans,R[i][j]+L[i][j]+U[i][j]+D[i][j]-3)
print(ans)


Measured memory_bytes: 348424
#import math
#import copy
#import sys
#import bisect
#input = sys.stdin.readline
mod=10**9+7
def swap(a,b):
    c=a
    a=b
    b=c
    return a,b
def factorial(x): #階乗計算
    n=1
    for i in range(x):
        n=(n*(i+1))%mod
    return n

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcm(a, b):
    return((a*b)//gcd(a,b))
def div(x): #約数配列
    div=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            div.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      div.append(x)
    return div
def div2(x): #素因数分解配列
    div2=[]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        while x%check==0:
            div2.append(check)
            x/=check
        check+=1
    if x != 1:
      div2.append(x)
    return div2

def main():
    # x,y = map(int,input().split())           x=1,y=2
    # a = input().split()                      a=['1','2','3',...,'n']
    # a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    # li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    # 複数行の「1 2 3 4」型の入力を一配列に
    # x = sorted([list(map(int, input().split())) for _ in range(n)])
    # ソート x.sort(key=lambda y:y[1])
    # [chr(i) for i in range(97, 97+26)] 英語小文字リスト
    # [chr(i) for i in range(65, 65+26)] 英語大文字リスト atcoder
    # ord(c) chr(2) alphabet <=> number
    n=int(input())
    a = list(map(int,input().split()))
    ans=1
    k=0
    a.sort()
    for i in range(n-1):
        k+=a[i]
        if k*2>=a[i+1]:
            ans+=1
        else:
            ans=1
    print(ans)

main()

Measured memory_bytes: 63856