akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
import static java.lang.Math.abs;
import static java.lang.Math.min;

public class Main{
public static void main(String... argv){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int k=sc.nextInt();
int ans=0;
for(int i=0;i<n;i++){
int x=sc.nextInt();
ans+=min(x,abs(k-x));
}
System.out.println(ans*2);
}
}

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

using namespace std;
using ll = long long;


int main(){
  ll n, k;
  cin >> n >> k;
  vector<ll> p(n);
  for(int i=0; i<n; i++) cin >> p[i], p[i]++;
  
  vector<ll> s(n+1, 0);
  for(int i=0; i<n; i++) s[i+1] = s[i] + p[i];
  
  ll res = 0;
  for(int i=0; i+k<=n; i++) res = max(res, s[i+k]-s[i]);
  
  cout << fixed << setprecision(10) << (double)(res)/2 << endl;

  return 0;
}

Measured memory_bytes: 6384
class TaskQ
  def initialize(qtime)
    @queue=[]
    @qtime=qtime
    @etime=0
  end

  def enq(name, qtime)
    @queue<<Process.new(name,qtime)
  end

  def deq
    process=@queue.shift
    process.ptime-=@qtime
    @etime+=@qtime
    if process.ptime<=0
      @etime+=process.ptime
      puts "#{process.name} #{@etime}"
    else
      @queue<<process
    end
  end

  def empty?
    return @queue.empty?
  end

  class Process
    attr_accessor :name, :ptime
    def initialize(name, ptime)
      @name=name
      @ptime=ptime
    end
  end
end

n,q=gets.split.map &:to_i
task=TaskQ.new(q)
n.times do
  name,ptime=gets.split
  task.enq(name,ptime.to_i)
end

loop do
  break if task.empty?
  task.deq
end

Measured memory_bytes: 13440
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>

using namespace std;
const int MAXN = 100005;
typedef long long LL;

inline int rd(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {f=ch=='-'?-1:1;ch=getchar();}
	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}

struct Data{
	LL diff;
	int id;
}data[MAXN];

int n,m,a[MAXN];
int fa[MAXN],num;
LL now[MAXN<<1],ans[MAXN],sum[MAXN];
bool vis[MAXN];
LL k; 

int get(int x){
	if(vis[x]) return 0;
	now[++num]=x;
	vis[x]=1;
	return get(fa[x])+1;
}

int main(){
//	freopen("data.txt","r",stdin);
//	freopen("wrong.txt","w",stdout);
	n=rd();
	for(register int i=1;i<=n;i++){
		a[i]=rd();
		data[i].diff=a[i]-a[i-1],data[i].id=i;
	}
	m=rd();scanf("%lld",&k);
	for(register int i=1;i<=m;i++){
		int x=rd();
		swap(data[x],data[x+1]);
	}
	for(register int i=1;i<=n;i++)	{
		if(data[i].id==i) continue;
		fa[i]=data[i].id;
	}
	for(register int i=1;i<=n;i++){
		if(data[i].id==i) {
			ans[i]=data[i].diff;
			continue;
		}
		if(vis[i]) continue;
		int siz=get(i);
		for(register int j=1;j<=siz;j++) now[j+siz]=now[j];
		LL to=(k-1ll)%(LL)siz;
		for(register int j=1;j<=siz;j++) 
			ans[now[j]]=data[now[j+to]].diff;
		num=0;
	}
//	for(register int i=1;i<=n;i++) cout<<ans[i]<<" ";cout<<endl;
	for(register int i=1;i<=n;i++)
		ans[i]+=ans[i-1],printf("%lld.0\n",ans[i]);
	return 0; 
}

Measured memory_bytes: 6272
import sys
input = lambda: sys.stdin.readline().rstrip()


def light_count(light, H, W, h, w, count, wr=-1, hr=-1):

    if wr != -1:
        for i in range(h * W + wr, h * W + w):
            light[i] += count
    elif hr != -1:
        for i in range(hr * W + w, h * W + w, W):
            light[i] += count


