akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dfs(ll node, vector<ll>& fg, const multimap<ll, ll>& ABm, ll group_no)
{
    if (fg[node] != 0) {
        return 0;
    }
    fg[node] = group_no;

    ll num = 1;
    auto r = ABm.equal_range(node);
    for (auto r = ABm.equal_range(node); r.first != r.second; r.first++) {
        num += dfs(r.first->second, fg, ABm, group_no);
    }
    return num;
}

void main_()
{
    ll N, M, K;
    cin >> N >> M >> K;
    multimap<ll, ll> ABm;
    for (ll i = 0; i < M; i++) {
        ll A, B;
        cin >> A >> B;
        ABm.emplace(A, B);
        ABm.emplace(B, A);
    }
    multimap<ll, ll> CDm;
    for (ll i = 0; i < K; i++) {
        ll C, D;
        cin >> C >> D;
        CDm.emplace(C, D);
        CDm.emplace(D, C);
    }

    vector<ll> fg(N + 1); // 1-origin

    map<ll, ll> group_num_m;
    for (ll i = 1; i <= N; i++) {
        if (fg[i] == 0) {
            auto num = dfs(i, fg, ABm, i);
            group_num_m[i] = num;
        }
    }

    for (ll i = 1; i <= N; i++) {
        ll ans = group_num_m[fg[i]] - 1; // 自分を含む友達グループから自分を引いた数
        auto it = ABm.equal_range(i);
        ans -= distance(it.first, it.second); // 自分と直接友達関係を除く

        for (auto it = CDm.equal_range(i); it.first != it.second; it.first++) {
            auto block_i = it.first->second;
            if (fg[i] == fg[block_i]) {
                // ブロック関係の相手が友達グループに含まれていたらその分を除く
                ans--;
            }
        }
        cout << ans << " ";
    }
    cout << "\n";
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 32512
#include<cstdio>
#include<functional>
#include<algorithm>
#include<queue>
#define MM 2100000000
using namespace std;
typedef pair<int,int> P;
P px[200001],py[200001],p1;
int main(void)
{
	int n,d,i,j,x,y,b,bb,x1,x2,y1,y2;
	long long s,mx;
	priority_queue<P> qxmx,qymx;
	priority_queue<P, vector<P> ,greater<P> > qxmn,qymn;
	scanf("%d %d",&n,&d);
	for(i=0;i<n;i++)	{
		scanf("%d %d %d",&x,&y,&b);
		px[i].first=b;	px[i].second=x;
		py[i].first=b;	py[i].second=y;
	}
	px[n].first=MM;	px[n].second=MM;
	py[n].first=MM;	py[n].second=MM;
	sort(px,px+n+1);
	sort(py,py+n+1);
//	for(i=0;i<n+1;i++)	printf("%d %d\n",px[i].first,px[i].second);
	j=0;
	while(1)	{
		if(px[j].first<=px[0].first+d)	{
			qxmn.push(P(px[j].second,px[j].first));
			qymn.push(P(py[j].second,py[j].first));
			qxmx.push(P(px[j].second,px[j].first));
			qymx.push(P(py[j].second,py[j].first));
			j++;
		}
		else {
			break;
		}
	}
	p1=qxmn.top();	x1=p1.first;
	p1=qymn.top();	y1=p1.first;	
	p1=qxmx.top();	x2=p1.first;
	p1=qymx.top();	y2=p1.first;	
	mx=(long long)(x2-x1)*(y2-y1);
	for(i=1;i<n;i++)	{
		while(qxmn.size()!=0)	{
			p1=qxmn.top();	
			if(p1.second<px[i].first)	qxmn.pop();
			else break;
		}
		while(qymn.size()!=0)	{
			p1=qymn.top();	
			if(p1.second<py[i].first)	qymn.pop();
			else break;
		}		
		while(qxmx.size()!=0)	{
			p1=qxmx.top();	
			if(p1.second<px[i].first)	qxmx.pop();
			else break;
		}	
		while(qymx.size()!=0)	{
			p1=qymx.top();	
			if(p1.second<py[i].first)	qymx.pop();
			else break;
		}	
		while(1)	{
			if(px[j].first<=px[i].first+d)	{
				qxmn.push(P(px[j].second,px[j].first));
				qymn.push(P(py[j].second,py[j].first));
				qxmx.push(P(px[j].second,px[j].first));
				qymx.push(P(py[j].second,py[j].first));
				j++;
			}
			else {
				break;
			}
		}
		p1=qxmn.top();	x1=p1.first;
		p1=qymn.top();	y1=p1.first;	
		p1=qxmx.top();	x2=p1.first;
		p1=qymx.top();	y2=p1.first;	
		mx=max(mx,(long long)(x2-x1)*(y2-y1));
	}	
	printf("%lld\n",mx);
	return 0;
}


Measured memory_bytes: 11904
import math
n, m, k = map(int, input().split())

mod = 10**9 + 7

def mpow(x, n):
  ans = 1
  while n != 0:
    if n&1:
      ans = ans * x % mod
    x = x * x % mod
    n = n // 2
  return ans

fac = [0] * (n*m+2)
finv = [0] * (n*m+2)
inv = [0] * (n*m+2)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1

for i in range(2, n*m+1):
  fac[i] = fac[i-1] * i % mod
  inv[i] = mod - inv[mod%i] * (mod // i) % mod
  finv[i] = finv[i-1] * inv[i] % mod

def choose(n,k):
  if n == 0 and k == 0:
    return 1
  if n < 0:
    return 0
  if n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod


sum = 0
for i in range(1, n+1):
  for j in range(1, m+1):
    score = i-1 + j-1
    cnt = (n-i+1) * (m-j+1)
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

for i in range(2, n+1):
  for j in range(1, m):
    score = i-1 + m-j
    cnt = (n-i+1) * j
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

sum = sum * choose(m*n-2,k-2)
sum = sum % mod
print(sum)



Measured memory_bytes: 28116
mod=pow(10,5)+2
N=int(input())
num=[0]*mod
ans=0
A=list(map(int, input().split()))
for i in range(N):
    num[A[i]]+=1
    ans+=A[i]
Q=int(input())
for i in range(Q):
    B,C=map(int, input().split())
    cnt=num[B]
    num[C]+=num[B]
    num[B]=0
    ans+=(C-B)*cnt
    print(ans)

Measured memory_bytes: 21832
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		var E = new List<int>[N];
		for(int i=0;i<N;i++){
			E[i] = new List<int>();
		}
		for(int i=0;i<N-1;i++){
			E[i].Add(i + 1);
			E[i + 1].Add(i);
		}
		E[X].Add(Y);
		E[Y].Add(X);
		
		int[] ans = new int[N];
		
		for(int i=0;i<N;i++){
			
			var q = new Queue<int>();
			q.Enqueue(i);
			var min = new int[N];
			for(int j=0;j<N;j++) min[j] = -1;
			min[i] = 0;
			while(q.Count > 0){
				var now = q.Dequeue();
				foreach(var nxt in E[now]){
					if(min[nxt] == -1){
						min[nxt] = min[now] + 1;
						q.Enqueue(nxt);
					}
				}
			}
			
			for(int j=i+1;j<N;j++){
				ans[min[j]]++;
			}
		}
		
		for(int j=1;j<=N-1;j++){
			Console.WriteLine(ans[j]);
		}
		
	}
	int N, X, Y;
	public Sol(){
		var d = ria();
		N = d[0]; X = d[1] - 1; Y = d[2] - 1;
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 29280
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<iomanip>
#include<stack>
#include<string.h>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define sz(a) (int)a.size()
using namespace std;

ll inf = 1e9 + 7;

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

const int MAX = 2000100;
const int MOD = 1000000007;


long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    // 前処理
    COMinit();
    int k;
    cin >> k;
    string s;
    cin >> s;
    int a = sz(s);
    ll ans = 0;
    rep(i, k + 1) {
        ll ansi = COM(a + k - 1 - i,a - 1);
        ansi *= modpow((ll)25, ll(k - i), inf);
        ansi %= inf;
        ansi *= modpow((ll)26, (ll)i, inf);
        ansi %= inf;
        ans += ansi;
        ans %= inf;
    }
    cout << ans << endl;
}


Measured memory_bytes: 52208
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);
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 (a > b) { a = b; return true; } return false; }

