akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std; inline void fileio(const char* in, const char* out) { freopen(in, "r", stdin); freopen(out, "w", stdout); } 
#define TD typedef
#define forx(i,n) for(int i = 0; i < (n); ++i)
TD long long ll; TD long double ld; TD pair<int,int> pii; TD pair<ll, ll> pll; TD vector<int> VI; TD vector<bool> VB; TD vector<ll> VL;
const char nl = '\n'; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fll; const ld EPS = 1e-9, PI = acos(-1);
#define ff first
#define ss second

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  // Emily <3
  int n, a, b;
  cin >> n >> a >> b;
  cout << min(n*a, b) << nl;
  
  cerr << "Time: " << (ld)clock() / CLOCKS_PER_SEC << nl;
  return 0;
}



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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

int toInt(string s) {
	return strtol(s.c_str(),0,0);
}

bool check(vector<int>& v) {
	int N = v.size();
	for (int i = 1; i < N; i += 2) {
		if (v[i-1] >= v[i]) return false;
	}
	for (int i = 2; i < N; i += 2) {
		if (v[i-1] <= v[i]) return false;
	}
	return true;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int N;
	while (cin >> N, N) {
		vector<string> s(N); cin >> s;
		vector<int> v(N);
		REP(i, N) {
			if (s[i] != "x") v[i] = toInt(s[i]);
		}
		set<int> kh;
		REP(i,N) {
			for (int d = -2; d <= 2; ++d) {
				kh.insert(v[i]+d);
			}
		}
		int cnt = 0, ans = 114514;
		EACH(x,kh) {
			REP(i,N) if (s[i] == "x") v[i] = x;
			if (check(v)) {
				++cnt;
				ans = x;
			}
		}
		if (cnt == 1) {
			cout << ans << endl;
		}
		else if (cnt == 0) {
			cout << "none" << endl;
		}
		else {
			cout << "ambiguous" << endl;
		}
/*
		vector<int> l = v, r = v;
		REP(i,N) {
			if (s[i] == "x") {
				l[i] = -inf;
				r[i] = inf;
			}
		}
		REP(i, N) {
			if (s[i] == "x") {
				if (i % 2 == 0) {
					r[i] = max(r[i], r[i-1]-1);
				}
				else if (i % 2 == 1) {
				}
			}
		}
*/
	}
}

Measured memory_bytes: 3384
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;

