akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n)repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
typedef pair<int,int> P;
typedef pair<int, P> PP;
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define fi first
#define se second
const int inf = 1e9+7;
const int INF = 1e18+7;
int mod = 1e9+7;

struct edge{int x, y, z;};
int a[200][200];
queue<edge> G;
signed main(){
	int n, m;
	scanf("%lld%lld", &n, &m);
	
	fill((int*)a, (int*)(a+200), inf);
	rep(i,200)a[i][i] = 0;
	rep(i,m){
		int x, y, z;
		scanf("%lld%lld%lld", &x, &y, &z);
		G.push((edge){x, y, z});
		a[x][y] = z;a[y][x] = z;
	}
	
	rrep(i,n)rrep(j,n)rrep(k,n){
		a[j][k] = min(a[j][k], a[j][i]+a[i][k]);
	}
	
	int ans = m;
	rep(i,m){
		edge e = G.front();G.pop();
		int f = 0;
		if(e.z == a[e.x][e.y])f = 1;
		ans -= f;
	}
	
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<math.h>
using namespace std;

long long int a[100000];
long long int cu(long long int x, long long int y){
  if(y==0)
    return x;
  return cu(y, x%y);
}

int main(){
long long int i, n, b;
  cin >> n;
  
for(i=0; i<n; i++)
  cin >> a[i];
  
  b = a[0];
for(i=1; i<n; i++){
  if(a[i] > b)
  b = cu(a[i], b);
  else
  b = cu(b, a[i]);
}
cout << b;
return 0;
}

Measured memory_bytes: 1024
x, y = map(int, input().split())

total_money = 0

if x >= 4:
    total_money += 0
elif x == 3:
    total_money += 100000
elif x == 2:
    total_money += 200000
elif x == 1:
    total_money += 300000

if y >= 4:
    total_money += 0
elif y == 3:
    total_money += 100000
elif y == 2:
    total_money += 200000
elif y == 1:
    total_money += 300000

if x == 1 and y == 1:
    total_money += 400000

print(total_money)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;

#define EPS (1e-7)
#define INF (1e9)
#define LLINF (1e18)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

//-------------------------------------

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, p;
    while (true)
    {
        cin >> n >> p;
        int now = 0;
        if (n == 0 && p == 0)
        {
            return 0;
        }
        int owan = p;
        vector<int> stone(n, 0); // 各候補者が持つ石の個数
        int ans;
        while (true)
        {
            if (owan > 0)
            {
                owan--;
                stone[now % n]++;
                if (stone[now % n] == p)
                {
                    cout << now % n << endl;
                    break;
                }
            }
            else
            {
                owan = stone[now % n];
                stone[now % n] = 0;
            }
            now++;
        }
    }

    return 0;
}


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

int main(){
  int n,m,yen=0;
  string s[105],t[105];

  cin >> n;
  for(int i=0;i<n;i++) cin >> s[i];
  cin >> m;
  for(int i=0;i<m;i++) cin >> t[i];

  for(int i=0;i<n;i++) {
    int score=0;
    for(int j=0;j<n;j++) if(s[i]==s[j]) score++;
    for(int j=0;j<m;j++) if(s[i]==t[j]) score--;
    yen=max(yen,score);
  }
  cout << yen << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    TreeMap<String, Integer> paper = new TreeMap<>();
    int max = 1;
    for(int i=0; i<N; i++){
      String tmp = sc.next();
      if(paper.containsKey(tmp)){
        paper.put(tmp, paper.get(tmp) + 1);
        max = Math.max(max, paper.get(tmp));
      }else{
        paper.put(tmp, 1);
      }
    }
    for(String key: paper.keySet()){
      if(max == paper.get(key)){
        System.out.println(key);
      }
    }
  }
}
    
        


Measured memory_bytes: 84384
#include <iostream>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;

int keta(string s)
{
    if(s[0] == '0') return 0;
    else{
        int ret = 0;
        for(int i=s.size()-1;i>=0;--i)
        {
            if(s[i] != '.') ++ret;
            else break;
        }
        return ret;
    }
}

int main()
{
    ll ans = 0, a;
    string s;
    cin >> a >> s;
    int j = 1;
    for(int i = s.size() - 1; i>=0; --i)
    {
        if(s[i] == '.') continue;
        ans += (s[i] - '0') * a * j;
        j *= 10;
    }
    ans /= 100;
    cout << ans << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var <= (end); var++)
#define RFOR(var, begin, end) for (int var = (begin); var >= (end); var--)
#define REP(var, length) FOR(var, 0, length - 1)
#define RREP(var, length) RFOR(var, length - 1, 0)
#define EACH(value, var) for (auto value : var)
#define SORT(var) sort(var.begin(), var.end())
#define REVERSE(var) reverse(var.begin(), var.end())
#define RSORT(var) SORT(var); REVERSE(var)
#define OPTIMIZE_STDIO ios::sync_with_stdio(false);cin.tie(0);cout.precision(10);cout << fixed
#define endl '\n'

const ll MOD = 1e9 + 7;
struct mint {
    ll x;
    mint() : x(0) {}
    mint(ll x) : x((x % MOD + MOD) % MOD) {}
    mint& operator+=(const mint& r) { if ((x += r.x) >= MOD) { x -= MOD; } return *this; }
    mint& operator-=(const mint& r) { if ((x -= r.x) < 0) { x += MOD; } return *this; }
    mint& operator*=(const mint& r) { if ((x *= r.x) > MOD) { x %= MOD; } return *this; }
    mint& operator++() { if ((++x) >= MOD) { x -= MOD; } return *this; }
    mint operator++(int) { mint ret = x; if ((++x) >= MOD) { x-= MOD; } return ret; }
    mint& operator--() { if ((--x) < 0) { x += MOD; } return *this; }
    mint operator--(int) { mint ret = x; if ((--x) < 0) { x += MOD; } return ret; }
    mint operator+(const mint& r) { mint ret; return ret = x + r.x; }
    mint operator-(const mint& r) { mint ret; return ret = x - r.x; }
    mint operator*(const mint& r) { mint ret; return ret = x * r.x; }
    mint operator-() { return mint() - *this; }
    bool operator<(const mint& a) { return x < a.x; }
    bool operator>(const mint& a) { return x > a.x; }
    bool operator<=(const mint& a) { return x <= a.x; }
    bool operator>=(const mint& a) { return x >= a.x; }
    bool operator==(const mint& a) { return x == a.x; }
    bool operator!=(const mint& a) { return x != a.x; }
};
ostream& operator<<(ostream& os, const mint& r) { os << r.x; return os; }
ostream& operator>>(ostream& os, const mint& r) { os >> r.x; return os; }

