akhauriyash/Code-Regression huggingface dataset:
import heapq
import sys


class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        return self.size[self.find[x]]


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    x, y, w = map(int, input().split())
    x -= 1
    y -= 1
    adj[x].append((y, w))
    adj[y].append((x, w))

dist = [0]*N


Un = UnionFind(N)
Q = [0]
while Q:
    current = Q.pop()
    for nex, wei in adj[current]:
        if Un.same(nex, current):
            continue
        else:
            Un.union(nex, current)
            dist[nex] = dist[current]+wei
            Q.append(nex)

dist = list(map(lambda x: x % 2, dist))
print("\n".join(map(str, dist)))


Measured memory_bytes: 46944
a=[]
for i in range(5):
  a.append(int(input()))
a=sorted(a,key=lambda x: -((x-1)%10))
c=0
for i in a[0:-1]:
  if i%10!=0:
    c+=(int(i/10)+1)*10
  else:
    c+=i
print(c+a[-1])

Measured memory_bytes: 3064
#include<stdio.h>
#include<math.h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define INFTY -1
//float inf=INFINITY;
int inf=(1<<21);
int n,a[MAX][MAX];

int prim(){
  int i,u,v,mincost,sum=0;
  int color[MAX],d[MAX],p[MAX];
  for(i=0;i<n;i++){
    d[i]=inf;
    p[i]=-1;
    color[i]=WHITE;
  }
  d[0]=0;
  while(1){
    mincost=inf;
    u=-1;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK && d[i]<mincost){	
	mincost=d[i];
	u=i;
      }
    }
    if(u==-1)break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK && a[u][v]!=inf){
	if(d[v]>a[u][v]){
	  d[v]=a[u][v];
	  p[v]=u;
	  color[v]=GRAY;
	}
      }
    }
  }
  for(i=0;i<n;i++){
    if(p[i]!=-1)sum+=a[i][p[i]];
  }
  return sum;
}

int main(){
  int i,j,e;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      if(e==-1)e=inf;
      a[i][j]=e;
    }
  }
  printf("%d\n",prim());
  return 0;
}



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

using namespace std;

int main(){
  int n, d, mn=12;
  map<int, int> mp;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> d;
    mn = min(mn, d);
    mp[d]++;
  }
  int mxl=0, mxr=0;
  for(auto p: mp){
    if(p.second==1){
      if(mxl<=mxr){
        mn = min(mn, p.first-mxl);
        mxl = p.first;
      }
      else{
        mn = min(mn, p.first-mxr);
        mxr = p.first;
      }
    }
    else if(p.second==2){
      mn = min({mn, p.first-mxl, p.first-mxr});
      mxl=p.first;
      mxr=p.first;
    }
    else{
      mn = 0;
    }
  }
  mn = min(mn, (12-mxl)+(12-mxr));
  cout << mn << endl;
}



Measured memory_bytes: 3616
#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 ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N=105;
int a[N];
int main()
{
  std::ios::sync_with_stdio(false);
  cin.tie(NULL) ; cout.tie(NULL) ;
  int n;
  cin>>n;
  rep(i,1,n+1) cin>>a[i];
  int ans=0;
  rep(i,1,n+1)
    {
      int j=i+1;
      while(j<=n && a[i]==a[j]) j++; j--;
      ans+=(j-i+1)/2;
      i=j;
    }
  cout<<ans<<endl;
  return 0 ;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<string>
#include<regex>
using namespace std;
int main () {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s,ans;
  cin >> s;
  regex re("A.*Z");
  smatch results;
  if (regex_search(s, results, re)){
    ans = results.str();
  }
  cout << ans.length() << endl;
}

Measured memory_bytes: 88212
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

int mp[3][3];

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


  REP(i, 3)REP(j, 3)cin >> mp[i][j];
  ll n;cin >> n;
  REP(_, n){
    ll a;cin >> a;
    REP(i, 3)REP(j, 3)if(a == mp[i][j])mp[i][j] = -1;
  }

  REP(i, 3){
    ll cou = 0;
    REP(j, 3)if(mp[i][j] == -1)cou++;
    if(cou == 3){cout << "Yes" << endl;return 0;}
  }
  REP(j, 3){
    ll cou = 0;
    REP(i, 3)if(mp[i][j] == -1)cou++;
    if(cou == 3){cout << "Yes" << endl;return 0;}
  }
  if(mp[0][0] == -1 && mp[1][1] == -1 && mp[2][2] == -1){cout << "Yes" << endl;return 0;}
  if(mp[2][0] == -1 && mp[1][1] == -1 && mp[0][2] == -1){cout << "Yes" << endl;return 0;}

  cout << "No" << endl;


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <unordered_map>
#include <queue>
#include <sstream>
#include <cstring>
#include <iomanip>

using namespace std;

typedef long long ll;

const ll INF=1e13+7;

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;}

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

