akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
//import java.math.BigInteger;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] a = new int[4];
        a[0] = Character.getNumericValue(str.charAt(0));
        a[1] = Character.getNumericValue(str.charAt(1));
        a[2] = Character.getNumericValue(str.charAt(2));
        a[3] = Character.getNumericValue(str.charAt(3));
        int I = 4;
        boolean test = true; 
        //int[] m = new int[N];
        int ans = a[0]+a[1]+a[2]+a[3];
        int ans2 = ans;
        if((a[0]+a[1]+a[2]+a[3])==7){
            System.out.println(a[0]+"+"+a[1]+"+"+a[2]+"+"+a[3]+"=7");
        }else if((a[0]-a[1]+a[2]+a[3])==7){
            System.out.println(a[0]+"-"+a[1]+"+"+a[2]+"+"+a[3]+"=7");
        }else if((a[0]+a[1]-a[2]+a[3])==7){
            System.out.println(a[0]+"+"+a[1]+"-"+a[2]+"+"+a[3]+"=7");
        }else if((a[0]+a[1]+a[2]-a[3])==7){
            System.out.println(a[0]+"+"+a[1]+"+"+a[2]+"-"+a[3]+"=7");
        }else if((a[0]-a[1]-a[2]+a[3])==7){
            System.out.println(a[0]+"-"+a[1]+"-"+a[2]+"+"+a[3]+"=7");
        }else if((a[0]-a[1]+a[2]-a[3])==7){
            System.out.println(a[0]+"-"+a[1]+"+"+a[2]+"-"+a[3]+"=7");
        }else if((a[0]+a[1]-a[2]-a[3])==7){
            System.out.println(a[0]+"+"+a[1]+"-"+a[2]+"-"+a[3]+"=7");
        }else if((a[0]-a[1]-a[2]-a[3])==7){
            System.out.println(a[0]+"-"+a[1]+"-"+a[2]+"-"+a[3]+"=7");
        }
        //System.out.println(a[0]);
    }
}


Measured memory_bytes: 39444
macro_rules! input {
    ($ttype:ty) => {
        {
            let mut input = String::new();
            let _= std::io::stdin().read_line(&mut input);
            input.trim().parse::<$ttype>().unwrap()
        }
    };

    ($($ttype:ty),*) => {
        {
            use std::io::BufRead;
            let mut input = String::new();
            let stdin = std::io::stdin();
            let _ = stdin.lock().read_line(&mut input);
            let mut iter = input.trim().split_whitespace();
            (
                $(iter.next().unwrap().parse::<$ttype>().unwrap(),)*
            )
        }
    };

    ($ttype:ty; $x:expr) => {
        {
            use std::io::BufRead;
            let mut input = String::new();
            let stdin = std::io::stdin();
            let _ = stdin.lock().read_line(&mut input);
            let v: Vec<$ttype> = input
                .trim()
                .split_whitespace()
                .map(|x| x.parse().unwrap())
                .collect();
            v
        }
    };

    ($ttype:ty; $x:expr; $y:expr) => {
        {
            use std::io::BufRead;
            let mut matrix = Vec::with_capacity($y);
            for _ in 0..$y {
                let mut input = String::new();
                let stdin = std::io::stdin();
                let _ = stdin.lock().read_line(&mut input);
                let v: Vec<$ttype> = input
                    .trim()
                    .split_whitespace()
                    .map(|x| x.parse().unwrap())
                    .collect();
                matrix.push(v);
            }
            matrix
        }
    };
}

fn main() {
    let (n, k) = input!(i64, i64);
    let a_list = input!(i64; n);

    if (n - k) % (k - 1) == 0 {
        println!("{}", (n - k) / (k - 1) + 1);
    } else {
        println!("{}", (n - k) / (k - 1) + 2);
    }
}

Measured memory_bytes: 6396
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
cnt_plus=0
cnt_zero=0
cnt_minus=0
arr_plus=[]
arr_minus=[]

for i in range(n):
    if arr[i]>0:
        cnt_plus+=1
        arr_plus.append(arr[i])
    elif arr[i]<0:
        cnt_minus+=1
        arr_minus.append(-arr[i])
    else:
        cnt_zero+=1
if cnt_plus+cnt_minus<k: #K個の積の中に0を含む場合、答えは0
    print(0)
    exit()
    
if k==n: #K=Nの場合
    if cnt_zero!=0: #0がひとつでもあれば答えは0
        print(0)
    else:
        ans=1
        for i in range(cnt_plus):
            ans*=arr_plus[i]
            ans%=mod
        for i in range(cnt_minus):
            ans*=arr_minus[i]
            ans%=mod
        if cnt_minus%2==0: #負の数が偶数個であれば積は正
            print(ans)
        else: #そうでなければ積は負となる
            print((-ans)%mod)
    exit()
if cnt_plus==0 and k%2==1: #正の数がないとき
    if cnt_zero!=0: #0がひとつでもあれば答えは0にできる
        print(0)
    else: #0がないときは負の数を絶対値が小さい順に掛けるのが最善
        arr_minus=sorted(arr_minus)
        tmp=1
        for i in range(k):
            tmp*=arr_minus[i]
            tmp%=mod
        print((-tmp)%mod)
    exit()
