akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdlib>
 
using namespace std;

struct Box{
  int num,d,tre;
  Box(){}
  Box(int n, int d, int t):num(n),d(d),tre(t){}
};
struct State{
  int visited,pos,t,w;
  State();
  State(int v, int p, int t, int w):visited(v),pos(p),t(t),w(w){}
  bool operator < (const State& s) const { return t > s.t;}
};
const int MAX = 16;
const int INF = (1<<28);
double T[(1<<MAX)][MAX];
int pre[(1<<MAX)][MAX];
int n;
vector<Box> V;
 
void init(){
  fill(T[0],T[0]+(1<<MAX)*MAX,INF);
}
 
void input(){
  cin >> n;
  for(int i = 0; i < n; i++){
    Box b;
    cin >> b.num >> b.d >> b.tre;
    V.push_back(b);
  }
}
 
double speed(double d, double w){return (70+20*w)/2000*d;}
 
void dijkstra(){
 
  priority_queue<State> Q;
  for(int i = 0; i < V.size(); i++){
    T[(1<<i)][i] = 0;
    Q.push(State((1<<i),i,0,V[i].tre));
    pre[(1<<i)][i] = -1;
  }
 
  while(!Q.empty()){
    State now = Q.top();
    Q.pop();
     
    if(T[now.visited][now.pos] < now.t) continue;
 
    for(int i = 0; i < V.size(); i++){
      if(!(now.visited&(1<<i))){
 
    State nex = now;
    nex.visited+=(1<<i);
    nex.pos = i;
    nex.t += speed(abs(V[now.pos].d-V[i].d),now.w);
    nex.w += V[i].tre;
     
    if(T[nex.visited][nex.pos] > nex.t){
      T[nex.visited][nex.pos] = nex.t;
      pre[nex.visited][nex.pos] = now.pos;
      Q.push(State(nex));
    }
      }
    }
     
  }
}
 
vector<int> makepath(){
  double mincos = INF;
  int minpos;
 
  for(int i = 0; i < V.size(); i++){
    if(T[(1<<V.size())-1][i] < mincos){
      mincos = T[(1<<V.size())-1][i];
      minpos = i;
    }
  }
 
  vector<int> path;
  int S = (1<<V.size())-1, v = minpos;

  while(1){
    if(S == 0) break;
    path.push_back(V[v].num);
    int tmp = v;
    v = pre[S][v];
    S -= (1<<tmp);
  }
  reverse(path.begin(),path.end());
  return path;
}
 
void solve(){
 
  dijkstra();
  vector<int> path = makepath();
 
  for(int i = 0; i < path.size(); i++){
    if(i) cout << " ";
    cout << path[i];
  }
  cout << endl;
}
 
 
int main(){
  init();
  input();
  solve();
  return 0;
}

Measured memory_bytes: 23148
#include<iostream>

using namespace std;

