akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <unordered_map>

using namespace std;
using ll = long long;

void _cin(){} template <class Head, class... Tail> void _cin(Head&& head, Tail&&... tail){ cin >> head; _cin(forward<Tail>(tail)...); }
void _cout(){ cout << "\n"; } template <class Head, class... Tail> void _cout(Head&& head, Tail&&... tail){ cout << head; _cout(forward<Tail>(tail)...); }
int gcd(int a, int b){ return (b == 0) ? a : gcd(b, a % b); }

#define For(i, n) for(int i = 0; i < (n); i ++)
#define Rep(n) For(_, n)
#define Range(c) c.begin(), c.end()
#define RevRange(c) c.rbegin(), c.rend()
#define Contains(c, x) (find(Range(c), x) != c.end())
#define Search(rb, re, x) distance(rb, find(rb, re, x))
#define Sort(a) sort(Range(a))
#define DeSort(a) sort(RevRange(a))
#define Reverse(c) reverse(Range(c))
#define Vec2(T, n, m, xs, x0) vector<vector<T>> xs(n, vector<T>(m, x0))
#define Sum(a) accumulate(Range(a), 0)
#define Cusum(T, xs, sxs) vector<T> sxs(xs.size()+1); For(i, (int)xs.size()) sxs[i+1] = sxs[i] + xs[i]
#define Cin(T, ...) T __VA_ARGS__; _cin(__VA_ARGS__)
#define Cins(T, n, xs) vector<T> xs(n); For(i, n) cin >> xs[i]
#define Cins2(T, n, xs, ys) vector<T> xs(n), ys(n); For(i, n) cin >> xs[i] >> ys[i]
#define Cins3(T, n, xs, ys, zs) vector<T> xs(n), ys(n), zs(n); For(i, n) cin >> xs[i] >> ys[i] >> zs[i]
#define Cinss(T, n, m, xs) Vec2(T, n, m, xs); For(i, n) For(j, m) cin >> xs[i][j]
#define Cinm(T, n, map) unordered_map<T, int> map; Rep(n){ Cin(T, x); map[x] ++; }
#define Cout(...) _cout(__VA_ARGS__)
#define Couts(xs) for(const auto &e : xs) cout << e << " "; cout << "\n"
#define Coutyn(cond) Cout((cond) ? "yes" : "no")
#define CoutYn(cond) Cout((cond) ? "Yes" : "No")
#define CoutYN(cond) Cout((cond) ? "YES" : "NO")

// constexpr int MOD = 1e9+7;

int main(void){
    Cin(ll, a, b, c, k);
    Cout((a-b) * ((k % 2) ? -1 : 1));
}


Measured memory_bytes: 256
// E - Coprime
#include <bits/stdc++.h>
using namespace std;
#define rpd(i,s,e,d) for(int i=(s);i<(int)(e);i+=(d))

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

	int mx = 1000000;
	vector<int> D(mx+1, 0);
	rpd(i, 2, mx+1, 1)
		if(!D[i]) rpd(j, i, mx+1, i) D[j] = i;

	int N; cin>>N;
	int g = 0;
	bool not_pairwise = false;
	unordered_map<int, bool> past;
	rpd(i, 0, N, 1){
		int a; cin>>a;
		g = gcd(g, a);
		if(not_pairwise) continue;
		unordered_map<int, bool> now;
		while(a != 1){
			// 素数 D[a]: 今回は未済 & 過去は済
			if(( not_pairwise = !now[D[a]] && past[D[a]] )) break;
			now[D[a]] = past[D[a]] = true;
			a /= D[a];
		}
	}
	int t = not_pairwise + (g > 1);
	cout<< vector<string>{"pairwise","setwise","not"}[t] <<" coprime\n";
}


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

public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        InputStreamScanner in = new InputStreamScanner(System.in);
        new Main().solve(in, out);
        out.flush();
    }

    private void solve(InputStreamScanner in, PrintWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();

        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int p = in.nextInt();
            map.put(p, in.nextInt() + map.getOrDefault(p, new Integer("0")));
        }

        int c = 0;
        long t = 0;
        for (int price : map.keySet()) {
            int number = map.get(price);
            if (c + number >= m) {
                t += (long)price * (m - c);
                break;
            }
            t += (long)price * number;
            c += number;
        }

        out.println(t);
    }

    static class InputStreamScanner {

        private InputStream in;

        private byte[] buf = new byte[1024];
        private int len = 0;
        private int off = 0;

        InputStreamScanner(InputStream in)	{
            this.in = in;
        }

        String next() {
            StringBuilder sb = new StringBuilder();
            for (int b = skip(); !isSpace(b);){
                sb.appendCodePoint(b);
                b = read();
            }
            return sb.toString();
        }

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

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

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

        char nextChar() {
            return (char)skip();
        }

        int skip() {
            for (int b; (b = read()) != -1;) {
                if (!isSpace(b)) {
                    return b;
                }
            }
            return -1;
        }

        private boolean isSpace(int c) {
            return c < 33 || c > 126;
        }

        private int read() {
            if (len == -1) {
                throw new InputMismatchException("End of Input");
            }
            if (off >= len){
                off = 0;
                try {
                    len = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException(e.getMessage());
                }
                if (len <= 0) {
                    return -1;
                }
            }
            return buf[off++];
        }
    }
}

Measured memory_bytes: 48328
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <functional>
#include <queue>
#include <map>
#define REP(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
const int INF = 100000000;

