akhauriyash/Code-Regression huggingface dataset:
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;

struct edge {
    int to, from, cost, id;
};

const int MAX_N = 100;
const int MAX_M = 1000;
const int INF = 100000;

int N, M;
int d[MAX_N][MAX_N];

edge E[2 * MAX_M];

bool used[MAX_M];

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

    cin >> N >> M;

    fill(d[0], d[MAX_N], INF);

    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a - 1][b - 1] = c;
        d[b - 1][a - 1] = c;
        edge et = { a - 1, b - 1, c, i };
        E[i * 2] = et;
        edge es = { b - 1, a - 1, c, i };
        E[i * 2 + 1] = es;
    }

    for (int i = 0; i < N; i++) {
        d[i][i] = 0;
    }

    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int res = 0;

    for (int k = 0; k < 2 * M; k++) {
        edge e = E[k];
        if (!used[e.id]) {
            for (int i = 0; i < N; i++) {
                if (d[i][e.from] + e.cost == d[i][e.to]) {
                    used[e.id] = true;
                    res++;
                    break;
                }
            }
        }
    }

    cout << M - res << "\n";

    return 0;
}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
using namespace std;
int main()
{
int x;
cin>>x;
if(x%10==2||x%10==4||x%10==5||x%10==7||x%10==9)
    cout<<"hon\n";
else if(x%10==0||x%10==1||x%10==6||x%10==8)
    cout<<"pon\n";
else if(x%10==3)
    cout<<"bon\n";

return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define il inline
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define rep0(i, n) for(int i = 0; i < (n); i ++)
#define per0(i, n) for(int i = (n) - 1; i >= 0; i --)
#define ept 1e-9
#define INF 0x3f3f3f3f
#define sz(x) (x).size()
#define All(x) (x).begin(), (x).end()
#define lowbit(x) ((x) & -(x))
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
inline ll read1()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const ll mod = 1e9 + 7;
const int N = 4e6 + 10;
const db pi = acos(-1);
vi a[1010];
int main()
{
	int n = read();
	int Q = read();
	
	while(Q --)
	{
		int op = read();
		if(op == 0) {int x = read();a[x].pb(read());}
		if(op == 1) 
		{
			int x = read();
			if(sz(a[x])) rep0(i, sz(a[x]) - 1) cout << a[x][i] << " ";
			if(sz(a[x])) cout << a[x][sz(a[x]) - 1];
			puts("");
		}
		if(op == 2) a[read()].clear();
	}
	return 0;
}



Measured memory_bytes: 5784
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define pii pair<int,int>
#define pll pair<ll,ll>
const int maxn = 1000000;
ll mod = INF;

int a,b;

int main(){
    cin >> a>>b;
    for(int i=1;i<=10000;i++){
        if(i*108/100-i==a&&i*110/100-i==b){
            cout << i<<endl;
            return 0;
        }
    }
    cout << -1<<endl;
    return 0;
}

Measured memory_bytes: 3588
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

SA = list(input())
SB = list(input())
SC = list(input())
S = {"a":SA, "b":SB, "c":SC}
turn = "a"
while 1:
	if len(S[turn]) == 0:
		break
	turn = S[turn].pop(0)
print(turn.upper())


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

int main(){
    int n, m;
    cin >> n >> m;
    map<ll,int, greater<ll>> v;
    rep(i, n) {
        ll a;
        cin >> a;
        v[a]++;
    }
    rep(i, m){
        int b; ll c;
        cin >> b >> c;
        v[c] += b; 
    }
    int u = n;
    ll ans = 0;
    for(auto x: v){
        if(u == 0) break;
        ans += x.first*min(u,x.second);
        u -= min(u,x.second);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12800
// atcoder/abc079/D/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int h, w;
  while (cin >> h >> w) {
    const int N = 10;
    int g[N][N];
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < N; ++j) {
        cin >> g[i][j];
      }
    }
    for (int k = 0; k < N; ++k) {
      for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
          setmin(g[i][j], g[i][k] + g[k][j]);
        }
      }
    }

    int sum = 0;
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
        int a;
        cin >> a;
        if (a != -1) sum += g[a][1];
      }
    }
    cout << sum << endl;
  }

  return 0;
}


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

int main(){
    int H, W;
    cin >> H >> W;
    while(1){
        if(H==0&&W==0) break;
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                cout << "#";
            }
            cout << endl;
        }
    cout <<endl;
    cin >> H>> W;
        
    }
    return 0;
    
}


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

using namespace std;

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

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

 int n,k,res=0;
  cin >> n >> k;
  rep(i,0,n){
    int h;
    cin >> h;
    if(h>=k) res++;
  }
  
 cout << res << endl;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    long long int n;
    cin>>n;
    vector<long long int> v(n);
    
    REP(i,n){
        cin>>v[i];

    }
    long long int all_money = abs(v[0])+abs(v[n-1]);
    FOR(i,1,n){
        all_money += abs(v[i] - v[i - 1]);
    }

    cout << all_money - abs(v[0])-abs(v[1]-v[0]) + abs(v[1]) << endl;
    FOR(i,1,n-1){
        cout << all_money - abs(v[i] - v[i - 1]) - abs(v[i + 1] - v[i]) + abs(v[i + 1] - v[i - 1]) << endl;
    }
    cout << all_money - abs(v[n - 1] ) - abs(v[n - 1] - v[n - 2]) + abs(v[n -2]) << endl;
    return 0;
}


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

