akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

#define EPS (1e-7)

int main() {
  char a;
  cin >> a;
  char ans = 'A';
  if (a <= 'z' && a >= 'a') {
    ans = 'a';
  }

  cout << ans << endl;
  return 0;
}




Measured memory_bytes: 3588
n=int(input())
s=input()
a=0
i=0
j=1
while j<n:
	if s[i:j] in s[j:]:
		a=max(a,len(s[i:j]))
		j+=1
	else:
		i+=1
	if i==j:
		i+=1
		j+=2
print(a)

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
#include <cassert>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <deque>

using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const int MAXN = 123456;
vector<pll> G[MAXN][2];
bool visit[MAXN];
LL dis[MAXN][2], ans[MAXN];

void solve(int s, int md) {
     priority_queue<pll, vector<pll>, greater<pll>> pq;
     memset(visit, 0, sizeof(visit));
     pq.push(make_pair(0, s));
     while (!pq.empty()) {
           auto tp = pq.top();
           pq.pop();
           LL cur = tp.second, cost = tp.first;
           if (visit[cur]) continue;
           visit[cur] = 1;
           dis[cur][md] = cost;
           //printf("cur = %lld md = %d dis = %lld\n", cur, md, dis[cur][md]);
           for (auto i : G[cur][md]) {
               pq.push(make_pair(cost + i.second, i.first));
           }
     }
}

int main() {
    int n, m, s, t;
    scanf("%d %d %d %d", &n, &m, &s, &t);
    for (int i = 0; i < m; i++) {
        int x, y;
        LL a, b;
        scanf("%d %d %lld %lld", &x, &y, &a, &b);
        G[x][0].push_back(make_pair(y, a));
        G[y][0].push_back(make_pair(x, a));
        G[x][1].push_back(make_pair(y, b));
        G[y][1].push_back(make_pair(x, b));
    }
    solve(s, 0);
    solve(t, 1);
    ans[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
        LL cur = dis[i][0] + dis[i][1];
        ans[i] = max(ans[i + 1], (LL)1e15 - cur);
    }
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}


Measured memory_bytes: 26032
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <set>

using namespace std;

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

   int ans = 1 ;
   int idx ;
   for (int i = 0; i < s.size(); i++)
   {
       if(s[i]=='A'){
           idx = i ;
           break ;
       }
   }
   
   int idxe = s.size()-1 ;
   while (1)
   {
       if(s[idxe]=='Z') break ;
        idxe-- ;
   }

 cout << idxe-idx+1 << endl ;

  return 0 ;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k; cin >> n >> k;
    bool dislike[10] = {};
    for(int i = 0; i < k; i++)
    {
        int d; cin >> d;
        dislike[d] = true;;
    }
    for(int x = n; x <= 100000; x++)
    {
        string s = to_string(x);
        bool NotContain = false;
        for(int i = 0; i < s.size(); i++)
        {
            if(dislike[s[i] - '0']) NotContain = true;
        }
        if(NotContain == false)
        {
            cout << x << endl;
            return 0;
        }
    }
    return 0;
}



