akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <map>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

string yn(bool x){
    return x ? "Yes" : "No";
}



int main(){
    int h,w; cin >> h >> w;
    string cell[h];
    rep(i,h) cin >> cell[i];
    
    bool ans[h][w];
    rep(i,h) rep(j,w) ans[i][j] = 1;
    
    rep(i,h){
        bool check = 1;
        
        rep(j,w){
            if(cell[i][j] == '#') check = 0;
        }
        if(check) rep(j,w) ans[i][j] = 0;
    }
    rep(i,w){
        bool check = 1;
        rep(j,h){
            if(cell[j][i] == '#') check = 0;
        }
        if(check) rep(j,h) ans[j][i] = 0;
    }
    
    rep(i,h){
        bool line = 0;
        rep(j,w){
            if(ans[i][j]) {
                cout << cell[i][j];
                line = 1;
            }
            
        }
        if(line)cout << endl;
    }
    

}







Measured memory_bytes: 256
local mmi, mma = math.min, math.max
local mab = math.abs
local n = io.read("*n")
local x, y, h = {}, {}, {}
local iref = 0
for i = 1, n do
  x[i], y[i], h[i] = io.read("*n", "*n", "*n")
  if 0 < h[i] then iref = i end
end
for xi = 0, 100 do
  for yi = 0, 100 do
    local hi = mab(xi - x[iref]) + mab(yi - y[iref]) + h[iref]
    local v = true
    for i = 1, n do
      if mma(0, hi - mab(xi - x[i]) - mab(yi - y[i])) ~= h[i] then
        v = false
        break
      end
    end
    if v then
      print(xi .. " " .. yi .. " " .. hi)
      os.exit()
    end
  end
end


Measured memory_bytes: 376
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;

int main() {
	ll x, y; cin >> x >> y;
	ll ans = 0;
	while (x*(1LL << ans) <= y) ++ans;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#define LEN 100005
#define MAX 1000
typedef struct pp{
  char name[100];
  int t;
}P;
int isEmpty();
void initialize();
int isFull();
void enqueue(P);
P dequeue();
int min(int, int);

int head,tail,n;/*globl avairable*/

 P Q[LEN+1];

int main(){
  int time = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &n, &q);
  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }
  head = 1;
  tail = n + 1;

  while(head != tail){
    u = dequeue();
    c = min(q, u.t);
    u.t -= c;
    time += c;
    if(u.t > 0){
      enqueue(u);
    } else {
      printf("%s %d\n",u.name,time);
    }
  }
  return 0;
}

void initialize(){
  head = 0;
  tail = 0;
}
int isEmpty(){
  return head == tail;
}
int isFull(){
  return head == (tail + 1) % MAX;
}
void enqueue(P x){
  Q[tail] = x;
  tail = (tail + 1) % LEN;
  //if(isFull()){
    /*error over flow*/
  //}
  /*
  Q[tail] = x;
  if(tail + 1 == MAX){
    tail = 0;
  } else {
    tail++;
  }
  */
}

P dequeue(){
  P x;
  /*
  head = (head + 1) % LEN;
  return x;
  */
  //if(isEmpty()){
    /*error under fllow*/
  //}
  x = Q[head];
  head = (head + 1) % LEN;
/*
  if(head + 1 == MAX){
    head = 0;
  }else{
    head++;
  }
  */
  return x;
}
int min(int x, int y){
  return x < y ? x : y;
}

Measured memory_bytes: 10756
#include <iostream>
#include <set>

using namespace std;

int main(void){
  int A, B, K;
  cin >> A >> B >> K;
  //入力終了

  set<int> s;

  //AからK番目以内に大きい数字を見る
  for(int n=A ; n<A+K; n++){
    if(A<=n && n<=B)
      s.insert(n);
  }

  //BからK番目以内に小さい数字を見る
  for(int n=B-K+1; n<=B; n++){
    if(A<=n && n<=B)
      s.insert(n);
  }

  //解答
  for(auto x : s)
    cout << x << endl;
  
  return 0;
}


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

using namespace std;

#define sint(a) scanf("%d",&a)
#define sint2(a,b) scanf("%d %d",&a,&b)
#define sll(a) scanf("%lld",&a)
#define sll2(a,b) scanf("%lld %lld",&a,&b)
#define ll long long
const double pi=acos(-1);
const int maxn=1e6+10;
const int mod=1e9+7;

