akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;

const i64 MOD = 1e9+7;

const i64 INF = 1e18+7;

signed main(){
    int n;
    cin >> n;
    vector<i64> a(n);
    for(auto& x : a)
        cin >> x;
    sort(a.begin(), a.end());
    i64 ans = 0;

    if(n % 2 == 0){
        for(int i = 0; i < n / 2 - 1; ++i)
            ans += -2 * a[i] + 2 * a[n - i - 1];
        ans += -a[n / 2 - 1] + a[n / 2];
    }else{
        for(int i = 0; i < n / 2; ++i)
            ans += -2 * a[i] + 2 * a[n - i - 1];
        ans += max(a[n / 2] - a[n / 2 + 1], a[n / 2 - 1] - a[n / 2]);
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
import std.stdio, std.conv, std.string, std.array, std.range, std.algorithm, std.container;
import std.math, std.random, std.bigint, std.datetime, std.format;
void main(string[] args){ if(args.length > 1) if(args[1] == "-debug") DEBUG = 1; solve(); }
void log()(){ writeln(""); } void log(T, A ...)(T t, lazy A a){ if(DEBUG) write(t, " "), log(a); } bool DEBUG = 0; 
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }
// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- //

void solve(){
	int n = read.to!int;
	int[] ps;
	foreach(i; 0 .. n) ps ~= read.to!int;
	
	int cnt;
	foreach(i, p; ps) if(i + 1 != p) cnt += 1;
	
	if(cnt <= 2) "YES".writeln;
	else "NO".writeln;
	
}


Measured memory_bytes: 256
n=int(input())
xllist=[list(map(int,input().split())) for _ in range(n)]
s_e=[]
for xl in xllist:
    s_e.append([xl[0]-xl[1],xl[0]+xl[1]])
s_e.sort(key=lambda x: x[1])
now=s_e.pop(0)[1]
ans=1
for xl in s_e:
    if now<=xl[0]:
        ans+=1
        now=xl[1]
print(ans)

Measured memory_bytes: 42596
import sys
import math
import heapq
from collections import deque
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,u,v=LI()

TR=[[] for i in range(N+1)]
for _ in range(N-1):
    i,j=LI()
    TR[i].append(j)
    TR[j].append(i)

DIST1=[-1]*(N+1)
DIST2=[-1]*(N+1)
FIFO = deque()

FIFO.append((v,0))
while FIFO:
    edge, dist = FIFO.popleft()
    DIST1[edge] = dist
    for i in TR[edge]:
        if DIST1[i] == -1:
            FIFO.append((i, dist+1))

FIFO.append((u, 0))

farest = 0
while FIFO:
    edge, dist = FIFO.popleft()
    DIST2[edge] = dist
    farest = max(farest, DIST1[edge])
    for i in TR[edge]:
        if DIST2[i] == -1 and dist+1 < DIST1[i]:
            FIFO.append((i, dist+1))

# print(DIST1)
# print(DIST2)
print(max(0, farest-1))


Measured memory_bytes: 66592
#include<stdio.h>
#include<string.h>
char m[22][22],*p;
int F(int x,int y)
{
	if(m[y][x]=='#')return 0;
	m[y][x]='#';
	return 1+F(x+1,y)+F(x-1,y)+F(x,y+1)+F(x,y-1);
}
int main()
{
	int w,h,i,x,y;
	while(scanf("%d%d",&w,&h),w)
	{
		for(i=1;i<=h;++i)
		{
			scanf("%s",m[i]+1);
			if(p=strchr(m[i]+1,'@'))x=p-m[y=i];
		}
		for(i=0;i<h+2;++i)m[i][0]=m[i][w+1]='#';
		for(i=0;i<w+2;++i)m[0][i]=m[h+1][i]='#';
		printf("%d\n",F(x,y));
	}
	return 0;
}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  cout << "{";
  for (int i = 0; i < vec.size(); i++)
    os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  cout << "}";
  return os;
}

// ====================================================================

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<vector<bool>> ldeta(n + 1, vector<bool>(10));  // それまでに何が出たか
  vector<vector<bool>> rdeta(n + 1, vector<bool>(10));

  for (int i = 1; i <= n; i++) {
    ldeta[i] = ldeta[i - 1];
    ldeta[i][s[i - 1] - '0'] = 1;
  }

  for (int i = n - 1; i >= 0; i--) {
    rdeta[i] = rdeta[i + 1];
    rdeta[i][s[i] - '0'] = 1;
  }

  // for (int i = 0; i <= n; i++) {
  //   cout << ldeta[i] << endl;
  // }
  // cout << endl;
  // for (int i = 0; i <= n; i++) {
  //   cout << rdeta[i] << endl;
  // }

  map<string, bool> ans;
  for (int i = 0; i < n; i++) {
    string res = "";
    res += s[i];
    for (int l = 0; l < 10; l++) {
      for (int r = 0; r < 10; r++) {
        if (ldeta[i][l] && rdeta[i + 1][r])
          ans[char(l) + res + char(r)] = true;
      }
    }
  }

  cout << ans.size() << endl;
}


