akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

using namespace std;
typedef unsigned long long int ll;

const ll INF = ((ll)1<<31) - (ll)1;

// ????????????????????±
template <typename T>
struct node {
	T v;
	node(){
		v = INF;
	}
	// ?????????????????´??°
	void update(T _v){
		v = _v;
	}
	// ??????????????´??°
	void merge(T vl, T vr){
		v = min(vl, vr);
	}
	// ????????????????????????
	T get(){
		return v;
	}
};

template <typename T, typename NODE=node<T> >
class SegTree{
public:
	vector<NODE> data;
	int N;
	SegTree(int _N){
		// _N <= (N = 2^k) ???????????????
		N = 1;
		while( N < _N ) N<<=1;
		data.resize(N*2+5);
	}

	// ?????°???????????????????????´??°
	void update(int l, T v){
		if( l >= N ) return;
		int k = l + N;	// ???????????????
		data[k].update(v);
		updateNode( k/2 );
	}
	// ???????????????????????£?????´??°
	void updateNode(int k){
		if( k <= 0 ) return;	// ???????????¶
		data[k].merge( data[k*2].get(), data[k*2+1].get() );
		updateNode(k/2);	// ??????
	}

	// ???????????? [l,r)
	T get(int l, int r=-1, int a=0, int b=-1, int k=1){
		if( r == -1 ) r = l+1;
		if( b == -1 ) b = N;
		//cout << l << " " << r << " " << a << " " << b << " " << k << endl;
		NODE nd;
		// ?????¨?????????????????´???
		if( l <= a && b <= r ) return data[k].get();
		// ?????¨?????????????????´???
		if( r <= a || b <= l ) return nd.get();
		// ?????????????????????????????´???
		int m = (a+b) / 2;
		T vl = get(l,r, a, m, k*2);
		T vr = get(l,r, m, b, k*2+1);
		nd.merge( vl, vr );
		return nd.get();
	}
};



// ?¢????

#include <algorithm>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()

typedef pair<int,int> pii;


// AOJ DSL_2_A
SegTree<ll> sg(100005);
int main(){
	int n, q;
	cin >> n >> q;
	rep(i,q){
		int c, x, y;
		cin >> c >> x >> y;
		if( c == 0 ){
			sg.update(x, y);
		}else{
			y++;
			cout << sg.get(x, y) << endl;
		}
		//rep(j,18) cout << sg.data[j].get() << " "; cout << endl;
	}
	return 0;
}


// arc026_C
/*
SegTree<ll> sg(100005);
int main(){
	int N, L;
	ll l[100005], r[100005], c[100005];
	vector<pii> v;

	cin >> N >> L;
	rep(i,N){
		cin >> l[i] >> r[i] >> c[i];
		v.emplace_back( r[i], i );
	}
	sort( all(v) );

	sg.update(0,0);
	for(auto p: v){
		int i = p.second;
		ll tmp = min( sg.get(r[i]), sg.get(l[i], r[i]+1) + c[i] );
		sg.update( r[i], tmp );
	}

	cout << sg.get(L) << endl;

	return 0;
}
*/

Measured memory_bytes: 4772
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string>
using namespace std;

int main(){
	string x;
	int i;
	while(getline(cin, x)){
		for(i = 0;i < x.size();i++){
			if(x[i] >= 'a' && x[i] <= 'a' + 25){
				x[i] = 'A' + (x[i] - 'a');
			}
		}
		cout << x << endl;
	}

	return 0;
}

Measured memory_bytes: 1172
ls = []
for i in range(3):
    ls.append(list(input().split(' ')))

N = int(input())
for i in range(N):
    X = input()
    for i in range(3):
        if X in ls[i]:
            ls[i][ls[i].index(X)] = 0

result = False
for i in range(3):
    if ls[i].count(0) == 3:
        result = True
        break

if not result:
    for i in range(3):
        cnt = 0
        for j in range(3):
            if ls[j][i] == 0:
                cnt += 1
        if cnt == 3:
            result = True
            break

if not result:
    cnt = 0
    for i in range(3):
        if ls[i][i] == 0:
            cnt += 1
    if cnt == 3:
        result = True

if not result:
    cnt = 0
    for i in range(3):
        if ls[i][3-i-1] == 0:
            cnt += 1
    if cnt == 3:
        result = True

if result:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9132
import math
import collections
import fractions
import itertools

def solve():
    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    x.sort()
    if n >= m:
        print(0)
    else:
        diff = [abs(x[i] - x[i+1]) for i in range(m-1)]
        diff.sort(reverse=True)
        ans = sum(diff)
        for i in range(n-1):
            ans -= diff[i]
        print(ans)
    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 21844
import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    aclist = [0] * N
    wrongcount = [0] * N
    for _ in range(M):
        p, S = readline().split()
        q = int(p)-1
        if aclist[q] == 0 and S == 'WA':
            wrongcount[q] += 1
        if S == 'AC':
            aclist[q] = 1

    pena = 0
    for i in range(N):
        if aclist[i] == 1:
            pena += wrongcount[i]
    ac = sum(aclist)

    print(ac, pena)


if __name__ == "__main__":
    main()


Measured memory_bytes: 4596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll p = 1e9+7;

ll n, h[105], dp[105][105], k;
map<int, int> m;
vector<int> v;

ll exp(ll x, ll k) {
	if (k < 0)
		return 0;
	if (k == 0)
		return 1;
	if (k%2 == 1)
		return x*exp(x, k-1)%p;
	ll y = exp(x, k/2);
	return y*y%p;
}

