akhauriyash/Code-Regression huggingface dataset:
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        #print(key)
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    #print(dp)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC142_E()

"""

"""

Measured memory_bytes: 75504
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	int n,i;
	cin>>n>>i;
	printf("%d\n",n-i+1);
}


Measured memory_bytes: 256
N = gets.to_i
hs = gets.split.map(&:to_i)

dp = Array.new(N)
dp[0] = 0
dp[1] = (hs[0] - hs[1]).abs

(2...N).each do |i|
  dp[i] =  [dp[i - 1] + (hs[i] - hs[i - 1]).abs, dp[i - 2] + (hs[i] - hs[i - 2]).abs].min
end

puts dp.last


Measured memory_bytes: 11396
a = input().split(" ")

tmp_out=[[""] for i in range(int(a[0])+2)]

for j in range(int(a[1])+2):
    tmp_out[0]=["".join(tmp_out[0]+["#"])]

for i in range(1, int(a[0])+1):
    tmp=input().split(" ")
    tmp_out[i]=["".join(["#"]+tmp+["#"])]

tmp_out[int(a[0])+1]=tmp_out[0]

for i in range(int(a[0])+2):
    print("".join(tmp_out[i]))

Measured memory_bytes: 3064
#include<stdio.h>
#include<stdlib.h>
#define min(x,y) x<y?x:y
int main(void){
	int n,m,i,j,c[10001],dp[50001];
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++) dp[i]=1<<20;
	for(i=1;i<=m;i++) scanf("%d",&c[i]);
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			if(j-c[i]>=0) dp[j]=min(dp[j],dp[j-c[i]]+1);
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}

Measured memory_bytes: 800
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
typedef pair<double,double> pdd;
const double EPS=1e-9;
#define debug(c) (cerr<<#c<<": "<<c<<"\n")
#define fi first
#define se second
#define mod 1000000007
#define pi acos(-1)
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
ll a[200005];
int main()
{
	ios;
	ll n,i,sum=0,d;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=2;i<=n;i++)
	{
		d=max(0ll,a[i-1]-a[i]);
		a[i]+=d;
		sum+=d;
	}
	cout<<sum<<endl;
}


Measured memory_bytes: 5224
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define nn '\n'
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg){cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg){cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) cout << n << '\n';
typedef vector<int> VI;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

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

    int n; cin >> n;
    VI v(n); REP(i,n) cin >> v[i]; SORT(v);
    double ans = (v[0]+v[1])/2.0;
    FOR(i,2,n) ans = (ans+v[i])/2.0;
    out(ans);

    return 0;
}

Measured memory_bytes: 256
package main
import "fmt"
import "math"

func main() {
	var N, a, b int
	fmt.Scan(&N, &a, &b)
	res := 0
	for i := 1; i <= N; i++ {
		tmp := i%10
		for j := 1; j <= 5; j++ {
			tmp += (i/int(math.Pow(10, float64(j))))%10
			
		}
		
		if tmp >= a && tmp <= b {
			res += i
		}
	}
	fmt.Println(res)
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  if((N%10==(N%100-N%10)/10 && (N%1000-N%100)/100==N%10)|| ((N-N%100)/1000==(N%1000-N%100)/100 &&(N%1000-N%100)/100==(N%100-N%10)/10)) {
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3648
#include <stdio.h>
using namespace std;
int main(void){
    double p;
    int N;
    scanf("%d",&N);
    p=N;
    if(N%2==0)//if even
    {
        printf("0.5");
    }
    else//if odd
    {
        printf("%f",((p-1)/2+1)/p);
    }
    

   return 0;
}

Measured memory_bytes: 128
// 標準入力
var fs = require('fs'),
length = fs.fstatSync(process.stdin.fd).size,
buffer = new Buffer(length),
bytesRead = fs.readSync(process.stdin.fd, buffer, 0, length, 0),
input = buffer.toString('utf8', 0, bytesRead).split('\n');
main();
 
function main(){
  var read = 0;
  var resultCase = 1;
  while(true){
    var maxWeight = +input[read++];
    if(!maxWeight){
      break;
    }
     
    var treasures = +input[read++];
    var pdp = new Int16Array(maxWeight + 1);
    for(var i = treasures; i--;){
      var c = input[read++].split(",");
      var tv = +c[0];
      var tw = +c[1];
 
      var dp = new Int16Array(maxWeight + 1);
      for(var w = 1; w <= maxWeight; w++){
        var pdpw = pdp[w];
        dp[w] = (w-tw < 0) ? pdpw : tmax(pdp[w-tw] + tv, pdpw);
      }
      pdp = dp;
    }
 
    var resultWeight = 1001;
    var resultCost = 0;
    for(var i = 0; i <= maxWeight; i++){
      var pdpi = pdp[i];
      if(pdpi > resultCost){
        resultCost = pdpi;
        resultWeight = i;
      }
    }
     
    console.log("Case " + resultCase++ + ":\n" + resultCost + "\n" + resultWeight);
  }
}

function tmax(a, b){
  return a>b?a:b;
}

function max(a, b) {
  var t = a - b;
  return a - (t & (t >> 31));
}

Measured memory_bytes: 12392
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		int r = scanner.nextInt();
		int s = scanner.nextInt();
		int p = scanner.nextInt();
		String t = scanner.next();
		scanner.close();
		int score = 0;
		boolean[] win = new boolean[n];
		for (int i = 0; i < n; i++) {
			if (i >= k && win[i - k] && t.charAt(i) == t.charAt(i - k))
				continue;
			else {
				win[i] = true;
			}
			switch (t.charAt(i)) {
			case 'r':
				score += p;
				break;
			case 's':
				score += r;
				break;
			case 'p':
				score += s;
				break;
			}

		}
		System.out.println(score);
	}

}