ll a[maxn];
ll b[maxn];
ll st[maxn];
int main()
{
    int n;
    cin>>n;
    int s=0;
    for(int i=0; i<n; i++)
    {
        cin>>b[i];
        a[b[i]]++;
        if(a[b[i]]==1)
        st[s++]=b[i];
    }
    ll sum=0;
    for(int i=0;i<s;i++)
    {
        int k=st[i];
        sum+=a[k]*(a[k]-1)/2;
    }
    for(int i=0; i<n; i++)
    {
        int k=b[i];
       cout<<sum-(a[k]*(a[k]-1)/2)+((a[k]-1)*(a[k]-2)/2)<<endl;
    }
    return 0;
}


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

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

  // A = 65
  // C = 67
  // Z = 90
  for (int i = 0; i < (int)s.size(); i++) {
    // 0-indexed な文字列Aからの距離
    int x = s.at(i) - 'A';
    // x から n 文字後の文字にする
    // A-Z は26文字で構成されており、26文字を超えた場合は1周するので、26の剰余を求める
    //
    // 仮に s.at(i) = 'A' の場合、A = 65、A = 65 のため、A - A = Aから0文字目となる。
    // 仮に s.at(i) = 'B' の場合、B = 66、A = 65 のため、B - A = Aから1文字目となる。
    // 仮に s.at(i) = 'Z' の場合、Z = 90、A = 65 のため、Z - A = Aから25文字目となる。
    // x は 0-indexed である。
    //
    // 3件目のケースについて、n = 2 の場合、25 + 2 = 27 となる。
    // つまり、Aから27文字目となる。
    // しかし、Zの次はAに戻るため、(x+n) % 26 で、A-Zの周期で割る。
    // Aから27文字目は、Aから1文字目となる。
    //
    // Aから0文字目はAのため、Aから1文字目はBとなる。
    //
    x = (x+n) % 26;
    // Aからx文字後の文字を表示する
    cout << static_cast<char>('A'+x);
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3608
n, y = list(map(int, input().strip().split()))
f=0
a=-1
b=-1
c=-1
for i  in range(0,n+1):
    for j in range(0,n-i+1):
        x=i*10000+j*5000+(n-i-j)*1000
        if y==x:
           a=i
           b=j
           c=n-i-j
print(a,b,c)

Measured memory_bytes: 9196
#include<cstdio>
#include<cstring>
#define LEN 100005

typedef struct pp{
	char name[100];
	int t;
} P;
P Q[LEN];
int head, tail, n;

void enqueue(P x){
	Q[tail] = x;
	tail = (tail + 1) % LEN;
} 

P dequeue(){
	P x = Q[head];
	head = (head + 1) % LEN;
	return x;
}

int min(int a, int b){
	return a < b ? a : b;
}

int main()
{
	int elaps = 0, c;
	int i, q;
	P u;
	scanf("%d %d", &n, &q);
	
	for(int i = 1; i <= n; i++){
		scanf("%s", Q[i].name);
		scanf("%d", &Q[i].t);
	}
	head = 1; tail = n + 1;
	
	while(head != tail){
		u = dequeue();
		c = min(q, u.t);
		u.t -= c;
		elaps += c;
		if(u.t > 0) enqueue(u);
		else {
			printf("%s %d\n", u.name, elaps);
		}
	}
	return 0;
}


Measured memory_bytes: 12732
use input::Input;

fn main() {
    let mut input = Input::default();

    let a: u32 = input.parse();
    let b: u32 = input.parse();

    println!("{}", a * b);
}

#[allow(dead_code)]
pub mod input {
    #[derive(Default)]
    pub struct Input(Vec<String>);

    impl Input {
        pub fn read_line(&mut self) -> String {
            let mut s = String::new();
            std::io::stdin().read_line(&mut s).ok().expect("read error");
            s
        }
        pub fn parse<T: std::str::FromStr>(&mut self) -> T {
            let x = if let Some(x) = self.0.pop() {
                x
            } else {
                let s = self.read_line();
                self.0 = s.split_whitespace().map(String::from).rev().collect();
                self.0.pop().expect("reached EOF")
            };
            x.parse().ok().expect("parse error")
        }
    }
}


Measured memory_bytes: 2140
import java.util.Scanner

fun main() {

    val scanner = Scanner(System.`in`)

    while (scanner.hasNext()) {
        val N = scanner.nextInt()
        val X = scanner.nextInt()
        val T = scanner.nextInt()

        val unit = N / X + if(N % X != 0) 1 else 0
        println(unit * T)
    }
}

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

using namespace std;

typedef long long int ll;

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

  int n;
  cin >> n;
  vector < int > a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  multiset < int > s(a.begin(), a.end());

  int ans = 0;
  while(!s.empty()){
    auto it = prev(s.end());
    int x = *it;
    int y = (1 << (32 - __builtin_clz(x))) - x;
    s.erase(it);
    it = s.find(y);
    if(it != s.end()){
      ans++;
      s.erase(it);
    }
  }

  cout << ans << '\n';
}


Measured memory_bytes: 10368
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long
#define int long long
#define Size(v) (int)v.size()

using namespace std;
// using namespace __gnu_pbds;

const int nax = 5e6 + 5;
int fact[nax];
const int MOD = 1e9 + 7;

int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}
int square(ll x) {return mul(x, x);}
int binpow(ll a, ll b) {
	if (b == 0) return 1 % MOD;
	if (b % 2 == 0) return square(binpow(a, b/2)) % MOD;
	return a*(square(binpow(a, b/2))) % MOD;
}
void genfact(ll n) {
	fact[0] = 1;
	for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i % MOD;
}
int inv(int x)
{
    return binpow(x, MOD - 2);
}

int divide(int x, int y)
{
    return mul(x, inv(y));
}
int Ckn(int n, int k)
{
	if (k > n) return 0;
    return divide(fact[n], mul(fact[k], fact[n - k]));
}

void solve() {
	int x, y;
	cin >> x >> y;

	fact[0] = 1;

	for (int i = 1; i <= 5000000; ++i) fact[i] = (fact[i - 1] * i) % MOD;

	if ((x + y) % 3 != 0) {
		cout << 0;
		return;
	}

	int mn = (x + y) / 3;

	int m = x - mn;

	m = max(m, y - mn);

	cout << Ckn(mn, m);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	while (t--) 
		solve();
	return 0;
}

Measured memory_bytes: 42716
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF 1e9
#define ALL(v) v.begin(), v.end()
#define max(v) *max_element(v.begin(), v.end())
#define min(v) *min_element(v.begin(), v.end())
using namespace std;
 
int main(void){
  vector<int> a, b;
  int s, t;
  for(int i = 0; i < 3; i++){
    cin>>s>>t;
    a.push_back(s);
    b.push_back(t);
  }
  vector<int> cnt(5);
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 5; j++){
      if(a[i]==j)
        cnt[j] += 1;
      if(b[i]==j)
        cnt[j] += 1;
    }
  }
  int key=0;
  for(int i = 0; i < 5; i++){
    if(cnt[i]>=3)
      key=1;
  }
  if(key==1)
    cout<<"NO";
  else
    cout<<"YES";
  return 0;
}

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

int main() {
  int n, temp;
  std::vector<int> A;
  
  std::cin >> n;
  
  for (auto i=0; i<n; ++i) {
    std::cin >> temp;
    A.push_back(temp);
  }
  
  bool flag = true;
  auto counter = 0;
  
  while (flag) {
    flag = false;
    for (auto i=n-1; i>0; --i) {
      if (A.at(i) < A.at(i-1)) {
        std::swap(A.at(i), A.at(i-1));
        flag = true;
        ++counter;
      }
    }
  }
  for (auto i=0; i<n-1; ++i)
    std::cout << A.at(i) << " ";
  
  std::cout << A.back() << std::endl << counter << std::endl;
}