int main(){
    int n,k,x,y;
    cin >> n >> k >> x >> y;

    int _sum=0;
    for(int i=1;i<=n;i++){
        if(i<=k){
            _sum+=x;
        }
        else{
            _sum+=y;
        }
    }
    cout << _sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;//typo用
using itn = int;//typo用
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a) - 1; i >= (intl)(b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl//1次元配列の出力
#define rrdebug(i, j, x) rep(i, alength(x))rep(j, alength(x[i]))cout << #x << "[" << i << "][" << j << "]:" << x[i][j] << endl//二次元配列の出力
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld EPS = 1.0e-14;//-9
const ld PI = acos(-1);
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
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; }
intl gcd(intl a, intl b){ if(!b)return a; return gcd(b, a % b); }
intl lcm(intl a,intl b){ return a / gcd(a, b) * b; }
intl kai(intl k){//k!を求める関数,
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl digit10(intl a){//aを10進数で表したときの桁数を求める関数
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}

signed main(){
    cout << fixed << setprecision(10);
    intl n;
    cin >> n;
    intl a[n];
    rep(i,n)cin >> a[i];
    intl cnt = 0;
    rep(i,n)cnt += (a[i] < 0);
    intl mi = INF;
    if(cnt % 2)rep(i,n)mi = min(mi,abs(a[i]));
    intl sum = 0;
    rep(i,n)sum += abs(a[i]);
    if(cnt % 2)sum -= 2 * mi;
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <math.h>
#include <set>
#include <vector>
#include <algorithm>
#include <map>


using namespace std;

typedef long long ll;
#define INF 0x3f3f3f3f
#define ESP 1e-8;
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
const double PI = acos(-1.0);
#define N 100005
int A[N], B[N], n, maxA, maxB, secA, secB, numAm, numBm, numAs, numBs;

map<int, int> ma, mb;

int main(){
    int i, ans;
    while(scanf("%d", &n)!=EOF){
        ma.clear(), mb.clear();
        maxA = maxB = secA = secB = 0;
        numAm = numBm = numAs = numBs = 0;
        for(i = 1; i <= n/2; i++){
            scanf("%d%d", &A[i], &B[i]);
            ma[A[i]]++, mb[B[i]]++;
            if(ma[A[i]] > maxA){
                if(numAm != A[i] || !numAm){
                    secA = maxA;
                    numAs = numAm;
                    maxA = ma[A[i]];
                    numAm = A[i];
                }
                else
                    maxA = ma[A[i]];
            }
            else if(ma[A[i]] > secA){
                if(numAs != A[i] || !numAs){
                    secA = ma[A[i]];
                    numAs = A[i];
                }
                else
                    secA = ma[A[i]];
            }
            if(mb[B[i]] > maxB){
                if(numBm != B[i] || !numBm){
                    secB = maxB;
                    numBs = numBm;
                    maxB = mb[B[i]];
                    numBm = B[i];
                }
                else
                    maxB = mb[B[i]];
            }
            else if(mb[B[i]] > secB){
                if(numBs != B[i] || !numBs){
                    secB = mb[B[i]];
                    numBs = B[i];
                }
                else
                    secB = mb[B[i]];
            }
        }
        if(numAm != numBm)
            ans = n-maxA-maxB;
        else
            ans = n-MAX(maxA+secB, secA+maxB);
        printf("%d\n", ans);
    }

    return 0;
}

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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

ll tentou[1<<18][18];
ll tentou_tmp[18];
ll num[1<<18];
ll dp[1<<18][51];

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

	REP(i, (1<<18)){
		REP(j, 51)dp[i][j] = INF;
		ll cou = 0;
		REP(j, 18){
			if(i & (1 << j)){
				tentou_tmp[j] = 1;
				cou++;
			}
			else {
				tentou_tmp[j] = 0;
			}
		}
		REV(j, 17)tentou_tmp[j] += tentou_tmp[j+1];
		num[i] = cou;
		REP(j, 18)tentou[i][j] = tentou_tmp[j];
	}

	ll n;cin >> n;
	vector<ll> a(n);
	vector<ll> b(n);
	REP(i, n)cin >> a[i];
	REP(i, n)cin >> b[i];

	dp[0][0] = 0;
	REP(i, (1<<n)){
		REP(j, 51)if(dp[i][j] != INF){
			//cout << bitset<5>(i) << " " << j << " " << dp[i][j] << endl;
			REP(ii, n){
				if(!(i & (1 << ii))){
					ll now;
					if(abs(num[i] - ii) % 2) now = b[ii];
					else now = a[ii];
					if(now < j)continue;
					//cout << " " << ii << " " << now << " " << bitset<5>(i | (1<<ii)) << endl;
					dp[i | (1<<ii)][now] = min(dp[i | (1<<ii)][now], dp[i][j] + tentou[i][ii]);
				}
			}
		}
	}

	ll ans = INF;
	REP(i, 51)ans = min(ans, dp[(1<<n)-1][i]);
	cout << (ans == INF ? -1 : ans) << endl;

	return 0;
}


Measured memory_bytes: 143616
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
int mod = 1e9 + 7;
int INF = 2e18;

signed main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    int sum = accumulate(A.begin(), A.end(), 0L);
    int ans = INF, temp = 0;
    for (int i = 0; i < N; i++) {
        temp += A[i];
        ans = min(ans, abs((sum - temp) - temp));
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include<stdio.h>

void print_a(int n, int *a)
{
	int i;
	for(i=0;i<n-1;i++) {
		printf("%d ", a[i]);
	}
	printf("%d\n", a[n-1]);
}

int main(void)
{
	int n, a[100], i, j, v;
	scanf("%d", &n);
	for(i=0;i<n;i++) {
		scanf("%d", &a[i]);
	}
	print_a(n, a);
	for(i=1;i<n;i++) {
		v = a[i];
		j = i-1;
		while(j >= 0 && a[j] > v) {
			a[j+1] = a[j];
			j--;
		}
		a[j+1] = v;
		print_a(n, a);
	}
	return 0;
}


Measured memory_bytes: 2048
#include <stdio.h>

/*  選択ソート(0オリジン) */
int selectionSort(int A[], int N) {
    int i, j, t, sw =0, minj;
    for(i=0;i<N-1;i++) {
        minj = i;
        for(j=i;j<N;j++) {
            if(A[j]<A[minj]) minj = j;
        }
        t=A[i]; A[i]=A[minj]; A[minj]=t;
        if(i!=minj) sw++;
    }
    return sw;
}

int main(void) {
    int A[100], N, i, sw;

    scanf("%d",&N);
    for(i=0;i<N;i++) scanf("%d",&A[i]);

    sw = selectionSort(A,N);

    for(i=0;i<N;i++) {
        if(i>0) printf(" ");
        printf("%d",A[i]);
    }
    printf("\n");
    printf("%d\n",sw);

    return 0;
}


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

const int MAX=100005;
vector<int> S[MAX];

int par[MAX];
int root(int a){
    if(par[a]==a) return a;
    else return par[a]=root(par[a]);
}
void unite(int a,int b){
    if(root(a)!=root(b)) par[root(b)]=root(a);
}
bool check(int a,int b){
    return root(a)==root(b);
}

int main(){

    int N,M;cin>>N>>M;
    for(int i=0;i<N;i++){
        par[i]=i;
    }
    for(int i=0;i<M;i++){
        int a,b;cin>>a>>b;
        unite(a,b);
    }
    int Q;cin>>Q;
    for(int i=0;i<Q;i++){
        int a,b;cin>>a>>b;
        if(check(a,b)) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }

}



Measured memory_bytes: 5852
#include<bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef long long int lli;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<pll> vop;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<int> vi;
#define REP(i,a,b) for( long long i=a;i<b;i++)
#define REPR(i,a,b) for(long long i=a;i>=b;i--)
#define adb(a) for(auto i:a) cout << i << " "; cout << endl
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
#define endl "\n"
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000009
#define MAX 500005;
#define PI 3.14159265358979323846

ll power(ll a, ll b, ll m) { ll ans = 1; a = a % m; while (b) { if (b & 1) ans = (ans * a) % m; b /= 2; a = (a * a) % m; } return ans; }

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

ll modInverse(ll a, ll m) { ll g = __gcd(a, m); return power(a, m - 2, m); }


int main()
{


    fastIO;
    int test = 1;
    //cin >> test;
    while (test--)
    {
        string s, t;
        cin >> s >> t;
        int n = s.size(), m = t.size();
        int dp[n + 1][m + 1];
        mem(dp, 0);
        REP(i, 1, n + 1) {
            REP(j, 1, m + 1) {
                if (s[i - 1] == t[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        string ans = "";
        int i = n, j = m;
        while (i > 0 && j > 0)
        {
            if (s[i - 1] == t[j - 1])
            {
                ans += s[i - 1];
                i--;
                j--;
            }
            else if (dp[i - 1][j] > dp[i][j - 1])
                i--;
            else
                j--;
        }
        reverse(ans.begin(), ans.end());
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 35456
n=int(input())
a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(a[n-1])

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        ArrayDeque<Character> dq = new ArrayDeque<>();
        int count = 0;

        for(int i =0; S.length() > i; i++){
            char c = S.charAt(i);
            if(dq.isEmpty() || dq.getFirst() == c){
                dq.addFirst(c);
            }else{
                dq.removeFirst();
                count++;
            }
            
        }
        System.out.println(count*2);

    }

}

Measured memory_bytes: 25572
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String buffer;

		try {
			while ((buffer = reader.readLine())  != null) {
				//String[] input = buffer.split(" ");
				char[] chars = buffer.toCharArray();
				for (int i = 0; i < chars.length; i++) {
					char ch = chars[i];
					if (Character.isLowerCase(ch)) {
						chars[i] = Character.toUpperCase(ch);
					}
					else {
						chars[i] = Character.toLowerCase(ch);
					}
				}
				System.out.println(String.valueOf(chars));
			}
		} catch (Exception ex) {
			ex.printStackTrace();
		}
	}
}



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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const double PI = 3.14159265358979323846;

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

template<typename T>
void print1(T begin, T end) {
	while (begin != end) {
		cerr << (*begin) << " ";
		*begin++;
	}
	cerr << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cerr << " " << Array[i][j];
		}
		cerr << endl;
	}
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	std::cerr << head << " ";
	print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
	int val = ((a % mod) + (b % mod)) % mod;
	if (val < 0) { val += mod; }
	a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

int N;
int d[111111];

signed main() {
	cin >> N;
	rep (i, N) {
		cin >> d[i];
	}
	sort(d, d+N);

	int mid = N / 2;
	int left = d[mid-1];
	int right = d[mid];

	cout << right - left << endl;

	return 0;
}

Measured memory_bytes: 1024
import java.util.*;

public class Main {
  public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);

    long a = sc.nextLong();
    long b = sc.nextLong();
    long c = sc.nextLong();
    long d = sc.nextLong();

    long m = lcm(c ,d);

    long x = b - a + 1;
    long y = (b / c) - (a - 1) / c;
    long z = (b / d) - (a - 1) / d;
    long w = (b / m) - (a - 1) / m;
    long ans = x - y - z + w;
    System.out.println(ans);
  }
  
  private static long gcd(long m, long n) {
    if(m < n) return gcd(n, m);
    if(n == 0) return m;
    return gcd(n, m % n);
  }

  private static long lcm(long m, long n) {
      return m * n / gcd(m, n);
  }

}


Measured memory_bytes: 21972
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){

    int a, max_div = 100, sub = 100;
    scanf("%d", &a);

    for(int i = 1; i <= 9; ++i){
        if (a%i == 0){
            max_div = i;
            sub = a/i;
        }
    }

    if(sub <= 9){
        printf("Yes\n");
    } else{
        printf("No\n");
    }


    return 0;
}


