akhauriyash/Code-Regression huggingface dataset:
//shara's here
//私は大きな男の子
//SPEEEEEEEEEED IS KEEEEEEEEEEY
//REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEAAAAAAAAAAAAAAAAAAAADDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
#include <bits/stdc++.h>
using namespace std;
//fold
typedef string s;
typedef long long ll;
typedef long double ld;
const ll INF = 1e18 + 10;
const ll MINF = -(1e18 + 10);
#if defined(BANYANYA)
#include "/home/xsharawi/Desktop/cpp/debug.hpp"
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define pb push_back
#define vl vector<ll>
#define vll vector<vector<ll> >
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
//endfold
ll sum(ll x){
	ll sumi=0;
	for(ll i=0;i<=x;i++)sumi+=i;
	return sumi;
	}
int main(){
    ll t,sum=0;
    cin>>t;
    while(t--){
	ll x,y;
	cin>>x>>y;
	sum+=((y-x)+1);
	}
	cout<<sum<<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

return 0;}
/*
███████████████████████████████████████████████████
███████████████████████████████████████████████████
██████████████████████████████████▀████████████████
██████████████████████████████████░▀███████████████
██████████████████████████████▌███░░░▀▀████████████
██▀████████████████████▐██████░▐██░░░░░░▀▀█████████
██░████████████████████▐█████▌░██▌▄░░░░▄▄░▄████▀███
█▌░███████████████████▀░█████░░░█░░░▄████░░███▀▐███
█▌░▐██████████████████░░████▌░░░▀░░▀███▀▀░▐███▄████
██░▀██████████████▌▐█▐▄▄████▌░░░░░░░░░░░░░▌████████
███░███████████████▀░▄▄██▀█▐░░░░░░░░░░░░░░▐████████
███▄░██████████████▄░░░░░░▀▀▀░░░░░░░░░░░░░█▐███████
████▄░██████████████████▄▄▄▄▄▄▐▄░░░░░░░░░░░████████
█████▄█████████████████▀▀▀▀▀▀░░░░░░░░░░░░░░████████
████████████████████████▄░░░░░░░░░░░░░░░▄░░████████
██████████████████████████▄▄▄░░░░░░░░░▄█░▄█████████
████████████████████████████████▄░░░░██▄███▀░░▀████
█████████████████████████████▀█████▄███▀▀▀░░▄▄░████
████████████████████████████▀░░▀░░▀▀░░░░▄▄▄██▀░░▀▀█
███████████████████████████▌░░░░░░░░░░░███████░░░▄█
███████████████▄░▀████████▀░░░░░░▀░░░░███████▌░░░██
███▄▄████████████▄░▀██████▄░░░░░█░░░░████████░░░▀▀
░▀█████████████████▄░▀█████░░░░██░░░░▀██████░░░░░▄█
▐█▄▀█████████████████▄░▀████░░░██▌░░░▐████▀░░░░▄███
▐███▄▀▀█████████████████▄░▀▀░░░░▀██▌▄█▀▀░░░▄▄██████
▀▀▀▀▀░░░▀▀▀▀▀░░░▀▀▀▀▀▀▀▀▀▀▀░░░░░░░▀▀░░░░░░▀▀▀▀▀▀▀▀▀
*/


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

template<typename T> struct FordFulkerson{
	struct edge{
		int to,rev;
		T cap;
	};
	vector< vector<edge> > G;
	deque<bool> vis;
	void init(int n){
		G.assign(n,vector<edge>());
		vis.assign(n,false);
	}
	void add_edge(int from,int to,T cap){
		G [from].push_back(edge{to,int(G [to].size()),cap});
		G [to].push_back(edge{from,int(G [from].size()) - 1,0});
	}
	T dfs(int curr,int t,T f){
		if(curr == t) return f;
		vis [curr] = true;
		for(int i = 0;i < int(G [curr].size());i++){
			edge& e = G [curr] [i];
			if(e.cap > 0 && vis [e.to] == false){
				T d = dfs(e.to,t,min<T>(f,e.cap));
				if(d == 0) continue;
				e.cap -= d;
				G [e.to] [e.rev].cap += d;
				return d;
			}
		}
		return 0;
	}
	T max_flow(int s,int t){
		T flow = 0;
		while(true){
			fill(vis.begin(),vis.end(),false);
			T d = dfs(s,t,numeric_limits<T>::max());
			if(d == 0) break;
			flow += d;
		}
		return flow;
	}
};

int N,M;

int main()
{
	scanf("%d%d",&N,&M);
	FordFulkerson<int> ff;
	ff.init(N);
	FOR(i,0,M){
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
		ff.add_edge(u,v,c);
	}

	printf("%d\n",ff.max_flow(0,N - 1));

	return 0;
}

Measured memory_bytes: 3324
using System;

namespace ABC158B
{
    static class Program
    {
        static void Main()
        {
            long[] nbrs = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
            var result = nbrs[0] / (nbrs[1] + nbrs[2]) * nbrs[1];
            var remaining = nbrs[0] % (nbrs[1] + nbrs[2]);
            result += Math.Min(remaining, nbrs[1]);
            Console.WriteLine(result);
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))
#define INFL 0x3f3f3f3f3f3f3f3fLL
typedef vector<vector<ll> > matrix;
const int mod = 1e9+7;
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll expo(ll base,ll pow){
    ll ans = 1;
    while(pow!=0){if(pow&1==1){ans = ans*base;ans = ans%mod;}
        base *= base;base%=mod;pow/=2;}return ans;}
ll inv(ll x){return expo(x,mod-2);}

double pi = 3.141592653589793238462643;
double error = 0.0000001;
int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};
/* -------Template ends here-------- */

