akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define FOR(i,a,b) for(long long i=a; i<b; i++)
#define ll long long
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define PB(x) push_back(x)
#define MP make_pair
#define f first
#define s second
#define ld long double
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<'Y'<<'e'<<'s'<<endl
#define coutn cout<<'N'<<'o'<<endl
#define coutY cout<<'Y'<<'E'<<'S'<<endl
#define coutN cout<<'N'<<'O'<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
const long long dx[4]={1,0,-1,0};
const long long dy[4]={0,1,0,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    int n; cin >> n;
    vint a(n);
    rep(i,n){
        cin >> a[i];
        if(a[i]==0){
            cout<<-0<<endl;
            return 0;
        }
    }
    int res=1;
    rep(i,n){
        if(a[i]>1e18/res){
            cout<<-1<<endl;
            return 0;
        }
        res*=a[i];
    }
    if(res>(ll)1e18) cout<<-1<<endl;
    else cout<<res<<endl;
}

Measured memory_bytes: 4064
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
A = [a for a, _ in AB]
B = [b for _, b in AB]
A.sort()
B.sort()

if N % 2 == 1:
    mi = A[N // 2]
    mx = B[N // 2]
    print(mx - mi + 1)
else:
    mi = A[N // 2] + A[N // 2 - 1]
    mx = B[N // 2] + B[N // 2 - 1]
    print(mx - mi + 1)


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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int T = sc.nextInt();
        int[][] AB = new int[N][2];
        for (int i = 0; i < N; i++) {
            AB[i][0] = sc.nextInt();
            AB[i][1] = sc.nextInt();
        }

        Arrays.sort(AB, (a, b) -> a[0] - b[0]);

        int max = 0;
        int[] dp = new int[T];

        for (int i = 0; i < N; i++) {
            int a = AB[i][0];
            int b = AB[i][1];
            max = Math.max(max, dp[T-1] + b);
            for (int j = T - 1; j >= 0; j--) {
    
                if (j >= a) {
                    dp[j] = Math.max(dp[j], dp[j-a] + b);
                }
            }
        }
        System.out.println(max);
    }
}


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

// main.cpp

int main() {
  std::int_fast64_t n;
  std::cin >> n;
  std::vector<std::int_fast64_t> a;
  a.reserve(n);
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), n, std::back_inserter(a));

  std::sort(a.begin(), a.end(), std::greater<std::int_fast64_t>());
  std::vector<std::int_fast64_t> alice;
  std::vector<std::int_fast64_t> bob;
  for (std::int_fast64_t i = 0; i < n; ++i) {
    if (i % 2 == 0) alice.push_back(a[i]);
    else bob.push_back(a[i]);
  }

  std::cout << std::accumulate(alice.begin(), alice.end(), static_cast<std::int_fast64_t>(0)) - std::accumulate(bob.begin(), bob.end(), static_cast<std::int_fast64_t>(0)) << std::endl;
  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp3
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            var imp = Console.ReadLine().Split(' ');
            int[] ary = new int[N];
            int H = 0;
            int count = 1;
            for(int i = 0; i < N; i++)
            {
                ary[i] = int.Parse(imp[i]);
            }
            for (int j = 1; j < N; j++)     //j個の旅館
            {
                int[] newone = new int[j];
                Array.Copy(ary, 0, newone, 0, j);
                H = newone.Max();
                //Console.WriteLine(H);
                if (H <= ary[j])
                {
                    count += 1;
                }
            }
            Console.WriteLine(count);
            //System.Threading.Thread.Sleep(3000);
        }
    }
    
}


Measured memory_bytes: 13268
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void MealDelivery() {
	int x, a, b;
	cin >> x >> a >> b;
	cout << (abs(x - a) < abs(x - b) ? "A" : "B") << endl;

}
int main() {

	MealDelivery();
	return 0;
}