Measured memory_bytes: 26356
#include <bits/stdc++.h>
using namespace std;
int main(){
  int k;
  string s;
  scanf("%d ", &k);
  cin>>s;
  int len=s.length();
  if(len<=k)
    cout<<s;
  else{
    for(int i=0; i<k; i++)
      cout<<s[i];
    cout<<"...";
  }
  return 0;
}

Measured memory_bytes: 3692
use proconio::{input, fastout};
use proconio::marker::{Chars};
use proconio::marker::Usize1;
use std::cmp::*;

macro_rules! debug {
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

#[fastout]
fn main() {
    input!{
        a: usize,
        b: usize,
        c: usize,
        d: usize,
    }

    println!("{}", max(0, min(b,d) as i64 - max(a,c) as i64));

}


Measured memory_bytes: 2144
import java.util.Scanner;

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

		String s = sc.nextLine();
		if (s.length() < 4) {
			System.out.println("No");
			sc.close();
			return;
		}

		System.out.println(s.substring(0, 4).equals("YAKI") ? "Yes" : "No");

		sc.close();
	}
}



Measured memory_bytes: 23892
n,k,*L=map(int,open(0).read().split())
X=[];Y=[]
for x,y in sorted((x,y) for x,y in zip(*[iter(L)]*2)):
	X.append(x)
	Y.append(y)
ans=float("inf")
for i in range(n-k+1):
	for j in range(i+k-1,n):
		w=X[j]-X[i]
		l=sorted(Y[i:j+1])
		h=min(My-my for my,My in zip(l,l[k-1:]))
		ans=min(ans,w*h)
print(ans)



Measured memory_bytes: 42348
import * as fs from "fs";

const input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
//const n = +input[0];
//const a = [];
//for(let i=0;i<n;i++){
//	a.push(input[i+1].split(" ").map((x:string):number=>+x));
//}

//const [n, m] = input[0].split(" ").map((x: string): number => +x);
//const a = input[1].split(" ").map((x: string): number => +x);

const n : number = +input[0];
const [s, t] : string[] = input[1].split(' ');
const ss : string[] = s.split('');
const tt : string[] = t.split('');

let ans : string = '';

for(let i = 0; i < n; i++){
    ans+=ss[i];
    ans+=tt[i];
}
console.log(ans);

Measured memory_bytes: 7372
import sys, math
from functools import lru_cache
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    A = list(mi())
    print(len(set(A))-1+len(set(A))%2)



if __name__ == '__main__':
    main()

Measured memory_bytes: 21456
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
using namespace std;

int N, M, X[5010], Y[5010];

int compress(int *p, vector<int> &s) {
  REP(i, 0, N) s.push_back(p[i]);
  sort(s.begin(), s.end());
  s.erase(unique(s.begin(), s.end()), s.end());
  REP(i, 0, N) p[i] = find(s.begin(), s.end(), p[i]) - s.begin();
  return s.size();
}

int main(void) {
  cin >> N >> M;
  REP(i, 0, N) cin >> X[i] >> Y[i];
  vector<int> sx, sy;
  int w = compress(X, sx);
  int h = compress(Y, sy);

  int **sum = (int**) malloc((h + 1) * sizeof(int*));
  REP(i, 0, h + 1) sum[i] = (int*) malloc((w + 1) * sizeof(int));
  REP(i, 0, h + 1) REP(j, 0, w + 1) sum[i][j] = 0;
  REP(i, 0, N) sum[Y[i] + 1][X[i] + 1]++;
  REP(i, 0, h) REP(j, 0, w + 1) sum[i + 1][j] += sum[i][j];
  REP(i, 0, h + 1) REP(j, 0, w) sum[i][j + 1] += sum[i][j];

  REP(i, 0, M) {
    int lx, rx, ly, ry;
    cin >> lx >> ly >> rx >> ry;
    int vlx = lower_bound(sx.begin(), sx.end(), lx) - sx.begin();
    int vly = lower_bound(sy.begin(), sy.end(), ly) - sy.begin();
    int vrx = upper_bound(sx.begin(), sx.end(), rx) - sx.begin();
    int vry = upper_bound(sy.begin(), sy.end(), ry) - sy.begin();
    cout << (sum[vry][vrx] - sum[vry][vlx] - sum[vly][vrx] + sum[vly][vlx]) << endl;;
  }

  return 0;
}

Measured memory_bytes: 101040
#include <iostream>

