akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        sc.close();
        int ans = 0;
        int i = 0;
        while (true) {
            if (i + k >= n) {
                ans++;
                break;
            }
            ans++;
            i += k - 1;
        }
        System.out.println(ans);

    }
}

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

ll memo[2020][2020];
int n;
vector<ll> a;

ll rec(int l, int len){
  if(memo[l][len]>0)return memo[l][len];
  if(len <= 1)return 0;

  int L = l, R = (l+len-1)%n;
  if(a[L]<a[R])R = (R+n-1)%n;
  else L = (L+1)%n;

  return memo[l][len] = max(a[L]+rec((L+1)%n,len-2) , a[R]+rec(L,len-2));
}

int main(){
  cin >> n;
  a.resize(n);
  for(int i=0;i<n;i++)cin >> a[i];

  ll res = 0;
  for(int i=0;i<n;i++){
    res = max( res, rec((i+1)%n,n-1) + a[i] );
  }
  cout << res << endl;
}

Measured memory_bytes: 32832
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define pb push_back
#define nl cout<<"\n"
#define db(x) cout<<x<<" "
#define fi(a,b) for(int i=a;i<b;i++)
#define fj(a,b) for(int j=a;j<b;j++)
#define fk(a,b) for(int k=a;k<b;k++)
#define F first
#define S second
#define UM unordered_map<int,int>
#define MP map<int,int>
#define mxsize (int)1e6

void fun(){
    int n;
    cin>>n;
    
    int a[n];
    fi(0,n) cin>>a[i];
    int g=a[0];
    map<int,int> mp;
    fi(1,n){
        g=__gcd(g,a[i]);
        mp[a[i]]++;
    }
    if(g!=1){
        cout<<"not coprime";
        return ;
    }
    for(auto i:mp){
        if(i.second > 1 && i.first != 1) {
            cout << "setwise coprime";
            return;
        }
    }
    
    fj(0,n){
        mp[a[j]]=1;
        for(int i=2;i*i<=a[j];i++){
            if(a[j]%i==0){
                int k=a[j]/i;
                if(mp[i]!=0||mp[k]!=0){
                    cout<<"setwise coprime";
                    return ;
                }
                mp[i]=1;
                mp[k]=1;
            }
        }
        
    }
    cout<<"pairwise coprime";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("/ATOM/input.txt", "r", stdin);
        freopen("/ATOM/output.txt", "w", stdout);
    #endif
    int t=1;
    // cin>>t;
    while(t--){
        fun();
    }
}

Measured memory_bytes: 54324
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		sc.nextLine();
		int[] a = new int[N];
		for (int i=0;i<N;i++){
			a[i] = sc.nextInt();
		}
		int profit = 0;
		int min = 2147483647;
		int count = 0;
		for (int i=0;i<N-1;i++){
			if (a[i+1]-a[i]>0){
				if (a[i]<min){
					min = a[i];
				}
				if (a[i+1]-min>profit){
					profit = a[i+1]-min;
					count = 1;
				}
				else if(a[i+1]-min==profit){
					count++;
				}
			}
		}
		System.out.println(count);
	}

}


Measured memory_bytes: 34012
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

int n,m,l[7],id[7],f[310][310][130];

int main()
{
    n=read();m=read();
    rep(i,1,n) l[i]=read();
    sort(l+1,l+1+n);
    rep(i,1,n-1) id[i]=i;
    int lim=(1<<(n-1))-1;
    double ans=0.0;
    while (1)
    {
        memset(f,0,sizeof(f));
        f[0][l[n]*n][0]=1;
        rep(i,1,n*m-1)
        {
            rep(j,i,n*m)
            {
                rep(sta,0,lim)
                {
                    f[i][j][sta]+=f[i-1][j][sta];
                    int x=i%n;
                    if ((!x) || ((sta>>(x-1))&1)) continue;
                    int nxtj=min(n*m,max(j,i+l[id[x]]*n)),nxts=(sta|(1<<(x-1)));
                    f[i][nxtj][nxts]+=f[i-1][j][sta];
                }
            }
        }
        ans+=f[n*m-1][n*m][lim];
        if (!next_permutation(id+1,id+n)) break;
    }
    //cout << ans << endl;
    rep(i,1,n-1) ans/=i;
    rep(i,1,n-1) ans/=m;
    printf("%0.15lf",ans);
    return 0;
}

Measured memory_bytes: 49024
n,*L=map(int,open(0).read().split())
G=[[]for _ in range(n)]
db=[-1]*n;db[0]=0
dw=[-1]*n;dw[-1]=0
for a,b in zip(*[iter(L)]*2):
	G[a-1]+=[b-1]
	G[b-1]+=[a-1]
q=[0]
while q:
	cur=q.pop(0)
	for nxt in G[cur]:
		if db[nxt]<0:
			q.append(nxt)
			db[nxt]=db[cur]+1
q=[n-1]
while q:
	cur=q.pop(0)
	for nxt in G[cur]:
		if dw[nxt]<0:
			q.append(nxt)
			dw[nxt]=dw[cur]+1
b=w=0
for i,j in zip(db,dw):
	if i<=j:b+=1
	else:w+=1
if b<=w:print("Snuke")
else:print("Fennec")

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

//abbriviations
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;

#define rep(i,a,b) for(ll i=a;i<b;i++)
#define _pb for push_back

//theory
//max(a,b)->returns the larger among a and b

//code
// do 
//     {
//         //process s
//     } 
// while (next_permutation(s.begin(),s.end()));