Measured memory_bytes: 256
def solve():
    A, B, C, D, E, F = map(int, input().split())

    waters = set()
    for i in range((30 + A - 1) // A + 1):
        for j in range((30 + B - 1) // B + 1):
            a = 100 * (i * A + j * B)
            if a > F or a == 0:
                continue
            waters.add(a)

    sugars = set()
    for k in range((3000 + C - 1) // C + 1):
        for l in range((3000 + D - 1) // D + 1):
            b = k * C + l * D
            if b > F:
                continue
            sugars.add(b)

    max_density = -1
    ans = [-1, -1]
    for w in waters:
        for s in sugars:
            if w + s > F or w // 100 * E < s:
                continue
            density = 100 * s / (w + s)
            if density > max_density:
                ans = [(w + s), s]
                max_density = density
    return ans


print(*solve())


Measured memory_bytes: 9204
#文字入力
str = input() 

#文字列の長さ取得
str_leg = len(str)

#判定

count = 0
#(0,1)(0,2)(0,3)(1,2)(1,3)(2,3)
for i in range(0, str_leg - 1):
    for j in range(i+1, str_leg):
        if (str[i] == str[j]):
             count = count + 1 

if(count == 2):
    print("Yes")
else:
     print("No")

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

#define MAX_LEN_W (100)

int main(int argc, char *argv[]) {
  int cnt[26] = {}, len = 0;
  char w[MAX_LEN_W];
  for (char c = fgetc(stdin); c >= 'a' && c <= 'z'; c = fgetc(stdin))
    w[len++] = c;
  for (int i = 0; i < len; i++)
    cnt[w[i] - 'a']++;
  for (int i = 0; i < 26; i++) {
    if (cnt[i] % 2 == 1) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  
  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		for (int x = 1; x <= n; x++) {
			int tmp = x + x * 8 / 100;
			if (tmp == n) {
				System.out.println(x);
				return;
			}
		}
		
		System.out.println(":(");
	}
}


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

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

    int kmax = (N-1)*(N-2)/2;

    if( kmax < K ){
        cout << -1 << endl;
        return 0;
    }

    M = (N-1) + ( kmax - K );

    cout << M << endl;

    for(int i=2; i<=N; i++){
            cout << 1 << " " << i << endl;
    }

    int count = 0;

    for(int i=2; i<N; i++){
        for(int j=i+1; j<=N; j++){
            if( count >= kmax - K ) break;
            cout << i << " " << j << endl;
            count++;
        }
        if( count >= kmax - K ) break;
    }

   return 0; 
}

Measured memory_bytes: 3600
#include <stdio.h>
#define N 200005

char s[N] = {0}, t[N] = {0}, *p, *q;
int main()
{
    int cnt = 0;
    scanf("%s%s", s, t);
    p = s; q = t;
    while(*p && *q)
        if(*p++ != *q++) 
            cnt++;
    printf("%d\n", cnt);

    return 0;
}

Measured memory_bytes: 2084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)


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

  int n;
  cin >> n;
  int l[n];
  const int l_max=1e3+1;
  int lc[l_max];
  rep(i,l_max) lc[i]=0;
  rep(i,n){
    cin >> l[i];
    lc[l[i]]++;
  }
  sort(l,l+n);
  ll ans=0;
  rep(i,n-2){
    for(int j=i+1; j<n-1; j++){
      int b=l[i]+l[j];
      int ind=lower_bound(l,l+n,b) - l - 1;
      /*      if(l[ind]==l[j]){
	ans+=max(ind-j+1,0);
      }
      else{
	ans+=max(ind-j,0);
	}*/
      //      cout << "i j " << i << " " << j <<  " " << ind << endl;
      ans+=max(ind-j,0);
    }
  }
  cout << ans << endl;

  
  return 0;
    

}


Measured memory_bytes: 256
import heapq
K = int(input())


def fun(h, n):
    tmp = str(n)
    if tmp[-1] == '0':
        heapq.heappush(h, int(tmp + '0'))
        heapq.heappush(h, int(tmp + '1'))
    elif tmp[-1] == '9':
        heapq.heappush(h, int(tmp + '8'))
        heapq.heappush(h, int(tmp + '9'))
    else:
        heapq.heappush(h, int(tmp + str(int(tmp[-1]) - 1)))
        heapq.heappush(h, int(tmp + tmp[-1]))
        heapq.heappush(h, int(tmp + str(int(tmp[-1]) + 1)))


h = list(range(1, 10))
while K > 0:
    tmp = heapq.heappop(h)
    fun(h, tmp)
    K -= 1
else:
    print(tmp)

Measured memory_bytes: 10740
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>

int isPrime(long n) {
  if (n== 2) return 1;
  else if ((n > 2) && (n % 2)) {
    long i = 3;
    long m = (long)sqrt(n);
    while (i <= m) {
      if(n % i) i+=2;
      else	return 0;
    }
    return 1;
  }
  return 0;
}

long nPrime(long Ns, long Ne){
  long n;
  long t=0;
  for(n=Ns;n<=Ne;n++) {
    t = t + isPrime(n);
  }
  return (t);
}

void ls(long *a,long *b){
  long i=*a;*a=*b;*b=i;
}

struct _N {
  long o;
  long v;
  long p;
} N[32];

void sS(struct _N *A, long a){
  long i,j;
  for(i=0;i<a;i++){
    long m=i;
    for(j=i;j<a;j++)
      if(A[j].v<A[m].v)
	m=j;
    if(A[i].v!=A[m].v)
      ls(&A[i].v,&A[m].v);
      ls(&A[i].o,&A[m].o);
      ls(&A[i].p,&A[m].p);
  }
}

int main(void){
  long P1[32];
  int n,i;
  for(n=0;n<32;n++) P1[n]=0;
  n=1;
  while (scanf("%ld\n",&N[n].v)!=EOF) {
    N[n].o = n;
    n++;
  }
  N[0].v=1; N[0].o = 0; N[0].p = 0;

  sS(N,n);
   for(i=1;i<=n;i++){
     N[i].p = N[i-1].p + nPrime(N[i-1].v+1, N[i].v);
   }
   for(i=1;i<n;i++) {
     int j;
     for(j=1;j<n;j++) 
       if (N[j].o == i)
	 printf("%ld\n",N[j].p);
   }
  return 0;
}

Measured memory_bytes: 600
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
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

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
const int dm = 1 << 21;
char dn[dm], * di = dn;
inline void putint2(int X) {
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}
inline void putint(ll X) {
	int keta = 0;
	char C[20];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}

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

	pair<int, int> LR[200000];
	int T = getint();
	rep(t, T) {
		int N = getint();

		if (N <= 2) {
			int k = getint(), l = getint(), r = getint();
			if (N == 1) putint2(l);
			else if (k == 2) {
				int k2 = getint(), l2 = getint(), r2 = getint();
				if (k2 == 2) putint2(l + l2);
				else putint2(l + max(l2, r2));
			}
			else {
				int k2 = getint(), l2 = getint(), r2 = getint();
				if (k2 == 2) putint2(l2 + max(l, r));
				else putint2(max(l + r2, l2 + r));
			}
			continue;
		}

		ll saishou = 0;
		int k1 = 0, k2 = N;
		rep(i, N) {
			int k = getint(), l = getint(), r = getint();

			if (l < r) {
				LR[--k2] = mp(k + 1, r - l);
				saishou += l;
			}
			else {
				LR[k1++] = mp(k, l - r);
				saishou += r;
			}
		}
		sort(LR, LR + k1);
		sort(LR + k1, LR + N);

		priority_queue<int> PQ;
		int i = k1;
		while (i < N && LR[i].first < k1) {
			PQ.push(LR[i++].second);
		}
		for (int j = k1; j <= N; j++) {
			while (i < N && LR[i].first <= j) {
				PQ.push(LR[i++].second);
			}
			if (PQ.size()) {
				auto q = PQ.top();
				PQ.pop();
				saishou += q;
			}
		}
		PQ = priority_queue<int>();
		i = k1 - 1;
		while (i >= 0 && LR[i].first > k1) {
			PQ.push(LR[i--].second);
		}
		for (int j = k1 - 1; j >= 0; j--) {
			while (i >= 0 && LR[i].first > j) {
				PQ.push(LR[i--].second);
			}
			if (PQ.size()) {
				auto q = PQ.top();
				PQ.pop();
				saishou += q;
			}
		}
		putint(saishou);
	}

	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

Measured memory_bytes: 5488
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
int a,b,c,d,ans1,ans2,ans3,ans4;
signed main(){
	cin>>a>>b>>c>>d;
	ans1=a*c;ans2=a*d;ans3=c*b;ans4=b*d;
	ans1=max(ans1,ans2);ans1=max(ans1,ans3);
	ans1=max(ans1,ans4);
	cout<<ans1<<endl;
	return 0;
} 

Measured memory_bytes: 3632
#include <stdio.h>

int main(void) {
  char a[10];
  scanf("%s", &a);

  char b[10];
  scanf("%s", &b);

  if (a[0] == b[2] && a[1] == b[1] && a[2] == b[0]) printf("YES");
  else {
    printf("NO");
  }

  return 0;
}


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

int main() {
	int n;
	cin >> n;
	vector<string> s(n);
	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i] >> p[i];
	}
	vector<int> ans(n);
	for (int i = 0; i < n; i++) {
		ans[i] = 0;
	}
	for (int i = 0; i < n; i++) {
		string name = "zzzzzzzzzz";
		int point = 0;
		for (int j = 0; j < n; j++) {
			if(p[j] != 101 && s[j] < name){
				ans[i] = j+1;
				name = s[j];
				point = p[j];
			}
			else if(p[j] != 101 &&s[j]==name && point < p[j]) {
				ans[i] = j+1;
				name = s[j];
				point = p[j];
			}
		}
		p[ans[i]-1] = 101;
	}
	for (int i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}
}


