akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
ll modexpo(ll a,ll b)
{
     ll ans=1LL;
     while(b>0)
     {
          if(b&1)ans=(ans*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return ans;
}
 
 
 
 
 
 
 
















int n,m;
int par[100005];
ll s[100005];
ll res[100005];
int find(int a){
     if(par[a]==a)return a;
     return par[a]=find(par[a]);
}
vector<pair<int,int>> edge;
int main()
{
     cin>>n>>m;
     for(int i=1;i<=n;i++){par[i]=i;s[i]=1;}
     edge.resize(m);
     for(int i=0;i<m;i++){
          cin>>edge[i].fi>>edge[i].se;
     }
     ll sum=1LL*n*(n-1)/2;
     res[m-1]=sum;
     for(int i=m-1;i>=1;i--){
          int x=edge[i].fi,y=edge[i].se;
          x=find(x),y=find(y);
          if(x==y){ res[i-1]=res[i];
          continue;}
         // cout<<s[x]<<" "<<s[y]<<"\n";
          res[i-1]=res[i]-1LL*s[x]*s[y];
          s[x]+=s[y];
          par[y]=x;
         
     }
     for(int i=0;i<m;i++)cout<<res[i]<<"\n";

}























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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i = 0;i<n;i++)arr[i]=sc.nextInt();
		Arrays.sort(arr);
		int bot = arr[n/2-1];;
		int top = arr[(n/2)];
		System.out.println(top-bot);
	}

}


Measured memory_bytes: 51960
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a,b,c,d;
    cin>>a>>b>>c>>d;
    long long int s[4];
    s[0]=a*c;
    s[1]=a*d;
    s[2]=b*c;
    s[3]=b*d;
   long long int s1,s2;
    s1=max(s[0],s[1]);
    s2=max(s[2],s[3]);
    cout<<max(s1,s2)<<endl;
    return 0;
}



Measured memory_bytes: 3644
OK = 0
BRO = 1

N,M=map(int, input().split())
Broken=[int(input()) for i in range(M)]
#K = "".join(list(BRO if i in Broken else OK for i in range(N+1)))
K = list(0 for i in range(N+1))
for i in range(M):
  K[Broken[i]] = 1
  
if N == 1:
  print(1)
  exit()
  
c=[0 for i in range(N+1)]
if K[N-1]==OK:
  c[1]=1
if K[N-2]==OK and K[N-1]==OK:
  c[2]=2
if K[N-2]==OK and K[N-1]==BRO:
  c[2]=1

for i in range(3,N+1):
  if K[N-i]==OK:
    if K[N-i+1]==OK and K[N-i+2]==OK:
      c[i]=c[i-1]+c[i-2]
    if K[N-i+1]==OK and K[N-i+2]==BRO:
      c[i]=c[i-1]
    if K[N-i+1]==BRO and K[N-i+2]==OK:
      c[i]=c[i-2]
  c[i]%=1000000007
  
print(c[N] % 1000000007)


Measured memory_bytes: 8648
import java.util.Scanner;
import java.lang.Math;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        double aa = 0;
        for(int i = 0; i<n ; i++){
            a[i]=sc.nextInt();
            aa = aa + a [i];
        }
        sc.close();

        a = sort(a);
        if(a[m-1] >= aa/(4.0*m)){
            System.out.println("Yes");          
        }else{
            System.out.println("No");
        }
    }
    public static int[] sort(int[] a){
        int x;
        for(int i=0;i<a.length;i++){
            x = a[i];
            for(int j=0;j<a.length;j++){
                if(x == Math.max(x,a[j])){
                    a[i]=a[j];
                    a[j]=x;
                    x=a[i];
                }
            }
        }
        return a;
    }
}

Measured memory_bytes: 23252
n=gets.to_i

arr=[[0,0,0]]
n.times{
    a,b,c=gets.split
    a=a.to_i
    b=b.to_i
    c=c.to_i
 arr<<[a,b,c]   }
 
i=0
n.times{
  ss=arr[i+1][0]-arr[i][0]
   tt=arr[i+1][1]-arr[i][1]
   tt=tt.abs
   uu=arr[i+1][2]-arr[i][2]
   uu=uu.abs
   
   
   if (ss+tt+uu)%2==0 && ss>=tt+uu
       i+=1
   else puts "No"
       exit
   end
    
}



puts "Yes"

Measured memory_bytes: 9596
N, K = gets.split.map(&:to_i)
P = gets.split.map(&:to_i)

S = Array.new(1000 + 1)
sum = 0
(1..1000).each do |n|
  sum += n
  S[n] = sum / n.to_f
end

list = Array.new(N)
current = 0
P.each.with_index do |n, i|
  current = current + S[n]
  list[i] = current
end

ans = 0
N.times do |i|
  break if i + K > N
  ret = list[i + K - 1] - (i == 0 ? 0 : list[i - 1])
  ans = ret if ret > ans
end
puts ans

