akhauriyash/Code-Regression huggingface dataset:
package main

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

type Scanner struct {
	reader  *bufio.Reader
	buffer  []string
	pointer int
}

func NewScanner() *Scanner {
	return &Scanner{
		reader:  bufio.NewReaderSize(os.Stdin, 4096),
		pointer: 0,
	}
}

func (self *Scanner) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, _ := self.reader.ReadLine()
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (self *Scanner) Next() string {
	if self.pointer >= len(self.buffer) {
		line := self.NextLine()
		self.buffer = strings.Fields(line)
		self.pointer = 0
	}
	self.pointer++
	return self.buffer[self.pointer-1]
}

func (self *Scanner) NextInt() int {
	s := self.Next()
	i, _ := strconv.ParseInt(s, 10, 32)
	return int(i)
}

func (self *Scanner) NextLong() int64 {
	s := self.Next()
	l, _ := strconv.ParseInt(s, 10, 64)
	return int64(l)
}

func (self *Scanner) NextFloat() float32 {
	s := self.Next()
	f, _ := strconv.ParseFloat(s, 32)
	return float32(f)
}

func (self *Scanner) NextFloat64() float64 {
	s := self.Next()
	d, _ := strconv.ParseFloat(s, 64)
	return float64(d)
}

// SegTreeIntMin ... 区間内の最小値を求める
type SegTreeIntMin struct {
	segment []int
	size    int
}

// NewSegTreeIntMin ... 初期化
func NewSegTreeIntMin(vals []int, n int) *SegTreeIntMin {

	size := 1
	for size < n {
		size <<= 1
	}
	segment := make([]int, size*4-1)
	for i := 0; i < size*4-1; i++ {
		segment[i] = (1 << 31) - 1
	}

	for i := 0; i < n; i++ {
		segment[size+i-1] = vals[i]
	}

	return &SegTreeIntMin{
		segment: segment,
		size:    size,
	}
}

// Set ... indexの位置のvalueを更新,最小値を更新していく
func (segtree *SegTreeIntMin) Set(index int, value int) {

	k := segtree.size + index - 1
	segtree.segment[k] = value

	for k > 0 {
		k = (k - 1) >> 1
		if segtree.segment[(k<<1)+1] <= segtree.segment[(k<<1)+2] {
			segtree.segment[k] = segtree.segment[(k<<1)+1]
		} else {
			segtree.segment[k] = segtree.segment[(k<<1)+2]
		}
	}
}

// Query ... 区間[a,b)に含まれる最小値を返す
func (segtree *SegTreeIntMin) Query(a, b, left, right, k int) int {
	if b <= left || right <= a {
		return (1 << 31) - 1
	}

	if left <= a && b <= right {
		return segtree.segment[k]
	}

	leftValue := segtree.Query(a, (a+b)>>1, left, right, (k<<1)+1)
	rightValue := segtree.Query((a+b)>>1, b, left, right, (k<<1)+2)

	if leftValue <= rightValue {
		return leftValue
	}
	return rightValue
}

func main() {
	cin := NewScanner()

	N := cin.NextInt()
	Q := cin.NextInt()

	A := make([]int, N)
	for i := 0; i < N; i++ {
		A[i] = (1 << 31) - 1
	}

	segTree := NewSegTreeIntMin(A, N)

	for i := 0; i < Q; i++ {
		com := cin.NextInt()
		x := cin.NextInt()
		y := cin.NextInt()

		if com == 0 {
			segTree.Set(x, y)
		} else {
			value := segTree.Query(0, segTree.size, x, y+1, 0)
			fmt.Println(value)
		}
	}
}



Measured memory_bytes: 10336
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<set>

int main() {
	int n;
	cin >> n;
	vector<vector<P>>lis(n);
	rep(i, n) {
		int a;
		cin >> a;
		rep(j, a) {
			int x, y;
			cin >> x >> y;
			x--;
			lis[i].push_back(P(x, y));
		}
	}
	int ans(0);
	for (int bit = 0; bit < (1 << n); ++bit) {
		int c = 0;
		int can = 0;
		rep(i, n) {
			int cnt(0);
			int a = lis[i].size();
			if (!(bit >> i & 1))continue;
			can++;
			rep(j, lis[i].size()) {
				int x = lis[i][j].first; int y = lis[i][j].second;
				if ((bit >> x & 1) && y != 1)cnt++;
				if (!(bit >> x & 1) && y == 1)cnt++;
			}
			if (cnt >= 1)c = -1;
		}
		//cout << bit << can << endl;
		if (c != -1) {
			ans = max(can, ans);
		}
		
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 3600
#include<stdio.h>

int main()
{
	int a,b,c,d,e,f,g;

	scanf("%d",&a);
	b=a/60;
	c=b/60;
	d=a-b*60;
	e=b-c*60;
	printf("%d:%d:%d\n",c,e,d);
}


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

import fileinput
import math

def main():
    for line in fileinput.input():
        a, b, c = map(int, line.strip().split())

        count = 0
        for i in range(a, b+1):
            if(c % i == 0):
                count += 1

        print(count)

if __name__ == '__main__':
    main()

Measured memory_bytes: 6732
#include <bits/stdc++.h>
    using namespace std;
    int n, m;
    int main(){
    	ios_base::sync_with_stdio(0);
    	cin.tie();
    	cout.tie();
      cin >> n >> m;
    	if(n!=m){
    		cout << "No" << endl;
    		return 0;
    	}
    	cout << "Yes" << endl;
    }

Measured memory_bytes: 256
import sys

input = sys.stdin.readline


def main():
    H, W = [int(x) for x in input().split()]
    S = [input().strip() for _ in range(H)]

    A = [[""] * W for j in range(H)]

    for j in range(H):
        for i in range(W):
            if S[j][i] == "#":
                A[j][i] = '#'
            else:
                cnt = 0
                for dj, di in ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)):
                    if 0 <= j + dj <= H - 1 and 0 <= i + di <= W - 1:
                        if S[j + dj][i + di] == '#':
                            cnt += 1

                A[j][i] = str(cnt)

    for a in A:
        print("".join(a))








