akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

int dp[10][10];
void solve()
{
    int K;
    scanf("%d", &K);

    int i,j,k;
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            if (i == 0) {
                dp[i][j] = 1;
            }
            else {
                for (k = -1; k <= 1; k++) {
                    int j2 = j + k;
                    if (j2 >= 0 && j2 <= 9) {
                        dp[i][j] += dp[i - 1][j2];
                    }
                }
            }
        }
     }

    vector<int> s(10);
    for (i = 0; i < 10; i++) {
        if (i > 0) s[i] = s[i - 1];
        for (j = 1; j < 10; j++) {
            s[i]+=dp[i][j];
        }
        //printf("[%d]%d\n", i, s);
        if (s[i] >= K) {
            break;
        }
    }

    int num = (i>0? s[i - 1]: 0);
    int curr = 0;
    for (k = 1; k < 10; k++) {
        if (num + dp[i][k] >= K) {
            curr = k;
            break;
        }
        else {
            num += dp[i][k];
        }        
    }
    printf("%d", curr);

    for(j=i-1; j>=0; j--) {
        int bgn = MAX(0,curr - 1);
        int end = MIN(9,curr + 1);
        for (k = bgn; k <= end; k++) {
            if (num + dp[j][k] >= K) {
                curr = k;
                printf("%d", curr);
                break;
            }
            else {
                num += dp[j][k];
            }        
        }
    }
    printf("\n");

    return;
}

int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}


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


void solve(long long A, long long B, long long H, long long M){
    long double thetaM = M * 6;
    long double thetaH = 1.0L * H * 30 + M / 2.0;
    //cout<<thetaM<<" "<<thetaH<<endl;
    thetaM /= 180.0;
    thetaM *= 3.141592653589793238462643383279;
    thetaH /= 180.0;
    thetaH *= 3.141592653589793238462643383279;
    long double x = cos(thetaH) * A - cos(thetaM) * B;
    long double y = sin(thetaH) * A - sin(thetaM) * B;
    cout<<setprecision(30)<<hypot(x, y)<<endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long H;
    scanf("%lld",&H);
    long long M;
    scanf("%lld",&M);
    solve(A, B, H, M);
    return 0;
}


Measured memory_bytes: 4256
import java.util.Scanner;

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

        int N = sc.nextInt();
        int[] mountains = new int[N];
        for (int i = 0; i < N; i++) {
            mountains[i] = sc.nextInt();
        }

        int answer = 0;

        int highest = 0;
        for (int i = 0; i < N; i++) {
            if (highest <= mountains[i]) {
                answer++;
                highest = mountains[i];
            }
        }

        System.out.println(answer);
    }
}

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

typedef struct strc{

    int val;
    int amount;

    strc(int v, int a){
        val = v;
        amount = a;
    }

}drinkinfo;


bool cmp(const strc &a,const strc &b){
    return a.val < b.val;
}



