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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		if (N<112)
			System.out.println(111);
		else if (N<223)
			System.out.println(222);
		else if (N<334)
			System.out.println(333);
		else if (N<445)
			System.out.println(444);
		else if (N<556)
			System.out.println(555);
		else if (N<667)
			System.out.println(666);
		else if (N<778)
			System.out.println(777);
		else if (N<889)
			System.out.println(888);
		else 
			System.out.println(999);
		sc.close();

	}

}

Measured memory_bytes: 21844
#include <iostream>
#include <stdio.h>
#include <vector> 
#include <math.h> 
#include <algorithm>
using namespace std;
int main(void){
    int n,m,x,y; cin >> n >> m >> x >> y;
    vector<int> X(n);
    vector<int> Y(m);
    int z = -99;
    string answer = "War";
    int i = 0;
    while (i < n) {
        cin >> X[i];
        i++;
    }
    i = 0;
    while (i < m) {
        cin >> Y[i];
        i++;
    }
    while (z < 101) {
        if (x >= z || z > y) {
            z++;
            continue;
        }

        int flag = 1;
        i = 0;
        while (i < n) {
            if(X[i] >= z) {
                flag = 0;
                break;
            }
            i++;
        }
        i = 0;
        while (i < m) {
            if(Y[i] < z) {
                flag = 0;
                break;
            }
            i++;
        }
        if (flag) answer = "No War";
        z++;
    }
    cout << answer << endl;
}

Measured memory_bytes: 3616
#include <iostream>
#include <cmath>
      
int main() {
    int n;
    std::cin >> n;
    while(n--){
        double x1, y1, x2, y2, x3, y3, x4, y4;
        std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        int ix1 = round(x1*100000), iy1 = round(y1*100000),
            ix2 = round(x2*100000), iy2 = round(y2*100000),
            ix3 = round(x3*100000), iy3 = round(y3*100000),
            ix4 = round(x4*100000), iy4 = round(y4*100000);
        int a = iy1 - iy2, b = ix2 - ix1, c = iy3 - iy4, d = ix4 - ix3;
        if(!((long long int)a*d - (long long int)b*c))
            std::cout << "YES" << std::endl;
        else
            std::cout << "NO" << std::endl;
        }
    return 0;
}

Measured memory_bytes: 1236
N = int(input())

def dfs(s):
    if int(s) >N :
        return 0
    if all(s.count(c) > 0 for c in '753'):
        res=1
    else:
        res=0
    for c in '753':
        res += dfs(s+c)
    return res

print(dfs('0'))

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

class Dice{
    public:
    int f[7];
    Dice(){}
        void roll_x(){roll(1,4,6,3);} // to E
        void roll_y(){roll(1,2,6,5);} // to N
        void roll_z(){roll(2,3,5,4);} // 上から見て時計回り
        void roll(int a, int b, int c, int d){
            int t=f[a]; f[a]=f[b]; f[b]=f[c]; f[c]=f[d]; f[d]=t;
        }
        void move(char ch){
            if(ch=='E') roll_x();
            if(ch=='S') for(int i=0;i<3;i++) roll_y();
            if(ch=='W') for(int i=0;i<3;i++) roll_x();
            if(ch=='N') roll_y();
        }
};

bool eq(Dice d1,Dice d2){
    for(int i=1;i<=6;i++){
        if(d1.f[i]!=d2.f[i]) return false;
    }
    return true;
}

bool equal(Dice d1, Dice d2){
    for(int i=0;i<6;i++){
        for(int j=0;j<4;j++){
            if(eq(d1,d2)) return true;
            d1.roll_z();
        }
        if(i%2==0) d1.roll_x();
        else d1.roll_y();
    }
    return false;
}

Dice d[100];
int n;

bool check(){
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(equal(d[i],d[j])) return false;
        }
    }
    return true;
}