const int M = 100001;

int l(ll x){
    int ans = 0;
    while(x%2 == 0){
        x/=2;
        ans++;
    }
    return ans;
}
int main(){
    //freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
    //cin.sync_with_stdio(false);
    //cin.tie(0); cout.tie(0);


    int a = 0 , b = 0 , c = 0;

    int n;
    si(n);

    for(int i = 1 ; i <= n  ;i++){
        ll el;
        sll(el);
        int x = l(el);
        if(x == 0){
            a++;
        }
        else if(x > 1){
            c++;
        }
        else if(x == 1){
            b++;
        }
    }

    if(c >= a || (c >= (a - 1) && b == 0)){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }


















}














Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll mod=1e9+7;
#define endl '\n'
#define SIGMA 128
const ld PI=3.14159265358979;
#define fr(i,n) for(i=1;i<=n;i++)
#define rep(i,k,n) for(i=k;i<=n;i++)
#define w(x) int x;cin>>x;while(x--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define ps(x,y) cout<<fixed<<setprecision(y)<<x<<endl
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vll vector<ll>
#define vvl vector<vll>
#define ppi pair<int,int>
#define ppl pair<ll,ll>
#define F first
#define S second 
#define LB lower_bound
#define UB upper_bound
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ll binpow(ll x, ll y, ll p){  ll res = 1;x = x % p;if (x == 0)return 0;while (y > 0)  { if (y & 1) res = (res*x) % p; y = y>>1;x = (x*x) % p;}return res;}  
ll gcd(ll a, ll b){ if (b == 0) return a; return gcd(b, a % b); } 
bool parity(ll x,ll y){ bool f = ((x ^ y) < 0);return !f;}


int main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    IOS

    ll n,i,j;
    cin>>n;
    ll score[n+1][n+1];
    fr(i,n)
        fr(j,n)
            cin>>score[i][j];

    ll dp[(1<<n)+1];

    rep(i,0,(1<<n)-1)
    {
        vll temp;
        for(j=0;j<n;j++)
        {
            if((1<<j)&i)
                temp.eb(j+1);
        }
        dp[i]=0;
        for(auto u: temp)
            for(auto v:temp)
                dp[i]+=score[u][v];
        dp[i]/=2;
    }
    rep(i,0,(1<<n)-1)
    {
        for(ll j=i;j>0;j=(j-1)&i)
        {
            dp[i]=max(dp[i],dp[j]+dp[i^j]);
        }
    }
    cout<<dp[(1<<n)-1]<<endl;

    return 0;  
}



Measured memory_bytes: 4152
@n = gets.to_i
@d = gets.split.map(&:to_i)

@memo = Array.new(24)
@memo[0] = 1
def calc(i)
    if i == @n
        a = -24
        x = 24
        @memo.each_with_index do |e, j|
            next if !e
            x = [x, j - a].min
            a = j
        end
        [x, 24 - a].min
    else
        x = []
        if !@memo[@d[i]]
            @memo[@d[i]] = 1
            x << calc(i+1)
            @memo[@d[i]] = nil
        end

        if !@memo[24-@d[i]]
            @memo[24-@d[i]] = 1
            x << calc(i+1)
            @memo[24-@d[i]] = nil
        end

        x.empty? ? 0 : x.max
    end
end

p calc(0)


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

