akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll, ll> PLL;
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) \
  for (int i = static_cast<int>(a); i < static_cast<int>(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, ) (__VA_ARGS__)  // NOLINT

ll ans;
ll N, M, Q;
ll t[10];
ll a[100];
ll b[100];
ll c[100];
ll d[100];

void dfs(int i) {
  if (i == N) {
    //rep(i, N) {
    //  cout << t[i] << " ";
    //}
    //cout << endl;
    ll score = 0;
    rep(i, Q) {
      if (t[b[i]] - t[a[i]] == c[i])
        score += d[i];
    }
    ans = max(ans, score);
  } else if (i == 0) {
    for (ll n = 1; n <= M; n++) {
      t[i] = n;
      dfs(i+1);
    }
  } else {
    for (ll n = t[i-1]; n <= M; n++) {
      t[i] = n;
      dfs(i+1);
    }
  }
}

signed main() {
  ans = -1;
  cin >> N >> M >> Q;
  rep(i, Q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--;
    b[i]--;
  }
  dfs(0);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>

int main()
{
    char x[1005];
    int i, sum = 0;
    
    while (1)
    {
        scanf("%s", x);
        if (x[0] == '0') break;
        for (i = 0;x[i] != '\0'; i++)
        {
            sum += x[i] - '0';
        }
        printf("%d\n", sum);
        sum = 0;
    }
    
    return 0;
}



Measured memory_bytes: 2696
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
#define sz(x) x.size()
// aよりbの方が小さかったら、aの値をbの値に置き換える。(swapではない！)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
// aよりbの方が大きかったら、aの値をbの値に置き換える。
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
// 素数かどうか判定
bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s; cin >> s;
	if (s.at(0) == s.at(1) || s.at(1) == s.at(2) || s.at(2) == s.at(3)) {
		cout << "Bad" << endl;
	}
	else {
		cout << "Good" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

ll	n , k;
vector<int> a(1000001),f(1000001);

// 二分探索法
// index が条件を満たすかどうか
bool isOK(ll index) {
	ll  c = 0;
	for(int i=0;i<n;i++) {
		if ((ll)a[i]*f[i] > index) c += a[i] - index / f[i];
	}
	if (c > k) return false;
    else return true;
}
// 汎用的な二分探索のテンプレ
ll binary_search(ll m) {
    ll left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    ll right = m; // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        ll mid = right + (left - right) / 2;

        if (isOK(mid)) right = mid;
        else left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}

int main() {
	ll		b,c,d,w,h,i,j,l,m,x,y,z;
	ll		ans = 0;
	string	s;
	cin >> n >> k;
	vector<int>	aa(n),ff(n);
	for(i=0;i<n;i++) cin >> aa[i];
	for(i=0;i<n;i++) cin >> ff[i];

	sort(aa.begin(),aa.end());
	sort(ff.begin(),ff.end());
	reverse(aa.begin(),aa.end());
	a = aa;
	f = ff;

	ans = binary_search((ll)a[0]*f[n-1]+1);
	cout << ans << endl;
	return 0;
}


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

int main()
{
  double a,b,x;
  double v;
  cin>>a>>b>>x;
  v=a*a*b/2;
  if(x<=v)
  {
    double h,r;
    h=x*2/b/a;
    r=90-atan(h/b)*180/M_PI;
    cout<<fixed<<setprecision(10);
    cout<<r<<endl;
  }
  else
  {
    double h,r;
    h=(a*a*b-x)*2/a/a;
    r=atan(h/a)*180/M_PI;
    cout<<fixed<<setprecision(10);
    cout<<r<<endl;
  }
}

Measured memory_bytes: 4068
#include<stdio.h>

int main()
{
	int memo,w,tate,c;
	int i,d;

	
	 while(scanf("%d",&d)!=EOF)
	 {
		 w=0;
		 memo=0.0;
		 c=600.0/d;
		 for(i=0;i<c-1;i++)
		 {
			 w+=d;
			 tate=w*w;
			 memo+=tate*d;
		 }
		 printf("%d\n",(int)memo);
	 }
	 return 0;
}

Measured memory_bytes: 596
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int max = Math.max(Math.max(a, b), c);
        int x = max * 3 - a - b - c;
        if (x % 2 == 0)
            System.out.println(x / 2);
        else
            System.out.println((x + 1) / 2 + 1);
    }
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Map = map<string,ll>;



int main(){
	ll A;
	cin >> A;
	ll B;
	cin >> B;
	if((B-1)%(A-1)==0)cout<<(B-1)/(A-1)<<endl;
	else cout<<(B-1)/(A-1)+1<<endl;
return 0;
}  



Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    // Here your code !
    int N;
    
    scanf("%d",&N);
    if(N<=1){
        printf("%d",N);
    }else if(N<=3){
        printf("2\n");
    }else if(N<=7){
        printf("4\n");
    }else if(N<=15){
        printf("8\n");
    }else if(N<=31){
        printf("16\n");
    }else if(N<=63){
        printf("32\n");
    }else{
        printf("64\n");
    }
    
    return 0;
}

Measured memory_bytes: 128
using System;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            int a = array[0], b = array[1], k = array[2];
            var answers = from i in Enumerable.Range(1, 100)
                          where a % i == 0 && b % i == 0
                          orderby i descending
                          select i;
            Console.WriteLine(answers.ElementAt(k - 1));
        }
    }
}

Measured memory_bytes: 13396
#include "bits/stdc++.h"

using namespace std;

void Calculate_Depth(vector<vector<int>>&edge, vector<int>&depth, int stnode) {
	depth[stnode] = 0;
	queue<int>Q;
	Q.push(stnode);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto i : edge[cn]) {
			if (depth[i] > depth[cn] + 1) {
				depth[i] = depth[cn] + 1;
				Q.push(i);
			}
		}
	}
	return;
}

