akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
const double EPS = 1e-9;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;

#define MAX_N (1<<18)

struct segtree{
    ll n, dat[2*MAX_N-1]; //(1<<17) = 130000
    int cnt[2*MAX_N-1];

    void init(int n_){
        n = 1;
        while(n < n_) n *= 2;
        for(int i = 0; i < 2*n-1; i++) dat[i] = 0;
        for(int i = 0; i < 2*n-1; i++) cnt[i] = 0;
    }

    void update(int k, ll a){
        k += n-1;
        dat[k] = a;
        cnt[k]++;
        while(k > 0){
            k = (k-1)/2;
            dat[k] = dat[k*2+1] + dat[k*2+2];
            cnt[k] = cnt[k*2+1] + cnt[k*2+2];
        }
    }

    //(a,b,0,0,seg.n)で呼ぶ
    ll query(int a, int b, int k, int l, int r){
        if(r <= a || b <= l) return 0;
        if(a <= l && r <= b) return dat[k];
        else{
            ll vl = query(a,b,k*2+1,l,(l+r)/2);
            ll vr = query(a,b,k*2+2,(l+r)/2,r);
            return vl + vr;
        }
    }
    ll bin(int k, int mid){
        if (k >= n-1) {
            return k-(n-1);
        }
        if (cnt[k*2+1] >= mid) bin(k*2+1, mid);
        else bin(k*2+2, mid - cnt[k*2+1]);
    }
} seg;

int q;
int q1 = 0;
ll a[200000], b[200000];
int o[200000];
set<pl> s;
map<pl, int> pos;
int rpos[200000];

int main() {
    cin >> q;
    seg.init(q);
    rep(i,q) {
        cin >> o[i];
        if (o[i] == 1) {
            cin >> a[q1] >> b[q1];
            s.insert(pl(a[q1],i)); q1++;
        }
    }
    {
        int i = 0;
        for (auto it = s.begin(); it != s.end(); it++) {
            rpos[i] = (*it).first;
            pos[*it] = i++;
        }
    }
    q1 = 0;
    ll B = 0;
    rep(i,q) {
        if (o[i] == 1) {
            //cerr << pos[a[q1]] << " " << a[q1] << endl;
            seg.update(pos[pl(a[q1],i)], a[q1]);
            B += b[q1];
            q1++;
        } else {
            int pos = seg.bin(0, (q1+1)/2);
            cout << rpos[pos] << " ";
            if (q1%2) {
                cout << B + -1 * seg.query(0, pos, 0, 0, seg.n) + seg.query(pos+1, seg.n, 0, 0, seg.n) << endl;;
            } else {
                cout << B + -1 * seg.query(0, pos+1, 0, 0, seg.n) + seg.query(pos+1, seg.n, 0, 0, seg.n) << endl;;
            }
            //cout << seg.bin()+B << endl;
        }
    }
}

Measured memory_bytes: 36096
/*
    @uthor: Amit Kumar
    user -->GitHub: drviruses ; CodeChef: dr_virus_ ; Codeforces,AtCoder,Hackerearth,Hakerrank: dr_virus;
*/
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#define ln mp::cpp_int;
#define ll    long long
#define ld    long double
#define ull   unsigned long long
#define endl "\n"
ll google_itr = 1;
#define google(x) cout<<"Case #"<<x<<":"
#define pi 3.14159265358979323846264338327950L

const ll mod = 1e9+7;
const ll inf = 1e18;