//alternate in first h1 squares
//does not alternate in first h2 squares
//total length x
ll ctalt(ll h1, ll h2, ll x) {
	if (h1 >= h2)
		return 0;
	ll ct1 = 0, ct2 = 0;
	if (h1 == 0)
		ct1 = exp(2, x);
	else
		ct1 = 2*exp(2, x-h1);
	if (h2 == 0)
		ct2 = exp(2, x);
	else
		ct2 = 2*exp(2, x-h2);
	return (p+ct1%p-ct2%p)%p;
}

int main() {
	cin >> n;
	v.push_back(0);
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
		if (m.count(h[i]) > 0)
			continue;
		m[h[i]] = 1;
		v.push_back(h[i]);
	}
	sort(v.begin(), v.end());
	k = v.size();
	v.push_back(1000000005);

	for (int i = 0; i < n; ++i) {
		if (i == 0) {
			for (int j = 0; j < k; ++j) {
				dp[i][j] = ctalt(v[j], v[j+1], h[i]);
			}
			continue;
		}

		int t = 0, t1 = 0;
		for (int j = 0; j < k; ++j) {
			if (h[i] == v[j])
				t = j;
			if (h[i-1] == v[j])
				t1 = j;
		}

		for (int j = 0; j <= t1; ++j) {
			if (h[i] <= h[i-1]) {
				if (v[j] >= h[i])
					dp[i][t] = (dp[i][t] + 2*dp[i-1][j])%p;
				else
					dp[i][j] = (dp[i][j] + dp[i-1][j])%p;
			} else {
				if (j < t1) {
					dp[i][j] = (dp[i][j] + dp[i-1][j]*exp(2, h[i]-h[i-1]))%p;
				} else {
					ll x = dp[i-1][j];
					for (int jj = t1; jj < k; ++jj)
						dp[i][jj] = (dp[i][jj] + x*ctalt(v[jj], v[jj+1], h[i]))%p;
				}
			}
		}
	}

	ll ans = 0;
	for (int j = 0; j < k; ++j)
		ans = (ans + dp[n-1][j])%p;
	cout << ans << endl;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define in(x) cin >> x
#define out(str) cout << str << endl

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

int A,B,C,D;

int main(){
    cin>>A>>B>>C>>D;
    if((A+B)==(C+D)){
        out("Balanced");
    }
    else if((A+B)>(C+D)){
        out("Left");
    }
    else{
        out("Right");
    }
}


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

using namespace std;

int main(){
    int N,A,B,sum=0;
    cin>>N>>A>>B;

    int i=N;
    while(i>0){
        int tmp=i,num=0;
        while(tmp>0){
            num += tmp%10;
            tmp/=10;
        }
        if(num>=A&&num<=B)
            sum += i;
        i--;
    }
    cout<<sum;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    map<string, int> mp;
    rep(i, n) {
        cin >> s[i];
        mp[s[i]]++;
    }

    cout << "AC x " << mp["AC"] << endl;
    cout << "WA x " << mp["WA"] << endl;
    cout << "TLE x " << mp["TLE"] << endl;
    cout << "RE x " << mp["RE"] << endl;
}

Measured memory_bytes: 6432
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
#define Graph vector<vector<int>>
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)
#define inf 1000000321
#pragma GCC optimize("Ofast")
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S;
    cin >> S;
    ll ans = 0;
    bool ok = true;
    if(S.size() == 1){cout << S << endl;
    return 0;
    }
    ll pre = 0;
    for(int i = 0;i < S.size();i++){
        if(S[i] != '9')ok = false;
        pre += S[i] - 48;
    }
    if(ok){
        cout << S.size()*9 << endl;
        return 0;
    }
    ans += S[0] - 48 - 1 + 9*(S.size()-1);
    cout<< max(ans,pre) << endl;
}   

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


void solve(long long A, long long B, long long C, long long D){
    if(A + B > C + D) cout << "Left" << endl;
    if(A + B == C + D) cout << "Balanced" << endl;
    if(A + B < C + D) cout << "Right" << endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    long long D;
    scanf("%lld",&D);
    solve(A, B, C, D);
    return 0;
}


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

int main() {
	int N;
	cin >> N;
	vector<int> d(N);
	for (int& i : d) cin >> i;
	sort(d.begin(), d.end());
	d.erase(unique(d.begin(), d.end()), d.end());
	cout << d.size();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	long long n,x,y;cin >> n >> x >> y;
	if(x%2==y%2) cout << (y-x)/2 << '\n';
	else cout << min((x+y-1)/2,(n-x+n-y+1)/2) << '\n';
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
#include <set>
using namespace std;

//ABC161_C
int main() {
	long long N, K;
	cin >> N >> K;

	N %= K;
	cout << min(N, K-N) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  string H;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> H;
    if (H == "Y") {
      cout << "Four" << endl;
      break;
    }
  }
  if (H != "Y") {
    cout << "Three" << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		HashMap hs = new HashMap();
		PrintWriter ou = new PrintWriter(System.out);
		int n = Integer.parseInt(sc.next()) - 1;
		int m = Integer.parseInt(sc.next());
		int[][] s = new int[2][m];
		for(int i = 0 ; i < m ; i++){
			for(int j = 0 ; j < 2 ; j++){
				s[j][i] = Integer.parseInt(sc.next());
			}
			s[0][i]--;
			s[1][i] += 48;
		}
		sc.close();
		boolean ebishu = true;
		boolean yyyy = true;
		int k = 0;
		if(n == 0){
			if(m == 0){
				ou.print(0);
				ebishu = false;
			}else{
				yyyy = false;
				for(int i = 0 ; i < 10 ; i++){
					boolean ebi = true;
					for(int j = 0 ; j < m && ebi ; j++){
						if(s[1][j] - 48 != i) ebi = false;
					}
					if(ebi){
						ou.print(i);
						ebishu = false;
					}
				}
				if(ebishu){
					ou.print(-1);
					ebishu = false;
				}
			}
		}
		for(k = (int)Math.pow(10 , n) ; yyyy && k < (int)Math.pow(10 , n + 1) && ebishu ; k++){
			String ss = String.valueOf(k);
			boolean ebi = true;
			for(int i = 0 ; i < m && ebi ; i++){
				if((int)ss.charAt(s[0][i]) != s[1][i]) ebi = false;
			}
			if(ebi){
				ou.print(k);
				ebishu = false;
				break;
			}
		}
		if(ebishu) ou.print(-1);
		ou.print("\n");
		ou.flush();
	}
}

