akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
#include<numeric>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;


//最大公約数
template<class T> T gcd(T a, T b)
{
	while (true)
	{
		T r;
		if (a%b == 0) return b;
		else
		{
			r = a % b;
			a = b;
			b = r;
		}
	}
}
//最小公倍数
template<class T> T lcm(T a, T b)
{
	return a / gcd(a, b)*b;
}
//文字0~9をint型0~9に変換
int char_to_int(char c)
{
	if (c == '0') return 0;
	if (c == '1') return 1;
	if (c == '2') return 2;
	if (c == '3') return 3;
	if (c == '4') return 4;
	if (c == '5') return 5;
	if (c == '6') return 6;
	if (c == '7') return 7;
	if (c == '8') return 8;
	if (c == '9') return 9;
	else return -1;
}
//int型0~9を文字0~9に変換
char int_to_char(int c) {
	if (c == 0) return '0';
	if (c == 1) return '1';
	if (c == 2) return '2';
	if (c == 3) return '3';
	if (c == 4) return '4';
	if (c == 5) return '5';
	if (c == 6) return '6';
	if (c == 7) return '7';
	if (c == 8) return '8';
	if (c == 9) return '9';
	else return'x';
}
//a^b mod MODを計算
long long int ModPower(long long int a, long long int b, long long int MOD)
{
	if (b == 0) return 1;
	else if (b % 2 == 0)
	{
		long long int d = ModPower(a, b / 2, MOD);
		return (d*d) % MOD;
	}
	else
	{
		return (a*ModPower(a, b - 1, MOD)) % MOD;
	}
}
//nCr mod MODを計算
long long int ModCombi(long long int n, long long int r, long long int MOD)
{
	if (n == 0 || r == 0) return 1;

	long long int Kn = 1, Kr = 1, Knr = 1;

	long long int temp = 1;
	for (long long int i = 1; i <= n; i++)
	{
		temp *= i;
		temp %= MOD;
		if (i == n) Kn = temp;
		if (i == r) Kr = temp;
		if (i == n - r) Knr = temp;
	}

	long long int x = ModPower(Kr, MOD - 2, MOD);
	long long int y = ModPower(Knr, MOD - 2, MOD);

	long long int ans;
	ans = Kn * x;
	ans %= MOD;
	ans *= y;
	ans %= MOD;

	return ans;
}
//int型10進数をord桁のstring型2進数に変換する
string binary(int x, int ord)
{
	int y;
	string ans = "";
	for (int i = 0; i < ord; i++)
	{
		y = x / (int)pow(2, ord - 1 - i);
		y %= 2;
		if (y == 0) ans += "0";
		else ans += "1";
	}

	return ans;
}
//ord桁のstring型2進数をint型10進数に変換する
int rep_binary(string x, int ord)
{
	int res = 0;
	for (int i = 0; i < ord; i++)
	{
		if (x[i] == '1') res += (int)pow(2, ord - 1 - i);
	}
	return res;
}


/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/


int main()
{
	const long long int mod = 1000000007;

	long long int N;
	char S[200005];
	cin >> N >> S;


	if (N == 1 && S[0] == 'B'&&S[1] == 'B')
	{
		cout << 1 << endl;
	}
	else if (S[0] == 'B'&&S[2 * N - 1] == 'B')
	{
		long long int lead = 1;
		long long int ans = 1;

		for (int i = 1; i < 2*N; i++)
		{
			if ((lead % 2 == 0 && S[i] == 'W') || (lead % 2 == 1 && S[i] == 'B'))
			{
				ans = (ans*lead) % mod;
				lead--;
			}
			else
			{
				lead++;
			}
		}

		if (lead != 0)
		{
			cout << 0 << endl;
		}
		else
		{
			for (int i = 0; i < N; i++)
			{
				ans = (ans*(i + 1)) % mod;
			}

			cout << ans << endl;
		}
	}
	else
	{
		cout << 0 << endl;
	}

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  bool isThree = true;	//3色か
  // ここにプログラムを追記
  for( int i = 0; i < N; ++i){
    string S;
    cin >> S;
    if( S == "Y" ){
      isThree = false;
      break;
    }
  }
  if( isThree ){
    cout << "Three" << endl;
  }else{
    cout << "Four" << endl;
  }
}

Measured memory_bytes: 3612
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    
    int N, M;
    cin >> N >> M;
    
    int ans[51] = {};
    for(int i=0; i < M; i++){
        int a, b;
        cin >> a >> b;
        ans[a]++;
        ans[b]++;
    }
    
    for(int i=1; i <= N; i++){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 3644
import itertools

N = int(input())
p_list = tuple(map(int, input().split()))
q_list = tuple(map(int, input().split()))

permu_list = list(itertools.permutations(range(1,N+1)))
p_index = permu_list.index(p_list)
q_index = permu_list.index(q_list)
ans = abs(p_index - q_index)
print(ans)

Measured memory_bytes: 8052
import java.util.*;

public class Main {
	static int ans = 0;
	static LinkedList list[];
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int a[] = new int[M];
		int b[] = new int[M];
		for(int i = 0; i < M; i++) {
			a[i] = sc.nextInt() - 1;
			b[i] = sc.nextInt() - 1;
		}
		
		list = new LinkedList[N];
		
		for(int i = 0; i < N; i++) {
			list[i] = new LinkedList();
		}
		for(int i = 0; i < M; i++) {
			list[a[i]].add(b[i]);
			list[b[i]].add(a[i]);
		}
		
		int n = N;
		int perm[] = new int[n];
		boolean flag[] = new boolean[n];
		makePerm(0, perm, flag);
		System.out.println(ans);
	}
	
	static void makePerm(int n, int perm[], boolean flag[]) {
		if(n == perm.length) {
			boolean ansflag = true;
			for(int i = 0; i < perm.length - 1; i++) {
				//System.out.print(perm[i]);
				if(perm[0] == 0) {
					if(!list[perm[i]].linked(perm[i + 1])) {
						ansflag = false;
					}
				} else {
					ansflag = false;
				}
			}
			//System.out.println();
			if(ansflag) {
				ans++;
			}
		} else {
			for(int i = 0; i < perm.length; i++) {
				if(flag[i]) {
					continue;
				} else {
					perm[n] = i;
					flag[i] = true;
					makePerm(n + 1, perm, flag);
					flag[i] = false;
				}
			}
		}
	}
}

