akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

using namespace std;

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

#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back



int main(){
    int y,m,d;
    while(cin>>y>>m>>d){
        if( y<1868 || (y==1868 && ( m<9 || (m==9 && d<8))) ){
            cout<<"pre-meiji"<<endl;
        }else if( y<1912 || (y==1912 && ( m<7  || (m==7  && d<=29))) ){
            cout<<"meiji ";
            cout<<1+y-1868<<" "<<m<<" "<<d<<endl;
        }else if( y<1926 || (y==1926 && ( m<12 || (m==12 && d<=24))) ){
            cout<<"taisho ";
            cout<<1+y-1912<<" "<<m<<" "<<d<<endl;
        }else if( y<1989 || (y==1989 && ( m<1  || (m==1  && d<=7 ))) ){
            cout<<"showa ";
            cout<<1+y-1926<<" "<<m<<" "<<d<<endl;
        }else{
            cout<<"heisei ";
            cout<<1+y-1989<<" "<<m<<" "<<d<<endl;
        }
    }
}

Measured memory_bytes: 1164
import sys
import math
from collections import deque
import heapq as hq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    T = NI()
    for _ in range(T):
        N = NI()
        camels = [NLI() for _ in range(N)]
        base = 0
        camels_L = [[] for _ in range(N+1)]
        camels_R = [[] for _ in range(N+1)]
        # 左から詰めるラクダと右から詰めるラクダを仕分ける
        for camel in camels:
            if camel[1] >= camel[2]:
                camels_L[camel[0]].append(camel[1] - camel[2])
                base += camel[2] # LとRの低いほうを加算
            else:
                camels_R[N - camel[0]].append(camel[2] - camel[1])
                base += camel[1] # LとRの低いほうを加算
        ans = 0
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_L[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        if heap_camels:
            ans += sum(heap_camels)

        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_R[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        if heap_camels:
            ans += sum(heap_camels)
        print(ans + base)



if __name__ == "__main__":
    main()

Measured memory_bytes: 87224
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define fs first
#define sc second
#define _GLIBCXX_DEBUG

int main(void){
    ll n,w;
    cin >>n >> w;
    vector<pair<ll,ll> > g;
    rep(_,n){
        ll v,w;
        cin >> v >> w;
        g.push_back(make_pair(w,v));
    }

    vector<vector<ll> > dp(w+1, vector<ll>(n+1,0));
    // dp[i][j] = 重さi以内で0~j-1の品物から選ぶときの価値の最大値
    for(ll i=1; i<=w; i++){
        for(ll j=1; j<=n; j++){
            dp[i][j] = dp[i][j-1];
            if(i-g[j-1].fs >= 0){
                dp[i][j]=max(dp[i][j], dp[i-g[j-1].fs][j-1]+g[j-1].sc);

            }
            //cout << dp[i][j] << ' ';
        }
        //cout << endl;
    }
    cout << dp[w][n] << endl;
}



Measured memory_bytes: 11048
#include<bits/stdc++.h>
#define all(x)x.begin(),x.end()
using namespace std;int f,Q,T,F;char C;string S;deque<char>q;main(){for(cin>>S>>Q,q={all(S)};Q--;){cin>>T;if(T&1)f^=1;else cin>>F>>C,F-1^f?q.push_back(C):q.push_front(C);}S={all(q)};if(f)reverse(all(S));cout<<S;}

Measured memory_bytes: 1280
#include<iostream>
#include<stdlib.h>
 
using namespace std;
 
struct Node{
  int key;
  Node* next;
  Node* prev;
};
 
struct List{
  Node* nil;
 
  void init(){
    nil=(Node*)malloc(sizeof(Node));
    nil->next=nil;
    nil->prev=nil;
    nil->key=0;
  }
 
  Node* find(int key){
    for(Node* i=nil->next;i!=nil;i=i->next){
      if(i->key==key)return i;
    }
    return nil;
  }
 
  void insert(Node *x){
    x->next=nil->next;
    nil->next->prev=x;
    nil->next=x;
    x->prev=nil;
  }
  
  void add(int x){
    Node* p = (Node*)malloc(sizeof(Node));
    p->key=x;
    insert(p);
  }
   
  void delete_x(int key){
    Node* x=find(key);
    if(x==nil)return;
    x->prev->next=x->next;
    x->next->prev=x->prev;
    free(x);
  }
   
  void deleteFirst(){
    Node* x = nil->next;
    x->prev->next=x->next;
    x->next->prev=x->prev;
    free(x);
  }
   
  void deleteLast(){
    Node* x = nil->prev;
    x->prev->next=x->next;
    x->next->prev=x->prev;
    free(x);   
  }
 
  void output(){
    int flg=0;
    for(Node* i=nil->next;i!=nil;i=i->next){
      if(flg)cout<<' ';
      cout<<i->key;
      flg=1;
    }
    cout<<endl;
  }
};
 
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
 
  List list;
  list.init();
  int n,x;
  string str;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>str;
    if(str=="insert"){
      cin>>x;
      list.add(x);
    }else if(str=="delete"){
      cin>>x;
      list.delete_x(x);
    }else if(str=="deleteFirst"){
      list.deleteFirst();
    }else {
      list.deleteLast();
    }
  }
  //cout<<'-'<<endl;
  list.output();
}



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

