akhauriyash/Code-Regression huggingface dataset:
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n,m = rl()
a = rl()

li=dict(Counter(a))
for _ in range(m):
    b, c = rl()
    if c in li:
        li[c]+=b
    else:
        li[c]=b
li=sorted(li.items(),key=lambda x: -x[0])
ans=0
res=n
for pair in li:
    if res<=0:
        continue
    if res>=pair[1]:
        ans+=pair[0]*pair[1]
        res-=pair[1]
    else:
        ans+=pair[0]*res
        res=0
print(ans)

Measured memory_bytes: 54316
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>
using namespace std;

class P{
public:
  string word;
  int edge;
  P(string a, int b){
    word = a;
    edge = b;
  }
  bool operator < (const P &a) const { return word > a.word; }
};

int main(){
  int n,a,s,g;
  int from[400],to[400];
  string spell[400];
  string ans[250][40];
  int prvx[250][40],prvy[250][40];

  while(1){
    cin >> n >> a >> s >> g;
    if(!n && !a && !s && !g)break;

    for(int i=0;i<a;i++)cin >> from[i] >> to[i] >> spell[i];
    for(int i=0;i<250;i++){
      for(int j=0;j<n;j++){
	ans[i][j] = "NO";
	prvx[i][j] = -1;
	prvy[i][j] = -1;
      }
    }
    ans[0][s] = "";

    priority_queue< P > str;
    for(int i=0;i<a;i++){
      if(from[i] == s)str.push(P(spell[i],i));
    }

    while(str.size()){
      P hoge = str.top();
      string tmp = hoge.word;
      int num = hoge.edge;

      if(ans[tmp.size()][to[num]] == "NO"){
	ans[tmp.size()][to[num]] = tmp;
	prvx[tmp.size()][to[num]] = tmp.size() - spell[num].size();
	prvy[tmp.size()][to[num]] = from[num];
	if(to[num] == g)break;
	for(int i=0;i<a;i++){
	  int sum = tmp.size() + spell[i].size();
	  if(from[i] == to[num] && sum < 250 && ans[sum][to[i]] == "NO")str.push(P(tmp+spell[i],i));
	}
      }
      str.pop();
    }
    
    string res = "NO";
    int pos = -1;
    for(int i=0;i<250;i++){
      if(res == "NO"){
	res = ans[i][g];
	pos = i;
      }else if(ans[i][g] != "NO" && res > ans[i][g]){
	res = ans[i][g];
	pos = i;
      }
    }

    if(pos>=0){
      vector<int> visit;
      int x = pos, y = g;
      bool loop = false;
      visit.push_back(y);
      while(x>=0 && y>=0){
	int t = prvx[x][y];
	y = prvy[x][y];
	x = t;

	for(int i=0;i<(int)visit.size();i++){;
	  if(visit[i] == y)loop = true;
	}
	if(loop)break;
	visit.push_back(y);
      }
      if(loop)res = "NO";
    }
    cout << res << endl;
  }
}

Measured memory_bytes: 10000
n = int(input())
x = [ int(x) for x in input().split() ]

s = sum(x)
avg = s // n

t = 0
for e in x:
    t += (e - avg)**2

u = 0
for e in x:
    u += (e - (avg + 1))**2

print(min([t, u]))



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

int main(){
	
	int a, b;
	
	cin >> a;
	cin >> b;
	
	if (a == 1 && b == 2){
		cout << "3";
	} else if (a == 2 && b == 1){
		cout << "3";
	} else if (a == 2 && b == 3){
		cout << "1";
	} else if (a == 3 && b == 2){
		cout << "1";
	} else if (a == 1 && b == 3){
		cout << "2";
	} else if (a == 3 && b == 1){
		cout << "2";
	} 
	
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

int main(){
	int a, b, n; cin >> n;
	a = b = 0;

	REP(i, n){
		int val; cin >> val;
		if( val % 4 == 0 ) a++;
		else if( val % 2 == 0) b++;
	}

	b = max(0, b - 1);

	if( a >= (n - b) / 2 ){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        Pattern p = Pattern.compile("\\s[A-Za-z]*\\s");
        Matcher m = p.matcher(s);
        if (m.find()) {
            System.out.println("A" + m.group().charAt(1) + "C");
        }

    }
}

Measured memory_bytes: 21716
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define mk make_pair
#define pi pair<int, int>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
using namespace std;
int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1},{0,0}};
//typedef pair<int, int> P;
//priority_queue<int, vector<int>, greater<int> > q;

const int N = 2e5+5;

int a[N];//储存i之前有多少个w

int main()
{
   IOS;
   int n;
   cin >> n;
   string s;
   cin >> s;
   int cntr = 0,cntw = 0;
   rep(i,0,n-1){
       if(s[i] == 'W')++cntw;
       a[i] = cntw;
   }
   //int cnt = 0;
   int res = 0;
   int tt = 0;
   per(i,n-1,0){
       if(s[i] == 'R'){
           if(a[i]-tt > 0){
               ++tt;
               ++res;
           }
       }
   }
   cout << res <<endl;
}


Measured memory_bytes: 4516
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
using  namespace std;


int a[255];
int main(){
	int N;
	cin>>N;
	for(int e=0;e<N;e++){
		cin>>a[e];
	}
	sort(a,a+N);
	for(int e=0;e<N;e++){
		}
		cout<<a[N-1]-a[0]<<endl;
}
	

Measured memory_bytes: 256
#include <iostream>

