akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;

#define REP(i,n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> pint;

int main() {
  priority_queue<int, vector<int> > q;
  int a;
  REP(i,3) {
    cin>>a;
    q.push(a);
  }
  int K; cin>>K;
  int sum = 0;
  while(--K >= 0) {
    a = q.top();
    q.pop();
    a *= 2;
    q.push(a);
  }
  while(!q.empty()) {
    sum += q.top();
    q.pop();
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 256
n,k = map(int, input().split())
count0 = 0
count1 = 0
for i in range(1,n+1):
    if i%k==0:
        count0 +=1
    if i%k==k/2:
        count1 +=1

if k%2==0:
    print(count0**3+count1**3)
else:
    print(count0**3)

Measured memory_bytes: 3060
#include<stdio.h>

int main(void)
{
	int r[101], a[101][101] = { 0 };
	int i, j, k, l, m, n, cmin = 0;

	scanf("%d", &n);

	for (i = 1;i <= n;i++) {
		scanf("%d %d", &r[i], &r[i + 1]);
	}
	
	for (i = 1;i <= n;i++) {
		a[i][i] = 0;
	}
	for (l = 1;l <= n; l++) {
		for (i = 1;i <= n - l;i++) {
			j = l + i;
			cmin = a[i][i] + a[i + 1][j] + r[i] * r[i + 1] * r[j + 1];
			for (k = i;k < j;k++) {
				if (a[i][k] + a[k + 1][j] + r[i] * r[k + 1] * r[j + 1] < cmin) {
					cmin = a[i][k] + a[k + 1][j] + r[i] * r[k + 1] * r[j + 1];
				}
			}
			a[i][j] = cmin;
		}
	}
	
	printf("%d\n", a[1][n]);

	return 0;
}
 



Measured memory_bytes: 2100
N = gets.to_i
A = gets.split.map(&:to_i).sort.insert(0, 0).push(9_000_000_000)
B = gets.split.map(&:to_i).sort
C = gets.split.map(&:to_i).sort.insert(0, 0).push(9_000_000_000)

ans = 0
B.each do |b|
  a = A.bsearch_index {|x| x >= b}
  next if a == 1
  c = C.bsearch_index {|x| x > b }
  next if c > N
  ans += (a - 1) * (N + 1 - c)
end

puts ans


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

int main() {
  int n;
  cin >> n;

  vector<int> moti(n);

  for(int i=0; i<n; i++) {
    cin >> moti.at(i);
  }

  for(int i=0; i<n; i++) {
    
    int z = moti.at(i);
    
    for(int j=i+1; j<n; j++){
      
       if( z < moti.at(j) ) {
         int c = z;
         z = moti.at(j);
         moti.at(j) = c;
       }
      
    }
    
    moti.at(i) = z;
    
  }
  
  int x=1;
  int a = moti.at(0);
  for (int i=1; i<n; i++){
    if( a > moti.at(i) ) {
        x++;
        a = moti.at(i);
    }
  }
  cout << x << endl; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long int N, A, B, C, D, E;
  cin >> N >> A >> B >> C >> D >> E;
  long long int a;
  a = min(A, min(B, min(C, min(D, E))));
  long long int ans = (N-1) / a + 5;
  cout << ans << endl;
  return 0;
}

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

using namespace std;

struct UnionFind {
  vector<int> data;
  UnionFind(int sz)
  {
    data.resize(sz, -1);
  }
  int find(int x)
  {
    if(data[x] < 0) return x;
    return data[x] = find(data[x]);
  }
  int unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x == y) return -1;
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return -data[x];
  }
};

struct edge {
  int u, v, w;
  edge(){}
  edge(int u, int v, int w):u(u), v(v), w(w){}
  bool operator < (const edge& e) const {
    return w < e.w;
  }
};

vector<edge> es;
int N, M;

const int inf = 1 << 25;

int kruskal(int idx)
{
  UnionFind uf(N);
  for(int i = idx; i < es.size(); i++) {
    edge& e = es[i];
    if(uf.unite(e.u, e.v) == N) {
      return e.w - es[idx].w;
    }
  }
  return inf;
}

