akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#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 all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const int DIV = 1e9+7;

int n, m, x;
vi a;

int main()
{
    cin >> n >> m >> x;
    a.resize(m); rep(i, m) cin >> a[i];

    int left = 0, right = 0;
    rep(i, m){
        if(a[i] < x) left++;
        else right++;
    }
    int ans = min(left, right);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun <T> Iterable<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)
fun <T> Array<T>.join(separator: CharSequence = ", ", prefix: CharSequence = "", postfix: CharSequence = "") = joinToString(separator, prefix, postfix)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val S = next()
    var ans = 0
    for (i in 1 until S.length) {
        if (S[i - 1] != S[i]) ans++
    }
    println(ans)
}

Measured memory_bytes: 34204
import math

#n,a,b
n,a,b=(int(x) for x in input().split())

allcount = math.floor(n/(a+b))
if a < n - allcount * (a+b):
    nokori = a
else:
    nokori = n - allcount * (a+b)
ans = allcount * a + nokori
print(ans)

"""
ans = 0
count = 0
while(n>0 and count<=10000):
    n -= a
    if n >= 0:
        ans += a
    else:
        ans += a + n
    n -= b
    count += 1
print(ans)
"""


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

namespace Atcoder
{
    public class Program
    {
        private static long mod = 1000000007;

        static void Main(string[] args)
        {
            var r = ReadSplit();
            var n = r[0].Int();
            var m = r[1].Int();
            var l = new Tuple<int, int, int>[m];
            for (int i = 0; i < m; i++)
            {
                var r2 = ReadSplit();
                var p = r2[0].Int();
                var y = r2[1].Int();
                l[i] = new Tuple<int, int, int>(p, y, i);
            }
            var tmpL = l.OrderBy(x => x.Item1).ThenBy(x => x.Item2).ToList();
            var ans = new string[m];
            int j = 1;
            var pre = tmpL[0].Item1;
            foreach (var item in tmpL)
            {
                if (pre != item.Item1)
                {
                    pre = item.Item1;
                    j = 1;
                }
                ans[item.Item3] = item.Item1.ToString().PadLeft(6, '0') + j.ToString().PadLeft(6, '0');
                j++;
            }

            for (int i = 0; i < m; i++)
            {
                Write(ans[i]);
            }
            Read();
        }

        public static string Read()
        {
            return Console.ReadLine();
        }

        public static string[] ReadSplit()
        {
            return Console.ReadLine().Split(' ');
        }

        public static void WriteRead(object str)
        {
            Console.WriteLine(str);
            Read();
        }

        public static void Write(object str)
        {
            Console.WriteLine(str);
        }

        private static bool ChangeMin<T>(ref T a, T b) where T : IComparable
        {
            if (a.CompareTo(b) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }

        private static bool ChangekMax<T>(ref T a, T b) where T : IComparable
        {
            if (b.CompareTo(a) > 0)
            {
                a = b;
                return true;
            }
            return false;
        }
    }
}


public static class Extentions
{
    public static int Int(this object obj)
    {
        return int.Parse(obj.ToString());
    }

    public static long Long(this object obj)
    {
        return long.Parse(obj.ToString());
    }

    public static decimal Decimal(this object obj)
    {
        return decimal.Parse(obj.ToString());
    }

    public static double Double(this object obj)
    {
        return double.Parse(obj.ToString());
    }

