akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;
import static java.lang.System.out;

public class Main{
    static MyReader in = new MyReader();

    public static void main(String[] args){
        final int N, K, L; {int[] a = in.ii(); N = a[0]; K = a[1]; L = a[2];}
        UnionFind road = new UnionFind(N+1);
        UnionFind rail = new UnionFind(N+1);
        for(int i = 0; i < K; i++){
            int[] city = in.ii();
            road.unite(city[0], city[1]);
        }
        for(int i = 0; i < L; i++){
            int[] city = in.ii();
            rail.unite(city[0], city[1]);
        }
        HashMap<Long, Integer> hm = new HashMap<>(N);
        for(int i = 1; i <= N; i++){
            long key = ((long)road.root(i)<<18) + rail.root(i);
            hm.put(key, 1+hm.getOrDefault(key, 0));
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= N; i++){
            long key = ((long)road.root(i)<<18) + rail.root(i);
            sb.append(hm.get(key)).append(' ');
        }
        out.println(sb);
    }

    static class UnionFind{
        int[] par, size;
        private final int MAX_N;
        UnionFind(int n){
            MAX_N = n;
            par = new int[n];
            size = new int[n];
            for(int i = 1; i < MAX_N; i++)
                par[i] = i;
            Arrays.fill(size, 1);
        }

        int root(int x){
            return par[x] == x ? x : (par[x] = root(par[x]));
        }

        boolean same(int x, int y){
            return root(x) == root(y);
        }

        void unite(int x, int y){
            x = root(x);
            y = root(y);
            if(x == y)
                return;
            if(x < y){
                par[y] = x;
                size[x] += size[y];
            }else{
                par[x] = y;
                size[y] += size[x];
            }
        }

        int size(int x){
            return size[root(x)];
        }
    }

    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }

        String s(){
            try{return readLine();}catch(IOException e){return "";}
        }

        String[] ss(){
            return s().split(" ");
        }

        int i(){
            return Integer.parseInt(s());
        }

        int[] ii(){
            String[] ss = ss();
            int[] ii = new int[ss.length];
            for(int j = 0; j < ss.length; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }

        ArrayList<Integer> li(){
            String[] ss = ss();
            ArrayList<Integer> li = new ArrayList<>();
            for(int j = 0; j < ss.length; j++) li.add(Integer.parseInt(ss[j]));
            return li;
        }

        long l(){
            return Long.parseLong(s());
        }

        long[] ll(){
            String[] ss = ss();
            long[] ll = new long[ss.length];
            for(int j = 0; j < ss.length; j++) ll[j] = Long.parseLong(ss[j]);
            return ll;
        }
    }
}


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

station = [list(map(int, input().split())) for i in range(N - 1)]



def next_start_time(arrive, C, S, F):
    for i in range(1000):
        if arrive > S:
            i = (arrive - S) // F
            if arrive <= S + i * F:
                break
            else:
                i = i + 1
                break
        elif arrive <= S + i * F:
            break
    return S + (i * F) + C


for i in range(N - 1):
    ans = 0
    for j in range(i, N - 1):
        ans = next_start_time(ans, station[j][0], station[j][1], station[j][2])
    print(ans)

print(0)

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

typedef long long ll;

ll N;
vector<ll> A;
ll R;