int main(){
    long long ans=0;
    int sum=0;
    int v,a;
    int n,m;
    cin >>n>>m;

    vector<drinkinfo> d;

    for (int i = 0; i < n; i++){
        cin >>v>>a;
        d.push_back(drinkinfo(v,a));
    }
    
    sort(d.begin(),d.end(),cmp);
    
    int i=0;
    while(sum <= m){
        if(i>=n)break;

        int buy=min(d[i].amount,m-sum);
        sum += buy;
        ans += (long long)buy*d[i].val;
        i++;
    }
    


    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 1400
#include<stdio.h>
#include<string.h>

int main(void){

char s[7];

scanf("%s",&s);

if(strcmp(s,"Sunny")==0){printf("Cloudy");}
if(strcmp(s,"Cloudy")==0){printf("Rainy");}
if(strcmp(s,"Rainy")==0){printf("Sunny");}

return 0;
}

Measured memory_bytes: 1632
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
const ll mod = 1e9 + 7;
ll dp[303][303][303], a[303];
vi v{0};
ll f(int i, int j) {
	return max(v[j]-v[i], 0ll);
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp, 0x0f, sizeof dp);
	ll n, k;
	cin >> n >> k;
	a[0]=0;
	for(int t, i = 1; i <= n; i++) {
		cin >> t;
		a[i]=t;
		v.pb(t);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	for(int i = 0; i <=n; i++) a[i] = lower_bound(all(v), a[i])-v.begin();
	ll ans = LLONG_MAX;
	dp[0][k][0]=0;
	for(int i = 1; i <= n; i++) {
		for(int lft = 0; lft <= k; lft++) {
			ll aa = 2e18;
			for(int c = 0; c < v.size(); c++)
			dp[i][lft][a[i]]=min(dp[i][lft][a[i]], dp[i-1][lft][c]+f(c, a[i]));
			for(int cur = 0; cur < v.size(); cur++) {
				if(cur) {
					aa += -v[cur-1]+v[cur];
				}
				aa = min(aa, dp[i-1][lft+(cur!=a[i])][cur]);
				dp[i][lft][cur] = min(dp[i][lft][cur], aa);
				if(i == n) {
					ans = min(ans, dp[i][lft][cur]);
				}
			}
			aa = 2e18;
			for(int cur = v.size(); cur--;) {
				aa = min(aa, dp[i-1][lft+(cur!=a[i])][cur]);
				dp[i][lft][cur] = min(dp[i][lft][cur], aa);
//				cout << i << " " << lft << " " << cur << " " << dp[i][lft][cur] << "\n";
				if(i == n) {
					ans = min(ans, dp[i][lft][cur]);
				}
			}
		}
	}
	cout << ans << "\n";
}


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

def myAnswer(s:int) -> int:
   i = 1
   a = [s]
   hantei = False
   while True:
      tmp = f(a[i - 1])
      if(tmp == 1):
         if(hantei == True):
            a.append(tmp)
            break
         else:
            hantei = True
      a.append(tmp)
      i+=1
   ans = 10**9
   while len(a) != 0:
      n = len(a)
      m = a.pop(-1)
      if(m in a):
         ans = min(ans,n)
   return ans



def modelAnswer():
   tmp=1
def main():
   s = int(input())
   print(myAnswer(s))

if __name__ == '__main__':
   main()

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

using namespace std;

typedef vector<long long> vi;

long long n,num,fin=0;
vi a,res;
bool kt=1;

void run(long long pos){
    //cout << num << " " << pos << " " << a[pos] << " " << fin << endl;
    if(num-a[pos]>1||pos<a[pos]){
        kt=false;
        return;
    }
    if(num-a[pos]!=1){
        fin+=a[pos];
    }
    num=a[pos];
    //cout << fin << " " << num << endl;
    return;
}

int main(){
    //freopen("inp.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d",&n);
    for(long long i=0;i<n;i++){
        long long inp;
        scanf("%lld",&inp);
        a.push_back(inp);
    }
    res.assign(n,0);
    num=0;
    for(long long i=n-1;i>=0;i--){
        run(i);
        if(kt==0){
            printf("-1");return 0;
        }
    }
    printf("%lld",fin);
    return 0;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll s[51],p[51];
ll f(ll N,ll X){
	if(N==0&&X==1)return 1;
	else if(X==1)return 0;
	if(1<X&&X<=1+s[N-1])return f(N-1,X-1);
	else if(X==2+s[N-1])return p[N-1]+1;
	else if(2+s[N-1]<X && X<=2+2*s[N-1]) return p[N-1]+1+f(N-1,X-2-s[N-1]);
	else if(X==3+2*s[N-1])return 2*p[N-1]+1;
}
int main(void){
	ll N,X;
	cin >> N >> X;
	ll ans = 0;
	s[0] = 1;
	p[0] = 1;
	for(int i=1;i<=N;i++){
		s[i] = 2*s[i-1]+3;
		p[i] = 2*p[i-1]+1;
	}
	ans = f(N,X);
	cout << ans << endl;
}	

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

#define rep(i,a,n) for (int i = a;i<=n;++i)
#define per(i,a,n) for (int i = n;i>=a;--i)
#define all(x) (x).begin(), (x).end()     
#define SZ(x) ((int)x.size())

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

mt19937 mrand(random_device{}());
ll rnd(ll a, ll b) { return a + mrand() % (b - a + 1); }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

const int N = 2e5 + 100;
vi g[N];
vl s[N];
int color[N], dp[N], cnt[N];
ll ans[N];
ll n;
map<int, int> per[N];

void merge(int i, int j) {
      if (per[i].size() < per[j].size())
            per[i].swap(per[j]);
      for (auto k : per[j]) {
            per[i][k.first] += k.second;
      }
      per[j].clear();
}

void dfs(int u, int p) {
      dp[u] = 1;
      for (int v : g[u]) {
            if (v == p) continue;
            dfs(v, u);
            dp[u] += dp[v];
            s[color[u]].push_back(dp[v] - per[v][color[u]]);
            merge(u, v);
      }
      per[u][color[u]] = dp[u];
}

int main() {
      ios::sync_with_stdio(false); cin.tie(0);
#ifdef arrias
      freopen("a.txt", "r", stdin);
#endif
      cin >> n;
      rep(i, 1, n) cin >> color[i], cnt[color[i]]++;
      rep(i, 1, n - 1) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
      }
      dfs(1, -1);
      rep(i, 1, n) {
            if (cnt[i] == 0) {
                  cout << 0 << "\n";
                  continue;
            }
            ans[i] = n * (n - 1) / 2 + n;
            ll sum = accumulate(all(s[i]), 0ll);
            if (sum + cnt[i] != n) {
                  s[i].push_back(n - cnt[i] - sum);
            }
            for (auto j : s[i]) {
                  ans[i] -= ((j * (j - 1) / 2) + j);
            }
            cout << ans[i] << "\n";
      }
      return 0;
}

Measured memory_bytes: 72448
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func main() {
	buf := make([]byte, 1024*1024)
	sc.Buffer(buf, bufio.MaxScanTokenSize)
	sc.Split(bufio.ScanWords)

	n := nextInt()
	b := make([]int, n-1)
	for i := 0; i < n-1; i++ {
		b[i] = nextInt()
	}

	fmt.Println(solve(n, b))
}

func solve(n int, b []int) int {
	s := b[0] + b[n-2]

	for i := 0; i < n-2; i++ {
		s += min(b[i], b[i+1])
	}

	return s
}


Measured memory_bytes: 1812
S = input()
N = len(S)
ans = 0
for i in range(2**(N-1)):
    stack = []
    for j in range(N-1):
        if (i>>j) & 1:
            stack.append("+")
        else:
            stack.append("*")
    
    tmp = 0
    num = S[0]
    for i in range(N-1):
        st = stack.pop()
        if st == "+":
            tmp += int(num)
            num = ""
        num += S[i+1]

    tmp += int(num)
    ans += tmp


print(ans)

Measured memory_bytes: 71092
#include<bits/stdc++.h>
using namespace std;
char s[110];

int main()
{
    int n,pos,maxn;
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;++i){
        if(s[i]=='I'){
            pos++;
        } 
        else pos--;
        maxn=max(maxn,pos);
    }
    printf("%d\n",maxn);
    return 0;
}