int main(){
    string s;
    cin >> s;
    int count = 0;
    for(int i = 0; i < s.size(); i++){
        if(i % 2 != 0){
            if(s[i] == 'L' || s[i] == 'U' || s[i] == 'D'){
                count++;
            }
        }else{
            if(s[i] == 'R' || s[i] == 'U' || s[i] == 'D'){
                count++;
            }
        }
    }
    if(count == s.size()){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

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

int main()
{
	int n, a, b;
	cin >> n >> a >> b;

	int d, ans = 0;
	for (int i = 1; i <= n; i++) {
		d = (i%10)+(i/10%10)+(i/100%10)+(i/1000%10)+(i/10000);
		if (a <= d and d <= b) ans += i;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();

			System.out.println((a-1)*(b-1));

		}
	}


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

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

int cnt[2000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, X, Y;
    cin >> N >> X >> Y;
    X--;
    Y--;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int dist = j - i;
            dist = min(dist, abs(i - X) + 1 + abs(j - Y));
            cnt[dist]++;
        }
    }
    for (int i = 1; i < N; i++)
        cout << cnt[i] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int INF = INT_MAX / 2;
int main(){
    int N, L; cin >> N >> L;
    int m = INF, n;
    int all = 0;
    for (int i = 0; i < N; i++)
    {
        all += L + i;
        m = min(m, abs(L + i));
        if(L+i>=0) n = m;
        else n = -m; 
    }
    cout << all - n << endl;
}


Measured memory_bytes: 256
#coding:utf-8
N = int(input())
A = sorted(list(map(int, input().split())))
mn = A[0]
mx = A[-1]
ls_xy = []
for a in A[1:-1]:
    if a > 0:
        ls_xy.append([mn,a])
        mn -= a
    else:
        ls_xy.append([mx,a])
        mx -= a
ls_xy.append([mx,mn])
print (mx -mn)
[print (x,y) for x,y in ls_xy]



Measured memory_bytes: 24104
#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)
using ll = long long;
vector<int> lis(200005, 1e9), G[200005];
int ans[200005], a[200005];
void DFS(const int& v, stack<pair<int, int>>& s, int& cnt) {
	int k = lower_bound(lis.begin(), lis.end(), a[v]) - lis.begin();
	cnt = max(cnt, k + 1);
	s.push({k, lis[k]});
	lis[k] = a[v];
	ans[v] = cnt;
	for (auto nv : G[v]) {
		if (ans[nv] == 0) DFS(nv, s, cnt);
	}
	int p = s.top().first, q = s.top().second;
	if (p == cnt - 1 and q == 1e9) cnt--;
	s.pop();
	lis[p] = q;
	return;
}
int main() {
	int n;
	scanf("%d", &n);
	rep(i, n) scanf("%d", &a[i]);
	rep(i, n - 1) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	stack<pair<int, int>> s;
	int cnt = 0;
	DFS(0, s, cnt);
	rep(i, n) printf("%d\n", ans[i]);
	return 0;
}


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

#define ll  long long
#define PII pair<ll,ll>
#define VI  vector<ll>
#define VB  vector<bool>
#define VC vector<char>
#define VVI vector<vector<ll>>
#define VVC vector<vector<char>>
#define VS  vector<string>
#define VP  vector<PII>
#define lf(i,a,b) for(ll i=a;i<=b;i++)
#define lr(i,a,b) for(ll i=a;i>=b;i--)
#define lfl(i,v) for(ll i=0;i<v.size();i++)
#define lrl(i,v) for(ll i=(ll)(v.size())-1;i>=0;i--)
#define chk2(a,b) cout<<"check :  "<<a<<" "<<b<<endl
#define chk3(a,b,c) cout<<"check :  "<<a<<" "<<b<<" "<<c<<endl
#define chk4(a,b,c,d) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define chk5(a,b,c,d,e) cout<<"check :  "<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl
#define l_b(v,k)  lower_bound(v.begin(),v.end(),k)-v.begin()
#define u_b(v,k)  upper_bound(v.begin(),v.end(),k)-v.begin()
#define mod 1000000007
#define sort(v) sort(v.begin(),v.end())
#define p_b push_back
#define p_f push_front
#define m_p make_pair
#define fir first
#define sec second
#define sz size()
ll dp[2005];
ll fun(ll s)
	{	if(s==0)
			return 1;
		if(s<0)
			return 0;
		if(dp[s]!=-1)
			return dp[s];
		ll ans=0;
		for(ll i=3;i<=s;i++)
		{	ans=(ans+fun(s-i))%mod;
		}
		return dp[s]=ans;
	}
int main()
{	ll s;cin>>s;
	memset(dp,-1,sizeof(dp));
	cout<<fun(s)<<endl;
}	

Measured memory_bytes: 3644
n, c, k = map(int, raw_input().split())
arrive = []

for _ in xrange(n):
    arrive.append(input())
arrive = sorted(arrive)

i = 0
buses = 0
while i < len(arrive):
    dep = arrive[i] + k
    j = 1
    while j < c and len(arrive) > j + i:
        if arrive[j + i] <= dep:
            j += 1
        else:
            break
    buses += 1

    i += j

print buses



Measured memory_bytes: 7104
import sys
lines = sys.stdin.readlines()
line1 = lines.pop(0).split(' ')
lineA = lines.pop(0).split(' ')
lineB = lines.pop(0).split(' ')

minP = int(min(lineA)) + int(min(lineB))
#print(minP)

A = int(line1[0])
#print(A)
B = int(line1[1])
#print(B)
M = int(line1[2])
#print(M)

for i in range(M):
  line = lines.pop(0).split(' ')
  ax = int(line[0])
  bx = int(line[1])
  cx = int(line[2]) if len(line) == 3 else 0
  #print(ax)
  #print(bx)
  #print(cx)
  price = int(lineA[ax-1]) + int(lineB[bx-1]) - cx
  #print(price)
  if minP > price:
    minP = price

print(minP)
  



Measured memory_bytes: 24696
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<(int64_t)N;i++)
typedef int64_t LL;
int main()
{
  LL N,K,x,y;
  queue<LL> q;
  rep(i,9)q.push(i+1);
  cin>>K;
  rep(i,K)
  {
    x=q.front(),q.pop(),y=x%10;
    if(y!=0)q.push(10*x+y-1);
    q.push(10*x+y);
    if(y!=9)q.push(10*x+y+1);
  }
  return cout<<x<<endl,0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define INF 1000000000
#define MOD 1000000007LL
#define EPSILON 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 21
int x, y, z;

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

    cin >> x >> y >> z;
    swap(x, y);
    swap(x, z);
    cout << x << " " << y << " " << z << "\n";
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}

