akhauriyash/Code-Regression huggingface dataset:
# 参考URL https://note.nkmk.me/python-union-find/
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    from sys import stdin
    input = stdin.buffer.readline

    n, q = map(int, input().split())

    uf = UnionFind(n)

    ans = []
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            uf.union(u, v)
        else:
            if uf.same(u, v):
                ans.append(1)
            else:
                ans.append(0)
    
    for i in ans:
        print(i)

main()

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

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

int MOD=1e9+7;
ll INF=1e18;

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

int par[200010];
int ranks[200010];

void init(int n){
    for(int i=0; i<n; i++){
        par[i]=i;
        ranks[i]=0;
    }
}

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

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

void unite(int x, int y){
    x=find(x);
    y=find(y);
    if(x == y) return;

    if(ranks[x] < ranks[y]){
        par[x]=y;
    }
    else{
        par[y]=x;
    }
    
    if(ranks[x] == ranks[y]){
        ranks[x]++;
    }
}

int par2[200010];
int ranks2[200010];

void init2(int n){
    for(int i=0; i<n; i++){
        par2[i]=i;
        ranks2[i]=0;
    }
}

int find2(int x){
    if(par2[x] == x){
        return x;
    }
    else{
        return par2[x]=find2(par2[x]);
    }
}

bool same2(int x, int y){
    return find2(x) == find2(y);
}

void unite2(int x, int y){
    x=find2(x);
    y=find2(y);
    if(x == y) return;

    if(ranks2[x] < ranks2[y]){
        par2[x]=y;
    }
    else{
        par2[y]=x;
    }
    
    if(ranks2[x] == ranks2[y]){
        ranks2[x]++;
    }
}

int main(){
    int n, k, l; cin>>n>>k>>l;
    init(n);
    init2(n);
    for(int i=0; i<k; i++){
        int p, q; cin>>p>>q;
        p--, q--;
        unite(p, q);
    }
    for(int i=0; i<l; i++){
        int r, s; cin>>r>>s;
        r--, s--;
        unite2(r, s);
    }
    
    map<P, int> ans;
    for(int i=0; i<n; i++){
        ans[P(find(i), find2(i))]++;
    }

    for(int i=0; i<n; i++){
        cout << ans[P(find(i), find2(i))] << " ";
    }
}

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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  ll W; scanf("%lld", &W);

  vector<vector<ll>> items(4, vector<ll>());
  for (int i = 0; i < 4; ++i) { items[i].push_back(0); }
  ll w0, w;
  ll v;
  scanf("%lld %lld", &w0, &v);
  items[0].push_back(v);
  for (int i = 1; i < N; ++i) {
    scanf("%lld %lld", &w, &v);
    items[w - w0].push_back(v);
  }
  for (int i = 0; i < 4; ++i) {
    sort(items[i].begin() + 1, items[i].end(), greater<ll>());
    for (int j = 1; j < (int)items[i].size(); ++j) {
      items[i][j] += items[i][j - 1];
    }
  }

  ll ans = 0;
  for (int i = 0; i < (int)items[0].size(); ++i) {
    ll a = i * w0;
    for (int j = 0; j < (int)items[1].size(); ++j) {
      ll b = j * (w0 + 1);
      if (a + b > W) { break; }
      for (int k = 0; k < (int)items[2].size(); ++k) {
        ll c = k * (w0 + 2);
        if (a + b + c > W) { break; }
        for (int l = 0; l < (int)items[3].size(); ++l) {
          ll d = l * (w0 + 3);
          if (a + b + c + d > W) { break; }
          ll val = items[0][i] + items[1][j] + items[2][k] + items[3][l];
          ans = max(ans, val);
        }
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    val Array(m, n) = io.StdIn.readLine().split(" ").map(_.toInt)
    println(power(m, n))
  }
  def power(m: Int, n: Int): Long = {
    var x: Long = m
    var y = n
    var acc: Long = 1
    while(y != 0) {
      if (y % 2 == 0) {
        x = x * x % 1000000007
        y /= 2
      } else {
        y -= 1
        acc = (x * acc) % 1000000007
      }
    }
    acc
  }
}

Measured memory_bytes: 43852
N = gets.chomp.to_i
A = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)
score = 0
old = 0

0.upto(N) do |i|
  enemy = A[i]
  hero = B[i] || 0

  if enemy <= old
    score += enemy
    old = hero
    next
  else
    enemy -= old
    score += old
  end

  if enemy <= hero
    score += enemy
    old = hero - enemy
  else
    score += hero
    old = 0
  end
end

puts score

Measured memory_bytes: 15500
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1e14;
const ll MOD = 1e9 + 7;

