akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

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

		int n = s.length();
		for (int i = 0; i < n; i++) {
			if (s.charAt(i) != s.charAt(n - 1 - i)) {
				System.out.println("No");
				return;
			}
		}
		int n2 = n / 2;
		for (int i = 0; i < n2; i++) {
			if (s.charAt(i) != s.charAt(n2 - 1 - i)) {
				System.out.println("No");
				return;
			}
		}
		for (int i = 0; i < n2; i++) {
			if (s.charAt(i + n2 + 1) != s.charAt(n - 1 - i)) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");
	}
}


Measured memory_bytes: 22608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int N;
ll K;
ll A[100010], B[100010];

bool solve(ll x, ll y) {
	bool f = true;
	rep(j, 31) {
		if(((x & (1<<j)) == 0) && (y & (1<<j))) {
			f = false;
		}
	}
	return f;
}


int main(void) {
	cin >> N >> K;
	rep(i, N) cin >> A[i] >> B[i];

	ll ans = 0;


	ll tans = 0;
	rep(i, N) {
		bool f = true;
		rep(j, 31) {
			if(((K & (1<<j)) == 0) && (A[i] & (1<<j))) {
				f = false;
				break;
			}
		}
		if(!f) continue;
		// printf("i %d\n", i);
		tans += B[i];
	}
	chmax(ans, tans);


	int idx = 0;
	rep(i, 31) if(K & (1<<i)) {
		idx = i;
	}
	ll ma = 1<<idx;
	// printf("ma %lld\n", ma);
	/*
	ll tans2 = 0;
	rep(i, N) if (A[i] < ma) {
		printf("i %d\n", i);
		tans2 += B[i];
	}
	printf("tans2 %lld\n", tans2);
	chmax(ans, tans2);
	*/

	ll mask = 0;
	rep(i, idx + 1) mask |= (1<<i);
	// printf("mask %lld\n", mAask);
	rep(i, idx + 1) {
		if((K & (1<<i)) == 0) continue;
		// printf("i %d\n", i);
		ll tans2 = 0;
		ll dmask = K ^ (1<<i);
		rep(j, i) dmask |= (1<<j);
		if(dmask > K) continue;
		// printf("dmask %lld\n", dmask);	
		rep(j, N) if(solve(dmask, A[j])) {
			// printf("j %d\n", j);
			tans2 += B[j];
		}
		// printf("tans2 %lld\n", tans2);
		chmax(ans, tans2);
	}

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

Measured memory_bytes: 1792
from fractions import gcd
import copy


def coprime2(a, b):
    return gcd(a, b) == 1


def main():
    A, B = [int(i) for i in input().split()]

    A_l = divisor(A)
    B_l = divisor(B)
    AB_l = set()
    for a in A_l:
        if a in B_l:
            AB_l.add(a)
    AB_l = sorted(list(AB_l))
    tmp = set(AB_l)
    ans = []
    for i, a in enumerate(AB_l):
        if a not in tmp:
            continue
        try:
            tmp.remove(a)
        except:
            pass
        for b in list(tmp):
            if gcd(a, b) != 1:
                try:
                    tmp.remove(b)
                except:
                    pass
        else:
            ans.append(a)

    print(len(ans))


def divisor(n):
    i = 1
    table = set()
    while i * i <= n:
        if n % i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table


if __name__ == "__main__":
    main()


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = (a); i < int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;
using i32 = int;
using i64 = long long;
using f64 = double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf64 = vector<f64>;
using vstr = vector<string>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  string s;
  cin >> s;
  int n = s.size();
  int ans = n;
  reps(i, n - 1) if (s[i - 1] != s[i]) {
    amin(ans, n / 2 + (abs(i * 2 - n) + 1) / 2);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 512
#ifdef _MSC_VER
#include "stdc++.h"
#endif
#ifdef __GNUC__
#include<bits/stdc++.h>
#endif
using namespace std;

using ll = long long;

//vector
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

//constant
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// vector
//template<typename T> vector<vector<T>> vv(ll H, ll W, T v) { return vector<vector<T>> vec(H, vector<T>(W, v)); }

// view vector
template<typename T> void view(T e) { cout << e << endl; }
template<typename T> void view(const vector<T>& v) { for (const auto& e : v) { cout << e << " "; } cout << endl; }
template<typename T> void view(const vector<vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

// DP
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }




// ***************************************


int main(){

    ll N;
    cin >> N;
    vll A(N);
    cin >> A[0];
    ll n = 1;
    REP(i, N - 1){
        ll tmp;
        cin >> tmp;
        if (tmp == A[n - 1]) continue;
        A[n] = tmp;
        n++;
    }


    bool is_inc = (A[0] < A[1]);
    ll money = 1000;
    ll buy;
    ll sell = 0;
    if (is_inc) {buy = A[0];}
    FOR(i, 1, n - 1){
        if (is_inc && (A[i] > A[i + 1])){
            sell = A[i];
            money = money % buy + (money / buy) * sell;
            is_inc = false;
        }
        else if (!is_inc && A[i] < A[i + 1]) {
            buy = A[i];
            is_inc = true;
        }
    }
    
    if (is_inc){
        sell = A[n - 1];
        money = money % buy + (money / buy) * sell;
    }

    cout << money << endl;


    return 0;
}


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

int main(){
  int d;
  cin>>d;
  if(d==22)
    cout<<"Christmas Eve Eve Eve"<<endl;
  else if(d==23)
    cout<<"Christmas Eve Eve"<<endl;
  else if(d==24)
    cout<<"Christmas Eve"<<endl;
  else if(d==25)
    cout<<"Christmas"<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

int n , k;
char s[55];

int main ( void ) {
	scanf ( "%d%d" , &n , &k );
	scanf ( "%s" , s + 1 );
	s[k] = s[k]-'A'+'a';
	for(int i=1;i<=strlen(s+1);i++)
		printf("%c",s[i]); 
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstdio>
using namespace std;
typedef long long ll;

int main() {
	ll a, b;
	cin >> a >> b;

	if (a + b >= 3 && ((a + b) % 3 == 0 || a % 3 == 0 || b % 3 == 0))
		cout << "Possible" << endl;
	else
		cout << "Impossible" << endl;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

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

    ll t;
    cin >> t;
    
    string s;
    set<string> str;

    while(t--)
    {
        cin >> s;
        str.insert(s);
    }

    cout << str.size();

    return 0;
} 

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

uint64_t *pnf, *ipnf;

uint64_t powmod(uint64_t x, uint64_t y, uint64_t p)
{
	if(y == 0){
		return 1;
	} else if(y % 2 == 1){
		return (powmod(x, y-1, p) * x) % p;
	} else {
		uint64_t t = powmod(x, y/2, p);
		return (t * t) % p;
	}
}

void fmod_init(uint64_t n, uint64_t p)
{
	pnf = new uint64_t[n+1];
	ipnf = new uint64_t[n+1];
	pnf[0] = 1;
	for(uint64_t i=0; i<n; i++){
		pnf[i+1] = (pnf[i] * (i+1)) % p;
	}
	ipnf[n] = powmod(pnf[n], p-2, p);
	for(uint64_t i=n; i>0; i--){
		ipnf[i-1] = (ipnf[i] * i) % p;
	}
}

uint64_t cmod(uint64_t n, uint64_t m, uint64_t p)
{
	return (pnf[n] * ipnf[n-m]) % p * ipnf[m] % p;
}

int main()
{
    int X, Y;
    cin >> X >> Y;

    uint64_t p = 1000000007;

    if((X + Y) % 3 != 0){
        cout << 0 << endl;
        return 0;
    }

    int s = (X + Y) / 3;

    int x = X - s;
    int y = Y - s;

    if(x < 0 || y < 0){
        cout << 0 << endl;
        return 0;
    }

    fmod_init(x+y, p);

    cout << cmod(x+y, x, p) << endl;

	return 0;
}


Measured memory_bytes: 10624
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;


int main()
{
	int n, m;
	cin >> n;
	map<string, int> a;
	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		if (a.count(temp) == 0) {
			a.insert(make_pair(temp, 1));
		}
		else
			a[temp]++;
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		string temp;
		cin >> temp;
		if (a.count(temp) == 0) {
			a.insert(make_pair(temp, -1));
		}
		else
			a[temp]--;
	}
	int ans = a.begin()->second;
	for (auto i = a.begin(); i != a.end(); i++) {
		if (i->second > ans) {
			ans = i->second;
		}
	}
	if (ans > 0)
		cout << ans << endl;
	else
		cout << 0 << endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>

#define pb push_back
#define mp make_pair

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef unsigned long long ull;
typedef long long ll;

int main() {
	map<int, ii> mii;
	
	int g[3][3];
	
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			cin >> g[i][j];
			mii[g[i][j]] = mp(i, j);			
		}
	}
	
	int n;
	cin >> n;
	
	for (int i = 0; i < n; ++i) {
		int k;
		cin >> k;
		
		if (mii.find(k) != mii.end()) {
			ii coords = mii[k];
			g[coords.first][coords.second] = 0;
		}
	}
	
	bool ok = false;
	//rows
	for (int i = 0; i < 3 && !ok; ++i) {
		int x = 0;
		for (int j = 0; j < 3; ++j) {
			x |= g[i][j];
		}
		if (x == 0) {
			cout << "Yes" << endl;
			ok = true;
		}
	}
	
	//cols
	for (int i = 0; i < 3 && !ok; ++i) {
		int x = 0;
		for (int j = 0; j < 3; ++j) {
			x |= g[j][i];
		}
		if (x == 0) {
			cout << "Yes" << endl;
			ok = true;
		}
	}
	
	//diags
	if (!ok) {
		if ((g[0][0] == 0 && 
	     g[1][1] == 0 && 
	     g[2][2] == 0) 
	    || 
	    (g[0][2] == 0 && 
	     g[1][1] == 0 && 
	     g[2][0] == 0)) {
			cout << "Yes" << endl;
		} else {
			cout << "No" << endl;
		}
	}
	
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<string>
#include<map>
#include<list>
#include<cstring>
#include<functional>
#include<algorithm>
#define INF 100000000
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,k) for(int i=0;i<k;i++)
#define PB push_back
using namespace std;
typedef pair<int,int> p;
typedef pair<p,p> P;
int dp[16][16],x,y;
int bx[16][16],by[16][16];
int func(int ny,int nx){
	if(dp[ny][nx]>=0)
		return dp[ny][nx];
	int sum=0;
	if(1+ny<=y&&by[nx][ny]==0)
	sum+=func(1+ny,nx);
	if(1+nx<=x&&bx[nx][ny]==0)
	sum+=func(ny,nx+1);
	return dp[ny][nx]=sum;
}
int main(){
	int n,a,b,c,d,p;
	cin>>n;
	while(n--){
		cin>>x>>y;
		cin>>p;
		memset(bx,0,sizeof(bx));
		memset(by,0,sizeof(by));
		rep(i,p){
			cin>>a>>b>>c>>d;
			if(a>c){
				bx[c][b]=-1;
			}else if(b>d){
				by[a][d]=-1;
			}else if(a<c){
				bx[a][b]=-1;
			}else{
				by[a][b]=-1;
			}
		}
		memset(dp,-1,sizeof(dp));
		dp[y][x]=1;
		int pre=func(0,0);
		if(pre>0)
		cout<<pre<<endl;
		else
		cout<<"Miserable Hokusai!"<<endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<map>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define pb push_back
#define pf push_front
 
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
 
ll gcd(ll x, ll y) {
	ll r;
	while ((r = x % y) != 0) {
		x = y;
		y = r;
	}
	return y;
	}
ll lcm(ll x, ll y) {
	x /= gcd(x, y);
	y /= gcd(x, y);
	return (x*y);
}

int main()
{
	int n;
    cin >> n;
    int a[n];
    rep(i,n) cin >> a[i];
    if(n%2==0){
        for(int i=(n-1);i>0;i-=2) cout << a[i] << " ";
        for(int i=0;i<n;i+=2) cout << a[i] << " ";
    }
    else{
        for(int i=(n-1);i>=0;i-=2) cout << a[i] << " ";
        for(int i=1;i<n;i+=2) cout << a[i] << " ";
    }
    cout << endl;
	return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long x, y, i, turu=0;
    cin >> x >> y;
    for(i=0;i<=x;i++){
        turu=x-i;
        if(turu*4+i*2==y){
            cout << "Yes" <<endl;
            return 0;
        }
    }
    cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 3628
#include<stdio.h>

int main(){
  int a,b,c,ans;
  scanf("%d%d%d",&a,&b,&c);
  ans=a+b;
  if(ans>a+c)ans=a+c;
  if(ans>b+c)ans=b+c;
  printf("%d\n",ans);
  return 0;
}



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

using namespace std;

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

using ll = long long;

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size();
    cout << '[';
	for (int i = 0; i < len; ++i) {
		s << v[i]; if (i < len-1) s << ", ";
	}
    cout << ']';
	return s;
}


int s[510][510] = {0};

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m, Q;
	cin >> n >> m >> Q;

	rep(i, m){
	    int l, r;
		cin >> l >> r;
		++s[l][r];
	}
	rep(i, n){
	    rep(j, n){
	        s[i+1][j+1] += s[i][j+1]+s[i+1][j]-s[i][j];
	    }
	}

	rep(i, Q){
	    int p, q;
		cin >> p >> q;
		cout << s[q][q]-s[q][p-1]-s[p-1][q]+s[p-1][p-1] << endl;
	}

    return 0;
}


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

int main()
{
    int n, m, c, i, j, count=0;
    cin>>n>>m>>c;

    int arr[n][m], b[m];

    for(i=0; i<m; i++)
        cin>>b[i];

    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
            cin>>arr[i][j];



    for(i=0; i<n; i++){
        int sum=0;
        for(j=0; j<m; j++){
            sum = sum + arr[i][j]*b[j];

        }
        if(sum+c > 0)
            count++;
    }

    cout<<count;

}


Measured memory_bytes: 256
N, M = list(map(int, input().split()))
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))

Ans = 0
for i in range(pow(2, N)):
  for j in range(len(ks)):
    c = i
    t = 0
    for k in range(N):
      n = c % 2
      if n == 1 and (k + 1) in ks[j][1:]:
        t += 1
      c //= 2
    if t % 2 != p[j]:
      break
  else:
    Ans += 1

print(Ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;

ll N, D, A, ans=0;
vector<pair<ll, ll>> XH;
vector<ll> C;
//vector<pair<ll, ll>> XH;
//ll X[200000], H[200000];

signed main(){
    cin >> N >> D >> A;
    for(int i=0;i<N;i++) {
        ll X, H;
        cin >> X >> H;
        XH.push_back(make_pair(X, H));
        C.push_back(0);
    }
    sort(XH.begin(), XH.end());
    //for(int i=0;i<N;i++) cout << C[i] << endl;
    for(int i=0;i<N;i++) {
        pair<ll, ll> p = XH[i];
        ll ileft = lower_bound(XH.begin(), XH.end(), make_pair((ll)p.first-2*D, (ll)-1000000000000))-XH.begin();
        ll pre=0;
        if(i) {
            C[i] = C[i-1];
        }
        if(ileft!=i&&i>0) {
            if(ileft>0) pre += C[i-1]-C[ileft-1];
            else pre += C[i-1];
        }
        p.second -= pre*A;
        if(p.second>0){
            if(p.second%A==0) {
                ll addi = p.second/A;
                //cout << C[i] << endl;
                //cout << addi << endl;
                C[i] += addi;
                //cout << C[i] << endl;
                //cout << endl;
            }
            else {
                ll addi = p.second/A;
                //cout << C[i] << endl;
                //cout << addi << endl;
                C[i] += addi+1;
                //cout << C[i] << endl;
                //cout << endl;
            }
        }
    }
    //for(int i=0;i<N;i++) cout << C[i] << endl;
    cout << C.back() << endl;
    return 0;
}

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

int main(){
  string s;
  cin >> s;
  bool flg = true;
  rep(i, s.size()){
    if(i % 2 == 0 && s[i] == 'h' && s[i+1] == 'i') continue;
    else if(i % 2 == 1) continue;
    else{
      flg = false;
      cout << "No" << endl;
      break;
    }
  }
  if(flg) cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;

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

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        System.out.println(n % 2 == 0 ? n : n *2);
    }
}

Measured memory_bytes: 23764
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

"""
Z algorithm
def Z(s):
    n = len(s)
    z = [0] * n
    z[0] = n

    L, R = 0, 0
    for i in range(1, n):
        if i >= R:
            L = R = i
            # 一致が続く限り伸ばす
            while(R < n and s[R - L] == s[R]):
                R += 1
            # LCAを書き込む
            # 頭から一致しない場合はR - L = i - i = 0
            z[i] = R - L
        # 全て利用できる場合
        elif z[i - L] < R - i:
            z[i] = z[i - L]
        # 一部利用できる場合
        else:
            L = i
            while(R < n and s[R - L] == s[R]):
                R += 1
            z[i] = R - L
    return z

# [5, 0, 3, 0, 1]
#print(Z('ababa'))

N = getN()
S = input()
ans = 0
for i in range(N):
    z = Z(S[i:])
    k = len(z)
    for j in range(k):
        # '' と 'ababa'
        # 'a' と 'baba'
        # 'ab' と 'aba'
        # ans は j('', 'a', 'ab')の長さ以上にならない（ダブらないため）
        ans = max(ans, min(j, z[j]))
print(ans)
"""

# Rolling hash
N = getN()
S = list(map(ord, list(input())))
# 適当
base = 1234
power = [1] * (N + 1)
# 部分文字列を数字に
for i in range(1, N + 1):
    power[i] = power[i - 1] * base % mod

def check(m):
    if N - m < m:
        return False
    res = 0
    for i in range(m):
        res += S[i] * power[m - i - 1]
        res %= mod
    dic = {res: 0}
    for i in range(N - m):
        res = ((res - S[i] * power[m - 1]) * base + S[i + m]) % mod
        if res in dic.keys():
            index = dic[res]
            if index + m <= i + 1:
                return True
        else:
            dic[res] = i + 1
    return False

ok = 0
ng = N + 1
while ng - ok > 1:
    mid = (ok + ng) // 2

    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Measured memory_bytes: 11480
#include <iostream>

using namespace std;

int main()
{
    int s[]={1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51};
    int n;
    cin>>n;
    cout<<s[n-1]<<endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a);i<(b);++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
#define INF 1000000000000000
#define MOD 1000000007
using PII = pair<int64_t, int64_t>;
using VI = vector<int64_t>;
using VVI = vector<VI>;
using VS = vector<string>;
using VP = vector<PII>;
using i64 = int64_t;
template<typename T> void invec(vector<T> &A){for(T& a : A) cin >> a;} // input vector

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

i64 N, K; cin >> N >> K;
VI A(N); invec(A);
int D = max((int)log2(K) + 1, (int)log2(*max_element(ALL(A))) + 1);
VI cnt0(D, 0);
for(i64 a: A){
    rep(digit, 0, D){
        cnt0[digit] += ((a & (1LL << digit)) == 0);
    }
}
i64 X = 0, f = 0;
Rrep(digit, D-1, 0){
    if (cnt0[digit] > N/2) X |= (1LL << digit);
    if (X > K) X ^= (1LL << digit);
}
for(i64 a: A) f += X ^ a;

cout << f << "\n";

return 0;
}
// 書いて考える．場合分け．情報整理．
// 単純に分かる量から．愚直解を実装して研究．
// 境界，出力文字列 チェック．行末にスペース入れない．
// 可読性優先．高速化次点．
// まずは全探索，分割，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 1024
import itertools
L=["2","3","4","5","6","7","8"]

