akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long N;
	cin >> N;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if (N == i * j) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(){
    // Your code here!
    int n;
    cin>>n;
    int A[4][13];
    for(int i=0; i<4; i++){
        for(int j=0; j<13; j++){
            A[i][j]=0;
        }
    }
    
    
    for(int i=0; i<n; i++){
        string s;
        int num;
        cin>>s>>num;
        
        if(s=="S"){
            A[0][num-1] = num;
        }
        else if(s=="H"){
            A[1][num-1] = num;
        }
        else if(s=="C"){
            A[2][num-1] = num;
        }
        else{
            A[3][num-1] = num;
        }
    }
    
    for(int i=0; i<4; i++){
        for(int j=0; j<13; j++){
            if(A[i][j]==0){
                if(i==0){
                    cout<<"S "<<j+1<<endl;
                }
                else if(i==1){
                    cout<<"H "<<j+1<<endl;
                }
                else if(i==2){
                    cout<<"C "<<j+1<<endl;
                }
                else{
                    cout<<"D "<<j+1<<endl;
                }
                
            }
        }
    }
    
    return 0;
}



Measured memory_bytes: 3112
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <set>
#include <stdlib.h>
#include <ctype.h>
#include <stack>
#include <bitset>
#include <iterator>
using namespace std;
#define ull unsigned long long
#define ll long long
const int maxn=1005;
int H,W,h,w;
int main(void){
	scanf("%d%d%d%d",&H,&W,&h,&w);
	printf("%d\n",H*W-(h*W+H*w-h*w));
	return 0;
}

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

bool isprime(long long int val) {
    if (val <= 1)return false;
    for (long long int i = 2; i*i <= val; i++) {
        if (val%i == 0LL)return false;
    }
    return true;
}

int main(){
    int n,m;
    cin>>n>>m;
    int ans=1;
    
    if(isprime(m)) {
        cout<<1<<endl;
        return 0;
    }

    for(int i=0;i+n<=m;i++){
        if(m%(i+n)==0){
            cout<<m/(i+n)<<endl;
            return 0;
        }
    }


}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<queue>
#include<vector>
using namespace std;

#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL

#define MAX 20
#define NIL -1

static char M[MAX][MAX];
static int color[MAX][MAX];
int W, H;
int cnt;

void dfs(int h, int w) {
	cnt++;
	color[h][w] = 0;
	if (h != H - 1 && M[h + 1][w] == '.'&&color[h + 1][w] == NIL)
		dfs(h + 1, w);
	if (h != 0 && M[h - 1][w] == '.'&&color[h - 1][w] == NIL)
		dfs(h - 1, w);
	if (w != W - 1 && M[h][w + 1] == '.'&&color[h][w + 1] == NIL)
		dfs(h, w + 1);
	if (w != 0 && M[h][w - 1] == '.'&&color[h][w - 1] == NIL)
		dfs(h, w - 1);
}

struct { int x; int y; } s;

