akhauriyash/Code-Regression huggingface dataset:
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <iomanip>
#include <iostream>
#include <limits>
#include <math.h>
#include <memory>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = int64_t;
using ull = uint64_t;

template<typename T>
vector<T> make_vec_nd(T init, size_t size) {
    return vector<T>(size, init);
}
template<typename T, typename... Args>
auto make_vec_nd(T init, size_t size, Args... rest) {
    auto inner = make_vec_nd(init, rest...);
    return vector<decltype(inner)>(size, inner);
}

int main() {
    ll N;
    cin >> N;
    vector<ll> ais;
    ll sum = 0;
    for (ll i = 0; i < N; i++) {
        ll ai;
        cin >> ai;
        ais.push_back(ai);
        sum += ai;
    }
    auto dp = make_vec_nd((ll)0, ais.size()+1, ais.size()+1);
    for (ll i = N-1; i >= 0; i--) {
        for (ll j = i+1; j <= N; j++) {
            dp[i][j] = max(-dp[i+1][j] + ais[i], -dp[i][j-1] + ais[j-1]);
        }
    }
    cout << dp[0][N] << endl;
}



Measured memory_bytes: 70784
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
using namespace std;

#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(ll (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define opf(i) cout<<fixed<<setprecision(10)<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;

//


// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    ll ans=0;
    vec(A,N);
    vec(B,N);
    vec(C,N);
    rep(i,N){
      cin>>A[i];A[i]--;
    }
    rep(i,N){
      cin>>B[i];ans+=B[i];
    }
    rep(i,N-1){
      cin>>C[i];
    }
    //ll ans=0;
    rep(i,N){
      
      if(i>=1){
        if(A[i]-A[i-1]==1)ans+=C[A[i-1]];
      }
    }
    op(ans)
    return 0;
}


Measured memory_bytes: 256
def main():
    s = input()
    t = input()

    dt = dict()
    ds = dict()
    for i in range(len(s)):
        if t[i] not in dt:
            dt[t[i]] = s[i]
        else:
            if dt[t[i]] != s[i]:
                print("No")
                return

        if s[i] not in ds:
            ds[s[i]] = t[i]
        else:
            if ds[s[i]] != t[i]:
                print("No")
                return

    print("Yes")

if __name__ == "__main__":
    main()

Measured memory_bytes: 3632
#include <stdio.h>
#include <string.h>

int main()
{

    int n,l,i,sum;
    scanf("%d%d",&n,&l);

    if(l>=0)
        i=0;
    else
    {
        if(0<=n-1+l)
            i=-l;
        else
            i=n-1;
    }
    sum=(n*(n-1))/2+(n-1)*l-i;
    printf("%d",sum);
}


Measured memory_bytes: 128
n, x, m = map(int, input().split())

num, lst = set(), []
for i in range(n):
    num.add(x), lst.append(x)
    x = x ** 2 % m
    if x in lst:
        cnt, idx = i + 1, lst.index(x)
        break

ans = sum(num)
if x in lst:
    div, mod = divmod(n - cnt, len(lst) - idx)
    ans += sum(lst[idx:]) * div
    ans += sum(lst[idx:idx + mod])
print(ans)


Measured memory_bytes: 80444
#include<math.h>
#include<bits/stdc++.h>
#include<string>

using namespace std;
int main()
{
  long long int n,d,m,s;
 cin>>d>>n;
 if(n==100)
 {
     n++;
 }
 m = ( long long int)(pow(100,d) + 0.5);
 s=m*n;
 cout<<s;



    return 0;

}











Measured memory_bytes: 256
#include <iostream>

using namespace std;

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

signed main() {
  int n;
  cin >> n;
  char c[n];
  rep(i,n) cin >> c[i];
  
  int s = 0, r = 0;
  rep(i,n) if(c[i] == 'R') s += 1;
  rep(i,s) if(c[i] == 'R') r += 1;
  cout << s - r << endl;
  return 0;
}

Measured memory_bytes: 3332
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>

#define ll long long 

using namespace std;

int n;
double N[3000];
double dp[3000][3000];
bool dpb[3000][3000];

double solve(int p, int k){
  if(p >= n && k != 0)
    return 1;

  if(k == 0){
    if(p < n)
      return N[p] * solve(p+1, k);
    else
      return 1;
  }

  if(dpb[p][k])
    return dp[p][k];
  
  dpb[p][k] = 1;
  return dp[p][k] = (1-N[p]) * solve(p+1, k-1) + N[p] * solve(p+1, k);
} 

int main()
{
    cin >> n;

    memset(dpb, 0, sizeof dpb);

    for(int i = 0; i < n; i++)
      cin >> N[i];
    
    cout << setprecision(10) << fixed << solve(0, n/2) << endl;
    
    return 0;
}

Measured memory_bytes: 51036
#include <stdio.h>
int main(){
  int m,f,r;
  char grade;
 
 
  while(1){
    scanf("%d %d %d",&m,&f,&r);
 
    if(m==-1 && f==-1 && r==-1)break;
 
    if(m==-1 || f==-1)grade='F';
    else if(m+f>=80)grade='A';
    else if(m+f>=65 && m+f<80)grade='B';
    else if((m+f>=50 && m+f<65)||(m+f>=30 && m+f<50 && r>=50))grade='C';
    else if(m+f>=30 && m+f<50 && r<50)grade='D';
    else grade='F';
 
    printf("%c\n",grade);
  }
  return 0;
}