Measured memory_bytes: 16524
#include<iostream>
using namespace std;
int main(){
  int N; cin>>N;
  int A[100],B[100];
  for(int i=0;i<N;i++){
    A[i]=0;
    B[i]=0;
  }
  for(int i=0;i<N;i++)
    cin>>A[i]; 
  for(int i=0;i<N;i++)
    cin>>B[i];
  for(int i=1;i<N;i++)
    A[i]+=A[i-1];
  for(int i=2;i<=N;i++)
    B[N-i]+=B[N-i+1];
  int ans=0;
  for(int i=0;i<N;i++)
    ans=max(ans,A[i]+B[i]);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
cnt=0
flg=True
while flg:
    for i in range(n):
        if a[i]%2==0:
            a[i]//=2
        else:
            flg=False
            break

    cnt+=1
print(cnt-1)


Measured memory_bytes: 38512
long long i,j,e,t,w,u,x[1<<17],y[1<<17];
int main(n){
  scanf("%d%lld%lld",&n,&e,&t);
  for(x[n]=2*e;i<n;){
    scanf("%lld",&x[i]);
    x[i++]*=2;
  }
  for(i=0,w=1ll<<50;i<n;){
    for(;j<i&&t<x[i]-x[j];){
      u=y[j]+x[i]-x[j++];
      w=w<u?w:u;
    }
    u=x[i]-x[j];
    u=y[j]+(u<t?t:u);
    y[i+1]=w<u?w:u;
    w+=(x[i+1]-x[i++]);
  }
  printf("%lld\n",y[n]+e);
  return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <vector>
#include <cfloat>
#include <string>
#include <cmath>
#include <set>
#include <cstdlib>
#include <map>
#include <ctime>
#include <iomanip>
#include <functional>
#include <deque>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <stack>
#include <climits>
#include <sys/time.h>
#include <cctype>

using namespace std;

typedef long long ll;


#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(a*x, a*y); }
  Point operator / (double a) { return Point(x/a, y/a); }

  double norm() { return x*x+y*y; }
  double abs() { return sqrt(norm()); }

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

typedef Point Vector;
typedef vector <Vector> Polygon;

class Segment {
 public:
  Point p1, p2;

  Segment(Point p1 = Point(), Point p2 = Point()): p1(p1), p2(p2) {}
};

double norm(Vector a) {
  return a.x*a.x+a.y*a.y;
}

double abs(Vector a) {
  return sqrt(norm(a));
}

// ?????????|a||b|cos
double cross(Vector a, Vector b) {
  return a.x*b.y-a.y*b.x;
}
// ?????????|a||b|sin
double dot(Vector a, Vector b) {
  return a.x*b.x+a.y*b.y;
}

// 1:???????¨??????? -1:????¨??????? 2:p2-p0-p1 -2:p0-p1-p2 0:p2???p0-p1???
int ccw(Point p0, Point p1, Point p2) {
  Vector a = p1-p0;
  Vector b = p2-p0;
  if (cross(a, b) > EPS) return 1;
  if (cross(a, b) < -EPS) return -1;
  if (dot(a, b) < -EPS) return 2;
  if (a.norm() < b.norm()) return -2;

  return 0;
}

// ??´?????????
bool isOrthogonal(Vector a, Vector b) {
  return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) {
  return isOrthogonal(a1-a2, b1-b2);
}

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

// ????????????
bool isParallel(Vector a, Vector b) {
  return equals(cross(a, b), 0.0);
}

bool isParallel(Point a1, Point a2, Point b1, Point b2) {
  return isParallel(a1-a2, b1-b2);
}

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

// ????????????
// p1!=p2????????????p3!=p4????????¶
bool intersect(Point p1, Point p2, Point p3, Point p4) {
  return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0 &&
          ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0);
}
bool intersect(Segment s1, Segment s2) {
  return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}


int main() {
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    Segment s1, s2;
    cin >> s1.p1.x >> s1.p1.y >> s1.p2.x >> s1.p2.y
        >> s2.p1.x >> s2.p1.y >> s2.p2.x >> s2.p2.y;
    cout << intersect(s1, s2) << endl;
  }
}

Measured memory_bytes: 1232
#include <iostream>

using namespace std;

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

  int a, b;
  cin >> a >> b;
  if (a + b == 15) {
    cout << "+" << endl;
  } else if (a * b == 15) {
    cout << "*" << endl;
  } else {
    cout << "x" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i,n) for (int i = 1; i < (int)(n+1); i++)
#define N_MAX 110
#define K_MAX 100010

int main() {
  int P, Q, R;
  cin >> P >> Q >> R;

  int res = P + Q + R - max(max(P, Q), R);

  cout << res << endl; 
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; ++i)

using namespace std;
using ll = long long;

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int n; cin >> n;
    map<string, int> m;
    rep(i, n){
        string s; cin >> s;
        m[s]++;
    }
    int Mx = 0;
    for (auto &&i : m)
    {
        Mx = max(Mx, i.second);
    }
    for (auto &&i : m)
    {
        if (Mx == i.second){
            cout << i.first << endl;
        }
    }
    
}