struct Node {
	int v;
	Node *p, *l, *r;
};

Node *root;

void insert(int v) {
	Node *p = root;
	Node *u = (Node *)malloc(sizeof(Node));
	u->v = v;
	u->l = u->r = nullptr;
	while (p != nullptr) {
		u->p = p;
		if (u->v < p->v)
			p = p->l;
		else
			p = p->r;
	}
	if (p == root)
		root = u;
	else {
		if (u->v < u->p->v)
			u->p->l = u;
		else
			u->p->r = u;
	}
}

Node *find(Node *u, int v) {
	while (u != nullptr && v != u->v) {
		if (v < u->v)
			u = u->l;
		else
			u = u->r;
	}
	return u;
}

void inorder(Node *u) {
	if (u == nullptr)return;
	inorder(u->l);
	cout << ' ' << u->v;
	inorder(u->r);
}

void preorder(Node *u) {
	if (u == nullptr)return;
	cout << ' ' << u->v;
	preorder(u->l);
	preorder(u->r);
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	rep(i, 0, n) {
		string com;
		cin >> com;
		if (com[0] == 'i') {
			int key; cin >> key;
			insert(key);
		}
		else if (com[0] == 'f') {
			int key; cin >> key;
			if (find(root, key))cout << "yes" << endl;
			else cout << "no" << endl;
		}
		else {
			inorder(root); cout << endl;
			preorder(root); cout << endl;
		}
	}
	return 0;
}

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

using namespace std;

int main() {
	string a, b;
	cin >> a >> b;
	if ((a == "H"&&b == "H") || (a == "D"&&b == "D")) {
		cout << "H" << endl;
	}
	else {
		cout << "D" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
n = int(input())
dic1 = {}
for i in range(n):
  temp = input()
  dic1.setdefault(temp, 0)
  dic1[temp] += 1
m = int(input())
for i in range(m):
  temp = input()
  dic1.setdefault(temp, 0)
  dic1[temp] -= 1
print(max(0, max(list(dic1.values()))))

Measured memory_bytes: 9108
def zerofill(s):
    return '0'*(6-len(s)) + s

n, m = map(int, input().split())
list = []
for i in range(m):
    p, y = map(int, input().split())
    list.append([p, y, i])
num = ['']*m # 認識番号
list.sort()
cnt = 0
p = 1
for v in list:
    if(v[0]!=p):
        p = v[0]
        cnt = 1
    else:
        cnt += 1
    num[v[2]] = zerofill(str(v[0])) + zerofill(str(cnt))
for val in num:
    print(val)


Measured memory_bytes: 31308
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
#ifdef DAIJOBU
#include "/home/v-o_o-v/deb.h"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif 

using namespace std;

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef long long lint;
typedef double ld;

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

	int n, m;
	cin >> n >> m;
	char grid[n][m];
	forn(i, n){
		forn(j, m)cin >> grid[i][j];
	}
	forn(i, n){
		forn(k, 2){
			forn(j, m)cout << grid[i][j];
			cout << '\n';
		}
	}
	return 0;
}
// Write Here



Measured memory_bytes: 256
N,M,K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)

max = 0

a = [0]
b = [0]
A.each_with_index do |n,i|
  a << a[i] + n
end
B.each_with_index do |n,i|
  b << b[i] + n
end

ans = 0
j = M

0.upto(N) do |i|
  if a[i] > K
    break
  end

  while b[j] > K - a[i] do
    j -= 1
  end
  c = i + j
  ans = c if c > ans
end

puts ans


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

int main() {
    int n;
    std::string s, t;
    std::cin >> n >> s >> t;
    for (int i = 0; i < n; i++) {
        bool flg = true;
        for (int j = 0; j < n - i; j++) {
            flg = flg && s[i + j] == t[j];
        }
        if (!flg) continue;

        std::cout << i + n << std::endl;
        return 0;
    }
    std::cout << 2 * n << std::endl;

    return 0;
}

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

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