Measured memory_bytes: 600
while True:
    n = int(input())
    max = 0
    min = 1000
    sum = 0
    if n == 0:
       break
    for i in range(n):

        s = int(input())
        sum += s
        if s < min:
            min = s
        if max < s:
            max = s
    ave = (sum - min - max) // (n - 2)
    print(ave)


Measured memory_bytes: 5596
#include<stdio.h>
int main(){
 int a,b,c,d;
 scanf("%d",&a);
 scanf("%d",&b);
 scanf("%d",&c);
 d = a*b;
 if(a*b < c){
   printf("%d", d);
 }else if(b*a > c){
   printf("%d",c);
 }else if(b*a == c){
   printf("%d", d);
 }
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int sum=0;
    int x,y;
    cin>>x>>y;
    if(x==1) sum+=300000;
    if(x==2) sum+=200000;
    if(x==3) sum+=100000;
    if(y==1) sum+=300000;
    if(y==2) sum+=200000;
    if(y==3) sum+=100000;
    if(x==1&&y==1) sum+=400000;
    cout<<sum;
}



Measured memory_bytes: 256
n=int(input())
L=input().split( )

R=[]
i=n-1
while 0<=i:
    r=L.pop(i)
    R.append(r)
    i-=1
for i in range(n):
    if i!=n-1:
        print(R[i],end=' ')
    else:
        print(R[i])



Measured memory_bytes: 5612
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>
#include<queue>
#include<functional>
#include<iso646.h>
#include<bitset>

using namespace std;

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

const double INF = 1e16;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;

const ll MAX_N = 1e5 + 10;
ll dp[MAX_N];

vector<vll> E;


void init() {
	for (ll i = 0; i < MAX_N; i++) {
		dp[i] = -1;
	}
}

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

ll longest(ll x) {
	if (dp[x] != -1) {
		return dp[x];
	}
	else {
		ll len = 0;
		dp[x] = len;
		for (auto e : E[x]) {
			if (dp[e] != -1) {
				chmax(len, dp[e] + 1);
			}
			else {
				chmax(len, longest(e) + 1);
			}
		}
		dp[x] = len;
		return len;
	}
}

int main() {
	ll i, j;
	init();
	ll N, M;
	cin >> N >> M;
	vll X, Y;
	E.assign(N + 1, vll());
	for (i = 0; i < M; i++) {
		ll x, y;
		cin >> x >> y;
		X.push_back(x);
		Y.push_back(y);
		E[x].push_back(y);
	}

	ll ans = 0;
	for (i = 1; i <= N; i++) {
		chmax(ans, longest(i));
	}
	cout << ans << endl;

	return 0;
}


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

#define ALL(v) v.begin(), v.end()
#define V vector
#define P pair
#define ld long double
#define ll long long

const int MOD =  1000000007;
const int IINF = INT_MAX;
const ll INF = 1LL << 60;


int main() {
    int n, m, x, y; cin >> n >> m >> x >> y;
    V<int> vx(n);
    for(int i = 0; i < n; i++) cin >> vx[i];
    V<int> vy(m);
    for(int i = 0; i < m; i++) cin >> vy[i];
    vx.push_back(x);
    vy.push_back(y);

    int xmax = *max_element(ALL(vx));
    int ymix = *min_element(ALL(vy));

    if(xmax < ymix){
        cout << "No War" << endl;
    }else{
        cout << "War" << endl;
    }



    return 0;
}


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

