akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define int long long
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>=0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const double pi = 3.141592653589793;

int n,c10,c50,c100,c500;


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    while (n!=0){
        cin >> c10 >> c50 >> c100 >> c500;
        int cnt=1e9;
        int ans[4]={};
        rep(i,c10+1)rep(j,c50+1)rep(k,c100+1)rep(l,c500+1){
            int m=i*10+j*50+k*100+l*500;
            if (i*10+j*50+k*100+l*500<n) continue;
            int ret=m-n;
            int tmp=0;
            tmp+=ret/500;
            ret-=500*(ret/500);
            tmp+=ret/100;
            ret-=100*(ret/100);
            tmp+=ret/50;
            ret-=50*(ret/50);
            tmp+=ret/10;
            if (c10+c50+c100+c500-(i+j+l+k)+tmp<cnt){
                cnt=c10+c50+c100+c500-(i+j+l+k)+tmp;
                ans[0]=i;ans[1]=j;ans[2]=k;ans[3]=l;
            }
        }
        if (ans[0]>0) cout << "10" << " " << ans[0] << endl;
        if (ans[1]>0) cout << "50" << " " << ans[1] << endl;
        if (ans[2]>0) cout << "100" << " " << ans[2] << endl;
        if (ans[3]>0) cout << "500" << " " << ans[3] << endl;
        cin >> n;
        if (n!=0) cout << endl;
    }

}

Measured memory_bytes: 3156
#include "omp.h"
#include <iostream>
#include <iomanip>
#include <string>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <vector>
#include <cassert>
#include <fstream>
#include <algorithm>
#include <list>
#include <random>
#include <ctime>
#include <random>
#include <bitset>
#include <unordered_set>
#include <cassert>
#include <list>


using namespace std;

typedef long long ll;
typedef long double ld;


const int sze = 51, M = 5e3 + 1, psze = 15;
const ll INF = 1e15;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	vector<ll> values(n);
	
	for (int i = 0; i < n; ++i)
		cin >> values[i];

	for (int i = 0; i < n; ++i)
		values[i] -= i + 1;

	sort(values.begin(), values.end());
	
	vector<ll> cnt(n);
	cnt[0] = values[0];
	for (int i = 1; i < n; ++i)
		cnt[i] += cnt[i - 1] + values[i];

	ll ans = INF;
	for (int i = 0; i < n; ++i)
	{
		ll v = 0;

		int l = -1, r = i + 1;
		while (r - l > 1)
		{
			int m = (l + r) >> 1;

			if (values[m] < 0)
				l = m;
			else
				r = m;
		}

		if (l != -1)
			v += abs(cnt[l] - values[i] * (l + 1)) + abs(cnt[i] - cnt[l] - values[i] * (i - l));
		else
			v += abs(cnt[i] - values[i] * (i + 1));

		v += cnt[n - 1] - cnt[i] - values[i] * (n - 1 - i);
		ans = min(ans, v);
	}

	cout << ans;
	return 0;
}	

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

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

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

/**
 * @brief 多次元 vector の作成
 * @author えびちゃん
 */
namespace detail {
    template<typename T, int N>
    auto make_vec(vector<int>& sizes, T const& x) {
        if constexpr (N == 1) {
            return vector(sizes[0], x);
        } else {
            int size = sizes[N-1];
            sizes.pop_back();
            return vector(size, make_vec<T, N-1>(sizes, x));
        }
    }
}
template<typename T, int N>
auto make_vec(int const(&sizes)[N], T const& x = T()) {
    vector<int> s(N);
    for (int i = 0; i < N; ++i) s[i] = sizes[N-i-1];
    return detail::make_vec<T, N>(s, x);
}

__attribute__((constructor))
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

template<typename T>
struct cumulative_sum_linear {
    int n;
    vector<T> x, a, b;

    cumulative_sum_linear(int n = 0) : n(n), x(n), a(n+1), b(n+1) {}

    void add(int l, int r, T p, T q) {
        a[l] += p;
        a[r] -= p;
        a[l] -= q * l;
        a[r] += q * l;
        b[l] += q;
        b[r] -= q;
    }

    void build() {
        for (int i = 0; i < n; ++i) {
            x[i] = a[i] + b[i] * i;
            a[i+1] += a[i];
            b[i+1] += b[i];
        }
    }

    T operator[](int i) const { return x[i]; }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    rep(i, n) cin >> a[i], a[i]--;

    ll sum = 0;
    cumulative_sum_linear<ll> cnt(2 * m);

    rep(i, n-1) {
        int d = (a[i+1] - a[i] + m) % m;
        sum += d;
        int s = (a[i] + 1) % m;
        cnt.add(s, s + d, 0, 1);
    }

    cnt.build();
    vector<ll> x(m);
    rep(i, m) x[i] = cnt[i] + cnt[i+m];
    cout << sum - *max_element(x.begin(), x.end()) << '\n';
}


Measured memory_bytes: 9008
import sys
sys.setrecursionlimit(10 ** 6)
import sys
def input():
    return sys.stdin.readline()[:-1]
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b
# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue
        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]
        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

Measured memory_bytes: 282972
N = int(input())

if 0 <= N <= 1000:
    print(1000-N)
elif 1000 < N <= 2000:
    print(2000-N)