Measured memory_bytes: 256
n,a=map(int,input().split())
x=list(map(int,input().split()))

dp=[[[0]*(n*50+1) for i in range(n+1)] for i in range(n)]
#dp[i][j][k]=i番目まででj枚のカードを選んだ時の合計がkになる組み合わせ
dp[0][0][0]=1
dp[0][1][x[0]]=1
for i in range(1,n):
    for j in range(n+1):
        for k in range(n*50+1):
            if dp[i-1][j][k]==0:continue
            #入れるとき
            dp[i][j+1][k+x[i]]+=dp[i-1][j][k]
            #入れない時
            dp[i][j][k]+=dp[i-1][j][k]

ans=0
for j in range(1,n+1):
    for k in range(n*50+1):
        if a*j==k:
            ans+=dp[-1][j][k]
print(ans)
#print(*dp[-1],sep='\n')

Measured memory_bytes: 91484
#include<bits/stdc++.h>
using namespace std;
/*int gcdf(int i,int j)
{

    int k,gcd;
    for(k=1; k<=i&&k<=j; k++)
    {
        if(i%k==0 && j%k==0)
            gcd = k;
    }
    return gcd;

}*/
int gcdf(int a, int b)
{
    if (a == 0)
        return b;
    return gcdf(b % a, a);
}
int main()
{

    int n,i,j,k,x,c=0;
        cin>>n;
        int g=0;
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                for(k=1;k<=n;k++){

                    x=gcdf(i,gcdf(j,k));

                    g=g+x;

                }
            }
        }
        printf("%d\n",g);

}




Measured memory_bytes: 3760
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
	ll n,d,x,y,c=0;
	cin>>n>>d;
	for(ll i=0;i<n;i++)
	{
		cin>>x>>y;
		if(sqrt(x*x+y*y)<=d)
		c++;
	}
	cout<<c;
}

Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll gcd(ll x, ll y) {
    if(y == 0) {
        return x;
    }
    return gcd(y, x%y);
}

ll lcm1(ll x, ll y) {
    return x/gcd(x, y)*y;
}

ll LCM(vl &v) {  // vの全要素のlcm
    ll res = 1;
    rep(i, v.size()) {
        res = lcm1(res, v[i]);
    }
    return res;
}
 
int main() {
    ll n, m;
    cin >> n >> m;

    vl a(n);
    rep(i, n) {
        cin >> a[i];
        a[i] /= 2;
    }

    ll lcm = LCM(a);
    rep(i, n) {
        if((lcm/a[i])%2 == 0) {
            out(0);
            re0;
        }
    }

    ll ans = m/(2*lcm);
    if(m%(2*lcm) >= lcm) {
        ans++;
    }
    
    out(ans);
    re0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);

		int N=sc.nextInt();
		int A=sc.nextInt()-1;
		int B=sc.nextInt()-1;
		int C=sc.nextInt()-1;
		int D=sc.nextInt()-1;
		String str=sc.next();

		sc.close();

		boolean flag=true;

		for(int i=A;i<Math.max(C, D)-1;i++){
			if(str.charAt(i)=='#' && str.charAt(i+1)=='#'){
				flag=false;
				break;
			}
		}

		if(C>D && flag){

			int cnt=0;
			for(int i=B-1;i<D;i++){
				if(str.charAt(i)=='.' && str.charAt(i+1)=='.' && str.charAt(i+2)=='.'){
					cnt++;
				}
			}

			if(cnt==0) flag=false;


		}


		if(flag) System.out.println("Yes");
		else System.out.println("No");

	}

}


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

using namespace std;

bool isPrime(int x) {
	int v = sqrt(x);
	for (int i = 2; i <= v; i++) {
		if (x % i == 0) return 0;
	}
	return 1;
}

