akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace ACprac
{
    class Program
    {
        static void Main(string[] args)
        {
            string b = Console.ReadLine();
            int count = 0;
            int lc = 0;

            for (int i = 0; i < b.Length; i++)
            {
                string S = b.Substring(i,1);
                if(S.Equals("A") || S.Equals("T") || S.Equals("G") || S.Equals("C"))
                {
                    lc++;
                }
                else
                {
                    if(count <= lc)
                    {
                        count = lc;
                        lc = 0;
                    }
                }

                if (count <= lc)
                {
                    count = lc;
                }

            }

            Console.WriteLine(count);

        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ep emplace_back
#define st first
#define sc second

using namespace std;

const ll mod = 998244353;
const int e = 1e6 + 69;
const int base = 311;

// dung igt thay cho gt luc tinh giai thua
// 3
// cach tao hoan vi tu n so : n*(n+1)/2;

ll a[e];
ll dp[e][2];

int main()
{
    vector<ll>kt(100, 0);
    ll a, b, c;
    cin >> a >> b >> c;
    kt[a] ++;
    kt[b] ++;
    kt[c] ++;
    if(kt[5] == 2 && kt[7] == 1) cout <<"YES";
    else cout <<"NO";
}


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

const int MAXN = 10000;

int main() {
    register int h, w, n, m, r = 0;
    static int d[MAXN + 1];
    std::ios::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL);
    std::cin >> h >> w >> n;
    for (register int i = 0; i < n; i++) {
        std::cin >> m;
        for (register int j = 0; j < m; j++) d[r++] = i + 1;
    }
    for (register int i = 0; i < h; i++) {
        for (register int j = 0; j < w; j++)
            printf("%d%c", d[i * w + (i % 2 ? w - j - 1 : j)],
                   w - j - 1 ? ' ' : '\n');
    }
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int par1[200001],par2[200001];
vector<pair<int,int>> idx;
map<pair<int,int>,int> cnt;
int rep1(int n)
{
    if(par1[n]==n)
        return n;
    return par1[n]=rep1(par1[n]);
}
int rep2(int n)
{
    if(par2[n]==n)
        return n;
    return par2[n]=rep2(par2[n]);
}
int main()
{
    int i,j;
    int n,k,l;
    int a,b,res=0;
    scanf("%d %d %d",&n,&k,&l);
    for(i=1;i<=n;i++){
        par1[i]=i;
        par2[i]=i;
    }
    for(i=0;i<k;i++){
        scanf("%d %d",&a,&b);

        int r1=rep1(a);
        int r2=rep1(b);
        par1[r1]=r2;
    }
    for(i=0;i<l;i++){
        scanf("%d %d",&a,&b);
        int r1=rep2(a);
        int r2=rep2(b);
        par2[r2]=r1;
    }
    for(i=1;i<=n;i++){

        idx.push_back(make_pair(rep1(i),rep2(i)));
    }

    for(i=0;i<idx.size();i++){
            //assert(idx[i].first == idx[i].second);
        cnt[idx[i]]++;
       // printf("%d %d\n",idx[i].first,idx[i].second);
    }
    for(i=0;i<idx.size();i++)
        printf("%d ",cnt[idx[i]]);
}

Measured memory_bytes: 15088
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

n, u, v, m = map(int, raw_input().split())

m1 = {}
m2 = {}

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        if n == 1:
            l = [0]
        else:
            l = [i, n + j]
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m1[lst_[j]] = l

for i in range(n):
    lst_ = map(int, raw_input().split())
    for j in range(n):
        if n == 1:
            l = [0]
        else:
            l = [i, n + j]
            if i == j:
                l.append(2 * n)
            if i + j == n - 1:
                l.append(2 * n + 1)
        m2[lst_[j]] = l

mu = {}
mv = {}

for loop in range(m):
    num = input()
    if num in m1:
        l = m1[num]
        for p in l:
            if not p in mu:
                mu[p] = 1
            else:
                mu[p] += 1
            if mu[p] == n:
                u -= 1
    
    if num in m2:
        l = m2[num]
        for p in l:
            if not p in mv:
                mv[p] = 1
            else:
                mv[p] += 1
            if mv[p] == n:
                v -= 1
    
    if u <= 0 or v <= 0:
        if v > 0:
            print "USAGI"
        elif u > 0:
            print "NEKO"
        else:
            print "DRAW"
        exit()

print "DRAW"


Measured memory_bytes: 61756
#include <bits/stdc++.h>
using namespace std;
const int BASE = 1e9 + 7;
const int N = 1e6;

long long fact[N + 5], invFact[N + 5], f[N + 5];

long long power(long long x, long long y)
{
  if (!y)
    return 1;
  long long res = power(x, y >> 1);
  res = res * res % BASE;
  if (y & 1)
    res = res * x % BASE;
  return res;
}

int main()
{
  int n, h, d;
  cin >> n >> h >> d;

  fact[0] = 1;
  for (int i = 1; i <= N; i++)
    fact[i] = fact[i - 1] * i % BASE;
  for (int i = 0; i <= N; i++)
    invFact[i] = power(fact[i], BASE - 2);

  long long sumFact = 0;
  for (int i = 1; i <= n; i++)
    sumFact = (sumFact + fact[i]) % BASE;


  f[0] = 1;
  long long curSum = 1;
  for (int i = 1, j = 0; i <= h; i++)
  {
    while (i - j > d)
      curSum = (curSum - f[j++] + BASE) % BASE;
    f[i] = curSum * sumFact % BASE;
    curSum = (curSum + f[i]) % BASE;
  }

  cout << f[h] * fact[n] % BASE * power(sumFact, BASE - 2) % BASE << endl;
}

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

using namespace std;

const long long MOD = 1000000007;


int main() {
	int H,W;
    cin >> H >> W;

    vector<vector<char>> board(H+2, vector<char>(W+2, '#'));
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> board[i][j];
        }
    }

    // (1,1)から(i,j)までの経路の数dp[i][j]
    vector<vector<long long>> dp(H+2, vector<long long>(W+2, 0));

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            if (i == 1 && j == 1) {
                dp[i][j] = 1;
                continue;
            }

            if (board[i][j] == '#') {
                dp[i][j] = 0;
            } else {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
        }
    }

    cout << dp[H][W] << endl;
	return 0;
}