def solve():
    H, W = map(int, input().split())
    S = [[] for _ in range(H)]
    light = [0 for _ in range(H * W)]
    for i in range(H):
        S[i] = list(input())

    for h in range(H):
        count = 0
        wr = -1
        for w in range(W):
            if S[h][w] == '.':
                if wr == -1:
                    wr = w
                count += 1
            elif S[h][w] == '#':
                if wr != -1:
                    light_count(light, H, W, h, w, count, wr=wr)
                    wr = -1
                    count = 0
        else:
            if wr != -1:
                light_count(light, H, W, h, w + 1, count, wr=wr)
                wr = -1
                count = 0

    for w in range(W):
        count = 0
        hr = -1
        for h in range(H):
            if S[h][w] == '.':
                if hr == -1:
                    hr = h
                count += 1
            elif S[h][w] == '#':
                if hr != -1:
                    light_count(light, H, W, h, w, count, hr=hr)
                    hr = -1
                    count = 0
        else:
            if hr != -1:
                light_count(light, H, W, h + 1, w, count, hr=hr)
                hr = -1
                count = 0

    print(max(light) - 1)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 220936
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define RFOR(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define rep(i,n) FOR(i,0,(n))
#define REPS(i,n) FOR(i,1,(n)+1)
#define RREP(i,n) RFOR(i,0,(n))
#define rng(x) (x).begin(),(x).end()
#define rrng(x) (x).rbegin(),(x).rend()
#define debug(x) cout << #x << " = " << (x) << endl;
#define SORT(x) sort(rng(x))
#define RSORT(x) sort(rrng(x))
#define SUM(x) accumulate(rng(x),0)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define uni(x) x.erase(unique(rng(x)),x.end())
#define SP << " " <<
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const int mod = 1000000007;
const double EPS = 1e-9;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

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

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

int main () {
  double a, b, x;
  cin >> a >> b >> x;
  double s0 = a*b/2;
  double s = x/a;
  double ans;
  if (s >= s0) {
    double h = 2*(a*b-s)/a;
    ans = atan2(h,a)*180/M_PI;
  }
  else {
    double w = 2*s/b;
    ans = atan2(b,w)*180/M_PI;
  }
  printf("%.10f\n", ans);
  return 0;
}

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

using namespace std;

typedef long long ll;

const int maxn=1e5+5,mod=1e9+7;

ll f(int x,int y)
{
    ll base=x,ans=1;
    while(y)
    {
        if(y%2)
            ans=ans*base%mod;
        base=base*base%mod;
        y/=2;
    }
    return ans%mod;
}

ll cmb(int n,int c)
{
    int i;
    ll ans=1;
    for(i=1;i<=c;i++)
    {
        ll v,w;
        v=(n-i+1)%mod;
        w=i%mod;
        ans=ans*(v*f(w,mod-2)%mod)%mod;
    }
    return ans%mod;
}

int main()
{
    int n,a,b;
    while(scanf("%d%d%d",&n,&a,&b)!=EOF)
    {
        ll kk;
        kk=f(2,n)-1;
        kk=(kk-cmb(n,a)+mod)%mod;
        kk=(kk-cmb(n,b)+mod)%mod;
      printf("%lld\n",kk);
    }
    return 0;
}


Measured memory_bytes: 256
using System;
class p
{
  static void Main()
  {
    string[] input = Console.ReadLine().Split(' ');
    int A = int.Parse(input[0]);
    int B = int.Parse(input[1]);
    int K = int.Parse(input[2]);
    
    int count = 0;
    for (int i = Math.Min(A, B); 0 < i; i--) {
      if (A%i==0 && B%i==0) {
        if (++count == K) {
          Console.WriteLine(i);
          break;
        }
      }
    }
  }
}

Measured memory_bytes: 13140
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
C=0
for i in range(n-1):
    if a[i]+1==a[i+1]:
        C+=c[a[i]-1]
print(sum(b)+C)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1e9

signed main()
{
    int x;
    cin >> x;
    int a = 100;
    int i = 0;
    for (; a < x; i++)
    {
        a = a + a / 100;
    }
    cout << i << endl;
}

Measured memory_bytes: 3636
# ABC083B - Some Sums
def main():
    n, a, b = [int(x) for x in input().split()]

    m = 0
    for i in range(1, n+1):
        s = str(i)
        k = 0
        for j in s:
            k += int(j)

        if a <= k and k <= b:
            m += i

    print(m)
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 39152
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
int main(){
	string s;
	cin >> s;
	ll ans=0;
	for(ll i=0;i<(1<<s.length()-1);i++){
		int preplus=0;
		for(int j=1;j<=s.length()-1;j++){
			if((i>>s.length()-1-j)&1){
				string subs=s.substr(preplus,j-preplus);
				ans+=stoll(subs);
				preplus=j;
			}
		}
		string subs=s.substr(preplus,s.length()-preplus);
		ans+=stoll(subs);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

vector<int> ZAlgorithm(string s){
  int N = s.size();
  vector<int> z(N);
  z[0] = N;
  int left = 0;
  int right = 0;
  for(int k = 1; k < N; k++){
    if(k > right){
      left = k;
      right = k;
      while(right < N && s[right] == s[right - left]){
        right++;
      }
      z[k] = right - left;
      right--;
    } else {
      int k1 = k - left;
      if(z[k1] + k <= right){
        z[k] = z[k1];
      } else {
        left = k;
        while(right < N && s[right] == s[right - left]){
          right++;
        }
        z[k] = right - left;
        right--;
      }
    }
  }

  return z;
}

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

  int ans = 0;
  for(int i = 0; i < N; i++){
    vector<int> z = ZAlgorithm(s.substr(i, N - i));
    for(int j = 0; j < z.size(); j++){
      ans = max(ans, min(j, z[j]));
    }
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
typedef long long LL;
using std::min;
int main(){
	LL n,m;scanf("%lld%lld",&n,&m);
	LL ans=min(n,m/2);
	n-=ans;m-=2*ans;
	if(n==0)ans+=m/4;
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;

public class Main {
	static int[] f = new int[101];
	static int n;
	private static void solve(){
		//Implement solution here.
		int n = ni();
		int m = ni();
		List<City> cl = new ArrayList<>();
		
		for(int i = 0; i < m; i++) {
			cl.add(new City(i, ni(), ni()));
		}
		Comparator<City> cmp1 = Comparator.comparing(City::getP).thenComparing(City::getY);
		Comparator<City> cmp2 = Comparator.comparing(City::getIdx);
		
		cl.sort(cmp1);
		
		int tmpp = -1;
		int tmpcnt = 1;
		for(int i = 0; i < m; i++) {
			City c = cl.get(i);
			if(c.p != tmpp) {
				tmpp = c.p;
				tmpcnt = 1;
			} else {
				tmpcnt++;
			}
			c.id = String.format("%06d", tmpp) + String.format("%06d", tmpcnt);
		}
		
		cl.sort(cmp2);
		StringBuilder sb = new StringBuilder();
		cl.forEach(v -> sb.append(v.id + System.getProperty("line.separator")));
		System.out.println(sb);
	}
	
	static class City {
		private int idx;
		private int p;
		private int y;
		public String id;
		public City(int idx, int p, int y) {
			this.idx = idx;
			this.p = p;
			this.y = y;
		}
		public int getIdx() {
			return idx;
		}
		public void setIdx(int idx) {
			this.idx = idx;
		}
		public int getP() {
			return p;
		}
		public void setP(int p) {
			this.p = p;
		}
		public int getY() {
			return y;
		}
		public void setY(int y) {
			this.y = y;
		}		
	}

	//Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		}
		solve();
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

Measured memory_bytes: 177680
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define MuhammedAly ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define popc(x) __builtin_popcount(x)
#define LLMX 1e18
#define NotinRange(n,m) i<0||i>=(n)||j<0||j>=(m)
#define mem(x,y) memset((x),(y),sizeof (x));
#define sz(a) (int)(a).size()
#define inFile(s) freopen((s),"r",stdin)
#define	outFile(s) freopen((s),"w",stdout)
#define biEdge(v, a, b) (v)[(a)].pb((b)), (v)[(b)].pb((a))
#define pi (2 * acos(0))
#define X real()
#define Y imag()
#define cross(a, b) ((conj(a) * (b)).Y)
#define dot(a, b) ((conj(a) * (b)).X)
#define vec(a,b) ((b) - (a))
#define ll long long
typedef long double ld;
typedef complex<double>point;
typedef tuple<int, int, int> line;
typedef pair<point, point>segment;
typedef vector<point>polygon;
const int N = 18, M = 100 + 5, OO = 0x3f3f3f3f, mod = 1e9 + 7, base = 131, mod2 = 1000136437, mod3 = 998244353;
const double EPS = 1e-9;

int main()
{
	MuhammedAly
	int n;
	cin >> n;
	int h[n+1],ans[n+1];
	for(int i =0;i<n;cin >> h[i++]);
	ans[0] = 0,ans[1] = abs(h[1] - h[0]);
	for(int i =2;i<n;i++)
		ans[i] = min(ans[i-1]+abs(h[i]-h[i-1]),ans[i-2]+abs(h[i]-h[i-2]));
	cout << ans[n-1];
	return 0;
}


Measured memory_bytes: 1024
import java.util.*;
public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();
		long D = sc.nextLong();
		long ans = (B / C - (A - 1) / C) + (B / D - (A - 1) / D) - (B / lcm(C, D) - (A - 1) / lcm(C, D));
		System.out.println(B - A - ans + 1);
	}
	
	static long lcm(long m, long n) {
	    return m * n / gcd(m, n);
	}

	static long gcd (long a, long b) {
		return b > 0 ? gcd(b, a % b) : a;
	}
}


Measured memory_bytes: 21204
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int Case = 1;
		while(true){
			int n = sc.nextInt();
			if(n==0)break;
			double a[][] = new double[n][2];
			for(int i=0;i<n;i++){
				a[i][0] = sc.nextDouble();
				a[i][1] = sc.nextDouble();
			}
			double area = 0;
			for(int i=0;i<n-1;i++) area+=(a[i][0]*a[i+1][1]-a[i][1]*a[i+1][0])/2;
			area+=(a[n-1][0]*a[0][1]-a[n-1][1]*a[0][0])/2;
			System.out.printf("%d %.1f\n", Case++, -area);
		}
	}
}

Measured memory_bytes: 31728
#include <bits/stdc++.h>
    using namespace std;
     
    int S, W;
     
    int main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cin >> S >> W;
        if(W >= S){
            cout << "unsafe" << endl;
        }else{
            cout << "safe" << endl;
        }
        return 0;
    }

Measured memory_bytes: 3612
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <set>
#include <utility>
#include <vector>
using namespace std;

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

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

	for(int n; cin >> n && n;) {
		vector<pair<int, int>> swimmers(n);
		vector<int> t(n), c(n);

		for(auto &e : swimmers) {
			cin >> e.first >> e.second;
		}

		sort(swimmers.begin(), swimmers.end());
		queue<pair<int, int>> go, back;
		for(int i = 0; i < n; ++i) {
			go.push({swimmers[i].first, i});
		}

		int go_last = swimmers[n - 1].first;
		int back_last = 0;
		while(true) {
			int time = INT_MAX;
			bool go_turn;
			set<int> S;

			if(!go.empty()) {
				time = go.front().first;
				go_turn = true;
			}
			if(!back.empty() && time > back.front().first) {
				time = back.front().first;
				go_turn = false;
			}

			if(go_turn) {
				while(!go.empty() && time == go.front().first) {
					S.insert(go.front().second);
					go.pop();
				}

				for(const auto &e : S) {
					chmax(back_last, time + swimmers[e].first);
					back.push({back_last, e});
				}
			}
			else {
				while(!back.empty() && time == back.front().first) {
					S.insert(back.front().second);
					back.pop();
				}

				for(const auto &e : S) {
					if(--swimmers[e].second == 0) continue;
					chmax(go_last, time + swimmers[e].first);
					go.push({go_last, e});
				}

				if(go.empty() && back.empty()) {
					cout << time << endl;
					break;
				}
			}
		}
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1224
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<utility>
#include<tuple>
#include<algorithm>
#include<cmath>
using namespace std;

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

template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
  int n;
  cin >> n;
  vector<vector<int>> x(n, vector<int>(3));
  rep(i,n) cin >> x[i][0] >> x[i][1] >> x[i][2];
  vector<vector<ll>> dp(n+1, vector<ll>(3));
  for(int i=1; i<=n; i++){
    rep(j,3){
      rep(k,3){
        if(j==k)
          continue;
        chmax(dp[i][k],dp[i-1][j]+x[i-1][k]);
      }
    }
  }
  ll res=0;
  rep(i,3)
    chmax(res, dp[n][i]);
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 11136
#include <algorithm>
#include <cstring>
#include <cstdio>
#define MOD 998244353
#define GEN 3
typedef long long ll;
inline int sum(int x, int y)
{
	x += y;
	if (x >= MOD)
		x -= MOD;
	return x;
}
inline int sub(int x, int y)
{
	x -= y;
	if (x < 0)
		x += MOD;
	return x;
}
inline int quick_pow(int a, int n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = (ll)res * a % MOD;
		a = (ll)a * a % MOD;
		n >>= 1;
	}
	return res;
}
int alpha[2][400005], poly_rev[400005], poly_ntt_lst = -1;
inline void poly_ntt_init(int n)
{
	if (poly_ntt_lst == n)
		return;
	poly_ntt_lst = n;
	alpha[0][0] = alpha[1][0] = 1;
	alpha[0][1] = quick_pow(GEN, (MOD - 1) / n);
	alpha[1][1] = quick_pow(alpha[0][1], MOD - 2);
	for (int i = 2; i <= n; i++)
	{
		for (int x = 0; x < 2; x++)
			alpha[x][i] = (ll)alpha[x][1] * alpha[x][i - 1] % MOD;
	}
	for (int i = 1, j = n >> 1; i + 1 < n; i++)
	{
		poly_rev[i] = j;
		int k = n >> 1;
		while (j >= k)
		{
			j -= k;
			k >>= 1;
		}
		j += k;
	}
}
inline void poly_ntt(int *arr, int n, bool f)
{
	poly_ntt_init(n);
	for (int i = 1; i + 1 < n; i++)
	{
		if (i < poly_rev[i])
			std::swap(arr[i], arr[poly_rev[i]]);
	}
	for (int i = 1; i < n; i <<= 1)
	{
		for (int j = 0, off = n / (i << 1); j + i < n; j += i << 1)
		{
			for (int k = j, cur = 0; k < j + i; k++, cur += off)
			{
				int x = (ll)arr[k + i] * alpha[f][cur] % MOD;
				arr[k + i] = sub(arr[k], x);
				arr[k] = sum(arr[k], x);
			}
		}
	}
	if (f)
	{
		int x = quick_pow(n, MOD - 2);
		for (int i = 0; i < n; i++)
			arr[i] = (ll)arr[i] * x % MOD;
	}
}
inline void poly_mul(int *a, int *b, int n)
{
	static int tmp[400005];
	int len = 1;
	while (len >> 1 < n)
		len <<= 1;
	memset(a + n, 0, len - n << 2);
	memcpy(tmp, b, n << 2);
	memset(tmp + n, 0, len - n << 2);
	poly_ntt(a, len, false);
	poly_ntt(tmp, len, false);
	for (int i = 0; i < len; i++)
		a[i] = (ll)a[i] * tmp[i] % MOD;
	poly_ntt(a, len, true);
}
int dp[400005], trans[400005], fact[400005], inv[400005];
char a[100005], b[100005];
int main()
{
	// freopen("AGC019-E.in", "r", stdin);
	fact[0] = inv[0] = 1;
	for (int i = 1; i <= 1e5; i++)
	{
		fact[i] = (ll)fact[i - 1] * i % MOD;
		inv[i] = quick_pow(fact[i], MOD - 2);
	}
	scanf("%s%s", a, b);
	int n = strlen(a), mid = 0, st = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i] == '1' && b[i] == '1')
			mid++;
		else if (a[i] == '1')
			st++;
	}
	for (int i = 0; i <= mid; i++)
		trans[i] = inv[i + 1];
	dp[0] = 1;
	int x = st;
	while (x)
	{
		if (x & 1)
			poly_mul(dp, trans, mid + 1);
		poly_mul(trans, trans, mid + 1);
		x >>= 1;
	}
	ll ans = 0;
	for (int i = 0; i <= mid; i++)
		(ans += dp[i]) %= MOD;
	printf("%lld\n", ans * fact[st] % MOD * fact[mid] % MOD * fact[st + mid] % MOD);
	return 0;
}


