akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll mod =1e9+7;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,a,b) for(int i=(a);i<(b);++i)

template<class T> T maxt(T x,T y) {if (x>y) return x;else return y;}
template<class T> T mint(T x,T y) {if (x>y) return y;else return x;}
//sort(v.begin(), v.end(), [](auto& x, auto& y){return x[1] < y[1];});


//小数出力
double print_double(double d){printf("%.11f", d);}

//約数列挙
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}



// ll combination_mod(int n, int k) {
//   k = mint(k,n-k);
//   ll ans = 1;
//   if (n==0 || k ==0) return ans;
//   rep(i,k) {
//     ans = ans*(n-i)%mod;
//     ans = ans*modinv(i+1)%mod;
//   }
//   return ans;
// }

struct edge {
  int from; //出発点
  int to;   //到達点
  ll cost; //移動コスト
};

//ベルマンフォード法
vector<ll> bellman_ford (vector<edge> edges, int V, int E, int r, ll INF = 100000000000) {  
  vector<ll> cost_to(V,INF);
  cost_to[r] = 0;
  rep(i,V) {
    rep(j,E) {
      edge e = edges[j];
      if (cost_to[e.from]==INF) continue;
      if (cost_to[e.to] > cost_to[e.from] + e.cost) {
        cost_to[e.to] = cost_to[e.from] + e.cost;
        if (i==V-1) {
          printf("NEGATIVE CYCLE\n");
          return {};
        }
      }

    }
  }
  return cost_to;
}

// combination
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}


// 木上の探索
vector<int> cnt;
void dfs(const vector<vector<int>> &G, int v, int p) {
    for (auto nv : G[v]) {
        if (nv == p) continue; // nv が親 p だったらダメ
        dfs(G, nv, v);
    }

    // 帰りがけ時に、部分木サイズを求める
    cnt[v] = 1; // 自分自身
    for (auto c : G[v]) {
        if (c == p) continue;
        cnt[v] += cnt[c]; // 子のサイズを加える
    }
}