Measured memory_bytes: 12064
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		ArrayList<String> list = new ArrayList<String>();
		int flag = 0;
		while(true){
			String str = br.readLine();
			if("0 0".equals(str)) break;
			list.add(str);
		}
		for(int i = 0 ; i <list.size() ; i++){
			String[] stra = list.get(i).split(" ");
			int h = Integer.parseInt(stra[0]);
			int w = Integer.parseInt(stra[1]);
			for (int j = 0 ; j < h ;j++){
				if(j%2 ==0){
					System.out.print("#");
					flag = 1;
					for(int k = flag ; k < w ; k++){
						if(k%2 == 0 ){
							System.out.print("#");
						}else {
							System.out.print(".");
						}
					}
				}else {
					System.out.print(".");
					flag = 0;
					for(int k = flag ; k < w-1 ; k++){
						if(k%2 == 0 ){
							System.out.print("#");
						}else {
							System.out.print(".");
						}
					}
				}

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

}

Measured memory_bytes: 25920
import sys
import copy
import  math
from _bisect import *
from collections import *
from operator import itemgetter
from math import factorial
"""
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
"""
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

a, b = na()
print(a + b if a + b < 10 else 'error')


Measured memory_bytes: 3572
#include<stdio.h>
#define N 100

int main(){
  int a,b[N],c,count,flag,i;
  count=0;
  scanf("%d",&a);

  for(i=0;i<a;i++){
    scanf("%d",&b[i]);
  }
  flag=1;
  while(flag){
    flag=0;
    for(i=a-1;i>0;i--){
      if(b[i]<b[i-1]){
	c=b[i];
	b[i]=b[i-1];
	b[i-1]=c;
	flag=1;
	count++;
      }
    }
  }
  for(i=0;i<a;i++){
    printf("%d",b[i]);
    if(i+1==a)break;
    printf(" ");
  }
  printf("\n%d\n",count);
  return 0;
}



Measured memory_bytes: 2124
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

int main(){
    int k;
    cin>>k;
    int v[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

    cout<<v[k-1]<<endl;








return 0;
}


Measured memory_bytes: 256
/* 만든 사람 <xrssa> */
/* 불타오르네, 불타오르네, 불타오르네 */
#include <bits/stdc++.h>
using namespace std;

#define f(i,n)        for(int i=0;i<n;i++)
#define fab(i,a,b)    for(int i=a;i<b;i++)
#define fa(elem, arr) for(auto &elem:arr)
#define all(a)        a.begin(),a.end()

void solve(){

    int L;scanf("%d",&L);
    printf("%.12f\n",(double)L*L*L/27);
}

int main()
{
    // 여러 테스트 사례 사용
    solve();
    return 0;
}


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

int main(){
    int n, m, k, f = 0;
    cin >> n >> m >> k;
    for(int i = 0; i <= n; i++){   //column
        for(int j = 0; j <= m; j++){   //row
            if(i * (m - j) + j * (n - i) == k){
                f = 1;
                break;
            }
        }
    }
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

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

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            // 解答はココに書く
            var N = cin.ReadInt;
            if (N > 200000)
            {
                Error.WriteLine("Error");
            }
            
            var P = cin.ReadIntArray(N);
            
            int num = 0;
            int pmin = 0;

            for (int i = 0; i < N; i++)
            {
                if (P[pmin] >= P[i])
                {
                    pmin = i;
                    num++;

                }
            }
            
            WriteLine(num);

            /* ex2
            var N = cin.ReadInt;
            var M = cin.ReadInt;
            var str = "";
            if (N >= M)
            {
                for (int i = 0; i < N; i++)
                {
                    str += M.ToString();
                }
            }
            else
            {
                for (int i = 0; i < M; i++)
                {
                    str += N.ToString();
                }
            }
            WriteLine("{0}", str);
            */
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}

Measured memory_bytes: 35468
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
last=-1
cnt=0
for i in range(len(ab)):
    if(ab[i][0]<=last):pass
    else:
        last=ab[i][1]-1
        cnt+=1
print(cnt)

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

#define ll long long

ll comb2(int x) { return 1LL*x*(x+1)/2; }

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

    vector<int> freq(26, 0);
    for(char c : s) freq[c-'a']++;

    ll res = comb2(n);
    for(int i=0; i<26; i++) res -= comb2(freq[i]);

    cout << res + 1 << endl;

    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Node {
	int key;
	struct Node* parent;
	struct Node* left;
	struct Node* right; 
};

typedef struct Node * NodePointer;

void insert( NodePointer t , int z){
	NodePointer x;
	if ( t -> key <= z){
		if  ( t -> right  == NULL){
			x =  (NodePointer) malloc (sizeof(struct Node));
			x -> key = z;
			x -> right = NULL;
			x -> left = NULL;
			t -> right = x;
			x -> parent = t;
		}else {
			insert ( t -> right , z);
		}
	
	}else {
		if  ( t -> left  == NULL){
			x =  (NodePointer) malloc (sizeof(struct Node));
			x -> key = z;
			x -> right = NULL;
			x -> left = NULL;
			t -> left = x;
			x -> parent = t;
		}else {
			insert ( t -> left , z);
		}
	}
};

void search ( NodePointer t, int tag){
	int flag = 0;
	while ( t != NULL){
		if ( t -> key == tag){flag = 1; break;}
		else if ( t -> key >= tag){
			t = t -> left;
		}else {
			t = t -> right;
		}
	}
	if (flag == 0 ){ printf("no\n");
	}else if (flag == 1){printf("yes\n");}
};

NodePointer delete (NodePointer t, int tag ){
	if (t == NULL){return NULL;}
	
	if ( t -> key > tag){
		t -> left = delete ( t -> left , tag);
	}else if (t -> key < tag){
		t -> right = delete ( t -> right , tag);
		
		
	}else if ( t -> key == tag){
		if ( t -> left == NULL){
			NodePointer temp = t -> right;
			if ( t -> right != NULL){
				t -> right -> parent = t -> parent;
			}
			free(t);
			return temp;
		}
		if ( t -> right == NULL){
			NodePointer temp = t -> left;
			if ( t -> left != NULL){
				t -> left -> parent = t -> parent;
			}
			free(t);
			return temp;
		}
		
		NodePointer i ;
		for ( i = t -> right; i -> left != NULL ; i = i -> left) ;	
		t -> key = i -> key;
		if ( i -> parent == t){
			t -> right = i -> right;
		}else {
			i -> parent  -> left = i -> right;
		}
		if ( i -> right != NULL){
			i -> right -> parent = i -> parent;
		}
		free(i);
	}
	return t;
};

void preorder ( NodePointer t){
	if ( t == NULL ){ return; }
	printf(" %d", t -> key);
	preorder( t -> left);
	preorder( t -> right);
};	

void inorder (NodePointer t){
	if ( t == NULL ){ return; }
	inorder( t -> left);
	printf(" %d", t -> key);
	inorder( t -> right);
};

void postorder (NodePointer t){
	if ( t == NULL ){ return; }
	postorder( t -> left);
	postorder( t -> right);
	printf(" %d", t -> key);
};


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

	NodePointer tree = (NodePointer) malloc (sizeof(struct Node));
	
	char input [8];
	int k;
	
	for ( int i = 0; i  < n; i++){
		scanf("%s" ,input);
		
		if ( strcmp( input , "insert") == 0 ){
			scanf("%d\n",&k);
			if ( i == 0)
			{
			tree -> key = k;
			tree -> right = NULL;
			tree -> left = NULL;
			}
			else {insert(tree , k);
			}
		}else if ( strcmp( input , "find") == 0 ){
			scanf("%d\n",&k);
			search( tree , k);
		}else if ( strcmp( input , "delete") == 0 ){
			scanf("%d\n",&k);
			delete( tree , k);
		}else {
			inorder(tree);
			printf("\n");
			
			preorder(tree);
			printf("\n");
		}
	}
	
	
	return 0;
}


Measured memory_bytes: 20484
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

field=[[float('inf') for i in range(w)]for j in range(h)]

q=deque()
q.append((0,0))
field[0][0]=0

n=0
while q:
    y,x=q.popleft()
    n=max(n,field[y][x])
    for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
        ny=y+dy
        nx=x+dx
        if 0<=ny<h and 0<=nx<w and field[ny][nx]==float('inf') and s[ny][nx]!='#':
            q.append((ny,nx))
            field[ny][nx]=field[y][x]+1

ans=0
check=field[h-1][w-1]

shiro=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            shiro+=1
ans=shiro-check-1

            
if field[h-1][w-1]!=float('inf'):
    print(ans)
else:
    print(-1)

    

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

int main(){
	
	int k;
	char kata[255];
	scanf("%d",&k);
	getchar();
	
	scanf("%[^\n]", &kata);
	int s = strlen(kata);
	
	for(int i = 0; i < k && kata[i] != '\0'; i++){
		printf("%c", kata[i]);
	}
	if(s > k){
		printf("...");
	}
	
	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun May 17 21:25:46 JST 2020
 **/

std::vector<std::string> t = {
    "pon", "pon", "hon", "bon", "hon", "hon", "pon", "hon", "pon", "hon",
};
signed main() {
    Int n;
    std::cin >> n;
    std::cout << t[n % 10] << std::endl;
}


Measured memory_bytes: 3600
#include <iostream>
#include <fstream>
#include <cmath>
#include <list>
#include <vector>
#include <tuple>
using namespace std;
//#define FILENAME "./F/in/b04"
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long

#define MOD 1000000007

int n;
vector<int> a;
vector<int> b;

int main(int argc, char *argv[]) {

#ifdef FILENAME
  ifstream file(FILENAME);
  cin.rdbuf(file.rdbuf());
#endif

  cin >> n;
  a.resize(n);
  b.resize(n);

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

  int sum = 0;
  for(int i = n; i >= 1; i--) {
    b[i-1] = a[i-1];
    for(int j = 2; i*j <= n; j++) b[i-1] = (b[i-1]+b[i*j-1]) % 2;
    if(b[i-1]==1) sum++;
  }

  cout << sum << endl;
  rep(i,n) {
    if(b[i]) cout << i+1 << " ";
  }
  
  
  return 0;
}


Measured memory_bytes: 2432
#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod =1000000007;
bool visited[1001][1001];
int depth[1001][1001];
char arr[1001][1001];
void dfs(int x,int y,int n,int m)
{

    if(!visited[x][y])
    {
        visited[x][y]=true;
        int xrr[2]={1,0};
        int yrr[2]={0,1};
        for(int i=0;i<=1;i++)
        {
            int xx=x+xrr[i];
            int yy=y+yrr[i];

            if(xx>n-1)
                continue;
            if(yy>m-1)
                continue;
            if(arr[xx][yy]=='#')
                continue;
// cout<<x<<" "<<y<<" "<<xx<<" "<<yy<<endl;
            if(!visited[xx][yy])
            {
              if(xx==n-1&&yy==m-1)
            {
                (depth[x][y])++;
                return;
            }

             dfs(xx,yy,n,m);
            }
             depth[x][y]=(depth[x][y]%mod+depth[xx][yy]%mod)%mod;
        }
    }
}

signed main()
{
 int n,m;
 cin>>n>>m;

 for(int i=0;i<n;i++)
 {
     for(int j=0;j<m;j++)
     {
         cin>>arr[i][j];
     }
 }
 for(int i=0;i<=1000;i++)
 {
     for(int j=0;j<=1000;j++)
     {
         depth[i][j]=0;
         visited[i][j]=false;
     }
 }

        dfs(0,0,n,m);
     cout<<depth[0][0]<<endl;
    return 0;
}




Measured memory_bytes: 10368
#10進数から26進数への変換の問題
#与えられた数を26で割った余りがa~zに対応する
st="Xabcdefghijklmnopqrstuvwxyz"
ans=""
kazu=int(input())
while(True):
    add=kazu%26
    if(add==0):#0の時zにするため
        add=26
    ans=st[add]+ans#アルファベットを後ろから加えてく
    kazu-=add#余りを引く
    if(kazu==0):#数が0になったら終わり
        break
    kazu=kazu//26#26で割って切り捨て

print(ans)

Measured memory_bytes: 9032
#include<cstdio>
#include<algorithm>
#define maxn 100050
#define ll long long
using namespace std;
struct anode{
	int x,num;
}a[maxn*2];
bool cmp(anode a,anode b){
	return a.x>b.x;
}
int main(){
	int n,m,k;
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	scanf("%d",&a[i].x),a[i].num=1;
	k=n;
	for (int i=1;i<=m;i++){
		n++;
		scanf("%d%d",&a[n].num,&a[n].x);
	}
	sort(a+1,a+1+n,cmp);
	ll ans=0;
	for (int i=1;i<=n;i++)
	if (a[i].num<=k) {
		k-=a[i].num,ans+=1ll*a[i].num*a[i].x;
	}else {
		ans+=1ll*a[i].x*k;
		break;
	}
	printf("%lld\n",ans);
	return 0;	
} 

Measured memory_bytes: 1664
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18;
const ld PI = acos((ld)-1);
const ld EPS = 1e-6;
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const char nl = '\n';

template <typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <typename T> inline T lcm(T a, T b) { return a / gcd(a, b) * b; }
template <class T> void ckmin(T& a, T b) { a = min(a, b); }
template <class T> void ckmax(T& a, T b) { a = max(a, b); }

// (Integer/Long).bitCount(x)
int pct(int x) { return __builtin_popcount(x); }
int pctll(ll x) { return __builtin_popcountll(x); }

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(string s = "") {
	unsyncIO();
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }
}

// Binary Exponentiation
ll pow(ll b, ll e, ll m = 0LL, ll ans = 1LL) { while (e) { if (e & 1LL) { ans *= b; if (m) ans %= m; } b *= b, e >>= 1LL; if (m) b %= m; } return ans; }

ll ans;

void try_it(ll x, ll y) {
	ckmax(ans, x * y);
}

void solve(int tcn) {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a <= 0LL && b >= 0LL || c <= 0LL && d >= 0LL) {
		ans = 0LL;
	}
	else {
		ans = -INF;
	}
	try_it(a, c);
	try_it(a, d);
	try_it(b, c);
	try_it(b, d);
	cout << ans << nl;
}