elif 2000 < N <= 3000:
    print(3000-N)
elif 3000 < N <= 4000:
    print(4000-N)
elif 4000 < N <= 5000:
    print(5000-N)
elif 5000 < N <= 6000:
    print(6000-N)
elif 6000 < N <= 7000:
    print(7000-N)
elif 7000 < N <= 8000:
    print(8000-N)
elif 8000 < N <= 9000:
    print(9000-N)
else:
    print(10000-N)

Measured memory_bytes: 9108
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

#define int long long
#define v first
#define w second

const int N = 200005;
pair<int,int> item[101];
int d[101][100005];
int n, W;

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> W;
	fill(d[0], d[0] + W + 1, LLONG_MIN);
	for(int i = 1 ; i <= n ; i ++){
		cin >> item[i].w >> item[i].v;
		fill(d[i], d[i] + W + 1, LLONG_MIN);
	}
	d[0][0] = 0;
	for(int i = 1 ; i <= n ; i ++)
		for(int j = 0 ; j <= W ; j ++)
			d[i][j] = max(d[i - 1][j], (j - item[i].w >= 0 ? d[i - 1][j - item[i].w] + item[i].v : 0LL));
	cout << *max_element(d[n], d[n] + W + 1);
}


Measured memory_bytes: 79232
#include<iostream>
#include<iostream>
#include<unordered_map>

using namespace std;

int main()
{
  int n;
  cin>>n;
  int a[n];
  long long int sum=0;
  unordered_map<int,int> m;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    m[a[i]]++;
    sum=sum+a[i];
  }
	int q;
  	cin>>q;
  	while(q--)
    {
      int search,val;
      cin>>search>>val;
      if(m[search]!=0){
       sum=sum-((search-val)*m[search]);
       m[val]=m[val]+m[search];
       m[search]=0;
      }
      cout<<sum<<"\n";
    }
}


Measured memory_bytes: 7300
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define     ll          long long int
#define     REP(i,x,n)    for(ll i=x;i<n;i++)
#define     SZ(v)       (ll)v.size()
#define     endl        "\n"
#define     ff          first
#define     ss          second
#define     PQ_MIN      priority_queue <ll, vector<ll>, greater<ll> >
#define     PQ          priority_queue <int>
#define     pbds        tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define     setbit(x)   __builtin_popcount(x)
#define     prec(n)     fixed<<setprecision(n)
#define     pb(n)       push_back(n)
#define     mp(a,b)     make_pair(a,b)
#define     clr(n)      memset(n,0,sizeof(n))
#define     reset(n)    memset(n,-1,sizeof(n))
#define     ii          pair<ll,ll>
#define     vll         vector<ll>
using namespace std;
using namespace __gnu_pbds;
bool comp(pair<ll,ll> a,pair<ll,ll> b) {       }
const ll MOD=1e9+7;
void print(vector<vector<ll> >&v)
{
    ll n=v.size();
    ll m=v[0].size();
    cout<<"\n";
    for(ll i=0;i<n;i++)
    {
        for(ll j=0;j<m;j++)
            cout<<v[i][j]<<" ";
        cout<<"\n";
    }
}
void print(vector<ll>&v)
{
    ll n=v.size();
    cout<<"\n";
    for(ll i=0;i<n;i++)
    {
            cout<<v[i]<<" ";
    }
        cout<<"\n";

}
void print(set<ll>&s)
{

cout<<endl;

set<ll>::iterator it;
for(it=s.begin();it!=s.end();it++)
    cout<<*it<<" ";
cout<<endl;
}
ll __lcm(ll a,ll b)
{
    return ((a*b)/__gcd(a,b));
}
ll power(ll a,ll p)
{
    ll res=1;
    while(p>0)
    {
        if(p&1){
            res=(res*a)%MOD;
            p--;
        }
            a=(a*a)%MOD;
            p/=2;
    }

    return res%MOD;
}
const ll INF=1e16;
const ll nxm=2e5+5;