int main() {
  int N;
  cin >> N;
  string S1,S2;
  cin >> S1 >> S2;
  vector<int> memo;
  rep(i,N) {
    if (S1[i]!=S2[i]) {
      memo.push_back(1);
      i++;
    }
    else memo.push_back(0);
  }
  ll ans = 1;
  rep(i,memo.size()) {
    if (i==0) {
      if (memo[i]) ans*=6;
      else ans*=3;
    }
    else {
      if (memo[i]) {
        if (memo[i-1]) ans*=3;
        else ans*=2;
      }
      else {
        if (memo[i-1]) ans*=1;
        else ans*=2;
      }
    }
    // cout << ans << endl;
    ans%=mod;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){  
  cin.tie(0);
  ios::sync_with_stdio(0);
  string s;
  while(getline(cin,s),s!="0"){
    Int m=count(s.begin(),s.end(),'x')*2-1;
    if(m==1){
      cout<<s<<endl;
      continue;
    }
    
    Int cur=0;
    vector<Int> L(m,-1),R(m,-1);
    
    function<Int(string)> dfs=[&](string s){
      //cout<<s<<endl;
      Int v=cur++;
      if(s=="x"){
	return v;
      }
      Int op=0;
      for(Int i=0;i<(Int)s.size();i++){
	if(s[i]=='(') op++;
	if(s[i]==')') op--;
	if(op==1&&s[i]==' '){
	  string ls=s.substr(1,i-1);
	  string rs=s.substr(i+1,s.size()-(i+2));
	  L[v]=dfs(ls);
	  R[v]=dfs(rs);
	  return v;
	}
      }
    };
    dfs(s);

    vector<string> sh(m);
    vector<set<string> > dp(m);
    vector<Int> p(m),q(m);
    vector<Int> p1(m),q1(m);
    vector<Int> p2(m),q2(m);

    auto check=[&](Int a,Int b,Int c,Int d){
      return a*d>c*b;
    };
    
    function<void(Int)> dfs2=[&](Int v){
      if(L[v]<0){
	p[v]=0;q[v]=1;
	sh[v]="()";
	dp[v].emplace(sh[v]);
	return;
      }
      dfs2(L[v]);
      dfs2(R[v]);
      
      set<string> uni;
      dp[v]=dp[R[v]];
      for(auto ss:dp[L[v]]){
	dp[v].emplace(ss);
	if(dp[R[v]].count(ss))
	  uni.emplace(ss);
      }
      p[v]=uni.size();
      q[v]=dp[v].size();
      
      sh[v]="("+(sh[L[v]]<sh[R[v]]?sh[L[v]]+sh[R[v]]:sh[R[v]]+sh[L[v]])+")";      
      dp[v].emplace(sh[v]);

      p1[v]=L[v];p2[v]=R[v];
    };
    dfs2(0);

    function<void(Int, Int)> dfs4=[&](Int v,Int k){
      if(L[v]<0) return;
      function<Int(Int,Int)> ccc=[&](Int a,Int b)->Int{
	if(check(p[a],q[a],p[b],q[b])){
	  return 1;
	}
	
	if(check(p[b],q[b],p[a],q[a])){
	  return 0;
	}
	
	if(!p[a]&&!p[b]){
	  return 0;
	}

	if(ccc(p1[a],p2[a])){
	  swap(p1[a],p2[a]);
	}

	if(ccc(p1[b],p2[b])){
	  swap(p1[b],p2[b]);
	}
	
	if(ccc(p1[a],p1[b])){
	  return 1;
	}
	
	if(ccc(p1[b],p1[a])){
	  return 0;
	}
	
	if(ccc(p2[a],p2[b])){
	  return 1;
	}
	
	return 0;
      };
      if(k^ccc(L[v],R[v])) swap(L[v],R[v]);
      dfs4(L[v],0);
      dfs4(R[v],1);
    };
    dfs4(0,0);

    stringstream ss;
    function<void(Int)> dfs3=[&](Int v){
      if(L[v]<0){
	ss<<"x";
	return;
      }
      ss<<"(";
      dfs3(L[v]);
      ss<<" ";
      dfs3(R[v]);
      ss<<")";
    };
    dfs3(0);
    cout<<ss.str()<<endl;
  }
  return 0;
}




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

int* fa;


void initset(int* s, int n)
{
    for (int i = 0; i < n; i++)
    {
        s[i] = i;
    }
}

int findfa(int a)
{
    if (a == fa[a])
        return a;
    else
    {
        fa[a] = findfa(fa[a]);
        return fa[a];
    }
}

void mergefa(int a, int b)
{
    fa[findfa(fa[b])] = findfa(fa[a]);
}




int main()
{
    int n, q;
    cin >> n >> q;
    fa = new int[n];
    initset(fa, n);
    int sig, a, b;
    queue<int> res;
    for (int i = 0; i < q; i++)
    {
        cin >> sig >> a >> b;
        if (sig)
        {
            if (findfa(a) != findfa(b))
                res.push(0);
            else
                res.push(1);
        }
        else
        {
            mergefa(a, b);
        }
    }
    while (!res.empty())
    {
        cout << res.front() << endl;
        res.pop();
    }
    return 0;

}


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

int main()
{
   long long n ;
   cin>>n ;
   vector<long long> vec(n,1) ;
   for(int i=2;i<n;i++)
   {
       for(int j=i;j<n;j=j+i)
       {
           vec[j]++ ;
       }
   }
   long long ans=0 ;
   for(int i=1;i<n;i++)
   {
       ans+=vec[n-i] ;
   }
   cout<<ans<<endl ;
    return 0;
}


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

using namespace std;

long long int euclid(long long int x, long long int y){
  long long int t;
  t = min(x,y);
  x = max(x,y);
  y = t;
  long long int r = x % y;
  long long int tmp = y;
  
  while(r != 0){
    tmp = r;
    r = y % r;
    y = tmp;
  }
  return tmp;
}

int mylog2(long long int n){
  int cnt = 0;
  while(n != 0){
    if(n % 2 != 0) break;
    n /= 2;
    cnt++;
  }
  return cnt;
}

int main(){
  int N;
  cin >> N;
  vector<long long int> V(N);
  for(int i = 0; i < N; i++){
    cin >> V[i];
  }
  long long int tmp = euclid(V[0], V[1]);
  //cout << tmp << " ";
  for(int i = 1; i < N-1; i++){
    tmp = euclid(tmp, V[i+1]);
    //cout << tmp << " ";
  }
  if(N == 1){
    cout << mylog2(V[0]);
  }else{
    cout << mylog2(tmp);
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
using namespace std;

void solve(string s){
	int ans = 700;
	for(char c : s){
		if(c=='o') ans+=100;
	}
	cout << ans << endl;
}

int main() {
	string s; cin >> s;
//	string s = "oxo";
	solve(s);
	return 0;
}


Measured memory_bytes: 256
program b173

implicit none
integer :: ac, wa, tle, re, n, i
character(len=3) :: a

ac = 0
wa = 0
tle = 0
re = 0

read *, n

do i = 1, n

 read *, a
 
 if (trim(a) == 'AC') then
  ac = ac + 1
 else if (trim(a) == 'WA') then
  wa = wa + 1
 else if (trim(a) == 'TLE') then
  tle = tle + 1
 else
  re = re + 1
 end if
end do

print *, 'AC x ', ac
print *, 'WA x ', wa
print *, 'TLE x ', tle
print *, 'RE x ', re

end program b173

Measured memory_bytes: 2868
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace C
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var NM = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var N = NM[0];
            var M = NM[1];
            var graph = new List<int>[N].Select(x => new List<int>()).ToArray();
            for (var i = 0; i < M; i++)
            {
                var ab = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
                var a = ab[0] - 1;
                var b = ab[1] - 1;
                graph[a].Add(b);
                graph[b].Add(a);
            }

            var answer = 0;
            for (var i = 0; i < N; i++)
            {
                var ok = true;
                for (var j = 0; j < N; j++)
                {
                    if (graph[j].Count == 1)
                    {
                        var index = graph[j].First();
                        graph[index].Remove(j);
                        graph[j].Clear();
                        answer++;
                        ok = false;
                    }
                }
                if (ok) break;
            }
            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 28384
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
// #pragma GCC optimize ("Ofast,unroll-loops,-ffloat-store")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

string to_string(const string& s) { return '"' + s + '"'; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
    #define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 3
#endif
 
#define cin_exception cin.exceptions(cin.failbit);
#define cout_precision cout.setf(ios::fixed); cout.precision(15);
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using ld = long double; using vi = vector<int>;
using ll = int_fast64_t; using ull = uint_fast64_t;
using vl = vector<ll>; using vul = vector<ull>;

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

void solve() {
    cout_precision;
    int l; cin >> l;
    l = l * l * l;
    cout << ld(l) / 27 << '\n';
}

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

int main() {
    fast_io;
#ifdef LOCAL
    cin_exception;
#endif
    int t = 1;
    // cin >> t;
    // preprocess();
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <vector>
#include  <string>
#include  <cstring>
#include  <stack>
#include  <queue>
#include  <cmath>
#include  <iomanip>
#include  <set>
#include  <map>
#include  <new>
#include <cstdint>
#include <cctype>
using namespace std;
#define rep(i,n)  for(int i = 0; i < n; i++)
#define lrep(i,n,m)  for(int i = n; i < m; i++)

using ll = long long;
using Vii = vector<vector<int> >;
using Gjudge = vector<vector<bool>>;
using Vi = vector<int>;
using Vl = vector<ll>;
using Vll = vector<vector<ll> >;
using Vs = vector<string>;
using Vb = vector<bool>;
using the = pair<int, int>;
using lthe = pair<ll, ll>;

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

const int Mod = static_cast<int>(1e9 + 7);
const int INF = INT_MAX;
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,1,0,-1 };


priority_queue<the> p[200000];
const int MAXP = 2 * 1e5;

int main()
{
	string s, t;
	cin >> s;
	t = s;

	transform(s.begin(), s.end(), s.begin(), ::toupper);
	if (t == s) {
		cout << "A" << endl;
	}
	else {
		cout << "a" << endl;
	}
}


Measured memory_bytes: 9872
#include<stdio.h>

#define N 100000

int ID[N]={0};

void def(){
	int i;
	for(i=0;i<N;++i){
		ID[i]=i;
	}
}
int find(int a){
	if(a==ID[a]){
		return a;
	}
	return ID[a]=find(ID[a]);
}

int Judge(int a, int b){
	if(find(a)==find(b))return 1;
	else return 0;
}

void unite(int a, int b){
	a=find(a);
	b=find(b);
	
	if(a==b)return;
	ID[b]=a;
}

int main(){
	int n,m,q,i,s,t;
	def();
	scanf("%d %d\n", &n, &m);
	for(i=0; i<m; i++){
		scanf("%d %d\n", &s, &t);
		unite(s,t);}
	scanf("%d\n",&q);
	
	for(i=0; i<q; i++){
		scanf("%d %d\n", &s, &t);
		if (Judge(s,t) == 1)printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

Measured memory_bytes: 2076
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(char &c){
  int i;
  for(;;){
    i = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c = i;
}
inline int rd(char c[]){
  int i;
  int sz = 0;
  for(;;){
    i = my_getchar_unlocked();
    if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
      break;
    }
  }
  c[sz++] = i;
  for(;;){
    i = my_getchar_unlocked();
    if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
      break;
    }
    c[sz++] = i;
  }
  c[sz]='\0';
  return sz;
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
int N;
char S[200000+2];
int R1;
int R2;
int W1;
int W2;
int totR;
int totW;
int main(){
  int i;
  int res = 1073709056;
  rd(N);
  rd(S);
  for(i=(0);i<(N);i++){
    if(S[i]=='R'){
      totR++;
    }
    else{
      totW++;
    }
  }
  for(i=(0);i<(N+1);i++){
    R2 = totR - R1;
    W2 = totW - W1;
    chmin(res, max_L(W1, R2));
    if(i < N){
      if(S[i]=='R'){
        R1++;
      }
      else{
        W1++;
      }
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200509-1

// --- original code ---
// int N;
// char S[2d5+2];
// int R1, R2, W1, W2;
// int totR, totW;
// {
//   int res = int_inf;
//   rd(N,S);
//   rep(i,N) if[S[i]=='R', totR++, totW++];
//   rep(i,N+1){
//     R2 = totR - R1;
//     W2 = totW - W1;
//     res <?= max(W1, R2);
// 
//     if(i < N) if[S[i]=='R', R1++, W1++];
//   }
//   wt(res);
// }


Measured memory_bytes: 4028
#include<bits/stdc++.h>
using namespace std;
typedef		 long long int    ll;
typedef		vector<ll>      vll;
#define     fi              first
#define     print(v)        for(ll i:v) cout<<i<<ss
#define     se              second
#define		pb              push_back
#define		nn              "\n"
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		ss              ' '
#define     pii             pair<ll,ll>
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
const double eps = 1e-8;


int main()
{
    ll mod=1e9+7;

    ll n,m;
    cin>>n>>m;
    string s[n+10];

    for(ll i=0; i<n; i++)
    {
        cin>>s[i];
    }
    ll dp[n][m];
    memset(dp,0,sizeof(dp));

    dp[n-1][m-1]=1;

    for(ll i=n-1; i>=0; i--)
    {
        for(ll j=m-1; j>=0; j--)
        {
            if(s[i][j]!='#')
            {
               // cout<<0;
                ll x=i,y=j-1;

                if(x>=0&&y>=0&&s[x][y]!='#')
                {
                    dp[x][y]+=dp[i][j];
                    dp[x][y]%=mod;

                }
                x=i-1,y=j;
                if(x>=0&&y>=0&&s[x][y]!='#')
                {
                    dp[x][y]+=dp[i][j];
                    dp[x][y]%=mod;

                }
            }
        }
    }


//    for(ll i=0; i<n; i++)
//    {
//        for(ll j=0; j<m; j++)
//        {
//            cout<<dp[i][j]<<ss;
//        }
//        cout<<nn;
//    }

    cout<<dp[0][0]<<nn;



}


/* Final check before submit :

1. array size or integer overflow,like uninitialised 0 index.

2. Think twice,code once.check all possible counter test case.

3. Be careful about corner case! n=1?k=1? something about 0?

4. avoid stupid mistake!complexity(t/m)?precision error?submit same code twice?

5. if got WA than remember that you are missing something common.
   *** Be confident!!! who knows? may be your one step back to AC ***
4. minus mod ans=(ans-k+mod)%mod;

*/






Measured memory_bytes: 13348
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vl vector<ll>
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll a;
  std::cin >> a;
  std::cout << a*a << '\n';
  return 0;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, K, L = map(int, input().split())
ufk = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    ufk.union(p, q)
ufl = UnionFind(N)
for _ in range(L):
    r, s = map(int, input().split())
    ufl.union(r, s)

d = {}
for i in range(1, N+1):
    k_par = ufk.find(i)
    l_par = ufl.find(i)
    d[(k_par, l_par)] = d.get((k_par, l_par), 0) + 1

ans = []
for i in range(1, N+1):
    ans.append(d[(ufk.find(i), ufl.find(i))])
print(*ans)


Measured memory_bytes: 55928
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		String N = sc.next();
		for(int i = 0; i < N.length(); i++) {
			if(N.substring(i, i + 1).equals("9")){
				System.out.println("Yes");
				return;
			}
		}
		System.out.println("No");
	}
}


Measured memory_bytes: 23252
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;

typedef long long int ll;
typedef pair<int,int> P;

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main()
{
	int n;
	cin>>n;
	vector<string> s(n);
	for (int i = 0; i < n; i++){
		cin>>s[i];
	}
	for (int i = 0; i < n; i++){
		sort(all(s[i]));
	}
	sort(all(s));
	// for(auto x : s){
	// 	cout<<x<<endl;
	// }
	ll ans = 0;
	ll cnt = 0;
	for (int i = 1; i < n; i++){
		if(s[i]==s[i-1]){
			if(cnt==0) cnt = 2;
			else cnt++;
		}else{
			ans += cnt*(cnt-1)/2;
			cnt = 0;
		}
	}
	ans += cnt*(cnt-1)/2;
	cout<<ans<<endl;
	
	return 0;
}

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

int main(){
    int h,w;
    cin >> h >> w;

    vector<vector<char>> a(h, vector<char>(w));

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> a.at(i).at(j);
        }
    }

    vector<bool> white_h(h,false),white_w(w,false);
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(a.at(i).at(j) == '#'){
                white_h.at(i) = true;
                break;
            }
        }
    }
    for(int j=0; j<w; j++){
        for(int i=0; i<h; i++){
            if(a.at(i).at(j) == '#'){
                white_w.at(j) = true;
                break;
            }
        }
    }

    for(int i=0; i<h; i++){
        if(white_h.at(i)){
            for(int j=0; j<w; j++){
                if(white_w.at(j)){
                    cout << a.at(i).at(j);
                }
            }
            cout << endl;
        }
    }
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

int main(int argc, char const *argv[]) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> path(n);
    int ans[n] = {-1}; // 距離を格納するリスト
    REP(i,n)
        ans[i] = -1;
    
    queue<int> que;
    
    REP(i,m) 
    {
        int a,b;
        cin >> a >> b;
        path[a-1].PB(b-1);
        path[b-1].PB(a-1);
    }
    que.push(0);

    // cout << endl;
    // REP(i,SIZE(path))
    // {   
    //     cout << i << " ";
    //     REP(j,SIZE(path[i]))
    //     {
    //         cout << path[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    ans[0] = 0;
    while (!que.empty())
    {
        int now = que.front(); //現在の場所
        que.pop();
        // cout << "here is top of roop" << endl;
        // cout << "que size" << que.size() << endl; 
        // cout << "now" << now  << endl;
        

        // if (que.size() > 100)
        //     break;

        REP(i,SIZE(path[now]))
        {
            int tmp = path[now][i];
            if (tmp == now) continue;
            if (ans[tmp] != -1)
                continue;
            else
            {
                ans[tmp] = now;
                que.push(tmp);
            }
            // 個々提出前に米
            // cout << "This is test " << now << " " << tmp << endl;
            // REP(i,n)
            //     cout << ans[i] << " ";
            // cout << endl;
        }
    }

    REP(i,n)
    {
        if (ans[i] == -1)
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    
    FOR(i,1,n-1)
        cout << ans[i]+1 << endl;

    return 0;
}


Measured memory_bytes: 10240
N, Y = [int(n) for n in input().split(' ')]

x = -1
y = -1
z = -1

for a in range(N+1):
    for b in range(N+1-a):
        c = N-a-b
        if (10000*a + 5000*b + 1000*c) == Y:
            x = a
            y = b
            z = c

print(x, y, z) 


Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector<int> v;
    string S, T;
    cin >> S >> T;
    rep(i, n) {
        if(S[i] == T[i]) v.push_back(1);
        else {
            v.push_back(2);
            i++;
        }
    }
    int ans = 1;
    rep(i, v.size()) {
        if(i == 0 && v[0] == 1) ans *= 3;
        else if(i == 0 && v[0] == 2) ans *= 6;
        else if (v[i - 1] == 2 && v[i] == 1) ans *= 1;
        else if (v[i - 1] == 2 && v[i] == 2) ans *= 3;
        else ans *= 2;
        ans %= mod;
    }
    // for(auto e: v) cout << e << " ";
    // cout << endl;
    cout << ans << endl;

    return 0;
}
// || 2
// ||
// --| 1
// --|
// |-- 2
// |--
// ----
// ----

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

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

int main(){
	int N ; cin>>N;
	vector<int> H(N);
	rep(i,N)cin>>H[i];
	bool ok = true;
	for(int i = N-1; i>0; --i){
		if(H[i-1]-H[i] > 1){ok = false; break;}
		if(H[i-1]-H[i] == 1)H[i-1]--;
	}
	cout<<((ok)?"Yes":"No")<<endl;
	return 0;
}

Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
typedef long long ll;


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, m; cin >> n >> m;
    int res = 0;
    if( n > 1){
        res += (n*(n-1))/2;
    }
    if(m > 1)
        res += (m*(m-1))/2;
        
    cout<<res<<endl;
    
    return 0;
}






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

using namespace std;
typedef long long ll;
typedef vector<ll> vl ;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

#define rep(i,N) for(int i=0; i < (int)N; i++)
#define all(v) (v).begin(),(v).end()

const int INF = 1001001001;

int main(){
	int n, k; cin >> n >> k;
	k--;
	vector<char> s(n); rep(i, n) cin >> s[i];
	s[k] = tolower(s[k]);
	rep(i,n) cout << s[i];
}

Measured memory_bytes: 256
import java.util.Scanner;

/**
 * Created by enpingkuang on 2020/9/19 7:53 下午
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long dp[] = new long[1000006];
        for(int i = 1;i<1000006;i++){
            for(int j = 1;j*i<1000006;j++){
                dp[j*i]++;
            }
        }
        long ans = 1;
        for (int i = 2; i < n; i++) {
            ans += dp[i];
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 43480
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define F first
#define S second
int a[200000];
int d[15];
signed main(){
    int n;
    bool ans=true;
    cin>>n;
    rep(i,n){
        cin>>a[i];
        rep(j,10){
            d[j]+=a[i]>>(j+1);
        }
    }
    rep(i,10){
        if(d[i]%2)ans=false;
    }
    if(ans)puts("Yes");
    else puts("No");
    return 0;
}


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

int main(){
  int n;
  cin >> n;
  int p[n], q[n], minV = 1000000, cnt = 0;
  for ( int i = 0; i < n; i++){
    cin >> p[i];
    minV = min(minV, p[i]);
    if(minV == p[i]){
      cnt++;
    }
  }

  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int a[N<<1],b[N<<1];
int s0[N<<1][N],s1[N<<1][N],f[N][N],pos1[N],pos0[N];
char s[555];
int main(){
	int n;
	scanf("%d",&n);
	for (int i=1;i<=2*n;i++){
		scanf("%s",s+1);
		scanf("%d",&a[i]);
		if (s[1]=='W') b[i]=0,pos0[a[i]]=i;
		else b[i]=1,pos1[a[i]]=i;
	}
	for (int i=1;i<=2*n;i++){
		for (int j=0;j<=n;j++){
			s0[i][j]=s0[i-1][j];
			s1[i][j]=s1[i-1][j];
			if (a[i-1]>j&&b[i-1]==0) s0[i][j]++;
			if (a[i-1]>j&&b[i-1]==1) s1[i][j]++;
		}
	}
	for (int i=0;i<=n;i++){
		for (int j=0;j<=n;j++){
			if (i==0&&j==0) continue;
			int p0=pos0[i],p1=pos1[j];
			f[i][j]=1e9;
			if (i) f[i][j]=min(f[i][j],f[i-1][j]+s0[p0][i-1]+s1[p0][j]);
			if (j) f[i][j]=min(f[i][j],f[i][j-1]+s0[p1][i]+s1[p1][j-1]);
		}
	}
	printf("%d\n",f[n][n]);
	return 0;
}

Measured memory_bytes: 78720
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, a, b) for(int i = (a); i <= (b); i++)
#define PER(i, a, b) for(int i = (a); i >= (b); i--)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define all(S) (S).begin(), (S).end()
#define pb push_back
#define mk make_pair
#define S second
#define F first
typedef long long ll;
typedef long double lf;
typedef pair<int, int> ii;
const int MAX =  2e5+5;

int main(int argc, char ** argv) {
	int d, t, s;
	scanf("%d%d%d", &d, &t, &s);
	if(s*t >= d) puts("Yes");
	else puts("No");
	return 0;
}


Measured memory_bytes: 3760
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
long long mod=1000000007;

int MIN(int A,int B){
    return A<B?A:B;
}

int MAX(int A,int B){
    return A>B?A:B;
}

int main(void){
    int h,w;
    scanf("%d%d",&h,&w);
    char s[h+2][w+2];
    for (int i=0; i<h; i++){
        scanf("%s\n",s[i]);
    }
    int a[h+2][w+2];
    int b[h+2][w+2];
    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            a[i][j]=-1;
            b[i][j]=-1;
        }
    }
    int count=0;
    for (int i=0; i<h; i++){
        count=0;
        for (int j=0; j<w; j++){
            if (s[i][j]=='.'){
                count++;
            } else if (s[i][j]=='#') {
                a[i][j-1]=count;
                count=0;
                a[i][j]=0;
            }
            if (j==w-1){
                a[i][j]=count;
            }
        }
    }
    for (int i=0; i<h; i++){
        for (int j=w-1; j>=0; j--){
            if (a[i][j]==-1){
                a[i][j]=a[i][j+1];
            }
        }
    }
    
    for (int i=0; i<w; i++){
        count=0;
        for (int j=0; j<h; j++){
            if (s[j][i]=='.'){
                count++;
            } else if (s[j][i]=='#') {
                b[j-1][i]=count;
                count=0;
                b[j][i]=0;
            }
            if (j==h-1){
                b[j][i]=count;
            }
        }
    }
    for (int i=0; i<w; i++){
        for (int j=h-1; j>=0; j--){
            if (b[j][i]==-1){
                b[j][i]=b[j+1][i];
            }
        }
    }
    int ans=0;
    for (int i=0; i<h; i++){
        for (int j=0; j<w; j++){
            ans=MAX(ans,a[i][j]+b[i][j]-1);
        }
    }
    printf("%d\n",ans);
    return 0 ;
}

Measured memory_bytes: 35328
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
using namespace std;
#define lint long long int
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
*/


int main() {
	int N, W;
	cin >> N >> W;
	vector<lint>w(N), v(N);
	for (int i =0 ; i < N; i++) {
		cin >> w[i] >> v[i];
	}
	vector<vector<lint>> dp(N + 1, vector<lint>(W + 1));
	for (int i = 0; i < N; i++) {
		for (int ws = 0; ws <= W; ws++) {
			if (ws >= w[i]) {
				dp[i + 1][ws] = max(dp[i][ws], dp[i][ws - w[i]] + v[i]);
			}
			else {
				dp[i + 1][ws] = dp[i][ws];
			}
		}
	}
	cout << dp[N][W] << endl;
}

Measured memory_bytes: 80256
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
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;}


int main() {
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int>nums;
    int cnt;
    if(s[0] != '1')nums.push_back(0);
    for(int i = 0;i<(int)s.size();i++) {
        cnt = 0;
        for(int j = i;j<(int)s.size();j++) {
            if(s[i] == s[j]) {
                i = j;
                cnt++;
            }
            else break;
        }
        nums.push_back(cnt);
        
    }
    
    vector<int>sum((int)nums.size()+1);
    rep(i,(int)nums.size()) {
        sum[i+1] = sum[i] + nums[i];
    }
    // rep(i,nums.size()) {
    //     cout << nums[i] << endl;
    // }
    // rep(i,sum.size()) {
    //     cout << sum[i] << endl;
    // }
    int ans = 0;
    for(int left = 0;left<(int)sum.size();left += 2) {
        int right = left+2*k+1;
        if(right>=(int)sum.size()) right = sum.size()-1;
        // cout << sum[right] << " " << sum[left] << endl;
        ans = max(ans,sum[right] - sum[left]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4376
#include<stdio.h>

int main(void)
{
   int a, b, x;

   scanf("%d%d",&a,&b);

   if(b!=1){
      x=(b-1)/(a-1);
      if((b-1)%(a-1)==0)
         printf("%d\n",x);
      else
         printf("%d\n",x+1);
   }
   else
      printf("0\n");
   return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<vector>
using namespace std;
int main() {
	int N;
	cin >> N;
	vector<int> B(N);
	vector<int> A(N , 0);
	for (int i = 0; i < N; i++) {
		cin >> B[i];
	}
	for (int i = 0; i < N / 2; i++) {
		A[0] += B[2 * i] - B[2 * i + 1];
	}
	A[0] += B[N - 1];
	for (int i = 1; i < N; i++) {
		A[i] = 2 * B[i - 1] - A[i - 1];
	}
	for (int i = 0; i < N; i++) {
		cout << A[i] << " ";
	}
	cout << endl;
	return 0;
}

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

int main() {
  string S;
  cin>>S;
  for(int i=0;i<S.size()-1;i++){
    if(S.at(i)=='A'&&S.at(i+1)=='C'){
      cout<<"Yes"<<endl;
      break;
    }
    else if(i==S.size()-2){
      cout<<"No"<<endl;
    }
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main(){
	int n,flag=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i-1]>a[i]){cout<<"No";return 0;}
		if(a[i-1]!=a[i])a[i]--;
	}
	cout<<"Yes";
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[9]={1,0,-1,0,1,1,-1,-1,0};
const ll dx[9]={0,-1,0,1,1,-1,1,-1,0};
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;
}

int main(){
    ll h,w,m;cin >> h >> w >> m;
    vl r(w),c(h);vpl it(m);
    rep(i,m){
        ll a,b;cin >> a >> b;a--;b--;
        it[i]={a,b};r[b]++;c[a]++;
    }
    vl rr(w),cc(h);
    ll ans=0,p=0,x=0,y=0;
    rep(i,w)chmax(ans,r[i]);
    rep(i,w)if(ans==r[i])rr[i]++,x++;
    rep(i,h)chmax(p,c[i]);
    rep(i,h)if(p==c[i])cc[i]++,y++;
    ll cnt=0;
    rep(i,m){
        if(rr[it[i].se]&&cc[it[i].fi])cnt++;
    }
    if(cnt==x*y)cout << ans+p-1 <<endl;
    else cout << ans+p <<endl;
} 

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

int main() {
  int a,b,c;
  cin>>a>>b>>c;
  if(a==7&&b==c&&b==5) {
    cout<<"YES"<<endl;
  }
  else if(b==7&&c==a&&c==5) {
    cout<<"YES"<<endl;
  }
  else if(c==7&&a==b&&a==5) {
    cout<<"YES"<<endl;
  }
  else {
    cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 256
const main = (input) => {
  const input = input.split("\n");
  const a = parseInt(input[0], 10);
  const b = parseInt(input[1], 10);
  const h = parseInt(input[2], 10);
  
  console.log((a+b)*h/2);
}
 
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    cin >> n;
    ll a[1000000];
    ll sum = 0;
    ll absmini = 1e10;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        sum += llabs(a[i]);
        absmini = min(absmini, llabs(a[i]));
    }
    for(int i = 0;i < n-1;i++){
        if(a[i] < 0)a[i] *= -1,a[i+1] *= -1;
    }
    if(a[n-1] < 0)sum -= 2 * absmini;
    cout << sum << endl;
}

Measured memory_bytes: 2816
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>qq;
const ll maxn=1e6+5;
int main()
{
    ll x,s=0;
    cin>>x;
    s+=x/500*1000;
    ll xx=x%500;
    s+=xx/5*5;
    cout<<s;
    return 0;
}
/*
10 6
8 3 7 8 2 9 3 8 2 4


20 20
*/


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define rep(i,l,n) for(i=l;i<n;i++)

int main(void){
	char s[101];
	char p[101];
	int i,j,ls,lp,a,m;
	
	scanf("%s",s);
	scanf("%s",p);
	
	ls=strlen(s);
	lp=strlen(p);
	
	a=0;
	
	rep(i,0,ls){
		if(a) break;
		rep(j,0,lp){
			m=i+j;
			if(m>=ls) m-=ls;
			if(s[m]!=p[j]) break;
			if(j==lp-1) a++;
			
		}
	}
	
	if(a) printf("Yes\n");
	else printf("No\n");
	
	return 0;
}



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

#define ll long long
#define ld long double
#define mod 1000000007LL
#define eps 1e-13
#define PI 3.141592653589793238L
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define endl '\n'
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mp make_pair
#define F first
#define S second
#define pb(x) push_back(x)
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define foi(i,a,n) for(i = (a); i <= (n); i++)
#define pd(x) cout<<x
#define sd(x) cin>>x
#define nl cout<<endl
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define sws ios_base::sync_with_stdio(false); cin.tie(0)
#define gcd __gcd
#define clr(x) memset(x,0,sizeof(x))
#define all(a) (a).begin(), (a).end()
#define foreach(i,a) for(__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define sz(a) (int)((a).size())
//int a[25]= { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };
//int dw[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
//int dw[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
//ll fibonacci[2][2] = {{0,1},{1,1}};
//ll identity[2][2] = {{1,0},{0,1}};
ll i,j,k;
ll n,a,b;

bool pos(vll h, ll x) {
	fo(i,0,n) {
		h[i] -= (b*x);
		if(h[i] < 0) h[i] = 0;
	}
	ll k = 0;
	fo(i,0,n) {
		k += ceil((double)h[i]/(double)(a-b));
	}
	return (k <= x);
}

int main() {
	cin>>n>>a>>b;
	vll h(n);
	fo(i,0,n) cin>>h[i];
	ll l = 0, r = mod;
	while((r-l) > 1) {
		ll m = ((l+r)/2);
		if(pos(h,m)) {
			r = m;
		}
		else {
			l = m+1;
		}
	}
	if(pos(h,l)) cout<<l<<endl;
	else cout<<r<<endl;
	return 0;
}

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

namespace ConsoleApplication1
{
    class SearchIsland
    {
        struct Position { internal int x, y; }

        readonly int[] moveX = new int[] { -1, 0, 1, 0 };
        readonly int[] moveY = new int[] { 0, -1, 0, 1 };

        int[,] map;

        public void MakeMap(string[] source)
        {
            map = new int[12, 12];

            for (int i = 0; i < 12; i++)
            {
                for (int j = 0; j < 12; j++)
                {
                    map[i, j] = int.Parse(source[i][j].ToString());
                }
            }
        }

        public int Count()
        {
            int count = 0;

            for (int i = 0; i < 12; i++)
            {
                for (int j = 0; j < 12; j++)
                {
                    if (map[i, j] == 1)
                    {
                        CheckIsland(i, j);
                        count++;
                    }
                }
            }
            return count;
        }

        private void CheckIsland(int i, int j)
        {
            Stack<Position> stk = new Stack<Position>();

            Position willPush;
            willPush.x = j;
            willPush.y = i;
            stk.Push(willPush);

            while (stk.Count > 0)
            {
                Position temp = stk.Pop();
                int posX = temp.x;
                int posY = temp.y;

                map[posY, posX] = 0;

                for (int n = 0; n < 4; n++)
                {
                    willPush.x = posX + moveX[n];
                    willPush.y = posY + moveY[n];

                    if (isValid(willPush.x, willPush.y))
                    {
                        if (map[willPush.y, willPush.x] == 1)
                        {
                            stk.Push(willPush);
                        }
                    }
                }
            }
        }

        private bool isValid(int x, int y)
        {
            if (x < 0 || x > 11) return false;
            if (y < 0 || y > 11) return false;
            return true;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            SearchIsland SI = new SearchIsland();

            string input;

            while (!string.IsNullOrEmpty(input = Console.ReadLine()))
            {
                string[] map = new string[12];
                map[0] = input;

                for (int i = 1; i < 12; i++)
                {
                    map[i] = Console.ReadLine();
                }

                SI.MakeMap(map);

                sb.AppendLine(SI.Count().ToString());

                Console.ReadLine();
            }
            Console.Write(sb);
        }
    }
}

Measured memory_bytes: 9984
h,w = gets.split.map(&:to_i)
a = (1..h).map{gets.split.map(&:to_i)}
b = (1..h).map{gets.split.map(&:to_i)}
ab = a.zip(b).map{|ta,tb|ta.zip(tb).map{|ua,ub|(ua-ub).abs}}

max = ab.map(&:max).max
zero = 1 << (h+w)*max/2

dp = (1..h).map{(1..w).map{nil}+[0]}+[(1..w).map{0}]

dp[0][-1] = dp[-1][0] = zero

(0...h).each{|th|
  abth = ab[th]
  dpth = dp[th]
  dpth1 = dp[th-1]
  (0...w).each{|tw|
    d = abth[tw]
    s = dpth1[tw] | dpth[tw-1]
    dst = (s << d) | (s >> d) 
    dpth[tw] = dst
  }
}
ans = dp[h-1][w-1]
p (0..max).find{|i|
  ans & (zero << i) > 0 ||
  ans & (zero >> i) > 0
}

Measured memory_bytes: 24316
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define co(n) cout<<n<<endl
#define all(n) (n).begin(),(n).end()
#define pb(n,m) n.push_back(m)
#define pi(n,m) n.insert(n.begin(),m);
#define ee(n) n.erase(n.end()-1)
#define eb(n) n.erase(n.begin())
#define check(n) reverse(all(n));rep(z,0,n.size())cout<<n[z];co("");reverse(all(n));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(){
  ll n,m,q,ans=0,x=0;
  cin>>n>>m>>q;
  ll a[q],b[q],c[q],d[q];
  rep(i,0,q) cin>>a[i]>>b[i]>>c[i]>>d[i];
  vector<int> z={};
  rep(i,0,n) pb(z,1);
  if(m==1){
    rep(i,0,q){
      if(z[b[i]-1]-z[a[i]-1]==c[i]) x+=d[i];
    }
    ans=max(x,ans);
    x=0;
    co(ans);
    return 0;
  }
  while(z[0]!=m){
    rep(i,0,q){
      if(z[b[i]-1]-z[a[i]-1]==c[i]) x+=d[i];
    }
    ans=max(x,ans);
    x=0;
    if(z[n-1]<m) z[n-1]++;
    else{
      rep(i,1,n){
        if(z[i]==m){
          z[i-1]++;
          if(z[i-1]!=m) rep(j,i,n) z[j]=z[i-1];
          break;
        }
      }
    }
  }
  co(ans);
    
  return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef long double ld;
const int maxn=25e6+10;

inline char gc(){
	return getchar();
	static const int maxs=1<<16;static char buf[maxs],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
    ll x=0;char c=gc();bool neg=0;
    while(c<'0'||c>'9'){if(c=='-') neg=1;c=gc();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=gc();
    return neg?(~x+1):x;
}

int N,a[2][3];
ll f[maxn];

int main(){
    //freopen("","r",stdin);
    N=rd();
    for(int i=0;i<=1;i++) for(int j=0;j<=2;j++) a[i][j]=rd();
    for(int i=1;i<=N;i++){
    	f[i]=f[i-1]+1;
    	for(int j=0;j<=2;j++){
    		if(i>=a[0][j]) f[i]=max(f[i],f[i-a[0][j]]+a[1][j]);
    	}
    }
    int now=f[N];
    CLR(f,0);
    for(int i=1;i<=now;i++){
    	f[i]=f[i-1]+1;
    	for(int j=0;j<=2;j++){
    		if(i>=a[1][j]) f[i]=max(f[i],f[i-a[1][j]]+a[0][j]);
    	}
    }
    printf("%lld\n",f[now]);
    return 0;
}

Measured memory_bytes: 195712
using System;
using System.Linq;
using static System.Math;

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            var ab = Console.ReadLine().Split().Select(int.Parse).ToArray();

            Console.WriteLine(Max(ab.Max() * 2 - 1, ab.Sum()));

        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    ll n;
    cin >>n;
    ll a[n];
    rep(i,n)cin>>a[i];
    ll res=0;
    rep(i,n)res+=a[i];
    for(int i=1;i<n-1;i+=2)res-=2*a[i]; 
    cout << res << " ";
    for(int i=1;i<n;i++){
        res = 2*a[i-1]-res;
        cout << res;
        if(i!=n-1)cout << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 2048
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 != 0 and a[i] % 5 != 0:
            print('DENIED')
            break
else:
    print('APPROVED')

Measured memory_bytes: 3060