akhauriyash/Code-Regression huggingface dataset:
n, q = map(int, input().split())
ki = [0]*(n+1)
for i in range(n-1):
  a, b = map(int, input().split())
  ki[b] = a

c = [0]*(n+1)
for i in range(q):
  p, x = map(int, input().split())
  c[p] += x

for i in range(1, n+1):
  c[i] += c[ki[i]]

print(" ".join(map(str, c[1:])))

Measured memory_bytes: 36896
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
 
int main() {
    int n, x;
    cin >> n >> x;
    vector<int> l(n);
    rep (i, n) cin >> l[i];
    int current_x = 0, count = 1;
    while (current_x <= x && count <= n) {
        current_x += l[count - 1];
        if (current_x <= x) count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

# In[86]:


# ans = [0]*(len(S)+1)
# for i in range(len(S)):
#     count_left = 0
#     count_right = 0
#     for j in range(i):
#         if S[i-j-1] == "<":
#             count_left += 1
#         else:
#             j -= 1
#             break
#     for k in range(i,len(S)):
#         if S[k] == ">":
#             count_right += 1
#         else:
#             k -= 1
#             break
#     ans[i] = max(count_left, count_right)
# #     print(count_left, count_right)
# #     print(S[i-j-1:i], S[i:k+1])
# # print(ans)
# print(sum(ans))


# In[87]:


from collections import deque
S = input()
left = deque([0])
right = deque([0])
cnt = 0
for s in S:
    if s == '<':
        cnt += 1
    else:
        cnt = 0
    left.append(cnt)
cnt = 0
for s in S[::-1]:
    if s == '>':
        cnt += 1
    else:
        cnt = 0
    right.appendleft(cnt)
ans = 0
for l, r in zip(left, right):
    ans += max(l, r)
print(ans)


# In[ ]:






Measured memory_bytes: 28448
require 'pp'

n = gets.chomp!.to_i
p_n = gets.chomp!.split(" ").map(&:to_i)

counter = 0
i = 0
while i < n
    if i + 1 == p_n[i]
        counter += 1
        if i + 2 == p_n[i + 1]
            i += 1
        end
    end
    i += 1
end

puts counter


Measured memory_bytes: 8668
#include <iostream>
#include<string>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main()
{
	string s;
	cin >> s;
	int k;
	cin >> k;
	for(int i=0;i<k;i++) {
		if (s[i] != '1') { cout << s[i] << endl; return 0; }
	}
	cout << 1 << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int a[20];
int main()
{
	long long  b,c,d=0,q=1;
	int z=0;
	cin>>b>>c;
	if(b>=0&&c>=0)
	cout<<"Positive"<<endl;
    if(b<=0&&c>=0)
    cout<<"Zero"<<endl;
    if(b<0&&c<=0)
    {
    	for(int i=b;i<=c;i++)
		{
			if(i<=c)
			{
			z++;	
			}
		}
    	if(z%2==0)
    	{
    		cout<<"Positive"<<endl;
    	}
    	else cout<<"Negative"<<endl;
    	
    }
    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#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>

using namespace std;

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

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


#define FILL(ptr, value) FILL_((ptr), sizeof(ptr)/sizeof(value), (value))
 
template <typename T>
void FILL_(void * ptr, size_t size, T value){
  std::fill((T*)ptr, (T*)ptr+size, value);
}
 

ll dp[101][100001];

int main(){
    std::ios::sync_with_stdio(false);
    int n, w;
    cin >> n >> w;
    ll weight[n] = {};
    int value[n] = {};

    for(int i=0;i<n;++i)
    {
        cin >> weight[i] >> value[i];
    }
    FILL(dp, 1ll << 62);
    dp[0][0] = 0;

    for(int i=0;i<n;++i)
    {
        for(int j=0;j<=100000;++j)
        {
            if(dp[i][j] + weight[i] <= w)
            {
                dp[i+1][j + value[i]] = min(dp[i+1][j + value[i]], dp[i][j] + weight[i]);
            }
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        }
    }
    
    for(int i=100000;i>0;--i)
    {
        if(dp[n][i] != (1ll << 62))
        {
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 79232
N = int(input())

def searcher(n):
	a, b = 0, 0
	while b*7 <= n:
		if (b*7) == n:
			return True
		a = 0
		while a*4 + b*7 <=n:
			if a*4 + b*7 == n :
				return True
			a += 1
		b += 1
	else:
		return False


if searcher(N):
	print("Yes")
else:
	print("No")

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    int n;
    cin>>n;
    bool flag=true;
    string s;
    while(flag){
        s=to_string(n);
        if(s[0]==s[1]&s[0]==s[2]){
            flag=false;
        }
        n++;
    }
    cout<<n-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <cmath>
#include <set>
using namespace std;

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

    vector<string> a(1001);
    for (int i = 0; i < 10; i++) {
        a[i] = "00" + to_string(i);
    }
    for (int i = 10; i < 100; i++) {
        a[i] = "0" + to_string(i);
    }
    for (int i = 100; i < 1000; i++) {
        a[i] = to_string(i);
    }

    /*
    for (int i = 0; i < 1000; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
    */

    bool st[1010] = {false};
    for (int i = 0; i < 1000; i++) {
        string b = a[i];
        int k = 0;
        for (int j = 0; j < n; j++) {
            if (b[k] == s[j]) k++;
            if (k == 3) st[i] = true;
        }
    }

    int ans = 0;
    for (int i = 0; i < 1000; i++) {
        if (st[i]) ans++;
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
	ll n,x,t;
	cin >> n >> x >> t;
	ll ans = t * ((n + x - 1)/x);
	cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3628
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
d={}
for i in a:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
p=max(a)*2
chk=[pow(2,i) for i in range(1,32) if pow(2,i)<=p]
ans=0
for i in a[::-1]:
    if d[i]>0:
        d[i]-=1
        for j in chk[::-1]:
            if j-i in d and d[j-i]>0:
                d[j-i]-=1
                ans+=1
                break
print(ans)

Measured memory_bytes: 110420
#include<iostream>
#include<math.h>
#include<string>
#include<algorithm>
using namespace std;

int main(){
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	sort(a,a+3);
	if(a[0]==5&&a[1]==5&&a[2]==7)cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector <int>v[100009];
long long d[100006][2],i,x,y,n;
long long dp(int x,int y,int z){
    if(z>1) return 0;
    if(d[x][z]) return d[x][z];
    long long s=0;
    d[x][z]=1;
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=y) {
            d[x][z]*=dp(v[x][i],x,0);
            d[x][z]%=1000000007;
            ++s;
        }
    if(s==0) return d[x][z]=2-z;
    if(z) return d[x][z];
    s=1;
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=y) {
            s*=dp(v[x][i],x,1);
            s%=1000000007;
        }
    d[x][z]=(d[x][z]+s)%1000000007;
    return d[x][z];
}
int main()
{
    cin>>n;
    for(i=0;i<n-1;i++) {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    cout<<dp(1,0,0);
    return 0;
}


Measured memory_bytes: 15616
S=input()
ans1=0
ans2=0
for i in range(len(S)):
	if i%2==0:
		if S[i]!='0':
			ans1+=1
	else:
		if S[i]!='1':
			ans1+=1
for i in range(len(S)):
	if i%2==0:
		if S[i]!='1':
			ans2+=1
	else:
		if S[i]!='0':
			ans2+=1
print(min(ans1,ans2))

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef vector<int> vi;
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define rint register int
#define SZ(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (rint it = (f); it <= (e); ++it)
#define per(it, f, e) for (rint it = (f); it >= (e); --it)
#define repe(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)
const int MAXN = 1e6 + 20;
int a[MAXN];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n;
	string s;
	cin >> n >> s;
	rep (i, 1, n) {
		a[i] = s[i - 1] - '0';
	}
	int flag = 2;
	rep (i, 1, n) {
		if (a[i] == 2) flag = 1;
	}
	int res = 0;
	if (flag == 2) {
		rep (i, 1, n) {
			a[i] = a[i] == 3;
		}
	}
	auto C = [&] (int n, int m) {
		return (n & m) == m;
	};
	rep (i, 1, n) if (a[i] & 1) {
		res ^= C(n - 1, i - 1);
	}
	cout << flag * res << endl;
	return 0;
}

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

int main()
{
  int N, K;
  while (scanf("%d %d ", &N, &K) == 2) {
    if (N == 0 && K == 0) {
      break;
    }
    //    printf("(N, K) = (%d, %d)\n", N, K);
    vector<int> S(K);
    for (int i = 0; i < K; i++) {
      int s;
      scanf("%d ", &s);
      S[i] = s;
    }
    
    bool flag = true;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < K; j++) {
	int b;
	scanf("%d ", &b);
	S[j] -= b;
	if (S[j] < 0) {
	  flag = false;
	}
      }      
    }
    if (flag) {
      printf("Yes\n");
    } else {
      printf("No\n");
    }
  }
}

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

using namespace std;

void solve()
{
	string str;
	while(cin >> str)
	{
		int data[10][10];
		for(int i = 0; i < 10; ++i)
		{
			data[0][i] = str[i] - '0';
		}
		for(int i = 1; i < 10; ++i)
		{
			for(int j = i; j < 10; ++j)
			{
				data[i][j] = (data[i - 1][j - 1] + data[i - 1][j]) % 10;
			}
		}
		cout << data[9][9] << endl;
	}
}

int main()
{
	solve();
	return(0);
}

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

using namespace std;

int main() {
	string str;
	cin >> str;
	for (int i = 0; i < str.length(); ++i) {
		if (i + 1 < str.length() && str[i] == str[i + 1]) {
			cout << i + 1 << " " << i + 2;

			return 0;
		}
		if (i + 2 < str.length() && str[i] == str[i + 2]) {
			cout << i + 1 << " " << i + 3;

			return 0;
		}
	}
	cout << "-1 -1";

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <complex>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>
#include <iterator>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;

const i64 mod = 1e9 + 7;
i64 ipow(i64 a, i64 b) {
    i64 x = a, y = 1;
    for (; b > 0; b >>= 1) {
        if (b & 1) (y *= x) %= mod;
        (x *= x) %= mod;
    }
    return y;
}
i64 inv(i64 x) {
    return ipow(x, mod - 2);
}
i64 fact(i64 x) {
    static vector<i64> f;
    i64 i = f.size();
    if (x >= i) {
        f.resize(x + 1);
        for (; i <= x; ++i) {
            f[i] = i == 0 ? 1 : i * f[i - 1] % mod;
        }
    }
    return f[x];
}
i64 perm(i64 n, i64 k) {
    return k <= n ? fact(n) * inv(fact(n - k)) % mod : 0;
}
i64 comb(i64 n, i64 k) {
    return k <= n ? fact(n) * inv(fact(k) * fact(n - k) % mod) % mod : 0;
}
int main() {
    i64 n, k;
    cin >> n >> k;
    cout << ipow(k, n) << endl;
    return 0;
}


Measured memory_bytes: 3092
using System;
using System.Linq;

class B3
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var query = Enumerable.Range(0, n)
			.Select(i => Console.ReadLine().Split())
			.Select((x, i) => new { Id = i + 1, City = x[0], Point = int.Parse(x[1]) })
			.OrderBy(r => r.City)
			.ThenByDescending(r => r.Point)
			.Select(r => r.Id);
		Console.WriteLine(string.Join("\n", query));
	}
}


Measured memory_bytes: 13788
#include <iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n;i++)
int main(void) {
    int a, b;cin >> a >> b;
    if (a < 0) {
        if (b >= 0)
            cout << "Zero" << endl;
        else if (abs(b - a) % 2 == 0) {
            cout << "Negative" << endl;
        }
        else
            cout << "Positive" << endl;
    }
    else {
        cout << "Positive" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define vc vector<int>
#define um unordered_map<int,int>
#define ll long long 
#define rep(i,a,b) for(__typeof(a) i=a; i<b; i++)
#define si(a) a.size()
#define all(a) a.begin(),a.end()
#define ss(a) a.second
#define ff(a) a.first
#define M 1000000
#define pb push_back
#define repit(i,a) for(auto i=a.begin(); i!=a.end(); i++)
#define take(arr,n) for(int i=0;i<n;i++)cin>>arr[i]
#define out(arr,n) for(int i=0;i<n;i++)cout<<arr[i]<<' '
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define reprev(i,b,a) for(__typeof(b) i=b; i>=a; i--)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define doublearray vector<vector<int>>
#define mod 998244353 
using namespace std;
ll max(ll a, ll b){ return a>b?a:b; }
ll min(ll a, ll b){ return a<b?a:b; }
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a, ll b){
    return (a*b)/gcd(a,b);
}
int binaryS(ll x, ll sb[], int m){
    int l = 0, r=m;
    int mid = (l+r)/2;
    while(l<r){
        mid = (l+r)/2;
        if(sb[mid]<x) l= mid+1;
        else if(sb[mid]>x) r = mid-1;
        else return mid;
    }
    return l;
}
int main(){
    fastio;
    int n; cin>>n; int arr[n]; take(arr,n);
    int fin = 0;
    rep(i,0,n){
        fin^=arr[i];
    }
    rep(i,0,n){
        cout<<(fin^arr[i])<<' ';
    }
    return 0;
}





Measured memory_bytes: 4328
#include<iostream>
#include<algorithm>
#include<math.h>
#include<cstdio>
#include<ctype.h>
#include<stdio.h>
#include<set>
#include<vector>
#include<map>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<numeric>
#include<string>
using namespace std;
typedef long long ll;
ll MOD = 1000000007;
int main() {
	ll N, A, B, C, D;
  	cin>>N>>A>>B>>C>>D;
	cin >> N >> A >> B >> C >> D;
       ll x = N/A;
       if(N%A!=0)x++;
       ll y =N/C;
       if(N%C!=0)y++;
       cout<<min(x*B,y*D)<<endl;
}





Measured memory_bytes: 3136
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
ll N;
  ll Y;
  cin >>N>>Y;
  
  ll count=0;
  ll x=0;
  ll y=0;
  ll z=0;
  rep(i,N+1) {
    repl(j,0,N-i+1) {
     ll b=N-x-y;
       if(b>=0) {
        if(i*10000+j*5000+(N-i-j)*1000==Y) {
          x=i;
          y=j;
          z=N-i-j;
          count=1;
          break;
       	 }
     	 }
      
   		 }
    
  }
  
  if(count==1) {
    cout<<x<<" "<<y<<" "<<z<<endl;
  }
  
  else {
    cout<<-1<<" "<<-1<<" "<<-1<<endl;
  }
}
  
 


Measured memory_bytes: 256
N, K = [int(n) for n in input().split()]
#dice = [int(n) for n in input().split()]
evs = [(1 + int(n))/2 for n in input().split()]
cumsum = [0]

for i in range(1,N+1):
    cumsum.append(cumsum[i-1] + evs[i-1])

k_cum = [cumsum[i+K] - cumsum[i] for i in range(N-K+1)]

print(max(k_cum))

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

#define PB          push_back
#define PF          push_front
#define MP          make_pair
#define FI          first
#define SE          second
#define SIZE( A )   int( ( A ).size( ) )
#define ALL( A )    ( A ).begin( ), ( A ).end( )
#define ALLR( A )   ( A ).rbegin( ), ( A ).rend( )

using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef double              lf;
typedef pair< int, int >    pii;
typedef pair< ll, ll >      pll;
typedef vector< bool >      vb;
typedef vector< lf >        vd;
typedef vector< ll >        vll;
typedef vector< int >       vi;
typedef vector< pii >       vpii;

const int MAXH = int( 1e2 )+10;
const int MAXN = int( 1e5 )+10;
const int MOD  = int( 360 );
const int oo   = INT_MAX;

int h,w,n;
int matrix[ MAXH ][ MAXH ], arr[ MAXN ];

int main( ) {

  #ifdef LOCAL
    freopen( "input", "r", stdin );
    //freopen( "output", "w", stdout );
  #else
    //freopen( "input", "r", stdin );
    //freopen( "output", "w", stdout );
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );
  #endif
  while( cin >> h >> w >> n ) {
    for( int i = 0; i < n; ++i ) {
      cin >> arr[ i ];
    }
    for( int i = 0, s = 1, j = 0, k = 0; i < h; ++i, s *= -1 ) {
      for( ; 0 <= j && j < w; j += s ) {
        if( arr[k] > 0 ) {
          matrix[ i ][ j ] = k+1;
          --arr[k];
        }
        else {
          k++;
          j -= s;
        }
      }
      j -= s;
    }
    for( int i = 0; i < h; ++i ) {
      for( int j = 0; j < w; ++j ) {
        cout << matrix[ i ][ j ] << " \n"[j+1 == w];
      }
    }
  }

  return 0;
}


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


using namespace std;

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

    vector<int> A(N);
    for (int i=0; i<N; i++) {
        cin >> A.at(i);
    }

     vector<int> B(N);
    for (int i=0; i<N; i++) {
        B.at(i) = K - A.at(i);
    }

    vector<int> C(N);
    for (int i=0; i<N; i++) {
        if (A.at(i) < B.at(i)) {
            C.at(i) = A.at(i);
        } else {
            C.at(i) = B.at(i);
        } 
    }

    vector<int> D(N); // i ~ i+1 
    for (int i=0; i<N-1; i++) {
            D.at(i) = A.at(i+1) - A.at(i);// A.at(i) ~ A.at(i+1)
    }
    D.at(N-1) = A.at(0) + B.at(N-1);

    int max = 0;
    int sum = 0;
    for (int x : D) {
        sum += x;
        if (x > max) {
            max = x;
        }
    }
   
   cout << sum - max << endl;

}

Measured memory_bytes: 3328
a=input()
if a=="MON":
  print("6")
elif a=="SUN":
  print("7")
elif a=="TUE":
  print("5")
elif a=="WED":
  print("4")
elif a=="THU":
  print("3")
elif a=="FRI":
  print("2")
elif a=="SAT":
  print("1")


Measured memory_bytes: 2940
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <string>
#include <string.h>
#include <sstream>
#include <ctime>

using namespace std;

#define eps 1e-12
#define pi 3.14159265358979323846
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define bgn begin
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair<ll,ll>






const int N=1010,N2=5010;
int n,u,x[N],s[N],s2[N];
bool dp[N2][N],y;

vector<int>adj[N];


string p,p2;






void dfs(int u)
{
	if(adj[u].empty())
	{
		s[u]=x[u];
		s2[u]=0;
		return;
	}
	int sum=0,v,k,t;
	for(int i=0;i<adj[u].size();i++)
	{
		v=adj[u][i];
		dfs(v);
		if(!y)return;
		if(i==0)
		{
			for(int j=0;j<=x[u];j++)
			{
				if(j==s[v]||j==s2[v])dp[j][v]=1;
				else dp[j][v]=0;
			}
		}
		else
		{
			k=adj[u][i-1];
			for(int j=0;j<=x[u];j++)
			{
				dp[j][v]=0;
				if(j>=s[v])dp[j][v]|=dp[j-s[v]][k];
				if(j>=s2[v])dp[j][v]|=dp[j-s2[v]][k];
			}
		}
		sum+=s[v]+s2[v];
	}
	for(int i=0;i<=x[u];i++)
	{
		if(dp[i][v])
		{
			dp[x[u]][u]=1;
			t=x[u]-i;
		}
	}
	if(!dp[x[u]][u])
	{
		y=0;
		return;
	}
	s[u]=x[u];
	sum+=t;
	s2[u]=sum-s[u];
}








void solve()
{
	p="POSSIBLE";
	p2="IMPOSSIBLE";
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		cin>>u;
		adj[u].pb(i);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	y=1;
	dfs(1);
	if(y)cout<<p<<"\n";
	else cout<<p2<<"\n";
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef localProject
	freopen("in.txt","r",stdin);
#endif
	solve();
	return 0;
}

Measured memory_bytes: 5248
#include <bits/stdc++.h>     
using namespace std;
typedef long long int ll;
typedef long long int lli;
typedef vector < ll > vi;
typedef vector<vi> vvi;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(c) cout << #c << " = " << c << endl;
#define Mod 1000000007
#define INF 1e9L
lli find_min(lli a,lli b){if(a>b) return b; return a;}
lli find_max(lli a,lli b){if(a<b) return b; return a;}

int main()
{
    fastio
    lli n,w;
    cin>>n>>w;
    lli val[n],wt[n];
    lli sum = 0;
    for(lli i = 0; i < n; i++)
    {
        cin>>wt[i]>>val[i];
        sum += val[i];
    }
    vi dp(sum+1 ,INF);
    dp[0] = 0;
    //dp[i] = the minimum total weight of items with total value exactly i
    for(lli i = 0 ; i < n ; i++)
    {
      for(lli j = sum - val[i];j>=0;j--)
     // for(lli j = 0; j < sum - val[i]; j++)
        dp[j + val[i]] = find_min(dp[j + val[i]] , dp[j] + wt[i]); 
    }
    lli ans = 0;
    for(lli i = 0;i <= sum;i++){
        if(dp[i] <= w)
        ans = find_max(ans,i);
    }
    cout<<ans<<'\n';
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {
    static final long MOD = 1000000007L;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] ar = new long[n];
        long arMax = 0;
        for(int i = 0; i < n; ++i) {
            ar[i] = sc.nextLong();
            arMax = Math.max(arMax, ar[i]);
        }
        
        Map<Long, Long> lcmPrimes = new HashMap<>();
        for(long i = 2; i <= arMax; ++i) lcmPrimes.put(i, 0L);
        for(int i = 0; i < n; ++i) {
            Map<Long, Long> p = primeFactorize(ar[i]);
            for(Map.Entry<Long, Long> e : p.entrySet()) {
                long key = e.getKey();
                long ev = e.getValue();
                long lv = lcmPrimes.get(key);
                lcmPrimes.put(key, Math.max(ev, lv));
            }
        }
        
        long lcm = 1L;
        for(Map.Entry<Long, Long> e : lcmPrimes.entrySet()) {
            long x = e.getKey();
            long y = e.getValue();
            lcm = lcm * pow(x, y) % MOD;
        }
        
        long ans = 0L;
        for(long v : ar) {
            long tmp = lcm * inv(v) % MOD;
            ans = (ans + tmp) % MOD;
        }
        System.out.println(ans);
    }
    
    static Map<Long, Long> primeFactorize(long n) {
        Map<Long, Long> primes = new HashMap<>();
        for(long d = 2L, ub = n; d * d <= ub; ++d) {
            long cnt = 0L;
            while(n % d == 0L) {
                ++cnt;
                n /= d;
            }
            primes.put(d, cnt);
        }
        
        if(n > 1L) primes.put(n, 1L);
        return primes;
    }
    
    static long pow(long x, long y) {
        if(y == 0L) return 1L;
        if(y == 1L) return x;
        
        long tmp = pow(x, y / 2);
        if(y % 2L == 0L) return tmp * tmp % MOD;
        else return x * tmp % MOD * tmp % MOD;
    }
    
    static long inv(long x) {
        return pow(x, MOD - 2);
    }
}


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

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

  vector<int> H(N);
  rep(i, N) cin >> H[i];

  int ans = 0;
  rep(i, N) {
    int cnt = 0;
    rep(j, i) {
      if (H[i] >= H[j])
        cnt++;
    }
    if (cnt == i)
      ans++;
  }

  cout << ans << endl;
}

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