Measured memory_bytes: 23808
#include<bits/stdc++.h>
using namespace std;using ll=long long;using vi=vector<int>;using vvi=vector<vi>;using vl=vector<ll>;using vvl=vector<vl>;using P=pair<int,int>;using PL=pair<ll,ll>;using vp=vector<P>;using vpl=vector<PL>;
template<typename T>constexpr auto inf=numeric_limits<T>::max()/2;constexpr int INF=inf<int>,MOD=1000000007;constexpr ll LINF=inf<ll>;
#define _ol3(_1,_2,_3,name,...)name
#define _rep(i,n)_repi(i,0,n)
#define _repi(i,a,b)for(int i=a,i##_l=(b);i<i##_l;++i)
#define REP(...)_ol3(__VA_ARGS__,_repi,_rep,)(__VA_ARGS__)
#define REPR(i,n)for(int i=n-1;i>=0;--i)
#define REPA(i,v)REP(i,(v).size())
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define bit(n)(1ll<<(n))
#define F first
#define S second
#define endl '\n'
#define cho(n,a,b)cout<<((n)?a:b)<<endl
void YES(int n){cho(n,"YES","NO");}void Yes(int n){cho(n,"Yes","No");}void Poss(int n){cho(n,"Possible","Impossible");}
void _print(ostream&){}template<class T,class...U>void _print(ostream&s,const T&t,const U&...u){s<<t<<(sizeof...(u)?' ':'\n');_print(s,u...);}
template<class...T>void print(const T&...t){_print(cout,t...);}template<class...T>void dprint(const T&...t){_print(cerr,t...);}
#ifndef LOCAL
struct osd{template<class T>osd&operator<<(const T&t){return*this;}};osd cer_;
#define dprint(...)
#define cerr cer_
#endif
template<class T>bool chmax(T&a,const T&b){bool x=a<b;x?a=b:b;return x;}template<class T>bool chmin(T&a,const T&b){bool x=a>b;x?a=b:b;return x;}
template<class T,class U>ostream&operator<<(ostream&o,const pair<T,U>&p){return o<<p.F<<' '<<p.S;}
template<class T,class U>istream&operator>>(istream&i,pair<T,U>&p){return i>>p.F>>p.S;}
template<class T>class iterable{static false_type c(string v);template<class U>static auto c(U v)->decltype(all(v),true_type());static false_type c(...);public:const static bool value=decltype(c(declval<T>()))::value;};
template<class T,typename=enable_if_t<iterable<T>::value>>ostream&operator<<(ostream&o,const T&v){for(auto&&i:v)o<<i<<' ';return o;}
template<class T>istream&operator>>(istream&i,vector<T>&v){for(T&j:v)i>>j;return i;}
template<class T>vector<T>&operator<<(vector<T>&v,const T&t){v.push_back(t);return v;}
template<class T>set<T>&operator<<(set<T>&v,const T&t){v.insert(t);return v;}
template<class T>multiset<T>&operator<<(multiset<T>&v,const T&t){v.insert(t);return v;}

int main(){
    cin.tie(0);ios::sync_with_stdio(0);
    int n;
    cin>>n;
    vi b(n);
    REP(i,n){
        int a;
        cin>>a;
        b[a-1]=i+1;
    }
    cout<<b<<endl;

}


Measured memory_bytes: 1280
import sys
K = int(input())
A,B = map(int,input().split())

if not ( 1 <= K <= 1000 ): sys.exit()
if not ( 1 <= A <= 1000 and A <= B <= 1000 ): sys.exit()

for I in range(A,B+1):
    if I % K == 0:
        print('OK')
        sys.exit()
print('NG')

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

int main() {
	int N, A, B, ans = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> A >> B;
		ans += B - A + 1;
	}
	cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll a,b;
	cin>>a>>b;
	ll ma=min(a,b);
	ll ans=1;
	for(ll i=2;i<=sqrt(ma);i++){
		if(a%i==0){
			while(a%i==0){
				a/=i;
			}
			if(b%i==0){
			//	cout << i<<endl;
				ans++;
				while(b%i==0){
					b/=i;
				}
			}
		}
		else{
			while(b%i==0){
				b/=i;
			}
		}
	}
	if(a!=1&&b!=1){
	if(a%b==0||b%a==0){
		ans++;
	}
	}
	cout <<ans;
	// your code goes here
	return 0;
}

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

struct init_ { init_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); } } init_;

