akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp> 
//using namespace boost::multiprecision; 
using namespace std;
#define ll long long int
#define ld long long double
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define nl '\n'
#define mp make_pair
#define debug1(x) cout <<#x<<" "<<x<<'\n';
#define debug2(x,y) cout <<#x<<" "<<x <<" "<<#y<<" "<<y <<'\n';
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<'\n';
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define inf 1e18
const int mod = (int)1e9+7;
pair<ll,ll>s4[4]={{-1,0},{1,0},{0,-1},{0,1}};
pair<ll,ll>s8[8]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,1},{1,0},{1,-1}};

void solve() {
    ll x;
    cin >>x;
    ll k=x;
    ll ans = 0;
    ll rem = x%500;
    ll q = x/500;
    ans = q*1000 + 5*(rem/5);
    cout << ans <<endl;
}

signed main() {
    boost;
    solve();
}

Measured memory_bytes: 256
import copy
n = int(input())
times = [int(i) for i in input().split()]
m = int(input())
px = [input().split() for _ in range(m)]
n_times = copy.copy(times)
for p,x in px:
    n_times[int(p)-1] = int(x)
    print(sum(n_times))
    n_times = copy.copy(times)

Measured memory_bytes: 3444
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
long long a[222222],lef[222222],rig[222222],n,ans;
priority_queue<pair<long long,long long> > pq;
int main()
{
	scanf("%lld",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
	{
		while(!pq.empty() && pq.top().first>a[i])
		{
			rig[pq.top().second]=i;
			pq.pop();
		}
		pq.push(make_pair(a[i],i)); 
	}
	while(!pq.empty())
	{
		rig[pq.top().second]=n+1;
		pq.pop();
	}
	for (int i=n;i>=1;i--)
	{
		while(!pq.empty() && pq.top().first>a[i])
		{
			lef[pq.top().second]=i;
			pq.pop();
		}
		pq.push(make_pair(a[i],i)); 
	}
	while(!pq.empty())
	{
		lef[pq.top().second]=0;
		pq.pop();
	}
	for (int i=1;i<=n;i++)
	{
		ans+=a[i]*(i-lef[i])*(rig[i]-i);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 10096
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  string s;
  cin >> s;
  n=s.length();
  if(s[n-1]=='3') cout << "bon";
  else if(s[n-1]=='0'||s[n-1]=='1'||s[n-1]=='6'||s[n-1]=='8'){
    cout << "pon";
  }
  else{cout << "hon";}
  return 0;
}

Measured memory_bytes: 3624
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main
{
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    public static void main(String args[])
    {
        FastReader obj = new FastReader();
        int dist = obj.nextInt(),house = obj.nextInt(),no_house[] = new int[house];
        for(int i=0;i<house;i++) no_house[i] = obj.nextInt();
        int find[] = new int[house];
        for(int i=0;i<house;i++)
        {
            if(i==0)
                find[i] = no_house[no_house.length-1]-no_house[i];
            else
                find[i] = (dist-no_house[i])+no_house[i-1];
        }
        int min = Integer.MAX_VALUE;
        for(int i=0;i<house;i++) min = Math.min(find[i],min);
        System.out.println(min);
    }
}


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

double dp[100110], ans[100110];

int main(){
	dp[1] = 1.0;
	for(int i = 1; i <= 100000; ++i){
		double pr1 = dp[i], pr2 = 1.0;
		for(int j = 0; j < 50; ++j){
			dp[i + j + 1] += pr1 * (1.0 - pr2);
			ans[i + j] += pr1 * pr2;
			pr1 *= pr2;
			pr2 *= 0.5;
		}
	}
	for(int i = 1; i <= 100000; ++i){
		ans[i] += ans[i - 1];
	}
	
	int n;
	while(scanf("%d", &n), n){
		printf("%f\n", ans[n]);
	}
}

Measured memory_bytes: 2624
package main

import "fmt"

func solve() int {
    var n int
    fmt.Scan(&n)
    table := make([][]int, n)
    for i := 0; i < n; i++ {
        table[i] = make([]int, n)
        for j := 0; j < n; j++ {
            var x int
            fmt.Scan(&x)
            table[i][j] = x
        }
    }

    not_used := make([][]bool, n)
    for i := 0; i < n; i++ {
        not_used[i] = make([]bool, n)
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if i != k && j != k {
                    if table[i][j] > table[i][k] + table[j][k] {
                        return -1
                    } else if table[i][j] == table[i][k] + table[j][k] {
                        table[i][j] = table[i][k] + table[j][k]
                        not_used[i][j] = true
                    }
                }
            }
        }
    }

    ret := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if not_used[i][j] == false {
                ret += table[i][j]
            }
        }
    }
    ret >>= 1
    return ret
}

func main() {
    fmt.Println(solve())
}


Measured memory_bytes: 4736
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
count = 0
for i in range(N):
    A = list(map(int, input().split()))
    value = [A[i]*B[i] for i in range(M)]
    value = sum(value) + C
    if value>0:
        count += 1
