akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>


int main(){
  int H, W; cin >> H >> W;
  int c[10][10];
  rep(i,10)rep(j,10) cin >> c[i][j];
  int A;
  map<int,int> d;
  rep(i,H) rep(j,W) {
    cin >> A;
    d[A]++;
  }

  queue<int> q;
  q.push(1);
  vector<int> dist(10,100000000);
  dist[1] = 0;
  while (!q.empty()){
    int a = q.front(); q.pop();
    rep(i,10){
      if (c[i][a]+dist[a]<dist[i]) {
        dist[i] = c[i][a] + dist[a];
        q.push(i);
      }
    }
  }
  ll ans = 0;
  for (auto p : d){
    if (p.first==-1) continue;

    ans += dist[p.first]*p.second;
  }
  cout << ans << endl;
  

  // cout << fixed << setprecision(10);
  
  return 0;
}


Measured memory_bytes: 3584
import           Control.Applicative
import           Control.DeepSeq
import           Control.Monad
import           Control.Monad.ST
import qualified Data.Array                    as A
import qualified Data.Array.IArray             as IA
import qualified Data.Array.IO                 as AI
import qualified Data.Array.MArray             as MA
import qualified Data.Array.ST                 as STA
import qualified Data.Array.Unboxed            as AU
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import qualified Data.Graph                    as G
import           Data.Int
import qualified Data.IntMap                   as IM
import qualified Data.IntSet                   as IS
import           Data.List
import qualified Data.Map.Strict               as M
import           Data.Maybe
import           Data.Ord
import qualified Data.Sequence                 as SQ
import qualified Data.Set                      as S
import           Data.Time
import qualified Data.Tree                     as T
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as VM
import qualified Data.Vector.Unboxed           as VU
import qualified Data.Vector.Unboxed.Mutable   as VUM

readInt :: IO Int
readInt = fst . fromJust . BS.readInt <$> BS.getLine

readInts :: IO [Int]
readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readIntLists :: Int -> IO [[Int]]
readIntLists n = replicateM n readInts

readInteger :: IO Integer
readInteger = fst . fromJust . BS.readInteger <$> BS.getLine

readIntegers :: IO [Integer]
readIntegers = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegerLists :: Int -> IO [[Integer]]
readIntegerLists n = replicateM n readIntegers

readStrings :: IO [String]
readStrings = map BS.unpack . BS.words <$> BS.getLine

readStringLists :: Int -> IO [[String]]
readStringLists n = replicateM n <$> readStrings

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

put :: Show a => a -> IO ()
put = putStr . show

putList :: Show a => [a] -> IO ()
putList [n     ] = put n
putList (n : ns) = do
  put n
  putStr " "
  putList ns

putStrList :: [String] -> IO ()
putStrList [n     ] = putStr n
putStrList (n : ns) = do
  putStr n
  putStr " "
  putStrList ns

yesNoUpper b | b         = putStrLn "YES"
             | otherwise = putStrLn "NO"

yesNo b | b         = putStrLn "Yes"
        | otherwise = putStrLn "No"

divCeiling x n | b == 0    = a
               | otherwise = a + 1
  where (a, b) = x `divMod` n

main = do
  [n, k] <- readInts
  print $ solve n k

solve n k = (sum $ map (\b -> f b k n) bs )- m
 where
  bs = [k + 1 .. n]
  m | k /= 0    = 0
    | otherwise = n

f b k n = p * max 0 (b - k) + max 0 (r - k + 1)
 where
  ms     = [k .. b - 1]
  (p, r) = n `divMod` b
  m | r == 0    = b + 1
    | otherwise = 0

g b k n m | m /= 0    = (n - m) `div` b + 1
          | otherwise = (n - m) `div` b


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

        for(int i = 0; i<=n;i++){
            sum =sum+i;
        }
        System.out.println(sum);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;

int main(){
 int a,b,c,x,y;
 cin>>a>>b>>c;

cout<<c<<" "<<a<<" "<<b<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

int top, s[1000];

int pop(){
	top--;
	return s[top+1];
}

void push(int a){
	s[++top]=a;
}

int main(){
	int b, a;
	top = 0;
	char c[3];
	while(cin >> c){
		if(c[0] == '+'){
			a = pop();
			b = pop();
			push(a+b);
		}
		else if(c[0]=='-'){
			a = pop();
			b = pop();
			push(b - a);
		}
		else if(c[0]=='*'){
			a = pop();
			b = pop();
			push(a * b);
		}
		else{
			push(atoi(c));
		}
	}
	cout << pop() << endl;
	return 0;
}



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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n)　for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef string ss;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    //y /= gcd(x,y);
    return (x*y);
}

