akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef pair<double,ll> pdl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<pdd> vdd;
typedef vector<pdi> vdi;
typedef vector<pdl> vdl;
#define fi first
#define se second
const ll INFLL=LLONG_MAX;
const int INF=INT_MAX;
const ll MAXLL=0x3f3f3f3f3f3f3f3f;
const int MAX=0x3f3f3f3f;
#define eb emplace_back
#define emp emplace
#define mp(a,b) make_pair(a,b)
template<class T> using min_heap=priority_queue<T,vector<T>,greater<T> >;
template<class T>
void sort(vector<T>& v){
	sort(v.begin(),v.end());
}
template <class T, class U>
void sort(vector<T>& v,U func){
	sort(v.begin(),v.end(),func);
}
template<class T>
void rsort(vector<T>& v){
	sort(v.rbegin(),v.rend());
}
template <class T>
int lb_index(vector<T>& v,T k){
	return lower_bound(v.begin(),v.end(),k)-v.begin();
}
template <class T>
int ub_index(vector<T>& v,T k){
	return upper_bound(v.begin(),v.end(),k)-v.begin();
}
template<class T>
bool is_sorted(vector<T>& v){
	return is_sorted(v.begin(),v.end());
}
template<class T>
bool sorted(vector<T>& v){
	return is_sorted(v);
}

void solve(){
	ll n;
	cin>>n;
	vl v(n);
	for(ll i=0;i<n;i++)cin>>v[i];
	rsort(v);
	priority_queue<ll>pq;
	pq.emp(v[0]);
	ll ans=0;
	for(ll i=1;i<n;i++){
		ans+=pq.top();
		ll u=pq.top();
		pq.pop();
		pq.emp(v[i]);
		pq.emp(v[i]);
	}
	cout<<ans<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	int numberofsubtestcases=1;
//	cin>>numberofsubtestcases;
	while(numberofsubtestcases--){
		solve();
	}
}

Measured memory_bytes: 6932
#include <bits/stdc++.h>
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define IFOR(i, m, n) for(int i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
const ll INF = 1e18;
/* テンプレートここまで */

int main() {
  ll x,y,z; cin >> x >> y >> z;
  ll k = 1;
  while(true){
    if(k*y+(k+1)*z<=x && x < (k+1)*y+(k+2)*z){
      cout << k << endl;
      return 0;
    }
    k++;
  }
}

Measured memory_bytes: 256
#include <stdio.h>

int a[1000000], b[1000000];

int main() {

	int i, n ;
	long long int sum=0;

	scanf("%d", &n);

	
	for (i = 0; i < n + 1; i++) scanf("%d", &a[i]);
	for (i = 0; i < n; i++)scanf("%d", &b[i]);
	for (i = n - 1; i >= 0; i--) {
		if (a[i + 1] >= b[i]) {
			sum += b[i];
			b[i] = 0;
		}
		else {
			sum += a[i + 1];
			b[i] -= a[i + 1];
		}

		if (a[i] >= b[i]) {
			sum += b[i];
			a[i] -= b[i];
		}
		else {
			sum += a[i];
			a[i] = 0;
		}
	}

	printf("%lld\n", sum);
	return 0;
}

Measured memory_bytes: 4608
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;
using ll = long long;

int main(){
    int x;
    cin >> x;
    bool is_prime=false;
    while(1){
        bool flag=0;
        for(int i=2;i*i<x;i++){
            if(x%i==0) flag=1;
        }
        if(flag==false){
            cout << x << endl;
            return 0;
        }
        x++;
    }
    return 0;
}

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

int main() {
    ios::sync_with_stdio(false);
    int N, W;
    cin >> N >> W;
    int w[N + 1], v[N + 1];
    map<int, vector<int> > dict;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
        dict[w[i]].push_back(v[i]);
    }
    for (int i = 0; i <= 3; i++) {
        vector<int>& v = dict[w[1] + i];
        sort(v.begin(), v.end(), greater<int>());                           // descending order
    }
    int max_value = 0;
    for (int a = 0; (size_t)a <= dict[w[1]].size(); a++) {                  // 'a': qty of w1
        if (a * w[1] > W)
            break;
        int value_a = 0;
        for (int i = 0; i < a; i++)
            value_a += dict[w[1]][i];
        for (int b = 0; (size_t)b <= dict[w[1] + 1].size(); b++) {          // 'b': qty of w1+1
            if (a * w[1] + b * (w[1] + 1) > W)
                break;
            int value_b = 0;
            for (int i = 0; i < b; i++)
                value_b += dict[w[1] + 1][i];
            for (int c = 0; (size_t)c <= dict[w[1] + 2].size(); c++) {      // 'c': qty of w1+2
                if (a * w[1] + b * (w[1] + 1) + c * (w[1] + 2) > W)
                    break;
                int value_c = 0;
                for (int i = 0; i < c; i++)
                    value_c += dict[w[1] + 2][i];
                for (int d = 0; (size_t)d <= dict[w[1] + 3].size(); d++) {  // 'd': qty of w1+3
                    if (a * w[1] + b * (w[1] + 1) + c * (w[1] + 2) + d * (w[1] + 3) > W)
                        break;
                    int value_d = 0;
                    for (int i = 0; i < d; i++)
                        value_d += dict[w[1] + 3][i];
                    max_value = max(max_value, value_a + value_b + value_c + value_d);
                }
            }
        }
    }
    cout << max_value << "\n";

    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [int(i) for i in input().split()]

A.insert(0,0)
A.append(0)

S = 0

for i in range(1,N+2):
    S += abs(A[i]-A[i-1])

for i in range(1,N+1):
    print(S + abs(A[i-1]-A[i+1]) - abs(A[i-1]-A[i]) - abs(A[i]-A[i+1]))


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

using namespace std;

int main() {
    string S;
    cin >> S;
    bool easy = true;
    int N = S.size();
    for(int i = 0; i < N; i++){
        if(i % 2 == 0 and S.at(i) == 'L') easy = false;
        else if(i % 2 == 1 and S.at(i) == 'R') easy = false;
    }

    if(easy) puts("Yes");
    else puts("No");
}

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

using namespace std;

char s[123];

int main() {
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  int a, b;
  scanf("%d%d", &a, &b);
  scanf("%s", s);
  int n = strlen(s);
  if (n != a + b + 1) {
    puts("No");
    return 0;
  }
  for (int i = 0; i < n; i++) {
    if (i == a && s[i] != '-') {
      puts("No");
      return 0;
    }
    if (i != a && (s[i] < '0' || s[i] > '9')) {
      puts("No");
      return 0;
    }
  }
  puts("Yes");
  return 0;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
//using namespace std;
//#define ll long long
//#define pb push_back
//#define F first
//#define S second
//const int mod = 1e9+7, A = 1e3+5;
//int main()
//{
//	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//	return 0;
//}
#include <iostream>
#include <map>
#include <algorithm>
#include <cmath>
#define ll long long
#define mod 1000000007
using namespace std;
 
ll n, arr[10004];
map<ll, ll>mp;
 
ll fp(ll base, ll power)
{
    if (power == 0) return 1;
    ll ans = fp(base, power / 2);
    ans = (ans * ans) % mod;
    if (power % 2 != 0)
        ans = (ans * (base % mod)) % mod;
    return ans;
}
 
void get_max(ll key, ll val)
{
    map<ll, ll>::iterator it = mp.find(key);
    if (it == mp.end())
        mp.insert({ key,val });
    else
        it->second = max(it->second, val);
}
 
void get_factors(ll x)
{
    for (ll i = 2; i*i <= x; i++)
    {
        if (x % i == 0)
        {
            ll power = 0;
            while (x % i == 0)
            {
                power++;
                x /= i;
            }
            get_max(i, power);
        }
    }
    if (x > 1)
        get_max(x, 1);
}
 
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        get_factors(arr[i]);
    }
    ll lcm = 1, ans = 0;
    for (auto i : mp)
        lcm = (lcm * fp(i.first, i.second)) % mod;
    for (int i = 0; i < n; i++)
        ans = (ans + ((lcm * fp(arr[i], mod - 2)) % mod)) % mod;
    cout << ans % mod << '\n';
    return 0;
}