int main(void){
    int R;
    string ans;
    cin >> R;
    if(R < 1200){
        ans = "ABC";
    }
    else if(R >= 1200 && R < 2800){
        ans = "ARC";
    }
    else{
        ans = "AGC";
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N,Q;
  cin>>N>>Q;
  vector<set<int>> A(N);
  for(int i=0;i<N-1;i++){
    int a,b;
    cin>>a>>b;
    A[a-1].insert(b-1);
    A[b-1].insert(a-1);
  }
  vector<int> B(N);
  for(int i=0;i<Q;i++){
    int p,x;
    cin>>p>>x;
    B[p-1]+=x;
  }
  queue<int> C;
  C.push(0);
  vector<bool> D(N,true);
  while(!C.empty()){
    int I=C.front();
    C.pop();
    D[I]=false;
    for(int i:A[I])
      if(D[i]){
        C.push(i);
        B[i]+=B[I];
      }
  }
  for(int i=0;i<N;i++){
    cout<<B[i];
    if(i==N-1)
      cout<<endl;
    else
      cout<<' ';
  }
}

Measured memory_bytes: 34660
#include <iostream>
#include <map>
#include <climits>
#include <string>
using namespace std;
 
unsigned long long to(string w , int base){
    unsigned long long ans = 0;
    for(int i = 0 ; i < w.size() ; i++) ans = ans * base + (w[i] >= 'A' ? w[i] - 'A' + 10 : w[i] - '0');
    return ans;
}
 
map<int,int> factor(int n){
    map<int,int> w;
    for(int i = 2 ; i*i<=n ; i++)
        while(n%i==0) w[i]++ , n /= i;
    if(n!=1) w[n]++;
    return w;
}
 
int main(){
    int n;
    string m;
    while(cin >> n >> m, n){
        unsigned long long v = to(m,n) , ans = -1;
        map<int,int> r = factor(n);
        for( map<int,int>::iterator it = r.begin() ; it != r.end() ; ++it){
            int a = it->first;
            int d = it->second;
            unsigned long long t = v;
            unsigned long long ok = 0;
            while(t){ ok += (t / a) ; t /= a;}
            ans = min(ok / d , ans);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 1204
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin
from math import cos, sin, atan2, pi

PI2 = pi / 2
L = [None, (1.0, 0.0)]
for _ in range(2, 1001):
    x, y = L[-1]
    rad = atan2(y, x) + PI2
    L.append((x + cos(rad), y + sin(rad)))

for line in stdin:
    n = int(line)
    if n == -1:
        break
    print('{:0.2f}\n{:0.2f}'.format(*L[n]))

Measured memory_bytes: 4644
N,K = map(int,input().split())

Bcnt = [[0 for j in range(K+1)] for i in range(K+1)]
Wcnt = [[0 for j in range(K+1)] for i in range(K+1)]

for i in range(N):
    x,y,c = input().split()
    x,y = int(x),int(y)
    if ((x-x%K)/K + (y-y%K)/K)%2:
        if c == 'W':
            Bcnt[x%K+1][y%K+1] += 1
        else:
            Wcnt[x%K+1][y%K+1] += 1
    else:
        if c == 'W':
            Wcnt[x%K+1][y%K+1] += 1
        else:
            Bcnt[x%K+1][y%K+1] += 1

for i in range(K):
    for j in range(K):
        Bcnt[i+1][j+1] += Bcnt[i+1][j] + Bcnt[i][j+1] - Bcnt[i][j]
        Wcnt[i+1][j+1] += Wcnt[i+1][j] + Wcnt[i][j+1] - Wcnt[i][j]

ans = 0
Bs = Bcnt[K][K]
Ws = Wcnt[K][K]

for i in range(K+1):
    for j in range(K+1):
        B = Bcnt[K][K] - Bcnt[K][j] - Bcnt[i][K] + 2*Bcnt[i][j]
        W = Wcnt[K][K] - Wcnt[K][j] - Wcnt[i][K] + 2*Wcnt[i][j]
        ans = max(ans, B+Ws-W, W+Bs-B)

print(ans)


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

using namespace std;
using ll = long long;
using ull = unsigned long long;

typedef pair<ll, ll> P;
typedef pair<double, double >pd;
typedef pair<string, string> sP;
typedef pair<ll, P> PP;
typedef pair<P, P> PPP;

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 5e14;
const double eps = 1e-10;
const double PI = acos(-1);
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second

ll a, b, c, n, m;
string s, t;

int main() {
	cin >> a;
	if (a < 1200) {
		cout << "ABC" << endl;
		return 0;
	}
	if (a < 2800) {
		cout << "ARC" << endl;
		return 0;
	}
	cout << "AGC" << endl;
	return 0;
}


Measured memory_bytes: 764
'''
問題：
    英小文字からなる文字列 S があります。

    S の長さが K 以下であれば、Sをそのまま出力してください。
    S の長さが K を上回っているならば、先頭 K 文字だけを切り出し、
    末尾に ... を付加して出力してください。
'''

'''
制約：
    K は 1 以上 100 以下の整数
    S は英小文字からなる文字列
    S の長さは 1 以上 100 以下
'''

# 標準入力からK, S を取得する
k = int(input())
s = str(input())

result = ""
if len(s) <= k:
    result = s
else:
    for i in range(0, k):
        result += s[i]
    result += "..."

print(result)


Measured memory_bytes: 8952
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define ALL(x)				(x).begin(),(x).end()
#define REP(i, n)			for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)		for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF					(ll)1e9
#define EPS					(double)1e-9
#define MOD					(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)			(((((x))+((n)-1))/(n)))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)			(((((x))+((n)-1))/(n))*(n))	/* Nの倍数に切り上げ */
#define FloorN(x, n)		((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)			(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)			(!IsOdd((x)))						
#define M_PI				3.14159265358979323846
typedef long long			ll;
typedef pair<ll, ll>		P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
struct SWAP_INFO {
	int val;
	bool isRed;
	int idx;
};

ll moveOne(int to, int from, vector<SWAP_INFO> &swapInfo)
{
	ll cnt = 0;
	for (int i = from; to < i; i--) {
		swap(swapInfo[i], swapInfo[i - 1]);
		cnt++;
	}
	return cnt;
}

bool sortOne(int N, vector<SWAP_INFO> &swapInfo, ll &swapCntOne, vector<int>	&sortedVal)
{
	swapCntOne = 0;
	REP(i, N) {
		bool isFind = false;
		int valOne = sortedVal[i];
		REPN(j, i, N) {
			if (valOne == swapInfo[j].val) {
				int diff = abs(swapInfo[j].idx - i);
				if (swapInfo[j].isRed) {
					if (IsEven(diff)) {
						swapCntOne += moveOne(i, j, swapInfo);
						isFind = true;
						break;
					}
				} else {
					if (IsOdd(diff)) {
						swapCntOne += moveOne(i, j, swapInfo);
						isFind = true;
						break;
					}
				}
			}
		}

		if (!isFind) {
			return false;
		}
	}

	return true;
}

// メイン
int main()
{
	int N;
	cin >> N;
	vector<int>	A(N), B(N);
	REP(i, N) cin >> A[i];
	REP(i, N) cin >> B[i];

	ll ans = INF;
	for (ll bitPtn = 0; bitPtn < ((ll)1 << N); bitPtn++) {
		vector<SWAP_INFO>	swapInfo(N);
		vector<int>	sortedVal(N);
		REP(i, N) {
			auto &one = swapInfo[i];
			if (bitPtn & ((ll)1 << i)) {
				one.val = sortedVal[i] = A[i];
				one.isRed = true;
			} else {
				one.val = sortedVal[i] = B[i];
				one.isRed = false;
			} 
			one.idx = i;
		}

		ll swapCntOne = 0;
		sort(ALL(sortedVal));
		if (sortOne(N, swapInfo, swapCntOne, sortedVal)) {
			ans = min(ans, swapCntOne);
		}
	}

	if (ans == INF) {
		cout << -1 << endl;
	} else {
		cout << ans << endl;
	}

	return 0;
}



Measured memory_bytes: 256
import Data.List.Split
import Data.Maybe
import qualified Data.ByteString.Char8 as B
main=mapM_(putStr.solve).chunksOf 3.map(map(fst.fromJust.B.readInt).B.words).B.lines=<<B.getContents
solve[[h,w],[n],as]=unlines.map(unwords.map show)$zipWith($)(cycle[id,reverse])$chunksOf w$concat$zipWith replicate as [1..n]

Measured memory_bytes: 1788
#include <stdio.h>
//prototype
int main(void);

int main(void){
  int n, x;
  int i, j, k;
  int sum;
  int count = 0;

  while (1) {
    scanf("%d %d", &n, &x);

    //exit condition
    if (n == 0 && x == 0) {
      break;
    }

    for (i = 1; i <= n - 2; i++) {
      for (j = i + 1; j <= n - 1; j++) {
        for (k = j + 1; k <= n; k++) {
          //calc
          sum = i + j + k;
          //judge process
          if (sum == x) { count++; }
        }
      }
    }

    printf("%d\n", count);

    //initialize count
    count = 0;
  }

  return 0;
}



Measured memory_bytes: 2040
#include<stdio.h>

int main(){

  int n;
  scanf("%d",&n);

  int count = 0;

  for(int i=1; i<=n; i++){
    int tmp = 0;
    if(i % 2 != 0 ){
    for(int j=1; j<=n; j++){
      if( i % j == 0 ) tmp++;
    }
    }
    if(tmp == 8) count ++;
  }

  printf("%d",count);

  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        // Here your code !
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        if (a==b)
            System.out.println("a == b");
        else if (a>b) 
            System.out.println("a > b");
        else
            System.out.println("a < b");
    
    }
}

Measured memory_bytes: 26192
x = gets.to_s
length = x.length
minimum_num = 754
(0..length-3).each do |a|
  array_start = 0+a
  array_end = 2+a
  three_num = x[array_start..array_end].to_i
  caluculated_num = (three_num - 753).abs
  minimum_num = caluculated_num if minimum_num > caluculated_num
end


puts minimum_num

Measured memory_bytes: 1788
ii = lambda:int(input())
mi = lambda:list(map(int,input().split()))
ix = lambda x:list(input() for _ in range(x))
mix = lambda x:list(mi() for _ in range(x))
iix = lambda x:list(int(input()) for _ in range(x))
##########
def main(a,b,k):
    res = []
    for i in range(1,min(a,b)+1):
        if a % i == 0 and b % i == 0:
            res.append(i)
    return res[-k]        
            
a,b,k = mi()
print(main(a,b,k))

Measured memory_bytes: 3064
#include <string>
#include <iostream>

using namespace std;

int main(){
    int n, i, j, check=0;
    string w[100];

    cin >> n;
    for(i=0; i<n; i++)
        cin >> w[i];
    
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if(i != j){
                if(w[i] == w[j])
                    check=1;
            }
        }
    }

    for(i=1; i<n; i++){
        j=0;
        while(w[i-1][j] != '\0')
            j++;
        j--;

        if(w[i-1][j] != w[i][0])
            check=1;
    }

    if(check == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

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


vector<ll> fact(200000+10,1);
vector<ll> ifact(200000+10,1);

ll mpow(ll x, ll n){ //x^n(mod mo) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % mo;
        x = x*x % mo;
        n = n >> 1;
    }
    return ans;
}


ll combi(ll n, ll r) {
  if(r == 0)return 1;
  if ( r * 2 > n ) r = n - r;
  ll dividend = 1;
  ll divisor  = 1;
  for ( ll i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    dividend %= mo;
    divisor  *= i;
    divisor %= mo;
  }
  return (dividend * mpow(divisor, mo-2)) % mo;
}

void prepare(ll n, ll k){
    for(int i=1;i<=n;i++){
        fact[i] = (i*fact[i-1]) % mo;
    }
    ifact[n] = mpow(fact[n], mo-2);
    for(int i=n-1; i>0; i--){
        ifact[i] = ((i+1)*ifact[i+1]) % mo;
    }
}
ll combinate(ll n, ll k){
    return (((fact[n]*ifact[n-k]) % mo)*ifact[k]) % mo;
}

int main(){
    ll n,k;
    cin >> n >> k;
    /*ll kk = k;
    if(n-1 < kk){
        cout << "b"<< endl;
        
        while(n-1 < kk){
            kk = kk - (n-1);
        }
        cout << "a"<< endl;

        k = n-1 - (kk%2);
    }*/
    k = min(k,n-1);
    prepare(n,k);

    ll sum = 0;
    for(ll j=0;j<=k;j++){
        //cout << j << endl;
        ll tmp = combinate(n,j);
        //cout << tmp << endl;
        //ll ue = 1;
        //ll shita = 1;
        /*
        for(ll i=n-j+1;i<=2*n-2*j-1;i++){
            ue *= i;
            ue %= mo;
        }
        for(ll i=1;i<=n-j-1;i++){
            shita *= i;
            shita %= mo;
        }
        ll res = (ue * mpow(shita , mo-2)) % mo;*/
        ll res = combinate(n-1,j);
        sum += (res*tmp) % mo;
        sum %= mo;
        /*
        (n+k-1)!/(n!*(k-1)!)

        (n-j+n-j-1)!/(n-j)!*(n-j-1)!
        */
    }
    cout << sum << endl;

}


Measured memory_bytes: 3328
/*input
2
*/
fn read_line() -> String {
    let mut return_ = format!("");
    std::io::stdin().read_line(&mut return_).ok();
    return_
}

fn main() {
    let r: f64 = read_line().trim().parse().unwrap();
    println!(
        "{:.5} {:.5}",
        r * r * std::f64::consts::PI,
        r * 2.0 * std::f64::consts::PI
    );
}



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

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

 int a, b;

 cin >> a >> b;


 for(int i=a; i<=b; ++i){
   if(i%k == 0){
     cout << "OK";
     return 0;
   }
 }
 cout << "NG";



}



Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

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


	ll N;
	cin >> N;
	ll base = 1;
	string res = "";
	if(N == 0) {
		cout << 0 << endl;
		return 0;
	}
	while(N != 0) {
		if(N % (base * 2) == 0) res = '0' + res;
		else {
			res = '1' + res;
			N -= base;
		}

		base *= -2;
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <random>
#include <cstdio>
#include <cstring>
#include <cmath>

// for i in f..<t { as swift
#define forin(i, f, t) for(auto i = f; i < t; i++)

using namespace std;
using ll = long long;
using XY = pair<int, int>;

int main() {
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    auto count = 0;
    forin(i, 0, a + 1) {
        forin(j, 0, b + 1) {
            forin(k, 0, c + 1) {
                if (500 * i + 100 * j + 50 * k == x)
                    count++;
            }
        }
    }
    
    cout << count << endl;
}



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

int main(void){
	int sx,sy,tx,ty,i;
	cin >> sx >> sy >> tx >> ty;
	for(i=(tx-sx); i>0; --i){
		cout << 'R';
	}
	for(i=(ty-sy); i>0; --i){
		cout << 'U';
	}
	for(i=(tx-sx); i>0; --i){
		cout << 'L';
	}
	for(i=(ty-sy); i>0; --i){
		cout << 'D';
	}
	cout << 'D';
	for(i=(tx-sx); i>0; --i){
		cout << 'R';
	}
	cout << 'R';
	cout << 'U';
	for(i=(ty-sy); i>0; --i){
		cout << 'U';
	}
	cout << 'L';
	cout << 'U';
	for(i=(tx-sx); i>0; --i){
		cout << 'L';
	}
	cout << 'L';
	cout << 'D';
	for(i=(ty-sy); i>0; --i){
		cout << 'D';
	}
	cout << 'R';
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int
main()
{
    uint64_t h,w;
    cin >> h >> w;

    if(h == 1 || w == 1){
        cout << "1" << endl;
        return 0;
    }

    uint64_t x1 = w * (h/2);
    if(h%2) {
        if(w > 2){
            if(w%2)
                x1 += (w/2 + 1);
            else
                x1 += w/2;
        } else
            x1 += w/2;
    }

    cout << x1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	if (a < b){
		if (b < c){
			printf("Yes\n");
		}
		else if (b >= c){
			printf("No\n");
		}
		else if (a > b){
			printf("No\n");
		}
	}
	else printf("No\n");
	return 0;
	}

Measured memory_bytes: 2616
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using ull = unsigned long long;
using ll = long long;
using namespace std;

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

int main(void) {

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

    sort(a.begin(), a.end(), greater<int>());

    int ans = a[0];
    for(int i = 1; i < n; ++i) {
        ans = gcd(ans, a[i]);
        // cout << ans << endl;
    }

    cout << ans << endl;

    return 0;
}

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

using namespace std;

int h, w;
char mp[100][100];

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

void dfs(int y, int x, char fruit)
{
    if (y < 0 || y >= h || x < 0 || x >= w || mp[y][x] != fruit) return;
    mp[y][x] = ' ';
    for (int i = 0; i < 4; ++i) dfs(y + dy[i], x + dx[i], fruit);
}

int main()
{
    while (cin >> h >> w, h || w) {
        for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) cin >> mp[i][j];

        int cnt = 0;

        for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
            if (mp[i][j] != ' ') {
                cnt++;
                dfs(i, j, mp[i][j]);
            }
        }

        printf("%d\n", cnt);
    } 
}

Measured memory_bytes: 1616
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX
#define INFL LLONG_MAX
typedef long long ll;
using namespace std;

#define MOD 1000000007


int main(){


  string s,t;
  int n;
  cin >> n;
  cin >> s >> t;
    string moji="";

rep(i,n){
    moji.push_back(s.at(i));
    moji.push_back(t.at(i));

  }



  cout << moji << endl ;


  }


Measured memory_bytes: 3572
import std.stdio, std.algorithm, std.range, std.conv, std.string, std.math, std.container, std.typecons;
import core.stdc.stdio;
// foreach, foreach_reverse, writeln

alias P = Tuple!(int,int);

int k;
class UnionFind {
	int score;
	int[] data, cnt;
	this(int n) {
		data = new int[n];
		cnt = new int[n];
		data[] = -1;
		score = 0;
	}
	int find(int v) {
		if (data[v] < 0) return v;
		return data[v] = find(data[v]);
	}
	int calc(int v) {
		v = find(v);
		int size = -data[v];
		return min(max(0,size-k+1), cnt[v]);
	}
	void add(int v, int x) {
		score -= calc(v);
		cnt[find(v)] += x;
		score += calc(v);
	}
	bool join(int u, int v) {
		u = find(u);
		v = find(v);
		if (u == v) return false;
		if (data[u] > data[v]) swap(u,v);
		score -= calc(u);
		score -= calc(v);
		data[u] += data[v];
		cnt[u] += cnt[v];
		data[v] = u;
		score += calc(u);
		return true;
	}
}

void main() {
	int n, q;
	scanf("%d%d%d", &n, &k, &q);
	int[] a = new int[n];
	foreach (i; 0..n) scanf("%d", &a[i]);
	int l = -1, r = 1_000_000_000;
	bool judge(int x) {
		UnionFind uf = new UnionFind(n);
		P[] events;
		foreach (i; 0..n) {
			events ~= P(a[i],n+i);
			events ~= P(a[i]-x,i);
		}
		events.sort.reverse;
		bool[] added = new bool[n];
		foreach (event; events) {
			int i = event[1];
			if (i < n) {
				uf.add(i,-1);
				//writeln("del ",i," ",uf.score);
			} else {
				i -= n;
				uf.add(i,1);
				if (i && added[i-1]) uf.join(i-1,i);
				if (i+1 < n && added[i+1]) uf.join(i+1,i);
				added[i] = true;
				//writeln("add ",i," ",uf.score);
				if (uf.score >= q) return true;
			}
		}
		return false;
	}
	while (l+1 < r) {
		int mid = (l+r)/2;
		if (judge(mid)) r = mid; else l = mid;
	}
	writeln(r);
}

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

//#define kk
#define FOR(i, n) for(int i=1; i<=n; i++)
#define ff first
#define ss second
#define ll int
typedef pair<int, int> pi;

int arr[100001];
int dp[100001];

void solve(){
	int n, k;
	cin>>n>>k;
	
	
	FOR(i, n) cin>>arr[i];
	
	dp[1]=0;
	
	for(int i=2; i<=n; i++){
		int ans=INT_MAX;
		for(int j=1; j<=k; j++){
			if(i-j>=1){
				ans=min(dp[i-j]+abs(arr[i]-arr[i-j]), ans);
			}
			else break;
		}
		dp[i]=ans;
	}
	
	//FOR(i, n) cout<<dp[i]<<" ";
	//cout<<endl; 
	
	cout<<dp[n]<<endl;	
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	#ifdef kk
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	
	int T=1;
	//cin>>T;
	
	while(T--){
		solve();
	}
}


Measured memory_bytes: 4436
import itertools

n = int(input())

x = []
y = []
for i in range(n):
    xx, yy = map(int,input().split())
    x.append(xx)
    y.append(yy)

total = 0
num = [i for i in range(n)]
for v in itertools.permutations(num, n):
    d = 0
    for i in range(n-1):
        cf, ct = v[i], v[i+1]
        d += ((x[ct] - x[cf])**2 + (y[ct] - y[cf])**2)**0.5
    total += d
for i in range(n, 1, -1):
    total /= i
print(total)

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

struct P{
    int alpha, beta;
};

P dp[32][32][32][32];

P rec(int l, int t, int r, int b, int acc, vector<vector<int> >& a){
    
    //cout << l << " " << t << " " << r << " " << b << " " << endl;
    P res;
    res.alpha = 0;
    res.beta = 0;    
    int sum = 0;
    //合計がアなら0を返す
    for(int i = t; i < b; i++){    
        for(int j = l; j < r; j++){
            sum += a[i][j];
        }
    }

    if(sum < acc){
        return res;
    }

    //分けて再帰呼び出し
    
    //縦
    for(int i = t + 1; i < b; i++){

        P left, right;

        //左
        if(dp[l][t][r][i].alpha != 0){
            left = dp[l][t][r][i];            
        }else{
            left = rec(l, t, r, i, acc, a);
        }

        //右
        if(dp[l][i][r][b].alpha != 0){
            right = dp[l][i][r][b];
        }else{
            right = rec(l, i, r, b, acc, a);
        }

        if(left.alpha != 0 && right.alpha != 0){
            if(res.alpha < left.alpha + right.alpha){
                res.alpha = left.alpha + right.alpha;
                res.beta = min(left.beta, right.beta);
            }else if(res.alpha == left.alpha + right.alpha){
                res.beta = max(res.beta, min(left.beta, right.beta));
            }
        }
    }

    //横
    for(int i = l + 1; i < r; i++){

        P left, right;

        //左
        if(dp[l][t][i][b].alpha != 0){
            left = dp[l][t][i][b];            
        }else{
            left = rec(l, t, i, b, acc, a);
        }

        //右
        if(dp[i][t][r][b].alpha != 0){
            right = dp[i][t][r][b];
        }else{
            right = rec(i, t, r, b, acc, a);
        }

        if(left.alpha != 0 && right.alpha != 0){
            if(res.alpha < left.alpha + right.alpha){
                res.alpha = left.alpha + right.alpha;
                res.beta = min(left.beta, right.beta);
            }else if(res.alpha == left.alpha + right.alpha){
                res.beta = max(res.beta, min(left.beta, right.beta));
            }
        }
    }

    if(res.alpha == 0){
        res.alpha = 1;
        res.beta = sum - acc;
    }

    dp[l][t][r][b] = res;
    return res;
}

int main(){

    while(1){
        
        memset(dp, 0, sizeof(dp));

        int num, power;
        int h, w, s; cin >> h >> w >> s;
        if(!h) break;

        int sum = 0;
        vector<vector<int> > a(h, vector<int> (w));
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> a[i][j];
                sum += a[i][j];
            }
        }

        int acc = sum - s;
        P ans = rec(0, 0, w, h, acc, a);
        
        //答え
        cout << ans.alpha << " " << ans.beta << endl;
    }

    return 0;
}


