akhauriyash/Code-Regression huggingface dataset:
S = input()
len_s = len(S)
rev = False
max_ = 2*10**5
index = max_ + len_s
rev_index = max_ - 1
s = ["." for _ in range(max_*2 + len_s)]
for i in range(len_s):
    s[max_+i] = S[i]
for _ in range(int(input())):
  t = input()
  if t == "1":
    rev = not rev
  else:
    t = t.split()
    if (t[1] == "1" and not rev) or (t[1] == "2" and rev):
      s[rev_index] = t[2]
      rev_index -= 1
    else:
      s[index] = t[2]
      index += 1
if rev:
  for i in range((max_ + max_ + len_s - 1), 0, -1):
    if s[i] != ".":
      print(s[i], end="")
else:
  for i in range((max_ + max_ + len_s)):
    if s[i] != ".":
      print(s[i], end="")

Measured memory_bytes: 8832
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x-I .)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> LP;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

//dp[i] = 0 ... not determined
//dp[i] = 1 ... win
//dp[i] = 2 ... lose
int N, K;
vector<int> a(100100);
vector<int> dp(100100, 0);

int solve(int k){
    if(dp[k] != 0)return dp[k];
    if(k < a[0])return dp[k] = 2;
    int res = 0;
    rep(i,N){
        if(k >= a[i])res = max(res, solve(k-a[i]));
    }
    return dp[k] = (res == 1 ? 2 : 1);
}

int main(){
    cin >> N >> K;
    rep(i,N)cin >> a[i];
    cout << (solve(K) == 1 ? "First" : "Second") << endl;
    return 0;
}

Measured memory_bytes: 8780
#include<iostream>
#define MAX 100005
#include <algorithm>
using namespace std;

int num[MAX];
long long sum[MAX];
int stone[MAX];
int place[MAX];

int main() {
	int n;
	cin >> n;
	int max; int max_n;
	max = 0; max_n = 0;
	int cnt = 1;
	for (int i = 1; i <= n; i++) {
		int s;
		cin >> s;
		stone[i] = s;
		if (max < s) { 
		max = s;
		place[cnt] = i;
		num[cnt] = s;
		cnt++;
		}
	}
	place[0] = 0;
	num[0] = 0;
	sort(stone+1, stone + n+1);
	sum[0] = 0;
	for (int i = 1; i <= n; i++) {
		sum[i] = sum[i - 1] + stone[i];
	}
	int now = 1;
	for (int i = 1; i <= n; i++) {
		if (place[now] != i) {
			cout << 0 << endl;
		}
		else {
			long long p;
			p = (stone + n+1 - lower_bound(stone, stone + n+1, num[now]))*(num[now] - num[now - 1]);
			p = p + sum[lower_bound(stone, stone + n, num[now]) - stone - 1] - sum[lower_bound(stone, stone + n, num[now - 1]) - stone]
					- (num[now - 1])*(lower_bound(stone, stone + n, num[now]) - 1 - lower_bound(stone, stone + n, num[now - 1]));
			cout << p << endl;
			now++;
		}
	}
}

Measured memory_bytes: 3072
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<iostream>
#include<algorithm>
#define int long long
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<33);
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>33)x=x*10+ch-48;
	if(fs)x=-x;	
}
using namespace std;
int n,ans;
main()
{
	re(n);
	int sum=0,x;
	while(n--)
	{
		re(x);
		if(!x)
			ans+=sum/2,sum=0;
		else 
			sum+=x;
	}
	ans+=sum/2;
	printf("%lld\n",ans);
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	long long int n, sum = 0;
	scanf("%lld", &n);
	
	for(int i = 1; i <= n; i++) {
		if(i % 3 == 0 || i % 5 == 0) {
			sum = sum;
		} else {
			sum += i;
		}
	}
	printf("%lld", sum);
	
	return 0;
}

Measured memory_bytes: 1704
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define const 1e6
bool f(ll a,ll b){
return a>b;
}

vector<int> v(100000);
vector<int> dp(100000,-1);
int n,k;
int fact(int curr){
	if(curr==n-1)
	return dp[curr]=0;
	if(dp[curr]!=-1)
	return dp[curr];
	int mini=1e9+5;
	for(int i=curr+1;i<=min(n-1,curr+k);i++){
		mini=min(mini,abs(v[curr]-v[i])+fact(i));
	}
	return dp[curr]=mini; 
}

int main(){
int t=1;

while(t--){
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>v[i];
cout<<fact(0)<<endl;
}

return 0;
}


Measured memory_bytes: 10356
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
  int n,q,t;
  string name;
  queue<pair<string,int> > Q;
  cin>>n>>q;
  for(int i=0;i<n;i++){
    cin>>name>>t;
    Q.push(make_pair(name,t));
  }

  pair<string,int> u;
  int elaps=0,a;

  while( !Q.empty()){
    u=Q.front();Q.pop();
    if(u.second<=q){
      elaps=elaps+u.second;
      cout<<u.first<<" "<<elaps<<endl;
    }else{
      elaps=elaps+q;
      Q.push(make_pair(u.first,u.second-q));
    }
  }


  return 0;
}