print(count)

Measured memory_bytes: 3060
T1, T2 = map(int, input().split())
A1, A2 = map(int, input().split())
B1, B2 = map(int, input().split())
Ad = A1 * T1 + A2 * T2
Bd = B1 * T1 + B2 * T2
if Ad == Bd:
    print('infinity')
else:
    if Bd > Ad:
        Ad, Bd = Bd, Ad
        A1, B1 = B1, A1
    if A1 > B1:
        print(0)
    else:
        num = (B1 - A1) * T1 // (Ad - Bd)
        if (B1 - A1) * T1 % (Ad - Bd) == 0:
            print(num * 2)
        else:
            print(num * 2 + 1)


Measured memory_bytes: 3064
N = int(input())
A = [int(input()) for _ in range(N)]
total = sum(A)
A = A + A

def check(next_piece, piece_size):
    for i in range(N):
        ni = next_piece[i]
        if ni == -1: continue
        if piece_size[i] >= total: continue

        ni %= N
        nni = next_piece[ni]
        if nni == -1: continue
        if total - piece_size[i] - piece_size[ni] >= mid:
            return True
    return False

def tow_pointers(mid):
    # しゃくとり法でインデックスの左側を全探索しつつ、合計がmid以上になる最小区間がどこまでかを求める
    # next_piece[i] := iから計算した合計がmid以上になる最小区間の終端インデックス
    # piece_size[i] := iから計算した合計がmid以上になる最小区間の終端インデックスまでの合計値
    next_piece = [-1] * N
    piece_size = [-1] * N
    right, amount = 0, 0
    for left in range(N):
        while right < N * 2 and amount < mid:
            amount += A[right]
            right += 1
        if amount >= mid:
            # amoutがmid以上の場合、それぞれの記録用配列に値を格納する
            next_piece[left] = right
            piece_size[left] = amount
        # ここの役割がわかんね、両方共なんだか必要に見えなくもない
        amount -= A[left]
    return next_piece, piece_size

# 二部探索
low, high = 0, 1 << 60
while high - low > 1:
    mid = low + (high - low) // 2
    next_piece, piece_size = tow_pointers(mid)
    if check(next_piece, piece_size):
        low = mid
    else:
        high = mid

print(low)




Measured memory_bytes: 24804
import java.util.Scanner

import scala.math._

object Main extends App {
  val sc = new Scanner(System.in)
  val N = sc.nextInt
  val h = Array.fill(N)(sc.nextInt)

  val dp = Array.fill(N)(Int.MaxValue)

  dp(0) = 0
  for (i <- 1 until N) {
    val dp1 = dp(i - 1) + abs(h(i) - h(i - 1))
    val dp2 = if (i != 1) dp(i - 2) + abs(h(i) - h(i - 2)) else Int.MaxValue
    dp(i) = min(dp1, dp2)
  }
  println(dp.last)
}


Measured memory_bytes: 53468
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

typedef long long ll;
const int mod=1e9+7;

