akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MOD = 1e9+7;

template <std::uint_fast64_t Modulus> class modint {
	using u64 = std::uint_fast64_t;

public:
	u64 a;

	constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
	constexpr u64 &value() noexcept { return a; }
	constexpr const u64 &value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept {
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept {
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept {
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept {
		return modint(*this) /= rhs;
	}
	constexpr modint &operator+=(const modint rhs) noexcept {
		a += rhs.a;
		if (a >= Modulus) {
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint &operator-=(const modint rhs) noexcept {
		if (a < rhs.a) {
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint &operator*=(const modint rhs) noexcept {
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint &operator/=(modint rhs) noexcept {
		u64 exp = Modulus - 2;
		while (exp) {
			if (exp % 2) {
				*this *= rhs;
			}
			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}
	
	friend ostream &operator<<(ostream &s,const modint &rhs) noexcept {
		return s << rhs.a;
	}
	
	modint pow(ll y) noexcept {
		modint result(1);
		modint x(a);
		
		while ( y ){
			if ( y & 1 )
				result *= x;
			x *= x;
			y >>= 1;
		}
		return result;
	}
};

using mint = modint<MOD>;


ll n, k;
mint ct[100001]; 

mint pown_table[100001];

// x^n%MOD を計算
mint pown( ll x ){
	if ( pown_table[x].value() == 0 ){
		mint mx = x;
		pown_table[x] = mx.pow(n);
	}
	return pown_table[x];
}



int main(){
	cin >> n >> k;
	
	for ( int gcd = k; gcd >= 1; gcd-- ){
		ll m = k / gcd;
		ct[gcd] += pown(m);
		
		for ( int g = gcd*2; g <= k; g += gcd )
			ct[gcd] -= ct[g];
	}
	
	mint result = 0;
	for ( int gcd = 1; gcd <= k; gcd++ ){
		result += ct[gcd]*gcd;
	}
	
	cout << result << endl;
	
	return 0;
}




Measured memory_bytes: 4492
W = []
K = []

for i in range(10) :
    W.append(int(input()))
    
for j in range(10) :
    K.append(int(input()))
    
Ws = sorted(W, reverse = True)
Ks = sorted(K, reverse = True)

w = 0
k = 0

for i in range(3) :
    w += Ws[i]
    k += Ks[i]
    
print(w, k)


Measured memory_bytes: 5600
n=gets.to_i
a=gets.split.map{|i|(i=i.to_i)%2>0?0:i%4>0?1:2}
a,b,c=(0..2).map{|i|a.count i}
puts (a>c&&(a+c<n||a-1>c))?:No:"Yes"

Measured memory_bytes: 8452
#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<ll, ll> 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; }

template<typename T>
struct BIT{
    private:
        vector<T> array;
        const int n;
    public:
        BIT(int _n) : array(_n + 1, 0), n(_n) {}
        // [1, i], i is 1-indexed
        T sum(int i){
            T s = 0;
            while(i > 0){
                s += array[i];
                i -= i & -i;
            }
            return s;
        }
        // [i, j), i and j are 1-indexed
        T sum(int i, int j){
            T ret_i = sum(i-1);
            T ret_j = sum(j);
            return ret_j - ret_i;
        }
        // i is 1-indexed
        void add(int i, T x){
            while(i <= n){
                array[i] += x;
                i += i & -i;
            }
        }

        // debug
        void print(){
            for(int i = 1; i < (int)array.size(); ++i){
                cout << sum(i, i+1) << " ";
            }
            cout << endl;
        }
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	ll d, a;
	cin >> n >> d >> a;
	vector<P> v(n+1);
	rep(i,n) cin >> v[i+1].first >> v[i+1].second;
	sort(v.begin(), v.end());
	ll ans = 0, sum = 0;
	BIT<ll> bit(n+5);
	for(int i = 1; i <= n; ++i){
		ll x = v[i].first;
		ll h = v[i].second - (sum - bit.sum(i));
		if(h <= 0) continue;
		ll cnt = (h + a - 1) / a;
		ans += cnt;
		ll dam = a * cnt;
		sum += dam;
		int ok = i, ng = n+1;
		while(ng - ok > 1){
			int mid = (ok + ng) / 2;
			ll y = v[mid].first;
			if(y <= x + 2*d) ok = mid;
			else ng = mid;
		}
		bit.add(ok+1, dam);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7940
#include <bits/stdc++.h>
#define FOR(i,a,b)  for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n)    FOR(i,0,n)
#define RER(i,n)    FOR(i,0,(n+1))
#define pb          push_back
#define mp(a,b)     make_pair((a),(b))
#define mset(m,v)   memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pair<ll, ll> > vpll;
typedef vector<string> vs;
typedef long double ld;
const double EPS    = 1e-10;
const int INF       = 1e+9;
const double PI     = acos(-1);


auto main() -> int
{
    string str;
    cin >> str;

    str.insert(4, 1, ' ');
    cout << str << endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(i,e) for(ll i=0;i<e;i++ )
typedef pair<ll,ll> P;
const ll mod = 1e9+7;
const ll INF = INT32_MAX;
ll i;


int main(){
    ll T,X;
    cin>>T>>X;
    cout<<1.0*T/X<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';

const int MAX = 5100000;
const int MOD = 998244353;

long long fac[MAX], finv[MAX], inv[MAX];
using namespace std;

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}



// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


using namespace std;

int main(void){
    COMinit();
    ll N, M, K;
    cin>>N>>M>>K;
    ll count=0;
    rep(i, K+1){
        ll th=M;
        th*=(COM(N-1, i)%MOD);
        th%=MOD;
        //cout<<COM(N-1, i)<<endl;
        th=th*(modpow(M-1, N-1-i, MOD)%MOD);
        //cout<<modpow(M-1, N-1-i, MOD)%MOD<<sp;
        count+=(th%MOD);
        count%=MOD;
    }
    cout<<count<<endl;
    return 0;
}


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

int main()
{
  ll n,k,i;
  cin>>n>>k;
  vector<ll>v;
  ll arr[n+1];
  for(i=1; i<=n; i++)
    cin>>arr[i];
  map<ll,ll>m;
  m[1]=1;
  v.push_back(1);
  ll p=1;
  while(1)
  {
     if(m[arr[p]]==1)
     {
      v.push_back(arr[p]);
      m[arr[p]]+=1;
      break;
     } 
     else
     {
      v.push_back(arr[p]);
      m[arr[p]]=1;
      p=arr[p];
     }
  }
  vector<ll>v1,v2;
  for(auto x: v)
  {
    if(m[x]==1)
      v1.push_back(x);
    else
      break;
  }

  int flag=0;
  for(auto x: v)
  { 
    if(m[x]==3)
      break;
    if(flag==1 || m[x]==2)
    {
      if(m[x]==2)
        m[x]+=1;
      v2.push_back(x);
      flag=1;
    }
    else
    {
      continue;
    }
  }
  // for(auto x: v1)
  //   cout<<x<<" ";
  // cout<<'\n';
  // for(auto x: v2)
  //   cout<<x<<" ";
  // cout<<'\n';
  k+=1;
  if(k<=v1.size())
    cout<<v1[k-1]<<'\n';
  else
  {
    k-=v1.size();
    ll no=k%v2.size();
    if(no==0)
    {
      cout<<v2[v2.size()-1]<<'\n';
    }
    else
      cout<<v2[no-1]<<'\n';
  }
  return 0;
}

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

int main() {
    ll n, k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<int> s;
    vector<int> ord(n + 1, -1);
    int c = 1, l = 0;

    {
        int v = 1;
        while (ord[v] == -1) {
            ord[v] = s.size();
            s.push_back(v);
            v = a[v - 1];
        }
        c = s.size() - ord[v];
        l = ord[v];
    }

    if (k < l)
        cout << s[k] << endl;
    else {
        k -= l;
        k %= c;
        cout << s[l + k] << endl;
    }

    return 0;
}


Measured memory_bytes: 5888
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define rep(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
 
using namespace std;
 
 
int main(){
  int e;
  while(cin>>e,e){
		int not_dp = 10000000;
        for(int i = 0;i*i*i<=e;i++){
					for(int j = 0;j*j+i*i*i<=e;j++){
						int x = e - i*i*i - j*j;
						not_dp = min(not_dp,x+i+j);
					}
				}
				cout << not_dp << endl;
  }
  return 0;
}

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

bool solve();
bool is_in(int, int);

int main()
{

    if (solve()) printf("Yes\n");
    else printf("No\n");

    return 0;
}

int n, m;
char a[50][64], b[50][64];

bool solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", a[i]);
    for (int i = 0; i < m; i++) scanf("%s", b[i]);

    for (int i = 0; i + m <= n; i++)
    {
        for (int j = 0; j + m <= n; j++)
        {
            if (is_in(i, j)) return true;
        }
    }
    return false;
}

bool is_in(int top, int left)
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (b[i][j] != a[top + i][left + j]) return false;
        }
    }
    return true;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <random>
#include <chrono>
#include <iomanip>
#define lint unsigned long long int
#define FOR(x, to) for(int x=0; x<(int)(to); x++)
#define DUMP(ar) for(auto itd=begin(ar); itd != end(ar); itd++) cout << "["s << itd - begin(ar) << "]:"s << *itd << endl
#define DUMPL(ar) for(auto itd=begin(ar); itd != end(ar); itd++) { cout << *itd; if(end(ar)-itd > 1) cout << ' '; } cout << endl
#define COUT(x) cout << (x) << endl
#define VCIN(ar) for(auto &vcin: (ar)) cin >> vcin
#define ALL(ar) ar.begin(), ar.end()
#define LOOPD(i) cout << "ループ["s << i << "]回目---------------"s << endl
using namespace std;
// lint:64ビット 10^19

lint gcd(lint x, lint y){
    if(y > x){
        lint tmp = x;
        x = y;
        y = tmp;
    }

    lint r = x % y;
    while(r != 0){
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}

lint lcm(lint x, lint y){
    lint tmp = gcd(x, y);
    return (x * y) / tmp;
}

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

    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    VCIN(a);
    vector<int> half = a;
    for(auto &i: half) i /= 2.0;

    lint l = 1;
    for(auto &t: half) l = lcm(t, l);

    for(int i=0; i<n; i++){
        if((l / half[i]) % 2 == 0){
            COUT("0"s);
            return 0;
        }
    }

    COUT(((m/l)+1) / 2);

    return 0;
}

Measured memory_bytes: 1024
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

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

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};




signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;

    ll n,m;
    ll p[100010];
    string s[100010];
    cin>>n>>m;
    rep(i,m){
        cin>>p[i]>>s[i];
    }
    ll t[100010]={};
    ll ans=0;
    ll wa[100010]={};
    ll answ=0;
    rep(i,m){
        if(s[i]=="AC"){
            if(t[p[i]]==0){
                ans++;
                t[p[i]]=1;
                answ+=wa[p[i]];
            }
        }
        else{
            wa[p[i]]++;
        }
    }
    cout<<ans<<" "<<answ<<endl;
    return 0;
}

Measured memory_bytes: 8064
#include<stdio.h>

int main(){
	int H=0,W=0;
	while(true){
		//たて→H よこ→W
		scanf("%d",&H);
		scanf("%d",&W);
		if(H==0 && W==0){
			break;
		}
		for(int i=0; i<H; i++){
			if(i%2==1){
				for(int j=0; j<W; j++){
					if(j%2==1){
						printf("#");
					}else{
						printf(".");
					}
				}
			}else{
				for(int j=0; j<W; j++){
					if(j%2==1){
						printf(".");
					}else{
						printf("#");
					}
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}



Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
//自作関数
template<class T> ll llpow(T x,T n){ll ans=1;while(n--){ans*=x;}return ans;}

#define rep(i,n) for(ll i=0;i<(ll)n;i++)
#define rep2(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)

long long INF = 1LL<<60;
int INFi = 1<<30;
int wid=20000;
int main(){
    int h,n;
    cin>>h>>n;
    vector<int> a(n),b(n);
    rep(i,n)cin>>a[i]>>b[i];
    int dp[h+1];
    rep(i,h+1)dp[i]=INFi;
    dp[0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<h;j++){
            int mj=min(j+a[i],h);
            chmin(dp[mj],dp[j]+b[i]);
        }
    }
    cout<<dp[h]<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <iomanip>

int main() {
    static const double pi = 3.141592653589793;

    int A, B, H, M;
    std::cin >> A >> B >> H >> M;

    double c = H * 30 + M * 0.5;
    double d = M * 6;
    if (c > d) std::swap(c, d);
    double r = std::min(d - c, 360 - d + c) * pi / 180;

    double res = A * A + B * B - 2 * A * B * std::cos(r);
    double ans = std::sqrt(res);
    std::cout << std::fixed << std::setprecision(12);
    std::cout << ans << "\n";
}

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

using i64 = int64_t;

int main(){
    int n;
    cin >> n;
    vector<i64> v(n+1);
    i64 sum = 0;
    for(int i=1;i<=n;++i){
        i64 a;
        cin >> a;
        v[i] = v[i-1] + a;
        sum += a;
    }
    i64 ans = 1e18;
    for(int i=1;i<n;++i){
        i64 cost = abs(sum - 2*v[i]);
        ans = min(ans, cost);
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<string.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

int h, w;

char grid[50][50];
int d[50][50];
int inf = -1;
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

int bfs() {
	int sy = 0, sx = 0, gy = h - 1, gx = w - 1;
	int r = h, c = w;
	queue<pair<int, int>>que;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			d[i][j] = inf;
		}
	}
	que.push(pair<int, int>(sy, sx));
	d[sy][sx] = 0;
	while (que.size() > 0) {
		pair<int, int>p = que.front();
		que.pop();
		if (p.first == gy && p.second == gx) {
			break;
		}
		for (int i = 0; i < 4; i++) {
			int ny = p.first + dy[i], nx = p.second + dx[i];
			if (0 <= ny && ny < r && 0 <= nx && nx < c && grid[ny][nx] != '#' && d[ny][nx] == inf) {
				que.push(pair<int, int>(ny, nx));
				d[ny][nx] = d[p.first][p.second] + 1;
			}
		}
	}
	return d[gy][gx]+1;
}

int main() {
	cin >> h >> w;
	int hcount = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			cin >> grid[i][j];
			if (grid[i][j] == '.') {
				hcount++;
			}
		}
	}
	int ans = bfs();
	if (ans != 0) {
		cout << hcount - ans << endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (Math.abs(x-a)>=Math.abs(x-b)){
        	System.out.print("B");	
        }else{
        	System.out.print("A");
        }
    }
}

Measured memory_bytes: 21844
from collections import deque

N = int(input())

def bfs(s):
    que = deque()
    que.append(s)
    cnt = 0
    while que.__len__() != 0:
        s = que.popleft()
        for ds in '753':
            ss = s + ds
            if int(ss) > N:
                continue
            if all(ss.count(i) > 0 for i in '753'):
                cnt += 1
            que.append(ss)
    return cnt

ans = 0
ans += bfs('3')
ans += bfs('5')
ans += bfs('7')

print(ans)

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

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

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

const int MAXN = 2e5 + 5;

int v[MAXN];
ll sum[MAXN];

ll get_sum(int l, int r) {
	return sum[r] - sum[l - 1];
}

ll get_mid_sum(int l, int r) {
	if (get_sum(l, l) >= get_sum(l + 1, r)) {
		return get_sum(l, l);
	}
	/*if (get_sum(r, r) >= get_sum(l, r - 1)) {
		return get_sum(r, r);
	}*/
	int l1 = l, r1 = r;
	for(; l1 + 1 < r1; ) {
		int mid = (l1 + r1) / 2;
		if (get_sum(l, mid) < get_sum(mid + 1, r)) {
			l1 = mid;
		} else {
			r1 = mid;
		}
	}
	ll mn = INF, mins = 0;
	for(int i = max(l, l1 - 3); i <= min(r - 1, l1 + 3); i++) {
		ll cur = abs(get_sum(l, i) - get_sum(i + 1, r));
		if (cur < mn) {
			mn = cur;
			mins = get_sum(l, i);
		}
	}
	return mins;
}

ll vv[4];

void solve(){
	int n;
	scanf("%d", &n);
	REPN(i, 1, n) {
		scanf("%d", &v[i]);
		sum[i] = sum[i - 1] + v[i];
	}
	ll ans = INF;
	REPN(i, 2, n - 2) {
		ll s1 = get_mid_sum(1, i);
		ll s2 = get_mid_sum(i + 1, n);
		vv[0] = s1;
		vv[1] = get_sum(1, i) - s1;
		vv[2] = s2;
		vv[3] = get_sum(i + 1, n) - s2;
		sort(vv, vv + 4);
		ans = min(ans, vv[3] - vv[0]);
	}
	cout << ans << endl;
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 2560
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define N 1000010


int main()
{
    int n,x;
    scanf("%d",&n);
    int ans=0,maxx=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(x>=maxx)
            ans++,maxx=x;
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		ProblemB solver = new ProblemB();
		solver.solve(1, in, out);
		out.close();
	}

	static class ProblemB {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int k = in.nextInt();
			int t = in.nextInt();
			int[] a = new int[t];
			for (int i = 0; i < t; i++) {
				a[i] = in.nextInt();
			}
			Arrays.sort(a);
			int p = a.length - 1;
			if (a[p] * 2 < k) {
				out.println(0);
				return;
			}
			int[] b = new int[k];
			for (int i = 0; i < k; i += 2) {
				while (a[p] == 0) {
					--p;
				}
				b[i] = p;
				--a[p];
			}
			int odd = k - 1;
			if (odd % 2 == 0) {
				--odd;
			}
			for (int i = odd; i >= 0; i -= 2) {
				while (a[p] == 0) {
					--p;
				}
				b[i] = p;
				--a[p];
			}
			// out.println(Arrays.toString(b));
			int ans = 0;
			for (int i = 1; i < k; i++) {
				if (b[i] == b[i - 1]) {
					++ans;
				}
			}
			out.println(ans);
		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(in.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

	}
}



Measured memory_bytes: 8404
#include<stdio.h>
int main(void){
    int a,b,W,H;
    while(1){
        scanf("%d%d",&H,&W);
        if (H==0||W==0)break;
        for(a=0;a<H;a++){
            for(b=0;b<W;b++){
                printf("#");
            }
        printf("\n");
    }
    printf("\n");
    }
    return 0;
}

Measured memory_bytes: 572
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string.h> 

#include<math.h>//pow(a,b)函数 ,abs(绝对值）函数 

using namespace std;
typedef long long ll;


int main(){
	int n,x=0,y=0;
	cin>>n;
	int a[n],b[n];
	for(int i=0;i<n;i++) 
		cin>>a[i];
	for(int j=0;j<n;j++) 
		cin>>b[j];
	do{x+=1;
	}while( next_permutation (a,a+n));
	do{y+=1;
	}while( next_permutation (b,b+n));
	
	cout<<abs(x-y);
	
	

	 

	
	return 0;
}





Measured memory_bytes: 3632
fn dig(currentChars: &Vec<char>, nChars: &Vec<char>, currentPoint: u32, a: u32, b: u32, isMax: bool) -> u32{
    if nChars.len() == 0 {
        if a > currentPoint || currentPoint > b {
            return 0;
        }
        let pointString: String = currentChars.iter().cloned().collect::<String>();
        let pointNum: u32 = pointString.parse().unwrap();
        return pointNum;
    }

    let mut choisebleNumber;
    let mut lastChars;
    let mut firstNumber;
    let mut tempChars = nChars.clone();
    if isMax {
        lastChars = tempChars.split_off(1);
        firstNumber = tempChars[0].to_digit(10).expect("失敗した？？");
        choisebleNumber = 0..firstNumber+1;
    } else {
        choisebleNumber = 0..10;
        lastChars = tempChars.split_off(1);
        firstNumber = 0;
    }

    let mut pointSum = 0;
    for i in choisebleNumber {
        let addedPoint = currentPoint + i;

        // 多すぎたらまずは足切り
        if addedPoint>b {
            break;
        }

        let _isMax = isMax && firstNumber == i;

        let mut _currentChars = currentChars.clone();

        let mut iChar = [std::char::from_digit(i, 10).unwrap()].to_vec();
        _currentChars.append(&mut iChar);

        pointSum = pointSum + dig(&mut _currentChars, &lastChars, addedPoint, a, b, _isMax);
    }

    return pointSum;
}

fn main() {
    let inputs: Vec<u32> = read().trim().split_whitespace().map(|x| x.parse().ok().unwrap()).collect();
    let n: u32 = inputs[0];
    let a = inputs[1];
    let b = inputs[2];

    let mut nChars = n.to_string().chars().collect();

    let empty: Vec<char> = "".chars().collect();

    let point = dig(&empty, &nChars, 0, a, b, true);
    println!("{}", point);
}

fn read() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s);
    s.to_string()
}


Measured memory_bytes: 4352
#include <stdio.h>

/* {1,2,3} -> ... -> {3,2,1} */
int next_permutation(int arr[],int n) {
	int target;
	int i;
	int temp;
	for (i = n - 2; i >= 0; i--) {
		if (arr[i] < arr[i + 1]) break;
	}
	if (i < 0) return 0;
	target = i;

	for (i = 0; target + i + 1 < n - i - 1; i++) {
		temp = arr[target + 1 + i];
		arr[target + 1 + i] = arr[n - 1 - i];
		arr[n - i - 1] = temp;
	}

	for (i = target + 1; i < n; i++) {
		if (arr[i] > arr[target]) break;
	}
	temp = arr[i];
	arr[i] = arr[target];
	arr[target] = temp;
	return 1;
}

int main(void) {
	int N;
	int a[16], w[16];
	int order[16];
	int i;
	int mikakosi = -1;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &a[i]) != 1) return 1;
	}
	for (i = 0; i < N; i++) {
		if (scanf("%d", &w[i]) != 1) return 1;
	}
	for (i = 0; i < N; i++) {
		order[i] = i;
	}
	do {
		int parunyasu = 0;
		for (i = 0; i < N; i++) {
			if (a[order[i]] && !a[order[(i + 1) % N]]) parunyasu += w[order[i]];
			else if (!a[order[i]] && a[order[(i + N - 1) % N]]) parunyasu += w[order[i]];
		}
		if (mikakosi < 0 || parunyasu < mikakosi) mikakosi = parunyasu;
	} while (next_permutation(order, N));
	printf("%d\n", mikakosi);
	return 0;
}



Measured memory_bytes: 2144
using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int count = int.Parse(Console.ReadLine());
        var line = Console.ReadLine();
        int min = 0;
        for(int i = 1; i < count; ++i)
        {
            if (line[i] == 'E') ++min;
        }
        int now = min;
        for(int leader = 0; leader < count - 1; ++leader)
        {
            if (line[leader] == 'W') ++now;
            if (line[leader + 1] == 'E') --now;
            if (now < min) min = now;
        }
        Console.WriteLine(min);
    }
}


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

class I {
  public:
    ll u, v, w;

    I(ll uu, ll vv, ll ww) {
      u = uu;
      v = vv;
      w = ww;
    }
};

class A {
  public:
    int n, m;
    vector<I> edges; 
    A(int nn, int mm, vector<I> e) {
      n = nn;
      m = mm;
      edges = e;
    }
};

A d(ll l) {
  int n = 2;
  vector<I> edges;

  while(true) {
    if(pow(2, n-1) <= l && l < pow(2, n)) {
      break;
    } 
    n++;
  }

  for(int i =1;i<n;i++) {
    I e(i, i+1, pow(2, i-1));
    edges.push_back(e);
    I e0(i, i+1, 0);
    edges.push_back(e0);
  }
  if(pow(2, n-1) == l) {
    return A(n, edges.size(), edges);
  }
  ll remain = l-1;
  ll offset = pow(2, n-1) -1;
  for(int i=n-2; i>=0; i--) {
    if(offset + pow(2, i) <= remain) {
      //cout << "remain -> " << remain << " path: " << pow(2, i) << endl;
      I e(i+1, n, remain - pow(2, i) + 1);
      remain -= pow(2, i);
      edges.push_back(e);
    }
  }

  return A(n, edges.size(), edges);
}

int main() {
  ll l;
  cin >> l;
  A a = d(l);
  cout << a.n << " " << a.m << endl;
  for(auto e: a.edges) {
    cout << e.u << " " << e.v << " " << e.w << endl;
  }
}

Measured memory_bytes: 4080
#include<iostream>
using namespace std;
int main(){
  int n,m,s,g1,g2;
  while(cin>>n>>m>>s>>g1>>g2,n||m||s||g1||g2){
    int i,j,k;
    int b1,b2,c;
    int d[105][105];
    int inf = 1<<20;
    for(i=1;i<=n;i++){
      for(j=1;j<=n;j++){
	if(i==j) d[i][j]=0;
	else d[i][j]=inf;
      }
    }
    for(i=0;i<m;i++) {
      cin >> b1 >> b2 >> c;
      d[b1][b2]=c;
    }
    for(k=1;k<=n;k++){
      for(i=1;i<=n;i++){
	if(d[i][k]==inf) continue;
	for(j=1;j<=n;j++){
	  if(d[k][j]==inf) continue;
	  d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	} 
      } 
    }
    int o=inf;
    for(i=1;i<=n;i++){
      o=min(o,d[s][i]+d[i][g1]+d[i][g2]);
    }
    cout << o << endl;
  }

}

Measured memory_bytes: 1200
import numpy as np
N = int(input())
A = np.array([list(map(int, input().split())) for _ in range(2)])

U = A[0][1:]
D = A[1][:-1]
i = -1
ans = 0
if N == 1:
    ans = A[0][0] + A[1][N - 1]
for i in range(N - 1):
    sum_U = U[:i].sum()
    sum_D = D[i:].sum()
    v = A[0][0] + A[1][N - 1] + sum_U + sum_D
    ans = max(ans, v)
print(ans)


Measured memory_bytes: 12500
#include <bits/stdc++.h>
using namespace std;
// type alias
typedef long long LL;
typedef pair<int,int> II;
typedef tuple<int,int,int> III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))
// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');
// debug cerr
template<class Iter> void __kumaerrc(Iter begin, Iter end) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; }
void __kumaerr(istream_iterator<string> it) { (void)it; cerr<<endl; }
template<typename T, typename... Args> void __kumaerr(istream_iterator<string> it, T a, Args... args) { cerr<<*it<<"="<<a<<", ",__kumaerr(++it, args...); }
template<typename S, typename T> std::ostream& operator<<(std::ostream& _os, const std::pair<S,T>& _p) { return _os<<"{"<<_p.first<<','<<_p.second<<"}"; }
#define __KUMATRACE__ true
#ifdef __KUMATRACE__
#define dump(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); __kumaerr(_it, args); }
#define dumpc(ar) { cerr<<#ar<<": "; FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
#define dumpC(beg,end) { cerr<<"~"<<#end<<": "; __kumaerrc(beg,end); }
#else
#define dump(args...)
#define dumpc(ar)
#define dumpC(beg,end)
#endif

// $ cp-batch ModSum | diff ModSum.out -
// $ g++ -std=c++14 -Wall -O2 -D_GLIBCXX_DEBUG -fsanitize=address ModSum.cpp && ./a.out

/*
 
 9/1/2019
 
 5:14-
 
 */

LL N;

LL solve() {
  LL res=N*(N-1)/2;
  return res;
}

void test() {
  FORE(i,1,10) {
    N=i;
    LL res=0;
    VI P(N); REP(j,N) P[j]=j+1;
    do {
      LL x=0;
      REP(j,N) x+=(j+1)%P[j];
      SMAX(res,x);
    } while(next_permutation(ALL(P)));
    assert(res==solve());
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout<<setprecision(12)<<fixed;
  
//  test();
  
  cin>>N;
  cout<<solve()<<endl;
  
  return 0;
}


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

int main() {
  vector<int> vec(5);
  int k;
  cin >> vec[0] >> vec[1] >> vec[2] >> vec[3] >> vec[4] >> k;
  bool flg = true;
  sort(vec.begin(), vec.end());

  if(vec[4]-vec[0] > k) {
    flg = false;
  }
  flg == true ? cout << "Yay!" << endl : cout << ":(" << endl;
}

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

int main() {
  int N, D, X;
  scanf("%d%d%d", &N, &D, &X);

  vector<int> A(N, 0);
  for (int i = 0; i < N; i++) {
    scanf("%d", &A.at(i));
  }

  int ans = X;
  for (int i = 0; i < N; i++) {
    int days = 1;
    while (days <= D) {
      ans++;
      days += A.at(i);
    }
  }

  printf("%d", ans);
  return 0;
}


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

using ll = long long;
//print(fixed << setprecision(10));
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repk(i,n,k) for(int i = k; i < (n); i++)
#define all(n) n.begin(), n.end()
#define print(n) cout << n << endl
double PI = acos(-1.0);
int INF = 1e9;
ll LINF = 1e18;
ll MOD = 1e9+7;


int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    string t;
    cin >> t;
    int l = t.size();

    rep(i,l){
        if(t[i]=='?'){
            if(i==l-1){
                t[i] = 'D';
            }
            else if(i==0){
                if(t[1] == 'P') t[i] = 'D';
                else t[i] = 'P';
            }
            else{
                if(t[i-1] == 'P') t[i] = 'D';
                else if(t[i+1] == 'P') t[i] = 'D';
                else t[i] = 'P';
            }
        }
    }
    print(t);
    return 0;
}

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

int main() {
    int r,d;
    cin>>r>>d;
    vector<int> x(20);
    cin>>x.at(0);
    for (int i=1; i<=10; i++) {
        x.at(i)=r*x.at(i-1)-d;
        cout<<x.at(i)<<endl;
    }
}

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

char s[500005];
int num[500005];


int main()
{

    scanf("%s",s+1);
    long long n=strlen(s+1);
    long long sum=0ll;
    for(int i=1;i<=n;){
        long long l=0ll,r=0ll;
        while(i<=n&&s[i]=='<')
        {
            i++;
            l++;
        }
        while(i<=n&&s[i]=='>')
        {
            i++;
            r++;
        }
        sum+=(l-1ll)*l/2ll;
        sum+=(r-1ll)*r/2ll;
        sum+=max(l,r);
    }
    printf("%lld",sum);
    return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define INF 1e9

static const int seed=20;
static const int D=365;
static const int ntype=26;
static int ans[D+1];
static int max_score=-INF;
static int t=130000;
class Contest{
public:
    Contest(){
        last=0;
    }
    int s[D+1];
    int c;
    int last;
};

static Contest contest[ntype+1];

void Input(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int d;
    cin>>d;
    for(int i=1;i<=ntype;++i){
        int t;
        cin>>t;
        contest[i].c=t;
    }
    for(int day=1;day<=D;++day){
        for(int type=1;type<=ntype;++type){
            int t;
            cin>>t;
            contest[type].s[day]=t;
        }
    }
}

int evaluate(){
    int sum=0;
    vector<int> l(ntype+1,0);
    for(int day=1;day<=D;++day){
        int type=ans[day];
        sum+=contest[type].s[day];
        l[type]=day;
        for(int t=1;t<=ntype;++t){
            sum-=contest[t].c*(day-l[t]);
        }
    }
    return sum;   
}

void Output(){
    for(int d=1;d<=D;++d) cout<<ans[d]<<'\n';
}

void Init(){
    for(int d=1;d<=D;++d) ans[d]=rand()%ntype+1;
}

void Greedy(){
    vector<int> l(ntype+1,0);
    int score=0;
    for(int d=1;d<=D;++d){
        for(int i=1;i<=ntype;++i) score-=contest[i].c*(d-l[i]);
        int temp=score;
        int t=-1;
        for(int i=1;i<=ntype;++i){
            int k=contest[i].s[d]+contest[i].c*(d-l[i])+score;
            if(k>temp){
                temp=k;
                t=i;
            }
        }
        ans[d]=t;
        l[t]=d;
    }
}

void change(){
    int p=rand()%D+1;
    int temp=ans[p];
    ans[p]=rand()%ntype+1;
    int temp_score=evaluate();
    if(max_score<temp_score) max_score=temp_score;
    else ans[p]=temp;
}

void swap(){
    int p1=rand()%D+1;
    int p2=rand()%D+1;
    while(p1==p2) p2=rand()%D+1;
    int temp=ans[p1];
    ans[p1]=ans[p2];
    ans[p2]=temp;
    int temp_score=evaluate();
    if(max_score<temp_score) max_score=temp_score;
    else{
        ans[p2]=ans[p1];
        ans[p1]=temp;
    }
}

void solve(int times){
    max_score=evaluate();
    for(int i=0;i<times;++i){
        swap();
        change();
    }
}

int main(){
    srand(seed);
    Input();
    Greedy();
    solve(t);
    Output();
}


Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl '\n'
#define pb push_back
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define mm memset
#define PI 3.14159265358979323846264338327950288419716939937510
#define MAXI (ll)2e5+3
#define M 998244353 
void solve(){

  string s,t;
  cin>>s>>t;
  int count=0;
  for(int i=0;i<t.length();i++){
    if(s[i]!=t[i]){
      count++;
    }
  }
  cout<<count<<endl;
}
int main(){

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll t=1;
  //cin>>t;
  for(ll i=0;i<t;i++){
    solve();
  }
  return 0;
} 

Measured memory_bytes: 3796
package main

import (
    . "fmt"
    "math"
)

func main() {
    var a, b, c, d float64
    Scanf("%f %f %f %f", &a, &b, &c, &d)

    if math.Abs(c - a) <= d || math.Abs(b - a) <= d && math.Abs(c - b) <= d {
        Println("Yes")
    } else {
        Println("No")
    }
 }


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std ;
int main () {
// input
int N; cin >> N ;
vector <int > V ( N );
for ( int i = 0; i < N ; ++ i ) {
cin >> V [ i ];
}
vector <int > C ( N );
for ( int i = 0; i < N ; ++ i ) {
cin >> C [ i ];
}
// compute
int ans = 0;
for ( int i = 0; i < N ; ++ i ) {
if ( V [ i ] > C [ i ]) {
ans += V [ i ] - C [ i ];
}
}
// output
cout << ans << endl ;
}

Measured memory_bytes: 256
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
mod = 10 ** 9 + 7
dp = [0] * (1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k - 1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])


Measured memory_bytes: 58220
#include<bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
const int mod=1e9+7;

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


vector<int>p(100005);
vector<int>sz(100005);


int find(int x)
{
  if(x==p[x])return x;
  else return p[x]=find(p[x]);
}
void uni(int x,int y)
{
  int a=find(x),b=find(y);
  if(a==b)return;

  if(sz[a]<sz[b])
  swap(a,b);

  p[b]=a;
  sz[a]+=sz[b];
}

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

int n,m,k;

map<pii,int>mp;
cin>>n>>m>>k;

for(int i=0;i<=n;i++)
{
  p[i]=i;
  sz[i]=1;
}
set<int>g[n+1];
for(int i=0;i<m;i++)
{
  int x,y;
  cin>>x>>y;
  uni(x,y);
  mp[{x,y}]++; mp[{y,x}]++;
  g[x].insert(y); g[y].insert(x);
}
for(int i=0;i<k;i++)
{
    int x,y;
  cin>>x>>y;

  mp[{x,y}]++; mp[{y,x}]++;   g[x].insert(y); g[y].insert(x);
}

for(int i=1;i<=n;i++)
{
  int x=sz[find(i)];
 
  for(auto j : g[i])
  {
    if(find(i)==find(j))x--;
  }
 cout<<x-1<<" ";


}




  
}



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

