akhauriyash/Code-Regression huggingface dataset:
#include    <iostream>
 
using namespace std;
 
bool F[1000003] = { false };
int DP[80000] = { 0 };
void prepa_Prime();
int count_Prime(int);
 
int main() {
    int n;

    prepa_Prime();
    while (cin >> n) {
        cout << count_Prime(n) << endl;;
    }
    return 0;
}
 
void prepa_Prime() {
    int i, c = 2;

    F[0] = F[1] = true;
    DP[0] = 1;

    DP[1] = 2;
    for (i = 4; i <= 1000003; i += 2) { F[i] = true; }
    
    for (i = 3; i <= 1000003; i += 2) {
        if (F[i] == false) {
            DP[c++] = i;
            for (int j = i * 2; j <= 1000003; j += i) {
                F[j] = true;
            }
        }
    }
}

int count_Prime(int n) {
    int i = 0;
    for (i; DP[i + 1] <= n; i++) {}
    return i;
}


Measured memory_bytes: 4368
#include <iostream>
#include <vector>
#include <set>
#include <map>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

using namespace std;

int main(int argc, const char * argv[]) {
    int N, C;
    cin >> N >> C;
    int D[30][30];
    REP(i, C) {
        REP(j, C) {
            int d;
            cin >> d;
            D[i][j] = d;
        }
    }
    int dd[3][30] = {0};
    REP(i, N) {
        REP(j, N) {
            int d;
            cin >> d;

            int cls = (i+1+j+1)%3;
            REP(k, C) dd[cls][k] += D[d-1][k];
        }
    }
    int ans = 1000*500*500;
    REP(i, C) REP(j, C) REP(k, C) {
        if (i != j && j != k && k != i) {
            ans = min(ans, dd[0][i]+dd[1][j]+dd[2][k]);
        }
    }

    cout << ans << endl;
    
    
}


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

typedef long long ll;

using namespace std;

int n;
ll m;
ll tez[110];
ll val[110];
ll memo[110][200000];

ll rek(int i, ll w){

    if (memo[i][w] != -1)return memo[i][w];
    if (i >= n)return 0;
    if (w > m)return 0;
    ll a = rek(i + 1, w + tez[i]) + val[i];
    if (w + tez[i] > m)a = 0;
    ll b = rek(i + 1, w);

    memo[i][w] = max(a,b);

    return max(a,b);
}

int main (){

    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> tez[i] >> val[i];

    }

    memset(memo, -1, sizeof memo);

    cout << rek(0, 0) << "\n";

    return 0;
}


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


using ll = long long;
using Pll = pair<ll, ll>;
vector<Pll> g[100005], h[100005];
ll n, m, s, t, u, v, a, b, dg[100005], dh[100005], ans[100005];

constexpr ll INF = (1LL << 60);

priority_queue<Pll, vector<Pll>, greater<Pll>> Q;

int main() {
  cin >> n >> m >> s >> t;
  s--, t--;
  for (int i = 0; i < m; ++i) {
    cin >> u >> v >> a >> b;
    u--, v--;
    g[u].push_back({v, a});
    g[v].push_back({u, a});
    h[u].push_back({v, b});
    h[v].push_back({u, b});
  }
  for (int i = 0; i < n; ++i) dg[i] = INF, dh[i] = INF;
  dg[s] = 0; Q.push({0, s});

  while (!Q.empty()) {
    int p = Q.top().second; Q.pop();
    for (const auto &f : g[p]) {
      ll cost = f.second, to = f.first;
      if (dg[to] > dg[p] + cost) {
        dg[to] = dg[p] + cost;
        Q.push({dg[to], to});
      }
    }
  }

  dh[t] = 0; Q.push({0, t});
  while (!Q.empty()) {
    int p = Q.top().second; Q.pop();
    for (const auto &f : h[p]) {
      ll cost = f.second, to = f.first;
      if (dh[to] > dh[p] + cost) {
        dh[to] = dh[p] + cost;
        Q.push({dh[to], to});
      }
    }
  }

  ans[n-1] = dg[n-1] + dh[n-1];
  for (int i = n-1; i > 0; --i) {
    ans[i-1] = min(ans[i], dg[i-1] + dh[i-1]);
  }
  for (int i = 0; i < n; ++i) {
    cout << 1000000000000000LL - ans[i] << endl;
  }
  return 0;
}


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

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

  if (abs(a-c) <= d || (abs(a-b) <= d && abs(b-c) <= d)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 888
#include<cstdio>
int main() {
	int a, b, c, tmp, triangle = 0, right = 0, acute = 0, obtuse = 0;
	while (true) {
		scanf("%d%d%d", &a, &b, &c);
		if (a > b) { tmp = b; b = a; a = tmp; }
		if (b > c) { tmp = c; c = b; b = tmp; }
		if (a > b) { tmp = b; b = a; a = tmp; }
		if (a + b <= c) {
			printf("%d %d %d %d\n", triangle, right, acute, obtuse);
			break;
		}
		else if (a*a + b*b > c*c) acute++;
		else if (a*a + b*b == c*c) right++;
		else obtuse++;
		triangle++;
	}
	return 0;
}


Measured memory_bytes: 2724
import os
import heapq
import sys,threading
import math
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10**5)
from io import BytesIO, IOBase
def gcd(a,b):
    if b==0:

        return a
    else:
        return gcd(b,a%b)
def power(x, p,m):
    res = 1
    while p:
        if p & 1:
            res = (res * x) % m
        x = (x * x) % m
        p >>= 1
    return res
def inar():
    return [int(k) for k in input().split()]

def lcm(num1,num2):
    return (num1*num2)//gcd(num1,num2)

def main():
    a,b=inar()
    print(lcm(a,b))




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()
    #threadin.Thread(target=main).start()


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

using ll = unsigned long long int;