using namespace std;

int main(){
    string s;
    cin >> s;
    if(s == "SUN"){
        cout << 7 << endl;
    }
    else if(s == "MON"){
        cout << 6 << endl;
    }
    else if(s == "TUE"){
        cout << 5 << endl;
    }
    else if(s == "WED"){
        cout << 4 << endl;
    }
    else if(s == "THU"){
        cout << 3 << endl;
    }
    else if(s == "FRI"){
        cout << 2 << endl;
    }
    else if(s == "SAT"){
        cout << 1 << endl;
    }
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
s=1
if 0 in A:
  print(0)
else:
  for i in range(N):
    s*=A[i]
    if s>10**18:
      print(-1)
      break
  if s<=10**18:
    print(s)

Measured memory_bytes: 21576
N = int(input())
# cnt[i][j] := 先頭がi, 末尾がjで始まるような数
cnt = [[0] * 10 for i in range(10)]
for n in range(1, N + 1):
    cnt[int(str(n)[0])][int(str(n)[-1])] += 1

ans = 0
for i in range(10):
    for j in range(10):
        ans += cnt[i][j] * cnt[j][i]

print(ans)

Measured memory_bytes: 9132
#include<iostream>
#include<string>
using namespace std;
#define MOD (1000000007)
typedef long long ll;
int main(){
  string s;
  ll tmp0,tmp1;
  cin >> s;
  tmp0=1;
  tmp1=2;
  for(int i=1;i<s.length();i++){
    if(s[i]=='1'){
      tmp0=tmp0*3+tmp1;
      tmp1*=2;
    }else{
      tmp0*=3;
    }
    tmp0%=MOD;
    tmp1%=MOD;
  }
  cout << (tmp0+tmp1)%MOD<<endl;
}


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

#define LL long long int 
#define mp make_pair
#define pb push_back
#define pii pair<int, int> 
#define TAM (int)1e5 + 10
using namespace std;

int n, m;
vector<LL> items;
LL ans;

LL pow(int a, int b){
    cout << a << "  " << b << endl;
    LL res = 1;
    for(int i=0; i<b; i++)
        res*=a;
    return res;
}


int main () {
    cin >> n >> m;
    items.resize(n);
    ans = 0;
    
    for(int i=0; i<n; i++) cin >> items[i], ans+=items[i];

    priority_queue<pair<LL, pair<int, LL> > > fila;
    
    for(int i=0; i<n; i++)
        fila.push(mp(items[i] - (items[i]/2), mp(1, items[i])));
    
    for(int i=0; i<m and !fila.empty(); i++){
        pair<LL, pair<int, LL> > atual = fila.top();
        fila.pop();
        ans-= atual.first;
        int number = atual.second.first;
        LL val = atual.second.second;
        if(number!=30)
            fila.push(mp(val/(1<<number) - val/(1<<(number+1)), mp(number+1, val)));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4980
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>

using namespace std;

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

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		new Main().run();
	}

	private void run() {
		Scanner scanner = new Scanner(System.in);
		loop: while (true) {
			w = scanner.nextInt();
			h = scanner.nextInt();
			if ((w | h) == 0)
				break;
			count = 0;
			visited = new boolean[h][w];
			sx = -1;
			sy = -1;
			boolean isworstpatt = (w == 7 && h == 7);
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					int now = scanner.nextInt();
					if (now == 0) {
						count++;
						if (sx == -1) {
							sy = i;
							sx = j;
						}
					} else {
						isworstpatt = false;
						visited[i][j] = true;
					}
				}
			}
			if (isworstpatt) {
				System.out.println("No");
				continue;
			}
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (visited[i][j])
						continue;
					int count = 0;
					for (int k = 0; k < 4; k++) {
						int x = j + vx[k];
						int y = i + vy[k];
						if (!isOK(x, y))
							continue;
						if (!visited[y][x])
							count++;
					}
					if (count < 2) {
						System.out.println("No");
						continue loop;
					}
				}
			}

			System.out.println(dfs(sx, sy, 0) ? "Yes" : "No");
		}

	}

	private boolean dfs(int x, int y, int deep) {
		if (count - deep < Math.abs(x - sx) + Math.abs(y - sy))
			return false;
		
		for (int i = 0; i < 4; i++) {
			int nx = x + vx[i];
			int ny = y + vy[i];
			if (!isOK(nx, ny))
				continue;
			if (ny == sy && nx == sx && deep + 1 == count)
				return true;
			if (visited[ny][nx])
				continue;
			boolean res = check(nx, ny);
			if (!res)
				continue;
			visited[ny][nx] = true;
			if (dfs(nx, ny, deep + 1))
				return true;
			visited[ny][nx] = false;
		}
		return false;

	}

	private boolean check(int x, int y) {
		for (int i = 0; i < vx.length; i++) {
			int nx = x + vx[i];
			int ny = y + vy[i];
			if (!isOK(nx, ny))
				continue;
			if (nx == sx && ny == sy)
				continue;
			if (visited[ny][nx])
				continue;
			int count = 0;
			for (int j = 0; j < 4; j++) {
				int nnx = nx + vx[j];
				int nny = ny + vy[j];
				if (!isOK(nnx, nny))
					continue;
				if (visited[nny][nnx])
					continue;
				count++;
			}
			if (count <= 1)
				return false;
		}
		return true;
	}

	private boolean isOK(int x, int y) {
		if (0 <= x && x < w && 0 <= y && y < h)
			return true;
		return false;
	}

	boolean[][] visited;
	boolean ans;
	int count, w, h, sx, sy;
	int[] vx = { 0, 1, 0, -1, 1, 1, -1, -1 };
	int[] vy = { -1, 0, 1, 0, -1, 1, 1, -1 };
}

