akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

void solve() {
	ll n, x, m;
	cin >> n >> x >> m;
	
	if(x == 0) {
		cout << 0 << endl;
		return;
	}
	
	int ok = 1;
	ll sum = x;
	vector<ll> a(1, x);
	vi seen(m + 1, 0);
	seen[a.back()] = 1;
	for(int i = 2; i <= n; i++) {
		ll res = (a.back() * a.back()) % m;
		
		if(res == 0) {
			cout << sum << endl;
			return;
		}
		
		if(!seen[res]) {
			a.pub(res);
			sum += a.back();
			seen[res] = i;
		} else {
			ok = 0;
			break;
		}
	}
	
	ll ans = sum;
//	if(!ok) {
		n -= a.size();
		ll rep = n / (a.size() - seen[(a.back() * a.back()) % m] + 1);
		sum = 0;
		for(int i = seen[(a.back() * a.back()) % m] - 1; i < a.size(); i++) sum += a[i];
		ans += rep * sum;
		n -= rep * (a.size() - seen[(a.back() * a.back()) % m] + 1);
		for(int i = seen[(a.back() * a.back()) % m] - 1; i < seen[(a.back() * a.back()) % m] + n - 1; i++) ans += a[i];
//	}
	
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	solve();
    return 0;
}

Measured memory_bytes: 4340
#include <bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
    ios::sync_with_stdio(false);
    cin>>a>>b;
    if(a*b==15&&a+b==15)
    {
        cout<<'x';
        return 0;
    }
    if(a*b==15)
    {
        cout<<'*';
        return 0;
    }
    if(a+b==15)
    {
        cout<<'+';
        return 0;
    }
    cout<<'x';
    return 0;
}


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

int main() {
    string a;
    int q, v, w ;
    string str, instr ; 
    cin >> a >>q ;
   
    for(int i = 0; i < q; i++){
        cin >> instr >> v >> w;
        if(instr =="replace"){
            string f;
            cin >> f;
            a = a.replace(v,w-v+1, f);
        }
        if(instr =="reverse"){
            string b = a;
            for(int j = 0; j < w - v +1; j++){
                
                a[v+j] = b[w-j];
            }
        }
        if(instr == "print"){
            string a4 = a.substr(v,w-v+1);
            cout << a4 << endl;
        }
    }
    
return 0;}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using namespace std;

int main(){
  int n,m,a;
  int h,p,q;

  while(cin>>n>>m>>a){
    if(!n)break;
    vector<vector<pair<int,int>>> line(1000);
    REP(i,m){
      cin >> h >> p >> q;
      line[h-1].push_back(make_pair(p,q));
    }
    
    RREP(i,line.size()){
      REP(j,line[i].size()){
	if(line[i][j].first == a)
	  a = line[i][j].second;
	else if(line[i][j].second == a)
	  a = line[i][j].first;
      }
    }
    cout << a << endl;
  }
      
    
  return 0;
}

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

int main(){
  string S,T;
  cin >> S >> T;
  if((S.length()+1)!=(T.length())){
    cout << "No" << endl;
    return 0;
  }
  for(int i=0;i<S.length();i++){
    if(S[i]!=T[i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
 
		if ((a * b * 1 % 2) != 0 || (a * b * 2 % 2) != 0 || (a * b * 3 % 2) != 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		scan.close();
	}
}

Measured memory_bytes: 23124
#include<iostream>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#define INF 1e9
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  return s;
}

template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
  s << vv[i] << endl;
  }
  return s;
}

int N;
vector<pair<ll,ll>> pos;
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> N;
  pos.resize(N);
  for(int n = 0 ; n < N ; n++){
    cin >> pos[n].first >> pos[n].second;
  }

  int parity1 = (abs(pos[0].first) + abs(pos[0].second)) % 2; 
  for(int i = 0 ; i < N ; i++){
    int parity2 = (abs(pos[i].first) + abs(pos[i].second)) % 2;
    pos[i] = make_pair(pos[i].first + pos[i].second,pos[i].first - pos[i].second);
    if(parity2 != parity1){
      cout << "-1" << endl;
      return 0;
    }
  }

  vector<ll> d;
  for(int i = 30; i >= 0 ; i--){
    d.push_back(1LL << i);
  }
  if(parity1 % 2 == 0){
    d.push_back(1);
  }
  cout << d.size() << endl;
  for(int j = 0 ; j < d.size() ; j++){
    cout << d[j] << " ";
  }
  cout << endl;

  for(int i = 0; i < N ; i++){
    int xdir,ydir;
    long long xsum = 0;
    long long ysum = 0;
    for(int j = 0 ; j < (int)d.size() ; j++){
      if (xsum <= pos[i].first) xdir = 1, xsum += d[j];
      else xdir = -1, xsum -= d[j];
      if (ysum <= pos[i].second) ydir = 1, ysum += d[j];
      else ydir = -1, ysum -= d[j];
      
      if (xdir == 1 && ydir == 1) cout << "R";
      else if (xdir == 1 && ydir == -1) cout << "U";
      else if (xdir == -1 && ydir == -1) cout << "L";
      else cout << "D";
    }
    cout << endl;
  }

  return 0;
}
#


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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define MOD 1000000007
typedef pair<li, li> PI;

