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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        int x = Integer.parseInt(input);
        char[] array = input.toCharArray();
        int sum = 0;

        for(char c: array){
            int i = Integer.parseInt(String.valueOf(c));
            sum += i;
        }

        if(x % sum == 0){
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static void printListOneLine(List list){
        for(int i=0; i<list.size(); i++){
            System.out.println(list.get(i));
        }
    }

    public static void printList(List list){
        for(int i=0; i<list.size(); i++){
            if(i == list.size()){
                System.out.println(list.get(i));
            } else {
                System.out.print(String.format("%d ", list.get(i)));
            }
        }
    }

    public static void printArray(int[] array){
        for(int i=0; i<array.length; i++){
            if(i == array.length){
                System.out.println(array[i]);
            } else {
                System.out.print(String.format("%d ", array[i]));
            }
        }
    }

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

    public static int lcm(int a, int b){
        return a * b / gcd(a, b);
    }
}


Measured memory_bytes: 21844
n = int(input())
aa = list(map(int, input().split()))
ans = 0
pos = [0] * (n + 1)

for i, a in enumerate(aa):
    pos[a] = i + 2
Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
for a in range(1,n + 1):
    i = pos[a]
    l0 = Lnext[i]
    l1 = Lnext[l0]
    r0 = Rnext[i]
    r1 = Rnext[r0]
    ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
    Lnext[r0] = l0
    Rnext[l0] = r0
print(ans)

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

#define REP(i, a, b) for (auto (i) = (a); (i) <= (b); (i)++)
#define F first
#define S second

const int N = 80;
ll a[N+5];
ii all_money[N+5];
ii all_stock[N+5];

signed main() {
	ios_base::sync_with_stdio(0);

	int n;
	cin >> n;
	REP(i, 0, n-1) {
		cin >> a[i];
	}
	all_stock[0] = {1000/a[0], 1000%a[0]};
	all_money[0] = {0, 1000};
	REP(i, 1, n-1) {
		ii new_money = {0, all_stock[i-1].F*a[i] + all_stock[i-1].S};
		all_money[i] = max(all_money[i-1], new_money);
		ii new_stock = {all_money[i-1].S/a[i], all_money[i-1].S%a[i]};
		all_stock[i] = max(all_stock[i-1], new_stock);
	}
	cout << all_money[n-1].S << '\n';
	return 0;
}

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

int main() {
  int a,b;
  cin>>a>>b;
  if(a==1&&b==2)cout<<3<<endl;
  if(a==1&&b==3)cout<<2<<endl;
  if(a==2&&b==1)cout<<3<<endl;
  if(a==2&&b==3)cout<<1<<endl;
  if(a==3&&b==1)cout<<2<<endl;
  if(a==3&&b==2)cout<<1<<endl;
}

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


int main()
{
	int a, b; cin >> a >> b;
	if (a == b)
		cout << "Draw" << endl;
	else if (a == 1 && b != 1)
		cout << "Alice" << endl;
	else if (b == 1 && a != 1)
		cout << "Bob" << endl;
	else if (a > b)
		cout << "Alice" << endl;
	else if (b > a)
		cout << "Bob" << endl;

	return 0;
}


Measured memory_bytes: 256
d = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for j in range(d)]

#t = [int(input()) for i in range(d)]

for i in range(d):
    print(1)
    
exit()

ans = []
last = [[0 for i in range(26)] for j in range(27)]
tmp_ans = [0]*26

for i in range(1,d+1):
    tmp_num = 0
    for j in range(26):
        tmp_ans[j] += s[i-1][j]
        last[j+1][j] = i
        for k in range(26):
            tmp_ans[j] -= (i-last[j+1][k])*c[k]
    idx = tmp_ans.index(max(tmp_ans))
    for j in range(26):
        for k in range(26):
            if k == idx:
                continue
            last[k][j] = last[idx][j]
    print(idx+1)
    #print(tmp_ans)
#print(ans)
    """
            
    ans += s[i-1][t[i-1]-1]
    last[t[i-1]-1] = i
    for j in range(26):
        ans -= (i-last[j])*c[j]
    print(ans)
    """
    


Measured memory_bytes: 68108
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define sz size()
#define mk make_pair
#define clr clear()
#define B begin()
#define E end()
#define EM empty()
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define all(cont) cont.begin(),cont.end()
#define pb push_back
string en="\n";
string t="hello";
#define sqr(a) ((a) * (a))
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,c=0;
     while(cin>>n>>k)
     {
         vi a;
         rep(i,n)
         {
             vp(a,x);
         }
         sort(all(a));
         s=INT_MAX; c=0;
         for(i=0;i+k<=n;i++)
         {
             c=a[i+k-1]-a[i];
             if(c<s)
                s=c;

         }
         cout<<s<<en;
     }



}




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

using ll = long long;
using ld  = long double;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-10; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

// #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
// int lcm(int a, int b){return a / gcd(a, b) * b;}
#define begin_end(a) a.begin(),a.end() //sort(begin_end(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll)(n) ; i++ )
#define DREP(i,m,n) for(ll i=(ll)(m) ; i > (ll)(n) ; i-- )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define p_b push_back
#define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに


// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// -------- template end - //


// - library ------------- //




// --------- library end - //