int main() {
    setIO();

    int t = 1; //cin >> t;
	for (int i = 1; i <= t; ++i) {
		//cout << "Case #" << i << ": ";
		solve(i);
	}
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for (ll i = (begin); i < (end); i++)
#define REP(i, n) FOR(i, 0, n)
#define IFOR(i, begin, end) for (ll i = (begin)-1; i >= (end); i--)
#define IREP(i, n) IFOR(i, n, 0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(), greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v)                                                              \
  cout << #v << "=(" << v[0];                                                  \
  FOR(i_debug, 1, v.size()) { cout << "," << v[i_debug]; }                     \
  cout << ")" << endl;
#define mdebug(m)                                                              \
  cout << #m << "=" << endl;                                                   \
  REP(i_debug, m.size()) {                                                     \
    REP(j_debug, m[i_debug].size()) { cout << m[i_debug][j_debug] << ","; }    \
    cout << endl;                                                              \
  }
#define Lower_bound(v, x)                                                      \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x)                                                      \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;

template <typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) {
  REP(i, a.size()) {
    cin >> a[i];
    a[i]--;
  }
}

ll mod = 1000000007;

int main() {

  ll X, Y;
  cin >> X >> Y;

  cout << X + Y / 2 << endl;

  return 0;
}

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