Measured memory_bytes: 128
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int num[] = new int[5];
		for (int i = 0; i < N; i++) {
			String S = sc.next();
			switch (S.charAt(0)) {
				case 'M':
					num[0]++;
					break;
				case 'A':
					num[1]++;
					break;
				case 'R':
					num[2]++;
					break;
				case 'C':
					num[3]++;
					break;
				case 'H':
					num[4]++;
					break;
			}
		}
		long ans = 0;
		for (int i = 0; i < 5; i++) {
			for (int j = i+1; j < 5; j++) {
				for (int k = j+1; k < 5; k++) {
					ans += (long)num[i] * (long)num[j] * (long)num[k];
				}
			}
		}
		System.out.println(ans);
	}
}

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

int main(){
  long long N,A;
  cin >> N >> A;
  vector<int> v(N);
  for(int i=0; i<N; i++){
    cin >> v[i];
  }
  long long cnt[60][3010][60]={};
  cnt[0][0][0]=1;
  for(int i=0; i<N; i++){
    for(int sum=0; sum<3000; sum++){
      for(int k=0; k<51; k++){
        cnt[i+1][sum+v[i]][k+1] += cnt[i][sum][k];
        cnt[i+1][sum][k] += cnt[i][sum][k];
      }
    }
  }
  
  long long ans=0;
  
  for(int sum=0; sum<3000; sum++){
     for(int k=0; k<51; k++){
       if(k==0) continue;
       if(A*k==sum){
         ans+=cnt[N][sum][k];
       }
     }
  }
  cout << ans << endl;
}


