akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--) 
#define Rep(i,a) for(int i = 0; i < a; i++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ab(x) ((x) < 0 ? -(x) : (x))
using namespace std;
typedef long long LL;
typedef map<int, int>::iterator mit;
typedef set<int>::iterator sit;
const int N = 1e6 + 10;
int t[N];
int main() {
	int n, c, k; scanf("%d%d%d",&n,&c,&k);
	rep(i,1,n) scanf("%d",&t[i]);
	sort(t + 1, t + n + 1);
	int j = 1, cnt = 0;
	for(; j <= n; cnt++) {
		int pos = t[j] + k, tmp = 0;
		while (j <= n && pos >= t[j] && tmp < c) j++, tmp++;
	}
	cout <<cnt<<endl;
	return 0;		
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String ans = "";
        for(int i = 0 ;i < line.length();i++){
            char ch = line.charAt(i);
            if(Character.isUpperCase(ch) == true){
                ch = Character.toLowerCase(ch);
            }
            else if(Character.isLowerCase(ch) == true){
                ch = Character.toUpperCase(ch);
            }
            ans += ch;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 31752
#include<stdio.h>

int main(void)
{
    char s[52];
    int n,ans=0;
    scanf("%d",&n);
    scanf("%s",s);
    for(int i=0;i<n;i++){
      if((s[i]=='A')&&(s[i+1]=='B')&&(s[i+2]=='C')) ans++;
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
constexpr int MOD = 1000000007;
constexpr int INF = 2147483647;
int main()
{
    vector<int> A(9);
    REP(i, 9) cin >> A[i];
    int N;
    cin >> N;
    vector<bool> p(9, false);
    REP(i, N) {
        int b;
        cin >> b;
        REP(j, 9) {
            if(A[j] == b) p[j] = true;
        }
    }
    if((p[0] && p[1] && p[2]) || (p[3] && p[4] && p[5]) || (p[6] && p[7] && p[8]) || (p[0] && p[3] && p[6]) || (p[1] && p[4] && p[7]) || (p[2] && p[5] && p[8]) || (p[0] && p[4] && p[8]) || (p[2] && p[4] && p[6])) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
import bisect
n=int(input())
a=list(map(int, input().split()))
q=int(input())
for i in range(q):
    k=int(input())
    if a[0]>k:
        print(0)
    elif k>a[n-1]:
        print(n)
    else:
        L = bisect.bisect_left(a,k)
        print(L)  


Measured memory_bytes: 17220
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void *wmem;
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16]={0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){
  int i;
  pair<T1, T2> *arr;
  walloc1d(&arr, N, &mem);
  for(i=0;i<(N);i++){
    arr[i].first = a[i];
    arr[i].second = b[i];
  }
  sort(arr, arr+N);
  for(i=0;i<(N);i++){
    a[i] = arr[i].first;
    b[i] = arr[i].second;
  }
}
template<class T1, class T2, class T3> void sortA_L(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  int i;
  pair<T1, pair<T2, T3> > *arr;
  walloc1d(&arr, N, &mem);
  for(i=0;i<(N);i++){
    arr[i].first = a[i];
    arr[i].second.first = b[i];
    arr[i].second.second = c[i];
  }
  sort(arr, arr+N);
  for(i=0;i<(N);i++){
    a[i] = arr[i].first;
    b[i] = arr[i].second.first;
    c[i] = arr[i].second.second;
  }
}
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(double &x){
  scanf("%lf",&x);
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(double x){
  printf("%.15f",x);
}
template<class T> inline T pow2_L(T a){
  return a*a;
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
char memarr[96000000];
int N;
double X[200];
double Y[200];
double t[100];
int main(){
  double res=0, sx, sy;
  int i, j;
  wmem = memarr;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<(N);Lj4PdHRW++){
      rd(X[Lj4PdHRW]);
      rd(Y[Lj4PdHRW]);
    }
  }
  for(i=0;i<(N);i++){
    t[i] = atan2(Y[i],X[i]);
  }
  sortA_L(N, t, X, Y);
  for(i=0;i<(N);i++){
    X[i+N] = X[i];
  }
  for(i=0;i<(N);i++){
    Y[i+N] = Y[i];
  }
  for(i=0;i<(N);i++){
    sx = sy = 0;
    for(j=0;j<(N);j++){
      sx += X[i+j];
      sy += Y[i+j];
      chmax(res,pow2_L(sx)+pow2_L(sy));
    }
  }
  res = sqrt(res);
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190902-1

// --- original code ---
// int N;
// double X[200], Y[200];
// double t[100];
// {
//   int i, j;
//   double sx, sy, res = 0;
//   
//   rd(N,(X,Y)(N));
//   rep(i,N) t[i] = atan2(Y[i],X[i]);
//   sortA(N, t, X, Y);
// 
//   rep(i,N) X[i+N] = X[i];
//   rep(i,N) Y[i+N] = Y[i];
// 
//   rep(i,N){
//     sx = sy = 0;
//     rep(j,N){
//       sx += X[i+j];
//       sy += Y[i+j];
//       res >?= sx**2 + sy**2;
//     }
//   }
// 
//   res = sqrt(res);
//   wt(res);
// }


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

using P = pair<int, int>;

int main(void)
{   
    int H, W, M;
    cin >> H >> W >> M;

    int h, w;
    vector<int> hc(H,0), wc(W,0);
    set<pair<int,int>> s;
    int hmax=0;
    int wmax=0;
    for(int i = 0; i < M; ++i){
        cin >> h >> w;
        h--;
        w--;
        hc[h]++;
        wc[w]++;
        s.emplace(P(h,w));
    }

    vector<int> seth, setw;
    for(int i=0; i < H; i++){
        if(hmax < hc[i]){
            hmax = hc[i];
        }
    }
    for(int i=0; i < W; i++){
        if(wmax < wc[i]){
            wmax = wc[i];
        }
    }

    for(int i=0; i < H; i++){
        if(hc[i] == hmax){
            seth.push_back(i);
        }
    }
    for(int i=0; i < W; i++){
        if(wc[i] == wmax){
            setw.push_back(i);
        }
    }

    int ans = wmax + hmax;
    for(int i : seth) for(int j : setw) {
        if(s.count(P(i, j)) != 0 ) continue;
        cout << ans << endl;
        return 0;
    }

    ans--;

    cout << ans << endl;

}


Measured memory_bytes: 23856
S = input()
T = input()
n = len(S)

s = list(S)
t = list(T)

s.sort()
t.sort()

v = 0
w = 0

a = [0 for i in range(0,n)]
b = [0 for i in range(0,n)]

c = [0 for i in range(0,26)]
d = [0 for i in range(0,26)]

for i in range(0,n-1):
    if s[i] == s[i+1]:
        a[i+1] = v
    else:
        v += 1
        a[i+1] = v

for i in range(0,n-1):
    if t[i] == t[i+1]:
        b[i+1] = w
    else:
        w += 1
        b[i+1] = w

for i in range(0,26):
    c[i] = a.count(i)

for i in range(0,26):
    d[i] = b.count(i)

c.sort()
d.sort()

if c == d:
    print("Yes")
else:
    print("No")

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

int solve(long long N, long long Y)
{
    long long sum = 0;
    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= N - i; j++)
        {
            for (int k = 0; k <= N - i - j; k++)
            {
                if ((i * 10000 + j * 5000 + k * 1000 == Y) && (i + j + k == N))
                {
                    cout << i << " " << j << " " << k << endl;
                    return 0;
                }
            }
        }
    }

    cout << "-1 -1 -1" << endl;
    return 0;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    long long Y;
    scanf("%lld", &Y);
    solve(N, Y);
    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <bitset>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <string>
#include <chrono>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <functional>
#include <sstream>

using namespace std;

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int p, q, r;
    cin >> p >> q >> r;
    int mx = max(p, max(q, r));

    int res = p + q + r - mx;
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 256
import math
#X = int(input())
b = [0 for i in range(1001)]
for i in range(2, 1001):
    j = i * i
    while j < 1001:
        if b[j] == 1:
            break
        b[j] = 1
        j *= i
b[1] = 1
X = int(input())
for i in range(X, 0, -1):
    if b[i] == 1:
        print(i)
        break


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



int main() {
	int64_t k;
  	int n, q;
  	cin >> n >> k >> q;
  	vector<int> a(q);	rep(i,q){int tmp; cin >> tmp; a.at(i) = tmp - 1;}
  	vector<int64_t> pt(n,k);
  	rep(i,q){
    	pt.at(a.at(i))++;
    }
  	rep(i,n){
    	pt.at(i) = pt.at(i) - q;
    }
	
  	rep(i,n){
    	if(pt.at(i) > 0) cout << "Yes" << endl;
      	else cout << "No" << endl;
    }
}

Measured memory_bytes: 1920
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <sstream>
#include <climits>
#include <cmath>
#include <map>
#include <stack>
using namespace std;
#define M_PI 3.141592
#define toRad 2.0*M_PI/360.0
#define inin(x) int x;cin>>x;
#define all(x) x.begin(),x.end()
#define debug(x) cout<<#x<<" "<<x<<endl;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define EPS 1e-12
#define pri_max 60000
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
/*
bool memo[pri_max] = {};
vector<int> pri;
void calc()
{
	for (int i = 2; i < pri_max; i++)
	{
		if (memo[i] == false)
		{
			pri.push_back(i);
			for (int l = i; l < pri_max; l += i)
			{
				memo[l] = true;
			}
		}
	}
}*/
int main()
{
	vector <pii> a;
	pii temp;
	while (scanf("%d,%d", &temp.second, &temp.first) && temp.first != 0 || temp.second != 0)a.push_back(temp);
	sort(all(a));
	reverse(all(a));
	vector<int> jun[200];
	int k = 0,v=a[0].first;
	for (int i = 0; i < a.size(); i++)
	{
		if (v != a[i].first)
		{
			v = a[i].first;
			k++;
		}
		jun[k].push_back(a[i].second);
	}

	int num;
	while (cin >> num)
	{
		bool flag = true;
		for (int i = 0; i < 200&&flag; i++)
		{
			for (int l = 0; l < jun[i].size(); l++)
			{
				if (jun[i][l] == num)
				{
					cout << i + 1 << endl;
					flag = false;
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 1272
#include <stdio.h>

int main ()
{
    int a, b,i,w,r, flag=0,e;
    scanf("%d %d", &a, &b);
    if(a>b)
    {
        w =a;
        r = b;
    }
    else
    {
        w = b;
        r = a;
    }
    for(i=r; i<=w; i++)
    {
        e = r*i*w;

        if(e%2!=0)
            flag =1;
    }
    if(flag==1)
    {
        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;
typedef long long ll;

int main(){
  int n;
  cin >> n;
  int a[n],b[n];
  rep(i,n)cin >> a[i];
  rep(i,n)b[i]=a[i];
  sort(a,a+n);
  int l = a[n/2-1];
  int r = a[n/2];
  rep(i,n){
    if(b[i]<=l)cout << r << endl;
    else cout << l << endl;
  }
  return 0;
}


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


int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  int n;
  cin>>n;
  vector<long long> v;
  for(int i=0;i<n;i++){
    long long t;
    cin>>t;
    v.push_back(t);
  }
  sort(v.rbegin(),v.rend());
  long long sum=v[0];
  int j=1;
  int cnt=0;

  for(int i=2;i<n;i++){
     sum+=v[j];
     cnt++;
     if(cnt==2){
      cnt=0;
      j+=1;
     }
  }
  cout<<sum<<endl;
       
  
}

Measured memory_bytes: 5316
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define VPII vector<pair<int,int> >
#define F first
#define S second
#define RF(x) freopen(x,"r",stdin)
#define WF(x) freopen(x,"w",stdout)
typedef long long LL;
using namespace std;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
const LL MOD = 1e9+7;
const int SIZE = 1e6+5;
const LL INF = 1LL<<58;
const double eps = 1e-13;

int main(){
	DRIII(i,o,t);DRI(j);DRIII(l,s,z);
	LL ans=o*2;
	if((i%2&&j%2&&l>0)||(i>0&&j%2&&l%2)||(i%2&&j>0&&l%2)){
		ans+=6;i--;j--;l--;
	}
	ans+=4*(i/2);
	i%=2;
	ans+=4*(j/2);
	j%=2;
	ans+=4*(l/2);
	l%=2;
	printf("%lld",ans/2);
}


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

using namespace std;

#define el				'\n'
#define sz(v)			((int)((v).size()))
#define all(v)          ((v).begin()),((v).end())
#define clr(v, d)		memset(v, d, sizeof(v))

double const EPS = 1e-8, PI = acos(-1);
const int N = 1e5 + 9, M = 1e5 + 9, OO = (int) 1e6 + 1;
const long long MOD = 1e9 + 7;

typedef long long ll;

void OUTPUT() {
	cout << fixed << setprecision(0);
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}

void READ() {
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
}
ll n, k, heights[N], mem[N];

ll dp(int i) {
	if (i >= n)
		return OO;
	if (i == n - 1)
		return 0;
	if (mem[i] != -1)
		return mem[i];
//	mem[i] = OO;
	for (int j = 1; j <= k; j++) {
		if (j == 1)
			mem[i] = dp(i + j) + abs(heights[i] - heights[i + j]);
		else
			mem[i] = min(mem[i], dp(i + j) + abs(heights[i] - heights[i + j]));
	}
	return mem[i];
}
//
//ll dp(int i) {
//	if (i >= n)
//		return OO;
//	if (i == n - 1)
//		return 0;
//	if (mem[i] != -1)
//		return mem[i];
//	ll a = dp(i + 1) + abs(heights[i] - heights[i + 1]);
//	ll b = dp(i + 2) + abs(heights[i] - heights[i + 2]);
////	cout << i << " " << a << " " << b << el;
//	mem[i] = min(a, b);
//	return mem[i];
//
//}

int main() {
//	READ();
	OUTPUT();
	clr(mem, -1);
	cin >> n;
	k = 2;
	for (int i = 0; i < n; ++i) {
		cin >> heights[i];
	}
	cout << dp(0);

	return 0;

}


Measured memory_bytes: 9600
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
#define F first
#define S second

const int mxn = 2e5+5;
int n;
bool good[mxn];
array<int, 3> a[mxn];

void solve(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }

    sort(a, a+n);

    set<int> ff, fb;
    for(int i = 0; i < n; ++i){
        ff.insert(i);
        fb.insert(i);
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> worstf, worstb;

    for(int i = 0; i < n; ++i){
        int k = a[i][0], l = a[i][1], r = a[i][2];
        if(l > r){
            auto lb = ff.upper_bound(k-1);
            if(lb == ff.begin()){
                ff.erase(--ff.end());

                if(!worstf.empty() && worstf.top().F < l-r){
                    good[worstf.top().S] = false;
                    worstf.pop();
                    worstf.push({l-r, i});
                    good[i] = true;
                }
                else{
                    good[i] = false;
                }
            }
            else{
                --lb;
                ff.erase(lb);
                worstf.push({l-r, i});
                good[i] = true;
            } 
        }
    }

    for(int i = n-1; i >= 0; --i){
        int k = a[i][0], l = a[i][1], r = a[i][2];
        if(r > l){
            auto lb = fb.lower_bound(k);
            if(lb == fb.end()){
                fb.erase(fb.begin());
                
                if(!worstb.empty() && worstb.top().F < r-l){
                    good[worstb.top().S] = false;
                    worstb.pop();
                    worstb.push({r-l, i});
                    good[i] = true;
                }
                else{
                    good[i] = false;
                }
            }
            else{
                fb.erase(lb);
                worstb.push({r-l, i});
                good[i] = true;
            }
        }  
    }

    ll ans = 0;
    for(int i = 0; i < n; ++i){
        int mn = min(a[i][1], a[i][2]), mx = max(a[i][1], a[i][2]);
        ans += good[i] ? mx : mn;
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T; cin >> T;
    for(int i = 0; i < T; ++i)
        solve();
    return 0;
}

Measured memory_bytes: 26824
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <string>
#include <math.h>
#include <cstdlib>
#include <istream>
#include <sstream>
#include <cctype>
#include <iomanip>
//cout << fixed << setprecision(20) << *** << endl;
#define rep(i,N) for(int i=0;i<(int)N;++i)
typedef long long ll;
using namespace std;

ll XC2(ll a){
	return a*(a-1)/2;
}

int main()
{
	ll N;
	map<ll,ll>mp;
	vector<ll>V;
	cin>>N;
	rep(i,N){
		ll t;
		cin>>t;
		V.push_back(t);
		if(mp.count(t)==0)mp[t]=1;
		else mp[t]++;
	}
	ll Count=0;
	auto iter = mp.begin();
	for(iter;iter!=mp.end();iter++){
		Count=Count+XC2(iter->second);
	}
	rep(i,V.size()){
		ll ANS=Count;
		ANS=ANS-XC2(mp[V[i]]);
		ANS=ANS+XC2(mp[V[i]]-1);
		cout<<ANS<<endl;
	}
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;
 
// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

map<ll, ll> mp;

int main() {
  ll N, P;
  cin >> N >> P;

  // 割る数の初期値
  ll a = 2;
  // √n ≧ a ( n ≧ a * a ) の間ループ処理
  while (P >= a * a) {
    // a で割り切れたら、a は素因数
    if (P % a == 0) {
      mp[a]++;
      P /= a;
    } else {
      a++;
    }
  }
  // 最後に残った n は素因数
  mp[P]++;

  ll ans = 1;
  for (map<ll, ll>::iterator it = mp.begin(); it != mp.end(); it++) {
    //cout << it->first << ":" << it->second << endl;
    if (it->second >= N) ans *= pow(it->first, it->second / N);
  }

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


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;

typedef long long ll;
const int MAXN=2e5+5;
const int MOD=1e9+7;
const int INF=0x3f3f3f3f;

int n,X,Y,ans;
int a[MAXN],b[MAXN],vis[MAXN],cnt[MAXN];
int mine[MAXN],pos[MAXN];
vector<int> E[MAXN];

void dfs(int u){
    vis[u]=1;
    for(int i=0;i<(int)E[u].size();i++){
        int v=E[u][i];
        if(vis[v]) continue;
        dfs(v);
    }
}

ll fac[MAXN],inv[MAXN];
void Init(){
    fac[0]=1;
    for(int i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%MOD;
    inv[1]=1;
    for(int i=2;i<MAXN;i++) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
    inv[0]=1;
    for(int i=1;i<MAXN;i++) inv[i]=inv[i]*inv[i-1]%MOD;
}

ll C(ll x,ll y){
    if(x<y) return 0;
    return 1ll*(fac[x]*inv[y]%MOD)*inv[x-y]%MOD;
}

void addedge(int u,int v){
    E[u].push_back(v);
    E[v].push_back(u);
}

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

    Init();
    memset(mine,0x3f,sizeof mine);
    scanf("%d%d%d",&n,&X,&Y);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i],&b[i]);
        if(mine[a[i]]>b[i]){
            mine[a[i]]=b[i];
            pos[a[i]]=i;
        }
    }
    for(int i=1;i<=n;i++)
        if(pos[a[i]]!=i&&b[i]+mine[a[i]]<=X)
            addedge(i,pos[a[i]]);
    int min1,min2,p1,p2,c1,c2;
    min1=min2=INF;
    for(int i=1;i<=n;i++)
        if(b[i]<min1)
            min1=b[i],p1=i,c1=a[i];
    for(int i=1;i<=n;i++)
        if(b[i]<min2&&a[i]!=c1)
            min2=b[i],p2=i,c2=a[i];
    for(int i=1;i<=n;i++){
        if(p1==i) continue;
        if(a[i]!=c1&&b[i]+min1<=Y)
            addedge(i,p1);
        if(min2!=INF&&a[i]!=c2&&b[i]+min2<=Y)
            addedge(i,p2);
    }
    dfs(p1);
    for(int i=1;i<=n;i++)
        if(vis[i])
            cnt[a[i]]++;
    ll tot=0,ans=1;
    for(int i=1;i<=n;i++) tot+=cnt[i];
    for(int i=1;i<=n;i++){
        if(!cnt[i]) continue;
        ans=1ll*ans*C(tot,cnt[i])%MOD;
        tot-=cnt[i];
    }
    printf("%lld",ans);

    fclose(stdin);
    fclose(stdout);
}


Measured memory_bytes: 19952
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int N;
  long long C,E1,E2;
  cin>>N>>C;
  vector<long long> x(100002,0),v(100002,0),s1(100002,0),s2(100002,0),f1(100002,0),g1(100002,0),f2(100002,0),g2(100002,0);
  for (int i = 1; i <= N; i++) cin>>x[i]>>v[i];
  s1[0] = 0;
  s2[N+1] = 0;
  for (int i = 1; i <= N; i++) {
    s1[i] = 0;
    s1[i] = s1[i-1]+v[i];
    f1[i] = s1[i] - x[i];
  }
  for (int i = N; i >= 0; i--) {
    s2[i] = 0;
    s2[i] = s2[i+1]+v[i];
    f2[i] = s2[i] - (C - x[i]);
  }
  g1[0] = f1[0];
  g2[N] = f2[N];
  for (int i = 1; i <= N; i++) {
    if(g1[i-1] >= f1[i]) g1[i] = g1[i-1];
    else g1[i] = f1[i];
  }
  for (int i = N - 1; i >= 0; i--) {
    if (g2[i+1] >= f2[i]) g2[i] = g2[i+1];
    else g2[i] = f2[i];
  }
  E1 = 0;
  for (int i = N; i > 0; i--) {
    long long tmp1;
    if (g1[i-1] <= 0) tmp1 = s2[i]  - (C - x[i]);
    else tmp1 = s2[i] + g1[i-1] - 2*(C - x[i]);
    if (E1 < tmp1) E1 = tmp1;
  }
  E2 = 0;
  for (int i = 0; i <= N; i++) {
    long long tmp2;
    if (g2[i+1] <= 0) tmp2 = s1[i] - x[i];
    else tmp2 = s1[i] + g2[i+1] - 2*x[i];
    if (E2 < tmp2) E2 = tmp2;
  }
  cout<<max(E1,E2)<<endl;
  return 0;
}

Measured memory_bytes: 6528
from bisect import bisect_left, bisect_right

n,k = map(int, input().split())
vl = list(map(int, input().split()))

ans = 0
for get_num in range(0,k+1):
    rem = k-get_num
    for l in range(0,get_num+1):
        r = get_num-l
        if l+r > n: continue
        ls = vl[:l]
        rs = vl[n-r:]
        curr_l = ls + rs
        curr_l.sort()
        minus_cnt = bisect_left(curr_l, 0)
        if minus_cnt <= rem:
            curr_ans = sum(curr_l[minus_cnt:])
            ans = max(curr_ans,ans)
        else:
            curr_ans = sum(curr_l[rem:])
            ans = max(curr_ans,ans)

print(ans)

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

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

    int a, b;
    cin >> a >> b;
    int res = 0;

    if(b == 1){
        cout << 0 << endl;
        return 0;
    }
    
    for (int i = 1; i <= b; ++i){
        int available = (i - 1) * (a - 1) + a;
        if(available >= b){
            res = i;
            break;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args) {
        long ans = 0;
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        int l = str.length();
        for (int i = 0; i < l / 2; i++) {
            String a = str.substring(i, i + 1);
            String b = str.substring(l - i - 1, l - i);
            if(!(a.equals(b))) ans++;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,c,d,res,i=1,flag=1;
	cin>>a>>b;
	long long mi=max(a,b),ma=a*b;

	for(c=mi,i=1;c<=ma&&flag;i++,c=mi*i)
	{
		if(c%a==0&&c%b==0)
		{
			res=c;flag=0;
			break;
		}
	}
	cout<<res;
	return 0;
}


Measured memory_bytes: 256
import sys

def query(n):
    q = ""
    for i in range(N):
        q += str(n + i)
        if i != N-1:
            q += " "
    
    print ("?" , q)

    ret = input()

    return ret


N = int(input())

l = 1
r = N + 1

lc = query(1)
if lc == "Red":
    rc = "Blue"
elif lc == "Blue":
    rc = "Red"
else:
    sys.exit()

while r - l != 1:

    m = (l + r) // 2
    mc = query(m)

    if mc == lc:
        l = m
        lc = mc
    else:
        r = m
        rc = mc

ans = [None] * (2 * N)
ans[l-1] = lc[0]
ans[r+N-2] = rc[0]
#print (ans)

eqstr = ""
for i in range(N-1):
    eqstr += str(l + 1 + i)
    eqstr += " "

#print (eqstr,l,r)

for i in range(l - 1):
    i += 1
    print ("?",eqstr + str(i))
    rec = input()
    ans[i-1] = rec[0]

for i in range(2 * N - (r + N - 1)):
    i += r+N
    print ("?",eqstr + str(i))
    rec = input()
    ans[i-1] = rec[0]

#print (ans)

BN = 0
RN = 0
eqstrT = ""
for i in range(N * 2):

    if ans[i] == "R" and RN < N // 2:
        eqstrT = eqstrT + str(i+1) + " "
        RN += 1
    if ans[i] == "B" and BN < N // 2:
        eqstrT = eqstrT + str(i+1) + " "
        BN += 1
    #print (eqstrT,ans[i])

for i in range(N * 2):
    if ans[i] == None:
        print ("?",eqstrT + str(i + 1))
        rec = input()
        ans[i] = rec[0]

print ("!","".join(ans))


Measured memory_bytes: 40960
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0;i<int(n);++i)
using namespace std;
template<class A>void pr(A a){cout << a << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;p(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;p(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;p(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for(int j=0;j<N;++j) {}

int main(void) {
  int x,a;cin>>x>>a;
  if(x < a) {
    pr(0);
  } else {
    pr(10);
  }
  return 0;
}


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

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

    long long a[100000];
    long long x;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        a[i] = x;
    }

    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            cout << 0 << "\n";
            return 0;
        }
    }

    long long limit = pow(10, 18);
    long long currProduct = 1;
    for (int i = 0; i < n; i++) {
        // a[i] * currProduct <= 10^18
        if (a[i] <= limit / currProduct) {
            currProduct *= a[i];
        } else {
            cout << -1 << "\n";
            return 0;
        }
    }

    cout << currProduct << "\n";
}

Measured memory_bytes: 4376
#include "bits/stdc++.h"
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int,int>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
ll int MOD=1e9+7;
#define INF 2*1e9
#define N 310000 
using namespace std;
string alphabet("abcdefghijklmnopqrstuvwxyz");

int nim(int a,int b){
    if(a<b) return 0;
    if(!(a%b)){
        return a/b;
    }
    return nim(a-((a-(a/b)*b-1)/(a/b+1)+1)*(a/b+1),b);
}
int main(){
    int n,ans=0;
    cin>>n;
    rep(i,n){
        int a,b;
        cin>>a>>b;
        ans^=nim(a,b);
    }
    cout<<((ans==0)?"Aoki":"Takahashi");
    return 0;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pb push_back
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-6
#define MEM(x) memset(x,0,sizeof(x))
#define MEMS(x) memset(x,-1,sizeof(x))
#define pi acos(-1)
#define last Last
using namespace std;
typedef long long LL;
int main(){
	int n,k,q;
	scanf("%d %d %d",&n,&k,&q);
	int a[2005];
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	a[n]=0;
	int ans=1e9;
	for(int i=0;i<n;i++){
		vector<int> v;
		vector<int> out;
		for(int j=0;j<=n;j++){
			//printf("%d\n",j);
			if(a[j]<a[i]){
				sort(v.begin(),v.end());
				//printf("%d\n",v.size()-k);
				for(int l=0;l<=(int)(v.size()-k);l++){
					//printf("%d %d %d\n",l,v.size()-k,l=(v.size()-k));
					out.pb(v[l]);
				}
				v.clear();
			}
			else{
				v.pb(a[j]);
			}
		}
		sort(out.begin(),out.end());
		if(out.size()>=q){
			ans=min(ans,out[q-1]-out[0]);
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.NavigableSet;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		NavigableSet<Time> set = new TreeSet<Time>();
		while (n-- > 0)
			set.add(new Time(scanner.nextInt(), scanner.nextInt()));

		int m = scanner.nextInt();
		while (m-- > 0)
			set.add(new Time(scanner.nextInt(), scanner.nextInt()));
		System.out.print(set.pollFirst());
		while(!set.isEmpty())
			System.out.print(" " + set.pollFirst());
		System.out.println();
	}

	class Time implements Comparable<Time> {
		int h, m;

		public Time(int h, int m) {
			super();
			this.h = h;
			this.m = m;
		}

		@Override
		public String toString() {
			return String.format("%d:%02d", h, m);
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + h;
			result = prime * result + m;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Time other = (Time) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (h != other.h)
				return false;
			if (m != other.m)
				return false;
			return true;
		}

		@Override
		public int compareTo(Time o) {
			if (this.h == o.h)
				return this.m - o.m;
			return this.h - o.h;
		}

		private Main getOuterType() {
			return Main.this;
		}

	}
}

Measured memory_bytes: 21000
from fractions import gcd
from math import sqrt, ceil

a, b = map(int, input().split())

ans = 0
tmp = 1
g = gcd(a,b)
while g > 1:
    for i in range(tmp+1,ceil(sqrt(g))):
        if g%i == 0:
            ans += 1
            tmp = i
            while g%i == 0:
                g //= i
            break
    else:
        # もうgでしか割れないはず
        ans += 1
        break
print(ans+1)


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

int main() {
  int N;
  cin >> N;
  for (int i = 0; i<N; i++){
    string a;
    cin >> a;
    if (a != "Y" && i != N-1) {
      continue;
    }
    else if (a != "Y" && i == N-1){
      cout << "Three" << endl;
      break;
    }
    cout << "Four" << endl;
    break;
  }
}


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

#define INF INT_MAX/2;
#define MOD 1000000007

using namespace std;

using ll = long long;
using ull = unsigned long long ;

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

   string S;
   cin>>S;
   string s="";
   int MIN = INF;
   for(int i=0;i<S.size()-2;i++){
      s=S[i];
      s=s+S[i+1];
      s=s+S[i+2];
      MIN = min(abs(atoi(s.c_str())-753),MIN);
   }
   cout<<MIN<<endl;
   return 0; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

vector<vector<pii>> m;//<to, const>
int Q,
K;
int N;
vector<bool> is_check;
vector<ll> cost;

void dp(int p){
    is_check[p] = true;
    for(auto &&c : m[p]){
        if(is_check[c.fi]) continue;
        cost[c.fi] += cost[p] + c.se;
        dp(c.fi);
    }
}

int main(void)
{
    cin >> N;
    m.assign(N, vector<pii>());
    REP(i, N-1){
        int a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        m[a].pb(pii(b, c));
        m[b].pb(pii(a, c));
    }
    cin >> Q >> K;
    vector<pii> query(Q);
    REP(i, Q){
        int x,y;
        cin >> x >> y;
        x--;y--;
        query[i] = pii(x,y);
    }

    is_check.assign(N, false);
    cost.assign(N, 0);

    dp(K-1);

    REP(i, Q){
        pr(cost[query[i].fi] + cost[query[i].se]);
    }
}

Measured memory_bytes: 13568
n = int(input())
ans = ""
for i in range(1, n + 1):
    if(i % 3 == 0):
        ans += " " + str(i)
        continue
    x = i
    while(x):
        if(x % 10 == 3):
            ans += " " + str(i)
            break
        x //= 10
print(ans)


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

int maxPerfectPower(int x) {
    int res = 1;
    for (int b = 2; b <= (int) std::ceil(std::sqrt(x)); ++b) {
        int p = 1;
        int a = 1;
        while (a <= x) {
            res = std::max(res, a);
            a = std::pow(b, ++p);
        }
    }
    return res;
}

int main() {
    int x;
    std::cin >> x;
    std::cout << maxPerfectPower(x) << std::endl;
}

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

using namespace std;

int main(int argc, char const *argv[]) {
  string S;
  cin >> S;
  int length = S.length();
  long long sum = stol(S.substr(0, length));

  for (int bit = 1; bit < (1 << (length - 1)); bit++) {
    int head = 0;
    for (int i = 0; i < length - 1; i++) {
      if (bit & (1 << i)) {
        sum += stoi(S.substr(head, i + 1 - head));
        head = i + 1;
      }
    }
    sum += stoi(S.substr(head, length - head));
  }
  cout << sum << "\n";
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
using namespace std;
typedef long long ll;
template<class T>
void read(T &res) {
  int f = 1; res = 0;
  char c = getchar();
  while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
  while(c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = getchar(); }
  res *= f;
}
const int N = 310;
const int INF = 0x3f3f3f3f;
int n, m, l;
ll ma[N][N], res[N][N];
int main() {
  read(n); read(m); read(l);
  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
      if(i != j) ma[i][j] = INF;
  int u, v;
  ll w;
  for(int i = 1; i <= m; ++i) {
    read(u); read(v); read(w);
    ma[u][v] = ma[v][u] = min(ma[u][v], w);
  }
  for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j)
        ma[i][j] = min(ma[i][j], ma[i][k] + ma[k][j]);
  for(int i = 1; i <= n; ++i) {
    res[i][i] = 0;
    for(int j = 1; j <= n; ++j) {
      res[i][j] = INF;
      if(ma[i][j] <= l) res[i][j] = 1;
    }
  }
  for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
      for(int j = 1; j <= n; ++j)
        res[i][j] = min(res[i][j], res[i][k] + res[k][j]);
  int q; read(q);
  while(q--) {
    read(u); read(v);
    if(res[u][v] == INF) puts("-1");
    else printf("%lld\n", res[u][v] - 1);
  }
  return 0;
}


Measured memory_bytes: 2048
#include <cstdio>
using namespace std;

int main ()
{
  char X;
  char Y;
  scanf("%c", &X);
  scanf(" %c", &Y);
  if (X > Y) {
    printf(">\n");
  } else if (X < Y) {
    printf("<\n");
  } else {
    printf("=\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;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int,int> P;

int main(){
  int n;
  cin >> n;
  int a[n];
  rep(i,n-1)cin >> a[i];
  vector<int> c(n,0);
  rep(i,n-1)c[a[i]-1]++;
  rep(i,n)cout << c[i] << endl;
  return 0;
}


Measured memory_bytes: 4788
#include <bits/stdc++.h>
using namespace std;
int abc(int a,int b){
  int n;
  if(b==0)return a;
  while(a%b!=0){
    n=a%b;
    a=b;
    b=n;
  }
  return b;
}
int main() {
  int  n;
  cin>>n;
  vector<int> a(n),l(n),r(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  l[0]=0;
  r[n-1]=0;
  for(int i=1;i<n;i++){
    l[i]=abc(a[i-1],l[i-1]);
  }
  for(int i=n-2;i>=0;i--){
    r[i]=abc(a[i+1],r[i+1]);
  }
  int ans=0;
  for(int i=0;i<n;i++){
    ans=max(ans,abc(l[i],r[i]));
  }
  cout<<ans<<endl;
}
      

Measured memory_bytes: 1408
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <numeric>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>

using namespace std;

typedef long long  ll;

const int INF = 1e9;

struct Node {
    int x, y, d, foot;
    Node() {}
    Node(int x, int y, int d, int foot) : x(x), y(y), d(d), foot(foot) {}
};
bool operator<(const Node &a, const Node &b) {
    return a.d > b.d;
}

const int dx[][9] = {{1, 2, 3, 1, 2, 1, 1, 2, 1},
                     {-1, -2, -3, -1, -2, -1, -1, -2, -1}};
const int dy[][9] = {{0, 0, 0, -1, -1, -2, 1, 1, 2},
                     {0, 0, 0, -1, -1, -2, 1, 1, 2}};

int main()
{
    int w, h;

    while (cin >> w >> h, w || h) {
        vector<vector<char>> block(h, vector<char>(w));

        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                cin >> block[i][j];

        // d[i][j][k] := (i, j)にk(0: 左, 1: 右)足を置いた時の最短距離
        vector<vector<vector<int>>> d(h, vector<vector<int>>(w, vector<int>(2, INF)));
        priority_queue<Node> que;

        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                if (block[i][j] == 'S') {
                    d[i][j][0] = d[i][j][1] = 0;
                    que.push(Node(j, i, 0, 0));
                    que.push(Node(j, i, 0, 1));
                }

        while (!que.empty()) {
            Node now = que.top();  que.pop();

            for (int j = 0; j < 9; ++j) {
                int nx = now.x + dx[now.foot][j];
                int ny = now.y + dy[now.foot][j];

                if (nx < 0 || ny < 0 || nx >= w || ny >= h)
                    continue;
                if (block[ny][nx] == 'X')
                    continue;

                int cost = 0;
                if (block[ny][nx] == 'S' || block[ny][nx] == 'T')
                    cost = 0;
                else if (isdigit(block[ny][nx]))
                    cost = (int)(block[ny][nx] - '0');

                if (d[ny][nx][(now.foot + 1) % 2] > d[now.y][now.x][now.foot] + cost) {
                    d[ny][nx][(now.foot + 1) % 2] = d[now.y][now.x][now.foot] + cost;
                    que.push(Node(nx, ny, d[ny][nx][(now.foot + 1) % 2], (now.foot + 1) % 2));
                }
            }
        }

        int res = INF;
        for (int i = 0; i < h; ++i)
            for (int j = 0; j < w; ++j)
                if (block[i][j] == 'T')
                    res = min(res, min(d[i][j][0], d[i][j][1]));

        if (res == INF)
            res = -1;
        cout << res << endl;
    }

    return 0;
}

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

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

    long long a, b, k;
    cin >> a >> b >> k;
    
    long long ak = min(a, k);
    a -= ak;
    k -= ak;
    
    b -= min(b, k);
    cout << a << ' ' << b << endl;

    return 0;
}

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

int main()
{
    int e;
    int x;
    while(1){
        cin >> e;
        int sum = e;
        if(e == 0){
            break;
        }
        for(int z = 0; z * z * z <= e; z++){
            for(int y = 0; z * z * z + y * y <= e; y++){
                x = e - (z * z * z + y * y);
                if(x + y + z < sum){
                    sum = x + y + z;
                }
            }
        }
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h> //JuniorMonster a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define mod 1000000007
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio();cin.tie();cout.tie();
using namespace std;
ll n,s1;
pair<string,ll>a[100000];
pair<string,ll>b[100000];
int32_t main(){
CODE_START;
cin>>n;
for(ll i=0;i<n;i++){
    cin>>a[i].f>>a[i].s;
    b[i].f=a[i].f;
    b[i].s=a[i].s;
}
sort(a,a+n);
ll z=-1,y=-1;
for(ll i=0;i<n-1;i++)
if(a[i].f==a[i+1].f){
    if(z==-1){
        z=i;
        y=i+1;
    }else {
    y=i+1;
    }
}else if(z!=-1){
    s1=0;
s1=0;
for(ll j=z;j<=(z+y)/2;j++){
    swap(a[j].s,a[y-s1].s);
    s1++;
}
z=-1;
}
if(z!=-1){
    s1=0;
for(ll j=z;j<=(z+y)/2;j++){
    swap(a[j].s,a[y-s1].s);
    s1++;
}
}
for(ll i=0;i<n;i++)
{
    for(ll j=0;j<n;j++)
    if(b[j].f==a[i].f&&b[j].s==a[i].s){
        cout<<j+1<<endl;
        break;
    }
}
return 0;}


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

#define FI(i,a,b) for(int i=(a);i<=(b);i++)
#define FD(i,a,b) for(int i=(a);i>=(b);i--)

#define LL long long
#define Ldouble long double
#define PI 3.1415926535897932384626

#define PII pair<int,int>
#define PLL pair<LL,LL>
#define mp make_pair
#define fi first
#define se second

using namespace std;

int n, s[3005], dp[3005], R;

vector<int> res, v[3005];

int dfs(int id, int pv){
	int cnt = 0, wp = 0;
	for(auto to: v[id]){
		if(to == pv) continue;
		if(s[to] < s[id]){
			cnt++;
			int res = dfs(to, id);
			if(res == 0) wp = 1;
		}
	}
	if(cnt == 0) return 0; //losing state
	
	if(wp) return 1;
	else return 0;
}
			

int main(){
	scanf("%d", &n);
	FI(i, 1, n) scanf("%d", &s[i]);
	FI(i, 2, n){
		int a, b;
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	FI(i, 1, n){
		R = i;
		if(dfs(R, -1) == 1) res.push_back(i);
	}
	FI(i, 0, (int)res.size() - 1) printf("%d%c", res[i], i == res.size() - 1 ? '\n':' ');
	return 0;
}

Measured memory_bytes: 384
#include <vector>
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>

using namespace std;


int main(void){
  
  int N,K,ans=0;

  cin >> N >> K;
  vector<int> S;

  for(int i = 0; i< N;i++){
    S.push_back(0);
  }

  for(int i = 0; i< K;i++){
    int d;
    cin >> d;

    for(int j = 0; j<d;j++){
      int tmp;
      cin >> tmp;

      S.at(tmp-1)++;


    }
  }

  for(int i = 0; i<N;i++){
    if(S.at(i)==0){
      ans++;
    }
  }
 
  cout << ans << endl;
 
  return 0;
}




Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define ll long long 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

int main()
{
    fast;
    int t=1;
    //cin>>t;
    while(t--)
    {
     double n,d;
     cin>>n>>d;
     int cnt=0;
     while(n--)
     {
      double x,y;
      cin>>x>>y;
      double temp=sqrt((x*x)+(y*y));
      if(temp<=d)
      {
        cnt++;
      }
     }
     cout<<cnt<<endl;
    }
}

Measured memory_bytes: 3768
//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __inline__ __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
    R int res,f=1;R char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=1e5+5;
bitset<N>vis;int p[N],A[N],st[N],top,n,m,g;
void init(int n=N-5){
	fp(i,2,n){
		if(!vis[i])p[++m]=i;
		for(R int j=1;j<=m&&i*p[j]<=n;++j){
			vis[i*p[j]]=1;
			if(i%p[j]==0)break;
		}
	}
}
void solve(int x){
	for(R int i=1;p[i]*p[i]<=x;++i)if(x%p[i]==0){
		st[++top]=p[i];
		while(x%p[i]==0)x/=p[i];
	}
	if(x!=1)st[++top]=x;
}
int main(){
//	freopen("testdata.in","r",stdin);
	n=read(),init();
	fd(i,n,0)A[i]=read(),g=__gcd(g,A[i]);
	solve(abs(g));
	for(R int i=1;p[i]<=n;++i)if(A[0]%p[i]==0){
		bool flag=1;
		fp(j,1,p[i]-1){
			int res=0;
			for(R int k=j;k<=n;k+=p[i]-1)(res+=A[k])%=p[i];
			if(res){flag=0;break;}
		}
		if(flag)st[++top]=p[i];
	}
	sort(st+1,st+1+top),top=unique(st+1,st+1+top)-st-1;
	fp(i,1,top)printf("%d\n",st[i]);
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
using namespace std;
/*ll power(ll x,ll y)
{
    ll res=1;
    while(y>0)
    {
        if(y%2==1)
            res=(res*x)%mod;
        x=(x*x)%mod;
        y=y/2;
    }
    return res;
}*/

int main()
{
ll a,b;
cin>>a>>b;
cout<<max(a*b,max(a+b,a-b))<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define PB push_back
#define MP make_pair

pair<int, int> stone[100000];

int main() {
	while (true) {
		int n, c, pos = 0;
		cin >> n;
		if (n == 0) break;

		REP(i, n) { stone[i].first = stone[i].second = 0; }

		scanf("%d", &c);
		stone[++pos] = MP(c, 1);

		FOR(i, 1, n) {
			scanf("%d", &c);

			if ((i + 1) % 2 == 1) {
				if (stone[pos].first == c) stone[pos].second++;
				else stone[++pos] = MP(c, 1);
			} else {
				if (stone[pos].first == c)
					stone[pos].second++;
				else {
					if (pos == 0) {
						stone[pos].first = c;
						stone[pos].second++;
					} else {
						stone[pos - 1].second += ++stone[pos].second;
						stone[pos].first = stone[pos].second = 0;
						pos--;
					}
				}
			}
		}

		int ans = 0;
		REP(i, pos + 1) if (stone[i].first == 0) ans += stone[i].second;
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> pi;
typedef pair<int,int> vi;

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i <= b; i++)


int main() {
	int N;
	pi cards;
	
	cin >> N;
	int n;
	for(int i = 0; i < N; i++){
		cin >> n;
		cards.PB(n);
	}
	sort(cards.begin(), cards.end());
	reverse(cards.begin(), cards.end());
	int al = 0;
	int bob = 0;
	for(int i = 0; i < N; i++){
		if(i % 2 == 0){
			al += cards[i];
		}
		else{
			bob += cards[i];
		}
	}
	cout << al - bob << "\n";

}


Measured memory_bytes: 256