akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on 2019/2/
Solved on 2019/2/
@author: shinjisu
"""


# ARC 067 C Factors of Factorial
import math


def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def getIntLines(n): return [int(input()) for i in range(n)]


def getIntMat(n):
    mat = []
    for i in range(n):
        mat.append(getIntList())
    return mat


def zeros2(n, m): return [zeros(m)]*n


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7


def dmp(x, cmt=''):
    global debug
    if debug:
        if cmt != '':
            print(cmt, ':  ', end='')
        print(x)
    return x


def getDivisor(n):
    div = []
    for i in range(2, n+1):
        if n % i == 0:
            div.append(i)
    return div


# n以下の素数を求める - エラトステネスのふるい
def getPrime(n):
    prime = [2]
    num = [i for i in range(3, n+1, 2)]
    while num != []:
        p = num.pop(0)  # 先頭は素数
        prime.append(p)
        for a in num:  # 素数で割り切れる数を除去
            if a % p == 0:
                num.remove(a)
    return prime


# 素因数分解する
def getPrimeFactor(n):
    if n <= 1:
        return [1], [1]
    prime = getPrime(n)
    factor = []
    power = []
    for a in prime:
        pw = 0
        while n % a == 0:
            pw += 1
            n //= a
        if pw > 0:
            factor.append(a)
            power.append(pw)
    return factor, power


def probC():
    N = getInt()
    dmp(N)
    divisor = zeros(N+1)
    for i in range(2, N+1):
        factor, power = getPrimeFactor(i)
        dmp((factor,power), 'factor,power')
        for j in range(len(factor)):
            divisor[factor[j]] += power[j]
    dmp(divisor)
    divCount = 1
    for i in range(2, N+1):
        divCount = divCount * (divisor[i]+1) % N1097
    return divCount


debug = False  # True False
ans = probC()
print(ans)
#for row in ans:
#    print(row)


"""
def getPrimeOld(n):
    prime = [2]
    num = [i for i in range(3, n+1, 2)]
    num.reverse()
    while num != []:
        p = num.pop()  # 末尾は素数
        prime.append(p)
        for a in num:  # 素数で割り切れる数を除去
            if a % p == 0:
                num.remove(a)
    return prime
