akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main {
    private static void debug(List<Integer> al){
        for(int xx : al) System.out.print(xx+" ");
        System.out.println();
    }
    private static void debug(int arr[]){
        for(int xx : arr) System.out.print(xx+" ");
        System.out.println();
    }
    private static void solver(InputReader sc, PrintWriter out) throws Exception {
            int n = sc.nextInt();
            long d = sc.nextLong();
            d *=d;
            int count=0;
            for(int i=0; i<n; i++){
                long x = sc.nextLong();
                long y = sc.nextLong();
                x *=x; y*=y;
                if(x+y <= d) count++;
            }
            out.println(count);
    }

    private static int lcm(int a, int b) {

        return (a * b) / gcd(a, b);
    }

    private static int gcd(int a, int b) {

        if (b == 0)
            return a;

        return gcd(b, a % b);
    }

    public static void main(String[] args) throws Exception {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        solver(in, out);
        out.close();
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}

class Pair {
    int x, y;

    Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return x == pair.x &&
                y == pair.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

class Tuple implements Comparable<Tuple> {
    int x, y, z;

    public Tuple(int x, int y, int z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public int compareTo(Tuple t) {
        if (this.z == t.z) {
            if (this.y == t.y) {
                return t.x - this.x;
            } else return t.y - this.y;
        } else
            return this.z - t.z;
    }


}

Measured memory_bytes: 55460
#include <bits/stdc++.h>
using namespace std;
long long f[1001][1001];
char c[1001][1001];
int main()
{
	int h,w,i,j;
	scanf("%d %d",&h,&w);
	for(i=1;i<=h;i++)
	{
		getchar();
		for(j=1;j<=w;j++)
			scanf("%c",&c[i][j]);
	}
	for(i=1;i<=h;i++)
	{
		for(j=1;j<=w;j++)
		{
			if(i==1&&j==1)
				f[i][j]=1;
			else if(c[i][j]=='#')
				f[i][j]=0;
			else if(c[i][j]=='.')
				f[i][j]=(f[i-1][j]+f[i][j-1])%1000000007;
		}
	}
	printf("%lld",f[h][w]);
	return 0;
}

Measured memory_bytes: 9088
import java.util.Scanner;


	public class Main {
		
		

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
	        
			int k = sc.nextInt();
			String s = sc.next();
			
			if(s.length()<=k) {
				System.out.println(s);
				return;
			}
			
			StringBuilder sb = new StringBuilder();
			sb.append(s);
			sb.replace(k, s.length(), "...");
			System.out.println(sb);
			
		}
		
	}


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

typedef long long ll;
int main(){
    ll N, M; cin >> N >> M;
    ll ans=1;
    for(ll i=1; i*i<=M; ++i){
        if(M%i==0){
            ll b = M/i;
            if(b*N<=M) ans = max(ans, b);
            if(i*N<=M) ans = max(ans, i);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn.{readInt,readLine}
import scala.collection.mutable.ArrayBuffer

object Main {
  val NIL = -1

  class Node(var parent:Int = NIL,var left:Int = NIL,var right:Int = NIL) { }

  def main(args:Array[String]) = {
    val n = readInt
    val tree = (0 until n).map(_=>new Node).toArray

    for(i<-0 until n) {
      val s = readLine.split(" ").map(_.toInt)
      tree(s(0)).left = s(1)
      tree(s(0)).right = s(2)
      if(s(1) != NIL) tree(s(1)).parent = s(0)
      if(s(2) != NIL) tree(s(2)).parent = s(0)
    }

    def preOrder(id:Int):Unit = {
      if(id!=NIL) {
        print(" "+id)
        preOrder(tree(id).left)
        preOrder(tree(id).right)
      }
    }

    def inOrder(id:Int):Unit = {
      if(id!=NIL) {
        inOrder(tree(id).left)
        print(" "+id)
        inOrder(tree(id).right)
      }
    }

    def postOrder(id:Int):Unit = {
      if(id!=NIL) {
        postOrder(tree(id).left)
        postOrder(tree(id).right)
        print(" "+id)
      }
    }

    val root = tree.indexWhere(_.parent == NIL)

    println("Preorder")
    preOrder(root)
    println
    println("Inorder")
    inOrder(root)
    println
    println("Postorder")
    postOrder(root)
    println
  }
}

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

using namespace std;

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

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int k;
  cin >> k;
  ll a[k];
  REP(i, k) cin >> a[i];
  ll ok = 1e18, ng = 0;
  while (1 < abs(ok - ng)) {
    ll mid = (ok + ng) / 2;
    ll n = mid;
    REP(i, k) n = a[i] * (n / a[i]);
    (2 <= n ? ok : ng) = mid;
  }
  ll mn = ok;
  ok = 0, ng = 1e18;
  while (1 < abs(ok - ng)) {
    ll mid = (ok + ng) / 2;
    ll n = mid;
    REP(i, k) n = a[i] * (n / a[i]);
    (n <= 2 ? ok : ng) = mid;
  }
  ll mx = ok;
  if (mx < mn) {
    puts("-1");
    return 0;
  }
  cout << mn << " " << mx << endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
	using namespace std;

	int main() {
		string S, T;
		cin >> S >> T;

		cout << T << S;
	}
		

Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
#include<limits.h>
#include<unordered_map>
#include<unordered_set>
#include<deque>
#include<cstdio>
using namespace std;
typedef long long int ll;
const int INF = 1 << 30;
#define rep(i,n) for(int i=(ll)0;i<(ll)n;++i)
#define ALL(x) x.begin(),x.end()
int main() {
	int n, a, b;
	cin >> n >> a >> b;
	cout << ((b-a-1)%2==0?"Borys":"Alice") << endl;
	return 0;
}

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

//#define int long long
#define ll long long
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    int n,k; cin >> n >> k;
    if(n%k==0)cout << 0 << endl;
    else cout << 1 << endl;
}


Measured memory_bytes: 256
'''
	We can show that if u and v belong to the same connected component, then they are friends w/ each other
	So everyone in a given connected component is friends with one another
	So everyone in a given connected component must be separated into different groups

	If we have a CC of with sz nodes in it, then we need at least sz different groups

	So, the minimum number of groups needed is max sz(CC)
'''
n, m = map(int,input().split())
adj = [[] for u in range(n+1)]
for i in range(m):
	u, v = map(int,input().split())
	adj[u].append(v)
	adj[v].append(u)

vis = [False for u in range(n+1)]
def bfs(s):
	sz = 0
	queue = [s]
	ptr = 0
	
	while ptr < len(queue):
		u = queue[ptr]
		if not vis[u]:
			vis[u] = True
			sz += 1
			for v in adj[u]:
				queue.append(v) 
		ptr += 1

	return sz

CCs = []
for u in range(1,n+1):
	if not vis[u]:
		CCs.append(bfs(u))

print(max(CCs))

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;

const double EPS = 1e-9;
const int MOD = 1e9 + 7;

ll calc(ll a, ll b, ll p) {
    if (b == 0) return 1;
    if (b % 2) {
        return (a * calc(a, b - 1, p)) % p;
    } else {
        ll t = calc(a, b / 2, p);
        return (t * t) % p;
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int x, y;
    cin >> x >> y;
    int move = (x + y) / 3;
    int w, h;
    w = x - move;
    h = y - move;
    int remain = w + h;
    if (w < 0 || h < 0 || move != remain) {
        cout << 0 << endl;
        return 0;
    }
    ll res = 1;
    FOR (i, 1, w + h + 1) {
        res = (res * i) % MOD;
    }
    FOR (i, 1, w + 1) {
        res = (res * calc(i, MOD - 2, MOD)) % MOD;
    }
    FOR (i, 1, h + 1) {
        res = (res * calc(i, MOD - 2, MOD)) % MOD;
    }
    cout << res << endl;

    return 0;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(){
  char s[50],t[50];
  scanf("%s%s",s,t);
  int i;
  for(i=0;i<strlen(s);i++){
    printf("%c",s[i]);
    if(i<strlen(t))printf("%c",t[i]);
  }
  return 0;
}


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

using namespace std;

#define MAX 35
#define EPS 1e-10
#define equal(a,b) (fabs(a-b) < EPS)

struct Point{
  double x,y;

  Point(){}
  Point(double x,double y) : x(x),y(y) {}

  Point operator + (const Point &p)const{ return Point(x+p.x,y+p.y); }
  Point operator - (const Point &p)const{ return Point(x-p.x,y-p.y); }
  Point operator * (const double &k)const{ return Point(x*k,y*k); }
  Point operator / (const double &k)const{ return Point(x/k,y/k); }
  bool operator < (const Point &p)const{ return x != p.x ? x < p.x : y < p.y; }
};

typedef Point Vector;
typedef vector<Point> Polygon;

double cross(const Point &a,const Point &b){ return a.x*b.y - b.x*a.y; }

ostream &operator << (ostream &os,Point &p){ 
  return os << "(" << p.x << "," << p.y << ")";
}

struct Segment{
  Point s,t;
  Segment(){}
  Segment(Point s,Point t) : s(s),t(t) {}
};

Point crosspointSS(const Segment &a,const Segment &b){
  Vector va = a.t-a.s, vb = b.t-b.s;
  double d = cross(vb,va);
  return a.s+va*cross(vb,b.t-a.s)*(1.0/d);
}

double getArea(const Polygon &p){
  int N = p.size();
  double res = 0;
  for(int i = 1 ; i < N+1 ; i++){
    res += (p[i%N].x-p[i-1].x)*(p[i%N].y+p[i-1].y);
  }
  res /= 2.0;
  return abs(res);
}

int main(){
  int N;
  while(cin >> N,N){
    double in;
    vector<Point> p[4];
    Point q[MAX][MAX];
    q[0][0] = Point(0,0);
    q[0][N+1] = Point(0,1);
    q[N+1][0] = Point(1,0);
    q[N+1][N+1] = Point(1,1);
    for(int i = 0 ; i < 2 ; i++){
      p[i].resize(N);
      for(int j = 0 ; j < N ; j++){
        cin >> in;
        p[i][j] = Point(in,i);
        if(i == 0){
          q[j+1][0] = p[i][j];
        }else{
          q[j+1][N+1] = p[i][j];
        }
      }
    }
    for(int i = 2 ; i < 4 ; i++){
      p[i].resize(N);
      for(int j = 0 ; j < N ; j++){
        cin >> in;
        p[i][j] = Point(i-2,in);
        if(i == 2){
          q[0][j+1] = p[i][j];
        }else{
          q[N+1][j+1] = p[i][j];
        }
      }
    }
    vector<Segment> s[2];
    for(int i = 0 ; i < N ; i++){
      s[0].push_back(Segment(p[0][i],p[1][i]));
    }
    for(int i = 0 ; i < N ; i++){
      s[1].push_back(Segment(p[2][i],p[3][i]));
    }
    for(int i = 0 ; i < N ; i++){
      for(int j = 0 ; j < N ; j++){
        Point cp = crosspointSS(s[0][i],s[1][j]);
        q[i+1][j+1] = cp;
      }
    }
    double res = 0;
    for(int i = 0 ; i <= N ; i++){
      for(int j = 0 ; j <= N ; j++){
        Polygon pg(4);
        pg[0] = q[i][j];
        pg[1] = q[i][j+1];
        pg[2] = q[i+1][j+1];
        pg[3] = q[i+1][j];
        res = max(res,getArea(pg));
      }
    }
    printf("%.10f\n",res);
  }
  return 0;
}

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

double dp[3030][3030];

double get(ll complete, ll i, double a[])
{
    if(i<0)
    {
        if( complete >n/2 ) return 1.0;
        else return 0.0;
    }
    if(dp[complete][i]!=-1) return dp[complete][i];

    double ans =  a[i]*get(complete+1,i-1,a) + (1.0-a[i])*get(complete,i-1,a);
    return dp[complete][i] = ans ;

}

int main() {
    for(ll i=0;i<3030;i++)
    {
        for(ll j=0;j<3030;j++) dp[i][j] = -1;
    }

    cin >> n;
    double a[n];
    for(ll i=0;i<n;i++) cin>> a[i];
    cout << fixed << setprecision(20) << get(0,n-1,a);
}


Measured memory_bytes: 72320
import java.util.*;
import java.util.function.*;
import java.lang.*;
import java.io.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int L = sc.nextInt();
        int R = sc.nextInt();
        int d = sc.nextInt();
        int ans = 0;
        for(int i=L; i<=R; i++){
            if(i%d==0) ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 35748
/*
  Contest 101
  A - Eating Symbols Easy
  Rakesh Kumar --> 24/09/2020
 */

#include <bits/stdc++.h>

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

    std::string s;
    std::getline(std::cin, s);
    int r = 0;
    for (char c : s)
        if (c == '+')
            ++r;
        else
            --r;
    std::cout << r << std::endl;

    return 0;
}


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

struct shi
{
	int32_t ken;
	int32_t shi;
	int32_t year;
	int32_t num;
};

int main()
{
	int32_t N, M;
	cin >> N >> M;

	vector<struct shi> S(M);
	for (int32_t i = 0; i < M; i++) {
		cin >> S[i].ken >> S[i].year;
		S[i].shi = i;
	}

	sort(S.begin(), S.end(), [](struct shi left, struct shi right) -> bool {
		if (left.ken == right.ken)
			return left.year < right.year;
		else
			return left.ken < right.ken;
	});

	map<int32_t, int32_t> map_ken;
	for (int32_t i = 0; i < M; i++) {
		if (map_ken.count(S[i].ken) == 0) {
			map_ken[S[i].ken] = 0;
		} else {
			map_ken[S[i].ken]++;
		}
		S[i].num = map_ken[S[i].ken] + 1;
	}

	sort(S.begin(), S.end(), [](struct shi left, struct shi right) -> bool {
		return left.shi < right.shi;
	});

	for (int32_t i = 0; i < M; i++) {
		cout << setfill('0') << right << setw(6) << S[i].ken;
		cout << setfill('0') << right << setw(6) << S[i].num << endl;
	}

	return 0;
}


Measured memory_bytes: 7808
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
int mod(ll a){
    int c=a%1000000007;
    if(c>=0)return c;
    else return c+1000000007;
}
typedef pair<int,int> i_i;


int main(){
  ll n,a,b;cin>>n>>a>>b;
    ll h[n+1];for(int i=1;i<=n;i++)cin>>h[i];
    
    ll left=1,right=1000000001;
    while(left<right){
        ll mid=(left+right)/2;
        
        ll g[n+1];for(int i=1;i<=n;i++)g[i]=h[i]-(ll)b*mid;
        ll count=0;
        for(int i=1;i<=n;i++){
            if(g[i]>0){
                if(g[i]%(a-b)!=0)count++;
                count+=g[i]/(a-b);
            }
        }
        if(count<=mid){
            right=mid;
        }else{
            left=mid+1;
        }
    }
    
    cout<<left<<endl;
    
    
    return 0;
}




Measured memory_bytes: 1792
using System;

class Program
{
 static void Main(string[] args) 
 {
   string[] nums;
   int a;
   int b;
   int sum;
   
   nums = Console.ReadLine().Split(' ');
   a = int.Parse(nums[0]);
   b = int.Parse(nums[1]);
   sum =  a * b;
   
   Console.WriteLine(( (sum % 2) == 0 ? "Even": "Odd" ));
 }
}

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

const int MAXN = 1e5;
int a[MAXN];
int c[MAXN];

main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        ans += x;
    }
    for (int i = 2; i <= n; ++i) {
        cin >> c[i];
    }
    for (int i = 1; i < n; ++i) {
        if (a[i] == a[i - 1] + 1) {
            ans += c[a[i]];
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
        int n;cin>>n;
        vector<int>nums;
        for(int i=0;i<2*n;i++)
        {
                int x;cin>>x;
                nums.push_back(x);
        }
        sort(nums.begin(),nums.end());
        long sum=0;
        //if(n>)
        for(int i=0;i<nums.size();i=i+2)
        {
                sum=sum+nums[i];
        }
        cout<<sum<<endl;
}

Measured memory_bytes: 256
#include<iostream>
 using namespace std;
 const long long mod = 1e9 + 7;
 int a[200005], b[200005], c[200005];
 long long num[200005];
int main() 
{
	 int n, k = 1;
	 cin >> n;
     for (int i = 1; i <= n; i++) 
		 scanf("%d", &a[i]);
	 c[1] = a[1];
	 int t = 1;
	 for (int i = 2; i <= n; i++) 
	 {
		 if (a[i] != c[t])
			 c[++t] = a[i];
	
	  }
	  num[0] = 1;
	  for (int i = 1; i <= t; i++) {
		   if (b[c[i]])
			   num[i] = (num[i - 1] + num[b[c[i]]]) % mod;
		   else num[i] = num[i - 1];
		       num[i] %= mod;
		       b[c[i]] = i;
		
	  }
	  cout << num[t] << endl;
	  return 0;
}

Measured memory_bytes: 4096
import java.io.*;
import java.util.*;

class Main{
	private static ArrayList<Integer> sum_dig(ArrayList<Integer> a){
		ArrayList<Integer> b = new ArrayList<Integer>();
		for(int i = 0;i<a.size()/2;i++){
			int sum = 0;
			if(i == 0) sum = a.get(0)+a.get(1);
			sum =  a.get(i*2)+a.get(i*2+1);
			String sums;
			sums = String.valueOf(sum);
			b.add(sums.length());
			}
		return b;
	}
	private static void print_dig(ArrayList<Integer> a){
		for(int i = 0;i<a.size();i++){
			System.out.println(a.get(i));
		}
	}
		public static void main(String args[]) throws IOException{
			ArrayList<Integer> dig = new ArrayList<Integer>();
			Scanner scan = new Scanner(System.in);

			int n1,n2;
			while(scan.hasNext()){
				try{
				String str1 = scan.next();
				String str2 = scan.next();
				
				n1 = Integer.parseInt(str1);
				n2 = Integer.parseInt(str2);
				dig.add(n1);
				dig.add(n2);
			}
			catch(NumberFormatException e){
				break;
			}
		}
			ArrayList<Integer> res = new ArrayList<Integer>();
			res = sum_dig(dig);
			print_dig(res);
	}
}

Measured memory_bytes: 12000
n = int(input())
peer = [[] for _ in range(n)]
rec = []
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
  rec.append([a,b])
can = []
for i in range(n):
  can.append(len(peer[i]))
#print(peer)
#print(can)
ans = max(can)
now = [0]
clr = [0 for _ in range(n)]
ok = [0 for _ in range(n)]
rank = [0 for _ in range(n)]
clr[0] = ans
ok[0] = 1
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if clr[y] == 0:
        now.append(y)
        clr[y] = ok[x]
        rank[y] = rank[x] + 1
        ok[x] = ok[x] % ans + 1
        ok[y] = clr[y] % ans + 1
print(ans)
#print(clr)
for w in rec:
  a,b = w
  if rank[a] > rank[b]:
    m = a
  else:
    m = b
  print(clr[m])
#print(rank)

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

int main(){
  int X;
  cin >> X;
  for (int i = X; true; i++){
    bool ans = true;
    for (int j = 2; j < sqrt(X); j++){
      if(i % j == 0) ans = false;
    }
    if (ans){
      cout << i << endl;
      break;
    }
  }
}  

Measured memory_bytes: 3628
loop do
  n = gets.chomp.to_i
  m = gets.chomp.to_i
  break if n == 0 && m == 0

  friend = []
  relation = []
  m.times do |i|
    relation << gets.chomp.split(" ").map(&:to_i)
    #p relation
    friend << relation[i][1] if relation[i][0] == 1
    frined << relation[i][0] if relation[i][1] == 1
  end
  #p friend
  if friend == []
    #puts "hoge"
    puts 0
    next
  end
  fFriend = []
  friend.each do |x|
    relation.each do |y|
      fFriend << y[1] if x == y[0] && y[1] != 1
      fFriend << y[0] if x == y[1] && y[0] != 1
    end
  end
  totFriend = friend + fFriend
  puts totFriend.uniq.length
end



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

using namespace std;

int main(){
        char c;
        cin>>c;
        if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
                cout<<"vowel"<<endl;
        }
        else{
                cout<<"consonant"<<endl;
        }
        return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
 
 
template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}
 
  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }
 
  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}
 
  Mint inv(){return pow(MOD-2);}
 
  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}
 
  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}
 
  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}
 
  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}
 
  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}

