akhauriyash/Code-Regression huggingface dataset:
INF = 10 ** 10
v, e = map(int, input().split())
adj = [[INF] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, input().split())
    adj[s][t] = d

mem = {}
end = 2 ** v - 1
def minCost(state, pos):
    if (state, pos) in mem:
        return mem[(state, pos)]

    if state == end:
        return adj[pos][0]

    mask = 1
    ret = INF
    for to in range(v):
        if mask & state:
            mask <<= 1
            continue

        ret = min(ret, adj[pos][to] + minCost(state | mask, to))
        mask <<= 1

    mem[(state, pos)] = ret
    return ret

result = minCost(1, 0)
if result >= INF:
    print(-1)
else:
    print(result)



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

int main() {
int A,B,C,x;
  cin >> A;
  cin >> B;
  cin >> C;
  cin >> x;
  int t = 0 ;
  for(int h = 0; h <= A; h++){
  for(int i = 0; i <= B; i++){
  for(int j = 0; j <= C; j++){
    if (500*h+100*i+50*j == x){
    t ++;
    }
    
  }
  }
  }
  cout << t << endl;
}

Measured memory_bytes: 256
#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 whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int n; cin >> n;
    ll count = 0;
    vector<int> enemy(n + 1), hero(n);
    REP(i, n + 1) cin >> enemy[i];
    REP(i, n) cin >> hero[i];
    REP(i, n){
        if(hero[i] >= enemy[i]){
            int next = hero[i] - enemy[i];
            if(enemy[i + 1] >= next){
                enemy[i + 1] -= next;
                count += hero[i];
            }
            else{
                count += enemy[i] + enemy[i + 1];
                enemy[i + 1] = 0;
            }
        }
        else count += hero[i];
    }
    cout << count << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
#include<math.h>
#define scani(x) scanf("%d",&x)
#define scanc(x) scanf("%s",x)

#define printi(x) printf("%d",x)
#define printin(x) printf("%d\n",x)
#define printc(x) printf("%s",x)
#define repd(i,n,m) for(int i = n; i > m; i--)
#define repu(i,n,m) for(int i = 0; i < m; i++)
#define allprintu(i,n,m,a) for(int i = 0; i < m; i++){if(i != m-1){printf("%d ",a[i]);}else{printf("%d\n",a[i]);}}
#define allprintd(i,n,m,a) for(int i = n; i > m; i--){if(i != 0){printf("%d ",a[i]);}else{printf("%d\n",a[i]);}}

int top,si[1000];

void push(int x){
	si[++top] = x;
}
int pop(){
	top--;
	return si[top+1];
}

int main(void){
	int a, b;
	top = 0;
	char sc[100];

	while(scanc(sc) != EOF){
		if (sc[0] == '+'){
			a = pop();
			b = pop();
			push(a+b);

		}else if(sc[0] == '-'){
			b = pop();
			a = pop();
			push(a-b);

		}else if(sc[0] == '*'){
			a = pop();
			b = pop();
			push(a*b);
		}else{
			push(atoi(sc));
		}
	}
	printin(pop());
	return 0;
}


Measured memory_bytes: 2092
N = int(input())
V = list(map(int, input().rstrip().split()))
C = list(map(int, input().rstrip().split()))
sub = [V[i]-C[i] for i in range(N)]
sub_extract = [sub[i] for i in range(N) if sub[i] > 0]
print(sum(sub_extract))

Measured memory_bytes: 3060
import java.util.*;
import java.math.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		List<Double> paths = new ArrayList<>();
		int[] x = new int[n];
		int[] y = new int[n];
		for(int i = 0; i < n; i++) {
			x[i] = in.nextInt();
			y[i] = in.nextInt();
		}
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				double xdist = (double)Math.abs(x[i] - x[j]);
				double ydist =(double)Math.abs(y[i] - y[j]);
				double dist = Math.sqrt((xdist * xdist) + (ydist * ydist));
				paths.add(dist);
			}
		}
		double ans = 0.0;
		double fact = 1.0;
		if(n == 2) {
			ans = (double)paths.get(0);
			System.out.printf("%.10f", ans);
		}else {
			for(int i = 1; i < n - 1; i++) fact *= i;
			for(int i = 0; i < paths.size(); i++) {
				double temp = paths.get(i) * fact * (n - 1);
				temp *= 2;
				ans += temp;
			}
			ans /= fact * (n - 1) * n;
			System.out.printf("%.10f", ans);
		}
	}
}