int main(){
	int n;
	cin >> n;
	vector<ll> num(6);
	for(int i=0; i<n; i++){
		string s;
		cin >> s;
		int tmp;
		switch(s[0]){
			case 'M':tmp=0;break;
			case 'A':tmp=1;break;
			case 'R':tmp=2;break;
			case 'C':tmp=3;break;
			case 'H':tmp=4;break;
			default :tmp=5;break;
		}
		num[tmp]++;
	}
	ll ans=0;
	for(int i=0; i<3; i++){
		for(int j=i+1; j<4; j++){
			for(int k=j+1; k<5; k++)
				ans += num[i]*num[j]*num[k];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>

#define F first
#define S second
#define vsort(v) sort((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())

using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    int n, x;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> x;
        v[i] = x;
    }
    vsort(v);
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (v[i] > v[i-1]) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define rep(i,a,b)	for(ll  i=a;i<b;i++)
#define hello777 ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#include <string>
#define pie 3.14159265358979323846
constexpr int MOD = 1e9+7;
const int MAX= 1e5+5;
using namespace std;


//ll gcd(int a, int b)
//{ 
//    if (a == 0) 
//        return b;  
//    return gcd(b % a, a);  
// } 
// 
//ll lcm(int a, int b)  
// {  
//    return a/gcd(a, b) *b;  
// }
//  
//int prime(int n)
//{
//	rep(i,2,n+1)
//	{
//		if(n%i==0)return i;
//	}
//	
//vector<unordered_set<int> > prime_factors(MAX,unordered_set<int>());
//int primes[MAX];
//int prefix[MAX][6];
//void sieve(){
//    //primes i stores the largest prime factor of a number....
//    for(int i=2;i<MAX;++i){
//        if(primes[i]!=0){
//            continue;
//        }
//        primes[i] = i;
//        for(int j=2*i;j<MAX;j+=i){
//            primes[j] = i;
//        }
//    }
//    
//    for(int i=2;i<MAX;++i){
//        int current = i;
//        
//        while(current!=1){
//            prime_factors[i].insert(primes[current]);
//            current = current/primes[current];
//        }
//    }
//    
//    for(int i=1;i<MAX;++i){
//        for(int k=1;k<=5;++k){
//            prefix[i][k] = prefix[i-1][k] + (prime_factors[i].size()==k);
//        }
//    }
//    
//}
void solve() 
{
	ll a;
	cin>>a;
	ll ans=a+a*a+a*a*a;
	cout<<ans<<endl;
}

int main()
{
	hello777;
	int q=1;
	
//    cin>>q;
    while(q--)
    {   
      solve();

    }
}



Measured memory_bytes: 3596
#include <stdio.h>
#define MAX 2000000

int H,A[MAX+1];

void maxHeap(int i);

int main(){
    int i;
    scanf("%d",&H);
    for(i=1;i<=H;i++)
        scanf("%d",&A[i]);
    for(i=H/2;i>=1;i--)
        maxHeap(i);
    for(i=1;i<=H;i++)
        printf(" %d",A[i]);
    puts("");
    return 0;
}



void maxHeap(int i){
    int l,r,largest,temp;
    l=2*i;
    r=2*i+1;
    if(l <= H && A[l] > A[i])
        largest=l;
    else
        largest=i;
    if(r <= H && A[r] > A[largest])
        largest=r;

    if(largest != i){
        temp=A[i];
        A[i]=A[largest];
        A[largest]=temp;
        maxHeap(largest);
    }
}


Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#define rep(i,l,n) for(lint i=l;i<n;i++)
#define rer(i,l,n) for(lint i=l;i<=n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define pb(a) push_back(a)
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef vector<int> vi;
typedef vector<lint> vli;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int dp[110][10010]={};

int main(){
	int N,W,v[110]={},w[110]={};
	cin>>N>>W;
	rep(i,1,N+1){
		cin>>v[i]>>w[i];
	}
	rep(i,1,N+1){
		rep(j,0,W+1){
			if(j>=w[i]){
				dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
			}else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	o(dp[N][W]);
}

Measured memory_bytes: 5212
#include<stdio.h>
int main(void)
{
	int a,b;
	char op[10];
	scanf("%d %c %d",&a,&op,&b);
	if(op[0]=='+'){
		printf("%d\n",a+b);
	}
	else{
		printf("%d\n",a-b);
	}
	return 0;
}

Measured memory_bytes: 128
/* ex2_2
   kohei_suzuki */

#include <stdio.h>
int main(void){
    int N; //マス目
    int A; //白のマス数

    scanf("%d", &N);//入力受取
    scanf("%d", &A);//入力受取

    if(1<=N<=100 && 0<=A<=N*N){
        printf("%d", N*N-A);
    }
    return 0;
}

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

int main(void){
    int a, b, c, d;
    while (cin >> a >> b >> c >> d && a) {
        if (a >= b*c) {
            cout << 0 << endl;
            continue;
        }
        int ans = (b * c - a) / d;
        if ((b * c - a) % d) ans++;
        cout << ans << endl;
    }
}

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

typedef unsigned uint;

unsigned count(std::vector<uint> s, std::vector<uint> t){
  uint n = 0;
  for(uint i = 0; i < t.size(); i++){
    uint v = t[i];
    uint min = 0, max = s.size();
    while(min < max){
      uint mid = (min + max) / 2;
      uint v_mid = s[mid];
      if(v_mid == v) n++;
      if(v_mid >= v) max = mid;
      else min = mid+1;
    }
  }
  return n;
}

int main(){
  std::ios_base::sync_with_stdio(false);

  uint n;
  std::cin >> n;
  std::vector<uint> s(n,0);
  for(uint i = 0; i < n; i++){
    std::cin >> s[i];
  }
  s.erase(std::unique(s.begin(),s.end()),s.end());

  uint q;
  std::cin >> q;
  std::vector<uint> t(q,0);
  for(uint i = 0; i < q; i++){
    std::cin >> t[i];
  }

  std::cout << count(s,t) << '\n';
}

Measured memory_bytes: 2064
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        solve(System.in, System.out);
    }

    static void solve(InputStream is, PrintStream os) {
        // Your code here!
        Scanner scan = new Scanner(is);
        int N = scan.nextInt();
        int a[] = new int[N];

        for(int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }

        int ans = 0;
        int nextK = 1;
        for(int i = 0; i < N; i++) {
            if(a[i] != nextK)
                ans++;
            else
                nextK++;
        }

        if(ans == N)
            os.println("-1");
        else
            os.println(ans);
    }
}

Measured memory_bytes: 88136
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int a = sc.nextInt();
      int b = sc.nextInt();
      int c = sc.nextInt();
      int m1 = Math.min(a,Math.min(b,c));
      int m2 = Math.max(a,Math.max(b,c));
      int n = a+b+c-m1-m2;
      if(m1==5&&n==5&&m2==7)System.out.println("YES");
      else System.out.println("NO");
    }
}