    public static T2 GetValueZero<T1, T2>(this Dictionary<T1, T2> d, T1 key) where T2 : struct
    {
        T2 value;
        if (d.TryGetValue(key, out value))
        {
            return value;
        }
        return new T2();
    }
}



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

const int MAXN = 1234567;

char s[MAXN];
int f[MAXN];
int nxt[MAXN],prv[MAXN];

int main()
{
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    memset(f,0,sizeof(f));
    nxt[n] = n;
    //记录以当前位置开始，向后数，第一个0的位置
    for(int i = n-1; i >= 0; --i)
    {
        if(s[i] == '0')
            nxt[i] = i;
        else
            nxt[i] = nxt[i+1];
    }
    //记录以当前位置开始，向前数，第一个0的位置
    for(int i = 0; i < n; ++i)
    {
        if(s[i] == '0')
            prv[i] = i;
        else
            prv[i] = (i==0?-1:prv[i-1]);
    }

    for(int i = 0; i  <= n; ++i)
    {
        if(i >= 3 && s[i-1] == '1' && s[i-2] == '0' && s[i-3] == '1')
        {
            int j = prv[i-3];
            f[i] = max(f[i],f[j+1]+(i-j-3));
            if(j != i-4)
                f[i] = max(f[i],f[j+2]+(i-j-4));
        }
        if(i == n)
            break;
        if(i+3 <= n && s[i] == '1' && s[i+1] == '0' && s[i+2] == '1')
        {
            int j = nxt[i+2];
            f[j] = max(f[j],f[i]+(j-i-2));
            if(j != i+3)
                f[j-1] = max(f[j-1],f[i]+(j-i-3));
        }
        f[i+1] = max(f[i+1],f[i]);
    }
    printf("%d\n",f[n]);
    return 0;
}


Measured memory_bytes: 13184
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
//a=0x61=97
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
typedef long double  ld;
typedef string str;
typedef pair<int,int> pairii;
typedef vector<int> veci;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(2)
int main() {
  ll n,flag;
  ll ans=1;
  cin>>n;
  ll x[n];
  rep(i,n){cin>>x[i];if(x[i]==0){cout<<0;return 0;}}
  rep(j,n){
    if(ans>1000000000000000000/x[j]){{cout<<-1;return 0;}}
    else ans*=x[j];
    if(ans>1000000000000000000){{cout<<-1;return 0;}}
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4408
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <map>
#include <iomanip>
using namespace std;

int main(){
    int num, people;
    cin >> num >> people;
    if(people==1){
        cout << "0" << endl;
    }else{
        cout << num-people<< endl;
    }

    return 0;
}


Measured memory_bytes: 888
#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(a)     (a).begin(),(a).end()
#define VI         vector<int>
#define MOD 1000000007

typedef long long int ll;

const ll INF=(ll)1e19;
//const int INF=(1<<30);


int main(){
  int n;
  cin >> n;
  map<int, int> mp;
  REP(i,n-1){
    int a;
    cin >> a;
    mp[a]++;
  }

  FOR(i,1,n+1){
    cout << mp[i]<< endl;
  }
}



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

int main(){
  int N;
  cin >> N;
  int a[N];
  rep(i, N)
    cin >> a[i];
  //ここまで入力 

  //a[i]の平均までの距離の和が最適になる
  
  //平均値を求めるために和を計算
  int sum = 0;
  rep(i, N)
    sum += a[i];
  
  //平均値を計算し，四捨五入
  double ave = (double)sum/N;
  ave = floor(ave+0.5);

  //コストの計算
  int ans = 0;
  rep(i, N)
    ans += (a[i]-ave)*(a[i]-ave);

  //解答
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;




int main()
{

    int N;
    ll L;
    cin >> N >> L;
    vl a(N);
    in(N,a);
    
    int b = -1;
    rep(i,N-1){
        if(a[i]+a[i+1] >= L){
            b = i+1;
            break;
        }
    }
    
    if(b == -1){
        cout << "Impossible" << endl;
        return 0;
    }
    
    cout << "Possible" << endl;
    reps(i,1,b) cout << i << endl;
    for (int i = N-1; i > b; i--) cout << i << endl;
    cout << b << endl;
    
    
    

    return 0;
}


Measured memory_bytes: 1664
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	public static void main (String[] args) throws java.lang.Exception {
		new Solution();
	}
}
class Solution {
	Scanner scanner;
	public Solution() {
		scanner = new Scanner(System.in);

		// scanner.nextLine();
		while (scanner.hasNext()) {
			run_case();
		}
	}
	private void run_case() {
		// scanner.nextLine();
		String line = scanner.nextLine();

		int H = Integer.parseInt(line.split("\\s+")[0]);
		int K = Integer.parseInt(line.split("\\s+")[1]);

		int[] arr = strToIntArray(scanner.nextLine());
		Arrays.sort(arr);

		int sz = arr.length;
		long res = 0;
		for (int i=0; i<sz-K; i++) {
			// System.out.println(arr[i]);
			res += arr[i];
		}

		System.out.println(res);
		return;
	}

	private int[] strToIntArray(String str) {
	    String[] vals = str.split("\\s+");
	    int sz = vals.length;
	    int[] res = new int[sz];
	    for (int i=0; i<sz; i++) {
	        res[i] = Integer.parseInt(vals[i]);
	    }
	    return res;
	}
}

// class Num implements Comparable<Num>{
// 	public int val;
//
// }


Measured memory_bytes: 76964
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <cmath>

using namespace std;
#define inputInt(a) int a;cin >> a; 
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define output(answer) cout << answer << endl;
#define f(i,s,e) for(int i=s; i<=e; i++)

int main()
{
    //input
    inputInt(W);inputInt(H);inputInt(x);inputInt(y);
  
    //main
    double ans = (double)W*H/2;

    // 出力
    output(ans);
    char ans2 = ((double)x == (double)W/2 && (double)y == (double)H/2) ? '1':'0';
    output(ans2);
    return 0;
}

Measured memory_bytes: 256
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:k,l,r=map(int,i().split());x+=[(k,l,r)]*(l>r);y+=[(n-k,r,l)]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

Measured memory_bytes: 39924
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int max = 0, min = 100;
        int x[] = new int[n];
        for (int i=0; i < n;i ++) {
            x[i] = scan.nextInt();
            if (x[i] > max) {
                max = x[i];
            }

            if (x[i] < min) {
                min = x[i];
            }
        }

        int minTotal = 99999999;
        for (int i = min; i <= max; i++) {
            int total = 0;
            for (int k = 0; k < n; k++) {
                total += Math.pow((x[k] - i), 2);
            }

            if (total < minTotal) {
                minTotal = total;
            }
        }
        System.out.println(minTotal);
    }
}

Measured memory_bytes: 23764
#include<bits/stdc++.h>
#define lli long long int

using namespace std;

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

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    lli a=0, b=0, c=0, k=0, count = 0;
    cin >> a >> b >> c >> k; 

    while(k != 0)
    {
        if(a == k)
        {
            count = a;
            break;        
        }
        if(a != 0)
        {
            count++;
            a--;
        } else if(b!=0)
        {
            b--;
        }
        else
        {
            count--;
            c--;
        }
        k--;
    }
    cout << count;
    
}