else: #正の数と負の数から合計K個取れるとき
    arr_plus=sorted(arr_plus,reverse=True)
    arr_minus=sorted(arr_minus,reverse=True)
    if k%2==0: #Kが偶数であれば何もしない
        ans=1
        pos_plus=0
        pos_minus=0
        cnt=0
    else: #Kが奇数であれば正の数から最大のものを取っておき、Kが偶数の場合に帰着させる
        ans=arr_plus[0]
        pos_plus=1
        pos_minus=0
        cnt=1
    while cnt<k:
        cand1=0
        if pos_plus<=cnt_plus-2: #正の数を2つ取れるなら取る
            cand1=arr_plus[pos_plus]*arr_plus[pos_plus+1]      
            cand2=0
        if pos_minus<=cnt_minus-2: #負の数を2つ取れるなら取る:
            cand2=arr_minus[pos_minus]*arr_minus[pos_minus+1]
        if cand1>=cand2: #正の数を2つ取った積のほうが大きい場合
            pos_plus+=2
            ans*=cand1
            ans%=mod
        else: #負の数を2つ取った積のほうが大きい場合
            pos_minus+=2
            ans*=cand2
            ans%=mod
        cnt+=2
    print(ans)
    exit()


Measured memory_bytes: 31720
#include<bits/stdc++.h>
using namespace std;
long int dp[3001][3001];
int main(){
  int n;
  cin>>n;
  long long int a[n];
  for(int i=0;i<n;i++)
  cin>>a[i];
  memset(dp,0,sizeof dp);
  int i=0,j=0;
  while(i<n&&j<n){
      if(i==j){
      dp[i][j]=a[i];
      i++;j++;
      }
    }
    i=0;j=1;
    while(i<n&&j<n){
        if(j==i+1){
        dp[i][j]=max(a[i],a[j]);
        i++;
        j++;
        }
    }
    i=0;j=0;
    for(int k=2;k<n;k++){
        i=0;j=i+k;
        while(i<n&&j<n){
            if(j==i+k)
            dp[i][j]=max(a[j]+min(dp[i][j-2],dp[i+1][j-1]),a[i]+min(dp[i+1][j-1],dp[i+2][j]));
            i++;j++;
        }
    }
    cout<<dp[0][n-1]-min(dp[0][n-2],dp[1][n-1]);
}

Measured memory_bytes: 73996
package main

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

func wordScanner() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}

func get_int(sc *bufio.Scanner) int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func get_string(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func main() {
	var h, w int
	sc := wordScanner()
	h = get_int(sc)
	w = get_int(sc)
	ss := make([]string, h)
	for i := range ss {
		ss[i] = get_string(sc)
	}

	xss := make([][]int, h)
	for i := range xss {
		xss[i] = make([]int, w)
	}

	for i := 0; i < h; i++ {
		from := 0
		for from < w {
			if ss[i][from] == '#' {
				from++
			} else {
				to := from
				for to < w && ss[i][to] != '#' {
					to++
				}
				for j := from; j < to; j++ {
					xss[i][j] = to - from
				}
				from = to
			}
		}
	}

	for j := 0; j < w; j++ {
		from := 0
		for from < h {
			if ss[from][j] == '#' {
				from++
			} else {
				to := from
				for to < h && ss[to][j] != '#' {
					to++
				}
				for i := from; i < to; i++ {
					xss[i][j] += to - from
				}
				from = to
			}
		}
	}

	ans := 0
	for _, xs := range xss {
		for _, x := range xs {
			if ans < x {
				ans = x
			}
		}
	}
	fmt.Println(ans - 1)
}


Measured memory_bytes: 38144
#include<stdio.h>
int gcd(int x,int y){
	int r,tmp;
	if(x<y){
		tmp=x;
		x=y;
		y=tmp;
	}
	r=x%y;
	while(r!=0){
		x=y;
		y=r;
		r=x%y;
	}
	return y;
}
int main(void){
	int x,y,r;
	scanf("%d",&x);
	scanf("%d",&y);
	r=gcd(x,y);
	printf("%d\n",r);
	return 0;
}


Measured memory_bytes: 2044
#include<cstdio>
#include<iostream>
using namespace std;
int n, c, num[5][1005], C[1005][1005], d[1005][1005];
int calc (int x, int y, int z) {
	int sum = 0;
	for (int j = 1; j <= c; j++)
		sum += d[j][x] * num[0][j] + d[j][y] * num[1][j] + d[j][z] * num[2][j];
	return sum;
}
int main() {
	cin >> n >> c;
	for (int i = 1; i <= c; i++)
		for (int j = 1; j <= c; j++)
			cin >> d[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			cin >> C[i][j];
			num[ (i + j) % 3][C[i][j]]++;
		}
	int ans = 0x7fffffff;
	for (int i = 1; i <= c; i++)
		for (int j = 1; j <= c; j++)
			for (int k = 1; k <= c; k++) {
				if (i == j || k == j || i == k) continue;
				ans = min (ans, calc (i, j, k));
			}
	cout << ans << endl;
}

Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
int main(void){
  int n; cin>>n;
  vector<int> a(n);
  for(auto& i:a) cin>>i;
  int res=0,m=1;
  for(int i=0; i<n; ++i){
    if(a[i]==m) ++m;
    else ++res;
  }
  if(m==1) res=-1;
  cout<<res;
  return 0;
}


Measured memory_bytes: 4048
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6 + 10;
bool vis[N];
vector<ll> prime;
ll factor[20], cntp, a, b;

void get_prime()
{
    memset(vis,0, sizeof(vis));
    for(ll i = 2; i <= N; ++i){
        if(!vis[i]) prime.push_back(i);
    for(ll p : prime){
        if(i * p > N) break;
        vis[i * p] = true;
        if(i % p == 0) break;
    }
    }
}

ll gcd(ll a, ll b)
{
    return !b ? a : gcd(b, a % b);
}

void get_factor(ll n)
{
    memset(factor, 0, sizeof(factor));
    ll fac = 1;
    for(ll p : prime){
        fac = 1;
        if(n % p == 0){
            while(n % p == 0){
                n /= p;
                fac *= p;
            }
            ++cntp;
            factor[cntp] = fac;
        }
    }
    if(n > 1) factor[++cntp] = n;
}


int main()
{
    get_prime();
    cin >> a >> b;
    ll m = gcd(a, b);
    get_factor(m);
    cout << cntp + 1 <<  '\n';
    return 0;
}

Measured memory_bytes: 5144
#include <bits/stdc++.h> 
#include <time.h>
#define F(i,a,b) for(long long i=a;i<=(b);++i)
#define dF(i,a,b) for(long long i=a;i>=(b);--i) 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-10
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 2e5+10; 
const int N = 1e5+10;
const int E = 1e6+10;  
ll n,k,p,h,w;
ll a[maxn];

int main(){
	cin>>n;
	ll mii=inf;
	ll sum = 0;
	F(i,1,n){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	if(n%2==0){
		sum+=a[n];
		dF(i,n-1,n/2+1){
			sum += 2*a[i];
		}
	}
	else{
		sum+= a[n]+a[n/2+1];
		dF(i,n-1,n/2+2){
			sum+=2*a[i];
		}
	}
	cout<<sum<<endl;
}


Measured memory_bytes: 5200
#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    int k, s;
    cin >> k >> s;

    int r = 0;
    REP(i, k+1) {
        REP(j, k+1) {
            if (i + j > s) break;
            else if (s - i - j <= k) r++;
        }
    }

    cout << r << endl;
}


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

int main(){
  int N;
  cin>>N;
  int a[N];
  int b[N-1];
  for (int i=0;i<N-1;i++){
    cin>>b[i];
  }
  
  for (int i=0;i<N;i++){
    a[i]=0;
  }
  a[0]=b[0];
  a[1]=b[0];
  for (int i=1;i<N-1;i++){
    if(a[i]>b[i]){
      a[i]=b[i];
    }
    a[i+1]=b[i];
  }
  int sum=0;
  for (int i=0;i<N;i++){
    //cout<<a[i]<<endl;
    sum=sum+a[i];
  }
  cout<<sum<<endl;
  return 0;
}

Measured memory_bytes: 256
/** 
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

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

typedef long long ll;
#define endl "\n"
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }

typedef pair<int, int> pii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;

int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
    cini(n);
    cini(k);
    cins(s);

    int cnt=1;
    char curSeg=s[0];
    for(int i=1; i<n; i++) {
        if(curSeg!=s[i])
            cnt++;
        curSeg=s[i];
    }

/* Number of happy person is sum(len_of_seg-1) for all segments.
 * Three kinds of operations:
 * 1. Reverse two consecutive segments of same length in on op. This will in fact
 * remove them, hence increase the number of h-people by 2
 * 2. Reverse the first+second segment, increses number of h-people by 1.
 */

    int ans=n-cnt;
    while(k && cnt>2) {
        k--;
        ans+=2;
        cnt-=2;
    }
    while(k && cnt>1) {
        k--;
        ans++;
        cnt--;
    }

    cout<<ans<<endl;

}