Measured memory_bytes: 768
#include<iostream>
using namespace std;
int main(){
	int n;
	cin >>n;
	int l;
	int max=0;
	int sum=0;
	for(int i=0;i<n;i++){
		cin>>l;
		if(max<l)
			max=l;
		sum+=l;
	}

if(max*2>=sum)
	cout<<"No";
else
	cout<<"Yes";



	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <assert.h>
#include <string>
#include <set>
#include <map>
using namespace std;
#define LL long long

int n,m;
int bm[12], sm[12];
int init = 0;

int main(){

	scanf("%d%d",&n,&m);
	for ( int i = 0; i < m; i++ ){
		int mask = 0;
		int k,x;
		scanf("%d",&k);
		while ( k-- ){
			scanf("%d",&x);
			x--;
			bm[x] |= (1<<i);
		}
	}

	int mask = 0;
	for ( int i = 0; i < m; i++ ){
		int p;
		scanf("%d",&p);
		if ( p == 1 ) mask |= (1<<i);
	}

	int ans = 0, mask2 = 0;
	for ( int i = 0; i < (1<<n); i++ ){
		mask2 = 0;
		for ( int j = 0; j < n; j++ ){
			if ( (i>>j) & 1 ) mask2 ^= bm[j];
		}
		if ( mask2 == mask ){
			ans++;
		}
	}

	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
//Written by Zhu Zeqi
//Come on,baby
//Hack,please
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define MAX 100000000000000000
#define MOD 1000000007
#define PI 3.141592653589793238462
#define INF 1000000000
typedef long long ll;
using namespace std;
int main(){
	//freopen("input.in","r",stdin);
	//freopen("output.out","w",stdout);
	int a,b,c;
	cin>>a>>b>>c;
	if(b-a==c-b)
	cout<<"YES";
	else
	cout<<"NO";
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int s = sc.nextInt();
        
        if (k == 0) {
            for (int i = 0; i < n; i++) {
                if (s == 1000000000) {
                    System.out.print(2);
                } else {
                    System.out.print(s+1);
                }
                if (i != n - 1) {
                    System.out.print(" ");
                } else {
                    System.out.println();
                return;
                }
            }
        }
        
        int[] array = new int[n];
        
        for (int i = 0; i < k - 1; i++) {
            array[i] = s;
        }
        
        int tmp = n - (k - 1);
        boolean komaru = false;
        if (tmp > s) {
            komaru = true;
        }
        
        
        if (tmp == s) {
            for (int i = k - 1; i < n; i++) {
                array[i] = 1;
            }
            
            for (int i = 0; i < n; i++) {
                System.out.print(array[i]);
                if (i != n - 1) {
                    System.out.print(" ");
                } else {
                    System.out.println();
                return;
                }
            }
        }
        
        if (komaru) {
            for (int i = k - 1; i < n - 1; i++) {
                if (s == 1000000000) {
                    array[i] = 2;
                } else {
                    array[i] = s + 1;
                }
            }
            array[n - 1] = s;
            
            for (int i = 0; i < n; i++) {
                System.out.print(array[i]);
                if (i != n - 1) {
                    System.out.print(" ");
                } else {
                    System.out.println();
                return;
                }
            }
        } else {
            for (int i = k - 1; i < n - 1; i++) {
                array[i] = 1;
            }
            array[n - 1] = s - (n - k);
            
            for (int i = 0; i < n; i++) {
                System.out.print(array[i]);
                if (i != n - 1) {
                    System.out.print(" ");
                } else {
                    System.out.println();
                return;
                }
            }
        }
    }
}


Measured memory_bytes: 43588
#include <stdio.h>

int main(void)
{
  int n, m, i, j, ans, tmp, now;
  int kyori[100000];

  scanf("%d %d", &n, &m);

  kyori[0] = 0;
  for(i = 1; i < n; i++){
    scanf("%d", &tmp);
    kyori[i] = kyori[i - 1] + tmp;
  }

  ans = now = 0;

  for(i = 0; i < m; i++){
    scanf("%d", &tmp);
    if(tmp > 0){
      ans += kyori[now + tmp] - kyori[now];
    }else{
      ans += kyori[now] - kyori[now + tmp];
    }
    now += tmp;
    ans %= 100000;
  }
  
  printf("%d\n",ans);
  return 0;


} 

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


public class Main {
	public static void main (String[] args) {
	Scanner s=new Scanner(System.in);
	int n=s.nextInt();
	long ans=0;
	for(int i=1;i<=n;i++)
	{if(i%3==0 || i%5==0)
	{}
	else
	ans+=i;
	}
	System.out.println(ans);
	}
}

Measured memory_bytes: 35788
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define r(i, j) for (int i = 1; i <= j; i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int N, M, Q;
int A[55], B[55], C[55], D[55];
int ans = 0;

void dfs(vec<int> Z) {
    int size = Z.size();
    if (size == N) {
        int tmpans = 0;
        rep(i, Q) {
            if (Z[B[i]] - Z[A[i]] == C[i]) tmpans += D[i];
        }
        ans = max(ans, tmpans);
        return;
    }

    for (int i = Z.back(); i <= M; ++i) {
        Z.push_back(i);
        dfs(Z);
        Z.pop_back();
    }
}

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

    rep(i, Q) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        --A[i];
        --B[i];
    }
    dfs(vec<int>(1, 1));
    cout << ans << endl;
}


Measured memory_bytes: 3580
// This file is a "Hello, world!" in Java language by OpenJDK for wandbox.

import java.util.*;
import java.io.*;

class Main
{
	public static void main(String[] args){
		new Main().run();
	}
	
	long sz(long a){
		int r=0;
		while(a>0){a/=2;r++;}
		return r;
	}
	//100
	//10,10
	//1,1,1,1
	//2^0+2^1+2^2=2^3-1
	void run(){
		Scanner sc=new Scanner(System.in);
		long H=sc.nextLong();
		System.out.println((1L<<sz(H))-1);
	}
}

// OpenJDK reference:
//   http://openjdk.java.net/

// Java language references:
//   http://docs.oracle.com/javase


Measured memory_bytes: 23252
from sys import stdin