static class Capitalize
{
    static void Main()
    {
        var s = Console.ReadLine()
            .Select( x => x == ' ' || x == '.'
                ? x
                : x + 'A' - 'a' )
            .Select( x => (char)x )
            .ToArray();
        Console.WriteLine( new string( s ) );
    }
}

Measured memory_bytes: 5556
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;
typedef long long llong;
const int MOD=1000000007;

int main(int argc, char**argv){
    int n, q;
    string s;

    cin >> n >> q;
    cin >> s;

    int l[q], r[q];
    for (int i = 0; i < q; i++){
        cin >> l[i] >> r[i];
    }

    vector<int> counters(n);
    for (int i = 0; i < n; i++) counters[i] = 0;

    for (int k = 0; k < s.size()-1; k++){
        if (s[k] ==  'A'){
            if (s[k+1] == 'C'){
                counters[k+1]++;
            }
        }
    }

    // cumulative sum
    for (int k = 1; k < s.size(); k++){
        counters[k+1] += counters[k];
    }

    for (int i = 0; i < q; i++){
        cout << counters[r[i]-1] - counters[l[i]-1] << endl;
    }

    return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
int main(){
	
  long long int w=0,i=0,j=0,y=0,z=0;
  string a,b,out;
  cin >> a >> b;
  long long int m= a.size(),n =b.size();
  long long int dp[m+1][n+1];
  memset(dp,0,sizeof(dp));
  for(i=1;i<=m;i++){
  	for(j=1;j<=n;j++){
    	if(a[i-1]==b[j-1]){dp[i][j]=1+dp[i-1][j-1];}
      	else{
        	dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
  }
  i= m;j =n;
  while(i>0&&j>0){
  	if(a[i-1]==b[j-1]){
      out.push_back(a[i-1]);
       i--;
       j--;
      }
    else{
      if(dp[i-1][j]>=dp[i][j-1]){i--;}
      else{j--;}
    }
  }
  //while(i--){out.push_back(a[i]);}
  //while(j--){out.push_back(b[j]);}
  //cout << dp[m][n]<<endl;
	for(i=out.size()-1;i>=0;i--){
    	cout << out[i]; 
    }
  /*for(i=0;i<=m;i++){
  	for(j=0;j<=n;j++){
    cout << dp[i][j]<<" ";
    }
    cout << endl;
  }*/
  
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cout<<#x<<"="<<x<<endl;
#define db2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
using namespace std;
int a,b,c;
int main() {
	cin>>a>>b>>c;
	printf("%d\n",c-min(a-b,c));
	return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader input =new BufferedReader (new InputStreamReader (System.in));
		String str = input.readLine( );

		String before = str;
		String after = "";
		int diff = 0;

		while(before.length() > 0){
			after = before.replace(String.valueOf(before.charAt(0)), "");
			diff = before.length() - after.length();
			if(diff%2 != 0){
				System.out.println("No");
				System.exit(0);
			}
			before = after;
		}

		System.out.println("Yes");

	}

}


Measured memory_bytes: 8400
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
ll gcd(ll a,ll b){
	if (a%b == 0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}

}

//最小公倍数
ll lcm(ll a,ll b){
	return a /gcd(a,b) * b;
}

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

// 素因数分解
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

// 10進数から2進数
int binary(int bina){
    int ans = 0;
    for (int i = 0; bina>0 ; i++)
    {
        ans = ans+(bina%2)*pow(10,i);
        bina = bina/2;
    }
    return ans;
}






int main() {
  int n,m; cin >>n >>m;
  vector<int> x(n, 0);
  rep(i,m){
    int a,b; cin >>a >>b;
    if(a==1) x[b]++;
    if(b==n) x[a]++;
  }
  for(int i = 2; i<n; i++){
    if(x[i]==2){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}

Measured memory_bytes: 4076
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct block{
	int w,s,v;
	void input(){
		scanf("%d%d%d",&w,&s,&v);
	}
	bool operator<(block a){
		return w+s<a.w+a.s;
	}
}bk[1005];
int n;
ll dp[20005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)bk[i].input();
	sort(bk+1,bk+n+1);
	for(int i=1;i<=n;i++)for(int j=bk[i].s;j>=0;j--)dp[j+bk[i].w]=max(dp[j+bk[i].w],dp[j]+bk[i].v);
	printf("%lld\n",*max_element(dp,dp+20005));
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define r(i,n) for(auto i=0;i<n;i++)
#define s(c) static_cast<int>((c).size())

int main(){
	int n;
	cin >> n;
	int64_t fib[n+1];
	fib[0] = fib[1] = 1;
	for(int i = 2; i <= n; i++){
		fib[i] = fib[i-1] + fib[i-2];
	}
	cout << fib[n] << endl;
}


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

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

    int poor = 0;
    if (a == b)
        poor++;
    if (b == c)
        poor++;
    if (c == a)
        poor++;

    if (poor == 1)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String n = scan.next();
    String x = scan.next();
    String t = scan.next();
    int nn = Integer.parseInt(n);
    int xx = Integer.parseInt(x);
    int tt = Integer.parseInt(t);
    
    int times;
    if (nn % xx == 0) {
      times = nn / xx;
    } else {
      times = (nn / xx) + 1;
    }
    int answer = tt * times;
    
    System.out.println(answer);
  }
}

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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
        #define eprintf(...) 42
#endif

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

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

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

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

  map<char, int> cnt;
  rep(i, n){
    cnt[s[i]]++;
  }

  ll ans = (ll)n*(n-1)/2;
  for(auto c : cnt){
    ans -= (ll)c.second*(c.second-1)/2;
  }

  cout << ans+1 << endl;

  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
typedef long long int ll;
using namespace std;
using Graph = vector<vector<int> >;

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int A,B;
cin>>A>>B;
int ans=1+2+3-A-B;
cout<<ans<<endl;
//system("pause");
return 0;
}

Measured memory_bytes: 256
fun main(args : Array<String> ) { 
  val m:MutableMap<Char, Int> = mutableMapOf()
  readLine()!!.toList().map { x ->
    if( m.get(x) == null ) 
      m[x] = 0
    m[x] = m[x]!! + 1
  }
  val r = m.all { xy ->
    val (x, y) = xy
    y%2 == 0
  }
  when(r) {
    true -> println("Yes")
    false -> println("No")
  }
}


Measured memory_bytes: 33804
n, a, b = map(int, input().split())
mod = 1000000007


def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a // b
        a, b = b, a-c*b
        p, q = q, p-c*q
    return p + mod if p < 0 else p


def comb(n, r, mod):
    numerator = denominator = 1
    for i in range(r):
        numerator = numerator * (n - i) % mod
        denominator = denominator * (i + 1) % mod
    return numerator * inv(denominator, mod) % mod


ans = pow(2, n, mod) - comb(n, a, mod) - comb(n, b, mod) - 1
print(ans % mod)


Measured memory_bytes: 38640
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int n = sc.nextInt();
			int m = sc.nextInt();
			if (n == 0 && m == 0)
				break;
			boolean[] inf = new boolean[n];
			inf[0] = true;
			for (int i = 1; i < inf.length; i++)
				inf[i] = false;
			int[] t = new int[m];
			int[] dt = new int[m];
			int[] s = new int[m];
			int[] d = new int[m];
			for (int i = 0; i < m; i++) {
				t[i] = sc.nextInt();
				dt[i] = t[i];
				s[i] = sc.nextInt() - 1;
				d[i] = sc.nextInt() - 1;
			}
			Arrays.sort(dt);
			for (int i = 0; i < m; i++)
				for (int j = 0; j < m; j++)
					if (t[j] == dt[i] && inf[s[j]] && !inf[d[j]])
						inf[d[j]] = true;
			int result = 0;
			for (int i = 0; i < inf.length; i++)
				if (inf[i])
					result++;
			System.out.println(result);
		}
		sc.close();
	}
}