ll pow2(ll n)
{
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        return pow2(n / 2) * pow2(n / 2);
    }
    return 2 * pow2(n - 1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N, M;
    cin >> N >> M;
    priority_queue<ll> A;
    rep(i, N)
    {
        int v;
        cin >> v;
        A.push(v);
    }
    for (int i = 0; i < M; i++) {
        int v = A.top()/2;
        A.pop();
        A.push(v);
    }
    ll sum = 0;
    while(!A.empty()) {
        sum += A.top();
        A.pop();
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1400
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

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

#define pb push_back
#define fr first
#define sc second

const ll M = 1000000007;

ll modpow(ll x,ll k){
	if(k == 0)return 1;
	ll ret = modpow(x,k/2);
	ret *= ret; ret %= M;
	if(k&1LL){
		ret *= x;
		ret %= M;
	}
	return ret;
}

int main(){
	int N;
	string s;
	cin >> N >> s;
	
	static ll dp[2][5005] = {};
	int t = 0, t_ = 1;
	dp[t][0] = 1;
	for(int i = 0 ; i < N ; i ++){
		dp[t_][0] = dp[t][0]+dp[t][1];
		while(dp[t_][0] >= M)dp[t_][0] -= M;
		for(int j = 1 ; j <= i+1 ; j ++){
			dp[t_][j] = dp[t][j-1]*2+dp[t][j+1];
			while(dp[t_][j] >= M)dp[t_][j] -= M;
		}
		swap(t,t_);
	}
	cout << (dp[t][s.size()]*modpow(2,(M-2)*s.size()))%M << endl;
}



Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
string s;
int cnt[155],type=0;
int main(){
	cin >> s;
	memset(cnt,0,sizeof cnt);
	for(int i=0;i<s.size();i++){
		++cnt[s[i]];
	}
	for(int i=1;i<=s.size();i++){
		if(cnt[s[i-1]]%2==1){
			type=-1;
		}
	}
	if(type==0){
		printf("Yes");
	}else printf("No");
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define MAX(p,q) ((p>q)?(p):(q))
#define MIN(p,q) ((p<q)?(p):(q))

#define INF 1000000000;
#define REP(i,n) for(i=1;i<=n;i++)

int gcd(int a,int b);
/*比較函数の実装
int -32768 to 32767 (2**15-1)
long -2147483648 to 2147483648 (2**31-1)
*/
int intcmp(const void *a,const void *b){
  return *(int *)a - *(int *)b;
}
//qsort(a,sizeof(a)/sizeof(int),sizeof(int),intcmp);
int longcmp(const void *a,const void *b){
  return *(long *)a - *(long *)b;
}
//qsort(a,sizeof(a)/sizeof(long),sizeof(long),longcmp);
int doublecmp(const void *a, const void *b){
  return *(double *)a - *(double *)b;
}
//qsort(a,sizeof(a)/sizeof(double),sizeof(double),doublecmp);
int main(void)
{
  int n,x;
  scanf("%d%d",&n,&x);
  int i;
  int b=1;
  int l[101]={};
  REP(i,n){
    scanf("%d",&l[i]);
    if(l[i]<=x){
      b++;
    }
    x -= l[i];


  }
  printf("%d",b);

  return 0;

}

int gcd(int a,int b)
{
  int max,min,tmp;
  max = MAX(a,b);
  min = MIN(a,b);
  if(max%min==0) return min;
  else
  {
    tmp = min;
    min = max%min;
    max = tmp;
    return gcd(max,min);
  }
}


Measured memory_bytes: 128
// https://atcoder.jp/contests/abc082/tasks/abc082_b
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    sort(ALL(s));
    sort(ALLR(t));
    if (s < t) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }

    return 0;
}


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

#define be begin
#define en end
#define pb push_back
#define ALL(a) (a).be() , (a).en()
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
#define REP2(i,s,n) for(int (i)=(s);(i)<(n);(i)++) 

using LL = long long;

template<typename T> using V = vector< T >;
using Vi = V<int>;
using Vll = V<LL>;

const int INF = 1999999999;
const LL INFLL = 999999999999999LL;

struct edge{
    int src; int dst; int weight;
    edge() : src(0), dst(0), weight(0) {}
    edge(int s, int d, int w) : src(s), dst(d), weight(w) {}
};

using edges = V<edge>;
using graph = V<edges>;

void add_edge(edges &g,int s, int d, int w=1){g.pb(edge(s,d,w));}
void add_edge(graph &g,int s, int d, int w=1){g[s].pb(edge(s,d,w));}

V<Vll> floyd(const graph &g){
    int i,j,k; int n = g.size();
    V<Vll> dist(n,Vll(n,INFLL/2));
    REP(i,n){dist[i][i]=0;}
    REP(i,n){for(auto &e:g[i]){dist[e.src][e.dst]=e.weight;}}
    REP(k,n){REP(i,n){REP(j,n){dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);}}}
    return dist;
}

int main(){
    LL n,m,l;
    cin>>n>>m>>l;

    graph G(n);
    Vll a(m),b(m),c(m);
    REP(i,m){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--;
        b[i]--;
        c[i];
        add_edge(G,a[i],b[i],c[i]);
        add_edge(G,b[i],a[i],c[i]);
    }

    LL q;
    cin>>q;
    Vll s(q),t(q);
    REP(i,q){
        cin>>s[i]>>t[i];
        s[i]--;
        t[i]--;
    }
    auto dist = floyd(G);
    graph G2(n);
    REP(i,dist.size()){
        REP(j,dist[i].size()){
            if(dist[i][j] <= l){
                add_edge(G2,i,j,1);
            }
        }
    }
    auto fuel = floyd(G2);
    REP(i,q){
        LL q_fuel = fuel[s[i]][t[i]];
        cout<<((q_fuel!=INFLL/2)?q_fuel-1:-1)<<endl;
    }
    return 0;
}

Measured memory_bytes: 7936
#include<stdio.h>
#include<string.h>

int main() {
    char ans;
    char buf[256];
    long int k;
    scanf("%s", &buf);
    scanf("%ld", &k);

    int len = strlen(buf);

    for(int i = 0; i < len; i++) {
        if (buf[i] == '1') {
            ans = '1';
            continue;
        }
        if (k < i + 1) {
            ans = '1';
            break;
        }
        ans = buf[i];
        break;
    }
    printf("%c", ans);
    return 0;
}

Measured memory_bytes: 128
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

func calcMinkowskiDistance(x, y []float64, p float64) float64 {
	d := 0.0
	for i := range x {
		d += math.Pow(math.Abs(x[i]-y[i]), p)
	}

	return math.Pow(d, 1/p)
}

func calcChebyshevDistance(x, y []float64) float64 {
	d := 0.0
	for i := range x {
		if d < math.Abs(x[i]-y[i]) {
			d = math.Abs(x[i] - y[i])
		}
	}
	return d
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanLines)

	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())

	sc.Scan()
	x := make([]float64, n)
	for i, s := range strings.Split(sc.Text(), " ") {
		x[i], _ = strconv.ParseFloat(s, 64)
	}

	sc.Scan()
	y := make([]float64, n)
	for i, s := range strings.Split(sc.Text(), " ") {
		y[i], _ = strconv.ParseFloat(s, 64)
	}

	fmt.Println(calcMinkowskiDistance(x, y, float64(1)))
	fmt.Println(calcMinkowskiDistance(x, y, float64(2)))
	fmt.Println(calcMinkowskiDistance(x, y, float64(3)))
	fmt.Println(calcChebyshevDistance(x, y))
}