long long __gcd(ll a, ll b) 
{ 
    if (b == 0) 
        return a; 
    return __gcd(b, a % b);
}



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

    string s;
    cin >> s;
    rep(i,0,s.size())
    {
        if (s[i]=='?')
            s[i]='D';
        cout << s[i];
    }


    return 0;
}

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

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; }

using ll = long long;

int main() {
  int N;
  cin >> N;
  int cnt=0, cnta=0, cntb=0, cntn=0;
  for(int i = 0; i < N; i++) {
    string S;
    cin >> S;
    for(int j = 0; j < S.size()-1; j++) {
      if(S.at(j) == 'A'&&S.at(j+1) == 'B') cnt++;
    }
    if(S.at(0) == 'B') cntb++;
    if(S.at(S.size()-1) == 'A') cnta++;
    if(S.at(0) == 'B'&&S.at(S.size()-1) == 'A') cntn++;
  }
  int a = 0;
  if(cntn == cnta && cnta!=0 && cntn == cntb) a=1;
  cout << cnt + min(cnta, cntb) - a << endl;
}
        

Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int n;
    int d[55];
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&d[i]);
    }
    int j;
    int sum =0;
    for(i=1;i<=n;i++){
        for(j=i;j<=n;j++){
           if(i!=j){ 
            sum  += d[i]*d[j];
           }
        }
    }
    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
main(){
int n;cin>>n;
vector<int> beki={1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,484,529,576,625,676,729,784,841,900,961,8,27,125,216,343,512,1000,32,243,128};
sort(beki.rbegin(),beki.rend());
for(int i=0;;i++){
if(beki[i]<=n){
cout<<beki[i]<<endl;
return 0;
}
}
}

Measured memory_bytes: 764
#include <stdio.h>
int main(){

  int n,i,check=0,c;
  char aun[2];

  scanf("%d",&n);
  c=n;

  for(i = 0; i < c; i++){

    if(check == -1){

      printf("NO\n");
      return 0;

    }

    scanf("%s",aun);
    //printf("%s ",aun);                                                                                                                                                                       

    if(aun[0] == 'A') check++;
    else check--;

    // printf("%d ",check);                                                                                                                                                                    

  }

  if(check == 0) printf("YES\n");
  else  printf("NO\n");

  return 0;

}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 10000000000000009
//#define INF 9223372036854775807
typedef long long ll;
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define ORREP(i,n) for(int i=(n);i>=1;--i)
#define ZREP(i,n) for(int i=1;i<(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define rollcall cout<<"I'm Sucu."<<endl;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define out(s,t,u) s?cout << t << endl:cout << u << endl
#define int ll
#define Endl endl
typedef pair<int,int> Pp;

signed main(){
    int N,A[114514];
    cin >> N;
    REP(i,N){
        cin >> A[i];
    }
    sort(A,A+N);
    int Ans=0;
    
    if(N==2){
        cout << A[1]-A[0] << endl;return 0;
    }
    
    if(N==3){
        cout << max(A[2]+A[1]-2*A[0],2*A[2]-A[1]-A[0]) << endl;return 0;
    }
    
    
    if(N%2==0){//Nが偶数
        for(int i=N-1;i>N/2;i--){
            Ans+=2*A[i];
        }
        Ans+=A[N/2]-A[N/2-1];
        for(int i=0;i<N/2-1;i++){
            Ans-=2*A[i];
        }
        cout << Ans << endl;
    }else{
        for(int i=N-1;i>(N+1)/2;i--){
            Ans+=2*A[i];
        }
        Ans+=A[(N+1)/2]-A[(N-3)/2];
        Ans+=max(A[(N+1)/2]-A[(N-1)/2],A[(N-1)/2]-A[(N-3)/2]);
        for(int i=0;i<(N-3)/2;i++){
            Ans-=2*A[i];
        }
        cout << Ans << endl;
    }
    
    return 0;
}   


Measured memory_bytes: 1024
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>
#include <random>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;



int main(){
	string s;
	cin >> s;
	LL d[2019]={};
	d[0]=1;
	LL ret=0;
	LL m=0;
	reverse(s.begin(),s.end());
	LL p=1;
	for(auto c:s){
		m+=(c-'0')*p;
		m%=2019;
		p*=10;
		p%=2019;
		//cerr << m << endl;
		ret+=d[m];
		d[m]++;
	}
	cout << ret << endl;
    return 0;
}


Measured memory_bytes: 3500
#include<stdio.h>
#include<string.h>
int main()
{
	char s[15];
	gets(s);
	int n=strlen(s);
	int f=0;
	int sum=0;
	for(int i=0;i<n;i++){
		if(s[0]!='A'){
			f=1;
			break;
		}
		if(s[1]=='C'||s[n-1]=='C'){
			f=1;
			break;
		}
		else if(s[i]=='C'){
			sum++;
		}
		if(s[i]>'A'&&s[i]<'C'||s[i]>'C'&&s[i]<'Z'){
			f=1;
			break;
		}
	}
	if(sum==1&&f==0){
		printf("AC\n");
	}
	else printf("WA\n");
}


Measured memory_bytes: 128
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<utility>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<math.h>
#include <map>
using namespace std;
typedef long long int ll;
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,a) repi(i,0,a)
#define all(u) u.begin(),u.end()
#define pl pair<ll,ll>
#define fi first
#define se second
#define mod 1000000007
#define inf 1<<30
#define mp(a,b) make_pair(a,b)
#define len(u,N) u.begin(),u.begin()+N


ll k;
vector<ll> A(10);

