akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi; 
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;

#define sz(a) int((a).size())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define ini(a, i) memset(a, i, sizeof(a))
#define contains(c, i) ((c).find(i) != (c).end())
#define present(i, c) (find(all(c), i) != (c).end())

#define trav(x, c) for(auto &x : c)
#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, b, e) for(int i = (b)-((b)>(e)); i != (e)-((b)>(e)); i += 1-2*((b)>(e)))

#define debug(args...) { string s_(#args); replace(all(s_), ',', ' '); stringstream ss_(s_); istream_iterator<string> it_(ss_); cerr_(it_, args); }
void cerr_(istream_iterator<string> it) { (void) it; }
template<class T, class... Args> void cerr_(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << endl; cerr_(++it, args...); }

template<class T, class S>  ostream& operator<<(ostream& os, const pair<T, S>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<class T> ostream& operator<<(ostream &os, const set<T> &s) { os << '{'; string sep; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<class T, class S> ostream& operator<<(ostream &os, const map<T, S> &m) { os << '{'; string sep; for (const auto &x : m) os << sep << x, sep = ", "; return os << '}'; }
template<class T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }

//=========================

void run_test() {
    int n; cin >> n;
    vi a(n);
	trav(_a, a) cin >> _a;
    sort(rall(a));
    ll ans = a[0]; n -= 2;
    int ix = 1, c = 0;
    while(n > 0) {
        if(c == 2) {
            c = 0;
            ix++;
        }
        ans += (ll) a[ix];
        n--;
        c++;
    }
    cout << ans << endl;
}

//=========================

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	//int t_ = 1, t__; cin >> t__; while(t_ <= t__) { cout << "Case #" << t_++ << ": "; run_test(); }
	// int t_; cin >> t_; while(t_--) run_test();
	run_test();
	return 0;	
}


Measured memory_bytes: 3984
import static java.lang.Math.*;
import static java.util.Arrays.*;

import java.util.*;
import java.io.*;
import java.math.BigInteger;

import static java.math.BigInteger.*;

public class Main {
	void solve() {
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] p = new int[N+2];
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			p[a]++;
			p[b]--;
		}
		for (int i = 0; i + 1 < p.length; i++) {
			p[i+1] += p[i];
		}
		boolean yes = true;
		for (int i = 0; i < N; i++) {
			if (p[i] % 2 != 0)
				yes = false;
		}
		out.println(yes ? "YES":"NO");
	}

	static void tr(Object... os) { System.err.println(deepToString(os)); }
	static void tr(int[][] as) { for (int[] a : as) tr(a); }

	void print(int[] a) {
		out.print(a[0]);
		for (int i = 1; i < a.length; i++) out.print(" " + a[i]);
		out.println();
	}

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

	MyScanner sc = null;
	PrintWriter out = null;
	public void run() throws Exception {
		sc = new MyScanner(System.in);
		out = new PrintWriter(System.out);
		for (;sc.hasNext();) {
			solve();
			out.flush();
		}
		out.close();
	}

	class MyScanner {
		String line;
		BufferedReader reader;
		StringTokenizer tokenizer;

		public MyScanner(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream));
			tokenizer = null;
		}
		public void eat() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					line = reader.readLine();
					if (line == null) {
						tokenizer = null;
						return;
					}
					tokenizer = new StringTokenizer(line);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		public String next() {
			eat();
			return tokenizer.nextToken();
		}
		public String nextLine() {
			try {
				return reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		public boolean hasNext() {
			eat();
			return (tokenizer != null && tokenizer.hasMoreElements());
		}
		public int nextInt() {
			return Integer.parseInt(next());
		}
		public long nextLong() {
			return Long.parseLong(next());
		}
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
	}
}

Measured memory_bytes: 43092
import qualified Data.Map as M

(!?) :: Ord k => M.Map k a -> k -> Maybe a
m !? k
  | M.member k m = Just $ m M.! k
  | otherwise = Nothing

toSwapMap :: String -> String -> Maybe (M.Map Char Char)
toSwapMap ss ts = foldr helper (Just M.empty) $ zip ss ts
  where helper (s,t) m = do
          m' <- m
          case m' !? s of
            Nothing -> return (M.insert s t m')
            Just u -> if t == u then m else Nothing

canSwap ss ts = (toSwapMap ss ts /= Nothing) && (toSwapMap ts ss /= Nothing)

main = do
  ss <- getLine
  ts <- getLine
  if canSwap ss ts
    then putStrLn "Yes"
    else putStrLn "No"


Measured memory_bytes: 28028
package main

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

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)
	S := make([]int, n)
	for i := range S {
		S[i] = nextInt(sc)
	}
	q := nextInt(sc)
	var ans int
	for i := 0; i < q; i++ {
		v := nextInt(sc)
		for i := range S {
			if S[i] == v {
				ans++
				break
			}
		}
	}
	fmt.Println(ans)
}
func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	t, _ := strconv.Atoi(sc.Text())
	return t
}



Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define MAX 100
#define MOD 1000000007
#define pb push_back

/* add vars here */

ll N;
vector<ll> a, b, c;

/* add your algorithm here */