Measured memory_bytes: 35904
#include<iostream>
#include<string>
#include<iomanip>

double n,k;

double res;

int main(){

    std::cin>>n>>k;

    for(int i=1;i<=n;i++){
        double kk=k,one=1;
        while(kk>i){
            kk/=2;
        }
        res+=kk/k;
    }

    res/=n;

    std::cout<<std::setprecision(13)<<res<<std::endl;

    return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long int n,k;
    cin>>n>>k;
    vector<long int> height(n);
    for(long int i=0;i<n;i++)
    cin>>height[i];
    long int cost[n+1];
    cost[0]=0;
    cost[1]=0;
    for(int i=2;i<n+1;i++)
    cost[i] = INT_MAX;
    for(long int i=2;i<n+1;i++)
    {
        for(int j=1;j<=k;j++)
        {
            if(i>j)
            {
                cost[i]= min(cost[i],cost[i-j]+abs(height[i-1]-height[i-j-1]));
            }
        }
    }
    cout<<cost[n]<<endl;
    return 0;
}

Measured memory_bytes: 1792
#define _CRT_SECURE_NO_DEPRECATE
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include "bits/stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define int long long int
#define SYNC std::ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii>   vii;
//typedef tree<int, null_type, less<int>, rb_tree_tag, 
//             tree_order_statistics_node_update> 
//    ost;
#define rep(i,l,r)   for (int i = (l); i < (r); i++)
#define here cout << " Hey!!\n";
#define  pb push_back
#define  F  first
#define  S  second
#define all(v) (v).begin(),(v).end()
#define sz(a) (int)((a).size())
#define sq(x) ((x)*(x))
template <typename T>
void etch(T V) {
	for (auto x : V)	cout << x << ' ' ;
	cout << '\n';
}
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
const int MOD = 1e9+7;
const int MOD1 = 998244353;
const int N = 2e5+5;
const int INF = 1000111000111000111LL;
const ld EPS = 1e-12;
const ld PI = 3.141592653589793116;