ll spf[nxm];
void sieve()
{
    memset(spf,-1,sizeof(spf));

    spf[0]=spf[1]=1;

    for(ll i=2;i<nxm;i++)
    {
        if(spf[i]==-1)
            spf[i]=i;
        for(ll j=i*i;j<nxm;j+=i)
        {
            if(spf[j]==-1)
                spf[j]=i;

        }

    }
//    while(x>1)
//    {
//        ll s=spf[x];
//        temp[s]++;
//        x/=s;
//    }


// log n prime factor
}
void solve(){
    
    
    
    
    
    ll n;
    cin>>n;
    
    if(n>=30)
        cout<<"Yes";
    else
        cout<<"No";
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


}
int main(){
//    freopen("timber_input", "r", stdin);
//    freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t=1;
//	cin>>t;
    REP(i,1,t+1)
    {
//    cout<<"Case #"<<i<<": ";
		solve();
    }
	return 0;
}
//  bitset<64>(x).to_ullong() // in my com  _ulong()
//  cout<<bitset<64>(ans).to_string().substr(64-m)<<endl;
/*

char s[100];

fgets(s,100,stdin);

stringstream stram(s);

string abc;

bool ok1=0,ok2=0;

while(stram>>abc)
*/


Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;
int fact(int n)
{
    if(n==0)
        return 1;
        int ans=1;
    for(int i=1;i<=n;i++)
     ans*=i;
     return ans;
}
int find(int n,int m)
{
  int r=fact(n)/(fact(n-m));
  return r;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
int ans=1;
int arr[n];
for(int i=0;i<n;i++)
    cin>>arr[i];
    int mod=pow(10,9)+7;
    map<int,int> mp;
    mp[-1]=1;
for(int i=0;i<n;i++)
{
    int x=arr[i];
    int val=mp[x-1];
    ans*=val;
    ans%=mod;
    mp[x]+=1;
    if(x-1!=-1&&mp[x-1])
    mp[x-1]-=1;
}
int r=0;
for(int i=0;i<n;i++)
{
    if(arr[i]==0)
        r++;
}
if(r<=3)
ans*=find(3,r);
else
    ans=0;
ans%=mod;
cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 10572
#include <stdio.h>


typedef long value_type;

value_type med3(value_type x, value_type y, value_type z) {
    if (x < y) {
        if (y < z) return y; else if (z < x) return x; else return z;
    } else {
        if (z < y) return y; else if (x < z) return x; else return z;
    }
}

void quicksort(value_type a[], int left, int right) {
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]);
        while (1) {
            while (a[i] < pivot) i++;
            while (pivot < a[j]) j--;
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp;
            i++; j--;
        }
        quicksort(a, left, i - 1);
        quicksort(a, j + 1, right);
    }
}

int main(void) {
	int n, k, i;
	long h[200001];
	long long sum;

	scanf("%d %d", &n, &k);
	for(i = 0; i < n; i++) {
		scanf("%ld", h + i);
	}

	quicksort(h, 0, n - 1);
	for(i = 0; i < n - k; i++) {
		sum += h[i];
	}

	printf("%lld\n", sum);

	return 0;
}


Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <iomanip>
#include <vector>
#include <functional>
#include <algorithm>
#include <cstdio>
#include <random>
#include <ctime>
#include <cstdlib>
#include <unordered_map>
#include <string.h>
#include <iostream>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    if (k % 2 == 0)
    {
        cout << a - b << endl;
    }
    else
    {
        cout << b - a << endl;
    }
}

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

template <class Abel>
struct BIT
{
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0; // to be set

    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n)
    {
        for (int iter = 0; iter < 2; ++iter)
            dat[iter].assign(n + 1, UNITY_SUM);
    }

    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x)
    {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x)
    {
        sub_add(0, a, x * -(a - 1));
        sub_add(1, a, x);
        sub_add(0, b, x * (b - 1));
        sub_add(1, b, x * (-1));
    }

    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a)
    {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i)
            res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b)
    {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }

    /* debug */
    void print()
    {
        for (int i = 1; i < (int)dat[0].size(); ++i)
            cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i];

    vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i)
    {
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) { return rights[i] < rights[j]; });

    BIT<int> bit(N + 5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids)
    {
        for (; r < rights[i]; ++r)
        {
            bit.add(prev[a[r]] + 2, r + 2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i] + 1, lefts[i] + 2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i)
        cout << res[i] << endl;
}

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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/2;
    public static final int inf = Integer.MAX_VALUE/2;

    static void solve(InputReader in, PrintWriter out){
        int a = in.ni(), b = in.ni(), c = in.ni(), d = in.ni();
        int ta = (a+d-1)/d, ao = (c+b-1)/b;
        if(ta>=ao)out.println("Yes");
        else out.println("No");
    }

    public static void main(String[] args){
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public double nd(){
            return Double.parseDouble(ns());
        }
        public char nc(){
            return ns().toCharArray()[0];
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 32756
using System;
using System.Collections.Generic;
using System.Linq;
 
class ARemainingBalls {
    static void Main(string[] args) {
        string[] st = System.Console.ReadLine().Trim().Split(' ');
        int[] ab = Console.ReadLine().Trim().Split(' ').Select(a => int.Parse(a)).ToArray();
        string u = System.Console.ReadLine();
        if (u.Equals(st[0])) {
            System.Console.Write(ab[0] - 1);
        } else {
            System.Console.Write(ab[0]);
        }
            System.Console.Write(" ");
        if (u.Equals(st[1])) {
            System.Console.WriteLine(ab[1] - 1);
        } else {
            System.Console.WriteLine(ab[1]);
        }
    }
}

Measured memory_bytes: 13268
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int c[110000];
vector<int>g[110000];
int dfs(int a,int b){

	for(int i=0;i<g[a].size();i++){
		if(g[a][i]==b)continue;
		if(c[a]<=c[g[a][i]])continue;
		if(dfs(g[a][i],a)==0)return 1;
	}
	return 0;
}
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=0;i<a-1;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
	}
	for(int i=0;i<a;i++){
		int ret=dfs(i,-1);
		if(ret==1)printf("%d ",i+1);
	}printf("\n");
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	string s; cin>>s;
	vector<int>cnt(s.size()+1,0);
	for(int i=0;i<s.size();++i){
		if(s.at(i)=='A'||s.at(i)=='C'||s.at(i)=='G'||s.at(i)=='T'){
			cnt.at(i+1)=cnt.at(i)+1;
		}
	}
	cout<<*max_element(cnt.begin(),cnt.end())<<"\n"s;
}

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

