akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <deque>
#include <list>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1LL << 60;
const ll MOD = 1000000007LL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b; cin >> a >> b;
    cout << (a+b)%24;
    cout << endl;
    return 0;
}



Measured memory_bytes: 256
n = int(input())

pattern = {}

for nn in range(1,n + 1):
    f = int(nn / (10 ** (len(str(nn) ) -1)))
    l = nn % 10  
    p = f * 10 + l
    if f == l:
        p = f
    
    if  p in pattern:
       pattern[p] += 1
    else:
        pattern[p] = 1


s = 0
for p, v in pattern.items():

    f = int(p / (10 ** (len(str(p) ) -1)))
    l = p % 10
    p2 = l * 10 + f
    if l == 0:
        continue      
    elif p < 10: 
        s +=  v * v
    elif p2 in pattern:
        s += v * pattern[p2]
print(s)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
	int m, k; cin >> m >> k;
	if(m <= 1){
		if(k == 0){
			for(int i = 0; i < 1<<m; i++) cout << i << " " << i << " "; cout << endl;
		} else {
			cout << -1 << endl;
		}
	} else {
		if(k < (1<<m)){
			deque<int> ans;
			ans.push_back(k);
			for(int i = 0; i < 1<<m; i++) if(i != k){
				ans.push_back(i);
				ans.push_front(i);
			}
			ans.push_back(k);
			while(!ans.empty()){
				cout << ans.back() << endl;
				ans.pop_back();
			}
		} else {
			cout << -1 << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 2944
import java.util.*;
class Main
{
  public static void main(String[] args)
  {
  
  Scanner sc = new Scanner(System.in);
  
  int k = sc.nextInt();
  int s = sc.nextInt();
  
  int sum = 0;
  
  for(int x=0 ; x<=k ; x++){
    for(int y=0 ; y<=k ; y++){
     int z = s-(x+y);
      if( (z<=k)&&(z>=0)){
        sum++;
      }
    }
}
System.out.println(sum);
}
}

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

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	
	int mn = 1e9;
	int res = 0;
	
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		
		if (x < mn) {
			mn = x;
			res++;
		}
	}
	
	printf("%d\n", res);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl;
#define COYE cout<<"YES"<<endl;
#define COYe cout<<"Yes"<<endl;
#define COye cout<<"yes"<<endl;
#define CONO cout<<"NO"<<endl;
#define CONo cout<<"No"<<endl;
#define COno cout<<"no"<<endl;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define ALL(V) ((V).begin(),(V).end())
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
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;}
const int vx[4]={0,1,0,-1},vy[4]={1,0,-1,0};
using namespace std;

int main(){
  ll N,ans=0ll;
  cin>>N;
  vector<pair<ll,ll>> P;
  REP(i,N){
    ll a;
    cin>>a;
    P.emplace_back(make_pair(a,i));
  }
  
  SORT(P);
  
  REP(i,N){
    ans+=abs(i-P[i].second)%2;
  }
  
  cout<<ans/2<<endl;
  return 0;
}

Measured memory_bytes: 2420
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
	int r, g, b;
	std::cin >> r >> g >> b;

	if ((g * 10 + b) % 4 == 0) {
		std::cout << "YES" << std::endl;
	} else {
		std::cout << "NO" << std::endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>func(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p;
}


int main() {
  int N,X;
  cin>>N>>X;
  vector<int>x(N);
  for(int i=0;i<N;i++){
    cin>>x[i];
  }
  int ans=x[0]-X;
  for(int i=0;i<N;i++){
    int y=abs(x[i]-X);
    ans=__gcd(ans,y);
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            bool[,] Array = new bool[4, 13];

            string str = Console.ReadLine();
            int n = int.Parse(str);

            for (int i = 0; i < n; ++i)
            {
                string[] strArray = Console.ReadLine().Split(' ');
                int number = int.Parse(strArray[1]);

                switch (strArray[0])
                {
                    case "S":
                        Array[0, number - 1] = true;
                        break;
                    case "H":
                        Array[1, number - 1] = true;
                        break;
                    case "C":
                        Array[2, number - 1] = true;
                        break;
                    case "D":
                        Array[3, number - 1] = true;
                        break;
                }

            }
            for (int j = 0; j < 4; ++j)
            {
                for (int i = 0; i < 13; ++i )
                {
                    if (Array[j,i] == false)
                    {
                        switch(j)
                        {
                            case 0:
                                Console.WriteLine("S {0}", i+1);
                                break;
                            case 1:
                                Console.WriteLine("H {0}",i+1);
                                break;
                            case 2:
                                Console.WriteLine("C {0}",i+1);
                                break;
                            case 3:
                                Console.WriteLine("D {0}",i+1);
                                break;
                        }
                    }
              
            }
            }
            
            

        }
    }
}

Measured memory_bytes: 5728
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
void solve();
 
clock_t start_time;
double get_current_time() {
	return (double)(clock() - start_time) / CLOCKS_PER_SEC;
}
 
int main() {
	// freopen("substring.in", "r", stdin);
	// freopen("substring.out", "w", stdout);
 
	ios_base::sync_with_stdio(false);
	solve();
}
 
/* ========== actual code starts here ========== */
 
