akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

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

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

void MAIN() {
    int L;
    scanf("%d", &L);
    VI A, B, C;
    for (int i=0; i<18; i++) {
	A.push_back(i);
	B.push_back(i+1);
	C.push_back(0);
	A.push_back(i);
	B.push_back(i+1);
	C.push_back(1<<i);
    }

    for (int i=18; i>=0; i--) {
	while (L >= (1<<i)) {
	    A.push_back(i);
	    B.push_back(19);
	    C.push_back(L-(1<<i));
	    L -= 1<<i;
	}
    }
    printf("20 %d\n", (int)A.size());
    REP (i, A.size()) printf("%d %d %d\n", A[i]+1, B[i]+1, C[i]);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



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

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

    int tmp = n, sum = 0;
    while(tmp / 10 != 0){
        sum += tmp % 10;
        tmp /= 10;
    }

    sum += tmp;


    cout << (n % sum == 0 ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.Arrays;
  
class Main{
  
static final int INF=Integer.MAX_VALUE/2;
static final PrintWriter out=new PrintWriter(System.out);
  
  
static class Edge{
int from;
int to;
int cost;
Edge(int from,int to,int cost){
this.from=from; this.to=to; this.cost=cost;
}
}
  
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line="";
while((line=br.readLine())!=null&&!line.isEmpty()){
int v=Integer.parseInt(line.split(" ")[0]);
int e=Integer.parseInt(line.split(" ")[1]);
int r=Integer.parseInt(line.split(" ")[2]);
Edge[] es=new Edge[e];
int[] d=new int[v];
for(int i=0;i<e;i++){
line=br.readLine();
int s=Integer.parseInt(line.split(" ")[0]);
int t=Integer.parseInt(line.split(" ")[1]);
int c=Integer.parseInt(line.split(" ")[2]);
es[i]=new Edge(s,t,c);
}
BellmanFord(e,r,es,d);
for(int i=0;i<v;i++){
if(d[i]==INF){
out.println("INF");
}
else{
out.println(d[i]);
}
}
out.flush();
}
}
  
private static void BellmanFord(int ee,int r,Edge[] es,int[] d){
Arrays.fill(d,INF);
d[r]=0;
while(true){
boolean update=false;
for(int i=0;i<ee;i++){
Edge e=es[i];
if(d[e.to]>d[e.from]+e.cost){
d[e.to]=d[e.from]+e.cost;
update=true;
}
}
if(!update){
break;
}
}
}
}

Measured memory_bytes: 340548
#include <iostream>
#include <string>
using namespace std;
int main( void )
{
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  string ret = "Three";
  for( int i=0; i<N; i++ ){
    char c;
    cin >> c;
    if( c == 'Y' ) ret = "Four";
  }
  cout << ret << endl;
}

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

int gcd(int a, int b){
  int smaller = min(a, b);
  int bigger = max(a, b);
  int surplus = bigger % smaller;
  if (surplus == 0)
    return smaller;
  surplus = gcd(smaller, surplus);
  return surplus;
}

int main() {
  int k;
  cin >> k;
  int ans = 0;
  for (int i = 1; i <= k; i++){
    for (int j = 1; j <= k; j++){
      for (int t = 1; t <= k; t++){
        ans += gcd(gcd(i, j), t);
      }
    }
  }
  cout << ans << endl;
}

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

int main(){
  int H,N;
  cin>>H>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin>>A.at(i);
  }
  int s=0;
  for(int i=0;i<N;i++){
    s = s+A.at(i);
  }
  if (s>=H){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
  
  
}

Measured memory_bytes: 640
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

signed main(){
    while(true){
        int n, m;
        cin >> n >> m;

        if(n == 0 && m == 0){
            break;
        }

        vector<int> a(n);
        rep(i, n) cin >> a[i];

        int ans = -1;
        rep(i, n){
            rep(j, n){
                if(i == j){
                    continue;
                }

                int tmp = a[i] + a[j];
                if(tmp > ans && tmp <= m){
                    ans = tmp;
                }
            }
        }
        if(ans == -1){
            cout << "NONE" << endl;
        }else{
            cout << ans << endl;
        }
    }

    return 0;
}



Measured memory_bytes: 3100
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=500050;
//ここまでテンプレ
vector<int> Z(string S){
	vector<int> A(S.size(),0);
	A[0]=S.size();
	int i=1,j=0;
	while(i<S.size()){
		while(i+j<S.size() && S[j]==S[i+j])
			++j;
		A[i]=j;
		if(j==0){
			++i;
			continue;
		}
		int k=1;
		while(i+k<S.size() && k+A[k]<j)
			A[i+k]=A[k],++k;
		i+=k;
		j-=k;
	}
	return A;
}
int main(){
	string W;
	cin>>W;
	//全部同じ文字の場合
	bool flag=true;
	for(int i=1;i<W.length();i++)
		if(W[i]!=W[0])
			flag=false;
	if(flag){
		cout<<W.length()<<endl;
		cout<<1<<endl;
		return 0;
	}

	int N=W.length();
	bool pre[SIZE]={},suf[SIZE]={};
	for(int i=0;i<=N;i++){
		pre[i]=true;
		suf[i]=true;
	}
	//prefixについて
	vint A=Z(W);
	//周期を全探索する
	for(int p=1;p<N;p++){
		//繰り返し回数を全探索する
		for(int k=2;(k-1)*p<=A[p];k++){
			pre[k*p]=false;
		}
	}
	//suffixについて
	reverse(W.begin(),W.end());
	vint B=Z(W);
	//周期を全探索する
	for(int p=1;p<N;p++){
		//繰り返し回数を全探索する
		for(int k=2;(k-1)*p<=B[p];k++){
			suf[k*p]=false;
		}
	}

	//Wがよい文字列の場合
	if(pre[N]){
		cout<<1<<endl;
		cout<<1<<endl;
		return 0;
	}

	int ans=0;
	for(int i=1;i<N;i++)
		if(pre[i] && suf[N-i])
			ans++;
	cout<<2<<endl;
	cout<<ans<<endl;
	/*
	for(int i=0;i<N;i++)
		cout<<A[i];
	cout<<endl;
	for(int i=0;i<N;i++)
		cout<<B[N-1-i];
	cout<<endl;

	cout<<endl;
	for(int i=0;i<=N;i++)
		cout<<pre[i];
	cout<<endl;
	for(int i=0;i<=N;i++)
		cout<<suf[N-i-1];
	cout<<endl;
	*/
	return 0;
}

Measured memory_bytes: 6168
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <bitset>
#include <memory>
#include <string>
#include <vector>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>
#include <algorithm>
#include <random>
#include <iomanip>
using namespace std;

int main(int argc, char *argv[]) {
	
	int x;
	cin >> x;
	for (int i = x; ; i++) {
		bool isPrime = true;
		for (int j = 2; j * j <= x; j++) {
			if (i % j == 0) {
				isPrime = false;
				break;
			}
		}
		if (isPrime) {
			cout << i << endl;
			return 0;
		}
	}
}









Measured memory_bytes: 256
import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)