class LinkedList {
	ArrayList<Integer> link = new ArrayList<Integer>();
	public void add(int vertex) {
		link.add(vertex);
	}
	
	public int get(int i){
		return link.get(i);
	}
	
	public void remove(int vertex) {
		link.remove(link.indexOf(vertex));
	}
	
	public void view() {
		for(int i = 0; i < link.size(); i++) {
			System.out.println(link.get(i));
		}
	}
	
	public boolean linked(int vertex) {
		if(link.contains(vertex)){
			return true;
		} else {
			return false;
		}
	}
	
	public int size() {
		return link.size();
	}
}

Measured memory_bytes: 23124
text = input()
odds= []
evens = []
flag1 = True
flag2 = True
for i in range(0,len(text),2):
    #print(text[i],end=" ")
    if text[i]=='L':
        flag1 = False
        break
    #print("\n")
for j in range(1,len(text),2):
    #print(text[j],end=" ")
    if text[j]=='R':
        flag2 = False
        break
#print(flag1,flag2)
if(not(flag1 and flag2)):
    print('No')
else:
    print('Yes')


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

const int MAX_N = 210;

void fail() {
	puts("-1");
	exit(0);
}

int n;
int a[MAX_N][MAX_N], dis[MAX_N], que[MAX_N];
bool vis[MAX_N], col[MAX_N];

void dfs(int x) {
	vis[x] = true;
	for (int i = 1; i <= n; ++i) {
		if (a[x][i]) {
			if (!vis[i]) {
				col[i] = col[x] ^ 1;
				dfs(i);
			} else if (col[x] == col[i]) fail();
		}
	}
}