void solve(istream& cin, ostream& cout) {
  ll n, ans;
  cin >> n;
  vector<ll> a(n);
  REP(i, n) {
    int in;
    cin >> in;
    a[i] = in;
  }
  RSORT(a);
  ans = 0;
  multiset<int> x;
  x.insert(a[0]);
  FOR(i, 1, n - 1) {
    x.insert(a[i]);
    x.insert(a[i]);
    auto itr = x.end();
    itr--;
    ans += *itr;
    x.erase(itr);
  }
  cout << ans << endl;
}

#ifndef TEST
int main() {
  OPTIMIZE_STDIO;
  solve(cin, cout);
}
#endif


Measured memory_bytes: 14260
#include<stdio.h>

int main(void){
 int a,b,c;
 scanf("%d", &a);
 scanf("%d", &b);
 scanf("%d", &c);

int temp;
if(a > b){
 temp = a;
 a = b;
 b = temp;
}
if(a > c){
 temp = a;
 a = c;
 c = temp;
}
if(b > c){
 temp = b;
 b = c;
 c = temp;
}
printf("%d %d %d\n", a,b,c);
return 0;
}

Measured memory_bytes: 596
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll n,c,dp[405][405],x[405][405],a[2][405];
int main()
{
	for(int i=0;i<=400;i++)x[0][i]=1;
	for(int i=1;i<=400;i++)for(int j=0;j<=400;j++)x[i][j]=1ll*x[i-1][j]*j%mod;
	for(int i=0;i<=400;i++)for(int j=1;j<=400;j++)x[i][j]=(x[i][j]+x[i][j-1])%mod;
	scanf("%lld%lld",&n,&c);
	for(int i=1;i<=n;i++)scanf("%lld",&a[0][i]);
	for(int i=1;i<=n;i++)scanf("%lld",&a[1][i]);
	dp[0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<=c;j++)
		{
			if(!dp[i][j])continue;
			for(int k=0;k<=c-j;k++)dp[i+1][j+k]=(dp[i+1][j+k]+dp[i][j]*(mod+x[k][a[1][i+1]]-x[k][a[0][i+1]-1]))%mod;	
		}	
	}
	printf("%lld\n",dp[n][c]);		
	return 0;
}

Measured memory_bytes: 4280
#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define dofloat cout<<fixed<<setprecision(8)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define bitcount __builtin_popcount
#define all(vec) vec.begin(),vec.end()
#define rall(vec) vec.rbegin(),vec.rend()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<long long> vl;
typedef pair<long long,long long> pll;
typedef vector<pair<long long,long long> > vll;
typedef vector<pair<int,int> > vii;
typedef vector<int> vi;
typedef pair<int,int> ii;
const long long MOD=1000000007;
const long long MAX=100005;
const long double PI=3.14159265359;
const long double G=9.807;
const long long INF=1e18;
const long double EPS=1e-6;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
bool isprime(ll a){
  if(a==2)return 1;
  if(!(a&1))return 0;
  for(ll i=3;i*i<=a;i+=2)
    if(a%i==0)return 0;
  return 1;
}
ll mpow(ll base,ll exponent,ll modulus){
  if(modulus==1)return 0;
  long long result = 1;
  base=base%modulus;
  while(exponent){
    if(exponent%2 == 1)
    result=(result*base)%modulus;
    exponent=exponent>>1;
    base=(base*base)%modulus;
  }
  return result;
}
ll minv(ll a,ll mod){
  ll _gcd=gcd(a,mod);
  assert(_gcd==1);
  return mpow(a,mod-2,mod);
}


/*
ll ncr(ll N,ll K){
  if(N<K)return 0;
  if(K==0)return 1;
  if(N==0)return 0;

  ll den=1;
  for(ll i=1;i<=K;i++)den*=i;
  ll num=1;
  while(K--){
    num*=N;
    if(num%den==0){
      num/=den;
      den=1;
    }
    N--;
  }

  return num;
}
*/
ll n;
int main(){FAST;
cin>>n;
ll d = n%10;
if(d == 0 or d == 1 or d == 6 or d == 8){
  cout<<"pon\n";
}
else if(d == 3){
  cout<<"bon\n";
}
else{
  cout<<"hon\n";
}
return 0;
}

/*
 WA? check edge cases, N=1,M=1 etc. Read code fully once and check all variables.
 Read the question again and see what you might have missed.
 Consider changing your solution or find more cases.
 */


Measured memory_bytes: 3616
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
#include <map>

using namespace std;
using ll = long long;
const ll INF = 1e9;

int main() {
    int N, A;
    cin >> N;
    N--;
    int v[N];
    for (int i = 0; i < N; i++) cin >> v[i];
    cin >> A;
    ll dp[N][21];
    for (int i = 0; i < N; i++) for (int j = 0; j < 21; j++) dp[i][j] = 0;

    dp[0][v[0]] = 1;
    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < 21; j++) {
            if (j + v[i+1] <= 20) {
                dp[i+1][j+v[i+1]] += dp[i][j];
            }
            if (j - v[i+1] >= 0) {
                dp[i+1][j-v[i+1]] += dp[i][j];
            }
        }
    }

    cout << dp[N-1][A] << endl;

    return 0;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