N,M=map(int,input().split())

L=L[:N-1]
A=list(itertools.permutations(L,N-1))
C=[]
for i in A:
    B=["1"]+list(i)
    C.append(B)
#print(C)
D={}
for i in range(M):
    a,b=input().split()
    D[(a,b)]=1
    D[(b,a)]=1
    
#print(D)

ans=0
for i in C:
    f=1
    for j in range(N-1):
        if (i[j],i[j+1]) not in D:
            f=0
            break
    if f==1:
        ans+=1
print(ans)

Measured memory_bytes: 41584
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class S,class T> istream& operator>>(istream &is,pair<S,T> &p) { return is >> p.first >> p.second; }
template<class S,class T> ostream& operator<<(ostream &os,const pair<S,T> &p) { return os<<'{'<<p.first<<","<<p.second<<'}'; }
template<class T> istream& operator>>(istream &is,vector<T> &v) { for(T &t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) { os<<'[';rep(i,v.size())os<<v[i]<<(i==v.size()-1?']':','); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
template<class T> bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vi a(n);
    cin >> a;
    rep(i,k) {
        vi na(n+1);
        rep(j,n) {
            int l = max(0,j-a[j]);
            int r = min(n-1,j+a[j]);
            na[l]++;
            na[r+1]--;
        }
        bool fi = true;
        rep(j,n) {
            na[j+1] += na[j];
            a[j] = na[j];
            if(a[j] != n) fi = false;
        }
        if(fi) {
            rep(j,n) cout << a[j] << (j == n-1 ? "\n" : " ");
            return 0;
        }
    }
    rep(j,n) cout << a[j] << (j == n-1 ? "\n" : " ");
}


Measured memory_bytes: 4972
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<bool> p(55556,true);
    p[0]=false;
    p[1]=false;
    for(int i=2;i*i<=55555;i++){
        if(p[i]){
            for(int j=2;j*i<=55555;j++){
                p[i*j]=false;
            }
        }
    }
    int n;cin >> n;
    vector<int> a;
    for(int i=0;i<=55555;i++){
        if(p[i]){
            if(i%5==1){
                a.push_back(i);
            }
        }
    }
    for(int i=0;i<n;i++){
        cout << a[i] << " ";
    }
    cout << endl;
}

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

