akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
  long long int n;
  scanf("%lld",&n);
  long long int i;
  long long int a;
  long long int ans = 0;
  for(i=0;i<n;i++) {
    scanf("%lld",&a);
    if(a%2==1) {
      ans = 1;
    }
  }
  if(ans > 0) {
    printf("first\n");
  } else {
    printf("second\n");
  }


  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define PI 3.14159265358979323846
#define int long long
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr long long INFL = numeric_limits<long long>::max() / 2;
constexpr int MOD = 1000000007;
using Graph = vector<vector<int>>;

const int dx[2]={0,1};
const int dy[2]={1,0};



signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int H,W;
    cin>>H>>W;
    string S[H];
    rep(i,H) cin>>S[i];

    vector<vector<int>> dist(H,vector<int>(W,INF));
    int sh=0,sw=0,gh=H-1,gw=W-1;
    if(S[0][0]=='#') dist[0][0]=1;
    else dist[0][0]=0;

    queue<pair<int,int>> q;
    q.push(make_pair(0,0));

    while(!q.empty()){
        pair<int,int> v=q.front();
        q.pop();
        int h=v.first;
        int w=v.second;
        rep(i,2){
            int nh=h+dx[i];
            int nw=w+dy[i];
            if(nh>=H || nw>=W) continue;

            int x=0;
            if(S[h][w]=='.'&&S[nh][nw]=='#') x++;
            if(dist[nh][nw]>dist[h][w]+x){
                dist[nh][nw]=dist[h][w]+x;
                q.push(make_pair(nh,nw));
            }
        }

    }
    cout << dist[gh][gw] << endl;


}


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