Measured memory_bytes: 3656
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int i = 1;
		int x;
		do {
			x = i;
			if (x % 3 == 0) {
				System.out.print(" " + i);
				continue;
			}
			while (true) {
				if (x % 10 == 3) {
					System.out.print(" " + i);
					break;
				}
				x /= 10;
				if (x != 0)
					continue;
				else
					break;
			}
		} while (i++ < n);
		System.out.println();
	}
}

Measured memory_bytes: 28768
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
 
struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is,pair<T1,T2>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}


signed main(){
    int n,m;cin>>n>>m;
    vector<vector<int>> g(n);
    rep(i,m){
        int u,v;cin>>u>>v;u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int cntsolo=0;
    vector<int> bi,notbi;

    vector<int> check(n,-1);
    bool bipf=true;
    int cnt=0;

    function<void(int)> dfs=[&](int now){
        cnt++;
        for(auto to:g[now]){
            if(check[to]==-1){
                check[to]=(check[now]^1);
                dfs(to);
            }else{
                if(check[now]==check[to]) bipf=false;
            }
        }
    };

    rep(i,n)if(check[i]==-1){
        if(g[i].size()==0){
            cntsolo++;
            continue;
        }

        bipf=true;
        cnt=0;
        check[i]=0;
        dfs(i);
        if(bipf)    bi.push_back(cnt);
        else        notbi.push_back(cnt);
    }

    
    ll res=0;
    res+=(ll)cntsolo*cntsolo;
    res+=(ll)2*cntsolo*(n-cntsolo);

    ll cbi=(ll)bi.size();
    ll cnb=(ll)notbi.size();

    res+=2*cbi*cbi;
    res+=cnb*cnb;

    res+=2*cbi*cnb;

    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 13672
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, x, y, z, f[100010], ans;
bool vis[100010];
inline int anc(int x){
    if(x == f[x]) return x;
    return f[x] = anc(f[x]);
}//路径压缩并查集
inline void Union(int x, int y){
    int fx = anc(x), fy = anc(y);
    if(fx != fy) f[fx] = fy;
    return;
}//合并
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) f[i] = i;
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d", &x, &y, &z);
        Union(x, y);
    }
    for(int i = 1; i <= n; ++i){
        if(!vis[anc(i)]){
            vis[f[i]] = 1;
            ans++;
        }
    }//统计数量
    printf("%d\n", ans);//输出，记得 AT 题要换行
    return 0;
}

Measured memory_bytes: 896
import sys
input = sys.stdin.readline
s, t, q = list(input()), list(input()), int(input())
ssum, tsum = [0], [0]
for i in range(len(s)):
    if s[i]=="A": ssum.append(ssum[-1]+1)
    else: ssum.append(ssum[-1]+2)
for i in range(len(t)):
    if t[i]=="A": tsum.append(tsum[-1]+1)
    else: tsum.append(tsum[-1]+2)
for i in range(q):
    a,b,c,d = map(int,input().split())
    sa = (ssum[b]-ssum[a-1])-(tsum[d]-tsum[c-1])
    if abs(sa)%3==0:print("YES")
    else: print("NO")

Measured memory_bytes: 13464
import java.util.*;
public class Main{
    int arr[][];
    int n;
    private void enter()
    {
        //System.out.print("Enter the size: ");
        Scanner sc=new Scanner(System.in);
        arr=new int[n=sc.nextInt()][3];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<3;j++)
                arr[i][j]=sc.nextInt();
        }
    }
    private void solve()
    {
        enter();
        for(int i=n-2;i>=0;i--)
        {
            arr[i][0]+=arr[i+1][1]>arr[i+1][2]?arr[i+1][1]:arr[i+1][2];
            arr[i][1]+=arr[i+1][0]>arr[i+1][2]?arr[i+1][0]:arr[i+1][2];
            arr[i][2]+=arr[i+1][1]>arr[i+1][0]?arr[i+1][1]:arr[i+1][0];
        }
    }
    private void finans()
    {
        solve();
        System.out.println(arr[0][0]>arr[0][1]?arr[0][0]>arr[0][2]?arr[0][0]:arr[0][2]:arr[0][1]>arr[0][2]?arr[0][1]:arr[0][2]);
    }
    public static void main(String args[]) {
      Main ob=new Main();
      ob.finans();
    }
}

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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vl = V<ll>;
using VVl = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pll = P<ll, ll>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

const double PI = acos(-1);
const ll MOD = 1e9+7;

string s;
int q;

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

    deque<char> dq;
    for (auto c: s) {
        dq.push_back(c);
    }

    bool f = true;
    REP(i, q) {
        int t; cin >> t;
        if (t == 1) {
            f = !f;
        } else {
            int x; char c; cin >> x >> c;
            if ((x == 1 && f) || (x == 2 && !f)) {
                dq.push_front(c);
            } else {
                dq.push_back(c);
            }
        }
    }

    if (f) {
        for (auto c: dq) {
            cout << c;
        }
    } else {
        RREP(i, dq.size()-1, 0) {
            cout << dq.back();
            dq.pop_back();
        }
    }

    cout << '\n';

    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;

int main()
{
	string s;
	cin >> s;
	if (s.size() == 2) {
		cout << s << endl;
	}
	else {
		for (int i = 0; i < 3; i++) {
			cout << s.at(2 - i);
		}
		cout << endl;
	}
}

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