Measured memory_bytes: 896
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	cnt := 0
	ans := 0
	for i:=1; i<=n; i+=2 {
		cnt = 0
		for j :=1; j<=n; j+=2 {
			if i%j == 0 {
				cnt++
			}
		}
		if cnt == 8 {
			ans++
		}
	}
	fmt.Println(ans)
}

Measured memory_bytes: 512
n = int(input())
s = [int(input()) for _ in range(n)]

total = sum(s)
s.sort()
if total % 10 != 0:
    print(total)
else:
    for i in range(n):
        if (total - s[i]) % 10 != 0:
            print(total - s[i])
            exit()
    print(0)

Measured memory_bytes: 3060
//
// Created by tac on 2016/10/18.
//

#include <cstdlib>
#include <cmath>
#include <iostream>
#include <iomanip>

namespace {

double distance(double x1, double y1, double x2, double y2) {
    return std::sqrt(std::pow(x2 - x1, 2) + std::pow(y2 - y1, 2));
}

}

int main() {
    double x1, x2, y1, y2;

    std::cin >> x1 >> x2 >> y1 >> y2;
    std::cout << std::fixed << std::setprecision(8) << distance(x1, x2, y1, y2);

    return EXIT_SUCCESS;
}

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

int main() {
    long H, W;
    cin >> H >> W;

    if (H == 1 || W == 1) {
        cout << 1;
        return 0;
    }

    long long evenNum, oddNum, total;

    oddNum  = H / 2;
    evenNum = (H % 2 == 0) ? oddNum : oddNum + 1;

    total = (W / 2 + ((W % 2 == 0) ? 0 : 1)) * evenNum + (W / 2) * oddNum;

    cout << total;
    
    return 0;
}

Measured memory_bytes: 384
n = int(input())
data = [0]*(10**6+2)
data[n] = 1
ans = 1
while True:
    if n%2 == 0:
        n //= 2
        ans += 1
        if data[n]:
            print(ans)
            break
        else:
            data[n] = 1
    else:
        n = 3*n + 1
        ans += 1
        if data[n]:
            print(ans)
            break
        else:
            data[n] = 1
    

Measured memory_bytes: 10868
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll mod = 1000000007;

ll r(ll x, ll y) {
  if (y == 0) return 1;
  else if (y % 2 == 0) return r(x, y/2) * r(x, y/2) % mod;
  else return x * r(x, (y-1)/2) % mod * r(x, (y-1)/2) % mod;
}
  
int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<bool> c(n);
  for (int i = 0; i < n; i++) {
    if (s[i] == 'R') {
      c[i] = 1;
    }
    else {
      c[i] = 0;
    }
  }
  vector<int> b(n, 0);
  int k = 0;
  while (k < n) {
    if (c[k]) {
      int j = k + 1;
      while (c[j]) {
        j++;
      }
      int sa = j - k;
      if (sa % 2 == 0) {
        b[j] += ((sa) / 2);
        b[j - 1] += ((sa) / 2);
      }
      else {
        b[j] += ((sa) / 2);
        b[j - 1] += ((sa + 1) /2);
      }
      k = j;
    }
    else {
      int j = k + 1;
      while (j < n && !c[j]) {
        j++;
      }
      int sa = j -k;
      if (sa % 2 == 0) {
        b[k-1] += ((sa) / 2);
        b[k] += ((sa) / 2);
      }
      else {
        b[k-1] += ((sa) / 2);
        b[k] += ((sa + 1) /2);
      }
      k = j;
    }
  }
  for (int i = 0; i < n-1; i++) {
    cout << b[i] << ' ';
  }
  cout << b[n-1] <<endl;
} 


Measured memory_bytes: 1024
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// get a integer
		int N = sc.nextInt();
		int K = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();
		
		int total = (N < K )? N*X: (X*K) + Y * (N-K);
		
		System.out.println(total);
	}
}

Measured memory_bytes: 23380
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
import random
sys.setrecursionlimit(4100000)


D = int(input())
C = list(map(int,input().split()))

S = []
for i in range(D):
    tmp = list(map(int,input().split()))
    S.append(tmp)


