akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int main() {
  int h,w;
  cin >> h >> w;
  int mp[h][w];
  rep(i,h){
    rep(j,w){
      char c;
      cin >> c;
      if(c == '#')mp[i][j] = 0;
      else mp[i][j] = INT_MAX-10;
    }
  }
  queue<P> q;
  rep(i,h){
    rep(j,w){
      if(mp[i][j] == 0)q.push(P(i,j));
    }
  }
  while(!q.empty()){
    //show(mp[5][3]);
    P p = q.front();q.pop();
    int y = p.fi,x=p.se;
    rep(i,4){
      int cost = mp[y][x]+1;
      if(y+dy[i]<0 || x+dx[i]<0 || y+dy[i]>=h || x+dx[i]>=w)continue;
      if(mp[y+dy[i]][x+dx[i]]>cost){
        mp[y+dy[i]][x+dx[i]]=cost;
        q.push(P(y+dy[i],x+dx[i]));
      }
    }
  }
  int mx = 0;
  rep(i,h){
    rep(j,w){
      maxs(mx,mp[i][j]);
    }
  }
  cout<<mx<<endl;
  return 0;
}

Measured memory_bytes: 12304
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

/*
struct Monoid{
    using T = _underlying_set_; //??¢??????????????°????????????
    T operator()(const T &a, const T &b) { return _a_op_b_; } //????????????
    static constexpr T identity() { return _identity_element_; } //?????????
};
*/

struct Monoid{
    using T = int; //??¢??????????????°????????????
    T operator()(const T &a, const T &b) { return a < b ? a : b; } //????????????
    static constexpr T identity() { return INT_MAX; } //?????????
};

template<class Monoid>
class SegTree{ //SegTree<Monoid> seg(n);
    private:
        using T = typename Monoid::T; //??°?????????????????¨????????¢???
        Monoid op; //???????????¢??°???????????§??????
        const int n; //????????????
        vector<T> t; //?????¨????????¨

        void prop_to(int i) { //?????????i????????¬
            t[i] = op(t[2 * i], t[2 * i + 1]);
        }

    public:
        SegTree(int n) : n(n), t(2 * n, op.identity()) {} //???????????§??????????????????
        SegTree(const vector<T> &v) : n(v.size()), t(2 * n){ //???????????¨???????????????
            copy(begin(v), end(v), begin(t) + n);
            for(int i = n - 1; i > -0; i--) prop_to(i);
        }

        void set(int i, const T &x){
            t[i += n] = x; 
            while(i >>= 1) prop_to(i);
        }

        void add(int i, const T &x){
            set(i, get(i) * x);
        }

        T get(int i) { return t[i + n]; } //??????i???????????????

        T query(int l, int r){
            T accl = op.identity(), accr = op.identity();
            for(l += n, r += n; l < r; l >>= 1, r >>= 1){
                if(l & 1) accl = op(accl, t[l++]);
                if(r & 1) accr = op(t[r-1], accr);
            }
            return op(accl, accr);
        }
};

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

    SegTree<Monoid> seg(n);
    rep(i,q){
        int com;
        cin >> com;
        if(com){
            int x, y;
            cin >> x >> y;
            cout << seg.query(x, y + 1) << endl;
        }else{
            int x, y;
            cin >> x >> y;
            seg.set(x, y);
        }
    }
}

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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define PI acos(-1.0)
#define sq(n) (n)*(n)

using namespace std;
typedef long long ll;

int main() {
    FAST;

   ll a,b,c,k;
   cin>>a>>b>>c>>k;

   while(b<=a && k!=0)
   {
       b=b*2;
       k--;
   }
   while(c<=b && k!=0)
   {
       c=c*2;
       k--;
   }

  // cout<<a<<" "<<b<<" "<<c<<endl;
   if(a<b && b<c)
   {
       cout<<"Yes"<<endl;
   }
   else
   {
       cout<<"No"<<endl;
   }




    return 0;
}




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