Measured memory_bytes: 21332
/*  -*- coding: utf-8 -*-
 *
 * c.cc: 
 */

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

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  int cnt = 0;
  char pc = ' ';
  for (int i = 0; i < s.size(); i++) {
    if (pc != s[i]) cnt++;
    pc = s[i];
  }

  printf("%d\n", cnt - 1);
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
    
using namespace std;

int main()
{ 
      ios::sync_with_stdio(0);
      cin.tie(0);
      
      int i,k,j,d,cnt=0;cin>>k>>j>>d;
      
      for(i=k;i<=j;i++)
     {
        if(i%d==0)
        cnt++;
    
     }
    
     cout<<cnt;

                          
     return 0;
}

Measured memory_bytes: 3664
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

class state{
	public:
		int x1,y1,x2,y2;
		int cost;
	state(int tx,int ty,int kx,int ky,int c){
		x1 = tx;
		y1 = ty;
		x2 = kx;
		y2 = ky;
		cost = c;
	}
};
int dx1[] = {-1,1,0,0};
int dy1[] = {0,0,1,-1};
int dx2[] = {1,-1,0,0};
int dy2[] = {0,0,-1,1};

int main()
{
	int x,y;
	while(cin >> x >> y){
		if(!x&&!y)
			break;
		int tx,ty,kx,ky;
		cin >> tx >> ty;
		cin >> kx >> ky;
		bool field[52][52];
		bool memo[52][52][52][52];
		memset(field,1,sizeof(field));
		memset(memo,false,sizeof(memo));
		
		for(int i=1;i<=y;i++){
			for(int j=1;j<=x;j++){
				cin >> field[i][j];
			}
		}
		queue<state> q;
		q.push(state(tx,ty,kx,ky,0));
		memo[tx][ty][kx][ky] = true;
		int ans = -1;
		while(!q.empty()){
			state st = q.front();q.pop();
			if(st.cost >= 100)
				break;
			if(st.x1 == st.x2 && st.y1 == st.y2){
				ans = st.cost;
				break;
			}
			for(int i=0;i<4;i++){
				int nx1 = st.x1 + dx1[i];
				int ny1 = st.y1 + dy1[i];
				int nx2 = st.x2 + dx2[i];
				int ny2 = st.y2 + dy2[i];
				state nst = st;
				if(field[ny1][nx1] == 0){
					nst.x1 = nx1;
					nst.y1 = ny1;
				}
				if(field[ny2][nx2] == 0){
					nst.x2 = nx2;
					nst.y2 = ny2;
				}
				nst.cost++;
				if(memo[nst.x1][nst.y1][nst.x2][nst.y2] == false){
					memo[nst.x1][nst.y1][nst.x2][nst.y2] = true;
					q.push(nst);
				}
			}
		}
		if(ans == -1)
			cout << "NA" << endl;
		else
			cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 8368
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string str;
    int sum = 0;

    cin >> str;

    if(str[0] == '1') sum++;
    if(str[1] == '1') sum++;
    if(str[2] == '1') sum++;

    cout << sum << endl;
     
    return 0;
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define ALL(x) (x).begin(), (x).end()

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1e15;

int main() {
  ll n, m;
  cin >> n >> m;
  if (n == m)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <cstdio>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)

typedef long long ll;

const int Inf = 100100100;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;  cin >> n >> m;
    int ans = 0;
    vector<int> x(m), div(m - 1);
    rep(i, m) {
      cin >> x[i];
    }
    sort(x.begin(), x.end(), greater<int>());
    rep(i, m - 1) {
      div[i] = x[i] - x[i + 1];
    }
    sort(div.begin(), div.end(), greater<int>());
    if (n >= m) {
      cout << 0 << '\n';
      return 0;
    }
    rep(i, n - 1) {
      div[i] = 0;
    }
    rep(i, m - 1) {
      ans += div[i];
    }
    cout << ans << '\n';

    return 0;
}


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

const int INF = 1000000000;

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

		if(n==0)
			break;

		int T[10][10];
		for(int i=0; i<10; i++){
			for(int j=0; j<10; j++){
				if(i==j){
					T[i][j] = 0;
				}
				else{
					T[i][j] = INF;
				}
			}
		}

		int m = 0;	

		for(int i=0; i<n; i++){
			int a, b, c;
			cin >> a >> b >> c;

			T[a][b] = T[b][a] = c;

			if(a+1>m){
				m = a+1;
			}
			if(b+1>m){
				m = b+1;
			}
		}
		
		int d[m];
		for(int i=0; i<m; i++)
			d[i]=0;
			
		for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				for(int k=0; k<m; k++){
					if(T[j][k]>T[j][i]+T[i][k]){
						T[j][k]=T[j][i]+T[i][k];
					}
				}
			}
		}
		
		int min,num;
		for(int i=0; i<m; i++){
			for(int j=0; j<m; j++){
				d[i]+=T[i][j];
			}
			if(min>d[i] || i==0){
				min=d[i];
				num=i;
			}
		}
		cout<<num<<' '<<min<<endl;
	}

	return 0;
}

