akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[]a =new int[n];
		long[]sig = new long[n];
		int[]acopy = new int[n];
		for(int i=0;i<n;i++){
			a[i]=scan.nextInt();
			acopy[i]=a[i];
/*			if(i==0){
				siga[i]=a[i];
			}else{
				siga[i]=siga[i-1]+a[i];
			}*/
		}




		//第一項目が正の場合と負の場合


		//a[0]が0の場合を考える
		long cnt=0;

		if(a[0]==0){
			a[0]++;
			cnt++;
		}
		sig[0]=a[0];
		for(int i=1;i<n;i++){
			sig[i]=sig[i-1]+a[i];

			//積が0なら符号が異なるように+-1
			if(sig[i]*sig[i-1]==0){
				if(sig[i-1]>0){
					a[i]--;
					cnt++;
				}else{
					a[i]++;
					cnt++;
				}
				sig[i]=sig[i-1]+a[i];
			}

			//積が負なら条件を満たしているのでok
			else if(sig[i]*sig[i-1]<0){
			}

			//積が正なら負になるまで変える
			else{
				if(sig[i-1]>0){
					a[i]-=(sig[i]+1);
					cnt+=sig[i]+1;
				}else{
					a[i]+=-sig[i]+1;
					cnt+=-sig[i]+1;
				}
				sig[i]=sig[i-1]+a[i];
			}

		}


		long cnt2=0;
		if(acopy[0]==0){
			acopy[0]--;
			cnt2++;
		}else if(acopy[0]>0){
			cnt2 +=acopy[0]+1;
			acopy[0]=-1;
		}else{
			cnt2+=-acopy[0]+1;
			acopy[0]=1;
		}
		sig[0]=acopy[0];
		for(int i=1;i<n;i++){
			sig[i]=sig[i-1]+acopy[i];

			//積が0なら符号が異なるように+-1
			if(sig[i]*sig[i-1]==0){
				if(sig[i-1]>0){
					acopy[i]--;
					cnt2++;
				}else{
					acopy[i]++;
					cnt2++;
				}
				sig[i]=sig[i-1]+acopy[i];
			}

			//積が負なら条件を満たしているのでok
			else if(sig[i]*sig[i-1]<0){
			}

			//積が正なら負になるまで変える
			else{
				if(sig[i-1]>0){
					acopy[i]-=(sig[i]+1);
					cnt2+=sig[i]+1;
				}else{
					acopy[i]+=-sig[i]+1;
					cnt2+=-sig[i]+1;
				}
				sig[i]=sig[i-1]+acopy[i];
			}

		}


		System.out.println(Math.min(cnt, cnt2));

	}

}


Measured memory_bytes: 60848
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string solve(string S, string T)
{
	const int n = S.size();
	for (int i = 0; i < n; ++i) {
		if (S == T) {
			return "Yes";
		}
		rotate(S.begin(), S.begin() + 1, S.end());
	}
	return "No";
}

int main()
{
	string S, T;
	cin >> S >> T;
	cout << solve(S, T) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#include <cassert>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define forn(i,n)for(int i=0;i<n;i++)
#define forna(i,a,n)for(int i=a;i<n;i++)
#define pb push_back
#define mp make_pair
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1e9+7
#define ff first
#define ss second
#define INF 1e18
#define MAX 200006
typedef long long ll;
using namespace std;
using namespace __gnu_pbds;
 
int main()
{
    IOS
    ll n,a,b;cin>>n>>a>>b;
  	cout<<(n/(a+b))*a + min(a,n%(a+b));
    
}

Measured memory_bytes: 256
D, G = map(int, input().split())
p, c = [], []
for i in range(D):
    a, b = map(int, input().split())
    p.append(a)
    c.append(b)

from itertools import product
res = 1 << 29
for v in product([0, 1], repeat=D):
    score, num = 0, 0
    for i in range(D):
        if v[i] == 1:
            score += c[i] + p[i] * 100 * (i + 1)
            num += p[i]
    if score >= G:
        res = min(res, num)
    else:
        for j in range(D - 1, -1, -1):
            if v[j] == 1:
                continue
            for k in range(p[j]):
                if score >= G:
                    break
                score += 100 * (j + 1)
                num += 1
        res = min(res, num)
print(res)

Measured memory_bytes: 43632
while True:
    a, op, b = (x for x in input().split())
    a = int(a)
    b = int(b)
    if op == "+":
        ans = a + b
    elif op == "-":
        ans = a - b
    elif op == "*":
        ans = a * b
    elif op == "/":
        ans = a // b
    elif op == "?":
        break
    print(ans)


Measured memory_bytes: 5604
s=0
k=int(input())
from math import gcd
from itertools import product
L=product([i for i in range(1,k+1)],repeat=2)
S=[gcd(a,b) for (a,b) in L]
from collections import Counter
S_counter=Counter(S)
for key,value in S_counter.items():
    for i in range(1,k+1):
        s+=gcd(key,i)*value
print(s)        

Measured memory_bytes: 9704
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
 
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
 
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
 
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
 
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
 
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
 
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
 
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
 
 
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
 
fn main() {
    /*     input! {
        n: usize,
        mut plan: [(i32, i32, i32); n],  // Vec<(i32, i32, i32)>
    }
 */
    input! {
        h: f64,
        w: f64,
    }

    if h == 1.0 || w == 1.0 {
        println!("1");
        return;
    }
    
    println!("{}",(h * w / 2_f64).ceil() as u64);
}


Measured memory_bytes: 4352
package main

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

func main() {
  io := IO{bufio.NewReaderSize(os.Stdin,100),bufio.NewWriterSize(os.Stdout,100)}
  n,u,v := io.Next3Ints()
  u,v = u-1,v-1
  g := make([][]int,n)
  for i:=0;i<n-1;i++ {
    a,b := io.Next2Ints()
    a,b = a-1,b-1
    g[a] = append(g[a],b)
    g[b] = append(g[b],a)
  }
  du := dfs(g,u)
  dv := dfs(g,v)
  x := 0
  for i:=0;i<n;i++ {
    if len(g[i]) > 1 { continue }
    if du[i] < dv[i] && x < dv[i] { x = dv[i] }
  }
  fmt.Println(x-1)
}
func dfs(g [][]int,s int) []int {
  x := make([]int,len(g))
  var rec func(int,int,int)
  rec = func(v,p,d int) {
    x[v] = d
    for _,u := range g[v] {
      if u == p { continue }
      rec(u,v,d+1)
    }
  }
  rec(s,-1,0)
  return x
}

type IO struct {
  reader *bufio.Reader
  writer *bufio.Writer
}
func(io *IO) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := io.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(io *IO) Println(a ...interface{}) (int,error) {
  return fmt.Fprintln(io.writer,a...)
}
func(io *IO) Flush() error {
  return io.writer.Flush()
}
func(io *IO) Next2Ints() (int,int) {
  s := strings.Fields(io.NextLine())
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  return x,y
}
func(io *IO) Next3Ints() (int,int,int) {
  s := strings.Fields(io.NextLine())
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  z,_ := strconv.Atoi(s[2])
  return x,y,z
}

Measured memory_bytes: 35712
#include <stdio.h>
#include <stdlib.h>

int main(void){
  char S[100]; long long int K, i, x=0;
  scanf("%s", &S);
  scanf("%lld", &K);
  for(i=0; i<K; i++){
    if(S[i] - '1' != 0){
      printf("%c\n", S[i]);
      x = 1;
      break;
    }
  }
  if(x == 0){
    printf("1\n");
  }
  return 0;
}


Measured memory_bytes: 128
(my $n,my $d)=split(/ /,<>);
my $counter=0;my $answer=0;
while ($n > $counter){($x,$y)=split(/ /,<>); if($d**2>=$x**2+$y**2){$answer++;};$counter++;($x,$y)=(0,0);}
print $answer;

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

#define ll long long int
#define vi vector<int>
using namespace std;

int main(){
    int x;
    cin >> x;
    for(long long int i=-1000;i*i*i*i*i<=1000000000;i++){
        for(long long int j=-1000;j*j*j*j*j<=1000000000;j++){
            if((i*i*i*i*i)-(j*j*j*j*j)==x){cout << i <<' ' <<j;return 0;}
        }
        
        
    }
    
}

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

typedef long long ll;
const ll INF = 1e9, MOD = 1e9 + 7;
const double EPS = 1e-9, PI = 3.141592653589793;
#define Cin(x) cin >> x
#define Cin2(x,y) cin >> x >> y
#define Cin3(x,y,z) cin >> x >> y >> z
#define Cin4(w,x,y,z) cin >> w >> x >> y >> z
#define Cout(x) cout << x << "\n"
#define Cout2(x,y) cout << x << y << "\n"
#define Cout3(x,y,z) cout << x << y << z << "\n"
#define Cout4(w,x,y,z) cout << w << x << y << z << "\n"
#define Kaigyou cout << "\n"
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define REPR(i,a,b) for(ll i=b;i>=a;i--)
#define repr(i,n) REPR(i,0,n)
#define Size(n) (n).size()
#define All(v) (v).begin(), (v).end()
#define Pb(i) push_back(i)

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

    ll a,b,c; Cin3(a,b,c);
    set<ll> st;
    st.insert(a);
    st.insert(b);
    st.insert(c);
    Cout(st.size());
    return 0;
}