int main (void) {
    long long i;
    int units_digits;
    int j;
    int k;

    scanf("%d", &k);

    long long queue[100001];
    int queue_last = 10;

    /* 初期値 */
    for ( i=1; i<=9; i++ )
        queue[i] = i;
    if ( k <= 9 )
        goto END;
    /* 実処理 */
    for ( i=1; ; i++ ) {
        units_digits = queue[i] % 10;
        for ( j=units_digits-1; j<=units_digits+1; j++ ) {
            if ( j == -1 || j >= 10 )
                continue;
            queue[queue_last] = queue[i] * 10 + j;
            if ( queue_last == k )
                goto END;
            queue_last++;
        }
    }
END:
    printf("%lld\n", queue[k]);
    return EXIT_SUCCESS;
}


Measured memory_bytes: 896
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int result[] = new int[26];
        for(int i = 0 ; i < 26 ; i++)
            result[i] = 0;
        while(sc.hasNext())
        {
            String str = sc.next();
            str = str.toLowerCase();
            for(int i = 0 ; i < str.length() ; i++)
            {
                char c = str.charAt(i);
                if(c >= 'a' && c <= 'z')
                    result[c - 'a']++;
            }
        }
        for(char ch = 'a' ; ch <= 'z' ; ch++)
        {
            System.out.println(ch + " : " + result[ch - 'a']);
        }
    }
}


Measured memory_bytes: 26336
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define size(v) v.size()

const int N=100005;
const int MOD=1e9+7;

 

// lower_bound - which does not compare less than val
// upper_bound - which compares greater than val
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define printclock cerr<<"Time : "<<1000*(int)clock()/(int)CLOCKS_PER_SEC<<"ms\n"
int32_t main()
{
  
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  /* stuff you should look for
  * int overflow, array bounds
  * special cases (n=1?)
  * do smth instead of nothing and stay organized
*/





int n;
cin>>n;
int count[N]={0};
int sum=0;
for(int i=0;i<n;i++)
{
	int x;
	cin>>x;
	count[x]++;
	sum+=x;
	
}
int q;
cin>>q;
while(q--)
{
	int a,b;
	cin>>a>>b;
	sum+=(b-a)*count[a];
	count[b]+=count[a];
	count[a]=0;
	cout<<sum<<" ";
	
	
	

}

cout<<endl;
printclock;
}




Measured memory_bytes: 4420
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn = 100100;
int arr[maxn], n;

int main() {
    cin>>n;
    for(int i=0;i<n;i++) {
        cin>>arr[i];
    }
    sort(arr, arr+n);

    int midpointl = 0;
    int midpointr = 0;

    if(arr[n-1] % 2) {
        midpointl = (arr[n-1] + 1) / 2;
        midpointr = midpointl + 1;
    }
    else {
        midpointl = midpointr = (arr[n-1] + 1) / 2;
    }

    int min_dist = INT_MAX;
    int index = 0;


    for(int i=0;i<n-1;i++) {
        if(arr[i] <= midpointl) {
            if(abs(midpointl - arr[i]) < min_dist) {
                min_dist = abs(midpointl - arr[i]);
                index = arr[i];
            }
        }
        else if(arr[i] > midpointr) {
            if(abs(arr[i] - midpointr) < min_dist) {
                min_dist = abs(arr[i] - midpointr);
                index = arr[i];
            }
        }
    }

    cout<<arr[n-1]<<" "<<index<<"\n";
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;



int main(){
		
		int a,b;
		cin>>a>>b;
		int arr [200000];
		for(int i=0;i<b;i++)cin>>arr[i];
		sort(arr,arr+b);
		int dis=a-(arr[b-1]-arr[0]);
		for(int i=1;i<b;i++)dis=max(dis,arr[i]-arr[i-1]);
		int ans=a-dis;
		cout<<ans<<endl;		
		return 0;
}

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

int main() {
	string s, t;
	cin >> s >> t;
	int ans = 0;
	rep(i, s.size()) if (s[i] == t[i]) ans++;
	cout << ans << endl;
	return 0;
}


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

int main(){
    int n, m;
    std::string s;
    std::cin >> n >> m >> s;
    std::reverse(s.begin(), s.end());
    int now = 0;
    std::vector<int> vec;
    while(1){
        if(now+m >= n){
            vec.push_back(n-now);
            break;
        }
        int prog = m;
        while(s[now+prog] - '0'){
            prog--;
            if(prog <= 0){
                std::cout << -1 << std::endl;
                return 0;
            }
        }
        vec.push_back(prog);
        now += prog;
    }
    std::reverse(vec.begin(), vec.end());
    for(int i : vec){
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}


Measured memory_bytes: 1144
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define llint long long

using namespace std;

int n, Q;
vector<llint> G[200005];
llint val[200005], ans[200005];

void dfs(llint v, llint p, llint s)
{
	s += val[v];
	ans[v] = s;
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == p) continue;
		dfs(G[v][i], v, s);
	}
}