if __name__ == '__main__':
    main()



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

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

using namespace std;

using int64 = int64_t;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, n;
  cin >> h >> n;
  int mx = h + 10010;
  const int INF = (int)1e9;
  vector<int> dp(mx, INF);
  dp[0] = 0;
  while (n--) {
    int a, b;
    cin >> a >> b;
    for (int i = a; i < mx; i++) {
      dp[i] = min(dp[i], dp[i - a] + b);
    }
  }
  int ans = INF;
  for (int i = h; i < mx; i++) {
    ans = min(ans, dp[i]);
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3728
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0L;i--)
#define prep(i,n) for(int64_t i=1;i <= (int64_t)(n);i++)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  int64_t array_num = 1;
  fspcnt = 0;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}

int64_t calcmodcomb(int64_t n,int64_t r){
  return (((modfact.at(n)*modinvfact.at(r))%univMod)*modinvfact.at(n-r))%univMod;
}

int64_t calcmodpositive(int64_t n){
  return (n + ((abs(n)+univMod-1)/univMod)*univMod)%univMod;
}
  
    */


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

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

Measured memory_bytes: 256
#include<stdio.h>

int main(){

int a1, a2;
scanf("%d %d", &a1, &a2);
if ((a1==1&&a2==2)||(a1==2&&a2==1))printf("%d\n", 3);
else if ((a1==1&&a2==3)||(a1==3&&a2==1))printf("%d\n", 2);
else if ((a1==2&&a2==3)||(a1==3&&a2==2))printf("%d\n", 1);

	return 0;
}

Measured memory_bytes: 1736
#include<iostream>

using namespace std;

int main(){
  int a,b,c,tmp;
  cin >> a >> b >> c;
  if(a > b){
    tmp = a;
    a = b;
    b = tmp;
  }
  if(b > c){
    tmp = b;
    b = c;
    c = tmp;
  }
  if(a > b){
    tmp = a;
    a = b;
    b = tmp;
  }
  cout << a << " " << b << " " << c << endl;
  return 0;
}


Measured memory_bytes: 3096
import java.util.Scanner;

//Videotape
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true){
			int h = sc.nextInt();
			int m = sc.nextInt();
			int s = sc.nextInt();
			if(h==-1)break;
			int x = h*3600+m*60+s;
			int r = 7200 - x;
			int r3 = 7200*3-x*3;
			if(r<0)r=0;
			if(r3<0)r3=0;
			int h1 = r/3600;
			r%=3600;
			int m1 = r/60;
			r%=60;
			int h2 = r3/3600;
			r3%=3600;
			int m2 = r3/60;
			r3%=60;
			System.out.printf("%02d:%02d:%02d\n", h1, m1, r);
			System.out.printf("%02d:%02d:%02d\n", h2, m2, r3);
		}
	}
}

Measured memory_bytes: 12000
lines = []
while line = gets
    lines << line.chomp.split(' ').map(&:to_i)
end

N = lines[0][0]
K = lines[0][1]
Q = lines[0][2]

num_correct = []
for i in 1..N do
  num_correct[i-1] = 0
end
for i in 1..Q do
  num_correct[lines[i][0] - 1] += 1
end

win = []
for i in 1..N do
  if K - (Q - num_correct[i-1]) > 0 then
    win.push("Yes")
  else
    win.push("No")
  end
end
  
puts win

Measured memory_bytes: 16840
n = int(input())
a = list(map(int, input().split()))
b = [0] * n

for i in range(n, 0, -1):
    j = i
    tmp = 0
    while True:
        j += i
        if j > n:
            break
        tmp = tmp + b[j-1]
    b[i-1] = int(tmp % 2 != a[i-1])

m = sum(b)
print(m)
if m > -1:
    for i in range(n):
        if b[i]: print(i+1)


Measured memory_bytes: 63068
using System;
using System.Collections.Generic;
using System.Linq;

namespace contest_Csharp
{
    class Program
    {
        static long power(long a, long b, long modulo)
        {
            long result = 1;
            long buff = a;
            for (long i = 1; i <= b; i *= 2)
            {
                result = result * ((b / i % (2) == 1) ? buff : 1) % modulo;
                buff = (buff * buff) % modulo;
            }
            return result % modulo;
        }
        static void Main(string[] args)
        {
            var vals = Console.ReadLine().Split(' ')
                .Select(x => long.Parse(x)).ToList();
            long X = vals[0];
            long money = 100;
            long year = 0;
            while (money<X)
            {
                money = money + money / 100;
                year++;
            }
            
            Console.WriteLine(year);
        }



    }
    
    
}


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

int main() {
	int n, m = 0;
	int a[100010], b[100010];
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];
	for (int i = 0; i < n; i++) {
		m = a[i] - 1;
		b[m] = i + 1;
	}
	for (int i = 0; i < n; i++)cout << b[i] << ' ';
	cout << endl;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<long> a(n);
    for(int i=0;i<n;i++)cin >> a.at(i);
    long m=0;
    long M=0;
    m=*min_element(a.begin(),a.end());
    M=*max_element(a.begin(),a.end());
    cout << M-m << endl;
    return 0;
}

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

// const int mod = 1000000007;
const int mod = 998244353;
struct mint {
  ll x;  // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a; }
  mint operator-(const mint a) const { return mint(*this) -= a; }
  mint operator*(const mint a) const { return mint(*this) *= a; }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod - 2); }
  mint& operator/=(const mint a) { return *this *= a.inv(); }
  mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