#define fi first
#define re return
#define se second
#define in insert
#define pb push_back
#define eb emplace_back
#define y1 y123123123123
#define all(x) x.begin(), x.end()
#define hash hash123s
 
#define repx(i, x, n) for (int i = x; i < (n); i++)
#define repd(i, n, d) for (int i = 0; i < (n); i += d)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepd(i, n, d) for (int i = (n) - 1; i >= 0; i -= d)
#define rep(i, n) for (int i = 0; i < (n); i++)

template<class t>
void print(t x, int end = 1) {
	cout << x << (end == 1 ? "\n" : " ");
}

template<class T>
void print(const vector<T> &v, int end = 1) {
	rep(i, (int) v.size()) {
		print(v[ i ], 0);
	}
	cout << endl;
}

template<class T>
void print(const set<T> &v, int end = 1) {
	for(auto to = v.begin(); to != v.end(); to++) {
		print(*to);
	}
	cout << endl;
}

template<class T>
void print(const map<T, T> &v, int end = 1) {
	for(auto to : v) {
		print(to.fi, 0);
		cout << ": ";
		print(to.se);
	}
}

template<class t>
void errprint(t x, int end = 1) {
	cerr << x << (end == 1 ? "\n" : " ");
}

#ifdef artem
	#define debug(x) x
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define debug(x)
#endif

void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> ans(n), cnt(n, 1);
	ans[ 0 ] = 1;
	rep(i, m) {
		int x, y;
		cin >> x >> y, --x, --y;
		if(ans[ x ]) ans[ y ] = 1;
		cnt[ y ]++;
		cnt[ x ] = max(0, cnt[ x ] - 1);
		if(!cnt[ x ] && ans[ x ]) ans[ x ] = 0;
	}

	int res = 0;
	rep(i, n) if(ans[ i ]) ++res;
	cout << res << endl;
}

Measured memory_bytes: 4000
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

H = I()

ans = 0
for i in range(H.bit_length()):
    ans += 2**i

print(ans)

Measured memory_bytes: 38384
# include <stdio.h>
# include <bits/stdc++.h>
 
 
#define _USE_MATH_DEFINES_
#define ll long long
#define ld long double
#define Accepted 0
#define pb push_back
#define mp make_pair
#define sz(x) (int)(x.size())
#define every(x) x.begin(),x.end()
#define F first
#define S second
#define For(i,x,y)  for (ll i = x; i <= y; i ++) 
#define FOr(i,x,y)  for (ll i = x; i >= y; i --)
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0)
// ROAD to...                                                                                                                                                                                                                Red
 
using namespace std;
 
inline bool isvowel (char c) {
	c = tolower(c);
    if (c == 'a' || c == 'e' || c == 'i' || c == 'y' || c == 'o' || c == 'u') return 1;
    return 0;
}
 
const double eps = 0.000001;
const ld pi = acos(-1);
const int maxn = 1e7 + 9;
const int mod = 1e9 + 7;
const ll MOD = 1e18 + 9;
const ll INF = 1e18 + 123;
const int inf = 2e9 + 11;
const int mxn = 1e6 + 9;
const int N = 6e5 + 123;                                          
const int M = 22;
const int pri = 997;
const int Magic = 2101;
 
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
 
int n, m, k; 
ll ans;
ll res = inf;
int main () {               
    cin >> n;
 
    For (i, 1, n) {
    	ll a, b;
    	cin >> a >> b;
    	if (a > b) {
    		res = min(res, b);
    	}
    	ans += a;
    }
 
    if(res == inf) res = ans;
 
    cout << ans - res;
    	
    return Accepted;
}
 
// Coded By OB

Measured memory_bytes: 384
n = int(input())
count = 0
l = []

for i in range(0, n):
    b = int(input())
    l.append(b)

maxv = l[1]-l[0]
minv = l[0]

for i in range(1,n):
    maxv = max(maxv, l[i]-minv)
    minv = min(minv, l[i])

print(maxv)



Measured memory_bytes: 13588
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e9;

signed main(){
  lint N; cin >> N;
  vector<lint> dp(N + 1, INF);
  dp[0] = 0; dp[1] = 1;
  for(lint i = 2; i <= N; i++){
    for(lint p6 = 1; p6 <= N; p6 *= 6){
      if(i - p6 >= 0) dp[i] = min(dp[i], dp[i - p6] + 1);
    }
    for(lint p9 = 1; p9 <= N; p9 *= 9){
      if(i - p9 >= 0) dp[i] = min(dp[i], dp[i - p9] + 1);
    }
  }
  cout << dp[N] << endl;
}

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

using namespace std;

int main() {
    int a, b, c, x, out = 0;
    cin >> a >> b >> c >> x;
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            for (int k = 0; k <= c; k++) {
                if (500 * i + 100 * j + 50 * k == x) {
                    out++;
                }
            }
        }
    }
    cout << out << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

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

  int max_number = 1;
  int max_count = 0;

  for (int i = 2; i <= n; ++i) {
    int j = i;
    int count = 0;
    while (j % 2 == 0) {
      ++count;
      j /= 2;
    }
    if (count > max_count) {
      max_count = count;
      max_number = i;
    }
  }

  cout << max_number << endl;
  return 0;
}