[N, K] = [int(x) for x in stdin.readline().rstrip().split()]
#この場合、10^100は無視しても大丈夫ではない
#足した個数によって10^100の桁の数が変わるので、問題が単純になる。
#これ少し考えればわかるけれど、
#0, 1, 2, ..., N からK個足してできる数は
#最小の値 0+1+2+...+K-1
#最大の値 N-K+1 + N-K+2 + ...+ N
#の間の任意の整数をとりうる。
#したがって、
# # (2N-K+1)*K/2 - (K-1)*K/2 + 1をK~Nについて計算すればよろしい

num_sum = 0
waru = 10**9+7
for i in range(K, N+2):
    num_sum += (2*N - i + 1)*i/2 - (i-1)*i/2 + 1
    #print(i,num_sum)
    num_sum = num_sum%waru

print(int(num_sum))




Measured memory_bytes: 67544
// SeptEtavioxy
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include<cmath>
#define re register
#define ll long long
#define il inline
#define rep(i,s,t) for(re int i=(s);i<=(t);i++)
#define rev_rep(i,s,t) for(re int i=(s);i>=(t);i--)
#define each(i,u) for(int i=head[u];i;i=bow[i].nxt)
#define pt(ch) putchar(ch)
#define pti(x) printf("%d",x)
#define ptll(x) printf("%lld",x)
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
using namespace std;
// c_ints
il int ci(){
	re char ch;int f=1;
	while(!isdigit(ch=getchar()))f= ch=='-'?-1:1 ;
	re int x= ch^'0';
	while(isdigit(ch=getchar()))x=(x*10)+(ch^'0');
	return f*x;
}
enum{N=200024,D=4024};
const int mod = 1e9+7;
void exgcd(ll a,ll b,ll&x,ll&y){
	if( !b ){ x=1,y=0; return ; }
	exgcd(b,a%b,y,x); y-=x*(a/b);
}
il ll inv(ll a){
	ll x,y;
	exgcd(a,mod,x,y);
	return (x+mod)%mod;
}
ll fac[D*2],F[D][D];
const int base = 2001;
#define f(i,j) F[(i)+base][(j)+base]
int a[N],b[N];
int main(){
//	printf("%lld",sizeof(G)+sizeof(a)+sizeof(b)+sizeof(fac);
//	return 0;
	int n=ci();
	fac[0]=1;
	rep(i,1,8000) fac[i]=fac[i-1]*i%mod;
	ll ans= 0;
	rep(i,1,n){
		a[i]=ci(), b[i]=ci();
		f(-a[i],-b[i])++;
		ans= (ans
			-fac[(a[i]+b[i])*2]
			*inv(fac[a[i]*2]*fac[b[i]*2]%mod)
		)%mod;
	}
//	printf("%lld\n",ans);
	rep(i,-2000,2000){
		rep(j,-2000,2000){
			f(i,j)= (f(i,j)+f(i-1,j)+f(i,j-1))%mod;
		}
	}
	rep(i,1,n) ans= (ans+f(a[i],b[i]))%mod;
	ans= ans*inv(2)%mod;
	ptll((ans+mod)%mod);
	return 0;
}

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

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)2e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;

ll l, r, p3[100], ans;
ll solvex(ll bit, ll x, ll l){
	if(x >= l)
		return p3[bit + 1];
	if(x + (1ll << (bit + 1)) - 1 < l)
		return 0;
	return (solvex(bit - 1, x, l) * 2 + solvex(bit - 1, x | (1ll << bit), l)) % mod;
}
ll solvey(ll bit, ll y, ll r){
	if(y + (1ll << (bit + 1)) - 1 <= r)
		return p3[bit + 1];
	if(y > r)
		return 0;
	return (solvey(bit - 1, y, r) + solvey(bit - 1, y | (1ll << bit), r) * 2) % mod;
}
ll solve(ll bit, ll x, ll y, ll l, ll r){
	if(x + (1ll << (bit + 1)) - 1 < l)
		return 0;
	if(y > r)
		return 0;
	if(y + (1ll << (bit + 1)) - 1 <= r)
		return solvex(bit, x, l);
	if(x >= l)
		return solvey(bit, y, r);
	return (solve(bit - 1, x, y, l, r) + solve(bit - 1, x , y | (1ll << bit), l, r) + solve(bit - 1, x | (1ll << bit), y | (1ll << bit), l, r)) % mod;
}
int main()
{
	p3[0] = 1;
	for(int i = 1; i < 100; i++)
		p3[i] = p3[i - 1] * 3 % mod;
	cin >> l >> r;
	for(int i = 0; i <= 60; i++)
		ans = (ans + solve(i - 1, (1ll << i), (1ll << i), l, r)) % mod;
	cout << ans;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define int long long 
typedef long long ll;
typedef pair<int,int>pi;
typedef vector<int>vi;

const int MAXN=100005;
const int MOD=1e18;
const int INF=1e15;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

int A[MAXN],N,nl[MAXN],pref[MAXN];

main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N;
	
	FOR(i,0,N) {
		cin>>A[i];
	}
	if (A[0] > 1) {
		cout<<-1;
		exit(0);
	}
	if (A[0]){
		FOR(i,1,N){
			if (A[i]){
				cout<<-1;
				exit(0);
			}
		}
		cout<<1;
		exit(0);
	}
	pref[0] = A[0];
	FOR(i,1,N) pref[i] = pref[i-1] + A[i];
	
	nl[0] = 1;
	int ans = 1;
	FOR(i,1,N){
		int allow = nl[i-1] * 2;
		allow = min(allow, INF);
		if (A[i] > allow) {
			cout<<-1;
			exit(0);
		}
		nl[i] = allow - A[i];
		nl[i] = min(nl[i], pref[N] - pref[i]);
		ans += A[i] + nl[i];
	}
	cout<<ans;	
}