int main(){
    double N,K,ans=0.0;
    int sum;
    cin>>N>>K;
    for(int i=1;i<=N;i++){
        sum=i;
        double probablity=1/N;
        while(sum<K){
            probablity*=0.5;
            sum*=2;
        }
        ans+=probablity;
    }
    cout<<setprecision(13)<<ans<<endl;
    return 0;
}

//a=97,z=122

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

using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const int INF = (1LL<<30);
#else
const ll INF = (1LL<<60);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

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); }

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

int a[100], b[100];
VI g[100];
bool used[105];

void dfs(int num) {
  used[num] = true;
  for(int i: g[num]) {
    if(!used[i]) dfs(i);
  }
}

signed main(void)
{
  int n, m;
  cin >> n >> m;
  REP(i, m) {
    cin >> a[i] >> b[i];
    a[i]--, b[i]--;
  }

  int ret = 0;
  REP(i, m) {
    REP(i, n) g[i].clear();
    REP(j, m) {
      if(i == j) continue;
      g[a[j]].PB(b[j]);
      g[b[j]].PB(a[j]);
    }
    memset(used, false, sizeof(used));
    dfs(0);
    bool flag = false;
    REP(j, n) if(!used[j]) flag = true;
    if(flag) {
      ret++;
    }
  }
  cout << ret << endl;

  return 0;
}


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

typedef double D;
typedef complex<D> P;
typedef pair<P, P> L;
typedef vector<P> VP;
const D EPS = 1e-9;
#define X real()
#define Y imag()
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

D dot(P a, P b) {
  return (conj(a)*b).X;
}

D cross(P a, P b) {
  return (conj(a)*b).Y;
}

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b,c) > EPS) return +1;
  if (cross(b,c) < -EPS) return -1;
  if (dot(b,c) < -EPS) return +2;
  if (norm(b) < norm(c)) return -2;
  return 0;
}

int main() {
  double x1, y1, x2, y2, x3, y3, xp, yp;
  while (cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> xp >> yp) {
    P a[3], p;
    a[0] = P(x1, y1);
    a[1] = P(x2, y2);
    a[2] = P(x3, y3);
    p = P(xp, yp);
    bool ok = true;
    for (int i = 0; i < 3; i++) {
      if (ccw(a[i], a[(i+1)%3], a[(i+2)%3]) != ccw(a[(i+1)%3], a[(i+2)%3], p)) {
	ok = false;
	break;
      }
    }
    if (ok) {
      std::cout << "YES" << std::endl;
    }else {
      std::cout << "NO" << std::endl;
    }
  }
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
using pi=pair<int,int>;
using vi=vc<int>;
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }
int SIZE(string s){ return (int)s.size(); }