int main()
{
  while(cin >> N >> M, N) {
    es.clear();
    for(int i = 0; i < M; i++) {
      int a, b, w;
      cin >> a >> b >> w; --a, --b;
      es.push_back(edge(a, b, w));
    }
    sort(es.begin(), es.end());
    int ans = inf;
    for(int i = 0; i <= M-N+1; i++) {
      ans = min(ans, kruskal(i));
    }
    if(ans == inf) cout << -1 << endl;
    else cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3220
n = STDIN.gets.chomp.to_i

prime = []
# ルート 100000まででOK
max =  Math.sqrt(100000).round
[*(2..100003)].each do |x|
  p_flg = true
  prime.each do |y|
    if x % y == 0
      p_flg = false
    end
    if y >= max
      break
    end
  end
  if p_flg
    if x >= n
      puts x
      break
    end
    prime.push(x)
  end
end


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/10/23  Problem: ABC 088 A / Link: http://abc088.contest.atcoder.jp/tasks/abc088_a  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL ans = 0LL;

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

	int N, A; cin >> N >> A;
	N %= 500;
	if (N <= A) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long int ll;
#define rep(i,n) for (int i = 0; i< (n); i++)
#define Rep(i,n,m) for (int i = (n); i< (m); i++)
#define Sort(a) sort(a.begin(), a.end())
#define Reverse(a) reverse(a.begin(), a.end())
const int INF = 1e9;
const ll MOD = 1000000007;
const ll LINF = 1e18;
using namespace std;



int main() {
    int n,k,count=0;
    
    
    cin>>n>>k;
    vector<int> d(k);
    vector<bool> b(n, false);
    vector<vector<int>> a(k, vector<int>(n, 0));
    for(int i = 0; i<k; i++){
        cin>>d[i];
      for(int j = 0; j<d[i]; j++){
         cin>>a[i][j];
      }
    }
    
    rep(i,k){
        rep(j, d[i]){
            b[a[i][j]-1] = true;
        }
    }
    
    rep(i,n){
        if(b[i]==false) count++;
    }
    
    cout<<count<<endl;
    
    return 0;
}


Measured memory_bytes: 3620
import java.util.*;

public class Main{
	
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	int x=sc.nextInt(),a=sc.nextInt(),b=sc.nextInt();
    if(b-a<=0){
      System.out.println("delicious");
    }else if(b-a<=x){
      System.out.println("safe");
    }else{
      System.out.println("dangerous");
    }
  }
}


Measured memory_bytes: 20948
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>

using namespace std;

void b_christmas_eve_eve(void) {
	int n;
	int* p;
	cin >> n;
	p = (int*)calloc(n, sizeof(int));
	for (int i = 0; i < n; i++) cin >> p[i];

	sort(p, p + n, std::greater<int>());
	p[0] /= 2;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum += p[i];
	}
	cout << sum << endl;
}
int main()
{
    b_christmas_eve_eve();

    return 0;
}


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

using namespace std;

typedef long long llint;