int main() {
	while (cin >> W >> H&&H&&W) {
		for (int h = 0; h < H; h++) {
			for (int w = 0; w < W; w++) {
				cin >> M[h][w];
				if (M[h][w] == '@')s.x = w, s.y = h;
			}
		}
		fill(color[0], color[MAX], NIL);
		cnt = 0;
		dfs(s.y, s.x);
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 1172
#include <bits/stdc++.h>
#include <vector>
#include <stack>

using namespace std;

int main(){

 int a,b; string s;
  cin>>a>>b;
  cin>>s;

  if(s[a] == '-')
  {
       for(int i=0;i<s.length();i++)
       {
            int number = s[i]-'0';
        if(number >=0 && number<10)
           continue;
        else if(i!= a){
        cout<<"No"<<endl;
        return 0; }
       }
  }
  else{
    cout<<"No"<<endl;
    return 0; }

  cout<<"Yes"<<endl;

return 0;
}


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

typedef long long LL;

using std::min;

const int N=1e5+10,Node=N*30,Inf=1e9+10;

int n,k,l[N],r[N];
LL ans,f[N],summ;

struct SegmentTree{
	#define ls son[z][0]
	#define rs son[z][1]
	int root,val[Node],node,son[Node][2];
	
	int newnode(int v=0){ ++node; son[node][0]=son[node][1]=0; val[node]=v; return node; }
	
	void Lazydown(int z) {
		if (!val[z]) return ;
		if (ls) val[ls]=val[z];else ls=newnode(val[z]);
		if (rs) val[rs]=val[z];else rs=newnode(val[z]);
		val[z]=0;
	}
	
	void add(int &z,int l,int r,int ql,int qr,int v) {
		if (!z) z=newnode();
		if (ql<=l && r<=qr) { val[z]=v; return ; }
		int mid=(l+r)>>1; Lazydown(z);
		if (ql<=mid) add(ls,l,mid,ql,qr,v);
		if (qr>mid)  add(rs,mid+1,r,ql,qr,v);
	}
	
	int query(int z,int l,int r,int pos) {
		if (!z) return 0;
		if (val[z]) return val[z];
		int mid=(l+r)>>1;
		if (pos<=mid) return query(ls,l,mid,pos);
		else return query(rs,mid+1,r,pos);
	}
	
}st;

void Init() {
	scanf("%d%d",&n,&k);
	int sum=0,a,b; ans=0ll;
	for (int i=0;i<n;++i) {
		scanf("%d%d",&a,&b);
		if (b==1 && (a<<1)>k) ans=-1;
		if (b==1) l[i]=sum;else l[i]=0;
		sum=(sum-(a<<1)%k+k)%k;
		if (b==1) r[i]=sum;else r[i]=k-1;
		summ+=(a<<1);
	}
}

void Check(int x) {
	if (l[0]<=r[0] && (l[0]>x || x>r[0])) return ;
	if (l[0]>r[0] && (l[0]<x && x<r[0])) return ;
	int j=st.query(st.root,0,k-1,x);
	if (j) ans=min(ans,f[j]+(l[j]-x+k)%k);
	else ans=0;
}

void Solve() {
	if (ans==-1) { printf("-1\n"); return ; }
	for (int i=n-1;i>=1;--i) {
		int j=st.query(st.root,0,k-1,l[i]);
		if (j) f[i]=f[j]+(l[j]-l[i]+k)%k;
		if (l[i]<=r[i]) {
			if (l[i]) st.add(st.root,0,k-1,0,l[i]-1,i);
			if (r[i]<k-1) st.add(st.root,0,k-1,r[i]+1,k-1,i);
		}else if (r[i]+1<=l[i]-1) st.add(st.root,0,k-1,r[i]+1,l[i]-1,i);
	}
	ans=1e18;
	for (int i=1;i<n;++i) {
		Check(l[i]); Check(r[i]);
	}
	printf("%lld\n",ans+summ);
}

int main() {
	Init();
	Solve();
	return 0;
}

Measured memory_bytes: 34560
#include<iostream>
using namespace std;
string s;
main()
{
    while(cin>>s,s!="0")
    {
        int a=0,b=0;
        for(int i=1;i<s.size();i++)(s[i]=='A'?a:b)++;
        if(a<b)cout<<a<<" "<<b+1<<endl;
        else cout<<a+1<<" "<<b<<endl;
    }
}


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

typedef long long int ll;
ll n;

int main() {
    ll i = 1;
    while(cin >> n) {
        if(n == 0) {
            printf("%lld\n", i);
            return 0;
        }

        i++;
    }

    return 0;
}

Measured memory_bytes: 3776
N,T = map(int,input().split())
root = []
ans = 10**4
for i in range(N):
    c,t = map(int,input().split())
    root.append([c,t])
for i in range(N):
    if root[i][1] > T:
        continue
    else:
        ans = min(ans,root[i][0])
if ans == 10**4:
    print("TLE")
else:
    print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int) (x.size())
#define pii pair<int, int>
#define fi first
#define se second

vector<pii> f;
vector<int> tmp(sz(f));
int lb(int x) {
    return lower_bound(tmp.begin(), tmp.end(), x) - tmp.begin();
}
int get_ans(int a, int b) {
    // cerr << lb(a) << " " << lb(b) << "\n";
    return (sz(f) - lb(a)) * (sz(f) - lb(b) - 1);
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    const int N = 101;
    vector<bool> is_prime(N, true);
    for (int i = 2; i * i <= N; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if(!is_prime[i]) continue;
        int cnt = 0;
        int t = n;
        while (t > 0) {
            cnt += t / i;
            t /= i;
        }
        f.push_back({cnt, i});
    }
    sort(f.begin(), f.end());
    for (auto &el : f) {
        cerr << el.se << " " << el.fi << "\n";
        tmp.push_back(el.fi);
    }
    int ans = get_ans(24, 2) + get_ans(14, 4);
    if (lb(74) < sz(f)) {
        ans++;
    }
    if(sz(f) - lb(4) >= 2 && sz(f) - lb(2) >= 3) {
        int x = sz(f) - lb(4);
        ans += (x * (x - 1) / 2) * (sz(f) - lb(2) - 2);
    }
    cout << ans << "\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define MAX 100
#define MOD 1000000007
#define pb push_back

/* add vars here */

string s;
ll k;
ll b[11];

/* add your algorithm here */

int main() {
  cin >> s;
  cin >> k;

  k -= 1;

  for (int i = 0; i < s.size(); ++i) {
    if (s[i] != '1') {
      cout << s[i] << endl;
      return 0;
    }
    if (k == i) {
      cout << '1' << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int (i)=0;(i) < (N); (i)++)
#define all(V) V.begin(), V.end()
using i64 = int_fast64_t;
using P = pair<int,int>;

template<typename T>
void Warshall_floyd(int V, vector<vector<T>>&dist ){
    for(int mid=0;mid<V;++mid){
        for(int s=0;s<V;++s){
            for(int e=0;e<V;++e){
                if(dist[s][mid] == 1e18 || dist[mid][e] == 1e18) continue;
                if(dist[s][e] > dist[s][mid] + dist[mid][e]) {
                    dist[s][e] = dist[s][mid] + dist[mid][e];
                }
            }
        }
    } 
}

int main(){
    int N, M, L;
    cin >> N >> M >> L;

    vector<vector<i64>> dist(N+1,vector<i64>(N+1,1e18));

    rep(i , M){
        int a, b, c;
        cin >> a >> b >> c;
        dist[a][b] = c;
        dist[b][a] = c;
    }

    Warshall_floyd(N+1, dist);
    
    vector<vector<int>> G(N+1, vector<int>(N+1, 1e9));
    for(int i = 0; i < N+1; i++){
        for(int j = i+1; j < N+1; j++){
            if(dist[i][j] <= L){
                G[i][j] = 1;
                G[j][i] = 1;
            }
        }
    }

    Warshall_floyd(N+1, G);

    int Q;
    cin >> Q;
    rep(i,Q){
        int s, t;
        cin >> s >> t;
        if(s > t) swap(s, t);
        int ans = G[s][t] - 1;
        if(ans == 1e9 -1) ans = -1;
        cout << ans << endl;
    }

}


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

int main(){
	int n,l;
	cin>>n>>l;
	vector<string >vs;
	for(int i=0;i<n;i++){
		string s;
		cin>>s;
		vs.push_back(s);
	}
	sort(vs.begin(),vs.end());
	for(int i=0;i<n;i++){
		cout<<vs[i];
	}
	puts("");
	return 0;
}

Measured memory_bytes: 3544
#include<bits/stdc++.h>
using namespace std;
int n,K;
int main() {
	scanf("%d%d",&n,&K);
	if(K&1) {
		int t=n/K;
		cout<<1ll*t*t*t;
		return 0;
	}
	long long ANS=0;
	for(int i=1;i<=n;i++) {
		int t=i%K;
		if(t*2!=K) continue;
		t=((n-t)/K+1);
		ANS+=1ll*t*t;
	}
	int t=n/K;
	cout<<ANS+1ll*t*t*t;
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  int min_X;
  cin >> min_X;
  int max_X=1-1000000000;
  for(int i=1;i<N;i++){
    int X;
    cin >> X;
    max_X=max(max_X,X-min_X);
    min_X=min(min_X,X);
  }
  cout << max_X << endl;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
using ll  = long long;
using vl  = vector<ll>;
using vi  = vector<int>;
#define _GLIBCXX_DEBUG
#define IO_STREAM cin.tie(0);ios::sync_with_stdio(false)
#define all(x) x.begin(),x.end()
#define rep(i,sta,end) for(int i=sta;i<end;++i)
#define lcm(a,b) (a)/__gcd((a),(b))*(b)
#define pb push_back
const ll INF = 1000000000000000;
const ll MOD = 1000000007;
const double PI = acos(-1);
//||
#define DBG(a,b,c,d) //cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl
//DBG("","","","");

int main(){
	IO_STREAM;
	string S;	cin>>S;
	ll ans=0;
	rep(i,0,S.size()){
		ans+=S[i]-'0';
	}
	if(ans%9){
		cout<<"No"<<endl;
	}
	else{
		cout<<"Yes"<<endl;
	}
	return 0;
}


Measured memory_bytes: 3744
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

bool is_prime(long long n){
	for (int i = 2; i * i <= n; i++){
		if (n % i == 0) return false;
	}
	return true;
}

int main(){
	int n, count = 0;
	long long m;
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> m;
		if (is_prime(m)) count++;
	}
	cout << count << endl;
}

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

#define fori(i,k,n) for(int i = k; i<n; i++)
#define ll long long
#define all(k) k.begin(),k.end()
#define ff first
#define ss second
#define pb push_back

const ll mod = 998244353;

const int mxn = 1e5+1;
ll n;
vector<int> a(n);

ll power(ll x,ll y,ll p){
    ll res = 1;
    x%=p;
    while(y>0){
        if(y&1)res = (res*x)%p;
        y>>=1;
        x = (x*x)%p;
    }
    return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	set<string> st;
	for(int i = 0; i<n; i++){
		string s;
		cin>>s;
		st.insert(s);
	}
	cout<<st.size()<<endl;
}

Measured memory_bytes: 19272
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

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

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()
	x := getInt()
	a := make([]int, N)
	b := make([]int, N)
	for i := 0; i < N; i++ {
		a[i] = getInt()
		if a[i] > x {
			b[i] = a[i] - x
		}
	}

	s := 0
	cnt := 0
	for i := 0; i < N; i++ {
		s = s + a[i]
		d := 0
		if s > x {
			d = s - x
			s = a[i] - d
			a[i] -= d
		} else {
			s = a[i]
		}
		cnt += d
	}
	out(cnt)
}


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

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

	int n;
	cin >> n;
	vector<int> h(n);
	for (int i = 0; i < n; i++)
		cin >> h[i];
	vector<ll> dp(n, 0);
	dp[1] = abs(h[1] - h[0]);
	for (int i = 2; i < n; i++)
		dp[i] = min(abs(h[i] - h[i - 1]) + dp[i - 1], abs(h[i] - h[i - 2]) + dp[i - 2]);
	cout << dp[n - 1];

	return 0;
}


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

int main(){
	int x,y;
	cin >> x >> y;
	while(!(x==0&&y==0)){
		if(x<y) cout << x << " " << y << endl;
		else cout << y << " " << x << endl;
		cin >> x >> y;
	}
	return 0;
}


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

#define MAX_NUM (1000000000 + 7)

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

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

int main() {
  cout << setprecision(18);
  u32 N;
  cin >> N;
  vector<u32> A(N - 1);
  ArrayInput(A);
  vector<u32> Res(N, 0);
  for (u32 i = 0; i < N - 1; ++i) {
    Res[A[i] - 1]++;
  }
  for (u32 i = 0; i < N; ++i) {
    cout << Res[i] << endl;
  }
}

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

int main() {
  ll n;
  cin >> n;
  set<ll> a;
  for(ll i=0;i<n;i++) {
    ll temp;
    cin >> temp;
    a.insert(temp);
  }
  if(a.size()==n) {
    cout << "YES" << endl;
  }
  else {
    cout << "NO" << endl;
  }
}

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

int main(){
  string S;
  cin >> S;
  int a = 0;
  for(int i = 0;i < 3;i++){
    if(S[i] == 'o')a++;
  }
  cout << 700 + 100 * a << endl;
}

Measured memory_bytes: 256
from functools import reduce

def main():
    # 初期値用:十分大きい数(100億)
    # 1e10

    # 初期値用:十分小さい数(-100億)
    # -1e10
    
    # 1文字のみを読み込み
    # s = input().rstrip()
    
    # スペース区切りで標準入力を配列として読み込み
    # s = input().rstrip().split(' ')

    # 1文字ずつ標準入力を配列として読み込み
    # s = list(input().rstrip())
    # N, A = [int(_) for _ in input().split()]
    # X = [int(_) for _ in input().split()]
    S = list(input().rstrip())
    tmp_color = S[0]
    ans=0 
    for i in range(len(S)):
        if(tmp_color != S[i]):
            tmp_color = S[i]
            ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 4580
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	static boolean xFlg, yFlg, swap;
	static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int x = sc.nextInt();
		int y = sc.nextInt();
		sc.close();

		if (x < 0) {
			x *= -1;
			xFlg = true;
		}
		if (y < 0) {
			y *= -1;
			yFlg = true;
		}
		if (x > y) {
			int t = x;
			x = y;
			y = t;
			swap = true;
		}
		int z = x + y;
		if (k % 2 == 0 && z % 2 == 1) {
			System.out.println(-1);
			return;
		}

		int ans = 1;
		if (z != k) {
			ans = (z + k - 1) / k;
			if (ans == 1) {
				ans = 2;
			}
			if (k * ans % 2 != z % 2) {
				ans++;
			}
		}
		pw.println(ans);

		if (ans == 3 && z < k && z % 2 == 1) {
			int x1 = k - y;
			print(x1, y);
			int x2 = (x + x1) / 2;
			print(x2, y + k - (x1 - x2));
			print(x, y);
		} else {
			int total = k * ans;
			int over = (total - z) / 2;
			int sum = 0;
			int x2 = 0;
			int y2 = 0;
			while (sum < total) {
				sum += k;
				if (sum <= x + over) {
					x2 = sum;
					y2 = 0;
				} else if (sum <= x + over + y) {
					x2 = x + over;
					y2 = sum - x2;
				} else {
					x2 = x;
					y2 = y;
				}
				print(x2, y2);
			}
		}
		pw.flush();
	}

	static void print(int x, int y) {
		if (swap) {
			int t = x;
			x = y;
			y = t;
		}
		if (yFlg) {
			y *= -1;
		}
		if (xFlg) {
			x *= -1;
		}
		pw.println(x + " " + y);
	}
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  int c0 = 0, c1 = 0, c2 = 0, c3 = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == "AC")
      c0++;
    else if (s[i] == "WA")
      c1++;
    else if (s[i] == "TLE")
      c2++;
    else
      c3++;
  }
  cout << "AC x " << c0 << '\n';
  cout << "WA x " << c1 << '\n';
  cout << "TLE x " << c2 << '\n';
  cout << "RE x " << c3 << '\n';
  return 0;
}