void Main() {
  int n, m;
  std::cin >> n >> m;

  std::priority_queue<int> q;

  for (int i = 0; i < n; i++) {
    int a;
    std::cin >> a;
    q.push(a);
  }

  for (int i = 0; i < m; i++) {
    int a = q.top();
    q.pop();

    q.push(a / 2);
  }

  long long ans = 0;
  for (int i = 0; i < n; i++) {
    ans += q.top();
    q.pop();
  }

  std::cout << ans << std::endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 892
#include<stdio.h>

int main(void){

	int a,b;
	char op;

	while(1){

		scanf("%d %c %d",&a,&op,&b);
		if(op == '?')
			break;

		else if(op == '+')
			printf("%d\n",a+b);
		else if(op == '-')
			printf("%d\n",a-b);
		else if(op == '*')
			printf("%d\n",a*b);
		else if(op == '/')
			printf("%d\n",a/b);

	}

	return 0;

}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
signed main()
{
    int n;
    cin >> n;
    int s = 0;
    int t = n;
    while (t > 0) {
        s += t % 10;
        t /= 10;
    }
    yorn(n % s == 0);
    return 0;
}

Measured memory_bytes: 3652
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;

int main()
{
  long N; cin >> N;
  long A[100005];
  for (int i = 0; i < N; i++)
    cin >> A[i];
  
  long ans = 0, mn_abs = 1000000000, how_many_minus = 0;
  for (int i = 0; i < N; i++)
  {
    ans += abs(A[i]);
    mn_abs = min(mn_abs, abs(A[i]));
    if (A[i] < 0)
    {
      how_many_minus ++;
    }
  }
  
  if (how_many_minus % 2 == 0)
  {
    cout << ans << endl;
  }
  else // how_many_minus % 2 == 1
  {
    cout << ans - mn_abs * 2 << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1024
H,W = [ int(it) for it in input().split() ]
li = [ [1 if it=="#" else 0 for it in input() ] for i in range(H) ]
#[print(it) for it in li]

po = []
for i in range(H):
  for j in range(W):
    if li[i][j]==1:
      po.append( (i,j) )
g = 0
for i in range(10000):
  po_ = []
  s = 0
  dw=[[0,1],[0,-1],[1,0],[-1,0]]
  for p,q in po:
    for dp,dq in dw:
      if ( 0<=p+dp and p+dp<H and 0<=q+dq and q+dq<W ):
        if (li[p+dp][q+dq]==0):
          s += 1
          li[p+dp][q+dq]=1
          po_.append( (p+dp,q+dq) )
  if (s==0):
    break
  else:
    g += 1
  po = po_
      
#[print(it) for it in li]
print (g)
  
  
    
    

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

int nanboku_num;
int tozai_num;
int nanboku[1501];
int tozai[1501];

int nanboku_list[1000001];
int tozai_list[1000001];

int main(void) {
	int i,j;
	int result;
	while(1) {
		scanf("%d%d",&nanboku_num,&tozai_num);
		if(nanboku_num==0 && tozai_num==0)break;
		for(i=1;i<=nanboku_num;i++) {
			scanf("%d",&nanboku[i]);
			nanboku[i]+=nanboku[i-1];
		}
		for(i=1;i<=tozai_num;i++) {
			scanf("%d",&tozai[i]);
			tozai[i]+=tozai[i-1];
		}
		memset(nanboku_list,0,sizeof(nanboku_list));
		memset(tozai_list,0,sizeof(tozai_list));
		for(i=0;i<nanboku_num;i++) {
			for(j=i+1;j<=nanboku_num;j++) {
				nanboku_list[nanboku[j]-nanboku[i]]++;
			}
		}
		for(i=0;i<tozai_num;i++) {
			for(j=i+1;j<=tozai_num;j++) {
				tozai_list[tozai[j]-tozai[i]]++;
			}
		}
		result=0;
		for(i=0;i<=1000000;i++)result+=nanboku_list[i]*tozai_list[i];
		printf("%d\n",result);
	}
	return 0;
}

Measured memory_bytes: 8232
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,n) for(long long i=0;i<n;++i)
#define REPP(i,m,n) for(long long i=m;i<n;++i)
#define rep(i,n) for(long long i = n-1;i>=0;--i)
#define repp(i,n,m) for(long long i = n-1; i >= m; --i)
#define ALL(N) (N.begin(),N.end())
#define de cout << "line : " << __LINE__ << " debug" << endl;
#define pb push_back
#define pq priority_queue
#define fi first
#define se second
#define Dcout(N) cout << setprecision(20) << N << endl
constexpr int INF = 2147483647;
constexpr long long INFF = 9223372036854775807;

signed main() {
    cin.tie(0);
	ios::sync_with_stdio(false);
    int N;cin >> N;
    if(N == 1){
        cout << 1 << endl;
        return 0;
    }
    string S[2*N];
    REP(i,N){cin >> S[i];S[i] += S[i];}
    REPP(i,N,2*N){S[i] = S[i-N];}

    int ans = 0;
    bool flag = 1;
	int K = N;
    REP(j,N){//左上の点を決定
        int i = 0;
        int x = i,y = j,A = 0;
        while(flag){
            REPP(k,x+1+A,x+N){
                if(S[k][y] != S[y-j+i][k+j-i]){
                    flag = 0;K--;
                    break;
                }
                else if(k == x+N-1 && A == N-2){
                    ans += K;K--;
                    flag = 0;
                }
            }
            y++;A++;
        }
        flag = 1;
    }
  K = N-1;

    REPP(i,1,N){//左上の点を決定
        int j = 0;
        int x = i,y = j,A = 0;
        while(flag){
            REPP(k,x+1+A,x+N){
                if(S[k][y] != S[y-j+i][k+j-i]){
                    flag = 0;K--;
                    break;
                }
                else if(k == x+N-1 && A == N-2){
                    ans += K;K--;
                    flag = 0;
                }
            }
            y++;A++;
        }
        flag = 1;
    }
    cout << ans << endl;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll Inf = 1e18;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int n, m, Q;
    cin >> n >> m >> Q;
    vector<vector<int> > sum(n + 1, vector<int>(n + 1));
    rep (i, m) {
        int l, r;
        cin >> l >> r;
        sum[l][r]++;
    }
    rep (i, n + 1) {
        FOR (j, 1, n + 1) {
            sum[i][j] += sum[i][j - 1];
        }
    }
    rep (j, n + 1) {
        FOR (i, 1, n + 1) {
            sum[i][j] += sum[i - 1][j];
        }
    }
    rep (i, Q) {
        int p, q;
        cin >> p >> q;
        cout << sum[q][q] - sum[q][p - 1] - sum[p - 1][q] + sum[p - 1][p - 1] << endl;
    } 
    
    return 0;
}



Measured memory_bytes: 1920
n,k,*a=map(int,open(0).read().split())
b=[[]for _ in range(max(a)+1)]
l=[]
for i,v in enumerate(a):
  b[v]+=i,
  l+=len(b[v]),
s=a[0]
i=c=0
while 1:
  t=b[s]
  m=len(t)
  j=l[i]
  c+=j==m
  i=t[j%m]+1
  if i==n:break
  s=a[i]
k%=c+1
s=a[0]
i=c=0
r=[]
while 1:
  t=b[s]
  m=len(t)
  j=l[i]
  f=j==m
  if c>k-2and f:
    r+=s,
    i+=1
  else:i=t[j%m]+1
  c+=f
  if i==n:break
  s=a[i]
print(*r)

Measured memory_bytes: 49148
input()

s = raw_input().strip()

l = "("
r = ")"

l_c = 0
r_c = 0
for c in s:
    if c == l:
        l_c+=1
    elif c == r:
        if l_c>0:
            l_c-=1
        else:
            r_c+=1
            
print "(" * r_c + s + ")" * l_c

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

int main() 
{
    string s;
    cin >> s;
    int n=0;
    for (int i=0; i<s.size()-1; i++)
    {
        if (s[i]==s[i+1] && s[i]=='0')
        {
            s[i+1] = '1';
            n++;
        }
        else if (s[i]==s[i+1] && s[i]=='1')
        {
            s[i+1] = '0';
            n++;
        }
    }
    cout << n;
    return 0;
}

Measured memory_bytes: 512
use std::fmt::Debug;
use std::str::FromStr;

pub struct TokenReader {
    reader: std::io::Stdin,
    tokens: Vec<String>,
    index: usize,
}

impl TokenReader {
    pub fn new() -> Self {
        Self {
            reader: std::io::stdin(),
            tokens: Vec::new(),
            index: 0,
        }
    }

    pub fn next<T>(&mut self) -> T
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index += 1;
        self.tokens[self.index - 1].parse().unwrap()
    }

    pub fn vector<T>(&mut self) -> Vec<T>
    where
        T: FromStr,
        T::Err: Debug,
    {
        if self.index >= self.tokens.len() {
            self.load_next_line();
        }
        self.index = self.tokens.len();
        self.tokens.iter().map(|tok| tok.parse().unwrap()).collect()
    }

    pub fn load_next_line(&mut self) {
        let mut line = String::new();
        self.reader.read_line(&mut line).unwrap();

        self.tokens = line
            .split_whitespace()
            .map(String::from)
            .collect();
        self.index = 0;
    }
}

type Graph = Vec<Vec<usize>>;

fn visit(graph: &Graph, node: usize, used: &mut Vec<bool>) -> usize {
    let mut count = 1;
    used[node] = true;

    for &son in graph[node].iter() {
        if !used[son] {
            count += visit(graph, son, used);
        }
    }
    count
}

fn solve(graph: &Graph) -> usize {
    let mut used = vec![false; graph.len()];
    let mut res = 0;

    for i in 0..graph.len() {
        if !used[i] {
            res = std::cmp::max(res, visit(graph, i, &mut used));
        }
    }
    res
}

fn main() {
    let mut reader = TokenReader::new();
    let nodes = reader.next();
    let edges = reader.next();

    let mut graph = vec![vec![]; nodes];
    for _ in 0..edges {
        let a = reader.next::<usize>() - 1;
        let b = reader.next::<usize>() - 1;
        graph[a].push(b);
        graph[b].push(a);
    }

    let res = solve(&graph);
    println!("{}", res);
}


Measured memory_bytes: 25612
#include<bits/stdc++.h>
#include<vector>
#include<set>
#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=0; i<(n); i++)
#define T int t, q=0; scanf("%d", &t); while(q++<t)
#define ll long long
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
ll x,y,z,a=0,b=0,c=0,d=0,sum,ans,total,cnt,n,m,k,p,kase,i,t;
string s1,s2;
#define N 100001
#define MX 1000000001
vector <ll> v;
map<ll,ll> mp;
set<ll> s;
map<ll,ll> :: iterator itr1, ptr1;
set<ll> :: iterator itr, ptr;


int main()
{


        cin>>s1;

        ans=0;
        sum=0;


       for(int i=0;i<s1.size();i++)
       {
           sum+=(s1[i]-'0');
       }

       if(sum%9==0)
        cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

    return 0;
}
// Happy Coding  (:


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

using namespace std;

const int N = (int)2e5 + 123;

int n, a, b, c, d;
string s;

void no() {
	cout << "No";
	exit(0);
}

void yes() {
	cout << "Yes";	
	exit(0);
}

int pref[2][N], suff[2][N]; // 0 - A, 1 - B

int main() {
	cin >> n >> a >> b >> c >> d;
	a --, b --, c --, d --;	
	cin >> s;
	pref[0][a] = 1, pref[1][b] = 1;
	for(int i = a + 1; i <= c; i ++) {
		if(s[i] == '#') continue;		
		pref[0][i] |= pref[0][i - 1];
		pref[0][i] |= pref[0][i - 2];
	}
	for(int i = b + 1; i <= d; i ++) {
		if(s[i] == '#') continue;
		pref[1][i] |= pref[1][i - 1];
		pref[1][i] |= pref[1][i - 2];
	}
	suff[0][c] = 1, suff[1][d] = 1;
	for(int i = c - 1; i >= a; i --) {
		if(s[i] == '#') continue;
		suff[0][i] |= suff[0][i + 1];
		suff[0][i] |= suff[0][i + 2];
	}
	for(int i = d - 1; i >= b; i --) {
		if(s[i] == '#') continue;		
		suff[1][i] |= suff[1][i + 1];
		suff[1][i] |= suff[1][i + 2];
	}
	if(c < d) {
		if(pref[1][d] && pref[0][c]) yes();
		else no();			
	} else {
		for(int i = b; i <= d; i ++) {
			if(s[i] == '#') continue;
			if(pref[1][i] && suff[1][i])
				if(pref[0][i - 1] && suff[0][i + 1])
					yes();
		}
		no();
	}
	return 0;
}

Measured memory_bytes: 2564
#include<iostream>

void makeabacus(char abacus[8][5],int num,int c);
void output(char abacus[8][5]);

int main()
{
	char abacus[8][5];
	
	bool first=true;
	while(1)
	{
		int num;
		std::cin>>num;
		if(std::cin.eof())break;
		
		for(int i=4;i>=0;i--)
		{
			int digit=num%10;
			num/=10;
			makeabacus(abacus,digit,i);
		}
		if(first){first=false;}
		else{std::cout<<std::endl;}
		output(abacus);
	}
	return 0;
}

void makeabacus(char abacus[8][5],int num,int c)
{
	int q=num/5;
	int s=num%5;
	int i=0;
	if(q==1)
	{
		abacus[0][c]=' ';
		abacus[1][c]='*';
	}
	else
	{
		abacus[0][c]='*';
		abacus[1][c]=' ';
	}
	abacus[2][c]='=';
	
	for(i=3;i<3+s;i++)
	{
		abacus[i][c]='*';
	}
	abacus[i++][c]=' ';
	for(;i<8;i++)
	{
		abacus[i][c]='*';
	}
}

void output(char abacus[8][5])
{
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<5;j++)
		{
			std::cout<<abacus[i][j];
		}
		std::cout<<std::endl;
	}
}

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