int main() {
  llint b;
  while (cin >> b, b) {
    llint f = 0, ans = 0;
    for (llint i = 1; i * i < 2 * b; i++) {
      if (2 * b % i) continue;
      llint a = (2 * b / i - i + 1) / 2;
      if (2 * b != i * (i + 2 * a - 1)) continue;
      if (a > 0) {
        if (ans < i) {
          f = a;
          ans = i;
        }
      }
    }
    cout << f << " " << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 3116
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<bitset>
#include <sstream>
#include<queue>
#include<stack>
#include<iomanip>
#include<functional>
#define rep(i,n) for(ll i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod =1e9+7;

int main()
{
    int n,a,b;
    cin>>n>>a>>b;
    string s;
    cin>>s;
    vector<string> ans(n);
    int pass=0;
    int foreignerpass=0;
    rep(i,n)
    {
        if(s[i]=='a')
        {
            if(pass<a+b)
            {
                ans[i]="Yes";
                pass++;
            }
            else
            {
                ans[i]="No";
            }
            

        }
        else if(s[i]=='b')
        {
            if(pass<a+b && foreignerpass<b)
            {
                ans[i]="Yes";
                pass++;
                foreignerpass++;
            }
            else
            {
                ans[i]="No";
            }
            

        }
        else
        {
            ans[i]="No";
        }

        

    }
    rep(i,n)
    {
        cout<<ans[i]<<endl;
    }
}

Measured memory_bytes: 6144
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = INT_MAX;
const ll linf = 3e18;
const double eps = 1e-9;

struct SegTree { // ??????min,max
    int n;
    vector<int> Max;
    vector<int> Min;
    void init(int n_) {
        n = 1;
        while (n < n_) n *= 2;
        Max.resize(2 * n);
        Min.resize(2 * n);
        for (int i = 0; i < 2 * n - 1; ++i) {
            Max[i] = -inf;
            Min[i] = inf;
        }
    }
    void update(int idx, int val) {
        idx += n - 1;
        Min[idx] = val;
        Max[idx] = val;
        while (idx > 0) {
            idx = (idx - 1) / 2;
            Min[idx] = min(Min[idx * 2 + 1], Min[idx * 2 + 2]);
            Max[idx] = max(Max[idx * 2 + 1], Max[idx * 2 + 2]);
        }
    }
    int get_min(int a, int b, int k = 0, int l = 0, int r = -1) { // [a, b)???min
        if (r == -1) r = n;
        if (r <= a || b <= l) return inf;
        if (a <= l && r <= b) return Min[k];
        int vl = get_min(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = get_min(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
    int get_max(int a, int b, int k = 0, int l = 0, int r = -1) { // [a, b)???max
        if (r == -1) r = n;
        if (r <= a || b <= l) return -inf;
        if (a <= l && r <= b) return Max[k];
        int vl = get_max(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = get_max(a, b, k * 2 + 2, (l + r) / 2, r);
        return max(vl, vr);
    }
};

signed main()
{
    int n, q; cin >> n >> q;

    SegTree seg;

    seg.init(n);

    rep(i, q) {
        int type, x, y;
        cin >> type >> x >> y;

        if (type % 2 == 0) {
            seg.update(x, y);
        } else {
            cout << seg.get_min(x, y + 1) << endl;
        }
    }
}

Measured memory_bytes: 3116
//ABC161 C

#include <bits/stdc++.h>
using namespace std;

long double N,K;
long long ans = 0;

int main() {
  cin >> N >> K;
  
  if(N>=K*1000000000){
    N -= floor(N/K)*K;
  }
  
  while(N > abs(N-K)){
    N = abs(N-K);
  }
  
  printf("%.0Lf\n",N);
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/abc122/submissions/9716257

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let t: Vec<char> = s.trim().chars().collect();
    // splitの区切り字を複数文字にできるのか
    let ans = t
        //"ACGT"は&str, cはcharなのでstrに変える必要がある
        .split(|c| !"ACGT".contains(&c.to_string()))
        .map(|x| x.len())
        .max()
        .unwrap();
    println!("{}", ans);
}

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

typedef double Real;

Real EPS = 1e-8;
const Real PI = acos(-1);

int sgn(Real a, Real b=0){return a<b-EPS?-1:a>b+EPS?1:0;}
Real sqr(Real a){return sqrt(max(a,(Real)0));}

struct Point{  
  Real add(Real a, Real b){
    if(abs(a+b) < EPS*(abs(a)+abs(b)))return 0;
    return a+b;
  }

  Real x, y;
  Point(){}
  Point(Real x,Real y) : x(x) , y(y){}

  Point operator + (Point p){return Point(add(x,p.x), add(y,p.y));}
  Point operator - (Point p){return Point(add(x,-p.x), add(y,-p.y));}
  Point operator * (Real d){return Point(x*d,y*d);}
  Point operator / (Real d){return Point(x/d,y/d);}
  bool operator == (Point p){return !sgn(dist(p));}
  //昇順
  bool operator < (Point p)const{return (p.x!=x)?x<p.x:y<p.y;}
  Real norm(){return sqr(x*x+y*y);}
  Real dist(Point a){return (*this-a).norm();}
  Real dot(Point a){return x*a.x+y*a.y;}
  Real cross(Point a){return x*a.y-y*a.x;}
};

struct Circle{
  Point p;
  Real r;
  Circle(){}
  Circle(Point p, Real r) : p(p) , r(r){}
  
  bool contain(Point a){
    return sgn((a-p).norm(),r)<=0;
  }
  
  Circle circumCircle(Point a,Point b){
    Point q=(a+b)/2;
    return Circle(q,(a-q).norm());
  }
  
  Circle circumscribedCircle(Point p, Point q, Point r){
    Point a=(q-p)*2,b=(r-p)*2;
    Point c(p.dot(p)-q.dot(q),p.dot(p)-r.dot(r));
    Circle res;
    res.p.x=a.y*c.y-b.y*c.x;
    res.p.y=b.x*c.x-a.x*c.y;
    res.p=res.p/a.cross(b);
    return Circle(res.p, p.dist(res.p));
  }

  Circle minEnclosingCircle(vector<Point>ps){
    if(ps.size()==0)return Circle(Point(0,0),0);
    if(ps.size()==1)return Circle(ps[0],0);

    Circle circle=circumCircle(ps[0],ps[1]);
    for(int i=2;i<ps.size();i++){
      if(!circle.contain(ps[i])){
	circle=circumCircle(ps[0],ps[i]);
	for(int j=1;j<i;j++){
	  if(!circle.contain(ps[j])){
	    circle=circumCircle(ps[j],ps[i]);
	    for(int k=0;k<j;k++){
	      if(!circle.contain(ps[k])){
		circle=circumscribedCircle(ps[i],ps[j],ps[k]);
	      }
	    }
	  }
	}
      }
    }
    return circle;
  }

};

int main(void){

  int n;
  cin >> n;
  vector<Point>ps(n);

  for(int i=0;i<n;i++)cin >> ps[i].x >> ps[i].y;
  Circle c;
  cout << setprecision(15) << c.minEnclosingCircle(ps).r << endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
	int a[4],b[4];
	int i,l;
	int ans[2]={0};	//hit blou
	while(scanf("%d",a)!=EOF){
		for(i=1;i<4;i++)
			scanf("%d",&a[i]);
			
		for(i=0;i<4;i++){
			scanf("%d",&b[i]);
			for(l=0; l<4; l++){
				if(a[l]==b[i])
					ans[1]++;
			}
			if(a[i]==b[i]){
			ans[1]--;
			ans[0]++;
			}
		}
		
		printf("%d %d\n",ans[0],ans[1]);
		ans[0]=0;
		ans[1]=0;
	}
	return 0;
}

Measured memory_bytes: 1024
#define LOCAL

#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <functional>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <iomanip>

using namespace std;

// From Errichto's Youtube stream
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using int64 = long long;

/////////////////////
// Code starts here//
/////////////////////

void df (int x, const vector<vector<int>> &g, vector<int> & col, int cur) {
    if (col[x] != -1)
        return;
    col[x] = cur;
    for (auto v : g[x]) {
        df(v, g, col, cur);
    }
}

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

    int N, K, L;

    cin >> N >> K >> L;

    vector<vector<int>> g;

    g.resize(N);

    auto doit = [&] (vector<int>& col) {
        int cur = 0;
        for (int i = 0; i < N; i++) {
            if (col[i] == -1) {
                df(i, g, col, cur++);
            }
        }    
    };

    for (int i = 1; i <= K; i++) {
        int p, q;
        cin >> p >> q;
        p--, q--;
        g[p].push_back(q);
        g[q].push_back(p);
    }

    vector<int> Kcol(N, -1);    
    doit(Kcol);

    g = vector<vector<int>> (N);
    for (int i = 1; i <= L; i++) {
        int p, q;
        cin >> p >> q;
        p--, q--;
        g[p].push_back(q);
        g[q].push_back(p);
    }

    vector<int> Lcol(N, -1);
    doit(Lcol);

    map<pair<int, int>, int> cache;
    for (int i = 0; i < N; i++) {
        cache[{Kcol[i], Lcol[i]}]++;
    }

    for (int i = 0; i < N; i++) {
        cout << cache[{Kcol[i], Lcol[i]}] << " ";
    }
    cout << "\n";

    return 0;
}


Measured memory_bytes: 20208
def main():
    sx, sy, tx, ty = map(int, input().split())
    x = tx - sx
    y = ty - sy
    s = ""
    s += "R"*x
    s += "U"*y
    s += s.translate(str.maketrans({"U": "D",
                                    "D": "U", "L": "R", "R": "L"}))
    tmp = ""
    tmp += "D"
    tmp += "R"*(x+1)
    tmp += "U"*(y+1)
    tmp += "L"
    s += tmp + tmp.translate(str.maketrans({"U": "D",
                                            "D": "U", "L": "R", "R": "L"}))
    print(s)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9148
list1=[]
while True:
    x = input("")
    if x == "0 0":
        break
    else:
        list1.append(x)

for i,v in enumerate(list1):
    x,y = map(int,v.split())
    if x <= y:
        print(str(x) + " " + str(y))
    else:
        print(str(y) + " " + str(x))

Measured memory_bytes: 7852
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    
    long long n;
    cin>>n;
    
    int rem,q;
    string s;
    while(n>0){
        
        n=n-1;
        rem= n%26;
        char ch=rem+'a';
        s=ch+s;
        n/=26;
    }
    
    cout<<s;
    
}


Measured memory_bytes: 3116
def polygon(N: int, L: list) -> bool:
    max_l = max(L)
    return max_l < sum(L) - max_l


if __name__ == "__main__":
    N = int(input())
    L = [int(s) for s in input().split()]

    ans = polygon(N, L)
    print('Yes' if ans else 'No')


Measured memory_bytes: 2940
from math import sqrt
N = int(input())
X = []
Y = []
for i in range(N):
  x, y = map(int, input().split())
  X.append(x)
  Y.append(y)
ans = 0
for i in range(0, N-1):
  for j in range(i+1, N):
    ans += sqrt((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2)
print(ans * 2.0 / N)

Measured memory_bytes: 62208
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<climits>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>
#include<bitset>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define MOD 1000000007
#define EPS 1e-9
 
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;
struct edge{int from, to; ll cost;};

int main(){
    std::ios::sync_with_stdio(0); cin.tie(0);
    int h,w;
    cin >> h >> w;
    int area[h][w], dp[h][w], ans = 0;
    repp(i, h) repp(j, w) cin >> area[i][j];

    dp[0][0] = 1-area[0][0];
    ans = dp[0][0];
    reppp(j, 1, w){
        if(!area[0][j]) dp[0][j] = 1;
        else dp[0][j] = 0;
        ans = max(dp[0][j], ans);
    }
    reppp(i, 1, h){
        if(!area[i][0]) dp[i][0] = 1;
        else dp[i][0] = 0;
        ans = max(dp[i][0], ans);
    }
    reppp(i, 1, h){
        reppp(j, 1, w){
            if(!area[i][j]) dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
            else dp[i][j] = 0;
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans*ans << endl;
    return 0;
}



Measured memory_bytes: 18448
#include <stdio.h>
float n,m,count=0,a[1005],b;
int ans;

void check(int i) {
    printf("\ncount: %f",count);
    printf("\na[i]: %f",a[i]);
    printf("\nb: %f",b);
    printf("\nm,n: %f %f",m,n);
    printf("\nans: %d",ans);
    printf("\n");
}



void solve() {
    b=0.25/m*count;
    // check(0);
    for (int i = 0; i < n; i++) {
        if (a[i]>=b) ans++;
        // check(i);
        if (ans>=m) {
            printf("Yes");
            break;
        }
    }
    if (ans<m) printf("No");
}

int main () {
    scanf("%f%f", &n, &m);
    for(int i=0;i<n;i++) {
        scanf("%f",&a[i]);
        count+=a[i];
        // check(i);
    }
    solve();
}


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

int main(){
	int N,M;
	cin >> N >> M;
	vector<int> H(N);
	for(auto &i:H)cin >> i;
	vector<vector<int>> graph(N);
	for(int i=0;i<M;i++){
		int A,B;
		cin >> A >> B;
		A--;
		B--;
		graph[A].push_back(B);
		graph[B].push_back(A);
	}
	
	int ans=0;
	for(int i=0;i<N;i++){
		bool flag=true;
		for(auto k:graph[i]){
			if(H[i]<=H[k])flag=false;
		}
		if(flag)ans++;
	}
	cout << ans << endl;
	return 0;
}

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

int main(void){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<int> sum0(n);
    vector<int> sum1(n);
    int now0=0;
    int now1=0;
    rep(i, n){
        if(s[i]=='W') now0++;
        else now1++;
        sum0[i]=now0;
        sum1[i]=now1;
    }
    int res=n;
    rep(i, n){
        int a0, a1;
        if(i==0) {
            a0=0; 
            a1=sum1[n-1]-sum1[0];
        }
        else if(i==n-1) {
            a1=0; 
            a0=sum0[n-2];
        }
        else {
            a0=sum0[i-1];
            a1=sum1[n-1]-sum1[i];
        }
        res=min(res, a0+a1);
    }
    cout<<res<<endl;
    return 0;
}

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

int main() {
	int N;
	cin >> N;
	int dp[100010];
	dp[0] = 0;
	for (int i = 1; i <= N; i++) {
		dp[i] = dp[i - 1] + 1;
		int x = 0;
		for (int j = 1; j < 10; j++) {
			x = pow(6, j);
			if (x > i)break;
			dp[i] = min(dp[i], dp[i - x] + 1);
		}
		for (int j = 1; j < 10; j++) {
			x = pow(9, j);
			if (x > i)break;
			dp[i] = min(dp[i], dp[i - x] + 1);
		}
	}
	cout << dp[N] << endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
 
int N;
int A[210];    
 
int main(){
  cin >> N;
  for (int i = 0; i < N; ++i) cin >> A[i];
  
  int res = 0;
  
  while(true){
    bool exist_odd=false;
    for(int i = 0;i<N;++i){
      if(A[i]%2 != 0)exist_odd = true;
    }
    
    if(exist_odd)break;
    
    for (int i = 0; i < N; ++i){
      A[i] /= 2;
    }
    ++res;
  }
  
  cout << res << endl;
}

Measured memory_bytes: 256
object Main extends App {

  import scala.io.StdIn._
  import scala.math._

  val n = readLine.trim.toInt
  val numbers = readLine.trim.split(' ').map(_.toInt).toList
  implicit val memo = Array.tabulate(21){_ ⇒ 0L}.also{_(numbers.head) = 1L}
  println(
    calPattern(numbers.tail)
  )
  def calPattern(numbers: List[Int])(implicit memo: Array[Long]): Long = {
    numbers match {
      case Nil ⇒ ???
      case h::Nil ⇒ memo(h)
      case h::t ⇒
        val add = (0 to (20 - h)).map{case i ⇒ memo(i)}
        val sub = (h to 20).map{case i ⇒ memo(i)}
        memo.indices.foreach(i ⇒ memo(i) = 0L)
        for (i ← 0 to (20 - h)){
          memo(i + h) += add(i)
        }
        for (i ← h to 20){
          memo(i - h) += sub(i - h)
        }
        calPattern(t)
    }
  }
  implicit class Extenion[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}



Measured memory_bytes: 44360
def main():
    x,y,a,b,c=map(int,input().split())
    P = sorted(list(map(int,input().split())))
    Q = sorted(list(map(int,input().split())))
    R = sorted(list(map(int,input().split())))[::-1]
    S = sorted(P[-x:] + Q[-y:])
    #print(S)
    ans = 0
    ind = 0
    for s in S:
        #print(ans, s)
        if ind < len(R):
            if s > R[ind]:
                ans += s
            else:
                ans += R[ind]
                ind += 1
        else:
            ans += s
    print(ans)
main()

Measured memory_bytes: 23200
def main():
    x, n = map(int, input().split())
    
    if n==0:
        print(x)
    else:
        p = list(map(int, input().split()))
        #p = [i+1 for i in range(100)]
        truefalse = [True]*101
        for i in range(n):
            truefalse[p[i]-1] = False
        
        a = 0
        while 1:
            if truefalse[x-a-1]:
                print(x-a)
                break
            elif truefalse[x+a-1]:
                print(x+a)
                break
            else:
                a += 1

if __name__ == "__main__":
    main()

Measured memory_bytes: 9152
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define fs first
#define sc second
#define INF 1000000000
#define MOD 1000000007
#define EPS 0.00000001


int main() {
    int A, B; cin >> A >> B;
    if((A+B)%2==0) cout << (A+B)/2 << endl;
    else cout << "IMPOSSIBLE" << endl;
    
    
    return 0;
}



Measured memory_bytes: 256
n = gets.to_i
a = gets.chomp.split(' ').map(&:to_i)

if a.all?{|k|k.even?}
  puts a.map{|x|
  count = 0
  while x%2 == 0
    x = x/2
    count+= 1
  end
  count
}.min
else
  puts 0
end

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

int main(void) {
  int H, W;
  cin >> H >> W;
  vector<string> G(H);
  for (int i = 0; i < H; ++i) cin >> G[i];

  vector<int> RH;
  for (int i = 0; i < H; ++i) {
    for (int j = 0; j < W; ++j) {
      if (G[i][j] == '#') {
        RH.emplace_back(i);
        break;
      }
    }
  }

  vector<int> RW;
  for (int i = 0; i < W; ++i) {
    for (auto j : RH) {
      if (G[j][i] == '#') {
        RW.emplace_back(i);
        break;
      }
    }
  }

  for (auto i : RH) {
    for (auto j : RW) {
      cout << G[i][j];
    }
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);

    if(a!=b&&a!=c)printf("%d\n",a);
    else if(b!=a&&b!=c)printf("%d\n",b);
    else if(c!=a&&c!=b)printf("%d\n",c);

    return 0;
}

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

int main(){
  int a, b, c;
  cin >> a >> b >> c;
  if((a == b & b == c) || (a != b && a != c && b != c)){
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
  
}

Measured memory_bytes: 384
import collections
N = int(input())
lsN = []
for i in range(N):
    lsN.append(input())
M = int(input())
lsM = []
for i in range(M):
    lsM.append(input())

counterN = collections.Counter(lsN)
counterM = collections.Counter(lsM)
ans = 0
for key in counterN.keys():
    money = counterN[key]
    if key in counterM.keys():
        money -= counterM[key]
    ans = max(ans,money)
print(ans)

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

int main(){
  int n,a[101],tmp,cnt=0;
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  for(int i=0;i<n-1;i++)
    for(int j=n-1;j>0;j--){
      if(a[j]<a[j-1]){
	tmp=a[j];
	a[j]=a[j-1];
	a[j-1]=tmp;
	cnt++;
      }
    }

  for(int i=0;i<n-1;i++)cout<<a[i]<<" ";
  cout<<a[n-1]<<endl<<cnt<<endl;
  
  return 0;
}

Measured memory_bytes: 1160
import kotlin.math.*
import java.util.*

const val MOD = 1_000_000_007L

fun readI() = readLine()!!.toInt()
fun readL() = readLine()!!.toLong()
fun readD() = readLine()!!.toDouble()
fun readIs() = readLine()!!.split(' ').map(String::toInt)
fun readLs() = readLine()!!.split(' ').map(String::toLong)
fun readDs() = readLine()!!.split(' ').map(String::toDouble)

fun main() {
  val n = readI()
  val aa = readLs().sortedDescending()
  var x = aa[0]
  for (i in 1 until n - 1) {
    x += aa[(i + 1) / 2]
  }
  println(x)
}


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

int int_len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}

int int_sum(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}






int gcd(int a,int b)
{
 
  int r, tmp;
 
  
 
  /* 自然数 a > b を確認・入替 */
  if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }
 
  /* ユークリッドの互除法 */
  r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }
 
 
 
  return b;
}







int fac(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}

int vec_sum(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}
///////////////////////////
int main() {
  int n,ans=0;
  cin>>n;
  vector<int> a(n),b(n);
  rep(i,n) cin>>a[i]>>b[i];
  rep(i,n){
    ans+=b[i]-a[i]+1;
  }
  cout<<ans<<endl;
}
///////////////////////////

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,a=0,b=0;
  string s;
  cin >> n >> s;
  for(int i=0;i<n;i++){
    if(s[i]=='('){
      a++;
    }else if(s[i]==')'){
      a--;
    }
    if(a<0){
      cout << '(';
      a++;
    }
  }
  cout << s;
  for(int i=s.size()-1;i>=0;i--){
    if(s[i]=='('){
      b--;
    }else if(s[i]==')'){
      b++;
    }
    if(b<0){
      cout << ')';
      b++;
    }
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	int n;
	
	cin >> n;

	string s[n];
	#if 0
	map<char, ll> m;

	rep(i, n)
	{
		cin >> s[i];
		m[s[i][0]]++;
	}
	

	ll count = 0;
	ll m_c = m['M'];
	ll a_c = m['A'];
	ll r_c = m['R'];
	ll c_c = m['C'];
	ll h_c = m['H'];
	
	
	// ac, but complicated
	if (m_c > 0)
	{
		if (a_c > 0)
		{
			if (r_c > 0)
			{
				count += m_c * a_c * r_c;
			}

			if (c_c > 0)
			{
				count += m_c * a_c * c_c;
			}

			if (h_c > 0)
			{
				count += m_c * a_c * h_c;
			}
		}

		if (r_c)
		{
			if (c_c > 0)
			{
				count += m_c * r_c * c_c;
			}

			if (h_c > 0)
			{
				count += m_c * r_c * h_c;
			}
		}

		if (c_c)
		{
			if (h_c)
			{
				count += m_c * h_c * c_c;
			}
		}
	}

	if (a_c > 0)
	{
		if (r_c > 0)
		{
			if (c_c)
			{
				count += a_c * c_c * r_c;
			}
			if (h_c)
			{
				count += a_c * h_c * r_c;
			}
			
		}

		if (c_c > 0)
		{
			if (h_c)
			{
				count += h_c * a_c * c_c;
			}
			
		}

	}

	if (r_c)
	{
		if (c_c)
		{
			if (h_c)
			{
				count += r_c * c_c * h_c;
			}
		}
	}
	cout << count << endl;
	# endif
	map<char, ll> S;

	rep(i, n)
	{
		cin >> s[i];
		S[s[i][0]]++;
	}
	
	ll res = 0;

	res += S['M'] * S['A'] * S['R'];
	res += S['M'] * S['A'] * S['C'];
	res += S['M'] * S['A'] * S['H'];
	res += S['M'] * S['R'] * S['C'];
	res += S['M'] * S['R'] * S['H'];
	res += S['M'] * S['C'] * S['H'];
	res += S['A'] * S['R'] * S['C'];
	res += S['A'] * S['R'] * S['H'];
	res += S['A'] * S['C'] * S['H'];
	res += S['R'] * S['C'] * S['H'];
	cout << res << endl;
	
	return 0;
}


Measured memory_bytes: 5760
#include <set>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 100005;

int n, sa, sb, ans;
int a[N], b[N], v[N];
int f[N], si[N];
vector<int> va, vb;

inline int Num(int x) {
  return lower_bound(v + 1, v + 1 + *v, x) - v;
}
int Sk(int x) {
  return f[x] == x? x : f[x] = Sk(f[x]);
}
void Mr(int x, int y) {
  x = Sk(x), y = Sk(y);
  if (x != y) f[x] = y, si[y] += si[x];
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    sa ^= (v[i] = a[i]);
    va.push_back(a[i]);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &b[i]);
    sb ^= b[i];
    vb.push_back(b[i]);
  }
  va.push_back(sa), vb.push_back(sb);
  sort(va.begin(), va.end());
  sort(vb.begin(), vb.end());
  if (va != vb) {
    puts("-1");
    return 0;
  }
  v[(*v) = n + 1] = sa;
  sort(v + 1, v + 1 + *v);
  *v = unique(v + 1, v + 1 + *v) - v - 1;
  for (int i = 1; i <= *v; ++i)
    f[i] = i;
  int rt = Num(sa), idx = -1;
  for (int i = 1; i <= n; ++i)
    a[i] = Num(a[i]);
  for (int i = 1; i <= n; ++i) {
    b[i] = Num(b[i]);
    if (a[i] != b[i]) ++si[b[i]];
  }
  for (int i = 1; i <= n; ++i) {
    if (a[i] == b[i]) continue;
    if (b[i] == rt) idx = i;
    Mr(a[i], b[i]);
  }
  if (idx != -1) --ans;
  for (int i = 1; i <= *v; ++i)
    if (Sk(i) == i && si[i] > 0) ans += si[i] + 1;
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 4600
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define ll  long long 
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
#define mod 1000000007
  vector<ll>to[1000005];
int main(){
  ll a,b,d;cin>>a>>b;
  vector<ll>c(101,1);
  rep(i,b){
    cin>>d;
    c[d]=0;
  }
  rep(i,200){
    ll e=a-i,f=a+i;
    if(c[e]){
      cout<<e;
      break;
    }
    else if(f>100){
      cout<<101;
      break;
    }
    else if(c[f]){
      cout<<f;
      break;
    }
  }
}


Measured memory_bytes: 27064
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N;
  cin >> N;
  int count = 11, flag;
  for(int i = 0; i < N; i++){
    flag = 0;
    while(flag == 0){
      flag = 1;
      for(int i = 2; i <= count / 2; i++){
        if(count % i == 0){
          flag = 0;
          count += 10;
          break;
        }
      }
    }
    cout << count << ' ';
    count += 10;
  }
  return 0;
}

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

using namespace std;

// Repetitions
#define FOR(i,a,n) for(ll i = ((ll) a); i < ((ll) n); ++i)
#define FORR(i, s, g) for(ll i = ((ll)s - 1); i >= ((ll) g); --i)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) FORR(i, n, 0)

// Container Utils
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define SORTALL(v) sort(ALL(v))
#define SZ(a) int((a).size())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())

// For Debug
#define DMP(x)  cerr << #x << " = " << (x) << endl
#define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

// Aliases
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef string str;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

// Constant variables
const long double PI = (acos(-1));
const long long MOD = 1000000007;

// I/O Asynchronizing
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

bool judge(const int n, const str &s) {
    if(n % 2 != 0) return false;
    REP(i, n / 2) {
        if(s[i] != s[i + n / 2]) return false;
    }
    return true;
}

int main() {
    int n;
    str s;
    cin >> n >> s;
    cout << (judge(n, s) ? "Yes" : "No") << "\n";

    return 0;
}


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

int main() {
  int N, A, B, C, D;
  char S[200005];

  cin >> N >> A >> B >> C >> D;
  for (int i = 1; i <= N; i++) cin >> S[i];

  bool flag = false;
  for (int i = B + 1; i <= D - 1; i++) {
    if (S[i] == '#') {
      if (flag) {
        cout << "No" << endl;
        return 0;
      }
      flag = true;
    } else {
      flag = false;
    }
  }

  int funuke = -1, cnt = 0;
  bool pass = false;
  if (D < C) {
    for (int i = B-1; i <= D+1; i++) {
      if (S[i] == '.') {
        cnt++;
      } else {
        cnt = 0;
      }
      if (cnt == 3) {
        pass = true;
        funuke = i - 1;
        break;
      }
    }

    if (!pass) {
      cout << "No" << endl;
      return 0;
    }
  }

  if (funuke > 0) S[funuke] = '#';

  flag = false;
  for (int i = A + 1; i <= C - 1; i++) {
    if (S[i] == '#') {
      if (flag) {
        cout << "No" << endl;
        return 0;
      }
      flag = true;
    } else {
      flag = false;
    }
  }

  cout << "Yes" << endl;

  return 0;

}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<iomanip>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
typedef long long ll;

int main(){
  int n,ans=0;
  cin>>n;
  int x[n];
  for(int i=0;i<n;i++){
    cin>>x[i];
  }
  for(int i=0;i<n-2;i++){
    if(x[i]>x[i+1] and x[i+1]>x[i+2])
    ans++;
    else if(x[i]<x[i+1] and x[i+1]<x[i+2])
    ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <functional>
#include <ctime>
#include <iomanip>
#include <sstream>
#include <algorithm>
#define ll long long
#define dd double
#define ull unsigned long long
#define mes(x,y) memset(x,y,sizeof(x))
#define si(i) scanf("%d",&i)
#define ss(i) scanf("%s",(i))
#define sd(i) scanf("%lf",&i)
#define INF 0x3f3f3f3f
#define eps 1e-16
#define PI acos(-1)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=2e9+9;
const int mod=1e9+7;
ll GCD(ll a,ll b) {//最大公约数
    return b == 0 ? a : GCD(b, a % b);
}
ll k[200040],sum=0;
map<ll,ll>mm,flag;
ll head(ll x){
    if(!flag[x]){
        if(k[x]!=x){
            sum+=mm[x];
            return head(k[x]);
        }
        else{
            sum+=mm[x];
            return x;
        }
    }else{
        sum+=mm[x];
    }

}
int main() {
    FAST_IO;
    ll n,i,j,m;
    while(cin>>n>>m){
        for(ll i=0;i<=n;i++)k[i]=i;
        ll x,y;mm.clear();flag.clear();
        for(i=0;i<(n-1);i++){
            cin>>x>>y;
            k[y]=x;
        }
        for(i=0;i<m;i++){
            cin>>x>>y;
            mm[x]+=y;
        }
        for(ll i=1;i<=n;i++){
            sum=0;
            head(i);
            flag[i]=1;
            mm[i]=sum;
            cout<<sum<<" ";
        }
        cout<<endl;
    }
}


Measured memory_bytes: 28928
N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]

ans = B[A[0]-1]
for i in range(1, N):
    ans += B[A[i]-1]
    if A[i] == A[i-1] + 1:
        ans += C[A[i-1]-1]
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> v(n, 0);
	vector<int> h(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		h[a - 1] = max(h[a - 1], v[b - 1]);
		h[b - 1] = max(h[b - 1], v[a - 1]);
	}
	int res = 0;
	for (int i = 0; i < n; i++) {
		res += h[i] < v[i];
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3996
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <list>
#include <stack>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld   long double
#define   pb   push_back
#define   vi  vector<int> 
#define   dbg(x)  cerr << #x << " = " << x << '\n'
#define   sz(x)  (int)x.size()
#define   all(a) (a.begin(),a.end())
#define   ff   first
#define   ss   second
#define   pii  pair<int,int> 
#define   lcm(a,b) (a*b)/__gcd(a,b) 
using namespace std;

inline void solve(){
    int n,ans=0; 
    cin>>n; 
    int a[n],d;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        a[i] -= i;
    }
    sort(a,a+n);
    if(n&1) d=a[n/2];
    else d=(a[n/2]+a[(n+1)/2])/2;
    for (int &i: a) ans += abs(i-d);
    cout << ans << endl;
}

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}

/*
7
1 1 1 1 2 3 4

answer: 6

*/


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

const double PI=acos(-1.0);

string divide[4] = {"dream", "dreamer", "erase", "eraser"};
string s;

bool dfs(int n) {
    if(n == s.size()) return true;
    for(string i : divide) {
        if(n + i.size() <= s.size() && s.substr(n, i.size()) == i) {
            if(dfs(n + i.size())) return true;
        }
    }

    return false;
}

int main() {
    cin >> s;

    cout << (dfs(0) ? "YES" : "NO") << endl;

    return 0;
}

Measured memory_bytes: 2688
import math
from functools import reduce

k = int(input())

answer = (1+k)*k/2

for i in range(1, k):
  for j in range(i+1, k+1):
    answer += 6*math.gcd(i, j)
    
for x in range(1, k-1):
  for y in range(x+1, k):
    for z in range(y+1, k+1):
      answer += 6*reduce(math.gcd, [x, y, z])
      
print(int(answer))


Measured memory_bytes: 9644
// a
#include <iostream>
#include<string>
//const int maxn =;
typedef long long int ll;
using namespace std;
string a,b,c;
int ia,ib;

int main()
{
    cin>>a>>b>>ia>>ib>>c;
    if(!a.compare(c))ia--;
    else ib--;
    cout<<ia<<" "<<ib<<endl;
    return 0;
}


Measured memory_bytes: 256
function Main(input){
  
  var str = input.trim().split("\n");
  var n = parseInt(str[0],10);
  var s = str[1];
  var k = parseInt(str[2],10);

  //console.log(s);
  
  var target = s.substr(k-1,1);
  
  regexp = new RegExp("[^"+target+"]","g");
  
  var news = s.replace(regexp,"*");
  
  console.log(news)
  

  
  
  
}//function end
 
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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



int main()
{
   long i,j,k;
   long n;
   long cnt = 0;
   long left,right,mid;
   long ans = 0;
   static long e[100000];
   for(i = 0;;i++) {
      scanf("%ld",&e[i]);
      if(e[i] == 0)
         break;
   }
   for(j = 0;j < i;j++) {
   printf("Case %ld: %ld\n",j+1,e[j]);
   }
   return 0;
}

Measured memory_bytes: 1108
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;


int *N;
int n;
bool solve(int i, int m){
    if(i == n){
        return m == 0 ? true:false;
    }
    return solve(i+1, m - N[i]) || solve(i+1, m);
}

int main(){
    int t;
    scanf("%d", &n);
    N = (int *)calloc(n, sizeof(int));
    for(int i=0; i<n; i++){
        scanf("%d", &N[i]);
    }
    
    scanf("%d", &t);
    for(int i=0; i<t; i++){
        int p;
        scanf("%d", &p);
        if(solve(0, p)){
            cout << "yes" << endl;
        }else{
            cout << "no" << endl;
        }
    }
}



Measured memory_bytes: 3240
// problem: "https://atcoder.jp/contests/abc161/tasks/abc161_d"

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool reqNum(ll n)
{
    if(n < 10)
        return true;

    ll p = n%10;
    while(n)
    {
        if(abs(p-(n%10)) > 1)
            return false;

        p = n%10;
        n /= 10;
    }

    return true;
}

ll genNext(ll n)
{
    string s = to_string(n);

    ll i;
    for(i=1;i!=s.size();i++)
    {
        if(abs(s[i]-s[i-1]) > 1)
        {
            if(s[i-1] == '9')
            {
                while(i < s.size())
                {
                    s[i] = max(s[i-1]-1,(int)'0');
                    i++;
                }
            }
            else
            {
                s[i-1] = s[i-1]+1;
                while(i < s.size())
                {
                    s[i] = max(s[i-1]-1,(int)'0');
                    i++;
                }
            }

            break;
        }
    }

    return stol(s);
}

ll genNum(ll k)
{
    ll i = 0;
    ll n = 1;

    while(i != k)
    {
        if(reqNum(n))       // define
        {
            n++;
            i++;
        }
        else
            n = genNext(n);
    }

    return n-1;
}

int main()
{
    ll k;
    cin>>k;

    cout<<genNum(k);        // define

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b / 2 << endl;

    return 0;
}


Measured memory_bytes: 256