int main(void)
{
	cin >> n >> Q;
	llint u, v;
	for(int i = 0; i < n-1; i++){
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	llint p, x;
	for(int q = 0; q < Q; q++){
		cin >> p >> x;
		val[p] += x;
	}
	
	dfs(1, -1, 0);
	
	for(int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl;
	
	return 0;
}

Measured memory_bytes: 28672
#pragma GCC optimize("O2,Ofast,inline,unroll-all-loops,-ffast-math")
using namespace std;
#include <bits/stdc++.h>
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb(X) push_back(X)
#define x first
#define y second
#define all(x) (x).begin(), (x).end()
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
typedef long long ll;
typedef vector<int> VI;
typedef vector<long long> VL;
typedef pair<int, int> pii;
//ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}


const int INF = 1e9 + 7;
int _, a[200005];

int main() {
	INIT
	int n;
	cin >> n;
	rep (i, 2, n + 1) {
		int t;
		cin >> t;
		a[t]++;
	}
	rep (i, 1, n + 1) {
		cout << a[i] << '\n';
	}
	
	


	return 0;
}

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


struct Node{
    ll pos;
    ll deep;
    char color;
    
    bool operator< (const Node &r) const{
        if(deep == r.deep){
            if(color == 'B')    return false;
            else if(r.color == 'B'){
                return true;
            }
            else{
                return true;
            }
        }
        else{
            return deep > r.deep;
        }
    }
};

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    rep(i, n-1)   cin >> a[i] >> b[i];
 
    vector<ll> g[n+5];
    rep(i, n-1) g[a[i]-1].push_back(b[i]-1);
    rep(i, n-1) g[b[i]-1].push_back(a[i]-1);
 
    priority_queue<Node> que;
    que.push({0, 0, 'B'});
    que.push({n-1, 0, 'W'});
    vector<char> color(n, 'N');
 
    vector<ll> mid;
    while(!que.empty()){
        Node node = que.top(); que.pop();
 
        if(color[node.pos] != 'N')   continue;
        color[node.pos] = node.color;
 
        for(auto to : g[node.pos]){
            que.push({to, node.deep+1, node.color});
        }
    }
  
    ll bcnt = 0;
    ll wcnt = 0;
    for(auto c : color){
        if(c == 'B')        bcnt++;
        else if(c == 'W')   wcnt++;
    }
 
    if(wcnt < bcnt) cout << "Fennec" << endl;
    else            cout << "Snuke" << endl;
 
    return 0;
}


Measured memory_bytes: 9464
a, b, c = [int(input()) for _ in range(3)]
x = int(input())
count = 0
sum = 0

for i in range(a+1):
    if x < 500*i:
        break
    for j in range(b+1):
        if x < 100*j + 500*i:
            break
        for l in range(c+1):
            sum = i*500 + j*100 + l*50
            if sum == x:
                count = count+1

print(count)


Measured memory_bytes: 3060
# Problem: https://atcoder.jp/contests/abc071/tasks/abc071_b
# Python 2nd Try

import sys
# from collections import defaultdict
# import heapq,copy
# from collections import deque
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def solver(inputStr):
    # print("STR={}".format(inputStr))
    # バケツを用意する
    bucket = [0] * 26
    result = "None"
    # print("Bucket:{}".format(bucket))
    for j in range(0, len(inputStr), +1):
        charNo = ord(inputStr[j]) - ord('a')
        bucket[charNo] = bucket[charNo] + 1
    for j in range(0, 26, +1):
        if bucket[j] == 0:
            result = chr(ord('a')+j)
            break
    # algorithm
    return result
if __name__ == "__main__":
    S = sys.stdin.readline().split()
    print("{}".format(solver(S[0])))


Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

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

    ll N, A, B;
    cin >> N >> A >> B;

    if ((B - A) % 2) {
        if (A - 1 < N - B) {
            ll turn = A - 1;
            cout << turn + 1 + ((B - turn - 1) - 1) / 2 << endl;
        } else {
            ll turn = N - B;
            cout << turn + 1 + (N - (A + turn + 1)) / 2 << endl;
        }
    } else {
        cout << (B - A) / 2 << endl;
    }

    return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n;
int a[252521];
ll dp[252521][6];

int main(){
  scanf("%d",&n);
  REP(i,n)scanf("%d",a+i);
  REP(i,n+1)REP(j,5)dp[i][j] = 1ll<<60;
  dp[0][0] = 0;
  REP(i,n)REP(j,5){
    CHMIN(dp[i][j+1], dp[i][j]);
    if(j==0 || j==4){
      CHMIN(dp[i+1][j], dp[i][j] + a[i]);
    }else if(j==1 || j==3){
      CHMIN(dp[i+1][j], dp[i][j] + (a[i]==0 ? 2 : a[i]%2));
    }else{
      CHMIN(dp[i+1][j], dp[i][j] + (a[i]%2==0 ? 1 : 0));
    }
  }
  ll ans = 1ll<<60;
  REP(j,5)CHMIN(ans, dp[n][j]);
  printf("%lld\n",ans);
  return 0;
}


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

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Solver solver = new Solver();
		solver.init();
		solver.readHead(in.readLine());
		// for (; solver.hasNext();) {
		// solver.readBody(in.readLine());
		// }
		// solver.solve();
	}
}

class Solver {
	int N;
	int cnt;

	public void init() {
		N = 0;
		cnt = 0;
	}

	public void readHead(String str) {
		String[] strArr = str.split(" ");
		N = Integer.parseInt(strArr[0]);
		// System.out.println(N);
		int ans = Integer.MAX_VALUE;
		for (int a = N - 1; a > 0; a--) {
			int ds = digtsum(a) + digtsum(N - a);
			if (ds < ans)
				ans = ds;
		}
		System.out.println(ans);
	}