Measured memory_bytes: 4608
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strND = br.readLine().split(" ");
        int N = Integer.parseInt(strND[0]);
        int D = Integer.parseInt(strND[1]);
        
        int[][] X = new int[N][D];
        
        for(int i = 0; i < N; i++){
            String[] strXi = br.readLine().split(" ");
            X[i] = Stream.of(strXi).mapToInt(Integer::parseInt).toArray();
        }
        int ans = 0;
        for(int i = 0; i < N - 1; i++){
            for(int j = i + 1; j < N; j++){
                
                int total = 0;
                for(int k = 0; k < D; k++){
                    total += Math.pow(Math.abs(X[i][k] - X[j][k]), 2);
                }
                
                double x = Math.sqrt(total);
                if ( x == (int) x ) ans++;
                
            }
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 28500
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;

int main(){
    ll n,k;
    cin>>n;
    lvec a(n);
    rep(i,n) cin>>a[i];
    sort(a.begin(),a.end());
    k=a[n-1];
    if(k%2==0){
        ll m=lower_bound(a.begin(),a.end(),k/2)-a.begin();
        if(m!=0){
            if(k-a[m]>a[m-1]) cout<<k<<" "<<a[m];
            else cout<<k<<" "<<a[m-1];
        }
        else cout<<k<<" "<<a[m];
    }else{
        ll m=lower_bound(a.begin(),a.end(),(k+1)/2)-a.begin();
        if(m!=0){
            if(k-a[m]>a[m-1]) cout<<k<<" "<<a[m];
            else cout<<k<<" "<<a[m-1];
        }
        else cout<<k<<" "<<a[m];
    }
}

Measured memory_bytes: 1024
import sys

a = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'.split(', ')

k = int(sys.stdin.readline().rstrip())

def main():
    return a[k-1]

if __name__ == "__main__":
    ans = main()
    print(ans)

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

int main() {
  int n,ans;
  cin >> n;
  ans = n;
  vector<string> s(n);
  for(int i = 0; i < n; i++){
    cin >> s.at(i);
  }
  sort(s.begin(),s.end());
  string a = s.at(0);
  for(int i = 1; i < n; i++){
    if(s.at(i) == a){
      ans--;
    }else{
      a = s.at(i);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 9600
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        for (int i=10*B;i<10*B+10;i++) {
            if (Math.floor(i*0.08)==A) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }
}

Measured memory_bytes: 23764
c=[]
d={}
while 1:
    a,b=map(int,input().split(','))
    if a==0:break
    c+=[b]
    d[a]=b
c=sorted(set(c))[::-1]
while 1:
    try:print(c.index(d[int(input())])+1)
    except:break

Measured memory_bytes: 7636
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <unordered_map>
#include <iomanip>

#define DEBUG(x) cout << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<pair<T, T> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;

	vector<int> votes(n);
	int sum = 0;
	for (int i = 0; i < n; ++i) {
		cin >> votes[i];
		sum += votes[i];
	}

	double min_votes = (double) sum / (4 * m);

	sort(votes.rbegin(), votes.rend());
	int chosen = 0;
	for (int i = 0; i < n; ++i) {
		if (votes[i] >= min_votes) {
			++chosen;
		}
	}

	if (chosen >= m) {
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}

	return 0;

}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <algorithm>
#include <vector>
#include <queue>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <sstream>
#include <cassert>
#include <functional>
#include <cfloat>
#include <climits>
#include <cstring>
#include <stack>
#include <time.h>
#include <complex>
#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
#define forn(i,n) for(int i=0;i<(int)(n);i++)
#define ford(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define fore(i,a,n) for(int i=(int)(a);i<(int)(n);i++)
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define last(a) (int(a.size())-1)
#define all(a) a.begin(),a.end()
const double EPS=1E-9;
const int INF=1000000000;
const int64 INF64=(int64) 1E18;
const double PI=3.1415926535897932384626433832;
char s[12345];
int main()
{
	cin>>s;
	int len=strlen(s);
	long long ans=0;
	forn(t,(1<<(len-1))){
		long long num=s[0]-'0';
		forn(i,len-1){
			if(t & (1<<i)){
				ans+=num;
				num=0;
			}
			num=num*10+s[i+1]-'0';
		}
		ans+=num;
	}
	cout<<ans<<endl;
    return 0;
}


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

int main() {
  string S;
  char temp='R';
  cin >> S;
  int cnt=0,ans=0;
  rep(i,3){
    if(S[i]=='S') {
      temp ='S';
      if(cnt>ans) ans = cnt;
      cnt=0;
    }
    else {
      temp ='R';
      cnt++;
      if(cnt>ans) ans = cnt;
    }
  }
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
 
template <class T> using V = vector<T>;
 
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;
}
 
const long long INF = 1LL << 60;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 

vll dp(100100);

ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    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;
    }
}
 
 
#define comuse Comuse()
 