int main() {
	int x;
	scanf("%d", &x);
	
	for (int i = x; ; i++) {
		if (isPrime(i)) return 0 * printf("%d\n", i);
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int N;
    cin >> N;
    rep(i, N) {
        cout << "ACL";
    }
    cout << '\n';
    return 0;
    // ll, 0, -, 1i, for s&g, debug
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
typedef pair<pair<int, int>, int> ppi;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef bitset<60> Bitset;
const ll INFL = 1LL << 60;
const int INF = 1000000005;
const int MAX = 300000;
const int MOD = 1000000007;
struct Graph{int to,coin; ll cost;};
struct Edge{int from,to,coin; ll cost;};
ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
//------------------------------------------------------------------------------------------------------------------------------

int main(void) {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;
    vi a(n),b(n),c(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    for(int i = 0; i < n; i++) cin>>b[i];
    for(int i = 0; i < n; i++) cin>>c[i];
    sort(a.begin(),a.end());sort(c.begin(),c.end());
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ll ta = lower_bound(a.begin(),a.end(),b[i]) - a.begin();
        ll tc = upper_bound(c.begin(),c.end(),b[i]) - c.begin();
        tc = n - tc;
        ans += ta * tc;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 4516
n = int(input())

li = [input() for _ in range(n)]
set_li = set(li)
flag = 'Yes'

if len(li) == len(set_li):
    for i in range(n):
        li[i] = list(li[i])
    for i in range(n-1):
        if li[i][len(li[i])-1] != li[i+1][0]:
            flag = 'No'
            break
else:
    flag = 'No'

print(flag)


Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;

const long long MOD = 1000000007;

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

	int n, k;
	cin >> n >> k;
	ll* h;
	h = new ll[n];
	rep(i, n) cin >> h[i];
	sort(h, h + n);

	ll ans = 0;
	rep(i, n - k) {
		ans += h[i];
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 1792
K = gets.chomp.to_i

q = (1..9).to_a

x = nil

K.times do
  x = q.shift
  b = 10 * x + x % 10
  q.push(b - 1) if x % 10 != 0
  q.push(b)
  q.push(b + 1) if x % 10 != 9
end

puts x

Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pf push_front
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


int main()
{
    fast
    ll n;
    cin>>n;
    ll arr[n],i;
    for(i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    ll dp[n+1];
    dp[0]=0;
    dp[1]=abs(arr[0]-arr[1]);
    for(i=2;i<=n;i++)
    {
        dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]) , dp[i-2]+abs(arr[i]-arr[i-2]));
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1792
// Har Har Mahadev
#include <bits/stdc++.h>
#define debug(x) cout << #x << " -> " << x << endl
#define booga cout << "booga" << endl
#define ll long long int
#define pb push_back

using namespace std;
int n,a[85];

void testcase(){
	
	cin >> n;
	for(int i{0};i < n;i++){
		cin >> a[i];
	}
	ll mon = 1000;
	for(int i{0};i < n-1;i++){
		if(a[i] < a[i+1]){
			mon += (ll)(a[i+1] - a[i]) * (ll)(mon / a[i]);
		}
	}
	cout << mon;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--){
		testcase();
	}
	return 0;
}


Measured memory_bytes: 3560
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

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

vl X(200000,0);
vector<pair<pair<char,ll>,pair<ll,ll>>> ans;

void add(ll a,ll b,ll p){
    X[p]=X[a]+X[b];
    ans.pb({{'+',a},{b,p}});
    return;
}

void cmp(ll a,ll b,ll p){
    ans.pb({{'<',a},{b,p}});
    if(X[a]<X[b]){
        X[p]=1;
    }
    else{
        X[p]=0;
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    add(0,1,3);
    cmp(2,3,3);
    rep(i,30){
        add(3+i,3+i,4+i);
    }
    rep(i,29){
        add(3+i,199999-i,199998-i);
    }
    rep(i,30){
        add(199940+i,199970+i,199940+i);
    }
    rep(i,30){//nowと比較したい
        cmp(199970+i,0,100+i);
        cmp(199970+i,0,1000+i);
        //cout << X[199970+i] << ' ' << X[0] << ' ' << X[100+i] << endl;
        rep(j,29-i){
            add(1000+i,1000+i,1000+i);
        }
        rep(j,30){
            add(1000+i,199970+j,199970+j);
        }
    }
    //cout << X[199969] << endl;
    rep(i,30){
        cmp(199940+i,1,200+i);
        cmp(199940+i,1,2000+i);
        //cout << 199940+i << ' ' << X[199940+i] << ' ' << X[1] << ' ' << X[200+i] << endl;
        rep(j,29-i){
            add(2000+i,2000+i,2000+i);
        }
        rep(j,30){
            add(2000+i,199940+j,199940+j);
        }
    }
    rep(i,30){
        rep(j,30){
            add(100+i,200+j,1000+30*i+j);
        }
    }
    rep(i,30){
        rep(j,30){
            cmp(3,1000+30*i+j,2000+30*i+j);
        }
    }
    rep(i,30){
        rep(j,30){
            rep(k,58-(i+j)){
                add(2000+30*i+j,2000+30*i+j,2000+30*i+j);
            }
        }
    }
    rep(i,900){
        add(2,2000+i,2);
    }
    //cout << X[2] << endl;
    cout << ans.size() << endl;
    rep(i,ans.size()){
        cout << ans[i].first.first << ' ' << ans[i].first.second << ' ' << ans[i].second.first << ' ' << ans[i].second.second << endl;
    }
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 5712
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, m; scanf("%d%d", &n, &m);
	std::vector<int> a(m), b(m);
	std::vector<std::vector<std::pair<int, int>>> g(n);
	std::map<std::pair<int, int>, int> mp;
	for(int i = 0; i < m; i++) {
		scanf("%d%d", &a[i], &b[i]);
		a[i]--; b[i]--;
		
		g[a[i]].push_back({b[i], i});
		g[b[i]].push_back({a[i], i});
		mp[{a[i], b[i]}] = mp[{b[i], a[i]}] = i;
	}
	
	if(m % 2) {
		printf("-1\n");
		return 0;
	}
	
	std::vector<bool> latte(m, false);
	std::vector<bool> used(n, false);
	std::vector<std::pair<int, int>> edges;
	std::function<int (int, int)> solve = [&](int v, int par) {
		used[v] = true;
		
		std::vector<int> vec;
		for(auto e: g[v]) {
			if(e.first == par or latte[e.second]) continue;
			if(used[e.first]) {
				vec.push_back(e.second);
				continue;
			}
			
			if(solve(e.first, v)) vec.push_back(e.second);
		}
		
		if(vec.size() == 0) return 1;
		if(vec.size() % 2) {
			vec.push_back(mp[{v, par}]);
			for(auto p: vec) {
				int x = a[p], y = b[p];
				if(x == v) edges.push_back({x, y});
				else edges.push_back({y, x});
				latte[p] = true;
			}
			return 0;
		} else {
			for(auto p: vec) {
				int x = a[p], y = b[p];
				if(x == v) edges.push_back({x, y});
				else edges.push_back({y, x});
				latte[p] = true;
			}	
			return 1;
		}
	};
	solve(0, -1);
	
	for(auto v: edges) printf("%d %d\n", v.first + 1, v.second + 1);
	return 0;
}


Measured memory_bytes: 36724
/* Author: Rennan Rocha
 * Time: $%Y%$-$%M%$-$%D%$ $%h%$:$%m%$:$%s%$
**/

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

#define F first
#define S second
#define PB push_back
#define MP make_pair

#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define pll pair<ll, ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define INF 1000000000000000000

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//*find_by_order(); order_of_key();

int n, wm;

ll dp[110][100010];
ll wt[110];
ll va[110];

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> wm;
    for(int i = 0; i <= 100; i++)
        for(int j = 0; j <= 100000; j++) dp[i][j] = INF;
    for(int i = 0; i < n; i++) {
        cin >> wt[i] >> va[i];
    }
    dp[0][0] = 0;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= 100000; j++) {
            if(dp[i][j] == INF) continue;
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
            dp[i+1][j+va[i]] = min(dp[i+1][j+va[i]], dp[i][j]+wt[i]);
        }
    }

    ll ans = 0;
    for(int i = 1; i <= 100000; i++) {
        if(dp[n][i] <= wm) ans = i;
    }
    cout << ans << "\n";
}


Measured memory_bytes: 80128
a, b, c = map(int, input().split())

tmp_list = []
i = 1
while True:
    tmp = a * i % b
    if tmp == c:
        print("YES")
        exit()
    else:
        if tmp in tmp_list:
            print("NO")
            exit()
        tmp_list.append(tmp)
        i += 1

Measured memory_bytes: 2940
#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int H;
	int N;
	
  	scanf("%d%d\n", &H, &N);
    
    int A[N];
    int sum = 0;
  	for(int i = 0; i < N; i++) {
    	scanf("%d", &A[i]);
      	sum += A[i];
    }
  
  	if(sum >= H) {
      printf("Yes");
    } else {
      printf("No");
    }
  	return 0;
}

Measured memory_bytes: 512
/*I wanna be the very best, like no one ever was...*/

#include<bits/stdc++.h>
using namespace std;
/*******  All Required define Pre-Processors and Constants    *******/

#define ll long long
#define ull unsigned long long 
#define ld long double
#define mem(a, b) memset(a, (b), sizeof(a))
#define rep(i, j, k) for (int i = j ; i < k ; ++i)
#define rrep(i, j, k) for (int i = j; i > k; --i)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define foreach(i, a) for(auto i: a)
#define forEach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define in(A, B, C) assert( B <= A && A <= C)
#define debug(a) cout << #a << ": " << a << endl
#define Flag(n) cout << "here " << n << endl
#define mp make_pair
#define pb push_back

#define endl '\n';
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll POSITIVE_INFINITY = 9223372036854775807;
const ll NEGATIVE_INFINITY = -9223372036854775807;
const ll MOD = 1000000007;
const ld PI = acos(-1.0);
 

#define TRACE
#ifdef TRACE
#define see(...) __f(#__VA_ARGS__,__VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr<<name<<" : "<<arg1<<endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma=strchr(names+1,',');cerr.write(names,comma-names)<<" : "<<arg1<<" | ";__f(comma+1, args...);
}
#else
#endif


