akhauriyash/Code-Regression huggingface dataset:
/**
       ������������    ������������
		Author : Avi J Patel
		University : DA-IICT
       ������������    ������������
**/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair 
#define mt make_tuple
#define N 100000
#define ff first
#define ss second
#define si size()
#define MOD 1000000007
#define large 10000000000000001

#define For(i,m,n) for(long long i=m;i<n;i++)
#define st(x) sort(x.begin(),x.end())
#define re(x,i) reverse(x.begin()+i,x.end())
#define FAST ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));

bool sortbysec(const pair<int,int> &a, 
              const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
} 
int main()
{
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	cout<<a[n/2]-a[n/2-1];
	return 0;
}








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

int main() {
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
  cin>>a[i];
}
sort(a,a+n);
int diff=a[n/2]-a[n/2 -1];
cout<<diff<<endl;
}

Measured memory_bytes: 640
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 invmod(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
    
def left_bin(a, n, c):
    ns = [int(i) for i in bin(n)[3:]]
    t = a
    for i in ns:
        t = t*t % c
        if i == 1:
            t = t*a % c
    return t

n, a, b = map(int, input().split())
c = 10**9 + 7

ans = left_bin(2, n, c) - 1 
temp = n
if a == 1:
    ans = (ans - n) % c
for i in range(1, b):
    temp = temp*(n-i) % c
    temp = temp*invmod(i+1, c) % c
    if i+1 == a:
        ans = (ans - temp) % c
ans = (ans - temp) % c
print(ans)


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

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

ll func[100001];
ll mod = 1000000007;

void setfunc(int i ) {
    func[0] = func[1] = 1;
    for(int j = 1; j<=i; ++j) {
        func[j+1] = func[j] * (j+1) % mod;
    }
}

int main(void) {
    int n, m;
    cin >> n >> m;
    setfunc(max(n,m));
    if(abs(n-m)>1) {
        cout << 0 << endl;
        return 0;
    }

    if( (n + m) % 2 == 0 )
        cout << func[n] * func[m]  * 2  % mod << endl;
    else
        cout << func[n] * func[m]   % mod << endl;

    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)
{
   int i, j, n;

   scanf("%d",&n);

   for(i=1;i<=9;i++) {
      for(j=1;j<=9;j++) {
         if(n==i*j) {
            printf("Yes\n");
            return 0;
         }
      }
   }

   printf("No\n");
   return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int MAX_N = 100005;
int N;
string s;
char ans[MAX_N];

bool f()
{
	for (int i = 1; i < N-2; ++i)
	{
		if(s[i] == 'o' && ans[i] == 'S' && ans[i-1] == 'S') ans[i+1] = 'S';
		else if(s[i] == 'o' && ans[i] == 'S' && ans[i-1] == 'W') ans[i+1] = 'W';
		else if(s[i] == 'o' && ans[i] == 'W' && ans[i-1] == 'S') ans[i+1] = 'W';
		else if(s[i] == 'o' && ans[i] == 'W' && ans[i-1] == 'W') ans[i+1] = 'S';
		else if(s[i] == 'x' && ans[i] == 'S' && ans[i-1] == 'S') ans[i+1] = 'W';
		else if(s[i] == 'x' && ans[i] == 'S' && ans[i-1] == 'W') ans[i+1] = 'S';
		else if(s[i] == 'x' && ans[i] == 'W' && ans[i-1] == 'S') ans[i+1] = 'S';
		else if(s[i] == 'x' && ans[i] == 'W' && ans[i-1] == 'W') ans[i+1] = 'W';
	}
	/*
	rep(i,N)
	{
		cout << ans[i];
	}
	cout << endl;
	*/
	if ((ans[N-1] == 'S' && s[N-1] == 'o' && ans[0] == ans[N-2]) || (ans[N-1] == 'S' && s[N-1] == 'x' && ans[0] != ans[N-2]) || (ans[N-1] == 'W' && s[N-1] == 'o' && ans[0] != ans[N-2]) || (ans[N-1] == 'W' && s[N-1] == 'x' && ans[0] == ans[N-2]))
	{
		if ((ans[N-2] == 'S' && s[N-2] == 'o' && ans[N-1] == ans[N-3]) || (ans[N-2] == 'S' && s[N-2] == 'x' && ans[N-1] != ans[N-3]) || (ans[N-2] == 'W' && s[N-2] == 'o' && ans[N-1] != ans[N-3]) || (ans[N-2] == 'W' && s[N-2] == 'x' && ans[N-1] == ans[N-3]))
		{
			rep(i,N)
			{
				cout << ans[i];
			}
			cout << endl;
			return true;
		}
	}
	return false;
}

int main()
{
	cin >> N;
	cin >> s;
	ans[0] = 'S';
	if (s[0] == 'o')
	{
		ans[1] = 'S'; ans[N-1] = 'S';
		if (f()) return 0;
		ans[1] = 'W'; ans[N-1] = 'W';
		if (f()) return 0;
	}
	else
	{
		ans[1] = 'S'; ans[N-1] = 'W';
		if (f()) return 0;
		ans[1] = 'W'; ans[N-1] = 'S';
		if (f()) return 0;
	}
	ans[0] = 'W';
	if (s[0] == 'o')
	{
		ans[1] = 'S'; ans[N-1] = 'W';
		if (f()) return 0;
		ans[1] = 'W'; ans[N-1] = 'S';
		if (f()) return 0;
	}
	else
	{
		ans[1] = 'S'; ans[N-1] = 'S';
		if (f()) return 0;
		ans[1] = 'W'; ans[N-1] = 'W';
		if (f()) return 0;
	}
	cout << "-1" << endl;
	return 0;
}

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

int main() {
    string S;
    cin >> S;

    string a = "abcdefghijklmnopqrstuvwxyz";
    char alphabet[26];
    for (int i = 0; i < 26; i++) {
        alphabet[i] = a.at(i);
    }

    int num[26] = {0};
    for (int i = 0; i < S.size(); i++) {
        for (int j = 0; j < 26; j++) {
            if (S.at(i) == alphabet[j]) {
                num[j]++;
            } 
        }
    }

    bool flag = true;
    for (int i = 0; i < 26; i++) {
        if (num[i] == 0) {
            cout << alphabet[i] << endl;
            flag = false;
            break;
        }
    }

    if (flag) {
        cout << "None" << endl;
    }
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    vvi a(n,vi(n));
    cin >> a;
    ll ans = 0;
    rep(i,n) rep2(j,i+1,n) {
        bool flag = true;
        rep(k,n) {
            if(i == k or j == k) continue;
            if(a[i][k]+a[k][j] == a[i][j]) flag = false;
            else if(a[i][k]+a[k][j] < a[i][j]) {
                cout << -1 << endl;
                return 0;
            }
        }
        if(flag) ans += a[i][j];
    }
    cout << ans << endl;
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define fst first
#define snd second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

const string YES = "";
const string NO  = "";

typedef long long ll;

void solve() {

}

int main() {
  int x;
  cin >> x;
  ll ans = 0;
  ll cnt = x / 500;
  ans += ( cnt * 1000LL );
  x -= ( cnt * 500 );
  while( x > 5 ) {
    if( x >= 5 ) {
      x -= 5;
      ans += 5;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <vector>
#define INF 0x3FFFFFFF

using namespace std;

typedef struct eda{
	int x;
	int y;
	int z;
}edge;

int main(void){
	int n, m, p, a, b, t[8], i, j, k, l;
	double d[30][1 << 8], ans;
	vector<edge> e;
	edge one;
	while(1){
		scanf("%d%d%d%d%d",&n,&m,&p,&a,&b);
		if(n == 0 && m == 0 && p == 0 && a == 0 && b == 0) break;
		a--, b--;
		for(i = 0;i < n;i++)
			scanf("%d",&t[i]);
		for(i = 0;i < p;i++){
			e.push_back(one);
			scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
			e[i].x--,e[i].y--;
		}
		for(i = 0;i < p;i++){
			e.push_back(one);
			e[i + p].x = e[i].y, e[i + p].y = e[i].x, e[i + p].z = e[i].z;
		}
		for(i = 0;i < m;i++)
			for(j = 0;j < (1 << n);j++) d[i][j] = (double) INF;

		d[a][(1 << n) - 1] = 0.0;
		for(i = 0;i < m;i++){ // max arith 30
			for(j = 0;j < p * 2;j++){ // max arith 100
				for(k = 0;k < (1 << n);k++){ // max arith 256
					for(l = 0;l < n;l++){ // max arith 8
						if(k & (1 << l) && d[e[j].y][k - (1 << l)] > d[e[j].x][k] + (double) e[j].z / t[l])
							d[e[j].y][k - (1 << l)] = d[e[j].x][k] + (double) e[j].z / t[l];

					}
				}
			}
		}
		ans = (double)INF;
		for(i = 0;i < (1 << n);i++)
			if(ans > d[b][i]) ans = d[b][i];
		if(ans != (double)INF)
			printf("%.3f\n",ans);
		else
			printf("Impossible\n");
		while(!e.empty()) e.pop_back();
	}
	return 0;
}

Measured memory_bytes: 1172
import java.util.*;
import java.math.*;
public class Main {
    static final int MOD = 1_000_000_007; // 10^9+7
    //static final int MAX = 2_147_483_646; // intの最大値
    static final int INF = 1_000_000_000; // 10^9
    static final int MAX = 10_000_000;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ary = new int[n];
        int[] count = new int[n+1];
        for(int i = 0;i < n;i++){
            ary[i] = sc.nextInt();
            count[ary[i]]++;
        }
        long ans = 0;
        for(int i = 0;i < n+1;i++){
            long tmp = count[i];
            tmp *= count[i]-1;
            tmp /=2;
            ans+= tmp;
        }
        for(int i = 0;i < n;i++){
            System.out.println(ans-count[ary[i]]+1);
        }

    }       
}






Measured memory_bytes: 94660
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		double r = scan.nextDouble();		
		double x = Math.PI;
		double l = 2 * r * x;
		double c = r * r * x;
		String g = String.format("%.6f", l);
		String h = String.format("%.6f", c);
		System.out.println(h+" "+g);
	}
}

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

int main(){
  int i;
	int n, q;
  string s;
  cin >> n >> q >> s;
  vector<int> l(q), r(q);
  
  rep(i, q) cin >> l[i] >> r[i];
  
  int ans[100005] = {0};
  
  rep(i, n-1){
    ans[i+1] = ans[i];
    if(s[i] == 'A' && s[i+1] == 'C'){
      ans[i+1] = ans[i] + 1;
    }
  }
  
  rep(i, q){
    cout << ans[r[i] - 1] - ans[l[i] - 1] << endl;
  }
}

Measured memory_bytes: 2176
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

template<typename T>
vector<T> gen_v(size_t a) { return vector<T>(a); }
template<typename T, typename ...Ts>
auto gen_v(size_t a, Ts... ts) { return vector<decltype(gen_v<T>(ts...))>(a, gen_v<T>(ts...)); }
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); }

int agc029a(string s) {
	int ans = 0;
	int k = 0;
	rep(i, 0, s.size()) {
		if (s[i] == 'B')break;
		k++;
	}
	rep(i, k, s.size()) {
		if (s[i] == 'W') {
			ans += i - k;
			k++;
		}
	}
	dump(s, ans);
	return ans;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s; cin >> s;
	string t = "";
	int ans = 0;
	rep(i, 0, s.size()) {
		if (i + 1 < s.size() && s[i] == 'B' && s[i + 1] == 'C') {
			t += 'W';
			i++;
		}
		else if (s[i] == 'A') {
			t += 'B';
		}
		else {
			ans += agc029a(t);
			t = "";
		}
	}
	ans += agc029a(t);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 916
#include <iostream>
#include <algorithm>

using namespace std;
using ll = long long;

void solve(ll N, ll A, ll B) {
  cout << min(N*A,B) << endl;
}

int main() {
  ll N;
  cin >> N;
  ll A;
  cin >> A;
  ll B;
  cin >> B;
  solve(N, A, B);
  return 0;
}


Measured memory_bytes: 256
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

n = I()
shogens = []

for i in range(n):
    a = I()
    shogens.append([])
    for j in range(a):
        x,y = LI()
        x -= 1
        shogens[-1].append((x,y))

def is_honest(i,j):
    return (i >> j) % 2 == 1

def honest_cnt(i):
    ans = 0
    for j in range(n):
        ans += is_honest(i,j)
    return ans 

ans = 0
for i in range(1 << n):
    ok = True
    for j in range(n):
        if not is_honest(i,j):continue
        for (x,y) in shogens[j]:
            if y == 0 and is_honest(i,x):ok = False
            if y == 1 and not is_honest(i,x):ok = False
    if ok:
        ans = max(ans, honest_cnt(i))
print(ans)

Measured memory_bytes: 9100
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

template<typename T> void chmax(T &a, T b) { a = std::max(a, b); }
template<typename T> void chmin(T &a, T b) { a = std::min(a, b); }
template<typename T> void chadd(T &a, T b) { a = a + b; }

namespace {  // 名前なし名前空間
	// gcd, lcm は C++17 でstdに標準入りしたので言語のバージョンに注意
	// 最大公約数
	ll gcd(ll a, ll b) {
		if (b == 0) return a;
		return gcd(b, a % b);
	}

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

int main() {

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

	int ans = 0;
	int tmp = 0;
	rep(i, n - 1) {
		if (h[i] >= h[i + 1]) {
			tmp++;
		}
		else {
			ans = max(ans, tmp);
			tmp = 0;
		}
	}

	ans = max(ans, tmp);

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

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

	if (N * A < B) {
		cout << N * A << endl;
	}
	else if (N * A > B) {
		cout << B << endl;
	}
	else if (N * A == B) {
		cout << B << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
using Graph=vector<vector<int>>;
using edge= struct{int to;ll cost;};


template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
  string s;cin>>s;
  if(s=="Sunny"){
    cout<<"Cloudy"<<endl;
  }
  else if(s=="Cloudy"){
    cout<<"Rainy"<<endl;
  }
  else{
    cout<<"Sunny"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
typedef long long ll;
namespace mp = boost::multiprecision;
using Mint = mp::cpp_int;
#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(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
#define sort_g(v) sort(all(v), greater<int>())
#define dump(x) cerr << #x << ' ' << '=' << ' ' << x << endl

int main() {
    int N, K;
    cin >> N >> K;
    cout << (N >= 2 * K - 1 ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
n,m = gets.split(" ").map{|v|
	v.to_i
}

$nbr = []
for i in 0..n-1
	$nbr[i] = []
end

#接続関係を配列に直す
m.times do
	a,b = gets.split(" ").map{|v|
		v.to_i
	}
	$nbr[a-1] << b-1
	$nbr[b-1] << a-1
end

def CountPath(cur, prevs, n)	
	if prevs.length == n-1
		return 1
	end

	sum = 0
	for v in $nbr[cur]
#		if v is not in prevs
		if !(prevs.include?(v))
			prevs << cur
			sum = sum + CountPath(v, prevs, n)
			prevs.delete_at(-1)

		end
	end
	
	return sum
end

if $nbr[0].length == 0
	# 頂点1からの辺がない
	puts 0
	exit
end

puts CountPath(0, [], n)


Measured memory_bytes: 1788
#include<stdio.h>
#define MAX 1000

typedef struct{
  int p;
  int l;
  int r;
}Binary;

Binary tree[MAX];

int main(){
  int i,n,k;
  int id;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    tree[i].l=tree[i].r=tree[i].p=-1;
  }
  for(i=0;i<n;i++){
    scanf("%d",&id);
    scanf("%d%d",&tree[id].l,&tree[id].r);
    if(tree[id].l!=-1)
      tree[tree[id].l].p=id;
    if(tree[id].r!=-1)
      tree[tree[id].r].p=id;
  }

  for(i=0;i<n;i++){
    print(i);
  }
  return 0;
}


void print(int);

int getheight(int i){
  int x=0,y=0;
  if(tree[i].l!=-1)
    x=getheight(tree[i].l)+1;
  if(tree[i].r!=-1)
    y=getheight(tree[i].r)+1;
  if(x>y)
    return x;
  else
    return y;
}

int getdepth(int i){
  int d=0;
  while(tree[i].p>=0){
    i=tree[i].p;
    d++;
  }
  return d;
}

int getsibling(int i){
  if(tree[i].p==-1)
    return -1;
  else if(tree[tree[i].p].r==i)
    return tree[tree[i].p].l;
  else
    return tree[tree[i].p].r;
}

int getdeg(int i){
  int d=0;
  if(tree[i].l!=-1)
    d++;
  if(tree[i].r!=-1)
    d++;
  return d;
}


void print(int i){
    int h=getheight(i);
    int dep=getdepth(i);

    printf("node %d: parent = %d, sibling = %d, degree = %d, ",i,tree[i].p,getsibling(i\
),getdeg(i));

    printf("depth = %d, height = %d, ",dep,h);
    if(dep==0)
      printf("root\n");
    else if(h==0)
      printf("leaf\n");
    else
      printf("internal node\n");
}

Measured memory_bytes: 612
#include "bits/stdc++.h"
using namespace std;
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2438&lang=jp
typedef long long ll;
#define INF 1<<30
#define LINF 1LL<<60
string YAML[50010];

vector<string> split(const string &s, char delim) {
	vector<string> elems;
	stringstream ss(s);
	string item;
	while (getline(ss, item, delim)) {
		if (!item.empty()) {
			elems.push_back(item);
		}
	}
	return elems;
}

int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	string k; cin >> k;
	auto key = split(k, '.');
	int key_cnt = key.size();
	cin.ignore();
	int cnt = 0;
	while (getline(cin, YAML[cnt++]));
	cnt--;
	int pre_space = 0;
	int key_at = 0;
	bool next_flag = false;
	bool through = false;
	for (int i = 0; i < cnt;i++) {
		auto yaml = split(YAML[i], ':');
		int space;
		for (int l = 0; l < yaml[0].length(); l++) if (yaml[0][l] != ' ') { space = l; break; }
		if (!through & space < pre_space)break;
		if (through & (space != pre_space)) continue;
		else through = false;

		if (next_flag) { pre_space = space; next_flag = false; }
		if (yaml[0].substr(space) == key[key_at]) {
			key_at++;
			if (key_at == key_cnt) {
				if (yaml.size() == 2) {
					yaml[1][0] = '"';
					cout << "string " << yaml[1] << '"' << endl; return 0;
				}
				else {
					cout << "object" << endl; return 0;
				}
			}
			else {
				if (yaml.size() == 2)break;
				else {
					next_flag = true;
					continue;
				}
			}
		}
		else {
			if (yaml.size() == 1)through = true;
			else continue;
		}
	}
	cout << "no such property" << endl;
	return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    string S;
    cin >> N >> S;
    if (S.size() % 2 == 1)
    {
        cout << "No" << endl;
    }
    else if (S.substr(0, N / 2) == S.substr(N / 2, N / 2))
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
import static java.lang.Math.*;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????
        int n,i,j,v;
        Scanner scan=new Scanner(System.in);
        n=scan.nextInt();
        int m[]=new int[n];
        int k[]=new int[n];
        for(i=0;i<m.length;i++)
        {
        	m[i]=scan.nextInt();
        }
        
        for(i=0;i<m.length-1;i++)
        {
        	System.out.print(m[i]+" ");
        }
        System.out.println(m[n-1]);
        for(i=1;i<=m.length-1;i++)
        {
        	v=m[i];
        	j=i-1;
        	while(j>=0&&m[j]>v)
        	{
        		m[j+1]=m[j];
        		j--;
        	}
        	m[j+1]=v;
        	for(j=0;j<m.length-1;j++)
        	{
        		System.out.print(m[j]+" ");
        	}
        	System.out.println(m[n-1]);
        }
	}
}

Measured memory_bytes: 24300
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; } value
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b, c;
  cin >> a >> b >> c;
  bool ans = false;
  if(a == b && b == c) ans = true;
  YesorNo(ans);
}

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

int main() {
  int N;
  int P,W,G,Y = 0;
  cin >> N;
  for (int i=0;i<N;i++){
    string S;
    cin >> S;
    if(S == "P"){
      if(P == 0){
        P++;
      }
    }else if(S == "W"){
      if(W == 0){
        W++;
      }
    }else if(S == "G"){
      if(G == 0){
        G++;
      }
    }else if(S == "Y"){
      if(Y == 0){
        Y++;
      }
    }
  }
  int num = P+W+G+Y;
  if(num == 4){
    cout << "Four" << endl;
  }else{
    cout << "Three" << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int INF = 1<<30;
const int maxn = 1e5+5;
struct node
{
    ll v;
    int flag;
    bool operator < (const node &e) const
    {
        if(v==e.v) return flag<e.flag;
        else return v>e.v;
    }
}apple[maxn*3];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll x,y,a,b,c;
    int cnt = 0;
    cin>>x>>y>>a>>b>>c;
    for(int i=0;i<a;i++) {cin>>apple[cnt].v;apple[cnt++].flag=1;}
    for(int i=0;i<b;i++) {cin>>apple[cnt].v;apple[cnt++].flag=2;}
    for(int i=0;i<c;i++) {cin>>apple[cnt].v;apple[cnt++].flag=3;}
    sort(apple,apple+cnt);
    int c1=0,c2=0,c3=0;
    ll ans = 0;
    for(int i=0;i<cnt;i++)
    {
        if(c1+c2+c3==x+y) break;
        int f = apple[i].flag;
        if(f==1)
        {
            if(c1<x) ans+=apple[i].v,c1++;
        }
        else if(f==2)
        {
            if(c2<y) ans+=apple[i].v,c2++;
        }
        else ans+=apple[i].v,c3++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a:A) cin >> a;} 

VI color;
void dfs(const VVI &G, int v, int c) {
    color[v] = c;
    if (c > 0) c = 1;
    for (auto nv : G[v]) {
        if (color[nv] != -1) continue; 
        dfs(G, nv, ++c);
    }
}

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

int N, K; cin >> N >> K;
VVI G(N+1);
rep(i, 0, N-1){
    int a, b; cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
}

color.assign(N+1, -1);
dfs(G, 1, 0);

i64 ans = 1;
rep(v, 1, N+1){
    (ans *= max((i64)0, K - color[v])) %= MOD;
}
cout << ans << "\n";

return 0;
}
// コンテスト前はtemplate振り返り。
// 書いて考える．場合分け．情報整理．
// 問題文から考える。自分ができることから考える。
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP(小さい問題から大きな問題)
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性→二分探索。逆から考える。
// 存在判定：構成方法，入力の特徴
// 構築問題。極端解を試す。
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// コーナーケース。境界値。数表出力プログラム作る
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 9984
from math import floor

def gcd(a,b):
    while b:
        a, b = b , a%b
    return a

def lcm(a, b):
    return abs(a*b) // gcd(a, b)

A, B, C, D = map(int, input().split())

def n(n):
    c = n // C
    d = n // D
    cd = n // lcm(C,D)
    return n - c - d + cd

print(n(B)-n(A-1))



Measured memory_bytes: 3060
S = input()
T = input()

s_read_chars = []
t_read_chars = []

encoded_S = ""
encoded_T = ""

for s, t in zip(S, T):
    if s not in s_read_chars:
        i = len(s_read_chars)
        s_read_chars.append(s)
    else:
        i = s_read_chars.index(s)
    encoded_S += str(i)
        
    if t not in t_read_chars:
        j = len(t_read_chars)
        t_read_chars.append(t)
    else:
        j = t_read_chars.index(t)
    encoded_T += str(j)

if encoded_S == encoded_T:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 4272
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
int main() {
	string s;
	cin>>s;
	int ans=0;
	rep(i,3)if(s[i]=='1')ans++;
	cout<<ans<<endl;
}

Measured memory_bytes: 256
import sys
for e in sys.stdin:
 a=float(e)
 t=[a,
 a*2,
 a*2/3,
 a*2/3*2,
 a*2/3*2/3,
 a*2/3*2/3*2,
 a*2/3*2/3*2/3,
 a*2/3*2/3*2/3*2,
 a*2/3*2/3*2/3*2/3,
 a*2/3*2/3*2/3*2/3*2]
 print(sum(t))


Measured memory_bytes: 5584
A,B,K=map(int,input().split())
if B-A>200:
    k=range(A,A+K)
    l=range(B-K+1,B+1)
    for i in k:
        print(i)
    for i in l:
        print(i)
else:
    s=range(A,B+1)
    t=[x for x in s if A<=x<=A+K-1 or B-K+1<=x<=B]
    t.sort()
    for i in t:
        print(i)


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

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

Measured memory_bytes: 256
nd=input().split()
n=int(nd[0])
d=int(nd[1])
count=0
z=d*d
for i in range(0,n):
	xy=input().split()
	x=int(xy[0])
	y=int(xy[1])
	if(x*x+y*y<=z):
		count+=1
print(count)


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

#define ll long long
#define ld long double
#define ii pair<int ,int >
#define S second
#define F first
#define PI 3.1415926535897932384626
#define SPEED std::ios_base::sync_with_stdio(false);



int main(){
    SPEED
    int n;
    cin>>n;
    vector<int>v(n);
    for(int & x : v){
        cin>>x;
    }
    int ans=1e9;
    sort(v.begin(),v.end());
    for(int i=v[0];i<=v[n-1];i++){
        int tmp=0;
        for(int j=0;j<n;j++){
            tmp+=(v[j]-i)*(v[j]-i);
        }
        ans=min(ans,tmp);
    }
    cout<<ans;

}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>

using namespace std;

long long a[100100];
int N;
long long L;

void input(){
	scanf("%d", &N);
	scanf("%lld", &L);
	for(int i = 0; i < N; ++i){
		scanf("%lld", a + i);
	}
}

int get(){
	long long ma = 0;
	int id = 0;
	for(int i = 0; i < N - 1; ++i){
		long long tmp = a[i] + a[i + 1];
		if(ma < tmp){
			ma = tmp;
			id = i;
		}
	}
	if(ma < L){
		printf("Impossible\n");
		exit(0);
	}
	return id;
}

int main(){
	input();
	int la = get();
	printf("Possible\n");
	for(int i = 0; i < la; ++i){
		printf("%d\n", i + 1);
	}
	for(int i = N - 2; i > la; --i){
		printf("%d\n", i + 1);
	}
	printf("%d\n", la + 1);
	return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

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

    int ans = 0;
    if(A >= K)ans = K;
    else if(A + B >= K)ans = A;
    else{
        int tmp = K - A - B;
        ans = A - tmp;
    }

    cout << ans << endl;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[1005],i,cnt1=0,cnt2=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=0;i<n;i++)
    {
        if(a[i]%2==0)
        {
            cnt1++;
            if(a[i]%3==0 || a[i]%5==0) cnt2++;
        }
    }
    if(cnt1==cnt2) cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;

    return 0;
}


Measured memory_bytes: 256
N  = int(input())
a = []
b = []
c = [] 
for i in range(N):
    aa, bb, cc = [int(i) for i in input().split()] 
    a.append(aa)
    b.append(bb)
    c.append(cc)

# cost[i][1], cost[i][2], cost[i][3]
cost = [[0 for i in range(3)] for j in range(N)]

cost[0][0] = a[0]
cost[0][1] = b[0]
cost[0][2] = c[0]

for i in range(1, N):
    cost[i][0] = max(cost[i-1][1] + a[i], cost[i-1][2] + a[i])
    cost[i][1] = max(cost[i-1][0] + b[i], cost[i-1][2] + b[i])
    cost[i][2] = max(cost[i-1][0] + c[i], cost[i-1][1] + c[i])

print(max(cost[N-1][0], cost[N-1][1],cost[N-1][2]))


Measured memory_bytes: 81112
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;
 
int gcd(int x,int y){
    if(y==0)return x;

    return gcd(y,x%y);
}
int lcm(int x,int y){
    return x*y/gcd(x,y);
}

int main(){

    int N,p[30]={},ans=0;
    cin>>N;
    for(int i=1;i<=N;i++){
        cin>>p[i];
    }

    for(int i=2;i<=(N-1);i++){
        if(p[i]<max(p[i-1],p[i+1])
            &&p[i]>min(p[i-1],p[i+1]))ans++;
    }

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

Measured memory_bytes: 256
k = int(input())
if k <= 12:
    print(k)
    exit()

dp = [[0]*10 for i in range(20)]
for i in range(10):
    dp[0][i] = 1
ans = 9
for i in range(1,18):
    for j in range(1,10):
        if j == 9:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-1]+dp[i-1][j+1]
    ans += sum(dp[i])
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    if ans >= k:
        
        s = ""
        for m in range(i,-1,-1):
            if m == i:
                for j in range(9,0,-1):
                    if ans-dp[m][j] >= k:
                        ans -= dp[m][j]
                    else:
                        s += str(j)
                        nex = j
                        
                        break
            else:
                if nex == 9:
                    for j in range(9,7,-1):
                        if ans-dp[m][j] >= k:
                            ans -= dp[m][j]
                        else:
                            s += str(j)
                            nex = j
                            
                            break
                else:
                    for j in range(nex+1,nex-2,-1):
                        if ans-dp[m][j] >= k:
                            ans -= dp[m][j]
                        else:
                            s += str(j)
                            nex = j
                            
                            break



        print(s)
        
        exit()


    


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

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

  cout << N * 800 - (N / 15 * 200) << endl;
}

Measured memory_bytes: 3572
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable : 4996)
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include<time.h>
#include<random>
#include<array>


