akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>


#define fs first
#define sc second

using namespace std;

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

int N, Q;
char t[210000], d[210000];
string s;

bool can_l(int x){
    for(int i = 0; i < Q; i++){
        if(t[i] == s[x]){
            if(d[i] == 'L'){
                x--;
            }
            else{
                x++;
            }
        }
        if(x < 0){
            return true;
        }
    }
    return false;
}

bool can_r(int x){
    for(int i = 0; i < Q; i++){
        if(t[i] == s[x]){
            if(d[i] == 'L'){
                x--;
            }
            else{
                x++;
            }
        }
        if(x >= N){
            return true;
        }
    }
    return false;
}


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

    for(int i = 0; i < Q; i++){
        cin >> t[i] >> d[i];
    }

    int l1 = 0, r1 = N;
    while(r1 - l1 > 1){
        int x = (l1 + r1) / 2;
        if(can_l(x)){
            l1 = x;
        }
        else{
            r1 = x;
        }
    }
    if(l1 == 0 && !can_l(l1)){
        l1--;
    }

    int l2 = -1, r2 = N-1;
    while(r2 - l2 > 1){
        int x = (l2 + r2) / 2;
        if(can_r(x)){
            r2 = x;
        }
        else{
            l2 = x;
        }
    }
    if(r2 == N-1 && !can_r(r2)){
        r2++;
    }

    // cout << l1 << " " << r2 << endl;

    if(l1 >= r2){
        cout << 0 << endl;
    }
    else{
        cout << N - (l1 + 1 + N - r2) << endl;
    }



    return 0;
}


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

using namespace std;

vector<int> dp[21][21];
array<int, 2> prv[1 << 20][21];
int ans[21][1 << 20];

void precalc() {
   for (int mask = 0; mask < 1 << 20; ++mask) {
      prv[mask][0] = {-1, -1};
      for (int i = 1; i <= 20; ++i) {
         prv[mask][i] = prv[mask][i - 1];
         prv[mask][i][((mask >> (i - 1)) & 1)] = i - 1;
      }
   }
}

void print(int len, int mask) {
   for (int i = len - 1; i >= 0; --i) {
      cout << ((mask >> i) & 1);
   }
}

char str[1 << 20];

int main() {
   ios_base::sync_with_stdio(false);
   precalc();
   int N, K;
   scanf("%d %d", &N, &K);
   for (int len = 0; len <= N; ++len) {
      for (int cur = 0; cur <= len; ++cur) {
         dp[len][cur].assign(1 << len, 0);
      }
   }
   for (int len = 0; len <= N; ++len) {
      scanf(" %s", str);
      for (int mask = 0; mask < 1 << len; ++mask) {
         dp[len][len][mask] = str[mask] - '0';
      }
   }
   for (int len = N; len >= 0; --len) {
      for (int cur = len; cur >= 0; --cur) {
         for (int mask = 0; mask < 1 << len; ++mask) {
            if (!dp[len][cur][mask]) continue;
            ans[len - cur][mask >> cur] += dp[len][cur][mask];
            for (int z = 0; z < 2; ++z) if (prv[mask][cur][z] != -1) {
               int nxt = prv[mask][cur][z];
               int delt = cur - nxt - 1;
               int tail = mask & ((1 << (nxt + 1)) - 1);
               int head = mask >> cur;
               int nmask = head << (nxt + 1) | tail;
               dp[len - delt][nxt][nmask] += dp[len][cur][mask];
            }
         }
      }
   }
   for (int len = N; len >= 0; --len) {
      for (int mask = 0; mask < 1 << len; ++mask) {
         if (ans[len][mask] >= K) {
            for (int i = len - 1; i >= 0; --i) {
               cout << (mask >> i & 1);
            }
            return 0;
         }
      }
   }
}


Measured memory_bytes: 385792
N=gets.chomp.to_i
a={}
N.times{
  t=gets.chomp.to_i
  if a[t]==nil then
    a[t]=1
  else
    a[t]+=1
  end
}
a.each{|k,v|
  a.delete(k) if v%2==0  
}
puts a.size


Measured memory_bytes: 10620
#include <iostream>

using namespace std;

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

int lcm(int a, int b)
{
  return a / gcd(a, b) * b;
}

int main()
{
  int a, b;

  while(cin>>a>>b){
    cout << gcd(a, b) << " " << lcm(a, b) << endl;
  }

  return 0;
}

Measured memory_bytes: 1160
//??\??????1????????¶????±?????????????d???????????????????????´???d????????¨??????2????????¶????????????????????????????¨???????????????????????????´????????????????????????
//?????????
//?????¶??¨??¶?????´??????x?????????y???????????´??°??§????????¨?????????????????????????????¢??§?????????
//????????\?????§???
//?????´??????????????????????????¶??¨??¶????????¶?????¨?????´?????????????????¢??????1??\???????????????????????????????????¢??§?????????
//?????´????????????????????????????????¶??¨??¶????????¶?????¨?????´?????????????????¢??????1???????????¨???????????§???????????¢ + 1??§?????????
//??????????????????????????¢??§?????????????????????????????????x?????? = y???????????´???????§?????????¢???d???2
//??????????????????????????????????????????2??????????????????
//
//???d * sqrt(2.0)??¨????????¨????????????sqrt(d * 2.0)??¨???????????????????????§2?????????????????????kiresou
//
//????¨????x?????????0?????????y?????????0?????¨????????????2?????????????????????????????????
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