int main() {
    rep(i,5) cin >> A[i];
    cin >> k;
    rep(i,4){
        repi(j,i+1,5){
            if (abs(A[i]-A[j]) > k){
                cout << ":(" << endl;
                return 0;
            }
        }
    }
    cout << "Yay!" << endl;
   
    
    return 0;
    
}


Measured memory_bytes: 256
fun main() {
    val (a, b, c) = readLine()!!.split(' ').map { it.toInt() }
    var ans = false

    var i = 1
    while (true) {
        if (i > 1 && a * i % b == a % b) {
            break
        }
        if (a * i % b == c) {
            ans = true
            break
        }
        i++
    }

    println(if (ans) "YES" else "NO")
}

Measured memory_bytes: 36276
#include<stdio.h>
int main()
{
int n,i,j,k,x,count;
	while(1){
		count=0;
		scanf("%d %d",&n,&x);
		if(n==0&&x==0){break;}
		for(i=1;i<n+1;i++){
			for(j=1;j<i;j++){
				for(k=1;k<j;k++){
					if(i+j+k==x){
						count++;
						//printf("(%d %d %d)\n", i, j, k);
					}
	
				}
			}
		
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<P> red(N), blue(N);
  for(int i = 0; i < N; i++){
    cin >> red.at(i).first >> red.at(i).second;
  }
  for(int i = 0; i < N; i++){
    cin >> blue.at(i).first >> blue.at(i).second;
  }
  vvi G(2*N, vi(0));
  for(int i = 0; i < N; i++){
    int x = red.at(i).first;
    int y = red.at(i).second;
    for(int j = 0; j < N; j++){
      int xx = blue.at(j).first;
      int yy = blue.at(j).second;
      if(x < xx && y < yy){
        G.at(i).push_back(N+j);
        G.at(N+j).push_back(i);
      }
    }
  }
  vi match(2*N, -1);
  vi flag(2*N, 0);
  function<bool(int)> dfs = [&](int v){
    flag.at(v) = 1;
    for(int i = 0; i < sz(G.at(v)); i++){
      int u = G.at(v).at(i);
      int w = match.at(u);
      if(flag.at(u)) continue;
      if(match.at(u) == -1 || (!flag.at(w) && dfs(w))){
        match.at(v) = u;
        match.at(u) = v;
        return true;
      }
    }
    return false;
  };
  int ans = 0;
  for(int i = 0; i < N; i++){
    if(match.at(i) != -1) continue;
    fill(ALL(flag), 0);
    if(dfs(i)) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 384
import java.util.*;

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

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        char[] S = sc.next().toCharArray();
        int N = S.length;

        int cnt1 = 0;
        int cnt2 = 0;
        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                if (S[i] != '0') cnt1++;
                if (S[i] != '1') cnt2++;
            } else {
                if (S[i] != '1') cnt1++;
                if (S[i] != '0') cnt2++;
            }
        }

        System.out.println(Math.min(cnt1, cnt2));
        return;
    }

}

Measured memory_bytes: 26276
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

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

using namespace std;

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

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

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

int N;
LL L[5011], R[5011];
pair<LL, int> P[5011];

LL dp[2][5011];
LL ep[2][5011];

void MAIN() {
    scanf("%d", &N);
    REP (i, N) scanf("%lld%lld", L+i, R+i);

    REP (i, N) P[i] = make_pair(L[i]+R[i], i);
    sort(P, P+N);
    reverse(P, P+N);

    memset(dp, 0x3f, sizeof dp);
    memset(ep, 0x3f, sizeof ep);
    int cur = 0, nxt = 1;
    dp[0][0] = 0;

    REP (i, N) {
	LL l = L[P[i].second];
	LL r = R[P[i].second];

	memset(dp[nxt], 0x3f, sizeof dp[nxt]);
	memset(ep[nxt], 0x3f, sizeof ep[nxt]);

	REP (a, i+1) {
	    int b = i-a;

	    if ((a+1)*2 <= N) {
		amin(dp[nxt][a+1], dp[cur][a] + r + (l+r)*a);
		amin(ep[nxt][a+1], ep[cur][a] + r + (l+r)*a);
	    }
	    if ((b+1)*2 <= N) {
		amin(dp[nxt][a], dp[cur][a] + l + (l+r)*b);
		amin(ep[nxt][a], ep[cur][a] + l + (l+r)*b);
	    }

	    amin(ep[nxt][a], dp[cur][a] + (N-1)/2*(l+r));
	}
	swap(cur, nxt);
    }

    LL ans;
    if (N % 2 == 0) ans = dp[cur][N/2];
    else ans = ep[cur][N/2];
    printf("%lld\n", ans);
}

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



Measured memory_bytes: 512
import java.util.Scanner;

