akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Text;

namespace _017_CaesarCipher
{
	class Program
	{
		static void Main ( string[] args )
		{
			string inputStr;

			while ((inputStr = Console.ReadLine ()) != null)
			{
				int convertNum = 0;

				foreach (var item in inputStr.Split (' '))
				{
					//the
					if (item.Length == 3)
					{
						if (item[0] - item[1] == 12 ||
							item[0] - item[1] == -14 &&
							item[1] - item[2] == 3 ||
							item[1] - item[2] == -23)
						{
							convertNum = item[0] - 't';
							break;
						}
					}
					//this
					//that
					else if (item.Length == 4)
					{
						if (item[0] - item[1] == 12 ||
							item[0] - item[1] == -14) 
						{
							if (item[1] - item[2] == -1 ||
								item[1] - item[2] == 25 &&
								item[2] - item[3] == -10 ||
								item[2] - item[3] == 16) 
							{
								convertNum = item[0] - 't';
								break;
							}
							if (item[1] - item[2] == 7 ||
								item[1] - item[2] == -19 &&
								item[2] - item[3] == -19 ||
								item[2] - item[3] == 7)
							{
								convertNum = item[0] - 't';
								break;
							}
						}
					}
				}

				StringBuilder result = new StringBuilder (inputStr.Length);

				foreach (var item in inputStr)
				{
					if (char.IsLower (item))
					{
						int ch = item - convertNum;

						if (ch < 'a')
							ch += 26;
						else if ('z' < ch)
							ch -= 26;

						result.Append ((char) ch);
					}
					else
					{
						result.Append (item);
					}
				}

				Console.WriteLine (result.ToString ());
			}
		}
	}
}

Measured memory_bytes: 8908
N = int(input())
inner = 0
B_ = 0
_A = 0
BA = 0

for _ in range(N):
    S = input()
    inner += S.count('AB')
    if S[0] == 'B':
        if S[-1] == 'A':
            BA += 1
        else:
            B_ += 1
    elif S[-1] == 'A':
        _A += 1

if BA == 0:
    print(inner + min(B_, _A))
else:
    if B_ == 0 and _A == 0:
        print(inner + BA - 1)
    else:
        print(inner + BA + min(B_, _A))


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

using namespace std;
typedef long long ll;
#define int ll

#define REP(i,n) for(int i=0;i<n;++i)
#define ALL(name) name.begin(),name.end()
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#define MAX_BIT 62

// 加減乗算で MOD を自動で取ってくれる型
// 割り算はやらないので逆元を適宜求めること
struct mint {
    ll x;
    mint(ll x = 0) : x(x % MOD) {}
    mint& operator += (const mint a) {
        if ( (x += a.x) >= MOD) { x -= MOD; }
        return *this;
    }
    mint& operator -= (const mint a) {
        if ( (x += MOD - a.x) >= MOD) { x -= MOD; }
        return *this;
    }
    mint& operator *= (const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator + (const mint a) const {
        mint res(*this);
        return res += a;
    }
    mint operator - (const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator * (const mint a) const {
        mint res(*this);
        return res *= a;
    }
};

// x の n 乗 を m で余りをとったもの
ll mod_pow(ll x, ll n, ll mod) {
    ll res = 1;
    while ( n > 0) {
        if (n & 1) { res = res * x % mod; } // 最下位ビットが立っているときに x^(2^i) を掛ける
        x = x * x % mod;                    // x を順次 2 乗していく
        n >>= 1;
    }
    return res;
}

// i 番目のビットが 0 である数
mint cnt_zero[MAX_BIT];
mint cnt_one[MAX_BIT];

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

    ll N;
    vector<ll> A;

    cin >> N;
    A.resize(N);
    REP(i, N) {
        cin >> A[i];
        REP(j, MAX_BIT) {
            if((A[i] >> j) & 1) {
                cnt_one[j] += 1;
            }
            else {
                cnt_zero[j] += 1;
            }
        }
    }

    mint ans = 0;
    REP(j, MAX_BIT) {
        ans += mint(mod_pow(2, j, MOD)) * cnt_one[j] * cnt_zero[j];
    }
    printf("%lld\n", ans.x);

    return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>

int main(void) {
	int a,b,c;

	scanf("%d %d %d",&a,&b,&c);

	if(a==b+c || a+b==c || b==a+c) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}

	return 0;
}


Measured memory_bytes: 128
#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>;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
  mint p(int n, int k) {
    return fact[n]*ifact[n-k];
  }
} c(1000005);

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= k; i++){
        mint ans = 1;
        if(n-k+1 < i){
            cout << 0 << endl;
            continue;
        }
        ans *= c(k-1, i-1);
        ans *= c(n-k+1,i);
        cout << ans << endl;
    }
}