Measured memory_bytes: 50668
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pii;
#define endl '\n'
#define F first
#define S second
const int MAX_N=2e5+5;

int n;
ll c;
ll h[MAX_N];
ll dp[MAX_N];
set<int> st;
priority_queue<pii,vector<pii>,greater<pii>> pq;

ll step(int x, int y)
{ return dp[x]+(h[y]-h[x])*(h[y]-h[x])+c; }
ll calc_limit(int x, int y)
{ return (dp[y]+h[y]*h[y]-dp[x]-h[x]*h[x]-1)/(2*(h[y]-h[x]))+1ll; }

int main()
{
	scanf("%d%lld",&n,&c);
	for(int i=0;i<n;i++) scanf("%lld",&h[i]);
	st.insert(0);
	for(int i=1;i<n;i++)
	{
		while(!pq.empty()&&pq.top().F<=h[i])
		{
			auto now=pq.top();
			pq.pop();
			auto it1=st.find(now.S);
			if(it1==st.end()) continue;
			auto it2=next(it1);
			if(it2==st.end()) continue;
			if(step((*it1),i)<step((*it2),i)) continue;
			if(it1!=st.begin())
			{
				auto it0=prev(it1);
				pq.push({calc_limit((*it0),(*it2)),(*it0)});
			}
			st.erase(it1);
		}
		dp[i]=step((*st.begin()),i);
		pq.push({calc_limit((*st.rbegin()),i),(*st.rbegin())});
		st.insert(i);
	}
	printf("%lld\n",dp[n-1]);
	return 0;
}



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

int N, Q, b, c;
long long sum;
const int k = 1e5+5;
int arr[k], cnt[k];

int main() {
	
	ios_base::sync_with_stdio(false);
	sum = 0;
	cin >> N;
	for(int i = 0; i < N; i++) {
		cin >> arr[i];
		cnt[arr[i]]++;
		sum += arr[i];
	}
	cin >> Q;
	for(int i = 0; i < Q; i++) {
		cin >> b >> c;
		sum += (c-b)*cnt[b];
		cout << sum << "\n";
		cnt[c] += cnt[b];
		cnt[b] = 0;
	}
}

Measured memory_bytes: 4360
#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    int n,m;
    while(1){
        cin >> n >> m;
        if(n==0 and m==0) break;
        vector<int> T(n,0);
        vector<int> H(m,0);
        rep(i,n) cin >> T[i];
        rep(i,m) cin >> H[i];
        int sum_T=0,sum_H=0;
        rep(i,n) sum_T += T[i];
        rep(i,m) sum_H += H[i];
        vector<pair<int,int>> info(0);
        rep(i,n){
            rep(j,m){
                if(sum_T-T[i]+H[j] == sum_H -H[j]+T[i]){
                    info.push_back(make_pair(T[i],H[j]));
                }
            }
        }
        if(info.size()==0) cout << -1 << endl;
        else{
            pair<int,int> ma = info[0];
            for(auto i : info){
                if(i.first+i.second < ma.second+ma.first) ma  = i;
            }
            cout << ma.first << " " << ma.second << endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 3200
// D - Widespread
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define rp(i,n) for(int i=0;i<(n);++i)

int main(){
	int N,A,B; cin>>N>>A>>B;
	vector<LL> H(N); rp(i, N) cin>>H[i];

	int ans = 1e9;
	LL ab = (LL)A - B;//additional damage
	int L = 0, R = 1e9;
	while(L <= R){
		int t = (L + R)/2;//mid
		LL s = 0;
		rp(i, N){
			LL h = H[i] - (LL)t*B;
			if(h > 0) s += (h+ab-1)/ab;
		}
		if(t >= s){
			R = t - 1;//mid-1
			ans = t;
		}
		else L = t + 1;//mid+1
	}
	cout<< ans <<endl;
}

Measured memory_bytes: 1152
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int count = 1;
	map<int, int> a;
	a[n]++;
	while(a[n]!=2){
		count++;
		if(n%2) n = 3*n + 1;
		else n = n/2;
		a[n]++;
	}
	cout << count << endl;
	return 0;
}


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

int main( void )
{
    ll A,B;
    char op;
    cin >> A >> op >> B;
    
    if ( op == '+' )
    {
        cout << A + B << endl;
    }
    
    else if ( op == '-' )
    {
        cout << A - B << endl;
    }
}

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

# not 0, but 9 == not 9, but 0
#2 * (9 ** n - 8 ** n)

# not 0,9
#8 ** n

# ans = all - (not 0, but 9 + not 9, but 0) - not 0,9
print((10**n - 2 * (9 ** n - 8 ** n) - 8 ** n) %  (10**9 + 7))


Measured memory_bytes: 10908
#include <bits/stdc++.h>
#define debug(x) (cout << "#x = " << (x) << '\n')

using namespace std;
typedef long long ll;

inline char gc() {
	static char buf[100000], *p1 = buf, *p2 = buf;
	return (p1 == p2) && (p2 = (p1 = buf) +
		fread(buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
}

#define dd ch = getchar()
template <class T>
inline void read(T &x) {
	x = 0;
	int f = 0; char dd;
	for (; !isdigit(ch); dd) f ^= (ch == '-');
	for (; isdigit(ch); dd)  x = (x << 1) + (x << 3) + (ch ^ 48);
	x = f? -x: x;
}
#undef dd

template <class T>
inline void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 | 48);
}

template <class T>
inline void wrn(T x) {
	write(x), putchar(' ');
}

template <class T>
inline void wln(T x) {
	write(x), putchar('\n');
}

template <class T>
inline void wlnn(T x, T y) {
	wrn(x), wln(y);
}

ll n, r;

int main()
{
	read(n), read(r);
	if (n < 10) r += (10 - n) * 100;
	return wln(r), 0;
}

/*

*/




Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>
#include<set>
#include <cassert>
 
using namespace std;
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) cout<<(p)<<endl;
#define PP(p) cout<<(p)<<" ";
#define INF 1e18

typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
//int dy[8]={1,1,1,0,-1,-1,-1,0};
//int dx[8]={-1,0,1,1,1,0,-1,-1};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int k,n;
vi a;
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>k>>n;
    a.resize(n);
    rep(i,n)cin>>a[i];
    sort(ALL(a));
    int m=0,cnt = 0;
    rep(i,n){
        int t = i-1;
        if(i == 0)t = n-1;
        m = max(m,min(abs(a[i]-a[t]),k-abs(a[i]-a[t])));
    }
    cout << k-m << endl;
    return 0;
}


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

int main() {
    long long n;
	scanf("%lld",&n);
	long long temp;
	long long twos[61];
	twos[0]=1;
	for(int i=1;i<61;i++)twos[i]=twos[i-1]*(long long)(2);
	bool arr[n][61];
	for(int i=0;i<n;i++){
		scanf("%lld",&temp);
		for(int j=60;j>=0;j--){
			if(temp&twos[j]){
				arr[i][j]=1;
				//printf("1");
			}else{
				arr[i][j]=0;
				//printf("0");
			}
		}
		//printf("\n");
	}
	long long ans=0;
	long long cur;
	long long MOD=1000000007;
	for(long long i=0;i<61;i++){
		cur=0;
		for(int j=0;j<n;j++){
			if(arr[j][i]){
				cur++;
			}
		}
		//printf("%d %d\n",cur,n-cur);
		//ans+=(cur*(n-cur))*(1<<i);
		ans+=((((cur)*(n-cur))%MOD)*(twos[i]%MOD))%MOD;
		ans%=MOD;
	}
	printf("%lld",ans);
}

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

using namespace std;

const int N = 1e5 + 5;

int n;


int main()
{
    cin>>n;
    for(int i = 1;i<=9;i++)
    {
        for(int j = 1 ; j<=9 ; j++)
        {
            if(i*j==n)
                return cout<<"Yes",0;
        }
    }
    cout<<"No";
    return 0;
}


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

int yoko[4]={-1,0,0,1};
int tate[4]={0,-1,1,0};

int bfs(const vector<vector<char>> &maze, vector<vi> &arrived, int h, int w){
    queue<pair<int,int>> que;
    pair<int,int> first=make_pair(h,w);
    que.push(first);
    int ret=0;
    arrived[h][w]=0;
    while(!que.empty()){
        pair<int,int> v=que.front();
        que.pop();
        for(int dir=0;dir<4;dir++){
            int next_h=v.first+tate[dir];
            int next_w=v.second+yoko[dir];
            if(maze[next_h][next_w]=='#') continue;
            if(arrived[next_h][next_w]!=-1) continue;
            arrived[next_h][next_w]=arrived[v.first][v.second]+1;
            ret=max(ret,arrived[next_h][next_w]);
            pair<int,int> next=make_pair(next_h,next_w);
            que.push(next); 
        }
    }
    return ret;
}

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<char>> maze(h+2,vector<char>(w+2,'#'));
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin >> maze[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(maze[i][j]=='#') continue;
            vector<vi> arrived(h+1,vi(w+1,-1));
            ans=max(ans,bfs(maze,arrived,i,j));
        }
    }
    cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

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

#define VIN(v) for(auto&elem_: (v) )cin>>elem_
#define VOUT(v, sep) for(_loop_int idx=0; idx<(_loop_int)v.size(); idx++) {cout<<v[idx]; if(idx<v.size()-1) cout<<sep;} cout<<endl

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(debugidx,v.size())cout<<" "<<v[debugidx];cout<<endl
#define DEBUG_ARR(v,n) cout<<#v<<":";REP(debugidx,n)cout<<" "<<v[debugidx];cout<<endl
#define ALL(a) (a).begin(),(a).end()