Measured memory_bytes: 256
import std.conv, std.stdio;
import std.algorithm, std.array, std.range, std.string;

void main()
{
    auto buf = readln.chomp.split.to!(int[]);
    auto tree = Tree(buf[0]);
    immutable q = buf[1];
    foreach (i; 1..tree.length)
    {
        buf = readln.chomp.split.to!(int[]);
        tree.addEdge(buf[0], buf[1]);
    }
    foreach (i; 0..q)
    {
        buf = readln.chomp.split.to!(int[]);
        tree[buf[0]-1].countUp(buf[1]);
    }
    "%(%d %)".writefln(tree.dfs);
}
struct Tree
{
    Node[] nodes;
    this (in size_t n)
    {
        nodes.length = n;
        nodes[0] = root;
        foreach (i; 1..n)
            nodes[i] = node;
    }
    void addEdge(in size_t a1, in size_t b1)
    {
        auto a = nodes[a1-1], b = nodes[b1-1];
        a.children ~= b1-1;
        assert (b.parent is null);
        b.parent = a;
    }
    alias nodes this;
    ulong[] dfs()
    {
        auto result = new ulong[nodes.length];
        auto visited = new bool[nodes.length];
        void _dfs(size_t p, long counter)
        {
            counter += nodes[p].counter;
            result[p] = counter;
            assert (!visited[p]);
            visited[p] = true;
            stderr.writefln("visit: %d", p);
            foreach (c; nodes[p].children)
                _dfs(c, counter);
        }
        _dfs(0, 0);
        assert (visited.all);
        return result;
    }
}
class Node
{
    bool isRoot;
    Node parent;
    size_t[] children;
    this (bool isRoot, Node parent, size_t[] children)
    {
        this.isRoot = isRoot;
        this.parent = parent;
        this.children = children;
    }
    long counter;
    void countUp(long x)
    {
        this.counter += x;
    }
}
auto root()
{
    return new Node(true, null, []);
}
auto node()
{
    return new Node(false, null, []);
}


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

#define MOD (1000000000+7)
#define MAX 100000

long long n, m;
long long x[MAX];
long long y[MAX];