Measured memory_bytes: 84232
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

using namespace std;
#define int long long
using ll = long long;
const int MX = 1e6;
const ll inf = 1e13;
const int mod = 1e9+7;
signed main() {
    
    string n;
    cin >> n;
    int ans = 0;
    rep(i,n.length()) {
        int c = (int)(n[i]-'0');
        ans +=c;
        ans %=9;
    }
    if(ans==0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}



Measured memory_bytes: 3748
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        
        Scanner sc = new Scanner(System.in);
        
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[] h = new int[N];
		int min = Integer.MAX_VALUE;
		int sub = 0;
		
		for(int i=0; i<N; i++) {
			h[i]= sc.nextInt();
		}
		Arrays.sort(h);
		for(int i=0; i<N-K+1; i++) {
			sub = h[i+K-1] - h[i];
			min = Math.min(min, sub);
		}
		System.out.println(min);
    }
}

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

int main(void) {
    long n;
    cin >> n;
    vector<pair<long,long>> a(n);
    for(long i=0; i<n; i++) {
        long x;
        cin >> x;
        a[i] = {x, i};
    }
    sort(a.begin(), a.end());

    set<long> s, rs;
    s.insert(n);
    s.insert(-1);
    rs.insert(-n);
    rs.insert(+1);

    long r = 0;
    for(long i=0; i<n; i++) {
        long x, idx;
        tie(x, idx) = a[i];
        long ub = *s.lower_bound(idx);
        long lb = -(*rs.lower_bound(-idx));

        s.insert(idx);
        rs.insert(-idx);

        r += x * (ub - idx) * (idx - lb);
    }
    cout << r << endl;
}