Mint<Int> f(Int r, Int c) {
    Mint<Int> res(0);
    res = res.comb(r+c, r);
    return res;
}

int main()
{
    Int r1, c1, r2, c2;
    cin >> r1 >> c1 >> r2 >> c2;

    Mint<Int> res = f(r2+1, c2+1) - f(r1,c2+1) - (f(r2+1, c1) - f(r1, c1));
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
const int N = 2e5+5;
const ll MOD = 1e9+7;
ll n;
ll fast_exp(ll base, ll exp)
{
  ll res=1;
  while(exp>0)
    {
      if(exp%2==1) res=(res*base)%MOD;
      base=(base*base)%MOD;
      exp/=2;
    }
  return res%MOD;
}

ll getInverse(ll n)
{
  return fast_exp(n, MOD-2) ;
}

ll divide(ll a, ll b)
{
  a=a%MOD ;
  b=b%MOD ;
  return (a*(getInverse(b)%MOD))%MOD ;
}
vector< vll > graph(N);
ll sizes[N] = {}, holy[N] = {};
void find_sizes(int i, int p)
{
    int j, si = graph[i].size();
    sizes[i] = 1;
    FOR0(j, si)
    {
        int v = graph[i][j];
        if( v == p) continue;
        find_sizes(v, i);
        sizes[i] += sizes[v];
    }
}
void dfs(int i, int p)
{
    int j, si = graph[i].size();
    ll sum = fast_exp(2, sizes[0] - sizes[i]);
    ll mul = sum;
    FOR0(j, si)
    {
        int v = graph[i][j];
        if( v == p) continue;
        dfs(v, i);
        ll cur = fast_exp(2, sizes[v]);
        mul *= cur;
        mul %= MOD;
        sum += (cur - 1);
        sum += MOD;
        sum %= MOD;
    }
    mul -= sum;
    mul += 2*MOD;
    mul %= MOD;
    holy[i] = mul;
}
int main()
{
    she_told_me_dont_worry
    ll n;
    cin>>n;
    ll i;
    FOR0(i, n-1)
    {
        int u, v;
        cin>>u>>v;
        u--;v--;
        graph[u].pb(v);
        graph[v].pb(u);
    }
    find_sizes(0, 0);
    dfs(0, 0);
    ll num = 0;
    FOR0(i, n)
    {
        num += holy[i];
        num %= MOD;
        //cout<<sizes[i]<<" "<<holy[i]<<" "<<endl;
    }
    //cout<<num<<endl;
    ll denom = fast_exp(2, n);
    num = divide(num, denom);
    cout<<num<<endl;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

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

int main(){
  long long x,a,b,c,d,ansa,ansb;
  cin>>x>>a>>b;
  if(x+a+b>21){
    cout<<"bust"<<endl;
  }
  else{
    cout<<"win"<<endl;
  }
}


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

namespace AtCoder
{
    class Program
    {
        private const int MODULO = 1000000007;
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static long Solve(int N, long[] A)
        {
            var dict = new Dictionary<long, int>();
            dict[0] = 1;
            long sum = 0;
            foreach (long a in A)
            {
                sum += a;
                if (!dict.ContainsKey(sum)) { dict[sum] = 0; }
                ++dict[sum];
            }
            long ans = 0;
            foreach (var value in dict.Values)
            {
                ans += Math.BigMul(value, value - 1) / 2;
            }
            return ans;
        }
        static void Main(string[] args)
        {
            int N = ReadInt();
            long[] A = ReadLongs();
            Console.WriteLine(Solve(N, A));
        }
    }
}


Measured memory_bytes: 39792
#pragma GCC optimize "-O3"
#pragma GCC target ("avx")
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int>>
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define MEMSET(a) memset(a,0,sizeof(a))
#define inf (1ll<<60)
#define SORT(v) sort(all(v))
#define RSORT(v) sort(all(v),greater<int>())
#define SPEED ios::sync_with_stdio(false);cin.tie(0);cout<<fixed<<setprecision(12)
signed gcd(int a, int b){return b?gcd(b,a%b):a;}
signed lcm(int a, int b){return a*b/gcd(a,b);}
//priority_queue<int, vi, greater<int> > que;//昇順

using namespace std;

const int mod=1e9+7;

signed main(){
    SPEED;
    int a,b;
    cin >> a >> b;
    if((a*b)%2==1)
    {
        cout << "Odd" << endl;
    }
    else
    {
        cout << "Even" << endl;
    }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define MOD (1e9+7)

int main(void){
	int x,y;
	cin >> x >> y;
	cout << ((x%y==0)?-1:x) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = 1; i <= n; i++)
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
using P = pair <int, int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
 
ll MOD = 1000000007;
ll INF =1<<30;

int main(){
   int n;
   cin >> n;
   for(int i = 1; i<=n;++i){
      if(i*108/100==n) {
         cout << i <<endl;
         return 0;
      }
   }
   cout << ":(" <<endl;
}

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
ll MOD = 1e9+7;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }

int main(){
  ll i, j;
  ll a, b;
  cin >> a >> b;
  if(a * b % 2 == 0)
  cout << "No" << endl;
  else
    cout << "Yes" << endl;

  return 0;
}

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


int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  int w,s;
  ll v;
  vector<tuple<int,int,ll> > info(n);
  //  cout << info.size() << endl;
  rep(i,n){
    cin >> w >> s >> v;
    info[i]=make_tuple(w,s,v);
  }
  sort(info.begin(), info.end(),[](tuple<int,int,ll> a,tuple<int,int,ll> b){
				  int sa=get<1>(a);
				  int sb=get<1>(b);
				  int wa=get<0>(a);
				  int wb=get<0>(b);
				  return min(sa,sb-wa) > min(sb,sa-wb);
				});
  int w_max=3e4;
  ll dp[w_max];
  ll ndp[w_max];
  rep(i,w_max) dp[i]=0;
  rep(i,w_max) ndp[i]=0;
  rep(i,n){
    rep(j,get<1>(info[i])+1){
      int nw=j+get<0>(info[i]);
      if(nw<w_max){
	ndp[nw]= max(dp[nw], dp[j]+get<2>(info[i]));
      }
    }
    rep(i,w_max) dp[i]=ndp[i];
  }
  ll ans=0;
  rep(i,w_max){
    //    if(dp[i]!=0) cout << "i dp " << i << " " << dp[i] << endl;
    ans=max(ans,dp[i]);
  }
  cout << ans << endl;

  return 0;
    

}


Measured memory_bytes: 768
object Main extends App {
  var array = Vector.empty[Int]
  var k = 0
  for(i<-1 to 5) {
    array :+= scala.io.StdIn.readInt()
  }
  val arrayTurple = array.map {d =>
    (d, if (d % 10 == 0) 0 else 10 - (d % 10))
  }
  val sum = arrayTurple.sortBy(_._2).zipWithIndex.map {case (a, index) =>
    if (index == 4) {
      a._1
    } else {
      a._1 + a._2
    }
  }.sum
  println(sum)
}

Measured memory_bytes: 25544
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
using LL = long long;

int main(void)
{
	int n;
	cin >> n;
	int maxn = 0, minn = 10000;
	for (int i = 0; i < n; ++i)
	{
		int a;
		cin >> a;
		maxn = max(maxn,a);
		minn = min(minn, a);
	}
	cout << maxn - minn << endl;
	return 0;
}


Measured memory_bytes: 256
#include <cassert>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  debug_out(t...);
}

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if(b==0)return 1;

  if ((a == 0)||(mod!=-1&&(a+mod)%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

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

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

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

  ll n,m;
  std::cin>>n>>m;

  std::vector<bool> ac(n,false);
  std::vector<ll> wa(n,0);

  ll wasum=0;

  rep(i,0,m){
    ll p;
    std::cin>>p;
    p--;
    std::string s;
    std::cin>>s;

    if(s=="AC"){
      if(!ac[p]){
        wasum+=wa[p];
        ac[p]=true;
      }
    }else{
      wa[p]++;
    }
  }

  ll accnt=0;
  rep(i,0,n)if(ac[i])accnt++;

  std::cout<<accnt<<" "<<wasum<<"\n";

  return 0;
}

Measured memory_bytes: 1024
#include<iostream>
    #include<string>
     
    using namespace std;
     
    int main() {
    	int a[26]{0};
    	string s;
    	cin >> s;
    	for (int i = 0; i < s.size(); i++)a[s[i] - 'a']++;
    	int cnt;
    	for (int i = 0; i < 26; i++) {
    		if (a[i] == 0) {
    			cnt = i;
    			break;
    		}
    		else if (i == 25) {
    			cout << "None" << endl;
    			return 0;
    		}
    	}
    	char ans = 'a';
    	ans += cnt;
    	cout << ans << endl;
    	return 0;
    }

Measured memory_bytes: 512
#include <stdio.h>
#include <stdlib.h>

struct Node {
  int key;
struct Node *prev,*next;
};

struct Node *nil;

void init();//双方向リストの初期化
void insert(int);
struct Node* listSearch(int );
void deleteNode(struct Node *);
void deleteFirst();
void deleteLast();
void deleteKey(int );

int main(){
  int key,n,i,size=0,p=0,d=0;
  char com[25];
  scanf("%d",&n);
  init();
  for(i=0;i<n;i++){
    scanf("%s%d",com,&key);
    if(com[0]=='i'){
      insert(key);
      p++;
      d++;
    }
    else if(com[6]=='F')
      deleteFirst();
    else if(com[6]=='L')
      deleteLast();
    else{ deleteKey(key);
      d++;
    }
  size--;
  }
  struct Node *cur=nil->next;
  int f=0;
  while(1){
    if(cur==nil)break;
    if(f++>0)printf(" ");
    printf("%d",cur->key);
    cur=cur->next;
  }
  printf("\n");


  return 0;
}
void init(){
  nil=(struct Node*)malloc(sizeof(struct Node));
  nil->next=nil;
  nil->prev=nil;
}
void insert(int key){
  struct Node *x=(struct Node*)malloc(sizeof(struct Node));
  x->key =key;
  x->next=nil->next;
  nil->next->prev=x;
  nil->next=x;
  x->prev=nil;
}
struct Node* listSearch(int key){
  struct Node *cur=nil->next;
  while(cur!=nil&&cur->key!=key)
    cur=cur->next;
  return cur;
}
void deleteNode(struct Node *t){
  if(t==nil)return;
  t->prev->next=t->next;
  t->next->prev=t->prev;
  free(t);
}
void deleteFirst(){
  deleteNode(nil->next);
}
void deleteLast(){
  deleteNode(nil->prev);
}
void deleteKey(int key){
  deleteNode(listSearch(key));
}



Measured memory_bytes: 32952
def solve():
    N = int(raw_input())
    H = [int(_) for _ in raw_input().split()]
    MaxH = H[0]
    cnt = 1
    for i in range(1,N):
        if H[i] >= MaxH:
            cnt += 1
            MaxH = H[i]
    print str(cnt)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 2568
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>

using namespace std;
typedef long long ll;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int m = max(a, max(b, c));
  
  while (true) {
    if ((3 * m - a - b - c) % 2 == 0) {
      break;
    }
    m++;
  }
  cout << (3 * m - a - b - c) / 2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

typedef long long ll;

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

// const int C ;
// const int M = 1000000007;

int main () {
  int H, W;
  cin >> H >> W;
  string S[100][100];
  for (auto i = 0; i < H; i++) {
    for (auto j = 0; j < W; j++) {
      cin >> S[i][j];
    }
  }
  for (auto i = 0; i < H; i++) {
    for (auto j = 0; j < W; j++) {
      if (S[i][j] == "snuke") {
        cout << (char)('A'+j);
        cout << i+1;
        cout << endl;
        return 0;
      }
    }
  }
}


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

int main () {

	int count=0;
	int i=0;
	int n;
	int l,r;
	cin>>n;

	while (i<n) {
		
		cin>>l>>r;
		count+=r+1-l;

	i++;
	}
	cout<<count<<endl;




}


Measured memory_bytes: 256
import java.util.*;
public class Main{
    static Scanner kbd = new Scanner(System.in);
    public static void main(String[] args){
	int n, m;
	for(n=1; n<=9; n++){
	    for(m=1; m<=9; m++){
		System.out.println(n+"x"+m+"="+n*m);
	    }
	}
    }
}

Measured memory_bytes: 17136
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[5050][5050],rdp[5050][5050];
int main(){
	int n,k;	cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++)	cin>>a[i];
	sort(a.begin(),a.end());
	//dp[i][j]:0〜(i-1)までの要素を用いて和がjになる集合の数
	dp[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<k;j++){
			if(dp[i][j]==0)	continue;
			dp[i+1][j]=1;
			if(j+a[i]<k)	dp[i+1][j+a[i]]=1;
		}
	}
	//rdp[i][j]:i〜(n-1)までの要素を用いて和がjになる集合の数
	rdp[n][0]=1;
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<k;j++){
			if(rdp[i+1][j]==0)	continue;
			rdp[i][j]=1;
			if(j+a[i]<k)	rdp[i][j+a[i]]=1;
		}
	}
	for(int i=n-1;i>=0;i--){
		if(a[i]>=k)	continue;
		bool flag=true;
		if(i==n-1){
			for(int j=k-a[i];j<k;j++){
				if(dp[i][j]!=0){
					flag=false;
					break;
				}
			}
		}
		else if(i==0){
			for(int j=k-a[i];j<k;j++){
				if(rdp[1][j]!=0){
					flag=false;
					break;
				}
			}
		}
		else{
			int sum=0;
			//[k-a[i],k-1]に無ければ不要
			for(int j=0;j<k;j++){
				sum+=rdp[i+1][j];
				if(j>=a[i])	sum-=rdp[i+1][j-a[i]];
				if(sum!=0&&dp[i][k-j-1]!=0){
					flag=false;
					break;
				}
			}
		}
		if(flag){
			cout<<i+1<<endl;
			return 0;
		}
	}
	cout<<0<<endl;
	return 0;
}


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

