akhauriyash/Code-Regression huggingface dataset:
#ABC157-E Simple String Queries
"""
英小文字26字が含まれるか否かを、2**26のint型で管理するセグ木。
これをbitwise-segment treeと言うらしい。
解法：
葉はその英小文字のbitで管理する。
segfuncにはx|yを登録することで、区間クエリをとった時に
2進数表記で1が出てくる回数が答えになる。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#input
n = int(readline())
s = readline().rstrip().decode('utf-8')
lst1 = [0]*n
kijun = ord("a")
for i in range(n):
    res = ord(s[i])-kijun
    lst1[i] = 1<<res #A:1,B:10,C:100,D:1000

#####segfunc######
def segfunc(x,y):
    return x|y

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0　(上の単位元の説明を参照)
　　積のセグ木 → 1　(上の単位元の説明を参照)
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num #単位元の配列(計算結果に影響を及ぼさない配列)を作成

init(lst1)

#query
q = int(readline())
for i in range(q):
    kind,a,b = readline().rstrip().decode('utf-8').split()

    if kind == "1": #a文字目をbに変更
        res = ord(b)-kijun
        update(int(a)-1,1<<res)

    else: #[a,b]の区間に含まれる文字の種類を出力
        ans = 0
        a,b = int(a)-1,int(b)-1
        res = query(a,b+1)
        for i in range(26):
            if res >> i &1:
                ans += 1
        print(ans)

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

int main() {
        ll int n;
         cin>>n;
         string s=to_string(n);
         int l=s.length();
         int k=pow(10,l-1);
         int y=n%10;
         if(y==2 || y==4 || y==5 || y==7 || y==9)
         {
             cout<<"hon"<<endl;
         }
         else if(y==3)
         {
             cout<<"bon"<<endl;
         }
         else
         {
             cout<<"pon"<<endl;
         }
}

Measured memory_bytes: 3736
#include <stdio.h>

int main(){
   long a,b,c,k,ans;

   scanf("%ld %ld %ld %ld",&a,&b,&c,&k);
   if (k>a) {
      ans=a;
      k-=a;
   } else {
      printf("%ld\n",k);
      return 0;
   }
   if (k>b)
      k-=b;
   else {
      printf("%ld\n",ans);
      return 0;
   }
   if (k>c) printf("%ld\n",ans-c);
   else     printf("%ld\n",ans-k);
   return 0;
}


Measured memory_bytes: 1732
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30);
const int INF = (1LL << 60);
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; }



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    int n;
    cin>>n;
    char s[n][n];
    rep(i,n) rep(j,n) cin>>s[i][j];
    ll ans=0;
    rep(_,n){// idou
        int ng=0;
        rep(i,n){
            rep(j,n){
                if(s[i][j]!=s[j][i]) ng++;
            }
        }
        if(ng==0) ans++;
        char y[n];
        rep(i,n) y[i]=s[0][i];
        rep(i,n-1) rep(j,n) s[i][j]=s[i+1][j];
        rep(i,n) s[n-1][i]=y[i];
    }
    cout<<ans*n<<endl;
    
}

Measured memory_bytes: 384
#coding: utf-8
A, B, C = map(int,input().split())
SORT = sorted([A,B,C])
t = 0

def doubleplus(x,y):
    return x+1, y+1
def oneplus(x):
    return x+2
while SORT[1] != SORT[2]:
    t += 1
    SORT[0], SORT[1] = doubleplus(SORT[0], SORT[1])
if (SORT[2]-SORT[0])%2 == 0:
    while SORT[0] != SORT[2]:
        t+=1
        SORT[0] =oneplus(SORT[0])
else:
    t +=2
    SORT[0], SORT[1] = doubleplus(SORT[0], SORT[1])
    SORT[0], SORT[2] = doubleplus(SORT[0], SORT[2])
    while SORT[0] != SORT[2]:
        t+=1
        SORT[0] =oneplus(SORT[0])


print(t)


Measured memory_bytes: 3064
tmp = input().split()
x = int(tmp[0])
n = int(tmp[1])

if(n == 0):
    print(x)
else:
    p_str_list = input().split()
    p_int_list = [int(x) for x in p_str_list]

    flg = True
    abs_count = 0
    answer = 0
    while(flg):
        search_n_minus = x - abs_count
        search_n_plus = x + abs_count
        if(search_n_minus in p_int_list):
            if(search_n_plus in p_int_list):
                abs_count += 1
            else:
                answer = search_n_plus
                break
        else:
            answer = search_n_minus
            break
    print(answer)

Measured memory_bytes: 9128
h, w, n = map(int, input().split())
a = {tuple(map(int, input().split())) for _ in range(n)}

d = {}
c = [0] * 10

def next(x, y):
    ret = []
    for i in range(max(0, x-2), min(h-2, x+1)):
        for j in range(max(0, y-2), min(w-2, y+1)):
            ret.append((i, j))
    return ret

for x, y in a:
    x -= 1
    y -= 1
    for s, t in next(x, y):
        if (s, t) not in d:
            count = 0
            for i in range(3):
                for j in range(3):
                    if (s + i + 1, t + j + 1) in a:
                        count += 1
            d[(s, t)] = count
            c[count] += 1

c[0] = (h-2) * (w-2) - sum(c)

for x in c:
    print(x)

Measured memory_bytes: 155252
def main(): 
    h,w = map(int,input().split())

    if w==1 or h==1:
        print(1)
        return

    if w%2==0:
        print(int(h*w/2))
    else:
        if h%2==0:
            print(int((w//2+1)*(h/2) + (w//2)*(h/2)))
        else:
            print(int((w//2+1)*(h//2+1) + (w//2)*(h//2)))

main()

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
long long int mul(long long int ans, long long int x, long long int y){
    while (y)
	{
        if (y%2)
		{
            ans = (ans * x) % MOD;
        }
        x = (x * x) % MOD;
        y >>= 1;
    }
    return ans;
}
long long int inv(long long int n)
{
    return mul(1, n, MOD-2);
}
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++)
	{
        cin >> a[i];
    }
    vector<int> prime(1000000, 0);
    for (int i=0; i<n; i++)
	{
        int m = a[i];
        int count = 0;
        while (m%2 == 0)
		{
            m /= 2;
            count++;
        }
        prime[2] = max(prime[2], count);
        for (int j=3; j*j<=m; j+=2)
		{
            count = 0;
            while (m%j == 0)
			{
                m /= j;
                count++;
            }
            prime[j] = max(prime[j], count);
        }
        prime[m] = max(prime[m], 1);
    }
 
    long long int lcm = 1;
    for (int i=2; i<prime.size(); i++)
	{
        if (prime[i] != 0)  lcm = mul(lcm, i, prime[i]);
    }
    long long int ans = 0;
    for (int i=0; i<n; i++)
	{
        long long m = a[i], _ans = lcm;
        int count = 0;
        while (m%2 == 0)
		{
            m /= 2;
            count++;
        }
        _ans = mul(_ans, inv(2), count);
        for (int j=3; j*j<=m; j+=2)
		{
            count = 0;
            while (m%j == 0)
			{
                m /= j;
                count++;
            }
            if (count != 0)  _ans = mul(_ans, inv(j), count);
        }
        _ans = mul(_ans, inv(m), 1);
        ans += _ans;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

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


    class Program
    {
        static void Main(string[] args)
        {
            string[] Input = Console.ReadLine().Split(' ');
            Console.WriteLine(int.Parse(Input[0]) * int.Parse(Input[1]));
        }
    }



Measured memory_bytes: 17896
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int h = 0;
      int w = 0;
      int k = 0;
     
      cin >> h;
      cin >> w;
      cin >> k;
      vector<vector<char>> table(h, vector<char>(w));
     
      int hh = 0;
      int ww = 0;
      while (true) {
        char c = 0;
        cin >> c;
        if (c == '\n') {
          continue;
        }
        table[hh][ww] = c;
        if (hh == h - 1 && ww == w - 1) {
          break;
        } else if (ww == w - 1) {
          hh++;
          ww = 0;
        } else {
          ww++;
        }
      }
     
      int result = 0;
      uint64_t max_h = (1 << h) - 1;
      uint64_t max_w = (1 << w) - 1;
      for (uint64_t deletedh = 0; deletedh <= max_h; deletedh++) {
        for (uint64_t deletedw = 0; deletedw <= max_w; deletedw++) {
          vector<uint8_t> deleted_h(h);
          vector<uint8_t> deleted_w(w);
          for (int i = 0; i < h; i++) {
            if (deletedh & (1 << i)) {
              deleted_h[i] = 1;
            } else {
              deleted_h[i] = 0;
            }
          }
          for (int j = 0; j < w; j++) {
            if (deletedw & (1 << j)) {
              deleted_w[j] = 1;
            } else {
              deleted_w[j] = 0;
            }
          }
     
          int count = 0;
          for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
              if (!deleted_h[i] && !deleted_w[j] && table[i][j] == '#') {
                count++;
              }
            }
          }
          if (count == k) {
            result++;
          }
        }
      }
      cout << result << endl;
    }

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

using namespace std;

typedef long long ll;
const int mx = 1e5+12;
ll dp[123][mx],n,weight[mx];
ll value[mx],totalSize;

ll solve(ll i,ll w){

if(i>n) return 0;
    
if(dp[i][w]!=-1) return dp[i][w];
    
ll ret1=0,ret2=0;

if(w+weight[i]<=totalSize)
ret1=value[i]+solve(i+1,w+weight[i]);
 
 ret2=solve(i+1,w);
    
 
 dp[i][w]=max(ret1,ret2);

return dp[i][w];

}

int main(){

cin>>n>>totalSize;

for(int i=1;i<=n;i++){
    cin>>weight[i]>>value[i];
}
memset(dp,-1,sizeof(dp));
cout<<solve(1,0)<<endl;

return 0;
}


Measured memory_bytes: 99756
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

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

const int INF = 1e9;
const long long LINF = 1e18;

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

    long long s = sqrt(N);
    while (N % s != 0) {
        s--;
    }
    long long r = N / s;
    cout << (s - 1) + (r - 1) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	string s;
	int ans=700;
	cin>>s;
	rep(i,3)if(s.at(i)=='o')ans+=100;
	cout<<ans<<endl;
}


Measured memory_bytes: 256
require 'pp'

# 空白区切の入力値を数値の配列で返却する
def gets_i_list()
  gets.chomp.split(" ").map(&:to_i)
end

N, W = gets_i_list
wv_list = []
N.times do
  wv_list.push gets_i_list
end

# 最大容量以下で、容量ごとの価値の最大値を格納する
dp = Array.new(W + 1, 0)

wv_list.each do |w, v|
  # 許容できる容量(wからW)の範囲の価値を更新する
  # uptoを使うと、ループで更新した値を参照してしまうため、downtoを使う
  W.downto(w) do |i|
    # 現在の値(dp[i])より、　itemを追加した場合の価値(dp[i - w] + v)が大きければ更新する
    if dp[i] < dp[i - w] + v
      dp[i] = dp[i - w] + v 
    end
  end
end
puts dp.max

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

using namespace std;

using ll = long long;
using dd = double;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<dd, dd>;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<dd>;
using vb = vector<bool>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;

template <class T, class V>
istream& operator>>(istream& in, pair<T, V>& pair) {
    return in >> pair.first >> pair.second;
}

template <class T>
istream& operator>>(istream& in, vector<T>& elements) {
    for (size_t i = 0; i < elements.size(); ++i) {
        in >> elements[i];
    }
    return in;
}

template <class Container, class Element>
bool Contains(const Container& container, const Element& element) {
    return container.find(element) != container.end();
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& elements) {
    for (const T& element : elements) {
        out << element << ' ';
    }
    return out;
}

template <class T, class V>
ostream& operator<<(ostream& out, const pair<T, V>& pair) {
    return out << pair.first << ' ' << pair.second;
}

#define FOR(i,n) for(size_t i=0, i##_len=(n); i<i##_len; ++i)
#define SORT(c) sort((c).begin(), (c).end())
#define SUM(c) accumulate((c).begin(), (c).end(), 0ll)

int main() {
    ios_base::sync_with_stdio(false);
    
    int a;
    string s;
    cin >> a >> s;
    
    if (a < 3200) {
        cout << "red" << endl;
    } else {
        cout << s << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define int long long
#define S second
#define pb push_back
#define Init ios::sync_with_stdio(0);

const int MX = 1000*1000+100,inf = 0x7FFFFFFF,mod=1e9+7;
using namespace std;
int n;
int inp[MX];
stack<int>stk;
struct inx{
    int r, l;
}pos[MX];
int32_t main(){
    Init
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>inp[i];
    }
    for(int i=0;i<n;i++){
        while(!stk.empty() && inp[stk.top()]>=inp[i]){
            stk.pop();
        }
        if(stk.empty()){
            pos[i].l = 0;
        }else{
            pos[i].l = stk.top()+1;
        }
        stk.push(i);
    }
    while(!stk.empty()){
        stk.pop();
    }
    for(int i=n-1;i>=0;i--){
        while(!stk.empty() && inp[stk.top()]>=inp[i]){
            stk.pop();
        }
        if(stk.empty()){
            pos[i].r = n;
        }else{
            pos[i].r = stk.top();
        }
        stk.push(i);
    }
    int sum=0;
    for(int i=0;i<n;i++){
        int dis[2] = {(i+1)-pos[i].l, pos[i].r-(i)};
        int x =((dis[0]*dis[1]));
        sum+=(x*inp[i]);
        //cout<<i<<' '<<pos[i].r<<' '<<pos[i].l<<' '<<abs(pos[i].r-pos[i].l)*inp[i]<<endl;
    }
    cout<<sum<<endl;
}


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

typedef long long int ll;

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    
    int a, b;
    cin >> a >> b;
    
    int sum = a + b;
    if (sum % 2)
        cout << "IMPOSSIBLE\n";
    else
        cout << sum / 2 << "\n";

    return 0;
}


Measured memory_bytes: 256
N, A, B = map(int, input().split())
S = input()

cnt_a, cnt_b = 0, 0
for i in range(N):
  if S[i] == 'a' and cnt_a + cnt_b < A+B:
    print("Yes")
    cnt_a += 1
  elif S[i] == 'b' and cnt_a + cnt_b < A+B and cnt_b < B:
    print("Yes")
    cnt_b += 1
  else:
    print("No")
    

Measured memory_bytes: 4016
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <map>
#include <queue>
#include <set>

using namespace std;

typedef unsigned long long int ULL;
typedef long long LL;
typedef long double LD;

const LL inf = 1000000000000000;
const LL mod = 1000000007;

int main()
{
	LL a, b, x;
	cin >> a >> b >> x;

	LD X = x, A = a, B = b;
	LD H = (X)/(A*A);

	if (H >= B/2) {

		cout << fixed << setprecision(10) << atan(((B-H)*2)/A)*(180.0)/(3.141592653589793238) << endl;
	}
	else {
		cout << fixed << setprecision(10) << atan((A*B*B)/(2*X))*(180.0)/(3.141592653589793238) << endl;
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
typedef long long ll;
#define all(x) (x).begin(), (x).end()  // sortなどの引数を省略
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define max3(x, y, z) max(x, max(y, z))

#ifdef _MSC_FULL_VER  //デバッグ出力
#define dout cout
#define debug() if (true)
#define check(x) std::cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) std::cout << "☆" << x << endl
#else
#define dout \
  if (false) cout
#define debug() if (false)
#define check(x) \
  if (false) cout << "★" << #x << "の値:" << (x) << endl
#define pass(x) \
  if (false) cout << "☆" << x << endl
#endif
using namespace std;
int main() {
  int a,b;
  cin >> a >> b;

  b+=a*3;
  cout << b/2;
  return 0;
}
/*
//よく使うやつ
int N;
cin >> N;
vector<int> list(N);
for (int i = 0; i < N; i++) {
cin >> list[i];
}
// for文
for (int i = 0; i < N; i++) {
}
//配列
vector<int> list;
list.at(i)
vector<vector<int>> list(10, vector<int>(10));
sort(all(list));
sort(all(list), greater<int>());
  //配列の内容表示
dout << "====listの内容====\n";
for (int i = 0; i < N; i++) dout << list[i] << endl;
dout << "====ここまで====\n";
*/


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

#ifndef __TOPCYBERFLOWER
#define debug(...) 0
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif

#define TYPEMAX(type)   numeric_limits<type>::max()
#define TYPEMIN(type)   numeric_limits<type>::min()
typedef long long ll;
typedef pair<int,int> pii;

int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,r; cin>>n>>r;
    if(n<=10) cout<<r+100*(10-n);
    else cout<<r;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>

int main() {
	int h, w, k, count = 0;
	scanf("%d%d%d", &h, &w, &k);
	char grid[6][6];
	for (int i = 0; i < h; ++i)
		for (int j = 0; j < w; ++j)
			scanf(" %c", &grid[i][j]);
	for (int rows = 0; rows < 1 << h; ++rows) {
		for (int col = 0; col < 1 << w; ++col) {
			int bks = 0;
			for (int i = 0; i < h; ++i)
				for (int j = 0; j < w; ++j)
					if ((rows >> i) & 1 == 1 && (col >> j) & 1 == 1)
						bks += grid[i][j] == '#';
			if (bks == k) count++;
		}
	}
	printf("%d\n", count);
}


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

int main ()
{
	while (true) {
		std::string buf;
		std::cin >> buf;
		if (buf == "0") break;
		
		int sum = 0;
		for (std::string::iterator it = buf.begin(); it != buf.end(); ++it) {
			sum += (*it) - 48;
		}
		std::cout << sum << std::endl;
	}
	
	return 0;
}




Measured memory_bytes: 3180
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
typedef pair<int, int> P;
constexpr double PI = 3.1415926535897932;   // acos(-1)
constexpr double EPS = 1e-9;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

struct UnionFind{
    int sz;     // vertex number
    vector<int> par;
    vector<int> rank;

    UnionFind(int n) : sz(n) {
        par.resize(sz);
        rank.assign(sz, 0);
        for(int i = 0; i < sz; ++i){
            par[i] = i;
        }
    }

    int find(int x){
        if(par[x] == x) return x;
        else    return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void unite(int x, int y){
        x = find(x), y = find(y);
        if(x == y)  return;
        if(rank[x] < rank[y])   par[x] = y;
        else{
            par[y] = x;
            if(rank[x] == rank[y])  ++rank[x];
        }
    }
};

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

    int n, m;
    cin >> n >> m;
    UnionFind uf(m);
    vector<vector<int>> l(n);
    for(int i = 0; i < n; ++i){
        int k;
        cin >> k;
        l[i].resize(k);
        for(int j = 0; j < k; ++j){
            cin >> l[i][j];
            --l[i][j];
            if(j > 0)   uf.unite(l[i][0], l[i][j]);
        }
    }
    
    bool ok = true;
    int group = uf.find(l[0][0]);
    for(int i = 1; i < n; ++i){
        if(uf.find(l[i][0]) != group){
            ok = false;
            break;
        }
    }

    if(ok)  cout << "YES\n";
    else    cout << "NO\n";
}

Measured memory_bytes: 6528
#include <stdio.h>
 
char str[1005];
char p[1005];
 
int main()
{
    int q, a, b;
    char op[10], *x, *y, c;
     
    scanf("%s%d", str, &q);
    while (q--) {
        scanf("%s%d%d", op, &a, &b);
        if (op[2] == 'i') {            
            b++, c = *(str+b), *(str+b) = 0, puts(str+a), *(str+b) = c;
        } else if (op[2] == 'v') {      
            x = str+a, y = str+b;
            while (x < y) {
                c = *x, *x = *y, *y = c;
                x++, y--;
            }
        } else {                       
            scanf("%s", p);
            x = str+a, y = p;
            while (*y) *x++ = *y++;
        }
    }
    return 0;
}


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

#define rep(i, n) for(int i=0; i < (n); ++i)
#define ll long long

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};
double expect(int k) {
    return (double) (k + 1) / 2;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, K; cin >> N >> K;
    vector<int> P(N); rep(i, N) cin >> P[i];
    vector<double> E(N);
    rep(i, N) E[i] = expect(P[i]);

    double ans = 0;
    double temp = 0;
    rep(i, K) temp += E[i];
    int i = K;
    chmax(ans, temp);
    while (i < N) {
        temp -= E[i - K];
        temp += E[i];
        chmax(ans, temp);
        i++;
    }
    printf("%.12f\n", ans);
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
typedef long long ll;

using namespace std;

int main(){

	string a,b;
	cin>>a>>b;
	int c=stoi(a+b);
	REP(i,1001){
		if(i*i==c){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;

    return 0;
}

Measured memory_bytes: 3616
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
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;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
int main() {
	long long int n;
	cin >> n;
	string s;
	if (n > 0) {
		long long int ni = 1;
		while (n != 0) {
			if (n % 2 == 1) {
				if (ni > 0) {
					s = s + to_string(1);
				}
				else {
					s = s + to_string(1);
					n = n + 1;
				}
			}
			else if (n % 2 == -1) {
				if (ni < 0) {
					s = s + to_string(1);
				}
				else {
					s = s + to_string(1);
					n = n + 1;
				}
			}
			else {
				s = s + to_string(0);
			}
			ni = ni * -2;
			n = n / 2;
		}
	}
	else if(n < 0) {
		long long int ni = 1;
		while (n != 0) {
			if (n % 2 == 1) {
				if (ni > 0) {
					s = s + to_string(1);
				}
				else {
					s = s + to_string(1);
					n = n - 1;
				}
			}
			else if (n % 2 == -1) {
				if (ni < 0) {
					s = s + to_string(1);
				}
				else {
					s = s + to_string(1);
					n = n - 1;
				}
			}
			else {
				s = s + to_string(0);
			}
			ni = ni * -2;
			n = n / 2;
		}
	}
	else {
		cout << 0;
		return 0;
	}
	reverse(s.begin(), s.end());
	cout << s;
}

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

int main(){
  string S;
  cin>>S;
  ll ss = S.size();
  ll mod = 2019;

  vector<int> sum(ss+1,0);

  ll d = 1;
  for(ll i = ss-1; i>=0; i--){
    ll a = (S[i]-'0')*d % mod;
    sum[i] = (sum[i+1] + a) % mod;
    d = 10*d %mod ;
    sum[i] %= mod;
  }

  ll ans = 0;
  vector<int> cou(2019,0);
  for(ll i=ss; i>=0;i--){
    ans+= cou[sum[i]];
    cou[sum[i]]++;

  }
  cout<< ans;
}


Measured memory_bytes: 4380
#include<bits/stdc++.h>
#define int long long
#define M 998244353
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define Zero(dp) memset(dp,0,sizeof(dp))
#define pb push_back
using namespace std;
int fast_power(int base,int power,int modulo)
{
	int result=1;
	while(power)
	{
		if(power%2)
		result=(result*base)%modulo;
		base=(base*base)%modulo;
		power/=2;
	}
	return result;
}
int inverse(int base,int modulo)
{
	return fast_power(base,modulo-2,modulo);
}
int32_t main(){
ios
int t=1;
//cin>>t;
while(t--)
{		

	int n;cin>>n;
	map<string,int> m;
	int mx=0;
	for(int i=0;i<n;i++)
	{
		string s;cin>>s;
		m[s]++;
		if(m[s]>mx)mx=m[s];
	}
	for(auto i:m)
	{
		if(i.second==mx)
			cout<<i.first<<'\n';
	}
}
}


Measured memory_bytes: 23808
import java.util.Scanner;
import java.util.Arrays;
 
public class Main{
  public static void main(String[] args){
    String[] input=(new Scanner(System.in)).nextLine().split(" ");
    String[] evenArray=new String[]{"0","2","4","6","8"};
    boolean result=Arrays.asList(evenArray).contains(input[0].substring(input[0].length()-1));
    result=result||Arrays.asList(evenArray).contains(input[1].substring(input[1].length()-1));
    String output=result?"Even":"Odd";
    System.out.println(output);
  }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
int main() {
    int r, g, b, k;
    cin >> r >> g >> b >> k;
    int cnt = 0;
    while(r >= g) {
        cnt++;
        g *= 2;
    }
    while(g >= b) {
        cnt++;
        b *= 2;
    }
    if(cnt <= k) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();
		N = N % 10;

		if (N == 3) {
			System.out.println("bon");
		}else if(N == 0 || N == 1 || N == 6 || N == 8) {
			System.out.println("pon");
		}else {
			System.out.println("hon");
		}
	}
}


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

int main(){
  ll n,t;
  cin >> n;
  vector<ll> a(n);
  priority_queue<ll> pq;
  rep(i,n){
    cin >> a[i];
    pq.push(a[i]);
  }
  rep(i,n){
    if(a[i]==pq.top()){
      pq.pop();
      cout << pq.top() << endl;
      pq.push(a[i]);
    }else{
      cout << pq.top() << endl;
    }
  }
}

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

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<int> > s(M);

    for (int i = 0; i < M; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int number_switch = 0;
            cin >> number_switch;
            number_switch--;
            s[i].push_back(number_switch);

        }
       
    }
    vector<int> p(M);
    for (int i = 0; i < M; i++) {
        cin >> p[i];
    }

    int ans = 0;
    for (int bit = 0; bit < (1 << N); bit++) {
        bool on = true;
        for (int i = 0; i < M; i++) {
            int number_on = 0;
            for (auto v : s[i]) {
                if (bit & (1 << v)) number_on++;
            }
            if (number_on % 2 != p[i]) {
                on = false;
            }
        }
        if (on) ans++;
    }
    cout << ans;
} 


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <functional>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define SQ(x) ((x)*(x))
#define Mod(x, mod) (((x)+(mod)%(mod))
#define MP make_pair
#define PB push_back
#define Fi first
#define Se second
#define INF (1<<29)
#define EPS 1e-10
#define MOD 1000000007

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

struct Edge{
  int u,v; double cost;
  Edge(){}
  Edge(int u, int v, double cost):u(u),v(v),cost(cost){}
  bool operator<(const Edge &a)const{
    return cost < a.cost;
  }
};

struct UnionFind{
  int par[10005];
  int rank[10005];
  UnionFind(int n){ init(n); }
  void init(int n){
    for(int i=0;i<n;i++){
      par[i] = i;
      rank[i] = 0;
    }
  }
  int find(int x){
    if(x == par[x]) return x;
    return par[x] = find(par[x]);
  }
  int same(int x, int y){
    return find(x) == find(y);
  }
  void unite(int x, int y){
    x = find(x); y = find(y);
    if(x==y) return;
    if(rank[x] < rank[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if(rank[x] == rank[y]) rank[x]++;
    }
  }
};

Edge es[50000000];
int N,M;
int x[10005],y[10005];

double kruskal(){
  UnionFind uf(N);
  double res = 0;
  sort(es, es+M);
  for(int i=0;i<M;i++){
    Edge e = es[i];
    if(!uf.same(e.u, e.v)){
      uf.unite(e.u, e.v);
      res += e.cost;
    }
  }
  return res;
}
  
int main(){
  double sum = 0.0;
  scanf("%d%d",&N,&M);
  rep(i,N) scanf("%d%d", &x[i],&y[i]);
  rep(i,M){
    int p,q;
    scanf("%d%d",&p,&q); p--; q--;
    double d = sqrt(SQ(x[p]-x[q])+SQ(y[p]-y[q]));
    es[i] = Edge(p,q, -d);
    sum += d;
  }
  printf("%lf\n", sum+kruskal());
  return 0;
}

Measured memory_bytes: 1828
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}

int main(){
  int n;
  cin >> n;
  if(n == 1){
    cout << "Hello World" << endl;
  }else{
    int a,b;
    cin >> a >> b;
    cout << a+b << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline void chmin(int& a, int b) { a = min(a, b); }
   
const int INF = INT_MAX;
const int MAX_N  = 1000000;
const int BACKET = 500;
   
    
int main()
{
  int N, Q;
  int A[MAX_N];
  int small[MAX_N / BACKET + 1];
  char s[32];
   
  fill_n(A, MAX_N, INF);
  fill_n(small, MAX_N / BACKET + 1, INF);
   
  fgets(s, sizeof(s), stdin);
  sscanf(s, "%d %d", &N, &Q);
     
  while(Q--) {
    int t, a, b;
    fgets(s, sizeof(s), stdin);
    sscanf(s, "%d %d %d", &t, &a, &b);
    if(t == 0) {
      int curr = a / BACKET;
      A[a] = b;
      small[curr] = INF;
      for(int i = 0; i < BACKET; i++) chmin(small[curr], A[curr * BACKET + i]);
    } else {
      int begin = (a + BACKET - 1) / BACKET;
      int end   = b / BACKET;
      int ret = INF;
      if(begin >= end) {
        for(int i = a; i <= b; i++) chmin(ret, A[i]);
      } else {
        for(int i = begin * BACKET - 1; i >= a; i--) chmin(ret, A[i]);
        for(int i = begin; i < end; i++) chmin(ret, small[i]);
        for(int i = end * BACKET; i <= b; i++) chmin(ret, A[i]); 
      }
      printf("%d\n", ret);
    }
  }
}

Measured memory_bytes: 5116
#include<bits/stdc++.h>
using namespace std;
int n, m, ERR;
int f[100010], val[100010];
int find(int x) {
	if(f[x] == x) return x;
	int px = f[x];
	f[x] = find(f[x]);
	val[x] += val[px];
	return f[x];
}
void merge(int x, int y, int d) {
	int px = find(x);
	int py = find(y);
	f[px] = f[py];
	val[x] = -val[x] + val[y] + d;
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) f[i] = i;
	for(int i = 1; i <= m; i ++) {
		int x, y, d;
		scanf("%d%d%d", &x, &y, &d);
		int px = find(x), py = find(y);
		if(px == py && val[x] - val[y] != d) ERR = 1;
		else if(px != py) {
			f[px] = py;
			val[px] = -val[x] + val[y] + d;
		}
	}
	if(ERR) printf("No\n");
	else printf("Yes\n");
	return 0;
}

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

int bubblesort(int A[], int N){
    int sw = 0; // counter
    
    for(int i = 0; i < N - 1; i++){
        for(int j = N-1; j > i; j--){
            if( A[j] < A[j - 1]){
                swap( A[j], A[j - 1]);
                sw++;
            }
        }
    }
    return sw;
}

int main(){
    int A[100], N, sw;
    
    cin >> N;
    for( int i = 0; i < N; i++) cin >> A[i];
    
    sw = bubblesort(A, N);
    
    for( int i = 0; i < N; i++){
        if(i) cout << " ";
        cout << A[i];
    }
    cout << endl;
    cout << sw << endl;
    
    return 0;
}


Measured memory_bytes: 3112
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define sz(v) int(v.size())

using namespace std;
using ll = int64_t;

struct Edge {
  int id, to;
};

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

  int N, M;
  cin >> N >> M;
  vector<int> D(N);
  for (int i = 0; i < N; i++) {
    cin >> D[i];
  }
  int min_cost = *min_element(all(D));
  vector<char> used(N, false);
  vector<char> color(N, false);
  vector<int> costs(M, -1);
  vector<vector<Edge>> G(N);
  for (int i = 0; i < M; i++) {
    int U, V;
    cin >> U >> V;
    --U, --V;
    G[U].pb(Edge{i, V});
    G[V].pb(Edge{i, U});
  }
  vector<int> order(N);
  iota(all(order), 0);
  sort(all(order), [&](auto lhs, auto rhs) {
    return D[lhs] < D[rhs];
  });
  for (int u : order) {
    for (auto e : G[u]) {
      int v = e.to;
      if (used[v]) {
        // assert(costs[e.id] == -1);
        costs[e.id] = D[u];
        if (!used[u]) {
          used[u] = true;
          color[u] = !color[v];
        }
      } else if (D[u] == D[v]) {
        // assert(costs[e.id] == -1);
        assert(!used[v]);
        costs[e.id] = D[u];
        color[v] = !color[u];
        used[u] = used[v] = true;
      }
    }
  }
  for (auto u : used) {
    if (!u) {
      cout << -1 << endl;
      return 0;
    }
  }
  for (int i = 0; i < N; i++) {
    cout << (color[i] ? "W" : "B");
  }
  cout << endl;
  for (int i = 0; i < M; i++) {
    assert(costs[i] != -1);
    cout << costs[i] << endl;
  }



  return 0;
}


Measured memory_bytes: 12032
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        o: Chars,
        e: Chars,
    }
    let mut j = 0;
    let mut l = 0;
    for i in 0..(o.len()+e.len()) {
        if i%2==0 {
            print!("{}", o[j]);
            j += 1;
        } else {
            print!("{}", e[l]);
            l += 1;
        }
    }

    print!("\n");

}


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

#define ff first
#define ss second
#define maxn 2000006
#define pb push_back
#define ll long long
#define lll __int128
#define vll vector<ll>
#define mll map<ll,ll>
#define MOD 1000000007
#define pll pair<ll,ll>
#define ull unsigned long long
#define f(i,x,n) for(int i=x;i<=n;i++)

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

using namespace std;

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

	ll n; cin >> n;

	cout << n*n*n;

	return 0;
}

Measured memory_bytes: 256
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int isprime(int n){
    int count =0;
    for(int i=2;i<=sqrt(n);i++)
    if(n%i==0)count++;
    if(count)return 0;
    return 1;
}
int main()
{
   ll n;
   cin>>n;
   ll a[n];
   ll s[2000009]={0};
   for(int i=0;i<n;i++){
   cin>>a[i];
   }
   sort(a,a+n);
   for(int i=0;i<n-1;i++){
       if(a[i]==a[i+1])s[a[i]]=1;
   }
   
   ll m = a[n-1];
   int count =0;
   for(ll i=0;i<n;i++){
       if(!s[a[i]])count++;
       for(ll j=1;j*a[i]<=m;j++)
       s[j*a[i]]=1;
   }
   
   cout<<count;
     return 0;
}




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

#define fr(i,n) _back
#define pb	push_back
#define eb	emplace_back
#define mk	make_pair
#define fi	first
#define se	second
#define endl	'\n'

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
const ll INF = 2e18;
const double PI = acos(-1.0);

ll solve(ll l, ll c) {
    ll ans = INF;

    //corta na linha
    for(ll i = 1; i <= l/2; i++) {
        ll area1 = c*i;
        ll sobraL = l-i;
        ll x = max(abs(area1 - (sobraL/2)*c), abs(area1 - (sobraL/2+(sobraL&1))*c));
        ll y = max(abs(area1 - (c/2)*sobraL), abs(area1 - (c/2+(c&1))*sobraL));
        ans = min({ans,x,y});
    }

    //corta na coluna
    for(ll i = 1; i <= c/2; i++) {
        ll area1 = l*i;
        ll sobraC = c-i;
        ll x = max(abs(area1 - (sobraC/2)*l), abs(area1 - (sobraC/2+(sobraC&1))*l));
        ll y = max(abs(area1 - (l/2)*sobraC), abs(area1 - (l/2+(l&1))*sobraC));
        ans = min({ans,x,y});
    }

    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    ll l,c; cin >> l >> c;
    cout << solve(l,c) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define F(i,j,k,in) for(int i=j;i<k;i+=in)
#define DF(i,j,k,in) for(int i=j;i>=k;i-=in)
#define foreach(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define PB push_back
#define ub upper_bound
#define lb lower_bound
#define ins insert
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   ll a,b,c;
   cin>>a>>b>>c;
   swap(a,b);
   swap(a,c);
   cout<<a<<" "<<b<<" "<<c;

return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int h,n;
	cin>>h>>n;
	vector<pair<int,int> > arr(n);
	for(int i=0;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		arr[i]=make_pair(a,b);
	}
	vector<int> dp(10002,INT_MAX);
	dp[0]=0;
	for(int i=0;i<10002;i++)
	{
		for(int j=0;j<n;j++)
		{
			dp[i]=min(dp[i],(dp[max(i-arr[j].first,0)]+arr[j].second));
		}
	}
	cout<<dp[h]<<endl;
	
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int N, M;

struct item{
    ll x;
    ll y;
    ll z;
};

ll num[8][1001][1001];

item cake[1000];

int main(void) {
    // insert code here...
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        cin >> cake[i].x >> cake[i].y >> cake[i].z;
    }
    
    for(int a = 0; a < 2; a++){
        for(int b = 0; b < 2; b++){
            for(int c = 0; c < 2; c++){
                for(int i = 0; i < N; i++){
                    for(int j = 0; j < M && j<=i; j++){
                        if(i==j){
                            num[a + b*2 + c*4][i+1][j+1] = num[a + b*2 + c*4][i][j] + cake[i].x*(-1 + 2*a) + cake[i].y*(-1 + 2*b) + cake[i].z*(-1 + 2*c);
                        }else{
                        num[a + b*2 + c*4][i+1][j+1] = max(num[a + b*2 + c*4][i][j] + cake[i].x*(-1 + 2*a) + cake[i].y*(-1 + 2*b) + cake[i].z*(-1 + 2*c), num[a + b*2 + c*4][i][j+1]);
                        }
//                        cout <<a <<b <<c << " " << i+1<<" "<< j+1<< num[a + b*2 + c*4][i+1][j+1] << endl;
                    }
                }
                
                
                
            }
        }
    }
    
    ll ans = 0;
    
    for(int i = 0; i < 8; i++){
        if(num[i][N][M]>ans){
            ans = num[i][N][M];
        }
    }
    
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 62208
#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const ll nmax=1e4+50;
const int mod=1e9+7;
using namespace std;
int n,i,x,y,j,b[nmax],sz[nmax],rs[nmax],ans;
pair<int,int>p,e[nmax];
set<pair<int,int> >s;
vector<int>a[nmax];
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<n;i++)
	{
		cin>>x>>y;
		a[x].pb(y);
		a[y].pb(x);
		e[i]={x,y};
	}
	for(i=1;i<=n;i++)cin>>b[i];
	sort(b+1,b+n+1);
	for(i=1;i<=n;i++)
	{
		sz[i]=(int)a[i].size();
		s.in({sz[i],i});
	}
	while(!s.empty())
	{
		p=(*s.begin());
		//cout<<p.fr<<" "<<p.sc<<endl;
		s.er(s.begin());
		rs[p.sc]=b[++j];
		sz[p.sc]=0;
		for(i=0;i<a[p.sc].size();i++)
		{
			if(sz[a[p.sc][i]])
			{
				s.er(s.fd({sz[a[p.sc][i]],a[p.sc][i]}));
				sz[a[p.sc][i]]--;
				s.in({sz[a[p.sc][i]],a[p.sc][i]});
			}
		}
	}
	for(i=1;i<n;i++)ans+=min(rs[e[i].fr],rs[e[i].sc]);
	cout<<ans<<endl;
	for(i=1;i<=n;i++)cout<<rs[i]<<" ";
	cout<<endl;
    return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;
using ll = long long ;

ll a, b, n;

int main () {

    cin >> a >> b >> n;
    ll has = min(b - 1, n);

    cout << (a * has) / b;
}
/*
    Good Luck
        -Lucina
*/
/*
    I hate Progmeth
*/


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

int main() {
    int n, h, w;
    cin >> n >> h >> w;
    int ans = 0;
    rep(i,n) {
        int a, b;
        cin >> a >> b;
        if (h <= a && w <= b) ans++;
    }
    cout << ans << endl;
}

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

int main() {
  string s;
  cin>>s;
  long long mod = 1e9+7;
  int n = s.length();
  long long dp[n+1][13];
  for (int i=0; i<n+1; i++) {
    for (int j=0; j<13; j++) {
      dp[i][j] = 0;
    }
  }
  dp[0][0] = 1;
  reverse(s.begin(), s.end());
  long long p10 = 1;
  for (int i=0; i<n; i++) {
    for (int j=0; j<10; j++) {
      if (s[i] != '?' && s[i] != '0' + j) {
        continue;
      }
      long long tmp = (p10 * j) % 13;
      for (int k=0; k<13; k++) {
        dp[i+1][(tmp+k)%13] += dp[i][k];
        dp[i+1][(tmp+k)%13] %= mod;
      }
    }
    p10 *= 10;
    p10 %= 13;
  }
  cout<<dp[n][5]<<endl;
}

Measured memory_bytes: 10624
#include <bits/stdc++.h>
#define Rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef int64_t intl;


int main(){
  int N;
  cin >>N;
  set<string> S;
  string A;
  Rep(i,N){
    cin >> A;
    S.insert(A);
  }
  cout << S.size();
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string a, b, c;
	cin >> a >> b >> c;
	if (a[a.size()-1]==b[0] && b[b.size()-1]==c[0]){
		cout << "YES" << endl;
	} else {
		cout << "NO" << endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long int
#define ldouble long double
#define vin vector<int>
#define rep(a,n) for(int i=(a);i<(n);i++)
#define INF (int)1000000007

//setprecision()<<

using namespace std;

void fin(int n,vin &a){
    rep(0,n){
        cin>>a.at(i);
    }
}

signed main(){
    int N,K,S;
    cin>>N>>K>>S;
    rep(0,N){
        if(i<K){
            cout<<S<<" ";
        }
        else{
            if(S==1000000000){
                cout<<S-1<<" ";
            }
            else{
                cout<<S+1<<" ";
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1280