Measured memory_bytes: 256
from collections import deque

n, m = map(int, input().split())
links = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].append(b)
    links[b].append(a)

ans = [-1] * n
ans[0] = 0
q = deque([(0, 0)])
while q:
    room, prev = q.popleft()
    for next_ in links[room]:
        if ans[next_] < 0:
            ans[next_] = room
            q.append((next_, room))

print('Yes')
for i in range(1, n):
    print(ans[i] + 1)

Measured memory_bytes: 38040
#include<bits/stdc++.h>
using namespace std;
const int N=1011;
char s[N],t[N];
int n,m;
int main(){
	cin>>s>>t;
	n=strlen(s);
	m=strlen(t);
	int i,j,ans=m;
	for(i=0;i+m<n+1;++i){
		int u=0;
		for(j=0;j<m;++j)
			u+=t[j]!=s[i+j];
		ans=min(ans,u);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>
#include <functional>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template<typename T> using VT = vector<T>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define EB emplace_back
#define GREATER(T) T, VT<T> greater<T>
template<typename T> inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

const int MAX = 1e5 + 10;
int N, M;
VT<pair<int, LL>> G[MAX];
LL dist[MAX];

int main(void) {
    cin >> N >> M;
    REP(i, N - 1) {
        G[i + 1].EB(i, 0);
    }
    REP(i, M) {
        int l, r, c;
        cin >> l >> r >> c;
        l--; r--;
        G[l].EB(r, c);
    }

    fill(dist, dist + MAX, LLINF);

    priority_queue<pair<LL, int>, VT<pair<LL, int>>, greater<pair<LL, int>>> pq;
    pq.emplace(0, 0);
    dist[0] = 0;
    while (!pq.empty()) {
        const auto cur = pq.top();
        pq.pop();
        if (dist[cur.second] < cur.first) continue;

        FORE(nxt, G[cur.second]) {
            const auto nxt_cost = cur.first + nxt.second;
            if (nxt_cost < dist[nxt.first]) {
                dist[nxt.first] = nxt_cost;
                pq.emplace(nxt_cost, nxt.first);
            }
        }
    }

    cout << (dist[N - 1] == LLINF ? -1 : dist[N - 1]) << endl;
}


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

#define INF 0x7fffffffffffff

typedef long long int LLI;

int N;
LLI as[314514];
LLI lsum[314514];
LLI rsum[314514];

int main() {
  scanf("%d", &N);
  for (int i=0; i<3*N; i++) {
    scanf("%lld", &as[i]);
  }

  multiset<LLI> st;
  for (int i=0; i<N; i++) {
    st.insert(as[i]);
    lsum[0] += as[i];
  }

  for (int i=N; i<N*2; i++) {
    st.insert(as[i]);
    lsum[i-N+1] = lsum[i-N] + as[i] - *st.begin();
    st.erase(st.begin());
  }

  st.clear();
  for (int i=2*N; i<3*N; i++) {
    st.insert(as[i]);
    rsum[N] += as[i];
  }

  for (int i=N*2-1; i>=N; i--) {
    st.insert(as[i]);
    rsum[i-N] = rsum[i-N+1] + as[i] - *st.rbegin();
    st.erase(next(st.rbegin()).base());
  }

  LLI ans = -INF;
  for (int i=0; i<=N; i++) {
    ans = max(ans, lsum[i] - rsum[i]);
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 10880
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    int n;
    cin >> n;
    int ans = 0;
    for(int a = 1; a <= n; a++){
        int b = (n - 1) / a;
        ans += b;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    vector<bool>issafe;
    cin >> N >> M;
    issafe.assign(N+1,true);
    for(int i=0; i<M; ++i){
        int a; cin >> a;
        issafe.at(a) = false;
    }

    vector<int> dp(N+1,0);
    
    dp[0] =1;
    if(issafe[1]) dp[1] =1;

    for(int n=2; n <=N; ++n){
        if(issafe[n-1]) dp[n] += dp[n-1];
        if(issafe[n-2]) dp[n] += dp[n-2];
        dp[n] %= 1000000007;
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>

using namespace std;

string
caesar (string str, int n)
{
  const string table = "abcdefghijklmnopqrstuvwxyz";
  string ans (str.length (), ' ');
  for (int i = 0; i < str.length (); i++)
    {
      int buf = table.find (str[i]);
      if (buf == string::npos)
	{
	  ans[i] = str[i];
	}
      else
	{
	  ans[i] = (buf + n < table.length ())? table[buf + n]
	    : table[buf + n - table.length ()];
	}
    }
  return ans;
}

int
main ()
{
  string str;
  while (getline (cin, str))
    {
      string after;
      for (int i = 0; i <= 25; i++)
	{
	  after = caesar (str, i);
	  if (after.find ("the") != string::npos)
	    break;
	  if (after.find ("this") != string::npos)
	    break;
	  if (after.find ("that") != string::npos)
	    break;
	}
      cout << after << endl;
    }
}

Measured memory_bytes: 1192
import numpy as np
N,D = list(map(int, input().split()))
x = [input().split() for i in range(N)]
f = np.vectorize(int)
x = f(x)
ans =0
for i in range(N):
    j = i+1
    while j < N:
        sum = 0
        for k in range(D):
            sum += (x[i][k]-x[j][k])**2
        sum = sum**(0.5)
        if sum == int(sum):
            ans += 1
            
        j+=1
print(ans)


Measured memory_bytes: 12472
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int t0 = 0;
    int x0 = 0;
    int y0 = 0;
    REP(i, n) {
        int t1, x1, y1;
        cin >> t1 >> x1 >> y1;
        int judge = t1 - t0 - abs(x1 - x0) - abs(y1 - y0);
        if(judge < 0 or judge % 2 == 1) {
            cout << "No" << endl;
            return 0;
        }
        t0 = t1;
        x0 = x1;
        y0 = y1;
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <stdio.h>

using namespace std;

#define ll long long
#define ld long double
#define v vector

#define rep(i, n)      for (int i = 0; i < (int)(n); ++i)
#define rep3(i, m, n)  for (int i = (m); i < (int)(n); ++i)
#define rrep(i, n)     for (int i = (int)(n)-1; i >= 0; --i)
#define rrep3(i, m, n) for (int i = (int)(n)-1; i >= (m); --i)
#define all(x) x.begin(), x.end()
#define rall(x) x.end(x), x.begin()

#define endl '\n'
const string YES = "Yes";
const string NO = "No";

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

bool solve(string S, string T) {
    T.pop_back();
    if (S == T) return true;
    else return false;
}

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

    string S, T;
    cin >> S >> T;

    auto ans = solve(S, T);
    cout << (ans ? YES : NO) << endl;

    return 0;
}


Measured memory_bytes: 3580
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		
		int []x = new int [n];
		int []y = new int [n];
		
		for(int i = 0 ; i < n ;i++) {
			x[i]= sc.nextInt();
			y[i]= sc.nextInt();
		}
		
		double sum = 0;
		

		int nn = 1;
		for(int i = 1 ; i <= n ; i++) {
			nn *= i;
		}
		
		for(int i = 0 ; i < n ; i++) {
			for(int j = i+1 ; j < n ; j++) {
				
				double a = Math.pow(x[i] - x[j],2) + Math.pow(y[i] - y[j], 2);
				double p= Math.sqrt(a);
				sum += 2 * nn/n * p;
			}
		}
		
		
		
		double ans =  (double) (sum / nn);
		
		
		System.out.println(ans);
		
		
	}

}


Measured memory_bytes: 21716
#include<stdio.h>
#define NUM 1000

int main(){
   int n,m,i,total,cnt=0,a[NUM];
   double limit;
   scanf("%d %d",&n,&m);
   for(i=0;i<n;i++){
      scanf("%d",&a[i]);
   }
   for(i=0;i<n;i++){
      total+=a[i];
   }
   limit=total/(4.0*m);
   for(i=0;i<n;i++){
      if(a[i]>=limit){
         cnt++;
      }
   }
   if(cnt>=m){
      printf("Yes");
   }else{
      printf("No");
   }
   return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
#define int long long

using namespace std;

int k;

int qpow(int a, int b, int modd) {
    int ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % modd;
        b >>= 1, base = base * base % modd;
    }
    return ans;
}

inline void work() {
    cin >> k;
    for (int i = 1; i <= 2e6; i++) {
        if ((7 * (qpow(10, i, 9 * k) - 1) % (9 * k) + (9 * k)) % (9 * k) == 0) {
            cout << i;
            exit(0);
        }
    }
    cout << -1 << endl;
}

signed main() {
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    work();
    return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
int main()
{
  int h,w,ss=0,c[55][55]={};
  char s[55][55];
  queue<int> q;
  cin>>h>>w;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){
      cin>>s[i][j];
      if(s[i][j]=='#')
        ss++;
    }
  c[0][0]=1;
  q.push(0);
  q.push(0);
  while(!q.empty()){
    int xx=q.front();
    q.pop();
    int yy=q.front();
    q.pop();
    if(xx>0)
      if(s[xx-1][yy]!='#'&&c[xx-1][yy]==0){
        c[xx-1][yy]=c[xx][yy]+1;
        q.push(xx-1);
        q.push(yy);
      }
    if(xx<h-1)
      if(s[xx+1][yy]!='#'&&c[xx+1][yy]==0){
        c[xx+1][yy]=c[xx][yy]+1;
        q.push(xx+1);
        q.push(yy);
      }
    if(yy>0)
      if(s[xx][yy-1]!='#'&&c[xx][yy-1]==0){
        c[xx][yy-1]=c[xx][yy]+1;
        q.push(xx);
        q.push(yy-1);
      }
    if(yy<w-1)
      if(s[xx][yy+1]!='#'&&c[xx][yy+1]==0){
        c[xx][yy+1]=c[xx][yy]+1;
        q.push(xx);
        q.push(yy+1);
      }
  }
  if(c[h-1][w-1]!=0)
    cout<<h*w-c[h-1][w-1]-ss;
  else
    cout<<"-1";
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    
    int a, b, c;
    
    
    
    Scanner sc = new Scanner(System.in);
	a = sc.nextInt();
    b = sc.nextInt();
    
    c = 2 * b;
    if (c > a) {
      c = a;
    }
    
    
    
    System.out.println(a - c);
    
    return;
  }
}

    
    
    

Measured memory_bytes: 23636
#include <cstdio>

const int MAXN=200005;

int main()
{
    int n,x;
    int p[MAXN],ans[MAXN];

    for (int i=0;i<MAXN;++i)
    {
        p[i]=MAXN-1;
        ans[i]=0;
    }

    scanf("%d",&n);
    for (int i=0;i<n;++i)
    {
        scanf("%d",&x);
        if (i==0) ans[i]=1;
        else ans[i]=ans[i-1]+ans[p[x]]*(p[x]!=i-1);
        ans[i]%=1000000007;
        p[x]=i;
    }
    printf("%d",ans[n-1]);

    return 0;
}


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

#define MOD (1000000000+7)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)
// template starts
typedef long long int ll;
ll fact(ll n, ll p){
	ll ans = 1;
	for(ll i = 1; i <= n; i++){
		ans *= i;
		ans %= p;
	}
	return ans;
}
ll power(ll x, ll n, ll p){
	ll res = 1;
	if(n == 1) return x%p;
	if(n%2 == 1) res = x%p;

	ll temp = power(x,n/2,p);
	return res*((temp*temp)%p)%p;
}
ll inv(ll a, ll p){
	return power(a,p-2,p);
}
ll nCr(ll n, ll r, ll p){
	if(r > n) return 0;
	ll t1 = fact(n,p);
	ll t2 = inv(fact(r,p),p);
	ll t3 = inv(fact(n-r,p),p);

	return (((t1*t2)%p)*t3)%p;
}
vector<vector<ll> > multiply(vector<vector<ll> > &a, vector<vector<ll> > &b, ll p){
	int r1,c1,r2,c2;
	r1 = a.size(); c1 = a[0].size();
	r2 = b.size(); c2 = b[0].size();

	vector<vector<ll> > result(r1,vector<ll>(c2,0));

	if(c1 != r2) return result;

	for(int i = 0; i < r1; i++){
		for(int j = 0; j < c2; j++){
			for(int k = 0; k < c1; k++){
				result[i][j] += a[i][k]*b[k][j];
				result[i][j] %= p;
			}
		}
	}
	return result;
}

vector<vector<ll> > power(vector<vector<ll> >&a,ll n, ll p){
	int r = a.size();
	vector<vector<ll> > result(r,vector<ll>(r,0));
	for(int i = 0; i < r; i++) result[i][i] = 1;

	while(n > 0){
		if(n%2 == 1){
			result = multiply(result,a,p);
		}
		n /= 2;
		a = multiply(a,a,p);
	}
	return result;
}
// template ends here

void solve(){
	// code starts from here
	ll N, K;
	cin >>N >> K;
	ll ans = 0;
	for(ll i = K; i <= N+1; i++){
		ll t= N+2-i;
		ll temp = t + (t-1)*(i-1);
		ans += temp;
		ans %= MOD;
	}
	cout << ans << endl;
}

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

	int T;
	T = 1;
	while(T--){
		solve();
	}

	return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <bitset>
#include <fstream>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
	int N, L;
	
	cin>>N>>L;

	vector<int> icicle(N);

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

	//ツ堕敖嘉陳づ可堕ォツつオツ堕アツつッツづゥ
	ll res = 0, buf = L - icicle[0];
	for(int i = 1; i < N; i++){
		if(icicle[i-1] >= icicle[i]){
			res = max(res, buf);
			buf = 0;
		}
		
		buf += L - icicle[i];
		
		if(i == N-1){
			if(icicle[i-1] >= icicle[i])
				res = max(res, (ll)icicle[i]);
			else
				res = max(res, buf);
		}
	}

	//ツ個クツ渉ュツ陳づ可堕ォツつオツ堕アツつッツづゥ
	buf = L - icicle[0];
	for(int i = 1; i < N; i++){
		if(icicle[i-1] <= icicle[i]){
			res = max(res, buf);
			buf = 0;
		}
		
		buf += L - icicle[i];
		
		if(i == N-1){
			if(icicle[i-1] <= icicle[i])
				res = max(res, (ll)icicle[i]);
			else
				res = max(res, buf);
		}
	}

	cout<<res<<endl;
	//cin.sync(); cin.get();
}

Measured memory_bytes: 1248
#include <bits/stdc++.h>
using namespace std;
const int INF = (int)1e9;

int n;

int points[100001][3];
int memo[100001][3];

int dp (int day, int prvTask) { // 0, 1, 2 for A, B, C resp
	if (day == n)
		return 0;
	if (memo[day][prvTask] != -1)
		return memo[day][prvTask];
	int ans = -INF;
	for (int i = 0; i < 3; i++) {
		if (i == prvTask)
			continue;
		if (points[day][i] + dp(day + 1, i) > ans) {
			ans = points[day][i] + dp(day + 1, i);
		}
	}
	memo[day][prvTask] = ans;
	return memo[day][prvTask];
}

int main () {
	int a, b, c;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> points[i][0] >> points[i][1] >> points[i][2];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			memo[i][j] = -1;
	a = dp(0, 0);
	b = dp(0, 1);
	c = dp(0, 2);
	cout << max(a, max(b, c)) << "\n";
	return 0;
}

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

int d[3005][3005];bool e[3005][3005];
int a,b,c;
signed main(){
   while(cin>>a>>b>>c,a|b|c){
       memset(d,0,sizeof(d));
       memset(e,false,sizeof(e));
   for(int f=0;f<a;f++){
       for(int g=0;g<b;g++){
	   scanf("%d",&e[f][g]);
	   }
       }
       d[0][0]=c-1;
       for(int h=0;h<a+b-1;h++){
	   for(int i=0;i<=h;i++){
	       int x=i,y=h-i;
	       if(d[x][y]&1){
		   if(e[x][y]){
		       d[x+1][y]+=d[x][y]/2;d[x][y+1]+=d[x][y]/2+1;
		       }
		   else {
		       d[x+1][y]+=d[x][y]/2+1;d[x][y+1]+=d[x][y]/2;
		       }
		   }
		else {d[x+1][y]+=d[x][y]/2;d[x][y+1]+=d[x][y]/2;}
		e[x][y]=(e[x][y]+d[x][y])&1;
	       }
	   }
	int x=0,y=0;
	while(1){
	    if(x==a||y==b){cout<<x+1<<" "<<y+1<<endl;break;}
	    if(e[x][y])y++;
	    else x++;
	    }
	}
    }

Measured memory_bytes: 47160
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy_dx0 = [[0,1],[1,0],[0,-1],[-1,0]] 
    dy_dx1 = [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0
 
    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            ny = p[0] + dy_dx0[i][0]
            nx = p[1] + dy_dx0[i][1]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] > d[p[0]][p[1]]:
                que.appendleft((ny,nx))
                d[ny][nx] = d[p[0]][p[1]]

        for i in range(20):
            ny = p[0] + dy_dx1[i][0]
            nx = p[1] + dy_dx1[i][1]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1 
 
    return d[gy][gx]

h, w = MAP()
sy, sx = MAP1()
gy, gx = MAP1()
s = [input() for _ in range(h)]
ans = bfs()
if ans == inf:
    print(-1)
else:
    print(ans)


Measured memory_bytes: 98680
import java.util.Arrays;
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int T=sc.nextInt();
		long time=0;
		int[] line=new int[N];
		for(int i=0; i<N; i++) {
			line[i]=sc.nextInt();
		}
		Arrays.sort(line);

		for(int i=0; i<N-1; i++) {
			time+=Math.min(line[i+1]-line[i], T);
		}
		time+=T;
		System.out.println(time);
	}
}