int pow(int a , int n ){
    ll res =1;
    while(n){
        if(n%2==1){
            res= (res*a)%MOD;
        }
        a=((a%MOD)*(a%MOD))%MOD;
        n/=2;
    }
    return res;
}



int main() {
    io;
    // freopen("in","r",stdin); 
    // freopen("out","w",stdout);
    int n;
    cin>>n;
    vector<int> v(n);
    rep(i,0,n)cin>>v[i];
    int flag = 1;
    sort(all(v));
    if(n%2==0){
        int start = 1;
        for(int i =0;i<n;i+=2){
            if(v[i]==start && v[i+1]==start){
                start+=2;

            }
            else {
                flag = 0;
                break;
            }

        }
        if(flag){
            // see(n/2);
            // cout<<pow(3,9);
            cout<<pow(2,n/2)<<endl;
            return 0;
        }
        else {
            cout<<0<<endl;
            return 0;
        }
    }
    else {
        // see("fasdfa");
        int start = 0;
        if(v[0]!=start){
            flag = 0;
        }
        start+=2; 

       for(int i =1;i<n;i+=2){
        

            if(v[i]==start && v[i+1]==start){
                start+=2;
            }
            else{
                // see(v[i]);
                flag = 0;
                break;
            }
        }

        if(flag){
            
            cout<<pow(2,(n-1)/2)<<endl;
            return 0;
        }
        else {
            cout<<0<<endl;
            return 0;
        }



    }

 
 
 
    
 
    return 0;
}


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