int main(){
	ll a,b,k;
	cin >> k >> a >> b;
	if(b <= (a + 2)){
		cout << k + 1 << endl;
		return 0;
	}
	ll val = ((k-a) / 2 * (b-a) + 1);
	ll sum = 0;
	if(!((k-a) % 2)){
		val += a;
	}else{
		val += b-1;
	}
	cout << val << endl;
	
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
char a[1010][1010];
ll dp[1010][1010];
ll x,y;
ll m=1e9+7;
ll dp1(int i,int j)
{
    if(i==x&&j==y)
        return 1;
    if(dp[i][j]!=-1)
        return dp[i][j];
    ll x1=0,x2=0;
    if(a[i][j+1]=='.')
        x1=dp1(i,j+1)%m;
    if(a[i+1][j]=='.')
        x2=dp1(i+1,j)%m;
    return dp[i][j]=(x1+x2)%m;
}
int main()
{
    ios_base::sync_with_stdio(0);
    memset(dp,-1,sizeof(dp));
    cin>>x>>y;
    for(int i = 1 ;i<=x; i++)
    {
        for(int j =1;j<=y;j++)
        {
            cin>>a[i][j];
        }
    }
    cout<<dp1(1,1);
    return 0;
}


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

vector<vector<int>> g;

bool get_path(int cur, int pre, int goal, vector<int> &path){
    static map<pair<int,int>, int> path_id;
    if (cur == goal) return true;
    for(int to : g[cur]){
        if(to == pre) continue;
        pair<int,int> p = {min(cur, to), max(cur, to)};
        int id = path_id.count(p) ? path_id[p] : path_id.size();
        path_id[p] = id;
        path.push_back(id);
        if (get_path(to, cur, goal, path)) {
            return true;
        } else {
            path.pop_back();
        }
    }
    return false;
}

int main(void){
    int n;
    cin >> n;
    g.resize(n);
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int m;
    cin >> m;
    vector<vector<int>> paths(m);
    rep(i,m){
        int u, v;
        cin >> u >> v;
        u--, v--;
        get_path(u, -1, v, paths[i]);
    }
    long long res = 0;
    rep(mask, 1<<m){
        vector<bool> on(n);
        rep(i,m){
            if (bit(i) & mask) {
                for(int e : paths[i]) {
                    on[e] = true;
                }
            }
        }
        int cnt = 0;
        rep(i,n) if(on[i]) cnt++;
        res += (((int)__builtin_popcount(mask) & 1) ? -1 : +1) * (1LL<<((n-1)-cnt));
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 384
def main():
    n = int(input())
    L = sorted([int(x) for x in input().split()])
    cnt = 0
    for a in range(n-2):
        for b in range(a+1, n-1):
            for c in range(b+1, n):
                if (L[a] != L[b]) and (L[b] != L[c]) and (L[c] != L[a]) and \
                    L[a] + L[b] > L[c]:
                    cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9208
def f(a):

	return a**0.5==int(a**0.5)#print(f(4))

n,d=map(int, input().split())

def g(a,b):

	ret=0

	for i in range(0,d):

		ret+=(a[i]-b[i])**2

	return ret

	

	

ans=0

a=[]

for i in range(0,n):

	a.append(list(map(int,input().split())))

	for j in range(0,i):

		if f(g(a[i],a[j])):

			ans+=1

print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		long K = sc.nextInt();
		int ub = 0;
		for (int i = 0; i < N; i++) {
			ub = Math.max(ub, a[i] = sc.nextInt());
		}
		int lb = 0;
		while (ub - lb > 1) {
			int m = (ub + lb) / 2;
			long Q = 0;
			for (int i = 0; i < N; i++) {
				Q += (a[i] - 1) / m;
			}
			if (Q <= K) {
				ub = m;
			} else {
				lb = m;
			}
		}
		System.out.println(ub);
	}
}


Measured memory_bytes: 59964
import java.util.*;
class Main{
	static Scanner s = new Scanner(System.in);
	public static void main(String[] args) {
		BitSet b = new BitSet(31);
		b.set(1, 31);
		for(int i=0;i<28;i++)
			b.clear(s.nextInt());
		System.out.println(b.toString().replaceAll("[^0-9,]", "").replace(',', '\n'));
	}
}

Measured memory_bytes: 26248
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
T,A = MI()
H = [abs(T-i*0.006-A) for i in LI()]
m = min(H)
print(H.index(m)+1)



Measured memory_bytes: 62716
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)

int const N = 100000;
map<int, int> mp[N + 1];
int pa[N + 1];

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	f(i, 1, n + 1)pa[i] = i;
	f(i, 1, n + 1)mp[i][i] = 0;
	while (m--){
		int l, r, d;
		scanf("%d%d%d", &l, &r, &d);
		if (pa[l] == pa[r]) { if (mp[pa[l]][r] - mp[pa[l]][l] != d) { printf("No\n"); return 0; } }
		else {
			int pl = pa[l], pr = pa[r];
			if (mp[pl].size() > mp[pr].size())swap(pl, pr), swap(l, r), d = -d;
			int z = mp[pr][r] - d - mp[pl][l];
			for (map<int, int>::iterator it = mp[pl].begin(); it != mp[pl].end(); mp[pl].erase(it++)){
				pa[it->first] = pr;
				mp[pr][it->first] = it->second + z;
			}
		}
	}
	printf("Yes\n");
}

Measured memory_bytes: 9984
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int n;
	cin>>n;
	cout<<a[n-1]<<endl;
	return 0;
}

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

dp = [10**9]*N
dp[0] = 0

for i in range(1,N):
  for j in range(K+1):
    if i-j >= 0:
      dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
  
print(dp[N-1])

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

int main(){
    unsigned long long a[3],b,c;
    cin >> a[0] >> a[1] >> a[2];
    sort(a,a+3);    
    if(a[0] % 2 == 0 || a[1] % 2 == 0 || a[2] % 2 == 0){
        cout << 0 << endl;
    }else{
        cout << a[0]*a[1] << endl;
    }
    return 0;
}


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