double dp[333][333][333];

li n;
li a[333];
li cnt[4];

int main(void)
{
	cin >> n;
	rep(i, n) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	dp[0][0][0] = 0;

	rep(i_3, n + 1) {
		rep(i_2, n + 1) {
			rep(i_1, n + 1) {
				if (i_1 == 0 && i_2 == 0 && i_3 == 0) {
					continue;
				}
				dp[i_3][i_2][i_1] = 0.0;
				if (i_3 > 0) {
					dp[i_3][i_2][i_1] += i_3 * (dp[i_3 - 1][i_2 + 1][i_1] + 1);
				}
				if (i_2 > 0) {
					dp[i_3][i_2][i_1] += i_2 * (dp[i_3][i_2 - 1][i_1 + 1] + 1);
				}
				if (i_1 > 0) {
					dp[i_3][i_2][i_1] += i_1 * (dp[i_3][i_2][i_1 - 1] + 1);
				}
				double p = 1.0 * (i_3 + i_2 + i_1) / n;
				dp[i_3][i_2][i_1] = (dp[i_3][i_2][i_1] * 1.0 / (i_3 + i_2 + i_1) + (1 - p) / p);
			}
		}
	}
	printf("%.12f\n", dp[cnt[3]][cnt[2]][cnt[1]]);


	return 0;
}

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

int main() 
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x,y;
    cin>>x>>y;
    if(x*2<=y&&y<=x*4&&y%2==0)
        cout<<"Yes"<<endl;
    else 
        cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
using namespace std;
int a[55];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	double s;
	s=a[0];
	for(int i=0;i<n;i++)
		s=(s+a[i])*1.0/(2*1.0);
	cout<<s;
}

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

int main(){
    int n;

    cin>>n;
    cin.ignore();

    while(n--){
        string str;
        getline(cin,str);

        for(int i=0;i+6<str.length();i++){
            if(str.substr(i,7)=="Hoshino"){
                str.replace(i,7,"Hoshina");
            }
        }

        cout<<str<<endl;
    }

    return 0;
}

Measured memory_bytes: 1220
#include <iostream>

using namespace std;

const int MAX_N = 100000;