public class Main
{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		long n=sc.nextLong();
		long m=sc.nextLong();
		long ans=0;
		if(n>=2){
			ans+=(n*(n-1))/2;
		}
		if(m>=2){
			ans+=(m*(m-1)/2);
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21460
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 105
#define mod 1000000007
#define ll long long
#define INF 0x7fffffff
int n, m, s;
ll gcd(ll a, ll b){return b ? gcd(b, a%b) : a;}
ll C(ll n, ll m)
{
    m = min(m, n - m);
    ll mul = 1, div = 1;
    for (int i = 0; i < m; i++)
    {
        mul *= (n - i);
        div *= (i + 1);
        ll g = gcd(mul, div);
        mul /= g, div /= g;
    }
    return mul / div;
}
int main(){
    ll n,m,ans=0;
    cin>>n>>m;
    if(n<2) ans+=0;
    else ans+=C(n,2);
    if(m<2) ans+=0;
    else ans+=C(m,2);
    cout<<ans;
    return 0;
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
#define reps(i,n) for(ll i=1;i<=(n);++i)
using ll = long long;
using str = string;
constexpr long long INF = (1LL<<60);
constexpr long long MOD = (1e9+7);
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;}
template<class T>inline bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
inline void dump(){cout<<endl;}
template<class Head,class... Tail>inline void dump(Head&& head, Tail&&... tail){cout<<head<<", ";dump(forward<Tail>(tail)...);}
template<typename T>inline istream &operator>>(istream&input,vector<T>&v){for(auto &elemnt:v)input>>elemnt;return input;}
using vertex = struct vertex{ll to,cost;vertex(ll to,ll cost):to(to),cost(cost){}};
using _vertex = struct _vertex{ll to;_vertex(ll to):to(to){}};
using edge = struct edge{ll from,to,cost;edge(ll from,ll to,ll cost):from(from),to(to),cost(cost){}};
using _edge = struct _edge{ll from,to;_edge(ll from,ll to):from(from),to(to){}};
using un_weighted_adjlist = vector<vector<_vertex>>;
using weighted_adjlist = vector<vector<vertex>>;
using un_weighted_edge = vector<_edge>;
using weighted_edge = vector<edge>;
main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);
  
  ll n,k;
  cin>>n>>k;
  un_weighted_adjlist adj(n);
  rep(i,n-1){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  vector<ll> res(n),confirm(n);
  stack<ll> que;
  que.push(0);
  while(!que.empty()){
    auto v=que.top();
    que.pop();
    ll cnt=0;
    for(const auto& nv:adj[v]){
      if(res[nv.to]!=0)cnt+=confirm[nv.to];
      else que.push(nv.to);
    }
    res[v]=k-cnt;
    if(res[v]<0){
      cout<<(0)<<endl;
      return 0;
    }
    confirm[v]++;
    for(const auto& nv:adj[v])confirm[nv.to]++;
  }

  ll ans=1ll;
  rep(i,n)(ans*=res[i])%=MOD;
  cout<<(ans%MOD)<<endl;
//for(auto x:res)cout<<x<<" ";cout<<endl;

}


Measured memory_bytes: 8948
import sys
input = sys.stdin.buffer.readline

n = int(input())
l = list(map(int,input().split()))
l.sort()
mx = l[-1]+l[-2]

length = [0]*(mx+1)
for i in range(n):
    for j in range(i+1,n):
        length[l[i]+l[j]] -= 1
        length[l[j]-l[i]+1] += 1

for i in range(1,mx+1):
    length[i] += length[i-1]

minus = [0]*n
for i in range(n):
    a = i
    for j in range(i+1,n):
        if l[i]*2 - 1 >= l[j]:
            a += 1
    minus[i] = a
#print(length)
#print(minus)
ans = 0
for i in range(n):
    ans += length[l[i]] - minus[i]


print(ans//3)

Measured memory_bytes: 73640
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <functional>
#include <climits>
#include <string>
#include <map>

#include <iomanip>


int main() {
	int n, k; std::cin >> n >> k;
	long double result = 0;
	for (auto i = 1; i <= n; ++i) {
		long double prob = 1;
		auto current = i;
		while (current < k) {
			current *= 2;
			prob /= 2;
		}
		result += prob;
	}
	std::cout << std::setprecision(15) << std::fixed << result / n << std::endl;
}

Measured memory_bytes: 888
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int maxn=100+10,maxm=1000000+10,inf=1000000000;
int h[maxn*2],now[maxn*2],d[maxn*2],go[maxm*2],dis[maxm*2],fx[maxm*2],nxt[maxm*2];
bool bz[maxn*2];
int i,j,k,l,t,n,m,tot,top,tmp,sx,sy,tx,ty,s,x,y;
char ch;
char get(){
	char ch=getchar();
	while (ch!='.'&&ch!='o'&&ch!='S'&&ch!='T') ch=getchar();
	return ch;
}
void add(int x,int y,int z,int d){
	go[++tot]=y;
	dis[tot]=z;
	fx[tot]=tot+d;
	nxt[tot]=h[x];
	h[x]=tot;
}
int dfs(int x,int flow){
	if (x==t){
		tmp+=flow;
		return flow;
	}
	bz[x]=1;
	int r=now[x],k;
	while (r){
		if (!bz[go[r]]&&dis[r]&&d[x]==d[go[r]]+1){
			k=dfs(go[r],min(dis[r],flow));
			if (k){
				dis[r]-=k;
				dis[fx[r]]+=k;
				now[x]=r;
				return k;
			}
		}
		r=nxt[r];
	}
	return now[x]=0;
}
bool change(){
	int i,r,tmp=inf;
	fo(i,s,t)
		if (bz[i]){
			r=h[i];
			while (r){
				if (!bz[go[r]]&&dis[r]&&d[go[r]]+1-d[i]<tmp) tmp=d[go[r]]+1-d[i];
				r=nxt[r];
			}
		}
	if (tmp==inf) return 0;
	fo(i,s,t)
		if (bz[i]) d[i]+=tmp;
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	fo(i,1,n)
		fo(j,1,m){
			ch=get();
			if (ch=='S') sx=i,sy=j;
			else if (ch=='T') tx=i,ty=j;
			else if (ch=='o'){
				add(i+1,j+n+1,1,1);
				add(j+n+1,i+1,0,-1);
				add(j+n+1,i+1,1,1);
				add(i+1,j+n+1,0,-1);
			}
		}
	s=1;t=n+m+2;
	add(s,sx+1,inf,1);
	add(sx+1,s,0,-1);
	add(s,sy+n+1,inf,1);
	add(sy+n+1,s,0,-1);
	add(tx+1,t,inf,1);
	add(t,tx+1,0,-1);
	add(ty+n+1,t,inf,1);
	add(t,ty+n+1,0,-1);
	do{
		fo(i,s,t) now[i]=h[i];
		fill(bz+s,bz+t+1,0);
		while (dfs(s,inf)) fill(bz+s,bz+t+1,0);
	}while (change());
	if (tmp>=inf) printf("-1\n");else printf("%d\n",tmp);
}

Measured memory_bytes: 6528
from math import sqrt
from collections import defaultdict

n, m = [int(i) for i in input().split()]

A = defaultdict(int)
p = 10 ** 9 + 7

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2

while m != 1 and i <= sqrt(m) + 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if m != 1:
    A[m] = 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

Measured memory_bytes: 12132
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll N, M;
	cin >> N >> M;
  	bool flag =false;
	map<ll,ll>mp;
	for (ll i = 0; i < M; i++) {
		ll a, b;
      	cin>>a>>b;
		if(a==1) mp[b]++;
    	if(b==N) mp[a]++;
    }
	for(auto p: mp ){
      if(p.second>=2)
        flag =true;
    }
	cout << ((flag) ? "POSSIBLE" : "IMPOSSIBLE")<< endl;
}
    

Measured memory_bytes: 12800
N = int(input())
A = input().split()
AA = [int(s) for s in A]

def Even(X):
    counter = 0
    for i in range(len(X)):
        if X[i] % 2 == 0:
            counter += 1
    if counter == len(X):
        return True
    else:
        return False

counter = 0
while Even(AA) == True:
    AA = [int(i / 2) for i in AA]
    counter += 1

print(counter)


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


int main() {

  int A, B, C;

  cin >> A >> B >> C;

  if(A == B && B == C)
  {
    cout << "No" << endl;
  }
  else if(A != B && B != C && C != A)
  {
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }

  return 0;
}

Measured memory_bytes: 256
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a >= b) { a = b; return 1; } return 0; }

