akhauriyash/Code-Regression huggingface dataset:
import java.awt.Point;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	public static final int[] dx = {1,0,-1,0};
	public static final int[] dy = {0,-1,0,1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			int w = sc.nextInt();
			int h = sc.nextInt();
			if (w == 0) {
				break;
			}
			int[][] m = new int[h][w];
			boolean[][] used = new boolean[h][w];
			for(int i=0;i<h;i++) {
				String s = sc.next();
				for(int j=0;j<w;j++) {
					m[i][j] = s.charAt(j) == '.' ? 0 : s.charAt(j) - '0';
				}
			}
			ArrayList<Piece> pieces = new ArrayList<Piece>();
			for(int i=0;i<h;i++) {
				for(int j=0;j<w;j++) {
					if (m[i][j] != 0 && !used[i][j]) {
						Piece piece = new Piece();
						int blocks = 0;
						int n = m[i][j];
						used[i][j] = true;
						Deque<Point> q = new ArrayDeque<Point>();
						q.offer(new Point(j,i));
						while(!q.isEmpty()) {
							Point p = q.poll();
							piece.shape[blocks++] = p;
							for(int k=0;k<4;k++) {
								int ni = p.y + dy[k];
								int nj = p.x + dx[k];
								if (ni < 0 || ni >= h || nj < 0 || nj >= w) {
									continue;
								}
								if (m[ni][nj] == n && !used[ni][nj]) {
									used[ni][nj] = true;
									q.offer(new Point(nj,ni));
								}
							}
						}
						pieces.add(piece);
					}
				}
			}
			for(int l=0;l<pieces.size();l++) {
				Piece p = pieces.get(l);
				for(int k=0;k<4;k++) {
					m[p.shape[k].y][p.shape[k].x] = l+1; 
				}
			}
			for(Piece p:pieces) {
				for(int k=0;k<4;k++) {
					int pi = p.shape[k].y;
					int pj = p.shape[k].x;
					if (pi >= 1 && m[pi-1][pj] != 0 && m[pi-1][pj] != m[pi][pj]) {
						if (!p.child.contains(m[pi-1][pj]-1)) {
							p.child.add(m[pi-1][pj]-1);
						}
					}
					if (pi == h-1 || (m[pi+1][pj] != 0 && m[pi+1][pj] != m[pi][pj])) {
						p.xr = Math.max(p.xr,pj);
						p.xl = Math.min(p.xl,pj);
					}
					p.xg_x4 += pj;
				}
			}
			boolean stable = true;
			for(int i=0;i<pieces.size();i++) {
				Piece p = pieces.get(i);
				HashSet<Integer> childs = new HashSet<Integer>();
				childs.add(i);
				childs(childs, pieces, p);
				int xgsum = 0;
				for(int j:childs) {
					xgsum += pieces.get(j).xg_x4;
				}
				int n = childs.size();
				stable &= 4 * n * p.xl < xgsum + 2 * n && xgsum + 2 * n < 4 * n * (p.xr+1);
				if (stable == false) {
					break;
				}
			}
			System.out.println(stable ? "STABLE" : "UNSTABLE");
		}
	}
	
	public static void childs(HashSet<Integer> ret,ArrayList<Piece> al,Piece p) {
		for(int i=0;i<p.child.size();i++) {
			int c = p.child.get(i);
			ret.add(c);
			childs(ret, al, al.get(c));
		}
	}
	
	static class Piece {
		Point[] shape = new Point[4];
		int xg_x4 = 0;
		int xl = Integer.MAX_VALUE;
		int xr = Integer.MIN_VALUE;
		ArrayList<Integer> child = new ArrayList<Integer>();
	}

}

Measured memory_bytes: 57948
#include<iostream>
using namespace std;
#include<stdio.h>

int main()
{
    int *A;
    int i, H;
    scanf("%d", &H);
    A = new int[H + 1];
    for(i = 1; i <= H; i++) scanf("%d", &A[i]);
    for(i = 1; i <= H; i++){
        printf("node %d: key = %d, ", i, A[i]);
        if(i / 2 > 0){ printf("parent key = %d, ", A[i / 2]); }
        if(2 * i <= H){ printf("left key = %d, ", A[2 * i]); }
        if(2 * i + 1 <= H){ printf("right key = %d, ", A[2 * i + 1]); }
        printf("\n");
    }
    delete [] A;
    return 0;
}

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

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<vector< pair<int, int> >> xy(N);
	for (int i = 0; i < N; ++i) {
		int a;
		cin >> a;
		for (int j = 0; j < a; ++j) {
			int x, y;
			cin >> x >> y;
			xy[i].emplace_back(x - 1, y);
		}
	}

	int ans = 0;
	for (int i = 0; i < (1<<N); ++i) {
		vector<int> memo(N, 0);
		int tmp = 0;
		for (int j = 0; j < N; ++j) {
			if ((i>>j) & 1) {
				++tmp;
				memo[j] = 1;
			}
		}

		bool ok = true;
		for (int j = 0; j < N; ++j) {
			if (memo[j] == 0) { continue; }
			for (int k = 0; k < xy[j].size(); ++k) {
				int x = xy[j][k].first, y = xy[j][k].second;
				if (memo[x] != y) { ok = false; }
			}
		}
		if (ok) { ans = max(ans, tmp); }
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL maxx = 1000000 + 10;
char H[maxx][15];

// ?°?????¬???¬??¢?????°???
LL CharToInt(char ch) {
	if (ch == 'A') return 1;
	if (ch == 'C') return 2;
	if (ch == 'G') return 3;
	if (ch == 'T') return 4;
	return 0;
}

// ?°?????¬??????¬?????°?????¶??????key
long long getKey(char str[]) {
	LL sum = 0, p = 1;
	LL len = strlen(str);
	for (long long int i = 0; i < len; i++) {
		sum += p * CharToInt(str[i]);
		p *= 5;
	}
	return sum;
}

LL h1(LL key) {
	return key % maxx;
}
LL h2(LL key) {
	return 1 + (key % (maxx - 1));
}
// find ??????
bool find(char str[]) {
	LL key, h;
	key = getKey(str);
	for (LL i = 0;; i++) {
		h = (h1(key) + i * h2(key)) % maxx;
		//?????°key
		if (strcmp(H[h], str) == 0) return true;
		// key????????¨
		else if (strlen(H[h]) == 0) return false;
	}
	return false;

}
// insert??????
void insert(char str[]) {
	LL key, h;
	key = getKey(str);
	for (LL i = 0;; i++) {
		h = (h1(key) + i * h2(key)) % maxx;
		//?????°key
		if (strcmp(H[h], str) == 0) return ;
		// key????????¨
		else if (strlen(H[h]) == 0) {
			// ?????\
			strcpy(H[h], str);
			return ;
		}
	}
}
int main() {
	int n, q, key;
	char str[20], op[20];
	for (int i = 0; i < maxx; i++)
		H[i][0] = '\0';
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s %s", op, str);
		if (op[0] == 'i')
			insert(str);
		else {
			if (find(str))
				printf("yes\n");
			else
				printf("no\n");
		}
	}
	return 0;
}