using namespace std;

#define REP(i, n) for(int i = 0;i < n;++i)
#define REPR(i, n) for(int i = n-1;i >= 0;--i)
#define FOR(i, m, n) for(int i = m;i < n;++i)
#define FORR(i, m, n) for(int i = m-1;i >= n;--i)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end())
#define ll long long
#define print(x) cout<<(x)<<'\n'
#define pe(x) cout<<(x)<<" "
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define lb(v,n) lower_bound(v.begin(), v.end(), (n))
#define ub(v,n) upper_bound(v.begin(), v.end(), (n))
#define int long long
//#define double long double
#define all(x) (x).begin(), (x).end()
#define print_space(v) REP(i,v.size())cout << v[i] << ((i == v.size() - 1) ? "\n" : " ")
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
typedef pair<int, int>P;
typedef array<int, 3> arr3;
std::random_device rd;
std::mt19937 mt(rd());
constexpr ll MOD = 998244353; constexpr int MAX = 2000020;
const double pi = acos(-1); constexpr double EPS = 1e-8;
constexpr ll INF = 1e18;


void solve() {
	int X, Y, A, B, C; cin >> X >> Y >> A >> B >> C;
	vector<int>p(A), q(B), r(C);
	REP(i, A)cin >> p[i];
	REP(i, B)cin >> q[i];
	REP(i, C)cin >> r[i];
	VSORT(p); VREVERSE(p);
	VSORT(q); VREVERSE(q);
	VSORT(r); VREVERSE(r);
	priority_queue<int, vector<int>,greater<int>>que;
	REP(i, X)que.push(p[i]);
	REP(i, Y)que.push(q[i]);
	priority_queue<int>rem;
	REP(i, C)rem.push(r[i]);
	int ans = 0;
	while (!que.empty()) {
		if (rem.empty()) {
			ans += que.top();
			que.pop();
		}
		else if (que.top() < rem.top()) {
			ans += rem.top();
			que.pop();
			rem.pop();
		}
		else {
			ans += que.top();
			que.pop();
		}
	}
	print(ans);
}



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	//int q; cin >> q;
	//while (q--)
	solve();
}



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