Measured memory_bytes: 6360
#include <iostream>
#include <cstring>
#include <bitset>
#include <cstdio>
using namespace std;
typedef long long ll;

const int maxn = 5010;

bitset<maxn> pre[maxn],suf[maxn],tmp;
int a[maxn];
int sum[maxn];

bool check(int x, int lb, int ub)
{
	for (int i=lb;i<=ub;i++)
		if (suf[x][i]) return true;
	return false;
}
	
int main()
{
	//freopen("D.in","r",stdin);
	//freopen("D.out","w",stdout);
	int n,k;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	
	pre[0].reset(); 
	pre[0][0] = 1;
	for (int i=1;i<=n;i++)
	{
		tmp.reset();
		if (a[i] < maxn) tmp = pre[i-1] << a[i];
		pre[i] = pre[i-1] | tmp;
	}
	
	suf[n+1].reset();
	suf[n+1][0] = 1;
	for (int i=n;i>=1;i--)
	{
		tmp.reset();
		if (a[i] < maxn) tmp = suf[i+1] << a[i];
		suf[i] = suf[i+1] | tmp;
	}
	
	int cnt = 0;
	for (int i=1;i<=n;i++)
	{
		int lb = max(k-a[i],0), ub = k-1;
		bool exist = false;
		for (int sum1=0;sum1<=ub;sum1++)
		{
			if (!pre[i-1][sum1]) continue;
			int lb2 = max(lb-sum1,0), ub2 = ub-sum1;
			if (ub2 < lb2) continue;
			if (check(i+1,lb2,ub2)) 
			{
				exist = true;
				break;
			}
		}
		if (!exist) cnt++;
	}
	printf("%d\n",cnt);
	return 0;
}


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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

