akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define inf 1013161010
#define mod 1000000007
#define mod1 998244353
#define ll long long
#define lf long double
#define sz(x) ((int)x.size())
#define rep(i,n) for(i=0;i<n;i++)
#define rep1(i,a,b) for(i=a;i<=b;i++)
#define fr freopen("x.txt","r",stdin)
#define frc freopen("y.txt","w",stdout)
#define all(x) x.begin(),x.end()
#define set0(x) memset(x,0,sizeof(x))
#define dbg cout<<"yo "<<endl;
#define pset(n) fixed<<showpoint<<setprecision(n)

#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pair<int,int> >
#define vll vector<ll>
#define vpll vector<pair<ll,ll> >
#define si set<int>
#define mii map<int,int>
#define umii unordered_map<int,int>
#define vi vector<int>
#define pb push_back
#define ff first
#define ss second
#define mp make_pair

template<class T>
using min_pq = priority_queue<T,vector<T>,greater<T>>;

typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> OST;

ll toint(const string &s) { stringstream ss; ss << s; ll x; ss >> x; return x; }
string tostring ( ll number ){  stringstream ss; ss<< number; return ss.str();}

const lf pi = 2*acos(0);
const int nn = 500006;
const lf EPS = 0.000000001;

ll gcd(ll a,ll b){return (b==0)? a:gcd(b,a%b); }
ll fast_pow(ll a,ll m, ll mode) { if(m==0) return 1; else if(m==1) return a; ll h=fast_pow(a,m/2,mode); if(m%2==0) return ((h*h)%mode); else return ((((h*h)%mode)*a)%mode);}
ll mmi(ll b, ll mode){return fast_pow(b, mode-2, mode);}


int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll i,j,n,tt;
    tt=1;
    // cin>>tt;
    while(tt--)
    {
        ll n, a, b;
        cin>>n>>a>>b;
        cout<<min(a, b)<<" "<<max(0LL, a + b - n)<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
void main(){
  import std.stdio, std.string, std.conv, std.algorithm;
  import std.typecons;

  int n; rd(n);
  auto g=new int[][](n, 0);
  alias Edge=Tuple!(int, "a", int, "b");
  auto edges=new Edge[](n-1);
  foreach(i; 0..(n-1)){
    int a, b; rd(a, b);
    a--; b--;
    g[a]~=b; g[b]~=a;
    edges[i]=Edge(a, b);
  }
  auto s=readln.split.to!(long[]);

  auto sz=new long[](n), par=new int[](n);
  void dfs(int i, int p=-1){
    sz[i]=1;
    par[i]=p;
    foreach(j; g[i])if(j!=p){
      dfs(j, i); sz[i]+=sz[j];
    }
  }

  dfs(0);
  auto c=new long[](n-1);
  foreach(i, e; edges){
    auto a=e.a, b=e.b;
    if(par[a]==b) swap(a, b);  // a
    auto na=n-sz[b], nb=sz[b]; // |
    if(na==nb) continue;       // b
    c[i]=(s[a]-s[b])/(nb-na);
  }

  auto idx=-1;
  foreach(i; 0..(n-1)){
    if(c[i]==0){idx=i; break;}
  }
  if(idx==-1){
    writefln("%(%s\n%)", c); return;
  }

  alias T=Tuple!(int, "to", long, "c");
  auto g2=new T[][](n, 0);
  foreach(i, e; edges){
    g2[e.a]~=T(e.b, c[i]);
    g2[e.b]~=T(e.a, c[i]);
  }

  auto sz2=new long[](n);
  void dfs2(int i, int p=-1){
    sz2[i]=1;
    foreach(e; g2[i])if(e.to!=p){
      if(e.c>0) dfs2(e.to, i), sz2[i]+=sz2[e.to];
    }
  }

  long dfs3(int i, int p=-1){
    long ret=0;
    foreach(e; g2[i])if(e.to!=p){
      if(e.c>0) ret+=(dfs3(e.to, i)+e.c*sz2[e.to]);
    }
    return ret;
  }

  auto va=edges[idx].a, vb=edges[idx].b;
  dfs2(va); auto suba=dfs3(va);
  fill(sz2, 0);
  dfs2(vb); auto subb=dfs3(vb);
  c[idx]=(s[va]-(suba+subb))/sz2[vb];

  writefln("%(%s\n%)", c);
}


void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}

Measured memory_bytes: 32188
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
//#define PI 3.14159265358979

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

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	int M;
	if (N > 0)
		M = A[0].size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

typedef pair< int, int > pii;
typedef long long ll;

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge >
	edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(11);
	}
};
initializer _____;

