akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define ld long double
#define int long long
#define double long double
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pi 3.141592653589793238
const int MOD = 1e9+7;
const int INF = 1LL<<60;


const int N = 2e5+5;

// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


void solve(){
    int n; cin>>n;
    vector<pii> f;
    vector<pii> b;
    int ans = 0;
    For(i, 0, n){
        int l, r, k; cin>>k>>l>>r;
        ans += min(l, r);
        if(l > r){
            f.pb({l-r, k});
        }
        else if(r > l){
            b.pb({r-l, k});
        }
    }
    sort(all(f)); reverse(all(f));
    sort(all(b)); reverse(all(b));
    set<int> s;
    For(i, 1, sz(f)+1){
        s.insert(i);
    }
    for(pii p: f){
        int ex = p.F;
        int pos = p.S;
        auto it = s.upper_bound(pos);
        if(it == s.begin())
            continue;
        it--;
        ans += ex;
        s.erase(it);
    }
    while(s.size()){
        s.erase(s.begin());
    }
    For(i, sz(f)+1, n+1){
        s.insert(i);
    }
    for(pii p: b){
        int ex = p.F;
        int pos = p.S;
        auto it = s.upper_bound(pos);
        if(it == s.end())
            continue;
        ans += ex;
        s.erase(it);
    }
    cout<<ans;
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1; 
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}



Measured memory_bytes: 11184
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

ll N, A, B;
vector<int> x(100001, 0);

int main(void){
    
    scanf("%lld %lld %lld", &N, &A, &B);
    for(int i = 0; i < N; ++i) scanf("%d", &x[i]);
    
    ll ans = 0;
    for(int i = 0; i < N - 1; ++i){
        ll dist = x[i + 1] - x[i];
        ans += (dist * A < B) ? dist * A : B;
    }
    printf("%lld\n", ans);
    
    return 0;
}

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

const ll INF = ll(1e12) + 1;