Measured memory_bytes: 22740
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#
def main():
    h, w, k = MII()
    cc = [IS() for _ in range(h)]
    all_blacks = 0
    for c in cc:
        all_blacks += sum(1 for s in c if s == '#')
    cnt = 0
    for hbit in range(1<<h):
        blacks = all_blacks
        hb = []
        # 行を選ぶ
        for i in range(h):
            if hbit & (1<<i):
                hb.append(i)
        # 選んだ行の黒を取り除く
        for hbi in hb:
            blacks -= sum([1 for s in cc[hbi] if s == '#'])
        # すでにk個以下であればskip
        if blacks < k:
            continue

        # 列を選択
        for wbit in range(1<<w):
            wb = []
            for i in range(w):
                if wbit & (1<<i):
                    wb.append(i)
            # 列の黒を取り除く（ただし横で選んだ部分は重複させない）
            wblack = 0
            for wbi in wb:
                for i in range(h):
                    # 行で選ばれている場合はスキップ
                    if i in hb:
                        continue
                    if cc[i][wbi] == '#':
                        wblack += 1
            if blacks - wblack == k:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

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

    int 
main (void)
{
    int DP[21][156][11];
    memset(DP, 0, sizeof(DP));
    DP[0][0][0] = 1;

    for (int n = 1; n <= 20; n++)
    {   
        for (int s = 0; s <= 155; s++)
        {   
            for (int k = 0; k <= 10; k++)
                DP[n][s][k] = DP[n-1][s][k];
        }                                                                       
        for (int s = 0; s <= 155; s++)
        {   
            for (int k = 1; k <= 10; k++)
            {   
                if (s+n <= 155)
                    DP[n][s+n][k] += DP[n-1][s][k-1];
            }   
        }   
    }   

    while (1) 
    {   
        int N, K, S;
        cin >> N >> K >> S;
        if (N == 0)
            break;
        cout << DP[N][S][K] << endl;
    }   
    return 0;
}



Measured memory_bytes: 3256
try:
     (n)  =  int(input())
except:
    exit

hh = n // 3600
mm = (n % 3600 ) // 60
ss = n % 60

#print ('{:0=2}:{:0=2}:{:0=2}'.format(hh,mm,ss))
print ('{}:{}:{}'.format(hh,mm,ss))


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


int main(){
    const int MAX_N = 1e5+10;
    int N, A[MAX_N], ans = 0;
    cin >> N;
    for (int i = 0; i < N; ++i){
        cin >> A[i];
        ans += abs(A[i]);
    }
    sort(A, A+N);

    if (A[0]   > 0) ans -= 2*A[0];
    if (A[N-1] < 0) ans += 2*A[N-1];
    cout << ans << endl;

    int p = A[N-1];
    int n = A[0];
    for (int i = 1; i < N-1; ++i){
        if (A[i] <= 0){
            cout << p << " " << A[i] << endl;
            p -= A[i];
        }
        if (A[i] > 0){
            cout << n << " " << A[i] << endl;
            n -= A[i];
        }
    }
    cout << p << " " << n << endl;

    return 0;
}

Measured memory_bytes: 2304
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <bitset>
using namespace std;

constexpr int div_up(int const x,int const y){return (x+y-1)/y;}

int stupid(vector<int> const &v){
  vector<int> r={0};
  for (int i: v)
    for (int j=r.size(); j--;)
      r.push_back(r[j]+i);
  sort(r.rbegin(),r.rend());
//  for (auto i: r) cout<<" "<<i; cout<<endl;
  return r[(r.size()-1)/2];
}

namespace thing{
  constexpr int size=div_up(2000*2000,64);
  static uint64_t possible[size];

  void init(){
    possible[0]=1;
  }

  void update(int x){
    int const diff_big=x/64;
    uint16_t const diff_small=x%64;
    uint16_t const ffid_small=64llu-diff_small;

    if (diff_small){
      for (int i=size; i-->diff_big+1;){
        possible[i] |= (possible[i-diff_big] << diff_small);
        possible[i] |= (possible[i-diff_big-1] >> ffid_small);
      }
      for (int i=diff_big+1; i-->diff_big;){
        possible[i] |= (possible[i-diff_big] << diff_small);
      }
    }else{
      for (int i=size; i-->diff_big;){
        possible[i] |= (possible[i-diff_big] << diff_small);
      }
    }
  }
};

int solve(vector<int> const &v){
  int const total=accumulate(v.begin(),v.end(),0);
  int const want=(total+1)/2;

  thing::init();
  for (int x: v) thing::update(x);

  for (int i=want; i<=total; i++)
    if (thing::possible[i/64]&(1llu<<(i%64llu)))
      return i;
}

int main(){
  int n; cin>>n;
  vector<int> v(n); for (auto &i: v) cin>>i;
  sort(v.begin(),v.end());
  cout<<solve(v)<<endl;
}

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