Measured memory_bytes: 1140
#include<cstdio>
int const needs[10]={6,2,5,5,4,5,6,3,7,6};
bool canuse[10];
int dp[10001][10]={};
//dp[i][j]=i本のマッチ棒で作れる整数のうち最大のものに含まれる数字jの個数
bool larger(int *a,int *b){
    int asum=0,bsum=0;
    for(int i=0;i<10;i++){
        asum+=a[i];
        bsum+=b[i];
    }
    if(asum!=bsum)return (asum<bsum);
    for(int i=9;i>=0;i--){
        if(a[i]!=b[i])return (a[i]<b[i]);
    }
    return false;
}
int sumi(int *a){
    int ans=0;
    for(int i=0;i<10;i++){
        ans+=a[i]*needs[i];
    }
    return ans;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<10;i++)canuse[i]=false;
    for(int i=0;i<m;i++){
        int a;
        scanf("%d",&a);
        canuse[a]=true;
    }
    for(int i=0;i<10;i++){
        dp[0][i]=0;
    }
    for(int i=1;i<=n;i++){
        int dpi[10][10]={};
        //dpi[j][k]=数字jを1つ足してマッチ棒がi本になった場合の数字kの個数
        //（足せない場合は0）
        for(int j=1;j<10;j++){
            if(canuse[j]&&(needs[j]<=i)&&needs[j]+sumi(dp[i-needs[j]])==i){
                for(int k=0;k<10;k++){
                    dpi[j][k]=dp[i-needs[j]][k]+((k==j)?1:0);
                }
            }
        }
        int ans=0;
        for(int j=1;j<10;j++){
            if(larger(dpi[ans],dpi[j]))ans=j;
        }
        for(int k=1;k<10;k++){
            dp[i][k]=dpi[ans][k];
        }
    }
    //output-debug
    // for(int i=0;i<=n;i++){
    //     for(int j=0;j<10;j++){
    //         printf("%3d ",dp[i][j]);
    //     }
    //     printf("\n");
    // }
    //output
    for(int i=9;i>0;i--){
        for(int j=dp[n][i];j>0;j--)printf("%d",i);
    }
    return 0;
}

Measured memory_bytes: 512
# include "cstdio"
# include "iostream"

using namespace std;

long long d,n; 