Measured memory_bytes: 22144
/**************************************************************************
Coded by: Saba Karimi(_VINTAGE)
Institution: AIT PUNE
***************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define ld long double
#define int long long int 
/**************************************************************************/
int mod = 1e9+7;
const int N = 1e6+7;
int mul(int a,int b)
{
    return ((a%mod)*(b%mod))%mod;
}
int add(int a,int b)
{
    return ((a%mod)+(b%mod))%mod;
}
int sub(int a,int b)
{
    return ((a%mod)-(b%mod)+mod)%mod;
}
int power(int a,int b)
{
    int res = 1;
    while(b!=0)
    {
        if(b&1)
            res = mul(res,a);
        b  = b>>1;
        a = mul(a,a);
    }
    return res;
}
int imodulo(int a)
{
    int ans = power(a,mod-2);
    return ans;
}
bool cmp(pii &p1,pii &p2)
{
    if(p1.first<p2.first)
        return true;
    if(p1.first == p2.first)
    {
        return p1.second<=p2.second;
    }
    return false;
}
int par[N];
int sz[N];
int ans;
void init()
{
    for(int i=1;i<N;i++)
    {
        par[i] = i;
        sz[i] = 1;
    }
}
int root(int x)
{
    while(x!=par[x])
    {
        x= par[x];
    }
    return x;
}
void unite(int x,int y)
{
    int rx = root(x);
    int ry = root(y);
    if(rx == ry)
        return ;
    ans-=(sz[rx]*sz[ry]);
    if(sz[rx]<sz[ry])
    {
        par[rx] = ry;
        sz[ry]+=sz[rx];
    }
    else
    {
        par[ry] = rx;
        sz[rx]+=sz[ry];
    }
}
signed main()
{
    fast;
    int n,m;
    cin>>n>>m;
    init();
    int u[m+1],v[m+1];
    for(int i=1;i<=m;i++)
        cin>>u[i]>>v[i];
    ans = (n*(n-1))/2;
    int res[m+1];
    for(int i=m;i>=1;i--)
    {
        res[i] = ans;
        unite(u[i],v[i]);
    }
    for(int i=1;i<=m;i++)
        cout<<res[i]<<"\n";
}

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

int main(){
	int n, q, query, x, t, s;
	
	cin>>n>>q;
	
	list<int> hoge[n];
	
	for(int i = 0; i < q; i++){
		cin>>query>>t;
		
		if(query == 0){
			cin>>x;
			hoge[t].push_back(x);
		} else if(query == 1){
			bool flag = false;
			for(int y : hoge[t]) cout<<(flag++?" ":"")<<y;cout<<endl;
		} else {
			cin>>s;
			hoge[s].splice(hoge[s].end(), hoge[t]);
		}
	}
	
	return 0;
}


Measured memory_bytes: 18632
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <cstring>
#include <bitset>
#include <functional>
#include <random>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define hr putchar(10)
#define pb push_back
#define lc (o<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define ls lc,l,mid
#define rs rc,mid+1,r
#define x first
#define y second
#define io std::ios::sync_with_stdio(false)
#define endl '\n'
#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int P = 1e9+7, INF = 0x3f3f3f3f;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}
ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}
inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}
//head



const int N = 1e6+10;
int n, f[N];

int main() {
	scanf("%d", &n);
	f[n] = n, f[n-1] = (ll)n*n%P;
	int s = 0;
	PER(i,1,n-2) {
		s = (s+f[i+3])%P;
		f[i] = (s+i+1+(ll)(n-1)*(n-1)+f[i+1])%P;
	}
	printf("%d\n", f[1]);
}








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

def main():
    list_ = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    k = int(input())
    print(list_[k - 1])

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
n = int(input())
h = list(map(int, (input().split())))
ans = 0
tmp = 0
for i in range(1, n):
   #print(i, tmp, ans)
  if h[i-1] >= h[i]:
    tmp += 1 
  if h[i-1] < h[i] or i == n-1:
    if ans <= tmp:
      ans = tmp
    tmp = 0
print(ans)
  

Measured memory_bytes: 63984
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define FOR(a, b, c) for (int (a) = (b); (a) < (c); ++(a))
#define ROF(a, b, c) for (int (a) = (c) - 1; (a) >= (b); --(a))
#define REP(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))

int main() {
    char c;
    cin >> c;
    cout << char(c + 1) << endl;
    return 0;
}


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

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