double getDist(double diffx, double diffy) {
	double epx = max(diffx - (int)diffx, (int)diffx - diffx);
	double epy = max(diffy - (int)diffy, (int)diffy - diffy);
	if (epx > 1e-12 && epy > 1e-12)	//??????????????´??°??§??????
		return diffx + diffy;
	//diffx?????´??°
	if (epx <= 1e-12) {
		//y?????????1??????
		if (diffy < 1)
			return max(diffx, diffy) + 1;
		//y?????????1??\???
		return diffx + diffy;
	}
	//diffy?????´??°
	else {
		//x?????????1??????
		if (diffx < 1)
			return max(diffx, diffy) + 1;
		//y?????????1??\???
		return diffx + diffy;
	}
}

int main() {
	double d, ans = 0;
	cin >> d;
	for (double diffx = 1; diffx <= d; diffx++) {
		double diffy = sqrt(d * d - diffx * diffx);
		ans = max(ans, getDist(diffx, diffy));
	}
	ans = max(ans, d * sqrt(2.0));
	
	printf("%.14f\n", ans);
	return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
using namespace std;
 
int a, b, c, d, hasil;
 
int main () {
cin >> a >> b >> c;
d=a-b;
if ((d>c)||(d==c)) {
     hasil=0;
     cout << hasil << endl;
 
}else{
     hasil=c-d;
     cout << hasil << endl;
}
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a < b) ? (a = b, 1) : 0;}
template<class T>bool chmin(T &a, const T &b) { return (b < a) ? (a = b, 1) : 0;}

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

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

// Problem Specific Parameter:

int main(void) {
	int n, k;
	cin >> n >> k;

	ll ans = 0LL;
	for (int b = k + 1; b <= n; ++b) {
		for (int a = k; a <= n; a += b) {
			const int lower = a;
			const int upper = min(a - k + b, n + 1);
			ans += upper - lower;
		}
	}

	if (k == 0) ans -= n;

	cout << ans << endl;

	return 0;
}

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

int main(){
    int N; cin >> N;
    int C[550], S[550], F[550];
    for(int i=0; i<N-1; i++){
        cin >> C[i] >> S[i] >> F[i];
    }

    //
    for(int i=0; i<N; i++){
        int now=0;
        for(int j=i; j<N-1; j++){
            if(now<S[j]){
                now=S[j];
            }
            else{
                now = (now+F[j]-1)/F[j] * F[j];
            }
            now +=C[j];

        }
        cout << now << endl;
    }
}

Measured memory_bytes: 256
// AOJ 0525 Osenbei
// 2017.11.12 bal4u
// 2018.3.8 use bitset

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

char buf[20010];

int main()
{
	int r, c, i, j, k, s, lim, cnt, ans;
	char *p;

	while (fgets(p=buf, 20, stdin) && *p != '0') {
		sscanf(p, "%d%d", &r, &c);
		
bitset <10002> b[10];

		for (j = 0; j < r; j++) {
			fgets(p=buf, 20010, stdin);
			for (i = 0; i < c; i++) b[j][i] = *p & 1, p+=2;
		}

bitset <10002> a[10];

		ans = 0; lim = 1 << r;
		for (k = 0; k < lim; k++) {
			for (j = 0; j < r; j++) a[j] = b[j];
			for (j = 0; j < r; j++) if (k & (1<<j)) a[j].flip(); 

			cnt = 0;
			for (i = 0; i < c; i++) {
				s = 0;
				for (j = 0; j < r; j++) s += a[j][i];
				if (s < r-s) s = r-s;
				cnt += s;
			}
			if (cnt > ans) ans = cnt;
		}
		printf("%d\n", ans);
	}
	return 0;
}



Measured memory_bytes: 3160
#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 main() {
    int N;
    cin >> N;
    vector<int> B(N);
    rep(i,N-1) cin >> B.at(i);
    int ans = 0;

    rep(i,N) {
        if (i == 0) {
            ans += B.at(0);
        } else if (i == N - 1) {
            ans += B.at(N - 2);
        } else {
            ans += min(B.at(i), B.at(i - 1));
        }
    }
    cout << ans << endl;
}


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

int cd(int a, int b, int k){
    int count = 0;
    int i;
    int list[100];
    int u = max(a,b);
    for(i=1;i<=u; i++){
        if(a%i==0&&b%i==0){
          count++;
          list[count]=i;
        }
    }
    return list[count-k+1];
}

int main(){
    int a,b,k;
    int count;
    cin >> a >> b >>k;
    cout << cd(a,b,k);
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong(); // 1
		long b = sc.nextLong(); // 0
		long c = sc.nextLong(); // -1
		long k = sc.nextLong();

		if (a >= k) {
			System.out.println(k);
		} else if (a + b >= k) {
			System.out.println(a);
		} else {
			long ans = a + b - k + a;
			System.out.println(ans);
		}
	}
}
 
 
 
 
 
 
 
 
 
 