Measured memory_bytes: 6000
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long dp[100010][4];
int n,Mod=1000000007;
string s;
int main()
{
	cin>>s;
	n=s.size();
	for(int i=n;i>=0;i--)
	{
		for(int j=3;j>=0;j--)
		{
			if(i==n)
				dp[i][j]=(j==3?1:0);
			else
			{
				dp[i][j]=dp[i+1][j]*(s[i]=='?'?3LL:1LL);
				if(j<3&&(s[i]=='?'||s[i]=="ABC"[j]))
					dp[i][j]+=dp[i+1][j+1];
			}
			dp[i][j]%=Mod;
		}
	}
	cout<<dp[0][0]<<endl;
	return 0;
}


Measured memory_bytes: 3584
//C
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

//Others

//Hang in there!
//LOVE Nyantako_GG

using namespace std;


int main() {
	int N, K;
	cin >> N >> K;
	vector<int>data(N);
	for (int i = 0; i < N; i++) {
		cin >> data[i];
	}
	sort(data.begin(), data.end());
	int ans = 0;
	for (int i = N - 1; i >= N - K; i--) {
		ans += data[i];
	}
	cout << ans << endl;
}


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

using namespace std;
using i64 = std::int_fast64_t;
using u64 = std::uint_fast64_t;

class RollingHash {
 private:
  using u64 = std::uint_fast64_t;

  const u64 mod = (1ULL << 61) - 1;
  std::vector<u64> hashes, pows;

  inline u64 add(u64 a, u64 b) const {
    a += b;
    if (a >= mod) a -= mod;
    return a;
  }

  inline u64 sub(u64 a, u64 b) const {
    if (a < b) a += mod;
    a -= b;
    return a;
  }

  inline u64 mul(u64 a, u64 b) const {
    u64 ah = a >> 31, al = a & ((1ULL << 31) - 1), bh = b >> 31,
        bl = b & ((1ULL << 31) - 1), m = ah * bl + al * bh,
        v = (ah * bh << 1) + (m >> 30) + ((m & ((1ULL << 30) - 1)) << 31) +
            al * bl;
    v = (v & ((1ULL << 61) - 1)) + (v >> 61);
    return v;
  }

 public:
  RollingHash(const std::string &S, u64 base = 10007)
      : hashes((int)S.size() + 1, 0), pows((int)S.size() + 1, 0) {
    int sz = (int)S.size();
    pows[0] = 1;
    for (int i = 0; i < sz; i++) {
      pows[i + 1] = mul(pows[i], base);
      hashes[i + 1] = add(mul(hashes[i], base), S[i]);
    }
  }

  inline u64 slice(int l, int r) const {
    return sub(hashes[r], mul(hashes[l], pows[r - l]));
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  string S;
  cin >> S;
  RollingHash rh(S);

  auto f = [&](int d) -> bool {
    map<u64, int> mp;
    for (int i = 0; i + d < N + 1; i++) {
      u64 x = rh.slice(i, i + d);
      if (mp.count(x)) {
        if (i - mp[x] >= d) return true;
      } else {
        mp[x] = i;
      }
    }
    return false;
  };

  int lo = 0, hi = N + 1;
  while (lo < hi) {
    int mi = (lo + hi + 1) >> 1;

    if (f(mi)) {
      lo = mi;
    } else {
      hi = mi - 1;
    }
  }
  cout << lo << '\n';
  return 0;
}


Measured memory_bytes: 640
#include <iostream>
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, s, n) for(int i = s; i < n; i++)
using namespace std;