Measured memory_bytes: 11316
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: i32 = read();
    println!("{}", n.pow(3));
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include <iostream>
using namespace std;
int main(){
  int num[] = {0,1,3,1,2,1,2,1,1,2,1,2,1};
  int A,B;
  cin >> A >> B;
  if(num[A] == num[B]){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

}

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

int main(){
  string S;
  cin >>S;
  int sum=0;
  
  for (int i=0;i<S.size();i++){
    if (i%2==0){
      if  (S.at(i)!='L'){
        sum++;
      }
    }
    else {
      if (S.at(i)!='R'){
        sum++;
      }
    }
  }
  if (sum==S.size()){
    cout << "Yes" <<endl;
  }
  else{
    cout << "No" <<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;

ll a[N], b[N], c[N];
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll x, y, z, k;
    cin >> x >> y >> z >> k;
    for(int i = 0; i < x; i++){
        cin >> a[i];
    }
    for(int i = 0; i < y; i++){
        cin >> b[i];
    }
    for(int i = 0; i < z; i++){
        cin >> c[i];
    }
    vector<ll> v;
    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            v.push_back(0LL + a[i] + b[j]);
        }
    }
    sort(v.begin(), v.end());
    vector<ll> ans;
    for(int i = v.size() - 1; i >= max((int)v.size() - 3005, 0); i--){
        for(int j = 0; j < z; j++){
            // cout << v[i] + c[j] << '\n';
            ans.push_back(v[i] + c[j]);
        }
    }
    // return 0;
    sort(ans.rbegin(), ans.rend());
    for(int i = 0; i < k; i++){
        cout << ans[i] << '\n';
    }

    return 0;
}