Measured memory_bytes: 3128
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

typedef long long ll;

constexpr ll LL_INF = 1e15;

int a[2][2000];

int main(void) {
    int i, j, n, x;
    cin >> n >> x;
    REP (i,n) cin >> a[0][i];

    ll ans = LL_INF;
    REP (i,n) {
        ll t = (ll)i * x;
        REP (j,n) {
            t += a[i%2][j];
            a[1-(i%2)][j] = min(a[i%2][j],a[i%2][(j+n-1)%n]);
        }
        ans = min(ans,t);
    }
    cout << ans << endl;
    return 0;
}


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

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back

int t, y, h, n;

void solve() {
  vector<int> s;
  s.pb(t); s.pb(y); s.pb(h);
  sort(s.begin(), s.end());
  double d1 = s[0] / 2.0;
  double d2 = s[1] / 2.0;
  cin>>n;
  rep(i,n) {
    double r; cin>>r;
    if (r*r > d1*d1 + d2*d2) {
      cout<<"OK"<<endl;
    } else {
      cout<<"NA"<<endl;
    }
  }
}

int main (int argc, char const* argv[]) {
  while (cin>>t>>y>>h, t||y||h) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;

const int MAX = 200005;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    COMinit();
    int H,W,A,B; cin>>H>>W>>A>>B;

    ll ans=0ll;

    for (int i = B+1; i <=W ; ++i) {
        (ans+=COM(H-A-1+i-1,i-1)*COM(A-1+W-i,A-1)%MOD)%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
int i;
int N;
double X;
char S[ 100 ];
const int Rate = 380000;
double Sum;

	ios::sync_with_stdio( false );
	cin.tie( 0 );

	cin >> N;

	Sum = 0;
	for( i = 0; i < N; i++ )
	{
		cin >> X;
		cin >> S;

		if( S[ 0 ] == 'J' )
			Sum += X;
		else
			Sum += X * Rate;
	}

	cout << fixed << Sum << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int len = str.length();	//入力の文字数
         
        Deque<Integer> downPos = new ArrayDeque<>();
        Deque<IntPair> downPosPool = new ArrayDeque<>();
         
        int totalPool = 0;
        for (int i = 0; i < len; i++) {
            char ch = str.charAt(i);
            if (ch == '\\') {
                downPos.push(i);
            } else if (ch == '/' && !downPos.isEmpty()) {
                int down_pos = downPos.pop();
                int haba = i - down_pos;
                totalPool += haba;
                while (!downPosPool.isEmpty() && downPosPool.peek().int1 > down_pos) {
                    haba = haba +  downPosPool.pop().int2;
                }
                downPosPool.push(new IntPair(down_pos, haba));
            }
        }
        System.out.println(totalPool);
         
        int size = downPosPool.size();
        System.out.print(size);
        for (int i = 0; i < size; i++) {
            System.out.print(" ");
            System.out.print(downPosPool.pollLast().int2);
        }
        System.out.println();
    }
     
    static class IntPair {
        int int1;
        int int2;
        IntPair(int i1, int i2) {
            int1 = i1;
            int2 = i2;
        }
    }
}
 


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

int n,t1[5],t2[5];
LL tmp[4],s[410],Ans;
map<LL,int> S;

LL gethash(int a,int b,int c,int d)
{
	LL A=a*1000000000ll+b*1000000ll+c*1000ll+d;
	LL B=b*1000000000ll+c*1000000ll+d*1000ll+a;
	LL C=c*1000000000ll+d*1000000ll+a*1000ll+b;
	LL D=d*1000000000ll+a*1000000ll+b*1000ll+c;
	return min(min(A,B),min(C,D));
}

void getcolor(LL hs,int &a,int &b,int &c,int &d)
{
	d=hs%1000; hs/=1000;
	c=hs%1000; hs/=1000;
	b=hs%1000; hs/=1000;
	a=hs%1000;
}

int main()
{
#ifdef h10
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	int i,j,x,y,a,b,c,d;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		s[i]=gethash(a,b,c,d);
	}
	sort(s+1,s+n+1);
	for (i=1;i<=n;i++) S[s[i]]++;
	for (i=1;i<=n;i++)
	for (j=i+1;j<=n;j++)
	{
		getcolor(s[i],t1[0],t1[1],t1[2],t1[3]);
		getcolor(s[j],t2[0],t2[1],t2[2],t2[3]);
		S[s[i]]--; S[s[j]]--;
		for (x=0;x<4;x++)
		{
			tmp[0]=gethash(t2[1],t2[0],t1[1],t1[0]);
			tmp[1]=gethash(t2[0],t2[3],t1[2],t1[1]);
			tmp[2]=gethash(t2[3],t2[2],t1[3],t1[2]);
			tmp[3]=gethash(t2[2],t2[1],t1[0],t1[3]);
			sort(tmp,tmp+4);
			int way;
			LL Sum=1;
			for (y=0;y<4;y++)
			{
				if (!y||tmp[y]!=tmp[y-1])
					way=S[tmp[y]];
				else
					way--;
				Sum=Sum*way;
				getcolor(tmp[y],a,b,c,d);
				if (a==c&&b==d)
				{
					Sum+=Sum;
					if (a==b) Sum+=Sum;
				}
			}
			Ans+=Sum;
			t1[4]=t1[0];
			for (y=0;y<4;y++) t1[y]=t1[y+1];
		}
		S[s[i]]++; S[s[j]]++;
	}
	Ans=Ans/3;
	printf("%lld\n",Ans);
}


