akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Dynamic;
using System.Linq;
using System.Security.Cryptography.X509Certificates;

namespace atcorder
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            string s = Console.ReadLine();
            if(3200 <= a)
            {
                Console.WriteLine(s);
            }
            else
            {
                Console.WriteLine("red");
            }
        }
    }
}

//文字配列の取得
//string[] strArray = Console.ReadLine().Split(' ').ToArray();
//string S = strArray[0];
//string T = strArray[1];

//文字列の取得
//string s = Console.ReadLine();

//数字配列の取得
//int[] intArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
//int H = intArray[0];
//int W = intArray[1];

//数字の取得
//int N = int.Parse(Console.ReadLine());

//リスト型(int)の取得
//List<int> A = new List<int>(Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray());

//出力
//Console.WriteLine(ans);
//Console.WriteLine("Yes");
//Console.WriteLine("No");
//Console.WriteLine(cnt);



Measured memory_bytes: 27360
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws java.lang.Exception {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[][][] = new int[4][3][10];

		for(int i=0; i<n; i++) {
			int b = sc.nextInt();
			int f = sc.nextInt();
			int r = sc.nextInt();
			int v = sc.nextInt();

			a[b-1][f-1][r-1] += v;

		}

		for(int i=0; i<4; i++) {
			if(i != 0) System.out.println("####################");
			for(int j=0; j<3; j++) {
				for(int k=0; k<10; k++) {
					System.out.print(" ");
					System.out.print(a[i][j][k]);
				}
				System.out.println();
			}
		}
	}

}



Measured memory_bytes: 29396
#include <iostream>
#include <utility>
#include <functional>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
#include <stdio.h>
#include <sstream>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define rem(i,n,x) for(int i=n;i>x;i--)
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define setp(x) setprecision(x)
using LL = long long;
using ULL = unsigned long long;