Measured memory_bytes: 43236
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let h: usize = itr.next().unwrap().parse().unwrap();
    let w: usize = itr.next().unwrap().parse().unwrap();
    let s: Vec<Vec<char>> = (0..h)
        .map(|_| itr.next().unwrap().chars().collect())
        .collect();

    let mut dist: Vec<Vec<usize>> = vec![vec![500; w + 1]; h + 1];
    let mut que = std::collections::VecDeque::new();
    let dx = [1, 0, -1, 0].to_vec();
    let dy = [0, -1, 0, 1].to_vec();

    dist[0][0] = 1;
    que.push_back((0, 0));

    while let Some((y, x)) = que.pop_front() {
        for i in 0..4 {
            let nx = x as isize + dx[i];
            let ny = y as isize + dy[i];
            if 0 <= nx
                && nx < w as isize
                && 0 <= ny
                && ny < h as isize
                && s[ny as usize][nx as usize] == '.'
                && dist[ny as usize][nx as usize] == 500
            {
                dist[ny as usize][nx as usize] = dist[y][x] + 1;
                que.push_back((ny as usize, nx as usize));
            }
        }
    }
    if dist[h - 1][w - 1] == 500 {
        println!("-1");
        return;
    }
    let mut ans = 0;
    for c in s {
        for i in c {
            if i == '.' {
                ans += 1;
            }
        }
    }
    println!("{}", ans - dist[h - 1][w - 1]);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