int main(){
	int K,S;
  cin>>K>>S;
  int X,Y,Z;
  int count=0;
  for(int i=0;i<=K;i++){
  	X=i;
    for(int j=0;j<=K;j++){
    	Y=j;
      if(X+Y<=S&&X+Y>=S-K)
        count++;
    }
  }
  cout<<count<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cout << #x " => " << (x) << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 28;
constexpr lint   INFL = 1LL << 60;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  int n, t;
  cin >> n >> t;
  vector<pair<int, int>> ab(n);
  rep (i, n) cin >> ab[i].first >> ab[i].second;
  vector<vector<int>> dpl(n + 1, vector<int>(t)), dpr(n + 1, vector<int>(t));
  rep1 (i, n) {
    int li = i - 1, ri = n - i;
    rep (j, t) dpl[i][j] = dpl[i - 1][j];
    rep (j, t) dpr[n - i][j] = dpr[n - i + 1][j];
    rep (j, t) {
      int lnext = j + ab[li].first, rnext = j + ab[ri].first;
      // dpl[i][j] = max(dpl[i][j], dpl[i - 1][j]);
      if (lnext < t) dpl[i][lnext] = max(dpl[i][lnext], dpl[i - 1][j] + ab[li].second);
      // dpr[n - i][j] = max(dpr[n - i][j], dpr[n - i + 1][j]);
      if (rnext < t) dpr[n - i][rnext] = max(dpr[n - i + 1][rnext], dpr[n - i + 1][j] + ab[ri].second);
    }
  }
  int maxi = 0;
  rep (i, n) {
    rep (j, t) {
      int sum = dpl[i][j] + dpr[i + 1][t - 1 - j];
      maxi = max(maxi, sum + ab[i].second);
    }
  }
  cout << maxi << endl;
  return 0;
}