using namespace std;
const int N = 1e5+5;
int n;
long long ans, a[N];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lld",a+i);
    sort(a+1,a+1+n);
    if(n%2) {
        for(int i=n/2+2;i<=n;++i) ans+=2*a[i];
        for(int i=1;i<=n/2-1;++i)ans-=2*a[i];
        ans -= a[n/2]+a[n/2+1];
        //long long dif = 2*a[n/2+1]-a[1]-a[n/2+2];
        //if(dif>0) ans+=dif;
        long long ans2=0;
        for(int i=n/2+3;i<=n;++i) ans2+=2*a[i];
        for(int i=1;i<=n/2;++i) ans2-=2*a[i];
        ans2+=a[n/2+1]+a[n/2+2];
        ans = max(ans2,ans);
    } else {
        for(int i=n/2+2;i<=n;++i) ans+=2*a[i];
        ans += a[n/2+1];
        for(int i=1;i<=n/2-1;++i) ans-=2*a[i];
        ans -= a[n/2];
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 1152
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

#ifdef _DEBUG
#include "../../library/library/debug_template.cpp"
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

	int N;
	cin >> N;

	lint ans = 1LL * N * (N  + 1) * (N + 2) / 6;
	vector<vector<int>> edges(N);
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		if (u > v) swap(u, v);
		ans -= 1LL * u * (N - v + 1);
	}

	cout << ans << "\n";

	return 0;
}



Measured memory_bytes: 7960
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll INF=1e18;
    ll n,m;
    cin>>n>>m;
    ll dis[n][n];
    ll a,b,c;
    for(int i=0;i<n;i++){
    	for(int j=0;j<n;j++){
    		if(i==j){
    			dis[i][j]=0;
    		}else{
    			dis[i][j]=INF;
    		}
    	}
    }
    for(int i=0;i<m;i++){
    	cin>>a>>b>>c;
    	dis[a][b]=c;
    }
    for(int k=0;k<n;k++){
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    		}
    	}
    }
    bool maki=true;
    for(int i=0;i<n;i++){
    	if(dis[i][i]<0)maki=false;
    }
    if(maki){
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			if(j)cout <<" ";
    			if(dis[i][j]>INF/2){
    				cout <<"INF";
    			}else{
    				cout << dis[i][j];
    			}
    		}
    		cout <<endl;
    	}
    }else{
    	cout << "NEGATIVE CYCLE" <<endl;
    }
    return 0;
}



Measured memory_bytes: 3292
use std::io;


fn main() {
    let (a, b) = {
        let i = read::<usize>();
        (i[0], i[1])
    };
    if b % a == 0 {
        println!("{}", a + b);
    } else {
        println!("{}", b - a);
    }
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
std::str::FromStr,
T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    A = LI()

    cnt = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j]<A[minj]:
                minj = j
        if i!=minj:
            A[i], A[minj] = A[minj], A[i]
            cnt+=1

    print(*A)
    print(cnt)

if __name__ == '__main__':
    resolve()



Measured memory_bytes: 5628
#include<iostream>
    #include<stdio.h>
    //#include <bits/stdc++.h>
    #include<vector>
    #include<float.h>
    #include<iomanip>
    #include<algorithm>
    #include<string>
    #include<cstring>
    #include<math.h>
    #include<cmath>
    #include<sstream>
    #include<set>
    #include<map>
    #include<queue>
    #include <cassert>
    #include <cmath>
    #include<cstdint>

    #define INF 1e9
    #define rep(i,n)for(int i=0;(i)<(int)(n);i++)
    #define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
    #define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
    #define vec(type,n) vector<type>(n)
    #define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))

    using namespace std;
    using ll = long long;
    using Graph = vector<vector<int>>;
    using P = pair<int,int>;

    ll cmb(ll n,int a,int mod){
        ll res = 1;
        rep(i,a){
            res *= (n-i);
            res /= (i+1);
            res %= mod;
        }
        return res;
    }

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

    int main(){
      int n,k;cin>>n>>k;
      VEC(int,h,n);
      sort(h.begin(),h.end());
      int res = INF;
      rep(i,n-k+1){
          res = min(h[k-1+i]-h[i],res);
      }
      cout<<res;
    }
    


Measured memory_bytes: 640
#include<iostream>
int n,s;
int count=0;

int method(int i,int j,int k){
  if(n==i){
    if(j==s){
      count++;
    }
    return 0;
  }
  if(k>9){
    return 0;
  }
  method(i+1,j+k,k+1);
  method(i,j,k+1);
  return 0;
}

int main(){

  while(std::cin >> n >> s){
    if(n==0&&s==0){
      break;
    }
    count =0;
    method(0,0,0);

    std::cout << count << std::endl;
  }
}

Measured memory_bytes: 3048
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>

#define MP make_pair
#define P pair

using namespace std;

int main()
{
	int n;
	double ans = 0;
	vector<int> cal;
	int top;
	int kizi;
	int doru;
	int top_cnt = 1;
	//割らないでおく値
	int true_value;

	cin >> n;

	cin >> doru;
	cin >> top;

	cin >> kizi;
	
	ans = kizi / doru;

	true_value = kizi;

	for (int i = 0; i < n; i++)
	{
		int now_top;
		cin >> now_top;

		cal.push_back(now_top);
	}

	sort(cal.begin() , cal.end());
	reverse(cal.begin() , cal.end());

	for (int i = 0; i < cal.size(); i++)
	{
		true_value += cal[i];
		//割る数は元の値とトッピングの数
		double value = (double)true_value / (doru + top * top_cnt);
		
		if (ans >= value)
		{
			break;
		}
		ans = value;

		top_cnt++;
	}

	cout << (int)ans << endl;

	return 0;
}

