akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll a[200010];
ll sum[200010];
ll dp[200010][2][3];
ll n;
ll func(ll here, ll ch, ll ch1)
{
	if (ch1 >= 3)return sum[here];
	if (here == n + 1)return 0;
	ll &ret = dp[here][ch][ch1];
	if (ret != -1)return ret;
	ret = 9999999999999999;
	if (ch1 < 3)
	{
		ret = min(ret, func(here, ch ^ 1, ch1 + 1));
	}
	if (a[here] == 0)
	{
		if (ch == 0)
			ret = min(ret, func(here + 1, ch, ch1) + 2);
		else
			ret = min(ret, func(here + 1, ch, ch1) + 1);
	}
	else
	{
		if (ch == a[here] % 2)
			ret = min(ret, func(here + 1, ch, ch1));
		else
			ret = min(ret, func(here + 1, ch, ch1) + 1);
	}
	return ret;
}
int main()
{
	memset(dp, -1, sizeof(dp));
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	for (int i = n; i >= 1; i--)
		sum[i] = sum[i + 1] + a[i];
	ll dap = 9999999999999999;
	ll sum1 = 0;
	for (int i = 1; i <= n; i++)
	{
		dap = min(func(i, 0, 0) + sum1, dap);
		sum1 += a[i];
	}
	printf("%lld", dap);
}


Measured memory_bytes: 22016
#include <iostream>
using namespace std;
int main(void){
    int H,W;
    for(;;){
        cin>>H>>W;
        if(H==0&&W==0){
            break;
        }
        for(int i=0;i<W;i++){
            cout<<'#';
        }
        cout<<endl;
        for(int i=2;i<H;i++){
            cout<<'#';
          for(int i=2;i<W;i++){
              cout<<'.';
   
          }
   cout<<'#'<<endl;

        }
      
         for(int i=0;i<W;i++){
            cout<<'#';
        }
        cout<<endl;
        cout<<endl;
    }
}


Measured memory_bytes: 3044
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string S;
    string T;
    cin >> S;
    cin >> T;

    string t_;
    
    for(auto it = T.begin(); it != T.end()-1; ++it)
    {
        t_.push_back(*it);
    }

    if (S == t_)
    {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3628
fn main() {
    let input: Vec<i32> = read_vec();
    let (n, d) = (input[0], input[1]);

    let mut points: Vec<(i32, i32)> = Vec::new();
    for _ in 0..n {
        let input: Vec<i32> = read_vec();
        points.push((input[0], input[1]));
    }

    println!("{}", solve(d, &points));
}

fn read<T: std::str::FromStr>() -> T {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    buf.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|s| s.parse().ok().unwrap())
        .collect()
}

fn solve(d: i32, points: &[(i32, i32)]) -> i32 {
    points
        .iter()
        .filter(|&&(x, y)| {
            let (x, y) = (x as i64, y as i64);
            let d = d as i64;
            x * x + y * y <= d * d
        })
        .count() as i32
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_solve_1() {
        let ps = vec![(0, 5), (-2, 4), (3, 4), (4, -4)];
        assert_eq!(3, solve(5, &ps));
    }

    #[test]
    fn test_solve_2() {
        let ps = vec![
            (1, 1),
            (1, 1),
            (1, 1),
            (1, 1),
            (1, 2),
            (1, 3),
            (2, 1),
            (2, 2),
            (2, 3),
            (3, 1),
            (3, 2),
            (3, 3),
        ];
        assert_eq!(7, solve(3, &ps));
    }

    #[test]
    fn test_solve_3() {
        let ps = vec![
            (14309, -32939),
            (-56855, 100340),
            (151364, 25430),
            (103789, -113141),
            (147404, -136977),
            (-37006, -30929),
            (188810, -49557),
            (13419, 70401),
            (-88280, 165170),
            (-196399, 137941),
            (-176527, -61904),
            (46659, 115261),
            (-153551, 114185),
            (98784, -6820),
            (94111, -86268),
            (-30401, 61477),
            (-55056, 7872),
            (5901, -163796),
            (138819, -185986),
            (-69848, -96669),
        ];
        assert_eq!(6, solve(100_000, &ps));
    }
}


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

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

using ll = long long;
using pii  = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

int main(){
    int a;
    cin >> a;
    cout << (a + a*a + a*a*a) << endl;
    return 0;
}


Measured memory_bytes: 3620
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

const int MOD = 1000000007, INF = 1111111111;
using namespace std;
using lint = long long;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (int i = 0; i < (int)vec.size(); i++) {
		os << vec[i] << (i + 1 == vec.size() ? "" : " ");
	}
	return os;
}