class Schejule:

    def __init__(self, sche):
        self.base = sche
        self.last = [0] * 26
        self.y = 0

    def get_score(self):
        self.y = 0
        for d in range(D):
            self.y += S[d][self.base[d]]

        for d in range(D):
            self.last[self.base[d]] = d + 1

            for j in range(26):
                self.y -= C[j] * (d+1 - self.last[j])

    def change_one(self, day, to):

        org = self.base[day]

        # 差分
        div = 0

        # その日の満足度の変化
        div += S[day][to] - S[day][org]

        # 損失
        org_loss = 0
        cha_loss = 0

        org_last = 0
        cha_last = 0
        for d in range(D):
            if self.base[d] == org:
                org_last = d + 1
            elif self.base[d] == to:
                cha_last = d + 1

            org_loss +=  C[org] * (d+1 - org_last)
            cha_loss +=  C[to ] * (d+1 - cha_last)

        def_loss = cha_loss + org_loss


        org_loss = 0
        cha_loss = 0

        org_last = 0
        cha_last = 0
        for d in range(D):
            if d != day:
                if self.base[d] == org:
                    org_last = d + 1
                elif self.base[d] == to:
                    cha_last = d + 1
            else:
                cha_last = d+1

            org_loss +=  C[org] * (d+1 - org_last)
            cha_loss +=  C[to ] * (d+1 - cha_last)

        aft_loss = cha_loss + org_loss


        # 全体の差分
        div -= aft_loss - def_loss

        # ε-greedy
        if div > 0 or random.randint(0, 9) >= 8:
            next_plan = self.base
            next_plan[day] = to

            sche_next = Schejule(next_plan)
            sche_next.y = self.y + div

            return sche_next
        else:
            return self



T = [0] * D

for i in range(D):
    max_day = 0
    for j in range(26):
        if S[i][max_day] < S[i][j]:
            max_day = j
    T[i] = max_day


sche_base = Schejule(T)
sche_base.get_score()


best_score = sche_base.y
best_set = sche_base.base.copy()

#print(sche_base.y)

#print(*sche_base.base)

for i in range(8000):
    d = random.randint(0, D - 1)
    t = random.randint(0, 26 - 1)

    sche_base  = sche_base.change_one(d, t)

    if best_score < sche_base.y:
        best_score = sche_base.y
        best_set = sche_base.base.copy()
        #print("updated!!!!")

    #print("now: ", sche_base.y, "->", *sche_base.base)
    #print("best:", best_score, "->", *best_set)
    #print("\n")
    #print(*sche_base.base)

    #print(sche_base.y)

for i in range(D):
    print(best_set[i] + 1)










Measured memory_bytes: 82136
from collections import Counter
H,W,M=map(int,input().split())
Hcnt=[0]*H
Wcnt=[0]*W
hw=[]
hwset=set()
for i in range(M):
    h,w=map(lambda x:int(x)-1,input().split())
    hw.append((h,w))
    hwset.add((h,w))
    Hcnt[h]+=1
    Wcnt[w]+=1

mH=max(Hcnt)
mW=max(Wcnt)

max_H,max_W=set(),set()
for i in range(H):
    if Hcnt[i]==mH:
        max_H.add(i)
for i in range(W):
    if Wcnt[i]==mW:
        max_W.add(i)
        
if len(max_H)*len(max_W)>M:
    print(mH+mW)
    exit()

for i in max_H:
    for j in max_W:
        if not (i,j) in hwset:
            print(mH+mW)
            exit()
print(mH+mW-1)

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

typedef long long ll;

const int N = 200000 + 5;
const ll MOD = 1e9 + 7;

ll n, m, k;
ll fact[N], invFact[N], ans;

void exgcd(ll a, ll b, ll &g, ll &x, ll &y) {
    if (!b) g = a, x = 1, y = 0;
    else exgcd(b, a % b, g, y, x), y -= x * (a / b);
}

inline ll inv(ll a) {
    ll g, res, tmp;
    exgcd(a, MOD, g, res, tmp);
    return res % MOD;
}

inline void init() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    invFact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}

inline ll C(int n, int m) {
    // if (m == 0) return 1;
    if (m > n) return 0;
    return fact[n] * (invFact[m] * invFact[n - m] % MOD) % MOD;
}

int main() {
    init();
    scanf("%lld %lld %lld", &n, &m, &k);
    for (ll i = 1; i <= n; i++) {
        ll tmp = (n - i) * m % MOD * m % MOD * C(n * m - 2, k - 2) % MOD * i % MOD;
        (ans += tmp) %= MOD;
    }
    for (ll i = 1; i <= m; i++) {
        ll tmp = (m - i) * n % MOD * n % MOD * C(n * m - 2, k - 2) % MOD * i % MOD;
        (ans += tmp) %= MOD;
    }
    printf("%lld\n", ans % MOD);
    return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
#define N 200050
#define add(u,v) to[++top]=head[u],head[u]=top,w[top]=v
#define For(x) for(int h=head[x],o=w[h];h;o=w[h=to[h]]) 
using namespace std;
int top=0,head[N<<1],to[N<<1],w[N<<1];
int f[N],g[N][2],q[N<<2],l,r,d[N],tot,n,m,x;
char s[N];
struct dat{
	int u,v;
	bool operator <(dat b) const{
		if (u==b.u) return v<b.v;
		return u<b.u;
	}
	bool operator ==(dat b) const{
		return (u==b.u&&v==b.v);
	}
}a[N];
inline void read(int &x){
	x=0;
	char ch=getchar();
	while (!isdigit(ch)) ch=getchar();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); 
} 
int main(){
	read(n),read(m),scanf("%s",s);
	for (int i=1;i<=n;i++) if (s[i-1]=='A') f[i]=1;
	for (int i=1;i<=m;i++) read(a[i].u),read(a[i].v);
	sort(a+1,a+m+1);
	
	if (a[1].u!=a[1].v){
		g[a[1].u][f[a[1].v]]++,g[a[1].v][f[a[1].u]]++;
		add(a[1].u,a[1].v),add(a[1].v,a[1].u);
		
	}
	else add(a[1].u,a[1].v),g[a[1].u][f[a[1].v]]++;
	
	for (int i=2;i<=m;i++) if (!(a[i]==a[i-1])){
		if (a[i].u!=a[i].v){
			g[a[i].u][f[a[i].v]]++,g[a[i].v][f[a[i].u]]++;
			add(a[i].u,a[i].v),add(a[i].v,a[i].u);
			
		}
		else add(a[i].u,a[i].v),g[a[i].u][f[a[i].v]]++;
	}
	
	l=0,r=-1,tot=n;
	for (int i=1;i<=n;i++) if (g[i][0]*g[i][1]==0) q[++r]=i,d[i]=1;
	while (l<=r){
		x=q[l++],tot--;
		For(x) if (!d[o]){
			g[o][f[x]]--;
			if (g[o][f[x]]==0) d[o]=1,q[++r]=o;
		}
	}
	
	if (tot) printf("Yes\n");else printf("No\n");
}