int N, M, K, T, Q;
signed main() {
	cin >> N;
	string S;
	cin >> S;
	cin >> Q;
	while (Q--) {
		cin >> K;
		int D = 0;
		int M = 0;
		int DM = 0;
		int ans = 0;
		queue< char > q;
		rep(i, N) {
			switch (S[i]) {
			case 'D':
				++D;
				break;
			case 'M':
				++M;
				DM += D;
				break;
			case 'C':
				ans += DM;
			default:
				break;
			}
			q.push(S[i]);
			if (q.size() >= K) {
				char c = q.front();
				q.pop();
				if (c == 'D') {
					DM -= M;
					--D;
				} else if (c == 'M') {
					--M;
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 2316
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
//#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1e9+7;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
//llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	string str;
	int kaz[26]={0};
	while(cin>>str){
		for(auto it:str){
			if('a'<=it&&it<='z'){kaz[it-'a']++;}
			if('A'<=it&&it<='Z'){kaz[it-'A']++;}
		}
	}
	for(int c=0;c<26;c++){cout<<(char)(c+'a')<<" : "<<kaz[c]<<endl;}
	return 0;
}


Measured memory_bytes: 3224
using System;
using System.Collections.Generic;
using System.Text;

namespace ALDS1_3_C {
    class Program {
        static void Main(string[] args) {
            int n = int.Parse(Console.ReadLine());
            LinkedList<int> ll = new LinkedList<int>();
            for(int i = 0; i < n; i++) {
                string[] input = Console.ReadLine().Split(' ');
                switch (input[0]) {
                    case "insert":
                        ll.AddFirst(int.Parse(input[1]));
                        break;
                    case "delete":
                        ll.Remove(int.Parse(input[1]));
                        break;
                    case "deleteFirst":
                        ll.RemoveFirst();
                        break;
                    case "deleteLast":
                        ll.RemoveLast();
                        break;
                }
            }

            StringBuilder sb = new StringBuilder();
            foreach (var num in ll) {
                sb.AppendFormat(" {0}", num);
            }
            Console.WriteLine(sb.ToString().TrimStart());
        }
    }
}

Measured memory_bytes: 82348
import java.util.*;

public class Main {
    static long count = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //数列の長さ
        int[] a = new int[n]; //数列A
        for(int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        mergeSort(a, 0, n); //マージソート
        System.out.println(count); //反転数を出力する
    }
    /**
     * マージソート
     */
    static void mergeSort(int[] s, int left, int right) {
        if(left+1 < right) {
            int mid = (left+right)/2;
            mergeSort(s, left, mid); //先頭から中間まで
            mergeSort(s, mid, right); //中間から末尾まで
            merge(s,left,mid,right); //二つの配列を結合する
        }
    }
    /**
     * マージ
     */
    static void merge(int[] s, int left, int mid, int right) {
        int n1 = mid-left;
        int n2 = right-mid;
        int[] a = new int[n1+1];
        int[] b = new int[n2+1];
        for(int i=0; i<n1; i++) a[i] = s[left+i];
        for(int i=0; i<n2; i++) b[i] = s[mid+i];
        a[n1] = Integer.MAX_VALUE;
        b[n2] = Integer.MAX_VALUE;
        int i=0, j=0;
        for (int k=left; k<right; k++) {
            if(a[i]<=b[j]) {
                s[k] = a[i];
                i++;
                count += j;
            } else {
                s[k] = b[j];
                j++;
            }
        }
    }
}



Measured memory_bytes: 101428
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AizuOnlineJudge
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]ITP1_4_D 最小値、最大値、合計値

            //コンソールの設定を変更
            Console.SetIn(new StreamReader(Console.OpenStandardInput(131072),
                                           Console.InputEncoding, false, 131072));

            //2行目の値を読み込む
            string line = Console.ReadLine().TrimEnd();
            line = Console.ReadLine().TrimEnd();
            
            string[] array = line.Split(' ');

            var numbers = new List<long>();

            foreach(string s in array)
            {
                try
                {
                    int num = int.Parse(s);
                    numbers.Add(num);
                }
                catch(Exception)
                {
                    Console.WriteLine(s);
                }
                
            }

            long min = numbers.Min();
            long max = numbers.Max();

            //numbersの要素をlong型にしておかないと、
            //結果を受け取る変数(sum)の許容範囲内の数値でも
            //Sum()で合計を計算する途中でエラーが出る
            long sum = numbers.Sum();
            
            Console.WriteLine("{0} {1} {2}", min, max, sum);
        }
    }
}