Measured memory_bytes: 18596
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]
typedef vector< int > vi;
typedef vector< ll > lvi;
typedef vector< vi > vvi;
typedef vector< lvi > lvvi;
typedef pair< int,int > ii;
typedef pair< ll,ll > lii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator
#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps
#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define ss second
#define mp make_pair
#define ld long double
#define ull unsigned long long int
#define mod 1000000007
ll nck[1005][1005],dp[1005][1005],dp2[1005][1005];
ll n,a,b,c,d;
ll modpow(ll x,ll y)
{
	ll ans=1;
	while(y>0)
	{
		if(y&1) ans=(ans*x)%mod;
		x=(x*x)%mod;
		y=y>>1;
	}
	return ans;
}
ll recurs(ll i,ll j)
{
	if(i<0) return 0;
	if(j>b) return 0;
	if(i==0) return 1;
	if(j==b) /*return 1;*/
	{
		if((i%b)!=0) return 0;
		else
		{
			ll k=i/j;
			if(k>=c && k<=d)
			{
				return dp2[j][k];
			}
			else return 0;
		}
	}
	if(dp[i][j]!=-1) return dp[i][j];
	dp[i][j]=recurs(i,j+1);
	// if(i==3 && j==1) cout<<dp[i][j]<<"***\n";
	for(int k=c;k<=d;k++)
	{
		if(k*j >i) break;
		dp[i][j]=(dp[i][j]+(((recurs(i-k*j,j+1)*nck[i][k*j])%mod)*dp2[j][k])%mod)%mod;
	}
	// cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
	return dp[i][j];
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
	cin>>n>>a>>b>>c>>d;
	nck[1][1]=1;
	nck[1][0]=1;
	for(int i=2;i<=n;i++)
	{
		nck[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			nck[i][j]=(nck[i-1][j]+nck[i-1][j-1])%mod;
		}
	}
	for(int i=a;i<=b;i++)
	{
		dp2[i][1]=1;
		for(int j=2;j<=d;j++)
		{
			if(i*j >n) break;
			dp2[i][j]=(dp2[i][j-1]*nck[i*j][i])%mod;
			dp2[i][j]=(dp2[i][j]*modpow(j,mod-2))%mod;
		}
	}
	memset(dp,-1,sizeof(dp));
	ll ans=recurs(n,a);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 23040
#include<iostream>
#include<cstdio>
using namespace std;
int __gcd(int x,int y){return y==0?x:__gcd(y,x%y);}
int a,sum;
int main()
{
	cin>>a;
	for(int i=1;i<=a;i++)
		for(int j=1;j<=a;j++)
			for(int k=1;k<=a;k++)
				sum+=__gcd(__gcd(i,j),__gcd(j,k));
	cout<<sum;
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
	int X;
	cin >> X;
	int point = 400, kyu = 8;
	int ans;
	while (kyu > 0) {
		if (X >= point && X <= point + 199) ans = kyu;
		point += 200;
		kyu--;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3632
n,m,x = map(int,input().split())
a = list(map(int,input().split()))
y = 0
z = 0
for i in range(m):
    if a[i] > x:
        break
    y = i+1
for i in range(m):
    if a[-1-i] < x:
        break
    z = i+1
print(min([m-y,m-z]))

Measured memory_bytes: 3064
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int inpt = int.Parse(Reader.ReadLine());

        int ans = 24 + (24 - inpt);
        Console.WriteLine(ans);


    }


    public class Reader
    {
        private static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"


21





";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n, k;
ll a[100010], s[100010];
vector<ll> v;

int main() {
    while (cin >> n >> k) {
        if (n == 0) break;
        rep(i, n) cin >> a[i];
        rep(i, n) s[i+1] = s[i] + a[i];

        ll ans = 0;
        for (int i = 0; i + k - 1 < n; i++) {
            ll tmp = s[i+k] - s[i];
            chmax(ans, tmp);
        }
        v.push_back(ans);
    }
    for (ll &x: v) cout << x << endl;
}



Measured memory_bytes: 4596
#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
typedef pair<int,int> P;
const int mod=1000000007;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}

signed main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<min({a+b,b+c,c+a})<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>
void Answer(void);
int cnt[4][3][10]={0};
int main(void){
	int i,j,k,n,m,x,y,z;
	char str[100];
	
	fgets(str,sizeof(str),stdin);
	sscanf(str,"%d",&m);
	for(i=0;i<m;i++){
		fgets(str,sizeof(str),stdin);
		sscanf(str,"%d %d %d %d",&x,&y,&z,&n);
		cnt[x-1][y-1][z-1] += n;
	}
	Answer();
	return 0;
}

void Answer(void){
	int i,j,k;
	for(i=0;i<4;i++){
		for(j=0;j<3;j++){
			for(k=0;k<10;k++){
				printf(" %d",cnt[i][j][k]);
			}
			printf("\n");
		}
		if(i < 3)
			printf("####################\n");
	}	
}

Measured memory_bytes: 616
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P2;
const int inf=1000000000;
int main() {
	int n;
	cin>>n;
	int t;
	int s=1;
	for(int i=1;i<n+1;++i){
		int k=0;
		int h=i;
		while(h%2==0){
			k++;
			h/=2;
		}
		if(t<k){
			s=i;
			t=k;
		}
	}
	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String [] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long [] a = new long[n];
        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextLong();
        }
        long sum = 0L;
        long mod = 1000000007L;
        long base = 1L;
        for (int b = 0; b < 60; ++b, base *= 2) {
            int [] ones = new int[n];
            int [] zeros = new int[n];
            if (((a[n - 1] >> b) & 1) == 1) {
                ones[n - 1] = 1;
            } else {
                zeros[n - 1] = 1;
            }
            for (int i = n - 2; i >= 0; --i) {
                if (((a[i] >> b) & 1) == 1) {
                    ones[i] = ones[i + 1] + 1;
                    zeros[i] = zeros[i + 1];
                } else {
                    zeros[i] = zeros[i + 1] + 1;
                    ones[i] = ones[i + 1];
                }
            }
            long currentSum = 0L;
            for (int i = 0; i <= n - 2; ++i) {
                if (((a[i] >> b) & 1) == 1) {
                    currentSum = (currentSum + zeros[i + 1]) % mod;
                } else {
                    currentSum = (currentSum + ones[i + 1]) % mod;
                }
            }
            sum = (sum + (currentSum * (base % mod)) % mod) % mod;
        }
        System.out.println(sum);
    }
}