Measured memory_bytes: 12416
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>

using namespace std;

const unsigned long long base = (unsigned long long) 1e9 + 7;

inline unsigned long long Hash( int x, int y ) {
	return base * x + y;
}

int main( void ) {
	int h, w, n;
	scanf("%i %i %i", &h, &w, &n);
	
	unordered_set<unsigned long long> Q;
	
	vector<int> X(n), Y(n);
	for( int i = 0; i < n; i++ ) {
		scanf("%i %i", &X[i], &Y[i]);
		Q.insert(Hash(X[i], Y[i]));
	}
	
	unordered_set<unsigned long long> seen;
	
	long long ans[10] = {0};
	for( int i = 0; i < n; i++ ) {
		for( int x = 0; x <= 2; x++ ) {
			for( int y = 0; y <= 2; y++ ) {
				int sx = X[i] - x, sy = Y[i] - y;
				if( (sx >= 1) && (sy >= 1) && (sx+2 <= h) && (sy+2 <= w) && !seen.count(Hash(sx, sy)) ) {
					seen.insert(Hash(sx, sy));
					
					int count = 0;
					for( int c = 0; c < 3; c++ ) {
						for( int k = 0; k < 3; k++ ) {
							count += Q.count(Hash(sx+c, sy+k));
						}
					}
										
					ans[count]++;
				}
 			}
		}
	}
	
	ans[0] = (long long) (h - 2) * (w - 2);
	for( int i = 1; i <= 9; i++ ) {
		ans[0] -= ans[i];
	}
	
	for( int i = 0; i <= 9; i++ ) {
		printf("%lld\n", ans[i]);
	}
	
	return 0;
}

Measured memory_bytes: 41488
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i = 0; i < (n); i++)
#define FORR(x, arr) for(auto& x:arr)
#define ITR(x, c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())
typedef long long ll;
typedef pair<int, int> P;
 
int n, k;
 
int main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin >> n >> k;
	int cur = 1;
	FOR(i, n) {
		if (cur <= k) cur *= 2;
		else cur += k;
	}
	cout << cur << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
char b;
  cin>>b;
  if(b=='A'){
    cout<<'T'<<endl;
  }
  else if(b=='C'){
    cout<<'G'<<endl;
  }
  else if(b=='G'){
    cout<<'C'<<endl;
  }
  else if(b=='T'){
    cout<<'A'<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) REP(i, 0, n)
#define REP(i, l, r) for (int i = l; i < r; i++)
using namespace std;
typedef pair<int, int> P;
struct edge {
	int to, cost;
};
class dijkstra {
  private:
	int V;
	int d[100002];
	priority_queue<P, vector<P>, greater<>> que;

  public:
    dijkstra(int v, int s, vector<edge> G[]) {
        V = v;
        update(s, G);
    }

    void update(int s, vector<edge> G[]) {
        fill(d, d + V + 1, 100000000000ll);
        d[s] = 0;
        que.push(make_pair(0, s));
        while (!que.empty()) {
            P p = que.top();
            que.pop();
            int v = p.second;
            if (d[v] < p.first)
                continue;
            rep(i, G[v].size()) {
                edge e = G[v][i];
                if (d[e.to] > d[v] + e.cost) {
                    d[e.to] = d[v] + e.cost;
                    que.push(make_pair(d[e.to], e.to));
                }
            }
        }
    }

	int find(int e) {
		return d[e];
	}
};

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

int lcm(int a, int b) {
	return a * b / gcd(a, b);
}

bool prime(int a) {
	if (a == 1)
		return false;
	for (int i = 2; i * i <= a; i++) {
		if (a % i == 0)
			return false;
	}
	return true;
}

class Union_Find {
  private:
	vector<int> t, s;

  public:
	Union_Find(int max_length) {
		rep(i, max_length + 1) {
			t.push_back(i);
			s.push_back(1);
		}
	}

	void Union(int x, int y) {
		if (same(x, y))
			return;
		int tx = Find(x), ty = Find(y);
		if (s[tx] < s[ty]) {
			s[ty] += s[tx];
			t[tx] = ty;
		}
		else if (s[tx] > s[ty]) {
			s[tx] += s[ty];
			t[ty] = tx;
		}
		else if (tx > ty) {
			t[tx] = ty;
			s[ty] += s[tx];
		}
		else {
			t[ty] = tx;
			s[tx] += s[ty];
		}
	}

	int Find(int n) {
		if (t[n] == n)
			return n;
		else
			return t[n] = Find(t[n]);
	}

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

	int get_Size(int a) {
		return s[a];
	}
};

vector<int> primeFactorization(int n) {
	vector<int> re;
	int cnt = 2;
	while (n != 1) {
		if (n % cnt != 0) {
			cnt++;
			continue;
		}
		n /= cnt;
		re.push_back(cnt);
	}
	return re;
}