using namespace std;

const int N = 200010;

int n, a[N];

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i); a[i] -= i;
  }
  sort(a + 1, a + n + 1);
  int x = a[1 + n >> 1];
  long long ans = 0;
  for (int i = 1; i <= n; ++i) {
    ans += (long long) abs(a[i] - x);
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 1024
#include<stdio.h>
long gcd(int a, int b) //ユークリッドの互除法による最小公倍数算出 (a>=b)
{
  long A=a, B=b, temp;
  while(a%b!=0){
    temp=a%b;
    a=b;
    b=temp;
  }
  return b*(A/b)*(B/b);
}

int main()
{
  int A,B;
  scanf("%d %d",&A,&B);
  
  long ans;
  if(A>B){
    ans = gcd(A,B);
  }else{
    ans = gcd(B,A);
  }
  printf("%ld",ans);
}


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

#define int long long

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long n;
  cin >> n;
  int x, m;
  cin >> x >> m;
  long long ans = x;
  --n;
  long long cur = (x * x) % m;
  long long sum = 0;
  vector<int> seen(m), res(m), val(m + 2);
  int pos = 1;
  while (n && !seen[cur]) {
    // cout << cur << ' ';
    sum += cur;
    seen[cur] = pos;
    res[cur] = sum;
    val[pos] = sum;
    cur = (cur * cur) % m;
    --n;
    if (n == 0) {
      cout << sum + x << '\n';
      return 0;
    }
    ++pos;
  }   
  // cout << "\n";
  // cout << cur << '\n';
  // cout << "sum: " << sum << '\n';
  int cycle = pos - seen[cur];
  int rep = sum - val[seen[cur] - 1];
  // cout << rep << '\n';
  sum += rep * (n / cycle);
  // cout << "cycle: " << cycle << '\n';
  // cout << n / cycle << '\n';
  // cout << "sum: " << sum << '\n';
  int rem = n % cycle;
  // cout << "rem: " << rem << '\n';
  if (rem) {
    // cout << val[seen[cur] + rem - 1] - val[seen[cur] - 1] << '\n'; 
    sum += val[seen[cur] + rem - 1] - val[seen[cur] - 1];
  }
  cout << sum + x << '\n';
  return 0;
}