Measured memory_bytes: 35620
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main()
{
	int x,h;
	while(1)
	{
		cin >> x >> h;
		if(x==0&&h==0)break;
		double t;
		t = sqrt((((double)x)/2.0)*(((double)x)/2.0)+(double)(h*h));
		double ans=0.0;
		ans += x*x;
		ans += double(x)*t*2;
		printf("%.6f\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
const ll mod = 1e9 + 7;
int main()
{
	SPEED
	int n;
	cin >> n;
	int ht[n];
	unordered_map<int, int> freq;
	ll ans = 0;

	for (int i = 0; i < n; ++i)
	{
		cin >> ht[i];
		freq[i - ht[i]]++;
	}

	for (int i = 0; i < n; ++i)
	{
		ans += freq[i+ht[i]];	
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 19312
#include <iostream>

#define N 100001
typedef long long int ll;

using namespace std;

int main(int argc, char *argv[]) {
  int n;
  ll a, b;
  ll x[N];
  cin >> n >> a >> b;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
  }

  ll ans = 0;
  for (int i = 0; i < n - 1; i++) {
    ll dist = x[i + 1] - x[i];
    ans += min(dist * a, b);
  }
  std::cout << ans << std::endl;
  return 0;
}


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

int main() {
  int n;
  cin>>n;
  bool ans=false;
  for(int i=0;i<n;i++){
    long long l;
    cin>>l;
      if(l%2==1)ans=true;
  }
  if(ans)cout<<"first"<<endl;
  else cout<<"second"<<endl;
}


Measured memory_bytes: 384
# -*- coding: utf-8 -*-
# 整数の入力
a = raw_input()
flags = 0
flage = 0
for s in a:
	if s == 'C':
		flags = 1
	if flags == 1 and s == 'F':
		flage = 1

if flage == 1:
	print 'Yes'
else:
	print 'No'

Measured memory_bytes: 2696
#include <iostream>
using namespace std;
int main() 
{
	string s ;
	cin>>s ;
	for (int i=0 ; i<s.length(); i++)
	{
		if(s[i]!=',')
		{
			cout<<s[i] ;   }
		else 
		{
			cout<<" " ;  
		}
	}
return 0 ;


}

Measured memory_bytes: 256
import java.io.DataInputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

	// invoked from main
	private void solve() throws Exception {
		int N = in.i(), K = in.i();
		ArrayList<Long> V = new ArrayList<>(N);
		for (int i = 0; i < N; i++)
			V.add(in.l());

		long maxsum = 0;
		ArrayList<Long> list = new ArrayList<>(K);
		for (int a = 0; a <= Math.min(N, K); a++) { // ここ K -> min(N, K)
			int b = Math.min(a, K-a);
			for (int l = 0; l <= a; l++) {
				int r = a - l;
				list.clear();
				for (int i = 0; i < l; i++) {
					list.add(V.get(i));
				}
				for (int i = 1; i <= r; i++) {
					list.add(V.get(N-i));
				}
				Collections.sort(list);
				long sum = list.stream().reduce(0L, (x, y) -> x + y);
				for (int i = 0; i < b; i++) {
					if (list.get(i) < 0) {
						sum -= list.get(i);
					} else {
						break;
					}
				}

				if (sum > maxsum) {
					maxsum = sum;
				}
			}
		}
		out.println(maxsum);
	}


	public static void main(String[] args) throws Exception {
		instance.solve();
	}

	static PrintStream out = System.out;
	static FastReader in = new FastReader();
	static Main instance = new Main();
}

class FastReader {
	final private int BUF_SIZE = 1 << 16;
	private DataInputStream din = new DataInputStream(System.in);
	private byte[] buffer = new byte[BUF_SIZE];
	private int bufferPointer, bytesRead;

	String s() throws IOException {
		return s(64);
	}

	// make for line
	String s(int capacity) throws IOException {
		byte[] buf = new byte[capacity];
		int cnt = 0, c;
		while ((c = c()) != -1) {
			if (Character.isSpaceChar(c)) break;
			buf[cnt++] = (byte) c;
		}
		return new String(buf, 0, cnt);
	}

	int i() throws IOException {
		int ret = 0;
		byte c = c();
		while (c <= ' ') c = c();
		boolean neg = (c == '-');
		if (neg) c = c();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = c()) >= '0' && c <= '9');
		return neg ? -ret : ret;
	}

	long l() throws IOException {
		long ret = 0;
		byte c = c();
		while (c <= ' ') c = c();
		boolean neg = (c == '-');
		if (neg) c = c();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = c()) >= '0' && c <= '9');
		return neg ? -ret : ret;
	}

	double d() throws IOException {
		double ret = 0, div = 1;
		byte c = c();
		while (c <= ' ') c = c();
		boolean neg = (c == '-');
		if (neg) c = c();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = c()) >= '0' && c <= '9');
		if (c == '.')
			while ((c = c()) >= '0' && c <= '9')
				ret += (c - '0') / (div *= 10);
		return neg ? -ret : ret;
	}

	private void fillBuffer() throws IOException {
		bytesRead = din.read(buffer, bufferPointer = 0, BUF_SIZE);
		if (bytesRead == -1) buffer[0] = -1;
	}

	byte c() throws IOException {
		if (bufferPointer == bytesRead) fillBuffer();
		return buffer[bufferPointer++];
	}
}



Measured memory_bytes: 28372
import java.util.Arrays;
import java.util.Scanner;

class Main {

	Scanner sc = new Scanner(System.in);
	final static long LNF = 1L << 60;
	final static double EPS = 1e-9;

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		int n = ni();
		int m = ni();
		int c = ni();

		int[] b = new int[m];
		for (int i = 0; i < m; i++) {
			b[i] = ni();
		}

		int ans = 0;
		for (int i = 0; i < n; i++) {
			int total = 0;
			for (int j = 0; j < m; j++) {
				int a = ni();
				total += b[j] * a;
			}
			if (total + c > 0) {
				++ans;

			}

		}
		System.out.println(ans);
	}

	int ni() {
		return Integer.parseInt(sc.next());
	}

	long nl() {
		return sc.nextLong();
	}

	double nd() {
		return Double.parseDouble(sc.next());
	}

	void debug(Object... os) {
		System.out.println(Arrays.deepToString(os));
	}

	static class Util {
		static <T extends Comparable<T>> T max(T a, T b) {
			if (a.compareTo(b) > 0) {
				return a;
			} else {
				return b;
			}
		}

		static <T extends Comparable<T>> T min(T a, T b) {
			if (a.compareTo(b) < 0) {
				return a;
			} else {
				return b;
			}
		}
	}

}


Measured memory_bytes: 21844
package main

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

var sc = bufio.NewScanner(os.Stdin)

func readInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func readString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
	x, y, z := readInt(), readInt(), readInt()

	x, y = y, x
	x, z = z, x

	fmt.Println(x, y, z)
}


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

class union_find {
 private:
  vector<int> parent;
  vector<int> rank;