int main() {
  int n,m; cin>>n;
  vector<string>  vecb(n),vecr(m);
  for(int i=0;  i<n; i++)cin>>vecb.at(i);
  cin>>m;
  for(int i=0;  i<m; i++)cin>>vecr.at(i);
  int nb,nr,ans=0;
  for(int i=0;  i<n; i++){
    nb=count(vecb.begin(),vecb.end(),vecb.at(i));
    nr=count(vecr.begin(),vecr.end(),vecb.at(i));
   // cout<<i<<" "<<nb<<" "<<nr<<" "<<nb-nr<<endl;
    ans= max(nb-nr,ans);
  }
  cout<<ans;
}






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

int main() {
    int n, l;
    cin >> n >> l;

    int taste = 0;
    int taste_sum = 0;
    for ( int i = 0; i < n; i++ ) {
        taste = l + i;
        taste_sum += taste;
    }

    int tmp_taste = 0;
    int taste_nearest = 0;
    for ( int i = 0; i < n; i++ ) {
        tmp_taste = taste_sum - ( l + i );
        if ( std::abs( taste_sum - tmp_taste ) < std::abs( taste_sum - taste_nearest ) ) {
            taste_nearest = tmp_taste;
        }
    }

    cout << taste_nearest << endl;

    return 0;
}

Measured memory_bytes: 256
import math

x, n = map(int, input().split(" "))
ps = input()
if ps == "":
    print(x)
    exit()
ps = sorted(list(map(int, ps.split(" "))))

if not x in ps or len(ps) == 0:
    print(x)
    exit()

g = 1
while True:
    if not (x - g in ps):
        print(x - g)
        exit()
    if not (x + g in ps):
        print(x + g)
        exit()
    g += 1
    if g == 101:
        print(0)
        exit()


Measured memory_bytes: 9208
#include <vector> 
#include <list> 
 #include <map>
 #include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << #x << '=' << (x) << endl;
#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;


#define yes cout<<"Yes"<<endl;
#define no cout<<"No"<<endl;

int main(){
 
    LL N;
    cin>>N;
    LL max_=0;
    for(LL i=1;i*i<=N;i++){
        max_=max(i*i,max_);
    }
    cout<<max_<<endl;




}


Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
const double pi = acos(-1) ;
signed main(){
    fastio
    int r ;
    cin >> r ;
    cout << fixed << setprecision(12) << r * pi * 2.0 << endl;
    return 0; 
}

Measured memory_bytes: 3792
#include <iostream>
using namespace std;
int main() {
	int h, w;
	string s[100];
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < h; i++) {
		cout << s[i] << "\n" << s[i] <<  endl;
	}
	return 0;
}

Measured memory_bytes: 256
n = list(map(int, list(input())))
n.reverse()
n.append(0)
l = len(n)
cnt = 0
for i in range(l):
    if n[i] <= 4:
        cnt += n[i]
    elif n[i] == 5:
        if n[i+1] >=5:
            cnt += 10-n[i]
            n[i+1] += 1
        else:
            cnt += n[i]
    else:
        cnt += 10-n[i]
        n[i+1] += 1
print(cnt)

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