signed main() {
    int n,p[20],ans=0;
    cin>>n;
    rep(i,n){
        cin>>p[i];
        if(i>1){
            int a[3];
            a[0]=p[i-2];
            a[1]=p[i-1];
            a[2]=p[i];
            sort(a,a+3);
            if(a[1]==p[i-1])ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string S, T;
    cin >> S >> T;
    for (int i = 0; i < S.size(); i++) {
        if (S == T) {
            cout << "Yes" << endl;
            return 0;
        }
        S = S.substr(S.size()-1, 1) + S.substr(0, S.size()-1);
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.algorithm, std.string, std.conv, std.array, std.range, std.math;
int read() { return readln.chomp.to!int; }
int[] reads() { return readln.split.to!(int[]); }

int Ceil(int x, int y) {
    return x / y + !!(x % y);
}

void solve() {
    int n, k; readf("%d %d\n", &n,&k);
    int[] a = reads();
    writeln(1 + Ceil(n-k, k-1));
}

void main() {
    solve();
    readln;
}

Measured memory_bytes: 3972
#include<stdio.h>

void selectionSort(int A[],int N){
  int i,j,temp,cnt=0,minj;

  for(i=0;i<N-1;i++){
    minj=i;
    for(j=i;j<N;j++){
      if(A[j]<A[minj]){
        minj=j;}
    }
      temp=A[i];
        A[i]=A[minj];
        A[minj]=temp;
        if(i != minj) cnt++;

    }

    for(i=0;i<N;i++){
      if(i>0) printf(" ");
      printf("%d",A[i]);
        }
    printf("\n");

    printf("%d\n",cnt);
}

  int main(){

    int N,i,A[100];

    scanf("%d\n",&N);
    for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }

   selectionSort(A,N);


    return 0;
  }






Measured memory_bytes: 2124
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef pair<int, int> pii;
typedef pair<double, int> pdi;
typedef long long ll;

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

    int h, w, m; cin >> h >> w >> m;
    vector<int> cnt_y(300000, 0), cnt_x(300000, 0);
    set<pii> s;

    for (int i = 0; i < m; i++)
    {
        int y, x; cin >> y >> x;
        cnt_y[y-1]++; cnt_x[x-1]++;
        s.insert({y-1, x-1});
    }
    int max_y = *max_element(cnt_y.begin(), cnt_y.end());
    int max_x = *max_element(cnt_x.begin(), cnt_x.end());

    vector<int> cand_y, cand_x;
    for (int i = 0; i < cnt_y.size(); i++)
        if (cnt_y[i] == max_y) cand_y.push_back(i);
    for (int i = 0; i < cnt_x.size(); i++)
        if (cnt_x[i] == max_x) cand_x.push_back(i);

    for (int y : cand_y)
        for (int x : cand_x)
            if (!s.count({y, x})) { cout << max_y+max_x << endl; return 0;}
    cout << max_y+max_x-1 << endl;
    return 0;
}


Measured memory_bytes: 23700
int main(void)
{
	long long x,c,a,cnt;
	scanf("%lld",&x);
	c=100;
	cnt=0;
	while(c<x){
		a=c*1/100;
		c=c+a;
		cnt++;
	}
		printf("%lld\n",cnt);
	return 0;
}



Measured memory_bytes: 1712
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <map>

using namespace std;

int main() {
  while (true) {
    int W, Q;
    cin >> W >> Q;
    vector<int> ws(W, -1);
    map<int, pair<int, int>> m; // id = idx, w
    if (W + Q == 0) {
      break;
    }
    for (int i = 0; i < Q; i++) {
      string s;
      cin >> s;
      if (s == "s") {
        int id, w;
        cin >> id >> w;
        if (W == 0) {
          cout << "impossible" << endl;
          continue;
        }
        for (int j = 0; j < W; j++) {
          bool isok = true;
          for (int k = j; k < j + w; k++) {
            if (j >= W) {
              isok = false;
              break;
            }
            if (ws[k] != -1) {
              isok = false;
              break;
            }
          }
          if (isok) {
            cout << j << endl;
            for (int k = j; k < j + w; k++) {
              ws[k] = id;
            }
            m[id] = pair<int, int>(j, w);
            break;
          }
          if (j == W - 1) {
            cout << "impossible" << endl;
          }
        }
      } else {
        int id;
        cin >> id;
        for (int j = 0; j < W; j++) {
          if (ws[j] == id) {
            ws[j] = -1;
          }
        }
      }
    }
    cout << "END" << endl;    
  }
  
  return 0;
}

Measured memory_bytes: 3124
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

class segTree{
    public:
    vector<ll>val;
    vector<ll>sub;
    vector<ll>left;
    vector<ll>right;
    ll offset;
    segTree(ll n, ll initVal = 0){
        offset = 2;
        while(offset < n + 1)offset <<= 1;
        val = vector<ll>(offset * 2, initVal);
        sub = vector<ll>(offset * 2, 0);
        left = vector<ll>(offset * 2, 0);
        right = vector<ll>(offset * 2, 0);
        for(ll i = 0; i < offset; i++){
            left[i + offset] = i;
            right[i + offset] = i;
        }
        for(ll i = offset - 1; i; i--){
            left[i] = left[i * 2];
            right[i] = right[i * 2 + 1];
        }
    }
    void update(ll l, ll r, ll x, ll p = 1){
        if(r < left[p] || right[p] < l)return;
        val[p] += x * (r - l + 1);
        if(left[p] == l && right[p] == r){
            sub[p] += x;
            return;
        }
        update(l, min(r, right[p * 2]), x, p * 2);
        update(max(l, left[p * 2 + 1]), r, x, p * 2 + 1);
    }

    ll get(ll l, ll r, ll p = 1){
        if(r < left[p])return 0;
        if(right[p] < l)return 0;
        // cout << p << ", " << l << " - " << r << endl;
        if(left[p] == l && right[p] == r){
            return val[p];
        }
        if(sub[p]){
            update(left[p*2], right[p*2], sub[p], p * 2);
            update(left[p*2+1], right[p*2+1], sub[p], p * 2 + 1);
            sub[p] = 0;
        }
        ll sum = 0;
        sum += get(l, min(r, right[p * 2]), p * 2);
        sum += get(max(l, left[p * 2 + 1]), r, p * 2 + 1);
        return sum;
    }

    void show(){
        cout << "-----" << endl;
        for(ll i = 1; i < offset * 2; i++){
            if(i < offset)cout << "(" << i << ")[" << val[i] << ", " << sub[i] << "] ";
            else cout << "<" << i - offset << ">[" << val[i] << ", " << sub[i] << "] ";
            ll flg = 1;
            for(ll tmp = i + 1; tmp; tmp /= 2){
                if((tmp & 1) && (tmp > 1))flg = 0;
            }
            if(flg)cout << endl;
        }
        cout << "+++++" << endl;
    }
};

int main(){

    ll N, Q;
    cin >> N >> Q;
    segTree tree(N);
    for(ll i = 0; i < Q; i++){
        ll q;
        cin >> q;
        if(q == 0){
            ll s, t, x;
            cin >> s >> t >> x;
            tree.update(s, t, x);
        }
        else{
            ll s, t;
            cin >> s >> t;
            cout << tree.get(s, t) << endl;
        }
        // tree.show();
    }

    return 0;
}


Measured memory_bytes: 11024
N = int(input())
xy = [[int(i) for i in input().split()] for _ in range(N)]

from itertools import permutations
from math import sqrt

states = list(permutations(list(range(N))))

ans = 0
for state in states:
    dist = 0
    for i,n in enumerate(state):
        if i == 0:
            prev = xy[n]
            continue
        now = xy[n]
        dist += sqrt((prev[0]-now[0]) ** 2+ (prev[1]-now[1]) ** 2)
        prev = now
    ans += dist

ans /= len(states)
print(ans)

Measured memory_bytes: 7972
#include <iostream>
#include <cctype>
#include <string>
#include <vector>
#include <stack>
#include <map>
using namespace std;
map<string, vector<bool>> mp;
int main() {
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		string name;
		int l, u;
		cin >> name >> l >> u;
		vector<bool> v;
		for (int i = 0; i <= 255; i++) {
			v.push_back(l <= i && i <= u);
		}
		mp[name] = v;
	}
	int n;
	cin >> n;
	stack<vector<bool>> s;
	for (int i = 0; i < n; i++) {
		string e;
		cin >> e;
		if (mp.find(e) != mp.end()) {
			s.push(mp[e]);
		}
		else if(isdigit(e[0])) {
			int val = 0;
			for (int j = 0; j < e.size(); j++) {
				val *= 10;
				val += e[j] - '0';
			}
			vector<bool> v;
			for (int j = 0; j <= 255; j++) {
				v.push_back(j == val);
			}
			s.push(v);
		}
		else {
			vector<bool> op1, op2, res;
			op2 = s.top(); s.pop();
			op1 = s.top(); s.pop();
			for (int j = 0; j <= 255; j++) res.push_back(0);
			for (int j = 0; j <= 255; j++) {
				if (!op1[j]) continue;
				for (int k = 0; k <= 255; k++) {
					if (!op2[k]) continue;
					if (e[0] == '+') {
						res[(j + k) % 256] = 1;
					}
					else if (e[0] == '-') {
						res[(j - k + 256) % 256] = 1;
					}
					else if (e[0] == '*') {
						res[j*k % 256] = 1;
					}
					else {
						if (k == 0) {
							cout << "error" << endl;
							return 0;
						}
						res[j / k] = 1;
					}
				}
			}
			s.push(res);
		}
	}
	cout << "correct" << endl;
}


Measured memory_bytes: 3216
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

const int mod = 1e9 + 7;
signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  int a[n + 1], b[m + 1];
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; i++) {
    cin >> b[i];
  }
  int dp[n + 1][m + 1];
  for (int i = 0; i <= n; i++) {
    dp[i][0] = 1;
  }
  for (int i = 0; i <= m; i++) {
    dp[0][i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (a[i] == b[j]) {
        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % mod;
      } else {
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mod) % mod;
      }
    }
  }
  cout << dp[n][m] << "\n";
}



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

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