//next[i][c]:= Sの i文字目以降で最初に文字 cが登場する index (Sは英小文字のみで構成)
vector<vector<int> > calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n+1, vector<int>(26, n));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'a'] = i;
    }
    return res;
}

void solve() {
	string a; cin >> a;
    auto next = calcNext(a);
    int n = (int)a.size();
    vector<int> dp(n + 1, inf);
    vector<char> rec(n + 1, '?');
    dp[n] = 1;
    for(int i = n - 1; i >= 0; --i) {
        per(j, 26) {
            if(next[i][j] == n) {
                if(chmin(dp[i], 1)) {
                    rec[i] = j + 'a';
                }
            } else if(chmin(dp[i], dp[next[i][j] + 1] + 1)) {
                rec[i] = j + 'a';
            }
        }
    }
    int now = 0;
    while(now < n) {
        cout << rec[now];
        now = next[now][rec[now] - 'a'] + 1;
    }
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

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

char board[105][105];
int dp[105][105];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>board[i]+1;
    memset(dp,127,sizeof(dp));
    dp[1][1] = (board[1][1]=='#');
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(i>1) dp[i][j] = min(dp[i][j],dp[i-1][j]+(board[i-1][j]=='.'&&board[i][j]=='#'));
            if(j>1) dp[i][j] = min(dp[i][j],dp[i][j-1]+(board[i][j-1]=='.'&&board[i][j]=='#'));
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
int main() {
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n; i++) {
        int x,y,b,p;
        int bb = 0,pp = 0;
        int tmp = 1e+8;
        scanf("%d%d%d%d",&x,&y,&b,&p);
        int cost = x * b + y * p;
        if(b >= 5 && p >= 2) cost *= 0.8;
        else {
            if(b < 5) bb = 5 - b;
            if(p < 2) pp = 2 - p;
            tmp = (cost + x * bb + y * pp) * 0.8;
        }
        printf("%d\n",min(cost,tmp));
    }
    return 0;
}

Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  for(int i=0;i<3;i++){
    if((s.at(i)-'0')==1) s.at(i)='9';
    else if((s.at(i)-'0')==9) s.at(i)='1';
  }
  cout << s << endl;
}


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

int main(int argc, const char *argv[])
{
    int n, m;
    cin >> n >> m;

    int p, ac = 0, wa = 0;
    string s;
    map<int, int> mp;
    for (int i = 0; i < m; i++)
    {
        cin >> p >> s;
        if (s == "AC")
        {
            if (mp[p] != -1)
            {
                ac++;
                wa += mp[p];
                mp[p] = -1;
            }
        }
        else
        {
            if (mp[p] != -1)
            {
                mp[p]++;
            }
        }
    }
    cout << ac << ' ' << wa << endl;
}

Measured memory_bytes: 4992
using System;

class Program
{
    static long MOD = 1000000007L;

    static void Main()
    {
        var N = long.Parse(Console.ReadLine());
        var result = ModPow(10, N);
        result = (result + MOD - ModPow(9, N)) % MOD;
        result = (result + MOD - ModPow(9, N)) % MOD;
        result = (result + ModPow(8, N)) % MOD;
        Console.WriteLine(result);
    }

    static long ModPow(long x, long y)
    {
        var m = x % MOD;
        for (int i = 1; i < y; i++)
        {
            m = (m * x) % MOD;
        }
        return m;
    }
}