int main(){

  ll N, D;
  cin >> N >> D;

  D = D * D; 

  ll ans = 0;
  rep(i, N){
    ll x = il();
    ll y = il();
    if (x * x + y * y <= D) ans++;
  }

  cout << ans << endl;


}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using vi=vector<int>;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int n,ans=0,r=0,l=100000000;
    cin >> n;
    string s;
    cin >> s;
    rep(i,n){
        if(s[i]=='W') l=min(l,i);
        if(s[i]=='R') r=max(r,i); 
    }
    while(1){
        if(l>=r) break;
        s[l]='R';
        s[r]='W';
        ++ans;
        for(int i=l;l<n;++i){
            if(s[i]=='W'){
                l=i;
                break;
            }
        }
        for(int j=r;r>=0;--j){
            if(s[j]=='R'){
                r=j;
                break;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}   

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

    const int MOD = 1000000007;
    const double PI = acos(-1); 

    //long long
    using ll = long long;

    //出力系
    #define print(x) cout << x << endl
    #define yes cout << "Yes" << endl
    #define YES cout << "YES" << endl
    #define no cout << "No" << endl
    #define NO cout << "NO" << endl
    
    // begin() end()
    #define all(x) (x).begin(),(x).end()

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

    //最大公約数（ll）
    ll gcd(ll x, ll y) { return y ? gcd(y,x%y) : x;}

    //素因数分解
    vector<pair<ll, int>>factorize(ll n){
      vector<pair<ll, int>> res;
      for(ll i = 2; i * i <= n; ++i){
        if(n % i) continue;
        res.emplace_back(i, 0);
        while(n % i == 0){
          n /= i;
          res.back().second++;
        }
      }
    if(n != 1) res.emplace_back(n, 1);
    return res;
    }



  // // 二分探索(最小値を出す問題は疑う)
  // bool C(ll x){
  //     ll res = 0;
  //     for(int i = 0; i < N; ++i){
  // 		res += max(0ll, A[i]-x/F[i]);
  //     }
  //     return res <= K;
  // }

  //   ll binary_search(ll ok, ll ng){
  //     while(abs(ok - ng) > 1){
  //       ll mid = (ok + ng) / 2;
  //       if(C(mid)) ok = mid;
  //       else ng = mid;
  //     }
  //     return ok;
  //   }
    int N;
    vector<int>x(10);
    vector<int>y(10);
  double dist(int i,int j)
{
    double dx = x[i]-x[j];
    double dy = y[i]-y[j];
    
    return pow(dx*dx + dy*dy,0.5);
}

  int main(){
    
    cin >> N;

    
    double sum = 0.0;
    vector<int>vct(N);
    
    REP(i, N) {
      cin >> x.at(i) >> y.at(i);
      vct.at(i) = i;
    }
    
    do{
        REP(i, N - 1){
          sum+=dist(vct[i],vct[i+1]);
        }
      }while(next_permutation(all(vct)));
    

    int fac = 1;
    for(int i = 2; i <= N; i++) fac *= i;
    cout << fixed << setprecision(10) << sum/fac << endl;

  }

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <limits>
using ll = long long;
constexpr int INF = std::numeric_limits<int>::max() / 2;
constexpr ll LNF = std::numeric_limits<ll>::max() / 2;

using namespace std;
int main() {
    int v[3], K;
    cin >> v[0] >> v[1] >> v[2] >> K;
    sort(begin(v), end(v));
    cout << ((v[2] << K) + v[0] + v[1]) << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.math.*;
class Main{
	static int mod = (int)1e9+7;
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	public static void main(String sp[])throws IOException{
		FastReader sc = new FastReader();
		
		int n = sc.nextInt();
		int arr[] = new int[n+1];
		int bi[] = new int[n+1];
		int sat[] = new int[n];
		
		for(int i=1;i<=n;i++)
			arr[i]=sc.nextInt();
		for(int i=1;i<=n;i++)
			bi[i]=sc.nextInt();
		for(int i=1;i<n;i++)
			sat[i]=sc.nextInt();
		
		long total=0;
		int prev=0;
		for(int i=1;i<=n;i++){
			int val = arr[i];
			if(prev+1==val){
				total+=bi[i];
				total+=sat[prev];
			
			}else{
				total+=bi[i];
			}
			prev=arr[i];	
		}
		
		System.out.println(total);
		
		
		
		
		
		
		out.close();
	}
	
	
	
	
	
	//static HashMap<Integer,Integer> visited = new HashMap<>();
		
	
	/*public static int compute(int root, int n, int m, Tree[] edge, int values[]){
			
			LinkedList<Integer> ll = 	new LinkedList<>();
			ll.add(root);
				
			while(ll.size()>0){
				int val = ll.removeFirst();
				visited.put(val,0);
				ArrayList<Integer> al = edge[val].al;
				int length = al.size();
				for(int i=0;i<length;i++){
					ll.addLast(al.get(i));
					int hold = edge[val].weight+values[root];
					values[al.get(i)] = Math.min(hold,values[al.get(i)]);
				}
			}
			return values[n];
			
	}*/
	
	
	public static class Tree{
		int weight;
		int destination;
	}
	
	
	
	public static int partition(int [] arr, int s, int e){
		
		int index=s;
		int pivot = arr[e];
		for(int i=s;i<=e-1;i++){
			if(arr[i]<=pivot){
				arr = swap(arr, index, i);
				index++;
			}
		}
		swap(arr,index,e);
		print(arr);
		return index;
	}
	
	public static int[] swap(int[] arr, int low, int high){
		int temp = arr[low];
		arr[low]=arr[high];
		arr[high]=temp;
		return arr;
	}
	
	
	public static long gcd(long a, long b){
		if(a==0)
			return b;
		
		return gcd(b%a,a);
	}
	
	public static void print(int[] arr){
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	
	public static class pair{
		int ai;
		int bi;
	}
	
	public static class comp implements Comparator<pair>{
		public int compare(pair o1, pair o2){
			return o1.bi-o2.bi;
		}
	}
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
	
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
}

Measured memory_bytes: 21588
package main

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

const MOD int64 = 1000000007

func main() {
  input := Input{bufio.NewReaderSize(os.Stdin,100)}
  n,k := input.NextInts()
  tree := make([][]int,n)
  for i:=0;i<n-1;i++ {
    a,b := input.NextInts()
    tree[a-1] = append(tree[a-1],b-1)
    tree[b-1] = append(tree[b-1],a-1)
  }
  dp := make([]int64,n)
  for i:=0;i<n;i++ { dp[i] = -1 }
  var dfs func(int)
  dfs = func(v int) {
    m := 1
    for _,e := range tree[v] {
      if dp[e] >= 0 { m++ }
    }
    for _,e := range tree[v] {
      if dp[e] >= 0 { continue }
      dp[e] = int64(k-m)
      if dp[e] < 0 { dp[e] = 0 }
      m++
      dfs(e)
    }
  }
  dp[0] = int64(k)
  dfs(0)
  ans := int64(1)
  for i:=0;i<n;i++ { ans = (dp[i]*ans)%MOD }
  fmt.Println(ans)
}

type Input struct { reader *bufio.Reader }
func(i *Input) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := i.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(i *Input) NextInts() (int,int) {
  s := strings.Fields(i.NextLine())
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  return x,y
}

Measured memory_bytes: 37248
N = int(input())
A = list(map(int, input().split()))
B = [A[0]]
Bf = [1]
C = []
for i in range(1, len(A)):
  if A[i-1] != A[i]:
    B.append(A[i])
    if A[i-1] < A[i]:
      Bf.append(0)
    else:
      Bf.append(1)
f = 1
for i in range(1, len(B)):
  if Bf[i-1] == f and Bf[i] == 1 - f:
    C.append(B[i-1])
    f = 1 - f
if Bf[-1] == 0:
  C.append(B[-1])
M = 1000
for i in range(len(C)//2):
  x = M // C[2*i]
  M = M - C[2*i] * x + C[2*i+1] * x
print(M)

Measured memory_bytes: 9240
#include <bits/stdc++.h>
#define pb push_back
#define REP(i, n) for (signed long long i = 0; i < (n); i++)
#define MOD 998244353
#define INF 98765431219876543
#define bitcnt(a) (ll) __builtin_popcount((a))
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<string, string> PS;

int main() {
  ll n;
  cin >> n;
  map<P, ll> m;
  vector<ll> v;
  vector<P> v1, v2;
  REP(i, n) {
    ll a;
    cin >> a;
    v.pb(a);
    m[P(a, i % 2)]++;
  }
  ll cnt = INF, cnt2 = INF;
  v1.pb(P(n / 2, -100));
  v2.pb(P(n / 2, -111));
  for (auto &a : m) {
    if (a.first.second == 0) {
      cnt = n / 2 - a.second;
      v1.pb(P(cnt, a.first.first));
    }

    if (a.first.second == 1) {
      cnt2 = n / 2 - a.second;
      v2.pb(P(cnt2, a.first.first));
    }
  }
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  if (v1[0].second == v2[0].second) {
    cout << min(v1[0].first + v2[1].first, v1[1].first + v2[0].first) << endl;
  } else {
    cout << v1[0].first + v2[0].first << endl;
  }
}

Measured memory_bytes: 9844
R,G,B,N = map(int,input().split())
ans = 0
for r in range(int(N/R)+1):
    for g in range(int((N-r*R)/G)+1):
        if N-(r*R+g*G) >= 0 and (N-(r*R+g*G))%B == 0:
        #    print(r,g,(N-(r*R+g*G))%B)
            ans += 1
print(ans)

Measured memory_bytes: 40556
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Main implements Runnable {
	public static void main(String[] args) {
		new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		// int n = sc.nextInt();
		// int q = sc.nextInt();
		// int[] w = new int[n];
		// for (int i = 0; i < n; ++i) {
		// w[i] = sc.nextInt();
		// }
		// HLDecomposition hl = new HLDecomposition(n);
		// ArrayList<Integer>[] g = new ArrayList[n];
		// for (int i = 0; i < n; ++i) {
		// int s = sc.nextInt() - 1;
		// int e = sc.nextInt() - 1;
		// hl.ae(s, e);
		// }
		// hl.pre();
		int n = sc.nextInt();
		HLDecomposition hl = new HLDecomposition(n);
		for (int i = 0; i < n; ++i) {
			int k = sc.nextInt();
			for (int j = 0; j < k; ++j) {
				int c = sc.nextInt();
				hl.ae(i, c);
			}
		}
		hl.pre();
		int q = sc.nextInt();
		for (int i = 0; i < q; ++i) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			System.out.println(hl.lca(u, v));
		}
	}

	class HLDecomposition {
		int n;
		int[] depth;
		int[] head;
		int[] heavy;
		int[] parent;
		int[] sz;// ??¨?????¨?????§??????
		ArrayList<Integer>[] g;
		int[] id;

		@SuppressWarnings("unchecked")
		public HLDecomposition(int n) {
			this.n = n;
			depth = new int[n];
			head = new int[n];
			heavy = new int[n];
			parent = new int[n];
			id = new int[n];
			sz = new int[n];
			g = new ArrayList[n];
			for (int i = 0; i < n; ++i) {
				g[i] = new ArrayList<>();
			}
			Arrays.fill(head, -1);
			Arrays.fill(id, -1);
			Arrays.fill(parent, -1);
		}

		void ae(int a, int b) {
			g[a].add(b);
			g[b].add(a);
		}

		void pre() {
			dfs(0, -1);
			bfs();
		}

		void bfs() {
			ArrayDeque<Integer> pend = new ArrayDeque<>();
			int gen = 0;
			pend.add(0);
			while (!pend.isEmpty()) {
				int v = pend.pollFirst();
				int top = v;
				for (; v != -1; v = heavy[v]) {
					id[v] = gen++;
					head[v] = top;
					for (int d : g[v]) {
						if (d == parent[v] || d == heavy[v]) {
							continue;
						}
						pend.add(d);
					}
				}
			}
		}

		int lca(int u, int v) {
			if (head[u] != head[v]) {
				if (depth[head[u]] < depth[head[v]]) {
					int tmp = u;
					u = v;
					v = tmp;
				}
				return lca(parent[head[u]], v);
			} else {
				if (depth[u] > depth[v]) {
					int tmp = u;
					u = v;
					v = tmp;
				}
				return u;
			}
		}

		int dfs(int c, int p) {
			parent[c] = p;
			int s = 1;
			int to = -1;
			for (int d : g[c]) {
				if (d == p)
					continue;
				depth[d] = depth[c] + 1;
				s += dfs(d, c);
				if (to == -1 || sz[d] > sz[to]) {
					to = d;
				}
			}
			sz[c] = s;
			heavy[c] = to;
			return s;
		}

	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}

}

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

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

    int n;
    int a[150000],b[100001],c[100001];
    int dp[150000][3];

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

    dp[0][0] = a[0];
    dp[0][1] = b[0];
    dp[0][2] = c[0];

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

        dp[i][0] = a[i]+max(dp[i-1][1],dp[i-1][2]);
        dp[i][1] = b[i]+max(dp[i-1][2],dp[i-1][0]);
        dp[i][2] = c[i]+max(dp[i-1][0],dp[i-1][1]);
    }

    cout << max(max(dp[n-1][0] ,dp[n-1][1] ),dp[n-1][2]) << endl;

}

Measured memory_bytes: 3200
#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)


def main():
    while 1:
        s=input()
        if "0 0" in s:
            break
        else:
            a,b=map(int,s.split())
            for i in range(a):
                if i%2:
                    print("".join([".#"[j%2]for j in range(b)]))
                else:
                    print("".join(["#."[j%2]for j in range(b)]))
        print()

if __name__ == '__main__':
    main()


Measured memory_bytes: 6920
n = int(input())
a = [int(i) for i in input().split()]
ok = True
for i in a:
	if i % 2 == 0:
		if (i % 3 != 0 and i % 5 != 0):
			ok = False
			break

if ok:
	print("APPROVED")
else:
	print("DENIED")


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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

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

#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define ins insert

#define debug(a) cerr<<(a)<<endl
#define dbrep(a,n) rep(_i,n) cerr<<(a[_i])<<" "; cerr<<endl
#define dbrep2(a,n,m) rep(_i,n){rep(_j,m) cerr<<(a[_i][_j])<<" "; cerr<<endl;}

using namespace std;

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A,B> &p){return os<<"("<<p.fi<<","<<p.se<<")";}
template<class A, class B>
istream &operator>>(istream &is, pair<A,B> &p){return is>>p.fi>>p.se;}

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,Q; cin>>N>>Q;
    vll a(N);
    rep(i,N) cin>>a[i];

    vll osum(N+1),sum(N+1);
    rep(i,N) osum[i+1]=osum[i]+(i%2==0?a[i]:0);
    rep(i,N) sum[i+1]=sum[i]+a[i];

    auto f = [&](ll x, ll y){
        if (y==-1){
            int idx = upper_bound(all(a),x)-a.begin();
            return pi(idx,idx);
        }
        ll lo = x - (y+1)/2;
        ll hi = x + y/2;
        int s = lower_bound(all(a),lo)-a.begin();
        int t = upper_bound(all(a),hi)-a.begin();
        return pi(s,t);
    };

    while(Q--){
        ll x; cin>>x;
        ll l=-1,r=2e9;
        while(r-l>1){
            ll c = (l+r)/2;
            auto [lo,hi] = f(x,c);
            int tk = (N-hi);
            int ao = (hi-lo);
            (tk>=ao)?(l=c):(r=c);
        }
        auto [lo,hi] = f(x,l);
        // debug(pi(lo,hi));
        ll ans = sum[N]-sum[hi];

        int tk = (N-hi);
        int ao = (hi-lo);
        if (tk>ao xor lo%2==1){
            ans+=osum[lo];
        }else{
            ans+=sum[lo]-osum[lo];
        }
        cout<<ans<<"\n";
    }
    return 0;
}