Measured memory_bytes: 88284
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<tuple>
#include<iomanip>
#include<map>
#include<queue>
#define int long long
using namespace std;

const int INF = 1e10;
const int ZERO = 0;
signed main() {
	int N;
	cin >> N;
	vector<int> vec(N);
	for(int i = 0;i < N;i++) {
		cin >> vec.at(i);
	}
	int cnt = 0;
	for(int i = 0;i < N;i++) {
		cnt += vec.at(i);
	}
	if(cnt % 10 != 0) {
		cout << cnt << endl;
	}
	else {
		sort(vec.begin(),vec.end());
		bool A = false;
		for(int i = 0;i < N;i++) {
			if(vec.at(i) % 10 != 0) {
				cout << cnt - vec.at(i) << endl;
				A = true;
              	break;
			}
		}
		if(A == false) {
			cout << 0 << endl;
		}
	}
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define MAXN 5005
#define reg register
#define inl inline
#define int long long
using namespace std;
const int Mod=1e9+7;
vector <int> g[MAXN];
int n,f[MAXN][MAXN],_[MAXN],siz[MAXN],t[MAXN];
void Dfs(reg int u,reg int pre)
{
	siz[u]=1;
	f[u][1]=1;
	for(auto v: g[u])
	{
		if(v==pre) continue;
		Dfs(v,u);
		for(reg int i=1;i<=siz[u]+siz[v];i++) t[i]=0;
		for(reg int i=1;i<=siz[u];i++)
		{
			for(reg int j=0;j<=siz[v];j++) t[i+j]=(t[i+j]+f[u][i]*f[v][j]%Mod)%Mod;
		}
		for(reg int i=1;i<=siz[u]+siz[v];i++) f[u][i]=t[i];
		siz[u]+=siz[v];
	}
	for(reg int i=2;i<=siz[u];i+=2) f[u][0]=(f[u][0]-f[u][i]*_[i]%Mod+Mod)%Mod;
}
signed main()
{
	scanf("%lld",&n);
	for(reg int i=1;i<n;i++)
	{
		reg int x,y;
		scanf("%lld %lld",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	_[0]=1;
	for(reg int i=2;i<=n;i+=2) _[i]=_[i-2]*(i-1)%Mod;
	Dfs(1,0);
	printf("%lld\n",Mod-f[1][0]);
	return 0;
}

Measured memory_bytes: 195072
#include "bits/stdc++.h"

using namespace std;
#define rep(i, n) for(int i = 0; i < signed(n); i++)
#define rrep(i, n) for(int i = signed(n) - 1; i >= 0; i--)
#define all(co) co.begin(), co.end()
//#define int long long
//using LL = long long;
//using P = pair < int, int > ;
//using PI = pair < P, int > ;
typedef pair<int, int> P;
typedef long long LL;
typedef pair<P, int> PI;
typedef pair<int, P> IP;
const int INF = 1 << 29;
const LL LINF = 1ll << 62ll;

struct edge{ int from, to, cost; };

int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

template<typename T = int>
vector<vector<T>> vvector(int h, int w, T def = T()){ return move(vector<vector<T>>(h, vector<T>(w, def))); }
class range {
private: struct I{ int x; int operator*(){ return x; }bool operator!=(I& lhs){ return x < lhs.x; }void operator++(){ ++x; } }; I i, n;
public:range(int n) :i({ 0 }), n({ n }){}range(int i, int n) :i({ i }), n({ n }){}I& begin(){ return i; }I& end(){ return n; }
};

signed main()
{
	int n;
	while (cin >> n && n)
	{
		int m; cin >> m;
		vector<vector<int>> triangle(n);
		rep(i, n) triangle[i].resize(i + 1);
		rep(i, m)
		{
			int a, b, x; cin >> a >> b >> x;
			a--; b--;
			triangle[a][b] = x + 1;
		}
		rep(i, n - 1) rep(j, i + 1)
		{
			triangle[i + 1][j] = max(triangle[i + 1][j], triangle[i][j] - 1);
			triangle[i + 1][j + 1] = max(triangle[i + 1][j + 1], triangle[i][j] - 1);
		}
		int ans = 0;
		rep(i, n)rep(j, i + 1)ans += !!triangle[i][j];
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 50104
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define int long long
 
signed main(){
	
 
	
	int n;
	cin>>n;

	int a[n];

	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int ma=-200;
	int mi=200;

	for(int i=0;i<n;i++){
		ma=max(a[i],ma);
		mi=min(a[i],mi);
	}
	// cout<<"---"<<endl;
	// cout<<ma<<" "<<mi<<endl;
	// cout<<"---"<<endl;


	int total=0;
	int ans=1e9;

	for(int i=mi;i<=ma;i++){
		total=0;


		for(int j=0;j<n;j++){


			int seki=(i-a[j])*(i-a[j]);
			total+=seki;

			// cout<<seki<<endl;

		}


		// cout<<total<<endl;
		ans=min(ans,total);

		// cout<<total<<endl;

	}

	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAXN 100010
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long
#define in_range(x, y, n) (x >= 0 and x<n and y >=0 and y<n)
using namespace std;
const ll mod = 1e18 + 7;

int main (){
    ios_base::sync_with_stdio(false);
    
    int a, b, n;
    cin >> n >> a >> b;

    for (int i=a; i<=b; i++){
        if (i%n == 0){
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3608
#include <stdio.h>

int main(void) {

int S;
int h;
int m;
int s;

scanf("%d",&S);

h = S / 3600;
m = (S - h * 3600) / 60;
s = S - (h * 3600 + m * 60);

printf("%d:%d:%d\n",h,m,s);

return 0;
}

Measured memory_bytes: 592
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
void Unused(...) {}
#ifndef DEBUG
  #define echo(...) Unused(__VA_ARGS__)
#else
  #define echo(...) fprintf(stderr, __VA_ARGS__)
#endif

const int MaxN = int(1e5) + 7;
const int Inf = 0x3f3f3f3f;

int n, k;
int pos[MaxN];

int main()
{
    // Scan
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; ++i)
        scanf("%d", pos + i);
    // Move win and calc ans
    const int w = k - 1;
    int ans = Inf;
    for (int i = 1; i <= n - w; ++i)
    {
        int shift = 0;
        if (pos[i] > 0)
            shift = pos[i];
        else if (pos[i + w] < 0)
            shift = -pos[i + w];
        else
            shift = std::min(-pos[i], pos[i + w]);
        ans = std::min(ans, pos[i + w] - pos[i] + shift);
    }
    printf("%d\n", ans);
    return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
char str[1000005];
int main() {
	int n;
	scanf("%d%s", &n, str);
	for (int i = 0; i < n; ++i) --str[i];
	auto f = [&](string s) {
		int ret = 0;
		for (int i = 0; i < n; ++i) {
			int odd = (((n - 1) & i) == i);
			if (s[i] == '1') ret ^= odd;
		}
		return ret;
	};
	bool hasOne = false;
	for (int i = 0; i < n; ++i) hasOne |= str[i] == '1';
	if (hasOne) {
		string strpar(str);
		for (int i = 0; i < n; ++i) {
			if (str[i] == '2') strpar[i] = '0';
		}
		printf("%d\n", f(strpar));
	} else {
		string strpar(str);
		for (int i = 0; i < n; ++i) {
			if (str[i] == '2') strpar[i] = '1';
		}
		printf("%d\n", f(strpar) * 2);
	}
}


Measured memory_bytes: 3200
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		int[] time = new int[N];
		long ans = 0;

		for (int i = 0; i < N; i++) {
			time[i] = sc.nextInt();
			if (i > 0) {
				if (T < time[i] - time[i-1]) {
					ans += T;
				} else {
					ans += time[i] - time[i-1];
				}
			}
		}

		ans += T;

		System.out.println(ans);
	}

}

Measured memory_bytes: 85064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define MOD 1000000007
#define MOD2 998244353
#define INF MOD
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

int last[400][30];
Int v[400];

int main() {
    int D;
    cin >> D;
    int c[30];
    Int s[D+10][30];
    // Int t[D+10];
    map<int, int> last;
    for (int i = 1; i <= 26; i++) {
        cin >> c[i];
    }
    for (int d = 1; d <= D; d++) {
        for (int i = 1; i <= 26; i++) {
            cin >> s[d][i];
        }
    }
    for (int d = 1; d <= D; d++) {
        cout << (d % 26) + 1 << endl;
    }
}

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

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

using namespace std;

using ll = long long;
using P = pair<int , int>;
  
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n; cin >> n;
  string ans = "No";
  for(int i = 0; i*4 <= n; ++i) {
    int sum = 0;
    for(int j = 0; sum <= n; ++j) {
      sum = i*4 + j*7;
      if(sum == n) ans = "Yes";
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        int X,Y,W,H;
        cin>>X>>Y>>W>>H;
        int m,cnt=0;
        cin>>m;
        while(m--){
            int x,y;
            cin>>x>>y;
            if(x>=X&&X+W>=x&&y>=Y&&Y+H>=y)cnt++;
        }
        cout<<cnt<<endl;

    }
}

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

int main(){
  string s;
  cin >> s;
  int count = 0;
  int N = s.size();
  for (int i = 0; i < N; i++){
    if (s.at(i) != s.at(N - i - 1)) count++;
  }
  cout << count / 2 << endl;
}


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

using namespace std;
using P = pair<int, int>;

int h, w, d, q;

P map[90002];
int cost[90002];


int main(){
    cin >> h >> w >> d;

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            int aij;
            cin >> aij;
            map[aij] = make_pair(i, j);
        }
    }

    for (int init = 1; init <= d; ++init) {
        cost[init] = 0;
        for (int i = init + d; i <= h * w; i += d) {
            P l = map[i - d];
            P r = map[i];
            int c = abs(l.first - r.first) + abs(l.second - r.second);
            cost[i] = cost[i - d] + c;
        }
    }

    // for (int i = 1; i <= h * w; ++i) {
        // cout << i << " " << cost[i] << endl;
    // }

    //long long ans = 0;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        cout << cost[r] - cost[l] << endl;
    }
    //cout << ans << endl;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> X(N);
  for(int i=0; i<N; ++i) cin >> X[i];
  int cnt = 0;
  int mx=0;
  for(int i=0; i<N; ++i){
    if(X[i] >= mx) ++cnt;
    mx= max(mx, X[i]);
  }
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map> 
#include <algorithm>
#include <cstring>
using namespace std; 

void solve(){
  int n, k; 
  cin >> n >> k; 
  long a[n]; 
  for(int i=0; i<n ; i++){
    cin>>a[i]; 
  }
  long dp[n]; 
  for(int i=0; i<n; i++){
    dp[i] = INT32_MAX;
  }
  dp[0] = 0; 
  // dp[1] = abs(a[1]-a[0]); 
  for(int i=1; i<n; i++){
    for(int j=max(0,i-k); j<i; j++){
      dp[i] = min(dp[i], dp[j] + abs(a[i]-a[j])); 
  }
  }
  cout << dp[n-1]<<"\n"; 
}

int main(){
  int t=1; 
  // cin>>t; 
  while(t--){
    solve(); 
  }
 return 0;
}

Measured memory_bytes: 4672
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a, b) ((a < b) ? a : b)
#define _max(a, b) ((a < b) ? b : a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a) ? 1 : -1)
#define SORT(v) sort(v.begin(), v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

int main() {
    cout << fixed << setprecision(10);
    double N;
    cin >> N;
    vector<int> v(N);
    REP(i, N) { cin >> v[i]; }
    SORT(v);
    double sum = (v[0] + v[1]) / 2.0;
    FOR(i, 2, N) { sum = (sum + v[i]) / 2; }
    cout << sum;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n;
    string s;
    cin>>n;
    bool y=false;
    for(int i=0;i<n;i++){
        cin>>s;
        if(s=="Y"){
            y=true;
        }
    }
    if(y){
        cout<<"Four";
    }else{
        cout<<"Three";
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;

ll po(ll a, int n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}
ll modinv(ll a) {
    return po(a, MOD - 2);
}
ll combi(int n, int k) {
    ll res = 1;
    for (int i = 0; i < k; ++i) {
        res = res * (n - i) % MOD;
    }
    for (int i = k; i >= 1; --i) {
        res = res * modinv(i) % MOD;
    }
    return res;
}
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    ll PO = po(2, n);
    ll A = combi(n, a);
    ll B = combi(n, b);
    ll ans = (PO - A - B - 1 ) % MOD;
    cout << (ans < 0 ? ans + MOD : ans) << endl;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
// template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
// template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
bool is_palindrome(string s){return s == string(s.rbegin(),s.rend());}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}



int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<std::string> S(N);
    for(int i = 0 ; i < N ; i++){
        std::cin >> S[i];
    }
    //solve(N, std::move(S));
    unordered_map<string,ll> m;
    for (long long i = 0; i < N; i++) {
        m[S[i]]++;
    }
    cout << m.size() << endl;
    return 0;
}


Measured memory_bytes: 23924
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 100010
#define INF 10000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000000;
const int MOD = 1000000007;
int main(){
    int n;
    IN(n);
    vector<int>a(n);
    int m1=0;
    int m2=0;
    REP(i,n){
        IN(a[i]);
        if(m1<a[i]){
            m2=m1;
            m1=a[i];
        }else if(m2<a[i]){
            m2=a[i];
        }
    }
    REP(i,n){
        if(a[i]==m1){
            OUT(m2);
        }else{
            OUT(m1);
        }
    }
	return 0;
}

Measured memory_bytes: 2432
def examB():
    N, M, X = LI()
    A = LI()
    L0 = bisect.bisect_left(A,X)
    L1 = M-L0
    ans = min(L0,L1)
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examB()


Measured memory_bytes: 38384
#include<iostream>
using namespace std;
int main(){
	int x, m;
	cin>>x;
	m=x%10;
	if(m==2||m==4||m==5||m==7||m==9)
	cout<<"hon";
	else if(m==0||m==1||m==6||m==8)
	cout<<"pon";
	else if(m==3)
	cout<<"bon";
}  

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

int main() {
    int N, M;
    while(cin >> N >> M, N || M) {
        vector<string> v(N);
        for(auto &i : v) cin >> i;

        string res = "";
        const int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
        const int dy[] = {-1, 0, 1, -1, 0, 1, -1, 1};
        set<string> s;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                for(int k = 0; k < 8; k++) {
                    int x = i;
                    int y = j;
                    int nx = (x + dx[k] + N) % N;
                    int ny = (y + dy[k] + M) % M;
                    string tmp = "";
                    tmp += v[i][j];
                    while(x != nx || y != ny) {
                        tmp += v[nx][ny];
                        nx = (nx + dx[k] + N) % N;
                        ny = (ny + dy[k] + M) % M;
                        if(res.size() <= tmp.size() && s.find(tmp) != s.end()) {
                            if(res.size() < tmp.size()) {
                                res = tmp;
                            } else if (res.size() == tmp.size()) {
                                res = min(res, tmp);
                            }
                        } else if (res.size() <= tmp.size()){
                            s.insert(tmp);
                        }
                    }
                }
            }
        }

        cout << (res == "" ? "0" : res) << endl;
    }

    return 0;
}

Measured memory_bytes: 32228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
    int n;
    cin >> n;
    int l,r,ans=0;

    for (int i = 0; i < n; i++)
    {
        cin >> l >> r;
        ans += r-l+1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 1000000007
#define TE 2e5
using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int N; cin >> N;
	vector<ll> L(N);
	for (int i = 0; i < N; i++) {
		cin >> L[i];
	}

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (L[i] == L[j])continue;
			for (int k = j + 1; k < N; k++) {
				if (L[i] == L[k] || L[j] == L[k])continue;
				if (abs(L[i] - L[j]) < L[k] && L[k] < abs(L[i] + L[j]))cnt++;
			}
		}
	}
	cout << cnt << endl;

}