int main(void) {
    int n;
    cin >> n;
    int a[n];
    rep(i, n) cin >> a[i];

    bool same[n];
    reps(i, 1, n) {
        same[i-1] = a[i] == a[i-1];
    }

    // rep(i, n-1) { cout << same[i] << " ";} cout << endl;
    int count = 0;
    int c = 0;
    rep(i, n-1) {
        if (same[i]) {
            c++;
            continue;
        }
        else {
            count += (c + 1)/2;
            c = 0;
        }
    }
    count += (c + 1)/2;

    cout << count << endl;
}



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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
void dump_debug(T list) {
#ifdef MY_DEBUG
    each(e, list) cout << e << " ";
    printf("\n");
#endif
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
vector<ll> G[2 * e5];
vector<ll> ans(2 * e5);
unordered_map<ll, ll> pl;
vector<bool> seen(2 * e5);

void dfs(ll now, ll value) {
    seen[now] = true;
    ans[now] = value;
    each(e, G[now]) {
        if (!seen[e]) {
            dfs(e, value + pl[e]);
        }
    }
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        ll n, q;
        cin >> n >> q;
        rep(i, n - 1) {
            ll a, b;
            cin >> a >> b;
            a--, b--;
            G[a].eb(b);
            G[b].eb(a);
        }

        rep(i, q) {
            ll p, x;
            cin >> p >> x;
            p--;
            pl[p] += x;
        }
        dfs(0, pl[0]);

        rep(i, n) cout << ans[i] << " ";

#ifdef MY_DEBUG
    }
#endif
    return 0;
}


Measured memory_bytes: 32584
macro_rules! scan {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              scan!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              scan!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty;;$n:expr) => {
          (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
      };
}

fn main() {
    let (n, c) = scan!(usize, usize);

    let mut chans = Vec::new();
    for _ in 0..c {
        chans.push([0; 2 * 100001])
    }

    for _ in 0..n {
        let (s, t, c) = scan!(usize, usize, usize);
        chans[c - 1][2 * s - 1] += 1;
        chans[c - 1][2 * t] -= 1
    }

    let mut tvs = [0; 2 * 100001];
    for i in 0..chans.len() {
        for j in 1..chans[i].len() {
            chans[i][j] += chans[i][j - 1];
        }
        for (tv, c) in tvs.iter_mut().zip(chans[i].iter()) {
            if *c > 0 {
                *tv += 1
            }
        }
    }

    println!("{}", tvs.iter().max().unwrap())
}


Measured memory_bytes: 33788
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define mp make_pair
#define ALL(obj) (obj).begin(),(obj).end()
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n) 
#define SIZE(x) ((int)(x).size())
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
typedef vector<lint> vec;
typedef vector<vector<lint>> matrix;
typedef priority_queue<lint> p_que;
typedef priority_queue<lint, vector<lint>, greater<lint>> p_que_rev;
const lint INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

lint gcd(lint a, lint b) {
    lint r;
    while (b != 0) {
        r = a % b;
        a = b; 
        b = r;
    }
    return a;
}

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

lint power(lint x, lint n, lint mod = MOD) {
    lint ret = 1;
    while(n > 0) {
        if(n & 1){
            (ret *= x) %= mod;
        }
        (x *= x) %= mod;
        n >>= 1;
    }
    return ret;
}

vector<lint> make_power(int n, lint base){
    lint num = 1;
    vector<lint> ret;
    for (int i=0; i<=n; ++i){
        ret.push_back(num);
        num *= base;
    }
    return ret;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
    return 0;
}

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

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


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

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL


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

    int n, x;
    cin >> n >> x;
    int l, r;
    s64 ans = 0;
    cin >> l;
    rep (i, n - 1)
    {
        cin >> r;
        if (l + r > x)
        {
            ans += l + r - x;
            r = MAX(0, x - l);
        }
        l = r;
    }

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



Measured memory_bytes: 384
n,a,b=map(int,input().split())
k=b-a-1
if k%2!=0:#間の卓が奇数
    ans=(k+1)//2
    print(ans)    
else:#偶数
    ans=min(b-1,n-a)
    ans1=min(a-1,n-b)+1+k//2
    print(min(ans,ans1))

Measured memory_bytes: 3060
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]

def main():
    xs = na()
    if len(set(xs)) == 2:
        print('Yes')
    else:
        print('No')

main()


Measured memory_bytes: 3060
#include <iostream>
#include <string>
using namespace std;
int main(){
  string a[3];
  for(int i=0;i<3;i++)cin >> a[i];
  for(int i=0;i<3;i++)cout << (char)(a[i][0]-'a'+'A');
  cout << endl;
  return 0;
}

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

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e5+10;

char s[N];
ll dp[N][2][2];

ll solve(int cur, int limit, int zero) {
	if (!cur) {
		return 1;
	}
	ll ret=0;
	//printf("dp[%d][%d][%d]=%d\n", cur, limit, zero, ret);
	if (dp[cur][limit][zero]!=-1) return dp[cur][limit][zero];
	
	for(int i=0; i<=1; i++) {
		for(int j=0; j<=1; j++) {
			if (i&&j) continue;
			else if (!i&&!j) {
				ret+=solve(cur-1, limit&&s[cur]=='0', zero);
				ret%=mod;
			}
			else if (s[cur]=='1'||!limit) {
				ret+=solve(cur-1, limit&&s[cur]=='1', 0);
				ret%=mod;
			}
		}
	}
	//printf("dp[%d][%d][%d]=%d\n", cur, limit, zero, ret);
	return dp[cur][limit][zero]=ret;
}