Measured memory_bytes: 87748
# coding: utf-8
#-------------------------------------------------------------------
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------
import math
def prm(n, r):
	return math.factorial(n)//math.factorial(n-r)

def cmb(n, r):
	return prm(n, r)//math.factorial(r)
#-------------------------------------------------------------------
def v(k):
	#p("B-1, k-1, cmb", B-1, k-1, cmb(B-1, k-1))
	p("R, k, cmb(R, k)",R, k, cmb(R, k))
#-------------------------------------------------------------------
MOD = 10**9+7
#-------------------------------------------------------------------


N, K = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

B=K
R=N-K


def calc(i):
	r = cmb(R+1, i)
	b = cmb(B-1, i-1)
	return (r * b) % MOD

for i in range(1,K+1):
	if R+1>=i:
		print( calc(i) )
	else:
		# R<=i, i>=R
		print(0)




Measured memory_bytes: 3316
#include<cstdio>
int a[1000001],b[1000001];
int main(){
    int n,m,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        int st,ed;
        scanf("%d%d",&st,&ed);
        if(st==1)a[ed]=1;
        if(ed==n)b[st]=1;
    }
    for(i=1;i<=m;i++)
        if(a[i]&&b[i]){
            printf("POSSIBLE\n");return 0;
        }
    printf("IMPOSSIBLE\n");
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 266666;
int n,m,v,p,a[N];
bool ck(int pos){
	int cnt=0;ll need=1ll*m*(v-(n-pos+1));
	per(i,pos-1,1)
		if(a[i]>a[pos]+m)cnt++,need-=m;
		else need-=a[pos]+m-a[i];
	rep(i,1,pos-1)if(need>0&&a[i]<=a[pos]+m)cnt++,need-=m-(a[pos]+m-a[i]);
//	rep(i,1,pos-1)cnt+=a[i]+(i<=v-(n-pos+1)?m:0)>a[pos]+m;
	return cnt<p;
}
int main() {
	read(n);read(m);read(v);read(p);
	rep(i,1,n)read(a[i]);sort(a+1,a+n+1);reverse(a+1,a+n+1);
	int res=p,l=p+1,r=n;
	while(l<=r){
		int mid=(l+r)>>1;
		if(ck(mid))res=mid,l=mid+1;else r=mid-1;
	}cout<<res;
	return 0;
}