def main():
    A, B = map(int, input().split())
    K = (A + B) / 2
    if math.ceil(K) != K:
        print("IMPOSSIBLE")
    else:
        print(int(K))

if __name__ == '__main__':
    main()

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


void solve(long long N, std::vector<long long> B){
    long long myresult = B[0]+B[N-2];
    for (int i=1; i< N-1; i++){
        myresult += min(B[i], B[i-1]);
    }
    cout << myresult << endl;

}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> B(N-1);
    for(int i = 0 ; i < N-1 ; i++){
        scanf("%lld",&B[i]);
    }
    solve(N, std::move(B));
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define sn(n) scanf("%d",&n)
#define pr(n) printf("%d",n)
#define pn printf("\n")
#define ll long long
#define p 1000000005
using namespace std;
int n,m;
int main()
{
    int k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)
    {
        if(i%2==0)
        {
            if(m%2==1)
                m--;
            n+=m/2;
            m/=2;
        }
        else
        {
            if(n%2==1)
                n--;
            m+=n/2;
            n/=2;
        }
    }
    printf("%d %d\n",n,m);
    return 0;
}


/*

Lucas(卢卡斯)定理

ll pow_quick(ll a, ll b)

{

    ll  ans =1;

    while(b)

    {

        if(b &1)  ans = ans * a % p;

        b>>=1;

        a = a*a % p;

    }

    return  ans;

}

ll C(ll n, ll m)

{

    if(m > n)  return 0;

    ll ans = 1;
    for(ll i=1; i<=m; i++)
    {
        ll a = (n+i-m)%p;

        ll b = i%p;

        ans = (ans*(a*pow_quick(b,p-2)%p))%p;

    }
    return ans;
}

ll Lucas(ll n, ll m )

{

    if(m ==0)  return 1;

    else return  (C(n%p, m%p)*Lucas(n/p, m/p))%p;

}


*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s, t;
  cin >> s >> t;
  int n = s.size(), count = 0;
  for(int i = 0; i < n; i++){
    if(s[i] != t[i]) count++;
  }
  printf("%d", count);
}


Measured memory_bytes: 3900
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#define For(i,a,b) for(int i=(a);i<(b);i++)
#define Rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;


int main() {
	string s;
	cin >> s;
	int n = s.size();
	ll res = 0;
	for (int bit = 0;bit < (1 << n - 1);bit++) {
		string t;
		t.push_back(s[0]);
		Rep(i, n-1) {
			if (bit & (1 << i)) {
				res += stoll(t);
				t.erase(0);
			}
			t.push_back(s[i + 1]);
		}
		res += stoll(t);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
N=int(input())
A=[int(input()) for i in range(N)]
ans=0
s=0
for i in range(N):
    ans+=A[i]//2
    s=A[i]-2*(A[i]//2)
    if i!=N-1 and A[i+1]!=0 and s!=0:
        A[i+1]-=s
        ans+=1
    #print(A,ans,s)
print(ans)

Measured memory_bytes: 51800
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int n, a[N], pre[N];
ll m, sum[N], ans;
ll check(int x) {
    ll cnt = 0;
    ans = 0;
    for(int i = 0; i < n; i++) {
        cnt += pre[max(0, x-a[i])];
        ans += sum[max(0, x-a[i])] + (ll)a[i]*pre[max(0, x-a[i])];
    }
    return cnt;
}
int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        pre[a[i]]++;
    }
    for(int i = N-2; i >= 0; i--) {
        sum[i] = sum[i+1] + (ll)i*pre[i];
        pre[i] += pre[i+1];
    }
    int l = 1, r = 200000, res = 0;
    while(l <= r) {
        int mid = (l+r)/2;
        if(check(mid) >= m) {
            res = mid;
            l = mid+1;
        } else {
            r = mid-1;
        }
    }
    ll cnt = check(res);
    cout << ans-(cnt-m)*res << '\n';
    return 0;
}

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

int main(void){
    ll n,a,b;
    cin >> n >> a >> b;
    if((a-b)%2==0){
        cout << abs(a-b)/2 << endl;
    }else{
        ll s,l;
        s=min(a,b);
        l=max(a,b);
        cout << min({l-1, n-s, (l-s-1)/2+min(s,n-l+1)}) << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

void calc_rectangle(int a, int b, int *s, int *l)
{
    *s = a * b;
    *l = a + a + b + b;
}

int main(void)
{
    int a, b, s, l;
    scanf("%d %d", &a, &b);
    calc_rectangle(a, b, &s, &l);
    printf("%d %d\n", s, l);
}


Measured memory_bytes: 2560
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var inps = ReadLongs();
            var A = inps[0];
            var B = inps[1];
            return A <= 9 && B <= 9 ? A * B : -1;
        }

        #region Console

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 13268
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;


int solve(int n, int sum, int amax) {
	if (n == 0) {
		if (sum == 0) {
			return 1;
		}
		else {
			return 0;
		}
	}
	else if (amax*n < sum ||0 * n>sum)return 0;
	else {
		int nans=0;
		for (int x =0; x <= amax; ++x) {
			nans+=solve(n-1,sum-x,x-1);
		}
		return nans;
	}
}


int main() {
	int a,b,c;
	int h=0,ch=0;
	while (scanf("%d,%d,%d",&a,&b,&c)!=-1) {
		vector<int>v{ a,b,c };
		a=v[0];
		b=v[1];
		c=v[2];
		if(a==b)h++;
		if(a*a+b*b==c*c)ch++;
	}
	cout<<ch<<endl<<h<<endl;
	return 0;
}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  vector<int> abc(3);
  abc = {A, B, C};
  sort(abc.begin(), abc.end());
  int s = abc.at(0);
  int m = abc.at(1);
  int l = abc.at(2);
  if (m % 2 == s % 2){
    cout << ((l - m) + (l - s)) / 2 << endl;
  }
  else{
    cout << 1 + ((l + 1 - m) + (l - s)) / 2 << endl;
  }
}

Measured memory_bytes: 3640
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
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 INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

int main(){
	string S; cin >> S;
	string ans;
	if(S[0] == 'S') ans = "Cloudy";
	else if(S[0] == 'C') ans = "Rainy";
	else ans = "Sunny";
	cout << ans << endl;
}



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

inline long long read(){
    long long s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9'){
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * w;
}
int a[1111], z = 999999, ans = 999999;
int main(){
    int x = read(), n = read();
    for (int i = 1; i <= n; i++){
        int xcj = read();
        a[xcj] = 1;
    }
    for (int i = 0; i <= 999; i++){
        if (x - i >= 0){
            if (a[x-i] == 0){
                cout << x-i << endl;
                return 0;
            }
        }
        if(a[x+i] == 0){
            cout << x + i << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
import java.io.*;
import java.util.HashMap;

class Main {
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] words = br.readLine().split(" ");
        
        HashMap<String, Integer> wordMap = new HashMap<String, Integer>();
        String maxLengthWord = "";
        for (int i = 0; i < words.length; i++) {
            if (wordMap.containsKey(words[i])) {
                wordMap.put(words[i], wordMap.get(words[i]) + 1);
            } else {
                wordMap.put(words[i], 1);
            }
            
            if (maxLengthWord.length() < words[i].length()) {
                maxLengthWord = words[i];
            }
        }
        
        // output
        int maxOftenCount = -1;
        String maxOftenWord = "";
        for (String key : wordMap.keySet()) {
            if (maxOftenCount < wordMap.get(key)) {
                maxOftenWord = key;
                maxOftenCount = wordMap.get(key);
            }
        }
        
        System.out.println(maxOftenWord + " " + maxLengthWord);
    }
}

Measured memory_bytes: 24116
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab.sort()
p = [0]*n
for i in range(q):
  a, b = map(int, input().split())
  p[a - 1] += b
s = ""
for i in ab:
  p[i[1]-1] += p[i[0]-1]
print(" ".join(map(str, p)))

Measured memory_bytes: 78428
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MOD = 998244353;
const int MAXN = 4000;

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

int comb[MAXN + 1][MAXN + 1];
int p2[MAXN + 1];

inline int get(int n, int k) {
    if(n < 0 || k <= 0)
        return 0;
    return comb[n + k - 1][k - 1];
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int n, k, i, j;
    ios::sync_with_stdio(false);
    cin >> k >> n;
    for(i = 0; i <= MAXN; i++) {
        comb[i][0] = 1;
        for(j = 1; j <= i; j++) {
            comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
            mod(comb[i][j]);
        }
    }
    p2[0] = 1;
    for(i = 1; i <= MAXN; i++) {
        p2[i] = p2[i - 1] * 2;
        mod(p2[i]);
    }
    for(int val = 2; val <= 2 * k; val++) {
        int m = val / 2 - max(1, val - k) + 1;
        int ans = 0;
        if(val & 1) {
            for(i = 0; i <= m; i++) {
                int cur = (1LL * comb[m][i] * p2[i]) % MOD;
                cur = (1LL * cur * get(n - i, i + k - 2 * m)) % MOD;
                ans += cur;
                mod(ans);
            }
        }
        else {
            for(i = 0; i < m; i++) {
                int cur = (1LL * comb[m - 1][i] * p2[i]) % MOD;
                cur = (1LL * cur * get(n - i, i + k - 2 * m + 1)) % MOD;
                ans += cur;
                mod(ans);
            }
            for(i = 1; i <= m; i++) {
                int cur = (1LL * comb[m - 1][i - 1] * p2[i - 1]) % MOD;
                cur = (1LL * cur * get(n - i, i + k - 2 * m)) % MOD;
                ans += cur;
                mod(ans);
            }
        }
        cout << ans << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}


Measured memory_bytes: 61312
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

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

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

inline double nCr(const int n, int r)
{

    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

//----------------------------------------------------------------

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> h(n);
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
    }
    sort(h.begin(), h.end());
    ll ans = infll;
    for (int i = 0; i < n - k + 1; i++)
    {
        chmin(ans, abs(h[i] - h[i + k - 1]));
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
int P(int x){
  int i;
  if(x<2) return 0;
  else if(x==2) return 1;
  if(x%2==0) return 0;
  for(i=3;i*i<=x;i+=2){
    if(x%i==0) return 0;
  }
  return 1;
}
int main(){
  int n,x,i;
  int c=0;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&x);
    if(P(x)) c++;
  }
  printf("%d\n",c);
  return 0;
}



Measured memory_bytes: 2000
#include <bits/stdc++.h>
#define REP(i,x,y) for(int i=(int)x;i<=(int)y;i++)
#define PER(i,x,y) for(int i=(int)x;i>=(int)y;i--)
#define FOR(i,x,y) for(int i=(int)x;i< (int)y;i++)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
using namespace std;
typedef long long LL;
typedef long double db;
typedef pair<int,int> PII;
const   int N=100005;
const   int P=1e9+7;

int n,a[N];

int main(){
	scanf("%d",&n);
	REP(i,1,n) scanf("%d",a+i);
	int ans=1,res=1;
	REP(i,1,n) ans*=3;
	REP(i,1,n) if(a[i]%2==0) res*=2;
	ans-=res;
	printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

static const ll MOD = 1000000007;

unordered_map<int,int> factorize(int x){
  unordered_map<int,int> ret;
  int d, q;
  while(x>=4 && x%2==0){ret[2]++; x/=2;}
  d = 3; q = x/d;
  while(q>=d){
    if(x%d==0){ ret[d]++; x=q; }else{ d+=2; }
    q=x/d;
  }
  ret[x]++;
  return ret;
}

ll mod_pow(ll x, ll n, ll mod){
  ll res = 1;
  while(n>0){
    if(n&1) res = res*x%mod;
    x = x*x%mod;
    n >>= 1;
  }
  return res;
}

ll extgcd(ll a, ll b, ll &x, ll &y){
  ll d = a;
  if(b!=0){
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }else{
    x = 1; y = 0;
  }
  return d;
}

ll mod_inverse(ll a, ll m){
  ll x, y;
  extgcd(a, m, x, y);
  return (m+x%m)%m;
}

int main(){
  int N;
  cin >> N;
  vector<int> v;
  vector<unordered_map<int,int>> w;
  unordered_map<int,int> f;
  rep(i,N){
    int a;
    cin >> a;
    v.push_back(a);

    unordered_map<int,int> res = factorize(a);
    w.push_back(res);
    FOR(it,res){
      if(f[it->first] < it->second){
        f[it->first] = it->second;
      }
    }
  }

  ll fx = 1;
  FOR(it,f){
    fx *= mod_pow(it->first, it->second, MOD);
    fx %= MOD;
  }
  
  unordered_map<int,ll> ret;
  ll ans = 0;
  rep(i,N){
    ll tmp = fx;
    FOR(it,w[i]){
      tmp *= mod_inverse(mod_pow(it->first, w[i][it->first], MOD), MOD);
      tmp %= MOD;
    }
    ans += tmp;
    ans %= MOD;
  }

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



Measured memory_bytes: 3288
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int dx[] = {0, 0, 1, -1};
constexpr int dy[] = {1, -1, 0, 0};

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

    int n;
    vector<P> v;

    cin >> n;
    REP(i, n * 2)
    {
        int a;
        cin >> a;
        v.push_back(make_pair(a, i / n));
    }

    SORT(v);

    ll res = 1;

    int i = 0;
    int pc = 0;
    int b = 0;

    while (i < n * 2)
    {
        if (v[i].second == 0)
        {
            if (b)
            {
                (res *= b) %= MOD;
                b--;
                pc--;
            }

            pc++;
        }
        else
        {
            if (pc)
            {
                (res *= pc) %= MOD;
                pc--;
                b--;
            }

            b++;
        }

        i++;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 2420
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
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; }

int main(void){
    int n,k,x,y; cin >> n >> k >> x >> y;
    cout << x*min(n,k)+y*max(0,n-k) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct cww { cww() { ios::sync_with_stdio(false); cin.tie(0); } }star;
#define P(x) cout << (x) << "\n"
#define p(x) cout << (x)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define vv(type, c, m, n, i) vector<vector<type>> c(m, vector<type>(n, i))
#define rep(i,a,n) for(int i=(a), i##_len=(n); i<i##_len; ++i)
#define rrep(i,a,n) for(int i=(a), i##_len=(n); i>i##_len; --i)
#define len(x) ((int)(x).size())
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
#define chmax(a,b) if(a<b)a=b
#define chmin(a,b) if(b<a)a=b
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
constexpr int dx[] = { 1, 0, -1,  0 };
constexpr int dy[] = { 0, 1,  0, -1 };
constexpr char dir[4] = { 'r', 'u', 'l', 'd' };
#define N 4
#define N2 16
#define LIMIT 100
int MDT[N2][N2];
struct Puzzle {
	int f[N2];
	int space, MD;
};
Puzzle state;
int limit;
int path[LIMIT];
int getAllMD(Puzzle pz) {
	int sum = 0;
	rep(i, 0, N2) {
		if (pz.f[i] == N2) continue;
		sum += MDT[i][pz.f[i] - 1];
	}
	return sum;
}
bool isSolved() {
	rep(i, 0, N2) if (state.f[i] != i + 1) return false;
	return true;
}
bool dfs(int depth, int prev) {
	if (state.MD == 0) return true;
	if (depth + state.MD > limit) return false;
	int sx = state.space / N;
	int sy = state.space % N;
	Puzzle tmp;
	int tx, ty;
	rep(r, 0, 4) {
		tx = sx + dx[r];
		ty = sy + dy[r];
		if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;
		if (max(prev, r) - min(prev, r) == 2) continue;
		tmp = state;
		state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1];
		state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1];
		swap(state.f[tx * N + ty], state.f[sx * N + sy]);
		state.space = tx * N + ty;
		if (dfs(depth + 1, r)) { path[depth] = r; return true; }
		state = tmp;
	}
	return false;
}
string iterative_deepening(Puzzle in) {
	in.MD = getAllMD(in);
	string ans = "";
	for (limit = in.MD; limit <= LIMIT; ++limit) {
		state = in;
		if (dfs(0, -100)) {
			ans = "";
			rep(i, 0, limit) ans += dir[path[i]];
			return ans;
		}
	}
	return "unsolvable";
}
int main() {
	rep(i, 0, N2) {
		rep(j, 0, N2) {
			MDT[i][j] = abs(i / N - j / N) + abs(i % N - j % N);
		}
	}
	Puzzle in;
	rep(i, 0, N2) {
		cin >> in.f[i];
		if (in.f[i] == 0) {
			in.f[i] = N2;
			in.space = i;
		}
	}
	P(len(iterative_deepening(in)));
	return 0;
}


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

int n;

int main() {

cin >> n;

if(n == 3) cout << 2 << " " << 5 << " " << 63 << " " ;
else {
    cout << 3 << " " << 9 << " ";
    if (n <= 15002) {
        if(n % 3 == 0) {
            int i;
            for(i = 1; i < n - 2; i++) cout << 2 * i << " ";
            cout << 2 * (i + 2) << " ";
        } else {
            for(int i = 1; i < n - 1; i++) cout << 2 * i << " ";
        }
    } else {
        if(n % 2 == 0) {
            for(int i = 1; i <= 15000; i++) cout << 2 * i << " ";
            for(int i = 1; i <= n - 15002; i++) cout << 6 * (i + 2) - 3 << " ";
        }
        else {
            for(int i = 1; i < 15000; i++) cout << 2 * i << " ";
            for(int i = 1; i <= n - 15001; i++) cout << 6 * (i + 2) - 3 << " ";
        }
    }
}

return 0;

}


Measured memory_bytes: 384
#include <iostream>

int main()
{
	int A, B, C, D;
	std::cin >> A >> B >> C >> D;

	if ( A * B >= C * D ) {
		std::cout << A * B << std::endl;
	}else{
		std::cout << C * D << std::endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <climits>

using namespace std;

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

    cout << unique(s.begin(), s.end()) - s.begin() - 1
         << endl;

    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define FOR(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
const long long dx[4]={1,0,-1,0};
const long long dy[4]={0,1,0,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

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

    int k,s; cin >> k >> s;
    int res=0;
    for(int x=0; x<=k; x++){
        for(int y=0; y<=k; y++){
            if(0<=s-x-y && s-x-y<=k) res++;
        }
    }
    cout<<res<<endl;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define mod 1000000007
#define eps 1e-8
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 202;
int n,m,r,a[N];
ll dp[N][N];

int main(){
    read3i(n,m,r);
    lp(i,1,r) readi(a[i]);
    lp(i,1,n) lp(j,1,n) dp[i][j] = infll;
    lp(i,1,m){
        int x,y,z;
        read3i(x,y,z);
        dp[x][y] = dp[y][x] = z;
    }

    lp(k,1,n) lp(i,1,n) lp(j,1,n) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

    ll ans = infll;
    sort(a+1, a+1+r);
    do{
        ll curr = 0;
        lp(i,2,r) curr += dp[a[i-1]][a[i]];
        ans = min(ans, curr);
    }while(next_permutation(a+1, a+1+r));
    cout <<ans;
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
*/