int main()
{
    long long N;
    cin >> N;
    map<int, int> mp;
    REP (i, N) {
        int a;
        cin >> a;
        mp[a]++;
    }
    int ans = 0;
    for (auto itr = mp.begin(); itr != mp.end(); itr++) {
        if (itr->second % 2 == 1)
            ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a)  (a).begin(),(a).end()

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

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

const ll INF = 1LL << 60;

int main(){
  ll s; cin >> s;
  const int v = 1e9;
  int x,y;
  x = (v - s%v)%v;//最後の %v は s%v=0 のときのため
  y = (s+x)/v;
  std::cout << "1000000000 1 " << x << ' ' << y << " 0 0" <<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

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

typedef long long ll;

int SURP = 1000000007;

int main(){
	int N;
	cin >> N;
	int ret = 0;
	REP(i,N){
		int a;
		cin >> a;
		while (a%2 == 0){
			a = a/2;
			ret++;
		}
	}
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<unordered_set>
#include<vector>

#define ll long long
#define P pair<int,int>
#define FOR(i,N) for(int i=0;i<(int)N;i++)
#define FORIN(i,a,b) for(int i=a;i<(int)b;i++)
#define ALL(x) (x).begin(),(x).end()
#define LAST(x) (x)[(x).size()-1]
#define GI(name) int (name);scanf("%d",&(name))
#define GI2(name1,name2) int (name1),(name2);scanf("%d %d",&(name1),&(name2))
#define GI3(name1,name2,name3) int (name1),(name2),(name3);scanf("%d %d %d",&(name1),&(name2),&(name3))
#define GVI(name,size) vector<int> (name)(size);FOR(i,(size))scanf("%d",&(name)[i])
#define MOD 1000000007

using namespace std;

string to_hex(int x){
    stringstream ss;
    ss<<hex<<x;
    return ss.str();
}

inline int get_int(){
    int ret;
    scanf("%d",&ret);
    return ret;
}

inline vector<int> get_ints(int n){
    vector<int> ret(n);
    FOR(i,n){
        scanf("%d",&ret[i]);
    }
    return ret;
}

inline string get_str(){
    string ret;
    cin>>ret;
    return ret;
}

bool is_prime(int n){
    int s=sqrt(n)+1;
    for(int i=2;i<=s;++i){
        if(n%i==0){
            return 0;
        }
    }
    return 1;
}

vector<P> prime_division(int n){
    vector<P> ret;
    int s=sqrt(n)+1;
    int c=0;
    for(int i=2;i<=n;++i){
        if(n%i==0){
            c=0;
            do{
                ++c;
                n/=i;
            }while(n%i==0);
            ret.push_back(P(i,c));
        }
    }
    return ret;
}

string to_string(string s){
    return s;
}

template<class T>
string to_string(vector<T> v){
    string ret="{";
    FOR(i,v.size()-1){
        ret+=to_string(v[i])+",";
    }
    if(v.size()>0){
        ret+=to_string(LAST(v));
    }
    ret+="}";
    return ret;
}

void debug_print(){
    cerr<<endl;
}

template<class Head,class... Tail>
void debug_print(Head head,Tail... tail){
    cerr<<to_string(head)<<" ";
    debug_print(tail...);
}

template<class... T>
void debug(T... args){
    cerr<<"["<<__LINE__<<"]: ";
    debug_print(args...);
}

void print(){
    cout<<endl;
}

template<class Head,class... Tail>
void print(Head head,Tail... tail){
    cout<<to_string(head);
    print(tail...);
}

int main(){
    GI2(N,K);
    GVI(l,N);
    sort(ALL(l),greater<int>());
    int ans=0;
    for(int i=0;i<K;++i)ans+=l[i];
    print(ans);
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        //set array
        String[] st = br.readLine().split(" ");
        int[] array = new int[n];
        for (int i = 0; i < n; i++){
            int a = Integer.parseInt(st[i]);
            array[i] = a;
        }
        
        int count = bubbleSort(array);
        printArray(array);
        System.out.println(count);
        
    }
    static void printArray(int[] arr){
        for (int i = 0; i < arr.length - 1; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println(arr[arr.length-1]);
    }
    static void printArray2(int[] arr){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length - 1; i++){
            sb.append(arr[i]);
            sb.append(" ");
        }
        sb.append(arr[arr.length - 1]);
        System.out.println(sb.toString());
    }
    static int bubbleSort(int[] arr){
        //bubble sort and count swaps
        int swapcnt = 0;
        for (int i = 0; i < arr.length; i++){
            for (int j = arr.length - 1; j > i; j--){
                if ( arr[j] < arr[j-1]){
                    swap(arr, j, j - 1);
                    swapcnt += 1;
                }
            }
        }
        return swapcnt;
    }
    static void swap(int[] arr, int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

Measured memory_bytes: 17072
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef long long LL;
typedef double DB;
const int Max = 1e5;
const int MOD = 1e9 + 7;


int n, m;
char a[10];
int main()
{
	scanf("%s", &a);
	int sum = 1;
	for(int i = 1; i < 4; i++)
	{
		if(a[i] == a[i - 1]) sum++;
		if(sum >= 3) break;
		if(a[i] != a[i - 1]) sum = 1;
	}
	if(sum >= 3) printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;

int e,minimum;

int solve(){
    minimum = e;
    for(int z=0;z*z*z<=e;z++){
        for(int y=0;y <= sqrt(e);y++){
            int x = e - z*z*z - y*y;
            if(x>=0)
                minimum = min(x+y+z,minimum);
        }
    }
    return minimum;
}

int main(){
    while(cin >> e && e!=0){
        cout << solve() << endl;
    }
}

Measured memory_bytes: 1160
#include<iostream>
#include<cstdio>
#include<vector>

struct Res{
	int i, j, k, r;
};

int data[310];
std::vector<Res> v;

int main(){
	while(true){
		for(int i = 0; i < 310; i++)data[i] = 2;
		v.clear();

		int a, b, c;
		int n;

		scanf("%d %d %d", &a, &b, &c);
		if(a == 0 && b == 0 && c == 0)break;
		scanf("%d", &n);

		for(int i = 0; i < n; i++){
			Res r;
			scanf("%d %d %d %d", &r.i, &r.j, &r.k, &r.r);
			if(r.r == 1)data[r.i] = 1, data[r.j] = 1, data[r.k] = 1;
			else v.push_back(r);
		}

		for(int i = 0; i < v.size(); i++){
			if(data[v[i].i] == 1 && data[v[i].j] == 1)data[v[i].k] = 0;
			if(data[v[i].i] == 1 && data[v[i].k] == 1)data[v[i].j] = 0;
			if(data[v[i].j] == 1 && data[v[i].k] == 1)data[v[i].i] = 0;
		}

		for(int i = 1; i <= a + b + c; i++){
			printf("%d\n", data[i]);
		}
	}
	return 0;
}

Measured memory_bytes: 1236
N, K = map(int, input().split())
h=[]
for i in range(N):
    h.append(int(input()))

h.sort()

min_d = 10**9
for i in range(N-K+1):
    min_d = min(h[i+K-1] - h[i],min_d)

print(min_d)

Measured memory_bytes: 7488
fun main(args: Array<String>) {
    while (true){
        val (h, w) = readLine()?.split(" ")?.map { it.toInt() } ?: return
        if (h == 0 && w == 0) return
        for (i in h downTo 1){
            for (j in w downTo 1){
                when{
                    j == 1 -> println("#")
                    i == 1 || i == h || j == w -> print("#")
                    else -> print(".")
                }
            }
        }
        println("")
    }
}


Measured memory_bytes: 39188
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int main(){
    //~ freopen("file.in", "r", stdin);
    int x;
    scanf("%d",&x);
    printf("%d\n",48-x);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define max 1000000
#define pb push_back
#define pairs pair<int, int>
#define vi vector<int>
#define vb vector<bool>
#define vii vector<pairs>
#define lb lower_bound
#define ub upper_bound
#define lli long long int
#define endl '\n'
#define FastInput ios_base::sync_with_stdio(false), cin.tie(NULL);
#define Cases  cout << "Case " << ++Case << ": ";
#define __test int tt; int Case=0; cin >> tt; while(tt--)
#define read(x) freopen(x, "r", stdin)
#define write(x) freopen(x, "w", stdout)
#define InputArray(a,n) for(int i=0;i<n;i++) cin >> a[i];
#define CopyArray(a,temp,n) for(int i=0;i<n;i++) temp[i]=a[i];
#define PrintArray(a,n) for(int i=0;i<n;i++) cout << a[i] << " "; cout << endl;
using namespace std;


int main() {
#ifdef Niloy
	read("input.txt");
	write("output.txt");
#endif

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	int x = (a + d - 1) / d;
	int y = (b + c - 1) / b;

	cout << (x >= y ? "Yes\n" : "No\n");

	cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
	return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define inf (int)(3e18)
#define P pair<int,int>
#define mod (int)(1e9+7)

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

template<class T> inline void chmin(T &a, T b) {
	a = min(a, b);
}
template<class T> inline void chmax(T &a, T b) {
	a = max(a, b);
}

int N,A[300005];
int mx[300005],mn[300005];
multiset<int>stmx,stmn;
signed main() {
	cin>>N;
	rep(i,3*N)cin>>A[i];
	rep(i,N){
		mx[N-1]+=A[i];
		stmx.insert(A[i]);
	}
	for(int i=N;i<2*N;i++){
		mx[i]=mx[i-1];
		int j=*stmx.begin();
		if(A[i]>j){
			mx[i]+=A[i];mx[i]-=j;
			stmx.erase(stmx.begin());
			stmx.insert(A[i]);
		}
	}
	for(int i=3*N-1;i>=2*N;i--){
		mn[2*N]+=A[i];
		stmn.insert(A[i]);
	}
	for(int i=2*N-1;i>=N;i--){
		mn[i]=mn[i+1];
		int j=*--stmn.end();
		if(A[i]<j){
			mn[i]+=A[i];mn[i]-=j;
			stmn.erase(--stmn.end());
			stmn.insert(A[i]);
		}
	}
	int ans=-inf;
	for(int i=N-1;i<2*N;i++)chmax(ans,mx[i]-mn[i+1]);
	cout<<ans<<endl;
}



Measured memory_bytes: 15360
n,k = map(int,input().split())
arr=list(map(int,input().split()))
arr.sort()
dp=[-1]*(k+1)

for i in range(1,k+1):
    m=1
    for j in arr:
        if(i>=j):
            m = min(dp[i-j],m)
    dp[i] = -1*m

if(dp[k]==1):
    print("First")
else:
    print("Second")

Measured memory_bytes: 42220
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define reps(i, m, n) for (int i = m; i < n; i++)
#define repr(i, m, n) for (int i = m; i >= n; i--)
#define db(x) cout << #x << "=" << x << endl;
template <class T>
bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define INF2 1000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
#define EPS 1e(-9);
using namespace std;
typedef long long ll;
//--GLOBAL---------------------------------

//--MAIN-----------------------------------
void Main() {
    string S;
    cin >> S;
    int N=S.length();

    ll ans=0;
    int now=0;
    int ct=1;
    int ma=0;

    rep(i,N){
        if(S[i]=='<'){
            ++now;
            ans+=now;
            ma=now;
        }
        else{
            if(now==0){
                if(ma==ct) ++ct;
                ans+=ct;
                ++ct;
            }
            else{
                now=0;
                ans+=now;
                ct=1;
            }
        }
    }

    cout<< ans<<"\n";

}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 1172
n=int(input())
s=input()
a=[]
last=s[-1]
a.append(s)

for i in range(n-1):
  s=input()
  a.append(s)
  if s[0]!=last:
    print('No')
    break
  last=s[-1]
  if i==n-2 and len(a)==len(set(a)):
    print('Yes')
  elif i==n-2:
    print('No')
    

Measured memory_bytes: 3060
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.bigint, std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
T lcm(T)(T x, T y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998_244_353;
//long mod = 1_000_003;
void moda(T)(ref T x, T y) { x = (x + y) % mod; }
void mods(T)(ref T x, T y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(T)(ref T x, T y) { x = (x * y) % mod; }
void modpow(T)(ref T x, T y) { if (!y) { x = 1; return; } auto t = x; x.modpow(y>>1); x.modm(x); if (y&1) x.modm(t); }
void modd(T)(ref T x, T y) { y.modpow(mod - 2); x.modm(y); }

struct UnionFind(T)
{
	void init(T n) { par = new T[](n); foreach (i; 0..n) par[i] = i; cnt = new T[](n); fill(cnt, 1); }
	T root(T i) { return par[i] == i ? i : (par[i] = root(par[i])); }
	bool same(T i, T j) { return root(i) == root(j); }
	void unite(T i, T j) { i = root(i); j = root(j); if (i == j) return; par[i] = j; cnt[j] += cnt[i]; }
	T size(T i) { return cnt[root(i)]; }
	T[] par, cnt;
}

void main()
{
	auto N = RD;
	auto Q = RD;
	UnionFind!long uf;
	uf.init(N);
	foreach (i; 0..Q)
	{
		auto t = RD;
		auto u = RD;
		auto v = RD;
		if (t == 0)
		{
			uf.unite(u, v);
		}
		else
		{
			auto r = uf.same(u, v);
			writeln(r ? 1 : 0);
		}
	}
	
	stdout.flush;
	debug readln;
}


Measured memory_bytes: 14216
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;
int n , num[100][200] , ans[200];
char a[100][100];
int main(){
	while(~scanf("%d" , &n)){
		memset(num , 0 , sizeof(num));
		memset(ans , 0 , sizeof(ans));
		for(int i = 1;i <= n;i++){
			scanf("%s" , a[i] + 1);
			for(int j = 1;j <= strlen(a[i] + 1);j++)
				num[i][a[i][j]]++;
		}
		int ok = 0;
		for(char i = 'a';i <= 'z';i++){
			if(num[1][i] != 0){
				ans[i] = num[1][i];
				for(int j = 2;j <= n;j++){
					ans[i] = min(ans[i] , num[j][i]);
				}
				if(ans[i] != 0) ok++;
			}
		}
		if(!ok) printf(" \n");
		else {
			for(char i = 'a';i <= 'z';i++){
				if(ans[i]){
					for(int j = 1;j <= ans[i];j++){
						printf("%c" , i);
					}
				}
			}
			printf("\n");
		}
	}
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
//#include <iostream>//POJ
//#include <vector>
//#include <string>
//#include <iomanip>
//#include <math.h>
using namespace std;
#define setc cin.tie(0);ios::sync_with_stdio(0)
#define repi(i,a,b) for(int i=(a), i##_len=(b); i<i##_len; ++i)
#define rep(i,n) repi(i,0,n)
#define repi_(i,a,b) for(int i=(a), i##_len=(b); i<=i##_len; ++i)
#define rep_(i,n) repi_(i,0,n)
#define all(x) (x).begin(),(x).end()
#define vsort(v) sort((v).begin(), (v).end())
#define gsort(v) tsort(v); reverse((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())
template<typename T> T vpop(vector<T> *v) {
	T res = v->back();
	v->pop_back();
	return res;
}
char vpop(string *v) {
	char res = v->back();
	v->pop_back();
	return res;
}
#define siz(v) ((int)(v).size())
#define ers(v, n) (v).erase((v).begin() + n)
#define cnt(v, n) count(all(v), n)
#define vmin(v) *min_element(v.begin(), v.end())
#define vmax(v) *max_element(v.begin(), v.end())
#define contain(q) !q.empty()
#define cont(q) !q.empty()
//#define qpop(q, a, b) a=q.back().first;b=q.back().second;q.pop()
//#define pqpop(p, a, b) a=q.top().first;b=q.top().second;q.pop()
#define el "\n"
#define sp " "
#define co(x) cout<<(x)<<el
#define coc(c, a, b) if(c)co((a));else co((b))
#define cosp(x) cout<<(x)<<' '
#define YES(c) coc(c,"YES", "NO")
#define Yes(c) coc(c,"Yes", "No")
#define yes(c) coc(c,"yes", "no")
#define POSSIBLE(c) coc(c, "POSSIBLE", "IMPOSSIBLE")
#define Possible(c) coc(c, "Possible", "Impossible")
#define possible(c) coc(c, "possible", "impossible")
#define inf INT_MAX
#define wildcard(T) numeric_limits<T>::min()

#define pb push_back
#define pq priority_queue
#define np next_permutation

#ifdef tqktmp_2
#define gc() getchar(); getchar()
#else
#define gc() 1
#endif
const unsigned int bf0 = (1 << 0);
const unsigned int bf1 = (1 << 1);
const unsigned int bf2 = (1 << 2);
const unsigned int bf3 = (1 << 3);
const unsigned int bf4 = (1 << 4);
const unsigned int bf5 = (1 << 5);
const unsigned int bf6 = (1 << 6);
const unsigned int bf7 = (1 << 7);

typedef long long lint;
typedef vector<int> ivec; typedef vector<string> svec;
typedef vector<vector<int>> ivvec;
typedef pair<int, int> P;

const int
	dx8[8] = { 0,1,1,1,0,-1,-1,-1 },
	dy8[8] = { 1,1,0,-1,-1,-1,0,1 },
	dx4[4] = { 0,1,0,-1 },
	dy4[4] = { 1,0,-1,0 };

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

int main() {
	setc;

	lint n; cin >> n;
	bool f=0;
	rep(i, 25) {
		rep(j, 25) {
			if (4 * i + 7 * j == n) { f = 1; break; }
		}
	}
	Yes(f);
	gc();
}


Measured memory_bytes: 256
N = int(input())
Tree = [[] for _ in range(N+1)]
UVW = []

for _ in range(N-1):
  u, v, w = map(int, input().split())
  Tree[u].append(v)
  Tree[v].append(u)
  UVW.append((u, v, w))

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in Tree[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

dis = [0] * (N+1)

for u, v, w in UVW:
  if parent[u] == v:
    dis[u] = w
  else:
    dis[v] = w

color = [-1] * (N+1)
color[root] = 0

for x in order:
  for y in Tree[x]:
    if y == parent[x]:
      continue
    if dis[y]%2 == 0:
      color[y] = color[x]
    else:
      color[y] = color[x] ^ 1

for i in range(1, N+1):
  print(color[i])

Measured memory_bytes: 39304
#include <iostream>
#define f first
#define s second
#define pb push_back
#define ENDL '\n'
#define all(a) begin(a),end(a)
#define sz(a) (int)(a.size())
#define deb(a) cout << #a << " = " << a << ENDL;
#define fore(i, a, b) for(int i(a), ThkMk(b); i < ThkMk; ++i)
#define _ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli> ii;


int main()
{   _
    string s, t; cin >> s >> t;
    int cnt = 0;
    fore(i, 0, sz(s)) if(s[i] != t[i]) ++cnt;
    cout << cnt << ENDL;
    return 0;
}


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

using namespace std;
const int maxn=3e5+5;
int a[maxn];
int main()
{
    int n, i, j;
    long long s2=0, s1=0;
    cin>>n;
    for(i=0; i<n; i++){scanf("%d", &a[i]);s2+=a[i];}
    long long ans=1e16;
    for(i=0; i<n-1; i++)
    {
        s1+=a[i];
        s2-=a[i];
        ans=min(ans, abs(s1-s2));
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1024
#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 INF = (1<<30);
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const int mod = 1000000007;
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
};
mint dp[2][2005][2005];

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n+1), t(m+1);
    rep(i, n) scanf("%d", &s[i]);
    rep(i, m) scanf("%d", &t[i]);
    dp[0][0][0] = 1;
    rep(i, n+1)rep(j, m+1){
        dp[0][i+1][j] += dp[0][i][j];
        dp[1][i][j] += dp[0][i][j];
        dp[1][i][j+1] += dp[1][i][j];
        if(s[i]==t[j]){
            dp[0][i+1][j+1] += dp[1][i][j];
        }
    }
    mint ans = dp[1][n][m];
    cout << ans.x << endl;
    return 0;
}

Measured memory_bytes: 63232
N=int(input())
S=[]
T=[]
for i in range(N):
	s=str(input())
	S.append(s)
for j in range(N):
	X=sorted(str(S[j])[k] for k in range(10))
	Y=X[0]+X[1]+X[2]+X[3]+X[4]+X[5]+X[6]+X[7]+X[8]+X[9]
	T.append(Y)
R=sorted(T)

l,r=0,0
ans=0
while r<N:
	if R[r]==R[l] and r==N-1:
		ans=ans+int((r-l)*(r-l+1)/2)
		r=r+1
	elif R[r]==R[l]:
		r=r+1
	else:
		ans=ans+int((r-l-1)*(r-l)/2)
		l=r
print(int(ans))

Measured memory_bytes: 18524
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPP(i,m,n) for(long long i=m;i<n;++i)
#define rep(i,n) for(long long i = n-1;i>=0;--i)
#define repp(i,n,m) for(long long i = n-1; i >= m; --i)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
#define pq priority_queue
#define Dcout(N) cout << setprecision(20) << N << endl
constexpr int INF = 2147483647;
constexpr long long INFF = 9223372036854775807;

ll A,B,C,D;

ll GCD(ll A,ll B){
    if(B == 0) return A;
    else return GCD(B,A%B);
}

bool solve(){
    if(A < B) return 0;
    if(D < B) return 0;
    if(C >= B - 1) return 1;
    ll G = GCD(B,D);
    //ll maxv = (C - A + G -1)/G;
    //if(A + G*maxv < B) return 0;
    ll Max = (B - A%G + G - 1)/G*G + A%G - G;
    if(Max > C) return 0;
    else return 1;
}

signed main() {
    cin.tie(0);
	ios::sync_with_stdio(false);
    int T;cin >> T;
    bool flag = 0;
    REP(query,T){
        flag = 0;
        cin >> A >> B >> C >> D;
        if(!solve()) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  int X, N;
  cin >> X >> N;
  vector<int> p(N);
  if(N == 0) { cout << X; return 0; }
  for(int i = 0; i < N; i++) {
    cin >> p[i];
  }
  
  int dis = 10000;
  int ans = 0;
  int flag = 1;
  for(int i = 120; i >= -100; i--) {
    flag = 1;
    for(int j = 0; j < N; j++) {
      if(i == p[j]){ flag = 0; break; }
    }
    if(flag) {
      if(dis >= abs(i - X)) { dis = abs(i - X); ans = i; }
    } 
  }

  cout << ans;
  return 0;
  }

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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

int main(){
    int n;
    double t, a;
    cin >> n >> t >> a;
    vector<double> h(n);
    rep(i, n){
        cin >> h[i];
        h[i] = t - h[i] * 0.006;
    }
    int ans = 0;
    double now = h[0];
    rep(i, n){
        if(abs(now - a) > abs(h[i] - a)){
            ans = i;
            now = h[i];
        }
    }
    ++ans;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

int main(int argc, char **argv)
{
	int a, b;
	int n;
	int acards[10000],bcards[10000];
	while(true){
		a = 0;
		b = 0;
		std::cin >> n;
		if(n == 0){
			break;
		}
		for(int i = 0; i < n; i++){
			std::cin >> acards[i] >> bcards[i];
			if(acards[i] < bcards[i]){
				b += bcards[i] + acards[i];
			}
			if(acards[i] > bcards[i]){
				a += bcards[i] + acards[i];
			}
			if(acards[i] == bcards[i]){
				a += acards[i];
				b += bcards[i];
			}
		}
		std::cout << a << " " << b << std::endl;
	}
	return 0;
}

Measured memory_bytes: 3088
#include<stdio.h>
#include<string.h>
void N(int dice[]);
void E(int dice[]);
void S(int dice[]);
void W(int dice[]);
void turn(int dice[]);
int main(void){
	int dice1[6],dice2[6],dice3[6];
	int i,j,flag=0;
	scanf("%d %d %d %d %d %d",&dice1[0],&dice1[1],&dice1[2],&dice1[3],&dice1[4],&dice1[5]);
	scanf("%d %d %d %d %d %d",&dice2[0],&dice2[1],&dice2[2],&dice2[3],&dice2[4],&dice2[5]);
	for(i=0;i<6;i++){
		if(dice1[0]==dice2[i]){
			memcpy(dice3,dice2,sizeof(int)*6);
			switch(i){
			case 0:
				break;
			case 1:
				N(dice3);
				break;
			case 2:
				W(dice3);
				break;
			case 3:
				E(dice3);
				break;
			case 4:
				S(dice3);
				break;
			case 5:
				N(dice3);
				N(dice3);
				break;
			}
			for(j=0;j<4;j++){
				if(dice1[0]==dice3[0] && dice1[1]==dice3[1] && dice1[2]==dice3[2] && dice1[3]==dice3[3] && dice1[4]==dice3[4] && dice1[5]==dice3[5]){
					flag=1;
					break;
				}
				else turn(dice3);
			}
		}
		if(flag==1) break;
	}
	if(flag==1) printf("Yes\n");
	else printf("No\n");

	return 0;
}
void N(int dice[]){
	int tmp;
	tmp=dice[0];
	dice[0]=dice[1];
	dice[1]=dice[5];
	dice[5]=dice[4];
	dice[4]=tmp; 
}
void E(int dice[]){
	int tmp;
	tmp=dice[0];
	dice[0]=dice[3];
	dice[3]=dice[5];
	dice[5]=dice[2];
	dice[2]=tmp;
}
void S(int dice[]){
	int tmp;
	tmp=dice[0];
	dice[0]=dice[4];
	dice[4]=dice[5];
	dice[5]=dice[1];
	dice[1]=tmp;
}
void W(int dice[]){
	int tmp;
	tmp=dice[0];
	dice[0]=dice[2];
	dice[2]=dice[5];
	dice[5]=dice[3];
	dice[3]=tmp;
}
void turn(int dice[]){
	int tmp;
	tmp=dice[1];
	dice[1]=dice[2];
	dice[2]=dice[4];
	dice[4]=dice[3];
	dice[3]=tmp;
}

Measured memory_bytes: 580
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
    int n;
    cin >>n;
    string s;
    cin >> s;
    string a,b;
    int i,j;
    if(n%2!=0){
        cout << "No" << endl;
        return 0;
    }
    for(i=0;i<n/2;i++)a+=s.at(i);
    for(i=n/2;i<n;i++)b+=s.at(i-n/2);
    string key;
    key=a+b;
    if(key==s)cout << "Yes"<< endl;
    else      cout << "No" << endl;
    return 0;
}

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

int main(){
    int N;
    string S,T;

    cin>>N>>S>>T;

    int check=N;

    for(int i=0;i<N;i++){
        if(S[i]==T[0]){ 
            for(int k=0;i+k<N;k++){
            
                if(S[i+k]==T[k]){
                    if(i+k==N-1){
                        check=i;
                        cout<<N+check<<endl;

                        return 0;
                    }
                    
                }
            }
        }
    }
                        cout<<N+check<<endl;


}

Measured memory_bytes: 256
#include<iostream>
#include <math.h>
using namespace std;
int main()
{
    long long h;
    cin >> h;
    long long ans=1;
    if(h>1){
        int c = 0;
        while(h>1){
            h/=2;
            c++;
        }
        ans=2*(long long)pow(2,c)-1;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  int N, Y, x = -1, y = -1, z = -1;
  bool f = false;
  int sum = 0;
  cin >> N >> Y;
  for(int i = 0; i < N+1; i++){
  	for(int j = 0; j < N+1-i; j++){
    	sum = 10000 * i + 5000 * j + 1000 * (N - i - j);
      	if(Y == sum){
          	x = i; y = j; z = N - x - y;
        }
    }
  }
  cout << x << " " << y << " " << z << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,x,y,dp[200005],bit[200005],c[200005],ans;

double ans1,ans2;

pi s,f;

deque <pi> a;
vector <pi> b;

bool comp2(pi a, pi b){
    return a.x>b.x;
}

void Upd(int nod, int v){
    while(nod<=n+2){
        bit[nod]=max(bit[nod],v);
        nod+=(nod&-nod);
    }
}

int Qry(int nod){
    int ans=0;
    while(nod){
        ans=max(ans,bit[nod]);
        nod-=(nod&-nod);
    }
    return ans;
}

int32_t main(){
    ios_base :: sync_with_stdio(0);
    cin >> s.x >> s.y >> f.x >> f.y;
    if(s.x>f.x){
        swap(s,f);
    }
    cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> x >> y;
        if(y>=min(s.y,f.y) && y<=max(s.y,f.y) && x>=min(s.x,f.x) && x<=max(s.x,f.x)) a.pb({x,y});
    }
    sort(a.begin(),a.end());
    n=a.size();
    for(int i=0;i<n;i++){
        b.pb({a[i].y,i+1});
    }
    if(s.y<f.y) sort(b.begin(),b.end());
    else sort(b.begin(),b.end(),comp2);
    for(int i=0;i<n;i++){
        c[b[i].y]=i+1;
    }
    c[0]=0; c[n+1]=n+1;
    for(int i=0;i<=n+1;i++){
        dp[i]=1;
        dp[i]+=Qry(c[i]+1);
        Upd(c[i]+1,dp[i]);
    }
    int cnt,bf=1;
    sort(a.begin(),a.end());
    for(int i=1;i<n;i++){
        if(a[i].y<a[i-1].y && s.y<=f.y) bf=0;
        if(a[i].y>a[i-1].y && s.y>=f.y) bf=0;
    }

    if((abs(f.x-s.x)==n-1 || abs(f.y-s.y)==n-1) && bf) cnt=1;
    else cnt=0;
    cout << fixed << setprecision(12) << ((double)abs(s.x-f.x)+abs(s.y-f.y))*100-(double)(2-acos(0))*(dp[n+1]-2-cnt)*10+(2*acos(0)-2)*cnt*10;
}


Measured memory_bytes: 6004
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <cstdio>
#include <climits>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
struct Edge {
    int to, cost;
    Edge(int to, int cost): to(to), cost(cost) {}
};

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<Edge>> AdjList;
AdjList graph;

const int INF = 100000000;

LL N, M;
LL arr[100010]={0};
int S[2010];
int T[2010];
LL dp[2010][2010];
int main() {
    cout << fixed << setprecision(15);

    LL W, H,x,y; cin >> W >> H >> x >> y;

    cout << W*H*0.5 << " " << (x + x == W && y + y == H) << endl;

    return 0;
}

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

int main() {
  auto min = [](auto a, auto b) { return (a < b) ? a : b; };
  int N, M, X;
  std::cin >> N >> M >> X;
  std::vector<int> A(M);
  for (int i = 0; i < M; i++) std::cin >> A[i];
  std::sort(A.begin(), A.end());
  auto i = std::lower_bound(A.begin(), A.end(), X);
  std::cout << min(i - A.begin(), A.end() - i);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vector<vector<vector<vector<ll>>>> dp(n, vector<vector<vector<ll>>>(4, vector<vector<ll>>(4, vector<ll>(4, 0))));
  for(int i=0;i<4;++i) {
    for(int j=0;j<4;++j) {
      for(int k=0;k<4;++k) {
        if((i == 0 && j == 1 && k == 2) || (i == 1 && j == 0 && k == 2) || (i == 0 && j == 2 && k == 1)) {
          continue;
        }
        dp[0][i][j][k] = 1;
      }
    }
  }
  for(int i=0;i<n-1;++i) {
    for(int j=0;j<4;++j) {
      for(int k=0;k<4;++k) {
        for(int l=0;l<4;++l) {
          if((k == 0 && l == 1) || (j == 0 && k == 1) ||
              (j == 0 && l == 1) || (k == 1 && l == 0)) {
            dp[i+1][k][l][0] += dp[i][j][k][l];
            dp[i+1][k][l][0] %= MOD;
            dp[i+1][k][l][1] += dp[i][j][k][l];
            dp[i+1][k][l][1] %= MOD;
            dp[i+1][k][l][3] += dp[i][j][k][l];
            dp[i+1][k][l][3] %= MOD;
          } else if(k == 0 && l == 2) {
            dp[i+1][k][l][0] += dp[i][j][k][l];
            dp[i+1][k][l][0] %= MOD;
            dp[i+1][k][l][2] += dp[i][j][k][l];
            dp[i+1][k][l][2] %= MOD;
            dp[i+1][k][l][3] += dp[i][j][k][l];
            dp[i+1][k][l][3] %= MOD;
          } else {
            dp[i+1][k][l][0] += dp[i][j][k][l];
            dp[i+1][k][l][0] %= MOD;
            dp[i+1][k][l][1] += dp[i][j][k][l];
            dp[i+1][k][l][2] %= MOD;
            dp[i+1][k][l][2] += dp[i][j][k][l];
            dp[i+1][k][l][2] %= MOD;
            dp[i+1][k][l][3] += dp[i][j][k][l];
            dp[i+1][k][l][3] %= MOD;
          }
        }
      }
    }
  }
  ll ans = 0;
  for(int i=0;i<4;++i) {
    for(int j=0;j<4;++j) {
      for(int k=0;k<4;++k) {
        ans += dp[n-3][i][j][k];
        ans %= MOD;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
using namespace std;
typedef long long ll;

int main() {
    int n, q; cin >> n >> q;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; i++)
    {
        int a, b; cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<ll> cnt(n);
    for (int i = 0; i < q; i++)
    {
        int p, x; cin >> p >> x;
        p--;
        cnt[p] += x;
    }

    // 幅優先    
    vector<bool> ok(n, false);
    queue<int> que;
    que.push(0);
    ok[0] = true;

    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (int nv : g[v]) {
            // cout << nv << endl;
            if (ok[nv]) continue;
            cnt[nv] += cnt[v];
            ok[nv] = true;
            que.push(nv);
        }
    }
    
    for (int i = 0; i < n; i++)
    {
        printf("%d%c", cnt[i], (i==n-1)? '\n' : ' ');
    }
    

    return 0;
}

Measured memory_bytes: 16372
#include <iostream>

using namespace std;

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

  int d[100];
  int num = 0;
  int result = 0;
  int tmp;
  int flag;
  while(cin >> tmp){
    flag = 1;
    d[result] = tmp;
    for(int i=0;i<(result);i++){
      if(tmp == d[i]){
        flag = 0;
        break;
      }
    }
    if(flag == 1) result = result + 1;
  }

  cout << result << endl;
  
  return 0;
}


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

int main() {
  int w, h, n;
  cin >> w >> h >> n;
  vector<int> x(n), y(n), a(n);
  for (int i = 0; i < n; i++)
    cin >> x[i] >> y[i] >> a[i];

  vector<vector<int>> A(h, vector<int>(w));
  for (int i = 0; i < n; i++) {
    if (a[i] == 1) {
      for (int z = 0; z < h; z++) {
        for (int v = 0; v < x[i]; v++) {
          A[z][v] = 1;
        }
      }
    } else if (a[i] == 2) {
      for (int z = 0; z < h; z++) {
        for (int v = x[i]; v < w; v++) {
          A[z][v] = 1;
        }
      }
    } else if (a[i] == 3) {
      for (int z = (h - y[i]); z < h; z++) {
        for (int v = 0; v < w; v++) {
          A[z][v] = 1;
        }
      }
    } else {
      for (int z = 0; z < (h - y[i]); z++) {
        for (int v = 0; v < w; v++) {
          A[z][v] = 1;
        }
      }
    }
  }
  int cnt = 0;
  for (int z = 0; z < h; z++) {
    for (int v = 0; v < w; v++) {
      if (A[z][v] == 0) cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    mod = 10**9+7
    
    fact = [1]
    fact_inv = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%mod
        fact.append(new_fact)
        fact_inv.append(pow(new_fact,mod-2,mod))
        
    def mod_comb_k(n,k,mod):
        return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
    
    a.sort()
    
    res = 0
    for i in range(n-k+1):
        res = (res + (a[n-1-i]- a[i])*mod_comb_k(n-i-1,k-1,mod)%mod)%mod

    print(res)
if __name__ == '__main__':
    main()


Measured memory_bytes: 67112
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <boost/math/common_factor.hpp> 
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int N = 1e5 + 10;
int main() 
{  ll n,t,x,y=0,i,j;
    x=1;
    cin>>n;
    int arr[n];
    for(i=0;i<n;i++) {
        cin>>arr[i];
    }
    for(i=0;i<n;i++) {
        if(arr[i]==x) {
            y++;
            x=x+1;
        }
    }    if(n-y!=n){
          cout<<n-y;
    }
    else {
        cout<<"-1";
    }
  
    
    return 0; 
} 

Measured memory_bytes: 1024
H, N = map(int, input().split())
A, B = [], []
for _ in range(N):
    ai, bi = map(int, input().split())
    A.append(ai)
    B.append(bi)

inf = 10**23

d = [inf] * (H+1)
d[0] = 0
for i in range(1, H+1):
    for abi in range(N):
        if A[abi] >= i:
            d[i] = min(d[i], B[abi])
        else:
            d[i] = min(d[i], d[i-A[abi]] + B[abi])


print(d[H])




Measured memory_bytes: 42476
import java.util.Arrays;
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int k=sc.nextInt(),t=sc.nextInt();
			int[] a=new int[t];
			for(int i=0;i<t;i++) a[i]=sc.nextInt();
			Arrays.sort(a);
			int ans=0,bf=t-1; a[t-1]--;
			for(int i=0;i<k-1;i++){
				int m1=-1,m2=-1;
				for(int j=0;j<t;j++){
					if(a[j]<=0) continue;
					if(m1==-1 || a[j]>a[m1]) m1=j;
					if(m2==-1 || a[j]>a[m2] && j!=bf) m2=j;
				}
				if(m1!=bf){
					a[m1]--;
					bf=m1;
				}
				else if(m2!=bf){
					a[m2]--;
					bf=m2;
				}
				else{
					ans++;
					a[m1]--;
					bf=m1;
				}
			}
			for(int i=0;i<t;i++) ans+=a[i];
			System.out.println(ans);
		}
	}
}

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

#define int long long
#define gcd            __gcd
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define deci(x, y)      fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PI             3.141592653589793238
using namespace std;

int32_t main() {
    nitin;
    string s;
    cin>>s;
    int ans=0;
    for(auto c:s)
    {
        ans+=c-'0';
    }
    if(ans%9==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 3776
N=gets.to_i
open=N.times.map{gets.split.map(&:to_i)}
ms=N.times.map{gets.split.map(&:to_i)}
ans=-Float::INFINITY
for i in 1..2**10-1
    shop=Array.new(N,0)
    for j in 0..9
        next if i[j]==0
        for k in 0..N-1
            shop[k]+=1 if open[k][j]==1
        end
    end
    can = shop.map.with_index{|e,i|ms[i][e]}.inject(:+)
    ans = ans < can ? can : ans
end
puts ans


Measured memory_bytes: 2428
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <iostream>
#include <string>

#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define PB push_back
#define MP make_pair

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

#define ALL(v) (v).begin(),(v).end()

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VPII;

const int MOD = 1000000007;
const int INF = 1e9;

const double EPS = 1e-9;
const double PI = acos(-1.0);

const int DX[4] = {1, 0, -1, 0};
const int DY[4] = {0, 1, 0, -1};

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }

int N, A[200001];

int main() {
    cin >> N;
    VI num(N + 1, 0);
    REP (i, N) {
        cin >> A[i];
        num[A[i]]++;
    }
    LL sum = 0;
    vector<LL> dif(N + 1, 0);
    REP (i, N) {
        LL n = (LL)num[i + 1];
        if (n >= 2) {
            LL c = n * (n - 1) / 2;
            sum += c;
            dif[i + 1] = c;
            if (n - 1 >= 2) {
                LL c2 = (n - 1) * (n - 2) / 2;
                dif[i + 1] -= c2;
            }
        }
    }
    REP (i, N) {
        cout << sum - dif[A[i]] << endl;
    }
    return 0;
}

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

int main(){
  int n, a, b;
  cin >> n >> a >> b;
  
  int ans;
  ans = min(n*a, b);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
	int t=1;
	//cin>>t;
	while(t--)
	{
	    int n,i;
	    cin>>n;
	    ll ans=0;
	    vector<ll>a(n);
	    map<ll,ll>mp;
	    for(i=0;i<n;i++) {
	        cin>>a[i];
	        mp[a[i]]++;
	    }
	    for(auto it:mp) 
	    {
	        ll x=(ll)it.second;
	        ans+=(x*(x-1))/2;
	    }
	    //cout<<ans<<endl;
	    for(i=0;i<n;i++)
	    {
	        ll x=(ll)mp[a[i]];
	        ll ans1=ans;
	        ans1-=(x*(x-1))/2;
	        x--;
	        ans1+=(x*(x-1))/2;
	        cout<<ans1<<"\n";
	    }
	}
	return 0;
}

Measured memory_bytes: 11008