ll solve() {
  for (ll i = 0; i < N; ++i) {
    R += A[i] / (N + 1);
    A[i] %= N + 1;
  }
  ll a_max = 0;
  for (ll i = 0; i < N; ++i) {
    A[i] += R;
    a_max = max(a_max, A[i]);
  }
  if (a_max >= 2 * N - 1) {
    ll k = a_max - (2 * N - 1);
    R += k * N;
    for (ll i = 0; i < N; ++i) A[i] -= k;
  }
  while (true) {
    auto it = max_element(A.begin(), A.end());
    if (*it <= N - 1) return R;
    ++R;
    *it -= N + 1;
    for (auto &a : A) ++a;
  }
}
int main() {
  cin >> N;
  A.resize(N);
  for (ll i = 0; i < N; ++i) cin >> A[i];
  cout << solve() << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[101],n,b,s;
int main()
{
cin>>n>>b;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)
{
if(a[i]<=b/2)s+=a[i]*2;
else s+=(b-a[i])*2;
}
cout<<s<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

void merge(int *,int,int,int,int);
void Sort(int *,int,int,int);

int c,L[260000],R[260000];

int main(){
  int n,i;
  int S[500000];

  scanf("%d",&n);

  for(i = 0;i < n; i++) scanf("%d",&S[i]);
  Sort(S,n,0,n);
  for(i = 0; i < n; i++){
    if(i) printf(" ");
    printf("%d",S[i]);
  }
  printf("\n");
  printf("%d\n",c);
  
  return 0;
}

void merge(int S[],int n,int left,int mid,int right){
  int n1,n2,i,k,j,a,b;

  n1 = mid - left;
  n2 = right - mid;

  for(i = 0; i < n1; i++) L[i] = S[left + i];
  for(i = 0; i < n2; i++) R[i] = S[mid + i];
  L[n1] = R[n2] = 1000000000;
  
  i = j = 0;
  for(k = left; k < right; k++){
    c++;
    if(L[i] <= R[j]){
      a = i++;
      S[k] = L[a];
    }
    else {
      b = j++;
      S[k] = R[b];
    }
  }
}

void Sort(int S[],int n,int left,int right){
  if(left+1 < right){
    int mid = (left + right)/2;
    Sort(S,n,left,mid);
    Sort(S,n,mid,right);
    merge(S,n,left,mid,right);
  }
}
    



Measured memory_bytes: 5680
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <math.h>

#ifdef _MSC_VER
#pragma warning(disable:4996)
#endif

using namespace std;



long long getlow(long long  n, long long  k) {
	return (k - 1) * k / 2;
}

long long gethigh(long long  n, long long  k) {
	return ((n - k + 1) + n) * k / 2;
}

long long get(long long  n, long long  k) {
	return gethigh(n, k) - getlow(n, k) + 1;
}


int main() {

	int n, k;

	cin >> n >> k;

	long long ans = 0;

	for (; k <= n+1; k++) {
		ans += get(n, k);
	}
	ans %= 1000000007;

	cout << ans;


	return 0;
}


Measured memory_bytes: 3624
N = int(input())
n = list(map(int, str(N)))
a = len(n)

if a % 2 == 0:
    print(int((10**int(a)-1)/11))
else:
    if a == 1:
        print(N)
    else:
        print(int(((100**int(a/2)-1)/11))+N-10**int(a-1)+1)


Measured memory_bytes: 9088
#include <stdio.h>


int main(void){
    int A,B,C;
    int X;

    int AX,BX,CX;
    int Aref, Bref, Cref;
    int Acnt, Bcnt, Ccnt;
    int wrong = 0;
    int ans = 0;
    scanf("%d%d%d%d",&A,&B,&C,&X);
    X = X / 50;
    // 10a + 2b + c = X
    // a <= A, b <= B, c <= C
    // X = 13, a,b,c = (1,1,1),(1,0,3),(0,6,1),(0,5,3),(0,4,5),...,(0,0,13) => 8
    // X = 58, a,b,c = (5,4,0),(5,3,2),...,(4,9,0),(4,8,2),...,(0,0,58) => ??
    Aref = X / 10;
    if (Aref > A){Aref = A;}
    Bref = (X - (Aref * 10)) / 2;
    if (Bref > B){Bref = B;}
    Cref = (X - (Bref * 2) - (Aref * 10));
    if (Cref > C){
        Cref = C;
        wrong = 1;
    }
    Acnt = Aref;
    Bcnt = Bref;
    Ccnt = Cref;

    while(1){
        if (wrong == 1){
            break;
        }
        Bref = Bcnt;
        Cref = Ccnt;
        while(1){
            //printf("(%d,%d,%d)\n",Acnt, Bcnt, Ccnt);
            ans++;            
            if(Bcnt > 0) {
                Bcnt--;
                Ccnt += 2;
                if (Ccnt > C){
                    break;
                }
            } else {
                break;
            }
        }
        Bcnt = Bref;
        Ccnt = Cref;
        //Acnt--
        if(Acnt > 0){
            Acnt--;
            Bcnt = (X - (Acnt * 10)) / 2;
            if (Bcnt > B){ Bcnt = B;}
            Ccnt = (X - (Bcnt * 2) - (Acnt * 10));
            if (Ccnt > C){
                break;
            }
        } else {
            break;
        }
    }
    printf("%d",ans);
    return 0;
}

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

int main() {
	int W, H, x, y, r;
	cin >> W >> H >> x >> y >> r;

	if ((x + r) > W || (y + r) > H) printf("No\n");
	else if ((x - r) < 0 || (y - r) < 0) printf("No\n");
	else printf("Yes\n");
}


Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
long long n,s,sub,a[100005],cc,tt,nw,t;
int main()
{
	cin>>n>>s;
	sub=n-s;
	if(sub<0)cout<<-1<<endl;
	else if(sub==0)cout<<n+1<<endl;
	else
	{
		for(int i=1;i<=sqrt(sub);i++)
		{
			if(sub%i)continue;
			a[++cc]=i;
			nw=0;tt=n;
			while(tt){nw+=(tt%(i+1));tt/=(i+1);}
			if(nw==s){cout<<i+1<<endl;return 0;}
		}
		for(int i=cc;i>=1;i--)
		{
			t=sub/a[i];
			nw=0;tt=n;
			while(tt){nw+=(tt%(t+1));tt/=(t+1);}
			if(nw==s){cout<<t+1<<endl;return 0;}
		}
		cout<<-1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (LLONG_MAX - 1e5)

using namespace std;

int N, A[100005];

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

    cin >> N;

    int sum = 0;
    REP(i, N) cin >> A[i], sum += A[i];

    int a = N * (N + 1) / 2;
    if (sum % a != 0) {
        cout << "NO" << endl;
        return 0;
    }

    int k = sum / a;

    bool ok = true;
    REP(i, N) {
        int next = i == N - 1 ? 0 : i + 1;
        int t = A[next] - A[i];
        if (t - k > 0) ok = false;
        if ((t - k) % N != 0) ok = false;
    }

    if (ok) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;

    }

    return 0;
}


Measured memory_bytes: 1024
A, B, C, X, Y = map(int, input().split())
mi = A * X + B * Y
mi = min(mi, C * 2 * min(X, Y) + (X-min(X, Y)) * A + (Y-min(X, Y)) * B)
mi = min(mi, C * 2 * max(X, Y))
print(mi)

Measured memory_bytes: 3060
char *S[]={"No","Yes"};
char f;

char a[26], b[26];
char *A=a-'a'+1, *B=b-'a'+1;
char s[200000], t[200000], c;
int n, i, j;
int main(){
  while((c=getchar())!=10){s[i++]=c;}
  while((c=getchar())!=10){t[j++]=c;}
  n=i;
  f=1;
  for(i=0; i<n; i++){
    if(A[s[i]]==0){
      A[s[i]]=t[i];
    }else if(A[s[i]]!=t[i]){
      f=0; break;
    }
    if(B[t[i]]==0){
      B[t[i]]=s[i];
    }else if(B[t[i]]!=s[i]){
      f=0; break;
    }
  }
  puts(S[f]);
}


Measured memory_bytes: 512
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<ctime>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file freopen("out1.out","w",stdout);
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REV(a) reverse(a.begin(),a.end())
#define SORT(a) sort(a.begin(),a.end())
#define inf (int)1e9
#define linf (ll)1e18
#define mod (inf+7)

int n;
vi g[111111];
int num[111111];

int main() {
		fastio
		cin>>n;
		int spec=0;
		FOR(i,1,n){
				int a,b;
				cin>>a>>b;
				g[a].push_back(b);
				g[b].push_back(a);
				num[a]++;
				spec=max(spec,num[a]);
				num[b]++;
				spec=max(spec,num[b]);
		}
		if(spec<=2){
				cout<<1<<endl;
				return 0;
		}
		queue<int>q;
		FOR(i,0,n)if(num[i]==1)q.push(i);
		while(!q.empty()){
				int cur=q.front();
				q.pop();
				int to;
				FOR(i,0,g[cur].size()){
						to=g[cur][i];
						if(num[to]>=2)break;
				}
				if(num[to]==2){
						num[to]=1;
						q.push(to);
				}
		}
		int ans=0;
		FOR(i,0,n){
				if(num[i]==1)continue;
				int nn=0;
				for(int j:g[i]){
						if(num[j]==1)nn++;
				}
				ans+=max(0,nn-1);
		}
		cout<<ans<<endl;






		return 0;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int iinf = 1 << 28;
const long long llinf = 1ll << 60;

int main() {
    ll n; cin >> n;
    ll ans = n - 1;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            ll b = n/i;
            ans = min(ans, i+b-2);
        }
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int a, b, c;
    bool ok=true;
    cin>>a>>b>>c;
    for (int i=1; i<=3600 && ok; i++)
    {
        if (i%60==c && i%(a+b)<=a) { cout<<i<<'\n'; ok=false; }
    }
    if (ok) cout<<"-1\n";
    return 0;
}



Measured memory_bytes: 3088
program main
    implicit none
    integer:: n, i
    integer, allocatable:: a(:), b(:)
    integer:: sum_

    read*, n
    sum_ = 0
    allocate(a(n), b(n-1))
    read*, b(1: n-1)

    do i = 1, n-2
        sum_ = sum_ + minval(b(i: i+1))
        
    end do
    print*, sum_ + b(n-1) + b(1)

end program

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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()
#define vprint(v) for(auto e:v){cout<<e<<" ";};cout<<endl;
#define vvprint(vv) for(auto v:vv)vprint(v);

template<typename T=ll>
vector<ll> djkstra(vector<unordered_map<ll, T>> &e, ll src, function<bool(const T&, const T&)> comp=greater<T>()){
    auto c = [&comp](pair<T, ll> l, pair<T, ll> r){ return comp(l.first, r.first); };
    priority_queue<pair<T, ll>, vector<pair<T, ll>>, decltype(c)> q(c);
    vector<T> s(e.size(), LLONG_MAX);
    q.push({0, src});
    while(!q.empty()){
        auto p = q.top();
        q.pop();
        ll d = p.first;
        ll n = p.second;
        if(s[n]<LLONG_MAX) continue;
        s[n] = d;
        for(auto t : e[n]){
            if(s[t.first]<LLONG_MAX) continue;
            q.push({d+t.second, t.first});
        }
    }
    return s;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(20);

    ll N, M, S;
    cin >> N >> M >> S;
    vll U(M), V(M), A(M), B(M);
    vll C(N), D(N);
    rep(i, M) cin >> U[i] >> V[i] >> A[i] >> B[i];
    rep(i, N) cin >> C[i] >> D[i];

    vector<unordered_map<ll, ll>> e(N*2500, unordered_map<ll, ll>());
    rep(i, M) rep(j, 2500){
        if(j-A[i]>=0){
            e[2500*(U[i]-1)+j][2500*(V[i]-1)+j-A[i]] = B[i];
            e[2500*(V[i]-1)+j][2500*(U[i]-1)+j-A[i]] = B[i];
        }
    }
    rep(i, N) rep(j, 2500) e[2500*i+j][2500*i+min(j+C[i], 2499ll)] = D[i];

    auto s = djkstra(e, min(S, 2499ll));
    REP(i, 1, N) cout << *min_element(s.begin()+i*2500, s.begin()+(i+1)*2500) << endl;
}


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

using namespace std;

char s[100010];
int n;

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		if (s[i] != s[i - 1]) ans++;
	}
	cout << ans - 1 << endl;
	return 0;
}

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