int main(){
  string S;
  cin >> S;
  int N;
  N = S.size();
  int res = 0;
  int check = 0;
  for(int i = 0; i < N; i++){
    if(S.at(i) == S.at(N-1-i)){
      check = check + 0;
    }
    else{
      check = check + 1;
    }
  }
  if(check == 0){
    res = res + 1;
  }
  int M = (N-1)/2;
  int chec = 0;
  for(int i = 0; i < M; i++){
    if(S.at(i) == S.at(M-1-i)){
      chec = chec+ 0;
    }
    else{
      chec = chec + 1;
    }
  }
  if(chec == 0){
    res = res + 1;
  }
  int L = (N+3)/2;
  int che = 0;
  for(int i = 0; i < N-L; i++){
    if(S.at(L+i-1) == S.at(N-1-i)){
      che = che+ 0;
    }
    else{
      che = che + 1;
    }
  }
  if(che == 0){
    res = res + 1;
  }
  if(res == 3){
    cout << "Yes";
  }
  if(res < 3){
    cout << "No";
  }
}


Measured memory_bytes: 256
//25
#include<iostream>
#include<algorithm>

using namespace std;

int m,n;
int g[10][10];
int cx,cy;
bool ra[10][10];

int dfs(int x,int y,int r){
  if(r==0){
    return x==cx||y==cy;
  }else{
    int a=0;
    for(int i=0;i<4;i++){
      int d[]={0,1,0,-1,0};
      int nx=x,ny=y;
      for(;;){
	nx+=d[i];
	ny+=d[i+1];
	if(nx<0||m<=nx||ny<0||n<=ny)break;
	if(g[ny][nx]==1){
	  g[ny][nx]=0;
	  a+=dfs(nx,ny,r-1);
	  g[ny][nx]=1;
	  break;
	}
      }
    }
    return a;
  }
}

int main(){
  while(cin>>m>>n,m|n){
    int nh=0;
    int x,y;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
	cin>>g[i][j];
	nh+=g[i][j]==1;
	if(g[i][j]==2){
	  cx=x=j;
	  cy=y=i;
	}
      }
    }
    fill(ra[0],ra[n],false);
    cout<<dfs(x,y,nh)<<endl;
  }
  return 0;
}

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

using namespace std;

#define ft first
#define sd second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define boost ios_base::sync_with_stdio(false), cin.tie(NULL)
#define inp freopen("code.in", "r+", stdin)
#define out freopen("code.out", "w+", stdout)
#define debug(os, var)                                     \
    (os) << "DBG: " << __FILE__ << "(" << __LINE__ << ") " \
         << #var << " = [" << (var) << "]" << endl

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef long long int ll;

int main()
{
    boost;
    //inp;
    int n, x, y;
    cin >> n;
    int cnt, ans;
    cnt = ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        if (x == y)
            ans = max(++cnt, ans);
        else
            cnt = 0;
    }
    if (ans >= 3)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3648
import scala.io.StdIn

object Main extends App {
  val n = StdIn.readLine().toInt
  val a = StdIn.readLine().split(' ').map(_.toLong)
  
  val b = a.groupBy(f => f)
  println(b.foldLeft(0L)( (acc, e) => acc + (if(e._2.length >= e._1) e._2.length - e._1 else e._2.length)))
  
}

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

X = list(range(1,N+1))

d = dict(zip(A, X))
d_sort = dict(sorted(d.items(), key=lambda x: x[1]))

ans_list = list(d_sort.values())
B = map(str, ans_list)
ans = ' '.join(B)
print(ans)


Measured memory_bytes: 36588
#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[i];
  }
  
  int ans = 0;
  int b;
  for(int i=0; i<n; i++){
    cin >> b;
    ans += b;
  }
  vector<int> c(n);
  for(int i=0; i<n-1; i++){
    cin >> c[i];
  }
  for(int i=0; i<n-1; i++){
    if(a[i]+1 == a[i+1] && a[i]-1<n-1)ans += c[a[i]-1];
  }
  
  cout << ans<<endl;
  return 0;
}

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