void add(ll& h, ll &m){
  if(m==59){
    h++;
    m=0;
  }else{
    m++;
  }
}

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

  ll h1,m1,h2,m2,k;
  cin>>h1>>m1>>h2>>m2>>k;
  ll ch=h1,cm=m1;
  ll res=0;
  while(true){
    ll nh=ch,nm=cm;
    ll cnt=0;
    while(nh<h2||(nh==h2&&nm<m2)){
      cnt++;
      add(nh,nm);
    }
    if(cnt<k)break;
    res++;
    add(ch,cm);
  }
  cout<<res-1<<endl;

  return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cassert>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
#include <forward_list>
#include <array>
#include <cstring>
#include <cmath>
#include <tuple>
#include <complex>
#include <bitset>
#include <climits>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pld = pair<LD, LD>;
int len_S, len_T;


int get_nr_diff_chrs(const deque<char> cur_str, const string searched_str)
{
    int res = 0;
    for (int i = 0; i < len_T; ++i)
    {
        res += cur_str[i] != searched_str[i];
    }

    return res;
}


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

    string S, T;
    cin >> S >> T;
    len_S = S.size(), len_T = T.size();
    
    deque<char> cur_str;
    for (const char &chr : S.substr(0, len_T))
    {
        cur_str.emplace_back(chr);
    }
    int ans = get_nr_diff_chrs(cur_str, T);
    for (int i = 1; i + len_T <= len_S; ++i)
    {
        cur_str.pop_front();
        cur_str.emplace_back(S[i + len_T - 1]);

        ans = min(ans, get_nr_diff_chrs(cur_str, T));
    }

    cout << ans;
}


Measured memory_bytes: 3628
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
 
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define loop(i,n) for(int i=0;i<(n);i++)
#define fori(a,b,i) for(int i=(a);i<=(b);i++)
#define ford(a,b,i) for(int i=(a);i>=(b);i--)
#define fast_io ios_base::sync_with_stdio(false) , cin.tie(NULL);


#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007

#define fir first
#define sec second
#define pb push_back
#define mp make_pair

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int,int> MII;
typedef set<int> SI;
typedef long long int llint;


int main(){
	llint n, k;
	cin>>n>>k;
	llint h[n];
	loop(i, n) cin>>h[i];
	llint dp[n];
	loop(i, n) dp[i] = INF;
	dp[0] = 0;
	for(int i = 1; i < n; ++i){
		for(int j = 1; j <= k; ++j){
			if(i - j < 0) break;
			//debug(dp[i]);
			//debug(i);
			dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i - j]));
		} 
	}
	cout<<dp[n-1];
	return 0;
}


Measured memory_bytes: 1792
H, W, A, B = map(int, input().split())

