akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define ll long long
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vvvl vector<vector<vector<ll> > >
#define vd vector<double>
#define vvd vector<vector<double> >
#define vvvd vector<vector<vector<double> > >
#define mod 1000000007
using namespace std;

long double dp[301][301][301];
ll n;

long double f(int i,int j,int k){
    if(dp[i][j][k] != -1) return dp[i][j][k];
    if(!(i+j+k)) return 0;
    long double ret = n;
    if(i > 0) ret += f(i-1,j,k)*i;
    if(j > 0) ret += f(i+1,j-1,k)*j;
    if(k > 0) ret += f(i,j+1,k-1)*k;
    ret *= (double)1/(i+j+k);
    return dp[i][j][k] = ret;
}

int main(void){
    cin>>n;
    vl a(n);
    for(int i=0;i<n;++i) cin>>a[i];
    vl c(3);
    for(int i=0;i<n;++i) c[a[i]-1]++;
    for(int i=0;i<301;++i) for(int j=0;j<301;j++) for(int k=0;k<301;++k) dp[i][j][k] = -1;
    cout<<setprecision(10)<<f(c[0],c[1],c[2])<<endl;
}


Measured memory_bytes: 426496
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;


struct Node {
  int key;
  Node *right,*parent,*left;
};

Node *root,*Nil;

Node * treemin(Node *x){
  while(x->left != Nil){
    x=x->left;
  }return x;
}

Node * find(Node *x,int k){
  while(x!=Nil && k!=x->key){
    if(k< x->key)x=x->left;
    else x=x->right;
  }return x;
}

Node * treesuc(Node *x){
  if(x->right != Nil){
    return treemin(x->right);
  }
  Node *y=x->parent;
  while(y!=Nil && x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}
void treedel(Node *z){
  Node *x,*y;
  if(z->left == Nil || z->right == Nil)y=z;
  else y=treesuc(z);

  if(y->left!=Nil){
    x=y->left;
  }
  else {
    x=y->right;
  }
  if(x!=Nil)x->parent=y->parent;
  if(y->parent==Nil){root=x;}
  else{
    if(y==y->parent->left){y->parent->left=x;}
    else {y->parent->right=x;}
  }

  if(y!=z){
    z->key=y->key;
  }
  free(y);
}
void insert(int a){
  Node *x=root,*y=Nil,*z;

  z=(struct Node *)malloc(sizeof( Node));
  z->key=a;
  z->left=Nil;
  z->right=Nil;

  while(x!=Nil){
    y=x;
    if(z->key < x->key){x = x->left;}
    else {x = x->right;}
  }
  z->parent=y;

  if(y==Nil){root=z;}
  else {
    if(z->key < y->key){y->left=z;}
    else {y->right=z;}
  }
}

void inorder(Node *x){
  if(x==Nil)return;
  inorder(x->left);
  printf(" %d",x->key);
  inorder(x->right);
}
void preorder(Node *x){
  if(x==Nil)return;
  printf(" %d",x->key);
  preorder(x->left);
  preorder(x->right);
}int main(){
  int n,i,a;
  string co;

  scanf("%d",&n);

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

    if(co[0]=='f'){
      scanf("%d",&a);
      Node *b=find(root,a);
      if(b!=Nil)printf("yes\n");
      else printf("no\n");
    }
    else if(co=="insert"){
      scanf("%d",&a);
      insert(a);
    }
    else if(co=="print"){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(co=="delete"){
      scanf("%d",&a);
      treedel(find(root,a));
    }
  }

  return 0;
}




Measured memory_bytes: 22036
// ------------------------------------
// Date:2018/ 3/17
// Problem:Not so Diverse b.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

typedef long long ll;

static const int MOD = 1000000007;

int cnt[202020];

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

  fill_n(cnt, 202020, 0);
  int N, K;
  cin >> N >> K;
  vector< pair< int, int > > a;
  REP(i, N) {
    int t;
    cin >> t;
    cnt[t - 1]++;
  }
  sort(cnt, cnt + 202020, greater< int >());

  ll ans = 0ll;
  FOR(i, K, 202020) {
    ans += cnt[i];
  }

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



Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
using namespace std;
const long long int INF = 99999999999999999;

//ユークリッドの互除法　a,bは最大公約数を求めたい２つの数
long long int gcd(long long int a, long long int b) {
	long long int tmp;
	long long int r = 1;
	if (b > a) {
		tmp = a;
		a = b;
		b = tmp;
	}
	r = a % b;
	while (r != 0) {


		a = b;
		b = r;
		r = a % b;

	}
	return b;
}
int main() {
	complex<long double>cmpmp;
	const long long int mod = 1000000007;
	map<long long int, long long int>mp;
	//cout << fixed << setprecision(10);
	string str;
	long long int a,b,c,d;
	cin >> a>>b>>c>>d;
	cout << b-a+1-(b / c + b / d - b / (c*d/gcd(c,d)) - ((a-1) / c + (a-1) / d - (a-1)/(c*d/gcd(c , d))));
}

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



int main() {
 int N;
 cin >> N;
  
  vector<int> a(N);
  
  for(int i=0; i<N; i++)
    cin >> a.at(i);
  
 
  sort(a.begin(),a.end(), greater<int>());
  int ans = 0;

  for(int i=0; i<N; i+=2)
    ans += a.at(i);
  for(int i=1; i<N; i+=2)
    ans -= a.at(i);
  
  
  cout << ans << endl;
}

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

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

	for(int i=n;i>0;i--){
		int j=2, sum=ans[i];
		while(i*j<=n){
			sum+=ans[i*j];
			j++;
		}
		if(sum%2 != a[i]%2) ans[i]=1;
		else ans[i]=0;
	}

	int sum=0;
	for(int i=1;i<=n;i++) if(ans[i]) sum++;

	bool flag=true;
	if(sum%2 != a[1]) flag=false;

	//if(flag==true){
		if(sum){
			cout<<sum<<endl;
			for(int i=1;i<=n;i++){
				if(ans[i]){
					cout<<i<<" ";
				}
			}
			cout<<endl;
		}else{
			cout<<0<<endl;

		}
	//}else{
	//	cout<<-1<<endl;
	//}



	return 0;
}


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