int32_t main()
{
	SYNC
	int n; cin >> n;
	vector<ld> v(n);
	map <pair<int, int> , int> dp;
	rep(i,0,n)	{
		cin >> v[i];
		v[i] = v[i] * 1e9;
		int x = (int)(v[i] + 0.1);
		int c2 = 0, c5 = 0;
		while (x % 2 == 0) {
			x /= 2;
			c2++;
		}
		while (x % 5 == 0) {
			x /= 5;
			c5++;
		}
		dp[{c2, c5}]++;
	}
	vector< pair<ii, int> > a;
	for (auto it : dp) {
		a.pb({it.F, it.S});
	}
	int ans = 0;
	for (int i = 0; i < sz(a); i++) {
		for (int j = i+1; j < sz(a); j++) {
			if (min(a[i].F.F+a[j].F.F, a[i].F.S + a[j].F.S) >= 18) {
				ans += (a[i].S * a[j].S);
			}
		}
		if (min(a[i].F.F, a[i].F.S) >= 9) {
			ans += (a[i].S*(a[i].S-1))/2;
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 6344
import java.util.Scanner;

public class Main{
	public static void main(String [] args) {
		Scanner sc = new Scanner(System.in);
		double D = sc.nextDouble();
		double T = sc.nextDouble();
		double S = sc.nextDouble();
		if((D/S) <= T)		System.out.println("Yes");
		else				System.out.println("No");
		sc.close();
	}

}


Measured memory_bytes: 37212
N = int(input())
a = 0
b = 0
c = 0
v = 0

for i in range(N):
    S = input()
    for j in range(len(S)-1):
        if S[j:j+2] == 'AB':
            c += 1
    if S[0] == 'B' and S[-1] == 'A':
        v += 1
        continue
    if S[0] == 'B':
        b += 1
    if S[-1] == 'A':
        a += 1
'''
if v >= 1:
    if a < b:
        a += 1
    else:
        b += 1
'''
if a >= 1 or b >= 1:
    print(c + v + min(a, b))
else:
    print(c + max(0, v-1))


Measured memory_bytes: 51672
# 入力
N, A, B, C = map(int, input().split())

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(
                pow(self.x, other.x, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    def __radd__(self, other):
        return ModInt(other + self.x)

    def __rsub__(self, other):
        return ModInt(other - self.x)

    def __rmul__(self, other):
        return ModInt(other * self.x)

    def __rtruediv__(self, other):
        return ModInt(other * pow(self.x, MOD - 2, MOD))

    def __rpow__(self, other):
        return ModInt(pow(other, self.x, MOD))


# f[n] = n! % (10**9 + 7)
f = [0 for _ in range(2 * N)]
f[0] = ModInt(1)
for i in range(1, 2 * N):
    f[i] = i * f[i - 1]

# 引き分けなしの分母
D = ModInt(100 - C)
# 1回のゲームにつき、高橋君が勝つ確率
p = A / D
# 1回のゲームにつき、青木君が勝つ確率
q = B / D

# 高橋君がN回、青木君がi回勝つケースの重み付き期待値の和、および
# 高橋君がi回、青木君がN回勝つケースの重み付き期待値の和
# を求めそれらの和を解とする
ans = (100 / D) * sum(
    (N + i) * (f[N + i - 1] / (f[i] * f[N - 1])) * (p**N * q**i + p**i * q**N)
    for i in range(N)
)

# 出力
print(ans)


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

char buf[100];
int main() {
	int q; cin >> q;
	rep(i, q) {
		ll s; scanf("%llx", &s);
		string t = bitset<32>(s).to_string();
		string a = t.substr(1, 24);
		int b = 0, p = 1;
		for (int i = a.size() - 1; i >= 0; i--) {
			b += p*(a[i] - '0'); p *= 2;
		}
		double d = 0, y = 0.5;
		string c = t.substr(25);
		rep(i, c.size()) {
			d += y*(c[i] - '0'); y /= 2;
		}
		double ans = b + d;
		if (t.front() == '1')ans = -ans;
		sprintf(buf, "%.50lf", ans);
		string u = buf;
		while (u.back() == '0')u.pop_back();
		if (u.back() == '.')u.pop_back();
		if ((int)u.find('.') == -1)u += ".0";
		cout << u << endl;
	}
}

Measured memory_bytes: 3276
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
typedef long long ll;


int main()
{
  ll M;
  cin >> M;
  ll d, c;
  ll S = 0;
  ll ans = -1;
  for (ll i = 0; i < M; ++i)
  {
    cin >> d >> c;
    S += d * c;
    ans += c;
  }
  while (S / 10 != 0)
  {
    ans += S / 10;
    S = S / 10 + S % 10;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import math
import numpy as np


def inputIntList():
    return [int(s) for s in input().split()]


def inputInt():
    return int(input())


def main():
    N = inputInt()
    act = [inputIntList() for _ in range(N)]
    act.append([0, 0, 0])
    dp = [[0 for _ in range(3)] for _ in range(N + 1)]
    dp[0] = act[0]
    for i in range(1, N + 1):
        for j in range(3):
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j - 2]) + act[i][j]
            # print(dp)

    return max(dp[-1])


if __name__ == "__main__":
    print(main())


Measured memory_bytes: 54652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)

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

    int N,M; cin >> N >> M;
    vei L(M),R(M);
    rep(i,M) cin >> L[i] >> R[i];
    if(maxel(L) > minel(R)) cout << 0 << endl;
    else cout << minel(R) - maxel(L) + 1 << endl;
    return 0;

}

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

int main() {
  int N;
  cin >> N;
  
  vector<int> H(N);
  for( int i = 0; i < N; i++ ) cin >> H.at(i);
  
  int count = 0;
  int ans = 0;
  for( int i = 0; i < N-1; i++ ){
    if( H.at(i) >= H.at(i+1) ){
      count++;
      ans = max(count, ans);
    }else{
      ans = max(count, ans);
      count = 0;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<ll>;
using VV = vector<VI>;
using VS = vector<string>;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl

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

    // input
    ll N; cin >> N;
    VI A(N);
    rep(i, N){
        cin >> A.at(i);
    }
    sort(ALL(A));

    if(N%2==0){
      // N型
      ll sum = 0;
      // 係数2
      ll L = N-2;
      rep(i, L/2){
        sum -= 2 * A[i];
        sum += 2 * A[N-1-i];
      }
      sum += A[N/2];
      sum -= A[N/2-1];
      p(sum);
    }
    else{
      // M型
      ll sum = 0;
      rep(i, (N+1)/2){
        ll c;
        if(i==N/2 || i==N/2-1){
          c = 1;
        }else{
          c = 2;
        }
        sum -= c * A[i];
      }
      FOR(i, (N+1)/2, N){
        sum += 2*A[i];
      }

      // W型
      ll sum2 = 0;
      FOR(i, N/2, N){
        ll c;
        if(i==N/2 || i==N/2+1){
          c = 1;
        }else{
          c = 2;
        }
        sum2 += c * A[i];
      }
      FOR(i, 0, N/2){
        sum2 -= 2 * A[i];
      }

      ll ans = max(sum, sum2);
      p(ans);
    }
    
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T, class T2> void smin(T& a, T2 val) {if (a > val) a = val;}template<class T, class T2> void smax(T& a, T2 val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int x, k, d;

int32_t main(){_
   
   cin >> x >> k >> d;

   x = abs(x);

   int currmoves = x / d;

   if (currmoves >= k){
      int ans = abs(x - k  * d);
      k -= 2;
      if (k >= 0){
         smin(ans, abs(x - k  * d));         
      }
      k -= 2;
      if (k >= 0){
         smin(ans, abs(x - k  * d));         
      }
      cout<<ans;
      exit(0);
   }

   int position = x - currmoves * d;
   tr(currmoves, position);

   int ans = 4e18;
   if (currmoves % 2 == k % 2){
      ans = abs(position);
   }

   if (currmoves + 1 <= k){
      currmoves++;
      position -= d;
      if (currmoves % 2 == k % 2){
         smin(ans, abs(position));
      }
   }

   if (currmoves + 1 <= k){
      currmoves++;
      position -= d;
      if (currmoves % 2 == k % 2){
         smin(ans, abs(position));
      }
   }

   currmoves = x / d;
   --currmoves;
   if (currmoves >= 0 and currmoves % 2 == k % 2){
      smin(ans, abs(x - currmoves * d));
   }

   --currmoves;
   if (currmoves >= 0 and currmoves % 2 == k % 2){
      smin(ans, abs(x - currmoves * d));
   }

   cout<<ans;
   return 0;
}

Measured memory_bytes: 3648
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // TODO 自動生成されたメソッド・スタブ
        Scanner scanner = new Scanner(System.in);
        int W = scanner.nextInt();
        int H = scanner.nextInt();
        int x = scanner.nextInt();
        int y = scanner.nextInt();
        int r = scanner.nextInt();
        if( x-r >= 0 && x + r <= W && y-r >=0 && y + r<=H){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }

    }

}


Measured memory_bytes: 26396
-- | Main entry point to the application.
module Main where

import Control.Applicative
import Control.Monad
import Data.List
import Debug.Trace
import Text.Printf

rInt :: String -> Int
rInt str = read str :: Int

findDiv :: Int -> Int -> Int -> Int
findDiv a b c
    | a > b = 0
    | a <= b && c `mod` a == 0 = 1 + findDiv (a+1) b c
    | a <= b && c `mod` a > 0 = 0 + findDiv (a+1) b c

-- | The main entry point.
main :: IO ()
main = do
    [a, b, c] <- (map rInt . words) <$> getLine
    --s <- getContents
    printf "%d\n" $ findDiv a b c

Measured memory_bytes: 4632
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <algorithm>

#define MOD7 1000000007
#define MOD9 1000000009

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

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int nextInt() {int a; cin >> a; return a;}
char nextChar() {char a; cin >> a; return a;}
double nextDouble() {double a; cin >> a; return a;}
string nextString() {string a; cin >> a; return a;}

void inputVector(vector<int> &v, int &n) {rep(i,n){v.push_back(nextInt());}}
void inputVector(vector<double> &v, int &n) {rep(i,n){v.push_back(nextDouble());}}
void inputVector(vector<string> &v, int &n) {rep(i,n){v.push_back(nextString());}}

signed main() {
    int n, k, m;
    while (cin >> n >> k >> m) {
	if (n == 0) break;

	int left = n;
	int now = m - 1;
	vector<int> v;

	REP(i, 1, n) v.push_back(i);
	rep(i, n - 1) {
	    v.erase(v.begin() + now);
	    m--;
	    left--;

	    now += (k - 1) % left;
	    now %= left;
	}
	cout << v[0] << endl;
    }

    return 0;
}

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

int main() {
  int A, B, K;
  
  cin >> A >> B;
  
  if (  ( ( A+B ) % 2 ) == 1  ) {
    
    cout << " IMPOSSIBLE " << endl;
    
  } else if ( A == B ) {
    
    cout << " IMPOSSIBLE " << endl;
    
  } else {
    
    K = ( A+B ) / 2;
      
    cout << K << endl;
  }
  
}

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

int main() {
  int k, s;
  cin >> k >> s;
  int c = 0;

  for(int x = 0; x <= k; x++){
    for(int y = 0; y <= k; y++){
      int z = s - x - y;
      if(0 <= z && z <= k){
        c++;
      }
    }
  }
  cout << c << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cinttypes>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<stack>


#define FSCNd64 "%" SCNd64
#define FPRId64 "%" PRId64

using namespace std;

using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
using vll=vector<ll>;
using vvll=vector<vll>;
using vpii=vector<pii>;

#define PI 3.1415926535897932384626433832795

template<typename X>
bool max_u(X&m, X v)
{
	if(m<v)
	{
		m=v;
		return true;
	}
	return false;
}


template<typename X>
bool min_u(X&m, X v)
{
	if(m>v)
	{
		m=v;
		return true;
	}
	return false;
}


struct solve
{
	solve(){}
	ll operator()() {
		return 0;
	}
};

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

	for(;;)
	{
		int a;
		cin >> a;
		if(cin.fail()) break;
		int ans=((a+1)*a+1)*a;
		cout << ans << "\n";
	}
	return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int main () {
  string S;
  cin >> S;
  long flag = -1, cos = 0, cot = 0, ans = 0;
  for(int i = 0; i < S.size(); i++){
    if(flag == -1 && S.at(i) == 'T')continue;
    else if(flag == -1 && S.at(i) == 'S'){
      flag = 1;
      cos++;
      continue;
    }
    if(flag == 1 && S.at(i) == 'S')cos++;
    else if(flag == 0 && S.at(i) == 'T')cot++;
    else if(flag == 0 && S.at(i) == 'S'){
      if(cos > cot){
        ans += cot;
        cos -= cot;
        cot = 0;
      } else {
        ans += cos;
        cos = 0;
        cot = 0;
      }
      flag = 1;
      cos++;
    } else if(flag == 1 && S.at(i) == 'T'){
      flag = 0;
      cot++;
    }
  }
  ans += min(cos, cot);
  cout << S.size() - 2 * ans << endl;
  return 0;
}

Measured memory_bytes: 640
def examC():
    N = I()
    d = defaultdict(int)
    for i in range(N):
        curD = defaultdict(int)
        S = SI()
        for s in S:
            curD[s]+=1
        if i==0:
            d = curD
            continue
        for s in alphabet:
            d[s] = min(d[s],curD[s])
    d = sorted(d.items())
    ans = ""
    for key,i in d:
        ans +=key*i
    print(ans)
    return

def examD():
    N, M = LI()
    X = LI(); Y = LI()
    distX = [0]*N; distY = [0]*M
    for i in range(N-1):
        distX[i+1] = X[i+1]-X[i]
    for i in range(M-1):
        distY[i+1] = Y[i+1]-Y[i]
    numX = [0]*N; numY = [0]*M
    for i in range(N):
        numX[i] = i*(N-i)
    for i in range(M):
        numY[i] = i*(M-i)
    LX = 0; LY = 0
    for i in range(N):
        LX += distX[i]*numX[i]
        LX %= mod
    for i in range(M):
        LY += distY[i]*numY[i]
        LY %= mod
#    print(numX,distX); print(numY,distY)
    ans = (LX*LY) % mod
    print(ans)
    return

def examE():
    S = SI(); T = SI()
    numaS = [0]*(len(S)+1)
    numaT = [0]*(len(T)+1)
    for i,s in enumerate(S):
        numaS[i+1] = numaS[i]
        if s=="A":
            numaS[i+1] +=1
    for i,s in enumerate(T):
        numaT[i+1] = numaT[i]
        if s=="A":
            numaT[i+1] +=1
#    print(numaS); print(numaT)
    Q = I()
    ans = ["YES"]*Q
    for i in range(Q):
        a,b,c,d = LI()
        curaS = numaS[b] - numaS[a-1]
        curbS = (b-a)-curaS+1
        curaT = numaT[d] - numaT[c-1]
        curbT = (d-c)-curaT+1
#        print(curaS,curbS,curaT,curbT)
        if (curaS%3+(curaS+curbS)%3)%3 != (curaT%3+(curaT+curbT)%3)%3:
#            if (curbS % 3 + (curaS + curbS) % 3) % 3 != (curbT % 3 + (curaT + curbT) % 3) % 3:
            ans[i]="NO"
    for v in ans:
        print(v)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()


Measured memory_bytes: 10320
#!/usr/bin/perl

$line == 0;
while(<>) {
    chomp;
    if ($line == 0) {
    } else {
        @n = split /\s+/, $_;
        push @l, $n[0];
        push @r, $n[1];
    }
    $line++;
}

foreach $i (0 .. $#l) {
    $total += $r[$i] - $l[$i] + 1;
}
print "$total\n";


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

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

    set<int> d;
    for( int i = 0; i < N; ++i ){
        int dd;
        cin >> dd;
        d.insert(dd);
    }


    cout << d.size() << endl;

    return 0;
}


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

void solve(long long N, string S){
	vector<int> w2e;
	vector<int> e2w;
	int w = 0;
	int e = 0;
	for(size_t i = 0; i < S.length(); i++)
	{
		if (S.c_str()[i] == 'W') {
			w2e.push_back(++w);
			e2w.push_back(e);
		} else {
			w2e.push_back(w);
			e2w.push_back(++e);
		}
	}

	int ans = 9999999;
	for(size_t i = 0; i < N; i++)
	{
		int x = (i == 0) ? 0 : w2e[i-1];
		int y = (i == N-1) ? 0 : e2w[N-1] - e2w[i];
		ans = min(ans, x+y);
	}

	cout << ans << endl;
}

int main(){	
	long long N;
	string S;
	scanf("%lld",&N);
	cin >> S;
	solve(N, S);
	return 0;
}



Measured memory_bytes: 4980
#include <stdio.h>

int main(){
int a,b;
	scanf("%d%d",&a,&b);
	if(a>b){
		printf("a > b\n");
	}else if(a<b){
		printf("a < b\n");
	}else{
		printf("a == b\n");
	}
	return 0;
}

Measured memory_bytes: 580
#include <iostream>
#include <string>
#define llint long long

using namespace std;

int n;
string s;

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

  cin >> n >> s;

  if(n % 2) cout << "No" << endl;
  else{
    if(s.substr(n/2) == s.substr(0, n/2)) cout << "Yes" << endl;
    else cout << "No" << endl;
  }

  return 0;
}


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

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

    vector<int> v(n);

    for(auto& x : v) cin >> x;

    sort(begin(v), end(v));

    v.erase(unique(begin(v), end(v)), end(v));

    cout << v.size() << endl;

    return 0;
}

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

int main() {
    int N;
    cin >> N;
    ll ans = 0;
    for (ll x = 1; x <= N; ++x) {
        ll y = N / x;
        ans += x * (1 + y) * y / 2;
    }
    cout << ans << endl;
}



Measured memory_bytes: 3616
from functools import reduce

# 入力
W, H = map(int, input().split())
p = [int(input()) for _ in range(W)]
q = [int(input()) for _ in range(H)]

# クラスカル法に基づいて解を求める
ans, _, _ = reduce(
    lambda acc, c: (
        (
            acc[0] + (H - acc[2] + 1) * c[0] if c[1] == 0 else
            acc[0] + (W - acc[1] + 1) * c[0]
        ),
        (
            acc[1] + 1 if c[1] == 0 else
            acc[1]
        ),
        (
            acc[2] + 1 if c[1] == 1 else
            acc[2]
        )
    ),
    sorted([(P, 0) for P in p] + [(Q, 1) for Q in q]),
    (0, 0, 0)
)

# 出力
print(ans)


Measured memory_bytes: 28084
#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;


struct A{
	int n;
	int pena;
	int id;
	bool operator<(const A &a)const{
		if(n!=a.n)return n>a.n;
		if(pena!=a.pena)return pena<a.pena;
		return id<a.id;
	}
};
int main(){
	int T,P,R;
	int p[50][10];
	A team[50];
	while(cin>>T>>P>>R,T|P|R){
		memset(p,0,sizeof(p));
		for(int i=0;i<T;i++){
			team[i].n=team[i].pena=0;
			team[i].id=i+1;
		}
		while(R--){
			int a,b,c;
			string mes;
			cin>>a>>b>>c>>mes;
			if(mes=="WRONG")p[a-1][b-1]++;
			else{
				team[a-1].n++;
				team[a-1].pena += p[a-1][b-1]*1200+c;
			}
		}
		sort(team,team+T);
		for(int i=0;i<T;i++){
			cout<<team[i].id<<' '<<team[i].n<<' '<<team[i].pena<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1240
N = int(input())
P = list(map(int,input().split()))
Q = list(map(int,input().split()))
p = sum(P)
q = sum(Q)
if P == Q:
    print("Yes")
else:
    m = 0
    l = 0
    for i in range(N):
        if Q[i] - P[i] > 0:
            if (Q[i] - P[i]) % 2 == 1:
                #p += (P[i] - Q[i]) * 2
                m += (Q[i] - P[i] + 1) // 2
                l += 1
            else:
                m += (Q[i] - P[i]) // 2
        elif Q[i] - P[i] < 0:
            #q += (Q[i] - P[i])
            l += (P[i] - Q[i])
    if m >= l:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 4600
def main():
    n = int(input())
    dp = [[0 for i in range(10)] for i in range(10)]
    for i in range(1,n+1):
        h,t = int(str(i)[0]), int(str(i)[-1])
        dp[h][t] += 1
    ans = 0
    for i in range(10):
        for j in range(10):
            ans += dp[i][j] * dp[j][i]
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 9096
#include<iostream>
using namespace std;
int sum, n, a, b, ok;
int main() {
	while (true) {
		sum = 0;
		ok = 0;
		cin >> n;
		if (n == 0) { break; }
		for (int i = 0; i < 12; i++) {
			cin >> a >> b;
			sum += a - b;
			if (sum >= n && ok == 0) { cout << i + 1 << endl; ok = 1; }
		}
		if (ok == 0) { cout << "NA" << endl; }
	}
}

Measured memory_bytes: 1160
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
//	tmp = input[1].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(input[0], 10);
  var S = input[1];
  
	if (a%2 == 0 ){
        var p = a/2;
      var t = S.substr( 0, p );
      var tt = S.substr( -p );
     //  console.log(t,tt);
       if (t ==tt){console.log('Yes');}
       else{console.log('No');}
      
    }
    else{console.log('No')}
}
 
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
h, w, k = map(int,input().split())
c = [ [ ] for _ in range(h)]
for i in range(h):
    c[i] = list(input())

n=h + w
b=[]
for s in range(2**n):
    a=[1 if s >> i &1 else 0 for i in range(n)] 
    b.append(a)

from copy import deepcopy
count = 0

for part_b in b:
    m =0
    d = deepcopy(c)
    row = part_b[:h]
    col = part_b[h:]
    for i in range(len(row)):
        flg = row[i]
        if flg:
            d[i] = ["赤" for _ in range(w)]
    
    for i in range(len(col)):
        flg = col[i]
        if flg:
            for j in range(h):
        
                d[j][i]= "赤"
                
    for i in range(h):
        for j in range(w):
            if d[i][j] == "#":
                m +=1
    if m==k:
        count +=1
print(count)

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

int main(){
  int N,M;
  cin>>N>>M;
  char S[N];
  cin>>S;
  if(S[M-1] == 'A') S[M-1] = 'a';
  if(S[M-1] == 'B') S[M-1] = 'b';
  if(S[M-1] == 'C') S[M-1] = 'c';
  for(int i = 0;i < N;i++)cout<<S[i];

}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

struct edge{
	int to,co,p;
};

vector<edge> vs[105];

int ds[105];
void bfs(int st){
	queue<mp> que;
	que.push(mp(0,st));
	memset(ds,-1,sizeof(ds));
	while(!que.empty()){
		mp pa=que.front();
		que.pop();
		int no=pa.sec,
			nd=pa.fir;
		if(ds[no]>=0)continue;
		ds[no]=nd;
		rep(i,vs[no].size()){
			int to=vs[no][i].to,
				ec=vs[no][i].co;
			if(ec<=0 || ds[to]>=0)continue;
			que.push(mp(nd+1,to));
		}
	}
}

int seen[105];
int dfs(int no,int gl,int f){
	if(no==gl)return f;
	for(;;){
		if(seen[no]>=vs[no].size())break;
		edge& e=vs[no][seen[no]];
		if(e.co>0 && ds[no] < ds[e.to]){
			int tf=dfs(e.to,gl,min(f,e.co));
			if(tf>0){
				e.co-=tf;
				vs[e.to][e.p].co+=tf;
				return tf;
			}
		}
		seen[no]++;
	}
	return 0;
}

/*
??????????????????????????¨???

print "32 61"
for i in xrange(30):
	print ("%d %d %d" % (i,i+1,3))
	print ("%d %d %d" % (i,i+1,3))
print "0 31 1"

??§????????????
???????????????????????????gone?????\?????????????????????????????§????????????

?????£???????????¬???????£??????¨???????????????????????????iterate?????????????????????

(?????????AOJ??§?????????????????£???????????????????????????...)
*/

int dinic(int st,int gl){
	int res=0;
	for(;;){
		bfs(st);
		if(ds[gl]<0)break;
		memset(seen,0,sizeof(seen));
		for(;;){
			int f=dfs(st,gl,IINF);
			if(f<=0)break;
			res+=f;
		}
	}
	return res;
}
	
int n,m;
int main(void){
	scanf("%d%d",&n,&m);
	rep(i,m){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		edge e;
		e.to=b; e.co=c; e.p=vs[b].size();
		vs[a].push_back(e);
		e.to=a; e.co=0; e.p=vs[a].size()-1;
		vs[b].push_back(e);
	}
	printf("%d\n",dinic(0,n-1));
	return 0;
}

Measured memory_bytes: 1260
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
gp_hash_table<int, int> mp;*/
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = acos(-1);
const double eps = -1e6;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 200001;
ll dp[40][mxN];
vector<pair<ll, ll>> arr;
bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
    return (a.second+1)*b.first<a.first*(b.second)+1;
}
vector<int> zero;
int n, T;
int main()
{   
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>T;
    int a, b;
    owo(i, 0, n) {
        cin>>a>>b;
        if(a==0) {
            zero.senpai(b);
        }else {
            arr.senpai({a, b});
        }
    }
    sort(zero.begin(), zero.end());
    sort(arr.begin(), arr.end(), cmp);
    owo(i, 0, 40) {
        owo(j, 0, mxN) {
            dp[i][j] = T+1;
        }
    }
    dp[0][0] = 0;
    owo(i, 0, arr.size()) {
        //cout<<arr[i].first<<" "<<arr[i].second<<"\n";
        dp[0][i+1] = 0;
        owo(j, 1, 40) {
            dp[j][i+1] = min(dp[j][i+1], dp[j][i]);
            dp[j][i+1] = min(dp[j][i+1], dp[j-1][i] + 1 + (dp[j-1][i] + 1)*arr[i].first + arr[i].second);
            //cout<<i<<" "<<j<<" "<<dp[j][i+1]<<"\n";
        }
    }
    int mx = 0;
    owo(i, 0, 40) {
        int curr = dp[i][arr.size()];
        if(curr>T)continue;
        int cnt = i;
        owo(j, 0, zero.size()) {
            curr+=zero[j]+1;
            if(curr<=T) cnt++;
        }
        mx = max(mx, cnt);
    }
    cout<<mx<<"\n";
    return 0;
}


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

char s[4];

int main(){
    scanf("%s", s);
    if (s[1] == 'R'){
        printf("%d\n", 1 + (s[0] == 'R') + (s[2] == 'R'));
    }
    else{
        printf("%d\n", int(s[0] == 'R' || s[2] == 'R'));
    }
    return 0;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;

const int maxn = 123;
int n , r , c , ans[maxn][maxn];

pair < int , int > nxt(pair < int , int > lol)
{
	int row = lol.first , col = lol.second;
	if(row % 2 == 0)
	{
		if(col == c - 1) return make_pair(row + 1 , col);
		else return make_pair(row , col + 1);
	}
	else
	{
		if(col == 0) return make_pair(row + 1 , col);
		else return make_pair(row , col - 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	cin >> r >> c >> n;
	pair < int , int > now = make_pair(0,0);
	for(int i=0;i<n;i++)
	{
		int x;
		cin >> x;
		while(x--)
		{
			ans[now.first][now.second] = i + 1;
			now = nxt(now);
		}
	}
	
	for(int i=0;i<r;i++)
	{
		for(int j=0;j<c;j++) cout << ans[i][j] << " ";
		cout << endl;
	}
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>


int main()
{
    long H,N;
    std::cin >> H >> N;
    std::vector<long> A;
    for(long i=0; i<N; i++){
        long temp;
        std::cin >> temp;
        A.push_back(temp);
    }
    long sum=0;
    for(long i=0; i<N; i++){
        sum+=A[i];
    }
    if(H<=sum){
        std::cout << "Yes" << std::endl;
    }else{
        std::cout << "No" << std::endl;
    }
    return 0;
}

Measured memory_bytes: 1400
n = int(input())
a = list(map(int, input().split()))


def gcd(a, b):
    if a <= b:
        if b % a == 0:
            return a
        else:
            return(gcd(b % a, a))
    else:
        if a % b == 0:
            return b
        else:
            return(gcd(a % b, b))


ans = gcd(a[0], a[1])

for i in range(2, len(a)):
    ans = gcd(ans, a[i])

print(ans)


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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};

std::string A;
int len[200100];
std::vector<std::tuple<int, int> > v;

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

    std::cin >> A;

    int N = A.size(), state = 0, m = 0;
    for(int i=N-1;i>=0;--i){
        state = state | (1 << (A[i] - 'a'));
        if(state + 1 == (1 << 26)){
            state = 0;
            ++m;
        }        
        len[i] = m;
    }
    
    for(int i=0;i<N;++i){
        v.emplace_back(A[i] - 'a', i);
    }
    sort(v.begin(), v.end());

    len[N] = -1;

    int pos = 0;
    while(pos < N){
        char c;
        for(int i=0;i<26;++i){
            int ne = lower_bound(v.begin(), v.end(), std::make_tuple(i, pos)) - v.begin();

            if(ne < N){
                ne = fst(v[ne]) == i ? snd(v[ne]) + 1 : N;
            }

            if(len[pos] == len[ne] + 1){
                c = 'a' + i;
                pos = ne;
                break;
            }
        }
        
        std::cout << c;
    }
    std::cout << std::endl;
}


Measured memory_bytes: 3468
#include <stdio.h>

int max(int a, int b){
	return a>b?a:b;
}

int min(int a, int b){
	return a<b?a:b;
}

int main(){
	int i,n;
	scanf("%d",&n);
	int r[n],minv[n],maxv[n],Max=-1000000000;
	for(i=0;i<n;i++){
		scanf("%d",&r[i]);
    }

	minv[0]=r[0];
	maxv[0]=r[n-1];
	for(i=1;i<n-1;i++){
		minv[i] = min (minv[i-1],r[i]);
		maxv[i] = max (maxv[i-1],r[n-1-i]);
	}
	for(i=0;i<n-1;i++){
		Max = max (Max, maxv[n-2-i]-minv[i]);
	}
	printf("%d\n", Max);

	return 0;
}

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

int main(void){
    int n;
    cin >> n;
    int bo[n];
    int ans = 0;
    int next = 0;
    for(int i = 0; i < n; i++)
        cin >> bo[i];

    for(int i = 1; i <= n; i++){
        next = bo[next]-1;
         if(next==1){
            ans = i;
            break;
         }
    }
    if(ans == 0)
        ans = -1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640