int main(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  // ll n;
  // cin >> n;
  ll n, m;
  cin >> n >> m;
  // ll n, m, k;
  // cin >> n >> m >> k;
  // int a[m], b[m];
  int a, b;
  int rel[n + 1][n + 1];
  zero(rel);
  fi(0, m) {
    // cin >> a[i] >> b[i];
    cin >> a >> b;
    rel[a][b] = 1;
    rel[b][a] = 1;
  }

  int per[n];
  fi(0, n) per[i] = i + 1;

  do {
    if(per[0] != 1) continue;
    int ok = 1;
    fi(0, n - 1) {
      if(!rel[per[i]][per[i + 1]]) {
        ok = 0;
        break;
      }
    }
    if(ok) ++ans;

  }while(next_permutation(per, per + n));
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,X,Y;
    cin>>n>>m>>X>>Y;
    vector<int> x(n);
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    vector<int> y(m);
    for(int i=0;i<m;i++){
        cin>>y[i];
    }
    sort(x.begin(),x.end());
    sort(y.begin(),y.end());
    int x_max = max(x[n-1],X);
    int y_min = min(y[0],Y);
    if(x_max < y_min){
        cout<<"No War"<<endl;
    }
    else{
        cout<<"War"<<endl;
    }
}

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

namespace cswork
{
    class Program
    {
        class Scanner
        {
            string[] s;
            int i;

            char[] cs = new char[] { ' ' };

            public Scanner()
            {
                s = new string[0];
                i = 0;
            }

            public string next()
            {
                if (i < s.Length) return s[i++];
                string st = Console.ReadLine();
                while (st == "") st = Console.ReadLine();

                s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
                i = 0;
                return next();
            }

            public int nextInt()
            {
                return int.Parse(next());
            }

            public long nextLong()
            {
                return long.Parse(next());
            }

            public double nextDouble()
            {
                return double.Parse(next());
            }
        }

        public Program() { }

        static void Main(string[] args)
        {
            new Program().Omame();
        }

        Scanner cin;
        const int MAXIN = 1024;
        bool[] used = new bool[MAXIN];
        int[] perm = new int[MAXIN];

        List<int[]> permList = new List<int[]>();

        public void Permutation(int pos, int n, int length)
        {
            if (pos == n)
            {
                permList.Add((int[])perm.Clone());
            }

            for (int i = 0; i < n; i++)
            {
                if (!used[i])
                {
                    perm[pos] = i;
                    used[i] = true;
                    Permutation(pos + 1, n, length);
                    used[i] = false;
                }
            }
        }

        public static List<long> GeneratePrime(long max)
        {
            long prime;
            double sqrtMax = Math.Sqrt(max);
            var primeList = new List<long>();

            List<long> searchList = new List<long>();
            for (long i = 2; i <= max - 1; i++)
            {
                searchList.Add(i);
            }

            do
            {
                prime = searchList.First();
                primeList.Add(prime);
                searchList.RemoveAll(n => n % prime == 0);
            } while (prime < sqrtMax);

            primeList.AddRange(searchList);

            return primeList;
        }

        void Omame()
        {
            cin = new Scanner();
            int n = cin.nextInt();

            for (int i = 0; i < n; i++)
            {
                int a = cin.nextInt();
                if (a % 2 == 0)
                {
                    if (a % 3 == 0 || a % 5 == 0)
                    {
                        continue;
                    }
                    else
                    {
                        Console.WriteLine("DENIED");
                        return;
                    }
                }
            }

            Console.WriteLine("APPROVED");
        }

    }
}


Measured memory_bytes: 11220
#include<iostream>
#include<vector>
#include<string>
#include<cstdio>

using namespace std;

int n;

char* moji(char* str)
{
	char temp[40000];
	
	char sub;
	int cont = 0, i = 0, cont2 = 0;
	/*
	for(int i = 0; str[i] != '\0'; i++){ 
		printf("%c",str[i]);
	}
	cout << endl;
	*/
	for(;;)
	{
		sub = str[i];
		cont = 0;
		for(;;i++){
			if(sub == str[i]){
				cont++;
			}
			else{
				break;
			}
		}
	//	printf("%dÂÌ%c¾æ\n",cont,sub);
		
		sprintf(temp+cont2, "%d\0", cont);
		while(temp[cont2] != '\0') cont2++;
		
		temp[cont2] = sub;
	//	printf("temp[%d] = %c\n",cont2,sub);
		cont2++;
		
		if(str[i] == '\0'){ 
			temp[cont2] = '\0';
			break;
		}
	}
	 
	n--;
	if(n == 0){
		for(int i = 0; temp[i] != '\0'; i++){
			if(isspace(temp[i]) == 1){
				break;
			}
			printf("%c",temp[i]);
		}
		cout << endl;
		return 0;
	}
	else{
		/*
		for(int i = 0; temp[i] != '\0'; i++){ 
			printf("%c",temp[i]);
		}
		cout << endl;
		*/
	    return moji(temp);
	}
}

