akhauriyash/Code-Regression huggingface dataset:
N = int(input())
nodes = [set() for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = (u - 1, v - 1)
    nodes[u].add((v, w))
    nodes[v].add((u, w))


ans = [-1 for _ in range(N)]
q = [(0, 0, -1)]

while q:
    v, dist, parent = q.pop()

    if dist % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1

    for u, w in nodes[v]:
        if u == parent:
            continue

        q.append((u, dist + w, v))

print("\n".join(map(str, ans)))


Measured memory_bytes: 56040
N,M=map(int,input().split())
l=[0]*M
for _ in range(N):
    a=list(map(int,input().split()))
    for i in range(1,len(a)):
        l[a[i]-1]+=1
        
ans=0
for i in l:
    if i==N:
        ans+=1

print(ans)

Measured memory_bytes: 3060
def main():
    from string import ascii_lowercase

    N = int(input())

    ans = []

    def dfs(s='a', ma='a'):
        if len(s) == N:
            ans.append(s)
            return

        for c in ascii_lowercase:
            dfs(s + c, max(c, ma))
            if c > ma: break

    dfs()

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


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

string solve(string s){
	string t;
	for(int a = 1; ; ++a)
	for(int b = 0; b < 26; ++b){
		t = s;
		for(int i = 0; i < t.size(); ++i){
			if(t[i] != ' '){
				t[i] = (a * (t[i] - 'a') + b) % 26 + 'a';
			}
		}
		if(t.find("this") != string::npos || t.find("that") != string::npos){
			return t;
		}
	}
}

int main(){
	int n;
	cin >> n;
	cin.get();
	string s;
	for(int i = 0; i < n; ++i){
		getline(cin, s);
		cout << solve(s) << '\n';
	}
}

Measured memory_bytes: 1212
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
using namespace std;
int main(){
    int N; cin >> N;
    vector<int> v(N);
    for(int i = 0;i<N;i++){cin >> v[i];}

    sort(ALL(v)); 

    double ans = 0;

    double bunbo = pow(2,N-1);

    double bunshi = v[0];

    for(int i = 2;i<=N;i++){bunshi += v[i-1]*(pow(2,i-2));}

    ans = bunshi / bunbo;

        cout<<defaultfloat<<setprecision(6);
    cout<<endl;

    cout << fixed << ans <<endl;

}

Measured memory_bytes: 384
D = int(input())
C = list(map(int ,input().split()))
S = [list(map(int, input().split())) for i in range(D)]
sumc = sum(C)
last = [0 for i in range(26)]

for i in range(D):
    ans = 0
    m = -1000000000000
    t = 1
    for k in range(26):
        l = last[k]
        last[k] = i+1
        ans = S[i][k]
        for j in range(26):
            ans -= C[j]*(i+1 - last[j])
        if ans > m:
            m = ans
            t = k + 1
        last[k] = l
    last[t-1] = i+1
    print(t)

Measured memory_bytes: 9292
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;

class Dice {
    int s1, s2, s3, s4, s5, s6;
public:
    Dice(int s1, int s2, int s3, int s4, int s5, int s6);

    void print();

    void roll(char F);
};

void Dice::roll(char F) {
    int tmp = s1;
    if (F == 'N') {
        s1 = s2;
        s2 = s6;
        s6 = s5;
        s5 = tmp;
    }
    if (F == 'W') {
        s1 = s3;
        s3 = s6;
        s6 = s4;
        s4 = tmp;
    }
    if (F == 'S') {
        s1 = s5;
        s5 = s6;
        s6 = s2;
        s2 = tmp;
    }
    if (F == 'E') {
        s1 = s4;
        s4 = s6;
        s6 = s3;
        s3 = tmp;
    }
}

void Dice::print() {
    cout << s1 << endl;
}

Dice::Dice(int _s1, int _s2, int _s3, int _s4, int _s5, int _s6) {
    s1 = _s1;
    s2 = _s2;
    s3 = _s3;
    s4 = _s4;
    s5 = _s5;
    s6 = _s6;
}

int main() {
    int s, S[6];
    for (int i = 0; i < 6; i++) {
        cin >> S[i];
    }
    Dice dice = Dice(S[0], S[1], S[2], S[3], S[4], S[5]);

    string str;
    cin >> str;
    for (int i=0;i<str.length();i++){
        dice.roll(str[i]);
    }
    dice.print();
}


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

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;
#define REP(i, n) for(ll i = 0LL; i < (ll)(n); i++)
#define REPR(i, n) for(ll i = n-1; i >= 0LL; i--)
#define FOR(i, n, m) for(ll i = n; i < (ll)(m); i++)
#define PRINT(x) cout << x << endl
#define ALL(v) v.begin(), v.end()
#define INF (ll)1e18
#define INFD 1e18
#define PI 3.14159265358979
#define MOD 1000000007
#define vl vector<ll>
#define Mat(T) vector<vector<T>>

vector<ll> dx = {-1, 1, 0, 0};
vector<ll> dy = {0, 0, 1, -1};

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

int main()
{
	ll N, M, X;
	cin >> N >> M >> X;
	vector<vector<ll>> mat(N, vector<ll>(M, 0));
	vector<ll> C(N);
	REP(i, N) {
		cin >> C[i];
		REP(j, M) {
			cin >> mat[i][j];
		}
	}
	ll ans = INF;
	REP(i, pow(2, N)) {
		ll cost = 0;
		vector<ll> A(N);
		REP(j, N) {
			if ((i >> j) & 1) {
				cost += C[j];
				REP(k, M) A[k] += mat[j][k];
			}
		}
		bool flag = false;
		REP(j, M) {
			if (A[j] < X) {
				flag = true;
			}
		}
		if (!flag) {
			ans = min(ans, cost);
		}
	}
	if (ans == INF) {
		PRINT(-1);
	} else {
		PRINT(ans);
	}
	return 0;
}


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

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		int x = stdIn.nextInt();

		int fif = x/500;

		int five = (x-fif*500)/5;

		System.out.println(fif*1000+five*5);


	}

}


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