int main() {
  cin >> N;

  rep(i,N) {
    ll t;
    scanf("%lld", &t);
    a.pb(t);
  }
  rep(i,N) {
    ll t;
    scanf("%lld", &t);
    b.pb(t);
  }
  rep(i,N) {
    ll t;
    scanf("%lld", &t);
    c.pb(t);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  vector<ll>::iterator aitr = a.begin();
  vector<ll>::iterator citr = c.begin();
  ll ans = 0;

  rep(i,N) {
    ll t = b[i];
    aitr = lower_bound(aitr, a.end(), t);
    citr = upper_bound(citr, c.end(), t);
    ll x = aitr - a.begin(), y = c.end() - citr;
    // cout << x << " " << y << endl;
    ans += x * y;
  }

  cout << ans << endl;
}


Measured memory_bytes: 3316
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        sc.close();
        
        boolean ok = false;
        for (int a = 0; a <= 100; a++) {
            int b = x-a;
            if (b >= 0) {
                if (2*a+4*b == y) {
                    ok = true;
                }
            }
        }

        if (ok) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}



Measured memory_bytes: 35724
#include<stdio.h>
#include<vector>

using namespace std;

int main(){
  int n=1;
  scanf("%d",&n);

  vector<int> l(n);
  for(int i=0;i<n;i++){
    scanf("%d",&l[i]);
  }

  int max = -10;
  int sum = 0;

  for(int i=0;i<n;i++){
    max = (l[i]>max) ? l[i] : max;
    sum += l[i];
  }
  sum -= max;

  if(sum>max){
    printf("Yes\n");
  }else{
    printf("No\n");
  }


  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <vector>
#include <climits>

typedef long long ll;

using namespace std;

void solve(){
    int h, w;
    while(cin >> h >> w){
        if(h == 0 && w == 0){
            return;
        }
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 3068
#include "bits/stdc++.h"
using namespace std;
#define mod 1000000007
#define dom 998244353
#define all(c) begin(c),end(c)
#define rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }
#define long long long
#define List vector
#define var auto
#define Count size()
#define Length size()
int dd[] = { 0, 1, 0, -1, 0 }; //→↓←↑

using mat = vector<vector<long>>;
mat matmul(mat ma, mat mb, long Mod)
{
	int p = ma.size();
	int q = mb[0].size();
	int r = ma[0].size();
	mat ret = mat(p, vector<long>(q));
	for (int i = 0; i < p; i++)
	{
		for (int j = 0; j < q; j++)
		{
			for (int k = 0; k < r; k++)
			{
				ret[i][j] += ma[i][k] * mb[k][j] % Mod;
			}
			ret[i][j] %= Mod;
		}
	}
	return ret;
}
mat matpow(mat m, long a, long Mod)
{
	if (a == 0)
	{
		int N = m.size();
		mat ret = mat(N, vector<long>(N));
		for (int i = 0; i < N; i++)
		{
			ret[i][i] = 1;
		}
		return ret;
	}
	if (a % 2 == 0)
	{
		mat ret = matpow(m, a / 2, Mod);
		return matmul(ret, ret, Mod);
	}
	else
	{
		return matmul(m, matpow(m, a - 1, Mod), Mod);
	}
}

void solve()
{
	int N; cin >> N;
	long K; cin >> K;
	mat A = mat(N, vector<long>(N));
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> A[i][j];
		}
	}
	mat B = matpow(A, K, mod);
	long sum = 0;
	rep(i, N)
	{
		rep(j, N)
		{
			sum += B[i][j];
		}
		sum %= mod;
	}
	cout << sum << endl;

	
}

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


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

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    int i, j;
    for(i = 0; i < m; i++){
        cin >> a.at(i);
    }
    int sum = 0;
    for(int x : a){
        sum += x;
    }
    int ans = n-sum;
    if(ans >= 0){
        cout << ans << endl;
    }
    else{
        cout << -1 << endl;
    }
    return 0;
}


Measured memory_bytes: 7220
import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    String[] line1 = br.readLine().split(" ");
    int n = Integer.parseInt(line1[0]);
    int m = Integer.parseInt(line1[1]);
    int[][] students = new int[n][2];
    int[][] checkpoints = new int[m][2];
    String[] data;
    for (int i=0; i<n; i++){
      data = br.readLine().split(" ");
      students[i][0] = Integer.parseInt(data[0]);
      students[i][1] = Integer.parseInt(data[1]);
    }
    for (int i=0; i<m; i++){
      data = br.readLine().split(" ");
      checkpoints[i][0] = Integer.parseInt(data[0]);
      checkpoints[i][1] = Integer.parseInt(data[1]);
    }
    
    StringBuilder stringBuilder = new StringBuilder();
    for (int i=0; i<n; i++){
      int minDistance = Integer.MAX_VALUE;
      int minIndex = 0;
      int tempDistance;
      for (int j=0; j<m; j++){
        tempDistance = Math.abs(students[i][0] - checkpoints[j][0]) + Math.abs(students[i][1] - checkpoints[j][1]);
        if (minDistance>tempDistance){
          minIndex = j + 1;
          minDistance = tempDistance;
        }
      }
      stringBuilder.append(minIndex).append("\n");
    }
    System.out.print(stringBuilder.toString());
  }
}


Measured memory_bytes: 22612
# from math import sqrt
# from heapq import heappush, heappop
# from collections import deque
# from functools import reduce

# a, b = [int(v) for v in input().split()]