int _ = (
#ifndef LOCAL
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false),
#endif
    std::cout.precision(10), std::cout.setf(std::ios::fixed));

using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T> using vec = std::vector<T>;
using namespace std;

int main() {
  string S;
  cin >> S;

  const string pat = "^A[a-z](?:[a-z]*C[a-z]*)[a-z]$";
  regex re(pat);
  cout << (regex_match(S, re) ? "AC" : "WA") << endl;
  return 0;
}


Measured memory_bytes: 3808
N = int(input())

l0 = 2
l1 = 1

if (N == 1):
    ans = 1
else:
    before = l0
    middle = l1
    
    for i in range(N - 1):
        nextt = before + middle
        before = middle
        middle = nextt
    
    ans = nextt

print(ans)


Measured memory_bytes: 9164
function checkStable(arr) {

}
function bubbleSort(lgh, arr) {
  var flag = 1;
  var count = 0;
  while(flag) {
    flag = 0;
    for(let i = 0; i < lgh-1; i++) {
      if(Number(arr[i][1]) > Number(arr[i+1][1])) {
        [arr[i], arr[i+1]] = [arr[i+1], arr[i]];
        flag = 1;
        count++;
      }
    }
  }
  console.log(arr.join(" "));
  return "Stable";
}
function selectionSort(lgh, arr) {
  var count = 0;
  for(let i = 0; i < lgh-1; i++) {
    var tmp = i;
    for(let j = i; j < lgh; j++) {
      if(Number(arr[j][1]) < Number(arr[tmp][1])) {
        tmp = j;
      }
    }
    if(i != tmp) {
      [arr[i], arr[tmp]] = [arr[tmp], arr[i]];
      count++;
    }
  }
  console.log(arr.join(" "));
}
function Main(input) {
  var [a, b] = input.split("\n");
  s = b.split(" ");
  b = b.split(" ");
  console.log(bubbleSort(a, b));
  selectionSort(a, s);
  console.log(s.join() === b.join() ? "Stable" : "Not stable");
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));



Measured memory_bytes: 16060
#include <stdio.h>
#include <stdlib.h>
#define p (int)(1e9 + 7)

int main(){
	int N, i, j, maxq = 0;
	scanf("%d", &N);
	int *q = (int *)malloc(sizeof(int) * N);
	for(i = 0; i < N; i++){
		scanf("%d", &q[i]);
		if(q[i] > maxq){
			maxq = q[i];
		}
	}
	int *is_prime = (int *)malloc(sizeof(int) * (maxq + 1));
	for(i = 0; i <= maxq; i++){
		is_prime[i] = 1;
	}
	for(i = 2; i <= maxq; i++){
		if(is_prime[i] == 1){
			for(j = 2; i * j <= maxq; j++){
				is_prime[i * j] = 0;
			}
		}
	}
	if(N == 1){
		if(is_prime[q[0]] == 1){
			printf("1\n");
		}
		else{
			printf("0\n");
		}
		return 0;
	}
	int *dp1 = (int *)malloc(sizeof(int) * N);
	int *dp2 = (int *)malloc(sizeof(int) * N);
	dp1[0] = is_prime[q[0]] == 1 ? 1 : 0;
	dp2[0] = 0;
	dp1[1] = (is_prime[q[1]] == 1 && q[0] < q[1]) ? dp1[0] : 0;
	dp2[1] = dp1[0];
	for(i = 2; i < N; i++){
		dp1[i] = 0;
		if(is_prime[q[i]] == 1){
			if(q[i - 1] < q[i]){
				dp1[i] += dp1[i - 1];
			}
			if(q[i - 2] < q[i]){
				dp1[i] += dp2[i - 1];
			}
		}
		dp1[i] %= p;
		dp2[i] = dp1[i - 1];
	}
	printf("%d\n", (dp1[N - 1] + dp2[N - 1]) % p);
	return 0;
}


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

#define ll long long int
ll mod=1000000007;
int main(){
	ll n,k;
	cin>>n>>k;
	ll arr[n+1][n+1];
	ll ans[n+1][n+1];
	ll mrr[n+1][n+1];
	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++){
			cin>>arr[i][j];
			ans[i][j]=0;
			mrr[i][j]=0;
		}
		ans[i][i]=1;
	}
	
//	ll ans[n+1][n+1];
	
	while(k>0){
		if((k&1)){
			for(ll i=0;i<n;i++){
				for(ll j=0;j<n;j++){
					for(ll k=0;k<n;k++){
						mrr[i][j]=(mrr[i][j]+ans[i][k]*arr[k][j])%mod;
					}
				}
			}
			for(ll i=0;i<n;i++){
				for(ll j=0;j<n;j++){
				//	cout<<mrr[i][j]<<' ';
					ans[i][j]=mrr[i][j];
					mrr[i][j]=0;
				}
				//cout<<'\n';
			}
		}
		
		for(ll i=0;i<n;i++){
				for(ll j=0;j<n;j++){
					for(ll k=0;k<n;k++){
						mrr[i][j]=(mrr[i][j]+arr[i][k]*arr[k][j])%mod;
					//	cout<<i<<' '<<k<<' '<<arr[i][k]<<'\n';
					}
				}
			}
		//	cout<<"helloooooooooo "<<k<<'\n';
			for(ll i=0;i<n;i++){
				for(ll j=0;j<n;j++){
				//	cout<<mrr[i][j]<<' ';
					arr[i][j]=mrr[i][j];
					mrr[i][j]=0;
				}
				//cout<<'\n';
			}
		//	cout<<"======================================\n";
		
		k/=2;
		
	}
	ll ansn=0;
	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++){
			ansn=(ansn+ans[i][j])%mod;
		}
	}
	
	cout<<ansn;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
const int MAXN = (1 << 20);
const int mod = (int)1e9 + 7;
const int64_t inf_time = 2e9 + 7 + 42;