#define  int  long long
#define  ld   long double
#define  endl  '\n'
const int mod = 1e9 + 7;

const int N = 3000;
ld dp[N][N], p[N];
int n;
bool vis[N][N];

ld solve(int i, int k)
{
  //base cases?
   if(i > n)
     return 2 * k >= n;

   if(vis[i][k])
      return dp[i][k];

   vis[i][k] = true;
   dp[i][k] = p[i] * solve(i + 1, k + 1) + (1.0 - p[i]) * solve(i + 1, k);

   return dp[i][k];
}

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

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

  ld ans = solve(1, 0);

  cout << fixed << setprecision(12) << ans << endl;

  return 0;
}

Measured memory_bytes: 150016
import java.util.*;
public class Main {
 
         
        public static void main(String[] args) throws java.io.IOException{
            Scanner scan = new Scanner(System.in);
            int n= scan.nextInt();
            while(n!=0){
            	int x =scan.nextInt();
            	int y =scan.nextInt();
            	int w =scan.nextInt();
            	int h =scan.nextInt();
            	int N = scan.nextInt();
            	int ans = 0;
            	for(int i=0;i<N;i++){
            		int cx = scan.nextInt();
            		int cy = scan.nextInt();
            		if(x<=cx&&cx<=x+w&&y<=cy&&cy<=y+h)ans++;
            	}
            	System.out.println(ans);
            	n--;
            }
        }
}

Measured memory_bytes: 12000
def s()
  gets()
end
def i()
  gets.to_i
end
def li()
  gets.split.map(&:to_i)
end
def ili()
  n = gets.to_i
  as = gets.split.map(&:to_i)
  [n, as]
end

n = i()
as = li()
res = {}
as.each{|a|
  if res[a.to_s] == nil
    res[a.to_s] = 1
  else
    res[a.to_s] += 1
  end
}
sum = 0
res.each{|key, val|
  key_i = key.to_i
  if key_i < val
    sum += val - key_i
  elsif key_i > val
    sum += val
  end
}
puts sum

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

using namespace std;
int n;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n;
    if(n%2 == 0 || n%5 == 0){
        cout<<-1;
        return 0;
    }
    int here = 7%n,cnt = 1;
    while(here){
        here*=10;
        here+=7;
        here%=n;
        cnt++;
    }
    cout<<cnt;
}


Measured memory_bytes: 3628
t[]={10,50,100,500,2e4};e[4];i,z;main(n){for(;scanf("%d%d%d%d%d",&n,e,e+1,e+2,e+3),n;){for(i&&puts(""),i=4;i--;n-=e[i]*t[i]);for(;++i-4;z>0&&printf("%d %d\n",t[i],z))z=e[i]+n%t[i+1]/t[i];}}

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