//=============modinv============================
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
//=================================================


ll N;
vector<vector<ll>> E;
vector<vector<ll>> dp;
ll mod = 1000000007;

ll dfs(ll index, ll par)
{
  ll res = 1;
  for (ll i = 0; i < E.at(index).size(); ++i)
  {
    ll check = E.at(index).at(i);
    if (check == par)
    {
      continue;
    }
    ll temp = dfs(check, index);
    dp.at(index).push_back(temp);
    res += temp;
  }
  if (N != res)
  {
    dp.at(index).push_back(N - res);
  }
  return res;
}

ll calc(vector<vector<ll>> dp)
{
  ll res = 0;
  for (ll i = 0; i < N; ++i)
  {
    if (dp.at(i).size() == 1)
    {
      continue;
    }
    ll temp = modpow(2, N - 1, mod) - 1;
    for (ll j = 0; j < dp.at(i).size(); ++j)
    {
      temp -= modpow(2, dp.at(i).at(j), mod) - 1;
      if (temp < 0)
      {
        temp += mod;
      }
    }
    res = (res + temp) % mod;
  }
  return res;
}

int main()
{
  cin >> N;
  dp = vector<vector<ll>>(N);
  E = vector<vector<ll>>(N);
  ll a, b;
  for (ll i = 0; i < N - 1; ++i)
  {
    cin >> a >> b;
    E.at(a - 1).push_back(b -1);
    E.at(b - 1).push_back(a -1);
  }

  dfs(0, -1);
  // for (ll i = 0; i < N; ++i)
  // {
  //   for (ll j = 0; j < dp.at(i).size(); ++j)
  //   {
  //     cout << dp.at(i).at(j) << ' ';
  //   }
  //   cout << endl;
  // }
  ll ans = calc(dp);
  ll inv2 = modinv(2,mod);
  for (ll i = 0; i < N; ++i)
  {
    ans = (ans * inv2) % mod;
  }
  cout << ans << endl;
}


Measured memory_bytes: 44800
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c) for(int i=0;i<c;++i)

int  main(){
int a,b,c;
cin >> a>> b>> c;
int d = c;
for(int i= 0;i<10;i++){
  d=a*d-b;
 cout << d<< endl;
}
return 0;
}

Measured memory_bytes: 256
//https://atcoder.jp/contests/abc165/tasks/abc165_b
//2020-05-02
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>
#include <iomanip>
using namespace std;

int main()
{
    long long num;
    cin >> num;
    long long tmp = 100;
    int count = 0;
    while(tmp<num){
        tmp += tmp/100;
        count ++;
    }
    cout << count  << endl;
    return 0;
}

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