int main(){
    cout << setprecision(20);
    ll n,m; cin >> n >> m;
    if(n != 1) n -= 2;
    if(m != 1) m -= 2;
    cout << n*m << endl;
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define endl                         '\n'	
#define Ceil(x,y)             ((x+y-1)/y)
#define sz(s)               (int)s.size()
#define RT(x)           return cout<<x,0;
#define mem(x,y)    memset(x,y,sizeof(x))
#define all(v) ((v).begin()), ((v).end())
#define vi                    vector<int>
#define fr(x,y) for(int x=0; x<(y); ++x)
#define fr2(x,z,y) for(int x=z; x<(y); ++x)
#define Rabee_Adel          file();
const double PI = acos(-1), EPS = 1e-7;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dr[] { -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[] { 0, 1, 1, 1, 0, -1, -1, -1 };
ll gcd(ll x, ll y) { return (!y) ? x : gcd(y, x%y); }
ll lcm(ll x, ll y) { return ((x / gcd(x, y))*y); }
ll mod = 998244353;
ll power(ll x, ll y){if (y == 0)return 1;if (y == 1)return x;ll r = power(x, y / 2) % mod;return r%mod*r%mod*power(x, y % 2) % mod;}
void file() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif  !ONLINEJUDGE
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

}
int main()
{
	
	Rabee_Adel
		ll a, b, c, d; cin >> a >>b >> c >> d;
	int f = 0;
	while (1)
	{
		if (f == 1)
		{
			if (c == 0){
				cout << "Yes";
				break;
			}
			if (a >= d) a -= d;
			else {
				cout << "No";
				break;
			}
			f = 0;
		}
		else
		{
			if (a == 0){
				cout << "No";
				break;
			}
			if (c >= b)c-= b;
			else {
				cout << "Yes";
				break;
			} 
			f = 1;
		}


	}
	
	
		
}

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

int main() {
  int N,K;
  cin >> N >> K ;
  vector<int> l(N);
  for(int i=0;i<N;i++){
    cin >> l.at(i);
  }
  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());
  int result = 0;
  for(int i=0;i<K;i++){
    result += l.at(i);
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
//0018 Sorting Five Numbers
//®a,b,c,d,eªüÍ³ê½Æ«A~É®ñµÄoÍ·évOðì¬¹æ

//±ñÈsort()Ä×ÎIíéæ¤ÈâèAVÎÈ¢Æ¹¶áÈ¢

#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;

int main(void)
{
	const int N = 5;
	int a[N];
	int i;

	//µå¤ªÈ¢©çÉÊÉ
	for(i = 0; i < N; i++)
		cin >> a[i];
	sort(a, a+N, greater<int>());
	for(i = 0; i < N; i++)
		(i ? cout<<' '<<a[i] : cout<<a[i]);
	cout << endl;

	/*
	//±êAVC++¾ÆRpCÅ«éÌÉñoµ½çRpCG[HçÁ½
	//[JNXÍn¹È¢ñ¾Á¯
	struct X
	{
		int operator()(int) { int a;cin >> a;return a;}
	};
	struct Y
	{
		int n;
		Y():n(0){}
		void operator()(int a) { (n++?cout<<' '<<a:cout<<a);}
	};
	transform(a, a+N, a, X());
	sort(a, a+N, greater<int>());
	for_each(a, a+N, Y());
	cout << endl;
	*/

	/*
	//±ê¾ÆAüÍÉEOFªKvÅAoÍÉXy[Xª½­ÈÁÄµÜ¤
	copy(istream_iterator<int>(cin), istream_iterator<int>(), a);
	sort(a, a+N, greater<int>());
	copy(a, a+N, ostream_iterator<int>(cout, " "));
	*/
	return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int ans = 0;
		if (m % n == 0) {
			ans = m / n;
		} else {
			int tmp = m / n;
			while (true) {
				if ((m - tmp * n) % tmp == 0) {
					break;
				} else {
					tmp--;
				}
			}
			ans = tmp;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 23636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define zero_pad(num) setfill('0') << std::right << setw(num)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n)cin >> a[i];
    ll ans = 0;
    int r = 0;
    int x = a[0];
    int sum = a[0];
    for(int l = 0; l < n; l++){
        if(r < n){
            while(x == sum){
                r++;
                if(r == n)break;
                x ^= a[r];
                sum += a[r];
            }
        }
        ans += r - l;
        x ^= a[l];
        sum -= a[l];
    }
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
#include <stack>
#include <cstdlib>
using namespace std;

int pop(stack<int> &s){
  int x = s.top();
  s.pop();
  return x;
}

int main(){
  stack<int> st;
  string c;
  while(cin >> c){
    int m, n;
    if(c == "+"){
      n = pop(st);
      m = pop(st);
      st.push(m+n);
    }
    else if (c == "-"){
      n = pop(st);
      m = pop(st);
      st.push(m-n);
    }
    else if (c == "*"){
      n = pop(st);
      m = pop(st);
      st.push(m*n);
    }
    else
      st.push(atoi(c.c_str()));
  }
  cout << st.top() << endl;
}



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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    while(true){
        ll n,w,d;
        cin >> n >> w >> d;
        if(n == 0 && w == 0 & d == 0){
            break;
        }
        vector<ll> p(n);
        vector<ll> s(n);
        for(i = 0;i < n;++i){
            cin >> p.at(i) >> s.at(i);
        }
        vector<pair<ll,ll>> youso;
        youso.emplace_back(w,d);
        for(i = 0;i < n;++i){
            pair<ll,ll> tmp = youso.at(p.at(i)-1);
            youso.erase(youso.begin() + p.at(i)-1);
            ll tw = tmp.first;
            ll td = tmp.second;
            s.at(i) %= (tw+td)*2;
            ll ti,tj,tk,tl;
            if(s.at(i) < tw){
                ti = s.at(i);   tj = td;    tk = tw - s.at(i);  tl = td;
            }else if(s.at(i) < tw + td){
                ti = tw;   tj = s.at(i) - tw;    tk = tw;  tl = td - tj;
            }else if(s.at(i) < tw + td + tw){
                ti = s.at(i) - tw - td;   tj = td;    tk = tw - ti;  tl = td;
            }else{
                ti = tw;   tj = s.at(i) - tw - td - tw;    tk = tw;  tl = td - tj;
            }
            if(ti*tj > tk*tl){
                swap(ti,tk);    swap(tj,tl);
            }
            youso.emplace_back(ti, tj);
            youso.emplace_back(tk, tl);
        }
        vector<ll> ans;
        for(i = 0;i < youso.size();++i){
            ans.push_back(youso.at(i).first*youso.at(i).second);
        }
        sort(all(ans));
        for(i = 0;i < ans.size()-1;++i){
            cout << ans.at(i) << " ";
        }
        cout << ans.at(i) << endl;
    }
    return 0;
}


Measured memory_bytes: 3160
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

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

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		MainLoop : while(true){
			int w = Integer.parseInt(scan.next());
			int h = Integer.parseInt(scan.next());
			if(w==0) break;
			byte[][] map = new byte[h][w];

			int sx = Integer.parseInt(scan.next())-1;
			int sy = Integer.parseInt(scan.next())-1;
			int gx = Integer.parseInt(scan.next())-1;
			int gy = Integer.parseInt(scan.next())-1;
			int n = Integer.parseInt(scan.next());
			for (int i = 0; i < n; i++) {
				byte c = scan.nextByte();
				int d = Integer.parseInt(scan.next());
				int x = Integer.parseInt(scan.next())-1;
				int y = Integer.parseInt(scan.next())-1;
				for (int j = 0; j < (d==0 ? 2 : 4) ; j++)
					for (int j2 = 0; j2 < (d==0 ? 4 : 2) ; j2++)
						map[j+y][j2+x] = c;

			}

			if(map[sy][sx]==0){
				out.println("NG");
				continue;
			}
			int color = map[sy][sx];
			LinkedList<int[]> que = new LinkedList<int[]>();
			que.offer(new int[]{sx,sy});

			while(!que.isEmpty()){
				int[] pos = que.poll();
				map[pos[1]][pos[0]]=0;
				if(pos[0]==gx && pos[1]==gy){
					out.println("OK");
					continue MainLoop;
				}

				for (int i = 0; i < 4; i++) {
					int nx = pos[0]+dx[i],ny = pos[1]+dy[i];
					if(nx>=0 && nx<w && ny>=0 && ny<h && color==map[ny][nx])
						que.offer(new int[]{nx,ny});
				}
			}
			out.println("NG");
		}

		out.flush();
	}
}