int main() {
  int n;
  cin >> n;
  vector<int> d(n);
  rep(i, n) cin >> d[i];
  if (d[0] != 0) {
    cout << 0 << endl;
    return 0;
  }
  sort(d.begin(), d.end());
  vector<P> p(1, P(d[0], 0));
  rep(i, n) {
    if (p.back().first == d[i])
      p.back().second++;
    else
      p.emplace_back(d[i], 1);
  }

  // for (auto x : p) cerr << x.first << " " << x.second << endl;

  if (!(p[0].first == 0 && p[0].second == 1)) {
    cout << 0 << endl;
    return 0;
  }

  rep(i, p.size()) {
    if (p[i].first != i) {
      cout << 0 << endl;
      return 0;
    }
  }

  mint ans = 1;
  rep(i, p.size() - 1) rep(j, p[i + 1].second) ans *= p[i].second;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4524
N = int(input())
S = [input() for _ in range(N)]
li = [[0 for _ in range(26)]for _ in range(N)]
cand = [10**6]*26
ans = ''
for ind,i in enumerate(S):
    for x in i:
        li[ind][ord(x)-97]+=1
    for li_ind,j in enumerate(li[ind]):
        cand[li_ind] = min(j,cand[li_ind])

for ind,i in enumerate(cand):
    ans += chr(97+ind)*i
print(ans)


Measured memory_bytes: 3064
N = int(input())
a = list(map(int, input().split()))
ans = 0
count = 1
for i in range(1, len(a)):
	if a[i] == a[i-1]:
		count += 1
		if i == len(a) - 1 and count > 2:
			ans += int(count / 2)
		elif i == len(a) - 1 and count == 2:
			ans += 1
	elif a[i] != a[i-1] and count == 2:
		ans += 1
		count = 1
	elif a[i] != a[i-1] and count > 2:
		ans += int(count / 2)
		count = 1
print(ans)

Measured memory_bytes: 3064
N,M=map(int, input().split())
G=[[] for _ in range(N)]

for i in range(M):
  a,b=map(int, input().split())
  G[a-1].append((i,b-1))
  G[b-1].append((i,a-1))
  
L=[-1]*M
def dfs(start,goal,pre,num):
  if start==goal:
    return False
  done[start]=1
  for i,next_node in G[start]:
    if next_node==pre or i==num or done[next_node]==1:
      continue
    if not dfs(next_node,goal,start,num):
      return False
  return True

for a in range(N):
  for t in G[a]:
    i,b=t
    done=[0]*N
    if L[i]==-1:
      #print(dfs(a,b,-1,i))
      if dfs(a,b,-1,i):
        L[i]=1
      else:
        L[i]=0
print(sum(L))
#print(L)

Measured memory_bytes: 3064
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools
import itertools
import math
import sys

INF = float('inf')


def solve(N: int):
    return N//2+N % 2


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    print(f'{solve(N)}')


if __name__ == '__main__':
    main()


Measured memory_bytes: 75152
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
#define int long long 
signed main(void){
    int N,M;
    int Ans=0;
    bool c=0;
    int a[60],b[60];
    bool hen[10][10]={};
    vector<int> V={1,2,3,4,5,6,7,8};
    cin >> N >> M;
    REP(i,M){
        cin >> a[i] >> b[i];
        hen[a[i]][b[i]]=1;
        hen[b[i]][a[i]]=1;
    }
    
    do {
        //REP(i,N)cout << V[i] << " ";
        //cout << endl;
        c=0;
        REP(i,N-1){
            if(hen[V[i]][V[i+1]]==0 && hen[V[i+1]][V[i]]==0){
                c=1;
            }
        }
        if(c==0){Ans++;}
    } while (next_permutation(V.begin()+1, V.begin()+N));
    cout << Ans << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

n = int(input())
def prime_factorize(n):
    prime_fact = []
    while n%2 == 0:
        prime_fact.append(2)
        n//=2
    f = 3
    while f * f <= n:
        if n % f == 0:
            prime_fact.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        prime_fact.append(n)
    return prime_fact
a = prime_factorize(n)
print(str(n)+": ",end = "")
print(*a)


Measured memory_bytes: 6328
#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() {
    int n;
    cin >> n;
    vector<int> p(n), idx(n);
    rep(i, n) {
        cin >> p[i];
        p[i]--;
        idx[p[i]] = i;
    }
    set<int> st;
    ll ans = 0;
    for (int i = n-1; i >= 0; --i) {
        int id = idx[i];
        st.insert(id);
        int l1, l2, r1, r2;
        l1 = l2 = -1;
        r1 = r2 = n;
        auto it_l = st.find(id);
        auto it_r = st.find(id);
        if (it_l != st.begin()) {
            it_l--;
            l1 = *it_l;
            if (it_l != st.begin()) {
                it_l--;
                l2 = *it_l;
            }
        }
        it_r++;
        if (it_r != st.end()) {
            r1 = *it_r;
            it_r++;
            if (it_r != st.end()) {
                r2 = *it_r;
            }
        }
        if (ll(id-l1) * (r2-r1) + ll(l1-l2) * (r1-id) < 0) {
            cout << id << endl;
            cout << l1 << endl;
            cout << l2 << endl;
            cout << r1 << endl;
            cout << r2 << endl;
            cout << "OK" << endl;
        }
        ans += (ll(id-l1) * (r2-r1) + ll(l1-l2) * (r1-id)) * (i+1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5760
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rrep(i, n) for (ll i = n - 1; i >= 0; i--)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define RRep(i, r, n) for (ll i = n - 1; i <= r; i--)
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define int long long
#define pb push_back
#define mp make_pair
const int dx[] = {0, -1, 0, 1};
const int dy[] = {1, 0, -1, 0};
const int MOD = (1000000007);
//const int MOD = (998244353);
//const int INF = (1 << 30)-1;
const int INF = (1LL << 60) - 1;
const double EPS = (1 >> 30);

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

using Graph = vector<vector<pair<int, int>>>;
using Ki = vector<vector<int>>;
using Vi = vector<int>;

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

    int h, w;
    cin >> h >> w;
    char a[h][w];
    rep(i, h) rep(j, w) cin >> a[i][j]; // nyuuryoku

    int b[h][w];
    rep(i, h)
    {
        rep(j, w)
        {
            if (a[i][j] == '#')
            {
                b[i][j] = -1; // -1 = visited
            }
        }
    }

    queue<tuple<int, int, int>> Q; // x y cnt
    rep(i, h)
    {
        rep(j, w)
        {
            if (a[i][j] == '#')
            {
                Q.push(make_tuple(i, j, 0));
            }
        }
    }
    int cnt;
    while (!Q.empty())
    {
        int x = get<0>(Q.front());
        int y = get<1>(Q.front());
        cnt = get<2>(Q.front());
        Q.pop();
        rep(i, 4)
        {
            int cx = x + dx[i];
            int cy = y + dy[i];
            if (cx < 0 || cy < 0 || cx >= h || cy >= w || b[cx][cy] == -1)
            {
                continue;
            }
            b[cx][cy] = -1;
            Q.push(make_tuple(cx, cy, cnt + 1));
        }
    }
    cout << cnt << endl;
}

Measured memory_bytes: 33204
#include <iostream>
#include <cstdio>
using namespace std;
const int mod = 1e9 + 7;
int n, k, jc[4000010], ny[4000010];
int f[2010][2010];
inline int ksm (int a, int p) {
	int res = 1;
	while (p) {
		if (p & 1) res = 1ll * res * a % mod;
		a = 1ll * a * a % mod, p >>= 1;
	}
	return res;
}
inline int C (int n, int m) { return 1ll * jc[n] * ny[m] % mod * ny[n - m] % mod; }
int main () {
	scanf ("%d%d", &n, &k);
	if (k == 1) { printf ("1\n"); return 0; }
	jc[0] = 1; for (int i = 1; i <= 4000000; i++) jc[i] = 1ll * jc[i - 1] * i % mod;
	ny[4000000] = ksm (jc[4000000], mod - 2);
	for (int i = 4000000; i >= 1; i--) ny[i - 1] = 1ll * ny[i] * i % mod;
	f[0][0] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			(f[i + 1][j] += f[i][j]) %= mod;
			int x = n * k - j * k - i + j;
			(f[i][j + 1] += 1ll * f[i][j] * C (x - 1, k - 2) % mod) %= mod;
		}
		(f[i + 1][i] += f[i][i]) %= mod;
	}
	for (int i = 1; i <= n; i++) f[n][n] = 1ll * f[n][n] * i % mod;
	printf ("%d\n", f[n][n]);
	return 0;
}

Measured memory_bytes: 46464
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, p[3];
  string t;
  cin >> n >> k >> p[0] >> p[1] >> p[2] >> t;
  vector<int> s(n);
  rep(i, n) {
    if (t[i] == 'r')
      s[i] = 2;
    if (t[i] == 's')
      s[i] = 0;
    else if (t[i] == 'p')
      s[i] = 1;
  }
  ll ans = 0;
  rep(i, k) {
    ans += p[s[i]];
    int prev = s[i];
    for (int j = i+k; j < n; j += k) {
      if (s[j] == prev) {
        prev = -1;
        continue;
      }
      ans += p[s[j]];
      prev = s[j];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 848
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

H,W = map(int,readline().split())
H += 2; W += 2
grid = '#' * W
for _ in range(H-2):
    grid += '#' + readline().rstrip().decode() + '#'
grid += '#' * W


def bfs(start):
    inf = 10**9
    dist = [inf] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '#':
                continue
            if dist[w] > dv + 1:
                dist[w] = dv + 1
                q.append(w)
    return max(x for x in dist if x != inf)


print(max(bfs(v) for v in range(H*W) if grid[v] != '#'))


Measured memory_bytes: 3316
using System;

namespace abc156_a
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int k = int.Parse(input[0]);
            int r = int.Parse(input[1]);

            if(k >= 10)
            {
                Console.WriteLine(r);
            }
            else
            {
                Console.WriteLine(r + 100 * (10 - k));
            }
            Console.Read();
        }
    }
}


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