int main()
 {
 	int i,n;
 	string s;
 	cin>>s;
 	n=s.length();
 	for(i=0;i<n;i++)
 		s[i]='x';
 	cout<<s<<endl;
 	return 0;
 }

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

int main(void) {
  int N;
  cin >> N;
  vector<int> C, S, F;
  for (int i = 0; i < N - 1; i++) {
    int c, s, f;
    cin >> c >> s >> f;
    C.push_back(c);
    S.push_back(s);
    F.push_back(f);
  }

  for (int i = 0; i < N; i++) {
    int t = 0;
    for (int j = i; j < N - 1; j++) {
      if (t < S[j])
        t = S[j];
      else if (t % F[j] != 0)
        t += F[j] - t % F[j];
      t += C[j];
    }
    cout << t << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h> 

int main (void) {
	int n, j, i, a;
	while(scanf("%d",&n) ,n ) {
		int icecream[10] = {0};
		for(i = 0; i < n; i++ ) {
			scanf("%d",&a);
			icecream[a]++;
		}
		for(i = 0; i < 10; i++ )  {
			if(icecream[i] == 0 ) {
				printf("-\n");
			} else {
				for(j = 0; j < icecream[i]; j++ ) {
					printf("*");
				}
				puts("");
			}
		}
	}
	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <iomanip>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repf(i, a, b) for (int i = (int)a; i < (int)b; i++)
#define repr(i, a, b) for (int i = (int)a; i > (int)b; i--)
#define all(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int infi = 1147483600;
const ll infl = 4e18 + 5;
const char ENDL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 998244353;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int ans = 0;
    rep(i,3){
        if (s[i]==t[i])
            ans++;
    }
    cout << ans << ENDL;
}

Measured memory_bytes: 256
#include<stdio.h>
      int main(void){
        int n,i,c;
        char a[100];
        char b[50];
        scanf("%d",&n);

        scanf("%s",a);

        c=n/2;
        if(n%2){
          printf("No\n");
          return 0;
        }
        for(int i=0;i<n/2;i++){
          if(a[i]!=a[i+c]){
            printf("No\n");
            return 0;
          }
        }
        printf("Yes\n");
        return 0;
      }


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int x,n,i=0,j,c=0,p,h[1000010];
    cin >> n;
    for(i=0;i<n;i++)
    {
        cin >> h[i]; 
    }
    if(n==1)
    {
        cout << "Yes" << endl;
        return 0;
    }
    for(i=0;i<n-1;i++)
    {
        if(h[i+1]<h[i])
        {
            h[i]-=1;
        }
        else if(h[i+1]==h[i] && h[i]-1>=h[i-1])
        {
            h[i]-=1;
        }
    }
    for(i=0;i<n-1;i++)
    {
        if(h[i]>h[i+1])
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;

}


Measured memory_bytes: 4400
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;
using ll = long long;

#define all(c) (c).begin(), (c).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

ll N;
bool ok(ll i) {
    ll d = N - i;
    return i * (i - 1) / 2 >= d;
}
int main() {
    cin >> N;
    if (N == 1) {
        cout << "1" << endl;
        return 0;
    }

    ll lb = 0;
    ll ub = N;
    while (ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        if (ok(mid))
            ub = mid;
        else
            lb = mid;
    }
    cout << ub << endl;
    ll d = N - ub;
    for (int i = ub - 1; i > 0; i--) {
        if (d - i >= 0) {
            cout << i << endl;
            d -= i;
        }
    }
    assert(d == 0);
    return 0;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

void main() {
    auto nq = readints();
    int n = nq[0], q = nq[1];
    for (int i = 0; i < q; i++) {
        auto xs = readints();

        if (xs[0] == 0) {
            int s = xs[1];
            int t = xs[2];
            int x = xs[3];
            add(s, t + 1, x, 0, 0, N / 2);
        }
        else {
            int s = xs[1];
            int t = xs[2];
            auto v = sum(s, t + 1, 0, 0, N / 2);
            writeln(v);
        }
    }
}

///////////////////////////////////////

const int N = 1 << 18; // ???????????°

long[N * 2] _data;
long[N * 2] _datb;

/// [a, b) ??? x ???????????????
/// k ????????????????????§????????? [l, r) ???????????????
void add(int a, int b, int x, int k, int l, int r) {
    if (a <= l && r <= b) {
        _data[k] += x;
    }
    else if (l < b && a < r) {
        _datb[k] += (min(b, r) - max(a, l)) * x;
        add(a, b, x, k * 2 + 1, l, (l + r) / 2);
        add(a, b, x, k * 2 + 2, (l + r) / 2, r);
    }
}

/// [a, b) ??????????±???????
/// k ????????????????????§????????? [l, r) ???????????????]
long sum(int a, int b, int k, int l, int r) {
    if (b <= l || r <= a)
        return 0;

    if (a <= l && r <= b)
        return _data[k] * (r - l) + _datb[k];

    auto ret = (min(b, r) - max(a, l)) * _data[k];
    ret += sum(a, b, k * 2 + 1, l, (l + r) / 2);
    ret += sum(a, b, k * 2 + 2, (l + r) / 2, r);
    return ret;
}

Measured memory_bytes: 11380
while True:
    try:
        a,b,c,d,e,f = map(int,input().split())
        x = (c*e - f*b)/(a*e - b*d)
        y = (c*d - f*a)/(b*d - e*a)
        x = round(x,3)
        y = round(y,3)
        if x == -0.0:
            x = 0.0
        if y == -0.0:
            y = 0.0
        print("{0:.3f}".format(x),end = ' ')
        print("{0:.3f}".format(y))
    except EOFError:
        break

Measured memory_bytes: 7672
(let* ((n (cons (read) (read)))
       (m (cons (read) (read))))
  (loop :do (if (<= (car n) 0)
                (progn (princ "No") (return))
                (decf (car m) (cdr n)))
        :do (if (<= (car m) 0)
                (progn (princ "Yes") (return))
                (decf (car n) (cdr m)))
        )
  )

Measured memory_bytes: 23584
def get_lcs s1, s2
  s1 = s1.chars
  s2 = s2.chars
  l1 = s1.length
  l2 = s2.length
  dp = Array.new(l1 + 1){Array.new(l2 + 1)}
  0.upto(l1) do |i|
    0.upto(l2) do |j|
      dp[i][j] = if i == 0 || j == 0
                   0
                 elsif s1[i - 1] == s2[j - 1]
                   dp[i - 1][j - 1] + 1
                 else
                   [dp[i][j - 1], dp[i - 1][j]].max
                 end
    end
  end
  dp[l1][l2]
end

n = gets.chomp.to_i
while seq_1 = gets
  seq_1 = seq_1.chomp
  seq_2 = gets.chomp
  puts get_lcs(seq_1, seq_2)
end


Measured memory_bytes: 52772
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
struct UnionFind {
    int n, cc, *u;
    UnionFind() : n(0), cc(0), u(NULL) {}
    UnionFind(int n_) : n(n_), cc(n_) {
	u = new int[n_];
	memset(u, -1, sizeof (int) * n);
    }
    UnionFind(const UnionFind &y) : n(y.n), cc(y.cc) {
	u = new int[y.n];
	memcpy(u, y.u, sizeof (int) * n);
    }
    ~UnionFind() {
	delete[] u; u = NULL;
	n = cc = 0;
    }
    friend void swap(UnionFind &x, UnionFind &y) {
	swap(x.n, y.n); swap(x.cc, y.cc); swap(x.u, y.u);
    }
    UnionFind& operator=(UnionFind y) { 
	swap(*this, y);
	return *this;
    }
    int root(int x) {
	int y = x, t;
	while (u[y] >= 0) y = u[y];
	while (x != y) { t = u[x]; u[x] = y; x = t; }
	return y;
    }
    bool link(int x, int y) {
	x = root(x); y = root(y);
	if (x == y) return false;
	if (u[y] < u[x]) swap(x, y);
	u[x] += u[y]; u[y] = x; cc--;
	return true;
    }
    bool same(int x, int y) { return root(x) == root(y); }
    int size(int x) { return -u[root(x)]; }
    int count() { return cc; }
};

int N, M;
int A[100011];
int B[100011];
VI G[100011];
int mark[100011];
bool use[100011];
pair<int, int> P[100011];
LL R[100011], sumB[100011];

void MAIN() {
    scanf("%d%d", &N, &M);
    REP (i, N) scanf("%d%d", A+i, B+i);
    REP (i, M) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	G[x].push_back(y);
	G[y].push_back(x);
    }

    REP (i, N) P[i] = make_pair(A[i]-B[i], i);
    sort(P, P+N);
    memset(mark, -1, sizeof mark);

    UnionFind U(N);
    REP (i_, N) {
	int v = P[i_].second;
	use[v] = true;
	VI ch;
	EACH (e, G[v]) if (use[*e]) {
	    int w = U.root(*e);
	    if (mark[w] == v) continue;
	    mark[w] = v;
	    ch.push_back(w);
	}
	EACH (e, ch) U.link(*e, v);

	LL c = max(A[v] - B[v], 0);
	LL sum = B[v];
	EACH (e, ch) {
	    sum += sumB[*e];
	}
	LL r = c + sum;

	EACH (e, ch) {
	    LL tmp = max(c, R[*e]) + sum - sumB[*e];
	    amin(r, tmp);
	}
	int w = U.root(v);
	R[w] = r;
	sumB[w] = sum;
    }

    int v = U.root(P[N-1].second);
    printf("%lld\n", R[v]);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



Measured memory_bytes: 10236
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pii>
#define endl '\n'
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define in insert
#define pi 3.14159265358979323846
#define rep(i,a,b) for(int i = a ; i < b ; i++)
#define repr(i,a,b) for(int i = b ; i > a ; i--)
  
long long fact(long long a, long long b){
    int r= max(a, b);
    int v= min(a, b);
    int l=1;
    // if(v==0)
    for(int i=r+1; i<=a+b; i++){
        l*=i;
    }
    for(int i=v; i>=2; i--){
        l/=i;
    }
    return l;
}

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

int powr(int a) { 
    int var=1;
    for(int i=0; i<a; i++){
        var*=2;
    }
    return var;
}

void func(int a, bool i){
    cout << a;
    if(a==100){
        i=1;
    }
    else if(a==0){
        return;
    }
    if(!i)
        func(a+1, i);
    else
        func(a-1, i);
}

int cnt[500000];

signed main(){   
    fast;
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    // if(n==1)
    int dp[n+1]={};
    dp[0]=0;
    dp[1]=a[0];
    for(int i=1; i<n; i++){
        if(i==1){
            dp[i] = dp[i-1]+abs(a[i-1]-a[i]);
            continue;
        }
        dp[i] = min(dp[i-1]+abs(a[i-1]-a[i]), dp[i-2]+abs(a[i-2]-a[i]));
    }
    cout << dp[n-1];
} 

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

int main(){
    int n;
    cin >> n;
    vector<int>vec = {};

    if(n == 0){
        cout << "0" << endl;
        return 0;
    }

    while(n != 1){
        if(n%2 == 1 || n%2 == -1){
            vec.push_back(1);
            n--;
            n /= (-2);
        }
        else { 
            vec.push_back(0);
            n /= (-2);
        }
    }vec.push_back(1);

    for(int i = (int)vec.size() - 1 ;i>=0;i--){
        cout << vec[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
X = list(map(int, input().split()))
if N >= M:
    print(0)
else:
    X.sort()
    Y = [X[i+1]-X[i] for i in range(M-1)]
    Y.sort()
    print(sum(Y[:M-1-(N-1)]))


Measured memory_bytes: 89340
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

template <typename T>
void printlnVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << endl;
  }
}

template <typename T>
void printVector(T v)
{
  rep(i, v.size())
  {
    cout << v[i] << " ";
  }
  cout << endl;
}

int main()
{
  long long N;
  cin >> N;
  vector<int> divisor;
  for (long long i = 1; i * i <= N; i++)
  {
    if (N % i == 0)
    {
      divisor.push_back(i);
      if (i * i != N)
        divisor.push_back(N / i);
    }
  }

  long long ans = 0;
  for (long long a : divisor)
  {
    long long m = N / a - 1;
    if (m != 0 && N / m == N % m)
      ans += m;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define pf push_front
#define mt make_tuple
#define popb pop_back
#define popf pop_front
#define int long long int
#define vi         vector<int>
#define vll        vector<ll>
#define vpii       vector<pair<int,int>>
#define vpll       vector<pair<ll,ll>>
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(container) int((container).size())
#define rep(i,a,b) for(i=a;i<b;i++)
#define tr(container,it)   for(auto it = container.begin(); it != container.end(); it++)
#define present(container, element) (container.find(element) != container.end())      //set,map etc.
#define cpresent(container, element) (find(all(container),element) != container.end())    //vector
#define hell 1000000007
#define PI 3.14159265
#define mod 998244353
#define fs first
#define sc second
#define TIME        cerr << "\nTime elapsed: " << setprecision(5) <<1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";

void solve()
{
  int n,i,j;
  cin>>n;
  int ans=0,a[n];
  rep(i,0,n)cin>>a[i];
  sort(a,a+n);
  ans= a[n-1];
  int cnt=1;
  j= n-2;
  for(cnt=1;cnt<n-1;cnt+=2)
  {
    ans+= 2*a[j];
    j--;
    if(cnt+2>n-1)
      ans-= (cnt+3-n)*a[j+1];
  }
  cout<<ans;
}
signed main()
{
  fastio
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  int t;
  t=1;
  //cin>>t;
  while(t--)
  solve();
  TIME
  return 0;
}

Measured memory_bytes: 5312
from sys import stdin

n = int(input())

xs = [int(input()) for _ in range(n)]

ans = 0
for x in xs:
    flg = True
    for y in range(2, int(x**0.5+1)):
        if x % y == 0:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Measured memory_bytes: 8224
#include <iostream>
#include <algorithm>

using namespace std;

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

    long long ans = 100001;
    long long s[3];

    for (long long i = 1; i < H; ++i) {
        s[0] = i * W;
        s[1] = (H - i) * (W / 2);
        s[2] = (H - i) * (W - (W / 2));
        sort(s, s + 3);
        ans = min(ans, s[2] - s[0]);
    }

    for (long long i = 1; i < W; ++i) {
        s[0] = i * H;
        s[1] = (W - i) * (H / 2);
        s[2] = (W - i) * (H - (H / 2));
        sort(s, s + 3);
        ans = min(ans, s[2] - s[0]);
    }

    for (long long i = 1; i < H; ++i) {
        s[0] = i * W;
        s[1] = ((H - i) / 2) * W;
        s[2] = ((H - i) - ((H - i) / 2)) * W;
        sort(s, s + 3);
        ans = min(ans, s[2] - s[0]);
    }

    for (long long i = 1; i < W; ++i) {
        s[0] = i * H;
        s[1] = ((W - i) / 2) * H;
        s[2] = ((W - i) - ((W - i) / 2)) * H;
        sort(s, s + 3);
        ans = min(ans, s[2] - s[0]);
    }

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

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

int main() {
  int A, B, k;
  cin >> A >> B;
  k =0; 
  for (int i = A; i <= B; i++){
    if (i / 10000 == i % 10 && i % 10000 / 1000 == i % 100 / 10) k ++;
  }
    cout << k << endl;

}

Measured memory_bytes: 256
N,W=map(int,input().split())
INF=10**9+1
import numpy as np
dp=np.full(N*1000+1,INF,dtype=int)
dp[0]=0
for i in range(N):
  w,v=map(int,input().split())
  np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])

for i in range(len(dp)-1,-1,-1):
  if dp[i]<=W:
    print(i)
    break


Measured memory_bytes: 14028
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(25) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 5100000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
  lli A,B,C,D,E,F,N,M,K,L,R,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> H >> W;
  Vec(G,string,H,"");
  rep(i,0,H)cin >> G[i];
  rep(i,0,H)rep(j,0,W)rep(l,0,H)rep(r,0,W){
    if(G[i][j]!='.')continue;
    if(G[l][r]!='.')continue;
    DV(dist,lli,H,W,-1);
    queue<pint> que;
    que.push(pint(i,j));
    dist[i][j]=0;
    while(!que.empty()){
      auto Xq=que.front();que.pop();
      rep(k,0,4){
        auto nx=Xq.first+dx[k];
        auto ny=Xq.second+dy[k];
        if(nx<0||ny<0||nx>=H||ny>=W)continue;
        if(dist[nx][ny]!=-1)continue;
        if(G[nx][ny]=='.'){
          dist[nx][ny]=dist[Xq.first][Xq.second]+1;
          que.push(pint(nx,ny));
        }
      }
    }
    num=max(num,dist[l][r]);
  }
  Out(num);
}

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

using namespace std;

int main()
{
	cerr << "Compilation Done." << '\n';
	int n, x, y;
	cin >> n  >> x >> y;
	map<int,int> mp;
	for(int i = 1; i <= n; i++) {
		for(int j = i+1; j <= n; j++) {
			int dis = j - i;
			int dis1 = abs(x-i) + 1 + abs(y-j);
			int dis2 = abs(y-i) + 1 + abs(x-j);
			dis = min({dis, dis1, dis2});
			mp[dis]++;
		}
	}
	vector<int> ans(n);
	for(auto& i:mp) {
		ans[i.first] = i.second;
	}
	for(int i = 1; i < n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef long long lli;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<ll> vll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<ll, str>> vpls;
typedef vector<tuple<str, ll, ll>> vtsl;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//実行部
void Main()
{
  ll n; cin >> n;
  fin((n - 2) * 180)
  return;
}

//前処理
int main()
{
  //ios::sync_with_stdio(false);
  //cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}


Measured memory_bytes: 256