string a;
map<string, int> dp;
int main(){
	int n;
	scanf("%d", &n);
	bool ok = 1;
	char last = 0;
	for(int i=1;i<=n;i++){
		cin >> a;
		if(dp.count(a)) ok = 0;
		dp[a] = 1;
		if(i != 1){
			if(a[0] != last) ok = 0;
		}
		last = a[a.length()-1];
	}
	if(ok) printf("Yes\n");
	else printf("No\n");
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<set>
#include<map>
using namespace std;
using ulong = unsigned long;
using ll = long long;
const int M = 1e9 + 7;
#pragma unused(M)

int main(){
	int n;
	string s, t;
	cin >> n >> s >> t;
	for(int i=0;i<s.size();i++){
		bool ok = true;
		for(int j=0;i+j<s.size();j++){
			if(s[i + j] != t[j]){
				ok = false;
				break;
			}
		}
		if(ok){
			cout << max(s.size(), i + t.size()) << endl;
			return 0;
		}
	}
	cout << s.size() + t.size() << endl;
	return 0;
}



Measured memory_bytes: 888
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fl(i,from,to) for(ll i=from;i<to;i++)
int main()
{
	string n;cin>>n;int cnt=0,i=0,maxo=0;
		while(i<3)
		{
			cnt=0;
			while(n[i]=='R'){cnt++;i++;}
			i++;
			maxo=max(cnt,maxo);
		}

	cout<<maxo<<endl;
}

Measured memory_bytes: 3540
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using static MyIO;


public class A
{
	public static void Main()
	{
		int A = GetInt();
		int B = GetInt();
		int C = GetInt();
		Console.WriteLine(((C >= A) && (C <= B)) ? "Yes" : "No");
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(v) v.begin(),v.end()

const int maxn = 3e3 + 100;
const ll inf = 2e18, mod = 1e9 + 7;

int n, a[maxn];
vector<int> graph[maxn];

bool dfs(int u, int prev = -1)
{
	int cnt = 0;
	bool res = true;
	for (int i : graph[u])
		if (i != prev)
		{
			if (a[i] < a[u])
				res &= dfs(i, u);
			else
				cnt++;
		}
	if (cnt == (int)graph[u].size() - (prev != -1))
		return false;
	return !res;
}

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

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		graph[--u].pb(--v);
		graph[v].pb(u);
	}

	for (int i = 0; i < n; i++)
		if (dfs(i))
			cout << i + 1 << ' ';
	cout << endl;
}



Measured memory_bytes: 512
#include <iostream>
#include <iomanip>

using namespace std;

int main() {

  int a, b, c;
  //cin >> a;
  double ans, ra, rb;
  string weatherReport;
  cin >> weatherReport;
  if(weatherReport == "Sunny"){
    cout << "Cloudy";
  }else if(weatherReport == "Cloudy"){
    cout << "Rainy";
  }else{
    cout << "Sunny";
  }
  return 0;
}


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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int N = 1e5;

int a[N];
vector<pair<int, int>> p;

void solve() {
  int n, m; scanf("%d%d", &n, &m);
  priority_queue<int> pq;
  for (int i = 0; i < n; ++i) {
    scanf("%d", a+i);
  }
  sort(a, a+n);
  for (int i = 0; i < m; ++i) {
    int x, y; scanf("%d%d", &x, &y);
    p.emplace_back(y, x);
  }
  sort(p.begin(), p.end(), greater<pair<int, int>>());
  long long ans = 0;
  int z = 0;
  for (int i = 0; i < (int)p.size() && z < n; ++i) {
    while (z < n && p[i].second && p[i].first > a[z]) {
      z++;
      ans += p[i].first;
      --p[i].second;
    }
  }
  for (; z < n; ++z) ans += a[z];
  printf("%lld", ans);
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


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

int main(){
	int A,B,M;
	cin >> A >> B >> M;
	vector<int> a(A);
	vector<int> b(B);
	for(auto &i:a)cin >> i;
	for(auto &i:b)cin >> i;
	int ans=(*min_element(a.begin(),a.end()))+(*min_element(b.begin(),b.end()));
	for(int i=0;i<M;i++){
		int x,y,c;
		cin >> x >> y >> c;
		x--;
		y--;
		ans=min(ans,a[x]+b[y]-c);
	}
	cout << ans << endl;
 	return 0;
}

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

int main(void){
  int n, k;
  cin >> n >> k;
  int h[n];
  for(int i = 0; i < n; i++) cin >> h[i];
  sort(h, h + n);
  int dif = h[n - 1];  
  for(int i = 0; i <= n - k; i++){
    dif = min(dif, h[i + k - 1] - h[i]);
  }
  cout << dif << endl;
  return 0;
}


Measured memory_bytes: 640
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

    public void Proc()
    {
        int masu = int.Parse(Reader.ReadLine());
        int nuru = int.Parse(Reader.ReadLine());
        int ans = masu * masu - nuru;
        Console.WriteLine(ans);
    
    }




    public class Reader
    {
        private static StringReader sr;
        public static bool IsDebug = false;
        public static string ReadLine()
        {
            if (IsDebug)
            {
                if (sr == null)
                {
                    sr = new StringReader(InputText.Trim());
                }
                return sr.ReadLine();
            }
            else
            {
                return Console.ReadLine();
            }
        }
        private static string InputText = @"


3
4



";
    }

    public static void Main(string[] args)
    {
#if DEBUG
        Reader.IsDebug = true;
#endif
        Program prg = new Program();
        prg.Proc();
    }
}


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

main(){

  ll n;
  cin>>n;
  vector<ll> a(n);
  rep(i,n)cin>>a[i];

  for(ll i=n-1;i>0;--i){
    if(a[i-1]>a[i])a[i-1]--;
  }
  rep(i,n-1){
    if(a[i]>a[i+1]){
      puts("No");
      return 0;
    }
  }
  puts("Yes");

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
using vi=vector<int>;
#define PB push_back
#define ALL(x) x.begin(),x.end()
//#define LN cerr<<__LINE__<<endl
#define LN 0
using pi=pair<int,int>;
int read(){
	int i;
	scanf("%d",&i);
	return i;
}
void chmin(int&a,int b){
	a=a<b?a:b;
}
void chmax(int&a,int b){
	a=a>b?a:b;
}
struct SegTree{
	vi buf;
	int s;
	SegTree(int n){
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2,-1);
	}
	void Update(int i,int v){
		i+=s;
		buf[i]=v;
		while((i/=2)>=1)buf[i]=max(buf[i*2],buf[i*2+1]);
	}
	int GetIdx(int b,int e,int t,vi&dst,int l,int r,int i){
		if(buf[i]<=t||e<=l||r<=b)return t;
		if(b<=l&&r<=e){
			if(l+1==r){
				if(t<buf[i])dst.PB(l);
				return max(t,buf[i]);
			}else{
				if(t<buf[i*2])
					t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
				if(t<buf[i*2+1])
					t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
				return t;
			}
		}
		t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
		t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
		return t;
	}
	void GetIdx(int b,int e,vi& dst){
		GetIdx(b,e,-1,dst,0,s,1);
	}
	int get(int x){
		return buf[x+s];
	}
};
inline int xorshift(){
	static int w=1145141919;
	w=w^(w<<17);
	w=w^(w>>13);
	w=w^(w<<5);
	return w;
}
struct Node{
	Node *l,*r;
	int v,s;
} buf[200010];
Node* Merge(Node*a,Node*b){
	if(!a)return b;
	if(!b)return a;
	int s=a->s+b->s,x=xorshift()%s;
	if(x<a->s){
		a->r=Merge(a->r,b);
		a->s=s;
		return a;
	}else{
		b->l=Merge(a,b->l);
		b->s=s;
		return b;
	}
}
using pn=pair<Node*,Node*>;
pn Split(Node*x,int t){
	if(!x)return pn(0,0);
	if(t<=x->v){
		pn c=Split(x->l,t);
		if(c.first)x->s-=c.first->s;
		x->l=c.second;
		return pn(c.first,x);
	}else{
		pn c=Split(x->r,t);
		if(c.second)x->s-=c.second->s;
		x->r=c.first;
		return pn(x,c.second);
	}
}
int MaxValue(Node* x){
	while(x->r)x=x->r;
	return x->v;
}
void Show(Node* x){
	if(!x)return;
	Show(x->l);
	cerr<<x->v<<" ";
	Show(x->r);
}
int main(){
	int n=read();
	SegTree seg(n*2);
	vector<Node*> trs(n*2);
	vi mx(n*2,-1);
	REP(i,n){
		int x=read()-1;
		seg.Update(i,x);
		trs[i]=buf+i;
		trs[i]->v=x;
		trs[i]->s=1;
		mx[i]=x;
	}
	vi idx;
	int sum=0;
	FOR(i,n,n*2){
		idx.clear();
		seg.GetIdx(0,i,idx);
		int last=-1;
		Node*x=0;
		sum+=idx.size();
		for(auto j:idx){
			LN;
			pn c=Split(trs[j],last);
			LN;
			last=mx[j];
			LN;
			if(c.first)
				mx[j]=MaxValue(c.first);
			else
				mx[j]=-1;
			LN;
			seg.Update(j,mx[j]);
			LN;
			trs[j]=c.first;
			LN;
			x=Merge(x,c.second);
			LN;
		}
		if(x->s==n){
			cout<<i-n<<endl;
			return 0;
		}
		if(sum>=2e7)return 0;
		mx[i]=last;
		seg.Update(i,mx[i]);
		trs[i]=x;
		//Show(x);
	}
}

Measured memory_bytes: 15744
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <climits>

#define X first
#define Y second
#define vsort(v) sort((v).begin(), (v).end())
#define vrev(v) reverse((v).begin(), (v).end())


//INT_MAX
//INT_MIN
//LLONG_MAX
//LLONG_MIN
//DBL_MIN
//DBL_MAX
//LDBL_MIN
//LDBL_MAX

using namespace std;
using ll = long long;

int main(int argc, const char * argv[]) {
    int h, w;
    cin >> h >> w;
    string s;
    vector<string> v(h);
    vector<int> l, r;
    for (int i = 0; i < h; i++) {
        cin >> s;
        v[i] = s;
    }
    bool flag;
    for (int i = 0; i < h; i++) {
        flag = true;
        for (int j = 0; j < w; j++) {
            if (v[i][j] == '#') {
                flag = false;
                break;
            }
        }
        if (flag) {
            l.push_back(i);
        }
    }
    for (int i = 0; i < w; i++) {
        flag = true;
        for (int j = 0; j < h; j++) {
            if (v[j][i] == '#') {
                flag = false;
                break;
            }
        }
        if (flag) {
            r.push_back(i);
        }
    }
    
    int num = 0;
    if (l.size() == 0 && r.size() == 0) {
        for (int i = 0; i < h; i++) {
            cout << v[i] << endl;
        }
    }else{
        for (int i = 0; i < h; i++) {
            if (l.size() == 0 || i != l[num]) {
                for (int j = 0; j < w; j++) {
                    if (r.size() == 0) {
                        cout << v[i][j];
                    }else{
                        flag = true;
                        for (int k = 0; k < r.size(); k++) {
                            if (j == r[k]) {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            cout << v[i][j];
                        }
                    }
                }
                cout << endl;
            }else{
                num++;
            }
        }
    }
}


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

typedef pair<int,int> pii;

#define fi first
#define se second

struct s {
	int time;
	pii foot;
	int nex;
	s() {};
	s(int t, pii f, int n) {
		time = t; foot = f; nex = n;
	}
};

bool operator<(const s &a, const s &b) {
	return a.time > b.time;
}

bool visit[70][70][2];
int w, h;
vector<string> v;

int main() {
	while(cin >> w >> h, w || h) {
		for(int i = 0; i < 70; i++)
			for(int j = 0; j < 70; j++)
				visit[i][j][0] = visit[i][j][1] = false;
		v.clear();
		for(int i = 0; i < h; i++) {
			string a = "";
			for(int j = 0; j < w; j++) {
				string b;
				cin >> b;
				a += b;
			}
			v.push_back(a);
		}
		priority_queue
 q;
		for(int i = 0; i < v.size(); i++) {
			for(int j = 0; j < v[i].size(); j++) {
				if(v[i][j] == 'S') {
					visit[i][j][0] = visit[i][j][1] = 1;
					q.push(s(0, pii(i,j), 0));
					q.push(s(0, pii(i,j), 1));
				}
			}
		}

		int res = -1;
		while(q.size()) {
			s a;
			a = q.top(); q.pop();
			if(v[a.foot.fi][a.foot.se] == 'T') {
				res = a.time;
				break;
			}

			for(int i = -2; i <= 2; i++) {
				for(int j = 1; j <= 3; j++) {
					if(abs(i) + abs(j) > 3) continue;
					int nx, ny;
					ny = a.foot.fi + i;
					if(a.nex)
						nx = a.foot.se + j;
					else
						nx = a.foot.se - j;
					if(ny < 0 || h <= ny || nx < 0 || w <= nx)
						continue;
					if(!visit[ny][nx][!a.nex] && v[ny][nx] != 'X') {
						if(v[ny][nx] == 'T')
							q.push(s(a.time, pii(ny,nx), !a.nex));
						else
							q.push(s(a.time+v[ny][nx]-'0', pii(ny,nx), !a.nex));
						visit[ny][nx][!a.nex] = true;
					}
				}
			}
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 1252
#include <stdio.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

const static int MAX = 50;
int n, k;
char C[MAX];
string s;

int main() {
    scanf("%d %d", &n, &k);
    scanf("%s", C);
    s = C;
    if ( s[k-1] == 'A' ) {
        s[k-1] = 'a';
    } else if ( s[k-1] == 'B' ) {
        s[k-1] = 'b';
    } else {
        s[k-1] = 'c';
    }
    printf("%s\n", s.c_str());
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb emplace_back
#define mt make_tuple
#define gcd __gcd
#define bitcount(x)  __builtin_popcount(x)
#define bitcountll(x)  __builtin_popcountll(x)
#define PI 3.141592653589
// Input
#define in(a) scanf("%d",&a)
#define in2(a,b) scanf("%d%d",&a,&b)
#define in3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define llin(a) cin >> a
#define inl(a) scanf("%lld",&a)
#define read(v,i,n) for(i=0;i<n;i++)in(v[i])
#define twod(mat,i,j,n,m) rep(i,n){rep(j,m)in(mat[i][j]);}
#define sc(ch) scanf("%c",&ch)
#define sstr(str) scanf("%s",str)
// Output
#define pr(a) printf("%d ",a)
#define pr2(a,b) printf("%d %d\n",a,b)
#define pr3(a,b,c) printf("%d %d %d\n",a,b,c)
#define out(a) printf("%d\n",a)
#define outl(a) printf("%lld\n",a)
#define llpr(a) cout << a << " "
#define llout(a) cout << a << "\n"
#define yes printf("YES\n")
#define no printf("NO\n")
#define lin printf("\n")
// Iterator
#define lp(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define lower(v,k) lower_bound(v.begin(),v.end(),k)-v.begin()
#define upper(v,k) upper_bound(v.begin(),v.end(),k)-v.begin()
#define tf(mytuple) get<0>(mytuple)
#define ts(mytuple) get<1>(mytuple)
#define tt(mytuple) get<2>(mytuple)
// Debug
#define dbg(v,i,n) for(i=0;i<n;i++)pr(v[i]); lin
#define what(x) cerr << #x << " : " << x << "\n"
#define ck printf("continue\n")
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
	cerr << *it << " = " << a << "\n";
	err(++it, args...);
}
// Data Type
#define ll long long int
#define ii pair<int,int>
#define pli pair<ll,int>
#define triple tuple<int,int,int>
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vvi vector<vector<int> >
#define viii vector<pair<pair<int,int>,int> >
#define vvii vector<vector<pair<int,int> > >
#define M 1000000007
#define N 500003  //check the limits, man
int main()
{
    int a,b,c;
    in3(a,b,c);
    b/=a;
    b=min(b,c);
    out(b);
}


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

int N,A;
bitset<4000001> b;

int main(){
	cin>>N;
	b[0]=1;
	for(int i=0;i<N;++i){
		cin>>A;
		b|=(b<<A);
	}
	int c=b.count()/2;
	for(int i=1;;++i){
		if(b[i])--c;
		if(!c){
			cout<<i<<endl;
			return 0;
		}
	}
}


Measured memory_bytes: 1664
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;

void main()
{
	auto nq = readln.chomp.split.map!(to!int);
  BinaryHeap!(Array!(int[]), "a[0] == b[0] ? a[1] > b[1] : a[0] < b[0]") q;
  auto num = new int[](nq[0]+1);

  foreach (_; 0..nq[1]) {
    auto x = readln.chomp.split.map!(to!int);
    num[x[0]] += x[1];
    int a[2];
    a[0] = num[x[0]];
    a[1] = x[0];
    q.insert(a.dup);
    
    while (!q.empty) {
      a = q.front;
      if (a[0] == num[a[1]]) {
        writeln(a[1], " ", a[0]);
        break;
      }
      q.removeFront;
    }
  }
}

Measured memory_bytes: 12168
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) {
  return '"' + s + '"';
}
string to_string(const char* s) {
  return to_string((string) s);
}
string to_string(bool b) {
  return (b ? "true" : "false");
}
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
 
#define ll long long
const long long mod = 1e9+7; // CHECK
long long power(long long a, long long b, long long m = mod) {
    if(b < 0) {
        return power(power(a, -b), mod-2);
    }
    long long x = 1;
    while(b) {
        if(b & 1) {
            x = 1ll * x * a % m;
        }
        a = 1ll * a * a % m;
        b /= 2;
    }
    return x;
}
// *****************************************************
// const long long INF = 2e18;
const int N = 3e5+9;

signed main() {  
    ios_base::sync_with_stdio(false); 
    #ifndef LOCAL
    cin.tie(0); cout.tie(0);
    #endif

    
    ll n, z, w; cin >> n >> z >> w;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    if(n == 1) {
        cout << abs(a[0]-w) << '\n';
        return 0;
    }
    cout << max(abs(a[n-1] - w), abs(a[n-2] - a[n-1])) << "\n";

    
    
    






    return 0;
    
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using Int = int64_t;
using UInt = uint64_t;
using C = std::complex<double>;
#define rep(i, n) for(Int i = 0; i < (Int)(n); ++i)
#define guard(x) if( not (x) ) continue;
#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif

Int mod = 1000000007;

Int fact[1123456];

void init() {
   fact[0] = 1;
   for(Int i = 1; i < 1123456; ++i) {
      fact[i] = fact[i-1] * i % mod;
   }
}

Int pow(Int x, Int n) {
   if( n == 0 ) return 1;
   Int t = pow(x,n/2);
   return n % 2 == 0 ? (t * t % mod) : (t * t % mod * x % mod);
}

Int div(Int x, Int y) {
   return x * pow(y, mod-2) % mod;
}

Int nCr(Int n, Int r) {
   if( r < 0 or n < r ) return 0;
   return div(fact[n], fact[r] * fact[n-r] % mod);
}

int main() {
   init();
   Int n;
   std::cin >> n;
   Int res = 0;
   std::vector<Int> xs(n);
   for(Int k = 0; k < n; ++k) {
      xs[k] = nCr(k-1, n-k-1) * fact[k] % mod * fact[n-1-k] % mod;
   }
   for(Int k = 0; k < n; ++k) {
      Int diff = (xs[k] - xs[k-1] + mod) % mod;
      Int t = diff * k % mod;
      res = (res + t) % mod;
   }
   printf("%ld\n", res);
}


Measured memory_bytes: 16896
INF = float('inf')

N, W = map(int, input().split())

# dp[i][j] : i番目までの品物を使い、価値がjとなるときの重さ
dp = [[INF] * 100010 for _ in range(N + 1)]
for i in range(N + 1):
    dp[i][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(100010):
        if j >= v:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - v] + w)
        else:
            dp[i][j] = dp[i - 1][j]

ans = 0
for i in range(100010):
    if 0 < dp[N][i] <= W:
        ans = max(ans, i)

print(ans)

Measured memory_bytes: 247896
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 500
		int a = sc.nextInt();
		// 100
		int b = sc.nextInt();
		// 50
		int c = sc.nextInt();
		// 合計
		int x = sc.nextInt();

		int p = 0;

		for (int i = 0; i <= a; ++i) {
			for (int j = 0; j <= b; ++j) {
				for (int k = 0; k <= c; ++k) {
					if (i * 500 + j * 100 + k * 50 == x) {
						p++;
					}
				}
			}
		}

		// 出力
		System.out.println(p);
	}
}

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

namespace Hit_and_Blow
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string l1 = Console.ReadLine();
                if (string.IsNullOrEmpty(l1)) break;
                string[] n1 = l1.Split(' ');
                string[] n2 = Console.ReadLine().Split(' ');
                int[] a = new int[4];
                int[] b = new int[4];
                for (int i = 0; i < 4; ++i)
                {
                    a[i] = int.Parse(n1[i]);
                    b[i] = int.Parse(n2[i]);
                }
                int hit = 0, blow = 0;
                for (int i = 0; i < 4; ++i)
                {
                    for (int j = 0; j < 4; ++j)
                    {
                        if (a[i] == b[j] && i == j)
                        {
                            ++hit;
                        }
                        else if (a[i] == b[j] && i != j)
                        {
                            ++blow;
                        }
                    }
                }
                string ans = hit.ToString() + " " + blow.ToString();
                Console.WriteLine(ans);
            }
        }
    }
}



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