Measured memory_bytes: 11136
w,h,n=map(int,raw_input().split())
x1,x2,y1,y2=0,w,0,h
for i in range(n):
    x,y,a=map(int,raw_input().split())
    if a==1: x1=max(x1,x)
    if a==2: x2=min(x2,x)
    if a==3: y1=max(y1,y)
    if a==4: y2=min(y2,y)
print max(0,x2-x1)*max(0,y2-y1)

Measured memory_bytes: 2568
using System;
using System.Collections.Generic;
using System.Linq;

namespace FallingAsleep
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int musicCount = int.Parse(Console.ReadLine());
            List<Music> playList = new List<Music>();

            // プレイリストを標準入力から読み込む
            for(int i = 0; i < musicCount; i++)
            {
                string[] inputRow = Console.ReadLine().Split(' ');

                var music = new Music(inputRow[0], int.Parse(inputRow[1]));

                playList.Add(music);
            }

            // ニワンゴ君が眠ってしまった瞬間流れて終わった曲
            string boringMusicName = Console.ReadLine();
            Music boringMusic = playList.Single(m => m.name == boringMusicName);

            // ニワンゴ君が寝過ごした曲リスト
            // 眠ってしまった曲の次の曲から
            var missedMusics = playList.SkipWhile(m => m.name != boringMusicName).Skip(1).ToList();
            // ニワンゴ君が寝ていた時間
            var sleepingTime = missedMusics.Sum(m => m.time);

            Console.WriteLine(sleepingTime);
        }
    }

    struct Music
    {
        public string name;
        public int time;

        public Music(string name, int time)
        {
            this.name = name;
            this.time = time;
        }

        public override string ToString()
        {
            return $"Music({name}, {time})";
        }
    }
}


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

