akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <deque>
#include <math.h>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <queue>
#include <vector>

#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define rFOR(i, a, b) for(int (i) = (b); (i) >= (a); --(i))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) rFOR(i, 0, (n-1))
#define SORT(A) std::sort((A).begin(), (A).end())
#define ALL(A) (A).begin(), (A).end()
// 座標圧縮 (for vector) : ソートしてから使うのが一般的 ; SORT(A) => COORDINATE_COMPRESSION(A)
#define COORDINATE_COMPRESSION(A) (A).erase(unique((A).begin(),(A).end()),(A).end())

using lli = long long int;
using pii = std::pair<int, int>;

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

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


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~




int main(void){
    int n; scanf("%d", &n);
    int ok = 0;
    REP(i, n){
        int a; scanf("%d", &a);
        if(ok + 1 == a) ok++;
    }
    if(ok == 0) puts("-1");
    else printf("%d\n", n - ok);


    


    return 0;
}


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

int main(){
long long n,d;
cin>>n>>d;
long long x,y;
long long ans=0;
for(long long i=0;i<n;i++){
    cin>>x>>y;
    if(x*x+y*y<=d*d){
        ans++;
    }
}
cout<<ans<<endl;
    return 0;
}


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

int main(){
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;

    string route;

    for(int i=0; i<tx-sx; i++){
        route.push_back('R');
    }
    for(int i=0; i<ty-sy; i++){
        route.push_back('U');
    }
    for(int i=0; i<tx-sx; i++){
        route.push_back('L');
    }
    for(int i=0; i<ty-sy; i++){
        route.push_back('D');
    }

    route.push_back('D');
    for(int i=0; i<tx-sx+1; i++){
        route.push_back('R');
    }
    for(int i=0; i<ty-sy+1; i++){
        route.push_back('U');
    }
    route.push_back('L');
    route.push_back('U');
    for(int i=0; i<tx-sx+1; i++){
        route.push_back('L');
    }
    for(int i=0; i<ty-sy+1; i++){
        route.push_back('D');
    }
    route.push_back('R');

    cout << route << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

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

    int ans = 3*n*n;

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


Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

int v[209][209];

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

void init() {
	for (int i = 1; i <= 200; i++) {
		for (int j = 1; j <= 200; j++) {
			v[i][j] = gcd(i, j);
		}
	}
}

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

	long long sum = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {
				sum += v[v[i][j]][k];
			}
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3796
// Never Give Up!
#include <stdio.h>
#include <iostream>
#include <limits>
#include <cstdint>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <bitset>
#include <array>
#include <string.h>
#include <stack>
#include <queue>
#include <stdint.h>
#include <sstream>
#include <map>
#include <set>
#include <locale>
#define mem(x, y) memset(x, y, sizeof x);
#define __STDC_LIMIT_MACROS
#define fio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int maxn = 2 * 1e5 + 10 , INF = 1e9;
int n , a[maxn] , ta[maxn];
map<int , int> mp;

int main(){     
      
	fio;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		ta[i] = a[i];
	}
	sort(a + 1 , a + n + 1);
	for(int i = 1; i <= n; i++){
		if(i <= n / 2) mp[a[i]] = a[n/2 + 1];
		else mp[a[i]] = a[n/2];
	}


	for(int i = 1; i <= n; i++){
		cout << mp[ta[i]] << endl;
	}


    	return 0;
}