from heapq import *
q = []
for _ in range(N):
    heappush(q, tuple(int(x) for x in input().split()))

acc = 0
while q:
    a, b = heappop(q)
    acc += b
    if acc >= K:
        print(a)
        break

Measured memory_bytes: 16668
#include <iostream>

using namespace std;

struct Vector
{
	double x;
	double y;
};

istream& operator>>(istream& stream, Vector& p)
{
	return stream >> p.x >> p.y;
}

double slope(Vector p1, Vector p2)
{
	return (p2.y - p1.y) / (p2.x - p1.x);
}

int main()
{
	int length;
	cin >> length;

	while(length-- > 0)
	{
		Vector a, b, c, d;
		cin >> a >> b >> c >> d;

		if( slope(a, b) == slope(c, d) )
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

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

#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(), (v).end() 
#define sz(v) (int)((v).size())
#define fs first
#define sd second

typedef long long ll;

typedef pair < int, int > pi;
typedef pair < pi, int > ppi;

typedef vector < int > vi;
typedef vector < vector < int > > vvi;
typedef vector < pi > vpi;
typedef vector < vpi > vvpi;
typedef vector < ppi > vppi;

void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}

void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}

#ifdef LOCAL
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

double get_time() {
	return 1.0 * clock() / CLOCKS_PER_SEC;
}

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0; i < n; i++)
		cin >> a[i];
	vector<long long> dp(n);
	dp[0] = 1000;
	for(int i = 1; i < n; i++) {
		dp[i] = dp[i - 1];
		for(int j = i - 1; j >= 0; j--) {
			dp[i] = max(dp[i], dp[j] + (a[i] - a[j])  * (dp[j] / a[j]));
		}
	}
	cout << dp[n - 1] << '\n';
}