int main(){
    cin >> n;
    
    for(int i=0;i<n;i++){
        for(int j=1;j<=6;j++) cin >> d[i].f[j];
    }

    if(check()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define Rep(i, r, n) for (ll i = r; i < n; i++)
#define MOD 1000000007
#define EPS (1 >> 30)
#define INF (1 << 30)
//#define INFll (1LL << 60)

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    //---------------------------------------------
    
    ll n;
    cin>>n;
    vector<string> s(n);
    rep(i,n){
        cin>>s[i];
    }
    ll m=0;
    ll a=0;
    ll r=0;
    ll c=0;
    ll h=0;
    ll ans=0;
    rep(i,n){
        if(s[i].at(0)=='M'){
            m++;
        }
        else if(s[i].at(0)=='R'){
            r++;
        }
        else if(s[i].at(0)=='A'){
            a++;
        }
        else if(s[i].at(0)=='C'){
            c++;
        }
        else if(s[i].at(0)=='H'){
            h++;
        }
    }
    ans+=m*r*a;
    ans+=m*r*c;
    ans+=m*r*h;
    ans+=m*a*c;
    ans+=m*a*h;
    ans+=m*c*h;
    ans+=r*a*c;
    ans+=r*a*h;
    ans+=r*c*h;
    ans+=a*c*h;
    cout<<ans<<endl;
    
}

Measured memory_bytes: 5760
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
from fractions import gcd

def main():
    mod=10**9+7
    N=I()
    ans=1
    for i in range(N):
        t=I()
        ans=(ans*t)//gcd(ans,t)
        
    print(ans)

main()


Measured memory_bytes: 64748
import queue

h, w = [int(i) for i in input().split(" ")]
s = ["" for i in range(0, h)]

for i in range(0, h):
    s[i] = input()

b = [[False for j in range(0, w)] for i in range(0, h)]

c = 0
for i in range(0, h):
    for j in range(0, w):
        if s[i][j] == ".":
            c += 1

q = queue.Queue()
q.put([0, 0, 0])
b[0][0] = True

def addq(i, j, d):
    global b
    global q
    if 0 <= i and i < h and 0 <= j and j < w and not b[i][j] and s[i][j] == ".":
        b[i][j] = True
        q.put([i, j, d])

f = False
while not q.empty():
    qi = q.get()
    if qi[0] == h - 1 and qi[1] == w - 1:
        f = True
        print(c - qi[2] - 1)
        break
    i = qi[0]
    j = qi[1]
    addq(i + 1, j, qi[2] + 1)
    addq(i, j + 1, qi[2] + 1)
    addq(i - 1, j, qi[2] + 1)
    addq(i, j - 1, qi[2] + 1)

if not f:
    print(-1)

Measured memory_bytes: 3952
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
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; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a, b;
  cin >> a >> b;
  cout << a/__gcd(a, b)*b << endl;
  return 0;
}

Measured memory_bytes: 256
import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.complex, std.container, std.math, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


enum MO = 10L^^9 + 7;

void main() {
  try {
    for (; ; ) {
      const N = readInt();
      const S = readToken();
      
      long ans = 1;
      long now = 0;
      foreach (i; 0 .. 2 * N) {
        if (S[i] == "WB"[cast(int)(now % 2)]) {
          // close
          if (now <= 0) {
            ans = 0;
            break;
          }
          ans *= now;
          ans %= MO;
          --now;
        } else {
          // open
          ++now;
        }
      }
      if (now != 0) {
        ans = 0;
      }
      foreach (k; 1 .. N + 1) {
        ans *= k;
        ans %= MO;
      }
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 2684
using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    int N;
    long[] A;
    long[] sum;
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        N = int.Parse(Console.ReadLine());
        string[] str = Console.ReadLine().Split(' ');
        A = new long[N];
        for(int i=0;i<N;i++){
            A[i] = int.Parse(str[i]);
        }
        Array.Sort(A);
        sum = new long[N];
        sum[0] = A[0];
        for(int i=1;i<N;i++){
            sum[i] = sum[i-1] + A[i];
        }
        int bf = 0;
        int bl = N-1;
        while(bf != bl){
            int bc = (bf+bl)/2;
            if(check(bc)){
                bl = bc;
            }
            else{
                bf = bc+1;
            }
        }
        sb.Append((N-bf)+"\n");
    }
    bool check(int c){
        long count = sum[c];
        for(int i=c+1;i<N;i++){
            if(count * 2 >= A[i]){
                count += A[i];
            }
            else{
                return false;
            }
        }
        return true;
    }
}

Measured memory_bytes: 26332
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for i in a:
  d[i] += 1
l = [0, 0]
for k, v in d.items():
  if v >= 4 and k >= max(l):
    l = [k, k]
  elif v >= 2 and k >= min(l):
    l = sorted(l)
    l[0] = k
print(l[0]*l[1])


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

ll X,Y,Z,A,B,C,N;
ll a[1001],b[1001],c[1001],ab[1001];
ll res[1001];

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

  cin>>X>>Y>>Z>>A>>B>>C>>N;
  rep(x,X)a[abs(x-A)%N]++;
  rep(y,Y)b[abs(y-B)%N]++;
  rep(z,Z)c[abs(z-C)%N]++;

  rep(i,N){
    rep(j,N){
      ab[(i+j)%N]+=a[i]*b[j];
    }
  }

  rep(i,N){
    rep(j,N){
      res[(i+j)%N]+=ab[i]*c[j];
    }
  }

  cout<<res[0];
  repl(i,1,N)cout<<" "<<res[i];
  cout<<endl;

  return 0;
}



Measured memory_bytes: 3252
#include<iostream>
#include<string.h>
using namespace std;
int a[10];