template<class T>
struct fenwick
{
    int sz;
    T tr[MAXN];

    void init(int n) { for(int i = 0; i <= n + 2; i++) tr[i] = 0; sz = n + 2; }

    T query(int x)
    {
        x++;
        if(x == 0) return 0;
        T ans = 0;
        for(; x > 0; x -= (x & -x))
            ans = (ans + tr[x] >= mod) ? (ans + tr[x] - mod) : (ans + tr[x]);
        return ans;
    }

    void update(int x, T val)
    {
        x++;
        if(x == 0) return;
        for(; x <= sz; x += (x & -x))
            tr[x] = (tr[x] + val >= mod) ? (tr[x] + val - mod) : (tr[x] + val);
    }

    T query(int l, int r) { return (query(r) - query(l - 1) + mod) % mod; }
};


int n;
pair<int, int> p[MAXN];

void read()
{
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> p[i].first >> p[i].second;
}

int pos[MAXN], low[MAXN], high[MAXN];
pair<int64_t, int> a[MAXN];

fenwick<int> t;

void solve()
{
    sort(p, p + n);
    for(int i = 0; i < n; i++) a[i] = {p[i].first + p[i].second * 1ll * inf_time, i}; sort(a, a + n);
    for(int i = 0; i < n; i++) pos[i] = lower_bound(a, a + n, make_pair((int64_t)(p[i].first + p[i].second * 1ll * inf_time), i)) - a;

    for(int i = 0; i < n; i++)
        if(i > 0) low[i] = max(pos[i], low[i - 1]);
        else low[i] = pos[i];

    for(int i = n - 1; i >= 0; i--)
        if(i < n - 1) high[i] = min(pos[i], high[i + 1]);
        else high[i] = pos[i];

    t.init(n + 1);
    t.update(0, 1);

    for(int i = 0; i < n; i++)
    {
        int x = t.query(high[i], low[i] + 1);
        t.update(low[i] + 1, x);
    }

    cout << t.query(n, n) << endl;
}

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

	read();
	solve();
	return 0;
}


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

namespace CS.Solve1
{
    class Program
    {
        static void Main(string[] args)
        {
            var NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            var givenN = NM[0];
            var givenM = NM[1];
            var Cities = new List<int[]>();
            for(var i = 0; i < givenM; i++)
            {
                var tmp = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
                Cities.Add(new int[] { tmp[0], tmp[1], i, 0 });
            }
            var OrderedCities = Cities.OrderBy(x => x[0]).ThenBy(x => x[1]).ToArray();
            OrderedCities[0][3] = 0;
            var rank = 0;
            var tmpPrefecture = OrderedCities[0][0];
            foreach(var tmp in OrderedCities.Skip(1))
            {
                if (tmp[0] == tmpPrefecture)
                {
                    rank++;
                    tmp[3] = rank;
                }
                else
                {
                    rank = 0;
                    tmp[3] = 0;
                    tmpPrefecture = tmp[0];
                }
            }
            foreach(var tmp in OrderedCities.OrderBy(x => x[2]))
            {
                Console.WriteLine("{0:000000}{1:000000}", tmp[0], tmp[3] + 1);
            }
        }
    }
}


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