Measured memory_bytes: 3632
n,l = map(int,input().split())
list1 = []
for i in range(n):
    list1.append(l+i)

if 0 in list1:
    del list1[list1.index(0)]
elif min(list1) > 0:
    del list1[list1.index(min(list1))]
else:
    del list1[list1.index(max(list1))]
print(sum(list1))

Measured memory_bytes: 3064
#include <stdio.h>
#define MOD 1000000007
long long int check[5010][5010];
long long int comb(int s, int t)
{
	if(t==0) return 1;
	if(t==s) return 1;
	if(check[s][t]) return check[s][t];
	return check[s][t] = (comb(s-1,t)+comb(s-1,t-1))%MOD;
}

int main()
{
	int a;
	scanf("%d",&a);
	
	long long int ans = 0;
	for(int i=1;i<=a;i++)
	{
		if(i*3<=a)
		{
			//(a-3i)Hi
			ans += comb(i+a-3*i-1,a-3*i);
			ans %= MOD;
		}
	}
	printf("%lld",ans);
}

Measured memory_bytes: 14888
/**************************
*                         *
*  Nothing Is Impossible  *
*                         *
**************************/
#include <algorithm>
#include <pthread.h>
#include <iostream>
#include <fstream>
#include <ctype.h>
#include <string>
#include <vector>
#include <thread>
#include <math.h>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <set>
#include <map>
#define GetRand(Min, Max) ((rand()%(int)(((Max) + 1)-(Min))) + (Min))
#define Rep(i, min, max) for(ll i = min; i < max; ++i)
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef long double ld;
using namespace std;