int main() {
	int A, B, C;
	cin >> A >> B >> C;

	int count = 0, money = 0;
	rep(i, 0, C) {
		money += A;
		if (money > B) break;
		else count++;
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef tuple<ll, ll, ll> ti;
 
#define REP(a,b,c) for(ll a=b;a<(c);a++)
#define PER(a,b,c) for(ll a=b;a>=(c);a--)
 
ll ii(){ ll x; cin >> x; return x; }
string is(){ string x; cin >> x; return x; }
ld id(){ ld x; cin >> x; return x; }
void oi(ll x){ cout << x; }
void od(ld x){ cout << fixed << setprecision(10) << x; }
void os(string x){ cout << x; }
void oe(){ cout << endl; }
void oie(ll x){ oi(x); oe(); }
void ode(ld x){ od(x); oe(); }
void ose(string x){ os(x); oe(); }

int main(){
    vector<ll> g;
    ll ret=0;
    vector<ll> A;
    ll N=ii();
    REP(i,0,N){
        A.push_back(ii());
    }
    sort(A.begin(),A.end(),greater<ll>());
    ll t=N/2+(N%2);
    REP(i,0,t){
        if(i!=0){
            ret+=A[i-1];
        }
    }
    REP(i,0,N-t-1){
        ret+=A[i+1];
    }
    ret+=A[t-1];
    oie(ret);
    
    return 0;
}

Measured memory_bytes: 5360
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;

int main(){
  int n,k;
  cin >> n >> k;
  int x[n];
  rep(i,n) cin >> x[i];
  
  int dist=0;
  rep(i,n){
    dist += 2*min(x[i], k-x[i]);
  }
  
  cout << dist << endl;
  
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to;
	ld cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
bool suf(ld a, ld b, ld c, ld d) {
	if (b <= c || d <= a) return 0;
	return 1;
}//[a,b),[c,d)
ll fact(ll x, ll k,ll p) {//最大値、個数
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
#define int long long
const long long inf = 4523372036854775807;
const int iinf = 1500000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
int n, m, k;
bool b[100001];
int pa[100001];
int root(int x) {
	if (pa[x] == x) return x;
	return pa[x] = root(pa[x]);
}
void unite(int x, int y) {
	x = root(x);
	y = root(y);
	pa[x] = y;
}
signed main() {
	cin >> n >> m;
	for (int i = 0; i <= m; i++)
		pa[i] = i;
	for (int i = 0; i < n; i++) {
		cin >> k;
		int u1, u2;
		for (int j = 0; j < k; j++) {
			if (j == 0) {
				cin >> u1;
				b[u1] = 1;
			}
			else {
				cin >> u2;
				unite(u1, u2);
				b[u2] = 1;
			}
		}
	}
	int t = 0;
	for (int i = 0; i <= m; i++) {
		if (b[i]) {
			if (t == 0)
				t = i;
			else {
				if (root(t) != root(i)) {
					cout << "NO\n";
					return 0;
				}
			}
		}
	}
	cout << "YES\n";
	getchar(); getchar();
}

Measured memory_bytes: 1536
A, B, C = map(int, input().split())
kawa = False
if A == B and C != A and C != B:
  kawa = True
if B == C and A != B and A != C:
  kawa = True
if A == C and B != A and B != C:
  kawa = True

if kawa:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <numeric>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <utility>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define all(vec) vec.begin(), vec.end()
#define MOD 1e9 + 7
#define INF 1e9
#define SENTINEL 2e9
#define PIE 3.1415926535

template <class T>
inline bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}
template <class T>
inline bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template <class T>
inline T GCD(T a, T b){if (b == 0) return a; else return GCD(b, a % b);}
template <class T>
inline T LCM(T a, T b) {return (a * b) / GCD(a, b);}

int main(){
    int n;
    cin >> n;
    vector<string> v(n);
    set<string> se;
    rep(i, n) {
        cin >> v[i];
        se.insert(v[i]);
    }
    cout << se.size() << endl;
}

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

int main () {
 int n,k;
 cin>>n>>k;
 vector<int> h(n);
 long long cnt =0;
 for (int i=0;i<n;i++){
   cin>>h.at(i);
 }
   sort(h.begin(),h.end());
 if(k==0){
   for(int i=0;i<n;i++){
     cnt +=h.at(i);
   }
   cout <<cnt<<endl;
 } else if(n<k){
   cout <<"0"<<endl;
 } else{
   for (int i=0;i<n-k;i++){
     cnt +=h.at(i);
   }
   cout <<cnt<<endl;
 }
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

int main(void){
    int H,W;
    cin >> H >> W;
    char S[H][W];
    rep(i,H) cin >> S[i];
    int ans=0;
    bool reach[H][W]={};
    int dis[H][W]={};
    bool check=true;
    rep(i,H) rep(j,W) if(S[i][j]=='#') check=false;
    if(check){
        cout << H+W-2 << endl;
        return 0;
    }
    rep(i,H) rep(j,W){
        if(S[i][j]=='#') continue;
        rep(k,H) rep(l,W) dis[k][l]=INF;
        dis[i][j]=0;
        queue<pint> Q;
        rep(k,H) rep(l,W) reach[k][l]=false;
        Q.push(pint(i,j));
        while(!Q.empty()){
            pint p=Q.front();
            Q.pop();
            reach[p.first][p.second]=true;
            if(p.first>0 && S[p.first-1][p.second]!='#') if(reach[p.first-1][p.second]==false) Q.push(pint(p.first-1,p.second)),dis[p.first-1][p.second]=dis[p.first][p.second]+1;
            if(p.first<H-1 && S[p.first+1][p.second]!='#') if(reach[p.first+1][p.second]==false) Q.push(pint(p.first+1,p.second)),dis[p.first+1][p.second]=dis[p.first][p.second]+1;
            if(p.second>0 && S[p.first][p.second-1]!='#') if(reach[p.first][p.second-1]==false) Q.push(pint(p.first,p.second-1)),dis[p.first][p.second-1]=dis[p.first][p.second]+1;
            if(p.second<W-1 && S[p.first][p.second+1]!='#') if(reach[p.first][p.second+1]==false) Q.push(pint(p.first,p.second+1)),dis[p.first][p.second+1]=dis[p.first][p.second]+1;
        }
        rep(k,H) rep(l,W) if(dis[k][l]!=INF) ans=max(ans,dis[k][l]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
// AOJ 2839 Ebi-chan and Integer Sequences
// 2019.3.1 bal4u

#include <stdio.h>
#include <stdlib.h>

#define MOD 1000000007

int main()
{
	long long n, m, k;
	long long ans, t;

	scanf("%lld%lld", &n, &m);
	if (n == 1) {
		printf("%d\n", (int)((m + 1) % MOD));
		return 0;
	}

	k = m / (n - 1);
	if (k & 1)
		ans = ((((k % MOD) * (((k + 1) >> 1) % MOD)) % MOD) * ((n - 1) % MOD)) % MOD;
	else
		ans = (((((k >> 1) % MOD) * ((k + 1) % MOD)) % MOD) * ((n - 1) % MOD)) % MOD;
	t = ((k % MOD) * ((m + 1) % MOD)) % MOD;

	ans = t-ans;
	if (ans < 0) ans += MOD;
	ans = ((m + 1) % MOD) + ((ans << 1) % MOD);
	printf("%d\n", (int)(ans % MOD));
	return 0;
}



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

MOD = 10**9+7
fac = [1]*(N+1)
rev = [1]*(N+1)
 
for i in range(1, N+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD
ans = 0

for i in range(1+min(N-1, K)):
  ans += comb(N, i) * comb(N-1, i)
ans %= MOD
print(ans)


Measured memory_bytes: 45668
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
//assert(q==w) если q!=w --> runtime error
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define ub upper_bound
#define lb lower_bound
#define bit __builtin_popcount
#define memset(x) memset(x,0,sizeof(x))

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<vector<int>> matrix;

inline void boost(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

const ll maxn=2e5+123;
const ll inf=1e9+123;
const ll linf=1e18+123;
const ll mod=1e9+7;
const double eps=1e-9;
const double pi=acos(-1);
int dx[8]={0,1,-1,0,1,-1,1,-1};
int dy[8]={1,0,0,-1,1,1,-1,-1};
int a[maxn];
int main(){
    boost();
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    int mx=0,mn=inf;
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mx=max(mx,a[i]);
        mn=min(mn,a[i]);
    }
    if(mx-mn>=2){
        cout<<"No";
        return 0;
    }
    if(mx==mn){
        bool ok=1,ok1=1;
        for(int i=1;i<=n;i++){
            if(a[i]!=n-1){
                ok=0;
            }
            if(2*a[i]>n){
                ok1=0;
            }
        }
        if(ok==0 && ok1==0){
            cout<<"No";
            return 0;
        }
        cout<<"Yes";
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==mn){
            x++;
        }
        else{
            y++;
        }
    }
    if(x+1<=mx && mx<=x+y/2){
        cout<<"Yes";
        return 0;
    }
    cout<<"No";
    exit(0);
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define mod 1000000007
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 


int main(){
  fastio
  ll x,k,d;
  cin>>x>>k>>d;
  ll dis = abs(x);
  ll ans;
  if(k*d == dis){
    ans =0;
  }
  else if(k < dis/d){
    ans = dis - k*d;    
  }
  else{
    ll steps = dis/d;
    ll far = dis-steps*d;
    ll moves = k - steps;
    if(moves%2==0){
      ans = far;
    }
    else {
      ans = abs(far-d);
    }
   
  }
  cout<<ans<<"\n";
  
  return 0; 
}


Measured memory_bytes: 3592
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"reflect"
	"strconv"
	"strings"
)

// SENTINEL is used for merge sort by adding the last index
var SENTINEL = 2000000000

type Card struct {
	suit  string
	value int
}

func merge(A []Card, n, left, mid, right int) {
	n1 := mid - left
	L := make([]Card, n1+1)
	n2 := right - mid
	R := make([]Card, n2+1)
	for i := 0; i < n1; i++ {
		L[i] = A[left+i]
	}
	for i := 0; i < n2; i++ {
		R[i] = A[mid+i]
	}
	L[n1].value, R[n2].value = SENTINEL, SENTINEL

	i, j := 0, 0
	for k := left; k < right; k++ {
		if L[i].value <= R[j].value {
			A[k] = L[i]
			i++
			continue
		}
		A[k] = R[j]
		j++
	}
}

func mergeSort(A []Card, n, left, right int) {
	mid := 0
	if left+1 < right {
		mid = (left + right) / 2
		mergeSort(A, n, left, mid)
		mergeSort(A, n, mid, right)
		merge(A, n, left, mid, right)
	}
}

func partition(A []Card, n, p, r int) int {
	x := A[r]
	i := p - 1
	for j := p; j < r; j++ {
		if A[j].value <= x.value {
			i++
			A[i], A[j] = A[j], A[i]
		}
	}
	A[i+1], A[r] = A[r], A[i+1]
	return i + 1
}

func quickSort(A []Card, n, p, r int) {
	q := 0
	if p < r {
		q = partition(A, n, p, r)
		quickSort(A, n, p, q-1)
		quickSort(A, n, q+1, r)
	}
}

func answer(r io.Reader) string {
	sc := bufio.NewScanner(r)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	A, B := make([]Card, n), make([]Card, n)
	for i := 0; i < n; i++ {
		sc.Scan()
		ss := strings.Split(sc.Text(), " ")
		A[i].suit = ss[0]
		A[i].value, _ = strconv.Atoi(ss[1])
		B[i].suit, B[i].value = A[i].suit, A[i].value
	}

	mergeSort(A, n, 0, n)
	quickSort(B, n, 0, n-1)

	var buf bytes.Buffer
	if reflect.DeepEqual(A, B) {
		buf.WriteString("Stable\n")
	} else {
		buf.WriteString("Not stable\n")
	}

	for i := 0; i < n; i++ {
		buf.WriteString(B[i].suit + " " + strconv.Itoa(B[i].value) + "\n")
	}
	return strings.TrimRight(buf.String(), "\n")
}

func main() {
	fmt.Println(answer(os.Stdin))
}



Measured memory_bytes: 16908
import java.util.Scanner;

public class Main 
{
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		
		int th = sc.nextInt();
		int ts = sc.nextInt();
		
		int ah = sc.nextInt();
		int as = sc.nextInt();
		
		int tm = ah%ts;
		int t  = ah/ts;
		if(tm > 0)
		{
			t++;
		}
		
		int am = th%as;
		int a  = th/as;
		if(am > 0)
		{
			a++;
		}
		
		if(t <= a)
		{
			System.out.println("Yes");
		}
		else
		{
			System.out.println("No");
		}
		
	
		
		sc.close();
		
		

	}

}


Measured memory_bytes: 35460
#include <stdio.h>

int main(void){

	int N;
	int num1 = 0, num2 = 0, num3 = 0;
	int SUM = 0;

	scanf("%d", &N);

	num1 = N / 100;
	num2 = (N - num1 * 100) / 10;
	num3 = N - num1 * 100 - num2 * 10;

	SUM = num3 * 100 + num2 * 10 + num1 * 1;

	if(N == SUM){
		printf("Yes\n");
	}else{
		printf("No\n");
	}

	return 0;

}


Measured memory_bytes: 128
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;

int main(void) {
  cout << std::fixed << std::setprecision(10);
  cin.tie(0);
  std::ios::sync_with_stdio(false);

  int n;
  cin>>n;
  std::vector<int> a(n);
  std::unordered_set<int> set;
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(set.find(a[i])==set.end()){
      set.insert(a[i]);
    }

  }
  if(set.size()<=3&&n%3==0){
    for(int bitpos=0;std::pow(2,bitpos+1)<=std::pow(10,9);bitpos++){
      int zero_count=0;
      int mask=(1<<bitpos);
      for(auto x:a){
        if((x&mask)==0){
          zero_count++;
        }
      }
      if(zero_count!=n/3&&zero_count!=n){
        cout<<"No"<<endl;
        return 0;
      }
    }
    cout<<"Yes"<<endl;
    return 0;
  }else if(set.size()==1&&*set.begin()==0){
    cout << "Yes" << endl;
  }else{
    cout<<"No"<<endl;
  }

  return 0;
}


Measured memory_bytes: 4004
import math

N, D = map(int, input().split())
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))

dist = 0
cnt = 0
for i in range(N):
    for j in range(N):
        dist = 0
        if j == i:
            continue
        for k in range(D):
            dist += (X[i][k] - X[j][k])**2
        dist = math.sqrt(dist)
        if dist == int(dist):
            cnt += 1
cnt /= 2
print(int(cnt))

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

vector<bool> prime(1e5, true);

int main(){
	prime[0] = prime[1] = false;
	for(int i=2; i*i<(int)prime.size(); i++){
		if(!prime[i]) continue;
		for(int j=2; i*j<(int)prime.size(); j++){
			prime[i*j]=false;
		}
	}
			
	while(1){
		int m, a, b;
		cin >> m >> a >> b;
		if(m==0) break;
		
		int p=0,q=0;
		for(int i=1; i<320; i++){
			if(!prime[i]) continue;
			int j=min(b*i/a, m/i);
			while(j>0 && !prime[j]) j--;
			if(j>=i && j*i > p*q){
				p=i;
				q=j;
			}
		}
		cout << p << " " << q << endl;
	}
	return 0;
}

Measured memory_bytes: 3108
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long lli;
typedef long double lld;
#define mod 1000000007
#define mod2 998244353
#define fori(n) for (int i = 0; i < n; i++)
#define forj(n) for (int j = 0; j < n; j++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl "\n"
#define sortvec(a) sort(a.begin(), a.end())
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl
#define cerr if(true) cerr

template <typename T, typename U>
ostream &operator<<(ostream &out, const pair<T, U> &p)
{
    out << "(" << p.first << ", " << p.second << ")";
    return out;
}
template <template <typename, typename...> class ContainerType, typename ValueType, typename... Args>
void print(const ContainerType<ValueType, Args...> &c)
{
    for (const auto &v : c)
        cout << v << ' ';
    cout << '\n';
}

void print() { cout << '\n'; }
template <typename T, typename... Args>
void print(T a, Args... args)
{
    cout << a << " ";
    print(args...);
}

lli llipower(lli x, lli y, lli p = LLONG_MAX)
{
    lli res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
lli binarySearch(vector<int> arr, int l, int r, int x)
{
    if (r >= l)
    {
        lli mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

//---------------------------------------------------------------------------------


int main(){
    int n;
    cin>>n;
    vector<int> a;
    vector<int> b;
    vector<int> all;
    int x,y;
    fori(n){
        cin>>x>>y;
        a.pb(x);
        b.pb(y);
        all.pb(x);
        all.pb(y);
    }
    sortvec(a);
    sortvec(b);
    sortvec(all);
    if(n%2==0){
        lli m1=a[n/2]+a[n/2 - 1];
        lli m2 = b[n / 2] + b[n / 2 - 1];
        cout<<m2-m1+1<<endl;
    }
    else{
        lli ans=b[n/2 ]-a[n/2]+1;
        cout<<ans<<endl;
    }
}



Measured memory_bytes: 6596
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n;
    cin >> n;
    int sum = 0;
    int MAX = 0;
    rep(i, n) {
        int l;
        cin >> l;
        sum += l;
        chmax(MAX, l);
    }
    sum -= MAX;
    cout << (MAX < sum ? "Yes" : "No") << endl;
}


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

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; --i)
#define INF (1 << 30)
#define MOD 1e9 + 7

char s[10][10];

int main() {
	while(cin >> s[0]) {
		FOR(i, 1, 8) cin >> s[i];
		rep(i, 8) rep(j, 8) if(s[i][j] == '1') {
			if(s[i][j+1] == '1') {
				if(s[i+1][j] == '1' && s[i+1][j+1] == '1') {
					printf("A\n");
					goto end;
				}
				else if(s[i+1][j+1] == '1' && s[i+1][j+2] == '1') {
					printf("E\n");
					goto end;
				}
				else if(s[i][j+2] == '1' && s[i][j+3] == '1') {
					printf("C\n");
					goto end;
				}
				else{
					printf("G\n");
					goto end;
				}
			}
			else {
				if(s[i+1][j-1] == '1' && s[i+1][j] == '1' && s[i+2][j-1] == '1') {
					printf("D\n");
					goto end;
				} 
				else if(s[i+1][j] == '1' && s[i+1][j+1] == '1' && s[i+2][j+1] == '1') {
					printf("F\n");
					goto end;
				}
				else {
					printf("B\n");
					goto end;
				}
			}
		}
		end:;
	}
	return 0;
}

Measured memory_bytes: 2944
var output;
var input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n");
var obj = {
  "list" : input,
  "index" : 0,
  "max" : input.length,
  "next" : function(){
    if(!this.hasNext()){return null;}
    var returnObj = this.list[this.index];
    this.index++;
    return returnObj;
  },
  "hasNext" : function(){return (this.index < this.max);}
}
Main();
function next(){return obj.next();}
function hasNext(){return obj.hasNext();}
function myout(t){console.log(t);}//standard output
function myerr(t){console.error(t);}//standard error
//[no]param
//不明値:何もしない 異常時:文字列「error」を返す（できる？）
//1:数値へ変換 2:半角SPで分割 4:半角SPで分割し、数値配列へ
//6:1文字に分割 7:1文字に分割し、数値配列へ
//8:半角SPで結合 9:改行で結合 0:文字なしで結合
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map((a)=>Number(a));case 6:return i.split("");case 7:return i.split("").map((a)=>Number(a));case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return "error";}}
function Main() {
  var N = myconv(next(),1);
  var list = myconv(next(),4);
  var output = 0;
  var last = 0;
  for(var i = 0; i < N; i++){
    if(i == 0){
       output++;
      last = list[i];
    }else{
      if(last > list[i]){
         output++;
        last = list[i];
      }
    }
  }
  myout(output);
}


Measured memory_bytes: 22224
N,K=map(int,input().split())#n人k種類
hito=[num for num in range(1,N+1)]
for i in range(K):
  d=int(input())#何人持ってるか
  A=list(map(int,input().split()))#2,3
  for a in A:
    if a in hito:
      hito.remove(a)
print(len(hito))

Measured memory_bytes: 9188
#include <bits/stdc++.h> 
using namespace std;
#define int long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
const int MOD = 1e9+7;
int mpow(int a,int b,int p=MOD){a=a%p;int res=1;while(b>0){if(b&1)res=(res*a)%p;a=(a*a)%p;b=b>>1;}return res%p;}
const int N=1e5+3;

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	// #ifndef LOCAL
	#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	// freopen("out10.txt","w",stdout);
	#endif
	int n,m;
	cin>>n>>m;
	cout<<(n*(n-1)/2)+(m-1)*m/2;
}
// Don't be afraid to fail. Be afraid not to try.
// "Become grindian instead of greendian" - aryanc403
// When you want to succeed as bad as you want to breathe, only then you’ll Be Successful!
// No Matter,How Fast You Are Driving If You Are Driving in a Wrong Direction You Will Never Reach Your Destination
// When failures hit you, you hit the failures back with Bounce Back!
// When you face failures, Don’t change your goal, Change your strategy!

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
class Main{
    public static void main(String[] args)throws IOException{
	Scanner s = new Scanner(System.in);
	long a,b;
	
	while(s.hasNext()){
	    a=s.nextInt();
	    b=s.nextInt();
	    System.out.println(getGCD(a,b)+" "+getLCM(a,b));
	    /* System.out.println(a*b);*/
	}
    }
    
    
  
    
    static long getGCD(long a, long b){
	if(b==0)
	    return a;
	else return getGCD(b ,a%b);
	
	    }

      static long getLCM(long a,long b){
	  return a*b/(getGCD(a,b));
    }
}

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

int main() {
    int i,N;
    int k=0;
    string arare;
    cin >> N;
    for (i=0;i<N;i++){
        cin >> arare;
     
        if(arare=="Y"){
            k=1;
        }
    }
    if(k==0){
        cout << "Three" <<endl;
    }
    else if(k==1){
        cout << "Four" <<endl;
    }
}

     


Measured memory_bytes: 256
function Main(input) {
    const inputs = input.split('\n');
    const whiteH = Number(inputs[0].split(' ')[0]);
    const whiteW = Number(inputs[0].split(' ')[1]);
    const blackH = Number(inputs[1].split(' ')[0]);
    const blackW = Number(inputs[1].split(' ')[1]);

    console.log(whiteH * whiteW - (blackH * whiteW + blackW * whiteH) + (blackW * blackH));
};

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

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=200001,INF=1<<30;

int main(){

    int N,K;cin>>N>>K;
    vector<int> A(N),B;
    for(int i=0;i<N;i++){
        cin>>A[i];
    }
    sort(all(A));
    for(int i=0;i<N;i++){
        if(A[i]<K) B.push_back(A[i]);
    }
    int M=int(B.size());
    if(M==0) cout<<0<<endl;
    else{
        
        vector<vector<int>> dp(K,vector<int>(2,0));
        dp[0][1]=1;
        bool ok=false;
        
        for(int i=0;i<M;i++){
            if(i==0){
                for(int j=0;j<=K-1;j++){
                    dp[j][i%2]=dp[j][(i+1)%2];
                }
            }else{
                for(int j=0;j<=K-1;j++){
                    if(j-B[i]<0) dp[j][i%2]=dp[j][(i+1)%2];
                    else if(dp[j-B[i]][(i+1)%2]) dp[j][i%2]=1;
                    else dp[j][i%2]=0;
                }
            }
        }
        
        for(int j=K-B[0];j<=K-1;j++){
            if(dp[j][(M-1)%2]) ok=true;
        }
        
        if(ok) cout<<0<<endl;
        else{
            vector<vector<int>> dp(K,vector<int>(2,0));
            dp[0][1]=1;
            bool ok=false;
            
            for(int i=0;i<M;i++){
                if(i==M-1){
                    for(int j=0;j<=K-1;j++){
                        dp[j][i%2]=dp[j][(i+1)%2];
                    }
                }else{
                    for(int j=0;j<=K-1;j++){
                        if(j-B[i]<0) dp[j][i%2]=dp[j][(i+1)%2];
                        else if(dp[j-B[i]][(i+1)%2]) dp[j][i%2]=1;
                        else dp[j][i%2]=0;
                    }
                }
            }
            
            for(int j=K-B[M-1];j<=K-1;j++){
                if(dp[j][(M-1)%2]) ok=true;
            }
            
            if(!ok) cout<<M<<endl;
            else{
                int left=0,right=M-1;
                while(right-left>1){
                    int mid=(left+right)/2;
                    bool ok=false;
                    vector<vector<int>> dp(K,vector<int>(2,0));
                    dp[0][1]=1;
                    
                    for(int i=0;i<M;i++){
                        if(i==mid){
                            for(int j=0;j<=K-1;j++){
                                dp[j][i%2]=dp[j][(i+1)%2];
                            }
                        }else{
                            for(int j=0;j<=K-1;j++){
                                if(j-B[i]<0) dp[j][i%2]=dp[j][(i+1)%2];
                                else if(dp[j-B[i]][(i+1)%2]) dp[j][i%2]=1;
                                else dp[j][i%2]=0;
                            }
                        }
                    }
                    
                    for(int j=K-A[mid];j<=K-1;j++){
                        if(dp[j][(M-1)%2]) ok=true;
                    }
                    
                    if(ok) right=mid;
                    else left=mid;
                    //cout<<left<<" "<<right<<endl;
                }
                
                cout<<left+1<<endl;
            }
        }
    }
}



Measured memory_bytes: 896
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

int main() {
	int n,m,sum=0;
	cin>>n>>m;
	vector<int>a(m);
	rep(i,m)cin>>a[i];
	rep(i,m)sum+=a[i];
	cout<<max(-1,n-sum);
	return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long  ll;
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main()
{
	ll n, a, b;
	scanf("%lld%lld%lld", &n, &a, &b);

	ll ans = 0;
	ll x[100001] = {};
	scanf("%lld", &x[1]);
	repe(i, 2, n) {
		scanf("%lld", &x[i]);
		ans += min((x[i] - x[i - 1])*a, b);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
def main():
    import sys
    sys.setrecursionlimit(200000)
    input = sys.stdin.readline

    #まずは、どこで閉路が発生しているかを見極める。また、このときに、閉路の辺の数を求める。
    #次に、町1から閉路の始点となっている街にたどり着くまでの辺の数を求めて、Kから引く。これをGとする。
    #Gを閉路の辺の数で割ったあまりを求める。

    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    #path[n] -> 街nに最初につくまでに移動した回数
    path = {}
    #count は現在の移動回数を保持しておく変数
    info = []
    def dfs(n,count):
        if n in path:
            #閉路が発生している、ということなので、path[n]が閉路の始点にたどり着くまでに必要な移動回数
            # count - path[n] +1 が閉路を構成している辺の数
            info.append(path[n])
            info.append(count - path[n] +1)
        else:
            count += 1
            path[n] = count
            nx = A[n-1]
            dfs(nx,count)
    dfs(1,-1)
    x,y = info
    if K <= x:
        for k,v in path.items():
            if v == K:
                print(k)
    else:
        K -= x
        K %= y
        for k,v in path.items():
            if v-x == K:
                print(k)


main()

Measured memory_bytes: 265944
#include <bits/stdc++.h>
#define lli long long int
#define DBG false
using namespace std;

int main(){
	int n;
	string s;
	cin >> n >> s;
	long long r = 0, g = 0, b = 0;
	for(int i=0; i<n; i++){
		if (s[i] == 'R') r++;
		if (s[i] == 'G') g++;
		if (s[i] == 'B') b++;
	}
 
	long long sum = r * g * b;

    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            int k = j + (j - i);
            if(k >= n) break;
            if(s[i] != s[j] && s[i] != s[k] && s[j] != s[k]) sum--;
        }
    }

    cout << sum << endl;
}


Measured memory_bytes: 3544
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));
int main(){
	string S; cin >> S;
	cout << S.front() << S.size()-2 << S.back() << endl;
}