int main() {
  int N;
  cin>>N;
  bool a=false;
  for(int i=1;i<10;i++){
    for(int j=1;j<10;j++){
      if(N==i*j) a=true;
    }
  }
  if(a) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


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


#define li			long long int
#define rep(i,to)	for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)	for(li i=(li)(start);i<((li)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())
#define bgn(v)		((v).begin())
#define eend(v)		((v).end())
#define allof(v)	(v).begin(), (v).end()
#define dodp(v,n)		memset(v,(li)n,sizeof(v))
#define bit(n)		(1ll<<(li)(n))
#define mp(a,b)		make_pair(a,b)
#define rin	rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)		idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)		idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)		idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)	for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)		idp p2((x).F, (x).S)
#define dump(x,n)	idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)	idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)	idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)	idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)	rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)	rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

bool board[111][111];

int main() {
	string s;
	cin>>s;
	li res=0;
	rep(i,sz(s)-1){
		if(s[i]!=s[i+1])res++;
	}
	cout<<res<<endl;


	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 123;
const ll LINF = (ll) 1e18 + 123;
const ld EPS = (ld) 1e-12;
const ll MOD = (ll) 1e9 + 7;

#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; i++)
#define per(i, f, t) for (auto i = f; i >= t; i--)

ll power(ll x, ll y, ll mod = MOD) {
    if (y == 0) {
        return 1;
    }
    if (y & 1) {
        return power(x, y - 1, mod) * x % mod;
    } else {
        ll tmp = power(x, y / 2, mod);
        return tmp * tmp % mod;
    }
}

void add(ll &x, ll y, ll mod = MOD) {
    x += y;
    if (x >= mod) x -= mod;
    if (x < 0) x += mod;
}

ll sum(ll x, ll y, ll mod = MOD) {
    add(x, y, mod);
    return x;
}

ll mult(ll x, ll y, ll mod = MOD) {
    return (x * y) % mod;
}

ll div(ll x, ll y, ll mod) {
    return x * power(y, mod - 2, mod);
}

template<typename A, typename B> bool mini(A &x, const B &y) {
    if (y < x) {
        x = y;
        return true;
    }
    return false;
}

template<typename A, typename B> bool maxi(A &x, const B &y) {
    if (y > x) {
        x = y;
        return true;
    }
    return false;
}

template<typename T> void read(T first, T last) {
    while (first != last) {
        cin >> *(first++);
    }
}

template<typename T> void print(T first, T last) {
    while (first != last) {
        cout << *(first++) << " ";
    }
    cout << "\n";
}

void run();

#define TASK ""

int main() {
#ifdef LOCAL
    if (strlen(TASK) > 0) {
        cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
    }
#endif
#ifndef LOCAL
    if (strlen(TASK)) {
        freopen(TASK ".in", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    cout << fixed << setprecision(12);
    run();
    return 0;
}

// == SOLUTION == //

const int N = (int) 1e5 + 123;

int n;
int a[N];
int cnt[3];

void run() {
    cin >> n;
    
    rep(i, 0, n) {
        cin >> a[i];
        if (a[i] % 4 == 0) {
            a[i] = 2;
        } else if (a[i] % 2 == 0) {
            a[i] = 1;
        } else {
            a[i] = 0;
        }
        cnt[a[i]]++;
    }
    
    if (((cnt[0] <= cnt[2] + 1) && (cnt[1] == 0)) || (cnt[0] <= cnt[2])) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
}


Measured memory_bytes: 640
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <complex>
using namespace std;


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

	int b_keta = floor(log10(b) + 1); // bの桁

	int sum = a * pow(10, b_keta) + b;

	int root = (int)sqrt(sum);

	if (pow(root, 2) == sum)	cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

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

const int N_MAX = 100;
const int W_MAX = 10000;

int N;
int W;

int *value;
int *weight;

int dp[N_MAX + 1][W_MAX + 1];

int rec(int index,int maxWeight)
{
    if(dp[index][maxWeight] != -1)
    {
        return dp[index][maxWeight];
    }
    int res;
    if(index==N)
    {
        res = 0;
    }
    else if (maxWeight < weight[index]){
        res = rec(index + 1,maxWeight);
    }
    else
    {
        res = max(
            rec(index + 1,maxWeight),
            rec(index + 1,maxWeight - weight[index]) + value[index]
        );
    }
    dp[index][maxWeight] = res;


    return res;
}

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

    for(int i = 0;i < N_MAX + 1;i++)
    {
        for(int j = 0;j < W_MAX + 1;j++)
        {
            dp[i][j] = -1;
        }
    }

    value = new int[N];
    weight = new int[N];

    for(int i = 0;i < N;i++)
    {
        cin >> value[i];
        cin >> weight[i];
    }

    cout << rec(0,W) << '\n';


}

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

void solve(long long N, long long W, std::vector<long long> w, std::vector<long long> v)
{
    vector<vec> dp(N + 1, vec(W + 1, -1e+18));
    dp[0][0] = 0;
    for (ll i = 0; i < N; i++)
    {
        for (ll j = 0; j <= W; j++)
        {

            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if (j + w[i] <= W)
                dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);
        }
    }
    ll ans = 0;
    for (ll i = 0; i <= W; i++)
    {
        ans = max(ans, dp[N][i]);
    }
    cout << ans << endl;
}

signed main()
{
    long long N;
    scanf("%lld", &N);
    long long W;
    scanf("%lld", &W);
    std::vector<long long> w(N);
    std::vector<long long> v(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &w[i]);
        scanf("%lld", &v[i]);
    }
    solve(N, W, std::move(w), std::move(v));
    return 0;
}


Measured memory_bytes: 83148
a = input()
if a == 'RRR':
    print("3")
elif a == 'RRS' or a == 'SRR':
    print("2")
elif a == 'RSS' or a == 'RSR' or a == 'SSR' or a == 'SRS':
    print("1")
else :
    print("0")


Measured memory_bytes: 9000
#include<iostream>
#include<stdio.h>
#include<string>

using namespace std;

int main(){
  string s;
  cin>>s;
  string::size_type idx=s.find('B');
  while(idx!=string::npos){
    if(idx==0)s.erase(s.begin()+idx);
   else s.erase(idx-1,2);
    if(idx==0)idx=s.find('B',idx);
    else idx=s.find('B',idx-1);
  }
  cout<<s<<endl;
  
  return 0;
  
}


Measured memory_bytes: 256
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = 1 / (4 * m) * sum(a)
ans = []
for i in a:
  if i >= b:
    ans.append(ans)
if len(ans) >= m:
  print('Yes')
else:
  print('No')

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

void Nor(int* di){
    int j;
    j=di[0];
    di[0]=di[1];
    di[1]=di[5];
    di[5]=di[4];
    di[4]=j;
}
void Eas(int* di){
    int j;
    j=di[0];
    di[0]=di[3];
    di[3]=di[5];
    di[5]=di[2];
    di[2]=j;
}

void Rol(int* di){
    int j;
    j=di[1];
    di[1]=di[3];
    di[3]=di[4];
    di[4]=di[2];
    di[2]=j;
}

int main(){
    int di[6]={};
    int n,i,a,b,k;
    for(i=0;i<6;i++){
        cin>>di[i];
    }
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a>>b;
        k=0;
        while(true){
            if(di[0]==a)break;
            if(k==4){
                Rol(di);
            } 
            Nor(di);
            k+=1;
        }
        while(true){
            Rol(di);
            if(di[1]==b)break;
        }
        cout<<di[2]<<endl;
    }
    return 0;
}