unsigned euclidean_gcd(unsigned a, unsigned b) {
  if(a < b) euclidean_gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){long N, X;
cin >> N >> X;
vector<long> x(N + 1);
erep(i, N) cin >> x.at(i);
erep(i, N) x.at(i) = abs(x.at(i) - X);
long ans = x.at(1);
erep(i, N - 1){
    ans = euclidean_gcd(ans, x.at(i + 1));
}

// int ans = euclidean_gcd(12, 16);



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




Measured memory_bytes: 1024
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD1 1000000007



int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  rep(i, N) cin >> d.at(i);

  sort(all(d));

  int ans = 1;

  rep(i, N - 1) {
    if (d.at(i) < d.at(i + 1)) ans++ ;
  }

  cout << ans << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

signed main() {
	// your code goes here
	fast
	ll n;
	cin>>n;
    ll h[n];
    for(ll i=0;i<n;i++)
        cin>>h[i];
    ll dp[n];
    dp[0]=0;
    dp[1]=fabs(h[1]-h[0]);
    for(ll i=2;i<n;i++)
    {
        dp[i]=min(dp[i-1]+fabs(h[i]-h[i-1]),dp[i-2]+fabs(h[i]-h[i-2]));
    }
    // for(ll i=0;i<n;i++)
    //     cout<<dp[i]<<" ";
    cout<<dp[n-1]<<endl;
	return 0;
}


Measured memory_bytes: 1920
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


struct p{
  int a;
  int b;
};

//int friendList[10001][10001];
//int blockList[10001][10001];

using Graph = vector<vector<int>>;

vector<bool> seen;

struct UnionFind{
  vector<int> d;
  UnionFind(int n) : d(n+1,-1) {}

  int root(int x){
    if(d[x] < 0){
      return x;
    }
    else{
      return root(d[x]);
    }

  }
  
  bool unite(int x,int y){

    x = root(x);
    y = root(y);

    if(x == y){
      return false;
    }
    else{
      if(size(x) > size(y)){
        swap(x,y);
      }
      d[y] += d[x];
      d[x] = y;
      return true;
    }

  }

  bool same(int x,int y){
    if(root(x) == root(y)){
      return true;
    }
    else{
      return false;
    }
  }

  int size(int x){
    return -d[root(x)];
  }
  
  
};

void dfs(const Graph &g,int v,UnionFind* uf,int root){
  seen[v] = true;

  for(auto next_v : g[v]){
    if(seen[next_v]) continue;
    uf->unite(root,next_v);
    dfs(g,next_v,uf,root);
  }
  
}



int main(){
  
  lll ii,jj,kk;
  vector<int> ret;

  int n,m,k;

  cin >> n >> m >> k;

  vector<struct p> friends(m);
  vector<struct p> block(k);

  set<int> friendSet[n+1];
  set<int> blockSet[n+1];  

  Graph g(n+1);
  seen.resize(n+1);
  
  int a,b,c,d;

  //フレンドリスト
  for(ii=0;ii<m;ii++){
    cin >> a >> b;
    struct p pp;

    pp.a = a;
    pp.b = b;
    
    friends.push_back(pp);

    friendSet[a].insert(b);
    friendSet[b].insert(a);
    g[a].push_back(b);
    g[b].push_back(a);
    //cout <<"a:" << a << "b" << b << endl;
  }

  struct p p1;

  //拒否リスト
  for(ii=0;ii<k;ii++){
    cin >> c >> d;
    //pp = (p*)malloc(sizeof(struct p));
    p1.a = c;
    p1.b = d;
    //cout <<"c:" << c << "d" << d << endl;    
    block[ii].a = c;
    block[ii].b = d;
    //block.push_back(p1);

    blockSet[c].insert(d);
    blockSet[d].insert(c);
    
  }

 // for(ii=0;ii<block.size();ii++){
 //   cout <<"a:" << block[ii].a << "b" << block[ii].b << endl;
 // }
  
  //cout << "serach Friend!" << endl;

  vector<set<int>> comb;
  int combNum = 0;

  UnionFind uf(n);
  int root;

  for(ii=1;ii<=n;ii++){
    
    if(!seen[ii]){

      set<int> s;
      root = ii;
      dfs(g,ii,&uf,root);
      comb.push_back(s);
      combNum++;

    }
    
  }

  //cout << combNum << endl;

  int fc[n+1];
  for(ii=1;ii<=n;ii++){
    //cout << "ii:" << ii << " " << uf.size(n) << " " << endl;
    fc[ii] = uf.size(ii) - friendSet[ii].size() -1;
  }



  for(ii=0;ii<k;ii++){
    //cout << "size:" << block.size() << endl;
    
    a = block[ii].a;
    b = block[ii].b;
    
    //cout <<"a:" << a << "b" << b << endl;
    if(uf.same(a,b)){
      fc[a]--;
      fc[b]--;
    }
  }

  for(ii=1;ii<=n;ii++){
    cout << fc[ii] << " ";
  }  
  //  for(ii=1;ii<=n;ii++){
//    for(jj=1;jj<=n;jj++){
//      if(
//    }
//  }

  //
  return 0;
}


Measured memory_bytes: 44060
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
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 = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

int main(){
    ll n,ans=0;
    cin >> n;
    for (ll i=0;i<n;i++){
        ll a;
        cin >> a;
        while(a%2==0){
            ans++;
            a/=2;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
    int n,l;
    cin >> n >> l;
    string s[n],t;
    rep(i,n) cin >> s[i];
    sort(s,s+n);
    rep(i,n){
        t += s[i];
    }
    cout << t << endl;
}

Measured memory_bytes: 256
n, W = map(int, input().split())
w = []
v = []
for _ in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

dp = [[float('inf') for j in range(10**5+1)] for i in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(10**5+1):
        if j < v[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]] + w[i])
ans = 0
for i in range(10**5,-1,-1):
    if dp[n][i] <= W:
        ans = i
        break
print(ans)

Measured memory_bytes: 320576
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define fi first
#define se second
const int MAX = 200000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;

int32_t main()
{
	int a, b, c;
	cin >> a >> b >> c;

	swap(a, b);
	swap(a, c);
	
	cout << a << ' ' << b << ' ' << c << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<string>
#include<math.h>
#define pi 3.141592653589
#include<iomanip>
#include<vector>
using namespace std;
#include<algorithm>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define INF 1e9
#define LINF 1e17
#define ll long long
#define MOD (int)(1e9+7)

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



int main() {

	int n, bef;
	string s[2];
	ll cnt;

	cin >> n >> s[0] >> s[1];
	rep(i, 0, n) {
		if (i == 0) {
			if (s[0][i] == s[1][i]) {
				cnt = 3;
				bef = 0;
			}
			else {
				cnt = 6;
				bef = 1;
				i++;
			}
		}
		else {
			if (s[0][i] == s[1][i]) {
				if (bef == 0) cnt = (cnt * 2) % MOD;
				else cnt = (cnt * 1) % MOD;
				bef = 0;
			}
			else {
				if (bef == 0) cnt = (cnt * 2) % MOD;
				else cnt = (cnt * 3) % MOD;
				i++;
				bef = 1;
			}
		}
	}
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1<<30)

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

void Main(){
  int N, M; cin >> N >> M;
  cout << (pow(2.0, M) * (1900 * M + 100 * (N - M))) << endl;
}

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

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

  Main();
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

def converter(n):
    L ="zabcdefghijklmnopqrstuvwxy"
    return L[n]

def solve(N: int):
    ans = ""
    num = N
    while True:
        p = num // 26
        q = num % 26
        ans = converter(q) + ans
        if q == 0:
            p -= 1
        if p <= 0:
            break
        num = p

    print(ans)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9212
import std.stdio;
import std.string;
import std.algorithm;

string[] s;
int[500][500] memo;
int h, w, ans;

void main(){
	while (readf("%d %d\n", &h, &w), h != 0 || w != 0) {
		s = [];
		for (int i = 0; i < h; i++) {
			s ~= chomp(readln());
		}
		for (int y = 0; y < h; y++) {
			for (int x = w-1; x >= 0; x--) {
				memo[y][x] = calcWidth(x, y);
			}
		}
		ans = 0;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				ans = max(ans, solve(x, y));
			}
		}
		writeln(ans);
	}
}

int calcWidth(int x, int y){
	int result = 1;
	if(s[y][x] == '*') return 0;
	if(x+1 < w) result += memo[y][x+1]; 
	return result;
}

int solve(int x, int y){
	int result = 0;
	int minWidth = 9999;
	for (int i = y; i < h; i++) {
		minWidth = min(minWidth, memo[i][x]);
		if(minWidth == 0) break;
		result = max(result, minWidth * (i-y+1));
	}
	return result;
}

Measured memory_bytes: 2516
T = input()
P = input()

if len(P) > len(T):
    pass
else:
    p = len(P)
    ans = []
    for i in range(len(T)-len(P)+1):
        tmp = ""
        for j in range(i,i+p):
            tmp += T[j]
        if tmp == P:
            ans.append(i)
    
    for i in ans:
        print(i)


Measured memory_bytes: 5576
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <random>
#include <set>
#include <stack>
#include <time.h>

//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater<int>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

using namespace std;
using ll = long long;
typedef std::pair<int,int> pii;
typedef std::vector<int> vi;
typedef std::vector<pii> vii;

#define PI 3.14159265358979323846264338327950L
const int mod = 1000000007;


void solve(){
    int n;
    cin >> n;
    int i = 0;
    while(i*1000 < n){
    i++;}
    cout << i*1000-n;
}

int main(){
    int T;
    T = 1;
    while(T--){
        solve();
        cout << endl;
    }
}






Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main()
{ long long n,temp=0;
  cin>>n;
   for(long long i=n;i>0;){
         temp=temp+(i%10);
        i=i/10;
    }
    if(n%temp==0)cout<<"Yes\n";
    else cout<<"No\n";
   return 0;
}


Measured memory_bytes: 256
/*
  AOJ #3027
  title:OOllOll
  @kankichi57301
 */
#include <stdio.h>


int main()
{
  int r,n;
  scanf("%d",&n);
  r=0;n++;
  while(n>1)
    n /= 2,r++;

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



Measured memory_bytes: 2120
#include<bits/stdc++.h>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

int main(){
    int N;
    ll Y;
    cin >> N >> Y;
    bool flag = true;
    rep(i, N+1){
        rep(j, N+1 - i){
            if (i*10000 + j * 5000 + (N - i - j) * 1000 == Y && flag) {
                cout << i << " " << j << " " << N - i - j << endl;
                flag = false;
            }
        }
    }

    if (flag) cout << -1 << " " << -1 << " " << -1 << endl;
}

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

typedef long long ll;
typedef vector<ll> vint;
typedef vector< vector<ll> > vvint;

#define rep(i,n) for(ll i=0;i<n;i++)
#define repf(i,f,n) for(ll i=f;i<n;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define mp make_pair
#define mt make_tuple
#define ALL(obj) (obj).begin(), (obj).end()
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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


int main() {
    cout<<fixed<<setprecision(10);

    ll l,r,d; cin>>l>>r>>d;

    ll ans = 0;
    repf(i,l,r+1){
        if(i%d==0) ans++;
    }
    cout<<ans<<endl;

    return 0;

}

Measured memory_bytes: 3592
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>

using namespace std;
const int Max = 1e6 + 5;
typedef long long ll;
ll sum;
int a[Max];

int main(){
	int n, m;
	while(~scanf("%d", &n)){
		sum = 0;
		for(int i = 0; i < n; i++) { scanf("%d", &a[i]); sum += a[i]; }
		sort(a, a + n, greater<int>());
		sum -= a[0];
		if(a[0] < sum) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	return 0;
}

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

int main() {
  int l, n;

  cin >> n >> l;

  vector<string> s(n);

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

  sort(s.begin(), s.end());

  for (int i = 0; i < n; i++) {
    cout << s[i];
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
template<class T>bool chmax(T &a, const T &b) {if(a<b) {a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) {if(b<a) {a=b; return 1;} return 0;}
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=998244353;

//for(i=0; i<N; i++) cin >> a[i];


ll f(ll a, ll b, ll c) {
  return a*a+b*b+c*c+a*b+b*c+c*a;
}

int main(void) {
  ll i, j, k;
  
  ll N;
  cin >> N;
  
  map<ll, ll> mp;
  for(ll x=1; x<=100; x++) {
    for(ll y=1; y<=100; y++) {
      for(ll z=1; z<=100; z++) {
        mp[f(x, y, z)]++;
      }
    }
  }
  
  for(i=1; i<=N; i++) pt(mp[i]);
  
}
 
 




Measured memory_bytes: 5896
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;cin>>N;
    vector<int> v(N);
    for(int i=0;i<N;i++){
        cin>>v[i];
    }
    sort(v.begin(),v.end());
    double ans;ans=v[0];
    for(int i=1;i<N;i++){
        ans=(ans+v[i])/2;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class MyClass
{
    static string Reverse(string str)
    {
        string str2 = "";
        foreach (var item in str)
        {
            str2 = item + str2;
        }
        return str2;
    }

    static List<string> Add(string str, List<string> list)
    {
        if (!list.Contains(str))
        {
            list.Add(str);
        }
        return list;
    }

    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        for (int x = 0; x < n; x++)
        {
            string str = Console.ReadLine();
            List<string> list = new List<string>();
            for (int i = 0; i < str.Length - 1; i++)
            {
                string a = "";
                string b = "";
                for (int j = 0; j < str.Length; j++)
                {
                    if (i >= j)
                    {
                        a += str[j];
                    }
                    else
                    {
                        b += str[j];
                    }
                }
                list = Add(a + b, list);
                list = Add(Reverse(a) + b, list);
                list = Add(a + Reverse(b), list);
                list = Add(Reverse(a) + Reverse(b), list);
                list = Add(b + a, list);
                list = Add(Reverse(b) + a, list);
                list = Add(b + Reverse(a), list);
                list = Add(Reverse(b) + Reverse(a), list);
            }
            Console.WriteLine(list.Count);
        }
    }
}


Measured memory_bytes: 6044
N = int(input())
h = list(map(int,input().split()))
n = 2
cost = [0]*N
cost[1] = abs(h[1]-h[0])
for n in range(2,N):
    cost[n] = min(cost[n-1]+abs(h[n-1]-h[n]),cost[n-2]+abs(h[n-2]-h[n]))
    
print(cost[N-1])

Measured memory_bytes: 84104
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>
#include <set>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

using LL = long long;

constexpr long long INF = 1e12;

//配るDP
int main() {

    int N;
    cin >> N;

    vector<LL> h(N);
    for (int i = 0; i < N; i++) cin >> h[i];

    vector<LL> dp(N, INF);
    dp[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= 2; j++) {
            int to = min(i + j, N - 1);
            dp[to] = min(dp[to], dp[i] + abs(h[to] - h[i]));
        }
    }

    cout << dp[N - 1] << endl;

    return 0;
}
















































Measured memory_bytes: 1920
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;


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

    vector<vector<char>> grid(n, vector<char>(n));
    rep(y, n) rep(x, n) cin >> grid[y][x];

    bool is_all_white = [&] {
        rep(y, n) rep(x, n) if (grid[y][x] == '#') return false;
        return true;
    }();

    if (is_all_white) {
        cout << -1 << endl;
        ret();
    }

    int mi = INT_MAX;
    auto x = [&](int i) {
        int b = 0;
        int w = 0;
        rep(j, n) if (grid[i][j] == '#') b++; else w++;

        bool has_b = [&] {
            rep(j, n) if (grid[j][i] == '#') return true;
            return false;
        }();

        if (has_b) return w;
        return w + 1;
    };
    rep(i, n) cmin(mi, x(i));

    int c = [&] {
        int ans = 0;
        rep(i, n) {
            bool b = [&] {
                rep(j, n) {
                    if (grid[j][i] == '.') return true;
                }
                return false;
            }();
            if (b) ans++;
        }
        return ans;
    }();

    cout << c + mi << endl;
}


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

#ifdef DEBUG
#define PRINT(x)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#x<<" = "<<(x)<<endl;
#define PRINTA(a,first,last)\
    cout<<"func "<<__func__<<": line "<<__LINE__<<": "<<#a<<"["<<(first)<<", "<<(last)<<")"<<endl;\
    for (int i=(first);i<(last);++i){cout<<#a<<"["<<i<<"] = "<<(a)[i]<<endl;}
#else
#define PRINT(x)
#define PRINTA(a,first,last)
#endif

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <class T, class U> void amax(T& x, U y) {if (x < y) x = y;}
template <class T, class U> void amin(T& x, U y) {if (x > y) x = y;}

int main(void)
{
    int N;
    int d[100];
    cin >> N;
    REP(i, N) cin >> d[i];
    sort(d, d + N);
    PRINTA(d, 0, N);
    int result = 0;
    int before = -1;
    REP(i, N) {
        if (d[i] != before) {
            result++;
            before = d[i];
        }
    }
    cout << result << endl;
    return 0;
}


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

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

int main(){
    int N;
    string S, T;
    cin >> N;
    cin >> S >> T;
    rep(i,N){
        cout << S.at(i)<<T.at(i);
    }
    cout << endl;
    return 0;
}

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

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);i--)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
//constexpr long long MOD = (ll) 1e9 + 7;
constexpr long long MOD = 998244353LL;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


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

struct Edge {
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve(){
    ll n;
    cin>>n;
    Array a(n);
    REP(i,n) cin>>a[i];

    ll ans=0;
    ll con=0;
    ll mi=INF;
    REP(i,n){
        if(a[i]<0){
             ans-=a[i];
             con++;
             chmin(mi,-a[i]);
        }
        else{
            ans+=a[i];
            chmin(mi,a[i]);
        }
    }
    if(con%2==0) cout<<ans<<en;
    else cout<<ans-2*mi<<en;
}

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

    solve();
    //ll t;cin>>t;REP(i,t) solve();

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 5010;
struct edge {
  int la,b;
} con[N];
int tot,fir[N];
void add(int from,int to) {
  con[++tot] = (edge) {fir[from],to};
  fir[from] = tot;
}
bitset<M> bit; 
int ned[N],n,dp[N];
bool dfs(int pos) {
  int lea = 0, sum = 0;
  for (int i = fir[pos] ; i ; i = con[i].la) {
    if (!dfs(con[i].b)) return 0;
    lea += min(ned[con[i].b],dp[con[i].b]);
    sum += ned[con[i].b] + dp[con[i].b];
  }
  if (lea > ned[pos]) return 0;
  bit.reset();
  bit[0] = 1;
  for (int i = fir[pos] ; i ; i = con[i].la)
    bit |= (bit << (abs(ned[con[i].b] - dp[con[i].b])));
  for (int i = ned[pos] - lea ; i >= 0 ; -- i) {
    if (bit[i]) {
      dp[pos] = sum - i - lea;
      break;
    }
  }
  return 1;
}
int main() {
  int x;
  scanf("%d",&n);
  for (int i = 2 ; i <= n ; ++ i) {
    scanf("%d",&x);
    add(x,i);
  }
  for (int i = 1 ; i <= n ; ++ i)
    scanf("%d",&ned[i]);
  if (dfs(1)) puts("POSSIBLE");
  else puts("IMPOSSIBLE");
  return 0;
}


Measured memory_bytes: 768
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define per(i,a) ROF(i,a,0)
#define pb push_back
using namespace std;
using ll=long long;
using ld=long double;
using ch=char;
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vP;
typedef vector<ch> vc;
typedef vector<vc> vvc;
const ll MOD=1000000007;
const ll MOD2=998244353;
const ld PI=acos(-1);
const ll INF=1e18;
struct edge{ll to,cost;};
struct edge2{ll from,to,cost;};

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

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

ll N,cnt1,cnt2,cnt3;
ld dp[301][301][301];

ld dfs(ll c1,ll c2,ll c3){
    if(dp[c1][c2][c3]>=0){
        return dp[c1][c2][c3];
    }
    if(c1==0&&c2==0&&c3==0){
        dp[0][0][0]=0;
        return 0;
    }
    ld res=1/(1-(ld)(N-c1-c2-c3)/N);
    if(c1>0){
        res+=dfs(c1-1,c2,c3)*c1/N/(1-(ld)(N-c1-c2-c3)/N);
    }
    if(c2>0){
        res+=dfs(c1+1,c2-1,c3)*c2/N/(1-(ld)(N-c1-c2-c3)/N);
    }
    if(c3>0){
        res+=dfs(c1,c2+1,c3-1)*c3/N/(1-(ld)(N-c1-c2-c3)/N);
    }
    dp[c1][c2][c3]=res;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    cnt1=0,cnt2=0,cnt3=0;
    rep(i,N){
        int a;
        cin >> a;
        if(a==1)cnt1++;
        if(a==2)cnt2++;
        if(a==3)cnt3++;
    }
    rep(i,301){
        rep(j,301){
            rep(k,301){
                dp[i][j][k]=-1;
            }
        }
    }
    cout << fixed << setprecision(10) << dfs(cnt1,cnt2,cnt3) << endl;
}
/*
overflow checked?
corner case checked?
boundary checked?
not TLE in worst case checked?
*/

Measured memory_bytes: 429956
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N,M = map(int,input().split())
d = defaultdict(list)
for _ in range(N):
    a,b = map(int,input().split())
    d[a].append(b)
Q = [] 
heapify(Q)
s = 0
for i in range(1,M+1):
    li = d[i]
    for k in li:
        heappush(Q,-k)
    if len(Q) == 0:
        continue
    c = heappop(Q)
    s += -c
print(s)

Measured memory_bytes: 37468
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        k: i64,
    }

    let mut ans: i64 = -1;
    let mut count = 0;
    let mut a = 0;

    while count <= k {
        let b = (10 * a + 7) % k;
        count += 1;

        if b == 0 {
            ans = count;
            break;
        } 
        
        a = b;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2196
N = int(input())
As = list(map(int, input().split()))

if len(set(As)) >= 3:
    print("No")
    exit()
elif len(set(As)) == 1:
    print("Yes" if 1 <= As[0] <= N // 2 or As[0] == N - 1 else "No")
    exit()
else:
    p, q = sorted(set(As))
    if p + 1 != q:
        print("No")
        exit()
    t = As.count(p)
    u = N - t
    if t + 1 <= q <= t + u // 2:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 87676
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <list>
#include <cmath>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <set>
using ll = long long;
using namespace std;

int main()
{
    int N;
    cin >> N;
    int x;
    int ans = 0;
    int m = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> x;
        m = max(m, x);
        ans += x;
    }
    cout << ans - m / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <time.h>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define reps(x,c) for(auto x:c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a) 
#define mp(a,b) make_pair((a),(b))
#define pl pair<ll,ll>
#define INF 2147483600
#define fi first
#define se second
#define dbg(x) cout << #x"="<< (x) << endl

int main(){
  ll n,c;cin>>n>>c;
  vector<ll> x(n),v(n);
  rep(i,n){
    cin>>x[i]>>v[i];
  }

  vector<ll> sum(n),sum_c(n);
  sum[0]=v[0];
  sum_c[0]=v[n-1];
  FOR(i,1,n){
    sum[i]=sum[i-1]+v[i];
    sum_c[i]=sum_c[i-1]+v[n-i-1];
  }

  vector<ll> invx(n);
  rep(i,n){
    invx[i]=c-x[n-i-1];
  }

  vector<ll> consume(n),consume_c(n);
  vector<ll> consume_b(n),consume_c_b(n);
  ll max_f=-1,max_c=-1;
  rep(i,n){
    consume[i]=sum[i]-x[i];
    consume_b[i]=consume[i]-x[i];
    consume_c[i]=sum_c[i]-invx[i];
    consume_c_b[i]=consume_c[i]-invx[i];
    max_f=max(max_f,consume[i]);
    max_c=max(max_c,consume_c[i]);
  }

  vector<ll> max_v(n),max_c_v(n);
  max_v[0]=consume[0];
  max_c_v[0]=consume_c[0];
  FOR(i,1,n){
    max_v[i]=max(consume[i],max_v[i-1]);
    max_c_v[i]=max(consume_c[i],max_c_v[i-1]);
  }
  ll ans=max(max_f,max_c);ans=max(ans,0ll);
  rep(i,n-1){
    ans=max(ans,consume_b[i]+max_c_v[n-i-2]);
    ans=max(ans,consume_c_b[i]+max_v[n-i-2]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 8960
# 写経しましたが、何もわかっていません。

def floor_sum(n, m, a, b):
    "Return sum( floor( (A * i + B) / M ) for i in range(N) )"
    ret = 0
    while True:
        if a >= m:
            ret += ((n - 1) * n) // 2 * (a // m)
            a %= m
        if b >= m:
            ret += n * (b // m)
            b %= m
        y_max = (a * n + b) // m
        x_max = y_max * m - b
        if y_max == 0:
            return ret
        ret += (n - (x_max + a - 1) // a) * y_max
        n, m, a, b = y_max, a, m, (a - x_max % a) % a
    
    return ret

def main():
    import sys
    input = sys.stdin.buffer.readline

    ans = []
    T = int(input())
    for _ in range(T):
        N, M, A, B = map(int, input().split())
        ans.append(floor_sum(N, M, A, B))

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


if __name__ == "__main__":
    main()

Measured memory_bytes: 79736