Measured memory_bytes: 5584
#include "bits/stdc++.h"
using namespace std;
#define inf 1e9
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define repf(i, x, n) for (ll i = (ll)(x); i < (ll)(n); i++)
#define repfr(i, n, x) for (ll i = (ll)(n)-1; i >= (ll)(x); i--)
using ll = int64_t;

void Main() {
  int n, k;
  std::cin >> n >> k;
  std::vector<int> a(n);
  std::set<int> s;
  for (auto &x : a) {
    std::cin >> x;
    s.insert(x);
  }

  std::vector<int> v(n + 1, 0);
  for (auto &x : a) {
    v[x]++;
  }

  int k_now = s.size();
  for (auto &x : v) {
    if (x) {
    } else {
      x = inf;
    }
  }

  sort(all(v));
  int need = k_now - k;
  int ans = 0;
  rep(i, need) { ans += v[i]; }

  std::cout << ans << '\n';

  return;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 11264
s = input()
t = input()
n = len(s)-len(t)+1
tn = len(t) 

ans = tn
for i in range(n):
    si = s[i:i+tn]
    cnt = 0
    for j in range(tn):
        if si[j] != t[j]:
            cnt += 1
    ans = min(ans, cnt)

print(ans)

Measured memory_bytes: 67624
#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;
// #pragma GCC optimize("O2")
typedef long long int ll;
typedef long double ld;
typedef map <ll,ll> mm;
typedef vector <ll> mv;
typedef pair <ll,ll> mp;
typedef set <ll> ms;
typedef multiset <ll> mms;
typedef queue <ll> mq;
typedef deque <ll> mdq;
typedef stack <ll> mst;
typedef priority_queue <ll> mpq;
typedef priority_queue <ll, vector<ll>, greater<ll> > mmh;
typedef complex<double> cd;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define flush cout.flush();
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb(v) push_back(v)
#define lb(v) lower_bound(v)
#define ub(v) upper_bound(v)
#define cn continue
#define forl(i,n) for(ll i=0;i<n;i++)
#define forlr(i,n) for(ll i=n-1;i>=0;i--)
#define rev(s) reverse(s.begin(),s.end())
void swap(ll &a,ll &b) {
	ll tmp=a;
	a=b;
	b=tmp;
}
ll atoistring(string s) {
	stringstream lol(s);
	ll x;
	lol>>x;
	return x;
}
void pv(mv v) {
	forl(i,v.size()) cout<<v[i]<<" ";
	cout<<"\n";
}
void pa(ll *v,ll size) {
	forl(i,size) cout<<v[i]<<" ";
	cout<<"\n";
}
void removeDups(mv &v) {
	sort(all(v));
	mv::iterator it = unique(v.begin(), v.end());
	v.resize(distance(v.begin(), it));
}
// ll facs[], facsinv[];
// ll nck(ll N,ll K,ll mod) {
// 	if(N<K) return 0;
// 	return (((facs[N]*facsinv[N-K])%mod)*facsinv[K])%mod;
// }
inline ld kthRoot(ld n, ll k) {
	return pow(k, (1.0 / k) * (log(n) / log(k)));
}
ll power(ll x,ll y,ll p) {
	ll res=1;
	x=x%p;
	while(y>0) {
		if(y&1) res = (res*x)%p;
		y=y>>1;
		x=(x*x)%p;
	}
	return res;
}
void checkmod(ll &x,ll mod) {
	if(x>=mod) x%=mod;
}
ll ncr(ll n, ll r, ll mod) {
	ll ans = 1;
	forl(i,min(r,n - r)) {
		ans *= n - i;
		checkmod(ans,mod);
		ans *= power(i+1, mod - 2,mod);
		checkmod(ans,mod);
	}
	return ans;
}
ll sumofgp(ll a,ll n,ll m) {
	// n = number of terms - 1
	if(n < 0) return 0;
	if(n == 0) return 1;
	if(n==1) return (1+a)%m;
	ll ans;
	if(n%2) ans=(1+a)*sumofgp((a*a)%m,(n-1)/2,m);
    else ans=1+((a*(1+a))%m)*sumofgp((a*a)%m,n/2-1,m);
    return ans%m;
}
ll power_of_2_not_less(ll n) {
	if(!n) return 1;
	n--;
	n |= n>>1;
	n |= n>>2;
	n |= n>>4;
	n |= n>>8;
	n |= n>>16;
	n |= n>>32;
	n++;
	return n;
}
ll mod = 1e9 + 7;
// void checktime()
// {
// 	struct timespec ts;
// 	printf("Running Program\n");
// 	clock_gettime(CLOCK_MONOTONIC_RAW,&ts);
// 	long double st=ts.tv_nsec/(1e9)+ts.tv_sec;
// 	// Call Funcn Here
// 	clock_gettime(CLOCK_MONOTONIC_RAW,&ts);
// 	long double en=ts.tv_nsec/(1e9)+ts.tv_sec;
// 	printf("Program ended\nTime = %Lf\n",en-st);
// }
ll arr[200005];
void thisIsMain() {
	ll n, k;
	cin>>n>>k;
	forl(i,n) cin>>arr[i];
	for(ll i=k;i<n;i++) if((arr[i] + arr[i - k] - 1) / arr[i - k] > 1) cout<<"Yes\n"; else cout<<"No\n";
}

int main(void)
{
	fastio
	ll t = 1;
	// cin>>t;
	while(t--) thisIsMain();
	return 0;
}

Measured memory_bytes: 5180
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();

		int minZ = -1000;
		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();
			if (x > minZ)
				minZ = x;
		}
		minZ++;

		int maxZ = Integer.MAX_VALUE;
		for (int i = 0; i < M; i++) {
			int y = sc.nextInt();
			if (y < maxZ)
				maxZ = y;
		}
		sc.close();

		for (int i = minZ; i <= maxZ; i++) {
			if (X < i && i <= Y) {
				System.out.println("No War");
				return;
			}
		}

		System.out.println("War");
	}
}


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