int main(){
    int n;
    cin >>n;
    for (int i = 1; i <= n; i++){
        if(i%3==0||i%10==3||i/10%10==3||i/10/10%10==3||i/10/10/10%10==3){
            cout<< ' ' << i ;
        }
    }
    cout<<endl;
}


Measured memory_bytes: 3088
#include <iostream>
using namespace std;
int m,d;
void nb(int);
int cnt = 0;
int main()
{
	cin >> m >> d;
	for(int i = 4; i <= m; i++){
		nb(i);	
	}
	cout << cnt << endl;
	return 0;
}

void nb(int i)
{
	for(int j = 2; j <= i/2; j++){
		if(i % j == 0){
			int x = j;
			int y = i / j;
			if(x < 10 && y < 10){
				if(x * 10 + y <= d) cnt++;
			}
			
		}
	}
	return;
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
  public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in);
    
    String input = scanner.nextLine();
    
    if ((input.equals("AAA")) || (input.equals("BBB"))){
      System.out.println("No");
    } else {
      System.out.println("Yes");
    }
    //System.out.println(input);
    //scanner.close();
  }
}

Measured memory_bytes: 23764
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
	int x, a, b;
	scanf("%d%d%d", &x, &a, &b);
	if (-a + b <= 0)printf("delicious\n");
	else if (-a + b <= x)printf("safe\n");
	else printf("dangerous\n");
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define wrln cout<<'\n';
#define fi first
#define se second
using namespace std;
const int N=3e5+10;
int di[N],dj[N],n,m,sl,k,y,x,i,j,res,dimax,djmax,disum,djsum,sum;
vector <pair <int,int > > luu;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) ;
    cin>>n>>m>>sl;
    x=y=0;
    while (sl--)
    {
        cin>>i>>j;
        di[i]++;
        dj[j]++;
        dimax=max(di[i],dimax);
        djmax=max(dj[j],djmax);
        luu.pb({i,j});
    }
    for (int i=1; i<=n; i++)
        if (di[i]==dimax) disum++;
    for (int i=1; i<=m; i++)
        if (dj[i]==djmax) djsum++;
    sum+=disum*djsum;
    for (auto i:luu)
    {
        if ( di[i.fi]==dimax && djmax ==dj[i.se])
            sum--;
      //  cout<<di[i.fi]<<" "<<dj[i.se]<<" "<<i.fi<<" "<<i.se; wrln;
    }
 //   cout<<sum; wrln;
    cout<<dimax+djmax-(sum==0);
}


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