#define int long long
#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define reps(i, n) for (int (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for (int (i) = (n) - 1; (i) >= 0; (i)--)
#define rreps(i, n) for (int (i) = (n); (i) > 0; (i)--)
typedef vector<int> vint;
typedef pair<int, int> pint;
constexpr double PI = 3.1415926535897932384626433832795028;
constexpr int DY[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int DX[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
template<typename T, typename U> inline bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> inline bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
struct Init {
    Init() {
        cout << fixed << setprecision(20);
        cerr << fixed << setprecision(20);
    };
} init;

int N, K;
string S;
signed main() {
    cin >> N >> K >> S;
    vint a;
    if (S[0] == '0') { a.push_back(0); }
    S = '2' + S;
    reps(i, S.length() - 1) {
        if (S[i] != S[i - 1]) { a.push_back(1); }
        else { a[a.size() - 1]++; }
    }
    if (S[S.length() - 1] == '0') { a.push_back(0); }
    vint imos;
    imos.push_back(0);
    reps(i, a.size()) { imos.push_back(imos[i - 1] + a[i - 1]); }
    K = min(K, (int) a.size() / 2);
    int ans = 0;
    for (int i = K * 2 + 1; i < imos.size(); i += 2) { chmax(ans, imos[i] - imos[i - (K * 2 + 1)]); }
    cout << ans << endl;
}

Measured memory_bytes: 2672
#include <iostream>

using namespace std;

int main() {
	int n; cin >> n;
	int ans = 100000;
	int tmp;
	for (int i=0; i<n; i++) {
		ans *= 1.05;
		tmp = ans / 1000 * 1000;
		if (tmp != ans) ans = tmp + 1000;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int main(void){
  string s;
  cin >> s;
  if(s.at(2) == s.at(3) && s.at(4) == s.at(5)){
    cout << "Yes";
  } else {
    cout << "No";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;

int main(){
  int a;cin>>a;
  string s;cin>>s;
  if(a>=3200){
    cout<<s<<endl;
  }else{
    cout<<"red"<<endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>

int isPrime(int u){
  int i;
  if (u<2) return 0;
  else if (u==2) return 1;
  if (u%2==0) return 0;
  for (i=3;i*i<=u;i+=2){
    if (u%i==0) return 0;
  }
  return 1;
}

int main(){
  int n, u, i;
  int C=0;
  scanf("%d", &n);
  for (i=0;i<n;i++){
    scanf("%d", &u);
    if (isPrime(u))C++;
  }
  printf("%d\n", C);
  
  return 0;
}



Measured memory_bytes: 2032
N, M = map(int,input().split())
xyz = []

for _ in range(N):
    x,y,z = map(int,input().split())
    xyz.append((x,y,z))

ans = 0

sign = [1,-1]    
for i in range(1<<3):
    dec = [0 for _ in range(N)]
    for j in range(3):
        jbit = ((i>>j)&1)
        
        for k in range(N):
            dec[k] += sign[jbit] * xyz[k][j]
        
    dec.sort(reverse=True)
    ans = max(ans,sum(dec[:M]))

print(ans)

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

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

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

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

	int h,w; cin >> h >> w;

	char field[1005][1005];

	for (int i = 0;i < h;i++){
		for (int j = 0;j < w;j++){
			cin >> field[i][j];
		}
	}

	int cnt[1005][1005]; memset(cnt,0,sizeof(cnt));
	vector<P> lis[2];

	for (int i = 0;i < h;i++){
		for (int j = 0;j < w;j++){
			if(field[i][j] >= '1' && field[i][j] <= '9'){
				for (int k = 0;k < 8;k++){
					int ni = i+dx[k], nj = j+dy[k];
					if(field[ni][nj] == '.') cnt[i][j]++;
				}
				if(cnt[i][j] >= field[i][j]-'0') lis[0].push_back(P(i,j));
			}
		}
	}

	int crt = 0, next = 1;
	int ans = 0;

	while(lis[crt].size()){
		ans++;
		map<P,bool> mp;
		for (int i = 0;i < lis[crt].size();i++){
			int ii = lis[crt][i].first, jj = lis[crt][i].second;
			field[ii][jj] = '.';
			cnt[ii][jj] = 0;
		}
		for (int i = 0;i < lis[crt].size();i++){
			int ii = lis[crt][i].first, jj = lis[crt][i].second;
			for (int j = 0;j < 8;j++){
				int ni = ii+dx[j], nj = jj+dy[j];
				if(field[ni][nj] >= '1' && field[ni][nj] <= '9'){
					cnt[ni][nj]++;
					if(cnt[ni][nj] >= field[ni][nj]-'0'){
						   	if(!mp[P(ni,nj)]){
								lis[next].push_back(P(ni,nj));
								mp[P(ni,nj)] = true;
							}
					}
				}
			}
		}
		lis[crt] = vector<P>(0);
		swap(crt,next);	
	}

	cout << ans << endl;

	return 0;

}



Measured memory_bytes: 8092
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
if k>n:
    k=n-1
dp=[int(0) for _ in range(n)]
dp[1]=abs(a[0]-a[1])
 
for i in range(2,n):
  ind = max(0,i-k)
  dp[i]=min([dp[v]+abs(a[i]-a[v]) for v in range(ind,i)])
  #dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]))
#print(dp[n-1])
print(dp[-1])

Measured memory_bytes: 20568
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    nums = [0]
    for _ in range(n):
        nums.append(I())
    
    dp = [[False]*(10001) for _ in range(n+1)]
    dp[0][0] = True
    ans = 0
    for i in range(1,n+1):
        num = nums[i]
        for j in range(10000):
            if num > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-num]
            if dp[i][j] and j%10 != 0:
                ans = max(ans,j)
    print(ans)


main()            


Measured memory_bytes: 75132
import java.util.*;

class Main{
    public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		int ia = sc.nextInt();
		int ib = sc.nextInt();
		int ic = sc.nextInt();
		int id = sc.nextInt();
		if((ia + ib) > (ic + id)){
			System.out.println("Left");
		}
		else if((ia + ib) == (ic + id)){
			System.out.println("Balanced");
		}
		else{
			System.out.println("Right");
		}
    }
}


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

#define LL long long

const int MAX_N = (2 * 1e5) + 5;

int N, A[MAX_N];
LL dp[MAX_N][4];
bool dp_solved[MAX_N][4];
LL answer;

LL solve(int index, int skips) {
  if(index < 0) return 0;
  if(index == 0) return A[0];

  if(dp_solved[index][skips]) return dp[index][skips];

  if(skips == 0) dp[index][skips] = A[index] + solve(index - 2, 0);
  if(skips == 1) dp[index][skips] = A[index] + max(solve(index - 2, 1), solve(index - 3, 0));
  if(skips == 2) dp[index][skips] = A[index] + max(solve(index - 2, 2), max(solve(index - 3, 1), solve(index - 4, 0)));

  dp_solved[index][skips] = true;
  return dp[index][skips];
}

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

  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];

  if(N % 2 == 0) answer = max(solve(N - 1, 1), solve(N - 2, 0));
  else answer = max(solve(N - 1, 2), max(solve(N - 2, 1), solve(N - 3, 0)));

  cout << answer << "\n";

  return 0;
}

Measured memory_bytes: 22392
#include <stdio.h>
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	if(a<b)
	printf("a < b\n");
	else if(a>b)
	printf("a > b\n");
	else
	printf("a == b\n");
	return 0;
}


Measured memory_bytes: 2056
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>
#include<numeric>
#include<limits.h>
#include<utility>
#include<cstdlib>
#include<bitset>
#define LP(i,n) for(int i=0;i<n;i++)
#define LPIN(n,a) for(int i=0;i<n;i++)cin >> a[i]
using namespace std;

int main(){
int n;
bool flag = true;
cin >> n;
vector<long long int> v(n);
for(int i=0;i<n;i++){
cin >> v[i];
}
v[n-1]++;
if(n==1){
    cout << "Yes" << endl;
    return 0;
}
if(n==2){
if(v[0] <= v[1]+1){
cout <<"Yes" << endl;
}
else cout <<"No" << endl;
return 0;
}
for(int i=n-2;i>=1;i--){
if(v[i+1] > v[i])v[i]++;
if(v[i]  < v[i-1]){
    flag = false;
    break;
}
}
//LP(i,n)cout << v[i] << " ";
//cout <<endl;
if(flag== true)cout <<"Yes" << endl;
else cout <<"No" << endl;
return 0;
}

Measured memory_bytes: 1024
// This file is a "Hello, world!" in Java language by OpenJDK for wandbox.

import java.util.*;
import java.io.*;

class Main
{
	public static void main(String[] args){
		new Main().run();
	}
	
	void run(){
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int K=sc.nextInt();
		long[] H=new long[N];
		for(int i=0;i<N;++i)H[i]=sc.nextLong();
		Arrays.sort(H);
		long ans=0;
		for(int i=0;i<N-K;++i)ans+=H[i];
		System.out.println(ans);
	}
}

// OpenJDK reference:
//   http://openjdk.java.net/

// Java language references:
//   http://docs.oracle.com/javase


Measured memory_bytes: 84916
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n,c;
	int p;
	int i,j;
	
	cin>>n>>c;
	
	int sum=0;
	for(i=0;i<c;i++){
		cin>>p;
		sum+=p;
	}
	
	if(sum%(n+1)!=0) cout<<sum/(n+1)+1<<endl;
	else cout<<sum/(n+1)<<endl;
	
	return 0;
}	
	


Measured memory_bytes: 3108
import java.util.*;

public class Main{
    void solve(){
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        int k = scan.nextInt();
        ArrayList<Integer> out = new ArrayList<>();
        for(int i = a; i < Math.min(a + k, b); i++) out.add(i);
        for(int i = Math.max(a, b - k + 1); i <= b; i++) if(!out.contains(i)) out.add(i);
        for(int i : out) System.out.println(i);
        scan.close();
    }

    public static void main(String[] args){
        new Main().solve();
    }
}


Measured memory_bytes: 36260
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
            while(sc.hasNext()) {
                int n = sc.nextInt();
                int a = sc.nextInt();
                int b = sc.nextInt();
                int c = sc.nextInt();
                int x = sc.nextInt();
                if(b+a+b+c+x == 0)break;
                int cnt = 0;
                int[] y = new int[n+1];
                for(int i=1;i<=n;i++) {
                	y[i] = sc.nextInt();
                }
                
                int X = x;
                boolean can = true;
                for(int i=1;i<=n;i++) {
	                while(true) {
	                	boolean fin = false;
	                	if(X==y[i]) {
	                		if(i != n)
	                			cnt++;
	                		X = (a*X + b) % c;
	                		fin = true;
	                		break;
	                	}
	                	if(cnt == 10000) {
	                		can = false;
	                		break;
	                	}
	                	X = (a*X + b) % c;
	                	if(!fin)cnt++;
	                }
	                if(!can)break;
                }
                if(!can || cnt > 10000)
                	System.out.println(-1);
                else
                	System.out.println(cnt);
            }
        }
    }
}


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