Measured memory_bytes: 17792
using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp3
{

    class Program
    {
        static void Main(string[] args)
        {
            string s = (Console.ReadLine());
            
            if(s == "Sunny")
            {
                Console.WriteLine("Cloudy");
            }

            if (s == "Cloudy")
            {
                Console.WriteLine("Rainy");
            }

            if (s == "Rainy")
            {
                Console.WriteLine("Sunny");
            }

        }
    }
}

Measured memory_bytes: 13140
N, Y = list(map(int, input().split()))

x = -1
y = -1
z = -1

for a in range(N+1):
    for b in range(N-a+1):
        c = N - a - b
        total = 10000 * a + 5000 * b + 1000 * c
        if Y == total:
            x = a
            y = b
            z = c

print(str(x)+" "+str(y)+" "+str(z))


Measured memory_bytes: 3064
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define SORTD(a) sort(a.rbegin(), a.rend());
#define ll long long
#define INF 1000000000000000000
#define INT_MAX 2147483647

#include <iostream>
#include <vector>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

int main(){
    int N,K;
    string S;
    cin >> N;
    cin >> S;
    cin >> K;
    char c = S[K-1];
    REP(i, S.length()){
        if(S[i]!=c){
            S[i] = '*';
        }
    }
    cout << S << endl;
    return 0;
}


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

const ll mod = 1000000007;

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

  vector<int> c(26);
  for (int i = 0; i < n; ++i) {
    c[s[i] - 'a'] += 1;
  }

  ll ans = 1;
  for (auto n : c)
    ans *= n + 1, ans %= mod;
  ans -= 1;

  cout << ans << endl;
}

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

using namespace std;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

int rand(int r = INT_MAX) {
    return rand(0, r);
}

int bit[60][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    long long k;
    cin >> k;
    vector <long long> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        for(int j = 0; j < 60; j++) {
            bit[j][(a[i] >> j) & 1]++;
        }
    }
    long long ans = 0;
    for(int i = 60; i >= 0; i--) {
        if((ans | (1LL << i)) > k) continue;
        if(bit[i][0] >= bit[i][1]) {
            ans |= (1LL << i);
        }
    }
    long long res = 0;
    for(int i = 0; i < n; i++) {
        res += a[i] ^ ans;
    }
    cout << res << '\n';
    return 0;
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int md = (int)1e9+7;
void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

int main(){
	int n,m;
	cin >>n >>m;
	vector<ll>  x(n),y(n),z(n); 
	rep(i,n) cin >>x[i] >>y[i] >>z[i];
	
	ll ans = -1LL<<60;
	rep(a,2) rep(b,2) rep(c,2){
		vector<ll> sma(n);
		rep(j,n){
			sma[j] =( a? x[j]: -x[j] )+( b? y[j]: -y[j] )+(c? z[j]: -z[j]);
		}
		sort(sma.rbegin(), sma.rend());
		ans = max(ans, accumulate(sma.begin(), sma.begin()+m, 0LL));
	}
	cout << ans <<"\n";
	return 0;
}


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

s3=["a..","a..",".aa"]
s = [["abcc", "abdd", "ddba", "ccba"],
["dccdd", "daa.c", "c..bc", "c..bd", "ddccd"],
["abbc..", "a.ac..", "bba.cc", "a..aab", "a..b.b", ".aabaa"],
["aba....","aba....","bab....","bab....","a..bbaa","a..aabb",".aabbaa"]]

if n == 2:
    print(-1)
elif n == 3:
    [print(x) for x in s3]
else:
    d, m = divmod(n, 4)
    d -= 1
    m += 4
    for i in range(d):
        [print("." * 4 * i + x + "." * (4 * (d - i - 1) + m)) for x in s[0]]
    [print("." * 4 * d + x) for x in s[m - 4]]

Measured memory_bytes: 4084
#include<stdio.h>

#define MAX 500000
#define INFTY 2000000000

int g_count;

void merge(int [],int,int,int);
void mergeSort(int [],int,int);

int main(){
  int n,i;
  int A[MAX];

  scanf("%d",&n);
  for(i = 0;i <= n-1;i++) scanf("%d",&A[i]);
  
  mergeSort(A,0,n);
  
  for(i = 0;i <= n-1;i++){
    if(i != 0) printf(" ");
    
    printf("%d",A[i]);
  }
  
  printf("\n");
  
  printf("%d\n",g_count);

  return 0;
}


void merge(int A[],int left,int mid,int right){
  int L[MAX / 2 + 2],R[MAX / 2 + 2];
  int n1,n2,i,j,k;
  
  n1 = mid - left;
  n2 = right - mid;
  /*L[0...n1],R[0...n2]を生成*/
  for(i = 0;i <= n1-1;i++)
    L[i] = A[left + i];

  for(i = 0;i <= n2-1;i++)
    R[i] = A[mid + i];
  
  L[n1] = INFTY;
  R[n2] = INFTY;
  i = 0;
  j= 0;
  for(k = left;k <= right-1;k++){
    g_count++;
    if (L[i] <= R[j])
      A[k] = L[i++];
    
    else
      A[k] = R[j++];
  }
}