Measured memory_bytes: 256
ii=3
s=[]
icase=0
if icase==0:
    for i in range(ii):
        s.append(list(map(int,input().split())))  # 二次元配列入力　二次元マップみたいな入力のとき
elif icase==1:
    s.append([1,0,1])
    s.append([2,1,2])
    s.append([1,0,1])

yn=1
for i in range(ii-1):
    if (s[i][1]-s[i][0])!=(s[i+1][1]-s[i+1][0]):
        yn=0
for i in range(ii-1):
    if (s[i][2]-s[i][0])!=(s[i+1][2]-s[i+1][0]):
        yn=0
for j in range(ii-1):
    if (s[1][j]-s[0][j])!=(s[1][j+1]-s[0][j+1]):
        yn=0
for j in range(ii-1):
    if (s[2][j]-s[0][j])!=(s[2][j+1]-s[0][j+1]):
        yn=0

if yn==1:
    print("Yes")
else:
    print("No")
        


Measured memory_bytes: 3064
// https://atcoder.jp/contests/abc179/tasks/abc179_e
// 解説放送

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

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

    vector<long> ids(m, -1);
    vector<long> xs;

    long len = 0;
    long tot = 0;
    while (ids[x] == -1)
    {
        xs.push_back(x);
        ids[x] = len;
        len++;
        tot += x;
        x = (x * x) % m;
    }

    long loop_len = len - ids[x];
    long loop_sum = 0;
    for (long i = ids[x]; i < len; i++)
    {
        loop_sum += xs[i];
    }

    long ans = 0;
    if (n < len)
    {
        for (long i = 0; i < n; i++)
        {
            ans += xs[i];
        }
    }
    else
    {
        ans += tot;
        n -= len;
        ans += (n / loop_len) * loop_sum;
        n %= loop_len;
        for (long i = 0; i < n; i++)
        {
            ans += xs[ids[x] + i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4604
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<class T>
bool chmax(T &a, T b){if(a < b){a = b; return true;} return false;}
template<class T>
bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;}
void print() {
    cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << " ";
    print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << " ";
    }
    cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
    for (auto& vec : df) {
        print(vec);
    }
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    ll sum = 0;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum ^= a[i];
    }
    vector<ll> ans(n);
    rep(i,0,n){
        ans[i] = sum ^ a[i];
    }

    print(ans);
}

Measured memory_bytes: 6328
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;



class Myon
{
	public Myon() { }
	public static int Main()
	{
		cin = new Scanner();
		new Myon().calc();
		return 0;
	}

	static Scanner cin;

	void calc()
	{
		int n = cin.nextInt();
		int d = cin.nextInt();

		int cnt = 0;

		var x = new List<List<int>>(n);
		for (int i = 0; i < n; i++)
		{
			var _x = new List<int>(d);
			for (int j = 0; j < d; j++)
			{
				_x.Add(cin.nextInt());
			}
			x.Add(_x);
		}

		for (int i = 0; i < n; i++)
		{
			for (int j = i + 1; j < n; j++)
			{
				int distSq = 0;
				for (int k = 0; k < d; k++)
				{
					distSq += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
				}
				int dist = (int)Math.Sqrt(distSq);
				if (dist * dist == distSq) cnt++;
			}
		}

		Console.WriteLine(cnt);
	}


	//swap
	void swap<T>(ref T a, ref T b)
	{
		T c = a;
		a = b;
		b = c;
	}
}

class Point
{
	List<int> x;
}


class Scanner
{
	string[] s;
	int i;

	char[] cs = new char[] { ' ' };

	public Scanner()
	{
		s = new string[0];
		i = 0;
	}

	public string next()
	{
		if (i < s.Length) return s[i++];
		string st = Console.ReadLine();
		while (st == "") st = Console.ReadLine();
		s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
		if (s.Length == 0) return next();
		i = 0;
		return s[i++];
	}

	public int nextInt()
	{
		return int.Parse(next());
	}
	public int[] ArrayInt(int N, int add = 0)
	{
		int[] Array = new int[N];
		for (int i = 0; i < N; i++)
		{
			Array[i] = nextInt() + add;
		}
		return Array;
	}

	public long nextLong()
	{
		return long.Parse(next());
	}

	public long[] ArrayLong(int N, long add = 0)
	{
		long[] Array = new long[N];
		for (int i = 0; i < N; i++)
		{
			Array[i] = nextLong() + add;
		}
		return Array;
	}

	public double nextDouble()
	{
		return double.Parse(next());
	}


	public double[] ArrayDouble(int N, double add = 0)
	{
		double[] Array = new double[N];
		for (int i = 0; i < N; i++)
		{
			Array[i] = nextDouble() + add;
		}
		return Array;
	}
}


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