using namespace std;
struct pp
{
    long long x,l;
} a[100005];
bool comp(pp a,pp b)
{
    return a.x+a.l<b.x+b.l;
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    long long cou=1;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i].x>>a[i].l;
    }
    sort(a,a+n,comp);
    long long t=a[0].x+a[0].l;
    for(int i=1; i<n; i++)
    {
        long long h=a[i].x-a[i].l;
        long long p=a[i].x+a[i].l;
        if(h>=t)
        {
            cou++;
            t=p;
        }
    }
    cout<<cou<<endl;
    return 0;
}


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

using namespace std;
#define ll long long
int main()
{
   ll a,b,n;
   cin>>a>>b>>n;
   if (n<b)
    cout<<(a*n)/b-a*(n/b);
   else
    cout<<(a*(b-1))/b;
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))

using namespace std;

using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
inline u64 xorshift() { static u64 x = 88172645463325252ull; x = x ^ (x << 7); return x = x ^ (x >> 9); }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { if (x < y) x = y; }
template <typename T> inline void amin(T &x, T y) { if (x > y) x = y; }
template <typename T> inline T power(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
template <typename T, typename S> istream& operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
template <typename T, typename S> ostream& operator<<(ostream &os, pair<T, S> &p) { os << p.first << ' ' << p.second; return os; }

void solve() {
  int x, y;
  cin >> x >> y;
  if (x == 1 && y == 1) {
    cout << 1000000 << endl;
  } else {
    auto f = [&](int a) {
      switch (a) {
        case 1: return 300000;
        case 2: return 200000;
        case 3: return 100000;
        default: return 0;
      }
    };
    cout << f(x) + f(y) << endl;
  }
}


Measured memory_bytes: 256
/*
　　　  ∧＿∧　やあ
　　 （´・ω・｀)　　　　　/　　　　　ようこそ、バーボンハウスへ。
　　 ／∇y:::::＼　　　 [￣]　　　　　このテキーラはサービスだから、まず飲んで落ち着いて欲しい。
　　 |:⊃:|:::::|　　　|──|
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|　うん、「また」なんだ。済まない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣|￣　  仏の顔もって言うしね、謝って許してもらおうとも思っていない。
￣￣￣￣￣￣￣￣￣￣￣￣￣￣／|
　　　　∇　∇　∇　∇　　　／.／|　　　でも、この提出を見たとき、君は、きっと言葉では言い表せない
　　　　┴　┴　┴　┴　／ ／　  |　　　「ときめき」みたいなものを感じてくれたと思う。
￣￣￣￣￣￣￣￣￣￣|／　　  |　　　殺伐としたコンテストの中で、そういう気持ちを忘れないで欲しい
￣￣￣￣￣￣￣￣￣￣　　　　 |　　　そう思って、この提出を投げたんだ。
　　　(⊆⊇)　(⊆⊇)　(⊆⊇)　　|
　    ||　　 ||　　||　　|　　　 じゃあ、判定を聞こうか。
　　.／|＼　／|＼ ／|＼
*/

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define fst first
#define snd second
#define ALL(obj) (obj).begin(),(obj).end()
#define debug(x) cerr << #x << " -> " << x << " (line:" << __LINE__ << ")" << '\n';
#define debugpair(x, y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ") (line:" << __LINE__ << ")" << '\n';
typedef long long lint;
typedef priority_queue<int> p_que;
typedef priority_queue<int, vector<int>, greater<int>()> p_que_rev;
// const int INF = INT_MAX;
const lint LINF = LLONG_MAX;
const lint MOD = 1000000000 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
const int di[]{0, -1, 0, 1, -1, -1, 1, 1};
const int dj[]{1, 0, -1, 0, 1, -1, -1, 1};

bool simulate(int start, int mode, string s, int n, int q, vector<char> &t, vector<char> &d){
  int pos = start;
  for (int i=0; i<q; ++i){
    if(s[pos] == t[i]){
      if(d[i] == 'L'){
        pos--;
      }
      else if(d[i] == 'R'){
        pos++;
      }
    }
    if(mode == 0 && pos < 0){
      return true;
    }
    else if(mode == 1 && pos >= n){
      return true;
    }
  }
  return false;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    lint n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<char> t(q);
    vector<char> d(q);
    for (int i=0; i<q; ++i){
      cin >> t[i] >> d[i];
    }
    int low = 0;
    int hi = n;
    int left = 0;
    int right = n;
    int mid;
    while(low != hi){
      mid = (low + hi) / 2;
      auto check = simulate(mid, 0, s, n, q, t, d);
      if(check){
        low = mid + 1;
      }
      else {
        hi = mid;
      }
    }
    left = low;
    // debug(left);
    low = 0;
    hi = n;
    while(low != hi){
      mid = (low + hi) / 2;
      auto check = simulate(mid, 1, s, n, q, t, d);
      // debugpair(mid, check);
      if(check){
        hi = mid;
      }
      else {
        low = mid + 1;
      }
    }
    right = low;
    // debug(right);
    lint ans = n;
    ans -= left;
    ans -= n - right;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1216
// 0203
#include <iostream>
#include <vector>
using namespace std;

int main(){
	while(1){
		int X, Y, c;
		vector<vector<int> > grid, count;
	
		cin>>X>>Y;
		if((X == 0) && (Y == 0))
			break;

		grid.resize(X+2);
		for(int i=0;i<X+2;i++)
			grid[i].resize(Y+2);

		for(int j=0;j<Y+2;j++){
			for(int i=0;i<X+2;i++){
				if((i == 0) || (i == X+1) || (j == 0) || (j == Y+1)){
					grid[i][j] = 1;
				}else{
					cin>>c;
					grid[i][j] = c;
				}
			}
		}

		count.resize(X+2);
		for(int i=0;i<X+2;i++)
			count[i].resize(Y+2);

		for(int i=0;i<X+2;i++)
			for(int j=0;j<Y+2;j++)
				count[i][j] = 0;

		for(int i=1;i<=X;i++)
			if(grid[i][1] == 0)
				count[i][1]++;

		for(int j=2;j<=Y;j++){
			for(int i=1;i<=X;i++){
				if(grid[i][j] == 1){
					continue;
				}else if(grid[i][j] == 2){
					if(grid[i][j-1] != 2)
						count[i][j] += count[i][j-1];
					if(grid[i][j-2] == 2)
						count[i][j] += count[i][j-2];
				}else{
					for(int k=-1;k<=1;k++)
						if(grid[i+k][j-1] != 2)
							count[i][j] += count[i+k][j-1];
					if(grid[i][j-2] == 2)
						count[i][j] += count[i][j-2];
				}
			}
		}

		int ans = 0;
		for(int i=1;i<=X;i++){
			ans += count[i][Y];
			if(grid[i][Y-1] == 2)
				ans += count[i][Y-1];
		}
		
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 1212
import java.util.*;

/*
問題文
整数 r が与えられます。

半径 r の円の面積が半径 1 の円の面積の何倍になるかを求めてください。
なお答えは制約の下では必ず整数になることが示せます。

制約
1≤r≤100
入力中のすべての値は整数である。

*/

public class Main {
    public static void main(String[] args){

        Scanner s = new Scanner(System.in);
        int r = s.nextInt();

        System.out.println(r*r);
    }
}

Measured memory_bytes: 22736
#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define INF  (1<<30)
#define INFL (1LL<<60)
#define MOD 1000000007LL
#define EPS ((ld)(1e-9))
 
#define sz(x) ((int)(x).size())
#define setz(x) memset(x, 0, sizeof(x))
#define all(x) (x).begin(), (x).end()
#define rep(i, e) for (int i = 0, _##i = (e); i < _##i; i++)
#define repp(i, s, e) for (int i = (s), _##i = (e); i < _##i; i++)
#define repr(i, s, e) for (int i = (s)-1, _##i = (e); i >= _##i; i--)
#define repi(i, x) for (auto &i : (x))
 
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const pair<T, V> pai) { 
    return os << '(' << pai.first << ' ' << pai.second << ')';
}
 
template<typename T>
ostream &operator<<(ostream &os, const vector<T> v) {
    cout << '[';
    for (auto p : v) cout << p << ",";
    cout << "]";
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &os, const set<T> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
template<typename T, typename V>
ostream &operator<<(ostream &os, const map<T, V> v) {
    cout << "{";
    for (auto p : v) cout << p << ",";
    cout << "}";
    return os;
}
 
#ifndef __SOULTCH
#define debug(...) 0
#define endl '\n'
#else
#define debug(...) cout << " [-] ", _dbg(#__VA_ARGS__, __VA_ARGS__)
template<class TH> void _dbg(const char *sdbg, TH h){ cout << sdbg << '=' << h << endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
    while(*sdbg != ',') cout << *sdbg++;
    cout << '=' << (h) << ','; 
    _dbg(sdbg+1, a...);
}
#endif
 
template<typename T> void get_max(T &a, T b) {a = max(a, b);}
template<typename T> void get_min(T &a, T b) {a = min(a, b);}

int N;

int main(void) {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> N;
    if (N < 3 or (N&-N) == N) return cout << "No" << endl, 0;

    cout << "Yes" << endl;
    cout << 1 << ' ' << 2 << endl;
    cout << 2 << ' ' << 3 << endl;
    cout << 3 << ' ' << N+1 << endl;
    cout << N+1 << ' ' << N+2 << endl;
    cout << N+2 << ' ' << N+3 << endl;

    for (int j = 4; j <= N; j += 2) {
        if (j == N) {
            if (j&2) {
                debug(j);
                cout << N+2 << ' ' << j << endl;
                cout << N+j-1 << ' ' << N+j << endl;
            } else {
                int p = (j&-j)+1;
                cout << p+N << ' ' << j << endl;
                cout << (j^p^1) << ' ' << N+j << endl;
            }
        } else {
            cout << 1 << ' ' << j << endl;
            cout << j << ' ' << j+1 << endl;
            cout << N+1 << ' ' << N+j+1 << endl;
            cout << N+j+1 << ' ' << N+j << endl;
        }
    }
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう
//a=0x61=97 '0'=0x30=48
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long  ll;
typedef long double  ld;
typedef string str;
typedef pair<int,int> pairii;
typedef vector<char> vecc;
const double pi=3.1415926535;
const ll  mod=1000000007;
//桁数指定　cout << fixed << setprecision(2)
int main() {
  int n;    int cnt=0;
  cin>>n;
  vecc v(n);
  {rep(i,n)cin>>v[i];}
  vecc vs(n);
    vs=v;
  sort(v.begin(),v.end());
  rep(i,n){
    if(v[i]!=vs[i])cnt++;}
  cnt/=2;
  cout<<cnt<<endl;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
vector<int> c(26);
vector<vector<int>> s(365, vector<int>(26, 0));
vector<int> last(26, -1);
int main() {
    int d;
    cin >> d;
    for(int i = 0; i < 26; i++) {
        cin >> c[i];
    }
    for(int i = 0; i < d; i++) {
        for(int j = 0; j < 26; j++) {
            cin >> s[i][j];
        }
    }
    vector<int> t(d, -1);
    vector<pair<int, int>> arg(26);
    for(int i = 0; i < 26; i++) {
        arg[i].first = -c[i];
        arg[i].second = i;
    }
    sort(all(arg));
    for(int i = 0; i < d; i++) {
        t[i] = arg[i % d].second;
        cout << t[i] + 1 << endl;
    }
}

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

int N;
ll A[110000];

int main(){
  cin >> N;
  rep(i, N) cin >> A[i];
  sort(A, A + N);
  if (A[0] == 0){
    cout << 0 << endl;
    return 0;
  }
  ll ans = 1;
  rep(i, N){
    if (A[i] > 1000000000000000000 / ans){
      cout << -1 << endl;
      return 0;
    }
    ans *= A[i];
  }
  cout << ans << endl;
}


Measured memory_bytes: 4388
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL a[10][10], sum;
int n, m;
void debug() {
	for(int i = 1; i <= 9; i++) {
		for(int j = 1; j <= 9; j++) {
			printf("%lld ", a[i][j]);
		}
		printf("\n");
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i = 0; i <= 9; i++)
		for(int j = 0; j <= 9; j++)
			scanf("%lld", &a[i][j]);
	//debug();
	for(int k = 0; k <= 9; k++)
		for(int i = 0; i <= 9; i++)
			for(int j = 0; j <= 9; j++)
				if(i != j && j != k)
				a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
	//printf("----------\n");
	//debug();
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			int t;
			scanf("%d", &t);
			if(t != 1 && t != -1)sum += a[t][1];
		}
	printf("%lld\n", sum);
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main(){
	string s;cin>>s;
	int x=s.size();
	s.PB('1');
	vl a(x+1,INF);
	ll cnt1=0,cnt2=0,ans=0;
	for(int i=0;i<x;++i){
		if(s[i]=='<'){
			cnt1++;
		}
        else{
			cnt2++;
		}
		if(s[i]=='>'&&s[i+1]=='<'){
			ll M=max(cnt1,cnt2),m=min(cnt1,cnt2);
			ans+=M*(M+1)/2+m*(m-1)/2;
			cnt1=0;cnt2=0;
		}
	}
	ll M=max(cnt1,cnt2),m=min(cnt1,cnt2);
	ans+=M*(M+1)/2+m*(m-1)/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 4740
#pragma warning(disable:4996)
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;
TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM V, TNM H> void resize(vector<V>& v, const H h) { v.resize(h); }
TPL<TNM V, TNM H, TNM ... T> inline void resize(vector<V>& v, const H& h, const T ... t) { v.resize(h); for (auto& _v : v) resize(_v, t ...); }
TPL<TNM V, TNM T> void fill(V& x, const T& val) { x = val; }
TPL<TNM V, TNM T> inline void fill(vector<V>& vec, const T& val) { for (auto& v : vec) fill(v, val); }
TPL<TNM T> inline void UNIQUE(vector<T>& vec) { sort(ALL(vec)); vec.erase(unique(ALL(vec)), vec.end()); }

inline bool range1d(int x, int W) { return (x >= 0) && (W > x); }
const int dx[] = { 1, -1, 4, -4 }; //左右上下

struct Node {
	string s;
	int c;
	Node(string _s, int _c) : s(_s), c(_c) {};
};

int main(void) {
	map<string, int> memo;
	queue<Node> q;
	q.push({ "01234567", 0 });
	while (q.size()) {
		Node v = q.front(); q.pop();
		if (memo.count(v.s) != 0)continue;
		memo[v.s] = v.c;
		REP(i, 4) {
			int id = v.s.find('0');
			if (i == 0 && id == 3)continue;
			if (i == 1 && id == 4)continue;
			string t = v.s;
			if (range1d(id + dx[i], 8)) {
				swap(t[id], t[id + dx[i]]);
				q.push({ t, v.c + 1 });
			}
		}
	}
	char c;
	while (cin >> c) {
		string S = "";
		S += c;
		REP(i, 7) {
			cin >> c;
			S += c;
		}
		cout << memo[S] << endl;
	}
	return 0;
}


Measured memory_bytes: 5444
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')


def solve():
    N = int(input())
    S = []
    R = []
    C = []
    for _ in range(N):
        s, c = input().strip().split()
        S.append(s)
        R.append(s[::-1])
        C.append(int(c))
    
    vis = set()
    mem = dict()

    def dp(s, p):
        if (s, p) in mem: return mem[s, p]
        if s == s[::-1]: return 0
        if (s, p) in vis: return INF

        ans = INF
        vis.add((s, p))
        for i, t in enumerate(S if p else R):
            if len(t) >= len(s) and t.startswith(s):
                ans = min(ans, dp(t[len(s):], p ^ 1) + C[i])
            elif len(s) > len(t) and s.startswith(t):
                ans = min(ans, dp(s[len(t):], p) + C[i])
        vis.discard((s, p))
        mem[s, p] = ans
        return ans
        
    ans = INF
    for i in range(N):
        ans = min(ans, dp(S[i], 0) + C[i])
    return -1 if ans == INF else ans


if __name__ == '__main__':
    ans = solve()
    print(ans)

Measured memory_bytes: 9164
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

int main() {

    string S;
    cin >> S;
    int Slong = S.size(), j = 0, stlong, ans = 0, k, cnt = 0;
    vector<int> st(0);

    for(int i = 0;i < Slong;i++){
        if(S[i] == 'T'){
            st.push_back(i);
            j++;
        }
    }
    stlong = st.size();

    for(int i = 0;i < Slong ;i++){
        cnt = i;
        for(int j = i;j < Slong;j++){
            if(S[j] == 'A' || S[j] == 'T' || S[j] == 'C' || S[j] == 'G'){
                cnt++;
            }
            if(cnt == j + 1){
                if(cnt == Slong){
                    ans = max(ans,cnt - i);
                }
            }
            else{
                ans = max(ans,cnt - i);
                break;
            }
        }
    }

    cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;

struct edge{int to;ll dist;};
vector<vector<edge>> G;
vec v;
void dfs(int s,int par){
    for(auto e:G[s]){
        if(e.to==par)continue;
        v[e.to]=v[s]+e.dist;
        dfs(e.to,s);
    }
}

int main(){
    G.resize(100010);
    v.resize(100010);
    int N;cin>>N;
    int a,b;ll c;
    for(int i=1;i<=N-1;i++){
        cin>>a>>b>>c;
        G[a].push_back((edge){b,c});
        G[b].push_back((edge){a,c});
    }
    int Q,K;cin>>Q>>K;
    v[K]=0;dfs(K,0);
    int x,y;
    for(int i=0;i<Q;i++){
        cin>>x>>y;
        cout<<v[x]+v[y]<<endl;
    }
    return 0;
}

Measured memory_bytes: 14336
#include<bits/stdc++.h>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define mp make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n,a[15],x[15][15],y[15][15];
int main(){
	cin>>n;
	rep(i,n){
		cin>>a[i];
		rep(j,a[i]){
			cin>>x[i][j]>>y[i][j];
			x[i][j]--;
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		bool f[15];
		zero(f);
		int h[15];
		memset(h,-1,sizeof(h));
		int ans1=0;
		for(int j=0;j<n;j++){
			if(i&(1<<j))
			f[j]=true,ans1++;
		}
		bool flag=true;
		for(int j=0;j<n;j++){
			if(f[j]){
				for(int k=0;k<a[j];k++){
					if(y[j][k]!=f[x[j][k]]){
						flag=false;
						break;
					}
				}	
			}else{
				int c=0;
				for(int k=0;k<a[j];k++){
					if(y[j][k]!=f[x[j][k]])
					c++;
				}
				if(c==0)
				flag=false;
			}
		}
		if(flag){
			ans=max(ans,ans1);
		}
	}
	cout<<ans;
	re 0;
}


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

int main() {
    int a, b; cin >> a >> b;
    int x;
    
    if (a > b) {
        x = a;
        a--;
    }
    else {
        x = b;
        b--;
    }
    x+= max(a, b);
    cout << x << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  int a, b, c;
  cin >> a >> b >> c;
  if(a+b+c>=22) co("bust");
  else co("win");
  
  return 0;
}

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


f = [c]
x = 1000000
k = [c, d]

while x != 0:
    x = max(k) % min(k)

    if x != 0:
        f.append(x)
    k.sort()
    k[1] = x
#print(min(f))

cc = (b // c)- ((a - 1) // c)
dd = (b // d)- ((a - 1) // d)
cd =(b // (c * d // min(f)))- ((a - 1) // (c * d // min(f)))
#print(cc,"cc")
#print(dd,"dd")
#print(cd,"cd")

print(int(b - a + 1 - cc - dd + cd))

Measured memory_bytes: 3064
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;


int main(){
	int a[3];
	scanf("%d%d%d", &a[0], &a[1], &a[2]);
	int cnt5 = 0, cnt7 = 0;
	for (int i = 0; i < 3; i++){
		if (a[i] == 5)cnt5++;
		if (a[i] == 7)cnt7++;
	}
	puts(cnt5 == 2 && cnt7 == 1 ? "YES" : "NO");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

long long n,dp1[100005][2],x[100005],y[100005],bitx[100005],bity[100005],a,b,t[100005],p[100005],q[100005],mod=1e9+7,dp2[100005][2];

void UpdX(long long nod, long long v){
    while(nod<=n+1){
        bitx[nod]+=v;
        bitx[nod]%=mod;
        nod+=(nod&-nod);
    }
}

void UpdY(long long nod, long long v){
    while(nod<=n+1){
        bity[nod]+=v;
        bity[nod]%=mod;
        nod+=(nod&-nod);
    }
}

long long SumX(long long nod){
    long long ans=0;
    while(nod){
        ans+=bitx[nod];
        ans%=mod;
        nod-=(nod&-nod);
    }
    return ans;
}

long long QryX(long long l, long long r){
    if(l>r) return 0;
    if(l<=1) return SumX(r);
    else return ((SumX(r)-SumX(l-1))%mod+mod)%mod;
}

long long SumY(long long nod){
    long long ans=0;
    while(nod){
        ans+=bity[nod];
        ans%=mod;
        nod-=(nod&-nod);
    }
    return ans;
}

long long QryY(long long l, long long r){
    if(l>r) return 0;
    if(r<1) return 0;
    if(l<=1) return SumY(r);
    else return ((SumY(r)-SumY(l-1))%mod+mod)%mod;
}

int main() {
    cin >> n >> a >> b;
    for(int i=1;i<=n;i++) cin >> t[i];
    x[1]=1; y[1]=1; p[1]=0; q[1]=0;
    for(int i=2;i<=n;i++){
        if(t[i]-t[i-1]>=a) x[i]=x[i-1];
        else x[i]=i;
        if(t[i]-t[i-1]>=b) y[i]=y[i-1];
        else y[i]=i;
        p[i]=p[i-1];
        while(t[i]-t[p[i]+1]>=a) p[i]++;
        q[i]=q[i-1];
        while(t[i]-t[q[i]+1]>=b) q[i]++;
        //cout << x[i] << ' ' << y[i] << ' ' << p[i] << ' ' << q[i] << '\n';
    }
    dp1[0][0]=1; dp1[0][1]=1; dp2[0][0]=1; dp2[0][1]=1;
    UpdX(1,1); UpdY(1,1);
    dp1[1][0]=1; dp1[1][1]=1; dp2[1][0]=1; dp2[1][1]=1;
    UpdX(2,1); UpdY(2,1);
    for(long long i=2;i<=n;i++){
        if(t[i]-t[i-1]>=a) dp1[i][0]+=dp1[i-1][0];
        dp1[i][0]+=QryX(y[i-1],min(p[i],i-2)+1);
        if(i<n) dp2[i][0]+=QryY(x[i],min(q[i+1],i-1)+1);
        dp1[i][0]%=mod; dp2[i][0]%=mod;
        UpdX(i+1,dp2[i][0]);
        if(t[i]-t[i-1]>=b) dp1[i][1]+=dp1[i-1][1];
        dp1[i][1]+=QryY(x[i-1],min(q[i],i-2)+1);
        if(i<n) dp2[i][1]+=QryX(y[i],min(p[i+1],i-1)+1);
        dp1[i][1]%=mod; dp2[i][1]%=mod;
        UpdY(i+1,dp2[i][1]);
        //cout << dp1[i][0] << ' ' << dp2[i][0] << ' ' << dp1[i][1] << ' ' << dp2[i][1] << '\n';
    }
    cout << (dp1[n][0]+dp1[n][1])%mod;
}


Measured memory_bytes: 8832
Q, H, S, D = map(int, input().split())
N = int(input())

ans = (N // 2) * min(Q * 8, H * 4, S * 2, D)
if N % 2 == 0:
    print(ans)
else:
    ans += min(Q * 4, H * 2, S)
    print(ans)


Measured memory_bytes: 2940