//0-indexed RMQ
class RMQ{
    public:
    int N;
    ll MAX;
    vector<ll>dat;
    RMQ(int n, ll x){
        N = 1;
        while(N < n)N *= 2;
        dat = vector<ll>(2 * N);
        for(int i = 0; i < 2 * N - 1; i++)dat[i] = x;
        MAX = (1ll) << 62;
    }
    void update(int k, ll x){
        k += N - 1;
        dat[k] = x;
        while(k > 0){
            k = (k - 1) / 2;
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    // [a, b)
    ll query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l)return MAX;
        if(a <= l && r <= b)return dat[k];
        else{
            ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
    ll query(int a, int b){
        return query(a, b, 0, 0, N);
    }
};

int main(){
    int N, Q;
    cin >> N >> Q;
    RMQ rmq(N, (1 << 31) - 1);
    for(int i = 0; i < Q; i++){
        int c, x, y;
        cin >> c >> x >> y;
        if(c == 0)rmq.update(x, y);
        else cout << rmq.query(x, y + 1) << endl;
    }
    
    return 0;
}


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

int main() {
  int W ,H , N;
  cin >> W >> H >> N;
  vector <tuple <int , int , int >> A(N);
  for ( int i=0 ; i<N ; i++){
    int a,b,c;
    cin >> a >> b >> c;
    A.at(i)=make_tuple(c,a,b);
  }
  int x_max=W ,x_min=0 , y_max=H , y_min=0;
  for ( int i=0 ; i< N ; i++){
    int c,b, a;
    tie(c,a,b) = A.at(i) ;
    if ( c == 1){
      x_min=max(x_min,a);
      continue ;
    }
    if ( c == 2){
      x_max=min(x_max,a);
      continue ;
    }
    if ( c == 3){
      y_min =max(y_min,b);
      continue ;
    }
    if ( c == 4){
      y_max =min(y_max,b);
    }
  }
  if (x_min<x_max && y_min < y_max){
    cout << (x_max-x_min)*(y_max-y_min) <<endl;
  }else cout << 0 << endl;
}
      
  

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int a;

int solve(int x, int y, int c, int d, int v = 1){
    if(x == 0) return 1;
    if(d == 0) return 0;
    int ans = 0;
    for (int i = v; i <= a/c; ++i) {
        int q = y*i;
        int p = q/y*x-q/i;
        int cc = c * i;
        if(p >= 0 && cc <= a) ans += solve(p, q, cc, d-1, max(v, i));
    }
    return ans;
}

int main() {
    int p, q, n;
    while (cin >> p >> q >> a >> n, p){
        int g = __gcd(p, q);
        p /= g; q /= g;
        cout << solve(p, q, 1, n) << "\n";

    }
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    string ans = "";
    while (N != 0) {
        if (N % 2 == 0)
            ans = "0" + ans;
        else {
            ans = "1" + ans;
            N--;
        }
        N /= -2;
    }
    if (ans == "")
        ans = "0";
    cout << ans << endl;
    return 0;
}

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

int main() {
    int A, B, K;
    std::cin >> A >> B >> K;

    for (int i = A; i < std::min(A + K, B + 1); ++i) {
        std::cout << i << std::endl;
    }

    for (int i = std::max(B - K + 1, A + K); i <= B; ++i) {
        std::cout << i << std::endl;
    }

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  int ans = 0;
  rep(i,1,n+1) {
    int a;
    cin >> a;
    if (i % 2 == 1 && a % 2 == 1) ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <unordered_set>
#include <cstdint>
#include <vector>
#include <sstream>
#include <string>
#include <climits>
#include <set>
#include <array>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <map>
using namespace std;

int main()
{
	string str;
	cin >> str;
	for (char ch : str)
		cout << 'x';
}

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

int main()
{
    int x[5] = {0};
    int n = 0;

    for (auto i = 0; i < 5; i++)
    {
        cin >> x[i];
        if (x[i] == 0) {
            n = i + 1;
            break;
        }
    }
    cout << n << endl;

    return 0;
}

Measured memory_bytes: 3588
n,a,b,c=[int(x) for x in input().split()]
S=[input() for i in range(n)]
ans=""
for i in range(n):
  s=S[i]
  if s=="AB":
    if a==0 and b==0:
      print("No")
      exit()
    elif a>b:
      ans+="B\n"
      a-=1
      b+=1
    elif b>a:
      ans+="A\n"
      a+=1
      b-=1
    else:
      if i+1<n and S[i+1]=="AC":
         ans+="A\n"
         a+=1
         b-=1
      else:
         ans+="B\n"
         a-=1
         b+=1
  elif s=="AC":
    if a==0 and c==0:
      print("No")
      exit()
    elif a>c:
      ans+="C\n"
      a-=1
      c+=1
    elif c>a:
      ans+="A\n"
      a+=1
      c-=1
    else:
        if i+1<n and S[i+1]=="BC":
            ans+="C\n"
            a-=1
            c+=1
        else:
            ans += "A\n"
            a+=1
            c-=1
  elif s=="BC":
    if c==0 and b==0:
      print("No")
      exit()
    elif c>b:
      ans+="B\n"
      c-=1
      b+=1
    elif b>c:
      ans+="C\n"
      c+=1
      b-=1
    else:
        if i+1<n and S[i+1]=="AB":
            ans += "B\n"
            b+=1
            c-=1
        else:
            ans+="C\n"
            c+=1
            b-=1
print("Yes")
print(ans,end="")

Measured memory_bytes: 16596
/*
 * written by Yaqi Zhang
 * University of Wisconsin-Madison
 * 2020
 */

#include<algorithm>
#include<cstring>
#include<iostream>
#include<map>
#include<unordered_map>
#include<queue>
#include<set>
#include<stdio.h>
#include<vector>

#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;

const int MAXN = 53;

int N, M, S;
vector<tuple<int, int, int>> graph[MAXN];
int cs[MAXN];
int ds[MAXN];

long long dijkstra(int start, int end) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, S * MAXN + start});
    vector<vector<ll>> dist(MAXN, vector<ll>(2505, -1LL));
    dist[start][S] = 0;
    while(!pq.empty()) {
        auto p = pq.top();
        pq.pop();
        ll t = p.first;
        int u = p.second % MAXN;
        int s = p.second / MAXN;
        if(u == end) return t;
        if(t < dist[u][s]) continue;
        for(auto & nei : graph[u]) {
            int v = get<0>(nei);
            int a = get<1>(nei);
            int b = get<2>(nei);
            if (s >= a) {
                if(dist[v][s - a] == -1 || dist[v][s - a] > t + b) {
                    dist[v][s - a] = t + b;
                    pq.push({t + b, (s - a) * MAXN + v});
                }
            }
        }
        int c = cs[u];
        int d = ds[u];
        if (s + c <= 2500) {
            if(dist[u][s + c] == -1 || dist[u][s + c] > t + d) {
                dist[u][s + c] = t + d;
                pq.push({t + d, (s + c) * MAXN + u});
            }
        }
    }
    return -1;
}


int main(int argc, char *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> S;
    S = min(S, 50 * 50);
    for(int i = 0; i < M; ++i) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        graph[u].emplace_back(v, a, b);
        graph[v].emplace_back(u, a, b);
    }
    for(int i = 0; i < N; ++i) {
        int c, d;
        cin >> c >> d;
        cs[i + 1] = c;
        ds[i + 1] = d;
    }
    for(int i = 2; i <= N; ++i) {
        cout << dijkstra(1, i) << endl;
    }
    return 0;

}