Measured memory_bytes: 3056
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] nl = scanner.nextLine().split(" ", 2);
        int n = Integer.parseInt(nl[0]);
        int l = Integer.parseInt(nl[1]);

        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextLine();
        }
        Arrays.sort(arr);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i]);
        }
        System.out.print("\n");
    }
}


Measured memory_bytes: 22996
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007
#define MAXN 205
#define MAXH 20
#define MAXM 52
#define INF 1LL << 30
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
const int N = 1000005;
ll dp[N][2];

ll sqr(ll x, ll mod){
	return (x*x) % mod;
}

ll mod_pow(ll x,ll p,ll mod){
	if(p == 0)return 1;
	return ((p&1?x:1LL) * sqr(mod_pow(x,p/2,mod), mod)) % mod;
}

ll inv(ll x){
	return mod_pow(x, MOD - 2, MOD);
}

ll mul(ll x,ll y){
	return x * y % MOD;
}

ll add(ll x, ll y){
	ll sum = x + y;
	if(sum >= MOD)sum-=MOD;
	return sum;
}

int main(){
	fast_io();
	int n;
	cin >> n;
	dp[1][1] = 1;
	dp[1][0] = n - 1;
	ll rsum = n - 1;
	ll inverse = inv(n - 1);
	fu(i,2,n){
		dp[i][0] = mul((n - 1), dp[i - 1][1]);
		dp[i][1] = add(mul(rsum - dp[i-1][0] + MOD, inverse), dp[i-1][1]);
		rsum = add(dp[i][0], rsum);
	}
	ll ans = add(dp[n][1], dp[n][0]);
	fu(i,1,n - 1)ans = add(ans, mul(n - 1, dp[i][0]));
	fu(i,1,n - 1)ans = add(ans, mul(mul(inverse, i), dp[i][0]));
	cout << ans << '\n';
}


Measured memory_bytes: 15872
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		List<Integer> list = new ArrayList<>();
		list.add(1);
		for (int i = 2; i <= 31; i++) {
			for (int j = 2; j <= 9; j++) {
				if (Math.pow(i, j) <= 1000) {
					list.add((int) Math.pow(i, j));
				} else break;
			}
		}
		List<Integer> hashlist = new ArrayList<>(new HashSet<>(list));
		Collections.sort(hashlist);
		for (int i = 0; i < hashlist.size(); i++) {
			if (x == 1000) {
				System.out.println(1000); return;
			}
			if (hashlist.get(i) > x) {
				System.out.println(hashlist.get(i-1)); return;
			}
		}
	}
}

Measured memory_bytes: 21716
#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
#include<cmath>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int k[3][100001];
	int dp[3][100001]={};
	for(int i=0;i<n;i++)
	{
		cin>>k[0][i+1]>>k[1][i+1]>>k[2][i+1];
	}
	for(int i=0;i<n;i++)
	{
		dp[0][i+1]=max(dp[1][i],dp[2][i])+k[0][i+1];
		dp[1][i+1]=max(dp[0][i],dp[2][i])+k[1][i+1];
		dp[2][i+1]=max(dp[1][i],dp[0][i])+k[2][i+1];
	}	
	cout<<max(max(dp[0][n],dp[1][n]),dp[2][n])<<endl;
	return 0;
}

Measured memory_bytes: 2560
n, m = map(int, input().split())
maxl = 0
minr = n
for i in range(m):
  l, r = map(int, input().split())
  maxl = max(maxl, l)
  minr = min(minr, r)
if maxl <= minr:
  print(minr - maxl + 1)
else:
  print(0)

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

final_count = 0
tmp_count = 0
for i in range(1, N):
    if H[i] <= H[i-1]:
        tmp_count += 1
    else:
        tmp_count = 0
    if tmp_count > final_count:
        final_count = tmp_count