int n, ans;
string s, t;
int main() {
	cin >> n >> s >> t;
	ans = n * 2;
	rep(i, n) {
		if (s.substr(s.size() - 1 - i, i + 1) == t.substr(0, i + 1)) {
			ans = n * 2 - (i + 1);
		}
	}
	s == t ? ans = n : n++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

void ChristmasEveEve()
{
  int n;
  cin >> n;
  int p;
  int ans = 0;
  int max = 0;
  for (int i = 0; i < n; i++)
  {
    cin >> p;
    ans = ans + p;
    if (max < p) max = p;
  }
  ans = ans - int(max / 2);
  
  cout << ans << endl;
  return;
}

int main()
{
  ChristmasEveEve();
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>

using namespace std;

typedef long long ll;
const ll nmax = 1e9 + 7;
const ll mod = 998244353;
const double PI = 2 * asin(1);

int main(){
  string S; cin >> S;

  int ans1 = 0, ans2 = 0;
  for (int i = 0; i < S.length(); i++){
    if (i % 2 == 0){
      if (S[i] == '0') ans1++;
      else ans2++;
    }else{
      if (S[i] == '1') ans1++;
      else ans2++;
    }
  }
  cout << min(ans1, ans2) << endl;

  return 0;
}


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

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

using namespace std;

typedef long long ll;

const ll LLINF = LLONG_MAX;

#define MAX_V 100010

struct Edge {
  int dst;
  ll w;
};

struct Data {
  int cur;
  ll height,w;
  bool operator < ( const Data &data ) const {
    if( w != data.w ) return w > data.w;
    return cur < data.cur;
  }
};

int V,E;
ll X,H[MAX_V],mini[MAX_V];
vector<Edge> G[MAX_V];

void compute() {
  rep(i,V) mini[i] = LLINF;
  mini[0] = 0;
  priority_queue<Data> Q;
  Q.push((Data){0,X,0});
  while( !Q.empty() ) {
    Data data = Q.top(); Q.pop();
    if( data.cur == V-1 ) {
      if( data.height != H[V-1] ) data.w += ( H[V-1] - data.height );
      cout << data.w << endl;
      return;
    }
    if( mini[data.cur] < data.w ) continue;
    rep(i,(int)G[data.cur].size()) {
      Edge &e = G[data.cur][i];
      ll cost = data.w;
      ll height = data.height;
      if( height - e.w >= 0LL ) {
        if( height - e.w > H[e.dst] ) {
          cost += ( height - e.w - H[e.dst] );
          cost += e.w;
          height = H[e.dst];
        } else {
          cost += e.w;
          height -= e.w;
        }
      } else {
        ll up = llabs( height - e.w );
        cost += up;
        height += up;
        cost += e.w;
        height = 0;
      }
      if( mini[e.dst] > cost ) {
        mini[e.dst] = cost;
        Q.push((Data){e.dst,height,cost});
      }
    }
  }
  puts("-1");
}

int main() {
  cin >> V >> E >> X;
  rep(i,V) cin >> H[i];
  rep(i,E) {
    int s,t; long long w;
    cin >> s >> t >> w;
    --s, --t;
    if( H[s] - w >= 0LL ) G[s].push_back((Edge){t,w});
    if( H[t] - w >= 0LL ) G[t].push_back((Edge){s,w});
  }
  compute();
  return 0;
}

Measured memory_bytes: 21476
#include <iostream>
#include <iomanip>
#include <cmath>
#define db long double
#define S(A,B) 2*Sin[A]*Sin[B]*Sin[n-A-B]
#define m (l+r)/2
using namespace std;
db ms,ls=0,rs=1.299038105676658,pi=3.14159265358979323846;
db Sin[200050];
long long n,k,i,p,q,l,r;
int main() {
	cin>>n>>k;
	cout<<setprecision(50);
	if (n%3==0&&k>1LL*n*(n-1)*(n-2)/6-n/3) {cout<<rs;return 0;}
	for (i=1;i<=n;i++) Sin[i]=sin(i*pi/n); k=k/n+(k%n>0);
	while (true) {
		db s=(ls+rs)/2;
		p=0,q=0,ms=0;
		for (i=1;i<=n/3;i++) {
			if (S(i,i)>s) break;
			l=i,r=(n-i)/2+1;
			while (r-l>1) if (S(i,m)<s) l=m;else r=m;
			if (ms<S(i,m)) ms=S(i,m),q=1+(m!=i&&m*2!=n-i);
			p+=2*(m-i)+1-(m*2==n-i);
		}
		if (k<=p&&p-q<k) break;
		if (p<k) ls=s;else rs=s;
	}
	cout<<ms;
}

Measured memory_bytes: 1152
/* 
****	
	AUTHOR :- @soham01 
****
*/
#include "bits/stdc++.h"
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long int h ,a;
	cin>>h>>a;
	cout<<ceil((double)(h/(double)a))<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define d(x) cout << #x << " = " << x << endl
const int maxn = 105;
int n, m;
int head[maxn], nxt[maxn << 1], tail[maxn << 1], ecnt = 1;
int a[maxn], x[maxn], y[maxn];
bool col[maxn << 1];
ll ans;

void addedge(int u, int v) {
	nxt[++ecnt] = head[u];
	head[u] = ecnt;
	tail[ecnt] = v;
}

bool dfs1(int u, int p, int t) {
	if (u == t) return true;
	for (int e = head[u]; e; e = nxt[e]) {
		int v = tail[e];
		if (v != p)
			if (dfs1(v, u, t)) {
				col[e] = col[e ^ 1] = true;
				return true;
			}
	}
	return false;
}

void dfs(int pos, int cnt) {
	if (pos == m + 1) {
		if (!cnt) return ;
		memset(col, false, sizeof(col));
		for (int i = 1; i <= cnt; i++) dfs1(x[a[i]], 0, y[a[i]]);
		ll tmp = ecnt - 1; // * 2
		for (int i = 2; i <= ecnt; i++) tmp -= col[i];
		tmp >>= 1;
		tmp = (1LL << tmp);
		if (cnt & 1) ans -= tmp;
		else ans += tmp;
		return ;
	}
	dfs(pos + 1, cnt);
	a[cnt + 1] = pos;
	dfs(pos + 1, cnt + 1);
	a[cnt + 1] = 0;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n - 1; i++) {
		int u, v; scanf("%d%d", &u, &v);
		addedge(u, v); addedge(v, u);
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) scanf("%d%d", &x[i], &y[i]);
	ans = (1LL << (n - 1));
	dfs(1, 0);
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <string>

using namespace std;

int main() {

	int n, q, t;
	string name;
	queue<pair<string, int> > Q;

	cin >> n >> q;

	for (int i = 0; i < n; i++) {
		cin >> name >> t;
		Q.push(make_pair(name, t));
	}
	pair<string, int> u;
	int elaps = 0;
	int a = 0;

	while (!Q.empty()) {
		u = Q.front();
		Q.pop();
		a = min(u.second, q);
		u.second -= a;
		elaps += a;
		if (u.second > 0) {
			Q.push(u);
		} else {
			cout << u.first << " " << elaps << endl;
		}
	}
	return 0;
}

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

int main() {





	int n, k;
	int min = 0;
	cin >> n >> k;

	int arr[n];

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + n);
	for (int j = 0; j < k; j++) {
		min = min + arr[j];
	}

	cout << min;

}

Measured memory_bytes: 3196
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long LL;
const int MAXN = 100000 + 3;
int a[5][5];
int n;
int vis[5][5];


int main() {
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            cin>>a[i][j];
    cin>>n;
    int flag, x;
    for(int k=0;k<n;k++) {
        cin>>x;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++) {
                if(a[i][j] == x) {
                    vis[i][j] = 1;
                }
            }
    }

    for(int i=0;i<3;i++) {
        flag = 1;
        for(int j=0;j<3;j++) {
            if(!vis[i][j])flag = 0;
        }
        if(flag) {
            cout<<"Yes"<<endl;
            return 0;
        }
    }

    for(int i=0;i<3;i++) {
        flag = 1;
        for(int j=0;j<3;j++) {
            if(!vis[j][i])flag = 0;
        }
        if(flag) {
            cout<<"Yes"<<endl;
            return 0;
        }
    }

    if(vis[0][0] && vis[1][1] && vis[2][2]
       || vis[0][2] && vis[1][1] && vis[2][0]) {
        cout<<"Yes"<<endl;
            return 0;
       }
    cout<<"No"<<endl;
    return 0;
}


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