#define WA printf("WA\n");
int main()
{
    ss s;
    ll ans=0;
    cin >> s;
    rep(i,SIZE(s)){
        if(s[i] == '+')ans++;
        else ans--;
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j,n,x,y;
    int mod=1000000007;
    cin>>n;
    vector<vector<int>> edges(n+1);
    for(i=0;i<n-1;i++)
    {
        cin>>x>>y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    vector<int> visited(n+1,-1);
    stack<int> s;
    vector<long long int > white(n+1,-1);
    vector<long long int > black(n+1,-1);
    s.push(1);
    visited[1]=1;
    while(!s.empty())
    {
        int top=s.top();
        if(visited[top]==1)
        {
            for(i=0;i<edges[top].size();i++)
            {   
                if(visited[edges[top][i]]==-1)
                {
                    visited[edges[top][i]]=1;
                    s.push(edges[top][i]);
                }
            }
            visited[top]=2;
        }
        else if(visited[top]==2)
        {
            s.pop();
            long long int b=1,w=1;
            for(i=0;i<edges[top].size();i++)
            {
                if(black[edges[top][i]]!=-1 && white[edges[top][i]]!=-1)
                {
                    w = (w* (black[edges[top][i]] + white[edges[top][i]]))%mod;
                    b = (b* white[edges[top][i]])%mod;
                }
            }
            white[top]=w;
            black[top]=b;
        }
        
        
    }

    cout<<(white[1]+black[1])%mod<<endl;
}

Measured memory_bytes: 8440
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(v) for (auto itr = v.begin(), itr != v.end(); ++itr)
#define LB(v, x) lower_bound(v.begin(), v.end(), x) - v.begin()
#define UB(v, x) upper_bound(v.begin(), v.end(), x) - v.begin()
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    int N;
    cin >> N;
    set<string> S;
    REP(i, N) {
        string s;
        cin >> s;
        S.insert(s);
    }
    cout << S.size() << endl;

    return 0;
}


Measured memory_bytes: 19244
x1,y1,x2,y2 = map(int ,input().split())
x = x2 - x1
y = y2 - y1
ans = ''
a = 'U'
b = 'D'
c = 'R'
d = 'L'


for _ in range(y):
    ans += a
for _ in range(x):
    ans += c
for _ in range(y):
    ans += b
for _ in range(x) :
    ans += d
ans += d
for _ in range(y + 1):
    ans += a
for _ in range(x +1):
    ans += c
ans += b
ans += c
for _ in range(y + 1):
    ans += b
for _ in range(x + 1):
    ans += d
ans += a
print(ans)

Measured memory_bytes: 3064
/*
  In the name of ALLAH
  Author : Raashid Anwar
*/

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
const int M1 =  998244353;
const int M2 =  1000000007;
mt19937 rng((uint64_t)chrono::steady_clock::now().time_since_epoch().count());

vector <int> c[300001];
int r[300001];

void solve() {
  int h, w, m;
  cin >> h >> w >> m;
  for(int i = 1; i <= w; i++)
    c[i].clear();
  for(int i = 1; i <= h; i++)
    r[i] = 0;
  for(int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    c[y].push_back(x);
    r[x]++;
  }
  multiset <int> s;
  for(int i = 1; i <= h; i++)
    s.insert(r[i]);
  int ans = 0;
  for(int i = 1; i <= w; i++) {
    for(int x : c[i]) {
      s.erase(s.find(r[x]));
      r[x]--;
      s.insert(r[x]);
    }
    ans = max(ans, (int)c[i].size() + (*(--s.end())));
    for(int x : c[i]) {
      s.erase(s.find(r[x]));
      r[x]++;
      s.insert(r[x]);
    }
  }
  cout << ans << "\n";
}
 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
}

Measured memory_bytes: 36416
use std::io;

fn input() -> (i64, i64) {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("");
    let mut iter = s.trim().split_whitespace();
    let a: i64 = iter.next().unwrap().parse().unwrap();
    let b: i64 = iter.next().unwrap().parse().unwrap();
    (a, b)
}

fn main() {
    loop {
        let (H, M) = input();
        if H == 0 && M == 0 {
            break;
        }
        for k in 0..M{
            print!("#");
        }
        print!("\n");
        if H>2{
            for i in 1..(H-1){
                print!("#");
                if M>2{
                    for j in 1..(M-1){
                      print!(".");
                  }
                }
                if M>1{
                    print!("#");
                }
            print!("\n");
            }
        }
        if H>1{
            for k in 0..M{
                print!("#");
                }
        }
        print!("\n");
        if H!=1{
            print!("\n");
        }
    }
}


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

#define int long long int 
int find(int *coe,int n)
{
    if(n==0)
    return 1;
    int result=0;

    for(int i=0;i<2;i++)
    if(coe[i]<=n)
    result+=find(coe,n-coe[i]);
    return result;
}
int32_t main()
{
    int coe[2]={4,7};
    int n;
    cin>>n;
    cout<<(find(coe,n)?"Yes":"No")<<endl;
}

Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
#define _USE_MATH_DEFINES
#include<math.h>
#include<sstream>
# include<set>
#define in(n, m) for (ll i=n; i<m;i++)
#define inj(n, m)for (ll j=n; j<m;j++)
#define ink(n, m)for (ll k=n; k<m;k++)
using namespace std;
using ll=long long;
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; }
const ll N=1e5, M = 1e5;
ll dp[200000];
ll a[100000][3];
const ll INF = 1LL << 60;


int main() {
	ll N;
	cin >> N;
	set<string>S;

	in(0, N) {
		string a;
		cin >> a;
		S.insert(a);
	}

	cout << S.size() << endl;
	
	return 0;
}