Measured memory_bytes: 9552
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
template <class T>
inline void rd(T &x) {
	x=0; char c=getchar(); int f=1;
	while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); }
	while(isdigit(c)) x=x*10-'0'+c,c=getchar(); x*=f;
}
const int N=310;
int mod;
int n,m;
int f[N][N],s[N][N];
int C[N][N];
int main() {
	rd(n),rd(m),rd(mod);
	for(int i=0;i<=n;++i) for(int j=0;j<=i;++j) C[i][j]=j?(C[i-1][j-1]+C[i-1][j])%mod:1;
	for(int i=m;i>=0;--i) f[1][i]=1,s[1][i]=(s[1][i+1]+f[1][i])%mod;
	for(int i=2;i<=n+1;++i) {
		for(int j=0;j<=m;++j)
			for(int z=1;z<i;++z) {
				f[i][j]=(f[i][j]+f[i-z][j]*(ll)s[z][j+1]%mod*C[i-2][z-1]%mod)%mod;
//				if(i==n+1&&j==0) cout<<"trans:"<<z<<' '<<f[i][j]<<' '<<i-2<<' '<<z-1<<' '<<C[i-2][z-1]<<endl;
			}

		for(int j=m;j>=0;--j) s[i][j]=(s[i][j+1]+f[i][j])%mod;
	}
//	for(int i=1;i<=n+1;++i,puts(""))
//		for(int j=0;j<=m;++j)
//			printf("%d ",f[i][j]);
	printf("%d",f[n+1][0]);
	return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int maxn = 15;

int c[maxn], a[maxn][maxn], mid[maxn];
int n, m, x;
int main() 
{
    //ios::sync_with_stdio(0); cin.tie(0); //C++关同步
    cin >> n >> m >> x;
    for(int i = 0; i < n; ++i){
        cin >> c[i];
        for(int j = 0; j < m; ++j){
            cin >> a[i][j];
        }
    }
    int ans = -1;
    for(int i = 0; i < (1 << n); ++i){
        int cnt = 0, ins = i;
        memset(mid, 0, sizeof(mid));
        for(int j = 0; j < n; ++j){
            if(ins & (1 << j)){
                for(int k = 0; k < m; ++k){
                    mid[k] += a[j][k];
                }
                cnt += c[j];
            }
        }
        int flag = 1;
        for(int k = 0; k < m; ++k)if(mid[k] < x)flag = 0;
        if(flag == 1){
            if(ans == -1 || ans > cnt)ans = cnt;
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3672
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);
	int[] memo;
	ArrayList<Integer> lh, lr;

	void run() {
		for (;;) {
			int n = sc.nextInt();
			if (n == 0) return;
			lh = new ArrayList<Integer>();
			lr = new ArrayList<Integer>();
			for (int i = 0; i < n; i++) {
				lh.add(sc.nextInt());
				lr.add(sc.nextInt());
			}
			int m = sc.nextInt();
			for (int i = 0; i < m; i++) {
				lh.add(sc.nextInt());
				lr.add(sc.nextInt());
			}
			memo = new int[lh.size()];
			Arrays.fill(memo, -1);
			int max = 0;
			for (int i = 0; i < lh.size(); i++) max = Math.max(max, solve(i));
			System.out.println(++max);
		}
	}

	int solve(int ii) {
		if (memo[ii] != -1) return memo[ii];

		int res = 0;
		for (int i = 0; i < lh.size(); i++) {
			if (lh.get(i) < lh.get(ii) && lr.get(i) < lr.get(ii)) res = Math.max(res, solve(i) + 1);
		}
		return memo[ii] = res;
	}

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

Measured memory_bytes: 22412
#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
struct Road {
	int from, to, distance, cost;
};
int main() {
	while (true) {
		int n, m; std::cin >> n >> m; if (n == 0) break;
		std::vector<std::vector<std::pair<int, int>>> towns(n);
		std::vector<Road> roads(m); for (auto i = 0; i < m; ++i) {
			auto& r = roads[i];
			std::cin >> r.from >> r.to >> r.distance >> r.cost; --r.from; --r.to;
			towns[r.from].emplace_back(i, r.to);
			towns[r.to].emplace_back(i, r.from);
		}
		auto comparator = [](const std::pair<int, int> a, const std::pair<int, int> b) {return a.second > b.second; };
		std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(comparator)> queue(comparator); queue.emplace(0, 0);
		std::vector<int> min_distance(n, INT_MAX); min_distance[0] = 0;
		std::vector<int> min_road_count(n, 0);
		while (!queue.empty()) {
			auto top = queue.top(); queue.pop();
			if (min_distance[top.first] == top.second) {
				for (const auto& p : towns[top.first]) {
					if (min_distance[p.second] > roads[p.first].distance + top.second) {
						min_distance[p.second] = roads[p.first].distance + top.second;
						queue.emplace(p.second, min_distance[p.second]);
						min_road_count[p.second] = 1;
					}
					else if (min_distance[p.second] == roads[p.first].distance + top.second) {
						min_road_count[p.second]++;
					}
				}
			}
		}
		auto result = std::accumulate(roads.begin(), roads.end(), 0, [](const int acc, const Road &r) {return acc + r.cost; });
		std::sort(roads.begin(), roads.end(), [](const Road a, const Road b) {return a.cost > b.cost; });
		for (auto r : roads) {
			if (min_distance[r.from] + r.distance == min_distance[r.to]) {
				if (min_road_count[r.to] > 1) {
					--min_road_count[r.to];
					result -= r.cost;
				}
			}
			else if (min_distance[r.to] + r.distance == min_distance[r.from]) {
				if (min_road_count[r.from] > 1) {
					--min_road_count[r.from];
					result -= r.cost;
				}
			}
			else {
				result -= r.cost;
			}
		}
		std::cout << result << '\n';
	}
}


Measured memory_bytes: 4288
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define INT long long
#define MOD (int)1e9 +7
using namespace std;

int n;

int main()
{
    INT a, b;
    scanf("%lld%lld", &a, &b);
    if( a > 0 && b > 0 ) puts("Positive");
    else if( a*b < 0 ) puts("Zero");
    else if( b > 0 )
    {
        a*=(-1);
        if( a%2==0 ) puts("Positive");
        else puts("Negative");
    }
    else
    {
        a*=(-1), b*=(-1);
        a = a-b;
        if( a%2==1 ) puts("Positive");
        else puts("Negative");
    }
    return 0;
}


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

using namespace std;

int main(){

 long int k,n,m;

 cin>>k;
 cin>>n>>m;

 for(int i=n;i<=m;i++){

    if(i%k == 0){
        cout<<"OK"<<endl;
        return 0; }
 }

 cout<<"NG"<<endl;

return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAXN = 1e3 + 7, MOD = 1e9 + 7;

int fact[MAXN], invfact[MAXN], dp[MAXN], N, A, B, C, D;

int bpow(int a, int p)
{
    int ans = 1;
    for (; p > 0; p >>= 1) {
        if (p & 1) {
            ans = 1ll * ans * a % MOD;
        }
        a = 1ll * a * a % MOD;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) fact[i] = (1ll * fact[i - 1] * i) % MOD;
    invfact[MAXN - 1] = bpow(fact[MAXN - 1], MOD - 2);
    for (int i = MAXN - 1; i > 0; --i) invfact[i - 1] = 1ll * invfact[i] * i % MOD;

    dp[0] = 1;
    cin >> N >> A >> B >> C >> D;
    for (int x = A; x <= B; ++x) {
        for (int i = N; i >= x * C; --i) {
            for (int j = C; j <= D && j * x <= i; ++j) {
                long long add = dp[i - j * x];
                add = add * fact[N - (i - j * x)] % MOD;
                add = add * invfact[N - i] % MOD;
                add = add * bpow(invfact[x], j) % MOD;
                add = add * invfact[j] % MOD;
                dp[i] = ((dp[i] += add) >= MOD ? dp[i] - MOD : dp[i]);
            }
        }
    }

    cout << dp[N] << endl;
}


Measured memory_bytes: 256
n = int(input())
x = list(map(int, input().split()))
import numpy as np

x = np.array(x)
ans = [0]*101

for i in range(101):
    y = np.full(n, i)
    z = x-y
    z = np.power(z, 2)
    ans[i] = np.sum(z)

print(int(min(ans)))


Measured memory_bytes: 12500
import math
list_str = []
list1 = []
for i in range(5):
	a = input()
	list_str.append(list(a))
	list1.append(int(a))


abs_max = 10
count = 0
for i in range(5):
	if int(list_str[i][-1]) != 0 and int(list_str[i][-1]) < abs_max:
		abs_max = int(list_str[i][-1])
for i in range(5):
	count += math.ceil(list1[i]/10)

if abs_max == 10:
	print(int(count*10))
else:
	print(int(count*10)-10+abs_max)

Measured memory_bytes: 38384
class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None
class Tree:
    def __init__(self):
        self.root = None
        self.inorder = []
        self.preorder = []

    def insert(self, node):

        p = None
        x = self.root        
        while x is not None:
            p = x
            # print(node.key, x.key)
            if node.key <= x.key:
                x = x.left
            else:
                x = x.right

        # insertするnodeの親を設定
        node.parent = p

        if p is None:
            self.root = node
        else:
            # insertするnodeを親のleftかrightに設定
            if node.key <= p.key:
                # print('leftに設定')
                p.left = node
            else:
                # print('rightに設定')
                p.right = node

    def find(self, key):
        node = self.root
        while node is not None:
            if node.key == key:
                return True
            elif key <= node.key:
                node = node.left
            else:
                node = node.right
        return False

    def print_inorder(self):
        self.inorder = []
        self.inorder_traverse(self.root)
        print(' ' + ' '.join(map(str, self.inorder)))

    def print_preorder(self):
        self.preorder = []
        self.preorder_traverse(self.root)
        print(' ' + ' '.join(map(str, self.preorder)))

    def inorder_traverse(self, node):
        if node is None:
            return
        self.inorder_traverse(node.left)
        self.inorder.append(node.key)
        self.inorder_traverse(node.right)

    def preorder_traverse(self, node):
        if node is None:
            return
        self.preorder.append(node.key)
        self.preorder_traverse(node.left)
        self.preorder_traverse(node.right)

tree = Tree()
m = int(input())
for i in range(m):
    line = input().split()
    if line[0] == 'print':
        tree.print_inorder()
        tree.print_preorder()
    elif line[0] == 'insert':
        key = int(line[1])
        tree.insert(Node(key))
    elif line[0] == 'find':
        key = int(line[1])
        if tree.find(key):
            print('yes')
        else:
            print('no')
    # elif line[0] == 'delete':
    #     print("current tree----")
    #     print(tree.root.key)
    #     print(tree.root.left.key)
    #     print(tree.root.left.right.key)
    #     print("current tree----")
    #     key = int(line[1])
    #     node = tree.find(key)
    #     tree.delete(node)


Measured memory_bytes: 121528
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(x) for(auto it=(x).begin();it!=(x).end();it++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
//#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

using namespace std;

int main(){
    string s;
    int ans=0;
    while(cin>>s){
        
        bool ok=true;
        rep(i,0,s.size()/2){
            if(s[i]!=s[s.size()-i-1])ok=false;
        }
        if(ok)ans++;
    }
    cout<<ans<<endl;
    
    return 0;
}



Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
using namespace std;

/*int main()
{
    char s;
    while(cin>>s&&s!='\n')
    {
        if(s>='a'&&s<='z')
        {
            s-=0x20;
        }else if(s>='A'&&s<='Z')
        {
            s+=0x20;
        }
        cout<<s;
    }cout<<endl;
}*/
int main()
{
    string s;
    getline(cin,s);
    REP(i,s.size())
    {
        if(s[i]>='a'&&s[i]<='z')s[i]-=0x20;
        else if(s[i]>='A'&&s[i]<='Z')s[i]+=0x20;
    }
    cout<<s<<endl;
}



Measured memory_bytes: 3144
#include<bits/stdc++.h>
 
#define si(x) scanf("%d",&x)
#define sf(x) scanf("%lf",&x)
#define sl(x) scanf("%lld",&x)
#define pr(x) prllf("%d\n",x)
#define prll(x) printf("%lld\n",x)
 
#define ll long long int
#define ull unsigned long long ll
#define F first
#define S second
 
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define ii pair<ll,ll> 
#define pll pair<ll,ll> 
#define vi vector<ll> 
#define vvi vector< vi > 
#define vl vector<long long ll>
#define vvl vector< vl >
#define vii vector< ii >
#define vvii vector< vii >
#define priority_queue pq;
#define sz(a) ll((a).size()) 
#define pb push_back 
#define mp make_pair
 
#define ROUNDOFFINT(d) d = (ll)((double)d + 0.5)
#define SET(a,b) memset(a,b,sizeof(a))
#define all(c) (c).begin(),(c).end() 
#define tr(i,c) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define ison(x,i) (((x) >> (i)) & 1)	//checks if ith bit is on
#define set0(x,i) (x & ~(1 << i))		//set ith bit in x to be zero
#define clr(a) memset(a,0,sizeof(a))
 
#define MOD 1000000007
#define INF 4000000000000000000
#define MAX 100000+5
using namespace std;

vi v;
vi x;
map<ll,ll> m;


int main()
{
	ll n,p;
	sl(n);
	ll ans = 0;
	rep(i,0,n)
	{
		sl(p);
		auto it = m.find(p);
		if(it==m.end())
			m.insert(mp(p,1));
		else
		{
			it->S++;
			if(it->S==2)
				v.pb(p);
			if(it->S==4)
				ans = max(ans,p*p);
		}
	}
	sort(all(v));
	reverse(all(v));
	if(v.size()>=2)
		ans = max(ans,v[0]*v[1]);
	prll(ans);
	return 0;
}

Measured memory_bytes: 6528
import std.stdio;

int[double] map;

void main(){
	int id;
	double time;
	foreach (i; 0..3) {
		double[] times;
		foreach (j; 0..8) {
			readf("%d %s\n", &id, &time);
			map[time] = id;
			times ~= time;
		}
		auto tmp = times.sort;
		writefln("%d %.2f", map[tmp[0]], tmp[0]);
		writefln("%d %.2f", map[tmp[1]], tmp[1]);
		map.remove(tmp[0]);
		map.remove(tmp[1]);
	}
	auto tmp = map.keys.sort;
	writefln("%d %.2f", map[tmp[0]], tmp[0]);
	writefln("%d %.2f", map[tmp[1]], tmp[1]);
}

Measured memory_bytes: 1136
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <functional>
#include <stack>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <array>
#include <climits>
#include <cassert>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

const ll MOD = 1000000000 + 7;
const ll INF = LLONG_MAX;
const ll MAX_V = ll(1e5) + 5;
const double EPS = 10e-8;
const double PI = 3.14159265359;

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int main() {
    int n, a[100005];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int amax = a[n-1], dmin = amax+1, half;
    for (int i = 0; i < n; i++) {
        if (amax % 2 == 0 && abs(a[i] - amax / 2) < dmin) {
            dmin = abs(a[i] - amax / 2);
            half = a[i];
        } else if (amax % 2 == 1 && (abs(a[i] - amax / 2) < dmin ||
                                 abs(a[i] - 1 - amax / 2) < dmin)) {
            dmin = min(abs(a[i] - amax / 2), abs(a[i] - 1 - amax / 2));
            half = a[i];
        }
    }
    cout << amax << " " << half << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, sum = 0;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    sum += i;
    if (sum >= n) {
      printf("%d\n", i);
      return 0;
    }
  }
  return 0;
}


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

using namespace std;

struct Combination {
	vector<int64_t> _fact, _rfact, _inv;
	int64_t MOD;

	Combination(size_t sz, int64_t mod) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1), MOD(mod) {
		_fact[0] = _rfact[sz] = _inv[0] = 1;
		for (int i = 1; i <= sz; ++i) {
			_fact[i] = _fact[i - 1] * i % MOD;
		}
		_rfact[sz] = inverse(_fact[sz]);
		for (int i = sz - 1; i >= 0; --i) {
			_rfact[i] = _rfact[i + 1] * (i + 1) % MOD;
		}
		for (int i = 1; i <= sz; ++i) {
			_inv[i] = _rfact[i] * _fact[i - 1] % MOD;
		}
	}

	inline int64_t fact(int k) const { return _fact[k]; }
	inline int64_t rfact(int k) const { return _rfact[k]; }
	inline int64_t inv(int k) const { return _inv[k]; }

	int64_t inverse(int64_t x) const { return pow(x, MOD - 2); }
	int64_t pow(int64_t x, int64_t n) const {
		int64_t ret = 1;
		while (n > 0) {
			if (n & 1) { (ret *= x) %= MOD; }
			(x *= x) %= MOD;
			n >>= 1;
		}
		return ret;
	}

	int64_t P(int n, int r) const {
		if (r < 0 || n < r) { return 0; }
		return fact(n) * rfact(n - r) % MOD;
	}
	int64_t C(int n, int r) const {
		if (r < 0 || n < r) { return 0; }
		return fact(n) * rfact(r) % MOD * rfact(n - r) % MOD;
	}
	int64_t H(int n, int r) const {
		if (n < 0 || r < 0) { return 0; }
		return r == 0 ? 1 : C(n + r - 1, r);
	}
};

int main() {
	constexpr Int MOD = 998244353;
	Int N, M, K;
	cin >> N >> M >> K;

	Combination cb(N + 1, MOD);
	Int ans = 0;
	for (Int k = 0; k <= K; ++k) {
		Int tmp = cb.C(N - 1, k) * M % MOD;
		(tmp *= cb.pow(M - 1, N - k - 1)) %= MOD;
		(ans += tmp) %= MOD;
	}
	cout << ans % MOD << endl;

	return 0;
}


Measured memory_bytes: 7936
x,n = map(int,input().split())
p = [int(i) for i in input().split()]
x_abs = 100000
ans = []
for i in range(-2,102):
    if i in p:
        continue
    if x_abs > abs(x-i):
        ans = i
        x_abs = abs(x-i)
    elif x_abs == abs(x-1):
        ans = min(ans, i)
print(ans)

Measured memory_bytes: 9132
import bisect
nibutan=bisect.bisect_left
def splitintinput():
    return [int(i) for i in input().split()]
N,M=splitintinput()
A=splitintinput()
A.sort()
BC=[splitintinput() for _ in range(M)]
#Cが大きい順にソート
BC.sort(reverse=True,key=lambda x:x[1])
#AのうちC未満のものを小さいほうからB個ソート
done=0
for B,C in BC:
    if done>=N:break
    index=nibutan(A,C,lo=done)#indexはそれより小さいものの数
    if index==done:break
    for j in range(done,min(done+B,index)):
        A[j]=C
        done+=1
print(sum(A))


Measured memory_bytes: 83480
#include <stdio.h>

const int Mod = 1000000007;

int main()
{
	int i, N, A;
	long long sum = 0, ans = 0;
	scanf("%d", &N);
	scanf("%d", &A);
	for (i = 2, sum = A; i <= N; i++) {
		scanf("%d", &A);
		ans = (ans + sum * A) % Mod;
		sum = (sum + A) % Mod;
	}
	printf("%lld\n", ans);
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1704
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	for i := range as {
		fmt.Scan(&as[i])
	}
	counter := make(map[int]int)
	for _, a := range as {
		counter[a]++
	}
	cnt := 0
	for _, c := range counter {
		if c%2 == 1 {
			cnt++
		}
	}
	fmt.Println(cnt)
}


Measured memory_bytes: 8704
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(int i=(int)(st),i##end=(int)(ed);i<=i##end;++i)
#define DREP(i,st,ed) for(int i=(int)(st),i##end=(int)(ed);i>=i##end;--i)
template<typename T>bool chkmin(T &x,const T &y){return x>y?x=y,1:0;}
template<typename T>bool chkmax(T &x,const T &y){return x<y?x=y,1:0;}
template<typename T>T read(){
	T x=0,f=1;
	char c=getchar();
	while((c<'0')||(c>'9')){if(c=='-')f=-1;c=getchar();}
	while((c>='0')&&(c<='9'))x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
#define read() read<int>()
template<typename T>void write(T x,char c){
	static char t[25];
	static int tlen;
	t[tlen=1]=c;
	if(x<0)putchar('-'),x=-x;
	do t[++tlen]=(x%10)^48;
	while(x/=10);
	while(tlen)putchar(t[tlen--]);
}
const int maxn=200005;
int n,m;
int a[maxn],dp[maxn];
vector<int>g[maxn];
struct seg_tree{
	int Min[maxn<<2];
	void update(int p,int l,int r,int L,int R,int x){
		if((L<=l)&&(R>=r)){chkmin(Min[p],x);return;}
		int mid=(l+r)>>1,u=p<<1,v=u+1;
		if(L<=mid)update(u,l,mid,L,R,x);
		if(R>mid)update(v,mid+1,r,L,R,x);
	}
	int query(int p,int l,int r,int pos){
		if(l==r)return Min[p];
		int mid=(l+r)>>1,u=p<<1,v=u+1,res=Min[p];
		if(pos<=mid)chkmin(res,query(u,l,mid,pos));
		else chkmin(res,query(v,mid+1,r,pos));
		return res;
	}
}T;
int main(){
	n=read();
	REP(i,1,n)a[i]=a[i-1]+(read()^1);
	m=read();
	REP(i,1,m){
		int l=read(),r=read();
		g[r].push_back(l-1);
	}
	memset(T.Min,0x3f,sizeof(T.Min));
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	REP(i,1,n){
		dp[i]=dp[i-1]+(a[i]-a[i-1]==0);
		REP(j,0,g[i].size()-1){
			int tmp=min(dp[g[i][j]]-a[g[i][j]],T.query(1,0,n,g[i][j]));
//			cout<<i<<' '<<g[i][j]<<' '<<tmp+a[i]<<' '<<endl;
			chkmin(dp[i],tmp+a[i]);
			T.update(1,0,n,g[i][j]+1,i,tmp);
		}
//		cout<<i<<' '<<dp[i]<<endl;
	}
//	REP(i,1,n)
//		write(dp[i],i==n?'\n':'\n');
	write(dp[n],'\n');
	return 0;
}

Measured memory_bytes: 14464
n,m = map(int,input().split())

k = []
for i in range(m):
    tmp = list(map(int,input().split()))
    k.append(tmp)

p = list(map(int,input().split()))

t = [False for i in range(n)]


_ = True
counter = 0
while(_):
    flag = True
    hantei = True



    for e,ki in enumerate(k):
        tmp = False
        for i in range(1,ki[0]+1):
            if t[ki[i]-1] == tmp:
                tmp = False
            else:
                tmp = True

        if p[e] != tmp:
            hantei = False
    if hantei:
        counter+=1


    for i in range(n):
        if flag and t[i]:
            t[i] = not t[i]
        elif flag:
            t[i] = not t[i]
            flag = False

    if flag:
        break

print(counter)

Measured memory_bytes: 3064
# encoding:utf-8
import copy
import numpy as np
import random

n,m,x = map(int,input().split())

a = [int(i) for i in input().split()]



#migi
cost_r = 0
for i in range(x,n):
    if i in a:
        cost_r += 1

cost_l = 0
for i in range(x):
    if i in a:
        cost_l += 1

print(min(cost_l,cost_r))


Measured memory_bytes: 13420
#include "bits/stdc++.h"
#define ll long long
using namespace std;
int main(){
char tmp;
cin>>tmp;
switch(tmp){
  case 'A':
  printf("T\n");
  break;
  case 'T':
  printf("A\n");
    break;
  case 'G':
  printf("C\n");
    break;
  case 'C':
  printf("G\n");
    break;
}

  return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
ma = []

for i in range(H):
    a = [input()]
    a.insert(0,"#")
    a.append("#")
    ma.append(a)

x = "#"*(W+2)

print(x)
for i in range(H):
    print("".join(ma[i]))  
print(x)
     



Measured memory_bytes: 3316
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <limits.h>
using namespace std;


int main(){
  int H, N ;
  cin >> H >> N ;
  int A[N] ;
  int B[N] ;
  for(int i=0;i<N;i++){
    cin >> A[i] >> B[i] ;
  }  
  int DP[H + 1] ;
  DP[0] = 0 ;
  for(int i=1;i<(H+1);i++){
    DP[i] = INT_MAX ;
    for(int j=0;j<N;j++){
      if(i >= A[j]){
        if(DP[i] > (DP[(i-A[j])] + B[j]) ){
          DP[i] = DP[(i-A[j])] + B[j] ;
        }  
      }
      else{
        if(DP[i] > B[j] ){
          DP[i] = B[j] ;
        }
      }  
    }  
  }  
  cout << DP[H] << endl ;
  return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define vi vector <int>
#define endl "\n"
#define f(n) for(int i=0;i<n;i++)
#define vvi vector <vector<int> >
#define vii vector <pair<int,int> >
#define rep(i,a,b) for (int i=a;i<b;i++)
#define repD(i,a,b) for (int i=a;i>=b;i--)
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define gcd __gcd
#define init(i,k) memset(i,k,sizeof i)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define setBits(x) __builtin_popcountll(x)
#define pii pair <int,int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define N 100005
#define mod 1000000007
int dp[N];
void solve()
{
	int n,k;
	cin>>n>>k;
	vi v(n);
	f(n)
		cin>>v[i];
	sort(v.begin(),v.end());
	for(int i=1;i<=k;i++)
	{
		for(auto x:v)
		{
			if(x<=i)
			{
				if(dp[i-x]==0)
				{
					dp[i]=1;
				}
			}
		}
	}
	if(dp[k]==1)
	{
		cout<<"First"<<endl;
	}
	else
	{
		cout<<"Second"<<endl;
	}
	return;
}
signed main()
{
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)
    {
    	//cout<<"Case #"<<i<<": ";
    	solve();
    	//cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 4368
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author alireza_kaviani
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<ld, ld> pld;
typedef pair<string, string> pss;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define set_random                  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline ll input() {
    ll n;
    cin >> n;
    return n;
}

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

set_random;

const ll MAXN = 2.5e7 + 10;
const ll INF = 1e15;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

ll n , ans , ga[4] , gb[4] , dp[MAXN] , dp2[MAXN];

int main() {
    fast_io;
    for(ll j = 0 ; j < MAXN ; j++){
        dp[j] = -INF;
        dp2[j] = -INF;
    }

    cin >> n >> ga[1] >> ga[2] >> ga[3] >> gb[1] >> gb[2] >> gb[3];

    dp[n] = 0;
    for(ll i = 1 ; i < 4 ; i++){
        for(ll j = MAXN - 1 ; j >= ga[i] ; j--){
            dp[j - ga[i]] = max(dp[j - ga[i]] , dp[j] + gb[i]);
        }
    }

    n = 0;
    for(ll i = 0 ; i < MAXN ; i++)  n = max(n , i + dp[i]);

    dp2[n] = 0;
    for(ll i = 1 ; i < 4 ; i++){
        for(ll j = MAXN - 1 ; j >= gb[i] ; j--){
            dp2[j - gb[i]] = max(dp2[j - gb[i]] , dp2[j] + ga[i]);
        }
    }

    n = 0;
    for(ll i = 0 ; i < MAXN ; i++)  n = max(n , i + dp2[i]);

    cout << n << endl;

    return 0;
}
/*
todo :
    1- set constants
    2- check TimeLimit and MemoryLimit
    3- check special test cases
    4- don't forget BS can help you that is good idea(use for loop for floats)
    5- don't forget printf and scanf can help you in your code speed
*/


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

using namespace std;
vector<vector<int>> g, ind;

vector<int> ord;

vector<bool> usd;
vector<vector<int>> gr;
vector<int> comp;
void ts(int u)
{
	if (usd[u])
		return;
	usd[u] = true;
	for (int v : g[u])
		ts(v);
	ord.push_back(u);
}

void scc(int u, int c)
{
	if (comp[u] != -1)
		return;
	comp[u] = c;
	for (int v : gr[u])
		scc(v, c);
}

int main()
{
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	g.resize(n);
	gr.resize(n);
	ind.resize(n);
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		--a, --b;
		g[a].push_back(b);
		gr[b].push_back(a);
		ind[a].push_back(i);
	}
	usd.resize(n);
	for (int i = 0; i < n; ++i)
		ts(i);
	reverse(ord.begin(), ord.end());
	comp.resize(n, -1);
	int c = 0;
	for (int x : ord)
	{
		if (comp[x] == -1)
			scc(x, c++);
	}
	vector<vector<int>> g1(c);
	for (int i = 0; i < n; ++i)
		for (int j : g[i])
			if (comp[i] != comp[j])
				g1[comp[i]].push_back(comp[j]);
	for (auto& x : g1)
	{
		//sort(x.begin(), x.end());
		//x.resize(unique(x.begin(), x.end()) - x.begin());
	}
	vector<vector<int>> cc(c);
	for (int i = 0; i < n; ++i)
		cc[comp[i]].push_back(i);
	vector<bool> diff(m);
	for (int i = 0; i < c; ++i)
	{
		vector<int> q;
		vector<int> cnt(c, 0), from(n, -1);
		cnt[i] = 2;
		from[i] = i;
		for (int j : g1[i])
			if (cnt[j] == 0)
				cnt[j] = 1, from[j] = j, q.push_back(j);
			else if (cnt[j] == 1)
				++cnt[j];
		for (int it = 0; it < q.size(); ++it)
		{
			int x = q[it];
			for (int y : g1[x])
			{
				if (cnt[y] == 2)
					continue;
				if (cnt[x] == 2)
					cnt[y] = 2, q.push_back(y);
				else if (cnt[y] == 1)
				{
					if (from[y] == from[x])
						continue;
					else
						cnt[y] = 2, q.push_back(y);
				}
				else 
					cnt[y] = 1, from[y] = from[x], q.push_back(y);
			}
		}
		for (int x : cnt)
			cerr << x << ' ';
		cerr << '\n';
		for (int i1 : cc[i])
			for (int j = 0; j < g[i1].size(); ++j)
				if (i != comp[g[i1][j]] && cnt[comp[g[i1][j]]] == 2)
					diff[ind[i1][j]] = true;
	}
	for (int i = 0; i < n; ++i)
	{
		vector<int> q;
		vector<int> cnt(n, 0), from(n, -1);
		cnt[i] = 2;
		from[i] = i;
		for (int j : g[i])
			cnt[j] = 1, from[j] = j, q.push_back(j);
		for (int it = 0; it < q.size(); ++it)
		{
			int x = q[it];
			for (int y : g[x])
			{
				if (cnt[y] == 2)
					continue;
				if (cnt[x] == 2)
					cnt[y] = 2, q.push_back(y);
				else if (cnt[y] == 1)
				{
					if (from[y] == from[x])
						continue;
					else
						cnt[y] = 2, q.push_back(y);
				}
				else 
					cnt[y] = 1, from[y] = from[x], q.push_back(y);
			}
		}
		for (int j = 0; j < g[i].size(); ++j)
			if (comp[i] == comp[g[i][j]] && cnt[g[i][j]] != 2)
				diff[ind[i][j]] = true;
	}
	for (int i = 0; i < m; ++i)
		if (diff[i])
			cout << "diff\n";
		else
			cout << "same\n";
}


Measured memory_bytes: 6912
#include <iostream>
#include <vector>
#include <tuple>
#include <cmath>
#include <algorithm>
using namespace std;
vector<tuple<int,int,int,int>> vec;

int calAns(vector<int>& A){
    int ans = 0;
    for(auto it : vec){
        int a,b,c,d;
        tie(a,b,c,d) = it;
        if(A[b-1]-A[a-1] == c)
            ans += d;
    }
    return ans;
}

int sol(vector<int>& A, int cur, int end, int m){
    if(cur == end){
        return calAns(A);
    }
    int res = 0;
    int s = A.size() ? A[cur-1] : 1;

    for(int i = s; i <= m ; ++i){
        A.push_back(i);
        res = max(res,sol(A,cur+1, end,m));
        A.pop_back();
    }
    return res;
}

int main(){
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 0,a,b,c,d; i < q ; ++i){
        cin >> a >> b >> c >> d;
        vec.emplace_back(a,b,c,d);
    }
    vector<int> A;
    cout << sol(A,0,n,m);

    return 0;
}

Measured memory_bytes: 3568
// prob name -
//author - COOL
#include <bits/stdc++.h>
#define f(i, n) for (int i = 0; i < n; i++)
#define ff first
#define ss second
#define int long long int
#define mii map<int, int>
#define vi vector<int>
#define fi(i, a, n)             \
    for (int i = 0; i < n; i++) \
    {                           \
        cin >> a[i];            \
    }
#define fo(i, a, n)             \
    for (int i = 0; i < n; i++) \
    {                           \
        cout << a[i] << " ";    \
    }
#define PB push_back
#define MP make_pair
#define pqb priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define mk(arr, n, type) type *arr = new type[n];
#define pw(b, p) pow(b, p) + 0.1
#define w(x)  \
    int x;    \
    cin >> x; \
    while (x--)
#define Pi 3.14159265358979
using namespace std; //_S_A_R_T_H_A_k_//
/// JAI SHREE RAM!!! ;{'*' <_l_> '*' };
/// Saare jahan se acha hindustan humara .....
/// JAI HIND DOSTON //-__ -//
int32_t main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
        int n,k;
        cin >> n>>k;
        // if(k>=n){
        //     cout<<0<<endl;
        //     return 0;
        // }
        int a[n+1];
    for (int  i = 1; i <= n; i++)
   {
     cin>>a[i];
   }
       // fi(i, a, n)
   int dp[n+1]={0};
   for (int  i = 0; i < n; i++)
   {
     dp[i] = 0;
   }
   
       dp[1] = 0; 
     //  dp[1] = abs(a[0]-a[1]);
   for(int i=2;i<=n;i++)
   { 
     int ans =inf;
     for (int  j = 1; j <= k; j++)
     {     if(i-j>0)
     ans = min(dp[i-j] + abs(a[i]-a[i-j]),ans); 
    }
     dp[i] = ans;
   }
   cout<<dp[n]<<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <set>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	set<int> s;
	int cnt=1;
	for(int i=0;i<=20;i++){
		s.insert(cnt);
		cnt*=2;
	}
	int n; cin >> n;
	if(s.find(n)!=s.end()){
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	cout << 1+n << " " << 2 << endl;
	cout << 2 << " " << 3+n << endl;
	cout << 3+n << " " << 1 << endl;
	cout << 1 << " " << 2+n << endl;
	cout << 2+n << " " << 3 << endl;
	if(n%2){
		for(int i=n;i>3;i-=2){
			int x=i^1;
			cout << i << " " << x << endl;
			cout << x << " " << 1 << endl;
			cout << 1 << " " << i+n << endl;
			cout << i+n << " " << x+n << endl;
		}
	}
	else{
		int y=*s.lower_bound(n);
		y/=2;
		cout << n << " " << y << endl;
		cout << (((n^y)^1)+n) << " " << n+n << endl;
		for(int i=n-1;i>3;i-=2){
			int x=i^1;
			cout << i << " " << x << endl;
			cout << x << " " << 1 << endl;
			cout << 1 << " " << i+n << endl;
			cout << i+n << " " << x+n << endl;
		}
	}
}

Measured memory_bytes: 2304
from itertools import product
n,a,b,c=map(int,input().split())
abc=[a,b,c]
l=tuple(int(input()) for _ in range(n))

ans=10**18
for a in product(range(4), repeat=n):
    MP=0
    take=[[] for _ in range(4)]

    for i in range(n):
        take[a[i]].append(l[i])
    
    if take[0] and take[1] and take[2]:
        for i,t in enumerate(take[:-1]):
            MP+=max(0, 10*(len(t)-1))
            MP+=abs(abc[i] - sum(t))
    else:
        continue

    ans=min(ans, MP) 

print(ans)


Measured memory_bytes: 3064
//Author:- S_Aditya

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
#define ll long long 
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld",n)
#define pri(n) printf("%d",n)
#define pln() printf("\n")
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define rep(i,init,n) for(int i=init;i<n;i++)
#define pb push_back     
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define inf INT_MAX
#define ninf INT_MIN
const ll mod=1e9+7;         
const int N=1e5+4;

int main()                  
{
    int n,k;
    
    scn(n); scn(k);
    
    int a[n],dp[n];
    
    rep(i,0,n)
    {
        scn(a[i]);
        
        dp[i]=inf;
    }
    
    dp[0]=0;
    
    rep(i,1,n)
    {
        rep(j,1,k+1)
        if(i-j>=0)
        {
            int here=dp[i-j]+abs(a[i]-a[i-j]);
            
            dp[i]=min(dp[i],here);
        }
    }
    
    pri(dp[n-1]);
    
} 

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

#define rep(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const ll INF = (1LL << 60)-1;

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

  ll x, y; cin >> x >> y;
  ll ans = INF;

  if(x <= y) ans = min(ans, y-x);
  if(-x <= y) ans = min(ans, 1+x+y);
  if(x <= -y) ans = min(ans, 1-x-y);
  if(-x <= -y) ans = min(ans, 2+x-y);

  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<map>
#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n;
    cin>>n;
    int h[n];
    int K;
    cin>>K;
    for(int i=0;i<n;i++)
        cin>>h[i];

    long long dp[n];
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for(int i=2;i<n;i++)
    {
        dp[i]=LONG_MAX;
        for(int k=1;k<=K &&i-k>=0 ;k++)
        dp[i]=min(dp[i], dp[i-k]+abs(h[i]-h[i-k]));
    }
    cout<<dp[n-1];
    return 0;
}


Measured memory_bytes: 1408
def main():
    n=int(input())
    a=list(map(int,input().split()))
    l=sum(a)
    cnt=0
    j=n
    for i in range(n):
        cnt+=a[i]
        if cnt>l/2:
            j=i
            break
    aa=sum(a[:j])
    b=sum(a[j:])
    c=sum(a[:j+1])
    d=sum(a[j+1:])
    print(min(abs(aa-b),abs(c-d)))
main()

Measured memory_bytes: 26220