void mergeSort(int A[],int left,int right){
  if(left + 1 < right){
    int mid = (left + right) / 2;
    mergeSort(A,left,mid);
    mergeSort(A,mid,right);
    merge(A,left,mid,right);
  }
}
  



Measured memory_bytes: 5620
#include <bits/stdc++.h>
const long long MOD = 1000000007;
const int INF = INT_MAX / 2;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
#define vi vector<ll>
#define vs vector<string>
#define vp vector<pair<ll, ll>>
#define vt vector<tuple<ll, ll, ll>>
using namespace std;
//vector<vector<ll>> vv(110, vector<ll>(50, 0));

typedef int Weight;
struct Edge
{
	int from, to; Weight cost;
	bool operator < (const Edge& e) const { return cost < e.cost; }
	bool operator > (const Edge& e) const { return cost > e.cost; }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
void add_edge(Graph &g, int from, int to, Weight cost)
{
	g[from].push_back(Edge{ from, to, cost });
}

int main()
{
	ll n, m;
	cin >> n >> m;
	vi v(n);
	REP(i, n) cin >> v[i];
	sort(ALL(v),greater<ll>());
	cout << accumulate(v.begin(), v.begin() + m, 0LL) << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
 	public static void main(String args[]){
     	Scanner sc=new Scanner(System.in);
      int a=sc.nextInt();
      int b=sc.nextInt();
      if(a<13&&a>=6)
        	b/=2;
      else if(a<6)
        	b=0;
      System.out.println(b);
    }
}

Measured memory_bytes: 21844
#include <iostream>

int main(){
   int N, A;
   std::cin >> N;

   int count[N];
   std::fill(count, count+N, 0);
   for(int i=1; i<N; ++i){
      std::cin >> A;
      ++count[A-1];
   }
   for(int i=0; i<N; ++i)
      std::cout << count[i] << std::endl;

   return 0;
}


Measured memory_bytes: 4380
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<" = "<<x<<endl;
#define dbg_v(v,n) {cerr<<#v<<" = [";for(int III=0;III<=n;III++)cerr<<v[III]<<(III!=n?",":"]\n");}
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define MOD 1000000007
#define zeros(x) x&(x-1)^x
#define fi first
#define se second
#define Nmax 500005
using namespace std;


template<typename T = int>
struct AIB{
    #define INIT_VALUE (type == 2 ? INF : (type == 1 ? -INF : 0))
    vector<T> A;
    int N, type;
    bool isReversed;
    const T INF = 1e9;

    // type 0 = sum, 1 = max, 2 = min
    AIB(int _N = Nmax + 5,int _type = 0, bool _isReversed = false) : N(_N), type(_type), isReversed(_isReversed){
        assert(type >= 0 && type <= 2);
        A.resize(N+1, INIT_VALUE);
    }

    void add(T pos, T val){
        for (pos=(isReversed ? N-pos-4 : pos+4);pos < N; pos += pos & (-pos)){
            if (type == 0) A[pos] += val;
            else if (type == 1) A[pos] = max(A[pos], val);
            else A[pos] = min(A[pos], val);
        }
    }

    T sum(T pos){
        T ans = INIT_VALUE;
        for (pos=(isReversed ? N-pos-4 : pos+4);pos > 0; pos -= pos & (-pos)){
            if (type == 0) ans += A[pos];
            else if (type == 1) ans = max(ans, A[pos]);
            else ans = min(ans, A[pos]);
        }
        return ans;
    }

    T sum(T L, T R){
        return sum(R) - sum(L-1);
    }

    T lowerBound(T val){
        long long p = 1, st = 0;
        for (;p<N;p<<=1);
        for (;p>=1;p>>=1) if (st + p < N && sum(st+p) < val) st += p;
        if (sum(st) < val) st++;
        return st;
    }
    #undef INIT_VALUE
};
AIB<int> aib(Nmax + 5, false, true), aib2(Nmax+5, false, false);

int n,k,v[Nmax],ans,lst,ok;
ll val[Nmax],s,L[Nmax],R[Nmax];

bool OK(int i){
	if (R[i]) return 1;
	if (i==k && val[i]) return 1;
	if (s != lst){
		if (s==0 && ok == 0){
			ok = 1;
			return 1;
		}
		else if (s==0) return 0;
		return 1;
	}
	return 0;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i=1;i<=n;i++) cin >> v[i];
    

    for (int i=1;i<=n;i++){
    	R[i] = aib.sum(v[i]);
    	aib.add(v[i],1);
    	if (i >= k){
    		aib.add(v[i-k+1], -1);
    	}
    }

    for (int i=n;i>=1;i--){
    	L[i] = aib2.sum(v[i]);
    	aib2.add(v[i], 1);
    	if (i+k-1<=n){
    		aib2.add(v[i+k-1], -1);
    	}
    }
    lst = -1;
    for (int i=1;i<=n;i++){
    	s += R[i];
    	if (i >= k){
    		// dbg(lst);
    		// dbg(s);
    		// dbg(R[i]);
    		if (OK(i)){
    			ans++;
    		}
    		lst = s;
    		// dbg(L[i-k+1]);
    		s -= L[i-k+1];
    	}
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 14208
while True:
    n,x=map(int,input().split())
    if n==0 and x==0:
        exit()
    else:
        i=0
        j=0
        k=0
        c=0
        for i in range(1,n-1):
            for j in range(i+1,n):
                for k in range(j+1,n+1):
                    if i+j+k==x:
                        c+=1
        print(c)


Measured memory_bytes: 5592
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(reverse=True)
dp = [10**10] * (10**4+5)
dp[0] = 0
# ぴったり倒せるときだけ更新して、答えを出力するときに最小値を出力する
for i in range(len(dp)):
    for a, b in AB:
        dp[i] = min(dp[i], dp[i-a]+b)

print(min(dp[H:]))


Measured memory_bytes: 42348
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int hill[10];
	for(int i=0;i<10;i++) {
		scanf("%d",&hill[i]);
	}
	sort(hill,hill+10);
	for(int i=9;i>=7;i--) {
		printf("%d\n",hill[i]);
	}
}

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

int main(){
  int x,a,b;
  cin >> x >> a >> b;
  if(b <= a) cout << "delicious" << endl;
  else if(b <= a + x)  cout << "safe" << endl;
  else cout << "dangerous" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#define flush fflush(stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pl;
const int mod = (int)1e9 + 7, INF = (int)1e9;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };


double dist(double x0, double y0, double x1, double y1) {
	return sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1));
}

