akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <time.h>

using namespace std;

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

int main()
{
  int n;
  cin >> n;
  vector<int> a(n), b(n), c(n);
  for (int i = 0; i < n; i++)
  {
    cin >> a[i];
    b[i] = i + a[i];
    c[i] = i - a[i];
  }
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  ll ans = 0;

  for (int num : b)
  {
    int lb = lower_bound(c.begin(), c.end(), num) - c.begin();
    int ub = upper_bound(c.begin(), c.end(), num) - c.begin();
    ans += ub - lb;
  }

  cout << ans << endl;
}


Measured memory_bytes: 5628
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
// this is game dp with 2 players and state only depends on k
// we just need to check whether a game is winna
int main()
{
  int n,k;
  cin>>n>>k;
  int dp[k+1][2],arr[n];
  for(int i=0;i<n;i++)
  cin>>arr[i];
  memset(dp,0,sizeof(dp));
  dp[0][1]=0;
  dp[0][0]=0;
  for(int i=1;i<=k;i++)
  {
      for(int t=0;t<1;t++)
      {
          for(int j=0;j<n;j++)
           {
               if(i-arr[j]>=0)
               {
                   if(!dp[i-arr[j]][(t)])
                   {
                       dp[i][t]=1;
                       break;

                   }
               }
           }
           if(dp[i][t]==0)
            {  dp[i][(t+1)]=1;
               
            }
            //cout<<i<<" "<<dp[i][0]<<" "<<dp[i][1]<<endl;
               
      }
  }
  if(dp[k][0])
  {
      cout<<"First"<<endl;
  }
  else{
      cout<<"Second"<<endl;
  }







}

Measured memory_bytes: 1024
a,b,c,d = map( int, input().split() )
def main(b,c,d):
    r1 = max(0, b - c)
    r2 = max(0, b - d)
    print(max(0,r1 - r2))
if a <= c:
    main(b, c, d)
else:
    main(d, a, b)


Measured memory_bytes: 2940
//Ashikur rahman Asif
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int a,b;
    long long int res=0;
    cin>>a>>b;
    while(a<=b)
    {
        a=a*2;
        res++;
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,K,U,L;
double cnt,V,T;
bool mp[10010];

int main(){
  cin>>N>>K>>T>>U>>V>>L;
  for(int i=0,a,A;i<N;i++){
    cin>>a;A=a;
    while(mp[a]&&(a-A)/V/T<K)a++;
    for(int j=a;j<L&&j<a+T*V;j++)cnt+=!mp[j],mp[j]=1;
  }

  printf("%.8f\n",cnt/V+(L-cnt)/U);
  return 0;
}

Measured memory_bytes: 1256
<?php
fscanf(STDIN,"%d %d %d %d %d",$a,$b,$ab,$x,$y);
$result = 0;

if(($a+$b) > 2*$ab)
{
  if($x > $y)
  {
    if($a > 2*$ab)//y枚ab購入 
    {
      $result = $y*2*$ab + ($x-$y)*2*$ab;
    }
    else
    {
      $result = $y*2*$ab + ($x-$y)*$a;
    }
  }
  else
  {
    if($b > 2*$ab)
    {
      $result = $x*2*$ab +($y-$x)*2*$ab;
    }
    else
    {
      $result = $x*2*$ab +($y-$x)*$b;
    }
  }
}
else
{
  if($x > $y)
  {
    if($a > 2*$ab)//y枚ab購入 
    {
      $result = $y*($a+$b) + ($x-$y)*2*$ab;
    }
    else
    {
      $result = $y*($a+$b) + ($x-$y)*$a;
    }
  }
  else
  {
    if($b > 2*$ab)
    {
      $result = $x*($a+$b) +($y-$x)*2*$ab;
    }
    else
    {
      $result = $x*($a+$b) +($y-$x)*$b;
    }
  }
}
echo($result);


Measured memory_bytes: 3576
#include<stdio.h>
int main(){
    int m,a,b,c,d;
    scanf("%d",&m);
    a=m/1000;
    b=m%1000/100;
    c=m%1000%100/10;
    d=m%1000%100%10;
    if(a+b+c+d==7)
      printf("%d+%d+%d+%d=7",a,b,c,d);
      else if(a-b+c+d==7)
      printf("%d-%d+%d+%d=7",a,b,c,d);
      else if(a+b-c+d==7)
      printf("%d+%d-%d+%d=7",a,b,c,d);
      else if(a+b+c-d==7)
      printf("%d+%d+%d-%d=7",a,b,c,d);
      else if(a-b-c+d==7)
      printf("%d-%d-%d+%d=7",a,b,c,d);
      else if(a+b-c-d==7)
      printf("%d+%d-%d-%d=7",a,b,c,d);
      else if(a-b+c-d==7)
      printf("%d-%d+%d-%d=7",a,b,c,d);
      else if(a-b-c-d==7)
      printf("%d-%d-%d-%d=7",a,b,c,d);
      return 0;
    }


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

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

    if(N % 2 == 1) PR(0);
    else {
        N /= 2;
        ll d = 5, cnt = 0;
        while(N / d > 0) {
            cnt += N / d;
            d *= 5;
        }
        PR(cnt);
    }

    return 0;
}

/*



*/

Measured memory_bytes: 3568
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        if(num < 1000) {
        	System.out.println("ABC");
        } else {
        	System.out.println("ABD");
        }
    }
}

Measured memory_bytes: 23764
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
#define MOD 1000000007
#define MAX(a,b) (a>b?a:b)
#define MAX3(a,b,c) MAX(a,MAX(b,c))
#define MIN(a,b) (a<b?a:b)
#define MIN3(a,b,c) MIN(a, MIN(b,c))
typedef long long lli;
int cmp(const void *a, const void *b) {
    return *(char*)a - *(char*)b;
}
int main()
{
    char s[4], a,b;
    int i, n=0,m=0;
    scanf("%s",s);
    qsort(s, 4, sizeof(char), cmp);
    if(s[0]==s[1] && s[2]==s[3] && s[0]!=s[2]) {
        printf("Yes");
    } else {
        printf("No");
    }

    return 0;
}