int main() {
	scanf("%s", s+1);
	int len=strlen(s+1);
	reverse(s+1, s+len+1);
	memset(dp, -1, sizeof(dp));
	cout<<solve(len, 1, 1)<<endl;
	return 0;
}


Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
int a[100001],b[100001],c[100001];
int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	for(int i=1;i<=n;i++) cin>>c[i];
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	sort(c+1,c+n+1);
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=(lower_bound(a+1,a+n+1,b[i])-a-1)*(n-(upper_bound(c+1,c+n+1,b[i])-c-1));
	cout<<ans;
}

Measured memory_bytes: 1408
import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();

        Pattern p1 = Pattern.compile("^.+keyence$");
        Pattern p2 = Pattern.compile("^k.+eyence$");
        Pattern p3 = Pattern.compile("^ke.+yence$");
        Pattern p4 = Pattern.compile("^key.+ence$");
        Pattern p5 = Pattern.compile("^keye.+nce$");
        Pattern p6 = Pattern.compile("^keyen.+ce$");
        Pattern p7 = Pattern.compile("^keyenc.+e$");
        Pattern p8 = Pattern.compile("^keyence.+$");
        Pattern p9 = Pattern.compile("^keyence$");

        Matcher m = p1.matcher(s);
        boolean isMatch = p1.matcher(s).matches();
        if(!isMatch) isMatch = p2.matcher(s).matches();
        if(!isMatch) isMatch = p3.matcher(s).matches();
        if(!isMatch) isMatch = p4.matcher(s).matches();
        if(!isMatch) isMatch = p5.matcher(s).matches();
        if(!isMatch) isMatch = p6.matcher(s).matches();
        if(!isMatch) isMatch = p7.matcher(s).matches();
        if(!isMatch) isMatch = p8.matcher(s).matches();
        if(!isMatch) isMatch = p9.matcher(s).matches();

        String ans = isMatch ? "YES" : "NO";
        System.out.println(ans);
    }
}


Measured memory_bytes: 22100
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(),x.end()