using namespace std;

inline int read() 
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') 
	{
		if (ch == '-')
			f = -1;
			ch = getchar();
	}
    while(ch >= '0' && ch <= '9') 
	{ 
		x = x * 10 + ch - 48;
		ch = getchar();
	}
    return x * f;
}

const int M = 1e5 + 10;

struct P 
{
    int b;
	long long c;
    bool operator < (const P & rhs) const
	{
        return c > rhs.c;      
    }
}p[M];

int main()
{
    int n = read(), m = read();
    priority_queue<long long, vector<long long>, greater<long long> > que;
    for (int i = 0; i < n; i++) 
	{
        int x = read();
        que.push((long long)x);
    }    
    for(int i = 0; i < m; i++) 
		p[i].b = read(), p[i].c = (long long)read();
    sort(p, p + m);
    for(int i = 0; i < m; i++) 
	{
        int b = p[i].b;
        if (p[i].c <= que.top())
			break;
        while (b--) 
		{
            if (que.top() < p[i].c) 
			{
                que.pop();
                que.push(p[i].c);
            }
			else 
                break;
        }
    }
    long long sum = 0;
    while(!que.empty()) 
	{
        int x = que.top(); 
		que.pop();
        sum += x;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 2676
import java.util.Scanner;

public class Main {
	private static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int sx = sc.nextInt();
		int sy = sc.nextInt();
		int tx = sc.nextInt();
		int ty = sc.nextInt();
		String s1, s2, s3, s4;
		int n = Math.abs(tx-sx);
		int m = Math.abs(ty-sy);

		if (tx>sx) {
			s1 = "R";
			s3 = "L";
		} else {
			s1 = "L";
			s3 = "R";
		}

		if (ty>sy) {
			s2 = "U";
			s4 = "D";
		} else {
			s2 = "D";
			s4 = "U";
		}

		StringBuilder sb = new StringBuilder();

		for (int i = 0;i < n;i++) sb.append(s1);
		for (int i = 0;i < m;i++) sb.append(s2);
		for (int i = 0;i < n;i++) sb.append(s3);
		for (int i = 0;i < m;i++) sb.append(s4);
		sb.append(s4);
		for (int i = 0;i <= n;i++) sb.append(s1);
		for (int i = 0;i <= m;i++) sb.append(s2);
		sb.append(s3);
		sb.append(s2);
		for (int i = 0;i <= n;i++) sb.append(s3);
		for (int i = 0;i <= m;i++) sb.append(s4);
		sb.append(s1);

		System.out.println(sb.toString());
	}
}


Measured memory_bytes: 9936
//
#include <vector>
#include <set>
#include <array>
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <numeric>
#include <bitset>

//
using ll = long long;
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);++i)
inline void yes(bool cond) { cond ? puts("Yes") : puts("No"); }
template<typename Type> inline void chmin(Type& a, Type b) { if (a > b) a = b; }
template<typename Type> inline void chmax(Type& a, Type b) { if (a < b) a = b; }
ll    BIGP = 1000000007;
ll    INF_I = std::numeric_limits<ll>::max();
float INF_F = std::numeric_limits<float>::infinity();
//
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    ll N, K;
    vector<ll> h;
    cin >> N >> K;
    rep(i, N)
    {
        ll t;
        cin >> t;
        h.push_back(t);
    }
    vector<ll> dp(N,INF_I);
    dp[0] = 0;
    rep(i, N)
    {
        rep(j, K)
        {
            ll t = i - j - 1;
            if (t >= 0)
            {
                chmin(dp[i], dp[t] + abs(h[i] - h[t]));
            }
        }
    }
    cout << dp.back();
}

Measured memory_bytes: 4632
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