int main(){
  int N, alice = 0, bob = 0, answer;

  cin >> N;

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

  //配列の並び替え（大きい順）
  sort(a.begin(), a.end());
  reverse(a.begin(), a.end());

  for(int i = 0; i < N; i++) {
    if(i % 2 == 0) alice += a.at(i);
    else if(i % 2 == 1) bob += a.at(i);
  }

  answer = max(alice,bob) - min(alice,bob);

  cout << answer << endl;
}



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

using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    for(int i = 1;; i++){
        int m = (int)(i*0.08);
        int n = (int)(i*0.1);
        if(m == a && n == b){
            cout << i << endl;
            return 0;
        }
        if(m > a || n > b){
            cout << -1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  // 入力
  // すべて整数
  // Q円0.25Lサイズ、H円0.5Lサイズ、S円1Lサイズ、D円2Lサイズ
  long Q, H, S, D;
  cin >> Q >> H >> S >> D;
  long N;
  cin >> N;
  // NLに必要な組み合わせを計算
  // 最安値が必要
  // 各サイズでできるだけ多くカバーしたときに最も安いものを探す
  // まずそれぞれ何単位必要か
  long aQ, aH, aS, aD;
  aQ = N / 0.25;
  aH = N / 0.5;
  aS = N;
  aD = N / 2; 
  // 必要な単位に価格をかける 
  long pQ, pH, pS, pD;
  pQ = aQ * Q;
  pH = aH * H;
  pS = aS * S;
  pD = aD * D;
  // 最も安いのはどれ
  long leastCost = min({pQ, pH, pS, pD});
  // leastCost に応じて金額計算
  long P = leastCost;
  if (leastCost == pD && N % 2 == 1) {
    P += min({Q*4, H*2, S});
  }
  // 出力
  cout << P << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

#define N_MAX 10000005

using namespace std;

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

const ll mod = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1LL << 60;

int main()
{
    map<string,int> m;

    int n;
    cin >> n;

    for(int i = 0;i < n; i++){
        string s;
        cin >> s;
        m[s] += 1;
    }
    int cnt = 0;
    map<string,int>::iterator p; 
    for (p=m.begin(); p!=m.end(); p++) {
        cnt = max(cnt,p->second);
    }
    vector<string> v;
    for (p=m.begin(); p!=m.end(); p++) {
        if(p->second == cnt){
            v.push_back(p->first);
        }
    }

    sort(v.begin(),v.end());
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << endl;
    }
}

Measured memory_bytes: 26868
//Priyanshu Kumar : IIIT Allahabad
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define MAX 100005
#define MOD 1000000007
#define sz size()
#define ln length()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define si(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define pi(n) printf("%d",n)
#define pin(n) printf("%d\n",n);
#define pl(n) printf("%lld",n)
#define pln(n) printf("%lld\n",n);
inline ll gcd(ll x,ll y){return x%y==0?y:gcd(y,x%y);}
inline ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
inline ll powmod(ll a,ll b,ll mod) 
{
	ll res=1;
	a%=mod; 
	assert(b>=0); 
	for(;b;b>>=1)
	{
		if(b&1)res=res*a%mod;
		a=a*a%mod;
	}
	return res;
}
inline ll mulmod(ll a, ll b, ll c)
{
	if(!b)return 0;
	ll x = mulmod(a, b/2, c);
	if (b & 1)return (x+x+a)%c;
	return (x+x)%c;
}

bool check(string s)
{
    //cout<<s<<endl;
    int i=0,j=s.length()/2;
    while(j < s.length())
    {
        if(s[i] != s[j])
            return false;
        i++;
        j++;
    }
    return true;
}

int iseven(string s)
{
    int l = s.length();
    for(int i=l-2;i>=1;i--)
    {
        if(i%2 == 1)
        {
            if(check(s.substr(0,i+1)))
                return i+1;
        }
    }
    return 0;
}

int main()
{
    string s;
    cin>>s;
    cout<<iseven(s)<<endl;    
	return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

type work struct {
	a, b int
}

type byB []work

func (bb byB) Len() int           { return len(bb) }
func (bb byB) Swap(i, j int)      { bb[i], bb[j] = bb[j], bb[i] }
func (bb byB) Less(i, j int) bool { return bb[i].b < bb[j].b }

func main() {
	var n int
	fmt.Scan(&n)
	ws := make([]work, n)
	for i := range ws {
		fmt.Scan(&ws[i].a, &ws[i].b)
	}

	sort.Sort(byB(ws))
	now := 0
	for _, w := range ws {
		now += w.a
		if now > w.b {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 9600
#include <iostream>

int main()
{
  int a,b,c,d;
  std::cin >> a >> b >> c >> d;
  int left{a+b},right{c+d};
  std::cout << ((left>right) ? "Left" : (left<right) ? "Right" : "Balanced") << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <stdlib.h>
using namespace std;
int h,w,d;
int a;
pair<int,int> x[90001];
int sum[90001];
int q;
int l[100000],r[100000];
int main(){
    cin>>h>>w>>d;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a;
            x[a]=make_pair(i,j);
        }
    }
    for(int i=1+d;i<=h*w;i++){
        sum[i]=sum[i-d]+abs(x[i].first-x[i-d].first)+abs(x[i].second-x[i-d].second);
    }
    cin>>q;
    for(int i=0;i<q;i++){
        cin>>l[i]>>r[i];
    }for(int i=0;i<q;i++){
        cout<<sum[r[i]]-sum[l[i]]<<endl;
    }
    return 0;
}

Measured memory_bytes: 2944
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int H, W, i1, i2;
    
    
    while (1) {
    
        cin >> H >> W;
        if (H == 0 && W == 0) break;
        
        for (i1=0; i1<H; i1++) {
            
            for (i2=0; i2<W; i2++){
                cout << "#";
            }
            
            cout << endl;
        }
    cout << "\n";
    
    }
    
}

Measured memory_bytes: 3044
#include<iostream>

using namespace std;

typedef long long ll;

namespace comb {
	ll fact[500001];
	ll fact_inv[500001];
	const ll MOD = 1000000007;

	ll modpow(ll a, ll b) {
		ll base = 1, kakeru = a;
		while (b > 0) {
			if (b & 1)base *= kakeru, base %= MOD;
			kakeru *= kakeru, kakeru %= MOD;
			b >>= 1;
		}
		return base;
	}

	void setup() {
		fact[0] = 1, fact[1] = 1;
		for (int i = 2; i <= 500000; i++) {
			fact[i] = (fact[i - 1] * i) % MOD;
		}

		fact_inv[500000] = modpow(fact[500000], MOD - 2);

		for (int i = 499999; i >= 0; i--) {
			fact_inv[i] = fact_inv[i + 1] * (i + 1);
			fact_inv[i] %= MOD;
		}

	}

	ll combination(int a, int b) {
		if (a - b < 0)return 0;
		ll ret = fact[a];
		ret *= fact_inv[b], ret %= MOD;
		ret *= fact_inv[a - b], ret %= MOD;
		return ret;
	}

	ll permutation(int a, int b) {
		if (a - b < 0)return 0;
		ll ret = fact[a];
		ret *= fact_inv[a - b], ret %= MOD;
		return ret;
	}

	ll homogeneous(int a, int b) {
		return combination(a + b - 1, b);
	}

}

int main() {
	comb::setup();
	ll n, k;
	cin >> n >> k;

	ll ans = 0;
	for (ll i = k; i <= n + 1; i++) {
		ans += n * (n + 1) / 2 - (n - i) * (n - i + 1) / 2 - i * (i - 1) / 2 + 1;
		ans %= comb::MOD;
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;

const int N = 1e6 + 10;

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

inline bool compute(int pos)
{
  int x = a[pos];
  for (int i = 1; i * i <= x; i++)
  {
    if (x % i == 0)
    {
      if (cnt[i] || cnt[x / i]) return false;
    }
  }
  return true;
}

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

inline int read()
{
  int res = 0;
  char c = nc();
  while (!isdigit(c)) c = nc();
  while (isdigit(c))
  {
    res = res * 10 + c - '0';
    c = nc();
  }
  return res;
}

signed main()
{
  int ans = 0;
  n = read();
  for (int i = 1; i <= n; i++)
  {
    a[i] = read();
    cnt[a[i]]++;
  }
  for (int i = 1; i <= n; i++)
  {
    cnt[a[i]]--;
    if (compute(i)) ans++;
    cnt[a[i]]++;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 9420
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

string convert[128];

inline string to_binary_string(int x) {
	return bitset<6>(x).to_string();
}

inline void init() {
	for(int i = 0; i < 26; ++i) {
		convert['A' + i] = to_binary_string(i);
		convert['a' + i] = to_binary_string(i + 26);
	}

	for(int i = 0; i < 10; ++i) {
		convert['0' + i] = to_binary_string(52 + i);
	}

	convert[static_cast<int>('+')] = to_binary_string(62);
	convert[static_cast<int>('/')] = to_binary_string(63);
}

inline string decode(const string &s, int len) {
	string res = "";
	for(const int &c : s) {
		res += convert[c];
	}
	return res.substr(0, len);
}

inline vector<string> input_image(int w, int h) {
	vector<string> res;
	res.reserve(h);

	for(int i = 0; i < h; ++i) {
		string in;
		cin >> in;
		res.emplace_back(decode(move(in), w));
	}

	return res;
}

void rotate(vector<string> &mat) {
	const int n = mat.size();
	const auto tmp = mat;

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			const int tx = -i + n - 1;
			const int ty = j;
			mat[ty][tx] = tmp[i][j];
		}
	}

}

typedef unsigned long long hash_t;

unordered_map<hash_t, int> rolling_hash_2d(const vector<string> &s, int size) {
	constexpr hash_t base_w = 1000000007ull;
	constexpr hash_t base_h = 999999997ull;

	const int h = s.size();
	const int w = s[0].size();

	hash_t pow_hash_w = 1;
	hash_t pow_hash_h = 1;
	for(int i = 0; i < size; ++i) {
		pow_hash_w *= base_w;
		pow_hash_h *= base_h;
	}

	vector<vector<hash_t>> hash_w(h, vector<hash_t>(w));
	for(int i = 0; i < h; ++i) {
		hash_t tmp = 0ull;
		for(int j = 0; j < w; ++j) {
			tmp = tmp * base_w + s[i][j];
			if(j >= size) tmp -= pow_hash_w * s[i][j - size];
			hash_w[i][j] = tmp;
		}
	}

	unordered_map<hash_t, int> res;
	for(int j = size - 1; j < w; ++j) {
		hash_t tmp = 0ull;
		for(int i = 0; i < h; ++i) {
			tmp = tmp * base_h + hash_w[i][j];
			if(i >= size) tmp -= pow_hash_h * hash_w[i - size][j];
			if(i >= size - 1) ++res[tmp];
		}
	}

	return res;
}

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

	init();

	for(int w, h, p; cin >> w >> h >> p && w;) {
		const vector<string> image = input_image(w, h);
		auto hash_i = rolling_hash_2d(image, p);

		vector<string> pattern = input_image(p, p);

		int ans = 0;
		for(int rev = 0; rev < 2; ++rev) {
			for(int rot = 0; rot < 4; ++rot) {
				const hash_t target = rolling_hash_2d(pattern, p).cbegin()->first;
				ans += hash_i[target];
				hash_i[target] = 0;
				rotate(pattern);
			}

			for(auto &s : pattern) reverse(begin(s), end(s));
		}

		cout << ans << endl;
	}

	return EXIT_SUCCESS;
}

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

using namespace std;

int main() {
  int n, a, b, c, d;
  string s;
  cin >> n >> a >> b >> c >> d >> s;
  bool bad = false;
  for (int i = a; i < c; i++) {
    bad |= s[i] == '#' && s[i - 1] == '#';
  }
  for (int i = b; i < d; i++) {
    bad |= s[i] == '#' && s[i - 1] == '#';
  }
  if (bad) {
    cout << "No" << '\n';
    return 0;
  }
  if (c < d) {
    cout << "Yes" << '\n';
    return 0;
  }
  bool good = false;
  for (int i = b; i <= d; i++) {
    good |= s[i] == '.' && s[i - 1] == '.' && i > 2 && s[i - 2] == '.';
  }
  cout << (good ? "Yes" : "No") << '\n';
  return 0; // :)
}


Measured memory_bytes: 3724
import math

N, M = map(int, input().split())

MAX = M // N

def prime2(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


def prob(i, s, ans):
    if i == len(A):
        if s <= MAX:
            ans = max(ans, s)
        return ans
    n, m = A[i]
    for j in range(m+1):
        ans = prob(i+1, s*n**j, ans)
    return ans

A = list(prime2(M).items())
ans = prob(0, 1, 1)
print(ans)

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

using namespace std;

int main() {
  long long n, x;
  cin >> n >> x;
  long long ans = n;
  long long a = x, b = n - x;
  while (b) {
    long long q = a / b;
    ans += 2 * b * q - b * (a % b == 0);
    swap(a -= b * q, b);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
char str[10]={'a','b','c','d','e','f','g','h','i','j'};

//探索して、最後まで探索したら出力
void dfs(string instr, int maxnum) { 
  string tmp;
  for(int i=0;i<=maxnum;i++){
    tmp = instr+str[i];
    //最後まで探索した
    if(tmp.length()==n)cout << tmp << endl;
    else{
      //まだで桁が同じ
      if(i<maxnum)dfs(tmp, maxnum);
      //まだで桁が増える
      else dfs(tmp, maxnum+1);
    }
  }
} 

int main(){
  cin >> n;
  
  dfs("", 0);
  return 0;
}


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

int h, w, k = 0;
int a[1000][1000];
queue<pair<int, int>> Q;

int main()
{
	cin >> h >> w;

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char s;

			cin >> s;

			if (s == '.')
				a[i][j] = 0;
			else {
				a[i][j] = 1;
				Q.push(make_pair(i, j));
			}
		}
	}
	
	while (!Q.empty()) {
		int i1 = Q.front().first, j1 = Q.front().second;

		Q.pop();
		k = a[i1][j1];

		if (i1 > 0 && a[i1 - 1][j1] == 0) {
			a[i1 - 1][j1] = k + 1;
			Q.push(make_pair(i1 - 1, j1));
		}

		if (i1 < h - 1 && a[i1 + 1][j1] == 0) {
			a[i1 + 1][j1] = k + 1;
			Q.push(make_pair(i1 + 1, j1));
		}

		if (j1 > 0 && a[i1][j1 - 1] == 0) {
			a[i1][j1 - 1] = k + 1;
			Q.push(make_pair(i1, j1 - 1));
		}

		if (j1 < w - 1 && a[i1][j1 + 1] == 0) {
			a[i1][j1 + 1] = k + 1;
			Q.push(make_pair(i1, j1 + 1));
		}
	}

	cout << k - 1 << endl;

	return 0;
}

Measured memory_bytes: 12304
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string A;
  cin >> A;
  
  if(A == "Sunny") cout << "Cloudy" << endl;
  else if(A == "Cloudy") cout << "Rainy" << endl;
  else cout << "Sunny" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
//const ll MOD = ;
ll mod(ll A, ll M) {return (A % M + M) % M;}
const ll INF = 1LL << 60;
template<class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
ll divceil(ll A, ll B) {return (A + (B - 1)) / B;}
ll myctoi(char C) {return C - '0';}
char myitoc(ll N) {return '0' + N;}
#define FINALANS(A) {cout << (A) << '\n'; exit(0);}

int main()
{
  ll H, W;
  cin >> H >> W;
  vector<string> A(H);
  for (ll i = 0; i < H; i++)
  {
    cin >> A.at(i);
  }

  vector<string> R(H), B(H);
  for (ll i = 0; i < H; i++)
  {
    if (i % 2 == 0)
    {
      R.at(i) = string(W - 1, '#') + '.';
      B.at(i) = string(W - 1, '.') + '#';
    }
    else
    {
      R.at(i) = '#' + string(W - 1, '.');
      B.at(i) = '.' + string(W - 1, '#');
    }
  }
  
  for (ll i = 0; i < H; i++)
  {
    for (ll j = 0; j < W; j++)
    {
      if (A.at(i).at(j) == '#')
      {
        R.at(i).at(j) = '#';
        B.at(i).at(j) = '#';
      }
    }
  }
  
  for (ll i = 0; i < H; i++)
  {
    cout << R.at(i) << endl;
  }
  cout << endl;
  for (ll i = 0; i < H; i++)
  {
    cout << B.at(i) << endl;
  }

  return 0;

  cerr << endl;
  for (ll i = 0; i < H; i++)
  {
    for (ll j = 0; j < W; j++)
    {
      if (R.at(i).at(j) == '#' && B.at(i).at(j) == '#')
        cerr << '#';
      else
        cerr << '.';
    }
    cerr << endl;
  }
}

Measured memory_bytes: 2048
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

const int N = (int)3e5;

ll mpow(ll a, ll b){
	if(b==0) return 1;
	else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
	else return mpow(a,b-1) * a % MOD;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
	if(kaijo_memo.size() > n) return kaijo_memo[n];
	if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
	while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
	return kaijo_memo[n];
}
ll nCr(ll n, ll r){
	if(n < r || r < 0) return 0;
	ll ret = 1;
	ret *= kaijo(n); ret %= MOD;
	ret *= mpow(kaijo(r), MOD-2); ret %= MOD;
	ret *= mpow(kaijo(n-r), MOD-2); ret %= MOD;
	return ret;
}

int main(void){
	ll ans = 0;
	ll n;cin>>n;
	vector<vector<ll>> A;
	rep(i,n){
		A.push_back(vector<ll>());
		rep(j,n){
			ll a;cin>>a;
			A[i].push_back(a);
		}
	}
	rep(from, n){
		rep(to, n){
			if(from >= to) continue;
			bool equal = false;
			rep(k, n){
				if(from == k || to == k) continue;
				if(A[from][to] == A[from][k] + A[k][to]){
					equal = true;
				}
				if(A[from][to] > A[from][k] + A[k][to]){
					cout<<-1<<endl;
					return 0;
				}
			}
			if(!equal){
				ans += A[from][to];
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1408
#include <vector>
#include <list>
#include <map>
#include <set>
#include "queue"
#include <deque>
#include <stack>
#include <numeric>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <complex>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include "fstream"
using namespace std;
#define PI acos(-1)
#define MOD (ll)1000000007
#define pii pair<long long ,long long >
#define ll  long long int
#define loop(i,n) for(ll i=0;i<n;i++)
#define loop2(i,n) for(ll i = 1;i<=n;i+=1)
#define pb push_back
#define mp make_pair
#define EPS 1e-8
void display(vector<ll> v1){loop(i,v1.size()){cout<<v1[i]<<" ";}cout<<endl;}
ll dx[8] = {0,1,0,-1,1,1,-1,-1};
ll dy[8] = {1,0,-1,0,1,-1,1,-1};

//Jai Shree Krishna
//:) :) :( :( :( :( :( :( :) :( :)
//Purple Dreams ??? 
//Shit ;More Shit and Hell lot of Shit and Still Shit 

vector<vector<ll> >g;

const int MAXN = (ll)1e6+100;
ll a[MAXN];
bool ok =  false;


ll DFS(ll v,ll par)
{
    ll sum = 0 ;
    ll max1 = 0 ;
    bool wasChild = false;
    loop(i,g[v].size())
    {
        if(ok==false)
            return 0;
        ll to = g[v][i];
        if(to==par)
            continue;
        ll val = DFS(to, v);
        sum+=val;
        max1 = max(max1,val);
        wasChild = true;
    }
    if(ok==false)
        return 0;
    if(wasChild==false)
        return a[v];
    ll maxC = 0  ;
    if(max1+max1<=sum)
    {
        maxC = sum/2;
    }
    else{
        maxC  = sum-max1;
    }
    ll c = sum-a[v];
    if((c<0)||(c>maxC))
    {
        ok = false;
        return 0;
    }
    return sum-c-c;
}

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

    ll n;
    cin>>n;
    loop(i,n)
    {
        cin>>a[i];
    }
    g.resize(n);
    loop(i,n-1)
    {
        ll v1,v2;
        cin>>v1>>v2;
        v1-=1;
        v2-=1;
        g[v1].push_back(v2);
        g[v2].push_back(v1);
    }
    if(n==2)
    {
        if(a[0]==a[1]){
    cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
        return 0;
    }
    ll root = 0 ;
    loop(i,n)
    {
        if(g[i].size()>1)
        {
            root = i;
        }
    }
    ok = true;
    ll val = DFS(root, -1);
    if((ok)&&(val==0))
    {
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
    
    return 0;
}


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

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; }

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

void vprint(vector<ll> A){
    ll L = A.size();
    FOR(i, 0, L){
        if(i) cout << ' ';
        cout << A[i];
    }
    cout << endl;
}

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

    // input
    ll N, D;
    cin >> N >> D;

    ll a = 2*D+1;

    if(N%a==0){
        p(N/a);
    }else{
        p(N/a + 1);
    }
    return 0;
}

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

int main(){
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++){
        cin >> a.at(i);
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    int Alice_point = 0;
    int Bob_point = 0;
    for (int i = 0; i < N; i++){
        if (i % 2 == 0){
            Alice_point += a.at(i);
        }
        else{
            Bob_point += a.at(i);
        }
    }
    cout << Alice_point - Bob_point << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

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

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

string search(string s, string p)
{
    for (int i = 0, j; i < s.size(); i++) {
        for (j = 0; j < p.size() && s[(i + j) % s.size()] == p[j]; j++)
            ;
        if (j >= p.size())
            return "Yes";
    }
    return "No";
}

int main()
{
    string s, p;

    getline(cin, s);
    getline(cin, p);

    cout << search(s, p) << endl;

    return 0;
}


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

int a[200004],rem[200004];
int min(int a, int b)
{
	if(a<b)
		return a;
	return b;
}

int minn(int x)
{
	if(x==3)
		return fabs(a[2]-a[0]);
	else if(x==2)
		return fabs(a[1]-a[0]);

	else if(rem[x]!=-1)
		return rem[x];

		rem[x]=min(minn(x-1)+fabs(a[x-1]-a[x-2]),minn(x-2)+fabs(a[x-1]-a[x-3]));
		//printf("\nfor %d, rem[x] is %d ",x,rem[x]);
	return rem[x];
}

int main()
{
	int n;
	scanf("%d",&n);;
	for(int i=0; i<n; i++)
		scanf("%d",&a[i]);;

	for(int i=0; i<200000; i++)
		rem[i]=-1;

	printf("%d",minn(n));
//	printf("%d %d",rem[3], rem[2]);

}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;

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

const ll mod=1000000007;

ll countBits(ll in){
  int res=0;
  for(;in>0;in>>=1){
    if((in&0x01)!=0){
      res++;
    }
  }
  return res;
}

template<typename T>
void show2dVector(vector<vector<T>>& v){
  for(int i=0;i<v.size();i++){
    int m=v[i].size();
    cout<<i<<" : ";
    for(int j=0;i<m;i++){
      cout<<v[i][j]<<" ";
    }
    cout<<endl;
  }
}

void bfs(const vector<vector<int>>&g, int v, vector<bool>& seen){
  seen[v]=true;
  cout<<v<<" ";
  for(auto next: g[v]){
    if(seen[next]){
      continue;
    }
    bfs(g,next,seen);
  }
}

bool dfs(vector<vector<int>> &g,int start,int goal,vector<bool>&seen){
  bool res=false;
  seen[start]=true;
  if(start==goal){
    return true;
  }
  for(auto next: g[start]){
    if(seen[next]){
      continue;
    }
    res=dfs(g,next,goal,seen);
    if(res){
      break;
    }
  }
  return res;
}

ll gcd(ll a,ll b) {
  return b? gcd(b,a%b): a;  
}
ll lcm(ll a,ll b) {
  return a*b/gcd(a,b);
}
bool isLowerCase(char c){
  return (c>='a'&&c<='z');
}

ll powm(ll a,ll n, ll m){
  ll ret=1;
  while(n>0){
    if(n%2==1){
      ret=(ret*a)%m;
    }
    n>>=1;
    a=(a*a)%m;
  }
  return ret;
}

const string yesno(bool ans){
  return (ans?"Yes":"No");
}
int main() {
  int n;cin>>n;
  map<string,int> a;
  a["AC"]=0;
  a["TLE"]=0;
  a["WA"]=0;
  a["RE"]=0;
  for(int i=0;i<n;i++){
    string val;cin>>val;
    a[val]++;
  }
  cout<<"AC x "<<a["AC"]<<endl;
  cout<<"WA x "<<a["WA"]<<endl;
  cout<<"TLE x "<<a["TLE"]<<endl;
  cout<<"RE x "<<a["RE"]<<endl;
  return 0;
}


Measured memory_bytes: 3616