int main() {
	int N;
	vector<int64_t> vec(87);
	vec.at(0) = 2;
	vec.at(1) = 1;
	for (int i = 2; i < 87; i++) {
		vec.at(i) = vec.at(i - 1) + vec.at(i - 2);
	}
	cin >> N;
	cout << vec.at(N) << endl;
}

Measured memory_bytes: 3640
#include <iostream>
using namespace std;
 
char c[55][55];
int H, W, cnt;
 
int main()
{
  cin>>H>>W;
  for  (int i=1; i<=H; i++) {
    for  (int j=1; j<=W; j++) cin>>c[i][j];
  }
  for  (int i=1; i<=H; i++) {
    for  (int j=1; j<=W; j++) {
  if  (c[i][j]=='#'&&c[i][j-1]!='#'&&c[i-1][j]!='#'&&c[i][j+1]!='#'&&c[i+1][j]!='#')  cnt++;
  }
 }
 if(cnt==0)  cout<<"Yes"<<endl;
 else  cout<<"No"<<endl;
 return 0;
}


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

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<vector<long long>> VVL;
typedef vector<string> VS;
typedef pair<ll, ll> P;
typedef tuple<int,int,int> tpl;

#define ALL(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())
#define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin()
#define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin()

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i)
#define RREP(i,n) RFOR(i,n,0)