void solve(ll N, ll K) {
  ll res = 1;
  REP(i,N) {
    res = min(res * 2, res + K);
  }
  cout << res << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll N;
	ll K;
	scanf("%lld", &N);
	scanf("%lld", &K);
	solve(N, K);
	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 NK = Sarray();
            var N = NK[0];
            var K = NK[1];
            N = N % K;
            var ans = Math.Min(N, K - N);
            WriteLine(ans);

            //Out.Flush();
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define REP(i,n) for(ll i = 0;i < n; i++)
int main(){
    string s;
    cin >> s;
    REP(i,s.length()){
        if(i%2==0) {
            if(s[i] == 'L') {
                cout << "No" << endl;
                return 0;
            }   
        }else{
            if(s[i] == 'R') {
                cout << "No" << endl;
                return 0;
            } 
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

#define NMAX 100000
int main(){
    /*long long N,X[NMAX],L[NMAX];

    cin>>N;
    for(int i=0;i<N;i++){
        cin>>X[i];
        cin>>L[i];
    }*/

    long long N,K,S;
    long long a[2];

    cin>>N>>K>>S;
    a[0]=S/2;
    a[1]=S-a[0];
    if(1){
        for(int i=0;i<N;i++){
            if(K>=1) cout<<S;
            else{
                if(S!=1000000000) cout<<"1000000000";
                else cout<<"999999999";
            }
            if(i>=0) K--;
            if(i!=N-1) cout<<" ";
            else cout<<endl;
        }
    }
    /*else{
        for(int i=0;i<N;i++){
            if(K>=1) cout<<a[i%2];
            else{
                if(S!=1000000000) cout<<"1000000000";
                else cout<<"999999999";
            }
            if(i>=1) K--;
            if(i!=N-1) cout<<" ";
            else cout<<endl;
        }
    }*/


}


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

int main(void) {
  ios::sync_with_stdio(false);
  int L, R, d;
  cin >> L >> R >> d;
  int answer = 0;
  for (int i = L; i <= R; ++i) {
    if (i % d == 0) ++answer;
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <set>
#include <unordered_map>
using namespace std;

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

const int INF = 1e9;
const int MAX_V = 1e6+1;

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef long long ll;

int A, B, X;
int main() {
  cin >> A >> B >> X;
  if(X - A < 0 || A + B < X) printf("%s\n", "NO");
  else printf("%s\n", "YES");
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lpin(i,n,a) for(int i=0;i<n;i++)cin>>a[i];
int main(){
  int n,m,a[1000],b[1000];
  cin>>n;
  lpin(i,n,a);
  cin>>m;
  lpin(i,m,b);
  if(lexicographical_compare(a,a+n,b,b+m)){
    cout<<"1"<<endl;
  }
  else cout<<"0"<<endl;
  return 0;
}



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

typedef long long ll;

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

int main() {
    ll k, q;
    cin >> k >> q;
    vector<ll> d(k);
    rep(i, k) cin >> d[i];
    rep(i, q) {
        ll n, x, m;
        cin >> n >> x >> m;
        vector<ll> s(k + 1, 0), e(k + 1, 0);
        rep(i, k) {
            s[i + 1] = s[i] + (d[i] % m);
            e[i + 1] = e[i];
            if (d[i] % m == 0) e[i + 1]++;
        }
        ll t = (x % m) + (n - 1) / k * s[k] + s[(n - 1) % k];
        cout << n - 1 - t / m - (n - 1) / k * e[k] - e[(n - 1) % k] << endl;
    }
}

Measured memory_bytes: 512
import heapq

def main():
  n = int(input())
  abs = [tuple(map(int, input().split())) for _ in range(n)]

  pq = []

  for ab in abs:
    a,b = ab[0],ab[1]
    heapq.heappush(pq, tuple([b,a]))

  dl = 0
  tc = 0

  ans = "Yes"

  for i in range(n):
    ba = heapq.heappop(pq)
    dl = ba[0]
    tc += ba[1]
    if dl < tc:
      ans = "No"
      break
  print(ans)
  
if __name__ == "__main__":
  main()

Measured memory_bytes: 104796
N = int(input())
A = list(map(int,input().split()))
dp = [0] * (N+10)
dp[2] = abs(A[1] - A[0])
for i in range(2,N):
    Ai = abs(A[i] - A[i-1])
    Ai2 = abs(A[i] - A[i-2])
    dp[i+1] = min(dp[i]+Ai,dp[i-1]+Ai2)

print(dp[N])

Measured memory_bytes: 13928
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
#define MAX_N (100010)

ll a[MAX_N + 1];

int main()
{
    int N;
    int L;
    ll max_pair = 0;
    int max_index = 0;

    scanf("%d %d", &N, &L);
    
    // 1-origin
    for ( int i = 1; i <= N; i++ ) {
	scanf("%lld", &a[i]);
	if ( i > 1 ) {
	    if ( max_pair < ( a[i-1] + a[i] ) ) {
		max_pair = (a[i-1] + a[i]);
		max_index = i - 1;
	    }
	}
    }

    if ( max_pair < L ) {
	printf("Impossible\n");
    }
    else {
	printf("Possible\n");
	for ( int i = 1; i < max_index; i++ ) {
	    printf("%d\n", i);
	}
	for ( int i = N - 1; i > max_index; i-- ) {
	    printf("%d\n", i);
	}

	printf("%d\n", max_index);
    }
    
    return 0;
}


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

namespace Solve
{
    public class Solve
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine();
            if (input[2] == input[3] &&
                input[4] == input[5])
            {
                Console.WriteLine("Yes");
            }
            else 
            {
                Console.WriteLine("No");
            }
        }
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define faster ios_base::sync_with_stdio(0);
#define faster_tie cin.tie(0);
#define fr(i,a,b) for(int i=a;i<=b;i++)

int main()
{

    ll a,b,c;
    cin>>a>>b>>c;
    ll ans=(b+c)-a;
    if(ans<0)ans=0;
    cout<<ans<<endl;
    return 0;
}


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


string num[100];
int get[100];
int n;

int check(string x) {
  for(int t = 0; t < n; t++) {
    for(int i = 0; i < 8; i++) {
      if(num[t][i] == '*') continue;
      if(num[t][i] != x[i]) break;
      if(i == 7) return t;
    }
  }
  return -1;
}

main() {
  int m;
  int sum;
  int tmp;
  string x;
  while((cin >> n) && n != 0) {
    sum = 0;
    cin >> m;
    for(int i = 0; i < n; i++) {
      cin >> num[i] >> get[i];
    }
    for(int i = 0; i < m; i++) {
      cin >> x;
      if((tmp = check(x)) != -1) sum += get[tmp];
    }
    cout << sum << endl;
  }
}

Measured memory_bytes: 924
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))

bool ok(string& x, char c)
{
    bool ret = true;
    rep (i, x.size())
    {
        if (x[i] != c) ret = false;
    }
    return ret;
}

int solve(string s, char c)
{
    int ret = 0;
    while (!ok(s, c))
    {
        string t(s.size() - 1, '\0');
        rep (i, t.size())
        {
            if (s[i] == c || s[i + 1] == c)
            {
                t[i] = c;
            }
            else
            {
                t[i] = s[i];
            }
        }
        s = t;
        ++ret;
    }
    return ret;
}

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

    string s;
    cin >> s;

    int ans = 1e9;
    rep (i, s.size())
    {
        ans = MIN(ans, solve(s, s[i]));
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  size_t A;
  cin >> A;

  size_t sum = 0;
  for (size_t i = 1; i <= A / 2; i++) {
    if (i + (A - i) == A && i != (A - i)) {
      sum++;
    }
  }

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, a, n) for (ll i = (a); i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
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;}

int main() {
    ll n, k;
    cin >> n >> k;
    ll g, mx;
    cin >> g;
    mx = g;
    rep(i, 1, n) {
        ll a;
        cin >> a;
        g = __gcd(g, a);
        chmax(mx, a);
    }
    if (k <= mx && k % g == 0) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
    
}

Measured memory_bytes: 256
import numpy as np
n,k=list(map(int,input().split()))
h=np.array(list(map(int,input().split())))
npmin=np.min
npabs=np.abs
k=min(k,n-1)
dp=np.zeros(n+1)
for i in range(2,k+1):
    dp[i]=npmin(dp[1:i]+npabs(h[i-1]-h[0:i-1]))
for i in range(k+1,n+1):
    dp[i]=npmin(dp[i-k:i]+npabs(h[i-1]-h[i-1-k:i-1]))
print(int(dp[n]))

Measured memory_bytes: 22936
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int mod=1e9+7;
const int INF = LONG_LONG_MAX;
inline int gcd(int a,int b){if(a==0) return b;return gcd(b%a,a);}
inline int pow(int a,int n,int mod){if(n==0)return 1;int p=pow(a,n/2,mod);p=(p%mod*p%mod)%mod;if(n%2) return (p%mod*a%mod)%mod;else return p;}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k<=a+b)
        cout<<min(k,a)<<endl;
    else
    {
        int d=k-a-b;
        cout<<a-d<<endl;
    }
    return 0;
}


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

int main(){
    int N;
    cin>>N;
    vector<int> A=vector<int>(N);
    for (int i=0; i<N; i++) {
        cin>>A[i];
    }
    
    int ans=0;
    int koeta=0;
    int lim=0;
    
    while (lim==0) {
        for (int i=0; i<N; i++) {
            if (A[i]%2==0) {
                A[i]=A[i]/2;
            }
            else{koeta++;}
        }
        if (koeta==0) {
            ans++;
        }
        else{lim++;}
    }
    
    cout<<ans;
 
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <algorithm>

const int MOD = (int)1e9 + 7;
const int kN = 2000 + 5;
const int kM = kN * 3;
int A, B;
int ways[kN][kN];
int suf[kN][kN];
int F[kM], Finv[kM], Inv[kM];

int binom(int a, int b)
{
    if (b < 0 || b > a) return 0;
    return F[a] * 1LL * Finv[a - b] % MOD * Finv[b] % MOD;
}

inline void add(int &a, int b)
{
    a += b;
    if (a >= MOD) a -= MOD;
}

int main()
{
    Inv[1] = 1;
    for (int i = 2; i < kM; ++ i)
        Inv[i] = (MOD - MOD / i) * 1LL * Inv[MOD % i] % MOD;
    F[0] = Finv[0] = 1;
    for (int i = 1; i < kM; ++ i) {
        F[i] = F[i - 1] * 1LL * i % MOD;
        Finv[i] = Finv[i - 1] * 1LL * Inv[i] % MOD;
    }
    scanf("%d%d", &A, &B);
    int result = 0;
    for (int b = 1; b <= B - 1; ++ b) {
        ways[0][b] = 1;
        for (int k = 1; k <= A; ++ k) {
            ways[k][b] = binom(b - 1, k);
            add(ways[k][b], ways[k - 1][b]);
        }
    }
    for (int a = 0; a <= A; ++ a)
        suf[a][0] = 1;
    for (int b = 1; b <= B; ++ b) {
        suf[0][b] = 1;
        for (int a = 1; a <= A; ++ a) {
            suf[a][b] = ways[a][b];
            add(suf[a][b], suf[a - 1][b]);
        }
    }

    for (int i = 0; i <= A; ++ i) {
        for (int j = 0; j + i <= A && j <= B - 1; ++ j) {
            int a = A - i - j;
            int b = j;
            add(result, binom(B - 1, j) * 1LL * suf[a][b] % MOD);
        }
    }
    printf("%d\n", result);

    return 0;
    result = 0;
    for (int i = 0; i <= A; ++ i) {
        for (int j = 0; j + i <= A && j <= B - 1; ++ j) {
            int a = A - i - j;
            int b = j;
            if (j == 0) {
                add(result, 1);
                continue;
            }
            for (int k = 0; k <= a; ++ k) {
                for (int r = 0; r + k <= a && r <= b - 1; ++ r) {
                    add(result, binom(b - 1, r) * 1LL * binom(B - 1, j) % MOD);
                }
            }
        }
    }
    printf("%d\n", result);
}



Measured memory_bytes: 31616
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <climits>
#include <cmath>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define FOR(i, m, n) for (int i = (int)m; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define REPe(e, mp) for (auto& e : mp)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
using ll = long long int;
using vecint = vector<int>;
using vecll = vector<ll>;
using vec2int = vector<vector<int>>;
using P = pair<int, int>;
////////////////////////////////////////////////
////////////////////////////////////////////////
int main() {
  ////////////////////////////////////////////////
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ////////////////////////////////////////////////
  ll n, p;
  cin >> n >> p;
  if (n == 1) {
    cout << p << endl;
    return 0;
  }
  ll ans = 1;
  ll test = 2;
  while (p >= pow(test, n)) {
    ll cnt = 0;
    while (p % (ll)pow(test, n) == 0) {
      p /= (ll)pow(test, n);
      cnt++;
    }
    ans *= (ll)pow(test, cnt);
    test++;
  }
  cout << ans << endl;
}
//////////////////////////////////////////////


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

int main(int argc, char const *argv[])
{
	int n,k;
	cin>>n>>k;
	double p[n];
	for (int i = 0; i < n; ++i)
	{
		cin>>p[i];
		p[i]=(p[i]+1.0)/2.0;
	}
	double ans=0.0;
	for (int i = 0; i < k; ++i)
	{
		ans+=p[i];
	}
	double now=ans;
	for (int i = k; i < n; ++i)
	{
		now+=p[i];
		now-=p[i-k];
		ans=max(ans,now);
	}
	printf("%.8f\n", ans);
	return 0;
}


Measured memory_bytes: 1792
N, M = map(int, input().split())
A = list(map(int, input().split()))

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
  if a_==0: break
print(sum(A))

Measured memory_bytes: 15020
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

struct Edge {
    ll from, to, cost;
    Edge(){}
    Edge(ll from, ll to, ll cost):from(from),to(to),cost(cost){}
};

bool comp(const Edge &e1, const Edge &e2) {
    return e1.cost<e2.cost;
}

class union_find {
private:
    vector<ll> par;
    vector<ll> ran;
    vector<ll> m_size;
public:
    union_find(int n);
    int find(int x);
    void unite(int x, int y);
    bool same(int x, int y);
    ll size(int x);
};

union_find::union_find(int n){
    par.resize(n);
    iota(par.begin(), par.end(), 0);
    ran.resize(n, 0);
    m_size.resize(n, 1);
};

int union_find::find(int x) {
    if (par[x] == x) return x;
    else return par[x] = find(par[x]);
};

void union_find::unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (ran[x] < ran[y]) swap(x,y);
    par[y] = x;
    m_size[x] += m_size[y];
    if (ran[x]==ran[y]) ran[x]++;
};

ll union_find::size(int x) {
    return m_size[find(x)];
}

bool union_find::same(int x, int y) {
    return (find(x) == find(y));
};


vector<Edge> g;

int V,E;

ll kruskal() {
    sort(g.begin(), g.end(), comp);
    union_find uf(V);
    ll res = 0ll;
    for (auto &&e: g) {
        if (!uf.same(e.from,e.to)) {
            uf.unite(e.from,e.to);
            res+=e.cost;
        }
    }
    return res;
}

typedef struct edge {
    ll to, cost;
} edge;

vector<vector<edge>> G;
vector<bool> used;

ll prim() {
    used.resize(V,false);
    priority_queue<P, vector<P>, greater<P>> pq;
    ll ret = 0;

    pq.push({0,0});// pair(cost,to)

    while (!pq.empty()) {
        P x = pq.top(); pq.pop();
        ll cost = x.first; ll v = x.second;
        
        if (used[v]) continue;
        used[v] = true;
        ret+=cost;
        for (auto &&e: G[v]) {
            if (!used[e.to]) pq.push({e.cost,e.to});
        }
    }
    return ret;
}

int main(int argc, char const *argv[]) {
    cin>>V>>E;
    G.resize(V+1);
    rep(i,E) {
        ll s,t,w;
        cin>>s>>t>>w;
        g.push_back(Edge(s,t,w));
        g.push_back(Edge(t,s,w));
        G[s].push_back({t,w});
        G[t].push_back({s,w});
    }

    // cout << kruskal() << endl;
    cout << prim() << endl;
    return 0;
}


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

using namespace std;
using ll=long long;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, a, n) for(int i = (n); i < (a); i++)

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  int n;cin>>n;
  cout<<pow(n,3)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX 1000000
#define INF 1000000
#define MOD 1e9
#define pb push_back
#define pairs pair<int, int>
#define vi vector<int>
#define vb vector<bool>
#define vii vector<pairs>
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define endl '\n'
using namespace std;
/* ----------------------------------------------------------------------------------- */

#define FastInput ios_base::sync_with_stdio(false), cin.tie(NULL);
#define all(x) x.begin(), x.end()
#define read(x) freopen(x, "r", stdin)
#define write(x) freopen(x, "w", stdout)
#define rep(i, a, n) for (int i = a; i < n; i++)
#define REP(i, a, n) for (int i = a; i <= n; i++)
#define inputArray(a,n) rep(i, 0, n) cin >> a[i];
#define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
#define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;

/* ----------------------------------------------------------------------------------- */

#define Cases  cout << "Case " << ++Case << ": ";
#define __test int tt; int Case=0; cin >> tt; while(tt--)

#define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, n){cout<<A[i][j]<<" ";}cout<<"\n";}cout<<"\n";}
#define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
#define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}

/* ----------------------------------------------------------------------------------- */

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }

struct debugger {
	typedef string::iterator si;
	static void call(si it, si ed) {}
	template<typename T, typename ... aT>
	static void call(si it, si ed, T a, aT... rest) {
		string b;
		for(; *it!=','; ++it)
			if(*it!=' ')
				b+=*it;
		cout << b << "=" << a << " ";
		call(++it, ed, rest...);
	}
};

/* ----------------------------------------------------------------------------------- */

void solve() {
	int n, m;
	cin >> n >> m;
	int yen = 500 * n;
	if(m <= yen) {
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
}

int main() {
	solve();

	// __test {
	// 	solve();
	// }
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int t=s.length();
    int m,c=0;
    if(t%2==0){m=t/2;}
    else{m=((t+1)/2);}
    for(int i=0;i<m;i++)
    {
        if((s.at(i))!=(s.at(t-1-i)))
        {
            c++;
        }        
    }
    cout<<c;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <cctype>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;

int main(){
    int a, b;
    string s;
    cin >> a >> b >> s;

    if(s[a] != '-'){
        cout << "No" << endl;
        return 0;
    }

    REP(i, a){
        if(!(s[i] >= '0' && '9' >= s[i])){
            cout << "No" << endl;
            return 0;
        }
    }
    REP(i, b){
        if(!(s[i+a+1] >= '0' && '9' >= s[i+a+1])){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, k, q, i, j, l, cnt = 0, x;

    cin >> n >> k >> q;

    vector <long long> v(n);

    for(i=0; i<n; i++)
    {
        v[i] = k - q;
    }

    for(i=0; i<q; i++)
    {
        cin >> x;
        v[x-1] += 1; /// Karon x=3 hole index 2 hobe 3 no person...
    }

    for(i=0; i<n; i++)
    {
        if(v[i] > 0)
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i, n)     for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n)    for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n)    for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n)   for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v)  for (auto &&V : v)
#define all(x)        (x).begin(), (x).end()
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = 1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;

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

  lint w, h, x, y;
  cin >> w >> h >> x >> y;
  double area = h * w / 2.0;
  int x2 = w - x;
  int y2 = h - y;
  cout << area << "\n" << (x == x2 && y == y2) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
  int N;
  cin >> N;
  int A[100][2];
  rep (i,2) {
    rep(j,N) {
      cin >> A[j][i];
    }
  }
  int ma = 0;
  rep(i, N) {
    int s = 0;   
    rep(j, i + 1) s += A[j][0];
    for (int j = i; j < N; j++) s += A[j][1];
    if (ma < s) ma = s;
  }
  cout << ma << endl;
}

Measured memory_bytes: 256
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

X, N = ri_()
p = ri_()
d = 1000
ans = 1000
for i in range(-500, 501):
    f = 1
    for pi in p:
        if i == pi:
            f = 0
    if f == 1 and d > abs(X - i):
        d = abs(X - i)
        ans = i
print(ans)

Measured memory_bytes: 9204
def inpl(): return list(map(int, input().split()))

N = int(input())
S = input()
F = [1]*(N//2 + 2)
for i in range(1, len(F)):
    F[i] = F[i]*26

OK = 0
NG = N//2 + 1

def check(l):
    D = set()
    for i in range(N-2*l+1):
        #print(S[i:i+l], S[i+l:i+2*l])
        D.add(S[i:i+l])
        if S[i+l:i+2*l] in D:
            return True
    else:
        return False



while abs(OK - NG) > 1:
    mid = (OK + NG)//2
    if check(mid):
        OK = mid
    else:
        NG = mid

print(OK)

Measured memory_bytes: 6388
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

using namespace std;

typedef long long LL;
#define int LL

const int inf = 1e9,maxn=2e5+5;

int n,a[maxn],sum[maxn];

void solve(int l,int r,int &a1,int &a2){
	int le = l, ri = r-1, res=inf;
	while(le <= ri){
		int mid=le+ri>>1;
		int x = sum[mid]-sum[l-1];
		int y = sum[r]-sum[mid];
		if(abs(x-y) < res){
			res = abs(x-y);
			a1 = x;a2 = y;
		}
		if(x<=y)le=mid+1;
		else ri=mid-1; 
	}
}

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]), sum[i]=sum[i-1]+a[i];
	
	int res=inf;
	for(int i=2;i<=n-2;i++){
		int p,q,r,s;
		solve(1,i,p,q);
		solve(i+1,n,r,s);
		res = min(res, max(max(p,q),max(r,s)) - min(min(p,q),min(r,s)));
	}
	printf("%lld\n",res);

	return 0;
}


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