int main()
{
	cin >> n >> m;
	for( int i = 0; i < n; i++ ) {
		cin >> x[i];
	}
	for( int i = 0; i < m; i++ ) {
		cin >> y[i];
	}

	long long xsum = 0;
	for( int i = 0; i < n; i++ ) {
		xsum = ( xsum + ( i * x[i] - (n - i - 1) * x[i] + MOD ) % MOD ) % MOD;
	}
	long long ysum = 0;
	for( int i = 0; i < m; i++ ) {
		ysum = ( ysum + ( i * y[i] - (m - i - 1) * y[i]  + MOD ) % MOD ) % MOD;
	}
	long long ans = xsum * ysum % MOD;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1792
// AOJ 0114: Electro-Fly
// 2017.8.23 bal4u@uu
// 1017.11.5 retry

#include <stdio.h>

long long gcd(long long a, long long b)
{
	long long r;
	while (b) r = a % b, a = b, b = r;
	return a;
}
long long lcm(long long a, long long b) { return a/gcd(a, b) * b; }

int carmichael(int a, int m)
{
    int n, b;
	for (n = 1, b = a; b != 1; n++) b = (b * a) % m;
	return n;
}

int main()
{
	int a1, a2, a3, m1, m2, m3, b1, b2, b3;

	while (scanf("%d%d%d%d%d%d", &a1, &m1, &a2, &m2, &a3, &m3) && a1 > 0) {
		b1 = carmichael(a1, m1);
		b2 = carmichael(a2, m2);
		b3 = carmichael(a3, m3);
		printf("%lld\n", lcm(lcm((long long)b1, (long long)b2), 
			(long long)b3));
	}
	return 0;
}

Measured memory_bytes: 1744
#include<bits/stdc++.h>
using namespace std;
#define int long long
bool ch(int a,int b){
  int x=1000000000000000LL;
  x/=a;
  x/=b;
  return x==0;
}
signed main(){
  int n,m,a,b,p,q;
  cin>>n>>m>>a>>b>>p>>q;
  if(a==1&&b==1){
    //cout<<m%(p+q)<<endl;
    if(ch(n,p+q)) cout<<min(m%(p+q),(p+q)-m%(p+q))<<endl;
    else{
      int t=n*(p+q);
      if(m>=t) cout<<m-t<<endl;
      else cout<<min(m%(p+q),(p+q)-m%(p+q))<<endl;
    }
    return 0;
  }
  int ans=m;
  int ta=1,tb=1;
  vector<int> v;
  for(int i=0;i<n;i++){
    if(ch(p,ta)) break;
    if(ch(q,tb)) break;
    int t=p*ta+q*tb;
    //cout<<t<<endl;
    if(t<=m) v.push_back(t);
    else{
      ans=min(ans,t-m);
      break;
    }
    if(ch(ta,a)) break;
    if(ch(tb,b)) break;
    ta*=a;tb*=b;
  }
  int x=v.size();
  int y=x/2;
  set<int> s;
  for(int i=0;i<(1<<y);i++){
    int t=0;
    for(int j=0;j<y;j++) if((i>>j)&1) t+=v[j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }    
    //cout<<t<<endl;
    s.insert(-t);
    ans=min(ans,m-t);
  }
   
  for(int i=0;i<(1<<(x-y));i++){
    int t=0;
    for(int j=0;j<(x-y);j++) if((i>>j)&1) t+=v[y+j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }
    //cout<<t<<endl;
    ans=min(ans,m-t);
    int u=t-m;
    int k=*s.lower_bound(u);
    ans=min(ans,m-(t-k));
  }
   
  s.clear();
  for(int i=0;i<(1<<y);i++){
    int t=0;
    for(int j=0;j<y;j++) if((i>>j)&1) t+=v[j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }    
    //cout<<t<<endl;
    s.insert(t);
    ans=min(ans,m-t);
  }
   
  int inf=m*2;
  s.insert(inf);
  for(int i=0;i<(1<<(x-y));i++){
    int t=0;
    for(int j=0;j<(x-y);j++) if((i>>j)&1) t+=v[y+j];
    if(t>m){
      ans=min(ans,t-m);
      continue;
    }
    //cout<<t<<endl;
    ans=min(ans,m-t);
    int v=m-t;
    int l=*s.lower_bound(v);
    if(l!=inf) ans=min(ans,(t+l)-m);
  }
  //assert(ans>=0);
  cout<<ans<<endl;
  return 0;
}

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

W, H, x, y, r = map(int, input().split())
# print(W, H, x, y, r)                      
if 0 + r <= x  <= W - r and 0  + r <= y <= H - r :
    print("Yes")
else :
    print("No")



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

using namespace std;

typedef long long int ll;
 
template<class T> inline bool chmax(T& a,T b){ if(a<b){ a=b; return true;} return false; }
template<class T> inline bool chmin(T& a,T b){ if(a>b){ a=b; return true;} return false; }
 
typedef pair<int,int> pair;

int main(){
    int n,l; cin >> n >> l;
    vector<string> s(n);
    for(int i=0;i<n;i++) cin >> s[i];

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

    for(auto v : s){
        cout << v;
    }

    cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
 
#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(LL i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const int mod = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAX = 100005;
int n;
int main()
{
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i = 0; i < 20; i++)
	{
		if(n == (1 << i))
		{
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	int maxStep = 0;
	for(int i = 0; i < 20; i++)
	{
		if((1 << i) - 1 <= n)
		{
			maxStep = i;
		}
	}
	int cnt = (1 << maxStep) - 1;
	
	for(int i = 2; i <= 2 * cnt; i++)
	{
		int fr = i , to = i - 1;
		if(fr > cnt)
		{
			fr -= cnt;
			fr += n;
		}
		if(to > cnt)
		{
			to -= cnt;
			to += n;
		}
		cout << fr << " " << to << endl;
	}
	for(int i = (1 << maxStep); i <= n - 1; i += 2)
	{
		int toXor = i ^ (i + 2);
		cout << i << " " << toXor << endl;
		cout << i + 1 << " " << i << endl;
		cout << i + n + 1 << " " << i + n << endl;
		cout << i + n + 1 << " " << toXor + 1 << endl;
	}
	if(n % 2 == 0)
	{
		int toXor = (n - 2) ^ n;
		cout << n << " " << n - 2 << endl;
		cout << toXor << " "  << 2 * n << endl;
	}
	//cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}


Measured memory_bytes: 2688
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <limits>
#include <climits>
#include <utility>
#include <algorithm>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main()
{
    int P, Q, R;
    cin >> P >> Q >> R;

    int ans = min(min(P + Q, Q + R), R + P);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()

typedef long long ll;

using namespace std;
//using namespace boost::multiprecision;


int main(){

    int v[3];

    cin >> v[0] >> v[1] >> v[2];

    if(v[0] + v[1] + v[2] >= 22){
        cout << "bust" << endl;
    }else{
        cout << "win" << endl;
    }

    return 0;
}

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

int main()
{
    ll n, m;
    cin >> n >> m;
    vector<P> shop(n);
    rep(i, n) cin >> shop[i].first >> shop[i].second;
    sort(shop.begin(), shop.end());
    ll ans = 0;
    rep(i, n)
    {
        if (m <= 0)
            break;
        int num = min(m, shop[i].second);
        ans += (ll)num * shop[i].first;
        m -= num;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4844
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <random>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define rep(i,n)	for(int i=0;i<n;i++)
#define srep(i,a,n)	for(int i=a;i<n;i++)
#define REP(i,n)	for(int i=0;i<=n;i++)
#define SREP(i,a,n)	for(int i=a;i<=n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
#define fst	first
#define scn second
#define bicnt(x)	__buildin__popcount(x)
#define gcd(a,b)	__gcd__(a,b)
#define debug(x)	cout<<"debug: "<<x<<endl
#define DEBUG 0
const ll inf = (ll)1e9;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

struct edge {
	int to, cap, cost, rev;
	edge(int to_, int cap_, int cost_, int rev_) {
		to = to_;
		cap = cap_;
		cost = cost_;
		rev = rev_;
	}
};

int n;
vector<edge> e[1010];
int h[1010];
int dist[1010];
int prevv[1010], preve[1010];

void add_edge(int s, int t, int cap, int cost) {
	e[s].push_back(edge(t, cap, cost, e[t].size()));
	e[t].push_back(edge(s, 0, -cost, e[s].size() - 1));
}

int min_cost_flow(int s, int t, int f) {
	int ret = 0;
	REP(i, n)	h[i] = 0;
	while (f > 0) {
		priority_queue<pii> pq;
		pq.push(mp(0, -s));
		REP(i, n)	dist[i] = inf;
		dist[s] = 0;
		while (!pq.empty()) {
			auto it = pq.top();	pq.pop();
			int v = -it.second, cost = -it.first;
			if (dist[v] < cost)	continue;
			rep(i, e[v].size()) {
				edge* to = &e[v][i];
				if (to->cap > 0 && dist[to->to] > dist[v] + to->cost + h[v] - h[to->to]) {
					dist[to->to] = dist[v] + to->cost + h[v] - h[to->to];
					prevv[to->to] = v;
					preve[to->to] = i;
					pq.push(mp(-dist[to->to], -to->to));
				}
			}
		}
		if (dist[t] == inf)	return -1;
		rep(i, n)	h[i] += dist[i];
		int d = f;
		for (int i = t; i != s; i = prevv[i]) {
			d = min(d, e[prevv[i]][preve[i]].cap);
		}
		f -= d;
		ret += d*h[t];
		for (int i = t; i != s; i = prevv[i]) {
			edge* to = &e[prevv[i]][preve[i]];
			to->cap -= d;
			e[i][to->rev].cap += d;
		}
	}
	return ret;
}

int main() {
	int e, f;	cin >> n >> e >> f;
	rep(i, e) {
		int s, t, c, d;	cin >> s >> t >> c >> d;
		add_edge(s, t, c, d);
	}
	cout << min_cost_flow(0, n - 1, f) << endl;
	return 0;
}

Measured memory_bytes: 3172
n = int(input())
a = list(map(int,input().split()))
rui = [0] * (n+1)
for i in range(n):
  rui[i+1] = rui[i] + a[i]
ans = float("inf")
for i in range(1,n):
  ans = min(ans,abs(rui[i]-(rui[n]-rui[i])))
print(ans)

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

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

    int n, m;
    cin >> n >> m;
    ll mod = 1e9 + 7;
    vector<ll> s(n + 1);
    set<int> a;
    rep(i, m)
    {
        int p;
        cin >> p;
        a.insert(p);
    }
    int l = 0;
    s[0] = 1;

    rep(i, n + 1)
    {
        if (a.find(i) != a.end())
        {
            s[i] = 0;
            l++;
            continue;
        }
        if (i >= 2)
            s[i] += s[i - 1] + s[i - 2];
        else if (i == 1)
            s[1] += s[0];
        s[i] %= mod;
    }
    cout << s[n] % mod << endl;

    return 0;
}


Measured memory_bytes: 5760
import numpy as np
import math
import itertools
n = int(input())
xy = []
for _ in range(n):
  xy.append(list(map(int, input().split())))
xy = np.array(xy)
dist = []
# calculate all distance
# n-1 * dist from a
# n-2 * dist from b
su = 0
for i in range(n-1):
  d = np.array(list(map(math.sqrt, ((xy[i+1:] - xy[i])**2).sum(axis=1))))
  mu = math.factorial(n-1)*2
  su += (d*mu).sum()
print(su/math.factorial(n))

Measured memory_bytes: 12504
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPS(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
#define INF 1e9
#define PI (acos(-1))
int main() {
    int a,b;
    cin>>a>>b;
    if(a<10&&b<10)cout<<a*b<<endl;
    else cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
#define pb push_back
#define int long long

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	string s; cin >> s;
	vector<array<int, 3>> pref(n), suf(n);
	map<char, int> mp = {{'R', 0}, {'G', 1}, {'B', 2}};
	for (int i = 0; i < n; ++i) {
		if (i) pref[i] = pref[i-1], suf[n-1-i] = suf[n-i];
		else pref[i] = suf[n-1-i] = {0, 0, 0};

		++pref[i][mp[s[i]]];
		++suf[n-1-i][mp[s[n-1-i]]];
	}
	int ans = 0;
	for (int i = 1; i+1 < n; ++i) {
		int x = mp[s[i]];
		int y = (x+1)%3;
		int z = (y+1)%3;
		ans += pref[i-1][y] * suf[i+1][z] + pref[i-1][z] * suf[i+1][y];
		for (int j = 1; ; ++j) {
			int p = i-j, q = i+j;
			if (p < 0 or q >= n) break;
			set<int> S = {x, mp[s[p]], mp[s[q]]};
			if (S.size() == 3) --ans;
		}
	}
	cout << ans;
}

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

using namespace std;

using llong = long long int;

#define rep(i, n) for (int i = 0; i < n; ++i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()

const static int MOD = 1000000007;
const static int INF = 1000000000;
const static int dx[4] = {1, 0, -1, 0};
const static int dy[4] = {0, 1, 0, -1};

int main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int d, t, s;
    cin >> d >> t >> s;

    cout <<  ((d <= t*s) ? "Yes" : "No") << endl;

    return 0;
}

Measured memory_bytes: 3664
using System;
using System.Linq;

namespace ABC141_C
{
    class Program
    {
        static void Main(string[] args)
        {
            var nkq = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var n = nkq[0];
            var k = nkq[1];
            var q = nkq[2];

            var a = new int[q];
            var na = new int[n];
            for (int i = 0; i < q; i++)
            {
                a[i] = int.Parse(Console.ReadLine());
                na[a[i] - 1]++;
            }

            for (int i = 0; i < n; i++)
            {
                if (k - (q - na[i]) <= 0)
                {
                    Console.WriteLine("No");
                }
                else
                {
                    Console.WriteLine("Yes");
                }
            }
        }
    }
}


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

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

using namespace std;

class union_find{
	int n;
	vector<int> p;
public:
	union_find(int n):n(n),p(n,-1){}
	int find(int u){ return p[u]<0?u:p[u]=find(p[u]); }
	void unite(int u,int v){
		u=find(u); v=find(v);
		if(u!=v){
			if(p[v]<p[u]) swap(u,v);
			p[u]+=p[v]; p[v]=u; n--;
		}
	}
	bool is_same(int u,int v){ return find(u)==find(v); }
	int size()const{ return n; }
	int size(int u){ return -p[find(u)]; }
};

int main(){
	int n,q; scanf("%d%d",&n,&q);
	union_find U(n);
	rep(_,q){
		int t,u,v; scanf("%d%d%d",&t,&u,&v);
		if(t==0) U.unite(u,v);
		else     printf("%d\n",U.is_same(u,v));
	}

	return 0;
}


Measured memory_bytes: 3988
D=int(input())
c=list(map(int,input().split()))
s=[]
t=[]
for i in range(D):
  s.append(list(map(int,input().split())))
l=[0]*26
Manzoku=0

max=0
target=0
deg=0
for d in range(1,D+1):
  for i in range(26):
    deg=c[i]*(d-l[i])
    if max < deg:
      max=deg
      target=i
  t.append(target+1)
  l[target]=d

for i in range(D):
  print(t[i])

Measured memory_bytes: 9376
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N;
    cin >> N;

    string S;
    cin >> S;

    for(auto it = S.begin(); it != S.end(); it++)
    {
        *it = *it + N;
        if(*it > 'Z')
        {
            *it = *it - 26;
        }
    }

    cout << S;
    return 0;
}

Measured memory_bytes: 256
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 40068
#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>

using namespace std;

const double PI = acos(-1);

double c, h, a, b, x;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> a >> b >> x;
	if (2 * x <= a * a * b) {
		c = 2 * x / a / b;
		h = c * b / hypot(c, b);
		cout << setprecision(10) << fixed << acos(h / b) * 180 / PI << '\n';
	} else {
		c = 2 * (double)(a * a * b - x) / a / a;
		h = c * a / hypot(c, a);
		cout << setprecision(10) << fixed << asin(h / a) * 180 / PI << '\n';
	}
	return 0;
}


Measured memory_bytes: 384
import sys

N, M, Q = map(int, sys.stdin.readline().strip().split())
con = []  # condition
for i in range(Q):
    con.append(list(map(int, sys.stdin.readline().strip().split())))

dig = N + 1  # dig -1 桁の数字を作る
A = [1] * dig
point = 0


def make(min=1, digit=1):
    global point
    for i in range(min, M + 1):
        A[digit] = i
        if digit != dig - 1:
            make(min=i, digit=digit + 1)
        else:
            temp_point = 0
            for c in con:
                if A[c[1]] - A[c[0]] == c[2]:
                    temp_point += c[3]
            point = max(point, temp_point)


for i in range(1, M + 1):
    make(min=i, digit=1)

print(point)


Measured memory_bytes: 9228
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for(int i=0;i<(int)n;i++)
ll mod=1e9+7;
#define PI acos(-1)

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

    if(n%2==0) cout<<n/2<<endl;
    else cout<<n/2+1<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
int main(){
	char s[26]={};
	scanf("%s",s);
	int a[26]={};
	int x=0;
	for(int i=0;i<26;i++){
		if(s[i]==0)break;
		a[s[i]-'a']++;
		if(i==25)x++;
	}
	if(x==0){
		for(int i=0;i<26;i++){
			if(a[i]==0){
				printf("%s",s);
				printf("%c\n",'a'+i);
				break;
			}
		}
	}else{
		for(int i=24;i>=0;i--){
			if(s[i+1]>s[i]){
				for(int j=0;j<i;j++){
					printf("%c",s[j]);
				}
				int b[26]={};
				for(int j=0;j<25-i;j++){
					b[j]=s[j+i+1];
				}
				std::sort(b,b+25-i);
				int q;
				for(int j=0;j<25-i;j++){
					if(b[j]>s[i]){
						q=j;
						break;
					}
				}
				printf("%c\n",b[q]);
				break;
			}
			if(i==0)printf("-1\n");
		}
	}
	return 0;
}

Measured memory_bytes: 128
n = int(input())
list = []

if n == 2:
    a, b = map(int, input().split())
    
    for i in range(1, a+1):
        if a%i == 0:
            list.append(i)
    
    for i in range(1, b+1):
        if b%i == 0:
            list.append(i)
    listDup = [x for x in set(list) if list.count(x) > 1]
    
if n == 3:
    a, b, c = map(int, input().split())
    
    for i in range(1, a+1):
        if a%i == 0:
            list.append(i)
    
    for i in range(1, b+1):
        if b%i == 0:
            list.append(i)
    
    for i in range(1, b+1):
        if b%i == 0:
            list.append(i)
            
    listDup = [x for x in set(list) if list.count(x) > 2]
    
listDup.sort()

for i in range(len(listDup)):
        print(listDup[i])



Measured memory_bytes: 5608
N = int(input())
P = [int(i) for i in input().split()]
asum = [1] * (N + 1)
bsum = [-1] * (N + 1)
bsum[0] = N
for i in range(N):
    p = P[i] - 1
    asum[p + 1] += 20000 - i
    bsum[0] += 20000 - i
    bsum[p] -= 20000 - i
a = [0] * N
b = [0] * N
a[0] = asum[0]
b[0] = bsum[0]
for i in range(1, N):
    a[i] = a[i - 1] + asum[i]
    b[i] = b[i - 1] + bsum[i]
for i in range(N):
    print(a[i], end=' ')
print()
for i in range(N):
    print(b[i], end=' ')


Measured memory_bytes: 7544
from collections import Counter as C;r=range(3)
def s():
	H,W,N,*L=map(int,open(0).read().split());K=[];M=[(H-2)*(W-2)]+[0]*9
	for a,b in zip(*[iter(L)]*2):
		for x in r:
			for y in r:
				if H-1>a-y>0<b-x<W-1:K+=[(a-y)*W+b-x]
	for k,v in C(C(K).values()).items():M[0]-=v;M[k]+=v
	print(*M)
if __name__=="__main__":s()

Measured memory_bytes: 124424
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

struct P {
    bool operator<(const P &p) const {
        return z < p.z;
    }
    int x, y;
    double z;
};

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

    vector<P> p;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if (x == 0 && y == 0) continue;
        double z = atan2((double)y, (double)x);
        p.push_back({ x, y, z });
    }

    n = p.size();
    if (n == 0) {
        cout << 0 << endl;
        exit(0);
    }
    sort(p.begin(), p.end());

    double r = 0;
    for (int i = 0; i < n; i++) {
        for (int k = 1; k <= n; k++) {
            double x = 0, y = 0, z = p[i].z;
            for (int j = 0; j < k; j++) {
                const P &q = p[(i + j) % n];
                x += q.x;
                y += q.y;
            }
            r = max(r, sqrt(x * x + y * y));
        }
    }

    printf("%.15f\n", r);

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<utility>
#include<stack>
#include<algorithm>
#include<string>
#include<string.h>
#include<assert.h>
#include<iomanip>
#include<unordered_map>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

const ll MAGIC = 1e7;

int main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  srand(time(0));
  ll n, a, b;
  cin >> a >> b >> n;
  // a = rand() % 1000000;
  // b = rand() % 50000000;
  // n = rand() % 50000000;
  // cout << a << " " << b << " " << n << endl;
  ll ans = 0;
  if(b < n){
    for(int i = 0; i <= min(MAGIC, b); ++i){
      ll cur = (a * (b - i) / b) - a * ((b - i) / b);
      ans = max(ans, cur);
    }
  }else{
    for(int i = 0; i <= min(MAGIC, n); ++i){
      ll cur = (a * (n - i) / b) - a * ((n - i) / b);
      ans = max(ans, cur);
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 3644
import java.util.Scanner;

import java.util.*;

public class Main{

	
	static public void  main(String[] args){
		Scanner scan = new Scanner(System.in);

		int x = scan.nextInt();
		int y = scan.nextInt();
		int z = scan.nextInt();
		int k = scan.nextInt();



		Long[] a = new Long[x];
		Long[] b = new Long[y];
		Long[] c = new Long[z];
		for(int i = 0; i < x; i++){
			a[i] = scan.nextLong();
		}
		for(int i = 0; i < y; i++){
			b[i] = scan.nextLong();
		}
		for(int i = 0; i < z; i++){
			c[i] = scan.nextLong();
		}

		List<Long> all = new ArrayList<>(k);
		
		Arrays.sort(a, Collections.reverseOrder());
		Arrays.sort(b, Collections.reverseOrder());
		Arrays.sort(c, Collections.reverseOrder());
		int p = 0;
		for(int i = 0; i < x; i++){
			for(int j = 0; j < y; j++){
				for(int l = 0; l < z; l++){
					if((i+1)*(j+1)*(l+1) <= k){
						all.add(a[i]+ b[j]+c[l]);
					}else{
						break;
					}
				}
			}
		}
		Collections.sort(all, Collections.reverseOrder());

		for(int i = 0; i < k; i++){
			System.out.println("" + all.get(i));
		}
		// Arrays.sort(all, Collections.reverseOrder());

		// int ap = 0;
		// int bp = 0;
		// int cp = 0;

		// System.out.println(a[ap] + b[bp] + c[cp]);
		// for(int i = 0 ; i < k; i++){
		// 	System.err.println("" + ap + ":" + bp + ":" +cp);

		// 	long _a = 0;
		// 	long _b = 0;
		// 	long _c = 0;
		// 	if (ap + 1 < a.length){
		// 		_a  = a[ap+1];
		// 	}
		// 	if (bp + 1 < b.length){
		// 		_b  = b[bp+1];
		// 	}
		// 	if (cp + 1 < c.length){
		// 		_c  = c[cp+1];
		// 	}

		// 	if(_a >  _b &&   _a > _c ){
		// 		System.out.println(a[ap+1] + b[bp] + c[cp]);
		// 	}else if(_b >  _a &&   _b > _c ){
		// 		System.out.println(a[ap] + b[bp+1] + c[cp]);
		// 	}else{
		// 		System.out.println(a[ap] + b[bp+1] + c[cp+1]);
		// 	}

			
		// }
		
	}
}


Measured memory_bytes: 34872
N = int(input())
A = list(map(int, input().split()))
rate = {"a":0, "b":0, "c":0, "d":0, "e":0, "f":0, "g":0, "h":0}
ratez = {"z":0}
for i in range(N):
    if A[i] >=1 and A[i] <= 399:
        rate["a"] += 1
    if A[i] >=400 and A[i] <= 799:
        rate["b"] += 1
    if A[i] >=800 and A[i] <= 1199:
        rate["c"] += 1
    if A[i] >=1200 and A[i] <= 1599:
        rate["d"] += 1
    if A[i] >=1600 and A[i] <= 1999:
        rate["e"] += 1
    if A[i] >=2000 and A[i] <= 2399:
        rate["f"] += 1
    if A[i] >=2400 and A[i] <= 2799:
        rate["g"] += 1
    if A[i] >=2800 and A[i] <= 3199:
        rate["h"] += 1
    if A[i] >=3200:
        ratez["z"] += 1
keys = [k for k, v in rate.items() if v != 0]

if ratez["z"] == 0:
    print(len(keys), len(keys))
elif len(keys) == 0:
    print(1, ratez["z"])
else:
    print(len(keys), len(keys)+ratez["z"])

Measured memory_bytes: 9164
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        final int MOD = (int)1e9+7;
        
        int n = Integer.parseInt(sc.next());
        long k = Long.parseLong(sc.next());
        
        int[] a = new int[n];
        for(int i=0; i<n; i++){
            a[i] = Integer.parseInt(sc.next());
        }
        
        Inversion in = new Inversion();
        int[] zaatu = in.shrink(a);
        int[] revzaatu = new int[n];
        for(int i=0; i<n; i++){
            revzaatu[n-i-1] = zaatu[i];
        }
        long nt = in.inv(zaatu, MOD);
        long rv = in.inv(revzaatu, MOD);
        
        long s = (k+1)%MOD*(k%MOD)/2%MOD;
        long t = (k-1)%MOD*(k%MOD)/2%MOD;
        
        long ans1 = s*nt%MOD;
        long ans2 = t*rv%MOD;
        
        System.out.println((ans1+ans2)%MOD);
    }
}

class Inversion{
    public long inv(int[] a, int mod){
        long cnt = 0;
        int size = a.length;
        BinaryIndexedTree bit = new BinaryIndexedTree(size);
        
        for(int i=0; i<size; i++){
            int p = a[i];
            bit.add(p, 1);
            cnt += i + 1 - bit.sum(p);
            cnt %= mod;
        }
        return cnt;
    }
    
    public static int[] shrink(int[] a){
		int n = a.length;
		long[] b = new long[n];
		for (int i = 0; i < n; i++){
			b[i] = ((long)a[i] << 32) + i;
        }
		Arrays.sort(b);
		int[] ret = new int[n];
		int p = 1;//1-indexed
		for (int i = 0; i < n; i++){
			if (i > 0 && (b[i]>>32) != (b[i - 1]>>32)){
				p++;
			}
			ret[(int)b[i]] = p;
		}
		return ret;
	}
}

class BinaryIndexedTree{
    int size;
    long[] tree;
    
    public BinaryIndexedTree(int n){
        this.size = n;
        this.tree = new long[n+1];
    }
    
    public long sum(int i){
        long s = 0L;
        while(0<i){
            s += tree[i];
            i -= i & -i;
        }
        return s;
    }
    
    public void add(int i, int x){
        while(i<=size){
            tree[i] += x;
            i += i & -i;
        }
    }
}


Measured memory_bytes: 23892
#pragma GCC optimize ("O2")
#pragma GCC target ("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const ll mod = 998244353;
int A, B, C, D;
ll memo[3001][3001];
ll keisan(int a, int b) {
	if (memo[a][b] != -1) return memo[a][b];

	if (A == a && B == b) {
		return 1;
	}
	if (A == a) {
		return memo[a][b] = keisan(a, b - 1) * a % mod;
	}
	if (B == b) {
		return memo[a][b] = keisan(a - 1, b) * b % mod;
	}

	ll aa = keisan(a, b - 1);
	ll bb = keisan(a - 1, b);
	ll ab = keisan(a - 1, b - 1);

	return memo[a][b] = ((aa * a + bb * b - ab * (a - 1) * (b - 1)) % mod + mod) % mod;
}

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


	cin >> A >> B >> C >> D;

	rep1(i, C) rep1(j, D) memo[i][j] = -1;

	co(keisan(C, D));


	Would you please return 0;
}

Measured memory_bytes: 74416
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


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

    odd = sum(a % 2 for a in A)
    four = sum(a % 4 == 0 for a in A)
    even = N - odd

    if even - four:
        if four >= odd:
            print('Yes')
        else:
            print('No')
    else:
        if four >= odd - 1:
            print('Yes')
        else:
            print('No')


if __name__ == "__main__":
    main()


Measured memory_bytes: 15020
#include<stdio.h>
#include<ctype.h>
#include<string.h>
int main(){
    char p[200],p2[100],s[100];

    scanf("%s",p);
    strcpy(p2,p);
    strcat(p,p2);
    scanf("%s",s);

    if(strstr(p,s)){
        printf("Yes\n");
    }else{
        printf("No\n");
    }
    return 0;
}




Measured memory_bytes: 2056
def main():
    n, k = map(int, input().split())
    *h, = sorted(map(int, input().split()), reverse=True)
    print(sum(h[k:]))


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


Measured memory_bytes: 26024
//#pragma GCC optimize ("O3")
//#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

constexpr int bm = 2461;
ll BIT[50][bm];
int zero[50];
//priority_queue<ll> PQ;
const int AS = 5000;
class saidai_tekitou_heap {
public:
	int HS = 0;
	const ll IM = -8e18;
	ll dat[AS * 2 + 2];
	saidai_tekitou_heap() : dat() {
		dat[0] = -IM;
	}
	void push(ll v) {
		int p = ++HS;
		while (v > dat[p >> 1]) dat[p] = dat[p >> 1], p >>= 1;
		dat[p] = v;
	}
	ll pop() {
		if (HS == 1) {
			HS = 0;
			return dat[1];
		}
		ll ret = dat[1];
		ll v = dat[HS];
		dat[HS--] = IM;
		int j = 2 + (dat[2] < dat[3]);
		while (v < dat[j]) {
			dat[j >> 1] = dat[j];
			j <<= 1;
			j += dat[j] < dat[j + 1];
		}
		dat[j >> 1] = v;
		return ret;
	}
} PQ;
inline ll query(int A, int gin) {
	ll kotae = 0;
	while (gin < bm) {
		kotae = max(BIT[A][gin], kotae);
		gin += gin & -gin;
	}
	return kotae;
}
inline void query2(int A, int gin, ll ti) {
	int tmp = gin;
	while (gin < bm) {
		if (BIT[A][gin] >= ti) return;
		gin += gin & -gin;
	}
	gin = tmp;
	while (gin > 0) {
		if (BIT[A][gin] >= ti) break;
		BIT[A][gin] = ti;
		gin -= gin & -gin;
	}
	PQ.push(ti << 18 | A << 12 | tmp);
}

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


	int N, M, S;
	cin >> N >> M >> S;
	if (S >= 2460) S = 2460;

	vector<ll> E[50];
	rep(i, M) {
		int u, v, a;
		ll b;
		cin >> u >> v >> a >> b;
		u--;
		v--;
		b = a << 8 | b << 16;
		E[u].pb(v | b);
		E[v].pb(u | b);
	}
	int C[50], D[50];
	rep(i, N) {
		cin >> C[i] >> D[i];
	}

	query2(0, S + 1, 4e12);
	ll zenbu = 0;
	ll owari = (1ll << N) - 1;

	while (PQ.HS) {
		auto p = PQ.pop();
		ll ti = p >> 18;
		int i = p >> 12 & 63;
		int gin = p & 4095;
		if (ti < query(i, gin)) continue;

		ll ti2 = ti - D[i];
		int gin2 = gin + C[i];
		if (gin2 > 2460) gin2 = 2460;
		query2(i, gin2, ti2);

		for (auto pp : E[i]) {
			int to = pp & 255;
			ti2 = ti - (pp >> 16);
			gin2 = gin - (pp >> 8 & 255);
			if (gin2 > 0) query2(to, gin2, ti2);
		}
		zenbu |= 1ll << i;
		if (zenbu == owari) break;
	}

	for (int i = 1; i < N; i++) {
		co(ll(4e12 - query(i, 1)));
	}



	Would you please return 0;
}

Measured memory_bytes: 4604
#include <iostream>
#include <vector>
#include <set>

using namespace std;

#define MAXN 200005

int N, M;
vector<int> parent;
vector<int> sz;

void init()
{
    parent.assign(N+1, 1);
    sz.assign(N+1, 1);
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
    }
}