Measured memory_bytes: 512
//@truneo
//The purpose of computation is insight, not numbers...
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
	int t;
	//cin>>t;
	t=1;
	while(t--)
	{
		ll n,k;
		cin>>n>>k;
		ll h[n];
		ll dp[n];
		memset(dp,0,sizeof(dp));
		
		for(ll i=0;i<n;i++)
		{
			cin>>h[i];
		}
		dp[1]=llabs(h[1]-h[0]);
		for(ll i=2;i<n;i++)
		{
			ll mn=100000000000000000;
			for(ll j=max((ll)0,i-k);j<i;j++)
			{
				mn=(ll)min(dp[j]+llabs(h[i]-h[j]),mn);
			}
			dp[i]=mn;
		}
		/*for(int i=0;i<n;i++)
		{
			cout<<dp[i]<<" ";
		}
		cout<<endl;*/
		cout<<dp[n-1]<<"\n";
	}


	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++);
int main(){
    string S; cin >> S;
    string T; 

    int N = S.length(); bool flag = true; int i = N-1;
    while(i > 0){
      	//cout << S.substr(i-4, 5) << endl;
        if(S.substr(i-4, 5) == "dream" || S.substr(i-4, 5) == "erase") i -= 5;
        else if(S.substr(i-5, 6) == "eraser") i -= 6;
        else if(S.substr(i-6, 7) == "dreamer") i -= 7;
        else{
            cout << "NO";
            flag = false;
            break;
        }
    }
    if(flag) cout << "YES";
}