Measured memory_bytes: 70912
// 2014/09/11 Tazoe

#include <iostream>
#include <queue>
#include <string>
#include <map>
using namespace std;

struct State{
	string G;
	int n;
};

bool is_over(string G)
{
	bool flg = true;

	for(int i=1; i<G.size(); i++){
		if(G[i]!=G[0]){
			flg = false;
			break;
		}
	}

	return flg;
}

void DFS(char g[12][12], char F, char T, int x, int y)
{
	if(g[y][x]!=F)
		return;

	g[y][x] = T;

	DFS(g, F, T, x+1, y);
	DFS(g, F, T, x-1, y);
	DFS(g, F, T, x, y+1);
	DFS(g, F, T, x, y-1);
}

string fill(string G, char C, int X, int Y)
{
	char g[12][12];
	for(int y=0; y<Y+2; y++){
		for(int x=0; x<X+2; x++){
			g[y][x] = 'N';
		}
	}

	for(int y=0; y<Y; y++){
		for(int x=0; x<X; x++){
			g[y+1][x+1] = G[y*X+x];
		}
	}

//	for(int y=0; y<Y+2; y++){
//		for(int x=0; x<X+2; x++){
//			cout << g[y][x];
//		}
//		cout << endl;
//	}

	DFS(g, G[0], C, 1, 1);

	for(int y=0; y<Y; y++){
		for(int x=0; x<X; x++){
			G[y*X+x] = g[y+1][x+1];
		}
	}

	return G;
}

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

		if(X==0 && Y==0)
			break;

		string G = "";
		for(int y=0; y<Y; y++){
			for(int x=0; x<X; x++){
				string C;
				cin >> C;

				G += C;
			}
		}