Measured memory_bytes: 12928
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, a, b) for(int i = a, i##_len = (b); i < i##_len; ++i)

int main()
{
    int X;
    scanf("%d", &X);
    int res = 0;
    for(int a = 0; a*100 <= X; ++a) 
        for(int b = 0; a*100+b*101 <= X; ++b)
            for(int c = 0; a*100+b*101+c*102 <= X; ++c)
                for(int d = 0; a*100+b*101+c*102+d*103 <= X; ++d)
                    for(int e = 0; a*100+b*101+c*102+d*103+e*104 <= X; ++e)
                        for(int f = 0; a*100+b*101+c*102+d*103+e*104+f*105 <= X; ++f)
                            if(a*100+b*101+c*102+d*103+e*104+f*105 == X) {
                                printf("1\n"); return 0;
                            }
    printf("0\n");
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
 
using namespace std;
 
 int main(void){
	 int H,W;
	 cin >> H >> W;
	 char check[H][W];
	 for(int i=0; i<H; i++){
		 for(int j=0; j<W; j++){
			cin >> check[i][j];
		 }
	 }	 
	char ans[H][W];
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			ans[i][j]=check[i][j];
		}
	}
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			if(check[i][j] == '.'){
				int cnt=0;
				if(i>0 && check[i-1][j] == '#') cnt++;
				if(i<H-1 && check[i+1][j] == '#') cnt++;
				if(j>0 && check[i][j-1] == '#') cnt++;
				if(j<W-1 && check[i][j+1] == '#') cnt++;
				if(i>0 && j>0 && check[i-1][j-1] == '#') cnt++;
				if(i>0 && j<W-1 && check[i-1][j+1] == '#') cnt++;
				if(i<H-1 && j>0 && check[i+1][j-1] == '#') cnt++;
				if(i<H-1 && j<W-1 && check[i+1][j+1] == '#') cnt++;
				ans[i][j]=char('0'+cnt);
			}
		}
	}
	for(int i=0; i<H; i++){
		for(int j=0; j<W; j++){
			cout << ans[i][j];
		}cout << endl;
	}
 }

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static void solve() {
		String s = in.next();
		int n = s.length();
		ArrayDeque<Integer> stack = new ArrayDeque<>();
		for (int i=0; i<n; i++) {
			switch (s.charAt(i)) {
				case '0': stack.addLast(0); break;
				case '1': stack.addLast(1); break;
				case 'B': stack.pollLast(); break;
			}
		}
		for (int i : stack) {
			out.print(i);
		}
		out.println();
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 9556
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<map>
#include<set>

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(a) (a).begin(),(a).end()
#define PI 3.141592653589793238
#define INF 1050000000
#define INFL (long long)(4e18)

using vi = vector<int>;

template<class T>
struct Edge {
	int to;
	T cost;
	Edge() {};
	Edge(int to, T cost) : to(to), cost(cost) {};
};

template<class T>
class Graph {
	int n;
	bool directed;
	vector<vector<Edge<T>>> edges;
public:

	Graph(int n, bool directed) :n(n), directed(directed), edges(vector<vector<Edge<T>>>(n)) {};
	Graph() {};

	void add(int to, T cost) {
		emplace_back(to, cost);
	}

	int size() {
		return n;
	}
};


int main() {

	double R;

	cin >> R;

	cout << fixed << setprecision(15) << R*2.0*PI << endl;

	return 0;
}

Measured memory_bytes: 3772
#include <stdio.h>

int main() {
    int n, x;

    while (1) {
        scanf("%d %d", &n, &x);
        if (n == 0 && x == 0) { break; }

        int count = 0;
        for (int i=1; i<x; ++i) {
            for (int j=i+1; j<=x-i; ++j) {
                int k = x - i - j;

                if (k <= j) { break; }
                if (n >= k && !(i == k || j == k)) {
                    ++count;
                }
            }
            if (i + i + 1 >= x) {
                break;
            }
        }
        printf("%d\n", count);
    }

    return 0;
}



Measured memory_bytes: 2144
#define _DEBUG 1
#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#ifdef _DEBUG
#define dump(x) cerr << #x << "=" << x << endl
#define dump2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define dump3(x, y, z)                                                     \
  cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z \
       << endl
#define check(s) cerr << s << endl
#else
#define dump(x)
#define dump2(x, y)
#define dump3(x, y, z)
#define check(s)
#endif

#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());

const ll LINF = 2e18;
const int INF = 1e9;

void solve(ll N, std::string S) {
  int cnt = 0;
  for (int i = 0; i < N - 2; i++) {
    if (S.at(i) == 'A' && S.at(i + 1) == 'B' && S.at(i + 2) == 'C') {
      cnt++;
    }
  }
  cout << cnt << endl;
}

int main() {
  ll N;
  scanf("%lld", &N);
  std::string S;
  std::cin >> S;
  solve(N, S);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int n,s;
  int m[100][100];
  cin>>n;
  int a=-10001;
  for(int i=0;i<n;++i){
    for(int j=0;j<n;++j){
      cin>>m[i][j];
      a=max(a,m[i][j]);
    }
  }
  for(int i=0;i<n;++i){
    int p[100]={0};
    for(int j=i;j<n;++j){
      s=0;
      for(int k=0;k<n;++k){
	p[k]+=m[j][k];
	s=max(s+p[k],0);
	if(s>0) a=max(a,s);
      }
    }
  }
  cout<<a<<endl;
  return 0;
}

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

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

string shuffle(string s, int h)
{
    string result = "";
    for (int i = h; i < s.size(); i++)
    {
        result += s[i];
    }
    rep(i, h)
    {
        result += s[i];
    }
    return result;
}

int main()
{
    vector<string> ans;
    string s;
    while (cin >> s, s != "-")
    {
        int m;
        cin >> m;
        rep(i, m)
        {
            int h;
            cin >> h;
            s = shuffle(s, h);
        }
        ans.push_back(s);
    }
    rep(i, ans.size())
    {
        cout << ans[i] << endl;
    }
}


Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  
  int A,B,C,D;
  
  cin>>A>>B>>C>>D;
  
  if(A+B==C+D){
    cout<<"Balanced"<<endl;
  }
  
  else if(A+B>C+D){
    cout<<"Left"<<endl;
  }
  
  else{
    cout<<"Right"<<endl;
  }
  
}

Measured memory_bytes: 256
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  char a;
  scanf("%c", &a);
  printf("%c\n", a + 1);
}

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

using namespace std;