int n, a, mx, t[15], d[15];
int main()
{
	int i;
	cin >> n;
	for (i = 1; i <= 9; i++) d[i] = t[i] = -1;
	while (n--) {
		scanf("%d", &a);
		for (i = 0; i <= 9; i++) if (d[i] >= 0) t[(i + a) % 10] = max(t[(i + a) % 10], d[i] + a);
		for (i = 0; i <= 9; i++) d[i] = max(d[i], t[i]), t[i] = -1;
 	}
 	for (i = 1; i <= 9; i++) mx = max(mx, d[i]);
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const long long mod = 998244353;
struct mint {
  long long x;
  mint(ll x = 0):x(x%mod) {}
  mint& operator+=(const mint a) {
    (x += a.x) %= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    (x += mod-a.x) %= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint ret(*this);
    return ret += a;
  }
  mint operator-(const mint a) const {
    mint ret(*this);
    return ret -= a;
  }
  mint operator*(const mint a) const {
    mint ret(*this);
    return ret *= a;
  }
  mint pow(ll t) const {
    if(t==0) return mint(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 {
    mint ret(*this);
    return ret /= a;
  }
};
ostream &operator<<(ostream& os, const mint& x) {
  os << x.x;
  return os;
}
class modutils {
  vector<mint> fact, invfact;
public:
  modutils(int n = 200005):fact(n+1),invfact(n+1) {
    fact[0] = 1;
    for(int i=1; i<=n; i++) fact[i] = fact[i-1] * i;
    invfact[n] = fact[n].inv();
    for(int i=n; i>=1; i--) invfact[i-1] = invfact[i] * i;
  }
  mint pow(mint x, ll n) {
    return x.pow(n);
  }
  mint comb(ll n, ll k) {
    if(n<0 || k<0 || n<k) return 0;
    return fact[n] * invfact[k] * invfact[n-k];
  }
  mint perm(ll n, ll k) {
    if(n<0 || k<0 || n<k) return 0;
    return fact[n] * invfact[n-k];
  }
  mint fac(ll n) {
    return fact[n];
  }
};
modutils mutil;



int main(){
  ll N, M, K;
  cin >> N >> M >> K;

  mint ret(0);
  rep(k,K+1){
    mint tmp(1);

    tmp *= mutil.comb(N-1, k);
    
    ll t = N - k;

    tmp *= M;
    tmp *= mutil.pow(M-1, t-1);

    ret += tmp;
  }

  cout << ret << endl;
  
  return 0;
}



Measured memory_bytes: 6232
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF 1<<30
#define LINF 1LL<<60
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N; cin >> N;
	map<ll, ll> m;
	vector<ll> a(N);
	for (int i = 0; i < N;i++) {
		cin >> a[i];
		m[a[i]]++; m[a[i] + 1]++; m[a[i] - 1]++;
	}
	ll ans = -1;
	for (auto it = m.begin(); it != m.end(); it++) {
		ans = max(ans, it->second);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7040
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.D
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var (N, M) = Read2Longs();
            var yakusuu = new List<long>();
            for (var i = 1; i * i < M; i++)
            {
                if (M % i == 0)
                {
                    yakusuu.Add(i);
                    if (i * i != M) { yakusuu.Add(M / i); }
                }
            }
            foreach (var item in yakusuu.OrderByDescending(x => x))
            {
                if (M % item != 0) { continue; }
                if (M / item < N) { continue; }
                return item;
            }
            return 1;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


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

int jump[12][2] = {{-1,2},{0,2},{1,2},{2,1},{2,0},{2,-1},{1,-2},{0,-2},{-1,-2},{-2,-1},{-2,0},{-2,1}};
int xs[10], ys[10];

bool shower(int xp, int yp, int xscr, int yscr) {
  return ((xp>=xscr-1)&&(xp<=xscr+1)&&(yp>=yscr-1)&&(yp<=yscr+1));
}

bool in_park(int xp, int yp) {
  return ((xp>=0) && (xp<10) && (yp>=0) && (yp<10));
}

bool dfs(int x, int y, int n) {
  if (!n) return true;
  int xx, yy, nn;

  nn = n-1;
  for (int i=0; i<12; i++) {
    xx = x + jump[i][0];
    yy = y + jump[i][1];
    if (!in_park) continue;
    if (shower(xx, yy, xs[nn], ys[nn])) {
      if (dfs(xx, yy, nn)) return true;
    }
  }
  return false;
}

int main() {
  int n, x0, y0;
  while (1) {
    cin >> x0 >> y0;
    if (!x0 && !y0) break;
    cin >> n;
    for (int i=0; i<n; i++) {
      cin >> xs[i] >> ys[i];
    }
    reverse(xs, xs+n);
    reverse(ys, ys+n);

    if (dfs(x0, y0, n)) {
      cout << "OK" << endl;
    } else {
      cout << "NA" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1152
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=3005;
int ans,n,mod,jc[N],inv[N],s[N][N],f[N],pw[N*N];
int ksm(int x,int y,int mod)
{
  int res=1;
  while (y) {if (y&1) res=(ll)res*x%mod;x=(ll)x*x%mod;y>>=1;}
  return res;
}
int c(int n,int m) {return (ll)jc[n]*inv[m]%mod*inv[n-m]%mod;}
int main()
{
	scanf("%d%d",&n,&mod);
	jc[0]=jc[1]=inv[0]=inv[1]=pw[0]=1;
	for (int i=2;i<=n;i++) jc[i]=(ll)jc[i-1]*i%mod,inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	for (int i=2;i<=n;i++) inv[i]=(ll)inv[i-1]*inv[i]%mod;
	for (int i=1;i<=n*n;i++) pw[i]=(ll)pw[i-1]*2%mod;
	for (int i=0;i<=n;i++) s[i][0]=1;//初始化，都有一种可能分到0个集合 
	for (int i=1;i<=n;i++)
	  for (int j=1;j<=i;j++)
	    s[i][j]=((ll)s[i-1][j-1]+(ll)(j+1)*s[i-1][j]%mod)%mod;//<=i个元素分入j个非空集合的方案数  
	for (int i=0;i<=n;i++)
	{
	   for (int j=0;j<=i;j++) f[i]=((ll)f[i]+(ll)s[i][j]*pw[(n-i)*j]%mod)%mod;
	   f[i]=(ll)f[i]*ksm(2,ksm(2,n-i,mod-1),mod)%mod;	
	}
	for (int i=0;i<=n;i++)
	  if (i&1) ans=((ll)ans-(ll)c(n,i)*f[i]%mod+mod)%mod;
	  else ans=((ll)ans+(ll)c(n,i)*f[i]%mod)%mod;
	printf("%d\n",ans);
	return 0;
}

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

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

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

    vector<int> d(n);
    for(int i=0; i<n; i++){
        d[i] = i+1;
    }

    int a, b, count = 0;
    do{
        bool flag_p = true, flag_q = true;
        for(int i=0; i<n; i++){
            if(d[i] != p[i]) flag_p = false;
            if(d[i] != q[i]) flag_q = false;
        }
        if(flag_p == true) a = count;
        if(flag_q == true) b = count;

        count += 1;
    }while(next_permutation(d.begin(),d.end()));

    cout << abs(a-b) << endl;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
B = [int(x) for x in input().split()]
A = [0]*N
A[0]   = B[0]
A[N-1] = B[N-2]
for T in range(0,N-2):
    A[T+1] = min(B[T],B[T+1])
print(sum(A))

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

int main()
{
  int N, M;
  cin >> N >> M;
  vector<int64_t> A(N), B(N), C(M), D(M);
  for (int i = 0; i < N; i++)
  {
    cin >> A[i] >> B[i];
  }
  for (int i = 0; i < M; i++)
  {
    cin >> C[i] >> D[i];
  }
  for (int i = 0; i < N; i++)
  {
    int64_t mind = (1LL << 62), minj = 0;
    for (int j = 0; j < M; j++)
    {
      int64_t d = abs(A.at(i) - C.at(j)) + abs(B.at(i) - D.at(j));
      if (d < mind)
      {
        mind = d;
        minj = j;
      }
    }
    cout << minj + 1 << endl;
  }
}


Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;
const int MOD = 1000000007; // 計算してからmodで割る ans = (ans * a) % mod
#define int long long
template <typename T = long long > T in () { T x; cin >> x; return(x);}
// int a = in() のように使うlong long以外の型の時はstirng s = in<string>()のように型を指定する

signed main(void){
    string sl; cin >> sl;
    REP(i, sl.size()) cout << 'x';
    cout << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdlib>
#include<iostream>
#include<vector>
#include<map>
#include<cmath>
#include<cstdio>
using namespace std;
int A,B;
char temp[6];

int main(int argc, char const *argv[])
{
cin>>A>>B;
int ans=0;
for(int i=A;i<=B;i++){
    sprintf(temp,"%d",i);
    if(temp[0]==temp[4]&&temp[1]==temp[3]){
        ans++;
    }
}
cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 256
A = [[] for _ in range(3)]

A[0] = list(map(int, input().split()))
A[1] = list(map(int, input().split()))
A[2] = list(map(int, input().split()))

N = int(input())
B = [[False, False, False] for _ in range(3)]
for i in range(N):
    b = int(input())
    for j in range(3):
        for k in range(3):
            if A[j][k] == b:
                B[j][k] = True

if all(B[0]) or all(B[1]) or all(B[2]):
    print('Yes')
elif all([B[0][0], B[1][0], B[2][0]]) or all([B[0][1], B[1][1], B[2][1]]) or all([B[0][2], B[1][2], B[2][2]]):
    print('Yes')
elif all([B[0][0], B[1][1], B[2][2]]) or all([B[0][2], B[1][1], B[2][0]]):
    print('Yes')
else:
    print("No")

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

#define REP(i, n) for(int64_t i = 0; i < n; i++)
#define REPR(i, n) for(int64_t i = n; i >= 0; i--)
#define FOR(i, m, n) for(int64_t i = m; i < n; i++)
#define FORR(i, m, n) for(int64_t i = m; i >= n; i--)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}
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;}
const ll INF= 1ll << 60;
const ll MOD = 1000000007;
double EPS = 1e-10;
//----------------------------------------------------------

int n,m;
ll h[100005];
bool ans[100005];
int main(){
    cin >> n >> m;
    int cnt=0;
    FOR(i,1,n+1)
    {
        cin >> h[i];
    }
    FOR(i,1,n+1)ans[i]=true;
    REP(i,m)
    {
        int a, b;
        cin >> a >> b;
        if(h[a]<h[b])ans[a]=false;
        else if(h[a]>h[b])ans[b]=false;
        else{
            ans[a]=false;
            ans[b]=false;
        }
    }
    FOR(i,1,n+1)
    {
        if(ans[i])cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 4508
#include<stdio.h>
#include<stdlib.h>

struct node {
    int key;
    struct node *left, *right, *parent;
};

typedef struct node* Node;

Node root;

void insert(int k) {
    Node x, y, newnode;

    newnode = (Node)malloc(sizeof(struct node));
    
    newnode->key = k;
    newnode->left = newnode->right = NULL;

    x = root; 
    y = NULL;
    
    while (x != NULL) {
        y = x;
        if (newnode->key < x->key) x = x->left;
        else x = x->right;
    }
    newnode->parent = y;

    if (y == NULL) root = newnode;
    else if (newnode->key < y->key) y->left = newnode;
    else y->right = newnode;
}

void inorder(Node T) {
    if (T == NULL) return;
    inorder(T->left);
    printf(" %d", T->key);
    inorder(T->right);
}

void preorder(Node T) {
    if (T == NULL) return;
    printf(" %d", T->key);
    preorder(T->left);
    preorder(T->right);
}

Node find(int k) {
    Node T;
    T = root;
    while (T != NULL && T->key != k) {
        if (k < T->key) T = T->left;
        else T = T->right;
    }

    return T;
}

Node getMinimum(Node n) {
    while (n->left != NULL) n = n->left;
    return n;
}

Node getSuccessor(Node z) {
    Node y;

    if (z->right != NULL) return getMinimum(z->right);

    y = z->parent;
    while (z != NULL && z == y->right) {
        z = y;
        y = y->parent;
    }

    return y;
}

void delete(Node z) {
    Node x, y;
    if (z->left != NULL && z->right != NULL) y = getSuccessor(z);
    else y = z;

    if (y->left != NULL) x = y->left;
    else x = y->right; 

    if (x != NULL) x->parent = y->parent;

    if (y->parent == NULL) root = x;
    else if (y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;

    if (y != z) z->key = y->key;

    free(y);
}

int main() {
    int n, k;
    int i;
    char com[8];

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf(" %s", com);
        if (com[0] == 'i') {
            scanf("%d", &k);
            insert(k);
        }
        else if (com[0] == 'p') {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
        else if (com[0] == 'f') {
            scanf("%d", &k);
            if (find(k) == NULL) printf("no\n");
            else printf("yes\n");
        }
        else {
            scanf("%d", &k);
            delete(find(k));
        }
    }

    return 0;
}



Measured memory_bytes: 20476
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;
using namespace std;
typedef long long int LL;
typedef unsigned long long int ULL;

int main() {
    int n, k;
    cin >> n >> k;
    string str;
    cin >> str;

    if (str[k-1] == 'A') str[k-1] = 'a';
    if (str[k-1] == 'B') str[k-1] = 'b';
    if (str[k-1] == 'C') str[k-1] = 'c';
    cout << str << endl;
    return 0;
}


Measured memory_bytes: 888
N, H, D = map(int, input().split())
P, a, s = 10**9+7, 1, 0
for i in range(1, N+1):
    a = a*i%P
    s = (s+a)%P

X = [a]
for i in range(1, H):
    X.append(a*s%P)
    a += X[-1]
    if i >= D: a -= X[-D-1]
    a %= P

print(a)

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

// int/long:            -2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:      -9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define MOD 1000000007

#define Rep0(i, n)      for (auto i=0; i<n; i++)
#define Rep1(i, n)      for (auto i=1; i<=n; i++)
#define Sort(P) sort(P.begin(), P.end())
#define Rev(P)  reverse(P.begin(), P.end())

int     main() {
        int N;
        cin >>N;
        N %=1000;
        if (0==N)
                cout <<0 <<endl;
        else
                cout <<1000-N <<endl;
        return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(int I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(int I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;




int main(){
	int N;
	while(1){
		cin >> N;
		if(N==0)break;
		vector<int> w(N+1);
		FOR(i,1,N+1)cin >> w[i];
		bool dp[N+1][N+1]={};
		int ans = 0;
		for(int i=2;i<N+1;i+=2){//i:幅
			FOR(j,1,N+1){//j:開始位置
				// [j,j+i-1]
				if(j+i-1>N)continue;
				if( (j+1 > j+i-2) && abs(w[j]-w[j+i-1])<=1){
					dp[j][j+i-1]=true;
					ans = max(ans,i);
				}else if(dp[j+1][j+i-2] && abs(w[j]-w[j+i-1])<=1){
					dp[j][j+i-1]=true;
					ans = max(ans,i);
				}
				for(int k=2;k<=i-2;k+=2){
					if(dp[j][j+k-1]&&dp[j+k][j+i-1]){
						dp[j][j+i-1]=true;
						ans = max(ans,i);
					}
				}
			}
		}
		int dpa[N+1][N+1]={};
		FOR(i,1,N)if(dp[i][i+1])dpa[i][i+1]=2;
		FOR(i,3,N+1){//幅
			FOR(j,1,N+1){//開始
				if(j+i-1>N)continue;
				for(int k=0;k<i;k++){
					dpa[j][j+i-1] = max(dpa[j][j+k-1]+dpa[j+k][j+i-1],dpa[j][j+i-1]);
					if(dp[j][j+i-1])dpa[j][j+i-1] = i;
				}
			}
		}
		cout << dpa[1][N] << endl;
	}
}


Measured memory_bytes: 3536
#include<iostream>
#include<iomanip>
#include<stdio.h>
#include<queue>
#include<math.h>
#include<ctime>
#include<deque>
#include<set>
#include<string.h>
#include<algorithm>
#include<map>
#include<stack>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define mmm(a,b) memset(a,b,sizeof(a))
#define sc(x) scanf("%d",&x)
using namespace std;
const ll mod = 1e9+7;
const ll inf = 1e17;
const double pi = acos(-1.0);
const int maxn = 1e6+5;
ll kase;
int n,m,p;
ll f[maxn],vis[maxn];
void run(){
    cin>>n;
    ll ans=0;
    for(int i=1;i<n;i++){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                ans+=(i==j*j?1:2);
            }
        }
    }
    cout<<ans;
}
int main(){
#ifdef haosao
freopen("main.h", "r", stdin);
//freopen("out.txt","w",stdout);
#endif
    ios::sync_with_stdio(false);
//    cin>>kase;
//    while(kase--)
        run();
    return 0;
}


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

int main()
{
    int n,d;
    cin>>n;
    if(n%2)d=(n/2)+1;
    else d=n/2;

    double p=(d*1.0)/(n*1.0);

    printf("%.6f\n",p);


    return 0;
}


Measured memory_bytes: 256
function sum_arr(arr) {
    return arr.reduce(function(prev, current, i, arr) {
        return prev+current;
    });
};


function main(arg) {
	arg = arg.split("\n")
	var N = arg[0].split(" ")[0]
	var A = arg[1].split(" ").map(e => Number(e))
	var B = arg[2].split(" ").map(e => Number(e))

	// var sum_a = sum_arr(A)
	// var sum_b = sum_arr(B)
	// var diff = sum_a - sum_b
	// // console.log(diff)
	// if (sum_a < sum_b) {
	// 	console.log(-1)
	// 	return;
	// }
// console.log(diff)

	var diffs = []
	var diff_m = 0

	var counter = 0

	for (var i = 0; i < A.length; i++) {
		var tmp = A[i] - B[i]
		if (tmp < 0) {
			diff_m += tmp
			counter++
		} else {
			diffs.push(tmp)
		}
	}

	if (diff_m >= 0) {
		console.log(0)
		return
	}

	diffs.sort((a,b) => b - a)

	for (var i = 0; i < diffs.length; i++) {
		diff_m += diffs[i]
		counter++

		if (diff_m > 0) {
			break
		}
	}

	if (diff_m  <= 0) {
		console.log(-1)
		return;
	}

	console.log(counter)

}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 32016
#include<cstdio>
#include<iostream>
#include<vector>

using namespace std;

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

const int N = 10;

class P{
	public:
	int x,y,kind;
	P(int x,int y,int kind):x(x),y(y),kind(kind){}
};

class B{
	public:
	int board[N][N];
	B(){rep(i,N)rep(j,N)board[i][j]=0;}
};


int color[3][5][5]={
	{
		{0,0,0,0,0},
		{0,0,1,0,0},
		{0,1,1,1,0},
		{0,0,1,0,0},
		{0,0,0,0,0}
	},
	{
		{0,0,0,0,0},
		{0,1,1,1,0},
		{0,1,1,1,0},
		{0,1,1,1,0},
		{0,0,0,0,0}
	},
	{
		{0,0,1,0,0},
		{0,1,1,1,0},
		{1,1,1,1,1},
		{0,1,1,1,0},
		{0,0,1,0,0}
	}
};

void put(B& b, P p, int sc=1){
	rep(i,5){
		rep(j,5){
			int nx = p.x+j-2;
			int ny = p.y+i-2;
			if(nx<0 || ny<0 || nx>=N || ny>=N)continue;
			if(color[p.kind][i][j]==1){
				b.board[ny][nx] -= sc;
			}
		}
	}
}

bool canput(B& b, P p){
	rep(i,5){
		rep(j,5){
			int nx = p.x+j-2;
			int ny = p.y+i-2;
			
			if(color[p.kind][i][j]==1){
				if(nx<0 || ny<0 || nx>=N || ny>=N)return false;
				if(b.board[ny][nx]<=0)return false;
			}
		}
	}
	return true;
}


void pboard(B& b){
	rep(i,N){
		rep(j,N)printf("%d ",b.board[i][j]);puts("");
	}
}

int n;
vector<P> ans;

void saiki(B& b, int x, int y, vector<P> temp){
	
	/*
	printf("%d %d\n",x,y);
	pboard(b);
	*/
	if(x==N-1 && y==N-1){
		
		ans = temp;
		if(ans.size()==0)ans.push_back(P(-1,-1,-1));
		return;
	}
	
	if(b.board[y][x]!=0){
		
		P cand[3]={P(x,y+1,0),P(x+1,y+1,1), P(x,y+2,2)};
		
		rep(i,3){
			if(!canput(b,cand[i]))continue;
			
			put(b,cand[i]);
			temp.push_back(cand[i]);
			
			saiki(b, x, y, temp);
			
			put(b,cand[i],-1);
			temp.pop_back();
		}
	}else{
		saiki(b, (x+1)%N, y+(x+1)/N, temp);
	}
}

int main(){
	
	B b;
	cin>>n;
	rep(i,N)rep(j,N){
		int c;
		cin>>c;
		b.board[i][j] = c;
	}
	
	vector<P> temp;
	ans.clear();
	saiki(b, 0,0, temp);
	
	if(ans.size()==0){
		puts("hoge");
	}else{
		if(ans[ans.size()-1].kind==-1){
			while(1){
				ans.push_back(P(0,0,0));
				if(ans.size()==0)break;
				ans.pop_back();
			}
		}
	}
	
	rep(i,ans.size()){
		printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].kind+1);
	}
}

Measured memory_bytes: 1224
#include <stdio.h>
#include <stdlib.h>
#define MAX_NUM 1005

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(void){
    int N, M, K;
    int array[MAX_NUM*MAX_NUM] = {-1};
    int num_index = 0;
    int i, j;

    scanf("%d %d %d", &N, &M, &K);

    for(i=0; i<=N; i++){
        for(j=0; j<=M; j++){
            array[num_index++] = i*M + j*N - 2*i*j; 
        }
    }

    qsort(array, num_index, sizeof(int), compare_int);
    if((int *)bsearch(&K, array, num_index, sizeof(int), compare_int) == NULL)
        printf("No");
    else
        printf("Yes");

    return 0;
}

Measured memory_bytes: 8060
#include <bits/stdc++.h>
using namespace std;
struct Fast {Fast() {std::cin.tie(0); ios::sync_with_stdio(false);}} fast;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007


int main() {
  int X, A;
  cin >> X >> A;
  cout << (X < A ? "0" : "10") << endl;
}



Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))
f = [0]*n
fflag = [False]*n
cnt = 0
flag = False
while False in fflag:
    for i in range(n):
        if f[i] == h[i]:
            fflag[i] = True
        if not fflag[i]:
            f[i] += 1
            flag = True
        elif flag:
            cnt += 1
            flag = False
    if flag:
        cnt += 1
        flag = False
print(cnt)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int dp[110][10010];
int v[110], w[110];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, W;
    cin >> n >> W;
    rep(i, 0, n){
        cin >> v[i] >> w[i];
    }
        int ans = 0;    
    rep(i, 0, n){
        rep(j, 0, W + 1){
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if(j - w[i] < 0) continue;
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
                chmax(ans, dp[i + 1][j]);
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 10972
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = input()
    if n[-1] in "24579":
        print("hon")
    elif n[-1] in "0168":
        print("pon")
    else:
        print("bon")
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 65468
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

//よくわかんないけど通った？

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


	int N, K;
	cin >> N >> K;
	int H[302] = {};
	rep1(i, N) cin >> H[i];
	ll hutuu = 0;
	rep(i, N + 1) {
		if (H[i + 1] > H[i]) hutuu += H[i + 1] - H[i];
	}

	ll dp[302][601] = {};
	rep(i, N + 1) {
		auto dpi = dp[i];
		ll tmp1 = max(0, H[i + 1] - H[i]);
		ll tmp2 = max(0, H[i] - H[i + 1]);
		ll tmp3 = min(tmp1, tmp2);
		int mae = H[i + 1];
		ll maetmp = tmp3;
		for (int j = i + 2; j <= N + 1; j++) {
			if (mae < H[j]) tmp1 += H[j] - mae;
			if (mae > H[j]) tmp2 += mae - H[j];
			tmp3 = min(tmp1, tmp2);
			if (maetmp < tmp3) {
				int k = j - i - 1;
				auto dpj = dp[j] + k;
				rep(p, K) chmax(dpj[p], dpi[p] + tmp3);
			}
			mae = H[j];
			maetmp = tmp3;
		}
		auto dpi2 = dp[i + 1];
		rep(p, K + 1) chmax(dpi2[p], dpi[p]);
	}
	co(hutuu - dp[N + 1][K]);


	Would you please return 0;
}

Measured memory_bytes: 1664
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (n);i++)
using ll = long long;
const ll MOD=1000000007;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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

vector<ll> v;
vector<ll> w;
vector<vector<ll>> table;

ll dp(ll n,ll sv)
{
  if(sv<=0) return 0;
  if(n<0)
  {
    return INF;
  }
  if(table.at(n).at(sv)<INF) return table.at(n).at(sv);
  chmin(table.at(n).at(sv),dp(n-1,sv-v.at(n))+w.at(n));
  chmin(table.at(n).at(sv),dp(n-1,sv));
  chmin(table.at(n).at(sv),(ll)1000000001);
  return table.at(n).at(sv);
}
int main() 
{
  ll N,W; cin>>N>>W;
  v=vector<ll>(N);
  w=vector<ll>(N);
  rep(i,N)
  {
    cin>>w.at(i)>>v.at(i);
  }
  table=vector<vector<ll>>(N,vector<ll>(100001,INF));
  for(int sv=100000;sv>=0;sv--)
  {
    if(dp(N-1,sv)<=W) 
    {
      cout<<sv<<endl;
      break;
    }  
  }  
  return 0;
}


Measured memory_bytes: 82448