int main(){
  int a, b, c, x, y, z;
  int i, imin, sum, min = 10000000000;

  cin >> a >> b >> c >> x >> y;

  if( x>y ){
    z = x;
  }else{
    z = y;
  }
 
  for( i=0; i<=z; i++ ){
    if( i<=x && i<=y ){
      sum = (x-i)*a + (y-i)*b + i*c*2;
    }else if( i>x ){
      sum = (y-i)*b + i*c*2;
    }else{
      sum = (x-i)*a + i*c*2;
    }
      
    if( sum < min ){
      min = sum;
      //imin = i;
      //      cout << i << " " << sum << " " << min << endl;
    }
  }
  cout << " " << min << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();
		int X = scan.nextInt() - 1;
		int Y = scan.nextInt() - 1;
		int[][] distance = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = i+1; j < N; j++) {
				distance[i][j] = j-i;
			}
		}

		for (int x = 0; x < Y; x++) {
			for (int y = X+1; y < N; y++) {
				if (distance[x][y] > Math.abs(X-x) + Math.abs(Y-y) + 1) {
					distance[x][y] = Math.abs(X-x) + Math.abs(Y-y) + 1;
				}
			}
		}

		int[] ans = new int[N];

		for (int x = 0; x < N; x++) {
			for (int y = x+1; y < N; y++) {
				ans[distance[x][y]]++;
			}
		}

		for (int i = 1; i < N; i++) {
			System.out.println(ans[i]);
		}

	}

}

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