Measured memory_bytes: 512
// When you are hungry for something and you're determined and you're focused 
// and you're committed to something it's hard to surrender, isn't it?

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ll long long 
#define int ll
#define mod 1000000007
#define mod1 1000000006
#define modi 998244353
#define setbit(x) __builtin_popcount(x)
#define fff(i,n) for(int i=0;i<n;i++)
#define fab(i,a,b) for(int i=(a);i<(b);i++)
#define ff first
#define ss second
#define pb push_back
vector<ll> vi[300005];
int color[100005];
ll pa[500005];
ll si[500005];
#define pb push_back
bool visi[1000005]={false};
bool is[100005];
ll fac[10000001];
ll prime[400005];
ll bit[100005];
const long double eps = 1.0e-14;      // allowable error
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
 
 
void fact(){
    fac[0]=1;
    for(int i=1;i<=10000000;i++){
        fac[i]=(fac[i-1]*i)%mod;
    }
    return ;
}
void sieve(){
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<400005;i++){
        prime[i]=1;
    }
    for(int i=2;i*i<400005;i++){
        if(prime[i]==1){
            for(int j=i*i;j<400005;j+=i){
                prime[j]=0;
            }
        }
    }
    
}
 
ll power(ll n , ll p ){
    if(p==0)
        return 1;
    
    ll res = power((n*n)%mod,p/2);
    if(p%2==1)
        res = (n*res)%mod;
    
    return res;
}
 
 
void upd(ll i,ll val,ll n) {
    for(;i<=n;i+=i&(-i))
        bit[i]+=val;
}
 