Measured memory_bytes: 3076
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var line = System.Console.ReadLine();
            var lineAry = line.Split(' ');
            int N = ConvToInt(lineAry[0]);
            int K = ConvToInt(lineAry[1]);

            line = System.Console.ReadLine();
            List<int> valList = new List<int>();
            foreach (var l in line.Split(' '))
            {
                valList.Add(ConvToInt(l));
            }
            valList.Sort();

            int sum = 0;
            for (int i=0; i<K; i++)
            {
                sum += valList[i];
            }

            Console.WriteLine(sum);
            return;
        }

        static int ConvToInt(string str)
        {
            int val = 0;
            return int.TryParse(str, out val) == true ? val : 0;
        }
    }
}


Measured memory_bytes: 28132
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
int main()
{
	int s,n,t;
	cin>>s>>n;
	while(n--)
	{
		cin>>t;
		s-=t;
		//printf("s=%d\n",s);//*************************
	}
	cout<<((s<0)?-1:s);
	return 0;
}

Measured memory_bytes: 3596
#include<iostream>
using namespace std;
int main()
{
    int bill;

    cin >> bill;
    if(bill%1000==0){
    
    cout << "0"<<endl;
    }
    else{
        int    return_bill=1000-(bill%1000);
        cout << return_bill<<endl;
    }

    return 0;
}


Measured memory_bytes: 3624
Option Strict On
Imports System.Console
Imports System.Collections.Generic

Module Program
    Const n As Integer = 3

    Sub Main()
        Dim s As New Dictionary(Of Integer, String)

        For i As Integer = 0 To n - 1
            s(Asc("A") + i) = NextString()
        Next

        Dim turn As Integer = Asc("A")

        Do While s(turn) <> ""
            Dim pre As Integer = turn
            turn = Asc(StrConv(s(turn)(0), vbUpperCase))
            s(pre) = Mid(s(pre), 2)
        Loop

        WriteLine(Chr(turn))
    End Sub

    Function NextString() As String
        Dim result As New List(Of String)
        Do
            Dim tmp As Integer = Read()
            If tmp < 0 Then Exit Do
            Dim nextChar As Char = Chr(tmp)

            If Not Char.IsWhiteSpace(nextChar) Then
                result.Add(nextChar)
            ElseIf nextChar <> vbCr Then
                Exit Do
            End If
        Loop
        Return String.Join("", result)
    End Function

End Module


Measured memory_bytes: 22096
from collections import deque
n = int(input())
edges_ls = [[0,0] for _ in range(n-1)]
edges_d = {}
ver_ls = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edges_d[(a,b)] = i
    edges_d[(b,a)] = i
    edges_ls[i] = [a,b]
    ver_ls[a].append(b)
    ver_ls[b].append(a)
n_color = 0
for ver in ver_ls:
    n_color = max(n_color,len(ver))
def next_color(color):
    return (color+1)%n_color

edge_color = [0] * (n-1)
q = deque()
color_now = 0
for ver in ver_ls[0]:
    q.append([0,ver,color_now])
    edge_color[edges_d[(0,ver)]] = color_now
    color_now = next_color(color_now)
done_ls = [0] * n
done_ls[0] = 1

while q:
    From, to, color_now = q.popleft()
    # verはtoからの行先
    for ver in ver_ls[to]:
        if not done_ls[ver]:
            q.append([to,ver,next_color(color_now)])
            edge_color[edges_d[(to,ver)]] = next_color(color_now)
            color_now = next_color(color_now)
    done_ls[to] = 1

print(n_color)
for color in edge_color:
    print(color+1)

Measured memory_bytes: 63736
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n, c; cin >> n >> c;
    
    vector<int> p(n);
    int cake = 0;
    
    for( int i = 0; i < c; i++ ){
        cin >> p[i];
        cake += p[i];    
    }
    
    if( cake % ( n + 1 ) == 0 ){
        cout << cake / ( n + 1 ) << endl;
    }else{
        cout << cake / ( n + 1 ) + 1 << endl;
    }
    
    
}


Measured memory_bytes: 3088
#include <iostream>
#include <cstring>
using namespace std;
int main() {
    char a[3];
    char b[3];
    char c[3];
    cin>>a;
    cin>>c;
    int j =0,count=0;
   for(int i=strlen(a)-1;i>=0;i--){

          b[j]=a[i];
          j++;
      }

   for (int k = 0; k < strlen(a); ++k) {
      if(b[k]==c[k]){
         count++;
      }
   }
   if(count==strlen(a)) cout<<"YES"<<endl;
   else cout<<"NO"<<endl;
   }


Measured memory_bytes: 256
#include <iostream>
//#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1
//#define INFTY 1000000000000000000

