akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;



int main(){
    string a,b,c; cin >> a >> b >> c;
    char ans[3];
    ans[0] = a[0];
    ans[1] = b[0];
    ans[2] = c[0];
    rep(i,3) cout << ans[i];
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdio>

using namespace std;
int ans=0;

void mark(char input[][102], int table[][102], int i, int j);

int main(){
    while (1) {
        int height=0,width=0;
        cin>>height>>width;
        //cout<<height<<width<<endl;
        if (height==0 || width == 0) {
            return 0;
        }

        char input[102][102];
        int table[102][102];
        for (int i=0; i<102; i++) {
            for (int j=0; j<102; j++) {
                input[i][j] = '\0';
                table[i][j] = 0;
            }
        }
        for (int i=1; i<height+1; i++) {
            string line;
            //getline(cin, line);
            cin>>line;
            for (int j=1; j<width+1; j++) {
                input[i][j] = line[j-1];
            }
        }
        for (int i=1; i<height+1; i++ ) {
            for (int j=1; j<width+1; j++) {
                if (table[i][j] == 0) {
                    ans++;
                    mark(input, table, i, j);
                }
            }
        }
        cout<<ans<<endl;
        ans = 0;
    }
}

void mark(char input[][102], int table[][102], int i, int j){
    if (table[i][j] != 0) {
        return;
    }
    char typeOfTree;
    typeOfTree = input[i][j];
    table[i][j] = ans;
    if (typeOfTree == input[i-1][j]) {
        mark(input, table, i-1, j);
    }
    if (typeOfTree == input[i][j-1]) {
        mark(input, table, i, j-1);
    }
    if (typeOfTree == input[i][j+1]) {
        mark(input, table, i, j+1);
    }
    if (typeOfTree == input[i+1][j]) {
        mark(input, table, i+1, j);
    }
}

Measured memory_bytes: 2496
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>
#include <stack>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)







int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    REP(i, n){
        cin >> a[i];
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(k + 1));
    dp[0][0] = 1;
    for(ll i = 0; i < n; i++){
        ll sum = 0;
        for(ll j = 0; j <= a[i]; j++){
            sum += dp[i][j];
            sum %= MOD;
            dp[i + 1][j] = sum;
        }
        for(ll j = a[i] + 1; j <= k; j++){
            sum += dp[i][j];
            sum -= dp[i][j - a[i] - 1];
            sum += MOD;
            sum %= MOD;
            dp[i + 1][j] = sum;
        }
    }
    cout << dp[n][k] << endl;
}

Measured memory_bytes: 80256
import math
x = int(input())
if x==1:
  print(1)
  exit()

used = {}
for b in range(2,int(math.sqrt(x))+1):
  p=2
  while(b**p<=x):
    used[b**p]=True
    p+=1

ans=0
for key in used.keys():
  ans = max(ans,key)

print(ans)
  

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef double dd;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<pair<int, int>> vpii;
typedef pair<int, int> pii;
typedef vector<pair<ll, ll>> vpll;
typedef pair<ll, ll> pll;

#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define all(c) (c).begin(), (c).end()
#define MOD 1000000007

int main(){
#ifdef HOME
    freopen("kek.in", "r", stdin);
    freopen("kek.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vl arr(n);
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    vl pre(n + 1, 0);
    vl suf(n + 1, 0);
    for(int i = 1; i < n + 1; i++)
        pre[i] = arr[i - 1] + pre[i - 1];
    for(int i = n - 1; i >= 0; i--)
        suf[i] = arr[i] + suf[i + 1];
    ll ans = INT_MAX;
   /* for(auto a : pre)
        cout << a << " ";
    cout << endl;
    for(auto a : suf)
        cout << a << " ";
    cout << endl;*/
    for(int i = 1; i < n; i++)
        ans = min(ans, (abs(suf[i] - pre[i])));
    cout << ans;
    return 0;
}

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

#define ll       long long
#define ull      unsigned ll
#define pii      pair<int, int>
#define pll      pair<ll, ll>
#define mp       make_pair
#define ff       first
#define ss       second
#define sz(x)    (int) x.size()
#define all(v)   v.begin(), v.end()

template <typename T> inline void smin(T &a, T b) {a = a < b ? a : b;}
template <typename T> inline void smax(T &a, T b) {a = a > b ? a : b;}

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl;}
template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ", ";
    err(++it, args...);
}

template <typename T> inline void Int(T &n) {
    n = 0; int f = 1; register int ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
    for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';
    n = n * f;
}

template <typename T, typename TT> inline void Int(T &n, TT &m) { Int(n); Int(m); }
template <typename T, typename TT, typename TTT> inline void Int(T &n, TT &m, TTT &l) { Int(n, m); Int(l); }

const int mod = (int) 1e9 + 7;

inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (ll) a * b % mod;}

const int inf = (int) 2e9 + 5;
const ll  Inf = (ll) 2e18 + 5;
const int N   = (int) 2e5 + 5;

#define EPS 0.000000001

int solve() {
    int a , b; Int(a, b);
    for(int i = 1; i <= 1e7; i++) {
        int x = (double) i * 0.08 + EPS;
        int y = (double) i * 0.1 + EPS;
        if(x == a and y == b) return printf("%d\n", i);
    }
    printf("-1\n");
    return 0;
}

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test = 1, tc = 0;
    //Int(test);
    //cin >> test;
    while (test--) {
        //printf("Case %d: ", ++tc);
        solve();
    }
    return 0;
}