"""


Measured memory_bytes: 3192
app = "APPROVED"
ng = "DENIED"

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

ok = True

for i, a in enumerate(A):
    if a % 2 == 0 and a % 3 != 0 and a % 5 != 0:
        ok = False

if ok:
    print(app)
else:
    print(ng)





Measured memory_bytes: 3060
//2018年  3月 23日 金曜日 15:49:37 JST
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int A[MAX_N], B[MAX_N], P[MAX_N];

void solve() {
	cin >> N;
	rep(i, 0, N) {
		int a; cin >> a; a--;
		P[a] = i;
	}
	A[0] = 0; B[0] = P[0];
	int bo = 0;
	rep(i, 1, N) {
		int a = P[i - 1], b = P[i];
		if(a < b) {
			A[i] = A[i - 1] + b - a;
			B[i] = B[i - 1];
			A[i]++;
			B[i]--;
		}
		else {
			A[i] = A[i - 1];
			B[i] = B[i - 1] - (a - b);
			A[i]++;
			B[i]--;
		}
		MIN(bo, A[i]);
		MIN(bo, B[i]);
	}
	rep(i, 0, N) {
		cout << A[i] - bo + 1 << " ";
	}
	cout << "\n";
	rep(i, 0, N) {
		cout << B[i] - bo + 1 << " ";
	}
	cout << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 896
import java.util.*;
import java.awt.Point;

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;

			HashMap<Integer,Point> built = new HashMap<Integer,Point>();
			HashMap<Integer,ArrayList<Edge>> map = new HashMap<Integer,ArrayList<Edge>>();

			for(int i=0;i<n;i++){
				built.put(sc.nextInt(),new Point(sc.nextInt(),sc.nextInt()));
			}

			for(int id : built.keySet()){
				map.put(id,new ArrayList<Edge>());

				for(int tid : built.keySet()){
					if(id == tid) continue;

					Point from = built.get(id);
					Point to = built.get(tid);
					double cost = from.distance(to);

					if(cost <= 50) map.get(id).add(new Edge(id,tid,cost));
				}
			}

			int m = sc.nextInt();
			while(m-- > 0){
				int s = sc.nextInt();
				int g = sc.nextInt();
				State ans = getPath(s,g,map);

				System.out.println(ans == null ? "NA" : ans);
			}
		}
	}

	private static State getPath(int s,int g,HashMap<Integer,ArrayList<Edge>> map){
		PriorityQueue<State> open = new PriorityQueue<State>();
		HashSet<State> closed = new HashSet<State>();

		ArrayList<Integer> tmp = new ArrayList<Integer>();
		tmp.add(s);
		open.add(new State(s,0,tmp));

		State ans = null;

		while(!open.isEmpty()){
			State st = open.poll();
			if(closed.contains(st)) continue;
			closed.add(st);

			if(st.n == g){
				ans = st;
				break;
			}

			open.addAll(st.nexts(map));
		}

		return ans;
	}
}

class Edge{
	int from,to;
	double cost;

	public Edge(int from,int to,double cost){
		this.from = from;
		this.to = to;
		this.cost = cost;
	}

	public String toString(){
		return String.format("[%d,%d,%.2f]",from,to,cost);
	}
}

class State implements Comparable<State>{
	int n;
	double cost;
	ArrayList<Integer> path;

	public State(int n,double cost,ArrayList<Integer> path){
		this.n = n;
		this.cost = cost;
		this.path = path;
	}

	public List<State> nexts(HashMap<Integer,ArrayList<Edge>> map){
		List<State> res = new ArrayList<State>();
		for(Edge e : map.get(n)){
			ArrayList<Integer> tmp = new ArrayList<Integer>(path);
			tmp.add(e.to);
			res.add(new State(e.to,cost+e.cost,tmp));
		}
		return res;
	}

	public int compareTo(State st){
		if(this.cost < st.cost) return -1;
		else if(this.cost > st.cost) return 1;
		return 0;
	}

	public boolean equals(Object o){
		State st = (State)o;
		return this.n == st.n;
	}

	public int hashCode(){
		return n;
	}

	public String toString(){
		String res = "" + path.get(0);
		for(int i=1;i<path.size();i++){
			res += " " + path.get(i);
		}

		return res;
	}
}

Measured memory_bytes: 12000
#include <stdio.h>
#define N 100000
#define INF 2147483647

struct Pair{
  char c;
  int num;
};

struct Pair X[N / 2 + 2], Y[N / 2 + 2];

void merge(struct Pair A[], int n, int left, int mid, int right){
  int i, j, k;
  int n1 = mid - left;
  int n2 = right - mid;
  for(i = 0; i < n1; i++){
    X[i] = A[left + i];
  }
  for(i = 0; i < n2; i++){
    Y[i] = A[mid + i];
  }
  X[n1].num = INF;
  Y[n2].num = INF;
  i = 0;
  j = 0;
  for(k = left; k < right; k++){
    if(X[i].num <= Y[j].num){
      A[k] = X[i++];
    }else {
      A[k] = Y[j++];
    }
  }
}

void mergeSort(struct Pair A[], int n, int left, int right){
  int mid;
  if(left + 1 < right){
    mid = (left + right) / 2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

int partition(struct Pair A[], int n, int p, int r){
  int i, j;
  struct Pair t, g;
  g = A[r];
  i = p - 1;
  for(j = p; j < r; j++){
    if(A[j].num <= g.num){
      i++;
      t = A[i];
      A[i] = A[j];
      A[j] = t;
    }
  }
  t = A[i + 1];
  A[i + 1] = A[r];
  A[r] = t;
  return i + 1;
}

void quickSort(struct Pair A[], int n, int p, int r){
  int q;
  if(p < r){
    q = partition(A, n, p, r);
    quickSort(A, n, p, q - 1);
    quickSort(A, n, q + 1, r);
  }
}

int main(){
  int i, n, v;
  struct Pair A[N], B[N];
  char cc[10];
  int stable = 1;

  scanf("%d", &n);

  for(i = 0; i < n; i++){
    scanf("%s %d", cc, &v);
    A[i].c = cc[0];
    B[i].c = A[i].c;
    A[i].num = v;
    B[i].num = A[i].num;
  }

  mergeSort(A, n, 0, n);
  quickSort(B, n, 0, n - 1);

  for(i = 0; i < n; i++){
    if(A[i].c != B[i].c){
      stable = 0;
    }
  }

  if(stable == 1){
    printf("Stable\n");
  }else{
    printf("Not stable\n");
  }
  for(i = 0; i < n; i++){
    printf("%c %d\n", B[i].c, B[i].num);
  }

  return 0;
}



Measured memory_bytes: 4144
import java.util.Scanner;

public class Main {

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

//    	File file = new File("test.txt");
//    	Scanner sc = new Scanner(file);
    	Scanner sc = new Scanner(System.in);
    	int ans = 0;
    	int N = sc.nextInt();
    	int M = sc.nextInt();
    	int[] ary = new int[M];
    	for(int i = 0; i < N; i++){
    		int cnt = sc.nextInt();
    		for(int j = 0; j < cnt; j++){
    			ary[sc.nextInt()-1]++;
    		}
    	}
    	sc.close();
    	for(int sum : ary){
    		if(sum == N) ans++;
    	}
    	System.out.println(ans);
    }

}


Measured memory_bytes: 23468
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

LL calc(LL s, LL len) {
    return len * (len - 1) / 2 + s * len;
}

int N;
LL K;

LL A[100011];
LL B[100011];
LL C[100011];
pair<LL, int> P[100011];

void MAIN() {
    scanf("%d%lld", &N, &K);

    LL small = calc(K, 2*N);
    LL large = calc(K+2*N, N);
    //eprintf("%lld %lld\n", small, large);

    bool yes = true;
    if (small > large) {
	yes = false;
    }
    if (yes) {
	int len = 0;
	REP (i, N) {
	    LL v = K+i;
	    if (v % 2 == 0) A[len++] = v;
	}
	REP (i, N) {
	    LL v = K+i;
	    if (v % 2 == 1) A[len++] = v;
	}

	REP (i, N) {
	    C[i] = K+2*N+i;
	    B[i] = C[i] - A[i];
	}

	REP (i, N) P[i] = make_pair(B[i], i);
	sort(P, P+N);
	REP (i, N) B[P[i].second] = N+K+i;
#ifdef LOCAL
	REP (i, N) assert(A[i] + B[i] <= C[i]);
	vector<LL> v;
	REP (i, N) {
	    v.push_back(A[i]);
	    v.push_back(B[i]);
	    v.push_back(C[i]);
	}
	sort(v.begin(), v.end());
	REP (i, v.size()) assert(v[i] == K+i);
#endif
    }

    if (yes) {
	REP (i, N) printf("%lld %lld %lld\n", A[i], B[i], C[i]);
    } else {
	puts("-1");
    }
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}



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

int main(){
    int a,b;
    cin >> a >> b;

    if(a < b){
        cout << "a < b" << endl;
    } else if(a > b) {
        cout << "a > b" << endl;
    }else {
        cout << "a == b" << endl;
    }
return 0;
}

Measured memory_bytes: 3100
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;

/**
 * Lottery Checker
 */
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		String[] words;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int n, m;
			n = parseInt(line.substring(0, line.indexOf(' ')));
			m = parseInt(line.substring(line.indexOf(' ') + 1));
			if ((n | m) == 0) break;

			Map<String, Integer> hits = new HashMap<>();

			for (int i = 0; i < n; i++) {
				words = br.readLine().split(" ");
				hits.put(words[0].replace("*", ""), parseInt(words[1]));
			}

			int sum = 0;

			for (int i = 0; i < m; i++) {
				String lott = br.readLine();
				int max = 0;
				for (int j = 0; j <= lott.length(); j++) {
					String _lott = lott.substring(j, lott.length());
					if (hits.get(_lott) != null) {
						max = Math.max(max, hits.get(_lott));
					}
				}
				sum += max;
			}

			System.out.println(sum);
		}
	}
}

Measured memory_bytes: 38504
import bisect
def resolve():
    S = input()
    T = input()
    lenT = len(T)
    found = False
    for i in range(len(S)-lenT, -1, -1):
        for j in range(0, lenT):
            if not (S[i+j] == "?" or S[i+j] == T[j]):
                break
        else:
            S = S[:i] + T + S[i+lenT:]
            found = True
            break
    if found:
        print(S.replace("?", "a"))
    else:
        print("UNRESTORABLE")

if '__main__' == __name__:
    resolve()

Measured memory_bytes: 38256
a,b=map(int,input().split())
lists=[list("#"*100) for i in range(50)]
lists+=[list("." *100) for i in range(50)]

counter1=0
for i in range(49):
    for j in range(i,95,3):
        if counter1==a-1:
            break
           
        else:
            lists[i][j]="."
            counter1+=1
counter2=0
for i in range(51,100):
    for j in range(i-50,95,3):
        if counter2==b-1:
            break
        else:
            lists[i][j]="#"
            counter2+=1
print(100,100)
for i in range(100):
    a="".join(lists[i])
    print(a)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define mod 1000000007
#define endl "\n" 
#define p pair<int, int>
#define arrinp(i, a, start, end); for(ll i = start; i <= end; i++) cin >> a[i];
#define arrout(i, a, start, end); for(ll i = start; i <= end; i++) cout << a[i] << " ";
#define swap(a, b) {a = a + b; b = a - b; a = a - b;
#define forfront(i, start, end) for(ll i = start; i <= end; i++)
#define forback(i, start, end) for(ll i = start; i >= end; i--)
#define out(x) cout << x << " ";
#define outline(x) cout << x << endl;
#define sortvector(v) sort(v.begin(), v.end());
#define sortvectorrev(v) sort(v.rbegin(), v.rend());
#define inf INT64_MAX
int32_t main()
{
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    arrinp(i, a, 1, n);
    vector<int> suf(n + 2);
    suf[n] = a[n];
    suf[n + 1] = 0;
    for(int i = n - 1; i > 0; i--)
    {
        suf[i] = suf[i + 1] + a[i];
        suf[i] %= mod;
    }
    int ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans += (a[i]*suf[i + 1])%mod;
        ans %= mod;
    }
    outline(ans)
    return 0;
}

Measured memory_bytes: 6364
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

def main():
    a, b, c = map(int, input().split())

    if a == b + c or b == a + c or c == a + b:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Measured memory_bytes: 10356
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
const int MAX = 999999999;

int main(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if((abs(a - b) <= d && abs(c - b) <= d) || abs(a - c) <= d){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define mii map<int,int>
#define qi queue<int>
#define pqi priority_queue<int>
#define pqgi priority_queue<int,vector<int>,greater<int>>
#define si set<int>
#define vi vector<int>
#define vll vector<long long int>
#define vii vector<pair<int,int>>
#define mii map<int,int>
#define ii pair<int,int>
#define SYNC ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FRE freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define f(i,a,b) for(int i=a;i<b;i++)
#define rf(j,c,d) for(int j=c;j>d;j--)
#define mod 1000000007
#define mo 998244353
#define inf 1e18
#define INF (int)INT_MAX
#define PI 3.1415926535898
using namespace std;
const int N=1e5+5;
/*ll po(ll A,ll B)
{
	ll RES=1;
	while(B)
	{
		if(B&1)
			RES*=A;
		B>>=1;
		A*=A;
	}
	return RES;
}*/
/*void sieve(int P)
{
	prime[0]=0;prime[1]=0;
	f(i,2,P+1)
		prime[i]=1;
	f(i,2,P+1)
	{
		if(prime[i]==1)
		{
			for(int j=i*i;j<P+1;j+=i)
			{
				prime[j]=i;
			}
		}
	}
}*/
void solve()
{
	int n;
	cin>>n;
	cout<<((1000-n%1000))%1000<<'\n';
	return;
}
int main()
{
    SYNC
    //sieve();
    int t=1;
    //cin>>t;
    while(t--)
    	solve();
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll a, b;
    cin >> a >> b;
    if((a * b) % 2 == 0){
        cout << "Even" << endl;
    }else{
        cout << "Odd" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <tuple>
#include <utility>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
const int INF = 1000000000;
const int MOD = 1000000007;
int main(){
	int h,n;
	cin >> h >> n;
	vector<P> ab(n);
	for(int i = 0;i < n;i++){
		int a,b;
		cin >> a >> b;
		ab[i] = P(a,b);
	}

	vector<int> dp(h+1,INF);
	dp[0] = 0;

	for(int i = 0;i < h;i++){
		for(int j = 0;j < n;j++){
			int a = ab[j].first;
			int b = ab[j].second;
			int ni = min(i+a,h);
			dp[ni] = min(dp[ni],dp[i]+b);
		}
	}

	cout << dp[h] << endl;
}


Measured memory_bytes: 256
N = int(input())
Di = 0
Di1 = []
Di2 = []
nmDi = 0
if N >= 3 and N <= 100:
   for x in range(N):
      Di = input()
      Di1.append(Di[0])
      Di2.append(Di[-1])
   for x in range(N):
      if Di1[x] == Di2[x]:
         nmDi += 1
         if nmDi == 3:
            break
      elif Di1[x] != Di2[x] and nmDi > 0:
         nmDi = 0
   if nmDi >= 3:
      print("Yes")
   else:
      print("No")
else:
   print ("No")

Measured memory_bytes: 9140
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 29);
const ll LINF = 1e18;
const double PI = acos(-1);

template<typename T>vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...)); }
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value != 0>::type
fill_v(U& u, const V... v) { u = U(v...); }
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value == 0>::type
fill_v(U& u, const V... v) { for (auto& e : u) fill_v<T>(e, v...); }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vll A(N+1),B(N+1);
	REP(i, N + 1) {
		cin >> A[i];
	}
	REP(i, N) {
		cin >> B[i];
	}
	ll ans = 0;
	ll pre = 0;
	REP(i, N) {
		int cur = min(A[i], B[i] + pre);
		ans += cur;
		pre = min(B[i],pre + B[i] - cur);
	}
	ans += min(A[N], B[N] + pre);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1792
from __future__ import division,print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
def walk(index,tm,L,d,f):
    tm+=1
    d[index]=tm
    for i in L[index]:
        if not d[i-1]:
            tm=walk(i-1,tm,L,d,f)
    tm+=1
    f[index]=tm
    return tm
 
def main():
    num=int(sys.stdin.readline())
    L=[]
    for _ in range(num):
        L.append([int(s) for s in sys.stdin.readline().split()[2:]])
    d=[0]*num
    f=[0]*num
    tm=0
    for i in range(num):
        if not d[i]:
            tm=walk(i,tm,L,d,f)
    for i in range(num):
        print(i+1,d[i],f[i])
 
main()

Measured memory_bytes: 6856
N,X=map(int,input().split())
A=[]
total=0
ans=N-1
for i in range(N):
    A.append(int(input()))
for i in range(N):
    total+=A[i]
X=X-total
while 0<=X:
    X-=min(A)
    ans+=1
print(ans)


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

using namespace std;

int main() {
    long long a, b,m,sol=1;
    cin>>a>>b;
    m=__gcd(a,b);
   
    for(long long d=2;d*d<=m;d++){
        if(m%d==0){
            sol++;
            
            while(m%d==0){
                m/=d;
            }
           // cout<<d<<" "<<m<<" "<<d*d<<endl;
        }
    }
    if(m!=1)    sol++;    
    cout<<sol;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

long long int a, b, x;
long long int ans = 0;

int main(void) {
	scanf("%lld%lld%lld", &a, &b, &x);
	
	ans = (b / x) - (a / x);
	if (a%x == 0) { ans++; }
	printf("%lld\n", ans);
	return 0;
}

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

int main(){
  int a,b,c;
  cin>>a>>b>>c;

  if( a > b ) swap(a,b);
  if(b>c) swap(b,c);
  if(a>b) swap(a,b);
  
  cout<<a<<" "<<b<<" "<<c<<endl;
 
  
  return 0;
}



   
  



Measured memory_bytes: 3116
#!/usr/bin/env python3
from collections import defaultdict

(n, ), *p = [[*map(int, i.split())] for i in open(0)]
d = defaultdict(int)
for i in range(n):
    for j in range(n):
        if i != j:
            d[(p[i][0] - p[j][0], p[i][1] - p[j][1])] += 1
print(n*(n<2) or n - max(d.values()))


Measured memory_bytes: 9628
#include <algorithm>
#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;
typedef pair<int, int> P;

int main()
{
    int h, w;
    cin >> h >> w;
    string s[2005];
    for(int i = 0; i < h; i++) cin >> s[i];
    vector<int> v[2005];
    for(int i = 1; i < h; i++){
        for(int j = 1; j < w; j++){
            int c = 0;
            for(int x = i - 1; x <= i; x++){
                for(int y = j - 1; y <= j; y++){
                    if(s[x][y] == '.') c++;
                }
            }
            if(c % 2) v[j].push_back(i);
        }
    }
    int ans = 0;
    for(int i = 0; i < h; i++){
        priority_queue<P> que;
        set<int> st;
        st.insert(0);
        st.insert(w);
        int d[2005]{0};
        d[0] = w;
        que.push(P(w, 0));
        vector<int> t[2005];
        for(int j = 1; j < w; j++){
            auto itr = upper_bound(v[j].begin(), v[j].end(), i);
            if(itr != v[j].end()) t[*itr].push_back(j);
        }
        for(int k = i + 1; k <= h; k++){
            ans = max(ans, que.top().first * (k - i));
            for(int j : t[k]){
                auto itr = st.upper_bound(j);
                itr--;
                int l = *itr;
                if(j != l){
                    st.insert(j);
                    d[j] = d[l] - (j - l);
                    d[l] = j - l;
                    que.push(P(d[j], j));
                    que.push(P(d[l], l));
                }
            }
            while(que.size()){
                P p = que.top();
                if(d[p.second] == p.first) break;
                que.pop();
            }
        }
    }
    cout << ans << endl;
}


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

int main(){
    int64_t N, M;
    cin >> N >> M;
    vector<int64_t> A(N), S(N+1);
    for(int i=0; i<N; i++) cin >> A[i];
    sort(A.begin(), A.end());
    for(int i=0; i<N; i++) S[i+1] = S[i] + A[i];

    // ok : ok以上がM回以上
    int64_t ok = 0, ng = 1e6;
    while(ng-ok>1){
        int64_t mid = (ok+ng)/2;
        int64_t num = 0;
        for(int i=0; i<N; i++){
            num += A.end() - lower_bound(A.begin(), A.end(), mid - A[i]);
        }
        (num >= M ? ok : ng) = mid;
    }
    int64_t ans = 0, num = 0;
    for(int i=0; i<N; i++){
        int pt = lower_bound(A.begin(), A.end(), ng - A[i]) - A.begin();
        num += N-pt;
        ans += S[N] - S[pt] + (N-pt)*A[i];
    }
    ans += ok*(M-num);
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, M: int, a: "List[int]"):
    dp = [0]*(N+1)
    dp[0] = 1
    B = set(a)
    for i in range(1, N+1):
        if i in B:
            continue
        if i > 1:
            dp[i] = (dp[i-1] + dp[i-2]) % MOD
        else:
            dp[i] = dp[i-1] % MOD
    print(dp[N])
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, a)


if __name__ == '__main__':
    main()


Measured memory_bytes: 13976
#include <bits/stdc++.h>
          using namespace std;
          #define tani_nachi_ke  ios_base::sync_with_stdio(false); cin.tie(NULL);
          #define M_PI 3.14159265358979323846
          #define data data_
          #define ff first
          #define ss second
          #define pb push_back
          #define ll long long
          #define ld long double

          int main()
          {
               tani_nachi_ke  

                string s;
                cin >> s;
                int n = s.size();
                while(n--)
                    cout <<'x';
                cout << endl;




         
               return 0;
          }

Measured memory_bytes: 256
if __name__ == '__main__':
    # ??????????????\???
    weeks = int(input())
    principal = 100000

    # ??????????¨????
    for i in range(weeks):
        interest = principal * 0.05
        principal += interest
        fraction = principal % 1000
        if fraction != 0:
            principal += (1000 - fraction)

    # ???????????????
    print(int(principal))

Measured memory_bytes: 7524
#include <stdio.h>
#define MAX 100000
	
int main() {
	char s[MAX];
	scanf("%s", s);
	int red = 0, blue = 0;
	for(int i = 0; i < MAX; i++){
		if(s[i] == '0')
			red++;
		else
			if(s[i] == '1')
				blue++;
			else
				break;
	}
	if(red <= blue)
		printf("%d\n", 2*red);	
	else
		printf("%d\n", 2*blue);
		

	return 0;
}

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

//a^n (mod m)
const ll mod = 1e9+7;
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//mod mでの a の逆元を求める
ll modinv(ll a) {
    ll b = mod, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= mod; 
    if (u < 0) u += mod;
    return u;
}

ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}

vector<pair<ll, ll>> prime_factorize(ll n) {
    vector<pair<ll, ll> > res;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

ll cnt[1000100];
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll n;
    cin>>n;
    ll a[n];
    ll l = 1;
    vector<vector<pair<ll,ll>>> v;
    for(int i=0;i<n;i++){
        cin>>a[i];
        v.push_back(prime_factorize(a[i]));
    }
    for(int i=0;i<v.size();i++){
        for(int j=0;j<v[i].size();j++){
            cnt[v[i][j].first] = max(cnt[v[i][j].first], v[i][j].second);
        }
    }
    for(int i=2;i<=1000000;i++){
        if(cnt[i]){
            l *= modpow(i,cnt[i]);
            l %= mod;
        }
    }
    ll ans = 0;
    for(int i=0;i<n;i++){
        ans += (l*modinv(a[i]))%mod;
        ans %= mod;
    }
    ans %= mod;
    cout << ans << endl;

    
}

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

//宣言
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

//数値
#define MOD 1000000007
#define INF (1<<20)
const double EPS = 1e-10;
const double PI = acos(-1.0);

//操作
#define FOR(i,a,b) for(int i=a;i<b;++i)
#define REP(i,n) FOR(i,0,n)
#define REPB(i,n) for(int i=n;i>=0;--i)
#define SORT(A) sort(A,A+sizeof(A)/sizeof(A[0]))
#define VSORT(A) sort(A.begin(),A.end())
#define EXIST(s,e) (s.find(e)!=s.end())
#define PB push_back
#define MP make_pair
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);

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


int main() {
	string s;
	cin >> s;
	int t = 100001;
		for (int i = 0;i < s.length()-1;i++) {
			if (s[i] + s[i + 1] == '0' + '1') t = min(t,max(i + 1,(int) s.length() - i- 1));
		}
	    if(t) cout << min(t,(int)s.length()) << endl;
        
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
template<typename T> void read(T &num){
	char c=getchar();T f=1;num=0;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	num*=f;
}
template<typename T> void qwq(T x){
	if(x>9)qwq(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	qwq(x);putchar('\n');
}

int main(){
	int h1,m1,h2,m2,k;read(h1);read(m1);read(h2);read(m2);read(k);
	write((h2-h1)*60+(m2-m1)-k);
	return 0;
}

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

using namespace std;

int main()
{
    long long mini=1000000000000000;
    vector <long long> divi;
    long long x;
    cin>>x;
    long long y=sqrt(x)+1;
    for (long long i=1;i<=y;i++){
        if (x%i==0) {
            mini=min((i+(x/i))-2,mini);
        }
    }
    cout<<mini;
    

    return 0;
}

Measured memory_bytes: 256
using System;

class WhileSample
{
    static void Main()
    {

    int H;
    int W;
        string[] input = Console.ReadLine().Split(' ');

        H = int.Parse(input[0]);
        W = int.Parse(input[1]);

        while (H != 0 && W != 0)
        {


            for (int x = 1; x <= H; x++)
            {
                for (int y = 1; y <= W; y++)
                {
                    // xy の値を、幅をそろえて表示
                    Console.Write("#");
                }
                Console.Write("\n");
            }
            Console.Write("\n");
            input = Console.ReadLine().Split(' ');

            H = int.Parse(input[0]);
            W = int.Parse(input[1]);
        }
    }
}


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

int main() {

  int K;
  cin >> K;

  vector<long long> a;
  for (int i = 1; i < 10; i++){
    a.push_back(i);
  }

  bool flg = true;
  while (flg) {
    if (K <= a.size()) {
      cout << a[K - 1] << endl;
      return 0;
    }
    K -= a.size();
    vector<long long> old;
    swap(old, a);
    for (int i = 0; i < old.size(); i++) {
      for (int j = -1; j < 2; j++) {
        int d = old[i] % 10 + j;
        if (d < 0 || 9 < d) {
          continue;
        }
        long long r = old[i] * 10 + d;
        a.push_back(r);
      }
    }
  }

  return 0;

}

Measured memory_bytes: 1712
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    for j in range(2, int(i**.5)+1):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)

Measured memory_bytes: 4972
# 頂点sから到達する頂点の集合
def dfs(edge, s):
    use = {s}
    q = [s]
    while q:
        v = q.pop()
        for w in edge[v]:
            if w in use:continue
            use.add(w)
            q.append(w)
    return use

# ベルマンフォード法
def bellman_ford(v, s, t, e):
    INF = 10**18
    # コストをINFで初期化
    d = [INF] * v
    # 開始頂点は0
    d[s] = 0
    # 負の閉路が無ければ更新はV-1回までで終わる
    for _ in range(v):
        f = False
        for a, b, c in e:
            if d[a]==INF:continue
            # aまでのコスト+辺abのコストがbまでのコストより小さければ更新
            cost = d[a] + c
            if cost < d[b]:
                d[b] = cost
                f = True
        # 更新が無ければbreak
        if not f:break
    else:
        # V回目まで更新があったら負の閉路がある
        return -1
    return max(-d[t], 0)

def main():
    import sys
    input = sys.stdin.readline
    n, m, p = map(int, input().split())
    edge = [[] for _ in range(n)]
    edge_rev = [[] for _ in range(n)]
    e = []
    for _ in range(m):
        a, b, c = map(int, input().split())
        edge[a-1].append(b-1)
        # 頂点Nからdfsするため辺の向きを逆にする
        edge_rev[b-1].append(a-1)
        e.append((a-1, b-1, p-c))
    """
    # 頂点1と頂点Nのどちらからも到達できる頂点の集合
    use = dfs(edge, 0) & dfs(edge_rev, n-1)
    # fromとtoがどちらもuseに含まれる辺のみ使う
    # そうすることで負の閉路を検出した場合答えは必ず-1になる
    """
    # ↑って思ってたけど頂点Nから到達できるか見るだけでいいらしいよ(えー)
    use = dfs(edge_rev, n-1)
    e = [(a, b, c) for a, b, c in e if a in use and b in use]
    print(bellman_ford(n, 0, n-1, e))   
if __name__ == '__main__':
    main()

Measured memory_bytes: 5276
inn = [int(x) for x in input().split()]

xx = inn[1] // 10000
ans = [-1, -1, -1]
if xx <= inn[1]:
    for x in range(xx+1):
        rem = inn[1] - 10000*x
        yy = rem // 5000
        for y in range(yy+1):
            z = (rem - 5000*y) // 1000
            if x+y+z == inn[0]:
                ans = [x, y, z]
                break

print(' '.join([str(x) for x in ans]))


Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
#define fios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
typedef long long ll;
#ifdef LOCAL
mt19937 rng(unsigned(70));
#else
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif
#define rand rng


int main() {
	// fios;
	string s, t;
	cin >> s >> t;
	for(int i = 0; i < (int)s.length(); i++) {
		if(s[i] != t[i]) {
			puts("No");
			return 0;
		}
	}
	cout << "Yes\n";

}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define ll long long
using namespace std;
  
 
int main() 
{
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll ans=0;
    if(k<a)
    {
        ans+=k;
        k=0;
    }
    else if(k>=a)
    {
        ans+=a;
        k-=a;
    }
    if(k>0)
    {
        if(k<b)
        {
            k=0;
        }
        else
        {
            k=k-b;
        }
        
    }
    if(k>0)
    {
        if(k<c)
        {
            ans-=k;
        }
        else
        {
            ans-=c;
        }
        
    }
    cout<<ans<<endl;
        
        
    return 0;
}


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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;

#define deb(x) cerr<<#x<<":"<<x<<"\n";
#define dvi(x) for(ll i=0;i<x.size();i++)cerr<<#x<<"["<<i<<"]:"<<x[i]<<" ";
#define iter(v) for(auto it:v)
#define wt ll t;cin>>t;while(t--)
#define rl(x) ll x;cin>>x;
#define rvi(x,n) vi x(n);for(ll i=0;i<n;i++) cin>>x[i];
#define rs(x) string x;cin>>x;
#define w(x) cout<<x<<endl;
#define wvi(x) for(ll i=0;i<x.size();i++) cout<<x[i]<<" ";cout<<endl;
#define ws(x) cout<<x<<endl;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ppb pop_back
#define pll pair<ll, ll>
#define fo(i,n) for(ll i=0;i<n;i++)
#define forr(i,a,b) for(ll i=a;i<b;i++)
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
const ll N = 1e9 + 7;

map<long long, long long> factorize(long long n) {	//returns map containing factor and multiplicity, Eg: 60 = {{2,2},{3,1},{5,1}}
	map<long long, long long> ans;
	for (long long i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ans[i]++;
			n /= i;
		}
	}
	if (n > 1) {
		ans[n]++;
		n = 1;
	}
	return ans;
}

void FAST() {	//FAST Input Output, DONT use both scnaf,prllf / cin,cout , Use any ONE system
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

ll powM(ll x, ll y, ll m) {	//returns (a^b)%m ( ^ is exponent )
	ll ans = 1, r = 1;
	x %= m;
	while (r > 0 && r <= y)
	{
		if (r & y)
		{
			ans *= x;
			ans %= m;
		}
		r <<= 1;
		x *= x;
		x %= m;
	}
	return ans;
} 

int main()
{
	FAST();
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
    //    freopen("output.txt", "w", stdout);
    #endif
//	wt{
		int n;
		cin>>n;
		vi a(n);
		fo(i,n) cin>>a[i];
		int l=0,r=0;
		sort(all(a));
		ll count=0;
		for(int i=0;i<n-2;i++)
		{
			l=i+1,r=i+2;
			while(l<n-1)
			{
				r=l+1;
				if(a[l]!=a[i])
				while(a[l]+a[i]>a[r] && r<n)
				{
					if(a[r]!=a[l])count++;
					r++;
					
				}
				l++;
			}
		}
		cout<<count;
//	}
}

Measured memory_bytes: 3676
def in_list(l, l_t, a):
    l[a] = l_t


ans_list = [[] for _ in range(60)]
p = 0

l = int(input())
bin_str = format(l, '020b')
for i in range(20):
    c = 0
    if c == 0 and str(bin_str)[i] == '1':
        c = 1
        n = 20-i
        k = i
        break;
for j in range(1, n):
    in_list(ans_list, [j, j+1, 0], p)
    p += 1
    in_list(ans_list, [j, j+1, 2**(n-1-j)], p)
    p += 1
c = 2**(n-1)

for m in range(k+1, 20):
    if str(bin_str[m]) == '1':
        in_list(ans_list, [1, n+m-20+1, c], p)
        p += 1
        c += 2 ** (19-m)

print(n, p)
for q in range(p):
    print(ans_list[q][0], ans_list[q][1], ans_list[q][2])

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;

ll x,y,i,j,fact[1000010],mod=7+1e9;

ll expBin( ll A , ll B ){
    if( !B ) return 1LL;
    ll myAns = expBin( A , B/2 );
    myAns = (myAns*myAns)%mod;
    if( B&1 ) myAns = (myAns*A)%mod;
    return myAns;
}

int main()
{

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

    cin >> x >> y;

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

    i = (x+x-y)/3;
    j = x-i-i;

    if( i<0 || j<0 ){
        cout << "0";
        return 0;
    }

    fact[ 0 ] = 1;
    for( ll k=1; k<=i+j; k++ ) fact[ k ] = ( fact[k-1]*k )%mod;

    cout << (((fact[ i+j ]*expBin( fact[ i ] , mod-2 ) )%mod)*expBin( fact[ j ] , mod-2 ))%mod;

    return 0;
}


Measured memory_bytes: 6400
# ABC099D - Good Grid
import sys

readline = sys.stdin.buffer.readline

from collections import Counter
from itertools import product


def main():
    N, C = map(int, readline().split())
    D = [0] + list([0] + list(map(int, readline().split())) for _ in range(C))
    grid = tuple(tuple(map(int, readline().split())) for _ in range(N))
    cost = [Counter() for _ in range(3)]
    for i, g in enumerate(grid):
        for j in range(3):
            cost[j].update(g[(j - i) % 3 :: 3])
    dist = [[] for _ in range(3)]
    for i, tgt in product(range(3), range(1, C + 1)):
        cur = sum(D[src][tgt] * cnt for src, cnt in cost[i].items())
        dist[i].append(cur)
    ans = 1 << 60
    for i, j in product(range(C), repeat=2):
        if i == j:
            continue
        cur = dist[0][i] + dist[1][j]
        cur += min(x for k, x in enumerate(dist[2]) if k not in (i, j))
        ans = min(ans, cur)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 5356
// ------------------------------------
// Date:2018/ 2/24
// Problem:AGC 004 DivideACuboid a.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl

using ll = long long;

#define MOD 1000000007

int main()
{
  int n;
  vector<ll> data(3);
  REP(i,3) {
    cin >> data[i];
    if (data[i]%2 == 0) {
      cout << "0" << endl;
      return 0;
    }
  }
  sort(ALL(data));
  cout << data[0]*data[1] << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H, W;
	cin >> H >> W;
	int res = 0;
	string S;

	int mx1 = -100000;
	int mn1 = 100000;
	int mx2 = -100000;
	int mn2 = 100000;
	for (int i = 0; i < H; i++) {
		cin >> S;
		for (int j = 0; j < W; j++) {
			if (S[j] == 'B') {
				mx1 = max(mx1, i + j);
				mn1 = min(mn1, i + j);
				mx2 = max(mx2, i - j);
				mn2 = min(mn2, i - j);
			}
		}
	}

	res = max(res, mx1 - mn1);
	res = max(res, mx2 - mn2);

	cout << res << endl;
}


Measured memory_bytes: 3260
_ = input()
numbers = map(int, input().split())
result, n_max, h_cur = 0, 0, next(numbers)
for hi in numbers:
    if h_cur >= hi:
        n_max += 1
    else:
        result = max(result, n_max)
        n_max = 0
    h_cur = hi
else:
    result = max(result, n_max)
print(result)


Measured memory_bytes: 11136
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
typedef long long LL;
const LL N = 100005;
 
LL ec = 0,to[N << 1],nxt[N << 1],hed[N],deg[N];
LL cnt = 0;
void add_edge(LL f,LL t){
	++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec;
	deg[t] ++;
}
 
LL vis[N] = {0},val[N],dis[N];
LL eu[N],ev[N],n;
string s;
 
void solve(){
	queue <LL> q;
	for(LL i = 1;i <= n;i ++) if(deg[i] == 1 && s[i] == 'B') q.push(i);
	while(!q.empty()){
		LL u = q.front(); q.pop();
		vis[u] = 1;
		for(LL i = hed[u];i;i = nxt[i]){
			LL v = to[i];
			if(!vis[v]){
				deg[v] --;
				if(deg[v] == 1 && s[v] == 'B') q.push(v);
			}
		}
	}
	memset(deg,0,sizeof(deg));
	memset(hed,0,sizeof(hed)); ec = 0;
	for(LL i = 1;i < n;i ++){
		if(vis[eu[i]] || vis[ev[i]]) continue;
		add_edge(eu[i],ev[i]);
		add_edge(ev[i],eu[i]);
	}
	for(LL i = 1;i <= n;i ++){
		val[i] = 0;
		if(vis[i]) continue;
		if((s[i] == 'B' && deg[i] % 2 == 1) || (s[i] == 'W' && deg[i] % 2 == 0)){
			val[i] = 2;
			cnt ++;
		}
	}
}
 
LL td = 0;
LL d[N];
void dfs(LL u,LL f){
	d[u] = val[u];
	for(LL i = hed[u];i;i = nxt[i]){
		LL v = to[i];
		if(v == f) continue;
		dfs(v,u);
		td = max(td,d[u] + d[v]);
		d[u] = max(d[u],d[v] + val[u]);
	}
}
 
int main(){
	ios::sync_with_stdio(false);
	cin >> n;
	for(LL i = 1;i < n;i ++){
		cin >> eu[i] >> ev[i];
		add_edge(eu[i],ev[i]);
		add_edge(ev[i],eu[i]);
	}
	cin >> s; s = ' ' + s;
	solve();
	LL trt = 1,ans;
	for(LL i = 1;i <= n;i ++) if(!vis[i]) trt = i;
	dfs(trt,0);
	ans = ec + cnt - td;
	cout << ans << '\n';
	return 0;
} 

Measured memory_bytes: 14184
#include <iostream>
#include <utility>
#include <algorithm>
#define inf 1000000007

using namespace std;

int N, L, Q;
int x[100005];
int Next[17][100005];

int main(void)
{
	cin >> N;
	for(int i = 0; i < N; i++) cin >> x[i];
	x[N] = x[N-1]+1;
	cin >> L;
	
	int p;
	for(int i = 0; i <= N; i++){
		Next[0][i] = upper_bound(x, x+N+1, x[i] + L) - x - 1;
	}
	for(int i = 1; i < 17; i++){
		for(int j = 0; j <= N; j++){
			Next[i][j] = Next[i-1][Next[i-1][j]];
		}
	}
	
	cin >> Q;
	int a, b;
	for(int q = 0; q < Q; q++){
		cin >> a >> b;
		a--, b--;
		if(a > b){
			int t = a;
			a = b, b = t;
		}
		
		int cur = a, ans = 0;
		for(int i = 16; i >= 0; i--){
			if(Next[i][cur] <= b){
				cur = Next[i][cur];
				ans += 1<<i;
			}
		}
		if(cur < b) ans++;
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 7808
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Prac
{
    class Program
    {
        static void Main(string[] args)
        {
           
            var temp = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
            var r = temp[0];
            var c = temp[1];
            temp = new List<int>();
            var sheat = new int[r + 1][];
            for(var i = 0;i<r;i++)
            {
                temp =  Console.ReadLine().Split(' ').Select(int.Parse).ToList();
                temp.Add(temp.Sum());
                sheat[i] = temp.ToArray();
            }
            sheat[r] = Enumerable.Repeat(0, c + 1).ToArray();
            var sum = 0;
            for (var i = 0; i < c; i++)
            {
                for (var j = 0; j < r; j++)
                {
                    sum += sheat[j][i];
                }
                sheat[r][i] = sum;
                sum = 0;
            }
            sheat[r][c] = sheat[r].Sum();
            var firstR = true;
            foreach(var s in sheat)
            {
                foreach (var ss in s)
                {
                    if (!firstR)
                        Console.Write(" ");
                    else
                        firstR = false;
                    Console.Write(ss);
                }
                Console.WriteLine();
                firstR = true;
            }

        }
    
    }
}

Measured memory_bytes: 20620
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s,t;
    int c=0;
    cin>>s>>t;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]==t[i])
        {
            c++;
        }
    }
    cout<<c<<endl;
    return 0;
}



Measured memory_bytes: 256