int main(){
    LL x;
    cin >> x;
    if(x>=30){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include<vector>
#include<string>
using namespace std;
int main() {
 int n,m,i,j,k[10],s[10][10],p[10],data[10]={1,2,4,8,16,32,64,128,256,512};
  int sum=0,d=0;
  bool g;
  cin >> n >> m;
  for (i=0;i<m;i++){
    cin >> k[i];
    for (j=0;j<k[i];j++) cin >> s[i][j];
  }
  for (i=0;i<m;i++) cin >> p[i];
  for (int t=0;t<data[n-1]*2;t++){
    g=true;
    for (i=0;i<m;i++){
      d=0;
      for (j=0;j<k[i];j++) if (t&data[s[i][j]-1]) d++;
      if (d%2!=p[i]){
        g=false;
        break;
      }
    }
    if (g) sum++;
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
while True:
    w, h = map(int, input().split())
    if w == 0: break
    goal = (w,h)
    vart = []
    hori = []
    for i in range(2*h-1):
        if i % 2 == 0:
            vart.append(list(map(int, input().split())))
        else:
            hori.append(list(map(int, input().split())))
    node = [[0 for i in range(h)] for i in range(w)]
    queue = [(0,0)]
    while queue:
        p = queue.pop(0)
        x, y = p[0], p[1]
        node[x][y] += 1
        if y-1 >= 0 and hori[y-1][x] == 0 and node[x][y-1] == 0:
            node[x][y-1] = node[x][y]
            queue.append((x,y-1))
        if y+1 < h and hori[y][x] == 0 and node[x][y+1] == 0:
            node[x][y+1] = node[x][y]
            queue.append((x,y+1))
        if x-1 >= 0 and vart[y][x-1] == 0 and node[x-1][y] == 0:
            node[x-1][y] = node[x][y]
            queue.append((x-1,y))
        if x+1 < w and vart[y][x] == 0 and node[x+1][y] == 0:
            node[x+1][y] = node[x][y]
            queue.append((x+1,y))
    print(node[w-1][h-1])

Measured memory_bytes: 7748
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
ll h, w;
vvc s(50, vc(50));
vvb visit(50, vb(50, false));
int DFS(int i, int j, int count)
{
	int ans=count;

	visit[i][j]=true;

	if(i>0){
		if(!visit[i-1][j]&&s[i-1][j]=='#') ans=DFS(i-1, j, count+1);
	}
	if(i<h-1){
		if(!visit[i+1][j]&&s[i+1][j]=='#') ans=DFS(i+1, j, count+1);
	}
	if(j>0){
		if(!visit[i][j-1]&&s[i][j-1]=='#') ans=DFS(i, j-1, count+1);
	}
	if(j<w-1){
		if(!visit[i][j+1]&&s[i][j+1]=='#') ans=DFS(i, j+1, count+1);
	}
	return ans;
}
int main(void)
{
	cin>>h>>w;

	rep(i, h){
		rep(j, w) cin>>s[i][j];
	}

	bool flag=true;
	rep(i, h){
		rep(j, w){
			if(!visit[i][j]&&s[i][j]=='#'){
				int ans=DFS(i, j, 1);
				if(ans==1){
					flag=false; break;
				}
			}
		}
	}
	cout<<yn(flag)<<endl;
}

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

using namespace std;
using ll = long long;

int main()
{
    ll a = 100, x, c = 0;
    cin >> x;
    while (a < x)
    {
        a += a / 100;
        c++;
    }
    cout << c << endl;
}

Measured memory_bytes: 3620
#include <cstdlib>
#include <iostream>
#include <string>
#include <time.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
//#include "bits/stdc++.h"
using namespace std;
//using namespace std::vector;
#define rep(i,a,b) for(int i=(a);i<(b);++i)


#define huge 1000000007
typedef long long ll;

int main(void) {

	ll N = 0;
	ll A = 0;
	ll B = 0;
	ll C = 0;
	ll K = 0;
	ll Y = 0;
	ll X = 0;
	//ll m[100000] = {};
	//ll p[100] = {};
	//ll x[100] = {};
	ll *x, *c, *d;
	string S,T,U;
	ll count = 0;
	ll sum = 0;
	ll min = 1;
	ll max = 0;
	int flag = 0;
	//char p;
	cin >> S >> T >> U;
	
	//x = (ll *)malloc(N * sizeof(ll));
	if(S[S.length()-1] == T[0] && T[T.length() - 1] == U[0])
	cout << "YES" << endl;
	else
		cout << "NO" << endl;


	return 0;

}



Measured memory_bytes: 256
n = int(input())
p = list(map(int, input().split()))
p1 = sorted(p)
c = 0
ans = 'YES'
for i in range(n):
    if p[i] != p1[i]:
        c += 1
    if c > 2:
        ans = 'NO'
        break
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
using namespace std;
//Xか＋のみ考えればよい
int main(){
	int A[3];cin >> A[0] >> A[1] >> A[2];
	int K,memo = 0;cin >>K;
	for (int i = 0;i<3;i++){
		for (int j = 0;j<3;j++){
			if (j >= i and A[j] >= A[i]){
				memo = A[i];
				A[i] = A[j];
				A[j] = memo;
			}
		}
	}
	for (int j = 0;j<K;j++){
		A[0] *= 2;
	}
	cout << A[0]+A[1]+A[2] <<endl;
}

Measured memory_bytes: 256
s = input()[::-1]
while True:
    if len(s) == 0:
        print ("YES")
        exit ()

    if s[0:5] == "maerd" or s[0:5] == "esare":
        s = s[5:]
    else:
        if s[0:6] == "resare":
            s = s[6:]
        else:
            if s[0:7] == "remaerd":
                s = s[7:]
            else:
                print ("NO")
                exit ()


Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;

void solve(){
  long double a, b; cin >> a >> b;
  ll ans = a * b;
  cout << ans << endl;
  return;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 3796
// #define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <locale>
#include <cctype>
#include <sstream>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef map<int, int> MAPII;
typedef map<double, int> MAPDI;
typedef vector<pair<int, int> > VPII;
typedef multimap<int, string, greater<int> > MuMAPIS;

#define MP make_pair
#define fastIO	cin.tie(0); ios::sync_with_stdio(false);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
//for gcc (未test)
// #define FOREACH_IT(it,c)	for(typeof(c)::iterator it=(c).begin(); it!=(c).end(); ++it)
//for Visual Studio
#define foreach_it(type,it,c) for(type::iterator it=c.begin(), c_end=c.end(); it!=c_end; ++it)

// ------------------- include, typedef, define END. -------------------

double BMI(int h, int w){
	// h/100 ではダメ, h/100.0 って書く.
	double ret = w / pow(h / 100.0, 2.0);
	return ret;
}

void solve(map<double, int> &bmiList){
	foreach_it(MAPDI, it, bmiList){
		cout << (*it).second << endl;
		break;
	}
}

int main(){
	fastIO;
	int n = 0;
	while (cin >> n,n){
		int i = 0, h = 0, w = 0;
		map<double, int> bmiList;
		while (n--){
			cin >> i >> h >> w;
			bmiList.insert(MP(abs(22.00 - BMI(h, w)), i));
		}
		solve(bmiList);
	}
	return 0;
}

Measured memory_bytes: 1264
n=int(input())
tbl=[[0 for j in range(10)] for i in range(10)]
for i in range(1,n+1):
  s=str(i)
  h=int(s[0])
  b=int(s[-1])
  tbl[h][b]+=1
ans=0
for i in range(10):
  for j in range(10):
    ans+=tbl[i][j]*tbl[j][i]
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

	int N; cin >> N;
	vi p(N); rep(i,N) cin >> p[i];
	
	vi maxi(N,0); int ma = INF;
	rep(i,N) {
		chmin(ma,p[i]);
		maxi[i] = ma;
	}

	int ans = 0;
	rep(i,N) {
		if(maxi[i] == p[i]) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  [a, b, c, k] <- getIntList
  let ans | k <= (a + b) = min a k
          | otherwise = a - (k - (a + b))
  print ans


Measured memory_bytes: 3756
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define mp make_pair
#define pb push_back
const int N=705;
vector<int> E[N];
set<pair<int,int> > has;
vector<pair<int,int> > sz;
int cnt[2];
int was[N];
bool bad;
void DFS(int u)
{
	cnt[was[u]]++;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(was[v]==-1) was[v]=was[u]^1,DFS(v);
		else
		{
			if(was[u]==was[v]) bad=1;//,printf("(%i %i)\n",u,v);
		}
	}
}
bool dp[N][N];
int main()
{
	int u,v,n,m,i,j;
	scanf("%i %i",&n,&m);
	while(m--) scanf("%i %i",&u,&v),has.insert(mp(u,v)),has.insert(mp(v,u));
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			if(!has.count(mp(i,j)))
			{
				E[i].pb(j);
				E[j].pb(i);
				//printf("->%i %i\n",i,j);
			}
		}
	}
	sz.pb(mp(-1,-1));
	for(i=1;i<=n;i++) was[i]=-1;
	for(i=1;i<=n;i++) if(was[i]==-1)
	{
		cnt[0]=cnt[1]=0;
		was[i]=1;DFS(i);
		sz.pb(mp(cnt[0],cnt[1]));
	}
	if(bad) return printf("-1\n"),0;
	int goal=n/2;
	dp[0][0]=1;
	for(i=1;i<sz.size();i++)
	{
		for(j=0;j<=goal;j++)
		{
			dp[i][j]=(j>=sz[i].first?dp[i-1][j-sz[i].first]:0)|(j>=sz[i].second?dp[i-1][j-sz[i].second]:0);
		}
	}
	int ans=0;
	for(i=0;i<=goal;i++) if(dp[sz.size()-1][i]) ans=i;
	int ret=n-ans;
	int out=ans*(ans-1)/2+ret*(ret-1)/2;
	printf("%i\n",out);
	return 0;
}

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

int main( ){
  string name,cp,sirei,p;
  int q,a,b,na;
  cin>>name>>q;
  na=(int)name.size();
  for(int i=0;i<q;i++){
    cin>>sirei;
    if(sirei=="print"){
      cin>>a>>b;
      cout<<name.substr(a,b-a+1)<<endl;
    }
    if(sirei=="reverse"){
      cin>>a>>b;
      cp=name.substr(a,b-a+1);
      na=cp.size();
      for(int i=0;i<na;i++)name[i+a]=cp[na-i-1];
    }
    if(sirei=="replace"){
      cin>>a>>b>>p;
      name=name.replace(a,b-a+1,p);
    }
  }
  return 0;
}

Measured memory_bytes: 3204
N,Q=map(int,input().split())
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
data=[0 for i in range(N+1)]
visited=[False for i in range(N+1)]
for i in range(Q):
    p,x=map(int,input().split())
    data[p]+=x
    
from collections import deque
d=deque()
e=deque()
visited[1]=True
d.append(1)
while d:
    while d:
        x=d.popleft()
        adder=data[x]
        for node in graph[x]:
            if visited[node]==False:
                visited[node]=True
                data[node]+=adder
                e.append(node)
            else:
                pass
    if e:
        d=e
        e=deque()
print(*data[1:])


Measured memory_bytes: 58148
#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.setf(ios::fixed); cout.precision(20);
    int n, m; cin >> n >> m;
    string s; cin >> s;
    reverse(s.begin(), s.end());
    deque<int> dq;
    for (int i = 0;;) {
        if (i == n) {
            for (int x : dq) {
                cout << x << " ";
            }
            cout << "\n";
            exit(0);
        }
        int j = i;
        int mx = i;
        while (j + 1 <= i + m && j + 1 <= n) {
            j++;
            if (s[j] == '0') {
                mx = j;
            }
        }
        if (mx == i) {
            cout << "-1\n";
            exit(0);
        }
        dq.push_front(mx - i);
        i = mx;
    }
}


Measured memory_bytes: 976
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x)          (x).begin(), (x).end()
#define rep(i, n)       for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t)   for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t)   for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...)  Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64  sigma(i64 n)            { return (n * (n + 1) >> 1); }
inline i64  updiv(i64 a, i64 b)     { return (a + b - 1) / b; }
inline i64  sqr(i64 n)              { return n * n; }
inline string to_string(char c)     { return string(1, c); }
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

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

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

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

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

template <typename Func>
struct FixPoint : Func {
    inline constexpr FixPoint(Func &&f) noexcept : Func(forward<Func>(f)) {}

    template <typename... Args>
    inline decltype(auto) operator()(Args &&... args) const {
        return Func::operator()(*this, forward<Args>(args)...);
    }
};

template< typename Func >
inline decltype(auto) makeFixPoint(Func &&f) {
    return FixPoint< Func >{forward< Func >(f)};
}
// }}} End Header

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

    var(int, N);
    vector<i64> a(N);
    vector<i64> sum(N + 1);

    rep(i, N) {
        input(a[i]);
    }
    sort(all(a));

    rep(i, N) {
        sum[i + 1] = sum[i] + a[i];
    }

    trace(a);
    trace(sum);

    i64 ans = 1;
    repr(i, N-2, 0) {
        if (sum[i+1] * 2 >= a[i+1]) {
            ++ans;
        } else {
            break;
        }
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 1792
using System;
using System.Linq;
namespace ABC150B
{
    public class MainClass
    {
        public static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            Console.WriteLine(s.Replace("ABC", "0").Where(c => c == '0').Count());
        }
    }
}


Measured memory_bytes: 11220
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    val trains = (0 until n - 1).map { SpecialTrain(sc.next().toInt(), sc.next().toInt(), sc.next().toInt()) }
    println(problem084c(n, trains))
}