#define hell                         1000000007
#define lcm(a,b)                     (a*b)/__gcd(a,b)
#define ll                           long long
#define vll                          vector<ll>
#define vi                           vector<int>
#define pll                          vector< pair<ll,ll> >
#define pb                           push_back
#define mp                           make_pair
#define all(v)                       v.begin(),v.end()
#define lbnd                         lower_bound
#define ubnd                         upper_bound
#define bs                           binary_search
#define F                            first
#define S                            second
#define rep(i,a,b)                   for(i=a;i<b;i++)
#define parr(a,n)                    for(ll it=0;it<n;it++) cout<<a[it]<<" ";cout<<endl;
#define pcont(a)                     for(auto it:a) cout<<it<<" ";cout<<endl;
#define ret(x)                       return cout<<x,0;
#define endl                           '\n'

/*constants*/
#define MAXN                         100005
#define PI                           3.14159265358979323846

/*debug*/
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template <typename Arg1>void __f(const char* name, Arg1&& arg1){ std::cout << name << " : " << arg1 << '\n';}
    template <typename Arg1, typename... Args>void __f(const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr(names + 1, ','); std::cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}
#else
#define trace(...)
#endif

using namespace std;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	ll i,j,n,m,k,cnt=0,ans=0,t=1;
	cin>>n;
	ll a[n];
	rep(i,0,n) cin>>a[i];
	rep(i,1,n-1){
		if((a[i]>a[i+1] && a[i]<a[i-1] )||(a[i]>a[i-1] && a[i]<a[i+1])) ans++;
	}	
	ret(ans)
	
	return 0;
}