#ifdef _DEBUG
template <class Head>
void dump(const char* str, Head &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + 1, t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

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

	int N;
	cin >> N;

	lint ans = 0;
	int l, r;
	for (int i = 0; i < N; i++) {
		cin >> l >> r;
		ans += r - l + 1;
	}

	cout << ans << "\n";

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll ,P> P3;
typedef pair<P ,P> PP;
const ll MOD = ll(1e9+7);
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-6;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()


int main() {
    int cnt[2]{};
    string s;
    cin >> s;
    REP(i,s.size()){
        if(s[i]-'0'!=i%2)cnt[0]++;
        if(s[i]-'0'!=(i+1)%2)cnt[1]++;
    }
    cout << min(cnt[0],cnt[1]) << endl;
    return 0;
}

Measured memory_bytes: 512
import sys
import bisect

def main():
  input = sys.stdin.readline
  inf = pow(10, 18)
  a, b, q = map(int, input().split())
  s = [-inf]+[int(input()) for _ in range(a)]+[inf]
  t = [-inf]+[int(input()) for _ in range(b)]+[inf]
  
  for _ in range(q):
    x = int(input())
    i = bisect.bisect_left(s, x)
    j = bisect.bisect_left(t, x)
    ans = inf
    for l in range(-1, 1):
      for m in range(-1, 1):
        sub = min([abs(x-s[i+l]), abs(x-t[j+m])])+abs(s[i+l]-t[j+m])
        if ans > sub:
          ans = sub
    print(ans)

if __name__ == "__main__":
  main()

Measured memory_bytes: 12800
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
using ll = long long;
using namespace std;

const long long MOD = 1000000007;
const ll LINF = 1LL << 50;


int main() {
  int N;
  cin >> N;
  vector<pair <ll, ll>> task;

  REP(n,N){
    ll a, b;
    cin >> a >> b;
    task.emplace_back(b,a);
  }

  sort(task.begin(), task.end());

  ll sum = 0;
  bool flag = true;

  for(auto v : task){
    sum += v.second;
    
    if (sum > v.first) {
      flag = false;
      break;
    }
  }

  if (flag == true) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

}


Measured memory_bytes: 7460
#include<stdio.h>
int main(void){
	
	int a,b;
	
	scanf("%d %d", &a, &b);
	
	int c = a * b;
	
	if(c % 2 == 0){
		printf("Even\n");
	}else{
		printf("Odd\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
n = int(input())

taxoff = n/1.08
ans = int(taxoff)
if n == int(ans*1.08):
    print(int(n/1.08))
elif n == int((ans+1)*1.08):
    print(ans+1)
elif n == int((ans-1)*1.08):
    print(ans-1)
else:
    print(":(")

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        String[] color = new String[2];
        int[] num = new int[2];
        Scanner scanner = new Scanner(System.in);
        color[0] = scanner.next();
        color[1] = scanner.next();
        num[0] = Integer.parseInt(scanner.next());
        num[1] = Integer.parseInt(scanner.next());
        if (scanner.next().equals(color[0])) {
            num[0] = num[0]-1;
        }else {
            num[1] = num[1]-1;
        }
        System.out.println(num[0]+" "+num[1]);
    }
}

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

#define DEBUG 0

#if DEBUG
  #define DLOG(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DLOG(...)
#endif

void debug(auto f) {
#if DEBUG
  f();
#endif
}

ll N, A, B;
vector<ll> p;
vector<ll> pos;
vector<ll> tbl;

void showtbl() {
  debug([]() {
      for (ll i = 0; i < 2*N+1; i++)  cerr << tbl.at(i) << ", ";
      cerr << endl;
    });
}

int main() {
#if !DEBUG
  ios_base::sync_with_stdio(false);
#endif

  cin >> N >> A >> B;
  p.resize(N);
  pos.resize(N);
  for (ll i = 0; i < N; i++)  {
    ll x;
    cin >> x;
    p.at(i) = x - 1;
  }
  for (ll i = 0; i < N; i++)  pos[p.at(i)] = i;
  tbl.resize(2*N+1);
  /*
    2*i+1 ... just i
    2*i+2 ... (i, i+1)
   */

  for (ll k = 0; k < N; k++) {
    ll i0 = pos.at(k);
    for (ll i = 0; i <= 2*i0; i++)  tbl.at(i) += B;
    for (ll i = 2*i0 + 2; i < 2*N + 1; i++)  tbl.at(i) += A;
    showtbl();
    for (ll i = 1; i < 2*N+1; i++) {
      tbl.at(i) = min(tbl.at(i-1), tbl.at(i));
    }
    showtbl();
  }
  cout << tbl.at(2*N) << endl;

  return 0;
}



Measured memory_bytes: 384
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)

typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;

constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main() {
    int n; cin>>n;
    deque<int> ans;
    REP(i,n) {
        int a;
        cin>>a;
        if (i%2==0) ans.push_back(a);
        else ans.push_front(a);
    }
    if (n%2==1) REP(i,n) cout<<ans[n-1-i]<<" ";
    else REP(i,n) cout<<ans[i]<<" ";
}


Measured memory_bytes: 2944
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int H,W,N;
int main()
{
    scanf("%d%d%d",&N,&H,&W);
    int ans=0;
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(i+H-1<=N&&j+W-1<=N) ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}



Measured memory_bytes: 256
#include <cstdio>

using namespace std;

int main()
{
  int k, s;
  int i;
  long long ans = 0;
  int target;

  scanf("%d %d", &k, &s);

  // exhaustion

  for (i=0; i<=k; i++) {
    target = s - i;
    if (target < 0) break;
    if (target > 2 * k) {
      continue;
    } else if (target >= k) {
      ans += (2 * k) - target + 1;
    } else {
      ans += target + 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 1712
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = na()

    total = sum(a)

    sunuke = 0
    ans = sys.maxsize
    for i in range(n - 1):
        sunuke += a[i]
        ans = min(ans, abs(total - sunuke*2))

    print(ans)

if __name__ == '__main__':
    main()


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

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

long long MOD = 1000000000 + 7;

int main(){
  cout << setprecision(10);
  int H,W;
  cin >> H >> W;

  string up = "";
  for(int i = 0; i < W+2; i++){
    up += "#";
  }
  cout << up << endl;

  for(int i = 0; i < H; i++){
    string tmp;
    cin >> tmp;
    tmp = "#" + tmp + "#";
    cout << tmp << endl;
  }
  cout << up << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

#define REP(i,p,n) for(ll i=p;i<ll(n);++i)
#define rep(i,n) REP(i,0,n)

using ll = long long int;
using pll = pair<ll, ll>;

const ll mod = static_cast<ll>(1e9) + 7;

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

    vector<ll> p(n);
    rep (i, n) { cin >> p[i]; }

    bool ans = true;
    rep (i, n - 1) { ans &= p[i] <= p[i + 1]; }

    for (ll i=0;i<n;++i)
    for (ll j=i+1;j<n;++j)
    {
        const ll tmp = p[j];
        p[j] = p[i];
        p[i] = tmp;

        bool ok = true;
        rep (k, n - 1) { ok &= p[k] <= p[k + 1]; }

        ans = ans || ok;

        p[i] = p[j];
        p[j] = tmp;
    }

    cout << (ans ? "YES" : "NO") << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)




int main() {
	int N;
	cin >>N;
	if (N == 1) {
		cout << "Hello World" << endl;
	}
	else {
		int A, B;
		cin >> A >> B;
		cout << A+B << endl;
	}
	
}

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

using namespace std;
typedef long long ll;

void solve(){
    int x;
    cin >> x;
    cout << 1 - x << "\n";
    return;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 3580
package main

import "fmt"

func main() {
	var a, b, c, d int
	fmt.Scan(&a, &b, &c, &d)

	if s, t := a*b, c*d; s >= t {
		fmt.Println(s)
	} else if s < t {
		fmt.Println(t)
	}
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll        = long long;
using ld        = long double;
using vl        = vector<ll>;
using vd        = vector<ld>;
using vs        = vector<string>;
using vb        = vector<bool>;
using vvl       = vector<vector<ll>>;
using vvd       = vector<vector<ld>>;
using vvs       = vector<vector<string>>;
using vvb       = vector<vector<bool>>;
using pll       = pair<ll, ll>;
constexpr ll mod= 1e9 + 7;
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for(ll(i)= 0; (i) < (n); (i)++)
#define REPS(i, n) for(ll(i)= 1; (i) <= (n); (i)++)
#define RREP(i, n) for(ll(i)= (n - 1); (i) >= 0; (i)--)
#define RREPS(i, n) for(ll(i)= (n); (i) > 0; (i)--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())
#define YES(n) ((n) ? "YES" : "NO")
#define Yes(n) ((n) ? "Yes" : "No")
#define yes(n) ((n) ? "yes" : "no")

template <class T>
inline void chmin(T& a, T b) {
    if(a > b) { a= b; }
}

template <class T>
inline void chmax(T& a, T b) {
    if(a < b) { a= b; }
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    ll N;
    cin >> N;
    vl A(N);
    vl B(N);
    REP(i,N)cin >> A[i] >> B[i];
    ll con = 0;
    bool ok = 0;
    REP(i,N){
        if(A[i] == B[i]){
            con++;
        }else{
            con = 0;
        }
        if(con >= 3)ok = 1;
    }
    cout << Yes(ok) << "\n";
}

Measured memory_bytes: 3660
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    s = input()
    if len(s) % 2 == 1:
        print("No")
        return
    for i in range(len(s)//2):
        if s[2*i:2*i+2] != 'hi':
            print("No")
            return
    print("Yes")


if __name__ == '__main__':
    main()


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

Measured memory_bytes: 3800
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
#include<set>
using namespace std;

const int N=2e5+5;
int n,fa[N],fath[N],val[N];
pair<int,int> now[N];

struct node
{
	int pos;
	bool operator < (const node &rhs) const
	{
		if(1LL*now[pos].first*now[rhs.pos].second!=
		1LL*now[pos].second*now[rhs.pos].first)
			return 1LL*now[pos].first*now[rhs.pos].second>
			1LL*now[pos].second*now[rhs.pos].first;
		return pos<rhs.pos;
	}
};
multiset<node> S;

int getfa(int x)
{
	if(fa[x]!=x) fa[x]=getfa(fa[x]);
	return fa[x];
}

void init()
{
	int i;
	scanf("%d",&n);
	for(i=2;i<=n;++i) scanf("%d",&fath[i]);
	for(i=1;i<=n;++i) scanf("%d",&val[i]);
	for(i=1;i<=n;++i)
	{
		fa[i]=i;
		if(val[i]) now[i].second=1;
		else now[i].first=1;
	}
	for(i=2;i<=n;++i) S.insert(node{i});
}

void work()
{
	int q=n-1;
	long long ans=0;
	while(q--)
	{
		node tt=*S.begin();S.erase(S.find(tt));
		int nowX=tt.pos;
		int nowFA=getfa(fath[nowX]);
		
		if(nowFA!=1) S.erase(S.find(node{nowFA}));
		ans+=1LL*now[nowFA].second*now[nowX].first;
		
		now[nowFA].first+=now[nowX].first;
		now[nowFA].second+=now[nowX].second;
		
		fa[nowX]=nowFA;
		if(nowFA!=1) S.insert(node{nowFA});
		
	}
	printf("%lld\n",ans);
}

int main()
{
	init();
	work();
	return 0;
}

Measured memory_bytes: 13568
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
int n;
signed main() {
	int ga, sa, ba, gb, sb, bb;
	cin >> n >> ga >> sa >> ba >> gb >> sb >> bb;
	if ((double)gb / ga < (double)sb / sa) { swap(gb, sb); swap(ga, sa); }
	if ((double)sb / sa < (double)bb / ba) { swap(sb, bb); swap(sa, ba); }
	if ((double)gb / ga < (double)sb / sa) { swap(gb, sb); swap(ga, sa); }
	int n1 = n;
	if (gb <= ga)goto heaven1;
	for (int i = n/ga; i >= 0; i--) {
		if (sb <= sa) {
			n1 = i * gb + n - i*ga;
			goto heaven1;
		}
		for (int j = (n - i * ga) / sa; j >= 0; j--) {
			if (bb <= ba) {
				n1 = max(n1, i*gb + j * sb + (n - i * ga - j * sa));
				goto hell1;
			}
			else {
				int k = (n - i * ga - j * sa) / ba;
				n1 = max(n1, i*gb + j * sb + k * bb + (n - i * ga - j * sa - k * ba));
				if ((n - i * ga - j * sa - k * ba) == 0)goto heaven1;
			}
		}
		hell1:;
	}
heaven1:n = n1;
	swap(ga, gb); swap(sa, sb); swap(ba, bb);
	if ((double)gb / ga < (double)sb / sa) { swap(gb, sb); swap(ga, sa); }
	if ((double)sb / sa < (double)bb / ba) { swap(sb, bb); swap(sa, ba); }
	if ((double)gb / ga < (double)sb / sa) { swap(gb, sb); swap(ga, sa); }
	if (gb <= ga)goto heaven2;
	for (int i = n / ga; i >= 0; i--) {
		if (sb <= sa) {
			n1 = i * gb + n - i * ga;
			goto heaven2;
		}
		for (int j = (n - i * ga) / sa; j >= 0; j--) {
			if (bb <= ba) {
				n1 = max(n1, i*gb + j * sb + (n - i * ga - j * sa));
				goto hell2;
			}
			else {
				int k = (n - i * ga - j * sa) / ba;
				n1 = max(n1, i*gb + j * sb + k * bb + (n - i * ga - j * sa - k * ba));
				if ((n - i * ga - j * sa - k * ba) == 0)goto heaven2;
			}
		}
	hell2:;
	}
heaven2:cout << n1 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
#include<cstdio>
#include<cstdlib>
using namespace std;
 
#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592
 
const double EPS = 1e-10;
 
using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;
ll modpow(ll a, ll n, ll m){
    if(n == 0) return 1;
    ll half = modpow(a,n/2,m);
    ll res = half * half % m;
    if(n & 1) res = res * (a%m) % m;
    return res;
}
struct Combination{
    vector<long long> _fac,_finv,_inv;
    const int m = MOD;

    Combination(int sz) : _fac(sz),_finv(sz),_inv(sz){
        _fac[0] = _fac[1] = 1;
        _finv[0] = _finv[1] = 1;
        _inv[1] = 1;
        for(int i = 2; i <= sz; i++){
            _fac[i] = _fac[i-1]*i%m;
            _inv[i] = m-_inv[m%i]*(m/i)%m;
            _finv[i] = _finv[i-1]*_inv[i]%m;
        }
    }

    inline long long fac(int n){return _fac[n];}
    inline long long inv(int n){return _inv[n];}
    inline long long finv(int n){return _finv[n];}

    long long comb(int n,int k){
        if(n < k) return 0;
        if(n < 0 || k < 0) return 0;
        return _fac[n]*(_finv[k]*_finv[n-k]%m)%m;
    }
};


 
int main(){
    int n,a,b; cin >> n >> a >> b;
    Combination C(2000000);
    ll now1 = 1,now2 = 1;
    rep(i,a){
        now1 *= n-i;
        now1 %= MOD;
    }
    rep(i,b){
        now2 *= n-i;
        now2 %= MOD;
    }
    ll ans = (((modpow(2,n,MOD)-1+MOD)%MOD-now1*C.finv(a)%MOD+MOD)%MOD-now2*C.finv(b)%MOD+MOD)%MOD;
    cout << ans << endl;
}

Measured memory_bytes: 47104
#include <bits/stdc++.h>
// make_tuple emplace_back next_permutation push_back make_pair second first
// setprecision

#if MYDEBUG
#include "lib/cp_debug.hpp"
#else
#define DBG(...) ;
#endif

using LL = long long;
constexpr LL LINF = 334ll << 53;
constexpr int INF = 15 << 26;
constexpr LL MOD = 1E9 + 7;

namespace Problem {
using namespace std;

class Solver {
   public:
    LL a, b, c, k;

    void solve() {
        cin >> a >> b >> c >> k;
        if (k % 2 == 0) {
            cout << a - b << "\n";
        } else {
            cout << b - a << "\n";
        }
    }
};
}  // namespace Problem

int main() {
    std::cin.tie(0);
    std::ios_base::sync_with_stdio(false);
    Problem::Solver sol;
    sol.solve();
    return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

    vector<int> cards(N);
    for(int i=0; i < N; i++){
        cin >> cards.at(i);
    }

    sort(cards.begin(), cards.end());

    int bob_point = 0;
    int alice_point = 0;
    for(int i = N-1; i >= 0; i--){
        if(i%2){
            // alice
            alice_point += cards.at(i);
        } else {
            // bob
            bob_point+= cards.at(i);
        }
    }

    cout << abs(alice_point - bob_point) << endl;
}

Measured memory_bytes: 256
//12
#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

struct P{
  double x,y,z;
  double sq(double a){
    return a*a;
  }
  double ds(P a){
    return sqrt(sq(x-a.x)+sq(y-a.y)+sq(z-a.z));
  }
};

int main(){
  int t;
  cin>>t;
  while(t--){
    double qr,rp,pq;
    int np;
    cin>>qr>>rp>>pq>>np;
    P ps[30];
    for(int i=0;i<np;i++){
      cin>>ps[i].x>>ps[i].y>>ps[i].z;
    }
    double e=1<<30;
    int p,q,r;
    for(int i=0;i<np;i++){
      for(int j=0;j<np;j++){
	for(int k=0;k<np;k++){
	  double cqr,crp,cpq;
	  cqr=ps[j].ds(ps[k])/qr;
	  crp=ps[k].ds(ps[i])/rp;
	  cpq=ps[i].ds(ps[j])/pq;
	  cqr/=crp;
	  cpq/=crp;
	  double me=max(fabs(cqr-1),fabs(cpq-1));
	  if(min(cqr,min(crp,cpq))>0&&me<e){
	    e=me;
	    p=i;
	    q=j;
	    r=k;
	  }
	}
      }
    }
    cout<<p+1<<' '<<q+1<<' '<<r+1<<endl;
  }
  return 0;
}
	    
    

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

}



Measured memory_bytes: 256
// H - Grid 1
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define MOD 1000000007

int main(){
	int H,W; cin>>H>>W;
	int dp[W+1]; for(int i=0; i<=W; i++) dp[i] = 0;
	dp[1] = 1;
	for(int h=1; h<=H; h++){
		string a; cin>>a;
		for(int w=1; w<=W; w++) dp[w] = a[w-1]=='.'? (dp[w] + dp[w-1]) % MOD: 0;
	}
	cout<< dp[W] <<endl;
}

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

int main() {
	char b;
	cin >> b;
	switch (b) {
	case 'A':
		cout << 'T' << endl;
		break;
	case 'T':
		cout << 'A' << endl;
		break;
	case 'C':
		cout << 'G' << endl;
		break;
	case 'G':
		cout << 'C' << endl;
		break;

	}
	return 0;
}

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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
// #define mod (998244353ll)

struct Edge {
  int to;
  Edge(int _to) : to(_to) {
  }
};
using Graph = vector<vector<Edge>>;

int cycle_node = -1;
vb seen;     // 探索済みフラグ
vb finished; // 探索済みで、絶対にサイクルがないノード

vi history;

void dfs(const Graph& g, int idx) {
  if (finished[idx]) {
    return;
  }

  history.push_back(idx);

  if (seen[idx]) {
    cycle_node = idx;
    return;
  }

  seen[idx] = true;

  for (const auto& e : g[idx]) {
    if (finished[e.to])
      continue;

    dfs(g, e.to);

    if (cycle_node != -1)
      return;
  }

  finished[idx] = true;
  history.pop_back();
}

// 閉路のパス
// 戻り値: 0→閉路なし 1→閉路あり
int find_cycle(const Graph& g, vector<int>& cycle) {
  ll n = g.size();

  // init
  cycle_node = -1;
  seen.assign(n, false);
  finished.assign(n, false);
  cycle.clear();

  // 全ての頂点を確認する
  rep(i, n) {
    dfs(g, i);
    // サイクルが見つかった時点でループを抜ける
    if (cycle_node != -1) {
      break;
    }
  }

  if (cycle_node == -1) {
    return 0;
  }

  // historyの始めにあるサイクルと無関係なデータを削除
  cycle.push_back(cycle_node);
  for (auto it = history.rbegin() + 1; it != history.rend(); it++) {
    if (*it == cycle[0]) {
      break;
    }
    cycle.push_back(*it);
  }
  reverse(all(cycle));

  return 1;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  ll n, m;
  cin >> n >> m;

  Graph g(n);

  rep(i, m) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].emplace_back(b);
  }

  vi cycle;
  if (!find_cycle(g, cycle)) {
    cout << -1 << endl;
    return 0;
  }

  // 検出した閉路に弦が存在するかを確認
find_smaller_cycle:

  ll cn = cycle.size();
  rep(i, cn) {
    for (auto e : g[cycle[i]]) {
      if (e.to == cycle[(i + 1) % cn]) {
        continue;
      }
      auto gen = find(all(cycle), e.to);
      if (gen == cycle.end()) {
        continue;
      }

      vi smaller_cycle;
      smaller_cycle.push_back(cycle[i]);

      vi cc = cycle;
      cc.insert(cc.end(), cycle.begin(), cycle.end());
      auto it = find(all(cc), e.to);

      while (*it != smaller_cycle[0]) {
        smaller_cycle.push_back(*it);
        it++;
      }

      cycle = smaller_cycle;
      goto find_smaller_cycle;
    }
  }

  cout << cycle.size() << endl;
  for (auto it : cycle) {
    cout << it + 1 << endl;
  }
}


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

int main(){
  int n;
  scanf("%d", &n);

  if(n < 1200) printf("ABC\n");

  else printf("ARC\n");
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	void run() {
		Scanner sc = new Scanner(System.in);

		int h = sc.nextInt();
		int w = sc.nextInt();
		char[][] c = new char[h][];
		for (int i = 0; i < h; i++) {
			c[i] = sc.next().toCharArray();
		}
		for (int i = 0; i < h; i++) {
			System.out.println(c[i]);
			System.out.println(c[i]);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}


Measured memory_bytes: 11504
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

template<class Type>
Type solve(Type res){
    int H,W; cin >> H >> W;
    for(int i = 0; i < H;i++){
        string s; cin >> s;
        cout << s << endl << s << endl;
    }
    return res;
}
int main(void) {
    cin.tie(0); ios::sync_with_stdio(false);
    solve<ll>(0);
    //cout << fixed << setprecision(12) << solve(0LL) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <istream>
#include <iterator>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
#define BR "\n"
#define REP(i,n) for(int (i)=0;(i)<(n);++(i))
#define ALL(cont) begin(cont),end(cont)
#define AS_MOD(a,b) ((((a) % (b) ) + (b)) % (b))
#define FEACH(it,cont) for(auto (it) = begin(cont); it!=end(cont);++it)
#define FEACHR(it,cont) for(auto (it) = rbegin(cont); it!=rend(cont);++it)
#define pb push_back
#define pob pop_back
#define fi first
#define se second
#define getll() ([](){ll s;scanf("%lld", &s);return s;})()
#define getld() ([](){ld s;scanf("%Lf", &s);return s;})()
#define prl(P) printf("%lld", P)
#define prd(P) printf("%.10Lf", P)
#define pr(P) printf(P)
#define MAX(V, T) V=max(V,T)

#define DumpArray(cont,from,to) for(int __i=from;__i<to;++__i) {cout<<"(" <<__i<<": " << cont[__i]<<")";} cout<<endl;

using namespace std;
typedef long long ll;
typedef long double ld;
ll mod=1000*1000*1000+7;
ll N,K;
ll C[2010][2010];
int main() {
    cin >> N >> K;
    memset(C,0,sizeof(C));
    for(int i=0;i<2010;++i){
        C[i][0]=1;
        C[i][i]=1;
    }
    for(int i=2;i<2010;++i) {
        for(int j=1;j<i;++j) {
            C[i][j]=AS_MOD(C[i-1][j-1]+C[i-1][j],mod);
        }
    }
    for(int i=1;i<=K;++i) {
        ll ans=1;
        ans *=C[K-1][i-1];
        ans *=C[N-K+1][i];
        cout << AS_MOD(ans,mod) << endl;
    }
    return 0;
}


Measured memory_bytes: 31872
n, a, b = map(int, input().split())
 
s = 0
for i in range(n+1):
  digitsum = i%10 + (i//10)%10 + (i//100)%10 + (i//1000)%10 + (i//10000)%10
  if a <= digitsum <= b:
    s += i
    
print(s)

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

int main(){
  int k, x;
  cin >> k >> x;
  
  int left = max((x - k + 1), -1000000);
  int right = min((x + k - 1), 1000000);
  
  for ( int i = left; i <= right; i++) cout << i << " ";
}

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

using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++)cin >> A[i];

	for (int i = 0; i < N; i++) {
		if (A[i] %2==0) {
			if (!(A[i] % 3 == 0 || A[i] % 5 == 0)) {
				cout << "DENIED";
				return 0;
			}
		}
	}
	cout << "APPROVED";

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <math.h>

#define X first
#define Y second
#define vsort(v) sort(v.begin(), v.end())
#define vrev(v) reverse(v.begin(), v.end())
#define P pair

// stoi(s): string to int
// stod(s): string to double

// INT_MAX
// INT_MIN
// LLONG_MAX
// LLONG_MIN
// DBL_MIN
// DBL_MAX
// LDBL_MIN
// LDBL_MAX

// A-Z: 65~90
// a-z: 97~122
// |a-z| = 26

using namespace std;
using ll = long long;

int main(int argc, const char *argv[])
{
    ll n;
    cin >> n;
    vector<ll> v(5);
    for (int i = 0; i < 5; i++)
    {
        cin >> v[i];
    }
    vsort(v);
    ll ans = ceil(1.0 * n / v[0]) + 4;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    vector<int> B(N-1);
    rep(i,0,N-1)cin >> B[i];
    ll sum = 0;
    sum += B[0] + B[N-2];
    rep(i,1,N-1){
        sum += min(B[i-1], B[i]);
    }
    cout << sum << endl;
}

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

int main()
{
int i;
int N;
int H;
int iCnt;
int iPre;

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

	cin >> N;
	cin >> iPre;

	iCnt = 1;
	for( i = 1; i < N; i++ )
	{
		cin >> H;

		if( iPre <= H )
		{
			iCnt++;
			iPre = H;
		}
	}

	cout << iCnt << endl;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

int main(){
	int a, b, c; ll k;
	scanf( "%d%d%d%lld", &a, &b, &c, &k );
	if( k&1 ) printf( "%d\n", b-a );
	else printf( "%d\n", a-b );
	return 0;
}

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

int n, ans;
string s;
int main() {
	cin>> n>> s;
	for(int i=0; i<n-2; i++) {
		if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C') ans++;
	}
	cout<< ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <set>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <limits>
#include <bitset>
#include <stack>
#include <queue>
#include <ctype.h>

typedef long long int lli;
#define rep(i,s,N) for(int i=s;i<N;i++)
#define MOD 1000000007
#define more(a,b) (((a)>(b))?(a):(b))
#define less(a,b) (((a)<(b))?(a):(b))

using namespace std;


int main(void)
{
	int N, M; cin >> N >> M;
	vector<int> A(N); 
	int sum = 0;
	rep(i, 0, N) {
		cin >> A[i];
		sum += A[i];
	}
	int popular = 0;
	rep(i, 0, N)if (sum <= 4 * M * A[i])popular++;
	
	if (popular >= M)cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>

#define MAXN 5000
#define MOD 1000000007
int N,len;
char str[MAXN+5];
long long dp[MAXN+5][MAXN+5];

int main(){
    scanf("%d%s",&N,str+1);
    len=strlen(str+1);
    dp[0][0]=1;
    for(int i=1;i<=N;i++)
        for(int j=0;j<=N;j++){
            if(j==0) dp[i][j]+=dp[i-1][j]+dp[i-1][j+1]*2;
            else dp[i][j]+=dp[i-1][j-1]+dp[i-1][j+1]*2;
            dp[i][j]%=MOD;
        }
    printf("%lld",dp[N][len]);
}


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

#define int long long
typedef pair<int, int> P;

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

/*
#define cin ifs
#define cout ofs
ifstream ifs("in.txt");
ofstream ofs("out.txt");
//*/

int N, M, X;
int U[2200], V[2200], W[2200];
int two[2200];
int mod = 1e9 + 7;

// クラスカル法を用いて最小全域木問題を解く

// Union-Find木
const int MAX_N = 100000;

struct UF {
    int par[MAX_N];  // 親
    int rank[MAX_N]; // 木の深さ

    // n要素で初期化
    void init(int n) {
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
        }
    }

    // 木の根を求める
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }

    // xとyの属する集合を併合
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;

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

    // xとyが同じ集合に属するか否か
    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

const int MAX_E = 100000;

struct edge { int u, v, cost; };

bool comp(const edge& e1, const edge& e2) {
    return e1.cost < e2.cost;
}

edge es[MAX_E];
UF uf;

int kruskal(int m) {
    swap(es[0], es[m]);
    sort(es + 1, es + M, comp);  // edge.costが小さい順にソートする
    uf.init(N + 10);              // Union-Findの初期化
    int res = 0;
    for (int i = 0; i < M; i++) {
        edge e = es[i];
        if (!uf.same(e.u, e.v)) {
            uf.unite(e.u, e.v);
            res += e.cost;
        }
    }
    return res;
}


int f(int x) {
    int C = 0;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            es[j] = {U[j], V[j], W[j]};
        }
        if (x >= kruskal(i)) {
            C++;
        }
    }
    if (C != 0) {
        return two[M - C + 1];
    } else {
        return two[M];
    }
}

signed main() {
    cin >> N >> M >> X;
    for (int i = 0; i < M; i++) {
        cin >> U[i] >> V[i] >> W[i];
    }
    two[0] = 1;
    for (int i = 1; i < 2200; i++) {
        two[i] = two[i - 1] * 2 % mod;
    }
    cout << (f(X - 1) - f(X) + mod) % mod << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=1000005,mod=1000000007;
const ll mod2=(ll)mod*mod;
int n,f[N];
ll fac[N],ni[N],ans;
inline ll p(int a,int b){
	return fac[a]*ni[a-b]%mod;
}
inline int ksm(ll a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
int main(){
	n=read();
	for(int i=fac[0]=1;i<=n;i++)fac[i]=fac[i-1]*i%mod; ni[n]=ksm(fac[n],mod-2);
	for(int i=n;i;i--)ni[i-1]=ni[i]*i%mod;
	for(int i=(n+1)/2;i<n;i++){
		f[i]=p(i-1,n-1-i)*fac[i]%mod;
		ans=ans+(ll)(f[i]-f[i-1]+mod)*i; if(ans>=mod2)ans-=mod2;
	}
	cout<<(ans+mod)%mod<<endl;
}


Measured memory_bytes: 19712
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use std::cmp::*;
use std::collections::*;
use std::mem::*;

fn main() {
    let (r, w, e) = (std::io::stdin(), std::io::stdout(), std::io::stderr());
    let mut io = IO::new(r.lock(), w.lock(), e.lock());
    let n = io.read::<usize>();
    let a = io.readn::<usize>(n);
    let mut sowa = 0f64;

    for &x in a.iter() {
        sowa += 1.0f64 / x as f64;
    }
    io.writeln(1f64 / sowa);
}

static MX: usize = 1010101;
static MOD: i64 = 1000000007;
static INF: i64 = std::i64::MAX >> 1;
// IO
use std::io::*;
struct IO<R: Read, W: Write, E: Write> {
    Read: R,
    Write: BufWriter<W>,
    Error: BufWriter<E>,
}
impl<R: Read, W: Write, E: Write> IO<R, W, E> {
    fn new(r: R, w: W, e: E) -> IO<R, W, E> {
        IO {
            Read: r,
            Write: BufWriter::new(w),
            Error: BufWriter::new(e),
        }
    }
    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
    {
        let next: String = self
            .Read
            .by_ref()
            .bytes()
            .map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect();
        next.parse().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    fn chari(&mut self) -> Vec<i64> {
        self.chars()
            .iter()
            .map(|&c| (c as u8 - b'0') as i64)
            .collect::<Vec<i64>>()
    }
    fn readn<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect::<Vec<_>>()
    }
    fn readmat<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n).map(|_| self.readn(m)).collect()
    }
    fn write<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
    }
    fn writeln<S: ToString>(&mut self, val: S) {
        self.Write.write(val.to_string().as_bytes());
        self.Write.write(b"\n");
    }
    fn debug<S: std::fmt::Debug>(&mut self, val: S) {
        writeln!(self.Error, "(debug) {:?}", &val);
    }
    fn debug2<S: std::fmt::Debug, T: std::fmt::Debug>(&mut self, val1: S, val2: T) {
        writeln!(self.Error, "(debug2) {:?} -> {:?}", val1, val2);
    }
    fn debug3<S: std::fmt::Debug, T: std::fmt::Debug, U: std::fmt::Debug>(
        &mut self,
        val1: S,
        val2: T,
        val3: U,
    ) {
        writeln!(
            self.Error,
            "(debug3) {:?} -> {:?} -> {:?}",
            val1, val2, val3
        );
    }
}


Measured memory_bytes: 2196
N, K = map(int, input().split())
s = list(map(int, input().split()))
all = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
usable = set(all) - set(s)
i = 0
while i == 0:
  num = N
  l = list(map(int, list(str(num))))
  wa = set(usable) | set(l)
  if wa == usable:
    i = i + 1
  else:
    N = N + 1
print(N)


Measured memory_bytes: 3064
#include <vector>
#include <complex>
#include <cstdio>
using namespace std;

typedef complex<double> P;
typedef vector<P> G;
double cross(const P& a, const P& b) {
	return imag(conj(a)*b);
}
bool in_triangle(const P& p1,const P& p2,const P& p3,const P& p){
	return cross(p2-p1,p-p1)>0 && cross(p3-p2,p-p2)>0 && cross(p1-p3,p-p3)>0;
}
int main(){
	double x1,y1,x2,y2,x3,y3,x,y;
	for(;~scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x,&y);){
		P p1(x1,y1),p2(x2,y2),p3(x3,y3),p(x,y);
		bool in=in_triangle(p1,p2,p3,p)||in_triangle(p2,p1,p3,p);
		puts(in?"YES":"NO");
	}
}

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

#define INF 1 << 30;
#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;

int main(){

	int n;
	while(cin >> n && n){
		// 段数
		int dp[32];
		rep(i, n) dp[i] = INF;
		
		dp[0] = 1;
		dp[1] = 2;
		dp[2] = 4;

		for(int i = 3; i < n; i++){
			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
		}

		cout << dp[n-1]/365/10  + 1<< endl;
	}
	return 0;
}

Measured memory_bytes: 1160
//
// Created by yamunaku on 2019/11/09.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    if(a[0] > 0){
        cout << 0 << endl;
        return 0;
    }
    vi c(n, 0);
    rep(i, n) c[a[i]]++;
    if(c[0] > 1){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 1;
    bool zero = false;
    repl(i, 1, n){
        if(c[i] == 0){
            zero = true;
        }else{
            if(zero){
                cout << 0 << endl;
                return 0;
            }
            rep(j, c[i]){
                ans = ans * c[i - 1] % MOD;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1152