Measured memory_bytes: 640
s=[]
s = input()
cnt=0
 
if(s[0] == s[1]):
    cnt+=1

if(s[0] == s[2]):
    cnt+=1
 
 
if(s[0] == s[3]):
    cnt+=1
 
 
if(s[1] == s[2]):
    cnt+=1
 
 
if(s[1] == s[3]):
    cnt+=1
 
 
if(s[2] == s[3]):
    cnt+=1
 
 
if cnt == 2 :
  print("Yes")
else :
  print("No")

Measured memory_bytes: 3064
#include <iostream>
#define MOD 1000000007
#define LL long long
using namespace std;
LL Pow(LL a,LL b)
{
    LL ans=1;
    while(b)
    {
        if(b&1)
        {
            b--;
            ans=(ans*a)%MOD;
        }
        else
        {
            b/=2;
            a=(a*a)%MOD;
        }
    }
    return ans;
}

int inv(int a)
{
    return a==1?1:(long long)(MOD-MOD/a)*inv(MOD%a)%MOD;
}
LL C(LL n,LL m)
{
    if(m<0)
        return 0;
    if(n<m)
        return 0;
    if(m>n-m)
        m=n-m;
    LL up=1,down=1;
    for(LL i=0; i<m; i++)
    {
        up=up*(n-i)%MOD;
        down=down*(i+1)%MOD;
    }
    return up*inv(down)%MOD;
}