Measured memory_bytes: 256
use strict;
use warnings;
use utf8;

my $people_num = <STDIN>;
my @data = ();
for (my $witness = 0; $witness < $people_num; $witness++) {
    my $testimony_num = <STDIN>;
    $data[$witness] = [];
    for (my $i = 0; $i < $testimony_num; $i++) {
        my ($person_plus_one, $is_honest) = split /\s/, <STDIN>;
        push $data[$witness], [$person_plus_one-1 , $is_honest];
    }
}

my $answer = 0;
for (my $x = 0; $x < 2**$people_num; $x++) {
    my @assumption = ();
    for (my $person = 0; $person < $people_num; $person++) {
        $assumption[$person] = ($x >> $person) & 1;
    }
    my $has_contradict_testimony = 0;
    for (my $witness = 0; $witness < $people_num; $witness++) {
        next unless $assumption[$witness];
        next unless values $data[$witness];
        $has_contradict_testimony = grep {
            my $person = $_->[0];
            my $is_honest = $_->[1];
            $assumption[$person] ne $is_honest;
        } values $data[$witness];
        last if $has_contradict_testimony;
    }
    unless ($has_contradict_testimony) {
        my $honest_people_num = grep {
            $_ == 1
        } @assumption;
        $answer = $honest_people_num if $honest_people_num > $answer;
    }
}
print $answer;