int main()
{
    string s, t, temp,t1;
    cin>>s;
    t = s;
    int f=0;
    reverse(t.begin(), t.end());
    if(t==s)
    {
        
        temp = s.substr(0, ((s.length()-1)/2));
        t1=temp;
        reverse(t1.begin(), t1.end());
        if(t1==temp)
        {
            temp = s.substr(((s.length()+3)/2)-1, s.length() - ((s.length()+3)/2)+1);
            t1=temp;
            reverse(t1.begin(), t1.end());
            if(t1==temp)
            {
                cout<<"Yes"<<endl;
                return 0;
            } 
        }
    }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const unsigned int M = 1000000007;
int data[105];
void sum(){
    data[0]=0,data[1]=1;
    for(int i=2;i<105;i++){
        data[i]=data[i-1]+i;
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int a,b,c;
    while(cin>>a>>b>>c){
        if(c>=a&&c<=b)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
function Main(input){
  input = input.split("\n");
	var T = Number(input[1].split(" ")[0]);
	var A = Number(input[1].split(" ")[1]);
	var H = input[2].split(" ").map((a)=>Number(a));
  var log = [5000000,0];
  for(var i=0;i<H.length;i++){
    var tmp=Math.abs((T-H[i]*0.006)-A);
    if(tmp<log[0]){
      log=[tmp,i+1];
    }
  }

  console.log(log[1]);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int W, a, b;
    cin >> W >> a >> b;
    if (a <= b + W && b <= a + W) {
        cout << 0 << endl;
        return 0;
    }
    cout << min(abs(b - (a + W)), abs(b+W - a)) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include<cstdio>
using namespace std;
char s[4];
int num[4];
int main()
{
    cin>>s;
    for(int i =0;i<4;i++)num[i] = s[i] - '0';
    for(int i =0;i<8;i++){
        int ans =0;
        if( i & 4 ) ans = num[0] + num[1];
        else ans = num[0] - num[1];
        if( i & 2 ) ans = ans + num[2];
        else ans = ans - num[2];
        if( i & 1) ans = ans + num[3];
        else ans = ans - num[3];

        if( ans == 7){
            printf("%d%c%d%c%d%c%d=7", num[0], i&4?'+':'-' , num[1],
                   i&2?'+':'-', num[2],
                   i&1?'+':'-', num[3]);
            return 0;
        }
    }
     return 0;
}


Measured memory_bytes: 256
n = int(input())
p = input().split()

ct = 0
for i in range(n-2):
    a = int(p[i])
    b = int(p[i+1])
    c = int(p[i+2])
    if a < b and b < c:
        ct += 1
    if c < b and b < a:
        ct += 1
print(ct)


Measured memory_bytes: 3060
import math

def main():
    R,G,B=map(int,input().split())
    K=int(input())

    #R<G<B
    res=0

    if G<=R:
        m=R/G
        n=int(math.log2(m))+1
        res+=n
        G=G*pow(2,n)
        if B<=G:
            m=G/B
            n=int(math.log2(m))+1
            res+=n
    elif B<=G:
        m=G/B
        n=int(math.log2(m))+1
        res+=n

    if res<=K:
        print("Yes")
    else:
        print("No")


if __name__=="__main__":
    main()

Measured memory_bytes: 62432
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>

using namespace std;

int main(){

  int n, x[100010]={}, y[100010]={}, t[100010]={};

  cin>>n;
  for(int i=1;i<=n;i++) cin>>t[i]>>x[i]>>y[i];

  for(int i=1;i<=n;i++){
    int dt=t[i]-t[i-1], dd=abs(x[i]-x[i-1])+abs(y[i]-y[i-1]);
    dt-=dd;
    if(dt<0){
      cout<<"No"<<endl;
      return 0;
    }else{
      if(dt%2){
        cout<<"No"<<endl;
        return 0;
      }
    }
  }

  cout<<"Yes"<<endl;

  return 0;
}


Measured memory_bytes: 1408
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] line = Stream.of(sc.nextLine().split(" ", 0)).mapToInt(Integer::parseInt).toArray();
		if (line[1] == 0) {
			System.out.println(line[0]);
		} else {
			int[] nums = Stream.of(sc.nextLine().split(" ", 0)).mapToInt(Integer::parseInt).toArray();
			int con = 0;
			boolean isLowerConFlg = false;
			boolean isUpperConFlg = false;
			while (true) {
				isLowerConFlg = false;
				isUpperConFlg = false;

				for (int i = 0; i < nums.length; i++) {
					if (nums[i] == (line[0] - con)) {
						isLowerConFlg = true;
						break;
					}
				}
				if (isLowerConFlg == false) {
					System.out.println(line[0] -con);
					break;
				}
				for (int i = 0; i < nums.length; i++) {
					if (nums[i] == (line[0] + con)) {
						isUpperConFlg = true;
						break;
					}
				}
				if (isUpperConFlg == false) {
					System.out.println(line[0] + con);
					break;
				}
				con++;
			}
		}

	}


}


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

int min_change(int N,string S){
    int kuro=0,shiro=0;

    for(int i=0;i<N;i++){
        if(S[i]=='.') shiro++;
    }
    int m=shiro;
    for(int i=0;i<N;i++){
        if(S[i]=='#') kuro++;
        if(S[i]=='.') shiro--;
        m = min(m,(kuro+shiro));
    }

    return m;
}

int main(){
    int N;
    string S;
    cin >> N >> S;
    cout << min_change(N,S) << endl;
    return 0;
}

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

const int N = 1E3+7;
const int INF = 1E9+7;
int mp[N][N];
int arr[N];
int n, m, k;
vector<int> ve;     //ve保存当前对行分割的结果

// 首先使用二进制枚举方法对行进行分割，然后根据行分割结果，判断每一列是否需要分割

// 用来计算从第x行到y行的第j列的值
int cal(int x, int y, int j)
{
    int sum = 0;
    for(int i = x; i <= y; i++)
        sum += mp[i][j];
    return sum;
}

// 计算当前针对行分割的sum
int check()
{
    int sum = 0;
    int len = ve.size();
    bool flag = 0;
    for(int i = 1; i < len; i++)    arr[i] = 0;

    // 计算每列是否需要分割
    for(int i = 1; i <= m; i++)
    {
        // 分别计算每个行分割的数字为1的总数
        for(int j = 1; j < len; j++)
        {
            arr[j] += cal(ve[j - 1] + 1, ve[j], i);
            if(arr[j] > k) 
            {
                sum++;
                flag = 1;
                break;
            }
        }
        if(!flag)   continue;
        flag = 0;
        // 如果加上当前列之后，分割的结果不符合要求，则将当前列进行分割
        for(int j = 1; j < len; j++)
        {
            // 将当前列的分割值重新赋给arr[j]
            arr[j] = cal(ve[j - 1] + 1, ve[j], i);
            // 如果只对当前列进行分割的结果还是不符合要求，则返回最大值，当前行分割不在继续进行分割
            if(arr[j] > k)  return INF;
        }
    }
    return sum;
}

int main()
{
    cin>>n>>m>>k;
    char x;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
        {
            cin>>x;
            if(x == '1')    mp[i][j] = 1;
            else    mp[i][j] = 0;
        }

    // 计算当前行分割的所有二进制数量
    int c = (1 << (n - 1)) - 1;
    int ans = INF;

    for(int i = 0; i <= c; i++)
    {
        ve.push_back(0);
        // 判断当前行是否被分割, 0表示从第1行进行分割, n - 2表示从第n - 1进行分割
        for(int j = 0; j < n - 1; j++)
        {
            if((1 << j) & i)   ve.push_back(j + 1); 
        }
        ve.push_back(n);
        int c = ve.size();
        ans = min(ans, c - 2 + check());
        ve.clear();
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r) for(long long i = l; i < r; i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define V_MAX 100001
vector<ll> G[V_MAX];
map<pair<ll,ll>, ll> Cost;
vector<ll> color(V_MAX,0);


// 2部グラフ判定
// 1. 色の反転は問題にならないので、初期値は1で塗る
// 2. 同色の頂点を取り出し、距離が偶数かを判定
bool is_bipartite(ll v, ll c){
    color[v] = c;
    rep(i, 0, G[v].size()){
      	//cout << v+1 << " " << G[v][i]+1 << " " << Cost[mp(v,G[v][i])] << endl;
        if(color[G[v][i]] == c && Cost[mp(v,G[v][i])] % 2 == 1){
            return false;
        }
        if(color[G[v][i]] == 0 && Cost[mp(v,G[v][i])] % 2 == 1){
            is_bipartite(G[v][i], -c);
        }else if(color[G[v][i]] == 0 && Cost[mp(v,G[v][i])] % 2 == 0){
            is_bipartite(G[v][i], c);
        }
    }
    return true;
}

int main(){
    ll n; cin >> n;
    
    rep(i,0,n-1){
        ll u, v, w;
        cin >> u >> v >> w;
      	u--; v--;
        G[u].pb(v); G[v].pb(u);
      	//cout << w << endl;
        Cost[mp(u,v)] = w; Cost[mp(v,u)] = w;
    }

    if(is_bipartite(0, 1)){
        rep(i,0,n) cout << (color[i] == 1 ? 1 : 0) << endl;
    }else{
        cout << "-1" << endl;
    }

}

Measured memory_bytes: 23552
S = input().split(" ")
N = int(S[0])
M = int(S[1])

arr = []
for i in range(N):
    Q = input().split(" ")
    arr.append([int(q)for q in Q])

arr.sort(key=lambda s: s[0])

count = 0
total = 0
for a in arr:
    if count + a[1] <= M:
        total += a[0] * a[1]
        count += a[1]
    else:
        total += a[0] * (M - count)
        count += (M - count)
        break

print(total)


Measured memory_bytes: 22820
#include <cmath>
#include <cstdio>
#include <limits>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>
#include <iomanip>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  string s, t;
  cin >> s >> t;
  bool isAns = false;
  ll n = s.size();
  rep(i, n) {
    s = s.substr(n - 1, 1) + s.substr(0, n - 1);
    if (t == s) isAns = true;
  }
  if (isAns) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

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

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vllin3(a,b,c,n) vll (a)(n);vll (b)(n);vll (c)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vlling(x,n) (x).assign(n,0);FOR(i,0,n-1){cin >>(x)[i];}
#define vlling2(a,b,n) (a).assign(n,0);(b).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vlling3(a,b,c,n) (a).assign(n,0);(b).assign(n,0);(c).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;

ll solve(ll m,ll n){
        if(m%n==0) return n;
        return solve(n,m%n);
}

signed main(){
        llin(a);
        llin(b);
        llin(c);
        llin(d);
        ll e=(c/solve(c,d))*d;
        sal((b-a+1)-b/c+(a-1)/c-b/d+(a-1)/d+b/e-(a-1)/e);
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;

typedef long long ll;
const int mod=1e9+7;

int main(){
	int n;
	cin >> n;
	vector<pair<int, int> > s(n);
	ll sum=0;
	for(int i=0; i<n; i++){
		cin >> s[i].first >> s[i].second;
		sum += s[i].first;
	}
	sort(s.begin(), s.end(), [](pair<int, int> x, 
	pair<int, int> y){
		return x.second<y.second;
	});
	for(int i=n-1; i>=0; i--){
		if(s[i].second<sum){
			cout << "No" << endl;
			return 0;
		}else{
			sum -= s[i].first;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pip;
const ll INF = 1e9+100;
const ll INFL = 1e18+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int N, M;
ll x[1000], y[1000], z[1000];

int main() {
	cin >> N >> M;
	REP(i, N) scanf("%lld %lld %lld", x + i, y + i, z + i);
	
	ll ans = 0;
	REP(i, 1<<3) {
		vector<ll> v;
		
		REP(j, N) {
			ll cur = 0;
			cur += (((i >> 0) & 1) ? -1 : 1) * x[j];
			cur += (((i >> 1) & 1) ? -1 : 1) * y[j];
			cur += (((i >> 2) & 1) ? -1 : 1) * z[j];
			
			v.push_back(cur);
		}
		sort(ALL(v), greater<ll>());
		
		ll sum = 0;
		REP(j, M) sum += v[j];
		chmax(ans, sum);
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#include<climits>
#include<set>
#define ll long long
using namespace std;
int main() {
	ll n,z=0;
	cin >> n;
	vector<ll>a(n),sum(n,0);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
		z += a[i];
		sum[i] = z;
	}
	ll sma = LLONG_MAX;
	ll smai;
	for (ll i = 0; i < n;i++) {
		ll o = sma;
		sma = min(sma, abs(sum[n - 1] - 2*sum[i]));
		if (sma != o) {
			smai = i;
		}
	}
	cout << sma << endl;

}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x,2.0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define max_queue(x) priority_queue<x>
#define min_queue(x) priority_queue<x, vector<x>, greater<x>>
#define big_sort(v) sort(all(v), [](int a, int b) { return a > b; })//大きい順にソート
using ll = long long;
using vi = vector<ll>;
using vvi = vector<vi>;
using vs = vector<string>;
using vd = vector<long double>;
#define co(x) cout << x << endl;
#define cins(n,v) rep(i,n){cin >> v.at(i);}
#define couts(v) rep(i,v.size()){cout << v.at(i) << endl;}
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
*/
int main() {
  int n,x,t;
  cin >> n>>x>>t;
  if(n%x==0){co(n/x*t);} else co((n/x+1)*t);
  return 0;
}


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

using i64 = int_fast64_t;
using f64 = double;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    i64 n;
    cin >> n;
    
    i64 ans = 0;
    i64 l = 0, r = 0, lr = 0;
    for (i64 i = 0; i < n; i++) {
        string s;
        cin >> s;

        if (s.front() == 'B' && s.back() == 'A') lr++;
        else if (s.front() == 'B') l++;
        else if (s.back() == 'A') r++;

        for (i64 j = 0; j + 1 < (i64) s.size(); j++) {
            if (s[j] == 'A' && s[j + 1] == 'B') ans++;
        }
    }

    if (lr > 0) {
        ans += lr - 1;
        if (l > 0) ans++, l--;
        if (r > 0) ans++, r--;
    }
    ans += min(l, r);
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 256
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <algorithm>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
#include <bitset>
#include <functional>
#include <numeric>
#include <ctime>
#include <cassert>
#include <cstring>
#include <fstream>

#define FOR(i, a, b) for(int (i)=(a); (i)<(b); (i)++)
#define IFOR(i, a, b) for(int (i)=(a);(i)<=(b);(i)++)
#define RFOR(i, a, b) for(int (i)=(a);(i)>=(b);(i)--)

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    FOR(i, 0, n) {
        cin >> a[i];
    }
    vector<long long> b(a);
    sort(b.begin(), b.end());
    vector<long long> accum(n);
    partial_sum(b.begin(), b.end(), accum.begin());

    int cnt = 0;
    FOR(i, 0, n) {
        long long t = a[i];
        long long req = 2 * t;
        bool ok = false;
        auto lb = b.begin();
        while (1) {
            if (lb == b.end()) {
                ok = true;
                break;
            }

            auto ub = upper_bound(lb, b.end(), req);
            if (lb == ub)
                break;

            int idx = distance(b.begin(), ub);
            idx--;
            t = accum[idx];
            req = 2 * t;
            lb = ub;
        }
        if (ok)
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 3e5+5,mod = 1e9+7;
int n,ans,cnt[61][2];
ll val[MAXN];
it add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
it mul(int x,int y){return 1ll*x*y%mod;}
il Updata(ll val){
	for(ri i=0;i<60;++i){
		int k=val>>i&1ll;
		int bas=(1ll<<i)%mod;
		ans=add(ans,mul(bas,cnt[i][k^1]));
		++cnt[i][k];
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n);
	for(ri i=1;i<=n;++i) read(val[i]);
	for(ri i=1;i<=n;++i) Updata(val[i]);
	print(ans);
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int sm[100005]; int n,m;
int main(){
    memset(sm,0,sizeof(sm));

    cin >> n >> m;
    int mx = 0;
    for(int i =0 ; i < m; i++){
        int f,t;
        cin >> f >> t;
        sm[f]++;
        sm[t]++;
        mx = max(mx, sm[f]);
        mx = max(mx, sm[t]);
    }
    for(int i = 0; i <= 100003; i++)
    {
        if(sm[i] != 0 && sm[i]%2 == 1){
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";


    return 0;
}


Measured memory_bytes: 640
//Two Anagrams

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define irep(i,a) for(auto i = a.begin(); i != a.end(); ++i)
#define nvarep(n,a) int n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
#define cout15(a) printf("%.15f\n",a)
template<class T>inline bool chmin(T& a,T b,bool f){
if(f==1){if(a>b){a=b;return true;}return false;}
else if(f==0){if(a<b){a=b;return true;}return false;}return false;}
typedef pair<ll,string> p;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

int main (){
    string s,t;
    cin>>s>>t;
    sort(range(s));
    sort(range(t),greater<int>());
    rep(i,0,min(s.size(),t.size())){
        if(s[i]==t[i])continue;
        else if(s[i]<t[i]){cout<<"Yes"<<nnn;return 0;}
        else if(s[i]>t[i]){cout<<"No"<<nnn;return 0;}
    }
    if(s.size()<t.size())cout<<"Yes"<<nnn;
    else cout<<"No"<<nnn;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<string>
//#include<string>
//#include<sstream>
using namespace std;
int main()
{
	int n;
	char a[200];
	scanf("%d",&n);
	scanf("%s",&a);
	int sum=0,max=0;
	for(int i=0;i<n;i++){
		if(a[i]=='I'){
			sum++;
			if(max<sum) max=sum;
		}
		else sum--;
	}
	printf("%d\n",max);
}

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



signed main(){
    int N;
    int A[214514];
    int B[214514]={};
    int Ans=0;
    int num;
    cin >> N;
    REP(i,N){
        cin >> A[i];
        B[i+1]=B[i]+A[i];
    }
    sort(B,B+N+1);
    /*REP(i,N+1){
        cout << B[i] << " ";
    }*/
    num=1;
    REP(i,N){
        if(B[i]==B[i+1]){
            num++;
        }else{
            //cout << B[i] << " " << (num * (num-1) / 2) << endl;
            Ans+=(num * (num-1) / 2);
            num=1;
        }
        if(i==N-1){
           // cout << B[i] << " " << (num * (num-1) / 2) << endl;
            Ans+=(num * (num-1) / 2);
            
        }
    }
    cout << Ans << endl;
    return 0;
}



Measured memory_bytes: 3584
import collections
N=int(input())
blue=[input() for i in range(N)]

b=collections.Counter(blue)

M=int(input())
for i in range(M):
    a=input()
    if a in b:
        b[a]-=1

ans=max(b.values())


if(ans<0):
    ans=0

print(ans)


Measured memory_bytes: 3316
n = int(input())

s=[]
res = 0
tmp = 0
eA=0
sB=0
eAsB=0
for i in range(n):
	s.append(input())
	tmp = s[i].count("AB")
	if tmp != 0:
		res += tmp
	if s[i][0]=="B" and s[i][-1]=="A":
		eAsB += 1
	elif s[i][-1]=="A":
		eA += 1
	elif s[i][0]=="B":
		sB += 1

if eAsB != 0:
	if eA < sB:
		res += eA+1
	elif eA == 0 and sB == 0:
		res += 0
	else:
		res += sB+1
else:
	if eA < sB:
		res += eA
	else:
		res += sB

if eAsB > 1:	
	res += eAsB-1

print(res)

Measured memory_bytes: 3700
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <numeric>
using namespace std;
typedef long long int ll;

struct UnionFind{
    vector<int> par,num;
    vector<bool> done;
    UnionFind(int n):par(n),num(n,1),done(n,false){
    	iota(par.begin(),par.end(),0);
    }
    int find(int v){
        return (par[v]==v)?v:(par[v]=find(par[v]));
    }
    void unite(int u,int v){
        u=find(u),v=find(v);
        if(u==v)return;
        if(num[u]<num[v])swap(u,v);
        num[u]+=num[v];
        par[v]=u;
        done[u]=done[u]|done[v];
    }
    bool same(int u,int v){
        return find(u) == find(v);
    }
    bool ispar(int v){
        return v=find(v);
    }
    int size(int v){
        return num[find(v)];
    }
};

int main(){
	int n,k,l; cin >> n >> k >> l;
	UnionFind uf(n),uf1(n);
	for(int i=0;i<k;i++){
		int p,q; cin >> p >> q;
		p--; q--;
		uf.unite(p,q);
	}
	for(int i=0;i<l;i++){
		int r,s; cin >> r >> s;
		r--; s--;
		uf1.unite(r,s);
	}
	vector<pair<int,int> > v;
	map<pair<int,int> ,int> mp;

	for(int i=0;i<n;i++){
		v.push_back(make_pair(uf.find(i),uf1.find(i)));
	}
	sort(v.begin(),v.end());
	int cnt=1;
	for(int i=0;i<v.size()-1;i++){
		if(v[i]==v[i+1])cnt++;
		else{
			mp[v[i]]=cnt;
			cnt=1;
		}
	}
	mp[v[v.size()-1]]=cnt;
	for(int i=0;i<n;i++){
		cout << mp[pair<int,int>(uf.find(i),uf1.find(i))] <<  " ";
	}
	cout << endl;
}


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

using namespace std;
typedef long long ll;

const ll MOD = 1e9 + 7;

vector<ll> fact;

void init_fact(int n) {
    fact = vector<ll>(n);
    fact[0] = 1;
    for (int i = 1; i < n; i++) fact[i] = fact[i - 1] * i % MOD;
}

ll calc_pow(ll x, ll pow) {
    if (pow == 0) return 1;
    ll a = calc_pow(x, pow / 2);
    a = a * a % MOD;
    if (pow % 2 == 1) a *= x;
    return a % MOD;
}

ll calc_div(ll a, ll b) {
    return a * calc_pow(b, MOD - 2) % MOD;
}

ll calc_comb(ll n, ll r) {
    if (n < r)return 0;
    return calc_div(fact[n], fact[r] * fact[n - r] % MOD);
}

int main() {
    init_fact(200000);

    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    sort(a.begin(), a.end());

    ll ret = 0;
    for (int i = 1; i < n; i++) {
        ll now = calc_comb(n, k);
        now -= calc_comb(i, k), now += MOD, now %= MOD;
        now -= calc_comb(n - i, k), now += MOD, now %= MOD;
        ret += now * (a[i] - a[i - 1]), ret %= MOD;
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 2176
#17:30
n,m = map(int,input().split())
import heapq
h = list(map(lambda x:-int(x),input().split()))
heapq.heapify(h)
for _ in range(m):
  now = heapq.heappop(h)
  heapq.heappush(h,-((-now)//2))
print(-sum(h))

Measured memory_bytes: 14380
import sys, heapq


def main():
    
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    value = [-int(inp) for inp in input().split()]

    heapq.heapify(value)

    for _ in range(M):
        new_elem = -(- heapq.heappop(value) // 2)
        heapq.heappush(value, new_elem)

    print(- sum(value))
    
if __name__=="__main__":
    main()

Measured memory_bytes: 14200
S = input()
pre_weather = "S"

cnt = 0
ans = 0
for i in range(3):
    if pre_weather == "R" and S[i] == "R":
        cnt += 1
    elif S[i] == "R":
        cnt = 1
    pre_weather = S[i]
    
    ans = max(cnt,ans)

print(ans)
    
    

    


Measured memory_bytes: 61808
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N=0, count=0;
  vector<int> d(101);
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> d.at(i);
  }
  sort(d.rbegin(),d.rend());
  for(int i=0;i<N;i++){
    if(d.at(i) > 0){
      count++;
      for(int j=i+1;j<N;j++){
        if(d.at(i) == d.at(j)){
          d.at(j)=-1;
        }
      }//for j
    }
  }
  cout << count << endl;
}

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

using namespace std;
using llong = int;
using ldbl = long double;
using P = pair<llong, llong>;
using PP = pair<P, P>;

#define BE(x) x.begin(), x.end()

// const llong inf = llong(1e18)+7;
// const llong mod = 1e9+7;

namespace std{
	template<>
	struct hash<P>{
		size_t operator()(const P &x) const{
			return hash<llong>()(x.first) ^ (hash<llong>()(x.second<<1));
		}
	};

	template<>
	struct hash<PP>{
		size_t operator()(const PP &x) const{
			return hash<P>()(x.first) ^ (hash<P>()(x.second));
		}
	};
}

int main(){
	llong N, K;
	vector<P> p;

	cin >> N >> K;
	p.resize(N);
	for(int i = 0; i < N; i++)
		cin >> p[i].first >> p[i].second;

	vector<PP> vec;
	for(int i = 0; i < N; i++){
		for(int j = i+1; j < N; j++){
			P a = p[i], b = p[j];
			P m,z;
			// ax == bx : mはinf zはyの位置
			if(a.first == b.first){
				m =  P(1,0);
				z = P(a.first,1);
			}
			// ay == by : mは0 y軸と直行する
			else if(a.second == b.second){
				m = P(0,1);
				z = P(a.second,1);
			}else{
				m = P(a.second - b.second, a.first - b.first);
				if(m.second < 0)
					m.first *= -1, m.second *= -1;
				short cmf = m.first, cms = m.second;
				short gcdM = __gcd((cmf>0?cmf:-cmf), (cms>0?cms:-cms));
				m.first /= gcdM, m.second /= gcdM;

				z = P(a.second*m.second - a.first*m.first, m.second);
				if(z.second < 0)
					z.first *= -1, z.second *= -1;
				short zmf = z.first, zms = z.second;
				short gcdZ = __gcd((zmf>0?zmf:-zmf), (zms>0?zms:-zms));
				z.first /= gcdZ, z.second /= gcdZ;
			}

			// PP in(m,z);
			// mp[in]++;
			vec.push_back(PP(m,z));
		}
	}

	bool check = false;
	sort(BE(vec));
	for(auto it = vec.begin(); it != vec.end(); it = upper_bound(BE(vec), *it)){
		llong n = upper_bound(BE(vec),*it) - it;
		if(1+sqrt(1+n*8)/2 >= K)
			check = true;
	}
	// for(auto it : mp){
	// 	P m = it.first.first;
	// 	P z = it.first.second;
	// 	llong n = (1+sqrt(1+it.second*8))/2.0;
	// 	// cerr << m.first << " " << m.second << " " << z.first << " " << z.second << " : " << it.second << " " << n << endl;
	// 	if(n >= K)
	// 		check = true;
	// }

	cout << check << endl;

	return 0;
}


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

using namespace std;
string s,t;
int f[3001][3001];
int main()
{

    cin >> s >> t;
   int n=s.size();
   int m=t.size();
   for(int i=0;i<=n;i++)
   {
       for(int j=0;j<=m;j++)
       {
           if(i==0 || j==0)f[i][j]=0;
          else if(s[i-1]==t[j-1])
           {
               f[i][j]=f[i-1][j-1]+1;
           }
           else
           {
               f[i][j]=max(f[i-1][j],f[i][j-1]);
           }
       }
   }
   int r1=n;
   int r2=m;
   string rez;
   while(r1>0 && r2>0)
   {
       if(s[r1-1]==t[r2-1])
       {
           rez.push_back(s[r1-1]);
           r1--;
           r2--;
       }
       else
       {
           if(f[r1-1][r2]>f[r1][r2-1])
           {
               r1--;
           }
           else
           {
               r2--;
           }
       }
   }
   reverse(rez.begin(),rez.end());
   cout << rez;
    return 0;
}


Measured memory_bytes: 35456
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,k;
    cin >> n >> k;
    bool b[10] = {};
    for (int i = 0; i < k; ++i) {
        int a;
        cin >> a;
        b[a] = 1;
    }
    while (1) {
        int x = n;
        bool ok = 1;
        for (;x && ok;x/=10)
            ok = !b[x%10];
        if (ok)
            break;
        ++n;
    }
    cout << n << '\n';
}


Measured memory_bytes: 256
use std::cmp;
use std::collections::HashMap;
use std::collections::VecDeque;
use std::io::Read;
use std::usize::MAX;

macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, [ $t:tt ]) => {{let len = read_value!($next, usize);(0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()}};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

fn solve() {
    input! {
        n: usize,
        a: [usize;n]
    }

    let mut sorted_a = a.clone();
    sorted_a.sort();

    let mut map: HashMap<usize, usize> = HashMap::new();
    for i in 0..n {
        let v = map.entry(sorted_a[i]).or_insert(0);
        *v += 1;
    }

    //println!("{:?}", map);

    let mut sum = 0;
    for (v, &count) in &map {
        sum += (count * (count - 1)) / 2;
    }

    for i in 0..n {
        let count = map.get(&a[i]).unwrap();
        let edit_sum = if count > &1 {
            sum - (count * (count - 1)) / 2 + ((count - 1) * (count - 2)) / 2
        } else {
            sum
        };
        println!("{}", edit_sum);
    }

    let mut ans = 0;
}

fn main() {
    let thd = std::thread::Builder::new().stack_size(104_857_600);
    thd.spawn(|| solve()).unwrap().join().unwrap();

    /*
    // 入力を一括で読み込む場合
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut input = buf.split_whitespace();

    // inputに対しnext()で読み込んでいく
    let q: usize = input.next().unwrap().parse().unwrap();
    */
}

const LARGE_PRIME: u64 = 1_000_000_007;

// @〜でsnippet


Measured memory_bytes: 21460
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

void run(void){
  int n,m;
  scanf("%d%d",&n,&m);
  if(n<m){
    int t=m;
    m=n;
    n=t;
  }
  if(n-m>1){
    printf("0\n");
    return;
  }
  const int mod=1000000007;
  int f=1;
  int i;
  for(i=1;i<=n;i++) f=(int64)f*i%mod;
  for(i=1;i<=m;i++) f=(int64)f*i%mod;
  if(n==m) f=2*f%mod;
  printf("%d\n",f);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
from collections import deque
limit = 3234566667
K = int(input())
ans = []

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
q.append(5)
q.append(6)
q.append(7)
q.append(8)
q.append(9)

# 10倍して足す
ans = []
while len(q):
    num = q.popleft()
    ans.append(num)
    last_num = str(num)[-1]
    if last_num == "9":
        next_num = num * 10 + 8
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + 9
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
    elif last_num == "0":
        next_num = num * 10
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
    else:
        next_num = num * 10 + int(last_num)
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + int(last_num) + 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
        next_num = num * 10 + int(last_num) - 1
        if next_num <= limit:
            ans.append(next_num)
            q.append(next_num)
ans = list(set(ans))
ans.sort()
print(ans[K-1])


Measured memory_bytes: 14904
#include<bits/stdc++.h>
#define li unsigned long long
#define ll long long
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
const ll M = 1e9 + 7;
using namespace std; 
int main() 
{
	FAST
	ll n,k;
	cin>>n>>k;
	ll a[n];
	for(ll i=0;i<n;i++) cin>>a[i];
	ll dp[n];
	dp[0]=0;
	dp[1]=abs(a[0]-a[1]);
	for(ll i=2;i<n;i++)
	{
      	ll temp;
      	if(i<k) temp=i;
      	else temp=k;
      	dp[i]=dp[i-1]+abs(a[i]-a[i-1]);
		for(ll j=1;j<=temp;j++)
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
	}
	cout<<dp[n-1];
	return 0;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <algorithm>
#include <utility>

template<typename T, size_t MAX_N>
class BIT
{
	public:
		BIT(size_t n) : _bit(), _n(n) {}

		T sum(size_t i)
		{
			T r = 0;
			while (i > 0)
			{
				r += _bit[i];
				i &= (i - 1);
			}
			return r;
		}

		void add(size_t i, T x)
		{
			while (i <= _n)
			{
				_bit[i] += x;
				i += i & -i;
			}
		}

	protected:
		T _bit[MAX_N + 1];
		size_t _n;
};

int main()
{
	int n;
	long long d, a;
	scanf("%d%lld%lld", &n, &d, &a);
	using pair = std::pair<long long, long long>;
	pair enemy[200000];
	for (int i = 0; i < n; ++i)
	{
		long long x, h;
		scanf("%lld%lld", &x, &h);
		enemy[i].first = x;
		enemy[i].second = h;
	}
	std::sort(enemy, enemy + n);
	BIT<long long, 200000> bit(n);
	long long ans = 0;
	for (int i = 0; i < n; ++i)
	{
		long long left = enemy[i].second - bit.sum(i + 1);
		if (left <= 0) continue;
		long long l = enemy[i].first;
		long long r = l + 2 * d;
		int ub = std::upper_bound(enemy, enemy + n, pair{r, 0}, [](auto& a, auto& b){ return a.first < b.first; }) - enemy;
		long long times = (left + a - 1) / a;
		ans += times;
		long long bomb = times * a;
		bit.add(i + 1, bomb);
		bit.add(ub + 1, -bomb);
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD 1000000007
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ull t;cin>>t;while(t--)
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i]
#define ov(a) for(ll i=0;i<a.size();i++)cout<<a[i]<<" ";nl
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main()
{
	fastio();
	ll N;
	cin>>N;
	dd ar[N];
	cn(ar,N);
	dd ans[N+1][N+1];
	for(ll i=0;i<=N;i++)
	{
		for(ll j=0;j<=N;j++)
		{
			ans[i][j]=0.0;
		}
	}
	ans[0][0]=1.0;
	for(ll i=1;i<=N;i++)
	{
		ans[i][0]=ans[i-1][0]*(1-ar[i-1]);
	}
	ans[1][1]=ar[0];
	for(ll i=2;i<=N;i++)
	{
		for(ll j=1;j<i;j++)
		{
			ans[i][j]=(ans[i-1][j-1]*ar[i-1]+ans[i-1][j]*(1-ar[i-1]));
		}
		ans[i][i]=ans[i-1][i-1]*ar[i-1];
	}
	dd sum=0.0;
	for(ll i=N/2+1;i<=N;i++)
		sum+=ans[N][i];
	cout<<fixed<<showpoint;
	cout<<setprecision(12);
	cout<<sum<<endl;
}	


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

template <typename T, typename P = less<>> struct slide {
    deque<T> q;
    P p;
    int size() const { return q.size(); }
    void push(T &&x) {
        while(!q.empty() && !p(q.back(), x))
            q.pop_back();
        q.push_back(x);
    }
    template <typename... U> void push(U &&... x) { push(T(x...)); }
    const T &top() const { return q.front(); }
    void pop() { q.pop_front(); }
};
pair<int, int> a[111111];
int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    slide<pair<int, int>> l;
    l.push(0, n);
    for(int i = n; i--;) {
        if(!l.size()) {
            cout << -1 << endl;
            return 0;
        }
        if(s[i] == '0') {
            a[i] = l.top();
            a[i].first++;
            l.push(a[i].first, i);
        }
        if(l.top().second == i + m)
            l.pop();
    }
    int i = 0;
    while(i < n) {
        cout << a[i].second - i << ' ';
        i = a[i].second;
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 1536
#include<iostream>
using namespace std;
#define MAX 100001
int red[MAX];
int sum[MAX];
int main()
{
    int n, m, a, b, count = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        red[i] = 0;
        sum[i] = 1;
    }
    red[1] = 1;
    while(m--)
    {
        cin >> a >> b;
        sum[a]--;
        sum[b]++;
        if(red[a] == 1)
        {
            if(sum[a] == 0)
                red[a] = 0;
            red[b] = 1;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(red[i] == 1)
            count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 1024