Measured memory_bytes: 5544
N=int(input())
A = [int(i) for i in input().split()]
cnt=0
ans=0
B=[]
C=[]
for i in range(N):
    B.append(abs(A[i]))
for i in range(N):
    if A[i]<0:
        C.append(A[i])
if len(C)%2==0:
    ans=sum(B)
    print(ans)
else:
    sel=min(B)
    print(sum(B)-2*abs(sel))

Measured memory_bytes: 14252
#include <stdio.h>
int main(void)
{
	int a,b,c,count=0,i,z;
	scanf("%d" "%d" "%d",&a,&b,&c);
	for(a;a <= b;a++)
	{
		z = c % a;
		if(z == 0)
		{
			count = count + 1;
		}
		else
		{
			count = count;
		}
	}
	printf("%d\n",count);
	return 0;
}

Measured memory_bytes: 596
import itertools

N = int(input())
# n週入力させる
P = [list(map(int,input().split())) for i in range(N)]

S = 0
# 3!
# pから2つ選ぶ組み合わせ
route = list(itertools.combinations(P, 2))
# 例題の出力結果
# [([0, 0], [1, 0]), ([0, 0], [0, 1]), ([1, 0], [0, 1])]
# 6通り全部計算式に当てはめる 2-1,3-2 3-2,4-3
for i in route:
  #  指定の計算式
   S += ((i[0][0] - i[1][0])**2 + (i[0][1] - i[1][1])**2)**0.5
   
print(S*2/N)

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

const int MAXN = 2e5;

int n, a[MAXN], ans;
multiset<int> leaf;

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; ++i){
		scanf("%d", &a[i]);
	}
	for(int i = 0; i < n; ++i){
		if(leaf.empty()){
			ans++;
		}else{
			auto p = leaf.lower_bound(a[i]);
			if(p == leaf.begin()){
				ans++;
			}else{
				p--;
				leaf.erase(p);
			}
		}
		leaf.insert(a[i]);
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using i64 = int64_t;
using u64 = uint64_t;

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

constexpr int64_t MOD = 1'000'000'007LL;
const int INF = 1001001001;

#define INT(NAME) int NAME; cin>>NAME;
#define INT64(NAME) int64_t NAME; cin>>NAME;
#define VECTOR(NAME, TYPE, SIZE) std::vector<TYPE> NAME((SIZE));\
    for(int xxxx_i=0; xxxx_i<SIZE; xxxx_i++) cin>>NAME[xxxx_i];
#define VECTOR_CIN(NAME, SIZE) (NAME).resize(SIZE); \
    for(int xxxx_i=0; xxxx_i<SIZE; xxxx_i++) cin>>NAME[xxxx_i];
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)    

vector<int> A, ans;
vector<vector<int>> tree;
vector<int> dp;

void dfs(int u, int par=-1) {
    int pos = lower_bound(dp.begin(), dp.end(), A[u]) - dp.begin();
    int old = dp[pos];
    dp[pos] = A[u];
    ans[u] = int(lower_bound(dp.begin(), dp.end(), INF) - dp.begin()) -1;
    for (int v : tree[u]) {
        if (v == par) continue;
        dfs(v, u);
    }
    dp[pos] = old;
}