ll combi(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;
}
 
 
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll n;
  	cin>>n;
  vll A(n);
  FOR(i,0,n){
    cin>>A[i];
  }
  SORT(A);
  ll ans=0;
  FOR(i,2,n){
    FOR(j,1,i){
      FOR(k,0,j){
        if(A[i]<A[j]+A[k]){
          ans++;
        }
      }
    }
  }
  co(ans)
}

Measured memory_bytes: 1024
use std::io::BufRead;

fn main() {
	print!("{}", result())
}

fn result() -> i64 {
	let stdin = std::io::stdin();
	let num = stdin.lock().lines()
		.skip(1)
		.flat_map(|l| l)
		.map(|l|
			l.split_whitespace()
				.flat_map(|s| s.parse::<i64>())
				.fold(0, |a, b| b - a)
				+ 1)
		.sum();
	num
}


Measured memory_bytes: 4352
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

int main() {
  int Q; cin >>Q;
  REP(q, Q){
    int ans = -1, cnt = 0;
    string s; cin >>s;
    set<string> S;
    while(S.find(s) == S.end()){
      if((int)s.length() == 1){
        ans = cnt;
        break;
      }
      ++cnt;
      S.insert(s);
      int tmp = 0;
      FOR(i, 1, (int)s.length()){
        int a = atoi(s.substr(0, i).c_str()), b = atoi(s.substr(i).c_str());
        tmp = max(tmp, a * b);
      }
      stringstream ss; ss <<tmp;
      s = ss.str();
    }
    cout <<ans <<endl;
  }
  return 0;
}

Measured memory_bytes: 1240
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod = 1e9 + 7;
void solve(){
    int n, y;
    cin >> n >> y;
    for (ll i = 0; i <= n; ++i) {
        for (ll j = 0; j <= n-i; ++j) {
            ll k = n - i - j;
            if (i * 10000ll + 5000ll * j + 1000ll * k == y) {
                cout << i << ' ' << j << ' ' << k;
                return;
            }
        }
    }
    cout << -1 << ' ' << -1 << ' ' << -1;
}
int main(){
    speed;
    int t = 1;
    //cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			String s = sc.next();
			String t = sc.next();
			if(s.compareTo("0")==0 && t.compareTo("0")==0)break;
			
			int hit = 0;
			int blow = 0;
			int temp = 0;
			int[] n = new int[4];
			for(int i=0;i<4;i++){
				n[i] = Integer.valueOf(s.substring(i,i+1));
			}
			for(int i=0;i<4;i++){
				temp = Integer.valueOf(t.substring(i,i+1));
				for(int j=0;j<4;j++){
					if(temp==n[j]){
						if(i==j)hit++;
						else blow++;
					}
				}
			}
			System.out.println(hit + " " + blow);
		}
	
	}	
}

Measured memory_bytes: 45976
//参照https://atcoder.jp/contests/diverta2019-2/submissions/5920210
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>
#include <string>

#define SIZE 55
using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;

ll x[SIZE],y[SIZE];
int main(void){
    int n;
    scanf("%d",&n);
    set <P> st;
    for(int i=0;i<n;i++){
         scanf("%lld %lld",&x[i],&y[i]);
         st.insert(P(x[i],y[i]));
    }
    vector <P> vx;
    int ret=0;
    for(int i=0;i<n;i++){
         for(int j=0;j<n;j++){
              if(i==j) continue;
              P p=P(x[i]-x[j],y[i]-y[j]);
              int cnt=0;
              for(int k=0;k<n;k++){
                   P q=P(p.first+x[k],p.second+y[k]);
                   if(st.count(q)) cnt++;
              }
              ret=max(ret,cnt);
         }
    }
    printf("%d\n",n-ret);
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 *
 * @author Suraj
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner in = new Scanner(System.in);
        int n= in.nextInt();
        String s= Integer.toString(n);
        int l=s.length();
        int p=(int) Math.pow(10, l-1);
        if(p==n){
            System.out.println(10);
        }
        else{
            int sum=0;
            int m;
            while(n > 0)
        {
            m = n % 10;
            sum = sum + m;
            n = n / 10;
        }
            System.out.println(sum);
        }
    }
    
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)
#define int long long

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