Measured memory_bytes: 7344
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main(){

    int N;
    cin >> N;

    int L[N];
    for(int i=0; i < N ; i++) cin >> L[i];

    sort(L, L+N , greater<int>());

    int answer = 0;
    for(int i=0; i< N-2; i++) {
        for(int j=i+1; j< N-1; j++){
            for(int k=j+1; k<N; k++){
                if(L[i] < L[j]+L[k]){
                    answer++;
                } else{
                    break;
                }
            }
        }
    }

    cout << answer << endl;

    return 0;
}



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

int main()
{
    ll N;
    cin >> N;

    if (N == 1)
    {
        cout << 0 << endl;
        return 0;
    }

    ll mod = pow(10, 9) + 7;
    ll ten_mod = 1;
    ll nine_mod = 1;
    ll eight_mod = 1;
    rep(i, N)
    {
        ten_mod *= 10;
        ten_mod %= mod;

        eight_mod *= 8;
        eight_mod %= mod;

        nine_mod *= 9;
        nine_mod %= mod;
    }

    ll ans = ten_mod - 2 * nine_mod + eight_mod;
    while (ans < 0)
    {
        ans += mod;
    }

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

Measured memory_bytes: 3624
import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    
    int x = sc.nextInt();
    int a = sc.nextInt();
    if(x<a){
      System.out.println(0);
    }
    else{
      System.out.println(10);
    }
  }
}

Measured memory_bytes: 23252
N = int(input())
S = list(map(int, input().split()))

ans = 0
for C in range(1, N):
    fkC = 0
    L = 0
    R = N-1
    if ((N-1) % C == 0):
        while L < R:
            fkC += S[L] + S[R]
            ans = max(ans, fkC)
            L += C
            R -= C
    else:
        while L+C < N-1:
            fkC += S[L] + S[R]
            ans = max(ans, fkC)
            L += C
            R -= C

print(ans)