int main(){
	int N,M;
	while(cin>>N>>M,N){
		vector<vector<int>>edge(N);
		for(int i=0;i<M;i++){
			int a,b;
			cin>>a>>b;
			a--;
			b--;
			edge[a].push_back(b);
			edge[b].push_back(a);
		}
		vector<int>depth(N,100000);
		Calculate_Depth(edge,depth,0);
		int odd=0,even=0;
		for(int i=0;i<N;i++){
			if(depth[i]&1)odd++;
			else even++;
		}
		for(int i=0;i<N;i++){
			for(auto j:edge[i]){
				if(depth[i]==depth[j])odd=1,even=3;
			}
		}
		set<int>ans;
		
		if(odd%2==0)ans.insert(odd/2);
		if(even%2==0)ans.insert(even/2);
		//if(odd==even)ans.insert(odd);
		//cout<<N<<endl;
		//cout<<odd<<" "<<even<<endl;
		cout<<ans.size()<<endl;
		for(auto i:ans)cout<<i<<endl;
	}
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

void leave(string message) {
    cout << message << endl;
    exit(0);
}

int main() {
    lint n;
    cin >> n;

    vector<lint> a(n);
    for(auto& elem : a)  cin >> elem;

    for(lint i=0; i<n; i++) {
        if(a[i] % 2 == 0 && (a[i] % 3 != 0 && a[i] % 5 != 0)) {
            leave("DENIED");
        }
    }
    leave("APPROVED");
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iomanip>
#include <cassert>
#include <random>
#include <tuple>
#include <cstdint>

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

using namespace std;
typedef long long ll;

const int INF = 1 << 30;
const int MOD = 1e9 + 7;


int main() {
    int n; cin >> n;
    string s; cin >> s;
    string ans = "";
    int right = 0;
    int left = 0;
    rep(i, n) {
        if (s[i] == '(') {
            left++;
        } else {
            if (left > 0) {
                left--;
            } else {
                right++;
            }
        }
    }
    rep(i, right) ans += '(';
    ans += s;

    reverse(s.begin(), s.end());

    right = 0;
    left = 0;
    rep(i, n) {
        if (s[i] == ')') {
            left++;
        } else {
            if (left > 0) {
                left--;
            } else {
                right++;
            }
        }
    }

    rep(i, right) ans += ')';

    cout << ans << endl;




    return 0;
}

Measured memory_bytes: 256
const Main = (input) => {
  const tmp = input.trim().split('\n')
  const N = parseInt(tmp[0])
  const aArr = tmp[1].split(' ').map(Number)

  var result = aArr.reduce((a, x) => a += x, 0) - N

  console.log(result)
  return result
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'))

Measured memory_bytes: 7500
import numpy as np

S = np.array(list(input()))
num_x = np.count_nonzero(S == 'x')
# print(f'{num_x=}')
A = [s for s in S if s != 'x']
# print(f'{S=}, {A=}')

if len(A) % 2 == 0:
    L = A[:len(A) // 2]
    R = A[len(A) // 2:][::-1]
else:
    L = A[:len(A) // 2]
    R = A[len(A) // 2 + 1:][::-1]
# print(f'{L=}, {R=}')
if not np.all(L == R):
    print(-1)
    exit()

# x以外の文字でsplitをする？'x' '' 'x' ''

T = []
subset = ''
for s in S:
    # print(f'{subset=}')
    if s == 'x':
        subset += 'x'
    else:
        T.append(subset)
        subset = ''
T.append(subset)
len_T = np.array([len(t) for t in T])
# print(f'{T=}, {len_T=}, {len_T - len_T[::-1]}')
ans = np.abs(len_T - len_T[::-1]).sum() // 2
print(ans)


Measured memory_bytes: 41904
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;


//文字0~9をint型0~9に変換
int char_to_int(char c)
{
	if (c == '0') return 0;
	if (c == '1') return 1;
	if (c == '2') return 2;
	if (c == '3') return 3;
	if (c == '4') return 4;
	if (c == '5') return 5;
	if (c == '6') return 6;
	if (c == '7') return 7;
	if (c == '8') return 8;
	if (c == '9') return 9;
	else return -1;
}
//a^b mod MODを計算
long long int ModPower(long long int a, long long int b, long long int MOD)
{
	if (b == 0) return 1;
	else if (b % 2 == 0)
	{
		long long int d = ModPower(a, b / 2, MOD);
		return (d*d) % MOD;
	}
	else
	{
		return (a*ModPower(a, b - 1, MOD)) % MOD;
	}
}
//nCr mod MODを計算
long long int ModCombi(long long int n, long long int r, long long int MOD)
{
	if (n == 0 || r == 0) return 1;

	long long int Kn=1, Kr=1, Knr=1;

	long long int temp = 1;
	for (long long int i = 1; i <= n; i++)
	{
		temp *= i;
		temp %= MOD;
		if (i == n) Kn = temp;
		if (i == r) Kr = temp;
		if (i == n - r) Knr = temp;
	}

	long long int x = ModPower(Kr, MOD - 2, MOD);
	long long int y = ModPower(Knr, MOD - 2, MOD);

	long long int ans;
	ans = Kn * x;
	ans %= MOD;
	ans *= y;
	ans %= MOD;

	return ans;
}


/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/

int H, W;
char S[2005][2005];

int U[2005][2005], D[2005][2005], R[2005][2005], L[2005][2005];

int main()
{
	cin >> H >> W;
	for (int i = 0; i < H; i++)
	{
		cin >> S[i];
	}

	for (int i = 0; i < W; i++)
	{
		if (S[0][i] == '.') U[0][i] = 1;

		for (int j = 1; j < H; j++)
		{
			if (S[j][i] == '.') U[j][i] = U[j - 1][i] + 1;
		}

		if (S[H - 1][i] == '.') D[H - 1][i] = 1;

		for (int j = H - 2; j >= 0; j--)
		{
			if (S[j][i] == '.') D[j][i] = D[j + 1][i] + 1;
		}
	}

	for (int i = 0; i < H; i++)
	{
		if (S[i][0] == '.') L[i][0] = 1;

		for (int j = 0; j < W; j++)
		{
			if (S[i][j] == '.') L[i][j] = L[i][j - 1] + 1;
		}

		if (S[i][W - 1] == '.') R[i][W - 1] = 1;

		for (int j = W - 2; j >= 0; j--)
		{
			if (S[i][j] == '.') R[i][j] = R[i][j + 1] + 1;
		}
	}

	int ans = 0;

	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			ans = max(ans, U[i][j] + D[i][j] + R[i][j] + L[i][j] - 3);
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 66944
import Control.Monad
import Data.List
import qualified Data.IntMap as M

main=do
    [n,m]<-map read.words<$>getLine::IO[Int]
    abs<-replicateM m $ map read.words<$>getLine::IO[[Int]]
    mapM_ (print.snd) $ M.toAscList $ foldl (\m [a,b] -> M.insertWith(+)a 1 $ M.insertWith(+)b 1 m) (M.fromList $ zip [1..n] $ repeat 0) abs


Measured memory_bytes: 892
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
struct node{
	int next,v,u,w;
}p[maxn];
int head[maxn],cnt,vis[maxn],n,k,maxx;
void add(int u,int v)
{
	p[cnt].v=v;
	p[cnt].next=head[u];
	head[u]=cnt++;
}
void dfs(int now,int fa,int step)
{
	maxx++;
	if(step==0)
	return ;
	for(int i=head[now];~i;i=p[i].next)
	{
		if(p[i].v==fa)
		continue;
		dfs(p[i].v,now,step-1);
	}
}
int main()
{
	int i,j,x,y;
	scanf("%d%d",&n,&k);
	for(i=0;i<=n;i++)
	head[i]=-1;
	for(i=0;i<n-1;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	int ans=0;
	if(k%2)   
	{
		for(i=1;i<=n;i++)
		{
			for(j=head[i];~j;j=p[j].next)
			{
				maxx=0;
				int t=p[j].v;
				dfs(t,i,k/2);
				dfs(i,t,k/2);
				ans=max(maxx,ans);
			}
		}
	}
	else     
	{
		for(i=1;i<=n;i++)
		{
			maxx=0;
			dfs(i,0,k/2);
			ans=max(maxx,ans);
		}
	}
	printf("%d\n",n-ans);
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn= 5e5+5;
#define mod 1000000007
#define endl '\n'
void rishabh(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int main() {
    int a,b;
    cin>>a>>b;
    int k=log10(b)+1;
    int temp=a*pow(10,k)+b;
    int x=sqrt(temp);
    if(x*x==temp){
        cout<<"Yes";
    }
    else cout<<"No";
}



Measured memory_bytes: 4012
A, B, C, X, Y = map(int, input().split())

ans = A * X + B * Y
for i in range(10 ** 5 + 1):
    total = 2 * C * i + A * max(0, X - i) + B * max(0, Y - i)
    ans = min(total, ans)

print(ans)


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

#define ll long long
#define INF 99999999
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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

    vector<int> C(N);
    vector<int> S(N);
    vector<int> F(N);

    rep(i,N-1) cin >> C[i] >> S[i] >> F[i];
    
    rep(j,N)
    {
        ll ans = 0;
        for(int i = j;i < N-1;i++)
        {
            if( ans < S[i] )
            {
                ans = S[i]+C[i];
            }
            else
            {
                ll start = S[i];
                while( start < ans ) start += F[i];
                //cout << "ans is " << ans << " and start is " << start << endl;
                ans = start + C[i];
            }
            //cout << ans << endl;
        }
        cout << ans << endl;
    }




}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int comp(const void* a, const void* b)
{ return *(int*)a > *(int*)b ; }
int findNumberOfTriangles(int arr[], int n)
{
	qsort(arr, n, sizeof( arr[0] ), comp);
	int count = 0;
	for (int i = 0; i < n - 2; ++i)
	{
		int k = i + 2;
		for (int j = i + 1; j < n; ++j)
		{
			while (k < n && arr[i] + arr[j] > arr[k])
			++k;
			if(k > j)
			count += k - j - 1;
		}
	}

	return count;
}
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;++i) cin>>a[i];
	cout<<findNumberOfTriangles( a, n );
	return 0;
}



Measured memory_bytes: 256
import numpy as np
A, B, M = list(map(int,input().split()))
a = np.array(list(map(int,input().split())))
b = np.array(list(map(int,input().split())))

x = []
for i in range(M) :
    x.append(list(map(int,input().split())))

x = np.array(x)
min_val = a.min() + b.min()

for i in range(len(x)) :
    if min_val > a[x[i][0]-1] + b[x[i][1]-1] - x[i][2] :
        min_val = a[x[i][0]-1] + b[x[i][1]-1] - x[i][2]

print(min_val)

Measured memory_bytes: 44572
#include <bits/stdc++.h>
#define rep(i,n) for (ll i=0; i<(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
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 main(){
    double a,b,h; cin >> a >> b >> h;
    double ans=(a+b)*h/2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef pair<int,pair<int,int> > P;
int main(){
  int n,m,a;
  while(cin>>n>>m>>a , n||m||a){
    int id[101];
    for(int i=1;i<=n;++i) id[i] = i;
    vector<P> ho;
    for(int i=0;i<m;++i){
      int h,x,y;
      cin>>h>>x>>y;
      ho.push_back(P(h,make_pair<int,int>(x,y)));
    }
    sort(ho.begin(),ho.end());
    
    for(int i=0;i<m;++i){
      swap(id[ho[i].second.first],id[ho[i].second.second]);
    }
    cout << id[a] << endl;
  }
  return 0;
}

Measured memory_bytes: 1224
N = int(input())
H = list(input().split())
num = 0
for A in range(N):
  tf = 1
  if A == 0:
    num+= 1
    continue
  for B in range(A + 1):
    if int(H[A]) < int(H[B]):
      tf = 0
  if tf:
    num += 1
print("{}".format(num))


Measured memory_bytes: 2940
#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

int main(void) {
  int N, A, B;
  scanf("%d %d %d", &N, &A, &B);

  if ((B - A) % 2) {
    puts("Borys");
  } else {
    puts("Alice");
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <algorithm>

#include <map>
using namespace std;

int main(void){
        int n;
        cin>>n;


        vector<long> A;
        vector<long> _A_sort;
        vector<long> A_sort;
        long a;
        for(int i=0; i<n; i++) {
                cin>>a;
                A.push_back(a);
                _A_sort.push_back(a);
        }
        sort(_A_sort.begin(),_A_sort.end());

        A_sort.push_back(_A_sort[0]);

        for(int i=1; i<n; i++) {
                if(A_sort[A_sort.size()-1]!=_A_sort[i]) {
                        A_sort.push_back(_A_sort[i]);
                }
        }
        map<long,long> d;
        for(long i=0; i<A_sort.size(); i++) {
                d[A_sort[i]]=i+1;
        }
        for(int i=0; i<n; i++) {
                A[i]=d[A[i]];
        }

        int counter[n];
        for(int i=0; i<n; i++) {
                counter[i]=1;
        }

        for(int i=0; i<n; i++) {
                for(int j=i-1; j>=0; j--) {
                        if(A[j]<A[i]) {
                                counter[i]=max(counter[i],counter[j]+1);
                                if(A[j]+1==A[i]){
                                        break;
                                }
                        }
                        else if(A[j]==A[i]) {
                                counter[i]=max(counter[j],counter[i]);
                                break;
                        }
                        else if(A[j]>A[i] && counter[j]<=counter[i]) {
                                break;
                        }

                }
        }

        int retval=0;
        for(int i=0; i<n; i++) {
                retval=max(counter[i],retval);
        }
        cout<<retval<<endl;



        return 0;
}



Measured memory_bytes: 11820
N = gets.to_i
ary1 = []
ary2 = []
for i in 0..N-1 do
  l,r = gets.split(" ").map(&:to_i)
  ary1.push(l)
  ary2.push(r)
end
sum = 0
for i in 0..N-1 do
  sum += ary2[i] - ary1[i] + 1
end
puts sum

Measured memory_bytes: 1788
#include <stdio.h>

int main(void){

    int A,B,C,most,second,third,answer = 0;
    
    scanf("%d %d %d",&A,&B,&C);
    
    most = A;
    second = B;
    third = C;
    
    if(B > A){
        most = B;
        second = A;
        
    }    
    if(most < C){
        most = C;
        second = B;
        third = A;
    }
    
    answer = 10*most + second + third;
    
    printf("%d",answer);
    
    return 0;
}


Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
const int mod= 1e+9+7;

/*int main(){
    ll N,C,K; cin>>N>>C>>K;
    vector<ll>T(N);
    rep(i,N)cin>>T[i];
    sort(T.begin(),T.end());
    ll ans=1,t=T[0],c=0;
    rep(i,N){
        if(c==C){
            c=0;
            ans++;
            t=T[i];
        }
        if(T[i]<=t+K){
            c++;
        }
        else{
            t=T[i];
            ans++;
            c=1;
        }
    }
    cout<<ans<<endl;
}*/

int main() {
    ll N,C,K; cin>>N>>C>>K;
    vector<ll>T(N);
    rep(i,N)cin>>T[i];
    sort(T.begin(),T.end());
    ll mx=0,mn=1e+9+7;
    ll cnt=0,ans=0;
    rep(i,N){
        mx=max(mx,T[i]);
        mn=min(mn,T[i]+K);
        cnt++;
        //cout<<cnt<<" ";
         if(mx>mn){
            ans++;
            mx=T[i],mn=T[i]+K;
           cnt=1;
            }
        else if(cnt>=C){
            //cout<<"UNKO"<<endl;
            ans++;
            mx=0,mn=1e+9+7;
            cnt=0;
        }
       
    }
    if(cnt!=0)cout<<ans+1<<endl;
    else cout<<ans<<endl;
}


 



Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define INF 1001001001
#define LINF (1LL << 62)
using namespace std;
using ll = long long;
using P = pair<int, int>;

void solv() {
    int A, B, M;
    cin >> A >> B >> M;
    int min_r = INF;
    int min_d = INF;
    vector<int> a(A), b(B);
    rep(i, A) {
        cin >> a[i];
        min_r = min(a[i], min_r);
    }
    rep(i, B) {
        cin >> b[i];
        min_d = min(b[i], min_d);
    }
    int min_sum = min_r + min_d;
    int sum = INF;
    rep(i, M) {
        int x, y, c;
        cin >> x >> y >> c;
        int buf = a[x-1] + b[y-1] - c;
        sum = min(sum, buf);
    }
    cout << min(sum, min_sum) << endl;
}

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

Measured memory_bytes: 1024
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        PriorityQueue<Job> q=new PriorityQueue<>();
        Job[] a = new Job[n];
        for(int i = 0; i < n; i++){
            a[i] = new Job(scanner.nextInt(),scanner.nextInt());
            q.add(a[i]);
        }
        Arrays.sort(a);
        long now = 0;
        for(long i = 0; i < n; i++){
            now += q.peek().day;
            if(now > q.poll().deadline){
                System.out.println("No");return;
            }
        }
        System.out.println("Yes");
    }
    static class Job implements Comparable<Job>{
		int day,deadline;
		public Job(int day,int deadline){
			this.deadline=deadline;
			this.day=day;
		}
		@Override
		public int compareTo(Job j){
            if(this.deadline==j.deadline){
                return j.day - this.day;
            }
			return this.deadline-j.deadline;
		}
	}
}



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

vector<vector<int>> graph(100001);
vector<int> d_1(100001), d_n(100001);
vector<bool> isVisited_1(100001, false);
vector<bool> isVisited_n(100002, false);

void dfs1(int now, int depth){
    isVisited_1[now] = true;
    d_1[now] = depth;
    int n = graph[now].size();
    rep(i,n){
        if(!isVisited_1[graph[now][i]]) dfs1(graph[now][i], depth+1);
    }
}

void dfsn(int now, int depth){
    isVisited_n[now] = true;
    d_n[now] = depth;
    int n = graph[now].size();
    rep(i,n){
        if(!isVisited_n[graph[now][i]]) dfsn(graph[now][i], depth+1);
    }
}

int main(){
    int n; cin >> n;
    int a, b;
    rep(i,n-1){
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs1(0,0);
    dfsn(n-1,0);
    int fen = 0, sun = 0;
    rep(i,n){
        if(d_1[i] <= d_n[i]) fen++;
        else sun++;
    }
    if(fen > sun) cout << "Fennec";
    else cout << "Snuke";
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
#define inf (long long)1e10
#define ofst 128
using namespace std;

struct data {
  int x, y, t;
  long long cost;
};
bool operator<(const data &l, const data &r) {
  return l.cost > r.cost;
}

int sx, sy, gx, gy, n, lx, ly;
set<pair<int, int>> st;
long long dis[300][300][8] = {0};
priority_queue<data> pq;

bool isvalid(const data &now) {
  return now.x >= -lx + ofst && now.x <= lx + ofst &&
         now.y >= -ly + ofst && now.y <= ly + ofst;
}
void move(data &now, int dir) {
  if(dir == 0 || ((dir == 1 || dir == 5) && now.x % 2 != 0))
    ++now.y;
  if(dir == 3 || ((dir == 2 || dir == 4) && now.x % 2 == 0))
    --now.y;
  if(dir == 1 || dir == 2) ++now.x;
  if(dir == 4 || dir == 5) --now.x;
}
long long solve();

int main() {
  cin >> sx >> sy >> gx >> gy >> n;
  sx += ofst;
  sy += ofst;
  gx += ofst;
  gy += ofst;
  for(int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    st.insert({x + ofst, y + ofst});
  }
  cin >> lx >> ly;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long res = inf;
  for(int i = 0; i < 300; ++i)
    for(int j = 0; j < 300; ++j)
      for(int k = 0; k < 7; ++k) dis[i][j][k] = inf;
  pq.push({sx, sy, 0, 0});
  dis[sx][sy][0] = 0;
  while(!pq.empty()) {
    data now = pq.top();
    pq.pop();
    if(dis[now.x][now.y][now.t] != now.cost) continue;
    for(int i = 0; i < 7; ++i) {
      data nextp = now;
      move(nextp, i);
      if(st.find({nextp.x, nextp.y}) != st.end()) continue;
      (++nextp.t) %= 6;
      if(abs((now.x - ofst) * (now.y - ofst) * now.t) % 6 !=
         i)
        ++nextp.cost;
      if(isvalid(nextp) &&
         dis[nextp.x][nextp.y][nextp.t] > nextp.cost) {
        dis[nextp.x][nextp.y][nextp.t] = nextp.cost;
        pq.push(nextp);
      }
    }
  }
  for(int i = 0; i < 6; ++i) res = min(res, dis[gx][gy][i]);
  if(res == inf) return -1;
  return res;
}


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

int N, A, B;

int main(void){
    
    scanf("%d %d %d", &N, &A, &B);
    printf("%d\n", min(N * A, B));
    
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, m, n) for(int i = (m); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

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; }

template<class T> inline auto __lcm(T& a, T& b) 
{ return a * b / __gcd(a, b); }

int main() {
    int N, K;  cin >> N >> K;
    vector<int> A(N);  rep(i, N) cin >> A[i];

    int tmp = N-K;
    int cnt = 1;
    rep(i, N) {
        if (tmp <= 0) break;
        tmp = tmp-K+1;
        ++cnt;
    }

    print(cnt);
}


Measured memory_bytes: 640
ans ([0,0]:_) = []
ans ([r,c]:x) = a:(ans x)
    where
        a = if (mod (r*c) 2) == 0
            then "yes"
            else "no"

main = do
    c <- getContents
    let i = map (map read) $ map words $ lines c :: [[Int]]
        o = ans i
    mapM_ putStrLn o


Measured memory_bytes: 4160
#include <iostream>

using namespace std;

int main() {

	int s[31], j=28, x;

	for(int i=1; i<31; i++) {
		s[i]=1;
	}
	while(j) {
		cin >> x;
		s[x]=0;
		j--;
	}
	for(int i=1; i<31; i++) {
		if(s[i]==1)
			cout << i << endl;
	}

	return 0;

}

Measured memory_bytes: 0
def calc(D, C, S, T):
    s = 0
    l = [-1] * len(C)
    for d, t in enumerate(T):
        t -= 1
        s += S[d][t]
        s -= C[t] * (d - l[t]) * (d - l[t] - 1) // 2
        l[t] = d
    s -= sum(c * (d - l[i]) * (d - l[i] + 1) // 2 for i, c in enumerate(C))
    return s


def main():
    D = int(input())
    C = list(map(int, input().split()))
    S = [list(map(int, input().split())) for _ in range(D)]
    
    for i in range(D):
        print(S[i].index(max(S[i])) + 1)

main()


Measured memory_bytes: 9400
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//using ll = long long;
using P = pair<int,int>;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;

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

signed main(){
	int n,k;
	string s;
	cin >> n >> k >> s;
	s[k - 1] -= 'A' - 'a';
	cout << s << endl;
}

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

using namespace std;
int n, m;
int parent[100000+5];

int find(int v){
    if(parent[v]==v)return v;
    return parent[v] = find(parent[v]);
}

void merge(int u, int v){
    u = find(u);
    v = find(v);
    if(u != v){
        parent[v] = u;
    }
}

int main(){
    
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        parent[i] = i;
    }
    while(m--){
        int u, v;
        cin >> u >> v;
        merge(u, v);
    }
    
    set<int> S;
    for(int i = 1; i <= n; i++){
        S.insert(find(i));
    }
    
    cout << S.size()-1 << endl;
    
    return 0;
    
}




Measured memory_bytes: 7980
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		for(int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if(!isValid(a)) {
				System.out.println("DENIED");
				return;
			}
		}
		System.out.println("APPROVED");
	}

	private static boolean isValid(int num) {
		if(num % 2 != 0) {
			return true;
		}

		if(num % 3 == 0) {
			return true;
		}

		if(num % 5 == 0) {
			return true;
		}

		return false;
	}
}

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

using I = long long;
using P = pair<I, I>;
using Node = tuple<I, I, I>;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for(auto& i: A) cin >> i;

  map<I, P> m;
  for(auto i=N-1; 0<=i; --i) ++m[A[i]].first, m[A[i]].second = i;
  priority_queue<Node> q;
  for(auto i: m) q.emplace(i.first, i.second.first, i.second.second);

  vector<I> ans(N);
  while(!q.empty()) {
    if(q.size() == 1) {
      I a, n, x;
      tie(a, n, x) = q.top(); q.pop();
      ans[x] += a * n;
    } else {
      I a1, n1, x1;
      I a2, n2, x2;
      tie(a1, n1, x1) = q.top(); q.pop();
      tie(a2, n2, x2) = q.top(); q.pop();
      ans[x1] += (a1 - a2) * n1;
      q.emplace(a2, n1 + n2, min(x1, x2));
    }
  }
  for(auto i: ans) cout << i << endl;
}


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

using namespace std;

int n, k, q;
int a[2010];

int go(int x){
    vector<pair<int, int>> b;
    for(int i = 0; i < n; i++){
        if(a[i] >= x){
            int r = i;
            while(r < n && a[r] >= x) r++;
            r--;
            b.push_back({i, r});
            i = r;
        }
    }
    vector<int> c;
    //cout << x << ": \n";
    for(auto u: b){
        vector<int> tmp;
        for(int i = u.first; i <= u.second; i++){
            tmp.push_back(a[i]);
        }
        sort(tmp.begin(), tmp.end());
        //cout << tmp.size() << endl;
        for(int i = 0; i < u.second - u.first + 1 - k + 1; i++){
            c.push_back(tmp[i]);
        }
    }
    sort(c.begin(), c.end());
    if(c.size() >= q) return c[q - 1] - c[0];
    return INT_MAX;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> k >> q;
    for(int i = 0; i < n; i++) cin >> a[i];
    int mn = INT_MAX;
    for(int i = 0; i < n; i++){
        mn = min(mn, go(a[i]));
    }
    cout << mn << endl;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void)
{
	char s[4];
	int i,r;
	scanf("%s",s);
	r=700;
	for(i=0;i<3;i++){
		if(s[i]=='o'){
			r+=100;
		}
	}
	printf("%d\n",r);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll getDays(ll y,ll m,ll d){
	if(m<=2){
		y--;
		m+=12;
	}
	ll dy=365*(y-1);
	ll c=y/100;
	ll dl=(y>>2)-c+(c>>2);
	ll dm=(m*979-1033)>>5;
	return dy+dl+dm+d-1;
}
int main(){
	for(string s;cin>>s,(s!="#");){
		if(count(s.begin(),s.end(),'.')==2){
			int y,m,d;
			sscanf(s.c_str(),"%d.%d.%d",&y,&m,&d);
			ll days=getDays(y,m,d)-getDays(2012,12,21);
			days%=20*18*20*20*13;
			int b,ka,t,w,ki,wei=20*18*20*20;
			b=days/wei;days%=wei;wei/=20;
			ka=days/wei;days%=wei;wei/=20;
			t=days/wei;days%=wei;wei/=18;
			w=days/wei;days%=wei;wei/=20;
			ki=days/wei;days%=wei;
			cout<<b<<"."<<ka<<"."<<t<<"."<<w<<"."<<ki<<"\n";
		}
		else{
			int b,ka,t,w,ki;
			sscanf(s.c_str(),"%d.%d.%d.%d.%d",&b,&ka,&t,&w,&ki);
			int days = 0;
			int wei = 1;
			days += wei * ki; wei *= 20;
			days += wei * w;  wei *= 18;
			days += wei * t;  wei *= 20;
			days += wei * ka; wei *= 20;
			days += wei * b;  wei * 13;
			int y = 2012 , m = 12 , d = 21;
			int table[] = {-1,31,28,31,30,31,30,31,31,30,31,30,31};
			while(days--){
				d++;
				if( d > table[m] + (m == 2 && ( y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) ) ){
					m++;
					d = 1;
				}
				if( m > 12 ){
					y++;
					m = 1;
				}
			}
			cout << y << "." << m << "." << d << endl;
		}
	}
	return 0;
}


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

using namespace std;
#define int long long
const int MOD = 1000000007;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int A[3];
	cin >> A[0] >> A[1] >> A[2];
	sort(A, A + 3);
	if ((A[0] == A[1] && A[1] != A[2]) || (A[0] != A[1] && A[1] == A[2])) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
}

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

int main(){
    int n;
    cin >> n;
    vector<int> X(n), A(n);
    for(int i = 0; i < n; i++){
        cin >> X[i];
        A[i] = X[i];
    }
    sort(A.begin(), A.end());
    for(int i = 0; i < n; i++){
        auto idx = lower_bound(A.begin(), A.end(), X[i]);
        //cout << idx - A.begin() << endl;
        if(idx - A.begin() < n / 2) cout << A[n / 2] << endl;
        else cout << A[(n / 2) - 1] << endl;
    }


    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

#define REP(i, N) for (int i = 0; i < N; i++)
#define REP1(i, N) for (int i = 1; i < N; i++)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ANS(a) cout << a << endl;
#define SORT(V) sort(V.begin(), V.end())
#define RSORT(V) sort(V.rbegin(), V.rend())

#define DBG(V) for (auto v : V) cout << v << " "; cout << endl

int N, D;
int X[10][10];

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

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < D; j++) {
      cin >> X[i][j];
    }
  }

  int ans = 0;
  for (int i = 0; i < N-1; i++) {
    for (int j = i+1; j < N; j++) {
      int sq = 0;
      for (int k = 0; k < D; k++) {
	sq += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
      }
      float rt = sqrt(sq);
      if (ceil(rt) == floor(rt)) {
	++ans;
      }
    }
  }

  ANS(ans);
  
  return 0;
}

/*
3 2
1 2
5 5
-2 8
 
 */


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
int main() {
	int n = ri();
	std::string s;
	std::cin >> s;
	int res = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = 0; k < 10; k++) {
				int cnt = 0;
				for (auto c : s) {
					if (cnt == 2 && c == k + '0') cnt++;
					if (cnt == 1 && c == j + '0') cnt++;
					if (cnt == 0 && c == i + '0') cnt++;
				}
				if (cnt == 3) res++;
			}
		}
	}
	std::cout << res << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int INF = 1001001001;

signed main()
{
    int n;
    cin >> n;
    
    int cnt[3] = {};
    
    rep(i, n){
        int a;
        cin >> a;
        if(a%4 == 0) cnt[2]++;
        else if(a%4 == 2) cnt[1]++;
        else cnt[0]++;
    }
    
    cout << ((cnt[0] <= cnt[2] || (cnt[0] == cnt[2] + 1 && cnt[1] == 0)) ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
from itertools import *

def loop(n):
  yield from repeat(n, (n-1)//2)
  if n & 1 == 0:
    yield n >> 1
  yield from repeat(0)

def branch(n, l):
  if n:
    yield 0
    l -= 3
    a, b = divmod(l, 2)
    s = 1
    for i in range(n+a+b):
      yield s
      if i < a:
        s += 2
      elif b and i==a:
        s += 1
      if n <= i:
        s -= 2
      elif i==n-1:
        s -= 1
  yield from repeat(0)

def b_to_b(n):
  n -= 1
  yield n
  yield from range(n, 0, -1)
  yield from repeat(0)

N, X, Y = map(int, input().split())
L = Y - X + 1
for p in islice(zip(loop(L), branch(X-1,L), branch(N-Y,L), b_to_b(N-L+1)), N-1):
  print(sum(p))


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

const int MAXN = 1e5 + 10;

int vis[MAXN][3],dp[MAXN][3],N,A[3][MAXN];

int solve(int pos,int last){

	if(pos == N + 1) return 0;

	if(vis[pos][last]) return dp[pos][last];
	vis[pos][last] = 1;

	int best = 0;

	for(int i = 0;i<3;i++){
		if(i != last) best = max(best, A[i][pos] + solve(pos+1,i) );
	}

	return dp[pos][last] = best;

}

int main(){

	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		scanf("%d %d %d",&A[0][i],&A[1][i],&A[2][i]);
	}

	printf("%d\n", max(solve(1,0), max(solve(1,1),solve(1,2)) ) );

	return 0;

}

Measured memory_bytes: 11520
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#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 <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    int S, W; cin >> S >> W;
    if(S <= W) cout << "unsafe" << endl;
    else cout << "safe" << endl;
    return 0;
}


Measured memory_bytes: 3632
n,k = [int(x) for x in input().split()]
mod = 10**9+7
MAX_N = 10**6
 
fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod
 
 
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
if k>=n:
  print(mod_comb_k(2*n-1,n,mod))
else:
  res=1
  for i in range(1,k+1):
    res = (res+mod_comb_k(n,i,mod)*mod_comb_k(n-1,n-i-1,mod))%mod
  print(res)

Measured memory_bytes: 101804
using System;
using System.Collections.Generic;
using System.Linq;

class D
{
	static void Main()
	{
		var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
		var js = Enumerable.Range(0, a[0]).Select(i => Console.ReadLine().Split().Select(int.Parse).ToArray()).Where(j => j[0] <= a[1]).GroupBy(j => j[0]).ToDictionary(g => g.Key, g => g.ToArray());

		var r = 0L;
		var l = new List<int>();
		for (var i = 1; i <= a[1]; i++)
		{
			if (js.ContainsKey(i))
				foreach (var j in js[i]) l.Insert(Search(l, j[1]), j[1]);

			if (!l.Any()) continue;
			r += l.Last();
			l.RemoveAt(l.Count - 1);
		}
		Console.WriteLine(r);
	}

	static int Search(IList<int> l, int v) => l.Any() ? Search(l, v, 0, l.Count) : 0;
	static int Search(IList<int> l, int v, int start, int count)
	{
		if (count == 1) return start + (v < l[start] ? 0 : 1);
		var c = count >> 1;
		var s = start + c;
		return v < l[s] ? Search(l, v, start, c) : Search(l, v, s, count - c);
	}
}


Measured memory_bytes: 43816
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<cstring>
using namespace std;

int main(void) {
	bool prime[100001];
	prime[0] = prime[1] = 0;
	int i;
	for(i = 2; i <= 100000; i++) {
		prime[i] = 1;
	}
	int  j, k, m, Q;
	cin >> Q;
	vector<int>l(Q);
	vector<int>r(Q);
	for (i = 2; i <= 316; i++) {
		if (prime[i]) {
			for (j = 2 * i; j <= 100000; j += i) {
				prime[j] = false;
			}
		}
	}
	
	
	int ans[100001];
	for (i = 0; i <= 100000; i++) {
		ans[i] = 0;
	}
	for (i = 3; i <= 100000; i += 2) {
		if (prime[i]&&prime[(i+1)/2]){ 
				ans[i] = ans[i - 2] + 1;
			}
		else{
			ans[i] = ans[i - 2];
		}
	}
	
	for (i = 0; i <= Q - 1; i++) {
		cin >> l[i] >> r[i];
	}
	for (i = 0; i <= Q - 1; i++) {
		if (prime[l[i]]&&prime[(l[i]+1)/2]) {
			cout << ans[r[i]] - ans[l[i]] + 1 << endl;
		}
		else {
			cout << ans[r[i]] - ans[l[i]] << endl;

		}
	}
	return 0;
}



Measured memory_bytes: 1920
N = int(input())
C = list(input())

ans = 0
r = N - 1
for l in range(N):
    if C[l] == 'R':
        continue
    r = max(l, r)
    while r > l and C[r] == 'W':
        r -= 1
    if r <= l:
        break
    C[l], C[r] = C[r], C[l]
    ans += 1

print(ans)


Measured memory_bytes: 10764
#include "bits/stdc++.h"
#include <cmath>
#include <iomanip>
using namespace std;
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define clr(a,v) memset(a, v, sizeof(a))
 
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define reflex ios_base::sync_with_stdio(false)
 
#define nl '\n'
#define ioi exit(0);
 

#define PI 3.14159265

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N= (int)5e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
//const int mod = 1000000007;
const ll linf = (ll)1e18 + 7;
 
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int kx[] = {-1,1,2,2,1,-1,-2,-2};
const int ky[] = {2,2,1,-1,-2,-2,-1,1};

struct dsu{
	int parent[N];
	void make_set(int v){
		parent[v] = v;
	}
	
	int find_set(int v){
		if(v == parent[v])
			return v;
		return find_set(parent[v]);
	}
	
	void union_sets(int a, int b){
		a = find_set(a);
		b = find_set(b);
		if(a != b)
			parent[b] = a;
	}
};



int main(){
	int n; cin>> n;
	if(n%2 == 0){
		cout<<n/2-1;
	}
	else
		cout<<n/2;
	return 0;
}
 
		


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

int main() {
  int N, M;
  cin >> N >> M;
  vector<long long> x(N), y(N), z(N);
  rep(i, N) cin >> x[i] >> y[i] >> z[i];

  long long ans = 0;
  rep(i, 2) {
    rep(j, 2) {
      rep(k, 2) {
        vector<long long> tmp(N);
        rep(l, N) {
          tmp[l] = (2*i-1) * x[l] + (2*j-1) * y[l] + (2*k-1) * z[l];
        }

        sort(all(tmp));

        long long res = 0;
        rep(l, M) {
          res += tmp[N-l-1];
        }

        ans = max(ans, res);
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<vector>

using namespace std;
using ll = long long;
const ll N = 1e6;
const double PI = acos(-1.0);
#define Test ll tesnum;tesnum = read();while(tesnum--)
ll read();

int main()
{
    long double x,y;
    cin>>x>>y;
    cout<<(ll)(x*y)<<endl;
    return "BT7274", NULL;
}

inline ll read() {
    ll hcy = 0, dia = 1;char boluo = getchar();
    while (!isdigit(boluo)) {if (boluo == '-')dia = -1;boluo = getchar();}
    while (isdigit(boluo)) {hcy = hcy * 10 + boluo - '0';boluo = getchar();}
    return hcy * dia;
}

Measured memory_bytes: 3780
#include<iostream>
#include<vector>
#include<string>
#include<math.h>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;

int main() {
	int K, S;
	cin >> K >> S;
	int count = 0;
	for (int i = 0; i <= K; i++) {
		for (int j = 0; j <= K; j++) {
			if (0 <= S-i-j && S-i-j <= K) {
					count++;
			}
		}
	}
	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
x = []
for i in range(m):
    x0, x1 = MAP()
    x.append([x0-1, x1-1])

r = [0]*n
w = [1]*n
t = [1]*n
r[0] = 1
w[0] = 0

for y in x:
    t[y[0]] -= 1
    t[y[1]] += 1

    if r[y[0]] > 0 and w[y[0]] == 0:
        r[y[0]] = 0
        r[y[1]] = 1
    elif r[y[0]] == 0 and w[y[0]] > 0:
        w[y[0]] -= 1
        w[y[1]] += 1
    elif r[y[0]] > 0 and w[y[0]] > 0:
        r[y[1]] = 1
        w[y[1]] += 1
    if t[y[0]] == 0:
        r[y[0]] = w[y[0]] = 0

ans = sum(r)
print(ans)

Measured memory_bytes: 27328