int main() {
  int N;
  long long ans = 0;
  int A[MAX_N];
  int B[MAX_N];
  cin >> N;
  for (int i=0; i<N; i++) {
    cin >> A[i] >> B[i];
  }
  for (int i=N-1; 0<=i; i--) {
    int tmp = (A[i] + ans) % B[i];
    if (tmp == 0) continue;
    ans += (B[i] - tmp);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1152
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>

using namespace std;

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

using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

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

    int h, w;
    cin >> h;
    cin >> w;
    int n;
    cin >> n;

    int res = (int)ceil(1.0*n / max(h, w));
    cout << res << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define ll long long 
#define S second
#define pb push_back
const int inf = 1000 * 1000 * 1000 + 1000;
const ll INF = 1LL * 1000 * 1000 * 1000 * 1000 * 1000 * 1000;

const int N = 1000 * 100 + 1000;
int a[N], d[N], x[N];

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

	int n, k, sum = 0, step;
	cin >> n;
	step = n * (n + 1) / 2;
	for(int i = 0; i < n; i++)
		cin >> a[i], sum += a[i];

	if(sum % step != 0){
		cout << "NO\n";
		return 0;
	}

	k = sum / step;
	for(int i = 0; i < n - 1; i++)
		d[i] = a[i + 1] - a[i];
	d[n - 1] = a[0] - a[n - 1];

	sum = 0;
	for(int i = 0; i < n; i++){
		int cnt = k - d[i];
		if(cnt % n != 0 || cnt < 0){
			cout << "NO\n";
			return 0;
		}
		x[i] = cnt / n;
		sum += x[i];
	}
	if(sum != k)
		cout << "NO\n";
	else
		cout << "YES\n";
	return 0;
}

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

int X, Y, Z;
vector<int> V;
vector<int> pl, gt;
vector<vector<double> > dp;

double calc(int v, int m)
{
	if (v == Y) return (double)m;
	if (dp[v][m] > -1.) return dp[v][m];
	
	double sum = 0;
	for (int i = 0; i < V.size(); i++){
		int tv = min(Y, v + V[i]);
		int tm = max(0, m + gt[tv]);
		tv = min(Y, tv + pl[tv]);
		
		sum += calc(tv, tm);
	}
	
	return dp[v][m] = sum / V.size();
}

int main()
{
	while (scanf("%d %d %d", &X, &Y, &Z), X){
		V.resize(X);
		pl = vector<int>(Y + 1, 0);
		gt = vector<int>(Y + 1, 0);
		dp = vector<vector<double> >(Y + 1, vector<double>(6000, -1.));
		
		for (int i = 0; i < X; i++){
			scanf("%d", &V[i]);
		}
		
		for (int i = 0; i < Z; i++){
			int N, E, A;
			scanf("%d %d %d", &N, &E, &A);
			if (E == 1) pl[N] = A;
			if (E == 2) gt[N] = A;
			if (E == 3) gt[N] = -A;
		}
		
		printf("%d\n", (int)calc(0, 0));
	}
}

Measured memory_bytes: 7952
import java.util.*;

public class Main {
    public static void main(final String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long p = sc.nextLong();
        if (n==1) {
            System.out.println(p);
            return;
        }
        if (p==1) {
            System.out.println(1);
            return;
        }
        int max = 1;
        for (int i = 1; Math.pow(i, n) <= p; i++) {
            if (p % Math.pow(i,n) == 0) {
                max = Math.max(max, i);
            }
        }
        System.out.println(max);
    }
}

Measured memory_bytes: 35768
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#c=[]
ct=0
#for i in range(n):
 #   c.append(b[i]-a[i])
for i in range(n):
    if b[i]-a[i]>=0:
        ct+=(a[i]+min(b[i]-a[i],a[i+1]))
        a[i+1]=max(a[i+1]-(b[i]-a[i]),0)
    else:
        ct+=b[i]
print(ct)

Measured memory_bytes: 18624
l, r = map(int, input().split())
dl, ml = divmod(l, 2019)
dr, mr = divmod(r, 2019)
if ml == 0 or mr == 0 or dr - dl != 0 or ml >= mr:
  print(0)
else:
  mi = l*(l+1)%2019
  for i in range(l, r):
    for j in range(i+1, r+1):
      temp = i*j%2019
      if temp < mi:
        mi = temp
  print(mi)

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

using namespace std;

typedef long long ll;

ll const INF = 2e9;
ll const NMAX = 100;
ll const VMAX = 100000;
ll n, w;
ll we[1 + NMAX], v[1 + NMAX];
ll dp[1 + NMAX][1 + VMAX];

int main() {
  cin >> n >> w;
  for(ll i = 1; i <= n; i++) {
    cin >> we[i] >> v[i];
  }
  for(ll i = 0; i <= n; i++) {
    for(ll j = 0; j <= VMAX; j++) {
      dp[i][j] = INF;
    }
  }
  dp[0][0] = 0;
  for(ll i = 1; i <= n; i++) {
    for(ll j = 0; j <= VMAX; j++) {
      dp[i][j] = dp[i-1][j];
      if(j >= v[i]) {
        dp[i][j] = min(dp[i][j], dp[i-1][j-v[i]] + we[i]);
      }
    }
  }
  for(ll j = VMAX; j >= 0; j--) {
    if(dp[n][j] <= w) {
      cout << j;
      return 0;
    }
  }
}


Measured memory_bytes: 79104
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n;
	std::cin >> n;
	for(int i=0;i<=n;i++) {
		if(n==108*i/100) {
			print(i);
			return 0;
		}
	}
	print(":(");
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define pb push_back
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#ifdef __linux__
#define getchar getchar_unlocked
#endif
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
typedef long long LL;
using namespace std;
const int N=310;
const int inf=0x3f3f3f3f;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifdef ztzshiwo
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n,K;
LL mod,dp[N][N],C[N][N],s[N][N];
inline void Add(LL&x,const LL&y){x=x+y<mod?x+y:x+y-mod;}
inline void init()
{
	C[0][0]=1;
	For(i,1,n)
		For(j,0,n)
			Add(C[i][j]=C[i-1][j],j?C[i-1][j-1]:0);
}
int main()
{
	file();
	read(n),read(K),read(mod);
	init();
	For(i,0,K)dp[1][i]=1;
	rFor(i,K,0)Add(s[1][i]=dp[1][i],s[1][i+1]);
	For(i,2,n+1)
	{
		For(j,0,K)
			For(k,1,i-1)
				Add(dp[i][j],s[k][j+1]*dp[i-k][j]%mod*C[i-2][k-1]%mod);
		rFor(j,K,0)Add(s[i][j]=dp[i][j],s[i][j+1]);
	} 
	printf("%lld\n",dp[n+1][0]);
	return 0;
}


Measured memory_bytes: 2432
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace AOJ_Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            var oneLine = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var dice = new Dice(oneLine);
            var rotateList = Console.ReadLine().Select(x => Enum.Parse(typeof(Direction), x.ToString())).ToList();
            foreach (Direction direction in rotateList)
            {
                dice.Rotate(direction);
            }

            Console.WriteLine(dice.Top);
        }
    }

    public class Dice
    {
        public int Top { get; private set; }
        public int Right { get; private set; }
        public int Front { get; private set; }
        public int Left { get; private set; }
        public int Bottom { get; private set; }
        public int Back { get; private set; }


        public Dice(IList<int> numbers)
        {
            //this.Number = numbers.ToArray();
            this.Top = numbers[0];
            this.Back = numbers[1];
            this.Right = numbers[2];
            this.Left = numbers[3];
            this.Front = numbers[4];
            this.Bottom = numbers[5];
        }


        public void Rotate(Direction direction)
        {
            var tmp = this.Top;
            switch (direction)
            {
                case Direction.N:
                    this.Top = this.Back;
                    this.Back = this.Bottom;
                    this.Bottom = this.Front;
                    this.Front = tmp;
                    break;
                case Direction.E:
                    this.Top = this.Left;
                    this.Left = this.Bottom;
                    this.Bottom = this.Right;
                    this.Right = tmp;
                    break;
                case Direction.W:
                    this.Top = this.Right;
                    this.Right = this.Bottom;
                    this.Bottom = this.Left;
                    this.Left = tmp;
                    break;
                case Direction.S:
                    this.Top = this.Front;
                    this.Front = this.Bottom;
                    this.Bottom = this.Back;
                    this.Back = tmp;
                    break;
                default:
                    break;
            }
        }
    }

    /// <summary>
    /// ダイスを転がす方向
    /// </summary>
    public enum Direction
    {
        N,
        E,
        W,
        S
    }

}



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