//		cout << G << endl;

		queue<struct State> que;

		struct State tmp;
		tmp.G = G;
		tmp.n = 0;
		que.push(tmp);

		map<string, bool> memo;

		while(!que.empty()){
			tmp = que.front();
			que.pop();

//			cout << tmp.G << ' ' << tmp.n << endl;

			if(memo.find(tmp.G)!=memo.end()){
				continue;
			}
			else{
				memo[tmp.G] = true;
			}

			if(is_over(tmp.G) || tmp.n>100){
				cout << tmp.n << endl;
				break;
			}

			if(tmp.G[0]=='R'){
				struct State tmp2;
				tmp2.G = fill(tmp.G, 'G', X, Y);
				tmp2.n = tmp.n+1;
				que.push(tmp2);
				tmp2.G = fill(tmp.G, 'B', X, Y);
				que.push(tmp2);
			}
			else if(tmp.G[0]=='G'){
				struct State tmp2;
				tmp2.G = fill(tmp.G, 'R', X, Y);
				tmp2.n = tmp.n+1;
				que.push(tmp2);
				tmp2.G = fill(tmp.G, 'B', X, Y);
				que.push(tmp2);
			}
			else if(tmp.G[0]=='B'){
				struct State tmp2;
				tmp2.G = fill(tmp.G, 'R', X, Y);
				tmp2.n = tmp.n+1;
				que.push(tmp2);
				tmp2.G = fill(tmp.G, 'G', X, Y);
				que.push(tmp2);
			}
		}
	}

	return 0;
}