#define en "\n"

const double EPS = 1e-9;
const double PI  = acos(-1.0);
const int INF = 2147483647;
const long long LINF = 1LL<<60;
const long long MOD = 1000000007; // 998244353

#define CLR(a) memset((a), 0, sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main(void){
    ll W,H; cin >> W >> H;
    VL p(W), q(H); REP(i,W) cin >> p[i]; REP(i,H) cin >> q[i];
    priority_queue<P,vector<P>,greater<P>> que;
    REP(i,W) que.push(P(p[i],0));
    REP(i,H) que.push(P(q[i],1));

    ll ans = 0;
    ll mx = (H+1)*(W+1) - 1, nx = 0, ny = 0;
    while(mx > 0){
        P a = que.top(); que.pop();
        ll cost = a.first;
        if(a.second){
            ans += cost * (W+1 - nx);
            ny++;
            mx -= W+1 - nx;
        }
        else{
            ans += cost * (H+1 - ny);
            nx++;
            mx -= H+1 - ny;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8048
import itertools

N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))


perm = list(range(1,N+1))
perm_list =[]
for v in itertools.permutations(perm,N):
	perm_list.append(v)
a = 0
b = 0
for i in range(len(perm_list)):
	#print(list(perm_list[i]),P)
	perm_list[i] = list(perm_list[i])
	if perm_list[i] == P:
		a = i+1
	if perm_list[i] == Q:
		b = i+1