void solve() {
    INT(N)
    VECTOR_CIN(A, N);
    tree.resize(N);
    REP(i,N-1) {
        INT(u); INT(v);
        u--; v--;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    ans.resize(N);
    dp.resize(N+1);
    fill(dp.begin(), dp.end(), INF);
    dp[0] = -INF;

    dfs(0);
    REP(i,N) cout<<ans[i]<<endl;
}

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

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

int main(){
  using namespace std;
  int n, t;
  vector<int> a;
  cin >> n;
  int cnt[n+1]={0};
  for(int i=0; i<n-1; i++){
    cin >> t;
    a.push_back(t);
  }
  sort(a.begin(), a.end());
  for(auto it = a.begin(); it != a.end(); it++){
    cnt[*it]++;
  }
  for(int i=1; i<=n; i++){
    cout << cnt[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 5036
from itertools import accumulate

N = int(input())
R = [int(input()) for _ in range(N)]

R_min = list(accumulate(R, min))
R_max = accumulate(reversed(R), max)
R_max = list(reversed(list(R_max)))

max_profit = -10**10
for i in range(N-1):
    profit = R_max[i+1] - R_min[i]
    if profit > max_profit:
        max_profit = profit

print(max_profit)
        


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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ASC(x) sort(ALL((x)))
#define DESC(x) sort(ALL((x)),greater<ll>())
#define REV(x) reverse(ALL((x)))
#define eb emplace_back

int main()
{
    ll a;
    cin >> a;
    PR(a+a*a+a*a*a);
    return 0;
}

/*



*/

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
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; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end



int main(){
    string s,t; cin>>s>>t;
    ll nxt[100010][26]; Fill(nxt,INF);
    rep(i,0,s.size())nxt[i][s[i]-'a']=0LL;
    rrep(i,s.size()*2-1,0)rep(j,0,26){
        chmin(nxt[(i-1+s.size())%s.size()][j],nxt[i%s.size()][j]+1LL);
    }
    ll ans=0;
    rep(i,0,t.size()){
        ll val=nxt[ans%(int)(s.size())][(int)(t[i]-'a')];
      cerr<<nxt[0][2]<<endl;
        if(val==INF){
            printf("-1");
            return 0;
        }
        ans+=val+1;
    }
    printf("%lld\n",ans);
    return 0;
}


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

namespace MyProgram
{
    public class Program
    {	
        public static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int h = int.Parse(str[0]);
            int w = int.Parse(str[1]);
            char[,] map = new char[h,w];
            
            bool cut = true;
            string s = "";
            for(int i = 0 ; i < h ; i++)
            {
                s = Console.ReadLine();
                for(int j = 0 ; j < w; j++)
                {
                    map[i,j] = s[j];
                }
            }
            
            
            for(int i = 0 ; i < h ; i++)
            {
                cut = true;
                s = Console.ReadLine();
                for(int j = 0 ; j < w; j++)
                {
                    if(map[i,j] == '#') cut = false;
                }
                if(cut)
                {
                    for(int j = 0 ; j < w; j++)
                    {
                        map[i,j] = '-';
                    }
                }
            }
            for(int i = 0 ; i < w ; i++)
            {
                cut = true;
                s = Console.ReadLine();
                for(int j = 0 ; j < h; j++)
                {
                    if(map[j,i] == '#') cut = false;
                }
                if(cut)
                {
                    for(int j = 0 ; j < h; j++)
                    {
                        map[j,i] = '-';
                    }
                }
            }
            List<char> c = new List<char>();
            for(int i = 0 ; i < h ; i++)
            {
                c.Clear();
                for(int j = 0 ; j < w ; j++)
                {
                    if(map[i,j]!='-')c.Add(map[i,j]);
                }
                if(c.Count>0)
                {
                    string ss = string.Join("",c);
                    Console.WriteLine(ss);
                }
            }
            
        }
    }
}

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

bool check(vector<pair<long, long>> target)
{
    long v = 0;
    for (pair<long, long> s : target)
    {
        // cout << v << " " << s.first << endl;
        if (v + s.first < 0)
            return false;
        v += s.second;
    }
    return true;
}

int main()
{
    long n;
    cin >> n;
    vector<pair<long, long>> minmaxlPl, minmaxlMi;
    long total = 0;
    rep(i, n)
    {
        string s;
        cin >> s;
        long minv = 0;
        long v = 0;
        rep(j, s.size())
        {
            char c = s[j];
            if (c == '(')
            {
                v += 1;
            }
            else
            {
                v -= 1;
            }
            minv = min(v, minv);
        }
        total += v;
        if (v >= 0)
        {
            minmaxlPl.emplace_back(minv, v);
        }
        else
        {
            minmaxlMi.emplace_back(minv - v, -v);
        }
    }
    sort(minmaxlPl.rbegin(), minmaxlPl.rend());
    sort(minmaxlMi.rbegin(), minmaxlMi.rend());
    if (check(minmaxlPl) && check(minmaxlMi) && total == 0)
    {
        puts("Yes");
    }
    else
    {
        puts("No");
    }
}

Measured memory_bytes: 34608
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <functional>
#include <cassert>
#include <utility>
#include <stack>
#include <queue>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int,int> Pi;
typedef long long int ll;
const int INF=(1<<30)-1;
const ll INFl=9223372036854775807;
const int MAX=310;
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/gcd(a, b)*b;}

int n;
int t[101];
int i2,i4,i14,i24,i74;
int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		int j=2;
		int w=i;
		while(w!=1){
			if(w%j==0){
				w/=j;
				t[j]++;
			}else{
				j++;
			}
		}
	}
	
	for(int i=2;i<=100;i++){
		if(t[i]>=74)i74++;
		if(t[i]>=24)i24++;
		if(t[i]>=14)i14++;
		if(t[i]>=4)i4++;
		if(t[i]>=2)i2++;
	}
	int ans=i74+i24*(i2-1)+i14*(i4-1)+i4*(i4-1)*(i2-2)/2;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define endl '\n'

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


int main()
{
    ll n,i,j,k=0;
    cin>>n;
    string s;
    cin>>s;
    if(n%2){cout<<"No"<<endl;}
    else{
            j=s.size()/2;
        for(i=0;i<j;i++)
        {
            if(s[i]==s[i+j]) k++;
        }
    if(k==j){cout<<"Yes"<<endl;}
    else{cout<<"No"<<endl;}
    }
    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <vector>

#define moduloNum 1000000007

using namespace std;

template <class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }

    return false;
}