Measured memory_bytes: 80128
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = input()
    n = len(S)

    if S == S[::-1]:
        ss = S[: n // 2]
        if ss == ss[::-1]:
            print("Yes")
        else:
            print("No")
    else:
        print("No")


if __name__ == '__main__':
    resolve()


Measured memory_bytes: 2940
#include<iostream>
#include <bits/stdc++.h>
#include<set>
#include<map>
#include<vector>
using namespace std;

int main(){
  int a;
  string S,s,f;
  cin >> a;
  cin >> S;
  if(a%2!=0){
    cout << "No"<<endl;
  }
  else{
  for(int i=0;i<a;i++){
    s=s+S.at(i);
  }
  for(int i=0;i<a/2;i++){
    f=f+S.at(i);
  }
  if(s==f+f){
    cout << "Yes"<<endl;
  }
  else{
  cout << "No"<<endl;
  }

  }
}

Measured memory_bytes: 256
'use strict';

function Main(INPUT) {
    const input = INPUT.split("\n")[0].split(" ");
    const x = parseInt(input[0], 10);
    const y = parseInt(input[1], 10);
    const a = [1, 3, 5, 7, 8, 10, 12];
    const b = [4, 6, 9, 11];

    if ((x == 2 && x == y) || (a.indexOf(x) >= 0 && a.indexOf(y) >= 0) || (b.indexOf(x) >= 0 && b.indexOf(y) >= 0)) {
        console.log("Yes");
    } else {
        console.log("No");
    }
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

const ll N = 200020, M = 4040, P = 2020;
const ll MOD = 1e9 + 7;
ll f[M][M], fra[M << 1], inv[M << 1], a[N], b[N];

ll qpow(ll a, ll b) {
	ll res = 1;
	for (; b; b >>= 1, a = a * a % MOD)
		if (b & 1) res = res * a % MOD;
	return res;
}

void init() {
	fra[0] = 1;
	for (ll i = 1; i <= 8000; i++) fra[i] = fra[i - 1] * i % MOD;
	inv[8000] = qpow(fra[8000], MOD - 2);
	for (ll i = 7999; i > 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

ll C(ll n, ll m) {
	if (m > n) return 0;
	return fra[n] * inv[n - m] % MOD * inv[m] % MOD;
}

int main() {
	init();
	ll n;
	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++) scanf("%lld%lld", &a[i], &b[i]);
	for (ll i = 1; i <= n; i++) f[P - a[i]][P - b[i]]++;
	for (ll i = 1; i <= 4030; i++)
		for (ll j = 1; j <= 4030; j++)
			f[i][j] = (f[i][j] + f[i - 1][j] + f[i][j - 1]) % MOD;
	ll ans = 0;
	for (ll i = 1; i <= n; i++)
		ans = ( ans + f[P + a[i]][P + b[i]]) % MOD;
	for (ll i = 1; i <= n; i++)
		ans = (ans - C((a[i] + b[i]) * 2, a[i] * 2) + MOD) % MOD;
	ans =  ans * qpow(2, MOD - 2) % MOD;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 134208
S = list(input())
N = len(S)+1
L = [0]*N
R = [0]*N
for i in range(N-1):
    if S[i] == "<":
        L[i+1] = L[i]+1
for i in range(N-2,-1,-1):
    if S[i] == ">":
        R[i] = R[i+1]+1
ans = 0
for i in range(N):
    ans += max(L[i],R[i])
print(ans)

Measured memory_bytes: 97500
#include<stdio.h>
#include<stdint.h>
#include<inttypes.h>

typedef int32_t i32;
typedef int64_t i64;

#define MIN(a, b) ((a) < (b) ? (a) : (b))

i64 f (i64 r, i64 n) {
  i64 t = 1;
  while (n--) {
    t *= r;
  }
  return t;
}

void run (void) {
  i64 n, a;
  scanf ("%" SCNi64 "%" SCNi64, &n, &a);
  i64 ans = n;
  for (i64 i = 2; i * i <= n; ++i) {
    for (i64 j = 1; 2 * j <= i; ++j) {
      i64 m = f (i / j, j - i % j) * f (i / j + 1, i % j);
      if (m > n) break;
      ans = MIN(ans, i + j * a + (n + m - 1) / m);
    }
  }
  printf ("%" PRIi64 "\n", ans);
}

int main (void) {
  run();
  return 0;
}

Measured memory_bytes: 128
import java.util.Comparator;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a[] = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = sc.nextInt();
		}
		TreeSet<Integer> ts = new TreeSet<>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				if(a[o1]==a[o2]) {
					return o1-o2;
				}
				return a[o1]-a[o2];
			}
			
		});
		for(int i=0;i<n;i++) {
			ts.add(i);
		}
		int order[] = new int[n];
		for(int i=0;i<n;i++) {
			order[i] = ts.first();
			ts.remove(ts.first());
		}
		long dp[][] = new long[n][n];
		for(int len=0;len<n;len++) {
			for(int i=0;i<n;i++) {
				int j = i+len;
				if(j>n-1) continue;
				if(i==j) {
					dp[i][j] = (long) Math.abs(order[0]-i)*a[order[0]];
				}
				else {
					dp[i][j] = Math.max((long) Math.abs(order[len]-i)*a[order[len]]+dp[i+1][j],(long) Math.abs(order[len]-j)*a[order[len]]+dp[i][j-1]);
				}
			}
		}
		System.out.println(dp[0][n-1]);
	}
}


Measured memory_bytes: 86432
def main():
    N = int(input())
    A = [int(input()) for i in range(N)]
    A_sort = sorted(A)
    if (A_sort[-1] == A_sort[-2]):
        for i in range(N):
            print(A_sort[-1])
    else:
        for i in range(N):
            if(A[i]==A_sort[-1]):
                print(A_sort[-2])
            else:
                print(A_sort[-1])

main()


Measured memory_bytes: 70488
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#include <set>
#include <map>
#include <stack>
#include <iomanip>
#include <tuple>
#define ll long long
using namespace std;
struct all_init
{
    all_init()
    {
        cout << fixed << setprecision(12);
    }
} All_init;


