akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
using namespace std;

pair<ll, ll> calc1(ll d, ll g, vector<ll> &p, vector<ll> &c, vector<bool> &pick)
{
    ll num = 0;
    ll remain = g;
    rep(i, d)
    {
        if (pick[i] == true)
        {
            num += p[i];
            remain -= p[i] * (i + 1) * 100 + c[i];
        }
    }
    return {num, remain};
}

int calc2(ll d, ll remain, vector<ll> &p, vector<ll> &c, vector<bool> &pick)
{
    ll IINF = (1 << 30);
    ll ret = IINF;
    rep(i, d)
    {
        if (pick[i] == false)
        {
            if ((p[i] - 1) * (i + 1) * 100 < remain)
            {
                continue;
            }
            ll cur = (remain + (i + 1) * 100 - 1) / ((i + 1) * 100);
            ret = min(ret, cur);
        }
    }
    return ret;
}

int main(int argc, char const *argv[])
{
    ll d, g;
    cin >> d >> g;
    vector<ll> p(d), c(d);
    rep(i, d)
    {
        cin >> p[i] >> c[i];
    }
    ll ans = (1 << 30);
    rep(i, (1 << d))
    {
        vector<bool> pick;
        rep(j, d)
        {
            pick.push_back((((i >> j) & 1) == 1) ? true : false);
            //cerr << pick.back() << " ";
        }
        //cerr << endl;
        auto ret = calc1(d, g, p, c, pick);
        //cerr << ret.first << " " << ret.second << endl
        //    << endl;
        if (ret.second <= 0)
            ans = min(ans, ret.first);
        else
        {
            ll rem = calc2(d, ret.second, p, c, pick);
            if (rem == (1 << 30))
            {
                continue;
            }
            ans = min(ans, ret.first + rem);
        }
    }
    assert(ans < (1 << 30));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
bool used[8];
string s[8];
int A[8];
bool ok(char a,char b){return (a^b)==32;}
bool dfs(int id)
{
	if(id==8)return true;
	for(int i=0;i<8;i++)
	{
		if(used[i])continue;
		used[i]=true;
		A[id]=i;
		for(int r=0;r<8;r++)
		{
			for(int rr=0;rr<4;rr++)
			{
				bool check=true;
				if(id==0);
				else if(id==1)check=ok(s[A[0]][4],s[i][1]);
				else if(id==2)check=ok(s[A[0]][2],s[i][3]);
				else if(id==3)check=ok(s[A[1]][2],s[i][3])&&ok(s[A[2]][4],s[i][1]);
				else if(id==4)check=ok(s[A[0]][5],s[i][0]);
				else if(id==5)check=ok(s[A[1]][5],s[i][0])&&ok(s[A[4]][4],s[i][1]);
				else if(id==6)check=ok(s[A[2]][5],s[i][0])&&ok(s[A[4]][2],s[i][3]);
				else if(id==7)check=ok(s[A[3]][5],s[i][0])&&ok(s[A[5]][2],s[i][3])&&ok(s[A[6]][4],s[i][1]);
				if(check)
				{
					if(dfs(id+1))return true;
				}
				char tmp=s[i][1];
				s[i][1]=s[i][2];
				s[i][2]=s[i][4];
				s[i][4]=s[i][3];
				s[i][3]=tmp;
			}
			if(r<4)
			{
				char tmp=s[i][0];
				s[i][0]=s[i][1];
				s[i][1]=s[i][5];
				s[i][5]=s[i][4];
				s[i][4]=tmp;
			}
			else
			{
				char tmp=s[i][0];
				s[i][0]=s[i][2];
				s[i][2]=s[i][5];
				s[i][5]=s[i][3];
				s[i][3]=tmp;
			}
		}
		used[i]=false;
		A[id]=0;
		if(id==0)return false;
	}
	return false;
}
main()
{
	while(cin>>s[0])
	{
		if(s[0]=="0")break;
		for(int i=1;i<8;i++)cin>>s[i];
		for(int i=0;i<8;i++)used[i]=false;
		cout<<(dfs(0)?"YES":"NO")<<endl;
	}
}


Measured memory_bytes: 3040
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    string a,b,c;
    cin>>a>>b>>c;
    if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0])cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

}


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