Measured memory_bytes: 19172
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define repr(i, n) for (int i = n - 1; i > 0; --i)
#define all(x) (x).begin(), (x).end()
#define pb(x) push_back(x);
using namespace std;
template <class T> bool chmax(T &a, const T &b) {if (a<b) {a = b; return 1;} return 0;}
template <class T> bool chmin(T &a, const T &b) {if (b<a) {a = b; return 1;} return 0;}
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

int main() {
    string s;
    cin >> s;
    for(int i=0; i<s.size(); i+=2) {
        if (s[i] == 'L') {
            cout << "No" << "\n";
            return 0;
        } 
    }
        for(int i=1; i<s.size(); i+=2) {
        if (s[i] == 'R') {
            cout << "No" << "\n";
            return 0;
        } 
    }
    cout << "Yes" << "\n"; 
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int dp[100];
int weight[6] = { 2 ,3 ,5 ,10 ,12 ,15 };
int value[6] = { 380 ,550 ,850 ,1520 ,1870 ,2244 };

void compute(void){
  
  for( int i = 0 ; i < 100 ; i++ ) dp[i] = 99999;;
  dp[0] = 0;
  for( int i = 0 ; i < 6 ; i++ ){
    for( int j = 0 ; j + weight[i] < 100 ; j++ ){
	dp[j + weight[i]] = min( dp[j + weight[i]] , dp[j] + value[i] );
      // 値段はvalueの6種類のみだからづいじそのパターンで計算
    }
  }

}

int main(void){

  compute();

  int n;
  while( cin >> n , n ){
    cout << dp[n/100] << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>

using namespace std;

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)a.size()
#define pw(n) (1ll << (n))

#define equal equalll
#define less lesss
const int N = -1;
const long long INF = 1e9 + 19;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

int n;

void read() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int y;
        cin >> y;
        sum = (sum + y) % 2;
    }
    if (sum == 0)
        puts("YES");
    else
        puts("NO");


}

void solve() {

}

void stress() {

}

int main(){
#ifdef HOME 
    freopen("in", "r", stdin);
#endif
    if (1) {
        read();
        solve();
    }
    else {
        stress();
    }

    return 0;
}



Measured memory_bytes: 764
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

#define EPS 1e-14
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) FOR(i, 0, n)
#define PI 2*acos(0.0)
#define ALL(a) (a).begin(),(a).end()
#define DEBUG(x) cout<<#x <<": "<< x << "\n"
#define DEBUG_ARR(a) REP(i, size(a)){ cout << #a << "[" << i << "]: " << a[i] << "\n"; }
const int VX[] = { 0, 1, 0, -1 };
const int VY[] = { 1, 0, -1, 0 };
const long MOD = 1000000007;

int main()
{
	//	--- I/O 高速化 ---
	cin.tie(0);
	ios::sync_with_stdio(false);
	// --- ここまで ---
	
	int N, M;
	
	cin >> N;
	vector<int> T(N, 0);
	REP(i, N)
	{
		cin >> T[i];
	}

	cin >> M;
	vector<int> P(M, 0);
	vector<int> X(M, 0);
	REP(i, M)
	{
		cin >> P[i] >> X[i];
	}

	REP(i, M)
	{
		int time = 0;
		
		REP(j , N)
		{
			if (P[i] == j + 1)
			{
				time += X[i];
			}
			else
			{
				time += T[j];
			}
		}
		cout << time << "\n";
	}



	return 0;
}



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

int main() {
    double ans;
    double a, b, x;
    cin >> a >> b >> x;
    double y = 2 * (a * a * b - x);
    if(y <= a * a * b)
        ans = atan2(y, a * a * a);
    else {
        y = 2 * x;
        ans = atan2(a * b * b, y);
    }
    ans *= 180;
    ans /= M_PI;
    cout << fixed << setprecision(10) << ans << endl;
}

Measured memory_bytes: 384
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    cnt=[0]*(N+1)
    for i in range(1,N+1):
        j=1
        while(i*j<=N):
            cnt[i*j]+=1
            j+=1
    ans=0
    for i in range(1,N+1):
        ans+=i*cnt[i]
    print(ans)
    
    
    
if __name__=="__main__":
    main()


Measured memory_bytes: 145744
n,q=map(int,input().split())
link=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,input().split())
    link[a-1].append(b-1)

under=[[] for i in range(n)]
for i in range(n-1, -1, -1):
    l=link[i]
    for j in l:
        under[i].append(j)

#for i in link:
#    print(i)
#print()
#for i in under:
#    print(i)


ans=[0]*n
for _ in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x

for i in range(n):
    for j in under[i]:
        ans[j]+=ans[i]
for i in ans:
    print("{} ".format(i), end="")
print()