Measured memory_bytes: 3628
n = gets.to_i
strs = gets.chomp.split(' ').map(&:to_i)

even_ary = strs.uniq.select{ |num| num.even? }
if even_ary.all? {|num| num % 3 == 0 || num % 5 == 0 }
  puts 'APPROVED'
else
  puts 'DENIED'
end

Measured memory_bytes: 1788
def main():
    n, k = map(int, input().split())
    h = []
    for i in range(n):
        h.append(int(input()))

    h.sort()

    ans = []
    for i in range(n-k+1):
        ans.append(abs(h[i] - h[i+k-1]))

    print(min(ans))

if __name__ == "__main__":
    main()


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

int N;
vector<vector<int> > g;
vector<int> dist;
vector<bool> visited;

vector<int> bfs(int n){
  dist.assign(N, 0);
  visited.assign(N, false);
  queue<int> q;
  q.push(n);
  dist[n] = 0;
  visited[n] = true;
  while(!q.empty()){
    int cur = q.front(); q.pop();
    for(auto i : g[cur]){
      if(visited[i]) continue;
      dist[i] = dist[cur] + 1;
      visited[i] = true;
      q.push(i);
    }
  }
  return dist;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int u, v; cin >> N >> u >> v; u--; v--;
  g.assign(N, vector<int>());
  REP(i, N-1){
    int A, B; cin >> A >> B; A--; B--;
    g[A].push_back(B);
    g[B].push_back(A);
  }
  vector<int> distT = bfs(u);
  vector<int> distA = bfs(v);
  int ans = 0;
  REP(i, N){
    if(distT[i] < distA[i]){
      ans = max(ans, distA[i]);
    }
  }
  cout << ans-1 << endl;
}