void Solve(){
	int n;	cin >> n;
	int arr[n],dp[n+1];
	Rep(i,0,n){
		cin >> arr[i];
	}
	dp[0] = 0;
	dp[1] = abs(arr[0]-arr[1]);
	Rep(i,2,n){
		dp[i] = min(dp[i-1]+abs(arr[i]-arr[i-1]), dp[i-2]+abs(arr[i]-arr[i-2]));
	}
	//dp[n] = min(dp[n-1],dp[n-2]);
	cout << dp[n-1] << endl;
}

int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(NULL); cout.tie(NULL);
	int t = 1;
	//int t;	cin >> t;
	while(t--) Solve();
	return 0;
}

Measured memory_bytes: 1024
from sys import stdin

def main():
    N, *LR = map(int, stdin.buffer.read().split())
    L, R = LR[::2], LR[1::2]

    max_l = max(L)
    min_r = min(R)

    ab = [(max(0, r - max_l + 1), -max(0, min_r - l + 1)) for l, r in zip(L, R)]
    ab.sort()

    mi = float("inf")
    ma = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)

    for (_, r), (l, _) in zip(ab, ab[1:]):
        mi = -r if mi > -r else mi
        ma = mi + l if ma < mi + l else ma

    print(ma)

main()


Measured memory_bytes: 27432
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k,s=0;
  cin>>n>>k;
  vector<int> p(n,1);
  for(int i=0;i<k;i++){
    int d;
    cin>>d;
    for(int j=0;j<d;j++){
      int a;
      cin>>a;
      p.at(a-1)=0;
    }
  }
  for(int i=0;i<n;i++){
    (p.at(i)==1?s+=1:s+=0);
  }
  cout<<s;
}