int main() {
  string s, t;
  cin >> s >> t;
  int ls = s.size();
  int lt = t.size();
  vector<vector<int>> dp(ls+1, vector<int>(lt+1));
  rep(i, ls+1) rep(j, lt+1) {
    if (i == 0 || j == 0) continue;
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    if (s[i-1] == t[j-1]) dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
  }
  int l = dp[ls][lt];
  string ans = "";
  int i = ls, j = lt;
  while (l) {
    while (dp[i-1][j] == l) --i;
    while (dp[i][j-1] == l) --j;
    ans += s[i-1];
    --i; --j; --l;
  }
  reverse(ans.begin(), ans.end());
  cout << ans << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	string s;
	ll k;
	cin>>s>>k;
	int n=s.size();
	if(n==1){
		ll ans=k/2;
		cout<<ans<<'\n';
		return 0;
	}
	int cnt=0;
	REP(i, n-1){
		if(s[i]==s[i+1]){
			++i;
			++cnt;
		}
	}
	int a=n-1;
	REP(i, n-1){
		if(s[i]!=s[i+1]){
			a=i;
			break;
		}
	}
	int b=-1;
	FORR(i, 0, n-1){
		if(s[i]!=s[i+1]){
			b=i;
			break;
		}
	}
	++a;
	b=n-b-1;
	// DEBUG(a);
	// DEBUG(b);
	if(a==n){
		if(a>1 && a&1){
			ll ans=(cnt*2+1)*k/2;
			cout<<ans<<'\n';
			return 0;
		}
	}
	ll ans=cnt*k;
	if(s[0]==s[n-1] && a>1 && b>1 && a&1 && b&1){
		ans+=k-1;
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define FIR first
#define SEC second
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

typedef int Flow;
struct Edge{
  int src;int dst;int rev;
  Flow cap;
  Edge(int s=0,int d=0,Flow c=0,int r=0):
  src(s),dst(d),cap(c),rev(r){}
};

using Graph = vector<vector<Edge>>;
Graph g;
bool used[101];
void add(int src,int dst,int cap){
  g[src].emplace_back(src,dst,cap,g[dst].size());
  g[dst].emplace_back(dst,src,0,g[src].size()-1);
}

int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  REP(i,g[v].size()){
    Edge &e=g[v][i];
    if(!used[e.dst]&&e.cap>0){
      int d=dfs(e.dst,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        g[e.dst][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}

signed main(){
  int V,E;
  cin>>V>>E;
  g=Graph(V);
  REP(i,E){
    int u,v,c;
    cin>>u>>v>>c;
    add(u,v,c);
  }
  int ans=0;
  for(;;){
    fill(used,used+V,0);
    int f=dfs(0,V-1,INF);
    if(!f)break;
    ans+=f;
  }
  cout<<ans<<endl;
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  
  double ans = 0;
  for (int i = 0; i < N; i++) {
    double x;
    string u;
    cin >> x >> u;
    
    if (u == "JPY") {
      ans += x;
    } else {
      ans += x * 380000.0;
    }
  }
  
  cout << fixed << setprecision(6) << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
p = [int(x) for x in input().split()]
dif = 0
for i in range(n):
    if p[i] != i + 1:  # 並び替えはせず、インデックスとの比較でOK
        dif += 1
if dif == 0 or dif == 2:
    print('YES')
else:
    print('NO')

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

long long n,m;
char S[100010],T[100010];

long long gcd(long long x,long long y)
{
	if (x%y==0) return y;
	return gcd(y,x%y);
}

int main()
{
	scanf("%d %d",&n,&m);
	scanf("%s",S);scanf("%s",T);
	long long GCD=gcd(n,m);
	long long LCM=n*m/GCD;
	if (S[0]!=T[0]) {printf("-1");return 0;}
	if (GCD==1) {printf("%lld",LCM);return 0;}
	long long ds=LCM/m,dt=LCM/n;
	long long i=0,j=0;
	while (i<n && j<m)
	{
		if (S[i]!=T[j]) {printf("-1");return 0;}
		i+=ds,j+=dt;
	}
	printf("%lld",LCM);
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n) f2or (int i = 1; i < (n); ++i)
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int num[5], k;
    rep(i,5) {
        cin >> num[i];
    }
    cin >> k;

    if(num[4] - num[0] <= k) cout << "Yay!"<< endl;
    else cout << ":(" << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
#define MAXN 5000
LL ksm(LL p, LL q)
{
    LL ret = 1LL;
    while(q != 0){
        if (q & 1) 
			ret = ret * p % mod;
        p = p * p % mod;
        q >>= 1;
    }
    return ret;
}
LL dp[MAXN+5][MAXN+5];
int main()
{
	LL N, len;
	string p;
	cin>>N>>p;
	len = p.size();
	dp[0][0] = 1;
	for(int i=0; i<=MAXN; i++)
	{
		for(int j=0; j<=i; j++)
		{
			dp[i+1][j+1] = (dp[i][j] * 2 % mod + dp[i+1][j+1]) % mod;
			dp[i+1][j-1>0?j-1:0] = (dp[i][j] % mod + dp[i+1][j-1>0?j-1:0] % mod) % mod;
		}
	}
	LL ans = ksm(ksm(2, len), (mod - 2)) * dp[N][len] % mod;
	printf("%lld", ans);
}

Measured memory_bytes: 194048
#include <iostream>

using namespace std;

const int N = 501;
const int C = 31;

int initialColor[N][N];
int cost[C][C];
int sum_cost[3][C];

int main()
{
    int n, c;
    cin >> n >> c;
    
    for(int i=0;i<c;++i)
    {
        for(int j=0;j<c;++j)
        {
            cin >> cost[i][j];
        }
    }

    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            cin >> initialColor[i][j];
        }
    }



    int ans = 1 << 30;

    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            for(int ind=0;ind<c;++ind)
            {
                sum_cost[(i+j)%3][ind] += cost[initialColor[i][j] - 1][ind];
            }
        }
    }

    for(int i=0;i<c;++i)
    {
        for(int j=0;j<c;++j)
        {
            for(int k=0;k<c;++k)
            {
                if(i == j || j == k || i == k) continue;

                ans = min(ans, sum_cost[0][i] + sum_cost[1][j] + sum_cost[2][k]);
            }
        }        
    }
    cout << ans << endl;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int n,m,ans;
string s,t;

int gcd(int n,int m) {
		if (m==0) return n;
		return gcd(m,n%m);
}

int main() {
		ios_base::sync_with_stdio(0); cin.tie(0);
		cin>>n>>m;
		cin>>s; cin>>t;
		int g = gcd(n,m);
		for (int i=0;i<g;i++) {
				int x = n/g*i;
				int y = m/g*i;
				if (s[x]!=t[y]) {
						cout<<-1;
						return 0;
				}
		}
		cout<<1ll*n*m/g<<endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=505;
const long long INF=4557430888798830399;
int n;
long long a[N][N];
long long s1[N][N],s2[N][N];
long long f[N][N];
long long calc1(int l1,int r1,int l2,int r2)
{
	swap(l1,l2);
	swap(r1,r2);
	if(l1>r1) return 0;
	if(l2>r2) return 0;
//	cerr<<"Calc1"<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" res:"<<s1[r1][r2]<<"\n";
	return s1[r1][r2]-s1[l1-1][r2]-s1[r1][l2-1]+s1[l1-1][l2-1];
}
long long calc2(int l1,int r1,int l2,int r2)
{
	if(l1>r1) return 0;
	if(l2>r2) return 0;
//	cerr<<"Calc-1"<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<" res:"<<s2[r1][r2]-s2[l1-1][r2]-s2[r1][l2-1]+s2[l1-1][l2-1]<<"\n";
	return s2[r1][r2]-s2[l1-1][r2]-s2[r1][l2-1]+s2[l1-1][l2-1];
}
int main()
{
//	freopen("data.in","r",stdin);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j) scanf("%lld",&a[i][j]);
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=n;j++)
//			printf("%lld ",a[i][j]);
//		printf("\n");
//	}
	for(int i=1;i<=n+1;i++)
		for(int j=1;j<=n+1;j++)
		{
			s1[i][j]=s1[i-1][j]+s1[i][j-1]-s1[i-1][j-1];
			if(i>j) s1[i][j]+=a[i][j];
			s2[i][j]=s2[i-1][j]+s2[i][j-1]-s2[i-1][j-1];
			if(i<j) s2[i][j]+=a[i][j];
		}
//	for(int i=1;i<=n+1;i++)
//	{
//		for(int j=1;j<=n+1;j++)
//			printf("%lld ",s1[i][j]);
//		printf("\n");
//	}
	memset(f,63,sizeof(f));
	f[0][0]=0;
	for(int i=0;i<=n;i++)
		for(int j=i;j<=n;j++)
			if(f[i][j]<INF)
				for(int k=j+1;k<=n+1;k++)

					{
						long long t=calc1(i+1,j,k+1,n+1)+calc2(j+1,k,j+1,k);
						f[j][k]=min(f[j][k],f[i][j]+t);
//						cerr<<"f"<<i<<" "<<j<<" "<<f[i][j]<<" ccc"<<" "<<t<<" "<<"to "<<j<<" "<<k<<" "<<f[j][k]<<"\n";
					}
	long long res=INF;
	for(int i=0;i<=n;i++)
		res=min(res,f[i][n+1]);
	printf("%lld",res);
	return 0;
}


Measured memory_bytes: 11764
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(INF)
#define INF 1e17
#define int ll
#define EPS (1e-6)
using namespace std;
using ll=long long;
using pii=pair<int,int>;

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }

int fpow(int b,int p)
{
	if(p==0) return 1;
	int h=fpow(b,p/2);
	if(p%2) return h*b%MOD*h%MOD;
	return h*h%MOD;
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n; cin>>n;
	string s; cin>>s;
	if(n>=3200) cout<<s<<"\n";
	else cout<<"red\n";
	return 0;
}




























Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  sort(s.begin(),s.end());
  bool ok=true;
  for(int i=0;i<s.size()-1;i++){
    if(s.at(i)==s.at(i+1)){
      ok=false;
    }
  }
  if(ok){
    cout<<"yes"<<endl;
  }
  else{
    cout<<"no"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long LCM(long a,long b){
  if(b==0){
  	return a;
  }else{
  	return LCM(b,a%b);
  }
}

int main() {
  long A,B;
  long ans;
  cin >> A >> B;
  ans=A*B/LCM(A,B);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>

using namespace std;

int main(){
	int p1;
	int p2;
	int p3;
	int j1;
	int j2;
	cin >> p1 >> p2 >> p3 >> j1 >> j2;
	cout << min({ p1, min (p2, p3)  }) + min({ j1, j2 }) - 50 << endl;
	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 3092
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
using namespace std;
 
typedef long long ll;
#define db(x) cerr << #x << ": " << x << '\n';
#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}

#define print(a) cout << a << endl;
#define printarr(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(v) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define rz(v, n) v.resize((n) + 1);
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define vvi vector <vi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll N = 2e5 + 1;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	string s;
	cin >> s;
	if (s == "ABC") cout << "ARC";
	else cout << "ABC";
	
}








Measured memory_bytes: 3656
N, K = gets.split.map{|i| i.to_i}
A = gets.split.map{|i| i.to_i}

count = Array.new(40, 0)
binary = Array.new(41)
k = Array.new(40)
ans = Array.new(40)

max = 0
binary[0] = 1
for i in 0..39
    binary[i + 1] = binary[i] * 2
    k[i] = K % binary[i + 1] / binary[i]

    A.each do |a|
        count[i] += a % binary[i + 1] / binary[i]
    end

    if i > Math.log2(K)
        ans[i] = 0
    else
        ans[i] = (count[i] > N / 2) ? 0 : 1
    end

    max += (N * ans[i] - count[i]).abs * binary[i]
end

for i in 0..39
    if k[39 - i] == ans[39 - i]
        next
    end

    if k[39 - i] == 1
        break
    end

    max += binary[39 - i] * (2 * count[39 - i] - N)
end

puts max

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

int main() {
	int N, M;
	cin >> N >> M;

	int ans = 1;
	for (int A = 1; A * A <= M; A++)
	{
		//約数の判定をする！！！
		if (M % A != 0) continue;

		int B = M / A;

		if ((long)A * N <= M) ans = max(ans, A);
		if ((long)B * N <= M) ans = max(ans, B);
	}
	cout << ans << endl;
}





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

int main(){
  int n,d[110];
  cin >>n;
  rep(i,n) cin >>d[i];
  int ans = 0;
  for(int i = 0; i<n; i++){
    for(int j = i+1; j<n; j++){
      ans += d[i]*d[j];
    }
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
const int INF = 1 << 29;
const ll LINF = 1l << 61;
const ld PI = abs(acos(-1));
#define pq priotity_queue
#define pb push_back
#define mp make_pair
#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define cbuf(buf, init) memset(buf, init, sizeof(buf))

template <class T>
constexpr T modp(T x, T y)
{
    return (y + x % y) % y;
}
template <class T>
constexpr T sq(T x)
{
    return x * x;
}
template <class T>
constexpr double divd(T x, T y)
{
    static_cast<double>(x) / static_cast<double>(y);
}

template <class T>
T nextInput()
{
    T t;
    cin >> t;
    return t;
}

#define netint nextInput<ll>()
#define netstr nextInput<string>()

template <class T>
void print(T&& t)
{
    cout << forward<T&&>(t) << endl;
}

void print(double t) { cout << fixed << setprecision(14) << t << endl; }

//

int main()
{
    //
    ll N = netint, M = netint;
    if (N >= 2 && M >= 2) {
        print((N - 2) * (M - 2));
    }
    else if (N == 1 && M == 1) {
        print(1);
    }
    else if (N == 1) {
        print(M - 2);
    }
    else if (M == 1) {
        print(N - 2);
    }
}


Measured memory_bytes: 256
using System;
class SS
{
  static void Main()
  {
    var lines=Console.ReadLine().Split(" ");
    double S=double.Parse(lines[0]);
    var L=double.Parse(lines[1]);
    var H=double.Parse(lines[2]);
    var M=double.Parse(lines[3]);
    if(H>12)
      H-=12;
    double angleA=360*M/60.0;
    double angleB=(H*60+M)*360/(60*12.0);
    double angle=angleA-angleB;
    if(angle<0)
      angle=angle+360;
    if(angle>180)
      angle=360-angle;
    var degree=angle*Math.PI/180.0;
    var leng=Math.Sqrt(S*S+L*L-2*S*L*Math.Cos(degree));
    Console.WriteLine("{0}",leng);
  }
}


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

int n,k,m;
string s,t;

int main() {
  cin >> n ;
  int a[n],sum=0; a[0]=0,a[n+1]=0;
  for(int i=1;i<=n+1;i++){
    cin >> a[i]; sum+=abs(a[i]-a[i-1]);
  }
  for(int i=1;i<=n;i++)
  cout << sum-(abs(a[i]-a[i-1])+abs(a[i+1]-a[i]))+abs(a[i+1]-a[i-1]) << endl;
}

Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <math.h>
#include <sstream>
#include <iomanip>
#define REP0(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define REP1(i,n) for((i)=1;(i)<=(long long)(n);(i)++)
#define ll long long
using namespace std;

ll i,j;
const int MOD = 1000000000 + 7;

int main(){
    int n;
    ll ans=0;
   

    cin>>n;
    ll dp[n]={1,0,0};
    if(n<=2){
        
    }
    else{
        for(i=3;i<=n;i++){
            dp[i]=(dp[i-3]+dp[i-1])%MOD;
        }
    }
    cout<<dp[n]<<'\n';
    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n) for (int i = (0); i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout << #x << " = " << (x) << endl
#define show2(x,y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl
#define show3(x,y,z) cout << #x << " = " << (x) << ", " << #y << " = " << (y) <<  ", " << #z << " = " << (z) << endl
#define showv(v) rep(i,v.size()) printf("%d%c", v[i], i==v.size()-1?'\n':' ')
#define showv2(v) rep(j,v.size()) showv(v[j])
#define showt(t,n) rep(i,n) printf("%d%c", t[i], i==n-1?'\n':' ')
#define showt2(t,r,c) rep(j,r) showt(t[j],c)
#define showvp(p) rep(i,p.size()) printf("%d %d\n", p[i].first, p[i].second);
#define printv(v) rep(i,v.size()) printf("%d\n", v[i])
#define printt(t,n) rep(i,n) printf("%d\n", t[i])
#define incl(v,x) find(all(v),x)!=v.end()
#define incls(s,c) s.find(c)!=string::npos
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define bit(n,k) ((n>>k)&1) // nのk bit目
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define uni(x) x.erase(unique(all(x)),x.end())
#define SP << " " <<
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using vp = vector<P>;
using vt = vector<T>;
const int mod = 1000000007;
const double EPS = 1e-9;
//const long double EPS = 1e-14;
const int INF = (1<<30)-1;
const ll LINF = (1LL<<62)-1;
#define dame { puts("No"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
inline int in() { int x; scanf("%d",&x); return x;}
inline ll lin() { ll x; scanf("%lld",&x); return x;}
inline char chin() { char x; scanf("%c",&x); return x;}
inline string stin() { string x; cin >> x; return x;}
inline double din() { double x; scanf("%lf",&x); return x;}
//template<class T = int> inline T in() { T x; cin >> x; return (x);}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
char itoa(int n) { return n + '0';}
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 () {
  ll n = lin();
  cout << (n-1)*n/2 << endl;
  return 0;
}

Measured memory_bytes: 256
n1 = []
(0..9).each { |x| n1[x] = 1 }
(10..50).each { |x| n1[x] = 0 }

n2 = []
(0..50).each { |x|
    n2[x] = 0
    (0..9).each {|y|
        n2[x] += n1[x - y] || 0
    }
}

n3 = []
(0..50).each {|x|
    n3[x] = 0
    (0..9).each {|y|
        n3[x] += n2[x - y] || 0
    }
}

n4 = []
(0..50).each {|x|
    n4[x] = 0
    (0..9).each {|y|
        n4[x] += n3[x - y] || 0
    }
}

while n = gets
    puts n4[n.to_i]
end

Measured memory_bytes: 8692
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 10000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* struct for mod Calculation*/
struct mint {
        ll x;
        mint(ll x = 0):x((x % mod + mod) % mod) {}
        mint operator-() const { return mint(-x); }
        mint& operator+=(const mint a) {
            if ((x += a.x) >= mod) x -= mod;
            return *this;
        }
        mint& operator-=(const mint a) {
            if ((x += mod - a.x) >= mod) x -= mod;
            return *this;
        }
        mint& operator*=(const mint a) {
            (x *= a.x) %= mod;
            return *this;
        }
        mint operator+(const mint a) const {
            mint res(*this);
            return res += a;
        }
        mint operator-(const mint a) const {
            mint res(*this);
            return res -= a;
        }
        mint operator*(const mint a) const {
            mint res(*this);
            return res *= a;
        }
        mint pow(ll t) const {
            if (!t) return 1;
            mint a = pow(t >> 1);
            a *= a;
            if (t & 1) a *= *this;
            return a;
        }
        // for prime mod
        mint inv() const {
            return pow(mod - 2);
        }
        mint& operator/=(const mint a) {
            return (*this) *= a.inv();
        }
        mint operator/(const mint a) const {
            mint res(*this);
            return res /= a;
        }
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
/* global variables */
/* function */
/* main */
int main(){
    int n;
    cin >> n;
    vector<mint> a(n);
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        a[i] = m;
    }

    mint sum = 0;
    mint trace = 0;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        trace += a[i] * a[i];
    }
    sum *= sum;

    mint ans = (sum - trace) / 2;

    cout << ans << '\n';
}

Measured memory_bytes: 4808
import collections

N = int(input())
A = list(map(int, input().split()))

B = dict(collections.Counter(A))
M = len(B)

ans = 0

for i in B.keys():
    if B[i] >= int(i):
        ans += B[i] - int(i)
    else:
        ans += B[i]

print(ans)

Measured memory_bytes: 24864
#include<cstdio>
#include<algorithm>
using namespace std;
int n,ans,a[101];
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;i+=2)ans+=(a[i]-a[i+1]);
	printf("%d",ans);
}

Measured memory_bytes: 128
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
XYC = [list(map(int, input().split())) for m in range(M)]
ans = min(a)+min(b)
for m in range(M):
  tmp = a[XYC[m][0]-1]+b[XYC[m][1]-1]-XYC[m][2]
  ans = min(tmp, ans)
print(ans)

Measured memory_bytes: 101036
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static final long MOD = 1_000_000_007;

    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();

        final Map<Integer, Long> countMap = new HashMap<>();
        for (int i = 2; i <= n; i++) {
            count(i, countMap);
        }

        long sum = 1;
        for (final long value : countMap.values()) {
            sum = (sum * (value + 1)) % MOD;
        }

        System.out.println(sum);
    }

    private static void count(int n, final Map<Integer, Long> countMap) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                countMap.compute(i, (k, v) -> v = v == null ? 1 : v + 1);
                n /= i;
                i--;
            }
        }

        if (n != 1) {
            countMap.compute(n, (k, v) -> v = v == null ? 1 : v + 1);
        }
    }
}