ans = 0 
MOD = 10**9 + 7
N = H + W - 2
fac = [1] * (N+1)
inv = [1] * (N+1)

# 階乗
for i in range(1, N+1):
    fac[i] = i * fac[i - 1] % MOD
 
# 普通の逆元テーブル
for i in range(1, N+1):
    inv[i] = pow(fac[i], MOD-2, MOD)
 
 
def f(x, y):
    ans = fac[x + y] * inv[x] * inv[y] % MOD
    return ans
 

for x in range(B, W):
    ans += f(x, H - A - 1) * f(W - 1 - x, A - 1)
    ans %= MOD
    
print(ans % MOD)

Measured memory_bytes: 20388
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
ll n,k,ans,b[3],a[100005],c[100005];
string t;
int main(){
	cin >> n >> k >> b[1] >> b[2] >> b[0] >> t;
	for(int i=0;i<n;i++)
		if(t[i]=='r')a[i]=0;
		else if(t[i]=='s')a[i]=1;
		else a[i]=2;
	for(int i=0;i<n;i++)
		if(i<k or a[i]!=a[i-k] or c[i-k]==0)ans+=b[a[i]],c[i]=1;
	cout << ans;
	return 0;
}

Measured memory_bytes: 2048
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val an = readLine()!!.split(" ").map { it.toInt() - 1 }

    var array = Array(n) { mutableSetOf<Int>() }
    for ((i, a) in an.withIndex()) {
        array[a].add(i)
    }

    var c = 0
    for ((i, a) in an.withIndex()) {
        if(array[i].contains(a)){
            c++
        }
    }
    println(c/2)
}

Measured memory_bytes: 85944
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
 
n = int(input())
edge = [[] for _ in range(n)]
edge_dict = dict()
 
for i in range(n - 1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)
    if a > b:
        edge_dict[(b, a)] = i
    else:
        edge_dict[(a, b)] = i
 
m = int(input())
uv = []
for _ in range(m):
    uv.append([int(item) - 1 for item in input().split()])
 
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(edge[v]) == 1:
        return False
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False
 
# edge-bitset of each set of constraints
edgest = [0] * 2**m
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in edge_dict:
            edgest[1 << i] |= (1 << edge_dict[(uu, vv)])
for i in range(1, 2**m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]
 
# dp[set of constraints]
dp = [0] * 2**m
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2**m):
    lsb = i & (-i)
    limit_num = bin(edgest[i] ^ edgest[i ^ lsb]).count("1")
    dp[i] = dp[i ^ lsb] >> limit_num
    # Inclusion and exclusion
    if bin(i).count("1") % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)

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

int main()
{
	int a1;
	int b1;
	int a2;
	int b2;
	int min;
	int max;
	while (cin >> a1 >> b1 >> a2 >> b2)
	{
		if (a1 > a2)
		{
			max = a1;
		}
		else
		{
			max = a2;
		}
		if (b1 > b2)
		{
			min = b2;
		}
		else
		{
			min = b1;
		}
		if (min - max > 0)
		{
			cout << min - max << endl;
		}
		else
		{
			cout << 0 << endl;
		}
	}

	return 0;
}

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

int max(int a,int b){if(a > b)return a;else return b;}

int main(){
    int n;cin >> n;
    vector<int> a(n+5);

    int INF = 100000000;
    int first = INF;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if((first == INF) && (a[i] == 1) )first = i;
    }


    if(first != INF){
        int ans = first ;
        int check = 2;
        for(int i = first+1; i < n;i++){
            if(a[i] == check){
                ans+=(i-first)-1;
                first = i;
                check++;
            }
            if(i == (n-1)){
                ans+=(i-first);
            }
        }

        cout << max(0,ans) << endl;
    }
    else{
        cout << -1 << endl;
    }
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
import sys


def solve(N: int, X: int, L: "List[int]"):
    x = 0
    pos = [0]
    for i,l in enumerate(L):
        x += l
        pos.append(x)

    for i,p in enumerate(pos):
        if p > X:
            print(i)
            return
    print(N+1)





# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    L = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, X, L)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

struct edge { int to; int cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int MOD = 1e9+7;
const double EPS = 1.0e-12;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

ll dp[110][100010];

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

	return 0;
}

Measured memory_bytes: 79360
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;
const long LINF = 1e13;
const long LLINF = 1e18;
const long ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}



int main() {

  ll k,a,b;

  cin >> k >>a >>b;
  


  ll bis =1;
  // long en=0;
  // ll ans = 0;

  double plusBisket = 0;

  plusBisket = (double)(b-a)/ (double)2;



  for(ll i=0;i<k;i++){
    if (plusBisket >= 1 && bis >= a && i <k-1){
      i++;
      bis += b-a;
    }else{
      bis++;
    }
  }

  cout << bis << endl;


}




















Measured memory_bytes: 256
s = int(input())
sl = [s]
while True:
    new_t = 0
    if s % 2 == 0:new_t = s//2
    else:new_t = 3 * s + 1
    if new_t in sl:
        print(len(sl)+1)
        break
    else:sl.append(new_t)
    s = new_t

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int x,y,z;cin >> x >> y >> z;
	x-=z;
	cout << x/(y+z) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<math.h>
#define rep(i,k,n) for(int i=k;i<n;i++)
#define ll long long
#define MOD 1000000007ll
#define ROD 1000000009ll
#define INF 1e18
#define MIN(a,b) (a>b?b:a)
using namespace std;
#define mp make_pair
#define pb push_back
#define  piii pair<pair<ll,ll>,ll>
#define pii pair<ll,ll>
#define fi first
#define se second
#define MAXN 1000055