int main(void) {
	int n, i, j, k, l;
	double x[53], y[53], ans, px, py, sl, m, b1, b2, s;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%lf%lf", &x[i], &y[i]);
	}

	if (n == 2) {
		ans = dist(x[0], y[0], x[1], y[1]) / 2.0;
		printf("%.12lf\n", ans);
		return 0;
	}

	ans = 10000.0;
	for (i = 0; i < n - 2; i++) for (j = i + 1; j < n - 1; j++) for (k = j + 1; k < n; k++) {
		if ((y[i] - y[j]) * (x[i] - x[k]) == (y[i] - y[k]) * (x[i] - x[j])) {
			continue;
		}
		m = x[j] * y[i] - x[j] * y[k] + x[i] * y[k] - x[k] * y[i] + x[k] * y[j] - x[i] * y[j];
		b1 = (x[k] - x[j]) / 2.0 / m * (x[i] - x[j]);
		b2 = (y[k] - y[j]) / 2.0 / m * (y[i] - y[j]);
		s = b1 + b2;
		px = (x[i] + x[k]) / 2.0 + (y[i] - y[k]) * s;
		py = (y[i] + y[k]) / 2.0 + (x[k] - x[i]) * s;
		sl = 0.0;
		for (l = 0; l < n; l++) {
			sl = max(sl, dist(px, py, x[l], y[l]));
		}
		ans = min(ans, sl);
	}

	for (i = 0; i < n - 1; i++) for (j = i + 1; j < n; j++) {
		px = (x[i] + x[j]) / 2;
		py = (y[i] + y[j]) / 2;
		sl = 0.0;
		for (k = 0; k < n; k++) {
			sl = max(sl, dist(px, py, x[k], y[k]));
		}
		ans = min(ans, sl);
	}
	
	printf("%.12lf\n", ans);

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
ll INF = 1LL << 60;

struct edge {
  ll to, cost;
  edge(ll t, ll c) : to(t), cost(c) {}
};

class Dijkstra {
 private:
  ll n_;
  vector<vector<edge> > G_;
  vl d_;
  set<pll> used_;
  vl prev_;

 public:
  Dijkstra(ll n) : n_(n), G_(n) {}
  void addEdge(ll v, ll to, ll cost) { G_[v].push_back(edge(to, cost)); }
  void exec(ll s) {
    d_ = vl(n_, INF);
    prev_ = vl(n_, -1);
    priority_queue<pll, vector<pll>, greater<pll> > que;
    d_[s] = 0;
    que.push({0, s});

    while (!que.empty()) {
      pll p = que.top();
      que.pop();
      ll v = p.second;
      if (d_[v] < p.first) continue;
      for (auto& e : G_[v]) {
        if (d_[e.to] > d_[v] + e.cost) {
          d_[e.to] = d_[v] + e.cost;
          prev_[e.to] = v;
          que.push({d_[e.to], e.to});
        }
      }
    }
    rep(i, n_) {
      if (i == s) continue;
      // cout << i << "->" << prev_[i] << endl;
      used_.insert({min((ll)i,prev_[i]),max((ll)i,prev_[i])});
    }
  }
  ll dist(ll g) { return d_[g]; }
  ll cnt_used() { return used_.size(); }
};

int main() {
  ll n,m;
  cin >> n>>m;
  Dijkstra d(n);
  rep(i,m) {
    ll a,b,c;
    cin>>a>>b>>c;
    a--,b--;
    d.addEdge(a,b,c);
    d.addEdge(b,a,c);
  }
  rep(i,n) {
    d.exec(i);
  }
  cout << m - d.cnt_used() << endl;
  return 0;
}


Measured memory_bytes: 384
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    c = Counter(A)
    v = list(sorted(c.values()))
    print(sum(v[:-K]))


if __name__ == '__main__':
    main()


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

#define ll long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n,m; cin >> n >> m;
    ll ms=0;
    ll retry = pow(2,m);

    cout << (m*1900 + (n-m)*100)*retry<< endl;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define int long long
using namespace std;
const int MAX_N=300;
int N;
double dp[MAX_N+2][MAX_N+2][MAX_N+2];

signed main(){
	cin>>N;
    int a[4]={};
    REP(i,N){
        int x;
        cin>>x;
        a[x]++;
    }
    REP(k,N+1) REP(j,N+1) REP(i,N+1){
        int S=i+j+k;
        if(S==0) continue;
        if(i) dp[i][j][k]+=dp[i-1][j][k]*(double)i/(double)S;
        if(j) dp[i][j][k]+=dp[i+1][j-1][k]*(double)j/(double)S;
        if(k) dp[i][j][k]+=dp[i][j+1][k-1]*(double)k/(double)S;
        dp[i][j][k]+=1.0*(double)N/(double)S;
    }
    printf("%.16f\n",dp[a[1]][a[2]][a[3]]);
}

Measured memory_bytes: 215296
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;