int find(int v)
{
    if (parent[v] == v)
        return v;
    
    return find(parent[v]);
}

bool same(int u, int v)
{
    return find(u) == find(v);
}

void join(int u, int v)
{
    u = find(u);
    v = find(v);
    
    if (u == v)
        return;
    
    if (sz[u] > sz[v])
        swap(u, v);
    
    parent[u] = v;
    sz[v] += sz[u];
}

int main()
{
    cin >> N >> M;
    init();
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        join(a, b);
    }
    set<int, greater<int> > s;
    for (int i = 1; i <= N; i++) {
        s.insert(sz[i]);
    }
    cout << *s.begin() << '\n';
    return 0;
}

Measured memory_bytes: 4824
p = [[0 for i in xrange(10)] for i in xrange(10)]

def drop(x, y, s):
    r = []
    d = [[x, y - 1], [x - 1, y], [x + 1, y], [x, y + 1], \
         [x - 1, y + 1], [x + 1, y + 1], [x - 1, y - 1], [x + 1, y - 1], \
         [x, y + 2], [x - 2, y], [x + 2, y], [x, y - 2]]
    for i in d[0:s*4]:
        if min(i) >= 0 and max(i) < 10: r.append(i)
    p[x][y] += 1
    for i in r:
        p[i[0]][i[1]] += 1

