akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXN = 10000000;
const int MAXON = 5000;
const int MOD = 1000000007;
void inc(int &a, int b) { if ((a += b) >= MOD) a -= MOD; }
void dec(int &a, int b) { inc(a, MOD - b); }

int inv[MAXN + 1];
int fac[MAXN + 1];
int ifac[MAXN + 1];

int prod(int l, int h) { return (ll)fac[h] * ifac[l - 1] % MOD; }
int choose(int n, int k) { if (k<0 || k>n) return 0; return (ll)fac[n] * ifac[k] % MOD*ifac[n - k] % MOD; }

// a items that we pick, b items that should be in the same cycles, c items that we don't care about
int calc(int a, int b, int c) {
	int ret = 0;
	FORE(i, 1,a) {
		// i items are non-identity
		int cur = fac[i];
		cur = (ll)cur*prod(i, i + b - 1) % MOD;
		cur = (ll)cur*prod(i + b + 1, i + b + c) % MOD;
		cur = (ll)cur*choose(a, i) % MOD;
		//printf("\t(%d,%d,%d): %d = %d\n", a, b, c, i, cur);
		if ((a - i) % 2 == 0) inc(ret, cur); else dec(ret, cur);
	}
	return ret;
}

int n, on;

int solve() {
	inv[1] = 1; FORE(i, 2, n) inv[i] = (ll)(MOD - MOD / i)*inv[MOD%i] % MOD;
	fac[0] = 1; FORE(i, 1, n) fac[i] = (ll)fac[i - 1] * i%MOD;
	ifac[0] = 1; FORE(i, 1, n) ifac[i] = (ll)ifac[i - 1] * inv[i] % MOD;

	int ret = 0;
	int off = n - on;
	FORE(i, 1, on) {
		int cur = calc(i, off, i == on ? 0 : on - i - 1);
		//printf("%d: %d\n", i, cur);
		inc(ret, cur);
	}
	return ret;
}

void run() {
	scanf("%d%d", &n, &on);
	printf("%d\n", solve());
}

int main() {
	run();
	return 0;
}


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

typedef struct{
	int p;
	int l;
	int r;
}Node;

void Preorder(int);
void Inorder(int);
void Postorder(int);

Node *node;

int main(void){
	int n,id,root;
	int i;

	scanf("%d",&n);

	node=(Node*)malloc(n*sizeof(Node));

	for(i=0;i<n;i++){
		node[i].p=-1;
		node[i].l=-1;
		node[i].r=-1;
	}

	for(i=0;i<n;i++){
		scanf("%d",&id);

		scanf("%d",&node[id].l);
		if(node[id].l != -1) node[node[id].l].p=id;

		scanf("%d",&node[id].r);
		if(node[id].r != -1) node[node[id].r].p=id;
	}

	for(i=0;i<n;i++){
		if(node[i].p==-1) root=i;
	}

	printf("Preorder\n");
	Preorder(root);
	printf("\n");

	printf("Inorder\n");
	Inorder(root);
	printf("\n");

	printf("Postorder\n");
	Postorder(root);
	printf("\n");

	free(node);

	return 0;
}

void Preorder(int id){
	printf(" %d",id);
	if(node[id].l != -1) Preorder(node[id].l);
	if(node[id].r != -1) Preorder(node[id].r);
}

void Inorder(int id){
	if(node[id].l != -1) Inorder(node[id].l);
	printf(" %d",id);
	if(node[id].r != -1) Inorder(node[id].r);
}

void Postorder(int id){
	if(node[id].l != -1) Postorder(node[id].l);
	if(node[id].r != -1) Postorder(node[id].r);
	printf(" %d",id);
}

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

#define rep(i, n) for (int i=0; i<(n); ++i)
using ll = long long;
using P = pair<int, int>;

int const MAX = 255;

int parent(int i) {
  return i / 2;
}
int left(int i) {
  return 2 * i;
}
int right(int i) {
  return 2*i + 1;
}