Measured memory_bytes: 3632
s = input()
t = input()
li_s = list(s)
li_t = list(t)
ma = {}
ma_2 = {}
for i,j in zip(li_s,li_t):
    if j not in ma:
        ma[j] = i
    elif ma[j] != i:
        print('No')
        exit()

    if i not in ma_2:
        ma_2[i] = j
    elif ma_2[i] != j:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 72796
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

// #define long long long 

template <typename T> void read_stdin(const size_t size, vector<T>& array)
{
   T value;
   for (size_t i(0); i < size; ++i) {
      cin >> value;
      array.push_back(value);
   }
}

template <typename T> void output_stdout(const vector<T>& array)
{
   for (const auto& value : array) {
      cout << value << endl;
   }
}

int main() {
   size_t N;
   vector<long> inputA;
   long outputA(0);

   // read
   {
      cin >> N;
      read_stdin(N, inputA);
   }

   // process
   {
      long sum(accumulate(inputA.begin(), inputA.end(), 0));
      for (const auto& v : inputA) {
         outputA += v * (sum - v);
      }
      outputA /= 2.0;
   }

   // output
   {
      cout << outputA << endl;
   }
   
   return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }

        static readonly long Mod = 1000000000 + 7;

        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });

            var NAB = Sarray();
            var N = NAB[0];
            var A = NAB[1];
            var B = NAB[2];
            var ans = N / (A + B) * A + Min(N % (A + B), A);
            WriteLine(ans);
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 13396
#include <stdio.h>

