akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			var cin = new Scanner2();
			int x = cin.Int();
			int ans = 0;
			ans += (x / 500) * 1000;
			ans += ((x % 500) / 5) * 5;

			Console.WriteLine(ans);
		}
	}

	public static class Helper
	{
		public static void UpdateMin32<T>(T array, int index, int value) where T : IList<int>
			=> array[index] = Math.Min(array[index], value);
		public static void UpdateMax32<T>(T array, int index, int value) where T : IList<int>
			=> array[index] = Math.Max(array[index], value);
		public static void UpdateMin64<T>(T array, int index, long value) where T : IList<long>
			=> array[index] = Math.Min(array[index], value);
		public static void UpdateMax64<T>(T array, int index, long value) where T : IList<long>
			=> array[index] = Math.Max(array[index], value);

		public static T[] Array<T>(int n, Func<int, T> init)
			=> Enumerable.Range(0, n).Select(x => init(x)).ToArray();
		public static List<T> List<T>(int n, Func<int, T> init)
			=> Enumerable.Range(0, n).Select(x => init(x)).ToList();
	}

	public class Scanner2
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private readonly string filePath_;
		private readonly Func<string> reader_;
		private string[] buf_;
		private int index_;

		public Scanner2(string file = "")
		{
			if (string.IsNullOrWhiteSpace(file)) {
				reader_ = Console.ReadLine;
			} else {
				filePath_ = file;
				var fs = new StreamReader(file);
				reader_ = fs.ReadLine;
			}
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = reader_();
			while (st == "") {
				st = reader_();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int() => int.Parse(Next());
		public long Long() => long.Parse(Next());
		public double Double() => double.Parse(Next());

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}

		public void Save(string text)
		{
			if (string.IsNullOrWhiteSpace(filePath_)) {
				return;
			}

			File.WriteAllText(filePath_ + "_output.txt", text);
		}
	}
}

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

int main()
{
    int n,k,data;
    cin>>n>>k;
    int i;
    int count = 0;
    for(i = 0; i < n; i++)
    {
        cin>>data;
        if(data >= k)
            count++;
    }
    cout<<count;
}

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

int main() {
    int n, k;
    cin >> n >> k;
    double pro = 0;
    for(int i=0; i<n; i++){
        if(i+1 < k){
            for(int j=0; j<1000; j++){
                if(pow(2,(j+1))*(i+1) >= k){
                pro += pow(0.5,(j+1));
                break;
                }
            }
        }
        else{
            pro += 1.0;
        }
    }
    cout << setprecision(10) << pro/n << endl;
}

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

using namespace std;