int main()
{
  int n, m;
  string str;
  char c[256], t;
  while (cin >> n, n){
    str = "";
    for (int i = 0; i < 256; i++) c[i] = i;
    for (int i = 0; i < n; i++){
      cin >> t;
      cin >> c[t];
    }
    cin >> m;
    for (int i = 0; i < m; i++){
      cin >> t;
      str += c[t];
    }
    cout << str << endl;
  }
}

Measured memory_bytes: 1324
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<utility>
#include<tuple>
#include<algorithm>
using namespace std;
#define INF 1e9

int main(){
    string S,T;
    cin>>S>>T;
    int N=S.size();
    if(S==T.substr(0,N)){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    ll A, B, K; cin >> A >> B >> K;
    rep(i, K){
        if (i % 2 == 0){
            if (A % 2 == 1){A--;}
            B += A / 2; A = A / 2;
        } else {
            if (B % 2 == 1){B--;}
            A += B / 2; B = B / 2;
        }
    }
    cout << A << " " << B << endl;
}

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


Measured memory_bytes: 3624
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e20

#solve
def solve():
    def fx(z):
        for i in range(n):
            if i in v:
                continue
            xi, yi = xy[i]
            x = A - xi
            y = B - yi
            if x ** 2 + y ** 2 > z ** 2:
                return False
        return True
    def ff(x1, x2, x3, y1, y2, y3):
        d = 2 * ((y1 - y3) * (x1 - x2) - (y1 - y2) * (x1 - x3))
        x = ((y1 - y3) * (y1 ** 2 - y2 ** 2 + x1 ** 2 - x2 ** 2) - (y1 - y2) * (y1 ** 2 - y3 ** 2 + x1 ** 2 - x3 ** 2)) / d
        y = ((x1 - x3) * (x1 ** 2 - x2 ** 2 + y1 ** 2 - y2 ** 2) - (x1 - x2) * (x1 ** 2 - x3 ** 2 + y1 ** 2 - y3 ** 2)) / -d
        r = math.sqrt((x - x1) ** 2 + (y - y1) ** 2)
        return x, y, r
    n = II()
    x = 0
    y = 0
    xy = LIR(n)
    ans = inf
    for i in range(n):
        for j in range(i):
            x1, y1 = xy[i]
            x2, y2 = xy[j]
            x = (x2 + x1) / 2
            y = (y2 + y1) / 2
            r = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2) / 2
            for k in range(n):
                if i != k and j != k:
                    x3, y3 = xy[k]
                    if (x3 - x) ** 2 + (y3 - y) ** 2 > r ** 2:
                        break
            else:
                ans = min(ans, r)
    # print(ans)
    full = itertools.combinations(range(n), 3)
    for f in full:
        a, b, c = f
        # print(a,b,c)
        axy = xy[a]
        x1, y1 = axy
        bxy = xy[b]
        x2, y2 = bxy
        cxy = xy[c]
        x3, y3 = cxy
        v = [a,b,c]
        a = x1 - x2
        b = y1 - y2
        c = x2 - x3
        d = y2 - y3
        try:
            A = (d * (x1 ** 2 + y1 ** 2 - x2 ** 2 - y2 ** 2) - b * (x2 ** 2 + y2 ** 2 - x3 ** 2 - y3 ** 2)) / (2 * (a * d - b * c))
            B = (-c * (x1 ** 2 + y1 ** 2 - x2 ** 2 - y2 ** 2) + a * (x2 ** 2 + y2 ** 2 - x3 ** 2 - y3 ** 2)) / (2 * (a * d - b * c))
            r = sqrt((x1 - A) ** 2 + (y1 - B) ** 2)
            if fx(r):
                ans = min(ans, r)
        except:
            continue
    
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()


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

