akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;
const long long ll_max = 9223372036854775807;
const int int_max = 2147483647;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

// 繰り返し二乗法
ll pow2(ll n, ll p, ll mod) {
	if (p == 0 || n == 1) {
		return 1;
	}
	else {
		ll ret = pow2(n * n % mod, p / 2, mod);
		if (p % 2 == 1) {
			ret *= n;
		}
		return ret % mod;
	}
}


#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	ll H, N;
	cin >> H >> N;
	vll A(N), B(N);
	rep(i, 0, N) {
		cin >> A[i] >> B[i];
	}
	
	vll t(1e8+10, 0);
	ll idx = 0;
	while (true) {
		idx++;
		rep(i, 0, N) {
			if (B[i] <= idx) {
				t[idx] = max(t[idx], t[idx - B[i]] + A[i]);
			}
		}
		if (t[idx] >= H) {
			cout << idx << endl;
			return 0;
		}
	}

	return 0;

}


Measured memory_bytes: 784440
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <time.h>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
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;}
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
using namespace std;
vector<vector<int>> Graph;
int DP[100010];
bool CAN=true;

int tree(int X){
  if(DP[X]!=0) return DP[X];
  
  vector<int> L;
  REP(i,Graph[X].size()){
    int NEXT=Graph[X][i];
    L.push_back(tree(NEXT));
  }
  SORT(L);
  int cnt=0;
  REP(i,L.size()){
    if(cnt<L[i]) cnt=L[i];
    cnt++;
  }
  DP[X]=cnt;
  return DP[X];
}

int main(){
  int N;
  cin>>N;
  Graph.resize(N);
  
  REP(i,N-1){
    int A;
    cin>>A;
    Graph[A-1].push_back(i+1);
  }
  
  tree(0);
  cout<<DP[0]<<endl;
  return 0;
}

Measured memory_bytes: 15488
n=int(input())
d=[]
e=[]
for i in range(n):
    p=[0,0]
    s=input()
    for j in s:
        if j==")":
            if p[0]!=0:
                p[0]-=1
            else:
                p[1]+=1
        else:
            p[0]+=1
    if p[0]-p[1]>=0:
        d.append(p)
    else:
        e.append(p)
d=sorted(d,key=lambda x:x[1])
e=sorted(e,key=lambda x:-x[0])
s=d+e
q=0
for i,j in s:
    if q<j:
        print("No")
        exit()
    else:
        q=q-j+i
if q==0:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 237712
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;
typedef pair<int, int> P;

int main()
{
	int n, m, d;
	cin >> n >> m >> d;
	if (d == 0) {
		printf("%.7f", (1.0 / n) * (m - 1));
	}
	else {
		printf("%.7f", (2.0 * (n - d) / n / n) * (m - 1));
	}
}


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