Measured memory_bytes: 69992
#include "bits/stdc++.h"
#include <random>
#include <algorithm>
#include <unordered_set>
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define pf push_front
#define ld long double
#define Sort(a) sort(a.begin(),a.end())
#define cSort(a,cmp) sort(a.begin(),a.end(),cmp)
#define reSort(a) sort(a.rbegin(), a.rend())
static const ll llMAX = numeric_limits<long long>::max();
static const int intMAX = numeric_limits<int>::max();
static const ll  llMIN = numeric_limits<long long>::min();
static const int intMIN = numeric_limits<int>::min();
static const ll d_5 = 100000;
static const ll d9_7 = 1000000007;
static const ll d_9 = 1000000000;
static const double PI=3.14159265358979323846;
template<class T>
T gcd(T a,T b){
  if(a==0){
    return b;

  }else if(b==0){
    return a;
  }
  while(1) {
    if(a < b) swap(a, b);
    if(!b) break;
    a %= b;
  }
  return a;
}
ll digitpower(ll a,ll b){//aのb乗を計算
  if(b==1){
    return a;
  }else if(b==0){
    return 1;
  }
  int mode=1;
  if(mode==0){
    if(b%2==1){
      ll tmp = digitpower(a,(b-1)/2);
      tmp%=d9_7;
      tmp*=tmp;
      tmp%=d9_7;
      tmp*=a;
      return (tmp)%d9_7;
    }else{
      ll tmp = digitpower(a,(b)/2);
      tmp%=d9_7;
      tmp*=tmp;
      tmp%=d9_7;
      return (tmp)%d9_7;
    }
  }else{
    if(b%2==1){
      ll tmp = digitpower(a,(b-1)/2);
      tmp*=tmp;
      tmp*=a;
      return (tmp);
    }else{
      ll tmp = digitpower(a,(b)/2);
      tmp*=tmp;
      return (tmp);
    }
  }
  return 0;
  
}
template<class T>
void Printvector(std::vector<T> &a){
  int size = a.size();
  rep(i,size){
    cout<<a[i]<<" ";
  }
  cout<<endl;
}
template<class T>
void Printvector(std::vector<std::vector<T>> &a){
  int size = a.size();
  rep(i,size){
    int size2=a[i].size();
    rep(j,size2){
      cout<<a[i][j]<<" ";
    }
    cout<<endl;
  }
  cout<<endl;
}
int main(void){
  int x,y,a,b,c,n,m;
  string s,t;
  cin>>a>>b>>c;
  swap(a,b);
  swap(a,c);
  int ans;
  cout<<a<<" "<<b<<" "<<c;
  return 0;
}

//<<std::setprecision(30)

//重複削除
 /* std::sort(vec.begin(), vec.end());
 
  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());*/

  //ペアの全探索
  /*do{
		int s=0;
		for(int i=0;i<n/2;i++)s+=v[i]^v[i+n/2];
		r=max(s,r);
		reverse(v.begin()+n/2,v.end());
	}while(next_permutation(v.begin(),v.end()));*/


Measured memory_bytes: 256
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
def LI(): return list(map(int, sys.stdin.readline().split()))

P = 10**9 + 7
N = 10000

n_ = 10**5 + 3

fun = [1 for i in range(n_+1)]
for i in range(1, n_ + 1):
    fun[i] = fun[i-1] * i % mod

rev = [1 for i in range(n_+1)]
rev[n_] = pow(fun[n_], mod-2, mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1) % mod

def nCr(n,r):
    if n <= 0 or r < 0 or r> n:return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod

N, K = LI()
A = LI()

A.sort()
B = copy.deepcopy(A)
B.reverse()
ans = 0

# max
tmp_n = N
tmp_k = K - 1
for b in B:
    tmp_n -= 1
    if tmp_n < tmp_k:
        break
    ans = (ans + b * nCr(tmp_n, tmp_k))%mod

# print(ans, "max")
# min
tmp_n = N
tmp_k = K - 1
for a in A:
    tmp_n -= 1
    if tmp_n < tmp_k:
        break
    ans = (ans - a * nCr(tmp_n, tmp_k))%mod

print(ans)


Measured memory_bytes: 110892
import queue

n,m = map(int, input().split())
root = [[] for i in range(n)]
for i in range(m):
    tmp1, tmp2 = map(int, input().split())
    root[tmp1 - 1].append(tmp2 - 1)
    root[tmp2 - 1].append(tmp1 - 1)
q = queue.Queue()
q.put(0)
arrive = [0 for i in range(n)]
ans = [0 for i in range(n)]
arrive[0] = 0
while not q.empty():
    now = q.get()
    for i in root[now]:
        if arrive[i] == 0 and i != 0:
            arrive[i] = arrive[now] + 1
            ans[i] = now + 1
            q.put(i)
        else:
            if arrive[i] > arrive[now] + 1:
                ans[i] = now + 1

if False:print("No")
else:
    print("Yes")
    for i in range(1,n):
        print(ans[i])

Measured memory_bytes: 38068
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n=RD()[::-1]
	N=list(map(int,n))+[0]
	#print(N)

	ans=0

	for i in range(len(n)+1):
		if N[i]<=4:
			ans+=N[i]
		elif N[i]>=6:
			ans+=10-N[i]
			N[i+1]+=1
		else:
			if N[i+1]<=4:
				ans+=N[i]
			else:
				ans+=N[i]
				N[i+1]+=1

	print(ans)









if __name__ == "__main__":
	main()


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

#define F first
#define S second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1010, M = 10;

int n, m;
int s[M], c[M];

string get(int t)
{
	if (!t) return "0";
	
	string s;
	while (t)
	{
		s += '0' + t % 10;
		t /= 10;
	}
	reverse(s.begin(), s.end());
	return s;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < m; i ++ ) cin >> s[i] >> c[i];
	
	for (int i = 0; i < N; i ++ )
	{
		string t = get(i);
		if (t.size() != n) continue;

		bool flag = true;
		for (int j = 0; j < m; j ++ )
			if (t[s[j] - 1] != c[j] + '0')
				flag = false;

		if (flag)
		{
			cout << i << endl;
			return 0;
		}
	}
	
	puts("-1");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <cmath>