Measured memory_bytes: 2692
#include <bits/stdc++.h>
using namespace std;
int main(){
  while(1){
  long long n,m;
    cin >> n >> m;
    if(n==0ll and m==0ll) break;
    char c[n][m];
    string s;
    map<char, pair<int, int> > mp;
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++){
        cin >> c[i][j];
        mp[c[i][j]]=make_pair(i,j);
      }
    }
    cin >> s;
    long long x=0,y=0,ans=0;
    for(size_t i=0;i<s.size();i++){
      ans+=abs(mp[s[i]].first-x)+abs(mp[s[i]].second-y)+1;
      x=mp[s[i]].first;
      y=mp[s[i]].second;
    }
    cout << ans << endl;
  }
  return 0;
}



Measured memory_bytes: 3216
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main(){
	int N; 
	cin >> N; 
	int B[110] = {};
	for(int i = 1; i <= N; i++){
		cin >> B[i]; 
	}
	int A[110] = {}; 
	for(int i = 1; i <= N; i++){
		A[i] = i; 
	}
	int ans[110] = {}; 
	bool possible = true; 
	for(int i = 1; i <= N; i++){
		for(int j = N; j >= 1; j--){
			if(A[j] == B[j]){
				ans[i] = B[j]; A[j] = -114514; 
				for(int k = j+1; k <= N; k++){
					A[k] --; 
				}
              break;
			}
		}
	}
	for(int i = 1; i <= N; i++){
		if(ans[i] == 0) {possible = false; break;}
	}
	if(!possible){cout << -1 << endl;}
	else{
		for(int i = N; i >= 1; i--){
			cout << ans[i] << endl;  
		}
	}
}

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