int main() {
  int N, K;
  cin >> N >> K;
  int ans = 0;
  N -= K;
  ans++;
  if (N == 0) {
    cout << ans << endl;
  }
  else {
    for (int i = 0; i < 1000000; i++) {
      N -= (K - 1);
      ans++;
      if (N <= 0) {
        cout << ans << endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 3532
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
using namespace std;
//max heap size
#define N 2000001
 
int heap_size=0;
int key[N];
 
//function parent
int parent(int i){
  return i/2;
}
//function left
int leftc(int i){
  return 2*i;
}
//function right
int rightc(int i){
  return 2*i+1;
}
 
//function maxHeapify
void maxHeapify(int i){
  int l,r,largest;
  int st;
  
  l=leftc(i);
  r=rightc(i);
 
  if(l<=heap_size && key[l]>key[i]) largest=l;
  else largest=i;
  
  if(r<=heap_size && key[r]>key[largest]) largest=r;
  
  if(largest!=i){
    st=key[i];
    key[i]=key[largest];
    key[largest]=st;
    maxHeapify(largest);
  }
}
 
//function heap increase key
int heapIncreaseKey(int i,int data){
  int st;
  if(data<key[i]) return -1;
  key[i]=data;
  while(i>1 && key[parent(i)]<key[i]){
    st=key[i];
    key[i]=key[parent(i)];
    key[parent(i)]=st;
    i=parent(i);
  }
  return 0;
}
 
//function max heap insert
void maxHeapInsert(int data){
  heap_size++;
  key[heap_size]=INT_MIN;
  heapIncreaseKey(heap_size,data);
}
 
//function extract
int heapExtractMax(void){
  int max;
 
  if(heap_size <1) return -1;
  max=key[1];
  key[1]=key[heap_size];
  heap_size--;
  maxHeapify(1);
  return max;
}
 
int main(){
 
  int data;
  char str[10];
  int st;
 
  while(1){
    //load string
    scanf("%s",str);
    //insert
    if(str[0]=='i'){
      scanf("%d",&data);
      maxHeapInsert(data);
    }
    //extract
    else if(strcmp("extract",str)==0){
      st=heapExtractMax();
      if(st!=-1) printf("%d\n",st);
    }
    //end
    else break;
  }
 
  return 0;
}

Measured memory_bytes: 4800
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    ll N, K;
    cin >> N >> K;
    int logK = 0;
    while ((1ll << logK) <= K) logK++;
    vector<vector<int>> exp_next(logK, vector<int>(N));
    for (int i = 0; i < N; ++i) {
        cin >> exp_next[0][i];
        exp_next[0][i]--;
    }
    for (int i = 1; i < logK; ++i) {
        for (int j = 0; j < N; ++j) {
            exp_next[i][j] = exp_next[i - 1][exp_next[i - 1][j]];
        }
    }

    int now = 0;
    for (int i = 0; i < logK; ++i) {
        if ((1ll << i) & K) now = exp_next[i][now];
    }

    cout << ++now << endl;
}

Measured memory_bytes: 51016
import java.util.*;

public class Main{
	
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
  	int n=sc.nextInt(),max=0,f=0;
    char[] ch=sc.next().toCharArray();
    for(int i=0;i<n;i++){
      if(ch[i]=='I'){
        f++;
        max=Math.max(max,f);
      }else{
        f--;
      }
    }
    System.out.println(max);
  }
}


Measured memory_bytes: 23252
A, B, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
xyc = [list(map(int, input().split())) for _ in range(m)]

ans = min(a) + min(b)

for x, y, c in xyc:
    ans = min(ans, a[x-1] + b[y-1] - c)

print(ans)

Measured memory_bytes: 38560
#include<cstdio>
#include<cstring>
long long cnt[200];
char s[300000];
int main()
{
	scanf("%s",s);
	long long n=strlen(s);
	for(int i=0;i<n;i++)cnt[s[i]]++;
	long long tot=0;
	for(int i='a';i<='z';i++)tot+=cnt[i]*(cnt[i]-1)/2;
	printf("%lld\n",n*(n-1)/2-tot+1);
}


Measured memory_bytes: 512
#include "bits/stdc++.h"

//region Template
#include "ext/pb_ds/assoc_container.hpp"

using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const int MOD = 1000000007;
using namespace std;
#define finish(x) cout << x; exit(0);
#define fastIO cin.tie(0); cin.sync_with_stdio(false);
#define endl '\n'

void setIn(string s) { freopen(s.c_str(), "r", stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }

//const string USCAO_TAG = "mountains";
void usaco(const string& USACO_TAG) { setIn(USACO_TAG + ".in"); setOut(USACO_TAG + ".out"); }
void print() {}
template<typename T, typename... Args>
void print(T firstArg, Args... args) {
	#ifdef LOCAL
	cout << firstArg << " ";
	print(args...);
	#endif
}
//endregion

/* Notes:
 * Farah </3
 */

const int MAXN = 1e6 + 5;

long long modPow(long long b, long long pow){
	long long ans = 1;
	long long p = b;
	while(pow){
		if(pow & 1)
			ans = (ans * p) % 1000000007;
		p = (p * p) % 1000000007;
		pow >>= 1;
	}
	return ans;
}

ld a[MAXN];

int main() {
	//usaco("milkvisits");

	#ifdef LOCAL
	setIn("in.txt");
	setOut("out.txt");
	#endif

	int n, k;
	cin >> n >> k;

	ld ans = 0;


	for(int i = 0; i < n; i++){
		ll t;
		cin >> t;

		a[i] = (t + 1) / 2.0;
	}

	for(int i = 0; i < k; i++){
		ans += a[i];
	}

	ld mxans = ans;

	for(int i = k; i < n; i++){
		ans -= a[i - k];
		ans += a[i];

		mxans = max(ans, mxans);
	}

	cout << fixed << setprecision(6) << mxans;

//	cout << ans
}

Measured memory_bytes: 4352
# coding:utf-8

INF = float('inf')


def inpl(): return list(map(int, input().split()))


n = int(input())
A = inpl()
tmp = [i + 1 for i in range(n)]

B = [A[i] - tmp[i] for i in range(n)]
B.sort()
b = B[n // 2]

ans = 0
for i in range(n):
    ans += abs(B[i] - b)

print(ans)

Measured memory_bytes: 29200
#include<stdio.h>
#define N 101
#define INF 1000000
int n;

int min(int a, int b){
  if(a>b) return b;
  else return a;
}

int matrixChainOrder(int *p){
  int i,j,k,m[N][N],l,q;
  for(i=1;i<=n;i++) m[i][i]=0;
 
  
  for(l=2;l<=n;l++){
    for(i=1;i<=n-l+1;i++){
      j=i+l-1;
      m[i][j]=INF;
      
      for(k=i;k<=j-1;k++){
	q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
	m[i][j]=min(m[i][j], q);
      }
    }
  }
  return m[1][j];
}

int main(){
  int p[N],i;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d%d",&p[i],&p[i+1]);

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



Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
int n,k,s=0,a[55];
bool co(int a,int b)
{
	return a<b;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1,co);
	for(int i=n;i>=n-k+1;i--)
	{
		s+=a[i];
	}
	cout<<s;
	return 0;
}

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

const int N = 100005;
const int M = 105;
const long long inf = 1e18+7;

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

int n, a[N];
char c;
long long f[N][M+1];

int main() {
	ios::sync_with_stdio(false);

	cin >> n >> a[0];
	for (int i = 1; i < n; ++i) {
		cin >> c >> a[i];
		if (c == '-') a[i] *= -1;
	}
	REP(i, n+1) REP(a, M+1) {
		f[i][a] = -inf;
	}
	f[0][0] = 0;
	REP(i, n) REP(x, M) {
		if (f[i][x] == -inf) continue;
		long long val = f[i][x] + (x%2?-1:+1)*a[i];
		f[i+1][x] = max(f[i+1][x], val);
		if (a[i] < 0) f[i+1][min(x+1,M)] = max(f[i+1][min(x+1,M)], val);
		if (x > 0) f[i+1][max(x-1,0)] = max(f[i+1][max(x-1,0)], val);
	}
	long long result = -inf;
	REP(a, M) result = max(result, f[n][a]);
	cout << result << endl;
	return 0;
}

Measured memory_bytes: 83456
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e9 + 10, MOD = 1e9 + 7;

vector<vector<pair<ll, ll>>> gr;

ll n, m;
bool used[SIZE][2];
set<pair<ll, ll>> s;
ll dp[SIZE][2], dist[SIZE][2];

void djikstra(int st, int ind) {
	used[st][ind] = 1;
	
	for (int i = 0; i < n; i++) dist[i][ind] = INF;
	dist[st][ind] = 0;
	dp[st][ind] = 1;
	for (int i = 0; i < n; i++) {
		s.insert({ dist[i][ind], i });
	}

	while (!s.empty()) {
		pair<ll, ll> v = *(s.begin());
		s.erase(s.begin());

		for (auto to : gr[v.second]) {
			if (dist[to.first][ind] == to.second + dist[v.second][ind]) {
				dp[to.first][ind] += dp[v.second][ind];
				dp[to.first][ind] %= MOD;
			}
			else if (dist[to.first][ind] > to.second + dist[v.second][ind]) {
				dp[to.first][ind] = dp[v.second][ind];
				s.erase({ dist[to.first][ind], to.first });
				dist[to.first][ind] = to.second + dist[v.second][ind];
				s.insert({ dist[to.first][ind], to.first });
			}
		}
	}
}

vector<tuple<ll, ll, ll>> edges;

int main()
{
	fastInp;
	ll s, t;
	cin >> n >> m;
	cin >> s >> t;
	s--; t--;

	gr.resize(n);
	for (int i = 0; i < m; i++) {
		ll u, v, d;
		cin >> u >> v >> d;
		u--; v--;
		edges.push_back({ u, v, d });
		gr[u].push_back({ v, d });
		gr[v].push_back({ u, d });
	}

	djikstra(s, 0);
	djikstra(t, 1);

	ll ans = (dp[t][0] * dp[s][1]) % MOD;

	for (int i = 0; i < n; i++) {
		if (dist[i][0] == dist[i][1] && dist[i][1] + dist[i][0] == dist[t][0]) {
			ans -= ((dp[i][0] * dp[i][1]) % MOD * ((dp[i][1] * dp[i][0]) % MOD)) % MOD;
			if (ans < 0) ans += MOD;
		}
	}

	ll tD = dist[t][0];
	for (auto cur : edges) {
		ll u = get<0>(cur), v = get<1>(cur), d = get<2>(cur);
		if ((dist[u][0] + dist[v][1] + d == tD)) {
			if ((dist[u][0] * 2 < tD && dist[v][1] * 2 < tD)) {
				ans -= ((dp[u][0] * dp[v][1]) % MOD * ((dp[u][0] * dp[v][1]) % MOD)) % MOD;
				if (ans < 0) ans += MOD;
			}
		}
		else if ((dist[u][1] + dist[v][0] + d == tD)) {
			if ((dist[u][1] * 2 < tD && dist[v][0] * 2 < tD)) {
				ans -= ((dp[u][1] * dp[v][0]) % MOD * ((dp[u][1] * dp[v][0]) % MOD)) % MOD;
				if (ans < 0) ans += MOD;
			}
		}
	}

	cout << ans;

	return 0;
}

Measured memory_bytes: 29688
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define MOD 1000000007
#define MOD2 998244353
#define INF MOD
#define LINF (1LL<<60)
#define a (10LL<<18)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

// 繰り返し二乗法 n^k % mod
int64_t modpow(int n, int k, int mod) {
    int64_t ret = 1;
    int64_t multi = n;
    for (int i = 0; i < 31; i++) {
        if (k >> i & 1) ret = ret * multi % mod;
        multi = multi * multi % mod;    
    }
    return ret;
}

Int fact[1100000];
Int invfact[1100000];

Int nCk(int n, int k) {
    return fact[n] * invfact[k] % MOD * invfact[n-k] % MOD;
}

Int nPk(int n, int k) {
    return fact[n] * invfact[n-k] % MOD;
}

int main() {
    int n, m;
    cin >> n >> m;
    fact[0] = 1;
    for (int i = 1; i < 1100000; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    invfact[1100000 - 1] = modpow(fact[1100000 - 1], MOD - 2, MOD);
    for (int i = 1100000 - 1; i > 0; i--) {
        invfact[i-1] = invfact[i] * i % MOD;
    }
    Int ans = 0;
    for (int k = 0; k <= n; k++) {
        Int tmp = nCk(n, k) * nPk(m, k) % MOD * nPk(m-k, n-k) % MOD * nPk(m-k, n-k) % MOD;
        if (k % 2 == 0) {
            ans += tmp;    
        }
        else {
            ans -= tmp;
        }
        ans %= MOD;
    }
    if (ans < 0) ans += MOD;
    cout << ans << endl;
}



Measured memory_bytes: 20760
#include <iostream>
using namespace std;
int main(){
	int n, k;
	cin >> n >> k;
	int r, s, p;
	cin >> r >> s >> p;
	char t[n];
	cin >> t;
	int count = 0;
	for(int i = 0; i < n; i++){
		if(i>=k){
			if(t[i] == t[i-k]){
				t[i] = 'x';
				continue;
			}
		}
		if(t[i] == 'r')count+=p;
		if(t[i] == 's')count+=r;
		if(t[i] == 'p')count+=s;
	}
	cout  << count << endl;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const long double PI = acos(-1.0L);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
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; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  cout << s[0] << (int)s.size()-2 << s.back() << endl;
  return 0;
}

Measured memory_bytes: 256
S = list(input())
ans = 0
ans2 = 0
for i in range(len(S)):
    if i % 2 == 0:
        if S[i] == "0":
            ans += 1
    else:
        if S[i] == "1":
            ans += 1

for i in range(len(S)):
    if i % 2 == 0:
        if S[i] == "1":
            ans2 += 1
    else:
        if S[i] == "0":
            ans2 += 1

print(min(ans,ans2))

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

int main() {
    int n, ans = 0;
    string s;
    cin >> n >> s;
    for(int i = 0; i < n-2; ++i) {
        if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C') {
            ans++;
        }
    }
    cout << ans << '\n';
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		long sum = 0;
		string[] str = Console.ReadLine().Split();
		long[]A = new long[N];
		for(var i=0;i<N;i++){
			A[i] = long.Parse(str[i]);
			sum += A[i];
		}
		long mod = 1000000007;
		long ans = 0;
		for(var i=0;i<N;i++){
			sum -= A[i];
			long a = sum % mod;
			a = a * A[i];
			ans += a;
			ans %= mod;
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 43396
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

const vector<int> ToBinary(const int digitNum, LLONG n)
{
    vector<int> ret(digitNum);
    for (int i = digitNum - 1; i >= 0; --i)
    {
        ret[i] = n % 2;
        n /= 2;
    }
    return ret;
}

const LLONG ToLLONG(const int digitNum, const vector<int> &binary)
{
    LLONG ret = 0LL;
    LLONG base = 1LL;
    for (int i = digitNum - 1; i >= 0; --i)
    {
        ret += binary[i] * base;
        base *= 2;
    }
    return ret;
}

int main()
{
    int N, K; cin >> N >> K;
    LLONG sum = 0LL;
    vector<LLONG> cumSums(N + 1);
    for (int i = 0; i < N; ++i)
    {
        LLONG ai; cin >> ai;
        sum += ai;
        cumSums[i + 1] = sum;
    }
    // N <= 1e3 と小さいので，部分列の個数は高々 1e6 個
    // K 個の部分列の論理積を計算してなるべく大きな値を作るためには
    // なるべく上位のビットで K 個全てで 1 が立っている組を選ぶ必要がある
    // -> 全ての部分列の和について，上位ビットから順に 1 が立っているものを選んでいく:O(digitNum * N^2)
    const int digitNum = 40;    // 総和の最大値が 10^12 より，40桁あれば十分
    vector<vector<int>> binaries;
    for (int l = 0; l < N; ++l)
    {
        for (int r = l; r < N; ++r)
        {
            binaries.push_back(ToBinary(digitNum, cumSums[r + 1] - cumSums[l]));
        }
    }
    for (int d = 0; d < digitNum; ++d)
    {
        vector<vector<int>> ones;
        for (const auto &binary : binaries)
        {
            if (binary[d] == 1)
            {
                ones.push_back(binary);
            }
        }
        // １が立っているものがK個以上あれば全て残す
        if (ones.size() > K)
        {
            binaries = ones;
        }
        // １が立っているものがK個であればそれらを選択して終了
        else if (ones.size() == K)
        {
            binaries = ones;
            break;
        }
        // １が立っているものがK個未満であれば，どう選んでもANDをとったときこの桁は０
        // -> この桁だけでは選択しようがないので次に移る
        else
        {
            continue;
        }
    }
    LLONG ans = ToLLONG(digitNum, binaries.front());
    for (const auto &binary : binaries)
    {
        ans = ans & ToLLONG(digitNum, binary);
    }
    cout << ans << endl;
}


Measured memory_bytes: 120104
#include<bits/stdc++.h>
using namespace std;
int s[10];
int main() {
    int a,b;
    scanf("%d%d",&a,&b);
    int sum=0;
    for(int i=a; i<=b; i++) {
        int j=i,cnt=0;
        while(j) {
            s[cnt++]=j%10;
            j/=10;
        }
        bool flag=false;
        for(j=0; j<2; j++) {
            if(s[j]!=s[5-j-1])
                flag=true;
        }
        if(!flag)
            sum++;
    }
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


signed main() {
  string s, t; 
  cin >> s >> t;

  if(t.substr(0, s.size()) == s) Yes;
  else No;

  return 0;
}

Measured memory_bytes: 3644
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var v = new int[n];
        var inputs = Console.ReadLine().Split(' ');
        var oddCounts = new Dictionary<int, int>();
        var evenCounts = new Dictionary<int, int>();
        for (int i = 0; i < n; i++)
        {
            v[i] = int.Parse(inputs[i]);
            Dictionary<int, int> targetCounts = null;
            if (i % 2 == 0)
            {
                targetCounts = evenCounts;
            }
            else
            {
                targetCounts = oddCounts;
            }

            if (targetCounts.ContainsKey(v[i]))
            {
                targetCounts[v[i]]++;
            }
            else
            {
                targetCounts.Add(v[i], 1);
            }
        }

        var evenTop2 = evenCounts.OrderByDescending((pair) => pair.Value).Take(2).Select(pair => pair.Key).ToList();
        var oddTop2 = oddCounts.OrderByDescending((pair) => pair.Value).Take(2).Select(pair => pair.Key).ToList();
        if (oddTop2.Count == 1)
        {
            oddTop2.Add(0);
        }

        var count = dfs(v, evenTop2, oddTop2);
        Console.WriteLine(count);
    }

    static int dfs(int[] v, List<int> evenTop2, List<int> oddTop2)
    {
        int min = 1000000;
        foreach (var even in evenTop2)
        {
            foreach (var odd in oddTop2)
            {
                if (even == odd)
                {
                    continue;
                }

                int evenOddCount = CalcCost(v, even, odd);
                int oddEvenCount = CalcCost(v, odd, even);
                min = Math.Min(min, evenOddCount);
                min = Math.Min(min, oddEvenCount);
            }
        }
        return min;
    }

    static int CalcCost(int[] v, int even, int odd)
    {
        int count = 0;
        for (int i = 0; i < v.Length; i++)
        {
            if (i % 2 == 0)
            {
                if (v[i] != even)
                {
                    count++;
                }
            }
            else
            {
                if (v[i] != odd)
                {
                    count++;
                }
            }
        }

        return count;
    }

}



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

template <class String>
vector<size_t> Failure(const String &s) {
  vector<size_t> f(s.size(), 0);
  size_t k = 0;
  for (size_t i = 1; i < s.size(); ++i) {
    while (k > 0 && s[i] != s[k]) k = f[k - 1];
    if (s[i] == s[k]) k++;
    f[i] = k;
  }
  return f;
}

template <class String>
vector<size_t> Search(const String &s, const String &t) {
  auto f = Failure(t);
  vector<size_t> res;
  for (size_t i = 0, k = 0; i < s.size(); ++i) {
    while (k > 0 && (k == t.size() || s[i] != t[k])) k = f[k - 1];
    if (s[i] == t[k]) k++;
    if (k == t.size()) res.push_back(i - t.size() + 1);
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 0; i < n; ++i) cin >> b[i];
  vector<int> cnt(n), ans(n);
  for (int bit = 0; bit < 30; ++bit) {
    for (int z = 0; z < 2; ++z) {
      vector<int> x(n), y(n);
      for (int i = 0; i < n; ++i) x[i] = (a[i] >> bit & 1) ^ z;
      for (int i = 0; i < n; ++i) y[i] = (b[i] >> bit & 1);
      for (int i = 0; i < n - 1; ++i) x.push_back(x[i]);
      auto res = Search(x, y);
      for (int i = 0; i < res.size(); ++i) {
        cnt[res[i]]++;
        if (z) ans[res[i]] |= (1 << bit);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    if (cnt[i] == 30) {
      cout << i << ' ' << ans[i] << "\n";
    }
  }
  return 0;
}


Measured memory_bytes: 11224
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
typedef long long ll;
using namespace std;
int main(void){
    int n,t;cin>>n>>t;
    vector<pair<int,int>> p(n);
    rep(i,n) cin>>p[i].first>>p[i].second;
    sort(p.begin(),p.end());
    int dp[n+1][t+1];
    rep(i,n){
        rep(j,t) dp[i][j]=0;
    }
    int res=0;
    rep(i,n){
        int a=p[i].first;
        int b=p[i].second;
        rep(j,t){
            dp[i+1][j]=max(dp[i][j],dp[i+1][j]);
            int nj=j+a;
            if(nj<t)dp[i+1][nj]=max(dp[i+1][nj],dp[i][j]+b);
        }
        int now=dp[i][t-1]+b;
        res=max(now,res);
    }
    cout<<res<<endl;
}


Measured memory_bytes: 35456
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int N;
  cin >> N;
  int A[N];
  for(int i = 0; i < N; i++) cin >> A[i];
  bool flag = true;
  int Ans = -1;
  while(flag){
    for(int i = 0; i < N; i++){
      if(A[i]%2==0) A[i] /= 2;
      else{
        flag = false;
        break;
      }
    }
    ++Ans;
  }

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


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

int main() {
  int a,b;
  cin >> a >> b;
  if(a%3==0 || b%3==0 || (a+b)%3==0 ) cout << "Possible" << endl;
  else cout << "Impossible" << endl;
}


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

using ll=long long;
const int inf=100000000;

int in(){
  int a;
  cin >> a;
  return a;
}//int型関数の受け取り

void forin(int* x,int y){
  for (int i=0;i<y;i++){
    cin >> x[i];
  }
}//(x,y) int型配列x[y]の受け取り

int intpow(int x,int y){
  double a=x,b=y;
  return pow(a,b);
}//(x,y) xをy乗

int intfabs(int x){
  double a=x;
  return fabs(a);
}//(x) xの絶対値

int fact(int x){
  if (x == 1) return 1;
  return x*fact(x-1);
}//(x) x!

int fib(int x){
  if (x <= 2) return x;
  int a[x];
  a[0]=1;
  a[1]=2;
  for (int i=2;i<x;i++){
    a[i]=a[i-1]+a[i-2];
  }
  return a[x-1];
}//(x) フィボナッチ数列のx番目

int div1(ll x){
  return x%1000000007;
}

main(){
  int n=in();
  string s;
  cin >> s;
  int k=in();
  for (int i=0;i<n;i++){
    if (s.at(i)!=s.at(k-1)) s.at(i)='*'; 
  }
  cout << s << endl;
}

Measured memory_bytes: 256
import sys,os
from collections import defaultdict, deque
from math import ceil, floor
if sys.version_info[1] >= 5:
    from math import gcd
else:
    from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    MOD = 10**9+7

    N,K = LMIIS()
    A = LMIIS()
    visited = [False]*N
    dest = defaultdict(int)
    ep = 1
    for i,a in enumerate(A):
        dest[i+1] = a

    visited = [0]*(N+1)
    o = 1
    loop = 0
    visited[o] = loop

    while visited[dest[o]] == 0:
        loop += 1
        visited[dest[o]] = loop
        o = dest[o]
    
    # print('o=',o)
    preloop = visited[dest[o]]
    loop = loop - visited[dest[o]] + 1
    # print(preloop,loop)
    # print(visited)
    origin = 1
    if K <= preloop: 
        for i in range(K):
            origin = dest[origin]
        print(origin)
        return

    num_visit = (K - preloop) % loop
    
    for i in range(preloop):
        origin = dest[origin]
    for i in range(num_visit):
        if dest[origin] == origin:
            break
        origin = dest[origin]
    print(origin)




    

if __name__ == '__main__':
    main()

Measured memory_bytes: 116852
from math import ceil

def attack(ab,N,H):
    cut_max = 0
    for i in range(N):
        cut_max = max(cut_max,ab[i][0])

    throw = [ab[i][1] for i in range(N)]
    throw.sort(reverse = True)
    throw.append(0)

    cnt,pt = 0,0
    while H > 0:
        if throw[pt] > cut_max:
            H -= throw[pt]
            cnt += 1
            pt += 1
        else:
            cnt += (ceil(H/cut_max))
            H = 0

    return cnt

def main():
    N,H = map(int,input().split())
    ab = [list(map(int,input().split())) for _ in range(N)]

    print(attack(ab,N,H))

if __name__ == "__main__":
    main()


Measured memory_bytes: 28588
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	for scanner.Scan() {
		n, _ := strconv.Atoi(scanner.Text())
		println(n)
		fmt.Println((n/15)*11800 + (n%15)*800)
		break
	}
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
    static String a[];
    static String n;
    static String ans;

  public static void main(String[] args) {
	  Scanner sc = new Scanner(System.in);
	  n = sc.next();
	  a = new String[n.length()];
	  for(int i = 0; i < n.length(); i++) {
		  a[i] = n.substring(i, i+1);
	  }
	  if(dfs(0,a[0],Integer.parseInt(a[0]))){
		  System.out.println(ans+"=7");
	  }
      sc.close();
  }
  static public Boolean dfs(int i,String sum,int sum2) {
	//基本ケース　枝の最後の基本ケース
    if (i == n.length()-1) {
    		if (sum2 == 7) {
    			ans = sum;
    			return true;
    		}
    		return false;
    }

    //再帰ケース
    if(dfs(i + 1,sum + "+" + a[i+1],sum2 + Integer.parseInt(a[i+1]))) return true;
    if(dfs(i + 1,sum + "-" + a[i+1],sum2 - Integer.parseInt(a[i+1]))) return true;

    return false;
  }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
using namespace std;
char a[5];
int main() {
	int x,i,k=0,l=0,m=0,n=0;
    cin>>x;
    for(i=0;i<x;i++)
    {
    	cin>>a;
    	if(a[0]=='A' && a[1]=='C')
    	k++;
    	if(a[0]=='W' && a[1]=='A')
    	l++;
    	if(a[0]=='T' && a[1]=='L' && a[2]=='E')
    	m++;
    	if(a[0]=='R' && a[1]=='E')
    	n++;
    	
    }
    cout<<"AC x "<<k<<endl;
    cout<<"WA x "<<l<<endl;
    cout<<"TLE x "<<m<<endl;
    cout<<"RE x "<<n<<endl;
	return 0;
}

Measured memory_bytes: 3616
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

import static java.lang.Integer.parseInt;

public class Main {

  public static void main(String[] args) {
    new Main().run();
  }

  public void run() {

    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      int n = parseInt(in.readLine());

      Point[] reds  = new Point[n];
      Point[] blues = new Point[n];
      String[] lines;
      for(int i=0, x=0, y=0; i<n; i++) {
        lines = in.readLine().split(" ");
        x = parseInt(lines[0]);
        y = parseInt(lines[1]);
        reds[i] = new Point(x, y); 
      }
      for(int i=0, x=0, y=0; i<n; i++) {
        lines = in.readLine().split(" ");
        x = parseInt(lines[0]);
        y = parseInt(lines[1]);
        blues[i] = new Point(x, y); 
      }

      Arrays.parallelSort(reds, new Comparator<Point>() {
        public int compare(Point a, Point b) {
          if(a.y == b.y) return 0;
          return a.y > b.y ? -1 : 1;  // 昇順
        }
      });

      Arrays.parallelSort(blues, new Comparator<Point>() {
        public int compare(Point a, Point b) {
          if(a.x == b.x) return 0;
          return a.x > b.x ? 1 : -1;  // 降順
        }
      });

      boolean[] isDone = new boolean[n];

      int ans = 0;
      for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
          if(!isDone[j] && reds[j].x < blues[i].x && reds[j].y < blues[i].y) {
            ans++;
            isDone[j] = true;
            break;
          }
        }
      }

      System.out.println(ans);
    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()

Int INF = 1e18;
Int mod = 1e9+7;
//Int mod = 998244353;

typedef struct {
    Int y, x;
} p_t;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Int n;
    cin >> n;
    vector<Int> a(3 * n);
    for (Int i = 0; i < 3 * n; i++) {
        cin >> a[i];
    }
    priority_queue<Int, vector<Int>, greater<Int>> q1;
    priority_queue<Int> q2;
    Int l_sum = 0;
    for (Int i = 0; i < n; i++) {
        l_sum += a[i];
        q1.push(a[i]);
    }
    Int r_sum = 0;
    for (Int i = 2 * n; i < 3 * n; i++) {
        r_sum += a[i];
        q2.push(a[i]);
    }
    vector<Int> rs(n + 1, r_sum);
    for (Int i = 2 * n - 1; i >= n; i--) {
        if (q2.top() <= a[i]) {
            rs[i - n] = r_sum;
            continue;
        }
        r_sum -= q2.top();
        q2.pop();
        r_sum += a[i];
        q2.push(a[i]);
        rs[i - n] = r_sum;
    }
    Int res = l_sum - r_sum;
    for (Int i = n; i < 2 * n; i++) {
        if (q1.top() < a[i]) {
            l_sum -= q1.top();
            q1.pop();
            l_sum += a[i];
            q1.push(a[i]);
        }
        res = max(res, l_sum - rs[i - n + 1]);
    }
    dump(res);
    return 0;
}

Measured memory_bytes: 5108
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll h,w;
	cin>>h>>w;
	if(h==1&&w==1){
		cout << 1;
		return 0;
	}
	if(h==1||w==1){
		cout << (h*w-2>=0? h*w-2:0);
		return 0;
	}
	cout << 	h*w-(2*h+2*w-4);
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
//#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
template <class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template <class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template <class T> inline T gcd(T a, T b) {if(a==0) return b; return gcd(b%a,a);}
template <class T> inline T lcm(T a, T b) {return a * b / gcd(a,b);}
template <class T> inline T sum(vector<T> &vec) {T res=0; for (int i = 0; i < vec.size(); i++) res += vec[i]; return res;}
template <class T> inline T mpow(T a, T b) {if(b==0)return 1; T c = mpow(a,b/2);if(b%2==1)return c*c*a; return c*c;}
const int INF = 1 << 30;
const long long INFLL = 1LL << 60;
typedef pair<int, int> P;

#define REP(i,n) for (int (i)=0;(i)<(n);(i)++)
#define FOR(i,n) for (int (i)=0;(i)<(n);(i)++)
#define REPB(i,n) for (int (i)=((n)-1);(i)>=0;(i)--)
#define FORB(i,n) for (int (i)=((n)-1);(i)>=0;(i)--)
#define SORT(A) sort((A).begin(),(A).end())

int main() {
    /*
    string S, T;
    cin >> S >> T;
    cout << T + S << endl;
*/
    ll A, B, K; cin >> A >> B >> K;
    if (K > A) {
        cout << 0 << " " << max(0LL,B - (K-A)) << endl;
    } else {
        cout << A-K << " " << B << endl;
    }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int main(void){
	int n,i,tmp[26],ans[26],j;
	string s;
	cin >> n;
	fill(ans,ans+26,INF);
	for(i=0; i<n; ++i){
		cin >> s;
		fill(tmp,tmp+26,0);
		for(j=s.l_ength()-1; j>=0; --j){
			++tmp[s[j]-'a'];
		}
		for(j=0; j<26; ++j){
			ans[j] = min(ans[j],tmp[j]);
		}
	}
	for(j=0; j<26; ++j){
		for(i=0; i<ans[j]; ++i){
			cout << ((char)('a'+j));
		}
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <deque>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int n;
  string s;
  cin >> n >> s;
  vector<int> r, g, b;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'R') r.push_back(i);
    else if (s[i] == 'G') g.push_back(i);
    else b.push_back(i);
  }
  ll ans = 0;
  for (auto i : r) {
    for (auto j : g) {
      for (auto k : b) {
        if (i + j == 2 * k) continue;
        if (j + k == 2 * i) continue;
        if (k + i == 2 * j) continue;
        ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3204
import java.util.*;

class Main {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for(int i=0;i<N;i++){
            A[i] = sc.nextInt();
        }
        //ここまで入力
        int ans = 0;
        int check = 1;
        boolean flag = true;

        //数列探索
        for(int i=0; i<N; i++){
            if(A[i] == check) {
                check++;
            } else ans++;
        }
        if(ans == N) flag = false;

        if(flag == true){
            System.out.println(ans);
        }else System.out.println("-1");
    }
}

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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

typedef pair<double, double> pd;
typedef vector<pd> vpd;


#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> t chmax(t&a,u b){if(a<b)a=b; return a;};
template<class t, class u> t chmin(t&a,u b){if(a>b)a=b; return a;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N;
  IN(N);
  vpll RL(N);
  REP(i,N){
    IN(RL[i].second, RL[i].first);
  }

  sort(ALL(RL));

  vll Lmax(N, RL[0].second);
  REP(i,N-1){
    Lmax[i+1] = max(Lmax[i], RL[i+1].second);
  }

  /*
  REP(i,N){
    debug_print(RL[i].second, RL[i].first);
  }
  */

  ll ans = max(RL[0].first-Lmax[N-2]+1, (ll)0)+(RL[N-1].first-RL[N-1].second)+1;
  ll Lmax_after = RL[N-1].second;
  for(ll i=N-2; i>0; --i){
    ll Lmax1 = Lmax[i-1];
    ll Rmin1 = RL[0].first;
    ll Lmax2 = RL[i].second;
    ll Rmin2 = RL[i].first;

    ll LR1 = max(Rmin1-Lmax1+1, (ll)0);
    ll LR2 = max(Rmin2-Lmax2+1, (ll)0);
    ll LR1_1 = max(Rmin1-max(Lmax_after, Lmax1)+1, (ll)0);
    ll LR2_1 = max(Rmin2-max(Lmax_after, Lmax2)+1, (ll)0);

    ll ans_tmp = max(LR1+LR2_1, LR1_1+LR2);

    chmax(ans, ans_tmp);
    chmax(Lmax_after, Lmax2);
  }

  OUT(ans);

  return 0;
}


Measured memory_bytes: 2560
def num_2pow(n: int) -> int:
    '''素因数分解した際の 2 の指数を求める。
    '''
    count = 0
    while n & 1 == 0:
        count += 1
        n >>= 1
    return count


def shift_only(N: int, A: list) -> int:
    return min(num_2pow(a) for a in A)


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = shift_only(N, A)
    print(ans)


Measured memory_bytes: 3060
from collections import Counter

N = int(input())
V = [int(i) for i in input().split()] 

if sum(V)/N == V[0] and sum(V)/N == V[N-1]:
  print(N//2)
  exit()

def get_most_common(lis):
  c = Counter(lis)
  m = c.most_common()
  return m

odds = V[0::2]
evens = V[1::2]

m_odds = get_most_common(odds)
m_evens = get_most_common(evens)

if m_odds[0][0] == m_evens[0][0]:
  minus = max(m_odds[0][1] + m_evens[1][1], m_odds[1][1] + m_evens[0][1])
else:
  minus = m_odds[0][1] + m_evens[0][1]
  
print(N - minus)

Measured memory_bytes: 21084
#include <stdio.h>
int main(void)
{
	for(;;)
	{
		int p,s[10],f=0,n,m,c;
		char d[101];
		scanf("%d",&p);
		if(p==0)
		{
			break;
		}
		for(n=0;n<10;n++)
		{
			s[n]=0;
		}
		scanf("%s",&d);
		for(n=0;n<100;n++)
		{
			if(d[n]=='M')
			{
				s[n%p]++;
			}
			else if(d[n]=='S')
			{
				f+=s[n%p]+1;
				s[n%p]=0;
			}
			else if(d[n]=='L')
			{
				s[n%p]+=f+1;
				f=0;
			}
		}
		for(n=0;n<p;n++)
		{
			for(m=n+1;m<p;m++)
			{
				if(s[n]>s[m])
				{
					c=s[n];
					s[n]=s[m];
					s[m]=c;
				}
			}
		}
		for(n=0;n<p;n++)
		{
			printf("%d ",s[n]);
		}
		printf("%d\n",f);
	}
	return 0;
}

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

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

    char d[n + 1];
    memset(d, 0, sizeof d);
    d[0] = 1;
    for (int i = 100; i <= 105; ++i) {
        for (int j = i; j <= n; ++j)
            d[j] |= d[j - i];
    }

    cout << int(d[n]) << endl;
}


Measured memory_bytes: 384
#include <stdio.h>

#define INF 999999999

const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int H, W;
char s[64][64];

int Qstart, Qend;
int q[64 * 64][2];

int saitan[64][64];

int main(void) {
	int i, j;
	int count;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 1; i <= H; i++) {
		if (scanf("%62s", s[i] + 1) != 1) return 1;
	}
	for (i = 0; i <= H + 1; i++) {
		for (j = 0; j <= W + 1; j++) saitan[i][j] = INF;
	}
	saitan[1][1] = 0;
	q[0][0] = 1; q[0][1] = 1;
	Qstart = 0; Qend = 1;
	while (Qstart < Qend) {
		int y = q[Qstart][0], x = q[Qstart][1];
		Qstart++;
		for (i = 0; i < 4; i++) {
			int ny = y + d[i][0], nx = x + d[i][1];
			if (s[ny][nx] == '.' && saitan[ny][nx] > saitan[y][x] + 1) {
				saitan[ny][nx] = saitan[y][x] + 1;
				q[Qend][0] = ny;
				q[Qend][1] = nx;
				Qend++;
			}
		}
	}
	count = 0;
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) {
			if (s[i][j] == '.') count++;
		}
	}
	printf("%d\n", saitan[H][W] < INF ? count - (saitan[H][W] + 1) : -1);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll n;
cin>>n;
cout <<(n-1)/2<< endl;
return 0;}



Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPLL(i, n) for (ll i = 0; i < (ll)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, X, Y; cin >> N >> X >> Y; X--; Y--;
  vector<int> ans(N, 0);
  REP(i, N-1){
    for(int j = i; j < N; j++){
      int tmp = min({abs(j-i), abs(i-X)+abs(j-Y)+1, abs(i-Y)+abs(j-X)+1});
      ans[tmp]++;
    }
  }
  for(int i = 1; i < N; i++){
    cout << ans[i] << endl;
  }
}

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

const int MOD = 1000000007;

ll pow(int n){
  ll p = 1;
  for (int i = 0; i < n; i++) {
    p = p * 4 % MOD;
  }
  return p;
}

int main() {
  
  int N;
  cin >> N;
  int POW = pow(N-1);
  
  vector<ll> c;
  for (int i = 0; i < N; i++) {
    ll n;
    cin >> n;
    c.push_back(n);
  }
  sort(c.begin(), c.end());
  
  
  
  
  ll ans = 0;
  for (int i = 0; i < N; i++) {
    ll p = 1;
    p = (p * (N-i+1)) % MOD;
    p = (p * c[i]) % MOD;
    ans = (ans + p) % MOD;
  }
  ans = (ans * POW) % MOD; 
  
  cout << ans << endl;
}


Measured memory_bytes: 2420
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int bsearch(vector<int> arr, int el)
{
    int l = 0, r = arr.size() - 1, mid;

    while (l <= r)
    {
        mid = (l + r) / 2;
        if (arr[mid] == el) return mid;
        if (arr[mid] > el) r = mid - 1;
        if (arr[mid] < el) l = mid + 1;
    }
    return -1;
}

bool containsDigits(int n, vector<int> d)
{
    while (n > 0)
    {
        if (bsearch(d, n % 10) != -1) return true;
        n = n / 10;
    }
    return false;
}

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> d(k);
    for (int i = 0; i < k; i++) cin >> d[i];
    while (containsDigits(n, d) != false) n++;
    cout << n << endl;
}

Measured memory_bytes: 256