Measured memory_bytes: 6244
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
S = list(input()[:-1])

for i in range(2*N):
    if (2*N-i-1)%2==1:
        if S[i]=='B':
            S[i] = 'W'
        else:
            S[i] = 'B'
    
if S.count('B')!=N:
    print(0)
    exit()

w = 0
ans = 1
MOD = 10**9+7

for i in range(2*N):
    if S[i]=='W':
        w += 1
    else:
        ans *= w
        w -= 1
        ans %= MOD

for i in range(1, N+1):
    ans *= i
    ans %= MOD

print(ans)

Measured memory_bytes: 82756
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int lw = sc.nextInt() + sc.nextInt();
		int rw = sc.nextInt() + sc.nextInt();

		if(lw > rw) {
			System.out.println("Left");
		} else if(lw < rw) {
			System.out.println("Right");
		} else {
			System.out.println("Balanced");
		}
	}
}

Measured memory_bytes: 35548
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
using ll=long long;
static const ll mod = 1e9 + 7;
static const ll INF = 1LL << 50;
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<double>a(n);
    rep(i,n)cin>>a[i];
    double ans=0;
    rep(i,n)ans+=1/a[i];
    printf("%.6lf\n",1/ans);
    return 0;
}


Measured memory_bytes: 256
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

#define INF (1LL << 60)

using namespace std;

int main()
{
    int V, E, X, A, B, C;

    scanf("%d", &V);
    scanf("%d", &E);
    scanf("%d", &X);

    vector<long long> R(V);

    vector<vector<pair<int, long long> > > G(V);
 
    for (int i = 0; i < V; i++)
    {
        scanf("%lld", &R[i]);
    }

    for (int i = 0; i < E; i++)
    {
        scanf("%d", &A);
        scanf("%d", &B);
        scanf("%d", &C);

        G[A - 1].push_back(make_pair(B - 1, C));
        G[B - 1].push_back(make_pair(A - 1, C));
    }

    vector<long long> D(V, INF); D[0] = 0;
    vector<long long> F(V, INF); F[0] = X;

    queue<int> que; que.push(0); // node

    while (!que.empty())
    {
        int node = que.front(); que.pop();

        int high = F[node];

        for (int i = 0; i < G[node].size(); i++)
        {
            int went = G[node][i].first;
            int cost = G[node][i].second;

            if (R[node] >= cost)
            {
                if (high - cost <= 0)
                {
                    long long t = D[node] + (cost - high) + cost; // high --> cost --> 0 meters

                    if (t < D[went])
                    {
                        D[went] = t;
                        F[went] = 0;

                        que.push(went);
                    }
                }
                else if(high - cost <= R[went])
                {
                    long long t = D[node] + cost; // high --> high --> (high - cost) meters

                    if (t < D[went])
                    {
                        D[went] = t;
                        F[went] = high - cost;

                        que.push(went);
                    }
                }
                else
                {
                    long long t = D[node] + high - R[went]; // high --> (R[went] + cost) --> R[went] meters

                    if (t < D[went])
                    {
                        D[went] = t;
                        F[went] = R[went];

                        que.push(went);
                    }
                }
            }
        }
    }

    printf("%lld\n", D[V - 1] != INF ? D[V - 1] + R[V - 1] - F[V - 1] : -1);

    return 0;
}

Measured memory_bytes: 23348
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

struct Restaurant{
	int id;
	string name;
	int price;
}; 

bool price_cmp(const struct Restaurant& a, const struct Restaurant& b) {
	return a.price > b.price;
}