int main()
{
    int n,m;
    cin >> n >> m;
    if(n==1&&!m)
    {
        cout << 0 << endl;
        return 0;
    }
    memset(a,-1,sizeof(a));
    bool f = 0;
    for(int i = 1; i <= m; i++)
    {
        int s,c;
        cin >> s >> c;
        if(n!=1&&s==1&&c==0)
        {
            f = 1;
        }
        else if(a[s]==-1)
        {
            a[s] = c;
        }
        else
        {
            //if(a[s]==0)a[s] = c;
            f = a[s] == c ? 0 : 1;
        }
    }
    if(f)
    {
        cout << "-1\n";
        return 0;
    }
    string ans = "";
    for(int i = 1; i <= n; i++)
    {
        if(a[i]==-1&&i==1)
            a[i] = 1;
        else if(a[i]==-1)
            a[i] = 0;
        ans += a[i] + '0';
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n, m, x = map(int, input().split())

ca = [[]]*n

for i in range(n):
    ca[i] = list(map(int, input().split()))

min = 10**15

for i in range(2**n):
    bin_i = bin(i)
    sum = 0
    point = [0]*m
    flag = 1
    l = len(bin_i)-2
    for j in range(l):
        if bin_i[-j-1] == "1":
            sum += ca[j][0]
            for k in range(m):
                point[k] += ca[j][k+1]

    for j in range(m):
        if point[j] >= x:
            pass
        else:
            flag = 0

    if flag:
        if sum <= min:
            min = sum

if min == 10**15:
    print("-1")
else:
    print(min)

Measured memory_bytes: 9248
import java.util.*;

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

    char[] input = scan.next().toCharArray();
    int[] arr = new int[input.length];
    for(int i = 0; i < arr.length; i++) arr[i] = (int)(input[i]-'0');

    int maxLoop = 1<<(arr.length-1);
    long result = 0;
    for(int i = 0; i < maxLoop; i++) {
      long sum = 0;
      long dummySum = arr[0];
      for(int j = 0; j < arr.length-1; j++) {
        if((i&(1<<j))==0) {
          dummySum*=10;
          dummySum += arr[j+1];
        }else {
          sum += dummySum;
          dummySum = arr[j+1];
        }
      }
      sum += dummySum;
      //System.out.println(Integer.toBinaryString(i)+","+sum);
      result += sum;
    }

    System.out.println(result);
  }
}