Measured memory_bytes: 768
import java.util.ArrayList;
import java.util.Scanner;

class Main{
	static int[][] dp;




	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		int[] p = new int[n];

		for(int i = 0;i < n;i++){
			list.add(new ArrayList<Integer>());
		}
		for(int i = 0;i < m;i++){
			int x = sc.nextInt()-1;
			int y = sc.nextInt()-1;
			list.get(x).add(y);
			p[y]++;
		}
		ArrayList<Integer> q = new ArrayList<Integer>();
		for(int i = 0;i < n;i++){				//誰からも繋がり先でない町(親ノード)を見つける
			if(p[i] == 0){
				q.add(i);
			}
		}
		int[] dp = new int[n];
		for(int i = 0;i < q.size();i++){
			int parent = q.get(i);
			for(int child : list.get(parent)){		//親ノードから繋がっている町を探す
				dp[child] = Math.max(dp[child], dp[parent]+1);
				p[child]--;					//親ノードからの矢印をなくす
				if(p[child] == 0){			//どこからも繋がり先出なくなったら親ノードになる
					q.add(child);			
				}
			}
		}
		int ans = 0;
		for(int i = 0;i < n;i++){
			ans = Math.max(ans,dp[i]);
		}
		System.out.println(ans);
		
		
		
		
		//		for(int i = 0;i < m;i++){
		//			int x = sc.nextInt();
		//			int y  = sc.nextInt();
		//			dp[x+1][y+1]++;
		//		}



	}

	//	static int dfs(int x, int y){
	//		
	//		
	//		
	//		
	//	}
}