while 1:
    try:
        x, y, s = map(int, raw_input().split(','))
        drop(x, y, s)
    except:
        break

print sum([i.count(0) for i in p])
print max([max(i) for i in p])

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

using namespace std;

struct interval {
    int s, f;

    interval(int s, int f) : s(s), f(f) {}
};

bool compare_f(const interval &x, const interval &y) {
    return x.f < y.f;
}

vector<interval> interval_scheduling(vector<interval> J) {
    vector<interval> A;
    sort(J.begin(), J.end(), compare_f);
    int f = 0;
    for (int i = 0; i < J.size(); ++i) {
        if (J[i].s >= f) {
            A.push_back(J[i]);
            f = J[i].f;
        }
    }
    return A;
}

signed main() {
    int N;
    vector<interval> Is;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        int x, l;
        cin >> x >> l;
        Is.emplace_back(max(0, x - l), x + l);
    }
    auto temp = interval_scheduling(Is);
    cout << temp.size() << endl;
    /*
    for (int i = 0; i < temp.size(); ++i) {
        cout << temp[i].s << " " << temp[i].f << endl;
    }
     */
}

Measured memory_bytes: 3316
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::prelude::BufRead;
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufReader, BufWriter, Write};
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::str::FromStr;

fn main() {
    let line = read_vector::<usize>();
    if line[0] == line[1] && line[1] == line[2] {
        println!("Yes");
    } else {
        println!("No");
    }
}