Measured memory_bytes: 8660
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define ts to_string
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector <string>
#define vvs vector <vector<string>>
#define pq  priority_queue<int>
using ll = long long;
/* ----------------よく使う数字や配列----------------- */
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
const int INF = 2000000000;
const int MINF=-2000000000;
constexpr ll mod = 1e9 + 7;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
/*---------------------template----------------------*/
/*----------------------end--------------------------*/
/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
bool isprime(ll a)//素数判定、primeならtrue,違うならfalse
{
    if (a < 2) return false;
    else if (a == 2) return true;
    else if (a % 2 == 0) return false;
    double m = sqrt(a);
    for (int i = 3; i <= m; i += 2)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    // 素数である
    return true;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
signed main(){
  int N,K;cin>>N>>K;
  cout<<N-K+1<<endl;
}



Measured memory_bytes: 3588
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
A,B,X=map(int, input().split())

if A>X:
    print("NO")
    sys.exit()

if X-A <= B:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 77056
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int main() {
	int N, D, X;
	cin >> N >> D >> X;
	
	int ans = 0;
	REP(i, N) {
		int a; scanf("%d", &a);
		ans += (D - 1) / a + 1;
	}
	ans += X;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			if(n==0) break;
			
			int max = 0;
			String[] codes = new String[n];
			for(int i=0;i<n;i++){
				String s = sc.next();
				codes[i] = "" + s.charAt(0);
				for(int j=0;j<s.length()-1;j++){
					char c = s.charAt(j);
					if(c=='a' || c=='i' || c=='u' || c=='e' || c=='o') codes[i] += s.charAt(j+1);
				}
				max = Math.max(max, codes[i].length());
			}
			
			String ans = "-1";
			for(int i=1;i<=max;i++){
				ArrayList<String> list = new ArrayList<String>();
				for(int j=0;j<n;j++){
					String s = codes[j];
					if(i<codes[j].length())	s = codes[j].substring(0, i);
					if(list.contains(s)) break;
					else list.add(s);
				}
				if(list.size()==n){
					ans = Integer.toString(i);
					break;
				}
			}
			
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 39816
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

template <int base>
int digit_sum(int n)
{
	int sum = 0;
	while (n > 0) {
		sum += n % base;
		n /= base;
	}
	return sum;
}

using ivec = vector<int>;

ivec read_int_args()
{
	int N;
	cin >> N;
	ivec v(N);
	for (auto& e : v) {
		cin >> e;
	}
	return v;
}

int main()
{
	int N;
	cin >> N;
	ivec B(N-1);
	for (auto& e : B) {
		cin >> e;
	}
	int sum = 0;
	sum += B[0];
	for (int i = 1; i <= N - 1; i++) {
		int a = B[i - 2];
		int b = B[i - 1];
		if (a > b) a = b;
		sum += a;
	}
	sum += B[N-2];
	
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>	
#include<cmath>
using namespace std;
int main() {
	long long n, a, b = 0, ans = 0; cin >> n;
	for (int h = 0; h < n; h++) {
		cin >> a;
		if (a == 0) {
			b = 0;
		}
		if (a % 2 == 0) {
			ans += a / 2;
		}
		else if (b == 1) {
			ans += a / 2 + 1; b = 0;
		}
		else {
			ans += a / 2; b = 1;
		}
	}
	cout << ans << endl;
	cin >> n;
}

Measured memory_bytes: 256
//from PKU1125
main(){
	int i,j,n,k,K,a,b,d,dist[10][10];
	for(;scanf("%d",&k),k;){
		/*initialize*/
		memset(dist,11,sizeof(dist));
		for(i=0;i<=9;i++)dist[i][i]=0;
		for(n=0;k;k--){
			scanf("%d%d%d",&a,&b,&d);
			if(n<a)n=a;
			if(n<b)n=b;
			dist[a][b]=d,dist[b][a]=d;
		}

		{/*warshall-floyd*/
			int k,i,j;
			for(k=0;k<=n;k++)
				for(i=0;i<=n;i++)
					for(j=0;j<=n;j++)
						if(dist[i][j]>dist[i][k]+dist[k][j])
							dist[i][j]=dist[i][k]+dist[k][j];
		}

		for(k=99999999,i=0;i<=n;i++){
			for(d=j=0;j<=n;j++)d+=dist[i][j];
			if(k>d)k=d,K=i;
		}
		printf("%d %d\n",K,k);
	}
	exit(0);
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

const ll N_MAX = 202020;

ll inv[N_MAX],fac[N_MAX],finv[N_MAX];
void make(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<N_MAX;i++){
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        fac[i]=fac[i-1]*(ll) i%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}

ll Combination(ll C, ll D){
    if(C<D) return 0;
    return fac[C]*(finv[D]*finv[C-D]%mod)%mod;
}

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

ll pows(ll x, ll k, ll mod){
	if(k == 1) return x;
	ll tmp = pows(x, k/2, mod);
	tmp *= tmp;
	tmp %= mod;
	if(k%2 == 0){
		return tmp;
	}else{
		return tmp * x % mod;
	}
}

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

    ll B, W;
    cin >> B >> W;
    ll mt = modinv(2, mod);

    vector<ll> p(202020, 0), q(202020, 0);
    REP(i, B+W-1){
    	p[i+1] = p[i] + (Combination(i, B-1) * pows(mt, i+1, mod)%mod);
    	p[i+1] %= mod;
    	q[i+1] = q[i] + (Combination(i, W-1) * pows(mt, i+1, mod)%mod);
    	q[i+1] %= mod;
    }
    REP(i, B+W){
    	ll res = (1 - p[i] + q[i] + mod) * mt;
    	cout << res%mod << endl;
    }
    return 0;
}

Measured memory_bytes: 10112
/*
 *
 * Author: r3gz3n
 * 
 * 3b 13 12 9 56 4e
 * 6 56 a a 5f f
 * 6 56 47 18 56 d
 * 13 46 14 1f 13 27
 * 52 52 a 5a 47 1
 * 1d 13 b 1b 49 17
 *
 */


#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;


#define fi first
#define se second


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

#define rep(i, a, b, k) for(__typeof(a) i = a;i < b;i += k)


#define endl '\n'


typedef vector<int> vii;

typedef pair<int, int> pii;


class Solution {
public:
    
    vii  ans;
    vector<bool> vis;
    int x, y, n;
    void bfs(int from) {
        queue<pii> q;
        q.push({from, 0});
        vis[from] = true;
        while(!q.empty()) {
            pii p = q.front();
            q.pop();
            if (p.fi > from)
                ans[p.se]++;
            if (p.fi < n and vis[p.fi+1] == false) {
                q.push({p.fi+1, p.se+1});
                vis[p.fi+1] = true;
            }
            if (p.fi > 1 and vis[p.fi-1] == false) {
                q.push({p.fi-1, p.se+1});
                vis[p.fi-1] = true;
            }
            if (p.fi == x and vis[y] == false) {
                q.push({y, p.se+1});
                vis[y] = true;
            }
        }
    }

    void solve(std::istream& in, std::ostream& out) {
        in >> n >> x >> y;
        vis = vector<bool>(n+1, false);
        ans = vii(n, 0);
        rep(i, 1, n, 1) {
            fill(all(vis), false);
            bfs(i);
        }
        rep(i, 1, n, 1) out << ans[i] << endl;
    }
};

void solve(std::istream& in, std::ostream& out)
{
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}


#include <fstream>
#include <iostream>


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


    istream& in = cin;


    ostream& out = cout;

    solve(in, out);
    return 0;
}




Measured memory_bytes: 256
def solve(a,i,sa,sb):
	if 2*sa >= all: return 2*sa-all
	if 2*sb >= all: return 2*sb-all
	return min(solve(a,i+1,sa+a[i],sb),solve(a,i+1,sa,sb+a[i]))
	
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	print solve(a,1,a[0],0)

Measured memory_bytes: 4244
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
#define pint pair<int, int>
#define vint vector<int>
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;
//const int MOD=998244353;
ll gcd(ll a,ll b){
    a=abs(a); b=abs(b);
    if(a==0||b==0) return a+b;
    else if(a>=b) return gcd(a%b,b);
    else return gcd(a,b%a);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}

int main(){
	ll n,m;
	string s,t;
	cin>>n>>m>>s>>t;
	ll g=gcd(n,m);
	ll l=lcm(n,m);
	bool f=true;
	FOR(i,0,g){
		if(s[i*(n/g)]!=t[i*(m/g)]) f=false;
	}
	if(f) co(l);
	else co(-1);
}


Measured memory_bytes: 512
a, b, c, d = map(int, input().split())

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(x, y):
    return x * y // gcd(x, y)


x = b//c + b//d - b//lcm(c,d)
y = (a-1)//c + (a-1)//d - (a-1)//lcm(c,d)

print((b-a+1)-(x-y))

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

int n, a, b;
char s[100055];

int main() {
	scanf("%d %d %d", &n, &a, &b);
	scanf("\n%s", s);

	int passed = 0, b_th = 0;

	for (int i = 0; i < n; i++) {
		bool pass = false;
		
		if (s[i] == 'a' && passed < a + b) pass = true;
		if (s[i] == 'b' && passed < a + b && b_th < b) pass = true;

		if (pass) {
			puts("Yes");
			passed++;
		} else puts("No");

		if (s[i] == 'b') b_th++;
	}

	return 0;
}

Measured memory_bytes: 768
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

/**
 * Property Distribution
 */
public class Main {

	static char DISTRIBUTED = '\0';
	static Deque<int[]> queue;
	static int count;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while (!(line = br.readLine()).equals("0 0")) {

			int h = Integer.parseInt(line.substring(0, line.indexOf(' ')));
			int w = Integer.parseInt(line.substring(line.indexOf(' ') + 1));

			// read in.
			char[][] prop = new char[h + 2][w + 2];
			for (int i = 1; i < h + 1; ++i) {
				line = br.readLine();
				for (int j = 1; j < w + 1; ++j) {
					prop[i][j] = line.charAt(j - 1);
				}
			}

			// solve
			queue = new ArrayDeque<int[]>();
			count = 0;
			for (int i = 1; i < h + 1; ++i) {
				for (int j = 1; j < w + 1; ++j) {
					if (prop[i][j] != DISTRIBUTED) {
						char fruit = prop[i][j];
						queue.offerLast(new int[] { i, j });
						while (!queue.isEmpty()) {
							distribute(prop, fruit);
						}
						++count;
					}
				}
			}
			// print
			System.out.println(count);
		}
	}

	static void distribute(char[][] prop, char fruit) {

		final int V[] = { 1, -1, 0, 0 };
		final int H[] = { 0, 0, 1, -1 };

		int xy[] = queue.pollLast();
		int x = xy[0];
		int y = xy[1];

		if (prop[x][y] == fruit) {

			// prop[x][y] = DISTRIBUTED;
			prop[x][y] ^= prop[x][y];

			for (int i = 0; i < 4; ++i) {
				int xv, yh;
				xv = x + V[i];
				yh = y + H[i];
				if (prop[xv][yh] == fruit) {
					queue.offerLast(new int[] { xv, yh });
				}
			}
		}
	}
}

Measured memory_bytes: 25964
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

############
############
############


N = int(input())
MOD = 10**9+7
memo = [ {} for _ in range(N+1) ]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if "".join(t).count("AGC") >= 1:
            return False
    return True

def dfs(current, last3):
    if last3 in memo[current]:
        return memo[current][last3]
    if current == N:
        return 1
    ret = 0
    for c in "ACGT":
        if ok(last3 + c):
            ret = (ret + dfs(current + 1, last3[1:] + c)) % MOD
    memo[current][last3] = ret
    return ret

print(int(dfs(0, "TTT") % MOD))


Measured memory_bytes: 48348
#include <bits/stdc++.h>
using namespace std;
typedef long long 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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/


int main(){
    string s; cin >> s;
    
    if(s[0] == s[1] && s[1] == s[2]){
        cout << "Yes" << endl;
        return 0;
    }
    else if(s[1] == s[2] && s[2] == s[3]){
        cout << "Yes" << endl;
        return 0;
    }
    else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIS = lambda: input().split()


def main():
    a, b, k = MI()
    for i in range(max(a, b), 0, -1):
        k -= (a % i == 0) and (b % i == 0)
        if k == 0:
            return i


if __name__ == "__main__":
    print(main())


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

int main()
{
    long long A, B, C;
    cin >> A >> B >> C;

    long long array[3] = {A, B, C};
    sort(array, array+3);

    long long ans;
    if (array[2] % 2 == 0)
        ans = 0;
    else
        ans = array[0] * array[1];
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
using namespace std;
const int N = 1e5+5;
void fast(){std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
int main()
{
	fast();
	string s,t;
	int n;
	cin>>n>>s>>t;
	for(int i=0;i<n;i++)cout<<s[i]<<t[i];
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
#define MOD 1000000007
int dig[5];
int main(){
	int n;
	cin >> n;
	for(int i=0;i<4;i++){
		dig[i]=n%10;
		n/=10;
	}
	if(dig[0]==dig[1]&&dig[1]==dig[2])cout << "Yes" << endl;
	else if(dig[1]==dig[2]&&dig[2]==dig[3])cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<sstream>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define loop(i,a,b) for(i=(ll)a;i<(ll)b;i++)
#define revloop(i,a,b) for(i=(ll)a;i>=(ll)b;i--)
#define stloop(it,v) for(it=v.begin();it!=v.end();++it)
#define ii pair<ll,ll>
#define MP make_pair
#define pb push_back
#define f first
#define s second
#define ll long long int
#define vi vector<int>
#define rs resize
int a[100005],b[100005],cum1[100005],cum2[100005],n,m,i;
ll a1,a2;
int main()
{  std::ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin>>n>>m;
   loop(i,0,n)
   {
    cin>>a[i];
    if(i==0)
     cum1[i]=a[i];
    else
     cum1[i]=(cum1[i-1]+a[i])%mod;
   }
   loop(i,0,m)
   {
    cin>>b[i];
    if(i==0)
     cum2[i]=b[i];
    else
     cum2[i]=(cum2[i-1]+b[i])%mod;
   }
   loop(i,1,n)
    a1=(a1+i*1LL*a[i]-cum1[i-1]+mod)%mod;
   loop(i,1,m)
    a2=(a2+i*1LL*b[i]-cum2[i-1]+mod)%mod;
   a1=(a1*1LL*a2)%mod;
   cout<<a1;
   return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<stack>
using namespace std;
string s; 
bool unbalanced(int i)
{
	int a = s[i], b = s[i+1], c = s[i+2];
	return a==b || b==c || a==c;
}
pair<int,int> solve()
{	
	cin >> s;
	int n = s.length();
	for(int i = 0; i < n-1; i++)
		if(s[i]==s[i+1])
			return {i+1,i+2};
			
	for(int i = 0; i < n-2; i++)
		if(unbalanced(i))
			return {i+1,i+3};
	return {-1,-1};
}
int main()
{
	auto p = solve();
	cout<<p.first<<" "<<p.second<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>

#define MOD 1000000007
using ll = long long;
using namespace std;

int N, Q;
string S;
vector<char> t, d;

int isDel(int now) {
	for (int i = 0; i < Q; i++)
	{
		if (now != -1 && now != N && S[now] == t[i]) {
			if (d[i] == 'L') {
				now--;
			}
			else {
				now++;
			}
		}
	}
	if (now == -1) {
		return -1;
	}
	else if (now == N) {
		return 1;
	}
	else {
		return 0;
	}
}

int main() {
	cin >> N >> Q >> S;
	for (int i = 0; i < Q; i++)
	{
		char a, b;
		cin >> a >> b;
		t.push_back(a);
		d.push_back(b);
	}
	// Find the left edge
	int left = 0, right = N;
	while (right - left > 1) {
		int mid = (left + right) / 2;
		if (isDel(mid) >= 0) {
			right = mid;
		}
		else {
			left = mid;
		}
	}
	int LE = right;
	// Find the right edge
	left = 0, right = N;
	while (right - left > 1) {
		int mid = (left + right) / 2;
		if (isDel(mid) <= 0) {
			left = mid;
		}
		else {
			right = mid;
		}
	}
	int RE = left;
	cout << RE - LE + 1 << endl;
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    ll n;
    cin >> n;
    ll answer = 0;
    REP(i,n){
        ll tmp;
        cin >> tmp;
        answer += tmp;
    }

    cout << answer - n << endl;

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import math

l = int(input())

r = math.floor(math.log2(l))

num_vertex = 0
num_edge = 0

num_vertex += r+1

print_list = []
for i in range(r):
    print_list.append([i+1, i+2, 0])
    print_list.append([i+1, i+2, 2**i])
    num_edge += 2


for i in reversed(range(r+1)):
    if l-2**i >= 2**r:
        print_list.append([i+1, r+1, l-2**i])
        l -= 2**i
        num_edge += 1

print(num_vertex, num_edge)
for i in print_list:
    print(*i)


Measured memory_bytes: 9276
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
ll n,h,w,a,b,s[80][80][12800],dp[80][80];
queue<P> que;
int main(void){
    cin>>h>>w;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>dp[i][j];
        }
    }
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a;
            dp[i][j]=abs(dp[i][j]-a);
        }
    }
    s[0][0][dp[0][0]]=1;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
                for(int k=0;k<12800;k++){
                    if(s[i][j][k]==1){
                        if(i+1<h){
                            s[i+1][j][k+dp[i+1][j]]=1;
                            s[i+1][j][abs(k-dp[i+1][j])]=1;
                        }
                        if(j+1<w){
                            s[i][j+1][k+dp[i][j+1]]=1;
                            s[i][j+1][abs(k-dp[i][j+1])]=1;
                        }
                    }
                }
            }
    }
    for(int i=0;i<12800;i++){
        if(s[h-1][w-1][i]==1){
            cout<<i<<endl;
            return 0;
        }
    }
}


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

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
//    ll ma=-1e9-1,mi=1e9+1,res,r;
//    res=ma;
//    for(int i=0;i<n;i++){
//        cin >> r;
//        res=max(res,r-mi);
//        if(r<mi)mi=r;
//    }
////    cout << "max:mi " << ma << ":" << mi << endl;
//    cout << res << endl;

    ll r;
    cin >> r;
    ll mi=r,res=-1e9;
    for(int i=1;i<n;i++){
        cin >> r;
        res=max(res,r-mi);
        if(mi>r)mi=r;
    }
    cout << res << endl;
}



Measured memory_bytes: 3212
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007


#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

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

Measured memory_bytes: 256
from collections import deque
INF = float("inf")
TO = 0;  CAP = 1;  REV = 2
class Dinic:
    def __init__(self, N):
        self.N = N
        self.V = [[] for _ in range(N)]  # to, cap, rev
        # 辺 e = V[n][m] の逆辺は V[e[TO]][e[REV]]
        self.level = [0] * N

    def add_edge(self, u, v, cap):
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, 0, len(self.V[u])-1])

    def bfs(self, s: int) -> bool:
        self.level = [-1] * self.N
        self.level[s] = 0
        q = deque()
        q.append(s)
        while len(q) != 0:
            v = q.popleft()
            for e in self.V[v]:
                if e[CAP] > 0 and self.level[e[TO]] == -1:  # capが1以上で未探索の辺
                    self.level[e[TO]] = self.level[v] + 1
                    q.append(e[TO])
        return True if self.level[self.g] != -1 else False  # 到達可能

    def dfs(self, v: int, f) -> int:
        if v == self.g:
            return f
        for i in range(self.ite[v], len(self.V[v])):
            self.ite[v] = i
            e = self.V[v][i]
            if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
                d = self.dfs(e[TO], min(f, e[CAP]))
                if d > 0:  # 増加路
                    e[CAP] -= d  # cap を減らす
                    self.V[e[TO]][e[REV]][CAP] += d  # 反対方向の cap を増やす
                    return d
        return 0

    def solve(self, s, g):
        self.g = g
        flow = 0
        while self.bfs(0):  # 到達可能な間
            self.ite = [0] * self.N
            f = self.dfs(s, INF)
            while f > 0:
                flow += f
                f = self.dfs(s, INF)
        return flow