int main() {
  int n;
  int heap[MAX];
  cin >> n;
  rep(i,n) cin >> heap[i+1];

  for (int i=1; i<=n; ++i) {
    cout << "node " << i << ": key = " << heap[i] << ", ";
    if (parent(i) >= 1) cout << "parent key = " << heap[parent(i)] << ", ";
    if (left(i) <= n) cout << "left key = " << heap[left(i)] << ", ";
    if (right(i) <= n) cout << "right key = " << heap[right(i)] << ", ";
    cout << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3104
#include <iostream>
#include <string.h>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;


int main(){
    int a[5],k;
    for(int i = 0; i < 5; i++){
        cin >> a[i];
    }
    cin >> k;
    int min, max;
    min = 123;
    max = 0;
    for(int i = 0; i < 5; i++){
       if(min >= a[i]){
           min = a[i];
       }
       if(max <= a[i]){
           max = a[i];
       }
    }
    if(max - min > k){
        cout <<  ":(\n";
    }
    else{
        cout << "Yay!\n";
    }


    return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())

s = (input())

if s[k-1] is 'A':
	o = s[:k-1] + 'a' +s[k:] 
elif s[k-1] is 'B':
	o = s[:k-1] + 'b' +s[k:] 
elif s[k-1] is 'C':
	o = s[:k-1] + 'c' +s[k:] 

print(o)


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
ll mod = 1000000007;

const int nmax = 40, abmax = 10, INF = 1000000;
int a[nmax], b[nmax], c[nmax];
int dp[nmax+1][nmax*abmax+1][nmax*abmax+1];

int main() {
    int n, ma, mb;
    cin >> n >> ma >> mb;
    rep(i, n) {
        cin >> a[i] >> b[i] >> c[i];
    }
    rep(i, n+1) {
        for(int ca = 0; ca <= nmax*abmax; ca++){
            for(int cb = 0; cb <= nmax*abmax; cb++){
                dp[i][ca][cb] = INF;
            }
        }
    }

    dp[0][0][0] = 0;
    rep(i, n) {
        for(int ca = 0; ca <= nmax*abmax; ca++) {
            for(int cb = 0; cb <= nmax*abmax; cb++) {
                if(dp[i][ca][cb] == INF) {
                    continue;
                }
                dp[i+1][ca][cb] = min( dp[i+1][ca][cb], dp[i][ca][cb] );
                dp[i+1][ca+a[i]][cb+b[i]] = min( dp[i+1][ca+a[i]][cb+b[i]], dp[i][ca][cb]+c[i] );
            }
        }
    }

    int ans = INF;
    for(int ca = 1; ca <= nmax*abmax; ca++) {
        for(int cb = 1; cb <= nmax*abmax; cb++) {
            if(ca*mb == cb*ma) {
                ans = min(ans, dp[n][ca][cb]);
            }
        }
    }
    if(ans == INF) {
        ans = -1;
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 25984
#include<iostream>
#include<queue>
using namespace std;
int x[9][9], dp[9][9][9][9], dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int px[3], py[3], H, W; queue<pair<int, int> >Q;
int main() {
	while (true) {
		for (int i = 0; i < 6561; i++) {
			x[i / 729][i % 9] = 1; dp[i / 729][(i / 81) % 9][(i / 9) % 9][i % 9] = 1 << 30;
		}
		cin >> W >> H; if (H == 0 && W == 0)break;
		for (int i = 1; i <= H; i++) {
			for (int j = 1; j <= W; j++) {
				cin >> x[i][j]; if (x[i][j] == 4) { px[0] = i; py[0] = j; x[i][j] = 0; }
				if (x[i][j] == 2) { px[1] = i; py[1] = j; x[i][j] = 0; }
				if (x[i][j] == 3) { px[2] = i; py[2] = j; x[i][j] = 0; }
			}
		}
		Q.push(make_pair(px[0] * 10 + py[0], px[1] * 10 + py[1])); dp[px[0]][py[0]][px[1]][py[1]] = 0;
		while (!Q.empty()) {
			int G = Q.front().first, H = Q.front().second; Q.pop();
			if (G == 31 && H == 23) {
				H = 23;
			}
			for (int i = 0; i < 4; i++) {
				int cx = G / 10, cy = G % 10; cx += dx[i]; cy += dy[i];
				if (x[cx][cy] == 1)continue;
				if (cx == H / 10 && cy == H % 10) {
					if (dp[G / 10][G % 10][cx + dx[i]][cy + dy[i]] > dp[G / 10][G % 10][cx][cy] + 1) {
						if (x[cx + dx[i]][cy + dy[i]] == 1)continue;
						dp[G / 10][G % 10][cx + dx[i]][cy + dy[i]] = dp[G / 10][G % 10][cx][cy] + 1;
						Q.push(make_pair(G, (cx + dx[i]) * 10 + (cy + dy[i])));
					}
				}
				else {
					if (dp[cx][cy][H / 10][H % 10] > dp[G / 10][G % 10][H / 10][H % 10]) {
						dp[cx][cy][H / 10][H % 10] = dp[G / 10][G % 10][H / 10][H % 10];
						Q.push(make_pair(cx * 10 + cy, H));
					}
				}
			}
		}
		int minx = 1 << 30; for (int i = 0; i < 81; i++)minx = min(minx, dp[i / 9][i % 9][px[2]][py[2]]);
		if (minx == 1 << 30) { minx = -1; }cout << minx << endl;
	}
	return 0;
}

Measured memory_bytes: 1240
import itertools as itr

D,G=map(int, input().split())
p=[list(map(int, input().split()))  for _ in range(D)]
b=list(itr.product(range(2),repeat=D))

ans=float('INF')

for i in range(len(b)):
    temp=0
    pnt=0
    for j in range(D):
        if b[i][j]==1:
            temp+=p[j][0]
            pnt+=(j+1)*100*p[j][0]
            pnt+=p[j][1]

    if pnt>=G:
        ans=min(ans,temp)
        
    else:
        for j in range(D):
            if b[i][-j-1]==0:
                for k in range(p[-j-1][0]-1):
                    temp+=1
                    pnt+=(D-j)*100
                    if pnt>=G:  
                        ans=min(ans,temp)
                        break
                break
                
print(int(ans))

Measured memory_bytes: 9248
import java.util.Scanner;

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

		Scanner sc = new Scanner(System.in);

		int N = Integer.parseInt(sc.next());
		int M = Integer.parseInt(sc.next());

		if(N == M) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

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

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

    string s;
    cin >> s;
    int n = s.size();

    vector<int> ans(n);

    REP(z, 2) {
        int count = 0;
        REP(i, n) {
            if (s[i] == 'R') count++;
            else {
                ans[i] += count / 2;
                ans[i - 1] += (count + 1) / 2;
                count = 0;
            }
        }
        // reverse して上記の R への操作を L にも行う
        reverse(ans.begin(), ans.end());
        reverse(s.begin(), s.end());
        REP(i, n) {
            if (s[i] == 'L') s[i] = 'R';
            else s[i] = 'L';
        }
    }

    REP(i, n) {
        cout << ans[i];
        if (i != n - 1) cout << ' ';
    }
    cout << '\n';
    return 0;
}


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

#define MAX 2000000000

long long Merge(std::vector<int>& List, int Left, int Mid, int Right);
long long MergeSort(std::vector<int>& List, int Left, int Right);

long long Merge(std::vector<int>& List, int Left, int Mid, int Right)
{
    int n1 = Mid - Left;
    int n2 = Right - Mid;
    long long Count = 0;
    
    std::vector<int> LList;
    LList.clear();
    for(int i = 0; i < n1; i++){
        LList.push_back(List[Left + i]);
    }
    
    std::vector<int> RList;
    RList.clear();
    for(int i = 0; i < n2; i++){
        RList.push_back(List[Mid + i]);
    }
    LList.push_back(MAX);
    RList.push_back(MAX);
    
    int j = 0;
    int k = 0;
    for(int l = Left; l < Right; l++){
        if(LList[j] <= RList[k]){
            List[l] = LList[j];
            j++;
        } else{
            List[l] = RList[k];
            k++;
            Count = Count + Mid + k - l - 1;
        }
    }
    return Count;
}

long long MergeSort(std::vector<int>& List, int Left, int Right)
{
    long long Count = 0;
    if(Left + 1 < Right){
        int Mid = (Left + Right) / 2;
        Count += MergeSort(List, Left, Mid);
        Count += MergeSort(List, Mid, Right);
        Count += Merge(List, Left, Mid, Right);
    }
    return Count;
}

int main(void){
    int Num, Temp;
    vector<int> List;
    List.clear();
    
    std::cin >> Num;
    
    for(int i = 0; i < Num; i++){
        std::cin >> Temp;
        List.push_back(Temp);
    }
    std::cout << MergeSort(List, 0, Num) << std::endl;
}

Measured memory_bytes: 3116
struct Read<R: std::io::BufRead> {
    stdin: R,
    v: Vec<String>,
    i: usize,
}
impl<R: std::io::BufRead> Read<R> {
    pub fn new(stdin: R) -> Self {
        Read {
            stdin: stdin,
            v: Vec::new(),
            i: 0,
        }
    }
    #[allow(dead_code)]
    pub fn read_one_line(&mut self) -> String {
        self.i = 0;
        self.v.clear();
        let mut buf = String::new();
        self.stdin.read_line(&mut buf).unwrap();
        buf.trim().to_owned()
    }
    pub fn read_line(&mut self) {
        self.i = 0;
        self.v.clear();
        let mut buf = String::new();
        self.stdin.read_line(&mut buf).unwrap();
        let buf = buf.trim().to_owned();
        let mut ws = buf.split_whitespace();
        loop {
            let x = ws.next();
            if x.is_none() {
                break;
            }
            let x = x.unwrap().to_owned();
            self.v.push(x);
        }
    }
    #[allow(dead_code)]
    pub fn read_a<T: std::str::FromStr>(&mut self) -> T {
        if self.i == self.v.len() {
            self.read_line();
        }
        let elem = &self.v[self.i];
        self.i += 1;
        elem.parse().unwrap_or_else(|_| panic!())
    }
}

use std::cmp;
use std::collections::HashMap;
fn main() {
    let stdin = std::io::stdin();
    let stdin = std::io::BufReader::new(stdin.lock());
    let mut r = Read::new(stdin);

    let n: i32 = r.read_a();

    let mut x = 0;
    for i in 1..100 {
        if 1000*i >= n {
            println!("{}", 1000*i - n);
            return;
        }
    }

}


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


int main() {
  string str;
  str = "abcdefghijklmnopqrstuvwxyz";
  char c; cin >> c;
  
  for(int i; i < 30; i++){
    if(str.at(i) == c){
      cout << str.at(i+1) << endl;
    break;
    }
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <list>
#include <algorithm>
#include <ctime>
#include <limits>
#include <iomanip>
#include <functional>
#include <array>
#include <climits>
#include <cmath>

using namespace std;
using ll = long long;
const ll MOD = (ll)1e9 + 7;

int main()
{
    int sum = 0;
    int mod_min = 10;
    int count = 0;
    for (int i = 0; i < 5; i++)
    {
        int a;
        cin >> a;
        sum += a / 10 * 10;
        int m = a % 10;
        if (m > 0)
        {
            count++;
            mod_min = min(m, mod_min);
        }
    }
    if (count > 0)
    {
        sum += (count - 1) * 10 + mod_min;
    }
    cout << sum;
    return 0;
}



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



int main() {
  int x;
  cin >> x;
  vector<int> p;
  p.push_back(2);
  for (int i = 3; i <= 100010; i++) {
    for (int j = 0; j < p.size(); j++) {
      if (i % p[j] == 0) break;
      if (p[j] * p[j] > i)  {
        p.push_back(i);
        break;
      }
    }
  }
  
  cout << *lower_bound(all(p), x) << endl;
  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define f first
#define s second
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define debug(x) cout << #x << " " << x << "\n"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll N = 1e2 + 3;
const ll M = 1e5 + 3;

ll n, k, w[N], v[N], dp[M], res;

ll _max(ll x, ll y, ll z) {
	return max(max(x, y), z);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for (ll i = 1; i <= n; ++i) cin >> w[i] >> v[i];
	
	dp[0] = 1;
	for (ll i = 1; i <= n; ++i) {
		for (ll j = k - w[i]; j >= 0; --j) {
			if (dp[j]) {
				dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
			}
		}
	}
	
	res = 0;
	for (ll i = 1; i <= k; ++i) res = max(res, dp[i] - 1);
	cout << res;
	
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
template<typename T>inline bool chkmin(T &x,T y){return (y<x)?(x=y,1):0;}
template<typename T>inline bool chkmax(T &x,T y){return (y>x)?(x=y,1):0;}
inline int read(){
	int x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x*f;
}
inline ll readll(){
	ll x;
	char c;
	int f=1;
	while((c=getchar())!='-' && (c>'9' || c<'0'));
	if(c=='-') f=-1,c=getchar();
	x=c^'0';
	while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
	return x*f;
}
const int maxn=5000+10,mod=1e9+7;
int Begin[maxn],sz[maxn],Next[maxn<<1],to[maxn<<1],e;
int dp[maxn][maxn],tmp[maxn],fac[maxn];
void add_edge(int x,int y){
	to[++e]=y;
	Next[e]=Begin[x];
	Begin[x]=e;
}
void dfs_init(int x,int ff){
	sz[x]=1;
	dp[x][1]=1;
	for(int i=Begin[x];i;i=Next[i]) if(to[i]!=ff){
		dfs_init(to[i],x);
		REP(j,0,sz[x]+sz[to[i]]) tmp[j]=0;
		REP(k,0,sz[x]) REP(j,0,sz[to[i]]) tmp[k+j]=(tmp[k+j]+(ll)dp[x][k]*dp[to[i]][j])%mod;
		sz[x]+=sz[to[i]];
		REP(j,0,sz[x]) dp[x][j]=tmp[j];
	}
	REP(i,2,sz[x]) dp[x][0]=(dp[x][0]-(ll)dp[x][i]*fac[i])%mod;
}
int main(){
	int n=read();
	REP(i,1,n-1){
		int x=read(),y=read();
		add_edge(x,y),add_edge(y,x);
	}
	fac[2]=1;
	REP(i,4,n) if(i%2==0) fac[i]=(ll)fac[i-2]*(i-1)%mod;
	dfs_init(1,0);
	printf("%d\n",(mod-dp[1][0])%mod);
	return 0;
}


Measured memory_bytes: 97280
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define forn(i,n1, n2) for (ll i = n1; i < n2; i++)
#define w(t) ll t;cin>>t;while(t--)
#define en "\n"
#define f first
#define s second
const ll mod = 1000000007;
using namespace std;
ll i, n, m, x, y, z, j, k, l, mn = LLONG_MAX, mx = 0, c, a[2000005], r, cnt = 0, sum = 0,p;
string str;
char ch;
set<ll> s;
map<ll, ll> mp;
vector<vector<ll>> g;
vector<ll> v;
char grid[60][60];
ll d[60][60];
bool vis[60][60];
ll dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
ll dy[] = {1, 0, -1, 0, 1, -1, 1, -1};
ll gcd(ll a , ll b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
ll comb(ll n , ll k)
{
    ll ans=1;
    for(j=1;j<=k;j++)
    {
        ans=(ans*(n-j+1))/j;
    }
    return ans;
}
ll power(ll x , ll y , ll p)
{
    x=x%p;
    if(x==0)return 0;
    ll res=1;
    while(y>0)
    {
        if(y%2==1){res=(res*x)%p;}
        y/=2;
        x=(x*x)%p;
    }
    return res;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>x;
    cout<<(power(10,x,mod)-2*power(9,x,mod)+power(8,x,mod)+2*mod)%mod;
    return 0;
}

Measured memory_bytes: 3640
let lcs x y =
  let m = String.length x in
  let n = String.length y in
  let dp = Array.make_matrix (m + 1) (n + 1) 0 in
  for i = 1 to m do
    for j = 1 to n do
      dp.(i).(j) <-
        if x.[i-1] = y.[j-1] then dp.(i-1).(j-1) + 1
        else
          let x = dp.(i-1).(j) in
          let y = dp.(i).(j-1) in
          max x y;
    done
  done;
  dp.(m).(n)

let () =
  let q = read_int () in
  for _ = 0 to q - 1 do
    let x = read_line () in
    let y = read_line () in
    lcs x y |> Printf.printf "%d\n"
  done

Measured memory_bytes: 18552
import bisect
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(N)]
STX.sort(key=lambda x:x[2])
ans=[-1]*Q
jump=[-1]*Q
D=[int(input()) for i in range(Q)]
for s,t,x in STX:
    l=bisect.bisect_left(D,s-x)
    r=bisect.bisect_left(D,t-x)
    while(l<r):
        k=jump[l]
        if k==-1:
            ans[l]=x
            jump[l]=r
            l+=1
        else:
            l=k
for i in range(Q):
    print(ans[i])


Measured memory_bytes: 106972
import java.util.*;
import java.io.*;

public class Main {
	public static void main (String[] args) {
	   InputReader in = new InputReader(System.in);
	   int n = in.readInt();
	   long k = in.readLong();
	   long range[] = new long[100005]; 
	   for(int i = 0; i<n; i++) {
		   int a = in.readInt();
		   int b = in.readInt();
		   range[a] += b; 
	   }
	  
	   for(int i = 1; i<100005; i++) {   
		   if(k <= range[i]) {
			   System.out.println(i);
			   return; 
		   }
		   k -= range[i]; 
	   }
	}
}

class InputReader {

	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	private SpaceCharFilter filter;

	public InputReader(InputStream stream) {
		this.stream = stream;
	}

	public int read() {
		if (numChars == -1)
			throw new InputMismatchException();
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (numChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	public long readLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			if (c < '0' || c > '9') {
				throw new InputMismatchException();
			}
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	
	public boolean isSpaceChar(int c) {
		if (filter != null)
			return filter.isSpaceChar(c);
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	public String next() {
		return readString();
	}

	public interface SpaceCharFilter {
		public boolean isSpaceChar(int ch);
	}
}

Measured memory_bytes: 22996
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		String s = sc.next();
		String output = s;
		
		char lastChar = s.charAt(s.length()-1);

		if(lastChar == 's') {
			System.out.println(output + "es");
		}
		else {
			System.out.println(output + "s");
		}
		
		
	}
}

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

int n,ans = 0;
int now = -2e9;
vector<pair<int,int>> v;

int main(){
  cin >> n;
  rep(i,n){
    ll x,l = 0; cin >> x >> l;
    v.push_back(make_pair(x+l,x-l));
  }    
  sort(v.begin(),v.end());
    
  rep(i,n){
    if(v[i].second < now) continue;
      else{
        now = v[i].first;
        ans++;
      }
  }
  cout << ans << endl;
}

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

int main(int argc, char *argv[]) {
  // read inputs
  char cs[5];
  scanf("%s", cs);

  // count each letter
  int cnts[26] = {};
  for (int i = 0; i < 4; i++) {
    cnts[cs[i] - 'A']++;
  }

  // solve
  int ok = 1;
  for (int i = 0; i < 26; i++) {
    if (cnts[i] != 2 && cnts[i] != 0) {
      ok = 0;
    }
  }

  if (ok) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  
  return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<int> V(N);
    rep(i,N) cin >> V.at(i);
    int cnt = 0;
    for (int i = 1; i < V.size() - 1; i++) {
        int a, b, c;
        a = V[i - 1];
        b = V[i];
        c = V[i + 1];
        if ((a > b && b > c) || (a < b && b < c)) cnt++;
    }
    cout << cnt << endl;
}


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

typedef struct{
  int num,sol,rank;
}set_c;

bool asc( const set_c& left , const set_c& right ){
  return left.sol>right.sol;
}

int main(){

  int key;
  vector< set_c > dat;
  set_c work;

  while(scanf("%d,%d",&work.num,&work.sol) , work.num!=0||work.sol!=0){
    work.rank=0;
    dat.push_back(work);
  }
  
  sort(dat.begin(),dat.end(),asc);
  

  //Rank
  int r=1;
  dat[0].rank=1;
  for(int i=1; i<(int)dat.size(); i++){
    if(dat[i].sol==dat[i-1].sol){
      dat[i].rank=r;
    }
    else{
      dat[i].rank = ++r;
    }
  }


  while(cin>>key){
    for(int i=0; i<(int)dat.size(); i++){
      if(dat[i].num == key ){
	cout << dat[i].rank << endl;
	break;
      }
    }
  }


  return 0;
}

Measured memory_bytes: 1264
#include <iostream>
#include <cstdio>
using namespace std;
int x, n;
int a[110], cnt[110];
int main() {
	cin >> x >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++;
	int i = 0;
	while (1) {
		if (!cnt[x - i]) {
			cout << x - i;
			return 0;
		} else if (!cnt[x + i]) {
			cout << x + i;
			return 0;
		} else {
			i++;
		}
	}
	return 0;
}

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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=Int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}


template<typename TV, const Int N> void read_tuple_impl(TV&) {}
template<typename TV, const Int N, typename Head, typename... Tail>
void read_tuple_impl(TV& ts) {
  get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));
  read_tuple_impl<TV, N+1, Tail...>(ts);
}
template<typename... Ts> decltype(auto) read_tuple(size_t n) {
  tuple<vector<Ts>...> ts;
  for(size_t i=0;i<n;i++) read_tuple_impl<decltype(ts), 0, Ts...>(ts);
  return ts;
}

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  Int n;
  cin>>n;

  auto [xs,ys]=read_tuple<Int, Int>(n);

  Int ans=0;
  set<Int> us,vs;
  for(Int i=0;i<n;i++){
    us.emplace(xs[i]+ys[i]);
    vs.emplace(xs[i]-ys[i]);

    chmax(ans,abs((xs[i]+ys[i])-*us.begin()));
    chmax(ans,abs((xs[i]+ys[i])-*us.rbegin()));

    chmax(ans,abs((xs[i]-ys[i])-*vs.begin()));
    chmax(ans,abs((xs[i]-ys[i])-*vs.rbegin()));
  }

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


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

bool revp2(const pair<ll,ll>&a,const pair<ll,ll>&b){return a.first>b.first;}
bool revp3(const pair<ll,ll>&a,const pair<ll,ll>&b){if(a.first==b.first)return a.second<b.second;
return a.first>b.first;}

int main()
{
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    ll a,b,c,x,y,s=INT_MAX;
    cin>>a>>b>>c>>x>>y;
    s=min(s,((ll)(x*a)+(ll)(y*b)));
    s=min(s,(ll)(max(x,y)*2ll*c));
    if(x>y)s=min(s,(ll)((x-y)*a)+(ll)(min(x,y)*2ll*c));
    else s=min(s,(ll)((y-x)*b)+(ll)(min(x,y)*2ll*c));
    cout<<s;

}


Measured memory_bytes: 3592
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
int main()
{
	int a=gi(),b=gi(),c=gi(),d=gi();
	LL p=4LL*gi(),ans=0;
	if (d<2*c&&d<4*b&&d<8*a) {
		ans+=1LL*(p/8)*d;
		p%=8;
	}
	if (c<2*b&&c<4*a) {
		ans+=1LL*(p/4)*c;
		p%=4;
	}
	if (b<2*a) {
		ans+=1LL*(p/2)*b;
		p%=2;
	}
	ans+=1LL*p*a;
	printf("%lld\n",ans);
	return 0;
}


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

int main(){
	int n;
	cin >> n;
	for(int i=0; i<n; i++){
		int a;
		cin >> a;
		if(a%2==0){
			if(a%3!=0 and a%5!=0){
				cout << "DENIED" << endl;
				return 0;
			}
		}
	}
	cout << "APPROVED" << endl;
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1ll, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
int main(void) {
	int c = 0, ans = 0;
	int k, _n;
	cin >> _n;
	for (int n = 3; n <= _n; n += 2) {
		c = 0;
		k = (int)sqrt(n);
		rep(i, 1, k + 1) {
			if (n % i == 0)c += (k * k == n ? 1 : 2);
		}
		if (c == 8)ans++;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3708
#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,ans,num;
bool f[200010];
vector<int> v[200010];
void dfs(int x){
	ans=max(ans,num);
	for (int i=0;i<v[x].size();i++)
		if (f[v[x][i]]==0){
			f[v[x][i]]=1;num++;
			dfs(v[x][i]);
		}
	return ;
}
int main(){
	cin>>n>>m;
	for (int i=0;i<m;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for (int i=1;i<=n;i++)
		if (f[i]==0){
			f[i]=1;num=1;
			dfs(i);
		}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 20892
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>

typedef long long ll;
const ll LL_MAX (1LL<<60);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    ll n;
    cin >> n;
    vector<ll> a(n);

    rep(i,0,n)
        cin >> a[i];

    ll k(1), cnt(0);
    rep(i,0,n)
        if (a[i] == k) cnt++, k++; 

    if (cnt==0) cout << -1 << endl;
    else cout << n-cnt << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int main(){
  int K,X;
  cin>>K>>X;

  if(500*K>=X) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

  return 0;
}


Measured memory_bytes: 256
//agc037_a_dp.cpp
//Sat Aug 17 22:04:24 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int dp[s.length()][2];
	for (int i=0;i<s.length();i++){
		dp[i][0] = 0;
		dp[i][1] = 0;
	}

	if (s[0]==s[1]){
		dp[0][0]=1;
		dp[0][1]=0;
		dp[1][0]=1;
		dp[1][1]=1;
	}else{
		dp[0][0]=1;
		dp[0][1]=0;
		dp[1][0]=2;
		dp[1][1]=1;
	}

//	cout << dp[0][0]<<" " << dp[0][1]<<endl;
//	cout << dp[1][0]<<" " << dp[1][1]<<endl;

	for (int i=2;i<s.length();i++){
		if (s[i]!=s[i-1]){
			dp[i][0]=dp[i-1][0]+1;
			dp[i][1]=dp[i-2][0]+1;
		}else{
			dp[i][0]=dp[i-1][1]+1;
			dp[i][1]=dp[i-2][0]+1;
		}
//	cout << dp[i][0]<<" " << dp[i][1]<<endl;
	}

	cout << max(dp[s.length()-1][0],dp[s.length()-1][1])<< endl;
//	printf("%.4f\n",ans);
}

Measured memory_bytes: 2180
H, W, K = map(int, input().split())
dp = [[0 for i in range(W)] for j in range(H+1)]
mod = 10**9+7
dp[0][0] = 1

if W == 1:
    print(1)
else:
    for k in range(H):
        for i in range(2**(W-1)):
            b = format(i, "0{}b".format(W-1))
            flag = 1
            for j in range(len(b)-1):
                if b[j+1] == "1" and b[j] == "1":
                    flag = 0
                    break
            if flag == 0:
                continue

            for j in range(len(b)):
                if flag == 0:
                    flag = 1
                    continue
                if b[j] == "1":
                    dp[k+1][j+1] += dp[k][j]
                    dp[k+1][j] += dp[k][j+1]
                    dp[k+1][j+1] %= mod
                    dp[k+1][j] %= mod
                    flag = 0
                else:
                    dp[k+1][j] += dp[k][j]
                    dp[k+1][j] %= mod
            if b[-1] == "0":
                dp[k+1][-1] += dp[k][-1]
                dp[k+1][-1] %= mod
    print(dp[H][K-1])


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
ll h[100005];

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lld",&h[i]);
	}
	bool flag=true;
	h[0]--;
	for(int i=1;i<n;i++){
		if(h[i-1]>h[i])flag=false;
		else{
			if(h[i-1]<h[i]){
				h[i]--;
			}
		}
	}
	printf("%s\n",flag?"Yes":"No");
	return 0;
}


Measured memory_bytes: 1024
/*input
3
21 -11
81234 94124 52141
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(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())
#ifdef leowang
#define debug(...) do{\
	fprintf(stderr,"%s - %d : (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
	_DO(__VA_ARGS__);\
}while(0)
template<typename I> void _DO(I&&x){cerr<<x<<endl;}
template<typename I,typename...T> void _DO(I&&x,T&&...tail){cerr<<x<<", ";_DO(tail...);}
#else
#define debug(...)
#endif
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
	out<<'('<<P.F<<','<<P.S<<')';
	return out;
}
//}}}
const ll maxn=300005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const double PI=acos(-1);
//const ll p=880301;
//const ll P=31;

ll mypow(ll a,ll b){
	ll res=1LL;
	while(b){
		if(b&1) res=res*a%MOD;
		a=a*a%MOD;
		
		b>>=1;
	}
	return res;
}

int main()
{
	IOS;
	int n;
	cin>>n;
	int T,A;
	cin>>T>>A;

	double bst=100000;
	int idx=-1;

	REP(i,n){
		int tmp;
		cin>>tmp;
		double tm=T-tmp*0.006;
		if(abs(tm-A)<abs(bst-A)){
			idx=i;
			bst=tm;
		}
	}
	cout<<idx+1<<'\n';
	return 0;
}


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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1'000'000'000ll + 7;
//const i64 smod = 998244353ll;
//const i64 inf = 1'000'000'000'000'000'000ll + 7;
//const i64 inf = 1'000'000'007;

const long double eps = 1e-8;

const i64 MAXN = 300'000 + 6;
const i64 MAXM = 502;

i64 n;

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    i64 h1, m1, h2, m2, a;
    cin >> h1 >> m1 >> h2 >> m2 >> a;

    i64 t = (h2 - h1) * 60 + (m2 - m1);
    i64 R = max(t - a, 0ll);
    cout << R << endl;

    return 0;
}

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

N, M = map(int, input().split())
A = list(map(int, input().split()))

cost = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
cd = [(a, cost[a]) for a in A]
cd.sort(key=lambda x: x[0], reverse=True)

dp = [0] + [-1] * N
for i in range(1, N + 1):
    for a, c in cd:
        if i - c >= 0 and 0 <= dp[i - c]:
            dp[i] = max(dp[i], dp[i - c] + 1)

ans, i = [], N
for _ in range(dp[-1]):
    for a, c in cd:
        if i - c >= 0 and dp[i - c] == dp[i] - 1:
            ans.append(a)
            i = i - c
            break

print(''.join(map(str, ans)))


Measured memory_bytes: 3796
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n)  for (int i = 0; i < (int) (n); i++)
#define REP1(i, n) for (int i = 1; i <= (int) (n); i++)
#define all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
using ll = long long;
const ll mod  = 1e9 + 7;
const int INF = 2e9;
using pint = pair <int, int>;

int main() {
  int k;
  cin >> k;
  int a[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
  cout << a[k - 1] << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int m,n;
int a,b;
vector<int> v[100001];
int t[100001];
void dfs(int a,int k)
{
	if(t[a]!=0)
		return;
	t[a]=k;
	for(int i=0;i<v[a].size();i++)
		dfs(v[a][i],k);
	return;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	int k=0;
	for(int i=1;i<=n;i++)
	{
		if(t[i]==0)
		{
			k++;
			dfs(i,k);
		}
	}
	cout<<k-1<<endl;
	return 0;
}


Measured memory_bytes: 9980
<?php
fscanf(STDIN, '%d %d %d', $cnt, $def, $solve);
$points = array_fill(1, $cnt, $def-$solve);
for ($i=0; $i < $solve; $i++) { 
    fscanf(STDIN, '%d', $idx);
    $points[$idx]++;
}
foreach ($points as $value) {
    if ($value > 0) {
        echo "Yes\n";
    } else {
        echo "No\n";
    }
}

Measured memory_bytes: 9080
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	int INF = 1 << 28;
	//long INF = 1L << 62;
	double EPS = 1e-10;
	int n, max;
	int[] items;
	boolean[] use;

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			n = sc.nextInt(); max = sc.nextInt();
			if((n|max) == 0) break;
			
			items = new int[n];
			for(int i=0;i<n;i++) items[i] = sc.nextInt();
			
			use = new boolean[max+1];
			use[0] = true;
			
			for(int i=0;i<=max;i++) for(int j=0;j<n;j++) if(i + items[j] <= max)
				use[i + items[j]] |= use[i];
			int ans = ans();
			System.out.println((ans < 0? "NA": ans));
		}
	}
	
	int ans() {
		for(int i=max;i>=1;i--) if(use[i] && isPrime(i))
			return i;
		return -1;
	}
	
	boolean isPrime(int x) {
		for(long j=2;j*j<=x;j++) if(x%j == 0) return false;
		return true;
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

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

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

using namespace std;

int main()
{
    string s;
    while (getline(cin, s), s != "END OF INPUT") {
        int cnt = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            cnt++;
            if (s[i] == ' ') {
                cout << cnt-1;
                cnt = 0;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 3192
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    int k;
    cin >> k;
    int m = 0;
    rep(i, k){
        m *= 10;
        m += 7;
        m %= k;
        if(m == 0){
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int d,a,b,c=1;
  cin>>a>>b;
  d=b;
  while(b>0)
  {
  	b/=10;
  	c*=10;
   }
   a=a*c;
   a+=d;
   int e=sqrt(a);
   if(e*e==a)
   {
   	cout<<"Yes"<<endl;
   	return 0;
	   }	
	else
	  cout<<"No"<<endl;
	  return 0;   
}

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 END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  int n,k; cin >> n >> k;
  vector<ll> a,sub;
  for (int i = 0; i < n; ++i) {
    ll t; cin >> t;
    a.pb(t);
  }

  for (int i = 0; i < n; ++i) {
    ll sum = a[i];
    sub.pb(sum);
    for (int j = i+1; j < n; ++j) {
      sum += a[j];
      sub.pb(sum);
    }
  }
  sortd(sub);

  vector<ll> two;
  ll t = 1;
  rep(i,42) {
    two.pb(t);
    t *= 2;
  }

  vector<ll> tmp = sub;
  ll ans = 0;
  for (int i = two.size() - 1; i >= 0; --i) {
    vector<ll> now;
    ll len = tmp.size();
    for (int j = 0; j < len; ++j) {
      ll tar = tmp[j];
      ll tt = tar & two[i];
      if (tt == two[i]) {
        now.pb(tar);
      }
    }
    // cout << now.size() << endl;
    if (now.size() >= k) {
      tmp = now;
      ans += two[i];
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 10104
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;

signed main(){
    
    int A, B, T; cin >> A >> B >> T;
    cout << (T / A) * B << endl;   
    return 0;
}


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



namespace Test1 {

    class ClassMain {




        public static void Main(String[] args) {
            string line;
            while ((line = Console.ReadLine()) != null) {
                string[] strs = line.Split(' ');
                int n = int.Parse(strs[0]);
                int m = int.Parse(strs[1]);
                int a = int.Parse(strs[2]);

                if (n == 0) { break; }

                int[] amida = Enumerable.Range(0, n).ToArray();
                amidaline[] lines = new amidaline[m];
                //amida Store
                for (int i = 0; i < m; i++) {
                    strs = Console.ReadLine().Split(' ');
                    lines[i] = new amidaline(int.Parse(strs[0]),
                        int.Parse(strs[1]),int.Parse(strs[2]));
                }

                //amida Process
                for (int height = 1000; height >= 1; height--) {
                    for(int lineN = 0; lineN < m ; lineN++){
                        amidaline a_line = lines[lineN];
                        if (a_line.h == height) {
                            a_line.swapAmida(amida);
                        }
                    }
                }
                int seikai = -1;
                for (int i = 0; i < n; i++) {
                    if (amida[i] == a - 1) { seikai = i; break; }
                }
                Console.WriteLine(seikai+1);


                    






            }
        }

        class amidaline {
            public int h;
            public int p;
            public int q;
            internal amidaline(int h, int p, int q) {
                this.h = h;
                this.p = p;
                this.q = q;
            }
            public void swapAmida(int[] amida){
                //Console.Write(string.Join(",",amida)+" -> ");
                int tmp = amida[p - 1];
                amida[p - 1] = amida[q - 1];
                amida[q - 1] = tmp;
                //Console.WriteLine(string.Join(",", amida));
            }

        }


    }
}

Measured memory_bytes: 6276
#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;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define int ll
#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

void solve() {
    int s, w;
    cin>>s>>w;
    if(w >= s) cout<<"unsafe";
    else cout<<"safe";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (LOCAL) {
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
        freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
    }
    int t = 1;
    //cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
int n;
string s;
cin>>n>>s;
int ans=0;
for(int i=1;i<=n-1;i++)
{
set<char> x(s.begin(),s.begin()+i),y(s.begin()+i,s.end());
int t=0;
for(char c='a';c<='z';c++)
if(x.count(c)&&y.count(c))t++;
ans=max(ans,t);
}
cout<<ans;
}

Measured memory_bytes: 256
#include <iostream>
#define rep(S, L) for (int i = S; i < L; ++i)
using namespace std;

int main() {
  long long a, b, c, d;
  cin >> a >> b >> c >> d;
  long long ans = 0;
  ans = max(a * c, a * d);
  ans = max(ans, b * c);
  ans = max(ans, b * d);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3192
N = int(input())
A = list(map(int, input().split()))


def judge(k):
  cnt = sum(max((a+k+1)//(N+1),0) for a in A)
  return cnt <= k

if judge(0):
  print(0)
  exit(0)

low = 0
high = 10**18

while low + 1 < high:
  mid = (low+high)//2
  if judge(mid):
    high = mid
  else:
    low = mid

r = high

for i in range(max(r-N*N,0),r):
  if judge(i):
    r = i
    break

print(r)

Measured memory_bytes: 3064