int main(){
	
	//double loop
	for(int i = 1; i <= 9; ++i){
		for(int j = 1; j <= 9; ++j){
			std::cout << i << "x" << j << "=" << i*j << std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1116
a,b,c,d=map(int,input().split())
def kosuu(a,b,c):
    if a%c==0:
        return (b-a)//c+1
    else:
        return(b-(a+(c-a%c)))//c+1

l=0
c1=c
d1=d
while c1!=0 and d1!=0:
    if c1<=d1:
        d1=d1%c1
    else:
        c1=c1%d1
if c1!=0:
    l=c1
else:
    l=d1

print(b-a+1-kosuu(a,b,c)-kosuu(a,b,d)+kosuu(a,b,c*d//l))


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();

        int sum = 0;
        int index = 0;
        for (int i = 0; i < n; i++) {
            int l = scanner.nextInt();
            sum += l;
            if (index == 0 && sum > x) {
                index = i;
            }
        }
        if (index == 0) {
            System.out.println(n + 1);
        } else {
            System.out.println(index + 1);
        }
    }
}


Measured memory_bytes: 23764
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <assert.h>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)



















int main(){
    ll x, a, b;
    cin >> x >> a >> b;
    cout << ((abs(x - a) < abs(x - b))? "A" : "B") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
using namespace std;
int main() {
	long long int n;
	std::cin >> n;
	    long long int happy=0;
	    if(n>500)
	    {
	        happy=(n/500)*1000;
	        happy=happy+((n%500)/5)*5;
	    }
	    else if(n==500)
	    {
	        happy=1000;
	    }
	    else
	    {
	       happy=(n/5)*5;   
	    }
	    std::cout << happy << std::endl;
	return 0;
}

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

#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
typedef long long ll;
typedef vector<int> vi;

const ll MOD = 1000000007;

const int N_MAX = 100010;

template<typename T>
bool isInExist(const T& c, const typename T::value_type& v) {
    return (c.end() != find(c.begin(),c.end(),v));
}

ll ModAdd(ll a, ll b) {
    return (a + b) % MOD;
}

int main() {
    int N, M, tmp;
    vi a(M);

    cin >> N >> M;
    REP(i, M) {
        cin >> tmp;
        a.emplace_back(tmp);
    }

    ll dp[N_MAX];
    REP(i, N_MAX) {
        dp[i] = 0;
    }
    dp[0] = 1;

    bool flag1 = false;
    bool flag2 = false;

    vi::iterator tmp_itr = a.begin();

    for (int i=0; i<N; ++i) {
        auto find_itr_1 = find(tmp_itr, a.end(),i+1);
        flag1 = (find_itr_1 != a.end());
        if (flag1) {
            tmp_itr = find_itr_1;
        }

        if (!flag1) {
            dp[i+1] = ModAdd(dp[i+1], dp[i]);
        }

        auto find_itr_2 = find(tmp_itr, a.end(),i+2);
        flag2 = (find_itr_2 != a.end());
    
        if (flag1 && flag2) {
            cout << 0 << endl;
            return 0;
        }
       
        if (!flag2) {
            dp[i+2] = ModAdd(dp[i+2], dp[i]);
        }
    }

    cout << dp[N] << endl;

    return 0;
}

Measured memory_bytes: 1528
#include <stdio.h>
#include <string.h>

int main(){
  int n,i,a[100000],count[100001]={0},ans=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    count[a[i]]++;
  }
  for(i=1;i<=100000;i++){
    if(count[i]!=0)ans++;
  }

  if(ans%2==0)printf("%d\n",ans-1);
  else printf("%d\n",ans);

  return 0;
}


Measured memory_bytes: 896
///  author:Kissheart  ///
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<deque>
#include<ctype.h>
#include<map>
#include<set>
#include<stack>
#include<string>
#define INF 0x3f3f3f3f
#define FAST_IO ios::sync_with_stdio(false)
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAX=2e5+10;
const int mod=1e9+7;
typedef long long ll;
using namespace std;
#define gcd(a,b) __gcd(a,b)
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;}
inline ll inv1(ll b){return qpow(b,mod-2);}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;}
inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;}
//freopen( "in.txt" , "r" , stdin );
//freopen( "data.txt" , "w" , stdout );
int n,t;
int a[MAX],vis[MAX];
int solve1()
{
    int ans=0,sum=0;
    int p;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=n;i+=2)
    {
        vis[a[i]]++;
        if(vis[a[i]]>sum)
        {
            sum=vis[a[i]];
            p=a[i];
        }
    }
    ans=(t-sum);
    sum=0;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i+=2)
    {
        vis[a[i]]++;
        if(vis[a[i]]>sum && a[i]!=p)
            sum=vis[a[i]];
    }
    ans+=(t-sum);
    return ans;
}
int solve2()
{
    int ans=0,sum=0;
    int p;
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i+=2)
    {
        vis[a[i]]++;
        if(vis[a[i]]>sum)
        {
            sum=vis[a[i]];
            p=a[i];
        }
    }
    ans=(t-sum);
    sum=0;
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=n;i+=2)
    {
        vis[a[i]]++;
        if(vis[a[i]]>sum && a[i]!=p)
            sum=vis[a[i]];
    }
    ans+=(t-sum);
    return ans;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    t=n/2;
    printf("%d\n",min(solve1(),solve2()));
    return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

const int MAX_N = 100050;
int N;
int a[MAX_N];