v, e = map(int, input().split())
dinic = Dinic(v)
for _ in range(e):
    dinic.add_edge(*map(int, input().split()))
print(dinic.solve(0, v-1))



Measured memory_bytes: 6320
#include <stdio.h>
int main(void)
{
    int i,n,m;
    char array[256];
    char a[2];
    char b[2];
    char input[2];
    while(1)
    {
        for(i=0;i<256;i++)
        {
            array[i] = i;
        }
        scanf("%d",&n);
        if(n == 0)return 0;
        for(i=0;i<n;i++)
        {
            scanf("%s %s",a,b);
            array[a[0]] = b[0];
        }
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%s",input);
            printf("%c",array[input[0]]);
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 2600
A = int(input())
B = int(input())
C = int(input())
X = int(input())
N500 = X // 500
R1 = X % 500
N100 = R1 // 100
R2 = R1 % 100
N50 = R2 // 50
count = 0
if R2 % 50 != 0:
	print(count)
	exit(0)
li = []
while N500>=0:
	while N100>=0:
		li.append((N500, N100, N50))
		N100 -= 1
		N50 += 2
	N100 = (N50 - 2) // 2
	N50 = (N50 - 2) % 2
	N500 -= 1
	N100 += 5

for n500, n100, n50 in li:
	if n500<=A and n100<=B and n50<=C:
		count += 1

print(count)

Measured memory_bytes: 3316
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        else:
            if self.size[x] < self.size[y]:
                self.par[x] = y
                self.size[y] += self.size[x]
            else:
                self.par[y] = x
                self.size[x] += self.size[y]
    def check(self, x, y):
        return self.find(x) == self.find(y)
    def cnt(self, x):
        return self.size[self.find(x)]

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(M)]

uf = UnionFind(N+1)
cnt = N*(N-1)//2
Ans = [0]*(M+1)
Ans[-1] = cnt
for i in range(M):
    a,b = AB[M-1-i]
    # 元々連結な場合
    if uf.check(a,b):
        Ans[M-1-i] = cnt
    # 元々連結ではない場合
    else:
        cnt -= uf.cnt(a)*uf.cnt(b)
        Ans[M-1-i] = cnt
    uf.unite(a,b)

for i in range(1,M+1):
    print(Ans[i])

Measured memory_bytes: 23364
#include<cstdio>

int main(void){
	int n, i;
	scanf("%d", &n);
	int F[n+1];
	F[0] = F[1] = 1;
	for(i = 2;i <= n;i++)
		F[i] = F[i-1] + F[i-2];
	printf("%d\n", F[n]);
	return 0;
}

Measured memory_bytes: 2720
#include <iostream>
using namespace std;
int H, W, h, w;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> H >> W >> h >> w;

  if ((H % h) == 0 && (W % w) == 0) {
    cout << "No" << endl;
    return 0;
  } 

  cout << "Yes" << endl;
  bool rev = false;
  if ((H % h) == 0) {
    swap(W, H);
    swap(w, h);
    rev = true;
  }
  // assert(H % h > 0);

  int c1 = 1 + 300000;
  int c2 = -h + (1 - h) * 300000;


  if (rev) {
    for(int j  = 0; j < W; ++j) {
      for(int i = 0; i < H; ++i) {
        if ((i % h) == h - 1) {
          cout << c2 << ' ';
        } else {
          cout << c1 << ' ';
        }
      }

      cout << '\n';
    }

    return 0;
  }

  // else
  for(int i = 0; i < H; ++i) {
    if ((i % h) == h - 1) {
      for(int j = 0; j < W; ++j) {
        cout << c2 << ' ';
      }
    } else {
      for(int j = 0; j < W; ++j) {
        cout << c1 << ' ';
      }
    }

    cout << '\n';
  }
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll n;
    string ans;
    cin >> n;
    ll i = 1;
    while(n != 0){
        ans += (n % (i*(-2)) ? "1" : "0");
        if(n % (i*(-2)))n -= i;
        i *= (-2);
    }
    reverse(all(ans));
    cout << (ans.size() ? ans : "0") << endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <set>
#include <math.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll mod = 1000000007;
const ll INF = 1000000000000000;
ll bit[100010], num;
ll par[100010];
ll n, m, s, t;

struct edge { ll to, cost; };
ll V;
vector<edge> G[300010];
ll d[300010];

void dijkstra(ll s)
{
	priority_queue<P, vector<P>, greater<P>> que;
	for (int i = 0; i <= 300010; i++)
	{
		d[i] = INF;
	}
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		ll v = p.second;
		if (d[v] < p.first) continue;
		for (ll i = 0; i < G[v].size(); i++)
		{
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

ll sum(ll i)
{
	ll s = 0;
	while (i > 0)
	{
		s += bit[i];
		i -= i & -i;
	}
	return s;
}

void add(ll i, ll x)
{
	while (i <= num)
	{
		bit[i] += x;
		i += i & -i;
	}
}

ll po(ll x, ll y)
{
	if (y == 0) return 1;
	if (y % 2)
	{
		return po(x, y - 1) * x % mod;
	}
	else
	{
		ll yyy = po(x, y / 2);
		return yyy * yyy % mod;
	}
}

ll div(ll x)
{
	return po(x, mod - 2);
}

int main(void)
{
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		ll u, v;
		cin >> u >> v;
		G[u].push_back(edge{ v + n, 1 });
		G[u + n].push_back(edge{ v + n * 2, 1 });
		G[u + n * 2].push_back(edge{ v, 1 });
	}
	cin >> s >> t;
	dijkstra(s);
	if (d[t] == INF)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << d[t] / 3 << endl;
	}
	int www;
	cin >> www;
}


Measured memory_bytes: 19840
#include <stdio.h>
int main(){
  int a, b, c, x=0;
  scanf("%d %d %d", &a, &b, &c);
  if(b>c) {x=b; b=c; c=x;}
  if(a>b) {x=a; a=b; b=x;}
  if(b>c) {x=b; b=c; c=x;}

  printf("%d %d %d\n",a ,b, c);

  return 0;
}

Measured memory_bytes: 596