int main()
{
  int N, K;
  cin >> N >> K;
  int X[N], Y[N], SX[N], SY[N];
  ll a, b, c, d, ans;
  ans = LLONG_MAX;
  for (int i = 0; i < N; ++i) {
    cin >> X[i] >> Y[i];
    SX[i] = X[i];
    SY[i] = Y[i];
  }
  sort(SX, SX+N);
  sort(SY, SY+N);
  for (int i = 0; i < N-1; ++i) {
    a = SX[i];
    for (int j = i+1; j < N; ++j) {
      b = SX[j];
      for (int k = 0; k < N-1; ++k) {
        c = SY[k];
        for (int l = k+1; l < N; ++l) {
          d = SY[l];
          int cnt=0;
          for (int m=0; m < N; ++m) {
            if ((a <= X[m]) and (X[m] <= b) and (c <= Y[m]) and ( Y[m] <= d)) {
              cnt++;
            }
          if (cnt >= K) {
            if ((b-a)*(d-c) < ans) {
              ans = (b-a)*(d-c);
            }
          }
          }

        }

      }

    }

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

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

int main() {
  int n;
  cin >> n;
  
  vector<int> vec(100, 0);
  int tmp;
  rep(i, n) {
    cin >> tmp;
    vec[tmp - 1] = 1;
  }

  int ans = 0;
  rep(i, 100) {
    if (vec[i] == 1)
      ans++;
  }

  cout << ans << endl;

  return 0;
}


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

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);
		while (true) {
			int n = scanner.nextInt();
			if (n == 0)
				break;
			boolean[][] map = new boolean[n][31];
			for (int i = 0; i < n; i++) {
				int f = scanner.nextInt();
				while (f-- > 0)
					map[i][scanner.nextInt()] = true;
			}
			int ans = -1;
			long[] bit = new long[n];
			for (int i = 0; i < n; i++)
				bit[i] = 1L << i;
			for (int t = 1; t <= 30; t++) {
				long a = 0;
				for (int i = 0; i < n; i++)
					if (map[i][t])
						a |= bit[i];
				for (int i = 0; i < n; i++)
					if (map[i][t])
						bit[i] = a;

				if (a == (1L << n) - 1) {
					ans = t;
					break;
				}
			}
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 64816
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll h,w,k;
  cin >> h >> w >> k;
  vector<string> maze(h);
  for(ll i=0;i<h;i++) cin >> maze[i];
  ll ans=0;
  for(ll i=0;i<(1<<h+w);i++) {
    bitset<20> bit(i);
    ll cnt=0;
    for(ll j=0;j<h;j++) {
      if(bit.test(j)) continue;
      for(ll k=0;k<w;k++) {
        if(bit.test(h+k)) continue;
        if(maze[j][k]=='#') {
          cnt++;
        }
      }
    }
    if(cnt==k) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3628
a, b, c, x, y = map(int, input().split())

# i組みのabを買うことについて全探索
ans = float("inf")
for i in range(max(x, y)+1):
    price = i * 2 * c + max(x-i, 0) * a + max(y-i, 0) * b
    ans = min(ans, price)
print(ans)


Measured memory_bytes: 2940
# ABC085 C Otoshidama
def main():
    n, y = [int(x) for x in input().split()]
    y //= 1000

    for i in range(n+1):
        y1 = 10 * i
        for j in range(n-i+1):
            y2 = 5 * j
            if y < y1 + y2:
                break
            #print(i, j, n-j-i)
            if y == y1 + y2 + (n-j-i):
                print(i, j, n-j-i)
                return

    print(-1, -1, -1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38884
N, X = map(int, input().split())
x = list(map(lambda x: abs(int(x)-X), input().split()))

def gcd(x, y):
    if x > y:
        x, y = y, x
    while x > 0:
        x, y = y%x, x
    return y

ans = x[0]
for xx in x:
    ans = gcd(ans, xx)

print(ans)

Measured memory_bytes: 15016
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    map<int,int> count_even;
    map<int,int> count_odd;
    int v[n];
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    for(int i = 0; i < n; i+=2){
        count_even[v[i]]++;
    }
    for(int i = 1; i < n; i+=2){
        count_odd[v[i]]++;
    }
    int max_even = 0;
    int max_odd = 0;
    int odd_key = 0;
    int even_key = 0;
    for (auto x : count_even){
        if(max_even <= x.second){
            max_even = x.second;
            even_key = x.first;
        }
    }
    for (auto x : count_odd){
        if(max_odd <= x.second && x.first != even_key){
            max_odd = x.second;
        }
    }
    int ans1 = n - max_even - max_odd;

    max_even = 0;
    max_odd = 0;
    odd_key = 0;
    even_key = 0;
    for (auto x : count_odd){
        if(max_odd <= x.second){
            max_odd = x.second;
            odd_key = x.first;
        }
    }
    for (auto x : count_even){
        if(max_even <= x.second && x.first != odd_key){
            max_even = x.second;
        }
    }
    int ans2 = n - max_even - max_odd;
    cout << min(ans1, ans2) << endl;
    return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef long int li;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<ll, ll>P;
typedef tuple<ll, int, int, int, int, int, int, int>T;
#define PI 3.14159265358979
const int MAX = 510000;
const int MOD = 1000000007;
const int INF=100000000;


int main(){
  ll N;
  cin>>N;
  ll ans=500ll;
  for(ll i=1ll;i*i<=N;i++){
    if(N%i==0){
      ll a=i;
      ll b=N/i;
      string p=to_string(a);
      string q=to_string(b);
      ll g=max(p.size(),q.size());
      ans=min(ans,g);
    }
  }
  cout<<ans;
}

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

using namespace std;

#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define pb emplace_back
#define ll long long
#define ld long double

const int INF = 2e9 + 1;
const ll INFLL = 1e18 + 1;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    deque<char> d;
    string s;
    cin >> s;
    for (auto &c : s) d.push_back(c);
    bool is_rev = false;
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            is_rev = !is_rev;
        } else {
            int f;
            cin >> f;
            char c;
            cin >> c;
            if (is_rev) f = 3 - f;
            if (f == 1) d.push_front(c);
            else d.push_back(c);
        }
    }
    string ans = "";
    for (auto &c : d) ans += c;
    if (is_rev) reverse(all(ans));
    cout << ans;
    return 0;
}


Measured memory_bytes: 4224
from collections import deque

def bfs():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    d = [[float("inf")] * w for _ in range(h)]
    que = deque([])
    que.append((0, 0))
    d[0][0] = 1
    
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            
            if 0 <= nx < h and 0 <= ny < w:
                if F[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    que.append((nx, ny))
    return d[h-1][w-1]

h, w = map(int, input().split())
F = [list(input()) for _ in range(h)]

if bfs() == float("inf"):
    print(-1)
    exit()
else:
    count = 0
    for i in range(h):
        for j in range(w):
          if F[i][j] == ".":
            count += 1
    ans = count - bfs()
    print(ans)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
//#define int         int64_t
#define ii          pair<int,int>
#define dd          pair<double,double>
#define vi          vector<int>
#define pb          push_back
#define all(x)      (x).begin(), (x).end()
#define checkBit(v, p)      (v&(1LL << p))
#define loop(i,a,b) for(int i = a;i < int(b);i++)
#define x           first
#define y           second
using namespace std;
int inf = 2e9, mod = 1e9 + 7;

struct edge {
  int u, v;
  int cap, flow;
  edge() {}
  edge(int u, int v, int cap): u(u), v(v), cap(cap), flow(0) {}
};

struct Dinic {
  int N;
  vector<edge> E;
  vector<vector<int> > g;
  vector<int> d, pt;

  Dinic(int N): N(N), E(0), g(N), d(N), pt(N) {}

  void Addedge(int u, int v, int cap) {
    if (u != v) {
      E.emplace_back(edge(u, v, cap));
      g[u].emplace_back(E.size() - 1);
      E.emplace_back(edge(v, u, 0));
      g[v].emplace_back(E.size() - 1);
    }
  }

  bool BFS(int S, int T) {
    queue<int> q({S});
    fill(d.begin(), d.end(), N + 1);
    d[S] = 0;
    while(!q.empty()) {
      int u = q.front(); q.pop();
      if (u == T) break;
      for (int k: g[u]) {
        edge &e = E[k];
        if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
          d[e.v] = d[e.u] + 1;
          q.emplace(e.v);
        }
      }
    }
    return d[T] != N + 1;
  }

  int DFS(int u, int T, int flow = -1) {
    if (u == T || flow == 0) return flow;
    for (int &i = pt[u]; i < g[u].size(); ++i) {
      edge &e = E[g[u][i]];
      edge &oe = E[g[u][i]^1];
      if (d[e.v] == d[e.u] + 1) {
        int amt = e.cap - e.flow;
        if (flow != -1 && amt > flow) amt = flow;
        if (int pushed = DFS(e.v, T, amt)) {
          e.flow += pushed;
          oe.flow -= pushed;
          return pushed;
        }
      }
    }
    return 0;
  }

  int MaxFlow(int S, int T) {
    int total = 0;
    while (BFS(S, T)) {
      fill(pt.begin(), pt.end(), 0);
      while (int flow = DFS(S, T))
        total += flow;
    }
    return total;
  }
};


int32_t main()
{
    ios_base::sync_with_stdio(false); cout << fixed <<setprecision(0);
    int n, m; cin >> n >> m;
    char c;
    Dinic din(n+m+2);
    ii p = {-1,-1};
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> c;
            if(c == '.') continue;
            din.Addedge(i, n+j, 1);
            din.Addedge(n+j, i, 1);
            if(c == 'S'){
                din.Addedge(n+m, i, 1e6), din.Addedge(n+m, n + j, 1e6);
                if(p.x != i && p.y != j) p = {i,j};
                else return cout << -1 << endl, 0;
            }
            if(c == 'T'){
                din.Addedge(i,n+m + 1, 1e6), din.Addedge(n + j, n+m+1, 1e6);
                if(p.x != i && p.y != j) p = {i,j};
                else return cout << -1 << endl, 0;
            }
        }
    }
    cout << din.MaxFlow(n+m, n+m+1) << endl;;
    return 0;
}


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