Measured memory_bytes: 14860
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define mod ((int)1e9+7)
#define lim 1000000000000000007
#define lim1 18446744073709551615  //Unsigned
#define sq(a) ((a)*(a))
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mms(v,i) memset(v,i,sizeof(v))
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define REPN(i,a,b) for (int i = a; i >= b; i--)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> PL;
typedef pair<ll,int> PLI;
typedef pair<int,ll> PIL;
typedef pair<int,pair<int,int> > pii;
typedef pair<double,double> pdd;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a,ll b) {
   ll res=1;
   while(b){
      if(b%2==1) res=(res*a)%mod;
      a=(a*a)%mod;
      b>>=1;
   }
   return res;
}
ll gcdll(ll a,ll b) {
    if (b==0) return a;
    return gcdll(b,a%b);
}
int gcd(int a,int b) {
    if (b==0) return a;
    return gcd(b,a%b);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = (int)1e5+5;
const int M = (int)3e3+5;
const int Q = 301;
const int logN = 19;

ll f(ll a) {
    return a*sq(sq(a));
}
ll val(ll a,ll b) {
    return f(a)-f(b);
}
void solve() {
    ll x;
    cin>>x;
    REP(a,-2000,2000) {
        REP(b,-2000,2000) {
            if(val(a,b)==x) {
                cout<<a<<" "<<b;
                return;
            }
        }
    }
    assert(false);
}
int main() {
    //freopen("output.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T=1;
    //cin>>T;
    REP(TC,1,T) {
        //cout<<"Case #"<<TC<<": ";
        solve();
        cout<<"\n";
    }
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, n)  for(ll i = 0; i < (n); ++i)
#define rep1(i,n)  for(ll i = 1;i <= (n); ++i)
#define pb push_back
#define M 1000000007
unordered_map<ll,ll>mp;

int main()
{
    fastIO
    ll n;
    cin>>n;
    ll v[n+1];
    for(ll i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    ll suf[n+2];
    suf[n+1]=0;
    for(int i=n;i>=1;i--)
        suf[i]=(v[i]+suf[i+1])%M;
    ll res=0;
    for(ll i=1;i<=n;i++)
    {
        ll x=(v[i]*suf[i+1])%M;
        res=(res+x)%M;
    }
    cout<<res;
	return 0;
}


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

using namespace std;

int main(){
	int n, k;
	cin >> n >> k;
	int x[n];
	for(int i = 0; i < n; i++)
		cin >> x[i];
	int r = 0;
	for(int i = 0; i < n; i++)
		r += 2 * min(x[i], abs(x[i] - k));
	cout << r;
	
	return 0;
}

Measured memory_bytes: 256
<?php

$input;
$input2;
$cnt=0;

fscanf(STDIN, "%s", $input);
fscanf(STDIN, "%s", $input2);

for($i=0;$i<3;$i++){
    if($input[$i]===$input2[$i]){
        $cnt++;
    }
}

echo $cnt;

?>

Measured memory_bytes: 3828
#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1LL<<60; // 無限大を表す値 (十分大きい値に定める)

// 入力
int N;
vector<long long> h;

// メモ化配列
vector<long long> dp;

long long rec(int i) {
    // 終端条件
    if (i == 0) return 0;

    // 計算済みならば返す
    if (dp[i] != -1) return dp[i];

    long long result = INF;
    if (i - 1 >= 0) result = min(result, rec(i-1) + abs(h[i] - h[i-1]));
    if (i - 2 >= 0) result = min(result, rec(i-2) + abs(h[i] - h[i-2]));
    
    // 答えをメモ化しながら返す
    return dp[i] = result;
}

int main() {
    cin >> N;
    h.resize(N);
    for (int i = 0; i < N; ++i) cin >> h[i];
    dp.assign(N+1, -1); // メモ化用配列を初期化
    cout << rec(N-1) << endl;
}

Measured memory_bytes: 9488
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int n, k, s;
    cin >> n >> k >> s;
    if (n == k) {
        REP(i, n) cout << s << (i == n - 1 ? EOL : ' ');
    } else {
        if (s == 1) {
            REP(i, k) cout << "1 ";
            REP(i, n - k) cout << 2 << (i == n - k - 1 ? EOL : ' ');
        } else if (s % 2 == 0) {
            REP(i, k + 1) cout << s / 2 << (i == n - 1 ? EOL : ' ');
            REP(i, n - k - 1) cout << (s == 1000000000 ? 1 : s + 1) << (i == n - k - 2 ? EOL : ' ');
        } else {
            REP(i, k + 1) cout << (i % 2 == 0 ? s / 2 : s / 2 + 1) << (i == n - 1 ? EOL : ' ');
            REP(i, n - k - 1) cout << (s == 1000000000 ? 1 : s + 1) << (i == n - k - 2 ? EOL : ' ');
        }
    }
}


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

#define rep(i, n) for(int i = 0; i < (n); i++)
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}

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

    int N;
    cin >> N;

    int counter[100000+2];
    memset(counter, 0, sizeof counter);

    int ans = -1;
    int a;
    rep(i, N) {
        cin >> a;
        chmax(ans, ++counter[a]);
        chmax(ans, ++counter[a + 1]);
        chmax(ans, ++counter[a + 2]);
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
fun main(args: Array<String>) {
    val (a, b, x) = readLine()!!.split(' ').map { it.toLong() }
    fun f(a:Long): Long {
        if (a == -1L) return 0L
        return a/x+1L
    }
    println(f(b) - f(a-1))
}



Measured memory_bytes: 36436
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int DINIC_MAX_V=1002;
const int DINIC_v_size=1002;
//const int INF=99999999;
vector<pair<pair<int,int> ,int> >DINIC_G[DINIC_MAX_V];
int DINIC_level[DINIC_MAX_V];
int DINIC_iter[DINIC_MAX_V];

void add_edge(int from,int to,int cap){
	DINIC_G[from].push_back(make_pair(make_pair(to,cap),DINIC_G[to].size()));
	DINIC_G[to].push_back(make_pair(make_pair(from,0),DINIC_G[from].size()-1));
}
void DINIC_bfs(int s){
	for(int i=0;i<DINIC_v_size;i++)DINIC_level[i]=-1;
	queue<int> Q;
	DINIC_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<DINIC_G[v].size();i++){
			if(DINIC_G[v][i].first.second>0&&DINIC_level[DINIC_G[v][i].first.first]<0){
				DINIC_level[DINIC_G[v][i].first.first]=DINIC_level[v]+1;
				Q.push(DINIC_G[v][i].first.first);
			}
		}
	}
}
int DINIC_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;DINIC_iter[v]<DINIC_G[v].size();DINIC_iter[v]++){
		int i=DINIC_iter[v];
		if(DINIC_G[v][i].first.second>0&&DINIC_level[v]<DINIC_level[DINIC_G[v][i].first.first]){
			int d=DINIC_dfs(DINIC_G[v][i].first.first,t,min(f,DINIC_G[v][i].first.second));
			if(d>0){
				DINIC_G[v][i]=make_pair(make_pair(DINIC_G[v][i].first.first,DINIC_G[v][i].first.second-d),DINIC_G[v][i].second);
				DINIC_G[DINIC_G[v][i].first.first][DINIC_G[v][i].second]=make_pair(make_pair(DINIC_G[DINIC_G[v][i].first.first][DINIC_G[v][i].second].first.first,DINIC_G[DINIC_G[v][i].first.first][DINIC_G[v][i].second].first.second+d),DINIC_G[DINIC_G[v][i].first.first][DINIC_G[v][i].second].second);
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		DINIC_bfs(s);
		if(DINIC_level[t]<0)return flow;
		for(int i=0;i<DINIC_v_size;i++)DINIC_iter[i]=0;
		int f;
		while((f=DINIC_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}
int c[500];
int d[500];
int gcd(int a,int b){
	while(b){
		a%=b;
		int c=a;
		a=b;
		b=c;
	}return a;
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a+b){
		for(int i=0;i<1002;i++)DINIC_G[i].clear();
		for(int i=0;i<1002;i++)DINIC_level[i]=DINIC_iter[i]=0;
		for(int i=0;i<a;i++)scanf("%d",c+i);
		for(int i=0;i<b;i++)scanf("%d",d+i);
		for(int i=0;i<a;i++)add_edge(1000,i,1);
		for(int i=0;i<b;i++)add_edge(a+i,1001,1);
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++)
				if(gcd(c[i],d[j])!=1)add_edge(i,a+j,1);
		printf("%d\n",max_flow(1000,1001));
	}
}

Measured memory_bytes: 7340
#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAXN 56
#define INF 21000000000000000
using namespace std;
long long n,s,m,ans=INF;
long long check(long long b,long long x)
{
	long long re=0;
	while(x)
	{
		re+=x%b;
		x/=b;
	}
	return re;
}
int main()
{
	scanf("%lld%lld",&n,&s);
	m=sqrt(n)+10;
	for(long long i=2;i<=m;i++)
	{
		if(check(i,n)==s)
		{
			printf("%lld",i);
			return 0;
		}
	}
	for(long long x1=m;x1>=1;x1--)
	{
		long long x=s-x1;
		long long b=(n-x)/x1;
		if(b*x1+x==n&&b>=2&&x<b&&x>=0&&x1<b)
		{
			ans=min(ans,b);
		}
	}
	if(ans==INF) 
	{
		if(n==s) printf("%lld",n+1);
		else printf("-1");
	}
	else printf("%lld",ans);
}

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

for _ in range(n):
    runners = []
    outs = 0
    score = 0
    while True:
        s = input()
        if s == "HIT":
            runners.append(0)
            for i in range(len(runners)):
                runners[i] += 1
                if runners[i] == 4:
                    score += 1
            if 4 in runners:
                runners.remove(4)
        elif s == "HOMERUN":
            score += len(runners) + 1
            runners = []
        elif s == "OUT":
            outs += 1
            if outs == 3:
                break
    print(score)

Measured memory_bytes: 7612
import bisect

N, K = map(int, input().split())
A = [int(x) for x in input().split()]

# Aを正負で分け、「積が負、積が0、積が正」それぞれのペア数を求める
A_minus = sorted([a for a in A if a < 0])
A_plus = sorted([a for a in A if a > 0])
len_minus = len(A_minus)
len_plus = len(A_plus)
len_zero = N - len_minus - len_plus
pairs_num = (len_minus * len_plus,
             (len_minus + len_plus) * len_zero + len_zero * (len_zero - 1) // 2,
             len_minus * (len_minus - 1) // 2 + len_plus * (len_plus - 1) // 2)
assert sum(pairs_num) == N * (N - 1) // 2

if K <= pairs_num[0]:
    L = -10 ** 18
    R = -1
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_plus):
            while j < len_minus and A_plus[i] * A_minus[j] <= M:
                j += 1
            count += j
        
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M
            
elif pairs_num[0] < K <= pairs_num[0] + pairs_num[1]:
    print(0)
    
else:
    K -= pairs_num[0] + pairs_num[1]
    A_minus = list(map(lambda x: -x, reversed(A_minus)))
    L = 1
    R = 10 ** 18
    while True:
        M = (L + R) // 2
        count = 0
        j = 0
        for i in range(len_minus-1, -1, -1):
            while j < len_minus and A_minus[i] * A_minus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
        j = 0
        for i in range(len_plus-1, -1, -1):
            while j < len_plus and A_plus[i] * A_plus[j] <= M:
                j += 1
            count += max(0, j - i - 1)
            
        if count < K and R - L == 1:
            print(R)
            break
        elif K <= count:
            R = M
        else:
            L = M


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

int main() {
	string s,t,r="";
	cin>>s>>t;

	int x=s.length();
	int y=t.length();
	
	int dp[x+1][y+1];
	
	for(int i=0;i<=x;i++){
		for(int j=0;j<=y;j++){
			if(i==0||j==0)dp[i][j]=0;
			else{
				if(s[i-1]==t[j-1]){
					dp[i][j]=dp[i-1][j-1]+1;
				}
				else{
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
	}
	int i=x,j=y;
	while(dp[i][j]!=0&&(i>=0&&j>=0)){
		if(dp[i][j]>max(dp[i-1][j],dp[i][j-1])){
			r=s[i-1]+r;
			i=i-1;
			j=j-1;
		}
		else{
			if(dp[i-1][j]>dp[i][j-1]){
				i=i-1;
			}
			else{
				j=j-1;
			}
		}
	}
	cout<<r;
	
	return 0;
}

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

const int MAXN = 100010;

int a[MAXN];

int main(){
	int N, L;
	scanf("%d %d", &N, &L);
	for (int i = 1; i <= N; ++i)
		scanf("%d", &a[i]);
	int p = 1;
	while (p < N){
		if (a[p] + a[p + 1] >= L)
			break;
		++p;
	}
	if (p == N){
		printf("Impossible");
		return 0;
	}
	printf("Possible\n");
	for (int i = 1; i < p; ++i)
		printf("%d\n", i);
	for (int i = N - 1; i > p; --i)
		printf("%d\n", i);
	printf("%d", p);
	return 0;
}


Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define ll long long
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define N 3000005
#define M 1000000007
#define pii pair<ll,ll>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

ll dp[N][2][2];
int n;
ll run(int idx,int a,int b)
{
    if(idx==n)
        return 1*(a==1)*(b==1);
    if(dp[idx][a][b]!=-1)
        return dp[idx][a][b];
    ll ans=0;
    for(int i=0;i<=9;i++)
    {
        ans+=run(idx+1,a|(i==0),b|(i==9));
        ans%=M;
    }
    return dp[idx][a][b]=ans;
}

main()
{
    memset(dp,-1,sizeof dp);
    cin>>n;
    cout<< run(0,0,0);
}



Measured memory_bytes: 175492
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
	string A, B;
    cin >> A >> B;
    if (A.size() > B.size()) {
        cout << "GREATER" << endl;
        return 0;
    }
    if (A.size() < B.size()) {
        cout << "LESS" << endl;
        return 0;
    }
    string ans = "EQUAL";
    rep(i, A.size()) {
        if (A[i] > B[i]) {
            ans = "GREATER";
            break;
        } else if (A[i] < B[i]) {
            ans = "LESS";
            break;
        }
    }
    cout << ans << endl;
}

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

using namespace std;

#define REP(var, n)  for (int var = 0; var < (n); var++)
#define RREP(var, n)  for (auto var = n - 1; var != static_cast<int>(-1); var--)
#define FOR(var, a, b)  for (auto var = (a); var < (b); var++)
#define RFOR(var, a, b)  for (auto var = b - 1; var != a; var--)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> pii;

#define all(c) begin(c),end(c)

#define D(x) do { std::cerr << x << " "; } while (0)
#define D2(x) do { std::cerr << #x << ": " << x << std::endl; } while (0)


template<typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
    if (!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}


template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

int MOD = (int) 1e9 + 7;

ll fpow(ll a, ll k) {
    ll res = 1;
    ll t = a;

    while (k > 0) {
        if (k % 2 == 1) {
            res = (res * t) % MOD;
        }
        t = (t * t) % MOD;
        k >>= 1;
    }

    return res;
}

vll fact;
vll ifact;

ll nCr(int r, int c) {
    ll r1 = (fact[r] * ifact[c]) % MOD;
    ll r2 = (r1 * ifact[r - c]) % MOD;
    return r2 % MOD;
}


ll solve() {
    int H, W, N;
    cin >> H >> W >> N;

    fact.resize(1e5 * 3);
    fact[0] = 1;
    FOR(i, 1, 1e5 * 3) fact[i] = (fact[i - 1] * i) % MOD;

    ifact.resize(1e5 * 3);
    REP(i, 1e5 * 3) ifact[i] = (fpow(fact[i], MOD - 2)) % MOD;


    vector<pii> walls(N + 1);
    REP(i, N) {
        int r, c;
        cin >> r >> c;
        --r, --c;
        walls[i] = {r, c};
    }
    walls[N] = {H - 1, W - 1};
    sort(all(walls));

    vll dp(N + 1, 0);
    REP(i, N + 1) {
        int ir = walls[i].first, ic = walls[i].second;
        dp[i] = nCr(ir + ic, ic);

        REP(j, i) {
            int jr = walls[j].first, jc = walls[j].second;

            if (jr <= ir && jc <= ic) {
                int dr = ir - jr, dc = ic - jc;
                // dp[i] -= dp[j] * nCr(dr + dc, dc);
                dp[i] = (MOD + (dp[i] - dp[j] * nCr(dr + dc, dc)) % MOD) % MOD;
            }
        }
    }

    return dp[N];
}


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

//    cout << (solve() ? "Heisei" : "TBD") << endl;
//    cout << (solve() ? "YES" : "NO") << endl;
    cout << solve() << endl;
//    solve();

    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n;
  string s,t;
  cin>>n>>s>>t;
  const Int MOD = 1e9+7;
  vector<Int> c(26,0),dp(n,0);
  dp[0]=1;
  for(Int i=0;i<n;i++){
    dp[i]+=c[t[i]-'a'];
    dp[i]%=MOD;
    c[s[i]-'a']+=dp[i];
    c[s[i]-'a']%=MOD;
  }
  cout<<dp.back()<<endl;
  return 0;
}



Measured memory_bytes: 3924