Measured memory_bytes: 161940
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <list>
#include <cstring>
#include <stack>
   
using namespace std;

#define mod 1000000007

vector<pair<int, int> > getgoal(int b[21][21], vector<bool>& ischecked, int n, int s, int c)
{
    vector<pair<int, int> > result;
    // cout << "nows : " << s << endl;
    for(int i = 1; i <= n; i++){
        if(b[s][i] != 0 && !ischecked[i]){
            // cout << i << " " << ischecked[i] << endl;
            ischecked[i] = true;
            vector<pair<int, int> > tmp = getgoal(b, ischecked, n, i, c + b[s][i]);
            copy(tmp.begin(), tmp.end(), back_inserter(result));
        }
    }
    if(result.size() == 0) result.push_back(make_pair(s, c));
    // cout << s << " : " << endl;
    // for(int i = 0; i < result.size(); i++){
    //     cout << result[i] << endl;
    // }
    return result;
}

int main()
{
    while(1){
        int n;
        cin >> n;
        if(n == 0) break;
        int bridge[21][21] = {};
        // for(int i = 1; i <= n; i++){
        //     for(int j = 1; j <= n; j++){
        //         bridge[i][j] = mod;
        //     }
        // }
        int ans = 0;
        for(int i = 0; i < n - 1; i++){
            int a, b, t;
            cin >> a >> b >> t;
            bridge[a][b] = t;
            bridge[b][a] = t;
            ans += 2 * t;
        }
        vector<bool> ischecked(n + 1, false);
        ischecked[1] = true;
        int maxlen = 0;
        vector<pair<int, int> > goal = getgoal(bridge, ischecked, n, 1, 0);
        for(int i = 0; i < goal.size(); i++){
            int goalnode = goal[i].first;
            int cost = goal[i].second;
            // cout << goalnode << " : " << cost << endl;
            for(int j = 1; j <= n; j++){
                ans -= 2 * bridge[goalnode][j];
                cost -= bridge[goalnode][j];
            }
            maxlen = max(maxlen, cost);
        }
        cout << ans - maxlen << endl;
    }
    return 0;
}

Measured memory_bytes: 1200
def check(x, y, new_x, new_y, dt):
  diff = abs(new_x - x) + abs(new_y - y)
  if dt%2 == diff%2 and diff <= dt:
    return True
  return False

n = int(input())
t, x, y, count = 0, 0, 0, 0
canReach = True
while(count < n):
  new_t, new_x, new_y = map(int, input().split())
  if not check(x, y, new_x, new_y, new_t-t):
    canReach = False
    break
  t, x, y = new_t, new_x, new_y
  count += 1
if canReach:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <cmath>

int64_t f(const int64_t b, const int64_t n)
{
    if (n < b)
    {
        return n;
    }
    else
    {
        return f(b, n / b) + (n % b);
    }
}

int main()
{
    int64_t n, s;
    std::cin >> n >> s;

    if (s == n)
    {
        // この場合は自明
        std::cout << n + 1 << std::endl;
        return 0;
    }
    else if (s > n)
    {
        std::cout << -1 << std::endl;
        return 0;
    }

    // bが大きいほうが各桁が大きくなるので、和も大きくなる傾向にある
    // ただし、単調ではないので、全探索になる
    //
    // sqrt(n) < b <= nで2桁のb進数になる
    // p,qを使って、n = p*b + q, s = p + q
    // n = p*b + s - p
    // n - s = p*(b - 1)
    // b = (n - s) / p + 1
    // また、n = p*b + q >= p*b > p^2
    // p < sqrt(n)
    //
    // 同様に3桁の場合も考えられるが、手間なうえに計算量はあまり減らないようなのであまり意味はない
    // よって、sqrt(n)まで全探索し、残りは2桁の場合を考える

    const int64_t sqrt_n = std::sqrt(n);
    for (int64_t b = 2; b <= sqrt_n; ++b)
    {
        if (f(b, n) == s)
        {
            std::cout << b << std::endl;
            return 0;
        }
    }

    // bの最小値なので、pを上から調べる
    for (int64_t p = sqrt_n; p >= 1; --p)
    {
        if ((n - s) % p)
        {
            continue;
        }
        const int64_t b = (n - s) / p + 1;
        if (b >= sqrt_n && b >= 2 && f(b, n) == s)
        {
            std::cout << b << std::endl;
            return 0;
        }
    }

    std::cout << -1 << std::endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
#define all(x) x.begin(),x.end()
const int inf=0x3f3f3f3f;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N,X,T; cin>>N>>X>>T;
	cout<<T*((N-1)/X+1);	
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

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

  ll sum = 0, square = 0;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum = (sum + a[i]) % mod;
    square = (square + a[i] * a[i]) % mod;
  }

  ll ans = (sum * sum) % mod - square;
  if (ans < 0) ans += mod;
  ll inv_2 = modinv(2, mod);
  cout << ((ans % mod) * inv_2) % mod << endl;
}


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

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define mp make_pair
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define MOD 1000000007