using namespace std;

template <typename T>
using Ve = vector<T>;

typedef long double ld;
typedef long long ll;

#define FO(i, N) for (int (i) = 0; (i) < (N); ++(i))
#define FOll(i, N) for (ll (i) = 0; (i) < (N); ++(i))
#define READALL(c) for (auto &e : c) { cin >> e; }
#define PRINTALL(c) for (const auto &e : c) { cout << e << "\t"; } cout << "\n";
#define MP(x, y) (make_pair((x), (y)))
#define MT(...) make_tuple(__VA_ARGS__)
#define G(i, x) get<i>(x)
#define ALL(x) begin(x), end(x)

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

	ll N, C;
	cin >> N >> C;

	Ve<ll> X(N), V(N);
	FO(i, N) {
		cin >> X[i] >> V[i];
	}

	ll ans = 0, running = 0;

	multiset<ll> clock, counter;
	Ve<ll> clockvec(N), countervec(N);

	FO(i, N) {
		running += V[i];
		clock.insert(running-X[i]);
		clockvec[i] = (running-X[i]);
		ans = max(running-X[i], ans);
	}

	ll dist = 0, loc = C;
	running = 0;

	for (int i = N-1; i >= 0; --i) {
		dist += loc-X[i];
		loc = X[i];
		running += V[i];

		counter.insert(running-dist);
		countervec[i] = (running-dist);
		ans = max(running-dist, ans);
	}

	running = 0;

	FO(i, N-1) {
		running += V[i];
		counter.erase(counter.find(countervec[i]));
		ans = max(ans, running-X[i]*2+*counter.rbegin());
	}

	// cout << ans << endl;

	dist = 0, loc = C, running = 0;

	for (int i = N-1; i > 0; --i) {
		dist += loc-X[i];
		loc = X[i];
		running += V[i];

		// cout << i << " " << running << " " << dist << " " << *clock.rbegin() << endl;

		clock.erase(clock.find(clockvec[i]));
		ans = max(running-dist*2+*clock.rbegin(), ans);
	}

	cout << ans << endl;
	
}

Measured memory_bytes: 12800
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("-funsafe-loop-optimizations")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
const int maxn = 2e5 + 33, mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, vis[33][33], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
char mat[33][33];
int bfs(int x, int y) {
	memset(vis, 0, sizeof vis);
	vis[x][y] = 1;
	int ans = 0;
	queue<pi> q;
	q.push(pi{x, y});
	while(!q.empty()) {
		tie(x, y) = q.front();
		q.pop();
		ans = vis[x][y];
//		cout << x << " " << y << " " << vis[x][y] << "\n";
		for(int i = 0; i < 4; i++) {
			int tx = x + dx[i], ty = y + dy[i];
//			cout << tx << " " << ty << "\n";
			if(tx<0||ty<0||tx>=n||ty>=m) continue;
//			cout << tx << " " << ty <</<< "\n";
			if(vis[tx][ty]||mat[tx][ty]=='#') continue;
			q.push({tx, ty});
			vis[tx][ty] = vis[x][y]+1;
		}
	}
	return ans-1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    int ans = 0;
    for(int i = 0; i <n ; i++)
    	for(int j = 0;j < m; j++) {
    		cin >> mat[i][j];
    	}
    for(int i = 0; i <n ; i++)
    	for(int j = 0;j < m; j++)
    		if(mat[i][j]!='#')
    		ans = max(ans, bfs(i, j));
//    bfs(n-1, 0);
    cout << ans;
}


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

const int INF = 1012345678;