ll qry(ll i) {
    ll sum=0;
    for(;i>0;i-=i&(-i))
        sum+=bit[i];
    return sum;
}
 
 
ll fin(ll u) {
    if(pa[u]==u)
        return u;
    return fin(pa[u]);
}
 
void uni(ll u,ll v) {
    ll p1=fin(u);
    ll p2=fin(v);
    if(p1==p2)
        return;
    if(si[p1]<si[p2])
        swap(p1,p2);
    si[p1]+=si[p2];
    pa[p2]=p1;
    return;
}

int log(int x) {
    int i;
    for(i=0;(1<<i)<=x;i++);
    return i;
}

vector<int> osci(vector<int> v) {
	vector<int> v1;
	int n=v.size();
	int i=0,j=n-1;
	for(int k=0;k<n;k++) {
		if(k%2==0)
			v1.pb(v[i++]);
		else
			v1.pb(v[j--]);
	}
	reverse(all(v1));
	return v1;
} 
 
int32_t main() {
    fio
	cout << fixed << setprecision(15);
    
    int n,m;
    cin >> n >> m;
    int a[n+1];
    fff(i,n+1)
    a[i]=0;
    
    fff(i,m) {
        int x,y;
        cin >> x >> y;
        a[x]+=1;
        a[y+1]-=1;
    }
    
    fab(i,1,n+1) 
    a[i]+=a[i-1];
    
    int c=0;
    fff(i,n+1) {
        if(a[i]==m)
        c++;
    }
    
    cout << c;

	return 0;
    
}