template<class C> using iodef_rng_t = typename enable_if<decltype(declval<C>().begin(), true_type{})::value && !is_same<C, string>::value>::type;
template<class C, class = iodef_rng_t<C>> istream& operator>>(istream& in, C& c) { for (auto& v : c) { in >> v; } return in; }
template<class C, class = iodef_rng_t<C>> ostream& operator<<(ostream& out, const C& c) { int i = 0; for (const auto& v : c) { if (i++) { out << ' '; } out << v; } return out; }
template<size_t N, class T, class R> using when_last = typename enable_if<N == tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N, class T, class R> using when_init = typename enable_if<N != tuple_size<remove_reference_t<T>>::value - 1, R>::type;
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_last<N, T, istream&> { return in >> get<N>(t); }
template<size_t N = 0, class T> auto operator>>(istream& in, T&& t) -> when_init<N, T, istream&> { return operator>><N + 1>(in >> get<N>(t), forward<T>(t)); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_last<N, T, ostream&> { return out << get<N>(t); }
template<size_t N = 0, class T> auto operator<<(ostream& out, const T& t) -> when_init<N, T, ostream&> { return operator<<<N + 1>(out << get<N>(t) << ' ', t); }

#ifdef LOCAL
template<class T> void trace_(const char* s, const T& v) { cerr << s << "=" << v; }
template<class T, class... Ts> void trace_(const char* s, const T& v, const Ts&... vs) { for (; *s != ','; ++s) { cerr << *s; } cerr << "=" << v << ","; trace_(++s, vs...); }
#define TRACE(...) (cerr << "\033[2m\033[33m", trace_(#__VA_ARGS__, __VA_ARGS__), cerr << "\033[0m\n")
#else
#define TRACE(...)
#endif

template<class Int, class Pred> Int bsearch(Int first, Int last, Pred p) noexcept {
    size_t len = last - first, half;
    Int mid;
    while (len > 0) {
        half = len >> 1;
        mid = first + half;
        if (p(mid)) {
            first = mid + 1;
            len = len - half - 1;
        } else {
            len = half;
        }
    }
    return first;
}

int main() {
    int n;
    int64_t k;
    cin >> n >> k;
    vector<int64_t> a(n);
    cin >> a;
    sort(a.begin(), a.end());
    constexpr int64_t inf = int64_t(1e18) + 1;
    int64_t ans = bsearch(-inf, inf, [&](int64_t x) {
        int64_t lowerx = 0;
        for (size_t i = 0; i < a.size(); i++) {
            if (a[i] >= 0) {
                lowerx += bsearch(0UL, a.size(), [&](size_t j) {
                    return a[i] * a[j] <= x;
                });
            } else {
                lowerx += n - bsearch(0UL, a.size(), [&](size_t j) {
                    return a[i] * a[j] > x;
                });
            }
            if (a[i] * a[i] <= x) lowerx--;
        }
        lowerx /= 2;
        TRACE(x, lowerx);
        return lowerx < k;
    });
    cout << ans << '\n';
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
int main() {
	int n,a[101],ma,mi;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (i == 0) {
			ma = a[i];
			mi = a[i];
		}
		if (a[i] > ma)ma = a[i];
		if (a[i] < mi)mi = a[i];
	}
	cout << abs(ma - mi) << endl;
	getchar();
	getchar();
	return 0;
}

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

int main()
{
	int i;
	long long A[5], N, Min, Ans;
	cin >> N;
	for (i = 0; i < 5; i++)
		cin >> A[i];

	Min = A[0];
	for (i = 0; i < 4; i++) {
		if (Min > A[i + 1])
			Min = A[i + 1];
	}
	if (fmod(N,Min) != 0)
		Ans = N / Min + 5.0;
	else
		Ans = N / Min + 4.0;

	cout << Ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string w;
int main() {
    cin >> w;
    sort(w.begin(), w.end());
    int slen = w.length();
    int counter = 1;
    char pre = w.at(0);
    if(slen == 1) {
        cout << "No" << endl;
        return 0;
    }
    
    for(int i = 1; i < slen; ++i) {
        if(pre == w.at(i)) {
            counter++;
        }else {
            if(counter % 2 != 0) {
                cout << "No" << endl;
                return 0;
            }else {
                pre = w.at(i);
                counter = 1;
            }
        }
    }

    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define rep(i, n) FOR(i, 0, n)
#define repi(i, n) FOR(i, 1, n + 1)
#define pp(v) cout << #v "=" << (v) << endl;
#define ppa(v) cout << "----\n"; rep(i,v.size()) cout << #v << "[" << i << "] = " << v[i] << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)
using namespace std;
using Graph = vector<vector<int>>;

int main() {
  int a,b,k;cin>>a>>b>>k;
  for (int i = a; i <= b; i++) {
    if (i < a + k || b - k < i) cout << i << endl;
  }
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>

using namespace std;
typedef long long LL;
#define pb push_back
const int maxn = 100005;
const int inf = 1<<28;

int ehead[maxn],ecnt;
struct edge {
	int u,v,next;
}edg[maxn*2];
void add(int u,int v) {
	edg[++ecnt]=(edge){u,v,ehead[u]};
	ehead[u]=ecnt;
	edg[++ecnt]=(edge){v,u,ehead[v]};
	ehead[v]=ecnt;
}
int a[maxn],mi[maxn],mx[maxn],n,m,rt,tag=true;
void dfs(int u,int fa,int oe)
{
	if (a[u]!=-1&&((a[u]^oe)&1)) tag=false;
	for (int v,j=ehead[u];j;j=edg[j].next)
		if ((v=edg[j].v)!=fa) dfs(v,u,oe^1);
}
void dp(int u,int fa)
{
	mi[u]=-inf;mx[u]=inf;
	for (int v,j=ehead[u];j;j=edg[j].next)
	if ((v=edg[j].v)!=fa) {
		dp(v,u);
		mi[u]=max(mi[u],mi[v]-1);
		mx[u]=min(mx[u],mx[v]+1);
	}
	if (a[u]!=-1) mi[u]=max(mi[u],a[u]),mx[u]=min(mx[u],a[u]);
	if (mi[u]>mx[u]) tag=false;
}
void mk(int u,int fa,int val)
{
	val=min(val,mx[u]);val=max(val,mi[u]);a[u]=val;
	for (int v,j=ehead[u];j;j=edg[j].next)
		if ((v=edg[j].v)!=fa) mk(v,u,val-1);
}
int main()
{
	#ifdef Amberframe
		freopen("arc063e.in","r",stdin);
		freopen("arc063e.out","w",stdout);
	#endif
	memset(a,-1,sizeof a);
	scanf("%d",&n);
	for (int u,v,i=1;i<n;i++)
		scanf("%d %d",&u,&v),add(u,v);
	scanf("%d",&m);
	for (int u,v,i=1;i<=m;i++)
		scanf("%d %d",&u,&v),a[u]=v,rt=u;
	if (rt) dfs(rt,0,a[rt]&1);else rt=1;dp(rt,0);
	if (mi[rt]<=mx[rt]&&tag) {
		puts("Yes");mk(rt,0,a[rt]!=-1?a[rt]:0);
		for (int i=1;i<=n;i++) printf("%d\n",a[i]);
	}
	else puts("No");
	return 0;
}

Measured memory_bytes: 9472
N, X, Y = map(int, input().split())

m = {i:[] for i in range(1, N+1)}
for i in range(1, N+1):
    if i > 1:
        m[i].append(i-1)
    if i < N:
        m[i].append(i+1)
m[X].append(Y)
m[Y].append(X)

# print(m)

from collections import deque

dists = [[]]
for i in range(1, N+1):
    dist = [float('inf')]*(N+1)
    dist[i] = 0
    q = deque([i])
    while q:
        p = q.popleft()
        for j in m[p]:
            if dist[j] > dist[p]+1:
                dist[j] = dist[p]+1
                q.append(j)
    dists.append(dist)

# print(dists)

ansm = {i:0 for i in range(1, N+1)}
for i in range(1, N+1):
    for j in range(1, N+1):
        if dists[i][j] == 0:
            continue
        ansm[dists[i][j]] += 1

for i in range(1, N):
    print(ansm[i]//2)


Measured memory_bytes: 130524
import java.io.*;
import java.util.*;
 
public class  Main{
	static int gcd(int a,int b) {
		if(b==0)return a;
		return gcd(b,a%b);
	}
	public static void main(String[] args) throws Exception{
		MScanner sc=new MScanner(System.in);
		PrintWriter pw=new PrintWriter(System.out);
		int a=sc.nextInt(),b=sc.nextInt();
		pw.println((a*1l*b)/(gcd(a,b)));
		pw.flush();
	}
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] takearr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] takearrl(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public Integer[] takearrobj(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] takearrlobj(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}

Measured memory_bytes: 21588
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	string s;
	cin >> s;
	vector<vector<ll>> acm(n, vector<ll>(n, 0));
	vector<vector<ll>> dp(n, vector<ll>(n, 0));
	REP(i, n) dp[0][i] = 1;
	acm[0][0] = dp[0][0];
	FOR(i, 1, n) acm[0][i] = acm[0][i - 1] + dp[0][i];
	FOR(i, 1, n) {
		REP(j, n - i) {
			if(s[i - 1] == '<') {
				dp[i][j] = acm[i - 1][j];
			} else {
				dp[i][j] = acm[i - 1][n - 1] - acm[i - 1][j];
			}
		}
		acm[i][0] = dp[i][0];
		FOR(j, 1, n) {
			acm[i][j] = acm[i][j - 1] + dp[i][j];
			acm[i][j] %= MOD;
		}
	}
	cout << (dp[n - 1][0] % MOD + MOD) % MOD << endl;
	return 0;
}

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


Measured memory_bytes: 141184
n, k = map(int, input().split())
p = list(map(int, input().split()))
i = k
total = maximum = sum(p[0:k])
i = k
while i < n:
    total = total-p[i-k]+p[i]
    maximum = max(maximum, total)
    i += 1
print((maximum+k)/2)


Measured memory_bytes: 71792
#include <cmath>
#include <iostream>

bool is_prime(int x) {
  if (x < 2) return false;
  for (int i = 2; i <= static_cast<int>(std::sqrt(x)); i++) {
    if (x % i == 0) return false;
  }
  return true;
}

int main() {
  int x;
  std::cin >> x;
  do {
    if (is_prime(x)) {
      std::cout << x << std::endl;
      break;
    }
  } while (x++);
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func water(n int, i int, hArray []int, fArray []int) {
	for j := i; j < n; j++ {
		if fArray[j] < hArray[j] {
			fArray[j]++
		} else {
			break
		}
	}
}

func main() {
	var n int
	fmt.Scan(&n)

	hArray, fArray := make([]int, n), make([]int, n)
	for i := range hArray {
		fmt.Scan(&hArray[i])
		fArray[i] = 0
	}

	cnt := 0
	for i := range hArray {
		for fArray[i] < hArray[i] {
			water(n, i, hArray, fArray)
			cnt++
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 512
#include<iostream>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
using namespace std;
using ll=long long;

#include<vector>
#include<algorithm>
#include<map>
namespace ProconLib{
    template<typename T>
    std::map<T,int> Compress(std::vector<T> v){
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        std::map<T,int> res;
        int id=0;
        for(auto &x:v){
            res[x]=id++;
        }
        return res;
    }
}
#include<vector>
namespace ProconLib{

    //Summation only
    template<typename Int>
    struct BIT{     
        private:
        int N;
        std::vector<Int> dat;
        public:
        BIT(int N):N(N),dat(N,0){}
        void add(int pos,Int x);
        Int query(int r);
        Int query(int l,int r);
    };

    template<typename Int>
    void BIT<Int>::add(int pos,Int x){
        pos++;
        while(pos<=N){
            dat[pos-1]+=x;
            pos+=pos&-pos;
        }
    }

    template<typename Int>
    Int BIT<Int>::query(int r){
        Int res=0;
        while(r>0){
            res+=dat[r-1];
            r-=r&-r;
        }
        return res;
    }

    template<typename Int>
    Int BIT<Int>::query(int l,int r){
        return query(r)-query(l);
    }
  
};
using namespace ProconLib;

const ll MOD=998244353;
struct P{
    int id;
    int x,y;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<int> x(n),y(n);
    for(int i=0;i<n;i++) cin>>x[i]>>y[i];
    auto mpX=Compress(x);
    auto mpY=Compress(y);
    vector<P> ps(n);
    for(int i=0;i<n;i++){
        ps[i].id=i;
        ps[i].x=mpX[x[i]];
        ps[i].y=mpY[y[i]];
    }

    
    vector<vector<int>> a(n,vector<int>(4));
    {
        BIT<ll> lefb(n),rigb(n);
        sort(ps.begin(),ps.end(),[](P lhs,P rhs){return lhs.x<rhs.x;});
        for(int i=0;i<ps.size();i++) rigb.add(ps[i].y,1);
        for(int i=0;i<ps.size();i++){
            a[ps[i].id][0]=rigb.query(ps[i].y+1,n);
            a[ps[i].id][1]=lefb.query(ps[i].y+1,n);
            a[ps[i].id][2]=lefb.query(0,ps[i].y);
            a[ps[i].id][3]=rigb.query(0,ps[i].y);
            lefb.add(ps[i].y,1);
            rigb.add(ps[i].y,-1);
        }
    }
    vector<ll> pow2(n+1);
    pow2[0]=1;
    for(int i=0;i+1<pow2.size();i++){
        pow2[i+1]=pow2[i]*2%MOD;
    }
    ll res=n*(pow2[n]-1)%MOD;
    for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
            res-=(pow2[a[i][j]+a[i][(j+1)%4]]-pow2[a[i][j]]);
        }
        res%=MOD;
    }
    res=(res+MOD)%MOD;
    cout<<res<<endl;


    return 0;
}


Measured memory_bytes: 36976
#include<stdio.h>
#include<stdlib.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
int main(void)
{
  int i=0,N=IN(),r=0,w=0;char *stones=(char*)malloc(sizeof(char)*(N+1));stones[N]=0;
  if(stones==NULL){exit(EXIT_FAILURE);}if(!scanf("%s",stones)){exit(EXIT_FAILURE);}
  while(N--){if(stones[N]=='R')r++;}while(r--){if(stones[i++]=='W')w++;}
  printf("%d\n",w);return free(stones),0;
}

Measured memory_bytes: 1780
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
#include<map>
#include<type_traits>
#include<tuple>
#include<deque>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,N) for(ll (i)=0;(i)<(N);(i)++)
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
const int mod = 1000000007;
const ll INF = ll(1e18) + 1;

const int MAXN = 100005;
vector<int> to[MAXN];

void dfs(int v, int d, vector<int> &dist) {
  dist[v] = d;
  for (int u : to[v]) {
    if(dist[u] != -1) continue;
    dfs(u, d + 1, dist);
  }
}

int main() {
  int n;
  cin >> n;
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  vector<int> snuke(n, -1), fennec(n, -1);
  dfs(0, 0, fennec);
  dfs(n - 1, 0, snuke);
  int fp = 0;
  int sp = 0;

  rep(i, n) {
    if(fennec[i] > snuke[i]) sp++;
    else fp++;
  }
  
  cout << (sp >= fp ? "Snuke" : "Fennec") << endl;

}

Measured memory_bytes: 11136
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, K;
	cin >> n >> K;

	vector<int> h(n);
	for (int i = 0; i < n; ++i)
		cin >> h[i];

	sort(h.begin(),h.end());

	int ans = h[K-1] - h[0];
	for (int i = K; i < n; ++i)
		ans = min(ans, h[i] - h[i-K+1]);

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

Measured memory_bytes: 640
package main

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

// Refarence:
// - https://atcoder.jp/contests/abc155/submissions/10158108
// - https://atcoder.jp/contests/abc155/submissions/10150710
// - https://www.youtube.com/watch?v=SG60Cp9pSog&t=3175s
func solution(n, k int, nums []int) int64 {
	var l, r int64 = -1 << 63, 1<<63 - 1
	sort.Ints(nums)
	for l+1 < r {
		x := (l + r) >> 1
		var tot int64 = 0
		for i := 0; i < n; i++ {
			if nums[i] < 0 {
				l, r := -1, n
				for l+1 < r {
					c := (l + r) >> 1
					if int64(nums[c])*int64(nums[i]) < x {
						r = c
					} else {
						l = c
					}
				}
				tot += int64(n) - int64(r)
			} else {
				l, r := -1, n
				for l+1 < r {
					c := (l + r) >> 1
					if int64(nums[c])*int64(nums[i]) < x {
						l = c
					} else {
						r = c
					}
				}
				tot += int64(r)
			}
			if int64(nums[i])*int64(nums[i]) < x {
				tot--
			}
		}
		tot /= 2
		if tot < int64(k) {
			l = x
		} else {
			r = x
		}
	}
	return l
}

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	reader := bufio.NewReaderSize(os.Stdin, 2*1e6)
	str, _, _ := reader.ReadLine()
	nums := make([]int, n)
	for i, s := range strings.Split(string(str), " ") {
		nums[i], _ = strconv.Atoi(s)
	}

	fmt.Println(solution(n, k, nums))
}


Measured memory_bytes: 9344
// Header {{{
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
typedef unsigned long long int ull;
typedef long long int ll;
#define rep(i,a,b) for (ll i=(a); i<(b); i++)
typedef pair<ll,ll> PLL;
// }}}
signed main() {
    set<string> ans;
    string s,t;
    cin>>s>>t;
    rep(i,0,s.size()-t.size()+1){
        bool ok = true;
        string q = s;
        rep(j,0,t.size()){
            if (t[j]!=s[i+j] && s[i+j]!='?'){
                ok=false;
                break;
            }
            q[i+j] = t[j];
        }
        if (!ok)
           continue;

        for(auto &c: q)
            if(c=='?')
                c='a';
        ans.insert(q);
    }
    if (ans.size()==0){
        cout<<"UNRESTORABLE"<<endl;
        return 0;
    }
    cout<<*ans.begin()<<endl;
    return 0;
}


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

using namespace std;

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

Measured memory_bytes: 3916
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  for(int i=0; i<n-2; i++){
    if(s.substr(i,3)=="ABC") ans++;
  }
  cout << ans << endl;
}

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

int main(){
	int n, k;
	cin >> n >> k;
  
  map<int, int> children;
  rep(i, k){
    int d;
    cin >> d;
    rep(j ,d){
      int a;
      cin >> a;
    if(!children.count(a)){children[a] = k;}
    }
  }
   
  cout << n - children.size() << endl; 
    return 0;
  }

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

using namespace std;

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

    int a,b,h;
    cin>>a>>b>>h;

    cout<<(a+b)*(h/2)<<"\n";


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

#define FREE -1
#define NOT_FREE 1
#define TRUE 1
#define FALSE 0
#define N 8

int row[8];
int col[8];
int dpos[2 * N - 1];
int dneg[2 * N - 1];

int Board[N][N];

void putQueen(int);
void printBoard();

int main(){
        int i, j, k, r, c;

        for(i = 0 ; i < N ; i++){
                row[i] = FREE;
                col[i] = FREE;
        }
        for(i = 0; i < 2*N - 1 ; i++){
                dpos[i] = FREE;
                dneg[i] = FREE;
        }
        for(i=0; i < N; i++)for(j = 0 ; j < N ;j++)Board[i][j] = FALSE;

        scanf("%d", &k);
        for(i = j = 0 ; i < k ; i++){
                scanf("%d %d", &r, &c);
                Board[r][c] = TRUE;
        }
        
        putQueen(0);

        return 0;
}

void putQueen(int x){
        int y, i, j;
        if(x == N){
                printBoard();
                return;
        }

        for(y = 0 ; y < N ; y++){
                        if(col[y] == NOT_FREE || dpos[x + y] == NOT_FREE || dneg[x - y + N - 1] == NOT_FREE)continue;
                        row[x] = y;
                        col[y] = dpos[x+y] = dneg[x - y + N-1] = NOT_FREE;
                        putQueen(x+1);
                        row[x] = col[y] = dpos[x+y] = dneg[x - y + N-1] = FREE; 
        }
}

void printBoard(){
        int i, j;
        for(i = 0 ; i < N ; i++){
                for(j = 0 ; j < N ; j++){
                        if(Board[i][j])if(row[i] != j)return;
                }
        }
        for(i = 0 ; i < N ; i++){
                for(j = 0 ; j < N ; j++){
                        if(row[i] == j)printf("Q");
                        else printf(".");
                }
                printf("\n");
        }
}



Measured memory_bytes: 2112
#include <iostream>
#include <stdlib.h>
using namespace std;

int main()
{
    long long a,b,cpy,i;
    std::cin>> a >> b;
    cpy = b;
    if(a%b==0)
        std::cout<<0;
    else
    {
        if(a>b)
        {
            i= a/b;
            b = b*i;
            a=a-b;
            if(abs(a-cpy)<a)
                a=abs(a-cpy);
        }
        else
            if(abs(a-cpy)<a)
                a=abs(a-cpy);
        std::cout<<a;
    }


}


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

int n, q,s[100000], t,  c=0;

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

    scanf("%d",&q);
    for(int i=0 ; i<q ; i++){
        scanf("%d",&t);
        for(int j=0 ; j<n ; j++){
            if(t == s[j]){
                c++;
                break;
            }
        }
    }

    printf("%d\n", c);

    return 0;
}


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

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

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

int main()
{
	int n, k;
  	cin >> n >> k;
  	for (int i = 0; i < k; i++)
    {
    	int a;
      	cin >> a;
      	n -= a;
    }
  	if (n < 0)
      cout << -1;
  	else
      cout << n;
  	return 0;
}

Measured memory_bytes: 3152
n = int(input())
lst = []
for i in range(n):
    lst.append(input().split())

for i in lst:
    i[-1] = int(i[-1])

s = sorted(lst, key=lambda x:(x[0], -x[1]))
ans = []

for i in s:
    for ind, j in enumerate(lst):
        if i == j:
            ans.append(ind+1)
        else:
            continue

for i in ans:
    print(i)

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

int main() {
  int FX = 0;
  int N,M;
  cin >> N;
  M = N;
  for (int i = 0; i < 8; i++){
    FX += M % 10;
    M /= 10;
  
  if (M < 1) break;
  }  
  if (N % FX == 0) cout << "Yes" << endl;
  
  else cout << "No" <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;
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;}

int main(){
  ll a, b, M; cin >> a >> b >> M;
  vector<ll> A(a); rep(i,a) cin >> A[i];
  vector<ll> B(b); rep(i,b) cin >> B[i];
  vector<pair<pair<ll,ll>,ll>> XYC(M);
  rep(i,M) cin >> XYC[i].first.first >> XYC[i].first.second >> XYC[i].second;
  ll ans = 1e9;
  rep(i,M){
    int ida = XYC[i].first.first-1;
    int idb = XYC[i].first.second-1;
    ans = min(ans, A[ida]+B[idb]-XYC[i].second);
  }
  ll mina = 1e9;
  ll minb = 1e9;
  rep(i,a){
    mina = min(mina, A[i]);
  }
  rep(i,b){
    minb = min(minb, B[i]);
  }
  ans = min(ans, mina+minb);
  cout << ans << endl;

  return 0;
}


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

int main() {
	string s, res;

	while (cin >> s) {
		res = "";
		int i = 0;
		while (i < s.size()) {
			if (s[i] == '@') {
				for (int j = 0; j < s[i + 1] - '1'; j++) {
					res += s[i + 2];
				}
				i += 2;
				continue;
			} else {
				res += s[i];
			}
			i++;
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 3184
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
constexpr ll mod=1000000007;
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
ll n,m;
struct edge{
    ll to,cost;
};
V<edge> graph[100005];
V<ll> dist;
void dfs1(int now,int par){
    for(edge &e:graph[now]){
        if(e.to==par)continue;
        dfs1(e.to,now);
        chmax(dist[now],dist[e.to]+e.cost);
    }
}
ll dfs2(int now,int d_par,int par){
    V<P> dc;
    dc.emplace_back(0,-1);
    for(edge &e:graph[now]){
        if(e.to==par)dc.emplace_back(d_par+e.cost,e.to);
        else dc.emplace_back(e.cost+dist[e.to],e.to);
    }
    sort(all(dc),greater<P>());
    ll res=dc[0].fi+dc[1].fi;
    for(edge &e:graph[now]){
        if(e.to==par)continue;
        chmax(res,dfs2(e.to,dc[dc[0].se==e.to].fi,now));
    }
    return res;
}
int main(){
    cin>>n;
    dist.assign(n,0);
    for(int i=0;i<n-1;i++){
        ll a,b,w;cin>>a>>b>>w;
        graph[a].emplace_back(edge{b,w});
        graph[b].emplace_back(edge{a,w});
    }
    dfs1(n/2,-1);
    cout<<dfs2(n/2,0,-1)<<"\n";
}



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

typedef long long ll;

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N),B(N);
    for(ll i=0; i<N; i++){
        cin >> A[i];
        B[i] = A[i];
    }
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    reverse(B.begin(),B.end());
    
    list<ll> lst1;
    bool flag1=true; ll a1=1,b1=0;
    for(ll i=0; i<N;){
        if(i==0){
            lst1.push_back(A[0]);
            i++;
        }
        else {
            if(flag1){
                lst1.push_front(B[b1++]);
                lst1.push_back(B[b1++]);
                i+=2;
                flag1=false;
            }
            else {
                lst1.push_front(A[a1++]);
                lst1.push_back(A[a1++]);
                i+=2;
                flag1=true;
            }
        }
    }
    ll ans1=0, x,y; ll cnt1=0;
    for(auto itr=lst1.begin(); itr!=lst1.end(); itr++,cnt1++){
        if(cnt1==N-1) break;
        x = *itr; y = *std::next(itr,1);
        ans1 += abs(x-y);
    }
    
    list<ll> lst2;
    bool flag2=true; ll a2=0,b2=1;
    for(ll i=0; i<N;){
        if(i==0){
            lst2.push_back(B[0]);
            i++;
        }
        else {
            if(!flag2){
                lst2.push_front(B[b2++]);
                lst2.push_back(B[b2++]);
                i+=2;
                flag2=true;
            }
            else {
                lst2.push_front(A[a2++]);
                lst2.push_back(A[a2++]);
                i+=2;
                flag2=false;
            }
        }
    }
    ll ans2=0; ll cnt2=0;
    for(auto itr=lst2.begin(); itr!=lst2.end(); itr++,cnt2++){
        if(cnt2==N-1) break;
        x = *itr; y = *std::next(itr,1);
        ans2 += abs(x-y);
    }
    
    cout << max(ans1,ans2) << endl;
}


Measured memory_bytes: 8064
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.next());
    int M = Integer.parseInt(sc.next());
    Map<Integer, ArrayList<Integer>> map = new TreeMap<Integer, ArrayList<Integer>>();
    for (int i = 0; i < M; i++) {
      int P = Integer.parseInt(sc.next());
      int Y = Integer.parseInt(sc.next());
      map.put(Y, new ArrayList<Integer>(Arrays.asList(P, i)));
    }
    String[] ans = new String[M];
    int[] cnt = new int[N + 1];
    for (List<Integer> i : map.values()) {
      ans[i.get(1)] = String.format("%06d%06d", i.get(0), ++cnt[i.get(0)]);
    }
    for (int i = 0; i < M; i++) {
      System.out.println(ans[i]);
    }
  }

}


Measured memory_bytes: 120532
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<map>
#include<functional>
#include<set>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
#define PB(a,num) FOR(i,0,num) {ll x; scanf("%lld",&x); a.pb(x); }
#define LOWER(a,x) lower_bound(ALL(a), x) - a.begin() - 1;
#define COUNT(a,x)  upper_bound(ALL(a), x) - lower_bound(ALL(a), x);
#define MCOUNT(a,x,y) upper_bound(ALL(a), y) - lower_bound(ALL(a), x);
#define INF 111111111111111111
#define MOD 1000000007
#define pb push_back
#define F first
#define S second
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef set<ll> SET;
typedef map<ll, ll> MAP;
ll n = 0, m = 0, ans = 0, sum = 0, cnt = 0, tmp = 0, ma = 0, mi = 0;
string s;
bool flag, ok;
ll dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
ll ddx[8] = { 1,-1,0,0,1,1,-1,-1 }, ddy[8] = { 0,0,1,-1,1,-1,1,-1 };
#pragma endregion
#define MAX 111111



int main(void) {
  SET st;
  MAP mp;
  ll a, b;
  cin >> n >> m;
  FOR(i, 0, m) {
	cin >> a >> b;
	if (a == 1) {
	  st.insert(b);
	}
	else if (b == 1) {
	  st.insert(a);
	}
	if (a == n) {
	  mp[b]++;
	}
	else if (b == n) {
	  mp[a]++;
	}
  }

  ok = false;
  for (auto it : st) {
	if (mp[it]) ok = true;
  }

  if (ok) {
	cout << "POSSIBLE" << endl;
  }
  else {
	cout << "IMPOSSIBLE" << endl;
  }

  return 0;
}

Measured memory_bytes: 17408
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,f,s[14][8],t,h,ans;
int main(){
    scanf("%d%d",&n,&f);
    for(int i=1;i<=11;i++)
        for(int j=1;j<=7;j++){
            t++;
            s[i][j]=t;
        }
    for(int i=1;i<=11;i++)
        for(int j=1;j<=7-3+1;j++){
            t=0;
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
                    t+=s[(i+k-1)%11+1][j+l];
            if(t%11==f)h++;
        }
    ans+=max(0,(n/11-1))*h;
    if(n/11>0)n-=(n/11-1)*11;
    for(int i=1;i<=n-3+1;i++)
        for(int j=1;j<=7-3+1;j++){
            t=0;
            for(int k=0;k<3;k++)
                for(int l=0;l<3;l++)
                    t+=s[(i+k-1)%11+1][j+l];
            if(t%11==f)ans++;
        }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<double>;
using vs = vector<string>;
using vb = vector<bool>;
using vp = vector<P>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvb = vector<vb>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll  INFL = 1e18;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int N; cin >> N;
    vd p(N); REP(i, N) cin >> p[i];
    vector<vd> dp(N+1, vd(N+1)); dp[0][0] = 1.0;
    REP(i, N)
    {
        for(int j = 0; j <= i; j++)
        {
            dp[i+1][j+1] += dp[i][j]*p[i];
            dp[i+1][j] += dp[i][j]*(1.0-p[i]);
        }
    }
    
    double ans = 0.0;
    for(int i = (N+1)/2; i <= N; i++)
    {
        ans += dp[N][i];
    }
    cout << ans << endl;
}

Measured memory_bytes: 70784