Measured memory_bytes: 1220
line1 = input('')
line2 = input('') 
result = True
cnt = int(line1)
list = line2.split(' ')
if len(list) != cnt:
  result = False
if result:
  for no_str in list:
    no = int(no_str)
    if no % 2 == 0:
      if no % 3 != 0 and no % 5 != 0:
        result = False

if result :
  print('APPROVED')
else:
  print('DENIED')



Measured memory_bytes: 3060
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i ++){
            int t = scan.nextInt();
            if (set.contains(t)){
                System.out.println("NO");
                return;
            }else
                set.add(t);
        }
        System.out.println("YES");
    }
}


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

#define mp make_pair
#define eb emplace_back
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#endif

const int MAXN = 100;
//#define int long long
const int INF = 1e9;

void solve(){
string s, t;
	cin >> s >> t;
	int n = (int)s.size();
	int m = (int)t.size();

	int ans = INF;
	for (int i = 0; i <= n - m; i++){
		int res = 0;
		for (int j = 0; j < m; j++){
			if (t[j] != s[i + j]) res++;
		}
		ans = min(ans, res);
	}

	cout << ans << '\n';
}

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

		solve();

    return 0;
}


Measured memory_bytes: 3664
from functools import reduce
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K * x)
        x = (x * x)
        n //= 2
    return (K * x)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 1000000007
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 1000000007)

N,K = (int(x) for x in input().split())
for i in range(1,K+1):
    if i > N-K+1:
        print('0')
    else:
        a = comb(K-1,i-1)
        b = comb(N-K+1,i)
        print(a*b%1000000007)

Measured memory_bytes: 3940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)
#define VL vector<ll>
#define VS vector<string>
#define VB vector<bool>
#define VP vector<pair<ll,ll>>
#define VVL vector<vector<ll>>
#define VVP vector<vector<pair<ll,ll>>>
#define PL pair<ll,ll>
#define ALL(v) (v).begin(), (v).end()
ll d1[4] = {1, -1, 0, 0};
ll d2[4] = {0, 0, 1, -1};

ll gcd(ll a, ll b){
    if(a < b) return gcd(b, a);
    ll r = a % b;
    while(r != 0){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

ll lcm(ll a, ll b){
    ll ret = a / gcd(a,b) * b;
    return ret;
}

int main(){
    ll n;
    cin >> n;
    cout << lcm(2, n) << endl;
    return 0;
}

Measured memory_bytes: 3592
N = int(input())
S = str(input())

r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = S.count('B')

ans = r_cnt*g_cnt*b_cnt

for i in range(N):
    for d in range(1, N):
        j = i + d
        k = j + d
        if k >= N:break
        if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
            ans -= 1

print(ans)

Measured memory_bytes: 9072
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.TreeSet;

public class Main {

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] head1 = br.readLine().split(" ");
    String[] head2 = br.readLine().split(" ");
    String[] head3 = br.readLine().split(" ");
    int h = Integer.parseInt(head1[0]);
    int w = Integer.parseInt(head1[1]);
    int ch = Integer.parseInt(head2[0]) - 1;
    int cw = Integer.parseInt(head2[1]) - 1;
    int dh = Integer.parseInt(head3[0]) - 1;
    int dw = Integer.parseInt(head3[1]) - 1;

    String[] map = new String[h];
    int[][] warp_count_tbl = new int[h][w];
    for (int i = 0; i < h; i++) {
      map[i] = br.readLine();
      Arrays.fill(warp_count_tbl[i], Integer.MAX_VALUE);
    }

    Queue<Player> queue = new ArrayDeque<>();
    Queue<Player> queue2 = new ArrayDeque<>();
    Player start = new Player(ch, cw);
    int warp_count = 0;
    warp_count_tbl[start.h][start.w] = warp_count;
    TreeSet<Player> set = new TreeSet<>();
    queue2.add(start);
    while (!queue2.isEmpty()) {
      queue.addAll(queue2);
      queue2.clear();
      while (!queue.isEmpty()) {
        Player player = queue.poll();
        if (warp_count_tbl[player.h][player.w] < warp_count) {
          continue;
        }
        if (player.h == dh && player.w == dw) {
          continue;
        }
        for(int i = player.h - 2; i <= player.h + 2; i++){
          if(i < 0 || i >= h){
            continue;
          }
          for(int j = player.w - 2; j <= player.w + 2; j++){
            if(j < 0 || j >= w){
              continue;
            }
            if(map[i].charAt(j) != '.'){
              continue;
            }
            if(warp_count_tbl[i][j] <= warp_count){
              continue;
            }
            if(Math.abs(player.h - i) + Math.abs(player.w - j) == 1){
              // Up Down Left Right
              warp_count_tbl[i][j] = warp_count;
              queue.add(new Player(i, j));
            } else if (warp_count_tbl[i][j] > warp_count + 1){
              // Warp
              warp_count_tbl[i][j] = warp_count + 1;
              set.add(new Player(i, j));
            }
          }
        }
      }
      warp_count++;
      for (Player p : set) {
        if (warp_count_tbl[p.h][p.w] == warp_count) {
          queue2.add(p);
        }
      }
      set.clear();
    }
    System.out.println(warp_count_tbl[dh][dw] == Integer.MAX_VALUE ? -1 : warp_count_tbl[dh][dw]);
  }

  static class Player implements Comparable<Player> {
    int h;
    int w;

    public Player(int h, int w) {
      this.h = h;
      this.w = w;
    }
    @Override
    public int compareTo(Player o) {
      if (this.h != o.h) {
        return Integer.compare(this.h, o.h);
      }
      return Integer.compare(this.w, o.w);
    }
  }
}