int main(void){
    int N, K;

    scanf("%d%d", &N, &K);

    int i, j;

    int *x = (int *) malloc(sizeof(int) * N);
    int *y = (int *) malloc(sizeof(int) * N);
    char *c = (char *) malloc(sizeof(char) * N);

    for(i = 0; i < N; i ++){
        scanf("%d%d%*c%c", x + i, y + i, c + i);
    }

    int **count_B = (int **) malloc(sizeof(int *) * K);
    int **count_W = (int **) malloc(sizeof(int *) * K);

    for(i = 0; i < K; i ++){
        count_B[i] = (int *) malloc(sizeof(int) * K);
        count_W[i] = (int *) malloc(sizeof(int) * K);

        for(j = 0; j < K; j ++){
            count_B[i][j] = count_W[i][j] = 0;
        }
    }
    // K * K に落とす
    for(i = 0; i < N; i ++){
        if(c[i] == 'B'){
            if((x[i] / K + y[i] / K) % 2 == 0){
                count_B[x[i] % K][y[i] % K] ++;
            }else{
                count_W[x[i] % K][y[i] % K] ++;
            }
        }else{
            if((x[i] / K + y[i] / K) % 2 == 0){
                count_W[x[i] % K][y[i] % K] ++;
            }else{
                count_B[x[i] % K][y[i] % K] ++;
            }
        }
    }
    // 累積和
    for(j = 1; j < K; j ++){
        count_B[0][j] += count_B[0][j - 1];
        count_W[0][j] += count_W[0][j - 1];
    }
    for(i = 1; i < K; i ++){
        count_B[i][0] += count_B[i - 1][0];
        count_W[i][0] += count_W[i - 1][0];

        for(j = 1; j < K; j ++){
            count_B[i][j] += count_B[i][j - 1] + count_B[i - 1][j] - count_B[i - 1][j - 1];
            count_W[i][j] += count_W[i][j - 1] + count_W[i - 1][j] - count_W[i - 1][j - 1];
        }
    }
    // 最大値を求める
    int max_sum = 0;

    for(i = 0; i < K; i ++){
        for(j = 0; j < K; j ++){
            int sum = count_B[K - 1][K - 1];

            if(i > 0){
                sum += - count_B[i - 1][K - 1] + count_W[i - 1][K - 1];
            }
            if(j > 0){
                sum += - count_B[K - 1][j - 1] + count_W[K - 1][j - 1];
            }
            if(i > 0 && j > 0){
                sum += 2 * (count_B[i - 1][j - 1] - count_W[i - 1][j - 1]);
            }
            if(sum > max_sum){
                max_sum = sum;
            }
        }
    }
    for(i = 0; i < K; i ++){
        for(j = 0; j < K; j ++){
            int sum = count_W[K - 1][K - 1];

            if(i > 0){
                sum += - count_W[i - 1][K - 1] + count_B[i - 1][K - 1];
            }
            if(j > 0){
                sum += - count_W[K - 1][j - 1] + count_B[K - 1][j - 1];
            }
            if(i > 0 && j > 0){
                sum += 2 * (count_W[i - 1][j - 1] - count_B[i - 1][j - 1]);
            }
            if(sum > max_sum){
                max_sum = sum;
            }
        }
    }
    printf("%d\n", max_sum);

    return 0;
}

Measured memory_bytes: 8960
#include<iostream>
using namespace std;
long long x[200000],y[200000];
int main()
{
	long long n,d,m=0,i,j,t=0;
	cin>>n>>d;
	for(i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];	
		if(t!=-1&&x[i]*x[i]+y[i]*y[i]<=d*d) m++;
	
	}
	cout<<m<<endl;
	return 0;
} 

Measured memory_bytes: 6760
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H;
long long int ans;


int main() {
	ios::sync_with_stdio(false);
	char a, b;
	cin >> a >> b;
	if (a == b)cout << "H\n";
	else cout << "D\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                   \
  ifstream in("atcoder-problems/diverta2019_2_b.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v) \
rep(l, v.size()) { cout << v[l] << " "; } \
cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18+100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N;
  cin >> N;
  
  vector<ll> x(N), y(N);
  rep(i, N) { cin >> x[i] >> y[i]; }

  ll ans = N;

  map<pair<ll, ll>, ll> map;
  rep(i, N) rep(j, N) {
    if (i == j) continue;
    ll p = x[i] - x[j];
    ll q = y[i] - y[j];
    map[{p, q}]++;
  }

  ll ret = 0;
  for (auto kv : map) {
    ret = max(ret, kv.second);
  }

  cout << ans - ret << endl;
}

Measured memory_bytes: 3652
#coding: utf-8
import math

while True:
    n = int(input())
    if n == 0:
        break
    s = [float(i) for i in input().split(" ")]
    m = 0

    for i in s:
        m += i
    m /= n

    a2 = 0
    for i in s:
        a2 += (i-m)**2/n

    print(math.sqrt(a2))



Measured memory_bytes: 5784
(let* ((n (read))
       (a (make-array n))
       (f (if (evenp n) 0 1))
       (c (if (evenp n) (/ n 2) (/ (1- n) 2)))
       (b (make-array n)))
  (dotimes (i n)
    (setf (aref a i) (read)))
  (dotimes (i n)
    (let ((j (+ c (* (expt -1 (+ i f)) (truncate (1+ i) 2)))))
      (setf (aref b j)
            (aref a i))))
  (loop with last = (1- n)
        for i from 0 to last
        do (princ (aref b i))
        unless (= i last) do (princ " "))
  (terpri))

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

static const int MAX = 10000;
static const int WHITE = 0;
static const int BLACK = 1;

int n, e;
int indeg[MAX], color[MAX];
vector<int> L[MAX];
vector<int> vec;

void bfs(int u) {
	queue<int> Q;
	Q.push(u);
	color[u] = BLACK;
	while (!Q.empty()) {
		int uu = Q.front();
		Q.pop();
		vec.push_back(uu);
		for (int i = 0; i < L[uu].size(); i++) {
			int v = L[uu][i];
			indeg[v]--;
			if (indeg[v] == 0) {
				color[v] = BLACK;
				Q.push(v);
			}
		}
	}
}

void TopoligicalSort() {
	for (int i = 0; i < n; i++)	{
		if (color[i] == WHITE && indeg[i] == 0) {
			bfs(i);
		}
	}
}

int main() {
	cin >> n >> e;
	int s, t;

	for (int i = 0; i < n; i++) {
		color[i] = WHITE;
		indeg[i] = 0;
	}

	for (int i = 0; i < e; i++)	{
		cin >> s >> t;
		indeg[t]++;
		L[s].push_back(t);
	}

	TopoligicalSort();

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

	return 0;

}

Measured memory_bytes: 2028
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
#define pii pair<int, int>
#define pll pair<long long, long long>