int main()
{
    int n,t;
    cin>>n>>t;
    vector<int> a(n);
    vector<int> b(n);
    int i,j;
    for(i=0;i<n;i++)cin>>a.at(i)>>b.at(i);
    vector<pair<int,int>> p(n);
    for(i=0;i<n;i++)p.at(i)=make_pair(a.at(i),b.at(i));
    sort(p.begin(),p.end());
    for(i=0;i<n;i++)
    {
        a.at(i)=p.at(i).first;
        b.at(i)=p.at(i).second;
    }
    vector<vector<int>> dp(n,vector<int>(t,0));
    for(i=1;i<n;i++)
    {
        for(j=1;j<t;j++)
        {
            if(j<a.at(i-1))dp.at(i).at(j)=dp.at(i-1).at(j);
            else
            {
                dp.at(i).at(j)=max(dp.at(i-1).at(j-a.at(i-1))+b.at(i-1),dp.at(i-1).at(j));
            }
        }
    }
    int ans=-1;
    for(i=0;i<n;i++)
    {
        int kans=-1;
        for(j=0;j<t;j++)
        {
            if(dp.at(i).at(j)>kans)kans=dp.at(i).at(j);
        }
        if(b.at(i)+kans>ans)ans=b.at(i)+kans;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 35584
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
using namespace std;
using ll = long long;
const ll MOD = 1000000007;

int main()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, 0, n) cin >> a[i];

    // internal
    ll in_cnt = 0;
    rep(i, 0, n)
        rep(j, i+1, n)
        if(a[j] < a[i])
            ++in_cnt;
    in_cnt = (in_cnt * k) % MOD;

    // external
    int cum_cnt = 0;
    int prev_cnt = 0;
    sort(a.begin(), a.end());
    rep(i, 0, n-1)
    {
        int cnt_now;
        if (a[i] < a[i+1])
            cnt_now = i+1;
        else
            cnt_now = prev_cnt;
        cum_cnt += cnt_now;
        prev_cnt = cnt_now;
    }
    ll comb = (k * (k-1)/2) % MOD;
    ll ext_cnt = ((ll)cum_cnt *  comb) % MOD;

    ll ans = (ext_cnt + in_cnt) % MOD;
    // cout << comb << endl;

    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define rep(i,m,n) for(int i=m;i<n;i++)
#define repr(i,n,m) for(int i=n;i>=m ;i--)
#define MOD 1000000007
#define float long double
#define pb push_back
#define mp make_pair
#define pp pop_back
#define pi 3.141592653589793238
#define print(v) for(int i=0;i<v.size();i++) cout<<v[i]<<" ";cout<<endl;
using namespace std;
bool sortbysec(const pair<int,int> &a,
             const pair<int,int> &b)
{
   return (a.second < b.second);
}
int lcm(int a, int b)  
 {  
    return (a*b)/__gcd(a, b);  
 }  
bool sortinrev(const pair<int,int> &a,  
              const pair<int,int> &b)
{
      return (a.first > b.first);
}
void solve()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	int t1=0,t2=0,t3=0;
	rep(i,0,n){
		if(s[i]=='R')
			t1++;
		else if(s[i]=='W')
			t2++;
	}
	bool flag=0;
	rep(i,t1,n){
		if(s[i]=='R')
		{
			t3++;
		}
	}
	cout<<min(t1,min(t2,t3));

}    
signed main()
{
                     // #ifndef ONLINE_JUDGE
                     // freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
                     // #endif 
  int t=1;
 //cin>>t;
  while(t--){
  solve();
  cout<<"\n";
}
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
 return 0;
}  


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

// Simultaneous Equation(0004)
int main()
{
	int a, b, c, d, e, f;
	while (cin >> a >> b >> c >> d >> e >> f) {
		double x = (e*c - b*f) / static_cast<double>(a*e - b*d);
		double y = (d*c - a*f) / static_cast<double>(b*d - a*e);
		
		if (x >= 0)
			x += 0.0005;
		else
			x -= 0.0005;

		if (y >= 0)
			y += 0.0005;
		else
			y -= 0.0005;

		int xx = x * 1000;
		int yy = y * 1000;

		printf("%.3lf %.3lf\n", xx/1000.0, yy/1000.0);

	}
	return 0;
}

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

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

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

    ll N,K; cin >> N >> K;
    vector<ll> H(N);
    for (int i = 0;i < N;i++){
        cin >> H[i];
    }
    sort(H.begin(),H.end());
    ll ans = 0;
    for (int i = 0;i < N-K;i++){
        ans += H[i];
    }

    cout << ans << endl;



    return 0;

}

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

using namespace std;

#define MAX_L 1010
typedef pair<char,int> P;

int L,limit[52],v;
string line[MAX_L];
map<P,int> val;

int change(char x){
  if(islower(x)){
    return x-'a';
  }
  return x-'A'+26;
}

int getDigit(int *l,int *cur){
  int res = 0;
  while(isdigit(line[*l][*cur])){
    res *= 10;
    res += line[*l][*cur]-'0';
    (*cur)++;
  }
  return res;
}

int getArray(int *l,int *cur){
  char x = line[*l][*cur];
  int idx = change(x);
  (*cur) += 2;
  int num;
  if(islower(line[*l][*cur]) || isupper(line[*l][*cur])){
    num = v = getArray(l,cur);
    if(num == -1){ return -1; }
    if(limit[idx] <= num){
      return -1;
    }
    (*cur)++;
    P p = P(x,num);
    if(val.find(p) == val.end()){
      return -1;
    }else{
      return val[P(x,num)];
    }
  }
  num = v = getDigit(l,cur);
  (*cur)++;
  if(limit[idx] <= num){ return -1; }
  else{
    P p = P(x,num);
    if(val.find(p) == val.end()){
      return -1;
    }else{
      return val[P(x,num)];
    }
  }
}

int solve(int l,int cur){
  if(l == L){ return 0; }
  char now = line[l][cur];
  if(islower(now) || isupper(now)){
    char x = line[l][cur];
    int num;
    getArray(&l,&cur);
    int v2 = v;
    if(line[l][cur] == '='){
      cur++;
      if(isdigit(line[l][cur])){
        num = getDigit(&l,&cur);
      }else{
        num = getArray(&l,&cur);
        if(num == -1){ return l+1; }
      }
      if(limit[change(x)] <= v2){ return l+1; }
      val[P(x,v2)] = num;
      return solve(l+1,0);
    }else if(line[l][cur] == '$'){
      limit[change(x)] = v;
      return solve(l+1,0);
    }
  }
  return l+1;
}