inline int gi()
{
	int f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

inline LL gl()
{
	LL f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 100003, M = N << 1;

int n, m;
int a[N], b[N], dp[N], s[N];
int c[N], id[N];
int fa[N], x[N];
vector <int> g[N];
int head[N], ver[M], nxt[M], tot;

inline bool cmp(int x, int y) {return c[x] < c[y];}

int getf(int u) {return fa[u] == u ? u : fa[u] = getf(fa[u]);}

void dfs(int u, int f)
{
	s[u] = b[u];
	for (int i = head[u]; i; i = nxt[i])
	{
		int v = ver[i];
		if (v == f) continue;
		dfs(v, u);
		s[u] += s[v];
	}
}

void dfs1(int u, int f)
{
	if (!head[u]) dp[u] = b[u] + c[u];
	else dp[u] = 1e18;
	for (int i = head[u]; i; i = nxt[i])
	{
		int v = ver[i];
		if (v == f) continue;
		dfs1(v, u);
		dp[u] = min(dp[u], s[u] - s[v] + max(c[u], dp[v]));
	}
}

inline void add(int u, int v)
{
	ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}

signed main()
{
	//File("");
	n = gi(), m = gi();
	for (int i = 1; i <= n; i+=1) a[i] = gi(), b[i] = gi(), c[i] = max(0ll, a[i] - b[i]), id[i] = i;
	sort(id + 1, id + 1 + n, cmp);
	for (int i = 1; i <= m; i+=1) {int u = gi(), v = gi(); g[u].push_back(v), g[v].push_back(u);}
//	for (int i = 1; i <= n; i+=1, puts(""))
//		for (int j = 0; j < g[i].size(); j+=1) cout << i << ' ' << g[i][j] << endl;
//	puts("?");
	for (int i = 1; i <= n; i+=1) fa[i] = i, x[id[i]] = i;
//	for (int i = 1; i <= n; i+=1) cout << c[i] << ' ' << id[i] << endl;
//	puts("!");
//	for (int i = 1; i <= n; i+=1) cout << x[i] << ' '; puts("$");
	for (int i = 1; i <= n; i+=1)
	{
		int u = id[i], sz = g[u].size();
		for (int j = 0; j < sz; j+=1)
		{
			int v = getf(g[u][j]);
//			cout << u << ' ' << v << endl;
            if (x[v] < x[u]) add(u, v), fa[v] = u;
		}
	}
//	for (int i = 1; i <= n; i+=1, puts("")) for (int j = head[i]; j; j = nxt[j]) cout << i << ' ' << j << endl;
	dfs(id[n], 0);
//	for (int i = 1; i <= n; i+=1) cout << s[i] << ' '; puts("#");
	dfs1(id[n], 0);
  	printf("%lld\n", dp[id[n]]);
	return 0;
}


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

int main() {
  string s; cin >> s;
  int len = s.size();
  int n; cin >> n;
  
  int cnt = 0;
  while(n--) {
    string tmp; cin >> tmp;
    tmp += tmp.substr(0, len-1);
    for(int i = 0; i < tmp.size(); i++) {
      if(tmp.substr(i, len) == s) {
        cnt++;
        break;
      }
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 1212
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N = int(input())

lst1 = [('a', 0)]
lst2 = []
for i in range(N - 1):
    if i % 2 == 0: #lst1 -->lst2
        lst2 = []
        for s, t in lst1:
            last = max(ord(s[i]) - ord('a'), t)
            for j in range(last + 2):
                lst2.append((s + chr(j + ord('a')), max(t, j)))
    else:
        lst1 = []
        for s, t in lst2:
            last = max(ord(s[i]) - ord('a'), t)
            for j in range(last + 2):
                lst1.append((s + chr(j + ord('a')), (max(t, j))))
           
if len(lst2) > len(lst1):
    lst2.sort()
    for s, t in lst2:
        print (s)
else:
    lst1.sort()
    for s, t in lst1:
        print (s)

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

int main() {
  char s[200000];
  scanf("%s", s);
  int n = (int) strlen(s);
  //printf("%d\n", n);
  int i;
  int a[n];
  long long int ans = 0;
  int b = 0;
  for(i=0;i<n;i++) {
    if(s[i] == 'B') {
      b++;
    } else {
      ans += b;
    }
  }
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, s, n)    for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...)  type __VA_ARGS__; read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream& operator>> (istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail&... tail) { cin >> head; read(tail...); }

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream& operator<< (ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = { " ", "" };
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x): x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

i64 f(i64 n, i64 p) {
    return n - n % p;
}

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

    dump(f(0, 5));
    dump(f(1, 5));
    dump(f(2, 5));
    dump(f(3, 5));

    var(int, N);
    vector<i64> a(N);
    read(a);

    const auto apply = [&](const i64 firstValue) {
        i64 now = firstValue;
        for (const auto p : a) {
            now = f(now, p);
        }
        return now;
    };

    i64 ansLow, ansHigh;
    {
        i64 ng = 0;
        i64 ok = LINF;
        while (ok - ng > 1) {
            const i64 mid = (ok + ng) / 2;
            if (apply(mid) >= 2) ok = mid;
            else ng = mid;
        }
        ansLow = ok;
    }
    {
        i64 ng = 0;
        i64 ok = LINF;
        while (ok - ng > 1) {
            const i64 mid = (ok + ng) / 2;
            if (apply(mid) > 2) ok = mid;
            else ng = mid;
        }
        ansHigh = ng;
    }
    if (ansLow > ansHigh) {
        print(-1);
    } else {
        print(ansLow, ansHigh);
    }

    return 0;
}


Measured memory_bytes: 1024
N, M = gets.chomp.split(' ').map(&:to_i)
pref_city_list =
  M.times.map.with_index { |i| gets.chomp.split(' ').map(&:to_i) + [i] }
group = pref_city_list.group_by(&:first)
answer = group.flat_map do |_, v|
  v.sort_by { |(_, year, _)| year }
   .map.with_index do |(pref, _, i), ii|
     [pref.to_s.rjust(6, '0') + (ii + 1).to_s.rjust(6, '0'), i]
   end
end
.sort_by { |(_, i)| i }
.map(&:first)
puts answer.join("\n")


Measured memory_bytes: 38912
#include <cstdio>
#include <iostream>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iomanip>
#include<string>
using namespace std;
long long a[1000];
long long b[1000];
#define rep(i,n) for(long long i=0;i<n;i++)
int main() {
	long long n;
	cin >> n;
	long long x, y;
	cin >> x >> y;
	rep(i, n) { cin >> a[i] >> b[i]; }
	long long iwa = 0;
	rep(i, n) { if (a[i] >= x && b[i] >= y) { iwa++; } }
	cout << iwa << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
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; }
const long long INF = 1LL << 60;
long long dp[100010];
long long h[100010];
const int MOD = 1000000007;

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

    int cur = 0;
    rep(i, n)
    {
        cur = a[cur] - 1;
        if (cur == 1)
        {
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 640
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <chrono>
#include <climits>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

template <class T1, class T2>
ostream& operator << (ostream& out, const pair <T1, T2> p)
{
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

template <class T1, class T2>
istream& operator >> (istream& in, pair<T1, T2> &p)
{
	in >> p.first >> p.second;
	return in;
}

template <class T>
istream& operator >> (istream& in, vector<T> &v)
{
	for (T &x : v)
		in >> x;
	return in;
}

template <class T>
ostream& operator << (ostream& out, const vector<vector<T>> &v)
{
	for (const vector<T> &x : v)
		out << x << '\n';
	return out;
}

template <class T>
ostream& operator << (ostream& out, const vector<T> &v)
{
	for (const T &x : v)
		out << x << ' ';
	return out;
}

long long gcd (long long a, long long b)
{
	if (b > a)
		swap(a, b);
	return (b ? gcd(b, a % b) : a);
}

using ll   = long long;
using pii  = pair<int, int>;
using pll  = pair<long long, long long>;
using tiii = pair<pair<int, int>, int>;
using vi   = vector<int>;
using vl   = vector<long long>;
using vvi  = vector<vector<int>>;
using vvl  = vector<vector<long long>>;

#define F          first
#define S          second
#define First      first.first
#define Second     first.second
#define Third      second
#define mp         make_pair
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define per(i,b,a) for (int i = (b); i > (a); i--)
#define all(x)     x.begin(), x.end()
#define ret(x)     return cout << x, 0;
#define throwex    throw runtime_error ("Found the error.");

const int h = 1000000007;

signed main()
{
	ios::sync_with_stdio(false);
	#ifdef ONLINE_JUDGE
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.setstate(ios::failbit);
	#endif

	string s;
	cin >> s;
	rep(i,0,s.size())
		if(s[i] == '?')
			s[i] = 'D';
	int ans = 0;
	rep(i,1,s.size())
		if(s[i] == 'D' and s[i-1] == 'P')
			ans++;
	cout << s;
	// cout << ans + count(all(s), 'D');
}


Measured memory_bytes: 3772
n, m = map(int, input().split())
hList = list(map(int, input().split()))
rootList = [list(map(int, input().split())) for _ in range(m)]
obsList = [1 for _ in range(n)]
for i in rootList:
    a, b = i[0]-1, i[1]-1
    aH, bH = hList[a] , hList[b]
    if aH >= bH:
        obsList[b] = 0
    if aH <= bH:
        obsList[a] = 0
print(sum(obsList))


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

using namespace std;

//#define MD 100010

int main(){
    int n;
    cin>>n;
    vector<long int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    long int ansl=0,ansr=0;
    sort(v.begin(),v.end());
    
    ansl=v[n-1];
    
    auto l = lower_bound(v.begin(),v.end(),ansl/2);
    if(*l==ansl/2){
        ansr=*l;
    }else if(*l==ansl){
        ansr=v[distance(v.begin(),l)-1];
    }else{
        if(distance(v.begin(),l)==0){
            ansr=*l;
        }else if(ansl%2==0){
            long int tmp1=abs(ansl/2-v[distance(v.begin(),l)]);
            long int tmp2=abs(ansl/2-v[distance(v.begin(),l)-1]);
            if(min(tmp1,tmp2)==tmp1){
                ansr=v[distance(v.begin(),l)];
            }else{
                 ansr=v[distance(v.begin(),l)-1];
            }
        }else{
            long int tmp1=abs((ansl/2+1)-v[distance(v.begin(),l)]);
            long int tmp2=abs((ansl/2+1)-v[distance(v.begin(),l)-1]);
            if(min(tmp1,tmp2)==tmp1){
                ansr=v[distance(v.begin(),l)];
            }else{
                 ansr=v[distance(v.begin(),l)-1];
            }
        }
    }
    
    cout<<ansl<<" "<<ansr<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

class Point {
public:
	double x, y;
	Point(double x = 0, double y = 0) :
			x(x), y(y) {
	}

	Point operator +(Point& p) {
		return Point(x + p.x, y + p.y);
	}
	Point operator -(Point& p) {
		return Point(x - p.x, y - p.y);
	}
	Point operator *(double a) {
		return Point(x * a, y * a);
	}
	Point operator /(double a) {
		return Point(x / a, y / a);
	}
	bool operator <(const Point& p) const {
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator ==(const Point& p) const {
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
};

class Segment {
public:
	Point p1, p2;
	Segment(Point p1, Point p2) :
			p1(p1), p2(p2) {

	}
};

int dot(Point p1, Point p2) {
	return p1.x * p2.x + p1.y * p2.y;
}
int cross(Point p1, Point p2) {
	return p1.x * p2.y - p1.y * p2.x;
}

bool isOrthogonal(Segment s1, Segment s2) {
	return equals(dot(s1.p1 - s1.p2, s2.p1 - s2.p2), 0.0);
}

bool isParallel(Segment s1, Segment s2) {
	return equals(cross(s1.p1 - s1.p2, s2.p1 - s2.p2), 0.0);
}

int main() {

	int q;
	scanf("%d", &q);

	for (int i = 0; i < q; ++i) {
		int p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y;
		scanf("%d %d %d %d %d %d %d %d", &p0x, &p0y, &p1x, &p1y, &p2x, &p2y, &p3x, &p3y);

		Point p1(p0x, p0y);
		Point p2(p1x, p1y);
		Point p3(p2x, p2y);
		Point p4(p3x, p3y);
		Segment s1(p1, p2);
		Segment s2(p3, p4);

		if (isOrthogonal(s1, s2)) {
			cout << 1 << endl;
		} else if (isParallel(s1, s2)) {
			cout << 2 << endl;
		} else {
			cout << 0 << endl;
		}
	}
	return 0;
}

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

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9+7;

int main() {
    int n; cin >> n;
    vector<int> a(n); rep(i, n) cin >> a[i];
    map<int, int> mp;
    rep(i, n) {
        mp[a[i]]++;
    }
    ll ans = 0;
    for (auto p: mp) {
        ll cnt = p.second;
        ans += cnt * (cnt-1) / 2;
    }

    rep(i, n) {
        cout << ans - (mp[a[i]]-1) << endl;
    }

    return 0;
}

Measured memory_bytes: 9472
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif


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

    ll N; cin >> N;
    vll a(N);
    rep(i,N) cin >> a[i];
    rep(i, N) if(a[i] == 0) {
        cout << 0 << endl;
        return 0;
    }

    boost::multiprecision::uint128_t ans = 1, INF = 1000000000000000000;
    rep(i, N) {
        ans *= a[i];
        if(INF < ans) {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3972
#include <bits/stdc++.h>    
using namespace std;
#define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb  push_back
#define show(x) cout<<(#x)<<" : "<<x<<endl;
#define ll  long long
#define int long long
#define ld  long double
#define fill(a,val) memset(a,val,sizeof(a))
#define mp  make_pair
#define ff  first
#define ss  second
#define pii pair<ll,ll>
#define sq(x) ((x)*(x))
#define all(v) v.begin(),v.end()
#define fone for(i=0;i<n;i++)
#define endl "\n"
const ll MOD     = 1000*1000*1000+7;
const ll INF     = 1ll*1000*1000*1000*1000*1000*1000 + 7;
const ll MOD2    = 998244353;
const ll N          = 5000*100+1;
const ll N2      = 1000*1000+5;
const ld PI  = 3.14159265;
const ll R   = 250;
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);} 
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;} 
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
    }


signed main ()
{
  fastio();
  int n,k,W;
  vector<pair<int,int>>vv;
  cin>>n>>W;

  int v[n],w[n];
  for(int i=0;i<n;i++)
  {
    cin>>w[i]>>v[i];
     vv.pb(mp(w[i],v[i]));
  }
  sort(all(vv));


  //cout<<"*";
  vector<vector<ll> > dp(n+1,vector<ll>(W+1,0LL));
  
  for (int i = 1; i <=n; i++)
  {
    for (int j = 0; j <= W; j++)
    {
      if(j-w[i-1]<0) dp[i][j] = dp[i-1][j];
      else dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
    }
  }
   int ans=0;
  for (int j = 0; j <= W; j++)
  {
    ans = max(ans,dp[n][j]);
  }
  cout<<ans<<endl;
  
return 0;
  
}




Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

int main(){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll ans=a*c;
    ans=max(ans,a*d);
    ans=max(ans,b*c);
    ans=max(ans,b*d);

    cout<<ans<<endl;

} 


Measured memory_bytes: 3632
#include<iostream>
#include<cstdlib>
using namespace std;

#define check cout<<"-------"<<endl
#define debug(x) cout<<x<<endl;
#define loop(i,x,n) for(int i = x; i < n; i++)
#define lop(i,n) repi(i,0,n)
#define fix(x) cout<<fixed<<setprecision(x);

//Node構造体
typedef struct node {
    int value = -1;
    node *parent = nullptr;  //親
    node *left = nullptr; //左の子
    node *right = nullptr; //右の子
} Node;

//rootノードの仮作成
Node *root = nullptr;

void Find(Node *, int);
void Free(Node *);
void Insert(int);
void InorderPrint(Node *);
void PreorderPrint(Node *);

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N; //命令の数
    cin>>N;
    
    char cmd[7]; //命令
    int v; //値
    while(N--) {
        cin>>cmd;
        if(cmd[0] == 'i') {  //入力がinsertの時
            cin>>v;
            Insert(v);
        } else if(cmd[0] == 'p') { //入力がprintの時
            InorderPrint(root);
            cout<<endl;
            PreorderPrint(root);
            cout<<endl;
        } else if(cmd[0] == 'f') {
            cin>>v;
            Find(root, v);
        }
    }
    Free(root);
    return 0;
}

//検索
void Find(Node *a, int v) {
    Node *subroot = root;
    while(subroot != nullptr) {
        if(subroot->value == v) {
            cout<<"yes"<<endl;
            return;
        }
        else if(subroot->value > v) subroot = subroot->left;
        else if(subroot->value < v) subroot = subroot->right;
    }
    cout<<"no"<<endl;
}

//メモリの開放
void Free(Node *a) {
    if(a->left != nullptr) Free(a->left);
    if(a->right != nullptr) Free(a->right);
    free(a);
}

//ノードを追加
void Insert(int x) {
    
    //追加するノードの作成
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->value = x;
    
    //rootノード作成
    if(root == nullptr) {
        root = newNode;
        return;
    }
    
    Node *y;
    Node *subroot = root;
    while(subroot != nullptr) {
        y = subroot;
        if(subroot->value > x) subroot = subroot->left;
        else if(subroot->value < x) subroot = subroot->right;
    }
    
    newNode->parent = y;
    if(y->value > x) y->left = newNode;
    else if(y->value < x) y->right = newNode;
}

//inorder巡回
void InorderPrint(Node *a) {
    if(a->left != nullptr) InorderPrint(a->left);
    cout<<' '<<(*a).value;
    if(a->right != nullptr) InorderPrint(a->right);
}

//preorder巡回
void PreorderPrint(Node *a) {
    cout<<' '<<a->value;
    if(a->left != nullptr) PreorderPrint(a->left);
    if(a->right != nullptr) PreorderPrint(a->right);
}



Measured memory_bytes: 21900
#include<bits/stdc++.h>
const int M=1e6;
using namespace std;
typedef long long ll;
const ll inf=1e18;
vector<pair<int,int>>v[M];
bool mark[M];
ll d[M];
void dijikstra(int x){
	fill(d,d + M, inf);
	fill(mark, mark + M, false);
	d[x] = 0;
	int u;
	priority_queue<pair<ll,int>,vector<pair<ll,int> >, greater<pair<ll,int> > > pq;
	pq.push({d[x], x});
	while(!pq.empty()){
		u = pq.top().second;
		pq.pop();
		if(mark[u])
			continue;
		mark[u] = true;
		for(auto p : v[u]) 
			if(d[p.first] > d[u] + p.second){
				d[p.first] = d[u] + p.second;
				pq.push({d[p.first], p.first});
			}
	}
}
int main() {
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		v[x].push_back({y,w});
		v[y].push_back({x,w});
	}
	int q,k;
	cin>>q>>k;
	dijikstra(k);
	while(q--)
	{
		int x,y;
		cin>>x>>y;
		cout<<d[x]+d[y]<<endl;
	}
	return 0;
}

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

#define inf 0x3f3f3f3f
#define INF 1000111000111000111LL
#define mod 1000000007
#define endl '\n'
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fi first
#define se second
#define all(cc) (cc).begin(),(cc).end()
using lli = long long int ;
using pii = pair<int, int> ;
using vi = vector<int> ;
using vb = vector<bool> ;
using vvi = vector<vector<int>> ;
using vlli = vector<long long int> ;
using vpii = vector<pair<int, int>> ;

int main()
  {
    ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
    int n, m, N, i, j, c ;
    bool dir=true ;
    cin>> n >> m ;
    cin>> N ;
    int grid[n+1][m+1]={0} ;
    vi a(N) ;
    for(int i=0 ; i<N ; i++)
      cin>> a[i] ;
    i=0 ; j=0 ; c=0 ;
    while(i<n)
      {
        if(dir)
          {
            if(a[c])
              {
                while(a[c])
                  {
                    grid[i][j]=c+1 ;
                    a[c]-- ;
                    if(j+1<m) j++ ;
                    else
                      {
                        i++ ;
                        j=m-1 ;
                        dir=false ;
                        break ;
                      }
                  }
              }
            else c++ ;
          }
        else
          {
            if(a[c])
              {
                while(a[c])
                  {
                    grid[i][j]=c+1 ;
                    a[c]-- ;
                    if(j-1>=0) j-- ;
                    else
                      {
                        i++ ;
                        j=0 ;
                        dir=true ;
                        break ;
                      }
                  }
              }
            else c++ ;
          }
      }
    for(int i=0 ; i<n ; i++)
      {
        for(int j=0 ; j<m ; j++)
          cout<< grid[i][j] << " " ;
        cout<< endl ;
      }
  }


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
    int w;
    int h;
    int x;
    int y;
    int r;
    cin >> w >>h >>x >> y >>r;
    if (x<0||y<0) cout << "No" << endl;

    else if (x+r>w || y+r>h) cout << "No" << endl;
    else  cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 3112
EPS = 0.0001
while True:
    try:
        a = list(map(float, input().split()))
        dd = a[0]*a[4]-a[3]*a[1]
        d1 = a[2]*a[4]-a[5]*a[1]
        d2 = a[0]*a[5]-a[3]*a[2]
        print("{0:.3f} {1:.3f}".format(d1/dd+EPS, d2/dd+EPS))
    except EOFError:
        break


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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
constexpr int mod = 1e9 + 7;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator-=(const mint a) {
    if ((x += mod - a.x) >= mod) x -= mod;
    return *this;
  }
  mint &operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1) a *= *this;
    return a;
  }
  mint inv() const { return pow(mod - 2); }
  mint &operator/=(const mint a) { return (*this) *= a.inv(); }
  mint operator/(const mint a) const {
    mint res(*this);
    return res /= a;
  }
  friend ostream &operator<<(ostream &os, const mint &a) { return (os << a.x); }
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

int n;
int k;
vector<vector<bitset<7>>> t;

int main() {
  int k, n;
  cin >> k >> n;
  vector<int> a(n);
  vector<int> d(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (i > 0) d[i] = a[i] - a[i - 1];
  }
  d[0] = a[0] + (k - a[n - 1]);

  cout << k - *max_element(d.cbegin(), d.cend()) << endl;
}


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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b,c; cin>>a>>b>>c;
	if (b-a==c-b) cout<<"YES";
	else cout<<"NO";
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<deque>
#include<queue>
#include<math.h>
#include<string>
#include<string.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<iomanip>
#include<map>
#include<unordered_map>
 
#include<algorithm>
#define inf 0x3f3f3f3f
#define sup_inf 2e18
#define pb push_back
 
#define ii pair<int,int>
#define f first
#define s second
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define iii pair<int, ii >
#define in freopen("entrada","r",stdin);
#define out freopen("myfile.txt", "w", stdout);
#define eps 1e-9
#define id pair<int ,double > 
#define di pair<double, int>
 
#define pi 3.14159265359
#define nl (no<<1)	
#define nr ( (no<<1)|1)
#define mid l + ( (r-l)>>1)
 
using namespace std;
		
const int maxn = 5e5 + 100;
const int MAX = 5e3 + 10;
typedef long long ll;
typedef vector< int> vi;		
  
  
 
int q;
string str;
int main (){
	//~ in
	
	fast_io
	
	cin >> str >> q;
 
	deque< char > ar;
	
	for(int i = 0 ;i < (int)str.size();i++) {
		ar.push_back ( str[i] );
	}
 
	int rev = 0;
	while (q--) {
		int x; 
		cin >> x;
		if (x == 1){
			rev^=1;
			
		}else {
			int w;
			char y;
			cin >> w >> y;
			if ( w == 2 )w = 0;
			if ( (w+rev)&1 ){
				ar.push_front(y);
			}else {
				ar.push_back(y);
			}
		}
	}
	
 
	
	if ( !rev ) {
		while ( !ar.empty()){ 
			cout << ar.front();
			ar.pop_front();
		}
	}else {
		while ( !ar.empty()){ 
				cout << ar.back();
				ar.pop_back();
		}
	}
	
	cout << '\n';
	
	return 0;
}


Measured memory_bytes: 976
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<pair<int, int>> weights(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> weights[i].first >> weights[i].second;
    vector<vector<int>> dp(n+1, vector<int>(w + 1));
    for (int i=1; i<=n; i++)
        for (int j=1; j<=w; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= weights[i].first)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i].first] + weights[i].second);
        }
    cout << dp.back().back() << "\n";
}

Measured memory_bytes: 83096
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359

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

	string S;
	cin >> S;
	bool flg[4] = {};
	for(int i=0; i<S.size(); i++){
		if(S[i] == 'N') flg[0] = true;
		if(S[i] == 'S') flg[1] = true;
		if(S[i] == 'W') flg[2] = true;
		if(S[i] == 'E') flg[3] = true;
	}
	if(flg[0] != flg[1] || flg[2] != flg[3]) cout << "No" << endl;
	else cout << "Yes" << endl;

	return 0;
}

Measured memory_bytes: 256