Measured memory_bytes: 512
/*Author:Copyrights: S7a2a7d 
 Hardwork can always beat talent */

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define pb push_back
#define ll long long
#define rep(i,n)  for(ll i=0;i<n;i++)
#define repi(i,n)  for(ll i=1;i<=n;i++)
#define mem(arr,x) memset(arr,x,sizeof(arr))
     
#define mp make_pair
#define ff first
#define ss second
     
 const double PI = 3.1415926535897932;
 const int mod = 1e9 + 7;  
 const int inf = 1e9 + 5;
ll lcm(ll a,ll b)
{
        return (a*b)/__gcd(a,b);
}
int gcd(int a, int b) 
{ 
    if (b == 0) 
        return a; 
    return gcd(b, a % b); 
} 
int max(int a,int b)
{
        if(a<b)
        return b;
        return a;
}

int main()
{
    fast_io;
    int T=1;
    //cin>>T;
    while(T--)
    {    
       ll n;
       cin>>n;
       int a[n];
       rep(i,n)
       cin>>a[i];
       vector<ll int>sums(n+1,0);
       for(int i=0;i<n;i++)
       {
          sums[i+1]=(sums[i]+a[i]);
       }
       ll ans=0;
       for(int i=0;i<n;i++)
       {
          ll req=(sums[n]-sums[i+1])%mod;
          ans=ans+(ll)(a[i]*req);
          ans=ans%mod;
       }
        cout<<ans<<'\n';
    }
            
   
 }

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

int main() {
  int D;
  cin >> D;
  if (D == 22) {
    cout << "Christmas Eve Eve Eve" << endl;
  } else if (D == 23) {
    cout << "Christmas Eve Eve" << endl;
  } else if (D == 24) {
    cout << "Christmas Eve" << endl;
  } else {
    cout << "Christmas" << endl;
  }
}


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

using namespace std;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
        char c = s[i];
        bool f;
        if (c == 'c') {
            f = false;
        } else if (c == 'a') {
            if (x+y < a+b) {
                f = true;
                x++;
            } else {
                f = false;
            }
        } else {
            if (x+y < a+b && y < b) {
                f = true;
                y++;
            } else {
                f = false;
            }
        }
        if (f) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
}

Measured memory_bytes: 896
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
#include <bitset> // bitset
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