int main(void){
   int n,x,count;
   while(true){
      cin >> n >> x;
      if ((n == 0) && (x == 0)){
         break;
      }
      count = 0;
      for (int i = 1; i <= n; i++){
         for (int j = i + 1; j <= n; j++){
            for (int k = j + 1; k <= n; k++){
               if (i + j + k == x){
                  count += 1;
               }
            }
         }
      }
      cout << count << endl;
   }
}



Measured memory_bytes: 3104
from collections import deque
N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    graph[a - 1].append((b - 1, c))
    graph[b - 1].append((a - 1, c))
Q, K = map(int, input().split())
visited = [0] * N
visited[K - 1] = 1
q = deque([(K - 1, 0)])
while q:
    p, c = q.popleft()
    for dst, d in graph[p]:
        if not visited[dst]:
            visited[dst] = c + d
            q.append((dst, c + d))
for _ in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    print(visited[x] + visited[y])

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

using namespace std;
typedef long long LL;

int main(){
  int A, B, K;
  cin >> A >> B >> K;
  int num=0;
  for(int i=min(A,B); i>=1; i--){
    if(A%i==0&&B%i==0) num++;
    if(num==K){
      cout << i << endl;
      return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 256
//Har Har Mahadev
using namespace std;
#include <bits/stdc++.h>
#define booga cout << "booga" << endl
#define ll long long int
#define pb push_back
#define mp make_pair
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " -> " << a << endl;
	err(++it, args...);
}

void testcase(){
	string s;
	cin >> s;
	int n = s.size();
	if(s[n-1] == 's')cout << s << "es";
	else cout << s << 's';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--){
		testcase();
	}
	return 0;
}


Measured memory_bytes: 3632
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count
from functools import lru_cache
from collections import defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    K,X = mis()
    print('Yes' if (500*K>=X) else 'No')


main()


Measured memory_bytes: 5684
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;

int main()
{
    int N, M;
    cin >> N >> M;
    vint cnt(N+1);
    for (size_t i = 0; i < M; i++)
    {
        int a,b;
        cin>>a>>b;
        cnt[a]++;
        cnt[b]++;
    }
    for (size_t i = 0; i < N; i++)
    {
        if(cnt[i]%2==1)
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

Measured memory_bytes: 3712
n = int(input())
lis = list(map(int,input().split()))
ans = [0]

for i in lis:
    if i % 2 == 0:
        if i%3 != 0 and i%5 != 0:
            ans[0]=1
            break
if ans[0] == 0:
    print("APPROVED")
else:
    print("DENIED")

Measured memory_bytes: 38256
#include <stdio.h>

int cnt[3];

int main()
{
	int N; scanf ("%d",&N);
	for (int i=0;i<N;i++){
		int x; scanf ("%d",&x);
		int c = 0; while (x % 2 == 0){
			x /= 2; c++;
		}
		if (c >= 2) cnt[2]++;
		else if (c == 1) cnt[1]++;
		else cnt[0]++;
	}

	if (cnt[1] == 0){
		if (cnt[0] > cnt[2] + 1) puts("No");
		else puts("Yes");
	}
	else{
		if (cnt[0] > cnt[2]) puts("No");
		else puts("Yes");
	}

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define SIZE 100005
#define INF 1000000005LL
//#define INF 1e18
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int par[SIZE]; //親
int rnk[SIZE]; //木の深さ
map<int,ll> M; //親がiである木の頂点数

ll s;

//初期化(n要素0オリジン)
void init(int n){
  for(int i=0;i<n;i++){
    par[i] = i;
    rnk[i] = 0;
    M[i] = 1;
  }
}

//xの根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

//x,yの属する集合を併合
void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y)return;

  //違う集合だったとき
  ll a = M[par[x]];
  ll b = M[par[y]];

  if(rnk[x] < rnk[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rnk[x] == rnk[y])rnk[x]++;
  }

  M[par[x]] = M[par[y]] = a+b;
  s -= a*b;
  
}

int n,m;
int a[SIZE],b[SIZE];
ll c[SIZE];

int main(){
  cin >> n >> m;
  s = (ll)n*(n-1)/2;
  rep(i,0,m){
    cin >> a[i] >> b[i];
  }
  init(n);
  for(int i=m-1;i>=0;i--){
    c[i] = s;
    unite(a[i],b[i]);
  }
  rep(i,0,m){
    cout << c[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 9856
#include<bits/stdc++.h>
using namespace std;
int n, k, seq[100005], t, ans, tmp;
char s[100005];
int main(){
    scanf("%d%d%s", &n, &k, s);
    if(s[0] == '0') t++;
    for(int i = 0; i < n; i++){
        if(t%2 == s[i] - '0') t++;
        seq[t]++;
    }
    if(s[n-1] == '0') t++;
    t++;
    if(t <= k*2+1) return 0*printf("%d\n", n);
    for(int i = 0; i <= k*2; i++) tmp += seq[i];
    ans = tmp;
    for(int i = k*2; i < t-2; i += 2){
        tmp += seq[i+1] + seq[i+2] - seq[i-k*2] - seq[i-k*2+1];
        ans = max(ans, tmp);
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 768
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<queue>
#include<tuple>
#include<utility>
#include<map>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define range(a) a.begin(), a.end()
#define endl "\n"
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define MP make_pair
using Graph = vector<vector<int>>;
const unsigned long long mod = 1e9 + 7;
const long long INF = 1LL<<60;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }

int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int x;
	cin >> x;
	if(x==1)
		cout << 0 << endl;
	else
		cout << 1 << endl;

	return 0;
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define PI (3.141592653589793)
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; }
using namespace std;

int H,W;
char maze[1010][1010];
int dp[1010][1010];

signed main(){
    cin>>H>>W;
    dp[1][1]=1;
    rep(i,H)rep(j,W)cin>>maze[i][j];
    rep(i,H){
        rep(j,W){
            if(maze[i][j]=='#')continue;
            chmax(dp[i+1][j+1],(dp[i][j+1]+dp[i+1][j])%mod);
        }
    }
    cout<<dp[H][W]<<endl;
}

Measured memory_bytes: 9216
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
Diff = [0] * (M - 1)
for i in range(0,M-1):
    Diff[i] = X[i+1] - X[i]
Diff.sort()
sum = 0
if N < M:
    for i in range(M - N):
        sum += Diff[i]
    print(sum)
else:
    print("0")



Measured memory_bytes: 13960
S = input()

while True:
    for word in ('dream', 'dreamer', 'erase', 'eraser'):
        if S.endswith(word):
            S = S[:len(S) - len(word)]
            break
    else:
        print('NO')
        break
    if len(S) == 0:
        print('YES')
        break


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define RFOR(i, s, n) for (int i = (n) - 1; i >= (s); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
const long long MOD = 1e9+7, INF = 1e18;
template<class T>inline bool CHMAX(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool CHMIN(T&a,T b){if(a>b){a=b;return true;}return false;}



signed main(){
	int N,M;
	cin>>N>>M;
	vector<int>a(N);
	vector<int>cnt(200020,0);
	REP(i,N)cin>>a[i];
	REP(i,M){
		int t;
		cin>>t;
		cnt[t]++;
	}
	
	vector<int>sum(200020,0);
	REP(i,200020){
		if(cnt[i]==0)continue;
		for(int j = 1;j*i<=200020;j++){
			sum[j*i]+=i*cnt[i];
		}
	}
	vector<int>add(200020,0);
	FOR(i,1,200020){
		add[i] = add[i-1] + M - sum[i];
	}
	int ans = 0;
	REP(i,N){
		ans += add[a[i]];
	}
	cout<<ans<<endl;
}


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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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

    int A, B;
    cin >> A >> B;
    cout << max(max(A+B, A-B), A*B) << endl;

    return 0;
}



Measured memory_bytes: 256
#ABC100-D Patisserie ABC
"""
+を採用するか-を採用するかで各評価値が2通りなので、
2**3の全探索を行えば良い
"""
import sys
from copy import deepcopy
from operator import itemgetter
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n,m = map(int,readline().split())
xyz = []
for i in range(n):
    xyz.append(list(map(int,readline().split())))

ans = 0

for i in range(1<<4):
    res = [0]*n
    for j in range(3):
        if i>>j&1==1:
            for k in range(n):
                res[k] += -xyz[k][j]
        else:
            for k in range(n):
                res[k] += xyz[k][j]
    
    res.sort(reverse=True)
    res2 = abs(sum(res[:m]))

    ans = max(ans,res2)


print(ans)

    

Measured memory_bytes: 40304
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define REP(i, n) for(int i = 0; i < n; i++)
#define max(v) *max_element(v.begin(), v.end())
#define min(v) *min_element(v.begin(), v.end())
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int MOD=1000000007;

int main(void){
  int n;
  cin>>n;
  if(n==3 || n==5 || n==7)
    cout<<"YES"<<endl;
  else
    cout<<"NO"<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define MAX_N (1<<18)
#define INF 100000000
#define MOD 1000000007
#define EPS 1e-10
#define SI 1001
using namespace std;
typedef long long ll;
typedef pair<int,bool> P;
typedef pair<P,P> PP;

int n, x;
int a[100000];

int main(){
    cin >> n >> x;
    ll ans = 0;
    rep(i,n){
        cin >> a[i];
        if(a[i] > x){
            ans += a[i]-x;
            a[i] = x;
        }
    }
    for(int i = 1; i < n; i++){
        if(a[i]+a[i-1] > x){
            ans += a[i-1]+a[i]-x;
            a[i] = x-a[i-1];
        }
    }
    cout << ans << endl;
}


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

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

    while (true) {
        int n, m; cin >> n >> m;
        if (n+m == 0) break;

        vector<int> vec(n);
        rep(i, n) cin >> vec[i];

        int ans = 0;
        rep(i, n) rep(j, n) {
            if (i==j) continue;
            if (vec[i]+vec[j]<=m) ans = max(ans, vec[i]+vec[j]);
        }

        if (ans) cout << ans << endl;
        else cout << "NONE" << endl;
    }
}


Measured memory_bytes: 3148
#include<iostream>
using namespace std;
long long calc(long n){
  if((n+1)%2)return ((n/2)%2?1:0)^n;
  else return (((n+1)/2)%2?1:0);
}
int main(){
  long long a,b;
  cin>>a>>b;
  cout<<(calc(b)^calc(a-1))<<endl;
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
from itertools import combinations
def inpl(): return map(int, input().split())

N = int(input())
S = [list(input()) for _ in range(N)]
ans = 0

for k in range(N):
    for i, j in combinations(range(N), 2):
        if S[i][(j+k)%N] != S[j][(i+k)%N]:
            break
    else:
        ans += N

print(ans)


Measured memory_bytes: 46392
n, m = map(int, input().split())
a, b = [0]*n, [0]*n
c, d = [0]*m, [0]*m
for i in range(n):
    a[i], b[i] = map(int,input().split())
for i in range(m):
    c[i], d[i] = map(int,input().split())


for i in range(n):
    l = 10 ** 9
    for j in range(m):
        if abs(a[i] - c[j]) + abs(b[i] - d[j]) < l:
            l = abs(a[i] - c[j]) + abs(b[i] - d[j])
            idx = j + 1

    print(idx)

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>
#include <iomanip>
#include <limits>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <list>
#include <cctype>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)

locale l = locale::classic();

int main(){
    int s;
    cin >> s;
    int x=s/100, y=s%100;
    if(1<=x && x<=12 && 1<=y && y<=12) cout << "AMBIGUOUS" << endl;
    else if(1<=y && y<=12) cout << "YYMM" << endl;
    else if(1<=x && x<=12) cout << "MMYY" << endl;
    else cout << "NA" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD 1000000007
#define eps 1e-8
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
//ifstream cinn("input.txt");ofstream coutt("output.txt");

int w[100],v[100],n,weight;

int dp[100][100001];

int fv(int i,int sum){
    if(sum>weight)return INT_MIN;
    if(i==n)return 0;
    if(dp[i][sum]!=-1)return dp[i][sum];
    int ans=max(fv(i+1,sum+w[i])+v[i],fv(i+1,sum));
    return dp[i][sum]=ans;
}

signed main(){
    FASTER;
    memset(dp,-1,sizeof(dp));
    cin>>n>>weight;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    cout<<fv(0,0);
}

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

int main(){
    int n;
    cin >> n;
    int A[n];
    for(int i = 0; i < n; i++) cin >> A[i];
    
    int count = 0;
    int min;
    for(int i = 0; i < n; i++){
        min = i;
        for(int j = i; j < n; j++){
            if(A[j] < A[min]) min = j;
        }
        if(min != i){
            swap(A[i], A[min]);
            count++;
        }
    }
    
    cout << A[0];
    for(int i = 1; i < n; i++) cout << " " <<A[i];
    cout << endl << count << endl;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
#define M 200010

int main() {
  long int K,N,nokori,roop;
  nokori = 0;
  roop = 0;
  int now = 1;
  int kaori;
  
  cin >> N >> K ;
  int A[N+1];
  int sumi[N+1] = {};
  int route[N+1] = {};
  int route2[N+1] = {};
  nokori = K + 1;
  
  for(int i=1;i<N+1;i++){
    cin >> A[i];
  }
 
  for(int i=0;i<N;i++){
    if(sumi[now] == 1){
      kaori = now;
      break;
    }
    nokori--;
    if(nokori == 0){
      cout << now << endl;
      break;
    }
    sumi[now] = 1;
    //cout << now << endl;
    now = A[now];
  }
  
  route[1] = kaori;
  now = A[now];
  roop = 1;
  
  if(nokori != 0){
    for(int i=2;i<N;i++){
      if(kaori == now)
        break;
      route[i] = now;
      now = A[now];
      roop++;
    }
    
    //cout << nokori << endl;
    
    nokori = nokori % roop;
    if(nokori == 0)
      cout << route[roop] << endl;
    else
      cout << route[nokori] << endl;
  }
  
}


Measured memory_bytes: 6760
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        double l = sc.nextDouble();
        double a = l / 3;
        double ans = a * a * a;
        System.out.println(String.format("%1$.7f", ans));
    }
}

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

typedef long long ll;
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

#define pi pair<int,int>
#define pl pair<lld,lld>

#define dump(x) cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl

#define mem0(x) memset(x,0,sizeof(x))
#define fillnum(x,n) fill(begin(x),end(x),n)
#define asort(x) sort(x.begin(),x.end())
#define dsort(x,t) sort(x.begin(),x.end(),greater<t>())
#define vuniq(x) x.erase(unique(x.begin(), x.end()), x.end())

#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)

int main() {
    string S;
    cin >> S;
    if(S.size() == 9){
        if(S == "AKIHABARA"){
            cout << "YES" << endl;
            exit(0);
        }
    } else if(S.size() == 8){
        if(S == "KIHABARA" || S == "AKIHBARA" || S == "AKIHABRA" || S == "AKIHABAR"){
            cout << "YES" << endl;
            exit(0);
        }
    } else if(S.size() == 7){
        if(S == "KIHBARA" || S == "KIHABRA" || S == "KIHABAR" || S == "AKIHBRA" || S == "AKIHBAR" || S == "AKIHABR"){
            cout << "YES" << endl;
            exit(0);
        }
    } else if(S.size() == 6){
        if(S == "AKIHBR" || S == "KIHABR" || S == "KIHBAR" || S == "KIHBRA"){
            cout << "YES" << endl;
            exit(0);
        }
    } else if(S.size() == 5){
        if(S == "KIHBR"){
            cout << "YES" << endl;
            exit(0);
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 3604
use strict;
use warnings;
use feature qw/ say /;

my $N = <>;
my @A = split /\s/, <>;

my $h = ();
my $i = 1;
$h->{$_} = $i++ for (@A);

my @out = map { $h->{$_} } (1 .. $N);

say join ' ', @out;

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

typedef struct rectangle {
    int w;
    int d;
} rect;

bool cmp_area(const rect &r1, const rect &r2) {
    return r1.w*r1.d < r2.w*r2.d;
}

void cut_rect(rect *r, int s, rect &r1, rect &r2) {
    int w = r->w;
    int d = r->d;
    s = s % (w+d);

    if (s < w) {
        r1.w = s;
        r1.d = d;
        r2.w = w-s;
        r2.d = d;
    } else {
        r1.w = w;
        r1.d = s-w;
        r2.w = w;
        r2.d = d-(s-w);
    }

    return;
}

int main() {
    while (true) {
        int n, w0, d0;
        cin >> n >> w0 >> d0;

        if (n == 0 && w0 == 0 && d0 == 0)
            break;

        vector<rect> vec;
        rect dummy = {0, 0};
        vec.push_back(dummy);
        rect rect_init = {w0, d0};
        vec.push_back(rect_init);

        for (int i = 0; i < n; i++) {
            int p, s;
            cin >> p >> s;
            rect rect_p = vec[p];
            vec.erase(vec.begin() + p);
            rect r1, r2;
            cut_rect(&rect_p, s, r1, r2);
            if (r1.w*r1.d < r2.w*r2.d) {
                vec.push_back(r1);
                vec.push_back(r2);
            } else {
                vec.push_back(r2);
                vec.push_back(r1);
            }
        }

        sort(vec.begin(), vec.end(), cmp_area);
        for (int i = 1; i < n+1; i++) {
            cout << vec[i].w * vec[i].d << " ";
        }
        cout << vec[n+1].w * vec[n+1].d << endl;
    }

    return 0;
}



Measured memory_bytes: 3128
n,k=map(int,input().split())
s=input()
ans=""
for i in range(n):
    if i==k-1:
        if s[i]=="A":
            ans+="a"
        elif s[i]=="B":
            ans+="b"
        else:
            ans+="c"
    else:
        ans+=s[i]
print(ans)


Measured memory_bytes: 3060
import math

n,k = (int(x) for x in input().split())

temp = 0
for i in range(1,n+1):
    x = math.ceil(math.log2(k/i))
    #print(x)
    if x<0:
        x=0
    temp += 1/2**x
    
print(temp/n)


Measured memory_bytes: 2940
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            String[] array = reader.readLine().split(" ");
            int N = Integer.parseInt(array[0]);
            int D = Integer.parseInt(array[1]);

            int ret = N / (D * 2 + 1);
            if (N % (D * 2 + 1) != 0) {
                ret++;
            }

            System.out.println(ret);
        }
    }

}


Measured memory_bytes: 23380
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int k,n;
    cin >> k >> n;
    int pos[n + 1];

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


    int dist = 0;
    for(int i=0;i<n;i++)
    {
        if(abs(pos[i+1] - pos[i]) > dist)
        {
            dist = abs(pos[i+1] - pos[i]);
        }
    }

    cout << k - dist << endl;

    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,a,b,x[111111],y[111111],p,q,num[111111],dis,pa[111111],l,r,ans,id,mx[111111];
pair<pair<long long,long long>,long long> point[111111],d,u;
long long dist(long long a,long long b)
{
	return max(abs(x[a]-x[b]),abs(y[a]-y[b]));
}
long long root(long long x)
{
	if (pa[x]!=x) pa[x]=root(pa[x]);
	return pa[x];
}
void Union(long long x,long long y)
{
	long long rx=root(x),ry=root(y);
	if (rx==ry) return;
	pa[rx]=ry;
}
int main()
{
	scanf("%lld%lld%lld",&n,&a,&b);
	for (long long i=1;i<=n;i++) pa[i]=i;
	for (long long i=1;i<=n;i++)
	{
		scanf("%lld%lld",&p,&q);
		x[i]=p+q;
		y[i]=p-q;
	}
	dis=dist(a,b);
	for (long long i=1;i<=n;i++)
	{
		point[i]=make_pair(make_pair(x[i],y[i]),i);
	}
	sort(point+1,point+n+1);
	for (long long i=1;i<=n;i++)
	{
		id=point[i].second;
		d=make_pair(make_pair(x[id]-dis,y[id]-dis),1);
		u=make_pair(make_pair(x[id]-dis,y[id]+dis),n);
		l=lower_bound(point+1,point+n+1,d)-point;
		r=upper_bound(point+1,point+n+1,u)-point-1;
		if (l>r) continue;
		num[id]=num[id]+r-l+1;
		Union(id,point[l].second);
		for (long long j=max(mx[l],l);j<=r-1;j++)
		{
			Union(point[j].second,point[j+1].second);
		}
		mx[l]=max(mx[l],r);
	}
	for (long long i=1;i<=n;i++) mx[i]=0;
	for (long long i=1;i<=n;i++)
	{
		point[i]=make_pair(make_pair(y[i],x[i]),i);
		swap(x[i],y[i]);
	}
	sort(point+1,point+n+1);
	for (long long i=1;i<=n;i++)
	{
		id=point[i].second;
		d=make_pair(make_pair(x[id]-dis,y[id]-dis+1),1);
		u=make_pair(make_pair(x[id]-dis,y[id]+dis-1),n);
		l=lower_bound(point+1,point+n+1,d)-point;
		r=upper_bound(point+1,point+n+1,u)-point-1;
		if (l>r) continue;
		num[id]=num[id]+r-l+1;
		Union(id,point[l].second);
		for (long long j=max(mx[l],l);j<=r-1;j++)
		{
			Union(point[j].second,point[j+1].second);
		}
		mx[l]=max(mx[l],r);
	}
	for (long long i=1;i<=n;i++)
	{
		if (root(i)==root(a)) 
		{
			ans+=num[i];
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
int main() {
  ll a,b,c,d;
  cin >>a>>b>>c>>d;
  ll k=lcm(c,d);
  cout <<b-a+1-((b/c-(a-1)/c)+(b/d-(a-1)/d)-(b/k-(a-1)/k))<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll A, B, C, X, Y;
    ll ans = 0;
    ll m;

    cin >> A >> B >> C >> X >> Y;

    m = min({X, Y});
    if (A+B < 2 * C) {
        ans += m * (A+B);
        X -= m;
        Y -= m;
    } else {
        ans += m * 2 * C;
        X -= m;
        Y -= m;
    }

    if (X == 0) {
        if (B < 2*C) {
            ans += Y * B;
        } else {
            ans += Y * 2 * C;
        }
    } else {
        if (A < 2*C) {
            ans += X * A;
        } else {
            ans += X * 2 * C;
        }
    }

    cout << ans << endl;
}


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

int main(void){
    int n,x;
    int ans;
    cin >>n>>x;
    if(n==1){
        if(x==2){
            ans=3;
        }else{
            ans=2;
        }
    }else if(n==2){
        if(x==1){
            ans=3;
        }else{
            ans=1;
        }
    }else{
        if(x==1){
            ans=2;
        }else{
            ans=1;
        }
    }
    cout << ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int A, B, K;
    cin >> A >> B >> K;
    for(int i = A; i <= min(A+K-1,B) ; i++) cout << i << endl;
    for(int i = max(A+K, B-K+1); i <=B ; i++) cout << i << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG

signed main() {
  int X, K, D; cin >> X >> K >> D;
  if(X < 0) X = -X;
  if(X/D >= K) cout << X-K*D << endl;
  else {
    int k = X/D;
    X -= k*D;
    K -= k;
    if(K%2 == 0) cout << X << endl;
    else cout << abs(X-D) << endl;
  }
    

}


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

vector<int> L, R;
priority_queue<int> Lque;
priority_queue<int, vector<int>, greater<int> > Rque;
int main()

{
    cin >> N;
    L.resize(N);
    R.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> L[i] >> R[i];
        Rque.push(R[i]);
        Lque.push(L[i]);
    }

    vector<int> Llst;
    vector<int> Rlst;
    while (!Rque.empty())
    {
        int Rtmp = Rque.top();
        int Ltmp = Lque.top();
        Rque.pop();
        Lque.pop();
        Rlst.push_back(Rtmp);
        Llst.push_back(Ltmp);
        if (Ltmp <= Rtmp) break;
    }
    // for (auto i : Llst) cout << i << " ";
    // cout << endl;
    // for (auto i : Rlst) cout << i << " ";
    // cout << endl;

    long long ans1 = abs(Llst[0]);
    long long ans2 = abs(Rlst[0]);

    int i = 0;
    while (i < (int)Llst.size())
    {
        if (Rlst[i] < Llst[i])
        {
            ans1 += Llst[i] - Rlst[i];
        }
        else
        {
            ans1 += abs(Llst[i]);
            break;
        }
        if (i == (int)Llst.size()-1 || Rlst[i] >= Llst[i+1])
        {
            ans1 += abs(Rlst[i]);
            break;
        }
        else
        {
            ans1 += Llst[i + 1] - Rlst[i];
        }
        i++;
    }

    i = 0;
    while (i < (int)Rlst.size())
    {
        if (Rlst[i] < Llst[i])
        {
            ans2 += Llst[i] - Rlst[i];
        }
        else
        {
            ans2 += abs(Rlst[i]);
            break;
        }
        if (i == (int)Llst.size() - 1 || Llst[i] <= Rlst[i + 1])
        {
            ans2 += abs(Llst[i]);
            break;
        }
        else
        {
            ans2 += abs(Rlst[i + 1] - Llst[i]);
        }
        i++;
    }

    cout << max(ans1, ans2) << endl;
    return 0;
}

Measured memory_bytes: 2548
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
int a[1001], b[1001];
pair<pair<int, int>, int> p[1001];
int main()
{
	int n, m, i;
	for (; ~scanf("%d%d", &n, &m),n; ) {
		for (i=0; i<n; ++i) scanf("%d", a+i);
		b[0] = m / a[0] * a[0];
		int min = b[0], minid = 0;
		for (i=1; i<n; ++i) {
			b[i] = 0;
			while (b[i] < min) b[i] += a[i];
			if (b[i] == min && b[i] + a[i] <= m && a[i] < a[minid])
				b[i] += a[i];
			if (b[i] > m) b[i] = m / a[i] * a[i];
			if (min > b[i]) { min = b[i]; minid = i; }
		}
		for (i=0; i<n; ++i) p[i] = make_pair(make_pair(b[i], a[i]), i+1);
		sort(p, p+n);

		int res = -1;
		if (p[0].first == p[1].first) 
			res = n;
		else
			res = p[0].second;
		printf("%d\n", res);
	}
	return 0;
}

Measured memory_bytes: 0