int main()
{
    ll n, m;
    cin >> n >> m;
    if(n<=m){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FIN         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii          pair<int,int>
#define F           first
#define S           second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define rall(x)     (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a)   for(int i = a; i >= 0; i--)
#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 
#define w(t)        while(t--)
#define sz(s)       int(s.size())
#define cls(a,car)  memset(a,car,sizeof (a))
#define db(x)       cerr << #x << " is " << x << '\n'
#define FL          freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
#define angle(x)    double(x * acos(-1) / 180.0)
using namespace std;
typedef long long   ll;
typedef vector<int> vi;
typedef vector<ii>  vii;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const double E = 1e-9;
int dx[] = {1, 0}, dy[] = {0, 1};
//int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
int add(int a, int b){return  a + b > mod ? a + b - mod : a + b;}
int mul(int a, int b){return a * b >= mod ? a * b % mod : a * b;}  
int n, k;
int v[105];
int dp[2][N], prefixsum[N]; 
int f(int i, int w){
    if(w < 0)return 0;
    if(i == 0){
        return w == 0 ? 1 : 0;
    }
    int &ans = dp[i][w];
    if(ans == -1){
        ans = 0;
        for(int j = 0; j <= v[i]; j++)
            ans = add(ans, f(i - 1, w - j));
    }
    return ans;
} 
int main(){
    //FL;
    FIN;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    for(int i = 0; i <= n; i++){
        if(i){
            prefixsum[0] = dp[(i - 1) & 1][0];
            for(int j = 1; j <= k; j++)
                prefixsum[j] = add(prefixsum[j - 1], dp[(i - 1) & 1][j]);
        }

        for(int w = 0; w <= k; w++){
            int &ans = dp[i & 1][w];
            if(i == 0){
                ans = (!w ? 1 : 0);
                continue;
            }
            ans = 0;
            ans = prefixsum[w];
            if(w - v[i] - 1 >= 0)
                ans = ((ans - prefixsum[w - v[i] - 1] + mod) % mod) % mod;
        }
    }

    cout << dp[n & 1][k] << '\n';

    EjecuteTime;
    return 0;
}       


Measured memory_bytes: 4936
#include<iostream>
using namespace std;
int main()
{
    int n, T, a, b;
    cin >> n >> T;
    int c[n], t[n];
    for(int i = 0; i < n; i++)
    {
        cin >> c[i] >> t[i];
    }

    for(int j = 0; j < n; j++)
    {
        for(int i = j; i < n; i++)
        {
            if(c[j] > c[i])
            {
                a = c[j];
                c[j] = c[i];
                c[i] = a;
                b = t[j];
                t[j] = t[i];
                t[i] = b;
            }
        }
    }
    for(int i = 0; i < n; i++)
    {
        if(t[i] <= T)
        {
            cout << c[i];
            return 0;
        }
    }
    cout << "TLE";
    return 0;
}

Measured memory_bytes: 3560
def count(state: int, ss: list):
    res = 0
    for s in ss:
        res += ((state >> s) & 1)
    return res


assert count(0b011, [0, 1]) == 2
assert count(0b011, [2]) == 0


def is_on(state: int, p: int, ss: list):
    return count(state, ss) % 2 == p


def main():
    N, M = map(int, input().split())

    sss = [
        list(map(lambda x: int(x)-1, input().split()))[1:] for _ in range(M)
    ]

    ps = list(map(int, input().split()))

    cnt = 0
    for state in range(0, 2**N):
        cnt += all(map(lambda x: is_on(state, x[0], x[1]), zip(ps, sss)))
    print(cnt)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using Graph=vector<vector<int>>;
#define MOD 1000000007
#define INF 1000000000

int main(){
  int N,M;
  cin>>N>>M;
  Graph G(N);
  vector<int> count(N,0);
  for(int i=0;i<N+M-1;i++){
    int A,B;
    cin>>A>>B;
    A--,B--;
    G.at(A).push_back(B);
    count.at(B)++;
  }

  int root;
  for(int i=0;i<N;i++){
    if(count.at(i)==0){
      root=i;
    }
  }

  vector<int> parent(N,-1);
  stack<int> s;
  s.push(root);
  while(!s.empty()){
    int v=s.top();
    s.pop();
    for(auto nv:G.at(v)){
      if(count.at(nv)>1){
        count.at(nv)--;
      }else{
        parent.at(nv)=v;
        s.push(nv);
      }
    }
  }

  for(int i=0;i<N;i++){
    cout<<parent.at(i)+1<<endl;
  }
}


Measured memory_bytes: 9544
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

const int MAX = 100001;
const int MOD = 1000000007;

typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef pair< ll, int > pli;
typedef pair< int, ll > pil;

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

  int n;
  cin >> n;
  int a[n];
  for(int i = 0; i < n; i++) cin >> a[i];

  int sum = 0;
  for(int i = 0; i < n; i++) sum += a[i];

  double ave = (double)sum / n;
  int j = 0;
  for(int i = 1; i < n; i++){
    if(abs(ave - a[j]) > abs(ave - a[i])) j = i;
  }

  cout << j << endl;

  return 0;
}


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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数 
unsigned gcd(unsigned a, unsigned b) {
  if(a < b) return gcd(b, a);
  unsigned r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

 int main(){
   int A, B;
   cin >> A >> B;
   int ans = max(A * B, max(A + B, A - B));
   print(ans);
 }

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

#define PB push_back

int main(int argc,char* argv[]){
  std::ios_base::sync_with_stdio(false);
  
  int n;
  string str;
  set<string> sstr[4];

  cin>>n;
  for(int i=0;i<n;i++){
    cin>>str;

    if(str[0]=='i'){
      cin>>str;
      switch(str[0]){
      case 'A':
	sstr[0].insert(str);
	break;
      case 'C':
	sstr[1].insert(str);
	break;
      case 'G':
	sstr[2].insert(str);
	break;
      case 'T':
	sstr[3].insert(str);
      }
    }
    else{
      cin>>str;
      switch(str[0]){
      case 'A':
	if(sstr[0].find(str)!=sstr[0].end())
	  cout<<"yes"<<endl;
	else
	  cout<<"no"<<endl;
	break;
      case 'C':
	if(sstr[1].find(str)!=sstr[1].end())
	  cout<<"yes"<<endl;
	else
	  cout<<"no"<<endl;
	break;
      case 'G':
	if(sstr[2].find(str)!=sstr[2].end())
	  cout<<"yes"<<endl;
	else
	  cout<<"no"<<endl;
	break;
      case 'T':
	if(sstr[3].find(str)!=sstr[3].end())
	  cout<<"yes"<<endl;
	else
	  cout<<"no"<<endl;
	break;
      }
    }
  }
  return 0;
}

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

using namespace std;
using llong = long long;
using P = pair<llong, llong>;

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

const llong inf = llong(1e18)+7;
const llong mod = 1e9+7;

int main(){
	llong N, M;
	vector<llong> D,T;
	map<llong,llong> m;

	cin >> N;
	D.resize(N);
	for(int i = 0; i < N; i++){
		cin >> D[i];
		m[D[i]]++;
	}

	cin >> M;
	T.resize(M);
	bool check = true;
	for(int i = 0; i < M; i++){
		cin >> T[i];
		if(m[T[i]] == 0)
			check = false;
		else
			m[T[i]]--;
	}

	if(check)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 15872
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#define f first
#define s second
#define mp make_pair
#define eb emplace_back
#define sz(s) ((int) s.size ())
#define all(s) s.begin (), s.end ()

using namespace std;

typedef long long ll;

const int N = 105;
const int mod = (int) 1e9 + 7;

int n, w, ans;
map<int, int> a, b;

inline void solve () {
        scanf ("%d%d", &n, &w);
        for (int i = 1; i <= n; i++) {
                int x, y; scanf ("%d%d", &x, &y);
                if (x > w) {
                        continue;
                }
                b.clear (); b[x] = y;
                for (auto j : a) {
                        if (j.f + x <= w) {
                                b[j.f + x] = max (b[j.f + x], j.s + y);
                        }
                }
                if (sz (a) < sz (b)) {
                        a.swap (b);
                }
                for (auto j : b) {
                        a[j.f] = max (a[j.f], j.s);
                }
        }
        for (auto i : a) {
                ans = max (ans, i.s);
        }
        printf ("%d\n", ans);
}

int tests = 1;

int main () {
//        freopen (".in", "r", stdin);
//        freopen (".out", "w", stdout);
//        scanf ("%d", &tests);
        while (tests--) {
                solve ();
        }
        return 0;
}


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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    S.erase(unique(S.begin(), S.end()), S.end());
    if (S.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

#define LL long long

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int INF=9999999;
const int MAXN=300000;

char str[MAXN+1];
LL vis[29];
LL ans;

int main(){
    cin>>str;
	LL len=strlen(str);
    for(int i=0;i<len;i++)
        vis[str[i]-'a']++;
    for(int i=0;i<26;i++) if(vis[i]>=2) ans+=(vis[i]*(vis[i]-1)/2);
    printf("%lld\n",(long long)len*(len-1)/2-ans+1);
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<string>
using namespace std;
#define ll long long int
#define pb push_back
#define mod 1000000007
#define all(x) x.begin(),x.end()
typedef vector<ll> vll;
typedef vector<int> vi;
ll modpower(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b>>=1;
	}
	return res;
}
int dp[100000][3];
int rec(int mat[][3],int n,int p,int r)
{
	if(r>=n)
		return 0;
	
	int mx=0;
	for(int i=0;i<3;i++)
	{
		if(dp[r][i]==-1)
			dp[r][i]=rec(mat,n,i,r+1)+mat[r][i];
		if(i!=p)
			mx=max(mx,dp[r][i]);
	}
	return mx;
	
}
int main() 
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);
	ll T=1;
//	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		int mat[n][3];
		for(int i=0;i<n;i++)
		{
			cin>>mat[i][0]>>mat[i][1]>>mat[i][2];
		}
		memset(dp,-1,sizeof(dp));
		int res=0;
		for(int i=0;i<3;i++)
		{
			dp[0][i]=rec(mat,n,i,1)+mat[0][i];
			res=max(res,dp[0][i]);
		}
//		for(int i=0;i<n;i++)
//		{
//			for(int j=0;j<3;j++)
//				cout<<dp[i][j]<<" ";
//			cout<<endl;
//		}
		cout<<res<<endl;
		
		
		
	
	}
	return 0;
}





Measured memory_bytes: 10368
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
	class Pair{
		int a;
		int b;
		Pair(int a,int b){
			this.a=a;
			this.b=b;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + getOuterType().hashCode();
			result = prime * result + a;
			result = prime * result + b;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (!getOuterType().equals(other.getOuterType()))
				return false;
			if (a != other.a)
				return false;
			if (b != other.b)
				return false;
			return true;
		}
		private Main getOuterType() {
			return Main.this;
		}
	}
	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	ArrayList<ArrayList<Integer>> klist;
	ArrayList<ArrayList<Integer>> llist;
	boolean kused[];
	boolean lused[];
	int kcolor[];
	int lcolor[];
	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		int l=sc.nextInt();
		klist = new ArrayList<ArrayList<Integer>>();
		llist = new ArrayList<ArrayList<Integer>>();
		kused = new boolean[n+1];
		lused = new boolean[n+1];
		kcolor = new int[n+1];
		lcolor = new int[n+1];
		for(int i=0; i<=n; i++) {
			klist.add(new ArrayList<Integer>());
			llist.add(new ArrayList<Integer>());
		}
		for(int i=0; i<k; i++) {
			int p=sc.nextInt();
			int q=sc.nextInt();
			klist.get(p).add(q);
			klist.get(q).add(p);
		}
		for(int i=0; i<l; i++) {
			int r=sc.nextInt();
			int s=sc.nextInt();
			llist.get(r).add(s);
			llist.get(s).add(r);
		}

		int color=1;
		for(int i=1; i<=n; i++) {
			if(!kused[i]) {
				dfs(i, klist, kused, kcolor, color);
			}
			if(!lused[i]) {
				dfs(i, llist, lused, lcolor, color);
			}
			color++;
		}
		Map<Pair , Integer> m = new HashMap<>();

		for(int i=1; i<=n; i++) {
			Pair p = new Pair(kcolor[i], lcolor[i]);
			m.put(p, m.get(p) != null ? m.get(p)+1 : 1);
		}
		for(int i=1; i<=n; i++) {
			if(i>1)System.out.print(" ");
			Pair p = new Pair(kcolor[i], lcolor[i]);
			System.out.print(m.get(p));
		}
		System.out.println();
		sc.close();
	}

	public void dfs(int s, ArrayList<ArrayList<Integer>> list, boolean[] used, int c[], int color) {
		ArrayDeque<Integer> g = new ArrayDeque<Integer>();
		g.add(s);
		used[s]=true;
		c[s]=color;
		while(!g.isEmpty()) {
			int p = g.pop();
			ArrayList<Integer> k = list.get(p);
			for(int i=0; i<k.size(); i++) {
				int q=k.get(i);
				if(p != q && ! used[q]) {
					g.add(q);
					c[q]=color;
					used[q]=true;
				}
			}
		}
	}
}