print(final_count)

Measured memory_bytes: 14252
#include <algorithm>
#include <array>
#include <bitset>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

struct BoolName : numpunct<char> {
  string t, f;
  BoolName (string t = "Yes", string f = "No") : t(t), f(f) {}
  string do_truename() const {return t;}
  string do_falsename() const {return f;}
};

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
    cout.imbue(locale(cout.getloc(), new BoolName));
  }
} initializer;

template<typename T> istream& operator>>(istream &s, vector<T> &v) {
  for (T &t : v) s >> t;
  return s;
}

template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
  for (const T &t : v) s << t << endl;
  return s;
}

void set_bool_name(string t, string f) {
  cout.imbue(locale(cout.getloc(), new BoolName(t, f)));
}

int main() {
  vector<int> a{0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
  int x, y;
  cin >> x >> y;
  cout << (a[x] == a[y] ? "Yes" : "No") << endl;
}



Measured memory_bytes: 256
import math
D, G = list(map(int,input().split()))
P = [0]*D
C = [0]*D
for i in range(D):
    p,c = list(map(int,input().split()))
    P[i], C[i] = p, c

ans = float("inf")
for i in range(2**D):
    comp_list = [0]*D
    tmp_num = 0
    tmp_score = 0
    for j in range(D):
        if (i >> j) & 1:
            comp_list[j] = 1
            tmp_num += P[j]
            tmp_score += P[j]*(j+1)*100 + C[j]
    if tmp_score >= G:
        if tmp_num < ans:
            ans = tmp_num
    else:
        list_notcomp= [k for k in range(D) if comp_list[k] == 0]
        if len(list_notcomp) != 0:
            if math.ceil((G - tmp_score) / (100*(max(list_notcomp) + 1))) < P[max(list_notcomp)]:
                tmp_num += math.ceil((G - tmp_score) / (100*(max(list_notcomp) + 1)))
                if tmp_num < ans:
                    ans = tmp_num
print(ans)

Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))

a.sort()

ans = 0
tmp = 10 ** 9

for i in a:
    if tmp > abs(i - a[n - 1] / 2):
        tmp = abs(i - a[n - 1] / 2)
        ans = i

print(a[n - 1], ans)


Measured memory_bytes: 14052
n,x = gets.split(' ').map(&:to_i)
a = gets.split(' ').map(&:to_i)
count = 0
a.sort!
sum = a.inject(:+)

if sum == x
	count = n
else
	n.times do
		break if x < a[0]
	x = x - a.shift
	count+=1
	end
count = count - 1 if count == n
end

puts count

Measured memory_bytes: 3836
n = int(input())
S = [input() for _ in range(n)]
 
from collections import Counter
 
counters = [Counter(s) for s in S]
 
all = set(counters[0])
for counter in counters:
    all &= set(counter)
 
minc = {c:100 for c in all}
for c in all:
    for counter in counters:
        minc[c] = min(minc[c], counter[c])
 
print("".join(c * minc[c] for c in sorted(minc.keys())))

Measured memory_bytes: 3444
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<cmath>
#include<string>
#include<bitset>
#include <sstream>
#include<queue>
#include<set>
#define rep(i,n) for(ll i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef pair<int,ll>P;

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e6;

int main()
{
    int a,b;
    cin>>a>>b;
    if(b%a==0)cout<<a+b;else cout<<b-a;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
#define ll long long
#define pll pair<ll,ll>
// typedef tree <ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> set_t;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define vi vector<ll>
#define vvi vector<vi>
#define P_Q priority_queue<ll>
#define p_q priority_queue<ll,vi,greater<ll>>
#define pb push_back
#define popb pop_back
#define ub upper_bound
#define lb lower_bound
#define loop(i,x,y,z) for(int i=x; i<=y; i+=z)
#define loopR(i,x,y,z) for(int i=x; i>=y; i-=z)
#define all(x) begin(x), end(x)
#define allR(x) rbegin(x), rend(x)
#define sum(x) accumulate(all(x),0LL)
#define minE(x) *min_element(all(x))
#define maxE(x) *max_element(all(x))
#define watch(x) cout<<(#x)<<" is "<<x<<'\n'
#define display(v,c) for(auto x:v) cout<<x<<c;
#define setbits(x) __builtin_popcount(x)
#define ctoi(x) (int)((x)-'a')
#define endl "\n"

int main(){
	IOS
	// do magic here
	ll n,u,v,minColors=0;
	cin>>n;
	vvi adj(n+1);
	vector<pll> edges;
	loop(i,0,n-2,1){
		cin>>u>>v;
		edges.pb({u,v});
		adj[u].pb(v);
		adj[v].pb(u);
	}
	loop(i,1,n,1) minColors=max(minColors,(ll)(adj[i].size()));
	vi visited(n+1,0),colorOF(n+1,0);

	queue<ll> Q;
	Q.push(1);
	visited[1]=1;

	map<pll,int> colors;

	while(!Q.empty()){
		ll node=Q.front();
		Q.pop();
		ll clr=1;
		for(auto x:adj[node]){
			if (!visited[x]){
				Q.push(x);
				if(colorOF[node]==clr) clr++;
				colors[{node,x}]=clr;
				colors[{x,node}]=clr;
				colorOF[x] = clr++;
				visited[x]=1;
			}
		}
	}
	cout<<minColors<<endl;
	for(auto x:edges) cout<<colors[x]<<endl;
	return 0;
}


Measured memory_bytes: 22128