int main()
{
  int n, d, x, c = 0;
  cin >> n >> d >> x;
  for (int i = 0; i < n; i++)
  {
    int a, y = 0;
    cin >> a;
    while (1)
    {
      int tmp = (y * a) + 1;
      if (tmp > d)
      {
        break;
      }
      c++;
      y++;
    }
  }
  cout << c + x << endl;
}


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

int main() {
  string S,T;
  cin >> S >> T;
  int sizeS = S.size();
  bool ans = true;
  for ( int i = 0; i < sizeS; i++){
    if (S.at(i) != T.at(i)){
      ans = false;
    }
  }
  if (ans){
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }    
}


Measured memory_bytes: 3628
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <cmath>
#include <cstring>

#define fi first
#define se second
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = 1; i < (n); ++i)
#define drep(i,n) for (int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(), (x).end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define pb push_back
#define sz(x) (int)(x).size()
#define PQ(T) priority_queue<T, v(T), greater<T> >

#define v(T) vector<T>
#define vv(T) v(v(T))

using namespace std;
typedef long long ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;

const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

const int mod = 1000000007;

int main() {
    string s;
    cin >> s;
    ll ans = 0;
    for (int bit = 0; bit < (1<<(sz(s)-1)); ++bit) {
        vector<int> S;
        rep(i,sz(s)-1) {
            if (bit & (1<<i)) S.pb(i);
        }
        if (sz(S)==0) ans += stoll(s);
        else {
            int pre = 0;
            rep(i,sz(S)) {
                int now = S[i];
                string sub = s.substr(pre, now+1-pre);
                ans += stoll(sub);
                
                if (i==sz(S)-1) {
                    string sub = s.substr(now+1, sz(s)-now);
                    ans += stoll(sub);
                }
                pre = now + 1;
            }
        }
        

    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define INIT 1e9+7
using namespace std;
typedef pair<int, int> P;
int c[100000];
vector<P> v[100000];
bool f(int x){
    for(int i=0;i<v[x].size();i++){
        int y = v[x][i].first, z = v[x][i].second;
        if(c[y] == INIT){
            c[y] = c[x] + z;
            if(!f(y))return false;
        }else if(c[y] != c[x] + z){
            return false;
        }
    }
    return true;
}
int main(void){
    int n, m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        r--;
        v[l].push_back(P(r,  d));
        v[r].push_back(P(l, -d));
    }
    for(int i=0;i<n;i++){
        c[i] = INIT;
    }
    for(int i=0;i<n;i++){
        if(c[i] == INIT){
            c[i] = 0;
            if(!f(i)){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 12928
#include <bits/stdc++.h>
#define pb emplace_back
#define mp make_pair

using namespace std;

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.precision(10);
	int a; cin >> a;
	int b; cin >> b;
	int c; cin >> c;
	if (a == b && b == c) cout << "Yes\n";
	else cout << "No\n"; 
}

Measured memory_bytes: 256
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;


typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1e9 + 7;

#define rep(i,b) for(i=0;i<b;++i)
#define repp(i,a,b) for(i=a;i<b;++i)

int main() {
    ll n , k;
    cin >> n >> k;
    ll sum = 0;
    for (size_t i = 0; i < k; i++) {
        /* code */
        ll x;
        cin >> x;
        sum += x;
    }
    if(sum >= n) cout << "Yes";
    else cout << "No";

    return 0;
}
/*
         ,--"""",--.__,---[],-------._
       ,"   __,'            \         \--""""""==;-
     ," _,-"  "/---.___     \       ___\   ,-'',"
    /,-'      / ;. ,.--'-.__\  _,-"" ,| `,'   /
   /``""""-._/,-|:\       []\,' ```-/:;-. `. /
             `  ;:::      ||       /:,;  `-.\
                =.,'__,---||-.____',.=
                =(:\_     ||__    ):)=
               ,"::::`----||::`--':::"._
             ,':::::::::::||::::::::::::'.
    .__     ;:::.-.:::::__||___:::::.-.:::\     __,
       """-;:::( O )::::>_|| _<::::( O )::::-"""
   =======;:::::`-`:::::::||':::::::`-`:::::\=======
    ,--"";:::_____________||______________::::""----.          , ,
         ; ::`._(    |    |||     |   )_,'::::\_,,,,,,,,,,____/,'_,
       ,;    :::`--._|____[]|_____|_.-'::::::::::::::::::::::::);_
      ;/ /      :::::::::,||,:::::::::::::::::::::::::::::::::::/
     /; ``''''----------/,'/,__,,,,,____:::::::::::::::::::::,"
     ;/                :);/|_;| ,--.. . ```-.:::::::::::::_,"
    /;                :::):__,'//""\\. ,--.. \:::,:::::_,"
   ;/              :::::/ . . . . . . //""\\. \::":__,"
   ;/          :::::::,' . . . . . . . . . . .:`::\
   ';      :::::::__,'. ,--.. . .,--. . . . . .:`::`
   ';   __,..--'''-. . //""\\. .//""\\ . ,--.. :`:::`
   ;    /  \\ .//""\\ . . . . . . . . . //""\\. :`::`
   ;   /       . . . . . . . . . . . . . . . . .:`::`
   ;   (          . . . . . . . . . . . . . . . ;:::`
   ,:  ;,            . . . . . . . . . . . . . ;':::`
   ,:  ;,             . . . . . . . . . . . . .;`:::
   ,:   ;,             . . . . . . . . . . . . ;`::;`
    ,:  ;             . . . . . . . . . . . . ;':::;`
     :   ;             . . . . . . . . . . . ,':::;
      :   '.          . . . . . . . .. . . .,':::;`
       :    `.       . . . . . . . . . . . ;::::;`
        '.    `-.   . . . . . . . . . . ,-'::::;
          `:_    ``--..___________..--'':::::;'`
             `._::,.:,.:,:_ctr_:,:,.::,.:_;'`
________________`"\/"\/\/'""""`\/"\/""\/"____________________________

*/


Measured memory_bytes: 384
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X, A):
    ans = 0
    for i, a in enumerate(A):
        ans += max(0, a-X)
        A[i] = min(a, X)

    for i in range(1, N):
        if A[i-1] + A[i] > X:
            ans -= X - (A[i-1] + A[i])
            A[i] += X - (A[i-1] + A[i])
    return ans


def main():
    N, X = read_int_n()
    A = read_int_n()
    print(slv(N, X, A))


if __name__ == '__main__':
    main()


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

using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;

#define INF LONG_MAX
#define MOD 1000000007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.end(),a.begin()

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

  int A,B;
  cin>>A>>B;
  map<int,int>m;
  m[A]++,m[B]++;
  for(int i=1;i<=3;i++){
    if(m[i]==0)cout<<i<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;

fn main() {
    input! {
        d: i64, t: i64, s: i64,
    }

    if d > t * s {
        println!("No");
    } else {
        println!("Yes");
    }
    // println!("{}", );
}


Measured memory_bytes: 2096
import java.util.Scanner;
public class Main {

    public static void main(String[] args) {

            try (Scanner sc = new Scanner(System.in)) {
                int w = sc.nextInt();
                int n = sc.nextInt();
                int[] values = new int[w];
                for (int i = 0; i < values.length; i++) {
                    values[i] = i + 1;
                }
                for (int i = 0; i < n; i++) {
                    String str = sc.next();
                    String[] ab = str.split(",");
                    int a = Integer.parseInt(ab[0]) - 1;
                    int b = Integer.parseInt(ab[1]) - 1;
                    int temp = values[a];
                    values[a]=values[b];
                    values[b]=temp;
                }
                for(int j=0;j<values.length;j++)
                System.out.println(values[j]);
            }
        }
    }



Measured memory_bytes: 26328
#include<stdio.h>
int main(){
  int i,n;
  long num,min,calmax;
  scanf("%d",&n);
  scanf("%ld%ld",&min,&num);
  calmax=num-min;
  if(num<min)
    min=num;
  for(i=2;i<n;i++){
    scanf("%ld",&num);
    if(num-min>calmax)
      calmax=num-min;
    if(min>num)
      min=num;
  }
  printf("%d\n",calmax);
  return 0;
}



Measured memory_bytes: 2144
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int V, E, r;
const long long INF = 1e12;
struct pqdata {
    int no;
    long long d;
    bool operator<(const pqdata &r) const { return d > r.d; }
};

struct graphdata {
    int to; long long dist;
};

vector< vector<graphdata> > graph(100100, vector<graphdata>());

int main() {
    cin >> V >> E >> r;
    for(int i = 0; i < E; ++i) {
        int s;
        graphdata indata;
        cin >> s >> indata.to >> indata.dist;
        graph.at(s).push_back(indata);
    }

    priority_queue<pqdata> pque;
    pqdata first;
    first.no = r; first.d = 0;
    pque.push(first);
    vector<long long> ans(V, INF);
    ans.at(r) = 0;
    while(!pque.empty()) {
        pqdata now = pque.top();
        pque.pop();
        if(ans.at(now.no) < now.d) continue;
        for(int i = 0; i < graph.at(now.no).size(); ++i) {
            pqdata next;
            next.no = graph.at(now.no).at(i).to; next.d = now.d+graph.at(now.no).at(i).dist;
            if(ans.at(next.no) > next.d) {
                ans.at(next.no) = next.d;
                pque.push(next);
            }
        }
    }

    for(int i = 0; i < V; ++i) {
        if(ans.at(i) == INF) cout << "INF" << endl;
        else cout << ans.at(i) << endl;
    }
}


Measured memory_bytes: 19396
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctype.h>
#include <math.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    double a=0.0;
    a=(n+1.0)/(2.0*n);
    if(n%2==0){
        cout <<"0.5"<<endl;
    }
    else{
        cout <<a<<endl;
    }
}


Measured memory_bytes: 256
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main () {
    input! {
        s : chars,
        t : chars,
    }
    for i in 0..3 {
        if s[i] != t[2 - i] {
            println!("NO");
            return ;
        }
    }
    println!("YES");
}

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

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

int main(){
	ll n, k;
  cin >> n >> k;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  vector<ll> kk;
  rep(i, n){
    if(k == a[i]){
      cout << "POSSIBLE" << endl;
      return 0;
    }
    else if(k < a[i]){
      kk.push_back(a[i] - k);
    }
  }

  if(!kk.empty()){
    ll tmp = a[0];
    for(int i = 1; i < n; ++i){
      tmp = gcd(tmp, a[i]);
    }
    for(int i = 0; i < kk.size(); ++i){
      if(kk[i] % tmp == 0){
        cout << "POSSIBLE" << endl;
        return 0;
      }
    }
  }
  cout << "IMPOSSIBLE" << endl;
	return 0;
}



Measured memory_bytes: 1408
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2005;

int n;
int a[N];
struct edge{
	int x,nxt;
}e[N*N*2];
int h[N],tot;
int fa[N];
int ans[N];
int f[N][N];
bool bz[N];

int gcd(int x,int y){return y==0?x:gcd(y,x%y);}

void inse(int x,int y){
	e[++tot].x=y;
	e[tot].nxt=h[x];
	h[x]=tot;
}

void addedge(int x,int y){
	inse(x,y);
	inse(y,x);
}

int getfather(int x){return fa[x]==x?x:fa[x]=getfather(fa[x]);}

bool cmp(int x,int y){
	return a[x]<a[y];
}

int c[N];

void merge(int *x,int *y){
	int ha=1,hb=1;
	fo(i,1,x[0]+y[0]){
		if (hb>y[0]||(ha<=x[0]&&a[x[ha]]>a[y[hb]]))c[i]=x[ha++];
		else c[i]=y[hb++];
	}
	c[0]=x[0]+y[0];
	fo(i,1,c[0])x[i]=c[i];
	x[0]=c[0];
}

void dfs(int x){
	bz[x]=1;
	int k=0,t[N];
	for(int p=h[x];p;p=e[p].nxt)t[++k]=e[p].x;
	sort(t+1,t+1+k,cmp);
	f[x][0]=0;
	fo(i,1,k)
	if (!bz[t[i]]){
		dfs(t[i]);
		merge(f[x],f[t[i]]);
	}
	fd(i,f[x][0]+1,2)f[x][i]=f[x][i-1];
	f[x][0]++;
	f[x][1]=x;
}

int main(){
	n=get();
	fo(i,1,n)fa[i]=i;
	fo(i,1,n)a[i]=get();
	fo(i,1,n)
		fo(j,i+1,n)
		if (gcd(a[i],a[j])!=1){
			int x=getfather(i),y=getfather(j);
			fa[x]=y;
			addedge(i,j);
		}
	ans[0]=0;
	fo(i,1,n)
	if (getfather(i)==i){
		int w=0;
		fo(j,1,n)
		if (getfather(j)==i)
			if (!w||a[w]>a[j])w=j;
		dfs(w);
		merge(ans,f[w]);
	}
	fo(i,1,n-1)printf("%d ",a[ans[i]]);
	printf("%d\n",a[ans[n]]);
	return 0;
}

Measured memory_bytes: 52736
import itertools

n, m, q = map(int,input().split())

l = [list(map(int,input().split())) for i in range(q)]

a = list(itertools.combinations_with_replacement(range(1,m+1), n))

max_score = 0

for i in a:
    temp = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            temp += j[3]
        
    max_score = max(max_score, temp)

print(max_score)

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

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

typedef long long ll;

const char nl = '\n' ;


int main()
{
   ios_base::sync_with_stdio(0); cin.tie(0);
   long long ans = 0;
   int k, s; cin >> k >> s;
   for(int x = 0; x <= k; x++)
   {
      for(int y = 0; y <= k; y++)
      {
         if(s - x - y >= 0 && s - x - y <= k)
            ans++;
      }
   }
   cout <<ans << nl;
	return 0;
}


Measured memory_bytes: 3584
#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;
  cin >> n;

  vector<int> ret(n);

  for(int i=0; i<n; i++){
    int a;
    cin >> a;
    ret[a-1] = i+1;
  }

  for(int i=0; i<n; i++){
    cout << ret[i] << " ";
  }
  cout << endl;

  return 0;
}

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

int main()
{
    int n;
    cin>>n;
    
    int h[n],dp[n];
    for(int i=0;i<n;i++)
    {
        cin>>h[i];
    }
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for(int i=2;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<dp[n-1];


return 0;
}



Measured memory_bytes: 1024
import math
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0

for a in range(N - 2):
    b = a + 1
    c = a + 2
    while c < N and b < N - 1:
        if L[c] >= L[a] + L[b]:
            ans += c - 1 - b
            b += 1
            if b == c:
                c += 1
        else:
            if c == N - 1:
                ans += (c - b) * (c - b + 1) // 2 
                break
            else:
                c += 1
        
print(ans)        

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

string S;
deque<char> s;
int Q, t, flip, F;
char C;

int main(){
    cin >> S >> Q;
    for(int i=0; i<S.size(); i++){
        s.push_back(S[i]);
    }
    for(int i=0; i<Q;i++){
        cin >> t;
        if(t==1){
            if (flip == 0){
                flip = 1;
            } else{
                flip = 0;
            }
        } else{
            cin >> F >> C;
            if(F == 1){
                if (flip == 0){
                    s.push_front(C);
                } else{
                    s.push_back(C);
                }
                
            } else{
                if (flip == 0){
                    s.push_back(C);
                } else{
                    s.push_front(C);
                }
                
            }

        }
    }
    if (flip == 0){
        for(int i=0; i<s.size(); i++){
        cout << s[i];
        }
    } else{
        for(int i=s.size()-1; i>=0; i--){
            cout << s[i];
        }
    }
    
    
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
#define pi acos(-1)
#define P pair<int,int>
#define fi first
#define se second
#define si signed
#define sc(x) scanf("%lld",&(x));
int n;
int A[]={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};
signed main()
{
    sc(n)
    cout<<A[n-1]<<'\n';
}


Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<double> d(n);
  rep(i,n) cin >> d[i];
  sort(d.begin(),d.end());
  double ans = d[0];
  for(int i=1;i<n;i++){
    ans = (ans+d[i])/2;
  }
  printf("%.10f\n",ans);
}

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

using namespace std;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")

#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"

#define sz(a) ((int)(a).size())
#define all(v) (v).begin(), (v).end()
#define tr(c, it) for (auto(it) = (c).begin(); (it) != (c).end(); it++)
#define pres(c, val) ((c).find(val) != (c).end())      //
#define cpres(c, val) (find(all(c), val) != (c).end()) //

#define pb push_back
#define mp make_pair
#define F first
#define S second

#define forf(i, a, b) for (int i = (a); i < (b); i++)
#define forb(i, a, b) for (int i = (b); i >= (a); i--)
#define fo(i, n) forf(i, 0, n)
#define fob(i, n) forb(i, 0, n - 1)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;

const int INF = 9e18;
// const int N = 1e9 + 7;
const int N = 998244353;

const auto start_time = std::chrono::high_resolution_clock::now();

void zark() {
  #ifdef ZARK
  auto end_time = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double> diff = end_time - start_time;
  cerr << "Time Taken : " << diff.count() << "s\n";
  #endif
}

#ifdef ZARK
#include "/home/aranjan/Desktop/CP/header.h"
#else
#define dbg(args...)
#endif

/* ------------------ Actual Coding Starts ------------------ */

void solve() {
  int x;
  cin >> x;
  int cnt = 0;
  int a = 100;
  while(a < x) a = (int)(1.01*a), cnt++;
  cout << cnt << endl;
}

int32_t main() {
  fastio;
  #ifdef ZARK
  freopen("input.in", "r", stdin);
  #endif

  // freopen("txt.in", "r", stdin);
  // freopen("txt.out", "w", stdout);
  // cout << fixed << setprecision(35);

  solve();
  zark();
  return 0;
}


Measured memory_bytes: 3700
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
#define SortAsc(c) std::sort(c.begin(), c.end())
#define SortDesc(c) std::sort(c.rbegin(), c.rend())
int dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int dy[8] = {1, 0, -1, 0, 1, -1, 1, -1};

int main()
{
    int n;
    cin >> n;
    vector<double> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    SortAsc(v);

    double res = v[0];
    for (int i = 1; i < n; i++)
    {
        res = (res + v[i]) / 2;
    }

    cout << std::fixed << std::setprecision(10) << res << endl;
}

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

using i64=int64_t;

#define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)
 
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif
 
const int inf=1.01e9;
const i64 inf64=4.01e18;
const double eps=1e-9;
 
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

i64 f(i64 b,i64 n){
    if(n<b) return n;
    return n%b+f(b,n/b);
}

void solve(){
    i64 n,s;
    cin >> n >> s;

    i64 x=1000000;

    if(n<x){
        rep(b,2,n+2){
            if(f(b,n)==s){
                cout << b << endl;
                return;
            }
        }
        cout << -1 << endl;
        return;
    }

    rep(b,2,x){
        if(f(b,n)==s){
            cout << b << endl;
            return;
        }
    }

    i64 k=n-s;
    set<i64> bs;
    if(k==0) bs.insert(n+1);
    for(i64 i=1; i*i<=k; ++i){
        if(k%i!=0) continue;
        if(i+1>=x) bs.insert(i+1);
        if(k/i+1>=x) bs.insert(k/i+1);
    }

    for(i64 b:bs){
        if(n%b+n/b==s){
            cout << b << endl;
            return;
        }
    }

    cout << -1 << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 384
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var nx = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            var list = new List<int>();
            for(int i = 0; i<nx[0];i++)
            {
                list.Add(int.Parse(Console.ReadLine()));
            }
            int ans = list.Count();
            nx[1] -= list.Sum();
            while(nx[1] >= list.Min())
            {
                nx[1] -= list.Min();
                ans++;
            }
            Console.WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13392