Measured memory_bytes: 44364
#include <iostream>
using namespace std;
int main () {
	int h, w, k;
	cin >> h >> w >> k;
	char grid[h][w];
	for (int i=0; i<h; i++) {
		for (int j=0; j<w; j++) {
			cin >> grid[i][j];
		}
	}
	int ans = 0;
	for (int i=0; i<(1<<h); i++) {
		for (int j=0; j<(1<<w); j++) {
			int cnt = 0;
			for (int x=0; x<h; x++) {
				for (int y=0; y<w; y++) {
					if ((i & (1<<x)) || (j & (1<<y))) continue;
					if (grid[x][y] == '#') cnt++;
				}
			}
			if (cnt == k) ans++;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3608
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>  
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <bitset>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
const double PI=acos(-1.0);

typedef long long Int;
typedef long long LL;
typedef unsigned long long UINT;
typedef vector <int> VI;
typedef pair <int, int> PII;
typedef pair <double, double> PDD;

const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 1007;
const int MAX1 = 2007;
const int MAX2 = 24000000;
const int LEN = 21;
const int BASE = 1000000000;

int n, m;
char A[MAX][MAX];
int R[MAX][MAX];

int main()
{
  cin >> n >> m;
  FOR (i,0,n)
    scanf("%s", A[i]);

  
  R[0][0] = (A[0][0] == '#' ? 1 : 0);
  FOR (i,0,n)
    FOR (j,0,m)
    {
      if (i == 0 && j == 0) continue;
      R[i][j] = INF;
      if (i > 0)
      {
        R[i][j] = min(R[i][j], R[i-1][j] + (A[i-1][j] == '.' && A[i][j] == '#'));
      }
      if (j > 0)
      {
        R[i][j] = min(R[i][j], R[i][j-1] + (A[i][j-1] == '.' && A[i][j] == '#'));
      }
    } 

  cout << R[n-1][m-1] << endl;

  
  return 0;
}


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

using namespace std;

typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int mi=0, mx=0;
  map<int, int> mp;
  for(int i=0; i<n; i++){
    int x;
    cin >> x;
    if(x / 400 < 8)
      mp[x / 400]++;
    else
      mx++;
  }
  int sum = 0;
  for(int i=0; i<8; i++){
    if(mp[i]) sum++;
  }
  if(sum){
    mi = sum;
    mx = mi + mx;
  }else{
    mi = 1;
    mx = mx;
  }
  cout << mi << " " << mx << endl;
  return 0;
}


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

int main(void){
    int ans=0;
    int N; cin >> N;

    for(int i=0; i<N; i++){
        int a,b; cin >> a >> b;
        ans+=b-a+1;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include<cstdio>
const int N=5*1e5+10;
char s[N];
int a[N],n,m,L[N],R[N],l,x,y,ans;
int ma(int a,int b){return a>b?a:b;}
int main()
{
	scanf("%d%d%s",&n,&m,s);
	for(int i=1;i<=n;i++)a[i]=s[i-1]-'0';
	for(int i=1;i<=n;i++)
		if(a[i]==0)
		{
			L[++l]=i;
			for(;i<=n;i++)if(a[i])break;
			i--;
			R[l]=i;
		}
	for(int i=1;i+m-1<=l;i++)
	{
		x=L[i]-1;
		y=R[i+m-1]+1;
		while(a[x])x--;
		while(a[y])y++;
		ans=ma(ans,y-x-1);
	}
	if(m>=l)ans=n;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}


int n,q;
vector<ll> a;

void solve(){
  ll x; cin >>x;
  ll sum = 0;
  ll res = 0;
  int right = 0;
  rep(left, n){
    while (right < n && sum + a[right] <= x){
      sum += a[right]; right++;
    }
    res += right - left;
    if (left == right) right++;
    else sum -= a[left];
  }
  cout <<res <<endl;
}

int main() {
  cin >>n >>q;
  a.assign(n, 0); rep(i, n) cin >>a.at(i);
  rep(i, q) solve();
}


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

typedef long long ll;
typedef vector<int> vi;
#define PB push_back
#define MP make_pair
#define endl '\n'
#define all(a) (a).begin(),(a).end()
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n;
int arr[100005];
int dp[100005];

int f(int indx)
{
    if(indx>=n-1)
        return 0;

    if(dp[indx]!=-1)
        return dp[indx];
    if(indx+1 <=n-1 && indx+2 <=n-1)
           return dp[indx]=min(abs(arr[indx]-arr[indx+1])+f(indx+1), abs( arr[indx]-arr[indx+2])+f(indx+2));
    else if(indx+1 <= n-1)
        return dp[indx]=abs( arr[indx]-arr[indx+1])+f(indx+1);
}

int main()
{
    optimize();
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>arr[i];
    memset(dp,-1,sizeof(dp));
    cout<<f(0)<<endl;
    return 0;
}


Measured memory_bytes: 7564
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i, s, n) for (int i = (s); i < (n); ++i)
#define rrep(i, n, g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(x) (int)(x).size()
#define dup(x, y) (((x) + (y)-1) / (y))
#define pb push_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int n;
  bool flag = true;
  cin >> n;
  rep(i, 0, n) {
    int a;
    cin >> a;
    if (a % 2 == 0) {
      if (a % 3 != 0 && a % 5 != 0) {
        cout << "DENIED" << endl;
        flag = false;
        break;
      }
    }
  }
  if (flag) cout << "APPROVED" << endl;
  return 0;
}

Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace ConsoleApplication2
{
    class Program
    {


        static void Main(string[] args)
        {

            long n = int.Parse(Console.ReadLine());
            long[] a = new long[n];
            List<long> color = new List<long>();
            for (int i = 0; i < n; i++)
            {
                a[i] = int.Parse(Console.ReadLine());
            }
            
            //colorは昇順だとinsertが遅いので降順にする
            color.Add(a[0]);

            for (int i = 1; i < n; i++)
            {
                int cnt = color.Count;
                if (a[i] <= color[cnt - 1])
                {
                    color.Add(a[i]);
                }
                else if (a[i] > color[0])
                {
                    color[0] = a[i];
                }
                else
                {
                    //2分探査
                    int iS, iM, iL;
                    iS = cnt - 1;// 最小値なのでこれにかぶせる可能性はある
                    iL = 0;// 最大値なのでこれにかぶせる可能性はない


                    for (int j = 0; j < cnt; j++)
                    {
                        iM = (iS + iL+1) / 2;

                        if (iS == iM)
                        {
                            color[iS] = a[i];
                            break;
                        }
                        if (color[iM] >= a[i])
                        {
                            iL = iM;
                        }
                        else
                        {
                            iS = iM;
                        }
                    }
                }
            }




                Console.WriteLine(color.Count);

            
        }
    }
}

Measured memory_bytes: 18908
def PrintI(i):
    print(" ", i)
    return i + 1
 
if __name__ == "__main__":
    n = input()
    n = int(n)
    s = ""
    for i in range(1, n + 1):
        if i % 3 == 0:
            s += " " + str(i)
        elif "3" in str(i):
            s += " " + str(i)
    print(s)

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

signed main() {
  int N,M;
  cin >> N >> M;
  priority_queue<int> A;
  for(int i=0; i<N; i++) {int a; cin >> a; A.push(a);}
  for(int i=0; i<M; i++) {
    int kakaku = A.top();
    A.pop();
    A.push(kakaku/2);
  }
  int sum = 0;
  while(A.size()) {
    sum += A.top();
    A.pop();
  }
  cout << sum << endl;
}

Measured memory_bytes: 1400
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;



int main(){
    ll n;
    cin>>n;
    ll ans=E;
    ll sum=0;
    for(int i=1;i<=n;i++){
        ll a;
        cin>>a;
        sum+=a;
        ans=min(ans,sum/i);
    }
    cout<<ans<<endl;
    
    
    
    return 0;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647
#define dset(n) cout << fixed << setprecision(n)

void yes() {
  cout << "Yes";
}

void no() {
  cout << "No";
}

int main() {
  kyun;
  in6 n;
  cin >> n;
  vi data(n);
  rep(i,n) cin >> data[i];
  in6 ans = 0;
  in6 here = data[0];
  in6 check = 0;
  in6 count = 0;
  repa(i,1,n) {
    if(here >= data[i]) {
      count++;
      here = data[i];
      check++;
      ans = max(ans,count);
    }
    else {
      ans = max(count,ans);
      here = data[i];
      count = 0;
    }
  }
  if(check == n-1) ans = n-1;
  cout << ans;
  hinata;
}

Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i <(int)(n); i++)
 
int main(){
int N, ans;
  ans=0;
  cin >> N;
  vector<int> vec(N);
  rep(i,N)
    cin >> vec.at(i);
  sort(vec.begin(), vec.end());
  rep(i,N-1){
    if(vec.at(i) < vec.at(i+1))
      ans++;
  }
  cout << ans+1 << endl;
}

Measured memory_bytes: 256
import collections
import math

N,M=map(int,input().split())

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

AmodM=[]
leftsummodM=[]
#rightsummodM=[]
#summodM=0
answer=0

for i in range(N):
  AmodM.append(A[i]%M)



leftmodcount=0
#rightmodcount=0
for i in range(N):
  leftmodcount+=AmodM[i]
  #rightmodcount+=AmodM[N-i-1]
  leftsummodM.append((leftmodcount)%M)
  #rightsummodM.append(rightmodcount)
  '''
  if leftmodcount%M==0:
    answer+=1
  if i!=N-1 and rightmodcount%M==0:
    answer+=1
  '''
count=collections.Counter(leftsummodM)

#print(count)

#0に関しては1個でも選べるので1個分多くカウントする
for k,v in count.items():
  if k==0:
    answer+=v*(v+1)//2
  else:
    answer+=(v-1)*v//2

print(answer)    

Measured memory_bytes: 17324
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define MAX (100000)
#define pii pair<int, int>

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

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
ll mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  ll tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

ll comb(ll n, ll r){
	ll res = 1;
  rep(i, 0, r){
    res *= n - i;
    res /= i + 1;
  }
  return res;
}

template<typename T>
T euclid(T a, T b){
  if(b == 0) return a;
  else return euclid(b, a % b);
}

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

void Main() {
  ll N, M; cin >> N >> M;
  string S, T; cin >> S >> T;
  ll L = (N * M) / euclid(N, M);
  ll l = ((L / N) * (L / M)) / euclid((L / N), (L / M));
  rep(i, 0, L / l){
    if(S[(l * i) / (L / N)] != T[(l * i) / (L / M)]) L = -1;
  }
  cout << L << endl;
}

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

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 640
X = int(input())

beki = []
for i in range(1,32):
    beki.append(i**2)
for i in range(1,11):
    beki.append(i**3)
for i in range(1,6):
    beki.append(i**4)
for i in range(1,4):
    beki.append(i**5)
for j in range(6,10):
    beki.append(2**j)
    
beki = sorted(beki, reverse=True)
for a in beki:
    if a <= X:
        print(a)
        break

Measured memory_bytes: 3064
#include<iostream>
#include<stdio.h>
using namespace std;

int main() {
	int n;
	while (cin >> n&&n) {
		int** magic_square = new int*[n];
		for (int i = 0; i < n; i++) {
			magic_square[i] = new int[n];
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				magic_square[i][j] = 0;
			}
		}
		magic_square[n / 2 + 1][n / 2] = 1;
		int in_x = n / 2, in_y = n / 2 + 1; int next_num = 2; int in_cnt = 1;
		while (1) {
			if (in_cnt == n*n)break;
			while (1) {
				bool in = false;
				in_x += 1; in_y += 1;
				one_more:
				if (in_x >= n)in_x = 0;
				if (in_y >= n)in_y = 0;
				if (!magic_square[in_y][in_x]) { 
					magic_square[in_y][in_x] = next_num;
					next_num++;
					in = true;
					in_cnt++;
				}
				else {
					in_x -= 1; in_y += 1;
					if (in_x < 0)in_x = n - 1;
					goto one_more;
				}
				if (in)break;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				printf("%4d", magic_square[i][j]);
			}
			cout << endl;
		}
	}
}


Measured memory_bytes: 3152
#include<iostream>
#include<string>
using namespace std;
main(){
  int f,i,m;
  string s;
  for(cin>>f;cin>>s;f?puts(f-2?"A":"B"):puts("NA")){
    f=0;
    for(i=1;s[0]+s[1]==101 & (m=s.find(35))!=string::npos & s[m-i]==s[m+i];)
      m-++i-1 | m+i-s.size()+1 | s[m+i]-'~'||(f=1);
    for(i=2;s[0]+s[1]==156 & s[i]==81 & s[i+1]==61;)
      ++++i-s.size()+2 | s[i]+s[i+1]-252 || (f=2);
  }
}

Measured memory_bytes: 0
#include <iostream>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

int main()
{
	const set<char> ACGT{ 'A', 'C', 'G', 'T' };

	string S;
	cin >> S;

	int ans = 0;
	int tmp = 0;
	for (auto c : S) {
		if (ACGT.count(c)) {
			++tmp;
			ans = max(ans, tmp);
		}
		else {
			tmp = 0;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
a,b,c,d = map(int,input().split())
x = c-a
y = d-b
print('U'*y + 'R'*x + 'D'*y + 'L'*x + 'L' + 'U'*(1+y) + 'R'*(1+x) + 'D' + 'R' + 'D'*(1+y) + 'L'*(1+x) + 'U')


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

signed main() {

  int A, B, C, K;
  cin >> A >> B >> C >> K;

  int max;
  if(K <= A){
    max = K;
  }else if(K <= A + B){
    max = A;
  }else{
    max = A - (K - (A + B));
  }
  cout << max << endl;
}


Measured memory_bytes: 3624
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <cstring>
#include <map> 
#include <set>
#include <queue>
#include <iomanip>

typedef long long ll;

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

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

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h,n, w,m,t; string s;
ll R, C;
ll sy, sx, gy, gx;
char maze[110][110];
ll dis[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);
}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j])%ma;
		}
	}
}