def main():
    N = int(input())

    table = []
    for _ in range(N):
        A = int(input())
        ary = []
        for _ in range(A):
            x, y = map(int, input().split())
            ary.append((x - 1, y))

        table.append(ary)

    def check(bit):
        for i in range(N):
            if (bit & (1 << i)) == 0:
                continue
            for x, y in table[i]:
                if y == 1 and bit & (1 << x) == 0:
                    return False
                if y == 0 and bit & (1 << x) != 0:
                    return False
        return True

    def search(i, bit):
        if i == N:
            if not check(bit):
                return 0
            return sum(1 for i in range(N) if (bit & (1 << i)) != 0)

        count1 = search(i + 1, bit)
        count2 = search(i + 1, bit | (1 << i))
        return max(count1, count2)

    count = search(0, 0)
    print(count)


main()


Measured memory_bytes: 3064
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int inf=1e9;
const long long INF=1e18;
const int dx[]={1,1,-1,-1};
const int dy[]={1,-1,1,-1};
int n,p,s,t; 
int head[2050];
struct edge
{
	int to,nex,cap,flow,cost;
	edge(int to=0,int nex=0,int cap=0,int flow=0,int cost=0):to(to),nex(nex),cap(cap),flow(flow),cost(cost){}
};
vector<edge> G;
inline void addedge(int u,int v,int c,int w)
{
	G.push_back(edge(v,head[u],c,0,w)),head[u]=G.size()-1;
	G.push_back(edge(u,head[v],0,0,-w)),head[v]=G.size()-1;
}
namespace MCMF
{
	int q[8050],hd,tl;
	int pre[2050];
	long long dis[2050];
	bool inq[2050];
	bool SPFA(int s,int t)
	{
		hd=tl=0;
		for(int i=0;i<p;++i)
		{
			dis[i]=-INF;
			pre[i]=-1;
			inq[i]=0;
		}
		dis[s]=0;
		inq[s]=1;
		q[tl++]=s;
		while(hd<tl)
		{
			int u=q[hd++];
			inq[u]=0;
			for(int i=head[u];~i;i=G[i].nex) if(G[i].cap!=G[i].flow)
			{
				int v=G[i].to;
				int w=G[i].cost;
				if(dis[v]<dis[u]+w)
				{
					dis[v]=dis[u]+w;
					pre[v]=i;
					if(!inq[v])
					{
						inq[v]=1;
						q[tl++]=v;
					}
				}
			}
		}
		return pre[t]!=-1;
	}
	void maxflow(int s,int t,int &flow,long long &cost)
	{
		flow=cost=0;
		while(SPFA(s,t))
		{
			int d=inf;
			for(int i=pre[t];~i;i=pre[G[i^1].to])
			{
  				d=min(d,G[i].cap-G[i].flow);
			}
			flow+=d;
			for(int i=pre[t];~i;i=pre[G[i^1].to])
			{
				G[i].flow+=d;
				G[i^1].flow-=d;
				cost+=1ll*d*G[i].cost;
			}
		}
	}
}
int main()
{
	scanf("%d",&n);
	p=4;
	s=p++;
	t=p++; 
	memset(head,-1,sizeof(head));
	for(int i=1;i<=n;++i)
	{
		int x,y,c; scanf("%d%d%d",&x,&y,&c);
		addedge(s,p,c,0);
		for(int k=0;k<4;++k)
		{
			addedge(p,k,inf,x*dx[k]+y*dy[k]);
		}
		++p;
	}
	for(int i=1;i<=n;++i)
	{
		int x,y,c; scanf("%d%d%d",&x,&y,&c);
		addedge(p,t,c,0);
		for(int k=0;k<4;++k)
		{
			addedge(k,p,inf,-x*dx[k]-y*dy[k]);
		}
		++p;
	}
	int flow;
	long long cost;
	MCMF::maxflow(s,t,flow,cost);
	printf("%lld\n",cost);
	return 0;
} 

Measured memory_bytes: 1084
use std::io::Read;