Measured memory_bytes: 26580
#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

char dt[6][8];

void color(char ch,int x,int y){
	rep(i,2){
		rep(j,2){
			dt[y+i][x+j]=ch;
		}
	}
}

void turnself(int i,int j){
	int alt=dt[i][j];
	dt[i][j]=dt[i+1][j];
	dt[i+1][j]=dt[i+1][j+1];
	dt[i+1][j+1]=dt[i][j+1];
	dt[i][j+1]=alt;
}

void turnF(){
	int alt1=dt[1][2];
	int alt2=dt[1][3];
	dt[1][2]=dt[3][1];
	dt[1][3]=dt[2][1];
	dt[2][1]=dt[4][2];
	dt[3][1]=dt[4][3];
	dt[4][2]=dt[3][4];
	dt[4][3]=dt[2][4];
	dt[3][4]=alt2;
	dt[2][4]=alt1;
	turnself(2,2);
}

void turnR(){
	int alt1=dt[0][3];
	int alt2=dt[1][3];
	dt[0][3]=dt[2][3];
	dt[1][3]=dt[3][3];
	dt[2][3]=dt[4][3];
	dt[3][3]=dt[5][3];
	dt[4][3]=dt[3][6];
	dt[5][3]=dt[2][6];
	dt[3][6]=alt1;
	dt[2][6]=alt2;
	turnself(2,4);
}