using namespace std;
using ll = long long;
#define int ll

void init();
void solve();

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a, b) for (int i = (int) (a); i < (int) (b); i++)
#define rrep(i, a) for (int i = (int) a-1; i >= 0; i--)
#define rreps(i, a, b) for (int i = (int) (a)-1; i >= (int) (b); i--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define TRUE__  "YES"
#define FALSE__ "NO"
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x

#ifdef LOCAL
#define lcout(a) cout << a
#define lcoutln(a) cout << a << endl
#define lcerr(a) cerr << a
#define lcerrln(a) cerr << a << endl
#else
#define lcout(a) 
#define lcoutln(a) 
#define lcerr(a) 
#define lcerrln(a) 
#endif
#define MOD 1000000007
#define PI 3.141592653589793238462643383

signed main()
{
	init();
	solve();
}

vector<int> sum;
int N;

void init()
{
	cin >> N;
	sum.resize(N+1);
	sum[0] = 0;
	reps(i, 1, N+1) {
		cin >> sum[i];
		sum[i] += sum[i-1];
	}
}

ll culc(int x)
{
	ll y = x;
	return y * (y - 1) / 2;
}

void solve()
{
	ll res = 0;
	sort(all(sum));
	rep(i, N+1) {
		int j = i + 1;
		int t = 1;
		while (sum[i] == sum[j] && j < N+1) {
			t++;
			j++;
		}
		i = j - 1;
		res += culc(t);
	}
	cout << res << endl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<math.h>
#include<algorithm>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)

using namespace std;

int main(){
	int d, n, x = 1, c, os = 0;
	cin >> d >> n;
	if (n == 100){
		os = 1;
	}
	REP(i,d){
		x *= 100;
	}
	cout << x * (n+os) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define level first
#define cnt second
using namespace std;
typedef pair<int,int> ii;
 
int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	int arr[n]; for(int i = 0;i < n;i++) cin >> arr[i];
	
	bool increasing = true;
	for(int i = 1;i < n;i++){
		if(arr[i] <= arr[i-1]) increasing = false;
	}
	
	if(increasing || n == 1){
		cout << 1;
		return 0;
	}
	
	int low = 1, high = n;
	while(low != high - 1){
		int mid = (low+high)/2;
		
		vector<ii> S = {ii(-1,0)};
		
		bool can = true;
		
		for(int i = 1;i < n;i++){
			
			if(arr[i-1] >= arr[i]){
				int cur = arr[i];
				
				while(S.back().level > cur) S.pop_back();
				
				while(true){
					if(S.back().level < cur){
						S.push_back(ii(cur,1));
						break;
					}
					else{
						S.back().cnt++;
						if(S.back().cnt == mid){
							S.pop_back();
							cur--;
							if(cur == 0){
								can = false;
								break;
							}
						}
						else{
							break;
						}
					}
				}				
			}
			
		}

		if(can) high = mid;
		else low = mid;
	}
	
	cout << high;
}


Measured memory_bytes: 4432
INF = 1 << 29
 
def contain(names)
  contained = []
  names.permutation(2).each do |s, t|
    contained << t if s.include?(t)
  end
  contained.each{ |name| names.delete(name) }
  names
end
 
def overlap(names, size)
  overlap_size = size.times.map{ [0] * size }
  (0...size).to_a.permutation(2).each do |i, j|
    k = [@len[i], @len[j]].min
    loop do
      if names[i][@len[i]-k..-1] == names[j][0,k]
        overlap_size[i][j] = k
        break
      end
      k -= 1
    end
  end
  overlap_size
end
 
 
while n = gets.to_i
  break if n == 0
  s = n.times.map{ gets.chomp }
  s = contain(s)
  m = s.size
  @len = s.map{ |name| name.size }
  overlap_size = overlap(s, m)
  dp = (1<<m).times.map{ [INF] * m }
  m.times{ |i| dp[1<<i][i] = @len[i] }
  (1<<m).times do |bits|
    m.times do |i|
      if (bits & (1<<i)) != 0
        pre = dp[bits][i]
        m.times do |j|
          bit = 1 << j
          if (bits & bit) == 0
            if dp[bits | bit][j] > pre + @len[j] - overlap_size[i][j]
              dp[bits | bit][j] = pre + @len[j] - overlap_size[i][j]
            end
          end
        end
      end
    end
  end
  p dp[(1<<m)-1].min
end

Measured memory_bytes: 20836
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i,n) for (int i = (int)(n)-1; i>=0; --i)
#define For(i,a,b) for(auto i=(a);i<=(b);++i)
#define rFor(i,a,b) for(auto i=(b);i>=(a);--i)
#define call(var) cerr<<#var<<"="<<var<<"\n";
#define dup(x,y) (((x)+(y)-1)/(y))
#define all(x) (x).begin(),(x).end()
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
const double pi = acos(-1);
template<class t,class u> inline bool chmax(t&a,u b){if(a<b){a=b;return true;}return false;}
template<class t,class u> inline bool chmin(t&a,u b){if(b<a){a=b;return true;}return false;}