ll GetDigit(ll num) {
	return log10(num) + 1;
}
ll Combination(int n, int r)
{
	if (n - r < r) r = n - r;
	if (r == 0) return 1;
	if (r == 1) return n;

	vector<ll> numerator(r);
	vector<ll> denominator(r);

	for (int k = 0; k < r; k++)
	{
		numerator[k] = n - r + k + 1;
		denominator[k] = k + 1;
	}

	for (int p = 2; p <= r; p++)
	{
		int pivot = denominator[p - 1];
		if (pivot > 1)
		{
			int offset = (n - r) % p;
			for (int k = p - 1; k < r; k += p)
			{
				numerator[k - offset] /= pivot;
				denominator[k] /= pivot;
			}
		}
	}

	ll result = 1;
	for (int k = 0; k < r; k++)
	{
		if (numerator[k] > 1) result *= numerator[k];
		result %= ma;
	}

	return result;
}

ll bfs() {
	queue<P> que;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) dis[i][j] = INF;
	}
	que.push(P(sy - 1, sx - 1));
	dis[sy - 1][sx - 1] = 0;

	while (que.size() > 0) {
		P p = que.front();
		que.pop();
		if (p.first == gy - 1 && p.second == gx - 1) break;
		for (ll i = 0; i < 4; i++) {
			ll ny = p.first + dy[i];
			ll nx = p.second + dx[i];
			if (0 <= ny && ny < R && 0 <= nx && nx < C && maze[ny][nx] == '.' && dis[ny][nx] == INF) {
				que.push(P(ny, nx));
				dis[ny][nx] = dis[p.first][p.second] + 1;
			}
		}
	}
	return dis[gy - 1][gx - 1];
}