int main(){
  char o[56];
  char e[56];
  int no,ne;
  int i,j,k;

  scanf("%s %s", o, e);

  no = strlen(o);
  ne = strlen(e);

  j = 0;
  k = 0;
  for(i = 1;i <= no + ne;i++){
    if(i % 2 == 0) printf("%c", e[j++]);

    else printf("%c", o[k++]);
  }

  printf("\n");

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;cin>>n;
	int sum=0;
	stringstream ss;
	string tmp;
	for(int i=1;i<=n;i++){
		ss.str("");
		ss.clear();
		ss<<i;
		ss>>tmp;
		if((int)tmp.size()%2==1)sum++;
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 256
import sys

# 関数 solve は，もちろん，問題に応じて書き換える
def solve (N):
    s=0
    for b in str(N):

        s = s + int(b)
    if N % s ==0:
        return 'Yes'
    else:
        return 'No'
   

# ここから下は，入力・出力形式が同じであれば，変えなくて良い．
def readQuestion():
    line = sys.stdin.readline().rstrip()
    return int(line)

def main():
    n = readQuestion()
    answer = solve(n)
    print(answer)
    
if __name__ == '__main__':
    main()

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

const int N=1e6+10;

int main(){
	int n;
	cin>>n;
	if(n==3){
		cout<<2<<endl;
		printf("1 3\n2 3\n");return 0;
	}
	vector<pair<int,int>>E;
	if(n&1){
		for(int i=1;i<=n/2;i++){
			int j=n-i;
			for(int l=1;l<i;l++){
				int r=n-l;
				E.push_back(make_pair(i,l));
				E.push_back(make_pair(i,r));
				E.push_back(make_pair(j,l));
				E.push_back(make_pair(j,r));
			}	
		}
		for(int i=1;i<n;i++)
			E.push_back(make_pair(i,n));
	}
	else{
		n++;
		for(int i=1;i<=n/2;i++){
			if(n==5&&i==2)break;
			int j=n-i;
			int l=i+1,r;
			if(l>n/2)l=1;
			r=n-l;
			E.push_back(make_pair(i,l));
			E.push_back(make_pair(i,r));
			E.push_back(make_pair(j,l));
			E.push_back(make_pair(j,r));
		}
	}
	cout<<E.size()<<endl;
	for(auto x:E)
		cout<<x.first<<" "<<x.second<<endl;
	
	
		
}
/*

1 2 1 2


1 2 3 3 2

1 2 2 3 3


*/


Measured memory_bytes: 384
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define SIZE_STRING 10
#define NUM_STRING 3
#define SIZE_RESULT 4

int main(void)
{
	/* 変数宣言 */
	char cS[NUM_STRING][SIZE_STRING];	// 入力文字列
	char cResult[SIZE_RESULT];			// 結果文字列
	int iLoop;							// ループカウンタ
	
	/* 変数初期化 */
	memset(cS, 0x00, sizeof(cS));
	memset(cResult, 0x00, SIZE_RESULT);
	
	/* 文字列読み込み */
	for(iLoop = 0; iLoop < NUM_STRING; iLoop++)
	{
		scanf("%s", cS[iLoop]);
	}
	
	/* 入力文字列の先頭文字を結果文字列へコピー */
	for(iLoop = 0; iLoop < NUM_STRING; iLoop++)
	{
		cResult[iLoop] = *cS[iLoop];
	}
	
	/* 結果文字列を大文字に変換 */
	for(iLoop = 0; iLoop < NUM_STRING; iLoop++)
	{
		cResult[iLoop] = toupper(cResult[iLoop]);
	}
	
	/* 結果出力 */
	printf("%s\n", cResult);
	
	return 0;
}

Measured memory_bytes: 128
Scanf.scanf "%d %d" (fun n xx ->
    let rec gcd a b = if b = 0 then a else gcd b (a mod b) in
    let x = Array.init n (fun _ -> Scanf.scanf " %d" (fun x -> abs(x - xx))) in
    let rec loop i acc =
        if i = n then acc else loop (i + 1) (gcd acc x.(i))
    in
    loop 1 x.(0) |> Printf.printf "%d\n"
)

Measured memory_bytes: 4736
#include<bits/stdc++.h>
#define fu(a,b) for(int i=a;i<b;i++)
#define fv(a,b) for(int j=a;j<b;j++)
#define ll long long
#define dl double
using namespace std;


int main()
{
	int n,W;
	cin>>n>>W;
	int w;
	ll val;
	ll dp[n+1][W+1];
	
	fu(0,n+1)
	fv(0,W+1)
	dp[i][j]=0;
	
	fu(1,n+1)
	{
		cin>>w>>val;
		{
			fv(1,W+1)
			{
				if(j>=w)
				{
					dp[i][j]=max(dp[i-1][j],val+dp[i-1][j-w]);
				}
				else
				{
					dp[i][j]=dp[i-1][j];
				}
			}
		}
	}
	
	cout<<dp[n][W];
}

Measured memory_bytes: 79104
from sys import stdin

if __name__ == '__main__':
    N, K = [int(x) for x in stdin.readline().rstrip().split()]
    P = [int(x) for x in stdin.readline().rstrip().split()]
    E = [((p*(p+1))/2)/p  for p in P]
    maxe = sum(E[0:0+K])
    frontval = maxe
    for i in range(1, N-K+1):
        val = frontval - E[i-1] + E[i+K-1]
        frontval = val
        if maxe < val:
            maxe = val
    print(maxe)

Measured memory_bytes: 25188
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)    for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define rrep(i, n)   for(int i=(n-1); i>=0; --i)
#define all(v)       v.begin(), v.end()
#define rall(v)      v.rbegin(), v.rend()
#define int          long long
template<typename T>
using vv  =  vector<vector<T>>;
using vi  = vector<int>;
using vvi = vector<vector<int>>;
using P   = pair<int, int>;
using ll  = long long;
constexpr ll INF = 1LL << 60;

signed main(){

    int a, b;
    cin >> a >> b;

    cout << a * b << endl;

    return 0;
}


Measured memory_bytes: 3620
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.time.LocalTime;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;


public class Main {

    public static void main(String[] args) {
    
    	FastScanner scan = new FastScanner();
    	
    	int n = scan.nextInt();
    	long count = 0;
    	
    outer:	for(int i = 1; i<n; i++) {
    		for(int j=1; j<n; j++) {
    			if(i * j < n) count++;
    			else continue outer;
    		}
    	}
    	
    	System.out.println(count);
    	
    }

    static class FastScanner{
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
    	String next() {
    		while(!st.hasMoreTokens())
    			try {
    				st = new StringTokenizer(br.readLine());
    			} catch (IOException e){
    				e.printStackTrace();
    			}
    		return st.nextToken();
    	}
    	
    	int nextInt() {
    		return Integer.parseInt(next());
    	}
    	
    	int [] readArray(int n) {
    		int [] a = new int[n];
    		for(int i=0; i<n ; i++) a[i] = nextInt();
    		return a;
    	}
    	
    	long nextLong() {
    		return Long.parseLong(next());
    	}
    	
    	
    }
    
   
}



Measured memory_bytes: 33348
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int (x); SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long (x); SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
#define M0(x) memset(x,0,sizeof(x))
#define FILL(x,y) memset(x,y,sizeof(x))
#define MM(x) memset(x,-1,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
///////////////////////////////////////////////
const ll MOD = 1000000007;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
///////////////////////////////////////////////

int main(){
    ll A,B,C;
    cin >> A >> B >> C;
    ll ans = min({A*B*(-C/2 + (C-C/2)), B*C*(-A/2 + (A-A/2)),C*A*(-B/2 + (B-B/2))});
    cout << ans << endl;
}


Measured memory_bytes: 256
# row = [int(x) for x in input().rstrip().split(" ")]
# n = int(input().rstrip())
# s = input().rstrip()

def resolve():
    import sys
    input = sys.stdin.readline

    n = int(input().rstrip())

    s_list = [input().rstrip() for _ in range(n)]

    from collections import Counter
    c = Counter(s_list)

    max_count = c.most_common()[0][1]

    words = [word for word, count in c.most_common() if count == max_count]
    words.sort()
    print("\n".join(words))




if __name__ == "__main__":
    resolve()


Measured memory_bytes: 149204
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-7;
typedef long long ll;
const ll maxx=2e5+10;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
ll a[maxx],b[maxx],cnt;
vector<ll> u,d,c;
int n;
int sign(ll x){
    return x>=0?1:-1;
}
ll cal(ll x){
    ll ans=0;
    for(auto t:c){
        if(t<0){
            if(x>=0){
                ans+=(int)(upper_bound(d.begin(),d.end(),(abs(x)/abs(t)))-d.begin());
                ans+=u.size();
            }else{
                ans+=u.size()-(int)(lower_bound(u.begin(),u.end(),(abs(x)+abs(t)-1)/abs(t))-u.begin());
            }
        }else{
            if(x>=0){
                ans+=(int)(upper_bound(u.begin(),u.end(),(x/t))-u.begin());
                ans+=d.size();
            }else{
                ans+=d.size()-(int)(lower_bound(d.begin(),d.end(),((abs(x)+abs(t)-1)/abs(t)))-d.begin());
            }
        }
        if(t*t<=x) ans--;
    }
    ans/=2;
    if(x>=0){
        ans+=cnt*(n-cnt)+cnt*(cnt-1)/2;
    }
    return ans;
}
int main(){
    ll k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            cnt++; continue;
        }
        if(a[i]>0) u.push_back(a[i]);
        else d.push_back(-a[i]);
        c.push_back(a[i]);

    }
    sort(u.begin(),u.end());
    sort(d.begin(),d.end());
    ll l=-1e18,r=1e18;
    while(l<r){
        ll mid=(l+r)>>1;
        if(cal(mid)>=k) r=mid;
        else l=mid+1;
    }
    cout<<l<<endl;
}