int main()
{
	char temp[40000];
	for(;;){
		cin >> n;
		if(n == 0){
			break;
		}
		cin >> temp;
		moji(temp);
	}
}

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

using namespace std;
int main()
{
  int N, K; cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A[i];
  sort(A.begin(), A.end());
  int result = 0;
  for (int i = 0; i < K; i++) result += A[i];
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 3624
#include <stdio.h>

int main(void)
{
	int m,f,r;

	while(1){
		scanf("%d %d %d", &m, &f, &r);
		if(m==-1 && f==-1 && r==-1){	/*??\????????????*/
			break;
		}
		if(m==-1 || f==-1){		/*?¬???????F*/
			printf("F\n");
		}
		else if(80 <= m+f){		/*????¨????????????\??????A*/
			printf("A\n");
		}
		else if(65 <= m+f && m+f<80){	/*????¨????????????\??????????????????B*/
			printf("B\n");
		}
		else if(50 <= m+f && m+f<65){	/*????¨????????????\??????????????????C*/
			printf("C\n");
		}
		else if(30 <= m+f && m+f<50){	/*????¨????????????\?????????????????§*/
			if(50<=r)
				printf("C\n");	/*???????¨????????????\??????C*/
			else 
				printf("D\n");	/*???????¨???????????????????D*/
		}
		else if(m+f<30) {		/*???????¨?????????????????¨??????????????????????F*/
			printf("F\n");
		}
	}

	return 0;
}

Measured memory_bytes: 584
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
taoshita = 0
for i in range(n):
  if a[i] > b[i]: 
    taoshita += b[i]
    a[i] -= b[i]
  else:
    yusha = b[i] - a[i]
    if a[i+1] > yusha:
      taoshita += a[i]+yusha
      a[i+1] -=  yusha
      a[i] = 0
    else:
      taoshita += a[i] + a[i+1]
      a[i+1] -= a [i+1]
      a[i] = 0
print(taoshita)

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

typedef long long int ll;
typedef unsigned long long ull;
typedef double db;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
#define fi first
#define sc second 
#define w(n) while(n--)
#define f(i,n) for(ll i=1;i<=n;i++)
#define fr(i,n) for(ll i=0;i<n;i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
db pie=3.141592653589793238;
int main()
{
	 ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   ll t;
   t=1;
  //cin>>t;
   w(t)
   {
   		ll l,r,d;
   		cin>>l>>r>>d;
   		ll cnt=0;
   		for(int i=l;i<=r;i++)
   		{
   		    if(i%d==0)
   		    cnt++;
   		}
   		cout<<cnt<<"\n";
   }
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

int main(){
	int N,K;
	cin>>N>>K;
	if ((N+1)/2 >=K){
		cout<<"YES"<<endl;
	}
	else{
		cout<<"NO"<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
h=[int(input()) for i in range(n)]
h.sort()
hantei=10**9+1
for i in range(len(h)-k+1):
  if (h[i+k-1]-h[i])<hantei:
    hantei=h[i+k-1]-h[i]
print(hantei)

Measured memory_bytes: 7484
//
//  main.cpp
//  CoderProj
//
//  Created by Minoru Hayashi on 2020/03/12.
//  Copyright © 2020 Minoru Hayashi. All rights reserved.
//
//
//
//

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

#define REP(i,n) for (int i=0; i<(n); i++)
#define REP2(i,x,n) for (int i=x; i<(n); i++)
#define ALL(n) begin(n), end(n)

using ll = long long;

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

// const ll INF = 1LL<<60;
// const int INF = 1<<29;
// const ll MOD = 1000000007;

//#define __DBG__

int countbit(int a){
  int n=0;
  while(a>0){
    if(a%2){n++;}
    a/=2;
  }
  return n;
}

void solve(void){
  
  int N;
  cin >> N;
  vector<int> A(N);
  vector<vector<int>> X(N,vector<int>(N,0));
  vector<vector<int>> Y(N,vector<int>(N,0));
  
  REP(i,N){
    cin >> A[i];
    REP(j,A[i]){
      cin >> X[i][j] >> Y[i][j];
      X[i][j]--;
    }
  }
  
  vector<int> test(N);
  vector<int> mask(N);
  
  ll nmax=0;

  REP(i,N){
    mask[i]=0;
    test[i]=0;
    REP(j,A[i]){
      test[i] = test[i] | (Y[i][j]<<X[i][j]);
      mask[i] = mask[i] | (1<<X[i][j]);
    }
  }

  REP(k,pow(2,N)){
    bool flag=true;
    REP(i,N){
      if(((1<<i)&k)==0){continue;} // i not honest ignore
      // if honest
      if((k & mask[i])^test[i]){
        flag = false;
        break;
      }
    }
    if(flag){
      if(nmax<countbit(k)){nmax = countbit(k);}
    }
  }
  
  cout << nmax << endl;

  return;
   
}


int main(int argc, const char * argv[]) {

    cin.tie(0);
    ios::sync_with_stdio(false);

    solve();
 
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,K;
    cin >> N >> K;
    vector<int> l(N);
    for(int i=0;i<N;i++) cin >> l[i];
    sort(l.rbegin(),l.rend());
    int total = 0; 
    for(int i=0;i<K;i++){
        total += l[i];
    }
    cout << total << endl;
}

Measured memory_bytes: 256
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    H=LI()
    now = 0
    for h in H:
        if now > h:
            print("No")
            return
        now = max(now, h-1)
    print("Yes")
if __name__ == '__main__':
    main()

Measured memory_bytes: 17420
#include <bits/stdc++.h>
using namespace std;
using graph = vector<vector<int>>;

vector<int> articulation_point(const graph& G) {
	int n = G.size(), idx = 0;
	vector<int> low(n), ord(n), art;
	function<void(int)> dfs = [&](int v) {
		low[v] = ord[v] = ++idx;
		for (auto w : G[v]) {
			if (ord[w]) {
				low[v] = min(low[v], ord[w]);
				continue;
			}
			dfs(w);
			low[v] = min(low[v], low[w]);
			if ((ord[v] == 1 && ord[w] != 2)
				|| (ord[v] != 1 && low[w] >= ord[v])) art.push_back(v);
		}
	};
	for (int u = 0; u < n; ++u) {
		if (ord[u] == 0) idx = 0, dfs(u);
	}
	return art;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, m;
	cin >> n >> m;
	graph G(n);
	for (int i = 0; i < m; i++) {
		int s, t;
		cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
	}
	auto ap = articulation_point(G);
	sort(ap.begin(), ap.end());
	ap.erase(unique(ap.begin(), ap.end()), ap.end());
	for (auto v : ap) {
		printf("%d\n", v);
	}
	return 0;
}



Measured memory_bytes: 4704
import java.util.*;
import java.lang.*;
class Main
{
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    HashMap<Integer,Integer> m=new HashMap<Integer,Integer>();
    long sum=0;
    for(int i=0;i<n;i++)
    {
      int val=sc.nextInt();
      m.put(val,m.getOrDefault(val,0)+1);
      sum+=val;
    }
    int q=sc.nextInt();
    for(int j=0;j<q;j++)
    {
      int b=sc.nextInt();
      int c=sc.nextInt();
      if(m.containsKey(b))
      {
        int num=m.get(b);
        sum+=num*(c-b);
        m.remove(b);
        m.put(c,m.getOrDefault(c,0)+num);   
        //long l=(num*c);
        //long k=(num*b);
        //sum+=num*(c-b);
      }
      System.out.println(sum);
    }
  }
}


Measured memory_bytes: 65524
N = int(input())
H = list(map(int, input().split()))

def calc(i,j):
    SUM=0
    T=H[i:j]
    TH=H
    if(len(T)==0):
        return 0
    
    tmp=min(T)
    for a in range(i,j):
        H[a]-=tmp
    SUM+=tmp
    
    List=[n for n, v in enumerate(T) if v == min(T)]

    if(len(T)>1):
        B=0
        for b in List:
            SUM+=calc(i+B,i+b)
            B=b+1
        SUM+=calc(i+B,j)

    return SUM


if __name__ == "__main__":

    print(calc(0,N))
    
    exit()




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

int a[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};

int main(){
	int K; cin >> K;
	cout << a[K-1] << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;

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

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


int main(){
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    rep(i, N) cin >> h[i];
    vector<int> dp(N, 1LL << 30);
    dp[0] = 0;
    rep(i, N){
        for(int j = 1; j <= K; j++){
            if(i + j >= N) break;
            chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }
    cout << dp[N - 1] << endl;
}

Measured memory_bytes: 4052
#include <stdio.h>
#include <set>
#include <vector>
#include <utility>
typedef long long ll;
using namespace std;

typedef pair<ll, pair<ll, ll> > plll;

int main(void) {
  ll i, j, k, n, m, s, t;
  scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
  vector<plll> vec[n + 1];
  set< pair<ll, ll> > se;
  for(i = 0; i < m; ++i) {
    plll p1;
    ll u, v, a, b;
    scanf("%lld%lld%lld%lld", &u, &v, &a, &b);
    p1.first = v, p1.second.first = a, p1.second.second = b;
    vec[u].push_back(p1);
    p1.first = u;
    vec[v].push_back(p1);
  }
  ll dis1[n + 1], dis2[n + 1], now = s;
  for(i = 0; i <= n; ++i) dis1[i] = 10e15, dis2[i] = 10e15;
  dis1[s] = 0, dis2[t] = 0;
  for(i = 1; i <= n; ++i) {
    if(i != s) se.insert(make_pair(10e15, i));
  }
  for(k = 0; k < n - 1; ++k) {
    for(i = 0; i < vec[now].size(); ++i) {
      if(dis1[vec[now][i].first] > dis1[now] + vec[now][i].second.first) {
        pair<ll, ll> pp = make_pair(dis1[vec[now][i].first], vec[now][i].first);
        se.erase(se.find(pp));
        dis1[vec[now][i].first] = dis1[now] + vec[now][i].second.first;
        pp.first = dis1[vec[now][i].first];
        se.insert(pp);
      }
    }
    now = (*(se.begin())).second;
    se.erase(se.begin());
  }
  now = t;
  for(i = 1; i <= n; ++i) {
    if(i != t) se.insert(make_pair(10e15, i));
  }
  for(k = 0; k < n - 1; ++k) {
    for(i = 0; i < vec[now].size(); ++i) {
      if(dis2[vec[now][i].first] > dis2[now] + vec[now][i].second.second) {
        pair<ll, ll> pp = make_pair(dis2[vec[now][i].first], vec[now][i].first);
        se.erase(se.find(pp));
        dis2[vec[now][i].first] = dis2[now] + vec[now][i].second.second;
        pp.first = dis2[vec[now][i].first];
        se.insert(pp);
      }
    }
    now = (*(se.begin())).second;
    se.erase(se.begin());
  }
  ll min[n + 1];
  for(i = 1; i <= n; ++i) min[i] = dis1[i] + dis2[i];
  for(i = n - 1; i > 0; --i) min[i] = min[i] > min[i + 1] ? min[i + 1] : min[i];
  ll inf = 10e14;
  for(i = 1; i <= n; ++i) printf("%lld\n", inf - min[i]);
  return 0;
}

Measured memory_bytes: 19328
n = int(input())
s = input()
d = dict()

for i in s:
    if i in d.keys():
        d[i] += 1
    else:
        d[i] = 1

for j in range(n-1):
    s = input()
    d2 = dict()
    for i in s:
        if i in d.keys():
            if i in d2.keys():
                d2[i] += 1
            else:
                d2[i] = 1
    for k in d.keys():
        if not k in d2.keys():
           d[k] = 0
        else:
            if d[k] > d2[k]:
                d[k] = d2[k]

for k in sorted(d.keys()):
    for l in range(d[k]):
        print(k, end='')

print()


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,begin,end) for(int i=(begin),i##_end = (end);i<i##_end;i++)

int main()
{
    int l,r;
    cin>>l>>r;
    vector<vector<int> > dp(2019,vector<int>(2019));
    for(int i=0;i<=2018;i++)
        for(int j=i+1;j<=2018;j++)
            dp[i][j] = i*j%2019;
    if(r-l>=2018){
        cout<<0<<endl;
        return 0;
    }
    l = l%2019;
    r = r%2019;
    int mn = 2019;
    if(l<r){
        for(int k=l;k<r;k++)
            mn = min(mn,*min_element(dp[k].begin()+k+1,dp[k].begin()+r+1));
        cout<<mn<<endl;
    }
    else cout<<0<<endl;
    return 0;
}


Measured memory_bytes: 16256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility>
#define maxn 100005
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n;
struct dish{
	int a,b;
	bool operator < (const dish &x)const
	{
		return a + b > x.a + x.b;
	}
}d[maxn];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&d[i].a,&d[i].b);
	}
	sort(d + 1,d + n + 1);
	ll ans = 0;
	for(int i=1;i<=n;i++){
		if(i & 1) ans += d[i].a;
		else ans -= d[i].b;
	}
	printf("%lld\n",ans);
	return 0;
}


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

int main(){
    int A,B,C;
    cin >> A >> B >> C;
    if(A==B && A!=C){
        cout << "Yes" << endl;
    }
    else if(B==C && B!=A){
        cout << "Yes" << endl;
    }
    else if(A==C && A!=B){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

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

#define REP(type, i, a, b) for( type i = a; i < b; i++ )
typedef long long ll;

using namespace std;

int main (void) {
    ll N, ans, SqrN;
    ll Fact = 1;
    scanf("%lld", &N);
    SqrN = (ll)sqrt(N);
    for ( int i = 2; i <= SqrN; i++ ){
        if ( N % i == 0 ) Fact = i;
    }
    ans = Fact + N / Fact - 2;
    printf("%lld\n", ans); 
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8
N = int(input())

arrays = list("abcdefghij")
pat_dic = {i:arrays[i] for i in range(N)}
par_patterns = list(range(10))

patterns = par_patterns[:N]
def next_search(arr,N):
    tmp = arr.copy()
    if len(tmp) == N:
        print(''.join([pat_dic[tmp[i]] for i in range(N)]))
        return None
    for st in patterns:
        if max([0]+tmp)+1 < st:
            continue
        tmp.append(st)
        if tmp[0] != 0:
            continue

        next_search(tmp, N)
        tmp = arr.copy()

next_search([], N)

Measured memory_bytes: 4340
N,K = map(int, input().strip().split())
P = list(map(int, input().strip().split()))
P = [(p+1)/2 for p in P]

ans = sum(P[0:K])
now = ans
for i in range(1,N-K+1):
  now = now - P[i-1] + P[i+K-1]
  ans = max(ans, now)
print(ans)



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

#define pb push_back
#define rb  pop_back
#define rf  pop_front
#define ins insert
#define f   first
#define s   second
#define um  unordered_map
#define us  unordered_set
#define pq  priority_queue

typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
typedef pair< long long int ,long long int > iil;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef vector< ll > vl;
typedef vector< vl > vvl;
typedef vector<double> vd;
typedef pair<double,double> pd;
typedef queue<int> qi;
typedef queue<double> qd;
typedef queue<ll> qll;
typedef us<int> si;
typedef us<double> sd;
typedef us<ll> sll;
typedef vector<vd> md;


const int MAX = 1e6;
const int N = 200043;
const int MOD = 998244353;

#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define sz(a) int((a).size())
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for( auto i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define EE endl
#define PI 3.14159265
#define g(a,b) a>b?a:b
#define l(a,b) a<b?a:b
#define SOT(A) sort(A.begin(),A.end())
#define SOTR(A) sort(A.rbegin(),A.rend())
#define REV(a) reverse(ALL(a))

// LOOP Control Statements
#define forn(i,j,n) for ( auto i=j ; i<n ; i++ )
#define fornd(i,j,n) for ( auto i=j ; i>n ; i-- )
#define FORE(i, b) for(auto &i:b)


#define SQ(i) (i*i)
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define IN(a, b) (a.find(b) != a.end())
#define BACK(a) a.back(); a.RB()
#define QBACK(a) a.top(); a.pop()
#define PRINT(a) FORE(i, a) cout << i << " "; cout << endl
#define take(V,f,n) for(int i=f;i<f+n;i++) cin>>V[i]
#define tcase(term) int tc;cin>>tc;for(int term=0; cout<<"CASE "<<term+1<<EE,term<tc;term++)





int main()
{
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	// tcase(terms)
	{
		int n,k;
		cin>>n>>k;
		vi A(n,0);
		forn(i,0,n) cin>>A[i];
		while(k>0){
			vi P(n+1);
			forn(i,0,n){
				P[max(0,i-A[i])]++;
				P[min(n,i+1+A[i])]--;
			}
			forn(i,1,n+1){
				P[i]+=P[i-1];
			}
			bool same=true;
			forn(i,0,n){
				if(A[i]!=P[i]) same=false;
				A[i]=P[i];
			}
			if(same) break;
			k--;
		}
		forn(i,0,n) cout<<A[i]<<" ";

	}

}


Measured memory_bytes: 4844
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>

using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 130000, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;

	//うーん
	ll u_n = ((tmp & ma0) ^ ma0);
	if (!u_n) {
		ci += 8;
		while (*ci++ >= '0');
		return 1000000000;
	}
	int dig = 68 - __builtin_ctzll(u_n);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += (72 - dig >> 3);
	return tmp;
}

int B[200000];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint();

	int A[200000];
	rep(i, N) A[i] = getint();

	rep(i, N) if (i + A[i] < N) B[i + A[i]]++;

	ll kotae = 0;
	rep(i, N) if (i - A[i] >= 0) kotae += B[i - A[i]];

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 3288
import java.util.*;
class Main
{
    public static void main(String[] args) 
    {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = s.nextInt();
        }
        for(int i=0;i<b.length;i++)
        {
            b[i] = s.nextInt();
        }

        int ans=0;
        for(int i=0;i<n;i++)
        {
            if(a[i]>b[i])
            {
                ans+=(a[i]-b[i]);
            }
        }

        System.out.println(ans);
        

    
    }
    

}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb push_back
#define REP(i, a, b)  for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i=(a-1), i##end = (b); i >=i##end; --i)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int N = 100000;
const int oo = 0x3f3f3f3f;
 
template<typename T> T read() {
    T n(0), f(1);
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48; 
    return n * f;
}

int n;
bool vis[N + 5];

queue<pii> q;
map<pii, int> g;
multiset<int> s[N + 5];

bool solve() {
    int tot = 0;
    while(!q.empty()) {
        pii x = q.front(); q.pop();
        if(g[x] < 2) continue;

        ++ tot;
        g[x] -= 2;

        int u = x.fst, v = x.snd;
        if(s[u].size() > s[v].size()) swap(u, v);

        s[u].erase(v);
        s[v].erase(u);

        for(const auto& y : s[u]) {
            (y < u ? -- g[pii(y, u)] : -- g[pii(u, y)]);
            
            s[y].erase(u);

            s[y].insert(v);
            s[v].insert(y);

            if(y < v) {
                if(++ g[pii(y, v)] == 2) q.push(pii(y, v));
            }else {
                if(++ g[pii(v, y)] == 2) q.push(pii(v, y));
            }
        }
    }

    return tot == n-1;
}

int main() {
#ifdef Wearry
    freopen("data.txt", "r", stdin);
    freopen("ans.txt", "w", stdout);
#endif 

    scanf("%d", &n);
    for(int i = 1; i < n*2 - 1; ++i) {
        static int u, v;
        scanf("%d%d", &u, &v);
        if(u > v) swap(u, v);

        s[u].insert(v);
        s[v].insert(u);
        
        if(++ g[pii(u, v)] >= 2) q.push(pii(u, v));
    }
    
    puts(solve() ? "YES" : "NO");

    return 0;
}


Measured memory_bytes: 42752
#include <bits/stdc++.h>
using namespace std;
using P = pair<int64_t, int64_t>;

void fail() {
    cout << -1 << '\n';
    exit(0);
}

int main() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for(auto &e : a) cin >> e;
    if(n == 0 && a[0] != 1) fail();
    for(int i = 1; i < n + 1; ++i) {
        if(a[0] && a[i]) fail();
    }
    vector<P> pairs(n + 1);
    pairs[n] = make_pair(0, 0);
    for(int i = n - 1; i >= 0; --i) {
        int64_t l = (pairs[i + 1].first + a[i + 1] + 1) / 2;
        int64_t r = pairs[i + 1].second + a[i + 1];
        pairs[i] = make_pair(l, r);
    }
    vector<int64_t> cnt(n + 1);
    cnt[0] = 1;
    for(int i = 1; i < n; ++i) {
        cnt[i] = min(pairs[i].second, cnt[i - 1] * 2 - a[i]);
        if(cnt[i] < pairs[i].first) fail();
    }
    int64_t ans = 0;
    for(int i = 0; i < n; ++i) ans += cnt[i] + a[i];
    cout << ans + a[n] << '\n';
    return 0;
}


Measured memory_bytes: 6128
extern crate num_traits;
/// input macro from https://qiita.com/tanakh/items/1ba42c7ca36cd29d0ac8
macro_rules ! read_value {($ next : expr , ($ ($ t : tt ) ,* ) ) => {($ (read_value ! ($ next , $ t ) ) ,* ) } ; ($ next : expr , [$ t : tt ; $ len : expr ] ) => {(0 ..$ len ) . map (| _ | read_value ! ($ next , $ t ) ) . collect ::< Vec < _ >> () } ; ($ next : expr , chars ) => {read_value ! ($ next , String ) . chars () . collect ::< Vec < char >> () } ; ($ next : expr , usize1 ) => {read_value ! ($ next , usize ) - 1 } ; ($ next : expr , $ t : ty ) => {$ next () . parse ::<$ t > () . expect ("Parse error" ) } ; }
macro_rules ! input_inner {($ next : expr ) => {} ; ($ next : expr , ) => {} ; ($ next : expr , $ var : ident : $ t : tt $ ($ r : tt ) * ) => {let $ var = read_value ! ($ next , $ t ) ; input_inner ! {$ next $ ($ r ) * } } ; }
macro_rules ! input {(source = $ s : expr , $ ($ r : tt ) * ) => {let mut iter = $ s . split_whitespace () ; let mut next = || {iter . next () . unwrap () } ; input_inner ! {next , $ ($ r ) * } } ; ($ ($ r : tt ) * ) => {let stdin = std :: io :: stdin () ; let mut bytes = std :: io :: Read :: bytes (std :: io :: BufReader :: new (stdin . lock () ) ) ; let mut next = move || -> String {bytes . by_ref () . map (| r | r . unwrap () as char ) . skip_while (| c | c . is_whitespace () ) . take_while (| c |! c . is_whitespace () ) . collect () } ; input_inner ! {next , $ ($ r ) * } } ; }

macro_rules ! rough_print {($ x : expr $ (, $ s : expr ) * ) => {print ! ("{:?}" , $ x ) ; $ (print ! (", {:?}" , $ s ) ; ) * println ! ("" ) ; } ; }

fn gcd<T>(a: T, b: T) -> T
where
    T: num_traits::PrimInt,
{
    if b == T::from(0).unwrap() {
        a
    }
    else {
        gcd(b, a % b)
    }
}
fn gcd_list<T>(list: &[T]) -> T
where
    T: num_traits::PrimInt,
{
    list.iter().fold(list[0], |a, &b| gcd(a, b))
}

fn solve() {
    input!(n: usize, a: [usize; n]);

    if gcd_list(&a) != 1 {
        println!("not coprime");
        return;
    }

    let &a_max = a.iter().max().unwrap();
    let mut elist: Vec<usize> = (0..=a_max).collect();
    for i in 2..=a_max {
        if elist[i] == i {
            let mut j = 2;
            while (i * j) <= a_max {
                if elist[i * j] > i {
                    elist[i * j] = i;
                }
                j += 1;
            }
        }
    }

    let mut divided = vec![false; a_max + 1];
    for &_ai in &a {
        let mut ai = _ai;

        while ai != 1 {
            let p = elist[ai];

            while elist[ai] == p {
                ai /= p;
            }

            if divided[p] {
                println!("setwise coprime");
                return;
            }

            divided[p] = true;
        }
    }

    println!("pairwise coprime");
}

fn main() {
    std::thread::Builder::new()
        .name("solve".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(solve)
        .unwrap()
        .join()
        .unwrap();
}


Measured memory_bytes: 16776
a=[1,3,5,7,8,10,12]
b=[4,6,9,11]
c=[2]

x,y=map(int,input().split())

if (x in a and y in a) or (x in b and y in b) or (x in c and y in c):
    print('Yes')   
else:
    print('No')


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

int main()
{
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
    {
        if (i == 3)
        {
            s[i] = '8';
        }
    }

    cout << s << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define ld long double
#define pii pair<int,int>
#define fi first
#define se second
#define mex 1000005
#define fast  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//vector<int> adj[mex];
//a+b=a^b+2*(a&b)
int K[1024][100001];

int main(){
	fast
	int n;
	cin>>n;
	int val[n],wt[n];
	for(int i=0;i<n;i++)
	 cin>>val[i]>>wt[i];
	int W=100001;
	
	int n1=min((1<<10)-1,n);
	//vector<vector<int>> K(n+1,vector<int> (W+1));
	
	
	for (int i = 0; i <= n1; i++) { 
        for (int w = 0; w <= W; w++) { 
            if (i == 0 || w == 0) 
                K[i][w] = 0; 
            else if (wt[i - 1] <= w) 
                K[i][w] = max(val[i - 1] + K[i/2][w - wt[i - 1]],K[i/2][w]); 
            else
                K[i][w] = K[i/2][w]; 
        } 
    }
    int q;
    cin>>q;
    while(q--){
		int v,l;
		cin>>v>>l;
		if(v<((1<<10)-1))
		 cout<<K[v][l]<<"\n";
		else{
			int l1=1,x1=2;
			while(x1<=v){
				x1=x1*2;
				l1+=1;
			}
			ll ans=0;
			for(int i=0;i<(1<<(l1-10));i++){
				int nn=v;
				ll s1=0,s2=0;
				for(int j=0;j<(l1-10);j++){
					if(i&(1LL<<j)){
						s1=s1+wt[nn-1];
						s2=s2+val[nn-1];
					}
					nn=nn/2;
				}
				if(s1>l)
				 continue;
				else
				 ans=max(ans,s2+K[nn][l-s1]);
			 }
			 cout<<ans<<"\n";
		 }
	 }
				   	 
}


Measured memory_bytes: 405672
#include<iostream>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
using namespace std;
using ll=long long;


int main(){
    int n;
    cin>>n;
    vector<ll> a(n);
    vector<ll> b(n);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    ll tar=accumulate(a.begin(),a.end(),0LL);
    ll sum=accumulate(b.begin(),b.end(),0LL);
    ll cnt=0;
    priority_queue<pair<ll,int>> que;
    for(int i=0;i<n;i++) que.push({b[i],i});
    while(tar<sum && !que.empty()){
        auto tmp=que.top(); que.pop();
        int i=tmp.second;
        if(b[i]==a[i]) continue;
        ll x=b[(i+n-1)%n]+b[(i+1)%n];
        if(b[i]-x<=0) break;
        ll sndv=max({b[(i+n-1)%n],b[(i+1)%n],a[i]});
        ll tm=(b[i]-sndv)/x;
        if(tm<=0) tm=1;
        b[i]-=x*tm;
        sum-=x*tm;
        cnt+=tm;
        if(b[i]<=0) break;
        que.push({b[i],i});
    }
    if(a==b){
        cout<<cnt<<endl;
    }
    else{
        cout<<-1<<endl;
    }
    
    return 0;
}


Measured memory_bytes: 9636