int main(void){
    int a,b,c,d,e,k;
    bool flag = false;
    cin >> a >> b >> c >> d >> e >> k;
    flag = (abs(a - b) <= k) && (abs(a - c) <= k) && (abs(a - d) <= k) && (abs(a - e) <= k) && (abs(b - c) <= k) && (abs(b - d) <= k) && (abs(b - e) <= k) && (abs(c - d) <= k) && (abs(c - e) <= k) && (abs(d - e) <= k) ? true : false;
    if(flag){
        cout << "Yay!" << endl;
    }else{
        cout << ":(" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>

using namespace std;

const int N = 100010;
int n, m, d, l, r, disl, disr, ld, rd;
int cur[N], dis[N], fa[N];

void find(int&x, int&d)
{
    while (fa[x] != x)
    {
        d += dis[x];
        x = fa[x];
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) fa[i] = i, dis[i] = 0, cur[i] = 0;
    while (m--)
    {
        scanf("%d%d%d", &l, &r, &d);
        find(ld = l, disl = 0); find(rd = r, disr = 0);
        if (ld == rd)
        {
            if (disr - disl != d) {puts("No"); return 0;}
        }
        else
        {
            d += disl - disr;
            if (cur[ld] > cur[rd]) fa[rd] = ld, dis[rd] = d; else
            if (cur[ld] < cur[rd]) fa[ld] = rd, dis[ld] = -d; else
                fa[rd] = ld, dis[rd] = d, ++cur[ld];
        }
    }
    puts("Yes");
    return 0;
}


Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
vector<int>dy({0,-1,0,1}),dx({1,0,-1,0});

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<vector<int>>abc(3,vector<int>(n));
	for(int i=0;i<n;++i){
		cin>>abc.at(0).at(i)>>abc.at(1).at(i)>>abc.at(2).at(i);
	}
	vector<vector<int>>dp(3,vector<int>(n,0));
	for(int i=0;i<3;++i){
		dp.at(i).front()=abc.at(i).front();
	}
	for(int i=1;i<n;++i){
		for(int j=0;j<3;++j){
			for(int k=0;k<3;++k){
				if(j==k)continue;
				dp.at(j).at(i)=max(dp.at(j).at(i),dp.at(k).at(i-1)+abc.at(j).at(i));
			}
		}
	}
	cout<<max({dp.at(0).back(),dp.at(1).back(),dp.at(2).back()})<<"\n"s;
}


Measured memory_bytes: 5852
import Data.List
import qualified Data.Array.IArray as A

main = do
  [h,w,a,b] <- map read . words <$> getLine
  print (iroha h w a b)

iroha h w a b = foldr1 (+%) (zipWith (*%) r1 r2)
  where
    t = factTable $ fromIntegral (h + w - 2)
    r1 = map (\y -> combMod t (y + (h-a-1)) y) [b .. w-1]
    r2 = map (\y -> combMod t (y + (a-1)) y) (reverse [0 .. (w-1)-b])


type FactTable = A.Array Int (Integer, Integer)

modulus :: Integer
modulus = 1000000007

(+%) :: Integer -> Integer -> Integer
(+%) x y = mod (x + y) modulus

(*%) :: Integer -> Integer -> Integer
(*%) x y = mod (x * y) modulus

powMod :: Integer -> Integer -> Integer
powMod x n
  | n == 0 = 1
  | odd n = x *% powMod x (n-1)
  | otherwise = let y = powMod x (div n 2) in y *% y

combMod :: FactTable -> Integer -> Integer -> Integer
combMod t n r
  | n < r = 0
  | otherwise = fst (t ! n) *% snd (t ! r) *% snd (t ! (n - r))

factTable :: Int -> FactTable
factTable n = A.listArray (0, n) (zip facts factInvs)
  where
    facts = scanl (*%) 1 [1 .. fromIntegral n]
    factInvs = map (\x -> mod (powMod x (modulus - 2)) modulus) facts

(!) :: FactTable -> Integer -> (Integer, Integer)
(!) t i = t A.! fromIntegral i


Measured memory_bytes: 60284
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int n=s.size();
	int ans=0;
	for (int i=0,sum=0;i<n;i++)
	{
		if (s[i]=='R') sum++;
		else sum=0;
		ans=max(ans,sum);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3232
Kth = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(Kth[int(input())-1])

Measured memory_bytes: 38256
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

const int INF = (int)1e16;

void solve(long long L, std::vector<long long> A){
    vector<vector<int>> dp(L + 1, vector<int>(5, INF));
    for(int i = 0; i < 5; ++i) {
        dp[0][i] = 0;
    }

    for(int i = 0; i < L; ++i) {
        dp[i + 1][0] = dp[i][0] + A[i];

        int c = A[i] % 2 == 0 ? (A[i] == 0 ? 2 : 0) : 1;
        dp[i + 1][1] = min(dp[i][1] + c, dp[i + 1][0]);

        int d = A[i] % 2 == 1 ? 0 : 1;
        dp[i + 1][2] = min(dp[i][2] + d, dp[i + 1][1]);

        dp[i + 1][3] = min(dp[i][3] + c, dp[i + 1][2]);

        dp[i + 1][4] = min(dp[i][4] + A[i], dp[i + 1][3]);
    }

    int res = dp[L][0];
    for(int i = 0; i < 5; ++i) {
        res = min(dp[L][i], res);
    }
    cout << res << endl;
}

signed main(){
    long long L;
    scanf("%lld",&L);
    std::vector<long long> A(L);
    for(int i = 0 ; i < L ; i++){
        scanf("%lld",&A[i]);
    }
    solve(L, std::move(A));
    return 0;
}

Measured memory_bytes: 15872
n, x = map(int, input().split())
ls = list(map(int, input().split()))
ans = [0, ls[0]]

for i in range(1,len(ls)):
    if ans[i] + ls[i] <= x:
        ans.append(ans[i] + ls[i])
    else:
        break
print(len(ans))

Measured memory_bytes: 3316
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

using Edges = vector<pair<int, LL>>;
using Graph = vector<Edges>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const LL INF = (1LL << 60);
vector<LL> dijkstra(const Graph &g, int s) {
    int n = g.size();
    vector<LL> dist(n, INF);
    min_priority_queue<pair<LL, int>> que;

    que.push({0, s});
    dist[s] = 0;
    while(not que.empty()) {
        auto dv = que.top(); que.pop();
        LL d = dv.first;
        int v = dv.second;

        if (dist[v] < d) continue;
        for (auto e : g[v]) {
            if (dist[v] + e.second < dist[e.first]) {
                dist[e.first] = dist[v] + e.second;
                que.push({dist[e.first], e.first});
            }
        }
    }
    return dist;
}
int main() {
    int n; cin >> n;
    Graph tree(n);
    rep(i, n - 1) {
        int a, b; LL c; cin >> a >> b >> c;
        --a; --b;
        tree[a].push_back({b, c});
        tree[b].push_back({a, c});
    }
    int q, k; cin >> q >> k;

    auto dist = dijkstra(tree, k - 1);
    vector<LL> ans;
    rep(i, q) {
        int x, y; cin >> x >> y;
        ans.push_back(dist[x - 1] + dist[y - 1]);
    }
    for (auto &x: ans ) {
        cout << x << endl;
    }

}


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

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

    int k, n, m, i, x, j, count=0;
    cin>>n>>m;
    vector<int> v(m);

    for(i=0; i<n; i++){
        cin>>k;
        for(j=0; j<k; j++){
            cin>>x;
            x--;
            v[x]++;
        }
    }
    for(i=0; i<m; i++){
        if(v[i] == n){
            count++;
        }

    }

    cout<<count;






}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

const int INF = 1e9;
const long long LINF = 1e18;
const double PI=3.14159265358979323846;

typedef priority_queue<int, vector<int>, greater<int>> priority_queue_asc;

int main() {
    int X, Y;
    cin >> X >> Y;

    for (int a = 0; a <= 100; a++) {
        for (int b = 0; b <= 100; b++) {
            if ((a + b == X) && (2 * a + 4 * b == Y)) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }

    cout << "No" << endl;
    return 0;
}


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

const int MAX = 1e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;
 
int A, B, C;

int main(){
    cin >> A >> B >> C;
    cout << max(0, C - (A - B)) << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;

    pair<int, int> ab[100100];
    for (int i = 0; i < M; i++) {
        cin >> ab[i].second >> ab[i].first;
    }

    sort(ab, ab + M);

    int ans = 0;
    int last = 0;
    for (int i = 0; i < M; i++) {
        int a = ab[i].second, b = ab[i].first;
        if (a >= last) {
            last = b;
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

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

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(rall(a));
    ll ans = 0;
    priority_queue<int> pq;
    rep(i, n) {
        if (i == 0) continue;
        if (i == 1) {
            ans += a[0];
            pq.push(a[1]);
            pq.push(a[1]);
        } else {
            int mx = pq.top();
            pq.pop();
            ans += mx;
            pq.push(a[i]);
            pq.push(a[i]);
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 5064
#include<stdio.h>
#include<iostream>
typedef unsigned long long ll;
using namespace std;
int main(){
    ll a,b,n,ans;
    scanf("%lld %lld %lld",&n,&a,&b);
    ans=(n/(a+b))*a;
    ll r=n%(a+b);
    if(r>0&&r<=a) ans+=r;
    else if(r>a) ans+=a;
    printf("%lld\n",ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

int main()
{
    cin >> X >> K>>D;

    if(X>0)
    {
        if(X/D <=K)
        {
            K-=X/D;
            X%=D;
            if(K%2)
            {
                X-=D;
            }
        }
        else
        {
            X-=K*D;
        }
    }
    else
    {
        if(abs(X/D) <=K)
        {
            K-=abs(X/D);
            X%=D;
            if(K%2)
            {
                X+=D;
            }
        }
        else
        {
            X+=K*D;
        }
    }
    cout<<abs(X);
    return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>
// *テンプレート*
#define int long long
#define rep(i, n) for (int i = 0; i < (n); i++)
#define P pair<int, int>
#define sz(x) x.size()
// aよりbの方が小さかったら、aの値をbの値に置き換える。(swapではない！)
template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
// aよりbの方が大きかったら、aの値をbの値に置き換える。
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>; 
//最大公約数
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
//最小公倍数
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

const long long mod = 1000000007;
const long long INF = 1LL << 60;
// *テンプレートここまで*

// pair -> vector<pair<int,int>> 
//		   AandB.push_back(make_pair(a[i],b[i]))



signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	vector<int>a(n); rep(i, n)cin >> a[i];
	sort(a.rbegin(), a.rend());
	int ma = a[0];
	int now = a[0];
	rep(i, n) {
		now = gcd(now, a[i]);
	}
	if (k%now == 0 && k <= ma) {
		cout << "POSSIBLE" << endl;
	}
	else {
		cout << "IMPOSSIBLE" << endl;
	}
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
    int a[1000000]={0,0,1,1},n,k=0;
    for(int i=4;i<1000000;i++){
        for(int j=2;j*j<=i;j++){
            if(i%j==0){k++;break;}
        }
        if(!k)a[i]++;
        k=0;
    }
    int b,c,d,x,s,q;
    while(cin>>b>>c>>d,b!=0&&c!=0&&d!=0){
        s=x=q=0;
        while(1){
            x=b+c*s;
            if(a[x]==1)q++;
            if(q==d)break;
            s++;
        }
        cout<<x<<endl;
    }
    return 0;
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

int main() {
    string s, t;
    cin >> s >> t;
    int n = s.length();
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] != t[i])
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3732
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

int main()
{
  vector<vecint> a(3,vecint(3));
  for(auto&& l:a)for(auto&& e:l)cin>>e;
  int n;
  cin>>n;
  for(auto&& i:irange(0,n)) {
    int b;
    cin>>b;
    for(auto&& l:a)for(auto&& e:l) {
      if (e == b) e = 0;
    }
  }
  bool ok = false;
  for(auto&& l:a) {
    bool h = true;
    for(auto&& e:l) {
      if (e != 0) h = false;
    }
    if (h) ok = true;
  }
  for(auto&& j:irange(0,3)) {
    bool v = true;
    for(auto&& i:irange(0,3)) {
      if (a[i][j] != 0) v = false;
    }
    if (v) ok = true;
  }
  if (!(a[0][0] || a[1][1] || a[2][2])) ok = true;
  if (!(a[2][0] || a[1][1] || a[0][2])) ok = true;
  if (ok) {
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
static const int N=100;
static const int WHITE=0;
static const int GRAY=1;
static const int BLACK=2;

int M[N][N],n;
int color[N],d[N],f[N],tt;

void dfs_visit(int u){
	int v;
	color[u]=GRAY;
	d[u]=++tt;
	for(v=0;v<n;v++){
		if(M[u][v]==0)
			continue;
		if(color[v]==WHITE){
			dfs_visit(v);
		}
	}
	color[u]=BLACK;
	f[u]=++tt;
	
}

void dfs(){
	int u;
	for(int i=0;i<n;i++){
		color[i]=WHITE;
	}
	tt=0;
	
	for(u=0;u<n;u++){
		if(color[u]==WHITE)
			dfs_visit(u);
	}
	
	for(int i=0;i<n;i++)
		cout<<i+1<<" "<<d[i]<<" "<<f[i]<<endl;
}

int main(){
	
	int k,u,v;
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)
			M[i][j]=0;
	}
	for(int i=0;i<n;i++){
		cin>>u>>k;
		u--;
		for(int j=0;j<k;j++){
			cin>>v;
			v--;
			M[u][v]=1;
		}
	}
		
	dfs();	

	return 0;
}



Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,a,b) for(ll i=a ; i<b ; i++)
const int max_n = 1e5;
const ll mod = 1e9+7;
typedef long double ld;
int main(){
  int h,w;  cin >> h >> w;
  string s[h+5];
  rep(i,0,h) cin >> s[i];
  int d[2005][2005];
  rep(i,0,h)rep(j,0,w) d[i][j] = 0;
  int ma = 0;
  rep(i,0,h)rep(j,0,w){
    if((j-1<0 || s[i][j-1]=='#') && s[i][j]=='.'){
      int k=j;
      while(s[i][j]==s[i][k] && k<w) k++;
      rep(t,j,k){
        d[i][t] +=k-j-1;
        ma = max(ma, d[i][t]);
      }
    }
    if((i-1<0||s[i-1][j]=='#') && s[i][j]=='.') {
      int k=i;
      while(s[i][j]==s[k][j] && k<h) k++;
      rep(t,i,k){
         d[t][j] += k-i;
         ma = max(ma, d[t][j]);
      }
    }
  }
  cout << ma << endl;
  return 0;
}


Measured memory_bytes: 19968
#ifdef _MSC_VER
#include <__msvc_all_public_headers.hpp>
#undef min
#undef max
#else
#define NDEBUG
#include <bits/stdc++.h>
#endif

using namespace std;
using large = long long;

int main() {
    large a, v, b, w, t;
    cin >> a >> v >> b >> w >> t;

    auto d = max(a, b) - min(a, b);
    if (d == 0) {
        cout << "YES";
        return 0;
    }
    if (w > v) {
        cout << "NO";
        return 0;
    }

    if (t * (v - w) >= d) {
        cout << "YES";
        return 0;
    }

    cout << "NO";
    return 0;
}


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

#define	MOD 1000000007;
#define PI 3.14159265358979323846;
#define rep(i,n) for(int i = 0;i<(int)n;i++)
using namespace std;
typedef long long ll;
ll mod = 1000000007;
static const long long INFTY = (1LL << 32);
static const long long MAX = 300;

bool diff = false;
int n;
ll M[MAX][MAX];
bool d_n[MAX][MAX];
void floyd() {
	for (int k = 0; k < n; k++)
	{
		for (int i = 0; i < n; i++)
		{
			if (M[i][k] == INFTY) continue;
			for (int j = 0; j < n; j++)
			{
				if (M[k][j] == INFTY) continue;

				if (M[i][j] > M[i][k] + M[k][j]) {
					diff = true;
					M[i][j] = M[i][k] + M[k][j];
				}

				if (M[i][j] == M[i][k] + M[k][j] && M[i][k] > 0 && M[k][j] > 0) {
					d_n[i][j] = true;
				}
			}
		}
	}
}

int main()
{
	cin >> n;
	rep(i, n)rep(j, n) {
		cin >> M[i][j];
	}

	floyd();

	ll ans = 0;
	if (!diff) {
		rep(i, n)rep(j, n) {
			if (d_n[i][j] == false) ans += M[i][j];
		}
		cout << ans / 2 << endl;
	}
	else {
		cout << -1 << endl;
	}

	return 0;
}

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

void fnInput(int& rnAmont, vector<int>& rvnDonAmt)
{
  int nDonSiz;
  cin >> nDonSiz >> rnAmont;

  rvnDonAmt.resize(nDonSiz);
  for (int& rnDonAmt : rvnDonAmt)
    cin >> rnDonAmt;
}

int fnDonCount(int nAmont, const vector<int>& cnrvnDonAmt)
{
  auto itMinAmt = min_element(begin(cnrvnDonAmt), end(cnrvnDonAmt));

  for (int nDonAmt : cnrvnDonAmt)
    nAmont -= nDonAmt;

  int nDonCnt = cnrvnDonAmt.size();
  nDonCnt += nAmont / *itMinAmt;

  return nDonCnt;
}

int main()
{
  int nAmont;
  vector<int> vnDonAmt;

  fnInput(nAmont, vnDonAmt);
  cout << fnDonCount(nAmont, vnDonAmt) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int main()
{
	int h, w, n;
	cin >> h >> w >> n;
	vector<vector<int> > obstacleXtoY(200001);
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		obstacleXtoY[x].push_back(y);
	}
	for(int i = 1; i <= h; i++){
		sort(obstacleXtoY[i].begin(), obstacleXtoY[i].end());
	}
	vector<pair<int, int> > nowRange;
	nowRange.push_back(make_pair(1, 2));
	for(int i = 2; i <= h; i++){
		// cout << i << endl;
		// nowRange : x = i - 1で、yとしてとりうる範囲
		// x = i - 1でゲームを終了できるかチェック
		int rangeItr = 0;
		for(int j = 0; j < obstacleXtoY[i].size(); j++){
			int obst = obstacleXtoY[i][j];
			while(rangeItr < nowRange.size() && obst > nowRange[rangeItr].second) rangeItr++;
			if(rangeItr == nowRange.size()) break;
			int l = nowRange[rangeItr].first;
			int r = nowRange[rangeItr].second;
			if(l <= obst && obst < r){
				cout << i - 1 << endl;
				return 0;
			}
		}
		// 次の行でのとりうる範囲を求める
		vector<pair<int, int> > nextRange;
		int itr = 0;
		for(int j = 0; j < nowRange.size(); j++){
			int l = nowRange[j].first;
			int r = nowRange[j].second;
			while(itr < obstacleXtoY[i].size() && obstacleXtoY[i][itr] < l) itr++;
			if(itr == obstacleXtoY[i].size()){
				nextRange.push_back(make_pair(l, r + 1));
				continue;
			}
			while(itr < obstacleXtoY[i].size() && obstacleXtoY[i][itr] <= r){
				if(l != obstacleXtoY[i][itr]){
					nextRange.push_back(make_pair(l, obstacleXtoY[i][itr]));
					l = obstacleXtoY[i][itr] + 1;
				}
				itr++;
			}
			if(l != r + 1){
				nextRange.push_back(make_pair(l, r + 1));
			}
		}
		nowRange.clear();
		for(int j = 0; j < nextRange.size(); j++){
			int l = nextRange[j].first;
			int r = nextRange[j].second;
			while(j + 1 < nextRange.size() && nextRange[j + 1].first < r){
				j++;
				r = nextRange[j].second;
			}
			nowRange.push_back(make_pair(l, r));
			// cout << l << " " << r << endl;
		}
	}
	cout << h << endl;
}

Measured memory_bytes: 11136
#include "bits/stdc++.h"
using namespace std;
#define repr(i,a,b) for(long long i=(long long)(a);i<(long long)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define PI 3.1415926535
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<Pll> vPll;
typedef vector<vector<int>> vvi;
typedef vector<vector<bool>> vvb;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<string>> vvs;
typedef vector<vector<double>> vvd;
typedef vector<vector<Pi>> vvPi;
typedef priority_queue<int, vector<int>, greater<int>> pqli;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi>> pqlP;
string YN(bool y) { return (y?"YES":"NO"); }
string yn(bool y) { return (y?"Yes":"No"); }
string ON(bool y) { return (y?"OK":"NG"); }
int main(void)
{
	ll k, a, b;

	cin>>k>>a>>b;

	if(a+2<b&&k>=a+1){
		k-=(a+1);
		cout<<b+(k/2)*(b-a)+k%2<<endl;
	} else{
		cout<<k+1<<endl;
	}
}


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

# input
X, Y = input().split()

# solve
l = ['A', 'B', 'C', 'D', 'E', 'F']

if l.index(X) < l.index(Y):
    ans = '<'
elif l.index(X) > l.index(Y):
    ans = '>'
else:
    ans = '='

# output
print(ans)


Measured memory_bytes: 2940
#include <iostream>

using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a * 10 + b + c > max(a + b * 10 + c, a + b + c * 10)) cout << a * 10 + b + c << endl;
    else cout << max(a + b * 10 + c, a + b + c * 10) << endl;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
input = sys.stdin.readline

# bisect_left(lists, 3)
# bisect_right(lists, 3)

def main():
	X, Y, Z, K = map(int, input().split(" "))
	As = []
	Bs = []
	Cs = []
	As = input().split()
	As = [int(s) for s in As]
	Bs = input().split()
	Bs = [int(s) for s in Bs]
	Cs = input().split()
	Cs = [int(s) for s in Cs]

	As.sort(reverse=True)
	Bs.sort(reverse=True)
	Cs.sort(reverse=True)

	ans1 = []
	for i, val in enumerate(As):
		for j, vol in enumerate(Bs):
			ans1.append(val+vol)

	ans1.sort(reverse=True)
	ans1 = ans1[:3000]

	ans2 = []
	for i, val in enumerate(ans1):
		for j, vol in enumerate(Cs):
			ans2.append(val+vol)

	ans2.sort(reverse=True)
	for i in range(K):
		print(ans2[i])
	
if __name__ == "__main__":
	main()
	

Measured memory_bytes: 161888
#include <stdio.h>

int main() {
  int n, x, l, d, i;
  i = 0; d = 0;
  scanf("%d %d", &n, &x);
  while ((d < x+1) && (i < n+1)) {
    i += 1;
    scanf("%d", &l);
    d += l;
  }
  printf("%d\n", i);
}

Measured memory_bytes: 128
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>

using namespace std;
int h, w;
char s[20][21];
int ans = 0, dis[20][20];

void init() {
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      dis[i][j] = 10000;
    }
  }
}

void bfs(int x, int y) {
  queue<pair<int, int> > q;
  q.push({x, y});
  while (!q.empty()) {
    pair<int, int> p = q.front();
    q.pop();
    if (p.first > 0 && s[p.first - 1][p.second] == '.' &&
        dis[p.first - 1][p.second] > dis[p.first][p.second] + 1) {
      dis[p.first - 1][p.second] = dis[p.first][p.second] + 1;
      q.push({p.first - 1, p.second});
    }
    if (p.first < h - 1 && s[p.first + 1][p.second] == '.' &&
        dis[p.first + 1][p.second] > dis[p.first][p.second] + 1) {
      dis[p.first + 1][p.second] = dis[p.first][p.second] + 1;
      q.push({p.first + 1, p.second});
    }
    if (p.second > 0 && s[p.first][p.second - 1] == '.' &&
        dis[p.first][p.second - 1] > dis[p.first][p.second] + 1) {
      dis[p.first][p.second - 1] = dis[p.first][p.second] + 1;
      q.push({p.first, p.second - 1});
    }
    if (p.second < w - 1 && s[p.first][p.second + 1] == '.' &&
        dis[p.first][p.second + 1] > dis[p.first][p.second] + 1) {
      dis[p.first][p.second + 1] = dis[p.first][p.second] + 1;
      q.push({p.first, p.second + 1});
    }
  }
}

int main() {
  scanf("%d%d", &h, &w);
  for (int i = 0; i < h; i++) {
    scanf("%s", s[i]);
  }
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      init();
      dis[i][j] = 0;
      if (s[i][j] == '.') {
        bfs(i, j);
        for (int k = 0; k < h; k++) {
          for (int l = 0; l < w; l++) {
            if (s[k][l] == '.') {
              ans = max(ans, dis[k][l]);
            }
          }
        }
      }
    }
  }
  printf("%d\n", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define LL long long
#define endl '\n'
using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string w;
    cin >> w;
    string t;
    int cnt = 0;
    while(cin >> t) {
        if (t == "END_OF_TEXT") {
            break;
        }
        REP(i, t.size()) {
            if ('A' <= t[i] && t[i] <= 'Z') {
                t[i] = tolower(t[i]);
            }
        }
        if (w == t) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3176
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin>>N;
  cin>>K;
  
  int ans=1;
  for(int i=0;i<N;i++) {
    if(ans*2<=ans+K) {
      ans*=2;
    }
    else{
      ans+=K;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
#include <map>
 
using namespace std;
int X, Y, Z;

int main()
{
  int A, B, C;
  int ret=0;

  cin >> X >> Y >> Z;

  A=X; B=Y; C=Z;

  swap(A, B);
  swap(A, C);

  printf("%d %d %d\n", A, B, C);
  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;	// 昇順
    // return *(int*)b - *(int*)a;		// 降順
}

int main()
{
    int   ret_scanf;
    int   i, j, n, in_data;
    int  buff[50];
    int   count;
    int   size;
     float data;

    // フォーマットに従って標準入力から入力
    ret_scanf = scanf("%d", &n);
    if (ret_scanf == 0) return 0;
    // printf("number of count = %d \n", n);

    count = 0;
    for (i = 0; i < n; i++) {
        ret_scanf = scanf("%d", &in_data);
        if (ret_scanf != 0) {
            *(buff + count) = in_data;
            count = count + 1;
            // printf("input data = %d\n", in_data);
        } else {
            return 0;
        }
    }
    qsort(buff, n, sizeof(int), compare_int);
 
    // for (i = 0; i < n; i++) {
    //     printf("%d ", buff[i]);
    // }
	// printf("\n");
	
	data = buff[0];
	for (int i = 0; i < n - 1; i++) {
		data =  (data + (float)buff[i + 1]) / 2;
              // printf(" --- %g \n", data);
	}
	printf("%g ", data);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct card {
	char al;
	char value;
};

void selection_sort(int n,vector<card> &vec);
void bubble_sort(int n, vector<card> &vec);
void isStable(vector<card> vec1,vector<card> vec2,int n);
void display(vector<card> vec, int n);


int main() {
	int n;
	cin >> n;
	vector<card> a1(n);
	vector<card> a2(n);
	for (int i = 0; i < n; i++) cin >> a1[i].al >> a1[i].value;
	for (int i = 0; i < n; i++) a2[i] = a1[i];

	bubble_sort(n, a1);
	selection_sort(n, a2);

	display(a1,n);
	cout << "Stable" << "\n";
	display(a2, n);
	isStable(a1, a2, n);
	return 0;
}

void bubble_sort(int n, vector<card> &vec) {
	bool flag = false;
	for(int i=0;i<n;i++){
		for (int j = n-1; j >=i+1 ; j--) {
			if (vec[j].value < vec[j - 1].value) {
				swap(vec[j], vec[j - 1]);
			}
		}
	}
}
void selection_sort(int n,vector<card> &vec) {
	int minj;
	for (int i = 0; i < n; i++) {
		minj = i;
		for (int j = i; j < n; j++) {
			if (vec[j].value < vec[minj].value) {
				minj = j;
			}
		}
		if (i != minj) {
			swap(vec[i], vec[minj]);
		}
	}
}

void isStable(vector<card> vec1,vector<card> vec2,int n) {
	bool flag = false;
	for (int i = 0; i < n; i++) {
		if (vec1[i].al != vec2[i].al) flag=true;
	}

	if (flag) cout<<"Not stable\n";
	else cout<<"Stable\n";
}

void display(vector<card> vec, int n) {
	for (int i = 0; i < n; i++) {
		if (i) cout << " ";
		cout << vec[i].al << vec[i].value;
	}
	cout << "\n";
}


Measured memory_bytes: 3148
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int h,w,k,ans[301][301],sum[301][301];
char c[301][301];
int main(){
    cin>>h>>w>>k;
    for(int i=0;i++<h;)for(int j=0;j++<w;){
        cin>>c[i][j];
        if(c[i][j]=='#')ans[i][j]=k--;
    }
    for(int i=0;i++<h;){
        for(int j=1;j++<w;){
            if(ans[i][j]==0)ans[i][j]=ans[i][j-1];
        }
        for(int j=w;j;j--){
            if(ans[i][j]==0)ans[i][j]=ans[i][j+1];
        }
    }
    for(int j=0;j++<w;){
        for(int i=1;i++<h;){
            if(ans[i][j]==0)ans[i][j]=ans[i-1][j];
        }
        for(int i=h;i;i--){
            if(ans[i][j]==0)ans[i][j]=ans[i+1][j];
        }
    }
    for(int i=0;i++<h;){
        for(int j=0;j++<w;){
            if(j!=1)cout<<" ";
            cout<<ans[i][j];
        }
        cout<<endl;
    }
}


Measured memory_bytes: 1152
#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 ans;
for(int i=0;i<N;i++){
  while(a[i]%2==0){
    a[i]=a[i]/2;
    ans ++;
  }
}
    cout<<ans<<endl;
  return 0;
  
}

Measured memory_bytes: 256
# frozen_string_literal: true

n = gets.to_f
a = gets.split.map(&:to_i)
mean = a.inject(:+) / n
min = (a.shift - mean).abs
ret = 0

a.each_with_index do |e, idx|
  d = (e - mean).abs
  if min > d
    min = d
    ret = idx + 1
  end
end

puts ret

Measured memory_bytes: 1788
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
   ll a,v,b,w,t;
   cin>>a>>v>>b>>w>>t;
   if(a>=0)
   {
       if(b>=0)
       {
           if(a+v*t>=b+w*t)
            cout<<"YES"<<endl;
           else
            cout<<"NO"<<endl;
       }
       else
       {


           if(a-v*t<=b-w*t)
            cout<<"YES"<<endl;
           else
            cout<<"NO"<<endl;
       }
   }
       else
       {
           if(b>=0)
           {
               if(a+v*t>=b+w*t)
                cout<<"YES"<<endl;
               else
                cout<<"NO"<<endl;
           }
           else
            if(a-v*t<=b-w*t)
              cout<<"YES"<<endl;
           else
            cout<<"NO"<<endl;
       }


 return 0;
}


Measured memory_bytes: 3588
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <map>

using namespace std;

int main()
{
    int N;
    if (scanf("%d", &N) < 1) return 0;

    map<int, int> m;

    for (int i = 0; i < N; i++)
    {
        int A;
        if (scanf("%d", &A) < 1) return 0;
        m[A]++;
    }

    printf("%d\n", m.size() % 2 ? m.size() : m.size() - 1);
    return 0;
}


Measured memory_bytes: 4864
def main():
    n = int(input())
    abc = []
    for _ in range(n):
        abc.append(tuple(map(int, input().split())))
    dp = [[0,0,0] for _ in range(n)]
    dp[0][0] = abc[0][0]
    dp[0][1] = abc[0][1]
    dp[0][2] = abc[0][2]

    for i in range(1, n):
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + abc[i][0]
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + abc[i][1]
        dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + abc[i][2]
    print(max(dp[n-1]))

if __name__ == '__main__':
    main()

Measured memory_bytes: 40224
///AJoy Sarker ,CSE JAHANGIRNAGAR UNIVERSITY 48 Batch
#include<bits/stdc++.h>
using namespace std;
#define SORT(c) sort((c).begin(),(c).end());
#define pb push_back
#define MP make_pair
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define pi 3.141592653589793
#define in scanf
#define out printf
#define ll long long
#define ull unsigned long long
#define w(x) int x;cin>>x;while(x--)
#define fast ios_base::sync_with_stdio(0)
#define FOR(i,a,b) for( int i=(a),_b=(b);i<=_b;i++)
#define DOW(i,b,a) for( int i=(b),_a=(a);i>=_a;i--)
#define sz size()
typedef unsigned long long UL;
template<typename T>inline T  S(T a)
{
    return a*a;
}
template<class T>inline string tostring(T a)
{
    ostringstream os("");
    os << a;
    return os.str();
}
template<typename T>inline ll tolong(T a)
{
    ll res;
    istringstream os(a);
    os>>res;
    return res;
}
template<typename T>inline T gcd(T a, T b)
{
    if (b == 0)return a;
    else return gcd(b, a % b);
}
template<typename T>inline T bigmod(T a, T b, T m)
{
    if (b == 0)return 1;
    else if (b % 2 == 0)return S(bigmod(a, b / 2, m)) % m;
    else return (a % m*bigmod(a, b - 1, m)) % m;
}
const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;
#define N 20000009
bool prime[N];
vector<ll> prm;
void seive ()
{

    memset(prime, true, sizeof(prime));

    for( ll i=2; i*i<=N; i++)
    {
        if (prime[i] == true)
        {
            prm.pb(i);
            for (ll j=i*i; j<=N; j += i)
                prime[j] = false;
        }
    }
}
void pr (int f)
{
    if(f==1)
        cout<<"YES\n";
    else
        cout<<"NO\n";
}
map<int,int>mp;
set<int> s;
int vis[111];
int main()
{
    fast;
    int n,d;
    cin>>n>>d;
    vector<vector<int> > V(n, vector<int>(d));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < d; j++)
        {
            cin >> V[i][j];
        }
    }
    int c = 0;
    for (int i = 0; i< n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            int D = 0;
            for (int k = 0; k < d; k++)
            {
                int diff = abs(V[i][k] - V[j][k]);
                D += diff*diff;
            }
            bool ok = false;
            for (int k = 0; k <= D; k++)
            {
                if (k*k == D)
                {
                    ok = true;
                }
            }
            if (ok)
            {
                c++;
            }
        }
    }
    cout <<c<<endl;
}




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

using namespace std;

int seen[200005] = {0};
int ans[200005] = {0};

void dfs(vector<vector<int> > &G, int s) {
    seen[s] = 1;
    for (int i = 0; i < G[s].size(); i++) {
        int n = G[s][i];

        if (seen[n] == 1)
            continue;

        ans[n] += ans[s];
        dfs(G, n);
    }
}

int main() {
    int n, q;  cin >> n >> q;
    vector<vector<int> > G(n);

    for (int i = 0; i < n-1; i++) {
        int a, b;   cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

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

    dfs(G, 0);

    for (int i = 0; i < n; i++)
        cout << ans[i] << " ";

    cout << endl;

    return 0;
}

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

using namespace std;

#define N 100010

int main(){
    int n,m,h[N],ma[N];
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
        cin>>h[i];
        ma[i]=0;
    }
    
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        ma[a]=max(ma[a],h[b]);
        ma[b]=max(ma[b],h[a]);
    }
    
    int ans=0;
    
    for(int i=1;i<=n;i++){
        ans+=h[i]>ma[i];
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 4404
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#define N 100005
using namespace std;
typedef long long ll;
int vis[N],a[N];
void creat()
{
    for(int i=2;i<=400;i++){
        if(!vis[i]){
            for(int j=i*2;j<=N;j+=i)
                vis[j]=1;
        }
    }
}
int main()
{

   memset(vis,0,sizeof(vis));
   creat();
   //for(int i=1;i<=30;i++)
   // printf("%d\n",vis[i]);
   vis[1]=1;
   int sum=0;
   for(int i=1;i<=N;i++)
   {
       if(i%2==1){
       if(vis[i]==0&&vis[(i+1)/2]==0)
         sum++;
       }

        a[i]=sum;
   }
  // printf("%d %d",a[3],a[6]);
   //printf("%d %d",a[7],a[11]);
   int n;
   while(scanf("%d",&n)==1){
     while(n--){
        int c,b;
        scanf("%d%d",&c,&b);
        /*int flag1=0,flag2=0;
        if(vis[c]==0&&vis[(c+1)/2]==0)
            flag1=1;
        if(vis[b]==0&&vis[(b+1)/2]==0)
            flag2=1;*/
        printf("%d\n",a[b]-a[c-1]);
     }
   }
}


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

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    int passNum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> h[i];
        if (h[i] >= K)
            passNum++;
    }
    cout << passNum << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>

using namespace std;

int main ()
{
	int sx, sy, tx, ty;
	cin >> sx >> sy >> tx >> ty;
	string A;
	int a = 0;
	while (a < tx-sx) {
		A = A + 'R';
		a++;
	}

	a = 0;

	while (a < ty-sy) {
		A = A + 'U';
		a++;
	}

	a = 0;

	while (a < tx-sx) {
		A = A + 'L';
		a++;
	}

	a = 0;

	while (a < ty-sy) {
		A = A + 'D';
		a++;
	}

	a = 0;

	A = A + 'L';

	while (a < ty-sy+1) {
		A = A + 'U';
		a++;
	}

	a = 0;

	while (a < tx-sx+1) {
		A = A + 'R';
		a++;
	}

	a = 0;

	A = A + 'D';

	A = A + 'R';

	while (a < ty-sy+1) {
		A = A + 'D';
		a++;
	}

	a = 0;

	while (a < tx-sx+1) {
		A = A + 'L';
		a++;
	}

	A = A + 'U';

	cout << A << endl;

}

Measured memory_bytes: 256