const ll MOD = 1000000007ll;
const int IINF = numeric_limits<int>::max()/2-1;
const ll LINF = numeric_limits<ll>::max()/2-1;
#define FIX(a) ((a)%MOD+MOD)%MOD

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int a,b,c;
    cin>>a>>b>>c;
    int ans = min(c, b/a);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
n, k = map(int, input().split())
s = input()
a = []
if s[0] == '0':
    a.append(0)
l = r = 0
while l < n:
    while r < n and s[l] == s[r]:
        r += 1
    a.append(r-l)
    l = r
if s[-1] == '0':
    a.append(0)
m = len(a)
if m // 2 <= k:
    print(n)
else:
    ans = 0
    asum = [0 for _ in range(m+1)]
    for i in range(m):
        asum[i+1] = asum[i] + a[i]
    for i in range(m+1-2*k):
        if i % 2:
            continue
        ans = max(ans, asum[i+2*k+1] - asum[i])
    print(ans)

Measured memory_bytes: 8004
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_table(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, K = LI()
    A = sorted(LI())
    F = sorted(LI(), reverse=True)

    left = -1
    right = (10 ** 12) + 1

    while right - left > 1:
        tmp = 0
        mid = (right + left) // 2
        # print(left, mid, right, "-"*100)
        for ai, fi in zip(A, F):
            xi = mid // fi
            tmp += max(0, ai - xi)
            # print(ai, fi, xi, ai - xi)
        if tmp <= K:
            right = mid
        else:
            left = mid

    print(right)

if __name__ == '__main__':
    main()

Measured memory_bytes: 122136
/*
	Copyright: razouq (c)
	Author: Anass BENDARSI
	Date: 10/06/2017 18:59:50
	flamers will **** you
*/
#include<bits/stdc++.h>
//#include<flamers.h>
#define ull unsigned long long
using namespace std;

int main(){
	int n, m;
	cin>>n>>m;
	string x;
	for(int i = 0; i < m+2; ++i) cout<<"#";
	cout<<endl;
	for(int i = 0; i < n; ++i){
		cin>>x;
		cout<<"#"<<x<<"#"<<endl;
	}
	for(int i = 0; i < m+2; ++i) cout<<"#";
	cout<<endl;

	return 0;
}


Measured memory_bytes: 256
/*
            _ _  ___            __ _ _  _       _     
 _   _  ___| | |/ _ \__      __/ _| | || |  ___| |__  
| | | |/ _ \ | | | | \ \ /\ / / |_| | || |_/ __| '_ \ 
| |_| |  __/ | | |_| |\ V  V /|  _| |__   _\__ \ | | |
 \__, |\___|_|_|\___/  \_/\_/ |_| |_|  |_| |___/_| |_|
 |___/                 

 */

#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
#define MOD 1000000007
#define INF 1000000000000000007
#define MAXN 300005


signed main(){
	fast
	int n;
	cin>>n;
	vector<int> p;
	int temp;
	For(i, 0, n){
		cin>>temp;
		if(temp!=i+1){
			p.pb(temp);
			p.pb(i+1);
		}
	}

	int s = p.size();
	if(s==0){
		cout<<"YES"<<endl;
	}else if(s==4){
		if(p[0]==p[3] && p[1]==p[2]){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}else{
		cout<<"NO"<<endl;
	}

    return 0;
}
    



Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>

using namespace std;

#define REP(a, i, n) for (int i = a; i < n; ++i)

long abs(long X) {
    return X < 0 ? -X : X;
}

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

    long a[N];
    REP(0, i, N) {
        cin >> a[i];
    }

    long x = a[0];
    long y = 0;
    REP(1, i, N) {
        y += a[i];
    }

    long ans = abs(x - y);
    REP(1, i, N - 1) {
        x += a[i];
        y -= a[i];
        long z = abs(x - y);

        if (z < ans) {
            ans = z;
        }
    }

    cout << ans << endl;

    return 0;
}


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

#define MOD 1000000007
#define ll long long int

vector <ll> alist[100004];

ll dfs(ll str,ll vis[]){
    vis[str]=1;
    for(ll j=0;j<alist[str].size();j++){
        if(!vis[alist[str][j]]){
            dfs(alist[str][j],vis);
        }
    }
}


int main(){
    ll i,j,k,m,n,flag=0,t,x,b,c,d,u,v,sum=0,y,fsum,ssum,ans=0,cnt,l=0;
    cin>>t;
    double r;
    r=3.14*t*2;
    cout<<r<<endl;
    
    
  //  cout<<"Yes"<<endl;
  //  cout<<"No"<<endl;
       
     
       
    
    
    return 0;
}

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

int main(){
    int a[3];
    int b[3];
    int c[4] = {0,0,0,0};

    for(int i=0;i<3;i++){
        cin >> a[i] >> b[i];
        c[a[i]-1]++;
        c[b[i]-1]++;
    }
    string ans = "YES";
    for(int i=0;i<4;i++){
        if(c[i] > 2){
            ans = "NO";
            break;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
class UnionFind:
    parent = []
    rank = []

    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                return self.rank[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    uf = UnionFind(N)
    
    for _ in range(M):
        a, b = map(int, input().split())
        uf.unite(a-1, b-1)
    
    ans = 0
    for i in range(N):
        if uf.isSame(i, A[i] -1):
            ans += 1

    return ans

print(solve())

Measured memory_bytes: 13812
#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  int ans;
  cin>>s;
  if(s=="SSS")
    ans=0;
  else if (s=="RRR")
    ans=3;
  else if (s=="RRS"||s=="SRR")
    ans=2;
  else ans=1;
  
  
  cout<<ans<<endl;
}
  

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    stack<string> st;
    while(1){
        string s;
        cin >> s;
        if(cin.eof()) break;
        if(s == "+" || s == "-" || s == "*"){
            int b = stoi(st.top()); st.pop();
            int a = stoi(st.top()); st.pop();
            int tmp;
            if(s == "+") tmp = a + b;
            if(s == "-") tmp = a - b;
            if(s == "*") tmp = a * b;
            st.push(to_string(tmp));
        }else{
            st.push(s);
        }
    }
    cout << st.top() << endl;
}

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

#define MAX 200000
#define SENTINEL 2000000000
typedef long long ll;

int L[MAX/2 + 2], R[MAX/2 + 2];

ll merge(int A[], int n, int left, int mid, int right){
    int i, j, k;
    ll cnt = 0;
    int n1 = mid - left;
    int n2 = right - mid;
    for(i=0;i<n1;i++) L[i] = A[left + i];
    for(i=0;i<n2;i++) R[i] = A[mid + i];
    L[n1] = R[n2] = SENTINEL;
    i=j=0;
    for(k=left;k<right;k++){
        if(L[i] <= R[j]){
            A[k] = L[i++];
        }else{
            A[k] = R[j++];
            cnt += n1 - i;
        }
    }
    return cnt;
}

ll mergeSort(int A[], int n, int left, int right){
    int mid;
    ll v1,v2,v3;
    if(left+1<right){
        mid = (left+right)/2;
        v1 = mergeSort(A,n,left,mid);
        v2 = mergeSort(A,n,mid,right);
        v3 = merge(A,n,left,mid,right);
        return v1+v2+v3;
    } else return 0;
}

int main(){
    int A[MAX],n,i;

    cin >> n;
    for(i=0;i<n;i++){
        cin>>A[i];
    }

    ll ans = mergeSort(A,n,0,n);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4664
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, c, k, t[N];

int main() {
    scanf("%d%d%d", &n, &c, &k);
    for(int i = 0; i < n; i++) {
        scanf("%d", &t[i]);
    }
    sort(t, t+n);
    int ans = 0, cur = 0, r = -1;
    for(int i = 0; i < n; i++) {
        if(cur >= c || r < t[i]) {
            r = t[i] + k;
            cur = 0;
            ans++;
        }
        cur++;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 640
A, B, M = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
l = []
for i in range(M):
    l.append([int(i) for i in input().split()])

cand = [min(a)+min(b)]
for i in range(M):
    if l[i][0]-1<A and l[i][1]-1<B:
        cand.append(a[l[i][0]-1]+b[l[i][1]-1]-l[i][2])

print(min(cand))

Measured memory_bytes: 36460
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
#include<functional>
using namespace std;
using ll=long long;
using ld=long double;
using pint=pair<int,int>;
using pll=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	vector<vector<ll>> a(n, vector<ll>(n));
	REP(i, n) REP(j, n) cin >> a[i][j];
	vector<vector<ll>> dp(n, vector<ll>(1ll << n, 0));
	REP(i, n) if(a[0][i]) dp[0][(1ll << i)] = 1;
	FOR(i, 1, n) REP(j, (1ll << n)) {
		bitset<21> bit(j);
		if(bit.count() != i + 1) continue;
		REP(k, n) {
			if(!bit[k] || !a[i][k]) continue;
			dp[i][j] += dp[i - 1][j ^ (1ll << k)];
		}
		dp[i][j] %= MOD;
	}
	cout << dp[n - 1][(1ll << n) - 1] << endl;
	return 0;
}

/* --------------------------------------- */


Measured memory_bytes: 360832
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.regex;
import std.stdio;
import std.string;
import std.typecons;

int readint() { return readln.chomp.to!int; }
int[] readints() { return readln.split.map!(to!int).array; }

void main() {
    auto s = readln.chomp;
    auto m = matchFirst(s, r"([0-9])\1\1");
    writeln(m.empty ? "No" : "Yes");
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

## 3進数

N = ii()

shiki = [1]
for i in range(10):
    tmp = shiki[-1]*3
    shiki.append(tmp)

ele = [3, 5, 7]
l = []
for keta in range(3, 10):
    maxx = shiki[keta]
    for i in range(maxx):
        ten = 10**(keta-1)
        tmp = 0
        for j in reversed(range(keta)):
            tmp += ele[i//shiki[j]] * ten
            i %= shiki[j]
            ten //= 10
        l.append(tmp)

cnt = 0
for num in l:
    if num > N:
        break
    num = str(num)
    if all(e in num for e in ['3', '5', '7']):
        cnt += 1
            
print(cnt)

Measured memory_bytes: 4360
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <map>
#include <set>
#include <list>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <limits>
#include <cassert>

using namespace std;

using i64 = long long int;
using u64 = std::uint_fast64_t;
using P = pair<i64, i64>;

struct edge {
    i64 from, to, cost;
    edge(i64 from, i64 to) : from(from), to(to), cost(1) {}
    edge(i64 from, i64 to, i64 cost) : from(from), to(to), cost(cost) {}
};
using Graph = vector<vector<edge>>;

constexpr i64 INF = std::numeric_limits<i64>::max();
constexpr i64 SINF = std::numeric_limits<i64>::max() / 10;
constexpr i64 MOD = 1000000007;
constexpr i64 dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
//const i64 dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//const i64 dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//const i64 dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
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 V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e : t) fill_v(e, v);
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main() {
    i64 a, b;
    cin >> a >> b;
    cout << max({a + b, a - b, a * b}) << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main {
	
	public static void main(String[] args) {
	
		MyScanner sc = new MyScanner();
		
		//String s=sc.next();
		int n=sc.nextInt();
		int m=sc.nextInt();
		int ans=0;
		int a[]=new int[m];
		int k[]=new int[n];
		int p;
		
		for(int i=0;i<n;i++) {
			k[i]=sc.nextInt();
			for(int j=0;j<k[i];j++) {
				p=sc.nextInt();
				a[p-1]++;
				if(a[p-1]==n){
					ans++;
				}
			}
					
		}
		System.out.println(ans);
		
	}	
	
	
	
//----------------------------------------------------------
	static int l_min(int[] a) {
		Arrays.sort(a);
		return a[0];
	}
	static int l_max(int[] a) {
		int l=a.length;
		Arrays.sort(a);
		return a[l-1];
	}
	public static PrintWriter out;

	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}
	

}


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

using namespace std;
using ll = long long;

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

    vector<ll> x(n), y(n);
    vector<ll> xary, yary;

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

        xary.push_back(x[i]);
        yary.push_back(y[i]);
    }

    sort(xary.begin(), xary.end());
    sort(yary.begin(), yary.end());

    ll ans = 1LL * (xary[n - 1] - xary[0]) * (yary[n - 1] - yary[0]);

    for (int xi = 0; xi < n;xi++)
    {
        for (int xj = xi + 1; xj < n;xj++)
        {
            for (int yi = 0; yi < n;yi++)
            {
                for (int yj = yi + 1; yj < n;yj++)
                {
                    ll l = xary[xi];
                    ll r = xary[xj];
                    ll d = yary[yi];
                    ll u = yary[yj];

                    // check the number of points in the rectangle.
                    int cnt = 0;
                    for (int i = 0; i < n; i++)
                    {
                        if(l <= x[i] && x[i] <= r && d <= y[i] && y[i] <= u)
                        {
                            cnt++;
                        }
                    }

                    if(cnt >= k)
                    {
                        ans = min(ans, 1LL * (r - l) * (u - d));
                    }
                }
            }
        }
    }
    cout << ans << endl;

    return 0;
}

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

int main(){
  int n;
  cin >> n;
  ll a[n], s[n+1], sum = 0;
  map<ll, ll> mp;
  for(int i = 0; i < n; i++) cin >> a[i];
  s[0] = 0;
  for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i-1];
  sort(s, s + n + 1);
  for(auto &e : s) mp[e]++;
  for(auto &e : mp) sum += e.second * (e.second - 1) / 2;
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 15872
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
#include <iomanip>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1844674407370955161
typedef long long int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007


int main()
{
    int N;
    cin >> N;
    int A[N];
    double s = 0;
    REP(i, 0, N)
    {
        cin >> A[i];
        s += 1.0 / A[i];
    }
    s = 1.0 / s;
    std::cout << std::setprecision(8) << s << endl;
    return 0;
}

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

int main(){
	int a,b,i,cnt,tmp;
	int flag[102];

	while(scanf("%d %d",&a,&b) != EOF){
		memset(flag,0,sizeof(flag));
		flag[a-1]++;
		flag[b-1]++;
		while(1){
			scanf("%d %d",&a,&b);
			if(a == 0 && b == 0){
				break;
			}
			flag[a-1]++;
			flag[b-1]++;
		}
		cnt = 0;
		tmp = 1;
		for(i = 0;i < 100;i++){
			if(flag[i] % 2 == 1){
				cnt++;
				if(cnt == 3){
					tmp = 0;
					break;
				}
			}
		}
		if(!(flag[0] == 1 && flag[1] == 1)){
			tmp = 0;
		}
		if(tmp){
			printf("OK\n");
		}else{
			printf("NG\n");
		}
	}

	return 0;
}

Measured memory_bytes: 584