#define int long long

using namespace std;

int d[101][100001];

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

//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    int n, w;
    cin >> n >> w;

    for(int i = 0; i <= n; i++)
        for(int j = 1; j <= 100000; j++)
            d[i][j] = INT_MAX;

    for(int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        for(int j = 1; j <= 100000; j++)
            d[i][j] = min(d[i-1][j], (j-b >= 0 ? d[i-1][j-b]+a : INT_MAX));
    }

    for(int j = 100000; j >= 0; j--) {
        if(d[n][j] <= w) {
            cout << j;
            return 0;
        }
    }

    return 0;
}


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

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

int cnt = 0; 
 for (int i = 0; i < s.size(); i++) {
   if (s[i] == 'o') {
     cnt++;
   }
 }

 cout << 700 + cnt * 100 << endl;
}


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

template<typename T> long long inversion_number_aux(vector<T> &v, int l, int r, vector<T> &tmp) {
	if (r - l <= 1) return 0;
	long long res = 0;
	const int half = (l + r) / 2;
	res += inversion_number_aux(v, l, half, tmp);
	res += inversion_number_aux(v, half, r, tmp);
	for (int i = l, j = half, k = l; k < r; k++) {
		bool right;
		if (i == half) right = true;
		else if (j == r) right = false;
		else right = v[j] < v[i];

		if (right) tmp[k] = v[j++];
		else {
			tmp[k] = v[i++];
			res += j - half;
		}
	}
	for (int i = l; i < r; i++) {
		v[i] = tmp[i];
	}
	return res;
}