void cerrall(const vector<bool>& a){rep(i,a.size()) cerr << i << " " << (a[i]? "True" : "False") << "\n"; cerr << "\n";}
template<class T> void cerrall(const vector<T>& a){for(auto& t : a) cerr << t << " "; cerr << "\n";}
template<class T> void cerrall(const set<T>& a){for(auto& t : a) cerr << t << " "; cerr << "\n";}
template<class T> void cerrall(const multiset<T>& a){for(auto& t : a) cerr << t << " "; cerr << "\n";}
template<class T, class U> void cerrall(const vector<pair<T,U>>& a){rep(i,a.size()) cerr << i << " : " << a[i].first << " " << a[i].second << "\n";}
template<class T, class U> void cerrall(const map<T,U>& a){for(auto& t : a) cerr << t.first << " " << t.second << "\n";}
template<class T, class U> void cerrall(const unordered_map<T,U>& a){for(auto& t : a) cerr << t.first << " " << t.second << "\n";}

template<class T> istream& operator>>(istream& is, vector<T>& a){rep(i,a.size()) is >> a[i]; return is;}
template<class T> ostream& operator<<(ostream& os, vector<T>& a){rep(i,a.size()) os << a[i] << " "; return os;}

template<class T, class U> istream& operator>>(istream& is, pair<T,U>& p){is >> p.first >> p.second; return is;}
template<class T, class U> ostream& operator<<(ostream& os, const pair<T,U>& p){os << "("<< p.first << "," << p.second << ")"; return os;}
template<class T, class U> ostream& operator<<(ostream& os, const map<T,U>& mp){for(auto& t : mp) os << t.first << " " << t.second << "\n"; return os;}