int main()
{
	ll n;
	scanf("%lld",&n);
	//cout<<(1&3)<<" ";
	if(__builtin_popcount(n)==1||n<3)
	{
		printf("No\n");
	}
	else if((n&3)==3)
	{
		printf("Yes\n");
		cout<<"1 2\n"<<"2 3\n"<<"3 "<<n+1<<"\n"<<n+1<<" "<<n+2<<"\n"<<n+2<<" "<<n+3<<"\n";
		ll pos=3;
		while(n!=pos)
		{
			cout<<n+pos<<" "<<pos+1<<"\n";
			cout<<pos+1<<" "<<pos+2<<"\n";

			cout<<pos+2<<" "<<pos+3<<"\n";
			cout<<pos+3<<" "<<pos+4<<"\n";
			cout<<pos+4<<" "<<n+pos+1<<"\n";
			cout<<n+pos+1<<" "<<n+pos+2<<"\n";
			cout<<n+pos+2<<" "<<n+pos+3<<"\n";
			cout<<n+pos+3<<" "<<n+pos+4<<"\n";
			pos+=4;
		}
	}
	else if((n&3)==0)
	{
		printf("Yes\n");
		cout<<"1 2\n"<<"2 3\n"<<"3 "<<n+1<<"\n"<<n+1<<" "<<n+2<<"\n"<<n+2<<" "<<n+3<<"\n";
		ll pos=3;
		while(n-1!=pos)
		{
			cout<<n+pos<<" "<<pos+1<<"\n";
			cout<<pos+1<<" "<<pos+2<<"\n";

			cout<<pos+2<<" "<<pos+3<<"\n";
			cout<<pos+3<<" "<<pos+4<<"\n";
			cout<<pos+4<<" "<<n+pos+1<<"\n";
			cout<<n+pos+1<<" "<<n+pos+2<<"\n";
			cout<<n+pos+2<<" "<<n+pos+3<<"\n";
			cout<<n+pos+3<<" "<<n+pos+4<<"\n";
			pos+=4;
		}

		ll low=(n&-n);
		ll high=n^(n&-n);
		low=n+low+1;
		cout<<n<<" "<<low<<"\n";
		cout<<high<<" "<<2*n<<"\n";
		
	}
	else if((n&3)==1)
	{
		printf("Yes\n");
		cout<<"1 2\n"<<"2 3\n"<<"3 "<<n+1<<"\n"<<n+1<<" "<<n+2<<"\n"<<n+2<<" "<<n+3<<"\n";
		ll pos=3;
		while(n-2!=pos)
		{
			cout<<n+pos<<" "<<pos+1<<"\n";
			cout<<pos+1<<" "<<pos+2<<"\n";

			cout<<pos+2<<" "<<pos+3<<"\n";
			cout<<pos+3<<" "<<pos+4<<"\n";
			cout<<pos+4<<" "<<n+pos+1<<"\n";
			cout<<n+pos+1<<" "<<n+pos+2<<"\n";
			cout<<n+pos+2<<" "<<n+pos+3<<"\n";
			cout<<n+pos+3<<" "<<n+pos+4<<"\n";
			pos+=4;
		}
		cout<<n-1<<" "<<n<<"\n";
		cout<<n<<" "<<1<<"\n";
		cout<<1<<" "<<n+n-1<<"\n";
		cout<<n+n-1<<" "<<n+n<<"\n";
	}
	else if((n&3)==2)
	{
		printf("Yes\n");
		cout<<"1 2\n"<<"2 3\n"<<"3 "<<n+1<<"\n"<<n+1<<" "<<n+2<<"\n"<<n+2<<" "<<n+3<<"\n";
		ll pos=3;
		while(n-3!=pos)
		{
			cout<<n+pos<<" "<<pos+1<<"\n";
			cout<<pos+1<<" "<<pos+2<<"\n";

			cout<<pos+2<<" "<<pos+3<<"\n";
			cout<<pos+3<<" "<<pos+4<<"\n";
			cout<<pos+4<<" "<<n+pos+1<<"\n";
			cout<<n+pos+1<<" "<<n+pos+2<<"\n";
			cout<<n+pos+2<<" "<<n+pos+3<<"\n";
			cout<<n+pos+3<<" "<<n+pos+4<<"\n";
			pos+=4;
		}
		
		cout<<n-1-1<<" "<<n-1<<"\n";
		cout<<n-1<<" "<<1<<"\n";
		cout<<1<<" "<<n+n-1-1<<"\n";
		cout<<n+n-1-1<<" "<<n+n-1<<"\n";
		
		cout<<n<<" "<<n-1<<"\n";
		cout<<2<<" "<<2*n<<"\n";
	}
}


Measured memory_bytes: 3676
#include <iostream>
#include <string>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main(int argc, char const *argv[]) {
  string s;
  cin >> s;
  bool flag = true;
  rep(i, s.size()) {
    if (i % 2 != 0) {
      if (s[i] == 'R')
        flag = false;
    } else {
      if (s[i] == 'L')
        flag = false;
    }
  }
  if (flag)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void dfs(int u, vector<vector<int>> &graph, vector<bool> &visited)
{
    visited[u] = true;
    for (auto v : graph[u])
    {
        if (!visited[v])
            dfs(v, graph, visited);
    }
}
int main()
{

    int n, m;
    cin >> n >> m;
    vector<bool>visited(n + 1,false);
    vector<vector<int>> graph(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    int count = 0;
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
           count++;
            dfs(i, graph, visited);
           
        }
    }
    cout << count - 1 << '\n';
}