Measured memory_bytes: 5604
#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
  int n;
  cin >> n;
  int a[n-1];
    for (int i=0; i<n; i++){
  cin >> a[i];
    }

  long long l;
  l=0;
  for (int i=1; i<n; i++){
 
     if (a[i]<a[i-1])
     { l += a[i-1]-a[i];
       a[i]=a[i-1];
     }
  }

  
 cout << l <<endl;
  return 0;
}


Measured memory_bytes: 4380
#include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

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

int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 };  // i<4:4way i<8:8way
int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n,m, sum = 0;
    cin >> n >> m ;
    vector<int> a(n);
    rep(i,n){
        cin >> a[i];
        sum += a[i];
    }
    int c = 0;
    rep(i,n){
        if(a[i]*(4*m) >= sum)c++;
    }
    if(c >= m)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main () {

  ll a, b;
  cin >> a;
  cin >> b;

  ll c = min(a, b); // small num
  ll d; // number of small num
  if (c == a) {
    d = b;
  }
  else {
    d = a;
  }

  REP(i, 0, d) {
    cout << c;
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a;
  cin >> a;
  
  string t;
  
  switch(a % 10)
  {
    case 2:
    case 4:
    case 5:
    case 7:
    case 9:
      t = "hon";
      break;
      
    case 0:
    case 1:
    case 6:
    case 8:
      t = "pon";
      break;
      
    case 3:
      t = "bon";
      break;
  }
  
  cout << t;
}

Measured memory_bytes: 3596
#include <iostream>
using namespace std;
int n;
int ans;
void saiki(int kai,int sum,int i) {
  if(sum == n) ans++;
  else if(kai < 4 && sum < n)
    for(int j=i;sum+j*j<=n;j++) saiki(kai+1,sum+j*j,j);
}

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

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

int main () {
  int a , b;
  cin >> a >> b;
  int N = b - a;
  int answer = 0;
  for(int i = 1; i < N + 1; i++){
    answer+=i;
  }
  cout << answer - b << endl;
}



Measured memory_bytes: 256
import bisect
import sys
A, B, Q = map(int, input().split())
INF = 10 ** 13
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
xs = [int(sys.stdin.readline()) for i in range(Q)]
for x in xs:
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

int main() {
source:
    ll n, m;
    cin >> n >> m;
    ll ans = n * (n - 1) / 2 + m * (m - 1) / 2;
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

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

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

vi g[N];
bool vis[N];
vi topo;

void dfs(int v) {
	vis[v] = 1;
	for(auto it : g[v]) {
		if(!vis[it]) {
			dfs(it);
		}
	}
	topo.pb(v);
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
	}
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			dfs(i);
		}
	}
	reverse(all(topo));
	int dp[n + 1] = {0};
	for(int i = 0; i < n; i++) {
		for(auto it : g[topo[i]]) {
			dp[it] = max(dp[it], dp[topo[i]] + 1);
		}
	}
	cout << *max_element(dp + 1, dp + n + 1);

	return 0;
}

Measured memory_bytes: 11864
import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        long n = in.nextLong();

        StringBuilder answer = new StringBuilder();
        while (n > 0) {
            n--;
            answer.append((char) ('a' + n % 26));
            n /= 26;
        }

        System.out.println(answer.reverse());
    }
}


Measured memory_bytes: 35712
n = int(input())
a = [int(i) for i in input().split()]

ptn = [3] + [0] * (max(a) + 1)
ans = 1
for i in a:
    ans *= ptn[i]
    ptn[i] -= 1
    ptn[i + 1] += 1

print(ans % 1000000007)


Measured memory_bytes: 13932
n = gets.to_i
p = gets.split.map(&:to_i)
c = 0

p.each do |i|
  if i > 0 && i < p.length - 1
    pp = [p[i-1], p[i], p[i+1]].sort
    c += 1 if pp[1] == p[i]
  end
end

puts c

Measured memory_bytes: 1788
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

using namespace std;

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

const ll mod = 1000000007;
const int inf = 1e9;
const long long INF = 1LL << 60;

int ans;
int w,h;

const int w_max = 60,h_max = 60;
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};
int v[h_max][w_max];
int f[h_max][w_max];


void dfs(int y,int x)
{
    if(v[y][x]){
        return ;
    }else{
        v[y][x] = true;
        for(int i = 0; i < 8; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(ny >= 0 && ny < h && nx >= 0 && nx < w && f[ny][nx] != 0 ){
                dfs(ny,nx);
            }
        }
    }
}

int main()
{
    while(true){
        cin >> w >> h;
        if(w == 0 && h == 0) break;
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> f[i][j];
                v[i][j] = false;
            }
        }
        ans = 0;
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(f[i][j] == 1){
                    if(!v[i][j]){
                        ans++;
                        dfs(i,j);
                    }
                }
            }
        }
        cout << ans << endl;
    }
} 


Measured memory_bytes: 3208
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
 
// Remove GCC optimizer for codechef
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
using namespace __gnu_pbds;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define endl "\n"
#define int long long
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
 