Measured memory_bytes: 128
#![allow(non_snake_case)]
use proconio::input;
// use std::collections::HashMap;

fn main() {
    input! {
        N: usize,
        mut As: [usize; N],
    }

    // 0-originに直す
    for i in 0..As.len() {
        As[i] -= 1;
    }

    let mut ans = 0;
    for i in 0..As.len() {
        for k in i + 1..As.len() {
            if As[i] == k && As[k] == i {
                ans += 1;
            }
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 3260
import java.util.*;
import java.io.*;
import java.math.BigInteger;
 
public class Main {
	public static void main(String[] args) {
	Scanner s = new Scanner(System.in);
	int X = s.nextInt();
	int count = 1;
	int src = X;
	while(src != 0){
		src = (src+X)%360;
		count++;
	}
	System.out.println(count);

    
  }
}

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

int main() {
  int N , num , s;
  num = 100000000000;
  cin >> N;
  for(int i=0;i<N;i++){
    s=0;
    int A;
    cin >> A;
    while(A % 2 == 0){
      s++;
      A /= 2;
    }
  	if(num > s){
      num = s;
    }
  }
  cout << num << endl;
  
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<assert.h>
#include<numeric>
#define rep(i,a,b) for(int (i)=(a);i<(b);i++)
using namespace std;

using ll = long long;

int K, S;
ll ans = 0;

int main() {
	cin >> K >> S;
	rep(i, 0, K + 1) {
		rep(j, 0, K + 1) {
			if (0 <= S-i - j && S-i - j <= K)ans++;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<functional>
#include<math.h>

using namespace std;

int main() {
	int N, x, mid;
	unsigned int long ans = 0;
	long A[200005], B[200005];

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> A[i];
		B[i] = A[i]-(i+1);

	}
	sort(B, B+N);


	if (N%2) {
		mid = B[N/2];
		for (int i = 0; i < N; i++) {
			x = B[i] - mid;
			ans += abs(x);
		}
	}
	else {
		mid = (B[N/2]+B[(N/2)-1])/2;
		for (int i = 0; i < N; i++) {
			x = B[i] - mid;
			ans += abs(x);
		}
	}
	cout << ans <<endl;

	return 0;
}

Measured memory_bytes: 3328
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val m = sc.nextInt()
    val q = sc.nextInt()
    val a = Array(q) { 0 }
    val b = Array(q) { 0 }
    val c = Array(q) { 0 }
    val d = Array(q) { 0 }
    for (i in 0 until q) {
        a[i] = sc.nextInt() - 1
        b[i] = sc.nextInt() - 1
        c[i] = sc.nextInt()
        d[i] = sc.nextInt()
    }
    var max = 0
    for (i1 in 1..m) {
        for (i2 in i1..m) {
            for (i3 in i2..m) {
                for (i4 in i3..m) {
                    for (i5 in i4..m) {
                        for (i6 in i5..m) {
                            for (i7 in i6..m) {
                                for (i8 in i7..m) {
                                    for (i9 in i8..m) {
                                        for (i10 in i9..m) {
                                            val arr = arrayOf(i1,i2,i3,i4,i5,i6,i7,i8,i9,i10)
                                            var score = 0
                                            for (i in 0 until q) {
                                                if (arr[b[i]]-arr[a[i]] == c[i]) {
                                                    score += d[i]
                                                }
                                            }
                                            max = maxOf(max, score)
                                        }

                                    }

                                }

                            }

                        }

                    }

                }

            }

        }
    }
    println(max)
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

Measured memory_bytes: 43456
//package acm.biginter;

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String args[])
    {
        Scanner cin = new Scanner(System.in);
        int n;
        n = cin.nextInt();
        BigInteger x,ans;
        ans = new BigInteger("1");
        int flag = 0;
        for(int i = 1;i <= n;i ++)
        {
            x = cin.nextBigInteger();
            if(x.compareTo(BigInteger.valueOf(0)) == 0)
            {
                ans = BigInteger.valueOf(0);
                flag = 1;
            }
            if(flag == 0) ans = ans.multiply(x);
            if(ans.compareTo(new BigInteger("1000000000000000000")) > 0) flag = 1;
        }
        if(ans.compareTo(new BigInteger("1000000000000000000")) > 0)
        {
            System.out.println("-1");
        }
        else System.out.println(ans);
    }
}


Measured memory_bytes: 59116
#include<stdio.h>
int main(){
  char a;
  int i,c[27]={0};
  while(scanf("%c",&a)!=EOF){
    if(a>=65&&a<=90){
      c[a-65]++;
    }
    if(a>=97&&a<=122){
      c[a-97]++;
    }
  }
  for(i=0;i<26;i++){
    printf("%c : %d\n",i+97,c[i]);
  }
}



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

template<typename integer>
integer __lcm(integer a, integer b) {
  return (a * b) / __gcd(a, b);
}

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

  vector<int> m(n);
  rep (i, n) cin >> m[i];

  int sum = 0;
  rep (i, n) sum += m[i];

  int ans = n;
  x -= sum;

  sort(m.begin(), m.end());
  while (x > 0) {
    x -= m[0];
    if (x >= 0) {
      ans++;
    }
    else {
      break;
    }
  }

  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<fstream>

#define MOD (1000000007)

using namespace std;

typedef long long int Int;

constexpr Int TEN(int n) { return n == 0 ? 1 : 10 * TEN(n-1); }

const int MAX_N = 100000+10;
class UF {
    private:
        int par[MAX_N];
        int rank[MAX_N];

    public:
        UF(int n) {
            for(int i = 1;i <= n;i++) {
                par[i] = i;
                rank[i] = 1;
            }
        }

        int root(int x) {
            return x == par[x] ? x : root(par[x]);
        }

        bool same(int x,int y) {
            return root(x) == root(y);
        }

        void merge(int x, int y) {
            x = root(x);
            y = root(y);
            if(x == y)
                return;

            if(rank[x] < rank[y]) {
                par[x] = y;
            } else {
                par[y] = x;
                if(rank[x] == rank[y])
                    rank[x]++;
            }
        }

        int connect(int n) {
            int sum = 0;
            for(int i = 1;i <= n;i++) {
                if(i == par[i])
                    sum++;
            }

            return sum;
        }
};

int N,M;

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

    UF uf(N);
    for(int i = 0;i < M;i++) {
        int x,y,z;
        cin>>x>>y>>z;
        uf.merge(x,y);
    }

    cout<<uf.connect(N)<<endl;

    return 0;
}


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

int main(){
  ll a;cin>>a;
  string b;cin>>b;
  
  b.erase(1,1);
  ll b_fix = stoll(b);


  cout << a * b_fix / 100 << endl;

}

Measured memory_bytes: 3636
#include<stdio.h>
#include<string.h>
int main()
{
	char a[5]={};
	while(gets(a)){
		if(strcmp(a,"MON")==0)
			printf("6\n");
		else if(strcmp(a,"TUE")==0)
			printf("5\n");
		else if(strcmp(a,"WED")==0)
			printf("4\n");
		else if(strcmp(a,"THU")==0)
			printf("3\n");
		else if(strcmp(a,"FRI")==0)
			printf("2\n");
		else if(strcmp(a,"SAT")==0)
			printf("1\n");
		else if(strcmp(a,"SUN")==0)
			printf("7\n");
	}
}

Measured memory_bytes: 128
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
const LL inf=1LL<<60;
LL n,a[200010],sum[200010],ans=inf;
LL k1,k2,p;
void solve()
{
	LL t1=max(max(sum[k1],sum[p]-sum[k1]),max(sum[k2]-sum[p],sum[n]-sum[k2]));
	LL t2=min(min(sum[k1],sum[p]-sum[k1]),min(sum[k2]-sum[p],sum[n]-sum[k2]));
	ans=min(ans,t1-t2);
}
int main()
{
	scanf("%lld",&n);
	for(LL i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(LL i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	k1=1;p=2;k2=3;
	while(k2<n-1&&abs(sum[k2]-sum[p]-(sum[n]-sum[k2]))>=abs(sum[k2+1]-sum[p]-(sum[n]-sum[k2+1]))) k2++;
	solve();
	while(p<n-2)
	{
		p++;if(k2==p) k2++;
		while(k1<p-1&&abs(sum[p]-sum[k1]-sum[k1])>=abs(sum[p]-sum[k1+1]-sum[k1+1])) k1++;
		while(k2<n-1&&abs(sum[k2]-sum[p]-(sum[n]-sum[k2]))>=abs(sum[k2+1]-sum[p]-(sum[n]-sum[k2+1]))) k2++;
		solve();
	}
	printf("%lld",ans);
}

Measured memory_bytes: 3328
import java.util.Scanner;

public class Main {
	public static Scanner sc;
	public static void main(String[] args){
		sc=new Scanner(System.in);
		while(true){
			Double n=sc.nextDouble(),hou=(double) 0,sum=(double) 0;
			if(n==0)break;
			for(int i=0;i<n;i++){
				Double s=sc.nextDouble();
				hou+=s*s;
				sum+=s;
			}
			Double kin=sum/n;
			Double a=Math.sqrt((hou/n)-kin*kin);
			System.out.println(a);
		}
	}

}

Measured memory_bytes: 39460
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <functional>
using namespace std;

typedef long long ll;

bool flag[20];

int main() {
	int n, k; cin >> n >> k;
	int d[20];
	for (int i = 0; i < n; ++i) {
		int d; cin >> d;
		flag[d] = true;
	}
	int ans = n;
	while (true) {
		bool f = true;
		int w = ans;
		while (w > 0) {
			f &= !flag[w % 10];
			w /= 10;
		}
		if (f) {
			cout << ans << endl;
			return 0;
		}
		++ans;
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>

using namespace std;
typedef long long LL;
const int LEN = 1e5 + 10;
int height[LEN];

int main() {
    int N, M;
    cin >> N >> M;
    map<int, set<int> > m;
    for (int i = 1; i <= N; i++) {
        cin >> height[i];
    }

    while (M--) {
        int posl, posr;
        cin >> posl >> posr;
        m[posl].insert(posr);
        m[posr].insert(posl);
    }
    set<int> s;
    map<int, set<int> >::iterator it = m.begin();
    for (; it != m.end(); it++) {
        set<int>::iterator it_s = it->second.begin();
        for (; it_s != it->second.end(); it_s++) {
            s.insert(*it_s);
        }
    }
    it = m.begin();
    int ans = 0;
    for (; it != m.end(); it++) {
        int flag = 1;
        set<int>::iterator it_s = it->second.begin();
        for (; it_s != it->second.end(); it_s++) {
            if (height[it->first] <= height[*it_s]) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            ans += 1;
        }
    }
    cout << ans + (N - s.size()) << endl;
    return 0;
}


Measured memory_bytes: 25520
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int N;
    cin>>N;
    double sum=0;
    for(int i=0;i<N;i++){
        double a;
        string b;
        cin>>a>>b;
        if(b=="JPY"){
            sum+=a;
        }
        else{
            sum+=a*380000;
        }
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
const int maxn=1e5+10;
using namespace std;

ll quickqow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans*=a;
		a*=a;b>>=1;
	}
	return ans;
}
ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
int main()
{
	int h,a;
	cin>>h>>a;
	if(h%a==0)
	{
		cout<<h/a<<endl;
	}
	else
	{
		cout<<h/a+1<<endl;
	 } 
	return 0;
}

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

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

  set<int> from1;
  set<int> ton;
  for (int i = 0; i < m; i++)
  {
    int a,b;
    cin >> a >> b;

    if(a==1) from1.insert(b);
    if(b==n) ton.insert(a);
  }

  for(int x:from1){
    if(ton.find(x)!=ton.end()){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 9600
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int ca=0,cb=0,cc=0;
string a,b,c;

int check(char t){
        if(ca==a.length()+1){
            puts("A");
            return 0;
        }
        if(cb==b.length()+1){
            puts("B");
            return 0;
        }
        if(cc==c.length()+1){
            puts("C");
            return 0;
        }
    if(t=='a'){
        ca++;
        check(a[ca-1]);
    }
    if(t=='b'){
        cb++;
        check(b[cb-1]);
    }
    if(t=='c'){
        cc++;
        check(c[cc-1]);
    }
    return 0;
}
int main(){
    cin >> a;
    cin >> b;
    cin >> c;
    check('a');
    return 0;
}

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

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;
typedef pair<ll,ll> pll;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=100+19;
const ll oo=1ll<<60;

set<int> E[N];
int a[N],b[N],dep[N],mx[N];
int n,x,y;
pll ans=mp(oo,oo),tmp;

void dfs(int x,int fa){
	tmp.fi=max(tmp.fi,0ll+dep[x]);
	int cnt=0;
	for (int y:E[x]) if (y!=fa){
		dep[y]=dep[x]+1;
		dfs(y,x);
		cnt++;
	}
	mx[dep[x]]=max(mx[dep[x]],cnt);
}
pll work(int x){
	tmp=mp(0,1);
	memset(mx,0,sizeof(mx));
	dep[x]=1;
	dfs(x,-1);
	For(i,1,tmp.fi) tmp.se*=mx[i];
	return tmp;
}

int main(){
	n=IN();
	For(i,1,n){
		a[i]=IN(),b[i]=IN();
		E[a[i]].insert(b[i]);
		E[b[i]].insert(a[i]);
	}
	For(i,1,n+1) ans=min(ans,work(i));
	For(i,1,n){
		E[a[i]].erase(b[i]);
		E[b[i]].erase(a[i]);
		E[a[i]].insert(n+1);
		E[b[i]].insert(n+1);
		E[n+1].insert(a[i]);
		E[n+1].insert(b[i]);
		pll tmp=work(n+1);
		ans=min(ans,mp(tmp.fi-1,tmp.se));
		E[n+1].erase(a[i]);
		E[n+1].erase(b[i]);
		E[a[i]].erase(n+1);
		E[b[i]].erase(n+1);
		E[a[i]].insert(b[i]);
		E[b[i]].insert(a[i]);
	}
	printf("%lld %lld\n",ans.fi,ans.se);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;

ll N, X, ans;
vector<ll> cnt(51);
vector<ll> pat(51);

void f(ll n, ll x) {
    if (x == 1) {
      if(n==0)ans++;
    } else if (x == 1 + cnt[n - 1] + 1) {
        ans += pat[n - 1] + 1;
    } else if (x == 1 + cnt[n - 1] + 1 + cnt[n - 1] + 1) {
        ans += pat[n];
    } else if (x <= 1 + cnt[n - 1]) {
        f(n - 1, x - 1);
    } else if (x > 1 + cnt[n - 1] + 1) {
        ans += pat[n - 1] + 1;
        f(n - 1, x - (1 + cnt[n - 1] + 1));
    }
}

int main() {
    cin >> N >> X;
    ans    = 0;
    cnt[0] = 1;
    pat[0] = 1;
    for (int i = 1; i <= 50; i++) {
        cnt[i] = 3 + cnt[i - 1] * 2;
        pat[i] = 1 + pat[i - 1] * 2;
    }
    f(N, X);
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,num,son[201010][2];
ll L,ans;
char s[101010];
ll bit(ll x){return x&(-x);}
void build_trie()
{
	int len=strlen(s+1),x=0;
	for (int i=1;i<=len;++i)
	{
		int c=s[i]-'0';
		if (!son[x][c]) ++num,son[x][c]=num;
		x=son[x][c];
	}
}
void dfs(int x,int deep)
{
	if (!son[x][0] && !son[x][1]) return;
	if (!son[x][0] || !son[x][1]) ans^=bit(L-deep);
	if (son[x][0]) dfs(son[x][0],deep+1);
	if (son[x][1]) dfs(son[x][1],deep+1);
}
int main()
{
	scanf("%d%lld",&n,&L);
	for (int i=1;i<=n;++i) scanf("%s",s+1),build_trie();
	dfs(0,0);
	if (ans) printf("Alice\n");
	else printf("Bob\n");
	return 0;
}

Measured memory_bytes: 3456
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))
 
using namespace std;
 
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;}
 
const ll INF=1e9+7;

int main(){
    ll n,W;
    cin >> n >> W;
    vector<ll> w(n);
    vector<ll> v(n);
    rep(i,n){
        cin >> w[i] >> v[i];
    }
    vector<vector<ll>> dp(n+1,vector<ll>(W+1));
    dp[0][0]=0;
    for(ll i=0;i<n;i++){
        for(ll j=0;j<=W;j++){
            if(j+w[i]<=W){
                dp[i+1][j+w[i]]=max(dp[i+1][j+w[i]],dp[i][j]+v[i]);
            }
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
        }
    }
    cout << dp[n][W] <<endl;
    return 0;
} 

Measured memory_bytes: 80256
n,m = map(int,input().split())
l=list(map(int,input().split()))
r=[True]*(n+1)
r[0]=False
d={}
for i in range(m):
    a,b=map(int,input().split())
    if l[a-1]>l[b-1]:
        r[b]=False
    if l[a-1]<l[b-1]:
        r[a]=False
    if l[a-1]==l[b-1]:
        r[a]=False
        r[b]=False
cnt=0
for i in r:
    if i:
        cnt+=1

print(cnt)

Measured memory_bytes: 86252
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long int ll;
int main(){
 ll n;
 cin >>n;
 if(n<=8) cout << n<<endl;
 else{
   ll p=9,k=9,l=18,u=0,j=10;
 while(1){
   u++;
  if(k<=n&&n<=l){
    cout << p<<endl;
    return 0;
  }
  if(u==9){
    u=0;
    k+=j;
    j*=10;
    l+=j;
    p++;
    continue;
  }
  k+=j;l+=j;p++;
 }
}
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <string>

using namespace std;

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

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

	vector<bool> views(n, true);

	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		a--;
		b--;
		if (h[a] == h[b]) {
			views[a] = false;
			views[b] = false;
		} else if (h[a] < h[b]) {
			views[a] = false;
		} else {
			views[b] = false;
		}
	}

	int ans = 0;
	for (bool b: views) {
		if (b) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3348
n = int(input())
L = list(map(int,input().split()))
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if max(L[i],L[j],L[k]) < (sum((L[i],L[j],L[k])) - max(L[i],L[j],L[k])) and L[i] != L[j] and L[j] != L[k] and L[k] != L[i]:
        ans += 1
print(ans)

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

typedef long long ll;
 
int main(int argc, char const *argv[])
{
	ll a,b,c;
	cin >> a >> b >> c;
	vector<ll> L = {a,b,c};
	ll s;
	if(a>b){
		if(b>c)
			s = b * c;
		else{
			if(a>c) s = b * c;
			else s = a * b;
		}
	}else{
		if(a>c) s = a * c;
		else{
			if(b>c) s =  a * c;
			else s = a * b;
		}
	}
	cout << s/2 << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
	public class Program
	{
		static void Main(string[] args)
		{
			int[] vs = Console.ReadLine().Split().Select(p => int.Parse(p)).ToArray();
			long r = vs[0];
			long D = vs[1];
			long x = vs[2];

			for (int i = 0; i < 10; i++) {
				x = r * x - D;
				Console.WriteLine(x);
			}
		}
	}
}


Measured memory_bytes: 13268
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
H,W=map(int,input().split())
Map=[input() for i in range(H)]
G=[[[] for i in range(W)] for i in range(H)]
for i in range(H):
  for j in range(W):
    if i>=1:
      if Map[i-1][j]!=Map[i][j]:
        G[i][j].append((i-1,j))
    if j>=1:
      if Map[i][j-1]!=Map[i][j]:
        G[i][j].append((i,j-1))
    if i<=H-2:
      if Map[i+1][j]!=Map[i][j]:
        G[i][j].append((i+1,j))
    if j<=W-2:
      if Map[i][j+1]!=Map[i][j]:
        G[i][j].append((i,j+1))
Visited=[[False]*W for i in range(H)]
def dfs(x,y):
  w,b=0,0
  if Visited[x][y]:
    return (0,0)
  Visited[x][y]=True
  if Map[x][y]==".":
    w+=1
  else:
    b+=1
  for p,q in G[x][y]:
    if not Visited[p][q]:
      w_,b_=dfs(p,q)
      w+=w_
      b+=b_
  return (w,b)
ans=0
for i in range(H):
  for j in range(W):
    p,q=dfs(i,j)
    ans+=p*q
print(ans)

  

Measured memory_bytes: 235608
n=int(input())
a=n
for i in range(n+1):
  x=i;y=n-i;c=0
  while x>=6:
    c+=x%6
    x=x//6
  c+=x
  while y>=9:
    c+=y%9
    y=y//9
  c+=y
  a=min(a,c)
print(a)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int n;
 	cin >> n;
 	int ans=1;
 	if(n==3){
 		cout << 9 << endl;
 		return 0;
 	}
 	if(n<3){
 		cout << 4 << endl;
 		return 0;
 	}
 	for (int i = 0; i < 10000000; i++){
 		if(n%2==0){
 			if(n==4){
 				cout << ans+3 << endl;
 				return 0;
 			}
 			n=n/2;
 			ans++;
 		}else{
 			n=n*3+1;
 			ans++;
 		}
 	}
 }

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using p = pair<ll, ll>;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
using Graph = VV;
int Inf = (1 << 30);
ll inf = (1LL << 60);
const int MOD = 1e9 + 7;
ll calc(ll a, ll x) {
	return (a / x) + 1;
}
int main() {
	ll a, b, x;
	cin >> a >> b >> x;
	a--;
	if (a != -1) cout << calc(b, x) - calc(a, x);
	else cout << calc(b, x);
	return 0;
}

Measured memory_bytes: 256
// AOJ 2824: Coastline
// 2017.9.23 bal4u@uu
// 2017.11.25

#include <stdio.h>

int a[100000], size;

char buf[30], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

int main()
{
	int t, d, l, x, i, ans;

	while (fgets(p=buf, 30, stdin) && *p != '0') {
		t = getint(), p++, d = getint(), p++, l = getint();
		size = 0;
		for (i = 0; i < t; i++) {
			fgets(p=buf, 30, stdin);
			if (getint() >= l) a[size++] = i;
		}
		t--, ans = 0;
		for (i = 1; i < size; i++) {
			x = d;
			if (   t - a[i-1] < d) x = t - a[i-1];
			if (a[i] - a[i-1] < x) ans += a[i] - a[i-1];
			else ans += x;
		}
		if (size > 0) {
			ans += (a[size-1] + d > t) ? t - a[size-1] : d;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 2084
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>

using namespace std;
using lli = long long int;

lli N;

int main() {

	lli ans = 0;
	cin >> N;

	map<lli, lli> m;

	for (int i = 0; i < N; i++) {
		lli a;
		cin >> a;
		m[a]++;
	}

	for (auto itr = m.rbegin(); itr != m.rend(); itr++) {
		while (itr->second > 0) {
			bool update = false;
			for (int i = 35; i >= 1; i--) {
				lli target = (1LL << i) - itr->first;
				auto find_itr = m.find(target);
				if (find_itr != m.end() && find_itr->second > 0) {
					if (itr->first == find_itr->first && find_itr->second == 1) {
						continue;
					}
					itr->second--;
					find_itr->second--;
					ans++;
					update = true;
					break;
				}
			}
			if (!update)
				break;
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 12800
n=int(input())
s=input()

ecount=s.count("E")
wcount=0
mn=n
for i in range(n):
    if s[i]=="E":
        ecount-=1
        count=ecount+wcount
        if mn>count:
            mn=count
    else:
        count=ecount+wcount
        if mn>count:
            mn=count
        wcount+=1

print(mn)


Measured memory_bytes: 9696
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# template


def resolve():
    ofs = 6400
    h, w = map(int, readline().split())
    a = readlines()
    A = [list(map(int, a[i].split())) for i in range(h)]
    B = [list(map(int, a[i+h].split())) for i in range(h)]
    dp = [[0]*w for _ in range(h)]
    x = abs(A[0][0]-B[0][0])
    dp[0][0] |= ((1 << (ofs+x)) | (1 << (ofs-x)))

    from itertools import product
    for i, j in product(range(h), range(w)):
        x = abs(A[i][j]-B[i][j])
        t = 0
        if(i-1 >= 0):
            t |= dp[i-1][j]
        if(j-1 >= 0):
            t |= dp[i][j-1]
        dp[i][j] |= ((t << x) | (t >> x))

    for i, s in enumerate(bin(dp[-1][-1])[-ofs-1:]):
        if(s == '1'):
            print(i)
            return


if __name__ == "__main__":
    INF = float("inf")
    MOD = 10**9+7
    resolve()


Measured memory_bytes: 51676
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <complex>
#include <iomanip>
#include <cassert>
#include <random>


int main() {
    int n, m; std::cin >> n >> m;
    std::vector<std::vector<int>> edg(n);
    std::vector<std::vector<long long>> cost(n);
    for (int i = 0; i < m; i++) {
        int a, b, c; std::cin >> a >> b >> c;
        a--; b--;
        edg[a].push_back(b);
        edg[b].push_back(a);
        cost[a].push_back(c);
        cost[b].push_back(c);
    }
    for (int i = 1; i < n; i++) {
        edg[i].push_back(i - 1);
        cost[i].push_back(0);
    }
    std::vector<long long> dist(n, 1e18);
    dist[0] = 0;
    std::priority_queue<std::pair<long long, int>> que;
    que.emplace(0, 0);
    while (!que.empty()) {
        int pos = que.top().second;
        que.pop();

        for (int i = 0; i < (int)edg[pos].size(); i++) {
            int u = edg[pos][i];
            long long c = cost[pos][i];
            if (dist[u] <= dist[pos] + c) continue;
            dist[u] = dist[pos] + c;
            que.emplace(-dist[u], u);
        }
    }
    std::cout << (dist[n - 1] != 1e18 ? dist[n - 1] : -1) << std::endl;
    return 0;
}


Measured memory_bytes: 16256
Mod = 10**9 + 7
N,M = gets.split.map &:to_i
X = gets.split.map &:to_i
Y = gets.split.map &:to_i

def ar(xs)
  sx = [0]
  ax = 0
  (0...xs.size).each{ |i|
    sx << (sx[-1] + xs[i] + Mod) % Mod
    ax = (ax + i*xs[i] - sx[-2] + Mod) % Mod
  }
  ax
end
  
p ar(X) * ar(Y) % Mod


Measured memory_bytes: 17160
n = int(input())
odd = [[i, 0] for i in range(100000)]
even = [[i, 0] for i in range(100000)]
arr = list(map(int, input().split()))
odd_e = True
even_e = True
for i, e in enumerate(arr):
    if i % 2 == 0:
        odd[e - 1][1] += 1
        if odd_e and arr[0] != e:
            odd_e = False
    else:
        even[e - 1][1] += 1
        if even_e and arr[1] != e:
            even_e = False
odd.sort(key=lambda z: z[1])
even.sort(key=lambda z: z[1])
if odd[-1][0] == even[-1][0]:
    if odd_e or even_e:
        ans = n - even[-1][1]
    elif odd[-2][1] > even[-2][1]:
        ans = n - even[-1][1] - odd[-2][1]
    else:
        ans = n - even[-2][1] - odd[-1][1]
else:
    ans = n - odd[-1][1] - even[-1][1]
print(ans)


Measured memory_bytes: 41200
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>

#define repeat(i,n) for (long long i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i] << '\n'
#define debugArrayP(x,n) for(long long i = 0; (i) < (n); ++ (i)) cerr << #x << "[" << i << "]: " << x[i].first<< " " << x[i].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

typedef ll Weight;
struct Edge {
    int src, dst;
    Weight weight;
    Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;


bool visit(const Graph &g, int v, vector<int> &order, vector<int> &color) {
  color[v] = 1;
  for(auto e: g[v]) {
    if (color[e.dst] == 2) continue;
    if (color[e.dst] == 1) return false;
    if (!visit(g, e.dst, order, color)) return false;
  }
  order.push_back(v); color[v] = 2;
  return true;
}
bool topologicalSort(const Graph &g, vector<int> &order) {
  int n = g.size();
  vector<int> color(n);
  repeat(u, n) if (!color[u] && !visit(g, u, order, color))
    return false;
  reverse(order.begin(),order.end());
  return true;
}

int dp[112345];
int N,M;
Graph G;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>N>>M;
  G.resize(N);
  repeat(i,M){
    int x,y;cin>>x>>y;
    x--;y--;
    G[x].push_back({x,y,1});
  }
  vint order;
  topologicalSort(G,order);
  //debug(isok);
  //cerr<<"!!!!!"<<endl;
  //debug(order[1]);
  //debugArray(order,N);
  int ans = 0;
  repeat(i,N){
    ans = max(ans,dp[order[i]]);
    for(Edge e:G[order[i]]){
      dp[e.dst] = max(dp[e.dst],dp[order[i]]+1);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 9468
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<string.h>
#include<vector>
#include<queue>
#include<stack> 
#include<stdlib.h> 
#include<time.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const double eps=10-8;
const double inf=0x3f3f3f3f;
const ll mod=1000000007; 
const int maxn=1000+15;
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;};
char ch[maxn];
int clo[maxn][maxn];
int pan[maxn];
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	ll a,b,c,i,j,p;
	ll l,r,d;
	cin>>l>>r>>d;
	ll ans=0;
	for(ll i=l;i<=r;i++)
	{
		if(i%d==0) ans++;
	}
	cout<<ans<<endl;

	 return 0;
}


Measured memory_bytes: 3648
#include<iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }    
    for(int j=0;j<n;j++){
        cout<<a[n-1-j];
        if(j<n-1){
            cout<<' ';
        }
    }
    cout<<endl;
}


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

int main() {
 map<string,UL> S;
 UL Q; scanf("%u",&Q);
 rep(q,Q){
  UL c; scanf("%u",&c);
  if(c==0){
   char buf[21]; UL x; scanf("%s%u",buf,&x);
   S[buf]=x;
  }
  if(c==1){
   char buf[21]; scanf("%s",buf);
   printf("%u\n",S[buf]);
  }
 }
 return 0;
}




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

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

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, K;
  cin >> N >> K;

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

  sort(p.begin(), p.end());
  int sum = 0;
  for ( int i = 0; i < K; i++ ) {
    sum += p[i];
  }

  cout << sum << endl;
  
  return 0;
}


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

class Solution {
    public:
        int sol(){
            int n,y,k;
            cin>>n>>k;
            vector<int> a;
            vector<int> dp(n,INT_MAX);
            for(int i=0;i<n;i++){
                cin>>y;
                a.push_back(y);
            }
            dp[0] = 0;
            for(int i=1;i<n;i++){
                for(int j=i-1;j>=0&&j>=i-k;j--){
                    dp[i] = min(dp[i],dp[j]+abs(a[j]-a[i])); 
                }
            }
            return dp[n-1];
        }
};

int main(){
    Solution test;
    cout<<test.sol();
    return 0;
}

Measured memory_bytes: 1276
#include<bits/stdc++.h>
#define maxn 3001

using namespace std;
typedef long long ll;
ll dp[maxn],n,M,P,p2[maxn*maxn],C[maxn][maxn],ans,f,fc[maxn],fi[maxn];

ll pow_(ll x,ll y,ll z)
{
    ll rt=1;
    while (y){
        if (y&1) rt=rt*x%z;
        y/=2;
        x=x*x%z;
    }
    return rt;
}

int main()
{
    cin >> n >> M;
    p2[0]=1; for (int i=1;i<=n*n;i++) p2[i]=p2[i-1]*2%M;
    fc[0]=fi[0]=1; for (int i=1;i<=n;i++) fc[i]=fc[i-1]*i%M,fi[i]=pow_(fc[i],M-2,M);
    C[0][0]=1;
    for (int i=1;i<=n;i++)
    {
        C[i][0]=0;C[i][i]=1;
        for (int j=1;j<i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j]*j)%M;
    }
    dp[0]=1; f=1;
    for (int i=1;i<=n;i++)
        for (int j=0;j<=i;j++)
            (dp[i]+=(C[i][j]+C[i][j+1]*(j+1))%M*p2[(n-i)*j])%=M;
    for (int i=0;i<=n;i++)
        (ans+=dp[i]*pow_(2ll,pow_(2ll,n-i,M-1),M)%M*fc[n]%M*fi[i]%M*fi[n-i]%M*f)%=M,f=-f;
    cout << (ans+M)%M << endl;
}


Measured memory_bytes: 139392
N, T = map(int,input().split())
List = list(map(int,input().split()))
Data = [0,0]
for item in List:
  if Data[0]>=item:
    Data[1] += T + item -Data[0]
    Data[0] = item +T
  else:
    Data[1] += T
    Data[0] = item +T
print(Data[1])

Measured memory_bytes: 26708
## subroutines

def max_cs(n)
  return n if n <= 2

  sum = n

  for i in (0...n)
    li = [i, n - 1 - i].min
    sum += 3 ** li - 1
  end

  sum
end

### main

while line = gets
  n = line.strip.to_i

  p max_cs(n)
end

Measured memory_bytes: 6092
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 2e5 + 10;
int a[M];
int main(){
    int k, n;
    scanf("%d%d", &k, &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int maxn = a[1] + k - a[n];
    for(int i = 2; i <= n; i++) {
        maxn = max(maxn, a[i] - a[i - 1]);
    }
    printf("%d\n", k - maxn);
    return 0;
}


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  map<int, int> freqs;
  int val;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &val);
    ++freqs[val];
  }
  int ans = 0;
  for (pair<int, int> p : freqs) {
    ans += (p.second & 1);
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 4992
#include <iostream>
#define MAX 100000
#define ll unsigned long long
using namespace std;

int main() {
    ll n, a[MAX + 100], node[MAX + 100], res = 0;

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

    if (n == 0) {
        cout << (a[0] == 1 ? 1: -1) << endl;
        return 0;
    }

    if (a[0] != 0) {
        cout << -1 << endl;
        return 0;
    }

    node[0] = 1;
    for (ll i = 1; i <= n; ++i) {
        if (a[i] > node[i - 1] * 2) {
            cout << -1 << endl;
            return 0;
        }

        node[i] = 2 * node[i-1] - a[i];
    }
    node[n] = 0;

    for (ll i = n+1; i-- > 0; ) {
        node[i-1] = node[i] + a[i] >= node[i-1] ? node[i-1] : node[i] + a[i];
        res += node[i] + a[i];
    }

    cout << res << endl;

}

Measured memory_bytes: 5176
import heapq

N,K=list(map(int,input().split(" ")))

arr=[0]*N
for z in range(N):
  heapq.heapreplace(arr,int(input()))

arr2=[0]*K
for z in range(K):
  arr2[z]=heapq.heappop(arr)

r=arr2[-1]-arr2[0]

z=0
try:
  while True:
    arr2[z]=heapq.heappop(arr)
    if z==K-1:
      zz=0
    else:
      zz=z+1

    rb=arr2[z]-arr2[zz]
    if rb<r:
      r=rb

    z+=1
    if z==K:
      z=0

except Exception:
  pass

print(r)

Measured memory_bytes: 7796
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int m=1e9+7;
int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    fastio
    int a,b,k;
    cin>>a>>b>>k;
    for(int i=min(a,b);i>0;--i){
    	if(a%i==0 && b%i==0) --k;
    	if(k==0){
    		cout<<i;
    		break;
    	}
    }
	return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // ABC153B - Common Raccoon vs Monster

        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt();
        int n = sc.nextInt();

        int[] a = new int[n];

        int ttl = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            ttl += a[i];
        }

        System.out.println(ttl < h ? "No" : "Yes");
    }
}

Measured memory_bytes: 50732
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, K, a =1;
  cin >> N >> K;
  for (int i =0 ; i <N ; i++) {
  if (a* 2 <= a + K){
  a *= 2;
  }
  else {
  a += K;
  }
 } 
  cout << a << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ld long double
#define vpii vector<pair<int,int> >
#define X first
#define Y second
#define fr(i,a,n) for(int i=a;i<n;i++)
#define mod 1000000007
#define fi ios_base::sync_with_stdio(false);cin.tie(NULL);



int main()
{
    ll a,b,n;
    cin>>a>>b>>n;
    ll x=min(n,b-1);
    cout<<(x*a)/b;
}

Measured memory_bytes: 3624
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
su = 0
kinshi = ''
dashita = [''] * N
for i in range(len(T)):
  s = T[i]
  if i - K >= 0:
    if s == dashita[i - K]:    
      continue
  if s == 'r':
    su += P
  elif s == 's':
    su += R
  elif s == 'p':
    su += S
  dashita[i] = s
print(su)
  

Measured memory_bytes: 4084
#include <bits/stdc++.h> 
using namespace std;
#define pb push_back
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define vli vector<ll>
#define graph vector<vector< int > >
#define vpi vector<pair<int ,int> >
#define vpli vector<pair<ll ,ll> >
#define mp make_pair
#define F first
#define S second
#define mod 998244353
#define INF (ll)1e10
#define wh(a) cout<<#a<<"  is  "<<a<<endl;
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define INI(a) memset(a,0,sizeof(a))
#define LIMIT 200006

ll po(ll a,ll b){
    ll ans=1,mul=a%mod;
    while(b){
        if(b%2==1){
            ans=(ans*mul)%mod;
        }
        mul=(mul*mul)%mod;
        b=b/2;
    }
    return ans;
}

// fac o(n)
ll fac[LIMIT];
ll invfac[LIMIT];
void ini(){
    fac[0]=1;
    invfac[0]=1;
    for(ll i=1;i<LIMIT;++i){
        fac[i]=(fac[i-1]*i)%mod;
        invfac[i]=po(fac[i],mod-2);
    }
}
ll ncr(ll n,ll r){
    if(n<r)return 0;
    if(r==0) return 1;
    return (fac[n]*((invfac[n-r]*invfac[r])%mod))%mod;
}

void solve(){
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    ini();
    // wh(ncr(2,0));
    // wh(ncr(2,1));
    // wh(ncr(2,2));
    for(ll i=0;i<=k;++i){
        // wh(n);wh(i);
        // wh(ncr(n-1,i));
        ans=(ans+(ncr(n-1,i)*((m*po(m-1,n-1-i))%mod))%mod)%mod;
        // wh(ans);
    }
    cout<<ans<<endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // #endif
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 6784
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define MP(x,y) make_pair(x,y)
#define X first
#define Y second

using namespace std;
using ll= long long ;

ll pow_mod(ll a, ll b){
  ll r = 1;
  for(;b>0; b>>=1){
    if(b&1) r = (r*a) ;
    a = (a * a);
  }
  return r;
}



int main(void){
  ll n, p;
  ll g = 0,  k = 0;
  ll a;
  cin >> n >> p;
  rep(i,n){
    cin >> a;
    if(a %2 == 0){
      g++;
    }else{
      k++;
    }
  }

  ll ans;

  if(p == 0){
    ans  = pow_mod(2, g);
    ans *= pow_mod(2, k);
  }else{
    ans = pow_mod(2,k);
  }

  ll ansg = 1;
  ll ansk = 0;
  rep(i, g){
    ansg += ansg;
  }
  rep(i, k){
    ll tmpg = ansg;
    ll tmpk = ansk;
    ansg += tmpk;
    ansk += tmpg;
  }
  if(p == 0){
    cout << ansg << endl;
  }else{
    cout << ansk << endl;
  }


  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(int argc, char *argv[])
{
  string s;
  cin >> s;
  s.erase(s.end()-8, s.end());
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256