Measured memory_bytes: 62668
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define tii tuple<int,int,int>
signed main(){
  int N,Y;
  cin>>N>>Y;
  Y/=1000;
  int x=-1,y=-1,z=-1;
  Y-=N;
  REP(i,0,N){
    REP(j,0,N-i){
      if(i*9+j*4==Y){
        x=i;
        y=j;
        z=N-i-j;
        goto QQ;
        }
      }
    }
  QQ:
  printf("%d %d %d\n",x,y,z);
}


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

template<typename T>
void fin (T a){
    cout<<a<<endl;
    exit(0);
}
template<typename S>
void print(S a){
    cout<<a<<endl;
}


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


    ll  a,b,v,w,t;
    cin>>a>>v>>b>>w>>t;
    if(abs(a-b)<=t*(v-w)){
        cout << "YES" <<endl;
        return 0;
    }else{
        cout << "NO" << endl;
        return 0;
    }

}


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

int main() {
	int L,R,A,B,C,D;
	string ans;
	cin >> A >> B >> C >> D;
	L = A + B;
	R = C + D;
	if (L > R)
	{
		ans = "Left";
	}
	else if (L < R)
	{
		ans = "Right";
	}
	else
	{
		ans = "Balanced";
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import math
N=int(input())
#考えるべき範囲
ans=11
#絶対ありえない数を定義しておく
for i in range(1,int(math.sqrt(N))+1):
    if N%i !=0:
        continue
    else:
        A=N//i
        A=str(A)
        i=str(i)
        F=max(len(A),len(i))
        if F<ans:
            ans=F

print(ans)
        

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

int main() {
	int n, x;
	bool f = 1;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (!(x & 1) && (x % 3 != 0 && x % 5 != 0)) f = 0;
	}
	puts(f ? "APPROVED" : "DENIED");
	return 0;
}



Measured memory_bytes: 256
N,K = map(int,input().split())
A = list(map(int,input().split()))

A.insert(0,-1)

visited = [False]*(N+1)
now_town = 1
to_start = 0

while 1:
    if visited[now_town] == True:
        break
    else:
        visited[now_town] = True
        now_town = A[now_town]
        to_start += 1

roop_start = now_town

now_town = roop_start
roop = 0
while 1:
    roop += 1
    now_town = A[now_town]
    if now_town == roop_start:
        break

to_start -= roop

if K <= to_start:
    now_town = 1
    for i in range(K):
        now_town = A[now_town]
    print(now_town)
else:
    K -= to_start
    K %= roop
    now_town = roop_start
    for i in range(K):
        now_town = A[now_town]
    print(now_town)









Measured memory_bytes: 92212
#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;
	while (1) {

		
		if (N%1000 == 0) {

			N =0;
			break;
		}
		else {
			N = N % 1000;
			N = 1000 - N;
			break;
		}
		
	}
	cout << N;
}

Measured memory_bytes: 3192
{-# LANGUAGE FlexibleContexts, OverloadedStrings #-}
import Control.Applicative
import Control.Monad
import qualified Data.ByteString.Char8 as B
import Data.Maybe (fromJust)
import Text.Printf
import Debug.Trace

bisearch p l r
  | r - l <= 1 = l
  | otherwise = bisearch p l' r'
    where m = (l+r) `div` 2
          (l',r') = if p m then (m,r) else (l,m)

main = do
  [x] <- getInts
  print $ p2 $ bisearch (\a->a*a<=x) 0 (x+1)
  where p2 x = x*x

-- util
getInts :: IO [Integer]
getInts = map (fst . fromJust . B.readInteger) . B.words <$> B.getLine


Measured memory_bytes: 380
#include <iostream>
#include <numeric>
#include <vector>
#include <math.h>
#include <map>
#include <algorithm>
#include <stdio.h>
#include <set>
#define mod 1000000007
using namespace std; 

int main(){
	int r;
	cin >> r;
	cout << 2 * r * M_PI << "\n";
}


Measured memory_bytes: 3796
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, i, j, k, id, best, x;
	cin >> n;
	vector<int> a(n);
	for (i = 0; i < n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	best = a[n - 1] * 2; id = -1;
	for (i = 0; i < n - 1; i++) {
		if (a[n - 1] % 2 == 0) x = abs(a[i] - (a[n - 1] / 2));
		else x = min(abs(a[i] - (a[n - 1] / 2)), abs(a[i] - (a[n - 1] / 2 + 1)));

		if (x < best) {
			best = x;
			id = i;
		}
	}
	cout << a[n - 1] << " " << a[id] << "\n";

	return 0;
}


Measured memory_bytes: 640
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#define db(x) cerr << #x << ": " << x << '\n';
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}