int main(int argc, char **argv) {
    std::cin >> N;

    for (int i = 1; i <= N; i++) {
        std::cin >> a[i];
    }

    std::unordered_map<int, int> mp;
    for (int i = 1; i <= N; i++) {
        if (mp.find(a[i]) != mp.end()) {
            mp[a[i]] += 1;
        } else {
            mp[a[i]] = 1;
        }
    }

    int ret = 0;
    for (auto pair : mp) {
        if (pair.first <= pair.second) {
            ret += pair.second - pair.first;
        } else {
            ret += pair.second;
        }
    }

    std::cout << ret << std::endl;

    return 0;
}

Measured memory_bytes: 4644
import sys
n, m = map(int, input().split())
x = list(map(int, input().split()))
a = []

if m == 1:
    print(0)
    sys.exit()

#x.sort()
list.sort(x)
#print(x)

for i in range(1, m):
    a.append(x[i] - x[i-1])

#list.sort(a, reverse=True)
a.sort()
#print(a)

count = max(x) - min(x)
for i in range(n-1):
    if len(a) == 0:
        break
    a.pop()
#    count -= a[i]

#print(count)
print(sum(a))

Measured memory_bytes: 13968
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	ll T = 1, A = 1;
	rep(i,n){
		ll t, a;
		cin >> t >> a;
		T = (T + t - 1) / t * t;
		A = (A + a - 1) / a * a;
		ll cmpT = T / t * a;
		if(cmpT < A) T = A / a * t;
		else if(cmpT > A) A = T / t * a;
	}
	ll ans = T + A;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int main(){
	vi a(12);
	rep(i, 12) cin>>a[i];
	map<int, int> m;
	for(int p : a) m[p]++;
	for(auto p : m) if(p.se & 1) {
		cout << "no" <<endl;
		return 0;
	}
	cout << "yes" << endl;
}

Measured memory_bytes: 3124
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<cmath>
#include<cstdio>
using namespace std;
int main(){
  int i;
  int h,w,n;
  while(scanf("%d%d%d",&h,&w,&n),h||w||n){
    int a[50000],b[50000],c[50000];
    for(i=0;i<n;++i)
      scanf("%d%d%d",a+i,b+i,c+i);
    int d[50000]={},e[50000]={},f=0,g=0;
    int ct=0;
    for(i=n-1;i>=0;--i){
      if(a[i]){
	if(d[b[i]]==0){
	  if(c[i])
	    ct+=h-g;
	  d[b[i]]=-1;
	  ++f;
	}
      }else{
	if(e[b[i]]==0){
	  if(c[i])
	    ct+=w-f;
	  e[b[i]]=-1;
	  ++g;
	}
      }
    }
    printf("%d\n",ct);
  }
  return 0;
}

Measured memory_bytes: 0
// 解答不能.
// kort0n氏.
// https://atcoder.jp/contests/abc153/submissions/9746540
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second