	private int digtsum(int num) {
		int ans = 0;
		for (int n = num; n > 0; n /= 10) {
			ans += n % 10;
		}
		return ans;
	}

	public boolean hasNext() {
		return cnt < N;
	}

	public void readBody(String str) {
		// System.out.println(str);
		cnt++;
	}

	public void solve() {

	}
}


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

 


int main() {
 int N,W;
  cin >>N>>W;
 vector<int>v(N+1);
 vector<int>w(N+1);
 long int dp[N+1][W+1]; 
  rep(i,N+1){
   rep(j,W+1){
   	dp[i][j]=0;
   }
  }
 rep(i,N){
 cin >> v[i+1] >> w[i+1];
 }
 for(int i=1;i<=N;i++){
 	for(int j=1;j<=W;j++){
    	if(w[i]<=j){
        dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
        }
    	else{dp[i][j]=dp[i-1][j];}
    }
 } 
  long int ans=0;
  rep(i,W+1){
  ans=max(ans,dp[N][i]);
  }
  cout<<ans<<endl;
  
}



Measured memory_bytes: 10988
/*
知らなかったこと
"あるグラフが２部グラフであるためには,
グラフに奇数本の辺からなる閉路（奇サイクル）が含まれないことが
必要十分である"

長さ３に着目する理由

二部グラフでは同じグループの頂点間に辺は無い
奇数回の移動では同じグループの頂点にはたどり着けないため,辺が追加されることも無い

二部グラフでないならば, 任意の２頂点の間に奇数長のパスが存在する
・・・グラフが完全グラフになるまで辺を追加する

二部グラフを分けたときに同じグループの頂点同士の距離は必ず偶数になる
*/

// http://ronly.hatenablog.com/entry/2017/10/15/134854

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
using namespace std;

const long long inf = 1e10;
const long long mod = 1e9+7;

typedef vector<vector<int> > G;
G graph;

int color[100050];

bool dfs(int u, int c){
    color[u] = c;
    for(int i=0; i<graph[u].size(); i++){
        int v = graph[u][i];
        if(color[v] == c){
            return false;
        }
        if(color[v] == 0 && !dfs(v, -c) ){
            return false;
        }
    }   
    return true;
}

int main(void){
    long long n, m;
    cin >> n >> m;
    graph = G(n);
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    long long B=0, W=0;
    if(dfs(0, 1)){
        for(int i=0; i<n; i++){
            if(color[i] == 1){
                B++;
            }else if(color[i] == -1){
                W++;
            }
        }
        cout << B*W - m << endl;
    }else{
        cout << ( (n*(n-1)) /2) - m << endl;
    }
    
    return 0;
}



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

const ll MOD = 1000000007;

void add(ll &a, ll &b) {
    a = (a + b) % MOD;
}

int main() {
    int H, W, K;
    cin >> H >> W >> K;

    vector<vector<ll>> dp(H + 1, vector<ll>(W));
    dp[0][0] = 1;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {

            // patternの列挙
            for (int a = 0; a < 1<<(W - 1); a++) {
                bool ok = true;
                for (int b = 0; b < (W - 1); b++) {
                    if ((a & 1<<b) && (a & 1<<(b + 1))) {
                        ok = false;
                        break;
                    }
                }

                if (!ok) continue;

                if (j == 0) {
                    if (a & 1<<j) {
                        add(dp[i + 1][1], dp[i][0]);
                    } else {
                        add(dp[i + 1][0], dp[i][0]);
                    }
                } else if (j == W - 1) {
                    if (a & 1<<(j - 1)) {
                        add(dp[i + 1][j - 1], dp[i][j]);
                    } else {
                        add(dp[i + 1][j], dp[i][j]);
                    }
                } else {
                    if (a & 1<<j) {
                        add(dp[i + 1][j + 1], dp[i][j]);
                    } else if (a & 1<<(j - 1)) {
                        add(dp[i + 1][j - 1], dp[i][j]);
                    } else {
                        add(dp[i + 1][j], dp[i][j]);
                    }
                }
            }
        }
    }

    cout << dp[H][K - 1] << endl;
}

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rsort(v) sort(all(v)); reverse(all(v))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template<typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template<typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template<typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template<typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template<typename T> inline T power(T x, i64 n) { T r = 1; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template<typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  string s;
  cin >> s;
  int k;
  cin >> k;
  rep(i, s.size()) {
    if (s[i] != 'a' && ('z' + 1) - s[i] <= k) {
      k -= ('z' + 1) - s[i];
      s[i] = 'a';
    }
  }
  if (k > 0) {
    k %= 26;
    char c = s[s.size() - 1];
    c += k;
    if (c > 'z') c -= 26;
    s[s.size() - 1] = c;
  }
  cout << s << '\n';
}


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