#[allow(dead_code)]
fn read<T>() -> T
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    return buf.trim().parse().unwrap();
}

#[allow(dead_code)]
fn read_vector<T>() -> Vec<T>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    let mut buf = String::with_capacity(100);
    stdin().read_line(&mut buf).unwrap();
    return buf.split_whitespace().map(|s| s.parse().unwrap()).collect();
}

#[allow(dead_code)]
fn read_matrix<T>() -> Vec<Vec<T>>
where
    T: std::str::FromStr,
    T::Err: std::fmt::Debug,
{
    use std::io::prelude::*;
    let stdin = stdin();
    let mut reader = BufReader::with_capacity(100 * 1024, stdin);
    let mut line = String::with_capacity(100);
    let mut matrix: Vec<Vec<T>> = Vec::new();

    while reader.read_line(&mut line).unwrap() > 0 {
        matrix.push(
            line.trim()
                .split_whitespace()
                .map(|s| s.parse().unwrap())
                .collect(),
        );
        line.clear();
    }

    return matrix;
}

#[allow(dead_code)]
fn read_chars() -> Vec<char> {
    let stdin = stdin();
    let mut buf = String::new();
    let _bytes = stdin.read_line(&mut buf).unwrap();
    return buf.trim().chars().collect();
}


Measured memory_bytes: 4352
from itertools import product
import re
N = int(input())
MOD = 10 ** 9 + 7


dp = [{''.join(last_3): 0 for last_3 in product('AGCT', repeat=3)} for i in range(N + 1)]
dp[0]['TTT'] = 1
NG_pattern = r'.*AGC|.*ACG|.*GAC|A.GC|AG.C|'


for i in range(1, N + 1):
    for last_3 in product('AGCT', repeat=3):
        last_3 = ''.join(last_3)
        for pre_s in 'AGCT':
            if re.match(NG_pattern, pre_s + last_3).group():
                continue
            else:
                dp[i][pre_s + last_3[:-1]] += dp[i - 1][last_3]
                dp[i][pre_s + last_3[:-1]] %= MOD

print(sum(dp[-1].values()) % MOD)


Measured memory_bytes: 4084