Measured memory_bytes: 195816
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,k;
    cin>>a>>b>>k;
    a=a-k;
    if(a<=0)
    {
        b=b+a;
        a=0;
    }
    if(b<=0)
    {
        b=0;
    }
    cout<<a<<" "<<b<<endl;


return 0;}


Measured memory_bytes: 3628
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;


void solve();

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

ll n,a,b,c,d;
map<ll,ll> dp;

ll f(ll x){
    if(x==0)return 0;
    if(x==1)return d;
    if(dp.count(x))return dp[x];
    
    ll ret=LINF;
    if(x<LINF/d)chmin(ret,x*d);
    if(x%2==0)chmin(ret,f(x/2)+a);
    else{
        chmin(ret,f(x/2)+a+x%2*d);
        chmin(ret,f(x/2+1)+a+(2-x%2)*d);
    }
    if(x%3==0)chmin(ret,f(x/3)+b);
    else {
        chmin(ret,f(x/3)+b+x%3*d);
        chmin(ret,f(x/3+1)+b+(3-x%3)*d);
    }
    if(x%5==0)chmin(ret,f(x/5)+c);
    else{
        chmin(ret,f(x/5)+c+x%5*d);
        chmin(ret,f(x/5+1)+c+(5-x%5)*d);
    }
    return dp[x] = ret;
}