int main() 
{
    ll n;
    cin >> n;
    double t  = sqrt(n);
    ll r = (ll)t;

    ll ans = INF;
    for (ll i=1; i<=r; i++) {
        if (n % i == 0) {
            ll x = abs((n/i) -1 ) + abs(i -1);
            ans = min(x, ans);
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int A,B,C,D;
    cin>>A>>B>>C>>D;
    for(int i=1;i<1000;i++){
        if(i%2==1){
            C=C-B;
            if(C<=0){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
        else{
            A=A-D;
            if(A<=0){
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
}


Measured memory_bytes: 3632
N,M = map(int,input().split())
Bridge = [[int(x)-1 for x in input().split()] for _ in range(M)]

Parent = [-1] * N
Size = [1] * N

def Pr(x):
    if Parent[x] == -1:
        return x
    else:
        return Pr(Parent[x])

Igr = [{i} for i in range(N)]
Inconv = [N*(N-1)//2] * (M+1)

for i in range(M):
    A = Bridge[M-1-i][0]
    B = Bridge[M-1-i][1]
    if Pr(A) == Pr(B):
        Inconv[M-1-i] = Inconv[M-i]
    else:
        Inconv[M-1-i] = Inconv[M-i]-(Size[Pr(A)]*Size[Pr(B)])
        if Size[Pr(A)]<Size[Pr(B)]:
            P = B
            C = A
        else:
            P = A
            C = B
        Size[Pr(P)] = Size[Pr(P)] + Size[Pr(C)]
        Parent[Pr(C)] = Pr(P)

for i in range(1,M+1):
    print(Inconv[i])


Measured memory_bytes: 54192
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


n = int(readline())


def dfs(s):
    if int(s) > n:
        return 0
    flag = True
    for check in '753':
        if s.count(check) <= 0:
            flag = False
    if flag:
        x = 1
    else:
        x = 0
    for check in '753':
        x += dfs(s + check)
    return x


print(dfs('0'))


Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#define mp make_pair
#define pb push_back
using namespace std;

int a, b;


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

    cin >> a >> b;

    if(a + b == 15)
    {
        cout << '+' << endl;
        return 0;
    }
    if(a * b == 15)
    {
        cout << '*' << endl;
        return 0;
    }

    cout << 'x' << endl;


    return 0;
}


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

int main() {
    int K; cin >> K;
    long long sum = 0;
    for(int a=1; a<=K; ++a) {
        for(int b=1; b<=K; ++b) {
            for(int c=1; c<=K; ++c) {
                sum += gcd(gcd(a, b), c);
            }
        }
    }
    cout << sum << '\n';
}

Measured memory_bytes: 3624
N = int(input())

def f(l, r):
  cnt = 0
  if l == r and l <= N:
    cnt += 1
  if l*10 + r <= N:
    cnt += 1
  for c in range(1, 5):
    x = l*10**(c+1) + r
    i = 0
    I = int("9"*c)
    while x <= N and i <= I:
      cnt += 1
      x += 10
      i += 1
  return cnt

C = [[0]*9 for _ in range(9)]
ans = 0

for i in range(9):
  for j in range(9):
    C[i][j] = f(i+1, j+1)

for i in range(9):
  for j in range(9):
    ans += C[i][j] * C[j][i]

print(ans)

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

using namespace std;
typedef long long ll;

struct TreeNode {
    int val;
    vector<tuple<ll, ll> > conn;
    TreeNode(int x) {
      val = x;
    }
};

int main() {
  ll N; cin >> N;
  vector<TreeNode> nodes;
  for (ll j=0; j < N; ++j) {
    nodes.push_back(TreeNode(0));
  }
  vector<bool> opened(N);
  for (ll j=0; j < N-1; ++j) {
    ll u, v, w; cin >> u >> v >> w;
    nodes[u-1].conn.push_back(make_tuple(w, v-1));
    nodes[v-1].conn.push_back(make_tuple(w, u-1));
  }
  queue<tuple<TreeNode*, ll>> q;
  q.push(make_tuple(&nodes[0], 0)); opened[0] = true;
  while (!q.empty()) {
    TreeNode* node; ll d;
    tie(node, d) = q.front(); q.pop();
    for (tuple<ll, ll> iter : node->conn) {
      ll dist, next; tie(dist, next) = iter;
      if (!opened[next]) {
        opened[next] = true;
        ll dd = d + dist;
        nodes[next].val = dd % 2 == 0 ? 0 : 1;
        q.push(make_tuple(&nodes[next], dd));
      }
    }
  }
  for (ll j=0; j < N; ++j) {
    cout << nodes[j].val << endl;
  }
  return 0;
}


Measured memory_bytes: 8940
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {

	public static void main(String[] args) {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		try {
			String scond = br.readLine();
			int intscond = Integer.parseInt(scond);

			int h = intscond/3600;
			int m = (intscond%3600)/60;
			int s = intscond%60;
			System.out.println(h+":"+m+":"+s);
		} catch (IOException e) {
			// TODO ????????????????????? catch ????????????
			e.printStackTrace();
		}



	}

}

Measured memory_bytes: 24392
import java.io.*;

import java.util.*;
import java.math.*;
import java.text.*;



class Main{
	private static double my_pow(double a){
		return a*a;	
	}

	private static ArrayList<Double> calc_circ(ArrayList<Double> p){

		ArrayList<Double> res = new ArrayList<Double>();

		double x1,x2,x3,y1,y2,y3,a,b,c,r,xc,yc,a1,b1,c1,a2,b2,c2,a3,b3,c3;
		

		for(int i = 0;i<p.size()/6;i++){

			x1=p.get(i*6);
			y1=p.get(i*6+1);

			x2=p.get(i*6+2);
			y2=p.get(i*6+3);
			x3=p.get(i*6+4);

			y3=p.get(i*6+5);
			a = Math.sqrt(my_pow(x1-x2)+my_pow(y1-y2));
			b = Math.sqrt(my_pow(x2-x3)+my_pow(y2-y3));
			c = Math.sqrt(my_pow(x1-x3)+my_pow(y1-y3));
			r = (a*b*c)/(Math.sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c)));
			a1 = 2*(x2-x1);
			b1 = 2*(y2-y1);
			c1 = my_pow(x1)-my_pow(x2)+my_pow(y1)-my_pow(y2);
			a2 = 2*(x3-x1);
			b2 = 2*(y3-y1);
			c2 = my_pow(x1)-my_pow(x3)+my_pow(y1)-my_pow(y3);
			xc = (b1*c2-b2*c1)/(a1*b2-a2*b1);
			yc = (c1*a2-c2*a1)/(a1*b2-a2*b1);
			res.add(xc);
			res.add(yc);
			res.add(r);

		}

		return res;

	}

	private static void print_circ(ArrayList<Double> a){
		String format = "0.000";

		DecimalFormat decimalFormat = new DecimalFormat( format );

		String str1,str2,str3;
		double x,y,r;		

		for(int i = 0;i<a.size()/3;i++){
			x = a.get(i*3);

			y = a.get(i*3+1);
			r = a.get(i*3+2);

			str1 = Double.toString(x);

			str2 = Double.toString(y);
			str3 = Double.toString(r);			
			
			BigDecimal bigDecimal1 = new BigDecimal( str1 );

			BigDecimal bigDecimal2 = new BigDecimal( str2 );			
			BigDecimal bigDecimal3 = new BigDecimal( str3 );

			BigDecimal Result1 = bigDecimal1.setScale(4,BigDecimal.ROUND_HALF_UP);

			BigDecimal Result2 = bigDecimal2.setScale(4,BigDecimal.ROUND_HALF_UP);
			BigDecimal Result3 = bigDecimal3.setScale(4,BigDecimal.ROUND_HALF_UP);


			System.out.println( decimalFormat.format( Result1 ) + " " + decimalFormat.format( Result2 ) + " " + decimalFormat.format( Result3 ) );

		}

	}

		public static void main(String args[]) throws IOException{

			ArrayList<Double> tri = new ArrayList<Double>();

			Scanner scan = new Scanner(System.in);

			

			int a;

			

			a = Integer.parseInt(scan.next());

			

			for(int i = a;i > 0;i--){

				for(int j = 0;j<6;j++){

					String str1 = scan.next();

					tri.add(Double.parseDouble(str1));

				}

			}

			ArrayList<Double> res = new ArrayList<Double>();

			res = calc_circ(tri);

			print_circ(res);

	}

}

Measured memory_bytes: 12000
#include<iostream>
#include<cmath>
#include<cstdio>
#include<math.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    double x[n+1], y[n+1],det[n+1];
    double D1 = 0,D2 = 0,D3 = 0,D0 = 0;
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    for(int i = 0; i < n; i++){
        cin >> y[i];
        det[i] = fabs(x[i]-y[i]);
        D1 += det[i];
        D2 += pow(det[i], 2);
        D3 += pow(det[i], 3);
        if(i == 0) D0 = det[i];
        else if (det[i] > D0) D0 = det[i];
    }
    printf("%lf %lf %lf %lf\n", D1, sqrt(D2), cbrt(D3), D0);
    return 0;
}


Measured memory_bytes: 3372
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
using namespace std;

int rem = 998244353;

int main()
{
  int n;
  cin >> n;
  int d[n];
  int a;
  int counter = 1;
  long pattern = 0;
  for(int i = 0 ;i<n;++i){
    d[i] = 0;
    
  }
  cin >> d[0];
  for(int i = 1 ;i<n;++i){
    cin >> a;
    d[a]++;
  }
  if(d[0]==0){
    pattern = 1;
    for(int i = 1 ;i<n;++i){
      if(counter < n){
        if(d[i]>0){
          for(int j = 0; j < d[i]; ++j){
            if(i > 1){
              pattern *= d[i-1];
            }
            pattern %= rem;
          }
          counter += d[i];
        }else if(d[i] == 0){
          pattern = 0;
          break;
        }
      }else{
        break;
      }
    }
  }
 
  printf("%d\n", pattern);

}

Measured memory_bytes: 640
#include<iostream>
using namespace std;
int ans(int n,int d){
    if(n<=2*d+1)
        return 1;
    return 1+ans(n-(2*d+1),d);
}
int main(){
  int n,d;
  cin>>n>>d;
  cout<<ans(n,d);
  return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main {
 
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] h = new int[n];
        for(int i = 0; i<n; i++){
        h[i] = scan.nextInt();
        }
        int solve = dp(n, h);
    System.out.println(solve);
    }
    public static int dp(int n, int[] h){
    int[] arr = new int[n];
    arr[1] = Math.abs(h[0] - h[1]);
    for(int i = 2; i<arr.length; i++){
    arr[i] = Math.min(Math.abs(h[i-1]-h[i])+arr[i-1], Math.abs(h[i-2]-h[i])+arr[i-2]);
    }
    return arr[n-1];
    }
    
}

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

using namespace std;

#define INT_MAX (2*1e9)

int n, m;
int a[15][15];
int c[15];
int ans = INT_MAX;
int x;

void cal(int choose[], int order);
int main()
{
    scanf("%d%d%d", &n, &m, &x);
    for(int i=0; i<n; i++){
        scanf("%d", &c[i]);
        for(int j=0; j<m; j++)
            scanf("%d", &a[i][j]);
    }
    int choose[15] = {};
    cal(choose, 0);
    if(ans == INT_MAX)
        printf("-1\n");
    else
        printf("%d\n", ans);
}

void cal(int choose[], int order)
{
    if(order == n){
        int cap[15] = {};
        for(int i=0; i<n; i++){
            if(choose[i]){
                for(int j=0; j<m; j++)
                    cap[j] += a[i][j];
            }
        }
        for(int i=0; i<m; i++){
            if(cap[i] < x)
                return;
        }
        int cost = 0;
        for(int i=0; i<n; i++)
            cost += c[i]*choose[i];
        ans = min(ans, cost);
        return;
    }
    for(int i=0; i<2; i++){
        choose[order] = i;
        cal(choose, order+1);
    }
}


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

int main(){
    long long int h, w;
    cin >> h >> w;
    long long int ans = 0;
    if(h == 1 || w == 1) ans = 1;
    else{
        ans = h * w;
        if(ans % 2 == 0) ans /= 2;
        else{
            ans /= 2;
            ans += 1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MIN -1000000
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
const int max_N=1e5+10;
int N;
int indeg[10005];
bool visited[10005];
vector<pair<int,int> > opes;
vector<int> costs;
int setcost[10005];
vector<int> G[10005];
ll ans=0;
int cindex=0;
void dfs(int s)
{
  visited[s]=true;
  setcost[s]=costs[cindex];
  cindex++;
  for (int i = 0; i < int(G[s].size()); ++i)
    {
      int nx=G[s][i];
      if(!visited[nx])
	{
	  ans+=min(setcost[nx],setcost[s]);
	  dfs(nx);
	}
    }
}
int main(void)
{
  memset(setcost,0,sizeof(setcost));
  memset(indeg,0,sizeof(indeg));
  memset(visited,false,sizeof(visited));
  cin >> N;
  for (int i = 0; i < N-1; ++i)
    {
      int a,b;
      cin >> a >> b;
      G[a].push_back(b);
      G[b].push_back(a);
      indeg[a]++;
      indeg[b]++;
    }
  for (int i = 0; i < N; ++i)
    {
      int c;
      cin >> c;
      costs.push_back(c);
    }
  int mnindeg=1e7;
  int startindex=-1;
  for (int i = 1; i <= N; ++i)
    {
      if(indeg[i]<mnindeg)
	{
	  startindex=i;
	  mnindeg=indeg[i];
	}
    }
  sort(costs.begin(),costs.end(),greater<int>());
  for (int i = 0; i < N; ++i)
    {
      if(i!=0) ans+=costs[i];
    }
  dfs(startindex);
  cout << ans << endl;
  for (int i = 1; i <= N; ++i)
    {
      if(i!=N)
	{
	  cout << setcost[i] << ' ';
	}
      else
	{
	  cout << setcost[i] << endl;
	}

    }
  return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <bits/stdc++.h>
#define inf 1000000007
using namespace std;

void func(int n){
    vector<long> dp(n+1,0);
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 3; j <= i; j++){
            dp[i] += dp[i-j];
            dp[i] %= inf;
        }
        //cout << dp[i];
    }
    cout << dp[n] << endl;
}

int main() {
	int n;
	cin >> n;
	func(n);
	return 0;
}


Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int n, k, q, freq[N];
int main() {
#ifndef ONLINE_JUDGE
//	freopen("input.in", "r", stdin);
#endif
	scanf("%d %d %d", &n, &k, &q);
	for (int i = 0; i< q; ++i) {
		int a;
		scanf("%d", &a);
		++freq[a];
	}
	for (int i = 1; i <=n; ++i) {
		if (k - (q - freq[i]) > 0) {
			puts("Yes");
		}else {
			puts("No");
		}
	}
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
#include <list>
#include <cstring>
using namespace std;
#define pi pair<int,int>
#define pl pair<long long,long long>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
typedef long long ll;
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}
struct edge {
    ll to,cost;
};

/*
const int COM_MAX = 500500;
long long fac[COM_MAX],finv[COM_MAX],inv[COM_MAX];
void init(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < COM_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 || n < 0 || k < 0) return 0;
    return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
*/

long long function(ll a){
    if (a % 4 == 0) return a;
    if (a % 4 == 1) return 1;
    if (a % 4 == 2) return a^1;
    else return 0;
}

int main(){
    ll a,b; cin >> a >> b;
    cout << (function(b)^function(a-1)) << endl;
}

Measured memory_bytes: 256
def main():
    n, *abcd = map(int, open(0).read().split())
    red = list(zip(abcd[0:2 * n + 1:2], abcd[1:2 * n + 1:2]))
    blue = list(zip(abcd[2 * n::2], abcd[2 * n + 1::2]))

    r = sorted(red, key=lambda p: p[1], reverse=True)
    b = sorted(blue)
    r = tuple(r)
    b = tuple(b)
    ans = 0
    done = []
    for xb, yb in b:
        for xr, yr in r:
            if xr < xb and yr < yb:
                if [xr, yr] not in done:
                    done.append([xr, yr])
                    ans += 1
                    break
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

// GCD : greatest common divisor (GCD) via Euclidean algorithm
func GCD(a, b int) int {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}

// LCM : find Least Common Multiple (LCM) via GCD
func LCM(a, b int, integers ...int) int {
	result := a / GCD(a, b) * b

	for i := 0; i < len(integers); i++ {
		result = LCM(result, integers[i])
	}

	return result
}
func main() {
	sc.Split(bufio.ScanWords)
	A, B, C, D := getInt(), getInt(), getInt(), getInt()

	n := B - A + 1

	E := LCM(C, D)

	c := B/C - (A-1)/C
	d := B/D - (A-1)/D
	e := B/E - (A-1)/E

	out(n - c - d + e)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define loop(i,a,b) for (int i=a; i<b; ++i)
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll N;
    cin >> N;
    ld ans=0;
    vector < ld > p(N);
    loop(i,0,N) cin >> p[i];
    vector <ld> heads(N+1,0); // heads[i] - Probability of i heads so far
    heads[0]=1;
    loop(i,0, N)
    {
        for (int j=N; j>=0; --j)
        {
            // Multiplication and addition rules of probability
            if (j>0) heads[j] = (heads[j-1]*p[i]) + (heads[j]*(1-p[i]));
            else heads[0]*=(1-p[i]);
        }
    }
    // loop(i,0,N+1) cout << heads[i] << " ";
    // cout << "\n";
    loop(i,N/2+1, N+1) ans+= heads[i];
    cout << fixed << setprecision(10) << ans << "\n";
    return 0;
}

Measured memory_bytes: 384
n = int(input())
possible = [1]
i=1
while i <= 100000:
  i = i*6
  possible+=[i]
i=1
while i <= 100000:
  i = i*9
  possible+=[i]
possible.sort(reverse =1)
ans = 0
table = set([n])
while True:
  if 0 in table:
    print(ans)
    break
  ans+=1
  nexttable = set()
  for num in table:
    for p in possible:
      if num - p >= 0:
        nexttable.add(num-p)
  table =nexttable

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

int main() {
	int n;
	double sigma=0.000000;
	cin >> n;
	vector<double> v(n);
	vector<string> u(n);
	for(int i=0;i<n;i++){
		cin >> v.at(i) >> u.at(i);
		if(u.at(i)=="JPY"){
			sigma+=v.at(i);
		}else{
			sigma+=v.at(i)*380000.0;
		}
	}
	cout << sigma << endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
    int a,b,c,x,y,z;
    scanf("%d %d %d",&a,&b,&c);
    if(a>b){
        x=a;
        a=b;
        b=x;
    }
    if(b>c){
        y=b;
        b=c;
        c=y;
    }
    if(a>b){
        z=a;
        a=b;
        b=z;
    }
    printf("%d %d %d\n",a,b,c);
    return 0;
}
    


Measured memory_bytes: 2044
def ser(visited,now):
  visited.append(now)
  if len(visited)==n:
    return 1
  cnt=0
  for i in bri[now]:
    if i not in visited:
      cnt+= ser(visited[:],i)
  return cnt

n,m=map(int,input().split())
bri=[[] for _ in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  bri[a-1].append(b-1)
  bri[b-1].append(a-1)
print(ser([],0))

Measured memory_bytes: 73528
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 

 
void solve()
{
	int n  ; 
	cin>>n ; 
	int b[n-1]   , a[n] ; 
	rep(i , n-1) cin>>b[i] ; 
	a[0] = b[0] ; 
	a[n-1] = b[n-2] ;
	repu(i , 1 , n-2){
		a[i]  = min(b[i-1], b[i]) ;
	}
	int ans =0 ;
	rep(i , n){
		ans +=a[i] ;
	}
	cout<<ans<<endl;
}
 
int main() {
    // #ifndef ONLINE_JUDGE
    //     // for getting input from input.txt
    //     freopen("input.txt", "r", stdin);
    //     // for writing output to output.txt
    //     freopen("output.txt", "w", stdout);
    // #endif
    
    // ios_base::sync_with_stdio(0);
    // cin.tie(NULL);
    int t = 1;
    // cin>>t;
    while(t--)
    {
        solve();
    } 
    // cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 256
use proconio::input;

fn solve(n: usize, a: &[i32]) -> Vec<i32> {
    let mut s = 0;
    for &x in a {
        s ^= x;
    }
    a.iter().map(|x| x ^ s).collect()
}

fn main() {
    input! {
        n: usize,
        a: [i32; n],
    }
    let r = solve(n, &a);
    for x in r {
        println!("{}", x);
    }
}


Measured memory_bytes: 6388
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N;
    cin >> N;
    VEC(int) A(N);
    READVEC(A);
    double s = 0;
    FOR(i, 0, N)
        s += A[i];

    int ret = 100 * 1000 * 1000, avg = (int) (s / N);
    FOR(sum, avg - 10, avg + 11) {
        int cost = 0;
        for(int a : A)
            cost += (a - sum) * (a - sum);
        ret = min(ret, cost);
    }
    cout << ret << endl;
    return 0;
};


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  
  if(a-b>c){
    cout << 0;
  } else {
    cout << c-(a-b);
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <iomanip>
using ll=long long;
using namespace std;

int main(){
    int N,K;
    cin>>N>>K;
    vector<int> P(N+2);
    for(int i=0;i<N;i++){
        cin>>P[i];
    }

    int tmp=0;
    for(int i=0;i<K;i++){
        tmp+=P[i];
    }
    int maxnum=tmp;
    for(int i=0;i+K<N;i++){
        tmp-=P[i];
        tmp+=P[i+K];
        if(tmp>maxnum){
            maxnum=tmp;
        }
    }
    double ans=(maxnum+K)/(double)2;
    cout<<fixed<<setprecision(7)<<ans<<endl;

    return 0;
}

Measured memory_bytes: 4004
mod = 998244353


class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod

    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod


N, M, K = map(int, input().split())
C = Combination(N)

ans = 0
for k in range(K + 1):
    now = C.calc(N - 1, k) * M * pow(M - 1, N - k - 1, mod) % mod
    ans = (ans + now) % mod

print(ans)

Measured memory_bytes: 24668
N, M = map( int, input().split() )
AdjMatric = [ [False]*N for _ in range(N) ]
for _ in range(M):
    a, b = map( int, input().split() )
    a -= 1
    b -= 1
    AdjMatric[a][b] = True
    AdjMatric[b][a] = True


ans = 0
for i in range(N):
    for j in range(i+1,N):
        if AdjMatric[i][j] == False: continue
        # 橋 i <-> j を取り除いたときに i -> j へ行けるかを全探索
        AdjMatric[i][j] = False
        isVisited = [False]*N
        s = [i]
        while s:
            tmp = s.pop()
            if isVisited[tmp]: continue
            isVisited[tmp] = True
            for k in range(N):
                if AdjMatric[tmp][k] == True: s.append(k)
        if isVisited[j] == False: ans += 1
        AdjMatric[i][j] = True

print( ans )


Measured memory_bytes: 3064
N,K= map(int,input().split())
list1 = []

for i in range(1,N+1):
    list1.append(i)

for j in range(K):
    d =int(input())
    lista = list(map(int,input().split()))
    for l in lista:
        for h in list1:
            if (l==h):
                list1.remove(h)

print(len(list1))

Measured memory_bytes: 9192
N = int(input())
*A, = map(int, input().split())
*B, = map(int, input().split())

bef = sum(A)
for i, n in enumerate(B):
    if n>A[i]:
        n-=A[i]
        A[i]=0
        
        if n>A[i+1]:
            n-=A[i+1]
            A[i+1]=0
        else:
            A[i+1]-=n
            n=0
    else:
        A[i]-=n
        n=0

print(bef-sum(A))

Measured memory_bytes: 19116
#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const long long mod=1e9+7;
const int N=2e5+7;

string str,res="";
int g[15];
int top=-1;
int main()
{
   cin>>str;
   for(int i=0;i<str.size();i++)
   {
   	 top++;
   	 if(str[i]=='0')
   	 g[top]=0;
   	 else if(str[i]=='1')
   	 g[top]=1;
   	 else
   	 {
   	    top--;
		if(top>-1)
			top--;
	 }
	 //cout<<g[0]<<endl;
	 //cout<<top<<g[top]<<endl;
   }
   for(int i=0;i<=top;i++)
    res+= (g[i]+'0');
   cout<<res<<endl;
}

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


using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}

const long long MOD = 998244353;

ll pw(ll x, ll y) {
  ll ans=1;
  for(int i=0; i<y; i++) {
    ans = (ans*x)%MOD;
  }
  return ans;
}

void solve(long long N, std::vector<long long> D){

  if(D[0]!=0){
    std::cout << 0 << std::endl;
    return;
  }
  for(ll i=1; i<N; i++) {
    if(D[i]==0) {
      std::cout << 0 << std::endl;
      return;
    }
  }
  sort(D.begin(), D.end());
  vector<ll> v;
  ll p = 0;
  ll c = 1;
  for(int i=1; i<N; i++) {
    if(D[i]==p) {
      c++;
    } else if(D[i]-1==p){
      v.push_back(c);
      c = 1;
    } else {
      std::cout << 0 << std::endl;
      return;
    }
    p = D[i];
  }
  v.push_back(c);

  ll ans=1;
  for(int i=1; i+1<v.size(); i++) {
    ans = (ans*pw(v[i], v[i+1]))%MOD;
  }
  std::cout << ans << std::endl;

}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> D(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&D[i]);
    }
    solve(N, std::move(D));
    return 0;
}


Measured memory_bytes: 2168
#include <stdio.h>

int main(void)
{
	int n, b, f, r, v, i, j, k, l;
	int h[4][3][10] = { 0 };

	scanf("%d", &n);

	for (i = 0;i<n;i++) {
		scanf("%d %d %d %d", &b, &f, &r, &v);
		h[b - 1][f - 1][r - 1] += v;
	}

	for (i = 0;i<4;i++) {
		for (j = 0;j<3;j++) {
			for (k = 0;k<10;k++) {
				printf(" %d", h[i][j][k]);
			}
			printf("\n");
		}
		if (i == 3) break;
		for (l = 0;l<20;l++) {
			printf("#");
		}
		printf("\n");
	}

	return 0;
}


Measured memory_bytes: 2032
import math
L=raw_input().split()
L1=[int(i) for i in L]
LA=raw_input().split()
L2=[int(i) for i in LA]
e=o=ans=0
for i in L2: 
	if i%2: o+=1
	else: e+=1
if L1[1]==0:
	for i in range(0,o+1,2):
		ans+=(math.factorial(o)/(math.factorial(i)*math.factorial(o-i)))
	print ans*(1<<e)
else:
	for i in range(1,o+1,2):
		ans+=(math.factorial(o)/(math.factorial(i)*math.factorial(o-i)))
	print ans*(1<<e)


Measured memory_bytes: 2692
def main(h, w, a):
    print('#' * (w + 2))

    for s in a:
        print('#{}#'.format(s))

    print('#' * (w + 2))


if __name__ == '__main__':
    h, w = map(int, input().split(' '))
    a = []

    for _ in range(h):
        a.append(input())

    main(h, w, a)


Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

namespace LogicSummoner
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = GetNumber();
            var a = GetNumbersDouble(n);
            var b = GetNumbersDouble(n);

            System.Console.WriteLine(Length(1, a, b).ToString("F6"));
            System.Console.WriteLine(Length(2, a, b).ToString("F6"));
            System.Console.WriteLine(Length(3, a, b).ToString("F6"));
            System.Console.WriteLine(Length(0, a, b).ToString("F6"));
        }

        static double Length(int p, double[] a, double[] b)
        {
            if (p == 0)
            {
                var max = double.MinValue;
                for (int i = 0; i < a.Length; i++)
                {
                    max = Math.Max(max, Math.Abs(a[i] - b[i]));
                }
                return max;
            }
            else
            {
                var sum = 0.0;
                for (int i = 0; i < a.Length; i++)
                {
                    sum += Math.Pow(Math.Abs(a[i] - b[i]), p);
                }
                return Math.Pow(sum, 1.0 / p);
            }
        }

        //static StreamReader Console = new StreamReader("input.txt");

        static int GetNumber()
        {
            return int.Parse(Console.ReadLine().Trim());
        }

        static double GetDounble()
        {
            return double.Parse(Console.ReadLine().Trim());
        }

        static int[] GetNumbersInt(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => int.Parse(x)).ToArray();
        }

        static long[] GetNumbersLong(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => long.Parse(x)).ToArray();
        }

        static double[] GetNumbersDouble(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).Select(x => double.Parse(x)).ToArray();
        }

        static string[] GetStrings(int n = 0)
        {
            return Console.ReadLine().Trim().Split(new[] { " " }, StringSplitOptions.RemoveEmptyEntries).ToArray();
        }
    }
}