print(abs(a-b))

Measured memory_bytes: 12276
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a, b = [0], [0]
for i in range(N):
	a.append(a[i] + A[i])
for i in range(M):
	b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
	if a[i] > K:
		break
	while b[j] > K - a[i]:
		j -= 1
	ans = max(ans, i + j)
print(ans)


Measured memory_bytes: 47360
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  string s(n,'0');
  int a[n-1],b[n-1],c=0;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      string t=s;
      t[i]=t[j]='1';
      cout<<"? "<<t<<endl;
      int d;
      cin>>d;
      if(d){
	a[c]=i;
	b[c]=j;
	c++;
      }
    }
  }
  cout<<"!";
  for(int i=0;i<n-1;i++) cout<<" ("<<a[i]<<","<<b[i]<<")";
  cout<<endl;
  return 0;
}


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

int main() {
    int a, b, c, d, maxv_BD, minv_BD, maxv_AC, minv_AC, cnt = 0;
    cin >> a >> b >> c >> d;
    maxv_BD = max(b, d);
    minv_BD = min(b, d);
    maxv_AC = max(a, c);
    minv_AC = min(a, c);
    
    cout << max(0, minv_BD - maxv_AC) << endl;
    return 0;
}

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

using namespace std;

int main() {
    vector<int> n;
    for(int i = 0;i < 4;++i){
        int k;
        cin >> k;
        n.push_back(k);
    }
    sort(n.begin(),n.end());
    if(n[0] == 1 && n[1] == 4 && n[2] == 7 && n[3] == 9)cout << "YES" << endl;
    else cout << "NO" << endl;
}







Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair

int N, D;
int Z;

ll dfs(ll x)
{
	if(x > N) return 0;
	int res = 0;
	if(x <= N && x%10==Z) res++;
	for(int i=0;i<=9;++i){
		res += dfs(10*x+i);
	}
	return res;
}

ll cal(int x, int y)
{
	Z=y;
	return dfs(x);
}

void solve()
{
	D = 0;
	int n = N;
	while(n){
		D++;
		n/=10;
	}
	ll ans = 0;
	for(int fa=1;fa<=9;++fa){
		for(int la=1;la<=9;++la){
			ans += cal(fa,la)*cal(la, fa);
		}
	}
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N;
	solve();
	return 0;
}

Measured memory_bytes: 384
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

ans = 0