using namespace std;

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

  sort(w.begin(), w.end());
  for (int i = 0, len = w.size(); i < len; i+=2) {
    if (w[i] != w[i+1]) {
      cout << "No";
      return 0;
    }
  }

  cout << "Yes";
}

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

int main() {
 string str1,str2;
 cin>>str1>>str2;
 int i;
 
    if(str1.size()!=(str2.size())-1){
		 cout<<"No"<<endl;	
      return 0;
    }
 for(i=0;i<str1.size();i++){
	 if(str1.at(i)!=str2.at(i)){
		 cout<<"No"<<endl;
       return 0;
	 }
 }
		 cout<<"Yes"<<endl;	
	
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n;
struct node {
    int x,y;
    int id;
}town[maxn];
struct edge {
    int st,ed;
    int cost;
}e[maxn*4];
int fa[maxn];
bool cmp1(const node &a,const node &b) {
    return a.x<b.x;
}
bool cmp2(const node &a,const node &b) {
    return a.y<b.y;
}
bool cmp3(const edge &a,const edge &b) {
    return a.cost<b.cost;
}
int Find(int x)
{
    if(fa[x]!=x)
        fa[x]=Find(fa[x]);
    return fa[x];
}
int main() {
	cin >> n;
    for(int i=1;i<=n;i++) {
        cin >> town[i].x >> town[i].y;
        town[i].id=i;
    }
    int k=0;
    sort(town+1,town+1+n,cmp1);
    for(int i=1;i<=n-1;i++) {
        e[k].st=town[i].id;
        e[k].ed=town[i+1].id;
        e[k++].cost=abs(town[i].x-town[i+1].x);
    }
    sort(town+1,town+1+n,cmp2);
    for(int i=1;i<=n-1;i++) {
        e[k].st=town[i].id;
        e[k].ed=town[i+1].id;
        e[k++].cost=abs(town[i].y-town[i+1].y);
	}
    sort(e,e+k,cmp3);
    for(int i=1;i<=n;i++)
        fa[i]=i;
	int ans=0;
	for(int i=0;i<k;i++) {
            int a=Find(e[i].st),b=Find(e[i].ed);
            if(a!=b) {
                ans+=e[i].cost;
                fa[b]=a;
            }
        }
    cout << ans;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
#define ll long long
//#define int long long
int n,m,ans=0,rec[200050],cnt=0;
vector<int> p[200050];
void dfs(int cur){
	rec[cur]=1;cnt++;
	for(int i=0;i<p[cur].size();i++){
		if(rec[p[cur][i]]==1)continue;
		dfs(p[cur][i]);
	}	
}
signed main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int a,b;cin>>a>>b;
		p[a].push_back(b);p[b].push_back(a);
	}
	for(int i=0;i<n;i++){
		if(rec[i]==1)continue;
		cnt=0;
		dfs(i);
		ans=max(ans,cnt);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 21404
#include<algorithm>
#include<cmath>
#include<climits>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<string>> vvs;
typedef vector<vector<bool>> vvb;
const ll MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
#define repl(i,s,e) for(int i=s;i<e;i++)
#define reple(i,s,e) for(int i=s;i<=e;i++)
#define revrep(i,n) for(int i=n-1;i>=0;i--)
#define all(x) (x).begin(),(x).end()

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

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

	ll p = (ll)ceil(sqrtl((ld)S));
	ll q = S / p;
	ll r = S % p;

	if (r > 0)
	{
		r -= p;
		q++;
	}

	//x[0], y[0]を原点に固定して、
	//S = x[1] * y[2] - y[1] * x[2]
	//S = p * q + rと比較する。
	//ただし、rを0以下にする必要がある。

	vll x(3), y(3);

	x[0] = y[0] = 0;
	x[1] = p;
	y[2] = q;
	y[1] = - r;
	x[2] = 1;

	cout << x[0] << " ";
	cout << y[0] << " ";
	cout << x[1] << " ";
	cout << y[1] << " ";
	cout << x[2] << " ";
	cout << y[2] << endl;

	return 0;
}

Measured memory_bytes: 512
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

// End of template.


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

    int n;
    int l[2020];
    cin >> n;
    rep(i, n) cin >> l[i];
    sort(begin(l), begin(l) + n);

    int ans = 0;
    for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
        ans += lower_bound(begin(l), begin(l) + n, l[i] + l[j]) - begin(l) - j - 1;
    }

    cout << ans << '\n';

    return 0;
}



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