bool name_cmp(const struct Restaurant& a, const struct Restaurant& b) {
	return a.name < b.name;
}

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

	string s;
	int p;
	vector<struct Restaurant> guide;
	struct Restaurant temp;

	for (int i = 0; i < n; i++) {
		cin >> s >> p;
		temp.id = i+1;
		temp.name = s;
		temp.price = p;
		guide.push_back(temp);
	}

	sort(guide.begin(), guide.end(), price_cmp);
	stable_sort(guide.begin(), guide.end(), name_cmp);

	for (int i = 0; i < n; i++) {
		cout << guide[i].id << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
typedef long long       ll;
#define pb                push_back
#define mp              make_pair
#define sz(a)           a.size()
#define mods(a, m)          ((a % m + m) % m)
#define md(a)               mods(a, MOD)
#define all(a)            (a).begin(), (a).end()
#define clr(a,h)          memset(a, (h), sizeof(a))
#define mem(a,h)          memset(a, (h), sizeof(a))
#define F first
#define S second
#define f first
#define s second
#define fore(i, b, e)     for (int i = b; i < e; i++)
#define forr(i, b, e)     for (int  i = b; i < e; i++)
#define endl '\n'
int faster_in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -faster_in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
//using namespace __gnu_pbds;
typedef long double       ld;

typedef pair<int, int>  ii;
typedef pair<int,ii> iii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int INF = int(1e9 + 7);
const int MOD = 1e9+7;
const double EPS = 1e-9;
const double PI = acos(-1);
#define tam 1000003 
int main()
{    
    std::ios::sync_with_stdio(false); cin.tie(0);
    string t;
    cin>>t;
    t=string(t.size(),'x');
    cout<<t<<endl;
}   
// PLUS ULTRA!


Measured memory_bytes: 256
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int a, b, c;
int main() {
	cin >> a >> b >> c;
	if (a == b) cout << c << endl;
	if (a == c) cout << b << endl;
	if (b == c) cout << a << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll n;
  cin >> n;
  vl a(n);
  rep(i,n){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  ll r=a[0]^a[n/3]^a[2*n/3];
  if(a[n-1]==0){
    cout << "Yes" << endl;
  }
  else if(n%3==0&&(a[0]==a[n/3-1]&&a[n/3]==a[2*n/3-1]&&a[2*n/3]==a[n-1])&&r==0){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
}

Measured memory_bytes: 1024
/*   _/                _/                 _/_/_/   _/
  _/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
   _/     _/    _/   _/     _/    _/  _/_/_/     _/
  _/     _/    _/   _/     _/    _/  _/    _/   _/
   _/_/   _/_/       _/_/   _/_/      _/_/     _/ */
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9+5;
const ll INF=1e18+5;
using P=pair<int,int>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll n,ans=1,f;
  string s,t;
  cin >> n >> s >> t;
  for(int i=0; i<n; i++) {
    if(i==0&&s[i]==t[i]) {
      ans*=3;
      ans%=MOD;
      f=1;
    }
    else if(i==0&&s[i]!=t[i]) {
      i++;
      ans*=6;
      ans%=MOD;
      f=0;
    }
    else {
      if(s[i]==t[i]) {
        if(f) {
          ans*=2;
          ans%=MOD;
        }
        else {
          f=1;
        }
      }
      else {
        i++;
        if(f) {
          ans*=2;
          ans%=MOD;
          f=0;
        }
        else {
          ans*=3;
          ans%=MOD;
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>  
using namespace std;
long long a[100001];
int main(){
	long long i,n,ans=0;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]);
	sort(a+1,a+n+1);
	long long k=a[1],q=1;
	for(i=2;i<=n;i++){
		if(a[i]==k)q++;
		else{
			k=a[i];
			if(q%2==1)ans++;
			q=1;
		}
	}if(q%2==1)ans++;
	cout<<ans<<endl;
}

Measured memory_bytes: 1024
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	void solve(Supplier<String> sc) {
		int N = Integer.parseInt(sc.get());
		long[] A = new long[N];
		Arrays.setAll(A, $ -> Long.parseLong(sc.get()));
		boolean increasing = false;
		boolean decreasing = true;
		long cash = 1000;
		long stock = 0;
		for (int i = 1; i < A.length; i++) {
			boolean inc = A[i] > A[i - 1];
			boolean dec = A[i] < A[i - 1];
			if (!inc && !dec) continue;
			if (increasing && dec){
				cash += stock * A[i - 1];
				stock = 0;
			} else if (decreasing && inc) {
				stock += cash / A[i - 1];
				cash = cash % A[i - 1];
			}
			increasing = inc;
			decreasing = dec;
		}
		System.out.println(cash + stock * A[N - 1]);
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		var reader = new BufferedReader(new InputStreamReader(System.in));
		new Solver().solve(new Supplier<>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

Measured memory_bytes: 33676
N = int(input())
ans = ''
if N == 0:
    print(0)
    exit()
while N != 0:
    if N % 2 == 0:
        ans = '0' + ans
        N = (N // -2)
    else:
        ans = '1' + ans
        N -= 1
        N = (N // -2)
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=1000 +117;
const int MM=1000 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
struct edge{
	int to,xt,rem;
	LL ct;
}e[100*NN];
int ecnt=2;
int p[2*NN]={};
void ADD(int a,int b,int cap,LL ct){
	e[ecnt].to=b;
	e[ecnt].xt=p[a];
	e[ecnt].rem=cap;
	e[ecnt].ct=ct;
	p[a]=ecnt++;
}
void add(int a,int b,int cap,LL ct){
	ADD(a,b,cap,ct);
	ADD(b,a,0,-ct);
}

int con[4][2]={{1,1},{1,-1},{-1,1},{-1,-1}};
struct node{
	LL x,y;
	LL v(int j){
		return x*con[j][0]+y*con[j][1];
	}
};

int src,fin;
int mid[4]={};
LL ans,flow;
int pre[2*NN]={};
LL sp[2*NN]={};
int pcnt=0;
queue<int> q;
bool inq[2*NN]={};
bool spfa(){
	for(int i=1;i<=pcnt;++i)sp[i]=1e18;
	sp[src]=0;
	q.push(src);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		inq[x]=0;
		for(int pos=p[x];pos;pos=e[pos].xt){
			int cur=e[pos].to;
			if(e[pos].rem&&sp[cur]>e[pos].ct+sp[x]){
				sp[cur]=e[pos].ct+sp[x];
				pre[cur]=pos;
				if(!inq[cur]){
					inq[cur]=1;
					q.push(cur);
				}
			}
		}
	}
	return sp[fin]!=1e18;
}
void getf(){
	while(spfa()){
		int cap=1e9;
		int pos=fin;
		while(pos!=src){
			int x=pre[pos];
			cap=min(e[x].rem,cap);
			pos=e[x^1].to;
		}
		flow+=cap;
		ans+=cap*sp[fin];
		pos=fin;
		while(pos!=src){
			int x=pre[pos];
			e[x].rem-=cap;
			e[x^1].rem+=cap;
			pos=e[x^1].to;
		}
	}
}
int main(){
	//open();
	n=read();
	for(int i=0;i<4;++i){
		mid[i]=2*n+i+1;
	}
	src=2*n+5;
	fin=src+1;
	pcnt=fin;
	for(int i=1;i<=n;++i){
		node a;
		a.x=read(),a.y=read();
		int c=read();
		add(src,i,c,0);
		for(int j=0;j<4;++j){
			add(i,mid[j],1e9,a.v(j));
		}
	}
	for(int i=1;i<=n;++i){
		node a;
		a.x=read(),a.y=read();
		int c=read();
		add(i+n,fin,c,0);
		for(int j=0;j<4;++j){
			add(mid[j],i+n,1e9,a.v(3^j));
		}
	}
	getf();
	printf("%lld\n",-ans);

	close();
	return 0;
}

Measured memory_bytes: 768
<?php
$fp = fopen('php://stdin', 'r');
while (feof($fp) == false) {
  $line = fgets($fp);
  if ($line == "") continue;
  $nums = explode(' ', $line);
  //GCDの計算
  $min_k = array_search(min($nums), $nums);   //値が小さい方のキー
  $max_k = $min_k == 0 ? 1 : 0;   //値が大きい方のキー
//  echo "min_k = $min_k".PHP_EOL;
//  echo "max_k = $max_k".PHP_EOL;
  for ($i=1; $i<=min($nums); $i++) {
    if ($nums[$min_k] % $i == 0) {
      if ($nums[$max_k] % ($nums[$min_k] / $i) == 0) {
        echo $nums[$min_k] / $i.' '; 
        break;
      }   
    }   
  }
  //LCMの計算
  $n = 1;
  while (true) {
    if (($nums[$max_k] * $n) % $nums[$min_k] == 0) {
      echo $nums[$max_k] * $n.PHP_EOL;
      break;
    }   
    $n++;
  }
}

Measured memory_bytes: 6656
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PI 4*atan(1.0)
typedef long long ll;
typedef long double ld;
using namespace std;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};

int calc(long long int a,long long int b,long long int p){
	if(!b) return 1;
	else if(!(b%2)){
		long long int d=calc(a,b/2,p);
		return (d*d)%p;
	}else return (a*calc(a,b-1,p))%p;
}
const int MAX=200000;

int main(){
	int H,W,A,B;
	ll ans=0;
	cin>>H>>W>>A>>B;
	ll inv[MAX]={};
	ll uniteA[MAX]={},uniteB[MAX]={};
	ll exc[MAX]={1,1,0},excinv[MAX]={1,1,0};
	for(int i=1;i<MAX;i++){
		inv[i]=calc(i,MOD-2,MOD);
	}
	for(int i=2;i<MAX;i++){
		exc[i]=exc[i-1]*i%MOD;
	}
	for(int i=2;i<MAX;i++){
		excinv[i]=excinv[i-1]*inv[i]%MOD;
	}

	for(int i=B;i<=W-1;i++){
		ll temp=1;
		temp=temp*exc[i+H-A-1]%MOD;
		temp=temp*excinv[H-A-1]%MOD;
		temp=temp*excinv[i]%MOD;
		uniteA[W-i-1]=temp;
		if(uniteA[W-i-1]);
			//printf("uniteA[%d]=%d\n",W-i-1,uniteA[W-1-i]);
	}
	for(int i=W-B-1;i>=0;i--){
		ll temp=1;
		temp=temp*exc[i+A-1]%MOD;
		temp=temp*excinv[A-1]%MOD;
		temp=temp*excinv[i]%MOD;
		uniteB[i]=temp;
		if(uniteB[i]);
			//printf("uniteB[%d]=%d\n",i,uniteB[i]);
	}
	for(int i=0;i<MAX;i++)
		ans=(ans+(uniteA[i]*uniteB[i])%MOD)%MOD;

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

Measured memory_bytes: 8064
#include <iostream>
#include <tuple>
#include <algorithm>
#include <vector>
using namespace std;
using P = pair<int,int>;

int main(){
    int n,m;
    cin>>n>>m;
    vector<P> V;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        V.emplace_back(x-1,y-1);
    }
    sort(V.begin(), V.end());
    int lb[n],ub[n];
    for(int i=0;i<n;i++) lb[i]=ub[i]=i;
    for(auto p:V){
        int x,y;
        tie(x,y)=p;
        lb[y]=lb[y+1]=min(lb[y],lb[y+1]);
        ub[y]=ub[y+1]=max(ub[y],ub[y+1]);
    }
    for(int i=0;i<n;i++){
        if(i)cout<<' ';
        cout<<ub[i]-lb[i]+1;
    }
    cout<<endl;

    return 0;
}

Measured memory_bytes: 5148
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <map>

using namespace std;


int main(void) {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	if (a * b <= c * d) {
		cout << c * d << endl;
	}
	else {
		cout << a * b << 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;
using P = pair<int,int>;
using vi = vector<int>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

int main() {
  bitset<100> list;
  int x, n, p;
  cin >> x >> n;
  rep(i,n){
    cin >> p;
    list.set(p-1,1);
  }
  if (!list.test(x-1)){
    cout << x << endl;
    return 0;
  }
  int j = 1;
  while(j < 100){
    if (x-j == 0){
      cout << 0 << endl;
      return 0;
    }
    else if (!list.test(x-j-1)){
      cout << x-j << endl;
      return 0;
    }
    if (x+j == 101){
      cout << 101 <<endl;
      return 0;
    }
    else if (!list.test(x+j-1)){
      cout << x+j <<endl;
      return 0;
    }
    j++;
  }
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define MIN -1000000
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
ll X,Y,Z,K;
ll A[1005],B[1005],C[1005];
vector<ll> AB={};
vector<ll> anss={};
int main(void)
{
  memset(A,0,sizeof(A));
  memset(B,0,sizeof(B));
  memset(C,0,sizeof(C));
  cin >> X >> Y >> Z >> K;
  for (int i = 0; i < X; ++i)
    {
      cin >> A[i];
    }
  for (int i = 0; i < Y; ++i)
    {
      cin >> B[i];
    }
  for (int i = 0; i < Z; ++i)
    {
      cin >> C[i];
    }
  for (int i = 0; i < X; ++i)
    {
      for (int j = 0; j < Y; ++j)
	{
	  AB.push_back(A[i]+B[j]);
	}
    }
  sort(AB.begin(),AB.end(),greater<ll>());
  for (int i = 0; i < min(3000LL,ll(AB.size())); ++i)
    {
      for (int j = 0; j < Z; ++j)
	{
	  //cout << AB[i] << ' ' << C[j] << endl;
	  anss.push_back(AB[i]+C[j]);
	}
    }
  sort(anss.begin(),anss.end(),greater<ll>());
  for (int i = 0; i < K; ++i)
    {
      cout << anss[i] << endl;
    }
  return 0;
}


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

using pii = pair<int,int>;
#define rep(i, j) for(int i=0; i < (int)(j); i++)

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

class Solver {
  public:
    int P, R, T;
    vector<int> L;
    vector<vector<int>> N;
    vector<pii> PR;

    bool check_terminated(vector<int> &need) {
        bool terminated = true;
        rep(r, R) terminated &= need[r] == 0;
        return terminated;
    }
    
    bool is_avoidable(int t) {
        vector<vector<int>> need = N;
        vector<int> left = L;

        vector<bool> terminated(P);
        int terminated_num = 0;

        // simulation
        rep(i, t) {
            int p = PR[i].first, r = PR[i].second;
            left[r]--;
            need[p][r]--;
            if(left[r] < 0) {
                return false; // lack of resource !
            }
            if(need[p][r] == 0) {
                assert(not terminated[p]);
                if(check_terminated(need[p])) {
                    rep(r2, R) left[r2] += N[p][r2] - need[p][r2];
                    terminated[p] = true;
                    terminated_num++;                            
                }
            }
        }            
        // greedy
        bool flg = true;
        while(terminated_num < P and flg) {
            flg = false;
            rep(p, P) {
                if(terminated[p]) continue;
                bool terminatable = true;
                rep(r, R) terminatable &= need[p][r] <= left[r];
                if(terminatable) {
                    rep(r, R) left[r] += N[p][r] - need[p][r];
                    terminated[p] = true;
                    terminated_num++;
                    flg = true;
                }                
            }
        }
        return terminated_num == P;
    }
    
    bool solve() {
        cin >> P >> R >> T;
        L.resize(R); cin >> L;
        N.resize(P, vector<int>(R)); cin >> N;
        PR.resize(T);
        rep(i, T) {
            cin >> PR[i].first >> PR[i].second;
            PR[i].first--;
            PR[i].second--;
        }

        int l = -1, r = T + 1;
        while(l + 1 < r) {
            int m = (l + r) / 2;
            (is_avoidable(m) ? l : r) = m;            
        }
        cout << (r > T ? -1 : r) << endl;
        return 0;
    }
};

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

Measured memory_bytes: 5248
# Studying https://atcoder.jp/contests/abc168/tasks/abc168_f
#      and https://mobile.twitter.com/chokudai/status/1262023105888698369

N,M = gets.split.map(&:to_i)
縦線 = N.times.map{ gets.split.map(&:to_i) }
横線 = M.times.map{ gets.split.map(&:to_i) }

経線 = 縦線.map{|_,_,c| c }.uniq.sort
緯線 = 横線.map{|d,| d }.uniq.sort

GW = 経線.size*2+3 # INF ゾーンと壁で囲います(+4)。
GH = 緯線.size*2+3
GI = lambda{|横,縦|
	i = 経線.bsearch_index{|_| 横<=_ }||経線.size # 線分の端点の座標に対応する
	j = 緯線.bsearch_index{|_| 縦<=_ }||緯線.size
	i1 = 経線[i] != 横 ? 1 : 0 # 線分間の座標に対応するための補正
	j1 = 緯線[j] != 縦 ? 1 : 0
	next (2+2*j-j1)*GW+(2+2*i-i1)
}
下 = lambda{|i|
	(i/GW+1)/2*2*GW + i%GW
}
上 = lambda{|i|
	i/GW/2*2*GW + i%GW
}
右 = lambda{|i|
	(i+1)/2*2
}
左 = lambda{|i|
	i/2*2
}
Grid = lambda{|g|
	縦線.each{|a,b,c|
		下[GI[c,a]].step(上[GI[c,b]], GW){|i|
			g[i] = '0'
		}
	}
	i = 0
	GH.times{
		g[i] = g[i+GW-1] = '0'
		i += GW
	}

	横線.each{|d,e,f|
		右[GI[e,d]].upto(左[GI[f,d]]){|i|
			g[i] = '0'
		}
	}
	0.upto(GW-1){|i|
		g[i] = g[-1-i] = '0'
	}

	return g
}['1'*(GW*GH)]
Area = lambda{|a|
	(GW+1).upto(GW+GW-2){|i|
		a[i] = a[-1-i] = Float::INFINITY
	}
	i = GW+1
	(GH-2).times{
		a[i] = a[i+GW-3] = Float::INFINITY
		i += GW
	}

	heights = 緯線.each_cons(2).map{|y,z| z-y }
	widths = 経線.each_cons(2).map{|y,z| z-y }
	j = (GW+1)*3
	heights.each{|h|
		i = 0
		widths.each{|w|
			a[j+i] = h*w
			i += 2
		}
		j += GW+GW
	}

	return a
}[[0]*(GW*GH)]

area = 0
cow = GI[0,0]
Grid[cow] = '0'
Q = [cow]
while at = Q.shift
	area += Area[at]
	[-1,1,GW,-GW].each{|mv|
		next if Grid[at+mv] == '0'
		Grid[at+mv] = '0'
		Q << at+mv
	}
end

puts(area.finite? ? area : 'INF')


Measured memory_bytes: 50112
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <valarray>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <tuple>
#include <random>

using namespace std;
using ll = long long;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  int n, k;
  cin >> n >> k;
  int cnt = 0;
  for (int i = 0; i < n; ++i)
  {
    int h;
    cin >> h;
    if (h >= k)
      cnt++;
  }
  cout << cnt << endl;

  return 0;
}


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




int main(){

    int N;
    ll W;
    cin >> N >> W;
    vl w(N);
    vi v(N);
    rep(i,N) cin >> w[i] >> v[i];
    
    vvl dp(N+1,vl(100005,infl));
    dp[0][0] = 0;
    
    rep(i,N){
        rep(j,100005){
            dp[i+1][j] = dp[i][j];
            if(j-v[i] >= 0) if(dp[i][j-v[i]]+w[i] <= W) chmin(dp[i+1][j],dp[i][j-v[i]]+w[i]);
        }
    }
    
    
    int ans = 0;
    rep(j,100005) if(dp[N][j] <= W) chmax(ans,j);
    
    cout << ans << endl;
    
    
    

    return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  string s;
  cin >> s;
  sort(all(s));
  if (s[0] == s[2]) no(); yes();
}


Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    int max_water = -1;
    int max_suger = -1;
    float max_node = -1;
    for(int i = 0; i <= f; i += 100 * a){
        for(int j = 0; j <= f - i; j += 100 * b){
            int water = i + j;
            if(water <= 0)
                continue;
            for(int k = 0; k <= f - water; k += c){
                for(int l = 0; l <= f - water - k; l += d){
                   int suger = k + l;
                   /*
                    if(suger <= 0)
                        continue;
                        */
                    float node = (float)suger / (suger + water) * 100;
                    if(e * water < 100 * suger)
                        continue;
                    if(max_node < node){
                        max_node = node;
                        max_water = water + suger;
                        max_suger = suger;
                    }
                }
            }
        }
    }
    cout << max_water << " " << max_suger << endl;
    return 0;
}


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

int main(){
	
	int n,m; cin>>n>>m;
	vector<vector<int>> d(n);
	for(int i=0; i<m; i++){
		int a,b; cin>>a>>b;
		d.at(a-1).push_back(b-1);
		d.at(b-1).push_back(a-1);
	}
	vector<int> to(n,-1);
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		auto p = q.front();
		q.pop();
		for(auto i:d.at(p)){
			if(to.at(i)==-1){
				to.at(i) = p;
				q.push(i);
			}
		}
	}
	cout << "Yes" << endl;
	for(int i=1; i<n; i++){
		cout << to.at(i)+1 << endl;
	}
}



Measured memory_bytes: 10072
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    if (abs(a - b) % 2)
        cout << "IMPOSSIBLE";
    else
        cout << (a + b) / 2;
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,k = LI()
    a = LI()
    b = LI()
    a = [0]+list(accumulate(a))
    b = [0]+list(accumulate(b))
    ans = 0
    for i in range(len(a)):
        sa = a[i]
        res = k-sa
        if res < 0:
            continue
        j = bisect.bisect_right(b,res)
        s = i+j-1
        if ans < s:
            ans = s
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 131440
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;
import core.bitop, core.thread;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) throw new EOFException; tokens = readln.split; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


immutable INF = 10^^9 + 10;

int N;
int[][] A;

void main() {
  try {
    for (; ; ) {
      N = readInt();
      A = new int[][](N, 3);
      foreach (i; 0 .. N) {
        foreach (j; 0 .. 3) {
          A[i][j] = readInt();
        }
      }
      auto dp = new int[][](N + 1, 3);
      foreach (i; 0 .. N + 1) {
        dp[i][] = -INF;
      }
      dp[0][] = 0;
      foreach (i; 0 .. N) {
        foreach (x; 0 .. 3) foreach (y; 0 .. 3) {
          if (x != y) {
            chmax(dp[i + 1][y], dp[i][x] + A[i][y]);
          }
        }
      }
      int ans = -INF;
      foreach (x; 0 .. 3) {
        chmax(ans, dp[N][x]);
      }
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}


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

#define ED return 0;
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) int(pow(x,y))
const long long mod = 1000000007;

int main() {
    int N, K;
    cin >> N >> K;
    if(N % K == 0){
        cout << 0 << endl;
    }
    else{
        cout << 1 << endl;
    }
}

Measured memory_bytes: 256
import fractions
def lcm(a):
    LCM = a[0]
    for i in range(1, n):
        LCM = LCM * a[i] // fractions.gcd(LCM, a[i])
    return LCM

n = int(input())
t = []
for i in range(n):
    t.append(int(input()))

print(lcm(t))

Measured memory_bytes: 5048
def Push(A,B):
	if A<=B:
		return B,A,B-1
	else:
		return A,A-1,B

def resolve():
	A,B=map(int,input().split())
	ans=0
	k,A,B=Push(A,B)
	ans+=k
	k,A,B=Push(A,B)
	ans+=k
	print(ans)

resolve()

Measured memory_bytes: 38384
#include<stdio.h>
int main(){
  int i,n,m,c[100010],a,b,r[100010]={1};
  scanf("%d %d",&n,&m);
  for(i=0;i<n;i++)c[i]=1;
  while(m--){
    scanf("%d %d",&a,&b);
    c[--b]++;
    c[--a]--;
    r[b]|=r[a];
    if(c[a]==0)r[a]=0;
  }
  for(i=m=0;i<n;i++)m+=r[i];
  printf("%d\n",m);
  return 0;
}


Measured memory_bytes: 896
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cout << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//#define int long long

void solve() {
	string s; cin >> s;
    int n = (int)s.size();
    vector<int> a(n + 1, 0);
    rep(i, n) {
        a[i + 1] = (a[i] ^ (1<<(s[i] - 'a')));
    }
    vector<int> x((1<<26), inf);
    vector<int> dp(n + 1, inf);
    dp[0] = 0;
    x[0] = 0;
    rep(i, n) {
        int y = (a[i + 1] ^ 0);
        chmin(dp[i + 1], x[y] + 1);
        chmin(x[a[i + 1]], dp[i + 1]);
        for(int bit = 0; bit < 26; ++bit) {
            int mask = (1<<bit);
            int y = (a[i + 1] ^ mask);
            chmin(dp[i + 1], x[y] + 1);
            chmin(x[a[i + 1]], dp[i + 1]);
        }
    }
    cout << dp[n] << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 264340
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <deque>
using namespace std;
using P = pair<int,int>;
typedef long long int ll;
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)

int main(){ 
    int n;
    cin >> n;
    map<string,int>mp;
    rep(i,n){
        string s;
        cin >>s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
    ll ans = 0;
    for(auto p:mp){
        int s = p.second;
        ans += (ll)s*(s-1)/2;
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i=0;i<n;i++) cin >> v[i];
    int S = 0;
    for (int i=0;i<n;i++) S += v[i];
    vector<pair<int, int> > a;
    for (int i=0;i<n;i++) a.push_back(make_pair(abs(S-v[i]*n), i));
    sort(a.begin(), a.end());
    cout << a[0].second;


}


Measured memory_bytes: 256
function Main(input){
    input = input.split("\n");
    var arr = input[1].split(" ").map(Number).sort(function(a,b){return a-b;});
    //console.log(arr)
    //console.log(arr)
    for(var i=0;i<Math.floor(arr.length/2)*2;i+=2){
      //  if(!arr[i+1]) break;
    //    console.log([i,arr[i],arr[i+1]])
        if(arr[i]<=0&&arr[i+1]<=0){
            arr[i]*=-1;
            arr[i+1]*=-1;
        }else if(arr[i]<0){
            if(arr[i]*-1>arr[i+1]){
                arr[i]*=-1;
                arr[i+1]*=-1;
            }
        }
    }
  //  console.log(arr)
    var sum = 0n;
    arr.forEach(function(val){
    //    console.log(val)
        sum += BigInt(val);
    });
    console.log(sum.toString())
}Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());


Measured memory_bytes: 45744
#include <stdio.h>
#include <string.h>
int main(){
  char str[10];
  scanf("%s",str);
  int i;
  int count = 0;
  int count_max = 0;
  for(i=0; i<strlen(str); i++){
    if(str[i]=='A'||str[i]=='C'||str[i]=='G'||str[i]=='T'){
      count++;
      if(count>count_max)
        count_max=count;
    }
    else
      count=0;
  }
  printf("%d\n",count_max);
  
  return 0;
}

Measured memory_bytes: 128
import sys
#input = sys.stdin.readline
from sys import setrecursionlimit
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N, X = inpl()
L = inpl()[::-1]
D = 0
ans = 1
D += L.pop()
while D <= X:
    ans += 1
    if len(L):
        D += L.pop()
    else:
        break
print(ans)

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

long long MOD=1000000007LL;

long long fac[111111],finv[111111],inv[111111];
 
void COMinit(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<111111;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(){
	int N;
	cin >> N;
	vector<int> a(N+1);
	for(auto &i:a)cin >> i;
	for(auto &i:a)i--;
	int w1,w2;
	
	vector<long long> ans(N+1,0);
	
	vector<bool> exist(N,false);
	for(int i=0;i<N+1;i++){
		if(exist[a[i]]){
			w2=i;
			break;
		}
		exist[a[i]]=true;
	}
	for(int i=0;i<w2;i++)if(a[i]==a[w2])w1=i;
	
	COMinit();
	
	ans[0]=N;
	ans[N]=1;
	for(int k=2;k<=N;k++){
		ans[k-1]+=COM(N-1,k);
		ans[k-1]+=COM(N-1,k-2);
		ans[k-1]+=COM(N-1,k-1)*2;
		ans[k-1]-=COM(N+1-(w2-w1+1),k-1);
		ans[k-1]+=MOD;
		ans[k-1]%=MOD;
	}
	for(auto &i:ans)cout << i << endl;
	return 0;
}

Measured memory_bytes: 4992
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Configuration;
using System.Diagnostics;

namespace test
{

    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            double debt = 100000;
            for (int i = 0; i < n; i++)
            {
                debt *= 1.05;
                if (debt % 1000 != 0)
                {
                    debt = debt - (debt % 1000) + 1000;
                }
            }

            Console.WriteLine(debt);

        }


    }
        
}

Measured memory_bytes: 19980
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define deb(x) cout<<#x<<" "<<x<<endl;
#define deb2(x, y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define deb3(x, y, z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define all(x) x.begin(), x.end()
#define sz(a) int((a).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

template <typename T>void print(T v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<v.size(); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto i= v.begin(); i!=v.end(); i++)cout<<setw(w)<<*i<<" ";cout<<endl;}
template <typename T>void print_vv(T v){if(v.size()==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<v[0].size(); j++)cout<<setw(w)<<j<<" ";cout<<endl;for(auto i= 0; i<v.size(); i++){cout<<i<<" {";for(auto j = 0; j!=v[i].size(); j++){cout<<setw(w)<<v[i][j]<<",";}cout<<"},"<<endl;}cout<<endl;}
template <class T, class U> void print_m(map<T,U> m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}

int main(){
    int s, w;
    cin>>s>>w;
    if(w>=s){
        cout<<"unsafe"<<endl;
    }else{
        cout<<"safe"<<endl;
    }
    return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
const int nmax = 200;
int a[nmax],n;
int main(){
    scanf("%d",&n);
    for(int i = 1;i<=n;++i) scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    printf("%d\n",abs(a[1]-a[n]));
    return 0;
}

Measured memory_bytes: 256
use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };

    let n = sc.read();
    let a: Vec<u64> = sc.vec(n);
    if n == 2 {
        if a[0] == a[1] {
            println!("YES");
        } else {
            println!("NO");
        }
        return;
    }
    let mut tree = vec![vec![]; n];
    for _ in 1..n {
        let a = sc.read::<usize>() - 1;
        let b = sc.read::<usize>() - 1;
        tree[a].push(b);
        tree[b].push(a);
    }

    for i in 0..n {
        if tree[i].len() > 1 {
            match dfs(i, i, &tree, &a) {
                Some(up) if up == 0 => println!("YES"),
                _ => println!("NO"),
            }
            return;
        }
    }
}

fn dfs(v: usize, p: usize, tree: &Vec<Vec<usize>>, a: &Vec<u64>) -> Option<u64> {
    if tree[v].len() == 1 {
        return Some(a[v]);
    }
    let mut sum = 0;
    let mut max = 0;
    for &next in tree[v].iter() {
        if p == next {
            continue;
        }
        match dfs(next, v, tree, a) {
            Some(next) => {
                sum += next;
                max = cmp::max(max, next);
            }
            None => {
                return None;
            }
        }
    }
    if 2 * a[v] < sum {
        return None;
    }
    let up = 2 * a[v] - sum;
    if sum < up {
        return None;
    }
    let connecting = (sum - up) / 2;
    if connecting + up < max {
        return None;
    }
    Some(up)
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 20476