class Pair implements Comparable{
	int from;		//p
	int end;		//y
	int num;
	int bango;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}



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

template <int MOD=1000000007>
struct Modular {
  int value;
  static const int MOD_value = MOD;

  Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}

  Modular& operator+=(Modular const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  Modular& operator-=(Modular const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  Modular& operator*=(Modular const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend Modular mexp(Modular a, long long e) {
    Modular res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }

  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) {return os << a.value;}
  friend bool operator==(Modular const& a, Modular const& b) {return a.value == b.value;}
  friend bool operator!=(Modular const& a, Modular const& b) {return a.value != b.value;}
};

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

  int n, m;
  cin >> n >> m;
  
  vector<Modular<>> fact(m + 5);
  fact[0] = 1;
  for (int i = 1; i < m + 5; ++i) fact[i] = i * fact[i - 1];
  
  auto npr = [&](int l, int r) {
    return fact[l] / fact[l-r];
  };

  auto ncr = [&](int l, int r) {
    return npr(l, r) / fact[r];
  };

  Modular<> ans = npr(m, n);
  for (int i = 1; i <= n; ++i) {
    int sign = (i&1) ? -1 : 1;
    ans += sign * ncr(n, i) * npr(m - i, n - i);
  }
  ans *= npr(m, n); 
  cout << ans << '\n';
}