const int INF = 1e16;
const double PI = acos(-1);
const int N = 1e6 + 7;
int mod = 998244353;

const int maxn = 1e5 + 7;
vector<int> graph[maxn];
vector<int> topo;
int visited[maxn], dp[maxn];

void dfs(int u)
{
    visited[u] = 1;
    for(int &v: graph[u])
        if(!visited[v])
            dfs(v);
    topo.pb(u);
}

int32_t main()
{
    IOS;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        graph[u].pb(v);
    }
    for(int i = 1; i <= n; i++)
        if(!visited[i])
            dfs(i);
    int ans = -1;
    for(int i = 0; i < topo.size(); i++)
    {
        int u = topo[i];
        for(int &v: graph[u])
            dp[u] = max(dp[u], dp[v] + 1);
        ans = max(ans, dp[u]);
    }
    cout << ans << endl;
    return 0;
}

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

int main() {
  int N;
  string S;
  
  cin >> N;
  for(int i = 0;i < N;i++){
    cin >> S;
    if(S == "Y"){
      break;
    }
  }
  
  if(S =="Y"){
  cout <<"Four" << endl;
  }
  else{
  cout <<"Three" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(int i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef long long int ll;
typedef pair<ll,ll> Pi;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

string s;
vector<string> ans;
int alr[26];

bool check(string s1){
	//int flag=0;
	//if(s1=="acc")flag=1;
	REP(i,26)alr[i]=0;
	REP(i,s1.size()){
		if(!alr[s1[i]-'a']&&s1[i]!='a'){
			alr[s1[i]-'a']=1;
			s1[i]=s1[i]-1;
		}
	}
	//if(flag)cout<<s1<<" 3"<<endl;
	if(s.substr(0,s1.size())==s1)return true;
	else return false;
}

void dfs(string s1){
	if(!check(s1))return;
	if(s1.size()==s.size()){
		ans.push_back(s1);
		return;
	}
	if(s[s1.size()]!='z')dfs(s1+(char)(s[s1.size()]+1));
	dfs(s1+s[s1.size()]);
	return;
}

int main(){
	while(1){
		cin>>s;
		if(s=="#")break;
		ans.clear();
		dfs("");
		cout<<ans.size()<<endl;
		sort(ans.begin(),ans.end());
		if(ans.size()>10){
			REP(i,5){
				cout<<ans[i]<<endl;
			}
			REP(i,5){
				cout<<ans[ans.size()-5+i]<<endl;
			}
		}else{
			REP(i,ans.size()){
				cout<<ans[i]<<endl;
			}
		}
		
	}
	return 0;
}


Measured memory_bytes: 4356
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
template<class T> struct Matrix {
  int width, height;
  vector<vector<T>> v;
  constexpr Matrix(int w) : width(w), height(w), v(w, vector<T>(w, 0)) {};
  constexpr Matrix(int w, int h) : width(w), height(h), v(w, vector<T>(h, 0)) {};
  Matrix operator+(const Matrix& n) const { Matrix ans = v; return ans += n; }
  Matrix operator*(const Matrix& n) const { Matrix ans = v; return ans *= n; }
  Matrix& operator+=(const Matrix& rhs) {
    for (int i = 0; i < height; ++i)
      for (int j = 0; j < width; ++j)
        v[i][j] += rhs.v[i][j];
    return *this;
  }
  Matrix& operator*=(const Matrix& rhs) {
    Matrix<T> ans(height, rhs.width);
    for (int i = 0; i < height; ++i)
      for (int j = 0; j < rhs.width; ++j)
        for (int k = 0; k < width; ++k)
          ans[i][j] += v[i][k] * rhs.v[k][j];
    width = rhs.width;
    v = ans.v;
    return *this;
  }
  Matrix pow(ll N) {
    Matrix pow = *this, ans(width);
    for (int i = 0; i < width; ++i) ans[i][i] = 1;
    for (ll p = N; p > 0; p >>= 1, pow *= pow)
      if (p & 1) ans *= pow;
    return ans;
  }
  vector<T>& operator[](int i) { return v[i]; }
};

template<int MOD> struct MInt {
  long long val;
  constexpr MInt(long long val = 0) : val(val % MOD) { if (val < 0) val += MOD; }
  MInt operator+(const MInt& n) const { return MInt(val) += n; }
  MInt operator*(const MInt& n) const { return MInt(val) *= n; }
  MInt& operator+=(const MInt& n) { val = (val + n.val) % MOD; return *this; }
  MInt& operator*=(const MInt& n) { val = (val * n.val) % MOD; return *this; }
  friend ostream& operator<<(ostream& os, const MInt& n) { os<<n.val; return os; }
  friend istream& operator>>(istream& os, MInt& n) { os>>n.val; return os; }
};
constexpr int MOD = 1e9+7;
using mint = MInt<MOD>;

int main() {
  int in(N); ll in(K);

  Matrix<mint> A(N);
  rep(i, N) rep(j, N)
    cin >> A[i][j];

  A = A.pow(K);

  mint ans = 0;
  rep(i, N) rep(j, N)
    ans += A[i][j];

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


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
long long ret5(long long num){
  return num*num*num*num*num;
}
int main()
{
  int X;
  cin>>X;
  for(int i=-200;i<200;i++){
    for(int j=-200;j<200;j++){
      if(ret5(i)==X+ret5(j)){
        cout<<i<<" "<<j;
        return 0;
      }
    }
  }
  cout<<0;
  return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n;
	int dp[31];
	int i;
	while(1){
		cin>>n;
		if(n==0)	break;
		for(i=1;i<=n;i++){
			dp[i]=0;
		}
		dp[1]=1;
		dp[2]=1;
		dp[3]=1;
		for(i=1;i<=n;i++){
			for(int j=1;j<=3;j++){
				dp[i+j]+=dp[i];
			}
		}
		if(dp[n]<3650){
			cout<<"1"<<endl;
		}
		else{
			int ans=dp[n]/3650;
			if(dp[n]%3650!=0){
				ans++;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3044
#include "bits/stdc++.h"
using namespace std;

const int N=2e5+20;

int n,m,k,a[N],b[N],ans;
long long dpa[N],dpb[N];

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),dpa[i]=dpa[i-1]+a[i];
	for(int i=1;i<=m;i++) scanf("%d",&b[i]),dpb[i]=dpb[i-1]+b[i];

	for(int i=0;i<=n;i++)
	{
		if(dpa[i]>k) break;
		int j=upper_bound(dpb+1,dpb+m+1,k-dpa[i])-dpb-1;
		ans=max(ans,i+j);
	}

	cout<<ans;
}

Measured memory_bytes: 8376
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#define INF 1000000007
using namespace std;

int main(void){
	int n,temp;
	cin >> n;
	vector<int> a(13,0);
	for(int i=0; i<n; i++){
		cin >> temp;
		a[temp/400]++;
	}
	int mini=0,red=0;
	for(int i=0; i<=12; i++){
		if(a[i] && i<=7)mini++;
		else if(a[i])red+=a[i];
	}
	if(mini!=0){
		cout << mini << " " << mini+red << endl;
	}else {
		cout << min(1,red) << " " << red << endl;
	}
	return 0;
}

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

vector<int> search(vector<vector<int>> const& flr, int sx, int sy, int const R) {
    const int H = flr.size();
    const int W = flr[0].size();
    vector<int> res = {0};
    vector<vector<bool>> visited(H, vector<bool>(W));
    visited[sy][sx] = true;
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(make_pair(flr[sy][sx], sy*W+sx));
    while(!que.empty() && res.size() <= R) {
        P p = que.top();
        int y = p.second / W, x = p.second % W;
        que.pop();
        res.push_back(max(res.back(), p.first));
        int dx[4] = {0, 1, 0, -1},
            dy[4] = {1, 0, -1, 0};
        for(int i=0; i<4; ++i) {
            int ny = y + dy[i], nx = x + dx[i];
            if(ny < 0 || H <= ny || nx < 0 || W <= nx || visited[ny][nx]) {
                continue;
            }
            visited[ny][nx] = true;
            que.push(make_pair(flr[ny][nx], ny*W+nx));
        }
    }
    return res;
}

int main() {
    int R;
    while(cin >> R, R) {
        int W, H, sx, sy;
        cin >> W >> H >> sx >> sy;
        sx--; sy--;
        vector<vector<int>> flr1(H, vector<int>(W));
        for(int i=0; i<H; ++i) {
            for(int j=0; j<W; ++j) {
                cin >> flr1[i][j];
            }
        }
        auto f1 = search(flr1, sx, sy, R);
        cin >> W >> H >> sx >> sy;
        sx--; sy--;
        vector<vector<int>> flr2(H, vector<int>(W));
        for(int i=0; i<H; ++i) {
            for(int j=0; j<W; ++j) {
                cin >> flr2[i][j];
            }
        }
        auto f2 = search(flr2, sx, sy, R);

        int res = 1e9;
        for(int i=0; i<f1.size(); ++i) {
            int t = f1[i];
            if(R - i >= f2.size()) {
                continue;
            }
            t += f2[R-i];
            res = min(res, t);
        }
        cout << res << endl;
    }
}


Measured memory_bytes: 6116
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self //value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

def main():
    N,*C=map(int, open(0).read().split())
    DP=[Fp(1)]*(N+1)
    prev={}
    for i,c in enumerate(C):
        d=DP[i]
        if c in prev and not (i and C[i-1]==c):
            d+=DP[prev[c]]
        prev[c]=i+1
        DP[i+1]=d
    print(DP[N])

if __name__ == "__main__":
    main()

Measured memory_bytes: 39740
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cassert>
#include <exception>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<string,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
const ll INF = 1e+9+7;
ll n,m,l;
string s,t;
ll d[100000],dp[100][100];

int main(){
  cin >> n >> m;
  if(n == m)puts("Draw");
  else if(n == 1)puts("Alice");
  else if(m == 1)puts("Bob");
  else if(n > m)puts("Alice");
  else puts("Bob");
  return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> L(N);

    int sum = 0;
    int max_l = 0;

    for (int n = 0; n < N; ++n)
    {
        cin >> L[n];
        sum += L[n];
        max_l = max(max_l, L[n]);
    }
    sum -= max_l;
    cout << (max_l < sum ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int main(){
	unsigned int a,b;
	cin>>a>>b;
	if((!(a&1) && (b&1)) || (!(b&1) && (a&1)))
		cout<<"IMPOSSIBLE";
	else
	{
		int k = (a + b)/2;
		cout<<k;
	}
	
	return 0;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int a,b; cin >> a >> b;
    cout << a*a - b << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
const ll MAX_V=100000;//頂点の制約
const ll INF=100000000000000000;

struct edge{ll to,cost;};

vector<edge> G[MAX_V];//隣接リスト
vector<ll> d(MAX_V,INF);//頂点sからの最短距離
ll N;//頂点数

void dijkstra(ll s){
    priority_queue<P,vector<P>,greater<P>> que;
    d[s]=0;
    que.push(P(0LL,s));//P.a:最短距離 P.b:頂点の番号

    while(!que.empty()){
        P p=que.top(); que.pop();
        ll v=p.b;//頂点番号
        if(d[v]<p.a) continue;
        rep(i,G[v].size()){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

int main(){
    cin>>N;
    //辺の情報入力
    rep(i,N-1){
        ll from,to,cost; cin>>from>>to>>cost;
        G[from-1].push_back((edge){to-1,cost});
        G[to-1].push_back((edge){from-1,cost});
    }
    dijkstra(0);
    rep(i,N){
      //cout<<d[i];
      if(d[i]%2==0) cout<<0<<endl;
      else cout<<1<<endl;
    }
}

Measured memory_bytes: 8704
#include <cstdio>
#include <iostream>
#include <string>
#include <unordered_map>
#include <deque>
using namespace std;

#define _gp(l) const auto gcu{getchar##l}; const auto pcu{putchar##l}
#ifdef __linux
_gp(_unlocked);
#else
_gp();
#endif
#define _DEF(r, n, ...) inline r n(__VA_ARGS__) noexcept
#define _T template <typename T>
#define _HT template <typename H,typename... T>
#define _OP(t) inline operator t()
struct _in {
#ifdef _GLIBCXX_STRING
	_OP(string){string s;for(char c;c=gcu(),c!=' '&&c!='\n';)s+=c;return s;}
#endif
	_OP(char){char c=gcu();gcu();return c;}
	_OP(double){double d; scanf("%lf",&d); gcu();return d;}
	_T _OP(T){T n{},m{1},c;if((c=gcu())=='-')m=-1,c=gcu();do{n=10*n+(c-'0'),c=gcu();}while(c>='0'&&c<='9');return m*n;}
} in;
#define _SCAN(...) _DEF(bool,scan,__VA_ARGS__)
_T _SCAN(T &o) {int c{gcu()};return c==EOF?false:(ungetc(c,stdin),o=in,true);}
_HT _SCAN(H &h,T&&... t){return scan(h)&&scan(t...);}
#define _OUT(...) _DEF(void,out,__VA_ARGS__)
#define _OUTL(...) _DEF(void,outl,__VA_ARGS__)
_OUT(bool b){pcu('0'+b);}
_OUT(const char *s){while(*s)pcu(*s++);}
_OUT(char c){pcu(c);}
#ifdef _GLIBCXX_STRING
_OUT(string &s){for(char c:s)pcu(c);}
#endif
_T _OUT(T n){static char b[20];char *p=b;T m=n<0?pcu('-'),-1:1;
	if(!n)*p++='0';else while(n)*p++=(char)(n%10*m+'0'),n/=10;while(p!=b)pcu(*--p);}
_OUTL(){out('\n');}
#ifdef _GLIBCXX_VECTOR
_T _OUT(vector<T> &v){for(T &x:v)out(&x == &v[0]?"":" "),out(x);}
#endif
_HT _OUT(H &&h, T... t){out(h);out(t...);}
template <typename... T> _OUTL(T... t){out(t...);outl();}
struct range{
	int e,b=0,s=1; range(int _b,int _e,int _s):e(_e),b(_b),s(_s){} range(int _b,int _e): e(_e), b(_b){} range(int _e):e(_e){}
	struct it { int v, s; it (int _v, int _s) : v(_v), s(_s) {} operator int()const{return v;} operator int&(){return v;} int operator*()const{return v;}
		it& operator++(){v+=s;return *this;} }; it begin() {return {b, s};} it end() {return {e, s};}};
unordered_map<char, string> enc = {
	{' ', "101"}, {'\'', "000000"}, {',', "000011"}, {'-', "10010001"}, {'.', "010001"},
	{'?', "000001"}, {'A', "100101"}, {'B', "10011010"}, {'C', "0101"}, {'D', "0001"},
	{'E', "110"}, {'F', "01001"}, {'G', "10011011"}, {'H', "010000"}, {'I', "0111"},
	{'J', "10011000"}, {'K', "0110"}, {'L', "00100"}, {'M', "10011001"}, {'N', "10011110"},
	{'O', "00101"}, {'P', "111"}, {'Q', "10011111"}, {'R', "1000"}, {'S', "00110"},
	{'T', "00111"}, {'U', "10011100"}, {'V', "10011101"}, {'W', "000010"}, {'X', "10010010"},
	{'Y', "10010011"}, {'Z', "10010000"} };

int main() {
	string s;
	while(getline(cin, s)) {
		deque<bool> b;
		for (char c: s)
			for (char d: enc[c])
				b.push_back(d - '0');
		if (b.size() % 5)
			for (int i = 5 - b.size() % 5; i; i--)
				b.push_back(false);
		for (int i: range(b.size() / 5)) {
			int t {};
			for (int j: range(5))
				t = t << 1 | b[i * 5 + j];
			out((char) (t < 26 ? t + 'A' : " .,-'?"[t - 26]));
		}
		outl();
	}
}


Measured memory_bytes: 3008
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
    bool poss[109]={false};
    int n;
    int a;
    cin>>a>>n;
    int mindif=1000000;
    int val=1000000;
    int x;
    for(int i=1;i<=n;i++) { cin>>x ; poss[x]=true ;}
    for(int i=0;i<=101;i++) if(!poss[i])
    {
        if(abs(a-i)<mindif){ mindif=abs(a-i); val=i;}
    }
    cout<<val;
}


Measured memory_bytes: 3596
N, M = map(int,input().split())
num = [0,1,2,3,4,5,6,7,8,9]
ans = [str(i) for i in range(10**(N-1), 10**N)]
check = [1 for i in range(10**(N-1), 10**N)]
if N == 1:
    ans.insert(0,"0")
    check.insert(0,1)

for i in range(M):
    s, c = map(int,input().split())
    s -= 1
    for idx, j in enumerate(ans):
        if j[s] != str(c):
            check[idx] = 0
for idx, i in enumerate(check):
    if i == 1:
        print(ans[idx])
        quit()
print(-1)

Measured memory_bytes: 9232
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long int;
#define rep(i, n) for (ll i = 0; i < n; i++) 

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

	ll n;
	string s;
	cin >> n >> s;
	ll white_num=0, black_num=0;
	rep(i, n) {
		if (s[i] == '.')
			white_num++;
	}

	ll ret = white_num;
	for (ll i = 0; i < n; i++) {
		if (s[i] == '.') {
			white_num--;
		}
		if (s[i] == '#') {
			black_num++;
		}
		ret = min(ret, white_num + black_num);
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double
#define sz(a) ((int)(a).size())
#define clr(a,v) memset(a, v, sizeof(a))
#define all(a) (a).begin(),(a).end()
#define pii pair<int,int>
#define pdd pair<ld,ld> 
#define rep(i,a,b) for(int i=a; i<b; i++)
#define dec(i,a,b) for(int i=a; i>=b; i--)
#define ler freopen("inspection.in","r",stdin);freopen("inspection.out","w",stdout)
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define debug cout<<"!!?!!\n"
using namespace std;
#define PI 2*asin(1) 
#define EPS 1e-9
#define MOD 1000000007
#define MAXN 5033
#define INF 2e9

bool L[MAXN][MAXN], R[MAXN][MAXN];
int n, k, v[MAXN];

int main(){
	//fastio;
	cin >> n >> k;
	rep(i,0,n) cin >> v[i];

	rep(i,0,MAXN) L[i][0]=R[i][0]=1;
	rep(i,0,n){
		if(i==0){
			if(v[0]<k) L[0][v[0]]=1; 
			continue;
		}
		
		rep(j,0,k) if(L[i-1][j] && j+v[i]<k) L[i][j+v[i]]=1;	
		rep(j,0,k) L[i][j]|= L[i-1][j];
	}
	for(int i=n-1; i>=0; i--){
		rep(j,0,k) if(R[i+1][j] && j+v[i]<k) R[i][j+v[i]]=1;
		rep(j,0,k) R[i][j]|= R[i+1][j];
	}
	
	int ans=0;
	for(int i=0; i<n; i++){
		bool ok=false;
		if(v[i]>=k) ok=true;
		rep(j,0,k) if(R[i+1][j] && j+v[i]>=k) ok=true;
		
		if(i>0){
			int r=k-1;
			rep(l,0,k){
				if(L[i-1][l]){
					while(r>=0 && (l+r>=k || R[i+1][r]==0)) r--;
					if(r>=0 && l+r+v[i]>=k)
						ok=true;
				}
			}
		}
		if(!ok) ans++;
	}
	cout << ans << endl;
}
















Measured memory_bytes: 49664
x = input()
count = 0
if x[0] == '1':
  for i in range(1, len(x)):
    if i % 2 == 1 and x[i] != '0':
      count = count + 1
    elif i % 2 == 0 and x[i] != '1':
      count = count + 1
else:
  for i in range(1, len(x)):
    if i % 2 == 1 and x[i] != '1':
      count = count + 1
    elif i % 2 == 0 and x[i] != '0':
      count = count + 1
print(count)


Measured memory_bytes: 3188
(defun count-pairs (k s)
  (let ((mx (if (>= k s)
              s
              k))
        (mn (if (>= k s)
              0
              (- s k))))
    (if (<= mn mx)
      (+ (- mx mn) 1)
      0)))

(defun solv (k s)
    (loop for i below (+ k 1)
        sum (count-pairs k (- s i))))
 
(defparameter k (read))
(defparameter s (read))
(defparameter ans (solv k s))
(princ ans)


Measured memory_bytes: 7396
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};


int main() {
    ll N;
    cin >>N;
    
    rep(i,N){
        rep(j,N){
            if(4*i+7*j==N){
                cout<<"Yes"<<endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;


    return 0;
    

}

Measured memory_bytes: 3624
def main():
    h, a = map(int, input().split())
    x = (h + (a - 1)) // a
    print(x)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define in freopen("in.txt","r",stdin)
//#define out freopen("out.txt","w",stdout) 
ll n,m,k,t,l,r;
ll b,c,d;
char A,B,C,X,Y,Z;
ll ans,MAX,MIN=40,sum;
ll a[200050],f[200050];
//ll dp1[1000][1000],dp2[1000][1000];
char str[200050],bx[200050];


int main()
{
    ll i,s,x,j;
    t=1;
    //scanf("%lld",&t);
    while(t--)
    {
		ll l,r,d;
		cin>>l>>r>>d;
		ll num=0;
		for(i=l;i<=r;i++)
		{
			if(i%d==0) num++;
		}
		cout<<num<<endl;
	}
	return 0;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (ll)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
typedef long long int ll;
typedef vector<int> vecint;
typedef vector<ll> vecll;
typedef vector<double> vecd;
typedef vector<string> vecstr;
typedef vector<char> vecchar;
typedef vector<bool> vecbool;
typedef vector<vector<bool>> vec2bool;
typedef vector<vector<int>> vec2int;
typedef vector<vector<double>> vec2d;
////////////////////////////////////////////////
void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
////////////////////////////////////////////////
ll pow_mod(ll x, int n) {
  // x^n (mod M)
  ll pow = 1;
  while (n != 0) {
    if (n & 1) pow = pow * x % MOD;
    x = x * x % MOD;
    n = n >> 1;
  }
  return pow;
}
////////////////////////////////////////////////
struct edge {
  int to;
  ll cost;
};
vector<vector<edge>> G;
typedef pair<ll, int> P;
////////////////////////////////////////////////
int main() {
  init();
  int n;
  cin >> n;
  G.resize(n);
  REP(i, n - 1) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    a--;
    b--;
    G[a].push_back(edge{b, c});
    G[b].push_back(edge{a, c});
  }
  int q, k;
  cin >> q >> k;
  k--;
  vector<pair<int, int>> task(q);
  for (auto& e : task) {
    cin >> e.first >> e.second;
    e.first--;
    e.second--;
  }

  ///////////////////////
  // djikstra
  vecll d(n, LLONG_MAX);
  priority_queue<P, vector<P>, greater<P>> que;
  d[k] = 0;
  que.push(P(0, k));
  while (!que.empty()) {
    P p = que.top();
    que.pop();
    int v = p.second;
    if (d[v] < p.first) {
      continue;
    }
    for (auto& e : G[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
  for (auto& e : task) {
    cout << d[e.first] + d[e.second] << endl;
  }
}


Measured memory_bytes: 11888
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

char s[100][100];
int vis[100][100];
int h , w;

void check(int x , int y)
{
	int tx = x - 2;
	int ty = y - 2;
	int cnt = 0;
	for(int i = 1 ; i <= 3 ; i++){
		for(int j = 1 ; j <= 3 ; j++){
			if(tx + i < 1 || ty + j < 1 || tx + i > h || ty + j > w) continue;
			if(s[tx + i][ty + j] == '#') cnt++;
		}
	}
	vis[x][y] = cnt;
}

int main()
{
	scanf("%d %d",&h ,&w);
	for(int i = 1 ; i <= h ; i++) scanf("%s",s[i] + 1);
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			if(s[i][j] == '.'){
				check(i , j);
			}
		}
	}
	for(int i = 1 ; i <= h ; i++){
		for(int j = 1 ; j <= w ; j++){
			if(s[i][j] == '.') printf("%d",vis[i][j]);
			else printf("%c",s[i][j]);
		}
		printf("\n");
	}
}

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

char maze[101][101];
int main(){
    int h,w;
    cin >> h >> w;
    rep(i,h) rep(j,w) {
        cin >> maze[i][j];
    }
    rep(i,h){
        bool all = true;
        rep(j,w){
            if (maze[i][j] != '.') {
                all = false;
                break; 
            }    
        }
        if (all){ 
            rep(q,w) maze[i][q] = 'x';
        }
    }
    rep(i,w){
        bool all = true;
        rep(j,h){
            if (maze[j][i] != '.' && maze[j][i] != 'x') {
                all = false;
                break; 
            }
        }
        if (all){
            rep(q,h) maze[q][i] = 'x';
        }
    }
    rep(i,h){
        bool yes = false;
        rep(j,w){
            if (maze[i][j] == 'x') continue;
            else {
                cout << maze[i][j];
                yes = true;
            }
        }
        if (yes) cout << endl;
    }


    
    
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * @author kawakami
 *
 */
class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner as = new Scanner(System.in);
		
		double a,b,C,S,L,h,to,cos,sin;
		String str;
		
		a = as.nextDouble();
		b = as.nextDouble();
		C = as.nextDouble();
		
		sin = Math.sin(Math.toRadians(C));
		cos = Math.cos(Math.toRadians(C));
		
		S = a * (b * sin) / 2;
		
		to = Math.sqrt(a * a + b * b - 2*(a * b * cos));
		
		L = a + b + to;
		
		h = b * sin;
		
		str = String.valueOf(S);
		System.out.println(str);
		str = String.valueOf(L);
		System.out.println(str);
		str = String.valueOf(h);
		System.out.println(str);

	}

}

Measured memory_bytes: 27960
#include <bits/stdc++.h>
using namespace std;
int main(){
	int x,y,a,b,c,p[100010],q[100010],r[100010];
	cin >> x >> y >> a >> b >> c;
	for(int i = 0; i < a; i++){
		cin >> p[i];
	}
	for(int i = 0; i < b; i++){
		cin >> q[i];
	}
	for(int i = 0; i < c; i++){
		cin >> r[i];
	}
	sort(p,p+a,greater<int >());
	sort(q,q+b,greater<int >());
	sort(r,r+c,greater<int >());
	long long sum = 0;
	int new_arr[200010];
	for(int i = 0; i < x;i++){
		new_arr[i] = p[i];
	}
	for(int i = 0; i < y;i++){
		new_arr[i + x] = q[i];
	}
	sort(new_arr,new_arr + (x+y));
	int temp = 0;
	for(int i = 0; i < c;i++){
		if(r[i] > new_arr[temp]){
			new_arr[temp] = r[i];
			temp++;
		}else break;
	}
	for(int i = 0; i < (x+y); i++)
		sum += new_arr[i];
	cout << sum << endl;
    return 0;
 
}

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

int main(){
  int n,m;cin >> n >> m;
  vector<int> x(m);rep(i,m)cin >> x[i];
  vector<int> y(m);
  sort(x.begin(),x.end());
  rep(i,m-1){
    y[i] = x[i+1]-x[i];
  }
  sort(y.begin(),y.end(),greater<>());
  int ans = 0;
  for(int i=n-1;i<m-1;++i)ans += y[i];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024