int main () {
  int a, b;
  cin >> a >> b;
  if (a*b%2 == 0) {
    cout << "Even" << endl;
  }
  if (a*b%2 == 1) {
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> plint;
typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 1e9 + 7, INF = 1e18;


template <std::int_fast64_t Modulus>
class modint
{
	using u64 = std::int_fast64_t;

public:
	u64 a;
	constexpr modint(const u64 x = 0) noexcept : a(x% Modulus) {}
	constexpr u64& value() noexcept { return a; }
	constexpr const u64& value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept
	{
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept
	{
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept
	{
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept
	{
		return modint(*this) /= rhs;
	}
	constexpr modint& operator+=(const modint rhs) noexcept
	{
		a += rhs.a;
		if (a >= Modulus)
		{
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint& operator-=(const modint rhs) noexcept
	{
		if (a < rhs.a)
		{
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint& operator*=(const modint rhs) noexcept
	{
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint& operator/=(modint rhs) noexcept
	{
		u64 exp = Modulus - 2;
		while (exp)
		{
			if (exp % 2)
			{
				*this *= rhs;
			}
			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}
};
typedef modint<MOD> ModInt;

ModInt mod_pow(ModInt x, ModInt n) {
	ModInt ret = 1;
	while (n.a > 0) {
		if (n.a & 1) (ret *= x);
		(x *= x);
		n.a >>= 1;
	}
	return ret;
}

lint N;
string s;
lint cnt[26];
int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	cin >> N >> s;
	REP(i, N) {
		cnt[s[i] - 'a']++;
	}
	ModInt ans = 1;
	REP(i, 26) ans *= (cnt[i] + 1);
	cout << ans.a - 1 << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <math.h>
#include <cmath>
#include <limits.h>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
    
    int N;
    int P;
    long long ans = 0;
    
    vector<int> A;
    
    cin >> N;
    cin >> P;
    
    int n_even = 0;
    
    for ( int i = 0; i < N; i++ ) {
        int t;
        cin >> t;
        
        if ( t%2 == 0 ) { n_even++; }
    }
    
    
    long long combination[N+1][N+1];
    
    for ( int i = 0; i <= N; i++ ) {
        for ( int j = 0; j <= i; j++ ) {
            
            if ( i == j || j == 0 ) { combination[i][j] = 1; }
            else {
                combination[i][j] = combination[i-1][j] + combination[i-1][j-1];
            }
        }
    }
    
    
    if ( P ) {
        
        
        for ( int i = 1; i <= N-n_even; i+=2 ) {
            ans += combination[N-n_even][i];
        }
        
        ans *= pow(2,n_even);
        
        
    }
    else {
        
        
        for ( int i = 0; i <= N-n_even; i+=2 ) {
            ans += combination[N-n_even][i];
        }
        
        ans *= pow(2,n_even);
        
    }
    
    cout << ans << endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int64_t>data(N);
  int count=0;
  for(int i=0;i<N;i++){
    cin >> data.at(i);
    if(data.at(i)<0) count++;
    data.at(i)=abs(data.at(i));
  }
  int64_t ans=0;
  if(count%2==0){
    for(int i=0;i<N;i++){
      ans+=data.at(i);
    }
  }
  else{
    sort(data.begin(),data.end());
    ans-=data.at(0);
    for(int i=1;i<N;i++){
      ans+=data.at(i);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 4052
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n){
        cin >> a[i];
        a[i] -= i+1;
    }
    sort(all(a));
    ld left = a[0];
    ld right = a[n-1];
    auto func = [&](ld x){
        ld ret = 0;
        rep(i,n)ret += abs(a[i] - x);
        return ret;
    };
    rep(i,100){
        ld t1 = (2*left + right) / 3;
        ld t2 = (left + 2*right) / 3;
        if(func(t1) < func(t2))right = t2;
        else left = t1;
    }
    
    ll ret = round(func(left));
    cout << ret << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>
int main()
{
	char str[4];
	scanf("%s",str);
	int count =0,i=0;
	while(1)
	{
//		int i=0;
		if(str[i] == str[i+1])
		{
			count++;
		}
		i++;
		if(i==3)
		{
			break;
		}
	}
	if(count>0)
	{
		printf("Bad\n");
	}
	else
	{
		printf("Good\n");
	}
	return 0;
}


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

string s, t;
int ans=0;

int main() {
  cin>>s;
  cin>>t;
  int len=s.size();
  for (int i=0; i<len; i++) {
    if (s[i]!=t[i]) ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3868
from sys import stdin


def readline_from_stdin() -> str:
    return stdin.readline().rstrip


if __name__ == '__main__':
    A, B, C = input().split()
    K = input()
    A, B, C, K = int(A), int(B), int(C), int(K)

    for k in range(K):
        if not B > A:
            B *= 2
            continue
        if not C > B:
            C *= 2
            continue

    if C > B > A:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 9192
import math
def fact(n):
    ans = 1
    for i in range(2, n+1):
        ans*= i
    return ans
def comb(n, c):
    return fact(n)//(fact(n-c)*c)
n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt=  0
i = 1
cycle = ['1']
set = {'1'}
for c in range(n):
    i = a[i-1]
    if(i in set):
        break
    else:
        cycle.append(i)
        set.add(i)

ind = cycle.index(i)
k-= ind
rcycle = cycle[ind:]
if(k <= 0):
    print(cycle[k+ind])
else:
    now = (k+1)%len(rcycle)
    print(rcycle[now-1])

Measured memory_bytes: 125800
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static int compress(int[] counts){
		int ret = 0;
		
		LOOP:
		while(true){
			boolean updated = false;
			
			for(int pos = 0; pos < counts.length; pos++){
				if(counts[pos] == 0){ continue; }
				
				int len = 1;
				for(int next = pos + 1; next < counts.length; next++){
					if(counts[next] == 0){ break; }
					len++;
				}
				
				if(len >= 3){
					updated = true;
					
					ret += len - 3;
					for(int i = pos; i < pos + len; i++){
						counts[i]--;
					}
					
					continue LOOP;
				}	
			}
			
			if(!updated){
				break;
			}
		}
		
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		
		char[] input = sc.next().toCharArray();
		
		int[] alpha_count = new int[26];
		int[] number_count = new int[10];
		
		for(char c : input){
			if('a' <= c && c <= 'z'){
				alpha_count[c - 'a']++;
			}else{
				number_count[Character.getNumericValue(c)]++;
			}
		}
		
		int length = input.length;
		length -= compress(alpha_count);
		length -= compress(number_count);
		
		System.out.println(length);
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while (!hasNext()) {
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

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

int main() {
    int n, m, l;
    long long A[110][110], B[110][110], C[110][110] = {};
    cin >> n >> m >> l;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> A[i][j];
        }
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < l; ++j) {
            cin >> B[i][j];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < l; ++j) {
            for (int k = 0; k < m; ++k) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < l - 1; ++j) {
            cout << C[i][j] << ' ';
        }
        cout << C[i][l - 1] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3332
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int Max = 1000000;
int main(){
  	int N, M;
  	cin >> N >> M;
  	bool e[N][N];

  	for(int i=0;i<N;i++){
  		for(int j=0;j<N;j++) e[i][j] = false;
  	}

  	int check[N];
  	int a, b;

  	for(int i=0;i<N;i++) check[i] = i;

  	for(int i=0;i<M;i++){
  		cin >> a >> b;
  		e[a-1][b-1] = true;
  		e[b-1][a-1] = true;
  	}

  	int ans = 0;
  	do{
  		bool flag = true;
  		for(int i=0;i<N-1;i++){
  			if(!e[check[i]][check[i+1]]){
  				flag = false;
  				break;
  			}
  		}
  		if(flag) ans++;
  	}while(next_permutation(check+1, check+N));

  	cout << ans <<endl;


    
  	return 0;
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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; }

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  vll a(n*3);
  rep(i,n*3) cin>>a[i];
  sort(a.rbegin(),a.rend());
  ll ans=0;
  for(ll i=1; i<n*2+1; i+=2){
    ans+=a[i];
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 2560
def main():
  from collections import deque
  n,w=map(int,input().split())
  item=deque([list(map(int,input().split())) for _ in range(n)])
  DP=[[0]*(w+1) for _ in range(n+1)]
  for i in range(1,n+1):
    itemNow=item.popleft()
    weight=itemNow[0]
    value=itemNow[1]
    for j in range(w+1):
      if j<weight:
        DP[i][j]=DP[i-1][j]
      else:
        DP[i][j]=max(DP[i-1][j],DP[i-1][j-weight]+value)
        
  print(DP[n][w])
      
if __name__=="__main__":
  main()

Measured memory_bytes: 118512
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()

g = gcd(N, M)
ans = N*M // g
N //= g
M //= g

if S[0] != T[0] or not all(i == j for i, j in zip(S[N::N], T[M::M])):
    ans = -1
print(ans)


Measured memory_bytes: 5344
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

int main() {
	lint N, M;
	cin >> N >> M;
	vector<lint>A(N);
	rep(i, N) {
		cin >> A[i];
	}
	vector<LLP> CB(M);
	rep(i, M) {
		cin >> CB[i].second >> CB[i].first;
	}
	sort(A);
	sort(CB);
	reverse(CB);
	vector<lint>V;
	lint cnt = 0;
	rep(i, M) {
		rep(j, CB[i].second) {
			if (cnt < N) {
				V.push_back(CB[i].first);
				cnt++;
			}
			else {
				break;
			}
		}
		if (cnt >= N) {
			break;
		}
	}
	rep(i, N) {
		V.push_back(0);
	}
	lint ans = 0;
	rep(i, N) {
		ans += max(A[i], V[i]);
	}
	cout <<ans << endl;
}


Measured memory_bytes: 5748
//Love and Freedom.
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define ll long long
#define inf 20021225
#define pa pair<ll,ll>
#define mp make_pair
#define fs first
#define se second
#define N 131072
#define pb push_back
#define ls(x) son[x][0]
#define rs(x) son[x][1]
using namespace std;
int read()
{
	int s=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return f*s;
}
vector<int> son[N+2]; int val[N+2];
vector<pa> f[N+2],tmp[2]; ll mid;
void dfs(int x)
{
	f[x].clear();
	if(!son[x].size()){f[x].pb(mp(0,0)); return;}
	dfs(ls(x)); dfs(rs(x));
	for(int p=0;p<2;p++)
	{
		tmp[p].clear(); int a=son[x][p],b=son[x][p^1]; int r=0;
		for(int i=0;i<f[a].size();i++)
		{
			while(r+1<f[b].size()&&f[b][r+1].fs+f[a][i].se+val[a]+val[b]<=mid)	r++;
			if(r<f[b].size() && f[b][r].fs+f[a][i].se+val[a]+val[b]<=mid)	tmp[p].pb(mp(f[a][i].fs+val[a],f[b][r].se+val[b]));
		}
	}
	int i=0,j=0; ll cur=1e18;
	while(i<tmp[0].size()&&j<tmp[1].size())
	{
		if(tmp[0][i]<tmp[1][j])
		{
			if(tmp[0][i].se<cur)
				f[x].pb(tmp[0][i]),cur=tmp[0][i].se;
			i++;
		}
		else
		{
			if(tmp[1][j].se<cur)
				f[x].pb(tmp[1][j]),cur=tmp[1][j].se;
			j++;
		}
	}
	while(i<tmp[0].size())
	{
		if(tmp[0][i].se<cur)
			f[x].pb(tmp[0][i]),cur=tmp[0][i].se;
		i++;
	}
	while(j<tmp[1].size())
	{	
		if(tmp[1][j].se<cur)
			f[x].pb(tmp[1][j]),cur=tmp[1][j].se;
		j++;
	}
}
bool check()
{
	dfs(1);
	if(f[1].size())	return 1;
	return 0;
}
int main()
{
	int n=read(); ll l=0,r=0;
	for(int i=2;i<=n;i++)
	{
		int fa=read(); val[i]=read();
		son[fa].pb(i); r+=val[i];
	}
	ll ans=r;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check())	ans=mid,r=mid-1;
		else	l=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 32988
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.Stack;

public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer root;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (root == null || !root.hasMoreTokens()) {
				try {
					root = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return root.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static int mod = (int) (1e9+7),n;
	static long cf = 998244353;
    static final int MAX = (int) 1e6;
    public static List<Integer>[] edges;
    public static int[][] parent;
    public static int col = 20;
    public static long[] Bit;
    public static long[] fac,inv;
    public  static int[] prime; 
    public static long[] dp;
	public static FastReader sc = new FastReader();
	public static void main(String[] args) {
	//	Scanner sc = new Scanner(System.in);
 
		int n = sc.nextInt();
		char[] s = sc.next().toCharArray();
		for(int i=0;i<s.length;++i) {
			int shift = (s[i]-'A') + n;
			if(shift > 25) s[i] = (char) ((shift-26)+'A');
			else s[i]+=n;
		}
		out.print(new String(s));
		out.close();
	}
	
	
}

Measured memory_bytes: 22612
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
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;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
    ll N;
    cin >> N;
    ll ans = 1;
    for (int i = 0; i < N; i++) {
        ans *= (i + 1);
        ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    rep(i,n) rep(j,n-1){
        cin >> a[i][j];
        a[i][j]--;
    } 

    int ans = 0;
    while(true){
        int mnx = 1001;
        rep(i,n) mnx = min(mnx, a[i][n-1]);
        if (mnx == n-1) break;

        set<P> st;
        rep(i,n){
            if (a[i][n-1] == n-1) continue;
            int j = a[i][a[i][n-1]];
            if (a[j][n-1] == n-1) continue;
            int k = a[j][a[j][n-1]];
            if (i == k) st.insert(make_pair(min(i,j), max(i,j)));
        }

        if (st.size() == 0){
            cout << -1 << endl;
            return 0;
        }

        for(auto p : st){
            int i = p.first, j = p.second;
            a[i][n-1]++;
            a[j][n-1]++;
        }
        ans++;
    }
    cout << ans << endl;
    return 0;
}

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

#define MAX_NUM (1000000000 + 7)

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

int main() {
  cout << setprecision(15);
  u32 N;
  cin >> N;
  cout << ((N / 2) + (N & 0x01)) << endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] strs = br.readLine().split(" ");
		
		int[] v1 = new int[100001];
		int[] v2 = new int[100001];
		
		for(int i = 0 ; i < v1.length ; i++){
			v1[i] = 0;
			v2[i] = 0;
		}
		
		for(int i = 0 ; i < n ; i++){
			if(i%2 == 0){
				v1[Integer.parseInt(strs[i])]++;
			}else{
				v2[Integer.parseInt(strs[i])]++;
			}
		}
		int max11 = 0;
		int max12 = 0;
		int max11id = 0;
		int max12id = 0;
		int max21 = 0;
		int max22 = 0;
		int max21id = 0;
		int max22id = 0;
		
		for(int i = 0 ; i < v1.length ; i++){
			if(v1[i] > max11){
				max12 = max11;
				max12id = max11id;
				max11 = v1[i];
				max11id = i;
			}else if(v1[i] > max12){
				max12 = v1[i];
				max12id = i;
			}
		}
		for(int i = 0 ; i < v2.length ; i++){
			if(v2[i] > max21){
				max22 = max21;
				max22id = max21id;
				max21 = v2[i];
				max21id = i;
			}else if(v2[i] > max22){
				max22 = v2[i];
				max22id = i;
			}
		}
		
		if(max11id != max21id){
			System.out.println((n - max11 - max21));
		}else{
			if((n - max11 - max22) < (n - max12 - max21)){
				System.out.println((n - max11 - max22));
			}else{
				System.out.println((n - max12 - max21));
			}
		}
	}
}


Measured memory_bytes: 35884
#include <bits/stdc++.h>                                           
 
#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1,	 -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 555;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e4 + 211;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


int a, b;
main () {		
	cin >> a >> b;
	forn (i, 1, 3)
		if (i != a && i != b)
			cout << i << ' ';			

}

Measured memory_bytes: 256
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <immintrin.h>
# include <cassert>
# include <array>
# include <tuple>
# include <unordered_map>
# include <unordered_set>
# include <thread>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using ui32 = unsigned int;
constexpr ll INFLL = 1e18;

#define CHECK_IMPL1(cond)              \
if (!(cond)) {                         \
    DEBUG("expected cond: " << #cond); \
    assert(cond);                      \
}

#define CHECK_IMPL2(cond, message)                                            \
if (!(cond)) {                                                                \
    DEBUG("expected cond: " << #cond << " failed with message: " << message); \
    assert(cond);                                                             \
}
#define CHECK_IMPL(_1, _2, NAME, ...) NAME
#define CHECK(...) CHECK_IMPL(__VA_ARGS__, CHECK_IMPL2, CHECK_IMPL1, CHECK_IMPL0)(__VA_ARGS__)

#ifdef __APPLE__
#define DEBUG(message) std::cerr << message << "\n";
#else
#define DEBUG(message)
#endif

void solve() {
  int n;
  cin >> n;
  vector<ll> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }
  ll ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    a[i] += ans;
    ll k = (a[i] + b[i] - 1) / b[i];
    ll add = k * b[i] - a[i];
    CHECK(add >= 0);
    CHECK((a[i] + add) % b[i] == 0);
    a[i] += add;
    ans += add;
  }
  cout << ans << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
#ifdef __APPLE__
  freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
#endif
  int t = 1;
//  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<array>
#define nguyendz the_best


#define ll long long
#define ld long double
#define pb push_back
#define all(n) n.begin(),n.end()
#define eb emplace_back
#define endl "\n"
#define pll pair<ll,ll>
#define YES cout <<"YES"<<endl;
#define NO cout <<"NO"<<endl;
#define ff first
#define ss second
#define setpre(x) fixed<<setprecision(x)


using namespace std;
const ll maxn=1e6+100;
vector<ll> adj[maxn];
ll a[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("A.INP","r"))
    {
         freopen("A.INP","r",stdin);
        freopen("A.OUT","w", stdout);
    }
    string s;
     cin>> s;
     ll n= s.length();
     for (int i=0;i<n;i++)
     {
         if (i==n-1)
         {
             ll t= s[i]-'0' ;
             if (t==3)
             {
                 cout <<"bon";
             }
             else if (t==0||t==1||t==6||t==8)
             {
                 cout <<"pon";
             }
             else
             {
                 cout <<"hon";
             }

         }
     }

}


Measured memory_bytes: 27108
#include <iostream>
#include <algorithm>
using namespace std;
static const int MAX = 100000;
static const int VMAX = 100000;

int n,s,A[MAX];
int B[MAX], T[VMAX];

int solve()
{
	int ans = 0;
	bool V[MAX];
	for (int i = 0; i < n; ++i)
	{
		B[i] = A[i];
		V[i] = false;
	}

	sort(B,B+n);
	for (int i = 0; i < n; ++i)
	{
		T[B[i]] = i;
	}

	for (int i = 0; i < n; ++i)
	{
		if(V[i]==true) continue;
		int cur = i;
		int S = 0;
		int m = VMAX;
		int an = 0;
		while(1)
		{
			V[cur] = true;
			an++;
			int v = A[cur];
			m = min(m , v);
			S += v;
			cur = T[v];
			if(V[cur]) break;
		}
		ans += min(S + (an - 2) * m, m + S + (an + 1) * s);
	}
	return ans;
}

int main()
{
	cin>>n;
	s = VMAX;
	for (int i = 0; i < n; ++i)
	{
		cin>>A[i];
		s = min(s, A[i]);
	}
	int ans = solve();
	cout<<ans<<endl;

	return 0;
}

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

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

class Sol{
	public void Solve(){
		if(B == 1){
			Console.WriteLine(0);
			return;
		}
		int open = 1;
		int tot = 1;
		for(int i=1;i<200;i++){
			if(open > 1){
				tot += A - 1;
				open--;
			} else {
				open = tot;
				tot += A - 1;
				open--;
			}
			if(tot >= B){
				Console.WriteLine(i);
				return;
			}
		}
		
		
	}
	int A,B;
	public Sol(){
		var d = ria();
		A = d[0]; B = d[1];
	}

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


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

using namespace std;

int main() {
int N;
cin >>  N;
vector<int> A(N);
for (int i = 0; i < N; ++i) {
  cin >> A[i];
}
int s = 0;
for (int i = 0; i < N; ++i) {
  if (i%2==0){s += A[i];}
  else{s -= A[i];}
}
cout << s << " ";
int x = s/2;

for(int i = 0; i < N-1; ++i) {
  cout <<  (A[i]-x)*2 << " ";
  x = A[i]-x;}
return 0;}


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

typedef long long ll;

int main(){
    int N;
    cin >> N;
    vector<ll> a(N), s(N);
    for(int i=0; i<N; i++) cin >> a[i];
    
    s[0] = a[0];
    for(int i=1; i<N; i++){
        s[i] = s[i-1]+a[i];
    }
    
    ll mi=2e18;
    for(int i=0; i<N-1; i++){
        mi = min(mi, abs(s[i]-(s[N-1]-s[i])));
        //cout << mi << endl;
    }
    cout << mi << endl;
}


Measured memory_bytes: 3328
#include <iostream>

using namespace std;

int main()
{
    //cout << "Hello world!" << endl;
    int a , b , c ;
    cin >> a >> b >> c;

    if((a == 5 && b == 5 && c == 7) || (a == 5 && c == 5 && b == 7) || (c == 5 && b == 5 && a == 7)){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3 + 5;
const int P = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, p[MAXN], s[MAXN], f[MAXN];
int find(int x) {
	if (f[x] == x) return x;
	else return f[x] = find(f[x]);
}
int fac[MAXN], powk[MAXN], dp[MAXN];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
int main() {
	int k = 0; read(n);
	for (int i = 1; i <= n; i++)
		f[i] = i, s[i] = 1;
	for (int i = 1; i <= n; i++) {
		read(p[i]);
		k += p[i] == -1;
		if (p[i] != -1) {
			int x = find(i), y = find(p[i]);
			if (x != y) {
				f[x] = y;
				s[y] += s[x];
			}
		}
	}
	dp[0] = powk[0] = fac[0] = 1;
	for (int i = 1; i <= n; i++) {
		fac[i] = 1ll * fac[i - 1] * i % P;
		powk[i] = 1ll * powk[i - 1] * (n - 1) % P;
	}
	int ans = 1ll * n * powk[k] % P;
	for (int i = 1; i <= n; i++)
		if (f[i] == i) {
			if (p[i] == -1) {
				for (int j = n; j >= 1; j--)
					update(dp[j], 1ll * dp[j - 1] * s[i] % P);
			} else update(ans, P - powk[k]);
		}
	for (int i = 1; i <= n; i++)
		if (p[i] == -1) update(ans, P - 1ll * (s[i] - 1) * powk[k - 1] % P);
	for (int i = 2; i <= k; i++)
		update(ans, P - 1ll * dp[i] * fac[i - 1] % P * powk[k - i] % P);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3720
n,a,b = map(int,input().split())
x = list(map(int,input().split()))

ans = 0
now = x[0]
for i in range(1,n):
    diff = x[i]-now
    if diff*a > b:
        ans += b
    else:
        ans += diff*a
    now = x[i]
    # print(ans)

print(ans)

Measured memory_bytes: 14252
#include <stdio.h>

int fun1(int page1, int eff1, int page2, int eff2, int date);
int main()
{
	int L,A,B,C,D;
	scanf("%d %d %d %d %d",&L,&A,&B,&C,&D);
	printf("%d\n",fun1(A,B,C,D,L));
	return 0;
}

int fun1(int page1, int page2, int eff1, int eff2, int date)
{
	int task1=0,task2=0,playDate;
	task1 = page1%eff1==0 ? page1/eff1 : page1/eff1+1;
	task2 = page2%eff2==0 ? page2/eff2 : page2/eff2+1;
	playDate = task1>task2 ? date-task1 : date-task2;
	return playDate;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
#define fore(i,a,b) for(ll i=(ll)(a);i<=(ll)(b);++i)
#define rep(i,n) fore(i,0,(n)-1)
#define rfore(i,a,b) for(ll i=(ll)(b);i>=(ll)(a);--i)
#define rrep(i,n) rfore(i,0,(n)-1)
#define all(x) (x).begin(),(x).end()
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
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;}
const ll MOD = 1000000007;

template< int mod >
struct ModInt {
  int x;

  ModInt() : x(0) {}

  ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

  ModInt &operator+=(const ModInt &p) {
    if((x += p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator-=(const ModInt &p) {
    if((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }

  ModInt &operator*=(const ModInt &p) {
    x = (int) (1LL * x * p.x % mod);
    return *this;
  }

  ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

  ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

  ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

  ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

  bool operator==(const ModInt &p) const { return x == p.x; }

  bool operator!=(const ModInt &p) const { return x != p.x; }

  ModInt inverse() const {
    int a = x, b = mod, u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(int64_t n) const {
    ModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ModInt &p) {
    return os << p.x;
  }

  friend istream &operator>>(istream &is, ModInt &a) {
    int64_t t;
    is >> t;
    a = ModInt< mod >(t);
    return (is);
  }

  static int get_mod() { return mod; }
};

using modint = ModInt< MOD >;

#define MAX 2005
modint dp[MAX][MAX];
void solve(long long N, long long M, std::vector<long long> S, std::vector<long long> T){
    rep(i,N)dp[i][0]=1;
    rep(i,M)dp[0][i]=1;
    rep(i,N)rep(j,M){
        dp[i+1][j+1]=dp[i+1][j]+dp[i][j+1];
        if(S[i]!=T[j])dp[i+1][j+1]-=dp[i][j];
    }
    cout<<dp[N][M]+2<<endl;
}

int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    std::vector<long long> S(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&S[i]);
    }
    std::vector<long long> T(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&T[i]);
    }
    solve(N, M, std::move(S), std::move(T));
}


Measured memory_bytes: 16512
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	int cnt = 0;
	for( int i = 1; i <= n; ++i ){
		int k; cin >> k;
		if( i != k ) ++cnt;
	}
	if( cnt <= 2 ) cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

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

Graph g;
vector<int> a, ans;
const int N = 2000005;
const int INF = 1000000000;
int dp[N];

void dfs(int v, int p=-1) {
  int i = lower_bound(dp, dp + N, a[v]) - dp;
  int old = dp[i];
  dp[i] = a[v];
  ans[v] = i;
  if (p != -1) ans[v] = max(ans[v], ans[p]);
  for(int u : g[v]) {
    if (u == p) continue;
    dfs(u, v);
  }
  dp[i] = old;
}

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

  dp[0] = -INF;
  for(int i = 1; i < N; ++i) {
    dp[i] = INF;
  }
  dfs(0);
  for(int i = 0; i < n; ++i) {
    cout << ans[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 37612
A, B, C = map(int, input().split())
K = int(input())

while K > 0:
    if A >= B:
        B *= 2
        K -= 1
    elif B >= C:
        C *= 2
        K -= 1
    if C > B and B > A:
        break
if C > B and B > A:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 61632
#include <iostream>

using namespace std;
int n,m,stanga,st,dr,mid,sol,dreapta;
char a[200005];
struct spell
{
    char l,d;
};
spell v[200005];
bool iese_prin_dreapta(int poz)
{
    int i;
    for(i=1;i<=m;i++)
    {
        if(v[i].l==a[poz])
        {
            if(v[i].d=='L')
            {
                poz--;
            }
            else
            {
                poz++;
            }
        }
        if(poz==0)
        {
            return 0;
        }
        else
        {
            if(poz==n+1)
            {
                return 1;
            }
        }
    }
    return (poz==n+1);
}
bool iese_prin_stanga(int poz)
{
    int i;
    for(i=1;i<=m;i++)
    {
        if(v[i].l==a[poz])
        {
            if(v[i].d=='L')
            {
                poz--;
            }
            else
            {
                poz++;
            }
        }
        if(poz==0)
        {
            return 1;
        }
        else
        {
            if(poz==n+1)
            {
                return 0;
            }
        }
    }
    return (poz==0);
}
int main()
{
    int i;
    cin>>n>>m;
    cin>>(a+1);
    for(i=1;i<=m;i++)
    {
        cin>>v[i].l>>v[i].d;
    }
    st=1;
    dr=n;
    stanga=0;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(iese_prin_dreapta(mid))
        {
            stanga=mid;
            dr=mid-1;
        }
        else
        {
            st=mid+1;
        }
    }
    st=1;
    dr=n;
    dreapta=n+1;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(iese_prin_stanga(mid))
        {
            dreapta=mid;
            st=mid+1;
        }
        else
        {
            dr=mid-1;
        }
    }
    if(stanga!=0)
    {
        sol+=n-stanga+1;
    }
    if(dreapta!=n+1)
    {
        sol+=dreapta;
    }
    cout<<n-sol;
    return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ull  unsigned long long
#define pb push_back
#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 40;
int g(int x, int y){
    if (x % y == 0) return x / y;
    int f = x / y + 1;
    int l = 0;
    int r = x + 1;
    while(r - l > 1){
        int mid = (r + l) / 2;
        if ((x - mid * f) / y == x / y) l = mid; else r = mid;
    }
    x -= l * f;
    if (l == 0) x -= f;
    return g(x, y);
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++){
        int n, k;
        cin >> n >> k;
        res ^= g(n, k);
    }
    if (res) cout << "Takahashi"; else cout << "Aoki";
}


Measured memory_bytes: 384
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    val n = sc.nextInt()
    val s = sc.nextInt()
    val a = Array(n) { sc.nextInt() }
    val mod = 998244353L
    var dp = Array(s + 1) { Array(3) { 0L } }
    // dp[i][j] := 選んだ数の総和がiで、状態がjであるような場合の数
    // 状態0 : 左端を選んでいない
    // 状態1 : 左端を選んだけど右端を選んでいない
    // 状態2 : 右端も選んだ
    // 最初はdp[i][j][k]にしてたけどTLEするので、配列使いまわしによる高速化を試す。通ってほしい…。
    dp[0][0] = 1
    for (i in 0 until n) {
        val newdp = Array(s + 1) { Array(3) { 0L } }
        for (j in 0..s) {
            //まずはa[i]を加えない場合

            //状態0は常に一定
            newdp[j][0] = dp[j][0]

            //左端を新たに決める(状態0→1)または決めた左端を引き継ぐ(状態1→1)
            newdp[j][1] += dp[j][0] + dp[j][1]

            //左端・右端を同時に決める(状態0→2)、右端のみ新たに決める(状態1→2)、決めた右端を引き継ぐ(状態2→2)
            newdp[j][2] += dp[j][0] + dp[j][1] + dp[j][2]

            //a[i]を加える場合
            if (j + a[i] <= s) {
                //右端を決めてある場合a[i]を加えられない
                newdp[j + a[i]][1] += dp[j][0] + dp[j][1]
                newdp[j + a[i]][2] += dp[j][0] + dp[j][1]
            }
            newdp[j][1] %= mod
            newdp[j][2] %= mod
        }
        dp = newdp
    }
    println(dp[s][2])
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 118676
cards_mirror = []
cards_shaffled = []
k = 0
try:
  while True:
    k += 1
    cards = list(input())
    n_irritation = int(input())
    if cards[0] == '-':
      break
    for i in range(n_irritation):
      n_shaffled = int(input())
      cards_mirror = cards.copy()
      for j in range(len(cards)):
        cards[j] = cards_mirror[(j+n_shaffled)%len(cards)]
    cards_shaffled.append(cards)
except EOFError:
  pass
for i in range(len(cards_shaffled)):
  for j in range(len(cards_shaffled[i])):
    print(cards_shaffled[i][j],end='')
  print('')


Measured memory_bytes: 5624