using ll = long long;
const ll inf = 1001001001;
int main() {
    int n, m;
    cin >> n >> m;
    vector<ll>h(n);
    vector<ll>v(n, 0);
    rep(i, 0, n){
        cin >> h[i];
    }
    rep(i, 0, m){
        int a, b;
        cin >> a >> b;
        a--; b--;
        v[a] = max(v[a],h[b]);
        v[b] = max(v[b],h[a]);
    }
    int ans = 0;
    rep(i, 0, n){
        if(v[i] < h[i])ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4812
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input!{
      n: usize,
      mut ss: [chars; n]
    }
    for i in 0..n {
        ss[i].sort();
    }
    let mut s2: Vec<String> = ss.iter().map(|s| s.iter().map(|&c| c).collect()).collect();

    use std::collections::HashMap;
    let mut map = HashMap::new();

    for s in s2.iter() {
        *map.entry(s).or_insert(0) += 1;
    }

    let mut ans = 0 as u64;
    for (k,v) in map {
        if v > 0 {
            ans += (v*(v-1))/2;
        }
    }
    puts!("{}\n", ans);
}


Measured memory_bytes: 26876
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
  int a[4],b[2];
  int ans=0,i;
  for(i=0;i<4;i++)
    cin >> a[i];
  for(i=0;i<2;i++)
    cin >> b[i];
  sort(a,a+4);
  sort(b,b+2);
  for(i=3;i>0;i--)
    ans+=a[i];
  ans+=b[1];
  cout << ans << '\n';
  return 0;
}
  

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

using namespace std;

int main()
{
  int N;
  string s;
  cin >> N >> s;
  long long sum[3][100010] = {{0}};
  string JOI = "JOI";
  for(int i = 1; i <= N; i++){
    for(int j = 0; j < 3; j++){
      sum[j][i] += sum[j][i-1] + (s[i-1] == JOI[j]);
    }
  }

  long long ans = 0;
  for(int i = 0; i < N; i++){
    if(s[i] == 'O') ans += sum[0][i]*(sum[2][N]-sum[2][i]);
  }

  long long inO = 0;
  for(int i = 0; i < N; i++){
    inO = max(inO, sum[0][i]*(sum[2][N]-sum[2][i]));
  }
  long long inJ = 0, inI = 0;
  for(int i = 0; i < N; i++){
    if(s[i] == 'O'){
      inJ += (sum[2][N]-sum[2][i+1]);
      inI += sum[0][i];
    }
  }
  cout << ans+max(inO, max(inJ, inI)) << endl;
  return 0;
}

Measured memory_bytes: 3688
#include <iostream>
#include <vector>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<map>
#include<bitset>
#include<math.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for(int i=m;i<(int)(n);i++)
typedef pair<int,int> pint;
typedef pair<long long,pint> p3;
typedef long long ll;
const int inf   = 1e9+7;
const ll  longinf = 1LL<<60;
const int mod=1e9+7;
int dx[4]={1,0,-1,0}, dy[4]={0,1,0,-1};

int main(){
  ll h,w;
  cin>>h>>w;
  map<pint,int> mp;
  int n;cin>>n;
  rep(i,n){
    int a,b;
    scanf("%d %d",&a,&b);
    REP(j,-1,2)REP(k,-1,2){
      int nx=a+j,ny=b+k;
      if(1<nx&&nx<h&&1<ny&&ny<w)
        mp[{nx,ny}]++;
      }
    }
  ll ans[10];
  rep(i,10)ans[i]=0;
  ans[0]=(h-2)*(w-2);
  for(auto x:mp){
    ans[x.second]++;
    ans[0]--;
    }
  rep(i,10)cout<<ans[i]<<"\n";
  return 0;
  }

Measured memory_bytes: 56448
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int h = sc.nextInt();
			int m = sc.nextInt();
			int s = sc.nextInt();
			if(h == -1 && m == -1 && s == -1) break;
			int t1 = 3600 * 2;
			int t2 = 3600 * 2 * 3;
			int t = h * 3600 + m * 60 + s;
			t1 -= t;
			t2 = 3 * t1;
			int h1 = t1 / 3600;
			t1 -= 3600 * h1;
			int m1 = t1 / 60;
			t1 -= 60 * m1;
			System.out.printf("%02d:%02d:%02d\n", h1, m1, t1);
			int h2 = t2 / 3600;
			t2 -= 3600 * h2;
			int m2 = t2 / 60;
			t2 -= 60 * m2;
			System.out.printf("%02d:%02d:%02d\n", h2, m2, t2);
		}
		sc.close();
	}
}


Measured memory_bytes: 26496
#include <bits/stdc++.h>
#define int long long int
#define ld long double
#define pb push_back
#define pf push_front
#define ft first
#define sc second
#define all(v) v.begin(), v.end()
using namespace std;
const int maxn = 201001;
signed main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ld l;
    cin >> l;
    cout.precision(16);
    l /= 3.0;
    cout << l * l * l;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline

n,a,b,c=map(int,input().split())
L=[]
A=[a,b,c]
for i in range(n):
    L.append(int(input()))
L.sort()

Ans=10**9
for i in range(4**n):
    F=[[] for i in range(3)] #竹格納:[A,B,C]
    now=i
    for j in range(n):
        r=now%(4**(j+1))
        chk=r//(4**(j))
        if chk!=3:
            F[chk].append(L[j])
        now-=r    
    if F[0] and F[1] and F[2]: #竹が1本以上あるとき
        ans=0
        for k in range(3):
            f=F[k] #竹一覧
            Len=len(f)
            mp=10**9
            for l in range(1,2**Len):
                t=0
                cnt=0
                for q in range(Len):
                    if (l>>q)&1:
                        cnt+=1
                        t+=f[q]
                mp=min(abs(t-A[k])+10*(max(0,cnt-1)),mp)
            ans+=mp
        Ans=min(ans,Ans)
print(Ans)