Measured memory_bytes: 7040
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define all(x) begin((x)), end((x))
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}


int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;cin>>n>>m;
    vector<vector<ll>> edges(n);
    vector<ll> next(n,-1);
    queue<ll> que;
    rep(i,m) {
        ll a,b;cin>>a>>b;
        a--;b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    que.push(0);
    while(!que.empty()) {
        ll now = que.front();
        que.pop();
        for(auto x:edges[now]) {
            if (next[x]==-1) {
                next[x] = now;
                que.push(x);
            }
        }
    }
    repr(i,1,n) {
        if (next[i]==-1){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    repr(i,1,n) {
        cout << next[i]+1<<endl;
    }
    return 0;
}


Measured memory_bytes: 13112
#include<iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<cstring>
#include<set>
#include<map>
#include<vector>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#define reep(n1,n2,n3) for(int n1=n3;n1<n2;n1++)
#define rep(n1,n2) reep(n1,n2,0)
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define INF 1e9
using namespace std;
typedef long long int lint;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int,int> > vp;
typedef pair<int,int> pi;
typedef pair<int,pair<int,int> > pii;
typedef vector<string> vs;
const double PI  = acos(-1.0);
int main(){
    int n;
    cin>>n;
    vi ca1(2*n),ca2(2*n);
    rep(i,2*n)ca1[i]=i+1;
    int m;
    cin>>m;
    rep(i,m){
        int k;
        cin>>k;
        if(k--){
            rep(j,2*n){
                if(j<=k){
                    if(i%2)ca1[j+2*n-k-1]=ca2[j];
                    else ca2[j+2*n-k-1]=ca1[j];
                }else{
                    if(i%2)ca1[j-k-1]=ca2[j];
                    else ca2[j-k-1]=ca1[j];
                }
            }
        }else{
            rep(j,2*n){
                if(j<n){
                    if(i%2)ca1[j*2]=ca2[j];
                    else ca2[j*2]=ca1[j];
                }else{
                    if(i%2)ca1[(j-n)*2+1]=ca2[j];
                    else ca2[(j-n)*2+1]=ca1[j];
                }
            }
        }
    }
    rep(i,2*n)
        if(m%2)cout<<ca2[i]<<endl;
        else cout<<ca1[i]<<endl;
}

Measured memory_bytes: 1196
from itertools import accumulate

n, k = map(int, input().split())

count = 0
a = [x for x in range(n+1)]
MOD = 10 ** 9 + 7

if k > n:
    print(1)
else:
    prefix_sum = list(accumulate(a))
    suffix_sum = list(accumulate(a[::-1]))

    res = [a - b + 1 for a, b in zip(suffix_sum, prefix_sum)]

    #print(prefix_sum)
    #print(suffix_sum)
    print(sum(res[k-1:]) % MOD)

    


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

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

    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }

    int lower = 0, upper = n, mid;
    while(upper - lower > 1){
        mid = (upper + lower) / 2;

        bool flag = true;
        map<int, int> string_data;

        for(int i=0; i+1<n; i++){
            if(a[i+1] > a[i]) continue;

            while(string_data.empty() == false){
                auto sd = *prev(string_data.end());
                if(sd.first >= a[i+1]) string_data.erase(sd.first);
                else break;
            }                

            int j = a[i+1] - 1;
            while(string_data.find(j) != string_data.end() && string_data[j] == mid - 1){
                string_data.erase(j);
                j -= 1;
            }
            if(j < 0){ flag = false; break; }

            if(string_data.find(j) == string_data.end()) string_data[j] = 0;
            string_data[j] += 1;

            if(string_data[j] >= mid){ flag = false; break; }
        }

        if(flag == true)  upper = mid;
        if(flag == false) lower = mid;
    }
    cout << upper << endl;
    return 0;
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
const int N = 405;
const int lg = 17;
const int mod = (int)1e9 + 7;
long long dp[N][N];
int a[N],b[N];
long long deg[N][N]; // i число с степенью
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int n,c;
    cin >> n >> c;
    for(int i = 1;i <= n;i++)cin >> a[i];
    for(int i = 1;i <= n;i++)cin >> b[i];
    dp[0][0] = 1;
    for(int i = 1;i <= n;i++){
        long long p[N];
        for(long long k = a[i];k <= b[i];++k)p[k] = 1;
        for(int j = 0;j <= c;j++){
            for(long long k = a[i];k <= b[i];k++){
                deg[i][j] += p[k];
                deg[i][j] %= mod;
                p[k] *= k;
                p[k] %= mod;
            }
        }
    }
    for(int i = 1;i <= n;i++){
        for(int s = 0;s <= c;++s){
            for(int j = 0;j <= c;++j){
                    if(s >= j)
                    dp[i][s] += ((deg[i][j] * dp[i - 1][s - j]) % mod),dp[i][s] %= mod;   
            }
        }
    }
    cout << dp[n][c];
  	return 0;
} 