int main()
{
	int a, b, c, d = 0;
	cin >> a >> b >> c >> d;
	int L = a + b;
	int R = c + d;
	string ans = "";
	if (L == R)
	{
		ans = "Balanced";
	}
	else if (L > R)
	{
		ans = "Left";
	}
	else
	{
		ans = "Right";
	}

	cout << ans << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef long long int ll;
typedef long int li;

int main(void){
    ll ans=0;
    ll k,a,b;
    cin >> k >> a >> b;
    if(b<=a+1)ans=k+1;
    else{
        ll j=k/(a+2);
        ll x=j*a-1;
        ll y=2*(x+1)/a;
        ans = (x+1)*(b/a)+(k-x-y);
      	ll ans2;
      	ll xy=(k-a+1)/2;
      	ans2=xy*(b-a)+((k-a+1)%2)+a;
      ans=max(ans,ans2);
    }
    cout << ans << endl;
}



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

int main() {
    int N;
    cin >> N;
    vector<int> V(N);
    for (int i = 0; i < N; i++)
        cin >> V[i];
    vector<int> C(N);
    for (int i = 0; i < N; i++)
        cin >> C[i];
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (V[i] - C[i] > 0) {
            ans += V[i] - C[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define mp make_pair
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using ll = long long;
using namespace std;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int a,b;
int main(){
    cin >> a >> b;
    cout << (a+b+1)/2 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
#include<complex>
#include<stack>
#include<queue>
#include<unordered_map>
#include<map>
using namespace std;

int main() {
  long long int h, n, i;
  vector<long long int> v;
  long long int u[200000];
  cin >> n;

  for (i = 0; i < n; i++) {
    cin >> h;
    v.push_back(h);
  }

  u[0] = 0;
  u[1] = abs(v[1] - v[0]);

  for (i = 2; i < n; i++) {
    u[i] = min(u[i-2] + abs(v[i-2] - v[i]), u[i-1] + abs(v[i-1] - v[i]));
  }

  cout << u[n - 1] << endl;

}


Measured memory_bytes: 1908
function Main(input) {
  input = input.split("\n");
  var n = parseInt(input[0]);
  tmp = input[1].split(" ");
  a=new Array(n).fill(0);
  for(i=0;i<n;i++){
    a[i]=parseInt(tmp[i]);
  }
  var odd=0;
  var four=0;
  for(i=0;i<n;i++){
    if(a[i]%2==1){
      odd++;
    }else if(a[i]%4==0){
      four++;
    }
  }
  var ans="No";
  if(odd==0){
    ans="Yes";
  }else if(odd-four<=0){
    ans="Yes";
  }else if(n==3&&odd-four<=1&&four>0){
    ans="Yes";
  }else if(n%2==1&&odd-four<=1){
    ans="Yes";
  }
  console.log('%s', ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 17484
#include<bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i=0; i<v.size(); i++) {
        cin >> v[i];
    }
    sort(v.begin(),v.end()) ;
    long long ans = 0;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            int val = v[i]+v[j];
            int index = lower_bound(v.begin(),v.end(),val) - v.begin() - j-1;
            // cout << index << endl;
            ans += index;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)

#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))

#define endl "\n"
#define pb push_back
#define rtn return
#define elif else if

#define MOD 1000000007
 
const int dx[]={1,0,-1,0}, dy[]={0,-1,0,1};
const int dx_8[]={1,1,0,-1,-1,-1,0,1}, dy_8[]={0,-1,-1,-1,0,1,1,1};

typedef long long ll;
typedef unsigned long long ull;

template <typename T>
inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template <typename T>
inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template <typename T>
inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template <typename T>
inline T nHr(T a,T b){return nCr(a+b-1,b);}
template <typename T>
inline T POW(T a,T b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

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

	int n, v[100000];
	cin >> n;
	REP(i, n) cin >> v[i];

	int k = v[0];
	bool same = true;
	REP(i, n){
		if(k != v[i]) same = false;
	}
	if(same){
		cout << n/2 << endl;
		rtn 0;
	}
	map<int, int> odd;
	map<int, int> even;

	for(int i = 0;i < n;i+=2) odd[v[i]]++;
	for(int i = 1;i < n;i+=2) even[v[i]]++;

	int omax = -1, emax = -1;
	int a, b;
	for(auto it = odd.begin();it != odd.end();it++){
		if(omax < it->second){
			omax = it->second;
			a = it->first;
		}
	}
	for(auto it = even.begin();it != even.end();it++){
		if(emax < it->second){
			int max = it->second;
			int p = it->first;
			if(a == p) continue;
			else{
				b = p;
				emax = max;
			}
		}
	}

	map<int, int> oddd;
	map<int, int> evenn;

	for(int i = 0;i < n;i+=2) oddd[v[i]]++;
	for(int i = 1;i < n;i+=2) evenn[v[i]]++;

	int oomax = -1, eemax = -1;
	int aa, bb;
	for(auto it = evenn.begin();it != evenn.end();it++){
		if(eemax < it->second){
			eemax = it->second;
			bb = it->first;
		}
	}
	for(auto it = oddd.begin();it != oddd.end();it++){
		if(oomax < it->second){
			int max = it->second;
			int p = it->first;
			if(bb == p) continue;
			else{
				aa = p;
				oomax = max;
			}
		}
	}
	
	cout << min(n/2-odd[a] + n/2-even[b], n/2-oddd[aa] + n/2-evenn[bb]) << endl;

	rtn 0;
}

Measured memory_bytes: 9984
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
using ull = unsigned long long;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

int main()
{
	ull w, h, x, y;
	cin >> w >> h >> x >> y;
	if (x == w / 2.0 && y == h / 2.0) {
		cout << (w * h / 2.0);
		cout << " ";
		cout << 1;
	}
	else {
		cout << (w * h / 2.0);
		cout << " ";
		cout << 0;
	}
}


Measured memory_bytes: 256
n = gets.to_i
txy = n.times.map{gets.split.map &:to_i}

t = x = y = 0

txy.each{|(net,tox,toy)|
  able = true
  
  dis = (x-tox).abs + (y-toy).abs
  able = false if (net-t)<dis
  able = false if (net-t)%2!=dis%2
  
  if !able
    puts 'No'
    exit
  end
  
  t = net
  x = tox
  y = toy
}

puts 'Yes'


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

using namespace std;

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

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

    long long a, b;
    cin >> a >> b;
    cout << a * b / gcd(a,b) << endl;

    return 0;
}



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

using namespace std;

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

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

vector<int> g[1000000];
int in[1000000];
bool use[1000000];
int dp[1000000];

int main() {
  int n;
  cin >> n;
  REP(i, n) {
    vector<int> vc;
    REP(j, n - 1) {
      int a;
      cin >> a;
      vc.push_back(a - 1);
    }
    REP(j, n - 1) {
      if (j) {
        int a = i;
        int b = vc[j - 1];
        int c = i;
        int d = vc[j];
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        g[1000 * a + b].push_back(1000 * c + d);
        use[1000 * a + b] = true;
        use[1000 * c + d] = true;
        in[1000 * c + d]++;
      }
    }
  }
  queue<int> que;
  REP(i, 1000000) {
    if (in[i] == 0 && use[i]) que.push(i);
  }
  vector<int> ts;
  while (que.size()) {
    int p = que.front();
    que.pop();
    ts.push_back(p);
    REP(i, g[p].size()) {
      int q = g[p][i];
      in[q]--;
      if (in[q] == 0) que.push(q);
    }
  }
  REP(i, 1000000) {
    if (in[i] != 0 && use[i]) {
      cout << -1 << endl;
      return 0;
    }
  }
  REP(i, ts.size()) {
    int cur = ts[i];
    REP(j, g[cur].size()) {
      int to = g[cur][j];
      dp[to] = max(dp[to], dp[cur] + 1);
    }
  }
  int ans = 0;
  REP(i, 1000000) ans = max(ans, dp[i]);
  cout << ans + 1 << endl;
  return 0;
}

Measured memory_bytes: 50168
#include<stdio.h>
int n,s,ans;
void F(depth,t,sum)
{
    if(depth==10)
    {
        if(t==n&&sum==s)
        {
            ans++;
        }
        return;
    }
    F(depth+1,t+1,sum+depth);
    F(depth+1,t,sum);
}
int main(void)
{
    while(scanf("%d %d",&n,&s),n+s)
    {
        F(0,0,0);
        printf("%d\n",ans);
        ans=0;
    }
}

Measured memory_bytes: 600
// ABC172-E
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define e_b emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ipair;
typedef pair<ll,ll> lpair;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る
void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る


vector<ll> fact(500020);
vector<ll> invfact(500020);
ll modpow(ll x,ll y,ll mod){ //x^y
    if(y==0) return 1;
    if(y==1) return x%mod;
    if(y%2==1) return x*modpow(x,y-1,mod)%mod;
    ll t=modpow(x,y/2,mod);
    return (t*t)%mod;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    ll n,m;
    ll mod=1000000007;
    cin>>n>>m;
    fact[0]=1;
    for(int i=1;i<=500010;i++){
        fact[i]=fact[i-1]*i%mod;
    }
    invfact[500010]=modpow(fact[500010],mod-2,mod);
    for(int i=500009;i>=0;i=i-1){
        invfact[i]=invfact[i+1]*(i+1)%mod;
    }
    ll ans=0;
    for(int k=0;k<=n;k++){
        ll cur=1;
        if(k%2==1) cur=-1;
        //nCk
        cur=cur*fact[n]*invfact[k]%mod;
        if(cur<0) cur+=mod; //curが負の可能性がある
        cur=cur*invfact[n-k]%mod;
        //mPk
        cur=cur*fact[m]%mod*invfact[m-k]%mod;
        //(m-k)P(n-k)^2
        ll nijo=fact[m-k]*invfact[(m-k)-(n-k)]%mod;
        nijo=modpow(nijo,2,mod);
        cur=cur*nijo%mod;
        ans+=cur;
        ans%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 11036
import java.util.Scanner;

class Main{
	static long f(long n,long k){
		if(gcd(n,k)!=1){
			long g=gcd(n,k);
			return g*f(n/g,k/g);
		}
		else return 3*n-3;
	}
	static long gcd(long x,long y){
		if(Math.max(x,y)%Math.min(x,y)==0) return Math.min(x,y);
		else return gcd(Math.min(x,y),Math.max(x,y)%Math.min(x,y));
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			long n=sc.nextLong();
			long x=sc.nextLong();
			System.out.println(f(n,x));
		}
	}
}

Measured memory_bytes: 9552
import numpy as np
from collections import defaultdict
from collections import Counter
from collections import OrderedDict
#key = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}
# A = int(input())
N = int(input())
S = input()

R_sum = 0
B_sum = 0
for i in range(N):
    if S[i] == 'R':
        R_sum += 1
    else:
       B_sum += 1
if R_sum > B_sum:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 12508
//
// Created by 李青坪 on 2018/10/27.
//

#include <cstdio>
#include <string>
#include <iostream>
#define MAXN 2000001
using namespace std;

int pQueue[MAXN];
int H = 0; // 记录优先级队列中有多少个结点了

void exchange(int i, int j){
    int temp = pQueue[i];
    pQueue[i] = pQueue[j];
    pQueue[j] = temp;
}

void insert(int value){
    ++H;
    pQueue[H] = value;
    int i = H;
    while (i/2 > 0){
        if (pQueue[i] > pQueue[i/2]){
            exchange(i, i/2);
        }
        i /= 2;
    }
}

int maxHeapJudge(int i){
    int l = i*2;
    int r = l+1;
    int largest = i;
    if (l <= H && pQueue[l] > pQueue[i]){
        largest = l;
    }
    if (r <= H && pQueue[r] > pQueue[largest]){
        largest = r;
    }
    if (largest != i){
        exchange(i, largest);
        maxHeapJudge(largest);
    }
}

int extract(){
    if (H < 1) return -1;
    int max = pQueue[1];
    pQueue[1] = pQueue[H];
    --H;
    maxHeapJudge(1);
    return max;
}

int main(){
    string command;
    cin >> command;
    int value;
    while (command != "end"){
        if (command == "insert"){
            scanf("%d", &value);
            insert(value);
        } else if (command == "extract"){
            printf("%d\n", extract());
        }
        cin >> command;
    }
}
/*
insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end

 */


Measured memory_bytes: 7196
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {

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

    if (b*2>=a) {
        printf("0");
    } else{
        printf("%d", a-b*2);
    }
    return 0;

}


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

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

bool chk[128];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	TEST(freopen("debug.txt", "w", stderr));
	int cnt=0, ans=0;
	string s;
	chk['A']=chk['T']=chk['G']=chk['C']=1;
	cin>>s;
	for(auto c: s) {
		if(chk[c]) ans=max(ans,++cnt);
		else cnt=0;
	}
	cout<<ans<<'\n';
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
#define     mod            (int)1e9+7
#define     MOD             998244353
#define     ll              long long
#define     mp              make_pair
#define     F               first
#define     S               second
#define     t()             int test;cin>>test;while(test--)
#define     ii              pair<int,int>
#define     que_max         priority_queue <int>
#define     IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define     endl            "\n"
#define     sz(x)           (int)(x).size()
#define     grid            vector<vector<ll> >
typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << endl;
  //use cerr if u want to display at the bottom
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ','); cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
#else
#define trace(...)
#endif

int const p = 1000000007;

vector<string> path;

bool valid(int r, int c)
{
  if (r >= 0 && c >= 0 && path[r][c] == '.')
    return true;

  return false;
}


int main()
{
#ifndef ONLINE_JUDGE
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif

  IOS;

  int n, m;

  cin >> n >> m;

  path.resize(n);

  for (auto& i : path)cin >> i;

  grid dp(n + 1, std::vector<ll>(m + 1, 0));

  dp[0][0] = 1;

  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (valid(i - 1, j))
        dp[i][j] = ((dp[i][j] % p) + (dp[i - 1][j] % p)) % p;

      if (valid(i, j - 1))
        dp[i][j] = ((dp[i][j] % p) + (dp[i][j - 1] % p)) % p;
    }
  }

  cout << dp[n - 1][m - 1] << endl;





}

Measured memory_bytes: 12176
import bisect

def main():
    n, *l = map(int, open(0).read().split())
    l = sorted(l, reverse=True)

    ans = 0
    for a_i in range(n-2):
        a = l[a_i]
        b_i = a_i + 1
        c_i = n - 1
        while b_i < c_i:
            b = l[b_i]
            c = l[c_i]
            if a < b + c:
                b_i += 1
                ans += c_i - b_i + 1
            else:
                c_i -= 1
    print(ans)
    return()

if __name__ == '__main__':
    main()


Measured memory_bytes: 3188
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}

int main() {
	ll N,an=1;
	cin >> N;
	while (N > 0) {
		N -= an;
		an++;
	}


	cout << an-1 << endl;
}


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

using namespace std;
#define inf 101010
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<pii,pii> pp;

int w,h;
int g[61][31];
vector<pii> st;
vector<pii> gl;
priority_queue<pp, vector<pp>, greater<pp> > que;
vector<vector<vector<int> > > d;

bool r(int y, int x) {
    if (y >= 0 && y < h && x >= 0 && x < w) return true;
    else return false;
}

void solve() {
    int ans = inf;
    while (!que.empty()) {
        pp p = que.top(); que.pop();
        int cost = p.first.first, foot = p.first.second;
        int ty = p.second.first, tx = p.second.second;
        if (g[ty][tx] == 10) {
            ans = cost-10;
            break;
        }
        
        for (int i = 1; i < 4; i++) {
            for (int j = -3+i; j < 4-i; j++) {
                int t = i * (1 - 2*foot); // 0 then +1, 1 then -1 so foot 0 is left, foot 1 is right
                int ny = ty+j, nx = tx+t;
                int co = g[ny][nx];
                if (!r(ny,nx) || g[ny][nx] == -1) continue;
                
                if (d[1-foot][ny][nx] > cost + co) {
                    d[1-foot][ny][nx] = cost+co;
                    que.push(mp(mp(cost+co, 1-foot), mp(ny, nx)));
                }
            }
        }
    }
    if (ans == inf) cout << -1 << endl;
    else cout << ans << endl;
}


int main(void){
    while (cin>>w>>h && w) {
        st.clear();
        gl.clear();
        priority_queue<pp, vector<pp>, greater<pp> > que2;
        que = que2;
        vector<vector<vector<int> > > d2(2, vector<vector<int> >(h+1, vector<int>(w+1, inf)));
        d = d2;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                char c;
                cin >> c;
                if (c == 'S') {
                    g[i][j] = -1;
                    que.push(mp(mp(0, 0), mp(i, j)));
                    que.push(mp(mp(0, 1), mp(i, j)));
                    d[0][i][j] = 0;
                    d[1][i][j] = 0;
                }
                else if (c == 'T') g[i][j] = 10;
                else if (c == 'X') g[i][j] = -1;
                else g[i][j] = c-'0';
            }
        }
        solve();
    }
}