using namespace std;
int main()
{
    int n;
    cin>>n;
    long long mini=1e9+7;
    int sum=0;
    while(n--)
    {
        int temp;
        cin>>temp;
        if(temp<=mini)
        {
            mini=temp;
            sum++;
        }
    }
    cout<<sum;
    return 0;
}

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

using namespace std;

int main(){

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

    int sum=0;

    int s=0;

    if(a>=b){

        for(int i=b;i>0;i--){

            if(a%i==0&&b%i==0) sum++;

            if(sum==k){

                s=i;

                break;

            }

        }

    }

    else if(a<b){

        for(int i=a;i>0;i--){

            if(a%i==0&&b%i==0) sum++;

            if(sum==k){

                s=i;

                break;

            }

        }

    }

    cout<<s<<endl;

}



Measured memory_bytes: 3584
#include <stdio.h>
int main(){
  int n,card[4][13]={0},num,i,j;
  char mark;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf(" %c %d",&mark,&num);
    switch(mark){
    case 'S':
      card[0][num-1]=1;
      break;
    case 'H':
      card[1][num-1]=1;
      break;
    case 'C':
      card[2][num-1]=1;
      break;
    case 'D':
      card[3][num-1]=1;
      break;
    }
  }
  for(i=0;i<4;i++){
    for(j=0;j<13;j++){
      if(!card[i][j]){
	switch(i){
	case 0:
	  printf("S %d\n",j+1);
	  break;
	case 1:
	  printf("H %d\n",j+1);
	  break;
	case 2:
	  printf("C %d\n",j+1);
	  break;
	case 3:
	  printf("D %d\n",j+1);
	  break;
	}
      }
    }
  }
  return 0;
}

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


#define reps(i,f,n) for(int i = f; i < int(n); i++)
#define rep(i,n) reps(i,0,n)
#define f(n) n.first
#define s(n) n.second
using namespace std;
typedef pair<int,int> PII;

const int INF = 1e28;

PII xy[256];
int main(){
	
	int n;
	while(scanf("%d", &n),n){
		
		
		xy[0] = PII(0,0);
		
		reps(i,1,n){
			int in, d;
			cin >> in >> d;
			switch(d){
				case 0:
					xy[i] = PII(f(xy[in]),s(xy[in])-1);
					break;
				case 1:
					xy[i] = PII(f(xy[in])-1,s(xy[in]));
					break;
				case 2:
					xy[i] = PII(f(xy[in]),s(xy[in])+1);
					break;
				case 3:
					xy[i] = PII(f(xy[in])+1,s(xy[in]));
					break;
			}
		}
		
		int minx = INF, miny = INF;
		int maxx = -INF, maxy = -INF;
		
		rep(i,n){
			if(f(xy[i]) > maxx){
				maxx = f(xy[i]);
			}
			if(f(xy[i]) < minx){
				minx = f(xy[i]);
			}
			if(s(xy[i]) > maxy){
				maxy = s(xy[i]);
			}
			if(s(xy[i]) < miny){
				miny = s(xy[i]);
			}
		}
		
		printf("%d %d\n", maxy - miny+1, maxx-minx+1);
	}
	return 0;
}

Measured memory_bytes: 1228
import sys
import re
n = int(input())
a = 0
b = 0
a_b = 0
cnt = 0
for i in range(n):
    s = sys.stdin.readline().strip()
    cnt += len(re.findall("AB", s))
    a += s[0] == "B"
    b += s[-1] == "A"
    a_b += (s[0] == "B" and s[-1] == "A")
plus = 0
if a == b == a_b != 0:
    plus -= 1
plus += min(a, b)
print(cnt + plus)

Measured memory_bytes: 3188
N=int(input())
inf=10**9+7
ans=0
if N==1:
    print(0)
else:
    temp1=1
    temp2=1
    temp3=1
    for i in range(N):
        temp1*=10
        temp2*=8
        temp3*=9
        temp1%=inf
        temp2%=inf
        temp3%=inf
    ans=temp1+temp2-2*temp3
    ans%=inf
    print(ans)