Measured memory_bytes: 6188
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  vector<int> vec(101,0);
  for(int i=a;i<b;i++){
    vec[i]++;
  }
  for(int i=c;i<d;i++){
    vec[i]++;
  }
  sort(vec.begin(),vec.end());
  cout<<(vec.end()-lower_bound(vec.begin(),vec.end(),2));
}

Measured memory_bytes: 256
A,B,H,M=map(int, input().split())
import math
by=B*math.sin(math.radians(90-6*M))
bx=B*math.cos(math.radians(90-6*M))
ay=A*math.sin(math.radians(90-0.5*(H*60+M)))
ax=A*math.cos(math.radians(90-0.5*(H*60+M)))
#print(ax,ay,bx,by)
d=(ax-bx)**2+(ay-by)**2
print(d**0.5)

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

int h,w;
char s[400][400], oc[400][400];

char inv(char c){
    if (c == '.') return '#';
    else return '.';
}

int check(int i1, int j1, int i2, int j2){
    if (oc[i2][j2] || i2 < 0 || i2 >=h || j2 < 0 || j2 >= w) return 0;
    else if (s[i1][j1] == inv(s[i2][j2])) return 1;
    else return 0;
}

void search(int i, int j, long long* ndot, long long* nsharp){
    oc[i][j] = 1;
    char c = s[i][j];
    if(c == '.') *ndot = *ndot + 1;
    else if(c == '#') *nsharp = *nsharp + 1;

    if (check(i,j,i-1,j)) search(i-1,j,ndot,nsharp);
    if (check(i,j,i,j-1)) search(i,j-1,ndot,nsharp);
    if (check(i,j,i+1,j)) search(i+1,j,ndot,nsharp);
    if (check(i,j,i,j+1)) search(i,j+1,ndot,nsharp);
}

int main(){
    cin >> h >> w;
    for(int i=0;i<h;i++){
        string ss;
        cin >> ss;
        for(int j=0;j<w;j++){
            s[i][j] = ss[j];
            oc[i][j] = 0;
        }
    }

    long long result = 0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(oc[i][j] == 0){
                long long ndot=0, nsharp=0;
                search(i,j,&ndot,&nsharp);
                result += ndot * nsharp;
            }
        }
    }

    cout << result << endl;
}

Measured memory_bytes: 13056