int main(){
	
	int n,m; cin>>n>>m;
	vector<vector<int>> e(n);
	for(int i=0; i<m; i++){
		int u,v; cin>>u>>v;
		e.at(--u).push_back(--v);
	}
	int s,t; cin>>s>>t;
	--s; --t;
	vector<vector<int>> d(n,vector<int>(3,-1));
	d.at(s).at(0) = 0;
	queue<pair<int,int>> q;
	q.push({s,0});
	while(!q.empty()){
		auto p = q.front();
		q.pop();
		for(auto i:e.at(p.first)){
			if(d.at(i).at((p.second+1)%3)==-1){
				d.at(i).at((p.second+1)%3) = d.at(p.first).at(p.second)+1;
				q.push({i,(p.second+1)%3});
			}
		}
	}
	if(d.at(t).at(0)==-1) d.at(t).at(0)=-3;
	cout << d.at(t).at(0)/3 << endl;
}



Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
const long long INF = 1LL << 60;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int main()
{
  cout << fixed << setprecision(10);
  int H, W, K;
  cin >> H >> W >> K;
  vector<string> c(H);
  rep(i, H)
  {
    cin >> c[i];
  }
  int ans = 0;
  for (int tmp = 0; tmp < (1 << H); tmp++)
  {
    bitset<6> s(tmp);
    for (int tmp2 = 0; tmp2 < (1 << W); tmp2++)
    {
      bitset<6> t(tmp2);
      int sum = 0;
      rep(i, H)
      {
        rep(j, W)
        {
          if (s.test(i)&& t.test(j))
          {
            if (c[i][j] == '#')
            {
              sum++;
            }
          }
        }
      }
      if (sum == K)
      {
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <utility>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <set>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <memory>
#include <initializer_list>
#include <iomanip>
#include <stack>
#include <bitset>
#include <cstdio>
// #include <complex>
#include <random>
 
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using ld = long double;
// const ll INF = 1e9;
const ld INF = 1e20;
const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;
//const double PI = acos(-1);


void solve() {
    int n;
    cin >> n;
    vector<int> d(n);
    int res = 0;
    for (int i = 0; i < n; ++i) {
        cin >> d[i];
        for (int j = 0; j < i; ++j) {
            res += d[i] * d[j];
        }
    }
    cout << res;
}

int main() {
    // freopen("moscow.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    solve();
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> c(n);
    vector<int> diff(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        diff[i] = v[i] - c[i];
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (diff[i] >= 0) {
            ans += diff[i];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int N=100;
int n;
double a[N];

void ext(int &m, int &M) {
    m=M=1;
    for(int i=2; i<=n; i++) {
        if(a[i]<a[m]) m=i;
        if(a[i]>a[M]) M=i;
    }
}

int main() {
    int i, m, M;
    scanf("%d", &n);
    for(i=1; i<=n; i++) scanf("%lf", &a[i]);
    ext(m, M);
    printf("%d\n", 2*(n-1));
    if(abs(a[M])>abs(a[m])) {
        for(i=2; i<=n; i++) {
            ext(m, M);
            a[i]+=a[M];
            a[i]+=a[M];
            printf("%d %d\n%d %d\n", M, i, M, i);
        }
    }
    else {
        for(i=n-1; i>=1; i--) {
            ext(m, M);
            a[i]+=a[m];
            a[i]+=a[m];
            printf("%d %d\n%d %d\n", m, i, m, i);
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define cps CLOCKS_PER_SEC
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define eb emplace_back
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define uni(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define fi first
#define se second
#define bitcount(x) __builtin_popcount(x)
#define bit(x) (1LL << x)
#define PI acos(-1.0)
#define EPS 1e-9

#define mod 1000000007
#define maxn 200005

using namespace std;

using namespace __gnu_pbds;
template<class key, class cmp = std::less<key>>
using ordered_set = tree<key, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
///All indexing is 0-based
///methods: find_by_order(k); & order_of_key(k);
///To make it an ordered_multiset, use pairs of (value, time_of_insertion)
///to distinguish values which are similar

typedef long long ll;
typedef double ld;
typedef pair<ll, ll> par;

ll a,b,c,sol,k;

int main()
{
    #ifdef acm
    freopen("a.in","r",stdin);
    #endif // acm
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> a >> b >> c >> k;

    sol += min(a,k);
    k-=a;
    if(k>0)
        k-=b;
    if(k>0)
        sol-=k;
    cout << sol;

}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3]) {
    cout<<"Bad"<<endl;
  }
  else{
    cout<<"Good"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
import sys

N, K = map(int, input().split())
A = list(map(int, input().split()))

alr = {}
now = 1
i = 0
while not now in alr.keys():
    alr[now] = i
    now = A[now-1]
    i += 1
    if i == K:
        print(now)
        sys.exit()

place = alr[now]
circle = len(alr) - place
rem = (K - place) % circle
for k, v in alr.items():
    if v == place + rem:
        print(k)
        break

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

// verified: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3998051
struct BipartiteMatching {
    int V;
    vector<vector<int>> graph;
    vector<int> match;
    vector<int> used;
    int updateIndex;

    void add_edge(int u, int v) {
        graph[u].push_back(v);
    }

    bool dfs(int v) {
        if (used[v] == updateIndex) return false;
        used[v] = updateIndex;
        for (int u : graph[v]) {
            int w = match[u];
            if (w == -1 || dfs(w)) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
        return false;
    }

    int bipartiteMatching() {
        match.assign(V, -1);
        used.assign(V, false);
        int res = 0;
        bool update = true;
        while (update) {
            update = false;
            for (int v = 0; v < V; ++v) {
                if (match[v] == -1 && dfs(v)) {
                    update = true;
                    res++;
                }
            }
            if (update) updateIndex++;
        }
        return res;
    }
};

int main() {
    int X, Y, E;
    cin >> X >> Y >> E;

    BipartiteMatching bm;
    bm.V = X + Y;
    bm.graph.resize(bm.V);
    for (int i = 0; i < E; ++i) {
        int x, y;
        cin >> x >> y;
        bm.add_edge(x, X + y);
    }

    cout << bm.bipartiteMatching() << endl;
}


Measured memory_bytes: 3200
import core.bitop, std.bitmanip;
import core.checkedint;
import std.algorithm, std.functional;
import std.array, std.container;
import std.bigint;
import std.conv;
import std.math, std.numeric;
import std.range, std.range.interfaces;
import std.stdio, std.string;
import std.typecons;
 
void main()
{
    int n;
    readf("%s", &n);
    readln;

    auto arr = readln.chomp.split.map!(to!int).array;
    
    int[int] mp;
    
    arr.each!(x => mp[x] += 1);
    
    arr = mp.values.sort().array;
    arr.reverse();
    
    debug { arr.writeln; }
    
    auto ans = new int[] (n+1);
    
    int bar = n;
    int rest = arr.sum;
    int have = 0;
    int le = 0;
    foreach (i, e; arr.enumerate(1)) {
        rest -= e;
        have += min(e, bar);
        
        while (i * bar > have + rest) {
            bar -= 1;
            while (le < arr.length && arr[le] > bar) { ++le; }
            have -= le;
        }
        
        ans[i] = bar;
    }
    
    ans.dropOne.map!(to!string).join(" ").writeln;
}

Measured memory_bytes: 36016
while(True):
	N = int(input())
	if N ==0 :break
	W, H = map(int, input().split())
	area = [ [ 0 for i in range(W)]for i in range(H)]
	ans_max = 0
	for i in range(N):
		w, h = map(int, input().split())
		area[h-1][w-1] = 1
	S, T = map(int, input().split())
	for i in range(H-T+1):
		for j in range(W-S+1):
			ans = 0
			for k in range(i,i+T):
				ans += sum(area[k][j:j+S])
			if ans_max<ans:
				ans_max = ans
	print(ans_max)


Measured memory_bytes: 5788
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#define LL long long
#define ULL unsigned long long
#define P 1000000007
#define H 10007
#define mod(a,b) a-a/b*b
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;

long long n,k;
struct zhk{
	int a,b;
}c[100010];

inline bool cmp(zhk a,zhk b)
{
	return a.a<b.a;
}

int main()
{
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&c[i].a,&c[i].b);
	}
	sort(c+1,c+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		k-=c[i].b;
		if(k<=0)
		{
			printf("%d",c[i].a);
			break;
		}
	}
	return 0;
}


Measured memory_bytes: 1024
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

T=int(input())
Juice=[None]*T
for i in range(T):
    Juice[i]=list(map(int,input().split()))

#A最初の在庫,Bすぬけ君が買う本数,C以下の場合D追加


#A→A%B
def juicecheck(i):
    A=Juice[i][0]
    B=Juice[i][1]
    C=Juice[i][2]
    D=Juice[i][3]

    if A<B:
        print("No")
        return
    elif B>D:
        print("No")
        return
    elif B-1<=C:
        print("Yes")
        return
    else:
        x=A%B
        y=D%B
        

        z=gcd(B,D)

        if z==1 or B-(C+1)>=z or  (C+1)%z<=x%z<=(B-1)%z or ( (C+1)%z>B%z and ((C+1)%z<=x%z or x%z<B%z) ):
            print("No")
            return

        print("Yes")
        return
                
        #(x+n*y)%B==[C+1,B)となるnがあれば"No"

for i in range(T):
    juicecheck(i)


Measured memory_bytes: 3188
def main():
        N = int(input())
        S = str(input())

        S_list = list(S)

        r = 0; g = 0; b = 0

        for s in S_list:
                if s=="R": r += 1
                elif s=="G": g += 1
                else: b += 1

        sub = 0

        for i in range(N):
                for j in range(i+1,N):
                        if S_list[i]==S_list[j]:
                                continue
                        k = 2*j-i
                        if k>=N or S_list[k]==S_list[i] or S_list[k]==S_list[j]:
                                continue
                        sub += 1

        ans = r*g*b - sub

        print("{}".format(ans))


if __name__=="__main__":
        main()

Measured memory_bytes: 9232
n = int(input())
h = list(map(int, input().split()))

count = 0
maximum = 0
for i in range(n-1):
    if h[i] >= h[i+1]:
        count += 1
    else:
        maximum = max(count,maximum)
        count = 0
maximum = max(count,maximum)
print(maximum)

Measured memory_bytes: 64112
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO                     \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0);
typedef long long ll;
/**
 * Uncomment the #define below if problem contains multiple test cases
 */
// #define MULTIPLE_TESTS 1

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

template <typename T>
inline void readGrid(vector<vector<T>>& grid, int R, int C) {
  grid.assign(R, vector<T>(C));
  for (int i = 0; i < R; ++i) {
    for (int j = 0; j < C; ++j) {
      cin >> grid[i][j];
    }
  }
}

inline bool safeChecker(int x, int y, int R, int C) {
  if (x < 0 || y < 0 || x >= R || y >= C) {
    return false;
  }
  return true;
}

const ll MOD = 1e9 + 7;
void solve() {
  int h, w;
  cin >> h >> w;
  vector<vector<char>> grid;
  readGrid(grid, h, w);
  vector<vector<ll>> ways(h, vector<ll>(w, 0));
  ways[0][0] = 1;
  for (int r = 0; r < h; ++r) {
    for (int c = 0; c < w; ++c) {
      if (grid[r][c] == '#') {
        continue;  // no way to reach here
      }
      if (safeChecker(r - 1, c, h, w)) {
        ways[r][c] += ways[r - 1][c];
        ways[r][c] %= MOD;
      }
      if (safeChecker(r, c - 1, h, w)) {
        ways[r][c] += ways[r][c - 1];
        ways[r][c] %= MOD;
      }
    }
  }
  cout << ways[h - 1][w - 1] << endl;
}
int main() {
  FAST_IO;
  int t = 1;
#ifdef MULTIPLE_TESTS
  cin >> t;
#endif

  while (t--) {
    solve();
  }

  return 0;
}


Measured memory_bytes: 9088
import os
import math

def main():
    a,b,h,m = map(int, input().split())

    rand2 = 6 * m
    rand3 = (0.5 * m) + (30 * h)
    rand_result = 0.0

    if (abs(rand3 - rand2) <= 180):
        rand_result = abs(rand3 - rand2)
    else:
        rand_result = 360 - abs(rand3 - rand2)

    
    ans = math.sqrt(pow(a,2) + pow(b,2) - (2*a*b*math.cos(math.radians(rand_result))))
    print(format(ans,'.10f'))

if __name__ == "__main__":
    main()

Measured memory_bytes: 9528
S = list(input())
T = list(input())

mindiff = len(S)
for i in range(len(S) - len(T) +1):
    diff = 0
    for j in range(len(T)):
        if(S[i+j] != T[j]):
            diff += 1
        pass
    if(diff < mindiff):
        mindiff = diff

print(mindiff)





Measured memory_bytes: 9080
/* Great things never come from comfort zones,
"whatever the mind of a man can conceive and believe,it can achieve." */
 
#include <bits/stdc++.h>
#define ll long long
#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x)     x.begin(),x.end()
#define tc   int tt; scf(tt); while(tt--)
#define inf INT_MAX
#define ninf INT_MIN
#define gcd __gcd
#define bitcount(n) __builtin_popcount(n)
typedef double dd;
using namespace std;
const ll mod =1e9+7;
const int N = 2e5+7;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)


int main()
{
    
    int n;
    scf(n);
    
    int a[n];
    
    map<int,int>m;
   
    rep(i,0,n)
    {
        scf(a[i]);
        
        m[a[i]]++;
    }

        sort(a,a+n);
    
    int x=a[n-1];
    
    bool isPrime[2*x];
    
    rep(i,1,2*x)
    isPrime[i]=1;
    
    int ctr=0;
    
    rep(i,0,n)
    {
        if(isPrime[a[i]])
        for(int j=a[i];j<=a[n-1];j+=a[i])
        { 
            if(j!=a[i])
            isPrime[j]=0;
        }
        
    }

        rep(i,0,n)
        {
            if(isPrime[a[i]]&&m[a[i]]==1)
            ctr++;
        }
        
        prin(ctr);
}

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


using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define endl        '\n'
#define ll          long long int
#define pb          push_back
#define sz(x)       (int)(x).size()
const ll mod = 1e9 + 7;

ll gcd(ll a, ll b) {
if (b == 0)  return a;
return gcd(b , a % b);
}

ll powm(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1)
res = (res * 1LL * a) % mod;
b >>= 1LL;
a = (a * 1LL * a) % mod;
}
return res;
}

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



int main() {
	fast
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
 
int n,k;cin>>n>>k;
ll a[n];
for(int i=0;i<n;i++)cin>>a[i];
ll dp[n];
dp[0]=0;
for(int i=1;i<n;i++)
{
   if(i-1>=0){
		dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
	}
	for(int j=2;j<=k;j++)
	{
      if(i-j>=0)
	{
        dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
	}

	}
	
	
}	

cout<<dp[n-1];

	return 0;
}



Measured memory_bytes: 5208
n = int(input())
s = input()

ans = 0
for i in range(1000):
    flag = [False, False, False]
    st = str(i).zfill(3)
    a = s.find(st[0])
    if a != -1:
        b = s.find(st[1],a+1)
        if b != -1:
            c =s.find(st[2],b+1)
            if c != -1:
                ans += 1
print(ans)

Measured memory_bytes: 3064
/*********************
*  Author: xuziyuan  * 
*********************/

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL n,n2=1,d[2],a[100010],ne[2][100010],dp[100010][2],dat[400010];
vector <LL> v;

void INIT(int k,int lb,int ub)
{
	if(lb==ub) return;
	INIT(k*2+1,lb,(lb+ub)/2);
	INIT(k*2+2,(lb+ub)/2+1,ub);
	dat[k]=min(dat[k*2+1],dat[k*2+2]);
}

LL query(int k,int lb,int ub,int tlb,int tub)
{
	if(ub<tlb||tub<lb) return 1e18;
	if(tlb<=lb&&ub<=tub) return dat[k];
	return min(query(k*2+1,lb,(lb+ub)/2,tlb,tub),query(k*2+2,(lb+ub)/2+1,ub,tlb,tub));
}

int main()
{
	cin>>n>>d[0]>>d[1];
	rep(i,n) cin>>a[i];
	rep(i,n-1) v.pb(a[i+1]-a[i]);
	rep(i,2) rep(j,n-1)
	{
		int lb=j+1,ub=n-1,mid;
		while(lb<ub)
		{
			mid=(lb+ub)/2;
			if(a[mid]-a[j]>=d[i]) ub=mid;
			else lb=mid+1;
		}
		if(a[lb]-a[j]<d[i]) ne[i][j]=n;
		else ne[i][j]=(lb==j+1 ? lb+1:lb);
	}
	while(n2<n-1) n2*=2;
	while(v.size()<n2+5) v.pb(5e18);
	rep(i,n2) dat[i+n2-1]=v[i];
	dp[0][0]=dp[0][1]=1;
	INIT(0,0,n2-1);
	rep(i,n)
	{
		rep(j,2)
		{
			if(dp[i][j]==0) continue;
			if(a[i+1]-a[i]>=d[j]) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
			int nepos=ne[j][i];
			LL val=query(0,0,n2-1,i+1,nepos-2);
			if(val<d[j^1]) continue;
			dp[nepos-1][j^1]=(dp[nepos-1][j^1]+dp[i][j])%MOD;
		}
	}
	cout<<(dp[n-1][0]+dp[n-1][1])%MOD<<endl;
	return 0;
}

Measured memory_bytes: 8432
import java.io.*;
  
public class Main {
    public static void main(String[] args) {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        try {
            String[] str = br.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            if(a < b){
            System.out.println("a < b");
            }else if(a > b){
            System.out.println("a > b");
            }else{
            System.out.println("a == b");
            }
        } catch(IOException e) {
            e.printStackTrace();
        }
    }
}

Measured memory_bytes: 24360
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <climits>
#define REP(i, n) for(int i = 0; i < (n); i++)
using namespace std;

const int MAX_V = 100;
const int MAX_E = 1000000;
const int INF = INT_MAX;

struct E{
  int to, cost;
  E(int t, int c) : to(t), cost(c) {};
};
typedef pair<int, int> pii;

int v;
vector<E> g[MAX_V];
int dd[MAX_V];

void dijkstra(int s)
{
  fill(dd, dd + v, INF);
  dd[s] = 0;
  priority_queue<pii, vector<pii>, greater<pii> > q;
  q.push(pii(0, s));
  
  while(!q.empty()){
    pii p = q.top();
    q.pop();
    int from = p.second;
    if(dd[from] < p.first) continue;
    
    for(int i = 0; i < g[from].size(); ++i){
      int to = g[from][i].to;
      int cost = g[from][i].cost;
      
      if(dd[to] > dd[from] + cost){
        dd[to] = dd[from] + cost;
        q.push(pii(dd[to], to));
      }
    }
  }
}

int main()
{
  while(1){
    int n, k;
    scanf("%d %d", &n, &k);
    if(n == 0 && k == 0){
      break;
    }else{
      v = n;
      REP(i, k){
        int r, a, b, c, d, e;
        cin >> r;
        if(r){
          cin >> c >> d >> e;
          g[c - 1].push_back(E(d - 1, e));
          g[d - 1].push_back(E(c - 1, e));
        }else{
          cin >> a >> b;
          dijkstra(a - 1);
          if(dd[b - 1] == INF)
            cout << "-1" << endl;
          else
            cout << dd[b - 1] << endl;
        }
      }
      REP(i, MAX_V)
        g[i].clear();
    }
  }
}

Measured memory_bytes: 1280
n,m,d=list(map(int,input().split()))

def sum(a,b):
    return (a+b)*(a+b+1)/2

def calc_between(n):
    if d==0:
        return n
    ans=n
    if 2*d+1<=n:
        ans+=(n-2*d)
    return ans

x=calc_between(n)
print((m-1)*x/n**2)

Measured memory_bytes: 3060
import heapq
import sys

a=[1,2,3,4,5,6,7,8,9]
heapq.heapify(a)

k = int(input())

if k<10:
  print(k)
  sys.exit()

ans = 9

while True:
  x = heapq.heappop(a)
  # print(a)
  if x%10 ==0:
    for i in [0,1]:
      y = x*10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)
  elif x%10 == 9:
    for i in [-1,0]:
      y = x*10 + x%10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)
  else:
    for i in [-1,0,1]:
      # print(i)
      y = x*10 + x%10 + i
      ans += 1
      if ans == k:
        print(y)
        sys.exit()
      heapq.heappush(a,y)

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

ll gcd(ll a,ll b){
  while(b!=0){
    a%=b;
    swap(a,b);
  }
  return a;
}

ll kaizyou(ll N){
  ll num=1;
  for(ll i=1;i<=N;i++){
  num*=i;
  }
  return num;
}

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

int cnt[10][10]={};

int main(){
  int N;
  cin >> N;
  int ans=0;
  for(int i=1;i<=N;i++){
    int num=i;
    while(num%10!=num){
      num/=10;
    }
    cnt[num][i%10]++;
  }
  for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
      ans+=cnt[i][j]*cnt[j][i];
    }
  }
  cout << ans << endl;
}
      
  
  
  

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close(); 
		for (int i = 1; i <= 9; i++) {
			if (n % i == 0 && n / i < 10) {
				System.out.println("Yes");
				System.exit(0);
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 24020
k, n = map(int , input().split())
lis = list(map(int,input().split()))
mi = [min(lis)] * n
li = [x - y for (x, y) in zip(lis, mi)]

li.append(k)
ans = list()
for i in range(n):
  ans.append(abs(li[(i + 1)] - li[i]))
print(k - max(ans))

Measured memory_bytes: 26444
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    int N;
    while (cin >> N) {
        vector<string> a(N);
        for (int i=0; i<N; ++i) cin >> a[i];
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());

        if ((int)a.size() == 1) {
            cout << "Yes" << endl;
            continue;
        }

        vector<int> deg(7, 0);
        vector<bool> has(7, false);
        for (int i=0; i<(int)a.size(); ++i) {
            if (a[i][0] != a[i][1]) {
                deg[a[i][0]-'0'] ++;
                deg[a[i][1]-'0'] ++;
            }
            has[a[i][0]-'0'] = true;
            has[a[i][1]-'0'] = true;
        }

        int odd = 0;
        bool bad = false;
        for (int i=0; i<7; ++i) {
            if (deg[i] % 2 == 1) odd ++;
            if (has[i] && deg[i] == 0) bad = true;
        }
        cout << (!bad && (odd == 2 || odd == 0) ? "Yes" : "No") << endl;
    }
    return 0;
}

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

constexpr int MAX = 1000001;

int main() {
    int X, Y;
    while(cin >> X >> Y, X) {
        vector<vector<int>> c(Y+1, vector<int>(X));
        for(int i=0; i<Y; ++i) {
            for(int j=0; j<X; ++j) {
                cin >> c[i][j];
            }
        }
        vector<vector<int>> dp(Y+1, vector<int>(X));
        for(int i=0; i<X; ++i) {
            dp[0][i] = c[0][i] == 0;
        }
        for(int i=0; i<Y-1; ++i) {
            for(int j=0; j<X; ++j) {
                if(c[i][j] == 1) {
                    continue;
                } else if(c[i][j] == 2) {
                    dp[i+2][j] += dp[i][j];
                } else {
                    int dx[3] = {-1, 0, 1};
                    for(int k=0; k<3; ++k) {
                        int nx = j + dx[k];
                        if(nx < 0 || X <= nx || dx[k] != 0 && c[i+1][nx] == 2) {
                            continue;
                        }
                        dp[i+1][nx] += dp[i][j];
                    }
                }
            }
        }
        int res = 0;
        for(int i=0; i<2; ++i) {
            for(int j=0; j<X; ++j) {
                if(c[Y-1+i][j] != 1) {
                    res += dp[Y-1+i][j];
                }
            }
        }
        cout << res << endl;
    }
}


Measured memory_bytes: 3116