signed main(){

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

  reverse(a.begin(),a.end());
  reverse(b.begin(),b.end());
  int ans = 0, add = 0;
  for(int i = 0; i < n; i++){
    a[i] += add;
    if(a[i]%b[i] == 0) continue;
    if(a[i] < b[i]){
      ans += b[i] - a[i];
      add += b[i] - a[i];
    }else {
      int res = (a[i] / b[i] + 1) * b[i];
      ans += res - a[i];
      add += res - a[i];
    }
  }
  cout << ans << endl;

  return 0;
}


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

int main(){
    ll n, a, b;
    cin >> n >> a >> b;
    if(a > b || (a < b && n == 1)){
        cout << 0 << endl;
    }else{
        cout << (n-2)*(b-a)+1<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <vector>
#include <algorithm> // sort
#include <map>
using namespace std;

using ll = long long int;
using ppi=pair<ll,ll>;
using pql =priority_queue<ll, vector<ll>, greater<ll>>;
using pq=priority_queue<ll>;

int main(){
    int n,x,y;
    cin>>n>>x>>y;
    int a[n];
    for(int i=0;i<n;i++){
        a[i]=min(max(x-1-i,i+1-x)+1,max(y-1-i,i+1-y));
    }
    int b[n-1];
    for(int i=0;i<n-1;i++){
        b[i]=0;
    }
    for(int j=0;j<n;j++){
        for(int k=j+1;k<n;k++){
            b[min(k-j,a[j]+a[k])-1]++;
        }
    }
    for(int i=0;i<n-1;i++){
        cout<<b[i]<<endl;
    }

}

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

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

  vector<vector<int>> a(n+1,vector<int>(3,0));

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

  vector<vector<int>> dp(n+1,vector<int>(3,0));
  rep(i,3) dp[0][i] = a[0][i];

  for(int i = 1; i <= n; i++){
    dp[i][0] = a[i][0] + max(dp[i-1][1],dp[i-1][2]);
    dp[i][1] = a[i][1] + max(dp[i-1][0],dp[i-1][2]);
    dp[i][2] = a[i][2] + max(dp[i-1][0],dp[i-1][1]);
  }

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

  return 0;
}


Measured memory_bytes: 14352
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////
int main(){
    int n;
    cin>>n;
    cout<<(n+1)/2<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define assem99 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ld long double
#define ii pair<int, int>
#define pll pair<ll, ll>
#define vii vector<ii>
#define f(i,a,b) for(int i=a; i<b; i++)
#define F first
#define S second
#define sz(a) (int)(a).size()
#define ReadFile freopen("input.txt","r",stdin)
#define WriteFile freopen("output.txt","w",stdout)
int x[] = { 0, -1, 0, 1, -1, 1, -1, 1 };
int y[] = { -1, 0, 1, 0, 1, -1, -1, 1 };
const int MOD = 1e9 + 7, N = 1e5 + 5;
const double pi = acos(-1);
using namespace std;

int n, k, arr[N], dp[N];
int solve(int id)
{
    if(id == n - 1) return 0;
    if(dp[id] != -1) return dp[id];
    int ans = 1e9;
    f(i, 1, k + 1)
    {
        if(id <= (n - 1) - i) ans = min(ans, abs(arr[id + i] - arr[id]) + solve(id + i));
        else break;
    }
    return dp[id] = ans;
}

int main() {
    assem99
    memset(dp, -1, sizeof(dp));
    cin>>n>>k;
    f(i, 0, n) cin>>arr[i];
    cout<<solve(0);

    return 0;
}


Measured memory_bytes: 5760
#include <cstdio>
#include <algorithm>
using namespace std;

#define st first
#define nd second
typedef pair<int, int> pii;

const int INF = 1e9;

int main()
{
	int n;
	scanf("%d", &n);

	pii* elems = new pii[n];
	int x, l;

	for (int i = 0; i < n; ++i)
	{
		scanf("%d%d", &x, &l);
		elems[i] = make_pair(x + l, x - l);
	}

	sort(elems, elems + n);

	int cur = -INF, res = 0;
	for (int i = 0; i < n; ++i)
		if (cur <= elems[i].nd)
		{
			++res;
			cur = elems[i].st;
		}

	printf("%d", res);

	delete[] elems;

	return 0;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		
		int a = fs.nextInt();
		int b = fs.nextInt();
		int x = fs.nextInt();
		
		if(a <= x && a+b >= x) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}


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

const int INF = 1e9+7;

struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

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

  ll n,m; cin>>n>>m;

  vector<int> a(m), b(m);
  rep(i,m) {
    cin>>a[i]>>b[i];
    a[i]--; b[i]--;
  }
  UnionFind uf(n);
  ll p = n*(n-1)/2;
  vector<ll> ans;
  rep(i,m){
    ans.push_back(p);
    ll s = a[m-i-1], t = b[m-i-1];
    if(uf.issame(s,t)) continue;

    ll ss = uf.size(s), st = uf.size(t);
    p -= ss*st;
    uf.merge(s,t);
  }
  
  reverse(ans.begin(), ans.end());
  rep(i, ans.size()) cout<<ans[i]<<"\n";

  return 0;
}


Measured memory_bytes: 3444
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))