int main() {
	ll x;
	cin >> x;
	
	for (ll i = 0;; i++) {
		if (i * (i + 1) / 2 >= x) {
			cout << i << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;cin>>n;
  int a[n];
  int b[3]={0,0,0};
  for(int i=0;i<n;i++){
    cin>>a[i];
    if(a[i]%2==1) b[0]++;
    if(a[i]%4==0) b[2]++;
    if(a[i]%4!=0&&a[i]%2==0) b[1]++;
  }
  string s;
  if(b[1]==0){
    if(b[0]<=b[2]+1) s="Yes";
    else s="No";
  }
  else{
    if(b[0]<=b[2]) s="Yes";
    else s="No";
  }
  cout<<s<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &&x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define INSEG(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v))os<<*i<<(i==end(v)-1?"":"\n");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void PSUM(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(0); ios::sync_with_stdio(false);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int>> g(N);
    vector<int> deg(N);
    REP(i, N - 1 + M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        deg[b]++;
    }
    auto tmp = deg;
    vector<int> par(N);
    stack<int> st;
    REP(i, N) if (deg[i] == 0) st.push(i);
    vector<int> sorted;
    while (!st.empty()) {
        int v = st.top(); st.pop();
        sorted.push_back(v);
        FORE(w, g[v]) {
            deg[w]--;
            if (deg[w] == 0) {
                st.push(w);
            }
        }
    }
    deg = tmp;
    REP(i, N) {
        int v = sorted[i];
        FORE(w, g[v]) {
            deg[w]--;
            if (deg[w] == 0) {
                par[w] = v + 1;
            }
        }
    }
    cout << par << endl;
    return (0^_^0);
}



Measured memory_bytes: 9588
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define ld long double
#define fast ios_base::sync_with_stdio(false) ;cin.tie(NULL);cout.tie(NULL)
#define F(i,a,b) for(int i= (int)(a); i<(int)(b);i++)
#define FI(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define RF(i,a,b) for(int i = (int)(a); i >= (int)(b); i--)
#define what_is(x) cerr << #x << " is " << x << endl;
#define ms(x,a) memset(x,(int)(a),sizeof(x))
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pii pair<int,int>
#define vi vector<int >
#define pb push_back
#define endl '\n'
#define mp make_pair
#define ff first
#define ss second
#define MOD 1000000007
const int N = 1e6+7 ;
string s ;
int n,a,b,c ;
int l[8] ;
const int INF = 1e9 + 7 ;
int dfs(int d, int x , int y , int z){
	if(d == n){
		if(min({x,y,z}))
			return (abs(x-a)+abs(y-b)+abs(z-c)) - 30 ;
		else return INF ;
	}
	int no = dfs(d+1,x,y,z) ;
	int phla = dfs(d+1,x+l[d],y,z) + 10 ;
	int dusra = dfs(d+1,x,y+l[d],z) + 10 ;
	int tsra = dfs(d+1,x,y,z+l[d]) + 10 ;
	return min({no,phla,dusra,tsra}) ;

}

int main(){fast ;
	cin >> n >> a >> b >> c ;
	for(int i = 0 ; i < n ; i++)
		cin >> l[i] ;
	
	cout << dfs(0,0,0,0) ;	
}


Measured memory_bytes: 256
n = int(input())
heights = list(map(int,input().split()))
ans = 0

for i in range(1,101):
    c = 0
    for j in range(1,n):
        if heights[j-1] >= i and heights[j] < i:
            c += 1
        else:
            continue
    if heights[-1] >= i:
        c += 1
    ans += c
    
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 100000001
#define dmp make_pair
#define dpb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int a[201], b[201][3];
pair<int,int> dp[201][2];
int main(){
	int d, n, ans = 0;
	scanf("%d%d", &d, &n);
	rrep(i,d)scanf("%d", &a[i]);
	rrep(i,n)scanf("%d%d%d", &b[i][0], &b[i][1], &b[i][2]);
	int t1, t2;
	for(int i = 1;i <= d;i++){
		t1 = INF;t2 = 0;
		for(int j = 1;j <= n;j++){
			if(b[j][0] <= a[i] && a[i] <= b[j][1]){
				t1 = min(t1, b[j][2]);
				t2 = max(t2, b[j][2]);
			}
		}
		dp[i][0].se = t1;
		dp[i][1].se = t2;
		dp[i][0].fi = dp[i-1][1].fi + abs(dp[i-1][1].se-t1);
		dp[i][0].fi = max(dp[i][0].fi, dp[i-1][0].fi + abs(dp[i-1][0].se-t1));
		dp[i][1].fi = dp[i-1][0].fi + abs(t2-dp[i-1][0].se);
		dp[i][1].fi = max(dp[i][1].fi, dp[i-1][1].fi + abs(t2-dp[i-1][1].se));
		if(i == 1){
			dp[i][0].fi = 0;
			dp[i][1].fi = 0;
		}
	}
	t1 = dp[d][0].fi;
	t2 = dp[d][1].fi;
	ans = max(t1, t2);
	printf("%d\n", ans);
	return 0;
}

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

int main(){
  int n,m;
  cin >>n >>m;
  int a[m], b[m];
  rep(i,m) cin >>a[i] >>b[i];
  int num[55] = {0};
  rep(i,m){
    num[a[i]]++;
    num[b[i]]++;
  }
  for(int i = 1; i <= n; i++){
    cout << num[i] << endl;
  }
  return 0;
}

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

using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repd(i,0,n)
typedef long long ll;


int main(){
  int n, x;
  cin >> n >> x;
  vector<int> a(n, 0);
  rep(i, n){
    cin >> a[i];
  }
  sort(a.begin(), a.end());
  int ans = 0;
  rep(i, n-1){
    if(x < a[i]) break;
    x -= a[i];
    ans++;
  }
  if(x == a[n-1]){
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
(N,K) = map(int,input().split())
man_list = []
for i in range(K):
    D = int(input())
    man_ele = list(map(int,input().split()))
    for j in man_ele:
        man_list.append(j)

man_list = list(set(man_list))
count = 0
for i in range(1,N+1):
    if i  not in man_list:
        count += 1
print(count)
    

Measured memory_bytes: 9212
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int h[100100];
  for(int i=0; i<n; i++){
    cin >> h[i];
  }
  int pre = -99;
  for(int i=0; i<n; i++){
    if(pre<=h[i]-1){
      pre = h[i] - 1;
    }
    else if(pre <= h[i]){
      pre = h[i];
    }
    else {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

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

signed main(){
    int n;
    while(cin >> n, n){
        vector<int> a(n);
        int sum = 0;
        rep(i, 0, n){
            cin >> a[i];
            sum += a[i];
        }
        int ave = sum / n;
        int ans = 0;
        rep(i, 0, n){
            if(a[i] <= ave) ans++;
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3096
#include<cstdio>

int main(){
    int n,m,l;
    scanf("%d %d %d",&n,&m,&l);
    int a[n][m];
    int b[m][l];
    long c[n][l];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < l; j++){
            scanf("%d",&b[i][j]);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < l; j++) {
            c[i][j] = 0;
            for(int k = 0; k < m; k ++){
                c[i][j] += a[i][k] * b[k][j];
            }
            if(j != l - 1){
                printf("%ld ",c[i][j]);
            }
            else{
                printf("%ld",c[i][j]);
            }
        }
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 2756
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N = II()
    v_li = LI()

    v_li.sort()

    ans = 0
    for i, v in enumerate(v_li):
        if i == 0:
            ans += (v / (2**(N-1)))
        else:
            ans += (v / (2**(N-i)))

    print(ans)


main()

Measured memory_bytes: 3064