int main(){
    int N, D; cin >> N >> D;
    vector<vector<int>> X(N, vector<int>(D)); //N行D列
    for(int i=0; i<N; ++i){
        for(int j=0; j<D; ++j){
            cin >> X[i][j]; //2次元の標準入力受け取り
        }
    }
    int ans = 0;
    for(int i=0; i<N; ++i){
        for(int j=i+1; j<N; ++j){
            int norm = 0;
            for(int k=0; k<D; ++k){
                int diff = abs(X[i][k] - X[j][k]);
                norm += diff * diff;
            }

            bool flag = false;
            for(int k=0; k<=norm; ++k){
                if(k*k == norm){
                    flag = true;
                }
            }
            if(flag) ++ans;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <climits>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <cstdio>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#include <set>
#include <map>
#include <complex>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
long long MOD = 998244353;
long long INF = 1000000000000000; //10^15
typedef long long ll;
typedef unsigned long long ull;


ll powMod(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll t = powMod(x, n/2, mod);
  t = t * t % mod;
  if (n & 1) return t * x % mod;
  return t;
}

ll gcd(ll a, ll b) {
  if (a == 0 || b == 0) return a + b;
  if (b > a) return gcd(b, a);
  return gcd(b, a % b);
}

int main(void) {

  string s;
  int n;
  cin >> n >> s;

  ll r = 0, g = 0, b = 0;
  rep(i, n) {
    if (s[i] == 'R') r++;
    if (s[i] == 'G') g++;
    if (s[i] == 'B') b++;
  }

  ll x = 0;
  rep(i, n) {
    rep(j, n) {
      if (i+2*j >= n) break;
      if (s[i] != s[i+j] && s[i+j] != s[i+2*j] && s[i+2*j] != s[i]) x++;
    }
  }

  cout << r*g*b-x << endl;
}
  
      


Measured memory_bytes: 3636
import math
import itertools
N = int(input())
town = [list(map(int, input().split())) for _ in range(N)]
path = []
for p in itertools.permutations(town):
    path.append(sum([math.sqrt((p[i+1][0]-p[i][0])**2 + (p[i+1][1]-p[i][1])**2) for i in range(len(p)-1)]))

print(sum(path)/len(path))

Measured memory_bytes: 43740
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

int n;
ll p,q;
ll c[500001];

int main(void){
	scanf("%d %lld %lld",&n,&p,&q);
	ll all=0;
	ll minus=0;
	for(int i=0;i<n;i++){
		scanf("%lld",&c[i]);
		c[i]+=(ll)p*i;
		minus+=(ll)p*i;
		all+=c[i];
	}
	sort(c,c+n);
	ll res=all;
	for(int i=0;i<n;i++){
		all+=(p*q-c[i]);
		res=max(res,all);
		q=q+2LL;
	}
	printf("%lld\n",res-minus);
	return 0;
}

Measured memory_bytes: 4948
#include <bits/stdc++.h>
#define ll long long
using namespace std;
  
int main(){
  ll n, k;
  ll a, b;
  cin >> n >> k;
  map<ll, ll> mp;
  for(int i = 0; i < n; i++){
    cin >> a >> b;
    mp[a] += b;
  }
  ll sum = 0;
  for(auto& itr : mp){
    sum += itr.second;
    if(sum >= k){
      cout << itr.first << endl;
      return 0;
    }
  }
}

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

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

    int a;
    int b;
    int c;
    cin >> a >> b;

    c = (a + b) / 2;
    if ((a + b) > c * 2) {
      c++;
    }
    cout << c << endl;
}

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

int main() {
	string s;
	cin >> s;
	printf("%s %s %s\n", s.substr(0, 5).c_str(), s.substr(6, 7).c_str(), s.substr(14, 5).c_str());
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <map>
#include <cmath>
#include <vector>

using namespace std;
typedef long long ll;
const ll mod = 998244353;

ll pow_mod(ll e, ll p){
  if (p == 0) return 1;
  ll ret = e;
  for (ll i=0; i<p - 1; i++){
    ret = (ret * e) % mod;
  }
  return ret;
}

int main(){
  int N, tmp;
  cin >> N;
  vector<int> D;
  unordered_set<int> appear;
  map<int, int> nums;
  bool flag_tmp = true;
  bool can = true;
  for (int i=0; i<N; i++){
    cin >> tmp;
    D.push_back(tmp);
    appear.insert(tmp);
    nums[tmp]++;
    if (i == 0 && tmp != 0){
      can = false;
    }
  }
  for (int i=0; i<N; i++){
    if (!flag_tmp && (appear.find(i) != appear.end())){
      can = false;
      break;
    }
    flag_tmp = (appear.find(i) != appear.end());
  }
  
  if (!can){
    cout << 0 << endl;
  }
  else{
    ll ans = 1;
    for (int i=0; i<N; i++){
      	if (i == 0 && nums[i] > 1){
          ans = 0;
          break;
        }
        if (i > 0){
          ans = (ans * (ll)pow_mod(nums[i - 1], nums[i])) % mod;
        }
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 9500
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

string s;

int main() {
    cin >> s;

    if (s == "AAA" || s == "BBB") cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 256
"""
[X-Li,X+Li)
"""
N = int(input())
rls = []
for i in range(N):
    x,l = map(int, input().split())
    rls.append((x+l,x-l))
rls.sort()
cnt = 0
r_now = -10**10
# print(rls)
for r,l in rls:
    if l >= r_now:
        cnt += 1
        r_now = r
print(cnt)

Measured memory_bytes: 16988
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back

typedef long long LL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef vector<LL> VL;

int main() {
	int a, b, k;
	cin >> a >> b >> k;
	int cnt = 0, ans;
	for (int i = max(a,b); i>=1; i--) {
		if (a%i == 0&&b%i==0) {
			cnt++;
			//cout << i << " " << cnt << endl;
		}
		if (cnt == k) { ans = i; break; }
	}
	cout << ans << endl;
}

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

#ifdef _DEBUG
#define debug(x) cout<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif

using namespace std;

int main() {
    int N;
    cin >> N;
    bool approved = true;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        if (a % 2 == 0 && a % 3 != 0 && a % 5 != 0) approved = false;
    }
    cout << (approved ? "APPROVED" : "DENIED") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define SORT(a) stable_sort(ALL(a))
#define RSORT(a) stable_sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNIQUE(a) a.erase(unique(ALL(a)), end(a))
#define lambda(i) [=](auto i)
#define compare(i, j) [=](auto i, auto j)
#define min_of(a) *min_element(ALL(a))
#define max_of(a) *max_element(ALL(a))
#define sum(a) accumulate(ALL(a), 0)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define SZ(a) (int)(a).size()
#define REP(i, n) for (decltype(+n) i = 0; i < (n); i++)
#define RREP(i, n) for (auto i = n - 1; i != static_cast<decltype(i)>(-1); i--)
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define RFOR(i, a, b) for (auto i = b - 1; i != a; i--)
#define EACH(i, a) for (auto&& i: (a))
using namespace std;

const int INF = 1e18;
const int MOD = 1e9 + 7;
int mod_add(int A, int B) { return (A + B) % MOD; }
int mod_sub(int A, int B) { return (A + MOD - B) % MOD; }
int mod_mul(int A, int B) { return ((A % MOD) * (B % MOD)) % MOD; }
int mod_bipow(int X, int Y) {
    if (Y == 0) return 1;
    else if (Y == 1) return X % MOD;
    else if (Y % 2 == 0) {
        int Z = mod_bipow(X, (int)(Y / 2));
        return mod_mul(Z, Z);
    } else {
        int Z = mod_bipow(X, (int)(Y / 2));
        return mod_mul(mod_mul(Z, Z), X);
    }
}
int mod_inv(int X) { return mod_bipow(X, MOD - 2); }
int mod_div(int A, int B) { return mod_mul(A, mod_inv(B)); }

vi fact;

struct vertex {
  vector<int> adj = vi(0);
  int dp = 1;
  int p_dp = 1;
  int p_s = 1;
  int s = 1;
  void merge(vertex vt) {
    p_dp = mod_mul(p_dp, vt.dp);
    p_s = mod_mul(p_s, fact[vt.s]);
    s += vt.s;
    update_dp();
  };
  void perge(vertex vt) {
    p_dp = mod_div(p_dp, vt.dp);
    p_s = mod_div(p_s, fact[vt.s]);
    s -= vt.s;
    update_dp();
  };
  void update_dp() {
    dp = mod_div(mod_mul(p_dp, fact[s - 1]), p_s);
  }
};

int n;
vector<vertex> v;

void dfs(int x, int p) {
  EACH(i, v[x].adj) {
    if (i == p) continue;
    dfs(i, x);
    v[x].merge(v[i]);
  }
}

void r_dfs(int x, int p) {
  EACH(i, v[x].adj) {
    if (i == p) continue;
    int p_dp_x = mod_div(v[x].p_dp, v[i].dp);
    int p_s_x = mod_div(v[x].p_s, fact[v[i].s]);
    int s_x = v[x].s - v[i].s;
    int dp_x = mod_div(mod_mul(p_dp_x, fact[s_x - 1]), p_s_x);
    v[i].p_dp = mod_mul(v[i].p_dp, dp_x);
    v[i].p_s = mod_mul(v[i].p_s, fact[s_x]);
    v[i].s += s_x;
    v[i].update_dp();
    r_dfs(i, x);
  }
}

void solve() {
  cin >> n;
  fact = vi(n, 1);
  v = vector<vertex>(n);
  FOR(i, 1, n) {
    int a, b;
    cin >> a >> b;
    a--;b--;
    v[a].adj.pb(b);
    v[b].adj.pb(a);
    fact[i] = mod_mul(fact[i - 1], i);
  }
  dfs(0, -1);
  r_dfs(0, -1);
  EACH(i, v) {
    cout << i.dp << endl;
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << fixed << setprecision(15);
  solve();
}


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

int main(){
	int N;
	scanf("%d",&N);
	int a;
	int b;
	int c;
	a = N%10;
	b = N/10%10;
	c = N/100;
	if(a==7||b==7||c==7){
		printf("Yes");
	}else{
		printf("No");
	}
return 0;
}

Measured memory_bytes: 1704
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>
#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 1LL << 61;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222


vpll edge[3333];
ll dp[3333];



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



  ll p;
  cin >> n >> m >> p;
  rep(i, m) {
    ll a, b, c;
    cin >> a >> b >> c;
    edge[a].pb(pll(b, c - p));
  }
  bool b = false;
  rep(i, 3333) dp[i] = -inf;
  dp[1] = 0;
  rep(i, 11110) {
    FOR(node, 1, n + 1) {
      if (dp[node] == -inf) continue;
      rep(j, edge[node].size()) {
        ll to = edge[node][j].first, cost = edge[node][j].second;
        if (dp[to] < dp[node] + cost) {
          dp[to] = dp[node] + cost;
          if (to == n && i > m) b = true;
        }
      }
    }
  }
  if (b) cout << "-1" << endl;
  else cout << max(0LL, dp[n]) << endl;

  return 0;
}


Measured memory_bytes: 640
#include<iostream>
#define int long long
using namespace std;
int n,a[200001],b[200001],s[200001],q[200001];
char t[5];
inline int sum(int l,int r){return s[r]-s[l-1];}
signed main()
{
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(i>1)cin>>t,t[0]=='-'?b[i]=1:0;
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		q[i]=q[i-1]+(b[i]?-a[i]:a[i]);
		cnt+=b[i];
	}
	if(cnt<2){cout<<q[n]<<endl;return 0;}
	int ans=-(1ll<<40);
	for(int i=n,j=n+1;i;i--)
		if(b[i])
		{
			if(j>n){j=i;continue;}
			ans=max(ans,q[i-1]-sum(i,j-1)+sum(j,n));
			j=i;
		}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 5632
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const ll linf = 1LL << 62;
const int inf = 99999999;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };
const ll atcoder = 1e9 + 7;

#define Endl endl
#define mp make_pair
#define all(v) v.begin(),v.end()
#define pb push_back
#define pr(x) cout << x << endl
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define rep(i,n) for(int i= 0;i<n;i++)
#define FOR(i,a,b) for(int i = a;i<b;i++)

template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T &val) {
	std::fill((T*)array, (T*)(array + N), val);
}

ll gcd(ll a, ll b) {//最大公約数
	if (a < b)swap(a, b);
	if (a%b == 0)return b;
	else gcd(b, a%b);
}

ll lcm(ll a, ll b) {//最小公倍数
	if (a < b)swap(a, b);
	return (a / gcd(a, b))*b;
}

int main() {

	ll n, k;
	cin >> n >> k;

	ll ans = 0;
	if (k == 0)ans = pow(n,2);
	else FOR(b, k, n + 1) ans += n / b * (b - k) + max(0LL, n%b - k + 1);
	pr(ans);
	

	//system("pause");
	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<queue>
#include<utility>
#include<cmath>
#include<sstream>
#include<istream>

using namespace std;


int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  int C[N+1] = {0};

  for(int i=0; i<N; i++){
    cin >> A[i];
    C[A[i]] += 1;
  }

  long long int gans = 0;
  for(int i=1; i<N+1; i++){
    long long int T = C[i];
    gans += T*(T-1)/2;
  }

  for(int i=0; i<N; i++){
    long long int ans = gans - (C[A[i]]-1);

    cout << ans << endl;
  }

  return 0;
}


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

int main()
{
    string S, T;
    cin >> S >> T;
    bool ans = 0;
    if (S.size() + 1 == T.size())
    {
        for (int i = 0; i < S.size(); i++)
        {
            if (S.at(i) == T.at(i))
            {
                ans = 1;
            }
            else
            {
                ans = 0;
                break;
            }
        }
    }

    if (ans)
    {
        cout << "Yes" << endl;
    }
    else
        cout << "No" << endl;
}


Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 
int main() {
  ll N;
  cin>>N;
  vector<ll> A(N);
  for(ll i=0;i<N;i++) {
cin>>A[i];
  }
  sort(all(A));
  reverse(all(A));
  ll ans=0;
  for(ll i=0;i<N-1;i+=2) {
    ans+=A[i]-A[i+1];
  }
  
  if(N%2!=0) {
ans+=A.back();
  }
  
  cout<<ans<<endl;
}


Measured memory_bytes: 3604
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

using ll = long long;
using P = pair<ll,ll>;

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
const int mod = 1000000007;
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")


P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}



int main(){
  long long a,b,k;cin>>a>>b>>k;
  if(a >= k){
    cout << a-k << " " << b << endl;
  }else{
    cout << 0 << " " << max(0LL,b-k+a) << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n;cin>>n;
    vector<ll> a(n),b(n);
    for(ll i=0;i<n;i++){
        cin>>a[i]>>b[i];
    }

    ll ans=0;
    for(ll i=n-1;i>=0;i--){
        ans+=(((a[i]+ans+b[i]-1)/b[i])*b[i]-(a[i]+ans));
    }

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

Measured memory_bytes: 1792
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n)  for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//输入输出
#define PII pair<int,int>
#define PB push_back
#define ENDL '\n'
#define x first
#define y second
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO

#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint>
inline void IN(INint &x)
{
	x = 0; int f = 1; char c; cin.get(c);
	while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
	while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
	x *= f;
}
template<typename INint>
inline void OUT(INint x)
{
	if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(2e5+10);
char a[maxn];
int BlaL[maxn], WhiR[maxn];

////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
	//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
	int T(1), times(0);
#ifdef CPP_IO// CPP_IO
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//cin >> T;
#else
	//IN(T);
#endif 
	/////////////////////////////////////////////////////////////////////////////////////////////////
	while (++times, T--)
	{
		int n; cin >> n;
		RE2(i, n)cin >> a[i], BlaL[i] = BlaL[i - 1] + (a[i] == '#');
		F2(i, n, 1)WhiR[i] = WhiR[i + 1] + (a[i] == '.');
		int ans = inf;
		F(i, 0, n)
		{
			ans = min(ans, BlaL[i] + WhiR[i + 1]);
		}
		cout << ans << endl;
	}
	///////////////////////////////////////////////////////////////////////////////////////////////////
	return 0;
}

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

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> ls(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> ls[i];
        sum += ls[i];
    }
    sort(ls.begin(), ls.end());
    int r = sum - ls.back();
    if (ls.back() < r) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
///////////////////// author : TrEbLeCleF /////////////////////
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define For(i, a) for (int i=0; i<(a); i++)
#define FORR(i,a,b) for (int i = (b)-1; i >= a; i--)
#define Forr(i,a) for (int i = (a)-1; i >= 0; i--)
/////////////////////////// ..... ///////////////////////////
#define deb(...) cerr << "[" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__) 
void DBG() { cerr << "]\n";}
template<typename T, typename ...Args> void DBG(T first, Args... args){
cerr << first; if(sizeof...(args))cerr<<", "; DBG(args...); }
/////////////////////////// ..... ///////////////////////////
#define int ll
#define pb(x) push_back(x)
#define print(v,s,e) for(int i = s; i < e; i++)cout << v[i]<<" ";cout<<"\n";
#define INF 1e17
#define PI 3.14159265358979323846 
int del_x[4] = {-1, 1, 0, 0};
int del_y[4] = {0, 0, 1, -1};
int XX[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int YY[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
/////////////////////////// GLOBAL ///////////////////////////

/////////////////////////// GLOBAL ///////////////////////////
void solve(){
	string s, t; cin >> s >> t;
	int n = s.length(), m = t.length();
	int dp[n+1][m+1];
	memset(dp,0,sizeof(dp));
	FOR(i,1,n+1){
		FOR(j,1,m+1){
			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]);
			}
		}
	}
	string ans;
	int i = n, j = m;
	while(i&&j){
		if(s[i-1]==t[j-1]){
			ans+= s[i-1];
			--i;
			--j;
		}
		else{
			if(dp[i-1][j] > dp[i][j-1]){
				--i;
			}
			else{
				--j;
			}
		}
	}
	reverse(ans.begin(),ans.end());
	cout << ans <<"\n";
}
int32_t main(){ 
	#ifndef ONLINE_JUDGE
		clock_t tStart = clock();
		freopen("TC", "r", stdin);
		//freopen("output.txt","w",stdout);
	#endif 
    ios_base:: sync_with_stdio(false); 
   	cin.tie(0); 
	int t=1;
	//cin >> t;
	for(int tt=1;tt<=t;tt++){
		//cout << "Case #"<<tt<<": ";
		solve();
	}
	#ifndef ONLINE_JUDGE
    	cerr << "\nRun Time -> "<<(double)(clock()-tStart)/CLOCKS_PER_SEC <<" sec\n";
    #endif
}

Measured memory_bytes: 74016
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def solve():
    N = int(input())
    C = input()

    num_r = C.count("R")
    num_w = C.count("W")
    ans = min(num_r, num_w)

    left_r = 0
    left_w = 0
    for i in range(N):
        left_r += C[i] == 'R'
        left_w += C[i] == 'W'

        right_r = num_r - left_r
        right_w = num_w - left_w
        ans = min(ans, min(left_w, right_r) + abs(left_w - right_r))

    print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()


Measured memory_bytes: 10192
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
int main() {
    int x;
    cin >> x;

    if(x < 1200){
        cout << "ABC" << endl;
    } else {
        cout << "ARC" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define N 2*10e5
#define precise cout<<fixed<<setprecision(10)
#pragma GCC optimize("O0")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")
#define rep(i,a,b) for(int i=a;i<b;i++)
#define min3(a,b,c) min(a,min(b,c))
#define nl cout<<"\n";
#define all(v) v.begin(),v.end()
#define F first
#define S second
typedef unsigned long long ll;
typedef vector<long long> vl;
typedef vector<pair<long,long>> vp;
void get(ll arr[],ll n){for(ll i=0;i<n;i++) cin>>arr[i];}
ll gcd(ll a,ll b);
ll binpow(ll a,ll b);
void solve()
{
	ll n;
	cin>>n;
	ll arr[n];
	get(arr,n);
	ll b[n];
	ll num=0;
	rep(i,0,n) num=num^arr[i];
	ll prev=0;
	rep(i,0,n)
	{
		b[i]=num^arr[i];
		//prev=prev^num;
	}	
	rep(i,0,n) cout<<b[i]<<" ";
}
int main()
{
 	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t;
	t=1;
	//cin>>t;
	while(t--)
	{
	 	solve();
	}
	//cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
ll binpow(ll a, ll b) {
   ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ll gcd(ll a,ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}


Measured memory_bytes: 6624
// È¥°É£¡Æ¤¿¨Çð! °ÑAC´ø»ØÀ´£¡
//      ¤Ø¡¡¡¡¡¡¡¡¡¡£¯|
// ¡¡¡¡/£Ü7¡¡¡¡¡¡ ¡Ï£ß/
// ¡¡ /¡¡©¦¡¡¡¡ £¯¡¡£¯								AC		AC		AC		AC
//    ©¦¡¡Z £ß,£¼¡¡£¯¡¡¡¡ /`©c						AC		AC		AC		AC
//    ©¦¡¡¡¡¡¡¡¡¡¡©c¡¡¡¡ /¡¡¡¡¡µ					AC		AC		AC		AC
// ¡¡Y¡¡¡¡¡¡¡¡¡¡`¡¡ /¡¡¡¡/  /						AC		AC		AC		AC
// ¡¡Øé¡ñ¡¡.¡¡¡ñ¡¡¡¡¡´¡¡/¡¡/						AC		AC		AC		AC
// ¡¡()¡¡ ¤Ø¡¡¡¡¡¡¡¡|¡¡£Ü¡´							AC		AC		AC		AC
// ¡¡¡¡>- ._¡¡ ¥£¡¡ ©¦ £¯£¯							AC		AC		AC		AC
// ¡¡ / ¤Ø¡¡¡¡ /¡¡/£¼| £Ü£Ü							AC		AC		AC		AC
// ¡¡ ©c_/¡¡¡¡(_£¯¡¡ ©¦£¯£¯							AC		AC		AC		AC
// ¡¡¡¡ 7¡¡¡¡¡¡¡¡¡¡¡¡¡¡|£¯							AC		AC		AC		AC
// ¡¡¡¡ £¾¨Dr£þ£þ`-¨D£ß/							AC		AC		AC		AC
//**************************************Accepted*****************************************//

#include<bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define Unique(x) x.erase(unique(all(x)),x.end());

#define CIN_FILE "input.txt"
#define COUT_FILE "output.txt"

#define Pig (OO)

using namespace std;

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

const int Days[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};

inline int read()
{
	#define gc getchar
	int ans=0;
	bool f=1;
	char ch=gc();
	
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	
	while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc();
	
	return f?ans:-ans;
	
	#undef gc
}

typedef long long ll;

ll n,w;
ll dp[100010];

int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	
	cin>>n>>w;
	for(int i=0;i<n;i++)
	{
		ll wei,val;
		cin>>wei>>val;
		
		for(int j=w;j>=wei;j--)dp[j]=max(dp[j],dp[j-wei]+val);
	}
	
	cout<<*max_element(dp,dp+w+1);
	
	//printf("Time used = %.12f",(double)(clock())/CLOCKS_PER_SEC);
	return 0;
}

/*  GOD BLESS  */


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> f(int x){
	vector<int> bb;
	while(x){
		bb.push_back(x%10);
		x/=10;
	}
	reverse(bb.begin(),bb.end());
	return bb;
}
int main(){
	int t; t=1;
	while(t--){
		ll n,k; cin>>n>>k;
		ll a[n];
		for(int i=0;i<n;++i)cin>>a[i];
		long double b[n];
	    for(int i=0;i<n;++i)b[i]=log(a[i]);
	    long double sum=0.0;
	    for(int i=0;i<n;++i)sum+=b[i];
	    for(int i=k;i<n;++i){
	    	long double zz=sum-b[i-k]+b[i];
	    	if(zz>sum)cout<<"Yes\n";
	    	else cout<<"No\n";
	    	sum=zz;
	    }
	}
}

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

#define ll long long
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x << endl
#define N 200005

#define newLine	printf("\n");

#define sll(X) scanf("%lld", &X);
#define pll(X) printf("%lld", X);
#define printAll(X, n)	for(int i=0;i<n;i++)	printf("%lld ", X[i]); newLine;
#define scanAll(X, n)	for(int i=0;i<n;i++)	scanf("%lld", &X[i]);

#define MAXX 10000007
bool p[MAXX];
 vector<ll> primes;
void calcSieve() {
	p[0] = 1; p[1] = 1;
	for(int i=2;i<MAXX;i++) {
		if(!p[i]) {
			for(int j=2;j*i<MAXX;j++) {
				p[i*j] = 1;
			}
			primes.push_back(i);
		}
	}
}

ll n;
map<ll, ll> mp;
void poo() {
	if(p[n] == 0) {
		// ps.push_back(1);
		mp[n] ++;
		return ;
	}
	for(int i=0; primes[i] * primes[i] <= n;i++) {
		ll thisC = 0;
		if(p[n] == 0) {
			mp[n] ++;
			return ;
		}
		while(n % primes[i] == 0) {
			n /= primes[i];
			thisC++;
		}
		mp[primes[i]] += thisC;
		/*if(thisC != 0)
			ps.push_back(thisC);*/
	}

	/*if(n != 1 && p[n] == 0) {
		ps.push_back(1);
	}*/
	if(n != 1 && p[n] == 0) {
		mp[n] ++;
	}

	return;
}

int main() {
	calcSieve();
	ll x;
	sll(x);
	for(int i=2;i<=x;i++) {
		n = i;
		poo();
	}
	ll ans = 1;
	for(int i=0;primes[i]<=x;i++) {
		// cout<<primes[i]<<" "<<mp[primes[i]]<<"\n";
		ans = (ans * (1 + mp[primes[i]])) % mod;
	}
	pll(ans);
	newLine
	return 0;
}

Measured memory_bytes: 18412
#include <stdio.h>

int N = 6;
double p[6], q[6];

double max(double a, double b){
	return a >= b ? a : b;
}

double Pr(double x){
	int i;
	double ans = 0;
	for(i = 0; i < N; i++){
		ans += max(p[i] * x, q[i] * (1 - x));
//		printf("ans[%d] = %lf\n", i, ans);
	}
	return ans;
}

int main(){
	int i;
	for(i = 0; i < N; i++){
		scanf("%lf", &p[i]);
		p[i] /= 100;
	}
	for(i = 0; i < N; i++){
		scanf("%lf", &q[i]);
		q[i] /= 100;
	}
/*	for(i = 0; i < N; i++){
		printf("%lf\n", p[i]);
	}
	for(i = 0; i < N; i++){
		printf("%lf\n", q[i]);
	}
*/	double l = 0, h1, h2, r = 1;
//	printf("Pr(%lf) = %lf\n", l, Pr(l));
//	printf("Pr(%lf) = %lf\n", r, Pr(r));
	for(i = 0; i < 100; i++){
		h1 = (l + l + r) / 3;
		h2 = (l + r + r) / 3;
		if(Pr(h1) < Pr(h2)){
			r = h2;
		}
		else{
			l = h1;
		}
	}
//	printf("%.12lf\n", (l + r) / 2);
	printf("%.12lf\n", Pr((l + r) / 2));
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 10000000000000000
#define endl '\n'
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; }
using namespace std;

signed main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    int m=n%100; n/=100;
    bool b=false,c=false;
    if(n>=1 and n<=12)b=true;
    if(m>=1 and m<=12)c=true;
    if(b and c)cout<<"AMBIGUOUS"<<endl;
    else if(b)cout<<"MMYY"<<endl;
    else if(c)cout<<"YYMM"<<endl;
    else cout<<"NA"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

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

	int N, W;
	cin >> N >> W;
	vector<pair<int, int> > v[4];

	int w0 = 0;
	rep(i, 0, 4) v[i].push_back(make_pair(0, 0));
	rep(i, 0, N) {
		int tmp_w, tmp_v;
		cin >> tmp_w >> tmp_v;

		if(i == 0) {
			v[i].push_back(make_pair(tmp_v, tmp_w));
			w0 = tmp_w;
		} else {
			v[tmp_w - w0].push_back(make_pair(tmp_v, tmp_w));
		}
	}
	
	rep(i, 0, 4) {
		vsort(v[i]);
		reverse(v[i].begin(), v[i].end());
	}

	ll rsl = -1;

	rep(i, 0, v[0].size() + 1) rep(j, 0, v[1].size() + 1) {
		if(i + j > N) continue;
		rep(k, 0, v[2].size() + 1) {
			if(i + j + k > N) continue;
			rep(l, 0, v[3].size() + 1) {
				if(i + j + k + l > N) continue;
				ll tmp_v = 0, tmp_w = 0;

				rep(a, 0, i) {
					tmp_v += v[0][a].first;
					tmp_w += v[0][a].second;
				}

				rep(b, 0, j) {
					tmp_v += v[1][b].first;
					tmp_w += v[1][b].second;
				}

				rep(c, 0, k) {
					tmp_v += v[2][c].first;
					tmp_w += v[2][c].second;
				}

				rep(d, 0, l) {
					tmp_v += v[3][d].first;
					tmp_w += v[3][d].second;
				}

				if(tmp_w <= W) rsl = max(rsl, tmp_v);
			}
		}
	}

	cout << rsl << endl;

}


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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int l, r, d;
	cin >> l >> r >> d;
	cout << r/d - (l - 1)/d << endl;
	return 0;
}

Measured memory_bytes: 3580
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll (i) = 0; (i) < (n); (i)++)
#define rep1(i, n) for(ll (i) = 1; (i) <= (n); (i)++)
#define rrep(i, n) for(ll (i) = (n) - 1; (i) >= 0; (i)--)
#define rrep1(i, n) for(ll (i) = (n); (i) >= 1; (i)--)
const ll INF = 1145141919;
const ll MOD = 1000000007;
template<class T> void chmax(T &a, const T &b){if(a < b){a = b;}}
template<class T> void chmin(T &a, const T &b){if(a > b){a = b;}}

int main(){

    ll flg[4] = {};
    rep1(i, 2){
        ll x;
        cin >> x;
        flg[x] = 1;
    }
    rep1(i, 3){
        if(flg[i] == 0)cout << i << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
<?php
    $n=trim(fgets(STDIN));
    $a = explode(" ", trim(fgets(STDIN)));
    $s = implode(" ", $a);
    echo $s . "\n";

    for ($i = 1; $i < $n; $i++) {
        $j = $i - 1;
        $v = $a[$i];

        while ($j >= 0 && $v < $a[$j]) {
            $a[$j + 1] = $a[$j];
            $j--;
        }   

        $a[$j + 1] = $v; 
        $s = implode(" ", $a);
        echo $s . "\n";
    }   
?>


Measured memory_bytes: 9268
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;

#define FOR(i,a,b) for(long long int i=(a);i<(b);i++)
#define REP(i,n) for(long long int i=0;i<(n);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI 3.14159265358479

typedef long long int ll;
typedef vector<long long int> vi;

int main(){
	string str;
	cin >> str;
	reverse(ALL(str));
	cout << str << "\n";
}

Measured memory_bytes: 1160
n = int(input())
a = list(map(int, input().split()))
sum_a = 0
ans1 = 0
ans2 = 0

for i in range(n):
    sum_a += a[i]
    if i % 2 == 0:
        if sum_a <= 0:
            ans1 += abs(sum_a) + 1
            sum_a = 1
    else:
        if sum_a >= 0:
            ans1 += abs(sum_a) + 1
            sum_a = -1

sum_a = 0

for i in range(n):
    sum_a += a[i]
    if i % 2 == 0:
        if sum_a >= 0:
            ans2 += abs(sum_a) + 1
            sum_a = -1
    else:
        if sum_a <= 0:
            ans2 += abs(sum_a) + 1
            sum_a = 1

print(min(ans1,ans2))


Measured memory_bytes: 14468
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }
int gcd(int a, int b)
{
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }
    
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b)
{
    return a * b / gcd(a, b);
}
int main(int argc, char* argv[]) {
    int n;
    cin >> n;
    vint a(n);
    ll ans =0;
    rep(i,n) {
        cin >> a[i];
        ans+=a[i]-1;
        }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256