Measured memory_bytes: 9564
#include <bits/stdc++.h>
using namespace std;
int w,a,b;
int main(){
	cin>>w>>a>>b;
	if(b>a+w)cout<<b-(w+a)<<endl;
	else if(a>b+w)cout<<a-(w+b)<<endl;
	else cout << 0 << endl;
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define ri register int
#define il inline
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define all(x) x.begin(),x.end() 
#define rep(i,a,b) for(ri i=(a);i<=(b);++i)
#define per(i,a,b) for(ri i=(a);i>=(b);--i)
#define ls (x<<1)
#define rs (x<<1|1)
#define mid (l+r>>1)
#define de(x) cout << #x << " = " << x << endl
#define dd() cout << "Out Put!\n"
const int maxn=1000010;
const double eps = 1e-8,PI = acos(-1.0);
const int inf=0x7f7f7f7f;
using namespace std;
int a[maxn];
char s[maxn];
il int qpow(int base,int m,int mod)
{
	int res = 1; 
	while(m)
	{
		if(m&1)
			(res*=base)%=mod;
		(base*=base)%=mod;
		m >>= 1ll;
	}
	return res%mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n >> s;
	int l = strlen(s)-1;
	int sum = 0;
	rep(i,0,l)
		sum+=s[i]-'0';
	int d=0,e=0,f=0;
	per(i,l,0)
		if(s[i] == '1')
		{
			if(sum!=1)
				d+=qpow(2,l-i,sum-1);
			f+=qpow(2,l-i,sum+1);
		}
	a[0] = 0;
	rep(i,1,200010)
	{
		int x= i;
		int ans = 0;
		int f=0;
		while(x)
		{		
			int cnt = 0;
			rep(j,0,25)
				if((1ll<<j)&x)
					cnt++;
			if(!f)
				f=cnt;
			x = x%cnt;
			ans++;
		}
		a[i] = ans;
	}
	rep(i,0,l)
	{
		if(s[i] == '1')
		{
			if(sum == 1)
			{
				cout << 0 << endl;
				continue;
			}
			int p = d;
			p-=qpow(2,l-i,sum-1);
			p = (p+sum-1)%(sum-1);
			cout<<a[p]+1 << endl;
		}
		else
		{
			int p = f;
			p+=qpow(2,l-i,sum+1);
			p%=(sum+1);
			cout <<a[p]+1 << endl;
		}
	}
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define forn(i, a, n) for (int i = a; i < n; ++i)
#define ford(i, a, n) for (int i = n - 1; i >= a; --i)
#define fore(i, a, n) for (int i = a; i <= n; ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
	for (auto i : a) cerr << i << ' ';\
	cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(2 * n);
	forn(i, 0, 2 * n) cin >> a[i];
	sort(all(a));
	int ans = 0;
	forn(i, 0, n) ans += a[2 * i];
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

# input
N = int(input())
T = list(map(int, input().split()))
M = int(input())
PX = [list(map(int, input().split())) for i in range(M)]

# solve & output
ans = sum(T)
for i in range(M):
    diff = PX[i][1] - T[PX[i][0] - 1]
    print(ans + diff)


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

using namespace std;

typedef pair<int, int> pii;
typedef pair<pii, pii> pp;

const int maxn = 1<<18;

int n, a[maxn];
pp dp[maxn];

pii tmp[5];

pp max(pp p1, pp p2) {
    tmp[0] = p1.first;
    tmp[1] = p1.second;
    tmp[2] = p2.first;
    tmp[3] = p2.second;
    sort(tmp, tmp+4);
    if (tmp[3].second == tmp[2].second) return pp(tmp[3], tmp[1]);
    else return pp(tmp[3], tmp[2]);
}

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

    cin >> n;
    for (int i = 0; i < (1<<n); i++) {
        cin >> a[i];
        dp[i] = pp(pii(a[i], i), pii(-2e9, -1));
    }

    for (int i = 0; i < (1<<n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                dp[i] = max(dp[i], dp[i ^ (1<<j)]);
            }
        }
    }

    int ans = -2e9;
    for (int i = 1; i < (1<<n); i++) {
        ans = max(ans, dp[i].first.first + dp[i].second.first);
        cout << ans << '\n';
    }
}

Measured memory_bytes: 8192
def main():
    n = int(input())
    count = 0
    for i in range(n):
        a,b = map(int,input().split())
        if a == b:
            count += 1
        else:
            count = 0

        if count == 3:
            print('Yes')
            return

    print('No')
    

main()


Measured memory_bytes: 62292
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define MOD 1000000007
#define MOD2 998244353
#define int long long
#define double long double
#define EPS 1e-9
//#define PI 3.14159265358979

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

using namespace std;

template < typename T >
ostream &operator<<(ostream &os, const vector< T > &A) {
	for (int i = 0; i < A.size(); i++)
		os << A[i] << " ";
	os << endl;
	return os;
}
template <>
ostream &operator<<(ostream &os, const vector< vector< int > > &A) {
	int N = A.size();
	int M;
	if (N > 0)
		M = A[0].size();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			os << A[i][j] << " ";
		os << endl;
	}
	return os;
}

typedef pair< int, int > pii;
typedef long long ll;

struct edge {
	int from, to, d, c;
	edge(int _from = 0, int _to = 0, int _d = 0, int _c = 0) {
		from = _from;
		to = _to;
		d = _d;
		c = _c;
	}
	bool operator<(const edge &rhs) const {
		return (d == rhs.d) ? (c < rhs.c) : (d < rhs.d);
	}
};
struct aabb {
	int x1, y1, x2, y2;
	aabb(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}
};

typedef vector< edge > edges;
typedef vector< edges > graph;
struct flow {
	int to, cap, rev, cost;
	flow(int to = 0, int cap = 0, int rev = 0, int cost = 0) : to(to), cap(cap), rev(rev), cost(cost) {}
};
typedef vector< vector< flow > > flows;

const int di[4] = {0, -1, 0, 1};
const int dj[4] = {-1, 0, 1, 0};
const int ci[5] = {0, 0, -1, 0, 1};
const int cj[5] = {0, -1, 0, 1, 0};
const ll LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const double PI = acos(-1);

int pow2(int n) { return 1LL << n; }
template < typename T, typename U >
bool chmin(T &x, const U &y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}
template < typename T, typename U >
bool chmax(T &x, const U &y) {
	if (x < y) {
		x = y;
		return true;
	}
	return false;
}

struct initializer {
	initializer() {
		cout << fixed << setprecision(20);
	}
};
initializer _____;