int flag[10];

int isPossible(int i){
  while(i){
    if(flag[i%10])return 0;
    i/=10;
  }
  return 1;
}

int main(){
  int n,k,p;
  cin>>n>>k;
  while(k--){
    cin>>p;
    flag[p]=1;
  }
  for(int i=n;;i++){
    if(isPossible(i)){
      cout<<i<<endl;
      exit(0);
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll gcd(ll a,ll b)
{
   	if(a<b)swap(a,b);
   	if(a%b)return gcd(b,a%b);
	else return(b);
}

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

int main()
{

	ll a,b,c,d,p,q;
	cin>>a>>b>>c>>d;	

	p=b-(b/c+b/d-b/lcm(c,d));
	q=(a-1)-((a-1)/c+(a-1)/d-(a-1)/lcm(c,d));
	cout<<p-q<<endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MAX=100020;
const int INF=1987654321;
struct town{
    int x,y,idx;
};
struct edge{
    int a,b,dist;
    bool operator<(const edge &p)const{
        return dist>p.dist;
    }
};
town a[MAX];
int chk[MAX];
bool cmp_x(town &a,town &b){
    return a.x<b.x;
}
bool cmp_y(town &a,town &b){
    return a.y<b.y;
}
int dist(town &a,town &b){
    return min(abs(a.x-b.x),abs(a.y-b.y));
}
vector<pii> conn[MAX];
priority_queue<edge> mst;
ll ans;
int n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y),a[i].idx=i+1;
    sort(a,a+n,cmp_x);
    for(int i=0;i<n-1;i++) {
        conn[a[i].idx].push_back(make_pair(a[i+1].idx,dist(a[i],a[i+1])));
        conn[a[i+1].idx].push_back(make_pair(a[i].idx,dist(a[i],a[i+1])));
    }
    sort(a,a+n,cmp_y);
    for(int i=0;i<n-1;i++) {
        conn[a[i].idx].push_back(make_pair(a[i+1].idx,dist(a[i],a[i+1])));
        conn[a[i+1].idx].push_back(make_pair(a[i].idx,dist(a[i],a[i+1])));
    }
    edge origin={0,0,INF};
    for(int i=1;i<=n;i++){
        for(int j=0;j<conn[i].size();j++) if(origin.dist>conn[i][j].second) origin={i,conn[i][j].first,conn[i][j].second};
    }
    mst.push(origin);
    while(!mst.empty()){
        edge tmp=mst.top();
        mst.pop();
        if(chk[tmp.a]==0||chk[tmp.b]==0){
            ans+=(ll)tmp.dist;
            if(chk[tmp.a]==0){
                chk[tmp.a]=1;
                for(int i=0;i<conn[tmp.a].size();i++) if(chk[conn[tmp.a][i].first]==0) mst.push({tmp.a,conn[tmp.a][i].first,conn[tmp.a][i].second});
            }
            if(chk[tmp.b]==0){
                chk[tmp.b]=1;
                for(int i=0;i<conn[tmp.b].size();i++) if(chk[conn[tmp.b][i].first]==0) mst.push({tmp.b,conn[tmp.b][i].first,conn[tmp.b][i].second});
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 11384
import copy

S=input()
Q=int(input())
Query=[]
temp=[]

revflag=0
sbef=[]
saft=[]

for i in range(Q):
    temp=input().split()
    if len(temp) ==1:
        revflag += 1
    else:
        if (revflag + int(temp[1])-1 )%2 == 0:
            sbef.append(temp[2])
        else:
            saft.append(temp[2])

ans=""

for i in range(len(sbef)):
    ans+=sbef[len(sbef)-i-1]

ans += S
for i in range(len(saft)):
    ans+=saft[i]

tmp=""
tmp2 = copy.copy(ans)


if revflag%2 ==1:
    for i in range(len(ans)):
        tmp+=tmp2[len(ans)-i-1]
    ans=tmp


print(ans)


Measured memory_bytes: 6224
#include<bits/stdc++.h>
#define ll long long
#define debug(a) cout<<a<<endl
#define pii pair<ll,ll>
#define INF (int) 1e9+7
#define maxn 109
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin>>n;
    priority_queue<pii,vector<pii>,greater<pii> >pq;
    for(int i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;
        pq.push({b,a});
    }
    bool cond=true;
    ll acttime=0;
    while(!pq.empty() && cond==true){
        auto x=pq.top();
        pq.pop();
        if(x.first<=acttime || acttime+x.second>x.first)cond=false;
        else acttime+=x.second;
    }
    if(cond)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
///usar double sempre ou long double
///pensar em casos que coisas dao negativas
///N esquecer de limpar as coisas em quest de varios testes
///OLHAR A COMPLEXIDADE PRA VER SE N PASSA POR BRUTE FORCE OU BRUTE FORCE COM ALGUMAS OTIMIZACOES



Measured memory_bytes: 6512
#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int h, a;
    cin >> h >> a;
    if (h % a==0) cout << h / a << endl;
    else cout << h / a + 1 << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<60;
const ll MOD=998244353LL;
template<class T> void chmin(T &a,T b){a=min(a,b);}
template<class T> void chmax(T &a,T b){a=max(a,b);}
template <typename T> class Segtree {
    inline T merge(const T &a, const T &b) { return max(a, b); }
    inline void act(T &a, const T &b) { a = b; }
    int n;
    T e;
    vector<T> dat;

  public:
    Segtree(int n_, T e) : e(e) {
        n = 1;
        while (n < n_) {
            n <<= 1;
        }
        dat.resize(2 * n, e);
    }
    void upd(int k, const T &x) {
        k += n;
        act(dat[k], x);
        k >>= 1;
        while (k > 0) {
            dat[k] = merge(dat[k << 1], dat[k << 1 | 1]);
            k >>= 1;
        }
    }
    T get(const int &a, const int &b, int k, int l, int r) {
        if (b <= l || r <= a) {
            return e;
        }
        if (a <= l && r <= b) {
            return dat[k];
        }
        return merge(get(a, b, k << 1, l, (l + r) >> 1),
                     get(a, b, k << 1 | 1, (l + r) >> 1, r));
    }
    inline T get(const int &a, const int &b) { //[a,b)
        if (a >= b) {
            return e;
        }
        return get(a, b, 1, 0, n);
    }
    int find(const int &a, const int &b, const T &x, int k, int l, int r) {
        if (b <= l || r <= a || dat[k] > x) {
            return -1;
        }
        if (k >= n) {
            return k - n;
        }
        int il = find(a, b, x, k << 1, l, (l + r) >> 1);
        if (il != -1) {
            return il;
        }
        return find(a, b, x, k << 1 | 1, (l + r) >> 1, r);
    }
    inline int find(const int &a, const int &b, const T &x) {
        if (a >= b) {
            return -1;
        }
        return find(a, b, x, 1, 0, n);
    }
};
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;cin>>n;
	vector<int> x(n);
	vector<P> v(n);
	for(int i=0;i<n;i++){
		cin>>v[i].first>>v[i].second;
		x[i]=v[i].first;
	}
	sort(all(v));
	sort(all(x));
	vector<int> r(n);
	vector<vector<int>> ls(n);
	Segtree<int> seg(n+1,-1);
	for(int i=n-1;i>=0;i--){
		int to=lower_bound(all(x),v[i].first+v[i].second)-x.begin();
		if(i+1<to){
			r[i]=seg.get(i+1,to);
		}else{
			r[i]=i;
		}
		seg.upd(i,r[i]);
		ls[r[i]].eb(i-1);
	}
	vector<ll> dp(n+1);
	dp[0]=1;
	for(int i=0;i<n;i++){
		for(auto &l:ls[i]){
			dp[i+1]+=dp[l+1];
			dp[i+1]%=MOD;
		}
		dp[i+1]+=dp[i];
		dp[i+1]%=MOD;
	}
	cout<<dp[n]<<endl;
}


Measured memory_bytes: 16512