int main(){
	long long ans=1; 
	scanf("%lld%lld",&d,&n);
	if(n==100){
		n++; 
	} 
	for(int i=1;i<=d;i++){
		ans*=100; 
	} 
	printf("%lld",ans*n); 
	return 0; 
} 

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define pb push_back
#define sc second
#define fr first
#define mk make_pair
#define ll long long
#define ii pair<int,int>
#define mp make_pair
using namespace std;
int n;
int memo[100005];
int a[100005];
int solve(int i)
{
    if(i == n-1)
    {
        return 0;
    }
    int &ret = memo[i];
    if(ret != -1)
        return ret;
    ret = 1e9;
    int s1 = abs(a[i]-a[i+1]);
    ret = min(ret , s1+solve(i+1));
    if(i+1 != n-1)
    {
        s1 = abs(a[i]-a[i+2]);
        ret = min(ret , s1+solve(i+2));
    }
    return ret;
}
int main()
{
    memset(memo,-1,sizeof(memo));
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cout<<solve(0);
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
int main(void){

   int n,a,b;
   std::cin>>n>>a>>b;
   int c = b-a;
   c = abs(c);
   if(c%2)
    std::cout<<"Borys"<<std::endl;
   else std::cout<<"Alice"<<std::endl;
   return 0;
}


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

int main(){
  int a,b;
  cin>>a>>b;
  cout<<"a";
  if(a<b) cout<<" < ";
  if(a>b) cout<<" > ";
  if(a==b) cout<<" == ";
  cout<<"b"<<endl;
  return 0;
}

Measured memory_bytes: 3084
#include<stdio.h>
int main(void)
{
	char m[4];
	int i;
	int a = 0,b = 0;
	int c = 0;

	scanf("%c%c%c",&m[0],&m[1],&m[2]);
	
	for(i = 0;i < 3;i++){
		if(m[i] == 'a'){
			a++;
		}
		if(m[i] == 'b'){
			b++;
		}
		if(m[i] == 'c'){
			c++;
		}
	}


	if(a == 1 && b == 1 && c == 1)
		printf("Yes\n");
	else    printf("No\n");

	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

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

  vector<string> maze(h);
  for (int y = 0; y < h; y++) {
    cin >> maze[y];
  }

  for (int y = 0; y < h; y++) {
    for (int x = 0; x < w; x++) {
      if (maze[y][x] == '#') {
        bool is_ok = false;
        for (int i = 0; i < 4; i++) {
          int nx = x+dx[i];
          int ny = y+dy[i];
          if (nx < 0 || ny < 0 || nx >= w || ny >=h) { continue; }
          if (maze[ny][nx] == '#') {
            is_ok = true;
          }
        }
        if (!is_ok) {
          cout << "No" << endl;
          return 0;
        }
      }
    }
  }
  cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (ll i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makel(N) ll N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007
#define re return 0
#define distance(x1,y1,x2,y2) sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

using namespace std;
using ll = long long int;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

template<typename T>
void maxi(T &a, T b) {
	a = max(a, b);
}

template<typename T>
void mini(T &a, T b) {
	a = min(a, b);
}

void exact_say(double x) {
	cout << setprecision(numeric_limits<double>::max_digits10) << x << endl;
}

const int max_comp = 50;
ll comp_table[50][50];
template <typename T>
T C(T x, T y) {
	if (y == 0 || x == y)return 1;
	else return comp_table[x][y] = comp_table[x][y] ? comp_table[x][y] : C(x - 1, y - 1) + C(x - 1, y);
}

int main() {
	ll ans = 0;
	ll ans1 = 0;
	ll ans2 = 0;
	ll n, a, b;
	cin >> n >> a >> b;
	vll v(n);
	rep(n)cin >> v[i];
	sort(rev(v));
	rep(a) ans1 += v[i];
	exact_say((double)ans1 / a);
	ans1 = 0;
	rep(a) {
		if (v[a - 1] == v[a - i - 1])++ans1;
	}
	rep(n - a) {
		if (v[a - 1] == v[a + i])++ans2;
	}
	if (v[0] != v[a - 1])ans = C(ans1 + ans2, ans1);
	else Rep(ans1, min(ans1 + ans2, b - a + ans1) + 1) {
		ans += C(ans1 + ans2, i);
	}
	say(ans);
}

Measured memory_bytes: 256
from math import ceil
from collections import deque
N, D, A = map(int, input().split())
Monsters = sorted([list(map(int, input().split())) for i in range(N)])
Monsters = [[x, ceil(h / A)] for x, h in Monsters]


acc_damage = 0
que = deque([])

ans = 0
for x, h in Monsters:
    # 期限切れの蓄積ダメージを削除
    while que and x > que[0][0]:
        limit, damage = que.popleft()
        acc_damage -= damage

    need = max(0, h - acc_damage)
    ans += need
    acc_damage += need

    if need:
        que.append([x + 2 * D, need])

print(ans)

Measured memory_bytes: 73212
#include <iostream>

using namespace std;

#define mod 1000000007

long long fact[1000005];


void precompute()	{
	for (int i = 1; i < 1000000; i++)	{
      	fact[i] = (i * (fact[i - 1] % mod)) % mod;
    }
}

long long power(int x, int y, int m)	{
	if (y == 0)
      	return 1;
  	long long p = (power(x, y / 2, m) % m);
  	p = ((p % m) * (p % m)) % m;
  	if (y % 2 == 0)
      	return p;
 	else
      	return ((x % m) * (p % m)) % m;
}

long long modinv(long long int x)	{
	return power(x, mod - 2, mod);
}

int main()	{
  	fact[0] = 1;
  	long long h, w, a, b;
  	precompute();
  	cin >> h >> w >> a >> b;
  	long long result = 0;
  	for (int i = 0; i <= w - b - 1; i++)	{
    	long long temp1 = ((fact[h - a + b + i - 1]) * modinv(fact[b + i]) % mod * modinv(fact[h - a - 1]) % mod) % mod;
      	long long temp2 = ((fact[w - b - i + a - 2]) * modinv(fact[w - b - 1 - i]) % mod * modinv(fact[a - 1]) % mod) % mod;
		long long temp = ((temp1 % mod) * (temp2 % mod)) % mod; 
     	result = ((result % mod) + (temp % mod)) % mod;
    }
  	cout << result % mod << endl;
  	return 0;
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[100001],b[100001];
pair<int,pair<int,int> > c[100001];
main(){
    cin>>n;
    long long ans=0;
    for(register int i=0;i<n;i++){
        scanf("%d%d",&a[i],&b[i]);
        c[i]=make_pair(a[i]+b[i],make_pair(a[i],b[i]));
    }
    sort(c,c+n);
    reverse(c,c+n);
    for(int i=0;i<n;i++){
        if(i%2==0)
            ans+=c[i].second.first;
        else
            ans-=c[i].second.second;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4096
S = input()
MOD = 10**9+7
DP = [0]*14 # A,AB,ABC,AB?,A?,A?C,A??,?,?B,?BC,?B?,??,??C,???
for i in range(len(S)):
    if S[i] == "A":
        DP[0] += 1
    elif S[i] == "B":
        for i in range(2,5,2):
            DP[i] += DP[i//2-1] 
            DP[i] %= MOD
    elif S[i] == "C":
        for i in range(6,13,2):
            DP[i] += DP[i//2-1]
            DP[i] %= MOD
    elif S[i] == "?":
        for i in range(6,13,2):
            DP[i+1] += DP[i//2-1]
            DP[i+1] %= MOD
        for i in range(2,5,2):
            DP[i+1] += DP[i//2-1] 
            DP[i+1] %= MOD    
        DP[1] += 1
q = DP[1]
Q0 = 3**q % MOD
Q1 = int(3**(q-1) % MOD)
Q2 = int(3**(q-2) % MOD)
Q3 = int(3**(q-3) % MOD)
Q = [0,0,0,0,0,0,Q0,Q1,Q1,Q2,Q1,Q2,Q2,Q3]
ans = 0
for i in range(14):
    ans += DP[i]*Q[i] % MOD
print(ans%MOD)

Measured memory_bytes: 44656
def nl(): return list(map(int, input().split()))

n, k = nl()
x = nl()

ans = float('inf')
for i in range(n - k + 1):
    ans = min(
            ans,
            abs(x[i]) + abs(x[i + k - 1] - x[i]),
            abs(x[i + k - 1]) + abs(x[i + k - 1] - x[i]),
        )
print(ans)

Measured memory_bytes: 14224
N,M = map(int, input().split())
mod = 1000000007
dp = [1 for _ in range(N+1)]
for i in range(M):
	dp[int(input())] = 0
for i in range(2,N+1):
	if dp[i] != 0:
		dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[N])

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

int main(void){
	int a, b, d, r;
	double f;
	cin >> a >> b;
	cout << a / b << " " << a%b << " " << fixed << setprecision(10) << double(a) / double(b) << endl;
    return 0;
}

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

int main(){
  int N,Y;
  cin >> N >> Y;
  bool a=false;
  for(int i=0;i<N+1;i++){
    for(int j=0;j<N+1;j++){
      int C=N-i-j;
      if(C<0){
        continue;
      }
      if(i*10000+j*5000+C*1000==Y){
        cout << i << " " << j << " " << C << endl;
        a=true;
        break;
      }
    }
    if(a){
      break;
    }
  }
  if(!a){
    cout << -1 << " " << -1 << " " << -1 << endl;
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 300

int main(void)
{
  int H,W;
  while(1){
    
    cin >> H >> W;
    if(H == 0 && W == 0) break;
    
    for(int i = 0;i < H;i++){
      for(int j = 0;j < W;j++){
        if(i == 0 || i == H - 1 || j == 0 || j == W - 1) printf("#");
        else printf(".");
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0; 
} 

Measured memory_bytes: 1112
<?php
  
  fscanf(STDIN,"%s",$n);
$d_li = explode(" ",trim(fgets(STDIN)));
sort($d_li);
$center_r = $d_li[count($d_li)/2];
$center_l = $d_li[count($d_li)/2-1];

echo ($center_r-$center_l)."\n";

Measured memory_bytes: 12792
import bisect
N = int(input())
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
C = list(map(int, input().split(" ")))
A.sort()
B.sort()
C.sort()

ans = 0
for b in B:
    i = bisect.bisect_left(A, b)
    j = bisect.bisect_right(C, b)
    ans += i * (N - j)
print(ans)

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

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> jun(n);
    rep(i,n){
        cin>>a[i];
        jun[a.at(i)-1]=i+1;
    }
    rep(i,n){
        cout<<jun[i]<<" ";
    }
    cout<<endl;
}

Measured memory_bytes: 3964
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;

ll dp[114][114514];

int main(){
	ll N,W;
	cin>>N>>W;
	vector<ll>w(N),v(N);
	for(int i=0;i<N;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=0;i<114;i++){
		for(int j=0;j<114514;j++){
			dp[i][j]=1145141919;
		}
	}
	dp[0][0]=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<114514;j++){
			if(j>=v[i])dp[i+1][j]=min(dp[i+1][j],dp[i][j-v[i]]+w[i]);	
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
		}
	}
	ll ans=0;
	for(int i=0;i<114514;i++){
		if(dp[N][i]<=W)ans=i;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 102400
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

//#define debug(x) ;
#define debug(x) cerr << #x << " = " << x << "\n";

ostream& operator<<(ostream& cerr, vector<ll> aux) {
  cerr << "[";
  for (auto e : aux) cerr << e << ' ';
  cerr << "]";
  return cerr;
}

const int maxT = 200011;
const int maxN = 600011;

struct node {
  int data;
  node* son[3];

  node() {
    data = 0;
    memset(son, 0, sizeof(son));
  }
};

int n, t;
int id[3], sol[maxN], cnt;
char s[maxT];
node* head;

void build(node* act, int lvl, int curr, int step) {
  if (lvl == n) {
    act->data = curr;
    return;
  }

  act->son[0] = new node();
  act->son[1] = new node();
  act->son[2] = new node();

  build(act->son[0], lvl + 1, curr, step * 3);
  build(act->son[1], lvl + 1, curr + step, step * 3);
  build(act->son[2], lvl + 1, curr + 2 * step, step * 3);
}

void salsa() {
  swap(id[1], id[2]);
}

void rumba(node* act, int lvl) {
 if (lvl == n) return;

 node* aux = act->son[id[2]];
 act->son[id[2]] = act->son[id[1]];
 act->son[id[1]] = act->son[id[0]];

 act->son[id[0]] = aux;
 rumba(act->son[id[0]], lvl + 1);
}

void print(node* act, int lvl, int curr, int step) {
  if (lvl == n) {
    sol[act->data] = curr;
    cnt++;
    return;
  }

  print(act->son[id[0]], lvl + 1, curr, step * 3);
  print(act->son[id[1]], lvl + 1, curr + step, step * 3);
  print(act->son[id[2]], lvl + 1, curr + 2 * step, step * 3);
}

int main()
{
  //freopen("test.in", "r", stdin);

  scanf("%d\n%s", &n, s);
  t = strlen(s);

  head = new node();
  build(head, 0, 0, 1);

  for (int i = 0; i < 3; i++) 
    id[i] = i;
   
  for (int i = 0; i < t; i++) {
    if (s[i] == 'S')
      salsa();
    else
      rumba(head, 0);
  }

  print(head, 0, 0, 1);
  for (int i = 0; i < cnt; i++)
    printf("%d ", sol[i]);

  return 0;
}


Measured memory_bytes: 43688
/*
注意范围！
short范围：-32768~32767
unsigned short范围：0~65535
int范围：-2147483648~2147483647
uint范围：0~4294967295
INT范围：-9223372036854775808~9223372036854775807
UINT范围：0~18446744073709551615
float范围：-3.4e38～3.4e38，精度：6~7位
double范围：-1.7e308~1.7e308，精度：15~16位
ldouble范围：-1.2e4932~1.2e4932，精度：18~19位
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define LL long long
#define pb push_back
#define pob pop_back
#define mp make_pair
#define FILL(a,v) memset((void*)a,v,sizeof(a))
#define FILL0(a) FILL(a,0)
#define FILL1(a) FILL(a,-1)
#define ALL(a) (a).begin(),(a).end()
#define Inf 1e9
#define Mod 1000000007
#define foreach(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define FOR(i,x) for(int i=0;i<x;i++)
#define RFOR(i,x) for(int i=x-1;i>=0;i--)
#define FFOR(i,a,b) for(int i=a;i<b;i++)
#define FRFOR(i,a,b) for(int i=a-1;i>=b;i--)
#define SZ(a) ((int)(a).size())
#define FI first
#define SE second
#define OVER(a) return puts(a),0
#define fastio ios::sync_with_stdio(0)
#define filei(f) freopen(f,"r",stdin)
#define fileo(f) freopen(f,"w",stdout)
using namespace std;
typedef pair<int,int> pii;
typedef unsigned long long UINT;
typedef unsigned int Uint;
typedef long long INT;
typedef pair<INT,INT> PII;

vector<int> aa[200007];
int n,m,a,b;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&a,&b);
		aa[a].pb(b);
		aa[b].pb(a);
	}
	for(int i=0;i<SZ(aa[1]);i++)
	{
		int dis=aa[1][i];
		for(int j=0;j<SZ(aa[dis]);j++)
			if(aa[dis][j]==n)
				OVER("POSSIBLE");
	}
	OVER("IMPOSSIBLE");
}


Measured memory_bytes: 12016
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static void gcd(int a, int b){
            int x = Math.max(a,b);
            int y = Math.min(a,b);
            int t = 0;
            while (y>0){
                t = x;
                x = y;
                y = t%y;
            }
            System.out.println(x);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int a = Integer.parseInt(line[0]);
        int b = Integer.parseInt(line[1]);
        gcd(a,b);
    }
}

Measured memory_bytes: 17092
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <limits>
#include <cmath>
#include <cassert>
#include <map>

using namespace std;
using ll = long long;

const int INF = 1<<30;
const int MOD = (int)1e9 + 7;
const int MAX_N = (int)1e5 + 5;
const int dy[] = {0, 1, 0, -1};
const int dx[] = {-1, 0, 1, 0};
#define debug(x) cout << #x << ": " << x << endl

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin >> n, n)
    {
        map<int, pair<int, int>> mp;
        mp[0] = make_pair(250, 250);
        for(int i = 1; i < n; i++)
        {
            int m, d; cin >> m >> d;
            pair<int, int> p = mp[m];
            mp[i] = make_pair(p.first + dy[d], p.second + dx[d]);
        }
        int table[600][600] = {};
        for(auto x : mp) table[x.second.first][x.second.second] = 1;
        int b = 0, t = 600, l = 600, r = 0;
        for(int i = 0; i < 600; i++)
        {
            for(int j = 0; j < 600; j++)
            {
                if(table[i][j]) t = min(t, i);
            }
        }
        for(int i = 599; i >= 0; i--)
        {
            for(int j = 0; j < 600; j++)
            {
                if(table[i][j]) b = max(b, i);
            }
        }
        for(int j = 0; j < 600; j++)
        {
            for(int i = 0; i < 600; i++)
            {
                if(table[i][j]) l = min(l, j);
            }
        }
        for(int j = 599; j >= 0; j--)
        {
            for(int i = 0; i < 600; i++)
            {
                if(table[i][j]) r = max(r, j);
            }
        }
        cout << r - l  + 1 << " " << b - t + 1 << endl;
    }
    return 0;
}




Measured memory_bytes: 4568
n,m = map(int,input().split())
lst = [0] * (n+2)
for _ in range(m):
	l,r = map(int, input().split())
	lst[l] += 1
	lst[r+1] -= 1
ans = 0
for i in range(1,n+1):
	lst[i] = lst[i-1] + lst[i]
	if lst[i] == m:
		ans += 1
print(ans)

Measured memory_bytes: 7028
#include <bits/stdc++.h>
using namespace std;
#define inf (1<<16)

int main(){
	int n;cin>>n;
	int a[12]={1,6,9,36,81,216,729,1296,6561,7776,46656,59049};
	vector<long long int> dp(n+1,inf);
	dp[0]=0;
	for(int i=0;i<=n;++i){
		for(int j=0;j<12;++j){
			if(i+a[j]<=n)dp[i+a[j]]=min(dp[i+a[j]],dp[i]+1);
		}
	}
	cout<<dp[n]<<endl;
}


Measured memory_bytes: 1024
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let mut seq = vec![0; n];
    for i in 0..n {
        seq[i] = read::<usize>();
    }
    let mut cnt = 0;
    let mut anss = vec![0; n];
    for i in (0..n).rev() {
        let mut sum = 0;
        let mut v = i + 1;
        while v <= n {
            sum += anss[v - 1];
            v += i + 1;
        }
        if sum % 2 != seq[i] {
            cnt += 1;
            anss[i] = 1;
        }
    }
    let mut first = true;
    println!("{}", cnt);
    for i in 0..n {
        if anss[i] == 1 {
            if !first {
                print!(" ");
            }
            print!("{}", i + 1);
            first = false;
        }
    }
}


Measured memory_bytes: 9084
main :: IO()
main = do
  n <- readLn :: IO Int
  str <- getLine
  let times = findSubStr str
  print times
  where
    findSubStr :: String -> Int
    findSubStr [] = 0
    findSubStr (s:ss) = findABC str + findSubStr ss
      where
        str = [s]++ss
        substr (list) 0 m = take m list
        substr (l:ls) n m = substr ls (n - 1) m
        findABC :: String -> Int
        findABC [] = 0
        findABC str = if (substr str 0 3 == "ABC") then 1 else 0

Measured memory_bytes: 508
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const ll INF=1000000000000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

int main(){
	static ll n,m;
	static ll l[200010],r[200010],d[200010];
	scanf("%lld%lld",&n,&m);
	rep(i,m)scanf("%lld%lld%lld",&l[i],&r[i],&d[i]);
	
	static vector<P> G[100010];
	rep(i,m){
		G[l[i]].pb(P(r[i],d[i]));
		G[r[i]].pb(P(l[i],-d[i]));
	}
	
	static ll x[100010];
	rep(i,100010)x[i] = -INF;
	rep1(i,n){
		if(x[l[i]] != -INF)continue;
		x[l[i]] = 0;
		queue<int> que;
		que.push(l[i]);
		while(!que.empty()){
			int q = que.front(); que.pop();
			rep(j,G[q].size()){
				if(x[G[q][j].fr] != -INF)continue;
				x[G[q][j].fr] = x[q] + G[q][j].sc;
				que.push(G[q][j].fr);
			}
		}
	}
	
	rep(i,m){
		if(x[l[i]] + d[i] != x[r[i]]){
			puts("No");
			return 0;
		}
	}
	puts("Yes");
}



Measured memory_bytes: 18560
main :: IO ()
main = do
  n <- read <$> getLine :: IO Integer
  let a = f (n `div` 3) * 3
      b = f (n `div` 5) * 5
      c = f (n `div` 15) * 15
      f x = (1 + x) * x `div` 2
  putStrLn $ show $ (f n) - a - b + c


Measured memory_bytes: 3856
my ($n, $k) = split(/\s+/, <>);
my $mod = 1e9+7;

sub sigma {
    my ($from, $to) = @_;
    return ($from+$to)/2*($to-$from+1);
}

my $sum = 0;
while ($k-1 <= $n) {
    $sum += sigma($n-$k+1, $n) - sigma(0, $k-1) + 1;
    $sum %= $mod;
    $k++;
}

print $sum, "\n";


Measured memory_bytes: 4824
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mp make_pair
#define pb push_back
#define pll pair<ll,ll>
#define INF 1000000007
ll n;
ll arr[100005][3]= {0};
ll vis[100005][3] = {0};
ll ansi[100005][3];


int dp(ll pos,ll last)
{
	if(pos-1==n)
	{
		return 0;
	}
	if(vis[pos][last]!=0)
	{
		return ansi[pos][last];
	}
	vis[pos][last] = 1;
	ll ans = 0;
	for(ll i=0;i<3;i++)
	{
		if(i!=last)
		{
			ans = max(ans,arr[pos][i]+dp(pos+1,i));
		}
	}
	return ansi[pos][last] = ans;
}



int main()
{
	ll i,j,k;
	cin>>n;
	//ll arr[n+1];
	ll d,e,f;

	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld%lld",&arr[i][0],&arr[i][1],&arr[i][2]);
	}
	ll a = dp(1,0);
	ll b = dp(1,1);
	ll c = dp(1,2);
	cout<<max(a,max(b,c))<<endl;
	return 0;

}

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

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

Measured memory_bytes: 256
using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using System.Numerics;

namespace competitive
{
    class Program
    {
        static void Main(string[] args)
        {
            var scanner = new Scanner();
            var x = scanner.NextInt();
            if (x >= 1200)
            {
                Console.WriteLine("ARC");
            }
            else
            {
                Console.WriteLine("ABC");
            }
        }
    }

    public static class Extensions
    {
        public static int ToInt(this string str) => int.Parse(str);
        public static double ToDouble(this string str) => double.Parse(str);
        public static long ToLong(this string str) => long.Parse(str);
        public static BigInteger ToBigInteger(this string str) => BigInteger.Parse(str);
    }

    public class Scanner
    {
        private TextReader reader;
        public Scanner()
        {
            reader = Console.In;
        }
        public Scanner(TextReader reader)
        {
            this.reader = reader;
        }
        private string NextWord()
        {
            var sb = new StringBuilder();
            while (true)
            {
                var c = reader.Read();
                if (c == -1 || c == 13 || c == 10)
                {
                    break;
                }
                sb.Append((char)c);
            }
            return sb.ToString();
        }
        public int NextInt()
        {
            return NextWord().ToInt();
        }
        public string Next()
        {
            return NextWord();
        }
        public double NextDouble()
        {
            return NextWord().ToDouble();
        }
        public long NextLong()
        {
            return NextWord().ToLong();
        }
        public BigInteger NextBigInteger()
        {
            return NextWord().ToBigInteger();
        }
        public string NextLine()
        {
            return reader.ReadLine();
        }
    }
}


Measured memory_bytes: 11348
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func Scan() string {
	sc.Scan()
	return sc.Text()
}

func iScan() int {
	n, _ := strconv.Atoi(Scan())
	return n
}

func fScan() float64 {
	n, _ := strconv.ParseFloat(Scan(), 64)
	return n
}
func stringToInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}
func SScan(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = Scan()
	}
	return a
}
func iSScan(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = iScan()
	}
	return a
}
func abs(x int) int {
	if x < 0 {
		x = -x
	}
	return x
}
func larger(a, b int) int {
	if a < b {
		return b
	} else {
		return a
	}
}
func smaller(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}
func max(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x < a[i] {
			x = a[i]
		}
	}
	return x
}
func min(a []int) int {
	x := a[0]
	for i := 0; i < len(a); i++ {
		if x > a[i] {
			x = a[i]
		}
	}
	return x
}
func sum(a []int) int {
	x := 0
	for _, v := range a {
		x += v
	}
	return x
}

var mod int = 1000000007

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, mod)
	sc.Split(bufio.ScanWords)
	a := iSScan(5)
	b := make([]int, 5)
	ans := 0
	for i, v := range a {
		ans += (v + 9) / 10 * 10
		b[i] = (v+9)/10*10 - v
	}
	fmt.Println(ans - max(b))
}


Measured memory_bytes: 1772
#define yuki(x, y) for(int i = x; i < (y); ++i)
#define yukj(x, y) for(int j = x; j < (y); ++j)
#define yukii(x, y) for(int i = x; i <= (y); ++i)
#define yukji(x, y) for(int j = x; j <= (y); ++j)
#define yuk(x, y, z) for(int x = y; x < (z); ++x)
#define yui(x, y, z) for(int x = y; x >= (z); --x)
#define sclr(x) memset(x, 0, sizeof(x))
#define sclr1(x) memset(x, -1, sizeof(x))
#define scl(x, y) memset(x, y, sizeof(x))
#define ft first
#define sc second
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long lol;
char s[101000];
int gcnt, pcnt;
int main(int argc, char **argv)
{
	scanf("%s", s);
	int l = strlen(s);
	yuki(0, l) if(s[i] == 'g') ++gcnt;
	else ++pcnt;
	printf("%d\n", (l>>1)-pcnt);
	return 0;
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = INT_MAX / 2;
const ll  inf = LLONG_MAX / 2;
const int mod = 1000000007;
const int MAX_N = 101010;
const long double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	/*------------------------------*/

	ll q, h, s, d, n;
	cin >> q >> h >> s >> d >> n;

	ll a = min(q * 4, min(h * 2, s));
	cout << min(a * n, d * (n / 2) + a * (n % 2)) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>

char field[12][12];

void rec(int i, int j){
	field[i][j] = '0';

	if (field[i + 1][j] == '1' && i + 1 < 12) rec(i + 1, j);
	if (field[i - 1][j] == '1' && i - 1 > -1) rec(i - 1, j);
	if (field[i][j + 1] == '1' && j + 1 < 12) rec(i, j + 1);
	if (field[i][j - 1] == '1' && j - 1 > -1) rec(i, j - 1);

}
int main(){
	int count = 0;
	
	while(1){
		bool end = false;
		for (int i = 0; i < 12; i++){
			if (scanf("%s", &field[i]) == EOF) end = true;
		}
		if (end) break;
		count = 0;
		for (int i = 0; i < 12; i++){
			for (int j = 0; j < 12; j++){
				if (field[i][j] == '1'){
					rec(i, j);
					count++;
				}
			}
		}
		printf("%d\n", count);
	}
	return 0;
}

Measured memory_bytes: 976
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define P 1000000007
#define inf 1e18
int main()
{
    string s;
    cin >> s;
    ll n = s.length();
    ll left[n + 2];
    ll right[n + 2];
    right[n] = 0;
    ll count = 0;
    for (ll i = n - 1; i >= 0; i--)
    {
        if (s[i] == '>')
        {
            count++;
            right[i] = count;
        }
        else
        {
            count = 0;
            right[i] = 0;
        }
    }

    left[0] = 0;
    count = 0;
    for (ll i = 0; i < n; i++)
    {
        if (s[i] == '<')
        {
            count++;
            left[i + 1] = count;
        }
        else
        {
            count = 0;
            left[i + 1] = 0;
        }
    }
    ll ans = 0;
    for (ll i = 0; i <= n; i++)
    {
        ans = ans + max(left[i], right[i]);
    }
    cout << ans << "\n";

    return (0);
}


Measured memory_bytes: 11680
'use strict'
const lines = require('fs').readFileSync(0, 'utf8').split('\n')
const firstLine = lines[0].split(' ').map(Number)
const N = firstLine[0]
const W = firstLine[1]
var dp = new Array(N + 1);
for(var i = 0; i < N + 1; i++){
  dp[i] = new Array(W + 1).fill(0);
}

for (let i=0;i < N;++i) {
  const tmp = lines[i+1].split(' ').map(Number)
  const value = tmp[1];
  const weight = tmp[0];
  for (let w=0; w<=W; ++w) {
    if (w - weight >= 0) {
      dp[i+1][w] = Math.max(dp[i+1][w], dp[i][w-weight] + value)
    }
    dp[i+1][w] = Math.max(dp[i+1][w], dp[i][w])
  }
}
console.log(dp[N][W])

Measured memory_bytes: 188416
//pragma
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define YOU using
#define DONT namespace
#define SAY std

YOU DONT SAY;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;

#define REPP(i,a,b,d) for(int i=a;i<=b;i+=d)
#define REP(i,a,b) REPP(i,a,b,1)
#define REVV(i,a,b,d) for(int i=a;i>=b;i-=d)
#define REV(i,a,b) REVV(i,a,b,1)

#define FOR(i,a) for(int i=0; i<a; i++)
#define FORD(i,a) for(int i=(int)a-1; i>=0; i--)

#define pb push_back
#define F first
#define S second

const int OO = 1e9;
const ll INF = 1e18;

const int irand(int lo,int hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

const ll lrand(ll lo,ll hi){
	return ((double)rand()/(RAND_MAX + 1.0)) * (hi-lo+1) + lo;
}

#define getc getchar
template<typename T>
T getnum(){
	int sign = 1;
	T ret = 0;
	char c;

	do{
		c = getc();
	}while(c == ' ' || c == '\n');
	if(c == '-')sign = -1;
	else ret = c-'0';
	while(1){
		c = getc();
		if(c < '0' || c > '9')break;
		ret = 10*ret + c-'0';
	}
	return sign * ret;
}

inline void ini(int& x){
	x = getnum<int>();
}

inline void scani(int& x){
	scanf("%d",&x);
}

//end of macro

const ll MOD = 1e9 + 7;
inline ll addmod(ll a, ll b){
	return (a+b)%MOD;
}
inline ll mulmod(ll a, ll b){
	return (a*b)%MOD;
}

int n;
int cnt[66][2];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #define endl '\n'
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    cout.precision(10);
    
    cin>>n;
    ll ans = 0;
    REP(i,1,n){
    	ll x;
    	cin>>x;
    	
    	ll mul = 1;
    	FOR(i,60){
    		bool key = (x & mul) > 0;
    		ans = addmod(ans, mulmod(cnt[i][key^1], mul % MOD));
    		cnt[i][key]++;
    		
    		mul <<= 1;
		}
	}
	
	cout << ans << endl;
    
    return 0;
}

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

const int N = 200010;

std::pair <int, int> p[N];
int sufmax[N], sufmin[N];
int n;

ll calc(){
	int max = 0, max1 = 0, min = INT_MAX, min1 = INT_MAX;
	for (int i = 0; i < n; ++ i){
		max = std::max(max, p[i].first);
		max1 = std::max(max1, p[i].second);
		min = std::min(min, p[i].first);
		min1 = std::min(min1, p[i].second);
	}
	return 1ll * (max - min) * (max1 - min1);
}

int main(){
	scanf("%d", &n);
	int max = 0, min = INT_MAX, sit1, sit2;
	for (int i = 0; i < n; ++ i){
		scanf("%d%d", &p[i].second, &p[i].first);
		if (p[i].first > p[i].second){
			std::swap(p[i].first, p[i].second);
		}
	}
	if (n == 1){
		return printf("0\n"), 0;
	}
	ll ans = calc();
	std::sort(p, p + n);
	sufmin[n] = INT_MAX;
	for (int i = n - 1; i >= 0; -- i){
		sufmax[i] = std::max(sufmax[i + 1], p[i].first);
		sufmin[i] = std::min(sufmin[i + 1], p[i].first);
	}
	int nowmax = 0, nowmin = INT_MAX;
	for (int i = 0; i < n; ++ i){
		int x = std::max(nowmax, sufmax[i]), y = std::min(nowmin, sufmin[i]);
		int _x = std::max(std::max(nowmax, p[i].second), sufmax[i + 1]), _y = std::min(std::min(nowmin, p[i].second), sufmin[i + 1]);
		if (_x - _y <= x - y){
			std::swap(p[i].first, p[i].second);
		}
		nowmax = std::max(nowmax, p[i].first);
		nowmin = std::min(nowmin, p[i].first);
	}
	return printf("%lld\n", std::min(calc(), ans)), 0;
}

Measured memory_bytes: 3328