template<typename T> long long inversion_number(vector<T> v) {
	vector<T> tmp(v.size());
	return inversion_number_aux<T>(v, 0, v.size(), tmp);
}

int main() {
	int n;
	cin >> n;
	vector<int> p(n), p0, p1;
	for (int i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		p[i]--;
		if (p[i] % 2 != i % 2) {
			cout << "No" << endl;
			return 0;
		}
		if (i % 2 == 0) p0.push_back(p[i]);
		else p1.push_back(p[i]);
	}
	long long inv = inversion_number(p);
	if (inv % 3 != 0 || inv / 3 != inversion_number(p0) + inversion_number(p1)) {
		cout << "No" << endl;
	} else cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 7856
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

class unionfind{
    private:
    std::vector<int> UF,rank;
    public:
    
    void init(int N){
        UF.clear();
        rank.clear();
        for(int i=0;i<N;i++){
            UF.push_back(i);
            rank.push_back(0);
        }
    }
    
    int root(int k){
        if(UF[k]==k){
            return k;
        }else{
            UF[k]=root(UF[k]);
            return UF[k];
        }
    }
    
    bool same(int p,int q){
        return root(p)==root(q);
    }
    
    void unite(int P,int Q){
        int p=root(P);
        int q=root(Q);
        if(p==q)return;
        if(rank[p]<rank[q])std::swap(p,q);
        UF[q]=p;
        if(rank[p]==rank[q])rank[p]++;
    }
    
};


signed main(void){
    int N,M,K;
    int A[114514],B[114514],C[114514],D[114514];
    cin >> N >> M >> K;
    REP(i,M){
        cin >> A[i] >> B[i];
        A[i]--;B[i]--;
    }
    REP(i,K){
        cin >> C[i] >> D[i];
        C[i]--;D[i]--;
    }
    
    unionfind UF;
    UF.init(N);
    REP(i,M){
        UF.unite(A[i],B[i]);
    }
    
    int ne[114514]={};
    int Ans[114514]={};
    
    REP(i,N){
        ne[UF.root(i)]++;
    }
    REP(i,N){
        Ans[i]=ne[UF.root(i)];
        Ans[i]--;
    }
    REP(i,M){
        if(UF.same(A[i],B[i])){
            Ans[A[i]]--;
            Ans[B[i]]--;
        }
    }
    REP(i,K){
        if(UF.same(C[i],D[i])){
            Ans[C[i]]--;
            Ans[D[i]]--;
        }
    }
    
    
    
    REP(i,N){
        cout << Ans[i];
        if(i!=N-1)cout << " ";
    }cout << endl;
    
    return 0;
}



Measured memory_bytes: 7916
#[allow(unused_imports)]
use std::cmp;
#[allow(unused_imports)]
use std::collections::*;
use std::usize;
#[allow(unused_imports)]
use std::vec::Vec;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: usize,
        k: usize,
        h: [usize; n],
    }
    let mut h = h;
    h.sort();
    let mut min = usize::MAX;
    for i in 0..n - k + 1 {
        let diff = h[i + k - 1] - h[i];
        if min > diff {
            min = diff;
        }
    }
    println!("{}", min)
}


Measured memory_bytes: 4352