Measured memory_bytes: 27496
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.nextInt();
            out.println(n >= 90 || n % 10 == 9 ? "Yes" : "No");
        }

    }

    static class FastScanner {
        private InputStream in;
        private byte[] buffer = new byte[1024];
        private int bufPointer;
        private int bufLength;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private int readByte() {
            if (bufPointer >= bufLength) {
                if (bufLength == -1)
                    throw new InputMismatchException();

                bufPointer = 0;
                try {
                    bufLength = in.read(buffer);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (bufLength <= 0)
                    return -1;
            }
            return buffer[bufPointer++];
        }

        private static boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public long nextLong() {
            long n = 0;

            int b = readByte();
            while (isSpaceChar(b))
                b = readByte();

            boolean minus = (b == '-');
            if (minus)
                b = readByte();

            while (b >= '0' && b <= '9') {
                n *= 10;
                n += b - '0';
                b = readByte();
            }

            if (!isSpaceChar(b))
                throw new NumberFormatException();

            return minus ? -n : n;
        }

        public int nextInt() {
            long n = nextLong();

            if (n < Integer.MIN_VALUE || n > Integer.MAX_VALUE)
                throw new NumberFormatException();

            return (int) n;
        }

    }
}



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


void knapsack(ll n,ll w,ll value[],ll wt[],ll sum)
{
    ll dp[n+1][sum+1];
    
    for(ll i=0;i<=n;i++)
    {
        dp[i][0]=0;
    }
    
    for(ll i=1;i<=sum;i++)
    {
        dp[0][i]=-1;
    }
    
    //dp[i][j] = Minimum weight required to make value j with elements upto (i-1)th index.
    //dp[i][j]=-1 represents this value can't be made with elements upto (i-1)th index.
    
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=sum;j++)
        {
            ll exclude=dp[i-1][j];
            
            ll include=-1;
            
            if(value[i-1]<=j && dp[i-1][j-value[i-1]]!=-1)
            {
                include=wt[i-1]+dp[i-1][j-value[i-1]];
            }
            
            if(include==-1 && exclude==-1)
            {
                dp[i][j]=-1; //this value can't be made
            }
            
            else if(include==-1)
            {
                dp[i][j]=exclude;
            }
            
            else if(exclude==-1)
            {
                dp[i][j]=include;
            }
            else
            {
                dp[i][j]=min(include,exclude);
            }
          
        }
        
    }
    
    ll bestans=-1;
    
    for(ll i=0;i<=sum;i++)
    {
        if(dp[n][i]!=-1 && dp[n][i]<=w)
        {
            bestans=i;
        }

    }
   
    cout<<bestans;
    
    
}


int main() {

	    ll n;
	    cin>>n;
	    //cout<<n<<"\n";
	    ll w;
	    cin>>w;
	  //  cout<<w<<"\n";
	    ll value[n];
	     ll wt[n];
	     ll sum=0;
	    for(ll i=0;i<n;i++)
	    {
	          cin>>wt[i];
	        cin>>value[i];
	       sum=sum+value[i];
	    }
	  
	   
	   knapsack(n,w,value,wt,sum);
	   
	 
	    
	
	return 0;
}


Measured memory_bytes: 79104
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <set>

using namespace std;


int main(){
	int n;
	cin >>n;
	vector<int> a;
	a.resize(n);
	for(int i=0; i<n; i++) cin >> a[i];
	sort(a.begin(), a.end(), greater<int>());
	
	
	vector<long long> len;
	int count=1;
	int f=a[0];
	for(int i=1; i<n; i++){
		if(a[i]==f) count+=1;
		else{
			f=a[i];
			count =1;
		}
		
		if(count ==2) len.push_back(f);
		if(count ==4) len.push_back(f);
	}
	sort(len.begin(), len.end(), greater<int>());
	if(len.size()>=2) cout << len[0]*len[1] << endl;
	else cout << 0 << endl;
	
	return 0;
}


Measured memory_bytes: 1276
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<n; ++i)
typedef long long ll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

//繰り返しn乗法……aをn乗したもののMOD(M)をとる
ll rep_power_modM(ll a, ll n, ll M){
    if(n == 0)return 1;
    if(n%2 == 0){ll tmp = rep_power_modM(a,n/2,M); return tmp*tmp%M;}
    return a*rep_power_modM(a,n-1,M)%M;
}

int main(){
    ll h; cin>>h;
    int count = 0;
    while(h>1){++count; h /= 2;}
    ll ans = 0;
    for(; count>=0; --count){
        ans += rep_power_modM(2,count,INF);
    }
    cout<<ans<<endl; return 0;
}


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

typedef long long ll;
typedef vector <bool> v_bool;
typedef vector <ll> v_ll;
typedef vector <vector <ll> > vv_ll;
typedef vector < pair <ll,ll> > vp_ll;
typedef pair <ll,ll> p_ll;

bool TEST=false;
ll MOD = 1000000007;