Measured memory_bytes: 63432
#include<bits/stdc++.h>
using namespace std;
int main(){
  int H,W,K;
  cin>>H>>W>>K;
  long a[8]={0};
  a[0]=1;
  long b[8];

  int c[8];//i個の横棒が隣合わないように配置する場合の数
  c[0]=1;//あとで使う
  c[1]=2;
  c[2]=3;
  //●:配置する ×:配置しない *:なんでも _:配置できない
  //一番左は配置する
  //●_**** :i-2個の配置の場合の数
  //一番左は配置しない
  //×***** :i-1個の配置の場合の数
  //よって、c[i]=c[i-1]+c[i-2]
  for(int i=3;i<8;i++){
  	c[i]=c[i-1]+c[i-2];
  }

  if(W>=4){
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(j==0){
          b[0]=a[0]*c[W-2]+a[1]*c[W-3];
        }else if(j==W-1){
          b[W-1]=a[W-2]*c[W-3]+a[W-1]*c[W-2];
        }else if(j==1){
          b[j]=a[j-1]*c[W-3]+a[j]*c[W-3]+a[j+1]*c[W-4];
        }else if(j==W-2){
        	b[j]=a[j-1]*c[W-4]+a[j]*c[W-3]+a[j+1]*c[W-3];
        }else{
        	b[j]=a[j-1]*c[j-2]*c[W-j-2]+a[j]*c[j-1]*c[W-j-2]+a[j+1]*c[j-1]*c[W-j-3];
        }
      }
      for(int j=0;j<W;j++){
        a[j]=b[j]%1000000007;
      }
    }
  }else if(W==3){
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(j==0){
          b[0]=a[0]*c[W-2]+a[1]*c[W-3];
        }else if(j==W-1){
          b[W-1]=a[W-2]*c[W-3]+a[W-1]*c[W-2];
        }else{
          b[j]=a[j-1]+a[j]+a[j+1];
        }
      }
      for(int j=0;j<W;j++){
        a[j]=b[j]%1000000007;
      }
    }
  }else if(W==2){
    for(int i=0;i<H;i++){
      for(int j=0;j<W;j++){
        if(j==0){
          b[0]=a[0]+a[1];
        }else if(j==W-1){
          b[W-1]=a[W-2]+a[W-1];
        }
      }
      for(int j=0;j<W;j++){
        a[j]=b[j]%1000000007;
      }
    }
  }else{
    a[0]=1;
  }

  cout<<a[K-1]<<endl;
}

Measured memory_bytes: 256
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, M, K = get_ints
A = get_ints
B = get_ints

ax = []
sum = 0
A.each do |a|
  sum += a
  break if sum > K
  ax.push(sum)
end

bx = []
sum = 0
B.each do |b|
  sum += b
  break if sum > K
  bx.push(sum)
end

if ax.length < bx.length
  cx = bx
  bx = ax
  ax = cx
end

i = ax.length - 1
j = 0

ans = ax.length

while i >= 0
  while j < bx.length
    if ax[i] + bx[j] <= K
      ans = i + j + 2 if ans < i + j + 2
      j += 1
    else
      break
    end
  end
  i -= 1
end

puts ans