 public:
  union_find(int n) : parent(n), rank(n) {
    for (int i = 0; i < n; i++) parent[i] = i;
  }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (rank[a] < rank[b]) {
      parent[a] = b;
    } else {
      parent[b] = a;
      if (rank[a] == rank[b]) rank[a]++;
    }
  }
  int find(int a) { return parent[a] == a ? a : parent[a] = find(parent[a]); }
};

int main() {
  int n, m;
  cin >> n >> m;
  union_find uf(n);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    uf.unite(x - 1, y - 1);
  }
  set<int> s;
  for (int i = 0; i < n; i++) s.insert(uf.find(i));
  cout << s.size() << endl;
}


Measured memory_bytes: 5760
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int N = 100005;

int n, mod;
int down[N];
int up[N];
map <int, int> id[N];
vector <int> adj[N], pre[N], suf[N];

void dfs(int u, int p) {
  down[u] = 1;
  for (int v : adj[u]) {
    if (v == p) continue;
    dfs(v, u);
    id[u][v] = pre[u].size();
    down[u] = (1ll * down[u] * (down[v] + 1)) % mod;
    pre[u].push_back(down[u]);
  }
  int cur = 1;
  for (int i = adj[u].size() - 1; i >= 0; i--) {
    int v = adj[u][i];
    if (v == p) continue;
    cur = (1ll * cur * (down[v] + 1)) % mod;
    suf[u].push_back(cur);
  }
  reverse(suf[u].begin(), suf[u].end());
}

void dfs1(int u, int p) {
  up[u] = 1;
  if (p != -1) {
    up[u] = up[p];
    int pos = id[p][u];
    if (pos > 0) {
      up[u] = (1ll * up[u] * pre[p][pos - 1]) % mod;
    }
    if (pos + 1 < suf[p].size()) {
      up[u] = (1ll * up[u] * suf[p][pos + 1]) % mod;
    }
    up[u] = (up[u] + 1) % mod;
  }
  for (int v : adj[u]) {
    if (v == p) continue;
    dfs1(v, u);
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> mod;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  dfs(1, -1);
  dfs1(1, -1);
  for (int i = 1; i <= n; i++) {
    cout << (1ll * up[i] * down[i]) % mod << endl;
  }
  return 0;
}


Measured memory_bytes: 34816
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VL vector<LL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 1e9;
const LL INF = 1e9;

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    /*
    int t,n;
    cin>>t;
    loop(t1,1,t+1)
    {
        int a[n];
        loop(i,0,n) cin>>a[i];
    }
    */

    LL n,k;
    cin>>n>>k;
    LL a[n+1];
    loop(i,1,n+1)
    {
        cin>>a[i];
    }

    LL t[n+1], c = 0, mv, ans = 1;
    memset(t,-1,sizeof(t));
    while(k)
    {
        if(t[ans] != -1)
        {
            mv = c - t[ans];
            k = k % mv;
            memset(t,-1,sizeof(t));
        }
        else
        {
            //cout<<k<<' '<<ans<<'\n';
            t[ans] = c;
            ++c;
            ans = a[ans];
            --k;
        }
    }

    cout<<ans<<'\n';
    /*
    if(f) cout<<"Yes"<<'\n';
    else cout<<"No"<<'\n';
    */

    return 0;
}