Measured memory_bytes: 9728
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
    int n;
    int q;
    string s;
    while(1){
        double m = 0; //heikin
        double a = 0;
        cin >>n;
        if (n == 0)break;
        for (int i = 0; i<n; i++){
            cin >>q;
            s[i] = q;
            
            m += s[i];
            
        }
        for(int i = 0; i<n; i++){
            
            a += ((s[i])-(m/n))*((s[i])-(m/n));
            
        }printf("%lf\n", sqrt(a/n));
        
    }return 0;
}



Measured memory_bytes: 3192
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <istream>
#include <map>
#include <set>
#include <queue>
#define rep0(i,n) for (int i = 0; i < (n); ++i)
#define rep1(i,n) for (int i = 1; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i) 
const long long INF = 1000000007;
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	/*
	/
	/
	/
	*/
	int n, m, x;
	cin >> n >> m >> x;
	int temp1 = 0;
	int temp2 = 0;
	int temp = 0;
	rep0(i, m) {
		cin >> temp;
		if (x < temp)temp1++;
		else temp2++;
	}
	cout << min(temp1, temp2) << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5*2 + 5;
long long add[maxn];
vector<int> G[maxn];
long long results[maxn];
void dfs(int curr,int past,int result){
  results[curr] = result + add[curr];
  for(auto i:G[curr]){
    if(i!=past){
      dfs(i,curr,results[curr]);
    }
  }
}
int main(){
	int n,q;cin>>n>>q;
    for(int i=1;i<n;++i){
      int f,t;
      cin>>f>>t;
      G[f].push_back(t);
      G[t].push_back(f);
    }
    memset(add,0,sizeof(add));
    memset(results,0,sizeof(results));
    for(int i=0;i<q;++i){
      int r,c;cin>>r>>c;
      add[r] += c;
    }
    dfs(1,0,0);
    for(int i=1;i<=n;++i)cout<<results[i]<<" ";
    cout<<endl;
	return 0;
}