int main()
{

    LL a,b,n;
    cin>>n>>a>>b;
    LL result=Pow(2,n)-C(n,a)-C(n,b)-1;
    while(result<0)
        result+=MOD;
    cout<<result;
}


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

int main(){
  int a,b,c,cnt;
  string s="No";
  cin >> a >> b;
  c = b;
  while(c>0){
    c /= 10;
    cnt++;
  }
 for(int i=0;i<400;i++){
   if(i*i==a*pow(10,cnt)+b){
     s = "Yes";
     break;
   }
 }
  cout << s << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
#define min(p,q)((p)<(q)?(p):(q))

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}

//union-find
int uniroot[200010];
void ufinit(int n){for(int i=0;i<n;i++){uniroot[i]=i;}}
int root(int x){return uniroot[x]!=x?uniroot[x]=root(uniroot[x]):x;}
int same(int x,int y){return root(x)==root(y);}
void uni(int x,int y){if((x=root(x))==(y=root(y)))return;uniroot[x]=y;}

ll K[200010];
ll L[200010];

ll KL[200010];
ll KL2[200010];
ll cnt[200010];
ll num;


int bserch(int i){
	ll l=0,r=num;
	while(r-l>1){
		int m=(l+r)/2;
		if(KL2[m]>KL[i])r=m;
		else l=m;
	}
	return l;
}