Measured memory_bytes: 51804
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define inf 0x3f3f3f3f
#define eps 1e-20
ll read()
{
	ll tmp=0; char c=getchar(),f=1;
	for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
	for(;'0'<=c&&c<='9';c=getchar())tmp=tmp*10+c-'0';
	return tmp*f;
}
using namespace std;
int t[100010],x[100010],y[100010];
int n;
int main()
{
	n=read();
	t[0]=x[0]=y[0]=0;
	int flag=1;
	for(int i=1;i<=n;i++){
		t[i]=read(); x[i]=read(); y[i]=read();
		if(t[i]-t[i-1]<abs(x[i]-x[i-1])+abs(y[i]-y[i-1])||(abs(x[i]-x[i-1])+abs(y[i]-y[i-1])+t[i]-t[i-1])%2){
			flag=0; break;
		}
	}
	if(flag)printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>
#define mod  1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back

using namespace std;

using ll = long long;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

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

const int N_MAX = 100005;
const int M_MAX = 200005;

struct Edge {
  int to;
  ll cost;
};

int N, M;
vector<int> L(M_MAX), R(M_MAX);
vector<ll> D(M_MAX);
vector<Edge> E[M_MAX];
vector<ll> pos(N_MAX, LLONG_MAX);
vector<bool> confirm(N_MAX, false);

bool dfs(int curr){
  if(confirm[curr]) return true;
  confirm[curr] = true;
  for(auto e : E[curr]){
    if(pos[e.to] == LLONG_MAX){
      pos[e.to] = pos[curr] + e.cost;
      if(!dfs(e.to)) return false;
    } else {
      if(pos[e.to] != pos[curr] + e.cost) return false;
    }
  }
  return true;
}

int main(){
  cin >> N >> M;
  // if(M == 0){cout << "Yes" << endl; return 0;}
  int start = N_MAX;
  for(int i = 0; i < M; i++){
    cin >> L[i] >> R[i] >> D[i];
    E[L[i]].push_back({R[i],  D[i]});
    E[R[i]].push_back({L[i], -D[i]});
    start = min({start, R[i], L[i]});
  }

  pos[start] = 0;
  bool ok = true;
  for(int i = start; i < N + 1; i++){
    if(!confirm[i] && !dfs(i)){
      ok = false;
      break;
    }
  }
  
  // for(int i = 0; i < N + 1; i++) cerr << i << ": " << pos[i] << endl;
  
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 22016
using System;

public class Dice
{
	private int[] labels;
	public const int TOP = 0;
	public const int FRONT = 1;
	public const int RIGHT = 2;
	public const int LEFT = 3;
	public const int BACK = 4;
	public const int BOTTOM = 5;
	public Dice( int[] labels )
	{
		this.labels = labels;
	}
	public void roll( string cmds )
	{
		int t;
		for( int i=0; i<cmds.Length; i++ ) {
			if( 'E' == cmds[i] ) {
			t = this.labels[TOP];
				this.labels[TOP] = this.labels[LEFT];
				this.labels[LEFT] = this.labels[BOTTOM];
				this.labels[BOTTOM] = this.labels[RIGHT];
				this.labels[RIGHT] = t;
			} else if( 'S' == cmds[i] ) {
				t = this.labels[TOP];
				this.labels[TOP] = this.labels[BACK];
				this.labels[BACK] = this.labels[BOTTOM];
				this.labels[BOTTOM] = this.labels[FRONT];
				this.labels[FRONT] = t;
			} else if( 'W' == cmds[i] ) {
				t = this.labels[TOP];
				this.labels[TOP] = this.labels[RIGHT];
				this.labels[RIGHT] = this.labels[BOTTOM];
				this.labels[BOTTOM] = this.labels[LEFT];
				this.labels[LEFT] = t;
			} else if( 'N' == cmds[i] ) {
				t = this.labels[TOP];
				this.labels[TOP] = this.labels[FRONT];
				this.labels[FRONT] = this.labels[BOTTOM];
				this.labels[BOTTOM] = this.labels[BACK];
				this.labels[BACK] = t;        
			} else if( 'M' == cmds[i] ) {
				t = this.labels[FRONT];
				this.labels[FRONT] = this.labels[RIGHT];
				this.labels[RIGHT] = this.labels[BACK];
				this.labels[BACK] = this.labels[LEFT];
				this.labels[LEFT] = t;        
			}	
		}
	}
	public int getLabel( int face )
	{
		return this.labels[face];
	}
	public bool isEqual( Dice another )
	{
		string cmds = "SWWWSMMMM";
		for( int i=0; i<6; i++ ) {
			if( another.getLabel( Dice.TOP ) == this.getLabel( Dice.TOP ) ) {
				for( int j=5; j<9; j++ ) {
					if( another.getLabel( Dice.FRONT ) == this.getLabel( Dice.FRONT ) ) {
						int k;
						for( k=Dice.TOP; k<=Dice.BOTTOM; k++ ) {
							if( another.getLabel( k ) != this.getLabel( k ) ) { break; }		
						}
						if( 6 == k ) { return true; }
						break;
					}
					this.roll( cmds[j].ToString() );		
				}
			}
			this.roll( cmds[i].ToString() );			
		}
		return false;
	}
	
}

public class Test
{
	public static void Main( )
	{

		int[] labels = Array.ConvertAll( Console.ReadLine().Split( ' ' ), int.Parse );
		Dice dice = new Dice( labels );
		labels = Array.ConvertAll( Console.ReadLine().Split( ' ' ), int.Parse );
		Dice dice2 = new Dice( labels );
		if( dice.isEqual( dice2 ) ) {
			Console.WriteLine( "Yes" );
		} else {
			Console.WriteLine( "No" );
		}
	}
}

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

using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define all(c) begin(c),end(c)
const ll INF = 1e10;
int main() {
	cin.sync_with_stdio(false);
	ll l0 = 2, l1 = 1, l2;
	int cnt = 2;
	int N;
	cin >> N;
	if (N == 1)cout << 1 << endl;
	else {
		while (1) {
			l2 = l0 + l1;
			l0 = l1; l1 = l2;
			if (cnt == N) {
				cout << l2 << endl;
				return 0;
			}
			cnt++;
		}
	}

	return 0;
}


Measured memory_bytes: 256
#Deven-Eleven:
D = (((-1, -1), (0, -1), (1, 0), (0, 1), (-1, 1), (-1, 0)),
     ((0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 0)))
def func(y, x):
    q = [(y, x, 0)]
    cover = [[-1] * m for _ in xrange(n)]
    while len(q) != 0:
        y, x, step = q.pop(0)
        if cover[y][x] >= 0:
            continue
        cover[y][x] = step
        for dx, dy in D[y % 2]:           
            ny, nx = y + dy, x + dx
            if 0 <= ny < n and 0 <= nx < m:
                q.append((ny, nx, step + 1))
    return cover
 
def solve():
    scover = [func(pos[1] - 1, pos[0] - 1) for pos in spos]
    min_cover = [[min(sc[y][x] for sc in scover) for x in xrange(m)] for y in xrange(n)]
    def count(cover):
        ret = 0
        for y in xrange(n):
            for x in xrange(m):
                if cover[y][x] < min_cover[y][x]:
                    ret += 1
        return ret
    return max(count(func(pos[1] - 1, pos[0] - 1)) for pos in tpos)
 
while True:
    try:
        data = raw_input()
        if data == "0":
            break
        m, n = map(int, data.split())
        s = input()
        spos = [map(int, raw_input().split()) for _ in xrange(s)]
        t = input()
        tpos = [map(int, raw_input().split()) for _ in xrange(t)]
        print solve()
    except:
        break

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;
  string S;
  cin >> S;
  int K;
  cin >> K;
  set<string> s;
  for(int i = 0; i < S.size(); i++){
    string tmp;
    for(int j = 0; i + j < S.size() && j < 5; j++){
      tmp += S[i+j];
      s.insert(tmp);
    }
  }
  for(int i = 0; i < K - 1; i++){
    string tmp = *s.begin();
    s.erase(tmp);
  }
  cout << *begin(s) <<endl;
}


Measured memory_bytes: 4800
#[allow(unused_imports)]
use proconio::{fastout, input};

#[fastout]
fn main() {
    input!(n: usize, mut l: [isize; n]);
    let mut count = 0;
    l.sort_unstable();

    for i in 0..n {
        for j in i + 1..n {
            let a1 = l[i] - l[j];
            let a2 = l[j] - l[i];
            let a3 = l[i] + l[j];
            for k in j + 1..n {
                if a1 < l[k] && a2 < l[k] && l[k] < a3 {
                    count += 1;
                }
            }
        }
    }

    println!("{}", count);
}


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

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

	string S;
	bool A = true;
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		if ((i + 1) % 2 == 1) {
			if (S[i] == 'L') A = false;
		}
		else {
			if (S[i] == 'R') A = false;
		}
	}
	
	if (A) cout << "Yes" << endl;
	else cout << "No" << 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;