fun problem084c(n: Int, trains: List<SpecialTrain>): String {
    val ans = mutableListOf<Int>()
    for (i in 0 until n - 1) {
        var time = 0
        for (j in i until n - 1) {
            val tn = trains[j]
            time += if (time <= tn.s) {
                tn.s - time + tn.c
            } else {
                var wait = tn.s
                while (wait < time) {
                    wait += tn.f
                    when {
                        wait + tn.f * 950000 < time -> wait += +tn.f * 950000
                        wait + tn.f * 900000 < time -> wait += +tn.f * 900000
                        wait + tn.f * 800000 < time -> wait += +tn.f * 800000
                        wait + tn.f * 500000 < time -> wait += +tn.f * 500000
                        wait + tn.f * 100000 < time -> wait += +tn.f * 100000
                        wait + tn.f * 50000 < time -> wait += +tn.f * 50000
                        wait + tn.f * 10000 < time -> wait += +tn.f * 10000
                        wait + tn.f * 5000 < time -> wait += +tn.f * 5000
                        wait + tn.f * 1000 < time -> wait += +tn.f * 1000
                        wait + tn.f * 500 < time -> wait += +tn.f * 500
                        wait + tn.f * 100 < time -> wait += +tn.f * 100
                    }
                }
                wait % time + tn.c
            }
        }
        ans.add(time)
    }
    return ans.joinToString("\n") + "\n0"
}

data class SpecialTrain(var c: Int, var s: Int, var f: Int)

Measured memory_bytes: 31748