Measured memory_bytes: 10384
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int n;
string s;

const LL MOD = 1e9+7;

LL memo[4005][4005][5];

LL dp(int l, int r, int indi){ // 0 = menaik, 1 menurun
	if(l<0 || r<0) return 0;
	if((l+r) == 0) return 1;
	LL &ret =  memo[l][r][indi];
	if(ret!=-1) return ret;
	int tot = l+r;
	if(indi == 0) ret = dp(l+1,r-1,indi);
	else ret = dp(l-1,r+1,indi);
	int id = n-tot;
//	s[id] = '>';
	if(s[id] == '>') ret+=dp(l - 1,r,1);
	else ret+=dp(l,r - 1,0);
	ret%=MOD; 
//	cout<<l<<" "<<r<<" "<<indi<<endl;
	return ret;
}

int main(){
	cin >> n;
	cin >> s;
	n--;
	memset(memo,-1,sizeof(memo));
	for(int i=0;i<=1;i++){
		for(int j=1;j<=n;j++){
			for(int k=0;k<=j;k++) dp(k,j-k,i);
		}
	}
	LL ans = dp(n,0,1);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 627200
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<string>
#include<time.h>
#include<utility>
#include<vector>
using namespace std;
const long mod = 1000000007;
//include<kyawa>
//--------------------

int main() {

	string res = "Yes";
	long N, n; cin >> N; n = N;
	vector<pair<long, long>> task;
	while (n--) { int i, j; cin >> i >> j; task.push_back(make_pair(i, j)); }

	sort(task.begin(), task.end() , [&](auto a, auto b) {return a.second < b.second; });//auto = pair<long , long>

	long now = 0;

	for (int i = 0; i < N; i++) { now += task[i].first; if (now > task[i].second) res = "No"; }

	cout << res << endl;
}

Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
int main() {
  string c;
  cin >> c;
  if (c=="a" || c=="i" || c=="u" || c=="e" || c=="o") {
      cout << "vowel" << endl;
  } else {
    cout << "consonant" << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include <cstdlib>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include <iomanip>
#include<stack>
#include <unordered_map>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
// #define pi acos(-1)
// #include<bits/stdc++.h>
typedef long long ll;
#define INF 0x7f7f7f7f //2139062143
#define INF1 0x3f3f3f3f //1061109567
#define INF2 2147483647
#define llINF 9223372036854775807
#define pi 3.14159265358979323846264338327950254
#define pb push_back
#define ll long long
#define debug cout << "debug\n";
#define STDIN freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
#define Quick ios::sync_with_stdio(false);cin.tie(NULL);
#define scai(x) scanf("%d", &x)
#define sca2i(x, y) scanf("%d %d", &x, &y)
#define scaf(x) scanf("%lf", &x)
#define sca2f(x, y) scanf("%lf %lf", &x, &y)
#define For(m,n) for (int i = m;  i < n; i++)
#define PII pair<int,int>
#define PLL pair<long, long>
#define lowbit(x) (x&-x)

const int maxn = 50;
#define ERR 1e-6
#define fabs(a) (a < 0 ? -(a) : a)
#define square(a) ((a) * (a))
const int N = 2e3 +10;
int n;
int ans[N];
int d[N][N];

int x, y, a, b, c;
vector<int> red;
vector<int> green;
vector<int> white;

int main()
{
    //STDIN
    cin >> x >> y >> a >> b >> c;
    for (int i = 1; i <= a; i++)
    {
        int t;
        scanf("%d", &t);
        red.push_back(t);
    }
    for (int i = 1; i <= b; i++)
    {
        int t;
        scanf("%d", &t);
        green.push_back(t);
    }
    for (int i = 1; i <= c; i++)
    {
        int t;
        scanf("%d", &t);
        white.push_back(t);
    }
    sort(red.begin(), red.end());
    sort(green.begin(), green.end());
    //sort(green.begin(), green.end());
    for (int i = 1; i <= x; i++)
    {
        int t = red.back();red.pop_back();
        white.push_back(t);
    }
    for (int i = 1; i <= y; i++)
    {
        int t = green.back();green.pop_back();
        white.push_back(t);
    }
    sort(white.begin(), white.end());
    long long ans = 0ll;
    for (int i = 1; i <= x+y; i++)
    {
        ans += (long long)white.back();white.pop_back();
    }
    cout << ans << endl;
}

Measured memory_bytes: 3188
#![allow(dead_code)]
#![allow(unused_must_use)]

fn solve(src: &str) -> String {
    use std::fmt::Write;
    let mut buf = String::new();
    let mut sc = Scanner::from_str(&src);

    let n: u32 = sc.read();
    writeln!(&mut buf, "{}", ((n+1)/2) as f64 / n as f64);

    buf
}

fn main() {
    let mut buf = String::new();
    use std::io::Read;
    std::io::stdin().read_to_string(&mut buf);
    use std::io::Write;
    std::io::stdout().write_all(solve(&buf).as_bytes());
}

#[test]
fn test() {
    assert_eq!(solve(r"4"),r"0.5000000000");
assert_eq!(solve(r"5"),r"0.6000000000");
assert_eq!(solve(r"1"),r"1.0000000000");
}

struct Scanner<I>{
    src: I
}

impl<'a> Scanner<std::str::SplitWhitespace<'a>> {
    fn from_str(src: &'a str) -> Self {
        Scanner { src: src.split_whitespace() }
    }
}

impl<'a, I> Scanner<I> where I: std::iter::Iterator<Item = &'a str>{
    fn read<T: std::str::FromStr>(&mut self) -> T {
        self.src.next().unwrap().parse().ok().expect("Parse error")
    }
    fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    fn chars(&mut self) -> Vec<char> {
        self.src.next().unwrap().chars().collect()
    }
}

Measured memory_bytes: 4352
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <string>
#include <numeric>
#include <algorithm>
#include <functional>
#include <iterator>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <complex>
#include <ctime>
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int main(){
	int n,a;
	vector<int> v;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        a*=-1;
        int it=upper_bound(v.begin(),v.end(),a)-v.begin();
        if(it==v.size())
        {
            v.push_back(a);
        }
        else
            v[it]=a;
    }
    printf("%d\n",v.size());
	return 0;
}


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

int main(){
  int n, m;
  cin >> n >> m;
  int a[m], b[m];
  dsu d(n);
  for(int i=0; i<m; i++){
    cin >> a[i] >> b[i];
    d.merge(a[i]-1, b[i]-1);
  }
  cout << d.groups().size()-1;
  return 0;
}


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

int main(void) {
	int N, K;
	scanf("%d %d", &N, &K);
	int x[100];
	int ans = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &x[i]);
		ans += min(x[i], abs(x[i] - K)) * 2;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3840
object Main extends App {
	val pw = new java.io.PrintWriter(System.out)

	val n = Scanner.nextInt

	def g(x: Long): Long = {
		val y = n / x
		y * (y + 1) * x / 2
	}

	pw.println((1 to n).foldLeft(0L){case (acc, j) => acc + g(j)})
	pw.flush()
}

object Scanner {
	private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0

	@inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
	@inline private def hasNextByte(): Boolean = if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else true
	@inline private def hasNext(): Boolean = {
		while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
		hasNextByte()
	}
	@inline private def readByte(): Byte = if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else -1

	def next(): String = {
		if(!hasNext()) ???
		val sb = new StringBuilder; var b = readByte()
		while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
		sb.toString
	}

	def nextInt(): Int = {
		val n = nextLong()
		if (n < Int.MinValue || Int.MaxValue < n) ???
		n.toInt
	}

	def nextLong(): Long = {
		if(!hasNext()) ???
		var minus = false; var b = readByte()
		if (b == '-') { minus = true; b = readByte() }

		@scala.annotation.tailrec
		def go (b: Byte, n: Long = 0): Long = if ('0' <= b && b <= '9') go(readByte(), n * 10 + b - '0') else if (minus) -n else n

		go(b)
	}

	def nextDouble(): Double = next().toDouble
}


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

int main() {
	int ans = 0;
	string W;
	cin >> W;

	string Q;
	cin >> Q;
	while (Q != "END_OF_TEXT") {

		transform(Q.begin(), Q.end(), Q.begin(), ::tolower);

		if (Q == W) ans++;

		cin >> Q;
	}

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



Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
int n,k,q;
int a[200010];
int main(){
	int x;
	cin>>n>>k>>q;
	k-=q;
	for(int i=1;i<=q;i++){
		scanf("%d",&x);
		a[x]++;
	}
	for(int i=1;i<=n;i++){
		if(a[i]+k>0) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

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

#define int long long int
#define ff first
#define ss second
#define pb push_back

int bexp(int a, int b)
{
    int res = 1;

    while (b)
    {
        if (b & 1) res = (res * a);

        a = (a * a); 
        b >>= 1;
    }
    return res;
}

#define N 200010
#define MOD 1000000007

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


int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(10);

    int n;
    cin >> n;

    int a[4] = {};
    string s;
    
    for (int i = 0; i < n; ++i)
    {
        cin >> s;
        if (s == "AC")
        {
            a[0]++;
        }
        else if (s == "WA")
        {
            a[1]++;
        }
        else if (s == "TLE")
        {
            a[2]++;
        }
        else
        {
            a[3]++;
        }
    }
    cout << "AC x " << a[0] << "\n"
        << "WA x " << a[1] << "\n"
        << "TLE x " << a[2] << "\n"
        << "RE x " << a[3] << endl;
    return 0;
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;
const ll LINF = 1e18 + 5;
int n, dp[N], h[N];
int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	cin >> n;
 	for(int i=1; i<=n; i++) cin >> h[i];
 	dp[1] = 0;
 	dp[2] = abs(h[2]-h[1]);
 	for(int i=3; i<=n; i++)
 		dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]));
 	cout << dp[n];
	return 0;
}


Measured memory_bytes: 1024
n=int(input())
a=list(map(int,input().split()))
a.sort()
x=y=0
while True:
  if len(a)>0:
    x+=a.pop()
  else:
    break
  if len(a)>0:
    y+=a.pop()
  else:
    break
print(x-y)

Measured memory_bytes: 3060