void turnD(){
	int alt1=dt[3][0];
	int alt2=dt[3][1];
	dt[3][0]=dt[3][6];
	dt[3][1]=dt[3][7];
	dt[3][6]=dt[3][4];
	dt[3][7]=dt[3][5];
	dt[3][4]=dt[3][2];
	dt[3][5]=dt[3][3];
	dt[3][2]=alt1;
	dt[3][3]=alt2;
	turnself(4,2);
}

void turnB(){
	int alt1=dt[2][5];
	int alt2=dt[3][5];
	dt[2][5]=dt[5][3];
	dt[3][5]=dt[5][2];
	dt[5][3]=dt[3][0];
	dt[5][2]=dt[2][0];
	dt[3][0]=dt[0][2];
	dt[2][0]=dt[0][3];
	dt[0][2]=alt1;
	dt[0][3]=alt2;
	turnself(2,6);
}

void turnL(){
	int alt1=dt[4][2];
	int alt2=dt[5][2];
	dt[4][2]=dt[2][2];
	dt[5][2]=dt[3][2];
	dt[2][2]=dt[0][2];
	dt[3][2]=dt[1][2];
	dt[0][2]=dt[3][7];
	dt[1][2]=dt[2][7];
	dt[3][7]=alt1;
	dt[2][7]=alt2;
	turnself(2,0);
}