Measured memory_bytes: 5316
n, y = map(int, input().split())
for i in range(min(n+1,y//10000+1)):
  r = y - i*10000
  for j in range(min(n+1-i,r//5000+1)):
    if j*5000 + (n-i-j)*1000 == r:
      print(i, j, n-i-j)
      exit()

print("-1 -1 -1")

Measured memory_bytes: 3064
def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 1000
    for i in range(1, n):
        if a[i-1] < a[i]:
            ans += (ans//a[i-1])*(a[i]-a[i-1])
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9172
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K = sc.nextInt();
		int x[] = new int[N];
		int ans = 0;
		for (int i = 0; i < N; i++) {
			x[i] = sc.nextInt();
			if (K - x[i] < x[i]) {
				ans += (K - x[i]) * 2;
			} else {
				ans += x[i] * 2;
			}
		}
		sc.close();
		System.out.println(ans);
	}
}


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

int main() {
	// your code goes here
	double a;
	double b;
	double x;
	cin >> x >> a >> b;
	
	double disA = ((a>x)?(a-x):(x-a));
	double disB = ((b>x)?(b-x):(x-b));
	
	if(disA > disB){
		cout << "B" << endl;
	}else{
		cout << "A" << endl;
	}
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	cin>>n;
	for(long long i=sqrt(n);i>=2;i--)
	{
		if(n%i==0)
		{
			cout<<i+n/i-2<<endl;
			return 0;
		}
	}
	cout<<n-1<<endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
internal class Data
{
    internal List<List<string>> Era { get; set; }
    internal List<int> Year { get; set; }
}
public class Pg
{
    static void Main()
    {
        var rd = new Reader();
        var op = new Operate();
        var lst = new List<string>();
        var dt = rd.Read().ToList();
        dt.ForEach(x => x.Year.ForEach(yr => Console.WriteLine(op.YearConverter(yr, x.Era))));
    }
}
class Operate
{
    internal string YearConverter(int yr, IEnumerable<List<string>> Era)
    {
        var Er = "";
        var tmp = 0;
        foreach (var v in Era)
        {
            tmp = 0;
            var delta = 0;
            var n1 = int.Parse(v[1]);
            var n2 = int.Parse(v[2]);
            delta = n2 - yr;
            Er = v[0];
            if (n2 >= yr && delta < n1 && n1 - delta > 0)
            {
                tmp = n1 - delta;
                break;
            }
        }
        return tmp != 0 ? Er + " " + tmp : "Unknown";
    }
}
class Reader
{
    internal IEnumerable<Data> Read()
    {
        int[] n;
        while (!(n = Console.ReadLine().Split().Select(int.Parse).ToArray()).All(x => x == 0))
        {
            var dt = new Data { Era = new List<List<string>>(), Year = new List<int>() };
            while (n[0]-- > 0)
                dt.Era.Add(Console.ReadLine().Split().ToList());
            while (n[1]-- > 0)
                dt.Year.Add(int.Parse(Console.ReadLine()));
            yield return dt;
        }
    }
}


Measured memory_bytes: 23032
/*
 * src.cpp
 *
 *  Created on: 2016/08/05
 *      Author: joi
 */

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

const int MAX_D=256,MAX_M=6,MAX_N=100,INF=1e8;

int m,n,k,d;
int cal[MAX_M];
char S[2][16];
int di;

struct edge{
	int to,cost;
	edge(int t=0,int c=0):to(t),cost(c){};
};

vector<edge> G[MAX_M+MAX_N+2];

int cost[MAX_M+MAX_N+2][1<<MAX_M];

struct C{
	int v,flg,cost;
	C(int v=0,int flg=0,int cost=0):v(v),flg(flg),cost(cost){};
	bool operator < (const C &a)const{
		if (flg!=a.flg){
			return flg>a.flg;
		}
		return cost>a.cost;
	}
};

void dijkstra(){
	REP(i,m+n+2){
		REP(j,1<<m){
			cost[i][j]=INF;
		}
	}
	cost[0][0]=0;
	priority_queue<C> pq;
	pq.push(C(0,0,0));
	while (!pq.empty()){
		C c=pq.top();
		pq.pop();
		if (c.cost>cost[c.v][c.flg]){
			continue;
		}
		REP(i,(int)G[c.v].size()){
			edge e=G[c.v][i];
			int cst=c.cost,f=c.flg;
			cst+=e.cost;
			if (e.to>0 && e.to<=m){
				if (!(f & ( 1 << (e.to-1) ) ) ){
					f+=1 << (e.to-1);
					cst-=cal[e.to-1];
				}else{
					continue;
				}
			}
			if (cst<cost[e.to][f]){
				cost[e.to][f]=cst;
				pq.push(C(e.to,f,cst));
			}
		}
	}
}

int asc(char *s){
	int res=0;
	while (*s){
		res*=10;
		res+=*s-'0';
		s++;
	}
	return res;
}

int main(){
	do{
		scanf("%d %d %d %d",&m,&n,&k,&d);
		if (m || n || k || d){
			REP(i,m+n+2){
				G[i].clear();
			}
			REP(i,m){
				scanf("%d",&cal[i]);
			}
			REP(i,d){
				int u[2];
				scanf("%s %s %d",S[0],S[1],&di);
				REP(j,2){
					switch(S[j][0]){
					case 'H':
						u[j]=0;
						break;
					case 'D':
						u[j]=m+n+1;
						break;
					case 'C':
						u[j]=asc(S[j]+1);
						break;
					case 'L':
						u[j]=asc(S[j]+1)+m;
						break;
					}
				}
				G[u[0]].push_back(edge(u[1],di*k));
				G[u[1]].push_back(edge(u[0],di*k));
			}
			dijkstra();
			int ans=cost[m+n+1][0];
			FOR(i,1,1<<m){
				ans=min(ans,cost[m+n+1][i]);
			}
			printf("%d\n",ans);
		}
	}while(m || n || k || d);
	return 0;
}

Measured memory_bytes: 1248