void solve(){
    ll t;cin>>t;
    while(t--){
        dp.clear();
        cin>>n>>a>>b>>c>>d;
        cout<<f(n)<<endl;
    }
}


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const string YES = "Yes";
const string NO = "No";
const ll mod = 1e9+7;

// map<ll,ll> primes(ll n){
//     map<ll, ll> r;
//     for(int i=2; i*i<=n; i++){
//         while(n % i ==0){
//             r[i]++;
//             n /= i;
//         }
//     }

//     if(n != 1) r[n] = 1;
//     return r;
// }

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


    ll n; cin>>n;
    if (n==2){
        cout << 1;
        return 0;
    }
    ll ans = 1;
    ll tmp = n-1;
    for (ll i = 2; i * i <= tmp; i++) {
        if (tmp % i == 0) {
            if (tmp / i == i) ans++; 
            else ans += 2;
        }
    }

    set<ll> st;
    // cout << ans << endl;
    for(ll k=2;k*k<=n;k++){
        if(n%k==0){
            st.insert(k);
            st.insert(n/k);
        }
    }
    st.insert(n);
    ll a = n;
    for(auto k:st){
        n = a;
        while(n%k==0){
            n /= k;
        }
        // cout << n << endl;
        if(n%k==1) ans++;
        // cout << ans << endl;
    }
    cout << ans;
    return 0;
    
}



Measured memory_bytes: 512
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

struct Info{
	Info(){
		to = cost = num = 0;
	}
	Info(int arg_to,ll arg_cost,ll arg_num){
		to = arg_to;
		cost = arg_cost;
		num = arg_num;
	}
	int to;
	ll cost,num;
};

struct Data{
	void set(ll arg_budget,ll arg_num_sum,int arg_town){
		budget = arg_budget;
		num_sum = arg_num_sum;
		town = arg_town;
	}
	ll budget,num_sum;
	int town;
};