for b in B:
    l = -1
    r = N
    while r - l > 1:
        m = (r + l) // 2
        if A[m] < b:
            l = m
        else:
            r = m
    a_cnt = l + 1 if l != -1 else 0

    l = -1
    r = N
    while r - l > 1:
        m = (r + l) // 2
        if C[m] > b:
            r = m
        else:
            l = m
    c_cnt = N - r

    ans += a_cnt * c_cnt

print(ans)


Measured memory_bytes: 24052
#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e18
using namespace std;

const int maxn = 210000;

ll L,R;
int n,pos;
bool flag;
int ex[maxn],id,mx;
char str[maxn];
struct node
{
	ll n,s[26];
	node(){n=0;memset(s,0,sizeof s);}
}f[maxn]; int ed;
inline node operator +(node &x,node &y)
{
	node re; re.n=x.n+y.n;
	for(int i=0;i<26;i++) re.s[i]=x.s[i]+y.s[i];
	return re;
}

void dp()
{
	f[0].n=pos;
	for(int i=0;i<pos;i++) f[0].s[str[i]-'a']++;
	f[1].n=n;
	for(int i=0;i<n;i++) f[1].s[str[i]-'a']++;
	
	ed=1;
	while(f[ed].n<inf) 
		f[ed+1]=f[ed]+f[ed-1],ed++;
}
node solve1(ll x)
{
	ll div=x/f[0].n,oth=x%f[0].n;
	node re; for(int i=0;i<26;i++) re.s[i]=f[0].s[i]*div;
	if(oth)
	{
		for(int i=0;i<oth;i++) re.s[str[i]-'a']++;
	}
	return re;
}
node solve2(ll x,int now)
{
	while(now&&f[now-1].n>=x) now--;
	node re;
	if(now<=1)
	{
		for(int i=0;i<x;i++) re.s[str[i]-'a']++;
		return re;
	}
	re=f[now-1];
	node temp=solve2(x-f[now-1].n,now-2);
	re=re+temp;
	return re;
}
node calc(ll x)
{
	node re;
	if(!x) return re;
	if(flag) re=solve1(x);
	else re=solve2(x,ed);
}

int main()
{
	scanf("%s",str); n=strlen(str); n>>=1; str[n]='$';
	id=1,mx=0;
	for(int i=1;i<n;i++)
	{
		if(mx>=i) ex[i]=min(ex[i-id],mx-i);
		while(str[i+ex[i]]==str[ex[i]]) ex[i]++;
	}
	
	flag=false;
	for(pos=1;pos<n&&pos+ex[pos]-1!=n-1;pos++);
	if(n%pos==0) flag=true;
	dp();
	
	scanf("%lld%lld",&L,&R);
	node a1=calc(R),a2=calc(L-1);
	for(int i=0;i<26;i++) printf("%lld ",a1.s[i]-a2.s[i]);
	
	return 0;
}


Measured memory_bytes: 45312
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

##### 無限 #####
# inf = float('inf')

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

inf = float('inf')

def main():
	S = input()
	S = S[:-1]
	N = len(S)

	K = inputInt()

	dp = [[[0 for ii in range(2)] for j in range(K+1)] for i in range(N+1)]
	dp[0][0][0] = 1

	cnt = 1
	for i in range(N):
		for j in range(K+1):
			for k in range(2):
				targetN = int(S[i])
				for num in range(10):
					ni = i+1
					nj = j
					nk = k

					if num != 0:
						nj += 1
						if nj > K:
							continue

					if k == 0:
						if num > targetN:
							continue
						elif num == targetN:
							nk = 0
						else:
							nk = 1
					else:
						nk = 1

					dp[ni][nj][nk] += dp[i][j][k]
		cnt += 1

	print(dp[N][K][0] + dp[N][K][1])

if __name__ == "__main__":
	main()


Measured memory_bytes: 40432
class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N + 1
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

    def add(self, i, x):
        self.elem[i] += x
        while i <= self.N:
            self.tree[i] += x
            i += i & -i

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


if __name__ == "__main__":
    N = int(input())
    P = list(map(int, input().split()))
    p_to_i = {p: i for i, p in enumerate(P, start=1)}
    bit = BinaryIndexTree(N)
    bit.add(p_to_i[N], 1)

    ans = 0
    for p in range(N - 1, 0, -1):
        cnt = N - p + 1
        i = p_to_i[p]
        # calc_C
        bit.add(i, 1)
        Bsum = bit.sum(i)
        l2 = max(0, bit.lower_bound(Bsum - 2))
        l1 = bit.lower_bound(Bsum - 1)
        r1 = bit.lower_bound(Bsum + 1)
        r2 = min(N + 1, bit.lower_bound(Bsum + 2))
        CL = (l1 - l2) * (r1 - i)
        CR = (r2 - r1) * (i - l1)
        C = CL + CR
        ans += p * C
    print(ans)

Measured memory_bytes: 64304
#include<iostream>
#include<string>
using namespace std;
int s[1010]={0};
int main(){
    int i,j,x,k;
    cin >> x;
    s[1]=1;
    for(i=2;i<=40;i++)
        if(s[i]==0)
            for(j=i*i;j<=1000;j*=i)
                s[j]=1;
    k=1;
    while(x){
        if(s[x]==1)
        {
            k=x;
            break;
        }
        x--;
    }
    cout << k << endl;
    return 0;
}


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

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

    if (d == 0)
    {
        cout << (double)1 / n * (m - 1) << endl;
        return 0;
    }

    long long plus = max(0ll, n - d);
    long long minus = max(0ll, n - (1 + d) + 1);
    long long dbl = plus + minus - n;
    long long sgl = n - dbl;
    cout << fixed << setprecision(7) << ((double)sgl / n / n + (double)dbl * 2 / n / n) * (m - 1) << endl;
}