using namespace std;

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

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

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
	int x, a;
	cin >> x >> a;
	cout << (x < a ? 0 : 10) << endl;
    
    return 0;
}



Measured memory_bytes: 3608
local n=io.read("*n","*l")
local a={}
local b={}
for i=1,n do
    x=io.read("*n")
    a[i]=x
    b[i]=x
end
table.sort(b)

for i=1,n do
    if a[i]>b[n//2] then
        print(b[n//2])
    else
        print(b[n//2+1])
    end
end


Measured memory_bytes: 10588
import java.util.*;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Set<String> set = new HashSet<>();
		
		for (int i = 0; i < n; i++) {
			set.add(sc.next());
		}
		System.out.println(set.size() == 3 ? "Three": "Four");
		
	}
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<bool> vb;

const int MAXN = 3000;

double prob[MAXN];
double matrix[MAXN][MAXN];

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

    int n; cin >> n;
    for(int i=1; i<=n; i++)
        cin >> prob[i];

    matrix[0][0] = 1;
    for(int i=1; i<=n; i++){
        matrix[0][i] = 0;
        matrix[i][0] = matrix[i-1][0]*(1-prob[i]);
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            matrix[i][j] = prob[i]*matrix[i-1][j-1] + (1-prob[i])*matrix[i-1][j];
        }
    }
    
    double ans=0;
    for(int i=(n+1)/2; i<=n; i++){
		ans += matrix[n][i];    
    }

    cout.precision(17);    
    cout << fixed << ans << '\n';

    return 0;
}



Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long int n;
    cin>>n;
    long long int arr[n];
    for(long long int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+n);
    long long int Min = arr[0];
    long long int Max = arr[n-1];
    long long int ans = LLONG_MAX;
    for(long long int i=Min;i<=Max;i++)
    {
        long long temp=0;
        for(int j=0;j<n;j++)
        {
            temp+=abs(arr[j]-i)*abs(arr[j]-i);
        }
        ans=min(ans,temp);
    }
    cout<<ans<<"\n";
}

Measured memory_bytes: 3580
import sys
input = sys.stdin.readline
from operator import itemgetter

def main():
	n, k = map(int, input().strip().split())
	if k % 2 == 1:
		print((n // k)**3)
	else:
		print((n // k)**3 + (((n-k//2)//k)+1)**3)

if __name__ == '__main__':
	main()


Measured memory_bytes: 38256
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

print(ans)

Measured memory_bytes: 75484
#include <bits/stdc++.h>
using namespace std;
template<typename T>
T gcd (T a, T b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (a < b) swap(a, b);
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
template<typename T1, typename T2>
inline bool chmax (T1& a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int main() {
  int n;
  cin >> n;
  vector<int> a(n + 1, 0);
  for (int i = 1; i <= n; i++) cin >> a[i];
  vector<int> l(n + 1, 0), r(n + 1, 0);
  for (int i = 1; i <= n; i++) l[i] = gcd(l[i - 1], a[i]);
  for (int i = n; i >= 1; i--) r[i - 1] = gcd(r[i], a[i]);
  int ret = 0;
  for (int i = 0; i < n; i++) {
    chmax(ret, gcd(l[i], r[i + 1]));
  }
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 1408
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=550;
int i,j,k,H,W,h,w,fg,t;
int a[N][N];
int main() {
	scanf("%d%d%d%d",&H,&W,&h,&w);
	if (H%h==0 && W%w==0) return puts("No"),0;
	puts("Yes");
	if (H%h) {
		for (i=1;i<=H;i++) {
			for (j=1;j<=W;j++) {
				if (i%h==0) t=-1000000*(h-1);
				else t=999999;
				printf("%d ",t);
			}
			puts("");
		}
	}
	else {
		for (i=1;i<=H;i++) {
			for (j=1;j<=W;j++) {
				if (j%w==0) t=-1000000*(w-1);
				else t=999999;
				printf("%d ",t);
			}
			puts("");
		}
	}
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,srt,end) for (long long i=(srt);i<(long long)(end);i++)
#define VL vector<ll> 
ll N,M;
int main(){
    cin>>N>>M;
    if(N==M)cout<<"Yes";
    else cout<<"No";
    return 0;
}

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

int main() {
  
  int K;
  int X;
  
  cin >> K >> X;
  
  int A = X - K + 1;
    
  for(int i = 0;i < K * 2 - 1;++i){
    cout << A;
    cout << " ";
    A++;
  }
}


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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int h,w,m; cin >> h >> w >> m;
  int br[300001];
  int bc[300001];
  int cntr[300001] = {};
  int cntc[300001] = {};
  int maxr=0,maxc=0;
  for(int i = 0; i < m; ++i){
    cin >> br[i] >> bc[i];
    ChangeMax(maxr,++cntr[br[i]]);
    ChangeMax(maxc,++cntc[bc[i]]);    
  }
  bitset<300001>r,c;
  int cr=0,cc=0;
  for(int i = 1; i <= h; ++i)if(maxr == cntr[i])cr+=r[i] = 1;
  for(int i = 1; i <= w; ++i)if(maxc == cntc[i])cc+=c[i] = 1;
  int cntd = 0;
  for(int i = 0; i < m; ++i)
    cntd += c[bc[i]]&&r[br[i]];
  cout << maxr + maxc - (cntd == cr*cc) << endl;
}


Measured memory_bytes: 8392
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int l, n;
    cin >> l >> n;
    string s;
    cin >> s;
    ll co = 0;
    for (int i = 1; i < l; i++) {
        if (s[i] == 'o' && s[i - 1] == 'o') {
            co++;
        }
    }
    ll res = l;
    for (int i = 0; i < n; i++) {
        res += co * 3LL;
        co *= 2LL;
    }
    cout << res << endl;
}



Measured memory_bytes: 3232
#include <bits/stdc++.h>  // include all standard C++ libraries

using namespace std;

// Loops
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define _rrep(i,n) rrepi(i,n,0)
#define rrepi(i,a,b) for(int i=int(a)-1;i>=int(b);--i)

#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(xi, x) for (auto&& xi : x)
// Note: we can use rep(i,N) or rep(i,from,to)


// typedef
using ll = long long;
template <class T> using vec = vector<T>;
using vi   = vector<int>;
using vvi  = vector<vi>;
using vvvi = vector<vvi>;
using pii  = pair<int, int>;


// Constants

// Shorter repr for frequently used terms
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second


// Algorithms
#define all(x) (x).begin(), (x).end()
#define uniq(v) v.erase( unique(all(v)), v.end() )
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))

template<class T> pair<T, size_t> max(vector<T> &x){ auto it = max_element(all(x)); return mp(*it, it-x.begin()); }
template<class T> pair<T, size_t> min(vector<T> &x){ auto it = min_element(all(x)); return mp(*it, it-x.begin()); }

template<class T> inline bool chmax(T &maxval, const T &newval) { if (maxval<newval) { maxval=newval; return 1; } return 0; }
template<class T> inline bool chmin(T &minval, const T &newval) { if (minval<newval) { minval=newval; return 1; } return 0; }

// Utilities
// Grid world utilities
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
#define inside(H,W,y,x) 0<=(x) && (x)<(W) && 0<=(y) && (y)<(H)

inline int in() {int x; cin >> x; return x;} // read int from cin
inline  ll IN() {ll x; cin >> x; return x;}  // read ll from cin



// Debug
#ifdef LOCAL
  #include "dump.hpp"
  #define debug(x) cerr << #x << ": " << x << '\n'
#else
  #define dump(...)
  #define debug(x)
#endif

// Paste snippets here!!
ll gcd(ll a, ll b) {
    if (b < a) swap(a,b);
    while (a) {
        ll c = a;
        a = b % c;
        b = c;
    }
    return b;
}
// 

int main(){
  cin.tie(0); ios::sync_with_stdio(false);    // Magic for faster cin
  int N=in();
  vector<ll> A(N);
  vector<ll> G1(N);
  vector<ll> G2(N);
  rep(i,N){ cin >> A[i]; }

  G1[0] = A[0];
  rep(i,1,N){
    G1[i] = gcd(G1[i-1],A[i]);
  }
  G2[N-1] = A[N-1];
  for(int i=N-2;i>=0;i--){
    G2[i] = gcd(G2[i+1],A[i]);
  }
  dump(G1,G2);
  ll g = max(G1[N-1],G2[0]);
  ll g2 = max(G2[1],max(G1[N-2], g));
  rep(i,1,N-1){
    if(G1[i-1]>G1[i] && G2[i]<G2[i+1]){
      g = max(g, gcd(G1[i-1],G2[i+1]));
    }
  }
  cout << max(g,g2) << endl;

  // ll gcd_f = A[0];
  // bool first = true;
  // rep(i,1,N){
  //   ll tmp = gcd(gcd_f,A[i]);
  //   if(first && tmp==1){
  //     first = false;
  //   } else {
  //     gcd_f = tmp;
  //   }
  // }
  // ll gcd_b = A[N-1];
  // first = true;
  // for(int i=N-2; i>=0; --i){
  //   ll tmp = gcd(gcd_b,A[i]);
  //   if(first && tmp==1){
  //     first = false;
  //   } else {
  //     gcd_b = tmp;
  //   }
  // }
  // cout << max(gcd_f, gcd_b) << endl;
  return 0;
}


Measured memory_bytes: 2560
#include "bits/stdc++.h"
using namespace std;

int main() {
	int N, count = 0;
	string A, B, C;
	cin >> N >> A >> B >> C;
	for (int i = 0; i < N; i++) {
		if (A[i] == B[i] && B[i] == C[i]) count += 0;
		else if (A[i] == B[i] || B[i] == C[i] || C[i] == A[i]) count += 1;
		else count += 2;
	}
	cout << count;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main()
{
    double n;
    while(scanf("%lf",&n)!=EOF)
    {
        double y=(n*n)/19.6;
        double k=0.0;
        int i;
        for(i=1;k<y;i++)
        {
            k=5.0*i-5.0;
        }
        printf("%d\n",i-1);
    }
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=(a);i<(b);i++)
#define MOD 1000000007
#define MP make_pair
#define PB push_back
typedef long long ll;

int N, K, C, cnt[26];
string s;

int main () {
        cin >> N >> K;
        fo(i, 0, N) {
                cin >> s;
                cnt[s[0] - 'A']++;
        }
        while (1) {
                sort(cnt, cnt+26), reverse(cnt, cnt+26);
                if (!cnt[K-1]) break;
                fo(i, 0, K) cnt[i]--;
                C++;
        }
        cout << C << endl;
        return 0;
}


Measured memory_bytes: 256
a,b=map(int,input().split())

def gcd(x,y):
  if x%y==0:
    return y
  else:
    return gcd(y,x%y)
  
  
n=gcd(a,b)  
i=2
ans=[1]

while i * i <= n:
  if n % i == 0:
    n /= i
    ans.append(i)
  else:
    i += 1

ans.append(n)    
  
print(len(set(ans)))

Measured memory_bytes: 3064