int main(){
	int n,k,l;
	scanf("%d%d%d",&n,&k,&l);
	
	ufinit(n+1);
	rep(i,0,k){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		uni(a,b);
	}
	rep(i,1,n+1)K[i]=root(i);
	
	ufinit(n+1);
	rep(i,0,l){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		uni(a,b);
	}
	rep(i,1,n+1)L[i]=root(i);
	
	rep(i,1,n+1)KL[i]=K[i]<<32|L[i];
	sortup(KL+1,n);
		
	num=1;
	KL2[0]=KL[1];
	cnt[0]=1;
	rep(i,2,n+1){
		if(KL[i]==KL2[num-1])cnt[num-1]++;
		else{
			KL2[num]=KL[i];
			cnt[num]=1;
			num++;
		}
	}

	rep(i,1,n+1)KL[i]=K[i]<<32|L[i];
	
	rep(i,1,n+1)printf("%d%c",cnt[bserch(i)],i==n?'\n':' ');
	return 0;
}

Measured memory_bytes: 9020
package main

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

func main() {
	var n, m int
	fmt.Scan(&n, &m)
	to5 := make(map[int]bool, 0)
	from1 := make(map[int]bool, 0)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < m; i++ {
		var s, t int
		sc.Scan()
		s, _ = strconv.Atoi(sc.Text())
		sc.Scan()
		t, _ = strconv.Atoi(sc.Text())
		if s == 1 {
			from1[t] = true
		}
		if t == n {
			to5[s] = true
		}
	}
	ok := false
	for i := 0; i < n; i++ {
		if from1[i] && to5[i] {
			ok = true
			break
		}
	}
	if ok {
		fmt.Println("POSSIBLE")
	} else {
		fmt.Println("IMPOSSIBLE")
	}
}


Measured memory_bytes: 8320
loop do
  a,b,c = gets.split.map(&:to_i)
  break if (a|b|c)==0
  n =gets.to_i
  items = Array.new(a+b+c+1,2)
  sets = Array.new
  n.times do
    i,j,k,r = gets.split.map(&:to_i)
    set=[i,j,k,r]
    if r==1
      sets.unshift(set)
    else
      sets << set
    end
  end
  sets.each do |ary|
    if ary[3]==1
      (0..2).each do|i|
        items[ary[i]]=1
      end
    else
      result = [items[ary[0]],items[ary[1]],items[ary[2]]]
      if result.count(1)==2 && result.count(2)==1
        items[ary[result.index(2)]]=0

      end
    end
  end
  items.delete_at(0)
  puts items
end

Measured memory_bytes: 2732
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_B main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int N; cin >> N;
    vi P(N); REP(i, N) cin >> P[i];

    int ans = 0;
    FOR(i,1,N-1) {
        if ((P[i - 1] < P[i] && P[i] < P[i + 1])
            || (P[i - 1] > P[i] && P[i] > P[i + 1])) ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<functional>
#include<list>
#include<map>
#include<iomanip>
#include<iostream>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
#include<algorithm>
#include<memory.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	int mlen=s.length()-2;
	int flag=1;
	while(flag==1){
		flag=0;
		for(int i=0;i< (mlen/2);i++){
			//cout<<s[i]<<endl<<s[mlen/2+i+1];
			if(s[i]!=s[mlen/2+i])
				flag=1;
		}
		if(flag==0)cout<<mlen<<endl;
		mlen-=2;
	}
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}
template<typename T> void chkmax(T &x,T y){x=x>y?x:y;}
char S[500010];int a[500010];int co[500010][2];