GCDF, GCDB = [0]*N, [0]*N
GCDF[1],GCDB[-2] = A[0], A[N-1]
for i in range(2, N):
    GCDF[i] = gcd(GCDF[i-1],A[i-1])
    GCDB[-(i+1)] = gcd(GCDB[-i], A[-i])
GCDm = [0]*N
GCDm[0] = GCDB[0]
GCDm[N-1] = GCDF[N-1]
for i in range(1, N-1):
    GCDm[i] = gcd(GCDF[i],GCDB[i])
ans = max(GCDm)
print(ans)

Measured memory_bytes: 16132
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

//ソートすればいいんですか？
//???
//しらないことだらけだ

int dp[3000];
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N, T;
	scanf("%d", &N);
	scanf("%d", &T);
	int AB[3000];
	rep(i, N) {
		int a, b;
		scanf("%d %d", &a, &b);
		AB[i] = (a << 12) + b;
	}
	sort(AB, AB + N);

	int saidai = 0;
	rep(i, N) {
		int a = AB[i] >> 12;
		auto dp2 = dp + a;
		int b = AB[i] & ((1 << 12) - 1);
		chmax(saidai, dp[0] + b);
		rep(j, T - a) {
			if (dp[j] < dp2[j] + b) dp[j] = dp2[j] + b;
		}
	}
	printf("%d", saidai);

	Would you please return 0;
}

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

anser = {}
for i in range(q):
    a = int(input())-1
    if not a in anser.keys():
        anser[a] = 1
    else:
        anser[a] += 1
for i in range(n):
    if not i in anser.keys():
        if k-q>0:
            print('Yes')
        else:
            print('No')
    else:
        if k-q+anser[i]>0:
            print('Yes')
        else:
            print('No')

Measured memory_bytes: 9064
#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
long double a,b;
int h,m;
long double c,d;
int main()
{
    cin>>a>>b>>h>>m;
    c=2.0*M_PI*h/12.0+2.0*M_PI*m/720.0,d=2.0*M_PI*m/60.0;
    printf("%.12Lf\n",sqrt(a*a+b*b-2*a*b*cos(fabs(c-d))));
	return 0;
}


Measured memory_bytes: 4168
using System;

namespace A___plusminusx
{
    class Program
    {
        static void Main(string[] args)
        {
            var ab = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            Console.WriteLine(Math.Max(ab[0] + ab[1], Math.Max(ab[0] - ab[1], ab[0] * ab[1])));
        }
    }
}


Measured memory_bytes: 11092