namespace ClosestPair{
	// DIM=3????£????????¬????????????????????????´?????????getNearPoints()makeBucket()?????´
	const double EPS = 1e-9;
	const int DIM = 3;
	typedef array<double,DIM> P;

	double dist(const P &p1,const P &p2){
		double ans = 0;
		for(int i = 0 ; i < DIM ; i++)
			ans += (p1[i]-p2[i])*(p1[i]-p2[i]);
		return sqrt(ans);
	}
	typedef array<int,DIM> Block;
	typedef map<Block,vector<int>> Bucket;
	Block getBlock(const P &p,double w){
		Block res;
		for(int i = 0 ; i < DIM ; i++) res[i] = p[i] / w;
		return res;
	}
	vector<int> getNearPoints(const Bucket &b,double w,const P &p){
		vector<int> res;
		auto key = getBlock(p,w);
		for(int x0 = -1 ; x0 <= 1 ; x0++)
			for(int x1 = -1 ; x1 <= 1 ; x1++)
				for(int x2 = -1 ; x2 <= 1 ; x2++){
					auto it = b.find(Block{key[0]+x0,key[1]+x1,key[2]+x2});
					if( it != b.end() ){
						for( int id : it->second ) res.push_back(id);
					}
				}
		return res;
	}
	//???w???n?¬?????????±????????????????????????????????¨????????°??¨??????????????????????±????????????¨?????§?????????
	Bucket makeBucket(const vector<P> &ps,double w){
		Bucket b;
		for(int i = 0 ; i < ps.size() ; i++)
			b[getBlock(ps[i],w)].push_back(i);
		return b;
	}
	// ????????????????????¢????????????????????±???????¬??§??????? map????????¨?????????????????§???????¨???????O(n log n)
	// ?????±??????????????????????§???????????????????????¢????????£?????????????????????????????????§??????????????§???????????????2w??????????????????????????????w???????????????????\??????????
	double closetPairDistance(vector<P> ps){
		assert(ps.size()>=2);
		random_shuffle(ps.begin(),ps.end());
		double w = dist(ps[0],ps[1]);
		vector<P> build = {ps[0],ps[1]};
		auto b = makeBucket(build,w);
		for(int i = 2 ; i < ps.size() ; i++){
			double next_w = w;
			for( int j : getNearPoints(b,2*w,ps[i]) )
				next_w = min(next_w,dist(ps[i],ps[j]));
			build.push_back(ps[i]);
			if( w - EPS > next_w ){
				w = next_w;
				b = makeBucket(build,2*w);
			}else{
				b[getBlock(ps[i],2*w)].push_back(i);
			}
		}
		return w;
	}
};

using namespace ClosestPair;

int main(){
	int n;
	vector<P> ps;
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		double x,y;
		cin >> x >> y;
		ps.push_back(P{x,y,0});
	}
	printf("%.10lf\n",closetPairDistance(ps));
}

Measured memory_bytes: 29592
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = [[] for _ in range(N)]
cou = 0

for _ in range(M):
    a, b = map(int, input().split())
    nums[a-1].append(b-1)
    nums[b-1].append(a-1)

def search(path):
    global cou
    n = path[len(path) - 1]
    if len(path) == N:
        cou += 1
    else:
        for x in nums[n]:
            if x not in path:
                path.append(x)
                search(path)
                path.pop()

search([0])
print(cou)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath> 
#include <queue>
#include <functional>

using namespace std;
//typedef long long ll;
typedef pair<int, int> P;
//static const int dx[4] = {1, -1, 0, 0};
//static const int dy[4] = {0, 0, 1, -1};

static const int MAX = 401;
static const int INF = 1000000;

//const ll MOD = 1e+9 + 7;