int main() {
    int H, W;
    cin >> H >> W;

    vector<vector<char>> a(H, vector<char>(W, ' '));
    vector<vector<int>> dp(H, vector<int>(W, 0));
    dp[0][0] = 1;

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

    for (int n = 0; n < H + W - 1; n++) {
        for (int i = 0; i < n + 1; i++) {
            int j;

            if (i < H && n - i < W) {
                j = n - i;
            } else {
                continue;
            }

            if (a[i][j] == '#') {
                dp[i][j] = 0;
                continue;
            }

            if (i == 0 && j > 0) {
                if (a[i][j - 1] == '.') {
                    dp[i][j] = dp[i][j - 1];
                }
            } else if (i > 0 && j == 0) {
                if (a[i - 1][j] == '.') {
                    dp[i][j] = dp[i - 1][j];
                }
            } else if (i > 0 && j > 0) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % moduloNum;
            }
        }
    }

    // for (auto row : dp) {
    //     for (auto v : row) {
    //         cout << v << " ";
    //     }
    //     cout << endl;
    // }

    cout << dp[H - 1][W - 1] << endl;

    return 0;
}


Measured memory_bytes: 5248
N,M=map(int,input().split())
a=[0]*(N+1)
for i in range(M):
    a[int(input())]=1
MOD = 1000000007

dp=[0]*(N+1)
dp[0]=1
if a[1]==1:
    dp[1]=0
else:dp[1]=1

for i in range(2,N+1):
    #n-1段目が安全なら
    if a[i-1]==0:
        dp[i]+=dp[i-1]
    #n-2段目が安全なら
    if a[i-2]==0:
        dp[i]+=dp[i-2]
    dp[i] = dp[i]%MOD
print(dp[N])

Measured memory_bytes: 7772
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <limits.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

typedef unsigned long long ULLONG;
typedef long long LLONG;

template <class _T> static _T tp_abs(const _T& a) {
	return ((a < 0) ? (a * -1) : a);
}
template <class _T> static _T tp_min(_T a, _T b) {
	return a < b ? a : b;
}
template <class _T> static _T tp_max(_T a, _T b) {
	return a > b ? a : b;
}
template<class _T> static void getint(_T& a) {
	const char* fmt = " %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld";
	}

	if (scanf(fmt, &a) < 0) {
		printf("g1int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b) {
	const char* fmt = " %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld";
	}

	if (scanf(fmt, &a, &b) < 0) {
		printf("g2int Error\n");
	}
}
template<class _T> static void getint(_T& a, _T& b, _T& c) {
	const char* fmt = " %d %d %d";
	if (sizeof(_T) == sizeof(long long)) {
		fmt = " %lld %lld %lld";
	}

	if (scanf(fmt, &a, &b, &c) < 0) {
		printf("g3int Error\n");
	}
}
static void getstring(char* buff) {
	if (scanf(" %s", buff) < 0) {
		printf("getstr error!\n");
	}
}
static const long long MOD_NUM = 1000000007LL;
template <class _T> static _T tp_pow(_T base, int exp)
{
	_T ans = 1;

	for (int i = 0; i < exp; i++) {
		ans *= base;
	}
	return ans;
}

static void E_task();

int main()
{
	E_task();
	fflush(stdout);
	return 0;
}

static void E_task()
{
	int N;
	getint(N);

	std::vector<LLONG> an(N, 0), bn(N, 0);

	for (int i = 0; i < N; i++) {
		LLONG a, b; getint<LLONG>(a, b);
		an[i] = a;
		bn[i] = b;
	}

	std::sort(an.begin(), an.end());
	std::sort(bn.begin(), bn.end());

	LLONG midMax, midMin;
	if (N % 2) {
		midMax = bn[N / 2];
		midMin = an[N / 2];
	}
	else {
		midMax = (bn[(N / 2) - 1] + bn[N / 2]);
		midMin = (an[(N / 2) - 1] + an[N / 2]);
	}

	printf("%lld\n", midMax - midMin + 1);
}