using P = pair<int,int>;

const int MX = 100001;

int main(){
  string s;
  cin >> s;

  int ans = 0;
  for(char c : s){
    if(c=='1') ans++;
  }

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

Measured memory_bytes: 3616
#include<iostream>
#include<math.h>
#include <algorithm>
#include<float.h>
#include <limits>
#include <vector> 
#include <numeric>

#define rep(i,a,n) for(int (i) = (a);(i) < (n);(i)++)
#define urep(i,a,n) for(int (i) = (a);(i) > (n);(i)--)
#define MOD 1000000007
#define ll long long

using namespace::std;
int main(){
int K,S;
  cin>>K>>S;
  int count=0;
  urep(i,S,-1){
    if(i<K+1){
      rep(u,0,S-i+1){
        if(u<K+1){
        if((S-i-u>-1)&&(S-i-u<K+1)){
          count++;
        }}
      }
    }
  }
  cout<<count;
  


}
// int *p = new int[N];

// vector<vector<int>> 変数名(左の個数, vector<int>(右の個数));

//


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

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

  vector<int> A(N+1,0), B(N+1,0), C(N,0);

  for (int i=1; i<=N; i++) {
    int a;
    cin >>a;
    A.at(i) =a;
  }
  for (int i=1; i<=N; i++) {
    int  b;
    cin >>b;
    B.at(i) =b;
  }
  for (int i=1; i<=N-1; i++) {
    int c;
    cin >>c;
    C.at(i) =c;
  }

  int man;
  for(auto x : B) {
    man += x;
  }
  for (int i=1; i<=N-1; i++) {
    if (A.at(i)+1 == A.at(i+1)) {
      man += C.at(A.at(i));
    }
  }
  cout << man <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll, vl/*, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, n) for(ll i = 1; i <= ll(n); i++)
//#define rep(i, k, n) for(ll i = k-1; i < ll(n); i++)
//#define rep2(i, k, n) for(ll i = k; i <= ll(n); i++)
#define all(v) (v).begin(), (v).end()
bool chmin(ll &a, ll &b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll &b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
ll num, ans=0, count=0;

int main() {
  ld sum=0;
  ll N, M;
  cin >> N >> M;
  vector<ld> A(N);
  rep(i, N) cin >> A[i];
  sort(all(A), greater<ld>());
  
  rep(i, N) sum += A[i];
  sum /= (4*M);

  if(A[M-1] >= sum) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    int n;
    
    scanf("%d", &n);
    
    int a[n];
    int i;
    
    for(i=0;i<n;i++) scanf("%d", &a[i]);
    
    int count = 0;
    
    for(i=0;i<n;i++){
        while(a[i]%2==0){
            a[i] /= 2;
            count++;
        }
    }
    
    printf("%d", count);

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string S;
  cin >> S;
  if (S == "SUN")
  {
    cout << 7 << endl;
  }
  if (S == "MON")
  {
    cout << 6 << endl;
  }
  if (S == "TUE")
  {
    cout << 5 << endl;
  }
  if (S == "WED")
  {
    cout << 4 << endl;
  }
  if (S == "THU")
  {
    cout << 3 << endl;
  }
  if (S == "FRI")
  {
    cout << 2 << endl;
  }
  if (S == "SAT")
  {
    cout << 1 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX=1e16;
const int INF=1e6+100;
int main()
{
    int n,a,b;
    cin>>n;
    ll x=1,y=1;
    ll r,l,mid;
    for(int i=0; i<n; i++){
        cin>>a>>b;
        mid=max(x/a,y/b);
        while(mid*a<x || mid*b<y) mid++;
        x=mid*a;
        y=mid*b;
    }
    cout<<x+y<<endl;
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define fs first
#define sc second

int main(void){
    int a,b;
    cin >> a >> b;
    int ans = b*10;
    while(1){
        if((int)(ans * 0.08) == a){
            cout << ans << endl;
            return 0;
        }
        if((int)(++ans * 0.1) != b){
            cout << -1 << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
L, R = gets.split.map(&:to_i)

if R - L >= 2018
  puts 0
else
  ans = 2019

  (L..R-1).each do |i|
    (i+1..R).each do |j|
      # p "i:#{i} j:#{j}"
      t = i*j % 2019
      if ans > t
        ans = t
      end
    end
  end

  p ans
end


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

int main() {
    int N, Q;  cin >> N >> Q;
    dsu d(N);
    for (int i = 0; i < Q; ++i) {
        int t, u, v;  cin >> t >> u >> v;
        if (t == 0) d.merge(u, v);
        else cout << d.same(u, v) << endl;
    }
}


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

int main() {
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i, n) cin >> x[i];
    int ans = 1001001001;
    for (int p = 1; p <= 100; ++p) {
        int now = 0;
        rep(i, n) now += (x[i]-p)*(x[i]-p);
        ans = min(ans, now);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//increase stack size
#pragma comment(linker, "/STACK:16777216")

ll mxm() {return LLONG_MIN;}
template<typename... Args>
ll mxm(ll a, Args... args) { return max(a,mxm(args...)); }

ll mnm() {return LLONG_MAX;}
template<typename... Args>
ll mnm(ll a, Args... args) { return min(a,mnm(args...)); }

template<class T> ostream& operator<<(ostream& os,vector<T> V){
	os<<"[ ";for(auto v:V)os<<v<<" ";return os<<"]";
}
template<class L,class R> ostream& operator<<(ostream& os,pair<L,R> P){
	return os<<"("<<P.first<<","<<P.second<<")";
}

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__,__VA_ARGS__)
template<typename Arg1>
void __f(const char* name,Arg1&& arg1){
	cout<<name<<" : "<<arg1<<endl;
}
template <typename Arg1,typename... Args>
void __f(const char* names,Arg1&& arg1,Args&&... args){
	const char* comma=strchr(names+1,',');cout.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1,args...);
}
#else
#define trace(...) 1
#endif

#define ld long double
#define pll pair<ll,ll>
#define ii pair<int,int>
#define vll vector<ll>
#define vii vector<ii>
#define vi vector<int>
#define vpll vector<pll>
#define vld vector<ld>
#define vvld vector<vld>
#define vvi vector<vi>
#define vvll vector<vll>
#define vvpll vector<vpll>
#define vvii vector<vii>
#define I insert
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x)	x.begin(),x.end()

const int mod=1e9+7;
// 128 bit: __int128
inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}

struct compare{
	bool operator() (const int &a,const int &b) const{
		return a>b;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
	int n;
	cin >> n;
	ll ans = 0;
	for(int i = 1; i <= n; i++){
		if(i % 3 > 0 && i % 5 > 0)
			ans += i;
	}
	cout << ans << endl;
}

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

def dfs(s):
  if int(s) > N:
    return 0
  
  if all(s.count(c) for c in "753"):
    ret = 1
  else:
    ret = 0
    
  for c in "753":
    ret += dfs(s+c)
  return ret

print(dfs("0"))

Measured memory_bytes: 54620
import java.util.*;
public class Main {
	// 2307 start
	//2322 TLE
	
	HashMap<String, HashSet<String>> data;

	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(true){
			int n = sc.nextInt();
			if(n == 0)break;
			String first = null;
			data = new HashMap<String, HashSet<String>>();
			for(int i = 0; i < n; i++){
				String [] input = sc.next().replaceAll("\\.", "").split(":");
				HashSet<String> s = new HashSet<String>();
				String [] mem = input[1].split(",");
				for(int j = 0; j <  mem.length; j++){
					s.add(mem[j]);
				}
				data.put(input[0], s);
				if(i == 0){
					first = input[0];
				}
			}
			HashSet<String> res = solve(first);
			
			System.out.println(res.size());
			//debug
			
//			for(String s : data.keySet()){
//				System.out.println("debug " + s + " " + Arrays.toString(data.get(s)));
//			}
//			System.out.println("-----");
		}
	}

	private HashSet<String> solve(String str) {
		
		if(data.containsKey(str)){
			HashSet<String> now = data.get(str);
			HashSet<String> res = new HashSet<String>();
			for(String key : now){
				res.addAll(solve(key));
			}
			data.put(str, res);
			return res;
		}
		else{
			HashSet<String> now = new HashSet<String>();
			now.add(str);
			return now;
		}
		
	}

	public static void main(String[] args) {
		Main obj = new Main();
		obj.doit();
	}
}

Measured memory_bytes: 13000
{-# LANGUAGE FlexibleInstances    #-}
{-# LANGUAGE TypeSynonymInstances #-}

import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                  as A
import qualified Data.Array.IArray           as IA
import qualified Data.Array.IO               as AI
import qualified Data.Array.MArray           as MA
import qualified Data.Array.ST               as STA
import qualified Data.Array.Unboxed          as AU
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import qualified Data.Graph                  as G
import           Data.Int
import qualified Data.IntMap                 as IM
import qualified Data.IntSet                 as IS
import           Data.List
import qualified Data.Map.Strict             as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence               as SQ
import qualified Data.Set                    as S
import           Data.Time
import qualified Data.Tree                   as T
import qualified Data.Vector                 as V
import qualified Data.Vector.Mutable         as VM
import qualified Data.Vector.Unboxed         as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putLn :: Show a => a -> IO ()
putLn = print

putList :: Show a => [a] -> IO ()
putList [n] = put n
putList (n:ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n] = putStr n
putStrList (n:ns) = do
  putStr n
  putStr " "
  putStrList ns

yesNoUpper b
  | b = putStrLn "YES"
  | otherwise = putStrLn "NO"

yesNo b
  | b = putStrLn "Yes"
  | otherwise = putStrLn "No"

main = do
  a<-readInt
  put $ sum $ take 2 $ sort a  

Measured memory_bytes: 380
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  string s,t;
  cin>>n>>s;
  t=s.at(0);
  for(int i=1;i<n;i++){
    if(s.at(i)!=s.at(i-1)){
      t+=s.at(i);
    }
  }
  cout<<t.size()<<endl;
}

Measured memory_bytes: 640
#include <stdio.h>

int main(){
  int X, Y, Z;
  scanf("%d %d %d", &X, &Y, &Z);
  printf("%d\n", (X - Z)/(Y + Z));
  return 0;
}


/*
n人が座れるとすると，
  X - n*Y >= (n + 1)*Z
すなわち
  X - Z >= (Y + Z)*n
が成り立つ．
*/


Measured memory_bytes: 128
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 200003; INF = float("inf")

import numpy as np

def fft_np(a, b, n):
	N = 2 ** ((n - 1).bit_length() + 1) - n
	a = np.append(a, [0] * N)
	b = np.append(b, [0] * N)
	A = np.fft.rfft(a)
	B = np.fft.rfft(b)
	C = A * B
	c = np.fft.irfft(C)
	c = np.rint(c).astype(int)

	return c

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	B = np.array([0] * mod)
	conv = defaultdict(int)
	num = 2
	for i in range(1, mod):
		conv[num] = i
		num = (num * 2) % mod

	for i in range(N):
		if A[i] == 0:
			continue
		x = conv[A[i]]
		B[x] += 1

	# print(B)

	C = fft_np(B, B, mod)
	# print(C)
	M = len(C)
	ans = 0
	for i in range(M):
		ans += C[i] * pow(2, i, mod)

	for i in range(mod):
		ans -= B[i] * pow(2, 2 * i, mod)

	print(ans // 2)



if __name__ == '__main__':
	main()








Measured memory_bytes: 102984
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

vector<vector<int>> edges;
vector<LL> values;
vector<int> visited;

void dfs(int node) {
  visited[node] = 1;
  for (int next : edges[node]) {
    if (!visited[next]) {
      values[next] += values[node];
      dfs(next);
    }
  }
}

int main(int argc, char *argv[]) {
  int n, q;
  cin >> n >> q;
  edges.resize(n);
  values.resize(n);
  visited.resize(n);
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    edges[a - 1].push_back(b - 1);
    edges[b - 1].push_back(a - 1);
  }
  for (int i = 0; i < q; ++i) {
    int p, x;
    cin >> p >> x;
    values[p - 1] += x;
  }
  dfs(0);
  for (LL v : values) {
    cout << " " << v;
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 21888
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;




int main()
{
	vector <string> S;
	string tmp;
	int N;

	int start = 0;
	int count = 0;
	int maxCount = 0;

	cin >> N;

	for(int i=0; i<N; i++){
		cin >> tmp;
		S.push_back(tmp);
	}

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

	for(int i=0; i<N; i++){
		if(S[i] == S[start]){
			count++;
			if(count > maxCount){
				maxCount = count;
			}
		}else{
			count = 1;
			start = i;
		}
	}

	count = 0;

	if(maxCount == 1){
		for(int i=0; i<N; i++){
			cout << S[i] << endl;
		}
	}else{
		for(int i=0; i<N; i++){
			if(S[i] == S[start]){
				count++;
				if(count == maxCount){
					cout << S[start] << endl;
				}
			}else{
				count = 1;
				start = i;
			}
		}
	}

	return 0;
}

Measured memory_bytes: 14320
import sys
read = sys.stdin.readline
import time
from heapq import heappush, heappop, heapify
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()

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

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)



Measured memory_bytes: 32732
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] dp = new int[n][3];
		dp[0][0] = sc.nextInt();
		dp[0][1] = sc.nextInt();
		dp[0][2] = sc.nextInt();
		for(int i = 1; i < n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			dp[i][0] = Math.max(dp[i-1][1]+a, dp[i-1][2]+a);
			dp[i][1] = Math.max(dp[i-1][0]+b, dp[i-1][2]+b);
			dp[i][2] = Math.max(dp[i-1][0]+c, dp[i-1][1]+c);
		}
		int max = Math.max(dp[n-1][0], Math.max(dp[n-1][1], dp[n-1][2]));
		System.out.println(max);
		sc.close();
	}

}