int n,k;
int h,ans;
int a,b,c;

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> a;
		if(a>=k) ans++;
	}
	cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

ll w,h,v,t,x,y,p,q;

ll dst(ll a,ll b,ll c, ll d){
    return (a-c)*(a-c)+(b-d)*(b-d);
}

pair<ll,ll> calc(ll i,ll j){
    pair<ll,ll> pa;
    ll a,b;
    if(abs(i)%2==0){
        a = p;
        a += w*i;
    }else{
        a = w-p;
        a += w*i;
    }
    if(abs(j)%2==0){
        b = q;
        b += h*j;
    }else{
        b = h-q;
        b += h*j;
    }
    return MP(a,b);
}

int main(){
    cin >> w >> h >> v >> t >> x >> y >> p >> q;
    ll ans = 0;
    ll k = 10*(v*t)/(w+h+10)+10;
    for(ll i=0;;i++){
        ll cnt = 0;
        ll ok = -1;
        ll ng = k;
        while(ng-ok>1){
            ll mid = (ok+ng)/2;
            pair<ll,ll> pa = calc(i,mid);
            if(dst(x,y,pa.first,pa.second)<=v*t*v*t){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        cnt += ok+1;
        ok = 0;
        ng = -k;
        while(ok-ng>1){
            ll mid = (ok+ng)/2;
            pair<ll,ll> pa = calc(i,mid);
            if(dst(x,y,pa.first,pa.second)<=v*t*v*t){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        cnt += -ok;
        if(cnt==0)break;
        ans += cnt;
    }
    for(ll i=-1;;i--){
        ll cnt = 0;
        ll ok = -1;
        ll ng = k;
        while(ng-ok>1){
            ll mid = (ok+ng)/2;
            pair<ll,ll> pa = calc(i,mid);
            if(dst(x,y,pa.first,pa.second)<=v*t*v*t){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        cnt += ok+1;
        ok = 0;
        ng = -k;
        while(ok-ng>1){
            ll mid = (ok+ng)/2;
            pair<ll,ll> pa = calc(i,mid);
            if(dst(x,y,pa.first,pa.second)<=v*t*v*t){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        cnt += -ok;
        if(cnt==0)break;
        ans += cnt;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3100
#include <iostream>

using namespace std;

int main(void)
{
	int cost;
	int ret;
	int count;
	
	while (1){
		cin >> cost;
		if (cost == 0)break;
		ret = 1000 - cost;
		
		count = 0;
		count += ret / 500;
		ret %= 500;
		count += ret / 100;
		ret %= 100;
		count += ret / 50;
		ret %= 50;
		count += ret / 10;
		ret %= 10;
		count += ret / 5;
		ret %= 5;
		count += ret;
		
		cout << count << endl;
	}
	
	return (0);
}

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


int main(void) {
  int N, Q;
  cin >> N >> Q;
  string str;
  cin >> str;

  // 累積和
  vector<int> s(N+1, 0);
  rep(i, N) {
    if (i+1 < N && str[i] == 'A' && str[i+1] == 'C') s[i+1] = s[i] + 1;
    else s[i+1] = s[i];
  }

  for (int q = 0; q < Q; ++q) {
    int l, r;
    cin >> l >> r;
    --l;
    --r;
    cout << s[r] - s[l] << endl;
  }

  return 0;
}


Measured memory_bytes: 3824
from collections import Counter

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    c = Counter(a)
    used = set()
    m = 10**6 + 1
    cnt = [0]*m
    ans = 0
    for ai in a:
        if c[ai]>1:
            if ai not in used:
                used.add(ai)
                for i in range(ai, m, ai):
                    cnt[i] += 1
        else:
            if cnt[ai] == 0:
                ans += 1
                for i in range(ai, m, ai):
                    cnt[i] += 1
    print(ans)

if __name__ == "__main__":
    solve()


Measured memory_bytes: 133888
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  int x,c=0;
  string s;
  cin>>x;
  s=to_string(x);
  for(int i=0;i<(int)s.size();i++) c+=s[i]-'0';
  cout<<(x%c==0?"Yes":"No")<<endl;
  return 0;
}


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

int main(){
  int a,b,c,d;
  cin>>a;
  d=a%10;
  c=(a%100-d)/10;
  b=(a%1000-c*10-d)/100;
  a/=1000;

  for(int i=0;i<8;++i){
    int x,y,z;
    x=i%2;
    y=(i>>1)%2;
    z=(i>>2)%2;
    if(x==1)x=-1;
    else x=1;
    if(y==1)y=-1;
    else y=1;
    if(z==1)z=-1;
    else z=1;
    if(a+x*b+y*c+z*d==7){
        cout << a << (x==1?"+":"-") << b << (y==1?"+":"-") << c << (z==1?"+":"-") << d << "=7" << endl;
        return 0;
     }
  }
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import collections
import itertools as it
import math
import numpy as np

#  = input()
#  = int(input())
N, M = map(int, input().split())
A = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()

c = 0
for a in A:
    # print((1/(4*M)) * sum(A))
    if (1/(4*M)) * sum(A) <= a:
        c += 1


# print(c, M)
print('Yes' if c >= M else 'No')


Measured memory_bytes: 12388
const input=require('fs').readFileSync('/dev/stdin','utf8').split(/[\s]/);let input_i=-1;const tn=():number=>{input_i++;return Number(input[input_i])};const tnn=(n:number):number[]=>{const a=[];for(let i=0;i<n;i++){a.push(tn())}return a};const ts=():string=>{input_i++;return String(input[input_i])};const tss=(n:number):string[]=>{const a=[];for(let i=0;i<n;i++){a.push(ts())}return a};const to=(...arg)=>{console.log(...arg)};const abs=(a)=>{return Math.abs(a)};const min=(...a)=>{return Math.min(...a)};const max=(...a)=>{return Math.max(...a)};const floor=(a)=>{return Math.floor(a)};const asc=(ar:number[])=>{return ar.sort((a,b)=>{return a-b})};const desc=(ar:number[])=>{const t=[...ar];return t.sort((a,b)=>{return b-a})};const sw=(a,arr:any[],op:'=='|'>='|'>'|'<='|'<'='==')=>{for(let i=0;i<arr.length-1;i+=2){if(eval(a+op+arr[i])){return arr[i+1]}}return arr[arr.length-1]};const near=(n:number,arr:number[]):number=>{let ne=arr[0],ni=0;for(let i=1;i<arr.length;i++){if(Math.abs(n-ne)>Math.abs(n-arr[i])){ne=arr[i];ni=i}}return ni};const deduplicate=(a:any[]):any[]=>{return Array.from(new Set(a))};
const main=()=>{
  let n=tn()
  let ar=tnn(n)
  let descar=desc(ar)
  let m=descar[0]
  let m2=descar[1]
  for(let i=0;i<n;i++){
    to(ar[i]!=m?m:m2)
  }
}
main()


Measured memory_bytes: 59244
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <string>

#include <algorithm>
#include <numeric>
#include <functional>
#include <iterator>
#include <random>
#include <complex>
#include <utility>
#include <tuple>
#include <memory>

#include <array>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <csignal>
#include <cstdint>
#include <cstddef>

#ifdef ONLINE_JUDGE
#define NDEBUG
#endif
#include <cassert>
#include <stdexcept>
#include <exception>

// << pair
template <typename T1, typename T2>
std::ostream&operator<<(std::ostream&os,const std::pair<T1,T2>&p){return os<<"("<<p.first<<", "<<p.second<<")";}
// << container
template <typename C>
std::ostream&_debug_go(std::ostream&os,const C&v) {bool first=true;os<<"[";for(auto i:v){if(!first)os<<", ";os<<i;first=false;}return os<<"]";}
// << {vector, set, map} delegating to _debug_go
template<typename T> std::ostream&operator<<(std::ostream&os,const std::vector<T>&v){return _debug_go(os, v);}
template<typename T> std::ostream&operator<<(std::ostream&os,const std::set<T>&v){return _debug_go(os, v);}
template<typename T1, typename T2> std::ostream&operator<<(std::ostream&os,const std::map<T1,T2>&v){return _debug_go(os, v);}
struct Debugger{template<typename T>Debugger&operator,(const T&v){std::cerr<<v<<" "; return *this;}} dbg;
#ifndef NDEBUG
#define debug(args...) do {dbg,args; cerr << "\n";} while(0)
#else
#define debug(args...)
#endif

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ITER(i, s, e) for (auto i((s)); i != (e); ++i)
#define IT(i, c) ITER(i, (c).begin(), (c).end())

using namespace std;

using ui = uint32_t;
using ll = int64_t;
using ull = uint64_t;
template <typename T = int> using Pt = complex<T>;

template <typename T>
T cross(const Pt<T>& a, const Pt<T>& b) { return a.real() * b.imag() - a.imag() * b.real(); }

template <typename T>
bool cmpPt(const Pt<T>& a, const Pt<T>& b) {
    return a.real() < b.real() || (a.real() == b.real() && a.imag() < b.imag());
}
// END TEMPLATE


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int A, B; cin >> A >> B;
    cout << max(A + B, max(A - B, A * B)) << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define dl double long
const int INF=0x3fffffff;
const ll MOD=1000000007;
const ll MODD=998244353;
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }

int main()
{
  ll N, L, sum, minabs=INF;
  cin >> N >> L;
  sum = (2*L+N-1)*N/2;
  REP(i, L, N+L){
    minabs = min(abs(minabs), abs(i));
  }
  if(minabs == L) cout << sum-minabs << "\n";
  else cout << sum+minabs << "\n";
}


Measured memory_bytes: 256
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Data.List

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words
getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
    [h,w] <- getIntList
    as <- concat . zipWith (\f a -> f a) (cycle [id, reverse]) . ind2D <$> replicateM h getIntList
    let ans = reverse . (\(a,_,_) -> a) $ foldl' count ([],True,(0,0)) as
    print $ length ans
    mapM_ putStrLn ans

ind2D as = map (\(i,bs) -> zipWith (\j b -> ((i,j),b)) [1..] bs ) $ zip [1..] as

count (s,e,(i,j)) ((k,l),b)
    | e && even b = (s,True,(k,l))
    | e && odd b = (s,False,(k,l))
    | even b = (p:s,False,(k,l))
    | odd b = (p:s,True,(k,l))
    where p = show i ++ " " ++ show j ++ " " ++ show k ++ " " ++ show l

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

using namespace std;

const int MAX_N = 3e5 + 200;

ll n, k, ci[MAX_N], di[MAX_N], tmp[MAX_N];

bool check(ll mid)
{
    for (ll i = 1; i <= n; i++)
        tmp[i] = mid / di[i];
    sort(tmp + 1, tmp + 1 + n);
    ll ans = 0;
    for (ll i = n; i >= 1; i--)
        ans += max(0LL, ci[i] - tmp[i]);
    return ans <= k;
}

int main()
{
    scanf("%lld%lld", &n, &k);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &ci[i]);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &di[i]);
    ll l = 0, r = 1e12, ans = 0;
    sort(ci + 1, ci + 1 + n), sort(di + 1, di + 1 + n);
    while (l <= r)
    {
        ll mid = (l + r) >> 1LL;
        if (check(mid))
            r = mid - 1, ans = mid;
        else
            l = mid + 1;
    }
    printf("%lld", ans);
    return 0;
}

Measured memory_bytes: 6016
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=5e18;
typedef pair<int,int> P;
signed main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,l;
  string s[105]={};
  cin >> n >> l;
  for(int i=0; i<n; i++) {
    cin >> s[i];
  }
  sort(s,s+n);
  for(int i=0; i<n; i++) {
    cout << s[i];
  }
  cout << endl;
}


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9

using namespace std;
typedef long long int lli;
typedef long long ll;

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

    string ans = "No";
    if(n[0] == '9' || n[1] == '9') ans = "Yes";

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

int gcd(int m ,int n) {
    if (m < n) return gcd(n, m);
    return gcd(n, m % n);
}

void solve() {
    int n;
    cin >> n;
    VI x(n), y(n);
    REP(i,0,n) cin >> x[i] >> y[i];

    map<PII, int> coords;
    REP(i,0,n) coords[MP(y[i], x[i])] = i;
    set<PII> s;
    REP(i,0,n) REP(j,i+1,n) {
        int dy = y[j] - y[i], dx = x[j] - x[i];
        s.emplace(dy,dx);
    }
    int ans = n;
    for (auto &p: s) {
        int dy = p.first, dx = p.second;
        vector<bool> used(n);
        int cnt = 0;
        REP(i,0,n) {
            if (used[i]) continue;
            ++cnt;
            int cx = x[i], cy = y[i];
            while (coords.count(MP(cy, cx)) > 0) {
                int index = coords[MP(cy, cx)];
                if (used[index]) {
                    --cnt;
                    break;
                }
                used[index] = true;
                cx += dx;
                cy += dy;
            }
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}

int main() {
    solve();
    
    return 0;
}

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

int main(){
int a,b;
int c[25000];
while(scanf("%d%d",&a,&b),a|b){
	int s=0;
	for(int d=0;d<a;d++)scanf("%d",&c[d]);
	sort(c,c+a);
	for(int e=0;e<a-1;e++){
		s+=c+a-upper_bound(c+e+1,c+a,b-c[e]);
	}
	printf("%d\n",s);
}
}

Measured memory_bytes: 3236
/*
[abc100] B - Ringo's Favorite Numbers
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

int D, N;

ll solve() {
    int ans = 1;
    for (int i = 0; i < D; i++) {
        ans *= 100;
    }
    ans *= (N == 100 ? 101 : N);
    return ans;
}

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

    cout << solve() << endl;

    return 0;
}


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

using namespace std;

typedef long long ll;

const int mod = 1e9 + 7, maxn = 1e5 + 10;
int dp[maxn][3], dp2[maxn][3], ans, p[maxn], cnt[maxn], cnt2[maxn], n;
string s;

int main(){
	p[0] = 1;
	for (int i = 1; i < maxn; ++i)
		p[i] = 3ll * p[i - 1] % mod;
	cin >> s;
	n = s.size();
	if (s[0] == 'A')
		dp[0][0]++;
	if (s[0] == '?')
		cnt[0] = 1;
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 3; ++j)
			dp[i][j] = dp[i - 1][j];
		cnt[i] = cnt[i - 1];
		if (s[i] == 'A')
			dp[i][0] = (dp[i][0] + 1) % mod;
		else if (s[i] == 'B')
			dp[i][1] = (dp[i][1] + dp[i - 1][0]) % mod;
		else if (s[i] == 'C')
			dp[i][2] = (dp[i - 1][1] + dp[i][2]) % mod;
		else 
			cnt[i]++;
	}
	if (s[n - 1] == 'C')
		dp2[n - 1][0]++;
	if (s[n - 1] == '?')
		cnt2[n - 1]++;
	for (int i = n - 2; ~i; --i) {
		cnt2[i] = cnt2[i + 1];
		for (int j = 0; j < 3; ++j)
			dp2[i][j] = dp2[i + 1][j];
		if (s[i] == 'C')
			dp2[i][0] = (dp2[i][0] + 1) % mod;
		else if (s[i] == 'B')
			dp2[i][1] = (dp2[i][1] + dp2[i + 1][0]) % mod;
		else if (s[i] == 'A')
			dp2[i][2] = (dp2[i][2] + dp2[i + 1][1]) % mod;
		else
			cnt2[i]++;
	}
	ll t = cnt[n - 1];
	ans = 1ll * dp[n - 1][2] * p[t] % mod;
	if (t >= 1) {
		int k = 0;
		for (int i = 0; i < n; ++i)
			if (s[i] == '?') {
				if (i + 1 < n)
					k = (k + dp2[i + 1][1]) % mod;
				if (i - 1 >= 0)
					k = (k + dp[i - 1][1]) % mod;
				if (i + 1 < n && i - 1 >= 0)
					k = (k + 1ll * dp[i - 1][0] * dp2[i + 1][0]) % mod;
			}
		ans = (ans + 1ll * k * p[t - 1]) % mod;
	}
	if (t >= 2) {
		int k = 0;
		for (int i = 0; i < n; ++i)
			if (s[i] != '?') {
				if (s[i] == 'A' && i + 1 < n)
					k = (k + 1ll * cnt2[i + 1] * (cnt2[i + 1] - 1) / 2) % mod;
				if (s[i] == 'C' && i - 1 >= 0)
					k = (k + 1ll * cnt[i - 1] * (cnt[i - 1] - 1) / 2) % mod;
				if (s[i] == 'B' && i + 1 < n && i - 1 >= 0)
					k = (k + 1ll * cnt[i - 1] * cnt2[i + 1]) % mod;
			}
		ans = (ans + 1ll * k * p[t - 2]) % mod;
	}
	if (t >= 3)
		ans = (ans + t * (t - 1) * (t - 2) / 6 % mod * p[t - 3]) % mod;
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 3968
def f(K):
    sum = 0
    p10 = 1
    for i in range(K+1):
        sum += p10*7
        p10 *= 10
        p10 %= K
        sum %= K

        if sum == 0:
            return i+1
    return -1


K = int(input())

print(f(K))


Measured memory_bytes: 9068
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

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

    if(N == 1) cout << 1 << endl;
    else{
        int ans = 2;
        while(ans <= N) ans *= 2;

        cout << ans/2 << endl;
    }
}

Measured memory_bytes: 256
pub fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

pub fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

pub fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

pub fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

use std::cmp::max;

fn main() {
    let nt: Vec<usize> = read_vec();
    let n = nt[0];
    let t = nt[1];
    let abv: Vec<Vec<usize>> = read_vec2(n);

    let mut dp1: Vec<Vec<u32>> = vec![vec![0; t]; n];

    let a = abv[0][0];
    let b = abv[0][1];
    for j in 0..t {
        if j < a {
            dp1[0][j] = 0;
        } else {
            dp1[0][j] = b as u32;
        }
    }
    for i in 1..n {
        let a = abv[i][0];
        let b = abv[i][1];
        for j in 0..t {
            if j < a {
                dp1[i][j] = dp1[i - 1][j];
            } else {
                dp1[i][j] = max(dp1[i - 1][j], dp1[i - 1][j - a] + b as u32);
            }
        }
    }

    let mut dp2: Vec<Vec<(u32, usize)>> = vec![vec![(0, 0); t]; n];

    let a = abv[0][0];
    let b = abv[0][1];
    for j in 0..t {
        dp2[0][j] = (b as u32, a);
    }
    for i in 1..n {
        let a = abv[i][0];
        let b = abv[i][1];
        for j in 0..t {
            let mut t = dp2[i - 1][j];
            let t1 = (dp1[i - 1][j] + b as u32, a);
            if t1.0 > t.0 {
                t = t1;
            }
            if j >= a {
                let t2 = (dp2[i - 1][j - a].0 + b as u32, dp2[i - 1][j - a].1);
                if t2.0 > t.0 {
                    t = t2;
                }
            }
            dp2[i][j] = t;
        }
    }

    println!("{}", dp2[n - 1][t - 1].0);
}


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

int main(){
  int N;
  cin>>N;
  vector<int64_t> X(N),X_sort(N);
  for(int i=0;i<N;++i){
    cin>>X.at(i);
    X_sort.at(i)=X.at(i);
  }
  sort(X_sort.begin(),X_sort.end());

  for(int i=0;i<N;++i){
    if(X.at(i)<=X_sort.at((N-1)/2)){
      cout<<X_sort.at((N-1)/2+1)<<endl;
    }
    else{
      cout<<X_sort.at((N-1)/2)<<endl;
    }
  }
}

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


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#define fo(i, n) for(int i=0; i<n; i++)
#define Fo(i, k, n) for(int i=k; i<n; i++)
#define w(x)  int x; cin>>x; while(x--)
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"
#define watch3(x,y,z) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<"\n"
#define watch4(x,y,z,q) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<" and "<<(#z)<<" is "<<(z)<<" and "<<(#q)<<" is "<<(q)<<"\n"
#define MOD 1000000007
#define INF 1000000007;
#define F first
#define S second
#define pb(x) push_back(x);


#define ll  long long
#define all(c) (c).begin(),(c).end()
#define endl "\n"

typedef vector<int> vl;
typedef vector< vl > vvl;
typedef pair< int, int> pll;
typedef map< int, int> mll;


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif





void c_p_c()
{
#ifndef ONLINE_JUDGE
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}
void parray(int a[], int n) {
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}
int no = 1, n1;
int recu(int n, int k, int val) {


	if (n == n1) {
		return min(val * 2, val + k);
	}
	return min( recu(n + 1, k, 2 * val), recu(n + 1, k, val + k)              );


}
int digit(int n) {

	int temp = 0;
	while (n) {
		// temp += n % 10;
		n = n / 10;
		temp++;
	}



	return temp;
}

bool check(int a[], int n) {
	for (int i = 0; i < n; ++i)
	{
		/* code */
		if (a[i] % 2)
			return false;
	}
	return true;
}


int main() {
	int i,  n, k, c = 0, sum = 0;
	c_p_c();
	// cout<<"Sd"<<endl;>
	// cin>>n>>k;
	string s, str;
	cin >> s >> str;
	string s1 = s + str;
	stringstream geek(s1);

	// The object has the value 12345 and stream
	// it to the integer x
	int x = 0;
	geek >> x;
	// cout << x << endl;
	// if(long double)
	long double u = sqrt(x);
	if (u - floor(u) == 0)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;





}

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

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

    int x,t;
    cin>>x>>t;
    cout<<(x-1)*(t-1)<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll l,r,d;cin>>l>>r>>d;
    cout<<r/d-(l-1)/d<<endl;
    return 0;
}

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

using namespace std;
using ll = long long;

int main(int argc, const char *argv[]) {
  int n, m;
  cin >> n >> m;

  vector<pair<ll, ll>> vp1(n), vp2(m);
  for (auto &p : vp1) cin >> p.first >> p.second;
  for (auto &p : vp2) cin >> p.first >> p.second;

  auto dist = [](pair<ll, ll> &a, pair<ll, ll> &b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
  };

  for (auto &p : vp1) {
    ll min_dist = dist(p, vp2.front());
    int min_idx = 0;
    for (int i = 0; i < m; i++) {
      auto &p2 = vp2[i];
      ll d = dist(p, p2);
      if (d < min_dist) {
        min_dist = d;
        min_idx = i;
      }
    }

    cout << min_idx + 1 << '\n';
  }

  return 0;
}

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef pair<ll, ll> PLL;

signed main() {
    ll N;
    string s;
    cin>>N>>s;

    vector<ll> v(s.size(), 0);
    v[0] = (s[0]==')')?-1:1;
    rep(i,1,s.size()){
        v[i]=v[i-1]+((s[i]==')')?-1:1);
    }

    ll mi = 0;
    rep(i,0,v.size())
        mi=min(mi, v[i]);
    rep(i,0,-mi)
        cout<<"(";
    cout<<s;

    rep(i,0,v[v.size()-1] + (-mi))
        cout<<")";
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#coding utf-8
import collections
_=input()
bars=[i for i in map(int,input().split())]
data=sorted(collections.Counter(bars).items(),key= lambda x: -x[0] )
stock=0
ret=0
for bar ,count in data:
    if count>=4:
        if stock:
            ret=stock*bar
            break
        else:
            ret=bar*bar
            break
    elif count>=2:
        if stock:
            ret=stock*bar
            break
        else:
            stock=bar
print(ret)


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

#define watch(x) cerr << (#x) << ": " << (x) << endl
#define int long long

int solve(vector<int>& nums, int i, int white_count) {
    int n = nums.size();
    if(i == n) return 0;

    int cand1 = nums[i] + solve(nums, i+2, white_count - nums[i+1]);
    return min(cand1, white_count);
}

int32_t main() {

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

    vector<int> nums;
    if(s[0] == '.') nums.push_back(0);

    int count = 1;
    for(int i = 1; i < n; ++i) {
        if(s[i] != s[i-1]) {
            nums.push_back(count);
            count = 1;
        } else {
            count++;
        }
    }
    nums.push_back(count);

    if(s.back() == '#') nums.push_back(0);
    int white_count = 0;
    for(int i = 1; i < (int)nums.size(); i+=2) {
        white_count += nums[i];
    }

    int ans = solve(nums, 0, white_count);

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


Measured memory_bytes: 5236