int main(){
    ll a;
    string b;cin >> a >> b;
    ll ans = 0;
    ans += (ll)(b[0] - '0') * 100;
    ans += (ll)(b[2] - '0') * 10;
    ans += (ll)(b[3] - '0');
    //call(ans);
    ans = a * ans / 100;
    cout << ans << endl;
}

Measured memory_bytes: 3628
MOD=10**9+7
def func(s):
    abc="ABC"
    n = len(s)
    dp=[[0 for _ in range(3+1)] for _ in range(n+1)]
    dp[n][3]=1

    for i in range(n-1,-1,-1):
        for j in range(3,-1,-1):
            if j==3:
                if s[i]=='?':
                    dp[i][j]=(dp[i+1][j]*3)%MOD
                else:
                    dp[i][j]=dp[i+1][j]
            else:
                m1=3 if s[i]=='?' else 1
                m2=1 if s[i]=='?' or s[i]==abc[j] else 0
                dp[i][j]=((m1*dp[i+1][j])%MOD +(m2*dp[i+1][j+1])%MOD)%MOD
    return dp[0][0]
print(func(input()))


Measured memory_bytes: 27572
#include <iostream>
#include <string>
using namespace std;
int main()
{
string S, T;
cin>>S>>T;
int N=S.size(), ans=0;
for(int i=0; i<=N; ++i)
{
	if(S[i] != T[i])
	{
		++ans;
	}
}
cout<<ans<<endl;
// abcde
// bcdea
}