Measured memory_bytes: 97484
#include <iostream>

using namespace std;

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if (a > b) swap(a,b);
    if (b > c) swap(b,c);
    if (a > b) swap(a,b);
    cout << a << ' ' << b << ' ' << c << endl;
    return 0;
}


Measured memory_bytes: 3112
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    int H, W;
    while(1){
        cin >> H >> W;
        if(H==0&&W==0) break;
        else{
            for(int i=0; i<H; i++){
                for(int j=0; j<W; j++){
                    if(i%2==1&&j%2==1)      cout << "#" << flush;
                    else if(i%2==0&&j%2==0) cout << "#" << flush;
                    else                    cout << "." << flush;
                }
                cout << endl;
            }
            cout << endl;
        }
    }
}


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

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

Measured memory_bytes: 3616
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
#define forn(i,a,b)for(int i=(a),_b=(b);i<=_b;i++)
#define fore(i,b,a)for(int i=(b),_a=(a);i>=_a;i--)
#define rep(i,n)for(int i=0,_n=n;i<n;i++)
#define ll long long
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define m_p make_pair
#define re return
#define pb push_back
#define si set<int>
#define ld long double
#define X first
#define Y second
#define st string
#define ull unsigned long long
#define mod 1000000007
#define INF 1000000007
#define x1 XZVJDFADSPFOE
#define y1 GASDIJSLDAEJF
#define x2 DFDAJKVOHKWIW
#define y2 PSFSAODSXVNMQ
#define LLINF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
inline void read(int &x)
{
	short negative=1;
    x=0;
    char c=getchar();
    while(c<'0' || c>'9')
    {
		if(c=='-')
			negative=-1;
		c=getchar();
	}
    while(c>='0' && c<='9')
        x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=negative;
}
ll quickpower(ll n,ll k){
	ll ans=1;
	while(k){
		if(k%2){
			ans*=n;
			ans%=mod;
		}
		n*=n;
		n%=mod;
		k/=2;
	}
	return ans;
}
string int_to_string(int n)
{
	string s="";
	while(n)
	{
		int now=n%10;
		s+=now+'0';
		n/=10;
	}
	reverse(s.begin(),s.end());
	return s;
}
int string_to_int(string s)
{
	int n=0;
	rep(i,s.size())
	{
		n*=10;
		n+=s[i]-'0';
	}
	return n;
}
ll low,high;
int n;
ll k;
ll a[200100];
bool check(int l)
{
	ll res=0;
	rep(i,n)
	{
		if(a[i]%l==0)
		{
			res+=a[i]/l-1;
		}
		else res+=a[i]/l;
	}
	if(res<=k)return 1;
	return 0;
}
int main()
{
	ios::sync_with_stdio(0);
	//think twice,code once
	cin>>n>>k;
	rep(i,n)cin>>a[i];
	low=1;
	high=1e9;
	while(low<high)
	{
		int mid=(low+high)>>1;
		if(check(mid))high=mid;
		else low=mid+1;
	}
	cout<<low<<endl;
	return 0;
}