Measured memory_bytes: 25856
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <utility>
#include <deque>
#include <stack>
#include <bitset>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define rep(i,n) for (int i=0;i<n;++i)
#define REP(i,n) for (int i=1;i<=n;++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define pf push_front
#define F first
#define S second
#define read(x) scanf("%d",&x)
int n;
char s[5005];
const ll H=19260817,P=998244353;
ll nxt[5005][5005];
int ans=0;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>s+1;
	for (int i=1;i<=n;++i){
		for (int j=1;i+j-1<=n;++j) nxt[i][j]=(nxt[i][j-1]+s[i+j-1])*H%P;
	}
	for (int i=1;i<n;++i){
		for (int j=i+1;j<=n;++j){
			if (s[i]!=s[j]) continue;
			int L=0,R=min(n-j+1,j-i);
			if (nxt[i][R]==nxt[j][R]){
				ans=max(ans,R);continue;
			}
			while(R-L>1){
				if (R<=ans) break;
				int M=L+R>>1;
				if (nxt[i][M]==nxt[j][M]) L=M;
				else R=M;
			}
			ans=max(ans,L);
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 194944
#include<stdio.h>
int main(void)
{
    int a, b, i, s, d, x;

    scanf("%d%d", &a, &b);
    d = 0;
    i = 1;
    s = b - a;
    while (i != s){
          d = d + i;
          i++;
    }
    x = d - a;
    printf("%d\n", x);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n, m;
  cin >> n >> m;
  vector<P> vp;
  rep(i, 0, n) {
    int a, b;
    cin >> a >> b;
    vp.emplace_back(a, b);
  }
  sort(vp.begin(), vp.end());

  ll ans = 0;
  rep(i, 0, n) {
    ll buy = min(m, vp[i].second);
    ans += buy * vp[i].first;
    m -= buy;
    if (m <= 0) {
      cout << ans << endl;
      break;
    }
  }
}


Measured memory_bytes: 1400
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
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()

typedef vector <int> VI;

void solve( vector <int> a, vector <int> b ) {
  for ( VI::iterator it_i = a.begin(); it_i != a.end(); ++ it_i ) {
    for ( VI::iterator it_j = b.begin(); it_j != b.end(); ++ it_j ) {
      swap( *it_i, *it_j );
      int sa = accumulate( a.begin(), a.end(), 0 );
      int sb = accumulate( b.begin(), b.end(), 0 );
      if ( sa == sb ) {
	cout << *it_j << " " << *it_i << endl;
	return;
      }
      swap( *it_i, *it_j );
    }
  }
  cout << -1 << endl;
}

int main() {
  int n, m;
  while ( cin >> n >> m ) {
    if ( n == 0 && m == 0 ) break;
    vector <int> a( n ), b ( m );
    for ( int i = 0; i < n; ++ i ) {
      cin >> a[i];
    }
    for ( int i = 0; i < m; ++ i ) {
      cin >> b[i];
    }
    solve( a, b );
  }
  return 0;
}

Measured memory_bytes: 0
#!/usr/local/gnu/bin/bash
a=(0 1 3 3 7 7 7 14 22 22 22 33 33 46 60)
c=(0 1 2 2 3 3 3 4 5 5 5 6 6 7 8 8)
read n
k=$((n/15))
echo $((60*k*k+c[n%15]*15*k+a[n%15]))


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

using namespace std;


int main(){

int W,H,C,cost;
cin>>W>>H>>C;

if(W==H)cost=C;

if(W>H){
for(int i=H;i>0;i--){
if(H%i==0&&W%i==0){
cost=((W/i)*(H/i))*C;
break;
}
}
}

if(W<H){
for(int i=W;i>0;i--){
if(H%i==0&&W%i==0){
cost=((W/i)*(H/i))*C;
break;
}
}
}

cout<<cost<<endl;

return 0;
}


Measured memory_bytes: 3100
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

class Interval {
public:
    long long int start, finish;

    bool operator < (const Interval& x) const   {
        if (finish != x.finish)
            return finish < x.finish;
        return start < x.start;
    }
} *intervals;

int main()  {
    long long int N, i, last_finished,a;

    cin>>a>>N; //Number of intervals
    intervals = new Interval[N];
    for (i = 0; i < N; i++)
        //scanf("%d %d", &intervals[i].start, &intervals[i].finish);
        cin>>intervals[i].start>>intervals[i].finish;

    // sort intervals in non-decreasing order of finish times
    sort(intervals, intervals + N);

    queue <long long int> opt;
    // construct the optimal solution
    for (i = 0, last_finished = 0; i < N; i++)
        if (intervals[i].start >= last_finished)    {
            opt.push(i);
            last_finished = intervals[i].finish;
        }

    // optimal solution
    //printf("%d\n", opt.size());
    cout<<opt.size();
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int n, i, p, a, gcda;
bool pairwise = true;
vector<bool> flag(1000005);
int main() {
    scanf("%d", &n);
    for (i = 1; i <= n; ++i) {
        scanf("%d", &a);
        gcda = __gcd(a, gcda);
        if (pairwise) {
            for (p = 2; p * p <= a; ++p)
                if (a % p == 0) {
                    do {
                        a /= p;
                    } while (a % p == 0);
                    if (flag[p]) {
                        pairwise = false;
                        break;
                    }
                    flag[p] = true;
                }
            if (a > 1) {
                if (flag[a])
                    pairwise = false;
                flag[a] = true;
            }
        }
    }
    puts(pairwise ? "pairwise coprime"
                  : gcda == 1 ? "setwise coprime" : "not coprime");
}

Measured memory_bytes: 3808
n=int(input())

if len(str(n)) == 1:
  print(n)
elif len(str(n)) == 2:
  print(9)
elif len(str(n)) == 3:
  print(9+n-99)
elif len(str(n)) == 4:
  print(9+900)
elif len(str(n)) == 5:
  print(9+900+n-9999)
elif len(str(n)) == 6:
  print(90909)

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		
		if(S.charAt(0) == S.charAt(1) && S.charAt(1) == S.charAt(2) && S.charAt(2) == S.charAt(3)) {
			System.out.println("No");
			return;
		}
		
		if(S.charAt(0) == S.charAt(1) && S.charAt(2) == S.charAt(3)) {
			System.out.println("Yes");
		} else if(S.charAt(0) == S.charAt(2) && S.charAt(1) == S.charAt(3)) {
			System.out.println("Yes");
		} else if(S.charAt(0) == S.charAt(3) && S.charAt(1) == S.charAt(2)) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		
	}
}


Measured memory_bytes: 22868
import sys

N, M = map(int, input().split())
p = list(map(int, input().split()))
p.insert(0,0)
pairs = [[int(c) for  c in l.strip().split()] for l in sys.stdin]

link = [[] for _ in  range(N+1)]
for i in range(M):
  x = pairs[i][0]
  y = pairs[i][1]
  link[x].append(y)
  link[y].append(x)


ans = 0
visited = set()
#数列の１つ１つの数字について
for i in range(1, N+1):

  #既に1度見た数字は飛ばす
  if i in visited:
    continue
  
  #linkedに交換可能なひとまとまりの数字をセットとして格納
  #ここでlinkedをリセット
  linked = set()

  #todoにはリンク先を調べないといけない数字のリストを格納
  todo = [i]
  while todo:

    #todoから1つずつ
    cur = todo.pop()
    for dest in link[cur]:

      #既にグループに入っている数字は飛ばす
      if dest not in linked:
        linked.add(dest)
        todo.append(dest)

  #「位置」を表すグループと「数字」を表すグループのオーバーラップ部分を数える
  ans += len(linked & set(p[n] for n in linked))
  #一度見た数字は再訪しない
  visited |= linked

#最後にまだ一度も見ていない数字のなかで、i = p[i]であるものを探す
for i in set(range(1,N+1)) - visited:
  ans += i == p[i]

print(ans)




Measured memory_bytes: 55128