Measured memory_bytes: 3920
#include <iostream>
#include <vector>

using namespace std;


int main()
{
	int N, M;
	cin >> N >> M;
	vector<int> a(N + 1, 1);
	for (int i = 0; i < M; i++)
	{
		int m;
		cin >> m;
		a[m] = 0;
	}

	vector<int> dp(N + 3, 0);

	dp[0] = 1;
	for (int i = 0; i <= N; i++)
	{
		dp[i + 1] += a[i] * dp[i];
		dp[i + 1] %= 1000000007;
		dp[i + 2] += a[i] * dp[i];
		dp[i + 2] %= 1000000007;
	}

	cout << dp[N] << endl;

	return 0;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <iterator>
#include <functional>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <fstream>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <list>
#include <sstream>
#include <complex>
#include <stdio.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef double LD;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LD, LD> PDD;
typedef pair<LL, LL> PLL;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<char> VCH;
typedef vector<LD> VLD;
typedef vector<string> VS;
typedef vector<VS> VSS;
typedef vector<VI> VVI;
typedef vector<VLL> VVLL;
typedef vector<VCH> VVCH;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef vector<PDD> VPDD;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
#define next fake_next
#define prev fake_prev
#define left fake_left
#define right fake_right

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, t) FOR(i,0,t)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())

const LD PI = acos(-1.0);
const LL mod = 1000000007;
const LL INF = 1e9;
const LL LINF = 1e18;
const LL MAXN = 5e3 + 1;

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);

	LL x, y;
	cin >> x >> y;

	LL ans = 1;

	while (x <= y)
	{
		if (x * 2 <= y)
			x *= 2LL, ++ans;
		else
			break;
	}

	cout << ans;
	//cin >> x;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace _517_LongestSteps
{
	class Program
	{
		static void Main ( string[] args )
		{
			while (true)
			{
				//input
				int[] orderNumber = Console.ReadLine ().Split (' ').Select (str => int.Parse (str)).ToArray ();

				bool isEnd = orderNumber.All (item => item == 0);
				if (isEnd)
				{
					break;
				}

				int dealCardCount = orderNumber[1];
				int[] cardArray = new int[dealCardCount];
				for (int lp = 0; lp < cardArray.Length; lp++)
				{
					cardArray[lp] = int.Parse (Console.ReadLine ());
				}

				//process
				int whiteCardCount = cardArray.Count (item => item == 0);
				cardArray = cardArray.Where (item => item != 0).OrderBy (item => item).ToArray ();

				List<ChainNumber> list = new List<ChainNumber> (cardArray.Length / 10);

				int previousItem = cardArray[0];
				int count = 1;

				//????´?????????¨??????
				for (int lp = 1; lp < cardArray.Length; lp++)
				{
					//????????????
					int item = cardArray[lp];

					//???????????¨????????????= n + 1??§????????°
					if (previousItem + 1 == item)
					{
						//????????????????¢???????
						count++;
					}
					//!= n + 1??§????????°
					else
					{
						//?????¨?????? - ???????????§?¨???????????????????????????¢???????????????????????????
						int spaceCount = item - previousItem - 1;

						//????´??????°??????
						ChainNumber number = new ChainNumber (count, spaceCount);
						list.Add (number);

						//????????????
						count = 1;
					}

					previousItem = item;

					//????????????
					if (lp + 1 == cardArray.Length)
					{
						ChainNumber number = new ChainNumber (count, 0);
						list.Add (number);
					}
				}

				int loop = 0;
				int maxLength = 0;

				//?????¨??????????´?????????¨??????????????§?????????????±???????
				while (loop < list.Count)
				{
					//?????????
					int length = 0;
					int instanceWhiteCardCount = whiteCardCount;

					//????´??????????????????????????´?????¶?????????????????????§
					while (loop < list.Count)
					{
						length += list[loop].Length;

						int needWhiteCardCount = list[loop].SpaceCount;

						//????´?????¶?????????°
						if (needWhiteCardCount <= instanceWhiteCardCount)
						{
							//?¶????
							instanceWhiteCardCount -= needWhiteCardCount;
							length += needWhiteCardCount;

							//????????????????????????
							loop++;
						}
						else
						{
							//?????????
							break;
						}
					}

					//????????????????????????
					loop++;

					//????´?????????£???????????°
					if (0 < instanceWhiteCardCount)
					{
						length += instanceWhiteCardCount;
					}

					//??????
					if (maxLength < length)
					{
						maxLength = length;
					}
				}

				//output
				Console.WriteLine (maxLength);
			}
		}

		class ChainNumber
		{
			public ChainNumber ( int length,int spaceCount )
			{
				this.Length = length;
				this.SpaceCount = spaceCount;
			}

			public int Length { private set; get; }
			public int SpaceCount { private set; get; }
		}
	}
}

Measured memory_bytes: 13436