Measured memory_bytes: 3204
from itertools import permutations

n = int(input())
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))
if p == q:
    print(0)
    exit()
base = sorted(p)
pi = 0
qi = 0
for i, v in enumerate(permutations(base, n)):
    if p == v:
        pi = i + 1
    elif q == v:
        qi = i + 1
        
    if pi * qi != 0:
        break
# print(f"{pi} {qi}")
print(abs(pi-qi))




Measured memory_bytes: 3064
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=1e3+1e2+7;

int n,a[N],sum;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i],sum+=a[i];
	sort(a+1,a+n+1);
	for(int i=0;i<=n;i++)
	{
		if((sum-a[i])%10!=0)
		{
			cout<<sum-a[i]<<endl;
			return 0;
		}
	}
	cout<<0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s; cin>>s;
	cout<<s[0]<<s[1]<<s[2]<<endl;
	return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <limits>
using namespace std;
// 素因数分解
typedef pair<long long, long long> P;
vector<P> prime_factorize(long long n)
{
    vector<P> res;
    for (long long p = 2; p * p <= n; ++p)
    {
        if (n % p != 0)
            continue;
        int num = 0;
        while (n % p == 0)
        {
            ++num;
            n /= p;
        }
        res.push_back(make_pair(p, num));
    }
    if (n != 1)
        res.push_back(make_pair(n, 1));
    return res;
}
// 因数分解
long long gcd(long long x, long long y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return gcd(y, x % y);
    }
}
const int MOD = 1000000007;
typedef long long unsigned int ll;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for (int i = 0; i < (n); i++)

