akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template<class T> inline bool chmax(T& a, T b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, T b) {if (a>b) {a=b; return true;} return false;}

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

const ll MAX = 200005;
vll fac(MAX, 0), finv(MAX, 0), inv(MAX, 0);

void initCombTable() {
  fac.at(0) = 1; fac.at(1) = 1;
  finv.at(0) = 1; finv.at(1) = 1;
  inv.at(1) = 1;
  rep(i, 2, MAX) {
    fac.at(i) = fac.at(i-1) * i % MOD;
    inv.at(i) = MOD - inv.at(MOD%i) * (MOD / i) % MOD;
    finv.at(i) = finv.at(i-1) * inv.at(i) % MOD;
  }
}

ll nCk(ll n, ll k) {
  if (n < 0 || k < 0 || n < k) return 0;
  return fac.at(n) * (finv.at(k) * finv.at(n-k) % MOD) % MOD;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    initCombTable();
    ll n, m, k; cin >> n >> m >> k;
    ll ans = 0;
    rep(i, 1, n) {
        ll tmp = i*(((n-i)*m%MOD)*m%MOD)%MOD;
        tmp = (tmp * nCk(n*m-2, k-2)) % MOD;
        ans += tmp;
        if (ans >= MOD) ans -= MOD;
    }
    rep(i, 1, m) {
        ll tmp = i*(((m-i)*n%MOD)*n%MOD)%MOD;
        tmp = tmp*nCk(n*m-2, k-2)%MOD;
        ans += tmp;
        if (ans >= MOD) ans -= MOD;
    }
    cout << ans << '\n';
    return 0;
}