Measured memory_bytes: 42684
A,B=map(int,input().split())
A-=1
def func1(X):
    xa=(X//4)*4+1
    xb=X%4
    sum=int(bin(0)[2:])
    if xb==3:
        return sum
    if xb==0:
        return int(bin(X)[2:])
    if xb==1:
        return int(bin(X-1)[2:])^int(bin(X)[2:])
    if xb==2:
        return int(bin(X-2)[2:])^int(bin(X-1)[2:])^int(bin(X)[2:])
A_=str(func1(A)).zfill(50)
B_=str(func1(B)).zfill(50)
c=""

for i in range(50):
    if A_[i]=="0" and B_[i]=="0":
        c+="0"
    if A_[i]=="0" and B_[i]=="1":
        c+="1"
    if A_[i]=="1" and B_[i]=="1":
        c+="0"
    if A_[i]=="1" and B_[i]=="0":
        c+="1"
print(int(c,2))

Measured memory_bytes: 38384
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  int N; cin >> N;
  LL ans = -1e+10, mini = 1e+10;
  REP(i,N){
	LL a; cin >> a;
	ans = max(ans, a - mini);
	mini = min(mini, a);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 1204
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container;
import std.numeric, std.math;
import core.bitop;

T RD(T = string)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T)(in string str) { return str.split.to!(T[]); }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

long mod = pow(10, 9) + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

struct UnionFind
{
	void init(long n) { par = new long[](n); foreach (i; 0..n) par[i] = i; }
	long root(long i) { return par[i] == i ? i : (par[i] = root(par[i])); }
	bool same(long i, long j) { return root(i) == root(j); }
	void unite(long i, long j) { i = root(i); j = root(j); if (i == j) return; par[i] = j; }
	long[] par;
}

void main()
{
	auto K = RD!long;
	auto A = RD!long;
	auto B = RD!long;

	auto c = max(B - A, 2);
	auto d = min(K, A - 1);

	long ans = d + 1;
	K -= d;
	ans += c * (K / 2);
	ans += K % 2; 

	writeln(ans);
	stdout.flush();
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<map>
#include<set>
#include<vector>
// #include<bits/stdc++.h>

using namespace std;
#define ll long long 
#define mod 1000000007

int n, m;
int arr[109];
bool comp(int a, int b) {
	return a > b;
}


int main() {
	cin>>n>>m;
	int sum = 0;
	for(int i = 0 ; i < n; i++) {
		cin>>arr[i];
		sum += arr[i];
	}
	sort(arr, arr + n, comp);

	double x = arr[m - 1] * 1.0;
	double y = 1.0*sum;
	y /= (m*4.0);

	if(x >= y)
		cout<<"Yes\n";
	else 
		cout<<"No\n";
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int nb; cin>>nb;
    std::vector<int> lines; lines.resize(nb);
    for(auto& a:lines) cin>>a;
    
    auto minv = lines[0];
    auto maxv = lines[1]-lines[0];
    for(auto itr=lines.begin()+1;itr!=lines.end();++itr){
        maxv = max(maxv, *itr-minv);
        minv = min(minv, *itr);
    }
    cout<< maxv << endl;
}

Measured memory_bytes: 3448
<?php
$n = trim(fgets(STDIN));

$dp[0] = 0;
for($i = 1; $i <= $n; $i++){
    $min = 100000;
    for($j = 0; $j <= 7; $j++){
        if(isset($dp[$i - pow(6,$j)])){
            $min = min($min, $dp[$i - pow(6,$j)] + 1);
        }
    }
    for($j = 1; $j <= 6; $j++){
        if(isset($dp[$i - pow(9,$j)])){
            $min = min($min, $dp[$i - pow(9,$j)] + 1);
        }
    }
    $dp[$i] = $min;
}
echo $dp[$n];


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int 
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mem(x) memset(x, 0, sizeof(x))
const int MOD = 1e9+7;

template <typename T>
void print(T AA[], int nn){for(int ii=0; ii<nn; ii+=1){cout<<AA[ii]<<" ";}cout<<endl;}
template <typename T> inline void print(T nn){ cout << nn << endl;}
/* ----------------------------------------------------------------------------------- */

const int N = 2e5+5;
const int sz = 1e7+1;
int H[N], A[N], n, tree[sz], dp[N];

void build(int node, int start, int end){
	if(start == end){
		tree[node] = dp[start];
		return;
	}
	int mid = (start+end)/2;
	build(1+(node<<1), start, mid);
	build(2+(node<<1), mid+1, end);
	tree[node] = max(tree[1+(node<<1)], tree[2+(node<<1)]);
}
 
void update(int node, int start, int end, int idx, int val){
	if(start==end){
		tree[node] = val;
		dp[idx] = val;
		return;
	}
	int mid = (start+end)/2;
	if(start<=idx && idx<=mid) update(1+(node<<1), start, mid, idx, val);
	else update(2+(node<<1), mid+1, end, idx, val);
	tree[node] = max(tree[1+(node<<1)], tree[2+(node<<1)]);
}
 
int query(int node, int start, int end, int l, int r){
	if(start>r || end<l) return LONG_MIN;
	if(l<=start && end<= r) return tree[node];
	int mid = (start+end)/2;
	int q1 = query(1+(node<<1), start, mid, l, r);
	int q2 = query(2+(node<<1), mid+1, end, l, r);
	return max(q1, q2);
}

int32_t main(){

	IOS

	mem(dp);
	mem(tree);

	cin >> n;
	for(int i=0; i<n; i+=1) cin >> H[i];
	for(int i=0; i<n; i+=1) cin >> A[i];

	build(0, 0, n);
	for(int i=0; i<n; i+=1){
		// Reduce this loop to find max by using segment tree
		// for(int j=0; j<H[i]; j+=1){
		// 	dp[H[i]] = max(dp[H[i]], dp[j]+A[i]);
		// }
		int maxi = query(0, 0, n, 0, H[i]-1);
		update(0, 0, n, H[i], maxi+A[i]);
	}
	print(query(0, 0, n, 0, n));

	return 0;
}

Measured memory_bytes: 83072
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <deque>

#define dump(x) cerr << #x << "=" << (x) << endl;
using namespace std;
using ll = long long;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define IN(x) int (x); cin >> x
#define INL(x) ll (x); cin >> x
#define VINT(a,n) vector<int> a(n)
#define VIN(a,n) VINT(a,n); REP(i,n){cin >> a[i];}
#define ALL(x) (x).begin(),(x).end()

int main () {
  string s;
  cin>>s;
  int c=0;
  int ans=0;
  REP(i,s.size()){
    if(s[i]=='A'||s[i]=='T'||s[i]=='C'||s[i]=='G'){
      c++;
    }
    else{
      ans=max(ans,c);
      c=0;
    }
    if(i==s.size()-1)
      ans=max(ans,c);
  }
  cout<<ans;
    
}


Measured memory_bytes: 256
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional> 
#include <iomanip>
#include <unordered_map>
#include <memory.h>
#include <cstring>
#include <fstream>

using namespace std;

long long int mypow(long long int x, long long int n)
{
	long long int res = 1;
	while (n > 0)
	{
		if (n % 2 == 1)
		{
			res = res * x;
		}
		x = x * x;
		n /= 2;
	}
	return res;
}
vector <int> prime;
map <int, int> cnt;
void eratos(void)
{
	bool isprime[1000001];
	memset(isprime, true, sizeof(isprime));
	for (int i = 2; i <= 1000000; i++)
	{
		if (isprime[i])
		{
			prime.push_back(i);
			for (int j = 2 * i; j <= 1000000; j += i)
			{
				isprime[j] = false;
			}
		}
	}
}
int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	long long int N, P;

	cin >> N >> P;

	if (N == 1)
	{
		cout << P << '\n';
		return 0;
	}
	long long int res = 0;

	eratos();

	for (int i = 0; i < prime.size(); i++)
	{
		if (P == 1)
		{
			break;
		}
		while (P % prime[i] == 0)
		{
			cnt[prime[i]]++;
			P /= prime[i];
		}
	}
	if (P != 1)
	{
		cnt[P]++;
	}
	res = 1;
	for (auto it : cnt)
	{
		//cout << it.first << ' ' << it.second << '\n';
		if (it.second >= N)
		{
			//cout << mypow(it.first, (it.second / N)) << '\n';
			res *= (mypow(it.first,(it.second / N)));
		}
		
	}

	cout << res << '\n';

	return 0;
}


Measured memory_bytes: 4816
//  RAKSHIT KADAM
//ALWAYS USE &IT FOR ITERATING USING AUTO ...
//USE COUNT(STARTING ADDRESS, ENDING ADRESS ,VALUE) FOR FINDING THE COUNT IN THE RESPECTIVE DATA STRUCTURE
//NOTE THAT MEMSET CANNOT ASSIGN A VALUE OF 10^18 IT WILL ASSIGN A LOWER VALUE THAN THAT!!!
//NOTE THAT MEMSET CANT FILL THE DOUBLE VALUES;
//ACCUMULATE DOES NOT WORK PROPERLY IF VALUES START SUMMING BEYOND 1E9...
 #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree< int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update>
#warning !!!check the size of arrayss!!!

// NUMERIC DEFINITIONS :
    #define INF 2000000000000000005
    #define MOD  1000000007
    #define newMOD  998244353
    #define MAX 300006
    #define pi 3.1415926535897932384626433832795
#define ld long double
 #define ll long long
 #define int long long

 #define P(gg) for(auto rax:gg){cout<<rax<<" ";}cout<<endl;
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define endl "\n"
 #define x first
 #define y second
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define forci(i,n) for(ll i=0;i<n;i++)
 #define vi vector<ll>
 #define Endl endl
 #define lb lower_bound
 #define ub upper_bound
#define pii pair<ll,ll>

 #define input freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout)
 #define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;

ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
int power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1;int p = power(x, y/2, m) % m;  p = (p * p) % m;                                                  return (y%2 == 0)? p : (x * p) % m;}
ll modInverse(int a, int m){int g = gcd(a, m); { return power(a, m-2, m);}}
const int maxn = 500005;
void solve()
{
    ll n;cin>>n;
    ll a[n+3],b[n+3];
    for(ll i=1;i<=n;i++)cin>>a[i]>>b[i];
    sort(a+1,a+n+1);sort(b+1,b+n+1);
    if(n%2==0)
    {
        
        cout<<b[n/2]+b[n/2+1] - a[n/2]-a[n/2 +1] +1<<endl;
    }
    else
    {
        cout<<b[n/2 +1]-a[n/2 +1]+1<<endl;
    }
        
}
signed main()
{
   Need_for_speed(activated);
    
//satisfy
//    {
//   solve();
//   }

    solve();
    return 0;
}