#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define rz(v, n) v.resize((n) + 1);
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll N = 2e5 + 1;
ll mod;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int power (int a, int b)
{
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	read(p);
	mod = p;
	int c[p] = {}, a[p] = {};
    FOR (i, 0, p - 1) cin >> a[i];
    	
	int ncr[3001][3001] = {}, po[3001][3001] = {};
	ncr[0][0] = po[0][0] = 1;
	FOR (i, 1, 3000)
	{
		ncr[i][0] = po[i][0] = 1;
		FOR (j, 1, i)
			ncr[i][j] = (ncr[i - 1][j] + ncr[i - 1][j - 1]) % p;
		
		FOR (j, 1, 3000)
			po[i][j] = po[i][j - 1]*i % p;
	}
	
	FOR (i, 0, p - 1)
	{
	    int b[p] = {};
	    FOR (j, 0, p - 1) b[j] = -ncr[p - 1][j]*po[p - i][p - 1 - j] % p;
	    b[0]++;
	    FOR (j, 0, p - 1) c[j] = (c[j] + a[i] * b[j]) % p;
	}
	
	FOR (i, 0, p - 1) cout << (c[i] + p) % p << " ";
}


















Measured memory_bytes: 141184
#include<stdio.h>
int ta[10010],to[30010],nt[30010],rta[10010],rto[30010],rnt[30010];
int id[10010],rid[10010],cmp[100010],r=0,f[10010]={0};
void dfs(int s){
  int i;
  f[s]=1;
  for(i=ta[s];i+1;i=nt[i]){
    if(f[to[i]]==0)dfs(to[i]);
  }
  id[rid[s]=r++]=s;//printf("\n");
}
void rdfs(int s,int k){
  int i;
  f[s]=2;
  cmp[s]=k;
  for(i=rta[s];i+1;i=rnt[i]){
    if(f[rto[i]]==1)rdfs(rto[i],k);
  }
}
void scc(int v,int e,int *a,int *b){
  int i,k;
  for(i=0;i<v;i++)ta[i]=rta[i]=-1;
  for(i=0;i<e;i++){
     nt[i]= ta[rto[i]=a[i]];
    rnt[i]=rta[ to[i]=b[i]];
    ta[a[i]]=rta[b[i]]=i;
  }
  for(i=k=0;i<v;i++){
    if(f[i]==0)dfs(i);
  }
  for(i=r;i;i--){
    if(f[id[i-1]]==1)rdfs(id[i-1],id[i-1]);
  }
}
int main(){
  int v,e,a[100010],b[100010],s,t,i;
  scanf("%d %d",&v,&e);
  for(i=0;i<e;i++)scanf("%d %d",&a[i],&b[i]);
  scc(v,e,a,b);
  scanf("%d",&v);
  while(v--){
    scanf("%d %d",&s,&t);
    printf("%d\n",cmp[s]-cmp[t]?0:1);
  }
  return 0;
}

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

int n;
vector<int> graph[100010];

int search(int i){
  int ans = 0;

  vector<int> data;
  for(int j = 0;j < graph[i].size();j++){
    data.push_back(search(graph[i][j]));
  }

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

  for(int j = 1;j <= data.size();j++){
    ans = max(ans, data[j-1] + j);
  }

  return ans;
}

int main(){
  cin >> n;

  int a[100010];
  for(int i = 1;i < n;i++){
    cin >> a[i];
    a[i]--;
    graph[a[i]].push_back(i);
  }

  cout << search(0) << endl;

  return 0;
}

Measured memory_bytes: 13952
num = gets.to_i
@steps = gets.split(" ").map(&:to_i)
@memo = []
@memo[0] = 0
@memo[1] = (@steps[0] - @steps[1]).abs

def recursive_min(step_number)
  if @memo[step_number]
    return @memo[step_number]
  else
    # 1個前からのコスト
    first = (@steps[step_number - 1] - @steps[step_number]).abs + recursive_min(step_number - 1)
    # 2個前からのコスト
    second = (@steps[step_number - 2] - @steps[step_number]).abs + recursive_min(step_number - 2)
    # 小さい方を格納
    min = [first, second].min
    @memo[step_number] = min
    return min
  end
end

(2..num - 1).each do |index|
  recursive_min(index)
end

puts recursive_min(num - 1)

Measured memory_bytes: 11396