int main(){
	string s,a;
	int n = 0;
	while(getline(cin,s)){
		for(int i = 0;i < s.length();++i){
			if('0' <= s[i] && s[i] <= '9' && i < s.length()){
				a = s[i];
				++i;
				while('0' <= s[i] && s[i] <= '9' && i < s.length()){
					a += s[i];
					++i;
				}
				n += atoi(a.c_str());
			}
		}
	}
	cout << n << endl;
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
using namespace std;
int main(void){
  int N,T;
  cin>>N>>T;
  int c[N],t[N];
  for(int i(0);i<N;i++){
    cin>>c[i]>>t[i];
  }
  int min(1001);
  for(int i(0);i<N;i++){
    if(T>=t[i] && min>c[i])min=c[i];
  }
  if(min==1001)cout<<"TLE"<<endl;
  else cout<<min<<endl;
  return 0;
}

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

// Inserted snippets: io, root
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }
// End snippets

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

  int n, k; read(n, k);
  vector<int> v(n);
  rep(i, 0, n) read(v[i]);
  rep(i, 0, n - k) {
    if (v[k + i] > v[i]) write("Yes"); else write("No");
  }
}


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

int main(){
	char kc[6][6][4];
int kabe[6][6][4];
for(int i=0;i<6;i++){
for(int j=0;j<6;j++){
for(int k=0;k<4;k++){
	kc[i][j][k]=' ';
kabe[i][j][k]=0;}}}
for(int i=0;i<4;i++){
scanf("%c%c%c%c\n%c%c%c%c%c\n",&kc[i+1][1][1],&kc[i+1][2][1],&kc[i+1][3][1],&kc[i+1][4][1],&kc[i+1][1][2],&kc[i+1][2][2],&kc[i+1][3][2],&kc[i+1][4][2],&kc[i+1][5][2]);}
scanf("%c%c%c%c\n",&kc[5][1][1],&kc[5][2][1],&kc[5][3][1],&kc[5][4][1]);
for(int i=1;i<6;i++){
	for(int j=1;j<6;j++){
		if(kc[i][j][1]=='1'){kabe[i][j][1]=1;}
		if(kc[i][j][2]=='1'){kabe[i][j][2]=1;}
	}
}

for(int i=1;i<6;i++){
for(int j=1;j<6;j++){
kabe[i][j][0]=kabe[i-1][j][2];
kabe[i][j][3]=kabe[i][j-1][1];}}
int muki=1;
int muki2;
int iti[2]={1,1};
int idou[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
string s="";
char a[4]={'U','R','D','L'};
while(1){
for(int i=3;i<7;i++){
muki2=muki+i;
muki2%=4;
if(kabe[iti[0]][iti[1]][muki2]==1){
s+=a[muki2];
muki=muki2;
iti[0]+=idou[muki][0];
iti[1]+=idou[muki][1];
break;}}
if(iti[0]==1&&iti[1]==1){break;}}
cout<<s<<endl;}

Measured memory_bytes: 1204
#include<bits/stdc++.h>
using namespace std;
const int maxn=100100;
const long long INF=1e18;
const long long Fir=1e15;
int S,T;
int n,m;
int beg[maxn],tto[maxn<<1],nex[maxn<<1],w1[maxn<<1],w2[maxn<<1],e;
void putin(int s,int t,int x,int y){
	tto[++e]=t;
	nex[e]=beg[s];
	beg[s]=e;
	w1[e]=x;
	w2[e]=y;
}
long long dis1[maxn],dis2[maxn];
struct node{
	int p;
	long long d;
};
bool operator < (const node &A,const node &B){
	return A.d>B.d;
}
priority_queue<node> q;
bool vis[maxn];
void dij(long long *dis,int *w,int s){
	for(int i=1;i<=n;i++)
		dis[i]=INF,vis[i]=0;
	dis[s]=0;
	q.push((node){s,0});
	node st;
	int u;
	while(!q.empty()){
		st=q.top();
		q.pop();
		u=st.p;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=beg[u];i;i=nex[i]){
			if(dis[tto[i]]>dis[u]+w[i]){
				dis[tto[i]]=dis[u]+w[i];
				q.push((node){tto[i],dis[tto[i]]});
			}
		}
	}
}
long long ans[maxn];
int main(){
//	freopen("A.in","r",stdin);
	scanf("%d%d",&n,&m);
	scanf("%d%d",&S,&T);
	int s,t,x,y;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&s,&t,&x,&y);
		putin(s,t,x,y);
		putin(t,s,x,y);
	}
	dij(dis1,w1,S);
	dij(dis2,w2,T);
	if(dis1[T]==INF){
		for(int i=0;i<=n-2;i++)
			printf("-1\n");
		return 0;
	}
	for(int i=1;i<=n;i++)
		ans[i]=dis1[i]+dis2[i];
	for(int i=n;i>=1;i--)
		if(ans[i]<ans[i-1])
			ans[i-1]=ans[i];
	for(int i=1;i<=n;i++){
		if(ans[i]<INF) printf("%lld\n",Fir-ans[i]);
		else
			printf("0\n");
	}
	return 0;
}


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

class UF{
  vi p,r;

public:
  UF(int n):p(n,-1),r(n,0){ }

  int find(int x){ return (p[x]<0)?x:(p[x] = find(p[x])); }

  void unite(int x,int y){
    x = find(x); y = find(y);
    if(x==y)return;

    if(r[x] < r[y])p[x] = y;
    else p[y] = x;
    if(r[x] == r[y])r[x]++;
  }

  bool same(int x,int y){return find(x)==find(y);}
};