fn main() {
    let mut buf = String::new();
    let stdin = std::io::stdin();
    stdin.lock().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let h = iter.next().unwrap().parse::<usize>().unwrap();

    let mut ans = 0_usize;
    for i in (0..41).rev() {
        if (h & 1<<i) != 0_usize {
            for j in 0..i+1 {
                ans += 1<<j;
            }
            break;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
using namespace std; 
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
const int INF = 1<<29;
typedef long long ll;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef vector<ii> vii;
inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
template<class T> void chmax(T & a, const T & b) { a = max(a, b); }
template<class T> void chmin(T & a, const T & b) { a = min(a, b); }
/////////////////////////////////////////////////////////////////////
int main()
{
    ll n, i, a, cnt = 0, mini = 10000000;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> a;
        if (a < mini)
        {
            cnt++;
            mini = a;
        }
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,w;
    cin>>n>>w;
    vector<int> v(n);
    vector<int> g(n);
    for(int i=0;i<n;i++){
        cin>>v.at(i)>>g.at(i);
    }

    vector<vector<long long>> dp(n+1,vector<long long> (w+1,0));
    for(int i=1;i<n+1;i++){
        for(int j=1;j<w+1;j++){
            if(j<g.at(i-1)){
                dp.at(i).at(j)=dp.at(i-1).at(j);
            }
            else{
                dp.at(i).at(j)=max(dp.at(i-1).at(j-g.at(i-1))+v.at(i-1),dp.at(i-1).at(j));
            }
        }
    }
    cout<<dp.at(n).at(w)<<endl;
}


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

int main() {
  int N,T,A;
  cin >> N >> T >> A;
  vector<int> H(N);
  for(int i = 0; i < N; i++) {
    cin >> H[i];
  }
  int num = 0;
  double minabs = abs(A - (T - H[0] * 0.006));
  for(int i = 1; i < N; i++) {
    double tmp = abs(A - (T - H[i] * 0.006));
    if(tmp < minabs) {
      minabs = tmp;
      num = i;
    }
  }
  cout << num + 1 << endl;
}


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

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

//Others
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 dx[8] = { -1,0,1,-1,1,-1,0,1 };
const int dy[8] = { 1,1,1,0,0,-1,-1,-1 };


//LOVE NyantakoGG	https://www.youtube.com/channel/UC6XdFs8T6Ei54O0FYl3PVVA


using namespace std;



int main() {
	int N, K;
	cin >> N >> K;
	int ans = 1;
	for (int i = 0; i < N; i++) {
		ans = min(ans * 2, ans + K);
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
while True:
  m, f, r = [int(n) for n in input().split()]
  if m == f == r == -1:
    break
  if m == -1 or f == -1:
    print('F')
    continue
  if 80 <= m+f:
    print('A')
    continue
  if 65 <= m+f < 80:
    print('B')
    continue
  if 50 <= m+f < 65:
    print('C')
    continue
  if 30 <= m+f < 50:
    if 50 <= r:
      print('C')
    else:
      print('D')
    continue
  if m+f < 30:
    print('F')



Measured memory_bytes: 5604
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
    int q;
    scanf("%d", &q);

    for (int i = 0; i < q; i++) {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        ll sq = (ll)ceil(sqrt(a*b)) - 1;
        ll ans = 2 * (sq - 1);
        if (sq * sq < a * b) {
            ans += 1;   
            if (sq * (sq + 1) < a * b) {
                ans += 1;
            }
        }
        if (sq >= a ^ sq >= b) {
            ans -= 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

Measured memory_bytes: 128
import sys
from typing import Callable, List, NoReturn, Tuple


def main() -> NoReturn:
    scan: Callable[[], str] = sys.stdin.readline

    n, k = map(int, scan().rstrip().split())
    a: Tuple[int] = tuple(int(a_i) - 1 for a_i in scan().rstrip().split())

    flag: List[bool] = [False] * n
    path: List[int] = []

    current_city: int = 0
    prev_city: int = -1

    while not flag[current_city]:
        flag[current_city] = True
        path.append(current_city)
        prev_city = current_city
        current_city = a[current_city]

    start_loop_index: int = path.index(current_city)

    if k < len(path):
        print(path[k] + 1)
    else:
        index_in_loop: int = (k - start_loop_index) % (len(path) - start_loop_index)
        print((path[start_loop_index:])[index_in_loop] + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 101084
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sort(a) sort(all(a))
using P = pair<int, int>;
using ll = long long;
using ld = long double;
int dx[4] = { 0, 1, 0,-1 };
int dy[4] = { 1, 0,-1, 0 };

signed main() {
  string s;
  cin >> s;
  int n = s.length();
  int ans =0;
  for (int i = 0; i < n/2; i++) {
    if (s[i]!=s[n-1-i]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
const ll mod = 1000000007;
const ll INF = 9223372036854775807;
#define Sort(a) sort(a.begin(), a.end())
#define Bsort(a) sort(a.begin(), a.end(), greater<ll>())
#define Pi acos(-1)

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  ll n;
  cin >> n;
  vector<ll> a(5000000);
  ll ans = 0;
  rep(i,n) {
    ll t;
    cin >> t;
    a[t-1]++;
    ans += t;
  }
  ll q;
  cin >> q;
  rep(i,q) {
    ll b, c;
    cin >> b >> c;
    ll r = a[b-1];
    a[b-1] = 0;
    a[c-1] += r;
    ans = ans + r*(c-b);
    cout << ans << '\n';
  }
}

Measured memory_bytes: 42228
MOD=998244353
N,K=[int(s) for s in input().split()]
ls=[0 for _ in range(N)]
lssum=[0 for _ in range(N)]
ls[0]=1
lssum[0]=1

sections=[[int(s) for s in input().split()] for _ in range(K)]
sections.sort()

for i in range(1,N):
  for sec in sections:
    if sec[0]>i:
      continue
    else:
      l=sec[0]
      r=min([i,sec[1]])
      ls[i]=(ls[i]+lssum[i-l]-lssum[i-r-1])%MOD
  lssum[i]=(lssum[i-1]+ls[i])%MOD
print(ls[N-1])
      

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

int main(){
    ll n;
    cin>>n;
    V a(n+1),b(n+1),c(n+1);
    a[0]=0;b[0]=0;c[0]=0;
    rep(i,n){
        ll aa,bb,cc;
        cin>>aa>>bb>>cc;
        a[i+1]=max(b[i],c[i])+aa;
        b[i+1]=max(a[i],c[i])+bb;
        c[i+1]=max(a[i],b[i])+cc;
    }
    cout<<max(a[n],max(b[n],c[n]))<<endl;
}


Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod=1e9+7;

int main(){
    int n;
    cin >> n;
    bool flag = true;
    for(int i=1; i<=9; i++){
        if(n%i==0){
            if(n/i<=9) flag = false;
        }
    }
    if(flag) cout << "No";
    else cout << "Yes";
}

Measured memory_bytes: 256
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	console.log(input[0]-0 >= 3200 ? input[1] : "red");
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI acos(-1.0)
#define test() int t; cin>>t; while(t--)
#define ll long long int
int mod = 1e9 + 7;
int main()
{
	IOS;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<ll> pref(n + 1, 0);
	for (int i = n - 1; i >= 0; i--) {
		pref[i] = (pref[i + 1] + a[i]) % mod;
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		ans = (ans + (a[i] * pref[i + 1]) % mod) % mod;
	}

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


Measured memory_bytes: 5556
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

#define MAX 250000

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

    int n;
    cin >> n;
    string s;
    cin >> s;

    long MOD[2] = {1758706867, 1299697759};
    long X[2] = {716447, 656323};

    vector<vector<long>> pow(2, vector<long>(2 * MAX + 2));
    pow[0][0] = pow[1][0] = 1;
    for (int k = 0; k < 2; k++) {
        for (int i = 1; i < pow[k].size(); i++) {
            pow[k][i] = (pow[k][i - 1] * X[k]) % MOD[k];
        }
    }

    vector<vector<long>> h(2, vector<long>(n + 1));
    vector<int> p(n + 1);
    for (int k = 0; k < 2; k++) {
        p[0] = MAX + 1;
        for (int i = 0; i < n; i++) {
            h[k][i + 1] = h[k][i];
            p[i + 1] = p[i];
            if (s[i] == '+') {
                h[k][i + 1] += pow[k][p[i]];
            } else if (s[i] == '-') {
                h[k][i + 1] -= pow[k][p[i]];
            } else if (s[i] == '>') {
                p[i + 1]++;
            } else if (s[i] == '<') {
                p[i + 1]--;
            }
            h[k][i + 1] %= MOD[k];
            while (h[k][i + 1] < 0) h[k][i + 1] += MOD[k];
        }
    }

//    for (int i = 0; i <= n; i++) {
//        cout << h[i] << " " << p[i] << "\n";
//    }

    long H[2] = {h[0][n] % MOD[0], h[1][n] % MOD[1]};
    map<pair<long, long>, int> mp;
    long res = 0;
    for (int i = n; i >= 0; i--) {
        long a[2], b[2];
        for (int k = 0; k < 2; k++) {
            a[k] = (h[k][i] * pow[k][MAX + 1]) % MOD[k];
            b[k] = (a[k] + H[k] * pow[k][p[i]]) % MOD[k];
        }
        res += mp[{b[0], b[1]}];
        mp[{a[0], a[1]}]++;
    }
    cout << res << "\n";

    return 0;
}

Measured memory_bytes: 44496
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n;
	scanf("%d", &n);
	ll a[200001], s[200001];
	s[0]=0;
	for(int i=1; i<=n; i++){
		scanf("%lld", &a[i]);
		s[i]=s[i-1]+a[i];
	}
	ll ans=1e16;
	for(int i=2; i<=n-2; i++){
		int j=upper_bound(s, s+i+1, s[i]/2)-s;
		int k=upper_bound(s+i+1, s+n+1, s[i]+(s[n]-s[i])/2)-s;
		ll x=max(max(max(s[j], s[i]-s[j]), s[k]-s[i]), s[n]-s[k])-min(min(min(s[j], s[i]-s[j]), s[k]-s[i]), s[n]-s[k]);
		if(x<ans) ans=x;
		x=max(max(max(s[j-1], s[i]-s[j-1]), s[k]-s[i]), s[n]-s[k])-min(min(min(s[j-1], s[i]-s[j-1]), s[k]-s[i]), s[n]-s[k]);
		if(x<ans) ans=x;
		x=max(max(max(s[j], s[i]-s[j]), s[k-1]-s[i]), s[n]-s[k-1])-min(min(min(s[j], s[i]-s[j]), s[k-1]-s[i]), s[n]-s[k-1]);
		if(x<ans) ans=x;
		x=max(max(max(s[j-1], s[i]-s[j-1]), s[k-1]-s[i]), s[n]-s[k-1])-min(min(min(s[j-1], s[i]-s[j-1]), s[k-1]-s[i]), s[n]-s[k-1]);
		if(x<ans) ans=x;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N;
    cin >> N;
    if (N == 0) {
        cout << "0" << endl;
        return 0;
    }
    string S = "";
    while (N != 0) {
        int r = N % (-2);
        N /= (-2);
        if (r < 0) {
            r += 2;
            N += 1;
        }
        S = to_string(r) + S;
    }
    cout << S << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

void print(long A[], long n) {
	for (long i = 0; i < n; i++) {
		if (i != 0) {
			cout << " ";
		}
		cout << A[i];
	}
	cout << endl;
}

long bubbleSort(long A[], long n) {
	long cnt = 0;
	bool flag = true;
	for (long j = n; flag && j > 0; j--) {
		flag = false;
		for (long i = 1; i < j; i++) {
			if (A[i - 1] > A[i]) {
				long v = A[i];
				A[i] = A[i - 1];
				A[i - 1] = v;
				cnt++;
				flag = true;
			}
		}
	}
	return cnt;
}

int main() {
	long n;
	cin >> n;
	long A[n];
	for (long i = 0; i < n; i++) {
		cin >> A[i];
	}
	
	long cnt = bubbleSort(A, n);
	print(A, n);
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<queue>

using std::cout;
using std::cin;
using std::setw;
using std::setfill;
using std::string;
using std::pair;
using std::vector;
using std::queue;
using std::priority_queue;
using std::greater;
using std::max;
using std::min;

using lli = long long int;
using ulli = unsigned long long int;

//#define EVEL 1

#ifndef EVEL
#define dbug(X) std::cout << #X << ":" <<X<<" " ;
#define dbugf(s) std::cout << s << " ";
#define dbugln std::cout<<"\n";
#else
#define dbug(X) {}
#define dbugf(s) {}
#define dbugln {}
#endif

lli X ,t;

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

	cin >> X >> t;
	if(X < t) cout << "0";
	else cout << X - t;
  return 0;
}


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

typedef long long ll;

int main()
{
    int i,j;
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    vector<int> c(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    for(i = 0;i < n;++i){
        cin >> b.at(i);
    }
    for(i = 0;i < n;++i){
        cin >> c.at(i);
    }
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());
    ll ans = 0;
    for(i = 0;i < n;++i){
        ll id_a = lower_bound(a.begin(), a.end(), b.at(i)) - a.begin();
        ll id_c = upper_bound(c.begin(), c.end(), b.at(i)) - c.begin();
        ans += id_a*(n-id_c);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
#define rep(i, start, end) for (long long i = start; i < end; ++i)
#define repreverse(i, start, end) for (long long i = start; i >= end; --i)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define len(x) ((long long)(x).size())
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vllvll = vector<vll>;
using pll = pair<ll, ll>;
template<class T>void print1d(T x,ll n=-1){if(n==-1)n=x.size();rep(i,0,n){cout<<x[i]<<' ';}cout<<'\n';}
template<class T>void print2d(T x,ll r=-1,ll c=-1){if(r==-1)r=x.size();if(c==-1)c=x[0].size();rep(i,0,r)print1d(x[i],c);}
template<class T, class U>bool haskey(T mp, U key) { return mp.find(key) != mp.end(); }
template<class T, class U>bool isin(T el, U container) { return find(all(container), el) != container.end(); }
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<class T>bool even(T n) { return ! (n & 1); }
template<class T>bool odd(T n) { return n & 1; }
template<class T>ld deg2rad(T deg) { return M_PI * deg / 180.0; }
template<class T>ld rad2deg(T rad) { return 180.0 * rad / M_PI; }
ll intpow(ll a,ll n){ll p=1;while(n){if(n&1)p*=a;a*=a;n>>=1;}return p;} 
const long double pi = M_PI;
const long long big = 1LL << 50;
const long long inf = 1LL << 60;
const long long mod = 1e9 + 7;



int main()
{
        ll N;
        cin >> N;
        vll A(N);
        rep(i, 0, N) cin >> A[i];

        map<ll, ll> mp1;
        map<ll, ll> mp2;

        rep(i, 0, N) {
                mp1[i+1+A[i]]++;
                mp2[i+1-A[i]]++;
        }

        ll ans = 0;
        for (auto x : mp1) {
                ans += x.second * mp2[x.first];
        }

        cout << ans << endl;
}

Measured memory_bytes: 38904
// AUTHOR : Kishan Srivastav
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main() {
	ios
#ifndef ONLINE_JUDGE
	in;
	out;
#endif
	int n,k;
	cin>>n;
	map<int,int> m;
	for(int i=0;i<n;i++){
	    cin>>k;
	    m[k]=i+1;
	}
	
	for(auto it:m){
	    cout<<it.second<<' ';
	}


}

Measured memory_bytes: 8344
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
const int MOD = 1000000007;
using ll = long long;
using P = pair<int, int>;

vector<vector<int>> g;

vector<int> dist;
void dfs1(int v, int p = -1){
  for(auto nv : g[v]){
    if(nv == p)continue;
    dfs1(nv, v);
    dist[v] = max(dist[v], dist[nv] + 1);
  }
}

vector<int> ans;
void dfs2(int v, int p = -1, int d_par = 0){
  vector<P> d_ch;
  d_ch.push_back({0, -1});
  for(auto nv : g[v]){
    if(nv == p)d_ch.push_back({d_par + 1, nv});
    else d_ch.push_back({dist[nv] + 1, nv});
  }

  sort(d_ch.rbegin(), d_ch.rend());
  ans[v] = d_ch[0].first;
  for(auto nv : g[v]){
    if(nv == p)continue;
    int flg = d_ch[0].second == nv;
    dfs2(nv, v, d_ch[flg].first);
  }
}

int main(){
  int n;
  cin >> n;
  g.resize(n);
  for(int i = 0; i < n - 1; ++i){
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  dist.assign(n, 0);
  dfs1(0);
  ans.resize(n);
  dfs2(0);
  for(int i = 0; i < n; ++i){
    cout << (n - 1) * 2 - ans[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 27804
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}




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

int a,b;
cin >> a >> b;

if((a+b )% 2 ==0) cout << (a+b) / 2 << endl;
else cout << "IMPOSSIBLE" << endl;

return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().run();
	}

	@SuppressWarnings("unchecked")
	private void run() {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int n = scanner.nextInt();
			int m = scanner.nextInt();
			if ((n | m) == 0)
				break;
			List<Edge>[] lists = new ArrayList[n];
			for (int i = 0; i < n; i++) {
				lists[i] = new ArrayList<Edge>();
			}
			for (int i = 0; i < m; i++) {
				int from = scanner.nextInt() - 1;
				int to = scanner.nextInt() - 1;
				int cost = scanner.nextInt();
				lists[from].add(new Edge(to, cost));
				lists[to].add(new Edge(from, cost));
			}
			int g = n - 1;
			PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
			pq.offer(new Edge(0, 0, 2));
			boolean[][] b = new boolean[n][3];
			while (!pq.isEmpty()) {
				Edge edge = pq.poll();
				if (edge.to == g && edge.ticket != 1) {
					System.out.println(edge.cost);
					break;
				}
				if(b[edge.to][edge.ticket])
					continue;
				b[edge.to][edge.ticket]=true;
				
				for (Edge e : lists[edge.to]) {
					if (edge.ticket == 1) {
						pq.offer(new Edge(e.to, edge.cost, 0));
					} else {
						if (edge.ticket == 2) {
							pq.offer(new Edge(e.to, edge.cost, 1));
						}
						pq.offer(new Edge(e.to, edge.cost + e.cost, edge.ticket));
					}
				}
			}
		}
	}

	class Edge implements Comparable<Edge> {
		int to, cost, ticket;

		public Edge(int to, int cost, int ticket) {
			super();
			this.to = to;
			this.cost = cost;
			this.ticket = ticket;
		}

		public Edge(int to, int cost) {
			super();
			this.to = to;
			this.cost = cost;
		}

		@Override
		public String toString() {
			return "Edge [to=" + to + ", cost=" + cost + ", ticket=" + ticket
					+ "]";
		}

		@Override
		public int compareTo(Edge o) {
			return this.cost - o.cost;
		}

	}
}

Measured memory_bytes: 33416
//#include <tourist>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <string>
#include <iomanip>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <queue>
#include <tuple>
#include <deque>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <utility>
#include <complex>
#include <functional>
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = (1 << 28);
const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0};
const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
//setprecision(15)有効数字15桁
//-std=c++14
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b)
{
    return a * b / gcd(a, b);
}
struct edge {
    int to, cost;
};
ll n, k;
vector<ll> a;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n>>k;

    for (int i = 0; i < n; i++)
    {
        ll temp;
        cin >> temp;
        a.push_back(temp);
    }
    sort(ALL(a));
    if(k>a[n-1]){
        return cout<<"IMPOSSIBLE"<<"\n",0;
    }
    ll g=a[0];
    for(int i=1;i<n;i++){
        g=gcd(g,a[i]);
    }
    if(k%g!=0){
        cout<<"IMPOSSIBLE"<<"\n",0;
    }
    else{
        cout<<"POSSIBLE"<<"\n",0;
    }
}



Measured memory_bytes: 1400
#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;

int main() {
    vector<string> idx2key(0);
    map<string, int> key2idx;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++) {
                idx2key.push_back({ "ACGT"[i], "ACGT"[j], "ACGT"[k] });
                key2idx[{ "ACGT"[i], "ACGT"[j], "ACGT"[k] }] = idx2key.size() - 1;
            }
        }
    }

    int n;
    cin >> n;

    vector<vector<int>> dp(n + 1, vector<int>(idx2key.size(), 0));
    for (int i = 0; i < static_cast<int>(idx2key.size()); i++) {
        if (idx2key[i] != "AGC" && idx2key[i] != "GAC" && idx2key[i] != "ACG") {
            dp[3][i] = 1;
        }
    }

    for (int i = 3; i < n; i++) {
        for (int j = 0; j < static_cast<int>(idx2key.size()); j++) {
            string key = idx2key[j];

            dp[i + 1][key2idx[{ key[1], key[2], 'A' }]] =
                (dp[i + 1][key2idx[{ key[1], key[2], 'A' }]] + dp[i][j]) % 1000000007;
            if ((key[1] != 'A' || key[2] != 'G')
                && (key[1] != 'G' || key[2] != 'A')
                && (key[0] != 'A' || key[2] != 'G')
                && (key[0] != 'A' || key[1] != 'G')) {
                dp[i + 1][key2idx[{ key[1], key[2], 'C' }]] =
                    (dp[i + 1][key2idx[{ key[1], key[2], 'C' }]] + dp[i][j]) % 1000000007;
            }
            if (key[1] != 'A' || key[2] != 'C') {
                dp[i + 1][key2idx[{ key[1], key[2], 'G' }]] =
                    (dp[i + 1][key2idx[{ key[1], key[2], 'G' }]] + dp[i][j]) % 1000000007;
            }
            dp[i + 1][key2idx[{ key[1], key[2], 'T' }]] =
                (dp[i + 1][key2idx[{ key[1], key[2], 'T' }]] + dp[i][j]) % 1000000007;
        }
    }

    int cnt = 0;
    for (int i = 0; i < static_cast<int>(idx2key.size()); i++) {
        cnt = (cnt + dp[n][i]) % 1000000007;
    }

    cout << cnt << endl;
}


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

using namespace std;
//using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0;i < (ll)n;i++)
#define ALL(x) (x).begin(),(x).end()
#define MOD 1000000007

const int mod = 998244353;

template<typename T>
class BIT{
  public:
  vector<T> s;
  const int n;
  BIT (int n_):s(n_+1,0),n(n_){}
  //[0,i],1-index
  T sum(T i){
    if(i == 0)return 0;
    T k = 0;
    while(i > 0){
      (k += s[i])%= mod;
      i -= i & (-i);
    }
    return k;
  }
  //[l,r],1-index
  T sum(int l,int r){
    return (sum(r)-sum(l-1)+mod)%mod;
  }
  // 1-index
  void add(int pos,T val){
    while(pos <= n){
      (s[pos] += val)%= mod;
      pos += pos & (-pos);
    }
  }
  int lower_bound(T k){
    int len = 1;
    while(len < n)len <<= 1;
    int l = 0;
    T x = 0;
    for(;len > 0;len >>= 1){
      if(l+len <= n && s[l+len]+x < k)x += s[l+len],l += len;
    }
    return l+1;
  }
};

int main(){
  
  int n,k;
  cin >> n >> k;
  vector<P> v(k);
  rep(i,k)cin >> v[i].first >> v[i].second;
  sort(ALL(v));
  BIT<ll> bit(n);
  for(int i = 1;i <= n;i++){
    rep(j,k){
      if(v[j].second <= i){
        bit.add(i,bit.sum(i-v[j].second,i-v[j].first));
      }else if(v[j].first <= i){
        bit.add(i,bit.sum(0,i-v[j].first));
      }
      if(v[j].first <= i && v[j].second >= i)bit.add(i,1);
    }
  }
  cout << bit.sum(n-1,n-1) << "\n";


  return 0;
}

Measured memory_bytes: 4784
"use strict";
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill(0).map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill(0).map(x=>"+r+")";return eval(r);}
function upper_bound(d,a,b,e){for(var c;1<b-a;)d[c=a+b>>1]<=e?a=c:b=c;return d[a]<=e?b:a};

console.log(main());
function main(){
  var n = o.a();
  var s = o.a(1);
  var ans = 0;
  var id = xArray("[]",10);
  for(var i = 0; i < n; i++){
    id[s[i]].push(i);
  }
  for(var i = 0; i < 10; i++){
    id[i].push(n);
  }
  for(var i = 0; i < 1000; i++){
    var a = i/100|0;
    var b = Math.floor(i/10)%10;
    var c = i%10;
    var x1 = id[a][0];
    if(x1 === n)continue;
    var x2 = upper_bound(id[b],0,id[b].length,x1);
    x2 = id[b][x2];
    if(x2 === n)continue;
    var x3 = upper_bound(id[c],0,id[c].length,x2);
    x3 = id[c][x3];
    if(x3 === n)continue;
    ans++;
  }
  return ans;
}

Measured memory_bytes: 7884
#include <algorithm>  // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <bitset>     // bitset
#include <cctype>     // isupper, islower, isdigit, toupper, tolower
#include <cstdint>    // int64_t, int*_t
#include <cstdio>     // printf
#include <deque>      // deque
#include <iomanip>    // fixed, setprecision
#include <iostream>   // cout, endl, cin
#include <map>        // map
#include <numeric>    // accumulate
#include <queue>      // queue, priority_queue
#include <set>        // set
#include <stack>      // stack
#include <string>     // string, to_string, stoi
#include <tuple>      // tuple, make_tuple
#include <unordered_map>  // unordered_map
#include <unordered_set>  // unordered_set
#include <utility>        // pair, make_pair
#include <vector>         // vector
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main() {
  ll N, a, mi = INT32_MAX, ma = -1;
  cin >> N;
  for (ll i = 0; i < N; i++) {
    cin >> a;
    mi = min(mi, a);
    ma = max(ma, a);
  }
  cout << ma - mi << endl;
}


Measured memory_bytes: 3124
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  int N;
  cin >> N;
  int p[N];
  for(int i = 0; i < N; i++) cin >> p[i];

  int ans = 0;
  for(int i = 0; i < N - 2; i++){
    int a[3];
    a[0] = p[i];
    a[1] = p[i+1];
    a[2] = p[i+2];
    sort(a, a + 3);
    if(a[1] == p[i+1]){
      ans++;
    }
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sp ' '
#define nyan "(=^・ω・^=)"
#define mkp make_pair
#define intmax 2147483647
#define llmax 9223372036854775807
#define lP pair<ll,ll>
#define iP pair<int,int>
typedef long long ll;
using namespace std;
const ll mod = 1000000007;
const int mod998 = 998244353;

int N;
ll L, res;
string S;
set<ll>st;

void dfs(ll x, int y) {
	if (y != L) {
		if (st.find((x * 3 + 1) % mod+mod*y) == st.end()) {
			if (st.find((x * 3 + 2) % mod+mod*y) != st.end()) {
				res ^= ((L - y)&-(L - y));
				dfs((x * 3 + 2) % mod, y + 1);
			}
		}
		else if (st.find((x * 3 + 2) % mod + mod * y) == st.end()) {
			res ^= ((L - y)&-(L - y));
			dfs((x * 3 + 1) % mod, y + 1);
		}
		else {
			dfs((x * 3 + 1) % mod, y + 1);
			dfs((x * 3 + 2) % mod, y + 1);
		}
	}
}

int main() {
	cin >> N >> L;
	while (N--) {
		cin >> S;
		ll t = 0;
		for (int i = 0; i < S.size(); ++i) {
			t *= 3;
			t += S[i] - '0' + 1;
			t %= mod;
			st.insert(t + mod * i);
		}
	}
	dfs(0, 0);
	if (res)
		cout << "Alice" << endl;
	else
		cout << "Bob" << endl;
	return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B;
string S, T;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
typedef pair<ll, ll> P;

int main() {
    cin>>S;
    bool yes = true;
    rep(i,S.size()){
        if(S[i] != (i&1 ? 'i' : 'h')) yes = false;
    }
    cout<<(yes && S.size()%2 == 0 ? "Yes" : "No")<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

int main() {
	int a;
	std::cin >> a;

	for (int i = 1; i < 10; ++i) {
		for (int j = 1; j < 10; ++j) {
			if (a == i * j) {
				std::cout << "Yes" << std::endl;
				return 0;
			}
		}
	}

	std::cout << "No" << std::endl;
}

Measured memory_bytes: 256