int main(){

	int N,M,L,from,to,next_town,tmp_cost,tmp_num;
	ll dist,num,ans;
	ll dp[101][101];

	vector<Info> V[101];

	queue<Data> Q;

	while(true){
		scanf("%d %d %d",&N,&M,&L);
		if(N == 0 && M == 0 && L == 0)break;

		for(int i = 1; i <= N; i++)V[i].clear();

		for(int i = 1; i <= N; i++){
			for(int k = 0; k <= L; k++)dp[i][k] = BIG_NUM;
		}

		for(int i = 1; i <= M; i++){
			scanf("%d %d %lld %lld",&from,&to,&dist,&num);
			V[from].push_back(Info(to,dist,num));
			V[to].push_back(Info(from,dist,num));
		}

		Data first;
		first.set(L,0,1);
		dp[1][L] = 0;

		Q.push(first);

		while(!Q.empty()){

			if(Q.front().town == N){
				Q.pop();
			}else if(Q.front().num_sum > dp[Q.front().town][Q.front().budget]){
				Q.pop();
			}else{

				for(int i = 0; i < V[Q.front().town].size(); i++){
					next_town = V[Q.front().town][i].to;
					tmp_cost = V[Q.front().town][i].cost;
					tmp_num = V[Q.front().town][i].num;

					if(Q.front().budget >= tmp_cost && dp[next_town][Q.front().budget-tmp_cost] > dp[Q.front().town][Q.front().budget]){
						dp[next_town][Q.front().budget-tmp_cost] = dp[Q.front().town][Q.front().budget];
						Data next;
						next.set(Q.front().budget-tmp_cost,Q.front().num_sum,next_town);
						Q.push(next);
					}

					if(dp[next_town][Q.front().budget] > dp[Q.front().town][Q.front().budget]+tmp_num){
						dp[next_town][Q.front().budget] = dp[Q.front().town][Q.front().budget]+tmp_num;
						Data next;
						next.set(Q.front().budget,Q.front().num_sum+tmp_num,next_town);
						Q.push(next);
					}
				}

				Q.pop();
			}
		}

		ans = BIG_NUM;
		for(int i = 0; i <= L; i++)ans = min(ans,dp[N][i]);

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


	return 0;
}

Measured memory_bytes: 3244
import math

def koch(p1, p2, n):
    if n == 0:
        return

    s = ((2 * p1[0] + 1 * p2[0]) / 3, (2 * p1[1] + 1 * p2[1]) / 3)
    t = ((1 * p1[0] + 2 * p2[0]) / 3, (1 * p1[1] + 2 * p2[1]) / 3)
    u = ((t[0] - s[0]) * math.cos(math.radians(60)) - (t[1] - s[1]) * math.sin(math.radians(60)) + s[0],
         (t[0] - s[0]) * math.sin(math.radians(60)) + (t[1] - s[1]) * math.cos(math.radians(60)) + s[1])


    koch(p1, s, n-1)
    print('{:8f} {:8f}'.format(s[0], s[1]))
    koch(s, u, n-1)
    print('{:8f} {:8f}'.format(u[0], u[1]))
    koch(u, t, n-1)
    print('{:8f} {:8f}'.format(t[0], t[1]))
    koch(t, p2, n-1)


if __name__ == "__main__":
    import sys
    input = sys.stdin.readline # faster input

    n = int(input())

    a = (0, 0)
    b = (100, 0)

    print('{:8f} {:8f}'.format(a[0], a[1]))
    koch(a, b, n)
    print('{:8f} {:8f}'.format(b[0], b[1]))



Measured memory_bytes: 5780
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;

#define rep(i,n)  for(int i = 0; i < (int)(n);    i++)
#define sz(x)     ((int)(x).size())
#define all(x)    (x).begin(),(x).end()

using ll = long long;

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

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  ll X; std::cin >> X;
  ll ans = (X/500)*1000;
  X -= (X/500)*500;
  std::cout << ans + (X/5)*5 << std::endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>

using namespace std;
typedef long long ll;

int main() {
  int N;
  scanf("%d", &N);
  vector<pair<int, int>> p(N);
  for (int i = 0; i < N; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    p[i] = make_pair(x, y);
  }
  map<int, vector<int>> mx;
  map<int, vector<int>> my;
  for (int i = 0; i < N; i++) {
    mx[p[i].first].push_back(p[i].second);
    my[p[i].second].push_back(p[i].first);
  }
  set<int> vx, vy;
  ll z = 0;
  for (auto it = mx.begin(); it != mx.end(); ++it) {
    int cx = 0, cy = 0;
    vector<int> s;
    s.push_back(it->first);
    while (!s.empty()) {
      int x = s.back();
      s.pop_back();
      if (vx.count(x) > 0) continue;
      vx.insert(x);
      cx++;
      vector<int> &yy = mx[x];
      for (auto jt = yy.begin(); jt != yy.end(); ++jt) {
        if (vy.count(*jt) > 0) continue;
        vy.insert(*jt);
        cy++;
        vector<int> &xx = my[*jt];
        for (auto kt = xx.begin(); kt != xx.end(); ++kt) {
          if (vx.count(*kt) > 0) continue;
          s.push_back(*kt);
        }
      }
    }
    z += ((ll)cx) * cy;
  }
  cout << z-N << endl;
}


Measured memory_bytes: 16640
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = 0

for i in range(0,N):
#    print(ans)
    ans = ans + B[A[i]-1]
    if i!= 0 and A[i] == A[i-1] + 1:
        ans = ans + C[A[i-1]-1]

print(ans)


Measured memory_bytes: 3060
#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

long long n, sol;
string s;
unordered_map <string, int> mp;

void f (string t, int flg) {
	string a, b;
	for (int mask=0; mask<(1<<n); mask++) {
		a = "", b = "";
		for (int i=0; i<n; i++) {
			if (mask & (1 << i)) {
				a += t[i];
			} else {
				b += t[i];
			}
		}
		if (flg) mp[a+'.'+b]++; else sol += mp[a+'.'+b];
	}
}

int main () {
	cin >> n >> s;
	f(s.substr(0, n), 1);
	s = s.substr(n, n);
	reverse(s.begin(), s.end());
	f(s, 0);
	cout << sol;
	return 0;
}

Measured memory_bytes: 69492
#include <iostream>

using namespace std;
int main(void){
    int a, b, x, y;
    
    while(true){
        cin >> x >> y ;
        if(x == 0 && y == 0)  break;
        
        if(x<y){
            a = x;
            b = y;
        } else {
            a = y;
            b = x;
        }
        cout << a << " " << b << endl ;
        
    }
}

Measured memory_bytes: 3108
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n;
ll a[200000];
ll s[200000];
set<ll> S;
map<ll,ll> tbl;
ll f(int l,int r){ //[l,r)
  if(r-l<=1)
    return 0;
  ll m = (l+r)/2;
  ll ret = f(l,m)+f(m,r);
  sort(s+l,s+m);
  sort(s+m,s+r);
  int x=l;
  int cnt=0;
  for(int y=m;y<r;++y){
    while(s[x]<=s[y] && x<m)
      ++x,++cnt;
    ret+=cnt;
  }
  return ret;
}

int main(){
  ll k;
  cin >> n >> k;
  for(int i=0;i<n;++i){
    cin >> a[i];
    a[i]-=k;
    if(i){
      s[i]=s[i-1]+a[i];
    }
    else
      s[i]=a[i];
    //    S.insert(s[i]);
  }

  ll ans=0;
  for(int i=0;i<n;++i)
    if(s[i]>=0)
      ++ans;

  /*
  int idx=0;
  for(auto i=S.begin();i!=S.end();++i)
    tbl[*i]=idx++;
  for(int i=0;i<n;++i)
    s[i]=tbl[s[i]];
  */  
  ans+= f(0,n);
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3456