int main() {

    int N, M_a, M_b; cin >> N >> M_a >> M_b;

    vector<P> Point(MAX);
    vector<int> Cost(MAX);
    for (int i = 0; i < N; i++) 
        cin >> Point[i].first >> Point[i].second >> Cost[i];

    int a_cnt, b_cnt, cost_cnt;
    vector< vector<int> > dp(MAX, vector<int>(MAX, INF));

    dp[0][0] = 0;

    for (int num = 0; num < N; num++) {

        a_cnt = Point[num].first;
        b_cnt = Point[num].second;
        cost_cnt = Cost[num];

        for (int i = MAX; i >= 1; i--) {

            if (a_cnt > i) continue;

            for (int j = MAX; j >= 1; j--) {

                if (b_cnt > j) continue;
                if (dp[i - a_cnt][j - b_cnt] != INF) {
                    dp[i][j] = min(dp[i - a_cnt][j - b_cnt] + cost_cnt, 
                                        dp[i][j]);
                }
            }
        }
    }
/*
    cout << '\n';
    for (int i = 1; i <= 10 * N; i++) {
        for (int j = 1; j <= 10 * N; j++) {
            cout << dp[i][j] << ' ';
        }
        cout << '\n';
    }
*/
    int max_m = max(M_a, M_b);
    int ans = INF;
    for (int i = 1; max_m * i < MAX; i++) {
        ans = min(ans, dp[M_a * i][M_b * i]);
        //cout << dp[M_a * i][M_b * i] << '\n';
    }
    if (ans == INF) 
        cout << -1 << '\n';
    else 
        cout << ans << '\n';

}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<60;
const int INF = 1<<28;
const long long MOD =1000000000+7;

int main(){
    int n,wlim;
    cin >>n>>wlim;
    vector<pair<long long,int>>data(n+1);//wegit,value
   
    //n,value->wight
    int ans=0;
    int vmax=0;
    
    for(int i=0;i<n;i++){
        cin >>data[i].first>>data[i].second;
        vmax+=data[i].second;
    }
    vector<vector<long long>> dp(n + 1, vector<long long>(vmax+5, INFLL));
    dp[0][0] = 0LL;
    for(int N=1;N<=n;N++){
        for(int v=vmax+3;v >=0;v--){
            chmin(dp[N][v],dp[N-1][v]);
            
            chmin(dp[N][v],dp[N][v+1]);
            
            if(v >=data[N-1].second){
                chmin(dp[N][v], dp[N - 1][v - data[N - 1].second] + data[N - 1].first);
            }
           // cout<<dp[N][v]<<" ";
            if(N==n){
                if(dp[N][v] <=wlim){
                    chmax(ans,v);
                }
            }
        }
     //   cout<<endl;
    }
    cout<<ans;
    
}


Measured memory_bytes: 80256
f = lambda: map(int, input().split())
n = int(input())
p = list(f())
m = 3*10**4
k = 10**9
a = [i*m for i in range(1, n+1)]
b = [k-a[i] for i in range(n)]
for i in range(n):
    b[p[i]-1] += i
print(*a)
print(*b)


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

int main() {
  int A, B;
  cin >> A >> B;
  if (A % 2 == 1 && B % 2 == 1) {
    cout << "Odd" << endl;
  }
  else {
    cout << "Even" << endl;
  }
}

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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = array[0];
            var K = array[1];

            var pArray = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var expectedArray = new double[N];

            for (int i = 0; i < N; i++)
            {
                var p = pArray[i];
                double s = 0;
                for (int j = 1; j <= p; j++)
                {
                    s += j;
                }

                expectedArray[i] = s / p;
            }

            double answer = 0;
            double before = 0;
            for (int i = 0; i < K-1; i++)
            {
                before += expectedArray[i];
            }

            for (int i = 0; i <= N - K; i++)
            {
                var a = before;
                if (i > 0)
                {
                    a -= expectedArray[i - 1];
                }

                a += expectedArray[i + K - 1];

                if (a > answer)
                {
                    answer = a;
                }

                before = a;
            }

            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 34652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  long long a,b,c;
  cin >> a >> b >> c;
  long long d=c-a-b;
  if(d>0 and d*d>4*a*b){
    cout << "Yes\n";
  }else{
    cout << "No\n";
  }
  return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define pb push_back
#define F first
#define S second
#define ins insert
#define mp make_pair
#define fo(i, n1, n, x) for(int i = n1; i <= n; i += x)
#define foo(i, n, n1, x) for(int i = n; i >= n1; i -= x)
#define bit __builtin_popcount
#define md (l + ((r - l) / 2))
#define all(x) x.begin(),x.end()
#define eb emplace_back
#define ub upper_bound
#define lb lower_bound
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;


using ll = long long;

//#define int ll


const int N = 3e5 + 11, mod = 1e9 + 7, mod2 = 998244353;
const int MAX = 1e5 + 11;
const int INF1 = 2e9 + 11;
const ll INF2 = 2e18 + 11;
const double INF3 = 1e8 + 11;
const int base = 500;
const int P = 31;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double EPS = 1e-4;
const double PI = acos(-1.0);


template<typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }


typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
bool prime(int n) {
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){return 0;}
    }return 1;}

ll a[N] , cnt[N];

int main() {
    ios;
    ll n;
    cin >> n;
    set<int> st;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
        cnt[a[i]] ++;
        st.insert(a[i]);
    }
    ll ans = 0;
    for(auto to: st) {
        ans += cnt[to] * (cnt[to] - 1) / 2;
    }
    for(int i = 1; i <= n; i ++) {
        cout << ans - cnt[a[i]] + 1 << endl;
    }
    return 0;
}


Measured memory_bytes: 11136
#include <stdio.h>
#include <string.h>

int main(void)
{
    int i;
    double n, count = 0;
    scanf("%lf", &n);

    for (i = 1; i <= n; i++)
    {
        if (i % 2 == 1) count++;
    }

    printf ("%lf", count / n);

    return 0;
}

Measured memory_bytes: 1740
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;


void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int).array;
    auto C = new int[](101010);

    foreach (i; 0..N)
        C[A[i]] += 1;

    int ans = 0;
    foreach (i; 0..100100) {
        if (i == 0)
            ans = max(ans, C[0] + C[1]);
        else
            ans = max(ans, C[i-1] + C[i] + C[i+1]);
    }

    ans.writeln;
}


Measured memory_bytes: 3760