int N, M, K, T, Q, H, W;
signed main() {
	cin >> N >> K;
	vector< int > A(N);
	rep(i, N) {
		cin >> A[i];
		--A[i];
	}
	vector< vector< int > > knext(64, vector< int >(N));
	rep(i, N) knext[0][i] = A[i];
	rep(k, 63) rep(i, N) knext[k + 1][i] = knext[k][knext[k][i]];
	int ans = 0;
	for (int k = 63; k >= 0; k--) {
		if (K - pow2(k) >= 0) {
			ans = knext[k][ans];
			K -= pow2(k);
		}
	}
	cout << ans + 1 << endl;
	//cout << knext;
	return 0;
}

Measured memory_bytes: 106468
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
#define FOR(i, m, n) for (int i = m; i < n; i++)
 
int main() {
    vector<pair<int,P> > ls;
    FOR(i,1,151){
        FOR(j,i+1,151){
            ls.push_back({i*i+j*j,P(i,j)});
        }
    }
    sort(ls.begin(),ls.end());
    while(1){
        int h,w;
        cin >> h >> w;
        if(h==0)break;
        int t = 0;
        while(ls[t].second != P(h,w))t++;
        cout << ls[t+1].second.first << " " << ls[t+1].second.second << endl;
    }
    return 0;
}


Measured memory_bytes: 3204
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
#define LL long long
using namespace std;
inline bool scan_d(int &num)  
{
        char in;bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}
struct note{
	int num,ard;
	bool operator < (const note &n) const {  
		if(num!=n.num)
        return num<n.num;
		return ard>n.ard;
    }
} a[300110];
int main(){
	int n;
	scan_d(n);
	for(int j = 0 ; j < n ; j++){
		scan_d(a[j].num);
		a[j].ard = 1;
	}
	for(int j = n; j < 2*n ; j++){
		scan_d(a[j].num);
		a[j].ard = 2;
	}
	for(int j = 2*n ; j < 3*n ; j++){
		scan_d(a[j].num);
		a[j].ard = 3;
	}
	sort(a,a+3*n);
	LL sum1= 0,sum2 = 0,sum3 = 0;
	//if(a[0].ard == 1) sum1++;
	for(int i = 0 ; i< 3*n;i++){
			if(a[i].ard == 1) sum1++;
			else if(a[i].ard == 2) sum2 += sum1;
			else if(a[i].ard == 3) {
				sum3 += sum2; 
			}
	//	printf("大小 %3d 位置 %3d 一的和%3d 二的和%3d 三的和%3d\n",a[i].num,a[i].ard,sum1,sum2,sum3);
	}
	printf("%lld\n",sum3);
} 

Measured memory_bytes: 2560
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n); i++) 
#define dunk(n) cout << n << endl
#define all(a) (a).begin(),(a).end()
typedef pair<int,int> P;
typedef long long ll;

int main() {
    int k;
    cin >> k;
    string s;
    cin >> s;
    if(s.size() <= k) dunk(s);
    else{
        rep(i,k){
            cout << s[i];
        }
        cout << "..." << endl;
    }
    return 0;
}

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

int main(){
    string s,t = "";
    cin >> s;
    string u = s;
    s += "  ";
    int i = 0;
    while(1){
        if(s.substr(i,5) == "dream"){
            i += 5;
            if(s.substr(i,2) == "er"){
                if(s.substr(i+2,1) == "d"){
                    i += 2;
                    t += "dreamer";
                }else if(s.substr(i+2,1) == "e"){
                    i += 2;
                    t += "dreamer";
                }else if(s.substr(i+2,1) == "a"){
                    t += "dream";
                }else if(s.substr(i+2,1) == " "){
                    i += 2;
                    t += "dreamer";
                }
            }else if(s.substr(i,1) == "d"){
                t += "dream";
            }else if(s.substr(i,1) == " "){
                t += "dream";
            }
        }

        else if(s.substr(i,5) == "erase"){
            i += 5;
            if(s.substr(i,1) == "r"){
                i += 1;
                t += "eraser";
            }else if(s.substr(i,1) == "e"){
                t += "erase";
            }else if(s.substr(i,1) == "d"){
                t += "erase";
            }else if(s.substr(i,1) == " "){
                t += "erase";
            }
        }
        else break;
        //if(s.substr(i,1) == " ")break;
    }
    if(u == t)cout << "YES" <<endl;
    else cout << "NO" << endl;
}

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

const int INF = 1e9;

int main() {
    int N;
    int h[100010];
    cin >> N;
    for (int i = 0; i < N; i++) cin >> h[i];

    // 1. DPテーブルの初期化
    int dp[100010];
    for (int i = 0; i < N; i++) dp[i] = INF;
    dp[0] = 0;

    // 2. DPテーブル更新方策
    // -- 足場iから足場jへのコストをc_ijとすると、足場iにたどり着くまでのコストは
    // -- min(c_(i-1)i, c_(i-2)i)
    for (int i = 1; i < N; i++) {
        if (i == 1) {
            dp[i] = abs(h[i] - h[0]);
        } else {
            int cost1 = dp[i-1] + abs(h[i] - h[i-1]);
            int cost2 = dp[i-2] + abs(h[i] - h[i-2]);
            dp[i] = min(cost1, cost2);
        }
    }
    cout << dp[N-1] << endl;
}


Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(10**6)
N = int(input())
edg = [list(map(int,input().split())) for _ in range(N-1)]
vtx = [[] for _ in range(N)]
for e in edg:
    v1,v2,w = e
    vtx[v1-1].append([v2-1,w])
    vtx[v2-1].append([v1-1,w])

colors = [1 for _ in range(N)]

def dfs(vtx,i=0,p=-1,c=1): # vertex and its parent
    colors[i] = c
    for v,w in vtx[i]:
        if v == p:
            continue
        dfs(vtx,v,i,1-c if w%2 != 0 else c)
dfs(vtx)

for v in colors:
    print(v)

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i, n) cin >> h[i];

    sort(h.begin(), h.end());

    int ans = INT32_MAX;
    rep(i, n - k + 1)
    {
        ans = min(ans, h[i + k - 1] - h[i]);
    }

    cout << ans << endl;
}


Measured memory_bytes: 640