int main()
{
    int k, n;
    cin >> k >> n;
    vector<int> A(n);
    rep(i, n)
    {
        cin >> A[i];
    }
    vector<int> seg(n);
    rep(i, n - 1)
    {
        seg[i] = A[i + 1] - A[i];
    }
    seg[n - 1] = A[0] + k - A[n - 1];
    sort(seg.begin(), seg.end());
    int ans = 0;
    rep(i, n - 1)
    {
        ans += seg[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4804
using System;
using System.Text;


namespace ABC126
{
    class Program
    {
        static int Main(string[] args)
        {
            ProblemA();
            return 0;
        }

        static int ProblemA()
        {
            string[] K = System.Console.ReadLine().Split(' ');
            string S = System.Console.ReadLine();
            string L = S.ToLower();
            char[] Answer = new char[S.Length];

            for(int i = 0; i < S.Length; i++)
            {
                if(i == int.Parse(K[1])-1)
                {
                    Answer[i] = L[i];
                }
                else
                {
                    Answer[i] = S[i];
                }
            }

            Console.WriteLine(Answer);

            return 0;
        }
    }


}


Measured memory_bytes: 11092
import java.util.Scanner;

public class Main {
    public static void main(String... args) {
        Scanner scanner = new Scanner(System.in);
        
        // MODの数値間違ってた・・・
        long MOD = 1000000007L;

        int N = scanner.nextInt();
        int[] A = new int[N];
        long sum = 0L;

        for (int i = 0; i < N; i++) {
            A[i] = scanner.nextInt();

            sum += A[i];

            // これ忘れてた
            sum %= MOD;
        }

        long result = 0L;
        for (int i = 0; i < N; i++) {
            sum -= A[i];

            if (sum < 0) {
                sum += MOD;
            }

            result += A[i] * sum;
            result %= MOD;
        }

        System.out.println(result);
    }
}

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

int main() {
  int n;
  while ( cin >> n , n) {
    int cnt_l = 0,cnt_d = 0,cnt_m = 0;
    int l = 0,d = 0,mid = 0;
    for ( int i = 0; i < n; i++ ) {
      int h,m,t;
      scanf("%d%*c%d%d",&h,&m,&t);
    
      if ( h < 2 ) h += 24;
      int time = t - m;
      if ( m > t ) time += 60;
    
      if ( 11 <= h && h <= 14 ) {
	cnt_l++;
	if ( time <= 8 ) l++;
      }else if ( 18 <= h && h <= 20 ) {
	cnt_d++;
	if ( time <= 8 ) d++;
      }else if ( 21 <= h && h <= 25 ) {
	cnt_m++;
	if ( time <= 8 ) mid++;
      }

    }

    if ( cnt_l == 0 && l == 0 ) cout << "lunch no guest" << endl;
    else cout << "lunch" << " " << l *100/cnt_l << endl;
  
    if ( cnt_d == 0 && d == 0 ) cout << "dinner no guest" << endl;
    else cout << "dinner" << " " << d *100/cnt_d << endl;
  
    if ( cnt_m == 0 && mid == 0 ) cout << "midnight no guest" << endl;
    else cout << "midnight" << " " << mid *100/cnt_m << endl;
  }

  return 0;
}

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

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

    int n = s.length();

    vector<vector<int>> dp(n, vector<int>(2));
    dp[0][0] = s[0] - '0';
    dp[0][1] = s[0] - '0' - 1;
    for(int i=0; i+1<n; i++){
        dp[i+1][0] = dp[i][0] + s[i+1] - '0';
        dp[i+1][1] = dp[i][1] + 9;
        if(s[i+1] - '0' >= 1) dp[i+1][1] = max(dp[i+1][1], dp[i][0] + (s[i+1] - '0' - 1));
    }
    //cout << dp[n-1][0] << " " << dp[n-1][1] << endl;
    cout << max(dp[n-1][0], dp[n-1][1]) << endl;
    return 0;
}

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

typedef long long ll;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

//read_kaisetsu
int main() {
    int n,a;cin>>n>>a;
    int x[n];rep(i,n)cin>>x[i];
    sort(x,x+n);
    int m=max(x[n-1],a);
    
    ll dp[n+1][n+1][n*m+1];

//    dp[0][0][0] = 1;
    rep(i,n+1)rep(j,n+1)rep(k,n*m+1){
        if(i==0 && j==0 && k==0)dp[i][j][k]=1;
        else if(i>=1 && k < x[i-1])dp[i][j][k]=dp[i-1][j][k];
        else if(i>=1 && j>=1 && k >= x[i-1])dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]];
        else dp[i][j][k]=0;
    }
    ll ans = 0;
    for(int i=1;i<=n;++i)ans+=dp[n][i][i*a];
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 54432