void bfs(int s) {
	int ql = 1, qr = 1;
	memset(dis, 0, (n + 1) * sizeof(dis[0]));
	que[1] = s;
	dis[s] = 1;
	while (ql <= qr) {
		int x = que[ql++];
		for (int i = 1; i <= n; ++i) {
			if (a[x][i] && !dis[i]) {
				dis[i] = dis[x] + 1;
				que[++qr] = i;
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			char c = getchar();
			while (c != '0' && c != '1') c = getchar();
			a[i][j] = c == '1';
		}
	}

	dfs(1);
	
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		bfs(i);
		for (int j = 1; j <= n; ++j) {
			ans = std::max(ans, dis[j]);
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 3960
#define _USE_MATH_DEFINES
#include <cmath>
#include <iostream>
# include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

typedef vector<long long int> vi;
#define pb push_back
#define all(x) x.begin(),x.end()
#define sci(x)         int x;       scanf("%d", &x);
#define scii(x, y)     int x, y;    scanf("%d %d", &x, &y);
#define sciii(x, y, z) int x, y, z; scanf("%d %d %d", &x, &y, &z);
#define sciiii(x, y, z, w) int x, y, z, w; scanf("%d %d %d %d", &x, &y, &z, &w);
#define scl(x)         ll x;       scanf("%lld", &x);
#define scll(x, y)     ll x, y;    scanf("%lld %lld", &x, &y);
#define sclll(x, y, z) ll x, y, z; scanf("%lld %lld %lld", &x, &y, &z);
#define TC(x)          sci(x); while(x --)
#define rep(i, x, y)   for (__typeof(x) i = x; i <= y; i ++)
#define repi(i, x, y)  for (__typeof(x) i = x; i >= y; i --)
#define fore(itr, x)   for (__typeof(x.begin()) itr = x.begin(); itr != x.end(); itr ++)
#define forei(itr, x)  for (__typeof(x.end()) itr = x.end() - 1; itr != x.begin() - 1; itr --)
#define nl cout<<"\n";
void PrintVector(vector<long long int> v,long long int n)
{
 
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
void Takevector(vector<long long int> &v,long long int n)
{
  for(long long int i=0;i <n;i++)
  { long long int number;
    cin>>number;
    v.push_back(number);
  }
}

vector<int> get_Factors(ll n)
{
      vector <int> v;
      for(ll i=1; i<=sqrt(n)+1; i++)
      {
            if(n%i==0)
            {
                  v.push_back(i);
                  v.push_back(n/i);
            }
      }
 
      return v;
}
string get_bin(ll n)
{
    string s = "";
    while(n > 0)
    {
        s += ('0' + n%2);
        n /= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}
 
ll bin_to_dec(string s)
{
    ll ans = 0;
    for(auto ch: s)
    {
        ans *= 2;
        ans += (ch - '0');
    }
    return ans;
}


long long powerexp(long long base, long long exp) {
   long long res = 1;
   while (exp > 0) {
      if (exp % 2 == 1)
         res= (res * base) ;
      exp = exp >> 1;
      base = (base * base) ;
   }
   return res;
}
long long powerexpwithmod(long long base, long long exp, int mod) {
   long long res = 1;
   while (exp > 0) {
      if (exp % 2 == 1)
         res= (res * base) % mod;
      exp = exp >> 1;
      base = (base * base) % mod;
   }
   return res;
}

int gcd(int a, int b)
{
    int c = a % b;
    while(c != 0)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}


int min(int x, int y)  
{  
    return (x < y)? x: y;  
      
}  

int main()
{
	scii(x,y);
	if(y>=2*x&&y<=4*x&&y%2==0) cout<<"Yes";
	else cout<<"No";
return 0;
}










Measured memory_bytes: 3752
/*
  AOJ 1046
  Title:Ghost Buster!
  @kankichi573
*/
#include <stdio.h>
#include <string.h>
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
int H,W;
char ban[20][21];
char reach[20][20];
char reach_b[20][20];
char pattern[11];


move_b(int *yp,int *xp,char m)
{
  //printf("d=[%c]|",m);

  if(m == '8')
    *yp = max(*yp-1,0);
  if(m == '2')
    *yp = min(*yp+1,H-1);
  if(m == '4')
    *xp = max(*xp-1,0);
  if(m == '6')
    *xp = min(*xp+1,W-1);
}

move_a(int *yp,int *xp,int d)
{

  if(d == 1 && *yp > 0 )
    *yp = *yp-1;
  else if(d == 2 && *yp < H-1 )
    *yp = *yp+1;
  else if(d == 3 && *xp > 0) 
    *xp = *xp-1;
  else if(d == 4 && *xp <W-1) 
    *xp = *xp+1;
}

dump(char ban[][21],char reach[][20],int ya,int xa,int yb,int xb)
{
  int i,j;
  char ban2[20][21];

  memcpy(ban2,ban,sizeof(ban2));
  ban2[ya][xa]='A';
  ban2[yb][xb]='B';
  printf("\n");
  for(i=0;i<H;i++)
    {
      for(j=0;j<W;j++)
	if(reach[i][j])
	  {
	    if(ban2[i][j]=='B')
	      printf("b");
	    else if(ban2[i][j]=='A')
	      printf("A");
	    else
	      printf("1");
	  }
	else
	  printf("%c",ban2[i][j]);
      printf("\n");
    }
}
search(char c,int *yp,int *xp)
{
  int i,j;

  for(i=0;i<H;i++)
    for(j=0;j<W;j++)
      if(ban[i][j]==c)
	{
	  *yp=i;*xp=j;
	  return;
	}
    
}
main()
{
  int i,j,k,ret,flag,flag_b,ya,xa,yb,xb,xa1,ya1,time,cyc_tim,len;
  char m,reach2[20][20];

  while(scanf("%d %d",&H,&W)  && (H||W))
    {
      for(i=0;i<H;i++)
	scanf("%s",&ban[i][0]);
      search('A',&ya,&xa);
      search('B',&yb,&xb);
      ban[ya][xa]=ban[yb][xb]='.';
      memset(reach,0,sizeof(reach));
      memset(reach_b,0,sizeof(reach_b));
      scanf("%s",pattern);
      len=strlen(pattern);
      
      reach[ya][xa]=1;
      reach_b[yb][xb]=1;

      time=1,flag=1;
      while(1)
      {
	cyc_tim=(time-1) % len;
	if(cyc_tim==0)
	  flag_b=0;
	m=pattern[cyc_tim];
	move_b(&yb,&xb,m);
	if(reach_b[yb][xb]==0)
	  {
	    reach_b[yb][xb]=1;
	    flag_b=1;
	  }

	flag=0;
	memcpy(reach2,reach,sizeof(reach2));
	for(i=0;i<H;i++)
	  for(j=0;j<W;j++)
	    if(reach[i][j]==1)
	      {
		  //printf("\nreach %d %d|",i,j);
		for(k=1;k<=4;k++)
		  {
		    ya1=i,xa1=j;
		    move_a(&ya1,&xa1,k);
		    //printf("r2 %d %d|",ya1,xa1);
		    if(reach2[ya1][xa1]==0 && ban[ya1][xa1]!='#')
		      {
			reach2[ya1][xa1]=1;
			  flag=1;
		      }
		  }
	      }

	memcpy(reach,reach2,sizeof(reach2));
#ifdef DEBUG
	dump(ban,reach,ya,xa,yb,xb);
#endif	  
	if(reach[yb][xb]==1)
	  {
	    //printf("hit %d %d\n",yb,xb);
	    
	    flag=1;
	    break;
	  }
	
	if(flag==0 && flag_b==0 && cyc_tim==len-1)
	  break;
	time++;
      }
      
      if(flag==0)
	printf("impossible\n");
      else
	printf("%d %d %d\n",time,yb,xb);
	
    }
  return(0);
}

Measured memory_bytes: 620
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

ll a, b, v, w, t;
int main() {
	scanf("%lld %lld %lld %lld %lld", &a, &v, &b, &w, &t);
	printf(abs(a-b)<=(v-w)*t ? "YES\n" : "NO\n");
}

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

int main(){
    double a,b;
    cin >>a>>b;
    if( (double) (a+b)/2==(int)(a+b)/2) cout <<(a+b)/2<<endl;
    else cout<< ((int) (a+b)/2+1)<<endl;
}

Measured memory_bytes: 3776
import java.util.*;

class Main{

    public static void main(String args[]) throws Exception{
        Main main = new Main();
    }

    public Main(){
        Scanner scanner = new Scanner(System.in);
        int H,N;
        H = Integer.parseInt(scanner.next());
        N = Integer.parseInt(scanner.next());
        int total = 0;
        for(int i=0;i<N;i++){
            total += Integer.parseInt(scanner.next());

            if(total >= H){
                System.out.println("Yes");
                return;
            }
        }

        System.out.println("No");
    }
}


Measured memory_bytes: 44060
#include <iostream>
#include <queue>
using namespace std;

int main()
{
    priority_queue<int> queue;
    int n;
    cin >> n;
    queue.push(n);
    cin >> n;
    queue.push(n);
    cin >> n;
    queue.push(n);

    int cost = 0;
    int c;
    c = queue.top(); queue.pop();
    cost += c - queue.top();
    c = queue.top(); queue.pop();
    cost += c - queue.top();

    cout << cost << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
struct Edge {
    int to;
    int cost;
};

class Dijkstra {
public:
    using P = std::pair<int, int>;

    Dijkstra(int v) : vnum(v) {
        this->edges.resize(v);       
    }
    ~Dijkstra() = default;

    void addEdge(int n, int t, int c) noexcept {
        this->edges[n].push_back({t, c});
    }

    // - return the shortest path lengths from s to each vertex
    // - if a vertex is unreachable from s, the value is INT32_MAX  
    std::vector<int> shortestPath(int s) const noexcept {
        std::vector<int> d(vnum, INT32_MAX);

        std::priority_queue<P, std::vector<P>, std::greater<P>> que;
        d[s] = 0;
        que.push(P(0, s));

        while (que.empty() == false) {
            const P p = que.top(); que.pop();
            const int v = p.second;
            if (d[v] < p.first) {
                continue;
            }

            for (const Edge& e : this->edges[v]) {
                if ((d[v] + e.cost) < d[e.to]) {
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }

        }

        return d;
    }
            
private:
    std::vector<std::vector<Edge>> edges;
    int vnum;
};

int main() {
    int V, E, r;
    std::cin >> V >> E >> r;

    Dijkstra dk(V);

    int s, t, d;
    for (int i = 0; i < E; ++i) {
        std::cin >> s >> t >> d;
        dk.addEdge(s, t, d);
    }

    const std::vector<int> paths = dk.shortestPath(r);
    for (int p : paths) {
        if (p == INT32_MAX) {
            std::cout << "INF" << std::endl;
        } else {
            std::cout << p << std::endl;
        }
    }

    return 0;
}



Measured memory_bytes: 12860
x, y = map(int, input().split())

A = [1, 3, 5, 7, 8, 10, 12]
B = [4, 6, 9, 11]
C = [2]

if x in A and y in A:
    print('Yes')
    exit()
if x in B and y in B:
    print('Yes')
    exit()
if x in C and y in C:
    print('Yes')
    exit()

print('No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int A, B, C, D = 0, E = 0;
  cin >> A >> B >> C;
  if (A == 5) D++;
  if (B == 5) D++;
  if (C == 5) D++;
  if (A == 7 || B == 7 || C ==7)
    E++;
  if (D == 2 && E == 1)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 3648
n,k = (int(i) for i in input().split())
d = 0
a = []
c = set( [i for i in range(1,n+1)])
for i in range(k):
	d = int(input())
	a.extend(int(i) for i in (input().split()))

b = set(a)
d = c-b
print(len(d))

""""
n,m = (int(i) for i in input().split())
h = [int(i) for i in input().split()]
ab =[]
for i in range(m):
	ab.append(list(map(int,input().split())))
	"""

Measured memory_bytes: 9204
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    k = int(input())
    a, b = list(map(int, readline().split()))

    x = 0
    while x <= b:
        x += k
        if a <= x <= b:
            print("OK")
            sys.exit()

    print("NG")

if __name__ == '__main__':
    main()


Measured memory_bytes: 61716
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <map>
#include <set>
#include <unordered_set>

typedef long long ll;

int main() {
    ll n;
    std::cin >> n;
    std::vector<ll> vect(n);
    std::vector<ll> prefsum(n);
    for (ll i = 0; i < n; ++i) {
        std::cin >> vect[i];
        prefsum[i] = vect[i];
        if (i != 0) {
            prefsum[i] += prefsum[i - 1];
        }
    }

    std::map<ll, ll> prs;
    for (ll i = 0; i < n; ++i) {
        if (prs.find(prefsum[i]) == prs.end()) {
            prs[prefsum[i]] = 1;
        } else {
            ++prs[prefsum[i]];
        }
    }

    ll ans = 0;
    for (auto iter : prs) {
        ans += ((iter.second * (iter.second - 1)) / 2);
        if (iter.first == 0)
            ans += iter.second;
    }

    std::cout << ans;
}

Measured memory_bytes: 15872
// Problem : F - LCS
// Contest : AtCoder - Educational DP Contest
// URL : https://atcoder.jp/contests/dp/tasks/dp_f
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#include<set>
#include<map>
#include<bitset>
#define rep(i,a,b)  for(i=a;i<b;i++)
#define Sort(a)	sort(a.begin(),a.end())
#define rev(a)	reverse(a.begin(),a.end())
#define all(a)	(a).begin(),(a).end()
#define vll vector<long long int>
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define db double
#define M 1000000007
#define pi 3.1415926535897932384626433832795028841971
#define INF 1e18

#define MAX 200005

using namespace std;
lli min(lli a,lli b){return a<b?a:b;}
lli min(lli a,lli b,lli c){a=min(a,b);a=min(a,c);return a;}
lli max(lli a,lli b){return a>b?a:b;}
lli max(lli a,lli b,lli c){a=max(a,b);a=max(a,c);return a;}
lli dsum(lli n){lli ans=0;while(n){ans+=(n%10);n/=10;}return ans;}
lli power(lli a,lli b){lli res=1;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;}
lli power(lli a,lli b,lli m){if(b==0)	return 1;if(b==1)	return a%m;lli res=1;a=a%m;while(b){if(b&1){res=(res*a)%m;}a=((a%m)*(a%m))%m;b>>=1;}return res;}
lli Ceil(lli a,lli b){lli res=a/b;if(a%b!=0)	res++;return res;}

template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

lli dxx[]={1,1,0,-1,-1,-1,0,1};
lli dyy[]={0,1,1,1,0,-1,-1,-1};
lli dx[]={1,0,-1,0};
lli dy[]={0,1,0,-1};

struct pll{
	lli x,y;
};
bool comp(pll a,pll b){
	if(a.x==b.x)	return a.y<b.y;
	else	return a.x<b.x;
}
string LCSqs(string s,string t)
{
	lli n,m;
	n=s.length();
	m=t.length();
	lli dp[n+1][m+1];
	for(lli i=0;i<=n;i++){
		for(lli j=0;j<=m;j++){
			if(i==0||j==0)	dp[i][j]=0;
			else{
				if(s[i-1]==t[j-1]){
					dp[i][j]=1+dp[i-1][j-1];
				}
				else{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
	}
	lli x,y;
	string ans;
	lli sum=-1;
	for(lli i=1;i<=n;i++){
		for(lli j=1;j<=m;j++){
			if(sum<dp[i][j]){
				sum=dp[i][j];
				x=i;
				y=j;
			}
		}
	}
	ans="";
	while(dp[x][y]!=0 && x>=0 && y>=0){
		if(s[x-1]==t[y-1]){
			ans.push_back(s[x-1]);
			x--;y--;
		}
		else{
			if(dp[x][y]==dp[x-1][y]){
				x--;
			}
			else{
				y--;
			}
		}
	}
	reverse(ans.begin(),ans.end());
	return ans;
}
void solve(lli the)
{
	char ch;
	db aa,bb,cc,dd,xx;
	string s1,s2,s3,str;
    lli i,j,k,a,b,c,d,n,m,l,r,x,y,z,low,high,mid,sum=0,ans=0,temp,t;
    cin >> s1 >> s2;
    cout << LCSqs(s1,s2) << endl;
    
    
}













int main()
{
	long long int t=1,c=1;
	// scanf("%lld",&t);
	while(t--){
		solve(c);
		c++;
	}
	return 0;
}
/* UJJWAL KESHRI */

Measured memory_bytes: 73976
/****************************************************************
# @Author:      iLovePKU_zbtxdy
# @DateTime:    2020-02-07 20:47:05
# @Description: Think twice. Code once. 
# @More: Once lots of AC, try Brute-force,dynamic programming
****************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define close std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define eps 1e-8
typedef long long ll;
const int maxn = 1e6+10;
const int INF = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
ll mod = 1e9+7;
int a, b , c , d , e , f;
int dp[5050][5050];
double td = 0.0;
int tot = 0, ans = 0;
void dfs(int sugar , int water ){
    if(dp[sugar][water] != -1)return;
    dp[sugar][water] = 1;
    if(sugar *100 > e*water)return ;
    if(sugar + water > f)return ;
    if (tot==0 || sugar * tot > ans*(sugar+water)){
        if (water>0){
            ans = sugar;
            tot = sugar + water;
        }
    }
    dfs(sugar, 100*a+water);
    dfs(sugar, 100*b+water);
    dfs(sugar + c, water);
    dfs(sugar + d, water);
}
int main()
{
    cin >> a >> b >> c >> d >> e >> f;
    memset(dp , 0xff , sizeof dp);
    dfs(0, 0);
    cout << tot << ' ' << ans << endl;
}
/***************************************************************************
*stuff you should look for
*int overflow, array bounds
*special cases (n=1?), set tle
*do smth instead of nothing and stay organized
***************************************************************************/

Measured memory_bytes: 99840
#include <bits/stdc++.h>
#define INF 2e9
#define MOD 1000000007
using namespace std;
typedef long long llong;
typedef long double ldouble;

using Graph = vector<vector<int>>;

// int ctoi(const char c){
//   if('0' <= c && c <= '9') return (c-'0');
//   return -1;
// }

// int gcd(int a, int b){
//   int ma = max(a,b);
//   int mi = min(a,b);
//   if(mi == 0) return ma;

//   return gcd(mi, ma%mi);
// }

int main(){
  llong A, B, N;
  cin >> A >> B >> N;
  llong q = A / B;
  llong r = A % B;
  llong x;
  if(B > N) x = N;
  else x = B-1;
  cout << q * x + (r * x) / B << endl;
}

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

int t(int h, int m, int s){
  return h*60*60 + m*60 + s;
}

void print(int t){
  int m,s;
  s = t%60; t/=60;
  m = t%60; t/=60;
  cout << t << " " << m << " " << s << endl;
}

int main(){
  for(int i=0;i<3;i++){
    int h,m,s, S,T;
    cin >> h >> m >> s;
    S = t(h,m,s);
    cin >> h >> m >> s;
    T = t(h,m,s);
    T -= S;
    print(T);
  }
}

Measured memory_bytes: 1160
//       Author: Mostafa Mounir Shehab
 
#include <bits/stdc++.h>
using namespace std;
 
#define PI  3.14159265  // PI = acos(-1)
#define EPS (1e-10)
#define endl "\n"
#define SZ(v) (int)(v.size())
typedef long long ll;
typedef long double ld;
//template <class Type>
 
 
void Fast(){
	std::ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL);
}
 
inline int D(){
	int t;
	scanf("%d",&t);
	return t;
}
inline ll llD(){
	ll t;
	scanf("%lld",&t);
	return t;
}
 
 
ll MOD=1e9 + 7;
ll OO=1e15;
const int N=1e2 + 5,M=1e5 + 3;
ll arr[N];
ll pre[N];
ll dp[N][M];


ll n,m,k,cnt,SU,idx,len,MN,MX,T;
ll l,r,mid;
ll a,b,c,d;
vector<pair<int,pair<int,char>>> vec;
string str,t,ans;
bool flage;

ll Solve(int idx,int val){
	
	if(idx == n)
		return !val ? 0 : OO;
	
	ll &ret = dp[idx][val];
	if(~ret)
		return ret;
	
	ret = Solve(idx+1,val);
	
	if(pre[idx] <= val)
		ret = min(ret , arr[idx] + Solve(idx+1,val-pre[idx])); 
	
	return ret;
}




int main(){
	
	memset(dp,-1,sizeof dp);
	cin>>n>>m;
	for(int i=0;i<n;++i)
		cin>>arr[i]>>pre[i];
	
	int MX=0;
	for(int i=1;i<M;++i)
		if(Solve(0,i) <= m)
			MX=i;
		
	cout<<MX<<endl;
	
	


}



















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

int n;
int pre[40];
int in[40];
vector<int> past;

//pre[id]??????????????????, in[l, r)?????¨?????¨v???????????????
void dfs(int id, int l, int r) {
	if (r - l == 1) {
		past.push_back(pre[id]);
		return;
	}
	
	int i;
	for (i = 0; i < r - l; i++) {
		if (in[l + i] == pre[id]) {
			break;
		}
	}
	if (i > 0) {
		dfs(id + 1, l, l + i);
	}
	if (l + i + 1 < r) {
		dfs(id + 1 + i, l + i + 1, r);
	}
	past.push_back(pre[id]);
}

int main() {
	int i;
	cin >> n;
	for (i = 0; i < n; i++) cin >> pre[i];
	for (i = 0; i < n; i++) cin >> in[i];
	dfs(0, 0, n);
	
	for (i = 0; i < past.size(); i++) {
		cout << past[i];
		if (i + 1 < past.size()) cout << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3168
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner((System.in));
		int x = sc.nextInt();
		int y = sc.nextInt();
		int z = sc.nextInt();
		int a = 0;
		
		x -= z;

		while (x >= y + z) {
			x -= (y + z);
			a++;
		}
		
		System.out.println(a);

		sc.close();
	}
}

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

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

int h, w, a[200][200];
int dp[200][200][200];

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

int main() {
    cin >> h >> w;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> a[i][j];
    fill_n(**dp, 200 * 200 * 200, -1e9);

    dp[0][0][0] = a[0][0];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            for (int ii = 0; ii < h; ii++) {
                int jj = (i + j) - ii;
                for (int k = 0; k < 2; k++) {
                    for (int kk = 0; kk < 2; kk++) {
                        int ni = i + dy[k];
                        int nj = j + dx[k];
                        int nii = ii + dy[kk];
                        int njj = jj + dx[kk];
                        if (ni >= h || nii >= h || nj >= w || njj >= w) continue;
                        int gain = 0;
                        if (ni == nii && nj == njj) {
                            gain = a[ni][nj];
                        } else {
                            gain = a[ni][nj] + a[nii][njj];
                        }
                        chmax(dp[ni][nj][nii], dp[i][j][ii] + gain);
                    }
                }
            }
        }
    }

    cout << dp[h - 1][w - 1][h - 1] << endl;
}

Measured memory_bytes: 31616
import Control.Monad
import Control.Monad.ST
import Data.List
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Unboxed.Mutable as MV

mk h w as = runST $ do
    v' <- MV.replicate (h*w) (0,0) :: ST s (MV.STVector s (Int,Int))
    forM_ (zip [(i,j)|i<-[1..h],j<-[1..w]] as) $ \((i,j),a) ->
        MV.unsafeWrite v' (a-1) (i,j)
    UV.unsafeFreeze v'

main = do
    (h:w:d:_)<-map read.words<$>getLine::IO[Int]
    as<-fmap concat $ replicateM h $ map read.words<$>getLine::IO[Int]
    q<-readLn::IO Int
    lrs<-replicateM q $ unfoldr (B.readInt.B.dropWhile(==' '))<$>B.getLine::IO[[Int]]
    --
    let lij = mk h w as
    --
    spp <- fmap V.fromList $ forM [0..d-1] $ \s -> do
        sp <- forM [s,(s+d)..(h*w)-d-1] $ \l -> do
            let (si,sj) = lij UV.! l
            let (ei,ej) = lij UV.! (l+d)
            return $ abs (si-ei) + abs(sj-ej)
        return $ UV.fromList $ scanl (+) 0 sp
    --
    putStr $ unlines $ map show $ map (solve spp d) lrs
--
solve spp d (l:r:_) = (p r1 r2) - (p l1 l2) 
    where
        l1 = (l+(d-1)) `mod` d
        l2 = (l-1) `div` d
        r1 = (r+(d-1)) `mod` d
        r2 = (r-1) `div` d
        p a b = (spp V.! a) UV.! b


Measured memory_bytes: 77308
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

inline int toInt(string s) {int v; istringstream sin(s);sin>>v; return v;}

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector< vector<int> > Mat;
typedef tuple<int, int, int, int> T;

const int MOD = (int)1e9+7;
const int INF = (int)1e9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

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

    int N;
    cin >> N;

    vector<bool> prime(N+1, true);
    prime[0] = prime[1] = false;
    for(int i = 2; i*i <= N; i++){
        if(prime[i] == false) continue;
        int tmp = 2;
        while(tmp*i <= N){
            prime[tmp*i] = false;
            tmp++;
        }
    }

    ll ans = 1;
    rep(i, N+1){
        if(prime[i] == false) continue;
        ll cnt = 0;

        FOR(j, i, N+1){
            int tmp = j;
            while(tmp % i == 0 && tmp != 0){
                tmp /= i;
                cnt++;
            }
        }
        if(0 < cnt) ans *= (cnt+1);
        ans %= MOD;
    }

    cout << ans << endl;

    return 0;
}

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


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  constexpr char endl = '\n';

  int N, W;
  cin >> N >> W;

  vector<int> values;
  vector<int> weights;
  for (int i=0; i<N; ++i) {
    ll w, v;
    cin >> w >> v;
//    items.emplace_back(make_pair(w, v));
    weights.push_back(w);
    values.push_back(v);
  }

  // dp[i][w]: maximum values when i-th item is the last item included
  vector<vector<ll>> dp(N, vector<ll>(W+1,0));
  for (ll i=0; i<N; ++i) {
    for (ll j=0; j<=W; ++j) {
      // _ _ _ ... _ _ _
      //               ^
      //               i
      if (i==0) {
        dp[i][j]=(j>=weights[i]?values[i]:0);
      }
      else if (weights[i]<=j) {
        ll not_included=dp[i-1][j];
        ll included=dp[i-1][j-weights[i]]+values[i];
        dp[i][j]=max(not_included, included);
      }
      else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }

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

  return 0;
}


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

int main(){
  string S; cin >> S;
  int maxLen = 0;
  int a = 0;
  for(int i = 0; i < (int)S.size(); i++){
    if(S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T'){
      a++;
    }
    else a = 0;
    maxLen = max(maxLen,a);
  }
  cout << maxLen << endl;
}

Measured memory_bytes: 256
N, W = map(int, input().split())
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    v, w = map(int, input().split())
    for j in range(W+1):
        if j-w >= 0:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j-w]+v)
        else:
            dp[i+1][j] = dp[i][j]
print(dp[N][W])


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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep3(i,m,n) for(int (i)=m;(i)<=(n);(i)++)
#define rep3rev(i,m,n) for(int (i)=m;(i)>=(n);(i)--)
#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

void Main()
{
	int n;
	cin >> n;
	vi a(n);
	rep(i,n) {cin >> a[i]; a[i]--;}
	int now = 0;
	vi seen(n,0);
	seen[0] = 1;
	int cnt = 0;
	while(1){
		cnt++;
		if(seen[a[now]] == 1) {
			cout << -1 << endl;
			return;
        }else if(a[now] == 1){
			cout << cnt << endl;
			return;
        }
		now = a[now];
		seen[now] = 1;
    }
  
	cout << "error" << endl;
	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;
typedef pair<int, int>P;
 
P h[3000];
int main() {
    int n;
    while (scanf("%d", &n), n) {
        rep(i, n)scanf("%d%d", &h[i].first, &h[i].second);
        sort(h, h + n);
        int Max = 0;
        rep(i, n) {
            for (int j = i + 1; j < n; j++) {
                int x = h[j].first - h[i].first,y = abs(h[j].second - h[i].second);
                if (!x)continue;
                P a = { h[i].first,h[i].second + x },b = { h[j].first,h[j].second + x };
                if (h[i].second < h[j].second) {
                    a.first -= y; b.first -= y;
                }
                else {
                    a.first += y; b.first += y;
                }
                if (binary_search(h, h + n, a) && binary_search(h, h + n, b))
                    Max = max(Max, (x + y)*(x + y) - x*y * 2);
            }
        }
        printf("%d\n", Max);
    }
}

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

using namespace std;

int n;
string str;
set<int> data;

int solve(){
   for(int cnt=0;;cnt++){
      if(str.size() == 1) return cnt;
      int tmp = atoi(str.c_str());
      if(data.find(tmp) != data.end()) break;
      data.insert(atoi(str.c_str()));
      int valM = 0;
      for(int i=1;i<str.size();i++){
	 int a = atoi(str.substr(0, i).c_str());
	 int b = atoi(str.substr(i).c_str());
	 valM = max(valM, a * b);
      }
      str = "";
      if(valM == 0) str += '0';
      else{
	 while(valM){
	    str += (char)(valM % 10) + '0';
	    valM /= 10;
	 }
	 reverse(str.begin(), str.end());
      }
   }
   return -1;
}

main(){
   cin >> n;
   for(int i=0;i<n;i++){
      data.clear();
      cin >> str;
      cout << solve() << endl;
   }
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back 
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define pii pair<int,int>
#define ld long double
#define int long long int 
#define F first 
#define S second
const int N = 1e5+1;
vector<int> adj[N];
int visit[N];
map<pii,int> mp;
int ans = 1;
void dfs(int src,int pc)
{
    visit[src] = 1;
    int color = 1;
    for(auto it:adj[src])
    {
        if(!visit[it])
        {
            if(color == pc)
                color++;
            mp[{it,src}] = color;
            mp[{src,it}] = color;
            ans = max(ans,color);
            dfs(it,color);
            color++;
        }
    }
}
signed main()
{
    fast;
    int n;
    cin>>n;
    vector<pii> edges;
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        edges.pb({a,b});
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1,0);
    cout<<ans<<"\n";
    for(auto it:edges)
    {
        cout<<mp[{it.first,it.second}]<<"\n";
    }
}

Measured memory_bytes: 21364
n=int(input())
s=str(input())
e_cnt=s.count('E')
num=[0]*n #Wの数
num2=[0]*(n+1) #Eno左から数えた数
count=0
count2=0
for i in range(n):
    if s[i]=='W':
        num[i]=count
        num2[i]=e_cnt-count2
        count+=1
    else:
        num[i]=count
        num2[i]=e_cnt-count2 
        count2+=1
    
   
#print(num,num2)

ans=[0]*n

for i in range(n):
    ans[i]=abs(num[i]+num2[i+1])
print(min(ans))



Measured memory_bytes: 37964
#include <bits/stdc++.h>
#define int long long
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,x[11111],y[11111],z[11111],ans=-1e16;
int d[]={1,-1};
main(){
  cin>>n>>m;
  r(i,n){
    cin>>x[i]>>y[i]>>z[i];
  }
  r(a,2)r(b,2)r(k,2){
    vector<int>v;
    r(i,n)v.push_back(x[i]*d[a]+y[i]*d[b]+z[i]*d[k]);
    sort(v.begin(),v.end(),greater<int>());
    int a=0;
    r(i,m)a+=v[i];
    ans=max(ans,a);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    int n;
    cin>>n;
    string a,b,c;
    cin>>a>>b>>c;
    int cnt=0;
    for(int i=0; i<n; i++){
        map<char,int>x;
        x[a[i]]++;
        x[b[i]]++;
        x[c[i]]++;
        if(x.size()==2)cnt+=1;
        if(x.size()==3)cnt+=2;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 256
n = int(input())
t = list(map(int, input().split()))

m = int(input())

px = []
for i in range(m):
  px.append(list(map(int,input().split())))

for i in px:
  tClone = t[:]
  tClone[i[0] - 1] = i[1]
  print(sum(tClone))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int S[MAX_N];
int X[MAX_N];
vector<int> G[MAX_N];

bool loop(int v, int p) {
	vector<vi> dp(2, vi(X[v] + 1, inf));
	int now = 0, next = 1;
	dp[0][0] = 0;
	rep(i, 0, sz(G[v])) {
		fill(dp[next].begin(), dp[next].begin() + X[v] + 1, inf);
		int n = G[v][i];
		loop(n, v);
		rep(w, 0, X[v] + 1) {
			if(dp[now][w] == inf) continue;
			if(w + X[n] <= X[v]) MIN(dp[next][w + X[n]], dp[now][w] + S[n]);
			if(w + S[n] <= X[v]) MIN(dp[next][w + S[n]], dp[now][w] + X[n]);
		}
		swap(now, next);
	}
	S[v] = inf;
	rep(i, 0, X[v] + 1) MIN(S[v], dp[now][i]);
	if(S[v] != inf) return true;
	else return false;
}
		

void solve() {
	cin >> N;
	fill(S, S + N, inf);
	rep(i, 0, N - 1) {
		int a; cin >> a; a--;
		G[a].pb(i + 1);
	}
	rep(i, 0, N) cin >> X[i];
	if(loop(0, -1)) cout << "POSSIBLE\n";
	else cout << "IMPOSSIBLE\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
#ifdef LOCAL
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



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

#define INF 1LL<<60

int main() {
    int h, n;
    cin >> h >> n;
    int a[1010], b[1010];
    vector<long long> dp(h + 1, INF);

    for (int i = 0; i < n; i++)
        cin >> a[i] >> b[i];

    dp[h] = 0;
    for (int i = h; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            int next = max(0, i - a[j]);
            dp[next] = min(dp[next], dp[i] + b[j]);
        }
    }
    cout << dp[0] << endl;

    return 0;
}


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

 int main()
 {
     long long takahashi, aoki, k;
     cin >> takahashi >> aoki >> k;
     for(int i = 1; i < (k + 1); i++)
     {
         if(i % 2 != 0)
         {
             if(takahashi % 2 != 0)
             {
                 takahashi = takahashi - 1;
             }

             aoki = aoki + takahashi/2;
             takahashi = takahashi/2;
         }

         if(i % 2 == 0)
         {
             if(aoki % 2 != 0)
             {
                 aoki = aoki - 1;
             }

             takahashi = takahashi + aoki/2;
             aoki = aoki/2;

         }
     }

     cout << takahashi << " " << aoki;
     return 0;
 }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

LL n, k, a[100000], b[40], dp[41][2];

LL z(LL x, LL y) { return (y == 0 ? x : n - x); }

int main() {
	cin >> n >> k;
	inc(i, n) { cin >> a[i]; }
	
	inc(i, n) {
	inc(j, 40) {
		b[j] += bit(a[i], j);
	}
	}
	
	dp[40][0] = 0;
	dp[40][1] = -1;
	dec(i, 40) {
		LL dp0 = dp[i + 1][0];
		LL dp1 = dp[i + 1][1];
		LL v0 = z(b[i], bit(k, i));
		LL v1 = max(z(b[i], 0), z(b[i], 1));
		dp[i][0] =                   dp0 + v0 * (1LL << i);
		dp[i][1] = (dp1 == -1 ? -1 : dp1 + v1 * (1LL << i));
		if(bit(k, i)) { setmax(dp[i][1], dp0 + z(b[i], 0) * (1LL << i)); }
		
	}
	
	// dec(i, 41) { cout << dp[i][0] << " " << dp[i][1] << endl; }
	
	cout << max(dp[0][0], dp[0][1]) << endl;
	
	return 0;
}


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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

int main(){

    int x,y;
    cin>>x>>y;

    int a2=4*x-y;
    if(y%2==0 && a2<=2*x && a2>=0)cout<<"Yes\n";
    else cout<<"No\n";

    return 0;

}

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

int main()
{
	
	int sx,sy,tx,ty;
	
	cin>>sx>>sy>>tx>>ty;
	int x=tx-sx;
	int y=ty-sy;
	
	int i;
	for(i=1;i<=x;i++)
	  cout<<"R";
	for(i=1;i<=y;i++)
	  cout<<"U";
	for(i=1;i<=x;i++)
	  cout<<"L";
	for(i=1;i<=y;i++)
	  cout<<"D";
	
	cout<<"D";
	for(i=1;i<=x+1;i++)
	  cout<<"R";
	for(i=1;i<=y+1;i++)
	  cout<<"U";
	cout<<"LU";
	for(i=1;i<=x+1;i++)
	 cout<<"L";
	 for(i=1;i<=y+1;i++)
	  cout<<"D";
	  
	  cout<<"R"<<endl;
	
	
	
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MAX_SIZE 100 // Maximum string size

int main()
{
    char str[MAX_SIZE];
    int i, len, status;
    int freq[26];

    cin >> str;

    len = strlen(str);

    /* Initialize frequency of each character to 0 */
    for(i=0; i<26; i++)
    {
        freq[i] = 0;
    }


    /* Find total number of occurrences of each character */
    for(i=0; i<len; i++)
    {
        /* If the current character is lowercase alphabet */
        if(str[i]>='a' && str[i]<='z')
        {
            freq[str[i] - 97]++;
        }
        else if(str[i]>='A' && str[i]<='Z')
        {
            freq[str[i] - 65]++;
        }
    }

    for(i=0; i<26; i++)
    {
        /* If current character exists in given string */
        if(freq[i]%2 == 0)
        {
            status = 1;
        }
        else{
            status = -1;
            break;
        }
    }
    if(status == -1)
        cout << "No";
    else if(status == 1)
        cout << "Yes";

    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define ct(string) cout << string << endl

int main() {
    vector<bool> alpha(26,false);
    char c;
    while (cin >> c) {
        alpha.at(c-'a') = true;
    }
    rep(i,26) {
        if (alpha.at(i) == false) {
            ct((char)(i+'a'));
            return 0;
        }
    }
    ct("None");
}

Measured memory_bytes: 256