ll popcount(ll num){
    num = num - ((num >> 1) & 0x55555555);
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    return ((num + (num >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

vector<pair<ll,ll>> factor_arr;

void myfactor(ll num){ 
    ll count = 0;   
    while (!(num % 2)) { 
        num >>= 1; count++; 
    }  
    if (count) factor_arr.push_back({2,count}); 
    for (auto i = 3; i <= sqrt(num); i += 2) { 
        count = 0; 
        while (num % i == 0) { 
            count++; 
            num /= i; 
        } 
        if (count) factor_arr.push_back({i,count}); 
    } 
    if (num > 2) factor_arr.push_back({num,1});
}

void virus(){
        ll n,k;
        cin>>n>>k;
        if(n < k) cout<<min(n,(k-n));
        else if(n%k == 0) cout<<"0";
        else{
            cout<<min(n,abs((n%k) - k));
        }
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
  /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/

    ll t=1;
    //cin>>t;
    while(t--){
           auto start = high_resolution_clock::now();
           virus();
           auto stop = high_resolution_clock::now();
           auto duration = duration_cast<seconds>(stop - start);
         //cout << "Time: "<<duration.count()<<endl;
        //your code goes here
    }
    return 0;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;
int main(){
  int n,x;
  cin >> n >> x;
  priority_queue<int>q;
  rep(i,n){
    int a;
    cin >> a;
    q.push(a);
   }
  rep(i,x){
    int b = q.top();q.pop();
    q.push(b/2);
    }
  ll ans = 0;
  while(!q.empty()){
    ans += q.top(); q.pop();
   }
  cout << ans << endl;
  }

Measured memory_bytes: 892
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
	string s;
	cin >> s;
	
	int ans = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '+') {
			ans = ++ans;
		}
		else {
			ans = --ans;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		//入力
		int N = sc.nextInt();

		//ページ数
		int page = N / 2;

		//あまり
		int amari = N % 2;

		if (1 == amari) {
			System.out.println(page + 1);

		} else {
			System.out.println(page);
		}

	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = (n); i >= 0; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 25;
const int MOD = 1e9+7;
const int MAX = 2*1e6+1;
ll fact[MAX], inv[MAX], finv[MAX];
void COM() {
  fact[0] = fact[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;

  for (int i = 2; i < MAX; i++)
  {
    fact[i] = i * fact[i-1] % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = inv[i] * finv[i-1] % MOD;
  }
}

ll combination(int n, int k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fact[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

int main() {
  int x, y;
  cin >> x >> y;
  int a = (2*y-x), b = (2*x-y);
  if (a < 0 || b < 0 || a%3 != 0 || b%3 != 0) {
    cout << 0 << endl;
    return 0;
  }
  
  COM();
  a /= 3;
  b /= 3;
  //cout << a << ' ' << b << endl;
  cout << combination(a+b,a) << endl;
  return 0;
}

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

int main()
{
    int N, K;
    std::string S;
    std::cin >> N >> S >> K;

    for (int i = 0; i < N; ++i)
    {
        if (S[i] != S[K - 1])
        {
            S[i] = '*';
        }
    }

    std::cout << S << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define LL long long
#define lowbit(x) (x&(-x))

struct xx {
	int xi,yi;
	bool operator < (const xx &_) const {
		return xi < _.xi;
	}
} w[N];
const int mo = 998244353;
LL Pow[N],Cnt[N][5];

LL C[N],ed;
void Update(int idx) {
	while(idx <= ed) {
		C[idx] ++;
		idx += lowbit(idx);
	}
	return ;
}
LL Sum(int idx) {
	LL res = 0;
	while(idx > 0) {
		res += C[idx];
		idx -= lowbit(idx);
	}
	return res;
}

void Add(LL &res,LL x) {
	res = res+x >= mo? res+x-mo:res+x;
	return ;
}

int B[N];
int main() {
	int n;
	cin >> n;
	Pow[0] = 1;
	for(int i=1; i<=n; i++) Pow[i] = Pow[i-1]*2%mo;

	int tot = 0;
	for(int i=1; i<=n; i++) scanf("%d%d",&w[i].xi,&w[i].yi),B[++tot] = w[i].yi;
	sort(B+1,B+tot+1);
	ed = unique(B+1,B+tot+1)-B-1;
	for(int i=1; i<=n; i++) w[i].yi = lower_bound(B+1,B+ed+1,w[i].yi) - B;

	sort(w+1,w+n+1);

	for(int i=1; i<=n; i++) {
		Cnt[i][3] = Sum(w[i].yi);
		Cnt[i][2] = i-1-Cnt[i][3];
		Update(w[i].yi);
	}
	memset(C,0,sizeof(C));
	for(int i=n; i>=1; i--) {
		Cnt[i][4] = Sum(w[i].yi);
		Cnt[i][1] = n-i-Cnt[i][4];
		Update(w[i].yi);
	}
	LL Ans = 0;
	/*
		Case0: Me.

		Case1: 1.3.
		Case2: 2.4.

		Case3: 1.3.2
		Case4: 1.3.4

		Case5: 2.4.1
		Case6: 2.4.3

		Case7: 1.2.3.4
	*/
	for(int i=1; i<=n; i++) {
		Add(Ans,Pow[n-1]);
		LL C1 = Pow[Cnt[i][1]]-1,C2 = Pow[Cnt[i][2]]-1,C3 = Pow[Cnt[i][3]]-1,C4 = Pow[Cnt[i][4]]-1;

		Add(Ans,C1*C3%mo);
		Add(Ans,C2*C4%mo);

		Add(Ans,C1*C3%mo*C2%mo);
		Add(Ans,C1*C3%mo*C4%mo);

		Add(Ans,C2*C4%mo*C1%mo);
		Add(Ans,C2*C4%mo*C3%mo);

		Add(Ans,C1*C2%mo*C3%mo*C4%mo);
	}
	cout<<Ans;
	return 0;
}

Measured memory_bytes: 13568
X = int(input())

fh = 0
f  = 0

while X > 0:
    if X // 500 > 0:
        num = X // 500
        fh += num
        X -= num * 500
    elif X // 5 > 0:
        num = X // 5
        f += num
        X -= num * 5
    else:
        break

ans = 1000 * fh + 5 * f

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, MOD = 1e9 + 7;

int a[N], f[N];
int las[N];
int main() {
    // freopen("data.in", "r", stdin);
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        f[i] = f[i - 1];
        if(las[a[i]] && las[a[i]] != i - 1) f[i] = (f[i] + f[las[a[i]]]) % MOD;
        las[a[i]] = i;
    }
    printf("%d\n", f[n]);
    return 0;
}


Measured memory_bytes: 2560
while True:
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        break
    X = max(a,b)
    Y = min(a,b)
    
    count = 0
    while True:
        count += 1
        d = X % Y
        X,Y = Y,d
        if d == 0:
            break
    print(X,count)


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

int main(){
  long long N,A,B;
  cin >> N >> A >> B;
  long long sum=(N/(A+B))*A;

  if(N%(A+B)<=A){
    cout << sum + N%(A+B) << endl;
  }
  else{
    cout << sum +A << endl;
  }
}


Measured memory_bytes: 256
#AGC032-B
"""
dp解法。
そこまでにその色で出来た組み合わせの総和がいくつかを保持する配列を
持っておく。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
lst1 = []
bef = -1
for i in range(n):
    res = int(readline())
    if bef == res:
        continue
    else:
        lst1.append(res)
        bef = res

n = len(lst1)
lst2 = [-1]*(2*10**5+1)
dp = [0]*(n+1)
dp[0] = 1
for i in range(1,n+1):
    c = lst1[i-1]
    if lst2[c]==-1:
        lst2[c] = i
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1] + dp[lst2[c]])%(10**9+7)
        lst2[c] = i

print(dp[-1])

Measured memory_bytes: 83848
n,W = gets.split.map(&:to_i)

s = 4.times.map{[]}
m = -1
n.times{
  w,v = gets.split.map(&:to_i)
  m = w if m==-1
  s[w-m] << v
}

4.times{|i|
  s[i] = [0] + s[i].sort.reverse
  (s[i].size-1).times{|j|
    s[i][j+1] += s[i][j]
  }
}

ans = 0
s[0].size.times{|i|
  s[1].size.times{|j|
    s[2].size.times{|k|
      s[3].size.times{|l|
        sum = (m)*i + (m+1)*j + (m+2)*k + (m+3)*l
        if sum <= W
          tmp = s[0][i] + s[1][j] + s[2][k] + s[3][l]
          ans = tmp if ans < tmp
        end
      }
    }
  }
}

p ans


Measured memory_bytes: 1916
#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N;
  string S;
  ll ans = 0;
  ll cur=0;
  cin >> N >> S;
  rep(i, N){
    if(S[i]=='I')ans++;
    else ans--;
    cur = max(ans, cur);
  }
  cout << cur;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,x;
	cin>>a>>b>>c>>x;
	int sum=0;
	int ans=0;
	for(int i=0;i<=a;i++)
	{
		for(int j=0;j<=b;j++)
		{
			for(int k=0;k<=c;k++)
			{
				sum=i*500+j*100+k*50;
				if(x==sum)	ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef long double ld;
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1010;
int n, m;
char t[N][N];
int a[N], b[N];
int A, B;

void tryFill() {
	set<pii> setik;
	for (int i = 0; i < m; i++)
		setik.insert(mp(-b[i], i));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			t[i][j] = '0';
	for (int i = 0; i < n; i++) {
		vector<int> z;
		for (int j = 0; j < a[i]; j++) {
			int p = setik.begin()->second;
			setik.erase(setik.begin());
			if (b[p] == 0) return;
			t[i][p] = '1';
			b[p]--;
			z.push_back(p);
		}
		for (int x : z)
			setik.insert(mp(-b[x], x));
	}
	for (int i = 0; i < n; i++) {
		t[i][m] = '\0';
		printf("%s\n", t[i]);
	}
	exit(0);
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d%d%d", &n, &m, &A, &B);
	for (int i = 0; i <= n; i++) {
		int sA = i * (m - A) + (n - i) * A;
		for (int k = 0; k < n; k++)
			a[k] = (k < i ? m - A : A);
		for (int j = 0; j <= m; j++) {
			int sB = j * (n - B) + (m - j) * B;
			if (sA != sB) continue;
			for (int k = 0; k < m; k++)
				b[k] = (k < j ? n - B : B);
			tryFill();
		}
	}
	printf("-1\n");
	return 0;
}


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

int main() {
  int N;
  long long int K;
  cin >> N >> K;
  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);
  
  long long int ans = 0, MOD = 1000000007;
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j < N; j++) {
      if (A.at(i) < A.at(j)) ans = (ans + K * (K - 1) / 2 % MOD) % MOD;
      else if (A.at(i) > A.at(j)) ans = (ans + K * (K + 1) / 2 % MOD) % MOD;
    }
  }
  
  if (ans < 0) ans += MOD;
  cout << ans << endl;
}

Measured memory_bytes: 3612
#include<iostream>
#include<string>
#include<cmath>
#include<cctype>
#include<cstdlib>

using namespace std;

int i;
string str;

bool dfs()
{
	bool flag = true;
	if(str[i] == 'm')
		i++;
	else 
		return false;
	
	
	if(str[i] == 'm')
		flag = dfs();
	if(str[i] == 'e')
		i++;
	else
		return false;
	
	if(!flag)return false;
	
	if(str[i] == 'm')
		flag = dfs();
	if(str[i] == 'w')
		i++;
	else
		return false;
	
	if(!flag)return false;
	
	return true;
	
}

int main()
{
	cin >> str;
	i = 0;
	if(dfs() && str[i] == '\0')cout << "Cat" << endl;
	else cout << "Rabbit" << endl;
	
	return 0;
}

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

#define rep(i, n) REP(i, 0, n)
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(x) cout << x << endl;

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

    int ans = to_string(n).length();
    // 
    for(long i = 1; i * i <= n; i++){
        if(n % i == 0){
            int a = to_string(i).length();
            int b = to_string(n / i).length();
            ans = min(ans, max(a, b));
        }
    }
    OP(ans);
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
c.sort()
ans = 0
for j in range(n):
    l = 0
    r = n - 1
    i = (l + r) // 2
    while l <= r:
        if a[i] >= b[j]:
            r = i - 1
        else:
            l = i + 1
        i = (l + r) // 2
    l = 0
    r = n - 1
    k = (l + r) // 2
    while l <= r:
        if c[k] <= b[j]:
            l = k + 1
        else:
            r = k - 1
        k = (l + r) // 2
    ans += (i + 1) * (n - (k + 1))
print(ans)

Measured memory_bytes: 29324
#include <iostream>

using namespace std;

int main(){
    int n, s[1000];
    while(cin >> n && n > 0){
        int  max = 0, min = 10000, sum = 0;
        for (int i = 0; i < n; i++){
            cin >> s[i];
            sum += s[i];
        }
        for (int i = 0; i < n; i++){
            if (s[i] > max)
                max = s[i];
        }
        for (int i = 0; i < n; i++){
            if (s[i] < min)
                min = s[i];
        }
        cout << (sum - max - min)/(n - 2) << endl;
    }
}

Measured memory_bytes: 1164
h, w = map(int, input().split())
s = ["."*(w+2)]+["."+input()+"." for i in range(h)]+["."*(w+2)]
for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j]=="#" and s[i-1][j]==s[i][j-1]==s[i][j+1]==s[i+1][j]==".":
            print("No")
            exit()
print("Yes")


Measured memory_bytes: 38896
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        if(a == 1){
            System.out.println("Hello World");
        } else if(a == 2){
            int b = sc.nextInt();
            int c = sc.nextInt();
            System.out.println(b + c);
        }
    }
}


Measured memory_bytes: 21716
#include<iostream>
using namespace std;
 
int main(){
  int N;
  int d[110];
  cin >> N;
  for(int i=0;i<N;i++) cin >> d[i];
  
  int num[110]={0};
  for(int i=0;i<N;i++){
    num[d[i]]++;
  }
  
  int count = 0;
  for(int i=0;i<=100;i++){
    if(num[i]>0){
      count++;
    }
  }
  cout << count << endl;
}

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

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] iArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
            long A = iArray[0];
            long B = iArray[1];
            long K = iArray[2];
            if (A == 0 && B == 0)
            {
                Console.WriteLine("0 0");
                return;
            }
            if(K == 0)
            {
                Console.WriteLine(A + " " + B);
                return;
            }
            if (K <= A)
            {
                Console.WriteLine((A - K) + " " + B);
                return;
            }
            if (A + B <= K)
            {
                Console.WriteLine("0 0");
                return;
            }
            if (K < A + B)
            {
                Console.WriteLine("0 " + (B - (K - A)));
            }
        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

Measured memory_bytes: 11348
#include <algorithm>
#include <iostream>

using namespace std;

const int M = 998244353;
int n, m, k;
long long kaijo[220000];
long long ans;

long long mpw(long long a, int n) {
  if (n == 0) return 1;
  if (n % 2) return mpw(a, n-1) * a % M;
  return mpw(a*a%M, n/2);
}

int main() {
  cin >> n >> m >> k;
  
  kaijo[0] = 1;
  for (int i = 1; i < 210000; i++) {
    kaijo[i] = kaijo[i-1] * i % M;
  }
  
  for (int i = 0; i <= k; i++) {
    ans += m * kaijo[n-1] % M * mpw(kaijo[i], M-2) % M * mpw(kaijo[n-i-1], M-2) % M * mpw(m-1, n-i-1) % M;
    ans %= M;
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 5280
#include<bits/stdc++.h>
#define N 100007
using namespace std;
int n,h,w,n0,tot=0,a,b;
long long cnt[20],mul=int(1e9)+7,mp[N<<5];
int main(){
	scanf("%d%d%d",&h,&w,&n);
	cnt[0]=1ll*(w-2)*(h-2);
	while(n--){
		scanf("%d%d",&a,&b);
		for(int j=0;j<3;++j)for(int k=0;k<3;++k)
			if(a-j>=1&&a-j<=h-2&&b-k>=1&&b-k<=w-2)mp[tot++]=mul*(a-j)+(b-k);
	}
	sort(mp,mp+tot);
	for(int tmp=1,i=0;i<tot;++i){
		if(mp[i]==mp[i+1])++tmp;
		else ++cnt[tmp],tmp=1,--cnt[0];
	}
	for(int i=0;i<=9;++i)printf("%lld\n",cnt[i]);
	return 0;
}

Measured memory_bytes: 8448
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define sz(a) ((int)(a).size())
#define vi vector<int>
#define pii pair<int,int>
#define R(a) scanf("%d",&a)
#define per(i,a,b) for(int i=a;i>=int(b);i--)
#define rep(i,a,b) for(int i=a;i<=int(b);i++)
#define rix(i,x) for(int i=last[x];i;i=pre[i])
ll pow(ll a,ll b,ll M){ll t=1;for(a%=M;b;b>>=1){if(b&1)t=t*a%M;a=a*a%M;}return t;}
const int N=1e5+5;
struct P{
	int x,y;
	friend int operator<(P a,P b){
		return a.x-a.y<b.x-b.y;
	}
}a[N];
priority_queue<int,vector<int>,greater<int> >q;
int x,y,z,n;ll ans=-1e18,cnt,b[N];
int main(){
	cin>>x>>y>>z;n=x+y+z;
	rep(i,1,n){
		int c;
		R(a[i].x);R(a[i].y);R(c);
		cnt+=c;a[i].x-=c;a[i].y-=c;
	}
	sort(a+1,a+n+1);
	ll sum=0;rep(i,1,n){
		if(sz(q)<y)q.push(a[i].y),sum+=a[i].y;
		else if(q.top()<a[i].y)sum-=q.top(),q.pop(),q.push(a[i].y),sum+=a[i].y;
		b[i]=sum;
	}
	while(!q.empty())q.pop();
	sum=0;per(i,n,1){
		if(sz(q)<x)q.push(a[i].x),sum+=a[i].x;
		else if(q.top()<a[i].x)sum-=q.top(),q.pop(),q.push(a[i].x),sum+=a[i].x;
		if(i-1>=y&&sz(q)==x)ans=max(ans,b[i-1]+sum);
	}
	cout<<ans+cnt<<endl;
}










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

int main(){
    string S;
    cin >> S;
    int ans = 0;
    int tmp = 0;
    int n = S.length();
    for(int i=0;i<n;++i){
      if(S[i]=='A'||S[i]=='C'||S[i]=='G'||S[i]=='T'){
        tmp += 1;
        if(i==n-1)ans=max(ans,tmp);
      }
      else{
        ans = max(ans,tmp);
        tmp = 0;
      }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
vector <string> a3 = {"aa.\n", "..a\n","..a\n"};
vector <string> a4 = {"aacd", 
                      "bbcd",
                      "efgg",
                      "efhh"};

vector <string> a5 = {"aabbc", 
                      "hii.c",
                      "h..jd",
                      "g..jd",
                      "gffee"};

vector <string> a7 = {"...rty.", 
                      "...rty.",
                      "..aabbc",
                      "rre...c",
                      "yye...d",
                      "uuf...d",
                      "..fgghh"};

void place(vector <vector <char> > &a, vector <string> &b, int o, int f){
    int y = b.size();
    for(int i = 0; i < y; ++i){
        for(int j = 0; j < y; ++j){
            a[i+o][j+f] = b[i][j];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout << setprecision(10);
    cout << fixed;
    int n;
    while(cin >> n){
        vector < vector <char> >a(n, vector <char> (n, '.'));
        if(n == 2){
            cout <<"-1\n";
            continue;
        }
        if(n % 3 == 0){
            int m = n;
            int o = 0;
            while(m){
                place(a,a3,o,o);
                o += 3;
                m -= 3;
            }
        }
        else if(n == 7){
            place(a,a7,0,0);
        }
        else if(n == 11){
            place(a,a7,0,0);
            place(a,a4,7,7);
        }
        else {
            int u = -1, k = 0;
            for(; k < n; ++k){
                if((n-k*4)%5 == 0){
                    u = (n-k*4)/5;
                    break;
                }
            }
            if(u == -1)cout <<"VERY VERY BAD\n";
            int o = 0;
            for(int i = 0; i < k; ++i){
                place(a,a4,o,o);
                o+=4;
            }
            for(int i = 0; i < u; ++i){
                place(a,a5,o,o);
                o+=5;
            }
        }
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                cout << a[i][j];
            }
            cout << '\n';
        }
    }
    //sort(a.begin(), a.end());
    //random_shuffle(a.begin(), a.end());
}


Measured memory_bytes: 2304
// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(),x.end()
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define erase_duplicates(x) sort(all(x)); (x).resize(distance((x).begin(), unique(all(x))));


using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef vector<LL> VLL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long double LD;
typedef pair<LD,LD> PLD;
typedef vector<LD> VLD;
typedef vector<PLD> VPLD;

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<" = "<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<" = "<<h<<", "; _dbg(sdbg+1, a...);
}

#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#define cerr if(0)cout
#endif

const int maxn = (1e6)+7;
const int maxk = 20;
const int inf = (1e9)+7;
const LL LLinf = ((LL)1e18)+7LL;
const LD eps = 1e-9;
const LL mod = 1e9+7;

// ***************************** CODE ***************************** //

LL val[maxn];
LL val2[maxn];

int main()
{
	_upgrade
  string s;
  cin>>s;
  for(int i = 0;i < SZ(s);i++)
  {
    if(s[i] == '<')
      val[i + 1] = val[i] + 1;
    else
      val[i + 1] = 0;
  }
  for(int i = SZ(s) - 1;i >= 0;i--)
  {
    if(s[i] == '<')
      val2[i] = 0;
    else
      val2[i] = val2[i + 1] + 1;
  }
  LL res = 0LL;
  for(int i = 0;i <= SZ(s);i++)
    res += max(val[i], val2[i]);
  cout<<res;

	return 0;
}


Measured memory_bytes: 11164
import java.util.*;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] a = new int[3];
        int n = 0;
        for(int i = 0; i<N; i++) {
            n = sc.nextInt();
            if(n%4==0) a[0]++;
            else if(n%2==0) a[1]++;
            else a[2]++;
        }
        if(a[0]>=a[2]) {
            System.out.println("Yes");
        }else if(a[2]-a[0]==1 && a[1] == 0) {
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 48504
#include <iostream>
#define MAX 100010

using namespace std;

long int a[MAX];

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

	a[0] = 0;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}

	long int count = 0;
	for (int i = 1; i <= N; i++) {
		long int d = a[i - 1] + a[i] - x;
		if (d > 0) {
			count += d;
			a[i] -= d;
		}
	}

	cout << count << endl;
}


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

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = INT_MAX;
const ll LLINF = INT64_MAX;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n, -1) {}
    void init(int n) { par.assign(n, -1); }

    int root(int x)
    {
        if (par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }

    bool issame(int x, int y)
    {
        return root(x) == root(y);
    }

    bool merge(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (par[x] > par[y])
            swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x)
    {
        return -par[root(x)];
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k, l;
    cin >> n >> k >> l;
    UnionFind way(n), train(n);
    for (int i = 0; i < k; i++)
    {
        int p, q;
        cin >> p >> q;
        p--;
        q--;
        way.merge(p, q);
    }
    for (int i = 0; i < l; i++)
    {
        int r, s;
        cin >> r >> s;
        r--;
        s--;
        train.merge(r, s);
    }
    vector<pair<int, int>> cnt(n);
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i++)
    {
        cnt[i] = make_pair(way.root(i), train.root(i));
        mp[cnt[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        cout << mp[cnt[i]] << " ";
    }
    cout << "\n";
}

Measured memory_bytes: 15104
a,b,c,d = map(int, input().split())
i = 1
TreminingHP = a
AreminingHP = c
while(True):
  if i % 2 is 1:
    AreminingHP-= b
    if AreminingHP<=0:
      print("Yes")
      break
  else:
    TreminingHP-= d
    if TreminingHP<=0:
      print("No")
      break
  
  i+=1

Measured memory_bytes: 9116
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i=0; i<(ll)n; i++)
#define REPR(i, n) for(ll i=(ll)n-1; i>=0; i--)
#define FOR(i, m, n) for(ll i=(ll)m; i<(ll)n; i++)
#define FORR(i, m, n) for(ll i=(ll)m-1; i>=(ll)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
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 (a>b) { a = b; return 1; } return 0; }
struct nya{ nya(){ cin.tie(0); ios::sync_with_stdio(false); } }nyan;


int main(){
    ll N;
    cin >> N;
    cout << N / 3 << "\n";
}


Measured memory_bytes: 256
#include<stdio.h>

int main() {
	int H, W;
	while (1) {
		scanf("%d %d", &H, &W);
		if (H == 0 && W == 0)break;
		for (int j = 0; j < W; j++) printf("#");
		printf("\n");
		for (int i = 0; i < H - 2; i++) {
			printf("#");
			for (int j = 0; j < W - 2; j++) printf(".");
			printf("#\n");
		}
		for (int j = 0; j < W; j++) printf("#");
		printf("\n\n");
	}

	return 0;
}


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

import numpy as np

N,M,L,R = map(int,input().split())

MOD = 10 ** 9 + 7

X=1000
fact = np.arange(X*X,dtype=np.int64).reshape(X,X)
fact[0,0] = 1
for n in range(1,X):
    fact[:,n] *= fact[:,n-1]
    fact[:,n] %= MOD
for n in range(1,X):
    fact[n] *= fact[n-1,-1]
    fact[n] %= MOD
fact = fact.ravel()

fact_inv = np.arange(1,X*X+1,dtype=np.int64)[::-1].reshape(X,X)
fact_inv[0,0] = pow(int(fact[-1]),MOD-2,MOD)
for n in range(1,X):
    fact_inv[:,n] *= fact_inv[:,n-1]
    fact_inv[:,n] %= MOD
for n in range(1,X):
    fact_inv[n] *= fact_inv[n-1,-1]
    fact_inv[n] %= MOD
fact_inv = fact_inv.ravel()[::-1]

U = N - M
comb = fact[U] * fact_inv[:U+1] % MOD * fact_inv[U::-1] % MOD
comb[1::2] *= (-1)

P = np.zeros(R+1,dtype=np.int64)
for i,x in enumerate(comb,M):
    P[::i] += x

P[:M-1:-1] -= P[-M-1::-1]
P %= MOD

# (1-x)^{N+1}で割る
Q = fact[N:N+R+1] * fact_inv[:R+1] % MOD * fact_inv[N] % MOD

def f(R):
    total = fact[R+N] * fact_inv[R] % MOD * fact_inv[N] % MOD
    x = (Q[R::-1] * P[:R+1] % MOD).sum() % MOD
    coef = fact[N] * fact_inv[M] % MOD * fact_inv[N-M] % MOD
    return (total - x*coef)%MOD

answer = (f(R) - f(L-1))%MOD
print(answer)


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

const int MOD = 1000000007;
const int INF = 1e9;

int main(){
  string s;
  cin >> s;
  int sum = 0;
  for(int i = 0; i < s.size(); i++){
    sum += s[i] - '0';
  }
  // cout << sum << endl;
  string ans = "No";
  if(sum%9 == 0) ans = "Yes";
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3720
a,b,c,d=map(int,input().split())
if a>=c and b>=d and d>a:
    print(d-a)
elif a<=c and b<=d and b>c:
    print(b-c)
elif a<c and d<b:
    print(d-c)
elif c<a and b<d:
    print(b-a)
else:
    print(0)

Measured memory_bytes: 3060
import heapq
INF = float('inf')


def dijkstra(g, s):
    n = len(g)
    dist = [INF] * n
    dist[s] = 0
    hq = []
    heapq.heappush(hq, (dist[s], s))
    while hq:
        cost, u = heapq.heappop(hq)
        if dist[u] < cost:
            continue
        for v, c in g[u]:
            if dist[v] <= dist[u] + c:
                continue
            dist[v] = dist[u] + c
            heapq.heappush(hq, (dist[v], v))
    return dist


V, E, r = map(int, input().split())
g = [[] for _ in range(V)]
for _ in range(E):
    s, t, d = map(int, input().split())
    g[s].append((t, d))
ds = dijkstra(g, r)
for d in ds:
    print('INF' if d == INF else d)


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

#define fs first
#define sc second
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using pii = pair<int, int>;
using vi = vector<int>;
using lint = long long;

const int inf = 1001001001;
const lint linf = 1001001001001001001ll;
const int mod = 1e9 + 7;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};

template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; } return a > b; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; } return a < b; }
template<typename T> inline void print(const T &x, string s = "\n") { cout << x << s; }
template<typename T> inline void print(const vector<T> &v, string s = " ")
{ if (!v.size()) puts(""); rep(i, v.size()) cout << v[i] << (i + 1 == v.size() ? "\n" : s); }
inline bool inside(int y, int x, int H, int W) { return 0 <= y && y < H && 0 <= x && x < W; }
inline lint in() { lint x; std::cin>>x; return x; }

struct UnionFind {
	vector<int> p, r;

	UnionFind() {}
	UnionFind(int size) { init(size); }

	void init(int size) {
		p.resize(size);
		r.resize(size);
		for (int i = 0; i < size; ++i) {
			p[i] = i; r[i] = 1;
		}
	}

	int root(int x) {
		if (p[x] == x) return x;
		else return p[x] = root(p[x]);
	}

	void unite(int x, int y) {
		x = root(x); y = root(y);

		if (x == y) return;

		if (r[x] > r[y]) swap(x, y);
		r[x] += r[y];
		p[y] = x;
	}

	bool is_root(int x) {
		return root(x) == x;
	}

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

	int element_count(int x) {
		x = root(x);
		return r[x];
	}
};

int n, k, l;

signed main() {
  cin >> n >> k >> l;
  UnionFind a(n), b(n);
  vi c(n), d(n);
  map<pii, int> ans;

  rep(i, k) {
    int u = in() - 1, v = in() - 1;
    a.unite(u, v);
  }

  rep(i, l) {
    int u = in() - 1, v = in() - 1;
    b.unite(u, v);
  }

  rep(i, n) c[i] = a.root(i);
  rep(i, n) d[i] = b.root(i);

  rep(i, n) {
    ans[mp(c[i], d[i])]++;
  }

  rep(i, n) cout << ans[mp(c[i], d[i])] << endl;

}


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

if x == 0:
    if y == 100:
        print(101)
    else:
        print(y)
if x == 1:
    if y == 100:
        print(10100)
    else:
        print(y*100)
if x == 2:
    if y == 100:
        print(1010000)
    else:
        print(y*10000)

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

struct Card{char suit, value;};

void bubbleSort(struct Card c[],int n){
    for (int i = 0; i < n; i++) {
        for (int k = n - 1; i < k; k--) {
            if(c[k].value < c[k-1].value){
                Card t = c[k];c[k] = c[k-1];c[k-1] = t;
            }
        }
    }
}

void selectionSort(struct Card c[],int n){
    for (int i = 0; i < n; i++) {
        int minj = i;
        for (int k = i+1; k < n; k++) {
            if (c[k].value < c[minj].value) {
                minj = k;
            }
        }
        struct Card t = c[i];c[i] = c[minj];c[minj] = t;
    }
}

void print(struct Card c[], int n){
    for (int i = 0; i < n; i++) {
        if(i)cout<<" ";
        cout<<c[i].suit<<c[i].value;
    }
    cout<<endl;
}

bool isStable(struct Card c1[], struct Card c2[], int n){
    for (int i = 0; i < n; i++) {
        if (c1[i].suit != c2[i].suit) {
            return false;
        }
    }
    return true;
}


int main(){
    Card c1[100],c2[100];
    int n;
    
    cin>>n;
    for (int i = 0; i < n; i++) {
        cin >> c1[i].suit>>c1[i].value;
    }
    
    for (int i = 0; i < n; i++) {
        c2[i] = c1[i];
    }
    
    bubbleSort(c1, n);
    selectionSort(c2, n);
    
    print(c1, n);
    cout << "Stable" << endl;
    print(c2, n);
    
    if(isStable(c1, c2, n)){
        cout<<"Stable"<<endl;
    }else{
        cout<<"Not stable"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 1160
#include <iostream>

using namespace std;

int h = 0, w = 0;
char s[51][51];
int checkmine(unsigned, unsigned);

int main() {
	
	int i, j;

	cin >> h >> w;
	for (i = 1; i <= h; i++) {
		for (j = 1; j <= w; j++) {
			cin >> s[j][i];
		}
	}

	for (i = 1; i <= h; i++) {
		for (j = 1; j <= w; j++) {
			int check = checkmine(j, i);
			if (check == -1) {
				cout << "#";
			}
			else {
				char out = '0' + check;
				cout << out;
			}
		}
		cout << endl;
	}

	return 0;
}
int checkmine(unsigned x, unsigned y) {
	int i, j;
	unsigned count = 0;
	if (s[x][y] == '#')return -1;
	for (i = -1; i <= 1; i++) {
		for (j = -1; j <= 1; j++) {
			if (x + i <= 0 || y + j <= 0)continue;

			if (s[x+i][y+j] == '#')count++;
		}
	}

	return count;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll     = long long;
using pii    = pair<int, int>;
using pll    = pair<ll, ll>;
using vi     = vector<int>;
using vl     = vector<ll>;
using vvi    = vector<vi>;
using vvl    = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int n;
    cin >> n;
    struct in {
        int h, p;
        bool operator<(const in &rhs) const { return h + p < rhs.h + rhs.p; };
    };
    vector<in> hp(n);
    for (int i = 0; i < n; ++i) {
        int h, p;
        cin >> h >> p;
        hp[i] = {h, p};
    }
    sort(hp.begin(), hp.end());
    vvl dp(n + 1, vl(n + 1, INF));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        chmin(dp[i][0], dp[i - 1][0]);
        for (int j = 1; j <= n; ++j) {
            chmin(dp[i][j], dp[i - 1][j]);
            if (dp[i - 1][j - 1] <= hp[i - 1].h) {
                chmin(dp[i][j], dp[i - 1][j - 1] + hp[i - 1].p);
            }
        }
    }
    int ret = 0;
    for (int j = 0; j <= n; ++j) {
        if (dp[n][j] != INF) {
            chmax(ret, j);
        }
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 195968
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    int n;
    while(cin>>n,n){
        string Name[10];
        double w[10],s[10];
        for(int i=0;i<n;i++)cin>>Name[i]>>w[i]>>s[i];
        vector<int>p(n),ans;
        for(int i=0;i<n;i++)p[i]=i;
        double mi=1<<25;
        do{
            double gu=0.0,gl=0.0,t=0.0;
            bool flag=true;
            for(int i=0;i<n;i++){
                int pos=p[i];
                gu+=(n-i)*w[pos];gl+=w[pos];
                if(s[pos]<t){
                    flag=false;
                    break;
                }
                t+=w[pos];

            }
            if(flag){
                double g=gu/gl;
                if(mi>g){
                    ans=p;
                    mi=g;
                }
            }
        }while(next_permutation(p.begin(),p.end()));

        reverse(ans.begin(),ans.end());
        for(int i=0;i<n;i++)cout<<Name[ans[i]]<<endl;
    }
    return 0;
}

Measured memory_bytes: 1248
// Knapsack 1
#include <climits>
#include <iostream>
#include <vector>
#define ll long long
using namespace std;

ll n, w;
ll dp[105][100005];
ll arr[105][2];

ll value(ll x, ll w)
{
    if (dp[x][w] != -1)
        return dp[x][w];
    if (x == n || w == 0)
    {
        return 0;
    }
    if (arr[x][0] > w)
    {
        dp[x][w] = value(x + 1, w);
        return dp[x][w];
    }
    dp[x][w] = max(value(x + 1, w - arr[x][0]) + arr[x][1], value(x + 1, w));
    return dp[x][w];
}

void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= w; j++)
            cout << dp[i][j];
        cout << endl;
    }
}

int main()
{
    cin >> n >> w;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i][0] >> arr[i][1];
    }
    for (int i = 0; i < 105; i++)
    {
        for (int j = 0; j <= w; j++)
            dp[i][j] = -1;
    }
    cout << value(0, w);
}

Measured memory_bytes: 82304
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N; cin>>N;
  vector<int> S(N);
  for(int i=0; i<N; i++){
    cin>>S.at(i);
  }
  sort(S.begin(),S.end());
  int Ans=1;
  for(int i=0; i<S.size()-1; i++){
    if(S.at(i)!=S.at(i+1))
      Ans++;
    else continue;
  }
  cout<<Ans<<endl;
}

Measured memory_bytes: 3560
from statistics import mean, median,variance,stdev
import numpy as np
import sys
import math
import fractions
import itertools

def j(q):
    if q==1: print("Yes")
    else:print("No")
    exit(0)


def ct(x,y):
    if (x>y):print("")
    elif (x<y): print("")
    else: print("")

def ip():
    return int(input())

def swap(s,pos):
    s[pos]-=1
    s[pos+1]+=1
    print(s)
    if pos == n-2: return s
    if s[pos+2] == 0: swap(s,pos+1)
    return s


#n = ip()                              #入力整数1つ
#h,w= (int(i) for i in input().split())      #入力整数横2つ
#n,x,y = (int(i) for i in input().split())    #入力整数横3つ
#n,m,x,y= (int(i) for i in input().split())  #入力整数横4つ
#a = [int(i) for i in input().split()]        #入力整数配列
a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)

#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
for i in range(0,len(a),2):
    print(a[i],end = '')


Measured memory_bytes: 14784
#include <cstdio>

#include <algorithm>
#include <functional>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 1010, P = 1000000007;

int n, m;
int r[N], c[N];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &r[i]);
  for (int i = 1; i <= m; ++i)
    scanf("%d", &c[i]);
  sort(r + 1, r + n + 1, greater<int>());
  sort(c + 1, c + m + 1, greater<int>());
  int a = 0, b = 0, ans = 1;
  for (int x = n * m; x; --x) {
    if (x == r[a + 1]) {
      ++a;
      if (x == c[b + 1])
        ++b;
      else {
        ans = ans * (ll)b % P;
      }
    } else if (x == c[b + 1]) {
      ++b;
      ans = ans * (ll)a % P;
    } else {
      ans = ans * (ll)(a * b - (n * m - x)) % P;
    }
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
	ll a=0,b=getchar(),c=1;
	while(!isdigit(b))c=b=='-'?-1:1,b=getchar();
	while(isdigit(b))a=a*10+b-'0',b=getchar();
	return a*c;
}
const ll mod=998244353;
ll n,ri,le,s0,f[1000005];
struct node{
	int x,y;
	bool operator<(node b)const{
		return x-y>b.x-b.y;
	}
}a[1000005];
char s[1000005];
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		ll l=0,r=0;
		scanf("%s",s+1);
		for(int j=1;s[j];j++)
			if(s[j]=='(')l++;
			else{
				if(l)l--;
				else r++;
			}
		if(!l and r)ri+=r;
		else if(l and !r)le+=l;
		else a[i]=(node){l,r};	
		s0+=l-r;
	}
	if(s0!=0)return puts("No"),0;
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		if(le<a[i].y)
			return puts("No"),0;
		le-=a[i].y-a[i].x;
	}
	if(le!=ri)puts("No");
	else puts("Yes");
	return 0;
}

Measured memory_bytes: 11468
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, A;
  cin >> N >> A;
 
  if ( N / 500 == 0 ) {
    cout << "Yes" << endl;
  }
  
  else if ( N % 500 <= A) {
    cout << "Yes" << endl;
  }
  
  else {
    cout << "No" << endl;
  } 
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  unsigned long int N,D,cnt=0,i;
  long int X,Y;

  //input
  scanf("%ld %ld",&N,&D);
  for(i=0;i<N;i++)
  {
    scanf("%lu %lu",&X,&Y);
    //printf("%ld \n",X*X);
    if(D*D>=X*X+Y*Y)
    {
      cnt++;
    }
  }
  //output
  printf("%d",cnt);
    
  return 0;
}

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

using namespace std;

int main(void) {
    int h[3][2], m[3][2], s[3][2], sec[3][2], diff;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 2; j++)
            cin >> h[i][j] >> m[i][j] >> s[i][j];
    
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 2; j++)
            sec[i][j] = 3600 * h[i][j] + 60 * m[i][j] + s[i][j];
    
    for (int i = 0; i < 3; i++) {
        diff = sec[i][1] - sec[i][0];
        cout << diff / 3600 << " " << (diff % 3600) / 60 << " " << diff % 60 << endl;
    }
    
    return 0;
}


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

int main() {
	string s; cin >> s;
	int ans;
	string op="+++";
	vector<int> num(4);
	for (int i = 0; i < 4; i++) {
		num[i] = s[i] - '0';
	}

	for (int bit = 0; 1 << 3;bit++) {
		ans = num[0];
		for (int i = 0; i < 3;i++) {
			if (bit & (1 << i)) {
				ans += num[i + 1];
				op[i] = '+';
			}
			else {
				ans -= num[i + 1];
				op[i] = '-';
			}
		}
		if (ans == 7) {
			break;
		}
	}
	for (int i = 0; i < 3; i++)cout << num[i] << op[i];
	cout << num[3] << "=7" << endl;

	return 0;
}


Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char s[16],s0[16]={'C', 'O', 'D', 'E', 'F', 'E', 'S', 'T', 'I', 'V', 'A', 'L', '2', '0', '1', '6'};
	gets(s);
	int x=0;
	for(int i=0;i<16;i++)
	if(s[i]!=s0[i]) x++;
	cout<<x;
}

Measured memory_bytes: 256
from sys import stdin
def solve():
    n = int(stdin.readline())
    ans = 0
    if n == 1: return 0
    prime = {}
    i = 2
    while i**2 <= n:
        if n%i != 0:
            i += 1
            continue
        ex = 0
        while n%i == 0:
            ex += 1
            n //= i
        prime[i] = ex
    if n != 1: prime[n] = 1
    for key in prime:
        cur = 1
        while prime[key] >= cur:
            ans += 1
            prime[key] -= cur
            cur += 1
    return ans

print(solve())


Measured memory_bytes: 63012