void turnU(){
	int alt1=dt[2][0];
	int alt2=dt[2][1];
	dt[2][0]=dt[2][2];
	dt[2][1]=dt[2][3];
	dt[2][2]=dt[2][4];
	dt[2][3]=dt[2][5];
	dt[2][4]=dt[2][6];
	dt[2][5]=dt[2][7];
	dt[2][6]=alt1;
	dt[2][7]=alt2;
	turnself(0,2);
}

int main(){
	rep(i,6)rep(j,8)dt[i][j]='.';
	color('r',2,0);
	color('g',0,2);
	color('y',2,2);
	color('o',2,4);
	color('b',4,2);
	color('w',6,2);
	string s;
	cin>>s;
	rep(i,s.size()){
		if(s[i]=='U')turnU();
		else if(s[i]=='F')turnF();
		else if(s[i]=='R')turnR();
		else if(s[i]=='D')turnD();
		else if(s[i]=='B')turnB();
		else if(s[i]=='L')turnL();
	}
	rep(i,6){
		rep(j,8){
			cout<<dt[i][j];
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1184
n = int(input())
a_s = [int(input()) for _ in range(n)]
c = 1
r = a_s[0]
while True:
  if r == 2:
    print(c)
    break
  r = a_s[r-1]
  c += 1
  if c > n:
    print(-1)
    break


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

using namespace std;
#define int long long
#define br cout<<"\n"
#define all(V) V.begin(),V.end()
#define rall(V) V.rbegin(),V.rend()
#define umap unordered_map
#define uset unordered_set

typedef vector<int> vi;
typedef vector<vi> vvi;

bool isPwrOf2(int x) { return x && (!(x&(x-1))); }
/*------------------------------------------------*/
string base2(int num)
{
    if(num==0){return "0";}
    string s="";
    while(num!=0){
        int rem = num%(-2);
        num/=(-2);
        if(rem<0){
            rem+= 2;
            num+=1;
        }
        s = to_string(rem) + s;
    }
    return s;
}
/*------------------------------------------------*/

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    // #ifndef ONLINE_JUDGE
    //     freopen("./input.txt", "r", stdin);
    //     freopen("./output.txt", "w", stdout);
    // #endif
    /*------------------------------------------------*/
    int num; cin>>num;
    cout<< base2(num);
    /*------------------------------------------------*/
    return 0;
}

Measured memory_bytes: 256
import itertools

N, M, Q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(Q)]

result = 0
for x in itertools.combinations_with_replacement(range(1, M + 1), N):
    temp = 0
    for a, b, c, d in A:
        if x[b - 1] - x[a - 1] == c:
            temp += d
    if temp > result:
        result = temp

print(result)


Measured memory_bytes: 9056