void show(){if (TEST){cout << endl;}}
void show(string x){if (TEST){cout << x;}}
void show(string x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(ll x){if (TEST){cout << x;}}
void show(ll x,bool enter){
  if (TEST){if (enter) cout << "<#> " << x << endl;else cout << x;}
}
void show(p_ll p){
  if (TEST){cout << "{ ";show(p.first);cout << " ";show(p.second);cout << " }";}
}
void show(v_ll v){
  if (TEST){
    cout << "<begin> ";
    for (ll i=0;i<v.size();i++){show(v[i]); cout << " ";}cout <<"<end>"<< endl;
}}
void show(vv_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}
void show(vp_ll v){
  if (TEST){
    cout << "//////////" << endl;
    for (ll i=0;i<v.size();i++){
      show(v[i]); cout << endl;
}}}

ll mod(ll x){
  ll n=MOD;
  ll ret=x%n;
  if (ret<0)ret+=n;
  return ret;
}
void mod_self(ll &x){
  x=mod(x);
}
ll mod_inv(ll x){
  ll n=MOD;
  ll y = x,z = n-2, ret=1;
  y=mod(y);
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  return ret;
}
ll mod_pow(ll x,ll a){
  ll y = x,z = a,ret=1;
  y=mod(y);
  if (z<0)z=-z;
  while (z>0){
    if(z%2==1) ret=mod(ret*y);
    y=mod(y*y);
    z/=2;
  }
  if (a<0) ret=mod_inv(ret);
  return ret;
}
v_ll mod_nck(ll n){
  v_ll nck(n+1,0);
  nck[0]=1;
  for (ll i=1;i<=n;i++){
    nck[i]=mod(nck[i-1]*(n+1-i));
    nck[i]=mod(nck[i]*mod_inv(i));
  }
  return nck;
}
v_ll mod_factorial(ll n){
  v_ll fct(n+1,0);
  fct[0]=1;
  for (ll i=1;i<=n;i++){
    fct[i]=mod(fct[i-1]*i);
  }
  return fct;
}

ll N,K,ans;
v_ll A;
int main(){
  cin >> N >> K;
  A.assign(N+10,0);
  for (ll i=1;i<=N;i++){
    cin >> A[i];
  }
  ans=0;
  for (ll i=1;i<=N;i++){
    for (ll j=1;j<N;j++){
      if (A[j]>A[j+1]){swap(A[j],A[j+1]);ans++;}
    }
  }
  //cout << ans << endl;
  ans*=K;
  ans*=2;
  ll k2=K*(K-1)/2;
  k2%=MOD;
  for (ll i=1;i<=N;i++){
    ll x=upper_bound(A.begin()+1,A.begin()+N+1,A[i])-lower_bound(A.begin()+1,A.begin()+N+1,A[i]);
    ll y=((N-x)*k2)%MOD;
    ans+=y;
    ans%=MOD;
  }
  ans*=mod_inv(2);
  ans%=MOD;
  cout << ans << endl;
}


Measured memory_bytes: 888
def chmin(a, b):
    if a > b:
        a = b
        return a
    else:
        return a

n = int(input())
ls = list(map(int, input().split()))

dp = [10**9] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = chmin(dp[i], dp[i - 1] + abs(ls[i] - ls[i - 1]))
    if i > 1:
        dp[i] =  chmin(dp[i], dp[i - 2] + abs(ls[i] - ls[i - 2]))

print(dp[n - 1])

Measured memory_bytes: 13976
class SegTreeMin
    attr_reader :dat
    def initialize(n_input, top=Float::INFINITY)
        @n_input = n_input
        @n = 1 << @n_input.to_s(2).length
        @top = top
        @dat = Array.new(2 * @n - 1, @top)
    end

    def update(k, a)
        k += @n - 1
        @dat[k] = a
        while k > 0
            k = (k - 1) / 2
            #@dat[k] = [@dat[2*k+1], @dat[2*k+2]].min
            @dat[k] = @dat[2*k+1]
            @dat[k] = @dat[2*k+2] if @dat[k] > @dat[2*k+2]
        end
    end

    # This works only when inserting larger value than all existing values
    def update_larger(k, a)
        k += @n - 1
        @dat[k] = a
        while k > 0
            k = (k - 1) / 2
            if @dat[k] <= a
                break
            else
                @dat[k] = a
            end
        end
    end

    # include a and b
    def min_between(a, b)
        query(a, b + 1, 0, 0, @n)
    end

    def query(a, b, k, l, r)
        return @top if r <= a || b <= l
        return @dat[k] if a <= l && r <= b
        vl = query(a, b, k * 2 + 1, l, (l + r) / 2)
        vr = query(a, b, k * 2 + 2, (l + r) / 2, r)
        #return [vl, vr].min
        return vl < vr ? vl : vr
    end
end

def power_mod(num, power)
    prod = 1
    num %= MOD
    while power > 0 do
        if power & 1 == 1
            prod = (prod * num) % MOD
        end
        num = (num * num) % MOD
        power >>= 1
    end
    return prod
end

class Array
    include Comparable
end

MOD = 10**9+7

N = gets.to_i
$hs = gets.split.map(&:to_i)
$st = SegTreeMin.new(N, [10**10, 10**10])
N.times do |i|
    $st.update(i, [$hs[i], i])
end

def rec(left, right, height)
    if left > right
        return [1, -1]
    end
    if left == right
        num = power_mod(2, $hs[left] - height)
        return [num, 0]
    end
    min, i = $st.min_between(left, right)
    ldp1, ldp2 = rec(left, i-1, min)
    rdp1, rdp2 = rec(i+1, right, min)
    dp1 = ldp1 * rdp1 * power_mod(2, min-height) % MOD
    dp2 = ((2*ldp1 + ldp2) * (2*rdp1 + rdp2) * 2 - 2 * ldp1 * rdp1) % MOD
    return [dp1, dp2]
end

puts rec(0, N-1, 0).inject(:+) % MOD

Measured memory_bytes: 1788
def f(n: int) -> int:
    if n % 2 == 0:
        return n // 2
    else:
        return 3 * n + 1


s = int(input())
sequences = [s]
while True:
    s = f(s)
    if s in sequences:
        print(len(sequences) + 1)
        break
    else:
        sequences.append(s)


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define F(i,a,b) for(int i=a;i<=b;i++)
#define D(i,a,b) for(int i=a;i>=b;i--)
#define MAXN 101
using namespace std;
char s[MAXN];
bool flag;
int main()
{
	cin>>s;
	int len=strlen(s);
	F(i,0,len-1)
	{
		if(flag&&s[i]=='F')
		{
			printf("Yes");return 0;
		}
		if(s[i]=='C')flag=true;
	}
	printf("No"); 
} 

Measured memory_bytes: 256
# coding: utf-8

N, X, Y = map(int, input().split())

n_k = [0] * (N+1)

for i in range(1, N):
    for j in range(i+1, N+1):
        n_k[min(abs(j-i), abs(X-i) + 1 + abs(j-Y))] += 1

for k in range(1, N):
    print(n_k[k])


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


#include <bits/stdc++.h>

using namespace std;

class EDoubleFactorial {
public:
    void solve(std::istream &cin, std::ostream &cout) {
        int64_t n;
        cin >> n;
        if (n % 2 != 0) {
            cout << 0 << endl;
        } else {
            int64_t tmp = 5;
            int64_t ans = 0;
            while (n > tmp) {
                ans += n / tmp / 2;
                n /= tmp;
            }
            cout << ans << endl;
        }
    }
};


int main() {
    EDoubleFactorial solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

int gcd(int a, int b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int x;
  cin >> x;
  cout << 360 / gcd(360, x);

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


Measured memory_bytes: 3184
using System;

class Program
{
	public static void Main(string[] args)
	{
		int minMagicTimes = 0;

        int N = int.Parse(Console.ReadLine());
        // スペース区切りの整数の入力
        string[] input = Console.ReadLine().Split(' ');

		for (int i = 0; i < input.Length-1;i++){
			if(input[i]==input[i+1]){
				minMagicTimes++;
				i++;
			}
		}
		Console.WriteLine(minMagicTimes);
	}
}


Measured memory_bytes: 13140
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int t=stdIn.nextInt();
        int h=t/3600;
		int m=(t%3600)/60;
		int s=t%3600%60;
		System.out.println(h+":"+m+":"+s);
	}
}


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

int main() {
    int K;
    string S;
    cin >> K >> S;
    
    if(S.size() > K){
        for(int i=0; i<K; i++){
            cout << S[i];
        }
        cout << "..." << endl;
    }else{
        cout << S << endl;
    }


}


Measured memory_bytes: 3596
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <climits>
#include <cmath>
#include <functional>
#include <map>
// #include <bits/stdc++.h>
using namespace std;

#define size_t int
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define debug(x) cerr << #x << " = " << (x) << " (line " << __LINE__ << ")" << endl;
#define debug1(i, x) cerr << "(" << (i) <<  ") " << #x << " = " << (x) << " (line " << __LINE__ << ")" << endl;
#define debug2(i, j, x) cerr << "(" << (i) << ", " << (j) <<  ") " << #x << " = " << (x) << " (line " << __LINE__ << ")" << endl;
template <typename T> class vec2d : public vector<vector<T>> {
public:
    vec2d(int H, int W): vector<vector<T>> (H, vector<T>(W)) {
    }
};
template <typename T> istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) is >> x;
  //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいいです。
  return is;
}
template <typename T> ostream& operator << (ostream& os, vector<T>& vec){
  REP(i, vec.size()) {
    os << vec[i] << ( i+1 == vec.size() ? "" : " " );
  }
  return os;
}
struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0);
        // cout<<fixed<<setprecision(20);
    };
}aaaaaaa;