Measured memory_bytes: 256
import scala.io.StdIn._

object Main extends App {

  val n = readInt()
  val a = readLine().split(" ").map(_.toInt)

  def solve() = {
    val ave = Math.round(a.sum.toDouble / a.length).toInt
    a.foldLeft(0) { (acc, num) =>
      acc + (num - ave) * (num - ave)
    }
  }
  println(solve())

}



Measured memory_bytes: 54852
#include <iostream>
#include <string.h>

using namespace std;

int main()
{
  int a[102][102] ={0};
  int c;
  int row,col;
  cin >> row >> col;

  for(int i = 0; i < row ; i++)
  {
    for(int j = 0; j < col ; j++)
    {
      cin >> a[i][j];
      a[i][col] += a[i][j];
      a[row][j] += a[i][j];
      a[row][col] += a[i][j];
    }
  }
  for(int i = 0; i <= row ; i++)
  {
    for(int j = 0; j <= col ; j++)
    {
      cout << a[i][j];
      if(j!= col) cout <<' ';
    }
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3108
#include <iostream>
#include <numeric>
using namespace std; 
 
int main(void){
    int a;cin >> a;
    int s=0;
    for (int i=a; ;i++){
        for (int q=2;q<i;q++){
            if (i%q==0){
                break;
            }
            else{
                s+=1;
            }        
        }
        if (s==i-2){
            cout << i << "\n";
            break;
        }
        else{
            s=0;
        }
        
    }
}
    

    

  


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n,m,a[1000];
int main(){
	cin>>n>>m;
	for(int i=0;i<n;i++){cin>>a[i];}
	for(int h=2;h<=m;h++){
		for(int i=0;i<n-1;i++){
			if(a[i]%h>a[i+1]%h){swap(a[i],a[i+1]);}
		}
	}
	for(int i=0;i<n;i++)cout<<a[i]<<endl;
	return 0;
}

Measured memory_bytes: 3100
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>

//#include <bits/stdc++.h>
using namespace std;
#define print(x) cout<<(x)<<endl
#define prints(x, y) cout<<(x)<<" "<<(y)<<endl
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define r_rep(i, n) for(int i = n; i >= 0; i--)
#define ll long long int
#define pb push_back

const long long INF = 1LL << 60;

int main() {
  int W, H, N, x, y, a;
  cin >> W >> H >> N;
  int x1 = 0, x2 = W, y1 = 0, y2 = H;
  rep(i, N){
    cin >> x >> y >> a;
    if (a==1) x1 = max(x1, x);
    if (a==2) x2 = min(x2, x);
    if (a==3) y1 = max(y1, y);
    if (a==4) y2 = min(y2, y);
  }

  if(x1 < x2 && y1 < y2) print((x2-x1)*(y2-y1));
  else print(0);
}


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

int main(void)
{
    int X;
    cin >> X;

    ll ans = 0;
    while (X >= 500)
    {
        X -= 500;
        ans += 1000;
    }
    // printf("%d\n", X);
    while (X >= 5)
    {
        X -= 5;
        ans += 5;
    }
    cout << ans << endl;
    return (0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Pair = pair<int, int>;

int main() {
    int N, K;
    cin >> N >> K;
    priority_queue<Pair> que;
    for(int i = 0; i < N; ++i) {
        int t, d;
        cin >> t >> d;
        que.emplace(d, t);
    }
    int64_t ans = 0, total = 0, neta = 0;
    vector<int> cnt(N + 1);
    priority_queue<Pair, vector<Pair>, greater<Pair>> sushi;
    auto push = [&](int d, int t) {
        if(!cnt[t]) neta++;
        else sushi.emplace(d, t);
        total += d;
        cnt[t]++;
    };
    auto pop = [&]() -> Pair {
        auto[d, t] = sushi.top(); sushi.pop();
        total -= d;
        cnt[t]--;
        if(!cnt[t]) neta--;
        return {d, t};
    };
    while(!que.empty()) {
        auto[d, t] = que.top(); que.pop();
        if(K) {
            K--;
            push(d, t);
        } else {
            if(sushi.empty()) break;
            auto[d2, t2] = pop();
            if(!cnt[t]) push(d, t);
            else push(d2, t2);
        }
        ans = max(ans, total + neta * neta);
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 5236
#include <iostream>

using namespace std;

int main() {
	int n; cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i) {
    	cin >> a[i];
    }
  
    int max = 0;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += a[i];
    	if (a[i] > max) {
        	max = a[i];
        }
    }
  
    if (sum - max > max) {
    	cout << "Yes\n";
    } else {
    	cout << "No\n";
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define mp make_pair
#define S second
#define F first
ll mod=1e9+7 ;
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define input_from_file  freopen("input.txt", "r", stdin);
using namespace std::chrono; 
ll dp[(1<<21)+1];
int main()
{
  // input_from_file 
  ll n;cin>>n;
  // cout<<n;
  ll vec[n][n];
  memset(dp,0,sizeof(dp));dp[0]=1;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)  cin>>vec[i][j];
  }
  for(int i=0;i<(1<<n);i++){
    ll m=__builtin_popcount(i);
    for(int j=0;j<n;j++)  {
      if(vec[m][j]==1 && (i&(1<<j))==0){
        dp[i|(1<<j)]+=dp[i];
        dp[i|(1<<j)]%=mod;
      }
    }
  }
  cout<<dp[(1<<n)-1]%mod<<endl;
  return 0;
}

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

#define MAX 402

int n;
int m;

bool use[MAX];

vector<pair<int,int> > v[MAX];

queue<int> q;

int id[MAX];
int cur[100002];
int h[MAX];

int belong[MAX];
int siz[MAX];

inline int root(int b){
	if (belong[b] == -1){
		return b;
	}
	belong[b] = root(belong[b]);
	return belong[b];
}
void merge(int a, int b){
	a = root(a);
	b = root(b);
	if (a == b)return;
	belong[a] = b;
}

int ocp[MAX][MAX];


int main(){
	memset(belong, -1, sizeof(belong));
	cin >> n >> m;
	for (int i = 0; i < m; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		x--;
		y--;
		v[x].push_back(make_pair(y,i) );
		v[y].push_back(make_pair(x,i) );
		merge(x, y);
	}
	int ans = 0;
	int sum = 0;
	for (int i1 = 0; i1 < n; i1++){
		memset(use, false, sizeof(use));
		memset(id, 0, sizeof(id));
		memset(cur, -1, sizeof(cur));
		memset(h, -1, sizeof(h));
		use[i1] = true;
		q.push(i1);
		h[i1] = INT_MAX;
		bool ng = false;
		while (!q.empty()){
			int b = q.front();
			q.pop();
			for (int &i = id[b]; i < v[b].size() && v[b][i].second <= h[b]; i++){
				if (cur[v[b][i].second] == -1){
					cur[v[b][i].second] = 0;
					if (use[v[b][i].first]){
						ng = true;
						break;
					}
					use[v[b][i].first] = true;
					h[v[b][i].first] = v[b][i].second;
					q.push(v[b][i].first);
				}
			}
			if (ng){
				while (!q.empty())q.pop();
				break;
			}
		}
		if (!ng){
			for (int i = 0; i < n; i++){
				ocp[i1][i] = h[i];
			}
		}
		else{
			ocp[i1][0] = -2;
		}
		
	}
	for (int i = 0; i < n; i++){
		for (int j = i + 1; j < n; j++){
			bool ng = false;
			if (ocp[i][0] != -2 && ocp[j][0] != -2){
				if (ocp[i][j] == -1 && ocp[j][i] == -1){
					for (int k = 0; k < n; k++){
						if (k != i&&k != j&&ocp[i][k] >= 0 && ocp[j][k] >= 0 && ocp[i][k] != ocp[j][k]){
							ng = true;
							break;
						}
					}
					if (ng == false){
						ans++;
					}
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 3840
#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;
#define MAX 10
pair<string, string> M[MAX];
int n;
string source, target;

string getNext(string str, string s, string t ){
    int i = 0;
    while( i+s.size()-1< str.size() ){
	if ( str.substr(i, s.size() ) == s ){
	    str.replace(i, s.size(), t);
	    i += t.size();
	} else i++;
    }
    return str;
}

int bfs(){
    queue<string> Q;
    map<string, int> D;
    map<string, bool> V;
    Q.push(source);
    D[source] = 0; V[source] = true;
    string u, v, s, t;
    while(!Q.empty() ){
	u = Q.front(); Q.pop();
	if ( u == target ) return D[u];
	for ( int i = 0; i < n; i++ ){
	    s = M[i].first; t = M[i].second;
	    v = getNext(u, s, t);
	    if ( !V[v] && v.size() <= target.size()){
		D[v] = D[u] + 1;
		V[v] = true;
		Q.push(v);
	    }
	}
    }
    return -1;
}

main(){
    while ( cin >> n && n ){
	for ( int i = 0; i < n; i++ ) cin >> M[i].first >> M[i].second;
	cin >> source >> target;
	cout << bfs() << endl;
    }
}

Measured memory_bytes: 1256
#include <bits/stdc++.h>
					using namespace std;
					#define pll pair<ll,ll>
					typedef long long ll;
					#define mod 51123987
					#define fi first
					#define se second
					#define mp make_pair
					#define pb push_back
					#define INF 1e15
			
					
					int main()
					{
						string s;
						cin>>s;
						string down=s;
						string up;
						ll q;
						cin>>q;
						while(q)
						{
							q--;
							ll t1;
							cin>>t1;
							if(t1==2)
							{
								ll f1;
								cin>>f1;
								char ch;
								cin>>ch;
								if(f1==1)
								{
									
									up.pb(ch);
								}
								else
								{
									down.pb(ch);
								}
							}
							else
							{
								string t=up;
								up=down;
								down=t;
							}
							//cout<<up<<" "<<down<<endl;
						}
						reverse(up.begin(),up.end());
						cout<<up<<down;
					}


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

using namespace std;

#define LOG(...) fprintf(stderr, __VA_ARGS__)
//#define LOG(...)
#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 (int i = 0; i < (int)(n); ++i)
#define RREP(i, n) for (int i = (int)(n - 1); i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(a) ((int)(a).size())
#define BIT(x, i) (((x) >> (i)) & 1)
#define SQ(x) ((x) * (x))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int main() {
    int d, e;
    while (cin >> d >> e, d|e) {
        double mi = 10e9;
        REP(x, 101) {
            REP(y, 101) {
                if (x + y == d) {
                    mi = min(mi, abs(hypot(x, y) - e));
                }
            }
        }
        cout << mi << endl;
    }
}

Measured memory_bytes: 3232
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

/* Union-Find-Tree */
class Union_Find {
public:
  vector<long long> par;
  vector<long long> rnk;

  Union_Find (long long n) {
    // par.resize(n), rnk.resize(n);
    for (int i = 0; i < n; ++i) {
      par.pb(i);
      rnk.pb(0);
    }
  }

  // 木の根を求める
  int find(int x) {
    if (par[x] == x)
    return x;
    else
    return par[x] = find(par[x]);
  }

  // xとyの属する集合を併合
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (rnk[x] < rnk[y]) {
      par[x] = y;
    } else {
      par[y] = x;
      if (rnk[x] == rnk[y]) rnk[x]++;
    }
  }

  // xとyが同じ集合に属するか否か
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

int main() {
  int n,k,l; scanf("%d %d %d", &n, &k, &l);
  Union_Find road(n), train(n);
  rep(i,k) {
    ll p,q; scanf("%lld %lld", &p, &q);
    p--,q--;
    road.unite(p,q);
  }

  rep(i,l) {
    ll r,s; scanf("%lld %lld", &r, &s);
    r--,s--;
    train.unite(r,s);
  }

  map<pair<int,int>, int> com;
  vector<pair<int,int>> s(n);
  for (int i = 0; i < n; ++i) {
    s[i].first = road.find(i);
    s[i].second = train.find(i);
    com[s[i]]++;
  }

  rep(i,n) {
    cout << com[s[i]] << " ";
  } END;

}


Measured memory_bytes: 20196
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;

int main() {
    int a,b;
    cin>>a>>b;
    if(a>9 || b>9){
        cout<<"-1";
    }else{
        cout<<a*b;
    }
}

Measured memory_bytes: 256
import numpy as np

N=int(input())
A=np.ones(N)
a=np.ones(N)

A=map(int,input().rstrip().split())


a=sorted(A,reverse=True)

a_product=1
flag_1e18=False
flag_0=False

if a[N-1]==0:
  flag_0=True

for i in range(0,N,1):
  a_product=a_product*a[i]
  if a_product>1e18:
    flag_1e18=True
    break
  else:
    continue
    
if flag_1e18==True and flag_0==False:
  print(-1)
elif flag_0==True:
  print(0)
else:
  print(a_product)
  


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

money = 1000
kabu = 0

for i in range(N):
    if kabu == 0:
        flag = True
        for j in range(i+1, N):
            if A[i] > A[j]:
                flag = False
                break
            elif A[i] < A[j]:
                flag = True
                break
        else:
            flag = False
        if flag:
            buy = money // A[i]
            money -= buy * A[i]
            kabu += buy
    else:
        flag = True
        for j in range(i+1, N):
            if A[i] < A[j]:
                flag = False
                break
            elif A[i] > A[j]:
                flag = True
                break
        if flag:
            money += kabu * A[i]
            kabu = 0
    # print(money, kabu)

print(money)

Measured memory_bytes: 63208
#include<iostream>
#include<vector>

using namespace std;
#define int long long

const int INF=(1LL<<31)-1;
struct SegmentTree{

   static const int N=1<<17;
   vector<int> seg, lazy;
   SegmentTree(){
      seg.resize(2*N-1, INF);
      lazy.resize(2*N-1, -1);// -1:????????£???????????¨???????????¨
   }

   void setLazy(int i, int x){
      lazy[i]=x;
      seg[i]=x;
   }

   void refresh(int i, int l, int r){
      if(lazy[i]!=-1){
         /*
         seg[i]=lazy[i];
         if(r-l>1){
            lazy[2*i+1]=lazy[i];
            lazy[2*i+2]=lazy[i];
         }
         */
         setLazy(2*i+1, lazy[i]);
         setLazy(2*i+2, lazy[i]);
         lazy[i]=-1;
      }
   }

   void update(int a, int b, int x, int i=0, int l=0, int r=N){
      //refresh(i, l, r);
      if(b<=l or r<=a){
         return;
      }else if(a<=l and r<=b){
         setLazy(i, x);
         return;
      }else{
         refresh(i, l, r);
         int m=(r+l)/2;
         update(a, b, x, 2*i+1, l, m);
         update(a, b, x, 2*i+2, m, r);
         seg[i]=min(seg[2*i+1], seg[2*i+2]);
      }
   }

   int getmin(int a, int b, int i=0, int l=0, int r=N){
      //refresh(i, l, r);
      if(b<=l or r<=a){
         return INF;
      }else if(a<=l and r<=b){
         return seg[i];
      }else{
         refresh(i, l, r);
         int m=(r+l)/2;
         int vl=getmin(a, b, 2*i+1, l, m);
         int vr=getmin(a, b, 2*i+2, m, r);
         return min(vl, vr);
      }
   }

};

signed main(){

   int N, Q;
   cin>> N>> Q;
   SegmentTree st;
   while(Q--){
      int q; cin>> q;
      if(q==0){
         int s, t, x;
         cin>> s>> t>> x;
         st.update(s, t+1, x);
      }else{
         int s, t;
         cin>> s>> t;
         cout<< st.getmin(s, t+1)<< endl;
      }
   }

   return 0;
}

Measured memory_bytes: 7084
eval"N,*A="+`dd`.split*s=?,
b=A[N,N].reverse
puts N.times{|i|$*[v=A[i]]||=i;v!=b[i]||(s=v;$r=i)}<A.count(s)?:No:[:Yes,$r?(t=[s])*(k=[$*[s],b[..$r].count(s)].min)+(b-t)+t*=b.count(s)-k:b]

Measured memory_bytes: 89268
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <set>

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

using namespace std;
typedef long long int ll;
const int INF = 1000000000;
const double PI = 3.1415926535897932;
const ll MOD = 1000000007;

int main()
{
    string s, t;
    cin >> s >> t;

    int ans = 0;
    rep(i, 3) {
        if (s[i] == t[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 200005
#define MOD 998244353
#define INF 10000000000

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define piii pair<ll, pii>
#define ft first
#define sd second

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

ll a,  b, c, d;
ll x, y, X1, Y1, X2, Y2;

bool check(ll X, ll Y){
    if(X>= X1 && X <= X2 && Y >= Y1 && Y <= Y2) return true;
    return false;
}

void solve(){


ll n;
cin >> n;
cout << (n+1)/2;
}

int main()
{
    fast();
    int t= 1; //cin >> t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <set>
using namespace std;
int main(){
	int n;
    cin>>n;
    set<string> result;
    for(int i=0;i<n;i++){
    	string str;
      	cin >> str;
      	result.insert(str);
    }
  	cout << result.size() <<"\n";
    return 0;
}

Measured memory_bytes: 19228
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pair<int,int>>


int main(){
    ios::sync_with_stdio(0);
    int n , k, ans = 0;
    cin >> n >> k;
    while(n > 0){
        n /= k;
        ++ans;
    }
    cout << ans;
    return 0;
}


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

public class Main {

	public static void main(String[] args) {
		int N, count;
		count = 0;
		Scanner input = new Scanner(System.in);
		N = input.nextInt();
		ArrayList<Integer> arr = new ArrayList<Integer>();
		
		for (int i = 0; i < N; i++) {
			int temp = input.nextInt();
			if(!arr.contains(temp)) {
				arr.add(temp);
				count++;
			}
		}
		System.out.println(count);

	}

}


Measured memory_bytes: 21972
n,k=map(int,input().split())
a=[]
d=[]
for i in range(k):
  di=int(input())
  ai=list(map(int,input().split()))
  d.append(di)
  a.append(ai)
c=[0]*n
for i in range(k):
  for j in range(len(a[i])):
    c[a[i][j]-1]+=1
cnt=0
for i in range(n):
  if c[i]==0:
    cnt+=1
print(cnt)

Measured memory_bytes: 9148
/*
 * cpp_filepath
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> ostream & operator << (ostream & out, vector<T> const & v) {
  for (auto &&a: v) out << a << " "; out << endl; return out;
}
template <class T> void dump(T &a) { cout << a << endl; }
void solve();
int main() { solve(); return 0; }


void solve() {
  int a, b, c; cin >> a >> b >> c;
  if (a + b >= c) cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

using namespace std;

vector<int> num(1e5+5);

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

    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (num[i] == i) {
            int tmp = num[i];    num[i] = num[i+1];    num[i+1] = tmp;  ans += 1;
        }
    }

    if (num[n] == n) {
        int tmp = num[n];    num[n] = num[n-1];    num[n-1] = tmp;  ans += 1;
    }

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

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;

#define fill(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const int N = 1e5+10;

ll dp[N][110];
ll pref[N];
int a[N];

int main(){
fast;
int n,k;
cin>>n>>k;

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

for(int v=0;v<=k;v++)
pref[v]=1;

//dp[v][i]=dp[v][i-1]+...+dp[v-a[i]][i-1];
for(int i=1;i<=n;i++) {
    for(int v=0;v<=k;v++) {
        dp[v][i]=pref[v]%mod;
        if(v-a[i]-1>=0) {
            dp[v][i] = (dp[v][i]-pref[v-a[i]-1])%mod;
        }
        if(dp[v][i]<0)
        dp[v][i]+=mod;
    }

    pref[0]=dp[0][i];
    for(int v=1;v<=k;v++) {
        pref[v]=(pref[v-1]+dp[v][i])%mod;
    }
}

cout<<dp[k][n]<<endl;
return 0;
}

Measured memory_bytes: 90196
N = int(input())
zahyo = [list(map(int, input().split())) for _ in range(N)]

hantei = True
xtemp = 0
ytemp = 0
ttemp = 0
for i in range(N):
    t = abs(zahyo[i][0] - ttemp)
    x = abs(zahyo[i][1] - xtemp)
    y = abs(zahyo[i][2] - ytemp)
    ttemp = zahyo[i][0]
    xtemp = zahyo[i][1]
    ytemp = zahyo[i][2]

    if ((x + y - t) > 0) or ((x + y - t) % 2 != 0):
        hantei = False
        break

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


Measured memory_bytes: 27380
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string a,b,c;
    cin>>a>>b>>c;
    int p=a[0]-'a';
    int q=b[0]-'a';
    int r=c[0]-'a';
    char x=p+'A';
    char y=q+'A';
    char z=r+'A';
    cout<<x<<y<<z<<endl;
    return 0;
}


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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);  
	int n, m;
	cin >> n >> m;
	long long ans = m * 1900 + (n - m) * 100;
	cout << ans * pow(2, m) << endl;
	return 0;	
}


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

const long long INF = 1LL << 50;
long Lmax(long x, long y) {
	if (x > y)return x;
	return y;
}

int max(int x, int y) {
	if (x > y)return x;
	return y;
}

long Lmim(long x, long y) {
	if (x < y)return x;
	return y;
}

int mim(int x, int y) {
	if (x < y)return x;
	return y;
}

int abs(int x) {
	if (x < 0) {
		return -x;
	}
	return x;
}



int N, M,A;

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

	cout << (N*N) - A << endl;

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define max(a,b) a>b ?a : b;
#define min(a,b) a<b ?a : b;
#define abs(a) a>0 ?a : -a;
int main(void){
  char s[4];
  int i,n=0,m=0;
  scanf("%s",s);
  for(i=0;i<3;i++){
    if(s[i]=='R'){
      n++;
      if(m<n){
        m=n;
      }
    }else{
      n=0;
    }
  }
  printf("%d\n",m);
  return 0;
}


Measured memory_bytes: 1736
import bisect, numpy
N,M,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A=numpy.cumsum(A)
B=numpy.cumsum(B)
ans=bisect.bisect_right(B,K)
for i in range(N):
  if K-A[i]>=0:
    ans=max(ans,i+1+bisect.bisect_right(B,K-A[i]))
print(ans)

Measured memory_bytes: 58656
fun main (args:Array<String>){
    val a = readLine()!!.toInt()
    var num = 0L
    for (i in 1..a)  {
        if(i % 3 == 0){
            continue
        }
        if(i % 5 == 0){
            continue
        }
        num += i
    }
    print(num)
}


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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

template<class T> inline bool chmin(T& a, T b){
    if(a > b){
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

int main(){

    int n;
    cin >> n;
    string s;
    cin >> s;
    int w_max, r_max;
    w_max = r_max = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if(s[i] == 'W') w_max++;
        else if(s[i] == 'R') r_max++;
    }
    if((w_max == 0 && r_max != 0) ||
       (w_max != 0 && r_max == 0)){
           cout << 0 << endl;
           return 0;
    }
    int w, r;
    w = 0;
    r = r_max;
    int ans = INF;
    for(int i = 0; i < (int)s.size(); i++){
        if(s[i] == 'W') w++;
        else if(s[i] == 'R') r--;
        ans = min(ans, max(w,r));
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3720
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define mst(a) memset(a,0,sizeof a)
int main(){
	string a;
	while(cin>>a)
	if(a[2]==a[3]&&a[4]==a[5])
	 	puts("Yes");
	else puts("No");
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < (N); i++)
#define vec vector<int>
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    cout << (b - a) * (b - a + 1) / 2 - b << endl;
}

Measured memory_bytes: 256
/* ex3_2 Therefore
   pandacodeb */

#include <stdio.h>

int main(void){
  int N;
  scanf("%d", &N);
  int r = N % 10;       //calculate reminder to determine the last digit of N

  //check number of the last digit (r)
  switch(r){
    case 2: case 4: case 5: case 7: case 9:
      printf("hon\n");
      break;
    case 0: case 1: case 6: case 8:
      printf("pon\n");
      break;
    case 3:
      printf("bon\n");
      break;
    default: break;
  }
  return 0;
}

Measured memory_bytes: 1620
#include <bits/stdc++.h>
//#include <atcoder/math>
//using namespace atcoder;
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iostream>
#include <numeric>
#define rep(i,n) for (int i = 0;i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
int INF = 1e9;
ll  LINF = 1e18;

const int mod = 1000000007;
class mint {
	long long x;
public:
	mint(long long x=0) : x((x%mod+mod)%mod) {}
	mint operator-() const { 
	return mint(-x);
	}
	mint& operator+=(const mint& a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator-=(const mint& a) {
		if ((x += mod-a.x) >= mod) x -= mod;
		return *this;
	}
	mint& operator*=(const  mint& a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint& a) const {
		mint res(*this);
		return res+=a;
	}
	mint operator-(const mint& a) const {
		mint res(*this);
		return res-=a;
	}
	mint operator*(const mint& a) const {
		mint res(*this);
		return res*=a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t>>1);
		a *= a;
		if (t&1) a *= *this;
		return a;
	}
	// for prime mod
	mint inv() const {
		return pow(mod-2);
	}
	mint& operator/=(const mint& a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint& a) const {
		mint res(*this);
		return res/=a;
	}
	friend ostream& operator<<(ostream& os, const mint& m){
		os << m.x;
		return os;
	}
};

int main(){
	int n,m;cin >> n >> m;
	vector<mint> x(n),y(m);
	vector<pair<mint,mint>> xd(n/2),yd(m/2);
	rep(i,n) {
		int temp;
		cin >> temp;
		x[i] = mint(temp);
	}
	rep(i,m) {
		int temp;cin >> temp;
		y[i] = mint(temp);
	}
	rep(i,n/2){
		if(i == 0){
			xd[i] = make_pair(x[n-1-i],x[i]);
		}else{
			xd[i] = make_pair(xd[i-1].first+x[n-1-i],xd[i-1].second+x[i]);
		}
	}
	rep(i,m/2){
		if(i == 0){
			yd[i] = make_pair(y[m-1-i],y[i]);
		}else{
			yd[i] = make_pair(yd[i-1].first+y[m-1-i],yd[i-1].second+y[i]);
		}
	}
	mint xlen = 0,ylen = 0;
	rep(i,n/2){
		if(i < n/2-1 || (n%2) == 1) xlen += (xd[i].first-xd[i].second)*2;
		else xlen += xd[i].first - xd[i].second; 
	}
	rep(i,m/2){
		if(i < m/2-1 || (m%2) == 1) ylen += (yd[i].first - yd[i].second)*2;
		else ylen += yd[i].first - yd[i].second;
	}
	//cout << xlen << " " << ylen << endl;
	cout << ylen*xlen << endl;
}

Measured memory_bytes: 6384
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 4000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

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

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
    long long x;
public:
    mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD - 2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res /= a;
    }

    friend ostream& operator<<(ostream& os, const mint& m) {
        os << m.x;
        return os;
    }
};

//////////////////////////

mint frac[MAX];

void fracinit() {
    frac[0] = 1;
    repn(i, MAX - 1) {
        frac[i] = frac[i - 1] * i;
    }
}

mint com(ll n, ll m) {
    if (n < 0 || m < 0) { return 0; }
    if (n < m) { return 0; }
    return frac[n] / frac[m] / frac[n - m];
}

mint H(ll n, ll m) {
    return com(n + m - 1, n);
}

int main() {
    fracinit();
    ll N, M;
    cin >> N >> M;

    mint ans = H(3*M,N);

    for (ll s = 2 * M + 1; s <= 3 * M; s++) {
        ans -= H(3 * M - s, N - 1) * N;
    }

    for (ll s = M + 1; s <= N; s++) {
        if ((3*M - s) % 2 != 0) { continue; }
        ans -= H((3 * M - s) / 2, N) * com(N, s);
    }

    cout << ans;


	system("PAUSE");
}

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

using namespace std;

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int main() {
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      char c;
      cin >> c;
      if (i == j)
        cout << c;
    }
  }
  cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

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

  if((S[2] == S[3]) && (S[4] == S[5])){
    cout << "Yes" << endl;
  } else{
    cout << "No" << endl;
  }
  
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n):
    """answerのリストを更新してからdfsして、oldで戻す"""
    i = bisect_left(dp, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        i = bisect_left(dp, A[c])
        old = dp[i]
        dp[i] = A[c]
        dfs(c)
        dp[i] = old

dp = [INF] * (N+1)
dp[0] = A[1]
dfs(1)
for a in answer[1:]:
    print(a)


Measured memory_bytes: 226364
N,M=list(map(int,input().split()))
s=set();t=set();
for i in range(M):
  a,b=list(map(int,input().split()))
  if(a==1):
    s.add(b)
  if(b==N):
    t.add(a)
print("POSSIBLE"if s&t else"IMPOSSIBLE")

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

typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)
#define deb(x)     cout << #x << " = "<<x<<endl

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

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

int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 200005;


ll gcd(ll  a , ll b) {
	return (b == 0) ? a : gcd(b, a % b);
}
ll binpow(ll a, ll b) {
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
ll powmod(ll a, ll b, ll m) {
	a %= m;
	ll res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}
ll modinv(ll n, ll p)
{
	return powmod(n, MOD - 2, MOD);
}
void max_self(ll &a, ll b) {
	a = max(a, b);
}


int main(int argc, char const *argv[])
{
	// two magical lines to speed up IO
	cin.tie(0);
	ios_base::sync_with_stdio(false);
// #ifndef ONLINE_JUDGE
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// #endif
	int n;
	cin >> n;
	vector <double> dp(n + 1, 0);
	dp[0] = 1;
	F0R(i, n) {
		double p;
		cin >> p;
		for (int j = i + 1; j >= 0; j--) {
			dp[j] = (j > 0 ? dp[j - 1] * p : 0 ) + dp[j] * (1 - p);
		}


	}
	double ans = 0;
	for (int h = n / 2 + 1; h <= n; h++) {
		ans += dp[h];
	}
	cout << fixed << setprecision(17) << ans << endl;
	return 0;

}





Measured memory_bytes: 3788
from collections import defaultdict
import heapq

n,m=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(n)]

dic=defaultdict(list)
for a,b in ab:
    dic[a]+=[-b]

li=[]
ans=0
for i in range(1,m+1):
    if dic[i]:
        for j in dic[i]:
            heapq.heappush(li,j)
    if li:
        ans+=heapq.heappop(li)
print(-ans)

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

ans = 0
for i in range(1, N + 1):
    count = 0
    now = i
    while now < K:
        count += 1
        now *= 2
    # print (i, count)
    ans += pow(0.5, count)
    # print (ans)

ans /= N

print (ans)

Measured memory_bytes: 3060
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	num, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return num
}

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func getMin(x ...int) int {
	min := math.MaxInt64
	for i := 0; i < len(x); i++ {
		if x[i] < min {
			min = x[i]
		}
	}
	return min
}

func pow(x, pow int) int {
	ans := x
	for i := 1; i < pow; i++ {
		ans = ans * x
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

var rdr = bufio.NewReaderSize(os.Stdin, 10000000)

func readLine() string {
	buf := make([]byte, 0, 10000000)
	for {
		l, p, err := rdr.ReadLine()
		if err != nil {
			panic(err)
		}
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func main() {

	t := readLine()
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	for i := 0; i < len(t); i++ {
		if t[i] == '?' {
			fmt.Fprint(w, "D")
		} else {
			fmt.Fprintf(w, "%c", t[i])
		}
	}
	fmt.Fprintln(w, "")
}


Measured memory_bytes: 3128
open Printf open Scanf
module MyInt = struct let (+) = (+) let (-) = (-) let (/) = (/) let ( * ) = ( * ) let (mod) = (mod) let (%) = (mod) let (+=) r v = r := !r + v let (-=) r v = r := !r - v let ( *=) r v= r := !r * v let (/=) r v = r := !r / v end
module MyInt64 = struct
	let (+$) = (+) let (-$) = (-) let (/$) = (/) let ( *$) = ( * ) let (+) p q = Int64.add p q let (-) p q = Int64.sub p q let ( * ) p q = Int64.mul p q let (/) p q = Int64.div p q let (+=) r v = r := !r + v let (-=) r v = r := !r - v let ( *=) r v= r := !r * v let (/=) r v = r := !r / v let labs p = if p < 0L then -1L*p else p let (~|) p = Int64.to_int p let (~~|) p = Int64.of_int p let input_i64_array n = Array.init (~| n) (fun _ -> Scanf.scanf " %Ld" (fun v -> v)) let get_i64 _ = Scanf.scanf " %Ld" (fun v -> v) let get_2_i64 _ = Scanf.scanf " %Ld %Ld" (fun u v -> u,v) let get_3_i64 _ = Scanf.scanf " %Ld %Ld %Ld" (fun u v w -> u,v,w) let get_4_i64 _ = Scanf.scanf " %Ld %Ld %Ld %Ld" (fun u v w x -> u,v,w,x) let get_5_i64 _ = Scanf.scanf " %Ld %Ld %Ld %Ld %Ld" (fun u v w x y -> u,v,w,x,y) let print_i64_endline n = n |> Int64.to_string |> print_endline let (mod) m n = m - (m/n) * n let (%) = (mod) let rec gcd m n = match m,n with | m,0L -> m | m,n -> gcd n (m mod n) let lcm m n = (m*n) / gcd m n let rep from_ to_ fbod = let i,f = ref ~|from_,ref true in while !i <= ~|to_ && !f do match fbod ~~| !i with | `Break -> f := false | _ -> i := !i +$ 1; done let repb from_ to_ fbod = let i,f = ref ~|from_,ref true in while !i <= ~|to_ && !f do match fbod (~~| !i) with | `Break -> f := false | _ -> i := !i +$ 1 done; !f let repm from_ to_ m_init fbod = let i,f,m = ref ~|from_,ref true,ref m_init in while !i <= ~|to_ && !f do match fbod !m (~~| !i) with | `Break -> f := false | `Break_m m' -> (f := false; m := m') | `Ok m' -> (i := !i +$ 1; m := m') done; !m let repmb from_ to_ m_init fbod = let i,f,m = ref ~|from_,ref true,ref m_init in while !i <= ~|to_ && !f do match fbod (~~| !i) !m with | `Break -> f := false | `Break_m m' -> (f := false; m := m') | `Ok m' -> (i := !i +$ 1; m := m') done; (!m,!f) let string_of_list ?(separator=" ") f ls = let rec f0 a s = match a with | [] -> s | [h] -> s ^ (f h) ^ separator | h::t -> f0 t (s ^ (f h) ^ separator) in f0 ls "" let char_list_of_string str = let rec f0 i a = if i<0 then a else f0 (i-$1) (str.[i]::a) in f0 (String.length str -$ 1) [] let string_of_char_list ls = List.fold_left (fun u v -> u ^ (String.make 1 v)) "" ls
	let (@@@) = (@) let (@) a i = a.(~|i) let (<@) a (i,v) = a.(~|i) <- v
	let ceildiv m n = (m+n-1L) / n
end open MyInt64

let () =
	let a,b,c,x,y = get_5_i64 0 in
	repm 0L (max x y) Int64.max_int (fun u v ->
		let xr,yr = max 0L (x-v),max 0L (y-v) in
		`Ok (min u (2L*c*v + a*xr + b * yr))
	) |> printf "%Ld\n"

Measured memory_bytes: 2560
#include<stdio.h>

int main(void) {
	long long n, a, b;
	long long x, y;
	long long blue;
	scanf("%lld %lld %lld", &n, &a, &b);

	x = n / (a + b);
	y = n % (a + b);

	if (a > y) {
		blue = x * a + y;
		printf("%lld", blue);
	}
	else if (y >= a) {
		blue = (x + 1) * a;
		printf("%lld", blue);
	}
	else if (y == 0) {
		blue = x * a;
		printf("%lld", blue);
	}

	return 0;
}

Measured memory_bytes: 128
import java.io.*;

class Main {
    BufferedReader bf;
    PrintWriter writer;
    StringBuilder sb;
    static boolean local_system = false;

    void run() throws IOException {
        char d = bf.readLine().trim().charAt(0);
        writer.println(d>='A'&&d<='Z' ? 'A' : 'a');
    }

    public static void main(String[] args) throws IOException {
        long start_time = System.currentTimeMillis();
        Main obj = new Main();
        obj.run();
        long end_time = System.currentTimeMillis();
        if (local_system) obj.writer.println("Time : " + (end_time - start_time));
        obj.close();
    }

    public Main(){
        writer = new PrintWriter(System.out);
        bf = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
    }

    public int getInt() throws IOException {
        return Integer.parseInt(bf.readLine());
    }

    public long getLong() throws IOException {
        return Long.parseLong(bf.readLine());
    }

    public int[] ints() throws IOException {
        String[] data = bf.readLine().split(" ");
        int[] send = new int[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Integer.parseInt(data[i]);
        return send;
    }

    public long[] longs() throws IOException {
        String[] data = bf.readLine().split(" ");
        long[] send = new long[data.length];
        for (int i = 0, h = data.length; i < h; i++) send[i] = Long.parseLong(data[i]);
        return send;
    }

    public void close() throws IOException{
        writer.flush();
        writer.close();
        bf.close();
    }
}




Measured memory_bytes: 25480