int main(){
	scanf("%s",S+1);int n=strlen(S+1);
	
	rep(i,1,n+1){
		if(S[i-1]=='>'&&S[i]=='>'){
			a[i]=co[i-1][1]-1;co[i][1]=a[i];continue;
		}else if(S[i-1]=='<'&&S[i]=='<'){
			a[i]=co[i-1][0]+1;co[i][0]=a[i];continue;
		}
		int ll=i-1;int rr=i;
		while(ll>=1&&S[ll]=='<')ll--;
		while(rr<=n&&S[rr]=='>')rr++;
		co[i][0]=i-ll-1;co[i][1]=rr-i;
		a[i]=max(i-ll-1,rr-i);
	}
	long long sum=0;
	rep(i,1,n+1)sum+=a[i];
	write(sum);
	return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N, T, l = 0, r = 0, cnt = 0;
  cin >> N >> T;

  for (int i = 0; i < N; i++) {
    int t;
    cin >> t;
    if (r < t) {
      cnt += r - l;
      l = t;
    }
    r = t + T;
  }
  cnt += r - l;

  cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3584
#include <iostream>

#define P 1000000007

using namespace std;

long dp[6][101];

int main(){
    int N;
    cin >> N;
    dp[0][0] = 1;
    for(int i = 1; i <= N; i++){
        dp[0][i] = (dp[0][i-1]*2+dp[1][i-1]*1+dp[2][i-1]*1+dp[3][i-1]*2+dp[4][i-1]*2+dp[5][i-1]*1)%P;
        dp[1][i] = (dp[0][i-1]*1+dp[1][i-1]*1+dp[2][i-1]*0+dp[3][i-1]*1+dp[4][i-1]*0+dp[5][i-1]*1)%P;
        dp[2][i] = (dp[0][i-1]*0+dp[1][i-1]*1+dp[2][i-1]*0+dp[3][i-1]*0+dp[4][i-1]*0+dp[5][i-1]*1)%P;
        dp[3][i] = (dp[0][i-1]*0+dp[1][i-1]*1+dp[2][i-1]*0+dp[3][i-1]*0+dp[4][i-1]*0+dp[5][i-1]*0)%P;
        dp[4][i] = (dp[0][i-1]*1+dp[1][i-1]*0+dp[2][i-1]*1+dp[3][i-1]*0+dp[4][i-1]*1+dp[5][i-1]*0)%P;
        dp[5][i] = (dp[0][i-1]*0+dp[1][i-1]*0+dp[2][i-1]*1+dp[3][i-1]*0+dp[4][i-1]*1+dp[5][i-1]*0)%P;
        if(i >= 4) dp[0][i] -= (dp[1][i-3]*1+dp[5][i-3]*1);
        if(i >= 4) dp[0][i] -= dp[2][i-2]*2;
    }
    long ans = (dp[0][N]+dp[1][N]+dp[2][N]+dp[3][N]+dp[4][N]+dp[5][N])%P;
    ans = (ans+P)%P;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string a,b,c;
int n;
int main()
{
	cin>>a>>b;
	c+=a;
	c+=b;
	n=atol(c.c_str());
	for (int i=1;i<=sqrt(n);i++)
	if (i*i==n)
	{
		cout<<"Yes";
		return 0;
	}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 256
sx,sy,tx,ty = map(int, input().split())
dx = abs(tx - sx)
dy = abs(ty - sy)

pass1 = "U"*dy + "R"*dx
pass2 = "D"*dy + "L"*dx
pass3 = "L" + "U"*(dy+1) + "R"*(dx+1) + "D"
pass4 = "R" + "D"*(dy+1) + "L"*(dx+1) + "U"
print(pass1 + pass2 + pass3 + pass4)

Measured memory_bytes: 3060
import sys
INF = 1e9 + 5
def solve(n, k, ls):
    dp = [0] * n
    dp[1] = abs(ls[0]-ls[1])
    for i in range (2,n):
        dp[i] = min(abs(ls[i] - ls[j]) + dp[j] for j in range(max(0,i-k),i))
    return dp[-1]

if __name__ == "__main__":
    f = sys.stdin
    fo = sys.stdout
    n, k = map(int, f.readline().split())
    arr = list(map(int, f.readline().split()))
    result = solve(n, k, arr)
    print(result)


Measured memory_bytes: 14016
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mood 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));

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

	int N;
	cin>>N;
	ll cnt=0;
	REP(i,N){
		int a;
		cin>>a;
		if(a%2==1)cnt++;
	}
	if(cnt%2==1)cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
	return 0;
}




















Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,temp,sum=0;
    cin>>n>>k;
    int a[n];

    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n-1; j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;

            }

        }
    }
    for(int i=0; i<k; i++)
    {
        sum+=a[i];
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
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; }

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    ll n,k;cin>>n>>k;
    vector<pair<ll,ll>> v(n);
    rep(i,n){
        ll t,d;cin>>t>>d;t--;
        v[i]=make_pair(d,t);
    }
    sort(ALL(v));
    ll ans=0,var=0;
    vector<pair<ll,ll>> vv;
    vector<pair<ll,ll>> rem;
    vector<ll> cnt(n,0);
    rep(i,k){
        ans+=v[n-i-1].first;
        if(cnt[v[n-i-1].second]==0) var++;
        cnt[v[n-i-1].second]++;
        vv.push_back(v[n-i-1]);
    }
    ans+=var*var;//答えの暫定値
    for(int i=k;i<n;i++){
        rem.push_back(v[n-i-1]);
    }
    reverse(ALL(vv));

    // for(auto x:vv){
    //     cout<<x.first<<' ';
    // }cout<<endl;
    // for(auto x:rem){
    //     cout<<x.first<<' ';
    // }cout<<endl;
    
    int idx=0;
    ll tmp=ans;
    for(auto x:rem){
        
        if(idx>=k) break;
        if(cnt[x.second]>0) continue;

        while(cnt[vv[idx].second]==1&&idx<k){
            idx++;
        }
        if(idx>=k) break;
        cnt[vv[idx].second]--;
        cnt[x.second]++;
        tmp-=vv[idx].first;
        tmp+=x.first;
        tmp+=(var+1)*(var+1)-var*var;
        ans=max(ans,tmp);
        var++;
        idx++;
    }
    //debug(cnt);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5236