void init(){
  val.clear();
  memset(limit,-1,sizeof(limit));
}

int main(){
  while(cin >> line[0],line[0] != "."){
    init();
    line[0] += '$';
    L = 1;
    while(true){
      cin >> line[L];
      if(line[L] == "."){ break; }
      line[L] += '$';
      L++;
    }
    cout << solve(0,0) << endl;
  }
  return 0;
}

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

int f(int a, int hp)
{
    return (hp + a - 1) / a;
}

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (f(b, c) <= f(d, a))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3564
MOD = 998244353
MAX = int(3e5 + 10)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def main():
    N, A, B, K = map(int, input().split())
    ans = 0
    # solve Ax + By = K
    for x in range(N+1):
        By = K - x * A
        if By >= 0 and By % B == 0 and By <= B * N:
            y = By // B
            tmp1 = FACT[N] * INV[x] * INV[N-x] % MOD
            tmp2 = FACT[N] * INV[y] * INV[N-y] % MOD
            ans = (ans + tmp1 * tmp2) % MOD
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 45932
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int n;
long long id[4000];
 long long value[4000];
 long long number[4000];
map<long long,  long long> total;

int main() {
  while(true){
    cin >> n;
    if(n==0){
        return 0;
    }
    vector<long long> v;
    for (int i = 0; i < n; i++) {
        cin >> id[i] >> value[i] >> number[i];
        if(total.find(id[i])==total.end()){
          total.insert(make_pair(id[i], 0));
        }
        total[id[i]] += value[i] * number[i];
        // if (total[id[i]] > 1000000 && find(v.begin(), v.end(), id[i]) == v.end()) {
        //   v.push_back(id[i]);
        // }
    }
    if(!total.empty()) {
        map< long long,  long long>::iterator it = total.begin();
        while (it != total.end()) {
            if ((*it).second >= 1000000) {
                v.push_back((*it).first);
            }
            ++it;
        }
    }
    if (v.empty()) {
        cout << "NA" << endl;
    }
    // for (vector<long long>::iterator it = v.begin(); it != v.end(); ++it) {
    //     cout << *it << endl;
    // }
    vector<long long> used;
    for(int i=0; i<n;i++){
      if(std::find(v.begin(), v.end(), id[i]) != v.end() && std::find(used.begin(), used.end(), id[i]) == used.end()){
        cout << id[i] << endl;
        used.push_back(id[i]);
      }
    }
    v.clear();
    total.clear();
  }
}

Measured memory_bytes: 1344
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<string>
#include<iomanip>

using namespace std;

#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++)
#define repn(i, n) for(int (i) = 1; (i) <= (n); (i)++)
#define repr(i, n) for(int (i) = (n-1); (i) >= 0; (i)--)
#define all(x) (x).begin(), (x).end()
#define lint long long
#define ulint unsigned long long

const int MAX = 100005;
const long long MOD = 1000000007;
long long fac[MAX], facinv[MAX], inv[MAX];

void facinit(){
    fac[0] = fac[1] = 1;
    facinv[0] = facinv[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;
        facinv[i] = facinv[i - 1] * inv[i] % MOD;
    }   
}

long long Perm(long long a, long long b){
    if (a < b) return 0;
    if (a < 0 || b < 0) return 0;
    return fac[a] * facinv[a - b] % MOD;
}

long long Combi(long long a, long long b){
    if (a < b) return 0;
    if (a == 0) return 0;
    if (a < 0 || b < 0) return 0;
    return fac[a] * (facinv[b] * facinv[a - b] % MOD) % MOD;
}


int main(){
    facinit();

    int n; cin >> n;
    vector<int> v; bool f[n]; memset(f, 0, sizeof(f)); int dup;
    rep(i, n+1){
        int a; cin >> a; a--;
        v.push_back(a);
        if(f[a]) dup = a;
        else f[a] = true;
    }
    int p = 0, q = 0, z = 0;
    rep(i, n+1){
        if(v[i] == dup) { z++; continue; }
        if(z == 0) p++;
        else if(z == 2) q++;
    }
    
    repn(k, n+1){
        if(k == 1){
            cout << n << endl;
            continue;
        }
        lint res = Combi(n+1, k) - Combi(p + q, k - 1);
        res = (res + MOD) % MOD;
        cout << res << endl;
    }
}

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

T = [None] * 121
for i in range(121):
    T[i] = i ** 5

ok = False
for a in range(121):
    for b in range(0, 120):
        if T[a] - T[b] == X:
            ok = True
            print(a, b)
            break
    for b in range(0, 121):
        if T[a] + T[b] == X:
            ok = True
            print(a, -b)
            break
    if ok:
        break

Measured memory_bytes: 9208
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    N, M = map(int, readline().split())
    uf = UnionFind(N)
    for _ in range(M):
        A, B = map(int, readline().split())
        uf.union(A-1,B-1)

    g = uf.group_count()
    print(g-1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 12956
import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();
        int D = sc.nextInt();
        boolean takahashi = true;
        while (A > 0 && C > 0) {
            if (takahashi) {
                C -= B;
            } else {
                A -= D;
            }
            takahashi = !takahashi;
        }
        System.out.println(A > 0 ? "Yes" : "No");
    }
}


Measured memory_bytes: 27040
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll MOD = 1e9+7;
const double pi = 3.14159265358979;
using vl = vector<ll>;
# define rep(i, n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
# define reps(i, n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
# define rrep(i, n) for(ll i=((ll)(n)-1); i>=0; --i)
# define rreps(i, n) for(ll i=((ll)(n)); i>0; --i)
# define all(x) (x).begin(), (x).end()

ll A,B;

ll Main() {
    cin >> A >> B;

    cout << A*B << endl;
    return 0;
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 3652
#include <iostream>
using namespace std;
int main(){
    int h, w;
    cin >> h >> w;
    while (!(h == 0 && w == 0)) {
        for (int i = 1; i <= h; i++) {
            for (int j = 1; j <= w; j++) {
                if (i == 1 || i == h || j == 1 || j == w) {
                    cout << "#";
                }
                else {
                    cout << ".";
                }
            }
            cout << endl;
        }
        cout << endl;
        cin >> h >> w;
    }
}


Measured memory_bytes: 3104