Measured memory_bytes: 4992
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    # p = tuple(geta(lambda s: int(s.decode()[2:])))
    p = tuple(geta(float))

    dp = [[0] * (i + 2) for i in range(N + 1)]
    dp[0][0] = 1

    for i, pi in enumerate(p, 1):
        qi = 1 - pi
        dpi = dp[i]
        dpi1 = dp[i - 1]

        dpi[0] = dpi1[0] * qi

        for j in range(1, i + 1):
            dpi[j] = dpi1[j - 1] * pi + dpi1[j] * qi

    print(sum(dp[N][N // 2 + 1:]))


if __name__ == "__main__":
    main()

Measured memory_bytes: 148444
// first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN  reverse replace stringstream string::npos length substr front
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()
const ll mod = 1e9 + 7 ;
const ll inf =
 // 1e9 + 5 ;
 1e18L + 5;
const ll nax = 2e5 + 5;
void min_self(ll&a , ll b){a=min(a,b);}
void max_self(ll&a , ll b){a=max(a,b);}
void add_self(ll&a , ll b){a=(a+b)%mod;}
//#define (x)  get<0>(x) 
//#define (x)  get<1>(x)
//#define (x)  get<2>(x)
signed main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n ;cin>> n; 
ll arr[n];for(ll i = 0 ; i<n ; i++)cin>>arr[i]; 

vector<vector<ll>>dp(n,vector<ll>(n,inf));
auto sum = [&](ll L , ll R){
	ll s = 0;
	for(ll i = L ; i<=R ; i++){
		s+=arr[i];
	}
	return s;

};

for(ll L = n-1 ; L>= 0 ; L--){
	for(ll R = L ; R<n ; R++){
		if(L == R)dp[L][R] = 0 ;
		else {
			ll s = sum(L,R);
			for(ll i = L  ; i< R ; i++){

				min_self(dp[L][R] , dp[L][i] + dp[i+1][R] + s);


			}



		}
	}
}

	cout<<dp[0][n-1];

	
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
int ans;
void ttor(int n, int r)
{
    if (n)
    {
        ttor(n / r, r);
        ans++;
    }
}
int main()
{
	int n,k;
	cin>>n>>k;
    ttor(n,k);
	cout<<ans<<endl;
}

Measured memory_bytes: 256
ll = lambda: list(map(int, input().split()))
testcases = 1
def abs(x):
    if x<0:
        return -x
    return x
# testcases = int(input())
for testcase in range(testcases):
    [n]=ll()
    weight=ll()
    pres=[0]
    for i in weight:
        pres.append(pres[-1]+i)
    minabs=100000000
    for i in range(1,n+1):
        minabs=min(minabs,abs(pres[i]-(pres[-1]-pres[i])))
    print(minabs)


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

int main()
{
	long long  a, b, n;
	cin >> n >> a >> b;
	if (n > 1 && b >= a || n == 1 && a == b)
		cout << (n - 2)*(b - a) + 1 << endl;
	else
		cout << 0 << endl;
	return 0;
}

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

using namespace std;
#define int long long

int  solve(int w,int n, int *weight,int * value)
{
	int dp[n+1][w+1];
	memset(dp,0,sizeof(dp));


	for(int i=1;i<=n;i++)
	{
		
		for(int j=1;j<=w;j++)
		{
			int ans=INT_MIN;
			if(j>=weight[i])
			{
				ans=max(dp[i-1][j],value[i]+dp[i-1][j-weight[i]]);
			}
			else
			{
				ans=dp[i-1][j];
			}

			dp[i][j]=ans;
		}
		
	}

	return dp[n][w];
}
int32_t main()
{
	int n,w;
	cin>>n>>w;

	int weight[n+1],value[n+1];

	for(int i=1;i<=n;i++)
	{
		cin>>weight[i]>>value[i];
	}

	cout<<solve(w,n,weight,value)<<endl;

	return 0;
}

Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll (i)=0; (i)<(n); (i)++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define pll pair<ll,ll> 
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
int inf=1000001000;
ll INF=100000000000000000;
ll MOD=1000000007;
//g++ code.cpp   ./a.out 

int main() {
   ll n;
   cin >> n;
   vector<ll> a(5);
   rep(i,5) cin >> a[i];
   sort(a.begin(),a.end());
   ll ans=(n+(a[0]-1))/a[0]+4;
   cout << ans << endl;
}



Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define Sort(Array) sort(Array.begin(), Array.end())
#define Reverse(a) reverse(a.begin(), a.end())
#define out(ans) cout << ans << endl;
const int MOD = 1000000007;
const int INF = 2147483647;

//------------↓------------- M -------------- E ---------------- M --------------- O ---------------↓--------------//
// コンパイル 
// g++ -std=c++1z
//
// -------型変換--------
// int を string に変換
// string s = to_string(n);
// string を int に変換
// int n = stoi(s);
//
// -------二分探索---------
// k以上の値が最初に現れる時のイテレータ
// lower_bound(data.begin(), data.end(), k)
// kより大きい値が最初の現れる時のイテレータ O(logN)
// upper_bound(data.begin(), data.end(), k)
// kがdataに存在するかをtrue or falseで返す O(logN)
// binary_search(data.begin(), data.end(), k)
// 
//
//
//
//
//
// 
//------------↑------------- M -------------- E ---------------- M --------------- O ---------------↑--------------//


int main() {

    string s; cin >> s;
    bool flag = false;
    if (s[0] == s[1] && s[2] == s[3] && s[1] != s[2]) flag = true;
    if (s[0] == s[2] && s[1] == s[3] && s[2] != s[1]) flag = true;
    if (s[0] == s[3] && s[1] == s[2] && s[3] != s[1]) flag = true;

    if (flag) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}






Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,M=map(int,input().split())
h=list(map(int,input().split()))
edge=[[] for _ in range(N)]
for _ in range(M):
    a,b=map(int1,input().split())
    edge[a].append(b)
    edge[b].append(a)
ans=0
for i in range(N):
    for nv in edge[i]:
        if h[nv]>=h[i]:
            break
    else:
        ans+=1
print(ans)

Measured memory_bytes: 95392
// template version 1.9

// varibable settings {{{
using namespace std;
#include <iostream>
#include <bits/stdc++.h>

#define int long long
const int INF=1e18;
const int MOD=1e9+7;
#define infile "../test/sample-1.in"
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
#define fi first
#define se second

// }}}

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)(b-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;
template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;

// dump macro
#ifdef PCM
  #include "dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;
// }}}

int solve(){
  int R,G,B,N;
  cin>>R>>G>>B>>N;

  int res=0;
  rep(r, N+1)rep(g, N+1){
    int x = r*R + g*G;
    if (x<=N and (N-x)%B==0) res++;
  }
  cout << res << endl;

  return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long n,d,t[100000],f[100000],nf=1,nt=0,nd=0,ans=0;
  cin>>n>>d;
  for(int i=0;i<n;i++){
    scanf("%lld %lld",&t[i],&f[i]);
  }
  for(int i=0;i<n;i++){
    long long dist=abs(f[i]-nf);
    long long T=t[i]-nt;
    if(T<dist){
      cout<<-1<<endl;
      return 0;
    }
    if(nf-1+f[i]-1<=T){
      ans+=nd*(nf-1);
      nd=0;
    }else{
      ans+=nd*T;
    }
    nd++;
    if(nd>d){
      cout<<-1<<endl;
      return 0;
    }
    nf=f[i];
    nt=t[i];
  }
  ans+=nd*(nf-1);
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 4808
n=int(input())
s=input()
f=0
for i in [[0,0],[0,1],[1,0],[1,1]]:
  d=[i[0],i[1]]
  for j in range(2,n):
    d.append((d[-2]+d[-1]+int(s[j-1]=="x"))%2)
  if (int(d[-2]==d[0])+d[-1]+int(s[-1]=="x"))%2 and (int(d[-1]==d[1])+d[0]+int(s[0]=="x"))%2:
    f=1
    break
if f:
  for i in d:
    if i:
      print("W",end="")
    else:
      print("S",end="")
  print()
else:
  print(-1)

Measured memory_bytes: 10068
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define SUM(a)  accumulate((a).begin(),(a).end(),0)
#define SORT(a) sort(ALL(a))
#define REV(a) reverse(ALL(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
typedef long long ll;
const int INTINF = 1<<29;
const ll LLINF = 1LL<<61;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
const int DX[8]={ 0, 1, 0,-1, 1, 1,-1,-1};
const int DY[8]={ 1, 0,-1, 0, 1,-1, 1,-1};


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  string s;
  cin >> n;
  cin >> s;
  int ans = 0;
  char old = ' ';
  REP(i,n){
    if (s[i]!=old){
      old = s[i];
      ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
	for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) true
#define dump(x) true
#endif

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);		//DON'T USE scanf/printf/puts !!
	cout << fixed << setprecision(20);
	
	int N; cin >> N;
	V<ll> L(N),R(N);
	rep(i,N) cin >> L[i] >> R[i], L[i]--;
	int LMAX = 0, RMIN = 0;
	rep(i,N){
		if(L[LMAX] < L[i]) LMAX = i;
		if(R[RMIN] > R[i]) RMIN = i;
	}
	ll ans = 0;
	{
		ll longest = 0;
		rep(i,N) if(i != LMAX && i != RMIN) chmax(longest,R[i]-L[i]);
		if(longest > 0){
			ans = longest + max(R[RMIN]-L[LMAX],0LL);
		}
	}

	auto inter = [&](int i,int j){
		return max(0LL, min(R[i],R[j]) - max(L[i],L[j]));
	};

	if(LMAX != RMIN){
		ll X = R[RMIN]-L[RMIN], Y = R[LMAX] - L[LMAX];
		using P = pair<ll,ll>;
		V<P> vs;
		rep(i,N) if(i != LMAX && i != RMIN){
			vs.emplace_back(inter(RMIN,i),inter(LMAX,i));
		}
		sort(all(vs),greater<P>());
		int K = vs.size();
		V<ll> a(K+1),b(K+1);
		a[0] = X; rep(i,K) a[i+1] = min(a[i],vs[i].fs);
		b[0] = Y; rep(i,K) b[i+1] = min(b[i],vs[K-1-i].sc);
		rep(i,K+1) chmax(ans,a[i]+b[K-i]);
	}
	cout << ans << endl;
}


Measured memory_bytes: 4976
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

bool is_lower(char &c){
  if('a' <= c && c <= 'z'){
    return true;
  }
  return false;
}

bool is_upper(char &c){
  if('A' <= c && c <= 'Z'){
    return true;
  }
  return false;
}

void to_lower(char &c){
  c += 'a' - 'A';
}

void to_upper(char &c){
  c += 'A' - 'a';
}

int main(){
  string str;
  getline(cin,str);
  for(int i=0;i<str.length();i++){
    if(is_lower(str[i])){
      to_upper(str[i]);
    }else if(is_upper(str[i])){
      to_lower(str[i]);
    }
    printf("%c",str[i]);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 3196
#include <stdio.h>

int main(void) {

	int A;
	int B;
    int C;

	scanf("%d", &A);
	scanf("%d", &B);
    scanf("%d", &C);

    int num1 = A - B;
    int num2 = C - num1;
    
    if(num2 < 0){
      puts("0");
    }
    else{
      printf("%d",num2);
    }
	return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<utility>
#include<cmath>
#include<cstring>
#include<map>
#include<sstream>
 
using namespace std;

long long H,W;

int main(){
  
  cin>>H>>W;
  
  long long sum = W*H;
  
  if(W == 1 || H == 1){
  	sum = 1;
  }else if (sum % 2 == 0){
  	sum /= 2;
  }else{
  	sum /= 2;
    sum++;
  }
  cout<<sum;
}


Measured memory_bytes: 256
var ans,s,s1,news:string;
    i:longint;
    c:char;
    n:longint;
    v:array['a'..'z']of boolean;
begin
  readln(s);
  n:=length(s);
  ans:='';
  for i:=1 to 27 do
  ans:=ans+'z';
  for i:=1 to n do
  begin
    v[s[i]]:=true;
    for c:='a' to 'z' do
    if (not v[c])and(c>=s[i]) then
    begin
      news:=s1+c;
      if (news<ans)and(news>s) then ans:=news;
    end;
    s1:=s1+s[i];
  end;
  for c:='a' to 'z' do
  if (not v[c]) then
  begin
    news:=s1+c;
    if (news<ans)and(news>s) then ans:=news;
  end;
  if length(ans)=27 then writeln(-1)else writeln(ans);
end.

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/math/common_factor.hpp>

#define rep_ui(k,n)      for(ui  i = (k); i < (n); ++i)
#define rep_si(k,n)      for(int i = (k); i < (n); ++i)
#define rep_ul(k,n)      for(ul  i = (k); i < (n); ++i)
#define rep_sl(k,n)      for(ll  i = (k); i < (n); ++i)
#define rep_ui_down(k,n) for(ui  i = (k); i > (n); --i)
#define rep_si_down(k,n) for(int i = (k); i > (n); --i)
#define rep_ul_down(k,n) for(ul  i = (k); i > (n); --i)
#define rep_sl_down(k,n) for(ll  i = (k); i > (n); --i)

#define rep_uj(k,n)      for(ui  j = (k); j < (n); ++j)
#define rep_sj(k,n)      for(int j = (k); j < (n); ++j)
#define rep_uj_down(k,n) for(ui  j = (k); j > (n); --j)
#define rep_sj_down(k,n) for(int j = (k); j > (n); --j)

#define rep(k,n)         rep_ui(k,n)

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

template<class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vc)
{
#ifdef BOOST_RANGE_ALGORITHM_FOR_EACH_HPP_INCLUDED
  boost::for_each(vc, [&os](T value) {
#else
  std::for_each(vc.begin(), vc.end(), [&os](T value) {
#endif
    os << value << '\n';
    });
  return os;
}

template<class T1, class T2>
inline
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p)
{
  return os << p.first << ' ' << p.second;
}

void solve(void)
{
  using std::string;
  using std::vector;
  using std::map;
  using std::pair;
  using std::cin;
  string S{}; std::cin >> S;
  //ui N{}; cin >> N;
  ui N = S.length();

  vector<ull> pattern(2);
  rep(0, 2)
  {
    rep_uj(0, N)
    {
      if ((S[j] - '0' ) ^ (i + j) % 2)
      {
        ++pattern[i];
      }
    }
  }


  ull ans = std::min(pattern[0], pattern[1]);

  using std::cout;
  cout << ans << '\n';
  return;
}

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

  solve();

  return 0;
}


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

using namespace std;

int main(void) {
    string s;
    cin >> s;

    string ans;
    for(int i=0; i<s.size(); i++) {
        if(s[i] != 'B') {
            ans.push_back(s[i]);
        } else if(!ans.empty()) {
            ans.pop_back();
        }
    }

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


Measured memory_bytes: 256
#pragma region head
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
#define double long double
typedef double ld;
const int INF = 1001001001001001001ll;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
#pragma endregion

signed main() {
  string S;
  cin >> S;
  int d = S[len(S) - 1] - '0';

  if (d == 3)
    cout << "bon" << endl;
  else if (d == 0 || d == 1 || d == 6 || d == 8)
    cout << "pon" << endl;
  else
    cout << "hon" << endl;
}

Measured memory_bytes: 3652
#include<iostream>
#include<list>
using namespace std;
int main() {
	list<int> line;
	int code;
	char codename[11];
	int time;
	cin >> time;
	list<int >::iterator he;
	for (int i = 0; i < time; ++i) {
		cin >> codename;
		if (codename[6] == 'F')line.pop_front();
		else if (codename[6] == 'L')line.pop_back();
		else {
			cin >> code;
			if (codename[0] == 'i')line.push_front(code);
			else {
				line.push_back(code);
				for (he = line.begin(); *he != code; ++he);
				if (++he != line.end())line.erase(--he);
				line.pop_back();
			}
		}
	}
	int doll = line.back();
	line.pop_back();
	for (he = line.begin(); he != line.end(); ++he) {
		cout << *he << ' ';
	}
	cout << doll << endl;
	cin >> time;
	return 0;
}

Measured memory_bytes: 32444
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():

    s=str(input())
    if s in ['AKIHABARA','AKIHABAR','AKIHABRA','AKIHABR',\
             'AKIHBARA','AKIHBARA','AKIHBRA','AKIHBR',\
             'KIHABARA','KIHABAR','KIHABRA','KIHABR',\
             'KIHBARA','KIHBAR','KIHBRA','KIHBR']:
        print('YES')
    else:
        print('NO')

resolve()

Measured memory_bytes: 38384
#include <stdio.h>
int main(){
	long long p=0;
	int a,b,c,x,y,i,j,k,l;
	scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);
	if(a+b<=2*c){
	printf("%d",a*x+b*y);
	return 0;
	
}
k=x;
if(k>y)k=y;
p=k*2*c;
x-=k;
y-=k;
if(x>0){
if(a>2*c)p+=2*c*x;
 else p+=a*x;
}
if(y>0){
if(b>2*c)p+=2*c*y;
 else p+=b*y;	
}
printf("%lld",p);
return 0;
}

Measured memory_bytes: 128
#include<stdio.h>

int main(){

    int A, B;
    int Add, Sub, Mul;
    int Result;

    scanf("%d %d", &A, &B);

    Add = A + B;
    Sub = A - B;
    Mul = A * B;

    if(Add >= Sub && Add >= Mul){
        Result = Add;
    }
    else if(Sub >= Add && Sub >= Mul){
        Result = Sub;
    }
    else{
        Result = Mul;
    }

    printf("%d", Result);

    return 0;
}


Measured memory_bytes: 128
import sys
h=['light ','']
for e in sys.stdin:
 e=float(e)
 for i in range(7):
  if[81,69,60,57,54,51,0][i]<e:print([h[e>91]+'heavy',h[e>75]+'middle',h[e>64]+'welter','light','feather','bantam',h[e>48]+'fly'][i]);break


Measured memory_bytes: 5592
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define INF (1 << 29)
#define LLINF (1LL << 60)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;

string to_string(string s) { return s; }

template <class S, class T>
string to_string(pair<S, T> p) {
  return "{" + to_string(p.first) + "," + to_string(p.second) + "}";
}

template <class S>
string to_string(unordered_set<S> s) {
  string ret = "{";
  for (S x : s) ret += to_string(x) + ",";
  return ret + "}";
}

template <class S, class T>
string to_string(map<S, T> m) {
  string ret = "{";
  for (pair<S, T> x : m) ret += to_string(x) + ",";
  return ret + "}";
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < (int)v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() { cerr << endl; }

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() { cout << endl; }

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  cin.tie(0);
  ll N;
  cin >> N;
  ll ans = N;
  for (ll i = 1; i * i <= N; ++i) {
    if (N % i > 0) continue;
    ll j = N / i;
    ans = min(ans, i + j - 2);
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 384
import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        for(int i = 0; i < 300; i++) {
          String line = sc.nextLine();
          String[] l = line.split(" ");
          int H = Integer.parseInt(l[0]);
          int W = Integer.parseInt(l[1]);
          if(H == 0 && W == 0) {
            break;
          }

          int flag;
          for(int h = 0; h < H; h++) {
            if(h % 2 == 0) {
              flag = 0;
            } else {
              flag = 1;
            }

            for(int w = 0; w < W; w++) {
              if(flag == 0) {
                System.out.print("#");
                flag = 1;
              } else {
                System.out.print(".");
                flag = 0;
              }
            }

            System.out.println();
          }

          System.out.println();
        }
    }
}

Measured memory_bytes: 32964
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
 
typedef long long int ll;
const ll N = 1e6 +9;
const ll p = 31;
const ll m = 1e9 + 7;
const ll inf= 1e14;
const ll mod = 1e9+7;
#define w first
#define v second
#define pb push_back
#define mp make_pair
using pii = pair<ll, ll>;
std::vector<ll> g[N];
ll powm(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }
ll lp[N];
bool vis[N];
void dfs(ll v){
     ll ans = 1;
     vis[v] = 1;
     for(auto i:g[v]){
          if(!vis[i])dfs(i);
          ans=max(ans,lp[i]+1);
     }
     lp[v] = ans;
}
int main() {   
     ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    

     ll q = 1;
     // cin>>q;
     while(q--){
          ll n,m;cin>>n>>m;
          string a[n];
          for(int i = 0;i<n;i++){
               cin>>a[i];
          }
          ll dp[n][m];
          for(int i = 0;i<n;i++){
               for(int j = 0;j<m;j++){
                    if(a[i][j]=='#'){
                         dp[i][j]=0;
                    }

                    else if(i==0 && j==0){
                         dp[i][j] = 1;
                    }
                    else if(i==0){
                         dp[i][j] = dp[i][j-1];
                    }
                    else if(j==0){
                         dp[i][j] = dp[i-1][j];
                    }
                    else{

                         dp[i][j] = (dp[i-1][j]+dp[i][j-1])%mod;
                    }

               }
          }
          cout<<dp[n-1][m-1]<<'\n';
     }
}         

Measured memory_bytes: 33152
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> P;

class Edge
{
	public:
	ll cost;
	int to;
	int from;

	Edge(int f,int t,ll c)
	{
		from=f;
		to=t;
		cost=c;
	}
};

class UF
{
	int node;//ノード数
	vector<int> parent;//親
	vector<int> depth;//深さ
	vector<int> size;//直径

	public:
	//コンストラクタ
	UF(int n)
	{
		node=n;
		parent.resize(n);
		depth.resize(n,0);
		size.resize(n,1);
		for(int i=0;i<node;i++)
			parent[i]=i;
	}

	//根を求める
	int find(int x)
	{
		int prex=x;
		while(parent[x]!=x)
		{
			x=parent[x];
			parent[prex]=parent[x];
			prex=x;
		}
		return x;
	}

	//併合
	void unite(int x,int y)
	{
		int parx=find(x);
		int pary=find(y);
		if(parx==pary)
			return;
		if(depth[parx]<depth[pary])
		{
			parent[pary]=parx;
			size[parx]+=size[pary];
		}else{
			parent[parx]=pary;
			size[pary]+=size[parx];
			if(depth[parx]==depth[pary])
				depth[pary]++;
		}
	}
	//同じ集合か
	bool same(int x,int y)
	{
		return find(x)==find(y);
	}
	//直径を求める
	int getsize(int x)
	{
		return size[find(x)];
	}
};

bool operator>(const Edge &lhs,const Edge &rhs)
{
	return lhs.cost>rhs.cost;
}

bool comp(const pair<P,int> &lhs, const pair<P,int> &rhs)
{
	if(lhs.first.second==rhs.first.second)
		return lhs.first.first<rhs.first.first;
	else
		return lhs.first.second<rhs.first.second;
}

pair<P,int> xy[100000];
priority_queue<Edge,vector<Edge>,greater<Edge>> que;
int main()
{
	int n;
	ll ans=0;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		ll x,y;
		cin>>x>>y;
		xy[i]=make_pair(P(x,y),i);
	}
	sort(xy,xy+n);//x昇順にソート
	//辺を作る
	for(int i=1;i<n;i++)
	{
		ll c=abs(xy[i].first.first-xy[i-1].first.first);
		que.push(Edge(xy[i-1].second,xy[i].second,c));
	}
	sort(xy,xy+n,comp);//y昇順にソート
	for(int i=1;i<n;i++)
	{
		ll c=abs(xy[i].first.second-xy[i-1].first.second);
		//cerr<<xy[i].first.second<<endl;
		que.push(Edge(xy[i-1].second,xy[i].second,c));
	}
	//辺張り終了
	UF u=UF(n);//ufの初期化
	//最小全域木
	while(u.getsize(0)<n)
	{
		Edge e=que.top();
		que.pop();
		//cerr<<u.getsize(0)<<" "<<e.from<<"<->"<<e.to<<" "<<e.cost<<endl;
		if(!u.same(e.from,e.to))
		{
			ans+=e.cost;
			//cerr<<ans<<endl;
			u.unite(e.from,e.to);
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 8816
use proconio::*;

#[fastout]
#[allow(non_snake_case)]
fn main() {
    input! {
        K: usize,
        A: usize, B: usize
    }
    let mut ans = false;
    for i in A..B + 1 {
        if i % K == 0 {
            ans = true;
        }
    }
    println!("{}",
        if ans { "OK" } else { "NG" }
    )
}

Measured memory_bytes: 2168
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        init();

        int P = nextInt(), Q = nextInt(), R = nextInt();

        System.out.println(Math.min(P + Q, Math.min(Q + R, R + P)));
    }

    //Input Reader
    private static BufferedReader reader;
    private static StringTokenizer tokenizer;

    private static void init() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    private static String next() throws IOException {
        String read;
        while (!tokenizer.hasMoreTokens()) {
            read = reader.readLine();
            if (read == null || read.equals(""))
                return "-1";
            tokenizer = new StringTokenizer(read);
        }

        return tokenizer.nextToken();
    }

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

Measured memory_bytes: 22996
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
using namespace std;
#define pi pair<int32,int32>
#define pl pair<int64,int64>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
// cout << fixed << setprecision(10);
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

int main(){
	string s; cin >> s;
	reverse(s.begin(),s.end());
	string t[4] = {"maerd","remaerd","esare","resare"};
	int index = 0,n = s.size();
	while (true){
		bool flg = false;
		for (int i = 0; i < 4; i++){
			if (s.substr(index,t[i].size()) == t[i]){
				flg = true;
				index += t[i].size();
				break;
			}
		}
		if (index >= n){
			cout << "YES" << endl;
			return 0;
		}
		if (flg){
			continue;
		} else {
			cout << "NO" << endl;
			return 0;
		}
	}
}
 


Measured memory_bytes: 512
import sys
input = sys.stdin.readline

INF = (1<<60)

N = int(input())
graph = [[] for _ in range(N)]
Edges = []
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    Edges.append((a-1, b-1))

def bfs(s, noback):
    q = [s]
    D = [-1]*N
    D[s] = 0
    while q:
        qq = []
        for p in q:
            for np in graph[p]:
                if D[np] == -1 and np != noback:
                    D[np] = D[p] + 1
                    qq.append(np)
        q = qq
    
    Ds = [0]*(N+1)
    faraway = 0
    for i, d in enumerate(D):
        faraway = max(faraway, d)
        Ds[d] = max(Ds[d], len(graph[i])-1)
    return Ds, faraway

colorful = INF
nodes = INF

for n in range(N):
    M = [0]*(N+1)
    far = 0
    leaves = 0
    for s in graph[n]:
        leaves += 1
        Ds, faraway = bfs(s, n)
        far = max(far, faraway)
        for i, d in enumerate(Ds):
            M[i] = max(M[i], d)
    color = far + 2
    if color <= colorful:
        if color != colorful:
            nodes = INF
        colorful = color
        for f in range(far):
            leaves *= M[f]
        if leaves < nodes:
            nodes = leaves

for a, b in Edges:
    M = [0]*(N+1)
    leaves = 2
    D1, faraway1 = bfs(a, b)
    for i, d in enumerate(D1):
        M[i] = max(M[i], d)
    
    D2, faraway2 = bfs(b, a)
    for i, d in enumerate(D2):
        M[i] = max(M[i], d)
    
    far = max(faraway1, faraway2)
    color = far + 1
    if color <= colorful:
        if color != colorful:
            nodes = INF
        colorful = color
        for f in range(far):
            leaves *= M[f]
        if leaves < nodes:
            nodes = leaves

print(colorful, nodes)

Measured memory_bytes: 74708
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>

template <typename Tp>
bool includes(std::set<Tp> const& x, std::set<Tp> const& y) {
  for (auto const& yi: y) if (!x.count(yi)) return false;
  return true;
}

int testcase_ends() {
  size_t N;
  scanf("%zu", &N);
  if (N == 0) return 1;

  std::vector<std::set<int>> p(N);
  for (auto& pi: p) {
    size_t M;
    scanf("%zu", &M);
    for (size_t i = 0; i < M; ++i) {
      int pp;
      scanf("%d", &pp);
      pi.insert(pp);
    }
  }

  size_t K;
  scanf("%zu", &K);

  std::set<int> l;
  for (size_t i = 0; i < K; ++i) {
    int ll;
    scanf("%d", &ll);
    l.insert(ll);
  }

  std::set<size_t> res;
  for (size_t i = 0; i < N; ++i) {
    if (includes(p[i], l)) res.insert(i+1);
  }
  if (res.size() != 1) return puts("-1"), 0;
  printf("%zu\n", *res.begin());
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int n;
  string s;
  cin >> n >> s;
  int ans = 0, x = 0;
  rep(i, n) {
    if(s[i] == 'I') {
      x++;
      ans = max(ans, x);
    } else
      x--;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
def main():
    N, K, Q = list(map(int, input().split(' ')))
    correct_counts = [0 for _ in range(N)]
    for _ in range(Q):
        A = int(input())
        correct_counts[A - 1] += 1
    for i in range(N):
        ans = 'Yes' if K - Q + correct_counts[i] > 0 else 'No'
        print(ans)


if __name__ == '__main__':
    main()

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

#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define reset(a, v) memset((a), v, sizeof(a))

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

const int N = 100005;

int n;
char S[N];

int main() {
	scanf("%s", S);
	n = strlen(S);
	int ans = n;
	for (int i = 0; i < n-1; ++i) {
		if (S[i] == S[i+1]) continue;
		ans = min(ans, max(i+1, n-1-i));
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 384
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

int main() {
    string s;
    cin >> s;
    reverse(all(s));
    if(s[0] == '0' || s[0] == '1' || s[0] == '6' || s[0] == '8') {
        cout << "pon" << endl;
    }

    if(s[0] == '2' || s[0] == '4' || s[0] == '5' || s[0] == '7' || s[0] == '9') {
        cout << "hon" << endl;
    }

    if(s[0] == '3') {
        cout << "bon" << endl;
    }
}

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

using namespace std;

int main() {
    vector<int> a = vector<int>(3);
    cin >> a[0] >> a[1] >> a[2];
    sort(a.begin(), a.end());
    cout << (a[1] - a[0]) + (a[2] - a[1]) << "\n";
}

Measured memory_bytes: 384
/*▄███████▀▀▀▀▀▀███████▄
░▐████▀▒ЗАПУСКАЕМ▒▀██████▄
░███▀▒▒▒▒▒ДЯДЮ▒▒▒▒▒▒▀█████
░▐██▒▒▒▒▒БОГДАНА▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄█████████████  █▒▒▐▌
░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐*/
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#include <iostream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <math.h>
#include <set>
#include <stack>
#include <bitset>
#include <map>
#include <queue>
#include <random>
#include <unordered_set>
#include <unordered_map>
#define DEBUG
#define fi first
#define se second
#define pqueue priority_queue
#define pb(x) push_back(x)
// #define endl '\n'
#define all(x) x.begin(), x.end()
#define int long long
#define mk(a, b) make_pair(a, b)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<vector<ll> > vvi;
typedef vector<ull> vull;
typedef vector<ll> vll;
// typedef tuple<ll, ll, ll> tiii;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector< vector<ll> > vvi;
typedef vector<char> vc;

const ll INF = 1e9;
const ll INFLL = 1e18;
const ll MOD = 1e9 + 7;
// const ll MAXN = 3e5;
const ld eps = 1e-6;
const ld eps2 = 1e-9;
const ll MOD2 = 998244353;
const ll dosz = 5e5;
const ll SZ = (1<<18);
const ld PI = atan2l(0, -1);


void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
        // freopen("a.in", "r",stdin);
#else
       // freopen("tickets.in", "r", stdin);
       // freopen("tickets.out", "w", stdout);
#endif
}

void solve(){
    string s;
    cin >> s;
    if(s=="ABC"){
        cout << "ARC" << endl;
    } else{
        cout << "ABC" << endl;
    }
} 

signed main() {
    fast_io();
    ll q = 1;
    // cout << fixed;
    // cin >> q;
    while(q--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define pi 3.14159
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int N = 2e7 + 9, M = 1e7, OO = 0x3f3f3f3f;
#define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin.sync_with_stdio(0);
int main()
{
int n,k,x,y;
scanf("%d %d %d %d",&n,&k,&x,&y);
if(n<=k){
    printf("%d",n*x);
}
else{
    printf("%d",(k*x)+(n-k)*y);
}



    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 2000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
int main() {
	int a, b;
	cin >> a >> b;
	string s;
	cin >> s;
	for (int i = 0;i < a;++i) {
		if (s[i] >= '0'&&s[i] <= '9') {

		}
		else {
			cout << "No" << endl;
			return 0;
		}
	}
	if (s[a] != '-') {
		cout << "No" << endl;
		return 0;
	}
	for (int i = a + 1;i < 1+a + b;++i) {
		if (s[i] >= '0'&&s[i] <= '9') {

		}
		else {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

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

    unordered_map<string, int64_t> dp;
    dp[""] = 1;

    for (auto i : irange(0L, n)) {
        decltype(dp) next;

        for (const auto& kv : dp) {
            const auto& key = kv.first;
            auto v = kv.second;

            // cerr << i << ":" << key << "=" << v << endl;

            auto last2 =
                    key.empty()
                            ? string()
                            : key.substr(
                                      max(static_cast<int64_t>(key.size()) - 2,
                                          0L),
                                      min(key.size(), 2uL));

            next[last2 + "A"] += v;
            if (last2 != "AC") {
                next[last2 + "G"] += v;
            }
            if (last2 != "AG" && last2 != "GA" &&
                !(key.size() == 3 && key.substr(0, 2) == "AG") &&
                !(key.size() == 3 && key[0] == 'A' && key[2] == 'G')) {
                next[last2 + "C"] += v;
            }
            next[last2 + "T"] += v;
        }

        for (auto&& kv : next) {
            kv.second %= 1000000007L;
        }

        dp = std::move(next);
    }

    int64_t ans = 0;
    for (const auto& kv : dp) {
        ans += kv.second;
        ans %= 1000000007L;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ld long double
#define int long long
using namespace std;
const int N = 2e5 + 50;
const int mod = 1e9 + 7;
const int inf = 1e17;
int dx[] = {0, 1, -1, 0, -1, 1, 1, -1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, m;
  cin >> n >> m;
  vector<pair<int,int> > store(n);
  for(int i = 0; i < n; i++){
  	cin >> store[i].first >> store[i].second;
  }
  sort(store.begin(), store.end());
  int ans = 0;
  for(int i = 0; (i < n && m > 0); i++){
  	ans += min(store[i].second, m) * store[i].first;
  	m -= min(store[i].second, m);
  }
  cout << ans;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll under[1000500];
ll over[1000500];
ll n, q, k, d;

void query(int now) {
    ll delta = (over[now+1] - under[now+1] + 1 + n) % n;
    if(delta * 2 >= n || delta == 0) {
        under[now] = 1;
        over[now] = n;
        return;
    }
    ll after = under[now+1];
    if(after > n / 2) after - n / 2;
    ll new_under = ((after-1) * 2 + 1) % n;
    under[now] = new_under;
    over[now] = (new_under + delta * 2 - 1 + n) % n;
    return;
}

bool isin(ll under, ll over, ll val) {
    if(under <= over) {
        if(((under <= val) && (val <= over))) {
            //cout << -1 << endl;
            return true;
        }
    } else {
        if(((val >= under) || (val <= over))) {
            //cout << -1 << endl;
            return true;
        }
    }
    //cerr << "FAILED " << under << " " << over << " " << val << endl;
    return false;
}

ll one(ll now) {
    if(now % 2 == 0) {
        return now / 2;
    }
    return n / 2 + (now + 1) / 2;
}

ll zero(ll now) {
    if(now % 2 == 0) {
        return n / 2 + now / 2;
    }
    return (now + 1) / 2;
}

int main() {
    cin >> n >> q >> k >> d;
    over[q] = d;
    under[q] = d;
    for(int i = q - 1; i >= 0; i--) {
        query(i);
    }
    for(int i = 0; i <= q; i++) {
        //cout << under[i] << " " << over[i] << endl;
    }
    /*
    if(under[0] < over[0]) {
        if(!((under[0] <= k) && (k <= over[0]))) {
            //cout << -1 << endl;
            return 0;
        }
    } else {
        if(!((k >= under[0]) || (k <= over[0]))) {
            //cout << -1 << endl;
            return 0;
        }
    }
    */
    if(!isin(under[0], over[0], k)) {
        cout << -1 << endl;
        return 0;
    }
    vector<int> ans;
    ll now = k;
    for(int i = 1; i <= q; i++) {
        ll NEW = zero(now);
        //cout << i << " NEWNUMBER : " << NEW << endl;
        if(isin(under[i], over[i], NEW)) {
            ans.push_back(0);
            now = NEW;
            //cout << "0 " << now << endl;
            continue;
        }
        NEW = one(now);
        ans.push_back(1);
        now = NEW;
        //cout << "1 " << now << endl;
    }
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
    return 0;
}


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

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

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int H, W;
  cin >> H >> W;

  vector<string> s(H);
  int cnt = 0;
  for (int i = 0; i < H; i++) {
    cin >> s[i];
    for (int j = 0; j < W; j++) {
      cnt += (s[i][j] == '#');
    }
  }

  queue<pii> que;
  que.emplace(0, 0);
  int d[50][50];
  memset(d, -1, sizeof(d));
  d[0][0] = 1;
  while (!que.empty()) {
    pii p = que.front(); que.pop();
    int y = p.first, x = p.second;
    for (int i = 0; i < 4; i++) {
      int ny = y + dy[i], nx = x + dx[i];
      if (ny >= 0 && ny < H && nx >= 0 && nx < W && s[ny][nx] == '.' && d[ny][nx] < 0) {
        que.emplace(ny, nx);
        d[ny][nx] = d[y][x] + 1;
      }
    }
  }
  cout << (d[H - 1][W - 1] < 0 ? -1 : H * W - cnt - d[H - 1][W - 1]) << endl;

  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
const long long md=1e9+7;
long long n,dp[101010][5];
vector<long long>g[101010];
void dfs(long long x,long long y)
{
	dp[x][0]=1;
	dp[x][1]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i];
		if(to!=y)
		{
			dfs(to,x);
			dp[x][0]=(dp[x][0]*(dp[to][0]+dp[to][1])%md)%md;
			dp[x][1]=(dp[x][1]*dp[to][0])%md;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		x--;
		y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(0,0);
	cout<<(dp[0][0]+dp[0][1])%md<<endl;
	return 0;
}

Measured memory_bytes: 16640
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(s) s.begin(), s.end()
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
const int DIV = 1e9+7;

int main()
{
    ll n, m, r;
    vector<ll> mati;
    cin >> n >> m >> r;
    mati.resize(r);
    rep(i,r){
        ll in;
        cin >> in;
        mati[i] = in-1;
    }
    ll d[200][200];
    rep(i,200){
        rep(j,200){
            d[i][j] = LINF;
        }
    }
    rep(i,m){
        ll a,b,c;
        cin >> a >> b >> c;
        d[a-1][b-1] = c;
        d[b-1][a-1] = c;
    }
    rep(k,n){
        rep(i,n){
            rep(j,n){
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
            }
        }
    }
    sort(all(mati));
    ll ans=LINF;
    do {
        ll dis=0;
        rep(i,r){
            if(i==0) continue;
            dis += d[mati[i]][mati[i-1]];
        }
        ans = min(ans, dis);
    }while(next_permutation(all(mati)));
    cout << ans << endl;
}


Measured memory_bytes: 512