Measured memory_bytes: 256
import math

s = input()
n = len(s)

r = [0]*n
l = [0]*n

r[0]=1
l[-1]=1

for i in range(1,n):
    if s[i]==s[i-1]=='R':
        r[i]=r[i-1]+1
    elif s[i]=='R':
        r[i]=1
    if s[-i-1]==s[-i]=='L':
        l[-i-1]=l[-i]+1
    elif s[-i-1]=='L':
        l[-i-1]=1

if s[1]=='L':
    print(math.ceil(r[0]/2)+math.floor(l[1]/ 2), end=' ')
else:
    print(0, end=' ')

for i in range(1,n-1):
    if r[i]!=0 and l[i+1]!=0:
        print(math.ceil(r[i]/2)+math.floor(l[i+1]/2),end=' ')
    elif r[i-1]!=0 and l[i]!=0:
        print(math.ceil(l[i]/2)+math.floor(r[i-1]/2),end=' ')
    else:
        print(0,end=' ')

if s[-2]=='R':
    print(math.ceil(l[-1] / 2) + math.floor(r[-2] / 2))
else:
    print(0)



Measured memory_bytes: 64472
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
typedef long long int ll;

struct t{string S; int p; int idx;};

bool comp(const t &a, const t &b){
	if(a.S == b.S) return a.p > b.p;
	return a.S < b.S;
}

int main(){
	int N;
	cin >> N;
	vector<t> va(N);
	for(int i = 0; i < N; i++){
		string s; int n;
		cin >> s >> n;
		va[i] = t{s, n, i};
	}
	sort(va.begin(), va.end(), comp);
	for(int i = 0; i < N; i++){
		cout << va[i].idx + 1 << endl;
	}
	return 0;
}


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

int main(){
    ll n, p; cin >> n >> p;
    ll tmp = p; 
    ll ans = 1;
    for(ll i = 2; i * i <= p; i++){
        int cnt = 0;
        while(tmp % i == 0){
            tmp /= i;
            cnt++;
        }
        ans *= pow(i, cnt/n);
    }
    if(n == 1) ans *= tmp;
    cout << ans << endl;
}

Measured memory_bytes: 4004
using System;
class Program
{    static void Main(String[] args){
  
    string[] str = Console.ReadLine().Split(' ');
    int a = int.Parse(str[0]);
    int b = int.Parse(str[1]);
    int c = int.Parse(str[2]);
    int kara;
    if(a>b){
        kara = b;
        b= a;
        a = kara;
    } 
    if(a>c){
        kara = c;
        c= a;
        a = kara;
    } 
    if(b>c){
        kara = c;
        c= b;
        b = kara;
    } 
    
    Console.WriteLine(a+b+c*10);

    } 
}   

Measured memory_bytes: 11092
use std::process::exit;

fn main() {
  let input: Vec<u32> = read_vec();
  for i in 1..10000 {
    if i*8/100 == input[0] && i*10/100  == input[1] {
      println!("{}", i);
      exit(0);
    }
  }
  println!("-1");
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
  let mut s = String::new();
  std::io::stdin().read_line(&mut s).ok();
  s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}


Measured memory_bytes: 2144
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
class UnionFind {
private:
	int size_; vector<int> g; vector<vector<int> > v;
public:
	UnionFind() : size_(0), g(vector<int>()), v(vector<vector<int> >()) {};
	UnionFind(int size__) : size_(size__) { g.resize(size_), v.resize(size_); for (int i = 0; i < size_; i++) g[i] = i, v[i] = { i }; };
	int size() { return size_; }
	int root(int x) { return g[x]; }
	int size(int x) { return v[x].size(); }
	bool same(int x, int y) { return g[x] == g[y]; }
	void unite(int x, int y) {
		x = g[x], y = g[y];
		if (x == y) return;
		if (v[x].size() < v[y].size()) swap(x, y);
		v[x].insert(v[x].end(), v[y].begin(), v[y].end());
		for (auto &e : v[y]) g[e] = x;
		v[y].clear();
	}
	bool operator==(const UnionFind& u) { return g == u.g; }
	bool operator!=(const UnionFind& u) { return g != u.g; }
	int operator[](int x) { return g[x]; }
};
struct edge { int s, to, cost; };
bool operator<(const edge& e1, const edge& e2) { return e1.cost < e2.cost; }
int V, E, x[10009], y[10009], s, t; edge e[99999];
int main() {
	scanf("%d%d", &V, &E);
	for (int i = 0; i < V; i++) scanf("%d%d", x + i, y + i);
	for (int i = 0; i < E; i++) {
		scanf("%d%d", &s, &t); s--, t--;
		int dist = (x[s] - x[t]) * (x[s] - x[t]) + (y[s] - y[t]) * (y[s] - y[t]);
		e[i] = edge{ s, t, dist };
	}
	sort(e, e + E);
	reverse(e, e + E);
	UnionFind u(V);
	double ret = 0;
	for (auto &v: e) {
		if (u.same(v.s, v.to)) ret += sqrt(v.cost);
		else u.unite(v.s, v.to);
	}
	printf("%.9f\n", ret);
	return 0;
}

Measured memory_bytes: 3724