Measured memory_bytes: 256
def main():
    N = int(input())
    if N < 10:
        print(N)
    elif str(N)[1:] == "9"*(len(str(N))-1):
        print(sum(list(map(int,list(str(N))))))
    else:
        ans = sum([9]*(len(str(N))-1))
        if int(str(N)[0]) >= 2:
            ans += int(str(N)[0])-1
        print(ans)

if __name__ == '__main__':
    main()

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

int main()
{
    char b;
    cin >> b;

    if (b == 'A')
        cout << "T" << endl;
    if (b == 'G')
        cout << "C" << endl;
    if (b == 'T')
        cout << "A" << endl;
    if (b == 'C')
        cout << "G" << endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static void main(String[] args){
        FastScanner sc = new FastScanner();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        if(a<b && b<c)System.out.println("Yes");
        else System.out.println("No");

    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}



Measured memory_bytes: 24224
a,b=map(int,input().split())
ans=0
l=[]
for i in range(b):
  i=a
  l.append(str(i))
ans=','.join(l)
ans_1=ans.replace(',','')

new_l=[]
for i in range(a):
  i=b
  new_l.append(str(i))
new_ans=','.join(new_l)
ans_2=new_ans.replace(',','')

if a == b:
  print(ans_1)
  
elif a > b:
  print(ans_2)
  
else:
  print(ans_1)
  
  

Measured memory_bytes: 3064
#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)

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int bitCount(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string a, b, c;  cin >> a >> b >> c;
    if (a[a.size() - 1] == b[0] && b[b.size() - 1] == c[0]) {
      cout << "YES" << '\n';
    } else {
      cout << "NO" << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>

using namespace std;
# define ll long long
# define int long long  //comment it out when MLE
//# define endl "\n"
#define gok ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//# define m 163577857
//# define MOD 163577857
# define pi acos(-1)
# define fi first
# define se second
#define REP(i,n) for (int i = 1; i <= n; i++)

const ll mod = 1000000007;
const int K = 2;
//typedef vector<vector<int> > matrix;
int add(int a, int b,int mod) {
    a%=mod;
    b%=mod;
	a += b;
	if (a >= mod) a -= mod;
	if(a<0)
    {
        a += mod;
        a %= mod;
    }
	return a;
}

int mul(ll a, int b,int mod) {
    a%=mod;
    b%=mod;
	a *= b;
	return a % mod;
}
int po(int a,int b,int mod)
{
    if(b==0)
        return 1;
    if(b%2==0)
        return po(mul(a,a,mod),b/2,mod);
    return mul(a,po(mul(a,a,mod),(b-1)/2,mod),mod);
}


ll fact[1000003];
ll inv[1000003];

void fact0()
{
	int i,j;
	fact[0]=1;
	for(i=1;i<=200000;i++)
	{
		fact[i]=i*fact[i-1]%mod;
	}
	inv[0]=1;
	inv[1]=1;
	ll p=mod;
	for (i=2; i<=200000; i++)
		inv[i] = (p - (p/i) * inv[p%i] % p) % p;

	for(i=2;i<=200000;i++)
	{
		inv[i]*=inv[i-1];
		inv[i]%=mod;
	}
}


signed main()
{
    gok
   //fact0();
  int p;
  cin>>p;
  int st=100;
  int an=1;
  while(st<p)
  {
      int tt = (st*1)/100;
      st+=tt;
      an++;
  }

 cout<<an-1;













    return 0;
    }


Measured memory_bytes: 3648
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define int long long 
using namespace std;
const int N = 2e3 + 5;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
int T, n, k, a, b, c, d;
void solve() {
	a = read(); b = read(); c = read(); d = read(); n = a + b;
	int l = 0, r = n + 1, mid, A, B;
	k = (max(a, b) - 1) / (min(a, b) + 1) + 1;
	while(l < r) {
		mid = (l + r) >> 1;
		A = a - mid / (k + 1) * k - mid % (k + 1); B = b - mid / (k + 1);
		if(B <= A * k) l = mid + 1;
		else r = mid;
	}
	A = a - l / (k + 1) * k - l % (k + 1); B = b - l / (k + 1); r = l + B - A * k + 1;
	for(int i = c; i <= min(d, l); ++ i) putchar(i % (k + 1) ? 'A' : 'B');
	for(int i = max(c, l + 1); i <= d; ++ i) putchar((i - r) % (k + 1) ? 'B' : 'A');
	puts("");
}
signed main() {
	T = read(); while(T -- > 0) solve();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
int main(void){
    ll n,x,in,count=0;
    vector<ll> a,b;
    cin>>n>>x;
    for(int i=0;i<n;i++){
        cin>>in;
        a.push_back(in);
    }
    for(int i=0;i<n-1;i++){
        b.push_back(a[i]+a[i+1]);
    }
    for(int i=0;i<n-1;i++){
        if(b[i]>x){
            ll t=b[i]-x;
            b[i]-=t;
            if(i!=n-2)b[i+1]-=min(a[i+1],t);
            count+=t;
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 2548
N,M = gets.split.map &:to_i
A = Array.new(M) {gets.split.map &:to_i}
X = Array.new N
A.each {|s,c| exit 0*p(-1) if c != X[-s]||=c }
exit 0*p(-1)  if N>1 && (0 == X[-1]||=1)
puts X.map{|x| x||0}.reverse! * ''

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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved
long long n,k;
int path[5010];
long long cost[5010];
vector<vector<long long>>sum(5010,vector<long long>(5010,0));


long long solve(int i){
    int move=1;
    int now=i;
    //1週の長さと累積和を求める。
    while(1){
        //sum[i].push_back(sum[i][move]+cost[path[now]]);
        sum[i][move]=sum[i][move-1]+cost[path[now]];
        move++;
        now=path[now];
        if(now==i){
            //cout<<"path_length="<<move-1<<endl;
            break;
        }
    }
    //L:=1週の長さ
    long long L=move-1;
    long long ret=0;
    
    int end=k%L;
    long long m=-INF;
    rep2(l,end){
        m=max(m,sum[i][l]);
    }
    if(end==0)m=0;
    long long M=-INF;
    //全区間での最大値
    rep2(l,L){
        M=max(M,sum[i][l]);
    }
    if(k>=L && sum[i][L]>=0){
        //ret+=(k/L)*sum[L];
        ret=max(m+(k/L)*sum[i][L],((k/L)-1)*sum[i][L]+M);
    }
    else if(k>=L && sum[i][L]<=0){
        ret=M;
    }
    else{
        ret=m;
    }

    // rep(l,L+1){
    //     cout<<sum[i][l]<<" ";
    // }
    // cout<<endl;
    // cout<<ret<<endl;
    return ret;

}
int main(){
    
    cin>>n>>k;
    rep2(i,n){
        cin>>path[i];
    }
    rep2(i,n){
        cin>>cost[i];
    }
    rep2(i,n)sum[i][0]=0;


    long long ans=-INF;
    rep2(i,n){
        ans=max(solve(i),ans);
    }
    cout<<ans<<endl;
    return 0;

}
/*


*/


Measured memory_bytes: 199396
a, b = map(int, input().split())
count = 0
for i in range(a+1):
  for j in range(a+1-i):
    c = (a-i-j)
    s = (10000*i) + (5000*j) + (1000*c)
    if s == b:
      print(i,j,c)
      count += 1
      break
  else:
    continue
  break
  
if count == 0:
  print(-1,-1,-1)

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

int root(int x,int par[]){
    if (par[x] == x) return x;
    return par[x]=root(par[x],par);
}

int main(void){
    int n,m,q,s,t,i,rs,rt;
    cin>>n>>m;
    int par[100000];
    for(i=0;i<n;i++)par[i]=i;
    
    for(i=0;i<m;i++){
        cin>>s>>t;
        rs=root(s,par),rt=root(t,par);
        if(rs!=rt)par[rs]=rt;
    }

    for(i=0;i<n;i++){
        par[i]=root(i,par);
    }
    
    cin>>q;
    for(i=0;i<q;i++){
        cin>>s>>t;
        if(par[s]==par[t]){
            cout<<"yes"<<endl;
        }
        else{
            cout<<"no"<<endl;
        }
    }
    
    return 0;
}



Measured memory_bytes: 5032
/*Whose woods these are I think I know.
His house is in the village though;
He will not see me stopping here
To watch his woods fill up with snow.

My little horse must think it queer
To stop without a farmhouse near
Between the woods and frozen lake
The darkest evening of the year.

He gives his harness bells a shake
To ask if there is some mistake.
The only other sound’s the sweep
Of easy wind and downy flake.

The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
const int maxn= 100010;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h=0,w=0;string s;
    cin>>h>>w;
    for(int i=0;i<h;++i)
    {
        for(int j=0;j<w;++j)
        {
            cin>>s;
            if(s=="snuke")
            {
                cout<<char(j+65)<<(i+1);
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=505,MAXM=1e4+5;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int n,N,cnt,p[MAXM],vis[MAXM],v[MAXN*3];ll ans[MAXN][MAXN];
inline void pre(int n=1e4){
	Rep(i,2,n){
		if(!vis[i])p[++cnt]=i;
		for(int j=1;j<=cnt&&i*p[j]<=n;j++){
			vis[i*p[j]]=1;if(i%p[j]==0)break;
		}
	}
}ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
inline ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
int main(){
	pre(),n=read();if(n==2){puts("4 7\n23 10");return 0;}N=1;
	Rep(i,1,n)Rep(j,1,n)if((i+j)&1){if(!v[i-j+n])v[i-j+n]=p[++N];ans[i][j]=v[i-j+n];}
	memset(v,0,sizeof(v));
	Rep(i,1,n)Rep(j,1,n)if((i+j)&1){if(!v[i+j])v[i+j]=p[++N];ans[i][j]*=v[i+j];}
	Rep(i,1,n)Rep(j,1,n)if(!((i+j)&1)){
		ans[i][j]=1;
		if(i>1)ans[i][j]=lcm(ans[i][j],ans[i-1][j]);if(j>1)ans[i][j]=lcm(ans[i][j],ans[i][j-1]);
		if(i<n)ans[i][j]=lcm(ans[i][j],ans[i+1][j]);if(j<n)ans[i][j]=lcm(ans[i][j],ans[i][j+1]);
		ans[i][j]++;
	}Rep(i,1,n){Rep(j,1,n)cout<<ans[i][j]<<' ';cout<<'\n';}
	return 0;
}




Measured memory_bytes: 5640
#include<bits/stdc++.h>
#define p 1000000007
#define ll long long
using namespace std;
char s[100010];
ll a[100010];
ll b[100010];
ll c[100010];
ll bc[100010];
inline ll power(ll x, ll y)
{
	ll Ans = 1;
	if(y < 0)
		return 0;
	while(y)
	{
		if(y & 1)
			Ans = Ans * x % p;
		x = x * x % p;
		y >>= 1;
	}
	return Ans;
}
ll q[100010];
ll qh[100010];
int main()
{
	ll Q = 0;
	scanf("%s", s);
	ll len = strlen(s);
	for(ll i = 0; i < len; ++ i)
	{
		a[i + 1] = (a[i + 1] + a[i]) % p;
		b[i + 1] = (b[i + 1] + b[i]) % p;
		q[i + 1] += q[i];
		if(s[i] == 'A')
			a[i + 1] = (a[i + 1] + 1) % p;
		else if(s[i] == 'B')
			b[i + 1] = (a[i + 1] + b[i + 1]) % p;
		else if(s[i] == '?')
		{
			++ q[i + 1];
			++ Q;
		}
	}
	for(ll i = len - 1; i >= 0; -- i)
	{
		c[i + 1] = (c[i + 1] + c[i + 2]) % p;
		bc[i + 1] = (bc[i + 1] + bc[i + 2]) % p;
		qh[i + 1] += qh[i + 2];
		if(s[i] == 'C')
			c[i + 1] = (c[i + 1] + 1) % p;
		else if(s[i] == 'B')
			bc[i + 1] = (bc[i + 1] + c[i + 1]) % p;
		else if (s[i] == '?')
			++ qh[i + 1];
	}
	ll Ans = 0;
	for(ll i = 0; i < len; ++ i)
		if(s[i] == 'C')
			Ans = (Ans + b[i + 1]) % p;
	Ans = Ans * power(3, Q) % p;
	//A
	for(ll i = 0; i < len; ++ i)
	{
		if(s[i] == '?')
			Ans = (Ans + power(3, Q - 1) * bc[i + 1] % p) % p;
	}
	//B
	for(ll i = 0; i < len; ++ i)
	{
		if(s[i] == '?')
			Ans = (Ans + power(3, Q - 1) * a[i + 1] % p * c[i + 1] % p) % p;
	}
	//C
	for(ll i = 0; i < len; ++ i)
	{
		if(s[i] == '?')
			Ans = (Ans + power(3, Q - 1) * b[i + 1] % p) % p;
	}
	//AB
	for(ll i = 0; i < len; ++ i)
	{
		if(s[i] == '?')
			Ans = (Ans + (q[i + 1] - 1) * power(3, Q - 2) % p * c[i + 1] % p) % p;
	}
	//AC
	for(ll i = 0; i < len; ++ i)
	{
		if(s[i] == 'B')
			Ans = (Ans + q[i + 1] * qh[i + 1] % p * power(3, Q - 2) % p) % p;
	}
	//BC
	for(ll i = 0; i < len; ++ i)
	{
		if(s[i] == '?')
			Ans = (Ans + (qh[i + 1] - 1) * power(3, Q - 2) % p * a[i + 1] % p) % p;
	}
	//ABC
	Ans = (Ans + Q * (Q - 1) * (Q - 2) / 6 % p * power(3, Q - 3) % p) % p;
	printf("%lld", Ans);
	return 0;
}

Measured memory_bytes: 4992
#include<iostream>
using namespace std;
int main(){
    int N,n,i,f,a,c;
    cin>>N;
    n=0;
    c=N;
    while(N>0){
        N=N/10;
        n=n+1;
    }
    f=0;
    if(n%2==0){
        a=9;
        n=n-1;
        for(i=n;i>2;i=i-2){
            a=a*100;
            f=a+f;
        }
        f=f+9;
        cout<<f;
    }
    else{
        if(n==1)
            cout<<c;
        else{
            n=n-1;
            a=90;
            for(i=n;i>2;i=i-2){
                a=a*100;
                c=c-a;
            }
            c=c-90;
            cout<<c;
        }
    }
    return 0;
}

Measured memory_bytes: 256