Measured memory_bytes: 5180
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int index = -1;
    if(n == k){
      System.out.println(1);
      System.exit(0);
    }
    for(int i = 0; i < n; i++){
      if(sc.nextInt() == 1){
        index = i;
        break;
      }
    }
    //System.out.println(index);
    int ans = (int)Math.ceil((double)index / (k - 1));
    //System.out.println(ans);
    if(index == 0) ans = 1;
    if(k-1 != 1){
      index += (index > (k-1)) ? (k-1) - (index % (k-1)) : (k - 1) - index;
    }
    if(index > n - 1){
      System.out.println(ans);
      System.exit(0);
    }
    //System.out.println(index);
    ans += (int)Math.ceil((n - 1 - index) / (double)(k - 1));
    System.out.println(ans);
  }
}

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

int main() {
    int H, W;
    
    while(true) {
        cin >> H >> W;

        if(H == 0 && W == 0) { break; }

        for(int i = 0; i < H; i++) {
            for(int j = 0; j < W; j++) {
                if((i + j) % 2 == 0) {
                    cout << "#";
                }
                else {
                    cout << ".";
                }
            }
            cout << "\n";
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 3108
n,k=map(int,input().split())
a=list(map(int,input().split()))
x,ans=0,0
for i in range(40,-1,-1):
    cnt1=0
    for j in a:
        if j>>i&1:
            cnt1+=1
    if n-cnt1>cnt1 and x+2**i<=k:
        x+=2**i
        ans+=(n-cnt1)*2**i
    else:
        ans+=cnt1*2**i
print(ans)

Measured memory_bytes: 14596
#include <iostream>
#include <algorithm>
#include <array>
#include <functional>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>

#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define rep(i,a,b) for(i = (a); i < (b); i++)
#define bitget(a,b) (((a) >> (b)) & 1)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vsort(x) sort(x.begin(),x.end())

using int64 = uint64_t;

using namespace std;

int main() {

	int i, j, k;
	int n;
	cin >> n;
	vint a(n), b(n), c(n+1);
	rep(i, 0, n)
		cin >> a[i];
	rep(i, 0, n)
		cin >> b[i];
	rep(i, 0, n)
		cin >> c[i+1];
	vsort(a);
	vsort(b);
	vsort(c);
	long long int d[2][100003] = {};
	int nowc = n;
	int now = 0;
	for (i = n - 1;i != -1;i--) {
		while (c[nowc] > b[i]) {
			now++;
			nowc--;
		}
		d[1][i] = now;
	}
	for (i = n - 2;i != -1;i--) {
		d[1][i] += d[1][i + 1];
	}
	nowc = n - 1;
	for (i = n - 1;i != -1;i--) {
		while (nowc!=-1&&b[nowc] > a[i]) {
			nowc--;
		}
		d[0][i] = d[1][nowc+1];
	}
	for (i = n - 2;i != -1;i--) {
		d[0][i] += d[0][i + 1];
	}
	cout << d[0][0] << endl;
	return 0;
}

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

using LL =unsigned long long;
using namespace std;

int main()
{
    int c,b;cin >> c >> b;
    string str;
    str += to_string(c);
    str += to_string(b);
    int ans = stoi(str);
    for(int a = 1;a < ans;a++){
        if((ans%a)==0&&(ans/a)==a){
            cout<<"Yes"<<endl;
            return 0;
        }            
    }
    cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256