int main() {
    string S, T;
    cin >> S >> T;
    int N = S.size();
    int n = T.size();
    int ans = n;
    for (int i = 0; i <= N - n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (S[i + j] != T[j]) {
                count++;
            }
        }
        if (ans > count) {
            ans = count;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3624
INF = 10 ** 9
N = int(input())
p = list(map(int, input().split()))
cnt = 1
minlst = [INF] * N
minlst[0] = p[0]
for i in range(1, N):
    minlst[i] = min(minlst[i - 1], p[i])

for i in range(1, N):
    if minlst[i] >= p[i]:
        cnt += 1

print(cnt)

Measured memory_bytes: 26012
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define reg register
#define M 200005
char s[M];
char t[M];
int n,m;
int Min[M][26];
LL Ans=0;
int main() {
	memset(Min,-1,sizeof(Min));
	scanf("%s%s",s+1,t+1);
	n=strlen(s+1),m=strlen(t+1);
	for(int i=n+1; i<=n*2; ++i)
		s[i]=s[i-n];
	for(int i=n*2; i>=0; --i) {
		if(i)Min[i][s[i]-'a']=i;
		for(int j=0; j<26; ++j)
			if(j!=s[i]-'a')Min[i][j]=Min[i+1][j];
	}
	int Now=0;
	for(int i=1; i<=m; ++i) {
		if(Min[Now+1][t[i]-'a']==-1){
			puts("-1");
			return 0;
		}
		Ans+=Min[Now+1][t[i]-'a']-Now;
		Now=Min[Now+1][t[i]-'a'];
		if(Now>n)Now-=n;
	}
	printf("%lld",Ans);
}

Measured memory_bytes: 20992
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace at
{
    class Program
    {
        static void Main(string[] args)
        {
            var seconds = int.Parse(Console.ReadLine());

            // TimeSpanのインスタンスを生成。時分は0でOK
            var span = new TimeSpan(0, 0, seconds);

            // フォーマットする
            var hhmmss = span.ToString(@"h\:m\:s");

            Console.WriteLine(hhmmss);  // 14:50:21
        }
    }
}



Measured memory_bytes: 18060
#include <bits/stdc++.h>
using namespace std;
#define sz(x) int(x.size())
#define rep(i,n) for (int i=0; i<(n); ++i)
using ll = long long;
const int INF = 1001001001;
const int mod = 1000000007;

int main(){
    int k;
    cin >> k;
    int l[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

    cout << l[k-1];

}

Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

using PI = P<int, int>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vll d(n);
    for (int i = 0; i < n; i++) cin >> d[i];
    V< V<PI> > edges(n);
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        a--, b--;
        edges[a].emplace_back(b, i), edges[b].emplace_back(a, i);
    }

    V< V<int> > ngh(n);
    vll ans(m, HIGHINF);
    bool ok = true;
    for (int i = 0; i < n; i++) {
        bool ok2 = false;
        ll mind = HIGHINF;
        PI minto;
        for (PI e: edges[i]) {
            if (d[i] >= d[e.first]) {
                ok2 = true;
                if (chmin(mind, d[e.first])) minto = e;
            }
        }
        ok &= ok2;
        ngh[i].emplace_back(minto.first), ngh[minto.first].emplace_back(i);
        ans[minto.second] = d[i];
    }

    if (!ok) {
        cout << -1 << '\n';
        return 0;
    }

    V<int> col(n, -1);
    for (int i = 0; i < n; i++) {
        if (col[i] != -1) continue;
        col[i] = 0;
        queue<int> que; que.push(i);
        while (!que.empty()) {
            int q = que.front(); que.pop();
            for (int e: ngh[q]) {
                if (col[e] != -1) continue;
                col[e] = col[q] ^ 1;
                que.push(e);
            }
        }
    }

    for (int i = 0; i < n; i++) cout << (col[i] == 0 ? 'B' : 'W');
    cout << '\n';
    for (int i = 0; i < m; i++) cout << min(ll(INF), ans[i]) << '\n';
    return 0;
}


Measured memory_bytes: 19760
# coding: utf-8

n, m = map(int, raw_input().split());

ans = 0;

for i in range(n):
    nums = map(int, raw_input().split());
    cnt = 0;
    for num in nums:
        if num == 1:
            cnt = cnt + 1;
            ans = max(ans,cnt);
print ans;

Measured memory_bytes: 6448
#include<iostream>
#include<string>
using namespace std;
struct Dice
{
    int s[6];
    void roll(char c)
    {


    int b;
    if(c=='E')
    {
        b=s[0];
        s[0]=s[3];
        s[3]=s[5];
        s[5]=s[2];
        s[2]=b;
    }
    if(c=='W')
    {
        b=s[0];
        s[0]=s[2];
        s[2]=s[5];
        s[5]=s[3];
        s[3]=b;
    }
    if(c=='N')
    {
        b=s[0];
        s[0]=s[1];
        s[1]=s[5];
        s[5]=s[4];
        s[4]=b;
    }
    if(c=='S')
    {
        b=s[0];
        s[0]=s[4];
        s[4]=s[5];
        s[5]=s[1];
        s[1]=b;
    }
    if(c=='R')//这是什么鬼东西，怎么还有往右的
    {
        b=s[1];
        s[1]=s[2];
        s[2]=s[4];
        s[4]=s[3];
        s[3]=b;   
    }
    }
    int top()
    {
        return s[0];
    }
    int right()
    {
        return s[2];
    }
    int left()
    {
        return s[3];
    }
    int front ()
    {
        return s[1];
    }
};
int main()
{
    Dice d;
    for(int i=0;i<6;i++)
        cin>>d.s[i];
   int n;cin>>n;
   while(n--)
   {
       int a,b;
       cin>>a>>b;
       if(d.left()==a) d.roll('E');
       if(d.right()==a) d.roll('W');
      while(d.top()!=a) d.roll('N');
      while(d.front ()!=b) d.roll('R');
      cout <<d.right ()<<endl;
      
       
   }
    return 0;

}



Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
char A[100005],B[100005];
long long a,b,n,ne[100005][30],Ne[30],now,H[30],an,Next;
long long ans;
int main() {
	scanf("%s",A+1);
	scanf("%s",B+1);
	a=strlen(A+1);
	b=strlen(B+1);
	for(int i=1; i<=a; i++) H[A[i]-'a']=1;
	an=0;
	for(int i=1; i<=b; i++) an|=(H[B[i]-'a']==0);
	if(an) return puts("-1"),0;
	for(int i=a; i; i--)Ne[A[i]-'a']=i;
	for(int i=a; i; i--) {
		for(int j=0; j<26; j++) ne[i][j]=Ne[j];
		Ne[A[i]-'a']=i;
	}
	now=Ne[B[1]-'a'],ans=now;
	for(int i=2; i<=b; i++) {
		Next=ne[now][B[i]-'a'];
		ans+=Next<=now?Next-now+a:Next-now;
		now=Next;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 23936
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<endl;
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;
const ll inf=1e15;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin>>n;
  vector<ll> b(n);
  rep(i,n-1) cin>>b[i+1];
  ll ans=0;
  ans=b[1]+b[n-1];
  FOR(i,2,n){
    ans+=min(b[i],b[i-1]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include  <stdio.h>

int main() {
	long long int input;
	long long int i;
	long long int sum = 0;

	scanf("%lld", &input);

	for(i = 1; i <= input; i++) {
		if(i % 3 == 0 || i % 5 == 0) {
			continue;
		} else {
			sum += i;
		}
	}

	printf("%lld\n", sum);
	return 0;
}



Measured memory_bytes: 1736
n=int(input())
X=list(map(int, input().split()))
X1=sorted(X)
mid_1=X1[int(n/2)-1]
mid_2=X1[int(n/2)]
for x in X:
    if x <= mid_1:
        print(mid_2)
    else:
        print(mid_1)

Measured memory_bytes: 25620
n, m = map(int, input().split())
arr_ = [tuple(map(int, input().split())) for _ in range(m)]
one = set([b for a, b in arr_ if a == 1])
last = set([a for a, b in arr_ if b == n])
print("POSSIBLE" if len(one & last) >= 1 else "IMPOSSIBLE")

Measured memory_bytes: 44120
# coding: utf-8

def f(n, k, h):
    dp = [float('inf') for _ in range(n)]
    dp[0] = 0
    for i in range(1, n):
        js = max(i - k, 0)
        dp[i] = min(dp[j] + abs(h[i] - h[j]) \
            for j in range(js, i))
    return(dp[i])

n, k = map(int, input().rstrip().split())    # 2 <= n <= 10^5, 1 <= k <= 100
h = list(map(int, input().rstrip().split()))

print(f(n, k, h))


Measured memory_bytes: 13980
#include <algorithm>
#include<bits/stdc++.h>
#include <ios>
using namespace std;
#define ll long long
#define f(n)  for(int i=0;i<n;i++) 
#define pb push_back
#define mp make_pair
 
 
void speed (){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
 
 int main(){
     speed();
     string s;
     cin>>s;
     int n=s.size();
     int f1=0,f2=0,f3=0;int v=0;
     int p1=0;int p2=((n-1)/2)-1;
     while(p1<p2){
         if(s[p1]==s[p2]){
             p1++;p2--;
         }else{
             f1=1;break;}
     }if(f1==0){v++;}
     int i=((n+3)/2)-1,j=n-1;
     while(i<j){
          if(s[i]==s[j]){
             i++;j--;
         }else{
             f2=1;break;}
     }if(f2==0){v++;}
   int d1=0,d2=n-1;
   while(d1<d2){
     if(s[d1]==s[d2]){d1++;d2--;}
     else{f3=1;break;}}
   if(f3==0){v++;}
     if(v==3){cout<<"Yes";}
     else{cout<<"No";}
 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;
typedef pair<int,int> pi;

const int N=2005;

int n,a[N],b[N],s1,s2,las[N],nex[N],ans;
char s[N];
int m,w,mx[N];
pi lim[N];

bool cmp(const pi&a,const pi&b){return a.fi>b.fi||a.fi==b.fi&&a.se<b.se;}
int ABS(int x){return x<0?-x:x;}
int calc(int l,int r,int p){
	if(l>r)r=l;
	if(p<l)l=p;if(p>r)r=p;
	if(l>0)l=0;if(r<0)r=0;
	return 2*(r-l)-ABS(p);
}

int main(){
	scanf("%s",s);n=strlen(s);ans=n<<1;
	for(int i=0;i<n;i++)a[i]=s[i]&1,s1+=a[i];
	scanf("%s",s);
	for(int i=0;i<n;i++)b[i]=s[i]&1,s2+=b[i];
	if(!s2)puts(s1?"-1":"0"),exit(0);
	for(int i=0;i<n;i++){
		while(!b[(n+i-las[i])%n])las[i]++;
		while(!b[(i+nex[i])%n])nex[i]++;
	}
	for(int i=-n+1;i<=n-1;i++){
		m=w=0;
		for(int j=0,t=(n+i)%n;j<n;j++,(++t<n?:t=0))if(a[j]^b[t]){
			w++;
			if(!b[t])lim[m++]={i-las[t],i+nex[t]};
		}
		if(w+ABS(i)>=ans)continue;
		if(!m)ans=min(ans,w+ABS(i));
		else{
			sort(lim,lim+m,cmp);
			mx[m]=i;
			for(int k=m;k>=1;k--)mx[k-1]=max(mx[k],lim[k-1].se);
			ans=min(ans,w+calc(i,mx[0],i));
			for(int k=0;k<m;k++)
				ans=min(ans,w+calc(lim[k].fi,mx[k+1],i));
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.Map.Entry;
import java.util.HashMap;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		ProblemC solver = new ProblemC();
		solver.solve(1, in, out);
		out.close();
	}

	static class ProblemC {
		public void solve(int testNumber, FastScanner in, PrintWriter out) {
			int n = in.nextInt();
			char[] s = in.next().toCharArray();
			char[] t = new char[n];
			Map<String, Integer>[] m1 = new Map[n + 1];
			Map<String, Integer>[] m2 = new Map[n + 1];
			for (int i = 0; i < m1.length; i++) {
				m1[i] = new HashMap<>();
				m2[i] = new HashMap<>();
			}
			for (int mask = 0; mask < 1 << n; mask++) {
				int l = 0;
				int r = n - 1;
				for (int i = 0; i < n; i++) {
					if ((mask & (1 << i)) == 0) {
						t[l++] = s[i];
					} else {
						t[r--] = s[i];
					}
				}
				add(m1[Integer.bitCount(mask)], new String(t));
			}
			for (int mask = 0; mask < 1 << n; mask++) {
				int l = 0;
				int r = n - 1;
				for (int i = n - 1; i >= 0; i--) {
					if ((mask & (1 << i)) != 0) {
						t[l++] = s[n + i];
					} else {
						t[r--] = s[n + i];
					}
				}
				add(m2[Integer.bitCount(mask)], new String(t));
			}
			long ans = 0;
			for (int i = 0; i <= n; i++) {
				for (Map.Entry<String, Integer> e : m1[i].entrySet()) {
					Integer v = m2[n - i].get(e.getKey());
					if (v != null) {
						ans += (long) e.getValue() * v;
					}
				}
			}
			out.println(ans);
		}

		private void add(Map<String, Integer> m, String k) {
			Integer v = m.get(k);
			if (v == null) {
				v = 0;
			}
			m.put(k, v + 1);
		}

	}

	static class FastScanner {
		private BufferedReader in;
		private StringTokenizer st;

		public FastScanner(InputStream stream) {
			in = new BufferedReader(new InputStreamReader(stream));
		}

		public String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					String rl = in.readLine();
					if (rl == null) {
						return null;
					}
					st = new StringTokenizer(rl);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return st.nextToken();
		}

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

	}
}



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

int main(void) {
	int a, b, c;
	cin >> a >> b >> c;
	if (a <= b && b <= c) {
		cout << a << " " << b << " " << c << endl;
	}
	else if (a >= b && b >= c) {
		cout << c << " " << b << " " << a << endl;
	}
	else if (a <= b && b >= c && a <= c) {
		cout << a << " " << c << " " << b << endl;
	}
	else if (a >= b&& b <= c && a >= c) {
		cout << b << " " << c << " " << a << endl;
	}
	else if (a >= b && b <= c && a <= c) {
		cout << b << " " << a << " " << c << endl;
	}
	else if (a<b && b>=c && a >= c) {
		cout << c << " " << a << " " << b << endl;
	}
	return		0;
}

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

using ll = long long;

const int N = 2e5 + 5;
 
int n;
long long f[N];
pair <int, int> a[N];
 
struct FenwickTree {
    long long bit[N];
    void init(){
        memset(bit, 0, sizeof bit);
    }
    
    void update (int x, long long val) {
        for (int i = x; i < N; i += i & -i) bit[i] = max(bit[i], val);
    }
    
    long long query (int x) {
        long long ans = 0;
        for (int i = x; i > 0; i -= i & -i) ans = max(ans, bit[i]);
        return ans;
    }
} fw;
 
int main()
{
   
    cin >> n; fw.init();
    for (int i = 1; i <= n; i++) cin >> a[i].first;
    for (int i = 1; i <= n; i++) cin >> a[i].second;
    for (int i = 1; i <= n; i++) f[i] = a[i].second;
    for (int i = 1; i <= n; i++) {
        f[i] = max(f[i], fw.query(a[i].first - 1) + a[i].second);
        fw.update(a[i].first, f[i]);
    }
    
    cout << *max_element(f + 1, f + n + 1);
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
long int n,q;
vector<long int> a[200001];
long long int vis[200001]={0};
long long int d[200001]={0};
void dfs(long int x)
{
    for(long int i=0;i<a[x].size();i++)
    {
        if(vis[a[x][i]]==0)
        {
            d[a[x][i]]+=d[x];
            vis[a[x][i]]=1;
            dfs(a[x][i]);
        }
    }
}
int main()
{
   cin>>n>>q;
   for(long int i=0;i<n-1;i++)
   {
       long int b,c;
       cin>>b>>c;
       a[b].push_back(c);
       a[c].push_back(b);
   }
   for(long int i=0;i<q;i++)
   {
       long int b,c;
       cin>>b>>c;
       d[b]+=c;
   }
   //for(long int i=1;i<=n;i++)
   //cout<<d[i]<<" ";
   vis[1]=1;
   dfs(1);
   for(long int i=1;i<=n;i++)
   cout<<d[i]<<" ";
}

Measured memory_bytes: 25856
while (1):
    a, op, b = input().split()
    a = int(a)
    b = int(b)
    if op == '+':
        print(a + b)
    elif op == '-':
        print(a - b)
    elif op == '*':
        print(a * b)
    elif op == '/':
        print(int(a / b))
    elif op == '?':
        break



Measured memory_bytes: 5596
#include <iostream>
#include <vector>

using namespace std;

class UnionFind {
public:
    explicit UnionFind(int N) : root(N, -1), size(N, 1) {}
    int getRoot(int u){ return root[u] == -1 ? u : root[u] = getRoot(root[u]); }
    int getSize(int u){ return size[getRoot(u)]; }
    bool same(int a, int b){
        return getRoot(a) == getRoot(b);
    }
    bool merge(int a, int b){
        int u = getRoot(a);
        int v = getRoot(b);
        if(u == v) return false;
        root[u] = v;
        size[v] += size[u];
        return true;
    }
private:
    vector<int> root;
    vector<int> size;
};

bool solve(const vector<pair<int, int>>& e1, const vector<pair<int, int>>& e2, long long N, long long M){
    if(M == N-1) return e2.empty();
    UnionFind uf(N);
    auto groupNum = N;
    for(auto& e : e1){
        if(uf.merge(e.first, e.second)) --groupNum;
    }
    if(groupNum <= 2) return M == N-1 && e2.empty();
    for(auto& e : e2){
        if(uf.same(e.first, e.second)) return false;
    }
    return M <= N - groupNum + groupNum*(groupNum-1)/2;
}

int main(){
    long long N, M, Q; cin >> N >> M >> Q;
    vector<pair<int, int>> e1;
    vector<pair<int, int>> e2;
    for(int i=0;i<Q;i++){
        int A, B, C; cin >> A >> B >> C;
        if(C == 0){
            e1.emplace_back(A, B);
        } else {
            e2.emplace_back(A, B);
        }
    }
    cout << (solve(e1, e2, N, M) ? "Yes" : "No") << endl;
}

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

void solve(std::istream &in, std::ostream &out);

int main() {
#ifdef LOCAL
  freopen("../IO/f.in", "r", stdin);
//  freopen("../IO/f.out", "w", stdout);
#else
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
#endif
  solve(std::cin, std::cout);
  return 0;
}

constexpr int N = (int)2e5 + 5;
vector<int> g[N];
int c[N], cc[N];
int64_t ans[N];
int n;

int64_t calc(int64_t x) {
  return x * (x + 1) / 2;
}

int dfs(int v, int p = -1) {
  int sz = 1;
  int col = c[v];
  int prev = cc[col];
  int p1 = prev;
  for (int u : g[v]) if (u != p) {
    int s_sz = dfs(u, v);
    int diff = cc[col] - p1;
    ans[col] += calc(s_sz - diff);
    p1 = cc[col];
    sz += s_sz;
  }
  cc[col] = prev + sz;
  return sz;
}

void solve(std::istream &in, std::ostream &out) {
  in >> n;
  for (int i = 0; i < n; ++i) in >> c[i];
  for (int i = 0, u, v; i < n - 1; ++i) {
    in >> u >> v;
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(0);
  for (int i = 1; i <= n; ++i) {
    if (c[0] != i) {
      out << calc(n) - ans[i] - calc(n - cc[i]) << '\n';
    } else {
      out << calc(n) - ans[i] << '\n';
    }
  }
}


Measured memory_bytes: 33220
A,B,C = map(int,input().split())
K = int(input())

while A >= B and K > 0:
    B = B*2
    K -= 1
while B >= C and K > 0:
    C = C*2
    K -= 1
if A < B and B < C:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9176
use proconio::*;
use std::ops;

const MOD: i64 = 1_000_000_007;

pub struct ModInt {
    val: i64,
}

impl ModInt {
    pub fn new(val: i64) -> ModInt {
        ModInt { val }
    }
}

impl ops::Add<i64> for ModInt {
    type Output = ModInt;
    fn add(self, _rhs: i64) -> ModInt {
        ModInt {
            val: (self.val + _rhs) % MOD,
        }
    }
}

impl ops::Add<ModInt> for ModInt {
    type Output = ModInt;
    fn add(self, _rhs: ModInt) -> ModInt {
        ModInt {
            val: (self.val + _rhs.val) % MOD,
        }
    }
}

impl ops::Sub<i64> for ModInt {
    type Output = ModInt;
    fn sub(self, _rhs: i64) -> ModInt {
        ModInt {
            val: (self.val - _rhs + MOD) % MOD,
        }
    }
}

impl ops::Sub<ModInt> for ModInt {
    type Output = ModInt;
    fn sub(self, _rhs: ModInt) -> ModInt {
        ModInt {
            val: (self.val - _rhs.val + MOD) % MOD,
        }
    }
}

impl ops::Mul<i64> for ModInt {
    type Output = ModInt;
    fn mul(self, _rhs: i64) -> ModInt {
        ModInt {
            val: (self.val * _rhs) % MOD,
        }
    }
}

impl ops::Mul<ModInt> for ModInt {
    type Output = ModInt;
    fn mul(self, _rhs: ModInt) -> ModInt {
        ModInt {
            val: (self.val * _rhs.val) % MOD,
        }
    }
}

impl ModInt {
    pub fn pow(self, mut base: i64, mut exp: i64) -> ModInt {
        let mut res = ModInt::new(1i64);
        while exp > 0 {
            if (exp & 1) > 0 {
                res = res * base;
            }
            exp >>= 1;
            base = base * base % MOD;
        }
        res
    }

    pub fn inv(self, base: i64) -> ModInt {
        self.pow(base, MOD - 2)
    }
}

fn main() {
    input! {
        n: i64,
    }
    let ten = ModInt::new(1).pow(10, n);
    let nine = ModInt::new(1).pow(9, n);
    let eight = ModInt::new(1).pow(8, n);

    println!("{}", (ten - nine * 2 + eight).val);
}


Measured memory_bytes: 2124
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        int N = fs.nextInt();
        int M = fs.nextInt();
        int C = fs.nextInt();
        List<Integer> B = new ArrayList<>();

        for (int i = 0; i < M; ++i) {
            B.add(fs.nextInt());
        }

        int ans = 0;
        for (int i = 0; i < N; ++i) {
            int tmp = 0;
            for (int j = 0; j < M; ++j) {
                tmp += fs.nextInt() * B.get(j);
            }
            if (tmp + C > 0) ++ans;
        }

        System.out.println(ans);
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}

    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }

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




Measured memory_bytes: 32192
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define FIND(x, target) find(x.begin(),x.end(),target)
#define pb(x) push_back(x)
#define pob(x) pop_back(x)
#define output(x) cout<<x<<endl
#define ERASE(x, n) x.erase(x.begin()+n)
// #define int long long
#define P pair<int, int>
typedef long long ll;

const long long int MOD = 1e9+7;
const int INF = -1;
ll dp[100005][13];

signed main(void) {
	ll N, Q;
	cin >> N >> Q;
	vector<vector<ll> > V(N);
	rep(i, N-1) {
		ll a, b;
		cin >> a >> b;
		a--;
		b--;
		V[a].pb(b);
		V[b].pb(a);
	}

	vector<ll> score(N);
	rep(i, Q) {
		ll p, x;
		cin >> p >> x;
		p--;
		
		score[p] += x;
	}

	queue<ll> tmp;
	tmp.push(0);
	vector<vector<ll> > newV(N);

	while(!tmp.empty()) {
		int now = tmp.front();
		tmp.pop();

		rep(i, V[now].size()) {
			int next = V[now][i];
			if (newV[next].size() == 0) {
				newV[now].pb(next);
				tmp.push(next);
				score[next] += score[now];
			}
		}
	}

	rep(i, N) {
		cout << score[i] << " ";
	}

	cout << endl;

}


Measured memory_bytes: 25856
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll Pow(ll n,ll p){
	ll r=1;
	for(;p>0;p>>=1){
		if(p&1) r=(r*n)%mod;
		n=(n*n)%mod;
	}
	return r;
}

const int M=200005;
ll F[M];

void Init(){
	F[0]=1;
	for(int i=1;i<M;i++) F[i]=F[i-1]*i%mod;
}

ll Div(ll n,ll m){
	return n*Pow(m,mod-2)%mod;
}

ll nCk(ll n,ll k){
	return Div(F[n],F[n-k]*F[k]%mod);
}

int n,k;

int main(){
	Init();
	cin>>n>>k;
	ll res=0;
	for(int i=0;i<=min(n-1,k);i++){
		(res+=nCk(n,i)*nCk(n-1,i))%=mod;
	}
	cout<<res<<endl;
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    int n;
    cin >> n;
    vector<int> P(n);
    rep(i, n) { cin >> P[i]; }
    vector<int> L(n + 1, 1e9 + 1);
    rep(i, n) { L[i + 1] = min(L[i], P[i]); }
    // dump(L);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (P[i] <= L[i]) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N; cin >> N;
  string S; cin >> S;
  vector<set<int> > alp(26, set<int>());
  REP(i, N){
    alp[S[i]-'a'].insert(i);
  }
  int Q; cin >> Q;
  vector<int> ans;
  REP(i, Q){
    int q; cin >> q;
    if(q == 1){
      // type1の処理を記載
      int I; char c; cin >> I >> c; I--;
      REP(j, 26){
        if(alp[j].find(I) != alp[j].end()){
          alp[j].erase(I);
        }
        alp[c-'a'].insert(I);
      }
    }else{
      // type2の処理を記載
      int s, e; cin >> s >> e; s--; e--;
      int tmp = 0;
      REP(j, 26){
        if(alp[j].lower_bound(s) == alp[j].end()) continue;
        if(*alp[j].lower_bound(s) <= e) tmp++;
      }
      ans.push_back(tmp);
    }
  }
  for(int i : ans){
    cout << i << endl;
  }
}

Measured memory_bytes: 24476
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, K; cin >> n >> K;

    int cur = 1;
    rep(_, n){
        cur += min(cur, K);
    }

    cout << cur << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

typedef long long ll;



int main() {
	string s; cin >> s;
	cout << s.substr(0, s.length() - 8) << endl;
	return 0;
}

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

int main(){
    string s, t;
    int a, b;
    string u;

    cin >> s >> t;
    cin >> a >> b;
    cin >> u;

    if(u == s){
        a--;
    }
    if(u == t){
        b--;
    }


    cout << a << " " << b <<   endl;   
}

Measured memory_bytes: 256
S = input()

p1 = [('0' if i % 2 == 0 else '1') for i in range(len(S))]
p2 = [('1' if i % 2 == 0 else '0') for i in range(len(S))]


tmp_ans1 = 0
for s, p in zip(S, p1):
    if s != p:
        tmp_ans1 += 1

tmp_ans2 = 0
for s, p in zip(S, p2):
    if s != p:
        tmp_ans2 += 1

print(min(tmp_ans1, tmp_ans2))


Measured memory_bytes: 4724