Measured memory_bytes: 6780
{-# LANGUAGE BangPatterns #-}
import           Control.Exception           (assert)
import           Control.Monad
import           Control.Monad.Primitive
import qualified Control.Monad.ST            as ST
import qualified Data.Array.IO               as IO
import qualified Data.Array.ST               as ST
import qualified Data.Array.Unboxed          as A
import           Data.Bits
import qualified Data.ByteString.Char8       as BS
import           Data.Char
import           Data.Foldable
import           Data.List
import qualified Data.Map.Strict             as Map
import           Data.Maybe
import qualified Data.Sequence               as Seq
import qualified Data.Set                    as Set
import qualified Data.Vector                 as VB
import qualified Data.Vector.Mutable         as VBM
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as VM
import           Debug.Trace

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine
getIntVec n = V.unfoldrN n (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

readInteger = fst . fromJust . BS.readInteger
readIntegerList = map readInteger . BS.words
getInteger = readInteger <$> BS.getLine
getIntegerList = readIntegerList <$> BS.getLine

inf :: Int
inf = 10^18

main = do
  s <- getLine
  t <- getLine

  let solve "" "" res = res
      solve (x:xs) (y:ys) res | x /= y = solve xs ys (res+1)
                              | otherwise = solve xs ys res

  print $ solve s t 0


Measured memory_bytes: 20100
#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 MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e18;
//const int INF=(1<<30);


int main(){
  string a,b,c;
  cin >> a >> b >> c;

  if(a[a.size()-1] == b[0] && b[b.size()-1] == c[0]){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}



Measured memory_bytes: 256
S=input()

SS=S[::-1]

#print(SS)

if(S!=SS):
    print("No")
    exit()

Slen=int((len(S)-1)/2)
S1=S[:Slen]
SS1=S1[::-1]

if(S1!=SS1):
    print("No")
    exit()
    
Slen=int((len(S)+3)/2)
S1=S[Slen-1:]
SS1=S1[::-1]
#print(S1)
if(S1!=SS1):
    print("No")
    exit()
print("Yes")


Measured memory_bytes: 3064
from collections import defaultdict
N = int(input())
A = map(int,input().split())

s = defaultdict(lambda :0)
b = defaultdict(lambda :0)
for i,a in enumerate(A):
    s[i-a] = s[i-a] + 1
    b[i+a] = b[i+a] + 1

c = 0
for k in s:
    if k in b:
        c += b[k]*s[k]

print(c)

Measured memory_bytes: 120452
#include <iostream>
using namespace std;
 //Compiler version g++ 6.3.0

 int main()
 {
 	int a=0,b=0,c=0,d=0,e=0,k=0;
 	cin >>a>>b>>c>>d>>e>>k;
 	if(e-a <= k) cout<<"Yay!"<<endl;
 	else cout<<":("<<endl;
 }

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

int main(int argc, const char * argv[]) {
    // insert code here...
    int H, W ;
    cin >> H>> W;
    int bin[H+2][W+2];
    //initialize
    for(int i =0;i<H+2;i++){
        for(int j=0;j<W+2;j++){
            bin[i][j]=0;
        }
    }
    for(int i =1;i<H+1;i++){
        for(int j=1;j<W+1;j++){
            char s;
            cin >> s;
            if(s == '.')bin[i][j]=0;
            else bin[i][j]=1;
        }
    }
                                                
    for(int i =1;i<H+1;i++){
        for(int j=1;j<W+1;j++){
            if(bin[i][j]>0){
                cout<<"#";
            }
            else{
            int sum = 0;
            sum = bin[i-1][j-1]+bin[i-1][j]+bin[i-1][j+1]
                    +bin[i][j-1]+bin[i][j+1]
                    +bin[i+1][j-1]+bin[i+1][j]+bin[i+1][j+1];
            cout << sum;
            }

        }
        cout <<endl;
    }
    
    
}


Measured memory_bytes: 256
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

require 'bigdecimal'

N, K = get_ints
A = get_ints

# ax = A.sort.map { |a| [BigDecimal(a), 1, BigDecimal(a)] }
# count = 0
# while count < K
#   value, divided, first = ax.pop
#   value = first / (divided + 1)
#   next_value = [value, divided + 1, first]
#   index = ax.bsearch_index { |a| a[0] >= value }
#   if index.nil?
#     ax.push(next_value)
#   else
#     ax.insert(index, next_value)
#   end
#   count += 1
#   # p ax.map { |a| {value: a[:value].to_f, divided: a[:divided], first: a[:first].to_f} }
# end
#
# puts ax.last[0].ceil

ax = A.sort.map { |a| a.to_f }

high = ax.last.to_i
low = 0
while high - low > 1
  mid = (high + low) / 2

  index = ax.bsearch_index { |a| a > mid }
  count = 0
  ax[index..].each do |a|
    count += (a / mid).ceil - 1
  end

  if count <= K
    high = mid
  else
    low = mid
  end
end

puts high


Measured memory_bytes: 33304
#include<bits/stdc++.h>
using namespace std;
int main()
{
   int n;
   cin>>n;
   map<string,int>mp;
   int maxx=0;
   while(n--)
   {
       string s;
       cin>>s;
       mp[s]++;
       maxx=max(mp[s],maxx);
   }
   map<string,int>::iterator it=mp.begin();
   while(it!=mp.end())
   {
       if(it->second==maxx) cout<<it->first<<endl;
       it++;
   }
}


Measured memory_bytes: 25216
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define ll long long
using namespace std;



int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> edge(n + 1);
	vector<int> high(n + 1);
	vector<bool> highest(n + 1, true);

	for (int i = 1; i <= n; i++) {
		cin >> high[i];
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		if (high[a] == high[b]) {
			highest[a] = highest[b] = false;
		} else if (high[a] > high[b]) {
			highest[b] = false;
		} else {
			highest[a] = false;
		}
	}
	
	int ans = 0;

	for (int i = 1; i <= n; i++) {
		if (highest[i]) ans++;
	}

	printf("%d", ans);


	return 0;
}

Measured memory_bytes: 4052
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int C, N;
	cin >> C >> N;
	vector<string> S(N);
	for (int i = 0; i < N; ++i) {
		cin >> S[i];
	}
	function<bool(int, int)> judge = [&](int i, int j) {
		if (S[i][j] == S[N - i - 1][j] && S[i][j] == S[i][N - j - 1] && S[i][j] == S[N - i - 1][N - j - 1]) return true;
		return false;
	};
	int cnt = 0;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			int x = min(i, N - i - 1), y = min(j, N - j - 1);
			if (x == i && y == j) {
				if (!judge(x, y)) ++cnt;
			}
		}
	}
	int ans = 0;
	if (cnt == 0) ++ans;
	for (int i = 1; i < C; ++i) {
		int D;
		cin >> D;
		for (int j = 0; j < D; ++j) {
			int x, y;
			cin >> x >> y; --x, --y;
			int tx = min(x, N - x - 1), ty = min(y, N - y - 1);
			if (!judge(tx, ty)) --cnt;
			S[x][y] = (S[x][y] == '0' ? '1' : '0');
			if (!judge(tx, ty)) ++cnt;
		}
		if (cnt == 0) ++ans;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3956
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,C,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;


int main(){
    cin>>S;
    S[3] = '8';
    cout<<S<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include<cstring>
#include <algorithm>
using  namespace std;
#define mem(v,x) memset(v,x,sizeof(v))
#define low(x) (x & (-x))
int pos[500010],n,m;

int main() {
    scanf("%d",&n);
    for (int i = 1; i <= n; i++){
       scanf("%d",&m);
       pos[m] = i;
    }
    int len = 1,ans = 5000000;
    for (int i = 1; i < n; i++){
        if (pos[i+1] > pos[i]) len++; else{
            ans = min(ans,n-len);
            len = 1;
        }
    }
    ans = min(ans,n-len);
    printf("%d\n",ans);

    return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll, ll> P;
using VP = vector<P>;
using VVP = vector<VP>;
using VI = vector<ll>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int inf = 1e9 + 7;
const ll INF = 1LL << 61;
const ll mod = 1e9 + 7;

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll i, j;
    ll n, w;
    cin >> n >> w;
    ll k;
    VVI r(4);
    for (i = 0; i <= 3; i++) r[i].pb(0);
    for (i = 0; i < n; i++) {
        ll q, v;
        cin >> q >> v;
        if (i == 0) k = q;
        r[q - k].pb(v);
    }
    for (i = 0; i <= 3; i++) sort(++r[i].begin(), r[i].end(), greater<ll>());
    for (i = 0; i <= 3; i++) {
        for (j = 1; j < r[i].size(); j++) r[i][j] += r[i][j - 1];
    }
    ll ans = 0;
    for (i = 0; i < r[0].size(); i++) {
        for (j = 0; j < r[1].size(); j++) {
            for (ll l = 0; l < r[2].size(); l++) {
                for (ll p = 0; p < r[3].size(); p++) {
                    if (i + j + l + p > n) continue;
                    if (i * k + j * (k + 1) + l * (k + 2) + p * (k + 3) > w) continue;
                    chmax(ans, r[0][i] + r[1][j] + r[2][l] + r[3][p]);
                }
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3668
#include<bits/stdc++.h>
using namespace std;
#define ANSWER(x) cout<<x<<endl
#define debug(x) cout<<#x<<": "<<x
const int BA = 1000;
const int INFTY = (1<<21);
int xg,yg,w,h,gc;
int maps[101][101];
int solve(int ys,int xs);
int main(){
  int tate[2] = {2,4};
  int yoko[2] = {4,2};
  int xs,ys,n;
  int c[101],d[101],x[101],y[101];
  while(1){
    fill(maps[0],maps[101],0);
    cin >> w >> h;
    if(w==0 && h==0)break;
    cin >> xs >> ys >> xg >> yg >> n;
    xs--;ys--;xg--;yg--;
    for(int i=0;i<n;i++){
      cin >> c[i] >> d[i] >> x[i] >> y[i];
      x[i]--;y[i]--;
    }
    for(int i=0;i<n;i++){
      for(int j=y[i];j<y[i]+tate[d[i]];j++){
	for(int k=x[i];k<x[i]+yoko[d[i]];k++){
	  if(j == ys && k == xs)gc = c[i];
	  maps[j][k] = c[i];
	}
      }
    }
    /* for(int i=0;i<h;i++){
       for(int j=0;j<w;j++){
       cout << maps[i][j];
       }
       cout << endl;
       }*///マップ確認用
    if(solve(ys,xs))cout << "OK\n";
    else cout << "NG\n";
  }
}
int solve(int ys,int xs){
  if(xs < 0 || ys < 0 || xs > w-1 || ys > h-1 || maps[ys][xs] == 0 || maps[ys][xs] != gc){
    return 0;
  }
  else if(ys == yg && xs == xg){
    return 1;
  }
  maps[ys][xs] = 0;
  return solve(ys+1,xs) + solve(ys,xs+1)+ solve(ys-1,xs) + solve(ys,xs-1);
}

Measured memory_bytes: 1168
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), i##ed = (b); i <= i##ed; i++)
#define per(i, a, b) for(int i = (a), i##ed = (b); i >= i##ed; i--)
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 100010;
int n, a[N];

template<typename T> void gi(T &x) {
	x = 0; register char c = getchar(), pre = 0;
	for(; c < '0' || c > '9'; pre = c, c = getchar());
	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10ll + (c ^ 48);
	if(pre == '-') x = -x;
}
int main() {
	scanf("%d", &n); rep(i, 1, n + n) scanf("%d", &a[i]);
	sort(a + 1, a + n + n + 1);
	for(int i = 1; i <= n + n; i += 2) a[0] += a[i];
	printf("%d\n", a[0]);
	return 0;
}

Measured memory_bytes: 256
// Winners don't quit and Quitters don't win
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mod 998244353
#define MAX 100005

vll cou;
vll s;
void solve(){
	ll i=2,c=1;
	s.pb(1);
	while(c<=100){
		s.pb(s[c-1]+i);
		i++;
		c++;
	}
}

void prime(ll n){
	ll i,j,c=0;
	while(n%2==0){
		n/=2;
		c++;
	}
	cou.pb(c);
	for(i=3;i*i<=n;i+=2){
		if(n%i==0){
			c = 0;
			while(n%i==0){
				n/=i;
				c++;
			}
			cou.pb(c);
		}
	}
	if(n>2){
		cou.pb(1);
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,i,ans=0;
    cin>>n;
    solve();
    prime(n);
    for(i=0;i<cou.size();++i){
    	ans += upper_bound(s.begin(),s.end(),cou[i]) - s.begin() ;
    }
    cout<<ans;
}

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

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> h(N);
	rep(i, N) cin >> h[i];

	vector<int> dp(N, 0);
	for(int i = 1; i < N; i++) {
		dp[i] = dp[i-1] + abs(h[i] - h[i-1]);
		for(int j = 1; j <= K; j++) {
			if(i - j >= 0)
				dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]));
		}
	}

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

	return 0;
}

Measured memory_bytes: 4016
#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef pair<int,int> P;
string str;
 
void change(int a,int b,int diff){
    char ach  = str[a],bch = str[b];
    int anum,bnum;
 
    anum = ach - 'a';
    bnum = bch - 'a';
    anum += diff;
    bnum += diff;
 
    if(anum >= 26) anum %= 26;
    if(bnum >= 26) bnum %= 26;
    str[a] = bnum + 'a';
    str[b] = anum + 'a';
}
 
int main(){
    int n;
    while(cin >> n,n){
	vector<P> v;
	str.clear();
	int a,b;
	cin >> str;
	for(int i = 0 ; i < n ; i++){
	    cin >> a >> b;
	    v.push_back(P(a,b));
	}
	for(int i = n-1 ; i >= 0 ; i--){   
	    change(v[i].first-1,v[i].second-1,v[i].second-v[i].first);
	}
	cout << str << endl;
    }
    return 0;
}

Measured memory_bytes: 3152
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <iomanip>
#include <numeric>
#pragma region Macros
#define int long long
#define double long double
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int FACT(int a) {
	if (a == 0)
		return 1;
	else
		return a * FACT(a - 1);
}
int nPr(int n, int r) {
	int s = n - r + 1;
	int sum = 1;
	for (int i = s; i <= n; i++)
		sum *= i;
	return sum;
}
//int nCr(int n, int r)
int nCr2(int n, int r) {
	return FACT(n) / (FACT(r) * FACT(n - r));
}
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
//int COUNTDIV(int n) 素因数分解して+1してかける奴
int COUNTDIV2(int n) {
	int ans = 0;
	REP(i, n) {
		if (n % i == 0)
			ans++;
	}
	return ans;
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min, int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}
inline bool PRIMEOR (int x) {
	if (x ==1)
		return false;
	if (x == 2)
		return true;
	if (x%2==0)
		return false;
	double sqrtx = sqrt(x);
	for (int i = 3; i <= sqrtx; i += 2) {
		if (x % i == 0)
			return false;
	}
	return true;
}

using namespace std;
#pragma endregion
signed main() {
	int N,ans=0,x;
	cin >> N;
	rep(i, N) {
		cin >> x;
		while (x % 2 == 0) {
			ans++;
			x /= 2;
		}	
	}
	cout << ans <<endl;
}

Measured memory_bytes: 256
#include"iostream"
using namespace std;
void Bubblesort(int num[], int n);
int main()
{
	int n;
	cin >> n;
	int*num = new int[n];
	int i;
	for (i = 0; i < n; ++i)
		cin >> num[i];
	Bubblesort(num, n);
	return 0;
}
void Bubblesort(int num[], int n)
{
	int i, j;
	int t,k=0;
	for(i=0;i<n;++i)
		for(j=n-1;j>i;--j)
			if(num[j]<num[j-1])
			{
				t = num[j];
				num[j] = num[j - 1];
				num[j - 1] = t;
				k++;
			}
	cout << num[0];
	for (i = 1; i < n; ++i)
		cout << ' ' << num[i];
	cout << endl << k << endl;
}


Measured memory_bytes: 3104
L,R = map(int,input().split())

if R-L>2019 or L>R :
    print(0)
    exit()
if L%2019+(R-L)>=2019 :
    print(0)
    exit()
l1=L%2019
r1=R%2019

ans = (L*(L+1))%2019
for i in range(L%2019,R%2019+1):
    for j in range(L%2019,R%2019+1):
        if i!=j :
            ans = min( (i*j)%2019, ans)

print( ans )

Measured memory_bytes: 9160
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n;
vector<int> E[maxn];
bool dfs(int x, int fa)
{
	int ret = 0;
	for(auto v : E[x])
		if(v != fa)
			ret += dfs(v, x);
	if(ret > 1) 
	{
		puts("First");
		exit(0);
	}
	return !ret;
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; ++i)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	if(dfs(1, 0)) puts("First");
	else puts("Second");
	return 0;
}

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

using namespace std;

int main()
{
	int n,m;
	cin >> n >> m;
	long long students[n][2],checkpoints[m][2];
	int i,j;
	for (i=0;i<n;i++)
	{
		cin >> students[i][0] >> students[i][1];
	}
	for (i=0;i<m;i++)
	{
		cin >> checkpoints[i][0] >> checkpoints[i][1];
	}

	for (i=0;i<n;i++)
	{
		long long min=abs(checkpoints[0][0]-students[i][0]) + abs(checkpoints[0][1]-students[i][1]),index=1;
		for (j=0;j<m;j++)
		{
			long long temp = abs(checkpoints[j][0]-students[i][0]) + abs(checkpoints[j][1]-students[i][1]);
			if (temp<min)
			{
				min = temp;
				index = j+1;
			}
		}
		cout << index << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pb push_back

using namespace std;

const int N=105;

ll n,W,v[N],w[N],mem[N][100100];

ll dp(int pos,int val)
{
    if (pos==n)
    {
        if (val==0)return 0;
        return 1e12;
    }
    if (mem[pos][val]!=-1)return mem[pos][val];
    ll ans=1e12;
    if (val-v[pos]>=0)ans=min(ans,w[pos]+dp(pos+1,val-v[pos]));
    ans=min(ans,dp(pos+1,val));
    return mem[pos][val]=ans;
}

int main()
{
    memset(mem,-1,sizeof mem);
    cin >> n >> W;
    for (int i=0;i<n;i++)
    {
        cin >> w[i] >> v[i];
    }
    ll ans=0;
    for (int i=0;i<=(1e5);i++)
    {
        if (dp(0,i)<=W)ans=max(ans,1ll*i);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 82432
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

template<typename T>
istream& operator>> (istream& is, vector<T> &vec){
    for(T& x: vec) is >> x;
    return is;
}



int main(){
    ll n; cin >> n;
    ll lists[101][101][101];
    fill(lists[0][0], lists[101][0], -1);
    vector<ll> cnt(60001, 0);
    rep(i, 100){
        rep(j, 100){
            rep(k, 100){
                if(lists[i][j][k] != -1){
                    cnt[lists[i][j][k]]++;
                    continue;
                }                
                ll tmp = pow(i+1, 2) + pow(j+1,2) + pow(k+1,2) + (i+1)*(j+1) + (j+1)*(k+1) + (k+1)*(i+1);
                lists[i][j][k] = tmp;
                lists[i][k][j] = tmp;
                lists[j][i][k] = tmp;
                lists[j][k][i] = tmp;
                lists[k][i][j] = tmp;
                lists[k][j][i] = tmp;

                cnt[tmp]++;
            }
        }
    }
    rep(i, n){
        cout << cnt[i+1] << endl;
    }
    return 0;
}

Measured memory_bytes: 11552
/*
Author: CNYALI_LK
LANG: C++
PROG: d.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %d\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<int,int> pii;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
int read(){
	int s=0,base=1;
	char c;
	while(!isdigit(c=getchar()))if(c=='-')base=-base;
	while(isdigit(c)){s=s*10+(c^48);c=getchar();}
	return s*base;
}
int a[102424],n;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int solve(){
	int xs=1,zs;
	while(1){
		zs=0;
		for(int i=1;i<=n;++i)if(a[i]==1)zs=1;
		if(zs){
			for(int i=1;i<=n;++i)xs=xs^((a[i]-1)&1);
			return !xs;
		}
		for(int i=1;i<=n;++i)if(!(a[i]&1))++zs;
		if(zs&1)return xs;
		else if(n-zs>1)return !xs;
		int g=0;
		for(int i=1;i<=n;++i){
			if(a[i]&1)--a[i];
			g=gcd(g,a[i]);
		}
		for(int i=1;i<=n;++i)a[i]/=g;
		xs^=1;
	}
}
int main(){
#ifdef cnyali_lk
	freopen("d.in","r",stdin);
	freopen("d.out","w",stdout);
#endif
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	printf(solve()?"First\n":"Second\n");
	return 0;
}



Measured memory_bytes: 640
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, -1, sizeof(mat))
typedef long long ll;
int N, Z, W;
int a[2222];
int memo[2222][2222][2];
int dp_a[2222], dp_b[2222];
// who -> 1 aが下
int dfs(int ai, int bi, int who) {
  if(memo[ai][bi][who] != -1) return memo[ai][bi][who];
  if(ai == N - 1 || bi == N - 1) return memo[ai][bi][who] = abs(a[ai] - a[bi]);
  if(who == 1) {
    int ret = 1e9;
    if(dp_a[ai] != -1) return memo[ai][bi][who] = dp_a[ai];
    for(int i = N - 1; i > ai; i--) {
      ret = min(ret, dfs(ai, i, -who));
    }
    dp_a[ai] = ret;
    return memo[ai][bi][who] = ret;
  } else {
    int ret = -1e9;
    if(dp_b[bi] != -1) return memo[ai][bi][who] = dp_b[bi];
    for(int i = N - 1; i > bi; i--) {
      ret = max(ret, dfs(i, bi, -who));
    }
    dp_b[bi] = ret;
    return memo[ai][bi][who] = ret;
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> Z >> W;
  FOR(i,2,N+2) cin >> a[i];
  a[0] = Z;
  a[1] = W;
  N += 2;
  CLR(memo);
  CLR(dp_a);
  CLR(dp_b);
  dp_a[N-1] = abs(a[N-1] - W);
  int ans = dfs(0,1,-1);
  cout << ans << endl;
}

Measured memory_bytes: 38912
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void calc(String[] strAry,int n)
	{
		long min=10000000;
		long max=-10000000;
		long sum=0;
		for(int i=0;i<n;i++)
		{
			long tmp=Integer.parseInt(strAry[i]);
			if(min>tmp)min=tmp;
			if(max<tmp)max=tmp;
			sum+=tmp;
		}
		System.out.println(min+" "+max+" "+sum);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str=br.readLine();
		int n=Integer.parseInt(str);
		str=br.readLine();
		String[] strAry =str.split(" ");
		calc(strAry,n);
	}
}

Measured memory_bytes: 28556
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int A = Integer.parseInt(sc.next());
        int B = Integer.parseInt(sc.next());
        int C = Integer.parseInt(sc.next());
        
        if(A + B >= C){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21332
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
P=[0]*(N+1)
T=[0]*(N+1)
for i in range(N):
    P[i+1]=P[i]+A[i]
    if A[i]>=0:
        T[i+1]=T[i]+A[i]
    else:
        T[i+1]=T[i]
a=max(sum(A),0)
for i in range(K,N+1):
    t=P[i]-P[i-K]
    s=T[i-K]-T[0]
    u=T[N]-T[i]
    a=max(a,s+t+u,s+u)
    #print(a,s,t,u)
print(a)

Measured memory_bytes: 67616
//2017-12-23
//miaomiao
//
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)

int main(){
//!
//	freopen("A.in", "r", stdin);
//	freopen("A.out", "w", stdout);

	LL x, y;
	scanf("%lld%lld", &x, &y);

	int ans = 0;

	LL now = x;
	while(now <= y){
		++ans; now <<= 1;
	}

	printf("%d\n", ans);

	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SIZE(a) int((a).size())
const int INF=INT_MAX;

int main(){
  string s,t;
  cin>>s;
  vll n(4);
  REP(i,4){
    n[i]=s[i]-'0';
  }
  REP(i,1<<3){
    bitset<3> a(i);
    int sum=n[0];
    REP(j,3){
      if(a.test(j)){
        sum+=n[j+1];t[j]='+';
      }
      else{
        sum-=n[j+1];t[j]='-';
      }
    }
    if(sum==7){
      cout<<s[0];
      REP(i,3){
        cout<<t[i]<<s[i+1];
      }
      cout<<"=7"<<endl;break;
    }
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<pair<string, string>, int> mp;
int n, rt;
string s;
int32_t main(){
    cin >> n >> s;
    for(int i=0;i<(1<<n);i++){
        string a = "", b = "";
        for(int j=0;j<n;j++){
            if(i&(1LL<<j)) a+=s[j];
            else b+=s[j];
        }
        mp[{a, b}]++;
    }
    for(int i=0;i<(1<<n);i++){
        string a = "", b = "";
        for(int j=0;j<n;j++){
            if(i&(1LL<<j)) a+=s[j+n];
            else b+=s[j+n];
        }
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        rt+=mp[{b, a}];
    }
    cout << rt;
}

Measured memory_bytes: 87040