Measured memory_bytes: 6452
<?php
list($n, $k) = ints();
$a = ints();
while ($k > 0) {
    $_a = array_fill(0, $n, 0);
    for ($i = 0; $i < $n; ++$i) {
        $l = max(0, $i - $a[$i]);
        $r = min($n - 1, $i + $a[$i]);
        $_a[$l]++;
        if ($r + 1 < $n) $_a[$r + 1]--;
    }
    for ($i = 0; $i < $n - 1; ++$i) $_a[$i + 1] += $_a[$i];
    if ($a === $_a) break;
    $a = $_a;
    $k--;
}
echo implode(' ', $_a);
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 40148
if __name__ == "__main__":
    N = int(input())
    D, X = list(map(int, (input().split(' '))))
    A = []
    for i in range(N):
        A.append(int(input()))
    snack_num = X
    for i in range(N):
        if A[i] == 1:
            snack_num += D
        elif D % A[i] == 0:
            snack_num += (D // A[i])
        else:
            snack_num += (D // A[i] + 1)
    print(snack_num)

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

int N,M,Q;
vector<vector<int> > G(101010);
int color[101010];
int memo[15][101010];
int V[101010],D[101010],C[101010];

void func(int d,int v,int c){
  if(memo[d][v]!=0) return;
  if(color[v]==0) color[v]=c;
  if(d==0){
    memo[0][v]=1;
    return;
  }
  func(d-1,v,c);
  rep(i,G[v].size()){
    func(d-1,G[v][i],c);
  }
  memo[d][v]=1;
  return;
}

int main(){
  cin>>N>>M;
  rep(i,M){
    int a,b; cin>>a>>b; a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  cin>>Q;
  rep(i,Q){
    cin>>V[i]>>D[i]>>C[i];
    V[i]--;
  }
  for(int i=Q-1;i>=0;i--) func(D[i],V[i],C[i]);
  rep(i,N) cout<<color[i]<<endl;
  return 0;
}


Measured memory_bytes: 13048
# D - String Formation

S = str(input())
Q = int(input())

# 1の数
c = 0
l = ''
r = ''

for _ in range(Q):
    q = [str(x) for x in input().split()]
    if q[0] == '1':
        c += 1
        l, r = r, l
    elif q[1]=='1':
        l = l + q[2]
    else:
        r = r + q[2]

if c%2==1:
    S = ''.join(reversed(S))

l = ''.join(reversed(l))

print(l+S+r)

Measured memory_bytes: 4852
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define md 1000000007
#define ld long double
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, i = 0, j= 0, k = 0, l = 0, m = 0, a = 0, b = 0, sum = 0, x = 0, y = 0, z = 0, c, p = 0;
    cin >> n >> x >> y;
    vector <ll> v(n+1);
    for(i = 1; i <= n; i++){
        for(j = i+1; j <= n; j++){
            a = abs(i-j);
            b = abs(i-x) + 1 + abs(j-y);
            c = abs(i-y) + 1 + abs(j-x);
            m = min(a,b);
            m = min(m,c);
            v[m]++;
        }
    }
    for(i = 1; i <= n-1; i++){
        cout << v[i] << endl;
    }

    return 0;
}


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

int main(void) {
	int a, b;
	cin >> a >> b;
	if ((a + b) == 15) {
		cout << "+" << endl;
	} else if ((a * b == 15)) {
		cout << "*" << endl;
	} else {
		cout << "x" << endl;
	}
	return 0;
}

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

int main() {
  int N;
  cin>>N;
  vector<int> a(N);
  vector<int> l(100005);
for(int i=0;i<N;i++) cin>>a[i];
if(a[0]!=0){
  cout<<0<<endl;
  return 0;
}
long mod  =998244353;
for(int i=0;i<N;i++) l[a[i]]++;
long ans=1;
if(l[0]!=1){
  cout<<0<<endl;
  return 0;
}
long tmp=1;
for(int i=0;i<=N;i++){
   if(i==0) ans*=l[0];
   else if(i==1){
    //ans *= l[1];
    tmp = l[1];
   }
   else if(i>=2){
     long base=1;
     for(int j=0;j<l[i];j++){
      base *= tmp;
      base = base%mod;
     }

     ans *= base;
     tmp=l[i];
   }

   ans = ans%mod;
}
cout<<ans<<endl;
  }


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

int gcd(int a, int b)
{
    while (a != b) {
        if (a > b) {
            a -= b;
        }
        else b -= a;
    }
    return a;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    long long sum = 0;

    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int z = 0; z < N; z++) {
        sum += gcd(i+1, gcd(j+1,z+1));
    }

    cout << sum;
}

Measured memory_bytes: 3608
import sys
input = sys.stdin.readline

def chmin(min,cur):
	if min > cur:
		min = cur
	return min

n,k = map(int,input().split())
h = list(map(int,input().split()))

dp = [float('inf')]*n
dp[0] = 0

for i in range(n):
	for j in range(k):
		try:
			dp[i+j+1] = chmin(dp[i+j+1],dp[i]+abs(h[i]-h[i+j+1]))
		except:
			break

print(dp[n-1])

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

#define MAXN 200010
#define ll long long
#define mod 1000000007

using namespace std;

int n, m, k, c;
int ans, tot;

int a[MAXN];

string s;

int main(){
	int t;
	scanf("%d%d%d", &n, &k, &c);
	cin >> s;
	
	
	int i = n, num = 0;
	while (i >= 1) {
		if (s[i - 1] == 'o') {
			num++;
			a[i]++;
		i -= c;
		}
		i--;
	}
	
//	for (int i = 1; i <= n; i++) {
//		cout << a[i] << " ";
//	}
//	cout << endl;
	
	if (num != k) {
//		cout << num << endl;
		return 0;
	}
	
	i = 1;
	while (i <= n) {
		if (s[i - 1] == 'o') {
			if (a[i] == 1) cout << i << endl;
		i += c;
		}
		i++;
	}

	return 0;
}


Measured memory_bytes: 2564