int main(int argc, char *argv[])
{
	string s;
	cin >> s;
	int n = s.size();
	vector<int> a;
	for (int i = 0; i < n; i++)
		if (s[i] == 'A') {
			a.push_back(1);
		} else if ((i + 1) < n && s[i] == 'B' && s[i + 1] == 'C') {
			a.push_back(2);
			i++;
		} else {
			a.push_back(0);
		}

	// for (int i = 0; i < a.size(); i++) cout << a[i] << endl;
	n = a.size();
	long long ans = 0;
	for (int i = 0, j = 0; i < n; i = j) {
		while (!a[i] && i < n) i++;
		if (i >= n) break;
		long long c = 0;
		for (j = i; j < n && a[j] != 0; j++) {}
		for (int k = j - 1, c = 0; k >= i; k--)
			if (a[k] == 2) c++;
			else if (a[k] == 1) ans += c;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1532
#include<iostream>
using namespace std;
int s[1<<17];
main()
{
	int n,m,a,b;cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		if(a>b)a^=b^=a^=b;
		s[a]++,s[b]--;
	}
	for(int i=1;i<=n+1;i++)s[i]+=s[i-1];
	int f=0;
	for(int i=1;i<n;i++)f|=s[i]%2;
	cout<<(f?"NO":"YES")<<endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
int main(void)         
{
    int n;
    set<int>s;
    while(cin>>n)
    {
        s.clear();
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            s.insert(x);
        }
        if(s.size()%2==0)
        cout<<s.size()-1<<endl;
        else
        cout<<s.size()<<endl;
     }
     return 0;
}

Measured memory_bytes: 4864
fun main(args: Array<String>) {
    val n = readInputLine().toInt()
    val hArr = readInputLine().split(" ").map{it.toInt()}.toIntArray()

    hArr[0]--

    for (i in 1 until n) {
        if (hArr[i] > hArr[i - 1]) {
            hArr[i]--
        }
        if (hArr[i] < hArr[i - 1]) {
            println("No")
            return
        }
    }
    
    println("Yes")
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 59688
//_nebula_
#include<bits/stdc++.h>
using namespace std;
#define int long  long
#define double long double
int t;
const int M=1e9+7;
int factt(int n)
{
    int ans=1;
    for(int i=1;i<=n;i++)
    {
        ans*=i;
        ans=ans%M;
    }
    return ans;
}
int max(int a,int b,int c)
{
    return max(a,max(b,c));
}
int min(int a,int b,int c)
{
    return min(a,min(b,c));
}
int fspow(int x,int y)
{
    int ans;
    if(y==0) return 1;
    ans=fspow(x, y/2);
    if(y%2==0) return (ans*ans);
    return x*ans*ans;
}
int gcd(int x,int y)
{
    if(x<y) swap(x,y);
    if(y==0) return x;
    return gcd(x%y,y);
}
int p2(int x)
{
    int ans=0;
    while(x>=1)
    {
        ans++;
        x/=2;
    }
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    t=1;
    // freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //cin>>t;
    // int tmp=t;
    while(t--)
    {
      string s;
      cin>>s;
      int ans=0;
      for(int i=0;i<s.size();i++) ans+=s[i]-'0';
      if(ans%9) cout<<"No\n";
      else cout<<"Yes\n";
    }
}


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

int digit(int a,int b){
  int res = 0;
  while(a){
  	a /= b;
  	++res;
  }
  return res;
}

int main(){
  int n,k;
  cin >> n >> k;
  cout << digit(n,k) << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    static HashMap<Integer, Integer> map;
    static void map_put(Integer x) {
        if (map.containsKey(x)) {
            map.put(x, map.get(x)+1);
        } else {
            map.put(x, 1);
        }
    }
    static void map_minus(Integer x) {
        map.put(x, map.get(x)-1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = Integer.parseInt(sc.next());
        int K = Integer.parseInt(sc.next());
        int[] A = new int[N];
        for (int i=0;i<N;i++) {
            A[i] = Integer.parseInt(sc.next())-1;
        }

        map = new HashMap<Integer, Integer>();
        long[] ruiseki = new long[N+1];
        for (int i=0;i<N;i++) {
            ruiseki[i+1] = ruiseki[i]+A[i];
        }
        for (int i=0;i<N+1;i++) {
            ruiseki[i] %= K;
        }

        int left = 0;
        int right = 0;
        long ans = 0L;
        while (right<Math.min(K, N+1)) {
            map_put((int)ruiseki[right]);
            right++;
        }
        while (left<N) {
            int aa = (int)ruiseki[left];
            ans += map.get(aa)-1;
            map_minus((int)ruiseki[left]);
            left++;
            if (right==N+1) continue;
            map_put((int)ruiseki[right]);
            right++;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 71188
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N,K = map(int,input().split())
h = list(map(int,input().split()))

INF = 10**20
dp = [INF]*(N+10)
dp[0] = 0
def distance(x,y):
    return abs(h[x]-h[y])

for i in range(1,N):
    for k in range(1,K+1):
        if i-k<0:break
        dp[i] = min(dp[i], dp[i-k] + distance(i-k,i))
print(dp[N-1])
    

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

int main(){
	int n,c,d;
	while(cin >> n && n){
		int a=0,b=0;
		for(int i=0;i<n;i++){
			cin >> c >> d;
			if(c>d){
				a+=c+d;
			}else if(c<d){
				b+=c+d;
			}else{
				a+=c;
				b+=d;
			}
		}
		cout << a << " " << b << endl;
	}
}

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

using namespace std;

#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n);i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(a);i>=(int)(b);--i)
#define ALL(a) (a).begin(),(a).end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;

const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;

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

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

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  REP(i, SZ(v)) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}

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

  ll n, k; cin >> n >> k;
  vi p(n);
  vll c(n);
  REP(i, n) {
    cin >> p[i];
    p[i]--;
  }
  REP(i, n) cin >> c[i];


  vector<pair<vi, ll>> v;
  vector<bool> sel(n, false);

  REP(i, n) {
    if(sel[i]) continue;
    ll su = 0;
    int pos = i;
    vector<int> tmpv;
    while(!sel[pos]) {
      sel[pos] = true;
      su += c[pos];
      tmpv.push_back(pos);
      pos = p[pos];
    }
    v.push_back({tmpv, su});
  }


  ll ma = -LINF;
  for(auto &e: v) {
    auto tmpv = e.first;
    ll su = e.second;

    vll tmp(2*SZ(tmpv));
    REP(i, SZ(tmpv)) {
      tmp[i] = c[tmpv[i]];
      tmp[i+SZ(tmpv)] = c[tmpv[i]];
    }

    ll rem = k % SZ(tmpv);
    vi vrem(SZ(tmpv));
    if(su >= 0) {
      REP(i, rem) {
        vrem[i] = k / SZ(tmpv);
      }
      FOR(i, rem, SZ(tmpv)) {
        vrem[i] = k / SZ(tmpv) -1;
      }
    }

    ll nowma = (rem == 0 ? 0 : -LINF);
    REP(i, SZ(tmpv)) {
      ll nowsu = 0;
      REP(j, min(k, (ll)SZ(tmpv))) {
        nowsu += tmp[i+j];
        chmax(ma, nowsu + vrem[j] * su);
      }
    }

  }
  cout << ma << endl;

}








Measured memory_bytes: 3868
#include<stdio.h>

int main(){
  int i, n, A[10001], q, key, sum = 0;

  scanf("%d",&n);
  for(i = 0 ; i < n ; i++){
    scanf("%d",&A[i]);
  }

  scanf("%d",&q);
  for(i = 0 ; i < q ; i++){
    scanf("%d",&key);
    if(linearSearch(A, n, key)){
      sum++;
    }
  }
  printf("%d\n",sum);

  return 0;
}

int linearSearch(int A[], int n, int key){
  int i = 0;
  A[n] = key;
  while(A[i] != key){
    i++;
  }
  return i != n;
}


Measured memory_bytes: 2108
tree = []
while true do
    n = gets.to_i
    break if n == 0
    n.times do
        tree.push(gets.chomp)
    end
    afters = []
    tree.reverse.each do |e|
        dot_count = e.count(".")
        next if dot_count == 0
        afters = afters.select{|after| after < dot_count }
        afters.push(dot_count)
        afters.each do |after|
            e[after-1] = "|"
        end
        e[dot_count-1] = "+"
        e.gsub!(/\./, " ")
    end
    puts tree
    tree = []
end


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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  while(a>0&&c>0){
    c-=b;
    a-=d;
  }
  if(c<1){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++){ cin >> a[i];}
  int pre = -999;
  int y=0;
  for(int i=0;i<n;i++){
    if (pre <= a[i]-1) {
      pre = a[i]-1;
    } else if (pre <= a[i]) {
      pre = a[i];
    } else {
      y=1;
      break;  
    }
  }
  if(y==0){
  cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
struct fastio { fastio() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } _fastio_;
template<class T> bool chmin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool chmax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

int main() {
	int d, t, s;
	std::cin >> d >> t >> s;
	if (t * s >= d) std::cout << "Yes" << '\n';
	else std::cout << "No" << '\n';
	
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define ll long long

int take()
{
    int n;
    scanf("%d",&n);
    return n;

}

ll takes()
{
    ll n;
    scanf("%lld",&n);
    return n;

}
#define M 200005
#define Int take()
#define LL takes()

#define fr(n) for(int i=1;i<=n;i++)
#define rfr(n) for(int i=n;i>=1;i--)
int cas;
#define print printf("Case %d:",++cas)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define mk  make_pair
#define fill(x,v) memset(x,v,sizeof x)
using namespace std;


int main(){
    string s,t,till="";
    cin>>s>>t;

    vector<string>ans;

    for(int i=0; i<s.size(); i++){
        int len=0,ques=0;
        for(int k=0; k<s.size() && k<t.size(); k++){
            if(t[k]==s[i+k]) len++;
            else if(s[i+k]=='?') ques++;
            else break;
        }

        if(ques+len==t.size()){
            string nw=till+t;
            for(int k=i+ques+len;k<s.size();k++){
                if(s[k]=='?') nw+='a';
        else nw+=s[k];
            }
            ans.pb(nw);
        }

        if(s[i]=='?') till+='a';
        else till+=s[i];
    }

    if(ans.empty( )) printf("UNRESTORABLE\n");
    else{
        sort(ans.begin(),ans.end());
        cout<<ans[0]<<"\n";
    }

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stdio.h>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
#include <fstream>
#include <list>
#include <iomanip>
#include <cctype>

using namespace std;

#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979

void printVec(std::vector<int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

int vector_finder(std::vector<string> vec, string number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}

#include <sstream> 
std::vector<std::string> StringSplit(const std::string& str, char sep)
{
	std::vector<std::string> v;
	std::stringstream ss(str);
	std::string buffer;
	while (std::getline(ss, buffer, sep)) {
		v.push_back(buffer);
	}
	return v;
}

Int gcd(Int a, Int b) {
	return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
	return a * b / gcd(a, b);
}

bool comp(const string a, const string b) {
	return a.length() < b.length();
}

bool integer(double num) {
	return floor(num) == num;
}
#

int main() {
	int n, m,X, Y; cin >> n >> m >> X >> Y;
	vector<int> x(n), y(m);
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> y[i];
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	if (x[n - 1] > X && y[0] < Y) {
		if (y[0] - x[n - 1] > 0) cout << "No War";
		else cout << "War";
	}
	else cout << "War";

	cout << endl;
	return 0;
}

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

typedef long long ll;
typedef pair<ll, ll> P;

const int MAX = 1e5 + 10;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int N, M, A[MAX], B[MAX];

class work{
    public:
        int a, b;
};

bool cmp(work &a, work &b){ return a.a < b.a || (a.a == b.a && a.b > b.b); }

int main(){
    cin >> N >> M;
    rep(i, N) cin >> A[i] >> B[i];

    vector<work> v;
    rep(i, N){
        work w;
        w.a = A[i];
        w.b = B[i];
        v.push_back(w);
    }
    sort(v.begin(), v.end(), cmp);
    rep(i, N){
        A[i] = v[i].a;
        B[i] = v[i].b;
    }

    ll ans = 0;
    priority_queue<int> q;
    int j = 0;
    for(int i = M - 1; i >= 0; --i){
        int day = M - i;

        while(j < N && A[j] <= day){
            q.push(B[j]);
            j++;
        }
        
        if(q.size()){
            ans += q.top();
            q.pop();
        }
    }

    cout << ans << endl;
}

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

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

using namespace std;
typedef long long ll;

int main(){
    int n;
    cin>>n;
    vector<int> a(n),b(n),c(n);
    rep(i,n) cin>>a[i];
    rep(i,n) cin>>b[i];
    rep(i,n) cin>>c[i];
    sort(a.begin(),a.end());
    sort(c.begin(),c.end());

    ll ans =0;
    rep(j,n){
        ll numa = lower_bound(a.begin(),a.end(),b[j]) - a.begin();
        ll numc = c.end() - upper_bound(c.begin(),c.end(),b[j]);
        ans += numa * numc;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <stdio.h>
using namespace std;

struct Node {
	int left;
	int right;
	int parent;
	int sibling;
};

int max(int a, int b) {
	return a < b ? b : a;
}

/*int depthHeight(Node* arr, int id, int d) {
	arr[id].depth = d;
	if ((arr[id].left != -1) && (arr[id].right != -1)) {
		arr[id].degree = 2;
		return arr[id].height = max(depthHeight(arr, arr[id].left, d + 1), depthHeight(arr, arr[id].right, d + 1)) + 1;
	}
	else if (arr[id].left != -1) {
		arr[id].degree = 1;
		return arr[id].height = depthHeight(arr, arr[id].left, d + 1) + 1;
	}
	else if (arr[id].right != -1) {
		arr[id].degree = 1;
		return (arr[id].height = depthHeight(arr, arr[id].right, d + 1) + 1);
	}
	else
		return arr[id].degree = arr[id].height = 0;
}

void print(Node* arr, int id) {
	printf("node %d: parent = %d, sibling = %d, degree = %d, depth = %d, height = %d, "
		, id, arr[id].parent, arr[id].sibling, arr[id].degree, arr[id].depth, arr[id].height);
	if (arr[id].parent == -1)
		cout << "root\n";
	else if (arr[id].height == 0)
		cout << "leaf\n";
	else
		cout << "internal node\n";
} */

/*void preorder(Node* arr, int id ,int len) {
	static int cnt = len;
	if (cnt != 1) {
		cout << id << " ";
		if(arr[id].left!=-1)
			preorder(arr, arr[id].left, cnt--);
		if(arr[id].right!=-1)
			preorder(arr, arr[id].right, cnt--);
	}
	else 
		cout << id << endl;
}*/

void preorder(Node* arr, int id) {
	cout << " " <<id;
	if (arr[id].left != -1)
		preorder(arr, arr[id].left);
	if (arr[id].right != -1)
		preorder(arr, arr[id].right);
}

void inorder(Node* arr, int id) {
	if (arr[id].left != -1)
		inorder(arr, arr[id].left);
	cout << " " << id ;
	if (arr[id].right != -1)
		inorder(arr, arr[id].right);
}

void postorder(Node* arr, int id) {
	if (arr[id].left != -1)
		postorder(arr, arr[id].left);
	if (arr[id].right != -1)
		postorder(arr, arr[id].right);
		cout << " " << id ;
}

int main() {
	int len;
	cin >> len;
	Node* arr = new Node[len];

	//set all the fields to -1 (in order to represent the root and the leaf of the tree)
	for (int i = 0; i < len; i++)
		arr[i].parent = arr[i].left = arr[i].right = arr[i].sibling = -1;

	int id;
	for (int i = 0; i < len; i++) {
		cin >> id;
		cin >> arr[id].left >> arr[id].right;
		arr[arr[id].left].parent = arr[arr[id].right].parent = id;
		arr[arr[id].left].sibling = arr[id].right;
		arr[arr[id].right].sibling = arr[id].left;
	}

	int r;
	for (r = 0; arr[r].parent != -1; r = arr[r].parent);
	cout << "Preorder\n";
	preorder(arr, r);
	cout << endl;
	cout << "Inorder\n";
	inorder(arr, r);
	cout << endl;
	cout << "Postorder\n";
	postorder(arr, r);
	cout << endl;
	return 0;
}


Measured memory_bytes: 3108
import bisect,collections,copy,heapq,itertools,math,string
import sys
def S(): return sys.stdin.readline().rstrip()
def M(): return map(int,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
a, b = M()
a += b
if a > 9:
    print('error')
else:
    print(a)

Measured memory_bytes: 74540
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1e9+7;
void ts()
{
    cout<<"***Test Point****"<<endl;
}
void write(ll ans)
{
    if(ans>9) write(ans/10);
    putchar(ans%10+'0');
}
inline int read()
{
    char c=getchar();int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x;
}
int n,v=0,x,a[205];
ll ans=0,dp[2][100005];
int main()
{
    n=read();x=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    dp[v][x]=1;
    for(int i=1;i<=n;i++,v^=1)
        for(int j=0;j<=x;j++)
        {
            dp[v^1][j%a[i]]=(dp[v^1][j%a[i]]+dp[v][j])%mod;
            dp[v^1][j]=(dp[v^1][j]+dp[v][j]*(n-i))%mod;
            dp[v][j]=0;
        }
    for(int i=0;i<=x;i++)
        ans=(ans+dp[v][i]*i)%mod;
    write(ans);
}


Measured memory_bytes: 1792
#include <iostream>
#include <cmath>
#include <climits>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <numeric>
using namespace std;
// scanf
#pragma warning(disable: 4996)
// v:vector  type:型  order:greater or less
#define _sort(v,type,order) do { sort(v.begin(),v.end(),order<type>()); } while(0)
// v:vector  default_value:初期値
#define _sum(v,default_value) accumulate(v.begin(),v.end(),default_value )
// 丸め
#define _round(v) round(v)
// 2乗 / 3乗
#define _square(v) pow(v,2)
#define _cube(v)   pow(v,3)
// 大小判定
#define _max(x,y) max(x,y)
#define _min(x,y) min(x,y)
// string ⇒ int
#define _stringtoi(s) stoi(s)
// double 平方根
#define _sqrt(x) sqrt(x)
// double 引数 x 以上で最小の整数値
#define _ceil(x) ceil(x)

int main()
{
	int32_t n,x;
	cin >> n >> x;

	int32_t temp;
	int32_t min = (int32_t)1e5 + 1;
	for (int32_t i = 0; i < n; i++) {
		cin >> temp;
		x -= temp;
		if (min > temp) {
			min = temp;
		}
	}
	printf("%d\n", n + x / min);
	return 0;
	//	std::cout << "Hello World!\n"; 
}


Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
int N;
int A[200000];
int main(){
  int i;
  long long res = 0;
  long long mx = -1;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  for(i=(0);i<(N);i++){
    res +=max_L(mx - A[i], 0);
    chmax(mx, A[i]);
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200813-1 [beta]

// --- original code ---
// int N, A[2d5];
// {
//   ll res = 0, mx = -1;
//   rd(N,A(N));
//   rep(i,N){
//     res += max(mx - A[i], 0);
//     mx >?= A[i];
//   }
//   wt(res);
// }


Measured memory_bytes: 5424
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, X;
    cin >> N >> X;
    int now = 0;
    int ans = 1;
    for(int i = 1; i <= N; i++) {
        int L;
        cin >> L;
        now += L;
        if(now <= X) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
# include <bits/stdc++.h>
# define ll long long
using namespace std;
const ll oo = 1e15, N = 2e5 + 10;
ll fun(ll x){
	return x * x * x * x * x;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll x;
	cin >> x;
	for(ll A = -3000; A <= 3000; ++A){
		for(ll B = -3000; B <= 3000; ++B){
			if(fun(A) - fun(B) == x){
				cout << A << ' ' << B << '\n';
				return 0;
			}
		}
	}
}

Measured memory_bytes: 3640
import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


INF = 10**9

def solve() -> int:
    N = read_int()
    D = read_ints()
    if N>23:
        return 0
    D.sort(key=lambda d:min(d, 24-d))
    right = True
    assignment = [False]*24
    assignment[0] = True
    for d in D:
        if right:
            if assignment[d]:
                return 0
            assignment[d] = True
        else:
            if assignment[(24-d)%24]:
                return 0
            assignment[(24-d)%24] = True
        right = not right

    count = 0
    counts = []
    for i in range(1, len(assignment)+1):
        i %= 24
        if not assignment[i]:
            count += 1
        else:
            counts.append(count)
            count = 0
    return min(counts)+1
        


if __name__ == '__main__':
    print(solve())


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

using Graph = vector<vector<int>>;
int num = 0,tmp = 0;

vector<bool> seen;
void dfs(const Graph &G,int v){
	tmp++;
	if(seen[v]){
		return;
	}
	seen[v] = true;
	num = max(num,tmp);
	for(auto next_v:G[v]){
		if(seen[next_v]){
			continue;
		}
		dfs(G,next_v);
	}
}

int main(){
	// sengen
	int n,m;
	// nyuryoku
	cin >> n >> m;
	Graph G(n);
	int a,b;
	for(int i=0;i<m;i++){
		cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	// keisan
	seen.assign(n,false);
	for(int i=0;i<n;i++){
		tmp = 0;
		dfs(G,i);
	}
	// syutsuryoku
	cout << num << endl;
}

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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

  ll n, d;
  cin >> n >> d;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  vector<vector<PII>> g(2*n);
  // 頂点の重みを辺の重みに変換
  REP(i, n) {
    g[i].push_back({i+n, a[i]});
    g[i+n].push_back({i, a[i]});
  }
  // abs(i-j) * d を表す辺
  REP(i, n-1) {
    g[n+i].push_back({n+i+1, d});
    g[n+i+1].push_back({n+i, d});
  }
  // グラフに色を塗って全域木の候補の辺を特定
  ll ret = 0;
  vector<ll> dist(2*n, INF), col(2*n, -1);
  struct node {
    ll dist, vertex, col;
    node() {}
    node(ll a, ll b, ll c) : dist(a), vertex(b), col(c) {}
    bool operator<(node nd) const { return dist > nd.dist; }
  };
  priority_queue<node> que;
  REP(i, n) que.push(node(0, i, i));
  while(que.size()) {
    node p = que.top(); que.pop();
    if(dist[p.vertex] == INF) {
      dist[p.vertex] = p.dist;
      col[p.vertex] = p.col;
      for(auto to: g[p.vertex]) {
        que.push(node(p.dist+to.second, to.first, p.col));
      }
    } else {
      if(p.col != col[p.vertex]) {
        ret += dist[p.vertex] + p.dist;
      }
    }
  }
  // 色が変わる辺について各端点から数えているので1/2
  cout << ret/2 << endl;

  return 0;
}

Measured memory_bytes: 59756
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    var ans = 0L
    for (i in 1..n) {
        ans += i * (i + 1L) / 2
    }
    for (i in 0 until n - 1) {
        val u = sc.nextInt()
        val v = sc.nextInt()
        val a = minOf(u, v)
        val b = maxOf(u, v)
        ans -= a * (n - b + 1L)
    }
    println(ans)
}

fun main() {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


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

int main() {
  int N, X;
  cin >> N >> X;
  vector<int> M(N);
  for (int i = 0; i < N; i++) cin >> M.at(i);
  int sum = accumulate(M.begin(), M.end(), 0);
  X -= sum;
  cout << N + X / *min_element(M.begin(), M.end()) << "\n";
}

Measured memory_bytes: 3636
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);
    
    int N = sc.nextInt();
    String[] W = new String[N];

    for (int i = 0; i < N; i++) {
      W[i] = sc.next();
    }

    sc.close();

    String result = "Yes";

    for (int i = 0; i < N; i++) {
      for (int j = i + 1; j < N; j++) {
        if (W[i].equals(W[j])) {
          result = "No";
          break;
        }
      }
      if (result == "No") {
        break;
      }
    }

    String start = "";

    if (result == "Yes") {
      for (int i = 0; i < N; i++) {
        if (i != 0) {
          String[] s_ = W[i].split("");
          if (s_[0].equals(start)) {
            start = s_[s_.length - 1];
          } else {
            result = "No";
            break;
          }
        } else {
          String[] s_ = W[i].split("");
          start = s_[s_.length - 1];
        }
      } 
    }

    System.out.println(result);

  }

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<29;
const ll LLINF = 1LL<<61;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ex[100]={};
  FOR(i,1,10)FOR(j,1,10){
    ex[i*j]++;
  }
  int n;
  cin >> n;
  if (ex[n]>0)cout << "Yes" << endl;
  else cout << "No" << endl;
}


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

#define num_max(p,q)((p)>(q)?(p):(q))
#define num_min(p,q)((p)<(q)?(p):(q))
int cmp(const void *a, const void *b)
{
	return *(int*)a - *(int*)b;//昇順
	 //降順ならreturn *(int*)b - *(int*)a;
}
int main()
{
	int N;
	scanf("%d", &N);
	if(N%2==0)printf("0.500000000\n");
	else printf("%lf\n", (double)((N / 2)+1) / N);
	return 0;
}

Measured memory_bytes: 128
from itertools import*
s,k=open(0)
k=int(k)
g=[len(list(v))for _,v in groupby(s)]
print(sum(c//2for c in g)*k-((s[0]==s[-2])*g[0]%2&g[-2]%2)*(-k//2**(len(s)-1==g[0])+1))

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

int main() {
    int n;
    cin>>n;
    double dn = n / 1.08;
    int ans = -1;
    for (int i = (int)dn-5; i < (int)dn+5; i++)
    {
        if ((int)(i*1.08) == n) {
            ans = i;
        }
        /* code */
    }
    if (ans != -1) {
        printf("%d\n",ans);
    }
    else {
        printf(":(\n");
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define PI 3.141592653589793238
using namespace std;
#define int long long
struct Point{
  double x,y;
  Point(){}
  Point(double x,double y) :x(x),y(y){}
  Point operator + (Point p) {return Point(x+p.x,y+p.y);}
  Point operator - (Point p) {return Point(x-p.x,y-p.y);}
  Point operator * (double k) {return Point(x*k,y*k);}
  Point operator / (double k) {return Point(x/k,y/k);}
  double norm(){return x*x+y*y;}
  double abs(){return sqrt(norm());}

  bool operator < (const Point &p) const{
    return x!=p.x ? x < p.x : y < p.y;
  }

  bool operator == (const Point &p) const{
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};

typedef Point Vector;
typedef vector<Point> Polygon;

istream &operator >> (istream &is,Point &p){
  is>>p.x>>p.y;
  return is;
}

Vector spin(Vector v,double theta){
  Vector res;
  res.x=cos(theta)*v.x-sin(theta)*v.y;
  res.y=sin(theta)*v.x+cos(theta)*v.y;
  return res;
}
void koch(int n,Point p1,Point p2,Polygon&p){
  if(n==0){
    p.push_back(p1);
    return;
  }
  Vector v=(p2-p1)/3;
  Point p3=p1+v;
  Point p4=p3+spin(v,60*PI/180);
  Point p5=p1+v*2;
  koch(n-1,p1,p3,p);
  koch(n-1,p3,p4,p);
  koch(n-1,p4,p5,p);
  koch(n-1,p5,p2,p);
}
signed main(){
  int n;
  cin>>n;
  Polygon p;
  koch(n,Point(0,0),Point(100,0),p);
  p.push_back(Point(100,0));
  for(int i=0;i<(int)p.size();i++)
    printf("%.12f %.12f\n",p[i].x,p[i].y);
  return 0;
}


Measured memory_bytes: 3484
#include<bits/stdc++.h>
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cout<<#x<<"="<<x<<endl;
#define db2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
using namespace std;
int k,x;
int main() {
	scanf("%d%d",&k,&x);
	for(int i=max(-1000000,x-k+1);i<=min(1000000,x+k-1);i++)printf("%d ",i);
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,N) for (int (i) = 0; (i) < (N); (i)++)

int main() {

	std::cin.tie(nullptr); std::ios::sync_with_stdio(false);
	
	int N; std::cin >> N;
	std::map<int, int> frequency;
	rep(i, N) {
		int tmp; std::cin >> tmp;
		frequency[tmp]++;
	}
	int ans = 0;
	for (const auto& m : frequency) {
		if (m.first < m.second)ans += (m.second - m.first);
		else if (m.first > m.second)ans += m.second;
	}

	std::cout << ans;

	return 0;
}

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

int main(){

    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
        
    int ans=0;
    int dp[n+2];
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++){
    
        dp[i]  = min(dp[i-2] + abs(a[i-2]-a[i]),dp[i-1]+abs(a[i-1]-a[i]));
    } 
    cout<<dp[n-1];
}   

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

using namespace std;


int main(int argc, char *argv[])
{
    
    
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    
    int n, s[1010];
    double mean = 0.0, sigma = 0.0;
    
    while (cin >> n, n) {
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            mean += s[i];
        }
        mean /= n;
        for (int i = 0; i < n; i++) {
            sigma += pow(s[i]-mean, 2);
        }
        sigma /= n;
        sigma = sqrt(sigma);
        cout << fixed << setprecision(8) << sigma << endl;
        sigma = 0.0;
        mean = 0.0;
    }
    
    return 0;
}



Measured memory_bytes: 3256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	sc := NewScanner()
	N, W := sc.NextInt(), sc.NextInt()
	w := make([]int, N)
	v := make([]int, N)
	for i := 0; i < N; i++ {
		w[i] = sc.NextInt()
		v[i] = sc.NextInt()
		if i > 0 {
			w[i] -= w[0]
		}
	}
	w0 := w[0]
	w[0] = 0

	dp := make([][]int, N+1)

	for i := 0; i < N+1; i++ {
		dp[i] = make([]int, 3*N+1)
		for j := 0; j < 3*N+1; j++ {
			dp[i][j] = -1
		}
	}
	dp[0][0] = 0
	for i := 0; i < N; i++ {
		for k := N ; k >= 1; k-- {
			for j := 3*N - w[i]; j >= w[i]; j-- {
				//println(i, j, k, w[i], v[i], ":", k*w0)
				if k*w0+j > W {
					continue
				}
				if dp[k-1][j-w[i]] < 0 {
					continue
				}

				dp[k][j] = max(dp[k][j], dp[k-1][j-w[i]]+v[i])
				//println("s", dp[k][j])

			}
		}
	}

	ans := 0
	for i := 0; i < N+1; i++ {
		for j := 3 * N; j >= 0; j-- {
			ans = max(ans, dp[i][j])
		}
	}
	fmt.Println(ans)
}

func max(a int, b int) int {
	if a < b {
		return b
	}
	return a
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r: rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}
func (s *Scanner) NextInt64() int64 {
	v, _ := strconv.ParseInt(s.Next(), 10, 64)
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)
			result = append(result, int(v))
			start = s.p + 1
		}
	}

	return result
}
func (s *Scanner) NextInt64Array() []int64 {
	s.pre()
	start := s.p
	result := []int64{}
	for ; s.p < len(s.buf)+1; s.p++ {
		if s.p == len(s.buf) || s.buf[s.p] == ' ' {
			v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)
			result = append(result, v)
			start = s.p + 1
		}
	}
	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}


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

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

ll factorize(ll n) {
  ll p = 2;
  ll res = 1;
  while (p * p < n) {
    if (n % p == 0) {
      res++;
      while (n % p == 0) {
        n /= p;
      }
    }
    p++;
  }
  if (n != 1) res++;
  return res;
}

int main() {
  ll a, b;
  cin >> a >> b;

  ll c = gcd(a, b);

  cout << factorize(c) << endl;

  return 0;
}


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

using namespace std;

int main() {
	string S;
	cin >> S;
	string ans = "Yes";

	for (int i = 0; i < S.length(); i = i+2) {
		if (S[i] == 'L') {
			ans = "No";
		}
		if (i + 1 < S.length()) {
			if (S[i + 1] == 'R') {
				ans = "No";
			}
		}
	}

	cout << ans << endl;
	

	return 0;
}

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

typedef vector<int> vi;
vector<vi> v, g;
vi st, ans;

void get_rec_ans(int now_v) {

	int ret_ans = 0;

	for (int i = 0;i < v[now_v].size();i++) {
		int new_v = v[now_v][i];

		if (ans[new_v] == -1) get_rec_ans(new_v);
			
		ret_ans = max(ret_ans, ans[new_v]);
	}

	ans[now_v] = ret_ans + 1;
}

int main() {
	int n, m, from, to;

	cin >> n >> m;

	v.resize(n); g.resize(n); ans.resize(n);

	fill (ans.begin(), ans.end(), -1);

	for (int i = 0;i < m;i++) {
		cin >> from >> to; from--; to--;

		v[to].push_back(from); g[from].push_back(to);		
	}

	for (int i = 0;i < n;i++) if (g[i].size() == 0) st.push_back(i);

	int general_answer = 0;

	for (int i = 0;i < st.size();i++) {
		get_rec_ans(st[i]);
		if (ans[st[i]] > general_answer) general_answer = ans[st[i]];
	}

	cout << general_answer - 1;
}


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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define Task ""

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 5;

signed main(void)
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("A.INP", "r")){
        freopen("A.INP", "r", stdin);
        freopen("A.OUT", "w", stdout);
    }
    if (fopen(Task".INP", "r")){
        freopen(Task".INP", "r", stdin);
        freopen(Task".OUT", "w", stdout);
    }
    int N; cin >> N;
    vector<int> a(N+5);
    for (int i=1; i<=N; ++i){
        cin >> a[i];
    }
    vector<int> res;
    while (N){
        int ok = 0;
        for (int i=1; i<=N; ++i){
            if (a[i] == i){
                ok = i;
            }
        }
        if (ok == 0){
            cout << "-1";
            return 0;
        }
        res.pb(ok);
        for (int i=ok; i<N; ++i){
            a[i] = a[i+1];
        }
        --N;
    }
    reverse(res.begin(), res.end());
    for (auto it : res) cout << it << '\n';
}


Measured memory_bytes: 256
import java.io.*;
 
public class Main{
  public static void main(String[] args) {
    try {
      long result;
      int n, i = 0;
      long num[] = {0, 0, 0, 0, 0};
 
      BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
 
      n = Integer.parseInt(reader.readLine());
      String name[] = new String[n];
      char nameF[] = new char[n];
 
      for(i = 0; i < n; i++){
        name[i] = reader.readLine();
      }
      
      for(i = 0; i < n; i++){
        nameF[i] = name[i].charAt(0);
      }
      
      for(i = 0; i < n; i++){
        if (nameF[i] == 'M') {
          num[0] = ++num[0];
        }
        if (nameF[i] == 'A') {
          num[1] = ++num[1];
        }
        if (nameF[i] == 'R') {
          num[2] = ++num[2];
        }
        if (nameF[i] == 'C') {
          num[3] = ++num[3];
        }
        if (nameF[i] == 'H') {
          num[4] = ++num[4];
        }
      }
 
      result = num[0]*num[1]*(num[2]+num[3]+num[4])+num[0]*num[2]*(num[3]+num[4])+num[0]*num[3]*num[4]
               +num[1]*num[2]*(num[3]+num[4])+num[1]*num[3]*num[4] + num[2]*num[3]*num[4];
      
      System.out.println(result);
    }
    catch (Exception e) {
      
    }
  }
}

Measured memory_bytes: 32596
package main

import (
	"bufio"
	"fmt"
	"os"
)

var H, W int
var grid []string
var d [][]int

func id(x, y int) int {
	return x + y*W
}

func idx(id int) int {
	return id % W
}

func idy(id int) int {
	return id / W
}

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

func bfs(s int) {
	used := make([]bool, H*W)
	q := make([][]int, 0)
	q = append(q, []int{s, 0})
	for len(q) > 0 {
		nowId, dist := q[0][0], q[0][1]
		q = q[1:]
		x, y := idx(nowId), idy(nowId)
		if grid[y][x] == '#' {
			continue
		}
		if used[nowId] {
			continue
		}
		used[nowId] = true
		d[s][nowId] = dist
		for i := 0; i < 4; i++ {
			nx := x + dx[i]
			ny := y + dy[i]
			if 0 <= nx && nx < W && 0 <= ny && ny < H {
				q = append(q, []int{id(nx, ny), dist + 1})
			}
		}
	}
}

func main() {
	H, W = ReadInt(), ReadInt()
	grid = make([]string, H)
	for i := 0; i < H; i++ {
		grid[i] = ReadString()
	}
	d = make([][]int, H*W)
	for i := 0; i < H*W; i++ {
		d[i] = make([]int, H*W)
	}
	for s := 0; s < H*W; s++ {
		bfs(s)
	}
	ans := -1
	for i := 0; i < H*W; i++ {
		for j := 0; j < H*W; j++ {
			if d[i][j] > ans {
				ans = d[i][j]
			}
		}
	}
	fmt.Println(ans)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }


Measured memory_bytes: 6480
#include<stdio.h>
using namespace std;
int search(int A[],int n,int key)
{
	int i=0;
	A[n]=key;
	while(A[i] !=key)	i++;
	return i !=n;
 } 
int main()
{
	int i,n,A[10000+1],q,key,sum=0;
	
	scanf("%d",&n);
	for(i=0;i<n;i++) 	scanf("%d",&A[i]);
	
	scanf("%d",&q);
	for(i=0;i<q;i++)
	{
		scanf("%d",&key);
		if(  search( A, n, key) ) sum++;
	 }
	 printf("%d\n",sum);
	 return 0;
}

Measured memory_bytes: 2764