struct LazySegmentTree{
private:
    int n;
    vector<LL> node, lazy;

public:
    LazySegmentTree(){
        int sz = 200050;
        n = 1;
        while(n < sz) n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);
        rep(i, sz) node[i + n - 1] = 0;
        repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void eval(int k, int l, int r){
        if(lazy[k] != 0){
            node[k] += lazy[k];
            if(r - l > 1){
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }
    void add(int a, int b, LL x, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }else{
            add(a, b, x, 2 * k + 1,           l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2,           r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }
    LL sum(int a, int b, int k = 0, int l = 0, int r = -1){
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        LL vl = sum(a, b, 2 * k + 1,           l, (l + r) / 2);
        LL vr = sum(a, b, 2 * k + 2, (l + r) / 2,           r);
        return vl + vr;
    }
};

int main(){
    int N;
    LL D, A;
    scanf("%d %lld %lld", &N, &D, &A);
    vector<P> v;
    v.resize(N);
    rep(i, N) scanf("%lld %lld", &v[i].a, &v[i].b);
    v.push_back({1e17, 1e17});
    sort(v.begin(), v.end());
    LazySegmentTree seg;
    rep(i, N){
        LL num = (v[i].b + A - 1) / A;
        seg.add(i, i + 1, num);
    }
    LL ans = 0;
    rep(i, N){
        if(seg.sum(i, i + 1) <= 0) continue;
        LL num = seg.sum(i, i + 1);
        P tmp = {v[i].a + 2 * D + 1, -1e18};
        auto itr = lower_bound(v.begin(), v.end(), tmp);
        itr--;
        int j = distance(v.begin(), itr);
        ans += num;
        seg.add(i, j + 1, -num);
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 13256
N = int(input())
A_list = [0]*2
A_list[0] = list(map(int, input().split()))
A_list[1] = list(map(int, input().split()))

candy_list = []
for i in range(N):
    count = 0
    for j in range(N):
        if i >= j:
            count += A_list[0][j]
            if i == j:
                count += A_list[1][j]
        else:
            count += A_list[1][j]
    candy_list.append(count)

print(max(candy_list))

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

int main(){
  long long int A,V,B,W,T;
  cin >> A >> V >> B >> W >> T;
  if(A<B){
    if(B-A<=(V-W)*T){
      cout << "YES" << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }
  else{
    if(A-B<=(V-W)*T){
      cout << "YES" << endl;
    }
    else{
      cout << "NO" << endl;
    }
  }
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REP2(i, a, b) for (int i = (a); i < (int)(b); i++)
typedef vector<int> VI;
typedef vector<VI> VVI;

int Main(int a, int b)
{
    int c = a-b*2;
    return (c >= 0) ? c : 0;
}

int main(void){
    int A, B;
    cin >> A >> B;
    cout << Main(A, B) << endl;
    return 0;
}

Measured memory_bytes: 256
from collections import defaultdict


class UnionFind(object):
    def __init__(self, n):
        self.parent = {i: i for i in range(n)}
        self.rank = {i: 0 for i in range(n)}
        self.size = {i: 1 for i in range(n)}
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])

        return self.parent[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y

        else:
            self.parent[y] = x

            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

        self.size[x] += self.size[y]
        self.size[y] = self.size[x]


    def get_size(self, x):
        return self.size[self.find(x)]


n, m, k = map(int, input().split())
As, Bs = list(), list()
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    As.append(a)
    Bs.append(b)

edge_friends = defaultdict(list)
for a, b in zip(As, Bs):
    edge_friends[a].append(b)
    edge_friends[b].append(a)

edge_block = defaultdict(list)
for i in range(k):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    edge_block[c].append(d)
    edge_block[d].append(c)

union_find = UnionFind(n)
for a, b in zip(As, Bs):
    union_find.union(a, b)

counts = list()
for i in range(n):
    parent = union_find.find(i)
    n_blocks = 0
    for node in edge_block[i]:
        if parent == union_find.find(node):
            n_blocks += 1
    n_friends = 0
    for node in edge_friends[i]:
        if parent == union_find.find(node):
            n_friends += 1

    count = union_find.get_size(i) - 1 - n_blocks - n_friends
    counts.append(count)

print(*counts)


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

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

	if(s=="SUN")cout << 7 <<endl;
	if(s=="MON")cout << 6 <<endl;
	if(s=="TUE")cout << 5 <<endl;
	if(s=="WED")cout << 4 <<endl;
	if(s=="THU")cout << 3 <<endl;
	if(s=="FRI")cout << 2 <<endl;
	if(s=="SAT")cout << 1 <<endl;
}

Measured memory_bytes: 256
arr = [[[0 for i in range(10)] for j in range(3)] for k in range(4)]
for i in range(int(input())):
    b,f,r,v = map(int, input().split())
    arr[b-1][f-1][r-1] += v
for i in range(4):
    for j in range(3):
        for k in range(10):
            if k == 0:
                print ("", end=" ")
            if k == 9:
                print(arr[i][j][k])
            else:
                print(arr[i][j][k], end=" ")
    if i != 3:
        print("#"*20)

Measured memory_bytes: 7744
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
    char fistr[11],ristr[101];
    int maxe,ring,ans=0,word,co=1,next=0;
    cin>>fistr;
    for(int i=0;i<11;i++){
        if(fistr[i]=='\0'){
            maxe=i;
            break;
        }
    }
    cin>>ring;
    for(int i=0;i<ring;i++){
        cin>>ristr;
        for(int j=0;j<101;j++){
            if(ristr[j]=='\0'){
                word=j-1;
                break;
            }
        }
        for(int j=0;j<word+1;j++){
            if(fistr[0]==ristr[j]&&j!=word){
                    //cout<<j<<endl;
                if(maxe==1){
                        ans++;
                        next=1;
                }
                for(int k=1;k<maxe;k++){
                       // cout<<j+co<<" "<<word<<endl;
                     if(j+co>word&&ristr[co+j-word-1]!=fistr[k])break;
                     else if(ristr[j+co]!=fistr[k]&&word>j+co)break;
                    if(k==maxe-1){
                            ans++;
                            next=1;
                    }
                    co++;
                }
                co=1;
                if(next==1){
                    next=0;
                    break;
                }
            }
            else if(fistr[0]==ristr[j]){
                co=0;
                if(maxe==1)ans++;
                for(int k=1;k<maxe;k++){
                    if(ristr[co]!=fistr[k])break;
                    if(k==maxe-1){
                            ans++;
                            //next=1;
                    }
                    co++;
                }
                co=1;
                /*if(next==1){
                    next=0;
                    break;
                }*/
            }
        }
    }
     cout<<ans<<endl;
}

Measured memory_bytes: 1168
n=int(input())
a=list(map(lambda x:min(int(x)//400,8),input().split()))
cat=[0]*8
f=0
for ai in a:
    if ai < 8:
        cat[ai]=1
    if ai == 8:
        f+=1
print(str(max(sum(cat),1))+' '+str(sum(cat)+f))



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

int n;   // 荷物の数
int k;   // トラックの台数
int w[100000] = {};  // それぞれの荷物の重さ

// 最大積載量Pのk台のトラックで何個の荷物が詰めるか
int check(int P) {
    int j = 0;
    int sum;

    for (int i = 0; i < k; i++) {
        sum = 0;
        while (sum + w[j] <= P) {
            sum += w[j];
            j++;
            if (j == n) return n;
        }
    }
    return j;
}

// 二分探索
int binarySearch() {
    int left = 0;
    int right = 10000 * 100000;  // 1つあたりの荷物の重さ * 荷物の最大量
    int mid;

    while(left < right) {
        mid = (left + right) / 2;
        int checkResult = check(mid);
        if (checkResult >= n) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return right;
}

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

    int P = binarySearch();
    printf("%d\n", P);

    return 0;
}


Measured memory_bytes: 2172
n, m = [int(i) for i in input().split()]
ab = [[int(i) for i in input().split()] for _ in range(n)]
ab.sort()
ans = 0
for i in ab:
    if m <= i[1]:
        ans += m * i[0]
        m = 0
    else:
        m -= i[1]
        ans += i[0] * i[1]
print(ans)


Measured memory_bytes: 60692
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#include <cassert>

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

using namespace std;

const int MOD = 1000000007;

vector<long long> fact_inv, inv, Com;

/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
void init_nCk(int n, int SIZE) {
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
    Com.resize(SIZE + 5);
    Com[0] = 1;
    for (int i = 1; i < SIZE + 5; i++) {
        Com[i] = Com[i - 1] * ((n - i + 1) * inv[i] % MOD) % MOD;
    }
}
/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int k) {
    assert(!(k < 0));
    return Com[k];
}

long long modPow(int i, int p) {
    if(p == 0) {
        return 1;
    }
    long long ret;
    if(p % 2 == 1) {
        ret = i * modPow(i, p-1);
    } else {
        long long mp = modPow(i, p/2); 
        ret = mp * mp;
    } 
    return ret % MOD;
}

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

    int numX = 2 * X - Y;
    int numY = 2 * Y - X;

    if(numX % 3 != 0 || numY % 3 != 0) {
        cout << 0 << endl;
        return 0;
    }
    if(numX < 0 || numY < 0) {
        cout << 0 << endl;
        return 0;
    }
    numX /= 3;
    numY /= 3;

    if(numX > numY)
        swap(numX, numY);

    init_nCk(numX + numY, numX);
    cout << nCk(numX) << endl;

    return 0;
}



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

using namespace std;


using int64 = long long;
const int64 INF = 1LL << 60;


int main() {
  int N, K, A[100000];
  cin >> N >> K;
  for(int i = 0; i < N; i++) cin >> A[i];
  vector< int64 > dp(N, INF);
  dp[0] = 0;
  for(int i = 1; i < N; i++) {
    for(int j = 1; j <= K; j++) {
      if(i - j >= 0) {
        dp[i] = min(dp[i], dp[i - j] + abs(A[i] - A[i-j]));
      }
    }
  }
  cout << dp.back() << endl;
}


Measured memory_bytes: 1408
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll   long long
#define ld long double
#define endl '\n'
#define INF 10000000000000000
#define pll pair<ll,ll>
#define ff first
#define ss second

using namespace std;
const ll N = 200005;
const ll MOD = 998244353;
vector<ll> g[N];
bool vis[N];
ll d[N];
ll in_degree[N];
void dfs(ll v) {
    vis[v]=1;
    for(ll i =0;i<g[v].size();i++) {
        ll to = g[v][i];
        d[to]=max(d[to],d[v]+1);
        in_degree[to]--;
        if(in_degree[to]==0)
            dfs(to);
    }
}
int main()
{
 //freopen("input.txt","r",stdin);
 //  freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,m;
    cin>>n>>m;
    for(ll i =1;i<=m;i++) {
        ll u,v;
        cin>>u>>v;
        g[u].push_back(v);
        ++in_degree[v];
    }
    for(ll i =1;i<=n;i++) {
        if(!vis[i] && in_degree[i]==0) dfs(i);
    }
    ll ans =0;
    for(ll i =1;i<=n;i++) {
        ans=max(ans,d[i]);
    }
    cout<<ans;


}


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

#define REP(i,n) for(int i = 0;i < n;i++)
#define REPR(i,n) for(int i = n-1;i >= 0;i--)
#define FOR(i,m,n) for(int i = m;i < n;i++)
#define PRINT(s) cout<<s
#define PRINTS(s) cout<<s<<' '
#define PRINTL(s) cout<<s<<endl
#define INF 2e9
#define ALL(v) v.begin(),v.end()
#define ll long long

using namespace std;

string pop_back(string s){
    string t = s.substr(0,s.size()-1);
    return t;
}

int gcd(int max,int min){
    
    if(max<min){
        int tmp=max;
        max=min;
        min=tmp;
    }

    if(max%min==0)return min;
    else return gcd(min,max%min);

}

int main(void){

    string s;
    cin>>s;
    int a[26]={0};

    for(int i=0;i<s.size();i++){
        int n = s[i]-'a';
        a[n]++;
    }

    char ans='a';
    for(int i=0;i<26;i++){
        if(a[i]>0)ans+=1;
        else break;
    }
    
    if(ans>'z')cout<<"None"<<endl;
    else{
        cout<<ans<<endl;
    }

    return 0;
}




Measured memory_bytes: 512
using System;
using System.Linq;
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            var s = Console.ReadLine();
            
            Console.WriteLine(s.Count(c => c == 'R') > s.Count(c => c == 'B') ? "Yes":"No");
        }
    }

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

#define mp make_pair
#define pb push_back
#define REP(i,a,n) for(int i = a;i < (n);i++)
#define rep(i,n) for(int i = 0;i < (n);i++)
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define range(x,min,max) ((min) <= (x) && (x) <= (max))
#define xyrange(x, minX, maxX, y, minY, maxY) (range(x, minX, maxX) && range(y, minY, maxY))

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef pair<int,int> PII;
typedef vector<PII> VPII;


const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};
const int INF = INT_MAX / 2;

LL a, b, x;

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	cin >> a >> b >> x;
	if (a == b && a % x) {
		cout << 0 << endl;
	} else {
		b = b / x * x;
		a = (a % x? (a / x + 1) * x : a / x * x);
		LL ans = b / x - a / x + 1;
		cout << ans << endl;
	}
	return 0;
}



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

using namespace std;

int f[16666], g[16666];
string s;
int t[2], n[2], z;
int a[2][8888];

int main(){
//	freopen("input.inp", "r", stdin);
	cin >> s >> t[0] >> t[1];
	int dir = -1;
	for(int i = 0; i < s.length(); ++i){
		if (s[i] == 'F'){
			if (dir == -1) ++z;
			else ++a[dir][n[dir]];
		}
		else{
			if (dir == -1) dir = 1;
			else dir ^= 1;
			++n[dir];
		}
	}
	//0->x;
	t[0] = abs(t[0] - z); 
	t[1] = abs(t[1]);
	for(int k = 0; k < 2; ++k){
		sort(a[k] + 1, a[k] + 1 + n[k]);
		reverse(a[k] + 1, a[k] + 1 + n[k]);
		memset(f, 0, sizeof(f));
		memset(g, 0, sizeof(g));
		int mx = 0;
		f[0] = g[0] = 1;
		for(int i = 1; i <= n[k]; ++i){
			mx += a[k][i];
			for(int j = 0; j <= mx; ++j){
				f[j] = 0;
				if (j >= a[k][i]) f[j] |= g[j - a[k][i]];
				if (j + a[k][i] <= mx) f[j] |= g[j + a[k][i]];
			}
			for(int j = 0; j <= mx; ++j) g[j] = f[j];
		}
		if (!f[t[k]]){
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T> class tRMQ {
  vector<T> data;
  T unit;

public:
  int n;
  function<T(const T &, const T &)> f;

  tRMQ(int _, T u, function<T(T, T)> bi) {
    unit = u;
    f = bi;
    n = 1;
    while (n < _) {
      n <<= 1;
    }
    data.resize(n * 4);
    for (int i = 0; i < n * 4; i++)
      data[i] = unit;
  }

  tRMQ(vector<T> &v, T u, function<T(T, T)> bi) {
    unit = u;
    f = bi;
    n = 1;
    while (n < v.size())
      n <<= 1;
    data.resize(n * 4);
    for (int i = 0; i < 3 * n; i++) {
      if (i < v.size())
        data[i + n] = v[i];
      else
        data[i + n] = u;
    }
    for (int i = n - 1; i >= 0; i--) {
      data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
    }
  }

  void update(int index, T val) {
    int i = index + n - 1;
    data[i] = val;
    while (i > 0) {
      i = (i - 1) / 2;
      data[i] = f(data[i * 2 + 1], data[i * 2 + 2]);
    }
  }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if (a < 0 || r <= a || b <= l)
      return unit;
    if (a <= l && r <= b)
      return data[k];
    else
      return f(query(a, b, k * 2 + 1, l, (l + r) / 2),
               query(a, b, k * 2 + 2, (r + l) / 2, r));
  }

  T query(int a, int b) { return query(a, b, 0, 0, n); }
};
int DAY = 86400;
int MOR = 10800;

int main() {
  int n;
  cin >> n;
  int base = 0;
  vector<ll> d(DAY);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    d[(base + a) % DAY] += 1;
    base += a + b;
    base %= DAY;
  }
  tRMQ<ll> q(d, 0ll, [](const ll &l, const ll &r) { return l + r; });
  ll ans = 0;
  for (int i = 0; i < DAY; i++) {
    ll b = q.query(max(-DAY + i, 0), max(-DAY + i + MOR + 1, 0)) +
           q.query(min(i, DAY), min(i + MOR + 1, DAY));
    ans = max(ans, b);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 4992
r,c = map(int,input().split())
table = []
for i in range(r):
  tmp = list(int(x) for x in input().split())
  table.append(tmp)
  
for i in range(r):
  sum = 0
  for j in range(c):
  
    if j == c-1:
      sum += table[i][j]
      print(table[i][j],end =" ")
      table[i].append(sum)
      print(sum,end ="")
    else:
      sum += table[i][j]
      print(table[i][j],end =" ")
  print()

tmp = 0
sum = 0
while(tmp < c+1):
  for i in range(r):
    sum += table[i][tmp]
  if tmp == c:
    print(sum,end ="")
  else:
    print(sum,end =" ")
  sum = 0

  tmp += 1
print()
    


Measured memory_bytes: 6224
import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created 2017/06/01.
 */
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    ArrayList<Double> ary = new ArrayList<>();

    while (true) {
      double input = Double.parseDouble(sc.next());
      ary.add(input);
      if (ary.size() == 1) break;
    }
    
    double a = ary.get(0);
    double x = Math.PI;
    
    double s = Math.pow(a,2) * x;
    double m = a * 2 * x;

    System.out.printf("%f",s);
    System.out.print(" ");
    System.out.printf("%f",m);
  }

}

Measured memory_bytes: 26436
#include <bits/stdc++.h>
    //#define int long long
    typedef long long ll;
    #define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
    #define forn(i, n) fore(i, 0, n)
    #define fori(i, l, r) fore(i, l, (r) + 1)
    #define sz(v) int((v).size())
    #define all(v) (v).begin(), (v).end()
    #define pb push_back
    #define mp make_pair
    #define ff first
    #define ss second
    using namespace std; 
     
    const double PI = atan(1)*4;

    int dx[8]={1,0,-1,0,1,-1,-1,1};
    int dy[8]={0,1,0,-1,1,1,-1,-1};
     
     
    bool isprime(int n)
    {
        for(int i=2;i*i<=n;i++)
            if(n%i==0)
                return false;
        return true;
    }

    const int mod = 998244353;
     
    bool comp(pair<int,int> a, pair<int,int> b)
    {
        return b.ff < a.ff ;
    }
     
    ll pw(ll b, ll e)
    {
        ll ans = 1;
        while(e)
        {
            if(e & 1)
                ans = (ans * b) % mod;
            b = (b * b) % mod;
            e >>= 1;
        }
        return ans;
    }

    ll fact[200002], inv[200002];
    
    ll C(ll n, ll k)
    {
        return ((((fact[n] * inv[k]) % mod) * inv[n-k]) % mod);
    }
     
    /*void bsearch(int max,int min)   //  for function 
    //void bsearch(int a,int n, int x)     // for array
    {
        int k=min;
     
        //  for array
     
    /*    for(int b=n/2; b>=1; b/=2)
        {
            while(k+b<n && arr[k+b]<=x) k+=b; 
        }
     
        if(arr[k]==x)
            cout<<"found at "<<k+1;
        else
            cout<<"not found";
    */
     
        //  for function 
     
    /*    for(int b=max; b>=1; b/=2)
        {
            while( !fn(b+k) ) k+=b;
        }
        cout<<k+1;
     
    }*/
     
    int vis[200005];
     
    int main()
    {
     
        int t=1;
        //cin>>t;
     
        while(t--)
        {
            int n,W;
            cin>>n>>W;

            int v[n],w[n],sz=0;
            forn(i,n) 
            {
                cin>>w[i]>>v[i];
                sz+=v[i];
            }

            ll dp[n+1][sz+1];

            memset(dp,2, sizeof(dp));

            //forn(i,n+1) dp[i][0]=0;
            //forn(i,sz+1) dp[0][i]=0;

            fori(i,1,n)
            {
                fori(j,1,sz)
                {
                    if(v[i-1]<=j)
                    {
                        dp[i][j]=min(w[i-1]+dp[i-1][j-v[i-1]] , dp[i-1][j]);
                    }
                    else
                        dp[i][j]=min((ll)w[i-1] , dp[i-1][j]);
                }
            }
            /*
            fori(i,1,n)
            {
                fori(j,1,sz)
                    cout<<dp[i][j]<<" ";
                cout<<"\n";
            }*/
            
            ll mx=0;
            for(ll i=1;i<=sz;i++)
            {
                if(dp[n][i] <= W)
                    mx=i;
            }
            cout<<mx+1;
        }
        return 0;
    }

Measured memory_bytes: 79104
#include<iostream>
#include<string>
#include<cctype>

using namespace std;

int number(const string &s, int &k);
int fact(const string &s, int &k);
int term(const string &s, int &k);

int expr(const string &s, int &k){
  int result = term(s,k);
  while(true){
    if(s[k]=='+')result += term(s,++k);
    else if(s[k]=='-')result -= term(s,++k);
    else break;
  }
  return result;
}

int term(const string &s, int &k){
  int res = fact(s,k);
  while(true){
    if(s[k]=='*')res *= fact(s,++k);
    else if(s[k]=='/')res /= fact(s,++k);
    else break;
  }
  return res;
}

int fact(const string &s, int &k){
  if(s[k]=='('){
    int res = 0;
    ++k;
    res = expr(s,k);
    k++;
    return res;
  }
  return number(s,k);
}

int number(const string &s, int &k){
  int res = 0;
  while(isdigit(s[k])){
    res *= 10;
    res += (int)(s[k++] - '0');
  }
  return res;
}

int main(void){

  int n;
  cin >> n;

  while(n--){
    string s;
    cin >> s;
    int k = 0;
    cout << expr(s, k) << endl;
  }
  
  return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  int res = 0;
  auto f = [](int x) {
    int res = 2;
    for (int i = 2; i * i < x + 1; i++) {
      if (x % i == 0) res += 2;
    }
    return res;
  };
  for (int i = 1; i < N + 1; i += 2) {
    if (f(i) == 8) res++;
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
N = int(input())
S = [input() for i in range(N)]
M = int(input())
T = [input() for i in range(M)]
 
Scores = []
for s in S:
  score = len([s2 for s2 in S if s == s2])
  score -= len([s2 for s2 in T if s == s2])
  Scores.append(score)
print(max(Scores) if max(Scores)>0 else 0)

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

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

typedef long long ll;

const int Inf = 100100100;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, x;  cin >> n >> x;
    vector<int> y(n), diff(n);
    int ans;
    rep(i, n) {
      cin >> y[i];
      diff[i] = abs(y[i] - x);
    }
    ans = diff[0];
    FOR(i, 1, n) {
      ans = gcd(ans, diff[i]);
    }
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 1024
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<algorithm>
#include<cstdio>

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 bm = 3010;
ll BIT[bm];
void add(int A, ll B) {
	while (A <= bm) {
		BIT[A] = max(BIT[A], B);
		A += A & -A;
	}
}
ll query(int A) {
	ll kotae = 0;
	while (A > 0) {
		kotae = max(BIT[A], kotae);
		A -= A & -A;
	}
	return kotae;
}

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

ll V[200000], tmp[200000];

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


	int R = getint(), C = getint(), K = getint();

	rep(i, K) {
		ll r = getint(), c = getint(), v = getint();
		V[i] = v << 30 | r << 12 | c;
	}

	const int b = 12;
	int kazu[1 << b] = {}, kazu2[1 << b] = {};
	rep(i, K) kazu[V[i] & ((1 << b) - 1)]++;
	rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
	for (int i = K - 1; i >= 0; i--) tmp[--kazu[V[i] & ((1 << b) - 1)]] = V[i];
	rep(i, K) kazu2[tmp[i] >> b & ((1 << b) - 1)]++;
	rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
	for (int i = K - 1; i >= 0; i--) V[--kazu2[tmp[i] >> b & ((1 << b) - 1)]] = tmp[i];

	int mae = -1;
	ll A[4] = {};
	ll L[3001];
	int l = 0;
	rep(k, K) {
		int v = V[k] >> 30;
		int i = V[k] >> 12 & 4095;
		int j = V[k] & 4095;
		if (mae != i) {
			mae = i;
			A[0] = 0;
			A[1] = 0;
			A[2] = 0;
			A[3] = 0;
			rep(a, l) add(L[a] & 4095, L[a] >> 12);
			l = 0;
		}
		ll kari = query(j);
		A[0] = kari;
		chmax(A[3], kari);
		chmax(A[2], kari);
		chmax(A[1], kari);
		chmax(A[3], A[2] + v);
		chmax(A[2], A[1] + v);
		chmax(A[1], A[0] + v);
		L[l++] = A[3] << 12 | j;
	}

	rep(a, l) add(L[a] & 4095, L[a] >> 12);
	ll kotae = query(C);

	printf("%lld\n", kotae);

	Would you please return 0;
}

Measured memory_bytes: 4924
N, L = map(int, input().split())
tmp = L
total = 0
aLst = [0] * N
for i in range(N):
    aLst[i] = tmp + i
    total += aLst[i]

ansL = [0] * N
ansM = [0] * N
for i in range(N):
    tmp = 0
    for j in range(N):
        if i == j:
            continue
        tmp += aLst[j]
    ansL[i] = tmp
    ansM[i] = abs(total - tmp)

ans = ansL[0]
tmp = ansM[0]
for i in range(1, N):
    if tmp > ansM[i]:
        tmp = ansM[i]
        ans = ansL[i]


print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main(){
  int N, M;
  cin >> N >> M;
  if(N == M)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 3564
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <numeric>
#include <string>
#include <bitset>
#include <functional>

using ld = long double;
using vld = std::vector<ld>;
using vvld = std::vector<vld>;
using vvvld = std::vector<vvld>;
using ll = long long;
using vll = std::vector<ll>;
using vvll = std::vector<vll>;
using vvvll = std::vector<vvll>;
using pll = std::pair<ll, ll>;
using vpll = std::vector<pll>;
using str = std::string;
using vstr = std::vector<str>;

template<typename T> bool chmin(T a, T &b) { return a < b ? b = a, true : false; }
template<typename T> bool chmax(T a, T &b) { return a > b ? b = a, true : false; }

constexpr ld PI = 3.141592653589793L;
constexpr ld EPS = std::numeric_limits<ld>::epsilon();

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }
bool isprime(ll n) {
    if (n == 1) return false;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}
ll rpow(ll x, ll n) {
    if (n == 0) return 1;
    ll k = 1;
    for (; n > 1; n /= 2) {
        if (n & 1) k *= x;
        x *= x;
    }
    return k * x;
}
ll modpow(ll x, ll n, ll mod) {
    if (n == 0) return 1;
    ll k = 1;
    for (; n > 1; n /= 2) {
        if (n & 1) (k *= x) %= mod;
        (x *= x) %= mod;
    }
    return k * x % mod;
}
ll modcomb(ll n, ll r, ll mod) {
    if (r < 0 || n < r) return 0;
    chmin(n - r, r);
    ll mul = 1, div = 1;
    for (ll i = 0; i < r; i++) {
        (mul *= n - i) %= mod;
        (div *= i + 1) %= mod;
    }
    return mul * modpow(div, mod - 2, mod) % mod;
}

/*------------------------------------------------------------------------*/

void solve();

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15);

    solve();
}
void solve() {
    ll a, b, c;
    std::cin >> a >> b >> c;

    if (c > a + b && 4 * a * b < rpow(c - (a + b), 2))
        std::cout << "Yes" << '\n';
    else
        std::cout << "No" << '\n';
}


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

using namespace std;

#define debug(x) cout << "\n" << __LINE__ << " " <<  (#x) << " is " << (x) << endl

int main(){
	#ifdef EVAL	
		freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	#endif
	int N;
	cin >> N;
	vector <int> v(N);
	for(int i = 0; i < N; i++){
		cin >> v[i];
	}
	for(int i = N - 2; i >= 0; i--){
		if(v[i] > v[i + 1]){
			v[i]--;
		}
		if(v[i] > v[i + 1]){
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	int ans = n;
	rep(i, n + 1) {
		int cnt = 0;
		int t = i;
		while (t > 0) {
			cnt += t % 6;
			t /= 6;
		}
		t = n - i;
		while (t > 0) {
			cnt += t % 9;
			t /= 9;
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
	ios::sync_with_stdio(0);
	int tc,a,b,aa,bb;
	while(cin>>tc){
		aa=bb=0;
		for(int i=0;i<tc;i++){
			cin>>a>>b;
			(a>aa)&&(aa=a,bb=b);
		}
		cout<<aa+bb<<"\n";
	}
} 

Measured memory_bytes: 256