signed main(signed argc, char **argv) {
  int N, M;
  cin >> N >> M;
  vector<vector<int>> s(M, vector<int>());
  for (size_t i = 0; i < M; i++) {
    int k;
    cin >> k;
    s[i].reserve(k);
    for (size_t j = 0; j < k; j++) {
      int tmp;
      cin >> tmp;
      s[i].push_back(tmp - 1);
    }
  }
  int p[M];
  for (size_t i = 0; i < M; i++) {
    cin >> p[i];
  }
  int index = pow(2, N);
  // debug(index);
  // debug(s[0]);
  int ans = 0;
  for (size_t i = 0; i < index; i++) {
    bool ok = true;
    for (size_t j = 0; j < M; j++) {
      int on = 0;
      for (size_t z = 0; z < s[j].size(); z++) {
        int a = s[j][z];
        // debug(a);
        if (i >> a & 1) {
          on++;
        }
      }
      // debug(on);
      if (on % 2 != p[j]) {
        ok = false;
      }
    }
    if (ok) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=202202;
int a[N];
int n;
int main(){
	scanf("%d",&n);
	for (int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	int mx=a[1];
	ll sum=0;
	for (int i=2; i<=n; i++){
		sum=sum+max(0,mx-a[i]);
		mx=max(mx,a[i]);
	}
	printf("%lld\n",sum);
	return 0;
}

Measured memory_bytes: 2460
#include<iostream>
#include<string>
using namespace std;
int main(){
    long N;
    cin>>N;
    string p,q,r;
    cin>>p>>q>>r;
    int m=0;
    for (int i=0;i<N;++i){
        if ((p[i]==q[i]&&p[i]!=r[i])|(p[i]==r[i]&&p[i]!=q[i])|(r[i]==q[i]&&p[i]!=r[i])){
            m+=1;
        }else if((p[i]!=r[i])&&(q[i]!=r[i])&&(p[i]!=r[i])){
            m+=2;
        }else{
            continue;
        }
    }
cout<<m<<endl;
}

Measured memory_bytes: 256