int n,q;
char c[100100];
int v[100100], p[100100];
int marked[100100], root[100100];

int main(){
  while(scanf("%d%d",&n,&q), n){
    for(int i=1;i<n;i++){
      scanf("%d",&p[i]); p[i]--;
    }
    memset(marked,0,sizeof(marked));

    marked[0] = 1;
    for(int i=0;i<q;i++){
      scanf(" %c %d ",&c[i],&v[i]); v[i]--;
      if(c[i]=='M')marked[v[i]]++;
    }

    UF uf(n);
    for(int i=1;i<n;i++){
      if(!marked[i])uf.unite(i,p[i]);
    }

    for(int i=0;i<n;i++){
      if(marked[i])root[uf.find(i)] = i;
    }

    long long ans = 0;
    for(int i=q-1;i>=0;i--){
      if(c[i] == 'M'){
	marked[v[i]]--;
	if(marked[v[i]] == 0){
	  int tmp = root[uf.find(p[v[i]])];
	  uf.unite(v[i],p[v[i]]);
	  root[uf.find(v[i])] = tmp;
	}
      }else{
	ans += root[uf.find(v[i])] + 1;
      }
    }
    cout << ans << endl;
  }
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  n %= 10;
  if(n == 3) cout << "bon" << endl;
  else if(n == 0 || n == 1 || n == 6 || n == 8) cout << "pon" << endl;
  else cout << "hon" << endl;
}

Measured memory_bytes: 3636
var
  s:string;
  i,x,y:longint;
begin
  readln(s);x:=pos('C',s);
  for i:=1 to length(s) do if s[i]='F' then y:=i;
  if (x=0) or (y=0) or (x>y) then write('No') else write('Yes');
end.

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
/*int n,w;
int wt[105];
int val[105];
int dp[105][100005];
int go(int i,int cost,int ww)
{
    if(i==n && ww<w){
        return 1000000000;
    }
    if(i==n && ww>=w) return 0;
    if(dp[i][cost]!=-1) return dp[i][cost];
    int a = min(go(i+1,cost+val[i],ww+wt[i])+wt[i],go(i+1,cost,ww));

    dp[i][cost] = a;
    return dp[i][cost];
}
int main()
{
    cin>>n>>w;
    for(int i=0;i<n;i++){
        cin>>wt[i]>>val[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<go(0,0,0);
    int ans;
    for(int i=0;i<=100;i++){
        if(dp[0][i]<w)
            ans = i;
    }
    cout<<endl;
    cout<<ans<<endl;
}*/
ll wt[105];
ll val[105];
ll dp[105][100001];
int main()
{
    int n,w;
    cin>>n>>w;
    for(int i=0;i<n;i++)
    {
        cin>>wt[i]>>val[i];

    }
    for(int i=0;i<=100;i++){
    for(int j=0;j<=100000;j++){

            dp[i][j] = 1000000000001;
        }

    }

    dp[0][0] = 0;
    //for(int i=0;i<n;i++)
    //dp[0][val[0]] = wt[0];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=100000;j++)
        {
            dp[i][j] = dp[i-1][j];
            if(j>=val[i-1])
            {
                dp[i][j] = min(dp[i][j],dp[i-1][j-val[i-1]]+wt[i-1]);
            }
        }
    }
    ll mx = 0;
    for(int i=100000;i>=0;i--)
    {
        if(dp[n][i]<=w && dp[n][i]!=0)
        {
            cout<<i<<endl;return 0;
        }
        //cout<<dp[n][i]<<endl;
    }
    cout<<mx<<endl;
}



Measured memory_bytes: 80128
#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>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second
#define endl "\n"

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<int, int> P;


int main(){
    int n;  cin >> n;
    vector<ll> a(n+1);
    vector<ll> s(n+1, 0);
    for(int i = 0; i < n+1; i++){
        cin >> a[i];
    }
    s[n] = a[n];
    for(int i = n-1; i >= 0; i--){
        s[i] = a[i] + s[i+1];
    }

    ll res = 1;
    ll available = 1;
    for(int i = 0; i < n+1; i++){
        if(a[i] > available){
            cout << -1 << endl;
            return 0;
        }
        else if(available > s[i]){
            cout << -1 << endl;
            return 0;
        }
        else{
            available -= a[i];
            ll ad = min(available * 2, s[i+1]);
            res += ad;
            available = ad;
        }
    }

    cout << res << endl;


    return 0;
}


Measured memory_bytes: 4844
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;

int main(){
	cin>>n;
	cout<<"Christmas";
	for(int i=n;i<25;i++) cout<<" Eve";
	cout<<endl;
}

Measured memory_bytes: 256
r,c,R,C=map(int,input().split())
m=10**9+7
max_n=2*10**6+1
fac=[1]*(max_n+1)
inv=[1]*(max_n+1)
ifac=[1]*(max_n+1)
for n in range(2,max_n+1):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
def comb(n,k):
    if n<k or n<0 or k<0:
        return 0
    return (fac[n]*ifac[k]*ifac[n-k])%m
def f(r,c):
    return sum([comb(i+1+c,c) for i in range(r+1)])%m
print((f(R,C)-f(R,c-1)-f(r-1,C)+f(r-1,c-1))%m)

Measured memory_bytes: 263832