Measured memory_bytes: 6792
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
long long gcd(long long x, long long y){
    if(y==0) return x;
    else return gcd(y,x%y);
}
//最小公倍数
long long lcm(long long x, long long y){
    return x / gcd(x, y) * y;
}
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int N; cin >> N;
    set<ll> st;
    bool f=true;
    for(int i=0;i<N;i++){
        ll A; cin >> A;
        if(st.count(A)){
            f=false;
        }
        st.insert(A);
    }
    if(f) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}


Measured memory_bytes: 12848
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

char p[3][3];

pair<int, int> getPoint(int a){
	rep(i,3){
		rep(j,3){
			if(p[i][j] == a) return make_pair(i,j);
		}
	}
	assert(false);
}

int getDistance(vector<pair<int, int>>& p, int a, int b){
	return abs(p[a].first - p[b].first) + abs(p[a].second - p[b].second);
}

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

	vector<vector<int>> v(9, vector<int>(9,0));
	rep(i,s.size() - 1){
		int a = s[i] - '0' - 1;
		int b = s[i + 1] - '0' - 1;
		if(a > b) swap(a,b);
		assert(a <= b);
		v[a][b]++;
	}


	vector<int> tmp(9);
	iota(all(tmp), 1);
	int ans_m = LONG_MAX;
	vector<int> ans_s;
	do{
		rep(i,9){
			p[i / 3][i % 3] = tmp[i];
		}

		vector<pair<int, int>> points(9);
		rep(i,9){
			points[i] = getPoint(i + 1);
		}

		int sum = 0;
		rep(i,9){
			rep(j,9){
				sum += getDistance(points, i, j) * v[i][j];
			}
		}
		if(sum < ans_m){
			ans_m = sum;
			ans_s = tmp;
		}
	}while(next_permutation(all(tmp)));

	rep(i,3){
		rep(j,3){
			cout << ans_s[i * 3 + j];
		}
		cout << endl;
	}
}



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

mod = 10**9 + 7

# factorial
factorial = [1,1]
# factorial inverse
factorial_inverse = [1,1]
# inverse for calculation
inverse = [0,1]

for i in range(2, n+1):
    factorial.append((factorial[-1]*i) % mod)
    inverse.append((- inverse[mod % i] * (mod//i)) % mod)
    factorial_inverse.append(factorial_inverse[-1] * inverse[-1] % mod)


def Binominal_theorem(n, k, mod):
    if n < k:
        return 0
    if (n < 0) or (k < 0):
        return 0
    return factorial[n] * factorial_inverse[k] * factorial_inverse[n-k] % mod

for i in range(1,k+1):
    ans = Binominal_theorem(n-k+1, i, mod) * Binominal_theorem(k-1, i-1, mod)
    ans = ans % mod
    print(ans)


Measured memory_bytes: 3572