int main(void){
    char s[200000];
    char t[200000];
    
    int i, j;
    i = 0;
    j = 0;
    
    scanf("%s\n%s", s, t);
    
    while (s[i] != '\0' && t[i] != '\0'){
            if(s[i] != t[i]){
                s[i] = t[i];
                j++;
            }
            i++;
    }
    printf("%d\n", j);
    
    return 0;
}

Measured memory_bytes: 2124
# -*- coding: utf-8 -*-

N = int(input().strip())
h_list = list(map(int, input().rstrip().split()))
#-----

cost = [0]*N
cost[1] = abs(h_list[1] - h_list[0])

for i in range(2,N):
  cost1 = cost[i-1] + abs(h_list[i] - h_list[i-1])
  cost2 = cost[i-2] + abs(h_list[i] - h_list[i-2])
  cost[i] = min( cost1, cost2 )

print(cost[-1])


Measured memory_bytes: 13928
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int mod = 1000000007;
int n, k;
vector<int> gL;
vector<int> gR;
vector<int> dp[101];

signed main() {
	int i, j;
	
	cin >> n >> k;
	
	for (i = 1; i <= n; ) {
		int st = i, ed = n + 1, mid;	//oooxxx, [st, ed)
		while (ed - st >= 2) {
			mid = (st + ed) / 2;
			if (n / i == n / mid) st = mid;
			else ed = mid;
		}
		
		//i ≦ m ≦ stなる整数mについて、[n / m]は同じ値を取る
		gL.push_back(i);
		gR.push_back(st);
		i = st + 1;
	}
	
	int sz = gL.size();
	
	rep(i, k + 1) {
		dp[i].resize(sz);
		rep(j, sz) dp[i][j] = 0;
	}
	
	dp[0][0] = 1;
	rep(i, k) {
		int ssum = 0;
		rep(j, sz) {
			ssum += dp[i][j];
			ssum %= mod;
			int rj = sz - 1 - j;
			dp[i + 1][rj] += ssum * (gR[rj] - gL[rj] + 1) % mod;
			dp[i + 1][rj] %= mod;
		}
	}
	
	int ans = 0;
	rep(j, sz) {
		ans += dp[k][j];
		ans %= mod;
	}
	cout << ans << endl;
	return 0;
}

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

const long long MOD = 1000000007;
const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  string S;
  cin >> N >> S;
  int num1 = 0, num2 = 0;
  for (int i = 0; i < N; i++)
  {
    if (S[i] == '(')
      num1++;
    else if (S[i] == ')' && num1 > 0)
      num1--;
  }
  for (int i = N - 1; i >= 0; i--)
  {
    if (S[i] == ')')
      num2++;
    else if (S[i] == '(' && num2 > 0)
      num2--;
  }
  string left, right;
  for (int i = 0; i < num1; i++)
    right += ")";
  for (int i = 0; i < num2; i++)
    left += "(";
  cout << left + S + right << endl;
  return 0;
}

// 前と後ろから()の数を数えていく 足りない分だけ足していく


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

using namespace std;

int x[11][11];

int main() {
  int N, D;
  while (cin >> N >> D) {
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < D; j++) {
        cin >> x[i][j];
      }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        int dist = 0;
        for (int k = 0; k < D; k++) {
          dist += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
        }
        double c = ceil(sqrt(dist));
        if (int(c * c) == dist) ans++;
      }
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 504