int main() {
	int N;
	cin >> N;
	vector<string> W(N);
	for(int i = 0; i < N; i++){
		cin >> W.at(i);
	}
	bool shiritori = true;
	for(int i = 1; i < N; i++){
		if(W.at(i)[0] != W.at(i - 1)[W.at(i - 1).size() - 1]){
			shiritori = false;
			break;
		}
		for(int j = 0; j < i; j++){
			if(W.at(i) == W.at(j)){
				shiritori = false;
				break;
			} 
		}
	}
	if(shiritori){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}
	return 0;
}

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

using namespace std;



void solve()
{
  int n, m;
  map<int, int> d;
  cin >> n;
  for(int i = 0; i < n; i++) {
    int info;
    cin >> info;
    if (!d.count(info)) d[info] = 0;
    d[info]++;
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    int info;
    cin >> info;
    if(!d.count(info) || !d[info]) {
      cout << "NO\n";
      return;
    }
    d[info]--;
  }
  cout << "YES\n";
}

int main()
{
  solve();
}

Measured memory_bytes: 9600
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from random import randint
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
import sys
import os
import re
sys.setrecursionlimit(9999)
inf = float('inf')
mod = int(1e9) + 7
mod_ = 998244353
N = 5001
 
'''
Check for special cases (n=1)
One wrong submission = 10 mins penalty!
do smth instead of nothing and stay organized
'''

def main():
	a, b = map(int, input().split())
	if max(a, b) <= 9:
		print(a*b)
	else:
		print(-1)


BUFSIZE = 8192
class FastI(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = StringIO()
		self.newlines = 0
 
	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()
 
	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count("\n") + (not b)
			ptr = self._buffer.tell()
			self._buffer.seek(0, 2), self._buffer.write(
				b), self._buffer.seek(ptr)
		self.newlines -= 1
		return self._buffer.readline()
class FastO(IOBase):
	def __init__(self, file):
		self._fd = file.fileno()
		self._buffer = __pypy__.builders.StringBuilder()
		self.write = lambda s: self._buffer.append(s)
 
	def flush(self):
		os.write(self._fd, self._buffer.build())
		self._buffer = __pypy__.builders.StringBuilder()
def print(*args, **kwargs):
	sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop("end", "\n"))
	if kwargs.pop("flush", False):
		file.flush()
def gcd(x, y):
	while y:
		x, y = y, x % y
	return x
sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")
if __name__ == "__main__":
	def bootstrap(cont):
		call, arg = cont.switch()
		while True:
			call, arg = cont.switch(to=continulet(
				lambda _, f, args: f(*args), call, arg))
	cont = continulet(bootstrap)
	cont.switch()
	main()

Measured memory_bytes: 31596
#include<bits/stdc++.h>
#define ll long long
const int maxn=200005;
using namespace std;
ll a[maxn],n,now,ans;
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",a+i),a[i]+=a[i-1];
	sort(a,a+n+1),now=1;
	for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) now=1; else ans+=now,now++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792